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_adaptivediving.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  diving heuristic that selects adaptively between the existing, public dive sets
28   	 * @author Gregor Hendel
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#include <assert.h>
34   	#include <string.h>
35   	
36   	#include "scip/heur_adaptivediving.h"
37   	#include "scip/heuristics.h"
38   	#include "scip/scipdefplugins.h"
39   	
40   	#define HEUR_NAME             "adaptivediving"
41   	#define HEUR_DESC             "diving heuristic that selects adaptively between the existing, public divesets"
42   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_DIVING
43   	#define HEUR_PRIORITY         -70000
44   	#define HEUR_FREQ             5
45   	#define HEUR_FREQOFS          3
46   	#define HEUR_MAXDEPTH         -1
47   	#define HEUR_TIMING           SCIP_HEURTIMING_AFTERLPPLUNGE
48   	#define HEUR_USESSUBSCIP      FALSE  /**< does the heuristic use a secondary SCIP instance? */
49   	
50   	#define DIVESETS_INITIALSIZE 10
51   	#define DEFAULT_INITIALSEED 13
52   	
53   	/*
54   	 * Default parameter settings
55   	 */
56   	#define DEFAULT_SELTYPE 'w'
57   	#define DEFAULT_SCORETYPE 'c'                /**< score parameter for selection: minimize either average 'n'odes, LP 'i'terations,
58   	                                              *  backtrack/'c'onflict ratio, 'd'epth, 1 / 's'olutions, or
59   	                                              *  1 / solutions'u'ccess */
60   	#define DEFAULT_USEADAPTIVECONTEXT FALSE
61   	#define DEFAULT_SELCONFIDENCECOEFF 10.0      /**< coefficient c to decrease initial confidence (calls + 1.0) / (calls + c) in scores */
62   	#define DEFAULT_EPSILON             1.0      /**< parameter that increases probability of exploration among divesets (only active if seltype is 'e') */
63   	#define DEFAULT_MAXLPITERQUOT       0.1      /**< maximal fraction of diving LP iterations compared to node LP iterations */
64   	#define DEFAULT_MAXLPITEROFS      1500L      /**< additional number of allowed LP iterations */
65   	#define DEFAULT_BESTSOLWEIGHT      10.0      /**< weight of incumbent solutions compared to other solutions in computation of LP iteration limit */
66   	
67   	/* locally defined heuristic data */
68   	struct SCIP_HeurData
69   	{
70   	   /* data structures used internally */
71   	   SCIP_SOL*             sol;                /**< working solution */
72   	   SCIP_RANDNUMGEN*      randnumgen;         /**< random number generator for selection */
73   	   SCIP_DIVESET**        divesets;           /**< publicly available divesets from diving heuristics */
74   	   int                   ndivesets;          /**< number of publicly available divesets from diving heuristics */
75   	   int                   divesetssize;       /**< array size for divesets array */
76   	   int                   lastselection;      /**< stores the last selected diveset when the heuristics was run */
77   	   /* user parameters */
78   	   SCIP_Real             epsilon;            /**< parameter that increases probability of exploration among divesets (only active if seltype is 'e') */
79   	   SCIP_Real             selconfidencecoeff; /**< coefficient c to decrease initial confidence (calls + 1.0) / (calls + c) in scores */
80   	   SCIP_Real             maxlpiterquot;      /**< maximal fraction of diving LP iterations compared to node LP iterations */
81   	   SCIP_Longint          maxlpiterofs;       /**< additional number of allowed LP iterations */
82   	   SCIP_Real             bestsolweight;      /**< weight of incumbent solutions compared to other solutions in computation of LP iteration limit */
83   	   char                  seltype;            /**< selection strategy: (e)psilon-greedy, (w)eighted distribution, (n)ext diving */
84   	   char                  scoretype;          /**< score parameter for selection: minimize either average 'n'odes, LP 'i'terations,
85   	                                               *  backtrack/'c'onflict ratio, 'd'epth, 1 / 's'olutions, or
86   	                                               *  1 / solutions'u'ccess */
87   	   SCIP_Bool             useadaptivecontext; /**< should the heuristic use its own statistics, or shared statistics? */
88   	};
89   	
90   	/*
91   	 * local methods
92   	 */
93   	
94   	
95   	/** get the selection score for this dive set */
96   	static
97   	SCIP_RETCODE divesetGetSelectionScore(
98   	   SCIP_DIVESET*         diveset,            /**< diving settings data structure */
99   	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
100  	   SCIP_DIVECONTEXT      divecontext,        /**< context for diving statistics */
101  	   SCIP_Real*            scoreptr            /**< pointer to store the score */
102  	   )
103  	{
104  	   SCIP_Real confidence;
105  	
106  	   assert(scoreptr != NULL);
107  	
108  	   /* compute confidence scalar (converges towards 1 with increasing number of calls) */
109  	   confidence = (SCIPdivesetGetNCalls(diveset, divecontext) + 1.0) /
110  	            (SCIPdivesetGetNCalls(diveset, divecontext) + heurdata->selconfidencecoeff);
111  	
112  	   switch (heurdata->scoretype) {
113  	      case 'n': /* min average nodes */
114  	         *scoreptr = confidence * SCIPdivesetGetNProbingNodes(diveset, divecontext) / (SCIPdivesetGetNCalls(diveset, divecontext) + 1.0);
115  	         break;
116  	      case 'i': /* min avg LP iterations */
117  	         *scoreptr = confidence * SCIPdivesetGetNLPIterations(diveset, divecontext) / (SCIPdivesetGetNCalls(diveset, divecontext) + 1.0);
118  	         break;
119  	      case 'c': /* min backtrack / conflict ratio (the current default) */
120  	         *scoreptr = confidence * (SCIPdivesetGetNBacktracks(diveset, divecontext)) / (SCIPdivesetGetNConflicts(diveset, divecontext) + 10.0);
121  	         break;
122  	      case 'd': /* minimum average depth */
123  	         *scoreptr = SCIPdivesetGetAvgDepth(diveset, divecontext) * confidence;
124  	         break;
125  	      case 's': /* maximum number of solutions */
126  	         *scoreptr = confidence / (SCIPdivesetGetNSols(diveset, divecontext) + 1.0);
127  	         break;
128  	      case 'u': /* maximum solution success (which weighs best solutions higher) */
129  	         *scoreptr = confidence / (SCIPdivesetGetSolSuccess(diveset, divecontext) + 1.0);
130  	         break;
131  	      default:
132  	         SCIPerrorMessage("Unsupported scoring parameter '%c'\n", heurdata->scoretype);
133  	         SCIPABORT();
134  	         *scoreptr = SCIP_INVALID;
135  	         return SCIP_PARAMETERWRONGVAL;
136  	   }
137  	
138  	   return SCIP_OKAY;
139  	}
140  	
141  	/*
142  	 * Callback methods
143  	 */
144  	
145  	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
146  	static
147  	SCIP_DECL_HEURCOPY(heurCopyAdaptivediving)
148  	{  /*lint --e{715}*/
149  	   assert(scip != NULL);
150  	   assert(heur != NULL);
151  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
152  	
153  	   /* call inclusion method of primal heuristic */
154  	   SCIP_CALL( SCIPincludeHeurAdaptivediving(scip) );
155  	
156  	   return SCIP_OKAY;
157  	}
158  	
159  	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
160  	static
161  	SCIP_DECL_HEURFREE(heurFreeAdaptivediving) /*lint --e{715}*/
162  	{  /*lint --e{715}*/
163  	   SCIP_HEURDATA* heurdata;
164  	
165  	   assert(heur != NULL);
166  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
167  	   assert(scip != NULL);
168  	
169  	   /* free heuristic data */
170  	   heurdata = SCIPheurGetData(heur);
171  	   assert(heurdata != NULL);
172  	
173  	   if( heurdata->divesets != NULL )
174  	   {
175  	      SCIPfreeBlockMemoryArray(scip, &heurdata->divesets, heurdata->divesetssize);
176  	   }
177  	
178  	   SCIPfreeRandom(scip, &heurdata->randnumgen);
179  	
180  	   SCIPfreeMemory(scip, &heurdata);
181  	   SCIPheurSetData(heur, NULL);
182  	
183  	   return SCIP_OKAY;
184  	}
185  	
186  	/** find publicly available divesets and store them */
187  	static
188  	SCIP_RETCODE findAndStoreDivesets(
189  	   SCIP*                 scip,               /**< SCIP data structure */
190  	   SCIP_HEUR*            heur,               /**< the heuristic */
191  	   SCIP_HEURDATA*        heurdata            /**< heuristic data */
192  	   )
193  	{
194  	   int h;
195  	   SCIP_HEUR** heurs;
196  	
197  	   assert(scip != NULL);
198  	   assert(heur != NULL);
199  	   assert(heurdata != NULL);
200  	
201  	   heurs = SCIPgetHeurs(scip);
202  	
203  	   heurdata->divesetssize = DIVESETS_INITIALSIZE;
204  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->divesets, heurdata->divesetssize) );
205  	   heurdata->ndivesets = 0;
206  	
207  	   for( h = 0; h < SCIPgetNHeurs(scip); ++h )
208  	   {
209  	      int d;
210  	      assert(heurs[h] != NULL);
211  	
212  	      /* loop over divesets of this heuristic and check whether they are public */
213  	      for( d = 0; d < SCIPheurGetNDivesets(heurs[h]); ++d )
214  	      {
215  	         SCIP_DIVESET* diveset = SCIPheurGetDivesets(heurs[h])[d];
216  	         if( SCIPdivesetIsPublic(diveset) )
217  	         {
218  	            SCIPdebugMsg(scip, "Found publicly available diveset %s\n", SCIPdivesetGetName(diveset));
219  	
220  	            if( heurdata->ndivesets == heurdata->divesetssize )
221  	            {
222  	               int newsize = 2 * heurdata->divesetssize;
223  	               SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &heurdata->divesets, heurdata->divesetssize, newsize) );
224  	               heurdata->divesetssize = newsize;
225  	            }
226  	            heurdata->divesets[heurdata->ndivesets++] = diveset;
227  	         }
228  	         else
229  	         {
230  	            SCIPdebugMsg(scip, "Skipping private diveset %s\n", SCIPdivesetGetName(diveset));
231  	         }
232  	      }
233  	   }
234  	   return SCIP_OKAY;
235  	}
236  	
237  	/** initialization method of primal heuristic (called after problem was transformed) */
238  	static
239  	SCIP_DECL_HEURINIT(heurInitAdaptivediving) /*lint --e{715}*/
240  	{  /*lint --e{715}*/
241  	   SCIP_HEURDATA* heurdata;
242  	
243  	   assert(heur != NULL);
244  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
245  	
246  	   /* get and reset heuristic data */
247  	   heurdata = SCIPheurGetData(heur);
248  	   heurdata->lastselection = -1;
249  	   if( heurdata->divesets != NULL )
250  	   {
251  	      /* we clear the list of collected divesets to ensure reproducability and consistent state across multiple runs
252  	       * within the same SCIP data structure */
253  	      SCIPfreeBlockMemoryArray(scip, &heurdata->divesets, heurdata->divesetssize);
254  	      assert(heurdata->divesets == NULL);
255  	   }
256  	
257  	   assert(heurdata != NULL);
258  	
259  	   /* create working solution */
260  	   SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
261  	
262  	   /* initialize random seed; use problem dimensions to vary initial order between different instances */
263  	   SCIPsetRandomSeed(scip, heurdata->randnumgen,
264  	         (unsigned int)(DEFAULT_INITIALSEED + SCIPgetNOrigVars(scip) + SCIPgetNOrigConss(scip)));
265  	
266  	   return SCIP_OKAY;
267  	}
268  	
269  	
270  	/** deinitialization method of primal heuristic (called before transformed problem is freed) */
271  	static
272  	SCIP_DECL_HEUREXIT(heurExitAdaptivediving) /*lint --e{715}*/
273  	{  /*lint --e{715}*/
274  	   SCIP_HEURDATA* heurdata;
275  	
276  	   assert(heur != NULL);
277  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
278  	
279  	   /* get heuristic data */
280  	   heurdata = SCIPheurGetData(heur);
281  	   assert(heurdata != NULL);
282  	
283  	   /* free working solution */
284  	   SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
285  	
286  	   return SCIP_OKAY;
287  	}
288  	
289  	/*
290  	 * heuristic specific interface methods
291  	 */
292  	
293  	/** get LP iteration limit for diving */
294  	static
295  	SCIP_Longint getLPIterlimit(
296  	   SCIP*                 scip,               /**< SCIP data structure */
297  	   SCIP_HEUR*            heur,               /**< the heuristic */
298  	   SCIP_HEURDATA*        heurdata            /**< heuristic data */
299  	   )
300  	{
301  	   SCIP_Real nsolsfound = SCIPheurGetNSolsFound(heur) + heurdata->bestsolweight * SCIPheurGetNBestSolsFound(heur);
302  	   SCIP_Longint nlpiterations = SCIPgetNNodeLPIterations(scip);
303  	   SCIP_Longint ncalls = SCIPheurGetNCalls(heur);
304  	
305  	   SCIP_Longint nlpiterationsdive = 0;
306  	   SCIP_Longint lpiterlimit;
307  	   int i;
308  	
309  	   assert(scip != NULL);
310  	   assert(heur != NULL);
311  	   assert(heurdata != NULL);
312  	
313  	   /* loop over the divesets and collect their individual iterations */
314  	   for( i = 0; i < heurdata->ndivesets; ++i )
315  	   {
316  	      nlpiterationsdive += SCIPdivesetGetNLPIterations(heurdata->divesets[i], SCIP_DIVECONTEXT_ADAPTIVE);
317  	   }
318  	
319  	   /* compute the iteration limit */
320  	   lpiterlimit = (SCIP_Longint)(heurdata->maxlpiterquot * (nsolsfound+1.0)/(ncalls+1.0) * nlpiterations);
321  	   lpiterlimit += heurdata->maxlpiterofs;
322  	   lpiterlimit -= nlpiterationsdive;
323  	
324  	   return lpiterlimit;
325  	}
326  	
327  	#ifdef SCIP_DEBUG
328  	/** print array for debug purpose */
329  	static
330  	char* printRealArray(
331  	   char*                 strbuf,             /**< string buffer array */
332  	   SCIP_Real*            elems,              /**< array elements */
333  	   int                   nelems              /**< number of elements */
334  	   )
335  	{
336  	   int c;
337  	   char* pos = strbuf;
338  	
339  	   for( c = 0; c < nelems; ++c )
340  	   {
341  	      pos += sprintf(pos, "%.4f ", elems[c]);
342  	   }
343  	
344  	   return strbuf;
345  	}
346  	#endif
347  	
348  	/** sample from a distribution defined by weights */ /*lint -e715*/
349  	static
350  	int sampleWeighted(
351  	   SCIP*                 scip,               /**< SCIP data structure */
352  	   SCIP_RANDNUMGEN*      rng,                /**< random number generator */
353  	   SCIP_Real*            weights,            /**< weights of a ground set that define the sampling distribution */
354  	   int                   nweights            /**< number of elements in the ground set */
355  	   )
356  	{
357  	   SCIP_Real weightsum;
358  	   SCIP_Real randomnr;
359  	   int w;
360  	#ifdef SCIP_DEBUG
361  	   char strbuf[SCIP_MAXSTRLEN];
362  	   SCIPdebugMsg(scip, "Weights: %s\n", printRealArray(strbuf, weights, nweights));
363  	#endif
364  	
365  	   weightsum = 0.0;
366  	   /* collect sum of weights */
367  	   for( w = 0; w < nweights; ++w )
368  	   {
369  	      weightsum += weights[w];
370  	   }
371  	   assert(weightsum > 0);
372  	
373  	   randomnr = SCIPrandomGetReal(rng, 0.0, weightsum);
374  	
375  	   weightsum = 0.0;
376  	   /* choose first element i such that the weight sum exceeds the random number */
377  	   for( w = 0; w < nweights - 1; ++w )
378  	   {
379  	      weightsum += weights[w];
380  	
381  	      if( weightsum >= randomnr )
382  	         break;
383  	   }
384  	   assert(w < nweights);
385  	   assert(weights[w] > 0.0);
386  	
387  	   return w;
388  	}
389  	
390  	/** select the diving method to apply */
391  	static
392  	SCIP_RETCODE selectDiving(
393  	   SCIP*                 scip,               /**< SCIP data structure */
394  	   SCIP_HEUR*            heur,               /**< the heuristic */
395  	   SCIP_HEURDATA*        heurdata,           /**< heuristic data */
396  	   int*                  selection           /**< selection made */
397  	   )
398  	{
399  	   SCIP_Bool* methodunavailable;
400  	   SCIP_DIVESET** divesets;
401  	   int ndivesets;
402  	   int d;
403  	   SCIP_RANDNUMGEN* rng;
404  	   SCIP_DIVECONTEXT divecontext;
405  	   SCIP_Real* weights;
406  	   SCIP_Real epsilon_t;
407  	
408  	   divesets = heurdata->divesets;
409  	   ndivesets = heurdata->ndivesets;
410  	   assert(ndivesets > 0);
411  	   assert(divesets != NULL);
412  	
413  	   SCIP_CALL( SCIPallocClearBufferArray(scip, &methodunavailable, ndivesets) );
414  	
415  	   divecontext = heurdata->useadaptivecontext ? SCIP_DIVECONTEXT_ADAPTIVE : SCIP_DIVECONTEXT_TOTAL;
416  	
417  	   /* check availability of divesets */
418  	   for( d = 0; d < heurdata->ndivesets; ++d )
419  	   {
420  	      SCIP_Bool available;
421  	      SCIP_CALL( SCIPisDivesetAvailable(scip, heurdata->divesets[d], &available) );
422  	      methodunavailable[d] = ! available;
423  	   }
424  	
425  	   *selection = -1;
426  	
427  	   rng = heurdata->randnumgen;
428  	   assert(rng != NULL);
429  	
430  	   switch (heurdata->seltype) {
431  	   case 'e':
432  	      epsilon_t = heurdata->epsilon * sqrt(ndivesets / (SCIPheurGetNCalls(heur) + 1.0));
433  	      epsilon_t = MAX(epsilon_t, 0.05);
434  	
435  	      /* select one of the available methods at random */
436  	      if( epsilon_t >= 1.0 || SCIPrandomGetReal(rng, 0.0, 1.0) < epsilon_t )
437  	      {
438  	         do
439  	         {
440  	            *selection = SCIPrandomGetInt(rng, 0, ndivesets - 1);
441  	         }
442  	         while( methodunavailable[*selection] );
443  	      }
444  	      else
445  	      {
446  	         SCIP_Real bestscore = SCIP_REAL_MAX;
447  	         for( d = 0; d < heurdata->ndivesets; ++d )
448  	         {
449  	            SCIP_Real score;
450  	
451  	            if( methodunavailable[d] )
452  	               continue;
453  	
454  	            SCIP_CALL( divesetGetSelectionScore(divesets[d], heurdata, divecontext, &score) );
455  	
456  	            if( score < bestscore )
457  	            {
458  	               bestscore = score;
459  	               *selection = d;
460  	            }
461  	         }
462  	      }
463  	      break;
464  	   case 'w':
465  	      SCIP_CALL( SCIPallocBufferArray(scip, &weights, ndivesets) );
466  	
467  	      /* initialize weights as inverse of the score + a small positive epsilon */
468  	      for( d = 0; d < ndivesets; ++d )
469  	      {
470  	         SCIP_Real score;
471  	
472  	         SCIP_CALL( divesetGetSelectionScore(divesets[d], heurdata, divecontext, &score) );
473  	
474  	         weights[d] = methodunavailable[d] ? 0.0 : 1 / (score + 1e-4);
475  	      }
476  	
477  	      *selection = sampleWeighted(scip, rng, weights, ndivesets);
478  	
479  	      SCIPfreeBufferArray(scip, &weights);
480  	      break;
481  	   case 'n':
482  	         /* continue from last selection and stop at the next available method */
483  	         *selection = heurdata->lastselection;
484  	
485  	         do
486  	         {
487  	            *selection = (*selection + 1) % ndivesets;
488  	         }
489  	         while( methodunavailable[*selection] );
490  	         heurdata->lastselection = *selection;
491  	      break;
492  	   default:
493  	      SCIPerrorMessage("Error: Unknown selection method %c\n", heurdata->seltype);
494  	
495  	      return SCIP_INVALIDDATA;
496  	   }
497  	
498  	   assert(*selection >= 0 && *selection < ndivesets);
499  	   SCIPfreeBufferArray(scip, &methodunavailable);
500  	
501  	   return SCIP_OKAY;
502  	}
503  	
504  	/** execution method of primal heuristic */
505  	static
506  	SCIP_DECL_HEUREXEC(heurExecAdaptivediving) /*lint --e{715}*/
507  	{  /*lint --e{715}*/
508  	   SCIP_HEURDATA* heurdata;
509  	   SCIP_DIVESET* diveset;
510  	   SCIP_DIVESET** divesets;
511  	   SCIP_Longint lpiterlimit;
512  	   int selection;
513  	
514  	
515  	   assert(heur != NULL);
516  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
517  	   assert(scip != NULL);
518  	   assert(result != NULL);
519  	   assert(SCIPhasCurrentNodeLP(scip));
520  	
521  	   heurdata = SCIPheurGetData(heur);
522  	   if( heurdata->divesets == NULL )
523  	   {
524  	      SCIP_CALL( findAndStoreDivesets(scip, heur, heurdata) );
525  	   }
526  	
527  	   divesets = heurdata->divesets;
528  	   assert(divesets != NULL);
529  	   assert(heurdata->ndivesets > 0);
530  	
531  	   SCIPdebugMsg(scip, "heurExecAdaptivediving: depth %d sols %d inf %u node %lld (last dive at %lld)\n",
532  	         SCIPgetDepth(scip),
533  	         SCIPgetNSols(scip),
534  	         nodeinfeasible,
535  	         SCIPgetNNodes(scip),
536  	         SCIPgetLastDivenode(scip)
537  	         );
538  	
539  	   *result = SCIP_DELAYED;
540  	
541  	   /* do not call heuristic in node that was already detected to be infeasible */
542  	   if( nodeinfeasible )
543  	      return SCIP_OKAY;
544  	
545  	   /* only call heuristic, if an optimal LP solution is at hand */
546  	   if( !SCIPhasCurrentNodeLP(scip) || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
547  	      return SCIP_OKAY;
548  	
549  	   /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
550  	   if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) )
551  	      return SCIP_OKAY;
552  	
553  	   /* only call heuristic, if the LP solution is basic (which allows fast resolve in diving) */
554  	   if( !SCIPisLPSolBasic(scip) )
555  	      return SCIP_OKAY;
556  	
557  	   /* don't dive two times at the same node */
558  	   if( SCIPgetLastDivenode(scip) == SCIPgetNNodes(scip) && SCIPgetDepth(scip) > 0 )
559  	   {
560  	      SCIPdebugMsg(scip, "already dived at node here\n");
561  	
562  	      return SCIP_OKAY;
563  	   }
564  	
565  	   *result = SCIP_DIDNOTRUN;
566  	
567  	   lpiterlimit = getLPIterlimit(scip, heur, heurdata);
568  	
569  	   if( lpiterlimit <= 0 )
570  	      return SCIP_OKAY;
571  	
572  	   /* select the next diving strategy based on previous success */
573  	   SCIP_CALL( selectDiving(scip, heur, heurdata, &selection) );
574  	   assert(selection >= 0 && selection < heurdata->ndivesets);
575  	
576  	   diveset = divesets[selection];
577  	   assert(diveset != NULL);
578  	
579  	   SCIPdebugMsg(scip, "Selected diveset %s\n", SCIPdivesetGetName(diveset));
580  	
581  	   SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible,
582  	         lpiterlimit, -1, -1.0, SCIP_DIVECONTEXT_ADAPTIVE) );
583  	
584  	   if( *result == SCIP_FOUNDSOL )
585  	   {
586  	      SCIPdebugMsg(scip, "Solution found by diveset %s\n", SCIPdivesetGetName(diveset));
587  	   }
588  	
589  	   return SCIP_OKAY;
590  	}
591  	
592  	/** creates the adaptivediving heuristic and includes it in SCIP */
593  	SCIP_RETCODE SCIPincludeHeurAdaptivediving(
594  	   SCIP*                 scip                /**< SCIP data structure */
595  	   )
596  	{
597  	   SCIP_RETCODE retcode;
598  	   SCIP_HEURDATA* heurdata;
599  	   SCIP_HEUR* heur;
600  	
601  	   /* create adaptivediving data */
602  	   heurdata = NULL;
603  	   SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
604  	
605  	   heurdata->divesets = NULL;
606  	   heurdata->ndivesets = 0;
607  	   heurdata->divesetssize = -1;
608  	
609  	   SCIP_CALL_TERMINATE( retcode, SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_INITIALSEED, TRUE), TERMINATE );
610  	
611  	   /* include adaptive diving primal heuristic */
612  	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
613  	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
614  	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecAdaptivediving, heurdata) );
615  	
616  	   assert(heur != NULL);
617  	
618  	   /* set non-NULL pointers to callback methods */
619  	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyAdaptivediving) );
620  	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeAdaptivediving) );
621  	   SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitAdaptivediving) );
622  	   SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitAdaptivediving) );
623  	
624  	   /* add parameters */
625  	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/epsilon",
626  	         "parameter that increases probability of exploration among divesets (only active if seltype is 'e')",
627  	         &heurdata->epsilon, FALSE, DEFAULT_EPSILON, 0.0, SCIP_REAL_MAX, NULL, NULL) );
628  	
629  	   SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/scoretype",
630  	         "score parameter for selection: minimize either average 'n'odes, LP 'i'terations,"
631  	         "backtrack/'c'onflict ratio, 'd'epth, 1 / 's'olutions, or 1 / solutions'u'ccess",
632  	         &heurdata->scoretype, FALSE, DEFAULT_SCORETYPE, "cdinsu", NULL, NULL) );
633  	
634  	   SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/seltype",
635  	         "selection strategy: (e)psilon-greedy, (w)eighted distribution, (n)ext diving",
636  	         &heurdata->seltype, FALSE, DEFAULT_SELTYPE, "enw", NULL, NULL) );
637  	
638  	   SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useadaptivecontext",
639  	         "should the heuristic use its own statistics, or shared statistics?", &heurdata->useadaptivecontext, TRUE,
640  	         DEFAULT_USEADAPTIVECONTEXT, NULL, NULL) );
641  	
642  	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/selconfidencecoeff",
643  	         "coefficient c to decrease initial confidence (calls + 1.0) / (calls + c) in scores",
644  	         &heurdata->selconfidencecoeff, FALSE, DEFAULT_SELCONFIDENCECOEFF, 1.0, (SCIP_Real)INT_MAX, NULL, NULL) );
645  	
646  	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxlpiterquot",
647  	         "maximal fraction of diving LP iterations compared to node LP iterations",
648  	         &heurdata->maxlpiterquot, FALSE, DEFAULT_MAXLPITERQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
649  	
650  	   SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxlpiterofs",
651  	         "additional number of allowed LP iterations",
652  	         &heurdata->maxlpiterofs, FALSE, DEFAULT_MAXLPITEROFS, 0L, (SCIP_Longint)INT_MAX, NULL, NULL) );
653  	
654  	   SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/bestsolweight",
655  	         "weight of incumbent solutions compared to other solutions in computation of LP iteration limit",
656  	         &heurdata->bestsolweight, FALSE, DEFAULT_BESTSOLWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
657  	
658  	/* cppcheck-suppress unusedLabel */
659  	TERMINATE:
660  	   if( retcode != SCIP_OKAY )
661  	   {
662  	      SCIPfreeMemory(scip, &heurdata);
663  	      return retcode;
664  	   }
665  	
666  	   return SCIP_OKAY;
667  	}
668