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-2019 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 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 "blockmemshell/memory.h"
24 #include "scip/cons_linear.h"
25 #include "scip/heur_zeroobj.h"
26 #include "scip/pub_event.h"
27 #include "scip/pub_heur.h"
28 #include "scip/pub_message.h"
29 #include "scip/pub_misc.h"
30 #include "scip/pub_var.h"
31 #include "scip/scip_branch.h"
32 #include "scip/scip_cons.h"
33 #include "scip/scip_copy.h"
34 #include "scip/scip_event.h"
35 #include "scip/scip_general.h"
36 #include "scip/scip_heur.h"
37 #include "scip/scip_lp.h"
38 #include "scip/scip_mem.h"
39 #include "scip/scip_message.h"
40 #include "scip/scip_nodesel.h"
41 #include "scip/scip_numerics.h"
42 #include "scip/scip_param.h"
43 #include "scip/scip_prob.h"
44 #include "scip/scip_sol.h"
45 #include "scip/scip_solve.h"
46 #include "scip/scip_solvingstats.h"
47 #include "scip/scip_tree.h"
48 #include "scip/scip_var.h"
49 #include <string.h>
50 
51 #define HEUR_NAME "zeroobj"
52 #define HEUR_DESC "heuristic trying to solve the problem without objective"
53 #define HEUR_DISPCHAR 'Z'
54 #define HEUR_PRIORITY 100
55 #define HEUR_FREQ -1
56 #define HEUR_FREQOFS 0
57 #define HEUR_MAXDEPTH 0
58 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_BEFOREPRESOL
59 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
60 
61 /* event handler properties */
62 #define EVENTHDLR_NAME "Zeroobj"
63 #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic"
64 
65 /* default values for zeroobj-specific plugins */
66 #define DEFAULT_MAXNODES 1000LL /* maximum number of nodes to regard in the subproblem */
67 #define DEFAULT_MINIMPROVE 0.01 /* factor by which zeroobj should at least improve the incumbent */
68 #define DEFAULT_MINNODES 100LL /* minimum number of nodes to regard in the subproblem */
69 #define DEFAULT_MAXLPITERS 5000LL /* maximum number of LP iterations to be performed in the subproblem */
70 #define DEFAULT_NODESOFS 100LL /* number of nodes added to the contingent of the total nodes */
71 #define DEFAULT_NODESQUOT 0.1 /* subproblem nodes in relation to nodes of the original problem */
72 #define DEFAULT_ADDALLSOLS FALSE /* should all subproblem solutions be added to the original SCIP? */
73 #define DEFAULT_ONLYWITHOUTSOL TRUE /**< should heuristic only be executed if no primal solution was found, yet? */
74 #define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */
75 
76 /*
77  * Data structures
78  */
79 
80 /** primal heuristic data */
81 struct SCIP_HeurData
82 {
83  SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
84  SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
85  SCIP_Longint maxlpiters; /**< maximum number of LP iterations to be performed in the subproblem */
86  SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
87  SCIP_Longint usednodes; /**< nodes already used by zeroobj in earlier calls */
88  SCIP_Real minimprove; /**< factor by which zeroobj should at least improve the incumbent */
89  SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
90  SCIP_Bool addallsols; /**< should all subproblem solutions be added to the original SCIP? */
91  SCIP_Bool onlywithoutsol; /**< should heuristic only be executed if no primal solution was found, yet? */
92  SCIP_Bool useuct; /**< should uct node selection be used at the beginning of the search? */
93 };
94 
95 
96 /*
97  * Local methods
98  */
99 
100 /** creates a new solution for the original problem by copying the solution of the subproblem */
101 static
103  SCIP* scip, /**< original SCIP data structure */
104  SCIP* subscip, /**< SCIP structure of the subproblem */
105  SCIP_VAR** subvars, /**< the variables of the subproblem */
106  SCIP_HEUR* heur, /**< zeroobj heuristic structure */
107  SCIP_SOL* subsol, /**< solution of the subproblem */
108  SCIP_Bool* success /**< used to store whether new solution was found or not */
109  )
110 {
111  SCIP_VAR** vars; /* the original problem's variables */
112  int nvars; /* the original problem's number of variables */
113  SCIP_Real* subsolvals; /* solution values of the subproblem */
114  SCIP_SOL* newsol; /* solution to be created for the original problem */
115 
116  assert(scip != NULL);
117  assert(subscip != NULL);
118  assert(subvars != NULL);
119  assert(subsol != NULL);
120 
121  /* get variables' data */
122  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
123 
124  /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
125  * since constraint copying may have required the copy of variables that are fixed in the main SCIP
126  */
127  assert(nvars <= SCIPgetNOrigVars(subscip));
128 
129  SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
130 
131  /* copy the solution */
132  SCIP_CALL( SCIPgetSolVals(subscip, subsol, nvars, subvars, subsolvals) );
133 
134  /* create new solution for the original problem */
135  SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
136  SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
137 
138  /* try to add new solution to scip and free it immediately */
139  SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
140 
141  SCIPfreeBufferArray(scip, &subsolvals);
142 
143  return SCIP_OKAY;
144 }
145 
146 /* ---------------- Callback methods of event handler ---------------- */
147 
148 /* exec the event handler
149  *
150  * we interrupt the solution process
151  */
152 static
153 SCIP_DECL_EVENTEXEC(eventExecZeroobj)
154 {
155  SCIP_HEURDATA* heurdata;
156 
157  assert(eventhdlr != NULL);
158  assert(eventdata != NULL);
159  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
160  assert(event != NULL);
162 
163  heurdata = (SCIP_HEURDATA*)eventdata;
164  assert(heurdata != NULL);
165 
166  /* interrupt solution process of sub-SCIP */
167  if( SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_ITERLIMIT || SCIPgetNLPIterations(scip) >= heurdata->maxlpiters )
168  {
170  }
171 
172  return SCIP_OKAY;
173 }
174 /* ---------------- Callback methods of primal heuristic ---------------- */
175 
176 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
177 static
178 SCIP_DECL_HEURCOPY(heurCopyZeroobj)
179 { /*lint --e{715}*/
180  assert(scip != NULL);
181  assert(heur != NULL);
182  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
183 
184  /* call inclusion method of primal heuristic */
186 
187  return SCIP_OKAY;
188 }
189 
190 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
191 static
192 SCIP_DECL_HEURFREE(heurFreeZeroobj)
193 { /*lint --e{715}*/
194  SCIP_HEURDATA* heurdata;
195 
196  assert( heur != NULL );
197  assert( scip != NULL );
198 
199  /* get heuristic data */
200  heurdata = SCIPheurGetData(heur);
201  assert( heurdata != NULL );
202 
203  /* free heuristic data */
204  SCIPfreeBlockMemory(scip, &heurdata);
205  SCIPheurSetData(heur, NULL);
206 
207  return SCIP_OKAY;
208 }
209 
210 
211 /** initialization method of primal heuristic (called after problem was transformed) */
212 static
213 SCIP_DECL_HEURINIT(heurInitZeroobj)
214 { /*lint --e{715}*/
215  SCIP_HEURDATA* heurdata;
216 
217  assert( heur != NULL );
218  assert( scip != NULL );
219 
220  /* get heuristic data */
221  heurdata = SCIPheurGetData(heur);
222  assert( heurdata != NULL );
223 
224  /* initialize data */
225  heurdata->usednodes = 0;
226 
227  return SCIP_OKAY;
228 }
229 
230 
231 /** execution method of primal heuristic */
232 static
233 SCIP_DECL_HEUREXEC(heurExecZeroobj)
234 { /*lint --e{715}*/
235  SCIP_HEURDATA* heurdata; /* heuristic's data */
236  SCIP_Longint nnodes; /* number of stalling nodes for the subproblem */
237 
238  assert( heur != NULL );
239  assert( scip != NULL );
240  assert( result != NULL );
241 
242  /* get heuristic data */
243  heurdata = SCIPheurGetData(heur);
244  assert( heurdata != NULL );
245 
246  /* calculate the maximal number of branching nodes until heuristic is aborted */
247  nnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
248 
249  /* reward zeroobj if it succeeded often */
250  nnodes = (SCIP_Longint)(nnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
251  nnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-SCIP as 100 nodes */
252  nnodes += heurdata->nodesofs;
253 
254  /* determine the node limit for the current process */
255  nnodes -= heurdata->usednodes;
256  nnodes = MIN(nnodes, heurdata->maxnodes);
257 
258  /* check whether we have enough nodes left to call subproblem solving */
259  if( nnodes < heurdata->minnodes )
260  {
261  SCIPdebugMsg(scip, "skipping zeroobj: nnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nnodes, heurdata->minnodes);
262  return SCIP_OKAY;
263  }
264 
265  /* do not run zeroobj, if the problem does not have an objective function anyway */
266  if( SCIPgetNObjVars(scip) == 0 )
267  {
268  SCIPdebugMsg(scip, "skipping zeroobj: pure feasibility problem anyway\n");
269  return SCIP_OKAY;
270  }
271 
272  if( SCIPisStopped(scip) )
273  return SCIP_OKAY;
274 
275  SCIP_CALL( SCIPapplyZeroobj(scip, heur, result, heurdata->minimprove, nnodes) );
276 
277  return SCIP_OKAY;
278 }
279 
280 /** setup and solve subscip */
281 static
283  SCIP* scip, /**< SCIP data structure */
284  SCIP* subscip, /**< SCIP data structure */
285  SCIP_HEUR* heur, /**< heuristic data structure */
286  SCIP_RESULT* result, /**< result data structure */
287  SCIP_Real minimprove, /**< factor by which zeroobj should at least improve the incumbent */
288  SCIP_Longint nnodes /**< node limit for the subproblem */
289  )
290 {
291  SCIP_Real cutoff; /* objective cutoff for the subproblem */
292  SCIP_Real large;
293  SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
294  SCIP_VAR** vars; /* original problem's variables */
295  SCIP_VAR** subvars; /* subproblem's variables */
296  SCIP_SOL** subsols;
297  SCIP_HEURDATA* heurdata; /* heuristic's private data structure */
298  SCIP_EVENTHDLR* eventhdlr; /* event handler for LP events */
299 
300  int nsubsols;
301  int nvars; /* number of original problem's variables */
302  int i;
303  SCIP_Bool success;
304  SCIP_Bool valid;
305 
306  assert(scip != NULL);
307  assert(subscip != NULL);
308  assert(heur != NULL);
309  assert(result != NULL);
310 
311  heurdata = SCIPheurGetData(heur);
312  assert(heurdata != NULL);
313 
314  /* get variable data */
315  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
316 
317  /* create the variable mapping hash map */
318  SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
319  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
320 
321  /* different methods to create sub-problem: either copy LP relaxation or the CIP with all constraints */
322  valid = FALSE;
323 
324  /* copy complete SCIP instance */
325  SCIP_CALL( SCIPcopy(scip, subscip, varmapfw, NULL, "zeroobj", TRUE, FALSE, TRUE, &valid) );
326  SCIPdebugMsg(scip, "Copying the SCIP instance was %s complete.\n", valid ? "" : "not ");
327 
328  /* create event handler for LP events */
329  eventhdlr = NULL;
330  SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecZeroobj, NULL) );
331  if( eventhdlr == NULL )
332  {
333  SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
334  return SCIP_PLUGINNOTFOUND;
335  }
336 
337  /* determine large value to set variables to */
338  large = SCIPinfinity(scip);
339  if( !SCIPisInfinity(scip, 0.1 / SCIPfeastol(scip)) )
340  large = 0.1 / SCIPfeastol(scip);
341 
342  /* get variable image and change to 0.0 in sub-SCIP */
343  for( i = 0; i < nvars; i++ )
344  {
345  SCIP_Real adjustedbound;
346  SCIP_Real lb;
347  SCIP_Real ub;
348  SCIP_Real inf;
349 
350  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
351  SCIP_CALL( SCIPchgVarObj(subscip, subvars[i], 0.0) );
352 
353  lb = SCIPvarGetLbGlobal(subvars[i]);
354  ub = SCIPvarGetUbGlobal(subvars[i]);
355  inf = SCIPinfinity(subscip);
356 
357  /* adjust infinite bounds in order to avoid that variables with non-zero objective
358  * get fixed to infinite value in zeroobj subproblem
359  */
360  if( SCIPisInfinity(subscip, ub ) )
361  {
362  adjustedbound = MAX(large, lb+large);
363  adjustedbound = MIN(adjustedbound, inf);
364  SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], adjustedbound) );
365  }
366  if( SCIPisInfinity(subscip, -lb ) )
367  {
368  adjustedbound = MIN(-large, ub-large);
369  adjustedbound = MAX(adjustedbound, -inf);
370  SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], adjustedbound) );
371  }
372  }
373 
374  /* free hash map */
375  SCIPhashmapFree(&varmapfw);
376 
377  /* do not abort subproblem on CTRL-C */
378  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
379 
380 #ifdef SCIP_DEBUG
381  /* for debugging, enable full output */
382  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
383  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
384 #else
385  /* disable statistic timing inside sub SCIP and output to console */
386  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
387  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
388 #endif
389 
390  /* set limits for the subproblem */
391  SCIP_CALL( SCIPcopyLimits(scip, subscip) );
392  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nnodes) );
393  SCIP_CALL( SCIPsetIntParam(subscip, "limits/solutions", 1) );
394 
395  /* forbid recursive call of heuristics and separators solving sub-SCIPs */
396  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
397 
398  /* disable expensive techniques that merely work on the dual bound */
399 
400  /* disable cutting plane separation */
402 
403  /* disable expensive presolving */
405  if( !SCIPisParamFixed(subscip, "presolving/maxrounds") )
406  {
407  SCIP_CALL( SCIPsetIntParam(subscip, "presolving/maxrounds", 50) );
408  }
409 
410  /* use restart dfs node selection */
411  if( SCIPfindNodesel(subscip, "restartdfs") != NULL && !SCIPisParamFixed(subscip, "nodeselection/restartdfs/stdpriority") )
412  {
413  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/restartdfs/stdpriority", INT_MAX/4) );
414  }
415 
416  /* activate uct node selection at the top of the tree */
417  if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") )
418  {
419  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) );
420  }
421  /* use least infeasible branching */
422  if( SCIPfindBranchrule(subscip, "leastinf") != NULL && !SCIPisParamFixed(subscip, "branching/leastinf/priority") )
423  {
424  SCIP_CALL( SCIPsetIntParam(subscip, "branching/leastinf/priority", INT_MAX/4) );
425  }
426 
427  /* employ a limit on the number of enforcement rounds in the quadratic constraint handler; this fixes the issue that
428  * sometimes the quadratic constraint handler needs hundreds or thousands of enforcement rounds to determine the
429  * feasibility status of a single node without fractional branching candidates by separation (namely for uflquad
430  * instances); however, the solution status of the sub-SCIP might get corrupted by this; hence no deductions shall be
431  * made for the original SCIP
432  */
433  if( SCIPfindConshdlr(subscip, "quadratic") != NULL && !SCIPisParamFixed(subscip, "constraints/quadratic/enfolplimit") )
434  {
435  SCIP_CALL( SCIPsetIntParam(subscip, "constraints/quadratic/enfolplimit", 10) );
436  }
437 
438  /* disable feaspump and fracdiving */
439  if( !SCIPisParamFixed(subscip, "heuristics/feaspump/freq") )
440  {
441  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/feaspump/freq", -1) );
442  }
443  if( !SCIPisParamFixed(subscip, "heuristics/fracdiving/freq") )
444  {
445  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/fracdiving/freq", -1) );
446  }
447 
448  /* speed up sub-SCIP by not checking dual LP feasibility */
449  SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
450 
451  /* restrict LP iterations */
452  SCIP_CALL( SCIPsetLongintParam(subscip, "lp/iterlim", 2*heurdata->maxlpiters / MAX(1,nnodes)) );
453  SCIP_CALL( SCIPsetLongintParam(subscip, "lp/rootiterlim", heurdata->maxlpiters) );
454 
455  /* if there is already a solution, add an objective cutoff */
456  if( SCIPgetNSols(scip) > 0 )
457  {
458  SCIP_Real upperbound;
459  SCIP_CONS* origobjcons;
460 #ifndef NDEBUG
461  int nobjvars;
462  nobjvars = 0;
463 #endif
464 
465  assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
466 
467  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
468 
469  if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(scip)) )
470  {
471  cutoff = (1-minimprove)*SCIPgetUpperbound(scip) + minimprove*SCIPgetLowerbound(scip);
472  }
473  else
474  {
475  if( SCIPgetUpperbound(scip) >= 0 )
476  cutoff = ( 1 - minimprove ) * SCIPgetUpperbound ( scip );
477  else
478  cutoff = ( 1 + minimprove ) * SCIPgetUpperbound ( scip );
479  }
480  cutoff = MIN(upperbound, cutoff);
481 
482  SCIP_CALL( SCIPcreateConsLinear(subscip, &origobjcons, "objbound_of_origscip", 0, NULL, NULL, -SCIPinfinity(subscip), cutoff,
484  for( i = 0; i < nvars; ++i)
485  {
486  if( !SCIPisFeasZero(subscip, SCIPvarGetObj(vars[i])) )
487  {
488  SCIP_CALL( SCIPaddCoefLinear(subscip, origobjcons, subvars[i], SCIPvarGetObj(vars[i])) );
489 #ifndef NDEBUG
490  nobjvars++;
491 #endif
492  }
493  }
494  SCIP_CALL( SCIPaddCons(subscip, origobjcons) );
495  SCIP_CALL( SCIPreleaseCons(subscip, &origobjcons) );
496  assert(nobjvars == SCIPgetNObjVars(scip));
497  }
498 
499  /* catch LP events of sub-SCIP */
500  SCIP_CALL( SCIPtransformProb(subscip) );
501  SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_NODESOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
502 
503  SCIPdebugMsg(scip, "solving subproblem: nnodes=%" SCIP_LONGINT_FORMAT "\n", nnodes);
504 
505  /* errors in solving the subproblem should not kill the overall solving process;
506  * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
507  */
508  SCIP_CALL_ABORT( SCIPsolve(subscip) );
509 
510  /* drop LP events of sub-SCIP */
511  SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_NODESOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
512 
513  /* check, whether a solution was found;
514  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
515  */
516  nsubsols = SCIPgetNSols(subscip);
517  subsols = SCIPgetSols(subscip);
518  success = FALSE;
519  for( i = 0; i < nsubsols && (!success || heurdata->addallsols); ++i )
520  {
521  SCIP_CALL( createNewSol(scip, subscip, subvars, heur, subsols[i], &success) );
522  if( success )
523  *result = SCIP_FOUNDSOL;
524  }
525 
526 #ifdef SCIP_DEBUG
527  SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
528 #endif
529 
530  /* free subproblem */
531  SCIPfreeBufferArray(scip, &subvars);
532 
533  return SCIP_OKAY;
534 }
535 
536 
537 /*
538  * primal heuristic specific interface methods
539  */
540 
541 
542 /** main procedure of the zeroobj heuristic, creates and solves a sub-SCIP */
544  SCIP* scip, /**< original SCIP data structure */
545  SCIP_HEUR* heur, /**< heuristic data structure */
546  SCIP_RESULT* result, /**< result data structure */
547  SCIP_Real minimprove, /**< factor by which zeroobj should at least improve the incumbent */
548  SCIP_Longint nnodes /**< node limit for the subproblem */
549  )
550 {
551  SCIP* subscip; /* the subproblem created by zeroobj */
552  SCIP_HEURDATA* heurdata; /* heuristic's private data structure */
553  SCIP_Bool success;
554  SCIP_RETCODE retcode;
555 
556  assert(scip != NULL);
557  assert(heur != NULL);
558  assert(result != NULL);
559 
560  assert(nnodes >= 0);
561  assert(0.0 <= minimprove && minimprove <= 1.0);
562 
563  *result = SCIP_DIDNOTRUN;
564 
565  /* only call heuristic once at the root */
566  if( SCIPgetDepth(scip) <= 0 && SCIPheurGetNCalls(heur) > 0 )
567  return SCIP_OKAY;
568 
569  /* get heuristic data */
570  heurdata = SCIPheurGetData(heur);
571  assert(heurdata != NULL);
572 
573  /* only call the heuristic if we do not have an incumbent */
574  if( SCIPgetNSolsFound(scip) > 0 && heurdata->onlywithoutsol )
575  return SCIP_OKAY;
576 
577  /* check whether there is enough time and memory left */
578  SCIP_CALL( SCIPcheckCopyLimits(scip, &success) );
579 
580  if( !success )
581  return SCIP_OKAY;
582 
583  *result = SCIP_DIDNOTFIND;
584 
585  /* initialize the subproblem */
586  SCIP_CALL( SCIPcreate(&subscip) );
587 
588  retcode = setupAndSolveSubscip(scip, subscip, heur, result, minimprove, nnodes);
589 
590  SCIP_CALL( SCIPfree(&subscip) );
591 
592  return retcode;
593 }
594 
595 
596 /** creates the zeroobj primal heuristic and includes it in SCIP */
598  SCIP* scip /**< SCIP data structure */
599  )
600 {
601  SCIP_HEURDATA* heurdata;
602  SCIP_HEUR* heur;
603 
604  /* create heuristic data */
605  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
606 
607  /* include primal heuristic */
608  heur = NULL;
609  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
611  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecZeroobj, heurdata) );
612  assert(heur != NULL);
613 
614  /* set non-NULL pointers to callback methods */
615  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyZeroobj) );
616  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeZeroobj) );
617  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitZeroobj) );
618 
619  /* add zeroobj primal heuristic parameters */
620  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
621  "maximum number of nodes to regard in the subproblem",
622  &heurdata->maxnodes, TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
623 
624  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
625  "number of nodes added to the contingent of the total nodes",
626  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
627 
628  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
629  "minimum number of nodes required to start the subproblem",
630  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
631 
632  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxlpiters",
633  "maximum number of LP iterations to be performed in the subproblem",
634  &heurdata->maxlpiters, TRUE, DEFAULT_MAXLPITERS, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
635 
636  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
637  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
638  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
639 
640  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
641  "factor by which zeroobj should at least improve the incumbent",
642  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
643 
644  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/addallsols",
645  "should all subproblem solutions be added to the original SCIP?",
646  &heurdata->addallsols, TRUE, DEFAULT_ADDALLSOLS, NULL, NULL) );
647 
648  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlywithoutsol",
649  "should heuristic only be executed if no primal solution was found, yet?",
650  &heurdata->onlywithoutsol, TRUE, DEFAULT_ONLYWITHOUTSOL, NULL, NULL) );
651  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct",
652  "should uct node selection be used at the beginning of the search?",
653  &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) );
654 
655  return SCIP_OKAY;
656 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
#define HEUR_FREQ
Definition: heur_zeroobj.c:55
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
SCIP_Real SCIPfeastol(SCIP *scip)
#define DEFAULT_MAXLPITERS
Definition: heur_zeroobj.c:69
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1380
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_RETCODE setupAndSolveSubscip(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real minimprove, SCIP_Longint nnodes)
Definition: heur_zeroobj.c:282
#define DEFAULT_NODESOFS
Definition: heur_zeroobj.c:70
#define NULL
Definition: def.h:253
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:686
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:876
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1254
public methods for SCIP parameter handling
public methods for node selector plugins
public methods for memory management
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1165
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
Definition: scip_solve.c:3399
public solving methods
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip_solve.c:354
static SCIP_DECL_HEURINIT(heurInitZeroobj)
Definition: heur_zeroobj.c:213
#define HEUR_FREQOFS
Definition: heur_zeroobj.c:56
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:314
#define DEFAULT_ADDALLSOLS
Definition: heur_zeroobj.c:72
#define FALSE
Definition: def.h:73
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17200
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define DEFAULT_USEUCT
Definition: heur_zeroobj.c:74
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2535
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3078
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
public methods for problem variables
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:47
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:891
SCIP_Real SCIPgetUpperbound(SCIP *scip)
#define SCIP_LONGINT_MAX
Definition: def.h:150
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
public methods for SCIP variables
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:184
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:158
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:2911
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1400
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
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_copy.c:2550
public methods for numerical tolerances
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:319
public methods for querying solving statistics
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2205
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:107
public methods for the branch-and-bound tree
#define DEFAULT_ONLYWITHOUTSOL
Definition: heur_zeroobj.c:73
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:282
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:286
public methods for event handler plugins and event handlers
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:276
static SCIP_DECL_HEURCOPY(heurCopyZeroobj)
Definition: heur_zeroobj.c:178
int SCIPgetNObjVars(SCIP *scip)
Definition: scip_prob.c:2215
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:47
#define EVENTHDLR_NAME
Definition: heur_zeroobj.c:62
#define DEFAULT_MINIMPROVE
Definition: heur_zeroobj.c:67
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:155
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1175
public methods for problem copies
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip_nodesel.c:224
#define SCIP_CALL(x)
Definition: def.h:365
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:940
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:995
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip_prob.c:2427
public methods for primal heuristic plugins and divesets
public methods for constraint handler plugins and constraints
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_Real SCIPinfinity(SCIP *scip)
public data structures and miscellaneous methods
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1254
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:637
#define SCIP_Bool
Definition: def.h:70
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2891
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17362
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool *success)
Definition: heur_zeroobj.c:102
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:209
#define DEFAULT_MAXNODES
Definition: heur_zeroobj.c:66
#define MIN(x, y)
Definition: def.h:223
#define HEUR_PRIORITY
Definition: heur_zeroobj.c:54
#define HEUR_TIMING
Definition: heur_zeroobj.c:58
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4880
static SCIP_DECL_EVENTEXEC(eventExecZeroobj)
Definition: heur_zeroobj.c:153
Constraint handler for linear constraints in their most general form, .
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:2947
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:94
SCIP_RETCODE SCIPapplyZeroobj(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real minimprove, SCIP_Longint nnodes)
Definition: heur_zeroobj.c:543
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:129
public methods for the LP relaxation, rows and columns
#define SCIP_EVENTTYPE_NODESOLVED
Definition: type_event.h:119
#define DEFAULT_NODESQUOT
Definition: heur_zeroobj.c:71
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:554
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1389
#define SCIP_LONGINT_FORMAT
Definition: def.h:156
public methods for branching rule plugins and branching
static SCIP_DECL_HEURFREE(heurFreeZeroobj)
Definition: heur_zeroobj.c:192
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4967
static SCIP_DECL_HEUREXEC(heurExecZeroobj)
Definition: heur_zeroobj.c:233
public methods for managing events
general public methods
#define MAX(x, y)
Definition: def.h:222
#define HEUR_NAME
Definition: heur_zeroobj.c:51
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
public methods for solutions
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_var.c:4451
heuristic that tries to solve the problem without objective. In Gurobi, this heuristic is known as "H...
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip_sol.c:2254
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:310
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17352
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:152
#define HEUR_DISPCHAR
Definition: heur_zeroobj.c:53
public methods for message output
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1861
#define HEUR_USESSUBSCIP
Definition: heur_zeroobj.c:59
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2925
#define SCIP_Real
Definition: def.h:164
#define HEUR_DESC
Definition: heur_zeroobj.c:52
public methods for message handling
#define HEUR_MAXDEPTH
Definition: heur_zeroobj.c:57
#define SCIP_Longint
Definition: def.h:149
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:438
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:168
SCIP_RETCODE SCIPincludeHeurZeroobj(SCIP *scip)
Definition: heur_zeroobj.c:597
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:101
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2765
#define nnodes
Definition: gastrans.c:65
public methods for primal heuristics
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:314
#define SCIP_CALL_ABORT(x)
Definition: def.h:344
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1109
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:3218
public methods for global and local (sub)problems
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:496
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:966
#define DEFAULT_MINNODES
Definition: heur_zeroobj.c:68
#define EVENTHDLR_DESC
Definition: heur_zeroobj.c:63
memory allocation routines