Scippy

SCIP

Solving Constraint Integer Programs

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 
34 #include "blockmemshell/memory.h"
35 #include "scip/cons_linear.h"
36 #include "scip/heur_scheduler.h"
37 #include "scip/heuristics.h"
39 #include "scip/pub_bandit_exp3.h"
40 #include "scip/pub_bandit_exp3ix.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"
48 #include "scip/pub_misc_select.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"
65 #include "scip/scip_randnumgen.h"
66 #include "scip/scip_sol.h"
67 #include "scip/scip_solve.h"
68 #include "scip/scip_solvingstats.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 
244 typedef struct data_crossover DATA_CROSSOVER; /**< crossover neighborhood data structure */
245 
246 typedef struct data_mutation DATA_MUTATION; /**< mutation neighborhood data structure */
247 
248 typedef struct data_dins DATA_DINS; /**< dins neighborhood data structure */
249 
250 typedef struct data_trustregion DATA_TRUSTREGION; /**< trustregion neighborhood data structure */
251 
252 typedef struct NH_FixingRate NH_FIXINGRATE; /** fixing rate data structure */
253 
254 typedef struct SolveFreq SOLVEFREQ; /** diving heuristic solving frequency data structure */
255 
256 typedef struct Heur_Stats HEUR_STATS; /**< heuristic statistics data structure */
257 
258 typedef struct Nh NH; /**< neighborhood data structure */
259 
260 typedef struct Diving_Heur DIVING_HEUR; /**< diving heuristic data structure */
261 
262 /*
263  * variable priorization data structure for sorting
264  */
265 typedef 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 */
345 };
346 typedef 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 */
374 struct 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 */
383 struct SolveFreq
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 */
392 struct 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 */
429 struct data_mutation
430 {
431  SCIP_RANDNUMGEN* rng; /**< random number generator */
432 };
433 
434 /** crossover neighborhood data structure */
435 struct 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 */
443 struct data_dins
444 {
445  int npoolsols; /**< number of pool solutions where binary solution values must agree */
446 };
447 
448 struct data_trustregion
449 {
450  SCIP_Real violpenalty; /**< the penalty for violating the trust region */
451 };
452 
453 /** primal heuristic data */
454 struct 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 */
525 struct 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 */
536 struct 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 
544 typedef struct SolveLimits SOLVELIMITS;
545 
546 /** data structure that can be used for variable prioritization for additional fixings */
547 struct 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 */
564 static
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 */
581 static
583  NH_FIXINGRATE* fx /**< fixing rate */
584  )
585 {
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  */
594 static
596  NH_FIXINGRATE* fx /**< fixing rate */
597  )
598 {
599  fx->targetfixingrate += fx->increment;
601 }
602 
603 /** decrease fixing rate
604  *
605  * decrease also the rate by which the target fixing rate is adjusted
606  */
607 static
609  NH_FIXINGRATE* fx /**< fixing rate */
610  )
611 {
612  fx->targetfixingrate -= fx->increment;
614 }
615 
616 /** update fixing rate based on the results of the current run */
617 static
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 {
624  NH_FIXINGRATE* fx;
625 
626  fx = &neighborhood->fixingrate;
627 
628  switch (subscipstatus)
629  {
630  case SCIP_STATUS_OPTIMAL:
635  /* decrease the fixing rate (make subproblem harder) */
636  decreaseFixingRate(fx);
637  break;
643  /* increase the fixing rate (make the subproblem easier) only if no solution was found */
644  if( runstats->nbestsolsfound <= 0 )
645  increaseFixingRate(fx);
646  break;
647  /* fall through cases to please lint */
648  case SCIP_STATUS_UNKNOWN:
654  default:
655  break;
656  }
657 
659 }
660 
661 /** reset the currently active neighborhood */
662 static
664  SCIP_HEURDATA* heurdata
665  )
666 {
667  assert(heurdata != NULL);
668  heurdata->currneighborhood = -1;
669  heurdata->ndelayedcalls = 0;
670 }
671 
672 /** reset target node limit */
673 static
675  SCIP_HEURDATA* heurdata /**< heuristic data */
676  )
677 {
678  heurdata->targetnodes = heurdata->minnodes;
679 }
680 
681 /** Reset neighborhood statistics */
682 static
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 
703  SCIP_CALL( SCIPresetClock(scip, stats->setupclock) );
704  SCIP_CALL( SCIPresetClock(scip, stats->execclock) );
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 */
716 static
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);
739  assert(neighborhood != NULL);
740  assert(name != NULL);
741 
742  SCIP_CALL( SCIPallocBlockMemory(scip, neighborhood) );
743  assert(*neighborhood != NULL);
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 */
781 static
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);
789  assert(neighborhood != NULL);
790 
791  nhptr = *neighborhood;
792  assert(nhptr != NULL);
793 
794  BMSfreeMemoryArray(&nhptr->name);
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 
805  SCIPfreeBlockMemory(scip, neighborhood);
806  *neighborhood = NULL;
807 
808  return SCIP_OKAY;
809 }
810 
811 /** initialize neighborhood specific data */
812 static
814  SCIP* scip, /**< SCIP data structure */
815  NH* neighborhood /**< neighborhood to initialize */
816  )
817 {
818  assert(scip != NULL);
819  assert(neighborhood != NULL);
820 
821  /* call the init callback of the neighborhood */
822  if( neighborhood->nhinit != NULL )
823  {
824  SCIP_CALL( neighborhood->nhinit(scip, neighborhood) );
825  }
826 
827  return SCIP_OKAY;
828 }
829 
830 /** deinitialize neighborhood specific data */
831 static
833  SCIP* scip, /**< SCIP data structure */
834  NH* neighborhood /**< neighborhood to initialize */
835  )
836 {
837  assert(scip != NULL);
838  assert(neighborhood != NULL);
839 
840  if( neighborhood->nhexit != NULL )
841  {
842  SCIP_CALL( neighborhood->nhexit(scip, neighborhood) );
843  }
844 
845  return SCIP_OKAY;
846 }
847 
848 /** creates a new solution for the original problem by copying the solution of the subproblem */
849 static
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;
862  SCIP_SOL* oldbestsol;
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 */
884  SCIP_CALL( SCIPtrySolFree(sourcescip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
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 */
900 static
902  SCIP* scip, /**< SCIP data structure */
903  DIVING_HEUR** divingheur /**< pointer to diving heuristic that should be freed */
904  )
905 {
906  DIVING_HEUR* divingheurptr;
907  assert(scip != NULL);
908  assert(divingheur != NULL);
909 
910  divingheurptr = *divingheur;
911  assert(divingheurptr != NULL);
912 
913  SCIP_CALL( SCIPfreeClock(scip, &divingheurptr->stats->setupclock) );
914  SCIP_CALL( SCIPfreeClock(scip, &divingheurptr->stats->execclock) );
915 
916  SCIPfreeBlockMemory(scip, &divingheurptr->solvefreqdata);
917  SCIPfreeBlockMemory(scip, &divingheurptr->stats);
918  SCIPfreeBlockMemory(scip, divingheur);
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  */
929 static
930 SCIP_DECL_EVENTEXEC(eventExecScheduler)
931 {
932  assert(eventhdlr != NULL);
933  assert(eventdata != NULL);
934  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
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));
952  SCIP_CALL( SCIPinterruptSolve(scip) );
953  }
954  break;
955  default:
956  break;
957  }
958 
959  return SCIP_OKAY;
960 }
961 
962 /** initialize heuristic statistics before the next run */
963 static
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;
977  stats->oldupperbound = SCIPgetUpperbound(scip);
978  stats->newupperbound = SCIPgetUpperbound(scip);
979 }
980 
981 /** update run stats after the sub SCIP was solved */
982 static
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 */
996 static
998  SCIP_STATUS subscipstatus /**< sub-SCIP status */
999  )
1000 {
1001  switch (subscipstatus)
1002  {
1003  case SCIP_STATUS_OPTIMAL:
1004  return (int)HIDX_OPT;
1006  return (int)HIDX_INFEAS;
1007  case SCIP_STATUS_NODELIMIT:
1008  return (int)HIDX_NODELIM;
1010  return (int)HIDX_STALLNODE;
1011  case SCIP_STATUS_SOLLIMIT:
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 */
1022 static
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  {
1040  NH* neighborhood;
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':
1068  epsgreedyweight = SCIPgetWeightsEpsgreedy(heurdata->bandit)[i + heurdata->ndiving];
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 */
1097 static
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  {
1112  DIVING_HEUR* divingheur;
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':
1137  ucb = SCIPgetConfidenceBoundUcb(heurdata->bandit, i);
1138  break;
1139  case 'g':
1140  epsgreedyweight = SCIPgetWeightsEpsgreedy(heurdata->bandit)[i];
1141  break;
1142  case 'e':
1143  proba = SCIPgetProbabilityExp3(heurdata->bandit, i);
1144  break;
1145  case 'i':
1146  probaix = SCIPgetProbabilityExp3IX(heurdata->bandit, 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 */
1165 static
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 
1173  assert(divingheur != NULL);
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 */
1194 static
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 
1203  assert( subscipstatus != NULL );
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  */
1237 static
1238 SCIP_DECL_SORTINDCOMP(sortIndCompScheduler)
1239 { /*lint --e{715}*/
1240  VARPRIO* varprio;
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 */
1306 static
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 
1328  bestbound = SCIPvarGetBestRootSol(var);
1329 
1330  /* using global reduced costs, the two factors yield a nonnegative score within tolerances */
1331  assert(SCIPisDualfeasZero(scip, redcost)
1332  || (SCIPisDualfeasNegative(scip, redcost) && ! SCIPisFeasPositive(scip, refsolval - bestbound))
1333  || (SCIPisDualfeasPositive(scip, redcost) && ! SCIPisFeasNegative(scip, refsolval - bestbound)));
1334  }
1335  else
1336  {
1337  /* this can be safely asserted here, since the heuristic would not reach this point, otherwise */
1338  assert(SCIPhasCurrentNodeLP(scip));
1339  assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL);
1340 
1341  redcost = SCIPgetVarRedcost(scip, var);
1342 
1343  bestbound = SCIPvarGetLPSol(var);
1344  }
1345 
1346  assert(! SCIPisInfinity(scip, REALABS(bestbound)));
1347  assert(SCIPisDualfeasZero(scip, redcost) || SCIPisFeasIntegral(scip, bestbound));
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 */
1359 static
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 
1376  lpsolval = uselocallpsol ? SCIPvarGetLPSol(var) : SCIPvarGetRootSol(var);
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  */
1388 static
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 {
1399  assert(SCIPisFeasIntegral(scip, val) || ! SCIPvarIsIntegral(var));
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  */
1426 static
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 {
1438  VARPRIO varprio;
1439  SCIP_VAR** vars;
1440  SCIP_Real* redcostscores;
1441  SCIP_Real* pscostscores;
1442  SCIP_Real* solvals;
1443  SCIP_RANDNUMGEN* rng;
1444  SCIP_VAR** unfixedvars;
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 
1466  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
1467 
1468  nbinintvars = nbinvars + nintvars;
1469 
1470  if( ntargetfixings >= nbinintvars )
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 
1485  SCIP_CALL( SCIPallocBufferArray(scip, &randscores, nbinintvars) );
1486  SCIP_CALL( SCIPallocBufferArray(scip, &perm, nbinintvars) );
1487  SCIP_CALL( SCIPallocBufferArray(scip, &distances, nvars) );
1488  SCIP_CALL( SCIPallocBufferArray(scip, &redcostscores, nbinintvars) );
1489  SCIP_CALL( SCIPallocBufferArray(scip, &solvals, nbinintvars) );
1490  SCIP_CALL( SCIPallocBufferArray(scip, &isfixed, nbinintvars) );
1491  SCIP_CALL( SCIPallocBufferArray(scip, &unfixedvars, nbinintvars) );
1492  SCIP_CALL( SCIPallocBufferArray(scip, &pscostscores, nbinintvars) );
1493 
1494  /* initialize variable graph distances from already fixed variables */
1495  if( varprio.usedistances )
1496  {
1497  SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, NULL, varbuf, *nfixings, distances, INT_MAX, INT_MAX, ntargetfixings) );
1498  }
1499  else
1500  {
1501  /* initialize all equal distances to make them irrelevant */
1502  BMSclearMemoryArray(distances, nbinintvars);
1503  }
1504 
1505  BMSclearMemoryArray(isfixed, nbinintvars);
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 
1520  SCIP_CALL( SCIPgetSolVals(scip, refsol, nbinintvars, vars, solvals) );
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 
1539  unfixedvars[nunfixedvars] = var;
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 
1560  nvarstoadd = MIN(nunfixedvars, nvarstoadd);
1561 
1562  /* select the first nvarstoadd many variables according to the score */
1563  if( nvarstoadd < nunfixedvars )
1564  SCIPselectInd(perm, sortIndCompScheduler, &varprio, 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);
1571  assert(permindex < nunfixedvars);
1572 
1573  tryAdd2variableBuffer(scip, unfixedvars[permindex], solvals[permindex], varbuf, valbuf, nfixings, TRUE);
1574  }
1575 
1576  *success = TRUE;
1577 
1578  /* free buffer arrays */
1579  SCIPfreeBufferArray(scip, &pscostscores);
1580  SCIPfreeBufferArray(scip, &unfixedvars);
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 */
1592 static
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) */
1638 static
1639 SCIP_DECL_HEURCOPY(heurCopyScheduler)
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 */
1652 static
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);
1661  assert(neighborhood != NULL);
1662 
1663  *solptr = NULL;
1664  if( neighborhood->nhrefsol != NULL )
1665  {
1666  SCIP_RESULT result;
1667  SCIP_CALL( neighborhood->nhrefsol(scip, neighborhood, solptr, &result) );
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  */
1683 static
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 {
1694  VARPRIO varprio;
1695  SCIP_Real* redcostscores;
1696  SCIP_Real* pscostscores;
1697  SCIP_Real* randscores;
1698  SCIP_VAR** unfixedvars;
1699  SCIP_VAR** varbufcpy;
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 
1714  nbinintvars = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
1715  if( nbinintvars == 0 )
1716  return SCIP_OKAY;
1717 
1718  assert(*nfixings > 0);
1719 
1720  nvars = SCIPgetNVars(scip);
1721  SCIP_CALL( SCIPallocBufferArray(scip, &isfixedvar, nvars) );
1722  SCIP_CALL( SCIPallocBufferArray(scip, &unfixedvars, nbinintvars) );
1723  SCIP_CALL( SCIPallocBufferArray(scip, &distances, nvars) );
1724  SCIP_CALL( SCIPallocBufferArray(scip, &fixeddistances, *nfixings) );
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 
1730  SCIP_CALL( SCIPduplicateBufferArray(scip, &varbufcpy, varbuf, *nfixings) );
1731  SCIP_CALL( SCIPduplicateBufferArray(scip, &valbufcpy, valbuf, *nfixings) );
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;
1748  vars = SCIPgetVars(scip);
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  {
1761  SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, NULL, unfixedvars, nunfixed, distances, INT_MAX, INT_MAX, INT_MAX) );
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  {
1772  BMSclearMemoryArray(fixeddistances, *nfixings);
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  {
1779  SCIP_VAR* fixedvar = varbuf[i];
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 */
1801  SCIPselectDownInd(perm, sortIndCompScheduler, &varprio, ntargetfixings, *nfixings);
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 */
1813  SCIPfreeBufferArray(scip, &valbufcpy);
1814  SCIPfreeBufferArray(scip, &varbufcpy);
1815  SCIPfreeBufferArray(scip, &pscostscores);
1816  SCIPfreeBufferArray(scip, &perm);
1817  SCIPfreeBufferArray(scip, &randscores);
1818  SCIPfreeBufferArray(scip, &redcostscores);
1819  SCIPfreeBufferArray(scip, &fixeddistances);
1820  SCIPfreeBufferArray(scip, &distances);
1821  SCIPfreeBufferArray(scip, &unfixedvars);
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 */
1830 static
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);
1847  assert(neighborhood != NULL);
1848  assert(varbuf != NULL);
1849  assert(valbuf != NULL);
1850  assert(nfixings != NULL);
1851  assert(result != NULL);
1852 
1853  *nfixings = 0;
1854 
1855  *result = SCIP_DIDNOTRUN;
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  {
1867  *result = SCIP_SUCCESS;
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);
1873  nbinintvars = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
1874  ntargetfixings = (int)(neighborhood->fixingrate.targetfixingrate * nbinintvars);
1875  nminfixings = (int)((neighborhood->fixingrate.targetfixingrate - heurdata->fixtol) * nbinintvars);
1876  nminfixings = MAX(nminfixings, 0);
1877  nmaxfixings = (int)((neighborhood->fixingrate.targetfixingrate + heurdata->unfixtol) * nbinintvars);
1878  nmaxfixings = MIN(nmaxfixings, 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;
1886  SCIP_SOL* refsol;
1887 
1888  /* get reference solution from neighborhood */
1889  SCIP_CALL( neighborhoodGetRefsol(scip, neighborhood, &refsol) );
1890 
1891  /* try to fix more variables based on the reference solution */
1892  if( refsol != NULL )
1893  {
1894  SCIP_CALL( LNSFixMoreVariables(scip, heurdata, refsol, varbuf, valbuf, nfixings, ntargetfixings, &success) );
1895  }
1896  else
1897  success = FALSE;
1898 
1899  if( success )
1900  *result = SCIP_SUCCESS;
1901  else if( *result == SCIP_SUCCESS )
1902  *result = SCIP_DIDNOTFIND;
1903  else
1904  *result = SCIP_DIDNOTRUN;
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 
1912  SCIP_CALL( LNSUnfixVariables(scip, heurdata, varbuf, valbuf, nfixings, ntargetfixings, &success) );
1913 
1914  assert(success);
1915  *result = SCIP_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 */
1927 static
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);
1940  assert(targetscip != NULL);
1941  assert(neighborhood != NULL);
1942  assert(targetvars != 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 */
1967 static
1969  SCIP* subscip, /**< SCIP data structure */
1970  SOLVELIMITS* solvelimits /**< pointer to solving limits data structure */
1971  )
1972 {
1973  assert(subscip != NULL);
1974  assert(solvelimits != 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 */
1987 static
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 {
1996  SCIP_HEURDATA* heurdata;
1997  SCIP_Bool avoidmemout;
1998 
1999  assert(scip != NULL);
2000  assert(heur != NULL);
2001  assert(solvelimits != 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 */
2034 static
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 */
2057  if( selection > heurdata->ndiving && subscipstatus == SCIP_STATUS_TIMELIMIT )
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 */
2112 static
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 {
2122  SCIP_HEURDATA* heurdata;
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 */
2189  if( ! SCIPisInfinity(scip, SCIPgetUpperbound(scip)) )
2190  {
2191  cutoff = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
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 
2205  vars = SCIPgetVars(scip);
2206  nvars = SCIPgetNVars(scip);
2207 
2208  SCIP_CALL( SCIPcreateConsLinear(subscip, &objcons, "objbound_of_origscip", 0, NULL, NULL, -SCIPinfinity(subscip), cutoff,
2209  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
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 */
2236 static
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 */
2253 static
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  */
2266 static
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  */
2279 static
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 */
2289 static
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 
2302 }
2303 
2304 /** find publicly available divesets and store them */
2305 static
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  {
2333  SCIP_DIVESET* diveset = SCIPheurGetDivesets(heurs[h])[d];
2334 
2335  if( SCIPdivesetIsPublic(diveset) )
2336  {
2337  DIVING_HEUR* divingheur;
2338 
2339  SCIPdebugMsg(scip, "Found publicly available diveset %s\n", SCIPdivesetGetName(diveset));
2340 
2341  /* allocate memory for the diving heuristic */
2342  SCIP_CALL( SCIPallocBlockMemory(scip, &divingheur) );
2343  SCIP_CALL( SCIPallocBlockMemory(scip, &(divingheur->stats)) );
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)) );
2355  SCIP_CALL( heurStatsReset(scip, divingheur->stats, TRUE) );
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 */
2378 static
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  {
2405  SCIP_CALL( SCIPbanditSelect(bandit, selection) );
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 */
2414 static
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);
2432  SCIP_CALL( SCIPbanditUpdate(bandit, selection, reward) );
2433 
2434  return SCIP_OKAY;
2435 }
2436 
2437 /** execute diving heuristic */
2438 static
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 {
2447  SCIP_HEURDATA* heurdata;
2448  DIVING_HEUR** divingheurs;
2449  SCIP_DIVESET* diveset;
2450 
2451  heurdata = SCIPheurGetData(heur);
2452  assert(heurdata != NULL);
2453 
2454  divingheurs = heurdata->divingheurs;
2455  assert(divingheurs != NULL);
2456  assert(heurdata->ndiving > 0);
2457  assert(selection < heurdata->ndiving);
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 */
2470  runstats->nbestsolsfound = SCIPgetNBestSolsFound(scip);
2471  runstats->oldupperbound = SCIPgetUpperbound(scip);
2472 
2473  if( strcmp(SCIPdivesetGetName(diveset), "guideddiving") != 0 || (strcmp(SCIPdivesetGetName(diveset), "guideddiving") == 0
2474  && SCIPgetNSols(scip) != 0 && !SCIPsolIsOriginal(SCIPgetBestSol(scip))) )
2475  {
2476  SCIP_CALL( SCIPstartClock(scip, divingheurs[selection]->stats->execclock) );
2477 
2478  /* perform dive */
2479  SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, divingheurs[selection]->diveset, heurdata->sol, heur,
2480  result, FALSE, -1LL, (int) divingheurs[selection]->nodelimit,
2481  divingheurs[selection]->solvefreqdata->currentsolvefreq, SCIP_DIVECONTEXT_SCHEDULER) );
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.) */
2490  runstats->nsolsfound = SCIPdivesetGetNSols(diveset, SCIP_DIVECONTEXT_SCHEDULER) - runstats->nsolsfound;
2491  runstats->nbestsolsfound = SCIPgetNBestSolsFound(scip) - runstats->nbestsolsfound;
2492  runstats->newupperbound = SCIPgetUpperbound(scip);
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",
2498  SCIPdivesetGetName(diveset), selection, runstats->nsolsfound, runstats->nbestsolsfound,
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 */
2510 static
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 {
2520  SCIP_HEURDATA* heurdata;
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;
2529  NH* neighborhood;
2530  SOLVELIMITS solvelimits;
2531  SCIP_Bool success;
2532  SCIP_Bool run;
2533 
2534  SCIP_HASHMAP* varmapf;
2535  SCIP_EVENTHDLR* eventhdlr;
2536  SCIP_EVENTDATA eventdata;
2537  char probnamesuffix[SCIP_MAXSTRLEN];
2538  int ndomchgs;
2539  int nchgobjs;
2540  int naddedconss;
2541  int v;
2542  SCIP_RETCODE retcode;
2543  SCIP_RESULT fixresult;
2544 
2545  heurdata = SCIPheurGetData(heur);
2546  assert(heurdata != NULL);
2547 
2548  *result = SCIP_DIDNOTRUN;
2549  *subscipstatus = SCIP_STATUS_UNKNOWN;
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 */
2555  SCIP_CALL( determineLimits(scip, heur, selection, &solvelimits, &run) );
2556 
2557  if( ! run )
2558  return SCIP_OKAY;
2559 
2560  /* allocate memory for variable fixings buffer */
2561  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2562  SCIP_CALL( SCIPallocBufferArray(scip, &varbuf, nvars) );
2563  SCIP_CALL( SCIPallocBufferArray(scip, &valbuf, nvars) );
2564  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
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 */
2572  SCIP_CALL( neighborhoodFixVariables(scip, heurdata, neighborhood, varbuf, valbuf, &nfixings, &fixresult) );
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 
2593  *result = SCIP_DIDNOTFIND;
2594 
2595  neighborhood->stats.nfixings += nfixings;
2596  runstats->nfixings = nfixings;
2597 
2598  SCIP_CALL( SCIPcreate(&subscip) );
2599  SCIP_CALL( SCIPhashmapCreate(&varmapf, SCIPblkmem(scip), nvars) );
2600  (void) SCIPsnprintf(probnamesuffix, SCIP_MAXSTRLEN, "scheduler_%s", neighborhood->name);
2601 
2602  /* todo later: run global propagation for this set of fixings */
2603  SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapf, probnamesuffix, varbuf, valbuf, nfixings, FALSE, heurdata->copycuts, &success, NULL) );
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 
2611  SCIPhashmapFree(&varmapf);
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 */
2635  SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecScheduler, NULL) );
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 
2670 CLEANUP:
2671  if( subscip != NULL )
2672  {
2673  SCIP_CALL( SCIPfree(&subscip) );
2674  }
2675 
2676  SCIPfreeBufferArray(scip, &subvars);
2677  SCIPfreeBufferArray(scip, &valbuf);
2678  SCIPfreeBufferArray(scip, &varbuf);
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 
2694  resetCurrentNeighborhood(heurdata);
2695  }
2696 
2697  return SCIP_OKAY;
2698 }
2699 
2700 /** execute selected heuristic */
2701 static
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 {
2711  SCIP_HEURDATA* heurdata;
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  {
2722  SCIP_CALL( executeDivingHeuristic(scip, heur, selection, runstats, result) );
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 */
2733 static
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) );
2763  resetTargetNodeLimit(heurdata);
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  */
2775 static
2777  SCIP* scip, /**< SCIP data structure */
2778  SCIP_HEUR* heur /**< scheduler heuristic */
2779  )
2780 {
2781  SCIP_HEURDATA* heurdata;
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 */
2790  SCIP_CALL( includeDivingHeurs(scip, heur, heurdata) );
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 */
2834 static
2835 SCIP_DECL_HEUREXEC(heurExecScheduler)
2836 { /*lint --e{715}*/
2837  SCIP_HEURDATA* heurdata;
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",
2849  SCIPgetDepth(scip), SCIPgetNSols(scip), nodeinfeasible, SCIPgetNNodes(scip));
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 
2858  *result = SCIP_DELAYED;
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 */
2869  if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) )
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
2900  && (SCIPgetNNodes(scip) - SCIPsolGetNodenum(SCIPgetBestSol(scip))) < heurdata->waitingnodes )
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 
2920  *result = SCIP_DIDNOTRUN;
2921  success = FALSE;
2922  {
2923  int selection;
2924  SCIP_Real reward;
2925  HEUR_STATS* stats;
2926  SCIP_STATUS subscipstatus;
2927 
2928  subscipstatus = SCIP_STATUS_UNKNOWN;
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 */
2936  SCIP_CALL( selectHeuristic(scip, heurdata, &selection) );
2937 
2938  /* execute selected heuristic */
2939  SCIP_CALL( executeHeuristic(scip, heur, selection, stats, &subscipstatus, result) );
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 */
2948  reward = getReward(scip, heurdata, selection, stats, subscipstatus);
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 */
2969  SCIP_CALL( updateSelectionStrategy(scip, heurdata, reward, selection) );
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 */
2985 static
2986 DECL_VARFIXINGS(varFixingsRens)
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 
3001  *result = SCIP_DELAYED;
3002 
3003  if( ! SCIPhasCurrentNodeLP(scip) )
3004  return SCIP_OKAY;
3006  return SCIP_OKAY;
3007 
3008  *result = SCIP_DIDNOTRUN;
3009 
3010  /* get variable information */
3011  SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
3012 
3013  /* return if no binary or integer variables are present */
3014  if( nbinvars + nintvars == 0 )
3015  return SCIP_OKAY;
3016 
3017  SCIP_CALL( SCIPallocBufferArray(scip, &fracidx, nbinvars + nintvars) );
3018  SCIP_CALL( SCIPallocBufferArray(scip, &frac, nbinvars + nintvars) );
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);
3025  assert((i < nbinvars && SCIPvarIsBinary(var)) || (i >= nbinvars && SCIPvarIsIntegral(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 */
3041  if( *nfixings < neighborhood->fixingrate.targetfixingrate * (nbinvars + nintvars) && nfracs > 0 )
3042  {
3043  SCIPsortDownRealInt(frac, fracidx, nfracs);
3044 
3045  /* prefer variables that are almost integer */
3046  for( i = 0; i < nfracs && *nfixings < neighborhood->fixingrate.targetfixingrate * (nbinvars + nintvars); i++ )
3047  {
3048  tryAdd2variableBuffer(scip, vars[fracidx[i]], SCIPround(scip, SCIPvarGetLPSol(vars[fracidx[i]])), varbuf, valbuf, nfixings, TRUE);
3049  }
3050  }
3051 
3052  SCIPfreeBufferArray(scip, &frac);
3053  SCIPfreeBufferArray(scip, &fracidx);
3054 
3055  *result = SCIP_SUCCESS;
3056 
3057  return SCIP_OKAY;
3058 }
3059 
3060 /** callback for RENS subproblem changes */
3061 static
3062 DECL_CHANGESUBSCIP(changeSubscipRens)
3063 { /*lint --e{715}*/
3064  SCIP_VAR** vars;
3065  int nintvars;
3066  int nbinvars;
3067  int i;
3068 
3069  assert(SCIPhasCurrentNodeLP(sourcescip));
3070  assert(SCIPgetLPSolstat(sourcescip) == SCIP_LPSOLSTAT_OPTIMAL);
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  {
3092  SCIP_CALL( SCIPchgVarLbGlobal(targetscip, subvars[i], newlb) );
3093  SCIP_CALL( SCIPchgVarUbGlobal(targetscip, subvars[i], newub) );
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  */
3107 static
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;
3122  SCIP_SOL* firstsol;
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;
3136  SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
3137  nbinintvars = nbinvars + nintvars;
3138  nvars = nbinintvars;
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];
3151  assert((v < SCIPgetNBinVars(scip) && SCIPvarIsBinary(var)) || (v >= SCIPgetNBinVars(scip) && SCIPvarIsIntegral(var)));
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 */
3173 static
3174 DECL_VARFIXINGS(varFixingsRins)
3175 {
3176  /*lint --e{715}*/
3177  int nbinvars;
3178  int nintvars;
3179  SCIP_VAR** vars;
3180  SCIP_SOL* incumbent;
3181  SCIP_SOL* sols[2];
3182  assert(scip != NULL);
3183  assert(varbuf != NULL);
3184  assert(nfixings != NULL);
3185  assert(valbuf != NULL);
3186 
3187  *result = SCIP_DELAYED;
3188 
3189  if( ! SCIPhasCurrentNodeLP(scip) )
3190  return SCIP_OKAY;
3192  return SCIP_OKAY;
3193 
3194  *result = SCIP_DIDNOTRUN;
3195 
3196  incumbent = SCIPgetBestSol(scip);
3197  if( incumbent == NULL )
3198  return SCIP_OKAY;
3199 
3200  if( SCIPsolGetOrigin(incumbent) == SCIP_SOLORIGIN_ORIGINAL )
3201  return SCIP_OKAY;
3202 
3203  /* get variable information */
3204  SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
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 
3213  SCIP_CALL( fixMatchingSolutionValues(scip, sols, 2, vars, nbinvars + nintvars, varbuf, valbuf, nfixings) );
3214 
3215  *result = SCIP_SUCCESS;
3216 
3217  return SCIP_OKAY;
3218 }
3219 
3220 /** initialization callback for crossover when a new problem is read */
3221 static
3222 DECL_NHINIT(nhInitCrossover)
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 */
3240 static
3241 DECL_NHEXIT(nhExitCrossover)
3242 { /*lint --e{715}*/
3243  DATA_CROSSOVER* data;
3244  data = neighborhood->data.crossover;
3245 
3246  assert(neighborhood != NULL);
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 */
3255 static
3256 DECL_NHFREE(nhFreeCrossover)
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 */
3265 static
3266 DECL_VARFIXINGS(varFixingsCrossover)
3267 { /*lint --e{715}*/
3268  DATA_CROSSOVER* data;
3269  SCIP_RANDNUMGEN* rng;
3270  SCIP_SOL** sols;
3271  SCIP_SOL** scipsols;
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 
3285  *result = SCIP_DIDNOTRUN;
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 */
3292  if( SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) == 0 )
3293  return SCIP_OKAY;
3294 
3295  rng = data->rng;
3296  lastdraw = SCIPgetNSols(scip);
3297  SCIP_CALL( SCIPallocBufferArray(scip, &sols, nsols) );
3298  scipsols = SCIPgetSols(scip);
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--;
3328  lastdraw = nextdraw;
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 
3338  *result = SCIP_SUCCESS;
3339 
3340  SCIPfreeBufferArray(scip, &sols);
3341 
3342  return SCIP_OKAY;
3343 }
3344 
3345 /** callback for crossover reference solution */
3346 static
3347 DECL_NHREFSOL(nhRefsolCrossover)
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;
3356  *result = SCIP_SUCCESS;
3357  }
3358  else
3359  {
3360  *result = SCIP_DIDNOTFIND;
3361  }
3362 
3363  return SCIP_OKAY;
3364 }
3365 
3366 /** initialization callback for mutation when a new problem is read */
3367 static
3368 DECL_NHINIT(nhInitMutation)
3369 { /*lint --e{715}*/
3370  DATA_MUTATION* data;
3371  assert(scip != NULL);
3372  assert(neighborhood != 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 */
3385 static
3386 DECL_NHEXIT(nhExitMutation)
3387 { /*lint --e{715}*/
3388  DATA_MUTATION* data;
3389  assert(scip != NULL);
3390  assert(neighborhood != 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 */
3402 static
3403 DECL_VARFIXINGS(varFixingsMutation)
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;
3415  SCIP_SOL* incumbentsol;
3416  SCIP_Real targetfixingrate;
3417 
3418  assert(scip != NULL);
3419  assert(neighborhood != NULL);
3420  assert(neighborhood->data.mutation != NULL);
3421  assert(neighborhood->data.mutation->rng != NULL);
3422  rng = neighborhood->data.mutation->rng;
3423 
3424  *result = SCIP_DIDNOTRUN;
3425 
3426  /* get the problem variables */
3427  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
3428 
3429  nbinintvars = nbinvars + nintvars;
3430  if( nbinintvars == 0 )
3431  return SCIP_OKAY;
3432 
3433  incumbentsol = SCIPgetBestSol(scip);
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 */
3441  if( nbinintvars <= ntargetfixings )
3442  return SCIP_OKAY;
3443 
3444  *result = SCIP_DIDNOTFIND;
3445 
3446  /* copy variables into a buffer array */
3447  SCIP_CALL( SCIPduplicateBufferArray(scip, &varscpy, vars, nbinintvars) );
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);
3453  assert(randint < nbinintvars);
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 */
3460  tryAdd2variableBuffer(scip, varscpy[i], SCIPgetSolVal(scip, incumbentsol, varscpy[i]), varbuf, valbuf, nfixings, TRUE);
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 )
3471  *result = SCIP_SUCCESS;
3472 
3473  /* free the buffer array */
3474  SCIPfreeBufferArray(scip, &varscpy);
3475 
3476  return SCIP_OKAY;
3477 }
3478 
3479 /** add local branching constraint */
3480 static
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;
3492  SCIP_SOL* referencesol;
3493  SCIP_CONS* localbranchcons;
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 
3514  SCIP_CALL( SCIPallocBufferArray(sourcescip, &consvals, nbinvars) );
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) );
3534  SCIP_CALL( SCIPaddCons(targetscip, localbranchcons) );
3535  SCIP_CALL( SCIPreleaseCons(targetscip, &localbranchcons) );
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 */
3546 static
3547 DECL_CHANGESUBSCIP(changeSubscipLocalbranching)
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 */
3556 static
3557 DECL_CHANGESUBSCIP(changeSubscipProximity)
3558 { /*lint --e{715}*/
3559  SCIP_SOL* referencesol;
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 */
3608 static
3609 DECL_CHANGESUBSCIP(changeSubscipZeroobjective)
3610 { /*lint --e{715}*/
3611  SCIP_CONSHDLR* conshdlrnl;
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");
3628  if( conshdlrnl != NULL && SCIPconshdlrGetNActiveConss(conshdlrnl) > 0 )
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 */
3648 static
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 */
3664  lbglobal = SCIPvarGetLbGlobal(var);
3665  ubglobal = SCIPvarGetUbGlobal(var);
3666 
3667  assert(SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER);
3668  /* get the current LP solution for each variable */
3669  lpsol = SCIPvarGetLPSol(var);
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  {
3688  range = SCIPfeasCeil(scip, range);
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  {
3699  range = SCIPfeasFloor(scip, range);
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 */
3722 static
3723 DECL_VARFIXINGS(varFixingsDins)
3724 {
3725  DATA_DINS* data;
3726  SCIP_SOL* rootlpsol;
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);
3737  nmipsols = SCIPgetNSols(scip);
3738  nmipsols = MIN(nmipsols, data->npoolsols);
3739 
3740  *result = SCIP_DELAYED;
3741 
3743  return SCIP_OKAY;
3744 
3745  *result = SCIP_DIDNOTRUN;
3746 
3747  if( nmipsols == 0 )
3748  return SCIP_OKAY;
3749 
3750  SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
3751 
3752  if( nbinvars + nintvars == 0 )
3753  return SCIP_OKAY;
3754 
3755  SCIP_CALL( SCIPcreateSol(scip, &rootlpsol, NULL) );
3756 
3757  /* save root solution LP values in solution */
3758  for( v = 0; v < nbinvars + nintvars; ++v )
3759  {
3760  SCIP_CALL( SCIPsetSolVal(scip, rootlpsol, vars[v], SCIPvarGetRootSol(vars[v])) );
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;
3784  computeIntegerVariableBoundsDins(scip, vars[v], &lb, &ub);
3785 
3786  if( ub - lb < 0.5 )
3787  {
3788  assert(SCIPisFeasIntegral(scip, lb));
3789  tryAdd2variableBuffer(scip, vars[v], lb, varbuf, valbuf, nfixings, TRUE);
3790  }
3791  }
3792 
3793  *result = SCIP_SUCCESS;
3794 
3795  SCIPfreeBufferArray(scip, &sols);
3796 
3797  SCIP_CALL( SCIPfreeSol(scip, &rootlpsol) );
3798 
3799  return SCIP_OKAY;
3800 }
3801 
3802 /** callback for DINS subproblem changes */
3803 static
3804 DECL_CHANGESUBSCIP(changeSubscipDins)
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 */
3839 static
3840 DECL_NHFREE(nhFreeDins)
3841 {
3842  assert(neighborhood->data.dins != NULL);
3843 
3844  SCIPfreeBlockMemory(scip, &neighborhood->data.dins);
3845 
3846  return SCIP_OKAY;
3847 }
3848 
3849 /** deinitialization callback for trustregion before SCIP is freed */
3850 static
3851 DECL_NHFREE(nhFreeTrustregion)
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 */
3861 static
3862 DECL_CHANGESUBSCIP(changeSubscipTrustregion)
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 */
3869  SCIP_CALL( SCIPaddTrustregionNeighborhoodConstraint(sourcescip, targetscip, subvars, data->violpenalty) );
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 */
3880 static
3881 DECL_NHREFSOL(nhRefsolIncumbent)
3882 { /*lint --e{715}*/
3883  assert(scip != NULL);
3884 
3885  if( SCIPgetBestSol(scip) != NULL )
3886  {
3887  *result = SCIP_SUCCESS;
3888  *solptr = SCIPgetBestSol(scip);
3889  }
3890  else
3891  {
3892  *result = SCIP_DIDNOTFIND;
3893  }
3894 
3895  return SCIP_OKAY;
3896 }
3897 
3898 
3899 /** callback function that deactivates a neighborhood on problems with no discrete variables */
3900 static
3901 DECL_NHDEACTIVATE(nhDeactivateDiscreteVars)
3902 { /*lint --e{715}*/
3903  assert(scip != NULL);
3904  assert(deactivate != NULL);
3905 
3906  /* deactivate if no discrete variables are present */
3907  *deactivate = (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) == 0);
3908 
3909  return SCIP_OKAY;
3910 }
3911 
3912 /** callback function that deactivates a neighborhood on problems with no binary variables */
3913 static
3914 DECL_NHDEACTIVATE(nhDeactivateBinVars)
3915 { /*lint --e{715}*/
3916  assert(scip != NULL);
3917  assert(deactivate != 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 */
3926 static
3927 DECL_NHDEACTIVATE(nhDeactivateObjVars)
3928 { /*lint --e{715}*/
3929  assert(scip != NULL);
3930  assert(deactivate != 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 */
3940 static
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;
3949  NH* localbranching;
3950  NH* crossover;
3951  NH* proximity;
3952  NH* zeroobjective;
3953  NH* dins;
3954  NH* trustregion;
3955 
3956  heurdata->nneighborhoods = 0;
3957 
3958  /* include the RENS neighborhood */
3959  SCIP_CALL( schedulerIncludeNeighborhood(scip, heurdata, &rens, "rens",
3961  varFixingsRens, changeSubscipRens, NULL, NULL, NULL, NULL, nhDeactivateDiscreteVars) );
3962 
3963  /* include the RINS neighborhood */
3964  SCIP_CALL( schedulerIncludeNeighborhood(scip, heurdata, &rins, "rins",
3966  varFixingsRins, NULL, NULL, NULL, NULL, nhRefsolIncumbent, nhDeactivateDiscreteVars) );
3967 
3968  /* include the mutation neighborhood */
3969  SCIP_CALL( schedulerIncludeNeighborhood(scip, heurdata, &mutation, "mutation",
3971  varFixingsMutation, NULL, nhInitMutation, nhExitMutation, NULL, nhRefsolIncumbent, nhDeactivateDiscreteVars) );
3972 
3973  /* include the local branching neighborhood */
3974  SCIP_CALL( schedulerIncludeNeighborhood(scip, heurdata, &localbranching, "localbranching",
3976  NULL, changeSubscipLocalbranching, NULL, NULL, NULL, nhRefsolIncumbent, nhDeactivateBinVars) );
3977 
3978  /* include the crossover neighborhood */
3979  SCIP_CALL( schedulerIncludeNeighborhood(scip, heurdata, &crossover, "crossover",
3981  varFixingsCrossover, NULL,
3982  nhInitCrossover, nhExitCrossover, nhFreeCrossover, nhRefsolCrossover, nhDeactivateDiscreteVars) );
3983 
3984  /* allocate data for crossover to include the parameter */
3985  SCIP_CALL( SCIPallocBlockMemory(scip, &crossover->data.crossover) );
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 */
3993  SCIP_CALL( schedulerIncludeNeighborhood(scip, heurdata, &proximity, "proximity",
3995  NULL, changeSubscipProximity, NULL, NULL, NULL, nhRefsolIncumbent, nhDeactivateBinVars) );
3996 
3997  /* include the Zeroobjective neighborhood */
3998  SCIP_CALL( schedulerIncludeNeighborhood(scip, heurdata, &zeroobjective, "zeroobjective",
4000  NULL, changeSubscipZeroobjective, NULL, NULL, NULL, nhRefsolIncumbent, nhDeactivateObjVars) );
4001 
4002  /* include the DINS neighborhood */
4003  SCIP_CALL( schedulerIncludeNeighborhood(scip, heurdata, &dins, "dins",
4005  varFixingsDins, changeSubscipDins, NULL, NULL, nhFreeDins, nhRefsolIncumbent, nhDeactivateBinVars) );
4006 
4007  /* allocate data for DINS to include the parameter */
4008  SCIP_CALL( SCIPallocBlockMemory(scip, &dins->data.dins) );
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",
4018  NULL, changeSubscipTrustregion, NULL, NULL, nhFreeTrustregion, nhRefsolIncumbent, nhDeactivateBinVars) );
4019 
4020  /* allocate data for trustregion to include the parameter */
4021  SCIP_CALL( SCIPallocBlockMemory(scip, &trustregion->data.trustregion) );
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) */
4031 static
4032 SCIP_DECL_HEURINIT(heurInitScheduler)
4033 { /*lint --e{715}*/
4034  SCIP_HEURDATA* heurdata;
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 
4051  SCIP_CALL( neighborhoodInit(scip, neighborhood) );
4052 
4053  SCIP_CALL( resetFixingRate(scip, &neighborhood->fixingrate) );
4054 
4055  SCIP_CALL( heurStatsReset(scip, &neighborhood->stats, FALSE) );
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) */
4075 static
4076 SCIP_DECL_HEURINITSOL(heurInitsolScheduler)
4077 { /*lint --e{715}*/
4078  SCIP_HEURDATA* heurdata;
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;
4146  SCIP_CALL( SCIPallocBufferArray(scip, &initpriorities, nheurs) );
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 
4161  SCIPfreeBufferArray(scip, &initpriorities);
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) );
4170  resetTargetNodeLimit(heurdata);
4171  }
4172  else if( heurdata->resetweights )
4173  {
4174  SCIP_CALL( SCIPresetBandit(scip, heurdata->bandit, priorities, initseed) );
4175  resetTargetNodeLimit(heurdata);
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 
4186  resetCurrentNeighborhood(heurdata);
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) */
4195 static
4196 SCIP_DECL_HEUREXIT(heurExitScheduler)
4197 { /*lint --e{715}*/
4198  SCIP_HEURDATA* heurdata;
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 
4212  SCIP_CALL( neighborhoodExit(scip, neighborhood) );
4213  }
4214 
4215  /* free working solution */
4216  SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
4217 
4218  return SCIP_OKAY;
4219 }
4220 
4221 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
4222 static
4223 SCIP_DECL_HEURFREE(heurFreeScheduler)
4224 { /*lint --e{715}*/
4225  SCIP_HEURDATA* heurdata;
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 
4262  SCIPfreeBlockMemoryArray(scip, &heurdata->neighborhoods, NNEIGHBORHOODS);
4263 
4264  SCIPfreeBlockMemory(scip, &heurdata);
4265 
4266  return SCIP_OKAY;
4267 }
4268 
4269 /** output method of statistics table to output file stream 'file' */
4270 static
4271 SCIP_DECL_TABLEOUTPUT(tableOutputNeighborhood)
4272 { /*lint --e{715}*/
4273  SCIP_HEURDATA* heurdata;
4274 
4275  assert(SCIPfindHeur(scip, HEUR_NAME) != NULL);
4276  heurdata = SCIPheurGetData(SCIPfindHeur(scip, HEUR_NAME));
4277  assert(heurdata != NULL);
4278 
4279  /* print neighborhood statistics */
4280  printNeighborhoodStatistics(scip, heurdata, file);
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 )
4288  printDivingHeurStatistics(scip, heurdata, file);
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 {
4302  SCIP_HEURDATA* heurdata;
4303  SCIP_HEUR* heur;
4304 
4305  /* create primal heuristic data */
4306  heurdata = NULL;
4307  heur = NULL;
4308 
4309  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
4310  BMSclearMemory(heurdata);
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 */
4320  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->neighborhoods, NNEIGHBORHOODS) );
4321 
4322  /* include primal heuristic */
4323  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
4325  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecScheduler, heurdata) );
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  */
4333  SCIP_CALL( includeNeighborhoods(scip, heurdata) );
4334 
4335  /* set non fundamental callbacks via setter functions */
4336  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyScheduler) );
4337  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeScheduler) );
4338  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitScheduler) );
4339  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolScheduler) );
4340  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitScheduler) );
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",
4345  &heurdata->maxnodes, TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
4346 
4347  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
4348  "offset added to the nodes budget",
4349  &heurdata->nodesoffset, FALSE, DEFAULT_NODESOFFSET, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
4350 
4351  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
4352  "minimum number of nodes required to start a sub-SCIP",
4353  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
4354 
4355  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/waitingnodes",
4356  "number of nodes since last incumbent solution that the heuristic should wait",
4357  &heurdata->waitingnodes, TRUE, DEFAULT_WAITINGNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
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 
4487  assert(SCIPfindTable(scip, TABLE_NAME_NEIGHBORHOOD) == NULL);
4489  NULL, NULL, NULL, NULL, NULL, NULL, tableOutputNeighborhood,
4491 
4492  return SCIP_OKAY;
4493 }
#define DEFAULT_ACTIVE_DINS
#define DEFAULT_GAMMA
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
Definition: sol.c:2721
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIP_Real targetfixingrate
Definition: heur_alns.c:365
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIP_EVENTTYPE_SCHEDULER
#define DECL_NHINIT(x)
#define DEFAULT_PRIORITY_PROXIMITY
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2082
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
NH_STATS stats
Definition: heur_alns.c:375
public methods for the epsilon greedy bandit selector
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#define DEFAULT_MINFIXINGRATE_RENS
#define DEFAULT_PRIORITY_LOCALBRANCHING
SCIP_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4945
int nfixings
Definition: heur_alns.c:356
#define DEFAULT_USESUBSCIPHEURS
#define SCIP_EVENTTYPE_LPSOLVED
Definition: type_event.h:101
static void updateSolveFreqIncrement(SOLVEFREQ *solvefreqdata)
SCIP_Real increment
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:979
HEUR_STATS * stats
#define DEFAULT_QUALREWARDWEIGHT
#define NULL
Definition: def.h:267
int nruns
Definition: heur_alns.c:352
int SCIPheurGetPriority(SCIP_HEUR *heur)
Definition: heur.c:1514
static SCIP_DECL_HEUREXEC(heurExecScheduler)
SCIP_DIVESET * diveset
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
static void updateHeurStatsDiving(HEUR_STATS *runstats, DIVING_HEUR *divingheur)
SCIP_Longint SCIPdivesetGetNBacktracks(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:615
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
#define DEFAULT_NSOLS_CROSSOVER
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for SCIP parameter handling
#define HEUR_DESC
HistIndex
Definition: heur_alns.c:330
SCIP_RETCODE SCIPcreateBanditExp3(SCIP *scip, SCIP_BANDIT **exp3, SCIP_Real *priorities, SCIP_Real gammaparam, SCIP_Real beta, int nactions, unsigned int initseed)
Definition: bandit_exp3.c:311
SCIP_RETCODE SCIPcreateBanditUcb(SCIP *scip, SCIP_BANDIT **ucb, SCIP_Real *priorities, SCIP_Real alpha, int nactions, unsigned int initseed)
Definition: bandit_ucb.c:339
static void resetTargetNodeLimit(SCIP_HEURDATA *heurdata)
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)
#define DEFAULT_BESTSOLWEIGHT
#define DECL_NHEXIT(x)
public methods for node selector plugins
#define SOLVEFREQ_STARTINC
#define DEFAULT_MINFIXINGRATE_ZEROOBJECTIVE
public methods for memory management
static SCIP_RETCODE includeDivingHeurs(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
enum HistIndex HISTINDEX
Definition: heur_alns.c:340
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
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 DECL_NHDEACTIVATE(x)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
DATA_DINS * dins
Definition: heur_alns.c:389
static SCIP_DECL_TABLEOUTPUT(tableOutputNeighborhood)
#define MUTATIONSEED
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18079
#define DEFAULT_SOLREWARDWEIGHT
SCIP_Longint nprobnodes
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:307
#define SCIP_MAXSTRLEN
Definition: def.h:288
SCIP_Real SCIPgetVarPseudocostVal(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta)
Definition: scip_var.c:8816
static SCIP_RETCODE setupSubScip(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SOLVELIMITS *solvelimits, SCIP_HEUR *heur, SCIP_Bool objchgd)
#define HEUR_NAME
#define DEFAULT_NSOLSLIM
SCIP_RETCODE SCIPbanditSelect(SCIP_BANDIT *bandit, int *action)
Definition: bandit.c:153
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:210
SCIP_Real SCIPgetVarRedcost(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1866
#define DEFAULT_USEREDCOST
#define DEFAULT_UNFIXTOL
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
char * name
Definition: heur_alns.c:373
public solving methods
static SCIP_DECL_HEURINITSOL(heurInitsolScheduler)
int nodelimit
SCIP_Longint nbestsolsfound
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
static void printNeighborhoodStatistics(SCIP *scip, SCIP_HEURDATA *heurdata, FILE *file)
public methods for timing
SCIP_RETCODE SCIPincludeHeurScheduler(SCIP *scip)
#define DEFAULT_ACTIVE_RINS
SCIP_DIVESET ** SCIPheurGetDivesets(SCIP_HEUR *heur)
Definition: heur.c:1651
#define DEFAULT_COPYCUTS
#define DEFAULT_INITDURINGROOT
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17600
SCIP_TABLE * SCIPfindTable(SCIP *scip, const char *name)
Definition: scip_table.c:94
SCIP_Real maxsolvefreq
SCIP_RETCODE SCIPstopClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip_timing.c:178
static SCIP_RETCODE neighborhoodGetRefsol(SCIP *scip, NH *neighborhood, SCIP_SOL **solptr)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
DATA_CROSSOVER * crossover
Definition: heur_alns.c:388
SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition: var.c:13351
#define DEFAULT_PRIORITY_MUTATION
void SCIPswapPointers(void **pointer1, void **pointer2)
Definition: misc.c:10396
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1866
#define DEFAULT_PRIORITY_TRUSTREGION
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip_sol.c:2119
#define FALSE
Definition: def.h:94
SCIP_Real * pscostscores
Definition: heur_alns.c:509
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
#define EVENTHDLR_NAME
public methods for Exp.3-IX
#define DEFAULT_PRIORITY_CROSSOVER
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:324
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
static int getHistIndex(SCIP_STATUS subscipstatus)
#define DEFAULT_MAXFIXINGRATE_TRUSTREGION
#define DEFAULT_SEED
SCIP_Real SCIPinfinity(SCIP *scip)
#define TABLE_POSITION_NEIGHBORHOOD
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
#define TRUE
Definition: def.h:93
SCIP_Longint stallnodes
Definition: heur_alns.c:497
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
int * distances
Definition: heur_alns.c:507
methods commonly used by primal heuristics
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:953
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:297
SCIP_HEUR ** SCIPgetHeurs(SCIP *scip)
Definition: scip_heur.c:271
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_Longint usednodes
NH_FIXINGRATE fixingrate
Definition: heur_alns.c:374
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17769
static void increaseFixingRate(NH_FIXINGRATE *fx)
SCIP_Bool SCIPisDualfeasZero(SCIP *scip, SCIP_Real val)
#define DEFAULT_MINNODES
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
public methods for problem variables
static GRAPHNODE ** active
void SCIPselectInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int k, int len)
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
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
HEUR_STATS stats
static SCIP_RETCODE heurStatsReset(SCIP *scip, HEUR_STATS *stats, SCIP_Bool usediving)
SCIP_Real timelimit
Definition: heur_alns.c:496
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:10108
SCIP_CLOCK * execclock
Adaptive heuristic to schedule LNS and diving heuristics.
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
SCIP_RETCODE SCIPfreeClock(SCIP *scip, SCIP_CLOCK **clck)
Definition: scip_timing.c:127
#define DEFAULT_PRIORITY_RENS
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
#define DEFAULT_USEPSCOST
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
DATA_TRUSTREGION * trustregion
Definition: heur_alns.c:390
#define SCIP_LONGINT_MAX
Definition: def.h:159
#define MINSOLVEFREQ
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:307
static SCIP_RETCODE addLocalBranchingConstraint(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **subvars, int distance, SCIP_Bool *success, int *naddedconss)
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip_general.c:590
public methods for SCIP variables
#define DECL_CHANGESUBSCIP(x)
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:603
Definition: heur_alns.c:371
SCIP_Longint SCIPdivesetGetNProbingNodes(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:602
SCIP_Real violpenalty
Definition: heur_alns.c:416
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
SCIP_Longint nsolsfound
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:5034
#define SCIPdebugMsg
Definition: scip_message.h:78
static void updateFixingRate(NH *neighborhood, SCIP_STATUS subscipstatus, HEUR_STATS *runstats)
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 SCIPprintStatistics(SCIP *scip, FILE *file)
#define DEFAULT_ACTIVE_MUTATION
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
#define DEFAULT_NODESQUOTMIN
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
public methods for numerical tolerances
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
#define DEFAULT_FIXTOL
#define DEFAULT_SUBSCIPRANDSEEDS
#define DEFAULT_ACTIVE_TRUSTREGION
public methods for querying solving statistics
union Nh::@5 data
SCIP_Bool SCIPdivesetIsPublic(SCIP_DIVESET *diveset)
Definition: heur.c:764
#define DEFAULT_INITLNSNODELIMIT
public methods for the branch-and-bound tree
#define DEFAULT_NPOOLSOLS_DINS
static SCIP_DECL_HEURFREE(heurFreeScheduler)
#define FIXINGRATE_DECAY
static SCIP_DECL_HEURINIT(heurInitScheduler)
#define NHISTENTRIES
SCIP_Real * redcostscores
Definition: heur_alns.c:508
SCIP_Real increment
Definition: heur_alns.c:366
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip_lp.c:667
#define DEFAULT_MAXFIXINGRATE_RINS
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18089
static SCIP_RETCODE setLimits(SCIP *subscip, SOLVELIMITS *solvelimits)
#define LRATEMIN
static void initRunStats(SCIP *scip, HEUR_STATS *stats)
public methods for managing constraints
#define DEFAULT_USEDISTANCES
#define SCIP_EVENTTYPE_SOLFOUND
Definition: type_event.h:144
#define MAXSOLVEFREQ
static void printDivingHeurStatistics(SCIP *scip, SCIP_HEURDATA *heurdata, FILE *file)
#define DECL_NHREFSOL(x)
SCIP_Real memorylimit
Definition: heur_alns.c:495
static void updateFixingRateIncrement(NH_FIXINGRATE *fx)
#define TABLE_NAME_NEIGHBORHOOD
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:226
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2486
#define DEFAULT_BANDITALGO
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1453
SCIP_RETCODE SCIPcreateClock(SCIP *scip, SCIP_CLOCK **clck)
Definition: scip_timing.c:76
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip_heur.c:258
#define BMSfreeMemoryArray(ptr)
Definition: memory.h:147
static void computeIntegerVariableBoundsDins(SCIP *scip, SCIP_VAR *var, SCIP_Real *lbptr, SCIP_Real *ubptr)
static SCIP_RETCODE executeLNSHeuristic(SCIP *scip, SCIP_HEUR *heur, int selection, HEUR_STATS *runstats, SCIP_STATUS *subscipstatus, SCIP_RESULT *result)
#define SCIPerrorMessage
Definition: pub_message.h:64
DATA_MUTATION * mutation
Definition: heur_alns.c:387
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:219
static void initSolveFreq(SOLVEFREQ *solvefreqdata)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2770
SCIP * scip
Definition: heur_alns.c:505
static SCIP_Real getVariableRedcostScore(SCIP *scip, SCIP_VAR *var, SCIP_Real refsolval, SCIP_Bool uselocalredcost)
#define TABLE_DESC_NEIGHBORHOOD
SCIP_RETCODE SCIPaddTrustregionNeighborhoodConstraint(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **subvars, SCIP_Real violpenalty)
Definition: heuristics.c:1025
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
#define DECL_NHFREE(x)
SCIP_Longint SCIPdivesetGetNSols(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:641
#define NNEIGHBORHOODS
static SCIP_DECL_HEURCOPY(heurCopyScheduler)
public methods for event handler plugins and event handlers
static SCIP_RETCODE determineLimits(SCIP *scip, SCIP_HEUR *heur, int selection, SOLVELIMITS *solvelimits, SCIP_Bool *runagain)
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1254
SCIP_RETCODE SCIPfreeBandit(SCIP *scip, SCIP_BANDIT **bandit)
Definition: scip_bandit.c:107
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)), DECL_NHDEACTIVATE((*nhdeactivate)))
#define SCIPallocBuffer(scip, ptr)
Definition: scip_mem.h:122
SCIP_Longint nodelimit
static SCIP_RETCODE schedulerFreeNeighborhood(SCIP *scip, NH **neighborhood)
#define DEFAULT_ACTIVE_LOCALBRANCHING
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:429
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:498
SCIP_RETCODE SCIPpresolve(SCIP *scip)
Definition: scip_solve.c:2316
#define DEFAULT_MAXCALLSSAMESOL
SCIP_RANDNUMGEN * rng
Definition: heur_alns.c:397
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
void SCIPselectDownInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int k, int len)
SCIP_SOL * sol
Definition: struct_heur.h:71
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:173
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3108
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:250
SCIP_SOL * selsol
Definition: heur_alns.c:405
SCIP_CLOCK * setupclock
#define HEUR_MAXDEPTH
SCIP_RETCODE SCIPperformGenericDivingAlgorithm(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Bool nodeinfeasible, SCIP_Longint iterlim, int nodelimit, SCIP_Real lpresolvedomchgquot, SCIP_DIVECONTEXT divecontext)
Definition: heuristics.c:220
static SCIP_RETCODE resetFixingRate(SCIP *scip, NH_FIXINGRATE *fixingrate)
SCIP_Real minsolvefreq
#define DEFAULT_MAXFIXINGRATE_ZEROOBJECTIVE
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 REALABS(x)
Definition: def.h:197
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:18453
static SCIP_RETCODE initRest(SCIP *scip, SCIP_HEUR *heur)
public methods for problem copies
public methods for primal CIP solutions
#define SCIP_CALL(x)
Definition: def.h:380
SCIP_Real SCIPgetLowerbound(SCIP *scip)
static SCIP_RETCODE neighborhoodInit(SCIP *scip, NH *neighborhood)
#define DEFAULT_MAXFIXINGRATE_CROSSOVER
#define HEUR_USESSUBSCIP
#define HEUR_FREQOFS
SCIP_VAR * h
Definition: circlepacking.c:68
#define DEFAULT_EPS
SCIP_Longint nodelimit
Definition: heur_alns.c:494
unsigned int useredcost
Definition: heur_alns.c:510
SCIP_Longint nbestsolsfound
Definition: heur_alns.c:355
static SCIP_RETCODE includeNeighborhoods(SCIP *scip, SCIP_HEURDATA *heurdata)
#define DEFAULT_EFFORTREWARDWEIGHT
int SCIPheurGetNDivesets(SCIP_HEUR *heur)
Definition: heur.c:1661
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1579
static void decreaseFixingRate(NH_FIXINGRATE *fx)
SCIP_CLOCK * setupclock
Definition: heur_alns.c:347
SCIP_Bool SCIPisDualfeasNegative(SCIP *scip, SCIP_Real val)
#define DEFAULT_HEURTIMELIMIT
#define DEFAULT_MAXFIXINGRATE_DINS
#define BMSduplicateMemoryArray(ptr, source, num)
Definition: memory.h:143
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:83
public methods for primal heuristic plugins and divesets
public methods for constraint handler plugins and constraints
#define DEFAULT_PRIORITY_DINS
#define DEFAULT_NODESQUOT
#define DEFAULT_USELOCALREDCOST
SCIP_Real priority
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_var.c:4515
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
#define CROSSOVERSEED
static SCIP_RETCODE selectHeuristic(SCIP *scip, SCIP_HEURDATA *heurdata, int *selection)
SCIP_Real * randscores
Definition: heur_alns.c:506
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1077
public data structures and miscellaneous methods
SCIP_Real SCIPgetProbabilityExp3(SCIP_BANDIT *exp3, int action)
Definition: bandit_exp3.c:363
#define SCIP_Bool
Definition: def.h:91
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:286
#define HEUR_PRIORITY
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
static void tryAdd2variableBuffer(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_VAR **varbuf, SCIP_Real *valbuf, int *nfixings, SCIP_Bool integer)
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:1030
SCIP_Longint usednodes
Definition: heur_alns.c:349
SCIP_Real newupperbound
static SCIP_RETCODE executeDivingHeuristic(SCIP *scip, SCIP_HEUR *heur, int selection, HEUR_STATS *runstats, SCIP_RESULT *result)
SCIP_Longint SCIPsolGetNodenum(SCIP_SOL *sol)
Definition: sol.c:2784
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
#define DEFAULT_ACTIVE_CROSSOVER
enum SCIP_Status SCIP_STATUS
Definition: type_stat.h:67
static const char * paramname[]
Definition: lpi_msk.c:5096
SCIP_RETCODE SCIPcreateBanditExp3IX(SCIP *scip, SCIP_BANDIT **exp3ix, SCIP_Real *priorities, int nactions, unsigned int initseed)
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip_prob.c:1422
#define DECL_VARFIXINGS(x)
SCIP_Real SCIPgetClockTime(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip_timing.c:319
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
#define DEFAULT_PRIORITY_ZEROOBJECTIVE
public methods for statistics table plugins
static void increaseSolveFreq(SOLVEFREQ *solvefreqdata)
#define DEFAULT_NSELECTIONS
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_Bool active
Definition: heur_alns.c:383
#define MIN(x, y)
Definition: def.h:243
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:487
#define DEFAULT_MINFIXINGRATE_TRUSTREGION
static SCIP_DECL_SORTINDCOMP(sortIndCompScheduler)
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:841
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17927
public methods for bandit algorithms
SCIP_Real SCIPvarGetBestRootRedcost(SCIP_VAR *var)
Definition: var.c:13783
#define DEFAULT_MINFIXINGRATE_CROSSOVER
static SCIP_Real getReward(SCIP *scip, SCIP_HEURDATA *heurdata, int selection, HEUR_STATS *runstats, SCIP_STATUS subscipstatus)
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2070
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:134
#define FIXINGRATE_STARTINC
static SCIP_RETCODE reinitBandit(SCIP *scip, SCIP_HEURDATA *heurdata, int nactions)
static SCIP_RETCODE neighborhoodExit(SCIP *scip, NH *neighborhood)
#define DEFAULT_BETA
static SCIP_RETCODE updateSelectionStrategy(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Real reward, int selection)
Constraint handler for linear constraints in their most general form, .
int SCIPgetNObjVars(SCIP *scip)
Definition: scip_prob.c:2220
#define HEUR_DISPCHAR
#define DEFAULT_MAXFIXINGRATE_LOCALBRANCHING
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
int npoolsols
Definition: heur_alns.c:411
#define BMSclearMemory(ptr)
Definition: memory.h:129
SCIP_Longint nsolsfound
Definition: heur_alns.c:354
SCIP_Longint nbacktracks
static SCIP_RETCODE executeHeuristic(SCIP *scip, SCIP_HEUR *heur, int selection, HEUR_STATS *runstats, SCIP_STATUS *subscipstatus, SCIP_RESULT *result)
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4672
unsigned int usedistances
Definition: heur_alns.c:511
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10130
#define DEFAULT_NODESOFFSET
public methods for the LP relaxation, rows and columns
#define DEFAULT_INITDIVINGNODELIMIT
SCIP_RETCODE SCIPsetCharParam(SCIP *scip, const char *name, char value)
Definition: scip_param.c:661
#define HEUR_FREQ
public methods for bandit algorithms
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
SCIP_RETCODE SCIPbanditUpdate(SCIP_BANDIT *bandit, int action, SCIP_Real score)
Definition: bandit.c:174
#define SCIP_REAL_MAX
Definition: def.h:174
#define LPLIMFAC
SCIP_Real SCIPgetProbabilityExp3IX(SCIP_BANDIT *exp3ix, int action)
static SCIP_Real getVariablePscostScore(SCIP *scip, SCIP_VAR *var, SCIP_Real refsolval, SCIP_Bool uselocallpsol)
#define DEFAULT_RESETWEIGHTS
SCIP_Real currentsolvefreq
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)
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
#define DEFAULT_MINFIXINGRATE_PROXIMITY
SCIP_Longint nconflicts
public methods for branching rule plugins and branching
int SCIPgetNHeurs(SCIP *scip)
Definition: scip_heur.c:282
SCIP_Bool SCIPisDualfeasPositive(SCIP *scip, SCIP_Real val)
SCIP_VAR ** b
Definition: circlepacking.c:65
public methods for managing events
#define SCIP_EVENTTYPE_BESTSOLFOUND
Definition: type_event.h:105
general public methods
#define SCIPfreeBuffer(scip, ptr)
Definition: scip_mem.h:134
#define MAX(x, y)
Definition: def.h:239
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:247
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2169
SCIP_Longint SCIPdivesetGetNConflicts(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:628
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:167
#define DEFAULT_MAXFIXINGRATE_MUTATION
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)
#define DEFAULT_TARGETNODEFACTOR
public methods for solutions
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition: scip_mem.c:100
public methods for random numbers
#define TABLE_EARLIEST_STAGE_NEIGHBORHOOD
SCIP_Real maxfixingrate
Definition: heur_alns.c:367
SCIP_RETCODE SCIPresetClock(SCIP *scip, SCIP_CLOCK *clck)