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 (c) 2002-2024 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 
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 /** 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,
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
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
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  assert(heur != NULL);
515  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
516  assert(scip != NULL);
517  assert(result != NULL);
518  assert(SCIPhasCurrentNodeLP(scip));
519 
520  heurdata = SCIPheurGetData(heur);
521  if( heurdata->divesets == NULL )
522  {
523  SCIP_CALL( findAndStoreDivesets(scip, heur, heurdata) );
524  }
525 
526  divesets = heurdata->divesets;
527  assert(divesets != NULL);
528  assert(heurdata->ndivesets > 0);
529 
530  SCIPdebugMsg(scip, "heurExecAdaptivediving: depth %d sols %d inf %u node %lld (last dive at %lld)\n",
533  nodeinfeasible,
536  );
537 
538  *result = SCIP_DELAYED;
539 
540  /* do not call heuristic in node that was already detected to be infeasible */
541  if( nodeinfeasible )
542  return SCIP_OKAY;
543 
544  /* only call heuristic, if an optimal LP solution is at hand */
546  return SCIP_OKAY;
547 
548  /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
550  return SCIP_OKAY;
551 
552  /* only call heuristic, if the LP solution is basic (which allows fast resolve in diving) */
553  if( !SCIPisLPSolBasic(scip) )
554  return SCIP_OKAY;
555 
556  /* don't dive two times at the same node */
558  {
559  SCIPdebugMsg(scip, "already dived at node here\n");
560 
561  return SCIP_OKAY;
562  }
563 
564  *result = SCIP_DIDNOTRUN;
565 
566  lpiterlimit = getLPIterlimit(scip, heur, heurdata);
567 
568  if( lpiterlimit <= 0 )
569  return SCIP_OKAY;
570 
571  /* select the next diving strategy based on previous success */
572  SCIP_CALL( selectDiving(scip, heur, heurdata, &selection) );
573  assert(selection >= 0 && selection < heurdata->ndivesets);
574 
575  diveset = divesets[selection];
576  assert(diveset != NULL);
577 
578  SCIPdebugMsg(scip, "Selected diveset %s\n", SCIPdivesetGetName(diveset));
579 
580  SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible,
581  lpiterlimit, -1, -1.0, SCIP_DIVECONTEXT_ADAPTIVE) );
582 
583  if( *result == SCIP_FOUNDSOL )
584  {
585  SCIPdebugMsg(scip, "Solution found by diveset %s\n", SCIPdivesetGetName(diveset));
586  }
587 
588  return SCIP_OKAY;
589 }
590 
591 /** creates the adaptivediving heuristic and includes it in SCIP */
593  SCIP* scip /**< SCIP data structure */
594  )
595 {
596  SCIP_RETCODE retcode;
597  SCIP_HEURDATA* heurdata;
598  SCIP_HEUR* heur;
599 
600  /* create adaptivediving data */
601  heurdata = NULL;
602  SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
603 
604  heurdata->divesets = NULL;
605  heurdata->ndivesets = 0;
606  heurdata->divesetssize = -1;
607 
608  SCIP_CALL_TERMINATE( retcode, SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_INITIALSEED, TRUE), TERMINATE );
609 
610  /* include adaptive diving primal heuristic */
613  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecAdaptivediving, heurdata) );
614 
615  assert(heur != NULL);
616 
617  /* set non-NULL pointers to callback methods */
618  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyAdaptivediving) );
619  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeAdaptivediving) );
620  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitAdaptivediving) );
621  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitAdaptivediving) );
622 
623  /* add parameters */
624  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/epsilon",
625  "parameter that increases probability of exploration among divesets (only active if seltype is 'e')",
626  &heurdata->epsilon, FALSE, DEFAULT_EPSILON, 0.0, SCIP_REAL_MAX, NULL, NULL) );
627 
628  SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/scoretype",
629  "score parameter for selection: minimize either average 'n'odes, LP 'i'terations,"
630  "backtrack/'c'onflict ratio, 'd'epth, 1 / 's'olutions, or 1 / solutions'u'ccess",
631  &heurdata->scoretype, FALSE, DEFAULT_SCORETYPE, "cdinsu", NULL, NULL) );
632 
633  SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/seltype",
634  "selection strategy: (e)psilon-greedy, (w)eighted distribution, (n)ext diving",
635  &heurdata->seltype, FALSE, DEFAULT_SELTYPE, "enw", NULL, NULL) );
636 
637  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useadaptivecontext",
638  "should the heuristic use its own statistics, or shared statistics?", &heurdata->useadaptivecontext, TRUE,
640 
641  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/selconfidencecoeff",
642  "coefficient c to decrease initial confidence (calls + 1.0) / (calls + c) in scores",
643  &heurdata->selconfidencecoeff, FALSE, DEFAULT_SELCONFIDENCECOEFF, 1.0, (SCIP_Real)INT_MAX, NULL, NULL) );
644 
645  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxlpiterquot",
646  "maximal fraction of diving LP iterations compared to node LP iterations",
647  &heurdata->maxlpiterquot, FALSE, DEFAULT_MAXLPITERQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
648 
649  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxlpiterofs",
650  "additional number of allowed LP iterations",
651  &heurdata->maxlpiterofs, FALSE, DEFAULT_MAXLPITEROFS, 0L, (SCIP_Longint)INT_MAX, NULL, NULL) );
652 
653  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/bestsolweight",
654  "weight of incumbent solutions compared to other solutions in computation of LP iteration limit",
655  &heurdata->bestsolweight, FALSE, DEFAULT_BESTSOLWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
656 
657 /* cppcheck-suppress unusedLabel */
658 TERMINATE:
659  if( retcode != SCIP_OKAY )
660  {
661  SCIPfreeMemory(scip, &heurdata);
662  return retcode;
663  }
664 
665  return SCIP_OKAY;
666 }
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 NULL
Definition: def.h:267
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
SCIP_Longint SCIPdivesetGetNBacktracks(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:615
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:288
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1599
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:2432
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Longint SCIPdivesetGetNLPIterations(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:589
int SCIPdivesetGetNCalls(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:485
SCIP_DIVESET ** SCIPheurGetDivesets(SCIP_HEUR *heur)
Definition: heur.c:1651
#define FALSE
Definition: def.h:94
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:93
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:77
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:10108
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1374
static SCIP_DECL_HEUREXIT(heurExitAdaptivediving)
SCIP_Longint SCIPdivesetGetNProbingNodes(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:602
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_Longint SCIPdivesetGetSolSuccess(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:471
SCIP_Bool SCIPdivesetIsPublic(SCIP_DIVESET *diveset)
Definition: heur.c:764
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:1453
#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:641
#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)
SCIP_RETCODE SCIPperformGenericDivingAlgorithm(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Bool nodeinfeasible, SCIP_Longint iterlim, int nodelimit, SCIP_Real lpresolvedomchgquot, SCIP_DIVECONTEXT divecontext)
Definition: heuristics.c:220
#define SCIP_CALL(x)
Definition: def.h:380
int SCIPgetNOrigConss(SCIP *scip)
Definition: scip_prob.c:3134
SCIP_VAR * h
Definition: circlepacking.c:68
int SCIPheurGetNDivesets(SCIP_HEUR *heur)
Definition: heur.c:1661
static SCIP_Longint getLPIterlimit(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1579
#define HEUR_MAXDEPTH
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:83
SCIP_Longint SCIPgetLastDivenode(SCIP *scip)
Definition: scip_lp.c:2745
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:91
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
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:841
#define DEFAULT_EPSILON
#define HEUR_NAME
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2070
#define HEUR_DISPCHAR
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10130
#define SCIP_REAL_MAX
Definition: def.h:174
#define DEFAULT_SELCONFIDENCECOEFF
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:78
#define DEFAULT_USEADAPTIVECONTEXT
int SCIPgetNHeurs(SCIP *scip)
Definition: scip_heur.c:282
#define MAX(x, y)
Definition: def.h:239
enum SCIP_DiveContext SCIP_DIVECONTEXT
Definition: type_heur.h:73
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:247
SCIP_Longint SCIPdivesetGetNConflicts(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:628
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:537
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:194
#define SCIP_Real
Definition: def.h:173
#define SCIP_CALL_TERMINATE(retcode, x, TERM)
Definition: def.h:401
#define SCIP_INVALID
Definition: def.h:193
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:158
SCIP_Longint SCIPheurGetNSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1589
#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:1364
#define HEUR_FREQ
SCIP_Longint SCIPgetNNodes(SCIP *scip)
#define SCIPABORT()
Definition: def.h:352
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:184
const char * SCIPdivesetGetName(SCIP_DIVESET *diveset)
Definition: heur.c:445