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