SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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#if !defined(_WIN32) && !defined(_WIN64)
75#include <strings.h> /*lint --e{766}*/ /* needed for strncasecmp() */
76#endif
77
78#define HEUR_NAME "alns"
79#define HEUR_DESC "Large neighborhood search heuristic that orchestrates the popular neighborhoods Local Branching, RINS, RENS, DINS etc."
80#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
81#define HEUR_PRIORITY -1100500
82#define HEUR_FREQ 20
83#define HEUR_FREQOFS 0
84#define HEUR_MAXDEPTH -1
85#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE | SCIP_HEURTIMING_DURINGLPLOOP
86#define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
87
88#define NNEIGHBORHOODS 9
89
90#define DEFAULT_SHOWNBSTATS FALSE /**< show statistics on neighborhoods? */
91
92/*
93 * limit parameters for sub-SCIPs
94 */
95#define DEFAULT_NODESQUOT 0.1
96#define DEFAULT_NODESQUOTMIN 0.0
97#define DEFAULT_NODESOFFSET 500LL
98#define DEFAULT_NSOLSLIM 3
99#define DEFAULT_MINNODES 50LL
100#define DEFAULT_MAXNODES 5000LL
101#define DEFAULT_WAITINGNODES 25LL /**< number of nodes since last incumbent solution that the heuristic should wait */
102#define DEFAULT_TARGETNODEFACTOR 1.05
103#define LRATEMIN 0.01 /**< lower bound for learning rate for target nodes and minimum improvement */
104#define LPLIMFAC 4.0
105#define DEFAULT_INITDURINGROOT FALSE
106#define DEFAULT_MAXCALLSSAMESOL -1 /**< number of allowed executions of the heuristic on the same incumbent solution */
107
108/*
109 * parameters for the minimum improvement
110 */
111#define DEFAULT_MINIMPROVELOW 0.01
112#define DEFAULT_MINIMPROVEHIGH 0.01
113#define MINIMPROVEFAC 1.5
114#define DEFAULT_STARTMINIMPROVE 0.01
115#define DEFAULT_ADJUSTMINIMPROVE FALSE
116#define DEFAULT_ADJUSTTARGETNODES TRUE /**< should the target nodes be dynamically adjusted? */
117
118/*
119 * bandit algorithm parameters
120 */
121#define DEFAULT_BESTSOLWEIGHT 1
122#define DEFAULT_BANDITALGO 'i' /**< the default bandit algorithm: (u)pper confidence bounds, (e)xp.3, epsilon (g)reedy, exp.3-(i)x */
123#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 */
124#define DEFAULT_SCALEBYEFFORT TRUE /**< should the reward be scaled by the effort? */
125#define DEFAULT_RESETWEIGHTS TRUE /**< should the bandit algorithms be reset when a new problem is read? */
126#define DEFAULT_SUBSCIPRANDSEEDS FALSE /**< should random seeds of sub-SCIPs be altered to increase diversification? */
127#define DEFAULT_REWARDBASELINE 0.5 /**< the reward baseline to separate successful and failed calls */
128#define DEFAULT_FIXTOL 0.1 /**< tolerance by which the fixing rate may be missed without generic fixing */
129#define DEFAULT_UNFIXTOL 0.1 /**< tolerance by which the fixing rate may be exceeded without generic unfixing */
130#define DEFAULT_USELOCALREDCOST FALSE /**< should local reduced costs be used for generic (un)fixing? */
131#define DEFAULT_BETA 0.0 /**< default reward offset between 0 and 1 at every observation for exp3 */
132
133/*
134 * the following 3 parameters have been tuned by a simulation experiment
135 * as described in the paper.
136 */
137#define DEFAULT_EPS 0.4685844 /**< increase exploration in epsilon-greedy bandit algorithm */
138#define DEFAULT_ALPHA 0.0016 /**< parameter to increase the confidence width in UCB */
139#define DEFAULT_GAMMA 0.07041455 /**< default weight between uniform (gamma ~ 1) and weight driven (gamma ~ 0) probability distribution for exp3 */
140/*
141 * parameters to control variable fixing
142 */
143#define DEFAULT_USEREDCOST TRUE /**< should reduced cost scores be used for variable priorization? */
144#define DEFAULT_USEPSCOST TRUE /**< should pseudo cost scores be used for variable priorization? */
145#define DEFAULT_USEDISTANCES TRUE /**< should distances from fixed variables be used for variable priorization */
146#define DEFAULT_DOMOREFIXINGS TRUE /**< should the ALNS heuristic do more fixings by itself based on variable prioritization
147 * until the target fixing rate is reached? */
148#define DEFAULT_ADJUSTFIXINGRATE TRUE /**< should the heuristic adjust the target fixing rate based on the success? */
149#define FIXINGRATE_DECAY 0.75 /**< geometric decay for fixing rate adjustments */
150#define FIXINGRATE_STARTINC 0.2 /**< initial increment value for fixing rate */
151#define DEFAULT_USESUBSCIPHEURS FALSE /**< should the heuristic activate other sub-SCIP heuristics during its search? */
152#define DEFAULT_COPYCUTS FALSE /**< should cutting planes be copied to the sub-SCIP? */
153#define DEFAULT_REWARDFILENAME "-" /**< file name to store all rewards and the selection of the bandit */
154
155/* individual random seeds */
156#define DEFAULT_SEED 113
157#define MUTATIONSEED 121
158#define CROSSOVERSEED 321
159
160/* individual neighborhood parameters */
161#define DEFAULT_MINFIXINGRATE_RENS 0.3
162#define DEFAULT_MAXFIXINGRATE_RENS 0.9
163#define DEFAULT_ACTIVE_RENS TRUE
164#define DEFAULT_PRIORITY_RENS 1.0
165
166#define DEFAULT_MINFIXINGRATE_RINS 0.3
167#define DEFAULT_MAXFIXINGRATE_RINS 0.9
168#define DEFAULT_ACTIVE_RINS TRUE
169#define DEFAULT_PRIORITY_RINS 1.0
170
171#define DEFAULT_MINFIXINGRATE_MUTATION 0.3
172#define DEFAULT_MAXFIXINGRATE_MUTATION 0.9
173#define DEFAULT_ACTIVE_MUTATION TRUE
174#define DEFAULT_PRIORITY_MUTATION 1.0
175
176#define DEFAULT_MINFIXINGRATE_LOCALBRANCHING 0.3
177#define DEFAULT_MAXFIXINGRATE_LOCALBRANCHING 0.9
178#define DEFAULT_ACTIVE_LOCALBRANCHING TRUE
179#define DEFAULT_PRIORITY_LOCALBRANCHING 1.0
180
181#define DEFAULT_MINFIXINGRATE_PROXIMITY 0.3
182#define DEFAULT_MAXFIXINGRATE_PROXIMITY 0.9
183#define DEFAULT_ACTIVE_PROXIMITY TRUE
184#define DEFAULT_PRIORITY_PROXIMITY 1.0
185
186#define DEFAULT_MINFIXINGRATE_CROSSOVER 0.3
187#define DEFAULT_MAXFIXINGRATE_CROSSOVER 0.9
188#define DEFAULT_ACTIVE_CROSSOVER TRUE
189#define DEFAULT_PRIORITY_CROSSOVER 1.0
190
191#define DEFAULT_MINFIXINGRATE_ZEROOBJECTIVE 0.3
192#define DEFAULT_MAXFIXINGRATE_ZEROOBJECTIVE 0.9
193#define DEFAULT_ACTIVE_ZEROOBJECTIVE TRUE
194#define DEFAULT_PRIORITY_ZEROOBJECTIVE 1.0
195
196#define DEFAULT_MINFIXINGRATE_DINS 0.3
197#define DEFAULT_MAXFIXINGRATE_DINS 0.9
198#define DEFAULT_ACTIVE_DINS TRUE
199#define DEFAULT_PRIORITY_DINS 1.0
200
201#define DEFAULT_MINFIXINGRATE_TRUSTREGION 0.3
202#define DEFAULT_MAXFIXINGRATE_TRUSTREGION 0.9
203#define DEFAULT_ACTIVE_TRUSTREGION FALSE
204#define DEFAULT_PRIORITY_TRUSTREGION 1.0
205
206
207#define DEFAULT_NSOLS_CROSSOVER 2 /**< parameter for the number of solutions that crossover should combine */
208#define DEFAULT_NPOOLSOLS_DINS 5 /**< number of pool solutions where binary solution values must agree */
209#define DEFAULT_VIOLPENALTY_TRUSTREGION 100.0 /**< the penalty for violating the trust region */
210
211/* event handler properties */
212#define EVENTHDLR_NAME "Alns"
213#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic"
214#define SCIP_EVENTTYPE_ALNS (SCIP_EVENTTYPE_LPSOLVED | SCIP_EVENTTYPE_SOLFOUND | SCIP_EVENTTYPE_BESTSOLFOUND)
215
216/* properties of the ALNS neighborhood statistics table */
217#define TABLE_NAME_NEIGHBORHOOD "neighborhood"
218#define TABLE_DESC_NEIGHBORHOOD "ALNS neighborhood statistics"
219#define TABLE_POSITION_NEIGHBORHOOD 12500 /**< the position of the statistics table */
220#define TABLE_EARLIEST_STAGE_NEIGHBORHOOD SCIP_STAGE_TRANSFORMED /**< output of the statistics table is only printed from this stage onwards */
221
222/** reward types of ALNS */
224 REWARDTYPE_TOTAL, /**< combination of the other rewards */
225 REWARDTYPE_BESTSOL, /**< 1, if a new solution was found, 0 otherwise */
226 REWARDTYPE_CLOSEDGAP, /**< 0 if no solution was found, closed gap otherwise */
227 REWARDTYPE_NOSOLPENALTY, /**< 1 if a solution was found, otherwise between 0 and 1 depending on the effort spent */
230
231/*
232 * Data structures
233 */
234
235/*
236 * additional neighborhood data structures
237 */
238
239
240typedef struct data_crossover DATA_CROSSOVER; /**< crossover neighborhood data structure */
241
242typedef struct data_mutation DATA_MUTATION; /**< mutation neighborhood data structure */
243
244typedef struct data_dins DATA_DINS; /**< dins neighborhood data structure */
245
246typedef struct data_trustregion DATA_TRUSTREGION; /**< trustregion neighborhood data structure */
247
248typedef struct NH_FixingRate NH_FIXINGRATE; /** fixing rate data structure */
249
250typedef struct NH_Stats NH_STATS; /**< neighborhood statistics data structure */
251
252typedef struct Nh NH; /**< neighborhood data structure */
253
254
255/*
256 * variable priorization data structure for sorting
257 */
258typedef struct VarPrio VARPRIO;
259
260/** callback to collect variable fixings of neighborhood */
261 #define DECL_VARFIXINGS(x) SCIP_RETCODE x ( \
262 SCIP* scip, /**< SCIP data structure */ \
263 NH* neighborhood, /**< ALNS neighborhood data structure */ \
264 SCIP_VAR** varbuf, /**< buffer array to collect variables to fix */\
265 SCIP_Real* valbuf, /**< buffer array to collect fixing values */ \
266 int* nfixings, /**< pointer to store the number of fixings */ \
267 SCIP_RESULT* result /**< result pointer */ \
268 )
269
270/** callback for subproblem changes other than variable fixings
271 *
272 * this callback can be used to further modify the subproblem by changes other than variable fixings.
273 * Typical modifications include restrictions of variable domains, the formulation of additional constraints,
274 * or changed objective coefficients.
275 *
276 * The callback should set the \p success pointer to indicate whether it was successful with its modifications or not.
277 */
278#define DECL_CHANGESUBSCIP(x) SCIP_RETCODE x ( \
279 SCIP* sourcescip, /**< source SCIP data structure */\
280 SCIP* targetscip, /**< target SCIP data structure */\
281 NH* neighborhood, /**< ALNS neighborhood data structure */\
282 SCIP_VAR** subvars, /**< array of targetscip variables in the same order as the source SCIP variables */\
283 int* ndomchgs, /**< pointer to store the number of performed domain changes */\
284 int* nchgobjs, /**< pointer to store the number of changed objective coefficients */ \
285 int* naddedconss, /**< pointer to store the number of additional constraints */\
286 SCIP_Bool* success /**< pointer to store if the sub-MIP was successfully adjusted */\
287 )
288
289/** optional initialization callback for neighborhoods when a new problem is read */
290#define DECL_NHINIT(x) SCIP_RETCODE x ( \
291 SCIP* scip, /**< SCIP data structure */ \
292 NH* neighborhood /**< neighborhood data structure */ \
293 )
294
295/** deinitialization callback for neighborhoods when exiting a problem */
296#define DECL_NHEXIT(x) SCIP_RETCODE x ( \
297 SCIP* scip, /**< SCIP data structure */ \
298 NH* neighborhood /**< neighborhood data structure */ \
299 )
300
301/** deinitialization callback for neighborhoods before SCIP is freed */
302#define DECL_NHFREE(x) SCIP_RETCODE x ( \
303 SCIP* scip, /**< SCIP data structure */ \
304 NH* neighborhood /**< neighborhood data structure */ \
305 )
306
307/** callback function to return a feasible reference solution for further fixings
308 *
309 * The reference solution should be stored in the \p solptr.
310 * The \p result pointer can be used to indicate either
311 *
312 * - SCIP_SUCCESS or
313 * - SCIP_DIDNOTFIND
314 */
315#define DECL_NHREFSOL(x) SCIP_RETCODE x ( \
316 SCIP* scip, /**< SCIP data structure */ \
317 NH* neighborhood, /**< neighborhood data structure */ \
318 SCIP_SOL** solptr, /**< pointer to store the reference solution */ \
319 SCIP_RESULT* result /**< pointer to indicate the callback success whether a reference solution is available */ \
320 )
321
322/** callback function to deactivate neighborhoods on problems where they are irrelevant */
323#define DECL_NHDEACTIVATE(x) SCIP_RETCODE x (\
324 SCIP* scip, /**< SCIP data structure */ \
325 SCIP_Bool* deactivate /**< pointer to store whether the neighborhood should be deactivated (TRUE) for an instance */ \
326 )
327
328/** sub-SCIP status code enumerator */
330{
331 HIDX_OPT = 0, /**< sub-SCIP was solved to optimality */
332 HIDX_USR = 1, /**< sub-SCIP was user interrupted */
333 HIDX_NODELIM = 2, /**< sub-SCIP reached the node limit */
334 HIDX_STALLNODE = 3, /**< sub-SCIP reached the stall node limit */
335 HIDX_INFEAS = 4, /**< sub-SCIP was infeasible */
336 HIDX_SOLLIM = 5, /**< sub-SCIP reached the solution limit */
337 HIDX_OTHER = 6 /**< sub-SCIP reached none of the above codes */
339typedef enum HistIndex HISTINDEX;
340#define NHISTENTRIES 7
341
342
343/** statistics for a neighborhood */
345{
346 SCIP_CLOCK* setupclock; /**< clock for sub-SCIP setup time */
347 SCIP_CLOCK* submipclock; /**< clock for the sub-SCIP solve */
348 SCIP_Longint usednodes; /**< total number of used nodes */
349 SCIP_Real oldupperbound; /**< upper bound before the sub-SCIP started */
350 SCIP_Real newupperbound; /**< new upper bound for allrewards mode to work correctly */
351 int nruns; /**< number of runs of a neighborhood */
352 int nrunsbestsol; /**< number of runs that produced a new incumbent */
353 SCIP_Longint nsolsfound; /**< the total number of solutions found */
354 SCIP_Longint nbestsolsfound; /**< the total number of improving solutions found */
355 int nfixings; /**< the number of fixings in one run */
356 int statushist[NHISTENTRIES]; /**< array to count sub-SCIP statuses */
357};
358
359
360/** fixing rate data structure to control the amount of target fixings of a neighborhood */
362{
363 SCIP_Real minfixingrate; /**< the minimum fixing rate */
364 SCIP_Real targetfixingrate; /**< the current target fixing rate */
365 SCIP_Real increment; /**< the current increment by which the target fixing rate is in-/decreased */
366 SCIP_Real maxfixingrate; /**< the maximum fixing rate */
367};
368
369/** neighborhood data structure with callbacks, statistics, fixing rate */
370struct Nh
371{
372 char* name; /**< the name of this neighborhood */
373 NH_FIXINGRATE fixingrate; /**< fixing rate for this neighborhood */
374 NH_STATS stats; /**< statistics for this neighborhood */
375 DECL_VARFIXINGS ((*varfixings)); /**< variable fixings callback for this neighborhood */
376 DECL_CHANGESUBSCIP ((*changesubscip)); /**< callback for subproblem changes other than variable fixings */
377 DECL_NHINIT ((*nhinit)); /**< initialization callback when a new problem is read */
378 DECL_NHEXIT ((*nhexit)); /**< deinitialization callback when exiting a problem */
379 DECL_NHFREE ((*nhfree)); /**< deinitialization callback before SCIP is freed */
380 DECL_NHREFSOL ((*nhrefsol)); /**< callback function to return a reference solution for further fixings, or NULL */
381 DECL_NHDEACTIVATE ((*nhdeactivate)); /**< callback function to deactivate neighborhoods on problems where they are irrelevant, or NULL if it is always active */
382 SCIP_Bool active; /**< is this neighborhood active or not? */
383 SCIP_Real priority; /**< positive call priority to initialize bandit algorithms */
384 union
385 {
386 DATA_MUTATION* mutation; /**< mutation data */
387 DATA_CROSSOVER* crossover; /**< crossover data */
388 DATA_DINS* dins; /**< dins data */
389 DATA_TRUSTREGION* trustregion; /**< trustregion data */
390 } data; /**< data object for neighborhood specific data */
391};
392
393/** mutation neighborhood data structure */
395{
396 SCIP_RANDNUMGEN* rng; /**< random number generator */
397};
398
399/** crossover neighborhood data structure */
401{
402 int nsols; /**< the number of solutions that crossover should combine */
403 SCIP_RANDNUMGEN* rng; /**< random number generator to draw from the solution pool */
404 SCIP_SOL* selsol; /**< best selected solution by crossover as reference point */
405};
406
407/** dins neighborhood data structure */
409{
410 int npoolsols; /**< number of pool solutions where binary solution values must agree */
411};
412
414{
415 SCIP_Real violpenalty; /**< the penalty for violating the trust region */
416};
417
418/** primal heuristic data */
419struct SCIP_HeurData
420{
421 NH** neighborhoods; /**< array of neighborhoods */
422 SCIP_BANDIT* bandit; /**< bandit algorithm */
423 SCIP_SOL* lastcallsol; /**< incumbent when the heuristic was last called */
424 char* rewardfilename; /**< file name to store all rewards and the selection of the bandit */
425 FILE* rewardfile; /**< reward file pointer, or NULL */
426 SCIP_Longint nodesoffset; /**< offset added to the nodes budget */
427 SCIP_Longint maxnodes; /**< maximum number of nodes in a single sub-SCIP */
428 SCIP_Longint targetnodes; /**< targeted number of nodes to start a sub-SCIP */
429 SCIP_Longint minnodes; /**< minimum number of nodes required to start a sub-SCIP */
430 SCIP_Longint usednodes; /**< total number of nodes already spent in sub-SCIPs */
431 SCIP_Longint waitingnodes; /**< number of nodes since last incumbent solution that the heuristic should wait */
432 SCIP_Real nodesquot; /**< fraction of nodes compared to the main SCIP for budget computation */
433 SCIP_Real nodesquotmin; /**< lower bound on fraction of nodes compared to the main SCIP for budget computation */
434 SCIP_Real startminimprove; /**< initial factor by which ALNS should at least improve the incumbent */
435 SCIP_Real minimprovelow; /**< lower threshold for the minimal improvement over the incumbent */
436 SCIP_Real minimprovehigh; /**< upper bound for the minimal improvement over the incumbent */
437 SCIP_Real minimprove; /**< factor by which ALNS should at least improve the incumbent */
438 SCIP_Real lplimfac; /**< limit fraction of LPs per node to interrupt sub-SCIP */
439 SCIP_Real exp3_gamma; /**< weight between uniform (gamma ~ 1) and weight driven (gamma ~ 0) probability distribution for exp3 */
440 SCIP_Real exp3_beta; /**< reward offset between 0 and 1 at every observation for exp3 */
441 SCIP_Real epsgreedy_eps; /**< increase exploration in epsilon-greedy bandit algorithm */
442 SCIP_Real ucb_alpha; /**< parameter to increase the confidence width in UCB */
443 SCIP_Real rewardcontrol; /**< reward control to increase the weight of the simple solution indicator
444 * and decrease the weight of the closed gap reward */
445 SCIP_Real targetnodefactor; /**< factor by which target node number is eventually increased */
446 SCIP_Real rewardbaseline; /**< the reward baseline to separate successful and failed calls */
447 SCIP_Real fixtol; /**< tolerance by which the fixing rate may be missed without generic fixing */
448 SCIP_Real unfixtol; /**< tolerance by which the fixing rate may be exceeded without generic unfixing */
449 int nneighborhoods; /**< number of neighborhoods */
450 int nactiveneighborhoods;/**< number of active neighborhoods */
451 int ninitneighborhoods; /**< neighborhoods that were used at least one time */
452 int nsolslim; /**< limit on the number of improving solutions in a sub-SCIP call */
453 int seed; /**< initial random seed for bandit algorithms and random decisions by neighborhoods */
454 int currneighborhood; /**< index of currently selected neighborhood */
455 int ndelayedcalls; /**< the number of delayed calls */
456 int maxcallssamesol; /**< number of allowed executions of the heuristic on the same incumbent solution
457 * (-1: no limit, 0: number of active neighborhoods) */
458 SCIP_Longint firstcallthissol; /**< counter for the number of calls on this incumbent */
459 char banditalgo; /**< the bandit algorithm: (u)pper confidence bounds, (e)xp.3, epsilon (g)reedy */
460 SCIP_Bool useredcost; /**< should reduced cost scores be used for variable prioritization? */
461 SCIP_Bool usedistances; /**< should distances from fixed variables be used for variable prioritization */
462 SCIP_Bool usepscost; /**< should pseudo cost scores be used for variable prioritization? */
463 SCIP_Bool domorefixings; /**< should the ALNS heuristic do more fixings by itself based on variable prioritization
464 * until the target fixing rate is reached? */
465 SCIP_Bool adjustfixingrate; /**< should the heuristic adjust the target fixing rate based on the success? */
466 SCIP_Bool usesubscipheurs; /**< should the heuristic activate other sub-SCIP heuristics during its search? */
467 SCIP_Bool adjustminimprove; /**< should the factor by which the minimum improvement is bound be dynamically updated? */
468 SCIP_Bool adjusttargetnodes; /**< should the target nodes be dynamically adjusted? */
469 SCIP_Bool resetweights; /**< should the bandit algorithms be reset when a new problem is read? */
470 SCIP_Bool subsciprandseeds; /**< should random seeds of sub-SCIPs be altered to increase diversification? */
471 SCIP_Bool scalebyeffort; /**< should the reward be scaled by the effort? */
472 SCIP_Bool copycuts; /**< should cutting planes be copied to the sub-SCIP? */
473 SCIP_Bool uselocalredcost; /**< should local reduced costs be used for generic (un)fixing? */
474 SCIP_Bool initduringroot; /**< should the heuristic be executed multiple times during the root node? */
475 SCIP_Bool shownbstats; /**< show statistics on neighborhoods? */
476};
477
478/** event handler data */
479struct SCIP_EventData
480{
481 SCIP_VAR** subvars; /**< the variables of the subproblem */
482 SCIP* sourcescip; /**< original SCIP data structure */
483 SCIP_HEUR* heur; /**< alns heuristic structure */
484 SCIP_Longint nodelimit; /**< node limit of the run */
485 SCIP_Real lplimfac; /**< limit fraction of LPs per node to interrupt sub-SCIP */
486 NH_STATS* runstats; /**< run statistics for the current neighborhood */
487 SCIP_Bool allrewardsmode; /**< true if solutions should only be checked for reward comparisons */
488};
489
490/** represents limits for the sub-SCIP solving process */
492{
493 SCIP_Longint nodelimit; /**< maximum number of solving nodes for the sub-SCIP */
494 SCIP_Real memorylimit; /**< memory limit for the sub-SCIP */
495 SCIP_Real timelimit; /**< time limit for the sub-SCIP */
496 SCIP_Longint stallnodes; /**< maximum number of nodes without (primal) stalling */
497};
498
500
501/** data structure that can be used for variable prioritization for additional fixings */
503{
504 SCIP* scip; /**< SCIP data structure */
505 SCIP_Real* randscores; /**< random scores for prioritization */
506 int* distances; /**< breadth-first distances from already fixed variables */
507 SCIP_Real* redcostscores; /**< reduced cost scores for fixing a variable to a reference value */
508 SCIP_Real* pscostscores; /**< pseudocost scores for fixing a variable to a reference value */
509 unsigned int useredcost:1; /**< should reduced cost scores be used for variable prioritization? */
510 unsigned int usedistances:1; /**< should distances from fixed variables be used for variable prioritization */
511 unsigned int usepscost:1; /**< should pseudo cost scores be used for variable prioritization? */
512};
513
514/*
515 * Local methods
516 */
517
518/** Reset target fixing rate */
519static
521 SCIP* scip, /**< SCIP data structure */
522 NH_FIXINGRATE* fixingrate /**< heuristic fixing rate */
523 )
524{
525 assert(scip != NULL);
526 assert(fixingrate != NULL);
527 fixingrate->increment = FIXINGRATE_STARTINC;
528
529 /* always start with the most conservative value */
530 fixingrate->targetfixingrate = fixingrate->maxfixingrate;
531
532 return SCIP_OKAY;
533}
534
535/** reset the currently active neighborhood */
536static
539 )
540{
541 assert(heurdata != NULL);
542 heurdata->currneighborhood = -1;
543 heurdata->ndelayedcalls = 0;
544}
545
546/** update increment for fixing rate */
547static
549 NH_FIXINGRATE* fx /**< fixing rate */
550 )
551{
552 fx->increment *= FIXINGRATE_DECAY;
553 fx->increment = MAX(fx->increment, LRATEMIN);
554}
555
556
557/** increase fixing rate
558 *
559 * decrease also the rate by which the target fixing rate is adjusted
560 */
561static
563 NH_FIXINGRATE* fx /**< fixing rate */
564 )
565{
566 fx->targetfixingrate += fx->increment;
567 fx->targetfixingrate = MIN(fx->targetfixingrate, fx->maxfixingrate);
568}
569
570/** decrease fixing rate
571 *
572 * decrease also the rate by which the target fixing rate is adjusted
573 */
574static
576 NH_FIXINGRATE* fx /**< fixing rate */
577 )
578{
579 fx->targetfixingrate -= fx->increment;
580 fx->targetfixingrate = MAX(fx->targetfixingrate, fx->minfixingrate);
581}
582
583/** update fixing rate based on the results of the current run */
584static
586 NH* neighborhood, /**< neighborhood */
587 SCIP_STATUS subscipstatus, /**< status of the sub-SCIP run */
588 NH_STATS* runstats /**< run statistics for this run */
589 )
590{
592
593 fx = &neighborhood->fixingrate;
594
595 switch (subscipstatus)
596 {
602 /* decrease the fixing rate (make subproblem harder) */
604 break;
609 /* increase the fixing rate (make the subproblem easier) only if no solution was found */
610 if( runstats->nbestsolsfound <= 0 )
612 break;
613 /* fall through cases to please lint */
621 default:
622 break;
623 }
624
626}
627
628/** increase target node limit */
629static
631 SCIP_HEURDATA* heurdata /**< heuristic data */
632 )
633{
634 heurdata->targetnodes = (SCIP_Longint)(heurdata->targetnodes * heurdata->targetnodefactor) + 1;
635
636 /* respect upper and lower parametrized bounds on targetnodes */
637 if( heurdata->targetnodes > heurdata->maxnodes )
638 heurdata->targetnodes = heurdata->maxnodes;
639}
640
641/** reset target node limit */
642static
644 SCIP_HEURDATA* heurdata /**< heuristic data */
645 )
646{
647 heurdata->targetnodes = heurdata->minnodes;
648}
649
650/** update target node limit based on the current run results */
651static
653 SCIP_HEURDATA* heurdata, /**< heuristic data */
654 NH_STATS* runstats, /**< statistics of the run */
655 SCIP_STATUS subscipstatus /**< status of the sub-SCIP run */
656 )
657{
658 switch (subscipstatus)
659 {
662 /* the subproblem could be explored more */
663 if( runstats->nbestsolsfound == 0 )
665 break;
671 break;
681 break;
682 default:
683 break;
684 }
685}
686
687/** reset the minimum improvement for the sub-SCIPs */
688static
690 SCIP_HEURDATA* heurdata /**< heuristic data */
691 )
692{
693 assert(heurdata != NULL);
694 heurdata->minimprove = heurdata->startminimprove;
695}
696
697/** increase minimum improvement for the sub-SCIPs */
698static
700 SCIP_HEURDATA* heurdata /**< heuristic data */
701 )
702{
703 assert(heurdata != NULL);
704
705 heurdata->minimprove *= MINIMPROVEFAC;
706 heurdata->minimprove = MIN(heurdata->minimprove, heurdata->minimprovehigh);
707}
708
709/** decrease the minimum improvement for the sub-SCIPs */
710static
712 SCIP_HEURDATA* heurdata /**< heuristic data */
713 )
714{
715 assert(heurdata != NULL);
716
717 heurdata->minimprove /= MINIMPROVEFAC;
718 SCIPdebugMessage("%.4f", heurdata->minimprovelow);
719 heurdata->minimprove = MAX(heurdata->minimprove, heurdata->minimprovelow);
720}
721
722/** update the minimum improvement based on the status of the sub-SCIP */
723static
725 SCIP_HEURDATA* heurdata, /**< heuristic data */
726 SCIP_STATUS subscipstatus, /**< status of the sub-SCIP run */
727 NH_STATS* runstats /**< run statistics for this run */
728 )
729{
730 assert(heurdata != NULL);
731
732 /* if the sub-SCIP status was infeasible, we rather want to make the sub-SCIP easier
733 * with a smaller minimum improvement.
734 *
735 * If a solution limit was reached, we may, set it higher.
736 */
737 switch (subscipstatus)
738 {
741 /* subproblem was infeasible, probably due to the minimum improvement -> decrease minimum improvement */
743
744 break;
748 /* subproblem could be optimally solved -> try higher minimum improvement */
750 break;
754 /* subproblem was too hard, decrease minimum improvement */
755 if( runstats->nbestsolsfound <= 0 )
757 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);
821 assert(name != NULL);
822
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);
869
871 assert(nhptr != NULL);
872
874
875 /* release further, neighborhood specific data structures */
876 if( nhptr->nhfree != NULL )
877 {
878 SCIP_CALL( nhptr->nhfree(scip, nhptr) );
879 }
880
881 SCIP_CALL( SCIPfreeClock(scip, &nhptr->stats.setupclock) );
882 SCIP_CALL( SCIPfreeClock(scip, &nhptr->stats.submipclock) );
883
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);
899
900 /* call the init callback of the neighborhood */
901 if( neighborhood->nhinit != NULL )
902 {
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);
918
919 if( neighborhood->nhexit != NULL )
920 {
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;
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 {
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 */
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);
1010 assert(event != NULL);
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 {
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':
1140 break;
1141 case 'g':
1143 break;
1144 case 'e':
1146 break;
1147 case '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 */
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}*/
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
1303
1304 /* using global reduced costs, the two factors yield a nonnegative score within tolerances */
1308 }
1309 else
1310 {
1311 /* this can be safely asserted here, since the heuristic would not reach this point, otherwise */
1314
1315 redcost = SCIPgetVarRedcost(scip, var);
1316
1318 }
1319
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
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 */
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);
1408
1409 *solptr = NULL;
1410 if( neighborhood->nhrefsol != NULL )
1411 {
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{
1445 SCIP_VAR** vars;
1446 SCIP_Real* redcostscores;
1447 SCIP_Real* pscostscores;
1448 SCIP_Real* solvals;
1449 SCIP_RANDNUMGEN* rng;
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
1477
1479
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
1497 SCIP_CALL( SCIPallocBufferArray(scip, &distances, nvars) );
1498 SCIP_CALL( SCIPallocBufferArray(scip, &redcostscores, nbinintvars) );
1502 SCIP_CALL( SCIPallocBufferArray(scip, &pscostscores, nbinintvars) );
1503
1504 /* initialize variable graph distances from already fixed variables */
1505 if( varprio.usedistances )
1506 {
1508 }
1509 else
1510 {
1511 /* initialize all equal distances to make them irrelevant */
1512 BMSclearMemoryArray(distances, nbinintvars);
1513 }
1514
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
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
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
1571
1572 /* select the first nvarstoadd many variables according to the score */
1573 if( 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);
1582
1584 }
1585
1586 *success = TRUE;
1587
1588 /* free buffer arrays */
1589 SCIPfreeBufferArray(scip, &pscostscores);
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{
1675 SCIP_Real* redcostscores;
1676 SCIP_Real* pscostscores;
1677 SCIP_Real* randscores;
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
1695 if( nbinintvars == 0 )
1696 return SCIP_OKAY;
1697
1698 assert(*nfixings > 0);
1699
1701 SCIP_CALL( SCIPallocBufferArray(scip, &isfixedvar, nvars) );
1703 SCIP_CALL( SCIPallocBufferArray(scip, &distances, nvars) );
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
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;
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 {
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 {
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 {
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 */
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 */
1795 SCIPfreeBufferArray(scip, &pscostscores);
1796 SCIPfreeBufferArray(scip, &perm);
1797 SCIPfreeBufferArray(scip, &randscores);
1798 SCIPfreeBufferArray(scip, &redcostscores);
1800 SCIPfreeBufferArray(scip, &distances);
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);
1828 assert(varbuf != NULL);
1829 assert(valbuf != NULL);
1830 assert(nfixings != NULL);
1831 assert(result != NULL);
1832
1833 *nfixings = 0;
1834
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 {
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);
1855 ntargetfixings = (int)(neighborhood->fixingrate.targetfixingrate * nbinintvars);
1856 nminfixings = (int)((neighborhood->fixingrate.targetfixingrate - heurdata->fixtol) * nbinintvars);
1858 nmaxfixings = (int)((neighborhood->fixingrate.targetfixingrate + heurdata->unfixtol) * 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;
1868
1869 /* get reference solution from neighborhood */
1871
1872 /* try to fix more variables based on the reference solution */
1873 if( refsol != NULL )
1874 {
1876 }
1877 else
1878 success = FALSE;
1879
1880 if( success )
1882 else if( *result == SCIP_SUCCESS )
1884 else
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
1894
1895 assert(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);
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);
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{
1977 SCIP_Real initfactor;
1978 SCIP_Real nodesquot;
1979 SCIP_Bool avoidmemout;
1980
1981 assert(scip != NULL);
1982 assert(heur != 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);
2057
2058 *neighborhoodidx = -1;
2059
2060 bandit = getBandit(heurdata);
2061
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 */
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) )
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
2141 reward = heurdata->rewardbaseline * rewardptr[REWARDTYPE_NOSOLPENALTY];
2142 }
2143
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);
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{
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) )
2270
2271 SCIPdebugMsg(scip, "Sub-SCIP cutoff: %15.9" SCIP_REAL_FORMAT " (%15.9" SCIP_REAL_FORMAT " in original space)\n",
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
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}*/
2328 SCIP_VAR** varbuf;
2329 SCIP_Real* valbuf;
2330 SCIP_VAR** vars;
2331 SCIP_VAR** subvars;
2332 NH_STATS runstats[NNEIGHBORHOODS];
2334 SCIP* subscip = NULL;
2335
2336 int nfixings;
2337 int nvars;
2338 int neighborhoodidx;
2339 int ntries;
2340 SCIP_Bool tryagain;
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
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
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 */
2402 {
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 */
2424 {
2425 SCIPdebugMsg(scip, "Delay ALNS heuristic until a feasible node with optimally solved LP relaxation\n");
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 {
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 )
2447 else
2448 neighborhoodidx = 0;
2449
2451 assert(heurdata->nactiveneighborhoods > neighborhoodidx);
2452
2453 /* allocate memory for variable fixings buffer */
2458
2459 /* initialize neighborhood statistics for a run */
2460 ntries = 1;
2461 do
2462 {
2464 SCIP_EVENTHDLR* eventhdlr;
2465 SCIP_EVENTDATA eventdata;
2467 SCIP_Real allfixingrate;
2468 int ndomchgs;
2469 int nchgobjs;
2470 int naddedconss;
2471 int v;
2472 SCIP_RETCODE retcode;
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]);
2481
2483 SCIP_CALL( SCIPstartClock(scip, neighborhood->stats.setupclock) );
2484
2485 /* determine variable fixings and objective coefficients of this neighborhood */
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 {
2521
2522 /* use SCIP_DIDNOTFIND to penalize the neighborhood with a bad reward */
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 {
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
2553 *result = fixresult;
2554 break;
2555 }
2556
2558
2559 neighborhood->stats.nfixings += nfixings;
2560 runstats[neighborhoodidx].nfixings = nfixings;
2561
2562 SCIP_CALL( SCIPcreate(&subscip) );
2565
2566 /* todo later: run global propagation for this set of fixings */
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
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 */
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 */
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);
2655 SCIPdebugMsg(scip, "Status of sub-SCIP run: %d\n", subscipstatus[neighborhoodidx]);
2656
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);
2679
2680 /* update bandit index that may have changed unless we are in all rewards mode */
2681 if( ! allrewardsmode )
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 */
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);
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 {
2716 }
2717
2718 /* update the bandit algorithm by the measured reward */
2720
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
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
2756
2757 if( ! SCIPhasCurrentNodeLP(scip) )
2758 return SCIP_OKAY;
2760 return SCIP_OKAY;
2761
2763
2764 /* get variable information */
2766
2767 /* return if no binary or integer variables are present */
2768 if( nbinvars + nintvars == 0 )
2769 return SCIP_OKAY;
2770
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);
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 */
2796 {
2798
2799 /* prefer variables that are almost integer */
2800 for( i = 0; i < nfracs && *nfixings < neighborhood->fixingrate.targetfixingrate * (nbinvars + nintvars); i++ )
2801 {
2803 }
2804 }
2805
2808
2810
2811 return SCIP_OKAY;
2812}
2813
2814/** callback for RENS subproblem changes */
2815static
2817{ /*lint --e{715}*/
2818 SCIP_VAR** vars;
2819 int nintvars;
2820 int nbinvars;
2821 int i;
2822
2823 assert(SCIPhasCurrentNodeLP(sourcescip));
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 {
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;
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;
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];
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
2929{
2930 /*lint --e{715}*/
2931 int nbinvars;
2932 int nintvars;
2933 SCIP_VAR** vars;
2935 SCIP_SOL* sols[2];
2936 assert(scip != NULL);
2937 assert(varbuf != NULL);
2938 assert(nfixings != NULL);
2939 assert(valbuf != NULL);
2940
2942
2943 if( ! SCIPhasCurrentNodeLP(scip) )
2944 return SCIP_OKAY;
2946 return SCIP_OKAY;
2947
2949
2951 if( incumbent == NULL )
2952 return SCIP_OKAY;
2953
2955 return SCIP_OKAY;
2956
2957 /* get variable information */
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
2968
2970
2971 return SCIP_OKAY;
2972}
2973
2974/** initialization callback for crossover when a new problem is read */
2975static
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
2996{ /*lint --e{715}*/
2997 DATA_CROSSOVER* data;
2998 data = neighborhood->data.crossover;
2999
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
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
3021{ /*lint --e{715}*/
3022 DATA_CROSSOVER* data;
3023 SCIP_RANDNUMGEN* rng;
3024 SCIP_SOL** sols;
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
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;
3051 SCIP_CALL( SCIPallocBufferArray(scip, &sols, nsols) );
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--;
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
3093
3094 SCIPfreeBufferArray(scip, &sols);
3095
3096 return SCIP_OKAY;
3097}
3098
3099/** callback for crossover reference solution */
3100static
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;
3111 }
3112 else
3113 {
3115 }
3116
3117 return SCIP_OKAY;
3118}
3119
3120/** initialization callback for mutation when a new problem is read */
3121static
3123{ /*lint --e{715}*/
3124 DATA_MUTATION* data;
3125 assert(scip != 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
3141{ /*lint --e{715}*/
3142 DATA_MUTATION* data;
3143 assert(scip != 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
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;
3170 SCIP_Real targetfixingrate;
3171
3172 assert(scip != NULL);
3174 assert(neighborhood->data.mutation != NULL);
3175 assert(neighborhood->data.mutation->rng != NULL);
3176 rng = neighborhood->data.mutation->rng;
3177
3179
3180 /* get the problem variables */
3182
3184 if( nbinintvars == 0 )
3185 return SCIP_OKAY;
3186
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 */
3196 return SCIP_OKAY;
3197
3199
3200 /* copy variables into a buffer array */
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);
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 */
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 )
3226
3227 /* free the buffer array */
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;
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
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) );
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
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
3312{ /*lint --e{715}*/
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
3364{ /*lint --e{715}*/
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");
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 */
3420
3422 /* get the current LP solution for each variable */
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 {
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 {
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
3478{
3479 DATA_DINS* data;
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);
3492 nmipsols = MIN(nmipsols, data->npoolsols);
3493
3495
3497 return SCIP_OKAY;
3498
3500
3501 if( nmipsols == 0 )
3502 return SCIP_OKAY;
3503
3505
3506 if( nbinvars + nintvars == 0 )
3507 return SCIP_OKAY;
3508
3510
3511 /* save root solution LP values in solution */
3512 for( v = 0; v < nbinvars + nintvars; ++v )
3513 {
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;
3539
3540 if( ub - lb < 0.5 )
3541 {
3543 tryAdd2variableBuffer(scip, vars[v], lb, varbuf, valbuf, nfixings, TRUE);
3544 }
3545 }
3546
3548
3549 SCIPfreeBufferArray(scip, &sols);
3550
3552
3553 return SCIP_OKAY;
3554}
3555
3556/** callback for DINS subproblem changes */
3557static
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
3595{
3596 assert(neighborhood->data.dins != NULL);
3597
3599
3600 return SCIP_OKAY;
3601}
3602
3603/** deinitialization callback for trustregion before SCIP is freed */
3604static
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
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 */
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
3646{ /*lint --e{715}*/
3647 assert(scip != NULL);
3648
3649 if( SCIPgetBestSol(scip) != NULL )
3650 {
3653 }
3654 else
3655 {
3657 }
3658
3659 return SCIP_OKAY;
3660}
3661
3662
3663/** callback function that deactivates a neighborhood on problems with no discrete variables */
3664static
3666{ /*lint --e{715}*/
3667 assert(scip != NULL);
3669
3670 /* deactivate if no discrete variables are present */
3672
3673 return SCIP_OKAY;
3674}
3675
3676/** callback function that deactivates a neighborhood on problems with no binary variables */
3677static
3679{ /*lint --e{715}*/
3680 assert(scip != 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
3692{ /*lint --e{715}*/
3693 assert(scip != 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;
3714 NH* crossover;
3715 NH* proximity;
3717 NH* dins;
3718 NH* trustregion;
3719
3720 heurdata->nneighborhoods = 0;
3721
3722 /* include the RENS neighborhood */
3726
3727 /* include the RINS neighborhood */
3731
3732 /* include the mutation neighborhood */
3733 SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &mutation, "mutation",
3736
3737 /* include the local branching neighborhood */
3741
3742 /* include the crossover neighborhood */
3743 SCIP_CALL( alnsIncludeNeighborhood(scip, heurdata, &crossover, "crossover",
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 */
3760
3761 /* include the Zeroobjective neighborhood */
3765
3766 /* include the DINS neighborhood */
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",
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}*/
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
3816
3817 SCIP_CALL( resetFixingRate(scip, &neighborhood->fixingrate) );
3818
3820 }
3821
3822 /* open reward file for reading */
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}*/
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
3902 }
3903 else if( heurdata->resetweights )
3904 {
3905 SCIP_CALL( SCIPresetBandit(scip, heurdata->bandit, priorities, initseed) );
3906
3909 }
3910 }
3911
3912 heurdata->usednodes = 0;
3913 heurdata->ninitneighborhoods = heurdata->nactiveneighborhoods;
3914
3915 heurdata->lastcallsol = NULL;
3916 heurdata->firstcallthissol = 0;
3917
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}*/
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
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}*/
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
3982
3984
3985 return SCIP_OKAY;
3986}
3987
3988/** output method of statistics table to output file stream 'file' */
3989static
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{
4013 SCIP_HEUR* heur;
4014
4015 /* create alns primal heuristic data */
4016 heurdata = NULL;
4017 heur = NULL;
4018
4021
4022 /* TODO make this a user parameter? */
4023 heurdata->lplimfac = LPLIMFAC;
4024
4026
4027 /* include primal heuristic */
4031
4032 assert(heur != NULL);
4033
4034 /* include all neighborhoods */
4036
4037 /* set non fundamental callbacks via setter functions */
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",
4052
4053 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
4054 "offset added to the nodes budget",
4056
4057 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
4058 "minimum number of nodes required to start a sub-SCIP",
4060
4061 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/waitingnodes",
4062 "number of nodes since last incumbent solution that the heuristic should wait",
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, "uegib", 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
4199
4200 return SCIP_OKAY;
4201}
static GRAPHNODE ** active
SCIP_VAR ** b
Constraint handler for linear constraints in their most general form, .
#define NULL
Definition def.h:267
#define SCIP_MAXSTRLEN
Definition def.h:288
#define SCIP_Longint
Definition def.h:158
#define SCIP_REAL_MAX
Definition def.h:174
#define MIN(x, y)
Definition def.h:243
#define SCIP_ALLOC(x)
Definition def.h:385
#define SCIP_Real
Definition def.h:173
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define MAX(x, y)
Definition def.h:239
#define SCIP_CALL_ABORT(x)
Definition def.h:353
#define SCIP_LONGINT_FORMAT
Definition def.h:165
#define SCIPABORT()
Definition def.h:346
#define REALABS(x)
Definition def.h:197
#define SCIP_LONGINT_MAX
Definition def.h:159
#define SCIP_REAL_FORMAT
Definition def.h:176
#define SCIP_CALL(x)
Definition def.h:374
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)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
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:3108
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3261
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition misc.c:3074
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
#define SCIPdebugMsg
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
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:10396
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)
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)
SCIP_Real SCIPgetProbabilityExp3(SCIP_BANDIT *exp3, int action)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
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 SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:178
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 SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:226
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition heur.c:1599
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:162
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition heur.c:1579
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition scip_heur.c:258
int SCIPheurGetFreq(SCIP_HEUR *heur)
Definition heur.c:1538
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:210
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:194
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)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition scip_sol.c:2169
SCIP_SOLORIGIN SCIPsolGetOrigin(SCIP_SOL *sol)
Definition sol.c:2711
SCIP_Longint SCIPsolGetNodenum(SCIP_SOL *sol)
Definition sol.c:2784
int SCIPgetNSols(SCIP *scip)
Definition scip_sol.c:2070
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition scip_sol.c:1254
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition scip_sol.c:2119
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:3251
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:3050
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition scip_sol.c:1077
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1217
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1347
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition scip_sol.c:1432
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition scip_solve.c:222
SCIP_RETCODE SCIPpresolve(SCIP *scip)
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
SCIP_RETCODE SCIPsolve(SCIP *scip)
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)
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)
SCIP_RETCODE SCIPstopClock(SCIP *scip, SCIP_CLOCK *clck)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_RETCODE SCIPfreeClock(SCIP *scip, SCIP_CLOCK **clck)
SCIP_Real SCIPgetClockTime(SCIP *scip, SCIP_CLOCK *clck)
SCIP_RETCODE SCIPstartClock(SCIP *scip, SCIP_CLOCK *clck)
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:670
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:17599
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:17538
SCIP_Real SCIPvarGetBestRootSol(SCIP_VAR *var)
Definition var.c:13715
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition var.c:17926
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:18088
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition var.c:17768
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17419
SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition var.c:13350
SCIP_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition scip_var.c:4945
SCIP_Real SCIPgetVarPseudocostVal(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta)
Definition scip_var.c:8816
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition var.c:17610
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition var.c:18452
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition scip_var.c:5034
SCIP_Real SCIPgetVarRedcost(SCIP *scip, SCIP_VAR *var)
Definition scip_var.c:1866
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:18078
SCIP_Real SCIPvarGetBestRootRedcost(SCIP_VAR *var)
Definition var.c:13782
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition scip_var.c:4515
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition misc.c:10130
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition misc.c:10108
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:10877
return SCIP_OKAY
SCIPfreeSol(scip, &heurdata->sol))
SCIPcreateSol(scip, &heurdata->sol, heur))
SCIPfreeRandom(scip, &heurdata->randnumgen)
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:173
#define DEFAULT_MINFIXINGRATE_ZEROOBJECTIVE
Definition heur_alns.c:191
enum HistIndex HISTINDEX
Definition heur_alns.c:339
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:296
static SCIP_RETCODE alnsFreeNeighborhood(SCIP *scip, NH **neighborhood)
Definition heur_alns.c:861
#define TABLE_POSITION_NEIGHBORHOOD
Definition heur_alns.c:219
#define DEFAULT_NODESQUOT
Definition heur_alns.c:95
static void increaseFixingRate(NH_FIXINGRATE *fx)
Definition heur_alns.c:562
#define DEFAULT_MINIMPROVEHIGH
Definition heur_alns.c:112
#define DEFAULT_MAXCALLSSAMESOL
Definition heur_alns.c:106
#define NNEIGHBORHOODS
Definition heur_alns.c:88
#define DEFAULT_NSOLSLIM
Definition heur_alns.c:98
#define DECL_NHDEACTIVATE(x)
Definition heur_alns.c:323
static SCIP_RETCODE neighborhoodStatsReset(SCIP *scip, NH_STATS *stats)
Definition heur_alns.c:773
#define DEFAULT_MINIMPROVELOW
Definition heur_alns.c:111
#define DEFAULT_REWARDBASELINE
Definition heur_alns.c:127
#define DEFAULT_PRIORITY_RENS
Definition heur_alns.c:164
#define DEFAULT_ACTIVE_PROXIMITY
Definition heur_alns.c:183
#define DEFAULT_NODESQUOTMIN
Definition heur_alns.c:96
#define DEFAULT_MINFIXINGRATE_DINS
Definition heur_alns.c:196
#define DEFAULT_SEED
Definition heur_alns.c:156
#define DEFAULT_ACTIVE_RINS
Definition heur_alns.c:168
static void updateNeighborhoodStats(NH_STATS *runstats, NH *neighborhood, SCIP_STATUS subscipstatus)
Definition heur_alns.c:1172
#define TABLE_NAME_NEIGHBORHOOD
Definition heur_alns.c:217
#define DEFAULT_COPYCUTS
Definition heur_alns.c:152
#define DEFAULT_MAXNODES
Definition heur_alns.c:100
static SCIP_RETCODE neighborhoodGetRefsol(SCIP *scip, NH *neighborhood, SCIP_SOL **solptr)
Definition heur_alns.c:1399
#define DEFAULT_USEREDCOST
Definition heur_alns.c:143
#define HEUR_TIMING
Definition heur_alns.c:85
#define DEFAULT_MINNODES
Definition heur_alns.c:99
#define DEFAULT_ADJUSTFIXINGRATE
Definition heur_alns.c:148
#define DEFAULT_ADJUSTMINIMPROVE
Definition heur_alns.c:115
static void decreaseFixingRate(NH_FIXINGRATE *fx)
Definition heur_alns.c:575
#define DECL_NHINIT(x)
Definition heur_alns.c:290
static void increaseMinimumImprovement(SCIP_HEURDATA *heurdata)
Definition heur_alns.c:699
#define DECL_NHFREE(x)
Definition heur_alns.c:302
#define MINIMPROVEFAC
Definition heur_alns.c:113
#define DEFAULT_FIXTOL
Definition heur_alns.c:128
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:83
#define FIXINGRATE_STARTINC
Definition heur_alns.c:150
#define HEUR_DESC
Definition heur_alns.c:79
static void resetMinimumImprovement(SCIP_HEURDATA *heurdata)
Definition heur_alns.c:689
#define DEFAULT_MAXFIXINGRATE_RENS
Definition heur_alns.c:162
#define DEFAULT_PRIORITY_PROXIMITY
Definition heur_alns.c:184
static void resetTargetNodeLimit(SCIP_HEURDATA *heurdata)
Definition heur_alns.c:643
static SCIP_RETCODE neighborhoodInit(SCIP *scip, NH *neighborhood)
Definition heur_alns.c:892
#define DEFAULT_STARTMINIMPROVE
Definition heur_alns.c:114
static SCIP_RETCODE alnsIncludeNeighborhood(SCIP *scip, SCIP_HEURDATA *heurdata, NH **neighborhood, const char *name, SCIP_Real minfixingrate, SCIP_Real maxfixingrate, SCIP_Bool active, SCIP_Real priority, DECL_VARFIXINGS((*varfixings)), DECL_CHANGESUBSCIP((*changesubscip)), DECL_NHINIT((*nhinit)), DECL_NHEXIT((*nhexit)), DECL_NHFREE((*nhfree)), DECL_NHREFSOL((*nhrefsol)),)
Definition heur_alns.c:798
#define DEFAULT_ACTIVE_TRUSTREGION
Definition heur_alns.c:203
#define DEFAULT_MINFIXINGRATE_RENS
Definition heur_alns.c:161
#define DEFAULT_MAXFIXINGRATE_DINS
Definition heur_alns.c:197
#define FIXINGRATE_DECAY
Definition heur_alns.c:149
#define DEFAULT_MINFIXINGRATE_RINS
Definition heur_alns.c:166
#define DEFAULT_PRIORITY_ZEROOBJECTIVE
Definition heur_alns.c:194
static void updateMinimumImprovement(SCIP_HEURDATA *heurdata, SCIP_STATUS subscipstatus, NH_STATS *runstats)
Definition heur_alns.c:724
#define DEFAULT_WAITINGNODES
Definition heur_alns.c:101
#define DEFAULT_NODESOFFSET
Definition heur_alns.c:97
#define TABLE_DESC_NEIGHBORHOOD
Definition heur_alns.c:218
#define DECL_CHANGESUBSCIP(x)
Definition heur_alns.c:278
RewardType
Definition heur_alns.c:223
@ REWARDTYPE_NOSOLPENALTY
Definition heur_alns.c:227
@ REWARDTYPE_BESTSOL
Definition heur_alns.c:225
@ REWARDTYPE_TOTAL
Definition heur_alns.c:224
@ NREWARDTYPES
Definition heur_alns.c:228
@ REWARDTYPE_CLOSEDGAP
Definition heur_alns.c:226
#define DEFAULT_RESETWEIGHTS
Definition heur_alns.c:125
#define HEUR_DISPCHAR
Definition heur_alns.c:80
#define HEUR_MAXDEPTH
Definition heur_alns.c:84
static void increaseTargetNodeLimit(SCIP_HEURDATA *heurdata)
Definition heur_alns.c:630
#define HEUR_PRIORITY
Definition heur_alns.c:81
#define DEFAULT_MAXFIXINGRATE_MUTATION
Definition heur_alns.c:172
#define TABLE_EARLIEST_STAGE_NEIGHBORHOOD
Definition heur_alns.c:220
#define DEFAULT_ADJUSTTARGETNODES
Definition heur_alns.c:116
static void updateTargetNodeLimit(SCIP_HEURDATA *heurdata, NH_STATS *runstats, SCIP_STATUS subscipstatus)
Definition heur_alns.c:652
#define DECL_NHREFSOL(x)
Definition heur_alns.c:315
#define DEFAULT_USELOCALREDCOST
Definition heur_alns.c:130
#define DEFAULT_MAXFIXINGRATE_TRUSTREGION
Definition heur_alns.c:202
#define DEFAULT_MAXFIXINGRATE_ZEROOBJECTIVE
Definition heur_alns.c:192
static void updateFixingRate(NH *neighborhood, SCIP_STATUS subscipstatus, NH_STATS *runstats)
Definition heur_alns.c:585
#define HEUR_NAME
Definition heur_alns.c:78
static void initRunStats(SCIP *scip, NH_STATS *stats)
Definition heur_alns.c:1039
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:163
#define NHISTENTRIES
Definition heur_alns.c:340
static void updateFixingRateIncrement(NH_FIXINGRATE *fx)
Definition heur_alns.c:548
#define DEFAULT_MINFIXINGRATE_CROSSOVER
Definition heur_alns.c:186
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:123
#define DEFAULT_ACTIVE_ZEROOBJECTIVE
Definition heur_alns.c:193
#define DEFAULT_MINFIXINGRATE_LOCALBRANCHING
Definition heur_alns.c:176
#define SCIP_EVENTTYPE_ALNS
Definition heur_alns.c:214
HistIndex
Definition heur_alns.c:330
@ HIDX_STALLNODE
Definition heur_alns.c:334
@ HIDX_OTHER
Definition heur_alns.c:337
@ HIDX_SOLLIM
Definition heur_alns.c:336
@ HIDX_USR
Definition heur_alns.c:332
@ HIDX_OPT
Definition heur_alns.c:331
@ HIDX_INFEAS
Definition heur_alns.c:335
@ HIDX_NODELIM
Definition heur_alns.c:333
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:189
#define DEFAULT_DOMOREFIXINGS
Definition heur_alns.c:146
static SCIP_RETCODE setLimits(SCIP *subscip, SOLVELIMITS *solvelimits)
Definition heur_alns.c:1949
#define DEFAULT_INITDURINGROOT
Definition heur_alns.c:105
#define DEFAULT_VIOLPENALTY_TRUSTREGION
Definition heur_alns.c:209
#define DEFAULT_UNFIXTOL
Definition heur_alns.c:129
static SCIP_RETCODE resetFixingRate(SCIP *scip, NH_FIXINGRATE *fixingrate)
Definition heur_alns.c:520
#define DEFAULT_ALPHA
Definition heur_alns.c:138
#define MUTATIONSEED
Definition heur_alns.c:157
#define DEFAULT_ACTIVE_LOCALBRANCHING
Definition heur_alns.c:178
static void decreaseMinimumImprovement(SCIP_HEURDATA *heurdata)
Definition heur_alns.c:711
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:174
#define DEFAULT_PRIORITY_RINS
Definition heur_alns.c:169
#define DEFAULT_REWARDFILENAME
Definition heur_alns.c:153
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:198
#define EVENTHDLR_DESC
Definition heur_alns.c:213
#define DEFAULT_PRIORITY_TRUSTREGION
Definition heur_alns.c:204
#define LPLIMFAC
Definition heur_alns.c:104
#define CROSSOVERSEED
Definition heur_alns.c:158
#define DEFAULT_MAXFIXINGRATE_LOCALBRANCHING
Definition heur_alns.c:177
#define HEUR_FREQ
Definition heur_alns.c:82
#define DEFAULT_SUBSCIPRANDSEEDS
Definition heur_alns.c:126
#define DEFAULT_NPOOLSOLS_DINS
Definition heur_alns.c:208
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:167
static SCIP_RETCODE includeNeighborhoods(SCIP *scip, SCIP_HEURDATA *heurdata)
Definition heur_alns.c:3705
#define DEFAULT_MINFIXINGRATE_MUTATION
Definition heur_alns.c:171
#define DEFAULT_EPS
Definition heur_alns.c:137
#define DEFAULT_TARGETNODEFACTOR
Definition heur_alns.c:102
#define DEFAULT_MAXFIXINGRATE_CROSSOVER
Definition heur_alns.c:187
#define DEFAULT_NSOLS_CROSSOVER
Definition heur_alns.c:207
#define DEFAULT_USEDISTANCES
Definition heur_alns.c:145
#define DEFAULT_SCALEBYEFFORT
Definition heur_alns.c:124
static void resetCurrentNeighborhood(SCIP_HEURDATA *heurdata)
Definition heur_alns.c:537
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:86
#define DEFAULT_BETA
Definition heur_alns.c:131
#define DEFAULT_SHOWNBSTATS
Definition heur_alns.c:90
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)
Definition heur_alns.c:911
#define DEFAULT_ACTIVE_CROSSOVER
Definition heur_alns.c:188
#define DEFAULT_USESUBSCIPHEURS
Definition heur_alns.c:151
#define DEFAULT_PRIORITY_DINS
Definition heur_alns.c:199
#define EVENTHDLR_NAME
Definition heur_alns.c:212
static void printNeighborhoodStatistics(SCIP *scip, SCIP_HEURDATA *heurdata, FILE *file)
Definition heur_alns.c:1094
static SCIP_RETCODE setupSubScip(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SOLVELIMITS *solvelimits, SCIP_HEUR *heur, SCIP_Bool objchgd)
Definition heur_alns.c:2174
#define DEFAULT_MAXFIXINGRATE_PROXIMITY
Definition heur_alns.c:182
static SCIP_RETCODE neighborhoodChangeSubscip(SCIP *sourcescip, SCIP *targetscip, NH *neighborhood, SCIP_VAR **targetvars, int *ndomchgs, int *nchgobjs, int *naddedconss, SCIP_Bool *success)
Definition heur_alns.c:1909
#define DECL_VARFIXINGS(x)
Definition heur_alns.c:261
#define DEFAULT_PRIORITY_LOCALBRANCHING
Definition heur_alns.c:179
#define DEFAULT_MINFIXINGRATE_TRUSTREGION
Definition heur_alns.c:201
#define DEFAULT_BESTSOLWEIGHT
Definition heur_alns.c:121
#define DEFAULT_BANDITALGO
Definition heur_alns.c:122
#define DEFAULT_MINFIXINGRATE_PROXIMITY
Definition heur_alns.c:181
static SCIP_RETCODE createBandit(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Real *priorities, unsigned int initseed)
Definition heur_alns.c:1603
static SCIP_RETCODE neighborhoodFixVariables(SCIP *scip, SCIP_HEURDATA *heurdata, NH *neighborhood, SCIP_VAR **varbuf, SCIP_Real *valbuf, int *nfixings, SCIP_RESULT *result)
Definition heur_alns.c:1811
#define DEFAULT_GAMMA
Definition heur_alns.c:139
#define LRATEMIN
Definition heur_alns.c:103
#define DEFAULT_USEPSCOST
Definition heur_alns.c:144
static SCIP_RETCODE transferSolution(SCIP *subscip, SCIP_EVENTDATA *eventdata)
Definition heur_alns.c:929
Adaptive large neighborhood search heuristic that orchestrates popular LNS heuristics.
SCIP_Bool cutoff
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
heurdata usednodes
Definition heur_locks.c:158
SCIP_VAR * var
SCIP_Real frac
SCIP_Real newobj
static SCIP_VAR ** vars
int nbinvars
int nintvars
methods commonly used by primal heuristics
static const char * paramname[]
Definition lpi_msk.c:5096
memory allocation routines
#define BMSduplicateMemoryArray(ptr, source, num)
Definition memory.h:143
#define BMSclearMemory(ptr)
Definition memory.h:129
#define BMSfreeMemoryArray(ptr)
Definition memory.h:147
#define BMScopyMemoryArray(ptr, source, num)
Definition memory.h:134
#define BMSclearMemoryArray(ptr, num)
Definition memory.h:130
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition scip_mem.c:57
public methods for bandit algorithms
public methods for the epsilon greedy bandit selector
public methods for Exp.3
public methods for Exp.3-IX
public methods for UCB bandit selection
public methods for managing constraints
public methods for managing events
public methods for primal heuristics
public methods for message output
#define SCIPerrorMessage
Definition pub_message.h:64
#define SCIPdebugMessage
Definition pub_message.h:96
public data structures and miscellaneous methods
methods for selecting (weighted) k-medians
public methods for primal CIP solutions
public methods for problem variables
public methods for bandit algorithms
public methods for branching rule plugins and branching
public methods for constraint handler plugins and constraints
public methods for problem copies
public methods for event handler plugins and event handlers
general public methods
public methods for primal heuristic plugins and divesets
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for node selector plugins
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for random numbers
public methods for solutions
public solving methods
public methods for querying solving statistics
public methods for statistics table plugins
public methods for timing
public methods for the branch-and-bound tree
public methods for SCIP variables
SCIP_Real targetfixingrate
Definition heur_alns.c:364
SCIP_Real increment
Definition heur_alns.c:365
SCIP_Real minfixingrate
Definition heur_alns.c:363
SCIP_Real maxfixingrate
Definition heur_alns.c:366
SCIP_Longint nsolsfound
Definition heur_alns.c:353
SCIP_Real newupperbound
Definition heur_alns.c:350
int statushist[NHISTENTRIES]
Definition heur_alns.c:356
SCIP_CLOCK * submipclock
Definition heur_alns.c:347
SCIP_CLOCK * setupclock
Definition heur_alns.c:346
int nruns
Definition heur_alns.c:351
SCIP_Longint nbestsolsfound
Definition heur_alns.c:354
SCIP_Longint usednodes
Definition heur_alns.c:348
SCIP_Real oldupperbound
Definition heur_alns.c:349
int nrunsbestsol
Definition heur_alns.c:352
int nfixings
Definition heur_alns.c:355
NH_FIXINGRATE fixingrate
Definition heur_alns.c:373
DECL_NHINIT((*nhinit))
DATA_MUTATION * mutation
Definition heur_alns.c:386
DECL_CHANGESUBSCIP((*changesubscip))
SCIP_Bool active
Definition heur_alns.c:382
NH_STATS stats
Definition heur_alns.c:374
DECL_NHFREE((*nhfree))
DATA_CROSSOVER * crossover
Definition heur_alns.c:387
DECL_NHEXIT((*nhexit))
DECL_NHDEACTIVATE((*nhdeactivate))
DATA_TRUSTREGION * trustregion
Definition heur_alns.c:389
DECL_VARFIXINGS((*varfixings))
DECL_NHREFSOL((*nhrefsol))
DATA_DINS * dins
Definition heur_alns.c:388
char * name
Definition heur_alns.c:372
SCIP_Real priority
Definition heur_alns.c:383
union Nh::@5 data
SCIP_Real timelimit
Definition heur_alns.c:495
SCIP_Longint stallnodes
Definition heur_alns.c:496
SCIP_Longint nodelimit
Definition heur_alns.c:493
SCIP_Real memorylimit
Definition heur_alns.c:494
SCIP * scip
Definition heur_alns.c:504
unsigned int useredcost
Definition heur_alns.c:509
SCIP_Real * randscores
Definition heur_alns.c:505
int * distances
Definition heur_alns.c:506
SCIP_Real * pscostscores
Definition heur_alns.c:508
unsigned int usedistances
Definition heur_alns.c:510
SCIP_Real * redcostscores
Definition heur_alns.c:507
unsigned int usepscost
Definition heur_alns.c:511
SCIP_SOL * selsol
Definition heur_alns.c:404
SCIP_RANDNUMGEN * rng
Definition heur_alns.c:403
int npoolsols
Definition heur_alns.c:410
SCIP_RANDNUMGEN * rng
Definition heur_alns.c:396
SCIP_Real violpenalty
Definition heur_alns.c:415
struct SCIP_EventData SCIP_EVENTDATA
Definition type_event.h:173
#define SCIP_DECL_EVENTEXEC(x)
Definition type_event.h:253
#define SCIP_EVENTTYPE_BESTSOLFOUND
Definition type_event.h:105
#define SCIP_EVENTTYPE_SOLFOUND
Definition type_event.h:144
#define SCIP_EVENTTYPE_LPSOLVED
Definition type_event.h:101
#define SCIP_DECL_HEURINITSOL(x)
Definition type_heur.h:132
#define SCIP_DECL_HEURCOPY(x)
Definition type_heur.h:97
struct SCIP_HeurData SCIP_HEURDATA
Definition type_heur.h:77
#define SCIP_DECL_HEURINIT(x)
Definition type_heur.h:113
#define SCIP_DECL_HEUREXIT(x)
Definition type_heur.h:121
#define SCIP_DECL_HEURFREE(x)
Definition type_heur.h:105
#define SCIP_DECL_HEUREXEC(x)
Definition type_heur.h:163
@ SCIP_LPSOLSTAT_OPTIMAL
Definition type_lp.h:43
#define SCIP_DECL_SORTINDCOMP(x)
Definition type_misc.h:180
@ SCIP_PARAMSETTING_OFF
@ SCIP_PARAMSETTING_FAST
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_DELAYED
Definition type_result.h:43
@ SCIP_DIDNOTFIND
Definition type_result.h:44
@ SCIP_SUCCESS
Definition type_result.h:58
enum SCIP_Result SCIP_RESULT
Definition type_result.h:61
@ SCIP_FILECREATEERROR
@ SCIP_INVALIDDATA
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_SOLORIGIN_ORIGINAL
Definition type_sol.h:42
@ SCIP_STATUS_OPTIMAL
Definition type_stat.h:61
@ SCIP_STATUS_TOTALNODELIMIT
Definition type_stat.h:45
@ SCIP_STATUS_BESTSOLLIMIT
Definition type_stat.h:57
@ SCIP_STATUS_SOLLIMIT
Definition type_stat.h:54
@ SCIP_STATUS_UNBOUNDED
Definition type_stat.h:63
@ SCIP_STATUS_UNKNOWN
Definition type_stat.h:42
@ SCIP_STATUS_GAPLIMIT
Definition type_stat.h:53
@ SCIP_STATUS_USERINTERRUPT
Definition type_stat.h:43
@ SCIP_STATUS_TERMINATE
Definition type_stat.h:65
@ SCIP_STATUS_INFORUNBD
Definition type_stat.h:64
@ SCIP_STATUS_STALLNODELIMIT
Definition type_stat.h:48
@ SCIP_STATUS_TIMELIMIT
Definition type_stat.h:51
@ SCIP_STATUS_INFEASIBLE
Definition type_stat.h:62
@ SCIP_STATUS_NODELIMIT
Definition type_stat.h:44
@ SCIP_STATUS_MEMLIMIT
Definition type_stat.h:52
@ SCIP_STATUS_RESTARTLIMIT
Definition type_stat.h:60
enum SCIP_Status SCIP_STATUS
Definition type_stat.h:67
#define SCIP_DECL_TABLEOUTPUT(x)
Definition type_table.h:122
#define SCIP_HEURTIMING_DURINGLPLOOP
Definition type_timing.h:79
@ SCIP_VARTYPE_INTEGER
Definition type_var.h:63
@ SCIP_VARSTATUS_COLUMN
Definition type_var.h:51