Scippy

SCIP

Solving Constraint Integer Programs

heur_rins.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_rins.c
17  * @brief LNS heuristic that combines the incumbent with the LP optimum
18  * @author Timo Berthold
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <assert.h>
24 #include <string.h>
25 #include "scip/scip.h"
26 #include "scip/scipdefplugins.h"
27 #include "scip/cons_linear.h"
28 #include "scip/heur_rins.h"
29 #include "scip/pub_misc.h"
30 
31 #define HEUR_NAME "rins"
32 #define HEUR_DESC "relaxation induced neighborhood search by Danna, Rothberg, and Le Pape"
33 #define HEUR_DISPCHAR 'N'
34 #define HEUR_PRIORITY -1101000
35 #define HEUR_FREQ 25
36 #define HEUR_FREQOFS 0
37 #define HEUR_MAXDEPTH -1
38 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE
39 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
40 
41 #define DEFAULT_NODESOFS 500 /* number of nodes added to the contingent of the total nodes */
42 #define DEFAULT_MAXNODES 5000 /* maximum number of nodes to regard in the subproblem */
43 #define DEFAULT_MINNODES 50 /* minimum number of nodes to regard in the subproblem */
44 #define DEFAULT_MINIMPROVE 0.01 /* factor by which RINS should at least improve the incumbent */
45 #define DEFAULT_MINFIXINGRATE 0.3 /* minimum percentage of integer variables that have to be fixed */
46 #define DEFAULT_NODESQUOT 0.1 /* subproblem nodes in relation to nodes of the original problem */
47 #define DEFAULT_LPLIMFAC 2.0 /* factor by which the limit on the number of LP depends on the node limit */
48 #define DEFAULT_NWAITINGNODES 200 /* number of nodes without incumbent change that heuristic should wait */
49 #define DEFAULT_USELPROWS FALSE /* should subproblem be created out of the rows in the LP rows,
50  * otherwise, the copy constructors of the constraints handlers are used */
51 #define DEFAULT_COPYCUTS TRUE /* if DEFAULT_USELPROWS is FALSE, then should all active cuts from the cutpool
52  * of the original scip be copied to constraints of the subscip
53  */
54 #define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */
55 
56 /* event handler properties */
57 #define EVENTHDLR_NAME "Rins"
58 #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic"
59 
60 /*
61  * Data structures
62  */
63 
64 /** primal heuristic data */
65 struct SCIP_HeurData
66 {
67  int nodesofs; /**< number of nodes added to the contingent of the total nodes */
68  int maxnodes; /**< maximum number of nodes to regard in the subproblem */
69  int minnodes; /**< minimum number of nodes to regard in the subproblem */
70  SCIP_Real minfixingrate; /**< minimum percentage of integer variables that have to be fixed */
71  int nwaitingnodes; /**< number of nodes without incumbent change that heuristic should wait */
72  SCIP_Real minimprove; /**< factor by which RINS should at least improve the incumbent */
73  SCIP_Real nodelimit; /**< the nodelimit employed in the current sub-SCIP, for the event handler*/
74  SCIP_Real lplimfac; /**< factor by which the limit on the number of LP depends on the node limit */
75  SCIP_Longint usednodes; /**< nodes already used by RINS in earlier calls */
76  SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
77  SCIP_Bool uselprows; /**< should subproblem be created out of the rows in the LP rows? */
78  SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied
79  * to constraints in subproblem?
80  */
81  SCIP_Bool useuct; /**< should uct node selection be used at the beginning of the search? */
82 };
83 
84 /*
85  * Local methods
86  */
87 
88 /** determines variable fixings for RINS
89  *
90  * RINS fixes variables with matching solution values in the current LP and the
91  * incumbent solution
92  */
93 static
95  SCIP* scip, /**< original SCIP data structure */
96  SCIP_VAR** fixedvars, /**< array to store source SCIP variables that should be fixed in the copy */
97  SCIP_Real* fixedvals, /**< array to store fixing values for variables that should be fixed in the copy */
98  int* nfixedvars, /**< pointer to store the number of variables that RINS can fix */
99  int fixedvarssize, /**< size of the buffer arrays to store potential fixings */
100  SCIP_Real minfixingrate, /**< percentage of integer variables that have to be fixed */
101  SCIP_Bool* success /**< pointer to store whether sufficiently many variable fixings were found */
102  )
103 {
104  SCIP_SOL* bestsol; /* incumbent solution of the original problem */
105  SCIP_VAR** vars; /* original scip variables */
106  SCIP_Real fixingrate;
107 
108  int nvars;
109  int nbinvars;
110  int nintvars;
111  int i;
112  int fixingcounter;
113 
114  assert(fixedvals != NULL);
115  assert(fixedvars != NULL);
116  assert(nfixedvars != NULL);
117 
118  /* get required data of the original problem */
119  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
120  bestsol = SCIPgetBestSol(scip);
121  assert(bestsol != NULL);
122 
123  fixingcounter = 0;
124  assert(fixedvarssize >= nbinvars + nintvars);
125 
126  /* determine variables to fix in the subproblem */
127  for( i = 0; i < nbinvars + nintvars; i++ )
128  {
129  SCIP_Real lpsolval;
130  SCIP_Real solval;
131 
132  /* get the current LP solution and the incumbent solution for each variable */
133  lpsolval = SCIPvarGetLPSol(vars[i]);
134  solval = SCIPgetSolVal(scip, bestsol, vars[i]);
135 
136  /* iff both solutions are equal, variable is stored to be fixed */
137  if( SCIPisFeasEQ(scip, lpsolval, solval) )
138  {
139  /* store the fixing and increase the number of fixed variables */
140  fixedvars[fixingcounter] = vars[i];
141  fixedvals[fixingcounter] = solval;
142  fixingcounter++;
143  }
144  }
145 
146  /* store the number of fixings */
147  *nfixedvars = fixingcounter;
148 
149  /* abort, if all variables should be fixed */
150  if( fixingcounter == nbinvars + nintvars )
151  {
152  *success = FALSE;
153  return SCIP_OKAY;
154  }
155  else
156  fixingrate = (SCIP_Real)fixingcounter / (SCIP_Real)(MAX(nbinvars + nintvars, 1));
157 
158  /* abort, if the amount of fixed variables is insufficient */
159  if( fixingrate < minfixingrate )
160  {
161  *success = FALSE;
162  return SCIP_OKAY;
163  }
164 
165  *success = TRUE;
166  return SCIP_OKAY;
167 }
168 
169 
170 /** creates a new solution for the original problem by copying the solution of the subproblem */
171 static
173  SCIP* scip, /**< original SCIP data structure */
174  SCIP* subscip, /**< SCIP structure of the subproblem */
175  SCIP_VAR** subvars, /**< the variables of the subproblem */
176  SCIP_HEUR* heur, /**< RINS heuristic structure */
177  SCIP_SOL* subsol, /**< solution of the subproblem */
178  SCIP_Bool* success /**< used to store whether new solution was found or not */
179  )
180 {
181  SCIP_VAR** vars; /* the original problem's variables */
182  int nvars;
183  SCIP_Real* subsolvals; /* solution values of the subproblem */
184  SCIP_SOL* newsol; /* solution to be created for the original problem */
185 
186  assert( scip != NULL );
187  assert( subscip != NULL );
188  assert( subvars != NULL );
189  assert( subsol != NULL );
190 
191  /* get variables' data */
192  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
193  /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
194  * since constraint copying may have required the copy of variables that are fixed in the main SCIP
195  */
196  assert(nvars <= SCIPgetNOrigVars(subscip));
197 
198  SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
199 
200  /* copy the solution */
201  SCIP_CALL( SCIPgetSolVals(subscip, subsol, nvars, subvars, subsolvals) );
202 
203  /* create new solution for the original problem */
204  SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
205  SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
206 
207  /* try to add new solution to scip and free it immediately */
208  SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
209 
210  SCIPfreeBufferArray(scip, &subsolvals);
211 
212  return SCIP_OKAY;
213 }
214 
215 /* ---------------- Callback methods of event handler ---------------- */
216 
217 /* exec the event handler
218  *
219  * we interrupt the solution process
220  */
221 static
222 SCIP_DECL_EVENTEXEC(eventExecRins)
223 {
224  SCIP_HEURDATA* heurdata;
225 
226  assert(eventhdlr != NULL);
227  assert(eventdata != NULL);
228  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
229  assert(event != NULL);
230  assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_LPSOLVED);
231 
232  heurdata = (SCIP_HEURDATA*)eventdata;
233  assert(heurdata != NULL);
234 
235  /* interrupt solution process of sub-SCIP */
236  if( SCIPgetNLPs(scip) > heurdata->lplimfac * heurdata->nodelimit )
237  {
238  SCIPdebugMsg(scip, "interrupt after %" SCIP_LONGINT_FORMAT " LPs\n",SCIPgetNLPs(scip));
240  }
241 
242  return SCIP_OKAY;
243 }
244 
245 
246 /*
247  * Callback methods of primal heuristic
248  */
249 
250 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
251 static
252 SCIP_DECL_HEURCOPY(heurCopyRins)
253 { /*lint --e{715}*/
254  assert(scip != NULL);
255  assert(heur != NULL);
256  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
257 
258  /* call inclusion method of primal heuristic */
260 
261  return SCIP_OKAY;
262 }
263 
264 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
265 static
266 SCIP_DECL_HEURFREE(heurFreeRins)
267 { /*lint --e{715}*/
268  SCIP_HEURDATA* heurdata;
269 
270  assert( heur != NULL );
271  assert( scip != NULL );
272 
273  /* get heuristic data */
274  heurdata = SCIPheurGetData(heur);
275  assert( heurdata != NULL );
276 
277  /* free heuristic data */
278  SCIPfreeBlockMemory(scip, &heurdata);
279  SCIPheurSetData(heur, NULL);
280 
281  return SCIP_OKAY;
282 }
283 
284 
285 /** initialization method of primal heuristic (called after problem was transformed) */
286 static
287 SCIP_DECL_HEURINIT(heurInitRins)
288 { /*lint --e{715}*/
289  SCIP_HEURDATA* heurdata;
290 
291  assert( heur != NULL );
292  assert( scip != NULL );
293 
294  /* get heuristic's data */
295  heurdata = SCIPheurGetData(heur);
296  assert( heurdata != NULL );
297 
298  /* initialize data */
299  heurdata->usednodes = 0;
300 
301  return SCIP_OKAY;
302 }
303 
304 
305 /** execution method of primal heuristic */
306 static
307 SCIP_DECL_HEUREXEC(heurExecRins)
308 { /*lint --e{715}*/
310 
311  SCIP_HEURDATA* heurdata; /* heuristic's data */
312  SCIP* subscip; /* the subproblem created by RINS */
313  SCIP_VAR** vars; /* original problem's variables */
314  SCIP_VAR** subvars; /* subproblem's variables */
315  SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
316  SCIP_EVENTHDLR* eventhdlr; /* event handler for LP events */
317  SCIP_VAR** fixedvars;
318  SCIP_Real* fixedvals;
319 
320  SCIP_Real cutoff; /* objective cutoff for the subproblem */
321  SCIP_Real upperbound;
322 
323  int nvars;
324  int nbinvars;
325  int nintvars;
326  int nfixedvars;
327  int i;
328 
329  SCIP_Bool success;
330 
331  assert( heur != NULL );
332  assert( scip != NULL );
333  assert( result != NULL );
334  assert( SCIPhasCurrentNodeLP(scip) );
335 
336  *result = SCIP_DELAYED;
337 
338  /* do not call heuristic of node was already detected to be infeasible */
339  if( nodeinfeasible )
340  return SCIP_OKAY;
341 
342  /* get heuristic's data */
343  heurdata = SCIPheurGetData(heur);
344  assert( heurdata != NULL );
345 
346  /* only call heuristic, if an optimal LP solution and a feasible solution are at hand */
348  return SCIP_OKAY;
349 
350  /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
352  return SCIP_OKAY;
353 
354  /* only call heuristic, if the best solution comes from transformed problem */
355  assert( SCIPgetBestSol(scip) != NULL );
357  return SCIP_OKAY;
358 
359  /* only call heuristic, if enough nodes were processed since last incumbent */
360  if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip,SCIPgetBestSol(scip)) < heurdata->nwaitingnodes)
361  return SCIP_OKAY;
362 
363  *result = SCIP_DIDNOTRUN;
364 
365  /* calculate the maximal number of branching nodes until heuristic is aborted */
366  nnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
367 
368  /* reward RINS if it succeeded often */
369  nnodes = (SCIP_Longint)(nnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
370  nnodes -= (SCIP_Longint)(100.0 * SCIPheurGetNCalls(heur)); /* count the setup costs for the sub-MIP as 100 nodes */
371  nnodes += heurdata->nodesofs;
372 
373  /* determine the node limit for the current process */
374  nnodes -= heurdata->usednodes;
375  nnodes = MIN(nnodes, heurdata->maxnodes);
376 
377  /* check whether we have enough nodes left to call subproblem solving */
378  if( nnodes < heurdata->minnodes )
379  return SCIP_OKAY;
380 
381  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
382 
383  /* check whether discrete variables are available */
384  if( nbinvars == 0 && nintvars == 0 )
385  return SCIP_OKAY;
386 
387  if( SCIPisStopped(scip) )
388  return SCIP_OKAY;
389 
390  /* allocate buffer storage to hold the RINS fixings */
391  SCIP_CALL( SCIPallocBufferArray(scip, &fixedvars, nbinvars + nintvars) );
392  SCIP_CALL( SCIPallocBufferArray(scip, &fixedvals, nbinvars + nintvars) );
393 
394  success = FALSE;
395 
396  nfixedvars = 0;
397  /* determine possible fixings for RINS: variables with same value in bestsol and LP relaxation */
398  SCIP_CALL( determineFixings(scip, fixedvars, fixedvals, &nfixedvars, nbinvars + nintvars, heurdata->minfixingrate, &success) );
399 
400  /* too few variables could be fixed by the RINS scheme */
401  if( !success )
402  goto TERMINATE;
403 
404  /* check whether there is enough time and memory left */
405  SCIP_CALL( SCIPcheckCopyLimits(scip, &success) );
406 
407  /* abort if no time is left or not enough memory to create a copy of SCIP */
408  if( !success )
409  goto TERMINATE;
410 
411  assert(nfixedvars > 0 && nfixedvars < nbinvars + nintvars);
412 
413  *result = SCIP_DIDNOTFIND;
414 
415  SCIPdebugMsg(scip, "RINS heuristic fixes %d out of %d binary+integer variables\n", nfixedvars, nbinvars + nintvars);
416  SCIP_CALL( SCIPcreate(&subscip) );
417 
418  /* create the variable mapping hash map */
419  SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
420 
421  /* create a problem copy as sub SCIP */
422  SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "rins", fixedvars, fixedvals, nfixedvars,
423  heurdata->uselprows, heurdata->copycuts, &success, NULL) );
424 
425  eventhdlr = NULL;
426  /* create event handler for LP events */
427  SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecRins, NULL) );
428  if( eventhdlr == NULL )
429  {
430  SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
431  return SCIP_PLUGINNOTFOUND;
432  }
433 
434  /* copy subproblem variables from map to obtain the same order */
435  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
436  for( i = 0; i < nvars; i++ )
437  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
438 
439  /* free hash map */
440  SCIPhashmapFree(&varmapfw);
441 
442  /* do not abort subproblem on CTRL-C */
443  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
444 
445 #ifdef SCIP_DEBUG
446  /* for debugging, enable full output */
447  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", SCIP_VERBLEVEL_FULL) );
448  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
449 #else
450  /* disable statistic timing inside sub SCIP and output to console */
451  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", (int) SCIP_VERBLEVEL_NONE) );
452  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
453 #endif
454 
455  /* set limits for the subproblem */
456  SCIP_CALL( SCIPcopyLimits(scip, subscip) );
457  heurdata->nodelimit = nnodes;
458  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nnodes) );
459  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", MAX(10, nnodes/10)) );
460  SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", 3) );
461 
462  /* forbid recursive call of heuristics and separators solving subMIPs */
463  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
464 
465  /* disable cutting plane separation */
467 
468  /* disable expensive presolving */
470 
471  /* use best estimate node selection */
472  if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
473  {
474  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
475  }
476 
477  /* activate uct node selection at the top of the tree */
478  if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") )
479  {
480  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) );
481  }
482 
483  /* use inference branching */
484  if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
485  {
486  SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
487  }
488 
489  /* enable conflict analysis and restrict conflict pool */
490  if( !SCIPisParamFixed(subscip, "conflict/enable") )
491  {
492  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) );
493  }
494  if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") )
495  {
496  SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) );
497  }
498 
499  /* speed up sub-SCIP by not checking dual LP feasibility */
500  SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
501 
502  /* employ a limit on the number of enforcement rounds in the quadratic constraint handler; this fixes the issue that
503  * sometimes the quadratic constraint handler needs hundreds or thousands of enforcement rounds to determine the
504  * feasibility status of a single node without fractional branching candidates by separation (namely for uflquad
505  * instances); however, the solution status of the sub-SCIP might get corrupted by this; hence no deductions shall be
506  * made for the original SCIP
507  */
508  if( SCIPfindConshdlr(subscip, "quadratic") != NULL && !SCIPisParamFixed(subscip, "constraints/quadratic/enfolplimit") )
509  {
510  SCIP_CALL( SCIPsetIntParam(subscip, "constraints/quadratic/enfolplimit", 500) );
511  }
512 
513  /* add an objective cutoff */
515 
516  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
517  if( !SCIPisInfinity(scip, -1.0 * SCIPgetLowerbound(scip)) )
518  {
519  cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip) + heurdata->minimprove * SCIPgetLowerbound(scip);
520  }
521  else
522  {
523  if( SCIPgetUpperbound(scip) >= 0 )
524  cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip);
525  else
526  cutoff = (1 + heurdata->minimprove) * SCIPgetUpperbound(scip);
527  }
528  cutoff = MIN(upperbound, cutoff);
529  SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) );
530 
531  /* catch LP events of sub-SCIP */
532  SCIP_CALL( SCIPtransformProb(subscip) );
533  SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
534 
535  /* Errors in solving the subproblem should not kill the overall solving process
536  * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
537  */
538  /* solve the subproblem */
539  SCIP_CALL_ABORT( SCIPsolve(subscip) );
540 
541  /* drop LP events of sub-SCIP */
542  SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
543 
544  /* we try to merge variable statistics with those of our main SCIP */
545  SCIP_CALL( SCIPmergeVariableStatistics(subscip, scip, subvars, vars, nvars) );
546 
547  /* print solving statistics of subproblem if we are in SCIP's debug mode */
549 
550  heurdata->usednodes += SCIPgetNNodes(subscip);
551 
552  /* check, whether a solution was found */
553  if( SCIPgetNSols(subscip) > 0 )
554  {
555  SCIP_SOL** subsols;
556  int nsubsols;
557 
558  /* check, whether a solution was found;
559  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
560  */
561  nsubsols = SCIPgetNSols(subscip);
562  subsols = SCIPgetSols(subscip);
563  success = FALSE;
564  for( i = 0; i < nsubsols && !success; ++i )
565  {
566  SCIP_CALL( createNewSol(scip, subscip, subvars, heur, subsols[i], &success) );
567  }
568  if( success )
569  *result = SCIP_FOUNDSOL;
570  }
571  /* free subproblem */
572  SCIPfreeBufferArray(scip, &subvars);
573  SCIP_CALL( SCIPfree(&subscip) );
574 
575  TERMINATE:
576  SCIPfreeBufferArray(scip, &fixedvals);
577  SCIPfreeBufferArray(scip, &fixedvars);
578 
579  return SCIP_OKAY;
580 }
581 
582 /*
583  * primal heuristic specific interface methods
584  */
585 
586 /** creates the RINS primal heuristic and includes it in SCIP */
588  SCIP* scip /**< SCIP data structure */
589  )
590 {
591  SCIP_HEURDATA* heurdata;
592  SCIP_HEUR* heur;
593 
594  /* create Rins primal heuristic data */
595  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
596 
597  /* include primal heuristic */
598  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
600  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecRins, heurdata) );
601 
602  assert(heur != NULL);
603 
604  /* set non-NULL pointers to callback methods */
605  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyRins) );
606  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeRins) );
607  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitRins) );
608 
609  /* add RINS primal heuristic parameters */
610  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
611  "number of nodes added to the contingent of the total nodes",
612  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0, INT_MAX, NULL, NULL) );
613 
614  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
615  "maximum number of nodes to regard in the subproblem",
616  &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0, INT_MAX, NULL, NULL) );
617 
618  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/minnodes",
619  "minimum number of nodes required to start the subproblem",
620  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0, INT_MAX, NULL, NULL) );
621 
622  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
623  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
624  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
625 
626  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nwaitingnodes",
627  "number of nodes without incumbent change that heuristic should wait",
628  &heurdata->nwaitingnodes, TRUE, DEFAULT_NWAITINGNODES, 0, INT_MAX, NULL, NULL) );
629 
630  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
631  "factor by which " HEUR_NAME " should at least improve the incumbent",
632  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
633 
634  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate",
635  "minimum percentage of integer variables that have to be fixed",
636  &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) );
637 
638  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lplimfac",
639  "factor by which the limit on the number of LP depends on the node limit",
640  &heurdata->lplimfac, TRUE, DEFAULT_LPLIMFAC, 1.0, SCIP_REAL_MAX, NULL, NULL) );
641 
642  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows",
643  "should subproblem be created out of the rows in the LP rows?",
644  &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
645 
646  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
647  "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
648  &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
649 
650  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct",
651  "should uct node selection be used at the beginning of the search?",
652  &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) );
653 
654 
655  return SCIP_OKAY;
656 }
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
Definition: sol.c:2299
#define SCIP_EVENTTYPE_LPSOLVED
Definition: type_event.h:84
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5130
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46320
static SCIP_DECL_HEUREXEC(heurExecRins)
Definition: heur_rins.c:307
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6576
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:42726
#define HEUR_PRIORITY
Definition: heur_rins.c:34
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1327
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip.c:12120
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46037
#define DEFAULT_MINNODES
Definition: heur_rins.c:43
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip.c:8561
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11554
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip.c:39108
#define FALSE
Definition: def.h:64
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2764
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:278
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip.c:4164
#define TRUE
Definition: def.h:63
#define SCIPdebug(x)
Definition: pub_message.h:74
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5104
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip.c:9219
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
#define HEUR_FREQ
Definition: heur_rins.c:35
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21973
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip.c:8034
#define EVENTHDLR_NAME
Definition: heur_rins.c:57
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2902
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22003
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip.c:696
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1102
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21956
#define SCIPdebugMsg
Definition: scip.h:451
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4237
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
Definition: scip.c:44659
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool *success)
Definition: heur_rins.c:172
#define DEFAULT_MINIMPROVE
Definition: heur_rins.c:44
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip.c:15846
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1181
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip.c:4373
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip.c:8095
#define HEUR_USESSUBSCIP
Definition: heur_rins.c:39
#define DEFAULT_USELPROWS
Definition: heur_rins.c:49
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:38219
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip.c:4602
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:45753
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:155
#define DEFAULT_MAXNODES
Definition: heur_rins.c:42
SCIP_RETCODE SCIPincludeHeurRins(SCIP *scip)
Definition: heur_rins.c:587
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2797
SCIP_RETCODE SCIPmergeVariableStatistics(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **sourcevars, SCIP_VAR **targetvars, int nvars)
Definition: scip.c:2420
#define DEFAULT_USEUCT
Definition: heur_rins.c:54
#define NULL
Definition: lpi_spx1.cpp:137
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:17543
#define DEFAULT_LPLIMFAC
Definition: heur_rins.c:47
#define SCIP_CALL(x)
Definition: def.h:316
SCIP_Real SCIPgetLowerbound(SCIP *scip)
Definition: scip.c:42550
static SCIP_DECL_HEURCOPY(heurCopyRins)
Definition: heur_rins.c:252
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1307
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip.c:28863
#define DEFAULT_MINFIXINGRATE
Definition: heur_rins.c:45
#define HEUR_TIMING
Definition: heur_rins.c:38
static SCIP_RETCODE determineFixings(SCIP *scip, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int *nfixedvars, int fixedvarssize, SCIP_Real minfixingrate, SCIP_Bool *success)
Definition: heur_rins.c:94
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21991
#define HEUR_MAXDEPTH
Definition: heur_rins.c:37
public data structures and miscellaneous methods
#define DEFAULT_NODESOFS
Definition: heur_rins.c:41
#define SCIP_Bool
Definition: def.h:61
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip.c:40434
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:28948
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:959
#define HEUR_DESC
Definition: heur_rins.c:32
#define HEUR_NAME
Definition: heur_rins.c:31
#define DEFAULT_NWAITINGNODES
Definition: heur_rins.c:48
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip.c:11114
LNS heuristic that combines the incumbent with the LP optimum.
#define MAX(x, y)
Definition: tclique_def.h:75
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip.c:40070
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip.c:4660
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip.c:40468
int SCIPgetNSols(SCIP *scip)
Definition: scip.c:39059
static SCIP_DECL_EVENTEXEC(eventExecRins)
Definition: heur_rins.c:222
Constraint handler for linear constraints in their most general form, .
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:46061
static SCIP_DECL_HEURINIT(heurInitRins)
Definition: heur_rins.c:287
#define SCIP_REAL_MAX
Definition: def.h:146
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip.c:29027
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip.c:39158
#define HEUR_DISPCHAR
Definition: heur_rins.c:33
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip.c:8111
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip.c:8907
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:899
#define SCIP_Real
Definition: def.h:145
#define HEUR_FREQOFS
Definition: heur_rins.c:36
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
#define MIN(x, y)
Definition: memory.c:75
#define SCIP_Longint
Definition: def.h:130
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip.c:4128
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:38084
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip.c:13717
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip.c:8079
#define nnodes
Definition: gastrans.c:65
SCIP_Real SCIPsumepsilon(SCIP *scip)
Definition: scip.c:45494
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
Definition: scip.c:17019
SCIP_Real SCIPgetUpperbound(SCIP *scip)
Definition: scip.c:42699
#define SCIP_CALL_ABORT(x)
Definition: def.h:295
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1092
#define DEFAULT_COPYCUTS
Definition: heur_rins.c:51
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:41409
SCIP_Longint SCIPgetNLPs(SCIP *scip)
Definition: scip.c:41590
static SCIP_DECL_HEURFREE(heurFreeRins)
Definition: heur_rins.c:266
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38182
default SCIP plugins
#define DEFAULT_NODESQUOT
Definition: heur_rins.c:46
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4293
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip.c:5055
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip.c:4718
SCIP callable library.
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4211
#define EVENTHDLR_DESC
Definition: heur_rins.c:58
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip.c:774
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37178
SCIP_Longint SCIPgetSolNodenum(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38483