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_dins.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief DINS primal heuristic (according to Ghosh) 28 * @author Timo Berthold 29 * @author Robert Waniek 30 */ 31 32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 33 34 #include "blockmemshell/memory.h" 35 #include "scip/cons_linear.h" 36 #include "scip/heur_dins.h" 37 #include "scip/heuristics.h" 38 #include "scip/pub_event.h" 39 #include "scip/pub_heur.h" 40 #include "scip/pub_message.h" 41 #include "scip/pub_misc.h" 42 #include "scip/pub_var.h" 43 #include "scip/scip_branch.h" 44 #include "scip/scip_cons.h" 45 #include "scip/scip_copy.h" 46 #include "scip/scip_event.h" 47 #include "scip/scip_general.h" 48 #include "scip/scip_heur.h" 49 #include "scip/scip_lp.h" 50 #include "scip/scip_mem.h" 51 #include "scip/scip_message.h" 52 #include "scip/scip_nodesel.h" 53 #include "scip/scip_numerics.h" 54 #include "scip/scip_param.h" 55 #include "scip/scip_prob.h" 56 #include "scip/scip_sol.h" 57 #include "scip/scip_solve.h" 58 #include "scip/scip_solvingstats.h" 59 #include "scip/scip_var.h" 60 #include <string.h> 61 62 #define HEUR_NAME "dins" 63 #define HEUR_DESC "distance induced neighborhood search by Ghosh" 64 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS 65 #define HEUR_PRIORITY -1105000 66 #define HEUR_FREQ -1 67 #define HEUR_FREQOFS 0 68 #define HEUR_MAXDEPTH -1 69 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE 70 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */ 71 72 #define DEFAULT_NODESOFS 5000LL /* number of nodes added to the contingent of the total nodes */ 73 #define DEFAULT_MAXNODES 5000LL /* maximum number of nodes to regard in the subproblem */ 74 #define DEFAULT_MINNODES 50LL /* minimum number of nodes to regard in the subproblem */ 75 #define DEFAULT_MINIMPROVE 0.01 /* factor by which DINS should at least improve the incumbent */ 76 #define DEFAULT_NODESQUOT 0.05 /* subproblem nodes in relation to nodes of the original problem */ 77 #define DEFAULT_LPLIMFAC 1.5 /* factor by which the limit on the number of LP depends on the node limit */ 78 #define DEFAULT_MINFIXINGRATE 0.3 /* minimum percentage of integer variables that have to be fixed */ 79 #define DEFAULT_NWAITINGNODES 200LL /* number of nodes without incumbent change that heuristic should wait */ 80 #define DEFAULT_NEIGHBORHOODSIZE 18 /* radius of the incumbents neighborhood to be searched */ 81 #define DEFAULT_SOLNUM 5 /* number of pool-solutions to be checked for flag array update */ 82 #define DEFAULT_USELPROWS FALSE /* should subproblem be created out of the rows in the LP rows, 83 * otherwise, the copy constructors of the constraints handlers are used */ 84 #define DEFAULT_COPYCUTS TRUE /* if DEFAULT_USELPROWS is FALSE, then should all active cuts from the cutpool 85 * of the original scip be copied to constraints of the subscip */ 86 87 #define DEFAULT_BESTSOLLIMIT 3 /* limit on number of improving incumbent solutions in sub-CIP */ 88 #define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */ 89 90 91 /* event handler properties */ 92 #define EVENTHDLR_NAME "Dins" 93 #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" 94 95 /* 96 * Data structures 97 */ 98 99 /** DINS primal heuristic data */ 100 struct SCIP_HeurData 101 { 102 SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */ 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_Real minfixingrate; /**< minimum percentage of integer variables that have to be fixed */ 106 SCIP_Longint nwaitingnodes; /**< number of nodes without incumbent change that heuristic should wait */ 107 SCIP_Real minimprove; /**< factor by which DINS should at least improve the incumbent */ 108 SCIP_Longint usednodes; /**< nodes already used by DINS in earlier calls */ 109 SCIP_Longint lastnsolsfound; /**< total number of found solutions at previous execution of DINS */ 110 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */ 111 SCIP_Real nodelimit; /**< the nodelimit employed in the current sub-SCIP, for the event handler*/ 112 SCIP_Real lplimfac; /**< factor by which the limit on the number of LP depends on the node limit */ 113 int neighborhoodsize; /**< radius of the incumbent's neighborhood to be searched */ 114 SCIP_Bool* delta; /**< stores whether a variable kept its value from root LP all the time */ 115 int deltalength; /**< if there are no binary variables, we need no flag array */ 116 int solnum; /**< number of pool-solutions to be checked for flag array update */ 117 SCIP_Bool uselprows; /**< should subproblem be created out of the rows in the LP rows? */ 118 SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied 119 * to constraints in subproblem? 120 */ 121 int bestsollimit; /**< limit on number of improving incumbent solutions in sub-CIP */ 122 SCIP_Bool useuct; /**< should uct node selection be used at the beginning of the search? */ 123 }; 124 125 126 /* 127 * Local methods 128 */ 129 130 /** compute tightened bounds for integer variables depending on how much the LP and the incumbent solution values differ */ 131 static 132 void computeIntegerVariableBounds( 133 SCIP* scip, /**< SCIP data structure of the original problem */ 134 SCIP_VAR* var, /**< the variable for which bounds should be computed */ 135 SCIP_Real* lbptr, /**< pointer to store the lower bound in the DINS sub-SCIP */ 136 SCIP_Real* ubptr /**< pointer to store the upper bound in the DINS sub-SCIP */ 137 ) 138 { 139 SCIP_Real mipsol; 140 SCIP_Real lpsol; 141 142 SCIP_Real lbglobal; 143 SCIP_Real ubglobal; 144 SCIP_SOL* bestsol; 145 146 /* get the bounds for each variable */ 147 lbglobal = SCIPvarGetLbGlobal(var); 148 ubglobal = SCIPvarGetUbGlobal(var); 149 150 assert(SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER); 151 /* get the current LP solution for each variable */ 152 lpsol = SCIPvarGetLPSol(var); 153 154 /* get the current MIP solution for each variable */ 155 bestsol = SCIPgetBestSol(scip); 156 mipsol = SCIPgetSolVal(scip, bestsol, var); 157 158 /* if the solution values differ by 0.5 or more, the variable is rebounded, otherwise it is just copied */ 159 if( REALABS(lpsol - mipsol) >= 0.5 ) 160 { 161 SCIP_Real range; 162 163 *lbptr = lbglobal; 164 *ubptr = ubglobal; 165 166 /* create a equally sized range around lpsol for general integers: bounds are lpsol +- (mipsol-lpsol) */ 167 range = 2*lpsol-mipsol; 168 169 if( mipsol >= lpsol ) 170 { 171 range = SCIPfeasCeil(scip, range); 172 *lbptr = MAX(*lbptr, range); 173 174 /* when the bound new upper bound is equal to the current MIP solution, we set both bounds to the integral bound (without eps) */ 175 if( SCIPisFeasEQ(scip, mipsol, *lbptr) ) 176 *ubptr = *lbptr; 177 else 178 *ubptr = mipsol; 179 } 180 else 181 { 182 range = SCIPfeasFloor(scip, range); 183 *ubptr = MIN(*ubptr, range); 184 185 /* when the bound new upper bound is equal to the current MIP solution, we set both bounds to the integral bound (without eps) */ 186 if( SCIPisFeasEQ(scip, mipsol, *ubptr) ) 187 *lbptr = *ubptr; 188 else 189 *lbptr = mipsol; 190 } 191 192 /* the global domain of variables might have been reduced since incumbent was found: adjust lb and ub accordingly */ 193 *lbptr = MAX(*lbptr, lbglobal); 194 *ubptr = MIN(*ubptr, ubglobal); 195 } 196 else 197 { 198 /* the global domain of variables might have been reduced since incumbent was found: adjust it accordingly */ 199 *lbptr = MAX(mipsol, lbglobal); 200 *ubptr = MIN(mipsol, ubglobal); 201 } 202 } 203 204 /** creates a subproblem for subscip by fixing a number of variables */ 205 static 206 SCIP_RETCODE determineVariableFixings( 207 SCIP* scip, /**< SCIP data structure of the original problem */ 208 SCIP_HEUR* heur, /**< DINS heuristic structure */ 209 SCIP_HEURDATA* heurdata, /**< heuristic data structure */ 210 SCIP_VAR** vars, /**< variables of the original problem */ 211 SCIP_VAR** fixedvars, /**< array to store variables that should be fixed in the sub-SCIP */ 212 SCIP_Real* fixedvals, /**< array to store fixing values for fixed variables */ 213 int nbinvars, /**< number of binary variables of problem and subproblem */ 214 int nintvars, /**< number of general integer variables of problem and subproblem */ 215 int* binfixings, /**< pointer to store number of binary variables that should be fixed */ 216 int* intfixings /**< pointer to store number of integer variables that should be fixed */ 217 ) 218 { 219 SCIP_SOL* bestsol; 220 SCIP_SOL** sols; 221 SCIP_Bool* delta; 222 int i; 223 int nsols; 224 SCIP_Longint nsolsfound; 225 int checklength; 226 int nfixedvars; 227 228 assert(scip != NULL); 229 assert(vars != NULL); 230 assert(fixedvars != NULL); 231 assert(fixedvals != NULL); 232 assert(binfixings != NULL); 233 assert(intfixings != NULL); 234 assert(heur != NULL); 235 236 /* get the best MIP-solution known so far */ 237 bestsol = SCIPgetBestSol(scip); 238 assert(bestsol != NULL); 239 240 /* get solution pool and number of solutions in pool */ 241 sols = SCIPgetSols(scip); 242 nsols = SCIPgetNSols(scip); 243 nsolsfound = SCIPgetNSolsFound(scip); 244 checklength = MIN(nsols, heurdata->solnum); 245 assert(sols != NULL); 246 assert(nsols > 0); 247 248 /* if new binary variables have been created, e.g., due to column generation, reallocate the delta array */ 249 if( heurdata->deltalength < nbinvars ) 250 { 251 int newsize; 252 253 newsize = SCIPcalcMemGrowSize(scip, nbinvars); 254 assert(newsize >= nbinvars); 255 256 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &heurdata->delta, heurdata->deltalength, newsize) ); 257 258 /* initialize new part of delta array */ 259 for( i = heurdata->deltalength; i < newsize; i++ ) 260 heurdata->delta[i] = TRUE; 261 262 heurdata->deltalength = newsize; 263 } 264 265 delta = heurdata->delta; 266 /* fixing for binary variables */ 267 /* hard fixing for some with mipsol(s)=lpsolval=rootlpsolval and preparation for soft fixing for the remaining */ 268 nfixedvars = 0; 269 *intfixings = *binfixings = 0; 270 for( i = 0; i < nbinvars; i++ ) 271 { 272 SCIP_Real lpsolval; 273 SCIP_Real mipsolval; 274 SCIP_Real rootlpsolval; 275 int j; 276 277 /* get the current LP solution for each variable */ 278 lpsolval = SCIPvarGetLPSol(vars[i]); 279 /* get the current MIP solution for each variable */ 280 mipsolval = SCIPgetSolVal(scip, bestsol, vars[i]); 281 /* get the root LP solution for each variable */ 282 rootlpsolval = SCIPvarGetRootSol(vars[i]); 283 284 if( SCIPisFeasEQ(scip, lpsolval, mipsolval) && SCIPisFeasEQ(scip, mipsolval, rootlpsolval) ) 285 { 286 /* update delta */ 287 if( nsols > 1 && heurdata->lastnsolsfound != nsolsfound && delta[i] ) /* no need to update delta[i] if already FALSE */ 288 { 289 /* no need to update delta[i] if already FALSE or sols[i] already checked on previous run or worse than DINS-solution of last run */ 290 for( j = 1; delta[i] && j < checklength && SCIPgetSolHeur(scip, sols[j]) != heur ; j++ ) 291 { 292 SCIP_Real solval; 293 solval = SCIPgetSolVal(scip, sols[j], vars[i]); 294 delta[i] = delta[i] && SCIPisFeasEQ(scip, mipsolval, solval); 295 } 296 } 297 298 /* hard fixing if rootlpsolval=nodelpsolval=mipsolval(s) and delta (is TRUE) */ 299 if( delta[i] ) 300 { 301 fixedvars[nfixedvars] = vars[i]; 302 fixedvals[nfixedvars] = mipsolval; 303 ++nfixedvars; 304 } 305 } 306 } 307 308 *binfixings = nfixedvars; 309 310 /* store the number of found solutions for next run */ 311 heurdata->lastnsolsfound = nsolsfound; 312 313 /* compute a tighter bound for the variable in the subproblem; */ 314 for( i = nbinvars; i < nbinvars + nintvars; ++i ) 315 { 316 SCIP_Real lb; 317 SCIP_Real ub; 318 computeIntegerVariableBounds(scip, vars[i], &lb, &ub); 319 320 /* hard fixing if heuristic bounds coincide */ 321 if( ub - lb < 0.5 ) 322 { 323 fixedvars[(nfixedvars)] = vars[i]; 324 fixedvals[(nfixedvars)] = lb; 325 ++nfixedvars; 326 } 327 } 328 329 *intfixings = nfixedvars - *binfixings; 330 331 return SCIP_OKAY; 332 } 333 334 /** creates a subproblem for subscip by fixing a number of variables */ 335 static 336 SCIP_RETCODE reboundIntegerVariables( 337 SCIP* scip, /**< SCIP data structure of the original problem */ 338 SCIP* subscip, /**< SCIP data structure of the subproblem */ 339 SCIP_VAR** vars, /**< variables of the original problem */ 340 SCIP_VAR** subvars, /**< variables of the DINS sub-SCIP */ 341 int nbinvars, /**< number of binary variables of problem and subproblem */ 342 int nintvars /**< number of general integer variables of problem and subproblem */ 343 ) 344 { 345 int i; 346 /* compute a tighter bound for the variable in the subproblem; */ 347 for( i = nbinvars; i < nbinvars + nintvars; ++i ) 348 { 349 SCIP_Real lb; 350 SCIP_Real ub; 351 352 if( subvars[i] == NULL ) 353 continue; 354 355 computeIntegerVariableBounds(scip, vars[i], &lb, &ub); 356 357 /* change variable bounds in the DINS subproblem; if bounds coincide, variable should already be fixed */ 358 if( ub - lb >= 0.5 ) 359 { 360 SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], lb) ); 361 SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], ub) ); 362 } 363 else 364 { 365 assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(subvars[i]), SCIPvarGetUbGlobal(subvars[i]))); 366 } 367 } 368 369 return SCIP_OKAY; 370 } 371 372 /** create the extra constraint of local branching and add it to subscip */ 373 static 374 SCIP_RETCODE addLocalBranchingConstraint( 375 SCIP* scip, /**< SCIP data structure of the original problem */ 376 SCIP* subscip, /**< SCIP data structure of the subproblem */ 377 SCIP_VAR** subvars, /**< variables of the subproblem */ 378 SCIP_HEURDATA* heurdata /**< heuristic's data structure */ 379 ) 380 { 381 SCIP_CONS* cons; /* local branching constraint to create */ 382 SCIP_VAR** vars; 383 SCIP_SOL* bestsol; 384 385 SCIP_VAR** consvars; 386 SCIP_Real* consvals; 387 SCIP_Real solval; 388 SCIP_Real lhs; 389 SCIP_Real rhs; 390 391 char consname[SCIP_MAXSTRLEN]; 392 393 int nbinvars; 394 int i; 395 int nconsvars; 396 397 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_dinsLBcons", SCIPgetProbName(scip)); 398 399 /* get the data of the variables and the best solution */ 400 SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, NULL, NULL, NULL) ); 401 bestsol = SCIPgetBestSol(scip); 402 assert(bestsol != NULL); 403 404 /* memory allocation */ 405 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nbinvars) ); 406 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nbinvars) ); 407 nconsvars = 0; 408 409 /* set initial left and right hand sides of local branching constraint */ 410 lhs = 0.0; 411 rhs = (SCIP_Real) heurdata->neighborhoodsize; 412 413 /* create the distance function of the binary variables (to incumbent solution) */ 414 for( i = 0; i < nbinvars; i++ ) 415 { 416 if( subvars[i] == NULL ) 417 continue; 418 419 assert(SCIPvarGetType(subvars[i]) == SCIP_VARTYPE_BINARY); 420 if( SCIPvarGetUbGlobal(subvars[i]) - SCIPvarGetLbGlobal(subvars[i]) < 0.5 ) 421 continue; 422 423 solval = SCIPgetSolVal(scip, bestsol, vars[i]); 424 assert(SCIPisFeasIntegral(scip, solval)); 425 426 /* is variable i part of the binary support of the current solution? */ 427 if( SCIPisFeasEQ(scip, solval, 1.0) ) 428 { 429 consvals[nconsvars] = -1.0; 430 rhs -= 1.0; 431 lhs -= 1.0; 432 } 433 else 434 consvals[nconsvars] = 1.0; 435 consvars[nconsvars++] = subvars[i]; 436 } 437 438 /* creates local branching constraint and adds it to subscip */ 439 SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, consname, nconsvars, consvars, consvals, 440 lhs, rhs, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) ); 441 SCIP_CALL( SCIPaddCons(subscip, cons) ); 442 SCIP_CALL( SCIPreleaseCons(subscip, &cons) ); 443 444 /* free local memory */ 445 SCIPfreeBufferArray(scip, &consvars); 446 SCIPfreeBufferArray(scip, &consvals); 447 448 return SCIP_OKAY; 449 } 450 451 static 452 SCIP_DECL_EVENTEXEC(eventExecDins); 453 454 /** wrapper for the part of heuristic that runs a subscip. Wrapper is needed to avoid possible ressource leaks */ 455 static 456 SCIP_RETCODE wrapperDins( 457 SCIP* scip, /**< original SCIP data structure */ 458 SCIP* subscip, /**< SCIP structure of the subproblem */ 459 SCIP_HEUR* heur, /**< Heuristic pointer */ 460 SCIP_HEURDATA* heurdata, /**< Heuristic's data */ 461 SCIP_VAR** vars, /**< original problem's variables */ 462 SCIP_VAR** fixedvars, /**< Fixed variables of original SCIP */ 463 SCIP_Real* fixedvals, /**< Fixed values of original SCIP */ 464 SCIP_RESULT* result, /**< Result pointer */ 465 int nvars, /**< Number of variables */ 466 int nbinvars, /**< Number of binary variables in original SCIP */ 467 int nintvars, /**< Number of integer variables in original SCIP */ 468 int binfixings, /**< Number of binary fixing in original SCIP */ 469 int intfixings, /**< Number of integer fixings in original SCIP */ 470 SCIP_Longint nsubnodes /**< Number of nodes in the subscip */ 471 ) 472 { 473 SCIP_VAR** subvars; /* variables of the subscip */ 474 SCIP_HASHMAP* varmapfw; /* hashmap for mapping between vars of scip and subscip */ 475 SCIP_EVENTHDLR* eventhdlr; /* event handler for LP events */ 476 SCIP_Real upperbound; /* upperbound of the original SCIP */ 477 SCIP_Real cutoff; /* objective cutoff for the subproblem */ 478 479 SCIP_Bool success; 480 481 int i; 482 int nsubsols; 483 484 /* create the variable mapping hash map */ 485 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) ); 486 SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) ); 487 488 success = FALSE; 489 eventhdlr = NULL; 490 491 /* create a problem copy as sub SCIP */ 492 SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "dins", fixedvars, fixedvals, binfixings + intfixings, 493 heurdata->uselprows, heurdata->copycuts, &success, NULL) ); 494 495 /* create event handler for LP events */ 496 SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecDins, NULL) ); 497 if( eventhdlr == NULL ) 498 { 499 SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n"); 500 return SCIP_PLUGINNOTFOUND; 501 } 502 503 SCIPdebugMsg(scip, "Copying the SCIP instance was %ssuccessful.\n", success ? "" : "not "); 504 505 SCIPdebugMsg(scip, "DINS subproblem: %d vars (%d binvars & %d intvars), %d cons\n", 506 SCIPgetNVars(subscip), SCIPgetNBinVars(subscip) , SCIPgetNIntVars(subscip) , SCIPgetNConss(subscip)); 507 508 /* store subproblem variables that correspond to original variables */ 509 for( i = 0; i < nvars; i++ ) 510 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]); 511 512 /* free hash map */ 513 SCIPhashmapFree(&varmapfw); 514 515 /* perform prepared softfixing for all unfixed vars if the number of unfixed vars is larger than the neighborhoodsize (otherwise it will be useless) */ 516 if( nbinvars - binfixings > heurdata->neighborhoodsize ) 517 { 518 SCIP_CALL( addLocalBranchingConstraint(scip, subscip, subvars, heurdata) ); 519 } 520 521 /* rebound integer variables if not all were fixed */ 522 if( intfixings < nintvars ) 523 { 524 assert(nintvars > 0); 525 SCIP_CALL( reboundIntegerVariables(scip, subscip, vars, subvars, nbinvars, nintvars) ); 526 } 527 528 /* do not abort subproblem on CTRL-C */ 529 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) ); 530 531 #ifdef SCIP_DEBUG 532 /* for debugging, enable full output */ 533 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) ); 534 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) ); 535 #else 536 /* disable statistic timing inside sub SCIP and output to console */ 537 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) ); 538 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) ); 539 #endif 540 541 /* set limits for the subproblem */ 542 SCIP_CALL( SCIPcopyLimits(scip, subscip) ); 543 heurdata->nodelimit = nsubnodes; 544 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nsubnodes) ); 545 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", MAX(10, nsubnodes/10)) ); 546 SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->bestsollimit) ); 547 548 /* forbid recursive call of heuristics and separators solving subMIPs */ 549 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) ); 550 551 /* disable cutting plane separation */ 552 SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) ); 553 554 /* disable expensive presolving */ 555 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) ); 556 557 /* use best estimate node selection */ 558 if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") ) 559 { 560 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) ); 561 } 562 563 /* activate uct node selection at the top of the tree */ 564 if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") ) 565 { 566 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) ); 567 } 568 569 /* use inference branching */ 570 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") ) 571 { 572 SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) ); 573 } 574 575 /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */ 576 if( !SCIPisParamFixed(subscip, "conflict/enable") ) 577 { 578 SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) ); 579 } 580 if( !SCIPisParamFixed(subscip, "conflict/useboundlp") ) 581 { 582 SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') ); 583 } 584 if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") ) 585 { 586 SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) ); 587 } 588 589 /* speed up sub-SCIP by not checking dual LP feasibility */ 590 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) ); 591 592 /* add an objective cutoff */ 593 assert(!SCIPisInfinity(scip, SCIPgetUpperbound(scip))); 594 595 if( !SCIPisInfinity(scip, -1.0*SCIPgetLowerbound(scip)) ) 596 { 597 cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip) + heurdata->minimprove * SCIPgetLowerbound(scip); 598 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip); 599 cutoff = MIN(upperbound, cutoff); 600 } 601 else 602 { 603 if( SCIPgetUpperbound(scip) >= 0 ) 604 cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip); 605 else 606 cutoff = (1 + heurdata->minimprove) * SCIPgetUpperbound(scip); 607 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip); 608 cutoff = MIN(upperbound, cutoff); 609 } 610 SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) ); 611 612 /* catch LP events of sub-SCIP */ 613 if( !heurdata->uselprows ) 614 { 615 assert(eventhdlr != NULL); 616 617 SCIP_CALL( SCIPtransformProb(subscip) ); 618 SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) ); 619 } 620 621 /* solve the subproblem */ 622 SCIPdebugMsg(scip, "solving DINS sub-MIP with neighborhoodsize %d and maxnodes %" SCIP_LONGINT_FORMAT "\n", heurdata->neighborhoodsize, nsubnodes); 623 624 /* Errors in solving the subproblem should not kill the overall solving process 625 * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. 626 */ 627 SCIP_CALL_ABORT( SCIPsolve(subscip) ); 628 629 /* drop LP events of sub-SCIP */ 630 if( !heurdata->uselprows ) 631 { 632 assert(eventhdlr != NULL); 633 634 SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) ); 635 } 636 637 /* print solving statistics of subproblem if we are in SCIP's debug mode */ 638 SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) ); 639 640 heurdata->usednodes += SCIPgetNNodes(subscip); 641 nsubsols = SCIPgetNSols(subscip); 642 SCIPdebugMsg(scip, "DINS used %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT " nodes and found %d solutions\n", SCIPgetNNodes(subscip), nsubnodes, nsubsols); 643 644 /* check, whether a (new) solution was found */ 645 if( nsubsols > 0 ) 646 { 647 /* check, whether a solution was found; due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted */ 648 SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, &success, NULL) ); 649 if( success ) 650 { 651 SCIPdebugMsg(scip, "DINS successfully found new solution\n"); 652 *result = SCIP_FOUNDSOL; 653 } 654 } 655 656 /* free subproblem */ 657 SCIPfreeBufferArray(scip, &subvars); 658 659 return SCIP_OKAY; 660 } 661 662 663 /* ---------------- Callback methods of event handler ---------------- */ 664 665 /* exec the event handler 666 * 667 * we interrupt the solution process 668 */ 669 static 670 SCIP_DECL_EVENTEXEC(eventExecDins) 671 { 672 SCIP_HEURDATA* heurdata; 673 674 assert(eventhdlr != NULL); 675 assert(eventdata != NULL); 676 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0); 677 assert(event != NULL); 678 assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_LPSOLVED); 679 680 heurdata = (SCIP_HEURDATA*)eventdata; 681 assert(heurdata != NULL); 682 683 /* interrupt solution process of sub-SCIP */ 684 if( SCIPgetNLPs(scip) > heurdata->lplimfac * heurdata->nodelimit ) 685 { 686 SCIPdebugMsg(scip, "interrupt after %" SCIP_LONGINT_FORMAT " LPs\n",SCIPgetNLPs(scip)); 687 SCIP_CALL( SCIPinterruptSolve(scip) ); 688 } 689 690 return SCIP_OKAY; 691 } 692 693 694 /* 695 * Callback methods of primal heuristic 696 */ 697 698 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 699 static 700 SCIP_DECL_HEURCOPY(heurCopyDins) 701 { /*lint --e{715}*/ 702 assert(scip != NULL); 703 assert(heur != NULL); 704 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 705 706 /* call inclusion method of primal heuristic */ 707 SCIP_CALL( SCIPincludeHeurDins(scip) ); 708 709 return SCIP_OKAY; 710 } 711 712 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 713 static 714 SCIP_DECL_HEURFREE(heurFreeDins) 715 { /*lint --e{715}*/ 716 SCIP_HEURDATA* heurdata; 717 718 assert(heur != NULL); 719 assert(scip != NULL); 720 721 /* get heuristic data */ 722 heurdata = SCIPheurGetData(heur); 723 assert(heurdata != NULL); 724 725 /* free heuristic data */ 726 SCIPfreeBlockMemory(scip, &heurdata); 727 SCIPheurSetData(heur, NULL); 728 729 return SCIP_OKAY; 730 } 731 732 733 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */ 734 static 735 SCIP_DECL_HEURINITSOL(heurInitsolDins) 736 { 737 SCIP_HEURDATA* heurdata; 738 int i; 739 740 assert(heur != NULL); 741 assert(scip != NULL); 742 743 /* get heuristic's data */ 744 heurdata = SCIPheurGetData(heur); 745 assert(heurdata != NULL); 746 747 /* initialize data */ 748 heurdata->usednodes = 0; 749 heurdata->lastnsolsfound = 0; 750 751 /* create flag array */ 752 heurdata->deltalength = SCIPgetNBinVars(scip); 753 754 /* no binvars => no flag array needed */ 755 if( heurdata->deltalength > 0 ) 756 { 757 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(heurdata->delta), heurdata->deltalength) ); 758 for( i = 0; i < heurdata->deltalength; i++ ) 759 heurdata->delta[i] = TRUE; 760 } 761 return SCIP_OKAY; 762 } 763 764 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */ 765 static 766 SCIP_DECL_HEUREXITSOL(heurExitsolDins) 767 { /*lint --e{715}*/ 768 SCIP_HEURDATA* heurdata; 769 770 assert(heur != NULL); 771 assert(scip != NULL); 772 773 /* get heuristic data */ 774 heurdata = SCIPheurGetData(heur); 775 assert(heurdata != NULL); 776 777 /* free flag array if exist */ 778 if( heurdata->deltalength > 0 ) 779 { 780 SCIPfreeBlockMemoryArray(scip, &(heurdata->delta), heurdata->deltalength); 781 } 782 return SCIP_OKAY; 783 } 784 785 /** execution method of primal heuristic */ 786 static 787 SCIP_DECL_HEUREXEC(heurExecDins) 788 { /*lint --e{715}*/ 789 SCIP_HEURDATA* heurdata; 790 SCIP* subscip; /* the subproblem created by DINS */ 791 SCIP_VAR** vars; /* variables of the original problem */ 792 SCIP_VAR** fixedvars; 793 SCIP_Real* fixedvals; 794 795 SCIP_Longint maxnnodes; /* maximum number of subnodes */ 796 SCIP_Longint nsubnodes; /* nodelimit for subscip */ 797 798 SCIP_RETCODE retcode; 799 800 int nvars; /* number of variables in original SCIP */ 801 int nbinvars; /* number of binary variables in original SCIP */ 802 int nintvars; /* number of general integer variables in original SCIP */ 803 int binfixings; 804 int intfixings; 805 806 SCIP_Bool success; /* used to store whether new solution was found or not */ 807 808 assert(heur != NULL); 809 assert(scip != NULL); 810 assert(result != NULL); 811 assert(SCIPhasCurrentNodeLP(scip)); 812 813 *result = SCIP_DELAYED; 814 815 /* do not call heuristic of node was already detected to be infeasible */ 816 if( nodeinfeasible ) 817 return SCIP_OKAY; 818 819 /* only call heuristic, if a CIP solution is at hand */ 820 if( SCIPgetNSols(scip) <= 0 ) 821 return SCIP_OKAY; 822 823 /* only call heuristic, if an optimal LP solution is at hand */ 824 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL ) 825 return SCIP_OKAY; 826 827 /* only call heuristic, if the LP objective value is smaller than the cutoff bound */ 828 if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) ) 829 return SCIP_OKAY; 830 831 /* get heuristic's data */ 832 heurdata = SCIPheurGetData(heur); 833 assert(heurdata != NULL); 834 835 /* only call heuristic, if enough nodes were processed since last incumbent */ 836 if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip, SCIPgetBestSol(scip)) < heurdata->nwaitingnodes ) 837 return SCIP_OKAY; 838 839 *result = SCIP_DIDNOTRUN; 840 841 /* determine the node limit for the current process */ 842 maxnnodes = (SCIP_Longint) (heurdata->nodesquot * SCIPgetNNodes(scip)); 843 844 /* reward DINS if it succeeded often */ 845 maxnnodes = (SCIP_Longint) (maxnnodes * (1.0 + 2.0 * (SCIPheurGetNBestSolsFound(heur)+1.0) / (SCIPheurGetNCalls(heur) + 1.0))); 846 847 /* count the setup costs for the sub-MIP as 100 nodes */ 848 maxnnodes -= 100 * SCIPheurGetNCalls(heur); 849 maxnnodes += heurdata->nodesofs; 850 851 /* determine the node limit for the current process */ 852 nsubnodes = maxnnodes - heurdata->usednodes; 853 nsubnodes = MIN(nsubnodes , heurdata->maxnodes); 854 855 /* check whether we have enough nodes left to call sub problem solving */ 856 if( nsubnodes < heurdata->minnodes ) 857 return SCIP_OKAY; 858 859 if( SCIPisStopped(scip) ) 860 return SCIP_OKAY; 861 862 /* get required data of the original problem */ 863 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) ); 864 assert(nbinvars <= nvars); 865 866 /* do not run heuristic if only continuous variables are present */ 867 if( nbinvars == 0 && nintvars == 0 ) 868 return SCIP_OKAY; 869 870 /* check whether there is enough time and memory left */ 871 SCIP_CALL( SCIPcheckCopyLimits(scip, &success) ); 872 873 /* abort if no time is left or not enough memory to create a copy of SCIP */ 874 if( !success ) 875 return SCIP_OKAY; 876 877 assert(vars != NULL); 878 879 SCIP_CALL( SCIPallocBufferArray(scip, &fixedvars, nbinvars + nintvars) ); 880 SCIP_CALL( SCIPallocBufferArray(scip, &fixedvals, nbinvars + nintvars) ); 881 882 /* collect variables that should be fixed in the DINS subproblem */ 883 binfixings = intfixings = 0; 884 SCIP_CALL( determineVariableFixings(scip, heur, heurdata, vars, fixedvars, fixedvals, nbinvars, nintvars, &binfixings, &intfixings) ); 885 886 /* abort, if all integer variables were fixed (which should not happen for MIP), 887 * but frequently happens for MINLPs using an LP relaxation */ 888 if( binfixings + intfixings == nbinvars + nintvars ) 889 goto TERMINATE; 890 891 /* abort, if the amount of fixed variables is insufficient */ 892 if( (binfixings + intfixings) / (SCIP_Real)(MAX(nbinvars + nintvars, 1)) < heurdata->minfixingrate ) 893 goto TERMINATE; 894 895 *result = SCIP_DIDNOTFIND; 896 897 /* initialize the subproblem */ 898 SCIP_CALL( SCIPcreate(&subscip) ); 899 900 retcode = wrapperDins(scip, subscip, heur, heurdata, vars, fixedvars, fixedvals, result, nvars, nbinvars, nintvars, binfixings, intfixings, nsubnodes); 901 SCIP_CALL( SCIPfree(&subscip) ); 902 903 SCIP_CALL( retcode ); 904 905 TERMINATE: 906 SCIPfreeBufferArray(scip, &fixedvals); 907 SCIPfreeBufferArray(scip, &fixedvars); 908 909 return SCIP_OKAY; 910 } 911 912 913 /* 914 * primal heuristic specific interface methods 915 */ 916 917 /** creates the DINS primal heuristic and includes it in SCIP */ 918 SCIP_RETCODE SCIPincludeHeurDins( 919 SCIP* scip /**< SCIP data structure */ 920 ) 921 { 922 SCIP_HEURDATA* heurdata; 923 SCIP_HEUR* heur; 924 925 /* create Dins primal heuristic data */ 926 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 927 928 /* include primal heuristic */ 929 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 930 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 931 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecDins, heurdata) ); 932 933 assert(heur != NULL); 934 935 /* set non-NULL pointers to callback methods */ 936 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyDins) ); 937 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeDins) ); 938 SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolDins) ); 939 SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolDins) ); 940 941 /* add DINS primal heuristic parameters */ 942 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs", 943 "number of nodes added to the contingent of the total nodes", 944 &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 945 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot", 946 "contingent of sub problem nodes in relation to the number of nodes of the original problem", 947 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) ); 948 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes", 949 "minimum number of nodes required to start the subproblem", 950 &heurdata->minnodes, FALSE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 951 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/solnum", 952 "number of pool-solutions to be checked for flag array update (for hard fixing of binary variables)", 953 &heurdata->solnum, FALSE, DEFAULT_SOLNUM, 1, INT_MAX, NULL, NULL) ); 954 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/neighborhoodsize", 955 "radius (using Manhattan metric) of the incumbent's neighborhood to be searched", 956 &heurdata->neighborhoodsize, FALSE, DEFAULT_NEIGHBORHOODSIZE, 1, INT_MAX, NULL, NULL) ); 957 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes", 958 "maximum number of nodes to regard in the subproblem", 959 &heurdata->maxnodes,TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 960 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove", 961 "factor by which " HEUR_NAME " should at least improve the incumbent", 962 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) ); 963 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nwaitingnodes", 964 "number of nodes without incumbent change that heuristic should wait", 965 &heurdata->nwaitingnodes, TRUE, DEFAULT_NWAITINGNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 966 967 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lplimfac", 968 "factor by which the limit on the number of LP depends on the node limit", 969 &heurdata->lplimfac, TRUE, DEFAULT_LPLIMFAC, 1.0, SCIP_REAL_MAX, NULL, NULL) ); 970 971 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate", 972 "minimum percentage of integer variables that have to be fixable", 973 &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) ); 974 975 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows", 976 "should subproblem be created out of the rows in the LP rows?", 977 &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) ); 978 979 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts", 980 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?", 981 &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) ); 982 983 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct", 984 "should uct node selection be used at the beginning of the search?", 985 &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) ); 986 987 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/bestsollimit", 988 "limit on number of improving incumbent solutions in sub-CIP", 989 &heurdata->bestsollimit, FALSE, DEFAULT_BESTSOLLIMIT, -1, INT_MAX, NULL, NULL) ); 990 991 return SCIP_OKAY; 992 } 993