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_rootsoldiving.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  LP diving heuristic that changes variable's objective values using root LP solution as guide
28   	 * @author Kati Wolter
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#include "blockmemshell/memory.h"
34   	#include "scip/heur_rootsoldiving.h"
35   	#include "scip/pub_heur.h"
36   	#include "scip/pub_message.h"
37   	#include "scip/pub_var.h"
38   	#include "scip/scip_branch.h"
39   	#include "scip/scip_general.h"
40   	#include "scip/scip_heur.h"
41   	#include "scip/scip_lp.h"
42   	#include "scip/scip_mem.h"
43   	#include "scip/scip_message.h"
44   	#include "scip/scip_numerics.h"
45   	#include "scip/scip_param.h"
46   	#include "scip/scip_prob.h"
47   	#include "scip/scip_sol.h"
48   	#include "scip/scip_solvingstats.h"
49   	#include "scip/scip_tree.h"
50   	#include <string.h>
51   	
52   	#define HEUR_NAME         "rootsoldiving"
53   	#define HEUR_DESC         "LP diving heuristic that changes variable's objective values using root LP solution as guide"
54   	#define HEUR_DISPCHAR     SCIP_HEURDISPCHAR_OBJDIVING
55   	#define HEUR_PRIORITY     -1005000
56   	#define HEUR_FREQ         20
57   	#define HEUR_FREQOFS       5
58   	#define HEUR_MAXDEPTH     -1
59   	#define HEUR_TIMING       SCIP_HEURTIMING_AFTERLPPLUNGE
60   	#define HEUR_USESSUBSCIP      FALSE  /**< does the heuristic use a secondary SCIP instance? */
61   	
62   	
63   	/*
64   	 * Default parameter settings
65   	 */
66   	
67   	#define DEFAULT_MINRELDEPTH         0.0 /**< minimal relative depth to start diving */
68   	#define DEFAULT_MAXRELDEPTH         1.0 /**< maximal relative depth to start diving */
69   	#define DEFAULT_MAXLPITERQUOT      0.01 /**< maximal fraction of diving LP iterations compared to node LP iterations */
70   	#define DEFAULT_MAXLPITEROFS       1000 /**< additional number of allowed LP iterations */
71   	#define DEFAULT_MAXSOLS              -1 /**< total number of feasible solutions found up to which heuristic is called
72   	                                              *   (-1: no limit) */
73   	#define DEFAULT_DEPTHFAC            0.5 /**< maximal diving depth: number of binary/integer variables times depthfac */
74   	#define DEFAULT_DEPTHFACNOSOL       2.0 /**< maximal diving depth factor if no feasible solution was found yet */
75   	
76   	#define MINLPITER                 10000 /**< minimal number of LP iterations allowed in each LP solving call */
77   	#define DEFAULT_ALPHA               0.9 /**< soft rounding factor to fade out objective coefficients */
78   	
79   	
80   	/* locally defined heuristic data */
81   	struct SCIP_HeurData
82   	{
83   	   SCIP_SOL*             sol;                /**< working solution */
84   	   SCIP_Real             minreldepth;        /**< minimal relative depth to start diving */
85   	   SCIP_Real             maxreldepth;        /**< maximal relative depth to start diving */
86   	   SCIP_Real             maxlpiterquot;      /**< maximal fraction of diving LP iterations compared to node LP iterations */
87   	   int                   maxlpiterofs;       /**< additional number of allowed LP iterations */
88   	   int                   maxsols;            /**< total number of feasible solutions found up to which heuristic is called
89   	                                              *   (-1: no limit) */
90   	   SCIP_Real             depthfac;           /**< maximal diving depth: number of binary/integer variables times depthfac */
91   	   SCIP_Real             depthfacnosol;      /**< maximal diving depth factor if no feasible solution was found yet */
92   	   SCIP_Real             alpha;              /**< soft rounding factor to fade out objective coefficients */
93   	   SCIP_Longint          nlpiterations;      /**< LP iterations used in this heuristic */
94   	   int                   nsuccess;           /**< number of runs that produced at least one feasible solution */
95   	};
96   	
97   	
98   	/*
99   	 * Callback methods
100  	 */
101  	
102  	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
103  	static
104  	SCIP_DECL_HEURCOPY(heurCopyRootsoldiving)
105  	{  /*lint --e{715}*/
106  	   assert(scip != NULL);
107  	   assert(heur != NULL);
108  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
109  	
110  	   /* call inclusion method of primal heuristic */
111  	   SCIP_CALL( SCIPincludeHeurRootsoldiving(scip) );
112  	
113  	   return SCIP_OKAY;
114  	}
115  	
116  	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
117  	static
118  	SCIP_DECL_HEURFREE(heurFreeRootsoldiving) /*lint --e{715}*/
119  	{  /*lint --e{715}*/
120  	   SCIP_HEURDATA* heurdata;
121  	
122  	   assert(heur != NULL);
123  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
124  	   assert(scip != NULL);
125  	
126  	   /* free heuristic data */
127  	   heurdata = SCIPheurGetData(heur);
128  	   assert(heurdata != NULL);
129  	   SCIPfreeBlockMemory(scip, &heurdata);
130  	   SCIPheurSetData(heur, NULL);
131  	
132  	   return SCIP_OKAY;
133  	}
134  	
135  	
136  	/** initialization method of primal heuristic (called after problem was transformed) */
137  	static
138  	SCIP_DECL_HEURINIT(heurInitRootsoldiving) /*lint --e{715}*/
139  	{  /*lint --e{715}*/
140  	   SCIP_HEURDATA* heurdata;
141  	
142  	   assert(heur != NULL);
143  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
144  	
145  	   /* get heuristic data */
146  	   heurdata = SCIPheurGetData(heur);
147  	   assert(heurdata != NULL);
148  	
149  	   /* create working solution */
150  	   SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
151  	
152  	   /* initialize data */
153  	   heurdata->nlpiterations = 0;
154  	   heurdata->nsuccess = 0;
155  	
156  	   return SCIP_OKAY;
157  	}
158  	
159  	
160  	/** deinitialization method of primal heuristic (called before transformed problem is freed) */
161  	static
162  	SCIP_DECL_HEUREXIT(heurExitRootsoldiving) /*lint --e{715}*/
163  	{  /*lint --e{715}*/
164  	   SCIP_HEURDATA* heurdata;
165  	
166  	   assert(heur != NULL);
167  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
168  	
169  	   /* get heuristic data */
170  	   heurdata = SCIPheurGetData(heur);
171  	   assert(heurdata != NULL);
172  	
173  	   /* free working solution */
174  	   SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
175  	
176  	   return SCIP_OKAY;
177  	}
178  	
179  	
180  	/** execution method of primal heuristic */
181  	static
182  	SCIP_DECL_HEUREXEC(heurExecRootsoldiving) /*lint --e{715}*/
183  	{  /*lint --e{715}*/
184  	   SCIP_HEURDATA* heurdata;
185  	   SCIP_VAR** vars;
186  	   SCIP_Real* rootsol;
187  	   SCIP_Real* objchgvals;
188  	   int* softroundings;
189  	   int* intvalrounds;
190  	   int nvars;
191  	   int nbinvars;
192  	   int nintvars;
193  	   int nlpcands;
194  	   SCIP_LPSOLSTAT lpsolstat;
195  	   SCIP_Real absstartobjval;
196  	   SCIP_Real objstep;
197  	   SCIP_Real alpha;
198  	   SCIP_Real oldobj;
199  	   SCIP_Real newobj;
200  	   SCIP_Bool lperror;
201  	   SCIP_Bool lpsolchanged;
202  	   SCIP_Longint nsolsfound;
203  	   SCIP_Longint ncalls;
204  	   SCIP_Longint nlpiterations;
205  	   SCIP_Longint maxnlpiterations;
206  	   int depth;
207  	   int maxdepth;
208  	   int maxdivedepth;
209  	   int divedepth;
210  	   int startnlpcands;
211  	   int ncycles;
212  	   int i;
213  	
214  	   assert(heur != NULL);
215  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
216  	   assert(scip != NULL);
217  	   assert(result != NULL);
218  	   assert(SCIPhasCurrentNodeLP(scip));
219  	
220  	   *result = SCIP_DELAYED;
221  	
222  	   /* do not call heuristic of node was already detected to be infeasible */
223  	   if( nodeinfeasible )
224  	      return SCIP_OKAY;
225  	
226  	   /* only call heuristic, if an optimal LP solution is at hand */
227  	   if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
228  	      return SCIP_OKAY;
229  	
230  	   /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
231  	   if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) )
232  	      return SCIP_OKAY;
233  	
234  	   /* only call heuristic, if the LP solution is basic (which allows fast resolve in diving) */
235  	   if( !SCIPisLPSolBasic(scip) )
236  	      return SCIP_OKAY;
237  	
238  	   /* don't dive two times at the same node */
239  	   if( SCIPgetLastDivenode(scip) == SCIPgetNNodes(scip) && SCIPgetDepth(scip) > 0 )
240  	      return SCIP_OKAY;
241  	
242  	   *result = SCIP_DIDNOTRUN;
243  	
244  	   /* get heuristic's data */
245  	   heurdata = SCIPheurGetData(heur);
246  	   assert(heurdata != NULL);
247  	
248  	   /* only apply heuristic, if only a few solutions have been found */
249  	   if( heurdata->maxsols >= 0 && SCIPgetNSolsFound(scip) >= heurdata->maxsols )
250  	      return SCIP_OKAY;
251  	
252  	   /* only try to dive, if we are in the correct part of the tree, given by minreldepth and maxreldepth */
253  	   depth = SCIPgetDepth(scip);
254  	   maxdepth = SCIPgetMaxDepth(scip);
255  	   maxdepth = MAX(maxdepth, 30);
256  	   if( depth < heurdata->minreldepth*maxdepth || depth > heurdata->maxreldepth*maxdepth )
257  	      return SCIP_OKAY;
258  	
259  	   /* calculate the maximal number of LP iterations until heuristic is aborted */
260  	   nlpiterations = SCIPgetNNodeLPIterations(scip);
261  	   ncalls = SCIPheurGetNCalls(heur);
262  	   nsolsfound = 10*SCIPheurGetNBestSolsFound(heur) + heurdata->nsuccess;
263  	   maxnlpiterations = (SCIP_Longint)((1.0 + 10.0*(nsolsfound+1.0)/(ncalls+1.0)) * heurdata->maxlpiterquot * nlpiterations);
264  	   maxnlpiterations += heurdata->maxlpiterofs;
265  	
266  	   /* don't try to dive, if we took too many LP iterations during diving */
267  	   if( heurdata->nlpiterations >= maxnlpiterations )
268  	      return SCIP_OKAY;
269  	
270  	   /* allow at least a certain number of LP iterations in this dive */
271  	   maxnlpiterations = MAX(maxnlpiterations, heurdata->nlpiterations + MINLPITER);
272  	
273  	   /* get number of fractional variables, that should be integral */
274  	   nlpcands = SCIPgetNLPBranchCands(scip);
275  	
276  	   /* don't try to dive, if there are no fractional variables */
277  	   if( nlpcands == 0 )
278  	      return SCIP_OKAY;
279  	
280  	   /* calculate the maximal diving depth */
281  	   nvars = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
282  	   if( SCIPgetNSolsFound(scip) == 0 )
283  	      maxdivedepth = (int)(heurdata->depthfacnosol * nvars);
284  	   else
285  	      maxdivedepth = (int)(heurdata->depthfac * nvars);
286  	   maxdivedepth = MAX(maxdivedepth, 10);
287  	
288  	   *result = SCIP_DIDNOTFIND;
289  	
290  	   /* get all variables of LP */
291  	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
292  	
293  	   /* get root solution value of all binary and integer variables */
294  	   SCIP_CALL( SCIPallocBufferArray(scip, &rootsol, nbinvars + nintvars) );
295  	   for( i = 0; i < nbinvars + nintvars; i++ )
296  	      rootsol[i] = SCIPvarGetRootSol(vars[i]);
297  	
298  	   /* get current LP objective value, and calculate length of a single step in an objective coefficient */
299  	   absstartobjval = SCIPgetLPObjval(scip);
300  	   absstartobjval = ABS(absstartobjval);
301  	   absstartobjval = MAX(absstartobjval, 1.0);
302  	   objstep = absstartobjval / 10.0;
303  	
304  	   /* initialize array storing the preferred soft rounding directions and counting the integral value rounds */
305  	   SCIP_CALL( SCIPallocBufferArray(scip, &softroundings, nbinvars + nintvars) );
306  	   BMSclearMemoryArray(softroundings, nbinvars + nintvars);
307  	   SCIP_CALL( SCIPallocBufferArray(scip, &intvalrounds, nbinvars + nintvars) );
308  	   BMSclearMemoryArray(intvalrounds, nbinvars + nintvars);
309  	
310  	   /* allocate temporary memory for buffering objective changes */
311  	   SCIP_CALL( SCIPallocBufferArray(scip, &objchgvals, nbinvars + nintvars) );
312  	
313  	   /* start diving */
314  	   SCIP_CALL( SCIPstartDive(scip) );
315  	
316  	   SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") executing rootsoldiving heuristic: depth=%d, %d fractionals, dualbound=%g, maxnlpiterations=%" SCIP_LONGINT_FORMAT ", maxdivedepth=%d, LPobj=%g, objstep=%g\n",
317  	      SCIPgetNNodes(scip), SCIPgetDepth(scip), nlpcands, SCIPgetDualbound(scip), maxnlpiterations, maxdivedepth,
318  	      SCIPgetLPObjval(scip), objstep);
319  	
320  	   lperror = FALSE;
321  	   divedepth = 0;
322  	   lpsolstat = SCIP_LPSOLSTAT_OPTIMAL;
323  	   alpha = heurdata->alpha;
324  	   ncycles = 0;
325  	   lpsolchanged = TRUE;
326  	   startnlpcands = nlpcands;
327  	   while( !lperror && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL && nlpcands > 0 && ncycles < 10
328  	      && (divedepth < 10
329  	         || nlpcands <= startnlpcands - divedepth/2
330  	         || (divedepth < maxdivedepth && heurdata->nlpiterations < maxnlpiterations))
331  	      && !SCIPisStopped(scip) )
332  	   {
333  	      SCIP_Bool success;
334  	      int hardroundingidx;
335  	      int hardroundingdir;
336  	      SCIP_Real hardroundingoldbd;
337  	      SCIP_Real hardroundingnewbd;
338  	      SCIP_Bool boundschanged;
339  	
340  	      SCIP_RETCODE retcode;
341  	
342  	      /* create solution from diving LP and try to round it */
343  	      SCIP_CALL( SCIPlinkLPSol(scip, heurdata->sol) );
344  	      SCIP_CALL( SCIProundSol(scip, heurdata->sol, &success) );
345  	
346  	      if( success )
347  	      {
348  	         SCIPdebugMsg(scip, "rootsoldiving found roundable primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol));
349  	
350  	         /* try to add solution to SCIP */
351  	         SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
352  	
353  	         /* check, if solution was feasible and good enough */
354  	         if( success )
355  	         {
356  	            SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
357  	            *result = SCIP_FOUNDSOL;
358  	         }
359  	      }
360  	
361  	      divedepth++;
362  	      hardroundingidx = -1;
363  	      hardroundingdir = 0;
364  	      hardroundingoldbd = 0.0;
365  	      hardroundingnewbd = 0.0;
366  	      boundschanged = FALSE;
367  	
368  	      SCIPdebugMsg(scip, "dive %d/%d, LP iter %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ":\n", divedepth, maxdivedepth, heurdata->nlpiterations, maxnlpiterations);
369  	
370  	      /* round solution x* from diving LP:
371  	       *   - x~_j = down(x*_j)    if x*_j is integer or binary variable and x*_j <= root solution_j
372  	       *   - x~_j = up(x*_j)      if x*_j is integer or binary variable and x*_j  > root solution_j
373  	       *   - x~_j = x*_j          if x*_j is continuous variable
374  	       * change objective function in diving LP:
375  	       *   - if x*_j is integral, or j is a continuous variable, set obj'_j = alpha * obj_j
376  	       *   - otherwise, set obj'_j = alpha * obj_j + sign(x*_j - x~_j)
377  	       */
378  	      for( i = 0; i < nbinvars + nintvars; i++ )
379  	      {
380  	         SCIP_VAR* var;
381  	         SCIP_Real solval;
382  	
383  	         var = vars[i];
384  	         oldobj = SCIPgetVarObjDive(scip, var);
385  	         newobj = oldobj;
386  	
387  	         solval =  SCIPvarGetLPSol(var);
388  	         if( SCIPisFeasIntegral(scip, solval) )
389  	         {
390  	            /* if the variable became integral after a soft rounding, count the rounds; after a while, fix it to its
391  	             * current integral value;
392  	             * otherwise, fade out the objective value
393  	             */
394  	            if( softroundings[i] != 0 && lpsolchanged )
395  	            {
396  	               intvalrounds[i]++;
397  	               if( intvalrounds[i] == 5 && SCIPgetVarLbDive(scip, var) < SCIPgetVarUbDive(scip, var) - 0.5 )
398  	               {
399  	                  /* use exact integral value, if the variable is only integral within numerical tolerances */
400  	                  solval = SCIPfloor(scip, solval+0.5);
401  	                  SCIPdebugMsg(scip, " -> fixing <%s> = %g\n", SCIPvarGetName(var), solval);
402  	                  SCIP_CALL( SCIPchgVarLbDive(scip, var, solval) );
403  	                  SCIP_CALL( SCIPchgVarUbDive(scip, var, solval) );
404  	                  boundschanged = TRUE;
405  	               }
406  	            }
407  	            else
408  	               newobj = alpha * oldobj;
409  	         }
410  	         else if( solval <= rootsol[i] )
411  	         {
412  	            /* if the variable was soft rounded most of the time downwards, round it downwards by changing the bounds;
413  	             * otherwise, apply soft rounding by changing the objective value
414  	             */
415  	            softroundings[i]--;
416  	            if( softroundings[i] <= -10 && hardroundingidx == -1 )
417  	            {
418  	               SCIPdebugMsg(scip, " -> hard rounding <%s>[%g] <= %g\n",
419  	                  SCIPvarGetName(var), solval, SCIPfeasFloor(scip, solval));
420  	               hardroundingidx = i;
421  	               hardroundingdir = -1;
422  	               hardroundingoldbd = SCIPgetVarUbDive(scip, var);
423  	               hardroundingnewbd = SCIPfeasFloor(scip, solval);
424  	               SCIP_CALL( SCIPchgVarUbDive(scip, var, hardroundingnewbd) );
425  	               boundschanged = TRUE;
426  	            }
427  	            else
428  	               newobj = alpha * oldobj + objstep;
429  	         }
430  	         else
431  	         {
432  	            /* if the variable was soft rounded most of the time upwards, round it upwards by changing the bounds;
433  	             * otherwise, apply soft rounding by changing the objective value
434  	             */
435  	            softroundings[i]++;
436  	            if( softroundings[i] >= +10 && hardroundingidx == -1 )
437  	            {
438  	               SCIPdebugMsg(scip, " -> hard rounding <%s>[%g] >= %g\n",
439  	                  SCIPvarGetName(var), solval, SCIPfeasCeil(scip, solval));
440  	               hardroundingidx = i;
441  	               hardroundingdir = +1;
442  	               hardroundingoldbd = SCIPgetVarLbDive(scip, var);
443  	               hardroundingnewbd = SCIPfeasCeil(scip, solval);
444  	               SCIP_CALL( SCIPchgVarLbDive(scip, var, hardroundingnewbd) );
445  	               boundschanged = TRUE;
446  	            }
447  	            else
448  	               newobj = alpha * oldobj - objstep;
449  	         }
450  	
451  	         /* remember the objective change */
452  	         objchgvals[i] = newobj;
453  	      }
454  	
455  	      /* apply objective changes if there was no bound change */
456  	      if( !boundschanged )
457  	      {
458  	         /* apply cached changes on integer variables */
459  	         for( i = 0; i < nbinvars + nintvars; ++i )
460  	         {
461  	            SCIP_VAR* var;
462  	
463  	            var = vars[i];
464  	            SCIPdebugMsg(scip, " -> i=%d  var <%s>, solval=%g, rootsol=%g, oldobj=%g, newobj=%g\n",
465  	               i, SCIPvarGetName(var), SCIPvarGetLPSol(var), rootsol[i], SCIPgetVarObjDive(scip, var), objchgvals[i]);
466  	
467  	            SCIP_CALL( SCIPchgVarObjDive(scip, var, objchgvals[i]) );
468  	         }
469  	
470  	         /* fade out the objective values of the continuous variables */
471  	         for( i = nbinvars + nintvars; i < nvars; i++ )
472  	         {
473  	            SCIP_VAR* var;
474  	
475  	            var = vars[i];
476  	            oldobj = SCIPgetVarObjDive(scip, var);
477  	            newobj = alpha * oldobj;
478  	
479  	            SCIPdebugMsg(scip, " -> i=%d  var <%s>, solval=%g, oldobj=%g, newobj=%g\n",
480  	               i, SCIPvarGetName(var), SCIPvarGetLPSol(var), oldobj, newobj);
481  	
482  	            SCIP_CALL( SCIPchgVarObjDive(scip, var, newobj) );
483  	         }
484  	      }
485  	
486  	   SOLVEAGAIN:
487  	      /* resolve the diving LP */
488  	      nlpiterations = SCIPgetNLPIterations(scip);
489  	
490  	      retcode = SCIPsolveDiveLP(scip,  MAX((int)(maxnlpiterations - heurdata->nlpiterations), MINLPITER), &lperror, NULL);
491  	      lpsolstat = SCIPgetLPSolstat(scip);
492  	
493  	      /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
494  	       * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
495  	       */
496  	      if( retcode != SCIP_OKAY )
497  	      {
498  	#ifndef NDEBUG
499  	         if( lpsolstat != SCIP_LPSOLSTAT_UNBOUNDEDRAY )
500  	         {
501  	            SCIP_CALL( retcode );
502  	         }
503  	#endif
504  	         SCIPwarningMessage(scip, "Error while solving LP in Rootsoldiving heuristic; LP solve terminated with code <%d>\n", retcode);
505  	         SCIPwarningMessage(scip, "This does not affect the remaining solution procedure --> continue\n");
506  	      }
507  	
508  	      if( lperror )
509  	         break;
510  	
511  	      /* update iteration count */
512  	      heurdata->nlpiterations += SCIPgetNLPIterations(scip) - nlpiterations;
513  	
514  	      /* if no LP iterations were performed, we stayed at the same solution -> count this cycling */
515  	      lpsolchanged = (SCIPgetNLPIterations(scip) != nlpiterations);
516  	      if( lpsolchanged )
517  	         ncycles = 0;
518  	      else if( !boundschanged ) /* do not count if integral variables have been fixed */
519  	         ncycles++;
520  	
521  	      /* get LP solution status and number of fractional variables, that should be integral */
522  	      if( lpsolstat == SCIP_LPSOLSTAT_INFEASIBLE && hardroundingidx != -1 )
523  	      {
524  	         SCIP_VAR* var;
525  	
526  	         var = vars[hardroundingidx];
527  	
528  	         /* round the hard rounded variable to the opposite direction and resolve the LP */
529  	         if( hardroundingdir == -1 )
530  	         {
531  	            SCIPdebugMsg(scip, " -> opposite hard rounding <%s> >= %g\n", SCIPvarGetName(var), hardroundingnewbd + 1.0);
532  	            SCIP_CALL( SCIPchgVarUbDive(scip, var, hardroundingoldbd) );
533  	            SCIP_CALL( SCIPchgVarLbDive(scip, var, hardroundingnewbd + 1.0) );
534  	         }
535  	         else
536  	         {
537  	            SCIPdebugMsg(scip, " -> opposite hard rounding <%s> <= %g\n", SCIPvarGetName(var), hardroundingnewbd - 1.0);
538  	            SCIP_CALL( SCIPchgVarLbDive(scip, var, hardroundingoldbd) );
539  	            SCIP_CALL( SCIPchgVarUbDive(scip, var, hardroundingnewbd - 1.0) );
540  	         }
541  	         hardroundingidx = -1;
542  	         goto SOLVEAGAIN;
543  	      }
544  	      if( lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
545  	         nlpcands = SCIPgetNLPBranchCands(scip);
546  	      SCIPdebugMsg(scip, "   -> lpsolstat=%d, nfrac=%d\n", lpsolstat, nlpcands);
547  	   }
548  	
549  	   SCIPdebugMsg(scip, "---> diving finished: lpsolstat = %d, depth %d/%d, LP iter %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT "\n",
550  	      lpsolstat, divedepth, maxdivedepth, heurdata->nlpiterations, maxnlpiterations);
551  	
552  	   /* check if a solution has been found */
553  	   if( nlpcands == 0 && !lperror && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
554  	   {
555  	      SCIP_Bool success;
556  	
557  	      /* create solution from diving LP */
558  	      SCIP_CALL( SCIPlinkLPSol(scip, heurdata->sol) );
559  	      SCIPdebugMsg(scip, "rootsoldiving found primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol));
560  	
561  	      /* try to add solution to SCIP */
562  	      SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
563  	
564  	      /* check, if solution was feasible and good enough */
565  	      if( success )
566  	      {
567  	         SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
568  	         *result = SCIP_FOUNDSOL;
569  	      }
570  	   }
571  	
572  	   /* end diving */
573  	   SCIP_CALL( SCIPendDive(scip) );
574  	
575  	   if( *result == SCIP_FOUNDSOL )
576  	      heurdata->nsuccess++;
577  	
578  	   /* free temporary memory */
579  	   SCIPfreeBufferArray(scip, &objchgvals);
580  	   SCIPfreeBufferArray(scip, &intvalrounds);
581  	   SCIPfreeBufferArray(scip, &softroundings);
582  	   SCIPfreeBufferArray(scip, &rootsol);
583  	
584  	   SCIPdebugMsg(scip, "rootsoldiving heuristic finished\n");
585  	
586  	   return SCIP_OKAY;
587  	}
588  	
589  	
590  	/*
591  	 * heuristic specific interface methods
592  	 */
593  	
594  	/** creates the rootsoldiving heuristic and includes it in SCIP */
595  	SCIP_RETCODE SCIPincludeHeurRootsoldiving(
596  	   SCIP*                 scip                /**< SCIP data structure */
597  	   )
598  	{
599  	   SCIP_HEURDATA* heurdata;
600  	   SCIP_HEUR* heur;
601  	
602  	   /* create Rootsoldiving primal heuristic data */
603  	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
604  	
605  	   /* include primal heuristic */
606  	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
607  	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
608  	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecRootsoldiving, heurdata) );
609  	
610  	   assert(heur != NULL);
611  	
612  	   /* set non-NULL pointers to callback methods */
613  	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyRootsoldiving) );
614  	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeRootsoldiving) );
615  	   SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitRootsoldiving) );
616  	   SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitRootsoldiving) );
617  	
618  	   /* rootsoldiving heuristic parameters */
619  	   SCIP_CALL( SCIPaddRealParam(scip,
620  	         "heuristics/rootsoldiving/minreldepth",
621  	         "minimal relative depth to start diving",
622  	         &heurdata->minreldepth, TRUE, DEFAULT_MINRELDEPTH, 0.0, 1.0, NULL, NULL) );
623  	   SCIP_CALL( SCIPaddRealParam(scip,
624  	         "heuristics/rootsoldiving/maxreldepth",
625  	         "maximal relative depth to start diving",
626  	         &heurdata->maxreldepth, TRUE, DEFAULT_MAXRELDEPTH, 0.0, 1.0, NULL, NULL) );
627  	   SCIP_CALL( SCIPaddRealParam(scip,
628  	         "heuristics/rootsoldiving/maxlpiterquot",
629  	         "maximal fraction of diving LP iterations compared to node LP iterations",
630  	         &heurdata->maxlpiterquot, FALSE, DEFAULT_MAXLPITERQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
631  	   SCIP_CALL( SCIPaddIntParam(scip,
632  	         "heuristics/rootsoldiving/maxlpiterofs",
633  	         "additional number of allowed LP iterations",
634  	         &heurdata->maxlpiterofs, FALSE, DEFAULT_MAXLPITEROFS, 0, INT_MAX, NULL, NULL) );
635  	   SCIP_CALL( SCIPaddIntParam(scip,
636  	         "heuristics/rootsoldiving/maxsols",
637  	         "total number of feasible solutions found up to which heuristic is called (-1: no limit)",
638  	         &heurdata->maxsols, TRUE, DEFAULT_MAXSOLS, -1, INT_MAX, NULL, NULL) );
639  	   SCIP_CALL( SCIPaddRealParam(scip,
640  	         "heuristics/rootsoldiving/depthfac",
641  	         "maximal diving depth: number of binary/integer variables times depthfac",
642  	         &heurdata->depthfac, TRUE, DEFAULT_DEPTHFAC, 0.0, SCIP_REAL_MAX, NULL, NULL) );
643  	   SCIP_CALL( SCIPaddRealParam(scip,
644  	         "heuristics/rootsoldiving/depthfacnosol",
645  	         "maximal diving depth factor if no feasible solution was found yet",
646  	         &heurdata->depthfacnosol, TRUE, DEFAULT_DEPTHFACNOSOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
647  	   SCIP_CALL( SCIPaddRealParam(scip,
648  	         "heuristics/rootsoldiving/alpha",
649  	         "soft rounding factor to fade out objective coefficients",
650  	         &heurdata->alpha, TRUE, DEFAULT_ALPHA, 0.0, 1.0, NULL, NULL) );
651  	
652  	   return SCIP_OKAY;
653  	}
654  	
655