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