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
152 SCIP_Real cutoff;
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 */
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
242{
244
245 assert(eventhdlr != NULL);
246 assert(eventdata != NULL);
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
272{ /*lint --e{715}*/
273 assert(scip != NULL);
274 assert(heur != NULL);
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
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
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;
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
482 default:
483 heurdata->callstatus = WAITFORNEWSOL;
484 SCIPdebugMsg(scip, " -> unexpected sub-MIP status <%d>: waiting for new solution\n", SCIPgetStatus(subscip));
485 break;
486 }
487
488 TERMINATE:
489 /* free subproblem */
490 SCIPfreeBufferArray(scip, &subvars);
491
492 return SCIP_OKAY;
493}
494
496/** execution method of primal heuristic */
497static
499{ /*lint --e{715}*/
500 SCIP_Longint maxnnodes; /* maximum number of subnodes */
501 SCIP_Longint nsubnodes; /* nodelimit for subscip */
502
504 SCIP* subscip; /* the subproblem created by localbranching */
505
506 SCIP_SOL* bestsol; /* best solution so far */
507
508 SCIP_Bool success;
509 SCIP_RETCODE retcode;
510
511 assert(heur != NULL);
512 assert(scip != NULL);
513 assert(result != NULL);
514
516
517 /* get heuristic's data */
519 assert( heurdata != NULL );
520
521 /* there should be enough binary variables that a local branching constraint makes sense */
522 if( SCIPgetNBinVars(scip) < 2*heurdata->neighborhoodsize )
523 return SCIP_OKAY;
524
526
527 /* only call heuristic, if an IP solution is at hand */
528 if( SCIPgetNSols(scip) <= 0 )
529 return SCIP_OKAY;
530
531 bestsol = SCIPgetBestSol(scip);
532 assert(bestsol != NULL);
533
534 /* only call heuristic, if the best solution comes from transformed problem */
535 if( SCIPsolIsOriginal(bestsol) )
536 return SCIP_OKAY;
537
538 /* only call heuristic, if enough nodes were processed since last incumbent */
539 if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip, bestsol) < heurdata->nwaitingnodes)
540 return SCIP_OKAY;
541
542 /* only call heuristic, if the best solution does not come from trivial heuristic */
543 if( SCIPsolGetHeur(bestsol) != NULL && strcmp(SCIPheurGetName(SCIPsolGetHeur(bestsol)), "trivial") == 0 )
544 return SCIP_OKAY;
545
546 /* reset neighborhood and minnodes, if new solution was found */
547 if( heurdata->lastsol != bestsol )
548 {
549 heurdata->curneighborhoodsize = heurdata->neighborhoodsize;
550 heurdata->curminnodes = heurdata->minnodes;
551 heurdata->emptyneighborhoodsize = 0;
552 heurdata->callstatus = EXECUTE;
553 heurdata->lastsol = bestsol;
554 }
555
556 /* if no new solution was found and local branching also seems to fail, just keep on waiting */
557 if( heurdata->callstatus == WAITFORNEWSOL )
558 return SCIP_OKAY;
559
561
562 /* calculate the maximal number of branching nodes until heuristic is aborted */
563 maxnnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
564
565 /* reward local branching if it succeeded often */
566 maxnnodes = (SCIP_Longint)(maxnnodes * (1.0 + 2.0*(SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur)+1.0)));
567 maxnnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-MIP as 100 nodes */
568 maxnnodes += heurdata->nodesofs;
569
570 /* determine the node limit for the current process */
571 nsubnodes = maxnnodes - heurdata->usednodes;
572 nsubnodes = MIN(nsubnodes, heurdata->maxnodes);
573
574 /* check whether we have enough nodes left to call sub problem solving */
575 if( nsubnodes < heurdata->curminnodes )
576 return SCIP_OKAY;
577
578 if( SCIPisStopped(scip) )
579 return SCIP_OKAY;
580
581 /* check whether there is enough time and memory left */
583
584 /* abort if no time is left or not enough memory to create a copy of SCIP */
585 if( !success )
586 return SCIP_OKAY;
587
589
590 SCIPdebugMsg(scip, "running localbranching heuristic ...\n");
591
592 SCIP_CALL( SCIPcreate(&subscip) );
593
594 retcode = setupAndSolveSubscipLocalbranching(scip, subscip, heur, nsubnodes, result);
595
596 SCIP_CALL( SCIPfree(&subscip) );
597
598 return retcode;
599}
600
601
602/*
603 * primal heuristic specific interface methods
604 */
605
606/** creates the localbranching primal heuristic and includes it in SCIP */
608 SCIP* scip /**< SCIP data structure */
609 )
610{
612 SCIP_HEUR* heur;
613
614 /* create Localbranching primal heuristic data */
616
617 /* include primal heuristic */
621
622 assert(heur != NULL);
623
624 /* set non-NULL pointers to callback methods */
628
629 /* add localbranching primal heuristic parameters */
630 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
631 "number of nodes added to the contingent of the total nodes",
632 &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0, INT_MAX, NULL, NULL) );
633
634 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/neighborhoodsize",
635 "radius (using Manhattan metric) of the incumbent's neighborhood to be searched",
636 &heurdata->neighborhoodsize, FALSE, DEFAULT_NEIGHBORHOODSIZE, 1, INT_MAX, NULL, NULL) );
637
638 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
639 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
640 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
641
642 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lplimfac",
643 "factor by which the limit on the number of LP depends on the node limit",
644 &heurdata->lplimfac, TRUE, DEFAULT_LPLIMFAC, 1.0, SCIP_REAL_MAX, NULL, NULL) );
645
646 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/minnodes",
647 "minimum number of nodes required to start the subproblem",
648 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0, INT_MAX, NULL, NULL) );
649
650 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
651 "maximum number of nodes to regard in the subproblem",
652 &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0, INT_MAX, NULL, NULL) );
653
654 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nwaitingnodes",
655 "number of nodes without incumbent change that heuristic should wait",
656 &heurdata->nwaitingnodes, TRUE, DEFAULT_NWAITINGNODES, 0, INT_MAX, NULL, NULL) );
657
658 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
659 "factor by which localbranching should at least improve the incumbent",
660 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
661
662 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows",
663 "should subproblem be created out of the rows in the LP rows?",
664 &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
665
666 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
667 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
668 &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
669
670 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/bestsollimit",
671 "limit on number of improving incumbent solutions in sub-CIP",
672 &heurdata->bestsollimit, FALSE, DEFAULT_BESTSOLLIMIT, -1, INT_MAX, NULL, NULL) );
673
674 return SCIP_OKAY;
675}
Constraint handler for linear constraints in their most general form, .
#define NULL
Definition def.h:267
#define SCIP_MAXSTRLEN
Definition def.h:288
#define SCIP_Longint
Definition def.h:158
#define SCIP_REAL_MAX
Definition def.h:174
#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 SCIP_CALL(x)
Definition def.h:374
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:3338
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: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
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:2169
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
SCIP_Longint SCIPgetSolNodenum(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1513
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1217
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition scip_solve.c:222
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:17584
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10877
return SCIP_OKAY
SCIP_Bool cutoff
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
#define EXECUTE
#define DEFAULT_NODESQUOT
#define DEFAULT_NWAITINGNODES
#define DEFAULT_NODESOFS
#define DEFAULT_COPYCUTS
#define DEFAULT_MAXNODES
#define HEUR_TIMING
#define DEFAULT_MINNODES
#define HEUR_FREQOFS
#define HEUR_DESC
#define DEFAULT_LPLIMFAC
#define DEFAULT_NEIGHBORHOODSIZE
static SCIP_RETCODE addLocalbranchingConstraintAndObjcutoff(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars)
#define WAITFORNEWSOL
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
#define DEFAULT_MINIMPROVE
#define HEUR_NAME
#define DEFAULT_USELPROWS
static SCIP_RETCODE setupAndSolveSubscipLocalbranching(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_Longint nsubnodes, SCIP_RESULT *result)
#define DEFAULT_BESTSOLLIMIT
#define EVENTHDLR_DESC
#define HEUR_FREQ
#define HEUR_USESSUBSCIP
#define EVENTHDLR_NAME
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_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
#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
@ 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
@ 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:54
@ SCIP_STATUS_UNBOUNDED
Definition type_stat.h:63
@ SCIP_STATUS_UNKNOWN
Definition type_stat.h:42
@ 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_MEMLIMIT
Definition type_stat.h:52
@ SCIP_STATUS_RESTARTLIMIT
Definition type_stat.h:60
@ SCIP_VARTYPE_BINARY
Definition type_var.h:62