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