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