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