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