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-2022 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 visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_zeroobj.c
17  * @ingroup DEFPLUGINS_HEUR
18  * @brief heuristic that tries to solve the problem without objective. In Gurobi, this heuristic is known as "Hail Mary"
19  * @author Timo Berthold
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include "blockmemshell/memory.h"
25 #include "scip/cons_linear.h"
26 #include "scip/heur_zeroobj.h"
27 #include "scip/pub_event.h"
28 #include "scip/pub_heur.h"
29 #include "scip/pub_message.h"
30 #include "scip/pub_misc.h"
31 #include "scip/pub_var.h"
32 #include "scip/scip_branch.h"
33 #include "scip/scip_cons.h"
34 #include "scip/scip_copy.h"
35 #include "scip/scip_event.h"
36 #include "scip/scip_general.h"
37 #include "scip/scip_heur.h"
38 #include "scip/scip_lp.h"
39 #include "scip/scip_mem.h"
40 #include "scip/scip_message.h"
41 #include "scip/scip_nodesel.h"
42 #include "scip/scip_numerics.h"
43 #include "scip/scip_param.h"
44 #include "scip/scip_prob.h"
45 #include "scip/scip_sol.h"
46 #include "scip/scip_solve.h"
47 #include "scip/scip_solvingstats.h"
48 #include "scip/scip_tree.h"
49 #include "scip/scip_var.h"
50 #include <string.h>
51 
52 #define HEUR_NAME "zeroobj"
53 #define HEUR_DESC "heuristic trying to solve the problem without objective"
54 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
55 #define HEUR_PRIORITY 100
56 #define HEUR_FREQ -1
57 #define HEUR_FREQOFS 0
58 #define HEUR_MAXDEPTH 0
59 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_BEFOREPRESOL
60 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
61 
62 /* event handler properties */
63 #define EVENTHDLR_NAME "Zeroobj"
64 #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic"
65 
66 /* default values for zeroobj-specific plugins */
67 #define DEFAULT_MAXNODES 1000LL /* maximum number of nodes to regard in the subproblem */
68 #define DEFAULT_MINIMPROVE 0.01 /* factor by which zeroobj should at least improve the incumbent */
69 #define DEFAULT_MINNODES 100LL /* minimum number of nodes to regard in the subproblem */
70 #define DEFAULT_MAXLPITERS 5000LL /* maximum number of LP iterations to be performed in the subproblem */
71 #define DEFAULT_NODESOFS 100LL /* number of nodes added to the contingent of the total nodes */
72 #define DEFAULT_NODESQUOT 0.1 /* subproblem nodes in relation to nodes of the original problem */
73 #define DEFAULT_ADDALLSOLS FALSE /* should all subproblem solutions be added to the original SCIP? */
74 #define DEFAULT_ONLYWITHOUTSOL TRUE /**< should heuristic only be executed if no primal solution was found, yet? */
75 #define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */
76 
77 /*
78  * Data structures
79  */
80 
81 /** primal heuristic data */
82 struct SCIP_HeurData
83 {
84  SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
85  SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
86  SCIP_Longint maxlpiters; /**< maximum number of LP iterations to be performed in the subproblem */
87  SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
88  SCIP_Longint usednodes; /**< nodes already used by zeroobj in earlier calls */
89  SCIP_Real minimprove; /**< factor by which zeroobj should at least improve the incumbent */
90  SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
91  SCIP_Bool addallsols; /**< should all subproblem solutions be added to the original SCIP? */
92  SCIP_Bool onlywithoutsol; /**< should heuristic only be executed if no primal solution was found, yet? */
93  SCIP_Bool useuct; /**< should uct node selection be used at the beginning of the search? */
94 };
95 
96 
97 /*
98  * Local methods
99  */
100 
101 /* ---------------- Callback methods of event handler ---------------- */
102 
103 /* exec the event handler
104  *
105  * we interrupt the solution process
106  */
107 static
108 SCIP_DECL_EVENTEXEC(eventExecZeroobj)
109 {
110  SCIP_HEURDATA* heurdata;
111 
112  assert(eventhdlr != NULL);
113  assert(eventdata != NULL);
114  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
115  assert(event != NULL);
117 
118  heurdata = (SCIP_HEURDATA*)eventdata;
119  assert(heurdata != NULL);
120 
121  /* interrupt solution process of sub-SCIP */
122  if( SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_ITERLIMIT || SCIPgetNLPIterations(scip) >= heurdata->maxlpiters )
123  {
125  }
126 
127  return SCIP_OKAY;
128 }
129 /* ---------------- Callback methods of primal heuristic ---------------- */
130 
131 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
132 static
133 SCIP_DECL_HEURCOPY(heurCopyZeroobj)
134 { /*lint --e{715}*/
135  assert(scip != NULL);
136  assert(heur != NULL);
137  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
138 
139  /* call inclusion method of primal heuristic */
141 
142  return SCIP_OKAY;
143 }
144 
145 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
146 static
147 SCIP_DECL_HEURFREE(heurFreeZeroobj)
148 { /*lint --e{715}*/
149  SCIP_HEURDATA* heurdata;
150 
151  assert( heur != NULL );
152  assert( scip != NULL );
153 
154  /* get heuristic data */
155  heurdata = SCIPheurGetData(heur);
156  assert( heurdata != NULL );
157 
158  /* free heuristic data */
159  SCIPfreeBlockMemory(scip, &heurdata);
160  SCIPheurSetData(heur, NULL);
161 
162  return SCIP_OKAY;
163 }
164 
165 
166 /** initialization method of primal heuristic (called after problem was transformed) */
167 static
168 SCIP_DECL_HEURINIT(heurInitZeroobj)
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  /* initialize data */
180  heurdata->usednodes = 0;
181 
182  return SCIP_OKAY;
183 }
184 
185 
186 /** execution method of primal heuristic */
187 static
188 SCIP_DECL_HEUREXEC(heurExecZeroobj)
189 { /*lint --e{715}*/
190  SCIP_HEURDATA* heurdata; /* heuristic's data */
191  SCIP_Longint nnodes; /* number of stalling nodes for the subproblem */
192 
193  assert( heur != NULL );
194  assert( scip != NULL );
195  assert( result != NULL );
196 
197  /* get heuristic data */
198  heurdata = SCIPheurGetData(heur);
199  assert( heurdata != NULL );
200 
201  /* calculate the maximal number of branching nodes until heuristic is aborted */
202  nnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
203 
204  /* reward zeroobj if it succeeded often */
205  nnodes = (SCIP_Longint)(nnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
206  nnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-SCIP as 100 nodes */
207  nnodes += heurdata->nodesofs;
208 
209  /* determine the node limit for the current process */
210  nnodes -= heurdata->usednodes;
211  nnodes = MIN(nnodes, heurdata->maxnodes);
212 
213  /* check whether we have enough nodes left to call subproblem solving */
214  if( nnodes < heurdata->minnodes )
215  {
216  SCIPdebugMsg(scip, "skipping zeroobj: nnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nnodes, heurdata->minnodes);
217  return SCIP_OKAY;
218  }
219 
220  /* do not run zeroobj, if the problem does not have an objective function anyway */
221  if( SCIPgetNObjVars(scip) == 0 )
222  {
223  SCIPdebugMsg(scip, "skipping zeroobj: pure feasibility problem anyway\n");
224  return SCIP_OKAY;
225  }
226 
227  if( SCIPisStopped(scip) )
228  return SCIP_OKAY;
229 
230  SCIP_CALL( SCIPapplyZeroobj(scip, heur, result, heurdata->minimprove, nnodes) );
231 
232  return SCIP_OKAY;
233 }
234 
235 /** setup and solve subscip */
236 static
238  SCIP* scip, /**< SCIP data structure */
239  SCIP* subscip, /**< SCIP data structure */
240  SCIP_HEUR* heur, /**< heuristic data structure */
241  SCIP_RESULT* result, /**< result data structure */
242  SCIP_Real minimprove, /**< factor by which zeroobj should at least improve the incumbent */
243  SCIP_Longint nnodes /**< node limit for the subproblem */
244  )
245 {
246  SCIP_Real cutoff; /* objective cutoff for the subproblem */
247  SCIP_Real large;
248  SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
249  SCIP_VAR** vars; /* original problem's variables */
250  SCIP_VAR** subvars; /* subproblem's variables */
251  SCIP_SOL** subsols;
252  SCIP_HEURDATA* heurdata; /* heuristic's private data structure */
253  SCIP_EVENTHDLR* eventhdlr; /* event handler for LP events */
254 
255  int nsubsols;
256  int nvars; /* number of original problem's variables */
257  int i;
258  SCIP_Bool success;
259  SCIP_Bool valid;
260 
261  assert(scip != NULL);
262  assert(subscip != NULL);
263  assert(heur != NULL);
264  assert(result != NULL);
265 
266  heurdata = SCIPheurGetData(heur);
267  assert(heurdata != NULL);
268 
269  /* get variable data */
270  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
271 
272  /* create the variable mapping hash map */
273  SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
274  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
275 
276  /* different methods to create sub-problem: either copy LP relaxation or the CIP with all constraints */
277  valid = FALSE;
278 
279  /* copy complete SCIP instance */
280  SCIP_CALL( SCIPcopy(scip, subscip, varmapfw, NULL, "zeroobj", TRUE, FALSE, FALSE, TRUE, &valid) );
281  SCIPdebugMsg(scip, "Copying the SCIP instance was %s complete.\n", valid ? "" : "not ");
282 
283  /* create event handler for LP events */
284  eventhdlr = NULL;
285  SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecZeroobj, NULL) );
286  if( eventhdlr == NULL )
287  {
288  SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
289  return SCIP_PLUGINNOTFOUND;
290  }
291 
292  /* determine large value to set variables to */
293  large = SCIPinfinity(scip);
294  if( !SCIPisInfinity(scip, 0.1 / SCIPfeastol(scip)) )
295  large = 0.1 / SCIPfeastol(scip);
296 
297  /* get variable image and change to 0.0 in sub-SCIP */
298  for( i = 0; i < nvars; i++ )
299  {
300  SCIP_Real adjustedbound;
301  SCIP_Real lb;
302  SCIP_Real ub;
303  SCIP_Real inf;
304 
305  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
306  if( subvars[i] == NULL )
307  continue;
308 
309  SCIP_CALL( SCIPchgVarObj(subscip, subvars[i], 0.0) );
310 
311  lb = SCIPvarGetLbGlobal(subvars[i]);
312  ub = SCIPvarGetUbGlobal(subvars[i]);
313  inf = SCIPinfinity(subscip);
314 
315  /* adjust infinite bounds in order to avoid that variables with non-zero objective
316  * get fixed to infinite value in zeroobj subproblem
317  */
318  if( SCIPisInfinity(subscip, ub ) )
319  {
320  adjustedbound = MAX(large, lb+large);
321  adjustedbound = MIN(adjustedbound, inf);
322  SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], adjustedbound) );
323  }
324  if( SCIPisInfinity(subscip, -lb ) )
325  {
326  adjustedbound = MIN(-large, ub-large);
327  adjustedbound = MAX(adjustedbound, -inf);
328  SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], adjustedbound) );
329  }
330  }
331 
332  /* free hash map */
333  SCIPhashmapFree(&varmapfw);
334 
335  /* do not abort subproblem on CTRL-C */
336  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
337 
338 #ifdef SCIP_DEBUG
339  /* for debugging, enable full output */
340  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
341  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
342 #else
343  /* disable statistic timing inside sub SCIP and output to console */
344  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
345  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
346 #endif
347 
348  /* set limits for the subproblem */
349  SCIP_CALL( SCIPcopyLimits(scip, subscip) );
350  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nnodes) );
351  SCIP_CALL( SCIPsetIntParam(subscip, "limits/solutions", 1) );
352 
353  /* forbid recursive call of heuristics and separators solving sub-SCIPs */
354  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
355 
356  /* disable expensive techniques that merely work on the dual bound */
357 
358  /* disable cutting plane separation */
360 
361  /* disable expensive presolving */
363  if( !SCIPisParamFixed(subscip, "presolving/maxrounds") )
364  {
365  SCIP_CALL( SCIPsetIntParam(subscip, "presolving/maxrounds", 50) );
366  }
367 
368  /* use restart dfs node selection */
369  if( SCIPfindNodesel(subscip, "restartdfs") != NULL && !SCIPisParamFixed(subscip, "nodeselection/restartdfs/stdpriority") )
370  {
371  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/restartdfs/stdpriority", INT_MAX/4) );
372  }
373 
374  /* activate uct node selection at the top of the tree */
375  if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") )
376  {
377  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) );
378  }
379  /* use least infeasible branching */
380  if( SCIPfindBranchrule(subscip, "leastinf") != NULL && !SCIPisParamFixed(subscip, "branching/leastinf/priority") )
381  {
382  SCIP_CALL( SCIPsetIntParam(subscip, "branching/leastinf/priority", INT_MAX/4) );
383  }
384 
385  /* disable feaspump and fracdiving */
386  if( !SCIPisParamFixed(subscip, "heuristics/feaspump/freq") )
387  {
388  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/feaspump/freq", -1) );
389  }
390  if( !SCIPisParamFixed(subscip, "heuristics/fracdiving/freq") )
391  {
392  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/fracdiving/freq", -1) );
393  }
394 
395  /* speed up sub-SCIP by not checking dual LP feasibility */
396  SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
397 
398  /* restrict LP iterations */
399  SCIP_CALL( SCIPsetLongintParam(subscip, "lp/iterlim", 2*heurdata->maxlpiters / MAX(1,nnodes)) );
400  SCIP_CALL( SCIPsetLongintParam(subscip, "lp/rootiterlim", heurdata->maxlpiters) );
401 
402  /* if there is already a solution, add an objective cutoff */
403  if( SCIPgetNSols(scip) > 0 )
404  {
405  SCIP_Real upperbound;
406  SCIP_CONS* origobjcons;
407 #ifndef NDEBUG
408  int nobjvars;
409  nobjvars = 0;
410 #endif
411 
412  assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
413 
414  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
415 
416  if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(scip)) )
417  {
418  cutoff = (1-minimprove)*SCIPgetUpperbound(scip) + minimprove*SCIPgetLowerbound(scip);
419  }
420  else
421  {
422  if( SCIPgetUpperbound(scip) >= 0 )
423  cutoff = ( 1 - minimprove ) * SCIPgetUpperbound ( scip );
424  else
425  cutoff = ( 1 + minimprove ) * SCIPgetUpperbound ( scip );
426  }
427  cutoff = MIN(upperbound, cutoff);
428 
429  SCIP_CALL( SCIPcreateConsLinear(subscip, &origobjcons, "objbound_of_origscip", 0, NULL, NULL, -SCIPinfinity(subscip), cutoff,
431  for( i = 0; i < nvars; ++i)
432  {
433  if( !SCIPisFeasZero(subscip, SCIPvarGetObj(vars[i])) )
434  {
435  assert(subvars[i] != NULL); /* subvars[i] can be NULL for relax-only vars, but they cannot appear in the objective */
436  SCIP_CALL( SCIPaddCoefLinear(subscip, origobjcons, subvars[i], SCIPvarGetObj(vars[i])) );
437 #ifndef NDEBUG
438  nobjvars++;
439 #endif
440  }
441  }
442  SCIP_CALL( SCIPaddCons(subscip, origobjcons) );
443  SCIP_CALL( SCIPreleaseCons(subscip, &origobjcons) );
444  assert(nobjvars == SCIPgetNObjVars(scip));
445  }
446 
447  /* catch LP events of sub-SCIP */
448  SCIP_CALL( SCIPtransformProb(subscip) );
449  SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_NODESOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
450 
451  SCIPdebugMsg(scip, "solving subproblem: nnodes=%" SCIP_LONGINT_FORMAT "\n", nnodes);
452 
453  /* errors in solving the subproblem should not kill the overall solving process;
454  * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
455  */
456  SCIP_CALL_ABORT( SCIPsolve(subscip) );
457 
458  /* drop LP events of sub-SCIP */
459  SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_NODESOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
460 
461  /* check, whether a solution was found;
462  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
463  */
464  nsubsols = SCIPgetNSols(subscip);
465  subsols = SCIPgetSols(subscip);
466  success = FALSE;
467  for( i = 0; i < nsubsols && (!success || heurdata->addallsols); ++i )
468  {
469  SCIP_SOL* newsol;
470 
471  SCIP_CALL( SCIPtranslateSubSol(scip, subscip, subsols[i], heur, subvars, &newsol) );
472 
473  SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
474  if( success )
475  *result = SCIP_FOUNDSOL;
476  }
477 
478 #ifdef SCIP_DEBUG
479  SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
480 #endif
481 
482  /* free subproblem */
483  SCIPfreeBufferArray(scip, &subvars);
484 
485  return SCIP_OKAY;
486 }
487 
488 
489 /*
490  * primal heuristic specific interface methods
491  */
492 
493 
494 /** main procedure of the zeroobj heuristic, creates and solves a sub-SCIP */
496  SCIP* scip, /**< original SCIP data structure */
497  SCIP_HEUR* heur, /**< heuristic data structure */
498  SCIP_RESULT* result, /**< result data structure */
499  SCIP_Real minimprove, /**< factor by which zeroobj should at least improve the incumbent */
500  SCIP_Longint nnodes /**< node limit for the subproblem */
501  )
502 {
503  SCIP* subscip; /* the subproblem created by zeroobj */
504  SCIP_HEURDATA* heurdata; /* heuristic's private data structure */
505  SCIP_Bool success;
506  SCIP_RETCODE retcode;
507 
508  assert(scip != NULL);
509  assert(heur != NULL);
510  assert(result != NULL);
511 
512  assert(nnodes >= 0);
513  assert(0.0 <= minimprove && minimprove <= 1.0);
514 
515  *result = SCIP_DIDNOTRUN;
516 
517  /* only call heuristic once at the root */
518  if( SCIPgetDepth(scip) <= 0 && SCIPheurGetNCalls(heur) > 0 )
519  return SCIP_OKAY;
520 
521  /* get heuristic data */
522  heurdata = SCIPheurGetData(heur);
523  assert(heurdata != NULL);
524 
525  /* only call the heuristic if we do not have an incumbent */
526  if( SCIPgetNSolsFound(scip) > 0 && heurdata->onlywithoutsol )
527  return SCIP_OKAY;
528 
529  /* check whether there is enough time and memory left */
530  SCIP_CALL( SCIPcheckCopyLimits(scip, &success) );
531 
532  if( !success )
533  return SCIP_OKAY;
534 
535  *result = SCIP_DIDNOTFIND;
536 
537  /* initialize the subproblem */
538  SCIP_CALL( SCIPcreate(&subscip) );
539 
540  retcode = setupAndSolveSubscip(scip, subscip, heur, result, minimprove, nnodes);
541 
542  SCIP_CALL( SCIPfree(&subscip) );
543 
544  return retcode;
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:56
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
#define DEFAULT_MAXLPITERS
Definition: heur_zeroobj.c:70
static SCIP_RETCODE setupAndSolveSubscip(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real minimprove, SCIP_Longint nnodes)
Definition: heur_zeroobj.c:237
SCIP_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4940
#define DEFAULT_NODESOFS
Definition: heur_zeroobj.c:71
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:949
SCIP_Real SCIPfeastol(SCIP *scip)
public methods for SCIP parameter handling
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
public methods for node selector plugins
public methods for memory management
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17910
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1587
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
SCIP_RETCODE SCIPcopy(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool threadsafe, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip_copy.c:2857
public solving methods
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:95
static SCIP_DECL_HEURINIT(heurInitZeroobj)
Definition: heur_zeroobj.c:168
#define HEUR_FREQOFS
Definition: heur_zeroobj.c:57
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1865
#define DEFAULT_ADDALLSOLS
Definition: heur_zeroobj.c:73
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip_sol.c:2254
#define FALSE
Definition: def.h:87
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
SCIP_RETCODE SCIPapplyZeroobj(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real minimprove, SCIP_Longint nnodes)
Definition: heur_zeroobj.c:495
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:315
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_param.c:102
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3278
SCIP_Real SCIPinfinity(SCIP *scip)
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:923
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:288
SCIP_RETCODE SCIPtranslateSubSol(SCIP *scip, SCIP *subscip, SCIP_SOL *subsol, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_SOL **newsol)
Definition: scip_copy.c:1399
#define DEFAULT_USEUCT
Definition: heur_zeroobj.c:75
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
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_heur.c:108
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3201
#define SCIP_LONGINT_MAX
Definition: def.h:163
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:283
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1362
public methods for SCIP variables
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:5029
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
public methods for numerical tolerances
public methods for querying solving statistics
public methods for the branch-and-bound tree
#define DEFAULT_ONLYWITHOUTSOL
Definition: heur_zeroobj.c:74
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17920
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2613
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1441
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:210
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2769
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
public methods for event handler plugins and event handlers
static SCIP_DECL_HEURCOPY(heurCopyZeroobj)
Definition: heur_zeroobj.c:133
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:420
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
#define EVENTHDLR_NAME
Definition: heur_zeroobj.c:63
SCIP_RETCODE SCIPincludeHeurZeroobj(SCIP *scip)
Definition: heur_zeroobj.c:549
#define DEFAULT_MINIMPROVE
Definition: heur_zeroobj.c:68
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:164
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3048
#define NULL
Definition: lpi_spx1.cpp:155
public methods for problem copies
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1567
public methods for primal heuristic plugins and divesets
public methods for constraint handler plugins and constraints
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_var.c:4510
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:84
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:277
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:1021
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:661
#define DEFAULT_MAXNODES
Definition: heur_zeroobj.c:67
#define MAX(x, y)
Definition: tclique_def.h:83
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_sol.c:3231
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:478
#define HEUR_PRIORITY
Definition: heur_zeroobj.c:55
#define HEUR_TIMING
Definition: heur_zeroobj.c:59
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:311
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17758
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2205
static SCIP_DECL_EVENTEXEC(eventExecZeroobj)
Definition: heur_zeroobj.c:108
Constraint handler for linear constraints in their most general form, .
int SCIPgetNObjVars(SCIP *scip)
Definition: scip_prob.c:2219
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
public methods for the LP relaxation, rows and columns
#define SCIP_EVENTTYPE_NODESOLVED
Definition: type_event.h:127
#define DEFAULT_NODESQUOT
Definition: heur_zeroobj.c:72
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)
public methods for branching rule plugins and branching
static SCIP_DECL_HEURFREE(heurFreeZeroobj)
Definition: heur_zeroobj.c:147
static SCIP_DECL_HEUREXEC(heurExecZeroobj)
Definition: heur_zeroobj.c:188
public methods for managing events
general public methods
#define HEUR_NAME
Definition: heur_zeroobj.c:52
public methods for solutions
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_cons.c:1110
#define HEUR_DISPCHAR
Definition: heur_zeroobj.c:54
public methods for message output
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
#define HEUR_USESSUBSCIP
Definition: heur_zeroobj.c:60
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip_nodesel.c:225
#define SCIP_Real
Definition: def.h:177
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:694
#define HEUR_DESC
Definition: heur_zeroobj.c:53
public methods for message handling
#define HEUR_MAXDEPTH
Definition: heur_zeroobj.c:58
#define SCIP_Longint
Definition: def.h:162
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3235
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip_solve.c:358
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
#define nnodes
Definition: gastrans.c:65
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
Definition: scip_solve.c:3516
SCIP_Real SCIPgetUpperbound(SCIP *scip)
public methods for primal heuristics
SCIPallocBlockMemory(scip, subsol))
#define SCIP_CALL_ABORT(x)
Definition: def.h:363
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1352
SCIP_Longint SCIPgetNNodes(SCIP *scip)
public methods for global and local (sub)problems
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_param.c:130
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:874
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:536
#define DEFAULT_MINNODES
Definition: heur_zeroobj.c:69
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_param.c:48
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:315
#define EVENTHDLR_DESC
Definition: heur_zeroobj.c:64
memory allocation routines