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