SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
heur_scheduler.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_scheduler.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief Adaptive heuristic to schedule LNS and diving heuristics
28 * @author Gregor Hendel
29 * @author Antonia Chmiela
30 */
31
32/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33
35#include "scip/cons_linear.h"
36#include "scip/heur_scheduler.h"
37#include "scip/heuristics.h"
41#include "scip/pub_bandit.h"
42#include "scip/pub_bandit_ucb.h"
43#include "scip/pub_cons.h"
44#include "scip/pub_event.h"
45#include "scip/pub_heur.h"
46#include "scip/pub_message.h"
47#include "scip/pub_misc.h"
49#include "scip/pub_sol.h"
50#include "scip/pub_var.h"
51#include "scip/scip_bandit.h"
52#include "scip/scip_branch.h"
53#include "scip/scip_cons.h"
54#include "scip/scip_copy.h"
55#include "scip/scip_event.h"
56#include "scip/scip_general.h"
57#include "scip/scip_heur.h"
58#include "scip/scip_lp.h"
59#include "scip/scip_mem.h"
60#include "scip/scip_message.h"
61#include "scip/scip_nodesel.h"
62#include "scip/scip_numerics.h"
63#include "scip/scip_param.h"
64#include "scip/scip_prob.h"
66#include "scip/scip_sol.h"
67#include "scip/scip_solve.h"
69#include "scip/scip_table.h"
70#include "scip/scip_timing.h"
71#include "scip/scip_tree.h"
72#include "scip/scip_var.h"
73#include <string.h>
74
75#if !defined(_WIN32) && !defined(_WIN64)
76#include <strings.h> /*lint --e{766}*/ /* needed for strncasecmp() */
77#endif
78
79#define HEUR_NAME "scheduler"
80#define HEUR_DESC "Adaptive heuristic to schedule LNS and diving heuristics"
81#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
82#define HEUR_PRIORITY -30000
83#define HEUR_FREQ -1
84#define HEUR_FREQOFS 0
85#define HEUR_MAXDEPTH -1
86#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
87#define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
88
89#define NNEIGHBORHOODS 9
90#define DIVINGHEURS_INITIALSIZE 10
91
92/*
93 * limit parameters for sub-SCIPs
94 */
95#define DEFAULT_NODESQUOT 0.1
96#define DEFAULT_NODESQUOTMIN 0.0
97#define DEFAULT_NODESOFFSET 500LL
98#define DEFAULT_NSOLSLIM 3
99#define DEFAULT_MINNODES 50LL
100#define DEFAULT_MAXNODES 500LL
101#define DEFAULT_WAITINGNODES 0LL /**< number of nodes since last incumbent solution that the heuristic should wait */
102#define DEFAULT_INITLNSNODELIMIT 50
103#define DEFAULT_INITDIVINGNODELIMIT 500LL
104#define DEFAULT_TARGETNODEFACTOR 1.05
105#define LRATEMIN 0.01 /**< lower bound for learning rate for target nodes and minimum improvement */
106#define LPLIMFAC 4.0
107#define DEFAULT_INITDURINGROOT FALSE
108#define DEFAULT_MAXCALLSSAMESOL -1 /**< number of allowed executions of the heuristic on the same incumbent solution */
109#define DEFAULT_HEURTIMELIMIT 60.0 /**< time limit for a single heuristic run */
110
111/*
112 * bandit algorithm parameters
113 */
114#define DEFAULT_BESTSOLWEIGHT 1
115#define DEFAULT_BANDITALGO 'i' /**< the default bandit algorithm: (u)pper confidence bounds, (e)xp.3, epsilon (g)reedy, exp.3-(i)x */
116#define DEFAULT_RESETWEIGHTS FALSE/**< should the bandit algorithms be reset when a new problem is read? */
117#define DEFAULT_SUBSCIPRANDSEEDS FALSE /**< should random seeds of sub-SCIPs be altered to increase diversification? */
118#define DEFAULT_FIXTOL 0.1 /**< tolerance by which the fixing rate may be missed without generic fixing */
119#define DEFAULT_UNFIXTOL 0.1 /**< tolerance by which the fixing rate may be exceeded without generic unfixing */
120#define DEFAULT_BETA 0.0 /**< default reward offset between 0 and 1 at every observation for exp3 */
121#define DEFAULT_NSELECTIONS 5 /**< number of heuristics picked by the scheduler in one call (-1: number of controlled heuristics, 0: until new incumbent is found) */
122
123/*
124 * parameters to control variable fixing
125 */
126#define DEFAULT_USEREDCOST TRUE /**< should reduced cost scores be used for variable priorization? */
127#define DEFAULT_USEPSCOST TRUE /**< should pseudo cost scores be used for variable priorization? */
128#define DEFAULT_USEDISTANCES TRUE /**< should distances from fixed variables be used for variable priorization */
129#define DEFAULT_USELOCALREDCOST FALSE /**< should local reduced costs be used for generic (un)fixing? */
130
131/*
132 * parameters for reward computation
133 */
134#define DEFAULT_EFFORTREWARDWEIGHT 0.2
135#define DEFAULT_SOLREWARDWEIGHT 0.3
136#define DEFAULT_QUALREWARDWEIGHT 0.3
137#define DEFAULT_CONFLICTREWARDWEIGHT 0.2
138
139/*
140 * the following 3 parameters have been tuned by a simulation experiment
141 * as described in the paper.
142 */
143#define DEFAULT_EPS 0.4685844 /**< increase exploration in epsilon-greedy bandit algorithm */
144#define DEFAULT_ALPHA 0.0016 /**< parameter to increase the confidence width in UCB */
145#define DEFAULT_GAMMA 0.07041455 /**< default weight between uniform (gamma ~ 1) and weight driven (gamma ~ 0) probability distribution for exp3 */
146
147/*
148 * parameters to control solve frequency for diving heuristics
149 */
150#define SOLVEFREQ_DECAY 0.75 /**< geometric decay for solving freq adjustments */
151#define SOLVEFREQ_STARTINC 0.2 /**< initial increment value for solving frequency */
152#define MAXSOLVEFREQ 0.3 /**< maximal solving frequency */
153#define MINSOLVEFREQ 0.05 /**< minimal solving frequency */
154
155/*
156 * parameters to control variable fixing
157 */
158#define FIXINGRATE_DECAY 0.75 /**< geometric decay for fixing rate adjustments */
159#define FIXINGRATE_STARTINC 0.2 /**< initial increment value for fixing rate */
160#define DEFAULT_USESUBSCIPHEURS FALSE /**< should the heuristic activate other sub-SCIP heuristics during its search? */
161#define DEFAULT_COPYCUTS FALSE /**< should cutting planes be copied to the sub-SCIP? */
162
163/* individual random seeds */
164#define DEFAULT_SEED 113
165#define MUTATIONSEED 121
166#define CROSSOVERSEED 321
167
168/* individual neighborhood parameters */
169#define DEFAULT_MINFIXINGRATE_RENS 0.3
170#define DEFAULT_MAXFIXINGRATE_RENS 0.9
171#define DEFAULT_ACTIVE_RENS TRUE
172//#define DEFAULT_PRIORITY_RENS 1.0
173#define DEFAULT_PRIORITY_RENS -1100000
174
175#define DEFAULT_MINFIXINGRATE_RINS 0.3
176#define DEFAULT_MAXFIXINGRATE_RINS 0.9
177#define DEFAULT_ACTIVE_RINS TRUE
178//#define DEFAULT_PRIORITY_RINS 1.0
179#define DEFAULT_PRIORITY_RINS -1101000
180
181#define DEFAULT_MINFIXINGRATE_MUTATION 0.3
182#define DEFAULT_MAXFIXINGRATE_MUTATION 0.9
183#define DEFAULT_ACTIVE_MUTATION TRUE
184//#define DEFAULT_PRIORITY_MUTATION 1.0
185#define DEFAULT_PRIORITY_MUTATION -1103010
186
187#define DEFAULT_MINFIXINGRATE_LOCALBRANCHING 0.3
188#define DEFAULT_MAXFIXINGRATE_LOCALBRANCHING 0.9
189#define DEFAULT_ACTIVE_LOCALBRANCHING TRUE
190//#define DEFAULT_PRIORITY_LOCALBRANCHING 1.0
191#define DEFAULT_PRIORITY_LOCALBRANCHING -1102000
192
193#define DEFAULT_MINFIXINGRATE_PROXIMITY 0.3
194#define DEFAULT_MAXFIXINGRATE_PROXIMITY 0.9
195#define DEFAULT_ACTIVE_PROXIMITY TRUE
196//#define DEFAULT_PRIORITY_PROXIMITY 1.0
197#define DEFAULT_PRIORITY_PROXIMITY -2000000
198
199#define DEFAULT_MINFIXINGRATE_CROSSOVER 0.3
200#define DEFAULT_MAXFIXINGRATE_CROSSOVER 0.9
201#define DEFAULT_ACTIVE_CROSSOVER TRUE
202//#define DEFAULT_PRIORITY_CROSSOVER 1.0
203#define DEFAULT_PRIORITY_CROSSOVER -1104000
204
205#define DEFAULT_MINFIXINGRATE_ZEROOBJECTIVE 0.3
206#define DEFAULT_MAXFIXINGRATE_ZEROOBJECTIVE 0.9
207#define DEFAULT_ACTIVE_ZEROOBJECTIVE TRUE
208//#define DEFAULT_PRIORITY_ZEROOBJECTIVE 1.0
209#define DEFAULT_PRIORITY_ZEROOBJECTIVE 100
210
211#define DEFAULT_MINFIXINGRATE_DINS 0.3
212#define DEFAULT_MAXFIXINGRATE_DINS 0.9
213#define DEFAULT_ACTIVE_DINS TRUE
214//#define DEFAULT_PRIORITY_DINS 1.0
215#define DEFAULT_PRIORITY_DINS -1105000
216
217#define DEFAULT_MINFIXINGRATE_TRUSTREGION 0.3
218#define DEFAULT_MAXFIXINGRATE_TRUSTREGION 0.9
219#define DEFAULT_ACTIVE_TRUSTREGION FALSE
220//#define DEFAULT_PRIORITY_TRUSTREGION 1.0
221#define DEFAULT_PRIORITY_TRUSTREGION -1102010
222
223
224#define DEFAULT_NSOLS_CROSSOVER 2 /**< parameter for the number of solutions that crossover should combine */
225#define DEFAULT_NPOOLSOLS_DINS 5 /**< number of pool solutions where binary solution values must agree */
226#define DEFAULT_VIOLPENALTY_TRUSTREGION 100.0 /**< the penalty for violating the trust region */
227
228/* event handler properties */
229#define EVENTHDLR_NAME "Scheduler"
230#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic"
231#define SCIP_EVENTTYPE_SCHEDULER (SCIP_EVENTTYPE_LPSOLVED | SCIP_EVENTTYPE_SOLFOUND | SCIP_EVENTTYPE_BESTSOLFOUND)
232
233/* properties of the scheduler neighborhood statistics table */
234#define TABLE_NAME_NEIGHBORHOOD "scheduler"
235#define TABLE_DESC_NEIGHBORHOOD "scheduler heuristics statistics"
236#define TABLE_POSITION_NEIGHBORHOOD 12500 /**< the position of the statistics table */
237#define TABLE_EARLIEST_STAGE_NEIGHBORHOOD SCIP_STAGE_TRANSFORMED /**< output of the statistics table is only printed from this stage onwards */
238
239/*
240 * additional neighborhood data structures
241 */
242
243
244typedef struct data_crossover DATA_CROSSOVER; /**< crossover neighborhood data structure */
245
246typedef struct data_mutation DATA_MUTATION; /**< mutation neighborhood data structure */
247
248typedef struct data_dins DATA_DINS; /**< dins neighborhood data structure */
249
250typedef struct data_trustregion DATA_TRUSTREGION; /**< trustregion neighborhood data structure */
251
252typedef struct NH_FixingRate NH_FIXINGRATE; /** fixing rate data structure */
253
254typedef struct SolveFreq SOLVEFREQ; /** diving heuristic solving frequency data structure */
255
256typedef struct Heur_Stats HEUR_STATS; /**< heuristic statistics data structure */
257
258typedef struct Nh NH; /**< neighborhood data structure */
259
260typedef struct Diving_Heur DIVING_HEUR; /**< diving heuristic data structure */
261
262/*
263 * variable priorization data structure for sorting
264 */
265typedef struct VarPrio VARPRIO;
266
267/** callback to collect variable fixings of neighborhood */
268 #define DECL_VARFIXINGS(x) SCIP_RETCODE x ( \
269 SCIP* scip, /**< SCIP data structure */ \
270 NH* neighborhood, /**< neighborhood data structure */ \
271 SCIP_VAR** varbuf, /**< buffer array to collect variables to fix */\
272 SCIP_Real* valbuf, /**< buffer array to collect fixing values */ \
273 int* nfixings, /**< pointer to store the number of fixings */ \
274 SCIP_RESULT* result /**< result pointer */ \
275 )
276
277/** callback for subproblem changes other than variable fixings
278 *
279 * this callback can be used to further modify the subproblem by changes other than variable fixings.
280 * Typical modifications include restrictions of variable domains, the formulation of additional constraints,
281 * or changed objective coefficients.
282 *
283 * The callback should set the \p success pointer to indicate whether it was successful with its modifications or not.
284 */
285#define DECL_CHANGESUBSCIP(x) SCIP_RETCODE x ( \
286 SCIP* sourcescip, /**< source SCIP data structure */\
287 SCIP* targetscip, /**< target SCIP data structure */\
288 NH* neighborhood, /**< neighborhood data structure */\
289 SCIP_VAR** subvars, /**< array of targetscip variables in the same order as the source SCIP variables */\
290 int* ndomchgs, /**< pointer to store the number of performed domain changes */\
291 int* nchgobjs, /**< pointer to store the number of changed objective coefficients */ \
292 int* naddedconss, /**< pointer to store the number of additional constraints */\
293 SCIP_Bool* success /**< pointer to store if the sub-MIP was successfully adjusted */\
294 )
295
296/** optional initialization callback for neighborhoods when a new problem is read */
297#define DECL_NHINIT(x) SCIP_RETCODE x ( \
298 SCIP* scip, /**< SCIP data structure */ \
299 NH* neighborhood /**< neighborhood data structure */ \
300 )
301
302/** deinitialization callback for neighborhoods when exiting a problem */
303#define DECL_NHEXIT(x) SCIP_RETCODE x ( \
304 SCIP* scip, /**< SCIP data structure */ \
305 NH* neighborhood /**< neighborhood data structure */ \
306 )
307
308/** deinitialization callback for neighborhoods before SCIP is freed */
309#define DECL_NHFREE(x) SCIP_RETCODE x ( \
310 SCIP* scip, /**< SCIP data structure */ \
311 NH* neighborhood /**< neighborhood data structure */ \
312 )
313
314/** callback function to return a feasible reference solution for further fixings
315 *
316 * The reference solution should be stored in the \p solptr.
317 * The \p result pointer can be used to indicate either
318 *
319 * - SCIP_SUCCESS or
320 * - SCIP_DIDNOTFIND
321 */
322#define DECL_NHREFSOL(x) SCIP_RETCODE x ( \
323 SCIP* scip, /**< SCIP data structure */ \
324 NH* neighborhood, /**< neighborhood data structure */ \
325 SCIP_SOL** solptr, /**< pointer to store the reference solution */ \
326 SCIP_RESULT* result /**< pointer to indicate the callback success whether a reference solution is available */ \
327 )
328
329/** callback function to deactivate neighborhoods on problems where they are irrelevant */
330#define DECL_NHDEACTIVATE(x) SCIP_RETCODE x (\
331 SCIP* scip, /**< SCIP data structure */ \
332 SCIP_Bool* deactivate /**< pointer to store whether the neighborhood should be deactivated (TRUE) for an instance */ \
333 )
334
335/** sub-SCIP status code enumerator */
337{
338 HIDX_OPT = 0, /**< sub-SCIP was solved to optimality */
339 HIDX_USR = 1, /**< sub-SCIP was user interrupted */
340 HIDX_NODELIM = 2, /**< sub-SCIP reached the node limit */
341 HIDX_STALLNODE = 3, /**< sub-SCIP reached the stall node limit */
342 HIDX_INFEAS = 4, /**< sub-SCIP was infeasible */
343 HIDX_SOLLIM = 5, /**< sub-SCIP reached the solution limit */
344 HIDX_OTHER = 6 /**< sub-SCIP reached none of the above codes */
346typedef enum HistIndex HISTINDEX;
347#define NHISTENTRIES 7
348
349
350/** statistics for heuristics */
352{
353 SCIP_Real oldupperbound; /**< upper bound before the heuristic started */
354 SCIP_Real newupperbound; /**< new upper bound for allrewards mode to work correctly */
355 int nruns; /**< number of runs of a heuristic */
356 int nrunsbestsol; /**< number of runs that produced a new incumbent */
357 SCIP_Longint nsolsfound; /**< the total number of solutions found */
358 SCIP_Longint nbestsolsfound; /**< the total number of improving solutions found */
359 SCIP_CLOCK* setupclock; /**< clock for setup time */
360 SCIP_CLOCK* execclock; /**< clock for the heuristic execution */
361 /* for diving */
362 SCIP_Longint nbacktracks; /**< total number of used backtracks */
363 SCIP_Longint nconflicts; /**< total number of conflict constraints generated */
364 SCIP_Longint nprobnodes; /**< total number of probing nodes used */
365 int divingdepth; /**< depth of last dive */
366 /* for LNS */
367 SCIP_Longint usednodes; /**< total number of used nodes */
368 int nfixings; /**< the number of fixings in one run */
369 int statushist[NHISTENTRIES]; /**< array to count sub-SCIP statuses */
370};
371
372
373/** fixing rate data structure to control the amount of target fixings of a neighborhood */
374struct NH_FixingRate
375{
376 SCIP_Real minfixingrate; /**< the minimum fixing rate */
377 SCIP_Real targetfixingrate; /**< the current target fixing rate */
378 SCIP_Real increment; /**< the current increment by which the target fixing rate is in-/decreased */
379 SCIP_Real maxfixingrate; /**< the maximum fixing rate */
380};
381
382/** solve frequency for diving heuristics */
384{
385 SCIP_Real minsolvefreq; /**< the minimum solve frequency */
386 SCIP_Real currentsolvefreq; /**< the current solve frequency */
387 SCIP_Real increment; /**< the current increment by which the solve frequency is in-/decreased */
388 SCIP_Real maxsolvefreq; /**< the maximum solve frequency */
389};
390
391/** neighborhood data structure with callbacks, statistics, fixing rate */
392struct Nh
393{
394 char* name; /**< the name of this neighborhood */
395 NH_FIXINGRATE fixingrate; /**< fixing rate for this neighborhood */
396 HEUR_STATS stats; /**< statistics for this neighborhood */
397 int nodelimit; /**< nodelimit for next execution */
398 DECL_VARFIXINGS ((*varfixings)); /**< variable fixings callback for this neighborhood */
399 DECL_CHANGESUBSCIP ((*changesubscip)); /**< callback for subproblem changes other than variable fixings */
400 DECL_NHINIT ((*nhinit)); /**< initialization callback when a new problem is read */
401 DECL_NHEXIT ((*nhexit)); /**< deinitialization callback when exiting a problem */
402 DECL_NHFREE ((*nhfree)); /**< deinitialization callback before SCIP is freed */
403 DECL_NHREFSOL ((*nhrefsol)); /**< callback function to return a reference solution for further fixings, or NULL */
404 DECL_NHDEACTIVATE ((*nhdeactivate)); /**< callback function to deactivate neighborhoods on problems where they are irrelevant, or NULL if it is always active */
405 SCIP_Bool active; /**< is this neighborhood active or not? */
406 SCIP_Real priority; /**< positive call priority to initialize bandit algorithms */
407 int rootnodepriority; /**< heuristic's priority for call at rootnode */
408 union
409 {
410 DATA_MUTATION* mutation; /**< mutation data */
411 DATA_CROSSOVER* crossover; /**< crossover data */
412 DATA_DINS* dins; /**< dins data */
413 DATA_TRUSTREGION* trustregion; /**< trustregion data */
414 } data; /**< data object for neighborhood specific data */
415};
416
417/** diving heuristic data structure with statistics and diveset */
419{
420 SCIP_DIVESET* diveset; /**< publicly available divesets from diving heuristics */
421 HEUR_STATS* stats; /**< statistics for this diveset */
422 SCIP_Longint nodelimit; /**< node limit of diving heuristics for next execution */
423 SOLVEFREQ* solvefreqdata; /**< solve frequency data */
424 SCIP_Real priority; /**< positive call priority to initialize bandit algorithms */
425 int rootnodepriority; /**< heuristic's priority for call at rootnode */
426};
427
428/** mutation neighborhood data structure */
429struct data_mutation
430{
431 SCIP_RANDNUMGEN* rng; /**< random number generator */
432};
433
434/** crossover neighborhood data structure */
435struct data_crossover
436{
437 int nsols; /**< the number of solutions that crossover should combine */
438 SCIP_RANDNUMGEN* rng; /**< random number generator to draw from the solution pool */
439 SCIP_SOL* selsol; /**< best selected solution by crossover as reference point */
440};
441
442/** dins neighborhood data structure */
443struct data_dins
444{
445 int npoolsols; /**< number of pool solutions where binary solution values must agree */
446};
447
448struct data_trustregion
449{
450 SCIP_Real violpenalty; /**< the penalty for violating the trust region */
451};
452
453/** primal heuristic data */
454struct SCIP_HeurData
455{
456 SCIP_BANDIT* bandit; /**< bandit algorithm */
457 int* sortedindices; /**< array of indices of heuristics sorted w.r.t. heuristic priorities */
458 int counter; /**< counter to count how often the scheduler selected a heuristic in the rootnode */
459 SCIP_SOL* lastcallsol; /**< incumbent when the heuristic was last called */
460 SCIP_Longint waitingnodes; /**< number of nodes since last incumbent solution that the heuristic should wait */
461 SCIP_Longint firstcallthissol; /**< counter for the number of calls on this incumbent */
462 char banditalgo; /**< the bandit algorithm: (u)pper confidence bounds, (e)xp.3, epsilon (g)reedy */
463 int maxcallssamesol; /**< number of allowed executions of the heuristic on the same incumbent solution
464 * (-1: no limit, 0: number of active neighborhoods) */
465 int nselections; /**< number of heuristics picked by the scheduler in one call
466 * (-1: number of controlled heuristics, 0: until new incumbent is found) */
467 int nskippedcalls; /**< number of calls to heuristic we need to skip since last execution */
468 int nfailedcalls; /**< number of failed calls to heursitic since last successful one */
469 SCIP_Bool resetweights; /**< should the bandit algorithms be reset when a new problem is read? */
470 SCIP_Bool initduringroot; /**< should the heuristic be executed multiple times during the root node? */
471 int maxnconflicts; /**< maximum number of conflicts detected by diving heur so far */
472 SCIP_Bool defaultroot; /**< should the default priorities be used at the root node */
473 SCIP_Real heurtimelimit; /**< time limit for a single heuristic run */
474 /* bandit algorithm parameters */
475 SCIP_Real exp3_gamma; /**< weight between uniform (gamma ~ 1) and weight driven (gamma ~ 0) probability distribution for exp3 */
476 SCIP_Real exp3_beta; /**< reward offset between 0 and 1 at every observation for exp3 */
477 SCIP_Real epsgreedy_eps; /**< increase exploration in epsilon-greedy bandit algorithm */
478 SCIP_Bool epsgreedy_usemod; /**< TRUE if modified version of the epsilon-greedy bandit algorithm should be used */
479 SCIP_Real ucb_alpha; /**< parameter to increase the confidence width in UCB */
480 /* reward function parameters (reward is a function between 0 and 1 and thus always upper bounded by 1, even if
481 * sum of weights do not add up to 1.0) */
482 SCIP_Real solrewardweight; /**< weight by how much finding a new incumbent is rewarded in reward function */
483 SCIP_Real effortrewardweight; /**< weight by how much effort is rewarded in reward function */
484 SCIP_Real qualrewardweight; /**< weight by how much quality of a new incumbent is rewarded in reward function */
485 SCIP_Real conflictrewardweight;/**< weight by how much number of conflicts found by diving is rewarded in reward function */
486 /* diving data */
487 SCIP_SOL* sol; /**< working solution */
488 DIVING_HEUR** divingheurs; /**< array of diving heuristics */
489 int divingheurssize; /**< array size for diving heurs array */
490 int ndiving; /**< number of diving heuristics used by scheduler */
491 SCIP_Longint initdivingnodelimit;/**< initial node limit for diving heuristics */
492 SCIP_Longint maxdivingnodelimit; /**< maximum of node limits among all diving heurisitics */
493 /* LNS data */
494 NH** neighborhoods; /**< array of neighborhoods */
495 SCIP_Longint nodesoffset; /**< offset added to the nodes budget */
496 SCIP_Longint maxnodes; /**< maximum number of nodes in a single sub-SCIP */
497 SCIP_Longint targetnodes; /**< targeted number of nodes to start a sub-SCIP */
498 SCIP_Longint minnodes; /**< minimum number of nodes required to start a sub-SCIP */
499 SCIP_Longint usednodes; /**< total number of nodes already spent in sub-SCIPs */
500 SCIP_Real nodesquot; /**< fraction of nodes compared to the main SCIP for budget computation */
501 SCIP_Real nodesquotmin; /**< lower bound on fraction of nodes compared to the main SCIP for budget computation */
502 SCIP_Real lplimfac; /**< limit fraction of LPs per node to interrupt sub-SCIP */
503 SCIP_Real targetnodefactor; /**< factor by which target node number is eventually increased */
504 SCIP_Real fixtol; /**< tolerance by which the fixing rate may be missed without generic fixing */
505 SCIP_Real unfixtol; /**< tolerance by which the fixing rate may be exceeded without generic unfixing */
506 int nneighborhoods; /**< number of neighborhoods */
507 int nactiveneighborhoods;/**< number of active neighborhoods */
508 int ninitneighborhoods; /**< neighborhoods that were used at least one time */
509 int nsolslim; /**< limit on the number of improving solutions in a sub-SCIP call */
510 int seed; /**< initial random seed for bandit algorithms and random decisions by neighborhoods */
511 int currneighborhood; /**< index of currently selected neighborhood */
512 int ndelayedcalls; /**< the number of delayed calls */
513 SCIP_Bool usesubscipheurs; /**< should the heuristic activate other sub-SCIP heuristics during its search? */
514 SCIP_Bool subsciprandseeds; /**< should random seeds of sub-SCIPs be altered to increase diversification? */
515 SCIP_Bool copycuts; /**< should cutting planes be copied to the sub-SCIP? */
516 int initlnsnodelimit; /**< initial node limit for LNS heuristics */
517 int maxlnsnodelimit; /**< maximum of nodelimits among all LNS heuristics */
518 SCIP_Bool useredcost; /**< should reduced cost scores be used for variable prioritization? */
519 SCIP_Bool usedistances; /**< should distances from fixed variables be used for variable prioritization */
520 SCIP_Bool usepscost; /**< should pseudo cost scores be used for variable prioritization? */
521 SCIP_Bool uselocalredcost; /**< should local reduced costs be used for generic (un)fixing? */
522};
523
524/** event handler data */
525struct SCIP_EventData
526{
527 SCIP_VAR** subvars; /**< the variables of the subproblem */
528 SCIP* sourcescip; /**< original SCIP data structure */
529 SCIP_HEUR* heur; /**< scheduler heuristic structure */
530 SCIP_Longint nodelimit; /**< node limit of the run */
531 SCIP_Real lplimfac; /**< limit fraction of LPs per node to interrupt sub-SCIP */
532 HEUR_STATS* runstats; /**< run statistics for the current neighborhood */
533};
534
535/** represents limits for the sub-SCIP solving process */
536struct SolveLimits
537{
538 SCIP_Longint nodelimit; /**< maximum number of solving nodes for the sub-SCIP */
539 SCIP_Real memorylimit; /**< memory limit for the sub-SCIP */
540 SCIP_Real timelimit; /**< time limit for the sub-SCIP */
541 SCIP_Longint stallnodes; /**< maximum number of nodes without (primal) stalling */
542};
543
545
546/** data structure that can be used for variable prioritization for additional fixings */
547struct VarPrio
548{
549 SCIP* scip; /**< SCIP data structure */
550 SCIP_Real* randscores; /**< random scores for prioritization */
551 int* distances; /**< breadth-first distances from already fixed variables */
552 SCIP_Real* redcostscores; /**< reduced cost scores for fixing a variable to a reference value */
553 SCIP_Real* pscostscores; /**< pseudocost scores for fixing a variable to a reference value */
554 unsigned int useredcost:1; /**< should reduced cost scores be used for variable prioritization? */
555 unsigned int usedistances:1; /**< should distances from fixed variables be used for variable prioritization */
556 unsigned int usepscost:1; /**< should pseudo cost scores be used for variable prioritization? */
557};
558
559/*
560 * Local methods
561 */
562
563/** Reset target fixing rate */
564static
566 SCIP* scip, /**< SCIP data structure */
567 NH_FIXINGRATE* fixingrate /**< heuristic fixing rate */
568 )
569{
570 assert(scip != NULL);
571 assert(fixingrate != NULL);
572 fixingrate->increment = FIXINGRATE_STARTINC;
573
574 /* always start with the most conservative value */
575 fixingrate->targetfixingrate = fixingrate->maxfixingrate;
576
577 return SCIP_OKAY;
578}
579
580/** update increment for fixing rate */
581static
583 NH_FIXINGRATE* fx /**< fixing rate */
584 )
585{
586 fx->increment *= FIXINGRATE_DECAY;
587 fx->increment = MAX(fx->increment, LRATEMIN);
588}
589
590/** increase fixing rate
591 *
592 * decrease also the rate by which the target fixing rate is adjusted
593 */
594static
596 NH_FIXINGRATE* fx /**< fixing rate */
597 )
598{
599 fx->targetfixingrate += fx->increment;
600 fx->targetfixingrate = MIN(fx->targetfixingrate, fx->maxfixingrate);
601}
602
603/** decrease fixing rate
604 *
605 * decrease also the rate by which the target fixing rate is adjusted
606 */
607static
609 NH_FIXINGRATE* fx /**< fixing rate */
610 )
611{
612 fx->targetfixingrate -= fx->increment;
613 fx->targetfixingrate = MAX(fx->targetfixingrate, fx->minfixingrate);
614}
615
616/** update fixing rate based on the results of the current run */
617static
619 NH* neighborhood, /**< neighborhood */
620 SCIP_STATUS subscipstatus, /**< status of the sub-SCIP run */
621 HEUR_STATS* runstats /**< run statistics for this run */
622 )
623{
625
626 fx = &neighborhood->fixingrate;
627
628 switch (subscipstatus)
629 {
635 /* decrease the fixing rate (make subproblem harder) */
637 break;
643 /* increase the fixing rate (make the subproblem easier) only if no solution was found */
644 if( runstats->nbestsolsfound <= 0 )
646 break;
647 /* fall through cases to please lint */
654 default:
655 break;
656 }
657
659}
660
661/** reset the currently active neighborhood */
662static
665 )
666{
667 assert(heurdata != NULL);
668 heurdata->currneighborhood = -1;
669 heurdata->ndelayedcalls = 0;
670}
671
672/** reset target node limit */
673static
675 SCIP_HEURDATA* heurdata /**< heuristic data */
676 )
677{
678 heurdata->targetnodes = heurdata->minnodes;
679}
680
681/** Reset neighborhood statistics */
682static
684 SCIP* scip, /**< SCIP data structure */
685 HEUR_STATS* stats, /**< heuristic statistics */
686 SCIP_Bool usediving /**< TRUE if the statistics belong to a diving heuristic */
687 )
688{
689 assert(scip != NULL);
690 assert(stats != NULL);
691
692 stats->nbestsolsfound = 0;
693 stats->nruns = 0;
694 stats->nrunsbestsol = 0;
695 stats->nsolsfound = 0;
696 stats->usednodes = 0L;
697 stats->nfixings = 0L;
698 stats->nbacktracks = 0L;
699 stats->nconflicts = 0L;
700 stats->nprobnodes = 0L;
701 stats->divingdepth = 0;
702
705
706 /* if we use diving, these stats are not used (and memory not allocated) */
707 if( ! usediving )
708 {
710 }
711
712 return SCIP_OKAY;
713}
714
715/** create a neighborhood of the specified name and include it into the scheduler heuristic */
716static
718 SCIP* scip, /**< SCIP data structure */
719 SCIP_HEURDATA* heurdata, /**< heuristic data of the scheduler heuristic */
720 NH** neighborhood, /**< pointer to store the neighborhood */
721 const char* name, /**< name for this neighborhood */
722 SCIP_Real minfixingrate, /**< default value for minfixingrate parameter of this neighborhood */
723 SCIP_Real maxfixingrate, /**< default value for maxfixingrate parameter of this neighborhood */
724 SCIP_Bool active, /**< default value for active parameter of this neighborhood */
725 int priority, /**< priority for heuristic in rootnode */
726 DECL_VARFIXINGS ((*varfixings)), /**< variable fixing callback for this neighborhood, or NULL */
727 DECL_CHANGESUBSCIP ((*changesubscip)), /**< subscip changes callback for this neighborhood, or NULL */
728 DECL_NHINIT ((*nhinit)), /**< initialization callback for neighborhood, or NULL */
729 DECL_NHEXIT ((*nhexit)), /**< deinitialization callback for neighborhood, or NULL */
730 DECL_NHFREE ((*nhfree)), /**< deinitialization callback before SCIP is freed, or NULL */
731 DECL_NHREFSOL ((*nhrefsol)), /**< callback function to return a reference solution for further fixings, or NULL */
732 DECL_NHDEACTIVATE ((*nhdeactivate)) /**< callback function to deactivate neighborhoods on problems where they are irrelevant, or NULL if neighborhood is always active */
733 )
734{
736
737 assert(scip != NULL);
738 assert(heurdata != NULL);
740 assert(name != NULL);
741
744
745 SCIP_ALLOC( BMSduplicateMemoryArray(&(*neighborhood)->name, name, strlen(name)+1) );
746
747 SCIP_CALL( SCIPcreateClock(scip, &(*neighborhood)->stats.setupclock) );
748 SCIP_CALL( SCIPcreateClock(scip, &(*neighborhood)->stats.execclock) );
749
750 (*neighborhood)->changesubscip = changesubscip;
751 (*neighborhood)->varfixings = varfixings;
752 (*neighborhood)->nhinit = nhinit;
753 (*neighborhood)->nhexit = nhexit;
754 (*neighborhood)->nhfree = nhfree;
755 (*neighborhood)->nhrefsol = nhrefsol;
756 (*neighborhood)->nhdeactivate = nhdeactivate;
757
758 (*neighborhood)->rootnodepriority = priority;
759
760 /* add parameters for this neighborhood */
761 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/scheduler/%s/minfixingrate", name);
762 SCIP_CALL( SCIPaddRealParam(scip, paramname, "minimum fixing rate for this neighborhood",
763 &(*neighborhood)->fixingrate.minfixingrate, TRUE, minfixingrate, 0.0, 1.0, NULL, NULL) );
764 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/scheduler/%s/maxfixingrate", name);
765 SCIP_CALL( SCIPaddRealParam(scip, paramname, "maximum fixing rate for this neighborhood",
766 &(*neighborhood)->fixingrate.maxfixingrate, TRUE, maxfixingrate, 0.0, 1.0, NULL, NULL) );
767 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/scheduler/%s/active", name);
768 SCIP_CALL( SCIPaddBoolParam(scip, paramname, "is this neighborhood active?",
769 &(*neighborhood)->active, TRUE, active, NULL, NULL) );
770 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/scheduler/%s/priority", name);
771 SCIP_CALL( SCIPaddRealParam(scip, paramname, "positive call priority to initialize bandit algorithms",
772 &(*neighborhood)->priority, TRUE, 1.0, 1e-2, 1.0, NULL, NULL) );
773
774 /* add the neighborhood to heuristic */
775 heurdata->neighborhoods[heurdata->nneighborhoods++] = (*neighborhood);
776
777 return SCIP_OKAY;
778}
779
780/** release all data and free neighborhood */
781static
783 SCIP* scip, /**< SCIP data structure */
784 NH** neighborhood /**< pointer to neighborhood that should be freed */
785 )
786{
787 NH* nhptr;
788 assert(scip != NULL);
790
792 assert(nhptr != NULL);
793
795
796 /* release further, neighborhood specific data structures */
797 if( nhptr->nhfree != NULL )
798 {
799 SCIP_CALL( nhptr->nhfree(scip, nhptr) );
800 }
801
802 SCIP_CALL( SCIPfreeClock(scip, &nhptr->stats.setupclock) );
803 SCIP_CALL( SCIPfreeClock(scip, &nhptr->stats.execclock) );
804
807
808 return SCIP_OKAY;
809}
810
811/** initialize neighborhood specific data */
812static
814 SCIP* scip, /**< SCIP data structure */
815 NH* neighborhood /**< neighborhood to initialize */
816 )
817{
818 assert(scip != NULL);
820
821 /* call the init callback of the neighborhood */
822 if( neighborhood->nhinit != NULL )
823 {
825 }
826
827 return SCIP_OKAY;
828}
829
830/** deinitialize neighborhood specific data */
831static
833 SCIP* scip, /**< SCIP data structure */
834 NH* neighborhood /**< neighborhood to initialize */
835 )
836{
837 assert(scip != NULL);
839
840 if( neighborhood->nhexit != NULL )
841 {
843 }
844
845 return SCIP_OKAY;
846}
847
848/** creates a new solution for the original problem by copying the solution of the subproblem */
849static
851 SCIP* subscip, /**< SCIP data structure of the subproblem */
852 SCIP_EVENTDATA* eventdata /**< event handler data */
853 )
854{
855 SCIP* sourcescip; /* original SCIP data structure */
856 SCIP_VAR** subvars; /* the variables of the subproblem */
857 SCIP_HEUR* heur; /* scheduler heuristic structure */
858 SCIP_SOL* subsol; /* solution of the subproblem */
859 SCIP_SOL* newsol; /* solution to be created for the original problem */
860 SCIP_Bool success;
861 HEUR_STATS* runstats;
863
864 assert(subscip != NULL);
865
866 subsol = SCIPgetBestSol(subscip);
867 assert(subsol != NULL);
868
869 sourcescip = eventdata->sourcescip;
870 subvars = eventdata->subvars;
871 heur = eventdata->heur;
872 runstats = eventdata->runstats;
873 assert(sourcescip != NULL);
874 assert(sourcescip != subscip);
875 assert(heur != NULL);
876 assert(subvars != NULL);
877 assert(runstats != NULL);
878
879 SCIP_CALL( SCIPtranslateSubSol(sourcescip, subscip, subsol, heur, subvars, &newsol) );
880
881 oldbestsol = SCIPgetBestSol(sourcescip);
882
883 /* try to add new solution to scip and free it immediately */
885
886 if( success )
887 {
888 runstats->nsolsfound++;
889 if( SCIPgetBestSol(sourcescip) != oldbestsol )
890 runstats->nbestsolsfound++;
891 }
892
893 /* update new upper bound for reward later */
894 runstats->newupperbound = SCIPgetUpperbound(sourcescip);
895
896 return SCIP_OKAY;
897}
898
899/** release all data and free diving heuristic */
900static
902 SCIP* scip, /**< SCIP data structure */
903 DIVING_HEUR** divingheur /**< pointer to diving heuristic that should be freed */
904 )
905{
907 assert(scip != NULL);
909
912
913 SCIP_CALL( SCIPfreeClock(scip, &divingheurptr->stats->setupclock) );
914 SCIP_CALL( SCIPfreeClock(scip, &divingheurptr->stats->execclock) );
915
916 SCIPfreeBlockMemory(scip, &divingheurptr->solvefreqdata);
919
920 return SCIP_OKAY;
921}
922
923/* ---------------- Callback methods of event handler ---------------- */
924
925/** execution callback of the event handler
926 *
927 * transfer new solutions or interrupt the solving process manually
928 */
929static
931{
932 assert(eventhdlr != NULL);
933 assert(eventdata != NULL);
935 assert(event != NULL);
937 assert(eventdata != NULL);
938
939 /* treat the different atomic events */
940 switch( SCIPeventGetType(event) )
941 {
944 /* try to transfer the solution to the original SCIP */
945 SCIP_CALL( transferSolution(scip, eventdata) );
946 break;
948 /* interrupt solution process of sub-SCIP */
949 if( SCIPgetNLPs(scip) > eventdata->lplimfac * eventdata->nodelimit )
950 {
951 SCIPdebugMsg(scip, "interrupt after %" SCIP_LONGINT_FORMAT " LPs\n", SCIPgetNLPs(scip));
953 }
954 break;
955 default:
956 break;
957 }
958
959 return SCIP_OKAY;
960}
961
962/** initialize heuristic statistics before the next run */
963static
965 SCIP* scip, /**< SCIP data structure */
966 HEUR_STATS* stats /**< run statistics */
967 )
968{
969 stats->nbestsolsfound = 0;
970 stats->nsolsfound = 0;
971 stats->usednodes = 0L;
972 stats->nprobnodes = 0L;
973 stats->nbacktracks = 0L;
974 stats->nconflicts = 0L;
975 stats->nfixings = 0;
976 stats->divingdepth = 0;
979}
980
981/** update run stats after the sub SCIP was solved */
982static
984 HEUR_STATS* stats, /**< run statistics */
985 SCIP* subscip /**< sub-SCIP instance, or NULL */
986 )
987{
988 /* treat an untransformed subscip as if none was created */
989 if( subscip != NULL && ! SCIPisTransformed(subscip) )
990 subscip = NULL;
991
992 stats->usednodes = subscip != NULL ? SCIPgetNNodes(subscip) : 0L;
993}
994
995/** get the histogram index for this status */
996static
998 SCIP_STATUS subscipstatus /**< sub-SCIP status */
999 )
1000{
1001 switch (subscipstatus)
1002 {
1004 return (int)HIDX_OPT;
1006 return (int)HIDX_INFEAS;
1008 return (int)HIDX_NODELIM;
1010 return (int)HIDX_STALLNODE;
1013 return (int)HIDX_SOLLIM;
1015 return (int)HIDX_USR;
1016 default:
1017 return (int)HIDX_OTHER;
1018 } /*lint !e788*/
1019}
1020
1021/** print neighborhood statistics */
1022static
1024 SCIP* scip, /**< SCIP data structure */
1025 SCIP_HEURDATA* heurdata, /**< heuristic data */
1026 FILE* file /**< file handle, or NULL for standard out */
1027 )
1028{
1029 int i;
1030 int j;
1032
1033 SCIPinfoMessage(scip, file, "LNS (Scheduler) : %10s %10s %10s %10s %10s %10s %10s %10s %10s %10s %10s %4s %4s %4s %4s %4s %4s %4s %4s\n",
1034 "Calls", "SetupTime", "SolveTime", "SolveNodes", "Sols", "Best", "Exp3", "Exp3-IX", "EpsGreedy", "UCB", "TgtFixRate",
1035 "Opt", "Inf", "Node", "Stal", "Sol", "Usr", "Othr", "Actv");
1036
1037 /* loop over neighborhoods and fill in statistics */
1038 for( i = 0; i < heurdata->nneighborhoods; ++i )
1039 {
1041 SCIP_Real proba;
1042 SCIP_Real probaix;
1043 SCIP_Real ucb;
1044 SCIP_Real epsgreedyweight;
1045
1046 neighborhood = heurdata->neighborhoods[i];
1047 SCIPinfoMessage(scip, file, " %-17s:", neighborhood->name);
1048 SCIPinfoMessage(scip, file, " %10d", neighborhood->stats.nruns);
1049 SCIPinfoMessage(scip, file, " %10.2f", SCIPgetClockTime(scip, neighborhood->stats.setupclock) );
1050 SCIPinfoMessage(scip, file, " %10.2f", SCIPgetClockTime(scip, neighborhood->stats.execclock) );
1051 SCIPinfoMessage(scip, file, " %10" SCIP_LONGINT_FORMAT, neighborhood->stats.usednodes );
1052 SCIPinfoMessage(scip, file, " %10" SCIP_LONGINT_FORMAT, neighborhood->stats.nsolsfound);
1053 SCIPinfoMessage(scip, file, " %10" SCIP_LONGINT_FORMAT, neighborhood->stats.nbestsolsfound);
1054
1055 proba = 0.0;
1056 probaix = 0.0;
1057 ucb = 1.0;
1058 epsgreedyweight = -1.0;
1059
1060 if( heurdata->bandit != NULL && i < heurdata->nactiveneighborhoods )
1061 {
1062 switch (heurdata->banditalgo)
1063 {
1064 case 'u':
1065 ucb = SCIPgetConfidenceBoundUcb(heurdata->bandit, i + heurdata->ndiving ); /* note: we need to shift the index since LNS heuristics come after diving */
1066 break;
1067 case 'g':
1069 break;
1070 case 'e':
1071 proba = SCIPgetProbabilityExp3(heurdata->bandit, i + heurdata->ndiving);
1072 break;
1073 case 'i':
1074 probaix = SCIPgetProbabilityExp3IX(heurdata->bandit, i + heurdata->ndiving);
1075 break;
1076 default:
1077 break;
1078 }
1079 }
1080
1081 SCIPinfoMessage(scip, file, " %10.5f", proba);
1082 SCIPinfoMessage(scip, file, " %10.5f", probaix);
1083 SCIPinfoMessage(scip, file, " %10.5f", epsgreedyweight);
1084 SCIPinfoMessage(scip, file, " %10.5f", ucb);
1085 SCIPinfoMessage(scip, file, " %10.3f", neighborhood->fixingrate.targetfixingrate);
1086
1087 /* loop over status histogram */
1088 for( j = 0; j < NHISTENTRIES; ++j )
1089 SCIPinfoMessage(scip, file, " %4d", neighborhood->stats.statushist[statusses[j]]);
1090
1091 SCIPinfoMessage(scip, file, " %4d", i < heurdata->nactiveneighborhoods ? 1 : 0);
1092 SCIPinfoMessage(scip, file, "\n");
1093 }
1094}
1095
1096/** print diving heuristic statistics */
1097static
1099 SCIP* scip, /**< SCIP data structure */
1100 SCIP_HEURDATA* heurdata, /**< heuristic data */
1101 FILE* file /**< file handle, or NULL for standard out */
1102 )
1103{
1104 int i;
1105
1106 SCIPinfoMessage(scip, file, "Diving (Scheduler) : %10s %10s %10s %10s %10s %10s %10s %10s %10s %10s %10s %10s \n",
1107 "Calls", "SetupTime", "SolveTime", "SolveNodes", "Sols", "Best", "Exp3", "Exp3-IX", "EpsGreedy", "UCB", "LPResolveQuot", "MaxDiveDepth");
1108
1109 /* loop over neighborhoods and fill in statistics */
1110 for( i = 0; i < heurdata->ndiving; ++i )
1111 {
1113 SCIP_Real proba;
1114 SCIP_Real probaix;
1115 SCIP_Real ucb;
1116 SCIP_Real epsgreedyweight;
1117
1118 divingheur = heurdata->divingheurs[i];
1119 SCIPinfoMessage(scip, file, " %-17s:", SCIPdivesetGetName(divingheur->diveset));
1120 SCIPinfoMessage(scip, file, " %10d", divingheur->stats->nruns);
1121 SCIPinfoMessage(scip, file, " %10.2f", SCIPgetClockTime(scip, divingheur->stats->setupclock) );
1122 SCIPinfoMessage(scip, file, " %10.2f", SCIPgetClockTime(scip, divingheur->stats->execclock) );
1123 SCIPinfoMessage(scip, file, " %10" SCIP_LONGINT_FORMAT, divingheur->stats->nprobnodes );
1124 SCIPinfoMessage(scip, file, " %10" SCIP_LONGINT_FORMAT, divingheur->stats->nsolsfound);
1125 SCIPinfoMessage(scip, file, " %10" SCIP_LONGINT_FORMAT, divingheur->stats->nbestsolsfound);
1126
1127 proba = 0.0;
1128 probaix = 0.0;
1129 ucb = 1.0;
1130 epsgreedyweight = -1.0;
1131
1132 if( heurdata->bandit != NULL )
1133 {
1134 switch (heurdata->banditalgo)
1135 {
1136 case 'u':
1138 break;
1139 case 'g':
1141 break;
1142 case 'e':
1144 break;
1145 case 'i':
1147 break;
1148 default:
1149 break;
1150 }
1151 }
1152
1153 SCIPinfoMessage(scip, file, " %10.5f", proba);
1154 SCIPinfoMessage(scip, file, " %10.5f", probaix);
1155 SCIPinfoMessage(scip, file, " %10.5f", epsgreedyweight);
1156 SCIPinfoMessage(scip, file, " %10.5f", ucb);
1157 SCIPinfoMessage(scip, file, " %10.3f", divingheur->solvefreqdata->currentsolvefreq);
1158 SCIPinfoMessage(scip, file, " %10lld", divingheur->nodelimit);
1159
1160 SCIPinfoMessage(scip, file, "\n");
1161 }
1162}
1163
1164/** update the statistics of the diving heuristic based on the heuristic run */
1165static
1167 HEUR_STATS* runstats, /**< run statistics */
1168 DIVING_HEUR* divingheur /**< the selected diving heuristic or NULL if LNS was used */
1169 )
1170{ /*lint --e{715}*/
1171 HEUR_STATS* stats;
1172
1174
1175 stats = divingheur->stats;
1176
1177 /* update diving specific statistics */
1178 stats->nprobnodes += runstats->nprobnodes;
1179 stats->nbacktracks += runstats->nbacktracks;
1180 stats->nconflicts += runstats->nconflicts;
1181
1182 /* copy run statistics into heur statistics */
1183 stats->nbestsolsfound += runstats->nbestsolsfound;
1184 stats->nsolsfound += runstats->nsolsfound;
1185 stats->nruns += 1;
1186
1187 if( runstats->nbestsolsfound > 0 )
1189 else if( runstats->nsolsfound > 0 )
1190 stats->nrunsbestsol++;
1191}
1192
1193/** update the statistics of LNS heuristic based on the heuristic run */
1194static
1196 HEUR_STATS* runstats, /**< run statistics */
1197 NH* neighborhood, /**< the selected neighborhood or NULL if diving was used */
1198 SCIP_STATUS* subscipstatus /**< status of the sub-SCIP solve or NULL if diving was used */
1199 )
1200{ /*lint --e{715}*/
1201 HEUR_STATS* stats;
1202
1204
1205 stats = &neighborhood->stats;
1206
1207 /* update LNS specific statistics */
1208 stats->usednodes += runstats->usednodes;
1209 ++stats->statushist[getHistIndex(*subscipstatus)]; /* update the counter for the subscip status */
1210
1211 /* copy run statistics into heur statistics */
1212 stats->nbestsolsfound += runstats->nbestsolsfound;
1213 stats->nsolsfound += runstats->nsolsfound;
1214 stats->nruns += 1;
1215
1216 if( runstats->nbestsolsfound > 0 )
1218 else if( runstats->nsolsfound > 0 )
1219 stats->nrunsbestsol++;
1220}
1221
1222/** sort callback for variable pointers using the ALNS variable prioritization
1223 *
1224 * the variable prioritization works hierarchically as follows. A variable
1225 * a has the higher priority over b iff
1226 *
1227 * - variable distances should be used and a has a smaller distance than b
1228 * - variable reduced costs should be used and a has a smaller score than b
1229 * - variable pseudo costs should be used and a has a smaller score than b
1230 * - based on previously assigned random scores
1231 *
1232 * @note: distances are context-based. For fixing more variables,
1233 * distances are initialized from the already fixed variables.
1234 * For unfixing variables, distances are initialized starting
1235 * from the unfixed variables
1236 */
1237static
1239{ /*lint --e{715}*/
1241
1242 varprio = (VARPRIO*)dataptr;
1243 assert(varprio != NULL);
1244 assert(varprio->randscores != NULL);
1245
1246 if( ind1 == ind2 )
1247 return 0;
1248
1249 /* priority is on distances, if enabled. The variable which is closer in a breadth-first search sense to
1250 * the already fixed variables has precedence */
1251 if( varprio->usedistances )
1252 {
1253 int dist1;
1254 int dist2;
1255
1256 dist1 = varprio->distances[ind1];
1257 dist2 = varprio->distances[ind2];
1258
1259 if( dist1 < 0 )
1260 dist1 = INT_MAX;
1261
1262 if( dist2 < 0 )
1263 dist2 = INT_MAX;
1264
1265 assert(varprio->distances != NULL);
1266 if( dist1 < dist2 )
1267 return -1;
1268 else if( dist1 > dist2 )
1269 return 1;
1270 }
1271
1272 assert(! varprio->usedistances || varprio->distances[ind1] == varprio->distances[ind2]);
1273
1274 /* if the indices tie considering distances or distances are disabled -> use reduced cost information instead */
1275 if( varprio->useredcost )
1276 {
1277 assert(varprio->redcostscores != NULL);
1278
1279 if( varprio->redcostscores[ind1] < varprio->redcostscores[ind2] )
1280 return -1;
1281 else if( varprio->redcostscores[ind1] > varprio->redcostscores[ind2] )
1282 return 1;
1283 }
1284
1285 /* use pseudo cost scores if reduced costs are disabled or a tie was found */
1286 if( varprio->usepscost )
1287 {
1288 assert(varprio->pscostscores != NULL);
1289
1290 /* prefer the variable with smaller pseudocost score */
1291 if( varprio->pscostscores[ind1] < varprio->pscostscores[ind2] )
1292 return -1;
1293 else if( varprio->pscostscores[ind1] > varprio->pscostscores[ind2] )
1294 return 1;
1295 }
1296
1297 if( varprio->randscores[ind1] < varprio->randscores[ind2] )
1298 return -1;
1299 else if( varprio->randscores[ind1] > varprio->randscores[ind2] )
1300 return 1;
1301
1302 return ind1 - ind2;
1303}
1304
1305/** Compute the reduced cost score for this variable in the reference solution */
1306static
1308 SCIP* scip, /**< SCIP data structure */
1309 SCIP_VAR* var, /**< the variable for which the score should be computed */
1310 SCIP_Real refsolval, /**< solution value in reference solution */
1311 SCIP_Bool uselocalredcost /**< should local reduced costs be used for generic (un)fixing? */
1312 )
1313{
1314 SCIP_Real bestbound;
1315 SCIP_Real redcost;
1316 SCIP_Real score;
1317 assert(scip != NULL);
1318 assert(var != NULL);
1319
1320 /* prefer column variables */
1322 return SCIPinfinity(scip);
1323
1324 if( ! uselocalredcost )
1325 {
1326 redcost = SCIPvarGetBestRootRedcost(var);
1327
1329
1330 /* using global reduced costs, the two factors yield a nonnegative score within tolerances */
1334 }
1335 else
1336 {
1337 /* this can be safely asserted here, since the heuristic would not reach this point, otherwise */
1340
1341 redcost = SCIPgetVarRedcost(scip, var);
1342
1344 }
1345
1348
1349 score = redcost * (refsolval - bestbound);
1350
1351 /* max out numerical inaccuracies from global scores */
1352 if( ! uselocalredcost )
1353 score = MAX(score, 0.0);
1354
1355 return score;
1356}
1357
1358/** get the pseudo cost score of this variable with respect to the reference solution */
1359static
1361 SCIP* scip, /**< SCIP data structure */
1362 SCIP_VAR* var, /**< the variable for which the score should be computed */
1363 SCIP_Real refsolval, /**< solution value in reference solution */
1364 SCIP_Bool uselocallpsol /**< should local LP solution be used? */
1365 )
1366{
1367 SCIP_Real lpsolval;
1368
1369 assert(scip != NULL);
1370 assert(var != NULL);
1371
1372 /* variables that aren't LP columns have no pseudocost score */
1374 return 0.0;
1375
1377
1378 /* the score is 0.0 if the values are equal */
1379 if( SCIPisEQ(scip, lpsolval, refsolval) )
1380 return 0.0;
1381 else
1382 return SCIPgetVarPseudocostVal(scip, var, refsolval - lpsolval);
1383}
1384
1385/** add variable and solution value to buffer data structure for variable fixings. The method checks if
1386 * the value still lies within the variable bounds. The value stays unfixed otherwise.
1387 */
1388static
1390 SCIP* scip, /**< SCIP data structure */
1391 SCIP_VAR* var, /**< (source) SCIP variable that should be added to the buffer */
1392 SCIP_Real val, /**< fixing value for this variable */
1393 SCIP_VAR** varbuf, /**< variable buffer to store variables that should be fixed */
1394 SCIP_Real* valbuf, /**< value buffer to store fixing values */
1395 int* nfixings, /**< pointer to number of fixed buffer variables, will be increased by 1 */
1396 SCIP_Bool integer /**< is this an integer variable? */
1397 )
1398{
1400 assert(*nfixings < SCIPgetNVars(scip));
1401
1402 /* round the value to its nearest integer */
1403 if( integer )
1404 val = SCIPfloor(scip, val + 0.5);
1405
1406 /* only add fixing if it is still valid within the global variable bounds. Invalidity
1407 * of this solution value may come from a dual reduction that was performed after the solution from which
1408 * this value originated was found
1409 */
1410 if( SCIPvarGetLbGlobal(var) <= val && val <= SCIPvarGetUbGlobal(var) )
1411 {
1412 varbuf[*nfixings] = var;
1413 valbuf[*nfixings] = val;
1414 ++(*nfixings);
1415 }
1416}
1417
1418/** fix additional variables found in feasible reference solution if the ones that the neighborhood found were not enough
1419 *
1420 * use not always the best solution for the values, but a reference solution provided by the neighborhood itself
1421 *
1422 * @note it may happen that the target fixing rate is not completely reached. This is the case if intermediate,
1423 * dual reductions render the solution values of the reference solution infeasible for
1424 * the current, global variable bounds.
1425 */
1426static
1428 SCIP* scip, /**< SCIP data structure */
1429 SCIP_HEURDATA* heurdata, /**< heuristic data of the Scheduler neighborhood */
1430 SCIP_SOL* refsol, /**< feasible reference solution for more variable fixings */
1431 SCIP_VAR** varbuf, /**< buffer array to store variables to fix */
1432 SCIP_Real* valbuf, /**< buffer array to store fixing values */
1433 int* nfixings, /**< pointer to store the number of fixings */
1434 int ntargetfixings, /**< number of required target fixings */
1435 SCIP_Bool* success /**< pointer to store whether the target fixings have been successfully reached */
1436 )
1437{
1439 SCIP_VAR** vars;
1440 SCIP_Real* redcostscores;
1441 SCIP_Real* pscostscores;
1442 SCIP_Real* solvals;
1443 SCIP_RANDNUMGEN* rng;
1445 SCIP_Bool* isfixed;
1446 int* distances;
1447 int* perm;
1448 SCIP_Real* randscores;
1449 int nbinvars;
1450 int nintvars;
1451 int nbinintvars;
1452 int nvars;
1453 int b;
1454 int nvarstoadd;
1455 int nunfixedvars;
1456
1457 assert(scip != NULL);
1458 assert(varbuf != NULL);
1459 assert(nfixings != NULL);
1460 assert(success != NULL);
1461 assert(heurdata != NULL);
1462 assert(refsol != NULL);
1463
1464 *success = FALSE;
1465
1467
1469
1471 return SCIP_OKAY;
1472
1473 /* determine the number of required additional fixings */
1474 nvarstoadd = ntargetfixings - *nfixings;
1475 if( nvarstoadd == 0 )
1476 return SCIP_OKAY;
1477
1478 varprio.usedistances = heurdata->usedistances && (*nfixings >= 1);
1479 varprio.useredcost = heurdata->useredcost;
1480 varprio.usepscost = heurdata->usepscost;
1481 varprio.scip = scip;
1482 rng = SCIPbanditGetRandnumgen(heurdata->bandit);
1483 assert(rng != NULL);
1484
1487 SCIP_CALL( SCIPallocBufferArray(scip, &distances, nvars) );
1488 SCIP_CALL( SCIPallocBufferArray(scip, &redcostscores, nbinintvars) );
1492 SCIP_CALL( SCIPallocBufferArray(scip, &pscostscores, nbinintvars) );
1493
1494 /* initialize variable graph distances from already fixed variables */
1495 if( varprio.usedistances )
1496 {
1498 }
1499 else
1500 {
1501 /* initialize all equal distances to make them irrelevant */
1502 BMSclearMemoryArray(distances, nbinintvars);
1503 }
1504
1506
1507 /* mark binary and integer variables if they are fixed */
1508 for( b = 0; b < *nfixings; ++b )
1509 {
1510 int probindex;
1511
1512 assert(varbuf[b] != NULL);
1513 probindex = SCIPvarGetProbindex(varbuf[b]);
1514 assert(probindex >= 0);
1515
1516 if( probindex < nbinintvars )
1517 isfixed[probindex] = TRUE;
1518 }
1519
1521
1522 /* assign scores to unfixed every discrete variable of the problem */
1523 nunfixedvars = 0;
1524 for( b = 0; b < nbinintvars; ++b )
1525 {
1526 SCIP_VAR* var = vars[b];
1527
1528 /* filter fixed variables */
1529 if( isfixed[b] )
1530 continue;
1531
1532 /* filter variables with a solution value outside its global bounds */
1533 if( solvals[b] < SCIPvarGetLbGlobal(var) - 0.5 || solvals[b] > SCIPvarGetUbGlobal(var) + 0.5 )
1534 continue;
1535
1536 redcostscores[nunfixedvars] = getVariableRedcostScore(scip, var, solvals[b], heurdata->uselocalredcost);
1537 pscostscores[nunfixedvars] = getVariablePscostScore(scip, var, solvals[b], heurdata->uselocalredcost);
1538
1540 perm[nunfixedvars] = nunfixedvars;
1541 randscores[nunfixedvars] = SCIPrandomGetReal(rng, 0.0, 1.0);
1542
1543 /* these assignments are based on the fact that nunfixedvars <= b */
1544 solvals[nunfixedvars] = solvals[b];
1545 distances[nunfixedvars] = distances[b];
1546
1547 //SCIPdebugMsg(scip, "Var <%s> scores: dist %3d, red cost %15.9g, pscost %15.9g rand %6.4f\n",
1548 // SCIPvarGetName(var), distances[nunfixedvars], redcostscores[nunfixedvars],
1549 // pscostscores[nunfixedvars], randscores[nunfixedvars]);
1550
1551 nunfixedvars++;
1552 }
1553
1554 /* use selection algorithm (order of the variables does not matter) for quickly completing the fixing */
1555 varprio.randscores = randscores;
1556 varprio.distances = distances;
1557 varprio.redcostscores = redcostscores;
1558 varprio.pscostscores = pscostscores;
1559
1561
1562 /* select the first nvarstoadd many variables according to the score */
1563 if( nvarstoadd < nunfixedvars )
1565
1566 /* loop over the first elements of the selection defined in permutation. They represent the best variables */
1567 for( b = 0; b < nvarstoadd; ++b )
1568 {
1569 int permindex = perm[b];
1570 assert(permindex >= 0);
1572
1574 }
1575
1576 *success = TRUE;
1577
1578 /* free buffer arrays */
1579 SCIPfreeBufferArray(scip, &pscostscores);
1581 SCIPfreeBufferArray(scip, &isfixed);
1582 SCIPfreeBufferArray(scip, &solvals);
1583 SCIPfreeBufferArray(scip, &redcostscores);
1584 SCIPfreeBufferArray(scip, &distances);
1585 SCIPfreeBufferArray(scip, &perm);
1586 SCIPfreeBufferArray(scip, &randscores);
1587
1588 return SCIP_OKAY;
1589}
1590
1591/** create the bandit algorithm for the heuristic depending on the user parameter */
1592static
1594 SCIP* scip, /**< SCIP data structure */
1595 SCIP_HEURDATA* heurdata, /**< heuristic data structure */
1596 SCIP_Real* priorities, /**< call priorities for active neighborhoods */
1597 unsigned int initseed /**< initial random seed */
1598 )
1599{
1600 int nactions;
1601
1602 nactions = heurdata->nactiveneighborhoods + heurdata->ndiving;
1603
1604 switch (heurdata->banditalgo)
1605 {
1606 case 'u':
1607 SCIP_CALL( SCIPcreateBanditUcb(scip, &heurdata->bandit, priorities,
1608 heurdata->ucb_alpha, nactions, initseed) );
1609 break;
1610
1611 case 'e':
1612 SCIP_CALL( SCIPcreateBanditExp3(scip, &heurdata->bandit, priorities,
1613 heurdata->exp3_gamma, heurdata->exp3_beta, nactions, initseed) );
1614 break;
1615
1616 case 'i':
1617 SCIP_CALL( SCIPcreateBanditExp3IX(scip, &heurdata->bandit, priorities, nactions, initseed) );
1618 break;
1619
1620 case 'g':
1621 SCIP_CALL( SCIPcreateBanditEpsgreedy(scip, &heurdata->bandit, priorities,
1622 heurdata->epsgreedy_eps, heurdata->epsgreedy_usemod, FALSE, 0.9, 0, nactions, initseed) );
1623 break;
1624
1625 default:
1626 SCIPerrorMessage("Unknown bandit parameter %c\n", heurdata->banditalgo);
1627 return SCIP_INVALIDDATA;
1628 }
1629
1630 return SCIP_OKAY;
1631}
1632
1633/*
1634 * Callback methods of primal heuristic
1635 */
1636
1637/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
1638static
1640{ /*lint --e{715}*/
1641 assert(scip != NULL);
1642 assert(heur != NULL);
1643 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1644
1645 /* call inclusion method of primal heuristic */
1647
1648 return SCIP_OKAY;
1649}
1650
1651/** query neighborhood for a reference solution for further fixings */
1652static
1654 SCIP* scip, /**< SCIP data structure */
1655 NH* neighborhood, /**< neighborhood data structure */
1656 SCIP_SOL** solptr /**< solution pointer */
1657 )
1658{
1659 assert(solptr != NULL);
1660 assert(scip != NULL);
1662
1663 *solptr = NULL;
1664 if( neighborhood->nhrefsol != NULL )
1665 {
1668
1669 if( result == SCIP_DIDNOTFIND )
1670 *solptr = NULL;
1671 else
1672 assert(*solptr != NULL);
1673 }
1674
1675 return SCIP_OKAY;
1676}
1677
1678/** unfix some of the variables because there are too many fixed
1679 *
1680 * a variable is ideally unfixed if it is close to other unfixed variables
1681 * and fixing it has a high reduced cost impact
1682 */
1683static
1685 SCIP* scip, /**< SCIP data structure */
1686 SCIP_HEURDATA* heurdata, /**< heuristic data of neighborhood */
1687 SCIP_VAR** varbuf, /**< buffer array to store variables to fix */
1688 SCIP_Real* valbuf, /**< buffer array to store fixing values */
1689 int* nfixings, /**< pointer to store the number of fixings */
1690 int ntargetfixings, /**< number of required target fixings */
1691 SCIP_Bool* success /**< pointer to store whether the target fixings have been successfully reached */
1692 )
1693{
1695 SCIP_Real* redcostscores;
1696 SCIP_Real* pscostscores;
1697 SCIP_Real* randscores;
1700 SCIP_Real* valbufcpy;
1701 SCIP_Bool* isfixedvar;
1702 SCIP_VAR** vars;
1703 SCIP_RANDNUMGEN* rng;
1704 int* distances;
1705 int* fixeddistances;
1706 int* perm;
1707 int nvars;
1708 int i;
1709 int nbinintvars;
1710 int nunfixed;
1711
1712 *success = FALSE;
1713
1715 if( nbinintvars == 0 )
1716 return SCIP_OKAY;
1717
1718 assert(*nfixings > 0);
1719
1721 SCIP_CALL( SCIPallocBufferArray(scip, &isfixedvar, nvars) );
1723 SCIP_CALL( SCIPallocBufferArray(scip, &distances, nvars) );
1725 SCIP_CALL( SCIPallocBufferArray(scip, &redcostscores, *nfixings) );
1726 SCIP_CALL( SCIPallocBufferArray(scip, &randscores, *nfixings) );
1727 SCIP_CALL( SCIPallocBufferArray(scip, &perm, *nfixings) );
1728 SCIP_CALL( SCIPallocBufferArray(scip, &pscostscores, *nfixings) );
1729
1732
1733 /*
1734 * collect the unfixed binary and integer variables
1735 */
1736 BMSclearMemoryArray(isfixedvar, nvars);
1737 /* loop over fixed variables and mark their respective positions as fixed */
1738 for( i = 0; i < *nfixings; ++i )
1739 {
1740 int probindex = SCIPvarGetProbindex(varbuf[i]);
1741
1742 assert(probindex >= 0);
1743
1744 isfixedvar[probindex] = TRUE;
1745 }
1746
1747 nunfixed = 0;
1749 /* collect unfixed binary and integer variables */
1750 for( i = 0; i < nbinintvars; ++i )
1751 {
1752 if( ! isfixedvar[i] )
1753 unfixedvars[nunfixed++] = vars[i];
1754 }
1755
1756 varprio.usedistances = heurdata->usedistances && nunfixed > 0;
1757
1758 /* collect distances of all fixed variables from those that are not fixed */
1759 if( varprio.usedistances )
1760 {
1762
1763 for( i = 0; i < *nfixings; ++i )
1764 {
1765 int probindex = SCIPvarGetProbindex(varbuf[i]);
1766 if( probindex >= 0 )
1767 fixeddistances[i] = distances[probindex];
1768 }
1769 }
1770 else
1771 {
1773 }
1774
1775 /* collect reduced cost scores of the fixings and assign random scores */
1776 rng = SCIPbanditGetRandnumgen(heurdata->bandit);
1777 for( i = 0; i < *nfixings; ++i )
1778 {
1780 SCIP_Real fixval = valbuf[i];
1781
1782 /* use negative reduced cost and pseudo cost scores to prefer variable fixings with small score */
1783 redcostscores[i] = - getVariableRedcostScore(scip, fixedvar, fixval, heurdata->uselocalredcost);
1784 pscostscores[i] = - getVariablePscostScore(scip, fixedvar, fixval, heurdata->uselocalredcost);
1785 randscores[i] = SCIPrandomGetReal(rng, 0.0, 1.0);
1786 perm[i] = i;
1787
1788 //SCIPdebugMsg(scip, "Var <%s> scores: dist %3d, red cost %15.9g, pscost %15.9g rand %6.4f\n",
1789 // SCIPvarGetName(fixedvar), fixeddistances[i], redcostscores[i], pscostscores[i], randscores[i]);
1790 }
1791
1792 varprio.distances = fixeddistances;
1793 varprio.randscores = randscores;
1794 varprio.redcostscores = redcostscores;
1795 varprio.pscostscores = pscostscores;
1796 varprio.useredcost = heurdata->useredcost;
1797 varprio.usepscost = heurdata->usepscost;
1798 varprio.scip = scip;
1799
1800 /* scores are assigned in such a way that variables with a smaller score should be fixed last */
1802
1803 /* bring the desired variables to the front of the array */
1804 for( i = 0; i < ntargetfixings; ++i )
1805 {
1806 valbuf[i] = valbufcpy[perm[i]];
1807 varbuf[i] = varbufcpy[perm[i]];
1808 }
1809
1810 *nfixings = ntargetfixings;
1811
1812 /* free the buffer arrays in reverse order of allocation */
1815 SCIPfreeBufferArray(scip, &pscostscores);
1816 SCIPfreeBufferArray(scip, &perm);
1817 SCIPfreeBufferArray(scip, &randscores);
1818 SCIPfreeBufferArray(scip, &redcostscores);
1820 SCIPfreeBufferArray(scip, &distances);
1822 SCIPfreeBufferArray(scip, &isfixedvar);
1823
1824 *success = TRUE;
1825
1826 return SCIP_OKAY;
1827}
1828
1829/** call variable fixing callback for this neighborhood and orchestrate additional variable fixings, if necessary */
1830static
1832 SCIP* scip, /**< SCIP data structure */
1833 SCIP_HEURDATA* heurdata, /**< heuristic data of the scheduler neighborhood */
1834 NH* neighborhood, /**< neighborhood data structure */
1835 SCIP_VAR** varbuf, /**< buffer array to keep variables that should be fixed */
1836 SCIP_Real* valbuf, /**< buffer array to keep fixing values */
1837 int* nfixings, /**< pointer to store the number of variable fixings */
1838 SCIP_RESULT* result /**< pointer to store the result of the fixing operation */
1839 )
1840{
1841 int ntargetfixings;
1842 int nmaxfixings;
1843 int nminfixings;
1844 int nbinintvars;
1845
1846 assert(scip != NULL);
1848 assert(varbuf != NULL);
1849 assert(valbuf != NULL);
1850 assert(nfixings != NULL);
1851 assert(result != NULL);
1852
1853 *nfixings = 0;
1854
1856 ntargetfixings = (int)(neighborhood->fixingrate.targetfixingrate * (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip)));
1857
1858 if( neighborhood->varfixings != NULL )
1859 {
1860 SCIP_CALL( neighborhood->varfixings(scip, neighborhood, varbuf, valbuf, nfixings, result) );
1861
1862 if( *result != SCIP_SUCCESS )
1863 return SCIP_OKAY;
1864 }
1865 else if( ntargetfixings == 0 )
1866 {
1868 return SCIP_OKAY;
1869 }
1870
1871 /* compute upper and lower target fixing limits using tolerance parameters */
1872 assert(neighborhood->varfixings == NULL || *result != SCIP_DIDNOTRUN);
1874 ntargetfixings = (int)(neighborhood->fixingrate.targetfixingrate * nbinintvars);
1875 nminfixings = (int)((neighborhood->fixingrate.targetfixingrate - heurdata->fixtol) * nbinintvars);
1877 nmaxfixings = (int)((neighborhood->fixingrate.targetfixingrate + heurdata->unfixtol) * nbinintvars);
1879
1880 SCIPdebugMsg(scip, "Neighborhood Fixings/Target: %d / %d <= %d <= %d\n",*nfixings, nminfixings, ntargetfixings, nmaxfixings);
1881
1882 /* if too few fixings, use a strategy to select more variable fixings: randomized, LP graph, ReducedCost based, mix */
1883 if( (*result == SCIP_SUCCESS || *result == SCIP_DIDNOTRUN) && (*nfixings < nminfixings) )
1884 {
1885 SCIP_Bool success;
1887
1888 /* get reference solution from neighborhood */
1890
1891 /* try to fix more variables based on the reference solution */
1892 if( refsol != NULL )
1893 {
1895 }
1896 else
1897 success = FALSE;
1898
1899 if( success )
1901 else if( *result == SCIP_SUCCESS )
1903 else
1905
1906 SCIPdebugMsg(scip, "After additional fixings: %d / %d\n",*nfixings, ntargetfixings);
1907 }
1908 else if( (SCIP_Real)(*nfixings) > nmaxfixings )
1909 {
1910 SCIP_Bool success;
1911
1913
1914 assert(success);
1916 SCIPdebugMsg(scip, "Unfixed variables, fixed variables remaining: %d\n", ntargetfixings);
1917 }
1918 else
1919 {
1920 SCIPdebugMsg(scip, "No additional fixings performed\n");
1921 }
1922
1923 return SCIP_OKAY;
1924}
1925
1926/** change the sub-SCIP by restricting variable domains, changing objective coefficients, or adding constraints */
1927static
1929 SCIP* sourcescip, /**< source SCIP data structure */
1930 SCIP* targetscip, /**< target SCIP data structure */
1931 NH* neighborhood, /**< neighborhood */
1932 SCIP_VAR** targetvars, /**< array of target SCIP variables aligned with source SCIP variables */
1933 int* ndomchgs, /**< pointer to store the number of variable domain changes */
1934 int* nchgobjs, /**< pointer to store the number of changed objective coefficients */
1935 int* naddedconss, /**< pointer to store the number of added constraints */
1936 SCIP_Bool* success /**< pointer to store whether the sub-SCIP has been successfully modified */
1937 )
1938{
1939 assert(sourcescip != NULL);
1943 assert(ndomchgs != NULL);
1944 assert(nchgobjs != NULL);
1945 assert(naddedconss != NULL);
1946 assert(success != NULL);
1947
1948 *success = FALSE;
1949 *ndomchgs = 0;
1950 *nchgobjs = 0;
1951 *naddedconss = 0;
1952
1953 /* call the change sub-SCIP callback of the neighborhood */
1954 if( neighborhood->changesubscip != NULL )
1955 {
1956 SCIP_CALL( neighborhood->changesubscip(sourcescip, targetscip, neighborhood, targetvars, ndomchgs, nchgobjs, naddedconss, success) );
1957 }
1958 else
1959 {
1960 *success = TRUE;
1961 }
1962
1963 return SCIP_OKAY;
1964}
1965
1966/** set sub-SCIP solving limits */
1967static
1969 SCIP* subscip, /**< SCIP data structure */
1970 SOLVELIMITS* solvelimits /**< pointer to solving limits data structure */
1971 )
1972{
1973 assert(subscip != NULL);
1975
1976 assert(solvelimits->nodelimit >= solvelimits->stallnodes);
1977
1978 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", solvelimits->nodelimit) );
1979 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", solvelimits->stallnodes));
1980 SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", solvelimits->timelimit) );
1981 SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", solvelimits->memorylimit) );
1982
1983 return SCIP_OKAY;
1984}
1985
1986/** determine limits for a sub-SCIP */
1987static
1989 SCIP* scip, /**< SCIP data structure */
1990 SCIP_HEUR* heur, /**< this heuristic */
1991 int selection, /**< index of selected neighborhood */
1992 SOLVELIMITS* solvelimits, /**< pointer to solving limits data structure */
1993 SCIP_Bool* runagain /**< can we solve another sub-SCIP with these limits */
1994 )
1995{
1997 SCIP_Bool avoidmemout;
1998
1999 assert(scip != NULL);
2000 assert(heur != NULL);
2002 assert(runagain != NULL);
2003
2004 heurdata = SCIPheurGetData(heur);
2005
2006 /* set time and memory */
2007 SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &solvelimits->memorylimit) );
2008 SCIP_CALL( SCIPgetBoolParam(scip, "misc/avoidmemout", &avoidmemout) );
2009 solvelimits->timelimit = heurdata->heurtimelimit;
2010
2011 /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
2012 if( ! SCIPisInfinity(scip, solvelimits->memorylimit) )
2013 {
2014 solvelimits->memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
2015 solvelimits->memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
2016 }
2017
2018 /* abort if no time is left or not enough memory (we don't abort in this case if misc_avoidmemout == FALSE)
2019 * to create a copy of SCIP, including external memory usage */
2020 if( avoidmemout && solvelimits->memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 )
2021 {
2022 SCIPdebugMsg(scip, "Aborting LNS heuristic call: Not enough memory or time left.\n");
2023 *runagain = FALSE;
2024 return SCIP_OKAY;
2025 }
2026
2027 solvelimits->stallnodes = -1;
2028 solvelimits->nodelimit = (SCIP_Longint) heurdata->neighborhoods[selection]->nodelimit;
2029
2030 return SCIP_OKAY;
2031}
2032
2033/** Calculate reward based on the selected reward measure */
2034static
2035SCIP_Real getReward(
2036 SCIP* scip, /**< SCIP data structure */
2037 SCIP_HEURDATA* heurdata, /**< heuristic data of the scheduler neighborhood */
2038 int selection, /**< index of selected heuristic */
2039 HEUR_STATS* runstats, /**< run statistics */
2040 SCIP_STATUS subscipstatus /**< status of the sub-SCIP if LNS was used */
2041 )
2042{
2043 SCIP_Real totalreward;
2044 SCIP_Real effortsaved;
2045 SCIP_Real bestsolreward;
2046 SCIP_Real closedgapreward;
2047 SCIP_Real conflictreward;
2048
2049 /* compute the effort it took to execute selected heuristic */
2050 if( selection < heurdata->ndiving )
2051 effortsaved = (SCIP_Real) runstats->divingdepth / (SCIP_Real)heurdata->maxdivingnodelimit;
2052 else
2053 effortsaved = MIN(1.0, (SCIP_Real) runstats->usednodes / (SCIP_Real)heurdata->maxlnsnodelimit);
2054 effortsaved = (1.0 - effortsaved);
2055
2056 /* if LNS heuristic terminated because of the time limit, punish it */
2058 effortsaved = 0.0;
2059
2060 assert(effortsaved >= 0.0 && effortsaved <= 1.0);
2061 assert(heurdata->maxlnsnodelimit > 0);
2062 assert(heurdata->maxdivingnodelimit > 0);
2063
2064 /* compute reward for number of conflicts generated */
2065 if( selection < heurdata->ndiving )
2066 {
2067 if( runstats->nconflicts == 0 )
2068 conflictreward = 0.0;
2069 else if( heurdata->maxnconflicts > 0 )
2070 conflictreward = (SCIP_Real) runstats->nconflicts / (SCIP_Real) heurdata->maxnconflicts;
2071 else
2072 conflictreward = 1.0;
2073 }
2074 else
2075 conflictreward = 0.0; /* LNS heuristics don't add conflict constraints */
2076 assert(conflictreward >= 0.0 && conflictreward <= 1.0);
2077
2078 /* a positive reward is only assigned if a new incumbent solution was found */
2079 if( runstats->nbestsolsfound > 0 )
2080 {
2081 SCIP_Real lb;
2082 SCIP_Real ub;
2083
2084 /* the indicator function is simply 1.0 */
2085 bestsolreward = 1.0;
2086
2087 ub = runstats->newupperbound;
2088 lb = SCIPgetLowerbound(scip);
2089
2090 /* compute the closed gap reward */
2091 if( SCIPisEQ(scip, ub, lb) || SCIPisInfinity(scip, runstats->oldupperbound) ) // gap is closed or first primal solution was found
2092 closedgapreward = 1.0;
2093 else
2094 closedgapreward = (runstats->oldupperbound - ub) / (runstats->oldupperbound - lb);
2095 }
2096 else
2097 {
2098 bestsolreward = 0.0;
2099 closedgapreward = 0.0;
2100 }
2101
2102 /* compute total reward */
2103 totalreward = heurdata->effortrewardweight * effortsaved + heurdata->solrewardweight * bestsolreward
2104 + heurdata->qualrewardweight * closedgapreward + heurdata->conflictrewardweight * conflictreward;
2105 totalreward = MIN( totalreward, 1.0);
2106 assert(totalreward >= 0.0 && totalreward <= 1.0);
2107
2108 return totalreward;
2109}
2110
2111/** set up the sub-SCIP parameters, objective cutoff, and solution limits */
2112static
2114 SCIP* scip, /**< SCIP data structure */
2115 SCIP* subscip, /**< sub-SCIP data structure */
2116 SCIP_VAR** subvars, /**< array of sub-SCIP variables in the order of the main SCIP */
2117 SOLVELIMITS* solvelimits, /**< pointer to solving limits data structure */
2118 SCIP_HEUR* heur, /**< this heuristic */
2119 SCIP_Bool objchgd /**< did the objective change between the source and the target SCIP? */
2120 )
2121{
2123 SCIP_Real cutoff;
2124
2125 heurdata = SCIPheurGetData(heur);
2126
2127 /* do not abort subproblem on CTRL-C */
2128 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
2129
2130 /* disable output to console unless we are in debug mode */
2131 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
2132
2133 /* disable statistic timing inside sub SCIP */
2134 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
2135
2136#ifdef SCHEDULER_SUBSCIPOUTPUT
2137 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
2138 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 1) );
2139 /* enable statistic timing inside sub SCIP */
2140 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", TRUE) );
2141#endif
2142
2143 SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->nsolslim) );
2144
2145 /* forbid recursive call of heuristics and separators solving subMIPs */
2146 if( ! heurdata->usesubscipheurs )
2147 {
2148 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
2149 }
2150
2151 /* disable cutting plane separation */
2153
2154 /* disable expensive presolving */
2156
2157 /* use best estimate node selection */
2158 if( SCIPfindNodesel(subscip, "estimate") != NULL && ! SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
2159 {
2160 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
2161 }
2162
2163 /* use inference branching */
2164 if( SCIPfindBranchrule(subscip, "inference") != NULL && ! SCIPisParamFixed(subscip, "branching/inference/priority") )
2165 {
2166 SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
2167 }
2168
2169 /* enable conflict analysis and restrict conflict pool */
2170 if( ! SCIPisParamFixed(subscip, "conflict/enable") )
2171 {
2172 SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) );
2173 }
2174
2175 if( !SCIPisParamFixed(subscip, "conflict/useboundlp") )
2176 {
2177 SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') );
2178 }
2179
2180 if( ! SCIPisParamFixed(subscip, "conflict/maxstoresize") )
2181 {
2182 SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) );
2183 }
2184
2185 /* speed up sub-SCIP by not checking dual LP feasibility */
2186 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
2187
2188 /* add an objective cutoff */
2190 {
2192
2193 /* if the objective changed between the source and the target SCIP, encode the cutoff as a constraint */
2194 if( ! objchgd )
2195 {
2196 SCIP_CALL(SCIPsetObjlimit(subscip, cutoff));
2197 }
2198 else
2199 {
2200 SCIP_CONS* objcons;
2201 int nvars;
2202 SCIP_VAR** vars;
2203 int i;
2204
2207
2208 SCIP_CALL( SCIPcreateConsLinear(subscip, &objcons, "objbound_of_origscip", 0, NULL, NULL, -SCIPinfinity(subscip), cutoff,
2210 for( i = 0; i < nvars; ++i)
2211 {
2212 if( ! SCIPisFeasZero(subscip, SCIPvarGetObj(vars[i])) )
2213 {
2214 assert(subvars[i] != NULL);
2215 SCIP_CALL( SCIPaddCoefLinear(subscip, objcons, subvars[i], SCIPvarGetObj(vars[i])) );
2216 }
2217 }
2218 SCIP_CALL( SCIPaddCons(subscip, objcons) );
2219 SCIP_CALL( SCIPreleaseCons(subscip, &objcons) );
2220 }
2221 }
2222
2223 /* set solve limits for sub-SCIP */
2224 SCIP_CALL( setLimits(subscip, solvelimits) );
2225
2226 /* change random seed of sub-SCIP */
2227 if( heurdata->subsciprandseeds )
2228 {
2229 SCIP_CALL( SCIPsetIntParam(subscip, "randomization/randomseedshift", (int)SCIPheurGetNCalls(heur)) );
2230 }
2231
2232 return SCIP_OKAY;
2233}
2234
2235/** initialize solving frequency */
2236static
2238 SOLVEFREQ* solvefreqdata /**< diving heuristic solving freq data */
2239 )
2240{
2241 assert(solvefreqdata != NULL);
2242
2243 /* initialize solve frequency data */
2244 solvefreqdata->increment = SOLVEFREQ_STARTINC;
2245 solvefreqdata->maxsolvefreq = MAXSOLVEFREQ;
2246 solvefreqdata->minsolvefreq = MINSOLVEFREQ;
2247
2248 /* always start with the most conservative value */
2249 solvefreqdata->currentsolvefreq = solvefreqdata->minsolvefreq;
2250}
2251
2252/** update increment for solving frequency */
2253static
2255 SOLVEFREQ* solvefreqdata /**< diving heuristic solving freq data */
2256 )
2257{
2258 solvefreqdata->increment *= SOLVEFREQ_DECAY;
2259 solvefreqdata->increment = MAX(solvefreqdata->increment, LRATEMIN);
2260}
2261
2262/** increase solving frequency
2263 *
2264 * decrease also the rate by which the solving frequency is adjusted
2265 */
2266static
2268 SOLVEFREQ* solvefreqdata /**< diving heuristic solving freq data */
2269 )
2270{
2271 solvefreqdata->currentsolvefreq += solvefreqdata->increment;
2272 solvefreqdata->currentsolvefreq = MIN(solvefreqdata->currentsolvefreq, solvefreqdata->maxsolvefreq);
2273}
2274
2275/** decrease solving frequency
2276 *
2277 * decrease also the rate by which the solving frequency is adjusted
2278 */
2279static
2281 SOLVEFREQ* solvefreqdata /**< diving heuristic solving freq data */
2282 )
2283{
2284 solvefreqdata->currentsolvefreq -= solvefreqdata->increment;
2285 solvefreqdata->currentsolvefreq = MAX(solvefreqdata->currentsolvefreq, solvefreqdata->minsolvefreq);
2286}
2287
2288/** update solve frequency for diving heuristics */
2289static
2291 DIVING_HEUR* divingheur, /**< diving heuristic */
2292 HEUR_STATS* stats /**< run statistics for this run */
2293 )
2294{
2295 /* find out why diving heuristic terminated and adapt resolve frequency accordingly */
2296 if( (int) stats->nprobnodes == divingheur->nodelimit )
2297 increaseSolveFreq(divingheur->solvefreqdata);
2298 else if( stats->nsolsfound == 0 )
2299 decreaseSolveFreq(divingheur->solvefreqdata);
2300
2301 updateSolveFreqIncrement(divingheur->solvefreqdata);
2302}
2303
2304/** find publicly available divesets and store them */
2305static
2307 SCIP* scip, /**< SCIP data structure */
2308 SCIP_HEUR* heur, /**< the heuristic */
2309 SCIP_HEURDATA* heurdata /**< heuristic data */
2310 )
2311{
2312 int h;
2313 SCIP_HEUR** heurs;
2314
2315 assert(scip != NULL);
2316 assert(heur != NULL);
2317 assert(heurdata != NULL);
2318
2319 heurs = SCIPgetHeurs(scip);
2320
2321 heurdata->divingheurssize = DIVINGHEURS_INITIALSIZE;
2322 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->divingheurs, heurdata->divingheurssize) );
2323 heurdata->ndiving = 0;
2324
2325 for( h = 0; h < SCIPgetNHeurs(scip); ++h )
2326 {
2327 int d;
2328 assert(heurs[h] != NULL);
2329
2330 /* loop over divesets of this heuristic and check whether they are public */
2331 for( d = 0; d < SCIPheurGetNDivesets(heurs[h]); ++d )
2332 {
2334
2336 {
2338
2339 SCIPdebugMsg(scip, "Found publicly available diveset %s\n", SCIPdivesetGetName(diveset));
2340
2341 /* allocate memory for the diving heuristic */
2344 SCIP_CALL( SCIPallocBlockMemory(scip, &(divingheur->solvefreqdata)) );
2345
2346 /* fill struct with diving heuristic specific information */
2347 divingheur->diveset = diveset;
2348 divingheur->nodelimit = heurdata->initdivingnodelimit;
2349 divingheur->rootnodepriority = SCIPheurGetPriority(heurs[h]);
2350 divingheur->priority = 1.0;
2351
2352 initSolveFreq(divingheur->solvefreqdata);
2353 SCIP_CALL( SCIPcreateClock(scip, &(divingheur->stats->setupclock)) );
2354 SCIP_CALL( SCIPcreateClock(scip, &(divingheur->stats->execclock)) );
2356
2357 if( heurdata->ndiving == heurdata->divingheurssize )
2358 {
2359 int newsize = 2 * heurdata->divingheurssize;
2360 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &heurdata->divingheurs, heurdata->divingheurssize, newsize) );
2361 heurdata->divingheurssize = newsize;
2362 }
2363 assert( heurdata->ndiving < heurdata->divingheurssize );
2364
2365 heurdata->divingheurs[heurdata->ndiving] = divingheur;
2366 heurdata->ndiving++;
2367 }
2368 else
2369 {
2370 SCIPdebugMsg(scip, "Skipping private diveset %s\n", SCIPdivesetGetName(diveset));
2371 }
2372 }
2373 }
2374 return SCIP_OKAY;
2375}
2376
2377/** select a heuristic depending on the selected bandit algorithm */
2378static
2380 SCIP* scip, /**< SCIP data structure */
2381 SCIP_HEURDATA* heurdata, /**< heuristic data of the scheduler heuristic */
2382 int* selection /**< pointer to store the selected heuristic index */
2383 )
2384{
2385 SCIP_BANDIT* bandit;
2386 int nactions;
2387
2388 assert(scip != NULL);
2389 assert(heurdata != NULL);
2390 assert(selection != NULL);
2391
2392 *selection = -1;
2393 bandit = heurdata->bandit;
2394 nactions = heurdata->ndiving + heurdata->nactiveneighborhoods;
2395
2396 /* if we use default priorities for executing heuristics for the first time, we don't have to call
2397 * the bandit to select next action */
2398 if( heurdata->defaultroot && heurdata->counter < nactions )
2399 {
2400 *selection = heurdata->sortedindices[heurdata->counter];
2401 heurdata->counter++;
2402 }
2403 else
2404 {
2406 }
2407 assert(*selection >= 0);
2408 assert(*selection < heurdata->nactiveneighborhoods + heurdata->ndiving);
2409
2410 return SCIP_OKAY;
2411}
2412
2413/** update selection strategy with observed reward for future draws */
2414static
2416 SCIP* scip, /**< SCIP data structure */
2417 SCIP_HEURDATA* heurdata, /**< heuristic data of the scheduler heuristic */
2418 SCIP_Real reward, /**< measured reward */
2419 int selection /**< the heuristic index that was chosen */
2420 )
2421{
2422 SCIP_BANDIT* bandit;
2423
2424 assert(scip != NULL);
2425 assert(heurdata != NULL);
2426 assert(selection >= 0);
2427 assert(selection < heurdata->nneighborhoods + heurdata->ndiving);
2428
2429 bandit = heurdata->bandit;
2430
2431 SCIPdebugMsg(scip, "Rewarding bandit algorithm action %d with reward %.2f\n", selection, reward);
2433
2434 return SCIP_OKAY;
2435}
2436
2437/** execute diving heuristic */
2438static
2440 SCIP* scip, /**< SCIP data structure */
2441 SCIP_HEUR* heur, /**< scheduler heuristic */
2442 int selection, /**< the heuristic index that was chosen */
2443 HEUR_STATS* runstats, /**< statistics of the call to selection */
2444 SCIP_RESULT* result /**< pointer to store the result of the heuristic call */
2445 )
2446{
2448 DIVING_HEUR** divingheurs;
2450
2451 heurdata = SCIPheurGetData(heur);
2452 assert(heurdata != NULL);
2453
2454 divingheurs = heurdata->divingheurs;
2455 assert(divingheurs != NULL);
2456 assert(heurdata->ndiving > 0);
2458 assert(divingheurs[selection] != NULL);
2459
2460 diveset = divingheurs[selection]->diveset;
2461 assert(diveset != NULL);
2462
2463 SCIPdebugMsg(scip, "Selected diving heuristic %s (idx: %d)\n", SCIPdivesetGetName(diveset), selection);
2464
2465 /* store some data beforehand to track all improvemnts */
2472
2473 if( strcmp(SCIPdivesetGetName(diveset), "guideddiving") != 0 || (strcmp(SCIPdivesetGetName(diveset), "guideddiving") == 0
2475 {
2476 SCIP_CALL( SCIPstartClock(scip, divingheurs[selection]->stats->execclock) );
2477
2478 /* perform dive */
2480 result, FALSE, -1LL, (int) divingheurs[selection]->nodelimit,
2482
2483 SCIP_CALL( SCIPstopClock(scip, divingheurs[selection]->stats->execclock) );
2484 }
2485
2486 /* store improvements (if solution was found, what solution was found, nconflict constraints, etc.) */
2493
2494 /* update maximum number of conflicts found */
2495 heurdata->maxnconflicts = MAX(heurdata->maxnconflicts, (int) runstats->nconflicts);
2496
2497 SCIPdebugMsg(scip, "Finished executing diving heuristic %s (idx: %d) with %lld sols (%lld best sols), %lld conflicts, %lld backtracks and %lld probing nodes \n",
2499 runstats->nconflicts, runstats->nbacktracks, runstats->nprobnodes);
2500
2501 if( runstats->nbestsolsfound > 0 )
2502 SCIPdebugMsg(scip, "Upperbound changed: %g -> %g\n", runstats->oldupperbound, runstats->newupperbound);
2503
2504 assert( runstats->nbestsolsfound == 0 || runstats->oldupperbound > runstats->newupperbound );
2505
2506 return SCIP_OKAY;
2507}
2508
2509/** execute LNS heuristic */
2510static
2512 SCIP* scip, /**< SCIP data structure */
2513 SCIP_HEUR* heur, /**< scheduler heuristic */
2514 int selection, /**< the heuristic index that was chosen */
2515 HEUR_STATS* runstats, /**< statistics of the call to selection */
2516 SCIP_STATUS* subscipstatus, /**< pointer to store status of the sub-SCIP solve */
2517 SCIP_RESULT* result /**< pointer to store the result of the heuristic call */
2518 )
2519{
2521 SCIP_VAR** varbuf;
2522 SCIP_Real* valbuf;
2523 SCIP_VAR** vars;
2524 SCIP_VAR** subvars;
2525 SCIP* subscip = NULL;
2526
2527 int nfixings;
2528 int nvars;
2531 SCIP_Bool success;
2532 SCIP_Bool run;
2533
2535 SCIP_EVENTHDLR* eventhdlr;
2536 SCIP_EVENTDATA eventdata;
2538 int ndomchgs;
2539 int nchgobjs;
2540 int naddedconss;
2541 int v;
2542 SCIP_RETCODE retcode;
2544
2545 heurdata = SCIPheurGetData(heur);
2546 assert(heurdata != NULL);
2547
2550 run = TRUE;
2551
2552 SCIPdebugMsg(scip, "Selected LNS heuristic %s (idx: %d)\n", heurdata->neighborhoods[selection]->name, selection + heurdata->ndiving);
2553
2554 /* check if budget allows a run of the next selected neighborhood */
2556
2557 if( ! run )
2558 return SCIP_OKAY;
2559
2560 /* allocate memory for variable fixings buffer */
2565
2566 neighborhood = heurdata->neighborhoods[selection];
2567 SCIPdebugMsg(scip, "Running '%s' neighborhood %d\n", neighborhood->name, selection);
2568
2569 SCIP_CALL( SCIPstartClock(scip, neighborhood->stats.setupclock) );
2570
2571 /* determine variable fixings and objective coefficients of this neighborhood */
2573
2574 SCIPdebugMsg(scip, "Fix %d/%d variables, result code %d\n", nfixings, nvars, fixresult);
2575
2576 /* Fixing was not successful, either because the fixing rate was not reached (and no additional variable
2577 * prioritization was used), or the neighborhood requested a delay, e.g., because no LP relaxation solution exists
2578 * at the current node
2579 *
2580 * The scheduler heuristic keeps a delayed neighborhood active and delays itself.
2581 * TODO: handle delays
2582 */
2583 if( fixresult != SCIP_SUCCESS )
2584 {
2585 SCIP_CALL( SCIPstopClock(scip, neighborhood->stats.setupclock) );
2586
2587 SCIPdebugMsg(scip, "Aborting LNS heuristic call: Not enough variables fixed.\n");
2588
2589 *result = fixresult;
2590 goto CLEANUP;
2591 }
2592
2594
2595 neighborhood->stats.nfixings += nfixings;
2596 runstats->nfixings = nfixings;
2597
2598 SCIP_CALL( SCIPcreate(&subscip) );
2600 (void) SCIPsnprintf(probnamesuffix, SCIP_MAXSTRLEN, "scheduler_%s", neighborhood->name);
2601
2602 /* todo later: run global propagation for this set of fixings */
2604
2605 /* store sub-SCIP variables in array for faster access */
2606 for( v = 0; v < nvars; ++v )
2607 {
2608 subvars[v] = (SCIP_VAR*)SCIPhashmapGetImage(varmapf, (void *)vars[v]);
2609 }
2610
2612
2613 /* let the neighborhood add additional constraints, or restrict domains */
2614 SCIP_CALL( neighborhoodChangeSubscip(scip, subscip, neighborhood, subvars, &ndomchgs, &nchgobjs, &naddedconss, &success) );
2615
2616 if( ! success )
2617 {
2618 SCIP_CALL( SCIPstopClock(scip, neighborhood->stats.setupclock) );
2619 SCIPdebugMsg(scip, "Aborting LNS heuristic call: Problems with creating subproblem.\n");
2620 goto CLEANUP;
2621 }
2622
2623 /* set up sub-SCIP parameters */
2624 SCIP_CALL( setupSubScip(scip, subscip, subvars, &solvelimits, heur, nchgobjs > 0) );
2625
2626 /* copy the necessary data into the event data to create new solutions */
2627 eventdata.nodelimit = solvelimits.nodelimit; /*lint !e644*/
2628 eventdata.lplimfac = heurdata->lplimfac;
2629 eventdata.heur = heur;
2630 eventdata.sourcescip = scip;
2631 eventdata.subvars = subvars;
2632 eventdata.runstats = runstats;
2633
2634 /* include an event handler to transfer solutions into the main SCIP */
2636
2637 /* transform the problem before catching the events */
2638 SCIP_CALL( SCIPtransformProb(subscip) );
2639 SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_SCHEDULER, eventhdlr, &eventdata, NULL) );
2640
2641 SCIP_CALL( SCIPstopClock(scip, neighborhood->stats.setupclock) );
2642
2643 SCIP_CALL( SCIPstartClock(scip, neighborhood->stats.execclock) );
2644
2645 /* set up sub-SCIP and run presolving */
2646 retcode = SCIPpresolve(subscip);
2647 if( retcode != SCIP_OKAY )
2648 {
2649 SCIPwarningMessage(scip, "Error while presolving subproblem in Scheduler heuristic; sub-SCIP terminated with code <%d>\n", retcode);
2650 SCIP_CALL( SCIPstopClock(scip, neighborhood->stats.execclock) );
2651
2652 SCIPABORT(); /*lint --e{527}*/
2653 goto CLEANUP;
2654 }
2655
2656 /* run sub-SCIP for the given budget, and collect statistics */
2657 SCIP_CALL_ABORT( SCIPsolve(subscip) );
2658
2659#ifdef SCHEDULER_SUBSCIPOUTPUT
2660 SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
2661#endif
2662
2663 SCIP_CALL( SCIPstopClock(scip, neighborhood->stats.execclock) );
2664
2665 /* update statistics based on the sub-SCIP run results */
2666 updateRunStats(runstats, subscip);
2667 *subscipstatus = SCIPgetStatus(subscip);
2668 SCIPdebugMsg(scip, "Status of sub-SCIP run: %d\n", *subscipstatus);
2669
2670CLEANUP:
2671 if( subscip != NULL )
2672 {
2673 SCIP_CALL( SCIPfree(&subscip) );
2674 }
2675
2676 SCIPfreeBufferArray(scip, &subvars);
2679
2680 if( *result != SCIP_DELAYED && *result != SCIP_DIDNOTRUN )
2681 {
2682 /* decrease the number of neighborhoods that have not been initialized */
2683 if( neighborhood->stats.nruns == 0 )
2684 --heurdata->ninitneighborhoods;
2685
2686 heurdata->usednodes += runstats->usednodes;
2687
2688 SCIPdebugMsg(scip, "Finished executing LNS heuristic %s (idx: %d) with %lld sols (%lld best sols) and %lld nodes used.\n",
2689 neighborhood->name, selection + heurdata->ndiving, runstats->nsolsfound, runstats->nbestsolsfound, runstats->usednodes);
2690
2691 if( runstats->nbestsolsfound > 0 )
2692 SCIPdebugMsg(scip, "Upperbound changed: %g -> %g\n", runstats->oldupperbound, SCIPgetUpperbound(scip));
2693
2695 }
2696
2697 return SCIP_OKAY;
2698}
2699
2700/** execute selected heuristic */
2701static
2703 SCIP* scip, /**< SCIP data structure */
2704 SCIP_HEUR* heur, /**< scheduler heuristic */
2705 int selection, /**< the heuristic index that was chosen */
2706 HEUR_STATS* runstats, /**< statistics of call to selection */
2707 SCIP_STATUS* subscipstatus, /**< pointer to store status of the sub-SCIP solve or NULL if diving was used */
2708 SCIP_RESULT* result /**< pointer to store the result of the heuristic call */
2709 )
2710{
2712
2713 heurdata = SCIPheurGetData(heur);
2714 assert(heurdata != NULL);
2715 assert(scip != NULL);
2716 assert(selection >= 0);
2717 assert(selection < heurdata->nneighborhoods + heurdata->ndiving);
2718
2719 /* check if a diving or LNS heuristic was selected */
2720 if( selection < heurdata->ndiving )
2721 {
2723 }
2724 else
2725 {
2726 SCIP_CALL( executeLNSHeuristic(scip, heur, selection - heurdata->ndiving, runstats, subscipstatus, result) );
2727 }
2728
2729 return SCIP_OKAY;
2730}
2731
2732/** reinitialize bandit algorithm since the number of actions has changed */
2733static
2735 SCIP* scip, /**< SCIP data structure */
2736 SCIP_HEURDATA* heurdata, /**< heuristic data */
2737 int nactions /**< new number of actions */
2738 )
2739{
2740 SCIP_Real* priorities;
2741 int i;
2742 unsigned int initseed;
2743
2744 /* allocate memory for the priorities */
2745 SCIP_CALL( SCIPallocBufferArray(scip, &priorities, nactions) );
2746
2747 /* get the priorities */
2748 for( i = 0; i < heurdata->ndiving; ++i )
2749 priorities[i] = heurdata->divingheurs[i]->priority;
2750 for( i = 0; i < heurdata->nactiveneighborhoods; ++i )
2751 priorities[i + heurdata->ndiving] = heurdata->neighborhoods[i]->priority;
2752
2753 /* free bandit if necessary */
2754 if( heurdata->bandit != NULL )
2755 {
2756 SCIP_CALL( SCIPfreeBandit(scip, &heurdata->bandit) );
2757 heurdata->bandit = NULL;
2758 }
2759
2760 /* create bandit again */
2761 initseed = (unsigned int)(heurdata->seed + SCIPgetNVars(scip));
2762 SCIP_CALL( createBandit(scip, heurdata, priorities, initseed) );
2764
2765 /* free memory */
2766 SCIPfreeBufferArray(scip, &priorities);
2767
2768 return SCIP_OKAY;
2769}
2770
2771/** initializes everything that was missing because diving heuristics were not proccessed by SCIP yet. In particular,
2772 * the function adds diving heuristics to heurdata, heurdata->maxdivingnodelimit,
2773 * heurdata->maxlnsnodelimit and heurdata->sortedindices if heurdata->defaultroot is set to TRUE
2774 */
2775static
2777 SCIP* scip, /**< SCIP data structure */
2778 SCIP_HEUR* heur /**< scheduler heuristic */
2779 )
2780{
2782 SCIP_Real* priorities;
2783 int nheurs;
2784 int i;
2785
2786 /* get heuristic data */
2787 heurdata = SCIPheurGetData(heur);
2788
2789 /* include the diving heuristics */
2791
2792 /* get number of active heuristics we can choose from */
2793 nheurs = heurdata->ndiving + heurdata->nactiveneighborhoods;
2794
2795 /* we need to initialize the bandit method again since the number of actions has changed */
2796 SCIP_CALL( reinitBandit(scip, heurdata, nheurs) );
2797
2798 /* set maximum of all node and diving depth limit */
2799 heurdata->maxdivingnodelimit = heurdata->initdivingnodelimit;
2800 heurdata->maxlnsnodelimit = heurdata->initlnsnodelimit;
2801
2802 /* initialize nodelimit for all LNS heursitics */
2803 for( i = 0; i < heurdata->nactiveneighborhoods; ++i )
2804 heurdata->neighborhoods[i]->nodelimit = heurdata->initlnsnodelimit;
2805
2806 /* initialize indices array and sort according to heuristic's priorities if we want to execute heuristics in default order
2807 * at the root node*/
2808 if( heurdata->defaultroot )
2809 {
2810 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->sortedindices, heurdata->ndiving + heurdata->nneighborhoods) );
2811 SCIP_CALL( SCIPallocBufferArray(scip, &priorities, nheurs) );
2812 heurdata->counter = 0;
2813
2814 for( i = 0; i < nheurs; ++i )
2815 {
2816 heurdata->sortedindices[i] = i;
2817
2818 if( i < heurdata->ndiving )
2819 priorities[i] = (SCIP_Real)-heurdata->divingheurs[i]->rootnodepriority;
2820 else
2821 priorities[i] = (SCIP_Real)-heurdata->neighborhoods[i - heurdata->ndiving]->rootnodepriority;
2822 }
2823
2824 /* sort indices */
2825 SCIPsortRealInt(priorities, heurdata->sortedindices, nheurs);
2826
2827 SCIPfreeBufferArray(scip, &priorities);
2828 }
2829
2830 return SCIP_OKAY;
2831}
2832
2833/** execution method of primal heuristic */
2834static
2836{ /*lint --e{715}*/
2838 SCIP_Bool success;
2839
2840 assert(heur != NULL);
2841 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
2842 assert(scip != NULL);
2843 assert(result != NULL);
2844
2845 /* get heuristic data */
2846 heurdata = SCIPheurGetData(heur);
2847
2848 SCIPdebugMsg(scip, "Calling heurExecScheduler: depth %d sols %d inf %u node %lld \n",
2850
2851 /* store diving heuristics if not done already and reset stats */
2852 if( heurdata->divingheurs == NULL )
2853 {
2854 SCIP_CALL( initRest(scip, heur) );
2855 }
2856 assert( heurdata->divingheurs != NULL );
2857
2859
2860 /* do not call heuristic in node that was already detected to be infeasible */
2861 if( nodeinfeasible )
2862 return SCIP_OKAY;
2863
2864 /* only call heuristic, if an optimal LP solution is at hand */
2866 return SCIP_OKAY;
2867
2868 /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
2870 return SCIP_OKAY;
2871
2872 /* only call heuristic, if the LP solution is basic (which allows fast resolve in diving) */
2873 if( !SCIPisLPSolBasic(scip) )
2874 return SCIP_OKAY;
2875
2876 /* update internal incumbent solution */
2877 if( SCIPgetBestSol(scip) != heurdata->lastcallsol )
2878 {
2879 heurdata->lastcallsol = SCIPgetBestSol(scip);
2880 heurdata->firstcallthissol = SCIPheurGetNCalls(heur);
2881 }
2882
2883 /* do not run more than a user-defined number of times on each incumbent (-1: no limit) */
2884 if( heurdata->maxcallssamesol != -1 )
2885 {
2886 SCIP_Longint samesollimit;
2887
2888 /* either it is the user-defined limit or the number of heuristics controlled by the scheduler */
2889 samesollimit = (heurdata->maxcallssamesol > 0) ? heurdata->maxcallssamesol : (SCIP_Longint) heurdata->nneighborhoods + heurdata->ndiving;
2890
2891 if( SCIPheurGetNCalls(heur) - heurdata->firstcallthissol >= samesollimit )
2892 {
2893 SCIPdebugMsg(scip, "Heuristic already called %" SCIP_LONGINT_FORMAT " times on current incumbent\n", SCIPheurGetNCalls(heur) - heurdata->firstcallthissol);
2894 return SCIP_OKAY;
2895 }
2896 }
2897
2898 /* wait for a sufficient number of nodes since last incumbent solution */
2899 if( SCIPgetDepth(scip) > 0 && SCIPgetBestSol(scip) != NULL
2901 {
2902 SCIPdebugMsg(scip, "Waiting nodes not satisfied\n");
2903 return SCIP_OKAY;
2904 }
2905
2906 /* skip this call if scheduler was too unsuccessful in the past few calls */
2907 if( heurdata->nskippedcalls > 0 )
2908 {
2909 /* reduce counter because we need to skip one call less now */
2910 heurdata->nskippedcalls--;
2911
2912 return SCIP_OKAY;
2913 }
2914 else
2915 {
2916 /* check if we need to skip calls in the future */
2917 heurdata->nskippedcalls = (int) floor(exp(0.1 * (SCIP_Real) heurdata->nfailedcalls)) - 1;
2918 }
2919
2921 success = FALSE;
2922 {
2923 int selection;
2924 SCIP_Real reward;
2925 HEUR_STATS* stats;
2927
2929
2930 /* allocate memory for statistics and initialize it */
2931 SCIP_CALL( SCIPallocBuffer(scip, &stats) );
2932 initRunStats(scip, stats);
2933
2934 /* select the heuristic based on previous success. The heuristics are sorted such that
2935 * diving comes before LNS */
2937
2938 /* execute selected heuristic */
2940
2941 /* update global statistics */
2942 if( selection < heurdata->ndiving ) /* diving was selected */
2943 updateHeurStatsDiving(stats, heurdata->divingheurs[selection]);
2944 else /* LNS was selected */
2945 updateHeurStatsLNS(stats, heurdata->neighborhoods[selection - heurdata->ndiving], &subscipstatus);
2946
2947 /* observe reward */
2949
2950 /* call was successfull if solution was found */
2951 if( stats->nbestsolsfound > 0 )
2952 success = TRUE;
2953
2954 /* update either LP resolve freq or target fixing rate, depending on which heuristic was chosen */
2955 if( selection < heurdata->ndiving )
2956 {
2957 /* update resolve freq */
2958 updateSolveFreq(heurdata->divingheurs[selection], stats);
2959 }
2960 else
2961 {
2962 /* update target fixing rate */
2963 SCIPdebugMsg(scip, "Update fixing rate: %.2f\n", heurdata->neighborhoods[selection - heurdata->ndiving]->fixingrate.targetfixingrate);
2964 updateFixingRate(heurdata->neighborhoods[selection - heurdata->ndiving], subscipstatus, stats);
2965 SCIPdebugMsg(scip, "New fixing rate: %.2f\n", heurdata->neighborhoods[selection - heurdata->ndiving]->fixingrate.targetfixingrate);
2966 }
2967
2968 /* update selection strategy */
2970
2971 /* free statistics data struct */
2972 SCIPfreeBuffer(scip, &stats);
2973 }
2974
2975 /* count how many consecutive failed calls we had */
2976 if( success )
2977 heurdata->nfailedcalls = 0;
2978 else
2979 heurdata->nfailedcalls++;
2980
2981 return SCIP_OKAY;
2982}
2983
2984/** callback to collect variable fixings of RENS */
2985static
2987{ /*lint --e{715}*/
2988 int nbinvars;
2989 int nintvars;
2990 SCIP_VAR** vars;
2991 int i;
2992 int *fracidx = NULL;
2993 SCIP_Real* frac = NULL;
2994 int nfracs;
2995
2996 assert(scip != NULL);
2997 assert(varbuf != NULL);
2998 assert(nfixings != NULL);
2999 assert(valbuf != NULL);
3000
3002
3003 if( ! SCIPhasCurrentNodeLP(scip) )
3004 return SCIP_OKAY;
3006 return SCIP_OKAY;
3007
3009
3010 /* get variable information */
3012
3013 /* return if no binary or integer variables are present */
3014 if( nbinvars + nintvars == 0 )
3015 return SCIP_OKAY;
3016
3019
3020 /* loop over binary and integer variables; determine those that should be fixed in the sub-SCIP */
3021 for( nfracs = 0, i = 0; i < nbinvars + nintvars; ++i )
3022 {
3023 SCIP_VAR* var = vars[i];
3024 SCIP_Real lpsolval = SCIPvarGetLPSol(var);
3026
3027 /* fix all binary and integer variables with integer LP solution value */
3028 if( SCIPisFeasIntegral(scip, lpsolval) )
3029 {
3030 tryAdd2variableBuffer(scip, var, lpsolval, varbuf, valbuf, nfixings, TRUE);
3031 }
3032 else
3033 {
3034 frac[nfracs] = SCIPfrac(scip, lpsolval);
3035 frac[nfracs] = MIN(frac[nfracs], 1.0 - frac[nfracs]);
3036 fracidx[nfracs++] = i;
3037 }
3038 }
3039
3040 /* do some additional fixing */
3042 {
3044
3045 /* prefer variables that are almost integer */
3046 for( i = 0; i < nfracs && *nfixings < neighborhood->fixingrate.targetfixingrate * (nbinvars + nintvars); i++ )
3047 {
3049 }
3050 }
3051
3054
3056
3057 return SCIP_OKAY;
3058}
3059
3060/** callback for RENS subproblem changes */
3061static
3063{ /*lint --e{715}*/
3064 SCIP_VAR** vars;
3065 int nintvars;
3066 int nbinvars;
3067 int i;
3068
3069 assert(SCIPhasCurrentNodeLP(sourcescip));
3071
3072 /* get variable information */
3073 SCIP_CALL( SCIPgetVarsData(sourcescip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
3074
3075 /* restrict bounds of integer variables with fractional solution value */
3076 for( i = nbinvars; i < nbinvars + nintvars; ++i )
3077 {
3078 SCIP_VAR* var = vars[i];
3079 SCIP_Real lpsolval = SCIPgetSolVal(sourcescip, NULL, var);
3080
3081 if( subvars[i] == NULL )
3082 continue;
3083
3084 if( ! SCIPisFeasIntegral(sourcescip, lpsolval) )
3085 {
3086 SCIP_Real newlb = SCIPfloor(sourcescip, lpsolval);
3087 SCIP_Real newub = newlb + 1.0;
3088
3089 /* only count this as a domain change if the new lower and upper bound are a further restriction */
3090 if( newlb > SCIPvarGetLbGlobal(subvars[i]) + 0.5 || newub < SCIPvarGetUbGlobal(subvars[i]) - 0.5 )
3091 {
3094 (*ndomchgs)++;
3095 }
3096 }
3097 }
3098
3099 *success = TRUE;
3100
3101 return SCIP_OKAY;
3102}
3103
3104/** collect fixings by matching solution values in a collection of solutions for all binary and integer variables,
3105 * or for a custom set of variables
3106 */
3107static
3109 SCIP* scip, /**< SCIP data structure */
3110 SCIP_SOL** sols, /**< array of 2 or more solutions. It is okay for the array to contain one element
3111 * equal to NULL to represent the current LP solution */
3112 int nsols, /**< number of solutions in the array */
3113 SCIP_VAR** vars, /**< variable array for which solution values must agree */
3114 int nvars, /**< number of variables, or -1 for all binary and integer variables */
3115 SCIP_VAR** varbuf, /**< buffer storage for variable fixings */
3116 SCIP_Real* valbuf, /**< buffer storage for fixing values */
3117 int* nfixings /**< pointer to store the number of fixings */
3118 )
3119{
3120 int v;
3121 int nbinintvars;
3123
3124 assert(scip != NULL);
3125 assert(sols != NULL);
3126 assert(nsols >= 2);
3127 assert(varbuf != NULL);
3128 assert(valbuf != NULL);
3129 assert(nfixings != NULL);
3130 assert(*nfixings == 0);
3131
3132 if( nvars == -1 || vars == NULL )
3133 {
3134 int nbinvars;
3135 int nintvars;
3139 }
3140 firstsol = sols[0];
3141 assert(nvars > 0);
3142
3143 /* loop over integer and binary variables and check if their solution values match in all solutions */
3144 for( v = 0; v < nvars; ++v )
3145 {
3146 SCIP_Real solval;
3147 SCIP_VAR* var;
3148 int s;
3149
3150 var = vars[v];
3152 solval = SCIPgetSolVal(scip, firstsol, var);
3153
3154 /* determine if solution values match in all given solutions */
3155 for( s = 1; s < nsols; ++s )
3156 {
3157 SCIP_Real solval2 = SCIPgetSolVal(scip, sols[s], var);
3158 if( ! SCIPisEQ(scip, solval, solval2) )
3159 break;
3160 }
3161
3162 /* if we did not break early, all solutions agree on the solution value of this variable */
3163 if( s == nsols )
3164 {
3165 tryAdd2variableBuffer(scip, var, solval, varbuf, valbuf, nfixings, TRUE);
3166 }
3167 }
3168
3169 return SCIP_OKAY;
3170}
3171
3172/** callback to collect variable fixings of RINS */
3173static
3175{
3176 /*lint --e{715}*/
3177 int nbinvars;
3178 int nintvars;
3179 SCIP_VAR** vars;
3181 SCIP_SOL* sols[2];
3182 assert(scip != NULL);
3183 assert(varbuf != NULL);
3184 assert(nfixings != NULL);
3185 assert(valbuf != NULL);
3186
3188
3189 if( ! SCIPhasCurrentNodeLP(scip) )
3190 return SCIP_OKAY;
3192 return SCIP_OKAY;
3193
3195
3197 if( incumbent == NULL )
3198 return SCIP_OKAY;
3199
3201 return SCIP_OKAY;
3202
3203 /* get variable information */
3205
3206 /* return if no binary or integer variables are present */
3207 if( nbinvars + nintvars == 0 )
3208 return SCIP_OKAY;
3209
3210 sols[0] = NULL;
3211 sols[1] = incumbent;
3212
3214
3216
3217 return SCIP_OKAY;
3218}
3219
3220/** initialization callback for crossover when a new problem is read */
3221static
3223{ /*lint --e{715}*/
3224 DATA_CROSSOVER* data;
3225
3226 data = neighborhood->data.crossover;
3227 assert(data != NULL);
3228
3229 if( data->rng != NULL )
3230 SCIPfreeRandom(scip, &data->rng);
3231
3232 data->selsol = NULL;
3233
3234 SCIP_CALL( SCIPcreateRandom(scip, &data->rng, CROSSOVERSEED + (unsigned int)SCIPgetNVars(scip), TRUE) );
3235
3236 return SCIP_OKAY;
3237}
3238
3239/** deinitialization callback for crossover when exiting a problem */
3240static
3242{ /*lint --e{715}*/
3243 DATA_CROSSOVER* data;
3244 data = neighborhood->data.crossover;
3245
3247 assert(data->rng != NULL);
3248
3249 SCIPfreeRandom(scip, &data->rng);
3250
3251 return SCIP_OKAY;
3252}
3253
3254/** deinitialization callback for crossover before SCIP is freed */
3255static
3257{ /*lint --e{715}*/
3258 assert(neighborhood->data.crossover != NULL);
3259 SCIPfreeBlockMemory(scip, &neighborhood->data.crossover);
3260
3261 return SCIP_OKAY;
3262}
3263
3264/** callback to collect variable fixings of crossover */
3265static
3267{ /*lint --e{715}*/
3268 DATA_CROSSOVER* data;
3269 SCIP_RANDNUMGEN* rng;
3270 SCIP_SOL** sols;
3272 int nsols;
3273 int lastdraw;
3274 assert(scip != NULL);
3275 assert(varbuf != NULL);
3276 assert(nfixings != NULL);
3277 assert(valbuf != NULL);
3278
3279 data = neighborhood->data.crossover;
3280
3281 assert(data != NULL);
3282 nsols = data->nsols;
3283 data->selsol = NULL;
3284
3286
3287 /* return if the pool has not enough solutions */
3288 if( nsols > SCIPgetNSols(scip) )
3289 return SCIP_OKAY;
3290
3291 /* return if no binary or integer variables are present */
3293 return SCIP_OKAY;
3294
3295 rng = data->rng;
3297 SCIP_CALL( SCIPallocBufferArray(scip, &sols, nsols) );
3299
3300 /* draw as many solutions from the pool as required by crossover, biased towards
3301 * better solutions; therefore, the sorting of the solutions by objective is implicitly used
3302 */
3303 while( nsols > 0 )
3304 {
3305 /* no need for randomization anymore, exactly nsols many solutions remain for the selection */
3306 if( lastdraw == nsols )
3307 {
3308 int s;
3309
3310 /* fill the remaining slots 0,...,nsols - 1 by the solutions at the same places */
3311 for( s = 0; s < nsols; ++s )
3312 sols[s] = scipsols[s];
3313
3314 nsols = 0;
3315 }
3316 else
3317 {
3318 int nextdraw;
3319
3320 assert(nsols < lastdraw);
3321
3322 /* draw from the lastdraw - nsols many solutions nsols - 1, ... lastdraw - 1 such that nsols many solution */
3323 nextdraw = SCIPrandomGetInt(rng, nsols - 1, lastdraw - 1);
3324 assert(nextdraw >= 0);
3325
3326 sols[nsols - 1] = scipsols[nextdraw];
3327 nsols--;
3329 }
3330 }
3331
3332 SCIP_CALL( fixMatchingSolutionValues(scip, sols, data->nsols, NULL, -1, varbuf, valbuf, nfixings) );
3333
3334 /* store best selected solution as reference solution */
3335 data->selsol = sols[0];
3336 assert(data->selsol != NULL);
3337
3339
3340 SCIPfreeBufferArray(scip, &sols);
3341
3342 return SCIP_OKAY;
3343}
3344
3345/** callback for crossover reference solution */
3346static
3348{ /*lint --e{715}*/
3349 DATA_CROSSOVER* data;
3350
3351 data = neighborhood->data.crossover;
3352
3353 if( data->selsol != NULL )
3354 {
3355 *solptr = data->selsol;
3357 }
3358 else
3359 {
3361 }
3362
3363 return SCIP_OKAY;
3364}
3365
3366/** initialization callback for mutation when a new problem is read */
3367static
3369{ /*lint --e{715}*/
3370 DATA_MUTATION* data;
3371 assert(scip != NULL);
3373
3374 SCIP_CALL( SCIPallocBlockMemory(scip, &neighborhood->data.mutation) );
3375
3376 data = neighborhood->data.mutation;
3377 assert(data != NULL);
3378
3379 SCIP_CALL( SCIPcreateRandom(scip, &data->rng, MUTATIONSEED + (unsigned int)SCIPgetNVars(scip), TRUE) );
3380
3381 return SCIP_OKAY;
3382}
3383
3384/** deinitialization callback for mutation when exiting a problem */
3385static
3387{ /*lint --e{715}*/
3388 DATA_MUTATION* data;
3389 assert(scip != NULL);
3391 data = neighborhood->data.mutation;
3392 assert(data != NULL);
3393
3394 SCIPfreeRandom(scip, &data->rng);
3395
3396 SCIPfreeBlockMemory(scip, &neighborhood->data.mutation);
3397
3398 return SCIP_OKAY;
3399}
3400
3401/** callback to collect variable fixings of mutation */
3402static
3404{ /*lint --e{715}*/
3405 SCIP_RANDNUMGEN* rng;
3406
3407 SCIP_VAR** vars;
3408 SCIP_VAR** varscpy;
3409 int i;
3410 int nvars;
3411 int nbinvars;
3412 int nintvars;
3413 int nbinintvars;
3414 int ntargetfixings;
3416 SCIP_Real targetfixingrate;
3417
3418 assert(scip != NULL);
3420 assert(neighborhood->data.mutation != NULL);
3421 assert(neighborhood->data.mutation->rng != NULL);
3422 rng = neighborhood->data.mutation->rng;
3423
3425
3426 /* get the problem variables */
3428
3430 if( nbinintvars == 0 )
3431 return SCIP_OKAY;
3432
3434 if( incumbentsol == NULL )
3435 return SCIP_OKAY;
3436
3437 targetfixingrate = neighborhood->fixingrate.targetfixingrate;
3438 ntargetfixings = (int)(targetfixingrate * nbinintvars) + 1;
3439
3440 /* don't continue if number of discrete variables is too small to reach target fixing rate */
3442 return SCIP_OKAY;
3443
3445
3446 /* copy variables into a buffer array */
3448
3449 /* partially perturb the array until the number of target fixings is reached */
3450 for( i = 0; *nfixings < ntargetfixings && i < nbinintvars; ++i )
3451 {
3452 int randint = SCIPrandomGetInt(rng, i, nbinintvars - 1);
3454
3455 if( randint > i )
3456 {
3457 SCIPswapPointers((void**)&varscpy[i], (void**)&varscpy[randint]);
3458 }
3459 /* copy the selected variables and their solution values into the buffer */
3461 }
3462
3463 assert(i == nbinintvars || *nfixings == ntargetfixings);
3464
3465 /* Not reaching the number of target fixings means that there is a significant fraction (at least 1 - targetfixingrate)
3466 * of variables for which the incumbent solution value does not lie within the global bounds anymore. This is a nonsuccess
3467 * for the neighborhood (additional fixings are not possible), which is okay because the incumbent solution is
3468 * significantly outdated
3469 */
3470 if( *nfixings == ntargetfixings )
3472
3473 /* free the buffer array */
3475
3476 return SCIP_OKAY;
3477}
3478
3479/** add local branching constraint */
3480static
3482 SCIP* sourcescip, /**< source SCIP data structure */
3483 SCIP* targetscip, /**< target SCIP data structure */
3484 SCIP_VAR** subvars, /**< array of sub SCIP variables in same order as source SCIP variables */
3485 int distance, /**< right hand side of the local branching constraint */
3486 SCIP_Bool* success, /**< pointer to store of a local branching constraint has been successfully added */
3487 int* naddedconss /**< pointer to increase the number of added constraints */
3488 )
3489{
3490 int nbinvars;
3491 int i;
3494 SCIP_VAR** vars;
3495 SCIP_Real* consvals;
3496 SCIP_Real rhs;
3497
3498 assert(sourcescip != NULL);
3499 assert(*success == FALSE);
3500
3501 nbinvars = SCIPgetNBinVars(sourcescip);
3502 vars = SCIPgetVars(sourcescip);
3503
3504 if( nbinvars <= 3 )
3505 return SCIP_OKAY;
3506
3507 referencesol = SCIPgetBestSol(sourcescip);
3508 if( referencesol == NULL )
3509 return SCIP_OKAY;
3510
3511 rhs = (SCIP_Real)distance;
3512 rhs = MAX(rhs, 2.0);
3513
3515
3516 /* loop over binary variables and fill the local branching constraint */
3517 for( i = 0; i < nbinvars; ++i )
3518 {
3519 /* skip variables that are not present in sub-SCIP */
3520 if( subvars[i] == NULL )
3521 continue;
3522
3523 if( SCIPisEQ(sourcescip, SCIPgetSolVal(sourcescip, referencesol, vars[i]), 0.0) )
3524 consvals[i] = 1.0;
3525 else
3526 {
3527 consvals[i] = -1.0;
3528 rhs -= 1.0;
3529 }
3530 }
3531
3532 /* create the local branching constraint in the target scip */
3533 SCIP_CALL( SCIPcreateConsBasicLinear(targetscip, &localbranchcons, "localbranch", nbinvars, subvars, consvals, -SCIPinfinity(sourcescip), rhs) );
3536
3537 *naddedconss = 1;
3538 *success = TRUE;
3539
3540 SCIPfreeBufferArray(sourcescip, &consvals);
3541
3542 return SCIP_OKAY;
3543}
3544
3545/** callback for local branching subproblem changes */
3546static
3548{ /*lint --e{715}*/
3549
3550 SCIP_CALL( addLocalBranchingConstraint(sourcescip, targetscip, subvars, (int)(0.2 * SCIPgetNBinVars(sourcescip)), success, naddedconss) );
3551
3552 return SCIP_OKAY;
3553}
3554
3555/** callback for proximity subproblem changes */
3556static
3558{ /*lint --e{715}*/
3560 SCIP_VAR** vars;
3561 int nbinvars;
3562 int nintvars;
3563 int nvars;
3564 int i;
3565
3566 SCIP_CALL( SCIPgetVarsData(sourcescip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
3567
3568 if( nbinvars == 0 )
3569 return SCIP_OKAY;
3570
3571 referencesol = SCIPgetBestSol(sourcescip);
3572 if( referencesol == NULL )
3573 return SCIP_OKAY;
3574
3575 /* loop over binary variables, set objective coefficients based on reference solution in a local branching fashion */
3576 for( i = 0; i < nbinvars; ++i )
3577 {
3578 SCIP_Real newobj;
3579
3580 /* skip variables not present in sub-SCIP */
3581 if( subvars[i] == NULL )
3582 continue;
3583
3584 if( SCIPgetSolVal(sourcescip, referencesol, vars[i]) < 0.5 )
3585 newobj = -1.0;
3586 else
3587 newobj = 1.0;
3588 SCIP_CALL( SCIPchgVarObj(targetscip, subvars[i], newobj) );
3589 }
3590
3591 /* loop over the remaining variables and change their objective coefficients to 0 */
3592 for( ; i < nvars; ++i )
3593 {
3594 /* skip variables not present in sub-SCIP */
3595 if( subvars[i] == NULL )
3596 continue;
3597
3598 SCIP_CALL( SCIPchgVarObj(targetscip, subvars[i], 0.0) );
3599 }
3600
3601 *nchgobjs = nvars;
3602 *success = TRUE;
3603
3604 return SCIP_OKAY;
3605}
3606
3607/** callback for zeroobjective subproblem changes */
3608static
3610{ /*lint --e{715}*/
3612 SCIP_VAR** vars;
3613 int nvars;
3614 int i;
3615
3616 assert(*success == FALSE);
3617
3618 SCIP_CALL( SCIPgetVarsData(sourcescip, &vars, &nvars, NULL, NULL, NULL, NULL) );
3619
3620 /* do not run if no objective variables are present */
3621 if( SCIPgetNObjVars(sourcescip) == 0 )
3622 return SCIP_OKAY;
3623
3624 /* zeroobj may trigger fixing objvar in nonlinear constraint to infinity,
3625 * which expr_var.c:simplify cannot handle at the moment; also #3273
3626 */
3627 conshdlrnl = SCIPfindConshdlr(sourcescip, "nonlinear");
3629 return SCIP_OKAY;
3630
3631 /* loop over the variables and change their objective coefficients to 0 */
3632 for( i = 0; i < nvars; ++i )
3633 {
3634 /* skip variables not present in sub-SCIP */
3635 if( subvars[i] == NULL )
3636 continue;
3637
3638 SCIP_CALL( SCIPchgVarObj(targetscip, subvars[i], 0.0) );
3639 }
3640
3641 *nchgobjs = nvars;
3642 *success = TRUE;
3643
3644 return SCIP_OKAY;
3645}
3646
3647/** compute tightened bounds for integer variables depending on how much the LP and the incumbent solution values differ */
3648static
3650 SCIP* scip, /**< SCIP data structure of the original problem */
3651 SCIP_VAR* var, /**< the variable for which bounds should be computed */
3652 SCIP_Real* lbptr, /**< pointer to store the lower bound in the DINS sub-SCIP */
3653 SCIP_Real* ubptr /**< pointer to store the upper bound in the DINS sub-SCIP */
3654 )
3655{
3656 SCIP_Real mipsol;
3657 SCIP_Real lpsol;
3658
3659 SCIP_Real lbglobal;
3660 SCIP_Real ubglobal;
3661 SCIP_SOL* bestsol;
3662
3663 /* get the bounds for each variable */
3666
3668 /* get the current LP solution for each variable */
3670
3671 /* get the current MIP solution for each variable */
3672 bestsol = SCIPgetBestSol(scip);
3673 mipsol = SCIPgetSolVal(scip, bestsol, var);
3674
3675 /* if the solution values differ by 0.5 or more, the variable is rebounded, otherwise it is just copied */
3676 if( REALABS(lpsol - mipsol) >= 0.5 )
3677 {
3678 SCIP_Real range;
3679
3680 *lbptr = lbglobal;
3681 *ubptr = ubglobal;
3682
3683 /* create an equally sized range around lpsol for general integers: bounds are lpsol +- (mipsol-lpsol) */
3684 range = 2 * lpsol - mipsol;
3685
3686 if( mipsol >= lpsol )
3687 {
3689 *lbptr = MAX(*lbptr, range);
3690
3691 /* when the bound new upper bound is equal to the current MIP solution, we set both bounds to the integral bound (without eps) */
3692 if( SCIPisFeasEQ(scip, mipsol, *lbptr) )
3693 *ubptr = *lbptr;
3694 else
3695 *ubptr = mipsol;
3696 }
3697 else
3698 {
3700 *ubptr = MIN(*ubptr, range);
3701
3702 /* when the bound new upper bound is equal to the current MIP solution, we set both bounds to the integral bound (without eps) */
3703 if( SCIPisFeasEQ(scip, mipsol, *ubptr) )
3704 *lbptr = *ubptr;
3705 else
3706 *lbptr = mipsol;
3707 }
3708
3709 /* the global domain of variables might have been reduced since incumbent was found: adjust lb and ub accordingly */
3710 *lbptr = MAX(*lbptr, lbglobal);
3711 *ubptr = MIN(*ubptr, ubglobal);
3712 }
3713 else
3714 {
3715 /* the global domain of variables might have been reduced since incumbent was found: adjust it accordingly */
3716 *lbptr = MAX(mipsol, lbglobal);
3717 *ubptr = MIN(mipsol, ubglobal);
3718 }
3719}
3720
3721/** callback to collect variable fixings of DINS */
3722static
3724{
3725 DATA_DINS* data;
3727 SCIP_SOL** sols;
3728 int nsols;
3729 int nmipsols;
3730 int nbinvars;
3731 int nintvars;
3732 SCIP_VAR** vars;
3733 int v;
3734
3735 data = neighborhood->data.dins;
3736 assert(data != NULL);
3738 nmipsols = MIN(nmipsols, data->npoolsols);
3739
3741
3743 return SCIP_OKAY;
3744
3746
3747 if( nmipsols == 0 )
3748 return SCIP_OKAY;
3749
3751
3752 if( nbinvars + nintvars == 0 )
3753 return SCIP_OKAY;
3754
3756
3757 /* save root solution LP values in solution */
3758 for( v = 0; v < nbinvars + nintvars; ++v )
3759 {
3761 }
3762
3763 /* add the node and the root LP solution */
3764 nsols = nmipsols + 2;
3765
3766 SCIP_CALL( SCIPallocBufferArray(scip, &sols, nsols) );
3767 sols[0] = NULL; /* node LP solution */
3768 sols[1] = rootlpsol;
3769
3770 /* copy the remaining MIP solutions after the LP solutions */
3771 BMScopyMemoryArray(&sols[2], SCIPgetSols(scip), nmipsols); /*lint !e866*/
3772
3773 /* 1. Binary variables are fixed if their values agree in all the solutions */
3774 if( nbinvars > 0 )
3775 {
3776 SCIP_CALL( fixMatchingSolutionValues(scip, sols, nsols, vars, nbinvars, varbuf, valbuf, nfixings) );
3777 }
3778
3779 /* 2. Integer variables are fixed if they have a very low distance between the incumbent and the root LP solution */
3780 for( v = nbinvars; v < nintvars; ++v )
3781 {
3782 SCIP_Real lb;
3783 SCIP_Real ub;
3785
3786 if( ub - lb < 0.5 )
3787 {
3789 tryAdd2variableBuffer(scip, vars[v], lb, varbuf, valbuf, nfixings, TRUE);
3790 }
3791 }
3792
3794
3795 SCIPfreeBufferArray(scip, &sols);
3796
3798
3799 return SCIP_OKAY;
3800}
3801
3802/** callback for DINS subproblem changes */
3803static
3805{ /*lint --e{715}*/
3806 SCIP_VAR** vars;
3807 int nintvars;
3808 int nbinvars;
3809 int v;
3810
3811 SCIP_CALL( SCIPgetVarsData(sourcescip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
3812
3813 /* 1. loop over integer variables and tighten the bounds */
3814 for( v = nbinvars; v < nintvars; ++v )
3815 {
3816 SCIP_Real lb;
3817 SCIP_Real ub;
3818
3819 /* skip variables not present in sub-SCIP */
3820 if( subvars[v] == NULL )
3821 continue;
3822
3823 computeIntegerVariableBoundsDins(sourcescip, vars[v], &lb, &ub);
3824
3825 SCIP_CALL( SCIPchgVarLbGlobal(targetscip, subvars[v], lb) );
3826 SCIP_CALL( SCIPchgVarUbGlobal(targetscip, subvars[v], ub) );
3827 ++(*ndomchgs);
3828 }
3829
3830 /* 2. add local branching constraint for binary variables */
3831 SCIP_CALL( addLocalBranchingConstraint(sourcescip, targetscip, subvars, (int)(0.1 * SCIPgetNBinVars(sourcescip)), success, naddedconss) );
3832
3833 *success = TRUE;
3834
3835 return SCIP_OKAY;
3836}
3837
3838/** deinitialization callback for DINS before SCIP is freed */
3839static
3841{
3842 assert(neighborhood->data.dins != NULL);
3843
3845
3846 return SCIP_OKAY;
3847}
3848
3849/** deinitialization callback for trustregion before SCIP is freed */
3850static
3852{
3853 assert(neighborhood->data.trustregion != NULL);
3854
3855 SCIPfreeBlockMemory(scip, &neighborhood->data.trustregion);
3856
3857 return SCIP_OKAY;
3858}
3859
3860/** add trust region neighborhood constraint and auxiliary objective variable */
3861static
3863{ /*lint --e{715}*/
3864 DATA_TRUSTREGION* data;
3865
3866 data = neighborhood->data.trustregion;
3867
3868 /* adding the neighborhood constraint for the trust region heuristic */
3870
3871 /* incrementing the change in objective since an additional variable is added to the objective to penalize the
3872 * violation of the trust region.
3873 */
3874 ++(*nchgobjs);
3875
3876 return SCIP_OKAY;
3877}
3878
3879/** callback that returns the incumbent solution as a reference point */
3880static
3882{ /*lint --e{715}*/
3883 assert(scip != NULL);
3884
3885 if( SCIPgetBestSol(scip) != NULL )
3886 {
3889 }
3890 else
3891 {
3893 }
3894
3895 return SCIP_OKAY;
3896}
3897
3898
3899/** callback function that deactivates a neighborhood on problems with no discrete variables */
3900static
3902{ /*lint --e{715}*/
3903 assert(scip != NULL);
3905
3906 /* deactivate if no discrete variables are present */
3908
3909 return SCIP_OKAY;
3910}
3911
3912/** callback function that deactivates a neighborhood on problems with no binary variables */
3913static
3915{ /*lint --e{715}*/
3916 assert(scip != NULL);
3918
3919 /* deactivate if no discrete variables are present */
3920 *deactivate = (SCIPgetNBinVars(scip) == 0);
3921
3922 return SCIP_OKAY;
3923}
3924
3925/** callback function that deactivates a neighborhood on problems with no objective variables */
3926static
3928{ /*lint --e{715}*/
3929 assert(scip != NULL);
3931
3932 /* deactivate if no discrete variables are present */
3933 *deactivate = (SCIPgetNObjVars(scip) == 0);
3934
3935 return SCIP_OKAY;
3936}
3937
3938
3939/** include all neighborhoods */
3940static
3942 SCIP* scip, /**< SCIP data structure */
3943 SCIP_HEURDATA* heurdata /**< heuristic data of the scheduler heuristic */
3944 )
3945{
3946 NH* rens;
3947 NH* rins;
3948 NH* mutation;
3950 NH* crossover;
3951 NH* proximity;
3953 NH* dins;
3954 NH* trustregion;
3955
3956 heurdata->nneighborhoods = 0;
3957
3958 /* include the RENS neighborhood */
3962
3963 /* include the RINS neighborhood */
3967
3968 /* include the mutation neighborhood */
3969 SCIP_CALL( schedulerIncludeNeighborhood(scip, heurdata, &mutation, "mutation",
3972
3973 /* include the local branching neighborhood */
3977
3978 /* include the crossover neighborhood */
3979 SCIP_CALL( schedulerIncludeNeighborhood(scip, heurdata, &crossover, "crossover",
3983
3984 /* allocate data for crossover to include the parameter */
3986 crossover->data.crossover->rng = NULL;
3987
3988 /* add crossover neighborhood parameters */
3989 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/scheduler/crossover/nsols", "the number of solutions that crossover should combine",
3990 &crossover->data.crossover->nsols, TRUE, DEFAULT_NSOLS_CROSSOVER, 2, 10, NULL, NULL) );
3991
3992 /* include the Proximity neighborhood */
3996
3997 /* include the Zeroobjective neighborhood */
4001
4002 /* include the DINS neighborhood */
4006
4007 /* allocate data for DINS to include the parameter */
4009
4010 /* add DINS neighborhood parameters */
4011 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/scheduler/dins/npoolsols",
4012 "number of pool solutions where binary solution values must agree",
4013 &dins->data.dins->npoolsols, TRUE, DEFAULT_NPOOLSOLS_DINS, 1, 100, NULL, NULL) );
4014
4015 /* include the trustregion neighborhood */
4016 SCIP_CALL( schedulerIncludeNeighborhood(scip, heurdata, &trustregion, "trustregion",
4019
4020 /* allocate data for trustregion to include the parameter */
4022
4023 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/trustregion/violpenalty",
4024 "the penalty for each change in the binary variables from the candidate solution",
4026
4027 return SCIP_OKAY;
4028}
4029
4030/** initialization method of primal heuristic (called after problem was transformed) */
4031static
4033{ /*lint --e{715}*/
4035 int i;
4036
4037 assert(scip != NULL);
4038 assert(heur != NULL);
4039
4040 heurdata = SCIPheurGetData(heur);
4041 assert(heurdata != NULL);
4042
4043 /* reactivate all neighborhoods if a new problem is read in */
4044 heurdata->nactiveneighborhoods = heurdata->nneighborhoods;
4045
4046 /* initialize neighborhoods for new problem */
4047 for( i = 0; i < heurdata->nneighborhoods; ++i )
4048 {
4049 NH* neighborhood = heurdata->neighborhoods[i];
4050
4052
4053 SCIP_CALL( resetFixingRate(scip, &neighborhood->fixingrate) );
4054
4056 }
4057
4058 /* we clear the list of collected diving heuristics to ensure reproducability and consistent state across multiple runs
4059 * within the same SCIP data structure */
4060 /* note: diving heuristics data will be initialized when executing scheduler */
4061 if( heurdata->divingheurs != NULL )
4062 {
4063 SCIPfreeBlockMemoryArray(scip, &heurdata->divingheurs, heurdata->divingheurssize);
4064 assert(heurdata->divingheurs == NULL);
4065 }
4066
4067 /* create working solution */
4068 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
4069
4070 return SCIP_OKAY;
4071}
4072
4073
4074/** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
4075static
4077{ /*lint --e{715}*/
4079 int i;
4080 SCIP_Real* priorities;
4081 unsigned int initseed;
4082
4083 assert(scip != NULL);
4084 assert(heur != NULL);
4085
4086 heurdata = SCIPheurGetData(heur);
4087 assert(heurdata != NULL);
4088 heurdata->nactiveneighborhoods = heurdata->nneighborhoods;
4089
4090 SCIP_CALL( SCIPallocBufferArray(scip, &priorities, heurdata->ndiving + heurdata->nactiveneighborhoods) );
4091
4092 /* init neighborhoods for new problem by resetting their statistics and fixing rate */
4093 for( i = heurdata->nneighborhoods - 1; i >= 0; --i )
4094 {
4095 NH* neighborhood = heurdata->neighborhoods[i];
4096 SCIP_Bool deactivate;
4097
4098 SCIP_CALL( neighborhood->nhdeactivate(scip, &deactivate) );
4099
4100 /* disable inactive neighborhoods */
4101 if( deactivate || ! neighborhood->active )
4102 {
4103 if( heurdata->nactiveneighborhoods - 1 > i )
4104 {
4105 assert(heurdata->neighborhoods[heurdata->nactiveneighborhoods - 1]->active);
4106 SCIPswapPointers((void **)&heurdata->neighborhoods[i], (void **)&heurdata->neighborhoods[heurdata->nactiveneighborhoods - 1]);
4107 }
4108 heurdata->nactiveneighborhoods--;
4109 }
4110 }
4111
4112 /* if diving is already initialized (only happens after all diving heuristics are initialized),
4113 * take the proper priorities. Otherwise, set all priorities to 1.0 */
4114 if( heurdata->divingheurs != NULL )
4115 {
4116 /* collect diving heuristic priorities */
4117 for( i = 0; i < heurdata->ndiving; ++i )
4118 priorities[i] = heurdata->divingheurs[i]->priority;
4119
4120 /* collect neighborhood priorities */
4121 for( i = 0; i < heurdata->nactiveneighborhoods; ++i )
4122 priorities[i + heurdata->ndiving] = heurdata->neighborhoods[i]->priority;
4123 }
4124 else
4125 {
4126 for( i = 0; i < heurdata->ndiving + heurdata->nactiveneighborhoods; ++i )
4127 priorities[i] = 1.0;
4128 }
4129
4130 initseed = (unsigned int)(heurdata->seed + SCIPgetNVars(scip));
4131
4132 /* active neighborhoods might change between init calls, reset functionality must take this into account */
4133 if( heurdata->bandit != NULL && SCIPbanditGetNActions(heurdata->bandit) != heurdata->ndiving + heurdata->nactiveneighborhoods )
4134 {
4135 SCIP_CALL( SCIPfreeBandit(scip, &heurdata->bandit) );
4136 heurdata->bandit = NULL;
4137
4138 /* since the number of active heursitics has changed, we have to update
4139 * how heuristics are sorted by priority, if we already initialized the data */
4140 if( heurdata->divingheurs != NULL )
4141 {
4142 SCIP_Real* initpriorities;
4143 int nheurs;
4144
4145 nheurs = heurdata->nactiveneighborhoods + heurdata->ndiving;
4147 heurdata->counter = 0;
4148
4149 for( i = 0; i < nheurs; ++i )
4150 {
4151 heurdata->sortedindices[i] = i;
4152
4153 if( i < heurdata->ndiving )
4154 initpriorities[i] = (SCIP_Real)-heurdata->divingheurs[i]->rootnodepriority;
4155 else
4156 initpriorities[i] = (SCIP_Real)-heurdata->neighborhoods[i - heurdata->ndiving]->rootnodepriority;
4157 }
4158
4159 SCIPsortRealInt(initpriorities, heurdata->sortedindices, nheurs);
4160
4162 }
4163 }
4164
4165 if( heurdata->nactiveneighborhoods + heurdata->ndiving > 0 )
4166 { /* create or reset bandit algorithm */
4167 if( heurdata->bandit == NULL )
4168 {
4169 SCIP_CALL( createBandit(scip, heurdata, priorities, initseed) );
4171 }
4172 else if( heurdata->resetweights )
4173 {
4174 SCIP_CALL( SCIPresetBandit(scip, heurdata->bandit, priorities, initseed) );
4176 }
4177 }
4178
4179 /* TODO: maybe do something for diving as well here? */
4180 heurdata->usednodes = 0;
4181 heurdata->ninitneighborhoods = heurdata->nactiveneighborhoods;
4182
4183 heurdata->lastcallsol = NULL;
4184 heurdata->firstcallthissol = 0;
4185
4187
4188 SCIPfreeBufferArray(scip, &priorities);
4189
4190 return SCIP_OKAY;
4191}
4192
4193
4194/** deinitialization method of primal heuristic (called before transformed problem is freed) */
4195static
4197{ /*lint --e{715}*/
4199 int i;
4200
4201 assert(scip != NULL);
4202 assert(heur != NULL);
4203
4204 heurdata = SCIPheurGetData(heur);
4205 assert(heurdata != NULL);
4206
4207 /* free neighborhood specific data */
4208 for( i = 0; i < heurdata->nneighborhoods; ++i )
4209 {
4210 NH* neighborhood = heurdata->neighborhoods[i];
4211
4213 }
4214
4215 /* free working solution */
4217
4218 return SCIP_OKAY;
4219}
4220
4221/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
4222static
4224{ /*lint --e{715}*/
4226 int i;
4227
4228 assert(scip != NULL);
4229 assert(heur != NULL);
4230
4231 heurdata = SCIPheurGetData(heur);
4232 assert(heurdata != NULL);
4233
4234 /* bandits are only initialized if a problem has been read */
4235 if( heurdata->bandit != NULL )
4236 {
4237 SCIP_CALL( SCIPfreeBandit(scip, &heurdata->bandit) );
4238 }
4239
4240 /* free diving heuristics */
4241 if( heurdata->divingheurs != NULL )
4242 {
4243 int j;
4244
4245 for( j = 0; j < heurdata->ndiving; ++j )
4246 {
4247 SCIP_CALL( schedulerFreeDivingHeur(scip, &(heurdata->divingheurs[j])) );
4248 }
4249
4250 SCIPfreeBlockMemoryArray(scip, &heurdata->divingheurs, heurdata->divingheurssize);
4251
4252 if( heurdata->defaultroot )
4253 SCIPfreeBlockMemoryArray(scip, &heurdata->sortedindices, heurdata->ndiving + heurdata->nneighborhoods);
4254 }
4255
4256 /* free neighborhoods */
4257 for( i = 0; i < heurdata->nneighborhoods; ++i )
4258 {
4259 SCIP_CALL( schedulerFreeNeighborhood(scip, &(heurdata->neighborhoods[i])) );
4260 }
4261
4263
4265
4266 return SCIP_OKAY;
4267}
4268
4269/** output method of statistics table to output file stream 'file' */
4270static
4272{ /*lint --e{715}*/
4274
4277 assert(heurdata != NULL);
4278
4279 /* print neighborhood statistics */
4281
4282 /* print only diving statistics if scheduler got executed at least once (because we only then
4283 * initialize the diving heuristics)
4284 * Note: More Diving statistics will be printed in scip_solvingstats.c with all other stats about
4285 * diving since adaptive diving and the scheudler use the same diving context
4286 */
4287 if( heurdata->divingheurs != NULL )
4289
4290 return SCIP_OKAY;
4291}
4292
4293/*
4294 * primal heuristic specific interface methods
4295 */
4296
4297/** creates the scheduler primal heuristic and includes it in SCIP */
4299 SCIP* scip /**< SCIP data structure */
4300 )
4301{
4303 SCIP_HEUR* heur;
4304
4305 /* create primal heuristic data */
4306 heurdata = NULL;
4307 heur = NULL;
4308
4311
4312 /* TODO make this a user parameter? */
4313 heurdata->lplimfac = LPLIMFAC;
4314
4315 heurdata->nskippedcalls = 0;
4316 heurdata->nfailedcalls = 0;
4317 heurdata->maxnconflicts = 0;
4318
4319 /* allocate memory for LNS heuristics */
4321
4322 /* include primal heuristic */
4326
4327 assert(heur != NULL);
4328
4329 /* include all neighborhoods */
4330 /* note: diving heuristics will be included when executing the scheduler heuristic for
4331 * the first time, because it relies on all heuristics being already added to SCIP
4332 */
4334
4335 /* set non fundamental callbacks via setter functions */
4341
4342 /* add scheduler primal heuristic parameters */
4343 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
4344 "maximum number of nodes to regard in the subproblem",
4346
4347 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
4348 "offset added to the nodes budget",
4350
4351 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
4352 "minimum number of nodes required to start a sub-SCIP",
4354
4355 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/waitingnodes",
4356 "number of nodes since last incumbent solution that the heuristic should wait",
4358
4359 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/initlnsnodelimit",
4360 "initial node limit for LNS heuristics",
4361 &heurdata->initlnsnodelimit, TRUE, DEFAULT_INITLNSNODELIMIT, 0, INT_MAX, NULL, NULL) );
4362
4363 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/initdivingnodelimit",
4364 "initial node limit for diving heuristics",
4365 &heurdata->initdivingnodelimit, TRUE, DEFAULT_INITDIVINGNODELIMIT, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
4366
4367 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
4368 "fraction of nodes compared to the main SCIP for budget computation",
4369 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
4370
4371 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquotmin",
4372 "lower bound fraction of nodes compared to the main SCIP for budget computation",
4373 &heurdata->nodesquotmin, FALSE, DEFAULT_NODESQUOTMIN, 0.0, 1.0, NULL, NULL) );
4374
4375 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nsolslim",
4376 "limit on the number of improving solutions in a sub-SCIP call",
4377 &heurdata->nsolslim, FALSE, DEFAULT_NSOLSLIM, -1, INT_MAX, NULL, NULL) );
4378
4379 SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/banditalgo",
4380 "the bandit algorithm: (u)pper confidence bounds, (e)xp.3, epsilon (g)reedy, exp.3-(i)x",
4381 &heurdata->banditalgo, TRUE, DEFAULT_BANDITALGO, "uegi", NULL, NULL) );
4382
4383 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/gamma",
4384 "weight between uniform (gamma ~ 1) and weight driven (gamma ~ 0) probability distribution for exp3",
4385 &heurdata->exp3_gamma, TRUE, DEFAULT_GAMMA, 0.0, 1.0, NULL, NULL) );
4386
4387 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/beta",
4388 "reward offset between 0 and 1 at every observation for Exp.3",
4389 &heurdata->exp3_beta, TRUE, DEFAULT_BETA, 0.0, 1.0, NULL, NULL) );
4390
4391 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/alpha",
4392 "parameter to increase the confidence width in UCB",
4393 &heurdata->ucb_alpha, TRUE, DEFAULT_ALPHA, 0.0, 100.0, NULL, NULL) );
4394
4395 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usedistances",
4396 "distances from fixed variables be used for variable prioritization",
4397 &heurdata->usedistances, TRUE, DEFAULT_USEDISTANCES, NULL, NULL) );
4398
4399 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useredcost",
4400 "should reduced cost scores be used for variable prioritization?",
4401 &heurdata->useredcost, TRUE, DEFAULT_USEREDCOST, NULL, NULL) );
4402
4403 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usepscost",
4404 "should pseudo cost scores be used for variable priorization?",
4405 &heurdata->usepscost, TRUE, DEFAULT_USEPSCOST, NULL, NULL) );
4406
4407 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselocalredcost",
4408 "should local reduced costs be used for generic (un)fixing?",
4409 &heurdata->uselocalredcost, TRUE, DEFAULT_USELOCALREDCOST, NULL, NULL) );
4410
4411 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usesubscipheurs",
4412 "should the heuristic activate other sub-SCIP heuristics during its search?",
4413 &heurdata->usesubscipheurs, TRUE, DEFAULT_USESUBSCIPHEURS, NULL, NULL) );
4414
4415 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/targetnodefactor",
4416 "factor by which target node number is eventually increased",
4417 &heurdata->targetnodefactor, TRUE, DEFAULT_TARGETNODEFACTOR, 1.0, 1e+5, NULL, NULL) );
4418
4419 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/seed",
4420 "initial random seed for bandit algorithms and random decisions by neighborhoods",
4421 &heurdata->seed, FALSE, DEFAULT_SEED, 0, INT_MAX, NULL, NULL) );
4422
4423 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxcallssamesol",
4424 "number of allowed executions of the heuristic on the same incumbent solution (-1: no limit, 0: number of active neighborhoods)",
4425 &heurdata->maxcallssamesol, TRUE, DEFAULT_MAXCALLSSAMESOL, -1, 100, NULL, NULL) );
4426
4427 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/eps",
4428 "increase exploration in epsilon-greedy bandit algorithm",
4429 &heurdata->epsgreedy_eps, TRUE, DEFAULT_EPS, 0.0, 1.0, NULL, NULL) );
4430
4431 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/epsgreedy_usemod",
4432 "TRUE if modified version of the epsilon-greedy bandit algorithm should be used",
4433 &heurdata->epsgreedy_usemod, TRUE, TRUE, NULL, NULL) );
4434
4435 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/solrewardweight",
4436 "weight by how much finding a new incumbent is rewarded in reward function",
4437 &heurdata->solrewardweight, TRUE, DEFAULT_SOLREWARDWEIGHT, 0.0, 1.0, NULL, NULL) );
4438
4439 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/effortrewardweight",
4440 "weight by how much effort is rewarded in reward function",
4441 &heurdata->effortrewardweight, TRUE, DEFAULT_EFFORTREWARDWEIGHT, 0.0, 1.0, NULL, NULL) );
4442
4443 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/qualrewardweight",
4444 "weight by how much quality of a new incumbent is rewarded in reward function",
4445 &heurdata->qualrewardweight, TRUE, DEFAULT_QUALREWARDWEIGHT, 0.0, 1.0, NULL, NULL) );
4446
4447 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/conflictrewardweight",
4448 "weight by how much number of conflicts found by diving is rewarded in reward function",
4449 &heurdata->conflictrewardweight, TRUE, DEFAULT_CONFLICTREWARDWEIGHT, 0.0, 1.0, NULL, NULL) );
4450
4451 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/resetweights",
4452 "should the bandit algorithms be reset when a new problem is read?",
4453 &heurdata->resetweights, TRUE, DEFAULT_RESETWEIGHTS, NULL, NULL) );
4454
4455 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/subsciprandseeds",
4456 "should random seeds of sub-SCIPs be altered to increase diversification?",
4457 &heurdata->subsciprandseeds, TRUE, DEFAULT_SUBSCIPRANDSEEDS, NULL, NULL) );
4458
4459 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
4460 "should cutting planes be copied to the sub-SCIP?",
4461 &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
4462
4463 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/fixtol",
4464 "tolerance by which the fixing rate may be missed without generic fixing",
4465 &heurdata->fixtol, TRUE, DEFAULT_FIXTOL, 0.0, 1.0, NULL, NULL) );
4466
4467 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/unfixtol",
4468 "tolerance by which the fixing rate may be exceeded without generic unfixing",
4469 &heurdata->unfixtol, TRUE, DEFAULT_UNFIXTOL, 0.0, 1.0, NULL, NULL) );
4470
4471 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/heurtimelimit",
4472 "time limit for a single heuristic run",
4473 &heurdata->heurtimelimit, TRUE, DEFAULT_HEURTIMELIMIT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
4474
4475 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/initduringroot",
4476 "should the heuristic be executed multiple times during the root node?",
4477 &heurdata->initduringroot, TRUE, DEFAULT_INITDURINGROOT, NULL, NULL) );
4478
4479 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/defaultroot",
4480 "should the default priorities be used at the root node?",
4481 &heurdata->defaultroot, TRUE, TRUE, NULL, NULL) );
4482
4483 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nselections",
4484 "number of heuristics picked by the scheduler in one call (-1: number of controlled heuristics, 0: until new incumbent is found)",
4485 &heurdata->nselections, TRUE, DEFAULT_NSELECTIONS, -1, 100, NULL, NULL) );
4486
4491
4492 return SCIP_OKAY;
4493}
static GRAPHNODE ** active
SCIP_VAR * h
SCIP_VAR ** b
Constraint handler for linear constraints in their most general form, .
#define NULL
Definition def.h:267
#define SCIP_MAXSTRLEN
Definition def.h:288
#define SCIP_Longint
Definition def.h:158
#define SCIP_REAL_MAX
Definition def.h:174
#define MIN(x, y)
Definition def.h:243
#define SCIP_ALLOC(x)
Definition def.h:385
#define SCIP_Real
Definition def.h:173
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define MAX(x, y)
Definition def.h:239
#define SCIP_CALL_ABORT(x)
Definition def.h:353
#define SCIP_LONGINT_FORMAT
Definition def.h:165
#define SCIPABORT()
Definition def.h:346
#define REALABS(x)
Definition def.h:197
#define SCIP_LONGINT_MAX
Definition def.h:159
#define SCIP_CALL(x)
Definition def.h:374
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPtranslateSubSol(SCIP *scip, SCIP *subscip, SCIP_SOL *subsol, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_SOL **newsol)
Definition scip_copy.c:1408
SCIP_Bool SCIPisTransformed(SCIP *scip)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
int SCIPgetNObjVars(SCIP *scip)
Definition scip_prob.c:2220
int SCIPgetNIntVars(SCIP *scip)
Definition scip_prob.c:2082
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition scip_prob.c:1422
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition scip_prob.c:1866
int SCIPgetNVars(SCIP *scip)
Definition scip_prob.c:1992
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:2770
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition scip_prob.c:1947
int SCIPgetNBinVars(SCIP *scip)
Definition scip_prob.c:2037
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition misc.c:3108
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3261
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition misc.c:3074
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
#define SCIPdebugMsg
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition scip_param.c:250
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_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition scip_param.c:219
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 SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:83
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition scip_param.c:545
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 SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition scip_param.c:487
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition scip_param.c:904
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition scip_param.c:307
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition scip_param.c:953
SCIP_RETCODE SCIPsetCharParam(SCIP *scip, const char *name, char value)
Definition scip_param.c:661
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 SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition scip_param.c:429
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition scip_param.c:603
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition scip_param.c:979
void SCIPswapPointers(void **pointer1, void **pointer2)
Definition misc.c:10396
SCIP_RETCODE SCIPincludeHeurScheduler(SCIP *scip)
SCIP_RETCODE SCIPresetBandit(SCIP *scip, SCIP_BANDIT *bandit, SCIP_Real *priorities, unsigned int seed)
Definition scip_bandit.c:91
SCIP_RETCODE SCIPbanditUpdate(SCIP_BANDIT *bandit, int action, SCIP_Real score)
Definition bandit.c:174
int SCIPbanditGetNActions(SCIP_BANDIT *bandit)
Definition bandit.c:303
SCIP_Real SCIPgetProbabilityExp3IX(SCIP_BANDIT *exp3ix, int action)
SCIP_Real * SCIPgetWeightsEpsgreedy(SCIP_BANDIT *epsgreedy)
SCIP_RANDNUMGEN * SCIPbanditGetRandnumgen(SCIP_BANDIT *bandit)
Definition bandit.c:293
SCIP_RETCODE SCIPcreateBanditExp3(SCIP *scip, SCIP_BANDIT **exp3, SCIP_Real *priorities, SCIP_Real gammaparam, SCIP_Real beta, int nactions, unsigned int initseed)
SCIP_RETCODE SCIPcreateBanditEpsgreedy(SCIP *scip, SCIP_BANDIT **epsgreedy, SCIP_Real *priorities, SCIP_Real eps, SCIP_Bool usemodification, SCIP_Bool preferrecent, SCIP_Real decayfactor, int avglim, int nactions, unsigned int initseed)
SCIP_Real SCIPgetConfidenceBoundUcb(SCIP_BANDIT *ucb, int action)
Definition bandit_ucb.c:264
SCIP_RETCODE SCIPcreateBanditExp3IX(SCIP *scip, SCIP_BANDIT **exp3ix, SCIP_Real *priorities, int nactions, unsigned int initseed)
SCIP_RETCODE SCIPbanditSelect(SCIP_BANDIT *bandit, int *action)
Definition bandit.c:153
SCIP_RETCODE SCIPcreateBanditUcb(SCIP *scip, SCIP_BANDIT **ucb, SCIP_Real *priorities, SCIP_Real alpha, int nactions, unsigned int initseed)
Definition bandit_ucb.c:339
SCIP_RETCODE SCIPfreeBandit(SCIP *scip, SCIP_BANDIT **bandit)
SCIP_Real SCIPgetProbabilityExp3(SCIP_BANDIT *exp3, int action)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition scip_cons.c:941
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4670
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition scip_cons.c:1174
SCIP_Bool SCIPdivesetIsPublic(SCIP_DIVESET *diveset)
Definition heur.c:764
SCIP_Longint SCIPdivesetGetNBacktracks(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition heur.c:615
SCIP_Longint SCIPdivesetGetNSols(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition heur.c:641
SCIP_Longint SCIPdivesetGetNConflicts(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition heur.c:628
const char * SCIPdivesetGetName(SCIP_DIVESET *diveset)
Definition heur.c:445
SCIP_Longint SCIPdivesetGetNProbingNodes(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition heur.c:602
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition scip_event.c:104
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition event.c:324
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition event.c:1030
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition scip_event.c:286
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:178
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition heur.c:1364
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
int SCIPheurGetPriority(SCIP_HEUR *heur)
Definition heur.c:1514
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:226
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:1579
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition scip_heur.c:258
int SCIPheurGetNDivesets(SCIP_HEUR *heur)
Definition heur.c:1661
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:1453
SCIP_DIVESET ** SCIPheurGetDivesets(SCIP_HEUR *heur)
Definition heur.c:1651
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
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition scip_mem.c:126
#define SCIPfreeBuffer(scip, ptr)
Definition scip_mem.h:134
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:110
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition scip_mem.c:100
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition scip_mem.h:132
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:93
#define SCIPallocBuffer(scip, ptr)
Definition scip_mem.h:122
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition scip_mem.h:99
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition scip_sol.c:2169
SCIP_SOLORIGIN SCIPsolGetOrigin(SCIP_SOL *sol)
Definition sol.c:2711
SCIP_Longint SCIPsolGetNodenum(SCIP_SOL *sol)
Definition sol.c:2784
int SCIPgetNSols(SCIP *scip)
Definition scip_sol.c:2070
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
Definition sol.c:2721
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition scip_sol.c:1254
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition scip_sol.c:2119
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition scip_sol.c:3050
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition scip_sol.c:1077
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1217
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition scip_solve.c:222
SCIP_RETCODE SCIPpresolve(SCIP *scip)
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
SCIP_RETCODE SCIPsolve(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Longint SCIPgetNBestSolsFound(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_RETCODE SCIPaddTrustregionNeighborhoodConstraint(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **subvars, SCIP_Real violpenalty)
SCIP_RETCODE SCIPcopyLargeNeighborhoodSearch(SCIP *sourcescip, SCIP *subscip, SCIP_HASHMAP *varmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool uselprows, SCIP_Bool copycuts, SCIP_Bool *success, SCIP_Bool *valid)
Definition heuristics.c:951
SCIP_TABLE * SCIPfindTable(SCIP *scip, const char *name)
Definition scip_table.c:94
SCIP_RETCODE SCIPincludeTable(SCIP *scip, const char *name, const char *desc, SCIP_Bool active, SCIP_DECL_TABLECOPY((*tablecopy)), SCIP_DECL_TABLEFREE((*tablefree)), SCIP_DECL_TABLEINIT((*tableinit)), SCIP_DECL_TABLEEXIT((*tableexit)), SCIP_DECL_TABLEINITSOL((*tableinitsol)), SCIP_DECL_TABLEEXITSOL((*tableexitsol)), SCIP_DECL_TABLEOUTPUT((*tableoutput)), SCIP_TABLEDATA *tabledata, int position, SCIP_STAGE earlieststage)
Definition scip_table.c:56
SCIP_RETCODE SCIPcreateClock(SCIP *scip, SCIP_CLOCK **clck)
Definition scip_timing.c:76
SCIP_RETCODE SCIPresetClock(SCIP *scip, SCIP_CLOCK *clck)
SCIP_RETCODE SCIPstopClock(SCIP *scip, SCIP_CLOCK *clck)
SCIP_RETCODE SCIPfreeClock(SCIP *scip, SCIP_CLOCK **clck)
SCIP_Real SCIPgetClockTime(SCIP *scip, SCIP_CLOCK *clck)
SCIP_RETCODE SCIPstartClock(SCIP *scip, SCIP_CLOCK *clck)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisDualfeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisDualfeasPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPround(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisDualfeasZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
int SCIPgetDepth(SCIP *scip)
Definition scip_tree.c:670
SCIP_RETCODE SCIPvariablegraphBreadthFirst(SCIP *scip, SCIP_VGRAPH *vargraph, SCIP_VAR **startvars, int nstartvars, int *distances, int maxdistance, int maxvars, int maxbinintvars)
Definition heur.c:1690
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition var.c:17599
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:17538
SCIP_Real SCIPvarGetBestRootSol(SCIP_VAR *var)
Definition var.c:13715
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition var.c:17926
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:18088
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition var.c:17768
SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition var.c:13350
SCIP_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition scip_var.c:4945
SCIP_Real SCIPgetVarPseudocostVal(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta)
Definition scip_var.c:8816
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition var.c:17610
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition var.c:18452
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition scip_var.c:5034
SCIP_Real SCIPgetVarRedcost(SCIP *scip, SCIP_VAR *var)
Definition scip_var.c:1866
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:18078
SCIP_Real SCIPvarGetBestRootRedcost(SCIP_VAR *var)
Definition var.c:13782
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition scip_var.c:4515
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition misc.c:10130
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition misc.c:10108
void SCIPselectInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int k, int len)
void SCIPselectDownInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int k, int len)
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10877
return SCIP_OKAY
SCIPfreeSol(scip, &heurdata->sol))
static SCIP_DIVESET * diveset
SCIPcreateSol(scip, &heurdata->sol, heur))
SCIPfreeRandom(scip, &heurdata->randnumgen)
int selection
SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, lpiterlimit, -1, -1.0, SCIP_DIVECONTEXT_ADAPTIVE))
enum HistIndex HISTINDEX
Definition heur_alns.c:339
HistIndex
Definition heur_alns.c:330
SCIP_Bool cutoff
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
static SCIP_SOL * sol
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
heurdata usednodes
Definition heur_locks.c:158
SCIP_VAR * var
SCIP_Real frac
SCIP_Real newobj
static SCIP_VAR ** vars
int nbinvars
int nintvars
static void tryAdd2variableBuffer(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_VAR **varbuf, SCIP_Real *valbuf, int *nfixings, SCIP_Bool integer)
static SCIP_Real getReward(SCIP *scip, SCIP_HEURDATA *heurdata, int selection, HEUR_STATS *runstats, SCIP_STATUS subscipstatus)
static SCIP_RETCODE includeDivingHeurs(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
#define DEFAULT_ACTIVE_MUTATION
#define DEFAULT_MINFIXINGRATE_ZEROOBJECTIVE
static void printDivingHeurStatistics(SCIP *scip, SCIP_HEURDATA *heurdata, FILE *file)
enum HistIndex HISTINDEX
static SCIP_RETCODE initRest(SCIP *scip, SCIP_HEUR *heur)
#define DECL_NHEXIT(x)
#define TABLE_POSITION_NEIGHBORHOOD
#define DEFAULT_NODESQUOT
static void increaseFixingRate(NH_FIXINGRATE *fx)
#define DEFAULT_MAXCALLSSAMESOL
#define NNEIGHBORHOODS
static SCIP_RETCODE updateSelectionStrategy(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Real reward, int selection)
#define DEFAULT_NSOLSLIM
#define DECL_NHDEACTIVATE(x)
#define DEFAULT_PRIORITY_RENS
#define DEFAULT_ACTIVE_PROXIMITY
#define DEFAULT_NODESQUOTMIN
#define DEFAULT_MINFIXINGRATE_DINS
#define DEFAULT_SEED
#define DEFAULT_ACTIVE_RINS
#define TABLE_NAME_NEIGHBORHOOD
static void initRunStats(SCIP *scip, HEUR_STATS *stats)
#define DEFAULT_COPYCUTS
#define DEFAULT_MAXNODES
static SCIP_RETCODE neighborhoodGetRefsol(SCIP *scip, NH *neighborhood, SCIP_SOL **solptr)
#define DEFAULT_USEREDCOST
#define SOLVEFREQ_DECAY
#define HEUR_TIMING
#define DEFAULT_MINNODES
static void decreaseFixingRate(NH_FIXINGRATE *fx)
#define DECL_NHINIT(x)
#define DECL_NHFREE(x)
static void decreaseSolveFreq(SOLVEFREQ *solvefreqdata)
static SCIP_RETCODE executeLNSHeuristic(SCIP *scip, SCIP_HEUR *heur, int selection, HEUR_STATS *runstats, SCIP_STATUS *subscipstatus, SCIP_RESULT *result)
#define DEFAULT_FIXTOL
static void updateFixingRate(NH *neighborhood, SCIP_STATUS subscipstatus, HEUR_STATS *runstats)
#define SCIP_EVENTTYPE_SCHEDULER
#define DEFAULT_SOLREWARDWEIGHT
#define HEUR_FREQOFS
static void updateRunStats(HEUR_STATS *stats, SCIP *subscip)
#define FIXINGRATE_STARTINC
#define HEUR_DESC
#define DEFAULT_MAXFIXINGRATE_RENS
#define DEFAULT_PRIORITY_PROXIMITY
static void resetTargetNodeLimit(SCIP_HEURDATA *heurdata)
#define SOLVEFREQ_STARTINC
static SCIP_RETCODE neighborhoodInit(SCIP *scip, NH *neighborhood)
#define DEFAULT_ACTIVE_TRUSTREGION
#define DEFAULT_MINFIXINGRATE_RENS
#define DEFAULT_MAXFIXINGRATE_DINS
#define FIXINGRATE_DECAY
#define DEFAULT_MINFIXINGRATE_RINS
#define DEFAULT_PRIORITY_ZEROOBJECTIVE
#define DEFAULT_INITLNSNODELIMIT
#define DEFAULT_WAITINGNODES
#define DEFAULT_HEURTIMELIMIT
#define DEFAULT_NODESOFFSET
#define TABLE_DESC_NEIGHBORHOOD
#define DECL_CHANGESUBSCIP(x)
#define DEFAULT_EFFORTREWARDWEIGHT
#define DEFAULT_RESETWEIGHTS
static SCIP_RETCODE selectHeuristic(SCIP *scip, SCIP_HEURDATA *heurdata, int *selection)
#define HEUR_DISPCHAR
#define DEFAULT_QUALREWARDWEIGHT
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
#define DEFAULT_MAXFIXINGRATE_MUTATION
#define TABLE_EARLIEST_STAGE_NEIGHBORHOOD
#define DECL_NHREFSOL(x)
static void increaseSolveFreq(SOLVEFREQ *solvefreqdata)
#define DEFAULT_USELOCALREDCOST
#define DEFAULT_CONFLICTREWARDWEIGHT
#define DEFAULT_MAXFIXINGRATE_TRUSTREGION
#define DIVINGHEURS_INITIALSIZE
#define DEFAULT_MAXFIXINGRATE_ZEROOBJECTIVE
#define HEUR_NAME
#define DEFAULT_ACTIVE_RENS
#define NHISTENTRIES
static SCIP_RETCODE schedulerIncludeNeighborhood(SCIP *scip, SCIP_HEURDATA *heurdata, NH **neighborhood, const char *name, SCIP_Real minfixingrate, SCIP_Real maxfixingrate, SCIP_Bool active, int priority, DECL_VARFIXINGS((*varfixings)), DECL_CHANGESUBSCIP((*changesubscip)), DECL_NHINIT((*nhinit)), DECL_NHEXIT((*nhexit)), DECL_NHFREE((*nhfree)), DECL_NHREFSOL((*nhrefsol)),)
static void initSolveFreq(SOLVEFREQ *solvefreqdata)
static void updateFixingRateIncrement(NH_FIXINGRATE *fx)
#define DEFAULT_INITDIVINGNODELIMIT
#define DEFAULT_MINFIXINGRATE_CROSSOVER
static SCIP_RETCODE addLocalBranchingConstraint(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **subvars, int distance, SCIP_Bool *success, int *naddedconss)
#define DEFAULT_ACTIVE_ZEROOBJECTIVE
#define DEFAULT_MINFIXINGRATE_LOCALBRANCHING
#define MINSOLVEFREQ
@ HIDX_STALLNODE
@ HIDX_OTHER
@ HIDX_SOLLIM
@ HIDX_USR
@ HIDX_OPT
@ HIDX_INFEAS
@ HIDX_NODELIM
#define DEFAULT_PRIORITY_CROSSOVER
#define DEFAULT_NSELECTIONS
static SCIP_RETCODE setLimits(SCIP *subscip, SOLVELIMITS *solvelimits)
#define DEFAULT_INITDURINGROOT
static SCIP_RETCODE executeHeuristic(SCIP *scip, SCIP_HEUR *heur, int selection, HEUR_STATS *runstats, SCIP_STATUS *subscipstatus, SCIP_RESULT *result)
#define DEFAULT_VIOLPENALTY_TRUSTREGION
#define DEFAULT_UNFIXTOL
static SCIP_RETCODE resetFixingRate(SCIP *scip, NH_FIXINGRATE *fixingrate)
#define DEFAULT_ALPHA
#define MUTATIONSEED
#define DEFAULT_ACTIVE_LOCALBRANCHING
static SCIP_RETCODE fixMatchingSolutionValues(SCIP *scip, SCIP_SOL **sols, int nsols, SCIP_VAR **vars, int nvars, SCIP_VAR **varbuf, SCIP_Real *valbuf, int *nfixings)
#define DEFAULT_PRIORITY_MUTATION
#define DEFAULT_PRIORITY_RINS
static SCIP_Real getVariablePscostScore(SCIP *scip, SCIP_VAR *var, SCIP_Real refsolval, SCIP_Bool uselocallpsol)
#define MAXSOLVEFREQ
static int getHistIndex(SCIP_STATUS subscipstatus)
#define DEFAULT_ACTIVE_DINS
#define EVENTHDLR_DESC
#define DEFAULT_PRIORITY_TRUSTREGION
static void updateSolveFreqIncrement(SOLVEFREQ *solvefreqdata)
#define LPLIMFAC
#define CROSSOVERSEED
#define DEFAULT_MAXFIXINGRATE_LOCALBRANCHING
#define HEUR_FREQ
#define DEFAULT_SUBSCIPRANDSEEDS
#define DEFAULT_NPOOLSOLS_DINS
static void computeIntegerVariableBoundsDins(SCIP *scip, SCIP_VAR *var, SCIP_Real *lbptr, SCIP_Real *ubptr)
#define DEFAULT_MAXFIXINGRATE_RINS
static SCIP_RETCODE includeNeighborhoods(SCIP *scip, SCIP_HEURDATA *heurdata)
#define DEFAULT_MINFIXINGRATE_MUTATION
#define DEFAULT_EPS
static SCIP_RETCODE LNSUnfixVariables(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **varbuf, SCIP_Real *valbuf, int *nfixings, int ntargetfixings, SCIP_Bool *success)
#define DEFAULT_TARGETNODEFACTOR
#define DEFAULT_MAXFIXINGRATE_CROSSOVER
#define DEFAULT_NSOLS_CROSSOVER
#define DEFAULT_USEDISTANCES
static SCIP_RETCODE reinitBandit(SCIP *scip, SCIP_HEURDATA *heurdata, int nactions)
static void updateHeurStatsLNS(HEUR_STATS *runstats, NH *neighborhood, SCIP_STATUS *subscipstatus)
static void resetCurrentNeighborhood(SCIP_HEURDATA *heurdata)
static SCIP_Real getVariableRedcostScore(SCIP *scip, SCIP_VAR *var, SCIP_Real refsolval, SCIP_Bool uselocalredcost)
static void updateSolveFreq(DIVING_HEUR *divingheur, HEUR_STATS *stats)
#define HEUR_USESSUBSCIP
#define DEFAULT_BETA
static SCIP_RETCODE schedulerFreeDivingHeur(SCIP *scip, DIVING_HEUR **divingheur)
static void updateHeurStatsDiving(HEUR_STATS *runstats, DIVING_HEUR *divingheur)
static SCIP_RETCODE schedulerFreeNeighborhood(SCIP *scip, NH **neighborhood)
static SCIP_RETCODE neighborhoodExit(SCIP *scip, NH *neighborhood)
#define DEFAULT_ACTIVE_CROSSOVER
static SCIP_RETCODE executeDivingHeuristic(SCIP *scip, SCIP_HEUR *heur, int selection, HEUR_STATS *runstats, SCIP_RESULT *result)
#define DEFAULT_USESUBSCIPHEURS
#define DEFAULT_PRIORITY_DINS
#define EVENTHDLR_NAME
static void printNeighborhoodStatistics(SCIP *scip, SCIP_HEURDATA *heurdata, FILE *file)
static SCIP_RETCODE setupSubScip(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SOLVELIMITS *solvelimits, SCIP_HEUR *heur, SCIP_Bool objchgd)
static SCIP_RETCODE determineLimits(SCIP *scip, SCIP_HEUR *heur, int selection, SOLVELIMITS *solvelimits, SCIP_Bool *runagain)
#define DEFAULT_MAXFIXINGRATE_PROXIMITY
static SCIP_RETCODE neighborhoodChangeSubscip(SCIP *sourcescip, SCIP *targetscip, NH *neighborhood, SCIP_VAR **targetvars, int *ndomchgs, int *nchgobjs, int *naddedconss, SCIP_Bool *success)
#define DECL_VARFIXINGS(x)
#define DEFAULT_PRIORITY_LOCALBRANCHING
static SCIP_RETCODE heurStatsReset(SCIP *scip, HEUR_STATS *stats, SCIP_Bool usediving)
#define DEFAULT_MINFIXINGRATE_TRUSTREGION
#define DEFAULT_BESTSOLWEIGHT
#define DEFAULT_BANDITALGO
static SCIP_RETCODE LNSFixMoreVariables(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_SOL *refsol, SCIP_VAR **varbuf, SCIP_Real *valbuf, int *nfixings, int ntargetfixings, SCIP_Bool *success)
#define DEFAULT_MINFIXINGRATE_PROXIMITY
static SCIP_RETCODE createBandit(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Real *priorities, unsigned int initseed)
static SCIP_RETCODE neighborhoodFixVariables(SCIP *scip, SCIP_HEURDATA *heurdata, NH *neighborhood, SCIP_VAR **varbuf, SCIP_Real *valbuf, int *nfixings, SCIP_RESULT *result)
#define DEFAULT_GAMMA
#define LRATEMIN
#define DEFAULT_USEPSCOST
static SCIP_RETCODE transferSolution(SCIP *subscip, SCIP_EVENTDATA *eventdata)
Adaptive heuristic to schedule LNS and diving heuristics.
methods commonly used by primal heuristics
static const char * paramname[]
Definition lpi_msk.c:5096
memory allocation routines
#define BMSduplicateMemoryArray(ptr, source, num)
Definition memory.h:143
#define BMSclearMemory(ptr)
Definition memory.h:129
#define BMSfreeMemoryArray(ptr)
Definition memory.h:147
#define BMScopyMemoryArray(ptr, source, num)
Definition memory.h:134
#define BMSclearMemoryArray(ptr, num)
Definition memory.h:130
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition scip_mem.c:57
public methods for bandit algorithms
public methods for the epsilon greedy bandit selector
public methods for Exp.3
public methods for Exp.3-IX
public methods for UCB bandit selection
public methods for managing constraints
public methods for managing events
public methods for primal heuristics
public methods for message output
#define SCIPerrorMessage
Definition pub_message.h:64
public data structures and miscellaneous methods
methods for selecting (weighted) k-medians
public methods for primal CIP solutions
public methods for problem variables
public methods for bandit algorithms
public methods for branching rule plugins and branching
public methods for constraint handler plugins and constraints
public methods for problem copies
public methods for event handler plugins and event handlers
general public methods
public methods for primal heuristic plugins and divesets
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for node selector plugins
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for random numbers
public methods for solutions
public solving methods
public methods for querying solving statistics
public methods for statistics table plugins
public methods for timing
public methods for the branch-and-bound tree
public methods for SCIP variables
SCIP_Longint nodelimit
SCIP_DIVESET * diveset
SOLVEFREQ * solvefreqdata
SCIP_Real priority
HEUR_STATS * stats
SCIP_Real oldupperbound
SCIP_Longint nprobnodes
int statushist[NHISTENTRIES]
SCIP_Longint nbacktracks
SCIP_Longint nconflicts
SCIP_CLOCK * execclock
SCIP_Longint nbestsolsfound
SCIP_Real newupperbound
SCIP_Longint usednodes
SCIP_CLOCK * setupclock
SCIP_Longint nsolsfound
SCIP_Real targetfixingrate
Definition heur_alns.c:364
SCIP_Real increment
Definition heur_alns.c:365
SCIP_Real minfixingrate
Definition heur_alns.c:363
SCIP_Real maxfixingrate
Definition heur_alns.c:366
HEUR_STATS stats
NH_FIXINGRATE fixingrate
Definition heur_alns.c:373
DECL_NHINIT((*nhinit))
DATA_MUTATION * mutation
Definition heur_alns.c:386
int nodelimit
DECL_CHANGESUBSCIP((*changesubscip))
SCIP_Bool active
Definition heur_alns.c:382
DECL_NHFREE((*nhfree))
DATA_CROSSOVER * crossover
Definition heur_alns.c:387
DECL_NHEXIT((*nhexit))
DECL_NHDEACTIVATE((*nhdeactivate))
DATA_TRUSTREGION * trustregion
Definition heur_alns.c:389
int rootnodepriority
DECL_VARFIXINGS((*varfixings))
DECL_NHREFSOL((*nhrefsol))
DATA_DINS * dins
Definition heur_alns.c:388
char * name
Definition heur_alns.c:372
SCIP_Real priority
Definition heur_alns.c:383
union Nh::@5 data
SCIP_SOL * sol
Definition struct_heur.h:71
SCIP_Real minsolvefreq
SCIP_Real increment
SCIP_Real maxsolvefreq
SCIP_Real currentsolvefreq
SCIP_Real timelimit
Definition heur_alns.c:495
SCIP_Longint stallnodes
Definition heur_alns.c:496
SCIP_Longint nodelimit
Definition heur_alns.c:493
SCIP_Real memorylimit
Definition heur_alns.c:494
SCIP * scip
Definition heur_alns.c:504
unsigned int useredcost
Definition heur_alns.c:509
SCIP_Real * randscores
Definition heur_alns.c:505
int * distances
Definition heur_alns.c:506
SCIP_Real * pscostscores
Definition heur_alns.c:508
unsigned int usedistances
Definition heur_alns.c:510
SCIP_Real * redcostscores
Definition heur_alns.c:507
unsigned int usepscost
Definition heur_alns.c:511
SCIP_SOL * selsol
Definition heur_alns.c:404
SCIP_RANDNUMGEN * rng
Definition heur_alns.c:403
int npoolsols
Definition heur_alns.c:410
SCIP_RANDNUMGEN * rng
Definition heur_alns.c:396
SCIP_Real violpenalty
Definition heur_alns.c:415
struct SCIP_EventData SCIP_EVENTDATA
Definition type_event.h:173
#define SCIP_DECL_EVENTEXEC(x)
Definition type_event.h:253
#define SCIP_EVENTTYPE_BESTSOLFOUND
Definition type_event.h:105
#define SCIP_EVENTTYPE_SOLFOUND
Definition type_event.h:144
#define SCIP_EVENTTYPE_LPSOLVED
Definition type_event.h:101
#define SCIP_DECL_HEURINITSOL(x)
Definition type_heur.h:132
#define SCIP_DECL_HEURCOPY(x)
Definition type_heur.h:97
struct SCIP_HeurData SCIP_HEURDATA
Definition type_heur.h:77
#define SCIP_DECL_HEURINIT(x)
Definition type_heur.h:113
#define SCIP_DECL_HEUREXIT(x)
Definition type_heur.h:121
#define SCIP_DECL_HEURFREE(x)
Definition type_heur.h:105
#define SCIP_DECL_HEUREXEC(x)
Definition type_heur.h:163
@ SCIP_DIVECONTEXT_SCHEDULER
Definition type_heur.h:71
@ SCIP_LPSOLSTAT_OPTIMAL
Definition type_lp.h:43
#define SCIP_DECL_SORTINDCOMP(x)
Definition type_misc.h:180
@ SCIP_PARAMSETTING_OFF
@ SCIP_PARAMSETTING_FAST
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_DELAYED
Definition type_result.h:43
@ SCIP_DIDNOTFIND
Definition type_result.h:44
@ SCIP_SUCCESS
Definition type_result.h:58
enum SCIP_Result SCIP_RESULT
Definition type_result.h:61
@ SCIP_INVALIDDATA
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_SOLORIGIN_ORIGINAL
Definition type_sol.h:42
@ SCIP_STATUS_OPTIMAL
Definition type_stat.h:61
@ SCIP_STATUS_TOTALNODELIMIT
Definition type_stat.h:45
@ SCIP_STATUS_BESTSOLLIMIT
Definition type_stat.h:57
@ SCIP_STATUS_SOLLIMIT
Definition type_stat.h:54
@ SCIP_STATUS_UNBOUNDED
Definition type_stat.h:63
@ SCIP_STATUS_UNKNOWN
Definition type_stat.h:42
@ SCIP_STATUS_GAPLIMIT
Definition type_stat.h:53
@ SCIP_STATUS_USERINTERRUPT
Definition type_stat.h:43
@ SCIP_STATUS_TERMINATE
Definition type_stat.h:65
@ SCIP_STATUS_INFORUNBD
Definition type_stat.h:64
@ SCIP_STATUS_STALLNODELIMIT
Definition type_stat.h:48
@ SCIP_STATUS_TIMELIMIT
Definition type_stat.h:51
@ SCIP_STATUS_INFEASIBLE
Definition type_stat.h:62
@ SCIP_STATUS_NODELIMIT
Definition type_stat.h:44
@ SCIP_STATUS_MEMLIMIT
Definition type_stat.h:52
@ SCIP_STATUS_RESTARTLIMIT
Definition type_stat.h:60
enum SCIP_Status SCIP_STATUS
Definition type_stat.h:67
#define SCIP_DECL_TABLEOUTPUT(x)
Definition type_table.h:122
@ SCIP_VARTYPE_INTEGER
Definition type_var.h:63
@ SCIP_VARSTATUS_COLUMN
Definition type_var.h:51