Scippy

SCIP

Solving Constraint Integer Programs

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{
138 SCIP_HEURDATA* heurdata;
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
159 heurdata = SCIPheurGetData(heur);
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 */
165 SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, NULL, NULL, NULL) );
166 bestsol = SCIPgetBestSol(scip);
167 assert( bestsol != NULL );
168
169 /* memory allocation */
170 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nbinvars) );
171 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nbinvars) );
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{
243 SCIP_HEURDATA* heurdata;
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}*/
287 SCIP_HEURDATA* heurdata;
288
289 assert( heur != NULL );
290 assert( scip != NULL );
291
292 /* get heuristic data */
293 heurdata = SCIPheurGetData(heur);
294 assert( heurdata != NULL );
295
296 /* free heuristic data */
297 SCIPfreeBlockMemory(scip, &heurdata);
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}*/
308 SCIP_HEURDATA* heurdata;
309
310 assert( heur != NULL );
311 assert( scip != NULL );
312
313 /* get heuristic's data */
314 heurdata = SCIPheurGetData(heur);
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 */
340 SCIP_HEURDATA* heurdata;
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
353 heurdata = SCIPheurGetData(heur);
354 assert(heurdata != NULL);
355
356 /* get the data of the variables and the best solution */
357 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
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 {
372 *result = SCIP_DIDNOTRUN;
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
388 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
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) );
407 SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
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
424 SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
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 )
438 *result = SCIP_FOUNDSOL;
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
505 SCIP_HEURDATA* heurdata;
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
517 *result = SCIP_DIDNOTRUN;
518
519 /* get heuristic's data */
520 heurdata = SCIPheurGetData(heur);
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
527 *result = SCIP_DELAYED;
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
562 *result = SCIP_DIDNOTRUN;
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
590 *result = SCIP_DIDNOTFIND;
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{
613 SCIP_HEURDATA* heurdata;
614 SCIP_HEUR* heur;
615
616 /* create Localbranching primal heuristic data */
617 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
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}
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 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 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:3339
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3253
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
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:498
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
Definition: scip_message.h:78
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 SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1364
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:117
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1599
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1579
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:194
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1453
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1374
#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)
Definition: scip_solve.c:3430
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2498
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
#define EXECUTE
#define DEFAULT_NODESQUOT
#define DEFAULT_NWAITINGNODES
static SCIP_DECL_HEURCOPY(heurCopyLocalbranching)
#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
static SCIP_DECL_EVENTEXEC(eventExecLocalbranching)
#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)
static SCIP_DECL_HEURFREE(heurFreeLocalbranching)
#define DEFAULT_BESTSOLLIMIT
#define EVENTHDLR_DESC
#define HEUR_FREQ
static SCIP_DECL_HEURINIT(heurInitLocalbranching)
#define HEUR_USESSUBSCIP
#define EVENTHDLR_NAME
static SCIP_DECL_HEUREXEC(heurExecLocalbranching)
Local branching heuristic according to Fischetti and Lodi.
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_EVENTTYPE_LPSOLVED
Definition: type_event.h:101
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_DELAYED
Definition: type_result.h:43
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_FOUNDSOL
Definition: type_result.h:56
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_PLUGINNOTFOUND
Definition: type_retcode.h:54
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ 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
@ SCIP_VARTYPE_BINARY
Definition: type_var.h:62