Scippy

SCIP

Solving Constraint Integer Programs

heur_proximity.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_proximity.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief improvement heuristic which uses an auxiliary objective instead of the original objective function which
28 * is itself added as a constraint to a sub-SCIP instance. The heuristic was presented by Matteo Fischetti
29 * and Michele Monaci.
30 * @author Gregor Hendel
31 */
32
33/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34
36#include "scip/cons_linear.h"
37#include "scip/heuristics.h"
38#include "scip/heur_proximity.h"
39#include "scip/pub_event.h"
40#include "scip/pub_heur.h"
41#include "scip/pub_message.h"
42#include "scip/pub_misc.h"
43#include "scip/pub_sol.h"
44#include "scip/pub_var.h"
45#include "scip/scip_branch.h"
46#include "scip/scip_cons.h"
47#include "scip/scip_copy.h"
48#include "scip/scip_event.h"
49#include "scip/scip_general.h"
50#include "scip/scip_heur.h"
51#include "scip/scip_lp.h"
52#include "scip/scip_mem.h"
53#include "scip/scip_message.h"
54#include "scip/scip_nlp.h"
55#include "scip/scip_nodesel.h"
56#include "scip/scip_numerics.h"
57#include "scip/scip_param.h"
58#include "scip/scip_prob.h"
59#include "scip/scip_sol.h"
60#include "scip/scip_solve.h"
62#include "scip/scip_timing.h"
63#include "scip/scip_var.h"
64#include <string.h>
65
66#define HEUR_NAME "proximity"
67#define HEUR_DESC "heuristic trying to improve the incumbent by an auxiliary proximity objective function"
68#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
69#define HEUR_PRIORITY -2000000
70#define HEUR_FREQ -1
71#define HEUR_FREQOFS 0
72#define HEUR_MAXDEPTH -1
73#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
74#define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
75
76/* event handler properties */
77#define EVENTHDLR_NAME "Proximity"
78#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic"
79
80/* default values for proximity-specific parameters */
81/* todo refine these values */
82#define DEFAULT_MAXNODES 10000LL /**< maximum number of nodes to regard in the subproblem */
83#define DEFAULT_MINIMPROVE 0.02 /**< factor by which proximity should at least improve the incumbent */
84#define DEFAULT_MINGAP 0.01 /**< minimum primal-dual gap for which the heuristic is executed */
85#define DEFAULT_MINNODES 1LL /**< minimum number of nodes to regard in the subproblem */
86#define DEFAULT_MINLPITERS 200LL /**< minimum number of LP iterations to perform in one sub-mip */
87#define DEFAULT_MAXLPITERS 100000LL /**< maximum number of LP iterations to be performed in the subproblem */
88#define DEFAULT_NODESOFS 50LL /**< number of nodes added to the contingent of the total nodes */
89#define DEFAULT_WAITINGNODES 100LL /**< default waiting nodes since last incumbent before heuristic is executed */
90#define DEFAULT_NODESQUOT 0.1 /**< default quotient of sub-MIP nodes with respect to number of processed nodes*/
91#define DEFAULT_USELPROWS FALSE /**< should subproblem be constructed based on LP row information? */
92#define DEFAULT_BINVARQUOT 0.1 /**< default threshold for percentage of binary variables required to start */
93#define DEFAULT_RESTART TRUE /**< should the heuristic immediately run again on its newly found solution? */
94#define DEFAULT_USEFINALLP FALSE /**< should the heuristic solve a final LP in case of continuous objective variables? */
95#define DEFAULT_LPITERSQUOT 0.2 /**< default quotient of sub-MIP LP iterations with respect to LP iterations so far */
96#define DEFAULT_USEUCT FALSE /**< should uct node selection be used at the beginning of the search? */
97
98/*
99 * Data structures
100 */
101
102/** primal heuristic data */
103struct SCIP_HeurData
104{
105 SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
106 SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
107 SCIP_Longint maxlpiters; /**< maximum number of LP iterations to be performed in the subproblem */
108 SCIP_Longint nusedlpiters; /**< number of actually performed LP iterations */
109 SCIP_Longint minlpiters; /**< minimum number of LP iterations to perform in one sub-mip */
110 SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
111 SCIP_Longint usednodes; /**< nodes already used by proximity in earlier calls */
112 SCIP_Longint waitingnodes; /**< waiting nodes since last incumbent before heuristic is executed */
113 SCIP_Real lpitersquot; /**< quotient of sub-MIP LP iterations with respect to LP iterations so far */
114 SCIP_Real minimprove; /**< factor by which proximity should at least improve the incumbent */
115 SCIP_Real mingap; /**< minimum primal-dual gap for which the heuristic is executed */
116 SCIP_Real nodesquot; /**< quotient of sub-MIP nodes with respect to number of processed nodes */
117 SCIP_Real binvarquot; /**< threshold for percantage of binary variables required to start */
118
119 SCIP* subscip; /**< the subscip used by the heuristic */
120 SCIP_HASHMAP* varmapfw; /**< map between scip variables and subscip variables */
121 SCIP_VAR** subvars; /**< variables in subscip */
122 SCIP_CONS* objcons; /**< the objective cutoff constraint of the subproblem */
123
124 int nsubvars; /**< the number of subvars */
125 int lastsolidx; /**< index of last solution on which the heuristic was processed */
126 int subprobidx; /**< counter for the subproblem index to be solved by proximity */
127
128 SCIP_Bool uselprows; /**< should subproblem be constructed based on LP row information? */
129 SCIP_Bool restart; /**< should the heuristic immediately run again on its newly found solution? */
130 SCIP_Bool usefinallp; /**< should the heuristic solve a final LP in case of continuous objective variables? */
131 SCIP_Bool useuct; /**< should uct node selection be used at the beginning of the search? */
132};
133
134
135/*
136 * Local methods
137 */
138
139/** optimizes the continuous variables in an LP diving by fixing all integer variables to the given solution values */
140static
142 SCIP* scip, /**< SCIP data structure */
143 SCIP_SOL* sol, /**< candidate solution for which continuous variables should be optimized */
144 SCIP_Bool* success /**< was the dive successful? */
145 )
146{
147 SCIP_VAR** vars;
148 SCIP_RETCODE retstat;
149
150 int v;
151 int nvars;
152 int ncontvars;
153 int nintvars;
154
155 SCIP_Bool lperror;
156 SCIP_Bool requiresnlp;
157
158 assert(success != NULL);
159
160 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, &ncontvars) );
161
162 nintvars = nvars - ncontvars;
163
164 /**@todo in case of an MINLP, if SCIPisNLPConstructed() is TRUE rather solve the NLP instead of the LP */
165 requiresnlp = SCIPisNLPConstructed(scip);
166 if( requiresnlp || ncontvars == 0 )
167 return SCIP_OKAY;
168
169 /* start diving to calculate the LP relaxation */
171
172 /* set the bounds of the variables: fixed for integers, global bounds for continuous */
173 for( v = 0; v < nvars; ++v )
174 {
176 {
177 SCIP_CALL( SCIPchgVarLbDive(scip, vars[v], SCIPvarGetLbGlobal(vars[v])) );
178 SCIP_CALL( SCIPchgVarUbDive(scip, vars[v], SCIPvarGetUbGlobal(vars[v])) );
179 }
180 }
181
182 /* apply this after global bounds to not cause an error with intermediate empty domains */
183 for( v = 0; v < nintvars; ++v )
184 {
186 {
187 SCIP_Real solval;
188
189 solval = SCIPgetSolVal(scip, sol, vars[v]);
190 SCIP_CALL( SCIPchgVarLbDive(scip, vars[v], solval) );
191 SCIP_CALL( SCIPchgVarUbDive(scip, vars[v], solval) );
192 }
193 }
194
195 /* solve LP */
196 SCIPdebugMsg(scip, " -> old LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
197
198 /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
199 * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
200 */
201 retstat = SCIPsolveDiveLP(scip, -1, &lperror, NULL);
202 if( retstat != SCIP_OKAY )
203 {
204#ifdef NDEBUG
205 SCIPwarningMessage(scip, "Error while solving LP in Proximity heuristic; LP solve terminated with code <%d>\n",retstat);
206#else
207 SCIP_CALL( retstat );
208#endif
209 }
210
211 SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
212 SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, SCIPgetLPSolstat(scip));
213 if( !lperror && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
214 {
216 SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
217 }
218
219 /* terminate diving mode */
221
222 return SCIP_OKAY;
223}
224
225/** creates a new solution for the original problem by copying the solution of the subproblem */
226static
228 SCIP* scip, /**< original SCIP data structure */
229 SCIP* subscip, /**< SCIP structure of the subproblem */
230 SCIP_VAR** subvars, /**< the variables of the subproblem */
231 SCIP_HEUR* heur, /**< proximity heuristic structure */
232 SCIP_SOL* subsol, /**< solution of the subproblem */
233 SCIP_Bool usefinallp, /**< should continuous variables be optimized by a final LP */
234 SCIP_Bool* success /**< used to store whether new solution was found or not */
235 )
236{
237 SCIP_VAR** vars; /* the original problem's variables */
238 int nvars; /* the original problem's number of variables */
239 int ncontvars; /* the original problem's number of continuous variables */
240 SCIP_Real* subsolvals; /* solution values of the subproblem */
241 SCIP_SOL* newsol; /* solution to be created for the original problem */
242 int i;
243
244 assert(scip != NULL);
245 assert(subscip != NULL);
246 assert(subvars != NULL);
247 assert(subsol != NULL);
248 assert(success != NULL);
249
250 /* get variables' data */
251 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, &ncontvars) );
252
253 SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
254
255 /* copy the solution */
256 for( i = 0; i < nvars; ++i )
257 {
258 if( subvars[i] == NULL )
259 subsolvals[i] = MIN(MAX(0.0, SCIPvarGetLbLocal(vars[i])), SCIPvarGetUbLocal(vars[i])); /*lint !e666*/
260 else
261 subsolvals[i] = SCIPgetSolVal(subscip, subsol, subvars[i]);
262 }
263
264 /* create new solution for the original problem */
265 SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
266 SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
267
268 *success = FALSE;
269
270 /* solve an LP with all integer variables fixed to improve solution quality */
271 if( ncontvars > 0 && usefinallp && SCIPisLPConstructed(scip) )
272 {
273 int v;
274 int ncontobjvars = 0; /* does the problem instance have continuous variables with nonzero objective coefficients? */
275 SCIP_Real sumofobjsquares = 0.0;
276
277 /* check if continuous variables with nonzero objective coefficient are present */
278 for( v = nvars - 1; v >= nvars - ncontvars; --v )
279 {
280 SCIP_VAR* var;
281
282 var = vars[v];
283 assert(vars[v] != NULL);
284 assert(!SCIPvarIsIntegral(var));
285
287 {
288 ++ncontobjvars;
289 sumofobjsquares += SCIPvarGetObj(var) * SCIPvarGetObj(var);
290 }
291 }
292
293 SCIPstatisticMessage(" Continuous Objective variables: %d, Euclidean OBJ: %g total, %g continuous\n", ncontobjvars, SCIPgetObjNorm(scip), sumofobjsquares);
294
295 /* solve a final LP to optimize solution values of continuous problem variables */
296 SCIPstatisticMessage("Solution Value before LP resolve: %g\n", SCIPgetSolOrigObj(scip, newsol));
297 SCIP_CALL( solveLp(scip, newsol, success) );
298
299 /* if the LP solve was not successful, reset the solution */
300 if( !*success )
301 {
302 for( v = nvars - 1; v >= nvars - ncontvars; --v )
303 {
304 SCIP_CALL( SCIPsetSolVal(scip, newsol, vars[v], subsolvals[v]) );
305 }
306 }
307 }
308
309 /* try to add new solution to SCIP and free it immediately */
310 if( !*success )
311 {
312 SCIP_CALL( SCIPtrySol(scip, newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
313 }
314 SCIP_CALL( SCIPfreeSol(scip, &newsol) );
315
316 SCIPfreeBufferArray(scip, &subsolvals);
317
318 return SCIP_OKAY;
319}
320
321/** sets solving parameters for the subproblem created by the heuristic */
322static
324 SCIP_HEURDATA* heurdata, /**< heuristic data structure */
325 SCIP* subscip /**< copied SCIP data structure */
326 )
327{
328 assert(subscip != NULL);
329
330 /* do not abort subproblem on CTRL-C */
331 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
332
333#ifdef SCIP_DEBUG
334 /* for debugging, enable full output */
335 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
336 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
337#else
338 /* disable statistic timing inside sub SCIP and output to console */
339 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
340 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
341#endif
342
343 /* forbid recursive call of heuristics and separators solving sub-SCIPs */
344 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
345
346 /* use restart dfs node selection */
347 if( SCIPfindNodesel(subscip, "restartdfs") != NULL && !SCIPisParamFixed(subscip, "nodeselection/restartdfs/stdpriority") )
348 {
349 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/restartdfs/stdpriority", INT_MAX/4) );
350 }
351
352 /* activate uct node selection at the top of the tree */
353 if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") )
354 {
355 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) );
356 }
357
358 /* disable expensive presolving
359 * todo maybe presolving can be entirely turned off here - parameter???
360 */
362
363 /* SCIP_CALL( SCIPsetPresolving(scip, SCIP_PARAMSETTING_OFF, TRUE) ); */
364 if( !SCIPisParamFixed(subscip, "presolving/maxrounds") )
365 {
366 SCIP_CALL( SCIPsetIntParam(subscip, "presolving/maxrounds", 50) );
367 }
368
369 /* disable cutting plane separation */
371
372 /* todo: check branching rule in sub-SCIP */
373 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
374 {
375 SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
376 }
377
378 /* disable feasibility pump and fractional diving */
379 if( !SCIPisParamFixed(subscip, "heuristics/feaspump/freq") )
380 {
381 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/feaspump/freq", -1) );
382 }
383 if( !SCIPisParamFixed(subscip, "heuristics/fracdiving/freq") )
384 {
385 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/fracdiving/freq", -1) );
386 }
387
388 /* todo check if
389 * SCIP_CALL( SCIPsetEmphasis(subscip, SCIP_PARAMEMPHASIS_FEASIBILITY, TRUE) );
390 * improves performance */
391
392 return SCIP_OKAY;
393}
394
395/** frees the subproblem */
396static
398 SCIP* scip, /**< SCIP data structure */
399 SCIP_HEURDATA* heurdata /**< heuristic data */
400 )
401{
402 /* free remaining memory from heuristic execution */
403 if( heurdata->subscip != NULL )
404 {
405 assert(heurdata->varmapfw != NULL);
406 assert(heurdata->subvars != NULL);
407 assert(heurdata->objcons != NULL);
408
409 SCIPdebugMsg(scip, "Freeing subproblem of proximity heuristic\n");
410 SCIPfreeBlockMemoryArray(scip, &heurdata->subvars, heurdata->nsubvars);
411 SCIPhashmapFree(&heurdata->varmapfw);
412 SCIP_CALL( SCIPreleaseCons(heurdata->subscip, &heurdata->objcons) );
413 SCIP_CALL( SCIPfree(&heurdata->subscip) );
414
415 heurdata->subscip = NULL;
416 heurdata->varmapfw = NULL;
417 heurdata->subvars = NULL;
418 heurdata->objcons = NULL;
419 }
420 return SCIP_OKAY;
421}
422
423/* ---------------- Callback methods of event handler ---------------- */
424
425/** exec the event handler
426 *
427 * We interrupt the solution process.
428 */
429static
430SCIP_DECL_EVENTEXEC(eventExecProximity)
431{
432 SCIP_HEURDATA* heurdata;
433
434 assert(eventhdlr != NULL);
435 assert(eventdata != NULL);
436 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
437 assert(event != NULL);
439
440 heurdata = (SCIP_HEURDATA*)eventdata;
441 assert(heurdata != NULL);
442
443 /* interrupt solution process of sub-SCIP
444 * todo adjust interruption limit */
445 if( SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_ITERLIMIT || SCIPgetNLPIterations(scip) >= heurdata->maxlpiters )
446 {
448 }
449
450 return SCIP_OKAY;
451}
452
453
454/* ---------------- Callback methods of primal heuristic ---------------- */
455
456/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
457static
458SCIP_DECL_HEURCOPY(heurCopyProximity)
459{ /*lint --e{715}*/
460 assert(scip != NULL);
461 assert(heur != NULL);
462 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
463
464 /* call inclusion method of primal heuristic */
466
467 return SCIP_OKAY;
468}
469
470/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
471static
472SCIP_DECL_HEURFREE(heurFreeProximity)
473{ /*lint --e{715}*/
474 SCIP_HEURDATA* heurdata;
475
476 assert( heur != NULL );
477 assert( scip != NULL );
478
479 /* get heuristic data */
480 heurdata = SCIPheurGetData(heur);
481 assert( heurdata != NULL );
482
483 /* free heuristic data */
484 SCIPfreeBlockMemory(scip, &heurdata);
485 SCIPheurSetData(heur, NULL);
486
487 return SCIP_OKAY;
488}
489
490
491/** initialization method of primal heuristic (called after problem was transformed) */
492static
493SCIP_DECL_HEURINIT(heurInitProximity)
494{ /*lint --e{715}*/
495 SCIP_HEURDATA* heurdata;
496
497 assert( heur != NULL );
498 assert( scip != NULL );
499
500 /* get heuristic data */
501 heurdata = SCIPheurGetData(heur);
502 assert( heurdata != NULL );
503
504 /* initialize data */
505 heurdata->usednodes = 0LL;
506 heurdata->lastsolidx = -1;
507 heurdata->nusedlpiters = 0LL;
508 heurdata->subprobidx = 0;
509
510 heurdata->subscip = NULL;
511 heurdata->varmapfw = NULL;
512 heurdata->subvars = NULL;
513 heurdata->objcons = NULL;
514
515 heurdata->nsubvars = 0;
516
517 return SCIP_OKAY;
518}
519
520/** solution process exiting method of proximity heuristic */
521static
522SCIP_DECL_HEUREXITSOL(heurExitsolProximity)
523{
524 SCIP_HEURDATA* heurdata;
525
526 assert( heur != NULL );
527 assert( scip != NULL );
528
529 /* get heuristic data */
530 heurdata = SCIPheurGetData(heur);
531 assert( heurdata != NULL );
532
533 SCIP_CALL( deleteSubproblem(scip, heurdata) );
534
535 assert(heurdata->subscip == NULL && heurdata->varmapfw == NULL && heurdata->subvars == NULL && heurdata->objcons == NULL);
536
537 return SCIP_OKAY;
538}
539
540/** execution method of primal heuristic */
541static
542SCIP_DECL_HEUREXEC(heurExecProximity)
543{ /*lint --e{715}*/
544 SCIP_HEURDATA* heurdata; /* heuristic's data */
545 SCIP_Longint nnodes; /* number of stalling nodes for the subproblem */
546 SCIP_Longint nlpiters; /* lp iteration limit for the subproblem */
547 SCIP_Bool foundsol = FALSE;
548
549 assert(heur != NULL);
550 assert(scip != NULL);
551 assert(result != NULL);
552
553 *result = SCIP_DIDNOTRUN;
554
555 /* get heuristic data */
556 heurdata = SCIPheurGetData(heur);
557 assert(heurdata != NULL);
558
559 /* do not run heuristic when there are only few binary varables */
560 if( SCIPgetNBinVars(scip) < heurdata->binvarquot * SCIPgetNVars(scip) )
561 return SCIP_OKAY;
562
563 /* calculate branching node limit for sub problem */
564 /* todo maybe treat root node differently */
565 nnodes = (SCIP_Longint) (heurdata->nodesquot * SCIPgetNNodes(scip));
566 nnodes += heurdata->nodesofs;
567
568 /* determine the node and LP iteration limit for the solve of the sub-SCIP */
569 nnodes -= heurdata->usednodes;
570 nnodes = MIN(nnodes, heurdata->maxnodes);
571
572 nlpiters = (SCIP_Longint) (heurdata->lpitersquot * SCIPgetNRootFirstLPIterations(scip));
573 nlpiters = MIN(nlpiters, heurdata->maxlpiters);
574
575 /* check whether we have enough nodes left to call subproblem solving */
576 if( nnodes < heurdata->minnodes )
577 {
578 SCIPdebugMsg(scip, "skipping proximity: nnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nnodes, heurdata->minnodes);
579 return SCIP_OKAY;
580 }
581
582 /* do not run proximity, if the problem does not have an objective function anyway */
583 if( SCIPgetNObjVars(scip) == 0 )
584 {
585 SCIPdebugMsg(scip, "skipping proximity: pure feasibility problem anyway\n");
586 return SCIP_OKAY;
587 }
588
589 do
590 {
591 /* main loop of proximity: in every iteration, a new subproblem is set up and solved until no improved solution
592 * is found or one of the heuristic limits on nodes or LP iterations is hit
593 * heuristic performs only one iteration if restart parameter is set to FALSE
594 */
595 SCIP_Longint nusednodes = 0LL;
596 SCIP_Longint nusedlpiters = 0LL;
597
598 nlpiters = MAX(nlpiters, heurdata->minlpiters);
599
600 /* define and solve the proximity subproblem */
601 SCIP_CALL( SCIPapplyProximity(scip, heur, result, heurdata->minimprove, nnodes, nlpiters, &nusednodes, &nusedlpiters, FALSE) );
602
603 /* adjust node limit and LP iteration limit for future iterations */
604 assert(nusednodes <= nnodes);
605 heurdata->usednodes += nusednodes;
606 nnodes -= nusednodes;
607
608 nlpiters -= nusedlpiters;
609 heurdata->nusedlpiters += nusedlpiters;
610
611 /* memorize if a new solution has been found in at least one iteration */
612 if( *result == SCIP_FOUNDSOL )
613 foundsol = TRUE;
614 }
615 while( *result == SCIP_FOUNDSOL && heurdata->restart && !SCIPisStopped(scip) && nnodes > 0 );
616
617 /* reset result pointer if solution has been found in previous iteration */
618 if( foundsol )
619 *result = SCIP_FOUNDSOL;
620
621 /* free the occupied memory */
622 if( heurdata->subscip != NULL )
623 {
624 /* just for testing the library method, in debug mode, we call the wrapper method for the actual delete method */
625#ifndef NDEBUG
627#else
628 SCIP_CALL( deleteSubproblem(scip, heurdata) );
629#endif
630 }
631 return SCIP_OKAY;
632}
633
634
635/*
636 * primal heuristic specific interface methods
637 */
638
639/** frees the sub-MIP created by proximity */
641 SCIP* scip /** SCIP data structure */
642 )
643{
644 SCIP_HEUR* heur;
645 SCIP_HEURDATA* heurdata;
646
647 assert(scip != NULL);
648
649 heur = SCIPfindHeur(scip, HEUR_NAME);
650 assert(heur != NULL);
651
652 heurdata = SCIPheurGetData(heur);
653 if( heurdata != NULL )
654 {
655 SCIP_CALL( deleteSubproblem(scip, heurdata) );
656 }
657
658 return SCIP_OKAY;
659}
660
661/** main procedure of the proximity heuristic, creates and solves a sub-SCIP
662 *
663 * @note The method can be applied in an iterative way, keeping the same subscip in between. If the @p freesubscip
664 * parameter is set to FALSE, the heuristic will keep the subscip data structures. Always set this parameter
665 * to TRUE, or call SCIPdeleteSubproblemProximity() afterwards.
666 */
668 SCIP* scip, /**< original SCIP data structure */
669 SCIP_HEUR* heur, /**< heuristic data structure */
670 SCIP_RESULT* result, /**< result data structure */
671 SCIP_Real minimprove, /**< factor by which proximity should at least improve the incumbent */
672 SCIP_Longint nnodes, /**< node limit for the subproblem */
673 SCIP_Longint nlpiters, /**< LP iteration limit for the subproblem */
674 SCIP_Longint* nusednodes, /**< pointer to store number of used nodes in subscip */
675 SCIP_Longint* nusedlpiters, /**< pointer to store number of used LP iterations in subscip */
676 SCIP_Bool freesubscip /**< should the created sub-MIP be freed at the end of the method? */
677 )
678{
679 SCIP* subscip; /* the subproblem created by proximity */
680 SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
681 SCIP_VAR** vars; /* original problem's variables */
682 SCIP_VAR** subvars; /* subproblem's variables */
683 SCIP_HEURDATA* heurdata; /* heuristic's private data structure */
684 SCIP_EVENTHDLR* eventhdlr; /* event handler for LP events */
685
686 SCIP_SOL* incumbent;
687 SCIP_CONS* objcons;
688 SCIP_Longint iterlim;
689
690 SCIP_Real large;
691 SCIP_Real inf;
692
693 SCIP_Real bestobj;
694 SCIP_Real objcutoff;
695 SCIP_Real lowerbound;
696
697 int nvars; /* number of original problem's variables */
698 int nfixedvars;
699 int nsubsols;
700 int solidx;
701 int i;
702
703 SCIP_Bool valid;
704 SCIP_Bool success;
705
706 assert(scip != NULL);
707 assert(heur != NULL);
708 assert(result != NULL);
709
710 assert(nnodes >= 0);
711 assert(0.0 <= minimprove && minimprove <= 1.0);
712
713 *result = SCIP_DIDNOTRUN;
714
715 /* get heuristic data */
716 heurdata = SCIPheurGetData(heur);
717 assert(heurdata != NULL);
718
719 /* only call the heuristic if we have an incumbent */
720 if( SCIPgetNSolsFound(scip) == 0 )
721 return SCIP_OKAY;
722
723 /* do not use heuristic on problems without binary variables */
724 if( SCIPgetNBinVars(scip) == 0 )
725 return SCIP_OKAY;
726
727 incumbent = SCIPgetBestSol(scip);
728 assert(incumbent != NULL);
729
730 /* make sure that the incumbent is valid for the transformed space, otherwise terminate */
731 if( SCIPsolIsOriginal(incumbent) )
732 return SCIP_OKAY;
733
734 solidx = SCIPsolGetIndex(incumbent);
735
736 if( heurdata->lastsolidx == solidx )
737 return SCIP_OKAY;
738
739 /* only call heuristic, if the best solution does not come from trivial heuristic */
740 if( SCIPsolGetHeur(incumbent) != NULL && strcmp(SCIPheurGetName(SCIPsolGetHeur(incumbent)), "trivial") == 0 )
741 return SCIP_OKAY;
742
743 /* waitingnodes parameter defines the minimum number of nodes to wait before a new incumbent is processed */
744 if( SCIPgetNNodes(scip) > 1 && SCIPgetNNodes(scip) - SCIPsolGetNodenum(incumbent) < heurdata->waitingnodes )
745 return SCIP_OKAY;
746
747 bestobj = SCIPgetSolTransObj(scip, incumbent);
748 lowerbound = SCIPgetLowerbound(scip);
749
750 /* use knowledge about integrality of objective to round up lower bound */
752 {
753 SCIPdebugMsg(scip, " Rounding up lower bound: %f --> %f \n", lowerbound, SCIPfeasCeil(scip, lowerbound));
754 lowerbound = SCIPfeasCeil(scip, lowerbound);
755 }
756
757 /* do not trigger heuristic if primal and dual bound are already close together */
758 if( SCIPisFeasLE(scip, bestobj, lowerbound) || SCIPgetGap(scip) <= heurdata->mingap )
759 return SCIP_OKAY;
760
761 /* calculate the minimum improvement for a heuristic solution in terms of the distance between incumbent objective
762 * and the lower bound */
763 if( SCIPisInfinity(scip, REALABS(lowerbound)) )
764 {
765 if( SCIPisZero(scip, bestobj) )
766 objcutoff = bestobj - 1;
767 else
768 objcutoff = (1 - minimprove) * bestobj;
769 }
770 else
771 objcutoff = minimprove * lowerbound + (1 - minimprove) * (bestobj);
772
773 /* use integrality of the objective function to round down (and thus strengthen) the objective cutoff */
775 objcutoff = SCIPfeasFloor(scip, objcutoff);
776
777 if( SCIPisFeasLT(scip, objcutoff, lowerbound) )
778 objcutoff = lowerbound;
779
780 /* exit execution if the right hand side of the objective constraint does not change (suggests that the heuristic
781 * was not successful in a previous iteration) */
782 if( heurdata->objcons != NULL && SCIPisFeasEQ(scip, SCIPgetRhsLinear(heurdata->subscip, heurdata->objcons), objcutoff) )
783 return SCIP_OKAY;
784
785 /* check whether there is enough time and memory left */
787
788 if( ! valid )
789 return SCIP_OKAY;
790
791 *result = SCIP_DIDNOTFIND;
792
793 heurdata->lastsolidx = solidx;
794
795 /* get variable data */
796 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
797
798 /* create a subscip and copy the original scip instance into it */
799 if( heurdata->subscip == NULL )
800 {
801 assert(heurdata->varmapfw == NULL);
802 assert(heurdata->objcons == NULL);
803
804 /* initialize the subproblem */
805 SCIP_CALL( SCIPcreate(&subscip) );
806
807 /* create the variable mapping hash map */
808 SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
809 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &subvars, nvars) );
810
811 /* copy complete SCIP instance */
812 valid = FALSE;
813
814 /* create a problem copy as sub SCIP */
815 SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "proximity", NULL, NULL, 0, heurdata->uselprows, TRUE,
816 &success, &valid) );
817
818 SCIPdebugMsg(scip, "Copying the SCIP instance was %s complete.\n", valid ? "" : "not ");
819
820 /* create event handler for LP events */
821 eventhdlr = NULL;
822 SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecProximity, NULL) );
823 if( eventhdlr == NULL )
824 {
825 SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
826 return SCIP_PLUGINNOTFOUND;
827 }
828
829 /* set up parameters for the copied instance */
830 SCIP_CALL( setupSubproblem(heurdata, subscip) );
831
832 /* create the objective constraint in the sub scip, first without variables and values which will be added later */
833 SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &objcons, "objbound_of_origscip", 0, NULL, NULL, -SCIPinfinity(subscip), SCIPinfinity(subscip)) );
834
835 /* determine large value to set variable bounds to, safe-guard to avoid fixings to infinite values */
836 large = SCIPinfinity(scip);
837 if( !SCIPisInfinity(scip, 0.1 / SCIPfeastol(scip)) )
838 large = 0.1 / SCIPfeastol(scip);
839 inf = SCIPinfinity(subscip);
840
841 /* get variable image and change objective to proximity function (Manhattan distance) in sub-SCIP */
842 for( i = 0; i < nvars; i++ )
843 {
844 SCIP_Real adjustedbound;
845 SCIP_Real lb;
846 SCIP_Real ub;
847
848 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
849
850 if( subvars[i] == NULL )
851 continue;
852
853 SCIP_CALL( SCIPchgVarObj(subscip, subvars[i], 0.0) );
854
855 lb = SCIPvarGetLbGlobal(subvars[i]);
856 ub = SCIPvarGetUbGlobal(subvars[i]);
857
858 /* adjust infinite bounds in order to avoid that variables with non-zero objective
859 * get fixed to infinite value in proximity subproblem
860 */
861 if( SCIPisInfinity(subscip, ub) )
862 {
863 adjustedbound = MAX(large, lb + large);
864 adjustedbound = MIN(adjustedbound, inf);
865 SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], adjustedbound) );
866 }
867 if( SCIPisInfinity(subscip, -lb) )
868 {
869 adjustedbound = MIN(-large, ub - large);
870 adjustedbound = MAX(adjustedbound, -inf);
871 SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], adjustedbound) );
872 }
873
874 /* add all nonzero objective coefficients to the objective constraint */
875 if( !SCIPisFeasZero(subscip, SCIPvarGetObj(vars[i])) )
876 {
877 SCIP_CALL( SCIPaddCoefLinear(subscip, objcons, subvars[i], SCIPvarGetObj(vars[i])) );
878 }
879 }
880
881 /* add objective constraint to the subscip */
882 SCIP_CALL( SCIPaddCons(subscip, objcons) );
883 }
884 else
885 {
886 /* the instance, event handler, hash map and variable array were already copied in a previous iteration
887 * and stored in heuristic data
888 */
889 assert(heurdata->varmapfw != NULL);
890 assert(heurdata->subvars != NULL);
891 assert(heurdata->objcons != NULL);
892
893 subscip = heurdata->subscip;
894 varmapfw = heurdata->varmapfw;
895 subvars = heurdata->subvars;
896 objcons = heurdata->objcons;
897
898 eventhdlr = SCIPfindEventhdlr(subscip, EVENTHDLR_NAME);
899 assert(eventhdlr != NULL);
900 }
901
902 SCIP_CALL( SCIPchgRhsLinear(subscip, objcons, objcutoff) );
903
904 for( i = 0; i < SCIPgetNBinVars(scip); ++i )
905 {
906 SCIP_Real solval;
907
908 if( subvars[i] == NULL )
909 continue;
910
911 /* objective coefficients are only set for binary variables of the problem */
912 assert(SCIPvarIsBinary(subvars[i]));
913
914 solval = SCIPgetSolVal(scip, incumbent, vars[i]);
915 assert(SCIPisFeasGE(scip, solval, 0.0));
916 assert(SCIPisFeasLE(scip, solval, 1.0));
917 assert(SCIPisFeasIntegral(scip, solval));
918
919 if( solval < 0.5 )
920 {
921 SCIP_CALL( SCIPchgVarObj(subscip, subvars[i], 1.0) );
922 }
923 else
924 {
925 SCIP_CALL( SCIPchgVarObj(subscip, subvars[i], -1.0) );
926 }
927 }
928
929 /* set limits for the subproblem */
930 SCIP_CALL( SCIPcopyLimits(scip, subscip) );
931 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nnodes) );
932 SCIP_CALL( SCIPsetIntParam(subscip, "limits/solutions", 1) );
933
934 /* restrict LP iterations */
935 /* todo set iterations limit depending on the number of iterations of the original problem root */
936 iterlim = nlpiters;
937 SCIP_CALL( SCIPsetLongintParam(subscip, "lp/iterlim", MAX(1, iterlim / MIN(10, nnodes))) );
938 SCIP_CALL( SCIPsetLongintParam(subscip, "lp/rootiterlim", iterlim) );
939
940 /* catch LP events of sub-SCIP */
941 SCIP_CALL( SCIPtransformProb(subscip) );
942 SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_NODESOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
943
944 SCIPstatisticMessage("solving subproblem at Node: %" SCIP_LONGINT_FORMAT " "
945 "nnodes: %" SCIP_LONGINT_FORMAT " "
946 "iterlim: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNNodes(scip), nnodes, iterlim);
947
948 /* solve the subproblem with all previously adjusted parameters */
949 nfixedvars = SCIPgetNFixedVars(subscip);
950
951 SCIP_CALL( SCIPpresolve(subscip) );
952
953 nfixedvars = SCIPgetNFixedVars(subscip) - nfixedvars;
954 assert(nfixedvars >= 0);
955 SCIPstatisticMessage("presolve fixings %d: %d\n", ++(heurdata->subprobidx), nfixedvars);
956
957 /* errors in solving the subproblem should not kill the overall solving process;
958 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
959 */
960 SCIP_CALL_ABORT( SCIPsolve(subscip) );
961
962 /* print solving statistics of subproblem if we are in SCIP's debug mode */
964 SCIPstatisticMessage("solve of subscip %d:"
965 "usednodes: %" SCIP_LONGINT_FORMAT " "
966 "lp iters: %" SCIP_LONGINT_FORMAT " "
967 "root iters: %" SCIP_LONGINT_FORMAT " "
968 "Presolving Time: %.2f\n", heurdata->subprobidx,
970
971 SCIPstatisticMessage("Solving Time %d: %.2f\n", heurdata->subprobidx, SCIPgetSolvingTime(subscip) );
972
973 /* drop LP events of sub-SCIP */
974 SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_NODESOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
975
976 /* keep track of relevant information for future runs of heuristic */
977 if( nusednodes != NULL )
978 *nusednodes = SCIPgetNNodes(subscip);
979 if( nusedlpiters != NULL )
980 *nusedlpiters = SCIPgetNLPIterations(subscip);
981
982 /* check whether a solution was found */
983 nsubsols = SCIPgetNSols(subscip);
984 incumbent = SCIPgetBestSol(subscip);
985 assert(nsubsols == 0 || incumbent != NULL);
986
987 SCIPstatisticMessage("primal bound before subproblem %d: %g\n", heurdata->subprobidx, SCIPgetPrimalbound(scip));
988 if( nsubsols > 0 )
989 {
990 /* try to translate the sub problem solution to the original scip instance */
991 success = FALSE;
992 SCIP_CALL( createNewSol(scip, subscip, subvars, heur, incumbent, heurdata->usefinallp, &success) );
993
994 if( success )
995 *result = SCIP_FOUNDSOL;
996 }
997 SCIPstatisticMessage("primal bound after subproblem %d: %g\n", heurdata->subprobidx, SCIPgetPrimalbound(scip));
998
999 /* free the transformed subproblem data */
1000 SCIP_CALL( SCIPfreeTransform(subscip) );
1001
1002 /* save subproblem in heuristic data for subsequent runs if it has been successful, otherwise free subproblem */
1003 heurdata->subscip = subscip;
1004 heurdata->varmapfw = varmapfw;
1005 heurdata->subvars = subvars;
1006 heurdata->objcons = objcons;
1007 heurdata->nsubvars = nvars;
1008
1009 /* delete the sub problem */
1010 if( freesubscip )
1011 {
1012 SCIP_CALL( deleteSubproblem(scip, heurdata) );
1013 }
1014
1015 return SCIP_OKAY;
1016}
1017
1018
1019/** creates the proximity primal heuristic and includes it in SCIP */
1021 SCIP* scip /**< SCIP data structure */
1022 )
1023{
1024 SCIP_HEURDATA* heurdata;
1025 SCIP_HEUR* heur = NULL;
1026
1027 /* create heuristic data */
1028 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1029
1030 /* include primal heuristic */
1033 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecProximity, heurdata) );
1034 assert(heur != NULL);
1035
1036 /* set non-NULL pointers to callback methods */
1037 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyProximity) );
1038 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeProximity) );
1039 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitProximity) );
1040 SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolProximity) );
1041
1042 /* add proximity primal heuristic parameters */
1043 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows",
1044 "should subproblem be constructed based on LP row information?",
1045 &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
1046
1047 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/restart",
1048 "should the heuristic immediately run again on its newly found solution?",
1049 &heurdata->restart, TRUE, DEFAULT_RESTART, NULL, NULL) );
1050
1051 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usefinallp",
1052 "should the heuristic solve a final LP in case of continuous objective variables?",
1053 &heurdata->usefinallp, TRUE, DEFAULT_USEFINALLP, NULL, NULL) );
1054
1055 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
1056 "maximum number of nodes to regard in the subproblem",
1057 &heurdata->maxnodes, TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1058
1059 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
1060 "number of nodes added to the contingent of the total nodes",
1061 &heurdata->nodesofs, TRUE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1062
1063 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
1064 "minimum number of nodes required to start the subproblem",
1065 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1066
1067 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxlpiters",
1068 "maximum number of LP iterations to be performed in the subproblem",
1069 &heurdata->maxlpiters, TRUE, DEFAULT_MAXLPITERS, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
1070
1071 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minlpiters",
1072 "minimum number of LP iterations performed in subproblem",
1073 &heurdata->minlpiters, TRUE, DEFAULT_MINLPITERS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1074
1075 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/waitingnodes",
1076 "waiting nodes since last incumbent before heuristic is executed",
1077 &heurdata->waitingnodes, TRUE, DEFAULT_WAITINGNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1078
1079 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
1080 "factor by which proximity should at least improve the incumbent",
1081 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
1082
1083 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
1084 "sub-MIP node limit w.r.t number of original nodes",
1085 &heurdata->nodesquot, TRUE, DEFAULT_NODESQUOT, 0.0, SCIPinfinity(scip), NULL, NULL) );
1086
1087 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/binvarquot",
1088 "threshold for percentage of binary variables required to start",
1089 &heurdata->binvarquot, TRUE, DEFAULT_BINVARQUOT, 0.0, 1.0, NULL, NULL) );
1090
1091 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lpitersquot",
1092 "quotient of sub-MIP LP iterations with respect to LP iterations so far",
1093 &heurdata->lpitersquot, TRUE, DEFAULT_LPITERSQUOT, 0.0, 1.0, NULL, NULL) );
1094
1095 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/mingap",
1096 "minimum primal-dual gap for which the heuristic is executed",
1097 &heurdata->mingap, TRUE, DEFAULT_MINGAP, 0.0, SCIPinfinity(scip), NULL, NULL) );
1098
1099 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct",
1100 "should uct node selection be used at the beginning of the search?",
1101 &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) );
1102
1103 return SCIP_OKAY;
1104}
Constraint handler for linear constraints in their most general form, .
#define NULL
Definition: def.h:267
#define SCIP_Longint
Definition: def.h:158
#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_CALL_ABORT(x)
Definition: def.h:353
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
#define REALABS(x)
Definition: def.h:197
#define SCIP_LONGINT_MAX
Definition: def.h:159
#define SCIP_CALL(x)
Definition: def.h:374
#define nnodes
Definition: gastrans.c:74
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3253
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 SCIPgetNObjVars(SCIP *scip)
Definition: scip_prob.c:2220
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
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2770
SCIP_Real SCIPgetObjNorm(SCIP *scip)
Definition: scip_prob.c:1641
int SCIPgetNFixedVars(SCIP *scip)
Definition: scip_prob.c:2309
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
SCIP_Bool SCIPisObjIntegral(SCIP *scip)
Definition: scip_prob.c:1562
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 SCIPdeleteSubproblemProximity(SCIP *scip)
SCIP_RETCODE SCIPapplyProximity(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real minimprove, SCIP_Longint nnodes, SCIP_Longint nlpiters, SCIP_Longint *nusednodes, SCIP_Longint *nusedlpiters, SCIP_Bool freesubscip)
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 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 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 SCIPincludeHeurProximity(SCIP *scip)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:297
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
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
SCIP_EVENTHDLR * SCIPfindEventhdlr(SCIP *scip, const char *name)
Definition: scip_event.c:234
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 SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:242
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_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip_heur.c:258
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_RETCODE SCIPchgVarLbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_lp.c:2419
SCIP_RETCODE SCIPchgVarUbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_lp.c:2451
SCIP_RETCODE SCIPstartDive(SCIP *scip)
Definition: scip_lp.c:2242
SCIP_RETCODE SCIPsolveDiveLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_lp.c:2678
SCIP_RETCODE SCIPendDive(SCIP *scip)
Definition: scip_lp.c:2291
SCIP_Bool SCIPisLPConstructed(SCIP *scip)
Definition: scip_lp.c:101
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip_nlp.c:110
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip_nodesel.c:234
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2169
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:184
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:841
SCIP_Longint SCIPsolGetNodenum(SCIP_SOL *sol)
Definition: sol.c:2784
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2070
SCIP_HEUR * SCIPsolGetHeur(SCIP_SOL *sol)
Definition: sol.c:2804
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
Definition: sol.c:2721
int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2835
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1119
SCIP_RETCODE SCIPtrySol(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:2954
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:882
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1300
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1077
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1347
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip_solve.c:222
SCIP_RETCODE SCIPpresolve(SCIP *scip)
Definition: scip_solve.c:2328
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
Definition: scip_solve.c:3344
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
Definition: scip_solve.c:3430
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2498
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
SCIP_Real SCIPgetGap(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Longint SCIPgetNRootLPIterations(SCIP *scip)
SCIP_Longint SCIPgetNRootFirstLPIterations(SCIP *scip)
SCIP_Longint SCIPgetNLPIterations(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 SCIPgetPresolvingTime(SCIP *scip)
Definition: scip_timing.c:442
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17599
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17538
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17926
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_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17610
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
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_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_var.c:4513
static SCIP_RETCODE solveLp(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
static SCIP_DECL_HEURINIT(heurInitProximity)
#define DEFAULT_RESTART
#define DEFAULT_NODESQUOT
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool usefinallp, SCIP_Bool *success)
#define DEFAULT_BINVARQUOT
#define DEFAULT_NODESOFS
#define DEFAULT_MINGAP
#define DEFAULT_USEFINALLP
#define DEFAULT_MAXNODES
static SCIP_RETCODE setupSubproblem(SCIP_HEURDATA *heurdata, SCIP *subscip)
#define HEUR_TIMING
#define DEFAULT_MINNODES
#define HEUR_FREQOFS
#define HEUR_DESC
#define DEFAULT_WAITINGNODES
#define DEFAULT_USEUCT
static SCIP_RETCODE deleteSubproblem(SCIP *scip, SCIP_HEURDATA *heurdata)
static SCIP_DECL_HEUREXITSOL(heurExitsolProximity)
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
#define DEFAULT_MINIMPROVE
#define HEUR_NAME
#define DEFAULT_USELPROWS
#define DEFAULT_LPITERSQUOT
static SCIP_DECL_HEUREXEC(heurExecProximity)
#define EVENTHDLR_DESC
#define HEUR_FREQ
#define DEFAULT_MAXLPITERS
static SCIP_DECL_HEURCOPY(heurCopyProximity)
#define HEUR_USESSUBSCIP
static SCIP_DECL_HEURFREE(heurFreeProximity)
#define EVENTHDLR_NAME
static SCIP_DECL_EVENTEXEC(eventExecProximity)
#define DEFAULT_MINLPITERS
improvement heuristic which uses an auxiliary objective instead of the original objective function wh...
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 SCIPstatisticMessage
Definition: pub_message.h:123
#define SCIPdebug(x)
Definition: pub_message.h:93
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 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_NODESOLVED
Definition: type_event.h:136
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:43
@ SCIP_LPSOLSTAT_ITERLIMIT
Definition: type_lp.h:47
@ SCIP_PARAMSETTING_OFF
Definition: type_paramset.h:63
@ SCIP_PARAMSETTING_FAST
Definition: type_paramset.h:62
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ 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
@ SCIP_VARSTATUS_COLUMN
Definition: type_var.h:51