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_vbounds.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood
28   	 * @author Timo Berthold
29   	 * @author Stefan Heinz
30   	 * @author Jens Schulz
31   	 * @author Gerald Gamrath
32   	 *
33   	 * @todo allow smaller fixing rate for probing LP?
34   	 * @todo allow smaller fixing rate after presolve if total number of variables is small (<= 1000)?
35   	 *
36   	 * More details about the heuristic can be found in@n
37   	 * Structure-Based Primal Heuristics for Mixed Integer Programming@n
38   	 * Gerald Gamrath, Timo Berthold, Stefan Heinz, and Michael Winkler@n
39   	 * Optimization in the Real World, Volume 13 of the series Mathematics for Industry, pp 37-53@n
40   	 * Preliminary version available as <a href="https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/5551">ZIB-Report 15-26</a>.
41   	 */
42   	
43   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
44   	
45   	#include "blockmemshell/memory.h"
46   	#include "scip/heur_locks.h"
47   	#include "scip/heur_vbounds.h"
48   	#include "scip/pub_heur.h"
49   	#include "scip/pub_implics.h"
50   	#include "scip/pub_message.h"
51   	#include "scip/pub_misc.h"
52   	#include "scip/pub_tree.h"
53   	#include "scip/pub_var.h"
54   	#include "scip/scip_branch.h"
55   	#include "scip/scip_cons.h"
56   	#include "scip/scip_copy.h"
57   	#include "scip/scip_general.h"
58   	#include "scip/scip_heur.h"
59   	#include "scip/scip_lp.h"
60   	#include "scip/scip_mem.h"
61   	#include "scip/scip_message.h"
62   	#include "scip/scip_numerics.h"
63   	#include "scip/scip_param.h"
64   	#include "scip/scip_prob.h"
65   	#include "scip/scip_probing.h"
66   	#include "scip/scip_sol.h"
67   	#include "scip/scip_solve.h"
68   	#include "scip/scip_solvingstats.h"
69   	#include "scip/scip_timing.h"
70   	#include "scip/scip_tree.h"
71   	#include "scip/scip_var.h"
72   	#include <string.h>
73   	
74   	#ifdef SCIP_STATISTIC
75   	#include "scip/clock.h"
76   	#endif
77   	
78   	#define VBOUNDVARIANT_NOOBJ      0x001u
79   	#define VBOUNDVARIANT_BESTBOUND  0x002u
80   	#define VBOUNDVARIANT_WORSTBOUND 0x004u
81   	
82   	#define HEUR_NAME             "vbounds"
83   	#define HEUR_DESC             "LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood"
84   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_PROP
85   	#define HEUR_PRIORITY         2500
86   	#define HEUR_FREQ             0
87   	#define HEUR_FREQOFS          0
88   	#define HEUR_MAXDEPTH         -1
89   	#define HEUR_TIMING           SCIP_HEURTIMING_BEFORENODE
90   	#define HEUR_USESSUBSCIP      TRUE      /**< does the heuristic use a secondary SCIP instance? */
91   	
92   	#define DEFAULT_MAXNODES      5000LL    /**< maximum number of nodes to regard in the subproblem */
93   	#define DEFAULT_MININTFIXINGRATE 0.65    /**< minimum percentage of integer variables that have to be fixed */
94   	#define DEFAULT_MINMIPFIXINGRATE 0.65    /**< minimuskipobjm percentage of variables that have to be fixed within sub-SCIP
95   	                                         *   (integer and continuous) */
96   	#define DEFAULT_MINIMPROVE    0.01      /**< factor by which vbounds heuristic should at least improve the
97   	                                         *   incumbent */
98   	#define DEFAULT_MINNODES      500LL     /**< minimum number of nodes to regard in the subproblem */
99   	#define DEFAULT_NODESOFS      500LL     /**< number of nodes added to the contingent of the total nodes */
100  	#define DEFAULT_NODESQUOT     0.1       /**< subproblem nodes in relation to nodes of the original problem */
101  	#define DEFAULT_MAXPROPROUNDS 2         /**< maximum number of propagation rounds during probing */
102  	#define DEFAULT_MAXBACKTRACKS 10        /**< maximum number of backtracks during the fixing process */
103  	#define DEFAULT_COPYCUTS      TRUE      /**< should all active cuts from the cutpool of the original scip be copied to
104  	                                         *   constraints of the subscip? */
105  	#define DEFAULT_USELOCKFIXINGS FALSE    /**< should more variables be fixed based on variable locks if
106  	                                         *   the fixing rate was not reached?
107  	                                         */
108  	
109  	/** which variants of the vbounds heuristic that try to stay feasible should be called? */
110  	#define DEFAULT_FEASVARIANT   (VBOUNDVARIANT_BESTBOUND | VBOUNDVARIANT_WORSTBOUND)
111  	
112  	/** which tightening variants of the vbounds heuristic should be called? */
113  	#define DEFAULT_TIGHTENVARIANT   (VBOUNDVARIANT_NOOBJ | VBOUNDVARIANT_BESTBOUND | VBOUNDVARIANT_WORSTBOUND)
114  	
115  	
116  	/*
117  	 * Data structures
118  	 */
119  	
120  	/** primal heuristic data */
121  	struct SCIP_HeurData
122  	{
123  	   SCIP_VAR**            vbvars;             /**< topological sorted variables with respect to the variable bounds */
124  	   SCIP_BOUNDTYPE*       vbbounds;           /**< topological sorted variables with respect to the variable bounds */
125  	   int                   nvbvars;            /**< number of variables in variable lower bound array */
126  	   SCIP_Longint          maxnodes;           /**< maximum number of nodes to regard in the subproblem */
127  	   SCIP_Longint          minnodes;           /**< minimum number of nodes to regard in the subproblem */
128  	   SCIP_Longint          nodesofs;           /**< number of nodes added to the contingent of the total nodes */
129  	   SCIP_Longint          usednodes;          /**< nodes already used by vbounds heuristic in earlier calls */
130  	   SCIP_Real             minintfixingrate;   /**< minimum percentage of integer variables that have to be fixed */
131  	   SCIP_Real             minmipfixingrate;   /**< minimum percentage of variables that have to be fixed within sub-SCIP
132  	                                              *   (integer and continuous) */
133  	   SCIP_Real             minimprove;         /**< factor by which vbounds heuristic should at least improve the incumbent */
134  	   SCIP_Real             nodesquot;          /**< subproblem nodes in relation to nodes of the original problem */
135  	   SCIP_Real             cutoffbound;
136  	   int                   maxproprounds;      /**< maximum number of propagation rounds during probing */
137  	   int                   maxbacktracks;      /**< maximum number of backtracks during the fixing process */
138  	   int                   feasvariant;        /**< which variants of the vbounds heuristic that try to stay feasible
139  	                                              *   should be called? */
140  	   int                   tightenvariant;     /**< which tightening variants of the vbounds heuristic should be called? */
141  	   SCIP_Bool             initialized;        /**< is the candidate list initialized? */
142  	   SCIP_Bool             applicable;         /**< is the heuristic applicable? */
143  	   SCIP_Bool             copycuts;           /**< should all active cuts from cutpool be copied to constraints in
144  	                                              *   subproblem? */
145  	   SCIP_Bool             uselockfixings;     /**< should more variables be fixed based on variable locks if
146  	                                              *   the fixing rate was not reached? */
147  	};
148  	
149  	/**@name Heuristic defines
150  	 *
151  	 * @{
152  	 *
153  	 * The heuristic works on indices representing a bound of a variable. This index will be called bound index in the
154  	 * following. For a given active variable with problem index i (note that active variables have problem indices
155  	 * between 0 and nactivevariable - 1), the bound index of its lower bound is 2*i, the bound index of its upper
156  	 * bound is 2*i + 1. The other way around, a given bound index i corresponds to the variable with problem index
157  	 * i/2 (rounded down), and to the lower bound, if i is even, to the upper bound if i is odd.
158  	 * The following macros can be used to convert bound index into variable problem index and boundtype and vice versa.
159  	 */
160  	#define getLbIndex(idx) (2*(idx))
161  	#define getUbIndex(idx) (2*(idx)+1)
162  	#define getVarIndex(idx) ((idx)/2)
163  	#define getBoundtype(idx) (((idx) % 2 == 0) ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER)
164  	#define isIndexLowerbound(idx) ((idx) % 2 == 0)
165  	#define getOtherBoundIndex(idx) (((idx) % 2 == 0) ? (idx) + 1 : (idx) - 1)
166  	
167  	
168  	/*
169  	 * Local methods
170  	 */
171  	
172  	/** reset heuristic data structure */
173  	static
174  	void heurdataReset(
175  	   SCIP_HEURDATA*        heurdata            /**< structure containing heurdata */
176  	   )
177  	{
178  	   heurdata->vbvars = NULL;
179  	   heurdata->vbbounds = NULL;
180  	   heurdata->nvbvars = 0;
181  	   heurdata->initialized = FALSE;
182  	   heurdata->applicable = FALSE;
183  	}
184  	
185  	
186  	/** performs depth-first-search in the implicitly given directed graph from the given start index */
187  	static
188  	SCIP_RETCODE dfs(
189  	   SCIP*                 scip,               /**< SCIP data structure */
190  	   int                   startnode,          /**< node to start the depth-first-search */
191  	   SCIP_Shortbool*       visited,            /**< array to store for each node, whether it was already visited */
192  	   int*                  dfsstack,           /**< array of size number of nodes to store the stack;
193  	                                              *   only needed for performance reasons */
194  	   int*                  stacknextedge,      /**< array of size number of nodes to store the number of adjacent nodes
195  	                                              *   already visited for each node on the stack; only needed for
196  	                                              *   performance reasons */
197  	   int*                  stacknextcliquevar, /**< array of size number of nodes to store the number of variables
198  	                                              *   already evaluated for the clique currently being evaluated */
199  	   int*                  cliqueexit,         /**< exit node when entering a clique */
200  	   int*                  dfsnodes,           /**< array of nodes that can be reached starting at startnode, in reverse
201  	                                              *   dfs order */
202  	   int*                  ndfsnodes           /**< pointer to store number of nodes that can be reached starting at
203  	                                              *   startnode */
204  	   )
205  	{
206  	   SCIP_VAR** vars;
207  	   SCIP_VAR* startvar;
208  	   SCIP_VAR** vbvars;
209  	   SCIP_Real* coefs;
210  	   SCIP_Bool lower;
211  	   SCIP_Bool found;
212  	   int maxstacksize;
213  	   int stacksize;
214  	   int curridx;
215  	   int idx;
216  	   int nvbvars;
217  	   int i;
218  	
219  	   assert(startnode >= 0);
220  	   assert(startnode < 2 * SCIPgetNVars(scip));
221  	   assert(visited != NULL);
222  	   assert(visited[startnode] == FALSE);
223  	   assert(dfsstack != NULL);
224  	   assert(dfsnodes != NULL);
225  	   assert(ndfsnodes != NULL);
226  	
227  	   vars = SCIPgetVars(scip);
228  	
229  	   /* put start node on the stack */
230  	   dfsstack[0] = startnode;
231  	   stacknextcliquevar[0] = 0;
232  	   stacknextedge[0] = 0;
233  	   maxstacksize = 1;
234  	   stacksize = 1;
235  	   idx = -1;
236  	
237  	   /* we run until no more bounds indices are on the stack */
238  	   while( stacksize > 0 )
239  	   {
240  	      /* get next node from stack */
241  	      curridx = dfsstack[stacksize - 1];
242  	
243  	      /* mark current node as visited */
244  	      assert(visited[curridx] == (stacknextedge[stacksize - 1] != 0));
245  	      visited[curridx] = TRUE;
246  	      found = FALSE;
247  	
248  	      startvar = vars[getVarIndex(curridx)];
249  	      lower = isIndexLowerbound(curridx);
250  	
251  	      if( stacknextedge[stacksize - 1] >= 0 )
252  	      {
253  	         /* go over edges corresponding to varbounds */
254  	         if( lower )
255  	         {
256  	            vbvars = SCIPvarGetVlbVars(startvar);
257  	            coefs = SCIPvarGetVlbCoefs(startvar);
258  	            nvbvars = SCIPvarGetNVlbs(startvar);
259  	         }
260  	         else
261  	         {
262  	            vbvars = SCIPvarGetVubVars(startvar);
263  	            coefs = SCIPvarGetVubCoefs(startvar);
264  	            nvbvars = SCIPvarGetNVubs(startvar);
265  	         }
266  	
267  	         /* iterate over all vbounds for the given bound */
268  	         for( i = stacknextedge[stacksize - 1]; i < nvbvars; ++i )
269  	         {
270  	            if( !SCIPvarIsActive(vbvars[i]) )
271  	               continue;
272  	
273  	            idx = (SCIPisPositive(scip, coefs[i]) == lower) ? getLbIndex(SCIPvarGetProbindex(vbvars[i])) : getUbIndex(SCIPvarGetProbindex(vbvars[i]));
274  	            assert(idx >= 0);
275  	
276  	            /* break when the first unvisited node is reached */
277  	            if( !visited[idx] )
278  	               break;
279  	         }
280  	
281  	         /* we stopped because we found an unhandled node and not because we reached the end of the list */
282  	         if( i < nvbvars )
283  	         {
284  	            assert(!visited[idx]);
285  	
286  	            /* put the adjacent node onto the stack */
287  	            dfsstack[stacksize] = idx;
288  	            stacknextedge[stacksize] = 0;
289  	            stacknextcliquevar[stacksize] = 0;
290  	            stacknextedge[stacksize - 1] = i + 1;
291  	            stacksize++;
292  	            assert(stacksize <= 2* SCIPgetNVars(scip));
293  	
294  	            /* restart while loop, get next index from stack */
295  	            continue;
296  	         }
297  	      }
298  	
299  	      stacknextedge[stacksize - 1] = -1;
300  	
301  	      /* treat cliques */
302  	      if( SCIPvarIsBinary(startvar) )
303  	      {
304  	         SCIP_CLIQUE** cliques = SCIPvarGetCliques(startvar, !lower);
305  	         int ncliques = SCIPvarGetNCliques(startvar, !lower);
306  	         int j;
307  	
308  	         /* iterate over all not yet handled cliques and search for an unvisited node */
309  	         for( j = -stacknextedge[stacksize - 1] - 1; j < ncliques; ++j )
310  	         {
311  	            SCIP_VAR** cliquevars;
312  	            SCIP_Bool* cliquevals;
313  	            int ncliquevars;
314  	
315  	            /* the first time we evaluate this clique for the current node */
316  	            if( stacknextcliquevar[stacksize - 1] == 0 )
317  	            {
318  	               if( cliqueexit[SCIPcliqueGetIndex(cliques[j])] > 0 )
319  	               {
320  	                  if( !visited[cliqueexit[SCIPcliqueGetIndex(cliques[j])] - 1] &&
321  	                     cliqueexit[SCIPcliqueGetIndex(cliques[j])] - 1 != curridx )
322  	                  {
323  	                     stacknextedge[stacksize - 1] = -j - 2;
324  	                     stacknextcliquevar[stacksize - 1] = 0;
325  	                     idx = cliqueexit[SCIPcliqueGetIndex(cliques[j])] - 1;
326  	                     cliqueexit[SCIPcliqueGetIndex(cliques[j])] = -1;
327  	                     found = TRUE;
328  	                  }
329  	                  else
330  	                     continue;
331  	               }
332  	               else if( cliqueexit[SCIPcliqueGetIndex(cliques[j])] == 0 )
333  	               {
334  	                  cliqueexit[SCIPcliqueGetIndex(cliques[j])] = getOtherBoundIndex(curridx) + 1;
335  	               }
336  	               else
337  	                  continue;
338  	            }
339  	            if( !found )
340  	            {
341  	               cliquevars = SCIPcliqueGetVars(cliques[j]);
342  	               cliquevals = SCIPcliqueGetValues(cliques[j]);
343  	               ncliquevars = SCIPcliqueGetNVars(cliques[j]);
344  	
345  	               for( i = 0; i < ncliquevars; ++i )
346  	               {
347  	                  assert(SCIPvarIsActive(cliquevars[i]));
348  	
349  	                  if( cliquevars[i] == startvar )
350  	                     continue;
351  	
352  	                  if( cliquevals[i] )
353  	                     idx = getLbIndex(SCIPvarGetProbindex(cliquevars[i]));
354  	                  else
355  	                     idx = getUbIndex(SCIPvarGetProbindex(cliquevars[i]));
356  	
357  	                  assert(idx >= 0 && idx < 2 * SCIPgetNVars(scip));
358  	
359  	                  /* break when the first unvisited node is reached */
360  	                  if( idx >= 0 && !visited[idx] )
361  	                  {
362  	                     if( i < ncliquevars - 1 )
363  	                     {
364  	                        stacknextedge[stacksize - 1] = -j - 1;
365  	                        stacknextcliquevar[stacksize - 1] = i + 1;
366  	                     }
367  	                     else
368  	                     {
369  	                        stacknextedge[stacksize - 1] = -j - 2;
370  	                        stacknextcliquevar[stacksize - 1] = 0;
371  	                     }
372  	                     found = TRUE;
373  	                     break;
374  	                  }
375  	               }
376  	            }
377  	            if( found )
378  	            {
379  	               assert(!visited[idx]);
380  	
381  	               /* put the adjacent node onto the stack */
382  	               dfsstack[stacksize] = idx;
383  	               stacknextedge[stacksize] = 0;
384  	               stacknextcliquevar[stacksize] = 0;
385  	               stacksize++;
386  	               assert(stacksize <= 2* SCIPgetNVars(scip));
387  	
388  	               break;
389  	            }
390  	         }
391  	         /* restart while loop, get next index from stack */
392  	         if( found )
393  	            continue;
394  	      }
395  	
396  	      maxstacksize = MAX(maxstacksize, stacksize);
397  	
398  	      /* the current node was completely handled, remove it from the stack */
399  	      stacksize--;
400  	
401  	      if( (maxstacksize > 1) && SCIPvarGetType(startvar) != SCIP_VARTYPE_CONTINUOUS )
402  	      {
403  	         /* store node in the sorted nodes array */
404  	         dfsnodes[(*ndfsnodes)] = curridx;
405  	         (*ndfsnodes)++;
406  	      }
407  	      else
408  	         visited[curridx] = FALSE;
409  	   }
410  	
411  	   return SCIP_OKAY;
412  	}
413  	
414  	
415  	/** sort the bounds of variables topologically */
416  	static
417  	SCIP_RETCODE topologicalSort(
418  	   SCIP*                 scip,               /**< SCIP data structure */
419  	   int*                  vbvars,             /**< array to store variable bounds in topological order */
420  	   int*                  nvbvars             /**< pointer to store number of variable bounds in the graph */
421  	   )
422  	{
423  	   int* dfsstack;
424  	   int* stacknextedge;
425  	   int* stacknextcliquevar;
426  	   int* cliqueexit;
427  	   SCIP_Shortbool* visited;
428  	   int nbounds;
429  	   int i;
430  	
431  	   assert(scip != NULL);
432  	
433  	   nbounds = 2 * SCIPgetNVars(scip);
434  	
435  	   SCIP_CALL( SCIPallocBufferArray(scip, &dfsstack, nbounds) );
436  	   SCIP_CALL( SCIPallocBufferArray(scip, &stacknextedge, nbounds) );
437  	   SCIP_CALL( SCIPallocBufferArray(scip, &stacknextcliquevar, nbounds) );
438  	   SCIP_CALL( SCIPallocClearBufferArray(scip, &cliqueexit, SCIPgetNCliques(scip)) );
439  	   SCIP_CALL( SCIPallocClearBufferArray(scip, &visited, nbounds) );
440  	
441  	   /* while there are unvisited nodes, run dfs on the inverse graph starting from one of these nodes; the dfs orders are
442  	    * stored in the topoorder array, later dfs calls are just appended after the stacks of previous dfs calls, which
443  	    * gives us a topological order
444  	    */
445  	   for( i = 0; i < nbounds; ++i )
446  	   {
447  	      if( !visited[i] )
448  	      {
449  	         SCIP_CALL( dfs(scip, i, visited, dfsstack, stacknextedge, stacknextcliquevar, cliqueexit, vbvars, nvbvars) );
450  	      }
451  	   }
452  	   assert(*nvbvars <= nbounds);
453  	
454  	   SCIPfreeBufferArray(scip, &visited);
455  	   SCIPfreeBufferArray(scip, &cliqueexit);
456  	   SCIPfreeBufferArray(scip, &stacknextcliquevar);
457  	   SCIPfreeBufferArray(scip, &stacknextedge);
458  	   SCIPfreeBufferArray(scip, &dfsstack);
459  	
460  	   return SCIP_OKAY;
461  	}
462  	
463  	/** initialize candidate lists */
464  	static
465  	SCIP_RETCODE initializeCandsLists(
466  	   SCIP*                 scip,               /**< original SCIP data structure */
467  	   SCIP_HEURDATA*        heurdata            /**< structure containing heurdata */
468  	   )
469  	{
470  	   SCIP_VAR** vars;
471  	   int* vbs;
472  	   int nvars;
473  	   int nvbs;
474  	   int v;
475  	
476  	   SCIPdebugMsg(scip, "initialize variable bound heuristic (%s)\n", SCIPgetProbName(scip));
477  	
478  	   vars = SCIPgetVars(scip);
479  	   nvars = SCIPgetNIntVars(scip) + SCIPgetNBinVars(scip) + SCIPgetNImplVars(scip);
480  	   nvbs = 0;
481  	
482  	   /* initialize data */
483  	   heurdata->usednodes = 0;
484  	   heurdata->initialized = TRUE;
485  	
486  	   if( nvars == 0 )
487  	      return SCIP_OKAY;
488  	
489  	   /* allocate memory for the arrays of the heurdata */
490  	   SCIP_CALL( SCIPallocBufferArray(scip, &vbs, 2 * nvars) );
491  	
492  	   /* create the topological sorted variable array with respect to the variable bounds */
493  	   SCIP_CALL( topologicalSort(scip, vbs, &nvbs) );
494  	
495  	   /* check if the candidate list contains enough candidates */
496  	   if( nvbs > 0 && nvbs >= 0.1 * heurdata->minintfixingrate * nvars )
497  	   {
498  	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->vbvars, nvbs) );
499  	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->vbbounds, nvbs) );
500  	
501  	      /* capture variable candidate list */
502  	      for( v = 0; v < nvbs; ++v )
503  	      {
504  	         heurdata->vbvars[v] = vars[getVarIndex(vbs[v])];
505  	         heurdata->vbbounds[v] = getBoundtype(vbs[v]);
506  	         assert(SCIPvarIsIntegral(heurdata->vbvars[v]));
507  	
508  	         SCIP_CALL( SCIPcaptureVar(scip, heurdata->vbvars[v]) );
509  	      }
510  	
511  	      heurdata->nvbvars = nvbs;
512  	      heurdata->applicable = TRUE;
513  	   }
514  	
515  	   /* free buffer arrays */
516  	   SCIPfreeBufferArray(scip, &vbs);
517  	
518  	   SCIPstatisticMessage("vbvars %.3g (%s)\n",
519  	      (nvbs * 100.0) / nvars, SCIPgetProbName(scip));
520  	
521  	   /* if there is already a solution, add an objective cutoff */
522  	   if( SCIPgetNSols(scip) > 0 )
523  	   {
524  	      SCIP_Real upperbound;
525  	      SCIP_Real minimprove;
526  	      SCIP_Real cutoffbound;
527  	
528  	      minimprove = heurdata->minimprove;
529  	      assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
530  	
531  	      upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
532  	
533  	      if( !SCIPisInfinity(scip, -1.0 * SCIPgetLowerbound(scip)) )
534  	      {
535  	         cutoffbound = (1-minimprove) * SCIPgetUpperbound(scip) + minimprove * SCIPgetLowerbound(scip);
536  	      }
537  	      else
538  	      {
539  	         if( SCIPgetUpperbound ( scip ) >= 0 )
540  	            cutoffbound = (1 - minimprove) * SCIPgetUpperbound(scip);
541  	         else
542  	            cutoffbound = (1 + minimprove) * SCIPgetUpperbound(scip);
543  	      }
544  	      heurdata->cutoffbound = MIN(upperbound, cutoffbound);
545  	   }
546  	   else
547  	      heurdata->cutoffbound = SCIPinfinity(scip);
548  	   return SCIP_OKAY;
549  	}
550  	
551  	/** apply variable bound fixing during probing */
552  	static
553  	SCIP_RETCODE applyVboundsFixings(
554  	   SCIP*                 scip,               /**< original SCIP data structure */
555  	   SCIP_HEURDATA*        heurdata,           /**< structure containing heurdata */
556  	   SCIP_VAR**            vars,               /**< variables to fix during probing */
557  	   int                   nvbvars,            /**< number of variables in the variable bound graph */
558  	   SCIP_Bool             tighten,            /**< should variables be fixed to cause other fixings? */
559  	   int                   obj,                /**< should the objective be taken into account? */
560  	   SCIP_Bool*            allobj1,            /**< pointer to store whether all variables were fixed according to obj=1 scheme */
561  	   SCIP_Bool*            allobj2,            /**< pointer to store whether all variables were fixed according to obj=2 scheme */
562  	   SCIP_Bool*            backtracked,        /**< was backtracking performed at least once? */
563  	   SCIP_Bool*            infeasible          /**< pointer to store whether propagation detected infeasibility */
564  	   )
565  	{
566  	   SCIP_VAR* lastvar;
567  	   SCIP_VAR* var;
568  	   SCIP_Real lastfixval;
569  	   SCIP_Bool lastfixedlb;
570  	   SCIP_Bool fixtolower;
571  	   SCIP_BOUNDTYPE bound;
572  	   int nbacktracks = 0;
573  	   int v;
574  	
575  	   /* loop over variables in topological order */
576  	   for( v = 0; v < nvbvars && !(*infeasible); ++v )
577  	   {
578  	      var = vars[v];
579  	      bound = heurdata->vbbounds[v];
580  	
581  	      /*SCIPdebugMsg(scip, "topoorder[%d]: %s(%s) (%s) [%g,%g] (obj=%g)\n", v,
582  	         bound == SCIP_BOUNDTYPE_UPPER ? "ub" : "lb", SCIPvarGetName(var),
583  	         SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS ? "c" : "d",
584  	         SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPvarGetObj(var));*/
585  	
586  	      /* only check integer or binary variables */
587  	      if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
588  	         continue;
589  	
590  	      /* skip variables which are already fixed */
591  	      if( SCIPvarGetLbLocal(var) + 0.5 > SCIPvarGetUbLocal(var) )
592  	         continue;
593  	
594  	      /* there are two cases for tighten:
595  	       * 1) tighten == TRUE:  we go through the list of variables and fix variables to force propagation;
596  	       *                      this is be obtained by fixing the variable to the other bound (which means
597  	       *                      that the current bound is changed and so, much propagation is triggered
598  	       *                      since we are starting with the bounds which are most influential).
599  	       * 2) tighten == FALSE: we fix variables to avoid too much propagation in order to avoid reaching
600  	       *                      infeasibility. Therefore, we fix the variable to the current bound, so that
601  	       *                      this bound is not changed and does not propagate. The other bound is changed
602  	       *                      and propagates, but is later in the order, so less influential.
603  	       */
604  	      fixtolower = (tighten == (bound == SCIP_BOUNDTYPE_UPPER));
605  	
606  	      /* if we want to take into account the objective function coefficients, we only perform a fixing if the variable
607  	       *  would be fixed to its best bound; otherwise, we just continue
608  	       */
609  	      if( ((SCIPvarGetObj(var) >= 0) != fixtolower) )
610  	      {
611  	         if( obj == 1 )
612  	            continue;
613  	         else
614  	            *allobj1 = FALSE;
615  	      }
616  	      /* if we want to take into account the objective function coefficients but reverted, we only perform a fixing if the variable
617  	       *  would be fixed to its worst bound; otherwise, we just continue
618  	       */
619  	      if( ((SCIPvarGetObj(var) >= 0) == fixtolower) )
620  	      {
621  	         if( obj == 2 )
622  	            continue;
623  	         else
624  	            *allobj2 = FALSE;
625  	      }
(1) Event value_overwrite: Overwriting previous write to "lastvar" with value from "var".
Also see events: [assigned_pointer]
626  	      lastvar = var;
627  	
628  	      /* fix the variable to its bound */
629  	      if( fixtolower )
630  	      {
631  	         /* we cannot fix to infinite bounds */
632  	         if( SCIPisInfinity(scip, -SCIPvarGetLbLocal(var)) )
633  	            continue;
634  	
635  	         /* only open a new probing node if we will not exceed the maximal tree depth */
636  	         if( SCIP_MAXTREEDEPTH > SCIPgetDepth(scip) )
637  	         {
638  	            SCIP_CALL( SCIPnewProbingNode(scip) );
639  	         }
640  	
641  	         /* fix variable to lower bound */
642  	         SCIP_CALL( SCIPfixVarProbing(scip, var, SCIPvarGetLbLocal(var)) );
643  	         SCIPdebugMsg(scip, "fixing %d: variable <%s> (obj=%g) to lower bound <%g> (%d pseudo cands)\n",
644  	            v, SCIPvarGetName(var), SCIPvarGetObj(var), SCIPvarGetLbLocal(var), SCIPgetNPseudoBranchCands(scip));
645  	         lastfixedlb = TRUE;
646  	         lastfixval = SCIPvarGetLbLocal(var);
647  	      }
648  	      else
649  	      {
650  	         /* we cannot fix to infinite bounds */
651  	         if( SCIPisInfinity(scip, SCIPvarGetUbLocal(var)) )
652  	            continue;
653  	
654  	         /* only open a new probing node if we will not exceed the maximal tree depth */
655  	         if( SCIP_MAXTREEDEPTH > SCIPgetDepth(scip) )
656  	         {
657  	            SCIP_CALL( SCIPnewProbingNode(scip) );
658  	         }
659  	
660  	         /* fix variable to upper bound */
661  	         SCIP_CALL( SCIPfixVarProbing(scip, var, SCIPvarGetUbLocal(var)) );
662  	         SCIPdebugMsg(scip, "fixing %d: variable <%s> (obj=%g) to upper bound <%g> (%d pseudo cands)\n",
663  	            v, SCIPvarGetName(var), SCIPvarGetObj(var), SCIPvarGetUbLocal(var), SCIPgetNPseudoBranchCands(scip));
664  	         lastfixedlb = FALSE;
665  	         lastfixval = SCIPvarGetUbLocal(var);
666  	      }
667  	
668  	      /* check if problem is already infeasible */
669  	      SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, infeasible, NULL) );
670  	
671  	      /* probing detected infeasibility: backtrack */
672  	      if( *infeasible )
673  	      {
674  	         assert(lastvar != NULL);
675  	
676  	         SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip) - 1) );
677  	         ++nbacktracks;
678  	         *infeasible = FALSE;
679  	
680  	         /* increase the lower bound of the variable which caused the infeasibility */
681  	         if( lastfixedlb && lastfixval + 0.5 < SCIPvarGetUbLocal(lastvar) )
682  	         {
683  	            if( lastfixval + 0.5 > SCIPvarGetLbLocal(lastvar) )
684  	            {
685  	               SCIP_CALL( SCIPchgVarLbProbing(scip, lastvar, lastfixval + 1.0) );
686  	            }
687  	         }
688  	         else if( !lastfixedlb && lastfixval - 0.5 > SCIPvarGetLbLocal(lastvar) )
689  	         {
690  	            if( lastfixval - 0.5 < SCIPvarGetUbLocal(lastvar) )
691  	            {
692  	               SCIP_CALL( SCIPchgVarUbProbing(scip, lastvar, lastfixval - 1.0) );
693  	            }
694  	         }
695  	         /* because of the limited number of propagation rounds, it may happen that conflict analysis finds a valid
696  	          * global bound for the last fixed variable that conflicts with applying the reverse bound change after backtracking;
697  	          * in that case, we ran into a deadend and stop
698  	          */
699  	         else
700  	         {
701  	            *infeasible = TRUE;
702  	         }
(2) Event assigned_pointer: Assigning value "NULL" to "lastvar" here, but that stored value is overwritten before it can be used.
Also see events: [value_overwrite]
703  	         lastvar = NULL;
704  	
705  	         if( !(*infeasible) )
706  	         {
707  	            /* propagate fixings */
708  	            SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, infeasible, NULL) );
709  	
710  	            SCIPdebugMessage("backtrack %d was %sfeasible\n", nbacktracks, (*infeasible ? "in" : ""));
711  	         }
712  	
713  	         if( *infeasible )
714  	         {
715  	            SCIPdebugMsg(scip, "probing was infeasible after %d backtracks\n", nbacktracks);
716  	
717  	            break;
718  	         }
719  	         else if( nbacktracks > heurdata->maxbacktracks )
720  	         {
721  	            SCIPdebugMsg(scip, "interrupt probing after %d backtracks\n", nbacktracks);
722  	            break;
723  	         }
724  	      }
725  	   }
726  	
727  	   *backtracked = (nbacktracks > 0);
728  	
729  	   return SCIP_OKAY;
730  	}
731  	
732  	/** copy problem to sub-SCIP, solve it, and add solutions */
733  	static
734  	SCIP_RETCODE setupAndSolveSubscip(
735  	   SCIP*                 scip,               /**< original SCIP data structure */
736  	   SCIP*                 subscip,            /**< SCIP structure of the subproblem */
737  	   SCIP_HEUR*            heur,               /**< heuristic */
738  	   SCIP_VAR**            vars,               /**< variables of the main SCIP */
739  	   int                   nvars,              /**< number of variables of the main SCIP */
740  	   SCIP_Longint          nstallnodes,        /**< stalling node limit for the sub-SCIP */
741  	   SCIP_Real             lowerbound,         /**< lower bound of the main SCIP / current subproblem */
742  	   int*                  nprevars,           /**< pointer to store the number of presolved variables */
743  	   SCIP_Bool*            wasfeas,            /**< pointer to store if a feasible solution was found */
744  	   SCIP_RESULT*          result              /**< pointer to store the result */
745  	   )
746  	{
747  	   SCIP_HEURDATA* heurdata;
748  	   SCIP_VAR** subvars;
749  	   SCIP_HASHMAP* varmap;
750  	   int i;
751  	
752  	   assert(scip != NULL);
753  	   assert(subscip != NULL);
754  	   assert(heur != NULL);
755  	
756  	   heurdata = SCIPheurGetData(heur);
757  	   assert(heurdata != NULL);
758  	
759  	   /* create the variable mapping hash map */
760  	   SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(subscip), nvars) );
761  	
762  	   SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmap, NULL, "_vbounds", NULL, NULL, 0, FALSE, FALSE, FALSE,
763  	         TRUE, NULL) );
764  	
765  	   if( heurdata->copycuts )
766  	   {
767  	      /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
768  	      SCIP_CALL( SCIPcopyCuts(scip, subscip, varmap, NULL, FALSE, NULL) );
769  	   }
770  	
771  	   SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
772  	
773  	   for( i = 0; i < nvars; i++ )
774  	      subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[i]);
775  	
776  	   /* free hash map */
777  	   SCIPhashmapFree(&varmap);
778  	
779  	   /* do not abort subproblem on CTRL-C */
780  	   SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
781  	
782  	#ifdef SCIP_DEBUG
783  	   /* for debugging, enable full output */
784  	   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
785  	   SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
786  	#else
787  	   /* disable statistic timing inside sub SCIP and output to console */
788  	   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
789  	   SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
790  	#endif
791  	
792  	   /* set limits for the subproblem */
793  	   SCIP_CALL( SCIPcopyLimits(scip, subscip) );
794  	   SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) );
795  	   SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", heurdata->maxnodes) );
796  	
797  	   /* speed up sub-SCIP by not checking dual LP feasibility */
798  	   SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
799  	
800  	   /* forbid call of heuristics and separators solving sub-CIPs */
801  	   SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
802  	
803  	   /* disable cutting plane separation */
804  	   SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
805  	
806  	   /* disable expensive presolving */
807  	   SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
808  	
809  	   /* use inference branching */
810  	   if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
811  	   {
812  	      SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
813  	   }
814  	
815  	   /* set a cutoff bound */
816  	   if( SCIPgetNSols(scip) > 0 )
817  	   {
818  	      SCIP_Real upperbound;
819  	      SCIP_Real minimprove;
820  	      SCIP_Real cutoffbound;
821  	
822  	      minimprove = heurdata->minimprove;
823  	      assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
824  	
825  	      upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
826  	
827  	      if( !SCIPisInfinity(scip, -1.0 * lowerbound) )
828  	      {
829  	         cutoffbound = (1-minimprove) * SCIPgetUpperbound(scip) + minimprove * lowerbound;
830  	      }
831  	      else
832  	      {
833  	         if( SCIPgetUpperbound ( scip ) >= 0 )
834  	            cutoffbound = (1 - minimprove) * SCIPgetUpperbound(scip);
835  	         else
836  	            cutoffbound = (1 + minimprove) * SCIPgetUpperbound(scip);
837  	      }
838  	      heurdata->cutoffbound = MIN(upperbound, cutoffbound);
839  	   }
840  	
841  	   if( !SCIPisInfinity(scip, heurdata->cutoffbound) )
842  	   {
843  	      SCIP_CALL( SCIPsetObjlimit(subscip, heurdata->cutoffbound) );
844  	      SCIPdebugMsg(scip, "setting objlimit for subscip to %g\n", heurdata->cutoffbound);
845  	   }
846  	
847  	   SCIPdebugMsg(scip, "starting solving vbound-submip at time %g\n", SCIPgetSolvingTime(scip));
848  	
849  	   /* solve the subproblem */
850  	   /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
851  	    * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
852  	    */
853  	   SCIP_CALL_ABORT( SCIPpresolve(subscip) );
854  	
855  	   SCIPdebugMsg(scip, "vbounds heuristic presolved subproblem at time %g : %d vars, %d cons; fixing value = %g\n",
856  	      SCIPgetSolvingTime(scip), SCIPgetNVars(subscip), SCIPgetNConss(subscip),
857  	      ((nvars - SCIPgetNVars(subscip)) / (SCIP_Real)nvars));
858  	
859  	   *nprevars = SCIPgetNVars(subscip);
860  	
861  	   /* after presolving, we should have at least reached a certain fixing rate over ALL variables (including continuous)
862  	    * to ensure that not only the MIP but also the LP relaxation is easy enough
863  	    */
864  	   if( ((nvars - SCIPgetNVars(subscip)) / (SCIP_Real)nvars) >= heurdata->minmipfixingrate )
865  	   {
866  	      SCIPdebugMsg(scip, "solving subproblem: nstallnodes=%" SCIP_LONGINT_FORMAT ", maxnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->maxnodes);
867  	
868  	      SCIP_CALL_ABORT( SCIPsolve(subscip) );
869  	
870  	      SCIPdebugMsg(scip, "ending solving vbounds-submip at time %g, status = %d\n", SCIPgetSolvingTime(scip), SCIPgetStatus(subscip));
871  	
872  	      /* check, whether a solution was found; due to numerics, it might happen that not all solutions are feasible ->
873  	       * try all solutions until one was accepted
874  	       */
875  	      SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, wasfeas, NULL) );
876  	      if( (*wasfeas) )
877  	      {
878  	         SCIPdebugMsg(scip, "found feasible solution in sub-MIP\n");
879  	         *result = SCIP_FOUNDSOL;
880  	      }
881  	   }
882  	
883  	#ifdef SCIP_DEBUG
884  	   SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
885  	#endif
886  	
887  	      /* free subproblem */
888  	   SCIPfreeBufferArray(scip, &subvars);
889  	
890  	   return SCIP_OKAY;
891  	}
892  	
893  	/** main procedure of the vbounds heuristic */
894  	static
895  	SCIP_RETCODE applyVbounds(
896  	   SCIP*                 scip,               /**< original SCIP data structure */
897  	   SCIP_HEUR*            heur,               /**< heuristic */
898  	   SCIP_HEURDATA*        heurdata,           /**< heuristic data structure */
899  	   SCIP_VAR**            vbvars,             /**< variables to fix during probing */
900  	   int                   nvbvars,            /**< number of variables to fix */
901  	   SCIP_Bool             tighten,            /**< should variables be fixed to cause other fixings? */
902  	   int                   obj,                /**< should the objective be taken into account? */
903  	   SCIP_Bool*            skipobj1,           /**< pointer to store whether the run with obj=1 can be skipped, or NULL */
904  	   SCIP_Bool*            skipobj2,           /**< pointer to store whether the run with obj=2 can be skipped, or NULL */
905  	   SCIP_RESULT*          result              /**< pointer to store the result */
906  	   )
907  	{
908  	   SCIPstatistic( SCIP_CLOCK* clock; )
909  	   SCIP_VAR** vars;
910  	   SCIP_Longint nstallnodes;
911  	   SCIP_LPSOLSTAT lpstatus;
912  	   SCIP_Real lowerbound;
913  	   SCIP_Bool wasfeas = FALSE;
914  	   SCIP_Bool cutoff;
915  	   SCIP_Bool lperror;
916  	   SCIP_Bool solvelp;
917  	   SCIP_Bool allobj1 = TRUE;
918  	   SCIP_Bool allobj2 = TRUE;
919  	   SCIP_Bool backtracked = TRUE;
920  	   int oldnpscands;
921  	   int npscands;
922  	   int nvars;
923  	   int nprevars;
924  	
925  	   assert(heur != NULL);
926  	   assert(heurdata != NULL);
927  	   assert(nvbvars > 0);
928  	
929  	   /* initialize default values */
930  	   cutoff = FALSE;
931  	
932  	   if( skipobj1 != NULL )
933  	      *skipobj1 = FALSE;
934  	   if( skipobj2 != NULL )
935  	      *skipobj2 = FALSE;
936  	
937  	   if( nvbvars < SCIPgetNVars(scip) * heurdata->minintfixingrate )
938  	      return SCIP_OKAY;
939  	
940  	   if( *result == SCIP_DIDNOTRUN )
941  	      *result = SCIP_DIDNOTFIND;
942  	
943  	   lowerbound = SCIPgetLowerbound(scip);
944  	
945  	   oldnpscands = SCIPgetNPseudoBranchCands(scip);
946  	
947  	   /* calculate the maximal number of branching nodes until heuristic is aborted */
948  	   nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
949  	
950  	   /* reward variable bounds heuristic if it succeeded often */
951  	   nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
952  	   nstallnodes -= 100 * SCIPheurGetNCalls(heur);  /* count the setup costs for the sub-MIP as 100 nodes */
953  	   nstallnodes += heurdata->nodesofs;
954  	
955  	   /* determine the node limit for the current process */
956  	   nstallnodes -= heurdata->usednodes;
957  	   nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
958  	
959  	   SCIPdebugMsg(scip, "apply variable bounds heuristic at node %lld on %d variable bounds, tighten: %u obj: %d\n",
960  	      SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), nvbvars, tighten, obj);
961  	
962  	   /* check whether we have enough nodes left to call subproblem solving */
963  	   if( nstallnodes < heurdata->minnodes )
964  	   {
965  	      SCIPdebugMsg(scip, "skipping " HEUR_NAME ": nstallnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->minnodes);
966  	      return SCIP_OKAY;
967  	   }
968  	
969  	   if( SCIPisStopped(scip) )
970  	      return SCIP_OKAY;
971  	
972  	   SCIPstatistic( SCIP_CALL( SCIPcreateClock(scip, &clock) ) );
973  	   SCIPstatistic( SCIP_CALL( SCIPstartClock(scip, clock) ) );
974  	
975  	   /* check whether the LP should be solved at the current node in the tree to determine whether the heuristic
976  	    * is allowed to solve an LP
977  	    */
978  	   solvelp = SCIPhasCurrentNodeLP(scip);
979  	
980  	   if( !SCIPisLPConstructed(scip) && solvelp )
981  	   {
982  	      SCIP_CALL( SCIPconstructLP(scip, &cutoff) );
983  	
984  	      /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */
985  	      if( cutoff )
986  	      {
987  	         SCIP_CALL( SCIPcutoffNode(scip, SCIPgetCurrentNode(scip)) );
988  	         goto TERMINATE;
989  	      }
990  	
991  	      SCIP_CALL( SCIPflushLP(scip) );
992  	   }
993  	
994  	   /* get variable data of original problem */
995  	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
996  	
997  	   SCIPstatistic( nprevars = nvars; )
998  	
999  	   /* start probing */
1000 	   SCIP_CALL( SCIPstartProbing(scip) );
1001 	
1002 	#ifdef COLLECTSTATISTICS
1003 	   SCIPenableVarHistory(scip);
1004 	#endif
1005 	
1006 	   /* apply the variable fixings */
1007 	   SCIP_CALL( applyVboundsFixings(scip, heurdata, vbvars, nvbvars, tighten, obj, &allobj1, &allobj2, &backtracked, &cutoff) );
1008 	
1009 	   if( skipobj1 != NULL )
1010 	      *skipobj1 = allobj1;
1011 	
1012 	   if( skipobj2 != NULL )
1013 	      *skipobj2 = allobj2;
1014 	
1015 	   if( cutoff || SCIPisStopped(scip) )
1016 	      goto TERMINATE;
1017 	
1018 	   /* check that we had enough fixings */
1019 	   npscands = SCIPgetNPseudoBranchCands(scip);
1020 	
1021 	   SCIPdebugMsg(scip, "npscands=%d, oldnpscands=%d, heurdata->minintfixingrate=%g\n", npscands, oldnpscands, heurdata->minintfixingrate);
1022 	
1023 	   /* check fixing rate */
1024 	   if( npscands > oldnpscands * (1.0 - heurdata->minintfixingrate) )
1025 	   {
1026 	      if( heurdata->uselockfixings && npscands <= 2.0 * oldnpscands * (1.0 - heurdata->minintfixingrate) )
1027 	      {
1028 	         SCIP_Bool allrowsfulfilled = FALSE;
1029 	
1030 	         SCIP_CALL( SCIPapplyLockFixings(scip, NULL, &cutoff, &allrowsfulfilled) );
1031 	
1032 	         if( cutoff || SCIPisStopped(scip) )
1033 	         {
1034 	            SCIPdebugMsg(scip, "cutoff or timeout in locks fixing\n");
1035 	            goto TERMINATE;
1036 	         }
1037 	
1038 	         npscands = SCIPgetNPseudoBranchCands(scip);
1039 	
1040 	         SCIPdebugMsg(scip, "after lockfixings: npscands=%d, oldnpscands=%d, allrowsfulfilled=%u, heurdata->minintfixingrate=%g\n",
1041 	            npscands, oldnpscands, allrowsfulfilled, heurdata->minintfixingrate);
1042 	
1043 	         if( !allrowsfulfilled && npscands > oldnpscands * (1 - heurdata->minintfixingrate) )
1044 	         {
1045 	            SCIPdebugMsg(scip, "--> too few fixings\n");
1046 	
1047 	            goto TERMINATE;
1048 	         }
1049 	      }
1050 	      else
1051 	      {
1052 	         SCIPdebugMsg(scip, "--> too few fixings\n");
1053 	
1054 	         goto TERMINATE;
1055 	      }
1056 	   }
1057 	
1058 	   assert(!cutoff);
1059 	
1060 	   /*************************** Probing LP Solving ***************************/
1061 	   lpstatus = SCIP_LPSOLSTAT_ERROR;
1062 	   lperror = FALSE;
1063 	   /* solve lp only if the problem is still feasible */
1064 	   if( solvelp )
1065 	   {
1066 	      char strbuf[SCIP_MAXSTRLEN];
1067 	      int ncols;
1068 	
1069 	      /* print message if relatively large LP is solved from scratch, since this could lead to a longer period during
1070 	       * which the user sees no output; more detailed probing stats only in debug mode */
1071 	      ncols = SCIPgetNLPCols(scip);
1072 	      if( !SCIPisLPSolBasic(scip) && ncols > 1000 )
1073 	      {
1074 	         int nunfixedcols = SCIPgetNUnfixedLPCols(scip);
1075 	
1076 	         if( nunfixedcols > 0.5 * ncols )
1077 	         {
1078 	            SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
1079 	               "Heuristic " HEUR_NAME " solving LP from scratch with %.1f %% unfixed columns (%d of %d) ...\n",
1080 	               100.0 * (nunfixedcols / (SCIP_Real)ncols), nunfixedcols, ncols);
1081 	         }
1082 	      }
1083 	      SCIPdebugMsg(scip, "Heuristic " HEUR_NAME " probing LP: %s\n",
1084 	         SCIPsnprintfProbingStats(scip, strbuf, SCIP_MAXSTRLEN));
1085 	
1086 	      /* solve LP; errors in the LP solver should not kill the overall solving process, if the LP is just needed for a
1087 	       * heuristic.  hence in optimized mode, the return code is caught and a warning is printed, only in debug mode,
1088 	       * SCIP will stop.
1089 	       */
1090 	      SCIPdebugMsg(scip, "starting solving vbound-lp at time %g\n", SCIPgetSolvingTime(scip));
1091 	#ifdef NDEBUG
1092 	      {
1093 	         SCIP_Bool retstat;
1094 	         retstat = SCIPsolveProbingLP(scip, -1, &lperror, NULL);
1095 	         if( retstat != SCIP_OKAY )
1096 	         {
1097 	            SCIPwarningMessage(scip, "Error while solving LP in vbound heuristic; LP solve terminated with code <%d>\n",
1098 	               retstat);
1099 	         }
1100 	      }
1101 	#else
1102 	      SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, NULL) );
1103 	#endif
1104 	      SCIPdebugMsg(scip, "ending solving vbound-lp at time %g\n", SCIPgetSolvingTime(scip));
1105 	
1106 	      lpstatus = SCIPgetLPSolstat(scip);
1107 	
1108 	      SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
1109 	      SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, lpstatus);
1110 	   }
1111 	
1112 	   /* check if this is a feasible solution */
1113 	   if( lpstatus == SCIP_LPSOLSTAT_OPTIMAL && !lperror )
1114 	   {
1115 	      SCIP_Bool stored;
1116 	      SCIP_Bool success;
1117 	      SCIP_SOL* sol;
1118 	
1119 	      lowerbound = SCIPgetLPObjval(scip);
1120 	
1121 	      /* copy the current LP solution to the working solution */
1122 	      SCIP_CALL( SCIPcreateSol(scip, &sol, heur) );
1123 	      SCIP_CALL( SCIPlinkLPSol(scip, sol) );
1124 	
1125 	      SCIP_CALL( SCIProundSol(scip, sol, &success) );
1126 	
1127 	      if( success )
1128 	      {
1129 	         SCIPdebugMsg(scip, "vbound heuristic found roundable primal solution: obj=%g\n",
1130 	            SCIPgetSolOrigObj(scip, sol));
1131 	
1132 	         /* check solution for feasibility, and add it to solution store if possible.
1133 	          * Neither integrality nor feasibility of LP rows have to be checked, because they
1134 	          * are guaranteed by the heuristic at this stage.
1135 	          */
1136 	#ifdef SCIP_DEBUG
1137 	         SCIP_CALL( SCIPtrySol(scip, sol, TRUE, TRUE, TRUE, TRUE, TRUE, &stored) );
1138 	#else
1139 	         SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, TRUE, FALSE, FALSE, &stored) );
1140 	#endif
1141 	
1142 	#ifdef SCIP_DEBUG
1143 	         SCIP_CALL( SCIPcheckSol(scip, sol, FALSE, FALSE, TRUE, TRUE, TRUE, &wasfeas) );
1144 	         assert(wasfeas);
1145 	         SCIPdebugMsg(scip, "found feasible solution by LP rounding: %16.9g\n", SCIPgetSolOrigObj(scip, sol));
1146 	#endif
1147 	
1148 	         if( stored )
1149 	            *result = SCIP_FOUNDSOL;
1150 	
1151 	         SCIP_CALL( SCIPfreeSol(scip, &sol) );
1152 	
1153 	         /* we found a solution, so we are done */
1154 	         goto TERMINATE;
1155 	      }
1156 	
1157 	      SCIP_CALL( SCIPfreeSol(scip, &sol) );
1158 	   }
1159 	   /*************************** END Probing LP Solving ***************************/
1160 	
1161 	   /*************************** Start Subscip Solving ***************************/
1162 	   /* if no solution has been found --> fix all other variables by subscip if necessary */
1163 	   if( !lperror && lpstatus != SCIP_LPSOLSTAT_INFEASIBLE && lpstatus != SCIP_LPSOLSTAT_OBJLIMIT )
1164 	   {
1165 	      SCIP* subscip;
1166 	      SCIP_RETCODE retcode;
1167 	      SCIP_Bool valid;
1168 	
1169 	      /* check whether there is enough time and memory left */
1170 	      SCIP_CALL( SCIPcheckCopyLimits(scip, &valid) );
1171 	
1172 	      if( !valid )
1173 	         goto TERMINATE;
1174 	
1175 	      /* create subproblem */
1176 	      SCIP_CALL( SCIPcreate(&subscip) );
1177 	
1178 	      retcode = setupAndSolveSubscip(scip, subscip, heur, vars, nvars, nstallnodes, lowerbound,
1179 	         &nprevars, &wasfeas, result);
1180 	
1181 	      SCIP_CALL( SCIPfree(&subscip) );
1182 	
1183 	      SCIP_CALL( retcode );
1184 	   }
1185 	
1186 	   /*************************** End Subscip Solving ***************************/
1187 	
1188 	 TERMINATE:
1189 	#ifdef SCIP_STATISTIC
1190 	   SCIP_CALL( SCIPstopClock(scip, clock) );
1191 	   SCIPstatisticMessage("vbound: tighten=%u obj=%d nvars=%d presolnvars=%d ratio=%.2f infeas=%u found=%d time=%.4f\n",
1192 	      tighten, obj, nvars, nprevars, (nvars - nprevars) / (SCIP_Real)nvars, cutoff,
1193 	      wasfeas ? 1 : 0, SCIPclockGetTime(clock) );
1194 	#endif
1195 	
1196 	   SCIPstatistic( SCIP_CALL( SCIPfreeClock(scip, &clock) ) );
1197 	
1198 	   /* exit probing mode */
1199 	   if( SCIPinProbing(scip) )
1200 	   {
1201 	      SCIP_CALL( SCIPendProbing(scip) );
1202 	   }
1203 	
1204 	   return SCIP_OKAY; /*lint !e438*/
1205 	}
1206 	
1207 	
1208 	/*
1209 	 * Callback methods of primal heuristic
1210 	 */
1211 	
1212 	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
1213 	static
1214 	SCIP_DECL_HEURCOPY(heurCopyVbounds)
1215 	{  /*lint --e{715}*/
1216 	   assert(scip != NULL);
1217 	   assert(heur != NULL);
1218 	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1219 	
1220 	   /* call inclusion method of heuristic */
1221 	   SCIP_CALL( SCIPincludeHeurVbounds(scip) );
1222 	
1223 	   return SCIP_OKAY;
1224 	}
1225 	
1226 	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
1227 	static
1228 	SCIP_DECL_HEURFREE(heurFreeVbounds)
1229 	{  /*lint --e{715}*/
1230 	   SCIP_HEURDATA* heurdata;
1231 	
1232 	   /* free heuristic data */
1233 	   heurdata = SCIPheurGetData(heur);
1234 	
1235 	   SCIPfreeBlockMemory(scip, &heurdata);
1236 	   SCIPheurSetData(heur, NULL);
1237 	
1238 	   return SCIP_OKAY;
1239 	}
1240 	
1241 	
1242 	/** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
1243 	static
1244 	SCIP_DECL_HEUREXITSOL(heurExitsolVbounds)
1245 	{  /*lint --e{715}*/
1246 	   SCIP_HEURDATA* heurdata;
1247 	   int v;
1248 	
1249 	   heurdata = SCIPheurGetData(heur);
1250 	   assert(heurdata != NULL);
1251 	
1252 	   /* release all variables */
1253 	   for( v = 0; v < heurdata->nvbvars; ++v )
1254 	   {
1255 	      SCIP_CALL( SCIPreleaseVar(scip, &heurdata->vbvars[v]) );
1256 	   }
1257 	
1258 	   /* free varbounds array */
1259 	   SCIPfreeBlockMemoryArrayNull(scip, &heurdata->vbbounds, heurdata->nvbvars);
1260 	   SCIPfreeBlockMemoryArrayNull(scip, &heurdata->vbvars, heurdata->nvbvars);
1261 	
1262 	   /* reset heuristic data structure */
1263 	   heurdataReset(heurdata);
1264 	
1265 	   return SCIP_OKAY;
1266 	}
1267 	
1268 	/** execution method of primal heuristic */
1269 	static
1270 	SCIP_DECL_HEUREXEC(heurExecVbounds)
1271 	{  /*lint --e{715}*/
1272 	   SCIP_HEURDATA* heurdata;
1273 	   SCIP_Bool skipobj1;
1274 	   SCIP_Bool skipobj2;
1275 	#ifdef NOCONFLICT
1276 	   SCIP_Bool enabledconflicts;
1277 	#endif
1278 	
1279 	   assert( heur != NULL );
1280 	   assert( scip != NULL );
1281 	   assert( result != NULL );
1282 	
1283 	   *result = SCIP_DIDNOTRUN;
1284 	
1285 	   if( SCIPgetNPseudoBranchCands(scip) == 0 )
1286 	      return SCIP_OKAY;
1287 	
1288 	   heurdata = SCIPheurGetData(heur);
1289 	   assert(heurdata != NULL);
1290 	
1291 	   if( !heurdata->initialized )
1292 	   {
1293 	      SCIP_CALL( initializeCandsLists(scip, heurdata) );
1294 	   }
1295 	
1296 	   if( !heurdata->applicable )
1297 	      return SCIP_OKAY;
1298 	
1299 	#ifdef NOCONFLICT
1300 	   /* disable conflict analysis */
1301 	   SCIP_CALL( SCIPgetBoolParam(scip, "conflict/enable", &enabledconflicts) );
1302 	
1303 	   if( !SCIPisParamFixed(scip, "conflict/enable") )
1304 	   {
1305 	      SCIP_CALL( SCIPsetBoolParam(scip, "conflict/enable", FALSE) );
1306 	   }
1307 	#endif
1308 	
1309 	   /* try variable bounds */
1310 	   skipobj1 = FALSE;
1311 	   skipobj2 = FALSE;
1312 	   if( ((unsigned)heurdata->feasvariant & VBOUNDVARIANT_NOOBJ) != 0 )
1313 	   {
1314 	      SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, FALSE, 0,
1315 	            &skipobj1, &skipobj2, result) );
1316 	   }
1317 	   if( !skipobj1 && ((unsigned) heurdata->feasvariant & VBOUNDVARIANT_BESTBOUND) != 0)
1318 	   {
1319 	      SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, FALSE, 1, NULL, NULL, result) );
1320 	   }
1321 	   if( !skipobj2 && ((unsigned) heurdata->feasvariant & VBOUNDVARIANT_WORSTBOUND) != 0)
1322 	   {
1323 	      SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, FALSE, 2, NULL, NULL, result) );
1324 	   }
1325 	
1326 	   skipobj1 = FALSE;
1327 	   skipobj2 = FALSE;
1328 	   if( ((unsigned) heurdata->tightenvariant & VBOUNDVARIANT_NOOBJ) != 0 )
1329 	   {
1330 	      SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, TRUE, 0,
1331 	            &skipobj1, &skipobj2, result) );
1332 	   }
1333 	   if( !skipobj1 && ((unsigned) heurdata->tightenvariant & VBOUNDVARIANT_BESTBOUND) != 0)
1334 	   {
1335 	      SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, TRUE, 1, NULL, NULL, result) );
1336 	   }
1337 	   if( !skipobj2 && ((unsigned) heurdata->tightenvariant & VBOUNDVARIANT_WORSTBOUND) != 0)
1338 	   {
1339 	      SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, TRUE, 2, NULL, NULL, result) );
1340 	   }
1341 	
1342 	#ifdef NOCONFLICT
1343 	   /* reset the conflict analysis */
1344 	   if( !SCIPisParamFixed(scip, "conflict/enable") )
1345 	   {
1346 	      SCIP_CALL( SCIPsetBoolParam(scip, "conflict/enable", enabledconflicts) );
1347 	   }
1348 	#endif
1349 	
1350 	   return SCIP_OKAY;
1351 	}
1352 	
1353 	/*
1354 	 * primal heuristic specific interface methods
1355 	 */
1356 	
1357 	/** creates the vbounds primal heuristic and includes it in SCIP */
1358 	SCIP_RETCODE SCIPincludeHeurVbounds(
1359 	   SCIP*                 scip                /**< SCIP data structure */
1360 	   )
1361 	{
1362 	   SCIP_HEURDATA* heurdata;
1363 	   SCIP_HEUR* heur;
1364 	
1365 	   /* create vbounds primal heuristic data */
1366 	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
1367 	   heurdataReset(heurdata);
1368 	
1369 	   /* include primal heuristic */
1370 	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1371 	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
1372 	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecVbounds, heurdata) );
1373 	
1374 	   assert(heur != NULL);
1375 	
1376 	   /* set non-NULL pointers to callback methods */
1377 	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyVbounds) );
1378 	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeVbounds) );
1379 	   SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolVbounds) );
1380 	
1381 	   /* add variable bounds primal heuristic parameters */
1382 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minintfixingrate",
1383 	         "minimum percentage of integer variables that have to be fixed",
1384 	         &heurdata->minintfixingrate, FALSE, DEFAULT_MININTFIXINGRATE, 0.0, 1.0, NULL, NULL) );
1385 	
1386 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minmipfixingrate",
1387 	         "minimum percentage of variables that have to be fixed within sub-SCIP (integer and continuous)",
1388 	         &heurdata->minmipfixingrate, FALSE, DEFAULT_MINMIPFIXINGRATE, 0.0, 1.0, NULL, NULL) );
1389 	
1390 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
1391 	         "maximum number of nodes to regard in the subproblem",
1392 	         &heurdata->maxnodes,  TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1393 	
1394 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
1395 	         "number of nodes added to the contingent of the total nodes",
1396 	         &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1397 	
1398 	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
1399 	         "minimum number of nodes required to start the subproblem",
1400 	         &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1401 	
1402 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
1403 	         "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1404 	         &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
1405 	
1406 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
1407 	         "factor by which " HEUR_NAME " heuristic should at least improve the incumbent",
1408 	         &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
1409 	
1410 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxproprounds",
1411 	         "maximum number of propagation rounds during probing (-1 infinity)",
1412 	         &heurdata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -1, INT_MAX/4, NULL, NULL) );
1413 	
1414 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
1415 	         "should all active cuts from cutpool be copied to constraints in subproblem?",
1416 	         &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
1417 	
1418 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselockfixings",
1419 	         "should more variables be fixed based on variable locks if the fixing rate was not reached?",
1420 	         &heurdata->uselockfixings, TRUE, DEFAULT_USELOCKFIXINGS, NULL, NULL) );
1421 	
1422 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxbacktracks",
1423 	         "maximum number of backtracks during the fixing process",
1424 	         &heurdata->maxbacktracks, TRUE, DEFAULT_MAXBACKTRACKS, -1, INT_MAX/4, NULL, NULL) );
1425 	
1426 	      SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/feasvariant",
1427 	         "which variants of the vbounds heuristic that try to stay feasible should be called? (0: off, 1: w/o looking at obj, 2: only fix to best bound, 4: only fix to worst bound",
1428 	            &heurdata->feasvariant, TRUE, (int) DEFAULT_FEASVARIANT, 0, 7, NULL, NULL) );
1429 	
1430 	      SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/tightenvariant",
1431 	         "which tightening variants of the vbounds heuristic should be called? (0: off, 1: w/o looking at obj, 2: only fix to best bound, 4: only fix to worst bound",
1432 	            &heurdata->tightenvariant, TRUE, (int) DEFAULT_TIGHTENVARIANT, 0, 7, NULL, NULL) );
1433 	
1434 	   return SCIP_OKAY;
1435 	}
1436 	
1437 	/**@} */
1438