Scippy

SCIP

Solving Constraint Integer Programs

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