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