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_vbounds.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood 28 * @author Timo Berthold 29 * @author Stefan Heinz 30 * @author Jens Schulz 31 * @author Gerald Gamrath 32 * 33 * @todo allow smaller fixing rate for probing LP? 34 * @todo allow smaller fixing rate after presolve if total number of variables is small (<= 1000)? 35 * 36 * More details about the heuristic can be found in@n 37 * Structure-Based Primal Heuristics for Mixed Integer Programming@n 38 * Gerald Gamrath, Timo Berthold, Stefan Heinz, and Michael Winkler@n 39 * Optimization in the Real World, Volume 13 of the series Mathematics for Industry, pp 37-53@n 40 * Preliminary version available as <a href="https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/5551">ZIB-Report 15-26</a>. 41 */ 42 43 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 44 45 #include "blockmemshell/memory.h" 46 #include "scip/heur_locks.h" 47 #include "scip/heur_vbounds.h" 48 #include "scip/pub_heur.h" 49 #include "scip/pub_implics.h" 50 #include "scip/pub_message.h" 51 #include "scip/pub_misc.h" 52 #include "scip/pub_tree.h" 53 #include "scip/pub_var.h" 54 #include "scip/scip_branch.h" 55 #include "scip/scip_cons.h" 56 #include "scip/scip_copy.h" 57 #include "scip/scip_general.h" 58 #include "scip/scip_heur.h" 59 #include "scip/scip_lp.h" 60 #include "scip/scip_mem.h" 61 #include "scip/scip_message.h" 62 #include "scip/scip_numerics.h" 63 #include "scip/scip_param.h" 64 #include "scip/scip_prob.h" 65 #include "scip/scip_probing.h" 66 #include "scip/scip_sol.h" 67 #include "scip/scip_solve.h" 68 #include "scip/scip_solvingstats.h" 69 #include "scip/scip_timing.h" 70 #include "scip/scip_tree.h" 71 #include "scip/scip_var.h" 72 #include <string.h> 73 74 #ifdef SCIP_STATISTIC 75 #include "scip/clock.h" 76 #endif 77 78 #define VBOUNDVARIANT_NOOBJ 0x001u 79 #define VBOUNDVARIANT_BESTBOUND 0x002u 80 #define VBOUNDVARIANT_WORSTBOUND 0x004u 81 82 #define HEUR_NAME "vbounds" 83 #define HEUR_DESC "LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood" 84 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_PROP 85 #define HEUR_PRIORITY 2500 86 #define HEUR_FREQ 0 87 #define HEUR_FREQOFS 0 88 #define HEUR_MAXDEPTH -1 89 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE 90 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */ 91 92 #define DEFAULT_MAXNODES 5000LL /**< maximum number of nodes to regard in the subproblem */ 93 #define DEFAULT_MININTFIXINGRATE 0.65 /**< minimum percentage of integer variables that have to be fixed */ 94 #define DEFAULT_MINMIPFIXINGRATE 0.65 /**< minimuskipobjm percentage of variables that have to be fixed within sub-SCIP 95 * (integer and continuous) */ 96 #define DEFAULT_MINIMPROVE 0.01 /**< factor by which vbounds heuristic should at least improve the 97 * incumbent */ 98 #define DEFAULT_MINNODES 500LL /**< minimum number of nodes to regard in the subproblem */ 99 #define DEFAULT_NODESOFS 500LL /**< number of nodes added to the contingent of the total nodes */ 100 #define DEFAULT_NODESQUOT 0.1 /**< subproblem nodes in relation to nodes of the original problem */ 101 #define DEFAULT_MAXPROPROUNDS 2 /**< maximum number of propagation rounds during probing */ 102 #define DEFAULT_MAXBACKTRACKS 10 /**< maximum number of backtracks during the fixing process */ 103 #define DEFAULT_COPYCUTS TRUE /**< should all active cuts from the cutpool of the original scip be copied to 104 * constraints of the subscip? */ 105 #define DEFAULT_USELOCKFIXINGS FALSE /**< should more variables be fixed based on variable locks if 106 * the fixing rate was not reached? 107 */ 108 109 /** which variants of the vbounds heuristic that try to stay feasible should be called? */ 110 #define DEFAULT_FEASVARIANT (VBOUNDVARIANT_BESTBOUND | VBOUNDVARIANT_WORSTBOUND) 111 112 /** which tightening variants of the vbounds heuristic should be called? */ 113 #define DEFAULT_TIGHTENVARIANT (VBOUNDVARIANT_NOOBJ | VBOUNDVARIANT_BESTBOUND | VBOUNDVARIANT_WORSTBOUND) 114 115 116 /* 117 * Data structures 118 */ 119 120 /** primal heuristic data */ 121 struct SCIP_HeurData 122 { 123 SCIP_VAR** vbvars; /**< topological sorted variables with respect to the variable bounds */ 124 SCIP_BOUNDTYPE* vbbounds; /**< topological sorted variables with respect to the variable bounds */ 125 int nvbvars; /**< number of variables in variable lower bound array */ 126 SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */ 127 SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */ 128 SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */ 129 SCIP_Longint usednodes; /**< nodes already used by vbounds heuristic in earlier calls */ 130 SCIP_Real minintfixingrate; /**< minimum percentage of integer variables that have to be fixed */ 131 SCIP_Real minmipfixingrate; /**< minimum percentage of variables that have to be fixed within sub-SCIP 132 * (integer and continuous) */ 133 SCIP_Real minimprove; /**< factor by which vbounds heuristic should at least improve the incumbent */ 134 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */ 135 SCIP_Real cutoffbound; 136 int maxproprounds; /**< maximum number of propagation rounds during probing */ 137 int maxbacktracks; /**< maximum number of backtracks during the fixing process */ 138 int feasvariant; /**< which variants of the vbounds heuristic that try to stay feasible 139 * should be called? */ 140 int tightenvariant; /**< which tightening variants of the vbounds heuristic should be called? */ 141 SCIP_Bool initialized; /**< is the candidate list initialized? */ 142 SCIP_Bool applicable; /**< is the heuristic applicable? */ 143 SCIP_Bool copycuts; /**< should all active cuts from cutpool be copied to constraints in 144 * subproblem? */ 145 SCIP_Bool uselockfixings; /**< should more variables be fixed based on variable locks if 146 * the fixing rate was not reached? */ 147 }; 148 149 /**@name Heuristic defines 150 * 151 * @{ 152 * 153 * The heuristic works on indices representing a bound of a variable. This index will be called bound index in the 154 * following. For a given active variable with problem index i (note that active variables have problem indices 155 * between 0 and nactivevariable - 1), the bound index of its lower bound is 2*i, the bound index of its upper 156 * bound is 2*i + 1. The other way around, a given bound index i corresponds to the variable with problem index 157 * i/2 (rounded down), and to the lower bound, if i is even, to the upper bound if i is odd. 158 * The following macros can be used to convert bound index into variable problem index and boundtype and vice versa. 159 */ 160 #define getLbIndex(idx) (2*(idx)) 161 #define getUbIndex(idx) (2*(idx)+1) 162 #define getVarIndex(idx) ((idx)/2) 163 #define getBoundtype(idx) (((idx) % 2 == 0) ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER) 164 #define isIndexLowerbound(idx) ((idx) % 2 == 0) 165 #define getOtherBoundIndex(idx) (((idx) % 2 == 0) ? (idx) + 1 : (idx) - 1) 166 167 168 /* 169 * Local methods 170 */ 171 172 /** reset heuristic data structure */ 173 static 174 void heurdataReset( 175 SCIP_HEURDATA* heurdata /**< structure containing heurdata */ 176 ) 177 { 178 heurdata->vbvars = NULL; 179 heurdata->vbbounds = NULL; 180 heurdata->nvbvars = 0; 181 heurdata->initialized = FALSE; 182 heurdata->applicable = FALSE; 183 } 184 185 186 /** performs depth-first-search in the implicitly given directed graph from the given start index */ 187 static 188 SCIP_RETCODE dfs( 189 SCIP* scip, /**< SCIP data structure */ 190 int startnode, /**< node to start the depth-first-search */ 191 SCIP_Shortbool* visited, /**< array to store for each node, whether it was already visited */ 192 int* dfsstack, /**< array of size number of nodes to store the stack; 193 * only needed for performance reasons */ 194 int* stacknextedge, /**< array of size number of nodes to store the number of adjacent nodes 195 * already visited for each node on the stack; only needed for 196 * performance reasons */ 197 int* stacknextcliquevar, /**< array of size number of nodes to store the number of variables 198 * already evaluated for the clique currently being evaluated */ 199 int* cliqueexit, /**< exit node when entering a clique */ 200 int* dfsnodes, /**< array of nodes that can be reached starting at startnode, in reverse 201 * dfs order */ 202 int* ndfsnodes /**< pointer to store number of nodes that can be reached starting at 203 * startnode */ 204 ) 205 { 206 SCIP_VAR** vars; 207 SCIP_VAR* startvar; 208 SCIP_VAR** vbvars; 209 SCIP_Real* coefs; 210 SCIP_Bool lower; 211 SCIP_Bool found; 212 int maxstacksize; 213 int stacksize; 214 int curridx; 215 int idx; 216 int nvbvars; 217 int i; 218 219 assert(startnode >= 0); 220 assert(startnode < 2 * SCIPgetNVars(scip)); 221 assert(visited != NULL); 222 assert(visited[startnode] == FALSE); 223 assert(dfsstack != NULL); 224 assert(dfsnodes != NULL); 225 assert(ndfsnodes != NULL); 226 227 vars = SCIPgetVars(scip); 228 229 /* put start node on the stack */ 230 dfsstack[0] = startnode; 231 stacknextcliquevar[0] = 0; 232 stacknextedge[0] = 0; 233 maxstacksize = 1; 234 stacksize = 1; 235 idx = -1; 236 237 /* we run until no more bounds indices are on the stack */ 238 while( stacksize > 0 ) 239 { 240 /* get next node from stack */ 241 curridx = dfsstack[stacksize - 1]; 242 243 /* mark current node as visited */ 244 assert(visited[curridx] == (stacknextedge[stacksize - 1] != 0)); 245 visited[curridx] = TRUE; 246 found = FALSE; 247 248 startvar = vars[getVarIndex(curridx)]; 249 lower = isIndexLowerbound(curridx); 250 251 if( stacknextedge[stacksize - 1] >= 0 ) 252 { 253 /* go over edges corresponding to varbounds */ 254 if( lower ) 255 { 256 vbvars = SCIPvarGetVlbVars(startvar); 257 coefs = SCIPvarGetVlbCoefs(startvar); 258 nvbvars = SCIPvarGetNVlbs(startvar); 259 } 260 else 261 { 262 vbvars = SCIPvarGetVubVars(startvar); 263 coefs = SCIPvarGetVubCoefs(startvar); 264 nvbvars = SCIPvarGetNVubs(startvar); 265 } 266 267 /* iterate over all vbounds for the given bound */ 268 for( i = stacknextedge[stacksize - 1]; i < nvbvars; ++i ) 269 { 270 if( !SCIPvarIsActive(vbvars[i]) ) 271 continue; 272 273 idx = (SCIPisPositive(scip, coefs[i]) == lower) ? getLbIndex(SCIPvarGetProbindex(vbvars[i])) : getUbIndex(SCIPvarGetProbindex(vbvars[i])); 274 assert(idx >= 0); 275 276 /* break when the first unvisited node is reached */ 277 if( !visited[idx] ) 278 break; 279 } 280 281 /* we stopped because we found an unhandled node and not because we reached the end of the list */ 282 if( i < nvbvars ) 283 { 284 assert(!visited[idx]); 285 286 /* put the adjacent node onto the stack */ 287 dfsstack[stacksize] = idx; 288 stacknextedge[stacksize] = 0; 289 stacknextcliquevar[stacksize] = 0; 290 stacknextedge[stacksize - 1] = i + 1; 291 stacksize++; 292 assert(stacksize <= 2* SCIPgetNVars(scip)); 293 294 /* restart while loop, get next index from stack */ 295 continue; 296 } 297 } 298 299 stacknextedge[stacksize - 1] = -1; 300 301 /* treat cliques */ 302 if( SCIPvarIsBinary(startvar) ) 303 { 304 SCIP_CLIQUE** cliques = SCIPvarGetCliques(startvar, !lower); 305 int ncliques = SCIPvarGetNCliques(startvar, !lower); 306 int j; 307 308 /* iterate over all not yet handled cliques and search for an unvisited node */ 309 for( j = -stacknextedge[stacksize - 1] - 1; j < ncliques; ++j ) 310 { 311 SCIP_VAR** cliquevars; 312 SCIP_Bool* cliquevals; 313 int ncliquevars; 314 315 /* the first time we evaluate this clique for the current node */ 316 if( stacknextcliquevar[stacksize - 1] == 0 ) 317 { 318 if( cliqueexit[SCIPcliqueGetIndex(cliques[j])] > 0 ) 319 { 320 if( !visited[cliqueexit[SCIPcliqueGetIndex(cliques[j])] - 1] && 321 cliqueexit[SCIPcliqueGetIndex(cliques[j])] - 1 != curridx ) 322 { 323 stacknextedge[stacksize - 1] = -j - 2; 324 stacknextcliquevar[stacksize - 1] = 0; 325 idx = cliqueexit[SCIPcliqueGetIndex(cliques[j])] - 1; 326 cliqueexit[SCIPcliqueGetIndex(cliques[j])] = -1; 327 found = TRUE; 328 } 329 else 330 continue; 331 } 332 else if( cliqueexit[SCIPcliqueGetIndex(cliques[j])] == 0 ) 333 { 334 cliqueexit[SCIPcliqueGetIndex(cliques[j])] = getOtherBoundIndex(curridx) + 1; 335 } 336 else 337 continue; 338 } 339 if( !found ) 340 { 341 cliquevars = SCIPcliqueGetVars(cliques[j]); 342 cliquevals = SCIPcliqueGetValues(cliques[j]); 343 ncliquevars = SCIPcliqueGetNVars(cliques[j]); 344 345 for( i = 0; i < ncliquevars; ++i ) 346 { 347 assert(SCIPvarIsActive(cliquevars[i])); 348 349 if( cliquevars[i] == startvar ) 350 continue; 351 352 if( cliquevals[i] ) 353 idx = getLbIndex(SCIPvarGetProbindex(cliquevars[i])); 354 else 355 idx = getUbIndex(SCIPvarGetProbindex(cliquevars[i])); 356 357 assert(idx >= 0 && idx < 2 * SCIPgetNVars(scip)); 358 359 /* break when the first unvisited node is reached */ 360 if( idx >= 0 && !visited[idx] ) 361 { 362 if( i < ncliquevars - 1 ) 363 { 364 stacknextedge[stacksize - 1] = -j - 1; 365 stacknextcliquevar[stacksize - 1] = i + 1; 366 } 367 else 368 { 369 stacknextedge[stacksize - 1] = -j - 2; 370 stacknextcliquevar[stacksize - 1] = 0; 371 } 372 found = TRUE; 373 break; 374 } 375 } 376 } 377 if( found ) 378 { 379 assert(!visited[idx]); 380 381 /* put the adjacent node onto the stack */ 382 dfsstack[stacksize] = idx; 383 stacknextedge[stacksize] = 0; 384 stacknextcliquevar[stacksize] = 0; 385 stacksize++; 386 assert(stacksize <= 2* SCIPgetNVars(scip)); 387 388 break; 389 } 390 } 391 /* restart while loop, get next index from stack */ 392 if( found ) 393 continue; 394 } 395 396 maxstacksize = MAX(maxstacksize, stacksize); 397 398 /* the current node was completely handled, remove it from the stack */ 399 stacksize--; 400 401 if( (maxstacksize > 1) && SCIPvarGetType(startvar) != SCIP_VARTYPE_CONTINUOUS ) 402 { 403 /* store node in the sorted nodes array */ 404 dfsnodes[(*ndfsnodes)] = curridx; 405 (*ndfsnodes)++; 406 } 407 else 408 visited[curridx] = FALSE; 409 } 410 411 return SCIP_OKAY; 412 } 413 414 415 /** sort the bounds of variables topologically */ 416 static 417 SCIP_RETCODE topologicalSort( 418 SCIP* scip, /**< SCIP data structure */ 419 int* vbvars, /**< array to store variable bounds in topological order */ 420 int* nvbvars /**< pointer to store number of variable bounds in the graph */ 421 ) 422 { 423 int* dfsstack; 424 int* stacknextedge; 425 int* stacknextcliquevar; 426 int* cliqueexit; 427 SCIP_Shortbool* visited; 428 int nbounds; 429 int i; 430 431 assert(scip != NULL); 432 433 nbounds = 2 * SCIPgetNVars(scip); 434 435 SCIP_CALL( SCIPallocBufferArray(scip, &dfsstack, nbounds) ); 436 SCIP_CALL( SCIPallocBufferArray(scip, &stacknextedge, nbounds) ); 437 SCIP_CALL( SCIPallocBufferArray(scip, &stacknextcliquevar, nbounds) ); 438 SCIP_CALL( SCIPallocClearBufferArray(scip, &cliqueexit, SCIPgetNCliques(scip)) ); 439 SCIP_CALL( SCIPallocClearBufferArray(scip, &visited, nbounds) ); 440 441 /* while there are unvisited nodes, run dfs on the inverse graph starting from one of these nodes; the dfs orders are 442 * stored in the topoorder array, later dfs calls are just appended after the stacks of previous dfs calls, which 443 * gives us a topological order 444 */ 445 for( i = 0; i < nbounds; ++i ) 446 { 447 if( !visited[i] ) 448 { 449 SCIP_CALL( dfs(scip, i, visited, dfsstack, stacknextedge, stacknextcliquevar, cliqueexit, vbvars, nvbvars) ); 450 } 451 } 452 assert(*nvbvars <= nbounds); 453 454 SCIPfreeBufferArray(scip, &visited); 455 SCIPfreeBufferArray(scip, &cliqueexit); 456 SCIPfreeBufferArray(scip, &stacknextcliquevar); 457 SCIPfreeBufferArray(scip, &stacknextedge); 458 SCIPfreeBufferArray(scip, &dfsstack); 459 460 return SCIP_OKAY; 461 } 462 463 /** initialize candidate lists */ 464 static 465 SCIP_RETCODE initializeCandsLists( 466 SCIP* scip, /**< original SCIP data structure */ 467 SCIP_HEURDATA* heurdata /**< structure containing heurdata */ 468 ) 469 { 470 SCIP_VAR** vars; 471 int* vbs; 472 int nvars; 473 int nvbs; 474 int v; 475 476 SCIPdebugMsg(scip, "initialize variable bound heuristic (%s)\n", SCIPgetProbName(scip)); 477 478 vars = SCIPgetVars(scip); 479 nvars = SCIPgetNIntVars(scip) + SCIPgetNBinVars(scip) + SCIPgetNImplVars(scip); 480 nvbs = 0; 481 482 /* initialize data */ 483 heurdata->usednodes = 0; 484 heurdata->initialized = TRUE; 485 486 if( nvars == 0 ) 487 return SCIP_OKAY; 488 489 /* allocate memory for the arrays of the heurdata */ 490 SCIP_CALL( SCIPallocBufferArray(scip, &vbs, 2 * nvars) ); 491 492 /* create the topological sorted variable array with respect to the variable bounds */ 493 SCIP_CALL( topologicalSort(scip, vbs, &nvbs) ); 494 495 /* check if the candidate list contains enough candidates */ 496 if( nvbs > 0 && nvbs >= 0.1 * heurdata->minintfixingrate * nvars ) 497 { 498 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->vbvars, nvbs) ); 499 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->vbbounds, nvbs) ); 500 501 /* capture variable candidate list */ 502 for( v = 0; v < nvbs; ++v ) 503 { 504 heurdata->vbvars[v] = vars[getVarIndex(vbs[v])]; 505 heurdata->vbbounds[v] = getBoundtype(vbs[v]); 506 assert(SCIPvarIsIntegral(heurdata->vbvars[v])); 507 508 SCIP_CALL( SCIPcaptureVar(scip, heurdata->vbvars[v]) ); 509 } 510 511 heurdata->nvbvars = nvbs; 512 heurdata->applicable = TRUE; 513 } 514 515 /* free buffer arrays */ 516 SCIPfreeBufferArray(scip, &vbs); 517 518 SCIPstatisticMessage("vbvars %.3g (%s)\n", 519 (nvbs * 100.0) / nvars, SCIPgetProbName(scip)); 520 521 /* if there is already a solution, add an objective cutoff */ 522 if( SCIPgetNSols(scip) > 0 ) 523 { 524 SCIP_Real upperbound; 525 SCIP_Real minimprove; 526 SCIP_Real cutoffbound; 527 528 minimprove = heurdata->minimprove; 529 assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) ); 530 531 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip); 532 533 if( !SCIPisInfinity(scip, -1.0 * SCIPgetLowerbound(scip)) ) 534 { 535 cutoffbound = (1-minimprove) * SCIPgetUpperbound(scip) + minimprove * SCIPgetLowerbound(scip); 536 } 537 else 538 { 539 if( SCIPgetUpperbound ( scip ) >= 0 ) 540 cutoffbound = (1 - minimprove) * SCIPgetUpperbound(scip); 541 else 542 cutoffbound = (1 + minimprove) * SCIPgetUpperbound(scip); 543 } 544 heurdata->cutoffbound = MIN(upperbound, cutoffbound); 545 } 546 else 547 heurdata->cutoffbound = SCIPinfinity(scip); 548 return SCIP_OKAY; 549 } 550 551 /** apply variable bound fixing during probing */ 552 static 553 SCIP_RETCODE applyVboundsFixings( 554 SCIP* scip, /**< original SCIP data structure */ 555 SCIP_HEURDATA* heurdata, /**< structure containing heurdata */ 556 SCIP_VAR** vars, /**< variables to fix during probing */ 557 int nvbvars, /**< number of variables in the variable bound graph */ 558 SCIP_Bool tighten, /**< should variables be fixed to cause other fixings? */ 559 int obj, /**< should the objective be taken into account? */ 560 SCIP_Bool* allobj1, /**< pointer to store whether all variables were fixed according to obj=1 scheme */ 561 SCIP_Bool* allobj2, /**< pointer to store whether all variables were fixed according to obj=2 scheme */ 562 SCIP_Bool* backtracked, /**< was backtracking performed at least once? */ 563 SCIP_Bool* infeasible /**< pointer to store whether propagation detected infeasibility */ 564 ) 565 { 566 SCIP_VAR* lastvar; 567 SCIP_VAR* var; 568 SCIP_Real lastfixval; 569 SCIP_Bool lastfixedlb; 570 SCIP_Bool fixtolower; 571 SCIP_BOUNDTYPE bound; 572 int nbacktracks = 0; 573 int v; 574 575 /* loop over variables in topological order */ 576 for( v = 0; v < nvbvars && !(*infeasible); ++v ) 577 { 578 var = vars[v]; 579 bound = heurdata->vbbounds[v]; 580 581 /*SCIPdebugMsg(scip, "topoorder[%d]: %s(%s) (%s) [%g,%g] (obj=%g)\n", v, 582 bound == SCIP_BOUNDTYPE_UPPER ? "ub" : "lb", SCIPvarGetName(var), 583 SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS ? "c" : "d", 584 SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPvarGetObj(var));*/ 585 586 /* only check integer or binary variables */ 587 if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS ) 588 continue; 589 590 /* skip variables which are already fixed */ 591 if( SCIPvarGetLbLocal(var) + 0.5 > SCIPvarGetUbLocal(var) ) 592 continue; 593 594 /* there are two cases for tighten: 595 * 1) tighten == TRUE: we go through the list of variables and fix variables to force propagation; 596 * this is be obtained by fixing the variable to the other bound (which means 597 * that the current bound is changed and so, much propagation is triggered 598 * since we are starting with the bounds which are most influential). 599 * 2) tighten == FALSE: we fix variables to avoid too much propagation in order to avoid reaching 600 * infeasibility. Therefore, we fix the variable to the current bound, so that 601 * this bound is not changed and does not propagate. The other bound is changed 602 * and propagates, but is later in the order, so less influential. 603 */ 604 fixtolower = (tighten == (bound == SCIP_BOUNDTYPE_UPPER)); 605 606 /* if we want to take into account the objective function coefficients, we only perform a fixing if the variable 607 * would be fixed to its best bound; otherwise, we just continue 608 */ 609 if( ((SCIPvarGetObj(var) >= 0) != fixtolower) ) 610 { 611 if( obj == 1 ) 612 continue; 613 else 614 *allobj1 = FALSE; 615 } 616 /* if we want to take into account the objective function coefficients but reverted, we only perform a fixing if the variable 617 * would be fixed to its worst bound; otherwise, we just continue 618 */ 619 if( ((SCIPvarGetObj(var) >= 0) == fixtolower) ) 620 { 621 if( obj == 2 ) 622 continue; 623 else 624 *allobj2 = FALSE; 625 } 626 lastvar = var; 627 628 /* fix the variable to its bound */ 629 if( fixtolower ) 630 { 631 /* we cannot fix to infinite bounds */ 632 if( SCIPisInfinity(scip, -SCIPvarGetLbLocal(var)) ) 633 continue; 634 635 /* only open a new probing node if we will not exceed the maximal tree depth */ 636 if( SCIP_MAXTREEDEPTH > SCIPgetDepth(scip) ) 637 { 638 SCIP_CALL( SCIPnewProbingNode(scip) ); 639 } 640 641 /* fix variable to lower bound */ 642 SCIP_CALL( SCIPfixVarProbing(scip, var, SCIPvarGetLbLocal(var)) ); 643 SCIPdebugMsg(scip, "fixing %d: variable <%s> (obj=%g) to lower bound <%g> (%d pseudo cands)\n", 644 v, SCIPvarGetName(var), SCIPvarGetObj(var), SCIPvarGetLbLocal(var), SCIPgetNPseudoBranchCands(scip)); 645 lastfixedlb = TRUE; 646 lastfixval = SCIPvarGetLbLocal(var); 647 } 648 else 649 { 650 /* we cannot fix to infinite bounds */ 651 if( SCIPisInfinity(scip, SCIPvarGetUbLocal(var)) ) 652 continue; 653 654 /* only open a new probing node if we will not exceed the maximal tree depth */ 655 if( SCIP_MAXTREEDEPTH > SCIPgetDepth(scip) ) 656 { 657 SCIP_CALL( SCIPnewProbingNode(scip) ); 658 } 659 660 /* fix variable to upper bound */ 661 SCIP_CALL( SCIPfixVarProbing(scip, var, SCIPvarGetUbLocal(var)) ); 662 SCIPdebugMsg(scip, "fixing %d: variable <%s> (obj=%g) to upper bound <%g> (%d pseudo cands)\n", 663 v, SCIPvarGetName(var), SCIPvarGetObj(var), SCIPvarGetUbLocal(var), SCIPgetNPseudoBranchCands(scip)); 664 lastfixedlb = FALSE; 665 lastfixval = SCIPvarGetUbLocal(var); 666 } 667 668 /* check if problem is already infeasible */ 669 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, infeasible, NULL) ); 670 671 /* probing detected infeasibility: backtrack */ 672 if( *infeasible ) 673 { 674 assert(lastvar != NULL); 675 676 SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip) - 1) ); 677 ++nbacktracks; 678 *infeasible = FALSE; 679 680 /* increase the lower bound of the variable which caused the infeasibility */ 681 if( lastfixedlb && lastfixval + 0.5 < SCIPvarGetUbLocal(lastvar) ) 682 { 683 if( lastfixval + 0.5 > SCIPvarGetLbLocal(lastvar) ) 684 { 685 SCIP_CALL( SCIPchgVarLbProbing(scip, lastvar, lastfixval + 1.0) ); 686 } 687 } 688 else if( !lastfixedlb && lastfixval - 0.5 > SCIPvarGetLbLocal(lastvar) ) 689 { 690 if( lastfixval - 0.5 < SCIPvarGetUbLocal(lastvar) ) 691 { 692 SCIP_CALL( SCIPchgVarUbProbing(scip, lastvar, lastfixval - 1.0) ); 693 } 694 } 695 /* because of the limited number of propagation rounds, it may happen that conflict analysis finds a valid 696 * global bound for the last fixed variable that conflicts with applying the reverse bound change after backtracking; 697 * in that case, we ran into a deadend and stop 698 */ 699 else 700 { 701 *infeasible = TRUE; 702 } 703 lastvar = NULL; 704 705 if( !(*infeasible) ) 706 { 707 /* propagate fixings */ 708 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, infeasible, NULL) ); 709 710 SCIPdebugMessage("backtrack %d was %sfeasible\n", nbacktracks, (*infeasible ? "in" : "")); 711 } 712 713 if( *infeasible ) 714 { 715 SCIPdebugMsg(scip, "probing was infeasible after %d backtracks\n", nbacktracks); 716 717 break; 718 } 719 else if( nbacktracks > heurdata->maxbacktracks ) 720 { 721 SCIPdebugMsg(scip, "interrupt probing after %d backtracks\n", nbacktracks); 722 break; 723 } 724 } 725 } 726 727 *backtracked = (nbacktracks > 0); 728 729 return SCIP_OKAY; 730 } 731 732 /** copy problem to sub-SCIP, solve it, and add solutions */ 733 static 734 SCIP_RETCODE setupAndSolveSubscip( 735 SCIP* scip, /**< original SCIP data structure */ 736 SCIP* subscip, /**< SCIP structure of the subproblem */ 737 SCIP_HEUR* heur, /**< heuristic */ 738 SCIP_VAR** vars, /**< variables of the main SCIP */ 739 int nvars, /**< number of variables of the main SCIP */ 740 SCIP_Longint nstallnodes, /**< stalling node limit for the sub-SCIP */ 741 SCIP_Real lowerbound, /**< lower bound of the main SCIP / current subproblem */ 742 int* nprevars, /**< pointer to store the number of presolved variables */ 743 SCIP_Bool* wasfeas, /**< pointer to store if a feasible solution was found */ 744 SCIP_RESULT* result /**< pointer to store the result */ 745 ) 746 { 747 SCIP_HEURDATA* heurdata; 748 SCIP_VAR** subvars; 749 SCIP_HASHMAP* varmap; 750 int i; 751 752 assert(scip != NULL); 753 assert(subscip != NULL); 754 assert(heur != NULL); 755 756 heurdata = SCIPheurGetData(heur); 757 assert(heurdata != NULL); 758 759 /* create the variable mapping hash map */ 760 SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(subscip), nvars) ); 761 762 SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmap, NULL, "_vbounds", NULL, NULL, 0, FALSE, FALSE, FALSE, 763 TRUE, NULL) ); 764 765 if( heurdata->copycuts ) 766 { 767 /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */ 768 SCIP_CALL( SCIPcopyCuts(scip, subscip, varmap, NULL, FALSE, NULL) ); 769 } 770 771 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) ); 772 773 for( i = 0; i < nvars; i++ ) 774 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[i]); 775 776 /* free hash map */ 777 SCIPhashmapFree(&varmap); 778 779 /* do not abort subproblem on CTRL-C */ 780 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) ); 781 782 #ifdef SCIP_DEBUG 783 /* for debugging, enable full output */ 784 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) ); 785 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) ); 786 #else 787 /* disable statistic timing inside sub SCIP and output to console */ 788 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) ); 789 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) ); 790 #endif 791 792 /* set limits for the subproblem */ 793 SCIP_CALL( SCIPcopyLimits(scip, subscip) ); 794 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) ); 795 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", heurdata->maxnodes) ); 796 797 /* speed up sub-SCIP by not checking dual LP feasibility */ 798 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) ); 799 800 /* forbid call of heuristics and separators solving sub-CIPs */ 801 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) ); 802 803 /* disable cutting plane separation */ 804 SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) ); 805 806 /* disable expensive presolving */ 807 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) ); 808 809 /* use inference branching */ 810 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") ) 811 { 812 SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) ); 813 } 814 815 /* set a cutoff bound */ 816 if( SCIPgetNSols(scip) > 0 ) 817 { 818 SCIP_Real upperbound; 819 SCIP_Real minimprove; 820 SCIP_Real cutoffbound; 821 822 minimprove = heurdata->minimprove; 823 assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) ); 824 825 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip); 826 827 if( !SCIPisInfinity(scip, -1.0 * lowerbound) ) 828 { 829 cutoffbound = (1-minimprove) * SCIPgetUpperbound(scip) + minimprove * lowerbound; 830 } 831 else 832 { 833 if( SCIPgetUpperbound ( scip ) >= 0 ) 834 cutoffbound = (1 - minimprove) * SCIPgetUpperbound(scip); 835 else 836 cutoffbound = (1 + minimprove) * SCIPgetUpperbound(scip); 837 } 838 heurdata->cutoffbound = MIN(upperbound, cutoffbound); 839 } 840 841 if( !SCIPisInfinity(scip, heurdata->cutoffbound) ) 842 { 843 SCIP_CALL( SCIPsetObjlimit(subscip, heurdata->cutoffbound) ); 844 SCIPdebugMsg(scip, "setting objlimit for subscip to %g\n", heurdata->cutoffbound); 845 } 846 847 SCIPdebugMsg(scip, "starting solving vbound-submip at time %g\n", SCIPgetSolvingTime(scip)); 848 849 /* solve the subproblem */ 850 /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic. 851 * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. 852 */ 853 SCIP_CALL_ABORT( SCIPpresolve(subscip) ); 854 855 SCIPdebugMsg(scip, "vbounds heuristic presolved subproblem at time %g : %d vars, %d cons; fixing value = %g\n", 856 SCIPgetSolvingTime(scip), SCIPgetNVars(subscip), SCIPgetNConss(subscip), 857 ((nvars - SCIPgetNVars(subscip)) / (SCIP_Real)nvars)); 858 859 *nprevars = SCIPgetNVars(subscip); 860 861 /* after presolving, we should have at least reached a certain fixing rate over ALL variables (including continuous) 862 * to ensure that not only the MIP but also the LP relaxation is easy enough 863 */ 864 if( ((nvars - SCIPgetNVars(subscip)) / (SCIP_Real)nvars) >= heurdata->minmipfixingrate ) 865 { 866 SCIPdebugMsg(scip, "solving subproblem: nstallnodes=%" SCIP_LONGINT_FORMAT ", maxnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->maxnodes); 867 868 SCIP_CALL_ABORT( SCIPsolve(subscip) ); 869 870 SCIPdebugMsg(scip, "ending solving vbounds-submip at time %g, status = %d\n", SCIPgetSolvingTime(scip), SCIPgetStatus(subscip)); 871 872 /* check, whether a solution was found; due to numerics, it might happen that not all solutions are feasible -> 873 * try all solutions until one was accepted 874 */ 875 SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, wasfeas, NULL) ); 876 if( (*wasfeas) ) 877 { 878 SCIPdebugMsg(scip, "found feasible solution in sub-MIP\n"); 879 *result = SCIP_FOUNDSOL; 880 } 881 } 882 883 #ifdef SCIP_DEBUG 884 SCIP_CALL( SCIPprintStatistics(subscip, NULL) ); 885 #endif 886 887 /* free subproblem */ 888 SCIPfreeBufferArray(scip, &subvars); 889 890 return SCIP_OKAY; 891 } 892 893 /** main procedure of the vbounds heuristic */ 894 static 895 SCIP_RETCODE applyVbounds( 896 SCIP* scip, /**< original SCIP data structure */ 897 SCIP_HEUR* heur, /**< heuristic */ 898 SCIP_HEURDATA* heurdata, /**< heuristic data structure */ 899 SCIP_VAR** vbvars, /**< variables to fix during probing */ 900 int nvbvars, /**< number of variables to fix */ 901 SCIP_Bool tighten, /**< should variables be fixed to cause other fixings? */ 902 int obj, /**< should the objective be taken into account? */ 903 SCIP_Bool* skipobj1, /**< pointer to store whether the run with obj=1 can be skipped, or NULL */ 904 SCIP_Bool* skipobj2, /**< pointer to store whether the run with obj=2 can be skipped, or NULL */ 905 SCIP_RESULT* result /**< pointer to store the result */ 906 ) 907 { 908 SCIPstatistic( SCIP_CLOCK* clock; ) 909 SCIP_VAR** vars; 910 SCIP_Longint nstallnodes; 911 SCIP_LPSOLSTAT lpstatus; 912 SCIP_Real lowerbound; 913 SCIP_Bool wasfeas = FALSE; 914 SCIP_Bool cutoff; 915 SCIP_Bool lperror; 916 SCIP_Bool solvelp; 917 SCIP_Bool allobj1 = TRUE; 918 SCIP_Bool allobj2 = TRUE; 919 SCIP_Bool backtracked = TRUE; 920 int oldnpscands; 921 int npscands; 922 int nvars; 923 int nprevars; 924 925 assert(heur != NULL); 926 assert(heurdata != NULL); 927 assert(nvbvars > 0); 928 929 /* initialize default values */ 930 cutoff = FALSE; 931 932 if( skipobj1 != NULL ) 933 *skipobj1 = FALSE; 934 if( skipobj2 != NULL ) 935 *skipobj2 = FALSE; 936 937 if( nvbvars < SCIPgetNVars(scip) * heurdata->minintfixingrate ) 938 return SCIP_OKAY; 939 940 if( *result == SCIP_DIDNOTRUN ) 941 *result = SCIP_DIDNOTFIND; 942 943 lowerbound = SCIPgetLowerbound(scip); 944 945 oldnpscands = SCIPgetNPseudoBranchCands(scip); 946 947 /* calculate the maximal number of branching nodes until heuristic is aborted */ 948 nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip)); 949 950 /* reward variable bounds heuristic if it succeeded often */ 951 nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0)); 952 nstallnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-MIP as 100 nodes */ 953 nstallnodes += heurdata->nodesofs; 954 955 /* determine the node limit for the current process */ 956 nstallnodes -= heurdata->usednodes; 957 nstallnodes = MIN(nstallnodes, heurdata->maxnodes); 958 959 SCIPdebugMsg(scip, "apply variable bounds heuristic at node %lld on %d variable bounds, tighten: %u obj: %d\n", 960 SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), nvbvars, tighten, obj); 961 962 /* check whether we have enough nodes left to call subproblem solving */ 963 if( nstallnodes < heurdata->minnodes ) 964 { 965 SCIPdebugMsg(scip, "skipping " HEUR_NAME ": nstallnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->minnodes); 966 return SCIP_OKAY; 967 } 968 969 if( SCIPisStopped(scip) ) 970 return SCIP_OKAY; 971 972 SCIPstatistic( SCIP_CALL( SCIPcreateClock(scip, &clock) ) ); 973 SCIPstatistic( SCIP_CALL( SCIPstartClock(scip, clock) ) ); 974 975 /* check whether the LP should be solved at the current node in the tree to determine whether the heuristic 976 * is allowed to solve an LP 977 */ 978 solvelp = SCIPhasCurrentNodeLP(scip); 979 980 if( !SCIPisLPConstructed(scip) && solvelp ) 981 { 982 SCIP_CALL( SCIPconstructLP(scip, &cutoff) ); 983 984 /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */ 985 if( cutoff ) 986 { 987 SCIP_CALL( SCIPcutoffNode(scip, SCIPgetCurrentNode(scip)) ); 988 goto TERMINATE; 989 } 990 991 SCIP_CALL( SCIPflushLP(scip) ); 992 } 993 994 /* get variable data of original problem */ 995 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 996 997 SCIPstatistic( nprevars = nvars; ) 998 999 /* start probing */ 1000 SCIP_CALL( SCIPstartProbing(scip) ); 1001 1002 #ifdef COLLECTSTATISTICS 1003 SCIPenableVarHistory(scip); 1004 #endif 1005 1006 /* apply the variable fixings */ 1007 SCIP_CALL( applyVboundsFixings(scip, heurdata, vbvars, nvbvars, tighten, obj, &allobj1, &allobj2, &backtracked, &cutoff) ); 1008 1009 if( skipobj1 != NULL ) 1010 *skipobj1 = allobj1; 1011 1012 if( skipobj2 != NULL ) 1013 *skipobj2 = allobj2; 1014 1015 if( cutoff || SCIPisStopped(scip) ) 1016 goto TERMINATE; 1017 1018 /* check that we had enough fixings */ 1019 npscands = SCIPgetNPseudoBranchCands(scip); 1020 1021 SCIPdebugMsg(scip, "npscands=%d, oldnpscands=%d, heurdata->minintfixingrate=%g\n", npscands, oldnpscands, heurdata->minintfixingrate); 1022 1023 /* check fixing rate */ 1024 if( npscands > oldnpscands * (1.0 - heurdata->minintfixingrate) ) 1025 { 1026 if( heurdata->uselockfixings && npscands <= 2.0 * oldnpscands * (1.0 - heurdata->minintfixingrate) ) 1027 { 1028 SCIP_Bool allrowsfulfilled = FALSE; 1029 1030 SCIP_CALL( SCIPapplyLockFixings(scip, NULL, &cutoff, &allrowsfulfilled) ); 1031 1032 if( cutoff || SCIPisStopped(scip) ) 1033 { 1034 SCIPdebugMsg(scip, "cutoff or timeout in locks fixing\n"); 1035 goto TERMINATE; 1036 } 1037 1038 npscands = SCIPgetNPseudoBranchCands(scip); 1039 1040 SCIPdebugMsg(scip, "after lockfixings: npscands=%d, oldnpscands=%d, allrowsfulfilled=%u, heurdata->minintfixingrate=%g\n", 1041 npscands, oldnpscands, allrowsfulfilled, heurdata->minintfixingrate); 1042 1043 if( !allrowsfulfilled && npscands > oldnpscands * (1 - heurdata->minintfixingrate) ) 1044 { 1045 SCIPdebugMsg(scip, "--> too few fixings\n"); 1046 1047 goto TERMINATE; 1048 } 1049 } 1050 else 1051 { 1052 SCIPdebugMsg(scip, "--> too few fixings\n"); 1053 1054 goto TERMINATE; 1055 } 1056 } 1057 1058 assert(!cutoff); 1059 1060 /*************************** Probing LP Solving ***************************/ 1061 lpstatus = SCIP_LPSOLSTAT_ERROR; 1062 lperror = FALSE; 1063 /* solve lp only if the problem is still feasible */ 1064 if( solvelp ) 1065 { 1066 char strbuf[SCIP_MAXSTRLEN]; 1067 int ncols; 1068 1069 /* print message if relatively large LP is solved from scratch, since this could lead to a longer period during 1070 * which the user sees no output; more detailed probing stats only in debug mode */ 1071 ncols = SCIPgetNLPCols(scip); 1072 if( !SCIPisLPSolBasic(scip) && ncols > 1000 ) 1073 { 1074 int nunfixedcols = SCIPgetNUnfixedLPCols(scip); 1075 1076 if( nunfixedcols > 0.5 * ncols ) 1077 { 1078 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, 1079 "Heuristic " HEUR_NAME " solving LP from scratch with %.1f %% unfixed columns (%d of %d) ...\n", 1080 100.0 * (nunfixedcols / (SCIP_Real)ncols), nunfixedcols, ncols); 1081 } 1082 } 1083 SCIPdebugMsg(scip, "Heuristic " HEUR_NAME " probing LP: %s\n", 1084 SCIPsnprintfProbingStats(scip, strbuf, SCIP_MAXSTRLEN)); 1085 1086 /* solve LP; errors in the LP solver should not kill the overall solving process, if the LP is just needed for a 1087 * heuristic. hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, 1088 * SCIP will stop. 1089 */ 1090 SCIPdebugMsg(scip, "starting solving vbound-lp at time %g\n", SCIPgetSolvingTime(scip)); 1091 #ifdef NDEBUG 1092 { 1093 SCIP_Bool retstat; 1094 retstat = SCIPsolveProbingLP(scip, -1, &lperror, NULL); 1095 if( retstat != SCIP_OKAY ) 1096 { 1097 SCIPwarningMessage(scip, "Error while solving LP in vbound heuristic; LP solve terminated with code <%d>\n", 1098 retstat); 1099 } 1100 } 1101 #else 1102 SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, NULL) ); 1103 #endif 1104 SCIPdebugMsg(scip, "ending solving vbound-lp at time %g\n", SCIPgetSolvingTime(scip)); 1105 1106 lpstatus = SCIPgetLPSolstat(scip); 1107 1108 SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip)); 1109 SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, lpstatus); 1110 } 1111 1112 /* check if this is a feasible solution */ 1113 if( lpstatus == SCIP_LPSOLSTAT_OPTIMAL && !lperror ) 1114 { 1115 SCIP_Bool stored; 1116 SCIP_Bool success; 1117 SCIP_SOL* sol; 1118 1119 lowerbound = SCIPgetLPObjval(scip); 1120 1121 /* copy the current LP solution to the working solution */ 1122 SCIP_CALL( SCIPcreateSol(scip, &sol, heur) ); 1123 SCIP_CALL( SCIPlinkLPSol(scip, sol) ); 1124 1125 SCIP_CALL( SCIProundSol(scip, sol, &success) ); 1126 1127 if( success ) 1128 { 1129 SCIPdebugMsg(scip, "vbound heuristic found roundable primal solution: obj=%g\n", 1130 SCIPgetSolOrigObj(scip, sol)); 1131 1132 /* check solution for feasibility, and add it to solution store if possible. 1133 * Neither integrality nor feasibility of LP rows have to be checked, because they 1134 * are guaranteed by the heuristic at this stage. 1135 */ 1136 #ifdef SCIP_DEBUG 1137 SCIP_CALL( SCIPtrySol(scip, sol, TRUE, TRUE, TRUE, TRUE, TRUE, &stored) ); 1138 #else 1139 SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, TRUE, FALSE, FALSE, &stored) ); 1140 #endif 1141 1142 #ifdef SCIP_DEBUG 1143 SCIP_CALL( SCIPcheckSol(scip, sol, FALSE, FALSE, TRUE, TRUE, TRUE, &wasfeas) ); 1144 assert(wasfeas); 1145 SCIPdebugMsg(scip, "found feasible solution by LP rounding: %16.9g\n", SCIPgetSolOrigObj(scip, sol)); 1146 #endif 1147 1148 if( stored ) 1149 *result = SCIP_FOUNDSOL; 1150 1151 SCIP_CALL( SCIPfreeSol(scip, &sol) ); 1152 1153 /* we found a solution, so we are done */ 1154 goto TERMINATE; 1155 } 1156 1157 SCIP_CALL( SCIPfreeSol(scip, &sol) ); 1158 } 1159 /*************************** END Probing LP Solving ***************************/ 1160 1161 /*************************** Start Subscip Solving ***************************/ 1162 /* if no solution has been found --> fix all other variables by subscip if necessary */ 1163 if( !lperror && lpstatus != SCIP_LPSOLSTAT_INFEASIBLE && lpstatus != SCIP_LPSOLSTAT_OBJLIMIT ) 1164 { 1165 SCIP* subscip; 1166 SCIP_RETCODE retcode; 1167 SCIP_Bool valid; 1168 1169 /* check whether there is enough time and memory left */ 1170 SCIP_CALL( SCIPcheckCopyLimits(scip, &valid) ); 1171 1172 if( !valid ) 1173 goto TERMINATE; 1174 1175 /* create subproblem */ 1176 SCIP_CALL( SCIPcreate(&subscip) ); 1177 1178 retcode = setupAndSolveSubscip(scip, subscip, heur, vars, nvars, nstallnodes, lowerbound, 1179 &nprevars, &wasfeas, result); 1180 1181 SCIP_CALL( SCIPfree(&subscip) ); 1182 1183 SCIP_CALL( retcode ); 1184 } 1185 1186 /*************************** End Subscip Solving ***************************/ 1187 1188 TERMINATE: 1189 #ifdef SCIP_STATISTIC 1190 SCIP_CALL( SCIPstopClock(scip, clock) ); 1191 SCIPstatisticMessage("vbound: tighten=%u obj=%d nvars=%d presolnvars=%d ratio=%.2f infeas=%u found=%d time=%.4f\n", 1192 tighten, obj, nvars, nprevars, (nvars - nprevars) / (SCIP_Real)nvars, cutoff, 1193 wasfeas ? 1 : 0, SCIPclockGetTime(clock) ); 1194 #endif 1195 1196 SCIPstatistic( SCIP_CALL( SCIPfreeClock(scip, &clock) ) ); 1197 1198 /* exit probing mode */ 1199 if( SCIPinProbing(scip) ) 1200 { 1201 SCIP_CALL( SCIPendProbing(scip) ); 1202 } 1203 1204 return SCIP_OKAY; /*lint !e438*/ 1205 } 1206 1207 1208 /* 1209 * Callback methods of primal heuristic 1210 */ 1211 1212 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 1213 static 1214 SCIP_DECL_HEURCOPY(heurCopyVbounds) 1215 { /*lint --e{715}*/ 1216 assert(scip != NULL); 1217 assert(heur != NULL); 1218 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 1219 1220 /* call inclusion method of heuristic */ 1221 SCIP_CALL( SCIPincludeHeurVbounds(scip) ); 1222 1223 return SCIP_OKAY; 1224 } 1225 1226 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 1227 static 1228 SCIP_DECL_HEURFREE(heurFreeVbounds) 1229 { /*lint --e{715}*/ 1230 SCIP_HEURDATA* heurdata; 1231 1232 /* free heuristic data */ 1233 heurdata = SCIPheurGetData(heur); 1234 1235 SCIPfreeBlockMemory(scip, &heurdata); 1236 SCIPheurSetData(heur, NULL); 1237 1238 return SCIP_OKAY; 1239 } 1240 1241 1242 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */ 1243 static 1244 SCIP_DECL_HEUREXITSOL(heurExitsolVbounds) 1245 { /*lint --e{715}*/ 1246 SCIP_HEURDATA* heurdata; 1247 int v; 1248 1249 heurdata = SCIPheurGetData(heur); 1250 assert(heurdata != NULL); 1251 1252 /* release all variables */ 1253 for( v = 0; v < heurdata->nvbvars; ++v ) 1254 { 1255 SCIP_CALL( SCIPreleaseVar(scip, &heurdata->vbvars[v]) ); 1256 } 1257 1258 /* free varbounds array */ 1259 SCIPfreeBlockMemoryArrayNull(scip, &heurdata->vbbounds, heurdata->nvbvars); 1260 SCIPfreeBlockMemoryArrayNull(scip, &heurdata->vbvars, heurdata->nvbvars); 1261 1262 /* reset heuristic data structure */ 1263 heurdataReset(heurdata); 1264 1265 return SCIP_OKAY; 1266 } 1267 1268 /** execution method of primal heuristic */ 1269 static 1270 SCIP_DECL_HEUREXEC(heurExecVbounds) 1271 { /*lint --e{715}*/ 1272 SCIP_HEURDATA* heurdata; 1273 SCIP_Bool skipobj1; 1274 SCIP_Bool skipobj2; 1275 #ifdef NOCONFLICT 1276 SCIP_Bool enabledconflicts; 1277 #endif 1278 1279 assert( heur != NULL ); 1280 assert( scip != NULL ); 1281 assert( result != NULL ); 1282 1283 *result = SCIP_DIDNOTRUN; 1284 1285 if( SCIPgetNPseudoBranchCands(scip) == 0 ) 1286 return SCIP_OKAY; 1287 1288 heurdata = SCIPheurGetData(heur); 1289 assert(heurdata != NULL); 1290 1291 if( !heurdata->initialized ) 1292 { 1293 SCIP_CALL( initializeCandsLists(scip, heurdata) ); 1294 } 1295 1296 if( !heurdata->applicable ) 1297 return SCIP_OKAY; 1298 1299 #ifdef NOCONFLICT 1300 /* disable conflict analysis */ 1301 SCIP_CALL( SCIPgetBoolParam(scip, "conflict/enable", &enabledconflicts) ); 1302 1303 if( !SCIPisParamFixed(scip, "conflict/enable") ) 1304 { 1305 SCIP_CALL( SCIPsetBoolParam(scip, "conflict/enable", FALSE) ); 1306 } 1307 #endif 1308 1309 /* try variable bounds */ 1310 skipobj1 = FALSE; 1311 skipobj2 = FALSE; 1312 if( ((unsigned)heurdata->feasvariant & VBOUNDVARIANT_NOOBJ) != 0 ) 1313 { 1314 SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, FALSE, 0, 1315 &skipobj1, &skipobj2, result) ); 1316 } 1317 if( !skipobj1 && ((unsigned) heurdata->feasvariant & VBOUNDVARIANT_BESTBOUND) != 0) 1318 { 1319 SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, FALSE, 1, NULL, NULL, result) ); 1320 } 1321 if( !skipobj2 && ((unsigned) heurdata->feasvariant & VBOUNDVARIANT_WORSTBOUND) != 0) 1322 { 1323 SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, FALSE, 2, NULL, NULL, result) ); 1324 } 1325 1326 skipobj1 = FALSE; 1327 skipobj2 = FALSE; 1328 if( ((unsigned) heurdata->tightenvariant & VBOUNDVARIANT_NOOBJ) != 0 ) 1329 { 1330 SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, TRUE, 0, 1331 &skipobj1, &skipobj2, result) ); 1332 } 1333 if( !skipobj1 && ((unsigned) heurdata->tightenvariant & VBOUNDVARIANT_BESTBOUND) != 0) 1334 { 1335 SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, TRUE, 1, NULL, NULL, result) ); 1336 } 1337 if( !skipobj2 && ((unsigned) heurdata->tightenvariant & VBOUNDVARIANT_WORSTBOUND) != 0) 1338 { 1339 SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, TRUE, 2, NULL, NULL, result) ); 1340 } 1341 1342 #ifdef NOCONFLICT 1343 /* reset the conflict analysis */ 1344 if( !SCIPisParamFixed(scip, "conflict/enable") ) 1345 { 1346 SCIP_CALL( SCIPsetBoolParam(scip, "conflict/enable", enabledconflicts) ); 1347 } 1348 #endif 1349 1350 return SCIP_OKAY; 1351 } 1352 1353 /* 1354 * primal heuristic specific interface methods 1355 */ 1356 1357 /** creates the vbounds primal heuristic and includes it in SCIP */ 1358 SCIP_RETCODE SCIPincludeHeurVbounds( 1359 SCIP* scip /**< SCIP data structure */ 1360 ) 1361 { 1362 SCIP_HEURDATA* heurdata; 1363 SCIP_HEUR* heur; 1364 1365 /* create vbounds primal heuristic data */ 1366 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 1367 heurdataReset(heurdata); 1368 1369 /* include primal heuristic */ 1370 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 1371 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 1372 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecVbounds, heurdata) ); 1373 1374 assert(heur != NULL); 1375 1376 /* set non-NULL pointers to callback methods */ 1377 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyVbounds) ); 1378 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeVbounds) ); 1379 SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolVbounds) ); 1380 1381 /* add variable bounds primal heuristic parameters */ 1382 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minintfixingrate", 1383 "minimum percentage of integer variables that have to be fixed", 1384 &heurdata->minintfixingrate, FALSE, DEFAULT_MININTFIXINGRATE, 0.0, 1.0, NULL, NULL) ); 1385 1386 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minmipfixingrate", 1387 "minimum percentage of variables that have to be fixed within sub-SCIP (integer and continuous)", 1388 &heurdata->minmipfixingrate, FALSE, DEFAULT_MINMIPFIXINGRATE, 0.0, 1.0, NULL, NULL) ); 1389 1390 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes", 1391 "maximum number of nodes to regard in the subproblem", 1392 &heurdata->maxnodes, TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 1393 1394 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs", 1395 "number of nodes added to the contingent of the total nodes", 1396 &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 1397 1398 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes", 1399 "minimum number of nodes required to start the subproblem", 1400 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 1401 1402 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot", 1403 "contingent of sub problem nodes in relation to the number of nodes of the original problem", 1404 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) ); 1405 1406 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove", 1407 "factor by which " HEUR_NAME " heuristic should at least improve the incumbent", 1408 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) ); 1409 1410 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxproprounds", 1411 "maximum number of propagation rounds during probing (-1 infinity)", 1412 &heurdata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -1, INT_MAX/4, NULL, NULL) ); 1413 1414 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts", 1415 "should all active cuts from cutpool be copied to constraints in subproblem?", 1416 &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) ); 1417 1418 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselockfixings", 1419 "should more variables be fixed based on variable locks if the fixing rate was not reached?", 1420 &heurdata->uselockfixings, TRUE, DEFAULT_USELOCKFIXINGS, NULL, NULL) ); 1421 1422 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxbacktracks", 1423 "maximum number of backtracks during the fixing process", 1424 &heurdata->maxbacktracks, TRUE, DEFAULT_MAXBACKTRACKS, -1, INT_MAX/4, NULL, NULL) ); 1425 1426 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/feasvariant", 1427 "which variants of the vbounds heuristic that try to stay feasible should be called? (0: off, 1: w/o looking at obj, 2: only fix to best bound, 4: only fix to worst bound", 1428 &heurdata->feasvariant, TRUE, (int) DEFAULT_FEASVARIANT, 0, 7, NULL, NULL) ); 1429 1430 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/tightenvariant", 1431 "which tightening variants of the vbounds heuristic should be called? (0: off, 1: w/o looking at obj, 2: only fix to best bound, 4: only fix to worst bound", 1432 &heurdata->tightenvariant, TRUE, (int) DEFAULT_TIGHTENVARIANT, 0, 7, NULL, NULL) ); 1433 1434 return SCIP_OKAY; 1435 } 1436 1437 /**@} */ 1438