Scippy

SCIP

Solving Constraint Integer Programs

heur_rens.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
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
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"
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 */
112struct 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};
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 */
144static
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 */
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 */
251static
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
312/* ---------------- Callback methods of event handler ---------------- */
313
314/* exec the event handler
315 *
316 * we interrupt the solution process
317 */
318static
319SCIP_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);
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 */
343static
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;
490
491 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
492
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
593TERMINATE:
594 /* free sub problem data */
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
678TERMINATE:
679 /* free buffer storage for variable fixings */
680 SCIPfreeBufferArray(scip, &fixedvals);
681 SCIPfreeBufferArray(scip, &fixedvars);
682
683 return SCIP_OKAY;
684}
686
687/*
688 * Callback methods of primal heuristic
689 */
690
691/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
692static
693SCIP_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) */
706static
707SCIP_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 */
720 SCIPheurSetData(heur, NULL);
721
722 return SCIP_OKAY;
723}
724
725/** initialization method of primal heuristic (called after problem was transformed) */
726static
727SCIP_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 */
746static
747SCIP_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;
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 */
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}
#define NULL
Definition: def.h:267
#define SCIP_Longint
Definition: def.h:158
#define SCIP_REAL_MAX
Definition: def.h:174
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
#define SCIPABORT()
Definition: def.h:346
#define SCIP_LONGINT_MAX
Definition: def.h:159
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3253
SCIP_RETCODE SCIPmergeVariableStatistics(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **sourcevars, SCIP_VAR **targetvars, int nvars)
Definition: scip_copy.c:1265
SCIP_RETCODE SCIPtranslateSubSol(SCIP *scip, SCIP *subscip, SCIP_SOL *subsol, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_SOL **newsol)
Definition: scip_copy.c:1408
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3296
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:724
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:339
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:307
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2082
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip_prob.c:1422
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1866
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3042
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip_prob.c:2432
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3108
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
#define SCIPdebugMsg
Definition: scip_message.h:78
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
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:595
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_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:219
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
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 SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:545
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 SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:487
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:904
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:953
SCIP_RETCODE SCIPsetCharParam(SCIP *scip, const char *name, char value)
Definition: scip_param.c:661
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 SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:429
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:979
SCIP_RETCODE SCIPincludeHeurRens(SCIP *scip)
Definition: heur_rens.c:811
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:297
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:428
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
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:324
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:1030
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:286
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:320
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1364
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
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1599
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1579
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:194
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1453
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1374
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:83
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:247
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
int SCIPgetNNlpis(SCIP *scip)
Definition: scip_nlpi.c:200
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip_nlp.c:110
SCIP_NLPSOLSTAT SCIPgetNLPSolstat(SCIP *scip)
Definition: scip_nlp.c:574
#define SCIPsolveNLP(...)
Definition: scip_nlp.h:361
SCIP_RETCODE SCIPsetNLPInitialGuessSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_nlp.c:501
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip_nodesel.c:234
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2169
SCIP_Longint SCIPsolGetNodenum(SCIP_SOL *sol)
Definition: sol.c:2784
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2070
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip_sol.c:2119
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:3050
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip_solve.c:222
SCIP_RETCODE SCIPpresolve(SCIP *scip)
Definition: scip_solve.c:2328
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
Definition: scip_solve.c:3430
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2498
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
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:951
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:378
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
SCIP_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4943
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:18452
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:5032
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
SCIP_Real SCIPvarGetNLPSol(SCIP_VAR *var)
Definition: var.c:18465
#define DEFAULT_FULLSCALE
Definition: heur_rens.c:91
static SCIP_DECL_HEUREXEC(heurExecRens)
Definition: heur_rens.c:739
#define DEFAULT_NODESQUOT
Definition: heur_rens.c:82
#define DEFAULT_STARTSOL
Definition: heur_rens.c:84
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:336
#define DEFAULT_BINARYBOUNDS
Definition: heur_rens.c:76
#define DEFAULT_NODESOFS
Definition: heur_rens.c:81
#define DEFAULT_COPYCUTS
Definition: heur_rens.c:87
#define DEFAULT_MAXNODES
Definition: heur_rens.c:77
#define HEUR_TIMING
Definition: heur_rens.c:72
#define DEFAULT_MINNODES
Definition: heur_rens.c:80
#define HEUR_FREQOFS
Definition: heur_rens.c:70
#define DEFAULT_EXTRATIME
Definition: heur_rens.c:88
#define HEUR_DESC
Definition: heur_rens.c:66
#define DEFAULT_LPLIMFAC
Definition: heur_rens.c:83
static SCIP_DECL_EVENTEXEC(eventExecRens)
Definition: heur_rens.c:311
#define DEFAULT_ADDALLSOLS
Definition: heur_rens.c:89
#define DEFAULT_MINFIXINGRATE
Definition: heur_rens.c:78
#define DEFAULT_USEUCT
Definition: heur_rens.c:93
static SCIP_DECL_HEURINIT(heurInitRens)
Definition: heur_rens.c:719
#define STARTSOL_CHOICES
Definition: heur_rens.c:85
#define HEUR_DISPCHAR
Definition: heur_rens.c:67
#define HEUR_MAXDEPTH
Definition: heur_rens.c:71
#define HEUR_PRIORITY
Definition: heur_rens.c:68
static SCIP_DECL_HEURCOPY(heurCopyRens)
Definition: heur_rens.c:685
#define DEFAULT_MINIMPROVE
Definition: heur_rens.c:79
#define HEUR_NAME
Definition: heur_rens.c:65
#define DEFAULT_USELPROWS
Definition: heur_rens.c:86
static SCIP_RETCODE restrictToBinaryBounds(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, char startsol)
Definition: heur_rens.c:244
#define DEFAULT_BESTSOLLIMIT
Definition: heur_rens.c:92
static SCIP_DECL_HEURFREE(heurFreeRens)
Definition: heur_rens.c:699
#define EVENTHDLR_DESC
Definition: heur_rens.c:97
#define HEUR_FREQ
Definition: heur_rens.c:69
#define HEUR_USESSUBSCIP
Definition: heur_rens.c:73
#define EVENTHDLR_NAME
Definition: heur_rens.c:96
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:137
LNS heuristic that finds the optimal rounding to a given point.
methods commonly used by primal heuristics
memory allocation routines
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
public methods for managing events
public methods for primal heuristics
public methods for message output
#define SCIPerrorMessage
Definition: pub_message.h:64
#define SCIPdebug(x)
Definition: pub_message.h:93
#define SCIPstatisticPrintf
Definition: pub_message.h:126
public data structures and miscellaneous methods
public methods for primal CIP solutions
public methods for problem variables
public methods for branching rule plugins and branching
public methods for constraint handler plugins and constraints
public methods for problem copies
public methods for event handler plugins and event handlers
general public methods
public methods for primal heuristic plugins and divesets
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for nonlinear relaxation
public methods for NLPI solver interfaces
public methods for node selector plugins
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for solutions
public solving methods
public methods for querying solving statistics
public methods for timing
public methods for SCIP variables
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:173
#define SCIP_EVENTTYPE_LPSOLVED
Definition: type_event.h:101
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:43
enum SCIP_NlpSolStat SCIP_NLPSOLSTAT
Definition: type_nlpi.h:168
@ SCIP_NLPSOLSTAT_FEASIBLE
Definition: type_nlpi.h:162
@ SCIP_NLPSOLSTAT_LOCOPT
Definition: type_nlpi.h:161
@ SCIP_NLPSOLSTAT_GLOBOPT
Definition: type_nlpi.h:160
@ SCIP_PARAMSETTING_OFF
Definition: type_paramset.h:63
@ SCIP_PARAMSETTING_FAST
Definition: type_paramset.h:62
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_DELAYED
Definition: type_result.h:43
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_FOUNDSOL
Definition: type_result.h:56
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_PLUGINNOTFOUND
Definition: type_retcode.h:54
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63