Scippy

SCIP

Solving Constraint Integer Programs

heur_zeroobj.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_zeroobj.c
17  * @brief heuristic that tries to solve the problem without objective. In Gurobi, this heuristic is known as "Hail Mary"
18  * @author Timo Berthold
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <assert.h>
24 #include <string.h>
25 
26 #include "scip/heur_zeroobj.h"
27 #include "scip/cons_linear.h"
28 
29 #define HEUR_NAME "zeroobj"
30 #define HEUR_DESC "heuristic trying to solve the problem without objective"
31 #define HEUR_DISPCHAR 'Z'
32 #define HEUR_PRIORITY 100
33 #define HEUR_FREQ -1
34 #define HEUR_FREQOFS 0
35 #define HEUR_MAXDEPTH 0
36 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_BEFOREPRESOL
37 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
38 
39 /* event handler properties */
40 #define EVENTHDLR_NAME "Zeroobj"
41 #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic"
42 
43 /* default values for zeroobj-specific plugins */
44 #define DEFAULT_MAXNODES 1000LL /* maximum number of nodes to regard in the subproblem */
45 #define DEFAULT_MINIMPROVE 0.01 /* factor by which zeroobj should at least improve the incumbent */
46 #define DEFAULT_MINNODES 100LL /* minimum number of nodes to regard in the subproblem */
47 #define DEFAULT_MAXLPITERS 5000LL /* maximum number of LP iterations to be performed in the subproblem */
48 #define DEFAULT_NODESOFS 100LL /* number of nodes added to the contingent of the total nodes */
49 #define DEFAULT_NODESQUOT 0.1 /* subproblem nodes in relation to nodes of the original problem */
50 #define DEFAULT_ADDALLSOLS FALSE /* should all subproblem solutions be added to the original SCIP? */
51 #define DEFAULT_ONLYWITHOUTSOL TRUE /**< should heuristic only be executed if no primal solution was found, yet? */
52 #define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */
53 
54 /*
55  * Data structures
56  */
57 
58 /** primal heuristic data */
59 struct SCIP_HeurData
60 {
61  SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
62  SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
63  SCIP_Longint maxlpiters; /**< maximum number of LP iterations to be performed in the subproblem */
64  SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
65  SCIP_Longint usednodes; /**< nodes already used by zeroobj in earlier calls */
66  SCIP_Real minimprove; /**< factor by which zeroobj should at least improve the incumbent */
67  SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
68  SCIP_Bool addallsols; /**< should all subproblem solutions be added to the original SCIP? */
69  SCIP_Bool onlywithoutsol; /**< should heuristic only be executed if no primal solution was found, yet? */
70  SCIP_Bool useuct; /**< should uct node selection be used at the beginning of the search? */
71 };
72 
73 
74 /*
75  * Local methods
76  */
77 
78 /** creates a new solution for the original problem by copying the solution of the subproblem */
79 static
81  SCIP* scip, /**< original SCIP data structure */
82  SCIP* subscip, /**< SCIP structure of the subproblem */
83  SCIP_VAR** subvars, /**< the variables of the subproblem */
84  SCIP_HEUR* heur, /**< zeroobj heuristic structure */
85  SCIP_SOL* subsol, /**< solution of the subproblem */
86  SCIP_Bool* success /**< used to store whether new solution was found or not */
87  )
88 {
89  SCIP_VAR** vars; /* the original problem's variables */
90  int nvars; /* the original problem's number of variables */
91  SCIP_Real* subsolvals; /* solution values of the subproblem */
92  SCIP_SOL* newsol; /* solution to be created for the original problem */
93 
94  assert(scip != NULL);
95  assert(subscip != NULL);
96  assert(subvars != NULL);
97  assert(subsol != NULL);
98 
99  /* get variables' data */
100  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
101 
102  /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
103  * since constraint copying may have required the copy of variables that are fixed in the main SCIP
104  */
105  assert(nvars <= SCIPgetNOrigVars(subscip));
106 
107  SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
108 
109  /* copy the solution */
110  SCIP_CALL( SCIPgetSolVals(subscip, subsol, nvars, subvars, subsolvals) );
111 
112  /* create new solution for the original problem */
113  SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
114  SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
115 
116  /* try to add new solution to scip and free it immediately */
117  SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
118 
119  SCIPfreeBufferArray(scip, &subsolvals);
120 
121  return SCIP_OKAY;
122 }
123 
124 /* ---------------- Callback methods of event handler ---------------- */
125 
126 /* exec the event handler
127  *
128  * we interrupt the solution process
129  */
130 static
131 SCIP_DECL_EVENTEXEC(eventExecZeroobj)
132 {
133  SCIP_HEURDATA* heurdata;
134 
135  assert(eventhdlr != NULL);
136  assert(eventdata != NULL);
137  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
138  assert(event != NULL);
140 
141  heurdata = (SCIP_HEURDATA*)eventdata;
142  assert(heurdata != NULL);
143 
144  /* interrupt solution process of sub-SCIP */
145  if( SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_ITERLIMIT || SCIPgetNLPIterations(scip) >= heurdata->maxlpiters )
146  {
148  }
149 
150  return SCIP_OKAY;
151 }
152 /* ---------------- Callback methods of primal heuristic ---------------- */
153 
154 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
155 static
156 SCIP_DECL_HEURCOPY(heurCopyZeroobj)
157 { /*lint --e{715}*/
158  assert(scip != NULL);
159  assert(heur != NULL);
160  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
161 
162  /* call inclusion method of primal heuristic */
164 
165  return SCIP_OKAY;
166 }
167 
168 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
169 static
170 SCIP_DECL_HEURFREE(heurFreeZeroobj)
171 { /*lint --e{715}*/
172  SCIP_HEURDATA* heurdata;
173 
174  assert( heur != NULL );
175  assert( scip != NULL );
176 
177  /* get heuristic data */
178  heurdata = SCIPheurGetData(heur);
179  assert( heurdata != NULL );
180 
181  /* free heuristic data */
182  SCIPfreeBlockMemory(scip, &heurdata);
183  SCIPheurSetData(heur, NULL);
184 
185  return SCIP_OKAY;
186 }
187 
188 
189 /** initialization method of primal heuristic (called after problem was transformed) */
190 static
191 SCIP_DECL_HEURINIT(heurInitZeroobj)
192 { /*lint --e{715}*/
193  SCIP_HEURDATA* heurdata;
194 
195  assert( heur != NULL );
196  assert( scip != NULL );
197 
198  /* get heuristic data */
199  heurdata = SCIPheurGetData(heur);
200  assert( heurdata != NULL );
201 
202  /* initialize data */
203  heurdata->usednodes = 0;
204 
205  return SCIP_OKAY;
206 }
207 
208 
209 /** execution method of primal heuristic */
210 static
211 SCIP_DECL_HEUREXEC(heurExecZeroobj)
212 { /*lint --e{715}*/
213 
214  SCIP_HEURDATA* heurdata; /* heuristic's data */
215  SCIP_Longint nnodes; /* number of stalling nodes for the subproblem */
216 
217  assert( heur != NULL );
218  assert( scip != NULL );
219  assert( result != NULL );
220 
221  /* get heuristic data */
222  heurdata = SCIPheurGetData(heur);
223  assert( heurdata != NULL );
224 
225  /* calculate the maximal number of branching nodes until heuristic is aborted */
226  nnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
227 
228  /* reward zeroobj if it succeeded often */
229  nnodes = (SCIP_Longint)(nnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
230  nnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-SCIP as 100 nodes */
231  nnodes += heurdata->nodesofs;
232 
233  /* determine the node limit for the current process */
234  nnodes -= heurdata->usednodes;
235  nnodes = MIN(nnodes, heurdata->maxnodes);
236 
237  /* check whether we have enough nodes left to call subproblem solving */
238  if( nnodes < heurdata->minnodes )
239  {
240  SCIPdebugMsg(scip, "skipping zeroobj: nnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nnodes, heurdata->minnodes);
241  return SCIP_OKAY;
242  }
243 
244  /* do not run zeroobj, if the problem does not have an objective function anyway */
245  if( SCIPgetNObjVars(scip) == 0 )
246  {
247  SCIPdebugMsg(scip, "skipping zeroobj: pure feasibility problem anyway\n");
248  return SCIP_OKAY;
249  }
250 
251  if( SCIPisStopped(scip) )
252  return SCIP_OKAY;
253 
254  SCIP_CALL( SCIPapplyZeroobj(scip, heur, result, heurdata->minimprove, nnodes) );
255 
256  return SCIP_OKAY;
257 }
258 
259 
260 /*
261  * primal heuristic specific interface methods
262  */
263 
264 
265 /** main procedure of the zeroobj heuristic, creates and solves a sub-SCIP */
267  SCIP* scip, /**< original SCIP data structure */
268  SCIP_HEUR* heur, /**< heuristic data structure */
269  SCIP_RESULT* result, /**< result data structure */
270  SCIP_Real minimprove, /**< factor by which zeroobj should at least improve the incumbent */
271  SCIP_Longint nnodes /**< node limit for the subproblem */
272  )
273 {
274  SCIP* subscip; /* the subproblem created by zeroobj */
275  SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
276  SCIP_VAR** vars; /* original problem's variables */
277  SCIP_VAR** subvars; /* subproblem's variables */
278  SCIP_HEURDATA* heurdata; /* heuristic's private data structure */
279  SCIP_EVENTHDLR* eventhdlr; /* event handler for LP events */
280 
281  SCIP_Real cutoff; /* objective cutoff for the subproblem */
282  SCIP_Real large;
283 
284  int nvars; /* number of original problem's variables */
285  int i;
286 
287  SCIP_Bool success;
288  SCIP_Bool valid;
289  SCIP_SOL** subsols;
290  int nsubsols;
291 
292  assert(scip != NULL);
293  assert(heur != NULL);
294  assert(result != NULL);
295 
296  assert(nnodes >= 0);
297  assert(0.0 <= minimprove && minimprove <= 1.0);
298 
299  *result = SCIP_DIDNOTRUN;
300 
301  /* only call heuristic once at the root */
302  if( SCIPgetDepth(scip) <= 0 && SCIPheurGetNCalls(heur) > 0 )
303  return SCIP_OKAY;
304 
305  /* get heuristic data */
306  heurdata = SCIPheurGetData(heur);
307  assert(heurdata != NULL);
308 
309  /* only call the heuristic if we do not have an incumbent */
310  if( SCIPgetNSolsFound(scip) > 0 && heurdata->onlywithoutsol )
311  return SCIP_OKAY;
312 
313  /* check whether there is enough time and memory left */
314  SCIP_CALL( SCIPcheckCopyLimits(scip, &success) );
315 
316  if( !success )
317  return SCIP_OKAY;
318 
319  *result = SCIP_DIDNOTFIND;
320 
321  /* get variable data */
322  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
323 
324  /* initialize the subproblem */
325  SCIP_CALL( SCIPcreate(&subscip) );
326 
327  /* create the variable mapping hash map */
328  SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
329  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
330 
331  /* different methods to create sub-problem: either copy LP relaxation or the CIP with all constraints */
332  valid = FALSE;
333 
334  /* copy complete SCIP instance */
335  SCIP_CALL( SCIPcopy(scip, subscip, varmapfw, NULL, "zeroobj", TRUE, FALSE, TRUE, &valid) );
336  SCIPdebugMsg(scip, "Copying the SCIP instance was %s complete.\n", valid ? "" : "not ");
337 
338  /* create event handler for LP events */
339  eventhdlr = NULL;
340  SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecZeroobj, NULL) );
341  if( eventhdlr == NULL )
342  {
343  SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
344  return SCIP_PLUGINNOTFOUND;
345  }
346 
347  /* determine large value to set variables to */
348  large = SCIPinfinity(scip);
349  if( !SCIPisInfinity(scip, 0.1 / SCIPfeastol(scip)) )
350  large = 0.1 / SCIPfeastol(scip);
351 
352  /* get variable image and change to 0.0 in sub-SCIP */
353  for( i = 0; i < nvars; i++ )
354  {
355  SCIP_Real adjustedbound;
356  SCIP_Real lb;
357  SCIP_Real ub;
358  SCIP_Real inf;
359 
360  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
361  SCIP_CALL( SCIPchgVarObj(subscip, subvars[i], 0.0) );
362 
363  lb = SCIPvarGetLbGlobal(subvars[i]);
364  ub = SCIPvarGetUbGlobal(subvars[i]);
365  inf = SCIPinfinity(subscip);
366 
367  /* adjust infinite bounds in order to avoid that variables with non-zero objective
368  * get fixed to infinite value in zeroobj subproblem
369  */
370  if( SCIPisInfinity(subscip, ub ) )
371  {
372  adjustedbound = MAX(large, lb+large);
373  adjustedbound = MIN(adjustedbound, inf);
374  SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], adjustedbound) );
375  }
376  if( SCIPisInfinity(subscip, -lb ) )
377  {
378  adjustedbound = MIN(-large, ub-large);
379  adjustedbound = MAX(adjustedbound, -inf);
380  SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], adjustedbound) );
381  }
382  }
383 
384  /* free hash map */
385  SCIPhashmapFree(&varmapfw);
386 
387  /* do not abort subproblem on CTRL-C */
388  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
389 
390 #ifdef SCIP_DEBUG
391  /* for debugging, enable full output */
392  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
393  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
394 #else
395  /* disable statistic timing inside sub SCIP and output to console */
396  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
397  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
398 #endif
399 
400  /* set limits for the subproblem */
401  SCIP_CALL( SCIPcopyLimits(scip, subscip) );
402  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nnodes) );
403  SCIP_CALL( SCIPsetIntParam(subscip, "limits/solutions", 1) );
404 
405  /* forbid recursive call of heuristics and separators solving sub-SCIPs */
406  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
407 
408  /* disable expensive techniques that merely work on the dual bound */
409 
410  /* disable cutting plane separation */
412 
413  /* disable expensive presolving */
415  if( !SCIPisParamFixed(subscip, "presolving/maxrounds") )
416  {
417  SCIP_CALL( SCIPsetIntParam(subscip, "presolving/maxrounds", 50) );
418  }
419 
420  /* use restart dfs node selection */
421  if( SCIPfindNodesel(subscip, "restartdfs") != NULL && !SCIPisParamFixed(subscip, "nodeselection/restartdfs/stdpriority") )
422  {
423  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/restartdfs/stdpriority", INT_MAX/4) );
424  }
425 
426  /* activate uct node selection at the top of the tree */
427  if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") )
428  {
429  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) );
430  }
431  /* use least infeasible branching */
432  if( SCIPfindBranchrule(subscip, "leastinf") != NULL && !SCIPisParamFixed(subscip, "branching/leastinf/priority") )
433  {
434  SCIP_CALL( SCIPsetIntParam(subscip, "branching/leastinf/priority", INT_MAX/4) );
435  }
436 
437  /* employ a limit on the number of enforcement rounds in the quadratic constraint handler; this fixes the issue that
438  * sometimes the quadratic constraint handler needs hundreds or thousands of enforcement rounds to determine the
439  * feasibility status of a single node without fractional branching candidates by separation (namely for uflquad
440  * instances); however, the solution status of the sub-SCIP might get corrupted by this; hence no deductions shall be
441  * made for the original SCIP
442  */
443  if( SCIPfindConshdlr(subscip, "quadratic") != NULL && !SCIPisParamFixed(subscip, "constraints/quadratic/enfolplimit") )
444  {
445  SCIP_CALL( SCIPsetIntParam(subscip, "constraints/quadratic/enfolplimit", 10) );
446  }
447 
448  /* disable feaspump and fracdiving */
449  if( !SCIPisParamFixed(subscip, "heuristics/feaspump/freq") )
450  {
451  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/feaspump/freq", -1) );
452  }
453  if( !SCIPisParamFixed(subscip, "heuristics/fracdiving/freq") )
454  {
455  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/fracdiving/freq", -1) );
456  }
457 
458  /* speed up sub-SCIP by not checking dual LP feasibility */
459  SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
460 
461  /* restrict LP iterations */
462  SCIP_CALL( SCIPsetLongintParam(subscip, "lp/iterlim", 2*heurdata->maxlpiters / MAX(1,nnodes)) );
463  SCIP_CALL( SCIPsetLongintParam(subscip, "lp/rootiterlim", heurdata->maxlpiters) );
464 
465  /* if there is already a solution, add an objective cutoff */
466  if( SCIPgetNSols(scip) > 0 )
467  {
468  SCIP_Real upperbound;
469  SCIP_CONS* origobjcons;
470 #ifndef NDEBUG
471  int nobjvars;
472  nobjvars = 0;
473 #endif
474 
475  assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
476 
477  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
478 
479  if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(scip)) )
480  {
481  cutoff = (1-minimprove)*SCIPgetUpperbound(scip) + minimprove*SCIPgetLowerbound(scip);
482  }
483  else
484  {
485  if( SCIPgetUpperbound(scip) >= 0 )
486  cutoff = ( 1 - minimprove ) * SCIPgetUpperbound ( scip );
487  else
488  cutoff = ( 1 + minimprove ) * SCIPgetUpperbound ( scip );
489  }
490  cutoff = MIN(upperbound, cutoff);
491 
492  SCIP_CALL( SCIPcreateConsLinear(subscip, &origobjcons, "objbound_of_origscip", 0, NULL, NULL, -SCIPinfinity(subscip), cutoff,
494  for( i = 0; i < nvars; ++i)
495  {
496  if( !SCIPisFeasZero(subscip, SCIPvarGetObj(vars[i])) )
497  {
498  SCIP_CALL( SCIPaddCoefLinear(subscip, origobjcons, subvars[i], SCIPvarGetObj(vars[i])) );
499 #ifndef NDEBUG
500  nobjvars++;
501 #endif
502  }
503  }
504  SCIP_CALL( SCIPaddCons(subscip, origobjcons) );
505  SCIP_CALL( SCIPreleaseCons(subscip, &origobjcons) );
506  assert(nobjvars == SCIPgetNObjVars(scip));
507  }
508 
509  /* catch LP events of sub-SCIP */
510  SCIP_CALL( SCIPtransformProb(subscip) );
511  SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_NODESOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
512 
513  SCIPdebugMsg(scip, "solving subproblem: nnodes=%" SCIP_LONGINT_FORMAT "\n", nnodes);
514 
515  /* drop LP events of sub-SCIP */
516  SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_NODESOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
517 
518  /* errors in solving the subproblem should not kill the overall solving process;
519  * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
520  */
521  SCIP_CALL_ABORT( SCIPsolve(subscip) );
522 
523  /* check, whether a solution was found;
524  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
525  */
526  nsubsols = SCIPgetNSols(subscip);
527  subsols = SCIPgetSols(subscip);
528  success = FALSE;
529  for( i = 0; i < nsubsols && (!success || heurdata->addallsols); ++i )
530  {
531  SCIP_CALL( createNewSol(scip, subscip, subvars, heur, subsols[i], &success) );
532  if( success )
533  *result = SCIP_FOUNDSOL;
534  }
535 
536 #ifdef SCIP_DEBUG
537  SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
538 #endif
539 
540  /* free subproblem */
541  SCIPfreeBufferArray(scip, &subvars);
542  SCIP_CALL( SCIPfree(&subscip) );
543 
544  return SCIP_OKAY;
545 }
546 
547 
548 /** creates the zeroobj primal heuristic and includes it in SCIP */
550  SCIP* scip /**< SCIP data structure */
551  )
552 {
553  SCIP_HEURDATA* heurdata;
554  SCIP_HEUR* heur;
555 
556  /* create heuristic data */
557  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
558 
559  /* include primal heuristic */
560  heur = NULL;
561  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
563  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecZeroobj, heurdata) );
564  assert(heur != NULL);
565 
566  /* set non-NULL pointers to callback methods */
567  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyZeroobj) );
568  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeZeroobj) );
569  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitZeroobj) );
570 
571  /* add zeroobj primal heuristic parameters */
572  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
573  "maximum number of nodes to regard in the subproblem",
574  &heurdata->maxnodes, TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
575 
576  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
577  "number of nodes added to the contingent of the total nodes",
578  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
579 
580  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
581  "minimum number of nodes required to start the subproblem",
582  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
583 
584  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxlpiters",
585  "maximum number of LP iterations to be performed in the subproblem",
586  &heurdata->maxlpiters, TRUE, DEFAULT_MAXLPITERS, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
587 
588  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
589  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
590  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
591 
592  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
593  "factor by which zeroobj should at least improve the incumbent",
594  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
595 
596  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/addallsols",
597  "should all subproblem solutions be added to the original SCIP?",
598  &heurdata->addallsols, TRUE, DEFAULT_ADDALLSOLS, NULL, NULL) );
599 
600  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlywithoutsol",
601  "should heuristic only be executed if no primal solution was found, yet?",
602  &heurdata->onlywithoutsol, TRUE, DEFAULT_ONLYWITHOUTSOL, NULL, NULL) );
603  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct",
604  "should uct node selection be used at the beginning of the search?",
605  &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) );
606 
607  return SCIP_OKAY;
608 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
#define HEUR_FREQ
Definition: heur_zeroobj.c:33
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:46385
#define DEFAULT_MAXLPITERS
Definition: heur_zeroobj.c:47
SCIP_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:21971
#define DEFAULT_NODESOFS
Definition: heur_zeroobj.c:48
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5130
SCIP_Real SCIPfeastol(SCIP *scip)
Definition: scip.c:45508
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip.c:41609
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6576
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17169
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1327
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
Definition: scip.c:42891
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip.c:12120
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip.c:8561
static SCIP_DECL_HEURINIT(heurInitZeroobj)
Definition: heur_zeroobj.c:191
#define HEUR_FREQOFS
Definition: heur_zeroobj.c:34
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11554
#define DEFAULT_ADDALLSOLS
Definition: heur_zeroobj.c:50
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip.c:39108
#define FALSE
Definition: def.h:64
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2764
SCIP_RETCODE SCIPapplyZeroobj(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real minimprove, SCIP_Longint nnodes)
Definition: heur_zeroobj.c:266
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:278
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4265
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip.c:4164
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:46050
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5104
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip.c:9219
#define DEFAULT_USEUCT
Definition: heur_zeroobj.c:52
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21973
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip.c:8034
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2902
#define SCIP_LONGINT_MAX
Definition: def.h:131
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22003
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip.c:696
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1102
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21956
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:22058
#define SCIPdebugMsg
Definition: scip.h:451
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
Definition: scip.c:44659
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
#define DEFAULT_ONLYWITHOUTSOL
Definition: heur_zeroobj.c:51
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17179
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip.c:15846
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1181
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip.c:4373
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:12459
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip.c:8095
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:38219
static SCIP_DECL_HEURCOPY(heurCopyZeroobj)
Definition: heur_zeroobj.c:156
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip.c:4602
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:45753
#define EVENTHDLR_NAME
Definition: heur_zeroobj.c:40
SCIP_RETCODE SCIPincludeHeurZeroobj(SCIP *scip)
Definition: heur_zeroobj.c:549
#define DEFAULT_MINIMPROVE
Definition: heur_zeroobj.c:45
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:155
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2797
#define NULL
Definition: lpi_spx1.cpp:137
#define SCIP_CALL(x)
Definition: def.h:316
SCIP_Real SCIPgetLowerbound(SCIP *scip)
Definition: scip.c:42550
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1307
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip.c:21542
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21991
#define SCIP_Bool
Definition: def.h:61
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip.c:40434
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:28948
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:959
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool *success)
Definition: heur_zeroobj.c:80
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:42321
#define DEFAULT_MAXNODES
Definition: heur_zeroobj.c:44
#define MAX(x, y)
Definition: tclique_def.h:75
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip.c:40070
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip.c:4660
#define HEUR_PRIORITY
Definition: heur_zeroobj.c:32
#define HEUR_TIMING
Definition: heur_zeroobj.c:36
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip.c:40468
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17017
int SCIPgetNSols(SCIP *scip)
Definition: scip.c:39059
static SCIP_DECL_EVENTEXEC(eventExecZeroobj)
Definition: heur_zeroobj.c:131
Constraint handler for linear constraints in their most general form, .
int SCIPgetNObjVars(SCIP *scip)
Definition: scip.c:11908
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:46061
#define SCIP_EVENTTYPE_NODESOLVED
Definition: type_event.h:119
#define DEFAULT_NODESQUOT
Definition: heur_zeroobj.c:49
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
static SCIP_DECL_HEURFREE(heurFreeZeroobj)
Definition: heur_zeroobj.c:170
static SCIP_DECL_HEUREXEC(heurExecZeroobj)
Definition: heur_zeroobj.c:211
#define HEUR_NAME
Definition: heur_zeroobj.c:29
heuristic that tries to solve the problem without objective. In Gurobi, this heuristic is known as "H...
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip.c:27417
#define HEUR_DISPCHAR
Definition: heur_zeroobj.c:31
SCIP_RETCODE SCIPcopy(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip.c:3767
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip.c:8111
#define HEUR_USESSUBSCIP
Definition: heur_zeroobj.c:37
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip.c:8907
#define SCIP_Real
Definition: def.h:145
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
#define HEUR_DESC
Definition: heur_zeroobj.c:30
#define MIN(x, y)
Definition: memory.c:75
#define HEUR_MAXDEPTH
Definition: heur_zeroobj.c:35
#define SCIP_Longint
Definition: def.h:130
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip.c:4128
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:38084
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip.c:13717
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip.c:8079
#define nnodes
Definition: gastrans.c:65
SCIP_Real SCIPsumepsilon(SCIP *scip)
Definition: scip.c:45494
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
Definition: scip.c:17019
SCIP_Real SCIPgetUpperbound(SCIP *scip)
Definition: scip.c:42699
#define SCIP_CALL_ABORT(x)
Definition: def.h:295
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1092
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:41409
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4293
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip.c:5055
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip.c:4718
#define DEFAULT_MINNODES
Definition: heur_zeroobj.c:46
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4211
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip.c:774
#define EVENTHDLR_DESC
Definition: heur_zeroobj.c:41
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37178