SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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-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
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 */
68struct 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 */
96static
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) */
110 (SCIPdivesetGetNCalls(diveset, divecontext) + heurdata->selconfidencecoeff);
111
112 switch (heurdata->scoretype) {
113 case 'n': /* min average nodes */
115 break;
116 case 'i': /* min avg LP iterations */
118 break;
119 case 'c': /* min backtrack / conflict ratio (the current default) */
121 break;
122 case 'd': /* minimum average depth */
124 break;
125 case 's': /* maximum number of solutions */
127 break;
128 case 'u': /* maximum solution success (which weighs best solutions higher) */
130 break;
131 default:
132 SCIPerrorMessage("Unsupported scoring parameter '%c'\n", heurdata->scoretype);
133 SCIPABORT();
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) */
146static
148{ /*lint --e{715}*/
149 assert(scip != NULL);
150 assert(heur != NULL);
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) */
160static
162{ /*lint --e{715}*/
164
165 assert(heur != NULL);
168
169 /* free heuristic data */
172
173 if( heurdata->divesets != NULL )
174 {
175 SCIPfreeBlockMemoryArray(scip, &heurdata->divesets, heurdata->divesetssize);
176 }
177
179
182
183 return SCIP_OKAY;
184}
185
186/** find publicly available divesets and store them */
187static
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 {
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) */
239static
241{ /*lint --e{715}*/
243
244 assert(heur != NULL);
246
247 /* get and reset heuristic data */
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 */
262
263 /* initialize random seed; use problem dimensions to vary initial order between different instances */
266
267 return SCIP_OKAY;
268}
269
270
271/** deinitialization method of primal heuristic (called before transformed problem is freed) */
272static
274{ /*lint --e{715}*/
276
277 assert(heur != NULL);
279
280 /* get heuristic data */
282 assert(heurdata != NULL);
283
284 /* free working solution */
286
287 return SCIP_OKAY;
288}
289
290/*
291 * heuristic specific interface methods
292 */
293
294/** get LP iteration limit for diving */
295static
296SCIP_Longint getLPIterlimit(
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);
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 {
318 }
319
320 /* compute the iteration limit */
321 lpiterlimit = (SCIP_Longint)(heurdata->maxlpiterquot * (nsolsfound+1.0)/(ncalls+1.0) * nlpiterations);
322 lpiterlimit += heurdata->maxlpiterofs;
324
325 return lpiterlimit;
326}
327
328#ifdef SCIP_DEBUG
329/** print array for debug purpose */
330static
331char* 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*/
350static
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 */
392static
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;
402 int ndivesets;
403 int d;
404 SCIP_RANDNUMGEN* rng;
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
415
417
418 /* check availability of divesets */
419 for( d = 0; d < heurdata->ndivesets; ++d )
420 {
421 SCIP_Bool 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
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
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);
501
502 return SCIP_OKAY;
503}
504
505/** execution method of primal heuristic */
506static
508{ /*lint --e{715}*/
512 SCIP_Longint lpiterlimit;
514
515 assert(heur != NULL);
517 assert(scip != NULL);
520
522 if( heurdata->divesets == NULL )
523 {
525 }
526
527 divesets = heurdata->divesets;
529 assert(heurdata->ndivesets > 0);
530
531 SCIPdebugMsg(scip, "heurExecAdaptivediving: depth %d sols %d inf %u node %lld (last dive at %lld)\n",
537 );
538
540
541 /* do not call heuristic in node that was already detected to be infeasible */
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
566
568
569 if( lpiterlimit <= 0 )
570 return SCIP_OKAY;
571
572 /* select the next diving strategy based on previous success */
575
578
579 SCIPdebugMsg(scip, "Selected diveset %s\n", SCIPdivesetGetName(diveset));
580
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;
599 SCIP_HEUR* heur;
600
601 /* create adaptivediving data */
602 heurdata = NULL;
604
605 heurdata->divesets = NULL;
606 heurdata->ndivesets = 0;
607 heurdata->divesetssize = -1;
608
610
611 /* include adaptive diving primal heuristic */
615
616 assert(heur != NULL);
617
618 /* set non-NULL pointers to callback methods */
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 */
660 if( retcode != SCIP_OKAY )
661 {
663 return retcode;
664 }
665
666 return SCIP_OKAY;
667}
SCIP_VAR * h
SCIP_VAR * w
#define SCIP_MAXSTRLEN
Definition def.h:302
#define SCIP_Longint
Definition def.h:171
#define SCIP_REAL_MAX
Definition def.h:187
#define SCIP_INVALID
Definition def.h:206
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define SCIP_CALL_TERMINATE(retcode, x, TERM)
Definition def.h:409
#define SCIPABORT()
Definition def.h:360
#define SCIP_CALL(x)
Definition def.h:388
int SCIPgetNOrigConss(SCIP *scip)
Definition scip_prob.c:3134
int SCIPgetNOrigVars(SCIP *scip)
Definition scip_prob.c:2432
#define SCIPdebugMsg
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
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
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_Bool SCIPdivesetIsPublic(SCIP_DIVESET *diveset)
Definition heur.c:762
SCIP_Longint SCIPdivesetGetNBacktracks(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition heur.c:613
SCIP_Longint SCIPdivesetGetNSols(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition heur.c:639
SCIP_Longint SCIPdivesetGetNConflicts(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition heur.c:626
SCIP_Real SCIPdivesetGetAvgDepth(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition heur.c:535
SCIP_Longint SCIPdivesetGetNLPIterations(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition heur.c:587
SCIP_Longint SCIPdivesetGetSolSuccess(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition heur.c:469
const char * SCIPdivesetGetName(SCIP_DIVESET *diveset)
Definition heur.c:443
SCIP_RETCODE SCIPisDivesetAvailable(SCIP *scip, SCIP_DIVESET *diveset, SCIP_Bool *available)
Definition scip_heur.c:363
int SCIPdivesetGetNCalls(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition heur.c:483
SCIP_Longint SCIPdivesetGetNProbingNodes(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition heur.c:600
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:178
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition heur.c:1361
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
SCIP_HEUR ** SCIPgetHeurs(SCIP *scip)
Definition scip_heur.c:271
SCIP_Longint SCIPheurGetNSolsFound(SCIP_HEUR *heur)
Definition heur.c:1586
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition heur.c:1596
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:162
int SCIPgetNHeurs(SCIP *scip)
Definition scip_heur.c:282
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition heur.c:1576
int SCIPheurGetNDivesets(SCIP_HEUR *heur)
Definition heur.c:1658
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:210
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:194
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition heur.c:1450
SCIP_DIVESET ** SCIPheurGetDivesets(SCIP_HEUR *heur)
Definition heur.c:1648
SCIP_Longint SCIPgetLastDivenode(SCIP *scip)
Definition scip_lp.c:2745
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition scip_lp.c:83
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition scip_lp.c:168
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition scip_lp.c:247
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition scip_lp.c:667
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:110
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition scip_mem.h:126
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPallocMemory(scip, ptr)
Definition scip_mem.h:60
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
#define SCIPfreeMemory(scip, ptr)
Definition scip_mem.h:78
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:93
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition scip_mem.h:99
int SCIPgetNSols(SCIP *scip)
Definition scip_sol.c:2214
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Longint SCIPgetNNodeLPIterations(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetDepth(SCIP *scip)
Definition scip_tree.c:670
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition misc.c:10041
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition misc.c:10019
static SCIP_Longint getLPIterlimit(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
static SCIP_RETCODE divesetGetSelectionScore(SCIP_DIVESET *diveset, SCIP_HEURDATA *heurdata, SCIP_DIVECONTEXT divecontext, SCIP_Real *scoreptr)
heurdata lastselection
#define DEFAULT_INITIALSEED
SCIPheurSetData(heur, NULL)
#define HEUR_TIMING
static int sampleWeighted(SCIP *scip, SCIP_RANDNUMGEN *rng, SCIP_Real *weights, int nweights)
return SCIP_OKAY
static SCIP_RETCODE findAndStoreDivesets(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
#define DEFAULT_MAXLPITERQUOT
#define HEUR_FREQOFS
#define HEUR_DESC
#define DEFAULT_USEADAPTIVECONTEXT
SCIP_RETCODE SCIPincludeHeurAdaptivediving(SCIP *scip)
#define DEFAULT_SCORETYPE
#define DEFAULT_SELCONFIDENCECOEFF
#define DIVESETS_INITIALSIZE
#define HEUR_DISPCHAR
#define DEFAULT_EPSILON
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, lpiterlimit, SCIP_DIVECONTEXT_ADAPTIVE))
SCIP_DIVESET ** divesets
#define DEFAULT_MAXLPITEROFS
SCIPfreeSol(scip, &heurdata->sol))
#define DEFAULT_SELTYPE
SCIP_Longint lpiterlimit
#define HEUR_NAME
SCIPfreeRandom(scip, &heurdata->randnumgen)
#define HEUR_FREQ
int selection
#define HEUR_USESSUBSCIP
static SCIP_RETCODE selectDiving(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, int *selection)
SCIPsetRandomSeed(scip, heurdata->randnumgen,(unsigned int)(DEFAULT_INITIALSEED+SCIPgetNOrigVars(scip)+SCIPgetNOrigConss(scip)))
#define DEFAULT_BESTSOLWEIGHT
static SCIP_DIVESET * diveset
SCIPcreateSol(scip, &heurdata->sol, heur))
diving heuristic that selects adaptively between the existing, public dive sets
SCIP_Longint nsolsfound
SCIP_Longint ncalls
int c
heurdata nlpiterations
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
static SCIP_SOL * sol
assert(minobj< SCIPgetCutoffbound(scip))
methods commonly used by primal heuristics
#define NULL
Definition lpi_spx1.cpp:161
#define SCIPerrorMessage
Definition pub_message.h:64
default SCIP plugins
SCIP_SOL * sol
Definition struct_heur.h:71
#define MAX(x, y)
Definition tclique_def.h:92
#define SCIP_DECL_HEURCOPY(x)
Definition type_heur.h:96
enum SCIP_DiveContext SCIP_DIVECONTEXT
Definition type_heur.h:72
struct SCIP_HeurData SCIP_HEURDATA
Definition type_heur.h:76
#define SCIP_DECL_HEURINIT(x)
Definition type_heur.h:112
#define SCIP_DECL_HEUREXIT(x)
Definition type_heur.h:120
#define SCIP_DECL_HEURFREE(x)
Definition type_heur.h:104
#define SCIP_DECL_HEUREXEC(x)
Definition type_heur.h:162
@ SCIP_DIVECONTEXT_TOTAL
Definition type_heur.h:68
@ SCIP_DIVECONTEXT_ADAPTIVE
Definition type_heur.h:70
@ SCIP_LPSOLSTAT_OPTIMAL
Definition type_lp.h:43
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_DELAYED
Definition type_result.h:43
@ SCIP_FOUNDSOL
Definition type_result.h:56
@ SCIP_INVALIDDATA
@ SCIP_PARAMETERWRONGVAL
enum SCIP_Retcode SCIP_RETCODE