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_nlpdiving.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  NLP diving heuristic that chooses fixings w.r.t. the fractionalities
28   	 * @author Timo Berthold
29   	 * @author Stefan Vigerske
30   	 */
31   	
32   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33   	
34   	#include "blockmemshell/memory.h"
35   	#include "scip/heur_nlpdiving.h"
36   	#include "scip/heur_subnlp.h"
37   	#include "scip/heur_undercover.h"
38   	#include "scip/pub_event.h"
39   	#include "scip/pub_heur.h"
40   	#include "scip/pub_message.h"
41   	#include "scip/pub_misc.h"
42   	#include "scip/pub_sol.h"
43   	#include "scip/pub_var.h"
44   	#include "scip/scip_branch.h"
45   	#include "scip/scip_copy.h"
46   	#include "scip/scip_event.h"
47   	#include "scip/scip_general.h"
48   	#include "scip/scip_heur.h"
49   	#include "scip/scip_lp.h"
50   	#include "scip/scip_mem.h"
51   	#include "scip/scip_message.h"
52   	#include "scip/scip_nlp.h"
53   	#include "scip/scip_nlpi.h"
54   	#include "scip/scip_nodesel.h"
55   	#include "scip/scip_numerics.h"
56   	#include "scip/scip_param.h"
57   	#include "scip/scip_prob.h"
58   	#include "scip/scip_probing.h"
59   	#include "scip/scip_randnumgen.h"
60   	#include "scip/scip_sol.h"
61   	#include "scip/scip_solve.h"
62   	#include "scip/scip_solvingstats.h"
63   	#include "scip/scip_timing.h"
64   	#include "scip/scip_tree.h"
65   	#include "scip/scip_var.h"
66   	#include <string.h>
67   	
68   	#define HEUR_NAME             "nlpdiving"
69   	#define HEUR_DESC             "NLP diving heuristic that chooses fixings w.r.t. the fractionalities"
70   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_DIVING
71   	#define HEUR_PRIORITY         -1003010
72   	#define HEUR_FREQ             10
73   	#define HEUR_FREQOFS          3
74   	#define HEUR_MAXDEPTH         -1
75   	#define HEUR_TIMING           SCIP_HEURTIMING_AFTERLPPLUNGE
76   	#define HEUR_USESSUBSCIP      FALSE  /**< does the heuristic use a secondary SCIP instance? */
77   	
78   	/* event handler properties */
79   	#define EVENTHDLR_NAME         "Nlpdiving"
80   	#define EVENTHDLR_DESC         "bound change event handler for " HEUR_NAME " heuristic"
81   	
82   	
83   	/*
84   	 * Default parameter settings
85   	 */
86   	
87   	#define DEFAULT_MINRELDEPTH         0.0 /**< minimal relative depth to start diving */
88   	#define DEFAULT_MAXRELDEPTH         1.0 /**< maximal relative depth to start diving */
89   	#define DEFAULT_MAXNLPITERABS       200 /**< minimial absolute number of allowed NLP iterations */
90   	#define DEFAULT_MAXNLPITERREL        10 /**< additional allowed number of NLP iterations relative to successfully found solutions */
91   	#define DEFAULT_MAXDIVEUBQUOT       0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
92   	                                         *   where diving is performed (0.0: no limit) */
93   	#define DEFAULT_MAXDIVEAVGQUOT      0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
94   	                                         *   where diving is performed (0.0: no limit) */
95   	#define DEFAULT_MAXDIVEUBQUOTNOSOL  0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
96   	#define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
97   	#define DEFAULT_MINSUCCQUOT         0.1 /**< heuristic will not run if less then this percentage of calls succeeded (0.0: no limit) */
98   	#define DEFAULT_MAXFEASNLPS          10 /**< maximal number of NLPs with feasible solution to solve during one dive */
99   	#define DEFAULT_FIXQUOT             0.2 /**< percentage of fractional variables that should be fixed before the next NLP solve */
100  	#define DEFAULT_BACKTRACK          TRUE /**< use one level of backtracking if infeasibility is encountered? */
101  	#define DEFAULT_LP                FALSE /**< should the LP relaxation be solved before the NLP relaxation? */
102  	#define DEFAULT_PREFERLPFRACS     FALSE /**< prefer variables that are also fractional in LP solution? */
103  	#define DEFAULT_PREFERCOVER        TRUE /**< should variables in a minimal cover be preferred? */
104  	#define DEFAULT_SOLVESUBMIP       FALSE /**< should a sub-MIP be solved if all cover variables are fixed? */
105  	#define DEFAULT_NLPSTART            's' /**< which point should be used as starting point for the NLP solver? */
106  	#define DEFAULT_VARSELRULE          'd' /**< which variable selection should be used? ('f'ractionality, 'c'oefficient,
107  	                                         *   'p'seudocost, 'g'uided, 'd'ouble)
108  	                                         */
109  	#define DEFAULT_NLPFASTFAIL        TRUE /**< should the NLP solver stop early if it converges slow? */
110  	#define DEFAULT_RANDSEED             97 /**< initial random seed */
111  	
112  	#define MINNLPITER                   10 /**< minimal number of NLP iterations allowed in each NLP solving call */
113  	
114  	/* locally defined heuristic data */
115  	struct SCIP_HeurData
116  	{
117  	   SCIP_SOL*             sol;                /**< working solution */
118  	   SCIP_Real             minreldepth;        /**< minimal relative depth to start diving */
119  	   SCIP_Real             maxreldepth;        /**< maximal relative depth to start diving */
120  	   int                   maxnlpiterabs;      /**< minimial absolute number of allowed NLP iterations */
121  	   int                   maxnlpiterrel;      /**< additional allowed number of NLP iterations relative to successfully found solutions */
122  	   SCIP_Real             maxdiveubquot;      /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
123  	                                              *   where diving is performed (0.0: no limit) */
124  	   SCIP_Real             maxdiveavgquot;     /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
125  	                                              *   where diving is performed (0.0: no limit) */
126  	   SCIP_Real             maxdiveubquotnosol; /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
127  	   SCIP_Real             maxdiveavgquotnosol;/**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
128  	   int                   maxfeasnlps;        /**< maximal number of NLPs with feasible solution to solve during one dive */
129  	   SCIP_Real             minsuccquot;        /**< heuristic will not run if less then this percentage of calls succeeded (0.0: no limit) */
130  	   SCIP_Real             fixquot;            /**< percentage of fractional variables that should be fixed before the next NLP solve */
131  	   SCIP_Bool             backtrack;          /**< use one level of backtracking if infeasibility is encountered? */
132  	   SCIP_Bool             lp;                 /**< should the LP relaxation be solved before the NLP relaxation? */
133  	   SCIP_Bool             preferlpfracs;      /**< prefer variables that are also fractional in LP solution? */
134  	   SCIP_Bool             prefercover;        /**< should variables in a minimal cover be preferred? */
135  	   SCIP_Bool             solvesubmip;        /**< should a sub-MIP be solved if all cover variables are fixed? */
136  	   SCIP_Bool             nlpfastfail;        /**< should the NLP solver stop early if it converges slow? */
137  	   char                  nlpstart;           /**< which point should be used as starting point for the NLP solver? */
138  	   char                  varselrule;         /**< which variable selection should be used? ('f'ractionality, 'c'oefficient,
139  	                                              *   'p'seudocost, 'g'uided, 'd'ouble)
140  	                                              */
141  	
142  	   int                   nnlpiterations;     /**< NLP iterations used in this heuristic */
143  	   int                   nsuccess;           /**< number of runs that produced at least one feasible solution */
144  	   int                   nfixedcovervars;    /**< number of variables in the cover that are already fixed */
145  	#ifdef SCIP_STATISTIC
146  	   int                   nnlpsolves;         /**< number of NLP solves */
147  	   int                   nfailcutoff;        /**< number of fails due to cutoff */
148  	   int                   nfaildepth;         /**< number of fails due to too deep */
149  	   int                   nfailnlperror;      /**< number of fails due to NLP error */
150  	#endif
151  	   SCIP_EVENTHDLR*       eventhdlr;          /**< event handler for bound change events */
152  	   SCIP_RANDNUMGEN*      randnumgen;         /**< random number generator */
153  	};
154  	
155  	
156  	/*
157  	 * local methods
158  	 */
159  	
160  	/** gets fractional variables of last NLP solution along with solution values and fractionalities
161  	 *
162  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
163  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
164  	 *
165  	 *  @pre This method can be called if SCIP is in one of the following stages:
166  	 *       - \ref SCIP_STAGE_INITSOLVE
167  	 *       - \ref SCIP_STAGE_SOLVING
168  	 */
169  	static
170  	SCIP_RETCODE getNLPFracVars(
171  	   SCIP*                 scip,               /**< SCIP data structure */
172  	   SCIP_HEURDATA*        heurdata,           /**< heuristic data structure */
173  	   SCIP_VAR***           nlpcands,           /**< pointer to store the array of NLP fractional variables, or NULL */
174  	   SCIP_Real**           nlpcandssol,        /**< pointer to store the array of NLP fractional variables solution values, or NULL */
175  	   SCIP_Real**           nlpcandsfrac,       /**< pointer to store the array of NLP fractional variables fractionalities, or NULL */
176  	   int*                  nnlpcands           /**< pointer to store the number of NLP fractional variables , or NULL */
177  	   )
178  	{
179  	   int c;
180  	
181  	   assert(scip != NULL);
182  	   assert(heurdata != NULL);
183  	   assert(nlpcands != NULL);
184  	   assert(nlpcandssol != NULL);
185  	   assert(nlpcandsfrac != NULL);
186  	   assert(nnlpcands != NULL);
187  	
188  	   /* get fractional variables that should be integral */
189  	   SCIP_CALL( SCIPgetNLPFracVars(scip, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, NULL) );
190  	
191  	   /* values may be outside the domain in exact arithmetic, but inside the domain within relative tolerance, and still
192  	    * slightly fractional, because SCIPisFeasIntegral() uses absolute tolerance; project value onto domain to avoid this
193  	    * (example: primsol=29.99999853455704, lower bound = 30)
194  	    */
195  	   for( c = 0; c < *nnlpcands; ++c )
196  	   {
197  	      assert(!SCIPisFeasIntegral(scip, (*nlpcandssol)[c]));
198  	
199  	      if( (*nlpcandssol)[c] < SCIPvarGetLbLocal((*nlpcands)[c]) || (*nlpcandssol)[c] > SCIPvarGetUbLocal((*nlpcands)[c]) )
200  	      {
201  	         SCIP_Real newval;
202  	
203  	         newval = ((*nlpcandssol)[c] < SCIPvarGetLbLocal((*nlpcands)[c]))
204  	            ? SCIPvarGetLbLocal((*nlpcands)[c]) - 0.5*SCIPfeastol(scip)
205  	            : SCIPvarGetUbLocal((*nlpcands)[c]) + 0.5*SCIPfeastol(scip);
206  	
207  	         assert(SCIPisFeasIntegral(scip, newval));
208  	
209  	         SCIP_CALL( SCIPsetSolVal(scip, heurdata->sol, (*nlpcands)[c], newval) );
210  	
211  	         (*nnlpcands)--;
212  	
213  	         if( c < *nnlpcands )
214  	         {
215  	            (*nlpcands)[c] = (*nlpcands)[*nnlpcands];
216  	            (*nlpcandssol)[c] = (*nlpcandssol)[*nnlpcands];
217  	            (*nlpcandsfrac)[c] = (*nlpcandsfrac)[*nnlpcands];
218  	         }
219  	      }
220  	   }
221  	
222  	   /* prefer decisions on variables which are also fractional in LP solution */
223  	   if( heurdata->preferlpfracs && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
224  	   {
225  	      for( c = 0; c < *nnlpcands; ++c )
226  	      {
227  	         if( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, NULL, (*nlpcands)[c])) )
228  	            (*nlpcandsfrac)[c] *= 100.0;
229  	      }
230  	   }
231  	
232  	   return SCIP_OKAY;
233  	}
234  	
235  	/** finds best candidate variable w.r.t. fractionality:
236  	 * - prefer variables that may not be rounded without destroying NLP feasibility:
237  	 *   - of these variables, round least fractional variable in corresponding direction
238  	 * - if all remaining fractional variables may be rounded without destroying NLP feasibility:
239  	 *   - round variable with least increasing objective value
240  	 * - binary variables are prefered
241  	 * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
242  	 *   also be prefered if a correpsonding parameter is set
243  	 */
244  	static
245  	SCIP_RETCODE chooseFracVar(
246  	   SCIP*                 scip,               /**< original SCIP data structure */
247  	   SCIP_HEURDATA*        heurdata,           /**< heuristic data structure */
248  	   SCIP_VAR**            nlpcands,           /**< array of NLP fractional variables */
249  	   SCIP_Real*            nlpcandssol,        /**< array of NLP fractional variables solution values */
250  	   SCIP_Real*            nlpcandsfrac,       /**< array of NLP fractional variables fractionalities */
251  	   int                   nnlpcands,          /**< number of NLP fractional variables */
252  	   SCIP_HASHMAP*         varincover,         /**< hash map for variables */
253  	   SCIP_Bool             covercomputed,      /**< has a minimal cover been computed? */
254  	   int*                  bestcand,           /**< pointer to store the index of the best candidate variable */
255  	   SCIP_Bool*            bestcandmayround,   /**< pointer to store whether best candidate is trivially roundable */
256  	   SCIP_Bool*            bestcandroundup     /**< pointer to store whether best candidate should be rounded up */
257  	   )
258  	{
259  	   SCIP_Real bestobjgain;
260  	   SCIP_Real bestfrac;
261  	   SCIP_Bool bestcandmayrounddown;
262  	   SCIP_Bool bestcandmayroundup;
263  	   int c;
264  	
265  	   /* check preconditions */
266  	   assert(scip != NULL);
267  	   assert(heurdata != NULL);
268  	   assert(nlpcands != NULL);
269  	   assert(nlpcandssol != NULL);
270  	   assert(nlpcandsfrac != NULL);
271  	   assert(covercomputed == (varincover != NULL));
272  	   assert(bestcand != NULL);
273  	   assert(bestcandmayround != NULL);
274  	   assert(bestcandroundup != NULL);
275  	
276  	   bestcandmayrounddown = TRUE;
277  	   bestcandmayroundup = TRUE;
278  	   bestobjgain = SCIPinfinity(scip);
279  	   bestfrac = SCIP_INVALID;
280  	
281  	   for( c = 0; c < nnlpcands; ++c )
282  	   {
283  	      SCIP_VAR* var;
284  	      SCIP_Bool mayrounddown;
285  	      SCIP_Bool mayroundup;
286  	      SCIP_Bool roundup;
287  	      SCIP_Real frac;
288  	      SCIP_Real obj;
289  	      SCIP_Real objgain;
290  	
291  	      var = nlpcands[c];
292  	
293  	      mayrounddown = SCIPvarMayRoundDown(var);
294  	      mayroundup = SCIPvarMayRoundUp(var);
295  	      frac = nlpcandsfrac[c];
296  	      obj = SCIPvarGetObj(var);
297  	
298  	      /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
299  	      if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
300  	         continue;
301  	
302  	      if( mayrounddown || mayroundup )
303  	      {
304  	         /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
305  	         if( bestcandmayrounddown || bestcandmayroundup )
306  	         {
307  	            /* choose rounding direction:
308  	             * - if variable may be rounded in both directions, round corresponding to the fractionality
309  	             * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
310  	             *   the current fractional solution
311  	             */
312  	            if( mayrounddown && mayroundup )
313  	            {
314  	               if( SCIPisEQ(scip, frac, 0.5) )
315  	                  roundup = (SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0);
316  	               else
317  	                  roundup = (frac > 0.5);
318  	            }
319  	            else
320  	               roundup = mayrounddown;
321  	
322  	            if( roundup )
323  	            {
324  	               frac = 1.0 - frac;
325  	               objgain = frac*obj;
326  	            }
327  	            else
328  	               objgain = -frac*obj;
329  	
330  	            /* penalize too small fractions */
331  	            if( SCIPisEQ(scip, frac, 0.01) )
332  	            {
333  	               /* try to avoid variability; decide randomly if the LP solution can contain some noise.
334  	                * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
335  	                */
336  	               if( SCIPrandomGetInt(heurdata->randnumgen, 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 )
337  	                  objgain *= 1000.0;
338  	            }
339  	            else if( frac < 0.01 )
340  	               objgain *= 1000.0;
341  	
342  	            /* prefer decisions on binary variables */
343  	            if( !SCIPvarIsBinary(var) )
344  	               objgain *= 1000.0;
345  	
346  	            /* prefer decisions on cover variables */
347  	            if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) )
348  	               objgain *= 1000.0;
349  	
350  	            /* check, if candidate is new best candidate */
351  	            if( SCIPisLT(scip, objgain, bestobjgain) || (SCIPisEQ(scip, objgain, bestobjgain) && frac < bestfrac) )
352  	            {
353  	               *bestcand = c;
354  	               bestobjgain = objgain;
355  	               bestfrac = frac;
356  	               bestcandmayrounddown = mayrounddown;
357  	               bestcandmayroundup = mayroundup;
358  	               *bestcandroundup = roundup;
359  	            }
360  	         }
361  	      }
362  	      else
363  	      {
364  	         /* the candidate may not be rounded */
365  	         if( SCIPisEQ(scip, frac, 0.5) )
366  	            roundup = (SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0);
367  	         else if( frac < 0.5 )
368  	            roundup = FALSE;
369  	         else
370  	            roundup = TRUE;
371  	
372  	         /* adjust fractional part */
373  	         if( roundup )
374  	            frac = 1.0 - frac;
375  	
376  	         /* penalize too small fractions */
377  	         if( SCIPisEQ(scip, frac, 0.01) )
378  	         {
379  	            /* try to avoid variability; decide randomly if the LP solution can contain some noise.
380  	             * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
381  	             */
382  	            if( SCIPrandomGetInt(heurdata->randnumgen, 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 )
383  	               frac += 10.0;
384  	         }
385  	         else if( frac < 0.01 )
386  	            frac += 10.0;
387  	
388  	         /* prefer decisions on binary variables */
389  	         if( !SCIPvarIsBinary(var) )
390  	            frac *= 1000.0;
391  	
392  	         /* prefer decisions on cover variables */
393  	         if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) )
394  	            frac *= 1000.0;
395  	
396  	         /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
397  	         if( bestcandmayrounddown || bestcandmayroundup || frac < bestfrac )
398  	         {
399  	            *bestcand = c;
400  	            bestfrac = frac;
401  	            bestcandmayrounddown = FALSE;
402  	            bestcandmayroundup = FALSE;
403  	            *bestcandroundup = roundup;
404  	         }
405  	         assert(bestfrac < SCIP_INVALID);
406  	      }
407  	   }
408  	
409  	   *bestcandmayround = bestcandmayroundup || bestcandmayrounddown;
410  	
411  	   return SCIP_OKAY;
412  	}
413  	
414  	/** finds best candidate variable w.r.t. vector length:
415  	 * - round variable with a small ratio between the increase in the objective and the locking numbers
416  	 * - binary variables are prefered
417  	 * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
418  	 *   also be prefered if a corresponding parameter is set
419  	 */
420  	static
421  	SCIP_RETCODE chooseVeclenVar(
422  	   SCIP*                 scip,               /**< original SCIP data structure */
423  	   SCIP_HEURDATA*        heurdata,           /**< heuristic data structure */
424  	   SCIP_VAR**            nlpcands,           /**< array of NLP fractional variables */
425  	   SCIP_Real*            nlpcandssol,        /**< array of NLP fractional variables solution values */
426  	   SCIP_Real*            nlpcandsfrac,       /**< array of NLP fractional variables fractionalities */
427  	   int                   nnlpcands,          /**< number of NLP fractional variables */
428  	   SCIP_HASHMAP*         varincover,         /**< hash map for variables */
429  	   SCIP_Bool             covercomputed,      /**< has a minimal cover been computed? */
430  	   int*                  bestcand,           /**< pointer to store the index of the best candidate variable */
431  	   SCIP_Bool*            bestcandmayround,   /**< pointer to store whether best candidate is trivially roundable */
432  	   SCIP_Bool*            bestcandroundup     /**< pointer to store whether best candidate should be rounded up */
433  	   )
434  	{
435  	   SCIP_Real bestscore;
436  	   int c;
437  	
438  	   /* check preconditions */
439  	   assert(scip != NULL);
440  	   assert(heurdata != NULL);
441  	   assert(nlpcands != NULL);
442  	   assert(nlpcandsfrac != NULL);
443  	   assert(nlpcandssol != NULL);
444  	   assert(bestcand != NULL);
445  	   assert(bestcandmayround != NULL);
446  	   assert(bestcandroundup != NULL);
447  	
448  	   *bestcandmayround = TRUE;
449  	   bestscore = SCIP_REAL_MAX;
450  	
451  	   /* get best candidate */
452  	   for( c = 0; c < nnlpcands; ++c )
453  	   {
454  	      SCIP_VAR* var;
455  	
456  	      SCIP_Real obj;
457  	      SCIP_Real objdelta;
458  	      SCIP_Real frac;
459  	      SCIP_Real score;
460  	
461  	      int nlocks;
462  	
463  	      SCIP_Bool roundup;
464  	
465  	      var = nlpcands[c];
466  	
467  	      /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
468  	      if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
469  	         continue;
470  	
471  	      frac = nlpcandsfrac[c];
472  	      obj = SCIPvarGetObj(var);
473  	      roundup = (obj >= 0.0);
474  	      objdelta = (roundup ? (1.0-frac)*obj : -frac * obj);
475  	      assert(objdelta >= 0.0);
476  	
477  	      /* check whether the variable is roundable */
478  	      *bestcandmayround = *bestcandmayround && (SCIPvarMayRoundDown(var) || SCIPvarMayRoundUp(var));
479  	      nlocks = SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) + SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL);
480  	
481  	      /* smaller score is better */
482  	      score = (objdelta + SCIPsumepsilon(scip))/((SCIP_Real)nlocks+1.0);
483  	
484  	      /* prefer decisions on binary variables */
485  	      if( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY )
486  	         score *= 1000.0;
487  	
488  	      /* prefer decisions on cover variables */
489  	      if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) )
490  	         score *= 1000;
491  	
492  	      /* check, if candidate is new best candidate */
493  	      if( score < bestscore )
494  	      {
495  	         *bestcand = c;
496  	         bestscore = score;
497  	         *bestcandroundup = roundup;
498  	      }
499  	   }
500  	
501  	   return SCIP_OKAY;
502  	}
503  	
504  	
505  	/** finds best candidate variable w.r.t. locking numbers:
506  	 * - prefer variables that may not be rounded without destroying LP feasibility:
507  	 *   - of these variables, round variable with least number of locks in corresponding direction
508  	 * - if all remaining fractional variables may be rounded without destroying LP feasibility:
509  	 *   - round variable with least number of locks in opposite of its feasible rounding direction
510  	 * - binary variables are prefered
511  	 * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
512  	 *   also be prefered if a correpsonding parameter is set
513  	 */
514  	static
515  	SCIP_RETCODE chooseCoefVar(
516  	   SCIP*                 scip,               /**< original SCIP data structure */
517  	   SCIP_HEURDATA*        heurdata,           /**< heuristic data structure */
518  	   SCIP_VAR**            nlpcands,           /**< array of NLP fractional variables */
519  	   SCIP_Real*            nlpcandssol,        /**< array of NLP fractional variables solution values */
520  	   SCIP_Real*            nlpcandsfrac,       /**< array of NLP fractional variables fractionalities */
521  	   int                   nnlpcands,          /**< number of NLP fractional variables */
522  	   SCIP_HASHMAP*         varincover,         /**< hash map for variables */
523  	   SCIP_Bool             covercomputed,      /**< has a minimal cover been computed? */
524  	   int*                  bestcand,           /**< pointer to store the index of the best candidate variable */
525  	   SCIP_Bool*            bestcandmayround,   /**< pointer to store whether best candidate is trivially roundable */
526  	   SCIP_Bool*            bestcandroundup     /**< pointer to store whether best candidate should be rounded up */
527  	   )
528  	{
529  	   SCIP_Bool bestcandmayrounddown;
530  	   SCIP_Bool bestcandmayroundup;
531  	   int bestnviolrows;             /* number of violated rows for best candidate */
532  	   SCIP_Real bestcandfrac;        /* fractionality of best candidate */
533  	   int c;
534  	
535  	   /* check preconditions */
536  	   assert(scip != NULL);
537  	   assert(heurdata != NULL);
538  	   assert(nlpcands != NULL);
539  	   assert(nlpcandsfrac != NULL);
540  	   assert(nlpcandssol != NULL);
541  	   assert(bestcand != NULL);
542  	   assert(bestcandmayround != NULL);
543  	   assert(bestcandroundup != NULL);
544  	
545  	   bestcandmayrounddown = TRUE;
546  	   bestcandmayroundup = TRUE;
547  	   bestnviolrows = INT_MAX;
548  	   bestcandfrac = SCIP_INVALID;
549  	
550  	   /* get best candidate */
551  	   for( c = 0; c < nnlpcands; ++c )
552  	   {
553  	      SCIP_VAR* var;
554  	
555  	      int nlocksdown;
556  	      int nlocksup;
557  	      int nviolrows;
558  	
559  	      SCIP_Bool mayrounddown;
560  	      SCIP_Bool mayroundup;
561  	      SCIP_Bool roundup;
562  	      SCIP_Real frac;
563  	
564  	      var = nlpcands[c];
565  	      mayrounddown = SCIPvarMayRoundDown(var);
566  	      mayroundup = SCIPvarMayRoundUp(var);
567  	      frac = nlpcandsfrac[c];
568  	
569  	      /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
570  	      if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
571  	         continue;
572  	
573  	      if( mayrounddown || mayroundup )
574  	      {
575  	         /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
576  	         if( bestcandmayrounddown || bestcandmayroundup )
577  	         {
578  	            /* choose rounding direction:
579  	             * - if variable may be rounded in both directions, round corresponding to the fractionality
580  	             * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
581  	             *   the current fractional solution
582  	             */
583  	            if( mayrounddown && mayroundup )
584  	            {
585  	               if( SCIPisEQ(scip, frac, 0.5) )
586  	                  roundup = (SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0);
587  	               else
588  	                  roundup = (frac > 0.5);
589  	            }
590  	            else
591  	               roundup = mayrounddown;
592  	
593  	            if( roundup )
594  	            {
595  	               frac = 1.0 - frac;
596  	               nviolrows = SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL);
597  	            }
598  	            else
599  	               nviolrows = SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL);
600  	
601  	            /* penalize too small fractions */
602  	            if( SCIPisEQ(scip, frac, 0.01) )
603  	            {
604  	               /* try to avoid variability; decide randomly if the LP solution can contain some noise.
605  	                * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
606  	                */
607  	               if( SCIPrandomGetInt(heurdata->randnumgen, 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 )
608  	                  nviolrows *= 100;
609  	            }
610  	            else if( frac < 0.01 )
611  	               nviolrows *= 100;
612  	
613  	            /* prefer decisions on binary variables */
614  	            if( !SCIPvarIsBinary(var) )
615  	               nviolrows *= 1000;
616  	
617  	            /* prefer decisions on cover variables */
618  	            if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) )
619  	               nviolrows *= 1000;
620  	
621  	            /* check, if candidate is new best candidate */
622  	            assert( (0.0 < frac && frac < 1.0) || SCIPvarIsBinary(var) );
623  	            if( nviolrows + frac < bestnviolrows + bestcandfrac )
624  	            {
625  	               *bestcand = c;
626  	               bestnviolrows = nviolrows;
627  	               bestcandfrac = frac;
628  	               bestcandmayrounddown = mayrounddown;
629  	               bestcandmayroundup = mayroundup;
630  	               *bestcandroundup = roundup;
631  	            }
632  	         }
633  	      }
634  	      else
635  	      {
636  	         /* the candidate may not be rounded */
637  	         nlocksdown = SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL);
638  	         nlocksup = SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL);
639  	
640  	         roundup = (nlocksdown > nlocksup);
641  	         if( !roundup )
642  	         {
643  	            roundup = (nlocksdown == nlocksup);
644  	            if( SCIPisEQ(scip, frac, 0.5) )
645  	               roundup = (roundup && (SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0));
646  	            else
647  	               roundup = (roundup && frac > 0.5);
648  	         }
649  	
650  	         if( roundup )
651  	         {
652  	            nviolrows = nlocksup;
653  	            frac = 1.0 - frac;
654  	         }
655  	         else
656  	            nviolrows = nlocksdown;
657  	
658  	         /* penalize too small fractions */
659  	         if( SCIPisEQ(scip, frac, 0.01) )
660  	         {
661  	            /* try to avoid variability; decide randomly if the LP solution can contain some noise.
662  	             * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
663  	             */
664  	            if( SCIPrandomGetInt(heurdata->randnumgen, 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 )
665  	               nviolrows *= 100;
666  	         }
667  	         else if( frac < 0.01 )
668  	            nviolrows *= 100;
669  	
670  	         /* prefer decisions on binary variables */
671  	         if( !SCIPvarIsBinary(var) )
672  	            nviolrows *= 100;
673  	
674  	         /* prefer decisions on cover variables */
675  	         if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) )
676  	            nviolrows *= 1000;
677  	
678  	         /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
679  	         assert((0.0 < frac && frac < 1.0) || SCIPvarIsBinary(var));
680  	         if( bestcandmayrounddown || bestcandmayroundup || nviolrows + frac < bestnviolrows + bestcandfrac )
681  	         {
682  	            *bestcand = c;
683  	            bestnviolrows = nviolrows;
684  	            bestcandfrac = frac;
685  	            bestcandmayrounddown = FALSE;
686  	            bestcandmayroundup = FALSE;
687  	            *bestcandroundup = roundup;
688  	         }
689  	         assert(bestcandfrac < SCIP_INVALID);
690  	      }
691  	   }
692  	
693  	   *bestcandmayround = bestcandmayroundup || bestcandmayrounddown;
694  	
695  	   return SCIP_OKAY;
696  	}
697  	
698  	/** calculates the pseudocost score for a given variable w.r.t. a given solution value and a given rounding direction */
699  	static
700  	void calcPscostQuot(
701  	   SCIP*                 scip,               /**< SCIP data structure */
702  	   SCIP_HEURDATA*        heurdata,           /**< heuristic data structure */
703  	   SCIP_VAR*             var,                /**< problem variable */
704  	   SCIP_Real             primsol,            /**< primal solution of variable */
705  	   SCIP_Real             frac,               /**< fractionality of variable */
706  	   int                   rounddir,           /**< -1: round down, +1: round up, 0: select due to pseudo cost values */
707  	   SCIP_Real*            pscostquot,         /**< pointer to store pseudo cost quotient */
708  	   SCIP_Bool*            roundup,            /**< pointer to store whether the variable should be rounded up */
709  	   SCIP_Bool             prefvar             /**< should this variable be preferred because it is in a minimal cover? */
710  	   )
711  	{
712  	   SCIP_Real pscostdown;
713  	   SCIP_Real pscostup;
714  	
715  	   assert(heurdata != NULL);
716  	   assert(pscostquot != NULL);
717  	   assert(roundup != NULL);
718  	   assert(SCIPisEQ(scip, frac, primsol - SCIPfeasFloor(scip, primsol)));
719  	
720  	   /* bound fractions to not prefer variables that are nearly integral */
721  	   frac = MAX(frac, 0.1);
722  	   frac = MIN(frac, 0.9);
723  	
724  	   /* get pseudo cost quotient */
725  	   pscostdown = SCIPgetVarPseudocostVal(scip, var, 0.0-frac);
726  	   pscostup = SCIPgetVarPseudocostVal(scip, var, 1.0-frac);
727  	   assert(pscostdown >= 0.0 && pscostup >= 0.0);
728  	
729  	   /* choose rounding direction
730  	    *
731  	    * to avoid performance variability caused by numerics we use random numbers to decide whether we want to roundup or
732  	    * round down if the values to compare are equal within tolerances.
733  	    */
734  	   if( rounddir == -1 )
735  	      *roundup = FALSE;
736  	   else if( rounddir == +1 )
737  	      *roundup = TRUE;
738  	   else if( SCIPisLT(scip, primsol, SCIPvarGetRootSol(var) - 0.4)
739  	         || (SCIPisEQ(scip, primsol, SCIPvarGetRootSol(var) - 0.4) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) )
740  	      *roundup = FALSE;
741  	   else if( SCIPisGT(scip, primsol, SCIPvarGetRootSol(var) + 0.4)
742  	         || (SCIPisEQ(scip, primsol, SCIPvarGetRootSol(var) + 0.4) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) )
743  	      *roundup = TRUE;
744  	   else if( SCIPisLT(scip, frac, 0.3) || (SCIPisEQ(scip, frac, 0.3) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) )
745  	      *roundup = FALSE;
746  	   else if( SCIPisGT(scip, frac, 0.7) || (SCIPisEQ(scip, frac, 0.7) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) )
747  	      *roundup = TRUE;
748  	   else if( SCIPisLT(scip, pscostdown, pscostup)
749  	         || (SCIPisEQ(scip, pscostdown, pscostup) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0))
750  	      *roundup = FALSE;
751  	   else
752  	      *roundup = TRUE;
753  	
754  	   /* calculate pseudo cost quotient */
755  	   if( *roundup )
756  	      *pscostquot = sqrt(frac) * (1.0+pscostdown) / (1.0+pscostup);
757  	   else
758  	      *pscostquot = sqrt(1.0-frac) * (1.0+pscostup) / (1.0+pscostdown);
759  	
760  	   /* prefer decisions on binary variables */
761  	   if( SCIPvarIsBinary(var) )
762  	      (*pscostquot) *= 1000.0;
763  	
764  	   /* prefer decisions on cover variables */
765  	   if( prefvar )
766  	      (*pscostquot) *= 1000.0;
767  	}
768  	
769  	/** finds best candidate variable w.r.t. pseudo costs:
770  	 * - prefer variables that may not be rounded without destroying LP feasibility:
771  	 *   - of these variables, round variable with largest rel. difference of pseudo cost values in corresponding
772  	 *     direction
773  	 * - if all remaining fractional variables may be rounded without destroying LP feasibility:
774  	 *   - round variable in the objective value direction
775  	 * - binary variables are prefered
776  	 * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
777  	 *   also be prefered if a correpsonding parameter is set
778  	 */
779  	static
780  	SCIP_RETCODE choosePscostVar(
781  	   SCIP*                 scip,               /**< original SCIP data structure */
782  	   SCIP_HEURDATA*        heurdata,           /**< heuristic data structure */
783  	   SCIP_VAR**            nlpcands,           /**< array of NLP fractional variables */
784  	   SCIP_Real*            nlpcandssol,        /**< array of NLP fractional variables solution values */
785  	   SCIP_Real*            nlpcandsfrac,       /**< array of NLP fractional variables fractionalities */
786  	   int                   nnlpcands,          /**< number of NLP fractional variables */
787  	   SCIP_HASHMAP*         varincover,         /**< hash map for variables */
788  	   SCIP_Bool             covercomputed,      /**< has a minimal cover been computed? */
789  	   int*                  bestcand,           /**< pointer to store the index of the best candidate variable */
790  	   SCIP_Bool*            bestcandmayround,   /**< pointer to store whether best candidate is trivially roundable */
791  	   SCIP_Bool*            bestcandroundup     /**< pointer to store whether best candidate should be rounded up */
792  	   )
793  	{
794  	   SCIP_Bool bestcandmayrounddown;
795  	   SCIP_Bool bestcandmayroundup;
796  	   SCIP_Real bestpscostquot;
797  	   int c;
798  	
799  	   /* check preconditions */
800  	   assert(scip != NULL);
801  	   assert(heurdata != NULL);
802  	   assert(nlpcands != NULL);
803  	   assert(nlpcandsfrac != NULL);
804  	   assert(nlpcandssol != NULL);
805  	   assert(bestcand != NULL);
806  	   assert(bestcandmayround != NULL);
807  	   assert(bestcandroundup != NULL);
808  	
809  	   bestcandmayrounddown = TRUE;
810  	   bestcandmayroundup = TRUE;
811  	   bestpscostquot = -1.0;
812  	
813  	   for( c = 0; c < nnlpcands; ++c )
814  	   {
815  	      SCIP_VAR* var;
816  	      SCIP_Real primsol;
817  	
818  	      SCIP_Bool mayrounddown;
819  	      SCIP_Bool mayroundup;
820  	      SCIP_Bool roundup;
821  	      SCIP_Bool prefvar;
822  	      SCIP_Real frac;
823  	      SCIP_Real pscostquot;
824  	
825  	      var = nlpcands[c];
826  	      mayrounddown = SCIPvarMayRoundDown(var);
827  	      mayroundup = SCIPvarMayRoundUp(var);
828  	      primsol = nlpcandssol[c];
829  	      frac = nlpcandsfrac[c];
830  	      prefvar = covercomputed && heurdata->prefercover && SCIPhashmapExists(varincover, var);
831  	      pscostquot = SCIP_INVALID;
832  	
833  	      if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
834  	         continue;
835  	
836  	      if( mayrounddown || mayroundup )
837  	      {
838  	         /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
839  	         if( bestcandmayrounddown || bestcandmayroundup )
840  	         {
841  	            /* choose rounding direction:
842  	             * - if variable may be rounded in both directions, round corresponding to the pseudo cost values
843  	             * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
844  	             *   the current fractional solution
845  	             */
846  	            roundup = FALSE;
847  	            if( mayrounddown && mayroundup )
848  	               calcPscostQuot(scip, heurdata, var, primsol, frac, 0, &pscostquot, &roundup, prefvar);
849  	            else if( mayrounddown )
850  	               calcPscostQuot(scip, heurdata, var, primsol, frac, +1, &pscostquot, &roundup, prefvar);
851  	            else
852  	               calcPscostQuot(scip, heurdata, var, primsol, frac, -1, &pscostquot, &roundup, prefvar);
853  	
854  	            assert(!SCIPisInfinity(scip,ABS(pscostquot)));
855  	
856  	            /* check, if candidate is new best candidate */
857  	            if( pscostquot > bestpscostquot )
858  	            {
859  	               *bestcand = c;
860  	               bestpscostquot = pscostquot;
861  	               bestcandmayrounddown = mayrounddown;
862  	               bestcandmayroundup = mayroundup;
863  	               *bestcandroundup = roundup;
864  	            }
865  	         }
866  	      }
867  	      else
868  	      {
869  	         /* the candidate may not be rounded: calculate pseudo cost quotient and preferred direction */
870  	         calcPscostQuot(scip, heurdata, var, primsol, frac, 0, &pscostquot, &roundup, prefvar);
871  	         assert(!SCIPisInfinity(scip,ABS(pscostquot)));
872  	
873  	         /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
874  	         if( bestcandmayrounddown || bestcandmayroundup || pscostquot > bestpscostquot )
875  	         {
876  	            *bestcand = c;
877  	            bestpscostquot = pscostquot;
878  	            bestcandmayrounddown = FALSE;
879  	            bestcandmayroundup = FALSE;
880  	            *bestcandroundup = roundup;
881  	         }
882  	      }
883  	   }
884  	
885  	   *bestcandmayround = bestcandmayroundup || bestcandmayrounddown;
886  	
887  	   return SCIP_OKAY;
888  	}
889  	
890  	/** finds best candidate variable w.r.t. the incumbent solution:
891  	 * - prefer variables that may not be rounded without destroying LP feasibility:
892  	 *   - of these variables, round a variable to its value in direction of incumbent solution, and choose the
893  	 *     variable that is closest to its rounded value
894  	 * - if all remaining fractional variables may be rounded without destroying LP feasibility:
895  	 *   - round variable in direction that destroys LP feasibility (other direction is checked by SCIProundSol())
896  	 *   - round variable with least increasing objective value
897  	 * - binary variables are prefered
898  	 * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
899  	 *   also be prefered if a correpsonding parameter is set
900  	 */
901  	static
902  	SCIP_RETCODE chooseGuidedVar(
903  	   SCIP*                 scip,               /**< original SCIP data structure */
904  	   SCIP_HEURDATA*        heurdata,           /**< heuristic data structure */
905  	   SCIP_VAR**            nlpcands,           /**< array of NLP fractional variables */
906  	   SCIP_Real*            nlpcandssol,        /**< array of NLP fractional variables solution values */
907  	   SCIP_Real*            nlpcandsfrac,       /**< array of NLP fractional variables fractionalities */
908  	   int                   nnlpcands,          /**< number of NLP fractional variables */
909  	   SCIP_SOL*             bestsol,            /**< incumbent solution */
910  	   SCIP_HASHMAP*         varincover,         /**< hash map for variables */
911  	   SCIP_Bool             covercomputed,      /**< has a minimal cover been computed? */
912  	   int*                  bestcand,           /**< pointer to store the index of the best candidate variable */
913  	   SCIP_Bool*            bestcandmayround,   /**< pointer to store whether best candidate is trivially roundable */
914  	   SCIP_Bool*            bestcandroundup     /**< pointer to store whether best candidate should be rounded up */
915  	   )
916  	{
917  	   SCIP_Real bestobjgain;
918  	   SCIP_Real bestfrac;
919  	   SCIP_Bool bestcandmayrounddown;
920  	   SCIP_Bool bestcandmayroundup;
921  	   int c;
922  	
923  	   /* check preconditions */
924  	   assert(scip != NULL);
925  	   assert(heurdata != NULL);
926  	   assert(nlpcands != NULL);
927  	   assert(nlpcandsfrac != NULL);
928  	   assert(nlpcandssol != NULL);
929  	   assert(bestcand != NULL);
930  	   assert(bestcandmayround != NULL);
931  	   assert(bestcandroundup != NULL);
932  	
933  	   bestcandmayrounddown = TRUE;
934  	   bestcandmayroundup = TRUE;
935  	   bestobjgain = SCIPinfinity(scip);
936  	   bestfrac = SCIP_INVALID;
937  	
938  	   for( c = 0; c < nnlpcands; ++c )
939  	   {
940  	      SCIP_VAR* var;
941  	      SCIP_Real bestsolval;
942  	      SCIP_Real solval;
943  	      SCIP_Real obj;
944  	      SCIP_Real frac;
945  	      SCIP_Real objgain;
946  	
947  	      SCIP_Bool mayrounddown;
948  	      SCIP_Bool mayroundup;
949  	      SCIP_Bool roundup;
950  	
951  	      var = nlpcands[c];
952  	      mayrounddown = SCIPvarMayRoundDown(var);
953  	      mayroundup = SCIPvarMayRoundUp(var);
954  	      solval = nlpcandssol[c];
955  	      frac = nlpcandsfrac[c];
956  	      obj = SCIPvarGetObj(var);
957  	      bestsolval = SCIPgetSolVal(scip, bestsol, var);
958  	
959  	      /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
960  	      if( SCIPisLT(scip, solval, SCIPvarGetLbLocal(var)) || SCIPisGT(scip, solval, SCIPvarGetUbLocal(var)) )
961  	         continue;
962  	
963  	      /* select default rounding direction
964  	       * try to avoid variability; decide randomly if the LP solution can contain some noise
965  	       */
966  	      if( SCIPisEQ(scip, solval, bestsolval) )
967  	         roundup = (SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0);
968  	      else
969  	         roundup = (solval < bestsolval);
970  	
971  	      if( mayrounddown || mayroundup )
972  	      {
973  	         /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
974  	         if( bestcandmayrounddown || bestcandmayroundup )
975  	         {
976  	            /* choose rounding direction:
977  	             * - if variable may be rounded in both directions, round corresponding to its value in incumbent solution
978  	             * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
979  	             *   the current fractional solution with SCIProundSol()
980  	             */
981  	            if( !mayrounddown || !mayroundup )
982  	               roundup = mayrounddown;
983  	
984  	            if( roundup )
985  	            {
986  	               frac = 1.0 - frac;
987  	               objgain = frac*obj;
988  	            }
989  	            else
990  	               objgain = -frac*obj;
991  	
992  	            /* penalize too small fractions */
993  	            if( SCIPisEQ(scip, frac, 0.01) )
994  	            {
995  	               /* try to avoid variability; decide randomly if the LP solution can contain some noise.
996  	                * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
997  	                */
998  	               if( SCIPrandomGetInt(heurdata->randnumgen, 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 )
999  	                  objgain *= 1000.0;
1000 	            }
1001 	            else if( frac < 0.01 )
1002 	               objgain *= 1000.0;
1003 	
1004 	            /* prefer decisions on binary variables */
1005 	            if( !SCIPvarIsBinary(var) )
1006 	               objgain *= 1000.0;
1007 	
1008 	            /* prefer decisions on cover variables */
1009 	            if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) )
1010 	               objgain *= 1000.0;
1011 	
1012 	            /* check, if candidate is new best candidate */
1013 	            if( SCIPisLT(scip, objgain, bestobjgain) || (SCIPisEQ(scip, objgain, bestobjgain) && frac < bestfrac) )
1014 	            {
1015 	               *bestcand = c;
1016 	               bestobjgain = objgain;
1017 	               bestfrac = frac;
1018 	               bestcandmayrounddown = mayrounddown;
1019 	               bestcandmayroundup = mayroundup;
1020 	               *bestcandroundup = roundup;
1021 	            }
1022 	         }
1023 	      }
1024 	      else
1025 	      {
1026 	         /* the candidate may not be rounded */
1027 	         if( roundup )
1028 	            frac = 1.0 - frac;
1029 	
1030 	         /* penalize too small fractions */
1031 	         if( SCIPisEQ(scip, frac, 0.01) )
1032 	         {
1033 	            /* try to avoid variability; decide randomly if the LP solution can contain some noise.
1034 	             * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
1035 	             */
1036 	            if( SCIPrandomGetInt(heurdata->randnumgen, 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 )
1037 	               frac += 10.0;
1038 	         }
1039 	         else if( frac < 0.01 )
1040 	            frac += 10.0;
1041 	
1042 	         /* prefer decisions on binary variables */
1043 	         if( !SCIPvarIsBinary(var) )
1044 	            frac *= 1000.0;
1045 	
1046 	         /* prefer decisions on cover variables */
1047 	         if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) )
1048 	            frac *= 1000.0;
1049 	
1050 	         /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
1051 	         if( bestcandmayrounddown || bestcandmayroundup || frac < bestfrac )
1052 	         {
1053 	            *bestcand = c;
1054 	            bestfrac = frac;
1055 	            bestcandmayrounddown = FALSE;
1056 	            bestcandmayroundup = FALSE;
1057 	            *bestcandroundup = roundup;
1058 	         }
1059 	      }
1060 	   }
1061 	
1062 	   *bestcandmayround = bestcandmayroundup || bestcandmayrounddown;
1063 	
1064 	   return SCIP_OKAY;
1065 	}
1066 	
1067 	/** finds best candidate variable w.r.t. both, the LP and the NLP solution:
1068 	 * - choose a variable for which the sum of the distances from the relaxations' solutions to a common
1069 	 *   integer value is minimal
1070 	 * - binary variables are prefered
1071 	 * - variables in a minimal cover might be prefered if a corresponding parameter is set
1072 	 */
1073 	static
1074 	SCIP_RETCODE chooseDoubleVar(
1075 	   SCIP*                 scip,               /**< original SCIP data structure */
1076 	   SCIP_HEURDATA*        heurdata,           /**< heuristic data structure */
1077 	   SCIP_VAR**            pseudocands,        /**< array of non-fixed variables */
1078 	   SCIP_Real*            pseudocandsnlpsol,  /**< array of NLP solution values */
1079 	   SCIP_Real*            pseudocandslpsol,   /**< array of LP solution values */
1080 	   int                   npseudocands,       /**< number of NLP fractional variables */
1081 	   SCIP_HASHMAP*         varincover,         /**< hash map for variables */
1082 	   SCIP_Bool             covercomputed,      /**< has a minimal cover been computed? */
1083 	   int*                  bestcand,           /**< pointer to store the index of the best candidate variable */
1084 	   SCIP_Real*            bestboundval,       /**< pointer to store the bound, the best candidate should be rounded to */
1085 	   SCIP_Bool*            bestcandmayround,   /**< pointer to store whether best candidate is trivially roundable */
1086 	   SCIP_Bool*            bestcandroundup     /**< pointer to store whether best candidate should be rounded up */
1087 	   )
1088 	{
1089 	   SCIP_Real bestfrac;
1090 	   int c;
1091 	
1092 	   /* check preconditions */
1093 	   assert(scip != NULL);
1094 	   assert(heurdata != NULL);
1095 	   assert(pseudocands != NULL);
1096 	   assert(pseudocandsnlpsol != NULL);
1097 	   assert(pseudocandslpsol != NULL);
1098 	   assert(covercomputed == (varincover != NULL));
1099 	   assert(bestcand != NULL);
1100 	   assert(bestcandmayround != NULL);
1101 	   assert(bestcandroundup != NULL);
1102 	
1103 	   bestfrac = SCIP_INVALID;
1104 	
1105 	   for( c = 0; c < npseudocands; ++c )
1106 	   {
1107 	      SCIP_VAR* var;
1108 	      SCIP_Bool mayround;
1109 	      SCIP_Bool roundup;
1110 	
1111 	      SCIP_Real frac;
1112 	      SCIP_Real lpsol;
1113 	      SCIP_Real nlpsol;
1114 	      SCIP_Real lpsolfloor;
1115 	      SCIP_Real nlpsolfloor;
1116 	      SCIP_Real lpsolceil;
1117 	      SCIP_Real nlpsolceil;
1118 	      SCIP_Real boundval;
1119 	      SCIP_Real floorval;
1120 	      SCIP_Real ceilval;
1121 	
1122 	      var = pseudocands[c];
1123 	      lpsol = pseudocandslpsol[c];
1124 	      nlpsol = pseudocandsnlpsol[c];
1125 	
1126 	      assert(SCIPvarGetUbLocal(var)-SCIPvarGetLbLocal(var) > 0.5);
1127 	      assert(SCIPisLE(scip, SCIPvarGetLbLocal(var), lpsol) && SCIPisLE(scip, lpsol, SCIPvarGetUbLocal(var)));
1128 	
1129 	      /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
1130 	      if( SCIPisLT(scip, nlpsol, SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpsol, SCIPvarGetUbLocal(var)) )
1131 	         continue;
1132 	
1133 	      mayround = SCIPvarMayRoundDown(var) || SCIPvarMayRoundUp(var);
1134 	
1135 	      /* if this candidate is trivially roundable, and we already know a candidate that is not, continue */
1136 	      if( mayround && !(*bestcandmayround) )
1137 	         continue;
1138 	
1139 	      if( SCIPisFeasEQ(scip, lpsol, nlpsol) && SCIPisFeasIntegral(scip, lpsol))
1140 	         continue;
1141 	
1142 	      lpsolfloor = SCIPfeasFloor(scip, lpsol);
1143 	      nlpsolfloor =  SCIPfeasFloor(scip, nlpsol);
1144 	      lpsolceil = SCIPfeasCeil(scip, lpsol);
1145 	      nlpsolceil =  SCIPfeasCeil(scip, nlpsol);
1146 	      floorval = MIN(lpsolfloor,nlpsolfloor);
1147 	      ceilval =  MAX(lpsolceil,nlpsolceil);
1148 	
1149 	      /* if both values are in the same interval, find out which integer is (in sum) the closer one, this will be the
1150 	       * new bound. The minima and maxima are necessary since one or both values with be integer
1151 	       */
1152 	      if( SCIPvarIsBinary(var) || ceilval-floorval < 1.5 )
1153 	      {
1154 	         frac = 0.33*(lpsol-floorval) + 0.67*(nlpsol-floorval);
1155 	         if( frac < 0.5 )
1156 	         {
1157 	            roundup = FALSE;
1158 	            boundval = MIN(lpsolfloor,nlpsolfloor);
1159 	         }
1160 	         else
1161 	         {
1162 	            roundup = TRUE;
1163 	            frac = 1.0-frac;
1164 	            boundval = MAX(nlpsolceil,lpsolceil);
1165 	         }
1166 	      }
1167 	      else
1168 	      {
1169 	         /* determine new bound in the middle of both relaxations, such that the NLP stays feasible */
1170 	         SCIP_Real midval;
1171 	         midval = (nlpsol+lpsol)/2.0;
1172 	         roundup = nlpsol > lpsol;
1173 	         frac = ABS(nlpsol-lpsol);
1174 	
1175 	         if( roundup )
1176 	            boundval = SCIPfeasCeil(scip, midval);
1177 	         else
1178 	            boundval = SCIPfeasFloor(scip, midval);
1179 	
1180 	         assert(roundup == SCIPisGT(scip, nlpsol, boundval));
1181 	      }
1182 	
1183 	      /* penalize too small fractions */
1184 	      if( SCIPisEQ(scip, frac, 0.01) )
1185 	      {
1186 	         /* try to avoid variability; decide randomly if the LP solution can contain some noise.
1187 	          * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
1188 	          */
1189 	         if( SCIPrandomGetInt(heurdata->randnumgen, 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 )
1190 	            frac += 10.0;
1191 	      }
1192 	      else if( frac < 0.01 )
1193 	         frac += 10.0;
1194 	
1195 	      /* prefer decisions on binary variables */
1196 	      if( !SCIPvarIsBinary(var) )
1197 	         frac *= 1000.0;
1198 	
1199 	      /* prefer decisions on cover variables */
1200 	      if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) )
1201 	         frac *= 1000.0;
1202 	
1203 	      /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
1204 	      if( frac < bestfrac || (*bestcandmayround && !mayround) )
1205 	      {
1206 	         *bestcand = c;
1207 	         bestfrac = frac;
1208 	         *bestcandmayround = FALSE;
1209 	         *bestcandroundup = roundup;
1210 	         *bestboundval = boundval;
1211 	      }
1212 	      assert(bestfrac < SCIP_INVALID);
1213 	   }
1214 	
1215 	   if( *bestcandroundup )
1216 	      *bestboundval -= 0.5;
1217 	   else
1218 	      *bestboundval += 0.5;
1219 	
1220 	   return SCIP_OKAY;
1221 	}
1222 	
1223 	/** creates a new solution for the original problem by copying the solution of the subproblem */
1224 	static
1225 	SCIP_RETCODE createNewSol(
1226 	   SCIP*                 scip,               /**< original SCIP data structure                        */
1227 	   SCIP*                 subscip,            /**< SCIP structure of the subproblem                    */
1228 	   SCIP_HEUR*            heur,               /**< heuristic structure                                 */
1229 	   SCIP_HASHMAP*         varmap,             /**< hash map for variables */
1230 	   SCIP_SOL*             subsol,             /**< solution of the subproblem                          */
1231 	   SCIP_Bool*            success             /**< used to store whether new solution was found or not */
1232 	   )
1233 	{
1234 	   SCIP_VAR** vars;                          /* the original problem's variables                */
1235 	   SCIP_Real* subsolvals;                    /* solution values of the subproblem               */
1236 	   SCIP_SOL*  newsol;                        /* solution to be created for the original problem */
1237 	   int        nvars;                         /* the original problem's number of variables      */
1238 	   SCIP_VAR* subvar;
1239 	   int i;
1240 	
1241 	   assert(scip != NULL);
1242 	   assert(subscip != NULL);
1243 	   assert(subsol != NULL);
1244 	
1245 	   /* get variables' data */
1246 	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
1247 	
1248 	   SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
1249 	
1250 	   /* copy the solution */
1251 	   for( i = 0; i < nvars; ++i )
1252 	   {
1253 	      subvar = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[i]);
1254 	      if( subvar == NULL )
1255 	         subsolvals[i] = MIN(MAX(0.0, SCIPvarGetLbLocal(vars[i])), SCIPvarGetUbLocal(vars[i]));  /*lint !e666*/
1256 	      else
1257 	         subsolvals[i] = SCIPgetSolVal(subscip, subsol, subvar);
1258 	   }
1259 	
1260 	   /* create new solution for the original problem */
1261 	   SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
1262 	   SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
1263 	
1264 	   /* try to add new solution to scip and free it immediately */
1265 	   SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
1266 	
1267 	   SCIPfreeBufferArray(scip, &subsolvals);
1268 	
1269 	   return SCIP_OKAY;
1270 	}
1271 	
1272 	/** todo setup and solve the subMIP */
1273 	static
1274 	SCIP_RETCODE doSolveSubMIP(
1275 	   SCIP*                 scip,               /**< SCIP data structure */
1276 	   SCIP*                 subscip,            /**< NLP diving subscip */
1277 	   SCIP_HEUR*            heur,               /**< heuristic data structure */
1278 	   SCIP_VAR**            covervars,          /**< variables in the cover, should be fixed locally */
1279 	   int                   ncovervars,         /**< number of variables in the cover */
1280 	   SCIP_Bool*            success             /**< pointer to store whether a solution was found */
1281 	   )
1282 	{
1283 	   SCIP_HASHMAP* varmap;
1284 	   SCIP_SOL** subsols;
1285 	   int c;
1286 	   int nsubsols;
1287 	
1288 	   assert(subscip != NULL);
1289 	   assert(scip != NULL);
1290 	   assert(heur != NULL);
1291 	
1292 	   /* create the variable mapping hash map */
1293 	   SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(subscip), SCIPgetNVars(scip)) );
1294 	
1295 	   *success = FALSE;
1296 	
1297 	   /* copy original problem to subproblem; do not copy pricers */
1298 	   SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmap, NULL, "undercoversub", NULL, NULL, 0, FALSE, FALSE, FALSE,
1299 	         TRUE, NULL) );
1300 	
1301 	   /* assert that cover variables are fixed in source and target SCIP */
1302 	   for( c = 0; c < ncovervars; c++)
1303 	   {
1304 	      assert(SCIPhashmapGetImage(varmap, covervars[c]) != NULL);  /* cover variable cannot be relaxation-only, thus must have been copied */
1305 	      assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(covervars[c]), SCIPvarGetUbLocal(covervars[c])));
1306 	      assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal((SCIP_VAR*) SCIPhashmapGetImage(varmap, covervars[c])),
1307 	            SCIPvarGetUbGlobal((SCIP_VAR*) SCIPhashmapGetImage(varmap, covervars[c]))));
1308 	   }
1309 	
1310 	   /* set parameters for sub-SCIP */
1311 	
1312 	   /* do not abort subproblem on CTRL-C */
1313 	   SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
1314 	
1315 	#ifdef SCIP_DEBUG
1316 	   /* for debugging, enable full output */
1317 	   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
1318 	   SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
1319 	#else
1320 	   /* disable statistic timing inside sub SCIP and output to console */
1321 	   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
1322 	   SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
1323 	#endif
1324 	
1325 	   /* set limits for the subproblem */
1326 	   SCIP_CALL( SCIPcopyLimits(scip, subscip) );
1327 	   SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", (SCIP_Longint)100) );
1328 	   SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", (SCIP_Longint)500) );
1329 	
1330 	   /* forbid recursive call of heuristics and separators solving sub-SCIPs */
1331 	   SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
1332 	
1333 	   /* disable cutting plane separation */
1334 	   SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
1335 	
1336 	   /* disable expensive presolving */
1337 	   SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
1338 	
1339 	   /* use best estimate node selection */
1340 	   if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
1341 	   {
1342 	      SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
1343 	   }
1344 	
1345 	   /* use inference branching */
1346 	   if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
1347 	   {
1348 	      SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
1349 	   }
1350 	
1351 	   /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */
1352 	   if( !SCIPisParamFixed(subscip, "conflict/enable") )
1353 	   {
1354 	      SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) );
1355 	   }
1356 	   if( !SCIPisParamFixed(subscip, "conflict/useboundlp") )
1357 	   {
1358 	      SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') );
1359 	   }
1360 	   if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") )
1361 	   {
1362 	      SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) );
1363 	   }
1364 	
1365 	   if( SCIPgetNSols(scip) > 0 )
1366 	   {
1367 	      SCIP_Real upperbound;
1368 	      SCIP_Real cutoffbound;
1369 	      SCIP_Real minimprove;
1370 	
1371 	      assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
1372 	
1373 	      upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
1374 	      minimprove = 0.01;
1375 	
1376 	      if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(scip)) )
1377 	      {
1378 	         cutoffbound = (1-minimprove)*SCIPgetUpperbound(scip) + minimprove*SCIPgetLowerbound(scip);
1379 	      }
1380 	      else
1381 	      {
1382 	         if( SCIPgetUpperbound(scip) >= 0 )
1383 	            cutoffbound = (1 - minimprove)*SCIPgetUpperbound(scip);
1384 	         else
1385 	            cutoffbound = (1 + minimprove)*SCIPgetUpperbound(scip);
1386 	      }
1387 	      cutoffbound = MIN(upperbound, cutoffbound);
1388 	      SCIP_CALL( SCIPsetObjlimit(subscip, cutoffbound) );
1389 	   }
1390 	
1391 	   SCIP_CALL_ABORT( SCIPsolve(subscip) );
1392 	
1393 	   /* check, whether a solution was found;
1394 	    * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
1395 	    */
1396 	   nsubsols = SCIPgetNSols(subscip);
1397 	   subsols = SCIPgetSols(subscip);
1398 	   for( c = 0; c < nsubsols && !(*success); ++c )
1399 	   {
1400 	      SCIP_CALL( createNewSol(scip, subscip, heur, varmap, subsols[c], success) );
1401 	   }
1402 	
1403 	   SCIPhashmapFree(&varmap);
1404 	
1405 	   return SCIP_OKAY;
1406 	}
1407 	
1408 	
1409 	/** solves subproblem and passes best feasible solution to original SCIP instance */
1410 	static
1411 	SCIP_RETCODE solveSubMIP(
1412 	   SCIP*                 scip,               /**< SCIP data structure of the original problem */
1413 	   SCIP_HEUR*            heur,               /**< heuristic data structure */
1414 	   SCIP_VAR**            covervars,          /**< variables in the cover, should be fixed locally */
1415 	   int                   ncovervars,         /**< number of variables in the cover */
1416 	   SCIP_Bool*            success             /**< pointer to store whether a solution was found */
1417 	   )
1418 	{
1419 	   SCIP* subscip;
1420 	   SCIP_RETCODE retcode;
1421 	
1422 	   /* check whether there is enough time and memory left */
1423 	   SCIP_CALL( SCIPcheckCopyLimits(scip, success) );
1424 	
1425 	   if( !(*success) )
1426 	      return SCIP_OKAY;
1427 	
1428 	   /* create subproblem */
1429 	   SCIP_CALL( SCIPcreate(&subscip) );
1430 	
1431 	   retcode = doSolveSubMIP(scip, subscip, heur, covervars, ncovervars, success);
1432 	
1433 	   /* free sub-SCIP even if an error occurred during the subscip solve */
1434 	   SCIP_CALL( SCIPfree(&subscip) );
1435 	
1436 	   SCIP_CALL( retcode );
1437 	
1438 	   return SCIP_OKAY;
1439 	}
1440 	
1441 	/* ---------------- Callback methods of event handler ---------------- */
1442 	
1443 	/* exec the event handler
1444 	 *
1445 	 * We update the number of variables fixed in the cover
1446 	 */
1447 	static
1448 	SCIP_DECL_EVENTEXEC(eventExecNlpdiving)
1449 	{
1450 	   SCIP_EVENTTYPE eventtype;
1451 	   SCIP_HEURDATA* heurdata;
1452 	   SCIP_VAR* var;
1453 	
1454 	   SCIP_Real oldbound;
1455 	   SCIP_Real newbound;
1456 	   SCIP_Real otherbound;
1457 	
1458 	   assert(eventhdlr != NULL);
1459 	   assert(eventdata != NULL);
1460 	   assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
1461 	   assert(event != NULL);
1462 	
1463 	   heurdata = (SCIP_HEURDATA*)eventdata;
1464 	   assert(heurdata != NULL);
1465 	   assert(0 <= heurdata->nfixedcovervars && heurdata->nfixedcovervars <= SCIPgetNVars(scip));
1466 	
1467 	   oldbound = SCIPeventGetOldbound(event);
1468 	   newbound = SCIPeventGetNewbound(event);
1469 	   var = SCIPeventGetVar(event);
1470 	
1471 	   eventtype = SCIPeventGetType(event);
1472 	   otherbound = (eventtype & SCIP_EVENTTYPE_LBCHANGED) ? SCIPvarGetUbLocal(var) : SCIPvarGetLbLocal(var);
1473 	
1474 	   switch( eventtype )
1475 	   {
1476 	   case SCIP_EVENTTYPE_LBTIGHTENED:
1477 	   case SCIP_EVENTTYPE_UBTIGHTENED:
1478 	      /* if cover variable is now fixed */
1479 	      if( SCIPisFeasEQ(scip, newbound, otherbound) && !SCIPisFeasEQ(scip, oldbound, otherbound) )
1480 	      {
1481 	         assert(!SCIPisEQ(scip, oldbound, otherbound));
1482 	         ++(heurdata->nfixedcovervars);
1483 	      }
1484 	      break;
1485 	   case SCIP_EVENTTYPE_LBRELAXED:
1486 	   case SCIP_EVENTTYPE_UBRELAXED:
1487 	      /* if cover variable is now unfixed */
1488 	      if( SCIPisFeasEQ(scip, oldbound, otherbound) && !SCIPisFeasEQ(scip, newbound, otherbound) )
1489 	      {
1490 	         assert(!SCIPisEQ(scip, newbound, otherbound));
1491 	         --(heurdata->nfixedcovervars);
1492 	      }
1493 	      break;
1494 	   default:
1495 	      SCIPerrorMessage("invalid event type.\n");
1496 	      return SCIP_INVALIDDATA;
1497 	   }
1498 	   assert(0 <= heurdata->nfixedcovervars && heurdata->nfixedcovervars <= SCIPgetNVars(scip));
1499 	
1500 	   /* SCIPdebugMsg(scip, "changed bound of cover variable <%s> from %f to %f (nfixedcovervars: %d).\n", SCIPvarGetName(var),
1501 	      oldbound, newbound, heurdata->nfixedcovervars); */
1502 	
1503 	   return SCIP_OKAY;
1504 	}
1505 	
1506 	
1507 	/*
1508 	 * Callback methods
1509 	 */
1510 	
1511 	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
1512 	static
1513 	SCIP_DECL_HEURCOPY(heurCopyNlpdiving)
1514 	{  /*lint --e{715}*/
1515 	   assert(scip != NULL);
1516 	   assert(heur != NULL);
1517 	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1518 	
1519 	   /* call inclusion method of primal heuristic */
1520 	   SCIP_CALL( SCIPincludeHeurNlpdiving(scip) );
1521 	
1522 	   return SCIP_OKAY;
1523 	}
1524 	
1525 	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
1526 	static
1527 	SCIP_DECL_HEURFREE(heurFreeNlpdiving) /*lint --e{715}*/
1528 	{  /*lint --e{715}*/
1529 	   SCIP_HEURDATA* heurdata;
1530 	
1531 	   assert(heur != NULL);
1532 	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1533 	   assert(scip != NULL);
1534 	
1535 	   /* free heuristic data */
1536 	   heurdata = SCIPheurGetData(heur);
1537 	   assert(heurdata != NULL);
1538 	   SCIPfreeBlockMemory(scip, &heurdata);
1539 	   SCIPheurSetData(heur, NULL);
1540 	
1541 	   return SCIP_OKAY;
1542 	}
1543 	
1544 	
1545 	/** initialization method of primal heuristic (called after problem was transformed) */
1546 	static
1547 	SCIP_DECL_HEURINIT(heurInitNlpdiving) /*lint --e{715}*/
1548 	{  /*lint --e{715}*/
1549 	   SCIP_HEURDATA* heurdata;
1550 	
1551 	   assert(heur != NULL);
1552 	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1553 	
1554 	   /* get heuristic data */
1555 	   heurdata = SCIPheurGetData(heur);
1556 	   assert(heurdata != NULL);
1557 	
1558 	   /* create working solution */
1559 	   SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
1560 	
1561 	   /* create random number generator */
1562 	   SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE) );
1563 	
1564 	   /* initialize data */
1565 	   heurdata->nnlpiterations = 0;
1566 	   heurdata->nsuccess = 0;
1567 	   heurdata->nfixedcovervars = 0;
1568 	   SCIPstatistic(
1569 	      heurdata->nnlpsolves = 0;
1570 	      heurdata->nfailcutoff = 0;
1571 	      heurdata->nfaildepth = 0;
1572 	      heurdata->nfailnlperror = 0;
1573 	      );
1574 	
1575 	   return SCIP_OKAY;
1576 	}
1577 	
1578 	
1579 	/** deinitialization method of primal heuristic (called before transformed problem is freed) */
1580 	static
1581 	SCIP_DECL_HEUREXIT(heurExitNlpdiving) /*lint --e{715}*/
1582 	{  /*lint --e{715}*/
1583 	   SCIP_HEURDATA* heurdata;
1584 	
1585 	   assert(heur != NULL);
1586 	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1587 	
1588 	   /* get heuristic data */
1589 	   heurdata = SCIPheurGetData(heur);
1590 	   assert(heurdata != NULL);
1591 	
1592 	   /* free random number generator */
1593 	   SCIPfreeRandom(scip, &heurdata->randnumgen);
1594 	
1595 	   /* free working solution */
1596 	   SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
1597 	
1598 	   SCIPstatistic(
1599 	      if( strstr(SCIPgetProbName(scip), "_covering") == NULL && SCIPheurGetNCalls(heur) > 0 )
1600 	      {
1601 	         SCIPstatisticMessage("%-30s %5" SCIP_LONGINT_FORMAT " sols in %5" SCIP_LONGINT_FORMAT " runs, %6.1fs, %7d NLP iters in %5d NLP solves, %5.1f avg., %3d%% success %3d%% cutoff %3d%% depth %3d%% nlperror\n",
1602 	            SCIPgetProbName(scip), SCIPheurGetNSolsFound(heur), SCIPheurGetNCalls(heur), SCIPheurGetTime(heur),
1603 	            heurdata->nnlpiterations, heurdata->nnlpsolves, heurdata->nnlpiterations/MAX(1.0,(SCIP_Real)heurdata->nnlpsolves),
1604 	            (100*heurdata->nsuccess) / (int)SCIPheurGetNCalls(heur), (100*heurdata->nfailcutoff) / (int)SCIPheurGetNCalls(heur), (100*heurdata->nfaildepth) / (int)SCIPheurGetNCalls(heur), (100*heurdata->nfailnlperror) / (int)SCIPheurGetNCalls(heur)
1605 	            );
1606 	      }
1607 	      );
1608 	
1609 	   return SCIP_OKAY;
1610 	}
1611 	
1612 	/** execution method of primal heuristic */
1613 	static
1614 	SCIP_DECL_HEUREXEC(heurExecNlpdiving)
1615 	{  /*lint --e{715}*/
1616 	   SCIP_HEURDATA* heurdata;
1617 	   SCIP_NLPSOLSTAT nlpsolstat;
1618 	   SCIP_LPSOLSTAT lpsolstat;
1619 	   SCIP_SOL* nlpstartsol;
1620 	   SCIP_SOL* bestsol;
1621 	   SCIP_VAR** nlpcands;
1622 	   SCIP_VAR** covervars;
1623 	   SCIP_Real* nlpcandssol;
1624 	   SCIP_Real* nlpcandsfrac;
1625 	   SCIP_Real* pseudocandslpsol;
1626 	   SCIP_Real* pseudocandsnlpsol;
1627 	   SCIP_HASHMAP* varincover;
1628 	   SCIP_Real searchubbound;
1629 	   SCIP_Real searchavgbound;
1630 	   SCIP_Real searchbound;
1631 	   SCIP_Real objval;
1632 	   SCIP_Real oldobjval;
1633 	   SCIP_Real fixquot;
1634 	   SCIP_Real bestboundval;
1635 	   SCIP_Bool bestcandmayround;
1636 	   SCIP_Bool bestcandroundup;
1637 	   SCIP_Bool nlperror;
1638 	   SCIP_Bool lperror;
1639 	   SCIP_Bool cutoff;
1640 	   SCIP_Bool backtracked;
1641 	   SCIP_Bool solvenlp;
1642 	   SCIP_Bool covercomputed;
1643 	   SCIP_Bool solvesubmip;
1644 	   SCIP_Longint ncalls;
1645 	   SCIP_Longint nsolsfound;
1646 	   int avgnnlpiterations;
1647 	   int maxnnlpiterations;
1648 	   int npseudocands;
1649 	   int nlpbranchcands;
1650 	   int ncovervars;
1651 	   int nnlpcands;
1652 	   int startnnlpcands;
1653 	   int depth;
1654 	   int maxdepth;
1655 	   int maxdivedepth;
1656 	   int divedepth;
1657 	   int lastnlpsolvedepth;
1658 	   int nfeasnlps;
1659 	   int bestcand;
1660 	   int c;
1661 	   int       backtrackdepth;   /* depth where to go when backtracking */
1662 	   SCIP_VAR* backtrackvar;     /* (first) variable to fix differently in backtracking */
1663 	   SCIP_Real backtrackvarval;  /* (fractional) value of backtrack variable */
1664 	   SCIP_Bool backtrackroundup; /* whether variable should be rounded up in backtracking */
1665 	
1666 	   backtrackdepth = -1;
1667 	   backtrackvar = NULL;
1668 	   backtrackvarval = 0.0;
1669 	   backtrackroundup = FALSE;
1670 	   bestsol = NULL;
1671 	   pseudocandsnlpsol = NULL;
1672 	   pseudocandslpsol = NULL;
1673 	   covervars = NULL;
1674 	
1675 	   assert(heur != NULL);
1676 	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1677 	   assert(scip != NULL);
1678 	   assert(result != NULL);
1679 	   /* assert(SCIPhasCurrentNodeLP(scip)); */
1680 	
1681 	   *result = SCIP_DIDNOTRUN;
1682 	
1683 	   /* do not call heuristic of node was already detected to be infeasible */
1684 	   if( nodeinfeasible )
1685 	      return SCIP_OKAY;
1686 	
1687 	   /* only call heuristic, if an NLP relaxation has been constructed */
1688 	   if( !SCIPisNLPConstructed(scip) || SCIPgetNNlpis(scip) == 0 )
1689 	      return SCIP_OKAY;
1690 	
1691 	   /* only call heuristic, if the current node will not be cutoff, e.g., due to a (integer and NLP-)feasible LP solution */
1692 	   if( SCIPisFeasGE(scip, SCIPgetLocalLowerbound(scip), SCIPgetUpperbound(scip)) )
1693 	      return SCIP_OKAY;
1694 	
1695 	   /* get heuristic's data */
1696 	   heurdata = SCIPheurGetData(heur);
1697 	   assert(heurdata != NULL);
1698 	
1699 	   /* do not call heuristic, if it barely succeded */
1700 	   if( (SCIPheurGetNSolsFound(heur) + 1.0) / (SCIP_Real)(SCIPheurGetNCalls(heur) + 1.0) < heurdata->minsuccquot )
1701 	      return SCIP_OKAY;
1702 	
1703 	   *result = SCIP_DELAYED;
1704 	
1705 	   /* don't dive two times at the same node */
1706 	   if( SCIPgetLastDivenode(scip) == SCIPgetNNodes(scip) && SCIPgetDepth(scip) > 0 )
1707 	      return SCIP_OKAY;
1708 	
1709 	   *result = SCIP_DIDNOTRUN;
1710 	
1711 	   /* only try to dive, if we are in the correct part of the tree, given by minreldepth and maxreldepth */
1712 	   depth = SCIPgetDepth(scip);
1713 	   maxdepth = SCIPgetMaxDepth(scip);
1714 	   maxdepth = MAX(maxdepth, 30);
1715 	   if( depth < heurdata->minreldepth*maxdepth || depth > heurdata->maxreldepth*maxdepth )
1716 	      return SCIP_OKAY;
1717 	
1718 	   /* calculate the maximal number of NLP iterations until heuristic is aborted
1719 	    * maximal number is maxnlpiterabs plus a success-depending multiplier of maxnlpiterrel
1720 	    */
1721 	   ncalls = SCIPheurGetNCalls(heur);
1722 	   nsolsfound = 10*SCIPheurGetNBestSolsFound(heur) + heurdata->nsuccess;
1723 	   maxnnlpiterations = heurdata->maxnlpiterabs;
1724 	   maxnnlpiterations += (int)((1.0 + 10.0*(nsolsfound+1.0)/(ncalls+1.0)) * heurdata->maxnlpiterrel);
1725 	
1726 	   /* don't try to dive, if we took too many NLP iterations during diving */
1727 	   if( heurdata->nnlpiterations >= maxnnlpiterations )
1728 	      return SCIP_OKAY;
1729 	
1730 	   /* allow at least a bit more than the so far average number of NLP iterations per dive */
1731 	   avgnnlpiterations = (int)(heurdata->nnlpiterations / MAX(ncalls, 1.0));
1732 	   maxnnlpiterations = (int)MAX((SCIP_Real) maxnnlpiterations, (SCIP_Real) heurdata->nnlpiterations + 1.2*avgnnlpiterations);
1733 	
1734 	   /* don't try to dive, if there are no unfixed discrete variables */
1735 	   SCIP_CALL( SCIPgetPseudoBranchCands(scip, NULL, &npseudocands, NULL) );
1736 	   if( npseudocands == 0 )
1737 	      return SCIP_OKAY;
1738 	
1739 	   *result = SCIP_DIDNOTFIND;
1740 	
1741 	   /* set starting point to lp solution */
1742 	   SCIP_CALL( SCIPsetNLPInitialGuessSol(scip, NULL) );
1743 	
1744 	   /* solve NLP relaxation, if not solved already */
1745 	   nlpsolstat = SCIPgetNLPSolstat(scip);
1746 	   if( nlpsolstat > SCIP_NLPSOLSTAT_FEASIBLE )
1747 	   {
1748 	      SCIP_NLPSTATISTICS nlpstatistics;
1749 	
1750 	      /* cppcheck-suppress syntaxError */
1751 	      SCIP_CALL( SCIPsolveNLP(scip,
1752 	         .iterlimit = maxnnlpiterations - heurdata->nnlpiterations,
1753 	         .fastfail = heurdata->nlpfastfail ? SCIP_NLPPARAM_FASTFAIL_AGGRESSIVE : SCIP_NLPPARAM_FASTFAIL_CONSERVATIVE) );  /*lint !e666*/
1754 	      SCIPstatistic( ++heurdata->nnlpsolves );
1755 	
1756 	      /* update iteration count */
1757 	      if( SCIPgetNLPTermstat(scip) < SCIP_NLPTERMSTAT_NUMERICERROR )
1758 	      {
1759 	         SCIP_CALL( SCIPgetNLPStatistics(scip, &nlpstatistics) );
1760 	         heurdata->nnlpiterations += nlpstatistics.niterations;
1761 	      }
1762 	
1763 	      nlpsolstat = SCIPgetNLPSolstat(scip);
1764 	
1765 	      /* give up, if no feasible solution found */
1766 	      if( nlpsolstat >= SCIP_NLPSOLSTAT_LOCINFEASIBLE )
1767 	      {
1768 	         SCIPdebugMsg(scip, "initial NLP infeasible or not solvable --> stop\n");
1769 	
1770 	         SCIPstatistic(
1771 	            if( SCIPgetNLPTermstat(scip) < SCIP_NLPTERMSTAT_NUMERICERROR )
1772 	               heurdata->nfailcutoff++;
1773 	            else
1774 	               heurdata->nfailnlperror++;
1775 	         )
1776 	
1777 	         return SCIP_OKAY;
1778 	      }
1779 	   }
1780 	
1781 	   /* get NLP solution */
1782 	   SCIP_CALL( SCIPlinkNLPSol(scip, heurdata->sol) );
1783 	
1784 	   /* get fractional variables that should be integral */
1785 	   SCIP_CALL( getNLPFracVars(scip, heurdata, &nlpcands, &nlpcandssol, &nlpcandsfrac, &nnlpcands) );
1786 	   assert(nnlpcands <= npseudocands);
1787 	
1788 	   /* get LP candidates if LP solution is optimal */
1789 	   lpsolstat = SCIPgetLPSolstat(scip);
1790 	   if( lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
1791 	      nlpbranchcands = SCIPgetNLPBranchCands(scip);
1792 	   else
1793 	      nlpbranchcands = 0;
1794 	
1795 	   /* don't try to dive, if there are no fractional variables */
1796 	   if( nnlpcands == 0 )
1797 	   {
1798 	      SCIP_Bool success;
1799 	
1800 	      /* check, if solution was feasible and good enough
1801 	       *
1802 	       * Note that even if the NLP solver found a feasible solution it does not mean that is satisfy the integrality
1803 	       * conditions for fixed variables. This happens because the NLP solver uses relative tolerances for the bound
1804 	       * constraints but SCIP uses absolute tolerances for checking the integrality conditions.
1805 	       */
1806 	#ifdef SCIP_DEBUG
1807 	      SCIP_CALL( SCIPtrySol(scip, heurdata->sol, TRUE, TRUE, FALSE, TRUE, TRUE, &success) );
1808 	#else
1809 	      SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, TRUE, TRUE, &success) );
1810 	#endif
1811 	      if( success )
1812 	      {
1813 	         SCIPdebugMsg(scip, " -> solution of first NLP was integral, feasible, and good enough\n");
1814 	         *result = SCIP_FOUNDSOL;
1815 	      }
1816 	
1817 	      return SCIP_OKAY;
1818 	   }
1819 	
1820 	   /* for guided diving: don't dive, if no feasible solutions exist */
1821 	   if( heurdata->varselrule == 'g' && SCIPgetNSols(scip) == 0 )
1822 	      return SCIP_OKAY;
1823 	
1824 	   /* for guided diving: get best solution that should guide the search; if this solution lives in the original variable space,
1825 	    * we cannot use it since it might violate the global bounds of the current problem
1826 	    */
1827 	   if( heurdata->varselrule == 'g' && SCIPsolIsOriginal(SCIPgetBestSol(scip)) )
1828 	      return SCIP_OKAY;
1829 	
1830 	   nlpstartsol = NULL;
1831 	   assert(nlpcandsfrac != NULL);
1832 	   assert(nlpcands != NULL);
1833 	   assert(nlpcandssol != NULL);
1834 	
1835 	   /* save solution of first NLP, if we may use it later */
1836 	   if( heurdata->nlpstart != 'n' )
1837 	   {
1838 	      SCIP_CALL( SCIPcreateNLPSol(scip, &nlpstartsol, heur) );
1839 	      SCIP_CALL( SCIPunlinkSol(scip, nlpstartsol) );
1840 	   }
1841 	
1842 	   /* calculate the objective search bound */
1843 	   if( SCIPgetNSolsFound(scip) == 0 )
1844 	   {
1845 	      if( heurdata->maxdiveubquotnosol > 0.0 )
1846 	         searchubbound = SCIPgetLowerbound(scip)
1847 	            + heurdata->maxdiveubquotnosol * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
1848 	      else
1849 	         searchubbound = SCIPinfinity(scip);
1850 	      if( heurdata->maxdiveavgquotnosol > 0.0 )
1851 	         searchavgbound = SCIPgetLowerbound(scip)
1852 	            + heurdata->maxdiveavgquotnosol * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
1853 	      else
1854 	         searchavgbound = SCIPinfinity(scip);
1855 	   }
1856 	   else
1857 	   {
1858 	      if( heurdata->maxdiveubquot > 0.0 )
1859 	         searchubbound = SCIPgetLowerbound(scip)
1860 	            + heurdata->maxdiveubquot * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
1861 	      else
1862 	         searchubbound = SCIPinfinity(scip);
1863 	      if( heurdata->maxdiveavgquot > 0.0 )
1864 	         searchavgbound = SCIPgetLowerbound(scip)
1865 	            + heurdata->maxdiveavgquot * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
1866 	      else
1867 	         searchavgbound = SCIPinfinity(scip);
1868 	   }
1869 	   searchbound = MIN(searchubbound, searchavgbound);
1870 	   if( SCIPisObjIntegral(scip) )
1871 	      searchbound = SCIPceil(scip, searchbound);
1872 	
1873 	   /* calculate the maximal diving depth: 10 * min{number of integer variables, max depth} */
1874 	   maxdivedepth = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
1875 	   maxdivedepth = MIN(maxdivedepth, maxdepth);
1876 	   maxdivedepth *= 10;
1877 	
1878 	   covercomputed = FALSE;
1879 	   varincover = NULL;
1880 	
1881 	   /* compute cover, if required */
1882 	   if( heurdata->prefercover || heurdata->solvesubmip )
1883 	   {
1884 	      SCIP_Real timelimit;
1885 	      SCIP_Real memorylimit;
1886 	
1887 	      /* get limits */
1888 	      SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
1889 	      SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
1890 	      if( !SCIPisInfinity(scip, timelimit) )
1891 	         timelimit -= SCIPgetSolvingTime(scip);
1892 	
1893 	      /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
1894 	      if( !SCIPisInfinity(scip, memorylimit) )
1895 	      {
1896 	         memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
1897 	         memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
1898 	      }
1899 	
1900 	      /* compute cover; use local bounds; only cover "and" and nonlinear constraints (no bounddisjunction or indicator),
1901 	       * including convex constraints */
1902 	      ncovervars = -1;
1903 	      SCIP_CALL( SCIPallocBufferArray(scip, &covervars, SCIPgetNVars(scip)) );
1904 	      if( memorylimit > 2.0*SCIPgetMemExternEstim(scip)/1048576.0 && timelimit > 0.05 )
1905 	      {
1906 	         SCIP_CALL( SCIPcomputeCoverUndercover(scip, &ncovervars, covervars, timelimit, memorylimit, SCIPinfinity(scip),
1907 	               FALSE, FALSE, TRUE, FALSE, FALSE, TRUE, 'u', &covercomputed) );
1908 	      }
1909 	
1910 	      if( covercomputed )
1911 	      {
1912 	         /* a cover can be empty, if the cover computation reveals that all nonlinear constraints are linear w.r.t. current variable fixations */
1913 	         assert(ncovervars >= 0);
1914 	
1915 	         /* create hash map */
1916 	         SCIP_CALL( SCIPhashmapCreate(&varincover, SCIPblkmem(scip), ncovervars) );
1917 	
1918 	         /* process variables in the cover */
1919 	         for( c = 0; c < ncovervars; c++ )
1920 	         {
1921 	            /* insert variable into hash map */
1922 	            if( SCIPvarGetType(covervars[c]) < SCIP_VARTYPE_IMPLINT )
1923 	            {
1924 	               assert(!SCIPhashmapExists(varincover, covervars[c]));
1925 	               SCIP_CALL( SCIPhashmapInsertInt(varincover, covervars[c], c+1) );
1926 	            }
1927 	
1928 	            /* catch bound change events of cover variables */
1929 	            assert(heurdata->eventhdlr != NULL);
1930 	            SCIP_CALL( SCIPcatchVarEvent(scip, covervars[c], SCIP_EVENTTYPE_BOUNDCHANGED, heurdata->eventhdlr,
1931 	                  (SCIP_EVENTDATA*) heurdata, NULL) );
1932 	            assert(!SCIPisFeasEQ(scip, SCIPvarGetLbLocal(covervars[c]), SCIPvarGetUbLocal(covervars[c])));
1933 	         }
1934 	      }
1935 	   }
1936 	   else
1937 	   {
1938 	      covervars = NULL;
1939 	      ncovervars = 0;
1940 	   }
1941 	
1942 	   /* start diving */
1943 	   SCIP_CALL( SCIPstartProbing(scip) );
1944 	
1945 	   /* enables collection of variable statistics during probing */
1946 	   SCIPenableVarHistory(scip);
1947 	
1948 	   /* get NLP objective value*/
1949 	   objval = SCIPgetNLPObjval(scip);
1950 	
1951 	   SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") executing nlpdiving heuristic: depth=%d, %d fractionals, dualbound=%g, searchbound=%g\n",
1952 	      SCIPgetNNodes(scip), SCIPgetDepth(scip), nnlpcands, SCIPgetDualbound(scip), SCIPretransformObj(scip, searchbound));
1953 	
1954 	   /* store a copy of the best solution, if guided diving should be used */
1955 	   if( heurdata->varselrule == 'g' )
1956 	   {
1957 	      assert(SCIPgetNSols(scip) > 0);
1958 	      assert(!SCIPsolIsOriginal(SCIPgetBestSol(scip)));
1959 	
1960 	      SCIP_CALL( SCIPcreateSolCopy(scip, &bestsol, SCIPgetBestSol(scip)) );
1961 	   }
1962 	
1963 	   /* if double diving should be used, create arrays to hold to entire LP and NLP solution */
1964 	   if( heurdata->varselrule == 'd' )
1965 	   {
1966 	      SCIP_CALL( SCIPallocBufferArray(scip, &pseudocandslpsol, npseudocands) );
1967 	      SCIP_CALL( SCIPallocBufferArray(scip, &pseudocandsnlpsol, npseudocands) );
1968 	   }
1969 	
1970 	   /* dive as long we are in the given objective, depth and iteration limits and fractional variables exist, but
1971 	    * - if possible, we dive at least with the depth 10
1972 	    * - if the number of fractional variables decreased at least with 1 variable per 2 dive depths, we continue diving
1973 	    */
1974 	   nlperror = FALSE;
1975 	   lperror = FALSE;
1976 	   cutoff = FALSE;
1977 	   divedepth = 0;
1978 	   lastnlpsolvedepth = 0;
1979 	   backtracked = FALSE;    /* whether we are in backtracking */
1980 	   fixquot = heurdata->fixquot;
1981 	   nfeasnlps = 1;
1982 	   startnnlpcands = nnlpcands;
1983 	   solvesubmip = heurdata->solvesubmip;
1984 	
1985 	   while( !nlperror && !cutoff && (nlpsolstat <= SCIP_NLPSOLSTAT_FEASIBLE || nlpsolstat == SCIP_NLPSOLSTAT_UNKNOWN) && nnlpcands > 0
1986 	      && (nfeasnlps < heurdata->maxfeasnlps
1987 	         || nnlpcands <= startnnlpcands - divedepth/2
1988 	         || (nfeasnlps < maxdivedepth && heurdata->nnlpiterations < maxnnlpiterations && objval < searchbound))
1989 	      && !SCIPisStopped(scip) )
1990 	   {
1991 	      SCIP_VAR* var;
1992 	      SCIP_Bool updatepscost;
1993 	
1994 	      /* open a new probing node if this will not exceed the maximal tree depth, otherwise stop here */
1995 	      if( SCIPgetDepth(scip) < SCIP_MAXTREEDEPTH )
1996 	      {
1997 	         SCIP_CALL( SCIPnewProbingNode(scip) );
1998 	         divedepth++;
1999 	      }
2000 	      else
2001 	         break;
2002 	
2003 	      bestcand = -1;
2004 	      bestcandmayround = TRUE;
2005 	      bestcandroundup = FALSE;
2006 	      bestboundval = SCIP_INVALID;
2007 	      updatepscost = TRUE;
2008 	      var = NULL;
2009 	
2010 	      /* find best candidate variable */
2011 	      switch( heurdata->varselrule )
2012 	      {
2013 	      case 'c':
2014 	         SCIP_CALL( chooseCoefVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, varincover, covercomputed,
2015 	               &bestcand, &bestcandmayround, &bestcandroundup) );
2016 	         if( bestcand >= 0 )
2017 	         {
2018 	            var = nlpcands[bestcand];
2019 	            bestboundval = nlpcandssol[bestcand];
2020 	         }
2021 	         break;
2022 	      case 'v':
2023 	         SCIP_CALL( chooseVeclenVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, varincover, covercomputed,
2024 	               &bestcand, &bestcandmayround, &bestcandroundup) );
2025 	         if( bestcand >= 0 )
2026 	         {
2027 	            var = nlpcands[bestcand];
2028 	            bestboundval = nlpcandssol[bestcand];
2029 	         }
2030 	         break;
2031 	      case 'p':
2032 	         SCIP_CALL( choosePscostVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, varincover, covercomputed,
2033 	               &bestcand, &bestcandmayround, &bestcandroundup) );
2034 	         if( bestcand >= 0 )
2035 	         {
2036 	            var = nlpcands[bestcand];
2037 	            bestboundval = nlpcandssol[bestcand];
2038 	         }
2039 	         break;
2040 	      case 'g':
2041 	         SCIP_CALL( chooseGuidedVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, bestsol, varincover, covercomputed,
2042 	               &bestcand, &bestcandmayround, &bestcandroundup) );
2043 	         if( bestcand >= 0 )
2044 	         {
2045 	            var = nlpcands[bestcand];
2046 	            bestboundval = nlpcandssol[bestcand];
2047 	         }
2048 	         break;
2049 	      case 'd':
2050 	         /* double diving only works if we have both relaxations at hand, otherwise we fall back to fractional diving */
2051 	         if( lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
2052 	         {
2053 	            SCIP_VAR** pseudocands;
2054 	
2055 	            SCIP_CALL( SCIPgetPseudoBranchCands(scip, &pseudocands, &npseudocands, NULL) );
2056 	            assert(backtrackdepth > 0 || nnlpcands <= npseudocands);
2057 	            assert(SCIPgetNLPBranchCands(scip) <= npseudocands);
2058 	            SCIP_CALL( SCIPgetSolVals(scip, NULL, npseudocands, pseudocands, pseudocandslpsol) );
2059 	            SCIP_CALL( SCIPgetSolVals(scip, heurdata->sol, npseudocands, pseudocands, pseudocandsnlpsol) );
2060 	            SCIP_CALL( chooseDoubleVar(scip, heurdata, pseudocands, pseudocandsnlpsol, pseudocandslpsol, npseudocands,
2061 	                  varincover, covercomputed, &bestcand, &bestboundval, &bestcandmayround, &bestcandroundup) );
2062 	            if( bestcand >= 0 )
2063 	               var = pseudocands[bestcand];
2064 	            break;
2065 	         }
2066 	         else
2067 	            updatepscost = FALSE;
2068 	         /*lint -fallthrough*/
2069 	      case 'f':
2070 	         SCIP_CALL( chooseFracVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, varincover, covercomputed,
2071 	               &bestcand, &bestcandmayround, &bestcandroundup) );
2072 	         if( bestcand >= 0 )
2073 	         {
2074 	            var = nlpcands[bestcand];
2075 	            bestboundval = nlpcandssol[bestcand];
2076 	         }
2077 	         break;
2078 	      default:
2079 	         SCIPerrorMessage("invalid variable selection rule\n");
2080 	         return SCIP_INVALIDDATA;
2081 	      }
2082 	
2083 	      /* if all candidates are roundable, try to round the solution
2084 	       * if var == NULL (i.e., bestcand == -1), then all solution candidates are outside bounds
2085 	       *   this should only happen if they are slightly outside bounds (i.e., still within feastol, relative tolerance),
2086 	       *   but far enough out to be considered as fractional (within feastol, but using absolute tolerance)
2087 	       *   in this case, we also try our luck with rounding
2088 	       */
2089 	      if( (var == NULL || bestcandmayround) && backtrackdepth == -1 )
2090 	      {
2091 	         SCIP_Bool success;
2092 	
2093 	         /* create solution from diving NLP and try to round it */
2094 	         SCIP_CALL( SCIProundSol(scip, heurdata->sol, &success) );
2095 	
2096 	         if( success )
2097 	         {
2098 	            SCIPdebugMsg(scip, "nlpdiving found roundable primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol));
2099 	
2100 	            /* try to add solution to SCIP */
2101 	#ifdef SCIP_DEBUG
2102 	            SCIP_CALL( SCIPtrySol(scip, heurdata->sol, TRUE, TRUE, FALSE, FALSE, TRUE, &success) );
2103 	#else
2104 	            SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, TRUE, &success) );
2105 	#endif
2106 	
2107 	            /* check, if solution was feasible and good enough */
2108 	            if( success )
2109 	            {
2110 	               SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
2111 	               *result = SCIP_FOUNDSOL;
2112 	            }
2113 	         }
2114 	      }
2115 	
2116 	      /* if all variables have been found to be essentially integral (even though there is some numerical doubt, see comment above), then stop */
2117 	      if( var == NULL )
2118 	         break;
2119 	
2120 	      do
2121 	      {
2122 	         SCIP_Real frac;
2123 	         frac = SCIP_INVALID;
2124 	
2125 	         if( backtracked && backtrackdepth > 0 )
2126 	         {
2127 	            assert(backtrackvar != NULL);
2128 	
2129 	            /* if the variable is already fixed or if the solution value is outside the domain, numerical troubles may have
2130 	             * occured or variable was fixed by propagation while backtracking => Abort diving!
2131 	             */
2132 	            if( SCIPvarGetLbLocal(backtrackvar) >= SCIPvarGetUbLocal(backtrackvar) - 0.5 )
2133 	            {
2134 	               SCIPdebugMsg(scip, "Selected variable <%s> already fixed to [%g,%g] (solval: %.9f), diving aborted \n",
2135 	                  SCIPvarGetName(backtrackvar), SCIPvarGetLbLocal(backtrackvar), SCIPvarGetUbLocal(backtrackvar), backtrackvarval);
2136 	               cutoff = TRUE;
2137 	               break;
2138 	            }
2139 	            if( SCIPisFeasLT(scip, backtrackvarval, SCIPvarGetLbLocal(backtrackvar)) || SCIPisFeasGT(scip, backtrackvarval, SCIPvarGetUbLocal(backtrackvar)) )
2140 	            {
2141 	               SCIPdebugMsg(scip, "selected variable's <%s> solution value is outside the domain [%g,%g] (solval: %.9f), diving aborted\n",
2142 	                  SCIPvarGetName(backtrackvar), SCIPvarGetLbLocal(backtrackvar), SCIPvarGetUbLocal(backtrackvar), backtrackvarval);
2143 	               assert(backtracked);
2144 	               break;
2145 	            }
2146 	
2147 	            /* round backtrack variable up or down */
2148 	            if( backtrackroundup )
2149 	            {
2150 	               SCIPdebugMsg(scip, "  dive %d/%d, NLP iter %d/%d: var <%s>, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
2151 	                  divedepth, maxdivedepth, heurdata->nnlpiterations, maxnnlpiterations,
2152 	                  SCIPvarGetName(backtrackvar), backtrackvarval, SCIPvarGetLbLocal(backtrackvar), SCIPvarGetUbLocal(backtrackvar),
2153 	                  SCIPfeasCeil(scip, backtrackvarval), SCIPvarGetUbLocal(backtrackvar));
2154 	               SCIP_CALL( SCIPchgVarLbProbing(scip, backtrackvar, SCIPfeasCeil(scip, backtrackvarval)) );
2155 	            }
2156 	            else
2157 	            {
2158 	               SCIPdebugMsg(scip, "  dive %d/%d, NLP iter %d/%d: var <%s>, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
2159 	                  divedepth, maxdivedepth, heurdata->nnlpiterations, maxnnlpiterations,
2160 	                  SCIPvarGetName(backtrackvar), backtrackvarval, SCIPvarGetLbLocal(backtrackvar), SCIPvarGetUbLocal(backtrackvar),
2161 	                  SCIPvarGetLbLocal(backtrackvar), SCIPfeasFloor(scip, backtrackvarval));
2162 	               SCIP_CALL( SCIPchgVarUbProbing(scip, backtrackvar, SCIPfeasFloor(scip, backtrackvarval)) );
2163 	            }
2164 	
2165 	            /* forget about backtrack variable */
2166 	            backtrackdepth = -1;
2167 	
2168 	            /* for pseudo cost computation */
2169 	            bestcandroundup = backtrackroundup;
2170 	            frac = SCIPfrac(scip, backtrackvarval);
2171 	            var = backtrackvar;
2172 	         }
2173 	         else
2174 	         {
2175 	            assert(var != NULL);
2176 	
2177 	            /* if the variable is already fixed or if the solution value is outside the domain, numerical troubles may have
2178 	             * occured or variable was fixed by propagation while backtracking => Abort diving!
2179 	             */
2180 	            if( SCIPvarGetLbLocal(var) >= SCIPvarGetUbLocal(var) - 0.5 )
2181 	            {
2182 	               SCIPdebugMsg(scip, "Selected variable <%s> already fixed to [%g,%g] (solval: %.9f), diving aborted \n",
2183 	                  SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bestboundval);
2184 	               cutoff = TRUE;
2185 	               break;
2186 	            }
2187 	            if( SCIPisFeasLT(scip, bestboundval, SCIPvarGetLbLocal(var)) || SCIPisFeasGT(scip, bestboundval, SCIPvarGetUbLocal(var)) )
2188 	            {
2189 	               SCIPdebugMsg(scip, "selected variable's <%s> solution value is outside the domain [%g,%g] (solval: %.9f), diving aborted\n",
2190 	                  SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bestboundval);
2191 	               assert(backtracked);
2192 	               break;
2193 	            }
2194 	
2195 	            /* apply rounding of best candidate */
2196 	            if( bestcandroundup == !backtracked )
2197 	            {
2198 	               /* round variable up */
2199 	               SCIPdebugMsg(scip, "  dive %d/%d, NLP iter %d/%d: var <%s>, round=%u, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
2200 	                  divedepth, maxdivedepth, heurdata->nnlpiterations, maxnnlpiterations,
2201 	                  SCIPvarGetName(var), bestcandmayround,
2202 	                  bestboundval, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var),
2203 	                  SCIPfeasCeil(scip, bestboundval), SCIPvarGetUbLocal(var));
2204 	               SCIP_CALL( SCIPchgVarLbProbing(scip, var, SCIPfeasCeil(scip, bestboundval)) );
2205 	
2206 	               /* remember variable for backtracking, if we have none yet (e.g., we are just after NLP solve) or we are half way to the next NLP solve */
2207 	               if( backtrackdepth == -1 || (divedepth - lastnlpsolvedepth == (int)(MIN(fixquot * nnlpcands, nlpbranchcands)/2.0)) )
2208 	               {
2209 	                  backtrackdepth   = divedepth;
2210 	                  backtrackvar     = var;
2211 	                  backtrackvarval  = bestboundval;
2212 	                  backtrackroundup = FALSE;
2213 	               }
2214 	            }
2215 	            else
2216 	            {
2217 	               /* round variable down */
2218 	               SCIPdebugMsg(scip, "  dive %d/%d, NLP iter %d/%d: var <%s>, round=%u, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
2219 	                  divedepth, maxdivedepth, heurdata->nnlpiterations, maxnnlpiterations,
2220 	                  SCIPvarGetName(var), bestcandmayround,
2221 	                  bestboundval, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var),
2222 	                  SCIPvarGetLbLocal(var), SCIPfeasFloor(scip, bestboundval));
2223 	               SCIP_CALL( SCIPchgVarUbProbing(scip, var, SCIPfeasFloor(scip, bestboundval)) );
2224 	
2225 	               /* remember variable for backtracking, if we have none yet (e.g., we are just after NLP solve) or we are half way to the next NLP solve */
2226 	               if( backtrackdepth == -1 || (divedepth - lastnlpsolvedepth == (int)(MIN(fixquot * nnlpcands, nlpbranchcands)/2.0)) )
2227 	               {
2228 	                  backtrackdepth   = divedepth;
2229 	                  backtrackvar     = var;
2230 	                  backtrackvarval  = bestboundval;
2231 	                  backtrackroundup = TRUE;
2232 	               }
2233 	            }
2234 	
2235 	            /* for pseudo-cost computation */
2236 	            if( updatepscost && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
2237 	            {
2238 	               if( heurdata->varselrule == 'd' )
2239 	               {
2240 	                  assert(pseudocandsnlpsol != NULL);
2241 	                  assert(0 <= bestcand && bestcand < npseudocands);
2242 	                  frac = SCIPfrac(scip, pseudocandsnlpsol[bestcand]);
2243 	               }
2244 	               else
2245 	                  frac = nlpcandsfrac[bestcand];
2246 	            }
2247 	         }
2248 	
2249 	         /* apply domain propagation */
2250 	         SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, NULL) );
2251 	         if( cutoff )
2252 	         {
2253 	            SCIPdebugMsg(scip, "  *** cutoff detected in propagation at level %d\n", SCIPgetProbingDepth(scip));
2254 	         }
2255 	
2256 	         /* if all variables in the cover are fixed or there is no fractional variable in the cover,
2257 	          * then solve a sub-MIP
2258 	          */
2259 	         if( !cutoff && solvesubmip && covercomputed &&
2260 	            (heurdata->nfixedcovervars == ncovervars ||
2261 	               (heurdata->nfixedcovervars >= (ncovervars+1)/2 && !SCIPhashmapExists(varincover, var))) )
2262 	         {
2263 	            int probingdepth;
2264 	
2265 	            solvesubmip = FALSE;
2266 	            probingdepth = SCIPgetProbingDepth(scip);
2267 	            assert(probingdepth >= 1);
2268 	            assert(covervars != NULL);
2269 	
2270 	            if( heurdata->nfixedcovervars != ncovervars )
2271 	            {
2272 	               /* fix all remaining cover variables */
2273 	               for( c = 0; c < ncovervars && !cutoff ; c++ )
2274 	               {
2275 	                  SCIP_Real lb;
2276 	                  SCIP_Real ub;
2277 	                  lb = SCIPvarGetLbLocal(covervars[c]);
2278 	                  ub = SCIPvarGetUbLocal(covervars[c]);
2279 	                  if( !SCIPisFeasEQ(scip, lb, ub) )
2280 	                  {
2281 	                     SCIP_Real nlpsolval;
2282 	
2283 	                     /* adopt lpsolval w.r.t. intermediate bound changes by propagation */
2284 	                     nlpsolval = SCIPvarGetNLPSol(covervars[c]);
2285 	                     nlpsolval = MIN(nlpsolval,ub);
2286 	                     nlpsolval = MAX(nlpsolval,lb);
2287 	                     assert(SCIPvarGetType(covervars[c]) >= SCIP_VARTYPE_IMPLINT || SCIPisFeasIntegral(scip, nlpsolval));
2288 	
2289 	                     /* open a new probing node if this will not exceed the maximal tree depth,
2290 	                      * otherwise fix all the remaining variables at the same probing node
2291 	                      * @todo do we need a new probing node for each fixing? if one of these fixings leads to a cutoff
2292 	                      *       we backtrack to the last probing node before we started to fix the covervars (and we do
2293 	                      *       not solve the probing LP). thus, it would be less work load in SCIPendProbing
2294 	                      *       and SCIPbacktrackProbing.
2295 	                      */
2296 	                     if( SCIP_MAXTREEDEPTH > SCIPgetDepth(scip) )
2297 	                     {
2298 	                        SCIP_CALL( SCIPnewProbingNode(scip) );
2299 	                     }
2300 	
2301 	                     /* fix and propagate */
2302 	                     assert(SCIPisLbBetter(scip, nlpsolval, lb, ub) || SCIPisUbBetter(scip, nlpsolval, lb, ub));
2303 	
2304 	                     if( SCIPisLbBetter(scip, nlpsolval, lb, ub) )
2305 	                     {
2306 	                        SCIP_CALL( SCIPchgVarLbProbing(scip, covervars[c], nlpsolval) );
2307 	                        /* if covervar was implicit integer and fractional, then nlpsolval may be below lower bound now, so adjust to new bound */
2308 	                        nlpsolval = MAX(nlpsolval, SCIPvarGetLbLocal(covervars[c])); /*lint !e666*/
2309 	                     }
2310 	                     if( SCIPisUbBetter(scip, nlpsolval, lb, ub) )
2311 	                     {
2312 	                        SCIP_CALL( SCIPchgVarUbProbing(scip, covervars[c], nlpsolval) );
2313 	                     }
2314 	
2315 	                     SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, NULL) );
2316 	                  }
2317 	               }
2318 	            }
2319 	
2320 	            /* solve sub-MIP or return to standard diving */
2321 	            if( cutoff )
2322 	            {
2323 	               SCIP_CALL( SCIPbacktrackProbing(scip, probingdepth) );
2324 	            }
2325 	            else
2326 	            {
2327 	               SCIP_Bool success;
2328 	               success = FALSE;
2329 	
2330 	               SCIP_CALL( solveSubMIP(scip, heur, covervars, ncovervars, &success));
2331 	               if( success )
2332 	                  *result = SCIP_FOUNDSOL;
2333 	               backtracked = TRUE; /* to avoid backtracking */
2334 	               nnlpcands = 0; /* to force termination */
2335 	               cutoff = TRUE;
2336 	            }
2337 	         }
2338 	
2339 	         /* resolve the diving LP */
2340 	         if( !cutoff && !lperror && (heurdata->lp || heurdata->varselrule == 'd')
2341 	            && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL && SCIPisLPSolBasic(scip) )
2342 	         {
2343 	            SCIP_CALL( SCIPsolveProbingLP(scip, 100, &lperror, &cutoff) );
2344 	
2345 	            /* get LP solution status, objective value, and fractional variables, that should be integral */
2346 	            lpsolstat = SCIPgetLPSolstat(scip);
2347 	            assert(cutoff || (lpsolstat != SCIP_LPSOLSTAT_OBJLIMIT && lpsolstat != SCIP_LPSOLSTAT_INFEASIBLE &&
2348 	                  (lpsolstat != SCIP_LPSOLSTAT_OPTIMAL || SCIPisLT(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)))));
2349 	
2350 	            if( lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
2351 	            {
2352 	               nlpbranchcands = SCIPgetNLPBranchCands(scip);
2353 	
2354 	               /* get new objective value */
2355 	               oldobjval = objval;
2356 	               objval = SCIPgetLPObjval(scip);
2357 	
2358 	               /* update pseudo cost values */
2359 	               if( updatepscost && SCIPisGT(scip, objval, oldobjval) )
2360 	               {
2361 	                  assert(frac != SCIP_INVALID);  /*lint !e777*/
2362 	                  if( bestcandroundup )
2363 	                  {
2364 	                     SCIP_CALL( SCIPupdateVarPseudocost(scip, var, 1.0-frac, objval - oldobjval, 1.0) );
2365 	                  }
2366 	                  else
2367 	                  {
2368 	                     SCIP_CALL( SCIPupdateVarPseudocost(scip, var, 0.0-frac, objval - oldobjval, 1.0) );
2369 	                  }
2370 	               }
2371 	            }
2372 	            else
2373 	            {
2374 	               nlpbranchcands = 0;
2375 	            }
2376 	
2377 	            if( cutoff )
2378 	            {
2379 	               SCIPdebugMsg(scip, "  *** cutoff detected in LP solving at level %d, lpsolstat = %d\n", SCIPgetProbingDepth(scip), lpsolstat);
2380 	            }
2381 	         }
2382 	         else
2383 	            lpsolstat = SCIP_LPSOLSTAT_NOTSOLVED;
2384 	
2385 	         /* check whether we want to solve the NLP, which is the case if
2386 	          * - we are in backtracking, or
2387 	          * - we have (actively) fixed/rounded fixquot*nnlpcands variables
2388 	          * - all fractional variables were rounded/fixed (due to fixing and domain propagation)
2389 	          */
2390 	         solvenlp = backtracked;
2391 	         if( !solvenlp && !cutoff )
2392 	         {
2393 	            solvenlp = (lastnlpsolvedepth < divedepth - fixquot * nnlpcands);
2394 	            if( !solvenlp )
2395 	            {
2396 	               /* check if fractional NLP variables are left (some may have been fixed by propagation) */
2397 	               for( c = 0; c < nnlpcands; ++c )
2398 	               {
2399 	                  var = nlpcands[c];
2400 	                  if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
2401 	                     continue;
2402 	                  else
2403 	                     break;
2404 	               }
2405 	               if( c == nnlpcands )
2406 	                  solvenlp = TRUE;
2407 	            }
2408 	         }
2409 	
2410 	         nlpsolstat = SCIP_NLPSOLSTAT_UNKNOWN;
2411 	
2412 	         /* resolve the diving NLP */
2413 	         if( !cutoff && solvenlp )
2414 	         {
2415 	            SCIP_NLPTERMSTAT termstat;
2416 	            SCIP_NLPSTATISTICS nlpstatistics;
2417 	
2418 	            /* set start solution, if we are in backtracking (previous NLP solve was infeasible) */
2419 	            if( heurdata->nlpstart != 'n' && backtracked )
2420 	            {
2421 	               assert(nlpstartsol != NULL);
2422 	
2423 	               SCIPdebugMsg(scip, "setting NLP initial guess\n");
2424 	
2425 	               SCIP_CALL( SCIPsetNLPInitialGuessSol(scip, nlpstartsol) );
2426 	            }
2427 	
2428 	            /* solve NLP; allow at least MINNLPITER many iterations */
2429 	            SCIP_CALL( SCIPsolveNLP(scip,
2430 	               .iterlimit = MAX(maxnnlpiterations - heurdata->nnlpiterations, MINNLPITER)) );  /*lint !e666*/
2431 	            SCIPstatistic( ++heurdata->nnlpsolves );
2432 	
2433 	            termstat = SCIPgetNLPTermstat(scip);
2434 	            if( termstat >= SCIP_NLPTERMSTAT_NUMERICERROR )
2435 	            {
2436 	               if( termstat >= SCIP_NLPTERMSTAT_LICENSEERROR )
2437 	               {
2438 	                  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL,
2439 	                     "Error while solving NLP in nlpdiving heuristic; NLP solve terminated with code <%d>\n", termstat);
2440 	               }
2441 	               nlperror = TRUE;
2442 	               break;
2443 	            }
2444 	
2445 	            /* update iteration count */
2446 	            SCIP_CALL( SCIPgetNLPStatistics(scip, &nlpstatistics) );
2447 	            heurdata->nnlpiterations += nlpstatistics.niterations;
2448 	
2449 	            /* get NLP solution status, objective value, and fractional variables, that should be integral */
2450 	            nlpsolstat = SCIPgetNLPSolstat(scip);
2451 	            cutoff = (nlpsolstat > SCIP_NLPSOLSTAT_FEASIBLE);
2452 	
2453 	            if( cutoff )
2454 	            {
2455 	               SCIPdebugMsg(scip, "  *** cutoff detected in NLP solving at level %d, nlpsolstat: %d\n", SCIPgetProbingDepth(scip), nlpsolstat);
2456 	            }
2457 	            else
2458 	            {
2459 	               SCIP_CALL( SCIPlinkNLPSol(scip, heurdata->sol) );
2460 	
2461 	               /* remember that we have solve NLP on this depth successfully */
2462 	               lastnlpsolvedepth = divedepth;
2463 	               /* forget previous backtrack variable, we will never go back to a depth before the current one */
2464 	               backtrackdepth = -1;
2465 	               /* store NLP solution for warmstarting, if nlpstart is 'f' */
2466 	               if( heurdata->nlpstart == 'f' )
2467 	               {
2468 	                  assert(nlpstartsol != NULL);
2469 	
2470 	                  /* copy NLP solution values into nlpstartsol, is there a better way to do this???? */
2471 	                  SCIP_CALL( SCIPlinkNLPSol(scip, nlpstartsol) );
2472 	                  SCIP_CALL( SCIPunlinkSol(scip, nlpstartsol) );
2473 	               }
2474 	               /* increase counter on number of NLP solves with feasible solution */
2475 	               ++nfeasnlps;
2476 	            }
2477 	         }
2478 	
2479 	         /* perform backtracking if a cutoff was detected */
2480 	         if( cutoff && !backtracked && heurdata->backtrack )
2481 	         {
2482 	            if( backtrackdepth == -1 )
2483 	            {
2484 	               /* backtrack one step */
2485 	               SCIPdebugMsg(scip, "  *** cutoff detected at level %d - backtracking one step\n", SCIPgetProbingDepth(scip));
2486 	               SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip)-1) );
2487 	
2488 	               /* after backtracking there has to be at least one open node without exceeding the maximal tree depth */
2489 	               assert(SCIP_MAXTREEDEPTH > SCIPgetDepth(scip));
2490 	
2491 	               SCIP_CALL( SCIPnewProbingNode(scip) );
2492 	            }
2493 	            else
2494 	            {
2495 	               /* if we have a stored a depth for backtracking, go there */
2496 	               SCIPdebugMsg(scip, "  *** cutoff detected at level %d - backtracking to depth %d\n", SCIPgetProbingDepth(scip), backtrackdepth);
2497 	               SCIP_CALL( SCIPbacktrackProbing(scip, backtrackdepth-1) );
2498 	
2499 	               /* after backtracking there has to be at least one open node without exceeding the maximal tree depth */
2500 	               assert(SCIP_MAXTREEDEPTH > SCIPgetDepth(scip));
2501 	
2502 	               SCIP_CALL( SCIPnewProbingNode(scip) );
2503 	               divedepth = backtrackdepth;
2504 	
2505 	               /* do not update pseudocosts if backtracking by more than one level */
2506 	               updatepscost = FALSE;
2507 	
2508 	               /* in case, we are feasible after backtracking, fix less variables at once in continuing diving
2509 	                * @todo should we remember the fixquot in heurdata for the next run?
2510 	                */
2511 	               fixquot *= 0.5;
2512 	            }
2513 	            /* remember that we are backtracking now */
2514 	            backtracked = TRUE;
2515 	         }
2516 	         else
2517 	            backtracked = FALSE;
2518 	      }
2519 	      while( backtracked );
2520 	
2521 	      if( !nlperror && !cutoff && nlpsolstat <= SCIP_NLPSOLSTAT_FEASIBLE )
2522 	      {
2523 	         /* get new fractional variables */
2524 	         SCIP_CALL( getNLPFracVars(scip, heurdata, &nlpcands, &nlpcandssol, &nlpcandsfrac, &nnlpcands) );
2525 	      }
2526 	      SCIPdebugMsg(scip, "   -> nlpsolstat=%d, objval=%g/%g, nfrac nlp=%d lp=%d\n", nlpsolstat, objval, searchbound, nnlpcands, nlpbranchcands);
2527 	   }
2528 	
2529 	   /*lint --e{774}*/
2530 	   SCIPdebugMsg(scip, "NLP nlpdiving ABORT due to ");
2531 	   if( nlperror || (nlpsolstat > SCIP_NLPSOLSTAT_LOCINFEASIBLE && nlpsolstat != SCIP_NLPSOLSTAT_UNKNOWN) )
2532 	   {
2533 	      SCIPdebugMsgPrint(scip, "NLP bad status - nlperror: %ud nlpsolstat: %d \n", nlperror, nlpsolstat);
2534 	      SCIPstatistic( heurdata->nfailnlperror++ );
2535 	   }
2536 	   else if( SCIPisStopped(scip) || cutoff )
2537 	   {
2538 	      SCIPdebugMsgPrint(scip, "LIMIT hit - stop: %ud cutoff: %ud \n", SCIPisStopped(scip), cutoff);
2539 	      SCIPstatistic( heurdata->nfailcutoff++ );
2540 	   }
2541 	   else if(! (divedepth < 10
2542 	         || nnlpcands <= startnnlpcands - divedepth/2
2543 	         || (divedepth < maxdivedepth && heurdata->nnlpiterations < maxnnlpiterations && objval < searchbound) ) )
2544 	   {
2545 	      SCIPdebugMsgPrint(scip, "TOO DEEP - divedepth: %4d cands halfed: %d ltmaxdepth: %d ltmaxiter: %d bound: %d\n", divedepth,
2546 	         (nnlpcands > startnnlpcands - divedepth/2), (divedepth >= maxdivedepth), (heurdata->nnlpiterations >= maxnnlpiterations),
2547 	         (objval >= searchbound));
2548 	      SCIPstatistic( heurdata->nfaildepth++ );
2549 	   }
2550 	   else if( nnlpcands == 0 && !nlperror && !cutoff && nlpsolstat <= SCIP_NLPSOLSTAT_FEASIBLE )
2551 	   {
2552 	      SCIPdebugMsgPrint(scip, "SUCCESS\n");
2553 	   }
2554 	   else
2555 	   {
2556 	      SCIPdebugMsgPrint(scip, "UNKNOWN, very mysterical reason\n");  /* see also special case var == NULL (bestcand == -1) after choose*Var above */
2557 	   }
2558 	
2559 	   /* check if a solution has been found */
2560 	   if( nnlpcands == 0 && !nlperror && !cutoff && nlpsolstat <= SCIP_NLPSOLSTAT_FEASIBLE )
2561 	   {
2562 	      SCIP_Bool success;
2563 	
2564 	      /* create solution from diving NLP */
2565 	      SCIPdebugMsg(scip, "nlpdiving found primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol));
2566 	
2567 	      /* try to add solution to SCIP
2568 	       *
2569 	       * Note that even if the NLP solver found a feasible solution it does not mean that is satisfy the integrality
2570 	       * conditions for fixed variables. This happens because the NLP solver uses relative tolerances for the bound
2571 	       * constraints but SCIP uses absolute tolerances for checking the integrality conditions.
2572 	       */
2573 	#ifdef SCIP_DEBUG
2574 	      SCIP_CALL( SCIPtrySol(scip, heurdata->sol, TRUE, TRUE, FALSE, TRUE, TRUE, &success) );
2575 	#else
2576 	      SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, TRUE, TRUE, &success) );
2577 	#endif
2578 	
2579 	      /* check, if solution was feasible and good enough */
2580 	      if( success )
2581 	      {
2582 	         SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
2583 	         *result = SCIP_FOUNDSOL;
2584 	      }
2585 	      else
2586 	      {
2587 	         SCIPdebugMsg(scip, " -> solution was not accepted\n");
2588 	      }
2589 	   }
2590 	
2591 	   /* end diving */
2592 	   SCIP_CALL( SCIPendProbing(scip) );
2593 	
2594 	   /* free hash map and drop variable bound change events */
2595 	   if( covercomputed )
2596 	   {
2597 	      assert(heurdata->eventhdlr != NULL);
2598 	      assert(heurdata->nfixedcovervars >= 0); /* variables might have been globally fixed in propagation */
2599 	      assert(varincover != NULL);
2600 	      assert(covervars != NULL);
2601 	
2602 	      SCIPhashmapFree(&varincover);
2603 	
2604 	      /* drop bound change events of cover variables */
2605 	      for( c = 0; c < ncovervars; c++ )
2606 	      {
2607 	         SCIP_CALL( SCIPdropVarEvent(scip, covervars[c], SCIP_EVENTTYPE_BOUNDCHANGED, heurdata->eventhdlr, (SCIP_EVENTDATA*)heurdata, -1) );
2608 	      }
2609 	   }
2610 	   else
2611 	      assert(varincover == NULL);
2612 	
2613 	   /* free NLP start solution */
2614 	   if( nlpstartsol != NULL )
2615 	   {
2616 	      SCIP_CALL( SCIPfreeSol(scip, &nlpstartsol) );
2617 	   }
2618 	
2619 	   /* free copied best solution */
2620 	   if( heurdata->varselrule == 'g' )
2621 	   {
2622 	      assert(bestsol != NULL);
2623 	      SCIP_CALL( SCIPfreeSol(scip, &bestsol) );
2624 	   }
2625 	   else
2626 	      assert(bestsol == NULL);
2627 	
2628 	   /* free arrays of LP and NLP solution */
2629 	   if( heurdata->varselrule == 'd' )
2630 	   {
2631 	      assert(pseudocandsnlpsol != NULL);
2632 	      assert(pseudocandsnlpsol != NULL);
2633 	      SCIPfreeBufferArray(scip, &pseudocandsnlpsol);
2634 	      SCIPfreeBufferArray(scip, &pseudocandslpsol);
2635 	   }
2636 	   else
2637 	   {
2638 	      assert(pseudocandsnlpsol == NULL);
2639 	      assert(pseudocandsnlpsol == NULL);
2640 	   }
2641 	
2642 	   /* free array of cover variables */
2643 	   if( heurdata->prefercover || heurdata->solvesubmip )
2644 	   {
2645 	      assert(covervars != NULL || !covercomputed);
2646 	      if( covervars != NULL )
2647 	         SCIPfreeBufferArray(scip, &covervars);
2648 	   }
2649 	   else
2650 	      assert(covervars == NULL);
2651 	
2652 	   if( *result == SCIP_FOUNDSOL )
2653 	      heurdata->nsuccess++;
2654 	
2655 	   SCIPdebugMsg(scip, "nlpdiving heuristic finished\n");
2656 	
2657 	   return SCIP_OKAY;  /*lint !e438*/
2658 	}
2659 	
2660 	
2661 	/*
2662 	 * heuristic specific interface methods
2663 	 */
2664 	
2665 	/** creates the nlpdiving heuristic and includes it in SCIP */
2666 	SCIP_RETCODE SCIPincludeHeurNlpdiving(
2667 	   SCIP*                 scip                /**< SCIP data structure */
2668 	   )
2669 	{
2670 	   SCIP_HEURDATA* heurdata;
2671 	   SCIP_HEUR* heur = NULL;
2672 	
2673 	   /* create heuristic data */
2674 	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
2675 	
2676 	   /* include heuristic */
2677 	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
2678 	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecNlpdiving, heurdata) );
2679 	
2680 	   assert(heur != NULL);
2681 	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyNlpdiving) );
2682 	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeNlpdiving) );
2683 	   SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitNlpdiving) );
2684 	   SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitNlpdiving) );
2685 	
2686 	   /* get event handler for bound change events */
2687 	   heurdata->eventhdlr = NULL;
2688 	   /* create event handler for bound change events */
2689 	   SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &heurdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
2690 	         eventExecNlpdiving, NULL) );
2691 	   if ( heurdata->eventhdlr == NULL )
2692 	   {
2693 	      SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
2694 	      return SCIP_PLUGINNOTFOUND;
2695 	   }
2696 	
2697 	   /* nlpdiving heuristic parameters */
2698 	   SCIP_CALL( SCIPaddRealParam(scip,
2699 	         "heuristics/" HEUR_NAME "/minreldepth",
2700 	         "minimal relative depth to start diving",
2701 	         &heurdata->minreldepth, TRUE, DEFAULT_MINRELDEPTH, 0.0, 1.0, NULL, NULL) );
2702 	   SCIP_CALL( SCIPaddRealParam(scip,
2703 	         "heuristics/" HEUR_NAME "/maxreldepth",
2704 	         "maximal relative depth to start diving",
2705 	         &heurdata->maxreldepth, TRUE, DEFAULT_MAXRELDEPTH, 0.0, 1.0, NULL, NULL) );
2706 	   SCIP_CALL( SCIPaddIntParam(scip,
2707 	         "heuristics/" HEUR_NAME "/maxnlpiterabs",
2708 	         "minimial absolute number of allowed NLP iterations",
2709 	         &heurdata->maxnlpiterabs, FALSE, DEFAULT_MAXNLPITERABS, 0, INT_MAX, NULL, NULL) );
2710 	   SCIP_CALL( SCIPaddIntParam(scip,
2711 	         "heuristics/" HEUR_NAME "/maxnlpiterrel",
2712 	         "additional allowed number of NLP iterations relative to successfully found solutions",
2713 	         &heurdata->maxnlpiterrel, FALSE, DEFAULT_MAXNLPITERREL, 0, INT_MAX, NULL, NULL) );
2714 	   SCIP_CALL( SCIPaddRealParam(scip,
2715 	         "heuristics/" HEUR_NAME "/maxdiveubquot",
2716 	         "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)",
2717 	         &heurdata->maxdiveubquot, TRUE, DEFAULT_MAXDIVEUBQUOT, 0.0, 1.0, NULL, NULL) );
2718 	   SCIP_CALL( SCIPaddRealParam(scip,
2719 	         "heuristics/" HEUR_NAME "/maxdiveavgquot",
2720 	         "maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)",
2721 	         &heurdata->maxdiveavgquot, TRUE, DEFAULT_MAXDIVEAVGQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2722 	   SCIP_CALL( SCIPaddRealParam(scip,
2723 	         "heuristics/" HEUR_NAME "/maxdiveubquotnosol",
2724 	         "maximal UBQUOT when no solution was found yet (0.0: no limit)",
2725 	         &heurdata->maxdiveubquotnosol, TRUE, DEFAULT_MAXDIVEUBQUOTNOSOL, 0.0, 1.0, NULL, NULL) );
2726 	   SCIP_CALL( SCIPaddRealParam(scip,
2727 	         "heuristics/" HEUR_NAME "/maxdiveavgquotnosol",
2728 	         "maximal AVGQUOT when no solution was found yet (0.0: no limit)",
2729 	         &heurdata->maxdiveavgquotnosol, TRUE, DEFAULT_MAXDIVEAVGQUOTNOSOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2730 	   SCIP_CALL( SCIPaddIntParam(scip,
2731 	         "heuristics/" HEUR_NAME "/maxfeasnlps",
2732 	         "maximal number of NLPs with feasible solution to solve during one dive",
2733 	         &heurdata->maxfeasnlps, FALSE, DEFAULT_MAXFEASNLPS, 1, INT_MAX, NULL, NULL) );
2734 	   SCIP_CALL( SCIPaddBoolParam(scip,
2735 	         "heuristics/" HEUR_NAME "/backtrack",
2736 	         "use one level of backtracking if infeasibility is encountered?",
2737 	         &heurdata->backtrack, FALSE, DEFAULT_BACKTRACK, NULL, NULL) );
2738 	   SCIP_CALL( SCIPaddBoolParam(scip,
2739 	         "heuristics/" HEUR_NAME "/lp",
2740 	         "should the LP relaxation be solved before the NLP relaxation?",
2741 	         &heurdata->lp, TRUE, DEFAULT_LP, NULL, NULL) );
2742 	   SCIP_CALL( SCIPaddBoolParam(scip,
2743 	         "heuristics/" HEUR_NAME "/preferlpfracs",
2744 	         "prefer variables that are also fractional in LP solution?",
2745 	         &heurdata->preferlpfracs, TRUE, DEFAULT_PREFERLPFRACS, NULL, NULL) );
2746 	   SCIP_CALL( SCIPaddRealParam(scip,
2747 	         "heuristics/" HEUR_NAME "/minsuccquot",
2748 	         "heuristic will not run if less then this percentage of calls succeeded (0.0: no limit)",
2749 	         &heurdata->minsuccquot, FALSE, DEFAULT_MINSUCCQUOT, 0.0, 1.0, NULL, NULL) );
2750 	   SCIP_CALL( SCIPaddRealParam(scip,
2751 	         "heuristics/" HEUR_NAME "/fixquot",
2752 	         "percentage of fractional variables that should be fixed before the next NLP solve",
2753 	         &heurdata->fixquot, FALSE, DEFAULT_FIXQUOT, 0.0, 1.0, NULL, NULL) );
2754 	   SCIP_CALL( SCIPaddBoolParam(scip,
2755 	         "heuristics/" HEUR_NAME "/prefercover",
2756 	         "should variables in a minimal cover be preferred?",
2757 	         &heurdata->prefercover, FALSE, DEFAULT_PREFERCOVER, NULL, NULL) );
2758 	   SCIP_CALL( SCIPaddBoolParam(scip,
2759 	         "heuristics/" HEUR_NAME "/solvesubmip",
2760 	         "should a sub-MIP be solved if all cover variables are fixed?",
2761 	         &heurdata->solvesubmip, FALSE, DEFAULT_SOLVESUBMIP, NULL, NULL) );
2762 	   SCIP_CALL( SCIPaddBoolParam(scip,
2763 	         "heuristics/" HEUR_NAME "/nlpfastfail",
2764 	         "should the NLP solver stop early if it converges slow?",
2765 	         &heurdata->nlpfastfail, FALSE, DEFAULT_NLPFASTFAIL, NULL, NULL) );
2766 	   SCIP_CALL( SCIPaddCharParam(scip,
2767 	         "heuristics/" HEUR_NAME "/nlpstart",
2768 	         "which point should be used as starting point for the NLP solver? ('n'one, last 'f'easible, from dive's'tart)",
2769 	         &heurdata->nlpstart, TRUE, DEFAULT_NLPSTART, "fns", NULL, NULL) );
2770 	   SCIP_CALL( SCIPaddCharParam(scip,
2771 	         "heuristics/" HEUR_NAME "/varselrule",
2772 	         "which variable selection should be used? ('f'ractionality, 'c'oefficient, 'p'seudocost, 'g'uided, 'd'ouble, 'v'eclen)",
2773 	         &heurdata->varselrule, FALSE, DEFAULT_VARSELRULE, "fcpgdv", NULL, NULL) );
2774 	
2775 	   return SCIP_OKAY;
2776 	}
2777