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-2014 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_localbranching.c
17  * @brief Local branching heuristic according to Fischetti and Lodi
18  * @author Timo Berthold
19  * @author Marc Pfetsch
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include <assert.h>
25 #include <string.h>
26 #include "scip/scip.h"
27 #include "scip/cons_linear.h"
28 #include "scip/scipdefplugins.h"
29 #include "scip/heur_localbranching.h"
30 #include "scip/pub_misc.h"
31 
32 #define HEUR_NAME "localbranching"
33 #define HEUR_DESC "local branching heuristic by Fischetti and Lodi"
34 #define HEUR_DISPCHAR 'L'
35 #define HEUR_PRIORITY -1102000
36 #define HEUR_FREQ -1
37 #define HEUR_FREQOFS 0
38 #define HEUR_MAXDEPTH -1
39 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
40 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
41 
42 #define DEFAULT_NEIGHBORHOODSIZE 18 /* radius of the incumbents neighborhood to be searched */
43 #define DEFAULT_NODESOFS 1000 /* number of nodes added to the contingent of the total nodes */
44 #define DEFAULT_MAXNODES 10000 /* maximum number of nodes to regard in the subproblem */
45 #define DEFAULT_MINIMPROVE 0.01 /* factor by which localbranching should at least improve the incumbent */
46 #define DEFAULT_MINNODES 1000 /* minimum number of nodes required to start the subproblem */
47 #define DEFAULT_NODESQUOT 0.05 /* contingent of sub problem nodes in relation to original nodes */
48 #define DEFAULT_LPLIMFAC 1.5 /* factor by which the limit on the number of LP depends on the node limit */
49 #define DEFAULT_NWAITINGNODES 200 /* number of nodes without incumbent change that heuristic should wait */
50 #define DEFAULT_USELPROWS FALSE /* should subproblem be created out of the rows in the LP rows,
51  * otherwise, the copy constructors of the constraints handlers are used */
52 #define DEFAULT_COPYCUTS TRUE /* if DEFAULT_USELPROWS is FALSE, then should all active cuts from the cutpool
53  * of the original scip be copied to constraints of the subscip
54  */
55 
56 /* event handler properties */
57 #define EVENTHDLR_NAME "Localbranching"
58 #define EVENTHDLR_DESC "LP event handler for "HEUR_NAME" heuristic"
59 
60 
61 #define EXECUTE 0
62 #define WAITFORNEWSOL 1
63 
64 
65 /*
66  * Data structures
67  */
68 
69 /** primal heuristic data */
70 struct SCIP_HeurData
71 {
72  int nwaitingnodes; /**< number of nodes without incumbent change that heuristic should wait */
73  int nodesofs; /**< number of nodes added to the contingent of the total nodes */
74  int minnodes; /**< minimum number of nodes required to start the subproblem */
75  int maxnodes; /**< maximum number of nodes to regard in the subproblem */
76  SCIP_Longint usednodes; /**< amount of nodes local branching used during all calls */
77  SCIP_Real nodesquot; /**< contingent of sub problem nodes in relation to original nodes */
78  SCIP_Real minimprove; /**< factor by which localbranching should at least improve the incumbent */
79  SCIP_Real nodelimit; /**< the nodelimit employed in the current sub-SCIP, for the event handler*/
80  SCIP_Real lplimfac; /**< factor by which the limit on the number of LP depends on the node limit */
81  int neighborhoodsize; /**< radius of the incumbent's neighborhood to be searched */
82  int callstatus; /**< current status of localbranching heuristic */
83  SCIP_SOL* lastsol; /**< the last incumbent localbranching used as reference point */
84  int curneighborhoodsize;/**< current neighborhoodsize */
85  int curminnodes; /**< current minimal number of nodes required to start the subproblem */
86  int emptyneighborhoodsize;/**< size of neighborhood that was proven to be empty */
87  SCIP_Bool uselprows; /**< should subproblem be created out of the rows in the LP rows? */
88  SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied
89  * to constraints in subproblem?
90  */
91 };
92 
93 
94 /*
95  * Local methods
96  */
97 
98 /** copies the problem of scip to the problem of subscip - only necessary if uselprows is false */
99 static
100 SCIP_RETCODE createSubproblem(
101  SCIP* scip, /**< SCIP data structure of the original problem */
102  SCIP* subscip, /**< SCIP data structure of the subproblem */
103  SCIP_VAR** subvars /**< variables of the subproblem */
104  )
105 {
106  SCIP_ROW** rows;
107  int nrows;
108  int i;
109 
110  /* get the rows and their number */
111  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
112 
113  for( i = 0; i < nrows; i++ )
114  {
115  SCIP_CONS* cons;
116  SCIP_VAR** consvars;
117  SCIP_COL** cols;
118  SCIP_Real constant;
119  SCIP_Real lhs;
120  SCIP_Real rhs;
121  SCIP_Real* vals;
122  int nnonz;
123  int j;
124 
125  /* ignore rows that are only locally valid */
126  if( SCIProwIsLocal(rows[i]) )
127  continue;
128 
129  /* get the row's data */
130  constant = SCIProwGetConstant(rows[i]);
131  lhs = SCIProwGetLhs(rows[i]) - constant;
132  rhs = SCIProwGetRhs(rows[i]) - constant;
133  vals = SCIProwGetVals(rows[i]);
134  nnonz = SCIProwGetNNonz(rows[i]);
135  cols = SCIProwGetCols(rows[i]);
136 
137  assert(lhs <= rhs);
138 
139  /* allocate memory array to be filled with the corresponding subproblem variables */
140  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nnonz) );
141  for( j = 0; j < nnonz; j++ )
142  consvars[j] = subvars[SCIPvarGetProbindex(SCIPcolGetVar(cols[j]))];
143 
144  /* create new constraint and add it to subscip */
145  SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, SCIProwGetName(rows[i]), nnonz, consvars, vals, lhs, rhs,
146  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
147  SCIP_CALL( SCIPaddCons(subscip, cons) );
148  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
149 
150  /* free memory */
151  SCIPfreeBufferArray(scip, &consvars);
152  }
153 
154  return SCIP_OKAY;
155 }
156 
157 /** create the extra constraint of local branching and add it to subscip */
158 static
159 SCIP_RETCODE addLocalBranchingConstraint(
160  SCIP* scip, /**< SCIP data structure of the original problem */
161  SCIP* subscip, /**< SCIP data structure of the subproblem */
162  SCIP_VAR** subvars, /**< variables of the subproblem */
163  SCIP_HEURDATA* heurdata /**< heuristic's data structure */
164  )
165 {
166  SCIP_CONS* cons; /* local branching constraint to create */
167  SCIP_VAR** consvars;
168  SCIP_VAR** vars;
169  SCIP_SOL* bestsol;
170 
171  int nbinvars;
172  int i;
173  SCIP_Real lhs;
174  SCIP_Real rhs;
175  SCIP_Real* consvals;
176  char consname[SCIP_MAXSTRLEN];
177 
178  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_localbranchcons", SCIPgetProbName(scip));
179 
180  /* get the data of the variables and the best solution */
181  SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, NULL, NULL, NULL) );
182  bestsol = SCIPgetBestSol(scip);
183  assert( bestsol != NULL );
184 
185  /* memory allocation */
186  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nbinvars) );
187  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nbinvars) );
188 
189  /* set initial left and right hand sides of local branching constraint */
190  lhs = (SCIP_Real)heurdata->emptyneighborhoodsize + 1.0;
191  rhs = (SCIP_Real)heurdata->curneighborhoodsize;
192 
193  /* create the distance (to incumbent) function of the binary variables */
194  for( i = 0; i < nbinvars; i++ )
195  {
196  SCIP_Real solval;
197 
198  solval = SCIPgetSolVal(scip, bestsol, vars[i]);
199  assert( SCIPisFeasIntegral(scip,solval) );
200 
201  /* is variable i part of the binary support of bestsol? */
202  if( SCIPisFeasEQ(scip,solval,1.0) )
203  {
204  consvals[i] = -1.0;
205  rhs -= 1.0;
206  lhs -= 1.0;
207  }
208  else
209  consvals[i] = 1.0;
210  consvars[i] = subvars[i];
211  assert( SCIPvarGetType(consvars[i]) == SCIP_VARTYPE_BINARY );
212  }
213 
214  /* creates localbranching constraint and adds it to subscip */
215  SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, consname, nbinvars, consvars, consvals,
216  lhs, rhs, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
217  SCIP_CALL( SCIPaddCons(subscip, cons) );
218  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
219 
220  /* free local memory */
221  SCIPfreeBufferArray(scip, &consvals);
222  SCIPfreeBufferArray(scip, &consvars);
223 
224  return SCIP_OKAY;
225 }
226 
227 
228 /** creates a new solution for the original problem by copying the solution of the subproblem */
229 static
230 SCIP_RETCODE createNewSol(
231  SCIP* scip, /**< SCIP data structure of the original problem */
232  SCIP* subscip, /**< SCIP data structure of the subproblem */
233  SCIP_VAR** subvars, /**< the variables of the subproblem */
234  SCIP_HEUR* heur, /**< the Localbranching heuristic */
235  SCIP_SOL* subsol, /**< solution of the subproblem */
236  SCIP_Bool* success /**< pointer to store, whether new solution was found */
237  )
238 {
239  SCIP_VAR** vars;
240  int nvars;
241  SCIP_SOL* newsol;
242  SCIP_Real* subsolvals;
243 
244  assert( scip != NULL );
245  assert( subscip != NULL );
246  assert( subvars != NULL );
247  assert( subsol != NULL );
248 
249  /* copy the solution */
250  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
251  /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
252  * since constraint copying may have required the copy of variables that are fixed in the main SCIP
253  */
254  assert(nvars <= SCIPgetNOrigVars(subscip));
255 
256  SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
257 
258  /* copy the solution */
259  SCIP_CALL( SCIPgetSolVals(subscip, subsol, nvars, subvars, subsolvals) );
260 
261  /* create new solution for the original problem */
262  SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
263  SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
264 
265  SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, TRUE, TRUE, TRUE, success) );
266 
267  SCIPfreeBufferArray(scip, &subsolvals);
268 
269  return SCIP_OKAY;
270 }
271 
272 
273 /* ---------------- Callback methods of event handler ---------------- */
274 
275 /* exec the event handler
276  *
277  * we interrupt the solution process
278  */
279 static
280 SCIP_DECL_EVENTEXEC(eventExecLocalbranching)
281 {
282  SCIP_HEURDATA* heurdata;
283 
284  assert(eventhdlr != NULL);
285  assert(eventdata != NULL);
286  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
287  assert(event != NULL);
288  assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_LPSOLVED);
289 
290  heurdata = (SCIP_HEURDATA*)eventdata;
291  assert(heurdata != NULL);
292 
293  /* interrupt solution process of sub-SCIP */
294  if( SCIPgetNLPs(scip) > heurdata->lplimfac * heurdata->nodelimit )
295  {
296  SCIPdebugMessage("interrupt after %"SCIP_LONGINT_FORMAT" LPs\n",SCIPgetNLPs(scip));
297  SCIP_CALL( SCIPinterruptSolve(scip) );
298  }
299 
300  return SCIP_OKAY;
301 }
302 
303 
304 /*
305  * Callback methods of primal heuristic
306  */
307 
308 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
309 static
310 SCIP_DECL_HEURCOPY(heurCopyLocalbranching)
311 { /*lint --e{715}*/
312  assert(scip != NULL);
313  assert(heur != NULL);
314  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
315 
316  /* call inclusion method of primal heuristic */
317  SCIP_CALL( SCIPincludeHeurLocalbranching(scip) );
318 
319  return SCIP_OKAY;
320 }
321 
322 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
323 static
324 SCIP_DECL_HEURFREE(heurFreeLocalbranching)
325 { /*lint --e{715}*/
326  SCIP_HEURDATA* heurdata;
327 
328  assert( heur != NULL );
329  assert( scip != NULL );
330 
331  /* get heuristic data */
332  heurdata = SCIPheurGetData(heur);
333  assert( heurdata != NULL );
334 
335  /* free heuristic data */
336  SCIPfreeMemory(scip, &heurdata);
337  SCIPheurSetData(heur, NULL);
338 
339  return SCIP_OKAY;
340 }
341 
342 
343 /** initialization method of primal heuristic (called after problem was transformed) */
344 static
345 SCIP_DECL_HEURINIT(heurInitLocalbranching)
346 { /*lint --e{715}*/
347  SCIP_HEURDATA* heurdata;
348 
349  assert( heur != NULL );
350  assert( scip != NULL );
351 
352  /* get heuristic's data */
353  heurdata = SCIPheurGetData(heur);
354  assert( heurdata != NULL );
355 
356  /* with a little abuse we initialize the heurdata as if localbranching would have finished its last step regularly */
357  heurdata->callstatus = WAITFORNEWSOL;
358  heurdata->lastsol = NULL;
359  heurdata->usednodes = 0;
360  heurdata->curneighborhoodsize = heurdata->neighborhoodsize;
361  heurdata->curminnodes = heurdata->minnodes;
362  heurdata->emptyneighborhoodsize = 0;
363 
364  return SCIP_OKAY;
365 }
366 
367 
368 /** execution method of primal heuristic */
369 static
370 SCIP_DECL_HEUREXEC(heurExecLocalbranching)
371 { /*lint --e{715}*/
372  SCIP_Longint maxnnodes; /* maximum number of subnodes */
373  SCIP_Longint nsubnodes; /* nodelimit for subscip */
374 
375  SCIP_HEURDATA* heurdata;
376  SCIP* subscip; /* the subproblem created by localbranching */
377  SCIP_VAR** subvars; /* subproblem's variables */
378  SCIP_SOL* bestsol; /* best solution so far */
379  SCIP_EVENTHDLR* eventhdlr; /* event handler for LP events */
380 
381  SCIP_Real timelimit; /* timelimit for subscip (equals remaining time of scip) */
382  SCIP_Real cutoff; /* objective cutoff for the subproblem */
383  SCIP_Real upperbound;
384  SCIP_Real memorylimit;
385 
386  SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
387  SCIP_VAR** vars;
388 
389  int nvars;
390  int i;
391 
392  SCIP_Bool success;
393 
394  SCIP_RETCODE retcode;
395 
396  assert(heur != NULL);
397  assert(scip != NULL);
398  assert(result != NULL);
399 
400  *result = SCIP_DIDNOTRUN;
401 
402  /* get heuristic's data */
403  heurdata = SCIPheurGetData(heur);
404  assert( heurdata != NULL );
405 
406  /* there should be enough binary variables that a local branching constraint makes sense */
407  if( SCIPgetNBinVars(scip) < 2*heurdata->neighborhoodsize )
408  return SCIP_OKAY;
409 
410  *result = SCIP_DELAYED;
411 
412  /* only call heuristic, if an IP solution is at hand */
413  if( SCIPgetNSols(scip) <= 0 )
414  return SCIP_OKAY;
415 
416  bestsol = SCIPgetBestSol(scip);
417  assert(bestsol != NULL);
418 
419  /* only call heuristic, if the best solution comes from transformed problem */
420  if( SCIPsolIsOriginal(bestsol) )
421  return SCIP_OKAY;
422 
423  /* only call heuristic, if enough nodes were processed since last incumbent */
424  if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip, bestsol) < heurdata->nwaitingnodes)
425  return SCIP_OKAY;
426 
427  /* only call heuristic, if the best solution does not come from trivial heuristic */
428  if( SCIPsolGetHeur(bestsol) != NULL && strcmp(SCIPheurGetName(SCIPsolGetHeur(bestsol)), "trivial") == 0 )
429  return SCIP_OKAY;
430 
431  /* reset neighborhood and minnodes, if new solution was found */
432  if( heurdata->lastsol != bestsol )
433  {
434  heurdata->curneighborhoodsize = heurdata->neighborhoodsize;
435  heurdata->curminnodes = heurdata->minnodes;
436  heurdata->emptyneighborhoodsize = 0;
437  heurdata->callstatus = EXECUTE;
438  heurdata->lastsol = bestsol;
439  }
440 
441  /* if no new solution was found and local branching also seems to fail, just keep on waiting */
442  if( heurdata->callstatus == WAITFORNEWSOL )
443  return SCIP_OKAY;
444 
445  *result = SCIP_DIDNOTRUN;
446 
447  /* calculate the maximal number of branching nodes until heuristic is aborted */
448  maxnnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
449 
450  /* reward local branching if it succeeded often */
451  maxnnodes = (SCIP_Longint)(maxnnodes * (1.0 + 2.0*(SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur)+1.0)));
452  maxnnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-MIP as 100 nodes */
453  maxnnodes += heurdata->nodesofs;
454 
455  /* determine the node limit for the current process */
456  nsubnodes = maxnnodes - heurdata->usednodes;
457  nsubnodes = MIN(nsubnodes, heurdata->maxnodes);
458 
459  /* check whether we have enough nodes left to call sub problem solving */
460  if( nsubnodes < heurdata->curminnodes )
461  return SCIP_OKAY;
462 
463  if( SCIPisStopped(scip) )
464  return SCIP_OKAY;
465 
466  *result = SCIP_DIDNOTFIND;
467 
468  SCIPdebugMessage("running localbranching heuristic ...\n");
469 
470  /* get the data of the variables and the best solution */
471  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
472 
473  /* initializing the subproblem */
474  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
475  SCIP_CALL( SCIPcreate(&subscip) );
476 
477  /* create the variable mapping hash map */
478  SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), SCIPcalcHashtableSize(5 * nvars)) );
479  success = FALSE;
480  eventhdlr = NULL;
481 
482  if( heurdata->uselprows )
483  {
484  char probname[SCIP_MAXSTRLEN];
485 
486  /* copy all plugins */
487  SCIP_CALL( SCIPincludeDefaultPlugins(subscip) );
488 
489  /* get name of the original problem and add the string "_localbranchsub" */
490  (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_localbranchsub", SCIPgetProbName(scip));
491 
492  /* create the subproblem */
493  SCIP_CALL( SCIPcreateProb(subscip, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
494 
495  /* copy all variables */
496  SCIP_CALL( SCIPcopyVars(scip, subscip, varmapfw, NULL, TRUE) );
497  }
498  else
499  {
500  SCIP_CALL( SCIPcopy(scip, subscip, varmapfw, NULL, "localbranchsub", TRUE, FALSE, TRUE, &success) );
501 
502  if( heurdata->copycuts )
503  {
504  /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
505  SCIP_CALL( SCIPcopyCuts(scip, subscip, varmapfw, NULL, TRUE, NULL) );
506  }
507 
508  /* create event handler for LP events */
509  SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecLocalbranching, NULL) );
510  if( eventhdlr == NULL )
511  {
512  SCIPerrorMessage("event handler for "HEUR_NAME" heuristic not found.\n");
513  return SCIP_PLUGINNOTFOUND;
514  }
515  }
516  SCIPdebugMessage("Copying the plugins was %ssuccessful.\n", success ? "" : "not ");
517 
518  for (i = 0; i < nvars; ++i)
519  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
520 
521  /* free hash map */
522  SCIPhashmapFree(&varmapfw);
523 
524  /* if the subproblem could not be created, free memory and return */
525  if( !success )
526  {
527  *result = SCIP_DIDNOTRUN;
528  goto TERMINATE;
529  }
530 
531  /* do not abort subproblem on CTRL-C */
532  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
533 
534 #ifndef SCIP_DEBUG
535  /* disable output to console */
536  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
537 #endif
538 
539  /* check whether there is enough time and memory left */
540  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
541  if( !SCIPisInfinity(scip, timelimit) )
542  timelimit -= SCIPgetSolvingTime(scip);
543  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
544 
545  /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
546  if( !SCIPisInfinity(scip, memorylimit) )
547  {
548  memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
549  memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
550  }
551 
552  /* abort if no time is left or not enough memory to create a copy of SCIP, including external memory usage */
553  if( timelimit <= 0.0 || memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 )
554  goto TERMINATE;
555 
556  /* set limits for the subproblem */
557  heurdata->nodelimit = nsubnodes;
558  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nsubnodes) );
559  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", MAX(10, nsubnodes/10)) );
560  SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", 3) );
561  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
562  SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
563 
564  /* forbid recursive call of heuristics and separators solving subMIPs */
565  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
566 
567  /* disable cutting plane separation */
568  SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
569 
570  /* disable expensive presolving */
571  SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
572 
573  /* use best estimate node selection */
574  if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
575  {
576  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
577  }
578 
579  /* use inference branching */
580  if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
581  {
582  SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
583  }
584 
585  /* disable conflict analysis */
586  if( !SCIPisParamFixed(subscip, "conflict/useprop") )
587  {
588  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/useprop", FALSE) );
589  }
590  if( !SCIPisParamFixed(subscip, "conflict/useinflp") )
591  {
592  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/useinflp", FALSE) );
593  }
594  if( !SCIPisParamFixed(subscip, "conflict/useboundlp") )
595  {
596  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/useboundlp", FALSE) );
597  }
598  if( !SCIPisParamFixed(subscip, "conflict/usesb") )
599  {
600  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/usesb", FALSE) );
601  }
602  if( !SCIPisParamFixed(subscip, "conflict/usepseudo") )
603  {
604  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/usepseudo", FALSE) );
605  }
606 
607  /* employ a limit on the number of enforcement rounds in the quadratic constraint handler; this fixes the issue that
608  * sometimes the quadratic constraint handler needs hundreds or thousands of enforcement rounds to determine the
609  * feasibility status of a single node without fractional branching candidates by separation (namely for uflquad
610  * instances); however, the solution status of the sub-SCIP might get corrupted by this; hence no deductions shall be
611  * made for the original SCIP
612  */
613  if( SCIPfindConshdlr(subscip, "quadratic") != NULL && !SCIPisParamFixed(subscip, "constraints/quadratic/enfolplimit") )
614  {
615  SCIP_CALL( SCIPsetIntParam(subscip, "constraints/quadratic/enfolplimit", 500) );
616  }
617 
618  /* copy the original problem and add the local branching constraint */
619  if( heurdata->uselprows )
620  {
621  SCIP_CALL( createSubproblem(scip, subscip, subvars) );
622  }
623  SCIP_CALL( addLocalBranchingConstraint(scip, subscip, subvars, heurdata) );
624 
625  /* add an objective cutoff */
626  cutoff = SCIPinfinity(scip);
627  assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
628 
629  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
630  if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(scip)) )
631  {
632  cutoff = (1-heurdata->minimprove)*SCIPgetUpperbound(scip) + heurdata->minimprove*SCIPgetLowerbound(scip);
633  }
634  else
635  {
636  if( SCIPgetUpperbound ( scip ) >= 0 )
637  cutoff = ( 1 - heurdata->minimprove ) * SCIPgetUpperbound ( scip );
638  else
639  cutoff = ( 1 + heurdata->minimprove ) * SCIPgetUpperbound ( scip );
640  }
641  cutoff = MIN(upperbound, cutoff );
642  SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) );
643 
644  /* catch LP events of sub-SCIP */
645  if( !heurdata->uselprows )
646  {
647  assert(eventhdlr != NULL);
648 
649  SCIP_CALL( SCIPtransformProb(subscip) );
650  SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
651  }
652 
653  /* solve the subproblem */
654  SCIPdebugMessage("solving local branching subproblem with neighborhoodsize %d and maxnodes %"SCIP_LONGINT_FORMAT"\n",
655  heurdata->curneighborhoodsize, nsubnodes);
656  retcode = SCIPsolve(subscip);
657 
658  /* drop LP events of sub-SCIP */
659  if( !heurdata->uselprows )
660  {
661  assert(eventhdlr != NULL);
662 
663  SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
664  }
665 
666  /* Errors in solving the subproblem should not kill the overall solving process
667  * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
668  */
669  if( retcode != SCIP_OKAY )
670  {
671 #ifndef NDEBUG
672  SCIP_CALL( retcode );
673 #endif
674  SCIPwarningMessage(scip, "Error while solving subproblem in local branching heuristic; sub-SCIP terminated with code <%d>\n",retcode);
675  }
676 
677  /* print solving statistics of subproblem if we are in SCIP's debug mode */
678  SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) );
679 
680  heurdata->usednodes += SCIPgetNNodes(subscip);
681  SCIPdebugMessage("local branching used %"SCIP_LONGINT_FORMAT"/%"SCIP_LONGINT_FORMAT" nodes\n",
682  SCIPgetNNodes(subscip), nsubnodes);
683 
684  /* check, whether a solution was found */
685  if( SCIPgetNSols(subscip) > 0 )
686  {
687  SCIP_SOL** subsols;
688  int nsubsols;
689 
690  /* check, whether a solution was found;
691  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
692  */
693  nsubsols = SCIPgetNSols(subscip);
694  subsols = SCIPgetSols(subscip);
695  success = FALSE;
696  for( i = 0; i < nsubsols && !success; ++i )
697  {
698  SCIP_CALL( createNewSol(scip, subscip, subvars, heur, subsols[i], &success) );
699  }
700  if( success )
701  {
702  SCIPdebugMessage("-> accepted solution of value %g\n", SCIPgetSolOrigObj(subscip, subsols[i]));
703  *result = SCIP_FOUNDSOL;
704  }
705  }
706 
707  /* check the status of the sub-MIP */
708  switch( SCIPgetStatus(subscip) )
709  {
710  case SCIP_STATUS_OPTIMAL:
711  case SCIP_STATUS_BESTSOLLIMIT:
712  heurdata->callstatus = WAITFORNEWSOL; /* new solution will immediately be installed at next call */
713  SCIPdebugMessage(" -> found new solution\n");
714  break;
715 
716  case SCIP_STATUS_NODELIMIT:
717  case SCIP_STATUS_STALLNODELIMIT:
718  case SCIP_STATUS_TOTALNODELIMIT:
719  heurdata->callstatus = EXECUTE;
720  heurdata->curneighborhoodsize = (heurdata->emptyneighborhoodsize + heurdata->curneighborhoodsize)/2;
721  heurdata->curminnodes *= 2;
722  SCIPdebugMessage(" -> node limit reached: reduced neighborhood to %d, increased minnodes to %d\n",
723  heurdata->curneighborhoodsize, heurdata->curminnodes);
724  if( heurdata->curneighborhoodsize <= heurdata->emptyneighborhoodsize )
725  {
726  heurdata->callstatus = WAITFORNEWSOL;
727  SCIPdebugMessage(" -> new neighborhood was already proven to be empty: wait for new solution\n");
728  }
729  break;
730 
731  case SCIP_STATUS_INFEASIBLE:
732  case SCIP_STATUS_INFORUNBD:
733  heurdata->emptyneighborhoodsize = heurdata->curneighborhoodsize;
734  heurdata->curneighborhoodsize += heurdata->curneighborhoodsize/2;
735  heurdata->curneighborhoodsize = MAX(heurdata->curneighborhoodsize, heurdata->emptyneighborhoodsize + 2);
736  heurdata->callstatus = EXECUTE;
737  SCIPdebugMessage(" -> neighborhood is empty: increased neighborhood to %d\n", heurdata->curneighborhoodsize);
738  break;
739 
740  case SCIP_STATUS_UNKNOWN:
741  case SCIP_STATUS_USERINTERRUPT:
742  case SCIP_STATUS_TIMELIMIT:
743  case SCIP_STATUS_MEMLIMIT:
744  case SCIP_STATUS_GAPLIMIT:
745  case SCIP_STATUS_SOLLIMIT:
746  case SCIP_STATUS_UNBOUNDED:
747  default:
748  heurdata->callstatus = WAITFORNEWSOL;
749  SCIPdebugMessage(" -> unexpected sub-MIP status <%d>: waiting for new solution\n", SCIPgetStatus(subscip));
750  break;
751  }
752 
753  TERMINATE:
754  /* free subproblem */
755  SCIPfreeBufferArray(scip, &subvars);
756  SCIP_CALL( SCIPfree(&subscip) );
757 
758  return SCIP_OKAY;
759 }
760 
761 
762 /*
763  * primal heuristic specific interface methods
764  */
765 
766 /** creates the localbranching primal heuristic and includes it in SCIP */
767 SCIP_RETCODE SCIPincludeHeurLocalbranching(
768  SCIP* scip /**< SCIP data structure */
769  )
770 {
771  SCIP_HEURDATA* heurdata;
772 
773  SCIP_HEUR* heur;
774 
775  /* create Localbranching primal heuristic data */
776  SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
777 
778  /* include primal heuristic */
779  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
780  HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
781  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecLocalbranching, heurdata) );
782 
783  assert(heur != NULL);
784 
785  /* set non-NULL pointers to callback methods */
786  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyLocalbranching) );
787  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeLocalbranching) );
788  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitLocalbranching) );
789 
790  /* add localbranching primal heuristic parameters */
791  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/nodesofs",
792  "number of nodes added to the contingent of the total nodes",
793  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0, INT_MAX, NULL, NULL) );
794 
795  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/neighborhoodsize",
796  "radius (using Manhattan metric) of the incumbent's neighborhood to be searched",
797  &heurdata->neighborhoodsize, FALSE, DEFAULT_NEIGHBORHOODSIZE, 1, INT_MAX, NULL, NULL) );
798 
799  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/nodesquot",
800  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
801  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
802 
803  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/lplimfac",
804  "factor by which the limit on the number of LP depends on the node limit",
805  &heurdata->lplimfac, TRUE, DEFAULT_LPLIMFAC, 1.0, SCIP_REAL_MAX, NULL, NULL) );
806 
807  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/minnodes",
808  "minimum number of nodes required to start the subproblem",
809  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0, INT_MAX, NULL, NULL) );
810 
811  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/maxnodes",
812  "maximum number of nodes to regard in the subproblem",
813  &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0, INT_MAX, NULL, NULL) );
814 
815  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/nwaitingnodes",
816  "number of nodes without incumbent change that heuristic should wait",
817  &heurdata->nwaitingnodes, TRUE, DEFAULT_NWAITINGNODES, 0, INT_MAX, NULL, NULL) );
818 
819  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/minimprove",
820  "factor by which localbranching should at least improve the incumbent",
821  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
822 
823  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/uselprows",
824  "should subproblem be created out of the rows in the LP rows?",
825  &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
826 
827  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/copycuts",
828  "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
829  &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
830 
831  return SCIP_OKAY;
832 }
833