Scippy

SCIP

Solving Constraint Integer Programs

heur_rens.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_rens.c
17  * @brief LNS heuristic that finds the optimal rounding to a given point
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 <stdio.h>
26 #include "scip/scip.h"
27 #include "scip/heur_rens.h"
28 #include "scip/scipdefplugins.h" /* needed for the secondary SCIP instance */
29 #include "scip/cons_linear.h" /* needed if the LP relaxation gets copied into linear constraints */
30 #include "scip/pub_misc.h"
31 
32 /* default values for standard parameters that every primal heuristic has in SCIP */
33 #define HEUR_NAME "rens"
34 #define HEUR_DESC "LNS exploring fractional neighborhood of relaxation's optimum"
35 #define HEUR_DISPCHAR 'E'
36 #define HEUR_PRIORITY -1100000
37 #define HEUR_FREQ 0
38 #define HEUR_FREQOFS 0
39 #define HEUR_MAXDEPTH -1
40 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE
41 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
42 
43 /* default values for RENS-specific plugins */
44 #define DEFAULT_BINARYBOUNDS TRUE /* should general integers get binary bounds [floor(.),ceil(.)] ? */
45 #define DEFAULT_MAXNODES 5000LL /* maximum number of nodes to regard in the subproblem */
46 #define DEFAULT_MINFIXINGRATE 0.5 /* minimum percentage of integer variables that have to be fixed */
47 #define DEFAULT_MINIMPROVE 0.01 /* factor by which RENS should at least improve the incumbent */
48 #define DEFAULT_MINNODES 50LL /* minimum number of nodes to regard in the subproblem */
49 #define DEFAULT_NODESOFS 500LL /* number of nodes added to the contingent of the total nodes */
50 #define DEFAULT_NODESQUOT 0.1 /* subproblem nodes in relation to nodes of the original problem */
51 #define DEFAULT_LPLIMFAC 2.0 /* factor by which the limit on the number of LP depends on the node limit */
52 #define DEFAULT_STARTSOL 'l' /* solution that is used for fixing values */
53 #define STARTSOL_CHOICES "nl" /* possible values for startsol ('l'p relaxation, 'n'lp relaxation) */
54 #define DEFAULT_USELPROWS FALSE /* should subproblem be created out of the rows in the LP rows,
55  * otherwise, the copy constructors of the constraints handlers are used */
56 #define DEFAULT_COPYCUTS TRUE /* if DEFAULT_USELPROWS is FALSE, then should all active cuts from the cutpool
57  * of the original scip be copied to constraints of the subscip
58  */
59 #define DEFAULT_EXTRATIME FALSE /* should the RENS sub-CIP get its own full time limit? This is only
60  * implemented for testing and not recommended to be used!
61  */
62 #define DEFAULT_ADDALLSOLS FALSE /* should all subproblem solutions be added to the original SCIP? */
63 
64 #define DEFAULT_FULLSCALE FALSE /* should the RENS sub-CIP be solved with full-scale SCIP settings, including
65  * techniques that merely work on the dual bound, e.g., cuts? This is only
66  * implemented for testing and not recommended to be used!
67  */
68 
69 /* event handler properties */
70 #define EVENTHDLR_NAME "Rens"
71 #define EVENTHDLR_DESC "LP event handler for "HEUR_NAME" heuristic"
72 
73 /*
74  * Data structures
75  */
76 
77 /** primal heuristic data */
78 struct SCIP_HeurData
79 {
80  SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
81  SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
82  SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
83  SCIP_Longint usednodes; /**< nodes already used by RENS in earlier calls */
84  SCIP_Real minfixingrate; /**< minimum percentage of integer variables that have to be fixed */
85  SCIP_Real minimprove; /**< factor by which RENS should at least improve the incumbent */
86  SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
87  SCIP_Real nodelimit; /**< the nodelimit employed in the current sub-SCIP, for the event handler*/
88  SCIP_Real lplimfac; /**< factor by which the limit on the number of LP depends on the node limit */
89  char startsol; /**< solution used for fixing values ('l'p relaxation, 'n'lp relaxation) */
90  SCIP_Bool binarybounds; /**< should general integers get binary bounds [floor(.),ceil(.)] ? */
91  SCIP_Bool uselprows; /**< should subproblem be created out of the rows in the LP rows? */
92  SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied
93  * to constraints in subproblem? */
94  SCIP_Bool extratime; /**< should the RENS sub-CIP get its own full time limit? This is only
95  * implemented for testing and not recommended to be used! */
96  SCIP_Bool addallsols; /**< should all subproblem solutions be added to the original SCIP? */
97  SCIP_Bool fullscale; /**< should the RENS sub-CIP be solved with full-scale SCIP settings,
98  * including techniques that merely work on the dual bound, e.g., cuts?
99  * This is only implemented for testing and not recommended to be used! */
100 };
101 
102 
103 /*
104  * Local methods
105  */
106 
107 /** compute the number of initial fixings and check whether the fixing rate exceeds the minimum fixing rate */
108 static
109 SCIP_RETCODE computeFixingrate(
110  SCIP* scip, /**< SCIP data structure */
111  SCIP_Real minfixingrate, /**< percentage of integer variables that have to be fixed */
112  char* startsol, /**< pointer to solution used for fixing values ('l'p relaxation, 'n'lp relaxation) */
113  SCIP_Real* fixingrate, /**< percentage of integers that get actually fixed */
114  SCIP_Bool* success /**< pointer to store whether minimum fixingrate is exceeded */
115  )
116 {
117  SCIP_VAR** vars;
118  int fixingcounter;
119  int nintvars;
120  int nbinvars;
121  int i;
122 
123  *fixingrate = 1.0;
124  *success = FALSE;
125 
126  fixingcounter = 0;
127 
128  /* if there is no NLP relaxation available (e.g., because the presolved problem is linear), use LP relaxation */
129  if( !SCIPisNLPConstructed(scip) )
130  {
131  SCIPdebugMessage("no NLP present, use LP relaxation instead\n");
132  (*startsol) = 'l';
133  }
134 
135  /* get required variable data */
136  SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
137 
138  /* try to solve NLP relaxation */
139  if( (*startsol) == 'n' )
140  {
141  SCIP_NLPSOLSTAT stat;
142  SCIPdebug( int nlpverblevel; )
143 
144  /* only call this function if NLP relaxation is available */
145  assert(SCIPisNLPConstructed(scip));
146 
147  /* activate NLP solver output if we are in SCIP's debug mode */
148  SCIPdebug( SCIP_CALL( SCIPgetNLPIntPar(scip, SCIP_NLPPAR_VERBLEVEL, &nlpverblevel) ) );
149  SCIPdebug( SCIP_CALL( SCIPsetNLPIntPar(scip, SCIP_NLPPAR_VERBLEVEL, MAX(1,nlpverblevel)) ) );
150 
151  SCIPdebugMessage("try to solve NLP relaxation to obtain fixing values\n");
152 
153  /* set starting point to LP solution */
154  SCIP_CALL( SCIPsetNLPInitialGuessSol(scip, NULL) );
155 
156  /* solve NLP relaxation */
157  SCIP_CALL( SCIPsolveNLP(scip) );
158 
159  /* get solution status of NLP solver */
160  stat = SCIPgetNLPSolstat(scip);
161  *success = (stat == SCIP_NLPSOLSTAT_GLOBOPT) || (stat == SCIP_NLPSOLSTAT_LOCOPT) || stat == (SCIP_NLPSOLSTAT_FEASIBLE);
162  SCIPdebugMessage("solving NLP relaxation was %s successful (stat=%d)\n", *success ? "" : "not", stat);
163 
164  /* reset NLP verblevel to the value it had before */
165  SCIPdebug( SCIP_CALL( SCIPsetNLPIntPar(scip, SCIP_NLPPAR_VERBLEVEL, nlpverblevel) ) );
166 
167  /* it the NLP was not successfully solved we stop the heuristic right away */
168  if( !(*success) )
169  return SCIP_OKAY;
170 
171  /* count the number of variables with integral solution values in the current NLP solution */
172  for( i = 0; i < nbinvars + nintvars; ++i )
173  {
174  SCIP_Real solval;
175 
176  solval = SCIPvarGetNLPSol(vars[i]);
177 
178  if( SCIPisFeasIntegral(scip, solval) )
179  fixingcounter++;
180  }
181  }
182  else
183  {
184  assert(*startsol == 'l');
185 
186  /* compute the number of variables which have an integral solution value in the LP */
187  fixingcounter = SCIPgetNPseudoBranchCands(scip) - SCIPgetNLPBranchCands(scip);
188  }
189 
190  /* abort, if all integer variables were fixed (which should not happen for MIP),
191  * but frequently happens for MINLPs using an LP relaxation
192  */
193  if( fixingcounter == nbinvars + nintvars )
194  return SCIP_OKAY;
195 
196  *fixingrate = fixingcounter / (SCIP_Real)(MAX(nbinvars + nintvars, 1));
197 
198  /* abort, if the amount of fixed variables is insufficient */
199  if( *fixingrate < minfixingrate )
200  return SCIP_OKAY;
201 
202  *success = TRUE;
203  return SCIP_OKAY;
204 }
205 
206 /** creates a subproblem by fixing a number of variables */
207 static
208 SCIP_RETCODE createSubproblem(
209  SCIP* scip, /**< original SCIP data structure */
210  SCIP* subscip, /**< SCIP data structure for the subproblem */
211  SCIP_VAR** subvars, /**< the variables of the subproblem */
212  char startsol, /**< solution used for fixing values ('l'p relaxation, 'n'lp relaxation) */
213  SCIP_Bool binarybounds, /**< should general integers get binary bounds [floor(.),ceil(.)] ? */
214  SCIP_Bool uselprows /**< should subproblem be created out of the rows in the LP rows? */
215  )
216 {
217  SCIP_VAR** vars; /* original SCIP variables */
218 
219  int nbinvars;
220  int nintvars;
221  int i;
222 
223  assert(scip != NULL);
224  assert(subscip != NULL);
225  assert(subvars != NULL);
226 
227  assert(startsol == 'l' || startsol == 'n');
228 
229  /* get required variable data */
230  SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
231 
232  /* change bounds of variables of the subproblem */
233  for( i = 0; i < nbinvars + nintvars; i++ )
234  {
235  SCIP_Real solval;
236  SCIP_Real lb;
237  SCIP_Real ub;
238 
239  /* get the current LP solution for each variable */
240  if( startsol == 'l')
241  solval = SCIPvarGetLPSol(vars[i]);
242  else
243  solval = SCIPvarGetNLPSol(vars[i]);
244 
245  if( SCIPisFeasIntegral(scip, solval) )
246  {
247  /* fix variables to current LP solution if it is integral,
248  * use exact integral value, if the variable is only integral within numerical tolerances
249  */
250  lb = SCIPfloor(scip, solval+0.5);
251  ub = lb;
252  }
253  else if( binarybounds )
254  {
255  /* if the subproblem should be a binary problem, change the bounds to nearest integers */
256  lb = SCIPfeasFloor(scip,solval);
257  ub = SCIPfeasCeil(scip,solval);
258  }
259  else
260  {
261  /* otherwise just copy bounds */
262  lb = SCIPvarGetLbGlobal(vars[i]);
263  ub = SCIPvarGetUbGlobal(vars[i]);
264  }
265 
266  /* perform the bound change */
267  SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], lb) );
268  SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], ub) );
269  }
270 
271  if( uselprows )
272  {
273  SCIP_ROW** rows; /* original scip rows */
274  int nrows;
275 
276  /* get the rows and their number */
277  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
278 
279  /* copy all rows to linear constraints */
280  for( i = 0; i < nrows; i++ )
281  {
282  SCIP_CONS* cons;
283  SCIP_VAR** consvars;
284  SCIP_COL** cols;
285  SCIP_Real constant;
286  SCIP_Real lhs;
287  SCIP_Real rhs;
288  SCIP_Real* vals;
289  int nnonz;
290  int j;
291 
292  /* ignore rows that are only locally valid */
293  if( SCIProwIsLocal(rows[i]) )
294  continue;
295 
296  /* get the row's data */
297  constant = SCIProwGetConstant(rows[i]);
298  lhs = SCIProwGetLhs(rows[i]) - constant;
299  rhs = SCIProwGetRhs(rows[i]) - constant;
300  vals = SCIProwGetVals(rows[i]);
301  nnonz = SCIProwGetNNonz(rows[i]);
302  cols = SCIProwGetCols(rows[i]);
303 
304  assert(lhs <= rhs);
305 
306  /* allocate memory array to be filled with the corresponding subproblem variables */
307  SCIP_CALL( SCIPallocBufferArray(subscip, &consvars, nnonz) );
308  for( j = 0; j < nnonz; j++ )
309  consvars[j] = subvars[SCIPvarGetProbindex(SCIPcolGetVar(cols[j]))];
310 
311  /* create a new linear constraint and add it to the subproblem */
312  SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, SCIProwGetName(rows[i]), nnonz, consvars, vals, lhs, rhs,
313  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
314  SCIP_CALL( SCIPaddCons(subscip, cons) );
315  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
316 
317  /* free temporary memory */
318  SCIPfreeBufferArray(subscip, &consvars);
319  }
320  }
321 
322  return SCIP_OKAY;
323 }
324 
325 
326 /** creates a new solution for the original problem by copying the solution of the subproblem */
327 static
328 SCIP_RETCODE createNewSol(
329  SCIP* scip, /**< original SCIP data structure */
330  SCIP* subscip, /**< SCIP structure of the subproblem */
331  SCIP_VAR** subvars, /**< the variables of the subproblem */
332  SCIP_HEUR* heur, /**< RENS heuristic structure */
333  SCIP_SOL* subsol, /**< solution of the subproblem */
334  SCIP_Bool* success /**< used to store whether new solution was found or not */
335  )
336 {
337  SCIP_VAR** vars; /* the original problem's variables */
338  int nvars; /* the original problem's number of variables */
339  SCIP_Real* subsolvals; /* solution values of the subproblem */
340  SCIP_SOL* newsol; /* solution to be created for the original problem */
341 
342  assert(scip != NULL);
343  assert(subscip != NULL);
344  assert(subvars != NULL);
345  assert(subsol != NULL);
346 
347  /* get variables' data */
348  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
349 
350  /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
351  * since constraint copying may have required the copy of variables that are fixed in the main SCIP
352  */
353  assert(nvars <= SCIPgetNOrigVars(subscip));
354 
355  SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
356 
357  /* copy the solution */
358  SCIP_CALL( SCIPgetSolVals(subscip, subsol, nvars, subvars, subsolvals) );
359 
360  /* create new solution for the original problem */
361  SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
362  SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
363 
364  /* try to add new solution to scip and free it immediately */
365  SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, TRUE, TRUE, TRUE, success) );
366 
367  SCIPfreeBufferArray(scip, &subsolvals);
368 
369  return SCIP_OKAY;
370 }
371 
372 /* ---------------- Callback methods of event handler ---------------- */
373 
374 /* exec the event handler
375  *
376  * we interrupt the solution process
377  */
378 static
379 SCIP_DECL_EVENTEXEC(eventExecRens)
380 {
381  SCIP_HEURDATA* heurdata;
382 
383  assert(eventhdlr != NULL);
384  assert(eventdata != NULL);
385  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
386  assert(event != NULL);
387  assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_LPSOLVED);
388 
389  heurdata = (SCIP_HEURDATA*)eventdata;
390  assert(heurdata != NULL);
391 
392  /* interrupt solution process of sub-SCIP */
393  if( SCIPgetNLPs(scip) > heurdata->lplimfac * heurdata->nodelimit )
394  {
395  SCIPdebugMessage("interrupt after %"SCIP_LONGINT_FORMAT" LPs\n",SCIPgetNLPs(scip));
396  SCIP_CALL( SCIPinterruptSolve(scip) );
397  }
398 
399  return SCIP_OKAY;
400 }
401 
402 /* ---------------- external methods of RENS heuristic ---------------- */
403 
404 /** main procedure of the RENS heuristic, creates and solves a sub-SCIP */
405 SCIP_RETCODE SCIPapplyRens(
406  SCIP* scip, /**< original SCIP data structure */
407  SCIP_HEUR* heur, /**< heuristic data structure */
408  SCIP_RESULT* result, /**< result data structure */
409  SCIP_Real minfixingrate, /**< minimum percentage of integer variables that have to be fixed */
410  SCIP_Real minimprove, /**< factor by which RENS should at least improve the incumbent */
411  SCIP_Longint maxnodes, /**< maximum number of nodes for the subproblem */
412  SCIP_Longint nstallnodes, /**< number of stalling nodes for the subproblem */
413  char startsol, /**< solution used for fixing values ('l'p relaxation, 'n'lp relaxation) */
414  SCIP_Bool binarybounds, /**< should general integers get binary bounds [floor(.),ceil(.)]? */
415  SCIP_Bool uselprows /**< should subproblem be created out of the rows in the LP rows? */
416  )
417 {
418  SCIP* subscip; /* the subproblem created by RENS */
419  SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
420  SCIP_VAR** vars; /* original problem's variables */
421  SCIP_VAR** subvars; /* subproblem's variables */
422  SCIP_HEURDATA* heurdata; /* heuristic's private data structure */
423  SCIP_EVENTHDLR* eventhdlr; /* event handler for LP events */
424 
425  SCIP_Real cutoff; /* objective cutoff for the subproblem */
426  SCIP_Real timelimit; /* time limit for RENS subproblem */
427  SCIP_Real memorylimit; /* memory limit for RENS subproblem */
428  SCIP_Real allfixingrate; /* percentage of all variables fixed */
429  SCIP_Real intfixingrate; /* percentage of integer variables fixed */
430 
431  int nvars; /* number of original problem's variables */
432  int i;
433 
434  SCIP_Bool success;
435  SCIP_RETCODE retcode;
436 
437  assert(scip != NULL);
438  assert(heur != NULL);
439  assert(result != NULL);
440 
441  assert(maxnodes >= 0);
442  assert(nstallnodes >= 0);
443 
444  assert(0.0 <= minfixingrate && minfixingrate <= 1.0);
445  assert(0.0 <= minimprove && minimprove <= 1.0);
446  assert(startsol == 'l' || startsol == 'n');
447 
448  *result = SCIP_DIDNOTRUN;
449 
450  /* compute the number of initial fixings and check if the fixing rate exceeds the minimum fixing rate */
451  SCIP_CALL( computeFixingrate(scip, minfixingrate, &startsol, &intfixingrate, &success) );
452 
453  if( !success )
454  {
455  SCIPstatisticPrintf("RENS statistic: fixed only %5.2f integer variables --> abort \n", intfixingrate);
456  return SCIP_OKAY;
457  }
458 
459  /* get heuristic data */
460  heurdata = SCIPheurGetData(heur);
461  assert(heurdata != NULL);
462 
463  /* check whether there is enough time and memory left */
464  timelimit = 0.0;
465  memorylimit = 0.0;
466  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
467  if( !SCIPisInfinity(scip, timelimit) && !heurdata->extratime )
468  timelimit -= SCIPgetSolvingTime(scip);
469  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
470 
471  /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
472  if( !SCIPisInfinity(scip, memorylimit) )
473  {
474  memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
475  memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
476  }
477 
478  /* abort if no time is left or not enough memory to create a copy of SCIP, including external memory usage */
479  if( timelimit <= 0.0 || memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 )
480  return SCIP_OKAY;
481 
482  *result = SCIP_DIDNOTFIND;
483 
484  /* get variable data */
485  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
486 
487  /* initialize the subproblem */
488  SCIP_CALL( SCIPcreate(&subscip) );
489 
490  /* create the variable mapping hash map */
491  SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), SCIPcalcHashtableSize(5 * nvars)) );
492  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
493 
494  eventhdlr = NULL;
495 
496  /* different methods to create sub-problem: either copy LP relaxation or the CIP with all constraints */
497  if( uselprows )
498  {
499  char probname[SCIP_MAXSTRLEN];
500 
501  /* copy all plugins */
502  SCIP_CALL( SCIPincludeDefaultPlugins(subscip) );
503 
504  /* get name of the original problem and add the string "_renssub" */
505  (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_renssub", SCIPgetProbName(scip));
506 
507  /* create the subproblem */
508  SCIP_CALL( SCIPcreateProb(subscip, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
509 
510  /* copy all variables */
511  SCIP_CALL( SCIPcopyVars(scip, subscip, varmapfw, NULL, TRUE) );
512  }
513  else
514  {
515  SCIP_Bool valid;
516 
517  valid = FALSE;
518 
519  /* copy complete SCIP instance */
520  SCIP_CALL( SCIPcopy(scip, subscip, varmapfw, NULL, "rens", TRUE, FALSE, TRUE, &valid) );
521 
522  if( heurdata->copycuts )
523  {
524  /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
525  SCIP_CALL( SCIPcopyCuts(scip, subscip, varmapfw, NULL, TRUE, NULL) );
526  }
527 
528  SCIPdebugMessage("Copying the SCIP instance was %s complete.\n", valid ? "" : "not ");
529 
530  /* create event handler for LP events */
531  SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecRens, NULL) );
532  if( eventhdlr == NULL )
533  {
534  SCIPerrorMessage("event handler for "HEUR_NAME" heuristic not found.\n");
535  return SCIP_PLUGINNOTFOUND;
536  }
537  }
538 
539  for( i = 0; i < nvars; i++ )
540  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
541 
542  /* free hash map */
543  SCIPhashmapFree(&varmapfw);
544 
545  /* create a new problem, which fixes variables with same value in bestsol and LP relaxation */
546  SCIP_CALL( createSubproblem(scip, subscip, subvars, startsol, binarybounds, uselprows) );
547  SCIPdebugMessage("RENS subproblem: %d vars, %d cons\n", SCIPgetNVars(subscip), SCIPgetNConss(subscip));
548 
549  /* do not abort subproblem on CTRL-C */
550  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
551 
552  /* disable output to console */
553  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
554 
555  /* set limits for the subproblem */
556  heurdata->nodelimit = maxnodes;
557  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) );
558  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", maxnodes) );
559  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
560  SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
561 
562  /* forbid recursive call of heuristics and separators solving sub-SCIPs */
563  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
564 
565  /* disable expensive techniques that merely work on the dual bound */
566  if( !heurdata->fullscale )
567  {
568  /* disable cutting plane separation */
569  SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
570 
571  /* disable expensive presolving */
572  SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
573 
574  /* use best estimate node selection */
575  if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
576  {
577  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
578  }
579 
580  /* use inference branching */
581  if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
582  {
583  SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
584  }
585 
586  /* disable conflict analysis */
587  if( !SCIPisParamFixed(subscip, "conflict/enable") )
588  {
589  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", FALSE) );
590  }
591 
592  /* employ a limit on the number of enforcement rounds in the quadratic constraint handler; this fixes the issue that
593  * sometimes the quadratic constraint handler needs hundreds or thousands of enforcement rounds to determine the
594  * feasibility status of a single node without fractional branching candidates by separation (namely for uflquad
595  * instances); however, the solution status of the sub-SCIP might get corrupted by this; hence no deductions shall be
596  * made for the original SCIP
597  */
598  if( SCIPfindConshdlr(subscip, "quadratic") != NULL && !SCIPisParamFixed(subscip, "constraints/quadratic/enfolplimit") )
599  {
600  SCIP_CALL( SCIPsetIntParam(subscip, "constraints/quadratic/enfolplimit", 500) );
601  }
602  }
603 
604 #ifdef SCIP_DEBUG
605  /* for debugging RENS, enable MIP output */
606  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
607  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
608 #endif
609 
610  /* if there is already a solution, add an objective cutoff */
611  if( SCIPgetNSols(scip) > 0 )
612  {
613  SCIP_Real upperbound;
614  cutoff = SCIPinfinity(scip);
615  assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
616 
617  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
618 
619  if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(scip)) )
620  {
621  cutoff = (1-minimprove)*SCIPgetUpperbound(scip) + minimprove*SCIPgetLowerbound(scip);
622  }
623  else
624  {
625  if( SCIPgetUpperbound ( scip ) >= 0 )
626  cutoff = ( 1 - minimprove ) * SCIPgetUpperbound ( scip );
627  else
628  cutoff = ( 1 + minimprove ) * SCIPgetUpperbound ( scip );
629  }
630  cutoff = MIN(upperbound, cutoff);
631  SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) );
632  }
633 
634  /* presolve the subproblem */
635  retcode = SCIPpresolve(subscip);
636 
637  /* errors in solving the subproblem should not kill the overall solving process;
638  * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
639  */
640  if( retcode != SCIP_OKAY )
641  {
642 #ifndef NDEBUG
643  SCIP_CALL( retcode );
644 #endif
645  SCIPwarningMessage(scip, "Error while presolving subproblem in RENS heuristic; sub-SCIP terminated with code <%d>\n", retcode);
646 
647  /* free */
648  SCIPfreeBufferArray(scip, &subvars);
649  SCIP_CALL( SCIPfree(&subscip) );
650  return SCIP_OKAY;
651  }
652 
653  SCIPdebugMessage("RENS presolved subproblem: %d vars, %d cons, success=%u\n", SCIPgetNVars(subscip), SCIPgetNConss(subscip), success);
654 
655  allfixingrate = (SCIPgetNOrigVars(subscip) - SCIPgetNVars(subscip)) / (SCIP_Real)SCIPgetNOrigVars(subscip);
656 
657  /* additional variables added in presolving may lead to the subSCIP having more variables than the original */
658  allfixingrate = MAX(allfixingrate, 0.0);
659 
660  /* after presolving, we should have at least reached a certain fixing rate over ALL variables (including continuous)
661  * to ensure that not only the MIP but also the LP relaxation is easy enough
662  */
663  if( allfixingrate >= minfixingrate / 2.0 )
664  {
665  SCIP_SOL** subsols;
666  int nsubsols;
667 
668  /* catch LP events of sub-SCIP */
669  if( !heurdata->uselprows )
670  {
671  assert(eventhdlr != NULL);
672 
673  SCIP_CALL( SCIPtransformProb(subscip) );
674  SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
675  }
676 
677  /* solve the subproblem */
678  SCIPdebugMessage("solving subproblem: nstallnodes=%"SCIP_LONGINT_FORMAT", maxnodes=%"SCIP_LONGINT_FORMAT"\n", nstallnodes, maxnodes);
679  retcode = SCIPsolve(subscip);
680 
681  /* drop LP events of sub-SCIP */
682  if( !heurdata->uselprows )
683  {
684  assert(eventhdlr != NULL);
685 
686  SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
687  }
688 
689  /* errors in solving the subproblem should not kill the overall solving process;
690  * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
691  */
692  if( retcode != SCIP_OKAY )
693  {
694 #ifndef NDEBUG
695  SCIP_CALL( retcode );
696 #endif
697  SCIPwarningMessage(scip, "Error while solving subproblem in RENS heuristic; sub-SCIP terminated with code <%d>\n", retcode);
698  }
699 
700  /* print solving statistics of subproblem if we are in SCIP's debug mode */
701  SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) );
702 
703  /* check, whether a solution was found;
704  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
705  */
706  nsubsols = SCIPgetNSols(subscip);
707  subsols = SCIPgetSols(subscip);
708  success = FALSE;
709  for( i = 0; i < nsubsols && (!success || heurdata->addallsols); ++i )
710  {
711  SCIP_CALL( createNewSol(scip, subscip, subvars, heur, subsols[i], &success) );
712  if( success )
713  *result = SCIP_FOUNDSOL;
714  }
715 
716  SCIPstatisticPrintf("RENS statistic: fixed %6.3f integer variables, %6.3f all variables, needed %6.1f seconds, %"SCIP_LONGINT_FORMAT" nodes, solution %10.4f found at node %"SCIP_LONGINT_FORMAT"\n",
717  intfixingrate, allfixingrate, SCIPgetSolvingTime(subscip), SCIPgetNNodes(subscip), success ? SCIPgetPrimalbound(scip) : SCIPinfinity(scip),
718  nsubsols > 0 ? SCIPsolGetNodenum(SCIPgetBestSol(subscip)) : -1 );
719  }
720  else
721  {
722  SCIPstatisticPrintf("RENS statistic: fixed only %6.3f integer variables, %6.3f all variables --> abort \n", intfixingrate, allfixingrate);
723  }
724 
725  /* free subproblem */
726  SCIPfreeBufferArray(scip, &subvars);
727  SCIP_CALL( SCIPfree(&subscip) );
728 
729  return SCIP_OKAY;
730 }
731 
732 
733 /*
734  * Callback methods of primal heuristic
735  */
736 
737 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
738 static
739 SCIP_DECL_HEURCOPY(heurCopyRens)
740 { /*lint --e{715}*/
741  assert(scip != NULL);
742  assert(heur != NULL);
743  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
744 
745  /* call inclusion method of primal heuristic */
746  SCIP_CALL( SCIPincludeHeurRens(scip) );
747 
748  return SCIP_OKAY;
749 }
750 
751 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
752 static
753 SCIP_DECL_HEURFREE(heurFreeRens)
754 { /*lint --e{715}*/
755  SCIP_HEURDATA* heurdata;
756 
757  assert( heur != NULL );
758  assert( scip != NULL );
759 
760  /* get heuristic data */
761  heurdata = SCIPheurGetData(heur);
762  assert( heurdata != NULL );
763 
764  /* free heuristic data */
765  SCIPfreeMemory(scip, &heurdata);
766  SCIPheurSetData(heur, NULL);
767 
768  return SCIP_OKAY;
769 }
770 
771 /** initialization method of primal heuristic (called after problem was transformed) */
772 static
773 SCIP_DECL_HEURINIT(heurInitRens)
774 { /*lint --e{715}*/
775  SCIP_HEURDATA* heurdata;
776 
777  assert( heur != NULL );
778  assert( scip != NULL );
779 
780  /* get heuristic data */
781  heurdata = SCIPheurGetData(heur);
782  assert( heurdata != NULL );
783 
784  /* initialize data */
785  heurdata->usednodes = 0;
786 
787  return SCIP_OKAY;
788 }
789 
790 
791 /** execution method of primal heuristic */
792 static
793 SCIP_DECL_HEUREXEC(heurExecRens)
794 { /*lint --e{715}*/
795 
796  SCIP_HEURDATA* heurdata; /* heuristic's data */
797  SCIP_Longint nstallnodes; /* number of stalling nodes for the subproblem */
798 
799  assert( heur != NULL );
800  assert( scip != NULL );
801  assert( result != NULL );
802  assert( SCIPhasCurrentNodeLP(scip) );
803 
804  *result = SCIP_DELAYED;
805 
806  /* do not call heuristic of node was already detected to be infeasible */
807  if( nodeinfeasible )
808  return SCIP_OKAY;
809 
810  /* get heuristic data */
811  heurdata = SCIPheurGetData(heur);
812  assert( heurdata != NULL );
813 
814  /* only call heuristic, if an optimal LP solution is at hand */
815  if( heurdata->startsol == 'l' && SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
816  return SCIP_OKAY;
817 
818  /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
819  if( heurdata->startsol == 'l' && SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) )
820  return SCIP_OKAY;
821 
822  /* only continue with some fractional variables */
823  if( heurdata->startsol == 'l' && SCIPgetNLPBranchCands(scip) == 0 )
824  return SCIP_OKAY;
825 
826  /* do not proceed, when we should use the NLP relaxation, but there is no NLP solver included in SCIP */
827  if( heurdata->startsol == 'n' && SCIPgetNNlpis(scip) == 0 )
828  return SCIP_OKAY;
829 
830  *result = SCIP_DIDNOTRUN;
831 
832  /* calculate the maximal number of branching nodes until heuristic is aborted */
833  nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
834 
835  /* reward RENS if it succeeded often */
836  nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
837  nstallnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-SCIP as 100 nodes */
838  nstallnodes += heurdata->nodesofs;
839 
840  /* determine the node limit for the current process */
841  nstallnodes -= heurdata->usednodes;
842  nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
843 
844  /* check whether we have enough nodes left to call subproblem solving */
845  if( nstallnodes < heurdata->minnodes )
846  {
847  SCIPdebugMessage("skipping RENS: nstallnodes=%"SCIP_LONGINT_FORMAT", minnodes=%"SCIP_LONGINT_FORMAT"\n", nstallnodes, heurdata->minnodes);
848  return SCIP_OKAY;
849  }
850 
851  if( SCIPisStopped(scip) && !heurdata->extratime )
852  return SCIP_OKAY;
853 
854  SCIP_CALL( SCIPapplyRens(scip, heur, result, heurdata->minfixingrate, heurdata->minimprove,
855  heurdata->maxnodes, nstallnodes, heurdata->startsol, heurdata->binarybounds, heurdata->uselprows) );
856 
857  return SCIP_OKAY;
858 }
859 
860 
861 /*
862  * primal heuristic specific interface methods
863  */
864 
865 /** creates the rens primal heuristic and includes it in SCIP */
866 SCIP_RETCODE SCIPincludeHeurRens(
867  SCIP* scip /**< SCIP data structure */
868  )
869 {
870  SCIP_HEURDATA* heurdata;
871  SCIP_HEUR* heur;
872 
873  /* create Rens primal heuristic data */
874  SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
875 
876  /* include primal heuristic */
877  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
878  HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
879  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecRens, heurdata) );
880 
881  assert(heur != NULL);
882 
883  /* set non-NULL pointers to callback methods */
884  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyRens) );
885  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeRens) );
886  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitRens) );
887 
888  /* add rens primal heuristic parameters */
889 
890  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/minfixingrate",
891  "minimum percentage of integer variables that have to be fixable",
892  &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) );
893 
894  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/"HEUR_NAME"/maxnodes",
895  "maximum number of nodes to regard in the subproblem",
896  &heurdata->maxnodes, TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
897 
898  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/"HEUR_NAME"/nodesofs",
899  "number of nodes added to the contingent of the total nodes",
900  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
901 
902  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/"HEUR_NAME"/minnodes",
903  "minimum number of nodes required to start the subproblem",
904  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
905 
906  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/nodesquot",
907  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
908  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
909 
910  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/minimprove",
911  "factor by which RENS should at least improve the incumbent",
912  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
913 
914  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/lplimfac",
915  "factor by which the limit on the number of LP depends on the node limit",
916  &heurdata->lplimfac, TRUE, DEFAULT_LPLIMFAC, 1.0, SCIP_REAL_MAX, NULL, NULL) );
917 
918  SCIP_CALL( SCIPaddCharParam(scip, "heuristics/"HEUR_NAME"/startsol",
919  "solution that is used for fixing values ('l'p relaxation, 'n'lp relaxation)",
920  &heurdata->startsol, FALSE, DEFAULT_STARTSOL, STARTSOL_CHOICES, NULL, NULL) );
921 
922  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/binarybounds",
923  "should general integers get binary bounds [floor(.),ceil(.)] ?",
924  &heurdata->binarybounds, TRUE, DEFAULT_BINARYBOUNDS, NULL, NULL) );
925 
926  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/uselprows",
927  "should subproblem be created out of the rows in the LP rows?",
928  &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
929 
930  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/copycuts",
931  "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
932  &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
933 
934  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/extratime",
935  "should the RENS sub-CIP get its own full time limit? This is only for tesing and not recommended!",
936  &heurdata->extratime, TRUE, DEFAULT_EXTRATIME, NULL, NULL) );
937 
938  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/addallsols",
939  "should all subproblem solutions be added to the original SCIP?",
940  &heurdata->addallsols, TRUE, DEFAULT_ADDALLSOLS, NULL, NULL) );
941 
942  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/fullscale",
943  "should the RENS sub-CIP be solved with cuts, conflicts, strong branching,... This is only for tesing and not recommended!",
944  &heurdata->fullscale, TRUE, DEFAULT_FULLSCALE, NULL, NULL) );
945 
946  return SCIP_OKAY;
947 }
948