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