SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
heur_localbranching.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_localbranching.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief Local branching heuristic according to Fischetti and Lodi
28 * @author Timo Berthold
29 * @author Marc Pfetsch
30 */
31
32/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33
35#include "scip/cons_linear.h"
36#include "scip/heuristics.h"
38#include "scip/pub_event.h"
39#include "scip/pub_heur.h"
40#include "scip/pub_message.h"
41#include "scip/pub_misc.h"
42#include "scip/pub_sol.h"
43#include "scip/pub_var.h"
44#include "scip/scip_branch.h"
45#include "scip/scip_cons.h"
46#include "scip/scip_copy.h"
47#include "scip/scip_event.h"
48#include "scip/scip_general.h"
49#include "scip/scip_heur.h"
50#include "scip/scip_mem.h"
51#include "scip/scip_message.h"
52#include "scip/scip_nodesel.h"
53#include "scip/scip_numerics.h"
54#include "scip/scip_param.h"
55#include "scip/scip_prob.h"
56#include "scip/scip_sol.h"
57#include "scip/scip_solve.h"
59#include <string.h>
60
61#define HEUR_NAME "localbranching"
62#define HEUR_DESC "local branching heuristic by Fischetti and Lodi"
63#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
64#define HEUR_PRIORITY -1102000
65#define HEUR_FREQ -1
66#define HEUR_FREQOFS 0
67#define HEUR_MAXDEPTH -1
68#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
69#define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
70
71#define DEFAULT_NEIGHBORHOODSIZE 18 /* radius of the incumbents neighborhood to be searched */
72#define DEFAULT_NODESOFS 1000 /* number of nodes added to the contingent of the total nodes */
73#define DEFAULT_MAXNODES 10000 /* maximum number of nodes to regard in the subproblem */
74#define DEFAULT_MINIMPROVE 0.01 /* factor by which localbranching should at least improve the incumbent */
75#define DEFAULT_MINNODES 1000 /* minimum number of nodes required to start the subproblem */
76#define DEFAULT_NODESQUOT 0.05 /* contingent of sub problem nodes in relation to original nodes */
77#define DEFAULT_LPLIMFAC 1.5 /* factor by which the limit on the number of LP depends on the node limit */
78#define DEFAULT_NWAITINGNODES 200 /* number of nodes without incumbent change that heuristic should wait */
79#define DEFAULT_USELPROWS FALSE /* should subproblem be created out of the rows in the LP rows,
80 * otherwise, the copy constructors of the constraints handlers are used */
81#define DEFAULT_COPYCUTS TRUE /* if DEFAULT_USELPROWS is FALSE, then should all active cuts from the cutpool
82 * of the original scip be copied to constraints of the subscip
83 */
84#define DEFAULT_BESTSOLLIMIT 3 /* limit on number of improving incumbent solutions in sub-CIP */
86/* event handler properties */
87#define EVENTHDLR_NAME "Localbranching"
88#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic"
90
91#define EXECUTE 0
92#define WAITFORNEWSOL 1
93
94
95/*
96 * Data structures
97 */
98
99/** primal heuristic data */
100struct SCIP_HeurData
101{
102 int nwaitingnodes; /**< number of nodes without incumbent change that heuristic should wait */
103 int nodesofs; /**< number of nodes added to the contingent of the total nodes */
104 int minnodes; /**< minimum number of nodes required to start the subproblem */
105 int maxnodes; /**< maximum number of nodes to regard in the subproblem */
106 SCIP_Longint usednodes; /**< amount of nodes local branching used during all calls */
107 SCIP_Real nodesquot; /**< contingent of sub problem nodes in relation to original nodes */
108 SCIP_Real minimprove; /**< factor by which localbranching should at least improve the incumbent */
109 SCIP_Real nodelimit; /**< the nodelimit employed in the current sub-SCIP, for the event handler*/
110 SCIP_Real lplimfac; /**< factor by which the limit on the number of LP depends on the node limit */
111 int neighborhoodsize; /**< radius of the incumbent's neighborhood to be searched */
112 int callstatus; /**< current status of localbranching heuristic */
113 SCIP_SOL* lastsol; /**< the last incumbent localbranching used as reference point */
114 int curneighborhoodsize;/**< current neighborhoodsize */
115 int curminnodes; /**< current minimal number of nodes required to start the subproblem */
116 int emptyneighborhoodsize;/**< size of neighborhood that was proven to be empty */
117 SCIP_Bool uselprows; /**< should subproblem be created out of the rows in the LP rows? */
118 SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied
119 * to constraints in subproblem?
120 */
121 int bestsollimit; /**< limit on number of improving incumbent solutions in sub-CIP */
122};
123
124
125/*
126 * Local methods
127 */
129/** create the extra constraint of local branching and add it to subscip */
130static
132 SCIP* scip, /**< SCIP data structure */
133 SCIP* subscip, /**< the subproblem created by localbranching */
134 SCIP_HEUR* heur, /**< the local branching heuristic */
135 SCIP_VAR** subvars /**< the subproblem variables */
136 )
137{
139 SCIP_CONS* cons; /* local branching constraint to create */
140 SCIP_VAR** consvars;
141 SCIP_VAR** vars;
142 SCIP_SOL* bestsol;
143
144 int nbinvars;
145 int nconsvars;
146 int i;
147 SCIP_Real lhs;
148 SCIP_Real rhs;
149 SCIP_Real* consvals;
150 char consname[SCIP_MAXSTRLEN];
151
153 SCIP_Real upperbound;
154
155 assert(scip != NULL);
156 assert(subscip != NULL);
157 assert(heur != NULL);
158
160 assert(heurdata != NULL);
161
162 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_localbranchcons", SCIPgetProbName(scip));
163
164 /* get the data of the variables and the best solution */
166 bestsol = SCIPgetBestSol(scip);
167 assert( bestsol != NULL );
168
169 /* memory allocation */
172 nconsvars = 0;
173
174 /* set initial left and right hand sides of local branching constraint */
175 lhs = (SCIP_Real)heurdata->emptyneighborhoodsize + 1.0;
176 rhs = (SCIP_Real)heurdata->curneighborhoodsize;
177
178 /* create the distance (to incumbent) function of the binary variables */
179 for( i = 0; i < nbinvars; i++ )
180 {
181 SCIP_Real solval;
182
183 if( subvars[i] == NULL )
184 continue;
185
186 solval = SCIPgetSolVal(scip, bestsol, vars[i]);
187 assert( SCIPisFeasIntegral(scip, solval) );
188
189 /* is variable i part of the binary support of bestsol? */
190 if( SCIPisFeasEQ(scip, solval, 1.0) )
191 {
192 consvals[nconsvars] = -1.0;
193 rhs -= 1.0;
194 lhs -= 1.0;
195 }
196 else
197 consvals[nconsvars] = 1.0;
198
199 consvars[nconsvars] = subvars[i];
200 assert( SCIPvarGetType(consvars[nconsvars]) == SCIP_VARTYPE_BINARY );
201
202 ++nconsvars;
203 }
204
205 /* creates localbranching constraint and adds it to subscip */
206 SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, consname, nconsvars, consvars, consvals,
207 lhs, rhs, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
208 SCIP_CALL( SCIPaddCons(subscip, cons) );
209 SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
210
211 /* add an objective cutoff */
213
214 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
216 {
217 cutoff = (1-heurdata->minimprove)*SCIPgetUpperbound(scip) + heurdata->minimprove*SCIPgetLowerbound(scip);
218 }
219 else
220 {
221 if( SCIPgetUpperbound ( scip ) >= 0 )
222 cutoff = ( 1 - heurdata->minimprove ) * SCIPgetUpperbound ( scip );
223 else
224 cutoff = ( 1 + heurdata->minimprove ) * SCIPgetUpperbound ( scip );
225 }
226 cutoff = MIN(upperbound, cutoff );
227 SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) );
228
229 /* free local memory */
230 SCIPfreeBufferArray(scip, &consvals);
231 SCIPfreeBufferArray(scip, &consvars);
232
233 return SCIP_OKAY;
234}
235
236
237/* ---------------- Callback methods of event handler ---------------- */
239/** event handler execution callback to interrupt the solution process */
240static
241SCIP_DECL_EVENTEXEC(eventExecLocalbranching)
242{
244
245 assert(eventhdlr != NULL);
246 assert(eventdata != NULL);
247 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
248 assert(event != NULL);
250
251 heurdata = (SCIP_HEURDATA*)eventdata;
252 assert(heurdata != NULL);
253
254 /* interrupt solution process of sub-SCIP */
255 if( SCIPgetNLPs(scip) > heurdata->lplimfac * heurdata->nodelimit )
256 {
257 SCIPdebugMsg(scip, "interrupt after %" SCIP_LONGINT_FORMAT " LPs\n",SCIPgetNLPs(scip));
259 }
260
261 return SCIP_OKAY;
262}
263
264
265/*
266 * Callback methods of primal heuristic
267 */
269/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
270static
271SCIP_DECL_HEURCOPY(heurCopyLocalbranching)
272{ /*lint --e{715}*/
273 assert(scip != NULL);
274 assert(heur != NULL);
275 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
276
277 /* call inclusion method of primal heuristic */
279
280 return SCIP_OKAY;
281}
283/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
284static
285SCIP_DECL_HEURFREE(heurFreeLocalbranching)
286{ /*lint --e{715}*/
288
289 assert( heur != NULL );
290 assert( scip != NULL );
291
292 /* get heuristic data */
294 assert( heurdata != NULL );
295
296 /* free heuristic data */
298 SCIPheurSetData(heur, NULL);
299
300 return SCIP_OKAY;
301}
302
304/** initialization method of primal heuristic (called after problem was transformed) */
305static
306SCIP_DECL_HEURINIT(heurInitLocalbranching)
307{ /*lint --e{715}*/
309
310 assert( heur != NULL );
311 assert( scip != NULL );
312
313 /* get heuristic's data */
315 assert( heurdata != NULL );
316
317 /* with a little abuse we initialize the heurdata as if localbranching would have finished its last step regularly */
318 heurdata->callstatus = WAITFORNEWSOL;
319 heurdata->lastsol = NULL;
320 heurdata->usednodes = 0;
321 heurdata->curneighborhoodsize = heurdata->neighborhoodsize;
322 heurdata->curminnodes = heurdata->minnodes;
323 heurdata->emptyneighborhoodsize = 0;
324
325 return SCIP_OKAY;
326}
328/** setup And solve local branching subscip */
329static
331 SCIP* scip, /**< SCIP data structure */
332 SCIP* subscip, /**< the subproblem created by localbranching */
333 SCIP_HEUR* heur, /**< localbranching heuristic */
334 SCIP_Longint nsubnodes, /**< nodelimit for subscip */
335 SCIP_RESULT* result /**< result pointer */
336 )
337{
338 SCIP_VAR** subvars; /* subproblem's variables */
339 SCIP_EVENTHDLR* eventhdlr; /* event handler for LP events */
341 SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
342 SCIP_VAR** vars;
343
344 int nvars;
345 int i;
346
347 SCIP_Bool success;
348
349 assert(scip != NULL);
350 assert(subscip != NULL);
351 assert(heur != NULL);
352
354 assert(heurdata != NULL);
355
356 /* get the data of the variables and the best solution */
358
359 /* create the variable mapping hash map */
360 SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
361 success = FALSE;
362
363 /* create a problem copy as sub SCIP */
364 SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "localbranching", NULL, NULL, 0, heurdata->uselprows,
365 heurdata->copycuts, &success, NULL) );
366
367 SCIPdebugMsg(scip, "Copying SCIP was %ssuccessful.\n", success ? "" : "not ");
368
369 /* if the subproblem could not be created, free memory and return */
370 if( !success )
371 {
373 goto TERMINATE;
374 }
375
376 /* create event handler for LP events */
377 eventhdlr = NULL;
378 SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecLocalbranching, NULL) );
379 if( eventhdlr == NULL )
380 {
381 /* free hash map */
382 SCIPhashmapFree(&varmapfw);
383
384 SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
385 return SCIP_PLUGINNOTFOUND;
386 }
387
389 for (i = 0; i < nvars; ++i)
390 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
391
392 /* free hash map */
393 SCIPhashmapFree(&varmapfw);
394
395 heurdata->nodelimit = nsubnodes;
396 SCIP_CALL( SCIPsetCommonSubscipParams(scip, subscip, nsubnodes, MAX(10, nsubnodes/10), heurdata->bestsollimit) );
397
398 /* adds the local branching constraint and the objective cutoff to the auxiliary problem */
399 SCIP_CALL( addLocalbranchingConstraintAndObjcutoff(scip, subscip, heur, subvars) );
400
401 /* catch LP events of sub-SCIP */
402 if( !heurdata->uselprows )
403 {
404 assert(eventhdlr != NULL);
405
406 SCIP_CALL( SCIPtransformProb(subscip) );
408 }
409
410 /* solve the subproblem */
411 SCIPdebugMsg(scip, "solving local branching subproblem with neighborhoodsize %d and maxnodes %" SCIP_LONGINT_FORMAT "\n",
412 heurdata->curneighborhoodsize, nsubnodes);
413
414 /* Errors in solving the subproblem should not kill the overall solving process
415 * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
416 */
417 SCIP_CALL_ABORT( SCIPsolve(subscip) );
418
419 /* drop LP events of sub-SCIP */
420 if( !heurdata->uselprows )
421 {
422 assert(eventhdlr != NULL);
423
425 }
426
427 /* print solving statistics of subproblem if we are in SCIP's debug mode */
429
430 heurdata->usednodes += SCIPgetNNodes(subscip);
431 SCIPdebugMsg(scip, "local branching used %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT " nodes\n",
432 SCIPgetNNodes(subscip), nsubnodes);
433
434 /* checks the solutions of the sub SCIP and adds them to the main SCIP if feasible */
435 SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, &success, NULL) );
436
437 if( success )
439
440 /* check the status of the sub-MIP */
441 switch( SCIPgetStatus(subscip) )
442 {
445 heurdata->callstatus = WAITFORNEWSOL; /* new solution will immediately be installed at next call */
446 SCIPdebugMsg(scip, " -> found new solution\n");
447 break;
448
452 heurdata->callstatus = EXECUTE;
453 heurdata->curneighborhoodsize = (heurdata->emptyneighborhoodsize + heurdata->curneighborhoodsize)/2;
454 heurdata->curminnodes *= 2;
455 SCIPdebugMsg(scip, " -> node limit reached: reduced neighborhood to %d, increased minnodes to %d\n",
456 heurdata->curneighborhoodsize, heurdata->curminnodes);
457 if( heurdata->curneighborhoodsize <= heurdata->emptyneighborhoodsize )
458 {
459 heurdata->callstatus = WAITFORNEWSOL;
460 SCIPdebugMsg(scip, " -> new neighborhood was already proven to be empty: wait for new solution\n");
461 }
462 break;
463
466 heurdata->emptyneighborhoodsize = heurdata->curneighborhoodsize;
467 heurdata->curneighborhoodsize += heurdata->curneighborhoodsize/2;
468 heurdata->curneighborhoodsize = MAX(heurdata->curneighborhoodsize, heurdata->emptyneighborhoodsize + 2);
469 heurdata->callstatus = EXECUTE;
470 SCIPdebugMsg(scip, " -> neighborhood is empty: increased neighborhood to %d\n", heurdata->curneighborhoodsize);
471 break;
472
484 default:
485 heurdata->callstatus = WAITFORNEWSOL;
486 SCIPdebugMsg(scip, " -> unexpected sub-MIP status <%d>: waiting for new solution\n", SCIPgetStatus(subscip));
487 break;
488 }
489
490 TERMINATE:
491 /* free subproblem */
492 SCIPfreeBufferArray(scip, &subvars);
493
494 return SCIP_OKAY;
495}
496
498/** execution method of primal heuristic */
499static
500SCIP_DECL_HEUREXEC(heurExecLocalbranching)
501{ /*lint --e{715}*/
502 SCIP_Longint maxnnodes; /* maximum number of subnodes */
503 SCIP_Longint nsubnodes; /* nodelimit for subscip */
504
506 SCIP* subscip; /* the subproblem created by localbranching */
507
508 SCIP_SOL* bestsol; /* best solution so far */
509
510 SCIP_Bool success;
511 SCIP_RETCODE retcode;
512
513 assert(heur != NULL);
514 assert(scip != NULL);
515 assert(result != NULL);
516
518
519 /* get heuristic's data */
521 assert( heurdata != NULL );
522
523 /* there should be enough binary variables that a local branching constraint makes sense */
524 if( SCIPgetNBinVars(scip) < 2*heurdata->neighborhoodsize )
525 return SCIP_OKAY;
526
528
529 /* only call heuristic, if an IP solution is at hand */
530 if( SCIPgetNSols(scip) <= 0 )
531 return SCIP_OKAY;
532
533 bestsol = SCIPgetBestSol(scip);
534 assert(bestsol != NULL);
535
536 /* only call heuristic, if the best solution comes from transformed problem */
537 if( SCIPsolIsOriginal(bestsol) )
538 return SCIP_OKAY;
539
540 /* only call heuristic, if enough nodes were processed since last incumbent */
541 if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip, bestsol) < heurdata->nwaitingnodes)
542 return SCIP_OKAY;
543
544 /* only call heuristic, if the best solution does not come from trivial heuristic */
545 if( SCIPsolGetHeur(bestsol) != NULL && strcmp(SCIPheurGetName(SCIPsolGetHeur(bestsol)), "trivial") == 0 )
546 return SCIP_OKAY;
547
548 /* reset neighborhood and minnodes, if new solution was found */
549 if( heurdata->lastsol != bestsol )
550 {
551 heurdata->curneighborhoodsize = heurdata->neighborhoodsize;
552 heurdata->curminnodes = heurdata->minnodes;
553 heurdata->emptyneighborhoodsize = 0;
554 heurdata->callstatus = EXECUTE;
555 heurdata->lastsol = bestsol;
556 }
557
558 /* if no new solution was found and local branching also seems to fail, just keep on waiting */
559 if( heurdata->callstatus == WAITFORNEWSOL )
560 return SCIP_OKAY;
561
563
564 /* calculate the maximal number of branching nodes until heuristic is aborted */
565 maxnnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
566
567 /* reward local branching if it succeeded often */
568 maxnnodes = (SCIP_Longint)(maxnnodes * (1.0 + 2.0*(SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur)+1.0)));
569 maxnnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-MIP as 100 nodes */
570 maxnnodes += heurdata->nodesofs;
571
572 /* determine the node limit for the current process */
573 nsubnodes = maxnnodes - heurdata->usednodes;
574 nsubnodes = MIN(nsubnodes, heurdata->maxnodes);
575
576 /* check whether we have enough nodes left to call sub problem solving */
577 if( nsubnodes < heurdata->curminnodes )
578 return SCIP_OKAY;
579
580 if( SCIPisStopped(scip) )
581 return SCIP_OKAY;
582
583 /* check whether there is enough time and memory left */
584 SCIP_CALL( SCIPcheckCopyLimits(scip, &success) );
585
586 /* abort if no time is left or not enough memory to create a copy of SCIP */
587 if( !success )
588 return SCIP_OKAY;
589
591
592 SCIPdebugMsg(scip, "running localbranching heuristic ...\n");
593
594 SCIP_CALL( SCIPcreate(&subscip) );
595
596 retcode = setupAndSolveSubscipLocalbranching(scip, subscip, heur, nsubnodes, result);
597
598 SCIP_CALL( SCIPfree(&subscip) );
599
600 return retcode;
601}
602
603
604/*
605 * primal heuristic specific interface methods
606 */
607
608/** creates the localbranching primal heuristic and includes it in SCIP */
610 SCIP* scip /**< SCIP data structure */
611 )
612{
614 SCIP_HEUR* heur;
615
616 /* create Localbranching primal heuristic data */
618
619 /* include primal heuristic */
622 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecLocalbranching, heurdata) );
623
624 assert(heur != NULL);
625
626 /* set non-NULL pointers to callback methods */
627 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyLocalbranching) );
628 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeLocalbranching) );
629 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitLocalbranching) );
630
631 /* add localbranching primal heuristic parameters */
632 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
633 "number of nodes added to the contingent of the total nodes",
634 &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0, INT_MAX, NULL, NULL) );
635
636 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/neighborhoodsize",
637 "radius (using Manhattan metric) of the incumbent's neighborhood to be searched",
638 &heurdata->neighborhoodsize, FALSE, DEFAULT_NEIGHBORHOODSIZE, 1, INT_MAX, NULL, NULL) );
639
640 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
641 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
642 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
643
644 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lplimfac",
645 "factor by which the limit on the number of LP depends on the node limit",
646 &heurdata->lplimfac, TRUE, DEFAULT_LPLIMFAC, 1.0, SCIP_REAL_MAX, NULL, NULL) );
647
648 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/minnodes",
649 "minimum number of nodes required to start the subproblem",
650 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0, INT_MAX, NULL, NULL) );
651
652 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
653 "maximum number of nodes to regard in the subproblem",
654 &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0, INT_MAX, NULL, NULL) );
655
656 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nwaitingnodes",
657 "number of nodes without incumbent change that heuristic should wait",
658 &heurdata->nwaitingnodes, TRUE, DEFAULT_NWAITINGNODES, 0, INT_MAX, NULL, NULL) );
659
660 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
661 "factor by which localbranching should at least improve the incumbent",
662 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
663
664 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows",
665 "should subproblem be created out of the rows in the LP rows?",
666 &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
667
668 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
669 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
670 &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
671
672 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/bestsollimit",
673 "limit on number of improving incumbent solutions in sub-CIP",
674 &heurdata->bestsollimit, FALSE, DEFAULT_BESTSOLLIMIT, -1, INT_MAX, NULL, NULL) );
675
676 return SCIP_OKAY;
677}
#define EVENTHDLR_NAME
#define EVENTHDLR_DESC
#define DEFAULT_MAXNODES
Constraint handler for linear constraints in their most general form, .
#define NULL
Definition def.h:266
#define SCIP_MAXSTRLEN
Definition def.h:287
#define SCIP_Longint
Definition def.h:157
#define SCIP_REAL_MAX
Definition def.h:173
#define SCIP_Bool
Definition def.h:91
#define MIN(x, y)
Definition def.h:242
#define SCIP_Real
Definition def.h:172
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define MAX(x, y)
Definition def.h:238
#define SCIP_CALL_ABORT(x)
Definition def.h:352
#define SCIP_LONGINT_FORMAT
Definition def.h:164
#define SCIP_CALL(x)
Definition def.h:373
#define DEFAULT_MINNODES
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPtranslateSubSols(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_Bool *success, int *solindex)
Definition scip_copy.c:1448
SCIP_RETCODE SCIPsetCommonSubscipParams(SCIP *sourcescip, SCIP *subscip, SCIP_Longint nsubnodes, SCIP_Longint nstallnodes, int bestsollimit)
Definition scip_copy.c:3339
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition scip_copy.c:3253
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
const char * SCIPgetProbName(SCIP *scip)
Definition scip_prob.c:1067
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
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:2770
int SCIPgetNBinVars(SCIP *scip)
Definition scip_prob.c:2037
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition misc.c:3111
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3264
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition misc.c:3077
#define SCIPdebugMsg
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 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 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 SCIPincludeHeurLocalbranching(SCIP *scip)
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
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 SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:178
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_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition heur.c:1599
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:162
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition heur.c:1579
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
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
#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
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition scip_sol.c:2165
int SCIPgetNSols(SCIP *scip)
Definition scip_sol.c:2066
SCIP_HEUR * SCIPsolGetHeur(SCIP_SOL *sol)
Definition sol.c:2804
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
Definition sol.c:2721
SCIP_Longint SCIPgetSolNodenum(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1509
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1213
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition scip_solve.c:223
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
SCIP_RETCODE SCIPsolve(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_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_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17583
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10880
#define HEUR_TIMING
return SCIP_OKAY
#define HEUR_FREQOFS
#define HEUR_DESC
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
#define HEUR_NAME
#define HEUR_FREQ
#define HEUR_USESSUBSCIP
#define DEFAULT_NODESQUOT
Definition heur_alns.c:91
#define DEFAULT_COPYCUTS
Definition heur_alns.c:148
#define DEFAULT_NODESOFS
Definition heur_clique.c:93
#define DEFAULT_MINIMPROVE
Definition heur_clique.c:90
#define DEFAULT_LPLIMFAC
#define DEFAULT_NWAITINGNODES
#define DEFAULT_USELPROWS
#define DEFAULT_BESTSOLLIMIT
#define DEFAULT_NEIGHBORHOODSIZE
Definition heur_dins.c:80
SCIP_Bool cutoff
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
#define EXECUTE
static SCIP_RETCODE addLocalbranchingConstraintAndObjcutoff(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars)
#define WAITFORNEWSOL
static SCIP_RETCODE setupAndSolveSubscipLocalbranching(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_Longint nsubnodes, SCIP_RESULT *result)
Local branching heuristic according to Fischetti and Lodi.
heurdata usednodes
Definition heur_locks.c:158
static SCIP_VAR ** vars
int nbinvars
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
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 memory management
public methods for message handling
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
struct SCIP_Cons SCIP_CONS
Definition type_cons.h:63
struct SCIP_Eventhdlr SCIP_EVENTHDLR
Definition type_event.h:154
struct SCIP_EventData SCIP_EVENTDATA
Definition type_event.h:173
#define SCIP_DECL_EVENTEXEC(x)
Definition type_event.h:253
#define SCIP_EVENTTYPE_LPSOLVED
Definition type_event.h:101
#define SCIP_DECL_HEURCOPY(x)
Definition type_heur.h:97
struct SCIP_HeurData SCIP_HEURDATA
Definition type_heur.h:77
struct SCIP_Heur SCIP_HEUR
Definition type_heur.h:76
#define SCIP_DECL_HEURINIT(x)
Definition type_heur.h:113
#define SCIP_DECL_HEURFREE(x)
Definition type_heur.h:105
#define SCIP_DECL_HEUREXEC(x)
Definition type_heur.h:163
struct SCIP_HashMap SCIP_HASHMAP
Definition type_misc.h:105
@ 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
enum SCIP_Retcode SCIP_RETCODE
struct Scip SCIP
Definition type_scip.h:39
struct SCIP_Sol SCIP_SOL
Definition type_sol.h:57
@ SCIP_STATUS_OPTIMAL
Definition type_stat.h:61
@ SCIP_STATUS_TOTALNODELIMIT
Definition type_stat.h:45
@ SCIP_STATUS_BESTSOLLIMIT
Definition type_stat.h:57
@ SCIP_STATUS_SOLLIMIT
Definition type_stat.h:56
@ SCIP_STATUS_UNBOUNDED
Definition type_stat.h:63
@ SCIP_STATUS_UNKNOWN
Definition type_stat.h:42
@ SCIP_STATUS_PRIMALLIMIT
Definition type_stat.h:54
@ SCIP_STATUS_GAPLIMIT
Definition type_stat.h:53
@ SCIP_STATUS_USERINTERRUPT
Definition type_stat.h:43
@ SCIP_STATUS_TERMINATE
Definition type_stat.h:65
@ SCIP_STATUS_INFORUNBD
Definition type_stat.h:64
@ SCIP_STATUS_STALLNODELIMIT
Definition type_stat.h:48
@ SCIP_STATUS_TIMELIMIT
Definition type_stat.h:51
@ SCIP_STATUS_INFEASIBLE
Definition type_stat.h:62
@ SCIP_STATUS_NODELIMIT
Definition type_stat.h:44
@ SCIP_STATUS_DUALLIMIT
Definition type_stat.h:55
@ SCIP_STATUS_MEMLIMIT
Definition type_stat.h:52
@ SCIP_STATUS_RESTARTLIMIT
Definition type_stat.h:60
struct SCIP_Var SCIP_VAR
Definition type_var.h:119
@ SCIP_VARTYPE_BINARY
Definition type_var.h:62