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-2020 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  /* employ a limit on the number of enforcement rounds in the quadratic constraint handler; this fixes the issue that
386  * sometimes the quadratic constraint handler needs hundreds or thousands of enforcement rounds to determine the
387  * feasibility status of a single node without fractional branching candidates by separation (namely for uflquad
388  * instances); however, the solution status of the sub-SCIP might get corrupted by this; hence no deductions shall be
389  * made for the original SCIP
390  */
391  if( SCIPfindConshdlr(subscip, "quadratic") != NULL && !SCIPisParamFixed(subscip, "constraints/quadratic/enfolplimit") )
392  {
393  SCIP_CALL( SCIPsetIntParam(subscip, "constraints/quadratic/enfolplimit", 10) );
394  }
395 
396  /* disable feaspump and fracdiving */
397  if( !SCIPisParamFixed(subscip, "heuristics/feaspump/freq") )
398  {
399  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/feaspump/freq", -1) );
400  }
401  if( !SCIPisParamFixed(subscip, "heuristics/fracdiving/freq") )
402  {
403  SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/fracdiving/freq", -1) );
404  }
405 
406  /* speed up sub-SCIP by not checking dual LP feasibility */
407  SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
408 
409  /* restrict LP iterations */
410  SCIP_CALL( SCIPsetLongintParam(subscip, "lp/iterlim", 2*heurdata->maxlpiters / MAX(1,nnodes)) );
411  SCIP_CALL( SCIPsetLongintParam(subscip, "lp/rootiterlim", heurdata->maxlpiters) );
412 
413  /* if there is already a solution, add an objective cutoff */
414  if( SCIPgetNSols(scip) > 0 )
415  {
416  SCIP_Real upperbound;
417  SCIP_CONS* origobjcons;
418 #ifndef NDEBUG
419  int nobjvars;
420  nobjvars = 0;
421 #endif
422 
423  assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
424 
425  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
426 
427  if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(scip)) )
428  {
429  cutoff = (1-minimprove)*SCIPgetUpperbound(scip) + minimprove*SCIPgetLowerbound(scip);
430  }
431  else
432  {
433  if( SCIPgetUpperbound(scip) >= 0 )
434  cutoff = ( 1 - minimprove ) * SCIPgetUpperbound ( scip );
435  else
436  cutoff = ( 1 + minimprove ) * SCIPgetUpperbound ( scip );
437  }
438  cutoff = MIN(upperbound, cutoff);
439 
440  SCIP_CALL( SCIPcreateConsLinear(subscip, &origobjcons, "objbound_of_origscip", 0, NULL, NULL, -SCIPinfinity(subscip), cutoff,
442  for( i = 0; i < nvars; ++i)
443  {
444  if( !SCIPisFeasZero(subscip, SCIPvarGetObj(vars[i])) )
445  {
446  assert(subvars[i] != NULL); /* subvars[i] can be NULL for relax-only vars, but they cannot appear in the objective */
447  SCIP_CALL( SCIPaddCoefLinear(subscip, origobjcons, subvars[i], SCIPvarGetObj(vars[i])) );
448 #ifndef NDEBUG
449  nobjvars++;
450 #endif
451  }
452  }
453  SCIP_CALL( SCIPaddCons(subscip, origobjcons) );
454  SCIP_CALL( SCIPreleaseCons(subscip, &origobjcons) );
455  assert(nobjvars == SCIPgetNObjVars(scip));
456  }
457 
458  /* catch LP events of sub-SCIP */
459  SCIP_CALL( SCIPtransformProb(subscip) );
460  SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_NODESOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
461 
462  SCIPdebugMsg(scip, "solving subproblem: nnodes=%" SCIP_LONGINT_FORMAT "\n", nnodes);
463 
464  /* errors in solving the subproblem should not kill the overall solving process;
465  * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
466  */
467  SCIP_CALL_ABORT( SCIPsolve(subscip) );
468 
469  /* drop LP events of sub-SCIP */
470  SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_NODESOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
471 
472  /* check, whether a solution was found;
473  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
474  */
475  nsubsols = SCIPgetNSols(subscip);
476  subsols = SCIPgetSols(subscip);
477  success = FALSE;
478  for( i = 0; i < nsubsols && (!success || heurdata->addallsols); ++i )
479  {
480  SCIP_SOL* newsol;
481 
482  SCIP_CALL( SCIPtranslateSubSol(scip, subscip, subsols[i], heur, subvars, &newsol) );
483 
484  SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
485  if( success )
486  *result = SCIP_FOUNDSOL;
487  }
488 
489 #ifdef SCIP_DEBUG
490  SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
491 #endif
492 
493  /* free subproblem */
494  SCIPfreeBufferArray(scip, &subvars);
495 
496  return SCIP_OKAY;
497 }
498 
499 
500 /*
501  * primal heuristic specific interface methods
502  */
503 
504 
505 /** main procedure of the zeroobj heuristic, creates and solves a sub-SCIP */
507  SCIP* scip, /**< original SCIP data structure */
508  SCIP_HEUR* heur, /**< heuristic data structure */
509  SCIP_RESULT* result, /**< result data structure */
510  SCIP_Real minimprove, /**< factor by which zeroobj should at least improve the incumbent */
511  SCIP_Longint nnodes /**< node limit for the subproblem */
512  )
513 {
514  SCIP* subscip; /* the subproblem created by zeroobj */
515  SCIP_HEURDATA* heurdata; /* heuristic's private data structure */
516  SCIP_Bool success;
517  SCIP_RETCODE retcode;
518 
519  assert(scip != NULL);
520  assert(heur != NULL);
521  assert(result != NULL);
522 
523  assert(nnodes >= 0);
524  assert(0.0 <= minimprove && minimprove <= 1.0);
525 
526  *result = SCIP_DIDNOTRUN;
527 
528  /* only call heuristic once at the root */
529  if( SCIPgetDepth(scip) <= 0 && SCIPheurGetNCalls(heur) > 0 )
530  return SCIP_OKAY;
531 
532  /* get heuristic data */
533  heurdata = SCIPheurGetData(heur);
534  assert(heurdata != NULL);
535 
536  /* only call the heuristic if we do not have an incumbent */
537  if( SCIPgetNSolsFound(scip) > 0 && heurdata->onlywithoutsol )
538  return SCIP_OKAY;
539 
540  /* check whether there is enough time and memory left */
541  SCIP_CALL( SCIPcheckCopyLimits(scip, &success) );
542 
543  if( !success )
544  return SCIP_OKAY;
545 
546  *result = SCIP_DIDNOTFIND;
547 
548  /* initialize the subproblem */
549  SCIP_CALL( SCIPcreate(&subscip) );
550 
551  retcode = setupAndSolveSubscip(scip, subscip, heur, result, minimprove, nnodes);
552 
553  SCIP_CALL( SCIPfree(&subscip) );
554 
555  return retcode;
556 }
557 
558 
559 /** creates the zeroobj primal heuristic and includes it in SCIP */
561  SCIP* scip /**< SCIP data structure */
562  )
563 {
564  SCIP_HEURDATA* heurdata;
565  SCIP_HEUR* heur;
566 
567  /* create heuristic data */
568  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
569 
570  /* include primal heuristic */
571  heur = NULL;
572  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
574  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecZeroobj, heurdata) );
575  assert(heur != NULL);
576 
577  /* set non-NULL pointers to callback methods */
578  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyZeroobj) );
579  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeZeroobj) );
580  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitZeroobj) );
581 
582  /* add zeroobj primal heuristic parameters */
583  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
584  "maximum number of nodes to regard in the subproblem",
585  &heurdata->maxnodes, TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
586 
587  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
588  "number of nodes added to the contingent of the total nodes",
589  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
590 
591  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
592  "minimum number of nodes required to start the subproblem",
593  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
594 
595  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxlpiters",
596  "maximum number of LP iterations to be performed in the subproblem",
597  &heurdata->maxlpiters, TRUE, DEFAULT_MAXLPITERS, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
598 
599  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
600  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
601  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
602 
603  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
604  "factor by which zeroobj should at least improve the incumbent",
605  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
606 
607  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/addallsols",
608  "should all subproblem solutions be added to the original SCIP?",
609  &heurdata->addallsols, TRUE, DEFAULT_ADDALLSOLS, NULL, NULL) );
610 
611  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlywithoutsol",
612  "should heuristic only be executed if no primal solution was found, yet?",
613  &heurdata->onlywithoutsol, TRUE, DEFAULT_ONLYWITHOUTSOL, NULL, NULL) );
614  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct",
615  "should uct node selection be used at the beginning of the search?",
616  &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) );
617 
618  return SCIP_OKAY;
619 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
#define HEUR_FREQ
Definition: heur_zeroobj.c:56
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
SCIP_Real SCIPfeastol(SCIP *scip)
#define DEFAULT_MAXLPITERS
Definition: heur_zeroobj.c:70
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1555
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:237
#define DEFAULT_NODESOFS
Definition: heur_zeroobj.c:71
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:687
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1429
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:1340
SCIP_RETCODE SCIPtranslateSubSol(SCIP *scip, SCIP *subscip, SCIP_SOL *subsol, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_SOL **newsol)
Definition: scip_copy.c:1356
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
Definition: scip_solve.c:3407
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:357
static SCIP_DECL_HEURINIT(heurInitZeroobj)
Definition: heur_zeroobj.c:168
#define HEUR_FREQOFS
Definition: heur_zeroobj.c:57
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:315
#define DEFAULT_ADDALLSOLS
Definition: heur_zeroobj.c:73
#define FALSE
Definition: def.h:73
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17515
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
#define DEFAULT_USEUCT
Definition: heur_zeroobj.c:75
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2527
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3200
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
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:2814
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:48
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:893
SCIP_Real SCIPgetUpperbound(SCIP *scip)
#define SCIP_LONGINT_MAX
Definition: def.h:149
#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:185
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3192
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1575
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
public methods for numerical tolerances
public methods for querying solving statistics
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2206
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
public methods for the branch-and-bound tree
#define DEFAULT_ONLYWITHOUTSOL
Definition: heur_zeroobj.c:74
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:283
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:288
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:277
static SCIP_DECL_HEURCOPY(heurCopyZeroobj)
Definition: heur_zeroobj.c:133
int SCIPgetNObjVars(SCIP *scip)
Definition: scip_prob.c:2214
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
#define EVENTHDLR_NAME
Definition: heur_zeroobj.c:63
#define DEFAULT_MINIMPROVE
Definition: heur_zeroobj.c:68
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:164
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1350
#define NULL
Definition: lpi_spx1.cpp:155
public methods for problem copies
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip_nodesel.c:225
#define SCIP_CALL(x)
Definition: def.h:364
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:942
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:1021
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
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:638
#define SCIP_Bool
Definition: def.h:70
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3013
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17677
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:210
#define DEFAULT_MAXNODES
Definition: heur_zeroobj.c:67
#define MAX(x, y)
Definition: tclique_def.h:83
#define HEUR_PRIORITY
Definition: heur_zeroobj.c:55
#define HEUR_TIMING
Definition: heur_zeroobj.c:59
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4943
static SCIP_DECL_EVENTEXEC(eventExecZeroobj)
Definition: heur_zeroobj.c:108
Constraint handler for linear constraints in their most general form, .
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3228
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
SCIP_RETCODE SCIPapplyZeroobj(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real minimprove, SCIP_Longint nnodes)
Definition: heur_zeroobj.c:506
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
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 SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:555
public methods for branching rule plugins and branching
static SCIP_DECL_HEURFREE(heurFreeZeroobj)
Definition: heur_zeroobj.c:147
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:5030
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
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
public methods for solutions
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_var.c:4514
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:2255
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:311
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17667
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
#define HEUR_DISPCHAR
Definition: heur_zeroobj.c:54
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:1860
#define HEUR_USESSUBSCIP
Definition: heur_zeroobj.c:60
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3047
#define SCIP_Real
Definition: def.h:163
#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:148
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:439
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
SCIP_RETCODE SCIPincludeHeurZeroobj(SCIP *scip)
Definition: heur_zeroobj.c:560
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 SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2764
#define nnodes
Definition: gastrans.c:65
public methods for primal heuristics
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:315
#define SCIP_CALL_ABORT(x)
Definition: def.h:343
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
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
public methods for global and local (sub)problems
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:497
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:968
#define DEFAULT_MINNODES
Definition: heur_zeroobj.c:69
#define EVENTHDLR_DESC
Definition: heur_zeroobj.c:64
memory allocation routines