1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file heur_gins.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief LNS heuristic that tries to delimit the search region to a neighborhood in the constraint graph 28 * @author Gregor Hendel 29 * 30 * Graph Induced Neighborhood Search (GINS) is a Large Neighborhood Search Heuristic that attempts to improve 31 * an incumbent solution by fixing a suitable percentage of integer variables to the incumbent and 32 * solving the resulting, smaller and presumably easier sub-MIP. 33 * 34 * Its search neighborhoods are based on distances in a bipartite graph \f$G\f$ with the variables and constraints as nodes 35 * and an edge between a variable and a constraint, if the variable is part of the constraint. 36 * Given an integer \f$k\f$, the \f$k\f$-neighborhood of a variable \f$v\f$ in \f$G\f$ is the set of variables, whose nodes 37 * are connected to \f$v\f$ by a path not longer than \f$2 \cdot k\f$. Intuitively, a judiciously chosen neighborhood size 38 * allows to consider a local portion of the overall problem. 39 * 40 * An initial variable selection is made by randomly sampling different neighborhoods across the whole main problem. 41 * The neighborhood that offers the largest potential for improvement is selected to become the local search neighborhood, 42 * while all variables outside the neighborhood are fixed to their incumbent solution values. 43 * 44 * GINS also supports a rolling horizon approach, during which several local neighborhoods are considered 45 * with increasing distance to the variable selected for the initial sub-problem. The rolling horizon approach ends 46 * if no improvement could be found or a sufficient part of the problem component variables has been part of 47 * at least one neighborhood. 48 */ 49 50 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 51 52 #include "blockmemshell/memory.h" 53 #include "scip/heur_gins.h" 54 #include "scip/heuristics.h" 55 #include "scip/pub_dcmp.h" 56 #include "scip/pub_heur.h" 57 #include "scip/pub_message.h" 58 #include "scip/pub_misc.h" 59 #include "scip/pub_misc_sort.h" 60 #include "scip/pub_sol.h" 61 #include "scip/pub_var.h" 62 #include "scip/scip_branch.h" 63 #include "scip/scip_cons.h" 64 #include "scip/scip_copy.h" 65 #include "scip/scip_dcmp.h" 66 #include "scip/scip_general.h" 67 #include "scip/scip_heur.h" 68 #include "scip/scip_mem.h" 69 #include "scip/scip_message.h" 70 #include "scip/scip_nodesel.h" 71 #include "scip/scip_numerics.h" 72 #include "scip/scip_param.h" 73 #include "scip/scip_prob.h" 74 #include "scip/scip_randnumgen.h" 75 #include "scip/scip_sol.h" 76 #include "scip/scip_solve.h" 77 #include "scip/scip_solvingstats.h" 78 #include "scip/scip_timing.h" 79 #include <string.h> 80 81 #define HEUR_NAME "gins" 82 #define HEUR_DESC "gins works on k-neighborhood in a variable-constraint graph" 83 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS 84 #define HEUR_PRIORITY -1103000 85 #define HEUR_FREQ 20 86 #define HEUR_FREQOFS 8 87 #define HEUR_MAXDEPTH -1 88 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE 89 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */ 90 91 #define DEFAULT_NODESOFS 500 /**< number of nodes added to the contingent of the total nodes */ 92 #define DEFAULT_MAXNODES 5000 /**< maximum number of nodes to regard in the subproblem */ 93 #define DEFAULT_MINIMPROVE 0.01 /**< factor by which Gins should at least improve the incumbent */ 94 #define DEFAULT_MINNODES 50 /**< minimum number of nodes to regard in the subproblem */ 95 #define DEFAULT_MINFIXINGRATE 0.66 /**< minimum percentage of integer variables that have to be fixed */ 96 #define DEFAULT_NODESQUOT 0.15 /**< subproblem nodes in relation to nodes of the original problem */ 97 #define DEFAULT_NWAITINGNODES 100 /**< number of nodes without incumbent change that heuristic should wait */ 98 #define DEFAULT_USELPROWS FALSE /**< should subproblem be created out of the rows in the LP rows, 99 * otherwise, the copy constructors of the constraints handlers are used */ 100 #define DEFAULT_COPYCUTS TRUE /**< if DEFAULT_USELPROWS is FALSE, then should all active cuts from the 101 * cutpool of the original scip be copied to constraints of the subscip */ 102 #define DEFAULT_BESTSOLLIMIT 3 /**< limit on number of improving incumbent solutions in sub-CIP */ 103 #define DEFAULT_FIXCONTVARS FALSE /**< should continuous variables outside the neighborhoods get fixed? */ 104 #define DEFAULT_POTENTIAL 'r' /**< the reference point to compute the neighborhood potential: (r)oot, (l)ocal lp, or (p)seudo solution */ 105 #define DEFAULT_MAXDISTANCE 3 /**< maximum distance to selected variable to enter the subproblem, or -1 to 106 * select the distance that best approximates the minimum fixing rate from below */ 107 #define DEFAULT_RANDSEED 71 108 #define DEFAULT_RELAXDENSECONSS FALSE /**< should dense constraints (at least as dense as 1 - minfixingrate) be 109 * ignored by connectivity graph? */ 110 #define DEFAULT_USEROLLINGHORIZON TRUE /**< should the heuristic solve a sequence of sub-MIP's around the first selected variable */ 111 #define DEFAULT_ROLLHORIZONLIMFAC 0.4 /**< limiting percentage for variables already used in sub-SCIPs to terminate rolling 112 * horizon approach */ 113 #define DEFAULT_USEDECOMP TRUE /**< should user decompositions be considered, if available? */ 114 #define DEFAULT_USEDECOMPROLLHORIZON FALSE /**< should user decompositions be considered for initial selection in rolling horizon, if available? */ 115 #define DEFAULT_USESELFALLBACK TRUE /**< should random initial variable selection be used if decomposition was not successful? */ 116 #define DEFAULT_OVERLAP 0.0 /**< overlap of blocks between runs - 0.0: no overlap, 1.0: shift by only 1 block */ 117 #define DEFAULT_CONSECUTIVEBLOCKS TRUE /**< should blocks be treated consecutively (sorted by ascending label?) */ 118 119 120 /* 121 * Data structures 122 */ 123 124 /** rolling horizon data structure to control multiple LNS heuristic runs away from an original source variable */ 125 struct RollingHorizon 126 { 127 SCIP_VGRAPH* variablegraph; /**< variable graph data structure for breadth-first-search neighborhoods */ 128 int* distances; /**< distances of the heuristic rolling horizon from the original source 129 * variable indexed by probindex */ 130 SCIP_Bool* used; /**< array that represents for every variable whether it has been used 131 * in a neighborhood indexed by probindex */ 132 int lastmaxdistance; /**< the last distance k for a neighborhood, will be decreased 133 * during the rolling horizon if the selected neighborhood is too large */ 134 int lastdistance; /**< last distance from originally selected variable in iteration zero */ 135 int distancessize; /**< size of the distances and used arrays */ 136 int niterations; /**< counter for the number of rolling horizon iterations */ 137 int nused; /**< counts the number variables that have been part of any neighborhood 138 * during the rolling horizon approach */ 139 int nnonreachable; /**< counter for the number of nonreachable variables (distance -1) from 140 * the initially selected variable */ 141 }; 142 typedef struct RollingHorizon ROLLINGHORIZON; 143 144 /** data structure to enable GINS to solve multiple decompositions in a sequential process */ 145 struct DecompHorizon 146 { 147 SCIP_DECOMP* decomp; /**< decomposition data structure used for this horizon */ 148 SCIP_VAR** vars; /**< variables sorted by block indices */ 149 SCIP_SOL** lastsolblock; /**< last solution for which block was part of the sub-SCIP */ 150 SCIP_Real* potential; /**< potential of each block */ 151 int* blocklabels; /**< sorted block labels of all variable blocks that satisfy the requirements */ 152 int* varblockend; /**< block end indices in sorted variables array (position of first variable of next block) */ 153 int* ndiscretevars; /**< number of binary and integer variables in each block */ 154 int* blockindices; /**< block indices (from 0 to nblocks) with respect to sorting of blocks */ 155 int* nvars; /**< number of variables (including continuous and implicit integers) in each block */ 156 SCIP_Bool* suitable; /**< TRUE if a block is suitable */ 157 int nsuitableblocks; /**< the total number of suitable blocks */ 158 int lastblockpos; /**< last remembered block position (in block indices, i.e., regarding sorting) */ 159 int nblocks; /**< the number of available variable blocks, only available after initialization */ 160 int memsize; /**< storage size of the used arrays */ 161 int varsmemsize; /**< storage size of the vars array */ 162 int overlapinterval[2]; /**< block positions of last interval forbidden by overlap */ 163 SCIP_Bool init; /**< has the decomposition horizon been initialized? */ 164 }; 165 typedef struct DecompHorizon DECOMPHORIZON; 166 167 /** data structure to hold elements that are taboo */ 168 struct TabooList 169 { 170 int* taboolabels; /**< labels or indices that are currently taboo */ 171 int* sortedlabels; /**< array of labels in sorted order for quicker finding */ 172 int memsize; /**< storage capacity of taboolabels */ 173 int ntaboolabels; /**< number of elements contained in taboo list */ 174 SCIP_Bool needssorting; /**< has an element been added since the last sort? */ 175 }; 176 typedef struct TabooList TABOOLIST; 177 178 /** primal heuristic data */ 179 struct SCIP_HeurData 180 { 181 int nodesofs; /**< number of nodes added to the contingent of the total nodes */ 182 int maxnodes; /**< maximum number of nodes to regard in the subproblem */ 183 int minnodes; /**< minimum number of nodes to regard in the subproblem */ 184 SCIP_Real minfixingrate; /**< minimum percentage of integer variables that have to be fixed */ 185 SCIP_Real overlap; /**< overlap of blocks between runs - 0.0: no overlap, 1.0: shift by only 1 block */ 186 int nwaitingnodes; /**< number of nodes without incumbent change that heuristic should wait */ 187 SCIP_Real minimprove; /**< factor by which Gins should at least improve the incumbent */ 188 SCIP_Longint usednodes; /**< nodes already used by Gins in earlier calls */ 189 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */ 190 SCIP_Real rollhorizonlimfac; /**< limiting percentage for variables already used in sub-SCIPs to terminate 191 * rolling horizon approach */ 192 DECOMPHORIZON* decomphorizon; /**< decomposition horizon data structure */ 193 SCIP_RANDNUMGEN* randnumgen; /**< random number generator */ 194 SCIP_SOL* lastinitsol; /**< last solution used for selection of initial variable */ 195 TABOOLIST* taboolist; /**< taboo list of block labels that should not be used */ 196 SCIP_Bool uselprows; /**< should subproblem be created out of the rows in the LP rows? */ 197 SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied 198 * to constraints in subproblem? */ 199 SCIP_Bool allblocksunsuitable; /**< remember if all blocks are unsuitable w.r.t. the current incumbent solution */ 200 SCIP_Bool fixcontvars; /**< should continuous variables outside the neighborhoods get fixed? */ 201 int bestsollimit; /**< limit on number of improving incumbent solutions in sub-CIP */ 202 int maxdistance; /**< maximum distance to selected variable to enter the subproblem, or -1 to 203 * select the distance that best approximates the minimum fixing rate from below */ 204 int sumneighborhoodvars;/**< neighborhood variables sum over all seen neighborhoods */ 205 int sumdiscneighborhoodvars; /**< neighborhood discrete variables sum over all seen neighboorhoods */ 206 int nneighborhoods; /**< number of calculated neighborhoods */ 207 int nsubmips; /**< counter for the number of sub-MIP's that can be higher than the number of 208 * calls of this heuristic */ 209 SCIP_Bool consecutiveblocks; /**< should blocks be treated consecutively (sorted by ascending label?) */ 210 SCIP_Bool relaxdenseconss; /**< should dense constraints (at least as dense as 1 - minfixingrate) be 211 * ignored by connectivity graph? */ 212 SCIP_Bool userollinghorizon; /**< should the heuristic solve a sequence of sub-MIP's around the first 213 * selected variable */ 214 SCIP_Bool usedecomp; /**< should user decompositions be considered, if available? */ 215 SCIP_Bool usedecomprollhorizon;/**< should user decompositions be considered for initial selection in rolling horizon, if available? */ 216 SCIP_Bool useselfallback; /**< should random initial variable selection be used if decomposition was not successful? */ 217 char potential; /**< the reference point to compute the neighborhood potential: (r)oot or 218 * (p)seudo solution */ 219 int maxseendistance; /**< maximum of all distances between two variables */ 220 int nrelaxedconstraints; /**< number of constraints that were relaxed */ 221 int nfailures; /**< counter for the number of unsuccessful runs of this heuristic */ 222 SCIP_Longint nextnodenumber; /**< the next node number at which the heuristic should be called again */ 223 SCIP_Longint targetnodes; /**< number of target nodes, slightly increasing if (stall) node limit is hit */ 224 }; 225 226 /** represents limits for the sub-SCIP solving process */ 227 struct SolveLimits 228 { 229 SCIP_Longint nodelimit; /**< maximum number of solving nodes for the sub-SCIP */ 230 SCIP_Longint stallnodelimit; /**< limit on the number of stall nodes (nodes after last incumbent) */ 231 }; 232 typedef struct SolveLimits SOLVELIMITS; 233 234 /* 235 * Local methods 236 */ 237 238 /** check if enough fixings have been found */ 239 static 240 SCIP_Bool checkFixingrate( 241 SCIP* scip, /**< SCIP data structure */ 242 SCIP_HEURDATA* heurdata, /**< heuristic data */ 243 int nfixings /**< actual number of fixings */ 244 ) 245 { 246 int fixthreshold; 247 int nvars = SCIPgetNVars(scip); 248 int nbinvars = SCIPgetNBinVars(scip); 249 int nintvars = SCIPgetNIntVars(scip); 250 fixthreshold = (int)(heurdata->minfixingrate * (heurdata->fixcontvars ? nvars : (nbinvars + nintvars))); 251 252 /* compare actual number of fixings to limit; if we fixed not enough variables we terminate here; 253 * we also terminate if no discrete variables are left 254 */ 255 if( nfixings < fixthreshold ) 256 { 257 SCIPdebugMsg(scip, "Fixed %d < %d variables in gins heuristic, stopping\n", nfixings, fixthreshold); 258 259 return FALSE; 260 } 261 else 262 { 263 SCIPdebugMsg(scip, "Fixed enough (%d >= %d) variables in gins heuristic\n", nfixings, fixthreshold); 264 265 return TRUE; 266 } 267 } 268 269 /** get the potential of a subset of variables (distance to a reference point such as the pseudo-solution or root 270 * LP solution) 271 */ 272 static 273 SCIP_Real getPotential( 274 SCIP* scip, /**< SCIP data structure */ 275 SCIP_HEURDATA* heurdata, /**< heuristic data */ 276 SCIP_SOL* sol, /**< solution */ 277 SCIP_VAR** vars, /**< variable array */ 278 int nvars /**< length of variable array */ 279 ) 280 { 281 SCIP_Real potential; 282 int i; 283 284 assert(scip != NULL); 285 assert(vars != NULL); 286 assert(sol != NULL); 287 288 if( nvars == 0 ) 289 return 0.0; 290 291 potential = 0.0; 292 293 for( i = 0; i < nvars; ++i ) 294 { 295 SCIP_Real objdelta; 296 SCIP_VAR* var; 297 SCIP_Real referencepoint; 298 SCIP_Real varobj; 299 300 var = vars[i]; 301 assert(var != NULL); 302 varobj = SCIPvarGetObj(var); 303 304 if( SCIPisZero(scip, varobj) ) 305 continue; 306 307 /* determine the reference point for potential computation */ 308 switch( heurdata->potential ) 309 { 310 /* use difference to pseudo solution using the bound in the objective direction */ 311 case 'p': 312 referencepoint = varobj > 0.0 ? SCIPvarGetLbGlobal(var) : SCIPvarGetUbGlobal(var); 313 break; 314 315 /* use root LP solution difference */ 316 case 'r': 317 referencepoint = SCIPvarGetRootSol(var); 318 break; 319 320 /* use local LP solution */ 321 case 'l': 322 referencepoint = SCIPgetSolVal(scip, NULL, var); 323 break; 324 default: 325 SCIPerrorMessage("Unknown potential computation %c specified\n", heurdata->potential); 326 referencepoint = 0.0; 327 break; 328 } 329 330 if( SCIPisInfinity(scip, REALABS(referencepoint)) ) 331 continue; 332 333 /* calculate the delta to the variables best bound */ 334 objdelta = (SCIPgetSolVal(scip, sol, var) - referencepoint) * varobj; 335 potential += objdelta; 336 } 337 338 return potential; 339 } 340 341 /** (re)set overlap interval of decomposition horizon */ 342 static 343 void decompHorizonSetOverlapInterval( 344 DECOMPHORIZON* decomphorizon, /**< decomposition horizon data structure */ 345 int leftborder, /**< left interval border */ 346 int rightborder /**< right interval border */ 347 ) 348 { 349 assert(decomphorizon != NULL); 350 assert(leftborder <= rightborder); 351 352 decomphorizon->overlapinterval[0] = leftborder; 353 decomphorizon->overlapinterval[1] = rightborder; 354 } 355 356 /** create a decomp horizon data structure */ 357 static 358 SCIP_RETCODE decompHorizonCreate( 359 SCIP* scip, /**< SCIP data structure */ 360 DECOMPHORIZON** decomphorizon, /**< pointer to store decomposition horizon */ 361 SCIP_DECOMP* decomp /**< decomposition in transformed space */ 362 ) 363 { 364 DECOMPHORIZON* decomphorizonptr; 365 int nblocks; 366 int memsize; 367 368 assert(scip != NULL); 369 assert(decomphorizon != NULL); 370 assert(decomp != NULL); 371 372 nblocks = SCIPdecompGetNBlocks(decomp); 373 374 assert(nblocks >= 1); 375 376 /* account an additional slot for the border */ 377 SCIP_CALL( SCIPallocBlockMemory(scip, decomphorizon) ); 378 decomphorizonptr = *decomphorizon; 379 decomphorizonptr->decomp = decomp; 380 decomphorizonptr->memsize = memsize = nblocks + 1; 381 382 /* allocate storage for block related information */ 383 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomphorizonptr->blocklabels, memsize) ); 384 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomphorizonptr->varblockend, memsize) ); 385 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomphorizonptr->suitable, memsize) ); 386 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomphorizonptr->ndiscretevars, memsize) ); 387 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomphorizonptr->nvars, memsize) ); 388 SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &decomphorizonptr->lastsolblock, memsize) ); 389 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomphorizonptr->potential, memsize) ); 390 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomphorizonptr->blockindices, memsize) ); 391 392 decomphorizonptr->lastblockpos = INT_MIN; /* cannot use -1 because this is defined for linking variables */ 393 394 /* initialize data later */ 395 decomphorizonptr->init = FALSE; 396 decomphorizonptr->vars = NULL; 397 decomphorizonptr->varsmemsize = 0; 398 399 return SCIP_OKAY; 400 } 401 402 /** free a decomp horizon data structure */ 403 static 404 void decompHorizonFree( 405 SCIP* scip, /**< SCIP data structure */ 406 DECOMPHORIZON** decomphorizon /**< pointer to decomposition horizon that should be freed */ 407 ) 408 { 409 DECOMPHORIZON* decomphorizonptr; 410 411 assert(scip != NULL); 412 assert(decomphorizon != NULL); 413 414 /* empty horizon */ 415 if( *decomphorizon == NULL ) 416 return; 417 418 decomphorizonptr = *decomphorizon; 419 SCIPfreeBlockMemoryArrayNull(scip, &decomphorizonptr->vars, decomphorizonptr->varsmemsize); 420 421 SCIPfreeBlockMemoryArray(scip, &decomphorizonptr->blocklabels, decomphorizonptr->memsize); 422 SCIPfreeBlockMemoryArray(scip, &decomphorizonptr->varblockend, decomphorizonptr->memsize); 423 SCIPfreeBlockMemoryArray(scip, &decomphorizonptr->suitable, decomphorizonptr->memsize); 424 SCIPfreeBlockMemoryArray(scip, &decomphorizonptr->ndiscretevars, decomphorizonptr->memsize); 425 SCIPfreeBlockMemoryArray(scip, &decomphorizonptr->nvars, decomphorizonptr->memsize); 426 SCIPfreeBlockMemoryArray(scip, &decomphorizonptr->lastsolblock, decomphorizonptr->memsize); 427 SCIPfreeBlockMemoryArray(scip, &decomphorizonptr->potential, decomphorizonptr->memsize); 428 SCIPfreeBlockMemoryArray(scip, &decomphorizonptr->blockindices, decomphorizonptr->memsize); 429 430 SCIPfreeBlockMemory(scip, decomphorizon); 431 432 *decomphorizon = NULL; 433 } 434 435 /** check if another run should be performed within the current decomposition horizon */ 436 static 437 SCIP_Bool decompHorizonRunAgain( 438 SCIP* scip, /**< SCIP data structure */ 439 DECOMPHORIZON* decomphorizon /**< decomposition horizon data structure */ 440 ) 441 { 442 assert(scip != NULL); 443 assert(decomphorizon != NULL); 444 445 assert(decomphorizon->lastblockpos >= 0); 446 assert(decomphorizon->lastblockpos < decomphorizon->nblocks); 447 448 return TRUE; 449 } 450 451 /** return TRUE if the decomposition horizon has already been initialized, FALSE otherwise */ 452 static 453 SCIP_Bool decompHorizonIsInitialized( 454 DECOMPHORIZON* decomphorizon /**< decomposition horizon data structure */ 455 ) 456 { 457 assert(decomphorizon != NULL); 458 459 return decomphorizon->init; 460 } 461 462 /** compares two block indices 463 * result: 464 * < 0: ind1 comes before (is better than) ind2 465 * = 0: both indices have the same value 466 * > 0: ind2 comes after (is worse than) ind2 467 */ 468 static 469 SCIP_DECL_SORTINDCOMP(sortIndCompDecompHorizon) 470 { 471 DECOMPHORIZON* decomphorizon = (DECOMPHORIZON*)dataptr; 472 SCIP_Real potentialbysize1; 473 SCIP_Real potentialbysize2; 474 475 assert(decomphorizon != NULL); 476 assert(ind1 >= 0); 477 assert(ind2 >= 0); 478 assert(ind1 < decomphorizon->nblocks); 479 assert(ind2 < decomphorizon->nblocks); 480 481 if( ind1 == ind2 ) 482 return 0; 483 484 /* linking variables are always sorted up front */ 485 if( decomphorizon->blocklabels[ind1] == SCIP_DECOMP_LINKVAR ) 486 return -1; 487 else if( decomphorizon->blocklabels[ind2] == SCIP_DECOMP_LINKVAR ) 488 return 1; 489 490 /* if one of the blocks is not suitable, return the other block */ 491 if( ! (decomphorizon->suitable[ind1] && decomphorizon->suitable[ind2]) ) 492 { 493 /* prefer the suitable block; break ties based on block position */ 494 if( decomphorizon->suitable[ind1] ) 495 return -1; 496 else if( decomphorizon->suitable[ind2] ) 497 return 1; 498 else 499 return ind1 - ind2; 500 } 501 502 assert(decomphorizon->suitable[ind1] && decomphorizon->suitable[ind2]); 503 504 potentialbysize1 = decomphorizon->potential[ind1] / (SCIP_Real)(MAX(decomphorizon->ndiscretevars[ind1], 1.0)); 505 potentialbysize2 = decomphorizon->potential[ind2] / (SCIP_Real)(MAX(decomphorizon->ndiscretevars[ind2], 1.0)); 506 507 /* prefer the block with higher potential */ 508 if( potentialbysize1 > potentialbysize2 ) 509 return -1; 510 else if( potentialbysize2 > potentialbysize1 ) 511 return 1; 512 513 /* finally, prefer the block with fewer discrete variables */ 514 return decomphorizon->ndiscretevars[ind1] - decomphorizon->ndiscretevars[ind2]; 515 } 516 517 /** initialize decomposition horizon data structure by setting up data structures and analyzing blocks */ 518 static 519 SCIP_RETCODE decompHorizonInitialize( 520 SCIP* scip, /**< SCIP data structure */ 521 DECOMPHORIZON* decomphorizon, /**< decomposition horizon data structure */ 522 SCIP_HEURDATA* heurdata /**< heuristic data structure */ 523 ) 524 { 525 SCIP_VAR** vars; 526 SCIP_VAR** varscopy; 527 int* varlabels; 528 int nvars; 529 int currblockstart; 530 int blockpos; 531 int nstblblocks; 532 int ncontvarsscip; 533 int b; 534 535 SCIP_DECOMP* decomp = decomphorizon->decomp; 536 537 assert(scip != NULL); 538 assert(decomp != NULL); 539 assert(! SCIPdecompIsOriginal(decomp)); 540 541 vars = SCIPgetVars(scip); 542 nvars = SCIPgetNVars(scip); 543 ncontvarsscip = SCIPgetNContVars(scip) + SCIPgetNImplVars(scip); 544 545 assert(vars != NULL); 546 547 /* get variable labels from decomposition */ 548 SCIP_CALL( SCIPallocBufferArray(scip, &varlabels, nvars) ); 549 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &varscopy, vars, nvars) ); 550 551 SCIPdecompGetVarsLabels(decomp, varscopy, varlabels, nvars); 552 553 /* sort labels and variables */ 554 SCIPsortIntPtr(varlabels, (void **)varscopy, nvars); 555 decomphorizon->vars = varscopy; 556 decomphorizon->varsmemsize = nvars; 557 558 blockpos = 0; 559 currblockstart = 0; 560 nstblblocks = 0; 561 /* loop over blocks, and check if they are suitable or not for the improvement heuristic */ 562 while( currblockstart < nvars ) 563 { 564 int blocklabel; 565 int currblockend; 566 int ndiscretevars; 567 int nfixedvars; 568 SCIP_Bool suitable; 569 assert(blockpos < decomphorizon->memsize); 570 571 blocklabel = varlabels[currblockstart]; 572 currblockend = currblockstart; 573 ndiscretevars = 0; 574 575 /* determine the block size and the variable types */ 576 do 577 { 578 if( SCIPvarGetType(varscopy[currblockend]) < SCIP_VARTYPE_IMPLINT ) 579 ++ndiscretevars; 580 581 currblockend++; 582 } 583 while( currblockend < nvars && varlabels[currblockend] == blocklabel ); 584 585 if( heurdata->fixcontvars ) 586 nfixedvars = nvars - (currblockend - currblockstart); 587 else 588 nfixedvars = nvars - ncontvarsscip - ndiscretevars; 589 590 suitable = nfixedvars > heurdata->minfixingrate * (heurdata->fixcontvars ? nvars : nvars - ncontvarsscip); 591 592 decomphorizon->suitable[blockpos] = suitable; 593 decomphorizon->blocklabels[blockpos] = blocklabel; 594 decomphorizon->varblockend[blockpos] = currblockend; 595 decomphorizon->nvars[blockpos] = currblockend - currblockstart; 596 decomphorizon->ndiscretevars[blockpos] = ndiscretevars; 597 598 currblockstart = currblockend; 599 nstblblocks += (suitable ? 1 : 0); 600 601 blockpos++; 602 } 603 604 /* not necessarily all blocks have variables; store number of available blocks */ 605 decomphorizon->nblocks = blockpos; 606 decomphorizon->nsuitableblocks = nstblblocks; 607 608 /* initialize block indices (identical to blockposition initially) */ 609 for( b = 0; b < decomphorizon->nblocks; ++b ) 610 decomphorizon->blockindices[b] = b; 611 612 decompHorizonSetOverlapInterval(decomphorizon, -1, -1); 613 614 SCIPdebugMsg(scip, "Initialized decomposition horizon for %d blocks (%d suitable)\n", 615 decomphorizon->nblocks, 616 decomphorizon->nsuitableblocks); 617 618 SCIPfreeBufferArray(scip, &varlabels); 619 620 decomphorizon->init = TRUE; 621 622 return SCIP_OKAY; 623 } 624 625 /** get the first block position of the consecutive interval with the highest potential */ 626 static 627 int decompHorizonGetFirstPosBestPotential( 628 SCIP* scip, /**< SCIP data structure */ 629 DECOMPHORIZON* decomphorizon, /**< decomposition horizon data structure */ 630 SCIP_HEURDATA* heurdata, /**< heuristic data */ 631 int maxblocksize /**< maximum block size in number of variables */ 632 ) 633 { 634 SCIP_SOL* bestsol; 635 SCIP_Real intervalpotential; 636 int b; 637 int nintervalvars; 638 int b1; 639 int b2; 640 int bestpos; 641 SCIP_Real maxpotential; 642 SCIP_Bool withlinkvars; 643 SCIP_Bool linkvarsexist; 644 645 assert(scip != NULL); 646 assert(decomphorizon != NULL); 647 bestsol = SCIPgetBestSol(scip); 648 assert(bestsol != NULL); 649 650 linkvarsexist = decomphorizon->blocklabels[0] == SCIP_DECOMP_LINKVAR; 651 bestpos = 0; 652 653 /* recompute potential of blocks */ 654 for( b = 0; b < decomphorizon->nblocks; ++b ) 655 { 656 /* unsuitable blocks are left out and should not be contained in an interval */ 657 if( ! decomphorizon->suitable[b] ) 658 { 659 decomphorizon->potential[b] = SCIP_REAL_MIN; 660 continue; 661 } 662 663 /* store the potential of this block */ 664 decomphorizon->potential[b] = getPotential(scip, heurdata, bestsol, 665 &decomphorizon->vars[b == 0 ? 0 : decomphorizon->varblockend[b - 1]], decomphorizon->nvars[b]); 666 } 667 668 /* sort the blocks such that the suitable blocks with the highest potential come first */ 669 if( ! heurdata->consecutiveblocks ) 670 { 671 SCIPsortInd(decomphorizon->blockindices, sortIndCompDecompHorizon, (void*)decomphorizon, decomphorizon->nblocks); 672 673 /* best potential block is now at the front (actual block position is retrieved from blockindices */ 674 SCIPdebugMsg(scip, "New potential based sorting with trailing block: 0 (label %d, potential %.4g)\n", 675 decomphorizon->blocklabels[decomphorizon->blockindices[0]], decomphorizon->potential[decomphorizon->blockindices[0]]); 676 677 return 0; 678 } 679 680 /* compute the consecutive blocks interval with largest potential */ 681 b1 = linkvarsexist ? 0 : -1; 682 b2 = -1; 683 nintervalvars = 0; 684 intervalpotential = 0.0; 685 maxpotential = 0.0; 686 withlinkvars = FALSE; 687 688 while( b1 < decomphorizon->nblocks - 1 ) 689 { 690 int blockindb1; 691 int blockindb2; 692 ++b1; 693 blockindb1 = decomphorizon->blockindices[b1]; 694 695 if( ! decomphorizon->suitable[decomphorizon->blockindices[b1]] ) 696 { 697 nintervalvars = 0; 698 intervalpotential = 0.0; 699 withlinkvars = FALSE; 700 b2 = b1; 701 continue; 702 } 703 704 /* interval starts at b1 */ 705 if( b2 < b1 ) 706 { 707 nintervalvars = decomphorizon->ndiscretevars[blockindb1]; 708 assert(nintervalvars < maxblocksize); /* otherwise, it wasn't suitable */ 709 intervalpotential = decomphorizon->potential[blockindb1]; 710 withlinkvars = FALSE; 711 b2 = b1; 712 } 713 /* subtract the variables from the previous block */ 714 else 715 { 716 int prevblockind; 717 assert(b1 > (linkvarsexist ? 1 : 0)); 718 prevblockind = decomphorizon->blockindices[b1 - 1]; 719 assert(decomphorizon->suitable[prevblockind]); 720 nintervalvars -= decomphorizon->ndiscretevars[prevblockind]; 721 intervalpotential -= decomphorizon->potential[prevblockind]; 722 } 723 724 /* check if block allows to include linking variables */ 725 if( ! withlinkvars && linkvarsexist && decomphorizon->ndiscretevars[0] + decomphorizon->ndiscretevars[blockindb1] < maxblocksize ) 726 { 727 withlinkvars = TRUE; 728 nintervalvars = decomphorizon->ndiscretevars[0] + decomphorizon->ndiscretevars[blockindb1]; 729 b2 = b1; 730 } 731 else if( withlinkvars && decomphorizon->ndiscretevars[0] + decomphorizon->ndiscretevars[blockindb1] >= maxblocksize ) 732 { 733 withlinkvars = FALSE; 734 nintervalvars = decomphorizon->ndiscretevars[blockindb1]; 735 b2 = b1; 736 } 737 738 /* extend the interval by further blocks, if possible */ 739 while( ++b2 < decomphorizon->nblocks ) 740 { 741 blockindb2 = decomphorizon->blockindices[b2]; 742 743 if( ! decomphorizon->suitable[blockindb2] || nintervalvars + decomphorizon->ndiscretevars[blockindb2] >= maxblocksize ) 744 break; 745 746 nintervalvars += decomphorizon->ndiscretevars[blockindb2]; 747 intervalpotential += decomphorizon->potential[blockindb2]; 748 } 749 750 /* store the start of the interval with maximum potential */ 751 if( intervalpotential > maxpotential ) 752 { 753 bestpos = b1; /* because pos is incremented by 1 again */ 754 maxpotential = intervalpotential; 755 } 756 } 757 758 SCIPdebugMsg(scip, "Potential based selection chooses interval starting from block %d with potential %.1g\n", 759 bestpos, maxpotential); 760 761 return bestpos; 762 } 763 764 /** has this block been used too recently? */ 765 static 766 SCIP_Bool decompHorizonBlockUsedRecently( 767 SCIP* scip, /**< SCIP data structure */ 768 DECOMPHORIZON* decomphorizon, /**< decomposition horizon data structure */ 769 int blockpos /**< position of block */ 770 ) 771 { 772 assert(scip != NULL); 773 assert(decomphorizon != NULL); 774 assert(0 <= blockpos); 775 assert(blockpos < decomphorizon->nblocks); 776 777 return (decomphorizon->lastsolblock[decomphorizon->blockindices[blockpos]] == SCIPgetBestSol(scip) || 778 (decomphorizon->overlapinterval[0] <= blockpos && blockpos <= decomphorizon->overlapinterval[1])); 779 } 780 781 /** query the start and end of the next suitable block after the last @p lastblockused 782 * 783 * @return TRUE if next suitable block could be found, otherwise FALSE 784 */ 785 static 786 SCIP_Bool decompHorizonNext( 787 SCIP* scip, /**< SCIP data structure */ 788 DECOMPHORIZON* decomphorizon, /**< decomposition horizon data structure */ 789 SCIP_HEURDATA* heurdata, /**< heuristic data */ 790 int maxblocksize, /**< maximum block size in number of variables */ 791 int* blockintervalstart, /**< pointer to store position of first block of interval */ 792 int* blockintervalend, /**< pointer to store position of last block of interval */ 793 int* nextblocklabel, /**< pointer to store label of the next suitable block */ 794 SCIP_Bool* fixlinkvars /**< should the linking variables be fixed, as well? */ 795 ) 796 { 797 SCIP_Bool found; 798 int pos; 799 int firstpos; 800 SCIP_SOL* bestsol; 801 assert(decomphorizon != NULL); 802 assert(blockintervalstart != NULL); 803 assert(blockintervalend != NULL); 804 assert(nextblocklabel != NULL); 805 assert(fixlinkvars != NULL); 806 807 assert(decomphorizon->init); 808 809 if( decomphorizon->nsuitableblocks == 0 ) 810 { 811 return FALSE; 812 } 813 814 /* get the last block position that was used by the heuristic. Search for it, and continue with the next block. */ 815 found = decomphorizon->lastblockpos >= 0; 816 firstpos = decomphorizon->lastblockpos; 817 assert(! found || (firstpos >= 0 && firstpos < decomphorizon->nblocks)); 818 819 bestsol = SCIPgetBestSol(scip); 820 821 /* choose first position based on potential; subtract -1 because we immediately increase it */ 822 if( ! found || bestsol != decomphorizon->lastsolblock[decomphorizon->blockindices[firstpos]] ) 823 firstpos = decompHorizonGetFirstPosBestPotential(scip, decomphorizon, heurdata, maxblocksize) - 1; 824 825 /* that's why we subtract 1 from potential based position computation */ 826 pos = (firstpos + 1) % decomphorizon->nblocks; 827 828 while( pos < decomphorizon->nblocks && 829 (! decomphorizon->suitable[decomphorizon->blockindices[pos]] || decomphorizon->blocklabels[decomphorizon->blockindices[pos]] == SCIP_DECOMP_LINKVAR || 830 decompHorizonBlockUsedRecently(scip, decomphorizon, pos)) ) 831 pos++; 832 833 if( pos == decomphorizon->nblocks ) 834 { 835 pos = 0; 836 while( pos < firstpos && 837 (! decomphorizon->suitable[decomphorizon->blockindices[pos]] || decomphorizon->blocklabels[decomphorizon->blockindices[pos]] == SCIP_DECOMP_LINKVAR || 838 decompHorizonBlockUsedRecently(scip, decomphorizon, pos)) ) 839 pos++; 840 } 841 842 assert(pos == firstpos || (0 <= pos && decomphorizon->nblocks > pos && (decomphorizon->suitable[decomphorizon->blockindices[pos]] || pos == 0))); 843 844 *fixlinkvars = TRUE; 845 /* the next suitable block position has been discovered */ 846 if( pos != firstpos && decomphorizon->suitable[decomphorizon->blockindices[pos]] && !decompHorizonBlockUsedRecently(scip, decomphorizon, pos) ) 847 { 848 int ndiscretevars; 849 *nextblocklabel = decomphorizon->blocklabels[decomphorizon->blockindices[pos]]; 850 *blockintervalstart = pos; 851 *blockintervalend = pos; 852 853 ndiscretevars = decomphorizon->ndiscretevars[decomphorizon->blockindices[pos]]; 854 /* check if linking variable block exceeds maximum block size */ 855 if( decomphorizon->blocklabels[0] == SCIP_DECOMP_LINKVAR ) 856 { 857 *fixlinkvars = decomphorizon->ndiscretevars[0] + ndiscretevars > maxblocksize; 858 } 859 860 /* add linking variables to the block */ 861 if( !(*fixlinkvars) ) 862 ndiscretevars += decomphorizon->ndiscretevars[0]; 863 864 /* extend the subproblem until maximum target fixing rate is reached */ 865 while( ++pos < decomphorizon->nblocks && decomphorizon->suitable[decomphorizon->blockindices[pos]] && ndiscretevars + decomphorizon->ndiscretevars[decomphorizon->blockindices[pos]] < maxblocksize ) 866 { 867 *blockintervalend = pos; 868 *nextblocklabel = decomphorizon->blocklabels[decomphorizon->blockindices[pos]]; 869 ndiscretevars += decomphorizon->ndiscretevars[decomphorizon->blockindices[pos]]; 870 } 871 872 return TRUE; 873 } 874 else 875 { 876 /* no next, suitable block exists */ 877 *blockintervalstart = *blockintervalend = -1; 878 *nextblocklabel = -100; 879 880 return FALSE; 881 } 882 } 883 884 /** get the variables of this decomposition horizon */ 885 static 886 SCIP_VAR** decomphorizonGetVars( 887 DECOMPHORIZON* decomphorizon /**< decomposition horizon data structure */ 888 ) 889 { 890 assert(decomphorizon != NULL); 891 assert(decomphorizon->init); 892 893 return decomphorizon->vars; 894 } 895 896 /** create a rolling horizon data structure */ 897 static 898 SCIP_RETCODE rollingHorizonCreate( 899 SCIP* scip, /**< SCIP data structure */ 900 ROLLINGHORIZON** rollinghorizon /**< pointer to rolling horizon data structure */ 901 ) 902 { 903 int size; 904 assert(scip != NULL); 905 assert(rollinghorizon != NULL); 906 907 size = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip); 908 SCIP_CALL( SCIPallocBlockMemory(scip, rollinghorizon) ); 909 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*rollinghorizon)->distances, size) ); 910 SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(*rollinghorizon)->used, size) ); 911 (*rollinghorizon)->distancessize = size; 912 (*rollinghorizon)->variablegraph = NULL; 913 (*rollinghorizon)->lastdistance = -1; 914 (*rollinghorizon)->niterations = 0; 915 (*rollinghorizon)->nused = 0; 916 917 return SCIP_OKAY; 918 } 919 920 921 /** reset a taboo list */ 922 static 923 void tabooListReset( 924 TABOOLIST* taboolist /**< taboo list data structure */ 925 ) 926 { 927 taboolist->ntaboolabels = 0; 928 taboolist->needssorting = FALSE; 929 } 930 931 /** create a taboo list data structure */ 932 static 933 SCIP_RETCODE createTabooList( 934 SCIP* scip, /**< SCIP data structure */ 935 TABOOLIST** taboolist, /**< pointer to store taboo list data structure */ 936 int initialsize /**< initial storage capacity of taboo list */ 937 ) 938 { 939 assert(scip != NULL); 940 assert(taboolist != NULL); 941 942 SCIP_CALL( SCIPallocBlockMemory(scip, taboolist) ); 943 944 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*taboolist)->taboolabels, initialsize) ); 945 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*taboolist)->sortedlabels, initialsize) ); 946 (*taboolist)->memsize = initialsize; 947 tabooListReset(*taboolist); 948 949 return SCIP_OKAY; 950 } 951 952 /** free a taboo list data structure */ 953 static 954 void freeTabooList( 955 SCIP* scip, /**< SCIP data structure */ 956 TABOOLIST** taboolist /**< pointer to taboo list data structure that should be freed */ 957 ) 958 { 959 assert(scip != NULL); 960 assert(taboolist != NULL); 961 962 if( *taboolist == NULL ) 963 return; 964 965 SCIPfreeBlockMemoryArray(scip, &(*taboolist)->sortedlabels, (*taboolist)->memsize); 966 SCIPfreeBlockMemoryArray(scip, &(*taboolist)->taboolabels, (*taboolist)->memsize); 967 SCIPfreeBlockMemory(scip, taboolist); 968 } 969 970 /** add an element to the taboo list */ 971 static 972 SCIP_RETCODE tabooListAdd( 973 SCIP* scip, /**< SCIP data structure */ 974 TABOOLIST* taboolist, /**< taboo list data structure */ 975 int elem /**< element that should be added to the taboo list */ 976 ) 977 { 978 assert(scip != NULL); 979 assert(taboolist != NULL); 980 981 if( taboolist->memsize == taboolist->ntaboolabels ) 982 { 983 int newsize = SCIPcalcMemGrowSize(scip, taboolist->ntaboolabels + 1); 984 assert(newsize >= taboolist->ntaboolabels + 1); 985 986 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &taboolist->taboolabels, taboolist->memsize, newsize) ); 987 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &taboolist->sortedlabels, taboolist->memsize, newsize) ); 988 989 taboolist->memsize = newsize; 990 } 991 992 assert(taboolist->ntaboolabels < taboolist->memsize); 993 taboolist->taboolabels[taboolist->ntaboolabels++] = elem; 994 995 taboolist->needssorting = TRUE; 996 997 return SCIP_OKAY; 998 } 999 1000 /** find an element in the taboo list */ 1001 static 1002 SCIP_Bool tabooListFind( 1003 TABOOLIST* taboolist, /**< taboo list data structure */ 1004 int elem /**< element that should be added to the taboo list */ 1005 ) 1006 { 1007 SCIP_Bool found; 1008 int pos; 1009 assert(taboolist != NULL); 1010 1011 if( taboolist->ntaboolabels == 0 ) 1012 return FALSE; 1013 1014 if( taboolist->needssorting ) 1015 { 1016 BMScopyMemoryArray(taboolist->sortedlabels, taboolist->taboolabels, taboolist->ntaboolabels); 1017 SCIPsortInt(taboolist->sortedlabels, taboolist->ntaboolabels); 1018 } 1019 1020 found = SCIPsortedvecFindInt(taboolist->sortedlabels, elem, taboolist->ntaboolabels, &pos); 1021 1022 return found; 1023 } 1024 1025 /** get most recent k elements from taboo list */ 1026 static 1027 int* tabooListGetLastK( 1028 TABOOLIST* taboolist, /**< taboo list data structure */ 1029 int k /**< the number of elements that should be returned */ 1030 ) 1031 { 1032 assert(taboolist != NULL); 1033 assert(k <= taboolist->ntaboolabels); 1034 assert(k > 0); 1035 1036 return &taboolist->taboolabels[taboolist->ntaboolabels - k]; 1037 } 1038 1039 /** get number of elements in taboo list */ 1040 static 1041 int taboolistgetNElems( 1042 TABOOLIST* taboolist /**< taboo list data structure */ 1043 ) 1044 { 1045 return taboolist->ntaboolabels; 1046 } 1047 1048 /** free a rolling horizon data structure */ 1049 static 1050 void rollingHorizonFree( 1051 SCIP* scip, /**< SCIP data structure */ 1052 ROLLINGHORIZON** rollinghorizon /**< pointer to rolling horizon data structure */ 1053 ) 1054 { 1055 assert(scip != NULL); 1056 assert(rollinghorizon != NULL); 1057 1058 /* empty rolling horizon */ 1059 if( *rollinghorizon == NULL ) 1060 return; 1061 1062 if( (*rollinghorizon)->variablegraph != NULL ) 1063 { 1064 SCIPvariableGraphFree(scip, &(*rollinghorizon)->variablegraph); 1065 } 1066 1067 SCIPfreeBlockMemoryArray(scip, &(*rollinghorizon)->distances, (*rollinghorizon)->distancessize); 1068 SCIPfreeBlockMemoryArray(scip, &(*rollinghorizon)->used, (*rollinghorizon)->distancessize); 1069 SCIPfreeBlockMemory(scip, rollinghorizon); 1070 } 1071 1072 /** is there potential to run another iteration of the rolling horizon approach? */ 1073 static 1074 SCIP_Bool rollingHorizonRunAgain( 1075 SCIP* scip, /**< SCIP data structure */ 1076 ROLLINGHORIZON* rollinghorizon, /**< rolling horizon data structure */ 1077 SCIP_HEURDATA* heurdata /**< heuristic data */ 1078 ) 1079 { 1080 int maxnused = (int)(heurdata->rollhorizonlimfac * (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) 1081 - rollinghorizon->nnonreachable)); 1082 1083 /* run again if a certain percentage of the reachable variables (in the same connected component) 1084 * was not used in a previous neighborhood 1085 */ 1086 return (rollinghorizon->nused < maxnused); 1087 } 1088 1089 /** store the distances from the selected variable permanently for the rolling horizon approach */ 1090 static 1091 void rollingHorizonStoreDistances( 1092 ROLLINGHORIZON* rollinghorizon, /**< rolling horizon data structure */ 1093 int* distances /**< breadth-first distances indexed by Probindex of variables */ 1094 ) 1095 { 1096 int i; 1097 BMScopyMemoryArray(rollinghorizon->distances, distances, rollinghorizon->distancessize); 1098 rollinghorizon->lastdistance = 0; 1099 rollinghorizon->nnonreachable = 0; 1100 1101 /* collect number of nonreachable variables */ 1102 for( i = 0; i < rollinghorizon->distancessize; ++i ) 1103 { 1104 if( distances[i] == -1 ) 1105 ++rollinghorizon->nnonreachable; 1106 } 1107 } 1108 1109 /** is the variable in the current neighborhood which is given by the breadth-first distances from a central variable? */ 1110 static 1111 SCIP_Bool isVariableInNeighborhood( 1112 SCIP_VAR* var, /**< problem variable */ 1113 int* distances, /**< breadth-first distances indexed by Probindex of variables */ 1114 int maxdistance /**< maximum distance (inclusive) to be considered for neighborhoods */ 1115 ) 1116 { 1117 assert(var != NULL); 1118 assert(distances != NULL); 1119 assert(maxdistance >= 0); 1120 assert(SCIPvarGetProbindex(var) >= 0); 1121 1122 return (distances[SCIPvarGetProbindex(var)] != -1 && distances[SCIPvarGetProbindex(var)] <= maxdistance); 1123 } 1124 1125 /** get fixing value of variable */ 1126 static 1127 SCIP_Real getFixVal( 1128 SCIP* scip, /**< SCIP data structure */ 1129 SCIP_SOL* sol, /**< solution in main SCIP for fixing values */ 1130 SCIP_VAR* var /**< problem variable */ 1131 ) 1132 { 1133 SCIP_Real fixval; 1134 SCIP_Real lb; 1135 SCIP_Real ub; 1136 1137 fixval = SCIPgetSolVal(scip, sol, var); 1138 lb = SCIPvarGetLbGlobal(var); 1139 ub = SCIPvarGetUbGlobal(var); 1140 assert(SCIPisLE(scip, lb, ub)); 1141 1142 /* due to dual reductions, it may happen that the solution value is not in the variable's domain anymore */ 1143 if( SCIPisLT(scip, fixval, lb) ) 1144 fixval = lb; 1145 else if( SCIPisGT(scip, fixval, ub) ) 1146 fixval = ub; 1147 1148 return fixval; 1149 } 1150 1151 /** fixes variables in subproblem based on long breadth-first distances in variable graph */ 1152 static 1153 SCIP_RETCODE fixNonNeighborhoodVariables( 1154 SCIP* scip, /**< SCIP data structure */ 1155 SCIP_HEURDATA* heurdata, /**< heuristic data */ 1156 ROLLINGHORIZON* rollinghorizon, /**< rolling horizon data structure to save relevant information, or NULL if not needed */ 1157 SCIP_SOL* sol, /**< solution in main SCIP for fixing values */ 1158 SCIP_VAR** vars, /**< variables in the main SCIP */ 1159 SCIP_VAR** fixedvars, /**< buffer to store variables that should be fixed */ 1160 SCIP_Real* fixedvals, /**< buffer to store fixing values for fixed variables */ 1161 int* distances, /**< breadth-first distances indexed by Probindex of variables */ 1162 int maxdistance, /**< maximum distance (inclusive) to be considered for neighborhoods */ 1163 int* nfixings /**< pointer to store number of fixed variables */ 1164 ) 1165 { 1166 int i; 1167 int nbinvars; 1168 int nintvars; 1169 int nvars; 1170 int nvarstofix; 1171 1172 SCIP_CALL( SCIPgetVarsData(scip, NULL, &nvars, &nbinvars, &nintvars, NULL, NULL) ); 1173 1174 nvarstofix = heurdata->fixcontvars ? nvars : nbinvars + nintvars; 1175 *nfixings = 0; 1176 1177 /* change bounds of variables of the subproblem */ 1178 for( i = 0; i < nvarstofix; i++ ) 1179 { 1180 /* fix all variables that are too far away from this variable according to maxdistance */ 1181 if( distances[i] == -1 || distances[i] > maxdistance ) 1182 { 1183 SCIP_Real fixval; 1184 1185 fixval = getFixVal(scip, sol, vars[i]); 1186 1187 /* store variable and value of this fixing */ 1188 if( !SCIPisInfinity(scip, REALABS(fixval)) ) 1189 { 1190 fixedvars[*nfixings] = vars[i]; 1191 fixedvals[*nfixings] = fixval; 1192 ++(*nfixings); 1193 } 1194 } 1195 else if( rollinghorizon != NULL && i < nbinvars + nintvars && ! rollinghorizon->used[i] ) 1196 { 1197 ++rollinghorizon->nused; 1198 rollinghorizon->used[i] = TRUE; 1199 } 1200 } 1201 1202 if( rollinghorizon != NULL ) 1203 { 1204 rollinghorizon->lastmaxdistance = maxdistance; 1205 rollinghorizon->niterations++; 1206 } 1207 1208 return SCIP_OKAY; 1209 } 1210 1211 /** determine the maximum allowed distance to stay within the restriction to fix at least minfixingrate many non 1212 * neighborhood variables 1213 */ 1214 static 1215 SCIP_RETCODE determineMaxDistance( 1216 SCIP* scip, /**< SCIP data structure */ 1217 SCIP_HEURDATA* heurdata, /**< heuristic data */ 1218 int* distances, /**< breadth-first distances indexed by Probindex of variables */ 1219 int* choosevardistance /**< pointer to store the computed maximum distance */ 1220 ) 1221 { 1222 int* distancescopy; 1223 int nrelevantdistances; 1224 int criticalidx; 1225 int zeropos; 1226 int nvars; 1227 int nbinvars; 1228 int nintvars; 1229 1230 SCIP_CALL( SCIPgetVarsData(scip, NULL, &nvars, &nbinvars, &nintvars, NULL, NULL) ); 1231 1232 nrelevantdistances = (heurdata->fixcontvars ? nvars : (nbinvars + nintvars)); 1233 1234 /* copy the relevant distances of either the discrete or all problem variables and sort them */ 1235 SCIP_CALL( SCIPduplicateBufferArray(scip, &distancescopy, distances, nrelevantdistances) ); 1236 SCIPsortInt(distancescopy, nrelevantdistances); 1237 1238 /* distances can be infinite in the case of multiple connected components; therefore, search for the index of the 1239 * zero entry, which is the unique representative of the chosen variable in the sorted distances 1240 */ 1241 zeropos = -1; 1242 1243 /* TODO: use selection method instead */ 1244 (void)SCIPsortedvecFindInt(distancescopy, 0, nrelevantdistances, &zeropos); 1245 assert(zeropos >= 0); 1246 1247 /* determine the critical index to look for an appropriate neighborhood distance, starting from the zero position */ 1248 criticalidx = zeropos + (int)((1.0 - heurdata->minfixingrate) * nrelevantdistances); 1249 criticalidx = MIN(criticalidx, nrelevantdistances - 1); 1250 1251 /* determine the maximum breadth-first distance such that the neighborhood size stays small enough (below 1-minfixingrate)*/ 1252 *choosevardistance = distancescopy[criticalidx]; 1253 1254 /* we set the distance to exactly the distance at the critical index. If the distance at critical index is not the 1255 * last one before the distance increases, we decrease the choosevardistance such that the entire neighborhood 1256 * fits into the minfixingrate restriction 1257 */ 1258 if( criticalidx != nrelevantdistances - 1 && distancescopy[criticalidx + 1] == *choosevardistance ) 1259 (*choosevardistance)--; 1260 1261 /* update the maximum distance */ 1262 heurdata->maxseendistance = MAX(heurdata->maxseendistance, distancescopy[nrelevantdistances - 1]); 1263 1264 SCIPfreeBufferArray(scip, &distancescopy); 1265 1266 return SCIP_OKAY; 1267 } 1268 1269 /** gets the average size of a discrete neighborhood over all variables tested */ 1270 static 1271 SCIP_Real heurdataAvgDiscreteNeighborhoodSize( 1272 SCIP_HEURDATA* heurdata /**< heuristic data */ 1273 ) 1274 { 1275 return heurdata->sumdiscneighborhoodvars / (MAX(1.0, (SCIP_Real)heurdata->nneighborhoods)); 1276 } 1277 1278 /** count occurrences of this label */ 1279 static 1280 int countLabel( 1281 int* labels, /**< sorted array of labels */ 1282 int start, /**< start position */ 1283 int nlabels /**< length of the labels array */ 1284 ) 1285 { 1286 int label = labels[start]; 1287 int end = start; 1288 1289 assert(labels != NULL); 1290 assert(start < nlabels); 1291 assert(start >= 0); 1292 1293 do 1294 { 1295 ++end; 1296 } 1297 while( end < nlabels && labels[end] == label ); 1298 1299 return end - start; 1300 } 1301 1302 /** todo select initial variable based on decomposition information, if available */ 1303 static 1304 SCIP_RETCODE selectInitialVariableDecomposition( 1305 SCIP* scip, /**< SCIP data structure */ 1306 SCIP_HEURDATA* heurdata, /**< heuristic data */ 1307 SCIP_DECOMP* decomp, /**< decomposition data structure with variable labels */ 1308 SCIP_VGRAPH* vargraph, /**< variable graph data structure to work on */ 1309 int* distances, /**< breadth-first distances indexed by Probindex of variables */ 1310 SCIP_VAR** selvar, /**< pointer to store the selected variable */ 1311 int* selvarmaxdistance /**< maximal distance k to consider for selected variable neighborhood */ 1312 ) 1313 { 1314 SCIP_SOL* sol; 1315 SCIP_VAR** vars; 1316 SCIP_VAR** varscopy; 1317 int* varlabels; 1318 int* discvaridxs; 1319 SCIP_Real bestpotential; 1320 int nbinvars; 1321 int nintvars; 1322 int nvars; 1323 int currblockstart; 1324 int bestvaridx; 1325 int cntmessages; 1326 int nblocks; 1327 TABOOLIST* taboolist; 1328 1329 assert(scip != NULL); 1330 assert(heurdata != NULL); 1331 assert(decomp != NULL); 1332 assert(vargraph != NULL); 1333 assert(distances != NULL); 1334 assert(selvar != NULL); 1335 assert(selvarmaxdistance != NULL); 1336 1337 sol = SCIPgetBestSol(scip); 1338 assert(sol != NULL); 1339 nblocks = SCIPdecompGetNBlocks(decomp); 1340 /* create a taboo list for recently used block labels at the first initial variable selection */ 1341 if( heurdata->taboolist == NULL ) 1342 { 1343 SCIPdebugMsg(scip, "Creating taboo list\n"); 1344 SCIP_CALL( createTabooList(scip, &heurdata->taboolist, nblocks) ); 1345 } 1346 1347 taboolist = heurdata->taboolist; 1348 assert(taboolist != NULL); 1349 1350 /* reset taboo list if a new solution has been found since the last initialization call */ 1351 if( sol != heurdata->lastinitsol ) 1352 { 1353 int nblockstokeep = 3; 1354 int e; 1355 int ntaboolistelems; 1356 ntaboolistelems = taboolistgetNElems(heurdata->taboolist); 1357 1358 /* keep the last 3 blocks except for border cases of very coarse decomposition, or too few taboo elements */ 1359 if( taboolistgetNElems(heurdata->taboolist) > 0 ) 1360 { 1361 nblockstokeep = MIN(nblockstokeep, nblocks - 1); 1362 nblockstokeep = MIN(nblockstokeep, MAX(1, ntaboolistelems - 1)); 1363 nblockstokeep = MAX(nblockstokeep, 0); 1364 } 1365 else 1366 nblockstokeep = 0; 1367 1368 SCIPdebugMsg(scip, "Resetting taboo list, keeping %d elements\n", nblockstokeep); 1369 if( nblockstokeep > 0 ) 1370 { 1371 int* labelstokeep; 1372 int* taboolistlastk; 1373 taboolistlastk = tabooListGetLastK(taboolist, nblockstokeep); 1374 SCIP_CALL( SCIPduplicateBufferArray(scip, &labelstokeep, taboolistlastk, nblockstokeep) ); 1375 1376 tabooListReset(taboolist); 1377 1378 /* reinstall the last 3 elements into the taboo list */ 1379 for( e = 0; e < nblockstokeep; ++e ) 1380 { 1381 SCIP_CALL( tabooListAdd(scip, taboolist, labelstokeep[e]) ); 1382 } 1383 1384 SCIPfreeBufferArray(scip, &labelstokeep); 1385 } 1386 else if( ntaboolistelems > 0 ) 1387 { 1388 tabooListReset(taboolist); 1389 } 1390 1391 heurdata->allblocksunsuitable = FALSE; 1392 } 1393 1394 *selvar = NULL; 1395 /* do not continue if, for this solution, all blocks are known to be unsuitable */ 1396 if( heurdata->allblocksunsuitable ) 1397 { 1398 SCIPdebugMsg(scip, "Skip initial variable selection because all blocks are unsuitable for solution %d\n", 1399 SCIPsolGetIndex(sol)); 1400 return SCIP_OKAY; 1401 } 1402 1403 /* get integer and binary variables from problem and labels for all variables */ 1404 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) ); 1405 1406 SCIP_CALL( SCIPduplicateBufferArray(scip, &varscopy, vars, nvars) ); 1407 SCIP_CALL( SCIPallocBufferArray(scip, &varlabels, nvars) ); 1408 SCIP_CALL( SCIPallocBufferArray(scip, &discvaridxs, nvars) ); 1409 1410 SCIPdecompGetVarsLabels(decomp, vars, varlabels, nvars); 1411 1412 /* sort the variables copy by the labels */ 1413 SCIPsortIntPtr(varlabels, (void **)varscopy, nvars); 1414 1415 currblockstart = 0; 1416 bestpotential = 0.0; 1417 bestvaridx = -1; 1418 cntmessages = 0; 1419 /* compute the potential for every block */ 1420 while( currblockstart < nvars ) 1421 { 1422 int currblockend; 1423 int v; 1424 int label = varlabels[currblockstart]; 1425 int ndiscblockvars; 1426 SCIP_Real potential; 1427 1428 currblockend = currblockstart + countLabel(varlabels, currblockstart, nvars); 1429 1430 /* this block was recently used and should be skipped */ 1431 if( tabooListFind(taboolist, label) ) 1432 { 1433 if( cntmessages++ < 3 ) 1434 SCIPdebugMsg(scip, "Skipping block <%d> from taboo list\n", label); 1435 1436 currblockstart += currblockend; 1437 1438 continue; 1439 } 1440 1441 /* author bzfhende 1442 * 1443 * TODO omit the linking variables from the computation of the potential? 1444 */ 1445 /* check if block has discrete variables */ 1446 ndiscblockvars = 0; 1447 for( v = currblockstart; v < currblockend; ++v ) 1448 { 1449 if( SCIPvarGetType(varscopy[v]) == SCIP_VARTYPE_BINARY || SCIPvarGetType(varscopy[v]) == SCIP_VARTYPE_INTEGER ) 1450 discvaridxs[ndiscblockvars++] = v; 1451 } 1452 1453 /* skip potential computation if block has no discrete variables */ 1454 if( ndiscblockvars > 0 ) 1455 { 1456 potential = getPotential(scip, heurdata, sol, &(varscopy[currblockstart]), currblockend - currblockstart); 1457 1458 if( potential > bestpotential ) 1459 { 1460 bestpotential = potential; 1461 /* randomize the selection of the best variable */ 1462 bestvaridx = discvaridxs[SCIPrandomGetInt(heurdata->randnumgen, 0, ndiscblockvars - 1)]; 1463 assert(bestvaridx >= 0); 1464 } 1465 } 1466 1467 currblockstart += currblockend; 1468 } 1469 1470 /* we return the first discrete variable from the block with maximum potential */ 1471 if( bestvaridx >= 0 ) 1472 { 1473 *selvar = varscopy[bestvaridx]; 1474 1475 /* save block label in taboo list to not use it again too soon */ 1476 SCIP_CALL( tabooListAdd(scip, taboolist, varlabels[bestvaridx]) ); 1477 1478 SCIPdebugMsg(scip, "Select initial variable <%s> from block <%d>\n", SCIPvarGetName(*selvar), varlabels[bestvaridx]); 1479 } 1480 else 1481 { 1482 SCIPdebugMsg(scip, "Could not find suitable block for variable selection.\n"); 1483 heurdata->allblocksunsuitable = TRUE; 1484 *selvar = NULL; 1485 } 1486 1487 /* use the variable constraint graph to compute distances to all other variables, and store the selvarmaxdistance */ 1488 if( *selvar != NULL ) 1489 { 1490 SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, vargraph, selvar, 1, distances, 1491 heurdata->maxdistance == -1 ? INT_MAX : heurdata->maxdistance, INT_MAX, INT_MAX) ); 1492 1493 SCIP_CALL( determineMaxDistance(scip, heurdata, distances, selvarmaxdistance) ); 1494 1495 /* maximum distance is 0, i.e., even the size of the 1-neighborhood of this variable exceeds the fixing rate */ 1496 if( *selvarmaxdistance == 0 ) 1497 { 1498 SCIPdebugMsg(scip, "1-Neighborhood of variable <%s> too large.\n", SCIPvarGetName(*selvar)); 1499 *selvar = NULL; 1500 } 1501 } 1502 1503 /* remember this solution for the next initial selection */ 1504 heurdata->lastinitsol = sol; 1505 1506 SCIPfreeBufferArray(scip, &discvaridxs); 1507 SCIPfreeBufferArray(scip, &varlabels); 1508 SCIPfreeBufferArray(scip, &varscopy); 1509 1510 return SCIP_OKAY; 1511 } 1512 1513 1514 1515 /** select a good starting variable at the first iteration of a rolling horizon approach */ 1516 static 1517 SCIP_RETCODE selectInitialVariableRandomly( 1518 SCIP* scip, /**< SCIP data structure */ 1519 SCIP_HEURDATA* heurdata, /**< heuristic data */ 1520 SCIP_VGRAPH* vargraph, /**< variable graph data structure to work on */ 1521 int* distances, /**< breadth-first distances indexed by Probindex of variables */ 1522 SCIP_VAR** selvar, /**< pointer to store the selected variable */ 1523 int* selvarmaxdistance /**< maximal distance k to consider for selected variable neighborhood */ 1524 ) 1525 { 1526 SCIP_SOL* sol; 1527 SCIP_VAR** vars; /* original scip variables */ 1528 int nbinvars; 1529 int nintvars; 1530 int nvars; 1531 int nsearched; 1532 int searchlimit; 1533 int nintegralvarsleft; 1534 int nintegralvarsbound; 1535 int v; 1536 SCIP_VAR** varscopy; 1537 int maxdistance; 1538 SCIP_Real maxpotential; 1539 1540 assert(vargraph != NULL); 1541 assert(scip != NULL); 1542 assert(heurdata != NULL); 1543 assert(selvar != NULL); 1544 sol = SCIPgetBestSol(scip); 1545 assert(sol != NULL); 1546 1547 /* get required data of the original problem */ 1548 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) ); 1549 1550 /* copy SCIP variables */ 1551 SCIP_CALL( SCIPduplicateBufferArray(scip, &varscopy, vars, nbinvars + nintvars) ); 1552 nsearched = 0; 1553 maxpotential = SCIP_REAL_MIN; 1554 1555 /* determine upper bound on neighborhood size */ 1556 nintegralvarsbound = (int)((1.0 - heurdata->minfixingrate) * (nbinvars + nintvars)); 1557 1558 /* maximum distance from selected variable for breadth-first search (if set to -1, we compute an exhaustive breadth-first 1559 * search and sort the variables by their distance) 1560 */ 1561 maxdistance = (heurdata->maxdistance == - 1 ? INT_MAX : heurdata->maxdistance); 1562 1563 nintegralvarsleft = nbinvars + nintvars; 1564 *selvar = NULL; 1565 1566 /* sort inactive variables to the end of the array */ 1567 for( v = nintegralvarsleft - 1; v >= 0; --v ) 1568 { 1569 if( ! SCIPvarIsActive(varscopy[v]) ) 1570 { 1571 varscopy[v] = varscopy[nintegralvarsleft - 1]; 1572 --nintegralvarsleft; 1573 } 1574 } 1575 1576 /* adjust the search limit */ 1577 searchlimit = heurdata->nneighborhoods < 10 ? 5 : (int)(nintegralvarsleft / heurdataAvgDiscreteNeighborhoodSize(heurdata)); 1578 searchlimit = MIN(searchlimit, 10); 1579 1580 /* multi variable potential: choose different disjoint neighborhoods, compare their potential */ 1581 while( nsearched < searchlimit && nintegralvarsleft > 0 ) 1582 { 1583 SCIP_VAR** neighborhood; 1584 SCIP_VAR* choosevar; 1585 int neighborhoodsize; 1586 int ndiscvarsneighborhood; 1587 int choosevardistance; 1588 1589 ++nsearched; 1590 1591 /* select a variable to start with randomly, but make sure it is active */ 1592 do 1593 { 1594 int idx = SCIPrandomGetInt(heurdata->randnumgen, 0, nintegralvarsleft - 1); 1595 choosevar = varscopy[idx]; 1596 assert(choosevar != NULL); 1597 /* sort inactive variables to the end */ 1598 if( SCIPvarGetProbindex(choosevar) < 0 ) 1599 { 1600 varscopy[idx] = varscopy[nintegralvarsleft - 1]; 1601 --nintegralvarsleft; 1602 } 1603 } 1604 while( SCIPvarGetProbindex(choosevar) < 0 && nintegralvarsleft > 0 ); 1605 1606 /* if there was no variable chosen, there are no active variables left */ 1607 if( SCIPvarGetProbindex(choosevar) < 0 ) 1608 { 1609 SCIPdebugMsg(scip, "No active variable left to perform breadth-first search\n"); 1610 break; 1611 } 1612 1613 assert(SCIPvarIsIntegral(choosevar)); 1614 1615 /* get neighborhood storage */ 1616 SCIP_CALL( SCIPallocBufferArray(scip, &neighborhood, nvars) ); 1617 1618 /* determine breadth-first distances from the chosen variable */ 1619 SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, vargraph, &choosevar, 1, distances, maxdistance, INT_MAX, INT_MAX) ); 1620 1621 /* use either automatic or user-defined max-distance for neighborhood in variable constraint graph */ 1622 if( heurdata->maxdistance != -1 ) 1623 { 1624 choosevardistance = heurdata->maxdistance; 1625 } 1626 else 1627 { 1628 SCIP_CALL( determineMaxDistance(scip, heurdata, distances, &choosevardistance) ); 1629 } 1630 1631 ndiscvarsneighborhood = 0; 1632 neighborhoodsize = 0; 1633 1634 /* loop over variables and determine neighborhood */ 1635 for( v = nvars - 1; v >= 0; --v ) 1636 { 1637 SCIP_VAR* currvar; 1638 currvar = vars[v]; 1639 1640 /* put variable in the neighborhood */ 1641 if( isVariableInNeighborhood(currvar, distances, choosevardistance) ) 1642 { 1643 neighborhood[neighborhoodsize++] = currvar; 1644 1645 /* increase discrete variables counter */ 1646 if( SCIPvarIsIntegral(currvar) ) 1647 ++ndiscvarsneighborhood; 1648 } 1649 } 1650 1651 /* check if neighborhood contains too many integer variables in order to satisfy the minimum fixing rate */ 1652 if( ndiscvarsneighborhood >= nintegralvarsbound || ndiscvarsneighborhood <= 1 ) 1653 { 1654 SCIPdebugMsg(scip, "Too many or too few discrete variables in neighboorhood: %d (%d)\n", 1655 ndiscvarsneighborhood, nbinvars + nintvars); 1656 } 1657 else 1658 { 1659 /* compare the neighborhood potential to the best potential found so far */ 1660 SCIP_Real potential = getPotential(scip, heurdata, sol, neighborhood, neighborhoodsize); 1661 1662 /* big potential, take this variable */ 1663 if( potential > maxpotential ) 1664 { 1665 maxpotential = potential; 1666 *selvar = choosevar; 1667 *selvarmaxdistance = choosevardistance; 1668 } 1669 } 1670 1671 /* sort neighborhood variables to the end so that this neighborhood is not considered in further samples */ 1672 for( v = nintegralvarsleft - 1; v >= 0; --v ) 1673 { 1674 SCIP_VAR* currvar; 1675 currvar = vars[v]; 1676 1677 if( isVariableInNeighborhood(currvar, distances, choosevardistance) ) 1678 { 1679 varscopy[v] = varscopy[nintegralvarsleft - 1]; 1680 --nintegralvarsleft; 1681 } 1682 } 1683 1684 heurdata->sumdiscneighborhoodvars += ndiscvarsneighborhood; 1685 heurdata->sumneighborhoodvars += neighborhoodsize; 1686 ++heurdata->nneighborhoods; 1687 1688 /* free current neighborhood */ 1689 SCIPfreeBufferArray(scip, &neighborhood); 1690 } 1691 1692 SCIPfreeBufferArray(scip, &varscopy); 1693 1694 /* maybe no variable has a positive delta */ 1695 if( !SCIPisPositive(scip, maxpotential) || *selvar == NULL ) 1696 { 1697 SCIPdebugMsg(scip, "Stopping with maxpotential %15.9f and selected variable %s\n", 1698 maxpotential, *selvar != NULL ? SCIPvarGetName(*selvar) : "none"); 1699 *selvar = NULL; 1700 } 1701 1702 return SCIP_OKAY; 1703 } 1704 1705 /** select the next variable using the rolling horizon */ 1706 static 1707 SCIP_RETCODE selectNextVariable( 1708 SCIP* scip, /**< SCIP data structure */ 1709 SCIP_HEURDATA* heurdata, /**< heuristic data */ 1710 ROLLINGHORIZON* rollinghorizon, /**< rolling horizon data structure to save relevant information, or NULL if not needed */ 1711 int* distances, /**< breadth-first distances indexed by Probindex of variables */ 1712 SCIP_VAR** selvar, /**< pointer to store the selected variable */ 1713 int* selvarmaxdistance /**< maximal distance k to consider for selected variable neighborhood */ 1714 ) 1715 { 1716 SCIP_VAR** vars; /* original scip variables */ 1717 int i; 1718 int nbinvars; 1719 int nintvars; 1720 int minunuseddistance; 1721 1722 assert(scip != NULL); 1723 assert(rollinghorizon != NULL); 1724 assert(distances != NULL); 1725 assert(selvar != NULL); 1726 assert(selvarmaxdistance != NULL); 1727 1728 SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) ); 1729 1730 /* loop over the variables that are left and pick the variable with 1731 * - the smallest, always nondecreasing distance 1732 * - that was not used before in a neighborhood 1733 */ 1734 do 1735 { 1736 minunuseddistance = INT_MAX; 1737 *selvarmaxdistance = rollinghorizon->lastmaxdistance; 1738 *selvar = NULL; 1739 for( i = 0; i < nbinvars + nintvars && minunuseddistance > rollinghorizon->lastdistance; ++i ) 1740 { 1741 if( rollinghorizon->distances[i] >= rollinghorizon->lastdistance 1742 && rollinghorizon->distances[i] < minunuseddistance && ! rollinghorizon->used[i] ) 1743 { 1744 minunuseddistance = rollinghorizon->distances[i]; 1745 *selvar = vars[i]; 1746 } 1747 } 1748 1749 /* if no variable could be selected, we can stop */ 1750 if( *selvar == NULL ) 1751 { 1752 *selvarmaxdistance = 0; 1753 return SCIP_OKAY; 1754 } 1755 1756 /* determine the distances to other variables from this variable */ 1757 SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, rollinghorizon->variablegraph, selvar, 1, distances, *selvarmaxdistance, INT_MAX, INT_MAX) ); 1758 1759 SCIP_CALL( determineMaxDistance(scip, heurdata, distances, selvarmaxdistance) ); 1760 1761 /* mark this variable as used in order to not find it again */ 1762 if( *selvarmaxdistance == 0 ) 1763 { 1764 rollinghorizon->used[SCIPvarGetProbindex(*selvar)] = TRUE; 1765 rollinghorizon->nused++; 1766 *selvar = NULL; 1767 } 1768 } 1769 while( rollingHorizonRunAgain(scip, rollinghorizon, heurdata) && (*selvar == NULL || *selvarmaxdistance == 0) ); 1770 1771 /* breadth-first search determines the distances of all variables 1772 * that are no more than maxdistance away from the start variable 1773 */ 1774 assert(*selvarmaxdistance <= rollinghorizon->lastmaxdistance); 1775 *selvarmaxdistance = MIN(*selvarmaxdistance, rollinghorizon->lastmaxdistance); 1776 rollinghorizon->lastdistance = minunuseddistance; 1777 rollinghorizon->lastmaxdistance = *selvarmaxdistance; 1778 1779 return SCIP_OKAY; 1780 } 1781 1782 /** mark some of the blocks between currblockstart and currblockend as recently used, depending on overlap */ 1783 static 1784 void decompHorizonMarkInterval( 1785 SCIP* scip, /**< SCIP data structure */ 1786 DECOMPHORIZON* decomphorizon, /**< decomposition horizon data structure */ 1787 SCIP_HEURDATA* heurdata, /**< heuristic data */ 1788 SCIP_SOL* sol, /**< solution by which some of the blocks should be marked */ 1789 int blockstartpos, /**< current start position of interval */ 1790 int blockendpos /**< current end position (inclusive) of interval */ 1791 ) 1792 { 1793 int nvarsinterval; 1794 int nvarsstartofinterval; 1795 int solstamppos; 1796 int b; 1797 SCIP_Real overlapcomplement; 1798 1799 assert(decomphorizon != NULL); 1800 assert(heurdata != NULL); 1801 1802 /* is the next block unsuitable or have we reached the end of the blocks? In those cases, 1803 * we mark all blocks of the current interval; we hence avoid to rerun on a subset of the current subproblem 1804 * in the next iteration; we achieve this by setting the overlap to 0.0, (its complement to 1.0) 1805 * such that all blocks are marked 1806 */ 1807 if( blockendpos == decomphorizon->nblocks - 1 || ! decomphorizon->suitable[decomphorizon->blockindices[blockendpos + 1]] ) 1808 overlapcomplement = 1.0; 1809 else 1810 overlapcomplement = 1.0 - heurdata->overlap; 1811 1812 /* count the total number of variables in the subproblem defining blocks */ 1813 nvarsinterval = 0; 1814 for( b = blockstartpos; b <= blockendpos; ++b ) 1815 nvarsinterval += decomphorizon->ndiscretevars[decomphorizon->blockindices[b]]; 1816 1817 nvarsstartofinterval = 0; 1818 /* stamp the first blocks up to the desired overlap by the current incumbent solution */ 1819 for( solstamppos = blockstartpos; solstamppos <= blockendpos; ++solstamppos ) 1820 { 1821 decomphorizon->lastsolblock[decomphorizon->blockindices[solstamppos]] = sol; 1822 nvarsstartofinterval += decomphorizon->ndiscretevars[decomphorizon->blockindices[solstamppos]]; 1823 1824 if( nvarsstartofinterval >= overlapcomplement * nvarsinterval ) 1825 break; 1826 } 1827 decomphorizon->lastblockpos = solstamppos; 1828 SCIPdebugMsg(scip, "Blocks %d (label %d)-- %d (label %d) marked with incumbent solution\n", 1829 blockstartpos, decomphorizon->blocklabels[decomphorizon->blockindices[blockstartpos]], 1830 solstamppos, decomphorizon->blocklabels[decomphorizon->blockindices[solstamppos]]); 1831 1832 /* remember the blocks up to the found position as most recent overlap interval */ 1833 decompHorizonSetOverlapInterval(decomphorizon, blockstartpos, solstamppos); 1834 } 1835 1836 /** determine the variable fixings based on a decomposition */ 1837 static 1838 SCIP_RETCODE determineVariableFixingsDecomp( 1839 SCIP* scip, /**< SCIP data structure */ 1840 DECOMPHORIZON* decomphorizon, /**< decomposition horizon data structure */ 1841 SCIP_VAR** fixedvars, /**< buffer to store variables that should be fixed */ 1842 SCIP_Real* fixedvals, /**< buffer to store fixing values for fixed variables */ 1843 int* nfixings, /**< pointer to store the number of fixed variables */ 1844 SCIP_HEURDATA* heurdata, /**< heuristic data */ 1845 SCIP_Bool* success /**< used to store whether the creation of the subproblem worked */ 1846 ) 1847 { 1848 SCIP_SOL* sol; 1849 SCIP_Bool hasnext; 1850 SCIP_Bool fixlinkvars; 1851 int currblockstart; 1852 int currblockend; 1853 int currblocklabel; 1854 int maxblocksize; 1855 1856 assert(scip != NULL); 1857 assert(decomphorizon != NULL); 1858 1859 sol = SCIPgetBestSol(scip); 1860 1861 /* initialize the decomposition horizon first for the current variables */ 1862 if( ! decompHorizonIsInitialized(decomphorizon) ) 1863 { 1864 SCIP_CALL( decompHorizonInitialize(scip, decomphorizon, heurdata) ); 1865 } 1866 1867 maxblocksize = (int)((1.0 - heurdata->minfixingrate) * (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip))) - 1; 1868 1869 /* query the next suitable interval of blocks */ 1870 hasnext = decompHorizonNext(scip, decomphorizon, heurdata, maxblocksize, 1871 &currblockstart, &currblockend, &currblocklabel, &fixlinkvars); 1872 1873 if( ! hasnext ) 1874 { 1875 SCIPdebugMsg(scip, "Could not find a suitable interval that follows %d\n", 1876 decomphorizon->lastblockpos); 1877 1878 *success = FALSE; 1879 } 1880 else 1881 { 1882 /* fix all discrete/continuous variables that are not part of this interval */ 1883 SCIP_VAR** vars; 1884 int v; 1885 int startblockposs[] = {fixlinkvars ? 0 : 1, currblockend + 1}; 1886 int endblockposs[] = {currblockstart, decomphorizon->nblocks}; 1887 int p; 1888 int b; 1889 1890 SCIPdebugMsg(scip, "Fix %s variables (%scluding linking variables) except blocks %d (label %d) -- %d (label %d)\n", 1891 heurdata->fixcontvars ? "all" : "discrete", 1892 fixlinkvars ? "in" : "ex", 1893 currblockstart, decomphorizon->blocklabels[decomphorizon->blockindices[currblockstart]], 1894 currblockend, decomphorizon->blocklabels[decomphorizon->blockindices[currblockend]]); 1895 1896 vars = decomphorizonGetVars(decomphorizon); 1897 1898 /* iterate over the two blocks left and right of the selected consecutive interval and fix all variables 1899 * 1900 * 0, ... b, ... ,[currblockstart, ..., currblockend], currblockend + 1, ..., decomphorizon->nblocks - 1 1901 */ 1902 for( p = 0; p < 2; ++p ) 1903 { 1904 /* iterate over all blocks and fix those outside of the blocks interval that defines the current subproblem */ 1905 for( b = startblockposs[p]; b < endblockposs[p]; ++b ) 1906 { 1907 int blockind = decomphorizon->blockindices[b]; 1908 int varstartpos = blockind == 0 ? 0 : decomphorizon->varblockend[blockind - 1]; 1909 int varendpos = decomphorizon->varblockend[blockind]; 1910 1911 /* fix variables inside of this block */ 1912 for( v = varstartpos; v < varendpos; ++v ) 1913 { 1914 SCIP_VAR* var = vars[v]; 1915 1916 if( heurdata->fixcontvars || SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS ) 1917 { 1918 SCIP_Real fixval; 1919 1920 fixval = getFixVal(scip, sol, var); 1921 1922 /* store variable and value of this fixing */ 1923 if( !SCIPisInfinity(scip, REALABS(fixval)) ) 1924 { 1925 fixedvars[*nfixings] = var; 1926 fixedvals[*nfixings] = fixval; 1927 ++(*nfixings); 1928 } 1929 } 1930 } 1931 } 1932 } 1933 1934 *success = checkFixingrate(scip, heurdata, *nfixings); 1935 1936 decompHorizonMarkInterval(scip, decomphorizon, heurdata, sol, currblockstart, currblockend); 1937 } 1938 1939 return SCIP_OKAY; /*lint !e438*/ 1940 } 1941 1942 /** choose a decomposition from the store or return NULL if none exists/no decomposition was suitable */ 1943 static 1944 SCIP_DECOMP* chooseDecomp( 1945 SCIP* scip /**< SCIP data structure */ 1946 ) 1947 { 1948 SCIP_DECOMP** decomps; 1949 int ndecomps; 1950 int currdecomp; 1951 1952 /* TODO coming soon: better selection than last nontrivial decomposition that has been input */ 1953 SCIPgetDecomps(scip, &decomps, &ndecomps, FALSE); 1954 currdecomp = ndecomps; 1955 1956 while( --currdecomp >= 0 ) 1957 { 1958 if( SCIPdecompGetNBlocks(decomps[currdecomp]) > 0 ) 1959 return decomps[currdecomp]; 1960 } 1961 1962 return NULL; 1963 } 1964 1965 /** determines the graph-induced variable fixings */ 1966 static 1967 SCIP_RETCODE determineVariableFixings( 1968 SCIP* scip, /**< original SCIP data structure */ 1969 SCIP_VAR** fixedvars, /**< buffer to store variables that should be fixed */ 1970 SCIP_Real* fixedvals, /**< buffer to store fixing values for fixed variables */ 1971 int* nfixings, /**< pointer to store the number of fixed variables */ 1972 SCIP_HEURDATA* heurdata, /**< heuristic data */ 1973 ROLLINGHORIZON* rollinghorizon, /**< rolling horizon data structure to save relevant information, or NULL if not needed */ 1974 DECOMPHORIZON* decomphorizon, /**< decomposition horizon data structure, or NULL */ 1975 SCIP_Bool* success /**< used to store whether the creation of the subproblem worked */ 1976 ) 1977 { 1978 SCIP_VAR** vars; 1979 SCIP_SOL* sol; 1980 int* distances; 1981 SCIP_VGRAPH* vargraph; 1982 SCIP_VAR* selvar; 1983 int nvars; 1984 int nbinvars; 1985 int nintvars; 1986 1987 int selvarmaxdistance; 1988 1989 assert(fixedvars != NULL); 1990 assert(fixedvals != NULL); 1991 assert(nfixings != NULL); 1992 1993 *success = TRUE; 1994 *nfixings = 0; 1995 selvarmaxdistance = 0; 1996 sol = SCIPgetBestSol(scip); 1997 assert(sol != NULL); 1998 1999 /* determine the variable fixings based on latest user decomposition */ 2000 if( decomphorizon != NULL ) 2001 { 2002 SCIP_CALL( determineVariableFixingsDecomp(scip, decomphorizon, fixedvars, fixedvals, nfixings, heurdata, success) ); 2003 2004 /* do not use fallback strategy if user parameter does not allow it */ 2005 if( *success || ! heurdata->useselfallback ) 2006 return SCIP_OKAY; 2007 } 2008 2009 /* get required data of the source problem */ 2010 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) ); 2011 /* get the saved variable graph, or create a new one */ 2012 if( rollinghorizon != NULL ) 2013 { 2014 if( rollinghorizon->niterations == 0 ) 2015 { 2016 /* create variable graph */ 2017 SCIPdebugMsg(scip, "Creating variable constraint graph\n"); 2018 SCIP_CALL( SCIPvariableGraphCreate(scip, &rollinghorizon->variablegraph, heurdata->relaxdenseconss, 1.0 - heurdata->minfixingrate, &heurdata->nrelaxedconstraints) ); 2019 } 2020 else 2021 assert(rollinghorizon->variablegraph != NULL); 2022 2023 vargraph = rollinghorizon->variablegraph; 2024 } 2025 else 2026 { 2027 /* create variable graph */ 2028 SCIPdebugMsg(scip, "Creating variable constraint graph\n"); 2029 SCIP_CALL( SCIPvariableGraphCreate(scip, &vargraph, heurdata->relaxdenseconss, 1.0 - heurdata->minfixingrate, &heurdata->nrelaxedconstraints) ); 2030 } 2031 2032 /* allocate buffer memory to hold distances */ 2033 SCIP_CALL( SCIPallocBufferArray(scip, &distances, nvars) ); 2034 2035 selvar = NULL; 2036 2037 /* in the first iteration of the rolling horizon approach, we select an initial variable */ 2038 if( rollinghorizon == NULL || rollinghorizon->niterations == 0 ) 2039 { 2040 SCIP_Bool userandomselection = TRUE; 2041 2042 /* choose the initial variable based on a user decomposition, if available */ 2043 if( heurdata->usedecomprollhorizon ) 2044 { 2045 SCIP_DECOMP* decomp = chooseDecomp(scip); 2046 if( decomp != NULL ) 2047 { 2048 SCIP_CALL( selectInitialVariableDecomposition(scip, heurdata, decomp, vargraph, 2049 distances, &selvar, &selvarmaxdistance) ); 2050 2051 userandomselection = (selvar == NULL && heurdata->useselfallback); 2052 } 2053 } 2054 2055 assert(selvar == NULL || !userandomselection); 2056 /* use random variable selection as fallback strategy, if no user decomposition is available, or the 2057 * heuristic should not use decomposition 2058 */ 2059 if( userandomselection ) 2060 { 2061 SCIP_CALL( selectInitialVariableRandomly(scip, heurdata, vargraph, distances, &selvar, &selvarmaxdistance) ); 2062 } 2063 2064 /* collect and save the distances in the rolling horizon data structure */ 2065 if( selvar != NULL && rollinghorizon != NULL ) 2066 { 2067 /* collect distances in the variable graph of all variables to the selected variable */ 2068 SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, vargraph, &selvar, 1, distances, INT_MAX, INT_MAX, INT_MAX) ); 2069 rollingHorizonStoreDistances(rollinghorizon, distances); 2070 rollinghorizon->lastmaxdistance = selvarmaxdistance; 2071 } 2072 } 2073 else 2074 { 2075 /* select the next variable, if variables are left */ 2076 SCIP_CALL( selectNextVariable(scip, heurdata, rollinghorizon, distances, &selvar, &selvarmaxdistance) ); 2077 } 2078 2079 assert(selvar == NULL || selvarmaxdistance > 0); 2080 if( selvar == NULL ) 2081 { 2082 *success = FALSE; 2083 } 2084 else 2085 { 2086 SCIPdebugMsg(scip, "Selected variable <%s> as central variable for a <%d>-neighborhood\n", 2087 SCIPvarGetName(selvar), selvarmaxdistance); 2088 2089 /* fix variables that are not in the neighborhood around the selected variable */ 2090 SCIP_CALL( fixNonNeighborhoodVariables(scip, heurdata, rollinghorizon, sol, vars, fixedvars, fixedvals, distances, 2091 selvarmaxdistance, nfixings) ); 2092 2093 *success = checkFixingrate(scip, heurdata, *nfixings); 2094 } 2095 2096 SCIPfreeBufferArray(scip, &distances); 2097 if( rollinghorizon == NULL ) 2098 SCIPvariableGraphFree(scip, &vargraph); 2099 2100 return SCIP_OKAY; 2101 } 2102 2103 /** set sub-SCIP solving limits */ 2104 static 2105 SCIP_RETCODE setLimits( 2106 SCIP* sourcescip, /**< SCIP data structure */ 2107 SCIP* subscip, /**< SCIP data structure */ 2108 SOLVELIMITS* solvelimits /**< pointer to solving limits data structure */ 2109 ) 2110 { 2111 assert(sourcescip != NULL); 2112 assert(subscip != NULL); 2113 assert(solvelimits != NULL); 2114 2115 SCIP_CALL( SCIPcopyLimits(sourcescip, subscip) ); 2116 2117 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", solvelimits->nodelimit) ); 2118 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", solvelimits->stallnodelimit) ); 2119 2120 /* safe long running times caused by lack of dual convergence */ 2121 SCIP_CALL( SCIPsetRealParam(subscip, "limits/gap", 0.01) ); 2122 2123 return SCIP_OKAY; 2124 } 2125 2126 /** set up the sub-SCIP */ 2127 static 2128 SCIP_RETCODE setupSubScip( 2129 SCIP* scip, /**< SCIP data structure */ 2130 SCIP* subscip, /**< sub-SCIP data structure */ 2131 SOLVELIMITS* solvelimits, /**< pointer to solving limits data structure */ 2132 SCIP_HEUR* heur /**< this heuristic */ 2133 ) 2134 { 2135 SCIP_HEURDATA* heurdata; 2136 SCIP_Real cutoff; 2137 SCIP_Real upperbound; 2138 2139 heurdata = SCIPheurGetData(heur); 2140 2141 /* do not abort subproblem on CTRL-C */ 2142 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) ); 2143 2144 /* disable output to console */ 2145 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) ); 2146 2147 /* disable statistic timing inside sub SCIP */ 2148 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) ); 2149 2150 SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->bestsollimit) ); 2151 2152 /* forbid recursive call of heuristics and separators solving subMIPs */ 2153 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) ); 2154 2155 /* disable cutting plane separation */ 2156 SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) ); 2157 2158 /* disable expensive presolving */ 2159 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) ); 2160 2161 /* use best estimate node selection */ 2162 if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") ) 2163 { 2164 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) ); 2165 } 2166 2167 /* use inference branching */ 2168 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") ) 2169 { 2170 SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) ); 2171 } 2172 2173 /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */ 2174 if( !SCIPisParamFixed(subscip, "conflict/enable") ) 2175 { 2176 SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) ); 2177 } 2178 if( !SCIPisParamFixed(subscip, "conflict/useboundlp") ) 2179 { 2180 SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') ); 2181 } 2182 if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") ) 2183 { 2184 SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) ); 2185 } 2186 2187 /* speed up sub-SCIP by not checking dual LP feasibility */ 2188 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) ); 2189 2190 /* add an objective cutoff */ 2191 assert( !SCIPisInfinity(scip, SCIPgetUpperbound(scip)) ); 2192 2193 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip); 2194 if( !SCIPisInfinity(scip, -1.0 * SCIPgetLowerbound(scip)) ) 2195 { 2196 cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip) 2197 + heurdata->minimprove * SCIPgetLowerbound(scip); 2198 } 2199 else 2200 { 2201 if( SCIPgetUpperbound(scip) >= 0 ) 2202 cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip); 2203 else 2204 cutoff = (1 + heurdata->minimprove) * SCIPgetUpperbound(scip); 2205 } 2206 cutoff = MIN(upperbound, cutoff); 2207 SCIP_CALL(SCIPsetObjlimit(subscip, cutoff)); 2208 2209 /* set solve limits for sub-SCIP */ 2210 SCIP_CALL( setLimits(scip, subscip, solvelimits) ); 2211 2212 return SCIP_OKAY; 2213 } 2214 2215 /** determine limits for a sub-SCIP */ 2216 static 2217 SCIP_RETCODE determineLimits( 2218 SCIP* scip, /**< SCIP data structure */ 2219 SCIP_HEUR* heur, /**< this heuristic */ 2220 SOLVELIMITS* solvelimits, /**< pointer to solving limits data structure */ 2221 SCIP_Bool* runagain /**< can we solve another sub-SCIP with these limits */ 2222 ) 2223 { 2224 SCIP_HEURDATA* heurdata; 2225 SCIP_Real maxnnodesr; 2226 SCIP_Real confidence; 2227 SCIP_Longint maxnnodes; 2228 SCIP_Bool copylimits; 2229 2230 assert(scip != NULL); 2231 assert(heur != NULL); 2232 assert(solvelimits != NULL); 2233 assert(runagain != NULL); 2234 2235 heurdata = SCIPheurGetData(heur); 2236 2237 /* check whether there is enough time and memory left */ 2238 SCIP_CALL( SCIPcheckCopyLimits(scip, ©limits) ); 2239 2240 if( ! copylimits ) 2241 *runagain = FALSE; 2242 2243 /* calculate the maximal number of branching nodes until heuristic is aborted */ 2244 maxnnodesr = heurdata->nodesquot * SCIPgetNNodes(scip); 2245 2246 /* reward gins if it succeeded often, count the setup costs for the sub-MIP as 100 nodes */ 2247 confidence = (SCIP_Real)SCIPheurGetNCalls(heur); 2248 confidence = confidence / (confidence + 5.0); 2249 maxnnodesr *= 1.0 + confidence * 2.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(heurdata->nsubmips + 1.0); 2250 maxnnodes = (SCIP_Longint)(maxnnodesr - 100.0 * heurdata->nsubmips); 2251 maxnnodes += heurdata->nodesofs; 2252 2253 /* determine the node limit for the current process */ 2254 solvelimits->nodelimit = maxnnodes - heurdata->usednodes; 2255 solvelimits->nodelimit = MIN(solvelimits->nodelimit, heurdata->maxnodes); 2256 2257 /* check whether we have enough nodes left to call subproblem solving */ 2258 if( solvelimits->nodelimit < heurdata->targetnodes ) 2259 *runagain = FALSE; 2260 2261 solvelimits->stallnodelimit = heurdata->targetnodes; 2262 2263 return SCIP_OKAY; 2264 } 2265 2266 /** updates heurdata after a run of GINS */ 2267 static 2268 void updateFailureStatistic( 2269 SCIP* scip, /**< original SCIP data structure */ 2270 SCIP_HEURDATA* heurdata /**< primal heuristic data */ 2271 ) 2272 { 2273 /* increase number of failures, calculate next node at which GINS should be called and update actual solutions */ 2274 heurdata->nfailures++; 2275 heurdata->nextnodenumber = (heurdata->nfailures <= 25 2276 ? SCIPgetNNodes(scip) + 100*(2LL << heurdata->nfailures) /*lint !e703*/ 2277 : SCIP_LONGINT_MAX); 2278 } 2279 2280 2281 /* 2282 * Callback methods of primal heuristic 2283 */ 2284 2285 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 2286 static 2287 SCIP_DECL_HEURCOPY(heurCopyGins) 2288 { /*lint --e{715}*/ 2289 assert(scip != NULL); 2290 assert(heur != NULL); 2291 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 2292 2293 /* call inclusion method of primal heuristic */ 2294 SCIP_CALL( SCIPincludeHeurGins(scip) ); 2295 2296 return SCIP_OKAY; 2297 } 2298 2299 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 2300 static 2301 SCIP_DECL_HEURFREE(heurFreeGins) 2302 { /*lint --e{715}*/ 2303 SCIP_HEURDATA* heurdata; 2304 2305 assert(heur != NULL); 2306 assert(scip != NULL); 2307 2308 /* get heuristic data */ 2309 heurdata = SCIPheurGetData(heur); 2310 assert(heurdata != NULL); 2311 2312 /* free heuristic data */ 2313 SCIPfreeBlockMemory(scip, &heurdata); 2314 SCIPheurSetData(heur, NULL); 2315 2316 return SCIP_OKAY; 2317 } 2318 2319 /** initialization method of primal heuristic (called after problem was transformed) */ 2320 static 2321 SCIP_DECL_HEURINIT(heurInitGins) 2322 { /*lint --e{715}*/ 2323 SCIP_HEURDATA* heurdata; 2324 2325 assert(heur != NULL); 2326 assert(scip != NULL); 2327 2328 /* get heuristic's data */ 2329 heurdata = SCIPheurGetData(heur); 2330 assert(heurdata != NULL); 2331 assert(heurdata->randnumgen == NULL); 2332 2333 /* initialize data */ 2334 heurdata->usednodes = 0; 2335 SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE) ); 2336 heurdata->sumdiscneighborhoodvars = heurdata->sumneighborhoodvars = 0; 2337 heurdata->nneighborhoods = 0; 2338 heurdata->maxseendistance = 0; 2339 heurdata->nsubmips = 0; 2340 heurdata->nfailures = 0; 2341 heurdata->nextnodenumber = 0; 2342 heurdata->lastinitsol = NULL; 2343 heurdata->allblocksunsuitable = FALSE; 2344 heurdata->taboolist = NULL; 2345 heurdata->targetnodes = heurdata->minnodes; 2346 2347 return SCIP_OKAY; 2348 } 2349 2350 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */ 2351 static 2352 SCIP_DECL_HEUREXITSOL(heurExitsolGins) 2353 { /*lint --e{715}*/ 2354 SCIP_HEURDATA* heurdata; 2355 2356 assert(heur != NULL); 2357 assert(scip != NULL); 2358 2359 /* get heuristic data */ 2360 heurdata = SCIPheurGetData(heur); 2361 assert(heurdata != NULL); 2362 2363 /* it is likely that the decomposition information changes between runs, we recreate the decomposition horizon */ 2364 decompHorizonFree(scip, &heurdata->decomphorizon); 2365 assert(heurdata->decomphorizon == NULL); 2366 2367 return SCIP_OKAY; 2368 } 2369 2370 /** initialization method of primal heuristic (called after problem was transformed) */ 2371 static 2372 SCIP_DECL_HEUREXIT(heurExitGins) 2373 { /*lint --e{715}*/ 2374 SCIP_HEURDATA* heurdata; 2375 2376 assert(heur != NULL); 2377 assert(scip != NULL); 2378 2379 /* get heuristic's data */ 2380 heurdata = SCIPheurGetData(heur); 2381 assert(heurdata != NULL); 2382 2383 SCIPstatistic( 2384 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Gins: Avg Neighborhood size: %.1f Avg. discrete neighboorhood vars: %.1f\n", 2385 heurdataAvgNeighborhoodSize(heurdata), heurdataAvgDiscreteNeighborhoodSize(heurdata)); 2386 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Gins: Max seen distance %d\n", heurdata->maxseendistance); 2387 printHistogram(scip, heurdata->consvarshist, "Constraint density histogram"); 2388 printHistogram(scip, heurdata->conscontvarshist, "Constraint continuous density histogram"); 2389 printHistogram(scip, heurdata->consdiscvarshist, "Constraint discrete density histogram"); 2390 ) 2391 2392 /* free some data structures that must be reset for a new problem */ 2393 freeTabooList(scip, &heurdata->taboolist); 2394 SCIPfreeRandom(scip, &heurdata->randnumgen); 2395 2396 heurdata->taboolist = NULL; 2397 heurdata->randnumgen = NULL; 2398 2399 return SCIP_OKAY; 2400 } 2401 2402 /** execution method of primal heuristic */ 2403 static 2404 SCIP_DECL_HEUREXEC(heurExecGins) 2405 { /*lint --e{715}*/ 2406 SCIP_HEURDATA* heurdata; /* heuristic's data */ 2407 SCIP* subscip; /* the subproblem created by gins */ 2408 SCIP_VAR** vars; /* original problem's variables */ 2409 SCIP_VAR** subvars; /* subproblem's variables */ 2410 SCIP_VAR** fixedvars; 2411 SCIP_Real* fixedvals; 2412 ROLLINGHORIZON* rollinghorizon; /* data structure for rolling horizon approach */ 2413 DECOMPHORIZON* decomphorizon; /* data structure for processing multiple blocks of a decomposition */ 2414 SCIP_DECOMP* decomp; 2415 SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */ 2416 2417 int nvars; /* number of original problem's variables */ 2418 int i; 2419 int nfixedvars; 2420 SOLVELIMITS solvelimits; 2421 SCIP_Bool runagain; 2422 2423 SCIP_Bool success; 2424 2425 assert(heur != NULL); 2426 assert(scip != NULL); 2427 assert(result != NULL); 2428 2429 /* get heuristic's data */ 2430 heurdata = SCIPheurGetData(heur); 2431 assert(heurdata != NULL); 2432 2433 *result = SCIP_DELAYED; 2434 2435 /* only call heuristic, if feasible solution is available */ 2436 if( SCIPgetNSols(scip) <= 0 ) 2437 return SCIP_OKAY; 2438 2439 /* in case of many unsuccessful calls, the nextnodenumber is increased to prevent us from running too often */ 2440 if( SCIPgetNNodes(scip) < heurdata->nextnodenumber ) 2441 return SCIP_OKAY; 2442 2443 /* only call heuristic, if the best solution comes from transformed problem */ 2444 assert(SCIPgetBestSol(scip) != NULL); 2445 if( SCIPsolIsOriginal(SCIPgetBestSol(scip)) ) 2446 return SCIP_OKAY; 2447 2448 /* only call heuristic, if enough nodes were processed since last incumbent */ 2449 if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip,SCIPgetBestSol(scip)) < heurdata->nwaitingnodes ) 2450 return SCIP_OKAY; 2451 2452 *result = SCIP_DIDNOTRUN; 2453 2454 /* only call heuristic, if discrete variables are present */ 2455 if( SCIPgetNBinVars(scip) == 0 && SCIPgetNIntVars(scip) == 0 ) 2456 return SCIP_OKAY; 2457 2458 if( SCIPisStopped(scip) ) 2459 return SCIP_OKAY; 2460 2461 runagain = TRUE; 2462 2463 /* determine solving limits for the sub-SCIP for the first time */ 2464 SCIP_CALL( determineLimits(scip, heur, &solvelimits, &runagain) ); 2465 2466 if( ! runagain ) 2467 return SCIP_OKAY; 2468 2469 *result = SCIP_DIDNOTFIND; 2470 2471 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 2472 SCIP_CALL( SCIPallocBufferArray(scip, &fixedvars, nvars) ); 2473 SCIP_CALL( SCIPallocBufferArray(scip, &fixedvals, nvars) ); 2474 2475 rollinghorizon = NULL; 2476 decomp = chooseDecomp(scip); 2477 if( decomp != NULL && heurdata->usedecomp && heurdata->decomphorizon == NULL ) 2478 { 2479 SCIP_CALL( decompHorizonCreate(scip, &heurdata->decomphorizon, decomp) ); 2480 } 2481 decomphorizon = heurdata->decomphorizon; 2482 /* only create a rolling horizon data structure if we need it */ 2483 if( decomphorizon == NULL && heurdata->userollinghorizon ) 2484 { 2485 SCIP_CALL( rollingHorizonCreate(scip, &rollinghorizon) ); 2486 } 2487 2488 do 2489 { 2490 SCIP_SOL* oldincumbent; 2491 SCIP_SOL* newincumbent; 2492 2493 /* create a new problem, by fixing all variables except for a small neighborhood */ 2494 SCIP_CALL( determineVariableFixings(scip, fixedvars, fixedvals, &nfixedvars, heurdata, rollinghorizon, decomphorizon, &success) ); 2495 2496 /* terminate if it was not possible to create the subproblem */ 2497 if( !success ) 2498 { 2499 SCIPdebugMsg(scip, "Could not create the subproblem -> skip call\n"); 2500 2501 /* do not count this as a call to the heuristic */ 2502 *result = SCIP_DIDNOTRUN; 2503 2504 /* count this as a failure and increase the number of waiting nodes until the next call */ 2505 updateFailureStatistic(scip, heurdata); 2506 goto TERMINATE; 2507 } 2508 2509 /* initializing the subproblem */ 2510 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) ); 2511 SCIP_CALL( SCIPcreate(&subscip) ); 2512 ++heurdata->nsubmips; 2513 2514 /* create the variable mapping hash map */ 2515 SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) ); 2516 2517 /* create a problem copy as sub SCIP */ 2518 SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "gins", fixedvars, fixedvals, nfixedvars, 2519 heurdata->uselprows, heurdata->copycuts, &success, NULL) ); 2520 2521 for( i = 0; i < nvars; i++ ) 2522 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]); 2523 2524 /* free hash map */ 2525 SCIPhashmapFree(&varmapfw); 2526 2527 /* set up limits for the subproblem */ 2528 SCIP_CALL( setupSubScip(scip, subscip, &solvelimits, heur) ); 2529 2530 /* solve the subproblem */ 2531 SCIPdebugMsg(scip, "Solve Gins subMIP\n"); 2532 2533 /* Errors in solving the subproblem should not kill the overall solving process 2534 * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. 2535 */ 2536 SCIP_CALL_ABORT( SCIPsolve(subscip) ); 2537 2538 SCIPdebugMsg(scip, "GINS subscip stats: %.2f sec., %" SCIP_LONGINT_FORMAT " nodes, status:%d\n", 2539 SCIPgetSolvingTime(subscip), SCIPgetNTotalNodes(subscip), SCIPgetStatus(subscip)); 2540 2541 /* increase target nodes if a (stall) node limit was reached; this will immediately affect the next run */ 2542 if( SCIPgetStatus(subscip) == SCIP_STATUS_NODELIMIT || SCIPgetStatus(subscip) == SCIP_STATUS_STALLNODELIMIT ) 2543 { 2544 heurdata->targetnodes = (SCIP_Longint)(1.05 * heurdata->targetnodes) + 5L; 2545 2546 /* but not too far */ 2547 heurdata->targetnodes = MIN(heurdata->targetnodes, heurdata->maxnodes / 2); 2548 2549 SCIPdebugMsg(scip, "New target nodes after stalling: %" SCIP_LONGINT_FORMAT "\n", heurdata->targetnodes); 2550 } 2551 2552 /* transfer variable statistics from sub-SCIP */ 2553 SCIP_CALL( SCIPmergeVariableStatistics(subscip, scip, subvars, vars, nvars) ); 2554 2555 heurdata->usednodes += SCIPgetNNodes(subscip); 2556 2557 success = FALSE; 2558 /* check, whether a solution was found; 2559 * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted 2560 */ 2561 oldincumbent = SCIPgetBestSol(scip); 2562 2563 SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, &success, NULL) ); 2564 if( success ) 2565 *result = SCIP_FOUNDSOL; 2566 2567 newincumbent = SCIPgetBestSol(scip); 2568 2569 /* free subproblem */ 2570 SCIPfreeBufferArray(scip, &subvars); 2571 SCIP_CALL( SCIPfree(&subscip) ); 2572 2573 /* check if we want to run another rolling horizon iteration */ 2574 runagain = success && (newincumbent != oldincumbent) && heurdata->userollinghorizon; 2575 if( runagain ) 2576 { 2577 assert(rollinghorizon != NULL || decomphorizon != NULL); 2578 SCIP_CALL( determineLimits(scip, heur, &solvelimits, &runagain ) ); 2579 2580 if( rollinghorizon != NULL ) 2581 runagain = runagain && rollingHorizonRunAgain(scip, rollinghorizon, heurdata) && (success); 2582 else if( decomphorizon != NULL ) 2583 runagain = runagain && decompHorizonRunAgain(scip, decomphorizon); 2584 } 2585 } 2586 while( runagain ); 2587 2588 /* delay the heuristic in case it was not successful */ 2589 if( *result != SCIP_FOUNDSOL ) 2590 updateFailureStatistic(scip, heurdata); 2591 2592 TERMINATE: 2593 2594 /* only free the rolling horizon data structure if we need to keep it */ 2595 if( heurdata->userollinghorizon ) 2596 { 2597 rollingHorizonFree(scip, &rollinghorizon); 2598 } 2599 2600 SCIPfreeBufferArray(scip, &fixedvals); 2601 SCIPfreeBufferArray(scip, &fixedvars); 2602 2603 return SCIP_OKAY; 2604 } 2605 2606 /* 2607 * primal heuristic specific interface methods 2608 */ 2609 2610 /** creates the gins primal heuristic and includes it in SCIP */ 2611 SCIP_RETCODE SCIPincludeHeurGins( 2612 SCIP* scip /**< SCIP data structure */ 2613 ) 2614 { 2615 SCIP_HEURDATA* heurdata; 2616 SCIP_HEUR* heur; 2617 2618 /* create Gins primal heuristic data */ 2619 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 2620 heurdata->randnumgen = NULL; 2621 heurdata->decomphorizon = NULL; 2622 2623 /* include primal heuristic */ 2624 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 2625 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 2626 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecGins, heurdata) ); 2627 2628 assert(heur != NULL); 2629 2630 /* set non-NULL pointers to callback methods */ 2631 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyGins) ); 2632 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeGins) ); 2633 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitGins) ); 2634 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitGins) ); 2635 SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolGins) ); 2636 2637 /* add gins primal heuristic parameters */ 2638 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nodesofs", 2639 "number of nodes added to the contingent of the total nodes", 2640 &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0, INT_MAX, NULL, NULL) ); 2641 2642 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxnodes", 2643 "maximum number of nodes to regard in the subproblem", 2644 &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0, INT_MAX, NULL, NULL) ); 2645 2646 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/minnodes", 2647 "minimum number of nodes required to start the subproblem", 2648 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0, INT_MAX, NULL, NULL) ); 2649 2650 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nwaitingnodes", 2651 "number of nodes without incumbent change that heuristic should wait", 2652 &heurdata->nwaitingnodes, TRUE, DEFAULT_NWAITINGNODES, 0, INT_MAX, NULL, NULL) ); 2653 2654 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot", 2655 "contingent of sub problem nodes in relation to the number of nodes of the original problem", 2656 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) ); 2657 2658 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate", 2659 "percentage of integer variables that have to be fixed", 2660 &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, SCIPsumepsilon(scip), 1.0-SCIPsumepsilon(scip), NULL, NULL) ); 2661 2662 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove", 2663 "factor by which " HEUR_NAME " should at least improve the incumbent", 2664 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) ); 2665 2666 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows", 2667 "should subproblem be created out of the rows in the LP rows?", 2668 &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) ); 2669 2670 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts", 2671 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?", 2672 &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) ); 2673 2674 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/fixcontvars", 2675 "should continuous variables outside the neighborhoods be fixed?", 2676 &heurdata->fixcontvars, TRUE, DEFAULT_FIXCONTVARS, NULL, NULL) ); 2677 2678 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/bestsollimit", 2679 "limit on number of improving incumbent solutions in sub-CIP", 2680 &heurdata->bestsollimit, FALSE, DEFAULT_BESTSOLLIMIT, -1, INT_MAX, NULL, NULL) ); 2681 2682 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxdistance", 2683 "maximum distance to selected variable to enter the subproblem, or -1 to select the distance " 2684 "that best approximates the minimum fixing rate from below", 2685 &heurdata->maxdistance, FALSE, DEFAULT_MAXDISTANCE, -1, INT_MAX, NULL, NULL) ); 2686 2687 SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/potential", 2688 "the reference point to compute the neighborhood potential: (r)oot, (l)ocal lp, or (p)seudo solution", 2689 &heurdata->potential, TRUE, DEFAULT_POTENTIAL, "lpr", NULL, NULL) ); 2690 2691 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/userollinghorizon", 2692 "should the heuristic solve a sequence of sub-MIP's around the first selected variable", 2693 &heurdata->userollinghorizon, TRUE, DEFAULT_USEROLLINGHORIZON, NULL, NULL) ); 2694 2695 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/relaxdenseconss", 2696 "should dense constraints (at least as dense as 1 - minfixingrate) be ignored by connectivity graph?", 2697 &heurdata->relaxdenseconss, TRUE, DEFAULT_RELAXDENSECONSS, NULL, NULL) ); 2698 2699 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/rollhorizonlimfac", 2700 "limiting percentage for variables already used in sub-SCIPs to terminate rolling horizon approach", 2701 &heurdata->rollhorizonlimfac, TRUE, DEFAULT_ROLLHORIZONLIMFAC, 0.0, 1.0, NULL, NULL) ); 2702 2703 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/overlap", 2704 "overlap of blocks between runs - 0.0: no overlap, 1.0: shift by only 1 block", 2705 &heurdata->overlap, TRUE, DEFAULT_OVERLAP, 0.0, 1.0, NULL, NULL) ); 2706 2707 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usedecomp", 2708 "should user decompositions be considered, if available?", 2709 &heurdata->usedecomp, TRUE, DEFAULT_USEDECOMP, NULL, NULL) ); 2710 2711 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usedecomprollhorizon", 2712 "should user decompositions be considered for initial selection in rolling horizon, if available?", 2713 &heurdata->usedecomprollhorizon, TRUE, DEFAULT_USEDECOMPROLLHORIZON, NULL, NULL) ); 2714 2715 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useselfallback", 2716 "should random initial variable selection be used if decomposition was not successful?", 2717 &heurdata->useselfallback, TRUE, DEFAULT_USESELFALLBACK, NULL, NULL) ); 2718 2719 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/consecutiveblocks", 2720 "should blocks be treated consecutively (sorted by ascending label?)", 2721 &heurdata->consecutiveblocks, TRUE, DEFAULT_CONSECUTIVEBLOCKS, NULL, NULL) ); 2722 2723 return SCIP_OKAY; 2724 } 2725