Scippy

SCIP

Solving Constraint Integer Programs

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