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.c
26   	 * @ingroup OTHER_CFILES
27   	 * @brief  methods for primal heuristics
28   	 * @author Tobias Achterberg
29   	 * @author Timo Berthold
30   	 */
31   	
32   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33   	
34   	#include <assert.h>
35   	#include <string.h>
36   	
37   	#include "scip/def.h"
38   	#include "scip/set.h"
39   	#include "scip/clock.h"
40   	#include "scip/paramset.h"
41   	#include "scip/primal.h"
42   	#include "scip/scip.h"
43   	#include "scip/heur.h"
44   	#include "scip/pub_message.h"
45   	#include "scip/pub_misc.h"
46   	#include "scip/misc.h"
47   	
48   	#include "scip/struct_heur.h"
49   	
50   	/** compares two heuristics w.r.t. to their delay positions and priorities */
51   	SCIP_DECL_SORTPTRCOMP(SCIPheurComp)
52   	{  /*lint --e{715}*/
53   	   SCIP_HEUR* heur1 = (SCIP_HEUR*)elem1;
54   	   SCIP_HEUR* heur2 = (SCIP_HEUR*)elem2;
55   	
56   	   assert(heur1 != NULL);
57   	   assert(heur2 != NULL);
58   	
59   	   if( heur1->delaypos == heur2->delaypos )
60   	      if( heur1->priority != heur2->priority )
61   	         return heur2->priority - heur1->priority; /* prefer higher priorities */
62   	      else
63   	         return (strcmp(heur1->name, heur2->name)); /* tiebreaker */
64   	   else if( heur1->delaypos == -1 )
65   	      return +1;                                /* prefer delayed heuristics */
66   	   else if( heur2->delaypos == -1 )
67   	      return -1;                                /* prefer delayed heuristics */
68   	   else if( heur1->ncalls * heur1->freq > heur2->ncalls * heur2->freq )
69   	      return +1;
70   	   else if( heur1->ncalls * heur1->freq < heur2->ncalls * heur2->freq )
71   	      return -1;
72   	   else
73   	      return heur1->delaypos - heur2->delaypos; /* prefer lower delay positions */
74   	}
75   	
76   	/** compares two heuristics w.r.t. to their priority values */
77   	SCIP_DECL_SORTPTRCOMP(SCIPheurCompPriority)
78   	{
79   	   return SCIPheurGetPriority((SCIP_HEUR*)elem2) -
80   	     SCIPheurGetPriority((SCIP_HEUR*)elem1);
81   	}
82   	
83   	/** comparison method for sorting heuristics w.r.t. to their name */
84   	SCIP_DECL_SORTPTRCOMP(SCIPheurCompName)
85   	{
86   	   return strcmp(SCIPheurGetName((SCIP_HEUR*)elem1), SCIPheurGetName((SCIP_HEUR*)elem2));
87   	}
88   	
89   	/** method to call, when the priority of a heuristic was changed */
90   	static
91   	SCIP_DECL_PARAMCHGD(paramChgdHeurPriority)
92   	{  /*lint --e{715}*/
93   	   SCIP_PARAMDATA* paramdata;
94   	
95   	   paramdata = SCIPparamGetData(param);
96   	   assert(paramdata != NULL);
97   	
98   	   /* use SCIPsetHeurPriority() to mark the heuristics unsorted */
99   	   SCIP_CALL( SCIPsetHeurPriority(scip, (SCIP_HEUR*)paramdata, SCIPparamGetInt(param)) ); /*lint !e740*/
100  	
101  	   return SCIP_OKAY;
102  	}
103  	
104  	/** resets diving statistics */
105  	static
106  	void resetDivesetStats(
107  	   SCIP_DIVESETSTATS*    divesetstats        /**< dive set statistics */
108  	   )
109  	{
110  	   assert(divesetstats != NULL);
111  	
112  	   divesetstats->nlpiterations = 0L;
113  	   divesetstats->totaldepth = 0L;
114  	   divesetstats->totalsoldepth = 0L;
115  	   divesetstats->totalnnodes = 0L;
116  	   divesetstats->totalnbacktracks = 0L;
117  	   divesetstats->minsoldepth = INT_MAX;
118  	   divesetstats->maxsoldepth = -1;
119  	   divesetstats->mindepth = INT_MAX;
120  	   divesetstats->maxdepth = -1;
121  	   divesetstats->nlps = 0;
122  	   divesetstats->nsolsfound = 0;
123  	   divesetstats->nbestsolsfound = 0;
124  	   divesetstats->nconflictsfound = 0;
125  	   divesetstats->ncalls = 0;
126  	   divesetstats->nsolcalls = 0;
127  	}
128  	
129  	/* resets diving settings counters */
130  	SCIP_RETCODE SCIPdivesetReset(
131  	   SCIP_DIVESET*         diveset,            /**< diveset to be reset */
132  	   SCIP_SET*             set                 /**< global SCIP settings */
133  	   )
134  	{
135  	   int d;
136  	
137  	   assert(diveset != NULL);
138  	   assert(diveset->randnumgen != NULL);
139  	
140  	   /* reset diveset statistics for all contexts */
141  	   for( d = 0; d < 4; ++d )
142  	   {
143  	      resetDivesetStats(diveset->divesetstats[d]);
144  	   }
145  	
146  	   /* reset the random number generator */
147  	   SCIPrandomSetSeed(diveset->randnumgen, (unsigned int) SCIPsetInitializeRandomSeed(set, diveset->initialseed));
148  	
149  	   return SCIP_OKAY;
150  	}
151  	
152  	/** update dive set statistics */
153  	static
154  	void updateDivesetstats(
155  	   SCIP_DIVESETSTATS*    divesetstats,       /**< dive set statistics */
156  	   int                   depth,              /**< the depth reached this time */
157  	   int                   nprobingnodes,      /**< the number of probing nodes explored this time */
158  	   int                   nbacktracks,        /**< the number of backtracks during probing this time */
159  	   SCIP_Longint          nsolsfound,         /**< number of new solutions found this time */
160  	   SCIP_Longint          nbestsolsfound,     /**< number of new best solutions found this time */
161  	   SCIP_Longint          nconflictsfound,    /**< number of new conflicts found this time */
162  	   SCIP_Bool             leavesol            /**< has the diving heuristic reached a feasible leaf */
163  	   )
164  	{
165  	   divesetstats->totaldepth += depth;
166  	   divesetstats->mindepth = MIN(divesetstats->mindepth, depth);
167  	   divesetstats->maxdepth = MAX(divesetstats->maxdepth, depth);
168  	   divesetstats->totalnnodes += nprobingnodes;
169  	   divesetstats->totalnbacktracks += nbacktracks;
170  	   divesetstats->ncalls++;
171  	
172  	   /* update solution statistics only if a solution was found */
173  	   if( leavesol )
174  	   {
175  	      divesetstats->totalsoldepth += depth;
176  	      divesetstats->minsoldepth = MIN(divesetstats->minsoldepth, depth);
177  	      divesetstats->maxsoldepth = MAX(divesetstats->maxsoldepth, depth);
178  	      divesetstats->nsolcalls++;
179  	   }
180  	
181  	   divesetstats->nsolsfound += nsolsfound;
182  	   divesetstats->nbestsolsfound += nbestsolsfound;
183  	   divesetstats->nconflictsfound += nconflictsfound;
184  	}
185  	
186  	/** returns the dive set statistics for the given context */
187  	static
188  	SCIP_DIVESETSTATS* divesetGetStats(
189  	   SCIP_DIVESET*         diveset,            /**< diveset to be reset */
190  	   SCIP_DIVECONTEXT      divecontext         /**< context for diving statistics */
191  	   )
192  	{
193  	   assert(diveset != NULL);
194  	   assert(divecontext == SCIP_DIVECONTEXT_ADAPTIVE ||
195  	         divecontext == SCIP_DIVECONTEXT_SINGLE ||
196  	         divecontext == SCIP_DIVECONTEXT_TOTAL ||
197  	         divecontext == SCIP_DIVECONTEXT_SCHEDULER );
198  	
199  	   return diveset->divesetstats[(int)divecontext];
200  	}
201  	
202  	/** update diveset statistics and global diveset statistics */
203  	void SCIPdivesetUpdateStats(
204  	   SCIP_DIVESET*         diveset,            /**< diveset to be reset */
205  	   SCIP_STAT*            stat,               /**< global SCIP statistics */
206  	   int                   depth,              /**< the depth reached this time */
207  	   int                   nprobingnodes,      /**< the number of probing nodes explored this time */
208  	   int                   nbacktracks,        /**< the number of backtracks during probing this time */
209  	   SCIP_Longint          nsolsfound,         /**< number of new solutions found this time */
210  	   SCIP_Longint          nbestsolsfound,     /**< number of new best solutions found this time */
211  	   SCIP_Longint          nconflictsfound,    /**< number of new conflicts found this time */
212  	   SCIP_Bool             leavesol,           /**< has the diving heuristic reached a feasible leaf */
213  	   SCIP_DIVECONTEXT      divecontext         /**< context for diving statistics */
214  	   )
215  	{
216  	   int c;
217  	   SCIP_DIVECONTEXT updatecontexts[] = {SCIP_DIVECONTEXT_TOTAL, divecontext};
218  	
219  	   assert(diveset != NULL);
220  	   assert(divecontext == SCIP_DIVECONTEXT_ADAPTIVE || divecontext == SCIP_DIVECONTEXT_SINGLE
221  	         || divecontext == SCIP_DIVECONTEXT_SCHEDULER);
222  	
223  	   /* update statistics for total context and given context */
224  	   for( c = 0; c < 2; ++c )
225  	   {
226  	      updateDivesetstats(divesetGetStats(diveset, updatecontexts[c]), depth, nprobingnodes,
227  	            nbacktracks, nsolsfound, nbestsolsfound, nconflictsfound, leavesol);
228  	   }
229  	
230  	   stat->totaldivesetdepth += depth;
231  	   stat->ndivesetcalls++;
232  	}
233  	
234  	/** append diveset to heuristic array of divesets */
235  	static
236  	SCIP_RETCODE heurAddDiveset(
237  	   SCIP_HEUR*            heur,               /**< the heuristic to which this dive setting belongs */
238  	   SCIP_DIVESET*         diveset             /**< pointer to the freshly created diveset */
239  	   )
240  	{
241  	   assert(heur != NULL);
242  	   assert(diveset != NULL);
243  	   assert(diveset->heur == NULL);
244  	
245  	   diveset->heur = heur;
246  	
247  	   if( heur->divesets == NULL )
248  	   {
249  	      assert(heur->ndivesets == 0);
250  	      SCIP_ALLOC( BMSallocMemoryArray(&heur->divesets, 1) );
251  	   }
252  	   else
253  	   {
254  	      assert(heur->ndivesets > 0);
255  	      SCIP_ALLOC( BMSreallocMemoryArray(&heur->divesets, heur->ndivesets + 1) ); /*lint !e776 I expect no overflow here */
256  	   }
257  	
258  	   /* append diveset to the end of the array */
259  	   heur->divesets[heur->ndivesets] = diveset;
260  	   heur->ndivesets++;
261  	
262  	   return SCIP_OKAY;
263  	}
264  	
265  	/** create a set of diving heuristic settings */
266  	SCIP_RETCODE SCIPdivesetCreate(
267  	   SCIP_DIVESET**        divesetptr,         /**< pointer to the freshly created diveset */
268  	   SCIP_HEUR*            heur,               /**< the heuristic to which this dive setting belongs */
269  	   const char*           name,               /**< name for the diveset, or NULL if the name of the heuristic should be used */
270  	   SCIP_SET*             set,                /**< global SCIP settings */
271  	   SCIP_MESSAGEHDLR*     messagehdlr,        /**< message handler */
272  	   BMS_BLKMEM*           blkmem,             /**< block memory for parameter settings */
273  	   SCIP_Real             minreldepth,        /**< minimal relative depth to start diving */
274  	   SCIP_Real             maxreldepth,        /**< maximal relative depth to start diving */
275  	   SCIP_Real             maxlpiterquot,      /**< maximal fraction of diving LP iterations compared to node LP iterations */
276  	   SCIP_Real             maxdiveubquot,      /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
277  	                                              *   where diving is performed (0.0: no limit) */
278  	   SCIP_Real             maxdiveavgquot,     /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
279  	                                              *   where diving is performed (0.0: no limit) */
280  	   SCIP_Real             maxdiveubquotnosol, /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
281  	   SCIP_Real             maxdiveavgquotnosol,/**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
282  	   SCIP_Real             lpresolvedomchgquot,/**< percentage of immediate domain changes during probing to trigger LP resolve */
283  	   int                   lpsolvefreq,        /**< LP solve frequency for (0: only if enough domain reductions are found by propagation)*/
284  	   int                   maxlpiterofs,       /**< additional number of allowed LP iterations */
285  	   unsigned int          initialseed,        /**< initial seed for random number generation */
286  	   SCIP_Bool             backtrack,          /**< use one level of backtracking if infeasibility is encountered? */
287  	   SCIP_Bool             onlylpbranchcands,  /**< should only LP branching candidates be considered instead of the slower but
288  	                                              *   more general constraint handler diving variable selection? */
289  	   SCIP_Bool             ispublic,           /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */
290  	   SCIP_DIVETYPE         divetypemask,       /**< bit mask that represents the supported dive types by this dive set */
291  	   SCIP_DECL_DIVESETGETSCORE((*divesetgetscore)), /**< method for candidate score and rounding direction */
292  	   SCIP_DECL_DIVESETAVAILABLE((*divesetavailable)) /**< callback to check availability of dive set at the current stage, or NULL if always available */
293  	   )
294  	{
295  	   int c;
296  	   char paramname[SCIP_MAXSTRLEN];
297  	   const char* divesetname;
298  	   SCIP_DIVESET* diveset;
299  	
300  	   assert(divesetptr != NULL);
301  	   assert(set != NULL);
302  	   assert(divesetgetscore != NULL);
303  	   assert(heur != NULL);
304  	   assert(blkmem != NULL);
305  	
306  	   SCIP_ALLOC( BMSallocBlockMemory(blkmem, divesetptr) );
307  	   diveset = *divesetptr;
308  	
309  	   /* allocate random number generator. Note that we must make explicit use of random seed initialization because
310  	    * we create the random number generator directly, not through the public SCIP API
311  	    */
312  	   diveset->initialseed = initialseed;
313  	
314  	   /* simply use 0 as initial seed, the seed is reset in SCIPdivesetReset, anyway */
315  	   SCIP_CALL( SCIPrandomCreate(&diveset->randnumgen, blkmem, 0) );
316  	
317  	   /* for convenience, the name gets inferred from the heuristic to which the diveset is added if no name is provided */
318  	   divesetname = (name == NULL ? SCIPheurGetName(heur) : name);
319  	   SCIP_ALLOC( BMSduplicateMemoryArray(&diveset->name, divesetname, strlen(divesetname)+1) );
320  	   diveset->heur = NULL;
321  	
322  	   /* scoring callbacks */
323  	   diveset->divesetgetscore = divesetgetscore;
324  	   diveset->divesetavailable = divesetavailable;
325  	
326  	   SCIP_CALL( heurAddDiveset(heur, diveset) );
327  	   diveset->sol = NULL;
328  	   diveset->divetypemask = divetypemask;
329  	   diveset->ispublic = ispublic;
330  	
331  	   /* allocate memory for diveset statistics */
332  	   for( c = 0; c < 4; ++c )
333  	   {
334  	      SCIP_DIVESETSTATS** divesetstatsptr = &diveset->divesetstats[c];
335  	      SCIP_ALLOC( BMSallocBlockMemory(blkmem, divesetstatsptr) );
336  	   }
337  	
338  	   SCIP_CALL( SCIPdivesetReset(diveset, set) );
339  	
340  	   /* add collection of diving heuristic specific parameters */
341  	   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/minreldepth", diveset->name);
342  	   SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem,
343  	         paramname, "minimal relative depth to start diving",
344  	         &diveset->minreldepth, TRUE, minreldepth, 0.0, 1.0, NULL, NULL) );
345  	
346  	   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxreldepth", diveset->name);
347  	   SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, paramname,
348  	         "maximal relative depth to start diving",
349  	         &diveset->maxreldepth, TRUE, maxreldepth, 0.0, 1.0, NULL, NULL) );
350  	
351  	   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxlpiterquot", diveset->name);
352  	   SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem,
353  	         paramname,
354  	         "maximal fraction of diving LP iterations compared to node LP iterations",
355  	         &diveset->maxlpiterquot, FALSE, maxlpiterquot, 0.0, SCIP_REAL_MAX, NULL, NULL) );
356  	
357  	   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxlpiterofs", diveset->name);
358  	   SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem,
359  	         paramname,
360  	         "additional number of allowed LP iterations",
361  	         &diveset->maxlpiterofs, FALSE, maxlpiterofs, 0, INT_MAX, NULL, NULL) );
362  	
363  	   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdiveubquot", diveset->name);
364  	   SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem,
365  	         paramname,
366  	         "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)",
367  	         &diveset->maxdiveubquot, TRUE, maxdiveubquot, 0.0, 1.0, NULL, NULL) );
368  	
369  	   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdiveavgquot", diveset->name);
370  	   SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem,
371  	         paramname,
372  	         "maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)",
373  	         &diveset->maxdiveavgquot, TRUE, maxdiveavgquot, 0.0, SCIP_REAL_MAX, NULL, NULL) );
374  	
375  	   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdiveubquotnosol", diveset->name);
376  	   SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem,
377  	         paramname,
378  	         "maximal UBQUOT when no solution was found yet (0.0: no limit)",
379  	         &diveset->maxdiveubquotnosol, TRUE, maxdiveubquotnosol, 0.0, 1.0, NULL, NULL) );
380  	
381  	   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdiveavgquotnosol", diveset->name);
382  	   SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem,
383  	         paramname,
384  	         "maximal AVGQUOT when no solution was found yet (0.0: no limit)",
385  	         &diveset->maxdiveavgquotnosol, TRUE, maxdiveavgquotnosol, 0.0, SCIP_REAL_MAX, NULL, NULL) );
386  	
387  	   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/backtrack", diveset->name);
388  	   SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem,
389  	         paramname,
390  	         "use one level of backtracking if infeasibility is encountered?",
391  	         &diveset->backtrack, FALSE, backtrack, NULL, NULL) );
392  	
393  	   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/lpresolvedomchgquot", diveset->name);
394  	   SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, paramname,
395  	         "percentage of immediate domain changes during probing to trigger LP resolve",
396  	         &diveset->lpresolvedomchgquot, FALSE, lpresolvedomchgquot,  0.0, SCIP_REAL_MAX, NULL, NULL) );
397  	
398  	   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/lpsolvefreq", diveset->name);
399  	   SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem,
400  	         paramname,
401  	         "LP solve frequency for diving heuristics (0: only after enough domain changes have been found)",
402  	         &diveset->lpsolvefreq, FALSE, lpsolvefreq, 0, INT_MAX,
403  	         NULL, NULL) );
404  	
405  	   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/onlylpbranchcands", diveset->name);
406  	   SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem,
407  	            paramname,
408  	            "should only LP branching candidates be considered instead of the slower but "
409  	            "more general constraint handler diving variable selection?",
410  	            &diveset->onlylpbranchcands, FALSE, onlylpbranchcands, NULL, NULL) );
411  	
412  	   return SCIP_OKAY;
413  	}
414  	
415  	/** get the heuristic to which this diving setting belongs */
416  	SCIP_HEUR* SCIPdivesetGetHeur(
417  	   SCIP_DIVESET*         diveset             /**< diving settings */
418  	   )
419  	{
420  	   return diveset->heur;
421  	}
422  	
423  	/** get the working solution of this dive set */
424  	SCIP_SOL* SCIPdivesetGetWorkSolution(
425  	   SCIP_DIVESET*         diveset             /**< diving settings */
426  	   )
427  	{
428  	   assert(diveset != NULL);
429  	
430  	   return diveset->sol;
431  	}
432  	
433  	/** set the working solution for this dive set */
434  	void SCIPdivesetSetWorkSolution(
435  	   SCIP_DIVESET*         diveset,            /**< diving settings */
436  	   SCIP_SOL*             sol                 /**< new working solution for this dive set, or NULL */
437  	   )
438  	{
439  	   assert(diveset != NULL);
440  	
441  	   diveset->sol = sol;
442  	}
443  	
444  	/** get the name of the dive set */
445  	const char* SCIPdivesetGetName(
446  	   SCIP_DIVESET*         diveset             /**< diving settings */
447  	   )
448  	{
449  	   assert(diveset != NULL);
450  	
451  	   return diveset->name;
452  	}
453  	
454  	/** get the minimum relative depth of the diving settings */
455  	SCIP_Real SCIPdivesetGetMinRelDepth(
456  	   SCIP_DIVESET*         diveset             /**< diving settings */
457  	   )
458  	{
459  	   return diveset->minreldepth;
460  	}
461  	
462  	/** get the maximum relative depth of the diving settings */
463  	SCIP_Real SCIPdivesetGetMaxRelDepth(
464  	   SCIP_DIVESET*         diveset             /**< diving settings */
465  	   )
466  	{
467  	   return diveset->maxreldepth;
468  	}
469  	
470  	/** get the number of successful runs of the diving settings */
471  	SCIP_Longint SCIPdivesetGetSolSuccess(
472  	   SCIP_DIVESET*         diveset,            /**< diving settings */
473  	   SCIP_DIVECONTEXT      divecontext         /**< context for diving statistics */
474  	
475  	   )
476  	{
477  	   SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
478  	
479  	   assert(divesetstats != NULL);
480  	
481  	   return 10 * divesetstats->nbestsolsfound + divesetstats->nsolsfound;
482  	}
483  	
484  	/** get the number of calls to this dive set */
485  	int SCIPdivesetGetNCalls(
486  	   SCIP_DIVESET*         diveset,            /**< diving settings */
487  	   SCIP_DIVECONTEXT      divecontext         /**< context for diving statistics */
488  	   )
489  	{
490  	   SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
491  	
492  	   assert(divesetstats != NULL);
493  	
494  	   return divesetstats->ncalls;
495  	}
496  	
497  	/** get the number of calls successfully terminated at a feasible leaf node */
498  	int SCIPdivesetGetNSolutionCalls(
499  	   SCIP_DIVESET*         diveset,            /**< diving settings */
500  	   SCIP_DIVECONTEXT      divecontext         /**< context for diving statistics */
501  	   )
502  	{
503  	   SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
504  	
505  	   assert(diveset != NULL);
506  	
507  	   return divesetstats->nsolcalls;
508  	}
509  	
510  	/** get the minimum depth reached by this dive set */
511  	int SCIPdivesetGetMinDepth(
512  	   SCIP_DIVESET*         diveset,            /**< diving settings */
513  	   SCIP_DIVECONTEXT      divecontext         /**< context for diving statistics */
514  	   )
515  	{
516  	   SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
517  	
518  	   assert(divesetstats != NULL);
519  	
520  	   return divesetstats->mindepth;
521  	}
522  	
523  	/** get the maximum depth reached by this dive set */
524  	int SCIPdivesetGetMaxDepth(
525  	   SCIP_DIVESET*         diveset,            /**< diving settings */
526  	   SCIP_DIVECONTEXT      divecontext         /**< context for diving statistics */
527  	   )
528  	{
529  	   SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
530  	
531  	   assert(divesetstats != NULL);
532  	
533  	   return divesetstats->maxdepth;
534  	}
535  	
536  	/** get the average depth this dive set reached during execution */
537  	SCIP_Real SCIPdivesetGetAvgDepth(
538  	   SCIP_DIVESET*         diveset,            /**< diving settings */
539  	   SCIP_DIVECONTEXT      divecontext         /**< context for diving statistics */
540  	   )
541  	{
542  	   SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
543  	
544  	   assert(divesetstats != NULL);
545  	
546  	   return (divesetstats->ncalls == 0 ? 0.0 : divesetstats->totaldepth / (SCIP_Real)divesetstats->ncalls);
547  	}
548  	
549  	/** get the minimum depth at which this dive set found a solution */
550  	int SCIPdivesetGetMinSolutionDepth(
551  	   SCIP_DIVESET*         diveset,            /**< diving settings */
552  	   SCIP_DIVECONTEXT      divecontext         /**< context for diving statistics */
553  	   )
554  	{
555  	   SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
556  	
557  	   assert(divesetstats != NULL);
558  	
559  	   return divesetstats->minsoldepth;
560  	}
561  	
562  	/** get the maximum depth at which this dive set found a solution */
563  	int SCIPdivesetGetMaxSolutionDepth(
564  	   SCIP_DIVESET*         diveset,            /**< diving settings */
565  	   SCIP_DIVECONTEXT      divecontext         /**< context for diving statistics */
566  	   )
567  	{
568  	   SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
569  	
570  	   assert(divesetstats != NULL);
571  	
572  	   return divesetstats->maxsoldepth;
573  	}
574  	
575  	/** get the average depth at which this dive set found a solution */
576  	SCIP_Real SCIPdivesetGetAvgSolutionDepth(
577  	   SCIP_DIVESET*         diveset,            /**< diving settings */
578  	   SCIP_DIVECONTEXT      divecontext         /**< context for diving statistics */
579  	   )
580  	{
581  	   SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
582  	
583  	   assert(divesetstats != NULL);
584  	
585  	   return (divesetstats->nsolcalls == 0 ? 0.0 : divesetstats->totalsoldepth / (SCIP_Real)divesetstats->nsolcalls);
586  	}
587  	
588  	/** get the total number of LP iterations used by this dive set */
589  	SCIP_Longint SCIPdivesetGetNLPIterations(
590  	   SCIP_DIVESET*         diveset,            /**< diving settings */
591  	   SCIP_DIVECONTEXT      divecontext         /**< context for diving statistics */
592  	   )
593  	{
594  	   SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
595  	
596  	   assert(divesetstats != NULL);
597  	
598  	   return divesetstats->nlpiterations;
599  	}
600  	
601  	/** get the total number of probing nodes used by this dive set */
602  	SCIP_Longint SCIPdivesetGetNProbingNodes(
603  	   SCIP_DIVESET*         diveset,            /**< diving settings */
604  	   SCIP_DIVECONTEXT      divecontext         /**< context for diving statistics */
605  	   )
606  	{
607  	   SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
608  	
609  	   assert(divesetstats != NULL);
610  	
611  	   return divesetstats->totalnnodes;
612  	}
613  	
614  	/** get the total number of backtracks performed by this dive set */
615  	SCIP_Longint SCIPdivesetGetNBacktracks(
616  	   SCIP_DIVESET*         diveset,            /**< diving settings */
617  	   SCIP_DIVECONTEXT      divecontext         /**< context for diving statistics */
618  	   )
619  	{
620  	   SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
621  	
622  	   assert(divesetstats != NULL);
623  	
624  	   return divesetstats->totalnbacktracks;
625  	}
626  	
627  	/** get the total number of conflicts found by this dive set */
628  	SCIP_Longint SCIPdivesetGetNConflicts(
629  	   SCIP_DIVESET*         diveset,            /**< diving settings */
630  	   SCIP_DIVECONTEXT      divecontext         /**< context for diving statistics */
631  	   )
632  	{
633  	   SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
634  	
635  	   assert(divesetstats != NULL);
636  	
637  	   return divesetstats->nconflictsfound;
638  	}
639  	
640  	/** get the total number of solutions (leaf and rounded solutions) found by the dive set */
641  	SCIP_Longint SCIPdivesetGetNSols(
642  	   SCIP_DIVESET*         diveset,            /**< diving settings */
643  	   SCIP_DIVECONTEXT      divecontext         /**< context for diving statistics */
644  	   )
645  	{
646  	   SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
647  	
648  	   assert(divesetstats != NULL);
649  	
650  	   return divesetstats->nsolsfound;
651  	}
652  	
653  	
654  	/** get the maximum LP iterations quotient of the diving settings */
655  	SCIP_Real SCIPdivesetGetMaxLPIterQuot(
656  	   SCIP_DIVESET*         diveset             /**< diving settings */
657  	   )
658  	{
659  	   return diveset->maxlpiterquot;
660  	}
661  	
662  	/** get the maximum LP iterations offset of the diving settings */
663  	int SCIPdivesetGetMaxLPIterOffset(
664  	   SCIP_DIVESET*         diveset             /**< diving settings */
665  	   )
666  	{
667  	   return diveset->maxlpiterofs;
668  	}
669  	
670  	/** get the maximum upper bound quotient parameter of the diving settings if no solution is available */
671  	SCIP_Real SCIPdivesetGetUbQuotNoSol(
672  	   SCIP_DIVESET*         diveset             /**< diving settings */
673  	   )
674  	{
675  	   return diveset->maxdiveubquotnosol;
676  	}
677  	
678  	/** get the average quotient parameter of the diving settings if no solution is available */
679  	SCIP_Real SCIPdivesetGetAvgQuotNoSol(
680  	   SCIP_DIVESET*         diveset             /**< diving settings */
681  	   )
682  	{
683  	   return diveset->maxdiveavgquotnosol;
684  	}
685  	/** get the maximum upper bound quotient parameter of the diving settings if an incumbent solution exists */
686  	SCIP_Real SCIPdivesetGetUbQuot(
687  	   SCIP_DIVESET*         diveset             /**< diving settings */
688  	   )
689  	{
690  	   return diveset->maxdiveubquot;
691  	}
692  	
693  	/** get the average upper bound quotient parameter of the diving settings if an incumbent solution exists */
694  	SCIP_Real SCIPdivesetGetAvgQuot(
695  	   SCIP_DIVESET*         diveset             /**< diving settings */
696  	   )
697  	{
698  	   return diveset->maxdiveavgquot;
699  	}
700  	
701  	/** should backtracking be applied? */
702  	SCIP_Bool SCIPdivesetUseBacktrack(
703  	   SCIP_DIVESET*         diveset             /**< diving settings */
704  	   )
705  	{
706  	   return diveset->backtrack;
707  	}
708  	
709  	/** returns the LP solve frequency for diving LPs (0: dynamically based on number of intermediate domain reductions) */
710  	int SCIPdivesetGetLPSolveFreq(
711  	   SCIP_DIVESET*         diveset             /**< diving settings */
712  	   )
713  	{
714  	   assert(diveset != NULL);
715  	
716  	   return diveset->lpsolvefreq;
717  	}
718  	
719  	/** returns the random number generator of this \p diveset for tie-breaking */
720  	SCIP_RANDNUMGEN* SCIPdivesetGetRandnumgen(
721  	   SCIP_DIVESET*         diveset             /**< diving settings */
722  	   )
723  	{
724  	   assert(diveset != NULL);
725  	   assert(diveset->randnumgen != NULL);
726  	
727  	   return diveset->randnumgen;
728  	}
729  	
730  	/** returns the domain reduction quotient for triggering an immediate resolve of the diving LP (0.0: always resolve)*/
731  	SCIP_Real SCIPdivesetGetLPResolveDomChgQuot(
732  	   SCIP_DIVESET*         diveset             /**< diving settings */
733  	   )
734  	{
735  	   assert(diveset != NULL);
736  	
737  	   return diveset->lpresolvedomchgquot;
738  	}
739  	
740  	/** should only LP branching candidates be considered instead of the slower but
741  	 *  more general constraint handler diving variable selection?
742  	 */
743  	SCIP_Bool SCIPdivesetUseOnlyLPBranchcands(
744  	   SCIP_DIVESET*         diveset             /**< diving settings */
745  	   )
746  	{
747  	   assert(diveset != NULL);
748  	
749  	   return diveset->onlylpbranchcands;
750  	}
751  	
752  	/** returns TRUE if dive set supports diving of the specified type */
753  	SCIP_Bool SCIPdivesetSupportsType(
754  	   SCIP_DIVESET*         diveset,            /**< diving settings */
755  	   SCIP_DIVETYPE         divetype            /**< bit mask that represents the supported dive types by this dive set */
756  	   )
757  	{
758  	   assert(diveset != NULL);
759  	
760  	   return (divetype & diveset->divetypemask);
761  	}
762  	
763  	/** is this dive set publicly available (ie., can be used by other primal heuristics?) */
764  	SCIP_Bool SCIPdivesetIsPublic(
765  	   SCIP_DIVESET*         diveset             /**< diving settings */
766  	   )
767  	{
768  	   assert(diveset != NULL);
769  	
770  	   return diveset->ispublic;
771  	}
772  	
773  	/** updates LP related diveset statistics */
774  	static
775  	void updateDivesetstatsLP(
776  	   SCIP_DIVESETSTATS*    divesetstats,       /**< diving settings */
777  	   SCIP_Longint          niterstoadd         /**< additional number of LP iterations to be added */
778  	   )
779  	{
780  	   assert(divesetstats != NULL);
781  	
782  	   divesetstats->nlpiterations += niterstoadd;
783  	   divesetstats->nlps++;
784  	}
785  	
786  	/** update diveset LP statistics, should be called after every LP solved by this diving heuristic */
787  	void SCIPdivesetUpdateLPStats(
788  	   SCIP_DIVESET*         diveset,            /**< diving settings */
789  	   SCIP_STAT*            stat,               /**< global SCIP statistics */
790  	   SCIP_Longint          niterstoadd,        /**< additional number of LP iterations to be added */
791  	   SCIP_DIVECONTEXT      divecontext         /**< context for diving statistics */
792  	   )
793  	{
794  	   assert(diveset != NULL);
795  	   assert(divecontext == SCIP_DIVECONTEXT_ADAPTIVE || divecontext == SCIP_DIVECONTEXT_SINGLE
796  	         || divecontext == SCIP_DIVECONTEXT_SCHEDULER);
797  	
798  	   /* update statistics for total context and given context */
799  	   updateDivesetstatsLP(divesetGetStats(diveset, divecontext), niterstoadd);
800  	   updateDivesetstatsLP(divesetGetStats(diveset, SCIP_DIVECONTEXT_TOTAL), niterstoadd);
801  	
802  	   stat->ndivesetlpiterations += niterstoadd;
803  	   stat->ndivesetlps++;
804  	}
805  	
806  	/** frees memory of a diveset */
807  	static
808  	void divesetFree(
809  	   SCIP_DIVESET**        divesetptr,         /**< general diving settings */
810  	   BMS_BLKMEM*           blkmem              /**< block memory for parameter settings */
811  	   )
812  	{
813  	   int c;
814  	   SCIP_DIVESET* diveset = *divesetptr;
815  	
816  	   assert(diveset != NULL);
817  	   assert(diveset->name != NULL);
818  	   assert(diveset->randnumgen != NULL);
819  	
820  	   SCIPrandomFree(&diveset->randnumgen, blkmem);
821  	
822  	   /* free all diveset statistics */
823  	   for( c = 0; c < 4; ++c )
824  	   {
825  	      SCIP_DIVESETSTATS** divesetstatsptr = &diveset->divesetstats[c];
826  	      BMSfreeBlockMemory(blkmem, divesetstatsptr);
827  	   }
828  	
829  	   BMSfreeMemoryArray(&diveset->name);
830  	   BMSfreeBlockMemory(blkmem, divesetptr);
831  	}
832  	
833  	/** get the candidate score and preferred rounding direction for a candidate variable */
834  	SCIP_RETCODE SCIPdivesetGetScore(
835  	   SCIP_DIVESET*         diveset,            /**< general diving settings */
836  	   SCIP_SET*             set,                /**< SCIP settings */
837  	   SCIP_DIVETYPE         divetype,           /**< the type of diving that should be applied */
838  	   SCIP_VAR*             divecand,           /**< the candidate for which the branching direction is requested */
839  	   SCIP_Real             divecandsol,        /**< LP solution value of the candidate */
840  	   SCIP_Real             divecandfrac,       /**< fractionality of the candidate */
841  	   SCIP_Real*            candscore,          /**< pointer to store the candidate score */
842  	   SCIP_Bool*            roundup             /**< pointer to store whether preferred direction for diving is upwards */
843  	   )
844  	{
845  	   assert(diveset->divesetgetscore != NULL);
846  	   assert(candscore != NULL);
847  	   assert(roundup != NULL);
848  	   assert(divecand != NULL);
849  	   assert(divetype & diveset->divetypemask);
850  	
851  	   SCIP_CALL( diveset->divesetgetscore(set->scip, diveset, divetype, divecand, divecandsol, divecandfrac,
852  	         candscore, roundup) );
853  	
854  	   return SCIP_OKAY;
855  	}
856  	
857  	/** check specific preconditions for diving, e.g., if an incumbent solution is available */
858  	SCIP_RETCODE SCIPdivesetIsAvailable(
859  	   SCIP_DIVESET*         diveset,            /**< diving heuristic settings */
860  	   SCIP_SET*             set,                /**< SCIP settings */
861  	   SCIP_Bool*            available           /**< pointer to store if the diving can run at the current solving stage */
862  	   )
863  	{
864  	   assert(set != NULL);
865  	   assert(diveset != NULL);
866  	   assert(available != NULL);
867  	
868  	   if( diveset->divesetavailable == NULL )
869  	      *available = TRUE;
870  	   else
871  	   {
872  	      *available = FALSE;
873  	      SCIP_CALL( diveset->divesetavailable(set->scip, diveset, available) );
874  	   }
875  	
876  	   return SCIP_OKAY;
877  	}
878  	
879  	
880  	
881  	/** copies the given primal heuristic to a new scip */
882  	SCIP_RETCODE SCIPheurCopyInclude(
883  	   SCIP_HEUR*            heur,               /**< primal heuristic */
884  	   SCIP_SET*             set                 /**< SCIP_SET of SCIP to copy to */
885  	   )
886  	{
887  	   assert(heur != NULL);
888  	   assert(set != NULL);
889  	   assert(set->scip != NULL);
890  	
891  	   if( heur->heurcopy != NULL )
892  	   {
893  	      SCIPsetDebugMsg(set, "including heur %s in subscip %p\n", SCIPheurGetName(heur), (void*)set->scip);
894  	      SCIP_CALL( heur->heurcopy(set->scip, heur) );
895  	   }
896  	
897  	   return SCIP_OKAY;
898  	}
899  	
900  	/** internal method for creating a primal heuristic */
901  	static
902  	SCIP_RETCODE doHeurCreate(
903  	   SCIP_HEUR**           heur,               /**< pointer to primal heuristic data structure */
904  	   SCIP_SET*             set,                /**< global SCIP settings */
905  	   SCIP_MESSAGEHDLR*     messagehdlr,        /**< message handler */
906  	   BMS_BLKMEM*           blkmem,             /**< block memory for parameter settings */
907  	   const char*           name,               /**< name of primal heuristic */
908  	   const char*           desc,               /**< description of primal heuristic */
909  	   char                  dispchar,           /**< display character of primal heuristic */
910  	   int                   priority,           /**< priority of the primal heuristic */
911  	   int                   freq,               /**< frequency for calling primal heuristic */
912  	   int                   freqofs,            /**< frequency offset for calling primal heuristic */
913  	   int                   maxdepth,           /**< maximal depth level to call heuristic at (-1: no limit) */
914  	   SCIP_HEURTIMING       timingmask,         /**< positions in the node solving loop where heuristic should be executed */
915  	   SCIP_Bool             usessubscip,        /**< does the heuristic use a secondary SCIP instance? */
916  	   SCIP_DECL_HEURCOPY    ((*heurcopy)),      /**< copy method of primal heuristic or NULL if you don't want to copy your plugin into sub-SCIPs */
917  	   SCIP_DECL_HEURFREE    ((*heurfree)),      /**< destructor of primal heuristic */
918  	   SCIP_DECL_HEURINIT    ((*heurinit)),      /**< initialize primal heuristic */
919  	   SCIP_DECL_HEUREXIT    ((*heurexit)),      /**< deinitialize primal heuristic */
920  	   SCIP_DECL_HEURINITSOL ((*heurinitsol)),   /**< solving process initialization method of primal heuristic */
921  	   SCIP_DECL_HEUREXITSOL ((*heurexitsol)),   /**< solving process deinitialization method of primal heuristic */
922  	   SCIP_DECL_HEUREXEC    ((*heurexec)),      /**< execution method of primal heuristic */
923  	   SCIP_HEURDATA*        heurdata            /**< primal heuristic data */
924  	   )
925  	{
926  	   char paramname[SCIP_MAXSTRLEN];
927  	   char paramdesc[SCIP_MAXSTRLEN];
928  	
929  	   assert(heur != NULL);
930  	   assert(name != NULL);
931  	   assert(desc != NULL);
932  	   assert(freq >= -1);
933  	   assert(freqofs >= 0);
934  	   assert(heurexec != NULL);
935  	
936  	   SCIP_ALLOC( BMSallocMemory(heur) );
937  	   BMSclearMemory(*heur);
938  	
939  	   SCIP_ALLOC( BMSduplicateMemoryArray(&(*heur)->name, name, strlen(name)+1) );
940  	   SCIP_ALLOC( BMSduplicateMemoryArray(&(*heur)->desc, desc, strlen(desc)+1) );
941  	   (*heur)->dispchar = dispchar;
942  	   (*heur)->priority = priority;
943  	   (*heur)->freq = freq;
944  	   (*heur)->freqofs = freqofs;
945  	   (*heur)->maxdepth = maxdepth;
946  	   (*heur)->delaypos = -1;
947  	   (*heur)->timingmask = timingmask;
948  	   (*heur)->usessubscip = usessubscip;
949  	   (*heur)->heurcopy = heurcopy;
950  	   (*heur)->heurfree = heurfree;
951  	   (*heur)->heurinit = heurinit;
952  	   (*heur)->heurexit = heurexit;
953  	   (*heur)->heurinitsol = heurinitsol;
954  	   (*heur)->heurexitsol = heurexitsol;
955  	   (*heur)->heurexec = heurexec;
956  	   (*heur)->heurdata = heurdata;
957  	   SCIP_CALL( SCIPclockCreate(&(*heur)->setuptime, SCIP_CLOCKTYPE_DEFAULT) );
958  	   SCIP_CALL( SCIPclockCreate(&(*heur)->heurclock, SCIP_CLOCKTYPE_DEFAULT) );
959  	   (*heur)->ncalls = 0;
960  	   (*heur)->nsolsfound = 0;
961  	   (*heur)->nbestsolsfound = 0;
962  	   (*heur)->initialized = FALSE;
963  	   (*heur)->divesets = NULL;
964  	   (*heur)->ndivesets = 0;
965  	
966  	   /* add parameters */
967  	   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/priority", name);
968  	   (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "priority of heuristic <%s>", name);
969  	   SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
970  	                  &(*heur)->priority, TRUE, priority, INT_MIN/4, INT_MAX/4,
971  	                  paramChgdHeurPriority, (SCIP_PARAMDATA*)(*heur)) ); /*lint !e740*/
972  	   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/freq", name);
973  	   (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "frequency for calling primal heuristic <%s> (-1: never, 0: only at depth freqofs)", name);
974  	   SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
975  	                  &(*heur)->freq, FALSE, freq, -1, SCIP_MAXTREEDEPTH, NULL, NULL) );
976  	   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/freqofs", name);
977  	   (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "frequency offset for calling primal heuristic <%s>", name);
978  	   SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
979  	                  &(*heur)->freqofs, FALSE, freqofs, 0, SCIP_MAXTREEDEPTH, NULL, NULL) );
980  	   (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdepth", name);
981  	   (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "maximal depth level to call primal heuristic <%s> (-1: no limit)", name);
982  	   SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
983  	                  &(*heur)->maxdepth, TRUE, maxdepth, -1, SCIP_MAXTREEDEPTH, NULL, NULL) );
984  	
985  	   return SCIP_OKAY;
986  	}
987  	
988  	/** creates a primal heuristic */
989  	SCIP_RETCODE SCIPheurCreate(
990  	   SCIP_HEUR**           heur,               /**< pointer to primal heuristic data structure */
991  	   SCIP_SET*             set,                /**< global SCIP settings */
992  	   SCIP_MESSAGEHDLR*     messagehdlr,        /**< message handler */
993  	   BMS_BLKMEM*           blkmem,             /**< block memory for parameter settings */
994  	   const char*           name,               /**< name of primal heuristic */
995  	   const char*           desc,               /**< description of primal heuristic */
996  	   char                  dispchar,           /**< display character of primal heuristic */
997  	   int                   priority,           /**< priority of the primal heuristic */
998  	   int                   freq,               /**< frequency for calling primal heuristic */
999  	   int                   freqofs,            /**< frequency offset for calling primal heuristic */
1000 	   int                   maxdepth,           /**< maximal depth level to call heuristic at (-1: no limit) */
1001 	   SCIP_HEURTIMING       timingmask,         /**< positions in the node solving loop where heuristic should be executed */
1002 	   SCIP_Bool             usessubscip,        /**< does the heuristic use a secondary SCIP instance? */
1003 	   SCIP_DECL_HEURCOPY    ((*heurcopy)),      /**< copy method of primal heuristic or NULL if you don't want to copy your plugin into sub-SCIPs */
1004 	   SCIP_DECL_HEURFREE    ((*heurfree)),      /**< destructor of primal heuristic */
1005 	   SCIP_DECL_HEURINIT    ((*heurinit)),      /**< initialize primal heuristic */
1006 	   SCIP_DECL_HEUREXIT    ((*heurexit)),      /**< deinitialize primal heuristic */
1007 	   SCIP_DECL_HEURINITSOL ((*heurinitsol)),   /**< solving process initialization method of primal heuristic */
1008 	   SCIP_DECL_HEUREXITSOL ((*heurexitsol)),   /**< solving process deinitialization method of primal heuristic */
1009 	   SCIP_DECL_HEUREXEC    ((*heurexec)),      /**< execution method of primal heuristic */
1010 	   SCIP_HEURDATA*        heurdata            /**< primal heuristic data */
1011 	   )
1012 	{
1013 	   assert(heur != NULL);
1014 	   assert(name != NULL);
1015 	   assert(desc != NULL);
1016 	   assert(freq >= -1);
1017 	   assert(freqofs >= 0);
1018 	   assert(heurexec != NULL);
1019 	
1020 	   SCIP_CALL_FINALLY( doHeurCreate(heur, set, messagehdlr, blkmem, name, desc, dispchar, priority, freq, freqofs,
1021 	      maxdepth, timingmask, usessubscip, heurcopy, heurfree, heurinit, heurexit, heurinitsol, heurexitsol, heurexec,
1022 	      heurdata), (void) SCIPheurFree(heur, set, blkmem) );
1023 	
1024 	   return SCIP_OKAY;
1025 	}
1026 	
1027 	/** calls destructor and frees memory of primal heuristic */
1028 	SCIP_RETCODE SCIPheurFree(
1029 	   SCIP_HEUR**           heur,               /**< pointer to primal heuristic data structure */
1030 	   SCIP_SET*             set,                /**< global SCIP settings */
1031 	   BMS_BLKMEM*           blkmem              /**< block memory */
1032 	   )
1033 	{
1034 	   int d;
1035 	   assert(heur != NULL);
1036 	   if( *heur == NULL )
1037 	      return SCIP_OKAY;
1038 	   assert(!(*heur)->initialized);
1039 	   assert(set != NULL);
1040 	   assert((*heur)->divesets != NULL || (*heur)->ndivesets == 0);
1041 	
1042 	   /* call destructor of primal heuristic */
1043 	   if( (*heur)->heurfree != NULL )
1044 	   {
1045 	      SCIP_CALL( (*heur)->heurfree(set->scip, *heur) );
1046 	   }
1047 	
1048 	   for( d = 0; d < (*heur)->ndivesets; ++d )
1049 	   {
1050 	      assert((*heur)->divesets[d] != NULL);
1051 	      divesetFree(&((*heur)->divesets[d]), blkmem);
1052 	   }
1053 	   BMSfreeMemoryArrayNull(&(*heur)->divesets);
1054 	   SCIPclockFree(&(*heur)->heurclock);
1055 	   SCIPclockFree(&(*heur)->setuptime);
1056 	   BMSfreeMemoryArrayNull(&(*heur)->name);
1057 	   BMSfreeMemoryArrayNull(&(*heur)->desc);
1058 	   BMSfreeMemory(heur);
1059 	
1060 	   return SCIP_OKAY;
1061 	}
1062 	
1063 	/** initializes primal heuristic */
1064 	SCIP_RETCODE SCIPheurInit(
1065 	   SCIP_HEUR*            heur,               /**< primal heuristic */
1066 	   SCIP_SET*             set                 /**< global SCIP settings */
1067 	   )
1068 	{
1069 	   int d;
1070 	   assert(heur != NULL);
1071 	   assert(set != NULL);
1072 	
1073 	   if( heur->initialized )
1074 	   {
1075 	      SCIPerrorMessage("primal heuristic <%s> already initialized\n", heur->name);
1076 	      return SCIP_INVALIDCALL;
1077 	   }
1078 	
1079 	   if( set->misc_resetstat )
1080 	   {
1081 	      SCIPclockReset(heur->setuptime);
1082 	      SCIPclockReset(heur->heurclock);
1083 	
1084 	      heur->delaypos = -1;
1085 	      heur->ncalls = 0;
1086 	      heur->nsolsfound = 0;
1087 	      heur->nbestsolsfound = 0;
1088 	
1089 	      set->heurssorted = FALSE;
1090 	      set->heursnamesorted = FALSE;
1091 	   }
1092 	
1093 	   if( heur->heurinit != NULL )
1094 	   {
1095 	      /* start timing */
1096 	      SCIPclockStart(heur->setuptime, set);
1097 	
1098 	      SCIP_CALL( heur->heurinit(set->scip, heur) );
1099 	
1100 	      /* stop timing */
1101 	      SCIPclockStop(heur->setuptime, set);
1102 	   }
1103 	
1104 	   /* reset dive sets */
1105 	   for( d = 0; d < heur->ndivesets; ++d )
1106 	   {
1107 	      assert(heur->divesets[d] != NULL);
1108 	      SCIP_CALL( SCIPdivesetReset(heur->divesets[d], set) );
1109 	   }
1110 	
1111 	   heur->initialized = TRUE;
1112 	
1113 	   return SCIP_OKAY;
1114 	}
1115 	
1116 	/** calls exit method of primal heuristic */
1117 	SCIP_RETCODE SCIPheurExit(
1118 	   SCIP_HEUR*            heur,               /**< primal heuristic */
1119 	   SCIP_SET*             set                 /**< global SCIP settings */
1120 	   )
1121 	{
1122 	   assert(heur != NULL);
1123 	   assert(set != NULL);
1124 	
1125 	   if( !heur->initialized )
1126 	   {
1127 	      SCIPerrorMessage("primal heuristic <%s> not initialized\n", heur->name);
1128 	      return SCIP_INVALIDCALL;
1129 	   }
1130 	
1131 	   if( heur->heurexit != NULL )
1132 	   {
1133 	      /* start timing */
1134 	      SCIPclockStart(heur->setuptime, set);
1135 	
1136 	      SCIP_CALL( heur->heurexit(set->scip, heur) );
1137 	
1138 	      /* stop timing */
1139 	      SCIPclockStop(heur->setuptime, set);
1140 	   }
1141 	   heur->initialized = FALSE;
1142 	
1143 	   return SCIP_OKAY;
1144 	}
1145 	
1146 	/** informs primal heuristic that the branch and bound process is being started */
1147 	SCIP_RETCODE SCIPheurInitsol(
1148 	   SCIP_HEUR*            heur,               /**< primal heuristic */
1149 	   SCIP_SET*             set                 /**< global SCIP settings */
1150 	   )
1151 	{
1152 	   assert(heur != NULL);
1153 	   assert(set != NULL);
1154 	
1155 	   if( heur->delaypos != -1 )
1156 	   {
1157 	      heur->delaypos = -1;
1158 	      set->heurssorted = FALSE;
1159 	   }
1160 	
1161 	   /* call solving process initialization method of primal heuristic */
1162 	   if( heur->heurinitsol != NULL )
1163 	   {
1164 	      /* start timing */
1165 	      SCIPclockStart(heur->setuptime, set);
1166 	
1167 	      SCIP_CALL( heur->heurinitsol(set->scip, heur) );
1168 	
1169 	      /* stop timing */
1170 	      SCIPclockStop(heur->setuptime, set);
1171 	   }
1172 	
1173 	   return SCIP_OKAY;
1174 	}
1175 	
1176 	/** informs primal heuristic that the branch and bound process data is being freed */
1177 	SCIP_RETCODE SCIPheurExitsol(
1178 	   SCIP_HEUR*            heur,               /**< primal heuristic */
1179 	   SCIP_SET*             set                 /**< global SCIP settings */
1180 	   )
1181 	{
1182 	   assert(heur != NULL);
1183 	   assert(set != NULL);
1184 	
1185 	   /* call solving process deinitialization method of primal heuristic */
1186 	   if( heur->heurexitsol != NULL )
1187 	   {
1188 	      /* start timing */
1189 	      SCIPclockStart(heur->setuptime, set);
1190 	
1191 	      SCIP_CALL( heur->heurexitsol(set->scip, heur) );
1192 	
1193 	      /* stop timing */
1194 	      SCIPclockStop(heur->setuptime, set);
1195 	   }
1196 	
1197 	   return SCIP_OKAY;
1198 	}
1199 	
1200 	/** should the heuristic be executed at the given depth, frequency, timing, ... */
1201 	SCIP_Bool SCIPheurShouldBeExecuted(
1202 	   SCIP_HEUR*            heur,               /**< primal heuristic */
1203 	   int                   depth,              /**< depth of current node */
1204 	   int                   lpstateforkdepth,   /**< depth of the last node with solved LP */
1205 	   SCIP_HEURTIMING       heurtiming,         /**< current point in the node solving process */
1206 	   SCIP_Bool*            delayed             /**< pointer to store whether the heuristic should be delayed */
1207 	   )
1208 	{
1209 	   SCIP_Bool execute;
1210 	
1211 	   if( ((heur->timingmask & SCIP_HEURTIMING_BEFOREPRESOL) && heurtiming == SCIP_HEURTIMING_BEFOREPRESOL)
1212 	       || ((heur->timingmask & SCIP_HEURTIMING_DURINGPRESOLLOOP) && heurtiming == SCIP_HEURTIMING_DURINGPRESOLLOOP) )
1213 	   {
1214 	      /* heuristic may be executed before/during presolving. Do so, if it was not disabled by setting the frequency to -1 */
1215 	      execute = heur->freq >= 0; 
1216 	   } 
1217 	   else if( (heur->timingmask & SCIP_HEURTIMING_AFTERPSEUDONODE) == 0
1218 	      && (heurtiming == SCIP_HEURTIMING_AFTERLPNODE || heurtiming == SCIP_HEURTIMING_AFTERLPPLUNGE) )
1219 	   {
1220 	      /* heuristic was skipped on intermediate pseudo nodes: check, if a node matching the execution frequency lies
1221 	       * between the current node and the last LP node of the path
1222 	       */
1223 	      execute = (heur->freq > 0 && depth >= heur->freqofs 
1224 	         && ((depth + heur->freq - heur->freqofs) / heur->freq
1225 	            != (lpstateforkdepth + heur->freq - heur->freqofs) / heur->freq));
1226 	   }
1227 	   else
1228 	   {
1229 	      /* heuristic may be executed on every node: check, if the current depth matches the execution frequency and offset */
1230 	      execute = (heur->freq > 0 && depth >= heur->freqofs && (depth - heur->freqofs) % heur->freq == 0);
1231 	   }
1232 	
1233 	   /* if frequency is zero, execute heuristic only at the depth level of the frequency offset */
1234 	   execute = execute || (depth == heur->freqofs && heur->freq == 0);
1235 	
1236 	   /* compare current depth against heuristic's maximal depth level */
1237 	   execute = execute && (heur->maxdepth == -1 || depth <= heur->maxdepth);
1238 	
1239 	   /* if the heuristic was delayed, execute it anyway */
1240 	   execute = execute || (heur->delaypos >= 0);
1241 	
1242 	   /* if the heuristic should be called after plunging but not during plunging, delay it if we are in plunging */
1243 	   if( execute
1244 	      && ((heurtiming == SCIP_HEURTIMING_AFTERLPNODE
1245 	            && (heur->timingmask & SCIP_HEURTIMING_AFTERLPNODE) == 0
1246 	            && (heur->timingmask & SCIP_HEURTIMING_AFTERLPPLUNGE) > 0)
1247 	         || (heurtiming == SCIP_HEURTIMING_AFTERPSEUDONODE
1248 	            && (heur->timingmask & SCIP_HEURTIMING_AFTERPSEUDONODE) == 0
1249 	            && (heur->timingmask & SCIP_HEURTIMING_AFTERPSEUDOPLUNGE) > 0)) )
1250 	   {
1251 	      /* the heuristic should be delayed until plunging is finished */
1252 	      execute = FALSE;
1253 	      *delayed = TRUE;
1254 	   }
1255 	
1256 	   /* execute heuristic only if its timing mask fits the current point in the node solving process */
1257 	   execute = execute && (heur->timingmask & heurtiming) > 0;
1258 	
1259 	   return execute;
1260 	}
1261 	
1262 	/** calls execution method of primal heuristic */
1263 	SCIP_RETCODE SCIPheurExec(
1264 	   SCIP_HEUR*            heur,               /**< primal heuristic */
1265 	   SCIP_SET*             set,                /**< global SCIP settings */
1266 	   SCIP_PRIMAL*          primal,             /**< primal data */
1267 	   int                   depth,              /**< depth of current node */
1268 	   int                   lpstateforkdepth,   /**< depth of the last node with solved LP */
1269 	   SCIP_HEURTIMING       heurtiming,         /**< current point in the node solving process */
1270 	   SCIP_Bool             nodeinfeasible,     /**< was the current node already detected to be infeasible? */
1271 	   int*                  ndelayedheurs,      /**< pointer to count the number of delayed heuristics */
1272 	   SCIP_RESULT*          result              /**< pointer to store the result of the callback method */
1273 	   )
1274 	{
1275 	   SCIP_Bool execute;
1276 	   SCIP_Bool delayed;
1277 	
1278 	   assert(heur != NULL);
1279 	   assert(heur->heurexec != NULL);
1280 	   assert(heur->freq >= -1);
1281 	   assert(heur->freqofs >= 0);
1282 	   assert(heur->maxdepth >= -1);
1283 	   assert(set != NULL);
1284 	   assert(set->scip != NULL);
1285 	   assert(primal != NULL);
1286 	   assert(depth >= 0 || heurtiming == SCIP_HEURTIMING_BEFOREPRESOL || heurtiming == SCIP_HEURTIMING_DURINGPRESOLLOOP);
1287 	   assert(ndelayedheurs != NULL);
1288 	   assert(result != NULL);
1289 	
1290 	   *result = SCIP_DIDNOTRUN;
1291 	
1292 	   delayed = FALSE;
1293 	   execute = SCIPheurShouldBeExecuted(heur, depth, lpstateforkdepth, heurtiming, &delayed);
1294 	
1295 	   if( delayed )
1296 	   {
1297 	      assert(!execute);
1298 	      *result = SCIP_DELAYED;
1299 	   }
1300 	
1301 	   if( execute )
1302 	   {
1303 	      SCIP_Longint oldnsolsfound;
1304 	      SCIP_Longint oldnbestsolsfound;
1305 	
1306 	      SCIPsetDebugMsg(set, "executing primal heuristic <%s> in depth %d (delaypos: %d)\n", heur->name, depth, heur->delaypos);
1307 	
1308 	      oldnsolsfound = primal->nsolsfound;
1309 	      oldnbestsolsfound = primal->nbestsolsfound;
1310 	
1311 	      /* start timing */
1312 	      SCIPclockStart(heur->heurclock, set);
1313 	
1314 	      /* call external method */
1315 	      SCIP_CALL( heur->heurexec(set->scip, heur, heurtiming, nodeinfeasible, result) );
1316 	
1317 	      /* stop timing */
1318 	      SCIPclockStop(heur->heurclock, set);
1319 	
1320 	      /* evaluate result */
1321 	      if( *result != SCIP_FOUNDSOL
1322 	         && *result != SCIP_DIDNOTFIND
1323 	         && *result != SCIP_DIDNOTRUN
1324 	         && *result != SCIP_DELAYED
1325 	         && *result != SCIP_UNBOUNDED )
1326 	      {
1327 	         SCIPerrorMessage("execution method of primal heuristic <%s> returned invalid result <%d>\n", 
1328 	            heur->name, *result);
1329 	         return SCIP_INVALIDRESULT;
1330 	      }
1331 	      if( *result != SCIP_DIDNOTRUN && *result != SCIP_DELAYED )
1332 	         heur->ncalls++;
1333 	      heur->nsolsfound += primal->nsolsfound - oldnsolsfound;
1334 	      heur->nbestsolsfound += primal->nbestsolsfound - oldnbestsolsfound;
1335 	
1336 	      /* update delay position of heuristic */
1337 	      if( *result != SCIP_DELAYED && heur->delaypos != -1 )
1338 	      {
1339 	         heur->delaypos = -1;
1340 	         set->heurssorted = FALSE;
1341 	      }
1342 	   }
1343 	   assert(*result == SCIP_DIDNOTRUN || *result == SCIP_DELAYED || *result == SCIP_UNBOUNDED || heur->delaypos == -1);
1344 	
1345 	   /* check if the heuristic was (still) delayed */
1346 	   if( *result == SCIP_DELAYED || heur->delaypos >= 0 )
1347 	   {
1348 	      SCIPsetDebugMsg(set, "delaying execution of primal heuristic <%s> in depth %d (delaypos: %d), heur was%s delayed before, had delaypos %d\n",
1349 	         heur->name, depth, *ndelayedheurs, heur->delaypos >= 0 ? "" : " not", heur->delaypos);
1350 	
1351 	      /* mark the heuristic delayed */
1352 	      if( heur->delaypos != *ndelayedheurs )
1353 	      {
1354 	         heur->delaypos = *ndelayedheurs;
1355 	         set->heurssorted = FALSE;
1356 	      }
1357 	      (*ndelayedheurs)++;
1358 	   }
1359 	
1360 	   return SCIP_OKAY;
1361 	}
1362 	
1363 	/** gets user data of primal heuristic */
1364 	SCIP_HEURDATA* SCIPheurGetData(
1365 	   SCIP_HEUR*            heur                /**< primal heuristic */
1366 	   )
1367 	{
1368 	   assert(heur != NULL);
1369 	
1370 	   return heur->heurdata;
1371 	}
1372 	
1373 	/** sets user data of primal heuristic; user has to free old data in advance! */
1374 	void SCIPheurSetData(
1375 	   SCIP_HEUR*            heur,               /**< primal heuristic */
1376 	   SCIP_HEURDATA*        heurdata            /**< new primal heuristic user data */
1377 	   )
1378 	{
1379 	   assert(heur != NULL);
1380 	
1381 	   heur->heurdata = heurdata;
1382 	}
1383 	
1384 	/* new callback setter methods */
1385 	
1386 	/** sets copy callback of primal heuristic */
1387 	void SCIPheurSetCopy(
1388 	   SCIP_HEUR*            heur,               /**< primal heuristic */
1389 	   SCIP_DECL_HEURCOPY    ((*heurcopy))       /**< copy callback of primal heuristic or NULL if you don't want to copy your plugin into sub-SCIPs */
1390 	   )
1391 	{
1392 	   assert(heur != NULL);
1393 	
1394 	   heur->heurcopy = heurcopy;
1395 	}
1396 	
1397 	/** sets destructor callback of primal heuristic */
1398 	void SCIPheurSetFree(
1399 	   SCIP_HEUR*            heur,               /**< primal heuristic */
1400 	   SCIP_DECL_HEURFREE    ((*heurfree))       /**< destructor of primal heuristic */
1401 	   )
1402 	{
1403 	   assert(heur != NULL);
1404 	
1405 	   heur->heurfree = heurfree;
1406 	}
1407 	
1408 	/** sets initialization callback of primal heuristic */
1409 	void SCIPheurSetInit(
1410 	   SCIP_HEUR*            heur,               /**< primal heuristic */
1411 	   SCIP_DECL_HEURINIT    ((*heurinit))       /**< initialize primal heuristic */
1412 	   )
1413 	{
1414 	   assert(heur != NULL);
1415 	
1416 	   heur->heurinit = heurinit;
1417 	}
1418 	
1419 	/** sets deinitialization callback of primal heuristic */
1420 	void SCIPheurSetExit(
1421 	   SCIP_HEUR*            heur,               /**< primal heuristic */
1422 	   SCIP_DECL_HEUREXIT    ((*heurexit))       /**< deinitialize primal heuristic */
1423 	   )
1424 	{
1425 	   assert(heur != NULL);
1426 	
1427 	   heur->heurexit = heurexit;
1428 	}
1429 	
1430 	/** sets solving process initialization callback of primal heuristic */
1431 	void SCIPheurSetInitsol(
1432 	   SCIP_HEUR*            heur,               /**< primal heuristic */
1433 	   SCIP_DECL_HEURINITSOL ((*heurinitsol))    /**< solving process initialization callback of primal heuristic */
1434 	   )
1435 	{
1436 	   assert(heur != NULL);
1437 	
1438 	   heur->heurinitsol = heurinitsol;
1439 	}
1440 	
1441 	/** sets solving process deinitialization callback of primal heuristic */
1442 	void SCIPheurSetExitsol(
1443 	   SCIP_HEUR*            heur,               /**< primal heuristic */
1444 	   SCIP_DECL_HEUREXITSOL ((*heurexitsol))    /**< solving process deinitialization callback of primal heuristic */
1445 	   )
1446 	{
1447 	   assert(heur != NULL);
1448 	
1449 	   heur->heurexitsol = heurexitsol;
1450 	}
1451 	
1452 	/** gets name of primal heuristic */
1453 	const char* SCIPheurGetName(
1454 	   SCIP_HEUR*            heur                /**< primal heuristic */
1455 	   )
1456 	{
1457 	   assert(heur != NULL);
1458 	
1459 	   return heur->name;
1460 	}
1461 	
1462 	/** gets description of primal heuristic */
1463 	const char* SCIPheurGetDesc(
1464 	   SCIP_HEUR*            heur                /**< primal heuristic */
1465 	   )
1466 	{
1467 	   assert(heur != NULL);
1468 	
1469 	   return heur->desc;
1470 	}
1471 	
1472 	/** gets display character of primal heuristic */
1473 	char SCIPheurGetDispchar(
1474 	   SCIP_HEUR*            heur                /**< primal heuristic */
1475 	   )
1476 	{
1477 	   assert(heur != NULL);
1478 	
1479 	   return heur->dispchar;
1480 	}
1481 	
1482 	/** returns the timing mask of the heuristic */
1483 	SCIP_HEURTIMING SCIPheurGetTimingmask(
1484 	   SCIP_HEUR*            heur                /**< primal heuristic */
1485 	   )
1486 	{
1487 	   assert(heur != NULL);
1488 	
1489 	   return heur->timingmask;
1490 	}
1491 	
1492 	/** sets new timing mask for heuristic */
1493 	void SCIPheurSetTimingmask(
1494 	   SCIP_HEUR*            heur,               /**< primal heuristic */
1495 	   SCIP_HEURTIMING       timingmask          /**< new timing mask of heuristic */
1496 	   )
1497 	{
1498 	   assert(heur != NULL);
1499 	
1500 	   heur->timingmask = timingmask;
1501 	}
1502 	
1503 	/** does the heuristic use a secondary SCIP instance? */
1504 	SCIP_Bool SCIPheurUsesSubscip(
1505 	   SCIP_HEUR*            heur                /**< primal heuristic */
1506 	   )
1507 	{
1508 	   assert(heur != NULL);
1509 	
1510 	   return heur->usessubscip;
1511 	}
1512 	
1513 	/** gets priority of primal heuristic */
1514 	int SCIPheurGetPriority(
1515 	   SCIP_HEUR*            heur                /**< primal heuristic */
1516 	   )
1517 	{
1518 	   assert(heur != NULL);
1519 	
1520 	   return heur->priority;
1521 	}
1522 	
1523 	/** sets priority of primal heuristic */
1524 	void SCIPheurSetPriority(
1525 	   SCIP_HEUR*            heur,               /**< primal heuristic */
1526 	   SCIP_SET*             set,                /**< global SCIP settings */
1527 	   int                   priority            /**< new priority of the primal heuristic */
1528 	   )
1529 	{
1530 	   assert(heur != NULL);
1531 	   assert(set != NULL);
1532 	
1533 	   heur->priority = priority;
1534 	   set->heurssorted = FALSE;
1535 	}
1536 	
1537 	/** gets frequency of primal heuristic */
1538 	int SCIPheurGetFreq(
1539 	   SCIP_HEUR*            heur                /**< primal heuristic */
1540 	   )
1541 	{
1542 	   assert(heur != NULL);
1543 	
1544 	   return heur->freq;
1545 	}
1546 	
1547 	/** sets frequency of primal heuristic */
1548 	void SCIPheurSetFreq(
1549 	   SCIP_HEUR*            heur,               /**< primal heuristic */
1550 	   int                   freq                /**< new frequency of heuristic */
1551 	   )
1552 	{
1553 	   assert(heur != NULL);
1554 	
1555 	   heur->freq = freq;
1556 	}
1557 	
1558 	/** gets frequency offset of primal heuristic */
1559 	int SCIPheurGetFreqofs(
1560 	   SCIP_HEUR*            heur                /**< primal heuristic */
1561 	   )
1562 	{
1563 	   assert(heur != NULL);
1564 	
1565 	   return heur->freqofs;
1566 	}
1567 	
1568 	/** gets maximal depth level for calling primal heuristic (returns -1, if no depth limit exists) */
1569 	int SCIPheurGetMaxdepth(
1570 	   SCIP_HEUR*            heur                /**< primal heuristic */
1571 	   )
1572 	{
1573 	   assert(heur != NULL);
1574 	
1575 	   return heur->maxdepth;
1576 	}
1577 	
1578 	/** gets the number of times, the heuristic was called and tried to find a solution */
1579 	SCIP_Longint SCIPheurGetNCalls(
1580 	   SCIP_HEUR*            heur                /**< primal heuristic */
1581 	   )
1582 	{
1583 	   assert(heur != NULL);
1584 	
1585 	   return heur->ncalls;
1586 	}
1587 	
1588 	/** gets the number of primal feasible solutions found by this heuristic */
1589 	SCIP_Longint SCIPheurGetNSolsFound(
1590 	   SCIP_HEUR*            heur                /**< primal heuristic */
1591 	   )
1592 	{
1593 	   assert(heur != NULL);
1594 	
1595 	   return heur->nsolsfound;
1596 	}
1597 	
1598 	/** gets the number of new best primal feasible solutions found by this heuristic */
1599 	SCIP_Longint SCIPheurGetNBestSolsFound(
1600 	   SCIP_HEUR*            heur                /**< primal heuristic */
1601 	   )
1602 	{
1603 	   assert(heur != NULL);
1604 	
1605 	   return heur->nbestsolsfound;
1606 	}
1607 	
1608 	/** is primal heuristic initialized? */
1609 	SCIP_Bool SCIPheurIsInitialized(
1610 	   SCIP_HEUR*            heur                /**< primal heuristic */
1611 	   )
1612 	{
1613 	   assert(heur != NULL);
1614 	
1615 	   return heur->initialized;
1616 	}
1617 	
1618 	/** enables or disables all clocks of \p heur, depending on the value of the flag */
1619 	void SCIPheurEnableOrDisableClocks(
1620 	   SCIP_HEUR*            heur,               /**< the heuristic for which all clocks should be enabled or disabled */
1621 	   SCIP_Bool             enable              /**< should the clocks of the heuristic be enabled? */
1622 	   )
1623 	{
1624 	   assert(heur != NULL);
1625 	
1626 	   SCIPclockEnableOrDisable(heur->setuptime, enable);
1627 	   SCIPclockEnableOrDisable(heur->heurclock, enable);
1628 	}
1629 	
1630 	/** gets time in seconds used in this heuristic for setting up for next stages */
1631 	SCIP_Real SCIPheurGetSetupTime(
1632 	   SCIP_HEUR*            heur                /**< primal heuristic */
1633 	   )
1634 	{
1635 	   assert(heur != NULL);
1636 	
1637 	   return SCIPclockGetTime(heur->setuptime);
1638 	}
1639 	
1640 	/** gets time in seconds used in this heuristic */
1641 	SCIP_Real SCIPheurGetTime(
1642 	   SCIP_HEUR*            heur                /**< primal heuristic */
1643 	   )
1644 	{
1645 	   assert(heur != NULL);
1646 	
1647 	   return SCIPclockGetTime(heur->heurclock);
1648 	}
1649 	
1650 	/** returns array of divesets of this primal heuristic, or NULL if it has no divesets */
1651 	SCIP_DIVESET** SCIPheurGetDivesets(
1652 	   SCIP_HEUR*            heur                /**< primal heuristic */
1653 	   )
1654 	{
1655 	   assert(heur != NULL);
1656 	
1657 	   return heur->divesets;
1658 	}
1659 	
1660 	/** returns the number of divesets of this primal heuristic */
1661 	int SCIPheurGetNDivesets(
1662 	   SCIP_HEUR*            heur                /**< primal heuristic */
1663 	   )
1664 	{
1665 	   assert(heur != NULL);
1666 	
1667 	   return heur->ndivesets;
1668 	}
1669 	
1670 	/** Perform breadth-first (BFS) search on the variable constraint graph.
1671 	 *
1672 	 *  The result of the algorithm is that the \p distances array contains the correct distances for
1673 	 *  every variable from the start variables. The distance of a variable can then be accessed through its
1674 	 *  problem index (calling SCIPvarGetProbindex()).
1675 	 *  Hence, The method assumes that the length of \p distances is at least
1676 	 *  SCIPgetNVars().
1677 	 *  Variables that are not connected through constraints to the start variables have a distance of -1.
1678 	 *
1679 	 *  Limits can be provided to further restrict the breadth-first search. If a distance limit is given,
1680 	 *  the search will be performed until the first variable at this distance is popped from the queue, i.e.,
1681 	 *  all variables with a distance < maxdistance have been labeled by the search.
1682 	 *  If a variable limit is given, the search stops after it completes the distance level at which
1683 	 *  the limit was reached. Hence, more variables may be actually labeled.
1684 	 *  The start variables are accounted for those variable limits.
1685 	 *
1686 	 *  If no variable variable constraint graph is provided, the method will create one and free it at the end
1687 	 *  This is useful for a single use of the variable constraint graph. For several consecutive uses,
1688 	 *  it is advised to create a variable constraint graph via SCIPvariableGraphCreate().
1689 	 */
1690 	SCIP_RETCODE SCIPvariablegraphBreadthFirst(
1691 	   SCIP*                 scip,               /**< SCIP data structure */
1692 	   SCIP_VGRAPH*          vargraph,           /**< pointer to the variable graph, or NULL to let the function create a local graph */
1693 	   SCIP_VAR**            startvars,          /**< array of start variables to calculate distance from */
1694 	   int                   nstartvars,         /**< number of starting variables, at least 1 */
1695 	   int*                  distances,          /**< array to keep distance in vargraph from start variables for every variable */
1696 	   int                   maxdistance,        /**< maximum distance >= 0 from start variable (INT_MAX for complete BFS) */
1697 	   int                   maxvars,            /**< maximum number of variables to compute distance for */
1698 	   int                   maxbinintvars       /**< maximum number of binary or integer variables to compute distance for */
1699 	   )
1700 	{
1701 	   SCIP_VAR** vars;
1702 	
1703 	   int* queue;
1704 	   int  nvars;
1705 	   int i;
1706 	   int currlvlidx;
1707 	   int nextlvlidx;
1708 	   int increment = 1;
1709 	   int currentdistance;
1710 	   int nbinintvarshit;
1711 	   int nvarshit;
1712 	   int nbinvars;
1713 	   int nintvars;
1714 	   int nbinintvars;
1715 	   SCIP_VAR** varbuffer;
1716 	   SCIP_Bool localvargraph;
1717 	
1718 	   assert(scip != NULL);
1719 	   assert(startvars != NULL);
1720 	   assert(nstartvars >= 1);
1721 	   assert(distances != NULL);
1722 	   assert(maxdistance >= 0);
1723 	
1724 	   /* get variable data */
1725 	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
1726 	
1727 	   if( nvars == 0 )
1728 	      return SCIP_OKAY;
1729 	
1730 	   nbinintvars = nbinvars + nintvars;
1731 	
1732 	   SCIP_CALL( SCIPallocBufferArray(scip, &queue, nvars) );
1733 	   SCIP_CALL( SCIPallocClearBufferArray(scip, &varbuffer, nvars) );
1734 	
1735 	   /* create a variable graph locally for this method, if none is provided */
1736 	   if( vargraph == NULL )
1737 	   {
1738 	      SCIP_CALL( SCIPvariableGraphCreate(scip, &vargraph, FALSE, 1.0, NULL) );
1739 	      localvargraph = TRUE;
1740 	   }
1741 	   else
1742 	      localvargraph = FALSE;
1743 	
1744 	   SCIPhashtableRemoveAll(vargraph->visitedconss);
1745 	
1746 	   /* initialize distances to -1 */
1747 	   for( i = 0; i < nvars; ++i )
1748 	   {
1749 	      queue[i] = -1;
1750 	      distances[i] = -1;
1751 	   }
1752 	
1753 	   nvarshit = 0;
1754 	   nbinintvarshit = 0;
1755 	   /* initialize distances for starting variables and add them to the queue */
1756 	   for( i = 0; i < nstartvars; ++i )
1757 	   {
1758 	      int probindex = SCIPvarGetProbindex(startvars[i]);
1759 	      assert(probindex >= 0);
1760 	      /* start variables have a distance of 0 */
1761 	      distances[probindex] = 0;
1762 	      queue[i] = probindex;
1763 	      nvarshit++;
1764 	
1765 	      if( probindex < nbinintvars )
1766 	         nbinintvarshit++;
1767 	   }
1768 	   currlvlidx = 0;
1769 	   nextlvlidx = nvars - 1;
1770 	
1771 	   /* loop over the queue and pop the next variable, starting with start variables */
1772 	   do
1773 	   {
1774 	      SCIP_VAR* currvar;
1775 	      int c;
1776 	      int varpos;
1777 	
1778 	      currvar = vars[queue[currlvlidx]];
1779 	      varpos = SCIPvarGetProbindex(currvar);
1780 	      currentdistance = distances[varpos];
1781 	      assert(currentdistance >= 0);
1782 	
1783 	      /* distances must only be computed up to maxdistance  */
1784 	      assert(currentdistance <= maxdistance);
1785 	
1786 	      /* check for termination because maximum distance has been reached */
1787 	      if( currentdistance == maxdistance )
1788 	         break;
1789 	
1790 	      assert(varpos >= 0);
1791 	
1792 	      /* loop over variable constraints and enqueue variables that were not visited yet */
1793 	      for( c = 0; c < vargraph->nvarconss[varpos]; ++c )
1794 	      {
1795 	         int nconsvars;
1796 	         int v;
1797 	         SCIP_Bool success;
1798 	         SCIP_CONS* cons = vargraph->varconss[varpos][c];
1799 	
1800 	         /* check first if this constraint has already been visited */
1801 	         if( SCIPhashtableExists(vargraph->visitedconss, (void *)cons) )
1802 	            continue;
1803 	
1804 	         /* request number of constraint variables */
1805 	         SCIP_CALL( SCIPgetConsNVars(scip, cons, &nconsvars, &success) );
1806 	
1807 	         if( !success )
1808 	            continue;
1809 	
1810 	         /* collect constraint variables in buffer */
1811 	         SCIP_CALL( SCIPgetConsVars(scip, cons, varbuffer, nvars, &success) );
1812 	
1813 	         if( !success )
1814 	            continue;
1815 	
1816 	         /* collect previously unvisited variables of the constraint and enqueue them for breadth-first search */
1817 	         for( v = 0; v < nconsvars; ++v )
1818 	         {
1819 	            SCIP_VAR* nextvar = varbuffer[v];
1820 	            int nextvarpos;
1821 	            assert(nextvar != NULL);
1822 	            if( !SCIPvarIsActive(nextvar) )
1823 	               continue;
1824 	
1825 	            nextvarpos = SCIPvarGetProbindex(nextvar);
1826 	            assert(nextvarpos >= 0);
1827 	
1828 	            /* insert variables that were not considered yet into the next level queue */
1829 	            if( distances[nextvarpos] == -1 )
1830 	            {
1831 	               distances[nextvarpos] = currentdistance + 1;
1832 	               queue[nextlvlidx] = nextvarpos;
1833 	               nextlvlidx -= increment;
1834 	
1835 	               nvarshit++;
1836 	               if( nextvarpos < nbinintvars )
1837 	                  ++nbinintvarshit;
1838 	            }
1839 	         } /* end constraint variables loop */
1840 	
1841 	         /* mark the constraint as visited */
1842 	         SCIP_CALL( SCIPhashtableInsert(vargraph->visitedconss, (void *)cons) );
1843 	      } /* end constraint loop */
1844 	
1845 	      queue[currlvlidx] = -1;
1846 	      currlvlidx += increment;
1847 	
1848 	      /* check if we need to swap current and next level index and reverse the increment */
1849 	      if( currlvlidx == nvars || currlvlidx == 0 || queue[currlvlidx] == -1 || currlvlidx == nextlvlidx )
1850 	      {
1851 	         /* break early if the distance has been determined for enough variables */
1852 	         if( nvarshit >= maxvars || nbinintvarshit >= maxbinintvars )
1853 	            break;
1854 	
1855 	         /* increment knows whether we are currently looping upwards (all variables with odd distance) or downwards the
1856 	          * queue
1857 	          */
1858 	         if( increment == +1 )
1859 	         {
1860 	            currlvlidx = nvars - 1;
1861 	            nextlvlidx = 0;
1862 	            increment = -1;
1863 	         }
1864 	         else
1865 	         {
1866 	            currlvlidx = 0;
1867 	            nextlvlidx = nvars - 1;
1868 	            increment = +1;
1869 	         }
1870 	      }
1871 	   }
1872 	   while( queue[currlvlidx] != -1 && distances[queue[currlvlidx]] >= currentdistance );
1873 	
1874 	   SCIPfreeBufferArray(scip, &varbuffer);
1875 	   SCIPfreeBufferArray(scip, &queue);
1876 	
1877 	   /* free also the variable graph, if it wasn't provided by the caller */
1878 	   if( localvargraph )
1879 	   {
1880 	      SCIPvariableGraphFree(scip, &vargraph);
1881 	   }
1882 	
1883 	   return SCIP_OKAY;
1884 	}
1885 	
1886 	/* fills variable graph data structure
1887 	 *
1888 	 * loops over global problem constraints and creates a mapping from the variables to their respective constraints
1889 	 */
1890 	static
1891 	SCIP_RETCODE fillVariableGraph(
1892 	   SCIP*                 scip,               /**< SCIP data structure */
1893 	   SCIP_VGRAPH*          vargraph,           /**< variable graph data structure for breadth-first-search neighborhoods */
1894 	   SCIP_Bool             relaxdenseconss,    /**< should dense constraints (at least as dense as \p density) be
1895 	                                              *   ignored by connectivity graph? */
1896 	   SCIP_Real             relaxdensity,       /**< density (with respect to number of variables) to relax constraint from graph */
1897 	   int*                  nrelaxedconstraints  /**< pointer to store the number of constraints that were relaxed, or NULL if not needed */
1898 	   )
1899 	{
1900 	   SCIP_CONS** conss;
1901 	   int nconss;
1902 	   int nvars;
1903 	   int c;
1904 	   int relaxlimit;
1905 	   SCIP_VAR** varbuffer;
1906 	
1907 	   assert(scip != NULL);
1908 	   assert(vargraph != NULL);
1909 	
1910 	   conss = SCIPgetConss(scip);
1911 	   nconss = SCIPgetNConss(scip);
1912 	
1913 	   nvars = SCIPgetNVars(scip);
1914 	   SCIP_CALL( SCIPallocBufferArray(scip, &varbuffer, nvars) );
1915 	
1916 	   if( nrelaxedconstraints != NULL )
1917 	      *nrelaxedconstraints = 0;
1918 	
1919 	   relaxlimit = (int)(relaxdensity * nvars);
1920 	
1921 	   for( c = 0; c < nconss; ++c )
1922 	   {
1923 	      int nconsvars;
1924 	      int v;
1925 	      SCIP_Bool success;
1926 	      SCIP_CONS* cons = conss[c];
1927 	
1928 	      /* we only consider constraints that are checkable */
1929 	      if( !SCIPconsIsChecked(cons) )
1930 	         continue;
1931 	
1932 	      /* request number of variables */
1933 	      SCIP_CALL( SCIPgetConsNVars(scip, cons, &nconsvars, &success) );
1934 	
1935 	      if( !success )
1936 	         continue;
1937 	
1938 	      /* relax constraints with density above the allowed number of free variables */
1939 	      if( relaxdenseconss && nconsvars >= relaxlimit )
1940 	      {
1941 	         if( nrelaxedconstraints != NULL )
1942 	            ++(*nrelaxedconstraints);
1943 	
1944 	         continue;
1945 	      }
1946 	
1947 	      /* collect constraint variables in buffer */
1948 	      SCIP_CALL( SCIPgetConsVars(scip, cons, varbuffer, nvars, &success) );
1949 	
1950 	      if( !success )
1951 	         continue;
1952 	
1953 	      /* loop over constraint variables and add this constraint to them if they are active */
1954 	      for( v = 0; v < nconsvars; ++v )
1955 	      {
1956 	         int varpos = SCIPvarGetProbindex(varbuffer[v]);
1957 	
1958 	         /* skip inactive variables */
1959 	         if( varpos == -1 )
1960 	            continue;
1961 	
1962 	         /* ensure array size */
1963 	         if( vargraph->varconssize[varpos] == vargraph->nvarconss[varpos]  )
1964 	         {
1965 	            int newmem = SCIPcalcMemGrowSize(scip, vargraph->nvarconss[varpos] + 1);
1966 	
1967 	            assert(newmem > vargraph->varconssize[varpos]);
1968 	
1969 	            if( vargraph->varconss[varpos] == NULL )
1970 	            {
1971 	               SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vargraph->varconss[varpos], newmem) );
1972 	            }
1973 	            else
1974 	            {
1975 	               SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &vargraph->varconss[varpos], vargraph->varconssize[varpos], newmem) ); /*lint !e866*/
1976 	            }
1977 	            vargraph->varconssize[varpos] = newmem;
1978 	         }
1979 	
1980 	         assert(vargraph->nvarconss[varpos] < vargraph->varconssize[varpos]);
1981 	
1982 	         /* add constraint to constraint array for this variable */
1983 	         vargraph->varconss[varpos][vargraph->nvarconss[varpos]] = cons;
1984 	         vargraph->nvarconss[varpos] += 1;
1985 	      }
1986 	   }
1987 	
1988 	   /* free the buffer */
1989 	   SCIPfreeBufferArray(scip, &varbuffer);
1990 	
1991 	   return SCIP_OKAY;
1992 	}
1993 	
1994 	/** initialization method of variable graph data structure */
1995 	SCIP_RETCODE SCIPvariableGraphCreate(
1996 	   SCIP*                 scip,               /**< SCIP data structure */
1997 	   SCIP_VGRAPH**         vargraph,           /**< pointer to the variable graph */
1998 	   SCIP_Bool             relaxdenseconss,    /**< should dense constraints (at least as dense as \p density) be
1999 	                                              *   ignored by connectivity graph? */
2000 	   SCIP_Real             relaxdensity,       /**< density (with respect to number of variables) to relax constraint from graph */
2001 	   int*                  nrelaxedconstraints  /**< pointer to store the number of constraints that were relaxed, or NULL if not needed */
2002 	   )
2003 	{
2004 	   int nvars;
2005 	   int nconss;
2006 	
2007 	   assert(scip != NULL);
2008 	   assert(vargraph != NULL);
2009 	
2010 	   nvars = SCIPgetNVars(scip);
2011 	   nconss = SCIPgetNConss(scip);
2012 	
2013 	   if( nvars == 0 )
2014 	      return SCIP_OKAY;
2015 	
2016 	   SCIP_CALL( SCIPallocBlockMemory(scip, vargraph) );
2017 	
2018 	   SCIP_CALL( SCIPhashtableCreate(&(*vargraph)->visitedconss, SCIPblkmem(scip), 2 * nconss, SCIPhashGetKeyStandard,
2019 	         SCIPhashKeyEqPtr, SCIPhashKeyValPtr, NULL) );
2020 	
2021 	   /* allocate and clear memory */
2022 	   SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(*vargraph)->varconss, nvars) );
2023 	   SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(*vargraph)->nvarconss, nvars) );
2024 	   SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(*vargraph)->varconssize, nvars) );
2025 	
2026 	   /* fill the variable graph with variable-constraint mapping for breadth-first search*/
2027 	   SCIP_CALL( fillVariableGraph(scip, *vargraph, relaxdenseconss, relaxdensity, nrelaxedconstraints) );
2028 	
2029 	   return SCIP_OKAY;
2030 	}
2031 	
2032 	/** deinitialization method of variable graph data structure */
2033 	void SCIPvariableGraphFree(
2034 	   SCIP*                 scip,               /**< SCIP data structure */
2035 	   SCIP_VGRAPH**         vargraph            /**< pointer to the variable graph */
2036 	   )
2037 	{
2038 	   int nvars;
2039 	   int v;
2040 	   assert(scip != NULL);
2041 	   assert(vargraph != NULL);
2042 	
2043 	   nvars = SCIPgetNVars(scip);
2044 	
2045 	   for( v = nvars - 1; v >= 0; --v )
2046 	   {
2047 	      SCIPfreeBlockMemoryArrayNull(scip, &(*vargraph)->varconss[v], (*vargraph)->varconssize[v]); /*lint !e866*/
2048 	   }
2049 	
2050 	   /* allocate and clear memory */
2051 	   SCIPfreeBlockMemoryArray(scip, &(*vargraph)->varconssize, nvars);
2052 	   SCIPfreeBlockMemoryArray(scip, &(*vargraph)->nvarconss, nvars);
2053 	   SCIPfreeBlockMemoryArray(scip, &(*vargraph)->varconss, nvars);
2054 	
2055 	   SCIPhashtableFree(&(*vargraph)->visitedconss);
2056 	
2057 	   SCIPfreeBlockMemory(scip, vargraph);
2058 	}
2059