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_intdiving.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  LP diving heuristic that fixes variables with integral LP value
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_intdiving.h"
35   	#include "scip/pub_heur.h"
36   	#include "scip/pub_lp.h"
37   	#include "scip/pub_message.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_probing.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             "intdiving"
56   	#define HEUR_DESC             "LP diving heuristic that fixes binary variables with large LP value to one"
57   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_DIVING
58   	#define HEUR_PRIORITY         -1003500
59   	#define HEUR_FREQ             -1
60   	#define HEUR_FREQOFS          9
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.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */
73   	#define DEFAULT_MAXLPITEROFS       1000 /**< additional number of allowed LP iterations */
74   	#define DEFAULT_MAXDIVEUBQUOT       0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
75   	                                         *   where diving is performed (0.0: no limit) */
76   	#define DEFAULT_MAXDIVEAVGQUOT      0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
77   	                                         *   where diving is performed (0.0: no limit) */
78   	#define DEFAULT_MAXDIVEUBQUOTNOSOL  0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
79   	#define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
80   	#define DEFAULT_BACKTRACK          TRUE /**< use one level of backtracking if infeasibility is encountered? */
81   	
82   	#define MINLPITER                 10000 /**< minimal number of LP iterations allowed in each LP solving call */
83   	
84   	
85   	/* locally defined heuristic data */
86   	struct SCIP_HeurData
87   	{
88   	   SCIP_SOL*             sol;                /**< working solution */
89   	   SCIP_Real             minreldepth;        /**< minimal relative depth to start diving */
90   	   SCIP_Real             maxreldepth;        /**< maximal relative depth to start diving */
91   	   SCIP_Real             maxlpiterquot;      /**< maximal fraction of diving LP iterations compared to node LP iterations */
92   	   int                   maxlpiterofs;       /**< additional number of allowed LP iterations */
93   	   SCIP_Real             maxdiveubquot;      /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
94   	                                              *   where diving is performed (0.0: no limit) */
95   	   SCIP_Real             maxdiveavgquot;     /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
96   	                                              *   where diving is performed (0.0: no limit) */
97   	   SCIP_Real             maxdiveubquotnosol; /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
98   	   SCIP_Real             maxdiveavgquotnosol;/**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
99   	   SCIP_Bool             backtrack;          /**< use one level of backtracking if infeasibility is encountered? */
100  	   SCIP_Longint          nlpiterations;      /**< LP iterations used in this heuristic */
101  	   int                   nsuccess;           /**< number of runs that produced at least one feasible solution */
102  	};
103  	
104  	
105  	/*
106  	 * local methods
107  	 */
108  	
109  	
110  	/*
111  	 * Callback methods
112  	 */
113  	
114  	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
115  	static
116  	SCIP_DECL_HEURCOPY(heurCopyIntdiving)
117  	{  /*lint --e{715}*/
118  	   assert(scip != NULL);
119  	   assert(heur != NULL);
120  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
121  	
122  	   /* call inclusion method of primal heuristic */
123  	   SCIP_CALL( SCIPincludeHeurIntdiving(scip) );
124  	
125  	   return SCIP_OKAY;
126  	}
127  	
128  	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
129  	static
130  	SCIP_DECL_HEURFREE(heurFreeIntdiving) /*lint --e{715}*/
131  	{  /*lint --e{715}*/
132  	   SCIP_HEURDATA* heurdata;
133  	
134  	   assert(heur != NULL);
135  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
136  	   assert(scip != NULL);
137  	
138  	   /* free heuristic data */
139  	   heurdata = SCIPheurGetData(heur);
140  	   assert(heurdata != NULL);
141  	   SCIPfreeBlockMemory(scip, &heurdata);
142  	   SCIPheurSetData(heur, NULL);
143  	
144  	   return SCIP_OKAY;
145  	}
146  	
147  	
148  	/** initialization method of primal heuristic (called after problem was transformed) */
149  	static
150  	SCIP_DECL_HEURINIT(heurInitIntdiving) /*lint --e{715}*/
151  	{  /*lint --e{715}*/
152  	   SCIP_HEURDATA* heurdata;
153  	
154  	   assert(heur != NULL);
155  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
156  	
157  	   /* get heuristic data */
158  	   heurdata = SCIPheurGetData(heur);
159  	   assert(heurdata != NULL);
160  	
161  	   /* create working solution */
162  	   SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
163  	
164  	   /* initialize data */
165  	   heurdata->nlpiterations = 0;
166  	   heurdata->nsuccess = 0;
167  	
168  	   return SCIP_OKAY;
169  	}
170  	
171  	
172  	/** deinitialization method of primal heuristic (called before transformed problem is freed) */
173  	static
174  	SCIP_DECL_HEUREXIT(heurExitIntdiving) /*lint --e{715}*/
175  	{  /*lint --e{715}*/
176  	   SCIP_HEURDATA* heurdata;
177  	
178  	   assert(heur != NULL);
179  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
180  	
181  	   /* get heuristic data */
182  	   heurdata = SCIPheurGetData(heur);
183  	   assert(heurdata != NULL);
184  	
185  	   /* free working solution */
186  	   SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
187  	
188  	   return SCIP_OKAY;
189  	}
190  	
191  	
192  	/** execution method of primal heuristic */
193  	static
194  	SCIP_DECL_HEUREXEC(heurExecIntdiving) /*lint --e{715}*/
195  	{  /*lint --e{715}*/
196  	   SCIP_HEURDATA* heurdata;
197  	   SCIP_LPSOLSTAT lpsolstat;
198  	   SCIP_VAR** pseudocands;
199  	   SCIP_VAR** fixcands;
200  	   SCIP_Real* fixcandscores;
201  	   SCIP_Real searchubbound;
202  	   SCIP_Real searchavgbound;
203  	   SCIP_Real searchbound;
204  	   SCIP_Real objval;
205  	   SCIP_Bool lperror;
206  	   SCIP_Bool cutoff;
207  	   SCIP_Bool backtracked;
208  	   SCIP_Longint ncalls;
209  	   SCIP_Longint nsolsfound;
210  	   SCIP_Longint nlpiterations;
211  	   SCIP_Longint maxnlpiterations;
212  	   int nfixcands;
213  	   int nbinfixcands;
214  	   int depth;
215  	   int maxdepth;
216  	   int maxdivedepth;
217  	   int divedepth;
218  	   int nextcand;
219  	   int c;
220  	
221  	   assert(heur != NULL);
222  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
223  	   assert(scip != NULL);
224  	   assert(result != NULL);
225  	   assert(SCIPhasCurrentNodeLP(scip));
226  	
227  	   *result = SCIP_DELAYED;
228  	
229  	   /* do not call heuristic of node was already detected to be infeasible */
230  	   if( nodeinfeasible )
231  	      return SCIP_OKAY;
232  	
233  	   /* only call heuristic, if an optimal LP solution is at hand */
234  	   if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
235  	      return SCIP_OKAY;
236  	
237  	   /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
238  	   if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) )
239  	      return SCIP_OKAY;
240  	
241  	   /* only call heuristic, if the LP solution is basic (which allows fast resolve in diving) */
242  	   if( !SCIPisLPSolBasic(scip) )
243  	      return SCIP_OKAY;
244  	
245  	   /* don't dive two times at the same node */
246  	   if( SCIPgetLastDivenode(scip) == SCIPgetNNodes(scip) && SCIPgetDepth(scip) > 0 )
247  	      return SCIP_OKAY;
248  	
249  	   *result = SCIP_DIDNOTRUN;
250  	
251  	   /* get heuristic's data */
252  	   heurdata = SCIPheurGetData(heur);
253  	   assert(heurdata != NULL);
254  	
255  	   /* only try to dive, if we are in the correct part of the tree, given by minreldepth and maxreldepth */
256  	   depth = SCIPgetDepth(scip);
257  	   maxdepth = SCIPgetMaxDepth(scip);
258  	   maxdepth = MAX(maxdepth, 100);
259  	   if( depth < heurdata->minreldepth*maxdepth || depth > heurdata->maxreldepth*maxdepth )
260  	      return SCIP_OKAY;
261  	
262  	   /* calculate the maximal number of LP iterations until heuristic is aborted */
263  	   nlpiterations = SCIPgetNNodeLPIterations(scip);
264  	   ncalls = SCIPheurGetNCalls(heur);
265  	   nsolsfound = 10*SCIPheurGetNBestSolsFound(heur) + heurdata->nsuccess;
266  	   maxnlpiterations = (SCIP_Longint)((1.0 + 10.0*(nsolsfound+1.0)/(ncalls+1.0)) * heurdata->maxlpiterquot * nlpiterations);
267  	   maxnlpiterations += heurdata->maxlpiterofs;
268  	
269  	   /* don't try to dive, if we took too many LP iterations during diving */
270  	   if( heurdata->nlpiterations >= maxnlpiterations )
271  	      return SCIP_OKAY;
272  	
273  	   /* allow at least a certain number of LP iterations in this dive */
274  	   maxnlpiterations = MAX(maxnlpiterations, heurdata->nlpiterations + MINLPITER);
275  	
276  	   /* get unfixed integer variables */
277  	   SCIP_CALL( SCIPgetPseudoBranchCands(scip, &pseudocands, &nfixcands, NULL) );
278  	
279  	   /* don't try to dive, if there are no fractional variables */
280  	   if( nfixcands == 0 )
281  	      return SCIP_OKAY;
282  	
283  	   /* calculate the objective search bound */
284  	   if( SCIPgetNSolsFound(scip) == 0 )
285  	   {
286  	      if( heurdata->maxdiveubquotnosol > 0.0 )
287  	         searchubbound = SCIPgetLowerbound(scip)
288  	            + heurdata->maxdiveubquotnosol * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
289  	      else
290  	         searchubbound = SCIPinfinity(scip);
291  	      if( heurdata->maxdiveavgquotnosol > 0.0 )
292  	         searchavgbound = SCIPgetLowerbound(scip)
293  	            + heurdata->maxdiveavgquotnosol * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
294  	      else
295  	         searchavgbound = SCIPinfinity(scip);
296  	   }
297  	   else
298  	   {
299  	      if( heurdata->maxdiveubquot > 0.0 )
300  	         searchubbound = SCIPgetLowerbound(scip)
301  	            + heurdata->maxdiveubquot * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
302  	      else
303  	         searchubbound = SCIPinfinity(scip);
304  	      if( heurdata->maxdiveavgquot > 0.0 )
305  	         searchavgbound = SCIPgetLowerbound(scip)
306  	            + heurdata->maxdiveavgquot * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
307  	      else
308  	         searchavgbound = SCIPinfinity(scip);
309  	   }
310  	   searchbound = MIN(searchubbound, searchavgbound);
311  	   if( SCIPisObjIntegral(scip) )
312  	      searchbound = SCIPceil(scip, searchbound);
313  	
314  	   /* calculate the maximal diving depth: 10 * min{number of integer variables, max depth} */
315  	   maxdivedepth = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
316  	   maxdivedepth = MIN(maxdivedepth, maxdepth);
317  	   maxdivedepth *= 10;
318  	
319  	   *result = SCIP_DIDNOTFIND;
320  	
321  	   /* start diving */
322  	   SCIP_CALL( SCIPstartProbing(scip) );
323  	
324  	   /* enables collection of variable statistics during probing */
325  	   SCIPenableVarHistory(scip);
326  	
327  	   SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") executing intdiving heuristic: depth=%d, %d non-fixed, dualbound=%g, searchbound=%g\n",
328  	      SCIPgetNNodes(scip), SCIPgetDepth(scip), nfixcands, SCIPgetDualbound(scip), SCIPretransformObj(scip, searchbound));
329  	
330  	   /* copy the pseudo candidates into own array, because we want to reorder them */
331  	   SCIP_CALL( SCIPduplicateBufferArray(scip, &fixcands, pseudocands, nfixcands) );
332  	
333  	   /* sort non-fixed variables by non-increasing inference score, but prefer binaries over integers in any case */
334  	   SCIP_CALL( SCIPallocBufferArray(scip, &fixcandscores, nfixcands) );
335  	   nbinfixcands = 0;
336  	   for( c = 0; c < nfixcands; ++c )
337  	   {
338  	      SCIP_VAR* var;
339  	      SCIP_Real score;
340  	      int colveclen;
341  	      int left;
342  	      int right;
343  	      int i;
344  	
345  	      assert(c >= nbinfixcands);
346  	      var = fixcands[c];
347  	      assert(SCIPvarIsIntegral(var));
348  	      colveclen = (SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN ? SCIPcolGetNNonz(SCIPvarGetCol(var)) : 0);
349  	      if( SCIPvarIsBinary(var) )
350  	      {
351  	         score = 500.0 * SCIPvarGetNCliques(var, TRUE) + 100.0 * SCIPvarGetNImpls(var, TRUE)
352  	            + SCIPgetVarAvgInferenceScore(scip, var) + (SCIP_Real)colveclen/100.0;
353  	
354  	         /* shift the non-binary variables one slot to the right */
355  	         for( i = c; i > nbinfixcands; --i )
356  	         {
357  	            fixcands[i] = fixcands[i-1];
358  	            fixcandscores[i] = fixcandscores[i-1];
359  	         }
360  	         /* put the new candidate into the first nbinfixcands slot */
361  	         left = 0;
362  	         right = nbinfixcands;
363  	         nbinfixcands++;
364  	      }
365  	      else
366  	      {
367  	         score = 5.0 * (SCIPvarGetNCliques(var, FALSE) + SCIPvarGetNCliques(var, TRUE))
368  	            + SCIPvarGetNImpls(var, FALSE) + SCIPvarGetNImpls(var, TRUE) + SCIPgetVarAvgInferenceScore(scip, var)
369  	            + (SCIP_Real)colveclen/10000.0;
370  	
371  	         /* put the new candidate in the slots after the binary candidates */
372  	         left = nbinfixcands;
373  	         right = c;
374  	      }
375  	      for( i = right; i > left && score > fixcandscores[i-1]; --i )
376  	      {
377  	         fixcands[i] = fixcands[i-1];
378  	         fixcandscores[i] = fixcandscores[i-1];
379  	      }
380  	      fixcands[i] = var;
381  	      fixcandscores[i] = score;
382  	      SCIPdebugMsg(scip, "  <%s>: ncliques=%d/%d, nimpls=%d/%d, inferencescore=%g, colveclen=%d  ->  score=%g\n",
383  	         SCIPvarGetName(var), SCIPvarGetNCliques(var, FALSE), SCIPvarGetNCliques(var, TRUE),
384  	         SCIPvarGetNImpls(var, FALSE), SCIPvarGetNImpls(var, TRUE), SCIPgetVarAvgInferenceScore(scip, var),
385  	         colveclen, score);
386  	   }
387  	   SCIPfreeBufferArray(scip, &fixcandscores);
388  	
389  	   /* get LP objective value */
390  	   lpsolstat = SCIP_LPSOLSTAT_OPTIMAL;
391  	   objval = SCIPgetLPObjval(scip);
392  	
393  	   /* dive as long we are in the given objective, depth and iteration limits, but if possible, we dive at least with
394  	    * the depth 10
395  	    */
396  	   lperror = FALSE;
397  	   cutoff = FALSE;
398  	   divedepth = 0;
399  	   nextcand = 0;
400  	   while( !lperror && !cutoff && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL
401  	      && (divedepth < 10
402  	         || (divedepth < maxdivedepth && heurdata->nlpiterations < maxnlpiterations && objval < searchbound))
403  	      && !SCIPisStopped(scip) )
404  	   {
405  	      SCIP_VAR* var;
406  	      SCIP_Real bestsolval;
407  	      SCIP_Real bestfixval;
408  	      int bestcand;
409  	      SCIP_Longint nnewlpiterations;
410  	      SCIP_Longint nnewdomreds;
411  	
412  	      /* open a new probing node if this will not exceed the maximal tree depth, otherwise stop here */
413  	      if( SCIPgetDepth(scip) < SCIP_MAXTREEDEPTH )
414  	      {
415  	         SCIP_CALL( SCIPnewProbingNode(scip) );
416  	         divedepth++;
417  	      }
418  	      else
419  	         break;
420  	
421  	      nnewlpiterations = 0;
422  	      nnewdomreds = 0;
423  	
424  	      /* fix binary variable that is closest to 1 in the LP solution to 1;
425  	       * if all binary variables are fixed, fix integer variable with least fractionality in LP solution
426  	       */
427  	      bestcand = -1;
428  	      bestsolval = -1.0;
429  	      bestfixval = 1.0;
430  	
431  	      /* look in the binary variables for fixing candidates */
432  	      for( c = nextcand; c < nbinfixcands; ++c )
433  	      {
434  	         SCIP_Real solval;
435  	
436  	         var = fixcands[c];
437  	
438  	         /* ignore already fixed variables */
439  	         if( var == NULL )
440  	            continue;
441  	         if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 )
442  	         {
443  	            fixcands[c] = NULL;
444  	            continue;
445  	         }
446  	
447  	         /* get the LP solution value */
448  	         solval = SCIPvarGetLPSol(var);
449  	
450  	         if( solval > bestsolval )
451  	         {
452  	            bestcand = c;
453  	            bestfixval = 1.0;
454  	            bestsolval = solval;
455  	            if( SCIPisGE(scip, bestsolval, 1.0) )
456  	            {
457  	               /* we found an unfixed binary variable with LP solution value of 1.0 - there cannot be a better candidate */
458  	               break;
459  	            }
460  	            else if( SCIPisLE(scip, bestsolval, 0.0) )
461  	            {
462  	               /* the variable is currently at 0.0 - this is the only situation where we want to fix it to 0.0 */
463  	               bestfixval = 0.0;
464  	            }
465  	         }
466  	      }
467  	
468  	      /* if all binary variables are fixed, look in the integer variables for a fixing candidate */
469  	      if( bestcand == -1 )
470  	      {
471  	         SCIP_Real bestfrac;
472  	
473  	         bestfrac = SCIP_INVALID;
474  	         for( c = MAX(nextcand, nbinfixcands); c < nfixcands; ++c )
475  	         {
476  	            SCIP_Real solval;
477  	            SCIP_Real frac;
478  	
479  	            var = fixcands[c];
480  	
481  	            /* ignore already fixed variables */
482  	            if( var == NULL )
483  	               continue;
484  	            if( SCIPvarGetUbLocal(var) - SCIPvarGetLbLocal(var) < 0.5 )
485  	            {
486  	               fixcands[c] = NULL;
487  	               continue;
488  	            }
489  	
490  	            /* get the LP solution value */
491  	            solval = SCIPvarGetLPSol(var);
492  	            frac = SCIPfrac(scip, solval);
493  	
494  	            /* ignore integer variables that are currently integral */
495  	            if( SCIPisFeasFracIntegral(scip, frac) )
496  	               continue;
497  	
498  	            if( frac < bestfrac )
499  	            {
500  	               bestcand = c;
501  	               bestsolval = solval;
502  	               bestfrac = frac;
503  	               bestfixval = SCIPfloor(scip, bestsolval + 0.5);
504  	               if( SCIPisZero(scip, bestfrac) )
505  	               {
506  	                  /* we found an unfixed integer variable with integral LP solution value */
507  	                  break;
508  	               }
509  	            }
510  	         }
511  	      }
512  	      assert(-1 <= bestcand && bestcand < nfixcands);
513  	
514  	      /* if there is no unfixed candidate left, we are done */
515  	      if( bestcand == -1 )
516  	         break;
517  	
518  	      var = fixcands[bestcand];
519  	      assert(var != NULL);
520  	      assert(SCIPvarIsIntegral(var));
521  	      assert(SCIPvarGetUbLocal(var) - SCIPvarGetLbLocal(var) > 0.5);
522  	      assert(SCIPisGE(scip, bestfixval, SCIPvarGetLbLocal(var)));
523  	      assert(SCIPisLE(scip, bestfixval, SCIPvarGetUbLocal(var)));
524  	
525  	      backtracked = FALSE;
526  	      do
527  	      {
528  	         /* if the variable is already fixed or if the solution value is outside the domain, numerical troubles may have
529  	          * occured or variable was fixed by propagation while backtracking => Abort diving!
530  	          */
531  	         if( SCIPvarGetLbLocal(var) >= SCIPvarGetUbLocal(var) - 0.5 )
532  	         {
533  	            SCIPdebugMsg(scip, "Selected variable <%s> already fixed to [%g,%g], diving aborted \n",
534  	               SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var));
535  	            cutoff = TRUE;
536  	            break;
537  	         }
538  	         if( SCIPisFeasLT(scip, bestfixval, SCIPvarGetLbLocal(var)) || SCIPisFeasGT(scip, bestfixval, SCIPvarGetUbLocal(var)) )
539  	         {
540  	            SCIPdebugMsg(scip, "selected variable's <%s> solution value is outside the domain [%g,%g] (solval: %.9f), diving aborted\n",
541  	               SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bestfixval);
542  	            assert(backtracked);
543  	            break;
544  	         }
545  	
546  	         /* apply fixing of best candidate */
547  	         SCIPdebugMsg(scip, "  dive %d/%d, LP iter %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ", %d unfixed: var <%s>, sol=%g, oldbounds=[%g,%g], fixed to %g\n",
548  	            divedepth, maxdivedepth, heurdata->nlpiterations, maxnlpiterations, SCIPgetNPseudoBranchCands(scip),
549  	            SCIPvarGetName(var), bestsolval, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bestfixval);
550  	         SCIP_CALL( SCIPfixVarProbing(scip, var, bestfixval) );
551  	
552  	         /* apply domain propagation */
553  	         SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, &nnewdomreds) );
554  	         if( !cutoff )
555  	         {
556  	            /* if the best candidate was just fixed to its LP value and no domain reduction was found, the LP solution
557  	             * stays valid, and the LP does not need to be resolved
558  	             */
559  	            if( nnewdomreds > 0 || !SCIPisEQ(scip, bestsolval, bestfixval) )
560  	            {
561  	            /* resolve the diving LP */
562  	               /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
563  	                * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
564  	                */
565  	#ifdef NDEBUG
566  	               SCIP_RETCODE retstat;
567  	               nlpiterations = SCIPgetNLPIterations(scip);
568  	               retstat = SCIPsolveProbingLP(scip, MAX((int)(maxnlpiterations - heurdata->nlpiterations), MINLPITER), &lperror, &cutoff);
569  	               if( retstat != SCIP_OKAY )
570  	               {
571  	                  SCIPwarningMessage(scip, "Error while solving LP in Intdiving heuristic; LP solve terminated with code <%d>\n",retstat);
572  	               }
573  	#else
574  	               nlpiterations = SCIPgetNLPIterations(scip);
575  	               SCIP_CALL( SCIPsolveProbingLP(scip, MAX((int)(maxnlpiterations - heurdata->nlpiterations), MINLPITER), &lperror, &cutoff) );
576  	#endif
577  	
578  	               if( lperror )
579  	                  break;
580  	
581  	               /* update iteration count */
582  	               nnewlpiterations = SCIPgetNLPIterations(scip) - nlpiterations;
583  	               heurdata->nlpiterations += nnewlpiterations;
584  	
585  	               /* get LP solution status */
586  	               lpsolstat = SCIPgetLPSolstat(scip);
587  	               assert(cutoff || (lpsolstat != SCIP_LPSOLSTAT_OBJLIMIT && lpsolstat != SCIP_LPSOLSTAT_INFEASIBLE &&
588  	                     (lpsolstat != SCIP_LPSOLSTAT_OPTIMAL || SCIPisLT(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)))));
589  	            }
590  	         }
591  	
592  	         /* perform backtracking if a cutoff was detected */
593  	         if( cutoff && !backtracked && heurdata->backtrack )
594  	         {
595  	            SCIPdebugMsg(scip, "  *** cutoff detected at level %d - backtracking\n", SCIPgetProbingDepth(scip));
596  	            SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip)-1) );
597  	
598  	            /* after backtracking there has to be at least one open node without exceeding the maximal tree depth */
599  	            assert(SCIP_MAXTREEDEPTH > SCIPgetDepth(scip));
600  	
601  	            SCIP_CALL( SCIPnewProbingNode(scip) );
602  	
603  	            bestfixval = SCIPvarIsBinary(var)
604  	               ? 1.0 - bestfixval
605  	               : (SCIPisGT(scip, bestsolval, bestfixval) && SCIPisFeasLE(scip, bestfixval + 1, SCIPvarGetUbLocal(var)) ? bestfixval + 1 : bestfixval - 1);
606  	
607  	            backtracked = TRUE;
608  	         }
609  	         else
610  	            backtracked = FALSE;
611  	      }
612  	      while( backtracked );
613  	
614  	      if( !lperror && !cutoff && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
615  	      {
616  	         SCIP_Bool success;
617  	
618  	         /* get new objective value */
619  	         objval = SCIPgetLPObjval(scip);
620  	
621  	         if( nnewlpiterations > 0 || !SCIPisEQ(scip, bestsolval, bestfixval) )
622  	         {
623  	            /* we must start again with the first candidate, since the LP solution changed */
624  	            nextcand = 0;
625  	
626  	            /* create solution from diving LP and try to round it */
627  	            SCIP_CALL( SCIPlinkLPSol(scip, heurdata->sol) );
628  	            SCIP_CALL( SCIProundSol(scip, heurdata->sol, &success) );
629  	            if( success )
630  	            {
631  	               SCIPdebugMsg(scip, "intdiving found roundable primal solution: obj=%g\n",
632  	                  SCIPgetSolOrigObj(scip, heurdata->sol));
633  	
634  	               /* try to add solution to SCIP */
635  	               SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
636  	
637  	               /* check, if solution was feasible and good enough */
638  	               if( success )
639  	               {
640  	                  SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
641  	                  *result = SCIP_FOUNDSOL;
642  	               }
643  	            }
644  	         }
645  	         else
646  	            nextcand = bestcand+1; /* continue with the next candidate in the following loop */
647  	      }
648  	      SCIPdebugMsg(scip, "   -> lpsolstat=%d, objval=%g/%g\n", lpsolstat, objval, searchbound);
649  	   }
650  	
651  	   /* free temporary memory */
652  	   SCIPfreeBufferArray(scip, &fixcands);
653  	
654  	   /* end diving */
655  	   SCIP_CALL( SCIPendProbing(scip) );
656  	
657  	   if( *result == SCIP_FOUNDSOL )
658  	      heurdata->nsuccess++;
659  	
660  	   SCIPdebugMsg(scip, "intdiving heuristic finished\n");
661  	
662  	   return SCIP_OKAY;  /*lint !e438*/
663  	}
664  	
665  	
666  	/*
667  	 * heuristic specific interface methods
668  	 */
669  	
670  	/** creates the intdiving heuristic and includes it in SCIP */
671  	SCIP_RETCODE SCIPincludeHeurIntdiving(
672  	   SCIP*                 scip                /**< SCIP data structure */
673  	   )
674  	{
675  	   SCIP_HEURDATA* heurdata;
676  	   SCIP_HEUR* heur;
677  	
678  	   /* create Intdiving primal heuristic data */
679  	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
680  	
681  	   /* include primal heuristic */
682  	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
683  	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
684  	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecIntdiving, heurdata) );
685  	
686  	   assert(heur != NULL);
687  	
688  	   /* set non-NULL pointers to callback methods */
689  	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyIntdiving) );
690  	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeIntdiving) );
691  	   SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitIntdiving) );
692  	   SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitIntdiving) );
693  	
694  	   /* intdiving heuristic parameters */
695  	   SCIP_CALL( SCIPaddRealParam(scip,
696  	         "heuristics/intdiving/minreldepth",
697  	         "minimal relative depth to start diving",
698  	         &heurdata->minreldepth, TRUE, DEFAULT_MINRELDEPTH, 0.0, 1.0, NULL, NULL) );
699  	   SCIP_CALL( SCIPaddRealParam(scip,
700  	         "heuristics/intdiving/maxreldepth",
701  	         "maximal relative depth to start diving",
702  	         &heurdata->maxreldepth, TRUE, DEFAULT_MAXRELDEPTH, 0.0, 1.0, NULL, NULL) );
703  	   SCIP_CALL( SCIPaddRealParam(scip,
704  	         "heuristics/intdiving/maxlpiterquot",
705  	         "maximal fraction of diving LP iterations compared to node LP iterations",
706  	         &heurdata->maxlpiterquot, FALSE, DEFAULT_MAXLPITERQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
707  	   SCIP_CALL( SCIPaddIntParam(scip,
708  	         "heuristics/intdiving/maxlpiterofs",
709  	         "additional number of allowed LP iterations",
710  	         &heurdata->maxlpiterofs, FALSE, DEFAULT_MAXLPITEROFS, 0, INT_MAX, NULL, NULL) );
711  	   SCIP_CALL( SCIPaddRealParam(scip,
712  	         "heuristics/intdiving/maxdiveubquot",
713  	         "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)",
714  	         &heurdata->maxdiveubquot, TRUE, DEFAULT_MAXDIVEUBQUOT, 0.0, 1.0, NULL, NULL) );
715  	   SCIP_CALL( SCIPaddRealParam(scip,
716  	         "heuristics/intdiving/maxdiveavgquot",
717  	         "maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)",
718  	         &heurdata->maxdiveavgquot, TRUE, DEFAULT_MAXDIVEAVGQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
719  	   SCIP_CALL( SCIPaddRealParam(scip,
720  	         "heuristics/intdiving/maxdiveubquotnosol",
721  	         "maximal UBQUOT when no solution was found yet (0.0: no limit)",
722  	         &heurdata->maxdiveubquotnosol, TRUE, DEFAULT_MAXDIVEUBQUOTNOSOL, 0.0, 1.0, NULL, NULL) );
723  	   SCIP_CALL( SCIPaddRealParam(scip,
724  	         "heuristics/intdiving/maxdiveavgquotnosol",
725  	         "maximal AVGQUOT when no solution was found yet (0.0: no limit)",
726  	         &heurdata->maxdiveavgquotnosol, TRUE, DEFAULT_MAXDIVEAVGQUOTNOSOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
727  	   SCIP_CALL( SCIPaddBoolParam(scip,
728  	         "heuristics/intdiving/backtrack",
729  	         "use one level of backtracking if infeasibility is encountered?",
730  	         &heurdata->backtrack, FALSE, DEFAULT_BACKTRACK, NULL, NULL) );
731  	
732  	   return SCIP_OKAY;
733  	}
734