Scippy

SCIP

Solving Constraint Integer Programs

heur_rins.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-2014 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_rins.c
17  * @brief LNS heuristic that combines the incumbent with the LP optimum
18  * @author Timo Berthold
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <assert.h>
24 #include <string.h>
25 #include "scip/scip.h"
26 #include "scip/scipdefplugins.h"
27 #include "scip/cons_linear.h"
28 #include "scip/heur_rins.h"
29 #include "scip/pub_misc.h"
30 
31 #define HEUR_NAME "rins"
32 #define HEUR_DESC "relaxation induced neighborhood search by Danna, Rothberg, and Le Pape"
33 #define HEUR_DISPCHAR 'N'
34 #define HEUR_PRIORITY -1101000
35 #define HEUR_FREQ 25
36 #define HEUR_FREQOFS 0
37 #define HEUR_MAXDEPTH -1
38 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE
39 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
40 
41 #define DEFAULT_NODESOFS 500 /* number of nodes added to the contingent of the total nodes */
42 #define DEFAULT_MAXNODES 5000 /* maximum number of nodes to regard in the subproblem */
43 #define DEFAULT_MINNODES 50 /* minimum number of nodes to regard in the subproblem */
44 #define DEFAULT_MINIMPROVE 0.01 /* factor by which RINS should at least improve the incumbent */
45 #define DEFAULT_MINFIXINGRATE 0.3 /* minimum percentage of integer variables that have to be fixed */
46 #define DEFAULT_NODESQUOT 0.1 /* subproblem nodes in relation to nodes of the original problem */
47 #define DEFAULT_LPLIMFAC 2.0 /* factor by which the limit on the number of LP depends on the node limit */
48 #define DEFAULT_NWAITINGNODES 200 /* number of nodes without incumbent change that heuristic should wait */
49 #define DEFAULT_USELPROWS FALSE /* should subproblem be created out of the rows in the LP rows,
50  * otherwise, the copy constructors of the constraints handlers are used */
51 #define DEFAULT_COPYCUTS TRUE /* if DEFAULT_USELPROWS is FALSE, then should all active cuts from the cutpool
52  * of the original scip be copied to constraints of the subscip
53  */
54 
55 /* event handler properties */
56 #define EVENTHDLR_NAME "Rins"
57 #define EVENTHDLR_DESC "LP event handler for "HEUR_NAME" heuristic"
58 
59 /*
60  * Data structures
61  */
62 
63 /** primal heuristic data */
64 struct SCIP_HeurData
65 {
66  int nodesofs; /**< number of nodes added to the contingent of the total nodes */
67  int maxnodes; /**< maximum number of nodes to regard in the subproblem */
68  int minnodes; /**< minimum number of nodes to regard in the subproblem */
69  SCIP_Real minfixingrate; /**< minimum percentage of integer variables that have to be fixed */
70  int nwaitingnodes; /**< number of nodes without incumbent change that heuristic should wait */
71  SCIP_Real minimprove; /**< factor by which RINS should at least improve the incumbent */
72  SCIP_Real nodelimit; /**< the nodelimit employed in the current sub-SCIP, for the event handler*/
73  SCIP_Real lplimfac; /**< factor by which the limit on the number of LP depends on the node limit */
74  SCIP_Longint usednodes; /**< nodes already used by RINS in earlier calls */
75  SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
76  SCIP_Bool uselprows; /**< should subproblem be created out of the rows in the LP rows? */
77  SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied
78  * to constraints in subproblem?
79  */
80 };
81 
82 /*
83  * Local methods
84  */
85 
86 /** creates a subproblem for subscip by fixing a number of variables */
87 static
88 SCIP_RETCODE createSubproblem(
89  SCIP* scip, /**< original SCIP data structure */
90  SCIP* subscip, /**< SCIP data structure for the subproblem */
91  SCIP_VAR** subvars, /**< the variables of the subproblem */
92  SCIP_Real minfixingrate, /**< percentage of integer variables that have to be fixed */
93  SCIP_Bool uselprows, /**< should subproblem be created out of the rows in the LP rows? */
94  SCIP_Bool* success /**< pointer to store whether the problem was created successfully */
95  )
96 {
97  SCIP_SOL* bestsol; /* incumbent solution of the original problem */
98  SCIP_VAR** vars; /* original scip variables */
99  SCIP_ROW** rows; /* original scip rows */
100  SCIP_Real fixingrate;
101 
102  int nrows;
103  int nvars;
104  int nbinvars;
105  int nintvars;
106  int i;
107  int fixingcounter;
108 
109  /* get required data of the original problem */
110  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
111  bestsol = SCIPgetBestSol(scip);
112  assert(bestsol != NULL);
113 
114  fixingcounter = 0;
115 
116  /* change bounds of variables of the subproblem */
117  for( i = 0; i < nbinvars + nintvars; i++ )
118  {
119  SCIP_Real lpsolval;
120  SCIP_Real solval;
121 
122  /* get the current LP solution and the incumbent solution for each variable */
123  lpsolval = SCIPvarGetLPSol(vars[i]);
124  solval = SCIPgetSolVal(scip, bestsol, vars[i]);
125 
126  /* iff both solutions are equal, variable is fixed to that value in the subproblem, otherwise it is just copied */
127  if( SCIPisFeasEQ(scip, lpsolval, solval) )
128  {
129  /* perform the bound change */
130  SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], solval) );
131  SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], solval) );
132  fixingcounter++;
133  }
134  }
135 
136  fixingrate = 0.0;
137 
138  /* abort, if all variables were fixed */
139  if( fixingcounter == nbinvars + nintvars )
140  {
141  *success = FALSE;
142  return SCIP_OKAY;
143  }
144  else
145  fixingrate = (SCIP_Real)fixingcounter / (SCIP_Real)(MAX(nbinvars + nintvars, 1));
146 
147  /* abort, if the amount of fixed variables is insufficient */
148  if( fixingrate < minfixingrate )
149  {
150  *success = FALSE;
151  return SCIP_OKAY;
152  }
153 
154  if( uselprows )
155  {
156  /* get the rows and their number */
157  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
158 
159  /* copy all rows to linear constraints */
160  for( i = 0; i < nrows; i++ )
161  {
162  SCIP_CONS* cons;
163  SCIP_VAR** consvars;
164  SCIP_COL** cols;
165  SCIP_Real constant;
166  SCIP_Real lhs;
167  SCIP_Real rhs;
168  SCIP_Real* vals;
169  int nnonz;
170  int j;
171 
172  /* ignore rows that are only locally valid */
173  if( SCIProwIsLocal(rows[i]) )
174  continue;
175 
176  /* get the row's data */
177  constant = SCIProwGetConstant(rows[i]);
178  lhs = SCIProwGetLhs(rows[i]) - constant;
179  rhs = SCIProwGetRhs(rows[i]) - constant;
180  vals = SCIProwGetVals(rows[i]);
181  nnonz = SCIProwGetNNonz(rows[i]);
182  cols = SCIProwGetCols(rows[i]);
183 
184  assert( lhs <= rhs );
185 
186  /* allocate memory array to be filled with the corresponding subproblem variables */
187  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nnonz) );
188  for( j = 0; j < nnonz; j++ )
189  consvars[j] = subvars[SCIPvarGetProbindex(SCIPcolGetVar(cols[j]))];
190 
191  /* create a new linear constraint and add it to the subproblem */
192  SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, SCIProwGetName(rows[i]), nnonz, consvars, vals, lhs, rhs,
193  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
194  SCIP_CALL( SCIPaddCons(subscip, cons) );
195  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
196 
197  /* free temporary memory */
198  SCIPfreeBufferArray(scip, &consvars);
199  }
200  }
201 
202  *success = TRUE;
203  return SCIP_OKAY;
204 }
205 
206 
207 /** creates a new solution for the original problem by copying the solution of the subproblem */
208 static
209 SCIP_RETCODE createNewSol(
210  SCIP* scip, /**< original SCIP data structure */
211  SCIP* subscip, /**< SCIP structure of the subproblem */
212  SCIP_VAR** subvars, /**< the variables of the subproblem */
213  SCIP_HEUR* heur, /**< RINS heuristic structure */
214  SCIP_SOL* subsol, /**< solution of the subproblem */
215  SCIP_Bool* success /**< used to store whether new solution was found or not */
216 )
217 {
218  SCIP_VAR** vars; /* the original problem's variables */
219  int nvars;
220  SCIP_Real* subsolvals; /* solution values of the subproblem */
221  SCIP_SOL* newsol; /* solution to be created for the original problem */
222 
223  assert( scip != NULL );
224  assert( subscip != NULL );
225  assert( subvars != NULL );
226  assert( subsol != NULL );
227 
228  /* get variables' data */
229  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
230  /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
231  * since constraint copying may have required the copy of variables that are fixed in the main SCIP
232  */
233  assert(nvars <= SCIPgetNOrigVars(subscip));
234 
235  SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
236 
237  /* copy the solution */
238  SCIP_CALL( SCIPgetSolVals(subscip, subsol, nvars, subvars, subsolvals) );
239 
240  /* create new solution for the original problem */
241  SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
242  SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
243 
244  /* try to add new solution to scip and free it immediately */
245  SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, TRUE, TRUE, TRUE, success) );
246 
247  SCIPfreeBufferArray(scip, &subsolvals);
248 
249  return SCIP_OKAY;
250 }
251 
252 /* ---------------- Callback methods of event handler ---------------- */
253 
254 /* exec the event handler
255  *
256  * we interrupt the solution process
257  */
258 static
259 SCIP_DECL_EVENTEXEC(eventExecRins)
260 {
261  SCIP_HEURDATA* heurdata;
262 
263  assert(eventhdlr != NULL);
264  assert(eventdata != NULL);
265  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
266  assert(event != NULL);
267  assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_LPSOLVED);
268 
269  heurdata = (SCIP_HEURDATA*)eventdata;
270  assert(heurdata != NULL);
271 
272  /* interrupt solution process of sub-SCIP */
273  if( SCIPgetNLPs(scip) > heurdata->lplimfac * heurdata->nodelimit )
274  {
275  SCIPdebugMessage("interrupt after %"SCIP_LONGINT_FORMAT" LPs\n",SCIPgetNLPs(scip));
276  SCIP_CALL( SCIPinterruptSolve(scip) );
277  }
278 
279  return SCIP_OKAY;
280 }
281 
282 
283 /*
284  * Callback methods of primal heuristic
285  */
286 
287 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
288 static
289 SCIP_DECL_HEURCOPY(heurCopyRins)
290 { /*lint --e{715}*/
291  assert(scip != NULL);
292  assert(heur != NULL);
293  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
294 
295  /* call inclusion method of primal heuristic */
296  SCIP_CALL( SCIPincludeHeurRins(scip) );
297 
298  return SCIP_OKAY;
299 }
300 
301 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
302 static
303 SCIP_DECL_HEURFREE(heurFreeRins)
304 { /*lint --e{715}*/
305  SCIP_HEURDATA* heurdata;
306 
307  assert( heur != NULL );
308  assert( scip != NULL );
309 
310  /* get heuristic data */
311  heurdata = SCIPheurGetData(heur);
312  assert( heurdata != NULL );
313 
314  /* free heuristic data */
315  SCIPfreeMemory(scip, &heurdata);
316  SCIPheurSetData(heur, NULL);
317 
318  return SCIP_OKAY;
319 }
320 
321 
322 /** initialization method of primal heuristic (called after problem was transformed) */
323 static
324 SCIP_DECL_HEURINIT(heurInitRins)
325 { /*lint --e{715}*/
326  SCIP_HEURDATA* heurdata;
327 
328  assert( heur != NULL );
329  assert( scip != NULL );
330 
331  /* get heuristic's data */
332  heurdata = SCIPheurGetData(heur);
333  assert( heurdata != NULL );
334 
335  /* initialize data */
336  heurdata->usednodes = 0;
337 
338  return SCIP_OKAY;
339 }
340 
341 
342 /** execution method of primal heuristic */
343 static
344 SCIP_DECL_HEUREXEC(heurExecRins)
345 { /*lint --e{715}*/
346  SCIP_Longint nnodes;
347 
348  SCIP_HEURDATA* heurdata; /* heuristic's data */
349  SCIP* subscip; /* the subproblem created by RINS */
350  SCIP_VAR** vars; /* original problem's variables */
351  SCIP_VAR** subvars; /* subproblem's variables */
352  SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
353  SCIP_EVENTHDLR* eventhdlr; /* event handler for LP events */
354 
355  SCIP_Real timelimit; /* timelimit for the subproblem */
356  SCIP_Real memorylimit;
357  SCIP_Real cutoff; /* objective cutoff for the subproblem */
358  SCIP_Real upperbound;
359 
360  int nvars;
361  int nbinvars;
362  int nintvars;
363  int i;
364 
365  SCIP_Bool success;
366  SCIP_RETCODE retcode;
367 
368  assert( heur != NULL );
369  assert( scip != NULL );
370  assert( result != NULL );
371  assert( SCIPhasCurrentNodeLP(scip) );
372 
373  *result = SCIP_DELAYED;
374 
375  /* do not call heuristic of node was already detected to be infeasible */
376  if( nodeinfeasible )
377  return SCIP_OKAY;
378 
379  /* get heuristic's data */
380  heurdata = SCIPheurGetData(heur);
381  assert( heurdata != NULL );
382 
383  /* only call heuristic, if an optimal LP solution and a feasible solution are at hand */
384  if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL || SCIPgetNSols(scip) <= 0 )
385  return SCIP_OKAY;
386 
387  /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
388  if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) )
389  return SCIP_OKAY;
390 
391  /* only call heuristic, if the best solution comes from transformed problem */
392  assert( SCIPgetBestSol(scip) != NULL );
393  if( SCIPsolIsOriginal(SCIPgetBestSol(scip)) )
394  return SCIP_OKAY;
395 
396  /* only call heuristic, if enough nodes were processed since last incumbent */
397  if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip,SCIPgetBestSol(scip)) < heurdata->nwaitingnodes)
398  return SCIP_OKAY;
399 
400  *result = SCIP_DIDNOTRUN;
401 
402  /* calculate the maximal number of branching nodes until heuristic is aborted */
403  nnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
404 
405  /* reward RINS if it succeeded often */
406  nnodes = (SCIP_Longint)(nnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
407  nnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-MIP as 100 nodes */
408  nnodes += heurdata->nodesofs;
409 
410  /* determine the node limit for the current process */
411  nnodes -= heurdata->usednodes;
412  nnodes = MIN(nnodes, heurdata->maxnodes);
413 
414  /* check whether we have enough nodes left to call subproblem solving */
415  if( nnodes < heurdata->minnodes )
416  return SCIP_OKAY;
417 
418  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
419 
420  /* check whether discrete variables are available */
421  if( nbinvars == 0 && nintvars == 0 )
422  return SCIP_OKAY;
423 
424  if( SCIPisStopped(scip) )
425  return SCIP_OKAY;
426 
427  *result = SCIP_DIDNOTFIND;
428 
429  /* initializing the subproblem */
430  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
431  SCIP_CALL( SCIPcreate(&subscip) );
432 
433  /* create the variable mapping hash map */
434  SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), SCIPcalcHashtableSize(5 * nvars)) );
435 
436  eventhdlr = NULL;
437 
438  if( heurdata->uselprows )
439  {
440  char probname[SCIP_MAXSTRLEN];
441 
442  /* copy all plugins */
443  SCIP_CALL( SCIPincludeDefaultPlugins(subscip) );
444 
445  /* get name of the original problem and add the string "_rinssub" */
446  (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_rinssub", SCIPgetProbName(scip));
447 
448  /* do not abort subproblem on CTRL-C */
449  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
450 
451  /* create the subproblem */
452  SCIP_CALL( SCIPcreateProb(subscip, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
453 
454  /* copy all variables */
455  SCIP_CALL( SCIPcopyVars(scip, subscip, varmapfw, NULL, TRUE) );
456  }
457  else
458  {
459  SCIP_Bool valid;
460  valid = FALSE;
461 
462  SCIP_CALL( SCIPcopy(scip, subscip, varmapfw, NULL, "rins", TRUE, FALSE, TRUE, &valid) );
463 
464  if( heurdata->copycuts )
465  {
466  /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
467  SCIP_CALL( SCIPcopyCuts(scip, subscip, varmapfw, NULL, TRUE, NULL) );
468  }
469 
470  SCIPdebugMessage("Copying the SCIP instance was %s complete.\n", valid ? "" : "not ");
471 
472  /* create event handler for LP events */
473  SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecRins, NULL) );
474  if( eventhdlr == NULL )
475  {
476  SCIPerrorMessage("event handler for "HEUR_NAME" heuristic not found.\n");
477  return SCIP_PLUGINNOTFOUND;
478  }
479  }
480 
481  for( i = 0; i < nvars; i++ )
482  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
483 
484  /* free hash map */
485  SCIPhashmapFree(&varmapfw);
486 
487  success = FALSE;
488 
489  /* create a new problem, which fixes variables with same value in bestsol and LP relaxation */
490  SCIP_CALL( createSubproblem(scip, subscip, subvars, heurdata->minfixingrate, heurdata->uselprows, &success) );
491 
492  if( !success )
493  {
494  *result = SCIP_DIDNOTRUN;
495  goto TERMINATE;
496  }
497 
498  /* disable output to console */
499  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
500 
501 #ifdef SCIP_DEBUG
502  /* for debugging RINS, enable MIP output */
503  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
504  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
505 #endif
506 
507  /* check whether there is enough time and memory left */
508  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
509  if( !SCIPisInfinity(scip, timelimit) )
510  timelimit -= SCIPgetSolvingTime(scip);
511  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
512 
513  /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
514  if( !SCIPisInfinity(scip, memorylimit) )
515  {
516  memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
517  memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
518  }
519 
520  /* abort if no time is left or not enough memory to create a copy of SCIP, including external memory usage */
521  if( timelimit <= 0.0 || memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 )
522  goto TERMINATE;
523 
524  /* set limits for the subproblem */
525  heurdata->nodelimit = nnodes;
526  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nnodes) );
527  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", MAX(10, nnodes/10)) );
528  SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", 3) );
529  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
530  SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
531 
532  /* forbid recursive call of heuristics and separators solving subMIPs */
533  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
534 
535  /* disable cutting plane separation */
536  SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
537 
538  /* disable expensive presolving */
539  SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
540 
541  /* use best estimate node selection */
542  if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
543  {
544  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
545  }
546 
547  /* use inference branching */
548  if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
549  {
550  SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
551  }
552 
553  /* disable conflict analysis */
554  if( !SCIPisParamFixed(subscip, "conflict/useprop") )
555  {
556  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/useprop", FALSE) );
557  }
558  if( !SCIPisParamFixed(subscip, "conflict/useinflp") )
559  {
560  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/useinflp", FALSE) );
561  }
562  if( !SCIPisParamFixed(subscip, "conflict/useboundlp") )
563  {
564  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/useboundlp", FALSE) );
565  }
566  if( !SCIPisParamFixed(subscip, "conflict/usesb") )
567  {
568  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/usesb", FALSE) );
569  }
570  if( !SCIPisParamFixed(subscip, "conflict/usepseudo") )
571  {
572  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/usepseudo", FALSE) );
573  }
574 
575  /* employ a limit on the number of enforcement rounds in the quadratic constraint handler; this fixes the issue that
576  * sometimes the quadratic constraint handler needs hundreds or thousands of enforcement rounds to determine the
577  * feasibility status of a single node without fractional branching candidates by separation (namely for uflquad
578  * instances); however, the solution status of the sub-SCIP might get corrupted by this; hence no deductions shall be
579  * made for the original SCIP
580  */
581  if( SCIPfindConshdlr(subscip, "quadratic") != NULL && !SCIPisParamFixed(subscip, "constraints/quadratic/enfolplimit") )
582  {
583  SCIP_CALL( SCIPsetIntParam(subscip, "constraints/quadratic/enfolplimit", 500) );
584  }
585 
586  /* add an objective cutoff */
587  cutoff = SCIPinfinity(scip);
588  assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
589 
590  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
591  if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(scip)) )
592  {
593  cutoff = (1-heurdata->minimprove)*SCIPgetUpperbound(scip) + heurdata->minimprove*SCIPgetLowerbound(scip);
594  }
595  else
596  {
597  if( SCIPgetUpperbound ( scip ) >= 0 )
598  cutoff = ( 1 - heurdata->minimprove ) * SCIPgetUpperbound ( scip );
599  else
600  cutoff = ( 1 + heurdata->minimprove ) * SCIPgetUpperbound ( scip );
601  }
602  cutoff = MIN(upperbound, cutoff );
603  SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) );
604 
605  /* catch LP events of sub-SCIP */
606  if( !heurdata->uselprows )
607  {
608  assert(eventhdlr != NULL);
609 
610  SCIP_CALL( SCIPtransformProb(subscip) );
611  SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
612  }
613 
614  /* solve the subproblem */
615  retcode = SCIPsolve(subscip);
616 
617  /* drop LP events of sub-SCIP */
618  if( !heurdata->uselprows )
619  {
620  assert(eventhdlr != NULL);
621 
622  SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
623  }
624 
625  /* Errors in solving the subproblem should not kill the overall solving process
626  * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
627  */
628  if( retcode != SCIP_OKAY )
629  {
630 #ifndef NDEBUG
631  SCIP_CALL( retcode );
632 #endif
633  SCIPwarningMessage(scip, "Error while solving subproblem in RINS heuristic; sub-SCIP terminated with code <%d>\n",retcode);
634  }
635 
636  /* print solving statistics of subproblem if we are in SCIP's debug mode */
637  SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) );
638 
639  heurdata->usednodes += SCIPgetNNodes(subscip);
640 
641  /* check, whether a solution was found */
642  if( SCIPgetNSols(subscip) > 0 )
643  {
644  SCIP_SOL** subsols;
645  int nsubsols;
646 
647  /* check, whether a solution was found;
648  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
649  */
650  nsubsols = SCIPgetNSols(subscip);
651  subsols = SCIPgetSols(subscip);
652  success = FALSE;
653  for( i = 0; i < nsubsols && !success; ++i )
654  {
655  SCIP_CALL( createNewSol(scip, subscip, subvars, heur, subsols[i], &success) );
656  }
657  if( success )
658  *result = SCIP_FOUNDSOL;
659  }
660 
661  TERMINATE:
662  /* free subproblem */
663  SCIPfreeBufferArray(scip, &subvars);
664  SCIP_CALL( SCIPfree(&subscip) );
665 
666  return SCIP_OKAY;
667 }
668 
669 /*
670  * primal heuristic specific interface methods
671  */
672 
673 /** creates the RINS primal heuristic and includes it in SCIP */
674 SCIP_RETCODE SCIPincludeHeurRins(
675  SCIP* scip /**< SCIP data structure */
676  )
677 {
678  SCIP_HEURDATA* heurdata;
679  SCIP_HEUR* heur;
680 
681  /* create Rins primal heuristic data */
682  SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
683 
684  /* include primal heuristic */
685  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
686  HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
687  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecRins, heurdata) );
688 
689  assert(heur != NULL);
690 
691  /* set non-NULL pointers to callback methods */
692  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyRins) );
693  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeRins) );
694  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitRins) );
695 
696  /* add RINS primal heuristic parameters */
697  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/nodesofs",
698  "number of nodes added to the contingent of the total nodes",
699  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0, INT_MAX, NULL, NULL) );
700 
701  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/maxnodes",
702  "maximum number of nodes to regard in the subproblem",
703  &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0, INT_MAX, NULL, NULL) );
704 
705  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/minnodes",
706  "minimum number of nodes required to start the subproblem",
707  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0, INT_MAX, NULL, NULL) );
708 
709  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/nodesquot",
710  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
711  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
712 
713  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/nwaitingnodes",
714  "number of nodes without incumbent change that heuristic should wait",
715  &heurdata->nwaitingnodes, TRUE, DEFAULT_NWAITINGNODES, 0, INT_MAX, NULL, NULL) );
716 
717  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/minimprove",
718  "factor by which "HEUR_NAME" should at least improve the incumbent",
719  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
720 
721  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/minfixingrate",
722  "minimum percentage of integer variables that have to be fixed",
723  &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) );
724 
725  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/lplimfac",
726  "factor by which the limit on the number of LP depends on the node limit",
727  &heurdata->lplimfac, TRUE, DEFAULT_LPLIMFAC, 1.0, SCIP_REAL_MAX, NULL, NULL) );
728 
729  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/uselprows",
730  "should subproblem be created out of the rows in the LP rows?",
731  &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
732 
733  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/copycuts",
734  "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
735  &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
736 
737  return SCIP_OKAY;
738 }
739