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