Scippy

SCIP

Solving Constraint Integer Programs

heur_adaptivediving.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright 2002-2022 Zuse Institute Berlin */
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 
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
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 */
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
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 
238 /** initialization method of primal heuristic (called after problem was transformed) */
239 static
240 SCIP_DECL_HEURINIT(heurInitAdaptivediving) /*lint --e{715}*/
241 { /*lint --e{715}*/
242  SCIP_HEURDATA* heurdata;
243 
244  assert(heur != NULL);
245  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
246 
247  /* get and reset heuristic data */
248  heurdata = SCIPheurGetData(heur);
249  heurdata->lastselection = -1;
250  if( heurdata->divesets != NULL )
251  {
252  /* we clear the list of collected divesets to ensure reproducability and consistent state across multiple runs
253  * within the same SCIP data structure */
254  SCIPfreeBlockMemoryArray(scip, &heurdata->divesets, heurdata->divesetssize);
255  assert(heurdata->divesets == NULL);
256  }
257 
258  assert(heurdata != NULL);
259 
260  /* create working solution */
261  SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
262 
263  /* initialize random seed; use problem dimensions to vary initial order between different instances */
264  SCIPsetRandomSeed(scip, heurdata->randnumgen,
266 
267  return SCIP_OKAY;
268 }
269 
270 
271 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
272 static
273 SCIP_DECL_HEUREXIT(heurExitAdaptivediving) /*lint --e{715}*/
274 { /*lint --e{715}*/
275  SCIP_HEURDATA* heurdata;
276 
277  assert(heur != NULL);
278  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
279 
280  /* get heuristic data */
281  heurdata = SCIPheurGetData(heur);
282  assert(heurdata != NULL);
283 
284  /* free working solution */
285  SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
286 
287  return SCIP_OKAY;
288 }
289 
290 /*
291  * heuristic specific interface methods
292  */
293 
294 /** get LP iteration limit for diving */
295 static
297  SCIP* scip, /**< SCIP data structure */
298  SCIP_HEUR* heur, /**< the heuristic */
299  SCIP_HEURDATA* heurdata /**< heuristic data */
300  )
301 {
302  SCIP_Real nsolsfound = SCIPheurGetNSolsFound(heur) + heurdata->bestsolweight * SCIPheurGetNBestSolsFound(heur);
303  SCIP_Longint nlpiterations = SCIPgetNNodeLPIterations(scip);
304  SCIP_Longint ncalls = SCIPheurGetNCalls(heur);
305 
306  SCIP_Longint nlpiterationsdive = 0;
307  SCIP_Longint lpiterlimit;
308  int i;
309 
310  assert(scip != NULL);
311  assert(heur != NULL);
312  assert(heurdata != NULL);
313 
314  /* loop over the divesets and collect their individual iterations */
315  for( i = 0; i < heurdata->ndivesets; ++i )
316  {
317  nlpiterationsdive += SCIPdivesetGetNLPIterations(heurdata->divesets[i], SCIP_DIVECONTEXT_ADAPTIVE);
318  }
319 
320  /* compute the iteration limit */
321  lpiterlimit = (SCIP_Longint)(heurdata->maxlpiterquot * (nsolsfound+1.0)/(ncalls+1.0) * nlpiterations);
322  lpiterlimit += heurdata->maxlpiterofs;
323  lpiterlimit -= nlpiterationsdive;
324 
325  return lpiterlimit;
326 }
327 
328 #ifdef SCIP_DEBUG
329 /** print array for debug purpose */
330 static
331 char* printRealArray(
332  char* strbuf, /**< string buffer array */
333  SCIP_Real* elems, /**< array elements */
334  int nelems /**< number of elements */
335  )
336 {
337  int c;
338  char* pos = strbuf;
339 
340  for( c = 0; c < nelems; ++c )
341  {
342  pos += sprintf(pos, "%.4f ", elems[c]);
343  }
344 
345  return strbuf;
346 }
347 #endif
348 
349 /** sample from a distribution defined by weights */ /*lint -e715*/
350 static
351 int sampleWeighted(
352  SCIP* scip, /**< SCIP data structure */
353  SCIP_RANDNUMGEN* rng, /**< random number generator */
354  SCIP_Real* weights, /**< weights of a ground set that define the sampling distribution */
355  int nweights /**< number of elements in the ground set */
356  )
357 {
358  SCIP_Real weightsum;
359  SCIP_Real randomnr;
360  int w;
361 #ifdef SCIP_DEBUG
362  char strbuf[SCIP_MAXSTRLEN];
363  SCIPdebugMsg(scip, "Weights: %s\n", printRealArray(strbuf, weights, nweights));
364 #endif
365 
366  weightsum = 0.0;
367  /* collect sum of weights */
368  for( w = 0; w < nweights; ++w )
369  {
370  weightsum += weights[w];
371  }
372  assert(weightsum > 0);
373 
374  randomnr = SCIPrandomGetReal(rng, 0.0, weightsum);
375 
376  weightsum = 0.0;
377  /* choose first element i such that the weight sum exceeds the random number */
378  for( w = 0; w < nweights - 1; ++w )
379  {
380  weightsum += weights[w];
381 
382  if( weightsum >= randomnr )
383  break;
384  }
385  assert(w < nweights);
386  assert(weights[w] > 0.0);
387 
388  return w;
389 }
390 
391 /** select the diving method to apply */
392 static
394  SCIP* scip, /**< SCIP data structure */
395  SCIP_HEUR* heur, /**< the heuristic */
396  SCIP_HEURDATA* heurdata, /**< heuristic data */
397  int* selection /**< selection made */
398  )
399 {
400  SCIP_Bool* methodunavailable;
401  SCIP_DIVESET** divesets;
402  int ndivesets;
403  int d;
404  SCIP_RANDNUMGEN* rng;
405  SCIP_DIVECONTEXT divecontext;
406  SCIP_Real* weights;
407  SCIP_Real epsilon_t;
408 
409  divesets = heurdata->divesets;
410  ndivesets = heurdata->ndivesets;
411  assert(ndivesets > 0);
412  assert(divesets != NULL);
413 
414  SCIP_CALL( SCIPallocClearBufferArray(scip, &methodunavailable, ndivesets) );
415 
416  divecontext = heurdata->useadaptivecontext ? SCIP_DIVECONTEXT_ADAPTIVE : SCIP_DIVECONTEXT_TOTAL;
417 
418  /* check availability of divesets */
419  for( d = 0; d < heurdata->ndivesets; ++d )
420  {
421  SCIP_Bool available;
422  SCIP_CALL( SCIPisDivesetAvailable(scip, heurdata->divesets[d], &available) );
423  methodunavailable[d] = ! available;
424  }
425 
426  *selection = -1;
427 
428  rng = heurdata->randnumgen;
429  assert(rng != NULL);
430 
431  switch (heurdata->seltype) {
432  case 'e':
433  epsilon_t = heurdata->epsilon * sqrt(ndivesets / (SCIPheurGetNCalls(heur) + 1.0));
434  epsilon_t = MAX(epsilon_t, 0.05);
435 
436  /* select one of the available methods at random */
437  if( epsilon_t >= 1.0 || SCIPrandomGetReal(rng, 0.0, 1.0) < epsilon_t )
438  {
439  do
440  {
441  *selection = SCIPrandomGetInt(rng, 0, ndivesets - 1);
442  }
443  while( methodunavailable[*selection] );
444  }
445  else
446  {
447  SCIP_Real bestscore = SCIP_REAL_MAX;
448  for( d = 0; d < heurdata->ndivesets; ++d )
449  {
450  SCIP_Real score;
451 
452  if( methodunavailable[d] )
453  continue;
454 
455  SCIP_CALL( divesetGetSelectionScore(divesets[d], heurdata, divecontext, &score) );
456 
457  if( score < bestscore )
458  {
459  bestscore = score;
460  *selection = d;
461  }
462  }
463  }
464  break;
465  case 'w':
466  SCIP_CALL( SCIPallocBufferArray(scip, &weights, ndivesets) );
467 
468  /* initialize weights as inverse of the score + a small positive epsilon */
469  for( d = 0; d < ndivesets; ++d )
470  {
471  SCIP_Real score;
472 
473  SCIP_CALL( divesetGetSelectionScore(divesets[d], heurdata, divecontext, &score) );
474 
475  weights[d] = methodunavailable[d] ? 0.0 : 1 / (score + 1e-4);
476  }
477 
478  *selection = sampleWeighted(scip, rng, weights, ndivesets);
479 
480  SCIPfreeBufferArray(scip, &weights);
481  break;
482  case 'n':
483  /* continue from last selection and stop at the next available method */
484  *selection = heurdata->lastselection;
485 
486  do
487  {
488  *selection = (*selection + 1) % ndivesets;
489  }
490  while( methodunavailable[*selection] );
491  heurdata->lastselection = *selection;
492  break;
493  default:
494  SCIPerrorMessage("Error: Unknown selection method %c\n", heurdata->seltype);
495 
496  return SCIP_INVALIDDATA;
497  }
498 
499  assert(*selection >= 0 && *selection < ndivesets);
500  SCIPfreeBufferArray(scip, &methodunavailable);
501 
502  return SCIP_OKAY;
503 }
504 
505 /** execution method of primal heuristic */
506 static
507 SCIP_DECL_HEUREXEC(heurExecAdaptivediving) /*lint --e{715}*/
508 { /*lint --e{715}*/
509  SCIP_HEURDATA* heurdata;
510  SCIP_DIVESET* diveset;
511  SCIP_DIVESET** divesets;
512  SCIP_Longint lpiterlimit;
513  int selection;
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",
534  nodeinfeasible,
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 */
547  return SCIP_OKAY;
548 
549  /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
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 */
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, 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 */
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 */
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,
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 }
static SCIP_RETCODE selectDiving(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, int *selection)
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
SCIP_Longint SCIPdivesetGetNBacktracks(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:613
static SCIP_DECL_HEUREXEC(heurExecAdaptivediving)
static SCIP_DECL_HEURFREE(heurFreeAdaptivediving)
#define DEFAULT_BESTSOLWEIGHT
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:126
#define SCIP_MAXSTRLEN
Definition: def.h:302
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1596
void SCIPsetRandomSeed(SCIP *scip, SCIP_RANDNUMGEN *randnumgen, unsigned int seed)
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:210
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip_prob.c:2440
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Longint SCIPdivesetGetNLPIterations(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:587
int SCIPdivesetGetNCalls(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:483
SCIP_DIVESET ** SCIPheurGetDivesets(SCIP_HEUR *heur)
Definition: heur.c:1648
#define FALSE
Definition: def.h:96
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:111
#define TRUE
Definition: def.h:95
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
methods commonly used by primal heuristics
SCIP_HEUR ** SCIPgetHeurs(SCIP *scip)
Definition: scip_heur.c:271
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:76
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:117
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:10012
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1371
static SCIP_DECL_HEUREXIT(heurExitAdaptivediving)
SCIP_Longint SCIPdivesetGetNProbingNodes(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:600
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_Longint SCIPdivesetGetSolSuccess(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:469
SCIP_RETCODE SCIPperformGenericDivingAlgorithm(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Bool nodeinfeasible, SCIP_Longint iterlim, SCIP_DIVECONTEXT divecontext)
Definition: heuristics.c:218
SCIP_Bool SCIPdivesetIsPublic(SCIP_DIVESET *diveset)
Definition: heur.c:762
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip_lp.c:667
SCIP_VAR * w
Definition: circlepacking.c:67
#define HEUR_PRIORITY
#define DEFAULT_SCORETYPE
#define HEUR_DESC
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1450
#define DEFAULT_INITIALSEED
#define SCIPerrorMessage
Definition: pub_message.h:64
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
SCIP_Longint SCIPdivesetGetNSols(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:639
#define HEUR_TIMING
static SCIP_DECL_HEURCOPY(heurCopyAdaptivediving)
SCIP_RETCODE SCIPincludeHeurAdaptivediving(SCIP *scip)
SCIP_SOL * sol
Definition: struct_heur.h:71
static SCIP_DECL_HEURINIT(heurInitAdaptivediving)
#define NULL
Definition: lpi_spx1.cpp:164
#define SCIP_CALL(x)
Definition: def.h:393
int SCIPgetNOrigConss(SCIP *scip)
Definition: scip_prob.c:3142
SCIP_VAR * h
Definition: circlepacking.c:68
int SCIPheurGetNDivesets(SCIP_HEUR *heur)
Definition: heur.c:1658
static SCIP_Longint getLPIterlimit(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1576
#define HEUR_MAXDEPTH
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:83
SCIP_Longint SCIPgetLastDivenode(SCIP *scip)
Definition: scip_lp.c:2739
SCIP_Longint SCIPgetNNodeLPIterations(SCIP *scip)
#define HEUR_FREQOFS
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define HEUR_USESSUBSCIP
#define SCIP_Bool
Definition: def.h:93
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
#define DIVESETS_INITIALSIZE
static SCIP_RETCODE findAndStoreDivesets(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
#define MAX(x, y)
Definition: tclique_def.h:92
SCIP_RETCODE SCIPisDivesetAvailable(SCIP *scip, SCIP_DIVESET *diveset, SCIP_Bool *available)
Definition: scip_heur.c:363
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:985
#define DEFAULT_EPSILON
#define HEUR_NAME
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2214
#define HEUR_DISPCHAR
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10034
#define SCIP_REAL_MAX
Definition: def.h:187
#define DEFAULT_SELCONFIDENCECOEFF
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:78
#define DEFAULT_USEADAPTIVECONTEXT
int SCIPgetNHeurs(SCIP *scip)
Definition: scip_heur.c:282
enum SCIP_DiveContext SCIP_DIVECONTEXT
Definition: type_heur.h:72
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:247
SCIP_Longint SCIPdivesetGetNConflicts(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:626
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:167
static int sampleWeighted(SCIP *scip, SCIP_RANDNUMGEN *rng, SCIP_Real *weights, int nweights)
#define DEFAULT_SELTYPE
SCIP_Real SCIPdivesetGetAvgDepth(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:535
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:194
#define SCIP_Real
Definition: def.h:186
#define SCIP_CALL_TERMINATE(retcode, x, TERM)
Definition: def.h:414
#define SCIP_INVALID
Definition: def.h:206
static SCIP_RETCODE divesetGetSelectionScore(SCIP_DIVESET *diveset, SCIP_HEURDATA *heurdata, SCIP_DIVECONTEXT divecontext, SCIP_Real *scoreptr)
#define DEFAULT_MAXLPITERQUOT
#define SCIP_Longint
Definition: def.h:171
SCIP_Longint SCIPheurGetNSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1586
#define DEFAULT_MAXLPITEROFS
diving heuristic that selects adaptively between the existing, public dive sets
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:60
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1361
#define HEUR_FREQ
SCIP_Longint SCIPgetNNodes(SCIP *scip)
#define SCIPABORT()
Definition: def.h:365
default SCIP plugins
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:328
const char * SCIPdivesetGetName(SCIP_DIVESET *diveset)
Definition: heur.c:443