1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 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   	
34   	#include "blockmemshell/memory.h"
35   	#include "scip/cons_linear.h"
36   	#include "scip/heuristics.h"
37   	#include "scip/heur_localbranching.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"
58   	#include "scip/scip_solvingstats.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            */
85   	
86   	/* event handler properties */
87   	#define EVENTHDLR_NAME         "Localbranching"
88   	#define EVENTHDLR_DESC         "LP event handler for " HEUR_NAME " heuristic"
89   	
90   	
91   	#define EXECUTE               0
92   	#define WAITFORNEWSOL         1
93   	
94   	
95   	/*
96   	 * Data structures
97   	 */
98   	
99   	/** primal heuristic data */
100  	struct 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  	 */
128  	
129  	/** create the extra constraint of local branching and add it to subscip */
130  	static
131  	SCIP_RETCODE addLocalbranchingConstraintAndObjcutoff(
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 */
212  	   assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
213  	
214  	   upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
215  	   if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(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 ---------------- */
238  	
239  	/** event handler execution callback to interrupt the solution process */
240  	static
241  	SCIP_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);
249  	   assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_LPSOLVED);
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));
258  	      SCIP_CALL( SCIPinterruptSolve(scip) );
259  	   }
260  	
261  	   return SCIP_OKAY;
262  	}
263  	
264  	
265  	/*
266  	 * Callback methods of primal heuristic
267  	 */
268  	
269  	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
270  	static
271  	SCIP_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 */
278  	   SCIP_CALL( SCIPincludeHeurLocalbranching(scip) );
279  	
280  	   return SCIP_OKAY;
281  	}
282  	
283  	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
284  	static
285  	SCIP_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  	
303  	
304  	/** initialization method of primal heuristic (called after problem was transformed) */
305  	static
306  	SCIP_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  	}
327  	
328  	/** setup And solve local branching subscip */
329  	static
330  	SCIP_RETCODE setupAndSolveSubscipLocalbranching(
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 */
428  	   SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) );
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  	   {
443  	   case SCIP_STATUS_OPTIMAL:
444  	   case SCIP_STATUS_BESTSOLLIMIT:
445  	      heurdata->callstatus = WAITFORNEWSOL; /* new solution will immediately be installed at next call */
446  	      SCIPdebugMsg(scip, " -> found new solution\n");
447  	      break;
448  	
449  	   case SCIP_STATUS_NODELIMIT:
450  	   case SCIP_STATUS_STALLNODELIMIT:
451  	   case SCIP_STATUS_TOTALNODELIMIT:
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  	
464  	   case SCIP_STATUS_INFEASIBLE:
465  	   case SCIP_STATUS_INFORUNBD:
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  	
473  	   case SCIP_STATUS_UNKNOWN:
474  	   case SCIP_STATUS_USERINTERRUPT:
475  	   case SCIP_STATUS_TERMINATE:
476  	   case SCIP_STATUS_TIMELIMIT:
477  	   case SCIP_STATUS_MEMLIMIT:
478  	   case SCIP_STATUS_GAPLIMIT:
479  	   case SCIP_STATUS_SOLLIMIT:
480  	   case SCIP_STATUS_RESTARTLIMIT:
481  	   case SCIP_STATUS_UNBOUNDED:
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  	
495  	
496  	/** execution method of primal heuristic */
497  	static
498  	SCIP_DECL_HEUREXEC(heurExecLocalbranching)
499  	{  /*lint --e{715}*/
500  	   SCIP_Longint maxnnodes;                   /* maximum number of subnodes                            */
501  	   SCIP_Longint nsubnodes;                   /* nodelimit for subscip                                 */
502  	
503  	   SCIP_HEURDATA* heurdata;
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  	
515  	   *result = SCIP_DIDNOTRUN;
516  	
517  	   /* get heuristic's data */
518  	   heurdata = SCIPheurGetData(heur);
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  	
525  	   *result = SCIP_DELAYED;
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  	
560  	   *result = SCIP_DIDNOTRUN;
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 */
582  	   SCIP_CALL( SCIPcheckCopyLimits(scip, &success) );
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  	
588  	   *result = SCIP_DIDNOTFIND;
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 */
607  	SCIP_RETCODE SCIPincludeHeurLocalbranching(
608  	   SCIP*                 scip                /**< SCIP data structure */
609  	   )
610  	{
611  	   SCIP_HEURDATA* heurdata;
612  	   SCIP_HEUR* heur;
613  	
614  	   /* create Localbranching primal heuristic data */
615  	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
616  	
617  	   /* include primal heuristic */
618  	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
619  	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
620  	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecLocalbranching, heurdata) );
621  	
622  	   assert(heur != NULL);
623  	
624  	   /* set non-NULL pointers to callback methods */
625  	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyLocalbranching) );
626  	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeLocalbranching) );
627  	   SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitLocalbranching) );
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  	}
676