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