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-2014 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 
53 /*
54  * Data structures
55  */
56 
57 /** primal heuristic data */
58 struct SCIP_HeurData
59 {
60  SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
61  SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
62  SCIP_Longint maxlpiters; /**< maximum number of LP iterations to be performed in the subproblem */
63  SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
64  SCIP_Longint usednodes; /**< nodes already used by zeroobj in earlier calls */
65  SCIP_Real minimprove; /**< factor by which zeroobj should at least improve the incumbent */
66  SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
67  SCIP_Bool addallsols; /**< should all subproblem solutions be added to the original SCIP? */
68  SCIP_Bool onlywithoutsol; /**< should heuristic only be executed if no primal solution was found, yet? */
69 };
70 
71 
72 /*
73  * Local methods
74  */
75 
76 /** creates a new solution for the original problem by copying the solution of the subproblem */
77 static
78 SCIP_RETCODE createNewSol(
79  SCIP* scip, /**< original SCIP data structure */
80  SCIP* subscip, /**< SCIP structure of the subproblem */
81  SCIP_VAR** subvars, /**< the variables of the subproblem */
82  SCIP_HEUR* heur, /**< zeroobj heuristic structure */
83  SCIP_SOL* subsol, /**< solution of the subproblem */
84  SCIP_Bool* success /**< used to store whether new solution was found or not */
85  )
86 {
87  SCIP_VAR** vars; /* the original problem's variables */
88  int nvars; /* the original problem's number of variables */
89  SCIP_Real* subsolvals; /* solution values of the subproblem */
90  SCIP_SOL* newsol; /* solution to be created for the original problem */
91 
92  assert(scip != NULL);
93  assert(subscip != NULL);
94  assert(subvars != NULL);
95  assert(subsol != NULL);
96 
97  /* get variables' data */
98  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
99 
100  /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
101  * since constraint copying may have required the copy of variables that are fixed in the main SCIP
102  */
103  assert(nvars <= SCIPgetNOrigVars(subscip));
104 
105  SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
106 
107  /* copy the solution */
108  SCIP_CALL( SCIPgetSolVals(subscip, subsol, nvars, subvars, subsolvals) );
109 
110  /* create new solution for the original problem */
111  SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
112  SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
113 
114  /* try to add new solution to scip and free it immediately */
115  SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, TRUE, TRUE, TRUE, success) );
116 
117  SCIPfreeBufferArray(scip, &subsolvals);
118 
119  return SCIP_OKAY;
120 }
121 
122 /* ---------------- Callback methods of event handler ---------------- */
123 
124 /* exec the event handler
125  *
126  * we interrupt the solution process
127  */
128 static
129 SCIP_DECL_EVENTEXEC(eventExecZeroobj)
130 {
131  SCIP_HEURDATA* heurdata;
132 
133  assert(eventhdlr != NULL);
134  assert(eventdata != NULL);
135  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
136  assert(event != NULL);
137  assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_NODESOLVED);
138 
139  heurdata = (SCIP_HEURDATA*)eventdata;
140  assert(heurdata != NULL);
141 
142  /* interrupt solution process of sub-SCIP */
143  if( SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_ITERLIMIT || SCIPgetNLPIterations(scip) >= heurdata->maxlpiters )
144  {
145  SCIP_CALL( SCIPinterruptSolve(scip) );
146  }
147 
148  return SCIP_OKAY;
149 }
150 /* ---------------- Callback methods of primal heuristic ---------------- */
151 
152 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
153 static
154 SCIP_DECL_HEURCOPY(heurCopyZeroobj)
155 { /*lint --e{715}*/
156  assert(scip != NULL);
157  assert(heur != NULL);
158  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
159 
160  /* call inclusion method of primal heuristic */
161  SCIP_CALL( SCIPincludeHeurZeroobj(scip) );
162 
163  return SCIP_OKAY;
164 }
165 
166 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
167 static
168 SCIP_DECL_HEURFREE(heurFreeZeroobj)
169 { /*lint --e{715}*/
170  SCIP_HEURDATA* heurdata;
171 
172  assert( heur != NULL );
173  assert( scip != NULL );
174 
175  /* get heuristic data */
176  heurdata = SCIPheurGetData(heur);
177  assert( heurdata != NULL );
178 
179  /* free heuristic data */
180  SCIPfreeMemory(scip, &heurdata);
181  SCIPheurSetData(heur, NULL);
182 
183  return SCIP_OKAY;
184 }
185 
186 
187 /** initialization method of primal heuristic (called after problem was transformed) */
188 static
189 SCIP_DECL_HEURINIT(heurInitZeroobj)
190 { /*lint --e{715}*/
191  SCIP_HEURDATA* heurdata;
192 
193  assert( heur != NULL );
194  assert( scip != NULL );
195 
196  /* get heuristic data */
197  heurdata = SCIPheurGetData(heur);
198  assert( heurdata != NULL );
199 
200  /* initialize data */
201  heurdata->usednodes = 0;
202 
203  return SCIP_OKAY;
204 }
205 
206 
207 /** execution method of primal heuristic */
208 static
209 SCIP_DECL_HEUREXEC(heurExecZeroobj)
210 { /*lint --e{715}*/
211 
212  SCIP_HEURDATA* heurdata; /* heuristic's data */
213  SCIP_Longint nnodes; /* number of stalling nodes for the subproblem */
214 
215  assert( heur != NULL );
216  assert( scip != NULL );
217  assert( result != NULL );
218 
219  /* get heuristic data */
220  heurdata = SCIPheurGetData(heur);
221  assert( heurdata != NULL );
222 
223  /* calculate the maximal number of branching nodes until heuristic is aborted */
224  nnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
225 
226  /* reward zeroobj if it succeeded often */
227  nnodes = (SCIP_Longint)(nnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
228  nnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-SCIP as 100 nodes */
229  nnodes += heurdata->nodesofs;
230 
231  /* determine the node limit for the current process */
232  nnodes -= heurdata->usednodes;
233  nnodes = MIN(nnodes, heurdata->maxnodes);
234 
235  /* check whether we have enough nodes left to call subproblem solving */
236  if( nnodes < heurdata->minnodes )
237  {
238  SCIPdebugMessage("skipping zeroobj: nnodes=%"SCIP_LONGINT_FORMAT", minnodes=%"SCIP_LONGINT_FORMAT"\n", nnodes, heurdata->minnodes);
239  return SCIP_OKAY;
240  }
241 
242  /* do not run zeroobj, if the problem does not have an objective function anyway */
243  if( SCIPgetNObjVars(scip) == 0 )
244  {
245  SCIPdebugMessage("skipping zeroobj: pure feasibility problem anyway\n");
246  return SCIP_OKAY;
247  }
248 
249  if( SCIPisStopped(scip) )
250  return SCIP_OKAY;
251 
252  SCIP_CALL( SCIPapplyZeroobj(scip, heur, result, heurdata->minimprove, nnodes) );
253 
254  return SCIP_OKAY;
255 }
256 
257 
258 /*
259  * primal heuristic specific interface methods
260  */
261 
262 
263 /** main procedure of the zeroobj heuristic, creates and solves a sub-SCIP */
264 SCIP_RETCODE SCIPapplyZeroobj(
265  SCIP* scip, /**< original SCIP data structure */
266  SCIP_HEUR* heur, /**< heuristic data structure */
267  SCIP_RESULT* result, /**< result data structure */
268  SCIP_Real minimprove, /**< factor by which zeroobj should at least improve the incumbent */
269  SCIP_Longint nnodes /**< node limit for the subproblem */
270  )
271 {
272  SCIP* subscip; /* the subproblem created by zeroobj */
273  SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
274  SCIP_VAR** vars; /* original problem's variables */
275  SCIP_VAR** subvars; /* subproblem's variables */
276  SCIP_HEURDATA* heurdata; /* heuristic's private data structure */
277  SCIP_EVENTHDLR* eventhdlr; /* event handler for LP events */
278 
279  SCIP_Real cutoff; /* objective cutoff for the subproblem */
280  SCIP_Real timelimit; /* time limit for zeroobj subproblem */
281  SCIP_Real memorylimit; /* memory limit for zeroobj 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_RETCODE retcode;
290  SCIP_SOL** subsols;
291  int nsubsols;
292 
293  assert(scip != NULL);
294  assert(heur != NULL);
295  assert(result != NULL);
296 
297  assert(nnodes >= 0);
298  assert(0.0 <= minimprove && minimprove <= 1.0);
299 
300  *result = SCIP_DIDNOTRUN;
301 
302  /* only call heuristic once at the root */
303  if( SCIPgetDepth(scip) <= 0 && SCIPheurGetNCalls(heur) > 0 )
304  return SCIP_OKAY;
305 
306  /* get heuristic data */
307  heurdata = SCIPheurGetData(heur);
308  assert(heurdata != NULL);
309 
310  /* only call the heuristic if we do not have an incumbent */
311  if( SCIPgetNSolsFound(scip) > 0 && heurdata->onlywithoutsol )
312  return SCIP_OKAY;
313 
314  /* check whether there is enough time and memory left */
315  timelimit = 0.0;
316  memorylimit = 0.0;
317  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
318  if( !SCIPisInfinity(scip, timelimit) )
319  timelimit -= SCIPgetSolvingTime(scip);
320  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
321 
322  /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
323  if( !SCIPisInfinity(scip, memorylimit) )
324  {
325  memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
326  memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
327  }
328 
329  /* abort if no time is left or not enough memory to create a copy of SCIP, including external memory usage */
330  if( timelimit <= 0.0 || memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 )
331  return SCIP_OKAY;
332 
333  *result = SCIP_DIDNOTFIND;
334 
335  /* get variable data */
336  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
337 
338  /* initialize the subproblem */
339  SCIP_CALL( SCIPcreate(&subscip) );
340 
341  /* create the variable mapping hash map */
342  SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), SCIPcalcHashtableSize(5 * nvars)) );
343  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
344 
345  /* different methods to create sub-problem: either copy LP relaxation or the CIP with all constraints */
346  valid = FALSE;
347 
348  /* copy complete SCIP instance */
349  SCIP_CALL( SCIPcopy(scip, subscip, varmapfw, NULL, "zeroobj", TRUE, FALSE, TRUE, &valid) );
350  SCIPdebugMessage("Copying the SCIP instance was %s complete.\n", valid ? "" : "not ");
351 
352  /* create event handler for LP events */
353  eventhdlr = NULL;
354  SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecZeroobj, NULL) );
355  if( eventhdlr == NULL )
356  {
357  SCIPerrorMessage("event handler for "HEUR_NAME" heuristic not found.\n");
358  return SCIP_PLUGINNOTFOUND;
359  }
360 
361  /* determine large value to set variables to */
362  large = SCIPinfinity(scip);
363  if( !SCIPisInfinity(scip, 0.1 / SCIPfeastol(scip)) )
364  large = 0.1 / SCIPfeastol(scip);
365 
366  /* get variable image and change to 0.0 in sub-SCIP */
367  for( i = 0; i < nvars; i++ )
368  {
369  SCIP_Real adjustedbound;
370  SCIP_Real lb;
371  SCIP_Real ub;
372  SCIP_Real inf;
373 
374  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
375  SCIP_CALL( SCIPchgVarObj(subscip, subvars[i], 0.0) );
376 
377  lb = SCIPvarGetLbGlobal(subvars[i]);
378  ub = SCIPvarGetUbGlobal(subvars[i]);
379  inf = SCIPinfinity(subscip);
380 
381  /* adjust infinite bounds in order to avoid that variables with non-zero objective
382  * get fixed to infinite value in zeroobj subproblem
383  */
384  if( SCIPisInfinity(subscip, ub ) )
385  {
386  adjustedbound = MAX(large, lb+large);
387  adjustedbound = MIN(adjustedbound, inf);
388  SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], adjustedbound) );
389  }
390  if( SCIPisInfinity(subscip, -lb ) )
391  {
392  adjustedbound = MIN(-large, ub-large);
393  adjustedbound = MAX(adjustedbound, -inf);
394  SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], adjustedbound) );
395  }
396  }
397 
398  /* free hash map */
399  SCIPhashmapFree(&varmapfw);
400 
401  /* do not abort subproblem on CTRL-C */
402  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
403 
404  /* disable output to console */
405  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
406 
407  /* set limits for the subproblem */
408  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nnodes) );
409  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
410  SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
411  SCIP_CALL( SCIPsetIntParam(subscip, "limits/solutions", 1) );
412 
413  /* forbid recursive call of heuristics and separators solving sub-SCIPs */
414  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
415 
416  /* disable expensive techniques that merely work on the dual bound */
417 
418  /* disable cutting plane separation */
419  SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
420 
421  /* disable expensive presolving */
422  SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
423  if( !SCIPisParamFixed(subscip, "presolving/maxrounds") )
424  {
425  SCIP_CALL( SCIPsetIntParam(subscip, "presolving/maxrounds", 50) );
426  }
427 
428  /* use best dfs node selection */
429  if( SCIPfindNodesel(subscip, "dfs") != NULL && !SCIPisParamFixed(subscip, "nodeselection/dfs/stdpriority") )
430  {
431  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/dfs/stdpriority", INT_MAX/4) );
432  }
433 
434  /* use inference branching */
435  if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
436  {
437  SCIP_CALL( SCIPsetIntParam(subscip, "branching/leastinf/priority", INT_MAX/4) );
438  }
439 
440  /* employ a limit on the number of enforcement rounds in the quadratic constraint handler; this fixes the issue that
441  * sometimes the quadratic constraint handler needs hundreds or thousands of enforcement rounds to determine the
442  * feasibility status of a single node without fractional branching candidates by separation (namely for uflquad
443  * instances); however, the solution status of the sub-SCIP might get corrupted by this; hence no deductions shall be
444  * made for the original SCIP
445  */
446  if( SCIPfindConshdlr(subscip, "quadratic") != NULL && !SCIPisParamFixed(subscip, "constraints/quadratic/enfolplimit") )
447  {
448  SCIP_CALL( SCIPsetIntParam(subscip, "constraints/quadratic/enfolplimit", 10) );
449  }
450 
451  /* disable feaspump and fracdiving */
452  if( !SCIPisParamFixed(subscip, "heuristics/feaspump/freq") )
453  {
454  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/feaspump/freq", -1) );
455  }
456  if( !SCIPisParamFixed(subscip, "heuristics/fracdiving/freq") )
457  {
458  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/fracdiving/freq", -1) );
459  }
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 #ifdef SCIP_DEBUG
466  /* for debugging zeroobj, enable MIP output */
467  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
468  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
469 #endif
470 
471  /* if there is already a solution, add an objective cutoff */
472  if( SCIPgetNSols(scip) > 0 )
473  {
474  SCIP_Real upperbound;
475  SCIP_CONS* origobjcons;
476 #ifndef NDEBUG
477  int nobjvars;
478  nobjvars = 0;
479 #endif
480 
481  cutoff = SCIPinfinity(scip);
482  assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
483 
484  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
485 
486  if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(scip)) )
487  {
488  cutoff = (1-minimprove)*SCIPgetUpperbound(scip) + minimprove*SCIPgetLowerbound(scip);
489  }
490  else
491  {
492  if( SCIPgetUpperbound(scip) >= 0 )
493  cutoff = ( 1 - minimprove ) * SCIPgetUpperbound ( scip );
494  else
495  cutoff = ( 1 + minimprove ) * SCIPgetUpperbound ( scip );
496  }
497  cutoff = MIN(upperbound, cutoff);
498 
499  SCIP_CALL( SCIPcreateConsLinear(subscip, &origobjcons, "objbound_of_origscip", 0, NULL, NULL, -SCIPinfinity(subscip), cutoff,
500  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
501  for( i = 0; i < nvars; ++i)
502  {
503  if( !SCIPisFeasZero(subscip, SCIPvarGetObj(vars[i])) )
504  {
505  SCIP_CALL( SCIPaddCoefLinear(subscip, origobjcons, subvars[i], SCIPvarGetObj(vars[i])) );
506 #ifndef NDEBUG
507  nobjvars++;
508 #endif
509  }
510  }
511  SCIP_CALL( SCIPaddCons(subscip, origobjcons) );
512  SCIP_CALL( SCIPreleaseCons(subscip, &origobjcons) );
513  assert(nobjvars == SCIPgetNObjVars(scip));
514  }
515 
516  /* catch LP events of sub-SCIP */
517  SCIP_CALL( SCIPtransformProb(subscip) );
518  SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_NODESOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
519 
520  SCIPdebugMessage("solving subproblem: nnodes=%"SCIP_LONGINT_FORMAT"\n", nnodes);
521  retcode = SCIPsolve(subscip);
522 
523  /* drop LP events of sub-SCIP */
524  SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_NODESOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
525 
526  /* errors in solving the subproblem should not kill the overall solving process;
527  * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
528  */
529  if( retcode != SCIP_OKAY )
530  {
531 #ifndef NDEBUG
532  SCIP_CALL( retcode );
533 #endif
534  SCIPwarningMessage(scip, "Error while solving subproblem in zeroobj heuristic; sub-SCIP terminated with code <%d>\n",retcode);
535  }
536 
537  /* check, whether a solution was found;
538  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
539  */
540  nsubsols = SCIPgetNSols(subscip);
541  subsols = SCIPgetSols(subscip);
542  success = FALSE;
543  for( i = 0; i < nsubsols && (!success || heurdata->addallsols); ++i )
544  {
545  SCIP_CALL( createNewSol(scip, subscip, subvars, heur, subsols[i], &success) );
546  if( success )
547  *result = SCIP_FOUNDSOL;
548  }
549 
550 #ifdef SCIP_DEBUG
551  SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
552 #endif
553 
554  /* free subproblem */
555  SCIPfreeBufferArray(scip, &subvars);
556  SCIP_CALL( SCIPfree(&subscip) );
557 
558  return SCIP_OKAY;
559 }
560 
561 
562 /** creates the zeroobj primal heuristic and includes it in SCIP */
563 SCIP_RETCODE SCIPincludeHeurZeroobj(
564  SCIP* scip /**< SCIP data structure */
565  )
566 {
567  SCIP_HEURDATA* heurdata;
568  SCIP_HEUR* heur;
569 
570  /* create heuristic data */
571  SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
572 
573  /* include primal heuristic */
574  heur = NULL;
575  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
576  HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
577  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecZeroobj, heurdata) );
578  assert(heur != NULL);
579 
580  /* set non-NULL pointers to callback methods */
581  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyZeroobj) );
582  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeZeroobj) );
583  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitZeroobj) );
584 
585  /* add zeroobj primal heuristic parameters */
586  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/"HEUR_NAME"/maxnodes",
587  "maximum number of nodes to regard in the subproblem",
588  &heurdata->maxnodes, TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
589 
590  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/"HEUR_NAME"/nodesofs",
591  "number of nodes added to the contingent of the total nodes",
592  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
593 
594  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/"HEUR_NAME"/minnodes",
595  "minimum number of nodes required to start the subproblem",
596  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
597 
598  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/"HEUR_NAME"/maxlpiters",
599  "maximum number of LP iterations to be performed in the subproblem",
600  &heurdata->maxlpiters, TRUE, DEFAULT_MAXLPITERS, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
601 
602  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/nodesquot",
603  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
604  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
605 
606  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/minimprove",
607  "factor by which zeroobj should at least improve the incumbent",
608  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
609 
610  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/addallsols",
611  "should all subproblem solutions be added to the original SCIP?",
612  &heurdata->addallsols, TRUE, DEFAULT_ADDALLSOLS, NULL, NULL) );
613 
614  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/onlywithoutsol",
615  "should heuristic only be executed if no primal solution was found, yet?",
616  &heurdata->onlywithoutsol, TRUE, DEFAULT_ONLYWITHOUTSOL, NULL, NULL) );
617 
618  return SCIP_OKAY;
619 }
620