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-2018 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  SCIP* scip;
1179 
1180  varprio = (VARPRIO*)dataptr;
1181  assert(varprio != NULL);
1182  assert(varprio->randscores != NULL);
1183 
1184  scip = varprio->scip;
1185  assert(scip != NULL);
1186 
1187  if( ind1 == ind2 )
1188  return 0;
1189 
1190  /* priority is on distances, if enabled. The variable which is closer in a breadth-first search sense to
1191  * the already fixed variables has precedence */
1192  if( varprio->usedistances )
1193  {
1194  int dist1;
1195  int dist2;
1196 
1197  dist1 = varprio->distances[ind1];
1198  dist2 = varprio->distances[ind2];
1199 
1200  if( dist1 < 0 )
1201  dist1 = INT_MAX;
1202 
1203  if( dist2 < 0 )
1204  dist2 = INT_MAX;
1205 
1206  assert(varprio->distances != NULL);
1207  if( dist1 < dist2 )
1208  return -1;
1209  else if( dist1 > dist2 )
1210  return 1;
1211  }
1212 
1213  assert(! varprio->usedistances || varprio->distances[ind1] == varprio->distances[ind2]);
1214 
1215  /* if the indices tie considering reduced costs or distances are disabled -> use reduced cost information instead */
1216  if( varprio->useredcost )
1217  {
1218  assert(varprio->redcostscores != NULL);
1219 
1220  if( SCIPisLT(scip, varprio->redcostscores[ind1], varprio->redcostscores[ind2]) )
1221  return -1;
1222  else if( SCIPisGT(scip, varprio->redcostscores[ind1], varprio->redcostscores[ind2]) )
1223  return 1;
1224  }
1225 
1226  assert(! varprio->useredcost || SCIPisEQ(scip, varprio->redcostscores[ind1], varprio->redcostscores[ind2]));
1227 
1228  /* use pseudo cost scores if reduced costs are disabled or a tie was found */
1229  if( varprio->usepscost )
1230  {
1231  assert(varprio->pscostscores != NULL);
1232 
1233  /* prefer the variable with smaller pseudocost score */
1234  if( SCIPisLT(scip, varprio->pscostscores[ind1], varprio->pscostscores[ind2]) )
1235  return -1;
1236  else if( SCIPisGT(scip, varprio->pscostscores[ind1], varprio->pscostscores[ind2]) )
1237  return 1;
1238  }
1239 
1240  if( varprio->randscores[ind1] < varprio->randscores[ind2] )
1241  return -1;
1242  else if( varprio->randscores[ind1] > varprio->randscores[ind2] )
1243  return 1;
1244 
1245  return ind1 - ind2;
1246 }
1247 
1248 /** Compute the reduced cost score for this variable in the reference solution */
1249 static
1251  SCIP* scip, /**< SCIP data structure */
1252  SCIP_VAR* var, /**< the variable for which the score should be computed */
1253  SCIP_Real refsolval, /**< solution value in reference solution */
1254  SCIP_Bool uselocalredcost /**< should local reduced costs be used for generic (un)fixing? */
1255  )
1256 {
1257  SCIP_Real bestbound;
1258  SCIP_Real redcost;
1259  SCIP_Real score;
1260  assert(scip != NULL);
1261  assert(var != NULL);
1262 
1263  /* prefer column variables */
1265  return SCIPinfinity(scip);
1266 
1267  if( ! uselocalredcost )
1268  {
1269  redcost = SCIPvarGetBestRootRedcost(var);
1270 
1271  bestbound = SCIPvarGetBestRootSol(var);
1272 
1273  /* using global reduced costs, the two factors yield a nonnegative score within tolerances */
1274  assert(SCIPisDualfeasZero(scip, redcost)
1275  || (SCIPisDualfeasNegative(scip, redcost) && ! SCIPisFeasPositive(scip, refsolval - bestbound))
1276  || (SCIPisDualfeasPositive(scip, redcost) && ! SCIPisFeasNegative(scip, refsolval - bestbound)));
1277  }
1278  else
1279  {
1280  /* this can be safely asserted here, since the heuristic would not reach this point, otherwise */
1281  assert(SCIPhasCurrentNodeLP(scip));
1282  assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL);
1283 
1284  redcost = SCIPgetVarRedcost(scip, var);
1285 
1286  bestbound = SCIPvarGetLPSol(var);
1287  }
1288 
1289  assert(! SCIPisInfinity(scip, REALABS(bestbound)));
1290  assert(SCIPisDualfeasZero(scip, redcost) || SCIPisFeasIntegral(scip, bestbound));
1291 
1292  score = redcost * (refsolval - bestbound);
1293 
1294  /* max out numerical inaccuracies from global scores */
1295  if( ! uselocalredcost )
1296  score = MAX(score, 0.0);
1297 
1298  return score;
1299 }
1300 
1301 /** get the pseudo cost score of this variable with respect to the reference solution */
1302 static
1304  SCIP* scip, /**< SCIP data structure */
1305  SCIP_VAR* var, /**< the variable for which the score should be computed */
1306  SCIP_Real refsolval /**< solution value in reference solution */
1307  )
1308 {
1309  SCIP_Real rootsolval;
1310 
1311  assert(scip != NULL);
1312  assert(var != NULL);
1313 
1314  /* variables that aren't LP columns have no pseudocost score */
1316  return 0.0;
1317 
1318  rootsolval = SCIPvarGetRootSol(var);
1319 
1320  /* the score is 0.0 if the values are equal */
1321  if( SCIPisEQ(scip, rootsolval, refsolval) )
1322  return 0.0;
1323  else
1324  return SCIPgetVarPseudocostVal(scip, var, refsolval - rootsolval);
1325 }
1326 
1327 /** add variable and solution value to buffer data structure for variable fixings. The method checks if
1328  * the value still lies within the variable bounds. The value stays unfixed otherwise.
1329  */
1330 static
1332  SCIP* scip, /**< SCIP data structure */
1333  SCIP_VAR* var, /**< (source) SCIP variable that should be added to the buffer */
1334  SCIP_Real val, /**< fixing value for this variable */
1335  SCIP_VAR** varbuf, /**< variable buffer to store variables that should be fixed */
1336  SCIP_Real* valbuf, /**< value buffer to store fixing values */
1337  int* nfixings, /**< pointer to number of fixed buffer variables, will be increased by 1 */
1338  SCIP_Bool integer /**< is this an integer variable? */
1339  )
1340 {
1341  assert(SCIPisFeasIntegral(scip, val) || ! SCIPvarIsIntegral(var));
1342  assert(*nfixings < SCIPgetNVars(scip));
1343 
1344  /* round the value to its nearest integer */
1345  if( integer )
1346  val = SCIPfloor(scip, val + 0.5);
1347 
1348  /* only add fixing if it is still valid within the global variable bounds. Invalidity
1349  * of this solution value may come from a dual reduction that was performed after the solution from which
1350  * this value originated was found
1351  */
1352  if( SCIPvarGetLbGlobal(var) <= val && val <= SCIPvarGetUbGlobal(var) )
1353  {
1354  varbuf[*nfixings] = var;
1355  valbuf[*nfixings] = val;
1356  ++(*nfixings);
1357  }
1358 }
1359 
1360 /** query neighborhood for a reference solution for further fixings */
1361 static
1363  SCIP* scip, /**< SCIP data structure */
1364  NH* neighborhood, /**< ALNS neighborhood data structure */
1365  SCIP_SOL** solptr /**< solution pointer */
1366  )
1367 {
1368  assert(solptr != NULL);
1369  assert(scip != NULL);
1370  assert(neighborhood != NULL);
1371 
1372  *solptr = NULL;
1373  if( neighborhood->nhrefsol != NULL )
1374  {
1375  SCIP_RESULT result;
1376  SCIP_CALL( neighborhood->nhrefsol(scip, neighborhood, solptr, &result) );
1377 
1378  if( result == SCIP_DIDNOTFIND )
1379  *solptr = NULL;
1380  else
1381  assert(*solptr != NULL);
1382  }
1383 
1384  return SCIP_OKAY;
1385 }
1386 
1387 /** fix additional variables found in feasible reference solution if the ones that the neighborhood found were not enough
1388  *
1389  * use not always the best solution for the values, but a reference solution provided by the neighborhood itself
1390  *
1391  * @note it may happen that the target fixing rate is not completely reached. This is the case if intermediate,
1392  * dual reductions render the solution values of the reference solution infeasible for
1393  * the current, global variable bounds.
1394  */
1395 static
1397  SCIP* scip, /**< SCIP data structure */
1398  SCIP_HEURDATA* heurdata, /**< heuristic data of the ALNS neighborhood */
1399  SCIP_SOL* refsol, /**< feasible reference solution for more variable fixings */
1400  SCIP_VAR** varbuf, /**< buffer array to store variables to fix */
1401  SCIP_Real* valbuf, /**< buffer array to store fixing values */
1402  int* nfixings, /**< pointer to store the number of fixings */
1403  int ntargetfixings, /**< number of required target fixings */
1404  SCIP_Bool* success /**< pointer to store whether the target fixings have been successfully reached */
1405  )
1406 {
1407  VARPRIO varprio;
1408  SCIP_VAR** vars;
1409  SCIP_Real* redcostscores;
1410  SCIP_Real* pscostscores;
1411  SCIP_Real* solvals;
1412  SCIP_RANDNUMGEN* rng;
1413  SCIP_VAR** unfixedvars;
1414  SCIP_Bool* isfixed;
1415  int* distances;
1416  int* perm;
1417  SCIP_Real* randscores;
1418  int nbinvars;
1419  int nintvars;
1420  int nbinintvars;
1421  int nvars;
1422  int b;
1423  int nvarstoadd;
1424  int nunfixedvars;
1425 
1426  assert(scip != NULL);
1427  assert(varbuf != NULL);
1428  assert(nfixings != NULL);
1429  assert(success != NULL);
1430  assert(heurdata != NULL);
1431  assert(refsol != NULL);
1432 
1433  *success = FALSE;
1434 
1435  /* if the user parameter forbids more fixings, return immediately */
1436  if( ! heurdata->domorefixings )
1437  return SCIP_OKAY;
1438 
1439  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
1440 
1441  nbinintvars = nbinvars + nintvars;
1442 
1443  if( ntargetfixings >= nbinintvars )
1444  return SCIP_OKAY;
1445 
1446  /* determine the number of required additional fixings */
1447  nvarstoadd = ntargetfixings - *nfixings;
1448  if( nvarstoadd == 0 )
1449  return SCIP_OKAY;
1450 
1451  varprio.usedistances = heurdata->usedistances && (*nfixings >= 1);
1452  varprio.useredcost = heurdata->useredcost;
1453  varprio.usepscost = heurdata->usepscost;
1454  varprio.scip = scip;
1455  rng = SCIPbanditGetRandnumgen(heurdata->bandit);
1456  assert(rng != NULL);
1457 
1458  SCIP_CALL( SCIPallocBufferArray(scip, &randscores, nbinintvars) );
1459  SCIP_CALL( SCIPallocBufferArray(scip, &perm, nbinintvars) );
1460  SCIP_CALL( SCIPallocBufferArray(scip, &distances, nvars) );
1461  SCIP_CALL( SCIPallocBufferArray(scip, &redcostscores, nbinintvars) );
1462  SCIP_CALL( SCIPallocBufferArray(scip, &solvals, nbinintvars) );
1463  SCIP_CALL( SCIPallocBufferArray(scip, &isfixed, nbinintvars) );
1464  SCIP_CALL( SCIPallocBufferArray(scip, &unfixedvars, nbinintvars) );
1465  SCIP_CALL( SCIPallocBufferArray(scip, &pscostscores, nbinintvars) );
1466 
1467  /* initialize variable graph distances from already fixed variables */
1468  if( varprio.usedistances )
1469  {
1470  SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, NULL, varbuf, *nfixings, distances, INT_MAX, INT_MAX, ntargetfixings) );
1471  }
1472  else
1473  {
1474  /* initialize all equal distances to make them irrelevant */
1475  BMSclearMemoryArray(distances, nbinintvars);
1476  }
1477 
1478  BMSclearMemoryArray(isfixed, nbinintvars);
1479 
1480  /* mark binary and integer variables if they are fixed */
1481  for( b = 0; b < *nfixings; ++b )
1482  {
1483  int probindex;
1484 
1485  assert(varbuf[b] != NULL);
1486  probindex = SCIPvarGetProbindex(varbuf[b]);
1487  assert(probindex >= 0);
1488 
1489  if( probindex < nbinintvars )
1490  isfixed[probindex] = TRUE;
1491  }
1492 
1493  SCIP_CALL( SCIPgetSolVals(scip, refsol, nbinintvars, vars, solvals) );
1494 
1495  /* assign scores to unfixed every discrete variable of the problem */
1496  nunfixedvars = 0;
1497  for( b = 0; b < nbinintvars; ++b )
1498  {
1499  SCIP_VAR* var = vars[b];
1500 
1501  /* filter fixed variables */
1502  if( isfixed[b] )
1503  continue;
1504 
1505  /* filter variables with a solution value outside its global bounds */
1506  if( solvals[b] < SCIPvarGetLbGlobal(var) - 0.5 || solvals[b] > SCIPvarGetUbGlobal(var) + 0.5 )
1507  continue;
1508 
1509  redcostscores[nunfixedvars] = getVariableRedcostScore(scip, var, solvals[b], heurdata->uselocalredcost);
1510  pscostscores[nunfixedvars] = getVariablePscostScore(scip, var, solvals[b]);
1511 
1512  unfixedvars[nunfixedvars] = var;
1513  perm[nunfixedvars] = nunfixedvars;
1514  randscores[nunfixedvars] = SCIPrandomGetReal(rng, 0.0, 1.0);
1515 
1516  /* these assignments are based on the fact that nunfixedvars <= b */
1517  solvals[nunfixedvars] = solvals[b];
1518  distances[nunfixedvars] = distances[b];
1519 
1520  SCIPdebugMsg(scip, "Var <%s> scores: dist %3d, red cost %15.9g, pscost %15.9g rand %6.4f\n",
1521  SCIPvarGetName(var), distances[nunfixedvars], redcostscores[nunfixedvars],
1522  pscostscores[nunfixedvars], randscores[nunfixedvars]);
1523 
1524  nunfixedvars++;
1525  }
1526 
1527  /* use selection algorithm (order of the variables does not matter) for quickly completing the fixing */
1528  varprio.randscores = randscores;
1529  varprio.distances = distances;
1530  varprio.redcostscores = redcostscores;
1531  varprio.pscostscores = pscostscores;
1532 
1533  nvarstoadd = MIN(nunfixedvars, nvarstoadd);
1534 
1535  /* select the first nvarstoadd many variables according to the score */
1536  if( nvarstoadd < nunfixedvars )
1537  SCIPselectInd(perm, sortIndCompAlns, &varprio, nvarstoadd, nunfixedvars);
1538 
1539  /* loop over the first elements of the selection defined in permutation. They represent the best variables */
1540  for( b = 0; b < nvarstoadd; ++b )
1541  {
1542  int permindex = perm[b];
1543  assert(permindex >= 0);
1544  assert(permindex < nunfixedvars);
1545 
1546  tryAdd2variableBuffer(scip, unfixedvars[permindex], solvals[permindex], varbuf, valbuf, nfixings, TRUE);
1547  }
1548 
1549  *success = TRUE;
1550 
1551  /* free buffer arrays */
1552  SCIPfreeBufferArray(scip, &pscostscores);
1553  SCIPfreeBufferArray(scip, &unfixedvars);
1554  SCIPfreeBufferArray(scip, &isfixed);
1555  SCIPfreeBufferArray(scip, &solvals);
1556  SCIPfreeBufferArray(scip, &redcostscores);
1557  SCIPfreeBufferArray(scip, &distances);
1558  SCIPfreeBufferArray(scip, &perm);
1559  SCIPfreeBufferArray(scip, &randscores);
1560 
1561  return SCIP_OKAY;
1562 }
1563 
1564 /** create the bandit algorithm for the heuristic depending on the user parameter */
1565 static
1567  SCIP* scip, /**< SCIP data structure */
1568  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
1569  SCIP_Real* priorities, /**< call priorities for active neighborhoods */
1570  unsigned int initseed /**< initial random seed */
1571  )
1572 {
1573  switch (heurdata->banditalgo)
1574  {
1575  case 'u':
1576  SCIP_CALL( SCIPcreateBanditUcb(scip, &heurdata->bandit, priorities,
1577  heurdata->ucb_alpha, heurdata->nactiveneighborhoods, initseed) );
1578  break;
1579 
1580  case 'e':
1581  SCIP_CALL( SCIPcreateBanditExp3(scip, &heurdata->bandit, priorities,
1582  heurdata->exp3_gamma, heurdata->exp3_beta, heurdata->nactiveneighborhoods, initseed) );
1583  break;
1584 
1585  case 'g':
1586  SCIP_CALL( SCIPcreateBanditEpsgreedy(scip, &heurdata->bandit, priorities,
1587  heurdata->epsgreedy_eps, FALSE, 0.9, 0, heurdata->nactiveneighborhoods, initseed) );
1588  break;
1589 
1590  default:
1591  SCIPerrorMessage("Unknown bandit parameter %c\n", heurdata->banditalgo);
1592  return SCIP_INVALIDDATA;
1593  }
1594 
1595  return SCIP_OKAY;
1596 }
1597 
1598 /*
1599  * Callback methods of primal heuristic
1600  */
1601 
1602 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
1603 static
1604 SCIP_DECL_HEURCOPY(heurCopyAlns)
1605 { /*lint --e{715}*/
1606  assert(scip != NULL);
1607  assert(heur != NULL);
1608  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1609 
1610  /* call inclusion method of primal heuristic */
1611  SCIP_CALL( SCIPincludeHeurAlns(scip) );
1612 
1613  return SCIP_OKAY;
1614 }
1615 
1616 /** unfix some of the variables because there are too many fixed
1617  *
1618  * a variable is ideally unfixed if it is close to other unfixed variables
1619  * and fixing it has a high reduced cost impact
1620  */
1621 static
1623  SCIP* scip, /**< SCIP data structure */
1624  SCIP_HEURDATA* heurdata, /**< heuristic data of the ALNS neighborhood */
1625  SCIP_VAR** varbuf, /**< buffer array to store variables to fix */
1626  SCIP_Real* valbuf, /**< buffer array to store fixing values */
1627  int* nfixings, /**< pointer to store the number of fixings */
1628  int ntargetfixings, /**< number of required target fixings */
1629  SCIP_Bool* success /**< pointer to store whether the target fixings have been successfully reached */
1630  )
1631 {
1632  VARPRIO varprio;
1633  SCIP_Real* redcostscores;
1634  SCIP_Real* pscostscores;
1635  SCIP_Real* randscores;
1636  SCIP_VAR** unfixedvars;
1637  SCIP_VAR** varbufcpy;
1638  SCIP_Real* valbufcpy;
1639  SCIP_Bool* isfixedvar;
1640  SCIP_VAR** vars;
1641  SCIP_RANDNUMGEN* rng;
1642  int* distances;
1643  int* fixeddistances;
1644  int* perm;
1645  int nvars;
1646  int i;
1647  int nbinintvars;
1648  int nunfixed;
1649 
1650  *success = FALSE;
1651 
1652  nbinintvars = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
1653  if( nbinintvars == 0 )
1654  return SCIP_OKAY;
1655 
1656  assert(*nfixings > 0);
1657 
1658  nvars = SCIPgetNVars(scip);
1659  SCIP_CALL( SCIPallocBufferArray(scip, &isfixedvar, nvars) );
1660  SCIP_CALL( SCIPallocBufferArray(scip, &unfixedvars, nbinintvars) );
1661  SCIP_CALL( SCIPallocBufferArray(scip, &distances, nvars) );
1662  SCIP_CALL( SCIPallocBufferArray(scip, &fixeddistances, *nfixings) );
1663  SCIP_CALL( SCIPallocBufferArray(scip, &redcostscores, *nfixings) );
1664  SCIP_CALL( SCIPallocBufferArray(scip, &randscores, *nfixings) );
1665  SCIP_CALL( SCIPallocBufferArray(scip, &perm, *nfixings) );
1666  SCIP_CALL( SCIPallocBufferArray(scip, &pscostscores, *nfixings) );
1667 
1668  SCIP_CALL( SCIPduplicateBufferArray(scip, &varbufcpy, varbuf, *nfixings) );
1669  SCIP_CALL( SCIPduplicateBufferArray(scip, &valbufcpy, valbuf, *nfixings) );
1670 
1671  /*
1672  * collect the unfixed binary and integer variables
1673  */
1674  BMSclearMemoryArray(isfixedvar, nvars);
1675  /* loop over fixed variables and mark their respective positions as fixed */
1676  for( i = 0; i < *nfixings; ++i )
1677  {
1678  int probindex = SCIPvarGetProbindex(varbuf[i]);
1679 
1680  assert(probindex >= 0);
1681 
1682  isfixedvar[probindex] = TRUE;
1683  }
1684 
1685  nunfixed = 0;
1686  vars = SCIPgetVars(scip);
1687  /* collect unfixed binary and integer variables */
1688  for( i = 0; i < nbinintvars; ++i )
1689  {
1690  if( ! isfixedvar[i] )
1691  unfixedvars[nunfixed++] = vars[i];
1692  }
1693 
1694  varprio.usedistances = heurdata->usedistances && nunfixed > 0;
1695 
1696  /* collect distances of all fixed variables from those that are not fixed */
1697  if( varprio.usedistances )
1698  {
1699  SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, NULL, unfixedvars, nunfixed, distances, INT_MAX, INT_MAX, INT_MAX) );
1700 
1701  for( i = 0; i < *nfixings; ++i )
1702  {
1703  int probindex = SCIPvarGetProbindex(varbuf[i]);
1704  if( probindex >= 0 )
1705  fixeddistances[i] = distances[probindex];
1706  }
1707  }
1708  else
1709  {
1710  BMSclearMemoryArray(fixeddistances, *nfixings);
1711  }
1712 
1713  /* collect reduced cost scores of the fixings and assign random scores */
1714  rng = SCIPbanditGetRandnumgen(heurdata->bandit);
1715  for( i = 0; i < *nfixings; ++i )
1716  {
1717  SCIP_VAR* fixedvar = varbuf[i];
1718  SCIP_Real fixval = valbuf[i];
1719 
1720  /* use negative reduced cost and pseudo cost scores to prefer variable fixings with small score */
1721  redcostscores[i] = - getVariableRedcostScore(scip, fixedvar, fixval, heurdata->uselocalredcost);
1722  pscostscores[i] = - getVariablePscostScore(scip, fixedvar, fixval);
1723  randscores[i] = SCIPrandomGetReal(rng, 0.0, 1.0);
1724  perm[i] = i;
1725 
1726  SCIPdebugMsg(scip, "Var <%s> scores: dist %3d, red cost %15.9g, pscost %15.9g rand %6.4f\n",
1727  SCIPvarGetName(fixedvar), fixeddistances[i], redcostscores[i], pscostscores[i], randscores[i]);
1728  }
1729 
1730  varprio.distances = fixeddistances;
1731  varprio.randscores = randscores;
1732  varprio.redcostscores = redcostscores;
1733  varprio.pscostscores = pscostscores;
1734  varprio.useredcost = heurdata->useredcost;
1735  varprio.usepscost = heurdata->usepscost;
1736  varprio.scip = scip;
1737 
1738  /* scores are assigned in such a way that variables with a smaller score should be fixed last */
1739  SCIPselectDownInd(perm, sortIndCompAlns, &varprio, ntargetfixings, *nfixings);
1740 
1741  /* bring the desired variables to the front of the array */
1742  for( i = 0; i < ntargetfixings; ++i )
1743  {
1744  valbuf[i] = valbufcpy[perm[i]];
1745  varbuf[i] = varbufcpy[perm[i]];
1746  }
1747 
1748  *nfixings = ntargetfixings;
1749 
1750  /* free the buffer arrays in reverse order of allocation */
1751  SCIPfreeBufferArray(scip, &valbufcpy);
1752  SCIPfreeBufferArray(scip, &varbufcpy);
1753  SCIPfreeBufferArray(scip, &pscostscores);
1754  SCIPfreeBufferArray(scip, &perm);
1755  SCIPfreeBufferArray(scip, &randscores);
1756  SCIPfreeBufferArray(scip, &redcostscores);
1757  SCIPfreeBufferArray(scip, &fixeddistances);
1758  SCIPfreeBufferArray(scip, &distances);
1759  SCIPfreeBufferArray(scip, &unfixedvars);
1760  SCIPfreeBufferArray(scip, &isfixedvar);
1761 
1762  *success = TRUE;
1763 
1764  return SCIP_OKAY;
1765 }
1766 
1767 /** call variable fixing callback for this neighborhood and orchestrate additional variable fixings, if necessary */
1768 static
1770  SCIP* scip, /**< SCIP data structure */
1771  SCIP_HEURDATA* heurdata, /**< heuristic data of the ALNS neighborhood */
1772  NH* neighborhood, /**< neighborhood data structure */
1773  SCIP_VAR** varbuf, /**< buffer array to keep variables that should be fixed */
1774  SCIP_Real* valbuf, /**< buffer array to keep fixing values */
1775  int* nfixings, /**< pointer to store the number of variable fixings */
1776  SCIP_RESULT* result /**< pointer to store the result of the fixing operation */
1777  )
1778 {
1779  int ntargetfixings;
1780  int nmaxfixings;
1781  int nminfixings;
1782  int nbinintvars;
1783 
1784  assert(scip != NULL);
1785  assert(neighborhood != NULL);
1786  assert(varbuf != NULL);
1787  assert(valbuf != NULL);
1788  assert(nfixings != NULL);
1789  assert(result != NULL);
1790 
1791  *nfixings = 0;
1792 
1793  *result = SCIP_DIDNOTRUN;
1794  ntargetfixings = (int)(neighborhood->fixingrate.targetfixingrate * (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip)));
1795 
1796  if( neighborhood->varfixings != NULL )
1797  {
1798  SCIP_CALL( neighborhood->varfixings(scip, neighborhood, varbuf, valbuf, nfixings, result) );
1799 
1800  if( *result != SCIP_SUCCESS )
1801  return SCIP_OKAY;
1802  }
1803  else if( ntargetfixings == 0 )
1804  {
1805  *result = SCIP_SUCCESS;
1806 
1807  return SCIP_OKAY;
1808  }
1809 
1810  /* compute upper and lower target fixing limits using tolerance parameters */
1811  assert(neighborhood->varfixings == NULL || *result != SCIP_DIDNOTRUN);
1812  nbinintvars = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
1813  ntargetfixings = (int)(neighborhood->fixingrate.targetfixingrate * nbinintvars);
1814  nminfixings = (int)((neighborhood->fixingrate.targetfixingrate - heurdata->fixtol) * nbinintvars);
1815  nminfixings = MAX(nminfixings, 0);
1816  nmaxfixings = (int)((neighborhood->fixingrate.targetfixingrate + heurdata->unfixtol) * nbinintvars);
1817  nmaxfixings = MIN(nmaxfixings, nbinintvars);
1818 
1819  SCIPdebugMsg(scip, "Neighborhood Fixings/Target: %d / %d <= %d <= %d\n",*nfixings, nminfixings, ntargetfixings, nmaxfixings);
1820 
1821  /* if too few fixings, use a strategy to select more variable fixings: randomized, LP graph, ReducedCost based, mix */
1822  if( (*result == SCIP_SUCCESS || *result == SCIP_DIDNOTRUN) && (*nfixings < nminfixings) )
1823  {
1824  SCIP_Bool success;
1825  SCIP_SOL* refsol;
1826 
1827  /* get reference solution from neighborhood */
1828  SCIP_CALL( neighborhoodGetRefsol(scip, neighborhood, &refsol) );
1829 
1830  /* try to fix more variables based on the reference solution */
1831  if( refsol != NULL )
1832  {
1833  SCIP_CALL( alnsFixMoreVariables(scip, heurdata, refsol, varbuf, valbuf, nfixings, ntargetfixings, &success) );
1834  }
1835  else
1836  success = FALSE;
1837 
1838  if( success )
1839  *result = SCIP_SUCCESS;
1840  else if( *result == SCIP_SUCCESS )
1841  *result = SCIP_DIDNOTFIND;
1842  else
1843  *result = SCIP_DIDNOTRUN;
1844 
1845  SCIPdebugMsg(scip, "After additional fixings: %d / %d\n",*nfixings, ntargetfixings);
1846  }
1847  else if( (SCIP_Real)(*nfixings) > nmaxfixings )
1848  {
1849  SCIP_Bool success;
1850 
1851  SCIP_CALL( alnsUnfixVariables(scip, heurdata, varbuf, valbuf, nfixings, ntargetfixings, &success) );
1852 
1853  assert(success);
1854  *result = SCIP_SUCCESS;
1855  SCIPdebugMsg(scip, "Unfixed variables, fixed variables remaining: %d\n", ntargetfixings);
1856  }
1857  else
1858  {
1859  SCIPdebugMsg(scip, "No additional fixings performed\n");
1860  }
1861 
1862  return SCIP_OKAY;
1863 }
1864 
1865 /** change the sub-SCIP by restricting variable domains, changing objective coefficients, or adding constraints */
1866 static
1868  SCIP* sourcescip, /**< source SCIP data structure */
1869  SCIP* targetscip, /**< target SCIP data structure */
1870  NH* neighborhood, /**< neighborhood */
1871  SCIP_VAR** targetvars, /**< array of target SCIP variables aligned with source SCIP variables */
1872  int* ndomchgs, /**< pointer to store the number of variable domain changes */
1873  int* nchgobjs, /**< pointer to store the number of changed objective coefficients */
1874  int* naddedconss, /**< pointer to store the number of added constraints */
1875  SCIP_Bool* success /**< pointer to store whether the sub-SCIP has been successfully modified */
1876  )
1877 {
1878  assert(sourcescip != NULL);
1879  assert(targetscip != NULL);
1880  assert(neighborhood != NULL);
1881  assert(targetvars != NULL);
1882  assert(ndomchgs != NULL);
1883  assert(nchgobjs != NULL);
1884  assert(naddedconss != NULL);
1885  assert(success != NULL);
1886 
1887  *success = FALSE;
1888  *ndomchgs = 0;
1889  *nchgobjs = 0;
1890  *naddedconss = 0;
1891 
1892  /* call the change sub-SCIP callback of the neighborhood */
1893  if( neighborhood->changesubscip != NULL )
1894  {
1895  SCIP_CALL( neighborhood->changesubscip(sourcescip, targetscip, targetvars, ndomchgs, nchgobjs, naddedconss, success) );
1896  }
1897  else
1898  {
1899  *success = TRUE;
1900  }
1901 
1902  return SCIP_OKAY;
1903 }
1904 
1905 /** set sub-SCIP solving limits */
1906 static
1908  SCIP* subscip, /**< SCIP data structure */
1909  SOLVELIMITS* solvelimits /**< pointer to solving limits data structure */
1910  )
1911 {
1912  assert(subscip != NULL);
1913  assert(solvelimits != NULL);
1914 
1915  assert(solvelimits->nodelimit >= solvelimits->stallnodes);
1916 
1917  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", solvelimits->nodelimit) );
1918  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", solvelimits->stallnodes));
1919  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", solvelimits->timelimit) );
1920  SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", solvelimits->memorylimit) );
1921 
1922  return SCIP_OKAY;
1923 }
1924 
1925 /** determine limits for a sub-SCIP */
1926 static
1928  SCIP* scip, /**< SCIP data structure */
1929  SCIP_HEUR* heur, /**< this heuristic */
1930  SOLVELIMITS* solvelimits, /**< pointer to solving limits data structure */
1931  SCIP_Bool* runagain /**< can we solve another sub-SCIP with these limits */
1932  )
1933 {
1934  SCIP_HEURDATA* heurdata;
1935  SCIP_Real initfactor;
1936  SCIP_Real nodesquot;
1937 
1938  assert(scip != NULL);
1939  assert(heur != NULL);
1940  assert(solvelimits != NULL);
1941  assert(runagain != NULL);
1942 
1943  heurdata = SCIPheurGetData(heur);
1944 
1945  /* check whether there is enough time and memory left */
1946  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &solvelimits->timelimit) );
1947  if( ! SCIPisInfinity(scip, solvelimits->timelimit) )
1948  solvelimits->timelimit -= SCIPgetSolvingTime(scip);
1949  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &solvelimits->memorylimit) );
1950 
1951  /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
1952  if( ! SCIPisInfinity(scip, solvelimits->memorylimit) )
1953  {
1954  solvelimits->memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
1955  solvelimits->memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
1956  }
1957 
1958  /* abort if no time is left or not enough memory to create a copy of SCIP, including external memory usage */
1959  if( solvelimits->timelimit <= 0.0 || solvelimits->memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 )
1960  *runagain = FALSE;
1961 
1962  nodesquot = heurdata->nodesquot;
1963 
1964  /* if the heuristic is used to measure all rewards, it will always be penalized here */
1965  if( heurdata->rewardfile == NULL )
1966  nodesquot *= (SCIPheurGetNBestSolsFound(heur) + 1.0)/(SCIPheurGetNCalls(heur) + 1.0);
1967 
1968  /* calculate the search node limit of the heuristic */
1969  solvelimits->stallnodes = (SCIP_Longint)(nodesquot * SCIPgetNNodes(scip));
1970  solvelimits->stallnodes += heurdata->nodesoffset;
1971  solvelimits->stallnodes -= heurdata->usednodes;
1972  solvelimits->stallnodes -= 100 * SCIPheurGetNCalls(heur);
1973  solvelimits->stallnodes = MIN(heurdata->maxnodes, solvelimits->stallnodes);
1974 
1975  /* use a smaller budget if not all neighborhoods have been initialized yet */
1976  assert(heurdata->ninitneighborhoods >= 0);
1977  initfactor = (heurdata->nactiveneighborhoods - heurdata->ninitneighborhoods + 1.0) / (heurdata->nactiveneighborhoods + 1.0);
1978  solvelimits->stallnodes = (SCIP_Longint)(solvelimits->stallnodes * initfactor);
1979  solvelimits->nodelimit = (SCIP_Longint)(heurdata->maxnodes);
1980 
1981  /* check whether we have enough nodes left to call subproblem solving */
1982  if( solvelimits->stallnodes < heurdata->targetnodes )
1983  *runagain = FALSE;
1984 
1985  return SCIP_OKAY;
1986 }
1987 
1988 /** return the bandit algorithm that should be used */
1989 static
1991  SCIP_HEURDATA* heurdata /**< heuristic data of the ALNS neighborhood */
1992  )
1993 {
1994  assert(heurdata != NULL);
1995  return heurdata->bandit;
1996 }
1997 
1998 /** select a neighborhood depending on the selected bandit algorithm */
1999 static
2001  SCIP* scip, /**< SCIP data structure */
2002  SCIP_HEURDATA* heurdata, /**< heuristic data of the ALNS neighborhood */
2003  int* neighborhoodidx /**< pointer to store the selected neighborhood index */
2004  )
2005 {
2006  SCIP_BANDIT* bandit;
2007  assert(scip != NULL);
2008  assert(heurdata != NULL);
2009  assert(neighborhoodidx != NULL);
2010 
2011  *neighborhoodidx = -1;
2012 
2013  bandit = getBandit(heurdata);
2014 
2015  SCIP_CALL( SCIPbanditSelect(bandit, neighborhoodidx) );
2016  assert(*neighborhoodidx >= 0);
2017 
2018  return SCIP_OKAY;
2019 }
2020 
2021 /** Calculate reward based on the selected reward measure */
2022 static
2024  SCIP* scip, /**< SCIP data structure */
2025  SCIP_HEURDATA* heurdata, /**< heuristic data of the ALNS neighborhood */
2026  NH_STATS* runstats, /**< run statistics */
2027  SCIP_Real* rewardptr /**< pointer to store the computed reward */
2028  )
2029 {
2030  SCIP_Real reward = 0.0;
2031  SCIP_Real effort;
2032  int ndiscretevars;
2033 
2034  assert(rewardptr != NULL);
2035  assert(runstats->usednodes >= 0);
2036  assert(runstats->nfixings >= 0);
2037 
2038  effort = runstats->usednodes / 100.0;
2039 
2040  ndiscretevars = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
2041  /* assume that every fixed variable linearly reduces the subproblem complexity */
2042  if( ndiscretevars > 0 )
2043  {
2044  effort = (1.0 - (runstats->nfixings / (SCIP_Real)ndiscretevars)) * effort;
2045  }
2046  assert(rewardptr != NULL);
2047 
2048  /* a positive reward is only assigned if a new incumbent solution was found */
2049  if( runstats->nbestsolsfound > 0 )
2050  {
2051  SCIP_Real bestsolreward;
2052  SCIP_Real closedgapreward;
2053  SCIP_Real rewardcontrol = heurdata->rewardcontrol;
2054 
2055  SCIP_Real lb;
2056  SCIP_Real ub;
2057 
2058  /* the indicator function is simply 1.0 */
2059  bestsolreward = 1.0;
2060 
2061  ub = runstats->newupperbound;
2062  lb = SCIPgetLowerbound(scip);
2063 
2064  /* compute the closed gap reward */
2065  if( SCIPisEQ(scip, ub, lb) || SCIPisInfinity(scip, runstats->oldupperbound) )
2066  closedgapreward = 1.0;
2067  else
2068  {
2069  closedgapreward = (runstats->oldupperbound - ub) / (runstats->oldupperbound - lb);
2070  }
2071 
2072  /* the reward is a convex combination of the best solution reward and the reward for the closed gap */
2073  reward = rewardcontrol * bestsolreward + (1.0 - rewardcontrol) * closedgapreward;
2074 
2075  /* optionally, scale the reward by the involved effort */
2076  if( heurdata->scalebyeffort )
2077  reward /= (effort + 1.0);
2078 
2079  /* add the baseline and rescale the reward into the interval [baseline, 1.0] */
2080  reward = heurdata->rewardbaseline + (1.0 - heurdata->rewardbaseline) * reward;
2081  }
2082  else
2083  {
2084  /* linearly decrease the reward based on the number of nodes spent */
2085  SCIP_Real maxeffort = heurdata->targetnodes;
2086  SCIP_Real usednodes = runstats->usednodes;
2087 
2088  if( ndiscretevars > 0 )
2089  usednodes *= (1.0 - (runstats->nfixings / (SCIP_Real)ndiscretevars));
2090 
2091  reward = heurdata->rewardbaseline - (usednodes) * heurdata->rewardbaseline / maxeffort;
2092  reward = MAX(0.0, reward);
2093  }
2094 
2095  *rewardptr = reward;
2096  return SCIP_OKAY;
2097 }
2098 
2099 /** update internal bandit algorithm statistics for future draws */
2100 static
2102  SCIP* scip, /**< SCIP data structure */
2103  SCIP_HEURDATA* heurdata, /**< heuristic data of the ALNS neighborhood */
2104  SCIP_Real reward, /**< measured reward */
2105  int neighborhoodidx /**< the neighborhood that was chosen */
2106  )
2107 {
2108  SCIP_BANDIT* bandit;
2109  assert(scip != NULL);
2110  assert(heurdata != NULL);
2111  assert(neighborhoodidx >= 0);
2112  assert(neighborhoodidx < heurdata->nactiveneighborhoods);
2113 
2114  bandit = getBandit(heurdata);
2115 
2116  SCIPdebugMsg(scip, "Rewarding bandit algorithm action %d with reward %.2f\n", neighborhoodidx, reward);
2117  SCIP_CALL( SCIPbanditUpdate(bandit, neighborhoodidx, reward) );
2118 
2119  return SCIP_OKAY;
2120 }
2121 
2122 /** set up the sub-SCIP parameters, objective cutoff, and solution limits */
2123 static
2125  SCIP* scip, /**< SCIP data structure */
2126  SCIP* subscip, /**< sub-SCIP data structure */
2127  SCIP_VAR** subvars, /**< array of sub-SCIP variables in the order of the main SCIP */
2128  SOLVELIMITS* solvelimits, /**< pointer to solving limits data structure */
2129  SCIP_HEUR* heur, /**< this heuristic */
2130  SCIP_Bool objchgd /**< did the objective change between the source and the target SCIP? */
2131  )
2132 {
2133  SCIP_HEURDATA* heurdata;
2134  SCIP_Real cutoff;
2135  SCIP_Real upperbound;
2136 
2137  heurdata = SCIPheurGetData(heur);
2138 
2139  /* do not abort subproblem on CTRL-C */
2140  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
2141 
2142  /* disable output to console unless we are in debug mode */
2143  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
2144 
2145  /* disable statistic timing inside sub SCIP */
2146  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
2147 
2148 #ifdef ALNS_SUBSCIPOUTPUT
2149  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
2150  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 1) );
2151  /* enable statistic timing inside sub SCIP */
2152  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", TRUE) );
2153 #endif
2154 
2155  SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->nsolslim) );
2156 
2157  /* forbid recursive call of heuristics and separators solving subMIPs */
2158  if( ! heurdata->usesubscipheurs )
2159  {
2160  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
2161  }
2162 
2163  /* disable cutting plane separation */
2165 
2166  /* disable expensive presolving */
2168 
2169  /* use best estimate node selection */
2170  if( SCIPfindNodesel(subscip, "estimate") != NULL && ! SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
2171  {
2172  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
2173  }
2174 
2175  /* use inference branching */
2176  if( SCIPfindBranchrule(subscip, "inference") != NULL && ! SCIPisParamFixed(subscip, "branching/inference/priority") )
2177  {
2178  SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
2179  }
2180 
2181  /* enable conflict analysis and restrict conflict pool */
2182  if( ! SCIPisParamFixed(subscip, "conflict/enable") )
2183  {
2184  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) );
2185  }
2186  if( ! SCIPisParamFixed(subscip, "conflict/maxstoresize") )
2187  {
2188  SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) );
2189  }
2190 
2191  /* speed up sub-SCIP by not checking dual LP feasibility */
2192  SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
2193 
2194  /* employ a limit on the number of enforcement rounds in the quadratic constraint handlers; this fixes the issue that
2195  * sometimes the quadratic constraint handler needs hundreds or thousands of enforcement rounds to determine the
2196  * feasibility status of a single node without fractional branching candidates by separation (namely for uflquad
2197  * instances); however, the solution status of the sub-SCIP might get corrupted by this; hence no decutions shall be
2198  * made for the original SCIP
2199  */
2200  if( SCIPfindConshdlr(subscip, "quadratic") != NULL && ! SCIPisParamFixed(subscip, "constraints/quadratic/enfolplimit") )
2201  {
2202  SCIP_CALL( SCIPsetIntParam(subscip, "constraints/quadratic/enfolplimit", 10) );
2203  }
2204 
2205  /* add an objective cutoff */
2206  if( ! SCIPisInfinity(scip, SCIPgetUpperbound(scip)) )
2207  {
2208  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
2209  if( ! SCIPisInfinity(scip, -1.0 * SCIPgetLowerbound(scip)) )
2210  {
2211  cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip)
2212  + heurdata->minimprove * SCIPgetLowerbound(scip);
2213  }
2214  else
2215  {
2216  if( SCIPgetUpperbound(scip) >= 0 )
2217  cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip);
2218  else
2219  cutoff = (1 + heurdata->minimprove) * SCIPgetUpperbound(scip);
2220  }
2221  cutoff = MIN(upperbound, cutoff);
2222 
2223  if( SCIPisObjIntegral(scip) )
2224  cutoff = SCIPfloor(scip, cutoff);
2225 
2226  SCIPdebugMsg(scip, "Sub-SCIP cutoff: %15.9" SCIP_REAL_FORMAT " (%15.9" SCIP_REAL_FORMAT " in original space)\n",
2227  cutoff, SCIPretransformObj(scip, cutoff));
2228 
2229  /* if the objective changed between the source and the target SCIP, encode the cutoff as a constraint */
2230  if( ! objchgd )
2231  {
2232  SCIP_CALL(SCIPsetObjlimit(subscip, cutoff));
2233 
2234  SCIPdebugMsg(scip, "Cutoff added as Objective Limit\n");
2235  }
2236  else
2237  {
2238  SCIP_CONS* objcons;
2239  int nvars;
2240  SCIP_VAR** vars;
2241  int i;
2242 
2243  vars = SCIPgetVars(scip);
2244  nvars = SCIPgetNVars(scip);
2245 
2246  SCIP_CALL( SCIPcreateConsLinear(subscip, &objcons, "objbound_of_origscip", 0, NULL, NULL, -SCIPinfinity(subscip), cutoff,
2247  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
2248  for( i = 0; i < nvars; ++i)
2249  {
2250  if( ! SCIPisFeasZero(subscip, SCIPvarGetObj(vars[i])) )
2251  {
2252  SCIP_CALL( SCIPaddCoefLinear(subscip, objcons, subvars[i], SCIPvarGetObj(vars[i])) );
2253  }
2254  }
2255  SCIP_CALL( SCIPaddCons(subscip, objcons) );
2256  SCIP_CALL( SCIPreleaseCons(subscip, &objcons) );
2257 
2258  SCIPdebugMsg(scip, "Cutoff added as constraint\n");
2259  }
2260  }
2261 
2262  /* set solve limits for sub-SCIP */
2263  SCIP_CALL( setLimits(subscip, solvelimits) );
2264 
2265  /* change random seed of sub-SCIP */
2266  if( heurdata->subsciprandseeds )
2267  {
2268  SCIP_CALL( SCIPsetIntParam(subscip, "randomization/randomseedshift", (int)SCIPheurGetNCalls(heur)) );
2269  }
2270 
2271  SCIPdebugMsg(scip, "Solve Limits: %lld (%lld) nodes (stall nodes), %.1f sec., %d sols\n",
2272  solvelimits->nodelimit, solvelimits->stallnodes, solvelimits->timelimit, heurdata->nsolslim);
2273 
2274  return SCIP_OKAY;
2275 }
2276 
2277 /** execution method of primal heuristic */
2278 static
2279 SCIP_DECL_HEUREXEC(heurExecAlns)
2280 { /*lint --e{715}*/
2281  SCIP_HEURDATA* heurdata;
2282  SCIP_VAR** varbuf;
2283  SCIP_Real* valbuf;
2284  SCIP_VAR** vars;
2285  SCIP_VAR** subvars;
2286  NH_STATS runstats[NNEIGHBORHOODS];
2287  SCIP_STATUS subscipstatus[NNEIGHBORHOODS];
2288  SCIP* subscip = NULL;
2289 
2290  int nfixings;
2291  int nvars;
2292  int neighborhoodidx;
2293  int ntries;
2294  SCIP_Bool tryagain;
2295  NH* neighborhood;
2296  SOLVELIMITS solvelimits;
2297  SCIP_Bool success;
2298  SCIP_Bool run;
2299  SCIP_Bool allrewardsmode;
2300  SCIP_Real rewards[NNEIGHBORHOODS];
2301  int banditidx;
2302  int i;
2303 
2304  heurdata = SCIPheurGetData(heur);
2305  assert(heurdata != NULL);
2306 
2307  *result = SCIP_DIDNOTRUN;
2308 
2309  if( heurdata->nactiveneighborhoods == 0 )
2310  return SCIP_OKAY;
2311 
2312  /* wait for a sufficient number of nodes since last incumbent solution */
2313  if( SCIPgetDepth(scip) > 0 && SCIPgetBestSol(scip) != NULL
2314  && (SCIPgetNNodes(scip) - SCIPsolGetNodenum(SCIPgetBestSol(scip))) < heurdata->waitingnodes )
2315  {
2316  SCIPdebugMsg(scip, "Waiting nodes not satisfied\n");
2317  return SCIP_OKAY;
2318  }
2319 
2320  run = TRUE;
2321  /* check if budget allows a run of the next selected neighborhood */
2322  SCIP_CALL( determineLimits(scip, heur, &solvelimits, &run) );
2323  SCIPdebugMsg(scip, "Budget check: %" SCIP_LONGINT_FORMAT " (%" SCIP_LONGINT_FORMAT ") %s\n", solvelimits.nodelimit, heurdata->targetnodes, run ? "passed" : "must wait");
2324 
2325  if( ! run )
2326  return SCIP_OKAY;
2327 
2328  /* delay the heuristic if local reduced costs should be used for generic variable unfixing */
2329  if( heurdata->uselocalredcost && (nodeinfeasible || ! SCIPhasCurrentNodeLP(scip) || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL) )
2330  {
2331  *result = SCIP_DELAYED;
2332 
2333  return SCIP_OKAY;
2334  }
2335 
2336  allrewardsmode = heurdata->rewardfile != NULL;
2337 
2338  /* apply some other rules for a fair all rewards mode; in normal execution mode, neighborhoods are iterated through */
2339  if( allrewardsmode )
2340  {
2341  /* most neighborhoods require an incumbent solution */
2342  if( SCIPgetNSols(scip) < 2 )
2343  {
2344  SCIPdebugMsg(scip, "Not enough solutions for all rewards mode\n");
2345  return SCIP_OKAY;
2346  }
2347 
2348  /* if the node is infeasible, or has no LP solution, which is required by some neighborhoods
2349  * if we are not in all rewards mode, the neighborhoods delay themselves individually
2350  */
2351  if( nodeinfeasible || ! SCIPhasCurrentNodeLP(scip) || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
2352  {
2353  SCIPdebugMsg(scip, "Delay ALNS heuristic until a feasible node with optimally solved LP relaxation\n");
2354  *result = SCIP_DELAYED;
2355  return SCIP_OKAY;
2356  }
2357  }
2358 
2359  /* use the neighborhood that requested a delay or select the next neighborhood to run based on the selected bandit algorithm */
2360  if( heurdata->currneighborhood >= 0 )
2361  {
2362  assert(! allrewardsmode);
2363  banditidx = heurdata->currneighborhood;
2364  SCIPdebugMsg(scip, "Select delayed neighborhood %d (was delayed %d times)\n", banditidx, heurdata->ndelayedcalls);
2365  }
2366  else
2367  {
2368  SCIP_CALL( selectNeighborhood(scip, heurdata, &banditidx) );
2369  SCIPdebugMsg(scip, "Selected neighborhood %d with bandit algorithm\n", banditidx);
2370  }
2371 
2372  /* in all rewards mode, we simply loop over all heuristics */
2373  if( ! allrewardsmode )
2374  neighborhoodidx = banditidx;
2375  else
2376  neighborhoodidx = 0;
2377 
2378  assert(neighborhoodidx >= 0);
2379  assert(heurdata->nactiveneighborhoods > neighborhoodidx);
2380 
2381  /* allocate memory for variable fixings buffer */
2382  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2383  SCIP_CALL( SCIPallocBufferArray(scip, &varbuf, nvars) );
2384  SCIP_CALL( SCIPallocBufferArray(scip, &valbuf, nvars) );
2385  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
2386 
2387  /* initialize neighborhood statistics for a run */
2388  ntries = 1;
2389  do
2390  {
2391  SCIP_HASHMAP* varmapf;
2392  SCIP_EVENTHDLR* eventhdlr;
2393  SCIP_EVENTDATA eventdata;
2394  int ndomchgs;
2395  int nchgobjs;
2396  int naddedconss;
2397  int v;
2398  SCIP_RESULT fixresult;
2399 
2400  tryagain = FALSE;
2401  neighborhood = heurdata->neighborhoods[neighborhoodidx];
2402  SCIPdebugMsg(scip, "Running '%s' neighborhood %d\n", neighborhood->name, neighborhoodidx);
2403 
2404  initRunStats(scip, &runstats[neighborhoodidx]);
2405  rewards[neighborhoodidx] = 0.0;
2406 
2407  subscipstatus[neighborhoodidx] = SCIP_STATUS_UNKNOWN;
2408  SCIP_CALL( SCIPstartClock(scip, neighborhood->stats.setupclock) );
2409 
2410  /* determine variable fixings and objective coefficients of this neighborhood */
2411  SCIP_CALL( neighborhoodFixVariables(scip, heurdata, neighborhood, varbuf, valbuf, &nfixings, &fixresult) );
2412 
2413  SCIPdebugMsg(scip, "Fix %d/%d variables, result code %d\n", nfixings, nvars,fixresult);
2414 
2415  /* Fixing was not successful, either because the fixing rate was not reached (and no additional variable
2416  * prioritization was used), or the neighborhood requested a delay, e.g., because no LP relaxation solution exists
2417  * at the current node
2418  *
2419  * The ALNS heuristic keeps a delayed neighborhood active and delays itself.
2420  */
2421  if( fixresult != SCIP_SUCCESS )
2422  {
2423  SCIP_CALL( SCIPstopClock(scip, neighborhood->stats.setupclock) );
2424 
2425  /* to determine all rewards, we cannot delay neighborhoods */
2426  if( allrewardsmode )
2427  {
2428  if( ntries == heurdata->nactiveneighborhoods )
2429  break;
2430 
2431  neighborhoodidx = (neighborhoodidx + 1) % heurdata->nactiveneighborhoods;
2432  ntries++;
2433  tryagain = TRUE;
2434 
2435  continue;
2436  }
2437 
2438  /* delay the heuristic along with the selected neighborhood
2439  *
2440  * if the neighborhood has been delayed for too many consecutive calls, the delay is treated as a failure */
2441  if( fixresult == SCIP_DELAYED )
2442  {
2443  if( heurdata->ndelayedcalls > (SCIPheurGetFreq(heur) / 4 + 1) )
2444  {
2445  resetCurrentNeighborhood(heurdata);
2446 
2447  /* use SCIP_DIDNOTFIND to penalize the neighborhood with a bad reward */
2448  fixresult = SCIP_DIDNOTFIND;
2449  }
2450  else if( heurdata->currneighborhood == -1 )
2451  {
2452  heurdata->currneighborhood = neighborhoodidx;
2453  heurdata->ndelayedcalls = 1;
2454  }
2455  else
2456  {
2457  heurdata->ndelayedcalls++;
2458  }
2459  }
2460 
2461  if( fixresult == SCIP_DIDNOTRUN )
2462  {
2463  if( ntries < heurdata->nactiveneighborhoods )
2464  {
2465  SCIP_CALL( updateBanditAlgorithm(scip, heurdata, 0.0, neighborhoodidx) );
2466  SCIP_CALL( selectNeighborhood(scip, heurdata, &neighborhoodidx) );
2467  ntries++;
2468  tryagain = TRUE;
2469 
2470  SCIPdebugMsg(scip, "Neighborhood cannot run -> try next neighborhood %d\n", neighborhoodidx);
2471  continue;
2472  }
2473  else
2474  break;
2475  }
2476 
2477  assert(fixresult == SCIP_DIDNOTFIND || fixresult == SCIP_DELAYED);
2478  *result = fixresult;
2479  break;
2480  }
2481 
2482  *result = SCIP_DIDNOTFIND;
2483 
2484  neighborhood->stats.nfixings += nfixings;
2485  runstats[neighborhoodidx].nfixings = nfixings;
2486 
2487  SCIP_CALL( SCIPcreate(&subscip) );
2488  SCIP_CALL( SCIPhashmapCreate(&varmapf, SCIPblkmem(scip), nvars) );
2489 
2490  /* todo later: run global propagation for this set of fixings */
2491  SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapf, neighborhood->name, varbuf, valbuf, nfixings, FALSE, heurdata->copycuts, &success, NULL) );
2492 
2493  /* store sub-SCIP variables in array for faster access */
2494  for( v = 0; v < nvars; ++v )
2495  {
2496  subvars[v] = (SCIP_VAR*)SCIPhashmapGetImage(varmapf, (void *)vars[v]);
2497  assert(subvars[v] != NULL);
2498  }
2499 
2500  SCIPhashmapFree(&varmapf);
2501 
2502  /* let the neighborhood add additional constraints, or restrict domains */
2503  SCIP_CALL( neighborhoodChangeSubscip(scip, subscip, neighborhood, subvars, &ndomchgs, &nchgobjs, &naddedconss, &success) );
2504 
2505  if( ! success )
2506  {
2507  SCIP_CALL( SCIPstopClock(scip, neighborhood->stats.setupclock) );
2508 
2509  if( ! allrewardsmode || ntries == heurdata->nactiveneighborhoods )
2510  break;
2511 
2512  neighborhoodidx = (neighborhoodidx + 1) % heurdata->nactiveneighborhoods;
2513  ntries++;
2514  tryagain = TRUE;
2515 
2516  SCIP_CALL( SCIPfree(&subscip) );
2517 
2518  continue;
2519  }
2520 
2521  /* set up sub-SCIP parameters */
2522  SCIP_CALL( setupSubScip(scip, subscip, subvars, &solvelimits, heur, nchgobjs > 0) );
2523 
2524  /* copy the necessary data into the event data to create new solutions */
2525  eventdata.nodelimit = solvelimits.nodelimit;
2526  eventdata.lplimfac = heurdata->lplimfac;
2527  eventdata.heur = heur;
2528  eventdata.sourcescip = scip;
2529  eventdata.subvars = subvars;
2530  eventdata.runstats = &runstats[neighborhoodidx];
2531  eventdata.allrewardsmode = allrewardsmode;
2532 
2533  /* include an event handler to transfer solutions into the main SCIP */
2534  SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecAlns, NULL) );
2535 
2536  /* transform the problem before catching the events */
2537  SCIP_CALL( SCIPtransformProb(subscip) );
2538  SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_ALNS, eventhdlr, &eventdata, NULL) );
2539 
2540  SCIP_CALL( SCIPstopClock(scip, neighborhood->stats.setupclock) );
2541 
2542  /* todo alternatively: set up sub-SCIP and run presolving */
2543  /* todo was presolving successful enough regarding fixings? otherwise terminate */
2544 
2545  SCIP_CALL( SCIPstartClock(scip, neighborhood->stats.submipclock) );
2546  /* run sub-SCIP for the given budget, and collect statistics */
2547  SCIP_CALL_ABORT( SCIPsolve(subscip) );
2548 
2549 #ifdef ALNS_SUBSCIPOUTPUT
2551 #endif
2552 
2553  SCIP_CALL( SCIPstopClock(scip, neighborhood->stats.submipclock) );
2554 
2555  /* update statistics based on the sub-SCIP run results */
2556  updateRunStats(scip, &runstats[neighborhoodidx], subscip);
2557  subscipstatus[neighborhoodidx] = SCIPgetStatus(subscip);
2558  SCIPdebugMsg(scip, "Status of sub-SCIP run: %d\n", subscipstatus[neighborhoodidx]);
2559 
2560  SCIP_CALL( getReward(scip, heurdata, &runstats[neighborhoodidx], &rewards[neighborhoodidx]) );
2561 
2562  /* in all rewards mode, continue with the next neighborhood */
2563  if( allrewardsmode && ntries < heurdata->nactiveneighborhoods )
2564  {
2565  neighborhoodidx = (neighborhoodidx + 1) % heurdata->nactiveneighborhoods;
2566  ntries++;
2567  tryagain = TRUE;
2568 
2569  SCIP_CALL( SCIPfree(&subscip) );
2570  }
2571  }
2572  while( tryagain && ! SCIPisStopped(scip) );
2573 
2574  if( subscip != NULL )
2575  {
2576  SCIP_CALL( SCIPfree(&subscip) );
2577  }
2578 
2579  SCIPfreeBufferArray(scip, &subvars);
2580  SCIPfreeBufferArray(scip, &valbuf);
2581  SCIPfreeBufferArray(scip, &varbuf);
2582 
2583  /* update bandit index that may have changed unless we are in all rewards mode */
2584  if( ! allrewardsmode )
2585  banditidx = neighborhoodidx;
2586 
2587  if( *result != SCIP_DELAYED )
2588  {
2589  /* decrease the number of neighborhoods that have not been initialized */
2590  if( neighborhood->stats.nruns == 0 )
2591  --heurdata->ninitneighborhoods;
2592 
2593  heurdata->usednodes += runstats[banditidx].usednodes;
2594 
2595  /* determine the success of this neighborhood, and update the target fixing rate for the next time */
2596  updateNeighborhoodStats(scip, &runstats[banditidx], heurdata->neighborhoods[banditidx], subscipstatus[banditidx]);
2597 
2598  /* adjust the fixing rate for this neighborhood
2599  * make no adjustments in all rewards mode, because this only affects 1 of 8 heuristics
2600  */
2601  if( heurdata->adjustfixingrate && ! allrewardsmode )
2602  {
2603  SCIPdebugMsg(scip, "Update fixing rate: %.2f\n", heurdata->neighborhoods[banditidx]->fixingrate.targetfixingrate);
2604  updateFixingRate(scip, heurdata->neighborhoods[banditidx], subscipstatus[banditidx], &runstats[banditidx]);
2605  SCIPdebugMsg(scip, "New fixing rate: %.2f\n", heurdata->neighborhoods[banditidx]->fixingrate.targetfixingrate);
2606  }
2607  /* similarly, update the minimum improvement for the ALNS heuristic */
2608  if( heurdata->adjustminimprove )
2609  {
2610  SCIPdebugMsg(scip, "Update Minimum Improvement: %.4f\n", heurdata->minimprove);
2611  updateMinimumImprovement(heurdata, subscipstatus[banditidx], &runstats[banditidx]);
2612  SCIPdebugMsg(scip, "--> %.4f\n", heurdata->minimprove);
2613  }
2614 
2615  /* update the target node limit based on the status of the selected algorithm */
2616  if( heurdata->adjusttargetnodes && SCIPheurGetNCalls(heur) >= heurdata->nactiveneighborhoods )
2617  {
2618  updateTargetNodeLimit(heurdata, &runstats[banditidx], subscipstatus[banditidx]);
2619  }
2620 
2621  /* update the bandit algorithm by the measured reward */
2622  SCIP_CALL( updateBanditAlgorithm(scip, heurdata, rewards[banditidx], banditidx) );
2623 
2624  resetCurrentNeighborhood(heurdata);
2625  }
2626 
2627  /* write single, measured rewards and the bandit index to the reward file */
2628  if( allrewardsmode )
2629  {
2630  for( i = 0; i < heurdata->nactiveneighborhoods; ++i )
2631  {
2632  fprintf(heurdata->rewardfile, "%.4f,", rewards[i]);
2633  }
2634  fprintf(heurdata->rewardfile, "%d\n", banditidx);
2635  }
2636 
2637  return SCIP_OKAY;
2638 }
2639 
2640 /** callback to collect variable fixings of RENS */
2641 static
2642 DECL_VARFIXINGS(varFixingsRens)
2643 { /*lint --e{715}*/
2644  int nbinvars;
2645  int nintvars;
2646  SCIP_VAR** vars;
2647  int i;
2648  assert(scip != NULL);
2649  assert(varbuf != NULL);
2650  assert(nfixings != NULL);
2651  assert(valbuf != NULL);
2652 
2653  *result = SCIP_DELAYED;
2654 
2655  if( ! SCIPhasCurrentNodeLP(scip) )
2656  return SCIP_OKAY;
2658  return SCIP_OKAY;
2659 
2660  *result = SCIP_DIDNOTRUN;
2661 
2662  /* get variable information */
2663  SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
2664 
2665  /* return if no binary or integer variables are present */
2666  if( nbinvars + nintvars == 0 )
2667  return SCIP_OKAY;
2668 
2669  /* loop over binary and integer variables; determine those that should be fixed in the sub-SCIP */
2670  for( i = 0; i < nbinvars + nintvars; ++i )
2671  {
2672  SCIP_VAR* var = vars[i];
2673  SCIP_Real lpsolval = SCIPgetSolVal(scip, NULL, var);
2674  assert((i < nbinvars && SCIPvarIsBinary(var)) || (i >= nbinvars && SCIPvarIsIntegral(var)));
2675 
2676  /* fix all binary and integer variables with integer LP solution value */
2677  if( SCIPisFeasIntegral(scip, lpsolval) )
2678  tryAdd2variableBuffer(scip, var, lpsolval, varbuf, valbuf, nfixings, TRUE);
2679  }
2680 
2681  *result = SCIP_SUCCESS;
2682 
2683  return SCIP_OKAY;
2684 }
2685 
2686 /** callback for RENS subproblem changes */
2687 static
2688 DECL_CHANGESUBSCIP(changeSubscipRens)
2689 { /*lint --e{715}*/
2690  SCIP_VAR** vars;
2691  int nintvars;
2692  int nbinvars;
2693  int i;
2694 
2695  assert(SCIPhasCurrentNodeLP(sourcescip));
2696  assert(SCIPgetLPSolstat(sourcescip) == SCIP_LPSOLSTAT_OPTIMAL);
2697 
2698  /* get variable information */
2699  SCIP_CALL( SCIPgetVarsData(sourcescip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
2700 
2701  /* restrict bounds of integer variables with fractional solution value */
2702  for( i = nbinvars; i < nbinvars + nintvars; ++i )
2703  {
2704  SCIP_VAR* var = vars[i];
2705  SCIP_Real lpsolval = SCIPgetSolVal(sourcescip, NULL, var);
2706 
2707  if( ! SCIPisFeasIntegral(sourcescip, lpsolval) )
2708  {
2709  SCIP_Real newlb = SCIPfloor(sourcescip, lpsolval);
2710  SCIP_Real newub = newlb + 1.0;
2711 
2712  /* only count this as a domain change if the new lower and upper bound are a further restriction */
2713  if( newlb > SCIPvarGetLbGlobal(subvars[i]) + 0.5 || newub < SCIPvarGetUbGlobal(subvars[i]) - 0.5 )
2714  {
2715  SCIP_CALL( SCIPchgVarLbGlobal(targetscip, subvars[i], newlb) );
2716  SCIP_CALL( SCIPchgVarUbGlobal(targetscip, subvars[i], newub) );
2717  (*ndomchgs)++;
2718  }
2719  }
2720  }
2721 
2722  *success = TRUE;
2723 
2724  return SCIP_OKAY;
2725 }
2726 
2727 /** collect fixings by matching solution values in a collection of solutions for all binary and integer variables,
2728  * or for a custom set of variables
2729  */
2730 static
2732  SCIP* scip, /**< SCIP data structure */
2733  SCIP_SOL** sols, /**< array of 2 or more solutions. It is okay for the array to contain one element
2734  * equal to NULL to represent the current LP solution */
2735  int nsols, /**< number of solutions in the array */
2736  SCIP_VAR** vars, /**< variable array for which solution values must agree */
2737  int nvars, /**< number of variables, or -1 for all binary and integer variables */
2738  SCIP_VAR** varbuf, /**< buffer storage for variable fixings */
2739  SCIP_Real* valbuf, /**< buffer storage for fixing values */
2740  int* nfixings /**< pointer to store the number of fixings */
2741  )
2742 {
2743  int v;
2744  int nbinintvars;
2745  SCIP_SOL* firstsol;
2746 
2747  assert(scip != NULL);
2748  assert(sols != NULL);
2749  assert(nsols >= 2);
2750  assert(varbuf != NULL);
2751  assert(valbuf != NULL);
2752  assert(nfixings != NULL);
2753  assert(*nfixings == 0);
2754 
2755  if( nvars == -1 || vars == NULL )
2756  {
2757  int nbinvars;
2758  int nintvars;
2759  SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
2760  nbinintvars = nbinvars + nintvars;
2761  nvars = nbinintvars;
2762  }
2763  firstsol = sols[0];
2764  assert(nvars > 0);
2765 
2766  /* loop over integer and binary variables and check if their solution values match in all solutions */
2767  for( v = 0; v < nvars; ++v )
2768  {
2769  SCIP_Real solval;
2770  SCIP_VAR* var;
2771  int s;
2772 
2773  var = vars[v];
2774  assert((v < SCIPgetNBinVars(scip) && SCIPvarIsBinary(var)) || (v >= SCIPgetNBinVars(scip) && SCIPvarIsIntegral(var)));
2775  solval = SCIPgetSolVal(scip, firstsol, var);
2776 
2777  /* determine if solution values match in all given solutions */
2778  for( s = 1; s < nsols; ++s )
2779  {
2780  SCIP_Real solval2 = SCIPgetSolVal(scip, sols[s], var);
2781  if( ! SCIPisEQ(scip, solval, solval2) )
2782  break;
2783  }
2784 
2785  /* if we did not break early, all solutions agree on the solution value of this variable */
2786  if( s == nsols )
2787  {
2788  tryAdd2variableBuffer(scip, var, solval, varbuf, valbuf, nfixings, TRUE);
2789  }
2790  }
2791 
2792  return SCIP_OKAY;
2793 }
2794 
2795 /** callback to collect variable fixings of RINS */
2796 static
2797 DECL_VARFIXINGS(varFixingsRins)
2799  /*lint --e{715}*/
2800  int nbinvars;
2801  int nintvars;
2802  SCIP_VAR** vars;
2803  SCIP_SOL* incumbent;
2804  SCIP_SOL* sols[2];
2805  assert(scip != NULL);
2806  assert(varbuf != NULL);
2807  assert(nfixings != NULL);
2808  assert(valbuf != NULL);
2809 
2810  *result = SCIP_DELAYED;
2811 
2812  if( ! SCIPhasCurrentNodeLP(scip) )
2813  return SCIP_OKAY;
2815  return SCIP_OKAY;
2816 
2817  *result = SCIP_DIDNOTRUN;
2818 
2819  incumbent = SCIPgetBestSol(scip);
2820  if( incumbent == NULL )
2821  return SCIP_OKAY;
2822 
2823  if( SCIPsolGetOrigin(incumbent) == SCIP_SOLORIGIN_ORIGINAL )
2824  return SCIP_OKAY;
2825 
2826  /* get variable information */
2827  SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
2828 
2829  /* return if no binary or integer variables are present */
2830  if( nbinvars + nintvars == 0 )
2831  return SCIP_OKAY;
2832 
2833  sols[0] = NULL;
2834  sols[1] = incumbent;
2835 
2836  SCIP_CALL( fixMatchingSolutionValues(scip, sols, 2, vars, nbinvars + nintvars, varbuf, valbuf, nfixings) );
2837 
2838  *result = SCIP_SUCCESS;
2839 
2840  return SCIP_OKAY;
2841 }
2842 
2843 /** initialization callback for crossover when a new problem is read */
2844 static
2845 DECL_NHINIT(nhInitCrossover)
2846 { /*lint --e{715}*/
2847  DATA_CROSSOVER* data;
2848 
2849  data = neighborhood->data.crossover;
2850  assert(data != NULL);
2851 
2852  if( data->rng != NULL )
2853  SCIPfreeRandom(scip, &data->rng);
2854 
2855  data->selsol = NULL;
2856 
2857  SCIP_CALL( SCIPcreateRandom(scip, &data->rng, CROSSOVERSEED + (unsigned int)SCIPgetNVars(scip), TRUE) );
2858 
2859  return SCIP_OKAY;
2860 }
2861 
2862 /** deinitialization callback for crossover when exiting a problem */
2863 static
2864 DECL_NHEXIT(nhExitCrossover)
2865 { /*lint --e{715}*/
2866  DATA_CROSSOVER* data;
2867  data = neighborhood->data.crossover;
2868 
2869  assert(neighborhood != NULL);
2870  assert(data->rng != NULL);
2871 
2872  SCIPfreeRandom(scip, &data->rng);
2873 
2874  return SCIP_OKAY;
2875 }
2876 
2877 /** deinitialization callback for crossover before SCIP is freed */
2878 static
2879 DECL_NHFREE(nhFreeCrossover)
2880 { /*lint --e{715}*/
2881  assert(neighborhood->data.crossover != NULL);
2882  SCIPfreeBlockMemory(scip, &neighborhood->data.crossover);
2883 
2884  return SCIP_OKAY;
2885 }
2886 
2887 /** callback to collect variable fixings of crossover */
2888 static
2889 DECL_VARFIXINGS(varFixingsCrossover)
2890 { /*lint --e{715}*/
2891  DATA_CROSSOVER* data;
2892  SCIP_RANDNUMGEN* rng;
2893  SCIP_SOL** sols;
2894  SCIP_SOL** scipsols;
2895  int nsols;
2896  int lastdraw;
2897  assert(scip != NULL);
2898  assert(varbuf != NULL);
2899  assert(nfixings != NULL);
2900  assert(valbuf != NULL);
2901 
2902  data = neighborhood->data.crossover;
2903 
2904  assert(data != NULL);
2905  nsols = data->nsols;
2906  data->selsol = NULL;
2907 
2908  *result = SCIP_DIDNOTRUN;
2909 
2910  /* return if the pool has not enough solutions */
2911  if( nsols > SCIPgetNSols(scip) )
2912  return SCIP_OKAY;
2913 
2914  /* return if no binary or integer variables are present */
2915  if( SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) == 0 )
2916  return SCIP_OKAY;
2917 
2918  rng = data->rng;
2919  lastdraw = SCIPgetNSols(scip);
2920  SCIP_CALL( SCIPallocBufferArray(scip, &sols, nsols) );
2921  scipsols = SCIPgetSols(scip);
2922 
2923  /* draw as many solutions from the pool as required by crossover, biased towards
2924  * better solutions; therefore, the sorting of the solutions by objective is implicitly used
2925  */
2926  while( nsols > 0 )
2927  {
2928  /* no need for randomization anymore, exactly nsols many solutions remain for the selection */
2929  if( lastdraw == nsols )
2930  {
2931  int s;
2932 
2933  /* fill the remaining slots 0,...,nsols - 1 by the solutions at the same places */
2934  for( s = 0; s < nsols; ++s )
2935  sols[s] = scipsols[s];
2936 
2937  nsols = 0;
2938  }
2939  else
2940  {
2941  int nextdraw;
2942 
2943  assert(nsols < lastdraw);
2944 
2945  /* draw from the lastdraw - nsols many solutions nsols - 1, ... lastdraw - 1 such that nsols many solution */
2946  nextdraw = SCIPrandomGetInt(rng, nsols - 1, lastdraw - 1);
2947  assert(nextdraw >= 0);
2948 
2949  sols[nsols - 1] = scipsols[nextdraw];
2950  nsols--;
2951  lastdraw = nextdraw;
2952  }
2953  }
2954 
2955  SCIP_CALL( fixMatchingSolutionValues(scip, sols, data->nsols, NULL, -1, varbuf, valbuf, nfixings) );
2956 
2957  /* store best selected solution as reference solution */
2958  data->selsol = sols[0];
2959  assert(data->selsol != NULL);
2960 
2961  *result = SCIP_SUCCESS;
2962 
2963  SCIPfreeBufferArray(scip, &sols);
2964 
2965  return SCIP_OKAY;
2966 }
2967 
2968 /** callback for crossover reference solution */
2969 static
2970 DECL_NHREFSOL(nhRefsolCrossover)
2971 { /*lint --e{715}*/
2972  DATA_CROSSOVER* data;
2973 
2974  data = neighborhood->data.crossover;
2975 
2976  if( data->selsol != NULL )
2977  {
2978  *solptr = data->selsol;
2979  *result = SCIP_SUCCESS;
2980  }
2981  else
2982  {
2983  *result = SCIP_DIDNOTFIND;
2984  }
2985 
2986  return SCIP_OKAY;
2987 }
2988 
2989 /** initialization callback for mutation when a new problem is read */
2990 static
2991 DECL_NHINIT(nhInitMutation)
2992 { /*lint --e{715}*/
2993  DATA_MUTATION* data;
2994  assert(scip != NULL);
2995  assert(neighborhood != NULL);
2996 
2997  SCIP_CALL( SCIPallocBlockMemory(scip, &neighborhood->data.mutation) );
2998 
2999  data = neighborhood->data.mutation;
3000  assert(data != NULL);
3001 
3002  SCIP_CALL( SCIPcreateRandom(scip, &data->rng, MUTATIONSEED + (unsigned int)SCIPgetNVars(scip), TRUE) );
3003 
3004  return SCIP_OKAY;
3005 }
3006 
3007 /** deinitialization callback for mutation when exiting a problem */
3008 static
3009 DECL_NHEXIT(nhExitMutation)
3010 { /*lint --e{715}*/
3011  DATA_MUTATION* data;
3012  assert(scip != NULL);
3013  assert(neighborhood != NULL);
3014  data = neighborhood->data.mutation;
3015  assert(data != NULL);
3016 
3017  SCIPfreeRandom(scip, &data->rng);
3018 
3019  SCIPfreeBlockMemory(scip, &neighborhood->data.mutation);
3020 
3021  return SCIP_OKAY;
3022 }
3023 
3024 /** callback to collect variable fixings of mutation */
3025 static
3026 DECL_VARFIXINGS(varFixingsMutation)
3027 { /*lint --e{715}*/
3028  SCIP_RANDNUMGEN* rng;
3029 
3030  SCIP_VAR** vars;
3031  SCIP_VAR** varscpy;
3032  int i;
3033  int nvars;
3034  int nbinvars;
3035  int nintvars;
3036  int nbinintvars;
3037  int ntargetfixings;
3038  SCIP_SOL* incumbentsol;
3039  SCIP_Real targetfixingrate;
3040 
3041  assert(scip != NULL);
3042  assert(neighborhood != NULL);
3043  assert(neighborhood->data.mutation != NULL);
3044  assert(neighborhood->data.mutation->rng != NULL);
3045  rng = neighborhood->data.mutation->rng;
3046 
3047  *result = SCIP_DIDNOTRUN;
3048 
3049  /* get the problem variables */
3050  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
3051 
3052  nbinintvars = nbinvars + nintvars;
3053  if( nbinintvars == 0 )
3054  return SCIP_OKAY;
3055 
3056  incumbentsol = SCIPgetBestSol(scip);
3057  if( incumbentsol == NULL )
3058  return SCIP_OKAY;
3059 
3060  targetfixingrate = neighborhood->fixingrate.targetfixingrate;
3061  ntargetfixings = (int)(targetfixingrate * nbinintvars) + 1;
3062 
3063  /* don't continue if number of discrete variables is too small to reach target fixing rate */
3064  if( nbinintvars <= ntargetfixings )
3065  return SCIP_OKAY;
3066 
3067  *result = SCIP_DIDNOTFIND;
3068 
3069  /* copy variables into a buffer array */
3070  SCIP_CALL( SCIPduplicateBufferArray(scip, &varscpy, vars, nbinintvars) );
3071 
3072  /* partially perturb the array until the number of target fixings is reached */
3073  for( i = 0; *nfixings < ntargetfixings && i < nbinintvars; ++i )
3074  {
3075  int randint = SCIPrandomGetInt(rng, i, nbinintvars - 1);
3076  assert(randint < nbinintvars);
3077 
3078  if( randint > i )
3079  {
3080  SCIPswapPointers((void**)&varscpy[i], (void**)&varscpy[randint]);
3081  }
3082  /* copy the selected variables and their solution values into the buffer */
3083  tryAdd2variableBuffer(scip, varscpy[i], SCIPgetSolVal(scip, incumbentsol, varscpy[i]), varbuf, valbuf, nfixings, TRUE);
3084  }
3085 
3086  assert(i == nbinintvars || *nfixings == ntargetfixings);
3087 
3088  /* Not reaching the number of target fixings means that there is a significant fraction (at least 1 - targetfixingrate)
3089  * of variables for which the incumbent solution value does not lie within the global bounds anymore. This is a nonsuccess
3090  * for the neighborhood (additional fixings are not possible), which is okay because the incumbent solution is
3091  * significantly outdated
3092  */
3093  if( *nfixings == ntargetfixings )
3094  *result = SCIP_SUCCESS;
3095 
3096  /* free the buffer array */
3097  SCIPfreeBufferArray(scip, &varscpy);
3098 
3099  return SCIP_OKAY;
3100 }
3101 
3102 /** add local branching constraint */
3103 static
3105  SCIP* sourcescip, /**< source SCIP data structure */
3106  SCIP* targetscip, /**< target SCIP data structure */
3107  SCIP_VAR** subvars, /**< array of sub SCIP variables in same order as source SCIP variables */
3108  int distance, /**< right hand side of the local branching constraint */
3109  SCIP_Bool* success, /**< pointer to store of a local branching constraint has been successfully added */
3110  int* naddedconss /**< pointer to increase the number of added constraints */
3111  )
3112 {
3113  int nbinvars;
3114  int i;
3115  SCIP_SOL* referencesol;
3116  SCIP_CONS* localbranchcons;
3117  SCIP_VAR** vars;
3118  SCIP_Real* consvals;
3119  SCIP_Real rhs;
3120 
3121  assert(sourcescip != NULL);
3122  assert(*success == FALSE);
3123 
3124  nbinvars = SCIPgetNBinVars(sourcescip);
3125  vars = SCIPgetVars(sourcescip);
3126 
3127  if( nbinvars <= 3 )
3128  return SCIP_OKAY;
3129 
3130  referencesol = SCIPgetBestSol(sourcescip);
3131  if( referencesol == NULL )
3132  return SCIP_OKAY;
3133 
3134  rhs = (SCIP_Real)distance;
3135  rhs = MAX(rhs, 2.0);
3136 
3137  SCIP_CALL( SCIPallocBufferArray(sourcescip, &consvals, nbinvars) );
3138 
3139  /* loop over binary variables and fill the local branching constraint */
3140  for( i = 0; i < nbinvars; ++i )
3141  {
3142  if( SCIPisEQ(sourcescip, SCIPgetSolVal(sourcescip, referencesol, vars[i]), 0.0) )
3143  consvals[i] = 1.0;
3144  else
3145  {
3146  consvals[i] = -1.0;
3147  rhs -= 1.0;
3148  }
3149  }
3150 
3151  /* create the local branching constraint in the target scip */
3152  SCIP_CALL( SCIPcreateConsBasicLinear(targetscip, &localbranchcons, "localbranch", nbinvars, subvars, consvals, -SCIPinfinity(sourcescip), rhs) );
3153  SCIP_CALL( SCIPaddCons(targetscip, localbranchcons) );
3154  SCIP_CALL( SCIPreleaseCons(targetscip, &localbranchcons) );
3155 
3156  *naddedconss = 1;
3157  *success = TRUE;
3158 
3159  SCIPfreeBufferArray(sourcescip, &consvals);
3160 
3161  return SCIP_OKAY;
3162 }
3163 
3164 /** callback for local branching subproblem changes */
3165 static
3166 DECL_CHANGESUBSCIP(changeSubscipLocalbranching)
3167 { /*lint --e{715}*/
3168 
3169  SCIP_CALL( addLocalBranchingConstraint(sourcescip, targetscip, subvars, (int)(0.2 * SCIPgetNBinVars(sourcescip)), success, naddedconss) );
3170 
3171  return SCIP_OKAY;
3172 }
3173 
3174 /** callback for proximity subproblem changes */
3175 static
3176 DECL_CHANGESUBSCIP(changeSubscipProximity)
3177 { /*lint --e{715}*/
3178  SCIP_SOL* referencesol;
3179  SCIP_VAR** vars;
3180  int nbinvars;
3181  int nintvars;
3182  int nvars;
3183  int i;
3184 
3185  SCIP_CALL( SCIPgetVarsData(sourcescip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
3186 
3187  if( nbinvars == 0 )
3188  return SCIP_OKAY;
3189 
3190  referencesol = SCIPgetBestSol(sourcescip);
3191  if( referencesol == NULL )
3192  return SCIP_OKAY;
3193 
3194  /* loop over binary variables, set objective coefficients based on reference solution in a local branching fashion */
3195  for( i = 0; i < nbinvars; ++i )
3196  {
3197  SCIP_Real newobj;
3198  if( SCIPgetSolVal(sourcescip, referencesol, vars[i]) < 0.5 )
3199  newobj = -1.0;
3200  else
3201  newobj = 1.0;
3202  SCIP_CALL( SCIPchgVarObj(targetscip, subvars[i], newobj) );
3203  }
3204 
3205  /* loop over the remaining variables and change their objective coefficients to 0 */
3206  for( ; i < nvars; ++i )
3207  {
3208  SCIP_CALL( SCIPchgVarObj(targetscip, subvars[i], 0.0) );
3209  }
3210 
3211  *nchgobjs = nvars;
3212  *success = TRUE;
3213 
3214  return SCIP_OKAY;
3215 }
3216 
3217 /** callback for zeroobjective subproblem changes */
3218 static
3219 DECL_CHANGESUBSCIP(changeSubscipZeroobjective)
3220 { /*lint --e{715}*/
3221  SCIP_VAR** vars;
3222  int nvars;
3223  int i;
3224 
3225  assert(*success == FALSE);
3226 
3227  SCIP_CALL( SCIPgetVarsData(sourcescip, &vars, &nvars, NULL, NULL, NULL, NULL) );
3228 
3229  /* do not run if no objective variables are present */
3230  if( SCIPgetNObjVars(sourcescip) == 0 )
3231  return SCIP_OKAY;
3232 
3233  /* loop over the variables and change their objective coefficients to 0 */
3234  for( i = 0; i < nvars; ++i )
3235  {
3236  SCIP_CALL( SCIPchgVarObj(targetscip, subvars[i], 0.0) );
3237  }
3238 
3239  *nchgobjs = nvars;
3240  *success = TRUE;
3241 
3242  return SCIP_OKAY;
3243 }
3244 
3245 /** compute tightened bounds for integer variables depending on how much the LP and the incumbent solution values differ */
3246 static
3248  SCIP* scip, /**< SCIP data structure of the original problem */
3249  SCIP_VAR* var, /**< the variable for which bounds should be computed */
3250  SCIP_Real* lbptr, /**< pointer to store the lower bound in the DINS sub-SCIP */
3251  SCIP_Real* ubptr /**< pointer to store the upper bound in the DINS sub-SCIP */
3252  )
3253 {
3254  SCIP_Real mipsol;
3255  SCIP_Real lpsol;
3256 
3257  SCIP_Real lbglobal;
3258  SCIP_Real ubglobal;
3259  SCIP_SOL* bestsol;
3260 
3261  /* get the bounds for each variable */
3262  lbglobal = SCIPvarGetLbGlobal(var);
3263  ubglobal = SCIPvarGetUbGlobal(var);
3264 
3265  assert(SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER);
3266  /* get the current LP solution for each variable */
3267  lpsol = SCIPvarGetLPSol(var);
3268 
3269  /* get the current MIP solution for each variable */
3270  bestsol = SCIPgetBestSol(scip);
3271  mipsol = SCIPgetSolVal(scip, bestsol, var);
3272 
3273  /* if the solution values differ by 0.5 or more, the variable is rebounded, otherwise it is just copied */
3274  if( REALABS(lpsol - mipsol) >= 0.5 )
3275  {
3276  SCIP_Real range;
3277 
3278  *lbptr = lbglobal;
3279  *ubptr = ubglobal;
3280 
3281  /* create an equally sized range around lpsol for general integers: bounds are lpsol +- (mipsol-lpsol) */
3282  range = 2 * lpsol - mipsol;
3283 
3284  if( mipsol >= lpsol )
3285  {
3286  range = SCIPfeasCeil(scip, range);
3287  *lbptr = MAX(*lbptr, range);
3288 
3289  /* when the bound new upper bound is equal to the current MIP solution, we set both bounds to the integral bound (without eps) */
3290  if( SCIPisFeasEQ(scip, mipsol, *lbptr) )
3291  *ubptr = *lbptr;
3292  else
3293  *ubptr = mipsol;
3294  }
3295  else
3296  {
3297  range = SCIPfeasFloor(scip, range);
3298  *ubptr = MIN(*ubptr, range);
3299 
3300  /* when the bound new upper bound is equal to the current MIP solution, we set both bounds to the integral bound (without eps) */
3301  if( SCIPisFeasEQ(scip, mipsol, *ubptr) )
3302  *lbptr = *ubptr;
3303  else
3304  *lbptr = mipsol;
3305  }
3306 
3307  /* the global domain of variables might have been reduced since incumbent was found: adjust lb and ub accordingly */
3308  *lbptr = MAX(*lbptr, lbglobal);
3309  *ubptr = MIN(*ubptr, ubglobal);
3310  }
3311  else
3312  {
3313  /* the global domain of variables might have been reduced since incumbent was found: adjust it accordingly */
3314  *lbptr = MAX(mipsol, lbglobal);
3315  *ubptr = MIN(mipsol, ubglobal);
3316  }
3317 }
3318 
3319 /** callback to collect variable fixings of DINS */
3320 static
3321 DECL_VARFIXINGS(varFixingsDins)
3323  DATA_DINS* data;
3324  SCIP_SOL* rootlpsol;
3325  SCIP_SOL** sols;
3326  int nsols;
3327  int nmipsols;
3328  int nbinvars;
3329  int nintvars;
3330  SCIP_VAR** vars;
3331  int v;
3332 
3333  data = neighborhood->data.dins;
3334  assert(data != NULL);
3335  nmipsols = SCIPgetNSols(scip);
3336  nmipsols = MIN(nmipsols, data->npoolsols);
3337 
3338  *result = SCIP_DELAYED;
3339 
3341  return SCIP_OKAY;
3342 
3343  *result = SCIP_DIDNOTRUN;
3344 
3345  if( nmipsols == 0 )
3346  return SCIP_OKAY;
3347 
3348  SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
3349 
3350  if( nbinvars + nintvars == 0 )
3351  return SCIP_OKAY;
3352 
3353  SCIP_CALL( SCIPcreateSol(scip, &rootlpsol, NULL) );
3354 
3355  /* save root solution LP values in solution */
3356  for( v = 0; v < nbinvars + nintvars; ++v )
3357  {
3358  SCIP_CALL( SCIPsetSolVal(scip, rootlpsol, vars[v], SCIPvarGetRootSol(vars[v])) );
3359  }
3360 
3361  /* add the node and the root LP solution */
3362  nsols = nmipsols + 2;
3363 
3364  SCIP_CALL( SCIPallocBufferArray(scip, &sols, nsols) );
3365  sols[0] = NULL; /* node LP solution */
3366  sols[1] = rootlpsol;
3367 
3368  /* copy the remaining MIP solutions after the LP solutions */
3369  BMScopyMemoryArray(&sols[2], SCIPgetSols(scip), nmipsols); /*lint !e866*/
3370 
3371  /* 1. Binary variables are fixed if their values agree in all the solutions */
3372  if( nbinvars > 0 )
3373  {
3374  SCIP_CALL( fixMatchingSolutionValues(scip, sols, nsols, vars, nbinvars, varbuf, valbuf, nfixings) );
3375  }
3376 
3377  /* 2. Integer variables are fixed if they have a very low distance between the incumbent and the root LP solution */
3378  for( v = nbinvars; v < nintvars; ++v )
3379  {
3380  SCIP_Real lb;
3381  SCIP_Real ub;
3382  computeIntegerVariableBoundsDins(scip, vars[v], &lb, &ub);
3383 
3384  if( ub - lb < 0.5 )
3385  {
3386  assert(SCIPisFeasIntegral(scip, lb));
3387  tryAdd2variableBuffer(scip, vars[v], lb, varbuf, valbuf, nfixings, TRUE);
3388  }
3389  }
3390 
3391  *result = SCIP_SUCCESS;
3392 
3393  SCIPfreeBufferArray(scip, &sols);
3394 
3395  SCIP_CALL( SCIPfreeSol(scip, &rootlpsol) );
3396 
3397  return SCIP_OKAY;
3398 }
3399 
3400 /** callback for DINS subproblem changes */
3401 static
3402 DECL_CHANGESUBSCIP(changeSubscipDins)
3403 { /*lint --e{715}*/
3404  SCIP_VAR** vars;
3405  int nintvars;
3406  int nbinvars;
3407  int v;
3408 
3409  SCIP_CALL( SCIPgetVarsData(sourcescip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
3410 
3411  /* 1. loop over integer variables and tighten the bounds */
3412  for( v = nbinvars; v < nintvars; ++v )
3413  {
3414  SCIP_Real lb;
3415  SCIP_Real ub;
3416 
3417  computeIntegerVariableBoundsDins(sourcescip, vars[v], &lb, &ub);
3418 
3419  SCIP_CALL( SCIPchgVarLbGlobal(targetscip, subvars[v], lb) );
3420  SCIP_CALL( SCIPchgVarUbGlobal(targetscip, subvars[v], ub) );
3421  ++(*ndomchgs);
3422  }
3423 
3424  /* 2. add local branching constraint for binary variables */
3425  SCIP_CALL( addLocalBranchingConstraint(sourcescip, targetscip, subvars, (int)(0.1 * SCIPgetNBinVars(sourcescip)), success, naddedconss) );
3426 
3427  *success = TRUE;
3428 
3429  return SCIP_OKAY;
3430 }
3431 
3432 /** deinitialization callback for DINS before SCIP is freed */
3433 static
3434 DECL_NHFREE(nhFreeDins)
3436  assert(neighborhood->data.dins != NULL);
3437 
3438  SCIPfreeBlockMemory(scip, &neighborhood->data.dins);
3439 
3440  return SCIP_OKAY;
3441 }
3442 
3443 /** callback that returns the incumbent solution as a reference point */
3444 static
3445 DECL_NHREFSOL(nhRefsolIncumbent)
3446 { /*lint --e{715}*/
3447  assert(scip != NULL);
3448 
3449  if( SCIPgetBestSol(scip) != NULL )
3450  {
3451  *result = SCIP_SUCCESS;
3452  *solptr = SCIPgetBestSol(scip);
3453  }
3454  else
3455  {
3456  *result = SCIP_DIDNOTFIND;
3457  }
3458 
3459  return SCIP_OKAY;
3460 }
3461 
3462 
3463 /** callback function that deactivates a neighborhood on problems with no discrete variables */
3464 static
3465 DECL_NHDEACTIVATE(nhDeactivateDiscreteVars)
3466 { /*lint --e{715}*/
3467  assert(scip != NULL);
3468  assert(deactivate != NULL);
3469 
3470  /* deactivate if no discrete variables are present */
3471  *deactivate = (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) == 0);
3472 
3473  return SCIP_OKAY;
3474 }
3475 
3476 /** callback function that deactivates a neighborhood on problems with no binary variables */
3477 static
3478 DECL_NHDEACTIVATE(nhDeactivateBinVars)
3479 { /*lint --e{715}*/
3480  assert(scip != NULL);
3481  assert(deactivate != NULL);
3482 
3483  /* deactivate if no discrete variables are present */
3484  *deactivate = (SCIPgetNBinVars(scip) == 0);
3485 
3486  return SCIP_OKAY;
3487 }
3488 
3489 /** callback function that deactivates a neighborhood on problems with no objective variables */
3490 static
3491 DECL_NHDEACTIVATE(nhDeactivateObjVars)
3492 { /*lint --e{715}*/
3493  assert(scip != NULL);
3494  assert(deactivate != NULL);
3495 
3496  /* deactivate if no discrete variables are present */
3497  *deactivate = (SCIPgetNObjVars(scip) == 0);
3498 
3499  return SCIP_OKAY;
3500 }
3501 
3502 
3503 /** include all neighborhoods */
3504 static
3506  SCIP* scip, /**< SCIP data structure */
3507  SCIP_HEURDATA* heurdata /**< heuristic data of the ALNS heuristic */
3508  )
3509 {
3510  NH* rens;
3511  NH* rins;
3512  NH* mutation;
3513  NH* localbranching;
3514  NH* crossover;
3515  NH* proximity;
3516  NH* zeroobjective;
3517  NH* dins;
3518 
3519  heurdata->nneighborhoods = 0;
3520 
3521  /* include the RENS neighborhood */
3522  SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &rens, "rens",
3524  varFixingsRens, changeSubscipRens, NULL, NULL, NULL, NULL, nhDeactivateDiscreteVars) );
3525 
3526  /* include the RINS neighborhood */
3527  SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &rins, "rins",
3529  varFixingsRins, NULL, NULL, NULL, NULL, nhRefsolIncumbent, nhDeactivateDiscreteVars) );
3530 
3531  /* include the mutation neighborhood */
3532  SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &mutation, "mutation",
3534  varFixingsMutation, NULL, nhInitMutation, nhExitMutation, NULL, nhRefsolIncumbent, nhDeactivateDiscreteVars) );
3535 
3536  /* include the local branching neighborhood */
3537  SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &localbranching, "localbranching",
3539  NULL, changeSubscipLocalbranching, NULL, NULL, NULL, nhRefsolIncumbent, nhDeactivateBinVars) );
3540 
3541  /* include the crossover neighborhood */
3542  SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &crossover, "crossover",
3544  varFixingsCrossover, NULL,
3545  nhInitCrossover, nhExitCrossover, nhFreeCrossover, nhRefsolCrossover, nhDeactivateDiscreteVars) );
3546 
3547  /* allocate data for crossover to include the parameter */
3548  SCIP_CALL( SCIPallocBlockMemory(scip, &crossover->data.crossover) );
3549  crossover->data.crossover->rng = NULL;
3550 
3551  /* add crossover neighborhood parameters */
3552  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/alns/crossover/nsols", "the number of solutions that crossover should combine",
3553  &crossover->data.crossover->nsols, TRUE, DEFAULT_NSOLS_CROSSOVER, 2, 10, NULL, NULL) );
3554 
3555  /* include the Proximity neighborhood */
3556  SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &proximity, "proximity",
3558  NULL, changeSubscipProximity, NULL, NULL, NULL, nhRefsolIncumbent, nhDeactivateBinVars) );
3559 
3560  /* include the Zeroobjective neighborhood */
3561  SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &zeroobjective, "zeroobjective",
3563  NULL, changeSubscipZeroobjective, NULL, NULL, NULL, nhRefsolIncumbent, nhDeactivateObjVars) );
3564 
3565  /* include the DINS neighborhood */
3566  SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &dins, "dins",
3568  varFixingsDins, changeSubscipDins, NULL, NULL, nhFreeDins, nhRefsolIncumbent, nhDeactivateBinVars) );
3569 
3570  /* allocate data for DINS to include the parameter */
3571  SCIP_CALL( SCIPallocBlockMemory(scip, &dins->data.dins) );
3572 
3573  /* add DINS neighborhood parameters */
3574  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/alns/dins/npoolsols",
3575  "number of pool solutions where binary solution values must agree",
3576  &dins->data.dins->npoolsols, TRUE, DEFAULT_NPOOLSOLS_DINS, 1, 100, NULL, NULL) );
3577 
3578  return SCIP_OKAY;
3579 }
3580 
3581 /** initialization method of primal heuristic (called after problem was transformed) */
3582 static
3583 SCIP_DECL_HEURINIT(heurInitAlns)
3584 { /*lint --e{715}*/
3585  SCIP_HEURDATA* heurdata;
3586  int i;
3587 
3588  assert(scip != NULL);
3589  assert(heur != NULL);
3590 
3591  heurdata = SCIPheurGetData(heur);
3592  assert(heurdata != NULL);
3593 
3594  /* reactivate all neighborhoods if a new problem is read in */
3595  heurdata->nactiveneighborhoods = heurdata->nneighborhoods;
3596 
3597  /* todo initialize neighborhoods for new problem */
3598  for( i = 0; i < heurdata->nneighborhoods; ++i )
3599  {
3600  NH* neighborhood = heurdata->neighborhoods[i];
3601 
3602  SCIP_CALL( neighborhoodInit(scip, neighborhood) );
3603 
3604  SCIP_CALL( resetFixingRate(scip, &neighborhood->fixingrate) );
3605 
3606  SCIP_CALL( neighborhoodStatsReset(scip, &neighborhood->stats) );
3607  }
3608 
3609  /* open reward file for reading */
3610  if( strncasecmp(heurdata->rewardfilename, DEFAULT_REWARDFILENAME, strlen(DEFAULT_REWARDFILENAME)) != 0 )
3611  {
3612  heurdata->rewardfile = fopen(heurdata->rewardfilename, "w");
3613 
3614  if( heurdata->rewardfile == NULL )
3615  {
3616  SCIPerrorMessage("Error: Could not open reward file <%s>\n", heurdata->rewardfilename);
3617  return SCIP_FILECREATEERROR;
3618  }
3619 
3620  SCIPdebugMsg(scip, "Writing reward information to <%s>\n", heurdata->rewardfilename);
3621  }
3622  else
3623  heurdata->rewardfile = NULL;
3624 
3625  return SCIP_OKAY;
3626 }
3627 
3628 
3629 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
3630 static
3631 SCIP_DECL_HEURINITSOL(heurInitsolAlns)
3632 { /*lint --e{715}*/
3633  SCIP_HEURDATA* heurdata;
3634  int i;
3635  SCIP_Real* priorities;
3636  unsigned int initseed;
3637 
3638  assert(scip != NULL);
3639  assert(heur != NULL);
3640 
3641  heurdata = SCIPheurGetData(heur);
3642  assert(heurdata != NULL);
3643  heurdata->nactiveneighborhoods = heurdata->nneighborhoods;
3644 
3645  SCIP_CALL( SCIPallocBufferArray(scip, &priorities, heurdata->nactiveneighborhoods) );
3646 
3647  /* init neighborhoods for new problem by resetting their statistics and fixing rate */
3648  for( i = heurdata->nneighborhoods - 1; i >= 0; --i )
3649  {
3650  NH* neighborhood = heurdata->neighborhoods[i];
3651  SCIP_Bool deactivate;
3652 
3653  SCIP_CALL( neighborhood->nhdeactivate(scip, &deactivate) );
3654 
3655  /* disable inactive neighborhoods */
3656  if( deactivate || ! neighborhood->active )
3657  {
3658  if( heurdata->nactiveneighborhoods - 1 > i )
3659  {
3660  assert(heurdata->neighborhoods[heurdata->nactiveneighborhoods - 1]->active);
3661  SCIPswapPointers((void **)&heurdata->neighborhoods[i], (void **)&heurdata->neighborhoods[heurdata->nactiveneighborhoods - 1]);
3662  }
3663  heurdata->nactiveneighborhoods--;
3664  }
3665  }
3666 
3667  /* collect neighborhood priorities */
3668  for( i = 0; i < heurdata->nactiveneighborhoods; ++i )
3669  priorities[i] = heurdata->neighborhoods[i]->priority;
3670 
3671  initseed = (unsigned int)heurdata->seed + SCIPgetNVars(scip);
3672 
3673  /* active neighborhoods might change between init calls, reset functionality must take this into account */
3674  if( heurdata->bandit != NULL && SCIPbanditGetNActions(heurdata->bandit) != heurdata->nactiveneighborhoods )
3675  {
3676  SCIP_CALL( SCIPfreeBandit(scip, &heurdata->bandit) );
3677 
3678  heurdata->bandit = NULL;
3679  }
3680 
3681  if( heurdata->nactiveneighborhoods > 0 )
3682  { /* create or reset bandit algorithm */
3683  if( heurdata->bandit == NULL )
3684  {
3685  SCIP_CALL( createBandit(scip, heurdata, priorities, initseed) );
3686 
3687  resetMinimumImprovement(heurdata);
3688  resetTargetNodeLimit(heurdata);
3689  }
3690  else if( heurdata->resetweights )
3691  {
3692  SCIP_CALL( SCIPresetBandit(scip, heurdata->bandit, priorities, initseed) );
3693 
3694  resetMinimumImprovement(heurdata);
3695  resetTargetNodeLimit(heurdata);
3696  }
3697  }
3698 
3699  heurdata->usednodes = 0;
3700  heurdata->ninitneighborhoods = heurdata->nactiveneighborhoods;
3701  resetCurrentNeighborhood(heurdata);
3702 
3703  SCIPfreeBufferArray(scip, &priorities);
3704 
3705  return SCIP_OKAY;
3706 }
3707 
3708 
3709 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
3710 static
3711 SCIP_DECL_HEUREXIT(heurExitAlns)
3712 { /*lint --e{715}*/
3713  SCIP_HEURDATA* heurdata;
3714  int i;
3715 
3716  assert(scip != NULL);
3717  assert(heur != NULL);
3718 
3719  heurdata = SCIPheurGetData(heur);
3720  assert(heurdata != NULL);
3721 
3722  /* free neighborhood specific data */
3723  for( i = 0; i < heurdata->nneighborhoods; ++i )
3724  {
3725  NH* neighborhood = heurdata->neighborhoods[i];
3726 
3727  SCIP_CALL( neighborhoodExit(scip, neighborhood) );
3728  }
3729 
3730  if( heurdata->rewardfile != NULL )
3731  {
3732  fclose(heurdata->rewardfile);
3733  heurdata->rewardfile = NULL;
3734  }
3735 
3736  return SCIP_OKAY;
3737 }
3738 
3739 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
3740 static
3741 SCIP_DECL_HEURFREE(heurFreeAlns)
3742 { /*lint --e{715}*/
3743  SCIP_HEURDATA* heurdata;
3744  int i;
3745 
3746  assert(scip != NULL);
3747  assert(heur != NULL);
3748 
3749  heurdata = SCIPheurGetData(heur);
3750  assert(heurdata != NULL);
3751 
3752  /* bandits are only initialized if a problem has been read */
3753  if( heurdata->bandit != NULL )
3754  {
3755  SCIP_CALL( SCIPfreeBandit(scip, &heurdata->bandit) );
3756  }
3757 
3758  /* free neighborhoods */
3759  for( i = 0; i < heurdata->nneighborhoods; ++i )
3760  {
3761  SCIP_CALL( alnsFreeNeighborhood(scip, &(heurdata->neighborhoods[i])) );
3762  }
3763 
3764  SCIPfreeBlockMemoryArray(scip, &heurdata->neighborhoods, NNEIGHBORHOODS);
3765 
3766  SCIPfreeBlockMemory(scip, &heurdata);
3767 
3768  return SCIP_OKAY;
3769 }
3770 
3771 /** output method of statistics table to output file stream 'file' */
3772 static
3773 SCIP_DECL_TABLEOUTPUT(tableOutputNeighborhood)
3774 { /*lint --e{715}*/
3775  SCIP_HEURDATA* heurdata;
3776 
3777  assert(SCIPfindHeur(scip, HEUR_NAME) != NULL);
3778  heurdata = SCIPheurGetData(SCIPfindHeur(scip, HEUR_NAME));
3779  assert(heurdata != NULL);
3780 
3781  printNeighborhoodStatistics(scip, heurdata, file);
3782 
3783  return SCIP_OKAY;
3784 }
3785 
3786 /*
3787  * primal heuristic specific interface methods
3788  */
3789 
3790 /** creates the alns primal heuristic and includes it in SCIP */
3792  SCIP* scip /**< SCIP data structure */
3793  )
3794 {
3795  SCIP_HEURDATA* heurdata;
3796  SCIP_HEUR* heur;
3797 
3798  /* create alns primal heuristic data */
3799  heurdata = NULL;
3800  heur = NULL;
3801 
3802  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
3803  BMSclearMemory(heurdata);
3804 
3805  /* TODO make this a user parameter? */
3806  heurdata->lplimfac = LPLIMFAC;
3807 
3808  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->neighborhoods, NNEIGHBORHOODS) );
3809 
3810  /* include primal heuristic */
3811  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
3813  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecAlns, heurdata) );
3814 
3815  assert(heur != NULL);
3816 
3817  /* include all neighborhoods */
3818  SCIP_CALL( includeNeighborhoods(scip, heurdata) );
3819 
3820  /* set non fundamental callbacks via setter functions */
3821  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyAlns) );
3822  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeAlns) );
3823  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitAlns) );
3824  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolAlns) );
3825  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitAlns) );
3826 
3827  /* add alns primal heuristic parameters */
3828  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
3829  "maximum number of nodes to regard in the subproblem",
3830  &heurdata->maxnodes, TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
3831 
3832  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
3833  "offset added to the nodes budget",
3834  &heurdata->nodesoffset, FALSE, DEFAULT_NODESOFFSET, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
3835 
3836  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
3837  "minimum number of nodes required to start a sub-SCIP",
3838  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
3839 
3840  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/waitingnodes",
3841  "number of nodes since last incumbent solution that the heuristic should wait",
3842  &heurdata->waitingnodes, TRUE, DEFAULT_WAITINGNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
3843 
3844  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
3845  "fraction of nodes compared to the main SCIP for budget computation",
3846  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
3847 
3848  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/startminimprove",
3849  "initial factor by which ALNS should at least improve the incumbent",
3850  &heurdata->startminimprove, TRUE, DEFAULT_STARTMINIMPROVE, 0.0, 1.0, NULL, NULL) );
3851 
3852  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprovelow",
3853  "lower threshold for the minimal improvement over the incumbent",
3854  &heurdata->minimprovelow, TRUE, DEFAULT_MINIMPROVELOW, 0.0, 1.0, NULL, NULL) );
3855 
3856  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprovehigh",
3857  "upper bound for the minimal improvement over the incumbent",
3858  &heurdata->minimprovehigh, TRUE, DEFAULT_MINIMPROVEHIGH, 0.0, 1.0, NULL, NULL) );
3859 
3860  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nsolslim",
3861  "limit on the number of improving solutions in a sub-SCIP call",
3862  &heurdata->nsolslim, FALSE, DEFAULT_NSOLSLIM, -1, INT_MAX, NULL, NULL) );
3863 
3864  SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/banditalgo",
3865  "the bandit algorithm: (u)pper confidence bounds, (e)xp.3, epsilon (g)reedy",
3866  &heurdata->banditalgo, TRUE, DEFAULT_BANDITALGO, "ueg", NULL, NULL) );
3867 
3868  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/gamma",
3869  "weight between uniform (gamma ~ 1) and weight driven (gamma ~ 0) probability distribution for exp3",
3870  &heurdata->exp3_gamma, TRUE, DEFAULT_GAMMA, 0.0, 1.0, NULL, NULL) );
3871 
3872  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/beta",
3873  "reward offset between 0 and 1 at every observation for Exp.3",
3874  &heurdata->exp3_beta, TRUE, DEFAULT_BETA, 0.0, 1.0, NULL, NULL) );
3875 
3876  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/alpha",
3877  "parameter to increase the confidence width in UCB",
3878  &heurdata->ucb_alpha, TRUE, DEFAULT_ALPHA, 0.0, 100.0, NULL, NULL) );
3879 
3880  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usedistances",
3881  "distances from fixed variables be used for variable prioritization",
3882  &heurdata->usedistances, TRUE, DEFAULT_USEDISTANCES, NULL, NULL) );
3883 
3884  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useredcost",
3885  "should reduced cost scores be used for variable prioritization?",
3886  &heurdata->useredcost, TRUE, DEFAULT_USEREDCOST, NULL, NULL) );
3887 
3888  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/domorefixings",
3889  "should the ALNS heuristic do more fixings by itself based on variable prioritization "
3890  "until the target fixing rate is reached?",
3891  &heurdata->domorefixings, TRUE, DEFAULT_DOMOREFIXINGS, NULL, NULL) );
3892 
3893  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/adjustfixingrate",
3894  "should the heuristic adjust the target fixing rate based on the success?",
3895  &heurdata->adjustfixingrate, TRUE, DEFAULT_ADJUSTFIXINGRATE, NULL, NULL) );
3896 
3897  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usesubscipheurs",
3898  "should the heuristic activate other sub-SCIP heuristics during its search?",
3899  &heurdata->usesubscipheurs, TRUE, DEFAULT_USESUBSCIPHEURS, NULL, NULL) );
3900 
3901  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/rewardcontrol",
3902  "reward control to increase the weight of the simple solution indicator and decrease the weight of the closed gap reward",
3903  &heurdata->rewardcontrol, TRUE, DEFAULT_REWARDCONTROL, 0.0, 1.0, NULL, NULL) );
3904 
3905  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/targetnodefactor",
3906  "factor by which target node number is eventually increased",
3907  &heurdata->targetnodefactor, TRUE, DEFAULT_TARGETNODEFACTOR, 1.0, 1e+5, NULL, NULL) );
3908 
3909  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/seed",
3910  "initial random seed for bandit algorithms and random decisions by neighborhoods",
3911  &heurdata->seed, FALSE, DEFAULT_SEED, 0, INT_MAX, NULL, NULL) );
3912 
3913  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/adjustminimprove",
3914  "should the factor by which the minimum improvement is bound be dynamically updated?",
3915  &heurdata->adjustminimprove, TRUE, DEFAULT_ADJUSTMINIMPROVE, NULL, NULL) );
3916 
3917  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/adjusttargetnodes",
3918  "should the target nodes be dynamically adjusted?",
3919  &heurdata->adjusttargetnodes, TRUE, DEFAULT_ADJUSTTARGETNODES, NULL, NULL) );
3920 
3921  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/eps",
3922  "increase exploration in epsilon-greedy bandit algorithm",
3923  &heurdata->epsgreedy_eps, TRUE, DEFAULT_EPS, 0.0, 1.0, NULL, NULL) );
3924 
3925  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/rewardbaseline",
3926  "the reward baseline to separate successful and failed calls",
3927  &heurdata->rewardbaseline, TRUE, DEFAULT_REWARDBASELINE, 0.0, 0.99, NULL, NULL) );
3928 
3929  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/resetweights",
3930  "should the bandit algorithms be reset when a new problem is read?",
3931  &heurdata->resetweights, TRUE, DEFAULT_RESETWEIGHTS, NULL, NULL) );
3932 
3933  SCIP_CALL( SCIPaddStringParam(scip, "heuristics/" HEUR_NAME "/rewardfilename", "file name to store all rewards and the selection of the bandit",
3934  &heurdata->rewardfilename, TRUE, DEFAULT_REWARDFILENAME, NULL, NULL) );
3935 
3936  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/subsciprandseeds",
3937  "should random seeds of sub-SCIPs be altered to increase diversification?",
3938  &heurdata->subsciprandseeds, TRUE, DEFAULT_SUBSCIPRANDSEEDS, NULL, NULL) );
3939 
3940  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/scalebyeffort",
3941  "should the reward be scaled by the effort?",
3942  &heurdata->scalebyeffort, TRUE, DEFAULT_SCALEBYEFFORT, NULL, NULL) );
3943 
3944  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
3945  "should cutting planes be copied to the sub-SCIP?",
3946  &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
3947 
3948  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/fixtol",
3949  "tolerance by which the fixing rate may be missed without generic fixing",
3950  &heurdata->fixtol, TRUE, DEFAULT_FIXTOL, 0.0, 1.0, NULL, NULL) );
3951 
3952  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/unfixtol",
3953  "tolerance by which the fixing rate may be exceeded without generic unfixing",
3954  &heurdata->fixtol, TRUE, DEFAULT_UNFIXTOL, 0.0, 1.0, NULL, NULL) );
3955 
3956  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselocalredcost",
3957  "should local reduced costs be used for generic (un)fixing?",
3958  &heurdata->uselocalredcost, TRUE, DEFAULT_USELOCALREDCOST, NULL, NULL) );
3959 
3960  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usepscost",
3961  "should pseudo cost scores be used for variable priorization?",
3962  &heurdata->usepscost, TRUE, DEFAULT_USEPSCOST, NULL, NULL) );
3963 
3964  assert(SCIPfindTable(scip, TABLE_NAME_NEIGHBORHOOD) == NULL);
3966  NULL, NULL, NULL, NULL, NULL, NULL, tableOutputNeighborhood,
3968 
3969  return SCIP_OKAY;
3970 }
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
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:116
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2134
#define DEFAULT_GAMMA
Definition: heur_alns.c:121
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
NH_STATS stats
Definition: heur_alns.c:338
public methods for the epsilon greedy bandit selector
#define DEFAULT_USESUBSCIPHEURS
Definition: heur_alns.c:134
#define DEFAULT_RESETWEIGHTS
Definition: heur_alns.c:107
static SCIP_DECL_TABLEOUTPUT(tableOutputNeighborhood)
Definition: heur_alns.c:3774
static SCIP_RETCODE addLocalBranchingConstraint(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **subvars, int distance, SCIP_Bool *success, int *naddedconss)
Definition: heur_alns.c:3105
SCIP_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4879
int nfixings
Definition: heur_alns.c:319
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:436
#define SCIP_EVENTTYPE_LPSOLVED
Definition: type_event.h:84
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:1048
SCIP_RETCODE SCIPcreateBanditEpsgreedy(SCIP *scip, SCIP_BANDIT **epsgreedy, SCIP_Real *priorities, SCIP_Real eps, SCIP_Bool preferrecent, SCIP_Real decayfactor, int avglim, int nactions, unsigned int initseed)
SCIP_Real oldupperbound
Definition: heur_alns.c:313
#define NULL
Definition: def.h:239
int nruns
Definition: heur_alns.c:315
#define DEFAULT_STARTMINIMPROVE
Definition: heur_alns.c:96
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:99
static SCIP_RETCODE createBandit(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Real *priorities, unsigned int initseed)
Definition: heur_alns.c:1567
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
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for SCIP parameter handling
HistIndex
Definition: heur_alns.c:293
SCIP_RETCODE SCIPcreateBanditExp3(SCIP *scip, SCIP_BANDIT **exp3, SCIP_Real *priorities, SCIP_Real gammaparam, SCIP_Real beta, int nactions, unsigned int initseed)
Definition: bandit_exp3.c:301
#define HEUR_DISPCHAR
Definition: heur_alns.c:67
#define DEFAULT_REWARDBASELINE
Definition: heur_alns.c:109
SCIP_Real * pscostscores
Definition: heur_alns.c:459
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_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
public methods for node selector plugins
SCIP_RETCODE SCIPincludeHeurAlns(SCIP *scip)
Definition: heur_alns.c:3792
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:1623
static void decreaseMinimumImprovement(SCIP_HEURDATA *heurdata)
Definition: heur_alns.c:663
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:954
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
DATA_DINS * dins
Definition: heur_alns.c:352
static void resetMinimumImprovement(SCIP_HEURDATA *heurdata)
Definition: heur_alns.c:641
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17343
#define DECL_NHINIT(x)
Definition: heur_alns.c:254
#define HEUR_FREQ
Definition: heur_alns.c:69
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:379
#define SCIP_MAXSTRLEN
Definition: def.h:260
SCIP_Real SCIPgetVarPseudocostVal(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta)
Definition: scip_var.c:8613
#define DEFAULT_NSOLSLIM
Definition: heur_alns.c:82
static SCIP_DECL_HEURINIT(heurInitAlns)
Definition: heur_alns.c:3584
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1400
#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
SCIP_RETCODE SCIPbanditSelect(SCIP_BANDIT *bandit, int *action)
Definition: bandit.c:143
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:280
SCIP_Real SCIPgetVarRedcost(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1866
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
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip_prob.c:2484
#define DEFAULT_USEREDCOST
Definition: heur_alns.c:125
public solving methods
SCIP * scip
Definition: heur_alns.c:455
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:172
public methods for timing
static SCIP_RETCODE updateBanditAlgorithm(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Real reward, int neighborhoodidx)
Definition: heur_alns.c:2102
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16909
#define DECL_VARFIXINGS(x)
Definition: heur_alns.c:226
SCIP_TABLE * SCIPfindTable(SCIP *scip, const char *name)
Definition: scip_table.c:84
SCIP_RETCODE SCIPstopClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip_timing.c:245
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
#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_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition: var.c:12827
#define TABLE_DESC_NEIGHBORHOOD
Definition: heur_alns.c:194
#define DECL_NHREFSOL(x)
Definition: heur_alns.c:279
void SCIPswapPointers(void **pointer1, void **pointer2)
Definition: misc.c:9645
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1918
#define LPLIMFAC
Definition: heur_alns.c:88
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip_sol.c:2329
#define FALSE
Definition: def.h:65
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2793
#define DEFAULT_ACTIVE_LOCALBRANCHING
Definition: heur_alns.c:161
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:314
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:183
#define DEFAULT_NODESOFFSET
Definition: heur_alns.c:81
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10017
#define TRUE
Definition: def.h:64
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
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:1022
#define DEFAULT_WAITINGNODES
Definition: heur_alns.c:85
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:286
NH_FIXINGRATE fixingrate
Definition: heur_alns.c:337
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17036
#define DEFAULT_NODESQUOT
Definition: heur_alns.c:80
SCIP_Bool SCIPisDualfeasZero(SCIP *scip, SCIP_Real val)
#define DEFAULT_MINIMPROVELOW
Definition: heur_alns.c:93
#define DECL_NHFREE(x)
Definition: heur_alns.c:266
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
public methods for problem variables
static GRAPHNODE ** active
void SCIPselectInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int k, int len)
static SCIP_RETCODE neighborhoodFixVariables(SCIP *scip, SCIP_HEURDATA *heurdata, NH *neighborhood, SCIP_VAR **varbuf, SCIP_Real *valbuf, int *nfixings, SCIP_RESULT *result)
Definition: heur_alns.c:1770
static SCIP_DECL_HEUREXIT(heurExitAlns)
Definition: heur_alns.c:3712
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
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:187
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:266
#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
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:9372
#define HEUR_NAME
Definition: heur_alns.c:65
#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:1397
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:138
SCIP_RETCODE SCIPfreeClock(SCIP *scip, SCIP_CLOCK **clck)
Definition: scip_timing.c:194
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2931
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIP_LONGINT_MAX
Definition: def.h:136
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
#define DEFAULT_UNFIXTOL
Definition: heur_alns.c:111
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:339
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip_general.c:611
public methods for SCIP variables
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:694
Definition: heur_alns.c:334
#define SCIP_EVENTTYPE_ALNS
Definition: heur_alns.c:190
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4966
#define SCIPdebugMsg
Definition: scip_message.h:88
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:155
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:279
#define DEFAULT_PRIORITY_ZEROOBJECTIVE
Definition: heur_alns.c:177
#define LRATEMIN
Definition: heur_alns.c:87
#define DEFAULT_ADJUSTFIXINGRATE
Definition: heur_alns.c:131
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
static SCIP_RETCODE alnsFreeNeighborhood(SCIP *scip, NH **neighborhood)
Definition: heur_alns.c:813
public methods for numerical tolerances
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
static void updateTargetNodeLimit(SCIP_HEURDATA *heurdata, NH_STATS *runstats, SCIP_STATUS subscipstatus)
Definition: heur_alns.c:604
#define HEUR_USESSUBSCIP
Definition: heur_alns.c:73
#define SCIP_REAL_FORMAT
Definition: def.h:153
public methods for querying solving statistics
static void updateNeighborhoodStats(SCIP *scip, NH_STATS *runstats, NH *neighborhood, SCIP_STATUS subscipstatus)
Definition: heur_alns.c:1135
#define DEFAULT_ACTIVE_RENS
Definition: heur_alns.c:146
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_Real increment
Definition: heur_alns.c:329
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17353
#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
#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_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:296
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2577
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1254
SCIP_RETCODE SCIPcreateClock(SCIP *scip, SCIP_CLOCK **clck)
Definition: scip_timing.c:143
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip_heur.c:328
#define BMSfreeMemoryArray(ptr)
Definition: memory.h:129
#define SCIPerrorMessage
Definition: pub_message.h:45
DATA_MUTATION * mutation
Definition: heur_alns.c:350
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:291
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2822
static SCIP_DECL_HEURCOPY(heurCopyAlns)
Definition: heur_alns.c:1605
#define DECL_NHDEACTIVATE(x)
Definition: heur_alns.c:287
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:248
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#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_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1447
SCIP_RETCODE SCIPfreeBandit(SCIP *scip, SCIP_BANDIT **bandit)
Definition: scip_bandit.c:91
char * name
Definition: heur_alns.c:336
static SCIP_DECL_HEURFREE(heurFreeAlns)
Definition: heur_alns.c:3742
union Nh::@4 data
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:520
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:519
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:128
#define DEFAULT_MINNODES
Definition: heur_alns.c:83
SCIP_CLOCK * submipclock
Definition: heur_alns.c:311
void SCIPselectDownInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int k, int len)
#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
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16729
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2826
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:3632
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1540
#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:174
int SCIPheurGetFreq(SCIP_HEUR *heur)
Definition: heur.c:1339
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:17717
#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
#define SCIP_CALL(x)
Definition: def.h:351
SCIP_Real SCIPgetLowerbound(SCIP *scip)
#define DEFAULT_SUBSCIPRANDSEEDS
Definition: heur_alns.c:108
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:1251
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1380
#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
SCIP_Bool SCIPisDualfeasNegative(SCIP *scip, SCIP_Real val)
#define BMSduplicateMemoryArray(ptr, source, num)
Definition: memory.h:125
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:141
public methods for primal heuristic plugins and divesets
public methods for constraint handler plugins and constraints
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_var.c:4450
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
SCIP_Real newupperbound
Definition: heur_alns.c:314
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
#define DEFAULT_USEPSCOST
Definition: heur_alns.c:126
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1270
public data structures and miscellaneous methods
#define DEFAULT_BESTSOLWEIGHT
Definition: heur_alns.c:103
#define DECL_NHEXIT(x)
Definition: heur_alns.c:260
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:3476
SCIP_Real SCIPgetProbabilityExp3(SCIP_BANDIT *exp3, int action)
Definition: bandit_exp3.c:353
#define SCIP_Bool
Definition: def.h:62
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:354
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:226
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:995
SCIP_Longint usednodes
Definition: heur_alns.c:312
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:2732
SCIP_Longint SCIPsolGetNodenum(SCIP_SOL *sol)
Definition: sol.c:2533
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
enum SCIP_Status SCIP_STATUS
Definition: type_stat.h:58
#define DEFAULT_MAXFIXINGRATE_ZEROOBJECTIVE
Definition: heur_alns.c:175
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip_prob.c:1478
SCIP_Real SCIPgetClockTime(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip_timing.c:377
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:715
public methods for statistics table plugins
static SCIP_Real getVariablePscostScore(SCIP *scip, SCIP_VAR *var, SCIP_Real refsolval)
Definition: heur_alns.c:1304
static SCIP_RETCODE transferSolution(SCIP *subscip, SCIP_EVENTDATA *eventdata)
Definition: heur_alns.c:881
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:3291
static void initRunStats(SCIP *scip, NH_STATS *stats)
Definition: heur_alns.c:1010
SCIP_Bool active
Definition: heur_alns.c:346
#define DECL_CHANGESUBSCIP(x)
Definition: heur_alns.c:243
#define MIN(x, y)
Definition: def.h:209
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:578
#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:1332
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:1034
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17191
public methods for bandit algorithms
SCIP_Real SCIPvarGetBestRootRedcost(SCIP_VAR *var)
Definition: var.c:13257
#define DEFAULT_MINFIXINGRATE_CROSSOVER
Definition: heur_alns.c:169
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2280
#define DEFAULT_ADJUSTMINIMPROVE
Definition: heur_alns.c:97
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:116
static void decreaseFixingRate(NH_FIXINGRATE *fx)
Definition: heur_alns.c:526
static SCIP_RETCODE neighborhoodExit(SCIP *scip, NH *neighborhood)
Definition: heur_alns.c:863
#define DEFAULT_SCALEBYEFFORT
Definition: heur_alns.c:106
static SCIP_DECL_HEUREXEC(heurExecAlns)
Definition: heur_alns.c:2280
#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 SCIPgetNObjVars(SCIP *scip)
Definition: scip_prob.c:2272
static SCIP_RETCODE neighborhoodGetRefsol(SCIP *scip, NH *neighborhood, SCIP_SOL **solptr)
Definition: heur_alns.c:1363
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
int npoolsols
Definition: heur_alns.c:373
#define BMSclearMemory(ptr)
Definition: memory.h:111
SCIP_Longint nsolsfound
Definition: heur_alns.c:317
static SCIP_RETCODE determineLimits(SCIP *scip, SCIP_HEUR *heur, SOLVELIMITS *solvelimits, SCIP_Bool *runagain)
Definition: heur_alns.c:1928
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2089
#define DEFAULT_DOMOREFIXINGS
Definition: heur_alns.c:128
unsigned int usedistances
Definition: heur_alns.c:461
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:9394
static SCIP_BANDIT * getBandit(SCIP_HEURDATA *heurdata)
Definition: heur_alns.c:1991
public methods for the LP relaxation, rows and columns
int nrunsbestsol
Definition: heur_alns.c:316
public methods for bandit algorithms
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:2044
SCIP_RETCODE SCIPbanditUpdate(SCIP_BANDIT *bandit, int action, SCIP_Real score)
Definition: bandit.c:164
#define EVENTHDLR_NAME
Definition: heur_alns.c:188
#define HEUR_MAXDEPTH
Definition: heur_alns.c:71
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_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
#define SCIP_LONGINT_FORMAT
Definition: def.h:142
public methods for branching rule plugins and branching
SCIP_Bool SCIPisDualfeasPositive(SCIP *scip, SCIP_Real val)
SCIP_VAR ** b
Definition: circlepacking.c:56
SCIP_Bool SCIPisObjIntegral(SCIP *scip)
Definition: scip_prob.c:1618
#define DEFAULT_PRIORITY_RENS
Definition: heur_alns.c:147
#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:208
#define DEFAULT_MAXFIXINGRATE_MUTATION
Definition: heur_alns.c:155
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2379
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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:239
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:2001
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition: scip_mem.c:171
public methods for random numbers
SCIP_Real maxfixingrate
Definition: heur_alns.c:330
#define DEFAULT_NPOOLSOLS_DINS
Definition: heur_alns.c:185
SCIP_RETCODE SCIPresetClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip_timing.c:211
#define DEFAULT_COPYCUTS
Definition: heur_alns.c:135
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1187
#define DEFAULT_FIXTOL
Definition: heur_alns.c:110
SCIP_Real SCIPvarGetBestRootSol(SCIP_VAR *var)
Definition: var.c:13191
static SCIP_RETCODE getReward(SCIP *scip, SCIP_HEURDATA *heurdata, NH_STATS *runstats, SCIP_Real *rewardptr)
Definition: heur_alns.c:2024
#define CROSSOVERSEED
Definition: heur_alns.c:141
static SCIP_RETCODE setLimits(SCIP *subscip, SOLVELIMITS *solvelimits)
Definition: heur_alns.c:1908
public methods for message output
SCIP_SOLORIGIN SCIPsolGetOrigin(SCIP_SOL *sol)
Definition: sol.c:2460
#define DEFAULT_NSOLS_CROSSOVER
Definition: heur_alns.c:184
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:264
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip_sol.c:1625
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition: scip_mem.c:197
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip_nodesel.c:304
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_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1999
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16848
int statushist[NHISTENTRIES]
Definition: heur_alns.c:320
#define SCIP_Real
Definition: def.h:150
SCIP_Real * SCIPgetWeightsEpsgreedy(SCIP_BANDIT *epsgreedy)
SCIP_RETCODE SCIPresetBandit(SCIP *scip, SCIP_BANDIT *bandit, SCIP_Real *priorities, unsigned int seed)
Definition: scip_bandit.c:75
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:739
#define DEFAULT_SEED
Definition: heur_alns.c:139
static int getHistIndex(SCIP_STATUS subscipstatus)
Definition: heur_alns.c:1040
int SCIPbanditGetNActions(SCIP_BANDIT *bandit)
Definition: bandit.c:293
public methods for message handling
public methods for Exp.3
#define SCIP_Longint
Definition: def.h:135
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
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16894
SCIP_RANDNUMGEN * SCIPbanditGetRandnumgen(SCIP_BANDIT *bandit)
Definition: bandit.c:283
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1312
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip_solve.c:400
#define DEFAULT_PRIORITY_CROSSOVER
Definition: heur_alns.c:172
#define DEFAULT_MAXFIXINGRATE_RINS
Definition: heur_alns.c:150
#define DEFAULT_ACTIVE_DINS
Definition: heur_alns.c:181
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:232
SCIP_Real * randscores
Definition: heur_alns.c:456
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
#define DEFAULT_MAXFIXINGRATE_CROSSOVER
Definition: heur_alns.c:170
SCIP_Real SCIPsumepsilon(SCIP *scip)
#define NHISTENTRIES
Definition: heur_alns.c:304
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
Definition: scip_solve.c:3439
SCIP_Real SCIPgetUpperbound(SCIP *scip)
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:112
public methods for primal heuristics
#define DEFAULT_USELOCALREDCOST
Definition: heur_alns.c:112
#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:330
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1165
static void computeIntegerVariableBoundsDins(SCIP *scip, SCIP_VAR *var, SCIP_Real *lbptr, SCIP_Real *ubptr)
Definition: heur_alns.c:3248
#define MUTATIONSEED
Definition: heur_alns.c:140
#define DEFAULT_BETA
Definition: heur_alns.c:113
#define TABLE_NAME_NEIGHBORHOOD
Definition: heur_alns.c:193
#define SCIP_ALLOC(x)
Definition: def.h:362
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
public methods for global and local (sub)problems
SCIP_Real SCIPgetConfidenceBoundUcb(SCIP_BANDIT *ucb, int action)
Definition: bandit_ucb.c:254
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16920
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:1868
#define TABLE_EARLIEST_STAGE_NEIGHBORHOOD
Definition: heur_alns.c:196
SCIP_RETCODE SCIPstartClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip_timing.c:228
static SCIP_RETCODE setupSubScip(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SOLVELIMITS *solvelimits, SCIP_HEUR *heur, SCIP_Bool objchgd)
Definition: heur_alns.c:2125
#define DEFAULT_REWARDCONTROL
Definition: heur_alns.c:105
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1410
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:211
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:973
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
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
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:636
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:129
int * distances
Definition: heur_alns.c:457
static void resetTargetNodeLimit(SCIP_HEURDATA *heurdata)
Definition: heur_alns.c:595
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:371
methods for selecting (weighted) k-medians
#define DEFAULT_ACTIVE_MUTATION
Definition: heur_alns.c:156
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:377
#define HEUR_PRIORITY
Definition: heur_alns.c:68
memory allocation routines
static SCIP_RETCODE includeNeighborhoods(SCIP *scip, SCIP_HEURDATA *heurdata)
Definition: heur_alns.c:3506