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 /** setup and solve subscip */
260 static
262  SCIP* scip, /**< SCIP data structure */
263  SCIP* subscip, /**< SCIP data structure */
264  SCIP_HEUR* heur, /**< heuristic data structure */
265  SCIP_RESULT* result, /**< result data structure */
266  SCIP_Real minimprove, /**< factor by which zeroobj should at least improve the incumbent */
267  SCIP_Longint nnodes /**< node limit for the subproblem */
268  )
269 {
270  SCIP_Real cutoff; /* objective cutoff for the subproblem */
271  SCIP_Real large;
272  SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
273  SCIP_VAR** vars; /* original problem's variables */
274  SCIP_VAR** subvars; /* subproblem's variables */
275  SCIP_SOL** subsols;
276  SCIP_HEURDATA* heurdata; /* heuristic's private data structure */
277  SCIP_EVENTHDLR* eventhdlr; /* event handler for LP events */
278 
279  int nsubsols;
280  int nvars; /* number of original problem's variables */
281  int i;
282  SCIP_Bool success;
283  SCIP_Bool valid;
284 
285 
286  assert(scip != NULL);
287  assert(subscip != NULL);
288  assert(heur != NULL);
289  assert(result != NULL);
290 
291  heurdata = SCIPheurGetData(heur);
292  assert(heurdata != NULL);
293 
294  /* get variable data */
295  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
296 
297  /* create the variable mapping hash map */
298  SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
299  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
300 
301  /* different methods to create sub-problem: either copy LP relaxation or the CIP with all constraints */
302  valid = FALSE;
303 
304  /* copy complete SCIP instance */
305  SCIP_CALL( SCIPcopy(scip, subscip, varmapfw, NULL, "zeroobj", TRUE, FALSE, TRUE, &valid) );
306  SCIPdebugMsg(scip, "Copying the SCIP instance was %s complete.\n", valid ? "" : "not ");
307 
308  /* create event handler for LP events */
309  eventhdlr = NULL;
310  SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecZeroobj, NULL) );
311  if( eventhdlr == NULL )
312  {
313  SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
314  return SCIP_PLUGINNOTFOUND;
315  }
316 
317  /* determine large value to set variables to */
318  large = SCIPinfinity(scip);
319  if( !SCIPisInfinity(scip, 0.1 / SCIPfeastol(scip)) )
320  large = 0.1 / SCIPfeastol(scip);
321 
322  /* get variable image and change to 0.0 in sub-SCIP */
323  for( i = 0; i < nvars; i++ )
324  {
325  SCIP_Real adjustedbound;
326  SCIP_Real lb;
327  SCIP_Real ub;
328  SCIP_Real inf;
329 
330  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
331  SCIP_CALL( SCIPchgVarObj(subscip, subvars[i], 0.0) );
332 
333  lb = SCIPvarGetLbGlobal(subvars[i]);
334  ub = SCIPvarGetUbGlobal(subvars[i]);
335  inf = SCIPinfinity(subscip);
336 
337  /* adjust infinite bounds in order to avoid that variables with non-zero objective
338  * get fixed to infinite value in zeroobj subproblem
339  */
340  if( SCIPisInfinity(subscip, ub ) )
341  {
342  adjustedbound = MAX(large, lb+large);
343  adjustedbound = MIN(adjustedbound, inf);
344  SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], adjustedbound) );
345  }
346  if( SCIPisInfinity(subscip, -lb ) )
347  {
348  adjustedbound = MIN(-large, ub-large);
349  adjustedbound = MAX(adjustedbound, -inf);
350  SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], adjustedbound) );
351  }
352  }
353 
354  /* free hash map */
355  SCIPhashmapFree(&varmapfw);
356 
357  /* do not abort subproblem on CTRL-C */
358  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
359 
360 #ifdef SCIP_DEBUG
361  /* for debugging, enable full output */
362  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
363  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
364 #else
365  /* disable statistic timing inside sub SCIP and output to console */
366  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
367  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
368 #endif
369 
370  /* set limits for the subproblem */
371  SCIP_CALL( SCIPcopyLimits(scip, subscip) );
372  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nnodes) );
373  SCIP_CALL( SCIPsetIntParam(subscip, "limits/solutions", 1) );
374 
375  /* forbid recursive call of heuristics and separators solving sub-SCIPs */
376  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
377 
378  /* disable expensive techniques that merely work on the dual bound */
379 
380  /* disable cutting plane separation */
382 
383  /* disable expensive presolving */
385  if( !SCIPisParamFixed(subscip, "presolving/maxrounds") )
386  {
387  SCIP_CALL( SCIPsetIntParam(subscip, "presolving/maxrounds", 50) );
388  }
389 
390  /* use restart dfs node selection */
391  if( SCIPfindNodesel(subscip, "restartdfs") != NULL && !SCIPisParamFixed(subscip, "nodeselection/restartdfs/stdpriority") )
392  {
393  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/restartdfs/stdpriority", INT_MAX/4) );
394  }
395 
396  /* activate uct node selection at the top of the tree */
397  if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") )
398  {
399  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) );
400  }
401  /* use least infeasible branching */
402  if( SCIPfindBranchrule(subscip, "leastinf") != NULL && !SCIPisParamFixed(subscip, "branching/leastinf/priority") )
403  {
404  SCIP_CALL( SCIPsetIntParam(subscip, "branching/leastinf/priority", INT_MAX/4) );
405  }
406 
407  /* employ a limit on the number of enforcement rounds in the quadratic constraint handler; this fixes the issue that
408  * sometimes the quadratic constraint handler needs hundreds or thousands of enforcement rounds to determine the
409  * feasibility status of a single node without fractional branching candidates by separation (namely for uflquad
410  * instances); however, the solution status of the sub-SCIP might get corrupted by this; hence no deductions shall be
411  * made for the original SCIP
412  */
413  if( SCIPfindConshdlr(subscip, "quadratic") != NULL && !SCIPisParamFixed(subscip, "constraints/quadratic/enfolplimit") )
414  {
415  SCIP_CALL( SCIPsetIntParam(subscip, "constraints/quadratic/enfolplimit", 10) );
416  }
417 
418  /* disable feaspump and fracdiving */
419  if( !SCIPisParamFixed(subscip, "heuristics/feaspump/freq") )
420  {
421  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/feaspump/freq", -1) );
422  }
423  if( !SCIPisParamFixed(subscip, "heuristics/fracdiving/freq") )
424  {
425  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/fracdiving/freq", -1) );
426  }
427 
428  /* speed up sub-SCIP by not checking dual LP feasibility */
429  SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
430 
431  /* restrict LP iterations */
432  SCIP_CALL( SCIPsetLongintParam(subscip, "lp/iterlim", 2*heurdata->maxlpiters / MAX(1,nnodes)) );
433  SCIP_CALL( SCIPsetLongintParam(subscip, "lp/rootiterlim", heurdata->maxlpiters) );
434 
435  /* if there is already a solution, add an objective cutoff */
436  if( SCIPgetNSols(scip) > 0 )
437  {
438  SCIP_Real upperbound;
439  SCIP_CONS* origobjcons;
440 #ifndef NDEBUG
441  int nobjvars;
442  nobjvars = 0;
443 #endif
444 
445  assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
446 
447  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
448 
449  if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(scip)) )
450  {
451  cutoff = (1-minimprove)*SCIPgetUpperbound(scip) + minimprove*SCIPgetLowerbound(scip);
452  }
453  else
454  {
455  if( SCIPgetUpperbound(scip) >= 0 )
456  cutoff = ( 1 - minimprove ) * SCIPgetUpperbound ( scip );
457  else
458  cutoff = ( 1 + minimprove ) * SCIPgetUpperbound ( scip );
459  }
460  cutoff = MIN(upperbound, cutoff);
461 
462  SCIP_CALL( SCIPcreateConsLinear(subscip, &origobjcons, "objbound_of_origscip", 0, NULL, NULL, -SCIPinfinity(subscip), cutoff,
464  for( i = 0; i < nvars; ++i)
465  {
466  if( !SCIPisFeasZero(subscip, SCIPvarGetObj(vars[i])) )
467  {
468  SCIP_CALL( SCIPaddCoefLinear(subscip, origobjcons, subvars[i], SCIPvarGetObj(vars[i])) );
469 #ifndef NDEBUG
470  nobjvars++;
471 #endif
472  }
473  }
474  SCIP_CALL( SCIPaddCons(subscip, origobjcons) );
475  SCIP_CALL( SCIPreleaseCons(subscip, &origobjcons) );
476  assert(nobjvars == SCIPgetNObjVars(scip));
477  }
478 
479  /* catch LP events of sub-SCIP */
480  SCIP_CALL( SCIPtransformProb(subscip) );
481  SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_NODESOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
482 
483  SCIPdebugMsg(scip, "solving subproblem: nnodes=%" SCIP_LONGINT_FORMAT "\n", nnodes);
484 
485 
486  /* errors in solving the subproblem should not kill the overall solving process;
487  * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
488  */
489  SCIP_CALL_ABORT( SCIPsolve(subscip) );
490 
491  /* drop LP events of sub-SCIP */
492  SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_NODESOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
493 
494  /* check, whether a solution was found;
495  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
496  */
497  nsubsols = SCIPgetNSols(subscip);
498  subsols = SCIPgetSols(subscip);
499  success = FALSE;
500  for( i = 0; i < nsubsols && (!success || heurdata->addallsols); ++i )
501  {
502  SCIP_CALL( createNewSol(scip, subscip, subvars, heur, subsols[i], &success) );
503  if( success )
504  *result = SCIP_FOUNDSOL;
505  }
506 
507 #ifdef SCIP_DEBUG
508  SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
509 #endif
510 
511  /* free subproblem */
512  SCIPfreeBufferArray(scip, &subvars);
513 
514  return SCIP_OKAY;
515 }
516 
517 
518 /*
519  * primal heuristic specific interface methods
520  */
521 
522 
523 /** main procedure of the zeroobj heuristic, creates and solves a sub-SCIP */
525  SCIP* scip, /**< original SCIP data structure */
526  SCIP_HEUR* heur, /**< heuristic data structure */
527  SCIP_RESULT* result, /**< result data structure */
528  SCIP_Real minimprove, /**< factor by which zeroobj should at least improve the incumbent */
529  SCIP_Longint nnodes /**< node limit for the subproblem */
530  )
531 {
532  SCIP* subscip; /* the subproblem created by zeroobj */
533  SCIP_HEURDATA* heurdata; /* heuristic's private data structure */
534  SCIP_Bool success;
535  SCIP_RETCODE retcode;
536 
537  assert(scip != NULL);
538  assert(heur != NULL);
539  assert(result != NULL);
540 
541  assert(nnodes >= 0);
542  assert(0.0 <= minimprove && minimprove <= 1.0);
543 
544  *result = SCIP_DIDNOTRUN;
545 
546  /* only call heuristic once at the root */
547  if( SCIPgetDepth(scip) <= 0 && SCIPheurGetNCalls(heur) > 0 )
548  return SCIP_OKAY;
549 
550  /* get heuristic data */
551  heurdata = SCIPheurGetData(heur);
552  assert(heurdata != NULL);
553 
554  /* only call the heuristic if we do not have an incumbent */
555  if( SCIPgetNSolsFound(scip) > 0 && heurdata->onlywithoutsol )
556  return SCIP_OKAY;
557 
558  /* check whether there is enough time and memory left */
559  SCIP_CALL( SCIPcheckCopyLimits(scip, &success) );
560 
561  if( !success )
562  return SCIP_OKAY;
563 
564  *result = SCIP_DIDNOTFIND;
565 
566 
567  /* initialize the subproblem */
568  SCIP_CALL( SCIPcreate(&subscip) );
569 
570  retcode = setupAndSolveSubscip(scip, subscip, heur, result, minimprove, nnodes);
571 
572  SCIP_CALL( SCIPfree(&subscip) );
573 
574  return retcode;
575 }
576 
577 
578 /** creates the zeroobj primal heuristic and includes it in SCIP */
580  SCIP* scip /**< SCIP data structure */
581  )
582 {
583  SCIP_HEURDATA* heurdata;
584  SCIP_HEUR* heur;
585 
586  /* create heuristic data */
587  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
588 
589  /* include primal heuristic */
590  heur = NULL;
591  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
593  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecZeroobj, heurdata) );
594  assert(heur != NULL);
595 
596  /* set non-NULL pointers to callback methods */
597  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyZeroobj) );
598  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeZeroobj) );
599  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitZeroobj) );
600 
601  /* add zeroobj primal heuristic parameters */
602  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
603  "maximum number of nodes to regard in the subproblem",
604  &heurdata->maxnodes, TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
605 
606  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
607  "number of nodes added to the contingent of the total nodes",
608  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
609 
610  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
611  "minimum number of nodes required to start the subproblem",
612  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
613 
614  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxlpiters",
615  "maximum number of LP iterations to be performed in the subproblem",
616  &heurdata->maxlpiters, TRUE, DEFAULT_MAXLPITERS, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
617 
618  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
619  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
620  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
621 
622  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
623  "factor by which zeroobj should at least improve the incumbent",
624  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
625 
626  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/addallsols",
627  "should all subproblem solutions be added to the original SCIP?",
628  &heurdata->addallsols, TRUE, DEFAULT_ADDALLSOLS, NULL, NULL) );
629 
630  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlywithoutsol",
631  "should heuristic only be executed if no primal solution was found, yet?",
632  &heurdata->onlywithoutsol, TRUE, DEFAULT_ONLYWITHOUTSOL, NULL, NULL) );
633  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct",
634  "should uct node selection be used at the beginning of the search?",
635  &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) );
636 
637  return SCIP_OKAY;
638 }
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:47357
#define DEFAULT_MAXLPITERS
Definition: heur_zeroobj.c:47
static SCIP_RETCODE setupAndSolveSubscip(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real minimprove, SCIP_Longint nnodes)
Definition: heur_zeroobj.c:261
SCIP_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:22276
#define DEFAULT_NODESOFS
Definition: heur_zeroobj.c:48
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5158
SCIP_Real SCIPfeastol(SCIP *scip)
Definition: scip.c:46437
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip.c:42327
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6604
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17276
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1344
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
Definition: scip.c:43613
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip.c:12246
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip.c:8611
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:11680
#define DEFAULT_ADDALLSOLS
Definition: heur_zeroobj.c:50
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip.c:39826
#define FALSE
Definition: def.h:64
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2793
SCIP_RETCODE SCIPapplyZeroobj(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real minimprove, SCIP_Longint nnodes)
Definition: heur_zeroobj.c:524
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:4293
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip.c:4192
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47022
#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:5132
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip.c:9269
#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:22602
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:8084
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2931
#define SCIP_LONGINT_MAX
Definition: def.h:135
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip.c:748
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1119
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:22363
#define SCIPdebugMsg
Definition: scip.h:455
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
Definition: scip.c:45645
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:17286
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip.c:16109
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1198
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip.c:4401
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:12585
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip.c:8145
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:38942
static SCIP_DECL_HEURCOPY(heurCopyZeroobj)
Definition: heur_zeroobj.c:156
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip.c:4630
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:46725
#define EVENTHDLR_NAME
Definition: heur_zeroobj.c:40
SCIP_RETCODE SCIPincludeHeurZeroobj(SCIP *scip)
Definition: heur_zeroobj.c:579
#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:2826
#define SCIP_CALL(x)
Definition: def.h:350
SCIP_Real SCIPgetLowerbound(SCIP *scip)
Definition: scip.c:43271
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1324
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip.c:21847
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
#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:41152
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:29287
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:43039
#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:40788
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip.c:4688
#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:41186
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17124
int SCIPgetNSols(SCIP *scip)
Definition: scip.c:39777
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:12034
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:47033
#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:27755
#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:3795
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip.c:8161
#define HEUR_USESSUBSCIP
Definition: heur_zeroobj.c:37
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip.c:8957
#define SCIP_Real
Definition: def.h:149
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1145
#define HEUR_DESC
Definition: heur_zeroobj.c:30
#define HEUR_MAXDEPTH
Definition: heur_zeroobj.c:35
#define SCIP_Longint
Definition: def.h:134
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip.c:4156
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:38807
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip.c:13929
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip.c:8129
#define nnodes
Definition: gastrans.c:65
SCIP_Real SCIPsumepsilon(SCIP *scip)
Definition: scip.c:46423
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
Definition: scip.c:17318
SCIP_Real SCIPgetUpperbound(SCIP *scip)
Definition: scip.c:43420
#define SCIP_CALL_ABORT(x)
Definition: def.h:329
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1109
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:42127
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:4321
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip.c:5083
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip.c:4746
#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:4239
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip.c:780
#define EVENTHDLR_DESC
Definition: heur_zeroobj.c:41
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37872