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_completesol.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief COMPLETESOL - primal heuristic trying to complete given partial solutions 28 * @author Jakob Witzig 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include "blockmemshell/memory.h" 34 #include "scip/cons_linear.h" 35 #include "scip/heur_completesol.h" 36 #include "scip/pub_event.h" 37 #include "scip/pub_heur.h" 38 #include "scip/pub_message.h" 39 #include "scip/pub_misc.h" 40 #include "scip/pub_sol.h" 41 #include "scip/pub_var.h" 42 #include "scip/scip_branch.h" 43 #include "scip/scip_cons.h" 44 #include "scip/scip_copy.h" 45 #include "scip/scip_event.h" 46 #include "scip/scip_general.h" 47 #include "scip/scip_heur.h" 48 #include "scip/scip_mem.h" 49 #include "scip/scip_message.h" 50 #include "scip/scip_nlp.h" 51 #include "scip/scip_nodesel.h" 52 #include "scip/scip_numerics.h" 53 #include "scip/scip_param.h" 54 #include "scip/scip_prob.h" 55 #include "scip/scip_probing.h" 56 #include "scip/scip_sol.h" 57 #include "scip/scip_solve.h" 58 #include "scip/scip_solvingstats.h" 59 #include "scip/scip_timing.h" 60 #include "scip/scip_tree.h" 61 #include "scip/scip_var.h" 62 #include <string.h> 63 64 #define HEUR_NAME "completesol" 65 #define HEUR_DESC "primal heuristic trying to complete given partial solutions" 66 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS 67 #define HEUR_PRIORITY 0 68 #define HEUR_FREQ 0 69 #define HEUR_FREQOFS 0 70 #define HEUR_MAXDEPTH 0 71 #define HEUR_TIMING SCIP_HEURTIMING_BEFOREPRESOL | SCIP_HEURTIMING_BEFORENODE 72 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */ 73 74 /* default values for heuristic plugins */ 75 #define DEFAULT_MAXNODES 5000LL /**< maximum number of nodes to regard in the subproblem */ 76 #define DEFAULT_MAXUNKRATE 0.85 /**< maximum percentage of unknown solution values */ 77 #define DEFAULT_ADDALLSOLS FALSE /**< should all subproblem solutions be added to the original SCIP? */ 78 #define DEFAULT_MINNODES 50LL /**< minimum number of nodes to regard in the subproblem */ 79 #define DEFAULT_NODESOFS 500LL /**< number of nodes added to the contingent of the total nodes */ 80 #define DEFAULT_NODESQUOT 0.1 /**< subproblem nodes in relation to nodes of the original problem */ 81 #define DEFAULT_LPLIMFAC 2.0 /**< factor by which the limit on the number of LP depends on the node limit */ 82 #define DEFAULT_OBJWEIGHT 1.0 /**< weight of the original objective function (1: only original objective) */ 83 #define DEFAULT_BOUNDWIDENING 0.1 /**< bound widening factor applied to continuous variables 84 * (0: round bounds to next integer, 1: relax to global bounds) 85 */ 86 #define DEFAULT_MINIMPROVE 0.01 /**< factor by which the incumbent should be improved at least */ 87 #define DEFAULT_MINOBJWEIGHT 1e-3 /**< minimal weight for original objective function (zero could lead to infinite solutions) */ 88 #define DEFAULT_IGNORECONT FALSE /**< should solution values for continuous variables be ignored? */ 89 #define DEFAULT_BESTSOLS 5 /**< heuristic stops, if the given number of improving solutions were found (-1: no limit) */ 90 #define DEFAULT_MAXPROPROUNDS 10 /**< maximal number of iterations in propagation (-1: no limit) */ 91 #define DEFAULT_MAXLPITER -1LL /**< maximal number of LP iterations (-1: no limit) */ 92 #define DEFAULT_MAXCONTVARS -1 /**< maximal number of continuous variables after presolving (-1: no limit) */ 93 #define DEFAULT_BEFOREPRESOL TRUE /**< should the heuristic run before presolving? */ 94 95 /* event handler properties */ 96 #define EVENTHDLR_NAME "Completesol" 97 #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" 98 99 100 /** primal heuristic data */ 101 struct SCIP_HeurData 102 { 103 SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */ 104 SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */ 105 SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */ 106 SCIP_Longint maxlpiter; /**< maximal number of LP iterations (-1: no limit) */ 107 SCIP_Real maxunknownrate; /**< maximal rate of changed coefficients in the objective function */ 108 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */ 109 SCIP_Real nodelimit; /**< the nodelimit employed in the current sub-SCIP, for the event handler*/ 110 SCIP_Real lplimfac; /**< factor by which the limit on the number of LP depends on the node limit */ 111 SCIP_Real objweight; /**< weight of the original objective function (1: only original obj, 0: try to keep to given solution) */ 112 SCIP_Real boundwidening; /**< bound widening factor applied to continuous variables 113 * (0: fix variables to given solution values, 1: relax to global bounds) 114 */ 115 SCIP_Real minimprove; /**< factor by which the incumbent should be improved at least */ 116 SCIP_Bool addallsols; /**< should all subproblem solutions be added to the original SCIP? */ 117 SCIP_Bool ignorecont; /**< should solution values for continuous variables be ignored? */ 118 SCIP_Bool beforepresol; /**< should the heuristic run before presolving? */ 119 int bestsols; /**< heuristic stops, if the given number of improving solutions were found (-1: no limit) */ 120 int maxcontvars; /**< maximal number of continuous variables after presolving (-1: no limit) */ 121 int maxproprounds; /**< maximal number of iterations in propagation (-1: no limit) */ 122 }; 123 124 /* ---------------- Callback methods of event handler ---------------- */ 125 126 /* exec the event handler 127 * 128 * we interrupt the solution process 129 */ 130 static 131 SCIP_DECL_EVENTEXEC(eventExecCompletesol) 132 { 133 SCIP_HEURDATA* heurdata; 134 135 assert(eventhdlr != NULL); 136 assert(eventdata != NULL); 137 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0); 138 assert(event != NULL); 139 assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_LPSOLVED); 140 141 heurdata = (SCIP_HEURDATA*)eventdata; 142 assert(heurdata != NULL); 143 144 /* interrupt solution process of sub-SCIP */ 145 if( SCIPgetNLPs(scip) > heurdata->lplimfac * heurdata->nodelimit ) 146 { 147 SCIPdebugMsg(scip, "interrupt after %" SCIP_LONGINT_FORMAT " LPs\n",SCIPgetNLPs(scip)); 148 SCIP_CALL( SCIPinterruptSolve(scip) ); 149 } 150 151 return SCIP_OKAY; 152 } 153 154 /** creates a subproblem by fixing a number of variables */ 155 static 156 SCIP_RETCODE createSubproblem( 157 SCIP* scip, /**< original SCIP data structure */ 158 SCIP* subscip, /**< SCIP data structure for the subproblem */ 159 SCIP_HEURDATA* heurdata, /**< heuristic's private data structure */ 160 SCIP_VAR** subvars, /**< the variables of the subproblem */ 161 SCIP_SOL* partialsol, /**< partial solution */ 162 SCIP_Bool* tightened /**< array to store for which variables we have found bound tightenings */ 163 ) 164 { 165 SCIP_VAR** vars; 166 SCIP_CONS* objcons; 167 SCIP_Real epsobj; 168 SCIP_Real cutoff; 169 SCIP_Real upperbound; 170 char consobjname[SCIP_MAXSTRLEN]; 171 int nvars; 172 int i; 173 174 assert(scip != NULL); 175 assert(subscip != NULL); 176 assert(subvars != NULL); 177 assert(heurdata != NULL); 178 179 /* if there is already a solution, add an objective cutoff */ 180 if( SCIPgetNSols(scip) > 0 ) 181 { 182 assert(!SCIPisInfinity(scip, SCIPgetUpperbound(scip))); 183 184 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip); 185 186 if( !SCIPisInfinity(scip, -1.0 * SCIPgetLowerbound(scip)) ) 187 cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip) + heurdata->minimprove * SCIPgetLowerbound(scip); 188 else 189 { 190 if( SCIPgetUpperbound(scip) >= 0 ) 191 cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip); 192 else 193 cutoff = (1 + heurdata->minimprove) * SCIPgetUpperbound(scip); 194 } 195 cutoff = MIN(upperbound, cutoff); 196 SCIPdebugMsg(scip, "set cutoff=%g for sub-SCIP\n", cutoff); 197 } 198 else 199 cutoff = SCIPinfinity(scip); 200 201 /* calculate objective coefficients for all potential epsilons */ 202 if( SCIPisEQ(scip, heurdata->objweight, 1.0) ) 203 return SCIP_OKAY; 204 else if( !SCIPisInfinity(scip, cutoff) ) 205 epsobj = 1.0; 206 else 207 { 208 /* divide by objweight to avoid changing objective coefficient of original problem variables */ 209 epsobj = (1.0 - heurdata->objweight)/heurdata->objweight; 210 211 /* scale with -1 if we have a maximization problem */ 212 if( SCIPgetObjsense(scip) == SCIP_OBJSENSE_MAXIMIZE ) 213 epsobj *= -1.0; 214 } 215 216 /* get active variables */ 217 vars = SCIPgetVars(scip); 218 nvars = SCIPgetNVars(scip); 219 220 objcons = NULL; 221 222 /* add constraints to measure the distance to the given partial solution */ 223 for( i = 0; i < nvars; i++ ) 224 { 225 SCIP_Real solval; 226 int idx; 227 228 assert(SCIPvarIsActive(vars[i])); 229 230 if( subvars[i] == NULL ) 231 continue; 232 233 /* add objective function as a constraint, if a primal bound exists */ 234 if( SCIPisInfinity(scip, cutoff) ) 235 { 236 /* create the constraints */ 237 if( objcons == NULL ) 238 { 239 SCIP_Real lhs; 240 SCIP_Real rhs; 241 242 if( SCIPgetObjsense(subscip) == SCIP_OBJSENSE_MINIMIZE ) 243 { 244 lhs = -SCIPinfinity(subscip); 245 rhs = cutoff; 246 } 247 else 248 { 249 lhs = cutoff; 250 rhs = SCIPinfinity(subscip); 251 } 252 253 (void)SCIPsnprintf(consobjname, SCIP_MAXSTRLEN, "obj"); 254 SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &objcons, consobjname, 0, NULL, NULL, lhs, rhs) ); 255 } 256 257 /* add the variable to the constraints */ 258 SCIP_CALL( SCIPaddCoefLinear(subscip, objcons, subvars[i], SCIPvarGetObj(subvars[i])) ); 259 260 /* set objective coefficient to 0.0 */ 261 SCIP_CALL( SCIPchgVarObj(subscip, subvars[i], 0.0) ); 262 } 263 264 solval = SCIPgetSolVal(scip, partialsol, vars[i]); 265 266 /* skip variables with unknown solution value */ 267 if( solval == SCIP_UNKNOWN ) /*lint !e777*/ 268 continue; 269 270 idx = SCIPvarGetProbindex(vars[i]); 271 assert(idx >= 0); 272 273 /* skip variables where we already found some bound tightenings */ 274 if( tightened[idx] == FALSE ) 275 { 276 /* special case: vars[i] is binary; we do not add an extra variable, but we mimic the behavior we would get with it. 277 * E.g., if the solval is 0.3, setting the variable to 0 would give a cost of 0.3 * epsobj, setting it to 1 gives 278 * 0.7 * epsobj. Thus, 0.3 * epsobj can be treated as a constant in the objective function and the variable gets 279 * an objective coefficient of 0.4 * epsobj. 280 */ 281 if( SCIPvarIsBinary(vars[i]) ) 282 { 283 SCIP_Real frac = SCIPfeasFrac(scip, solval); 284 SCIP_Real objcoef; 285 286 frac = MIN(frac, 1-frac); 287 objcoef = (1 - 2*frac) * epsobj * (int)SCIPgetObjsense(scip); 288 289 if( solval > 0.5 ) 290 { 291 SCIP_CALL( SCIPchgVarObj(scip, vars[i], -objcoef) ); 292 } 293 else 294 { 295 SCIP_CALL( SCIPchgVarObj(scip, vars[i], objcoef) ); 296 } 297 } 298 else 299 { 300 SCIP_CONS* conspos; 301 SCIP_CONS* consneg; 302 SCIP_VAR* eps; 303 char consnamepos[SCIP_MAXSTRLEN]; 304 char consnameneg[SCIP_MAXSTRLEN]; 305 char epsname[SCIP_MAXSTRLEN]; 306 307 /* create two new variables */ 308 (void)SCIPsnprintf(epsname, SCIP_MAXSTRLEN, "eps_%s", SCIPvarGetName(subvars[i])); 309 310 SCIP_CALL( SCIPcreateVarBasic(subscip, &eps, epsname, 0.0, SCIPinfinity(scip), epsobj, SCIP_VARTYPE_CONTINUOUS) ); 311 SCIP_CALL( SCIPaddVar(subscip, eps) ); 312 313 /* create two constraints */ 314 (void)SCIPsnprintf(consnamepos, SCIP_MAXSTRLEN, "cons_%s_pos", SCIPvarGetName(subvars[i])); 315 (void)SCIPsnprintf(consnameneg, SCIP_MAXSTRLEN, "cons_%s_neq", SCIPvarGetName(subvars[i])); 316 317 /* x_{i} - s_{i} <= e_{i} <==> x_{i} - e_{i} <= s_{i} */ 318 SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &conspos, consnamepos, 0, NULL, NULL, -SCIPinfinity(scip), solval) ); 319 SCIP_CALL( SCIPaddCoefLinear(subscip, conspos, subvars[i], 1.0) ); 320 SCIP_CALL( SCIPaddCoefLinear(subscip, conspos, eps, -1.0) ); 321 SCIP_CALL( SCIPaddCons(subscip, conspos) ); 322 SCIP_CALL( SCIPreleaseCons(subscip, &conspos) ); 323 324 /* s_{i} - x_{i} <= e_{i} <==> e_{i} - x_{i} >= s_{i} */ 325 SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &consneg, consnameneg, 0, NULL, NULL, solval, SCIPinfinity(scip)) ); 326 SCIP_CALL( SCIPaddCoefLinear(subscip, consneg, subvars[i], -1.0) ); 327 SCIP_CALL( SCIPaddCoefLinear(subscip, consneg, eps, 1.0) ); 328 SCIP_CALL( SCIPaddCons(subscip, consneg) ); 329 SCIP_CALL( SCIPreleaseCons(subscip, &consneg) ); 330 331 /* release the variables */ 332 SCIP_CALL( SCIPreleaseVar(subscip, &eps) ); 333 } 334 } 335 } 336 337 /* add and release the constraint representing the original objective function */ 338 if( objcons != NULL ) 339 { 340 SCIP_CALL( SCIPaddCons(subscip, objcons) ); 341 SCIP_CALL( SCIPreleaseCons(subscip, &objcons) ); 342 } 343 344 return SCIP_OKAY; 345 } 346 347 /** perform a probing bound change or fixes the variable */ 348 static 349 SCIP_RETCODE chgProbingBound( 350 SCIP* scip, /**< original SCIP data structure */ 351 SCIP_VAR* var, /**< problem variable */ 352 SCIP_Real newval, /**< new bound */ 353 SCIP_BRANCHDIR branchdir, /**< bound change direction */ 354 SCIP_Bool* success /**< pointer to store whether the bound could be tightened */ 355 ) 356 { 357 SCIP_Real ub; 358 SCIP_Real lb; 359 360 assert(scip != NULL); 361 assert(var != NULL); 362 363 (*success) = FALSE; 364 365 ub = SCIPvarGetUbLocal(var); 366 lb = SCIPvarGetLbLocal(var); 367 368 switch (branchdir) { 369 case SCIP_BRANCHDIR_DOWNWARDS: 370 if( SCIPisLT(scip, newval, ub) && SCIPisGE(scip, newval, lb) ) 371 { 372 SCIP_CALL( SCIPchgVarUbProbing(scip, var, newval) ); 373 (*success) = TRUE; 374 } 375 break; 376 case SCIP_BRANCHDIR_UPWARDS: 377 if( SCIPisLE(scip, newval, ub) && SCIPisGT(scip, newval, lb) ) 378 { 379 SCIP_CALL( SCIPchgVarLbProbing(scip, var, newval) ); 380 (*success) = TRUE; 381 } 382 break; 383 case SCIP_BRANCHDIR_FIXED: 384 if( SCIPisLE(scip, newval, ub) && SCIPisGE(scip, newval, lb) ) 385 { 386 SCIP_CALL( SCIPfixVarProbing(scip, var, newval) ); 387 (*success) = TRUE; 388 } 389 break; 390 default: 391 return SCIP_INVALIDDATA; 392 }/*lint !e788*/ 393 394 return SCIP_OKAY; 395 } 396 397 /** tries variables bound changes guided by the given solution */ 398 static 399 SCIP_RETCODE tightenVariables( 400 SCIP* scip, /**< original SCIP data structure */ 401 SCIP_HEURDATA* heurdata, /**< heuristic's private data structure */ 402 SCIP_VAR** vars, /**< problem variables */ 403 int nvars, /**< number of problem variables */ 404 SCIP_SOL* sol, /**< solution to guide the bound changes */ 405 SCIP_Bool* tightened, /**< array to store if variable bound could be tightened */ 406 SCIP_Bool* infeasible /**< pointer to store whether subproblem is infeasible */ 407 ) 408 { 409 #ifndef NDEBUG 410 SCIP_Bool incontsection; 411 #endif 412 SCIP_Bool abortearly; 413 SCIP_Bool cutoff; 414 SCIP_Bool probingsuccess; 415 SCIP_Longint ndomreds; 416 SCIP_Longint ndomredssum; 417 int nbndtightenings; 418 int v; 419 420 assert(scip != NULL); 421 assert(heurdata != NULL); 422 assert(vars != NULL); 423 assert(nvars >= 0); 424 assert(sol != NULL); 425 assert(tightened != NULL); 426 427 assert(SCIPsolGetOrigin(sol) == SCIP_SOLORIGIN_PARTIAL); 428 429 SCIPdebugMsg(scip, "> start probing along the solution values\n"); 430 431 *infeasible = FALSE; 432 abortearly = FALSE; 433 nbndtightenings = 0; 434 ndomredssum = 0; 435 #ifndef NDEBUG 436 incontsection = FALSE; 437 #endif 438 439 /* there is at least one integral variable; open one probing node for all non-continuous variables */ 440 if( nvars - SCIPgetNContVars(scip) > 0 ) 441 { 442 SCIP_CALL( SCIPnewProbingNode(scip) ); 443 } 444 445 for( v = 0; v < nvars && !abortearly; v++ ) 446 { 447 SCIP_Real solval; 448 449 assert(SCIPvarIsActive(vars[v])); 450 451 cutoff = FALSE; 452 ndomreds = 0; 453 454 #ifndef NDEBUG 455 incontsection |= (!SCIPvarIsIntegral(vars[v])); /*lint !e514*/ 456 assert(!incontsection || !SCIPvarIsIntegral(vars[v])); 457 #endif 458 459 /* return if we have found enough domain reductions tightenings */ 460 if( ndomredssum > 0.3*nvars ) 461 break; 462 463 solval = SCIPgetSolVal(scip, sol, vars[v]); 464 465 /* skip unknown variables */ 466 if( solval == SCIP_UNKNOWN ) /*lint !e777*/ 467 continue; 468 assert(!SCIPisInfinity(scip, solval) && !SCIPisInfinity(scip, -solval)); 469 470 /* variable is binary or integer */ 471 if( SCIPvarIsIntegral(vars[v]) ) 472 { 473 /* the solution value is integral, try to fix them */ 474 if( SCIPisIntegral(scip, solval) ) 475 { 476 SCIP_CALL( chgProbingBound(scip, vars[v], solval, SCIP_BRANCHDIR_FIXED, &probingsuccess) ); 477 tightened[SCIPvarGetProbindex(vars[v])] = TRUE; 478 ++nbndtightenings; 479 480 #ifdef SCIP_MORE_DEBUG 481 SCIPdebugMsg(scip, "> fix variable <%s> = [%g,%g] to %g \n", SCIPvarGetName(vars[v]), 482 SCIPvarGetLbGlobal(vars[v]), SCIPvarGetUbGlobal(vars[v]), solval); 483 #endif 484 } 485 else 486 { 487 SCIP_Real ub = SCIPceil(scip, solval) + 1.0; 488 SCIP_Real lb = SCIPfloor(scip, solval) - 1.0; 489 490 /* try tightening of upper bound */ 491 if( SCIPisLT(scip, ub, SCIPvarGetUbLocal(vars[v])) ) 492 { 493 SCIP_CALL( chgProbingBound(scip, vars[v], solval, SCIP_BRANCHDIR_DOWNWARDS, &probingsuccess) ); 494 tightened[SCIPvarGetProbindex(vars[v])] = TRUE; 495 ++nbndtightenings; 496 497 #ifdef SCIP_MORE_DEBUG 498 SCIPdebugMsg(scip, "> tighten upper bound of variable <%s>: %g to %g\n", SCIPvarGetName(vars[v]), 499 SCIPvarGetUbGlobal(vars[v]), ub); 500 #endif 501 } 502 503 /* try tightening of lower bound */ 504 if( SCIPisGT(scip, lb, SCIPvarGetLbLocal(vars[v])) ) 505 { 506 SCIP_CALL( chgProbingBound(scip, vars[v], solval, SCIP_BRANCHDIR_UPWARDS, &probingsuccess) ); 507 tightened[SCIPvarGetProbindex(vars[v])] = TRUE; 508 ++nbndtightenings; 509 510 #ifdef SCIP_MORE_DEBUG 511 SCIPdebugMsg(scip, "> tighten lower bound of variable <%s>: %g to %g\n", SCIPvarGetName(vars[v]), 512 SCIPvarGetLbGlobal(vars[v]), ub); 513 #endif 514 } 515 } 516 } 517 /* variable is continuous */ 518 else 519 { 520 /* fix to lb or ub */ 521 if( SCIPisEQ(scip, solval, SCIPvarGetLbLocal(vars[v])) || SCIPisEQ(scip, solval, SCIPvarGetUbLocal(vars[v])) ) 522 { 523 /* open a new probing node */ 524 if( SCIPgetProbingDepth(scip) < SCIP_MAXTREEDEPTH-10 ) 525 { 526 SCIP_CALL( SCIPnewProbingNode(scip) ); 527 528 SCIP_CALL( chgProbingBound(scip, vars[v], solval, SCIP_BRANCHDIR_FIXED, &probingsuccess) ); 529 530 /* skip propagation if the bound could not be changed, e.g., already tightened due to previous 531 * domain propagation 532 */ 533 if( probingsuccess ) 534 { 535 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, &cutoff, &ndomreds) ); 536 } 537 538 if( cutoff ) 539 { 540 ndomreds = 0; 541 SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip)-1) ); 542 } 543 else 544 { 545 assert(SCIPvarGetProbindex(vars[v]) >= 0); 546 tightened[SCIPvarGetProbindex(vars[v])] = TRUE; 547 ++nbndtightenings; 548 #ifdef SCIP_MORE_DEBUG 549 SCIPdebugMsg(scip, "> fix variable <%s> = [%g,%g] to %g (ndomreds=%lld)\n", SCIPvarGetName(vars[v]), 550 SCIPvarGetLbGlobal(vars[v]), SCIPvarGetUbGlobal(vars[v]), solval, ndomreds); 551 #endif 552 } 553 } 554 else 555 /* abort probing */ 556 abortearly = TRUE; 557 } 558 else 559 { 560 SCIP_Real offset; 561 SCIP_Real newub = SCIPvarGetUbGlobal(vars[v]); 562 SCIP_Real newlb = SCIPvarGetLbGlobal(vars[v]); 563 564 /* both bound are finite */ 565 if( !SCIPisInfinity(scip, -newlb) && !SCIPisInfinity(scip, newub) ) 566 offset = REALABS(heurdata->boundwidening * (newub-newlb)); 567 else 568 { 569 offset = 0.0; 570 571 /* if exactly one bound is finite, widen bound w.r.t. solution value and finite bound */ 572 if( !SCIPisInfinity(scip, -newlb) ) 573 offset = REALABS(heurdata->boundwidening * (solval-newlb)); 574 else if( !SCIPisInfinity(scip, newub) ) 575 offset = REALABS(heurdata->boundwidening * (newub-solval)); 576 } 577 578 /* update bounds */ 579 newub = SCIPceil(scip, solval) + offset; 580 newlb = SCIPfloor(scip, solval) - offset; 581 582 /* try tightening of upper bound */ 583 if( SCIPisLT(scip, newub, SCIPvarGetUbLocal(vars[v])) ) 584 { 585 /* open a new probing node */ 586 if( SCIPgetProbingDepth(scip) < SCIP_MAXTREEDEPTH-10 ) 587 { 588 SCIP_CALL( SCIPnewProbingNode(scip) ); 589 SCIP_CALL( chgProbingBound(scip, vars[v], newub, SCIP_BRANCHDIR_DOWNWARDS, &probingsuccess) ); 590 591 /* skip propagation if the bound could not be changed, e.g., already tightened due to previous 592 * domain propagation 593 */ 594 if( probingsuccess ) 595 { 596 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, &cutoff, &ndomreds) ); 597 } 598 599 if( cutoff ) 600 { 601 ndomreds = 0; 602 603 /* backtrack to last feasible probing node */ 604 SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip)-1) ); 605 606 /* we can tighten the lower bound by newub */ 607 SCIP_CALL( chgProbingBound(scip, vars[v], newub, SCIP_BRANCHDIR_UPWARDS, &probingsuccess) ); 608 609 /* propagate the new bound */ 610 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, &cutoff, &ndomreds) ); 611 612 /* there is no feasible solution w.r.t. the current bounds */ 613 if( cutoff ) 614 { 615 SCIPdebugMsg(scip, "> subproblem is infeasible within the local bounds\n"); 616 *infeasible = TRUE; 617 return SCIP_OKAY; 618 } 619 #ifdef SCIP_MORE_DEBUG 620 SCIPdebugMsg(scip, "> tighten lower bound of variable <%s>: %g to %g\n", 621 SCIPvarGetName(vars[v]), SCIPvarGetLbGlobal(vars[v]), newub); 622 #endif 623 } 624 else 625 { 626 assert(SCIPvarGetProbindex(vars[v]) >= 0); 627 tightened[SCIPvarGetProbindex(vars[v])] = TRUE; 628 ++nbndtightenings; 629 #ifdef SCIP_MORE_DEBUG 630 SCIPdebugMsg(scip, "> tighten upper bound of variable <%s>: %g to %g (ndomreds=%lld)\n", 631 SCIPvarGetName(vars[v]), SCIPvarGetUbGlobal(vars[v]), newub, ndomreds); 632 #endif 633 } 634 } 635 else 636 /* abort probing */ 637 abortearly = TRUE; 638 } 639 640 /* try tightening of lower bound */ 641 if( SCIPisGT(scip, newlb, SCIPvarGetLbLocal(vars[v])) ) 642 { 643 /* open a new probing node */ 644 if( SCIPgetProbingDepth(scip) < SCIP_MAXTREEDEPTH-10 ) 645 { 646 SCIP_CALL( SCIPnewProbingNode(scip) ); 647 SCIP_CALL( chgProbingBound(scip, vars[v], newlb, SCIP_BRANCHDIR_UPWARDS, &probingsuccess) ); 648 649 /* skip propagation if the bound could not be changed, e.g., already tightened due to previous 650 * domain propagation 651 */ 652 if( probingsuccess ) 653 { 654 SCIP_CALL( SCIPpropagateProbing(scip, -1, &cutoff, &ndomreds) ); 655 } 656 657 if( cutoff ) 658 { 659 ndomreds = 0; 660 661 /* backtrack to last feasible probing node */ 662 SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip)-1) ); 663 664 /* we can tighten the upper bound by newlb */ 665 SCIP_CALL( chgProbingBound(scip, vars[v], newlb, SCIP_BRANCHDIR_DOWNWARDS, &probingsuccess) ); 666 667 /* propagate the new bound */ 668 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, &cutoff, &ndomreds) ); 669 670 /* there is no feasible solution w.r.t. the current bounds */ 671 if( cutoff ) 672 { 673 SCIPdebugMsg(scip, "> subproblem is infeasible within the local bounds\n"); 674 *infeasible = TRUE; 675 return SCIP_OKAY; 676 } 677 #ifdef SCIP_MORE_DEBUG 678 SCIPdebugMsg(scip, "> tighten upper bound of variable <%s>: %g to %g\n", 679 SCIPvarGetName(vars[v]), SCIPvarGetUbGlobal(vars[v]), newlb); 680 #endif 681 } 682 else 683 { 684 assert(SCIPvarGetProbindex(vars[v]) >= 0); 685 tightened[SCIPvarGetProbindex(vars[v])] = TRUE; 686 ++nbndtightenings; 687 #ifdef SCIP_MORE_DEBUG 688 SCIPdebugMsg(scip, "> tighten lower bound of variable <%s>: %g to %g (ndomreds=%lld)\n", 689 SCIPvarGetName(vars[v]), SCIPvarGetLbGlobal(vars[v]), newlb, ndomreds); 690 #endif 691 } 692 } 693 else 694 /* abort probing */ 695 abortearly = TRUE; 696 } 697 } 698 } 699 700 ndomredssum += ndomreds; 701 } 702 703 SCIPdebugMsg(scip, "> found %d bound tightenings and %lld induced domain reductions (abort=%u).\n", nbndtightenings, 704 ndomredssum, abortearly); 705 706 return SCIP_OKAY; 707 } 708 709 /* setup and solve the sub-SCIP */ 710 static 711 SCIP_RETCODE setupAndSolve( 712 SCIP* scip, /**< original SCIP data structure */ 713 SCIP* subscip, /**< sub-SCIP data structure */ 714 SCIP_HEUR* heur, /**< heuristic data structure */ 715 SCIP_HEURDATA* heurdata, /**< heuristic's private data structure */ 716 SCIP_RESULT* result, /**< result data structure */ 717 SCIP_Longint nstallnodes, /**< number of stalling nodes for the subproblem */ 718 SCIP_SOL* partialsol, /**< partial solution */ 719 SCIP_Bool* tightened /**< array to store whether a variable was already tightened */ 720 ) 721 { 722 SCIP_HASHMAP* varmapf; 723 SCIP_VAR** vars; 724 SCIP_VAR** subvars = NULL; 725 SCIP_EVENTHDLR* eventhdlr; 726 int nvars; 727 int i; 728 729 SCIP_SOL** subsols; 730 int nsubsols; 731 732 SCIP_Bool valid; 733 SCIP_Bool success; 734 SCIP_RETCODE retcode; 735 736 assert(scip != NULL); 737 assert(subscip != NULL); 738 assert(heur != NULL); 739 assert(heurdata != NULL); 740 assert(result != NULL); 741 assert(partialsol != NULL); 742 743 vars = SCIPgetVars(scip); 744 nvars = SCIPgetNVars(scip); 745 746 /* create the variable mapping hash map */ 747 SCIP_CALL( SCIPhashmapCreate(&varmapf, SCIPblkmem(subscip), nvars) ); 748 749 eventhdlr = NULL; 750 valid = FALSE; 751 752 /* copy complete SCIP instance */ 753 SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmapf, NULL, "completesol", NULL, NULL, 0, FALSE, FALSE, FALSE, 754 TRUE, &valid) ); 755 SCIPdebugMsg(scip, "Copying the SCIP instance returned with valid=%u.\n", valid); 756 757 /* create event handler for LP events */ 758 SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecCompletesol, NULL) ); 759 if( eventhdlr == NULL ) 760 { 761 SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n"); 762 return SCIP_PLUGINNOTFOUND; 763 } 764 765 /* allocate memory to align the SCIP and the sub-SCIP variables */ 766 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) ); 767 768 /* map all variables */ 769 for( i = 0; i < nvars; i++ ) 770 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapf, vars[i]); 771 772 /* free hash map */ 773 SCIPhashmapFree(&varmapf); 774 775 /* create a new problem, which fixes variables with same value in bestsol and LP relaxation */ 776 SCIP_CALL( createSubproblem(scip, subscip, heurdata, subvars, partialsol, tightened) ); 777 SCIPdebugMsg(scip, "Completesol subproblem: %d vars, %d cons\n", SCIPgetNVars(subscip), SCIPgetNConss(subscip)); 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", SCIP_VERBLEVEL_FULL) ); 785 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", -1) ); 786 #else 787 /* disable statistic timing inside sub SCIP and output to console */ 788 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", (int) SCIP_VERBLEVEL_NONE) ); 789 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) ); 790 #endif 791 792 /* set limits for the subproblem */ 793 SCIP_CALL( SCIPcopyLimits(scip, subscip) ); 794 heurdata->nodelimit = heurdata->maxnodes; 795 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) ); 796 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", heurdata->maxnodes) ); 797 SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->bestsols) ); 798 799 /* limit the number of LP iterations */ 800 SCIP_CALL( SCIPsetLongintParam(subscip, "lp/iterlim", heurdata->maxlpiter) ); 801 SCIP_CALL( SCIPsetLongintParam(subscip, "lp/rootiterlim", heurdata->maxlpiter) ); 802 803 /* forbid recursive call of heuristics and separators solving sub-SCIPs */ 804 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) ); 805 806 /* disable cutting plane separation */ 807 SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) ); 808 809 /* disable expensive presolving */ 810 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) ); 811 812 /* use best estimate node selection */ 813 if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") ) 814 { 815 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) ); 816 } 817 818 /* use inference branching */ 819 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") ) 820 { 821 SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) ); 822 } 823 824 /* disable conflict analysis */ 825 if( !SCIPisParamFixed(subscip, "conflict/enable") ) 826 { 827 SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", FALSE) ); 828 } 829 830 /* speed up sub-SCIP by not checking dual LP feasibility */ 831 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) ); 832 833 SCIP_CALL( SCIPtransformProb(subscip) ); 834 SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) ); 835 836 /* solve the subproblem */ 837 SCIPdebugMsg(scip, "solving subproblem: nstallnodes=%" SCIP_LONGINT_FORMAT ", maxnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->maxnodes); 838 839 /* errors in solving the subproblem should not kill the overall solving process; 840 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. 841 */ 842 843 retcode = SCIPpresolve(subscip); 844 845 /* errors in presolving the subproblem should not kill the overall solving process; 846 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. 847 */ 848 if( retcode != SCIP_OKAY ) 849 { 850 SCIPwarningMessage(scip, "Error while presolving subproblem in %s heuristic; sub-SCIP terminated with code <%d>\n", HEUR_NAME, retcode); 851 852 SCIPABORT(); /*lint --e{527}*/ 853 854 goto TERMINATE; 855 } 856 857 if( SCIPgetStage(subscip) == SCIP_STAGE_PRESOLVED ) 858 { 859 SCIPdebugMsg(scip, "presolved instance has bin=%d, int=%d, cont=%d variables\n", 860 SCIPgetNBinVars(subscip), SCIPgetNIntVars(subscip), SCIPgetNContVars(subscip)); 861 862 /* check whether the presolved instance is small enough */ 863 if( heurdata->maxcontvars >= 0 && SCIPgetNContVars(subscip) > heurdata->maxcontvars ) 864 { 865 SCIPdebugMsg(scip, "presolved instance has too many continuous variables (maxcontvars: %d)\n", heurdata->maxcontvars); 866 goto TERMINATE; 867 } 868 869 /* set node limit of 1 if the presolved problem is an LP, otherwise we would start branching if an LP iteration 870 * limit was set by the user. 871 */ 872 if( !SCIPisNLPEnabled(subscip) && SCIPgetNContVars(subscip) == SCIPgetNVars(subscip) ) 873 { 874 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", 1LL) ); 875 } 876 877 retcode = SCIPsolve(subscip); 878 879 /* errors in solving the subproblem should not kill the overall solving process; 880 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. 881 */ 882 if( retcode != SCIP_OKAY ) 883 { 884 SCIPwarningMessage(scip, "Error while solving subproblem in %s heuristic; sub-SCIP terminated with code <%d>\n", HEUR_NAME, retcode); 885 886 SCIPABORT(); /*lint --e{527}*/ 887 888 goto TERMINATE; 889 } 890 } 891 892 SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) ); 893 894 /* print solving statistics of subproblem if we are in SCIP's debug mode */ 895 SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) ); 896 897 /* check, whether a solution was found; 898 * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted 899 */ 900 nsubsols = SCIPgetNSols(subscip); 901 subsols = SCIPgetSols(subscip); 902 success = FALSE; 903 for( i = 0; i < nsubsols && (!success || heurdata->addallsols); i++ ) 904 { 905 SCIP_SOL* newsol; 906 907 /* create new solution, try to add to SCIP, and free it immediately */ 908 SCIP_CALL( SCIPtranslateSubSol(scip, subscip, subsols[i], heur, subvars, &newsol) ); 909 SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) ); 910 911 if( success ) 912 *result = SCIP_FOUNDSOL; 913 } 914 915 SCIPstatisticPrintf("%s statistic: fixed %6.3f integer variables, needed %6.1f seconds, %" SCIP_LONGINT_FORMAT " nodes, solution %10.4f found at node %" SCIP_LONGINT_FORMAT "\n", 916 HEUR_NAME, 0.0, SCIPgetSolvingTime(subscip), SCIPgetNNodes(subscip), success ? SCIPgetPrimalbound(scip) : SCIPinfinity(scip), 917 nsubsols > 0 ? SCIPsolGetNodenum(SCIPgetBestSol(subscip)) : -1 ); 918 919 /* print message if the completion of a partial solution failed */ 920 if( *result != SCIP_FOUNDSOL ) 921 { 922 switch( SCIPgetStatus(subscip) ) 923 { 924 case SCIP_STATUS_INFEASIBLE: 925 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "completion of a partial solution failed (subproblem is infeasible)\n"); 926 break; 927 case SCIP_STATUS_NODELIMIT: 928 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "completion of a partial solution failed (node limit exceeded)\n"); 929 break; 930 case SCIP_STATUS_TIMELIMIT: 931 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "completion of a partial solution failed (time limit exceeded)\n"); 932 break; 933 case SCIP_STATUS_MEMLIMIT: 934 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "completion of a partial solution failed (memory limit exceeded)\n"); 935 break; 936 default: 937 break; 938 } /*lint !e788*/ 939 } 940 941 TERMINATE: 942 SCIPfreeBufferArray(scip, &subvars); 943 944 return SCIP_OKAY; 945 } 946 947 /** main procedure of the completesol heuristic, creates and solves a sub-SCIP */ 948 static 949 SCIP_RETCODE applyCompletesol( 950 SCIP* scip, /**< original SCIP data structure */ 951 SCIP_HEUR* heur, /**< heuristic data structure */ 952 SCIP_HEURDATA* heurdata, /**< heuristic's private data structure */ 953 SCIP_RESULT* result, /**< result data structure */ 954 SCIP_Longint nstallnodes, /**< number of stalling nodes for the subproblem */ 955 SCIP_SOL* partialsol /**< partial solution */ 956 ) 957 { 958 SCIP* subscip; 959 SCIP_VAR** vars; 960 SCIP_Bool* tightened; 961 SCIP_Bool infeasible; 962 SCIP_Bool success; 963 SCIP_RETCODE retcode; 964 int nvars; 965 966 assert(scip != NULL); 967 assert(heur != NULL); 968 assert(heurdata != NULL); 969 assert(result != NULL); 970 assert(partialsol != NULL); 971 972 *result = SCIP_DIDNOTRUN; 973 974 SCIPdebugMsg(scip, "+---+ Start Completesol heuristic +---+\n"); 975 976 /* check whether there is enough time and memory left */ 977 SCIP_CALL( SCIPcheckCopyLimits(scip, &success) ); 978 979 if( !success ) 980 return SCIP_OKAY; 981 982 *result = SCIP_DIDNOTFIND; 983 984 /* get variable data */ 985 vars = SCIPgetVars(scip); 986 nvars = SCIPgetNVars(scip); 987 988 /* get buffer memory and initialize it to FALSE */ 989 SCIP_CALL( SCIPallocClearBufferArray(scip, &tightened, nvars) ); 990 991 SCIP_CALL( SCIPstartProbing(scip) ); 992 993 SCIP_CALL( tightenVariables(scip, heurdata, vars, nvars, partialsol, tightened, &infeasible) ); 994 995 if( infeasible ) 996 { 997 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "completion of a partial solution failed (subproblem is infeasible)\n"); 998 goto ENDPROBING; 999 } 1000 1001 /* initialize the subproblem */ 1002 SCIP_CALL( SCIPcreate(&subscip) ); 1003 1004 retcode = setupAndSolve(scip, subscip, heur, heurdata, result, nstallnodes, partialsol, tightened); 1005 1006 /* free subproblem */ 1007 SCIP_CALL( SCIPfree(&subscip) ); 1008 1009 SCIP_CALL( retcode ); 1010 1011 ENDPROBING: 1012 SCIPfreeBufferArray(scip, &tightened); 1013 SCIP_CALL( SCIPendProbing(scip) ); 1014 1015 return SCIP_OKAY; 1016 } 1017 1018 1019 /* 1020 * Callback methods of primal heuristic 1021 */ 1022 1023 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 1024 static 1025 SCIP_DECL_HEURCOPY(heurCopyCompletesol) 1026 { /*lint --e{715}*/ 1027 assert(scip != NULL); 1028 assert(heur != NULL); 1029 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 1030 1031 /* call inclusion method of primal heuristic */ 1032 SCIP_CALL( SCIPincludeHeurCompletesol(scip) ); 1033 1034 return SCIP_OKAY; 1035 } 1036 1037 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 1038 static 1039 SCIP_DECL_HEURFREE(heurFreeCompletesol) 1040 { /*lint --e{715}*/ 1041 SCIP_HEURDATA* heurdata; 1042 1043 assert(heur != NULL); 1044 assert(scip != NULL); 1045 1046 /* get heuristic data */ 1047 heurdata = SCIPheurGetData(heur); 1048 assert(heurdata != NULL); 1049 1050 /* free heuristic data */ 1051 SCIPfreeBlockMemory(scip, &heurdata); 1052 SCIPheurSetData(heur, NULL); 1053 1054 return SCIP_OKAY; 1055 } 1056 1057 /** execution method of primal heuristic */ 1058 static 1059 SCIP_DECL_HEUREXEC(heurExecCompletesol) 1060 {/*lint --e{715}*/ 1061 SCIP_HEURDATA* heurdata; 1062 SCIP_VAR** vars; 1063 SCIP_SOL** partialsols; 1064 SCIP_Longint nstallnodes; 1065 int npartialsols; 1066 int nunknown; 1067 int nfracints; 1068 int nvars; 1069 int s; 1070 int v; 1071 1072 assert( heur != NULL ); 1073 assert( scip != NULL ); 1074 assert( result != NULL ); 1075 1076 *result = SCIP_DELAYED; 1077 1078 /* do not call heuristic of node was already detected to be infeasible */ 1079 if( nodeinfeasible ) 1080 return SCIP_OKAY; 1081 1082 /* get heuristic data */ 1083 heurdata = SCIPheurGetData(heur); 1084 assert( heurdata != NULL ); 1085 1086 *result = SCIP_DIDNOTRUN; 1087 1088 if( SCIPisStopped(scip) ) 1089 return SCIP_OKAY; 1090 1091 /* do not run after restart */ 1092 if( SCIPgetNRuns(scip) > 1 ) 1093 return SCIP_OKAY; 1094 1095 /* check whether we want to run before presolving */ 1096 if( (heurtiming & SCIP_HEURTIMING_BEFOREPRESOL) && !heurdata->beforepresol ) 1097 return SCIP_OKAY; 1098 1099 /* only run before root node */ 1100 if( (heurtiming & SCIP_HEURTIMING_BEFORENODE) 1101 && (heurdata->beforepresol || SCIPgetCurrentNode(scip) != SCIPgetRootNode(scip)) ) 1102 return SCIP_OKAY; 1103 1104 /* get variable data and return of no variables are left in the problem */ 1105 vars = SCIPgetVars(scip); 1106 nvars = SCIPgetNVars(scip); 1107 1108 if( nvars == 0 ) 1109 return SCIP_OKAY; 1110 1111 /* calculate the maximal number of branching nodes until heuristic is aborted */ 1112 nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip)); 1113 1114 /* reward Completesol if it succeeded often */ 1115 nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0)); 1116 nstallnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-SCIP as 100 nodes */ 1117 nstallnodes += heurdata->nodesofs; 1118 1119 /* determine the node limit for the current process */ 1120 nstallnodes = MIN(nstallnodes, heurdata->maxnodes); 1121 1122 /* check whether we have enough nodes left to call subproblem solving */ 1123 if( nstallnodes < heurdata->minnodes ) 1124 { 1125 SCIPdebugMsg(scip, "skipping Complete: nstallnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", 1126 nstallnodes, heurdata->minnodes); 1127 return SCIP_OKAY; 1128 } 1129 1130 /* check the number of variables with unknown value and continuous variables with fractional value */ 1131 nfracints = 0; 1132 1133 /* get all partial sols */ 1134 npartialsols = SCIPgetNPartialSols(scip); 1135 partialsols = SCIPgetPartialSols(scip); 1136 1137 /* loop over all partial solutions */ 1138 for( s = 0; s < npartialsols; s++ ) 1139 { 1140 SCIP_SOL* sol; 1141 SCIP_Real solval; 1142 SCIP_Real unknownrate; 1143 1144 sol = partialsols[s]; 1145 assert(sol != NULL); 1146 assert(SCIPsolIsPartial(sol)); 1147 1148 nunknown = 0; 1149 /* loop over all variables */ 1150 for( v = 0; v < nvars; v++ ) 1151 { 1152 assert(SCIPvarIsActive(vars[v])); 1153 1154 /* skip continuous variables if they should ignored */ 1155 if( !SCIPvarIsIntegral(vars[v]) && heurdata->ignorecont ) 1156 continue; 1157 1158 solval = SCIPgetSolVal(scip, sol, vars[v]); 1159 1160 /* we only want to count variables that are unfixed after the presolving */ 1161 if( solval == SCIP_UNKNOWN ) /*lint !e777*/ 1162 ++nunknown; 1163 else if( SCIPvarIsIntegral(vars[v]) && !SCIPisIntegral(scip, solval) ) 1164 ++nfracints; 1165 } 1166 1167 if( heurdata->ignorecont ) 1168 unknownrate = nunknown/((SCIP_Real)SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) + SCIPgetNImplVars(scip)); 1169 else 1170 unknownrate = nunknown/((SCIP_Real)nvars); 1171 SCIPdebugMsg(scip, "%d (rate %.4f) unknown solution values\n", nunknown, unknownrate); 1172 1173 /* run the heuristic, if not too many unknown variables exist */ 1174 if( unknownrate > heurdata->maxunknownrate ) 1175 { 1176 SCIPwarningMessage(scip, "ignore partial solution (%d) because unknown rate is too large (%g > %g)\n", s, 1177 unknownrate, heurdata->maxunknownrate); 1178 continue; 1179 } 1180 1181 /* all variables have a finite/known solution value all integer variables have an integral solution value, 1182 * and there are no continuous variables 1183 * in the sub-SCIP, all variables would be fixed, so create a new solution without solving a sub-SCIP 1184 */ 1185 if( nunknown == 0 && nfracints == 0 && SCIPgetNContVars(scip) == 0 && SCIPgetNImplVars(scip) == 0 ) 1186 { 1187 SCIP_SOL* newsol; 1188 SCIP_Bool stored; 1189 1190 assert(vars != NULL); 1191 assert(nvars >= 0); 1192 1193 SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) ); 1194 1195 for( v = 0; v < nvars; v++ ) 1196 { 1197 solval = SCIPgetSolVal(scip, sol, vars[v]); 1198 assert(solval != SCIP_UNKNOWN); /*lint !e777*/ 1199 1200 SCIP_CALL( SCIPsetSolVal(scip, newsol, vars[v], solval) ); 1201 } 1202 1203 SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &stored) ); 1204 if( stored ) 1205 *result = SCIP_FOUNDSOL; 1206 } 1207 else 1208 { 1209 /* run the heuristic */ 1210 SCIP_CALL( applyCompletesol(scip, heur, heurdata, result, nstallnodes, sol) ); 1211 } 1212 } 1213 1214 return SCIP_OKAY; 1215 } 1216 1217 1218 /* 1219 * primal heuristic specific interface methods 1220 */ 1221 1222 /** creates the completesol primal heuristic and includes it in SCIP */ 1223 SCIP_RETCODE SCIPincludeHeurCompletesol( 1224 SCIP* scip /**< SCIP data structure */ 1225 ) 1226 { 1227 SCIP_HEURDATA* heurdata; 1228 SCIP_HEUR* heur; 1229 1230 /* create completesol primal heuristic data */ 1231 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 1232 assert(heurdata != NULL); 1233 1234 /* include primal heuristic */ 1235 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 1236 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 1237 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecCompletesol, heurdata) ); 1238 1239 assert(heur != NULL); 1240 1241 /* set non fundamental callbacks via setter functions */ 1242 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyCompletesol) ); 1243 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeCompletesol) ); 1244 1245 /* add completesol primal heuristic parameters */ 1246 1247 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes", 1248 "maximum number of nodes to regard in the subproblem", 1249 &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 1250 1251 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes", 1252 "minimum number of nodes required to start the subproblem", 1253 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 1254 1255 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxunknownrate", 1256 "maximal rate of unknown solution values", 1257 &heurdata->maxunknownrate, FALSE, DEFAULT_MAXUNKRATE, 0.0, 1.0, NULL, NULL) ); 1258 1259 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/addallsols", 1260 "should all subproblem solutions be added to the original SCIP?", 1261 &heurdata->addallsols, TRUE, DEFAULT_ADDALLSOLS, NULL, NULL) ); 1262 1263 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs", 1264 "number of nodes added to the contingent of the total nodes", 1265 &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 1266 1267 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot", 1268 "contingent of sub problem nodes in relation to the number of nodes of the original problem", 1269 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) ); 1270 1271 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lplimfac", 1272 "factor by which the limit on the number of LP depends on the node limit", 1273 &heurdata->lplimfac, TRUE, DEFAULT_LPLIMFAC, 1.0, SCIP_REAL_MAX, NULL, NULL) ); 1274 1275 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/objweight", 1276 "weight of the original objective function (1: only original objective)", 1277 &heurdata->objweight, TRUE, DEFAULT_OBJWEIGHT, DEFAULT_MINOBJWEIGHT, 1.0, NULL, NULL) ); 1278 1279 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/boundwidening", 1280 "bound widening factor applied to continuous variables (0: fix variables to given solution values, 1: relax to global bounds)", 1281 &heurdata->boundwidening, TRUE, DEFAULT_BOUNDWIDENING, 0.0, 1.0, NULL, NULL) ); 1282 1283 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove", 1284 "factor by which the incumbent should be improved at least", 1285 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) ); 1286 1287 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/ignorecont", 1288 "should number of continuous variables be ignored?", 1289 &heurdata->ignorecont, FALSE, DEFAULT_IGNORECONT, NULL, NULL) ); 1290 1291 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/solutions", 1292 "heuristic stops, if the given number of improving solutions were found (-1: no limit)", 1293 &heurdata->bestsols, FALSE, DEFAULT_BESTSOLS, -1, INT_MAX, NULL, NULL) ); 1294 1295 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxproprounds", 1296 "maximal number of iterations in propagation (-1: no limit)", 1297 &heurdata->maxproprounds, FALSE, DEFAULT_MAXPROPROUNDS, -1, INT_MAX, NULL, NULL) ); 1298 1299 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/beforepresol", 1300 "should the heuristic run before presolving?", 1301 &heurdata->beforepresol, FALSE, DEFAULT_BEFOREPRESOL, NULL, NULL) ); 1302 1303 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxlpiter", 1304 "maximal number of LP iterations (-1: no limit)", 1305 &heurdata->maxlpiter, FALSE, DEFAULT_MAXLPITER, -1LL, SCIP_LONGINT_MAX, NULL, NULL) ); 1306 1307 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxcontvars", 1308 "maximal number of continuous variables after presolving", 1309 &heurdata->maxcontvars, FALSE, DEFAULT_MAXCONTVARS, -1, INT_MAX, NULL, NULL) ); 1310 1311 return SCIP_OKAY; 1312 } 1313