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_gins.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  LNS heuristic that tries to delimit the search region to a neighborhood in the constraint graph
28   	 * @author Gregor Hendel
29   	 *
30   	 * Graph Induced Neighborhood Search (GINS) is a Large Neighborhood Search Heuristic that attempts to improve
31   	 * an incumbent solution by fixing a suitable percentage of integer variables to the incumbent and
32   	 * solving the resulting, smaller and presumably easier sub-MIP.
33   	 *
34   	 * Its search neighborhoods are based on distances in a bipartite graph \f$G\f$ with the variables and constraints as nodes
35   	 * and an edge between a variable and a constraint, if the variable is part of the constraint.
36   	 * Given an integer \f$k\f$, the \f$k\f$-neighborhood of a variable \f$v\f$ in \f$G\f$ is the set of variables, whose nodes
37   	 * are connected to \f$v\f$ by a path not longer than \f$2 \cdot k\f$. Intuitively, a judiciously chosen neighborhood size
38   	 * allows to consider a local portion of the overall problem.
39   	 *
40   	 * An initial variable selection is made by randomly sampling different neighborhoods across the whole main problem.
41   	 * The neighborhood that offers the largest potential for improvement is selected to become the local search neighborhood,
42   	 * while all variables outside the neighborhood are fixed to their incumbent solution values.
43   	 *
44   	 * GINS also supports a rolling horizon approach, during which several local neighborhoods are considered
45   	 * with increasing distance to the variable selected for the initial sub-problem. The rolling horizon approach ends
46   	 * if no improvement could be found or a sufficient part of the problem component variables has been part of
47   	 * at least one neighborhood.
48   	 */
49   	
50   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
51   	
52   	#include "blockmemshell/memory.h"
53   	#include "scip/heur_gins.h"
54   	#include "scip/heuristics.h"
55   	#include "scip/pub_dcmp.h"
56   	#include "scip/pub_heur.h"
57   	#include "scip/pub_message.h"
58   	#include "scip/pub_misc.h"
59   	#include "scip/pub_misc_sort.h"
60   	#include "scip/pub_sol.h"
61   	#include "scip/pub_var.h"
62   	#include "scip/scip_branch.h"
63   	#include "scip/scip_cons.h"
64   	#include "scip/scip_copy.h"
65   	#include "scip/scip_dcmp.h"
66   	#include "scip/scip_general.h"
67   	#include "scip/scip_heur.h"
68   	#include "scip/scip_mem.h"
69   	#include "scip/scip_message.h"
70   	#include "scip/scip_nodesel.h"
71   	#include "scip/scip_numerics.h"
72   	#include "scip/scip_param.h"
73   	#include "scip/scip_prob.h"
74   	#include "scip/scip_randnumgen.h"
75   	#include "scip/scip_sol.h"
76   	#include "scip/scip_solve.h"
77   	#include "scip/scip_solvingstats.h"
78   	#include "scip/scip_timing.h"
79   	#include <string.h>
80   	
81   	#define HEUR_NAME             "gins"
82   	#define HEUR_DESC             "gins works on k-neighborhood in a variable-constraint graph"
83   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_LNS
84   	#define HEUR_PRIORITY         -1103000
85   	#define HEUR_FREQ             20
86   	#define HEUR_FREQOFS          8
87   	#define HEUR_MAXDEPTH         -1
88   	#define HEUR_TIMING           SCIP_HEURTIMING_AFTERNODE
89   	#define HEUR_USESSUBSCIP      TRUE  /**< does the heuristic use a secondary SCIP instance? */
90   	
91   	#define DEFAULT_NODESOFS      500            /**< number of nodes added to the contingent of the total nodes */
92   	#define DEFAULT_MAXNODES      5000           /**< maximum number of nodes to regard in the subproblem */
93   	#define DEFAULT_MINIMPROVE    0.01           /**< factor by which Gins should at least improve the incumbent */
94   	#define DEFAULT_MINNODES      50             /**< minimum number of nodes to regard in the subproblem */
95   	#define DEFAULT_MINFIXINGRATE 0.66           /**< minimum percentage of integer variables that have to be fixed */
96   	#define DEFAULT_NODESQUOT     0.15           /**< subproblem nodes in relation to nodes of the original problem */
97   	#define DEFAULT_NWAITINGNODES 100            /**< number of nodes without incumbent change that heuristic should wait */
98   	#define DEFAULT_USELPROWS     FALSE          /**< should subproblem be created out of the rows in the LP rows,
99   	                                              *   otherwise, the copy constructors of the constraints handlers are used */
100  	#define DEFAULT_COPYCUTS      TRUE           /**< if DEFAULT_USELPROWS is FALSE, then should all active cuts from the
101  	                                              *   cutpool of the original scip be copied to constraints of the subscip */
102  	#define DEFAULT_BESTSOLLIMIT    3            /**< limit on number of improving incumbent solutions in sub-CIP */
103  	#define DEFAULT_FIXCONTVARS FALSE            /**< should continuous variables outside the neighborhoods get fixed? */
104  	#define DEFAULT_POTENTIAL      'r'           /**< the reference point to compute the neighborhood potential: (r)oot, (l)ocal lp, or (p)seudo solution */
105  	#define DEFAULT_MAXDISTANCE     3            /**< maximum distance to selected variable to enter the subproblem, or -1 to
106  	                                              *   select the distance that best approximates the minimum fixing rate from below */
107  	#define DEFAULT_RANDSEED       71
108  	#define DEFAULT_RELAXDENSECONSS FALSE        /**< should dense constraints (at least as dense as 1 - minfixingrate) be
109  	                                              *   ignored by connectivity graph? */
110  	#define DEFAULT_USEROLLINGHORIZON TRUE       /**< should the heuristic solve a sequence of sub-MIP's around the first selected variable */
111  	#define DEFAULT_ROLLHORIZONLIMFAC  0.4       /**< limiting percentage for variables already used in sub-SCIPs to terminate rolling
112  	                                              *   horizon approach */
113  	#define DEFAULT_USEDECOMP    TRUE            /**< should user decompositions be considered, if available? */
114  	#define DEFAULT_USEDECOMPROLLHORIZON FALSE   /**< should user decompositions be considered for initial selection in rolling horizon, if available? */
115  	#define DEFAULT_USESELFALLBACK  TRUE         /**< should random initial variable selection be used if decomposition was not successful? */
116  	#define DEFAULT_OVERLAP          0.0         /**< overlap of blocks between runs - 0.0: no overlap, 1.0: shift by only 1 block */
117  	#define DEFAULT_CONSECUTIVEBLOCKS TRUE       /**< should blocks be treated consecutively (sorted by ascending label?) */
118  	
119  	
120  	/*
121  	 * Data structures
122  	 */
123  	
124  	/** rolling horizon data structure to control multiple LNS heuristic runs away from an original source variable */
125  	struct RollingHorizon
126  	{
127  	   SCIP_VGRAPH*          variablegraph;      /**< variable graph data structure for breadth-first-search neighborhoods */
128  	   int*                  distances;          /**< distances of the heuristic rolling horizon from the original source
129  	                                              *   variable indexed by probindex */
130  	   SCIP_Bool*            used;               /**< array that represents for every variable whether it has been used
131  	                                              *   in a neighborhood indexed by probindex */
132  	   int                   lastmaxdistance;    /**< the last distance k for a neighborhood, will be decreased
133  	                                              *   during the rolling horizon if the selected neighborhood is too large */
134  	   int                   lastdistance;       /**< last distance from originally selected variable in iteration zero */
135  	   int                   distancessize;      /**< size of the distances and used arrays */
136  	   int                   niterations;        /**< counter for the number of rolling horizon iterations */
137  	   int                   nused;              /**< counts the number variables that have been part of any neighborhood
138  	                                              *   during the rolling horizon approach */
139  	   int                   nnonreachable;      /**< counter for the number of nonreachable variables (distance -1) from
140  	                                              *   the initially selected variable */
141  	};
142  	typedef struct RollingHorizon ROLLINGHORIZON;
143  	
144  	/** data structure to enable GINS to solve multiple decompositions in a sequential process */
145  	struct DecompHorizon
146  	{
147  	   SCIP_DECOMP*          decomp;             /**< decomposition data structure used for this horizon */
148  	   SCIP_VAR**            vars;               /**< variables sorted by block indices */
149  	   SCIP_SOL**            lastsolblock;       /**< last solution for which block was part of the sub-SCIP */
150  	   SCIP_Real*            potential;          /**< potential of each block */
151  	   int*                  blocklabels;        /**< sorted block labels of all variable blocks that satisfy the requirements */
152  	   int*                  varblockend;        /**< block end indices in sorted variables array (position of first variable of next block) */
153  	   int*                  ndiscretevars;      /**< number of binary and integer variables in each block */
154  	   int*                  blockindices;       /**< block indices (from 0 to nblocks) with respect to sorting of blocks */
155  	   int*                  nvars;              /**< number of variables (including continuous and implicit integers) in each block */
156  	   SCIP_Bool*            suitable;           /**< TRUE if a block is suitable */
157  	   int                   nsuitableblocks;    /**< the total number of suitable blocks */
158  	   int                   lastblockpos;       /**< last remembered block position (in block indices, i.e., regarding sorting) */
159  	   int                   nblocks;            /**< the number of available variable blocks, only available after initialization */
160  	   int                   memsize;            /**< storage size of the used arrays */
161  	   int                   varsmemsize;        /**< storage size of the vars array */
162  	   int                   overlapinterval[2]; /**< block positions of last interval forbidden by overlap */
163  	   SCIP_Bool             init;               /**< has the decomposition horizon been initialized? */
164  	};
165  	typedef struct DecompHorizon DECOMPHORIZON;
166  	
167  	/** data structure to hold elements that are taboo */
168  	struct TabooList
169  	{
170  	   int*                  taboolabels;        /**< labels or indices that are currently taboo */
171  	   int*                  sortedlabels;       /**< array of labels in sorted order for quicker finding */
172  	   int                   memsize;            /**< storage capacity of taboolabels */
173  	   int                   ntaboolabels;       /**< number of elements contained in taboo list */
174  	   SCIP_Bool             needssorting;       /**< has an element been added since the last sort? */
175  	};
176  	typedef struct TabooList TABOOLIST;
177  	
178  	/** primal heuristic data */
179  	struct SCIP_HeurData
180  	{
181  	   int                   nodesofs;           /**< number of nodes added to the contingent of the total nodes */
182  	   int                   maxnodes;           /**< maximum number of nodes to regard in the subproblem */
183  	   int                   minnodes;           /**< minimum number of nodes to regard in the subproblem */
184  	   SCIP_Real             minfixingrate;      /**< minimum percentage of integer variables that have to be fixed */
185  	   SCIP_Real             overlap;            /**< overlap of blocks between runs - 0.0: no overlap, 1.0: shift by only 1 block */
186  	   int                   nwaitingnodes;      /**< number of nodes without incumbent change that heuristic should wait */
187  	   SCIP_Real             minimprove;         /**< factor by which Gins should at least improve the incumbent */
188  	   SCIP_Longint          usednodes;          /**< nodes already used by Gins in earlier calls */
189  	   SCIP_Real             nodesquot;          /**< subproblem nodes in relation to nodes of the original problem */
190  	   SCIP_Real             rollhorizonlimfac;  /**< limiting percentage for variables already used in sub-SCIPs to terminate
191  	                                              *   rolling horizon approach */
192  	   DECOMPHORIZON*        decomphorizon;      /**< decomposition horizon data structure */
193  	   SCIP_RANDNUMGEN*      randnumgen;         /**< random number generator                              */
194  	   SCIP_SOL*             lastinitsol;        /**< last solution used for selection of initial variable */
195  	   TABOOLIST*            taboolist;          /**< taboo list of block labels that should not be used */
196  	   SCIP_Bool             uselprows;          /**< should subproblem be created out of the rows in the LP rows? */
197  	   SCIP_Bool             copycuts;           /**< if uselprows == FALSE, should all active cuts from cutpool be copied
198  	                                              *   to constraints in subproblem? */
199  	   SCIP_Bool             allblocksunsuitable; /**< remember if all blocks are unsuitable w.r.t. the current incumbent solution  */
200  	   SCIP_Bool             fixcontvars;        /**< should continuous variables outside the neighborhoods get fixed? */
201  	   int                   bestsollimit;       /**< limit on number of improving incumbent solutions in sub-CIP */
202  	   int                   maxdistance;        /**< maximum distance to selected variable to enter the subproblem, or -1 to
203  	                                              *   select the distance that best approximates the minimum fixing rate from below */
204  	   int                   sumneighborhoodvars;/**< neighborhood variables sum over all seen neighborhoods */
205  	   int                   sumdiscneighborhoodvars; /**< neighborhood discrete variables sum over all seen neighboorhoods */
206  	   int                   nneighborhoods;     /**< number of calculated neighborhoods */
207  	   int                   nsubmips;           /**< counter for the number of sub-MIP's that can be higher than the number of
208  	                                              *   calls of this heuristic */
209  	   SCIP_Bool             consecutiveblocks;  /**< should blocks be treated consecutively (sorted by ascending label?) */
210  	   SCIP_Bool             relaxdenseconss;    /**< should dense constraints (at least as dense as 1 - minfixingrate) be
211  	                                              *   ignored by connectivity graph? */
212  	   SCIP_Bool             userollinghorizon;  /**< should the heuristic solve a sequence of sub-MIP's around the first
213  	                                              *   selected variable */
214  	   SCIP_Bool             usedecomp;          /**< should user decompositions be considered, if available? */
215  	   SCIP_Bool             usedecomprollhorizon;/**< should user decompositions be considered for initial selection in rolling horizon, if available? */
216  	   SCIP_Bool             useselfallback;     /**< should random initial variable selection be used if decomposition was not successful? */
217  	   char                  potential;          /**< the reference point to compute the neighborhood potential: (r)oot or
218  	                                              *   (p)seudo solution */
219  	   int                   maxseendistance;    /**< maximum of all distances between two variables */
220  	   int                   nrelaxedconstraints; /**< number of constraints that were relaxed */
221  	   int                   nfailures;           /**< counter for the number of unsuccessful runs of this heuristic */
222  	   SCIP_Longint          nextnodenumber;      /**< the next node number at which the heuristic should be called again */
223  	   SCIP_Longint          targetnodes;         /**< number of target nodes, slightly increasing if (stall) node limit is hit */
224  	};
225  	
226  	/** represents limits for the sub-SCIP solving process */
227  	struct SolveLimits
228  	{
229  	   SCIP_Longint          nodelimit;          /**< maximum number of solving nodes for the sub-SCIP */
230  	   SCIP_Longint          stallnodelimit;     /**< limit on the number of stall nodes (nodes after last incumbent) */
231  	};
232  	typedef struct SolveLimits SOLVELIMITS;
233  	
234  	/*
235  	 * Local methods
236  	 */
237  	
238  	/** check if enough fixings have been found */
239  	static
240  	SCIP_Bool checkFixingrate(
241  	   SCIP*                 scip,               /**< SCIP data structure */
242  	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
243  	   int                   nfixings            /**< actual number of fixings */
244  	   )
245  	{
246  	   int fixthreshold;
247  	   int nvars = SCIPgetNVars(scip);
248  	   int nbinvars = SCIPgetNBinVars(scip);
249  	   int nintvars = SCIPgetNIntVars(scip);
250  	   fixthreshold = (int)(heurdata->minfixingrate * (heurdata->fixcontvars ? nvars : (nbinvars + nintvars)));
251  	
252  	   /* compare actual number of fixings to limit; if we fixed not enough variables we terminate here;
253  	    * we also terminate if no discrete variables are left
254  	    */
255  	   if( nfixings < fixthreshold )
256  	   {
257  	      SCIPdebugMsg(scip, "Fixed %d < %d variables in gins heuristic, stopping\n", nfixings, fixthreshold);
258  	
259  	      return FALSE;
260  	   }
261  	   else
262  	   {
263  	      SCIPdebugMsg(scip, "Fixed enough (%d >= %d) variables in gins heuristic\n", nfixings, fixthreshold);
264  	
265  	      return TRUE;
266  	   }
267  	}
268  	
269  	/** get the potential of a subset of variables (distance to a reference point such as the pseudo-solution or root
270  	 * LP solution)
271  	 */
272  	static
273  	SCIP_Real getPotential(
274  	   SCIP*                 scip,               /**< SCIP data structure */
275  	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
276  	   SCIP_SOL*             sol,                /**< solution */
277  	   SCIP_VAR**            vars,               /**< variable array */
278  	   int                   nvars               /**< length of variable array */
279  	   )
280  	{
281  	   SCIP_Real potential;
282  	   int i;
283  	
284  	   assert(scip != NULL);
285  	   assert(vars != NULL);
286  	   assert(sol != NULL);
287  	
288  	   if( nvars == 0 )
289  	      return 0.0;
290  	
291  	   potential = 0.0;
292  	
293  	   for( i = 0; i < nvars; ++i )
294  	   {
295  	      SCIP_Real objdelta;
296  	      SCIP_VAR* var;
297  	      SCIP_Real referencepoint;
298  	      SCIP_Real varobj;
299  	
300  	      var = vars[i];
301  	      assert(var != NULL);
302  	      varobj = SCIPvarGetObj(var);
303  	
304  	      if( SCIPisZero(scip, varobj) )
305  	         continue;
306  	
307  	      /* determine the reference point for potential computation */
308  	      switch( heurdata->potential )
309  	      {
310  	         /* use difference to pseudo solution using the bound in the objective direction */
311  	         case 'p':
312  	            referencepoint = varobj > 0.0 ? SCIPvarGetLbGlobal(var) : SCIPvarGetUbGlobal(var);
313  	            break;
314  	
315  	         /* use root LP solution difference */
316  	         case 'r':
317  	            referencepoint = SCIPvarGetRootSol(var);
318  	            break;
319  	
320  	         /* use local LP solution */
321  	         case 'l':
322  	            referencepoint = SCIPgetSolVal(scip, NULL, var);
323  	            break;
324  	         default:
325  	            SCIPerrorMessage("Unknown potential computation %c specified\n", heurdata->potential);
326  	            referencepoint = 0.0;
327  	            break;
328  	      }
329  	
330  	      if( SCIPisInfinity(scip, REALABS(referencepoint)) )
331  	         continue;
332  	
333  	      /* calculate the delta to the variables best bound */
334  	      objdelta = (SCIPgetSolVal(scip, sol, var) - referencepoint) * varobj;
335  	      potential += objdelta;
336  	   }
337  	
338  	   return potential;
339  	}
340  	
341  	/** (re)set overlap interval of decomposition horizon */
342  	static
343  	void decompHorizonSetOverlapInterval(
344  	   DECOMPHORIZON*        decomphorizon,      /**< decomposition horizon data structure */
345  	   int                   leftborder,         /**< left interval border */
346  	   int                   rightborder         /**< right interval border */
347  	   )
348  	{
349  	   assert(decomphorizon != NULL);
350  	   assert(leftborder <= rightborder);
351  	
352  	   decomphorizon->overlapinterval[0] = leftborder;
353  	   decomphorizon->overlapinterval[1] = rightborder;
354  	}
355  	
356  	/** create a decomp horizon data structure */
357  	static
358  	SCIP_RETCODE decompHorizonCreate(
359  	   SCIP*                 scip,               /**< SCIP data structure */
360  	   DECOMPHORIZON**       decomphorizon,      /**< pointer to store decomposition horizon */
361  	   SCIP_DECOMP*          decomp              /**< decomposition in transformed space */
362  	   )
363  	{
364  	   DECOMPHORIZON* decomphorizonptr;
365  	   int nblocks;
366  	   int memsize;
367  	
368  	   assert(scip != NULL);
369  	   assert(decomphorizon != NULL);
370  	   assert(decomp != NULL);
371  	
372  	   nblocks = SCIPdecompGetNBlocks(decomp);
373  	
374  	   assert(nblocks >= 1);
375  	
376  	   /* account an additional slot for the border */
377  	   SCIP_CALL( SCIPallocBlockMemory(scip, decomphorizon) );
378  	   decomphorizonptr = *decomphorizon;
379  	   decomphorizonptr->decomp = decomp;
380  	   decomphorizonptr->memsize = memsize = nblocks + 1;
381  	
382  	   /* allocate storage for block related information */
383  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomphorizonptr->blocklabels, memsize) );
384  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomphorizonptr->varblockend, memsize) );
385  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomphorizonptr->suitable, memsize) );
386  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomphorizonptr->ndiscretevars, memsize) );
387  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomphorizonptr->nvars, memsize) );
388  	   SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &decomphorizonptr->lastsolblock, memsize) );
389  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomphorizonptr->potential, memsize) );
390  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomphorizonptr->blockindices, memsize) );
391  	
392  	   decomphorizonptr->lastblockpos = INT_MIN; /* cannot use -1 because this is defined for linking variables */
393  	
394  	   /* initialize data later */
395  	   decomphorizonptr->init = FALSE;
396  	   decomphorizonptr->vars = NULL;
397  	   decomphorizonptr->varsmemsize = 0;
398  	
399  	   return SCIP_OKAY;
400  	}
401  	
402  	/** free a decomp horizon data structure */
403  	static
404  	void decompHorizonFree(
405  	   SCIP*                 scip,               /**< SCIP data structure */
406  	   DECOMPHORIZON**       decomphorizon       /**< pointer to decomposition horizon that should be freed */
407  	   )
408  	{
409  	   DECOMPHORIZON* decomphorizonptr;
410  	
411  	   assert(scip != NULL);
412  	   assert(decomphorizon != NULL);
413  	
414  	   /* empty horizon */
415  	   if( *decomphorizon == NULL )
416  	      return;
417  	
418  	   decomphorizonptr = *decomphorizon;
419  	   SCIPfreeBlockMemoryArrayNull(scip, &decomphorizonptr->vars, decomphorizonptr->varsmemsize);
420  	
421  	   SCIPfreeBlockMemoryArray(scip, &decomphorizonptr->blocklabels, decomphorizonptr->memsize);
422  	   SCIPfreeBlockMemoryArray(scip, &decomphorizonptr->varblockend, decomphorizonptr->memsize);
423  	   SCIPfreeBlockMemoryArray(scip, &decomphorizonptr->suitable, decomphorizonptr->memsize);
424  	   SCIPfreeBlockMemoryArray(scip, &decomphorizonptr->ndiscretevars, decomphorizonptr->memsize);
425  	   SCIPfreeBlockMemoryArray(scip, &decomphorizonptr->nvars, decomphorizonptr->memsize);
426  	   SCIPfreeBlockMemoryArray(scip, &decomphorizonptr->lastsolblock, decomphorizonptr->memsize);
427  	   SCIPfreeBlockMemoryArray(scip, &decomphorizonptr->potential, decomphorizonptr->memsize);
428  	   SCIPfreeBlockMemoryArray(scip, &decomphorizonptr->blockindices, decomphorizonptr->memsize);
429  	
430  	   SCIPfreeBlockMemory(scip, decomphorizon);
431  	
432  	   *decomphorizon = NULL;
433  	}
434  	
435  	/** check if another run should be performed within the current decomposition horizon */
436  	static
437  	SCIP_Bool decompHorizonRunAgain(
438  	   SCIP*                 scip,               /**< SCIP data structure */
439  	   DECOMPHORIZON*        decomphorizon       /**< decomposition horizon data structure */
440  	   )
441  	{
442  	   assert(scip != NULL);
443  	   assert(decomphorizon != NULL);
444  	
445  	   assert(decomphorizon->lastblockpos >= 0);
446  	   assert(decomphorizon->lastblockpos < decomphorizon->nblocks);
447  	
448  	   return TRUE;
449  	}
450  	
451  	/** return TRUE if the decomposition horizon has already been initialized, FALSE otherwise */
452  	static
453  	SCIP_Bool decompHorizonIsInitialized(
454  	   DECOMPHORIZON*        decomphorizon       /**< decomposition horizon data structure */
455  	   )
456  	{
457  	   assert(decomphorizon != NULL);
458  	
459  	   return decomphorizon->init;
460  	}
461  	
462  	/** compares two block indices
463  	 *  result:
464  	 *    < 0: ind1 comes before (is better than) ind2
465  	 *    = 0: both indices have the same value
466  	 *    > 0: ind2 comes after (is worse than) ind2
467  	 */
468  	static
469  	SCIP_DECL_SORTINDCOMP(sortIndCompDecompHorizon)
470  	{
471  	   DECOMPHORIZON* decomphorizon = (DECOMPHORIZON*)dataptr;
472  	   SCIP_Real potentialbysize1;
473  	   SCIP_Real potentialbysize2;
474  	
475  	   assert(decomphorizon != NULL);
476  	   assert(ind1 >= 0);
477  	   assert(ind2 >= 0);
478  	   assert(ind1 < decomphorizon->nblocks);
479  	   assert(ind2 < decomphorizon->nblocks);
480  	
481  	   if( ind1 == ind2 )
482  	      return 0;
483  	
484  	   /* linking variables are always sorted up front */
485  	   if( decomphorizon->blocklabels[ind1] == SCIP_DECOMP_LINKVAR )
486  	      return -1;
487  	   else if( decomphorizon->blocklabels[ind2] == SCIP_DECOMP_LINKVAR )
488  	      return 1;
489  	
490  	   /* if one of the blocks is not suitable, return the other block */
491  	   if( ! (decomphorizon->suitable[ind1] && decomphorizon->suitable[ind2]) )
492  	   {
493  	      /* prefer the suitable block; break ties based on block position */
494  	      if( decomphorizon->suitable[ind1] )
495  	         return -1;
496  	      else if( decomphorizon->suitable[ind2] )
497  	         return 1;
498  	      else
499  	         return ind1 - ind2;
500  	   }
501  	
502  	   assert(decomphorizon->suitable[ind1] && decomphorizon->suitable[ind2]);
503  	
504  	   potentialbysize1 = decomphorizon->potential[ind1] / (SCIP_Real)(MAX(decomphorizon->ndiscretevars[ind1], 1.0));
505  	   potentialbysize2 = decomphorizon->potential[ind2] / (SCIP_Real)(MAX(decomphorizon->ndiscretevars[ind2], 1.0));
506  	
507  	   /* prefer the block with higher potential */
508  	   if( potentialbysize1 > potentialbysize2 )
509  	      return -1;
510  	   else if( potentialbysize2 > potentialbysize1 )
511  	      return 1;
512  	
513  	   /* finally, prefer the block with fewer discrete variables */
514  	   return decomphorizon->ndiscretevars[ind1] - decomphorizon->ndiscretevars[ind2];
515  	}
516  	
517  	/** initialize decomposition horizon data structure by setting up data structures and analyzing blocks */
518  	static
519  	SCIP_RETCODE decompHorizonInitialize(
520  	   SCIP*                 scip,               /**< SCIP data structure */
521  	   DECOMPHORIZON*        decomphorizon,      /**< decomposition horizon data structure */
522  	   SCIP_HEURDATA*        heurdata            /**< heuristic data structure */
523  	   )
524  	{
525  	   SCIP_VAR** vars;
526  	   SCIP_VAR** varscopy;
527  	   int* varlabels;
528  	   int nvars;
529  	   int currblockstart;
530  	   int blockpos;
531  	   int nstblblocks;
532  	   int ncontvarsscip;
533  	   int b;
534  	
535  	   SCIP_DECOMP* decomp = decomphorizon->decomp;
536  	
537  	   assert(scip != NULL);
538  	   assert(decomp != NULL);
539  	   assert(! SCIPdecompIsOriginal(decomp));
540  	
541  	   vars = SCIPgetVars(scip);
542  	   nvars = SCIPgetNVars(scip);
543  	   ncontvarsscip = SCIPgetNContVars(scip) + SCIPgetNImplVars(scip);
544  	
545  	   assert(vars != NULL);
546  	
547  	   /* get variable labels from decomposition */
548  	   SCIP_CALL( SCIPallocBufferArray(scip, &varlabels, nvars) );
549  	   SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &varscopy, vars, nvars) );
550  	
551  	   SCIPdecompGetVarsLabels(decomp, varscopy, varlabels, nvars);
552  	
553  	   /*  sort labels and variables */
554  	   SCIPsortIntPtr(varlabels, (void **)varscopy, nvars);
555  	   decomphorizon->vars = varscopy;
556  	   decomphorizon->varsmemsize = nvars;
557  	
558  	   blockpos = 0;
559  	   currblockstart = 0;
560  	   nstblblocks = 0;
561  	   /* loop over blocks, and check if they are suitable or not for the improvement heuristic */
562  	   while( currblockstart < nvars )
563  	   {
564  	      int blocklabel;
565  	      int currblockend;
566  	      int ndiscretevars;
567  	      int nfixedvars;
568  	      SCIP_Bool suitable;
569  	      assert(blockpos < decomphorizon->memsize);
570  	
571  	      blocklabel = varlabels[currblockstart];
572  	      currblockend = currblockstart;
573  	      ndiscretevars = 0;
574  	
575  	      /* determine the block size and the variable types */
576  	      do
577  	      {
578  	         if( SCIPvarGetType(varscopy[currblockend]) < SCIP_VARTYPE_IMPLINT )
579  	            ++ndiscretevars;
580  	
581  	         currblockend++;
582  	      }
583  	      while( currblockend < nvars && varlabels[currblockend] == blocklabel );
584  	
585  	      if( heurdata->fixcontvars )
586  	         nfixedvars = nvars - (currblockend - currblockstart);
587  	      else
588  	         nfixedvars = nvars - ncontvarsscip - ndiscretevars;
589  	
590  	      suitable = nfixedvars > heurdata->minfixingrate * (heurdata->fixcontvars ? nvars : nvars - ncontvarsscip);
591  	
592  	      decomphorizon->suitable[blockpos] = suitable;
593  	      decomphorizon->blocklabels[blockpos] = blocklabel;
594  	      decomphorizon->varblockend[blockpos] = currblockend;
595  	      decomphorizon->nvars[blockpos] = currblockend - currblockstart;
596  	      decomphorizon->ndiscretevars[blockpos] = ndiscretevars;
597  	
598  	      currblockstart = currblockend;
599  	      nstblblocks += (suitable ? 1 : 0);
600  	
601  	      blockpos++;
602  	   }
603  	
604  	   /* not necessarily all blocks have variables; store number of available blocks */
605  	   decomphorizon->nblocks = blockpos;
606  	   decomphorizon->nsuitableblocks = nstblblocks;
607  	
608  	   /* initialize block indices (identical to blockposition initially) */
609  	   for( b = 0; b < decomphorizon->nblocks; ++b )
610  	      decomphorizon->blockindices[b] = b;
611  	
612  	   decompHorizonSetOverlapInterval(decomphorizon, -1, -1);
613  	
614  	   SCIPdebugMsg(scip, "Initialized decomposition horizon for %d blocks (%d suitable)\n",
615  	      decomphorizon->nblocks,
616  	      decomphorizon->nsuitableblocks);
617  	
618  	   SCIPfreeBufferArray(scip, &varlabels);
619  	
620  	   decomphorizon->init = TRUE;
621  	
622  	   return SCIP_OKAY;
623  	}
624  	
625  	/** get the first block position of the consecutive interval with the highest potential */
626  	static
627  	int decompHorizonGetFirstPosBestPotential(
628  	   SCIP*                 scip,               /**< SCIP data structure */
629  	   DECOMPHORIZON*        decomphorizon,      /**< decomposition horizon data structure */
630  	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
631  	   int                   maxblocksize        /**< maximum block size in number of variables */
632  	   )
633  	{
634  	   SCIP_SOL* bestsol;
635  	   SCIP_Real intervalpotential;
636  	   int b;
637  	   int nintervalvars;
638  	   int b1;
639  	   int b2;
640  	   int bestpos;
641  	   SCIP_Real maxpotential;
642  	   SCIP_Bool withlinkvars;
643  	   SCIP_Bool linkvarsexist;
644  	
645  	   assert(scip != NULL);
646  	   assert(decomphorizon != NULL);
647  	   bestsol = SCIPgetBestSol(scip);
648  	   assert(bestsol != NULL);
649  	
650  	   linkvarsexist = decomphorizon->blocklabels[0] == SCIP_DECOMP_LINKVAR;
651  	   bestpos = 0;
652  	
653  	   /* recompute potential of blocks */
654  	   for( b = 0; b < decomphorizon->nblocks; ++b )
655  	   {
656  	      /* unsuitable blocks are left out and should not be contained in an interval */
657  	      if( ! decomphorizon->suitable[b] )
658  	      {
659  	         decomphorizon->potential[b] = SCIP_REAL_MIN;
660  	         continue;
661  	      }
662  	
663  	      /* store the potential of this block */
664  	      decomphorizon->potential[b] = getPotential(scip, heurdata, bestsol,
665  	               &decomphorizon->vars[b == 0 ? 0 : decomphorizon->varblockend[b - 1]], decomphorizon->nvars[b]);
666  	   }
667  	
668  	   /* sort the blocks such that the suitable blocks with the highest potential come first */
669  	   if( ! heurdata->consecutiveblocks )
670  	   {
671  	      SCIPsortInd(decomphorizon->blockindices, sortIndCompDecompHorizon, (void*)decomphorizon, decomphorizon->nblocks);
672  	
673  	      /* best potential block is now at the front (actual block position is retrieved from blockindices */
674  	      SCIPdebugMsg(scip, "New potential based sorting with trailing block: 0 (label %d, potential %.4g)\n",
675  	         decomphorizon->blocklabels[decomphorizon->blockindices[0]], decomphorizon->potential[decomphorizon->blockindices[0]]);
676  	
677  	      return 0;
678  	   }
679  	
680  	   /* compute the consecutive blocks interval with largest potential */
681  	   b1 = linkvarsexist ? 0 : -1;
682  	   b2 = -1;
683  	   nintervalvars = 0;
684  	   intervalpotential = 0.0;
685  	   maxpotential = 0.0;
686  	   withlinkvars = FALSE;
687  	
688  	   while( b1 < decomphorizon->nblocks - 1 )
689  	   {
690  	      int blockindb1;
691  	      int blockindb2;
692  	      ++b1;
693  	      blockindb1 = decomphorizon->blockindices[b1];
694  	
695  	      if( ! decomphorizon->suitable[decomphorizon->blockindices[b1]] )
696  	      {
697  	         nintervalvars = 0;
698  	         intervalpotential = 0.0;
699  	         withlinkvars = FALSE;
700  	         b2 = b1;
701  	         continue;
702  	      }
703  	
704  	      /* interval starts at b1 */
705  	      if( b2 < b1 )
706  	      {
707  	         nintervalvars = decomphorizon->ndiscretevars[blockindb1];
708  	         assert(nintervalvars < maxblocksize); /* otherwise, it wasn't suitable */
709  	         intervalpotential = decomphorizon->potential[blockindb1];
710  	         withlinkvars = FALSE;
711  	         b2 = b1;
712  	      }
713  	      /* subtract the variables from the previous block */
714  	      else
715  	      {
716  	         int prevblockind;
717  	         assert(b1 > (linkvarsexist ? 1 : 0));
718  	         prevblockind = decomphorizon->blockindices[b1 - 1];
719  	         assert(decomphorizon->suitable[prevblockind]);
720  	         nintervalvars -= decomphorizon->ndiscretevars[prevblockind];
721  	         intervalpotential -= decomphorizon->potential[prevblockind];
722  	      }
723  	
724  	      /* check if block allows to include linking variables */
725  	      if( ! withlinkvars && linkvarsexist && decomphorizon->ndiscretevars[0] + decomphorizon->ndiscretevars[blockindb1] < maxblocksize )
726  	      {
727  	         withlinkvars = TRUE;
728  	         nintervalvars = decomphorizon->ndiscretevars[0] + decomphorizon->ndiscretevars[blockindb1];
729  	         b2 = b1;
730  	      }
731  	      else if( withlinkvars && decomphorizon->ndiscretevars[0] + decomphorizon->ndiscretevars[blockindb1] >= maxblocksize )
732  	      {
733  	         withlinkvars = FALSE;
734  	         nintervalvars = decomphorizon->ndiscretevars[blockindb1];
735  	         b2 = b1;
736  	      }
737  	
738  	      /* extend the interval by further blocks, if possible */
739  	      while( ++b2 < decomphorizon->nblocks )
740  	      {
741  	         blockindb2 = decomphorizon->blockindices[b2];
742  	
743  	         if( ! decomphorizon->suitable[blockindb2] || nintervalvars + decomphorizon->ndiscretevars[blockindb2] >= maxblocksize )
744  	            break;
745  	
746  	         nintervalvars += decomphorizon->ndiscretevars[blockindb2];
747  	         intervalpotential += decomphorizon->potential[blockindb2];
748  	      }
749  	
750  	      /* store the start of the interval with maximum potential */
751  	      if( intervalpotential > maxpotential )
752  	      {
753  	         bestpos = b1; /* because pos is incremented by 1 again */
754  	         maxpotential = intervalpotential;
755  	      }
756  	   }
757  	
758  	   SCIPdebugMsg(scip, "Potential based selection chooses interval starting from block %d with potential %.1g\n",
759  	      bestpos, maxpotential);
760  	
761  	   return bestpos;
762  	}
763  	
764  	/** has this block been used too recently? */
765  	static
766  	SCIP_Bool decompHorizonBlockUsedRecently(
767  	   SCIP*                 scip,               /**< SCIP data structure */
768  	   DECOMPHORIZON*        decomphorizon,      /**< decomposition horizon data structure */
769  	   int                   blockpos            /**< position of block */
770  	   )
771  	{
772  	   assert(scip != NULL);
773  	   assert(decomphorizon != NULL);
774  	   assert(0 <= blockpos);
775  	   assert(blockpos < decomphorizon->nblocks);
776  	
777  	   return (decomphorizon->lastsolblock[decomphorizon->blockindices[blockpos]] == SCIPgetBestSol(scip) ||
778  	      (decomphorizon->overlapinterval[0] <= blockpos && blockpos <= decomphorizon->overlapinterval[1]));
779  	}
780  	
781  	/** query the start and end of the next suitable block after the last @p lastblockused
782  	 *
783  	 *  @return TRUE if next suitable block could be found, otherwise FALSE
784  	 */
785  	static
786  	SCIP_Bool decompHorizonNext(
787  	   SCIP*                 scip,               /**< SCIP data structure */
788  	   DECOMPHORIZON*        decomphorizon,      /**< decomposition horizon data structure */
789  	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
790  	   int                   maxblocksize,       /**< maximum block size in number of variables */
791  	   int*                  blockintervalstart, /**< pointer to store position of first block of interval */
792  	   int*                  blockintervalend,   /**< pointer to store position of last block of interval */
793  	   int*                  nextblocklabel,     /**< pointer to store label of the next suitable block */
794  	   SCIP_Bool*            fixlinkvars         /**< should the linking variables be fixed, as well? */
795  	   )
796  	{
797  	   SCIP_Bool found;
798  	   int pos;
799  	   int firstpos;
800  	   SCIP_SOL* bestsol;
801  	   assert(decomphorizon != NULL);
802  	   assert(blockintervalstart != NULL);
803  	   assert(blockintervalend != NULL);
804  	   assert(nextblocklabel != NULL);
805  	   assert(fixlinkvars != NULL);
806  	
807  	   assert(decomphorizon->init);
808  	
809  	   if( decomphorizon->nsuitableblocks == 0 )
810  	   {
811  	      return FALSE;
812  	   }
813  	
814  	   /* get the last block position that was used by the heuristic. Search for it, and continue with the next block. */
815  	   found = decomphorizon->lastblockpos >= 0;
816  	   firstpos = decomphorizon->lastblockpos;
817  	   assert(! found || (firstpos >= 0 && firstpos < decomphorizon->nblocks));
818  	
819  	   bestsol = SCIPgetBestSol(scip);
820  	
821  	   /* choose first position based on potential; subtract -1 because we immediately increase it */
822  	   if( ! found || bestsol != decomphorizon->lastsolblock[decomphorizon->blockindices[firstpos]] )
823  	      firstpos = decompHorizonGetFirstPosBestPotential(scip, decomphorizon, heurdata, maxblocksize) - 1;
824  	
825  	   /* that's why we subtract 1 from potential based position computation */
826  	   pos = (firstpos + 1) % decomphorizon->nblocks;
827  	
828  	   while( pos < decomphorizon->nblocks &&
829  	      (! decomphorizon->suitable[decomphorizon->blockindices[pos]] || decomphorizon->blocklabels[decomphorizon->blockindices[pos]] == SCIP_DECOMP_LINKVAR ||
830  	         decompHorizonBlockUsedRecently(scip, decomphorizon, pos)) )
831  	      pos++;
832  	
833  	   if( pos == decomphorizon->nblocks )
834  	   {
835  	      pos = 0;
836  	      while( pos < firstpos &&
837  	         (! decomphorizon->suitable[decomphorizon->blockindices[pos]] || decomphorizon->blocklabels[decomphorizon->blockindices[pos]] == SCIP_DECOMP_LINKVAR ||
838  	            decompHorizonBlockUsedRecently(scip, decomphorizon, pos)) )
839  	         pos++;
840  	   }
841  	
842  	   assert(pos == firstpos || (0 <= pos && decomphorizon->nblocks > pos && (decomphorizon->suitable[decomphorizon->blockindices[pos]] || pos == 0)));
843  	
844  	   *fixlinkvars = TRUE;
845  	   /* the next suitable block position has been discovered */
846  	   if( pos != firstpos && decomphorizon->suitable[decomphorizon->blockindices[pos]] && !decompHorizonBlockUsedRecently(scip, decomphorizon, pos) )
847  	   {
848  	      int ndiscretevars;
849  	      *nextblocklabel = decomphorizon->blocklabels[decomphorizon->blockindices[pos]];
850  	      *blockintervalstart = pos;
851  	      *blockintervalend = pos;
852  	
853  	      ndiscretevars = decomphorizon->ndiscretevars[decomphorizon->blockindices[pos]];
854  	      /* check if linking variable block exceeds maximum block size */
855  	      if( decomphorizon->blocklabels[0] == SCIP_DECOMP_LINKVAR )
856  	      {
857  	         *fixlinkvars = decomphorizon->ndiscretevars[0] + ndiscretevars > maxblocksize;
858  	      }
859  	
860  	      /* add linking variables to the block */
861  	      if( !(*fixlinkvars) )
862  	         ndiscretevars += decomphorizon->ndiscretevars[0];
863  	
864  	      /* extend the subproblem until maximum target fixing rate is reached */
865  	      while( ++pos < decomphorizon->nblocks && decomphorizon->suitable[decomphorizon->blockindices[pos]] && ndiscretevars + decomphorizon->ndiscretevars[decomphorizon->blockindices[pos]] < maxblocksize )
866  	      {
867  	         *blockintervalend = pos;
868  	         *nextblocklabel = decomphorizon->blocklabels[decomphorizon->blockindices[pos]];
869  	         ndiscretevars += decomphorizon->ndiscretevars[decomphorizon->blockindices[pos]];
870  	      }
871  	
872  	      return TRUE;
873  	   }
874  	   else
875  	   {
876  	      /* no next, suitable block exists */
877  	      *blockintervalstart = *blockintervalend = -1;
878  	      *nextblocklabel = -100;
879  	
880  	      return FALSE;
881  	   }
882  	}
883  	
884  	/** get the variables of this decomposition horizon */
885  	static
886  	SCIP_VAR** decomphorizonGetVars(
887  	   DECOMPHORIZON*        decomphorizon       /**< decomposition horizon data structure */
888  	   )
889  	{
890  	   assert(decomphorizon != NULL);
891  	   assert(decomphorizon->init);
892  	
893  	   return decomphorizon->vars;
894  	}
895  	
896  	/** create a rolling horizon data structure */
897  	static
898  	SCIP_RETCODE rollingHorizonCreate(
899  	   SCIP*                 scip,               /**< SCIP data structure */
900  	   ROLLINGHORIZON**      rollinghorizon      /**< pointer to rolling horizon data structure */
901  	   )
902  	{
903  	   int size;
904  	   assert(scip != NULL);
905  	   assert(rollinghorizon != NULL);
906  	
907  	   size = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
908  	   SCIP_CALL( SCIPallocBlockMemory(scip, rollinghorizon) );
909  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*rollinghorizon)->distances, size) );
910  	   SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(*rollinghorizon)->used, size) );
911  	   (*rollinghorizon)->distancessize = size;
912  	   (*rollinghorizon)->variablegraph = NULL;
913  	   (*rollinghorizon)->lastdistance = -1;
914  	   (*rollinghorizon)->niterations = 0;
915  	   (*rollinghorizon)->nused = 0;
916  	
917  	   return SCIP_OKAY;
918  	}
919  	
920  	
921  	/** reset a taboo list */
922  	static
923  	void tabooListReset(
924  	   TABOOLIST*            taboolist           /**< taboo list data structure */
925  	   )
926  	{
927  	   taboolist->ntaboolabels = 0;
928  	   taboolist->needssorting = FALSE;
929  	}
930  	
931  	/** create a taboo list data structure */
932  	static
933  	SCIP_RETCODE createTabooList(
934  	   SCIP*                 scip,               /**< SCIP data structure */
935  	   TABOOLIST**           taboolist,          /**< pointer to store taboo list data structure */
936  	   int                   initialsize         /**< initial storage capacity of taboo list */
937  	   )
938  	{
939  	   assert(scip != NULL);
940  	   assert(taboolist != NULL);
941  	
942  	   SCIP_CALL( SCIPallocBlockMemory(scip, taboolist) );
943  	
944  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*taboolist)->taboolabels, initialsize) );
945  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*taboolist)->sortedlabels, initialsize) );
946  	   (*taboolist)->memsize = initialsize;
947  	   tabooListReset(*taboolist);
948  	
949  	   return SCIP_OKAY;
950  	}
951  	
952  	/** free a taboo list data structure */
953  	static
954  	void freeTabooList(
955  	   SCIP*                 scip,               /**< SCIP data structure */
956  	   TABOOLIST**           taboolist           /**< pointer to taboo list data structure that should be freed */
957  	   )
958  	{
959  	   assert(scip != NULL);
960  	   assert(taboolist != NULL);
961  	
962  	   if( *taboolist == NULL )
963  	      return;
964  	
965  	   SCIPfreeBlockMemoryArray(scip, &(*taboolist)->sortedlabels, (*taboolist)->memsize);
966  	   SCIPfreeBlockMemoryArray(scip, &(*taboolist)->taboolabels, (*taboolist)->memsize);
967  	   SCIPfreeBlockMemory(scip, taboolist);
968  	}
969  	
970  	/** add an element to the taboo list */
971  	static
972  	SCIP_RETCODE tabooListAdd(
973  	   SCIP*                 scip,               /**< SCIP data structure */
974  	   TABOOLIST*            taboolist,          /**< taboo list data structure */
975  	   int                   elem                /**< element that should be added to the taboo list */
976  	   )
977  	{
978  	   assert(scip != NULL);
979  	   assert(taboolist != NULL);
980  	
981  	   if( taboolist->memsize == taboolist->ntaboolabels )
982  	   {
983  	      int newsize = SCIPcalcMemGrowSize(scip, taboolist->ntaboolabels + 1);
984  	      assert(newsize >= taboolist->ntaboolabels + 1);
985  	
986  	      SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &taboolist->taboolabels, taboolist->memsize, newsize) );
987  	      SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &taboolist->sortedlabels, taboolist->memsize, newsize) );
988  	
989  	      taboolist->memsize = newsize;
990  	   }
991  	
992  	   assert(taboolist->ntaboolabels < taboolist->memsize);
993  	   taboolist->taboolabels[taboolist->ntaboolabels++] = elem;
994  	
995  	   taboolist->needssorting = TRUE;
996  	
997  	   return SCIP_OKAY;
998  	}
999  	
1000 	/** find an element in the taboo list */
1001 	static
1002 	SCIP_Bool tabooListFind(
1003 	   TABOOLIST*            taboolist,          /**< taboo list data structure */
1004 	   int                   elem                /**< element that should be added to the taboo list */
1005 	   )
1006 	{
1007 	   SCIP_Bool found;
1008 	   int pos;
1009 	   assert(taboolist != NULL);
1010 	
1011 	   if( taboolist->ntaboolabels == 0 )
1012 	      return FALSE;
1013 	
1014 	   if( taboolist->needssorting )
1015 	   {
1016 	      BMScopyMemoryArray(taboolist->sortedlabels, taboolist->taboolabels, taboolist->ntaboolabels);
1017 	      SCIPsortInt(taboolist->sortedlabels, taboolist->ntaboolabels);
1018 	   }
1019 	
1020 	   found = SCIPsortedvecFindInt(taboolist->sortedlabels, elem, taboolist->ntaboolabels, &pos);
1021 	
1022 	   return found;
1023 	}
1024 	
1025 	/** get most recent k elements from taboo list */
1026 	static
1027 	int* tabooListGetLastK(
1028 	   TABOOLIST*            taboolist,          /**< taboo list data structure */
1029 	   int                   k                   /**< the number of elements that should be returned */
1030 	   )
1031 	{
1032 	   assert(taboolist != NULL);
1033 	   assert(k <= taboolist->ntaboolabels);
1034 	   assert(k > 0);
1035 	
1036 	   return &taboolist->taboolabels[taboolist->ntaboolabels - k];
1037 	}
1038 	
1039 	/** get number of elements in taboo list */
1040 	static
1041 	int taboolistgetNElems(
1042 	   TABOOLIST*            taboolist           /**< taboo list data structure */
1043 	   )
1044 	{
1045 	   return taboolist->ntaboolabels;
1046 	}
1047 	
1048 	/** free a rolling horizon data structure */
1049 	static
1050 	void rollingHorizonFree(
1051 	   SCIP*                 scip,               /**< SCIP data structure */
1052 	   ROLLINGHORIZON**      rollinghorizon      /**< pointer to rolling horizon data structure */
1053 	   )
1054 	{
1055 	   assert(scip != NULL);
1056 	   assert(rollinghorizon != NULL);
1057 	
1058 	   /* empty rolling horizon */
1059 	   if( *rollinghorizon == NULL )
1060 	      return;
1061 	
1062 	   if( (*rollinghorizon)->variablegraph != NULL )
1063 	   {
1064 	      SCIPvariableGraphFree(scip, &(*rollinghorizon)->variablegraph);
1065 	   }
1066 	
1067 	   SCIPfreeBlockMemoryArray(scip, &(*rollinghorizon)->distances, (*rollinghorizon)->distancessize);
1068 	   SCIPfreeBlockMemoryArray(scip, &(*rollinghorizon)->used, (*rollinghorizon)->distancessize);
1069 	   SCIPfreeBlockMemory(scip, rollinghorizon);
1070 	}
1071 	
1072 	/** is there potential to run another iteration of the rolling horizon approach? */
1073 	static
1074 	SCIP_Bool rollingHorizonRunAgain(
1075 	   SCIP*                 scip,               /**< SCIP data structure */
1076 	   ROLLINGHORIZON*       rollinghorizon,     /**< rolling horizon data structure */
1077 	   SCIP_HEURDATA*        heurdata            /**< heuristic data */
1078 	   )
1079 	{
1080 	   int maxnused = (int)(heurdata->rollhorizonlimfac * (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip)
1081 	         - rollinghorizon->nnonreachable));
1082 	
1083 	   /* run again if a certain percentage of the reachable variables (in the same connected component)
1084 	    * was not used in a previous neighborhood
1085 	    */
1086 	   return (rollinghorizon->nused < maxnused);
1087 	}
1088 	
1089 	/** store the distances from the selected variable permanently for the rolling horizon approach */
1090 	static
1091 	void rollingHorizonStoreDistances(
1092 	   ROLLINGHORIZON*       rollinghorizon,     /**< rolling horizon data structure */
1093 	   int*                  distances           /**< breadth-first distances indexed by Probindex of variables */
1094 	   )
1095 	{
1096 	   int i;
1097 	   BMScopyMemoryArray(rollinghorizon->distances, distances, rollinghorizon->distancessize);
1098 	   rollinghorizon->lastdistance = 0;
1099 	   rollinghorizon->nnonreachable = 0;
1100 	
1101 	   /* collect number of nonreachable variables */
1102 	   for( i = 0; i < rollinghorizon->distancessize; ++i )
1103 	   {
1104 	      if( distances[i] == -1 )
1105 	         ++rollinghorizon->nnonreachable;
1106 	   }
1107 	}
1108 	
1109 	/** is the variable in the current neighborhood which is given by the breadth-first distances from a central variable? */
1110 	static
1111 	SCIP_Bool isVariableInNeighborhood(
1112 	   SCIP_VAR*             var,                /**< problem variable */
1113 	   int*                  distances,          /**< breadth-first distances indexed by Probindex of variables */
1114 	   int                   maxdistance         /**< maximum distance (inclusive) to be considered for neighborhoods */
1115 	   )
1116 	{
1117 	   assert(var != NULL);
1118 	   assert(distances != NULL);
1119 	   assert(maxdistance >= 0);
1120 	   assert(SCIPvarGetProbindex(var) >= 0);
1121 	
1122 	   return (distances[SCIPvarGetProbindex(var)] != -1 && distances[SCIPvarGetProbindex(var)] <= maxdistance);
1123 	}
1124 	
1125 	/** get fixing value of variable */
1126 	static
1127 	SCIP_Real getFixVal(
1128 	   SCIP*                 scip,               /**< SCIP data structure */
1129 	   SCIP_SOL*             sol,                /**< solution in main SCIP for fixing values */
1130 	   SCIP_VAR*             var                 /**< problem variable */
1131 	   )
1132 	{
1133 	   SCIP_Real fixval;
1134 	   SCIP_Real lb;
1135 	   SCIP_Real ub;
1136 	
1137 	   fixval = SCIPgetSolVal(scip, sol, var);
1138 	   lb = SCIPvarGetLbGlobal(var);
1139 	   ub = SCIPvarGetUbGlobal(var);
1140 	   assert(SCIPisLE(scip, lb, ub));
1141 	
1142 	   /* due to dual reductions, it may happen that the solution value is not in the variable's domain anymore */
1143 	   if( SCIPisLT(scip, fixval, lb) )
1144 	      fixval = lb;
1145 	   else if( SCIPisGT(scip, fixval, ub) )
1146 	      fixval = ub;
1147 	
1148 	   return fixval;
1149 	}
1150 	
1151 	/** fixes variables in subproblem based on long breadth-first distances in variable graph */
1152 	static
1153 	SCIP_RETCODE fixNonNeighborhoodVariables(
1154 	   SCIP*                 scip,               /**< SCIP data structure */
1155 	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
1156 	   ROLLINGHORIZON*       rollinghorizon,     /**< rolling horizon data structure to save relevant information, or NULL if not needed */
1157 	   SCIP_SOL*             sol,                /**< solution in main SCIP for fixing values */
1158 	   SCIP_VAR**            vars,               /**< variables in the main SCIP */
1159 	   SCIP_VAR**            fixedvars,          /**< buffer to store variables that should be fixed */
1160 	   SCIP_Real*            fixedvals,          /**< buffer to store fixing values for fixed variables */
1161 	   int*                  distances,          /**< breadth-first distances indexed by Probindex of variables */
1162 	   int                   maxdistance,        /**< maximum distance (inclusive) to be considered for neighborhoods */
1163 	   int*                  nfixings            /**< pointer to store number of fixed variables */
1164 	   )
1165 	{
1166 	   int i;
1167 	   int nbinvars;
1168 	   int nintvars;
1169 	   int nvars;
1170 	   int nvarstofix;
1171 	
1172 	   SCIP_CALL( SCIPgetVarsData(scip, NULL, &nvars, &nbinvars, &nintvars, NULL, NULL) );
1173 	
1174 	   nvarstofix = heurdata->fixcontvars ? nvars : nbinvars + nintvars;
1175 	   *nfixings = 0;
1176 	
1177 	   /* change bounds of variables of the subproblem */
1178 	   for( i = 0; i < nvarstofix; i++ )
1179 	   {
1180 	      /* fix all variables that are too far away from this variable according to maxdistance */
1181 	      if( distances[i] == -1 || distances[i] > maxdistance )
1182 	      {
1183 	         SCIP_Real fixval;
1184 	
1185 	         fixval = getFixVal(scip, sol, vars[i]);
1186 	
1187 	         /* store variable and value of this fixing */
1188 	         if( !SCIPisInfinity(scip, REALABS(fixval)) )
1189 	         {
1190 	            fixedvars[*nfixings] = vars[i];
1191 	            fixedvals[*nfixings] = fixval;
1192 	            ++(*nfixings);
1193 	         }
1194 	      }
1195 	      else if( rollinghorizon != NULL && i < nbinvars + nintvars && ! rollinghorizon->used[i] )
1196 	      {
1197 	         ++rollinghorizon->nused;
1198 	         rollinghorizon->used[i] = TRUE;
1199 	      }
1200 	   }
1201 	
1202 	   if( rollinghorizon != NULL )
1203 	   {
1204 	      rollinghorizon->lastmaxdistance = maxdistance;
1205 	      rollinghorizon->niterations++;
1206 	   }
1207 	
1208 	   return SCIP_OKAY;
1209 	}
1210 	
1211 	/** determine the maximum allowed distance to stay within the restriction to fix at least minfixingrate many non
1212 	 *  neighborhood variables
1213 	 */
1214 	static
1215 	SCIP_RETCODE determineMaxDistance(
1216 	   SCIP*                 scip,               /**< SCIP data structure */
1217 	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
1218 	   int*                  distances,          /**< breadth-first distances indexed by Probindex of variables */
1219 	   int*                  choosevardistance   /**< pointer to store the computed maximum distance */
1220 	   )
1221 	{
1222 	   int* distancescopy;
1223 	   int nrelevantdistances;
1224 	   int criticalidx;
1225 	   int zeropos;
1226 	   int nvars;
1227 	   int nbinvars;
1228 	   int nintvars;
1229 	
1230 	   SCIP_CALL( SCIPgetVarsData(scip, NULL, &nvars, &nbinvars, &nintvars, NULL, NULL) );
1231 	
1232 	   nrelevantdistances = (heurdata->fixcontvars ?  nvars : (nbinvars + nintvars));
1233 	
1234 	   /* copy the relevant distances of either the discrete or all problem variables and sort them */
1235 	   SCIP_CALL( SCIPduplicateBufferArray(scip, &distancescopy, distances, nrelevantdistances) );
1236 	   SCIPsortInt(distancescopy, nrelevantdistances);
1237 	
1238 	   /* distances can be infinite in the case of multiple connected components; therefore, search for the index of the
1239 	    * zero entry, which is the unique representative of the chosen variable in the sorted distances
1240 	    */
1241 	   zeropos = -1;
1242 	
1243 	   /* TODO: use selection method instead */
1244 	   (void)SCIPsortedvecFindInt(distancescopy, 0, nrelevantdistances, &zeropos);
1245 	   assert(zeropos >= 0);
1246 	
1247 	   /* determine the critical index to look for an appropriate neighborhood distance, starting from the zero position */
1248 	   criticalidx = zeropos + (int)((1.0 - heurdata->minfixingrate) * nrelevantdistances);
1249 	   criticalidx = MIN(criticalidx, nrelevantdistances - 1);
1250 	
1251 	   /* determine the maximum breadth-first distance such that the neighborhood size stays small enough (below 1-minfixingrate)*/
1252 	   *choosevardistance = distancescopy[criticalidx];
1253 	
1254 	   /* we set the distance to exactly the distance at the critical index. If the distance at critical index is not the
1255 	    * last one before the distance increases, we decrease the choosevardistance such that the entire neighborhood
1256 	    * fits into the minfixingrate restriction
1257 	    */
1258 	   if( criticalidx != nrelevantdistances - 1 && distancescopy[criticalidx + 1] == *choosevardistance )
1259 	      (*choosevardistance)--;
1260 	
1261 	   /* update the maximum distance */
1262 	   heurdata->maxseendistance = MAX(heurdata->maxseendistance, distancescopy[nrelevantdistances - 1]);
1263 	
1264 	   SCIPfreeBufferArray(scip, &distancescopy);
1265 	
1266 	   return SCIP_OKAY;
1267 	}
1268 	
1269 	/** gets the average size of a discrete neighborhood over all variables tested */
1270 	static
1271 	SCIP_Real heurdataAvgDiscreteNeighborhoodSize(
1272 	   SCIP_HEURDATA*        heurdata            /**< heuristic data */
1273 	   )
1274 	{
1275 	   return heurdata->sumdiscneighborhoodvars / (MAX(1.0, (SCIP_Real)heurdata->nneighborhoods));
1276 	}
1277 	
1278 	/** count occurrences of this label */
1279 	static
1280 	int countLabel(
1281 	   int*                  labels,             /**< sorted array of labels */
1282 	   int                   start,              /**< start position */
1283 	   int                   nlabels             /**< length of the labels array */
1284 	   )
1285 	{
1286 	   int label = labels[start];
1287 	   int end = start;
1288 	
1289 	   assert(labels != NULL);
1290 	   assert(start < nlabels);
1291 	   assert(start >= 0);
1292 	
1293 	   do
1294 	   {
1295 	      ++end;
1296 	   }
1297 	   while( end < nlabels && labels[end] == label );
1298 	
1299 	   return end - start;
1300 	}
1301 	
1302 	/** todo select initial variable based on decomposition information, if available */
1303 	static
1304 	SCIP_RETCODE selectInitialVariableDecomposition(
1305 	   SCIP*                 scip,               /**< SCIP data structure */
1306 	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
1307 	   SCIP_DECOMP*          decomp,             /**< decomposition data structure with variable labels */
1308 	   SCIP_VGRAPH*          vargraph,           /**< variable graph data structure to work on */
1309 	   int*                  distances,          /**< breadth-first distances indexed by Probindex of variables */
1310 	   SCIP_VAR**            selvar,             /**< pointer to store the selected variable */
1311 	   int*                  selvarmaxdistance   /**< maximal distance k to consider for selected variable neighborhood */
1312 	   )
1313 	{
1314 	   SCIP_SOL* sol;
1315 	   SCIP_VAR** vars;
1316 	   SCIP_VAR** varscopy;
1317 	   int* varlabels;
1318 	   int* discvaridxs;
1319 	   SCIP_Real bestpotential;
1320 	   int nbinvars;
1321 	   int nintvars;
1322 	   int nvars;
1323 	   int currblockstart;
1324 	   int bestvaridx;
1325 	   int cntmessages;
1326 	   int nblocks;
1327 	   TABOOLIST* taboolist;
1328 	
1329 	   assert(scip != NULL);
1330 	   assert(heurdata != NULL);
1331 	   assert(decomp != NULL);
1332 	   assert(vargraph != NULL);
1333 	   assert(distances != NULL);
1334 	   assert(selvar != NULL);
1335 	   assert(selvarmaxdistance != NULL);
1336 	
1337 	   sol = SCIPgetBestSol(scip);
1338 	   assert(sol != NULL);
1339 	   nblocks = SCIPdecompGetNBlocks(decomp);
1340 	   /* create a taboo list for recently used block labels at the first initial variable selection */
1341 	   if( heurdata->taboolist == NULL )
1342 	   {
1343 	      SCIPdebugMsg(scip, "Creating taboo list\n");
1344 	      SCIP_CALL( createTabooList(scip, &heurdata->taboolist, nblocks) );
1345 	   }
1346 	
1347 	   taboolist = heurdata->taboolist;
1348 	   assert(taboolist != NULL);
1349 	
1350 	   /* reset taboo list if a new solution has been found since the last initialization call */
1351 	   if( sol != heurdata->lastinitsol )
1352 	   {
1353 	      int nblockstokeep = 3;
1354 	      int e;
1355 	      int ntaboolistelems;
1356 	      ntaboolistelems = taboolistgetNElems(heurdata->taboolist);
1357 	
1358 	      /* keep the last 3 blocks except for border cases of very coarse decomposition, or too few taboo elements */
1359 	      if( taboolistgetNElems(heurdata->taboolist) > 0 )
1360 	      {
1361 	         nblockstokeep = MIN(nblockstokeep, nblocks - 1);
1362 	         nblockstokeep = MIN(nblockstokeep, MAX(1, ntaboolistelems - 1));
1363 	         nblockstokeep = MAX(nblockstokeep, 0);
1364 	      }
1365 	      else
1366 	         nblockstokeep = 0;
1367 	
1368 	      SCIPdebugMsg(scip, "Resetting taboo list, keeping %d elements\n", nblockstokeep);
1369 	      if( nblockstokeep > 0 )
1370 	      {
1371 	         int* labelstokeep;
1372 	         int* taboolistlastk;
1373 	         taboolistlastk = tabooListGetLastK(taboolist, nblockstokeep);
1374 	         SCIP_CALL( SCIPduplicateBufferArray(scip, &labelstokeep, taboolistlastk, nblockstokeep) );
1375 	
1376 	         tabooListReset(taboolist);
1377 	
1378 	         /* reinstall the last 3 elements into the taboo list */
1379 	         for( e = 0; e < nblockstokeep; ++e )
1380 	         {
1381 	            SCIP_CALL( tabooListAdd(scip, taboolist, labelstokeep[e]) );
1382 	         }
1383 	
1384 	         SCIPfreeBufferArray(scip, &labelstokeep);
1385 	      }
1386 	      else if( ntaboolistelems > 0 )
1387 	      {
1388 	         tabooListReset(taboolist);
1389 	      }
1390 	
1391 	      heurdata->allblocksunsuitable = FALSE;
1392 	   }
1393 	
1394 	   *selvar = NULL;
1395 	   /* do not continue if, for this solution, all blocks are known to be unsuitable */
1396 	   if( heurdata->allblocksunsuitable )
1397 	   {
1398 	      SCIPdebugMsg(scip, "Skip initial variable selection because all blocks are unsuitable for solution %d\n",
1399 	         SCIPsolGetIndex(sol));
1400 	      return SCIP_OKAY;
1401 	   }
1402 	
1403 	   /* get integer and binary variables from problem and labels for all variables */
1404 	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
1405 	
1406 	   SCIP_CALL( SCIPduplicateBufferArray(scip, &varscopy, vars, nvars) );
1407 	   SCIP_CALL( SCIPallocBufferArray(scip, &varlabels, nvars) );
1408 	   SCIP_CALL( SCIPallocBufferArray(scip, &discvaridxs, nvars) );
1409 	
1410 	   SCIPdecompGetVarsLabels(decomp, vars, varlabels, nvars);
1411 	
1412 	   /* sort the variables copy by the labels */
1413 	   SCIPsortIntPtr(varlabels, (void **)varscopy, nvars);
1414 	
1415 	   currblockstart = 0;
1416 	   bestpotential = 0.0;
1417 	   bestvaridx = -1;
1418 	   cntmessages = 0;
1419 	   /* compute the potential for every block */
1420 	   while( currblockstart < nvars )
1421 	   {
1422 	      int currblockend;
1423 	      int v;
1424 	      int label = varlabels[currblockstart];
1425 	      int ndiscblockvars;
1426 	      SCIP_Real potential;
1427 	
1428 	      currblockend = currblockstart + countLabel(varlabels, currblockstart, nvars);
1429 	
1430 	      /* this block was recently used and should be skipped */
1431 	      if( tabooListFind(taboolist, label) )
1432 	      {
1433 	         if( cntmessages++ < 3 )
1434 	            SCIPdebugMsg(scip, "Skipping block <%d> from taboo list\n", label);
1435 	
1436 	         currblockstart += currblockend;
1437 	
1438 	         continue;
1439 	      }
1440 	
1441 	      /* author bzfhende
1442 	       *
1443 	       * TODO omit the linking variables from the computation of the potential?
1444 	       */
1445 	      /* check if block has discrete variables */
1446 	      ndiscblockvars = 0;
1447 	      for( v = currblockstart; v < currblockend; ++v )
1448 	      {
1449 	         if( SCIPvarGetType(varscopy[v]) == SCIP_VARTYPE_BINARY || SCIPvarGetType(varscopy[v]) == SCIP_VARTYPE_INTEGER )
1450 	            discvaridxs[ndiscblockvars++] = v;
1451 	      }
1452 	
1453 	      /* skip potential computation if block has no discrete variables */
1454 	      if( ndiscblockvars > 0 )
1455 	      {
1456 	         potential = getPotential(scip, heurdata, sol, &(varscopy[currblockstart]), currblockend - currblockstart);
1457 	
1458 	         if( potential > bestpotential )
1459 	         {
1460 	            bestpotential = potential;
1461 	            /* randomize the selection of the best variable */
1462 	            bestvaridx = discvaridxs[SCIPrandomGetInt(heurdata->randnumgen, 0, ndiscblockvars - 1)];
1463 	            assert(bestvaridx >= 0);
1464 	         }
1465 	      }
1466 	
1467 	      currblockstart += currblockend;
1468 	   }
1469 	
1470 	   /* we return the first discrete variable from the block with maximum potential */
1471 	   if( bestvaridx >= 0 )
1472 	   {
1473 	      *selvar = varscopy[bestvaridx];
1474 	
1475 	      /* save block label in taboo list to not use it again too soon */
1476 	      SCIP_CALL( tabooListAdd(scip, taboolist, varlabels[bestvaridx]) );
1477 	
1478 	      SCIPdebugMsg(scip, "Select initial variable <%s> from block <%d>\n", SCIPvarGetName(*selvar), varlabels[bestvaridx]);
1479 	   }
1480 	   else
1481 	   {
1482 	      SCIPdebugMsg(scip, "Could not find suitable block for variable selection.\n");
1483 	      heurdata->allblocksunsuitable = TRUE;
1484 	      *selvar = NULL;
1485 	   }
1486 	
1487 	   /* use the variable constraint graph to compute distances to all other variables, and store the selvarmaxdistance */
1488 	   if( *selvar != NULL )
1489 	   {
1490 	      SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, vargraph, selvar, 1, distances,
1491 	            heurdata->maxdistance == -1 ? INT_MAX : heurdata->maxdistance, INT_MAX, INT_MAX) );
1492 	
1493 	      SCIP_CALL( determineMaxDistance(scip, heurdata, distances, selvarmaxdistance) );
1494 	
1495 	      /* maximum distance is 0, i.e., even the size of the 1-neighborhood of this variable exceeds the fixing rate */
1496 	      if( *selvarmaxdistance == 0 )
1497 	      {
1498 	         SCIPdebugMsg(scip, "1-Neighborhood of variable <%s> too large.\n", SCIPvarGetName(*selvar));
1499 	         *selvar = NULL;
1500 	      }
1501 	   }
1502 	
1503 	   /* remember this solution for the next initial selection */
1504 	   heurdata->lastinitsol = sol;
1505 	
1506 	   SCIPfreeBufferArray(scip, &discvaridxs);
1507 	   SCIPfreeBufferArray(scip, &varlabels);
1508 	   SCIPfreeBufferArray(scip, &varscopy);
1509 	
1510 	   return SCIP_OKAY;
1511 	}
1512 	
1513 	
1514 	
1515 	/** select a good starting variable at the first iteration of a rolling horizon approach */
1516 	static
1517 	SCIP_RETCODE selectInitialVariableRandomly(
1518 	   SCIP*                 scip,               /**< SCIP data structure */
1519 	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
1520 	   SCIP_VGRAPH*          vargraph,           /**< variable graph data structure to work on */
1521 	   int*                  distances,          /**< breadth-first distances indexed by Probindex of variables */
1522 	   SCIP_VAR**            selvar,             /**< pointer to store the selected variable */
1523 	   int*                  selvarmaxdistance   /**< maximal distance k to consider for selected variable neighborhood */
1524 	   )
1525 	{
1526 	   SCIP_SOL* sol;
1527 	   SCIP_VAR** vars;                          /* original scip variables */
1528 	   int nbinvars;
1529 	   int nintvars;
1530 	   int nvars;
1531 	   int nsearched;
1532 	   int searchlimit;
1533 	   int nintegralvarsleft;
1534 	   int nintegralvarsbound;
1535 	   int v;
1536 	   SCIP_VAR** varscopy;
1537 	   int maxdistance;
1538 	   SCIP_Real maxpotential;
1539 	
1540 	   assert(vargraph != NULL);
1541 	   assert(scip != NULL);
1542 	   assert(heurdata != NULL);
1543 	   assert(selvar != NULL);
1544 	   sol = SCIPgetBestSol(scip);
1545 	   assert(sol != NULL);
1546 	
1547 	   /* get required data of the original problem */
1548 	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
1549 	
1550 	   /* copy SCIP variables */
1551 	   SCIP_CALL( SCIPduplicateBufferArray(scip, &varscopy, vars, nbinvars + nintvars) );
1552 	   nsearched = 0;
1553 	   maxpotential = SCIP_REAL_MIN;
1554 	
1555 	   /* determine upper bound on neighborhood size */
1556 	   nintegralvarsbound = (int)((1.0 - heurdata->minfixingrate) * (nbinvars + nintvars));
1557 	
1558 	   /* maximum distance from selected variable for breadth-first search (if set to -1, we compute an exhaustive breadth-first
1559 	    * search and sort the variables by their distance)
1560 	    */
1561 	   maxdistance = (heurdata->maxdistance == - 1 ? INT_MAX : heurdata->maxdistance);
1562 	
1563 	   nintegralvarsleft  = nbinvars + nintvars;
1564 	   *selvar = NULL;
1565 	
1566 	   /* sort inactive variables to the end of the array */
1567 	   for( v = nintegralvarsleft - 1; v >= 0; --v )
1568 	   {
1569 	      if( ! SCIPvarIsActive(varscopy[v]) )
1570 	      {
1571 	         varscopy[v] = varscopy[nintegralvarsleft - 1];
1572 	         --nintegralvarsleft;
1573 	      }
1574 	   }
1575 	
1576 	   /* adjust the search limit */
1577 	   searchlimit = heurdata->nneighborhoods < 10 ? 5 : (int)(nintegralvarsleft / heurdataAvgDiscreteNeighborhoodSize(heurdata));
1578 	   searchlimit = MIN(searchlimit, 10);
1579 	
1580 	   /* multi variable potential: choose different disjoint neighborhoods, compare their potential */
1581 	   while( nsearched < searchlimit && nintegralvarsleft > 0 )
1582 	   {
1583 	      SCIP_VAR** neighborhood;
1584 	      SCIP_VAR* choosevar;
1585 	      int neighborhoodsize;
1586 	      int ndiscvarsneighborhood;
1587 	      int choosevardistance;
1588 	
1589 	      ++nsearched;
1590 	
1591 	      /* select a variable to start with randomly, but make sure it is active */
1592 	      do
1593 	      {
1594 	         int idx = SCIPrandomGetInt(heurdata->randnumgen, 0, nintegralvarsleft - 1);
1595 	         choosevar = varscopy[idx];
1596 	         assert(choosevar != NULL);
1597 	         /* sort inactive variables to the end */
1598 	         if( SCIPvarGetProbindex(choosevar) < 0 )
1599 	         {
1600 	            varscopy[idx] = varscopy[nintegralvarsleft - 1];
1601 	            --nintegralvarsleft;
1602 	         }
1603 	      }
1604 	      while( SCIPvarGetProbindex(choosevar) < 0 && nintegralvarsleft > 0 );
1605 	
1606 	      /* if there was no variable chosen, there are no active variables left */
1607 	      if( SCIPvarGetProbindex(choosevar) < 0 )
1608 	      {
1609 	         SCIPdebugMsg(scip, "No active variable left to perform breadth-first search\n");
1610 	         break;
1611 	      }
1612 	
1613 	      assert(SCIPvarIsIntegral(choosevar));
1614 	
1615 	      /* get neighborhood storage */
1616 	      SCIP_CALL( SCIPallocBufferArray(scip, &neighborhood, nvars) );
1617 	
1618 	      /* determine breadth-first distances from the chosen variable */
1619 	      SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, vargraph, &choosevar, 1, distances, maxdistance, INT_MAX, INT_MAX) );
1620 	
1621 	      /* use either automatic or user-defined max-distance for neighborhood in variable constraint graph */
1622 	      if( heurdata->maxdistance != -1 )
1623 	      {
1624 	         choosevardistance = heurdata->maxdistance;
1625 	      }
1626 	      else
1627 	      {
1628 	         SCIP_CALL( determineMaxDistance(scip, heurdata, distances, &choosevardistance) );
1629 	      }
1630 	
1631 	      ndiscvarsneighborhood = 0;
1632 	      neighborhoodsize = 0;
1633 	
1634 	      /* loop over variables and determine neighborhood */
1635 	      for( v = nvars - 1; v >= 0; --v )
1636 	      {
1637 	         SCIP_VAR* currvar;
1638 	         currvar = vars[v];
1639 	
1640 	         /* put variable in the neighborhood */
1641 	         if( isVariableInNeighborhood(currvar, distances, choosevardistance) )
1642 	         {
1643 	            neighborhood[neighborhoodsize++] = currvar;
1644 	
1645 	            /* increase discrete variables counter */
1646 	            if( SCIPvarIsIntegral(currvar) )
1647 	               ++ndiscvarsneighborhood;
1648 	         }
1649 	      }
1650 	
1651 	      /* check if neighborhood contains too many integer variables in order to satisfy the minimum fixing rate */
1652 	      if( ndiscvarsneighborhood >= nintegralvarsbound || ndiscvarsneighborhood <= 1 )
1653 	      {
1654 	         SCIPdebugMsg(scip, "Too many or too few discrete variables in neighboorhood: %d (%d)\n",
1655 	            ndiscvarsneighborhood, nbinvars + nintvars);
1656 	      }
1657 	      else
1658 	      {
1659 	         /* compare the neighborhood potential to the best potential found so far */
1660 	         SCIP_Real potential = getPotential(scip, heurdata, sol, neighborhood, neighborhoodsize);
1661 	
1662 	         /* big potential, take this variable */
1663 	         if( potential > maxpotential )
1664 	         {
1665 	            maxpotential = potential;
1666 	            *selvar = choosevar;
1667 	            *selvarmaxdistance = choosevardistance;
1668 	         }
1669 	      }
1670 	
1671 	      /* sort neighborhood variables to the end so that this neighborhood is not considered in further samples */
1672 	      for( v = nintegralvarsleft - 1; v >= 0; --v )
1673 	      {
1674 	         SCIP_VAR* currvar;
1675 	         currvar = vars[v];
1676 	
1677 	         if( isVariableInNeighborhood(currvar, distances, choosevardistance) )
1678 	         {
1679 	            varscopy[v] = varscopy[nintegralvarsleft - 1];
1680 	            --nintegralvarsleft;
1681 	         }
1682 	      }
1683 	
1684 	      heurdata->sumdiscneighborhoodvars += ndiscvarsneighborhood;
1685 	      heurdata->sumneighborhoodvars += neighborhoodsize;
1686 	      ++heurdata->nneighborhoods;
1687 	
1688 	      /* free current neighborhood */
1689 	      SCIPfreeBufferArray(scip, &neighborhood);
1690 	   }
1691 	
1692 	   SCIPfreeBufferArray(scip, &varscopy);
1693 	
1694 	   /* maybe no variable has a positive delta */
1695 	   if( !SCIPisPositive(scip, maxpotential) || *selvar == NULL )
1696 	   {
1697 	      SCIPdebugMsg(scip, "Stopping with maxpotential %15.9f and selected variable %s\n",
1698 	            maxpotential, *selvar != NULL ? SCIPvarGetName(*selvar) : "none");
1699 	      *selvar = NULL;
1700 	   }
1701 	
1702 	   return SCIP_OKAY;
1703 	}
1704 	
1705 	/** select the next variable using the rolling horizon */
1706 	static
1707 	SCIP_RETCODE selectNextVariable(
1708 	   SCIP*                 scip,               /**< SCIP data structure */
1709 	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
1710 	   ROLLINGHORIZON*       rollinghorizon,     /**< rolling horizon data structure to save relevant information, or NULL if not needed */
1711 	   int*                  distances,          /**< breadth-first distances indexed by Probindex of variables */
1712 	   SCIP_VAR**            selvar,             /**< pointer to store the selected variable */
1713 	   int*                  selvarmaxdistance   /**< maximal distance k to consider for selected variable neighborhood */
1714 	   )
1715 	{
1716 	   SCIP_VAR** vars;                          /* original scip variables */
1717 	   int i;
1718 	   int nbinvars;
1719 	   int nintvars;
1720 	   int minunuseddistance;
1721 	
1722 	   assert(scip != NULL);
1723 	   assert(rollinghorizon != NULL);
1724 	   assert(distances != NULL);
1725 	   assert(selvar != NULL);
1726 	   assert(selvarmaxdistance != NULL);
1727 	
1728 	   SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
1729 	
1730 	   /* loop over the variables that are left and pick the variable with
1731 	    * - the smallest, always nondecreasing distance
1732 	    * - that was not used before in a neighborhood
1733 	    */
1734 	   do
1735 	   {
1736 	      minunuseddistance = INT_MAX;
1737 	      *selvarmaxdistance = rollinghorizon->lastmaxdistance;
1738 	      *selvar = NULL;
1739 	      for( i = 0; i < nbinvars + nintvars && minunuseddistance > rollinghorizon->lastdistance; ++i )
1740 	      {
1741 	         if( rollinghorizon->distances[i] >= rollinghorizon->lastdistance
1742 	               && rollinghorizon->distances[i] < minunuseddistance && ! rollinghorizon->used[i] )
1743 	         {
1744 	            minunuseddistance = rollinghorizon->distances[i];
1745 	            *selvar = vars[i];
1746 	         }
1747 	      }
1748 	
1749 	      /* if no variable could be selected, we can stop */
1750 	      if( *selvar == NULL )
1751 	      {
1752 	         *selvarmaxdistance = 0;
1753 	         return SCIP_OKAY;
1754 	      }
1755 	
1756 	      /* determine the distances to other variables from this variable */
1757 	      SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, rollinghorizon->variablegraph, selvar, 1, distances, *selvarmaxdistance, INT_MAX, INT_MAX) );
1758 	
1759 	      SCIP_CALL( determineMaxDistance(scip, heurdata, distances, selvarmaxdistance) );
1760 	
1761 	      /* mark this variable as used in order to not find it again */
1762 	      if( *selvarmaxdistance == 0 )
1763 	      {
1764 	         rollinghorizon->used[SCIPvarGetProbindex(*selvar)] = TRUE;
1765 	         rollinghorizon->nused++;
1766 	         *selvar = NULL;
1767 	      }
1768 	   }
1769 	   while( rollingHorizonRunAgain(scip, rollinghorizon, heurdata) && (*selvar == NULL || *selvarmaxdistance == 0) );
1770 	
1771 	   /* breadth-first search determines the distances of all variables
1772 	    * that are no more than maxdistance away from the start variable
1773 	    */
1774 	   assert(*selvarmaxdistance <= rollinghorizon->lastmaxdistance);
1775 	   *selvarmaxdistance = MIN(*selvarmaxdistance, rollinghorizon->lastmaxdistance);
1776 	   rollinghorizon->lastdistance = minunuseddistance;
1777 	   rollinghorizon->lastmaxdistance = *selvarmaxdistance;
1778 	
1779 	   return SCIP_OKAY;
1780 	}
1781 	
1782 	/** mark some of the blocks between currblockstart and currblockend as recently used, depending on overlap */
1783 	static
1784 	void decompHorizonMarkInterval(
1785 	   SCIP*                 scip,               /**< SCIP data structure */
1786 	   DECOMPHORIZON*        decomphorizon,      /**< decomposition horizon data structure */
1787 	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
1788 	   SCIP_SOL*             sol,                /**< solution by which some of the blocks should be marked */
1789 	   int                   blockstartpos,      /**< current start position of interval */
1790 	   int                   blockendpos         /**< current end position (inclusive) of interval */
1791 	   )
1792 	{
1793 	   int nvarsinterval;
1794 	   int nvarsstartofinterval;
1795 	   int solstamppos;
1796 	   int b;
1797 	   SCIP_Real overlapcomplement;
1798 	
1799 	   assert(decomphorizon != NULL);
1800 	   assert(heurdata != NULL);
1801 	
1802 	   /* is the next block unsuitable or have we reached the end of the blocks? In those cases,
1803 	    * we mark all blocks of the current interval; we hence avoid to rerun on a subset of the current subproblem
1804 	    * in the next iteration; we achieve this by setting the overlap to 0.0, (its complement to 1.0)
1805 	    * such that all blocks are marked
1806 	    */
1807 	   if( blockendpos == decomphorizon->nblocks - 1 || ! decomphorizon->suitable[decomphorizon->blockindices[blockendpos + 1]] )
1808 	      overlapcomplement = 1.0;
1809 	   else
1810 	      overlapcomplement = 1.0 - heurdata->overlap;
1811 	
1812 	   /* count the total number of variables in the subproblem defining blocks */
1813 	   nvarsinterval = 0;
1814 	   for( b = blockstartpos; b <= blockendpos; ++b )
1815 	      nvarsinterval += decomphorizon->ndiscretevars[decomphorizon->blockindices[b]];
1816 	
1817 	   nvarsstartofinterval = 0;
1818 	   /* stamp the first blocks up to the desired overlap by the current incumbent solution */
1819 	   for( solstamppos = blockstartpos; solstamppos <= blockendpos; ++solstamppos )
1820 	   {
1821 	      decomphorizon->lastsolblock[decomphorizon->blockindices[solstamppos]] = sol;
1822 	      nvarsstartofinterval += decomphorizon->ndiscretevars[decomphorizon->blockindices[solstamppos]];
1823 	
1824 	      if( nvarsstartofinterval >= overlapcomplement * nvarsinterval )
1825 	         break;
1826 	   }
1827 	   decomphorizon->lastblockpos = solstamppos;
1828 	   SCIPdebugMsg(scip, "Blocks %d (label %d)-- %d (label %d) marked with incumbent solution\n",
1829 	      blockstartpos, decomphorizon->blocklabels[decomphorizon->blockindices[blockstartpos]],
1830 	      solstamppos, decomphorizon->blocklabels[decomphorizon->blockindices[solstamppos]]);
1831 	
1832 	   /* remember the blocks up to the found position as most recent overlap interval */
1833 	   decompHorizonSetOverlapInterval(decomphorizon, blockstartpos, solstamppos);
1834 	}
1835 	
1836 	/** determine the variable fixings based on a decomposition */
1837 	static
1838 	SCIP_RETCODE determineVariableFixingsDecomp(
1839 	   SCIP*                 scip,               /**< SCIP data structure */
1840 	   DECOMPHORIZON*        decomphorizon,      /**< decomposition horizon data structure */
1841 	   SCIP_VAR**            fixedvars,          /**< buffer to store variables that should be fixed */
1842 	   SCIP_Real*            fixedvals,          /**< buffer to store fixing values for fixed variables */
1843 	   int*                  nfixings,           /**< pointer to store the number of fixed variables */
1844 	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
1845 	   SCIP_Bool*            success             /**< used to store whether the creation of the subproblem worked */
1846 	   )
1847 	{
1848 	   SCIP_SOL* sol;
1849 	   SCIP_Bool hasnext;
1850 	   SCIP_Bool fixlinkvars;
1851 	   int currblockstart;
1852 	   int currblockend;
1853 	   int currblocklabel;
1854 	   int maxblocksize;
1855 	
1856 	   assert(scip != NULL);
1857 	   assert(decomphorizon != NULL);
1858 	
1859 	   sol = SCIPgetBestSol(scip);
1860 	
1861 	   /* initialize the decomposition horizon first for the current variables */
1862 	   if( ! decompHorizonIsInitialized(decomphorizon) )
1863 	   {
1864 	      SCIP_CALL( decompHorizonInitialize(scip, decomphorizon, heurdata) );
1865 	   }
1866 	
1867 	   maxblocksize = (int)((1.0 - heurdata->minfixingrate) * (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip))) - 1;
1868 	
1869 	   /* query the next suitable interval of blocks */
1870 	   hasnext = decompHorizonNext(scip, decomphorizon, heurdata, maxblocksize,
1871 	            &currblockstart, &currblockend, &currblocklabel, &fixlinkvars);
1872 	
1873 	   if( ! hasnext )
1874 	   {
1875 	      SCIPdebugMsg(scip, "Could not find a suitable interval that follows %d\n",
1876 	               decomphorizon->lastblockpos);
1877 	
1878 	      *success = FALSE;
1879 	   }
1880 	   else
1881 	   {
1882 	      /* fix all discrete/continuous variables that are not part of this interval */
1883 	      SCIP_VAR** vars;
1884 	      int v;
1885 	      int startblockposs[] = {fixlinkvars ? 0 : 1, currblockend + 1};
1886 	      int endblockposs[] = {currblockstart, decomphorizon->nblocks};
1887 	      int p;
1888 	      int b;
1889 	
1890 	      SCIPdebugMsg(scip, "Fix %s variables (%scluding linking variables) except blocks %d (label %d) -- %d (label %d)\n",
1891 	         heurdata->fixcontvars ? "all" : "discrete",
1892 	         fixlinkvars ? "in" : "ex",
1893 	         currblockstart, decomphorizon->blocklabels[decomphorizon->blockindices[currblockstart]],
1894 	         currblockend, decomphorizon->blocklabels[decomphorizon->blockindices[currblockend]]);
1895 	
1896 	      vars = decomphorizonGetVars(decomphorizon);
1897 	
1898 	      /* iterate over the two blocks left and right of the selected consecutive interval and fix all variables
1899 	       *
1900 	       * 0, ... b, ... ,[currblockstart, ..., currblockend], currblockend + 1, ..., decomphorizon->nblocks - 1
1901 	       */
1902 	      for( p = 0; p < 2; ++p )
1903 	      {
1904 	         /* iterate over all blocks and fix those outside of the blocks interval that defines the current subproblem */
1905 	         for( b = startblockposs[p]; b < endblockposs[p]; ++b )
1906 	         {
1907 	            int blockind = decomphorizon->blockindices[b];
1908 	            int varstartpos = blockind == 0 ? 0 : decomphorizon->varblockend[blockind - 1];
1909 	            int varendpos = decomphorizon->varblockend[blockind];
1910 	
1911 	            /* fix variables inside of this block */
1912 	            for( v = varstartpos; v < varendpos; ++v )
1913 	            {
1914 	               SCIP_VAR* var = vars[v];
1915 	
1916 	               if( heurdata->fixcontvars || SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS )
1917 	               {
1918 	                  SCIP_Real fixval;
1919 	
1920 	                  fixval = getFixVal(scip, sol, var);
1921 	
1922 	                  /* store variable and value of this fixing */
1923 	                  if( !SCIPisInfinity(scip, REALABS(fixval)) )
1924 	                  {
1925 	                     fixedvars[*nfixings] = var;
1926 	                     fixedvals[*nfixings] = fixval;
1927 	                     ++(*nfixings);
1928 	                  }
1929 	               }
1930 	            }
1931 	         }
1932 	      }
1933 	
1934 	      *success = checkFixingrate(scip, heurdata, *nfixings);
1935 	
1936 	      decompHorizonMarkInterval(scip, decomphorizon, heurdata, sol, currblockstart, currblockend);
1937 	   }
1938 	
1939 	   return SCIP_OKAY; /*lint !e438*/
1940 	}
1941 	
1942 	/** choose a decomposition from the store or return NULL if none exists/no decomposition was suitable */
1943 	static
1944 	SCIP_DECOMP* chooseDecomp(
1945 	   SCIP*                 scip                /**< SCIP data structure */
1946 	   )
1947 	{
1948 	   SCIP_DECOMP** decomps;
1949 	   int ndecomps;
1950 	   int currdecomp;
1951 	
1952 	   /* TODO coming soon: better selection than last nontrivial decomposition that has been input */
1953 	   SCIPgetDecomps(scip, &decomps, &ndecomps, FALSE);
1954 	   currdecomp = ndecomps;
1955 	
1956 	   while( --currdecomp >= 0 )
1957 	   {
1958 	      if( SCIPdecompGetNBlocks(decomps[currdecomp]) > 0 )
1959 	         return decomps[currdecomp];
1960 	   }
1961 	
1962 	   return NULL;
1963 	}
1964 	
1965 	/** determines the graph-induced variable fixings */
1966 	static
1967 	SCIP_RETCODE determineVariableFixings(
1968 	   SCIP*                 scip,               /**< original SCIP data structure */
1969 	   SCIP_VAR**            fixedvars,          /**< buffer to store variables that should be fixed */
1970 	   SCIP_Real*            fixedvals,          /**< buffer to store fixing values for fixed variables */
1971 	   int*                  nfixings,           /**< pointer to store the number of fixed variables */
1972 	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
1973 	   ROLLINGHORIZON*       rollinghorizon,     /**< rolling horizon data structure to save relevant information, or NULL if not needed */
1974 	   DECOMPHORIZON*        decomphorizon,      /**< decomposition horizon data structure, or NULL */
1975 	   SCIP_Bool*            success             /**< used to store whether the creation of the subproblem worked */
1976 	   )
1977 	{
1978 	   SCIP_VAR** vars;
1979 	   SCIP_SOL* sol;
1980 	   int* distances;
1981 	   SCIP_VGRAPH* vargraph;
1982 	   SCIP_VAR* selvar;
1983 	   int nvars;
1984 	   int nbinvars;
1985 	   int nintvars;
1986 	
1987 	   int selvarmaxdistance;
1988 	
1989 	   assert(fixedvars != NULL);
1990 	   assert(fixedvals != NULL);
1991 	   assert(nfixings != NULL);
1992 	
1993 	   *success = TRUE;
1994 	   *nfixings = 0;
1995 	   selvarmaxdistance = 0;
1996 	   sol = SCIPgetBestSol(scip);
1997 	   assert(sol != NULL);
1998 	
1999 	   /* determine the variable fixings based on latest user decomposition */
2000 	   if( decomphorizon != NULL )
2001 	   {
2002 	      SCIP_CALL( determineVariableFixingsDecomp(scip, decomphorizon, fixedvars, fixedvals, nfixings, heurdata, success) );
2003 	
2004 	      /* do not use fallback strategy if user parameter does not allow it */
2005 	      if( *success || ! heurdata->useselfallback )
2006 	         return SCIP_OKAY;
2007 	   }
2008 	
2009 	   /* get required data of the source problem */
2010 	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
2011 	   /* get the saved variable graph, or create a new one */
2012 	   if( rollinghorizon != NULL )
2013 	   {
2014 	      if( rollinghorizon->niterations == 0 )
2015 	      {
2016 	         /* create variable graph */
2017 	         SCIPdebugMsg(scip, "Creating variable constraint graph\n");
2018 	         SCIP_CALL( SCIPvariableGraphCreate(scip, &rollinghorizon->variablegraph, heurdata->relaxdenseconss, 1.0 - heurdata->minfixingrate, &heurdata->nrelaxedconstraints) );
2019 	      }
2020 	      else
2021 	         assert(rollinghorizon->variablegraph != NULL);
2022 	
2023 	      vargraph = rollinghorizon->variablegraph;
2024 	   }
2025 	   else
2026 	   {
2027 	      /* create variable graph */
2028 	      SCIPdebugMsg(scip, "Creating variable constraint graph\n");
2029 	      SCIP_CALL( SCIPvariableGraphCreate(scip, &vargraph, heurdata->relaxdenseconss, 1.0 - heurdata->minfixingrate, &heurdata->nrelaxedconstraints) );
2030 	   }
2031 	
2032 	   /* allocate buffer memory to hold distances */
2033 	   SCIP_CALL( SCIPallocBufferArray(scip, &distances, nvars) );
2034 	
2035 	   selvar = NULL;
2036 	
2037 	   /* in the first iteration of the rolling horizon approach, we select an initial variable */
2038 	   if( rollinghorizon == NULL || rollinghorizon->niterations == 0 )
2039 	   {
2040 	      SCIP_Bool userandomselection = TRUE;
2041 	
2042 	      /* choose the initial variable based on a user decomposition, if available */
2043 	      if( heurdata->usedecomprollhorizon )
2044 	      {
2045 	         SCIP_DECOMP* decomp = chooseDecomp(scip);
2046 	         if( decomp != NULL )
2047 	         {
2048 	            SCIP_CALL( selectInitialVariableDecomposition(scip, heurdata, decomp, vargraph,
2049 	                  distances, &selvar, &selvarmaxdistance) );
2050 	
2051 	            userandomselection = (selvar == NULL && heurdata->useselfallback);
2052 	         }
2053 	      }
2054 	
2055 	      assert(selvar == NULL || !userandomselection);
2056 	      /* use random variable selection as fallback strategy, if no user decomposition is available, or the
2057 	       * heuristic should not use decomposition
2058 	       */
2059 	      if( userandomselection )
2060 	      {
2061 	         SCIP_CALL( selectInitialVariableRandomly(scip, heurdata, vargraph, distances, &selvar, &selvarmaxdistance) );
2062 	      }
2063 	
2064 	      /* collect and save the distances in the rolling horizon data structure */
2065 	      if( selvar != NULL && rollinghorizon != NULL )
2066 	      {
2067 	         /* collect distances in the variable graph of all variables to the selected variable */
2068 	         SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, vargraph, &selvar, 1, distances, INT_MAX, INT_MAX, INT_MAX) );
2069 	         rollingHorizonStoreDistances(rollinghorizon, distances);
2070 	         rollinghorizon->lastmaxdistance = selvarmaxdistance;
2071 	      }
2072 	   }
2073 	   else
2074 	   {
2075 	      /* select the next variable, if variables are left */
2076 	      SCIP_CALL( selectNextVariable(scip, heurdata, rollinghorizon, distances, &selvar, &selvarmaxdistance) );
2077 	   }
2078 	
2079 	   assert(selvar == NULL || selvarmaxdistance > 0);
2080 	   if( selvar == NULL )
2081 	   {
2082 	      *success = FALSE;
2083 	   }
2084 	   else
2085 	   {
2086 	      SCIPdebugMsg(scip, "Selected variable <%s> as central variable for a <%d>-neighborhood\n",
2087 	         SCIPvarGetName(selvar), selvarmaxdistance);
2088 	
2089 	      /* fix variables that are not in the neighborhood around the selected variable */
2090 	      SCIP_CALL( fixNonNeighborhoodVariables(scip, heurdata, rollinghorizon, sol, vars, fixedvars, fixedvals, distances,
2091 	            selvarmaxdistance, nfixings) );
2092 	
2093 	     *success = checkFixingrate(scip, heurdata, *nfixings);
2094 	   }
2095 	
2096 	   SCIPfreeBufferArray(scip, &distances);
2097 	   if( rollinghorizon == NULL )
2098 	      SCIPvariableGraphFree(scip, &vargraph);
2099 	
2100 	   return SCIP_OKAY;
2101 	}
2102 	
2103 	/** set sub-SCIP solving limits */
2104 	static
2105 	SCIP_RETCODE setLimits(
2106 	   SCIP*                 sourcescip,         /**< SCIP data structure */
2107 	   SCIP*                 subscip,            /**< SCIP data structure */
2108 	   SOLVELIMITS*          solvelimits         /**< pointer to solving limits data structure */
2109 	   )
2110 	{
2111 	   assert(sourcescip != NULL);
2112 	   assert(subscip != NULL);
2113 	   assert(solvelimits != NULL);
2114 	
2115 	   SCIP_CALL( SCIPcopyLimits(sourcescip, subscip) );
2116 	
2117 	   SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", solvelimits->nodelimit) );
2118 	   SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", solvelimits->stallnodelimit) );
2119 	
2120 	   /* safe long running times caused by lack of dual convergence */
2121 	   SCIP_CALL( SCIPsetRealParam(subscip, "limits/gap", 0.01) );
2122 	
2123 	   return SCIP_OKAY;
2124 	}
2125 	
2126 	/** set up the sub-SCIP */
2127 	static
2128 	SCIP_RETCODE setupSubScip(
2129 	   SCIP*                 scip,               /**< SCIP data structure */
2130 	   SCIP*                 subscip,            /**< sub-SCIP data structure */
2131 	   SOLVELIMITS*          solvelimits,        /**< pointer to solving limits data structure */
2132 	   SCIP_HEUR*            heur                /**< this heuristic */
2133 	   )
2134 	{
2135 	   SCIP_HEURDATA* heurdata;
2136 	   SCIP_Real cutoff;
2137 	   SCIP_Real upperbound;
2138 	
2139 	   heurdata = SCIPheurGetData(heur);
2140 	
2141 	   /* do not abort subproblem on CTRL-C */
2142 	   SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
2143 	
2144 	   /* disable output to console */
2145 	   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
2146 	
2147 	   /* disable statistic timing inside sub SCIP */
2148 	   SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
2149 	
2150 	   SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->bestsollimit) );
2151 	
2152 	   /* forbid recursive call of heuristics and separators solving subMIPs */
2153 	   SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
2154 	
2155 	   /* disable cutting plane separation */
2156 	   SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
2157 	
2158 	   /* disable expensive presolving */
2159 	   SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
2160 	
2161 	   /* use best estimate node selection */
2162 	   if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
2163 	   {
2164 	      SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
2165 	   }
2166 	
2167 	   /* use inference branching */
2168 	   if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
2169 	   {
2170 	      SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
2171 	   }
2172 	
2173 	   /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */
2174 	   if( !SCIPisParamFixed(subscip, "conflict/enable") )
2175 	   {
2176 	      SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) );
2177 	   }
2178 	   if( !SCIPisParamFixed(subscip, "conflict/useboundlp") )
2179 	   {
2180 	      SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') );
2181 	   }
2182 	   if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") )
2183 	   {
2184 	      SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) );
2185 	   }
2186 	
2187 	   /* speed up sub-SCIP by not checking dual LP feasibility */
2188 	   SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
2189 	
2190 	   /* add an objective cutoff */
2191 	   assert( !SCIPisInfinity(scip, SCIPgetUpperbound(scip)) );
2192 	
2193 	   upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
2194 	   if( !SCIPisInfinity(scip, -1.0 * SCIPgetLowerbound(scip)) )
2195 	   {
2196 	      cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip)
2197 	                      + heurdata->minimprove * SCIPgetLowerbound(scip);
2198 	   }
2199 	   else
2200 	   {
2201 	      if( SCIPgetUpperbound(scip) >= 0 )
2202 	         cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip);
2203 	      else
2204 	         cutoff = (1 + heurdata->minimprove) * SCIPgetUpperbound(scip);
2205 	   }
2206 	   cutoff = MIN(upperbound, cutoff);
2207 	   SCIP_CALL(SCIPsetObjlimit(subscip, cutoff));
2208 	
2209 	   /* set solve limits for sub-SCIP */
2210 	   SCIP_CALL( setLimits(scip, subscip, solvelimits) );
2211 	
2212 	   return SCIP_OKAY;
2213 	}
2214 	
2215 	/** determine limits for a sub-SCIP */
2216 	static
2217 	SCIP_RETCODE determineLimits(
2218 	   SCIP*                 scip,               /**< SCIP data structure */
2219 	   SCIP_HEUR*            heur,               /**< this heuristic */
2220 	   SOLVELIMITS*          solvelimits,        /**< pointer to solving limits data structure */
2221 	   SCIP_Bool*            runagain            /**< can we solve another sub-SCIP with these limits */
2222 	   )
2223 	{
2224 	   SCIP_HEURDATA* heurdata;
2225 	   SCIP_Real maxnnodesr;
2226 	   SCIP_Real confidence;
2227 	   SCIP_Longint maxnnodes;
2228 	   SCIP_Bool copylimits;
2229 	
2230 	   assert(scip != NULL);
2231 	   assert(heur != NULL);
2232 	   assert(solvelimits != NULL);
2233 	   assert(runagain != NULL);
2234 	
2235 	   heurdata = SCIPheurGetData(heur);
2236 	
2237 	   /* check whether there is enough time and memory left */
2238 	   SCIP_CALL( SCIPcheckCopyLimits(scip, &copylimits) );
2239 	
2240 	   if( ! copylimits )
2241 	      *runagain = FALSE;
2242 	
2243 	   /* calculate the maximal number of branching nodes until heuristic is aborted */
2244 	   maxnnodesr = heurdata->nodesquot * SCIPgetNNodes(scip);
2245 	
2246 	   /* reward gins if it succeeded often, count the setup costs for the sub-MIP as 100 nodes */
2247 	   confidence = (SCIP_Real)SCIPheurGetNCalls(heur);
2248 	   confidence = confidence / (confidence + 5.0);
2249 	   maxnnodesr *= 1.0 + confidence * 2.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(heurdata->nsubmips + 1.0);
2250 	   maxnnodes = (SCIP_Longint)(maxnnodesr - 100.0 * heurdata->nsubmips);
2251 	   maxnnodes += heurdata->nodesofs;
2252 	
2253 	   /* determine the node limit for the current process */
2254 	   solvelimits->nodelimit = maxnnodes - heurdata->usednodes;
2255 	   solvelimits->nodelimit = MIN(solvelimits->nodelimit, heurdata->maxnodes);
2256 	
2257 	   /* check whether we have enough nodes left to call subproblem solving */
2258 	   if( solvelimits->nodelimit < heurdata->targetnodes )
2259 	      *runagain = FALSE;
2260 	
2261 	   solvelimits->stallnodelimit = heurdata->targetnodes;
2262 	
2263 	   return SCIP_OKAY;
2264 	}
2265 	
2266 	/** updates heurdata after a run of GINS */
2267 	static
2268 	void updateFailureStatistic(
2269 	   SCIP*                 scip,               /**< original SCIP data structure */
2270 	   SCIP_HEURDATA*        heurdata            /**< primal heuristic data */
2271 	   )
2272 	{
2273 	   /* increase number of failures, calculate next node at which GINS should be called and update actual solutions */
2274 	   heurdata->nfailures++;
2275 	   heurdata->nextnodenumber = (heurdata->nfailures <= 25
2276 	      ? SCIPgetNNodes(scip) + 100*(2LL << heurdata->nfailures) /*lint !e703*/
2277 	      : SCIP_LONGINT_MAX);
2278 	}
2279 	
2280 	
2281 	/*
2282 	 * Callback methods of primal heuristic
2283 	 */
2284 	
2285 	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
2286 	static
2287 	SCIP_DECL_HEURCOPY(heurCopyGins)
2288 	{  /*lint --e{715}*/
2289 	   assert(scip != NULL);
2290 	   assert(heur != NULL);
2291 	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
2292 	
2293 	   /* call inclusion method of primal heuristic */
2294 	   SCIP_CALL( SCIPincludeHeurGins(scip) );
2295 	
2296 	   return SCIP_OKAY;
2297 	}
2298 	
2299 	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
2300 	static
2301 	SCIP_DECL_HEURFREE(heurFreeGins)
2302 	{  /*lint --e{715}*/
2303 	   SCIP_HEURDATA* heurdata;
2304 	
2305 	   assert(heur != NULL);
2306 	   assert(scip != NULL);
2307 	
2308 	   /* get heuristic data */
2309 	   heurdata = SCIPheurGetData(heur);
2310 	   assert(heurdata != NULL);
2311 	
2312 	   /* free heuristic data */
2313 	   SCIPfreeBlockMemory(scip, &heurdata);
2314 	   SCIPheurSetData(heur, NULL);
2315 	
2316 	   return SCIP_OKAY;
2317 	}
2318 	
2319 	/** initialization method of primal heuristic (called after problem was transformed) */
2320 	static
2321 	SCIP_DECL_HEURINIT(heurInitGins)
2322 	{  /*lint --e{715}*/
2323 	   SCIP_HEURDATA* heurdata;
2324 	
2325 	   assert(heur != NULL);
2326 	   assert(scip != NULL);
2327 	
2328 	   /* get heuristic's data */
2329 	   heurdata = SCIPheurGetData(heur);
2330 	   assert(heurdata != NULL);
2331 	   assert(heurdata->randnumgen == NULL);
2332 	
2333 	   /* initialize data */
2334 	   heurdata->usednodes = 0;
2335 	   SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE) );
2336 	   heurdata->sumdiscneighborhoodvars = heurdata->sumneighborhoodvars = 0;
2337 	   heurdata->nneighborhoods = 0;
2338 	   heurdata->maxseendistance = 0;
2339 	   heurdata->nsubmips = 0;
2340 	   heurdata->nfailures = 0;
2341 	   heurdata->nextnodenumber = 0;
2342 	   heurdata->lastinitsol = NULL;
2343 	   heurdata->allblocksunsuitable = FALSE;
2344 	   heurdata->taboolist = NULL;
2345 	   heurdata->targetnodes = heurdata->minnodes;
2346 	
2347 	   return SCIP_OKAY;
2348 	}
2349 	
2350 	/** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
2351 	static
2352 	SCIP_DECL_HEUREXITSOL(heurExitsolGins)
2353 	{  /*lint --e{715}*/
2354 	   SCIP_HEURDATA* heurdata;
2355 	
2356 	   assert(heur != NULL);
2357 	   assert(scip != NULL);
2358 	
2359 	   /* get heuristic data */
2360 	   heurdata = SCIPheurGetData(heur);
2361 	   assert(heurdata != NULL);
2362 	
2363 	   /* it is likely that the decomposition information changes between runs, we recreate the decomposition horizon */
2364 	   decompHorizonFree(scip, &heurdata->decomphorizon);
2365 	   assert(heurdata->decomphorizon == NULL);
2366 	
2367 	   return SCIP_OKAY;
2368 	}
2369 	
2370 	/** initialization method of primal heuristic (called after problem was transformed) */
2371 	static
2372 	SCIP_DECL_HEUREXIT(heurExitGins)
2373 	{  /*lint --e{715}*/
2374 	   SCIP_HEURDATA* heurdata;
2375 	
2376 	   assert(heur != NULL);
2377 	   assert(scip != NULL);
2378 	
2379 	   /* get heuristic's data */
2380 	   heurdata = SCIPheurGetData(heur);
2381 	   assert(heurdata != NULL);
2382 	
2383 	   SCIPstatistic(
2384 	      SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Gins: Avg Neighborhood size: %.1f Avg. discrete neighboorhood vars: %.1f\n",
2385 	            heurdataAvgNeighborhoodSize(heurdata), heurdataAvgDiscreteNeighborhoodSize(heurdata));
2386 	      SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Gins: Max seen distance %d\n", heurdata->maxseendistance);
2387 	      printHistogram(scip, heurdata->consvarshist, "Constraint density histogram");
2388 	      printHistogram(scip, heurdata->conscontvarshist, "Constraint continuous density histogram");
2389 	      printHistogram(scip, heurdata->consdiscvarshist, "Constraint discrete density histogram");
2390 	      )
2391 	
2392 	   /* free some data structures that must be reset for a new problem */
2393 	   freeTabooList(scip, &heurdata->taboolist);
2394 	   SCIPfreeRandom(scip, &heurdata->randnumgen);
2395 	
2396 	   heurdata->taboolist = NULL;
2397 	   heurdata->randnumgen = NULL;
2398 	
2399 	   return SCIP_OKAY;
2400 	}
2401 	
2402 	/** execution method of primal heuristic */
2403 	static
2404 	SCIP_DECL_HEUREXEC(heurExecGins)
2405 	{  /*lint --e{715}*/
2406 	   SCIP_HEURDATA* heurdata;                  /* heuristic's data */
2407 	   SCIP* subscip;                            /* the subproblem created by gins */
2408 	   SCIP_VAR** vars;                          /* original problem's variables */
2409 	   SCIP_VAR** subvars;                       /* subproblem's variables */
2410 	   SCIP_VAR** fixedvars;
2411 	   SCIP_Real* fixedvals;
2412 	   ROLLINGHORIZON* rollinghorizon;           /* data structure for rolling horizon approach */
2413 	   DECOMPHORIZON* decomphorizon;             /* data structure for processing multiple blocks of a decomposition */
2414 	   SCIP_DECOMP* decomp;
2415 	   SCIP_HASHMAP* varmapfw;                   /* mapping of SCIP variables to sub-SCIP variables */
2416 	
2417 	   int nvars;                                /* number of original problem's variables */
2418 	   int i;
2419 	   int nfixedvars;
2420 	   SOLVELIMITS solvelimits;
2421 	   SCIP_Bool runagain;
2422 	
2423 	   SCIP_Bool success;
2424 	
2425 	   assert(heur != NULL);
2426 	   assert(scip != NULL);
2427 	   assert(result != NULL);
2428 	
2429 	   /* get heuristic's data */
2430 	   heurdata = SCIPheurGetData(heur);
2431 	   assert(heurdata != NULL);
2432 	
2433 	   *result = SCIP_DELAYED;
2434 	
2435 	   /* only call heuristic, if feasible solution is available */
2436 	   if( SCIPgetNSols(scip) <= 0 )
2437 	      return SCIP_OKAY;
2438 	
2439 	   /* in case of many unsuccessful calls, the nextnodenumber is increased to prevent us from running too often  */
2440 	   if( SCIPgetNNodes(scip) < heurdata->nextnodenumber )
2441 	      return SCIP_OKAY;
2442 	
2443 	   /* only call heuristic, if the best solution comes from transformed problem */
2444 	   assert(SCIPgetBestSol(scip) != NULL);
2445 	   if( SCIPsolIsOriginal(SCIPgetBestSol(scip)) )
2446 	      return SCIP_OKAY;
2447 	
2448 	   /* only call heuristic, if enough nodes were processed since last incumbent */
2449 	   if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip,SCIPgetBestSol(scip)) < heurdata->nwaitingnodes )
2450 	      return SCIP_OKAY;
2451 	
2452 	   *result = SCIP_DIDNOTRUN;
2453 	
2454 	   /* only call heuristic, if discrete variables are present */
2455 	   if( SCIPgetNBinVars(scip) == 0 && SCIPgetNIntVars(scip) == 0 )
2456 	      return SCIP_OKAY;
2457 	
2458 	   if( SCIPisStopped(scip) )
2459 	      return SCIP_OKAY;
2460 	
2461 	   runagain = TRUE;
2462 	
2463 	   /* determine solving limits for the sub-SCIP for the first time */
2464 	   SCIP_CALL( determineLimits(scip, heur, &solvelimits, &runagain) );
2465 	
2466 	   if( ! runagain )
2467 	      return SCIP_OKAY;
2468 	
2469 	   *result = SCIP_DIDNOTFIND;
2470 	
2471 	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2472 	   SCIP_CALL( SCIPallocBufferArray(scip, &fixedvars, nvars) );
2473 	   SCIP_CALL( SCIPallocBufferArray(scip, &fixedvals, nvars) );
2474 	
2475 	   rollinghorizon = NULL;
2476 	   decomp = chooseDecomp(scip);
2477 	   if( decomp != NULL && heurdata->usedecomp && heurdata->decomphorizon == NULL )
2478 	   {
2479 	      SCIP_CALL( decompHorizonCreate(scip, &heurdata->decomphorizon, decomp) );
2480 	   }
2481 	   decomphorizon = heurdata->decomphorizon;
2482 	   /* only create a rolling horizon data structure if we need it */
2483 	   if( decomphorizon == NULL && heurdata->userollinghorizon )
2484 	   {
2485 	      SCIP_CALL( rollingHorizonCreate(scip, &rollinghorizon) );
2486 	   }
2487 	
2488 	   do
2489 	   {
2490 	      SCIP_SOL* oldincumbent;
2491 	      SCIP_SOL* newincumbent;
2492 	
2493 	      /* create a new problem, by fixing all variables except for a small neighborhood */
2494 	      SCIP_CALL( determineVariableFixings(scip, fixedvars, fixedvals, &nfixedvars, heurdata, rollinghorizon, decomphorizon, &success) );
2495 	
2496 	      /* terminate if it was not possible to create the subproblem */
2497 	      if( !success )
2498 	      {
2499 	         SCIPdebugMsg(scip, "Could not create the subproblem -> skip call\n");
2500 	
2501 	         /* do not count this as a call to the heuristic */
2502 	         *result = SCIP_DIDNOTRUN;
2503 	
2504 	         /* count this as a failure and increase the number of waiting nodes until the next call */
2505 	         updateFailureStatistic(scip, heurdata);
2506 	         goto TERMINATE;
2507 	      }
2508 	
2509 	      /* initializing the subproblem */
2510 	      SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
2511 	      SCIP_CALL( SCIPcreate(&subscip) );
2512 	      ++heurdata->nsubmips;
2513 	
2514 	      /* create the variable mapping hash map */
2515 	      SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
2516 	
2517 	      /* create a problem copy as sub SCIP */
2518 	      SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "gins", fixedvars, fixedvals, nfixedvars,
2519 	            heurdata->uselprows, heurdata->copycuts, &success, NULL) );
2520 	
2521 	      for( i = 0; i < nvars; i++ )
2522 	         subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
2523 	
2524 	      /* free hash map */
2525 	      SCIPhashmapFree(&varmapfw);
2526 	
2527 	      /* set up limits for the subproblem */
2528 	      SCIP_CALL( setupSubScip(scip, subscip, &solvelimits, heur) );
2529 	
2530 	      /* solve the subproblem */
2531 	      SCIPdebugMsg(scip, "Solve Gins subMIP\n");
2532 	
2533 	      /* Errors in solving the subproblem should not kill the overall solving process
2534 	       * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
2535 	       */
2536 	      SCIP_CALL_ABORT( SCIPsolve(subscip) );
2537 	
2538 	      SCIPdebugMsg(scip, "GINS subscip stats: %.2f sec., %" SCIP_LONGINT_FORMAT " nodes, status:%d\n",
2539 	         SCIPgetSolvingTime(subscip), SCIPgetNTotalNodes(subscip), SCIPgetStatus(subscip));
2540 	
2541 	      /* increase target nodes if a (stall) node limit was reached; this will immediately affect the next run */
2542 	      if( SCIPgetStatus(subscip) == SCIP_STATUS_NODELIMIT || SCIPgetStatus(subscip) == SCIP_STATUS_STALLNODELIMIT )
2543 	      {
2544 	         heurdata->targetnodes = (SCIP_Longint)(1.05 * heurdata->targetnodes) + 5L;
2545 	
2546 	         /* but not too far */
2547 	         heurdata->targetnodes = MIN(heurdata->targetnodes, heurdata->maxnodes / 2);
2548 	
2549 	         SCIPdebugMsg(scip, "New target nodes after stalling: %" SCIP_LONGINT_FORMAT "\n", heurdata->targetnodes);
2550 	      }
2551 	
2552 	      /* transfer variable statistics from sub-SCIP */
2553 	      SCIP_CALL( SCIPmergeVariableStatistics(subscip, scip, subvars, vars, nvars) );
2554 	
2555 	      heurdata->usednodes += SCIPgetNNodes(subscip);
2556 	
2557 	      success = FALSE;
2558 	      /* check, whether a solution was found;
2559 	       * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
2560 	       */
2561 	      oldincumbent = SCIPgetBestSol(scip);
2562 	
2563 	      SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, &success, NULL) );
2564 	      if( success )
2565 	         *result = SCIP_FOUNDSOL;
2566 	
2567 	      newincumbent = SCIPgetBestSol(scip);
2568 	
2569 	      /* free subproblem */
2570 	      SCIPfreeBufferArray(scip, &subvars);
2571 	      SCIP_CALL( SCIPfree(&subscip) );
2572 	
2573 	      /* check if we want to run another rolling horizon iteration */
2574 	      runagain = success && (newincumbent != oldincumbent) && heurdata->userollinghorizon;
2575 	      if( runagain )
2576 	      {
2577 	         assert(rollinghorizon != NULL || decomphorizon != NULL);
2578 	         SCIP_CALL( determineLimits(scip, heur, &solvelimits, &runagain ) );
2579 	
2580 	         if( rollinghorizon != NULL )
2581 	            runagain = runagain && rollingHorizonRunAgain(scip, rollinghorizon, heurdata) && (success);
2582 	         else if( decomphorizon != NULL )
2583 	            runagain = runagain && decompHorizonRunAgain(scip, decomphorizon);
2584 	      }
2585 	   }
2586 	   while( runagain );
2587 	
2588 	   /* delay the heuristic in case it was not successful */
2589 	   if( *result != SCIP_FOUNDSOL )
2590 	      updateFailureStatistic(scip, heurdata);
2591 	
2592 	TERMINATE:
2593 	
2594 	   /* only free the rolling horizon data structure if we need to keep it */
2595 	   if( heurdata->userollinghorizon )
2596 	   {
2597 	      rollingHorizonFree(scip, &rollinghorizon);
2598 	   }
2599 	
2600 	   SCIPfreeBufferArray(scip, &fixedvals);
2601 	   SCIPfreeBufferArray(scip, &fixedvars);
2602 	
2603 	   return SCIP_OKAY;
2604 	}
2605 	
2606 	/*
2607 	 * primal heuristic specific interface methods
2608 	 */
2609 	
2610 	/** creates the gins primal heuristic and includes it in SCIP */
2611 	SCIP_RETCODE SCIPincludeHeurGins(
2612 	   SCIP*                 scip                /**< SCIP data structure */
2613 	   )
2614 	{
2615 	   SCIP_HEURDATA* heurdata;
2616 	   SCIP_HEUR* heur;
2617 	
2618 	   /* create Gins primal heuristic data */
2619 	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
2620 	   heurdata->randnumgen = NULL;
2621 	   heurdata->decomphorizon = NULL;
2622 	
2623 	   /* include primal heuristic */
2624 	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
2625 	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
2626 	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecGins, heurdata) );
2627 	
2628 	   assert(heur != NULL);
2629 	
2630 	   /* set non-NULL pointers to callback methods */
2631 	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyGins) );
2632 	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeGins) );
2633 	   SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitGins) );
2634 	   SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitGins) );
2635 	   SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolGins) );
2636 	
2637 	   /* add gins primal heuristic parameters */
2638 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
2639 	         "number of nodes added to the contingent of the total nodes",
2640 	         &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0, INT_MAX, NULL, NULL) );
2641 	
2642 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
2643 	         "maximum number of nodes to regard in the subproblem",
2644 	         &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0, INT_MAX, NULL, NULL) );
2645 	
2646 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/minnodes",
2647 	         "minimum number of nodes required to start the subproblem",
2648 	         &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0, INT_MAX, NULL, NULL) );
2649 	
2650 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nwaitingnodes",
2651 	         "number of nodes without incumbent change that heuristic should wait",
2652 	         &heurdata->nwaitingnodes, TRUE, DEFAULT_NWAITINGNODES, 0, INT_MAX, NULL, NULL) );
2653 	
2654 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
2655 	         "contingent of sub problem nodes in relation to the number of nodes of the original problem",
2656 	         &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
2657 	
2658 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate",
2659 	         "percentage of integer variables that have to be fixed",
2660 	         &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, SCIPsumepsilon(scip), 1.0-SCIPsumepsilon(scip), NULL, NULL) );
2661 	
2662 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
2663 	         "factor by which " HEUR_NAME " should at least improve the incumbent",
2664 	         &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
2665 	
2666 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows",
2667 	         "should subproblem be created out of the rows in the LP rows?",
2668 	         &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
2669 	
2670 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
2671 	         "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
2672 	         &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
2673 	
2674 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/fixcontvars",
2675 	         "should continuous variables outside the neighborhoods be fixed?",
2676 	         &heurdata->fixcontvars, TRUE, DEFAULT_FIXCONTVARS, NULL, NULL) );
2677 	
2678 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/bestsollimit",
2679 	         "limit on number of improving incumbent solutions in sub-CIP",
2680 	         &heurdata->bestsollimit, FALSE, DEFAULT_BESTSOLLIMIT, -1, INT_MAX, NULL, NULL) );
2681 	
2682 	   SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxdistance",
2683 	         "maximum distance to selected variable to enter the subproblem, or -1 to select the distance "
2684 	         "that best approximates the minimum fixing rate from below",
2685 	         &heurdata->maxdistance, FALSE, DEFAULT_MAXDISTANCE, -1, INT_MAX, NULL, NULL) );
2686 	
2687 	   SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/potential",
2688 	         "the reference point to compute the neighborhood potential: (r)oot, (l)ocal lp, or (p)seudo solution",
2689 	         &heurdata->potential, TRUE, DEFAULT_POTENTIAL, "lpr", NULL, NULL) );
2690 	
2691 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/userollinghorizon",
2692 	         "should the heuristic solve a sequence of sub-MIP's around the first selected variable",
2693 	         &heurdata->userollinghorizon, TRUE, DEFAULT_USEROLLINGHORIZON, NULL, NULL) );
2694 	
2695 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/relaxdenseconss",
2696 	         "should dense constraints (at least as dense as 1 - minfixingrate) be ignored by connectivity graph?",
2697 	         &heurdata->relaxdenseconss, TRUE, DEFAULT_RELAXDENSECONSS, NULL, NULL) );
2698 	
2699 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/rollhorizonlimfac",
2700 	         "limiting percentage for variables already used in sub-SCIPs to terminate rolling horizon approach",
2701 	         &heurdata->rollhorizonlimfac, TRUE, DEFAULT_ROLLHORIZONLIMFAC, 0.0, 1.0, NULL, NULL) );
2702 	
2703 	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/overlap",
2704 	         "overlap of blocks between runs - 0.0: no overlap, 1.0: shift by only 1 block",
2705 	         &heurdata->overlap, TRUE, DEFAULT_OVERLAP, 0.0, 1.0, NULL, NULL) );
2706 	
2707 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usedecomp",
2708 	         "should user decompositions be considered, if available?",
2709 	         &heurdata->usedecomp, TRUE, DEFAULT_USEDECOMP, NULL, NULL) );
2710 	
2711 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usedecomprollhorizon",
2712 	         "should user decompositions be considered for initial selection in rolling horizon, if available?",
2713 	         &heurdata->usedecomprollhorizon, TRUE, DEFAULT_USEDECOMPROLLHORIZON, NULL, NULL) );
2714 	
2715 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useselfallback",
2716 	         "should random initial variable selection be used if decomposition was not successful?",
2717 	         &heurdata->useselfallback, TRUE, DEFAULT_USESELFALLBACK, NULL, NULL) );
2718 	
2719 	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/consecutiveblocks",
2720 	         "should blocks be treated consecutively (sorted by ascending label?)",
2721 	         &heurdata->consecutiveblocks, TRUE, DEFAULT_CONSECUTIVEBLOCKS, NULL, NULL) );
2722 	
2723 	   return SCIP_OKAY;
2724 	}
2725