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