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