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_lpface.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief lpface primal heuristic that searches the optimal LP face inside a sub-MIP 28 * @author Gregor Hendel 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/scipdefplugins.h" 36 #include "scip/heur_lpface.h" 37 #include "scip/pub_event.h" 38 #include "scip/pub_heur.h" 39 #include "scip/pub_lp.h" 40 #include "scip/pub_message.h" 41 #include "scip/pub_misc.h" 42 #include "scip/pub_sol.h" 43 #include "scip/pub_tree.h" 44 #include "scip/pub_var.h" 45 #include "scip/scip_branch.h" 46 #include "scip/scip_cons.h" 47 #include "scip/scip_copy.h" 48 #include "scip/scip_event.h" 49 #include "scip/scip_general.h" 50 #include "scip/scip_heur.h" 51 #include "scip/scip_lp.h" 52 #include "scip/scip_mem.h" 53 #include "scip/scip_message.h" 54 #include "scip/scip_nodesel.h" 55 #include "scip/scip_numerics.h" 56 #include "scip/scip_param.h" 57 #include "scip/scip_prob.h" 58 #include "scip/scip_sol.h" 59 #include "scip/scip_solve.h" 60 #include "scip/scip_solvingstats.h" 61 #include "scip/scip_timing.h" 62 #include "scip/scip_tree.h" 63 #include "scip/scip_var.h" 64 #include <string.h> 65 66 #define HEUR_NAME "lpface" 67 #define HEUR_DESC "LNS heuristic that searches the optimal LP face inside a sub-MIP" 68 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS 69 #define HEUR_PRIORITY -1104010 70 #define HEUR_FREQ 15 71 #define HEUR_FREQOFS 0 72 #define HEUR_MAXDEPTH -1 73 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE 74 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */ 75 76 #define DEFAULT_MAXNODES 5000LL /**< maximum number of nodes to regard in the subproblem */ 77 #define DEFAULT_MINNODES 50LL /**< minimum number of nodes to regard in the subproblem */ 78 #define DEFAULT_MINFIXINGRATE 0.1 /**< required percentage of fixed integer variables in sub-MIP to run */ 79 #define DEFAULT_NODESOFS 200LL /**< 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_USELPROWS TRUE /**< 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 uselprows == FALSE, should all active cuts from cutpool be copied 85 * to constraints in subproblem? */ 86 #define DEFAULT_DUALBASISEQUATIONS FALSE /**< should the dually nonbasic rows be turned into equations? */ 87 #define DEFAULT_KEEPSUBSCIP FALSE /**< should the heuristic continue solving the same sub-SCIP? */ 88 #define DEFAULT_MINPATHLEN 5 /**< the minimum active search tree path length along which the lower bound 89 * hasn't changed before heuristic becomes active */ 90 /* event handler properties */ 91 #define EVENTHDLR_NAME "Lpface" 92 #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" 93 94 /* 95 * Data structures 96 */ 97 98 /** data structure to keep sub-SCIP across runs */ 99 struct SubscipData 100 { 101 SCIP* subscip; /**< pointer to store sub-SCIP data structure */ 102 SCIP_VAR** subvars; /**< array of variables of the sub-problem */ 103 int nsubvars; /**< number of sub-problem variables */ 104 SCIP_Real objbound; /**< lower bound on objective for when sub SCIP was created */ 105 }; 106 typedef struct SubscipData SUBSCIPDATA; 107 108 /** primal heuristic data */ 109 struct SCIP_HeurData 110 { 111 SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */ 112 SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */ 113 SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */ 114 SCIP_Longint usednodes; /**< nodes already used by lpface in earlier calls */ 115 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */ 116 117 unsigned int nfailures; /**< number of failures since last successful call */ 118 SCIP_Longint nextnodenumber; /**< number of nodes at which lpface should be called the next time */ 119 SCIP_Real lastlpobjinfeas; /**< last LP objective where the sub-MIP was run to proven infeasibility */ 120 SCIP_Real minfixingrate; /**< required percentage of fixed integer variables in sub-MIP to run */ 121 SCIP_Real nodelimit; /**< the nodelimit employed in the current sub-SCIP, for the event handler*/ 122 SCIP_Real lplimfac; /**< factor by which the limit on the number of LP depends on the node limit */ 123 SCIP_Bool uselprows; /**< should subproblem be created out of the rows in the LP rows? */ 124 SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied 125 * to constraints in subproblem? */ 126 SCIP_Bool dualbasisequations; /**< should the dually nonbasic rows be turned into equations? */ 127 SCIP_Bool keepsubscip; /**< should the heuristic continue solving the same sub-SCIP? */ 128 char subscipobjective; /**< objective function in the sub-SCIP: (z)ero, (r)oot-LP-difference, 129 * (i)nference, LP (f)ractionality, (o)riginal */ 130 131 SCIP_STATUS submipstatus; /**< return status of the sub-MIP */ 132 SCIP_Longint submipnlpiters; /**< number of LP iterations of the sub-MIP */ 133 SCIP_Real submippresoltime; /**< time required to presolve the sub-MIP */ 134 int nvarsfixed; /**< the number of fixed variables by the heuristic */ 135 int minpathlen; /**< the minimum active search tree path length along which the lower bound 136 * hasn't changed before heuristic becomes active */ 137 SUBSCIPDATA* subscipdata; /**< sub-SCIP data structure */ 138 }; 139 140 /* 141 * Local methods 142 */ 143 144 /** determine variable fixings for sub-SCIP based on reduced costs */ 145 static 146 SCIP_RETCODE determineVariableFixings( 147 SCIP* scip, /**< SCIP data structure */ 148 SCIP_HEURDATA* heurdata, /**< primal heuristic data */ 149 SCIP_VAR** fixvars, /**< buffer to store variables that should be fixed */ 150 SCIP_Real* fixvals, /**< buffer to store corresponding fixing values */ 151 int* nfixvars, /**< pointer to store number of variables that should be fixed */ 152 SCIP_Bool* success /**< pointer to store whether enough integer variables were fixed */ 153 ) 154 { 155 SCIP_VAR** vars; /* original scip variables */ 156 SCIP_Real fixingrate; /* percentage of variables that are fixed */ 157 int nvars; 158 int nbinvars; 159 int nintvars; 160 int i; 161 int fixingcounter; 162 163 /* get required data of the main scip problem */ 164 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) ); 165 166 fixingcounter = 0; 167 168 assert(nvars >= nbinvars + nintvars); 169 170 *nfixvars = 0; 171 /* loop over problem variables and fix all with nonzero reduced costs to their solution value */ 172 for( i = 0; i < nvars; i++ ) 173 { 174 SCIP_Real solval; 175 SCIP_COL* col; 176 SCIP_Real redcost; 177 SCIP_Real lbglobal; 178 SCIP_Real ubglobal; 179 SCIP_VAR* var; 180 181 var = vars[i]; 182 183 /* skip non-column variables */ 184 if( SCIPvarGetStatus(var) != SCIP_VARSTATUS_COLUMN ) 185 continue; 186 187 /* skip relaxation only variables */ 188 if( SCIPvarIsRelaxationOnly(var) ) 189 continue; 190 191 solval = SCIPgetSolVal(scip, NULL, var); 192 col = SCIPvarGetCol(vars[i]); 193 assert(col != NULL); 194 redcost = SCIPgetColRedcost(scip, col); 195 lbglobal = SCIPvarGetLbGlobal(var); 196 ubglobal = SCIPvarGetUbGlobal(var); 197 198 /* fix the variable to its solution value if variable is nonbasic (i.e., at one of its bounds) 199 * with nonzero reduced costs 200 */ 201 if( ! SCIPisDualfeasZero(scip, redcost) ) 202 { 203 /* fix variable based on reduced cost information, respecting global bounds */ 204 if( (redcost > 0 && SCIPisFeasEQ(scip, solval, lbglobal)) || 205 (redcost < 0 && SCIPisFeasEQ(scip, solval, ubglobal)) ) 206 { 207 assert(! SCIPisInfinity(scip, REALABS(solval))); 208 209 fixvars[*nfixvars] = var; 210 fixvals[*nfixvars] = solval; 211 212 if( SCIPvarIsIntegral(var) ) 213 ++fixingcounter; 214 215 ++(*nfixvars); 216 } 217 } 218 } 219 220 fixingrate = (SCIP_Real)fixingcounter / (SCIP_Real)(MAX(nbinvars + nintvars, 1)); 221 heurdata->nvarsfixed = fixingcounter; 222 223 /* if all variables were fixed or amount of fixed variables is insufficient, skip residual part of 224 * subproblem creation and abort immediately 225 */ 226 *success = (fixingcounter < nvars && fixingrate >= heurdata->minfixingrate); 227 228 SCIPdebugMsg(scip, " LP face heuristic fixed %senough variables (%d out of %d)\n", 229 *success ? "": "not ", fixingcounter, nvars); 230 231 return SCIP_OKAY; 232 } 233 234 /** creates the rows of the subproblem */ 235 static 236 SCIP_RETCODE createRows( 237 SCIP* scip, /**< original SCIP data structure */ 238 SCIP* subscip, /**< SCIP data structure for the subproblem */ 239 SCIP_VAR** subvars, /**< the variables of the subproblem */ 240 SCIP_Bool dualbasisequations /**< should the dually nonbasic rows be turned into equations? */ 241 ) 242 { 243 SCIP_ROW** rows; /* original scip rows */ 244 245 int nrows; 246 int i; 247 248 /* get the rows and their number */ 249 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) ); 250 251 /* copy all global rows to linear constraints, unless they contain relaxation-only variables */ 252 for( i = 0; i < nrows; i++ ) 253 { 254 SCIP_VAR** consvars; /* new constraint's variables */ 255 SCIP_COL** cols; /* original row's columns */ 256 SCIP_CONS* cons; /* new constraint */ 257 258 SCIP_Real* vals; /* variables' coefficient values of the row */ 259 SCIP_Real constant; /* constant added to the row */ 260 SCIP_Real lhs; /* left hand side of the row */ 261 SCIP_Real rhs; /* left right side of the row */ 262 SCIP_Real dualsol; 263 SCIP_Real rowsolactivity; 264 int j; 265 int nnonz; 266 267 /* ignore rows that are only locally valid */ 268 if( SCIProwIsLocal(rows[i]) ) 269 continue; 270 271 /* get the row's data */ 272 constant = SCIProwGetConstant(rows[i]); 273 vals = SCIProwGetVals(rows[i]); 274 nnonz = SCIProwGetNNonz(rows[i]); 275 cols = SCIProwGetCols(rows[i]); 276 277 /* only subtract constant if left hand side is not infinite */ 278 lhs = SCIProwGetLhs(rows[i]); 279 if( ! SCIPisInfinity(scip, -lhs) ) 280 lhs -= constant; 281 282 /* only subtract constant if right hand side is not infinite */ 283 rhs = SCIProwGetRhs(rows[i]); 284 if( ! SCIPisInfinity(scip, rhs) ) 285 rhs -= constant; 286 287 assert(lhs <= rhs); 288 289 /* allocate memory array to be filled with the corresponding subproblem variables */ 290 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nnonz) ); 291 for( j = 0; j < nnonz; j++ ) 292 { 293 consvars[j] = subvars[SCIPvarGetProbindex(SCIPcolGetVar(cols[j]))]; 294 if( consvars[j] == NULL ) 295 break; 296 } 297 /* skip row if not all variables are in sub-SCIP, i.e., relaxation-only variables */ 298 if( j < nnonz ) 299 { 300 SCIPfreeBufferArray(scip, &consvars); 301 continue; 302 } 303 304 dualsol = SCIProwGetDualsol(rows[i]); 305 rowsolactivity = SCIPgetRowActivity(scip, rows[i]); 306 307 /* transform into equation if the row is sharp and has a nonzero dual solution */ 308 if( dualbasisequations && ! SCIPisDualfeasZero(scip, dualsol) ) 309 { 310 if( dualsol > 0.0 && SCIPisFeasEQ(scip, rowsolactivity, lhs) ) 311 rhs = lhs; 312 else if( dualsol < 0.0 && SCIPisFeasEQ(scip, rowsolactivity, rhs) ) 313 lhs = rhs; 314 } 315 316 /* create a new linear constraint and add it to the subproblem */ 317 SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, SCIProwGetName(rows[i]), nnonz, consvars, vals, lhs, rhs, 318 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) ); 319 SCIP_CALL( SCIPaddCons(subscip, cons) ); 320 SCIP_CALL( SCIPreleaseCons(subscip, &cons) ); 321 322 /* free temporary memory */ 323 SCIPfreeBufferArray(scip, &consvars); 324 } 325 326 return SCIP_OKAY; 327 } 328 329 /** create the LP face subproblem constraints */ 330 static 331 SCIP_RETCODE setupSubproblem( 332 SCIP* scip, /**< original SCIP data structure */ 333 SCIP* subscip, /**< SCIP data structure for the subproblem */ 334 SCIP_VAR** subvars, /**< the variables of the subproblem */ 335 SCIP_HEURDATA* heurdata /**< primal heuristic data */ 336 ) 337 { 338 SCIP_VAR** vars = SCIPgetVars(scip); 339 int nvars = SCIPgetNVars(scip); 340 SCIP_Real lowerbound; 341 SCIP_CONS* origobjcons; 342 int i; 343 #ifndef NDEBUG 344 int nobjvars = 0; 345 #endif 346 347 /* we copy the rows of the LP, if enough variables could be fixed and we work on the MIP relaxation of the problem */ 348 if( heurdata->uselprows ) 349 { 350 SCIP_CALL( createRows(scip, subscip, subvars, heurdata->dualbasisequations) ); 351 } 352 353 /* add an equation that the objective function must be equal to the lower bound */ 354 lowerbound = SCIPgetLowerbound(scip); 355 356 SCIP_CALL( SCIPcreateConsLinear(subscip, &origobjcons, "objbound_of_origscip", 0, NULL, NULL, lowerbound, lowerbound, 357 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 358 359 for( i = 0; i < nvars; ++i) 360 { 361 if( ! SCIPisZero(subscip, SCIPvarGetObj(vars[i])) ) 362 { 363 assert(subvars[i] != NULL); /* a relaxation-only variable cannot have an objective coefficient */ 364 SCIP_CALL( SCIPaddCoefLinear(subscip, origobjcons, subvars[i], SCIPvarGetObj(vars[i])) ); 365 #ifndef NDEBUG 366 nobjvars++; 367 #endif 368 } 369 } 370 assert(nobjvars == SCIPgetNObjVars(scip)); 371 372 SCIP_CALL( SCIPaddCons(subscip, origobjcons) ); 373 SCIP_CALL( SCIPreleaseCons(subscip, &origobjcons) ); 374 375 return SCIP_OKAY; 376 } 377 378 /** updates heurdata after an unsuccessful run of lpface */ 379 static 380 void updateFailureStatistic( 381 SCIP* scip, /**< original SCIP data structure */ 382 SCIP_HEURDATA* heurdata /**< primal heuristic data */ 383 ) 384 { 385 /* increase number of failures, calculate next node at which lpface should be called and update actual solutions */ 386 heurdata->nfailures++; 387 heurdata->nextnodenumber = (heurdata->nfailures <= 25 388 ? SCIPgetNNodes(scip) + 100*(2LL << heurdata->nfailures) /*lint !e703*/ 389 : SCIP_LONGINT_MAX); 390 } 391 392 /** calculate a node limit based on node limiting parameters of the heuristic */ 393 static 394 SCIP_Longint calcNodeLimit( 395 SCIP* scip, /**< (original) SCIP data structure */ 396 SCIP_HEUR* heur, /**< LP face heuristic */ 397 SCIP_HEURDATA* heurdata /**< primal heuristic data */ 398 ) 399 { 400 SCIP_Longint nodelimit; 401 402 /* calculate the maximal number of branching nodes until heuristic is aborted */ 403 nodelimit = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip)); 404 405 /* count the setup costs for the sub-MIP as 100 nodes */ 406 nodelimit -= 100 * SCIPheurGetNCalls(heur); 407 408 /* add the offset */ 409 nodelimit += heurdata->nodesofs; 410 411 /* subtract previously used nodes */ 412 nodelimit -= heurdata->usednodes; 413 414 /* do not use more than the maximum number of allowed nodes in one run */ 415 nodelimit = MIN(nodelimit, heurdata->maxnodes); 416 417 /* if the subscip has been kept from a previous run, add the number of already processed nodes */ 418 if( heurdata->subscipdata->subscip != NULL ) 419 nodelimit += SCIPgetNNodes(heurdata->subscipdata->subscip); 420 421 return nodelimit; 422 } 423 424 /** sets node, time, and memory limit according to the parameter settings of the heuristic */ 425 static 426 SCIP_RETCODE setSubscipLimits( 427 SCIP* scip, /**< original SCIP data structure */ 428 SCIP* subscip, /**< data structure of the sub-problem */ 429 SCIP_HEUR* heur, /**< LP face heuristic */ 430 SCIP_HEURDATA* heurdata, /**< heuristic data structure */ 431 SCIP_Bool* success /**< did we successfully set all parameters up? */ 432 ) 433 { 434 SCIP_Real timelimit; 435 SCIP_Real memorylimit; 436 SCIP_Longint nodelimit; 437 SCIP_Bool avoidmemout; 438 439 *success = TRUE; 440 441 /* check whether there is enough time and memory left */ 442 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) ); 443 SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) ); 444 SCIP_CALL( SCIPgetBoolParam(scip, "misc/avoidmemout", &avoidmemout) ); 445 446 if( ! SCIPisInfinity(scip, timelimit) ) 447 timelimit -= SCIPgetSolvingTime(scip); 448 449 /* substract the memory already used by the main SCIP and the estimated memory usage of external software */ 450 if( ! SCIPisInfinity(scip, memorylimit) ) 451 { 452 memorylimit -= SCIPgetMemUsed(scip)/1048576.0; 453 memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0; 454 } 455 456 /* abort if no time is left or not enough memory (we don't abort in this case if misc_avoidmemout == FALSE) 457 * to create a copy of SCIP, including external memory usage */ 458 if( timelimit <= 0.0 || (avoidmemout && memorylimit <= 2.0 * SCIPgetMemExternEstim(scip) / 1048576.0) ) 459 { 460 *success = FALSE; 461 return SCIP_OKAY; 462 } 463 464 /* calculate node limit for the subproblem */ 465 nodelimit = calcNodeLimit(scip, heur, heurdata); 466 467 /* we should have aborted the sub-SCIP procedure earlier if no additional nodes are allowed 468 * with the current parameter settings 469 */ 470 assert(nodelimit > SCIPgetNNodes(subscip)); 471 472 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelimit) ); 473 heurdata->nodelimit = nodelimit; 474 475 /* set also the other two limits */ 476 SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) ); 477 SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) ); 478 479 return SCIP_OKAY; 480 } 481 482 /** sets all one-time parameter settings like search strategy, but no limits */ 483 static 484 SCIP_RETCODE setSubscipParameters( 485 SCIP* subscip /**< data structure of the sub-problem */ 486 ) 487 { 488 /* do not abort subproblem on CTRL-C */ 489 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) ); 490 491 /* for debugging lpface, enable MIP output */ 492 #ifdef SCIP_DEBUG 493 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) ); 494 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 1) ); 495 #endif 496 497 /* disable statistic timing inside sub SCIP */ 498 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) ); 499 500 /* forbid recursive call of heuristics and separators solving subMIPs */ 501 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) ); 502 503 /* disable expensive cutting plane separation */ 504 SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_FAST, TRUE) ); 505 506 /* disable expensive presolving */ 507 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) ); 508 509 /* use restart depth first node selection */ 510 if( SCIPfindNodesel(subscip, "restartdfs") != NULL && ! SCIPisParamFixed(subscip, "nodeselection/restartdfs/stdpriority") ) 511 { 512 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/restartdfs/stdpriority", INT_MAX/4) ); 513 } 514 515 /* use inference branching */ 516 if( SCIPfindBranchrule(subscip, "inference") != NULL && ! SCIPisParamFixed(subscip, "branching/inference/priority") ) 517 { 518 SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) ); 519 } 520 521 /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */ 522 if( !SCIPisParamFixed(subscip, "conflict/enable") ) 523 { 524 SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) ); 525 } 526 if( !SCIPisParamFixed(subscip, "conflict/useboundlp") ) 527 { 528 SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') ); 529 } 530 if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") ) 531 { 532 SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) ); 533 } 534 535 return SCIP_OKAY; 536 } 537 538 /** reset the sub-SCIP data to its default values */ 539 static 540 void subscipdataReset( 541 SUBSCIPDATA* subscipdata /**< data structure of the sub-problem */ 542 ) 543 { 544 subscipdata->subscip = NULL; 545 subscipdata->subvars = NULL; 546 subscipdata->nsubvars = 0; 547 subscipdata->objbound = SCIP_INVALID; 548 } 549 550 /** free the stored sub-SCIP information */ 551 static 552 SCIP_RETCODE subscipdataFreeSubscip( 553 SCIP* scip, /**< original SCIP data structure */ 554 SUBSCIPDATA* subscipdata /**< data structure of the sub-problem */ 555 ) 556 { 557 assert(subscipdata != NULL); 558 559 /* free the subscipdata's scip */ 560 if( subscipdata->subscip != NULL ) 561 { 562 SCIP_CALL( SCIPfree(&subscipdata->subscip) ); 563 } 564 565 subscipdata->subscip = NULL; 566 567 /* free the subscip variables */ 568 if( subscipdata->subvars != NULL ) 569 { 570 assert(subscipdata->nsubvars > 0); 571 SCIPfreeBlockMemoryArray(scip, &subscipdata->subvars, subscipdata->nsubvars); 572 } 573 574 subscipdataReset(subscipdata); 575 576 return SCIP_OKAY; 577 } 578 579 /** store the sub-SCIP to the data structure */ 580 static 581 SCIP_RETCODE subscipdataCopySubscip( 582 SCIP* scip, /**< original SCIP data structure */ 583 SUBSCIPDATA* subscipdata, /**< data structure of the sub-problem */ 584 SCIP* subscip, /**< sub scip data structure to keep */ 585 SCIP_VAR** subvars, /**< sub scip variable array in the order of the main SCIP variables */ 586 int nvars /**< number of sub SCIP variables */ 587 ) 588 { 589 assert(scip != NULL); 590 assert(subscipdata != NULL); 591 assert(subscip != NULL); 592 assert(subvars != NULL); 593 assert(nvars == SCIPgetNVars(scip)); 594 595 assert(subscipdata->subscip == NULL); 596 assert(subscipdata->subvars == NULL); 597 598 subscipdata->subscip = subscip; 599 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &subscipdata->subvars, subvars, nvars) ); 600 subscipdata->nsubvars = nvars; 601 602 subscipdata->objbound = SCIPgetNodeLowerbound(scip, SCIPgetCurrentNode(scip)); 603 604 return SCIP_OKAY; 605 } 606 607 #ifdef SCIP_DEBUG 608 /** print debug message listing solving time, nodes, and status of sub-SCIP */ 609 static 610 SCIP_RETCODE subscipGetInfo( 611 SCIP* scip, /**< SCIP data structure */ 612 SCIP* subscip /**< sub SCIP data */ 613 ) 614 { 615 SCIP_Real timelimit; 616 SCIP_Real memorylimit; 617 SCIP_Longint nodelimit; 618 SCIP_Real time; 619 SCIP_Longint nodes; 620 SCIP_STATUS status; 621 622 SCIP_CALL( SCIPgetRealParam(subscip, "limits/time", &timelimit) ); 623 SCIP_CALL( SCIPgetRealParam(subscip, "limits/memory", &memorylimit) ); 624 SCIP_CALL( SCIPgetLongintParam(subscip, "limits/nodes", &nodelimit) ); 625 626 time = SCIPgetSolvingTime(subscip); 627 nodes = SCIPgetNNodes(subscip); 628 status = SCIPgetStatus(subscip); 629 630 SCIPdebugMsg(scip, "SCIP info: Time: %.1f (Limit: %.1f) Nodes: %"SCIP_LONGINT_FORMAT" (Limit: %"SCIP_LONGINT_FORMAT") Status: %d\n", 631 time, timelimit, nodes, nodelimit, status); 632 633 return SCIP_OKAY; 634 } 635 #endif 636 637 /** create the objective function based on the user selection */ 638 static 639 SCIP_RETCODE changeSubvariableObjective( 640 SCIP* scip, /**< SCIP data structure */ 641 SCIP* subscip, /**< sub-SCIP data structure */ 642 SCIP_VAR* var, /**< SCIP variable */ 643 SCIP_VAR* subvar, /**< sub-SCIP variable whose objective coefficient is changed */ 644 SCIP_HEURDATA* heurdata /**< heuristic data structure to control how the objective is changed */ 645 ) 646 { 647 SCIP_Real objcoeff; 648 SCIP_Real upfrac; 649 SCIP_Real downfrac; 650 SCIP_Real lpsolval; 651 SCIP_Real rootlpsolval; 652 653 /* create the objective value based on the choice of the sub-SCIP objective */ 654 switch( heurdata->subscipobjective ) 655 { 656 /* use zero as objective function */ 657 case 'z': 658 objcoeff = 0.0; 659 break; 660 661 /* use current LP fractionality as objective */ 662 case 'f': 663 lpsolval = SCIPvarGetLPSol(var); 664 downfrac = SCIPfrac(scip, lpsolval); 665 upfrac = 1.0 - downfrac; 666 667 objcoeff = downfrac - upfrac; 668 break; 669 670 /* use root LP solution difference */ 671 case 'r': 672 lpsolval = SCIPvarGetLPSol(var); 673 rootlpsolval = SCIPvarGetRootSol(var); 674 objcoeff = rootlpsolval - lpsolval; 675 break; 676 677 /* use average inferences */ 678 case 'i': 679 objcoeff = SCIPgetVarAvgInferences(scip, var, SCIP_BRANCHDIR_DOWNWARDS) 680 - SCIPgetVarAvgInferences(scip, var, SCIP_BRANCHDIR_UPWARDS); 681 break; 682 683 /* use original objective function */ 684 case 'o': 685 objcoeff = SCIPvarGetObj(var); 686 break; 687 default: 688 objcoeff = 0.0; 689 break; 690 } 691 692 SCIP_CALL( SCIPchgVarObj(subscip, subvar, objcoeff) ); 693 694 return SCIP_OKAY; 695 } 696 697 /* ---------------- Callback methods of event handler ---------------- */ 698 699 /** execution callback of the event handler for Lpface sub-SCIP 700 * 701 * we interrupt the solution process if we hit the LP iteration limit per node 702 */ 703 static 704 SCIP_DECL_EVENTEXEC(eventExecLpface) 705 { 706 SCIP_HEURDATA* heurdata; 707 708 assert(eventhdlr != NULL); 709 assert(eventdata != NULL); 710 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0); 711 assert(event != NULL); 712 assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_LPSOLVED); 713 714 heurdata = (SCIP_HEURDATA*)eventdata; 715 assert(heurdata != NULL); 716 717 /* interrupt solution process of sub-SCIP */ 718 if( SCIPgetNLPs(scip) > heurdata->lplimfac * heurdata->nodelimit ) 719 { 720 SCIPdebugMsg(scip, "interrupt after %" SCIP_LONGINT_FORMAT " LPs\n",SCIPgetNLPs(scip)); 721 SCIP_CALL( SCIPinterruptSolve(scip) ); 722 } 723 724 return SCIP_OKAY; 725 } 726 727 /** setup and solve the subproblem and catch the return code */ 728 static 729 SCIP_RETCODE setupSubscipLpface( 730 SCIP* scip, /**< SCIP data structure */ 731 SCIP* subscip, /**< sub-SCIP data structure */ 732 SCIP_HEURDATA* heurdata, /**< heuristics data */ 733 SCIP_VAR** subvars, /**< subproblem's variables */ 734 SCIP_VAR** vars, /**< original problem's variables */ 735 SCIP_VAR** fixvars, /**< variables that should be fixed */ 736 SCIP_Real* fixvals, /**< corresponding fixing values */ 737 int nfixvars, /**< number of variables that should be fixed */ 738 int nvars /**< number of original problem's variables */ 739 ) 740 { 741 SCIP_HASHMAP* varmapfw = NULL; /* mapping of SCIP variables to sub-SCIP variables */ 742 SCIP_Bool success; 743 int i; 744 745 assert( subscip != NULL ); 746 assert( heurdata != NULL ); 747 assert( vars != NULL ); 748 749 /* create the variable hash map */ 750 SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) ); 751 success = FALSE; 752 753 if( heurdata->uselprows ) 754 { 755 SCIP_Bool valid; 756 char probname[SCIP_MAXSTRLEN]; 757 758 /* copy all plugins */ 759 SCIP_CALL( SCIPcopyPlugins(scip, subscip, TRUE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, 760 TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, &valid) ); 761 /* get name of the original problem and add the string "_lpfacesub" */ 762 (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_lpfacesub", SCIPgetProbName(scip)); 763 764 /* create the subproblem */ 765 SCIP_CALL( SCIPcreateProbBasic(subscip, probname) ); 766 SCIPsetSubscipDepth(subscip, SCIPgetSubscipDepth(scip) + 1); 767 768 /* copy all variables */ 769 SCIP_CALL( SCIPcopyVars(scip, subscip, varmapfw, NULL, fixvars, fixvals, nfixvars, TRUE) ); 770 771 /* copy parameter settings */ 772 SCIP_CALL( SCIPcopyParamSettings(scip, subscip) ); 773 } 774 else 775 { 776 SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmapfw, NULL, "lpface", fixvars, fixvals, nfixvars, TRUE, FALSE, FALSE, TRUE, &success) ); 777 778 if( heurdata->copycuts ) 779 { 780 /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */ 781 SCIP_CALL( SCIPcopyCuts(scip, subscip, varmapfw, NULL, TRUE, NULL) ); 782 } 783 } 784 785 /* fill subvars array with mapping from original variables and set the objective coefficient to the desired value */ 786 for( i = 0; i < nvars; i++ ) 787 { 788 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]); 789 790 if( subvars[i] != NULL ) 791 { 792 SCIP_CALL( changeSubvariableObjective(scip, subscip, vars[i], subvars[i], heurdata) ); 793 } 794 } 795 796 /* free hash map */ 797 SCIPhashmapFree(&varmapfw); 798 799 /* disable output to console */ 800 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) ); 801 802 /* fix variables that are at their bounds and have nonzero reduced costs */ 803 SCIP_CALL( setupSubproblem(scip, subscip, subvars, heurdata) ); 804 805 /* set up sub-SCIP parameters */ 806 SCIP_CALL( setSubscipParameters(subscip) ); 807 808 return SCIP_OKAY; 809 } 810 811 /** setup and solve the subproblem and catch the return code */ 812 static 813 SCIP_RETCODE solveSubscipLpface( 814 SCIP* scip, /**< SCIP data structure */ 815 SCIP* subscip, /**< sub-SCIP data structure */ 816 SCIP_HEUR* heur, /**< mutation heuristic */ 817 SCIP_HEURDATA* heurdata, /**< heuristics data */ 818 SCIP_VAR** subvars, /**< subproblem's variables */ 819 SCIP_RESULT* result, /**< pointer to store the result */ 820 SCIP_Real focusnodelb, /**< lower bound of the focus node */ 821 SCIP_Bool* keepthisscip /**< should the subscip be kept or deleted? */ 822 ) 823 { 824 SCIP_EVENTHDLR* eventhdlr; 825 SCIP_Bool success; 826 827 assert( scip != NULL ); 828 assert( subscip != NULL ); 829 assert( heur != NULL ); 830 assert( heurdata != NULL ); 831 assert( subvars != NULL ); 832 833 /* create event handler for LP events */ 834 SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecLpface, NULL) ); 835 if( eventhdlr == NULL ) 836 { 837 SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n"); 838 return SCIP_PLUGINNOTFOUND; 839 } 840 841 /* determine node, memory, and time limits for the sub-SCIP. Both node and time limit change with every call to 842 * the heuristic 843 */ 844 SCIP_CALL( setSubscipLimits(scip, subscip, heur, heurdata, &success) ); 845 846 /* if we did not succeed to set the limits of the subscip to let it run, we won't keep it any longer */ 847 if( !success ) 848 { 849 *keepthisscip = FALSE; 850 851 return SCIP_OKAY; 852 } 853 854 /* catch LP events of sub-SCIP */ 855 SCIP_CALL( SCIPtransformProb(subscip) ); 856 SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) ); 857 858 #ifdef WRITELPFACEPROB 859 { 860 char probfilename[] = "./lpface_prob.mps"; 861 char paramfilename[] = "./lpface_prob.set"; 862 SCIPinfoMessage(scip, NULL, "Writing problem and parameters to file: <%s> <%s>\n", probfilename, paramfilename); 863 SCIP_CALL( SCIPwriteOrigProblem(subscip, probfilename, NULL, FALSE) ); 864 SCIP_CALL( SCIPwriteParams(subscip, paramfilename, TRUE, TRUE) ); 865 } 866 #endif 867 868 /* we must not be infeasible at this stage */ 869 assert(SCIPgetStatus(subscip) != SCIP_STATUS_INFEASIBLE); 870 871 /* solve the subproblem */ 872 SCIPdebugMsg(scip, "Solve Lpface subMIP\n"); 873 SCIPdebug( 874 SCIP_CALL( subscipGetInfo(scip, subscip) ); 875 ) 876 877 /* Errors in solving the subproblem should not kill the overall solving process. 878 * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. 879 */ 880 SCIP_CALL_ABORT( SCIPsolve(subscip) ); 881 882 /* print solving statistics of subproblem if we are in SCIP's debug mode */ 883 SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) ); 884 885 /* save useful information regarding the subscip runs */ 886 heurdata->usednodes += SCIPgetNNodes(subscip); 887 heurdata->submipnlpiters += SCIPgetNLPIterations(subscip); 888 heurdata->submippresoltime += SCIPgetPresolvingTime(subscip); 889 heurdata->submipstatus = SCIPgetStatus(subscip); 890 891 /* store the focus node lower bound as infeasible to avoid running on this face again */ 892 if( heurdata->submipstatus == SCIP_STATUS_INFEASIBLE ) 893 { 894 heurdata->lastlpobjinfeas = focusnodelb; 895 *keepthisscip = FALSE; 896 } 897 else if( SCIPgetNSols(subscip) > 0 ) 898 { 899 int solindex; 900 901 /* check, whether a solution was found; 902 * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one is accepted 903 */ 904 SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, &success, &solindex) ); 905 SCIPdebugMsg(scip, "Transfer was %s successful\n", success ? "" : "not"); 906 907 /* we found an optimal solution and are done. Thus, we free the subscip immediately */ 908 if( success ) 909 { 910 *keepthisscip = FALSE; 911 *result = SCIP_FOUNDSOL; 912 } 913 914 /* if solution could not be added to problem => run is counted as a failure */ 915 if( ! success || solindex != SCIPsolGetIndex(SCIPgetBestSol(scip)) ) 916 updateFailureStatistic(scip, heurdata); 917 } 918 else 919 { 920 /* if no new solution was found, run was a failure */ 921 updateFailureStatistic(scip, heurdata); 922 } 923 924 return SCIP_OKAY; 925 } 926 927 /* 928 * Callback methods of primal heuristic 929 */ 930 931 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 932 static 933 SCIP_DECL_HEURCOPY(heurCopyLpface) 934 { /*lint --e{715}*/ 935 assert(scip != NULL); 936 assert(heur != NULL); 937 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 938 939 /* call inclusion method of primal heuristic */ 940 SCIP_CALL( SCIPincludeHeurLpface(scip) ); 941 942 return SCIP_OKAY; 943 } 944 945 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 946 static 947 SCIP_DECL_HEURFREE(heurFreeLpface) 948 { /*lint --e{715}*/ 949 SCIP_HEURDATA* heurdata; 950 951 assert(heur != NULL); 952 assert(scip != NULL); 953 954 /* get heuristic data */ 955 heurdata = SCIPheurGetData(heur); 956 assert(heurdata != NULL); 957 958 /* free heuristic data */ 959 SCIPfreeBlockMemory(scip, &heurdata); 960 SCIPheurSetData(heur, NULL); 961 962 return SCIP_OKAY; 963 } 964 965 /** initialization method of primal heuristic (called after problem was transformed) */ 966 static 967 SCIP_DECL_HEURINIT(heurInitLpface) 968 { /*lint --e{715}*/ 969 SCIP_HEURDATA* heurdata; 970 971 assert(heur != NULL); 972 assert(scip != NULL); 973 974 /* get heuristic's data */ 975 heurdata = SCIPheurGetData(heur); 976 assert(heurdata != NULL); 977 978 /* initialize data */ 979 heurdata->usednodes = 0; 980 heurdata->nfailures = 0; 981 heurdata->nextnodenumber = 0; 982 983 heurdata->submipstatus = SCIP_STATUS_UNKNOWN; 984 heurdata->submipnlpiters = -1; 985 heurdata->submippresoltime = 0.0; 986 heurdata->nvarsfixed = -1; 987 988 return SCIP_OKAY; 989 } 990 991 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */ 992 static 993 SCIP_DECL_HEURINITSOL(heurInitsolLpface) 994 { /*lint --e{715}*/ 995 SCIP_HEURDATA* heurdata; 996 997 assert(heur != NULL); 998 assert(scip != NULL); 999 1000 /* get heuristic's data */ 1001 heurdata = SCIPheurGetData(heur); 1002 assert(heurdata != NULL); 1003 1004 /* reset the last infeasible objective because it lives in transformed space and must be invalidated at every restart */ 1005 heurdata->lastlpobjinfeas = -SCIPinfinity(scip); 1006 1007 assert(heurdata->subscipdata == NULL); 1008 1009 /* variable order might have changed since the last run, reinitialize sub-SCIP data */ 1010 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata->subscipdata) ); 1011 subscipdataReset(heurdata->subscipdata); 1012 1013 return SCIP_OKAY; 1014 } 1015 1016 /** solving process deinitialization method of primal heuristic (called before branch and bound process is exiting) */ 1017 static 1018 SCIP_DECL_HEUREXITSOL(heurExitsolLpface) 1019 { /*lint --e{715}*/ 1020 SCIP_HEURDATA* heurdata; 1021 1022 assert(heur != NULL); 1023 assert(scip != NULL); 1024 1025 /* get heuristic's data */ 1026 heurdata = SCIPheurGetData(heur); 1027 assert(heurdata != NULL); 1028 1029 /* variable order might change after restart, free the heuristic subscipdata */ 1030 assert(heurdata->keepsubscip || heurdata->subscipdata->subscip == NULL); 1031 if( heurdata->subscipdata->subscip != NULL ) 1032 { 1033 /* free kept data structures first */ 1034 SCIP_CALL( subscipdataFreeSubscip(scip, heurdata->subscipdata) ); 1035 } 1036 1037 /* free the sub-SCIP data structure */ 1038 SCIPfreeBlockMemory(scip, &heurdata->subscipdata); 1039 1040 return SCIP_OKAY; 1041 } 1042 1043 #ifdef SCIP_STATISTIC 1044 /** deinitialization method of primal heuristic (called before transformed problem is freed) */ 1045 static 1046 SCIP_DECL_HEUREXIT(heurExitLpface) 1047 { /*lint --e{715}*/ 1048 SCIP_HEURDATA* heurdata; 1049 1050 assert(heur != NULL); 1051 assert(scip != NULL); 1052 1053 /* get heuristic's data */ 1054 heurdata = SCIPheurGetData(heur); 1055 assert(heurdata != NULL); 1056 1057 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, 1058 "LP Face heuristic stats: Status: %d Nodes: %d LP iters: %d Fixed: %d Presolving time: %.2f\n", 1059 heurdata->submipstatus, heurdata->usednodes, heurdata->submipnlpiters, heurdata->nvarsfixed, heurdata->submippresoltime); 1060 1061 return SCIP_OKAY; 1062 } 1063 #else 1064 #define heurExitLpface NULL 1065 #endif 1066 1067 /** execution method of primal heuristic */ 1068 static 1069 SCIP_DECL_HEUREXEC(heurExecLpface) 1070 { /*lint --e{715}*/ 1071 SCIP* subscip; /* the subproblem created by lpface */ 1072 SCIP_HEURDATA* heurdata; /* primal heuristic data */ 1073 SCIP_VAR** vars; /* original problem's variables */ 1074 SCIP_VAR** subvars; /* subproblem's variables */ 1075 SCIP_RETCODE retcode; 1076 SCIP_Bool keepthisscip; 1077 SCIP_Real focusnodelb; 1078 SCIP_Real rootlb; 1079 SCIP_Longint nodelimit; /* node limit for the subproblem */ 1080 int nvars; /* number of original problem's variables */ 1081 int nbinvars; 1082 int nintvars; 1083 1084 assert(heur != NULL); 1085 assert(scip != NULL); 1086 assert(result != NULL); 1087 1088 /* get heuristic's data */ 1089 heurdata = SCIPheurGetData(heur); 1090 assert(heurdata != NULL); 1091 1092 *result = SCIP_DELAYED; 1093 1094 /* we skip infeasible nodes */ 1095 if( nodeinfeasible ) 1096 return SCIP_OKAY; 1097 1098 /* the node number to run the heuristic again was not yet reached */ 1099 if( SCIPgetNNodes(scip) < heurdata->nextnodenumber ) 1100 return SCIP_OKAY; 1101 1102 /* do not run heuristic on nodes that were not solved to optimality */ 1103 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL ) 1104 return SCIP_OKAY; 1105 1106 /* LP face requires that the LP defines a valid lower bound for the current node */ 1107 if( ! SCIPisLPRelax(scip) || ! SCIPallColsInLP(scip) ) 1108 return SCIP_OKAY; 1109 1110 assert(SCIPgetCurrentNode(scip) != NULL); 1111 focusnodelb = SCIPgetNodeLowerbound(scip, SCIPgetCurrentNode(scip)); 1112 1113 /* from the checked conditions, the LP objective should be a valid lower bound for the current node */ 1114 assert(SCIPisGE(scip, focusnodelb, SCIPgetLPObjval(scip))); 1115 1116 /* do not run if the current focus node already has a lower bound higher than the LP value at the node, 1117 * for example, due to strong branching 1118 */ 1119 if( SCIPisGT(scip, focusnodelb, SCIPgetLPObjval(scip)) ) 1120 return SCIP_OKAY; 1121 1122 /* delay heuristic if the active search tree path is not deep enough */ 1123 if( SCIPgetDepth(scip) < heurdata->minpathlen - 1 ) 1124 return SCIP_OKAY; 1125 1126 /* only run at lower bound defining nodes */ 1127 if( SCIPisGT(scip, focusnodelb, SCIPgetLowerbound(scip)) ) 1128 return SCIP_OKAY; 1129 1130 /* only run if lower bound has increased since last LP objective where the sub-MIP was solved to infeasibility */ 1131 if( SCIPisEQ(scip, heurdata->lastlpobjinfeas, focusnodelb) ) 1132 return SCIP_OKAY; 1133 1134 /* make the reasoning stronger if the objective value must be integral */ 1135 if( SCIPisObjIntegral(scip) 1136 && (! SCIPisIntegral(scip, focusnodelb) || SCIPisLT(scip, focusnodelb, heurdata->lastlpobjinfeas + 1.0)) ) 1137 return SCIP_OKAY; 1138 1139 rootlb = SCIPgetLowerboundRoot(scip); 1140 assert(SCIPisLE(scip, rootlb, focusnodelb)); 1141 1142 /* if the lower bound hasn't changed since the root node, we want to run anyway, otherwise we base our decision on the 1143 * total path length of the active search tree along which the lower bound did not change anymore. 1144 */ 1145 if( SCIPisLT(scip, rootlb, focusnodelb) ) 1146 { 1147 SCIP_NODE* parent; 1148 int nonimprovingpathlen = 0; /* the length of the current path (in edges) along which the lower bound stayed the same */ 1149 1150 parent = SCIPnodeGetParent(SCIPgetCurrentNode(scip)); 1151 1152 /* count the path length along which the dual bound has not changed */ 1153 while( SCIPisEQ(scip, SCIPnodeGetLowerbound(parent), focusnodelb) && nonimprovingpathlen < heurdata->minpathlen ) 1154 { 1155 ++nonimprovingpathlen; 1156 1157 /* we cannot hit the root node because the root lower bound is strictly smaller */ 1158 assert(SCIPnodeGetParent(parent) != NULL); 1159 parent = SCIPnodeGetParent(parent); 1160 } 1161 1162 /* we return if the nonimproving path is too short measured by the heuristic frequency */ 1163 if( nonimprovingpathlen < heurdata->minpathlen ) 1164 { 1165 /* we do not delay the heuristic if the path has length zero, otherwise it may be called at children so that 1166 * the path length is sufficient 1167 */ 1168 if( nonimprovingpathlen == 0 ) 1169 *result = SCIP_DIDNOTRUN; 1170 1171 return SCIP_OKAY; 1172 } 1173 } 1174 1175 *result = SCIP_DIDNOTRUN; 1176 1177 /* calculate the maximal number of branching nodes until heuristic is aborted */ 1178 nodelimit = calcNodeLimit(scip, heur, heurdata); 1179 1180 /* check whether we have enough nodes left to call subproblem solving */ 1181 if( nodelimit < heurdata->minnodes ) 1182 return SCIP_OKAY; 1183 1184 if( SCIPisStopped(scip) ) 1185 return SCIP_OKAY; 1186 1187 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) ); 1188 assert(nvars > 0); 1189 1190 /* check whether discrete variables are present */ 1191 if( nbinvars == 0 && nintvars == 0 ) 1192 return SCIP_OKAY; 1193 1194 *result = SCIP_DIDNOTFIND; 1195 1196 keepthisscip = heurdata->keepsubscip; 1197 1198 /* check if variable number increased since last call to the sub-SCIP */ 1199 if( heurdata->subscipdata->subscip != NULL && heurdata->subscipdata->nsubvars != nvars ) 1200 { 1201 SCIPdebugMsg(scip, "Free subscip of LP face heuristic because variable number %d changed since last call (was %d)\n", 1202 nvars, heurdata->subscipdata->nsubvars); 1203 1204 SCIP_CALL( subscipdataFreeSubscip(scip, heurdata->subscipdata) ); 1205 } 1206 else if( heurdata->subscipdata->subscip != NULL && SCIPisGT(scip, focusnodelb, heurdata->subscipdata->objbound) ) 1207 { 1208 SCIPdebugMsg(scip, "Free subscip of LP face heuristic because of different dual bound: %16.9g > %16.9g\n", 1209 SCIPretransformObj(scip, focusnodelb), SCIPretransformObj(scip, heurdata->subscipdata->objbound)); 1210 1211 SCIP_CALL( subscipdataFreeSubscip(scip, heurdata->subscipdata) ); 1212 } 1213 1214 /* retrieve the sub-SCIP from the heuristic data structure */ 1215 if( heurdata->subscipdata->subscip != NULL ) 1216 { 1217 subscip = heurdata->subscipdata->subscip; 1218 subvars = heurdata->subscipdata->subvars; 1219 nvars = heurdata->subscipdata->nsubvars; 1220 1221 SCIPdebug( 1222 SCIPdebugMsg(scip, "Loaded sub-SCIP from previous run:\n"); 1223 SCIP_CALL( subscipGetInfo(scip, subscip) ); 1224 ) 1225 } 1226 else 1227 { 1228 SCIP_VAR** fixvars; 1229 SCIP_Real* fixvals; 1230 int nfixvars; 1231 SCIP_Bool success; 1232 1233 assert(heurdata->subscipdata->subscip == NULL); 1234 1235 /* allocate memory to hold sub-SCIP variables */ 1236 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) ); 1237 1238 SCIP_CALL( SCIPallocBufferArray(scip, &fixvars, nvars) ); 1239 SCIP_CALL( SCIPallocBufferArray(scip, &fixvals, nvars) ); 1240 1241 SCIP_CALL( determineVariableFixings(scip, heurdata, fixvars, fixvals, &nfixvars, &success) ); 1242 1243 if( ! success ) 1244 { 1245 SCIPfreeBufferArray(scip, &fixvals); 1246 SCIPfreeBufferArray(scip, &fixvars); 1247 SCIPfreeBufferArray(scip, &subvars); 1248 1249 *result = SCIP_DIDNOTRUN; 1250 return SCIP_OKAY; 1251 } 1252 1253 SCIPdebugMsg(scip, "Creating new sub-Problem for LP face heuristic\n"); 1254 1255 /* initialize the subproblem */ 1256 SCIP_CALL( SCIPcreate(&subscip) ); 1257 1258 SCIP_CALL( setupSubscipLpface(scip, subscip, heurdata, subvars, vars, fixvars, fixvals, nfixvars, nvars) ); 1259 1260 SCIPfreeBufferArray(scip, &fixvals); 1261 SCIPfreeBufferArray(scip, &fixvars); 1262 } 1263 1264 retcode = solveSubscipLpface(scip, subscip, heur, heurdata, subvars, result, focusnodelb, &keepthisscip); 1265 1266 SCIP_CALL( retcode ); 1267 1268 /* free subproblem or store it for the next run of the heuristic */ 1269 if( ! keepthisscip ) 1270 { 1271 /* we only allocated buffer memory if no previous subscip was reinstalled */ 1272 if( heurdata->subscipdata->subscip == NULL ) 1273 { 1274 SCIPfreeBufferArray(scip, &subvars); 1275 SCIP_CALL( SCIPfree(&subscip) ); 1276 } 1277 else 1278 SCIP_CALL( subscipdataFreeSubscip(scip, heurdata->subscipdata) ); 1279 1280 subscipdataReset(heurdata->subscipdata); 1281 } 1282 else 1283 { 1284 /* if the subscip has not yet been stored, we copy the subscip into the heuristic data to keep it for the next run */ 1285 if( heurdata->subscipdata->subscip == NULL ) 1286 { 1287 SCIP_CALL( subscipdataCopySubscip(scip, heurdata->subscipdata, subscip, subvars, nvars) ); 1288 SCIPfreeBufferArray(scip, &subvars); 1289 } 1290 else 1291 { 1292 assert(heurdata->subscipdata->subscip == subscip); 1293 assert(heurdata->subscipdata->subvars == subvars); 1294 assert(heurdata->subscipdata->nsubvars == nvars); 1295 } 1296 } 1297 1298 return SCIP_OKAY; 1299 } 1300 1301 /* 1302 * primal heuristic specific interface methods 1303 */ 1304 1305 /** creates the lpface primal heuristic and includes it in SCIP */ 1306 SCIP_RETCODE SCIPincludeHeurLpface( 1307 SCIP* scip /**< SCIP data structure */ 1308 ) 1309 { 1310 SCIP_HEURDATA* heurdata; 1311 SCIP_HEUR* heur; 1312 1313 /* create Lpface primal heuristic data */ 1314 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 1315 1316 heurdata->subscipdata = NULL; 1317 1318 /* include primal heuristic */ 1319 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 1320 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 1321 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecLpface, heurdata) ); 1322 1323 assert(heur != NULL); 1324 1325 /* set non-NULL pointers to callback methods */ 1326 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyLpface) ); 1327 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeLpface) ); 1328 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitLpface) ); 1329 SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolLpface) ); 1330 SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolLpface) ); 1331 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitLpface) ); 1332 1333 /* add lpface primal heuristic parameters */ 1334 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs", 1335 "number of nodes added to the contingent of the total nodes", 1336 &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 1337 1338 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes", 1339 "maximum number of nodes to regard in the subproblem", 1340 &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 1341 1342 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes", 1343 "minimum number of nodes required to start the subproblem", 1344 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 1345 1346 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot", 1347 "contingent of sub problem nodes in relation to the number of nodes of the original problem", 1348 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) ); 1349 1350 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate", 1351 "required percentage of fixed integer variables in sub-MIP to run", 1352 &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) ); 1353 1354 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lplimfac", 1355 "factor by which the limit on the number of LP depends on the node limit", 1356 &heurdata->lplimfac, TRUE, DEFAULT_LPLIMFAC, 1.0, SCIP_REAL_MAX, NULL, NULL) ); 1357 1358 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows", 1359 "should subproblem be created out of the rows in the LP rows?", 1360 &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) ); 1361 1362 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/dualbasisequations", 1363 "should dually nonbasic rows be turned into equations?", 1364 &heurdata->dualbasisequations, TRUE, DEFAULT_DUALBASISEQUATIONS, NULL, NULL) ); 1365 1366 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/keepsubscip", 1367 "should the heuristic continue solving the same sub-SCIP?", 1368 &heurdata->keepsubscip, TRUE, DEFAULT_KEEPSUBSCIP, NULL, NULL) ); 1369 1370 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts", 1371 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?", 1372 &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) ); 1373 1374 SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/subscipobjective", 1375 "objective function in the sub-SCIP: (z)ero, (r)oot-LP-difference, (i)nference, LP (f)ractionality, (o)riginal", 1376 &heurdata->subscipobjective, TRUE, 'z', "forzi", NULL, NULL) ); 1377 1378 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/minpathlen", 1379 "the minimum active search tree path length along which lower bound hasn't changed before heuristic becomes active", 1380 &heurdata->minpathlen, TRUE, DEFAULT_MINPATHLEN, 0, 65531, NULL, NULL) ); 1381 1382 return SCIP_OKAY; 1383 } 1384