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_subnlp.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief NLP local search primal heuristic using sub-SCIPs 28 * @author Stefan Vigerske 29 * 30 * @todo reconstruct sub-SCIP if problem has changed 31 */ 32 33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 34 35 #include "blockmemshell/memory.h" 36 #include "scip/nlpi_ipopt.h" 37 #include "scip/cons_bounddisjunction.h" 38 #include "scip/cons_setppc.h" 39 #include "scip/heur_subnlp.h" 40 #include "scip/pub_event.h" 41 #include "scip/pub_heur.h" 42 #include "scip/pub_message.h" 43 #include "scip/pub_misc.h" 44 #include "scip/pub_sol.h" 45 #include "scip/pub_var.h" 46 #include "scip/scip_branch.h" 47 #include "scip/scip_cons.h" 48 #include "scip/scip_copy.h" 49 #include "scip/scip_event.h" 50 #include "scip/scip_general.h" 51 #include "scip/scip_heur.h" 52 #include "scip/scip_lp.h" 53 #include "scip/scip_mem.h" 54 #include "scip/scip_message.h" 55 #include "scip/scip_nlp.h" 56 #include "scip/scip_nlpi.h" 57 #include "scip/scip_numerics.h" 58 #include "scip/scip_param.h" 59 #include "scip/scip_presol.h" 60 #include "scip/scip_pricer.h" 61 #include "scip/scip_prob.h" 62 #include "scip/scip_sol.h" 63 #include "scip/scip_solve.h" 64 #include "scip/scip_solvingstats.h" 65 #include "scip/scip_timing.h" 66 #include "scip/scip_var.h" 67 #include <string.h> 68 69 #define HEUR_NAME "subnlp" 70 #define HEUR_DESC "primal heuristic that performs a local search in an NLP after fixing integer variables and presolving" 71 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS 72 #define HEUR_PRIORITY -2000010 73 #define HEUR_FREQ 1 74 #define HEUR_FREQOFS 0 75 #define HEUR_MAXDEPTH -1 76 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE 77 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? we set this to FALSE because we want this heuristic to also run within other heuristics */ 78 79 /* 80 * Data structures 81 */ 82 83 /** primal heuristic data */ 84 struct SCIP_HeurData 85 { 86 SCIP* subscip; /**< copy of CIP where presolving and NLP solving is done */ 87 SCIP_Bool triedsetupsubscip; /**< whether we have tried to setup a sub-SCIP */ 88 SCIP_Bool subscipisvalid; /**< whether all constraints have been copied */ 89 SCIP_Bool continuous; /**< whether problem was continuous when sub-SCIP was created */ 90 int nseriousnlpierror; /**< number of consecutive serious NLP solver failures (memout, ...) */ 91 SCIP_EVENTHDLR* eventhdlr; /**< event handler for global bound change events */ 92 93 int nvars; /**< number of active transformed variables in SCIP */ 94 int nsubvars; /**< number of original variables in sub-SCIP */ 95 SCIP_VAR** var_subscip2scip; /**< mapping variables in sub-SCIP to SCIP variables */ 96 SCIP_VAR** var_scip2subscip; /**< mapping variables in SCIP to sub-SCIP variables */ 97 98 SCIP_SOL* startcand; /**< candidate for start point for heuristic */ 99 SCIP_Real startcandviol; /**< violation of start point candidate w.r.t. constraint that reported this candidate */ 100 SCIP_SOL* lastsol; /**< pointer to last found solution (or NULL if none), not captured, thus may be dangling */ 101 102 int nlpverblevel; /**< verbosity level of NLP solver */ 103 SCIP_Real opttol; /**< optimality tolerance to use for NLP solves */ 104 SCIP_Real feastolfactor; /**< factor on SCIP feasibility tolerance for NLP solves if resolving when NLP solution not feasible in CIP */ 105 SCIP_Real feastol; /**< feasibility tolerance for NLP solves */ 106 SCIP_Bool tighterfeastolfailed;/**< whether we tried to use a tighter feasibility tolerance but the NLP solution was still not accepted */ 107 int maxpresolverounds; /**< limit on number of presolve rounds in sub-SCIP */ 108 int presolveemphasis; /**< presolve emphasis in sub-SCIP */ 109 SCIP_Bool setcutoff; /**< whether to set cutoff in sub-SCIP to current primal bound */ 110 SCIP_Bool forbidfixings; /**< whether to add constraints that forbid specific fixations that turned out to be infeasible */ 111 SCIP_Bool keepcopy; /**< whether to keep SCIP copy or to create new copy each time heuristic is applied */ 112 SCIP_Real expectinfeas; /**< when to tell NLP solver that an infeasible NLP is not unexpected */ 113 114 SCIP_Longint iterused; /**< number of iterations used so far (+ number of heuristic runs + number of presolve runs in subscip) */ 115 SCIP_Longint iterusedokay; /**< number of iterations used so far when NLP stopped with status okay */ 116 SCIP_Longint iterusediterlim; /**< maximal number of iterations used when NLP stopped due to iteration limit */ 117 int nnlpsolves; /**< number of NLP solves */ 118 int nnlpsolvesokay; /**< number of NLP solves with status okay */ 119 int nnlpsolvesiterlim; /**< number of NLP solves that hit an iteration limit */ 120 int nnlpsolvesinfeas; /**< number of NLP solves with status okay and infeasible */ 121 int nodesoffset; /**< number of nodes added to the actual number of nodes when computing itercontingent */ 122 SCIP_Real nodesfactor; /**< factor to apply to number of nodes in SCIP to compute initial itercontingent */ 123 SCIP_Real successrateexp; /**< exponent for power of success rate to be multiplied with itercontingent */ 124 int iterinit; /**< number of iterations used for initial NLP solves */ 125 int ninitsolves; /**< number of successful NLP solves until switching to iterlimit guess and using success rate */ 126 int itermin; /**< minimal number of iterations for NLP solves */ 127 }; 128 129 130 /* 131 * Local methods 132 */ 133 134 /** indicates whether the heuristic should be running, i.e., whether we expect something nonlinear after fixing all discrete variables */ 135 static 136 SCIP_RETCODE runHeuristic( 137 SCIP* scip, /**< SCIP data structure */ 138 SCIP_Bool* runheur /**< buffer to store whether to run heuristic */ 139 ) 140 { 141 assert(scip != NULL); 142 assert(runheur != NULL); 143 144 /* do not run heuristic if no NLP solver is available */ 145 if( SCIPgetNNlpis(scip) <= 0 ) 146 { 147 *runheur = FALSE; 148 return SCIP_OKAY; 149 } 150 151 /* do not run heuristic if no NLP */ 152 if( !SCIPisNLPConstructed(scip) ) 153 { 154 *runheur = FALSE; 155 return SCIP_OKAY; 156 } 157 158 /* do not run heuristic if no continuous nonlinear variables in NLP */ 159 SCIP_CALL( SCIPhasNLPContinuousNonlinearity(scip, runheur) ); 160 161 return SCIP_OKAY; 162 } 163 164 /** free sub-SCIP data structure */ 165 static 166 SCIP_RETCODE freeSubSCIP( 167 SCIP* scip, /**< SCIP data structure */ 168 SCIP_HEURDATA* heurdata /**< heuristic data structure */ 169 ) 170 { 171 SCIP_VAR** subvars; 172 int nsubvars; 173 int i; 174 SCIP_VAR* var; 175 SCIP_VAR* subvar; 176 177 assert(scip != NULL); 178 assert(heurdata != NULL); 179 180 assert(heurdata->subscip != NULL); 181 182 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nsubvars, NULL, NULL, NULL, NULL) ); 183 assert(nsubvars == heurdata->nsubvars); 184 185 /* drop global bound change events 186 * release variables in SCIP and sub-SCIP 187 */ 188 for( i = 0; i < heurdata->nsubvars; ++i ) 189 { 190 subvar = subvars[i]; 191 assert(subvar != NULL); 192 assert(SCIPvarGetProbindex(subvar) == i); 193 194 var = heurdata->var_subscip2scip[SCIPvarGetProbindex(subvar)]; 195 assert(var != NULL); 196 assert(SCIPvarGetProbindex(var) <= heurdata->nvars); 197 assert(!SCIPvarIsActive(var) || heurdata->var_scip2subscip[SCIPvarGetProbindex(var)] == subvar); 198 199 SCIP_CALL( SCIPdropVarEvent(scip, var, SCIP_EVENTTYPE_GBDCHANGED, heurdata->eventhdlr, (SCIP_EVENTDATA*)heurdata, -1) ); 200 201 SCIP_CALL( SCIPreleaseVar(heurdata->subscip, &subvar) ); 202 SCIP_CALL( SCIPreleaseVar(scip, &var) ); 203 } 204 205 /* free variable mappings subscip -> scip and scip -> subscip */ 206 SCIPfreeBlockMemoryArray(scip, &heurdata->var_subscip2scip, heurdata->nsubvars); 207 SCIPfreeBlockMemoryArray(scip, &heurdata->var_scip2subscip, heurdata->nvars); 208 heurdata->nsubvars = 0; 209 heurdata->nvars = 0; 210 211 /* free sub-SCIP */ 212 SCIP_CALL( SCIPfree(&heurdata->subscip) ); 213 214 return SCIP_OKAY; 215 } 216 217 /** creates copy of CIP from problem in SCIP */ 218 static 219 SCIP_RETCODE createSubSCIP( 220 SCIP* scip, /**< SCIP data structure */ 221 SCIP_HEURDATA* heurdata /**< heuristic data structure */ 222 ) 223 { 224 int nvars; 225 SCIP_VAR** vars; 226 SCIP_VAR** subvars; 227 SCIP_VAR* var; 228 SCIP_VAR* subvar; 229 SCIP_Bool success; 230 char probname[SCIP_MAXSTRLEN]; 231 int i; 232 SCIP_HASHMAP* varsmap; 233 SCIP_HASHMAP* conssmap; 234 235 assert(heurdata != NULL); 236 assert(heurdata->subscip == NULL); 237 238 heurdata->triedsetupsubscip = TRUE; 239 240 /* initializing the subproblem */ 241 SCIP_CALL( SCIPcreate(&heurdata->subscip) ); 242 243 /* create sub-SCIP copy of CIP */ 244 245 /* copy interesting plugins */ 246 success = TRUE; 247 SCIP_CALL( SCIPcopyPlugins(scip, heurdata->subscip, 248 FALSE, /* readers */ 249 FALSE, /* pricers */ 250 TRUE, /* conshdlrs */ 251 FALSE, /* conflicthdlrs */ 252 TRUE, /* presolvers */ 253 FALSE, /* relaxators */ 254 FALSE, /* separators */ 255 FALSE, /* cutselectors */ 256 TRUE, /* propagators */ 257 FALSE, /* heuristics */ 258 TRUE, /* eventhandler */ 259 TRUE, /* nodeselectors (SCIP gives an error if there is none) */ 260 FALSE, /* branchrules */ 261 TRUE, /* displays */ 262 FALSE, /* tables */ 263 FALSE, /* dialogs */ 264 TRUE, /* expression handlers */ 265 TRUE, /* nlpis */ 266 TRUE, /* message handler */ 267 &success) ); 268 if( !success ) 269 { 270 SCIPdebugMsg(scip, "failed to copy some plugins to sub-SCIP, continue anyway\n"); 271 } 272 273 /* check if we still have NLPI's in subscip */ 274 if( SCIPgetNNlpis(heurdata->subscip) <= 0 ) 275 { 276 SCIPdebugMsg(scip, "none of the NLPIs from main SCIP copied into sub-SCIP, give up heuristic.\n"); 277 SCIP_CALL( SCIPfree(&heurdata->subscip) ); 278 279 return SCIP_OKAY; 280 } 281 282 /* copy parameter settings */ 283 SCIP_CALL( SCIPcopyParamSettings(scip, heurdata->subscip) ); 284 285 /* create problem in sub-SCIP */ 286 /* get name of the original problem and add "subnlp" */ 287 (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_subnlp", SCIPgetProbName(scip)); 288 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 289 SCIP_CALL( SCIPhashmapCreate(&varsmap, SCIPblkmem(scip), nvars) ); 290 SCIP_CALL( SCIPhashmapCreate(&conssmap, SCIPblkmem(scip), SCIPgetNConss(scip)) ); 291 SCIP_CALL( SCIPcopyProb(scip, heurdata->subscip, varsmap, conssmap, TRUE, probname) ); 292 293 /* copy all variables */ 294 SCIP_CALL( SCIPcopyVars(scip, heurdata->subscip, varsmap, conssmap, NULL, NULL, 0, TRUE) ); 295 296 /* copy as many constraints as possible */ 297 SCIP_CALL( SCIPcopyConss(scip, heurdata->subscip, varsmap, conssmap, TRUE, FALSE, &heurdata->subscipisvalid) ); 298 SCIPhashmapFree(&conssmap); 299 if( !heurdata->subscipisvalid ) 300 { 301 SCIPdebugMsg(scip, "failed to copy some constraints to sub-SCIP, continue anyway\n"); 302 } 303 304 /* create arrays translating scip transformed vars to subscip original vars, and vice versa 305 * capture variables in SCIP and sub-SCIP 306 * catch global bound change events 307 */ 308 309 SCIP_CALL( SCIPgetVarsData(heurdata->subscip, &subvars, &heurdata->nsubvars, NULL, NULL, NULL, NULL) ); 310 311 SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &heurdata->var_subscip2scip, heurdata->nsubvars) ); 312 313 heurdata->nvars = nvars; 314 SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &heurdata->var_scip2subscip, heurdata->nvars) ); 315 316 /* we need to get all subscip variables, also those which are copies of fixed variables from the main scip 317 * therefore we iterate over the hashmap 318 */ 319 for( i = 0; i < SCIPhashmapGetNEntries(varsmap); ++i ) 320 { 321 SCIP_HASHMAPENTRY* entry; 322 entry = SCIPhashmapGetEntry(varsmap, i); 323 if( entry != NULL ) 324 { 325 var = (SCIP_VAR*) SCIPhashmapEntryGetOrigin(entry); 326 subvar = (SCIP_VAR*) SCIPhashmapEntryGetImage(entry); 327 assert(subvar != NULL); 328 assert(SCIPvarGetProbindex(subvar) >= 0); 329 assert(SCIPvarGetProbindex(subvar) <= heurdata->nsubvars); 330 331 if( SCIPvarIsActive(var) ) 332 { 333 assert(SCIPvarGetProbindex(var) <= heurdata->nvars); 334 assert(heurdata->var_scip2subscip[SCIPvarGetProbindex(var)] == NULL); /* assert that we have no mapping for this var yet */ 335 heurdata->var_scip2subscip[SCIPvarGetProbindex(var)] = subvar; 336 } 337 338 assert(heurdata->var_subscip2scip[SCIPvarGetProbindex(subvar)] == NULL); /* assert that we have no mapping for this subvar yet */ 339 heurdata->var_subscip2scip[SCIPvarGetProbindex(subvar)] = var; 340 } 341 } 342 343 for( i = 0; i < heurdata->nsubvars; ++i ) 344 { 345 subvar = SCIPgetVars(heurdata->subscip)[i]; 346 assert(SCIPvarGetProbindex(subvar) == i); 347 var = heurdata->var_subscip2scip[i]; 348 349 SCIP_CALL( SCIPcaptureVar(scip, var) ); 350 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, subvar) ); 351 352 assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetLbGlobal(subvar))); 353 assert(SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(var), SCIPvarGetUbGlobal(subvar))); 354 355 SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_GBDCHANGED, heurdata->eventhdlr, (SCIP_EVENTDATA*)heurdata, NULL) ); 356 } 357 358 #ifndef NDEBUG 359 for( i = 0; i < heurdata->nvars; ++i ) 360 { 361 assert(heurdata->var_scip2subscip[i] == NULL || (SCIP_VAR*)SCIPhashmapGetImage(varsmap, (void*)vars[i]) == heurdata->var_scip2subscip[i]); 362 } 363 for( i = 0; i < heurdata->nsubvars; ++i ) 364 { 365 assert(heurdata->var_subscip2scip[i] != NULL); 366 assert((SCIP_VAR*)SCIPhashmapGetImage(varsmap, (void*)heurdata->var_subscip2scip[i]) == subvars[i]); 367 } 368 #endif 369 370 /* do not need hashmap anymore */ 371 SCIPhashmapFree(&varsmap); 372 373 /* do not abort subproblem on CTRL-C */ 374 SCIP_CALL( SCIPsetBoolParam(heurdata->subscip, "misc/catchctrlc", FALSE) ); 375 376 /* disable keeping solutions from one subscip solve for next solve (with usually different fixings) */ 377 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "limits/maxorigsol", 0) ); 378 379 #ifdef SCIP_DEBUG 380 /* for debugging, enable SCIP output */ 381 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "display/verblevel", 5) ); 382 #else 383 /* disable output to console */ 384 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "display/verblevel", 0) ); 385 #endif 386 387 /* reset some limits to default values, in case users changed them in main scip (SCIPcopy copies parameter values :-() */ 388 SCIP_CALL( SCIPresetParam(heurdata->subscip, "limits/absgap") ); 389 SCIP_CALL( SCIPresetParam(heurdata->subscip, "limits/bestsol") ); 390 SCIP_CALL( SCIPresetParam(heurdata->subscip, "limits/gap") ); 391 SCIP_CALL( SCIPresetParam(heurdata->subscip, "limits/restarts") ); 392 SCIP_CALL( SCIPresetParam(heurdata->subscip, "limits/solutions") ); 393 SCIP_CALL( SCIPresetParam(heurdata->subscip, "limits/time") ); 394 SCIP_CALL( SCIPresetParam(heurdata->subscip, "limits/totalnodes") ); 395 396 /* we remember here which way (continuous or not) we went, in case all binary and integer vars get fixed in root */ 397 heurdata->continuous = SCIPgetNBinVars(heurdata->subscip) == 0 && SCIPgetNIntVars(heurdata->subscip) == 0; 398 if( !heurdata->continuous ) 399 { 400 /* set presolve maxrounds and emphasis; always disable components presolver 401 * heuristics and separators were not copied into subscip, so should not need to switch off 402 */ 403 if( !SCIPisParamFixed(heurdata->subscip, "presolving/maxrounds") ) 404 { 405 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "presolving/maxrounds", heurdata->maxpresolverounds) ); 406 } 407 SCIP_CALL( SCIPsetPresolving(heurdata->subscip, (SCIP_PARAMSETTING)heurdata->presolveemphasis, TRUE) ); 408 if( !SCIPisParamFixed(heurdata->subscip, "constraints/components/maxprerounds") ) 409 { 410 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "constraints/components/maxprerounds", 0) ); 411 } 412 } 413 else 414 { 415 /* for continuous problems, disable presolve and move subscip into a stage where it has a NLP 416 * the only reason why we don't solve the NLP in the main SCIP is that we want global variable bounds for the NLP 417 */ 418 SCIP_RETCODE retcode; 419 420 SCIP_CALL( SCIPtransformProb(heurdata->subscip) ); 421 422 SCIP_CALL( SCIPsetPresolving(heurdata->subscip, SCIP_PARAMSETTING_OFF, TRUE) ); 423 SCIP_CALL( SCIPpresolve(heurdata->subscip) ); 424 425 if( SCIPgetStage(heurdata->subscip) != SCIP_STAGE_PRESOLVED || SCIPgetNVars(heurdata->subscip) == 0 ) 426 { 427 /* presolve found problem infeasible, solved it, or stopped due to some limit 428 * all a bit strange, since problem should be the same as original, presolve was disabled, and we didn't set any limits 429 * we will give up and not run the heuristic 430 */ 431 SCIP_CALL( freeSubSCIP(scip, heurdata) ); 432 return SCIP_OKAY; 433 } 434 435 /* do initial solve, i.e., "solve" root node with node limit 0 (should do scip.c::initSolve and then stop immediately in solve.c::SCIPsolveCIP) */ 436 SCIP_CALL( SCIPsetLongintParam(heurdata->subscip, "limits/nodes", 0LL) ); 437 retcode = SCIPsolve(heurdata->subscip); 438 439 /* errors in solving the subproblem should not kill the overall solving process 440 * hence, the return code is caught and a warning is printed 441 */ 442 if( retcode != SCIP_OKAY ) 443 { 444 SCIPwarningMessage(scip, "Error while initializing subproblem in subnlp heuristic; sub-SCIP terminated with code <%d>\n", retcode); 445 SCIP_CALL( freeSubSCIP(scip, heurdata) ); 446 return SCIP_OKAY; 447 } 448 449 /* If we are in stage "solved" (strange) or have no NLP (also strange), then do not run heuristic, too */ 450 if( SCIPgetStage(heurdata->subscip) == SCIP_STAGE_SOLVED || !SCIPisNLPConstructed(heurdata->subscip) ) 451 { 452 SCIP_CALL( freeSubSCIP(scip, heurdata) ); 453 return SCIP_OKAY; 454 } 455 456 assert(SCIPgetStage(heurdata->subscip) == SCIP_STAGE_SOLVING); 457 assert(SCIPgetStatus(heurdata->subscip) == SCIP_STATUS_NODELIMIT); 458 assert(SCIPisNLPConstructed(heurdata->subscip)); 459 } 460 461 return SCIP_OKAY; 462 } 463 464 /** process variable global bound change event */ 465 static 466 SCIP_DECL_EVENTEXEC(processVarEvent) 467 { 468 SCIP_HEURDATA* heurdata; 469 SCIP_VAR* var; 470 SCIP_VAR* subvar; 471 int idx; 472 473 assert(scip != NULL); 474 assert(event != NULL); 475 assert(eventdata != NULL); 476 assert(eventhdlr != NULL); 477 478 heurdata = (SCIP_HEURDATA*)eventdata; 479 assert(heurdata != NULL); 480 481 var = SCIPeventGetVar(event); 482 assert(var != NULL); 483 484 idx = SCIPvarGetProbindex(var); 485 /* if event corresponds to an active variable, we can easily look up the corresponding subvar 486 * if it is an inactive variable that has been copied to the subproblem, 487 * then we need to check the subscip2scip mapping 488 * @todo we could do this faster if we keep the variables mapping from SCIPcopy around 489 */ 490 if( idx >= 0 ) 491 { 492 assert(idx < heurdata->nvars); 493 494 subvar = heurdata->var_scip2subscip[idx]; 495 } 496 else 497 { 498 for( idx = 0; idx < heurdata->nsubvars; ++idx ) 499 { 500 if( heurdata->var_subscip2scip[idx] == var ) 501 break; 502 } 503 assert(idx < heurdata->nsubvars); 504 subvar = SCIPgetVars(heurdata->subscip)[idx]; 505 } 506 assert(subvar != NULL); 507 508 if( SCIPeventGetType(event) & SCIP_EVENTTYPE_GLBCHANGED ) 509 { 510 SCIP_CALL( SCIPchgVarLbGlobal(heurdata->subscip, subvar, SCIPeventGetNewbound(event)) ); 511 } 512 513 if( SCIPeventGetType(event) & SCIP_EVENTTYPE_GUBCHANGED ) 514 { 515 SCIP_CALL( SCIPchgVarUbGlobal(heurdata->subscip, subvar, SCIPeventGetNewbound(event)) ); 516 } 517 518 return SCIP_OKAY; 519 } 520 521 /* creates a SCIP_SOL in our SCIP space out of the solution from NLP solver in sub-SCIP */ 522 static 523 SCIP_RETCODE createSolFromNLP( 524 SCIP* scip, /**< SCIP data structure */ 525 SCIP_HEUR* heur, /**< heuristic data structure */ 526 SCIP_SOL** sol, /**< buffer to store solution value; if pointing to NULL, then a new solution is created, otherwise values in the given one are overwritten */ 527 SCIP_HEUR* authorheur /**< the heuristic which should be registered as author of the solution */ 528 ) 529 { 530 SCIP_HEURDATA* heurdata; 531 SCIP_VAR** vars; 532 int nvars; 533 SCIP_VAR* var; 534 SCIP_VAR* subvar; 535 SCIP_Real solval; 536 int i; 537 538 assert(scip != NULL); 539 assert(heur != NULL); 540 assert(sol != NULL); 541 542 heurdata = SCIPheurGetData(heur); 543 assert(heurdata != NULL); 544 assert(SCIPhasNLPSolution(heurdata->subscip)); 545 546 if( *sol == NULL ) 547 { 548 SCIP_CALL( SCIPcreateSol(scip, sol, authorheur) ); 549 } 550 else 551 { 552 SCIPsolSetHeur(*sol, authorheur); 553 } 554 555 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 556 557 assert(nvars >= heurdata->nvars); 558 for( i = 0; i < heurdata->nvars; ++i ) 559 { 560 var = vars[i]; 561 assert(var != NULL); 562 assert(SCIPvarIsActive(var)); /* SCIPgetVarsData should have given us only active vars */ 563 564 subvar = heurdata->var_scip2subscip[i]; 565 if( subvar == NULL ) 566 solval = MIN(MAX(0.0, SCIPvarGetLbLocal(var)), SCIPvarGetUbLocal(var)); /*lint !e666*/ 567 else 568 solval = SCIPvarGetNLPSol(subvar); 569 570 assert(solval != SCIP_INVALID); /*lint !e777*/ 571 SCIP_CALL( SCIPsetSolVal(scip, *sol, var, solval) ); 572 } 573 574 for( ; i < nvars; ++i ) 575 { 576 var = vars[i]; 577 assert(var != NULL); 578 assert(SCIPvarIsActive(var)); /* SCIPgetVarsData should have given us only active vars */ 579 580 solval = MIN(MAX(0.0, SCIPvarGetLbLocal(var)), SCIPvarGetUbLocal(var)); /*lint !e666*/ 581 SCIP_CALL( SCIPsetSolVal(scip, *sol, var, solval) ); 582 } 583 584 return SCIP_OKAY; 585 } 586 587 /** creates SCIP solution from NLP and tries adding to SCIP or only checks feasibility */ 588 static 589 SCIP_RETCODE processNLPSol( 590 SCIP* scip, /**< original SCIP data structure */ 591 SCIP_HEUR* heur, /**< heuristic data structure */ 592 SCIP_HEUR* authorheur, /**< the heuristic that should be the author of solution, if any */ 593 SCIP_RESULT* result, /**< buffer to store result FOUNDSOL if a solution has been found and accepted */ 594 SCIP_SOL* resultsol /**< a solution where to store found solution values, if any, or NULL if to try adding to SCIP */ 595 ) 596 { 597 SCIP_HEURDATA* heurdata; 598 599 assert(scip != NULL); 600 assert(heur != NULL); 601 assert(result != NULL); 602 603 heurdata = SCIPheurGetData(heur); 604 assert(heurdata != NULL); 605 606 assert(SCIPhasNLPSolution(heurdata->subscip)); 607 608 if( resultsol == NULL ) 609 { 610 /* resultsol NULL means we should try adding the sol to SCIP */ 611 if( SCIPisLE(scip, SCIPgetNLPObjval(heurdata->subscip), SCIPgetUpperbound(scip)) ) 612 { 613 /* solution is feasible and should improve upper bound, so try adding it to SCIP */ 614 SCIP_SOL* sol; 615 SCIP_Bool stored; 616 617 sol = NULL; 618 SCIP_CALL( createSolFromNLP(scip, heur, &sol, authorheur) ); 619 620 heurdata->lastsol = sol; /* remember just the pointer so we might recognize if this solution comes back as startingpoint */ 621 #ifdef SCIP_DEBUG 622 /* print the infeasibilities to stdout */ 623 SCIP_CALL( SCIPtrySolFree(scip, &sol, TRUE, TRUE, TRUE, FALSE, TRUE, &stored) ); 624 #else 625 SCIP_CALL( SCIPtrySolFree(scip, &sol, FALSE, FALSE, TRUE, FALSE, TRUE, &stored) ); 626 #endif 627 628 if( stored ) 629 { 630 /* SCIP stored solution (yippi!), so we are done */ 631 if( heurdata->nlpverblevel >= 1 ) 632 { 633 SCIPinfoMessage(scip, NULL, "SCIP stored solution from NLP solve\n"); 634 } 635 else 636 { 637 SCIPdebugMsg(scip, "SCIP stored solution from NLP solve\n"); 638 } 639 640 *result = SCIP_FOUNDSOL; 641 } 642 else 643 { 644 if( heurdata->nlpverblevel >= 1 ) 645 { 646 SCIPinfoMessage(scip, NULL, "solution reported by NLP solver not stored by SCIP\n"); 647 } 648 else 649 { 650 SCIPdebugMsg(scip, "solution reported by NLP solver not stored by SCIP\n"); 651 } 652 } 653 } 654 else if( heurdata->nlpverblevel >= 1 ) 655 { 656 SCIPinfoMessage(scip, NULL, "subnlp solution objval %e is above the primal bound %e\n", 657 SCIPgetNLPObjval(heurdata->subscip), SCIPgetUpperbound(scip)); 658 } 659 } 660 else 661 { 662 /* only create a solution and pass it back in resultsol, do not add to SCIP */ 663 SCIP_Bool feasible; 664 665 SCIP_CALL( createSolFromNLP(scip, heur, &resultsol, authorheur) ); 666 667 heurdata->lastsol = resultsol; 668 #ifdef SCIP_DEBUG 669 /* print the infeasibilities to stdout */ 670 SCIP_CALL( SCIPcheckSol(scip, resultsol, TRUE, TRUE, TRUE, FALSE, TRUE, &feasible) ); 671 #else 672 SCIP_CALL( SCIPcheckSol(scip, resultsol, FALSE, FALSE, TRUE, FALSE, TRUE, &feasible) ); 673 #endif 674 if( feasible ) 675 { 676 /* SCIP find solution feasible, so we are done */ 677 if( heurdata->nlpverblevel >= 1 ) 678 { 679 SCIPinfoMessage(scip, NULL, "solution reported by NLP solver feasible for SCIP\n"); 680 } 681 else 682 { 683 SCIPdebugMsg(scip, "solution reported by NLP solver feasible for SCIP\n"); 684 } 685 *result = SCIP_FOUNDSOL; 686 } 687 else 688 { 689 if( heurdata->nlpverblevel >= 1 ) 690 { 691 SCIPinfoMessage(scip, NULL, "solution reported by NLP solver not feasible for SCIP\n"); 692 } 693 else 694 { 695 SCIPdebugMsg(scip, "solution reported by NLP solver not feasible for SCIP\n"); 696 } 697 } 698 } 699 700 return SCIP_OKAY; 701 } 702 703 /* creates a SCIP_SOL in our SCIP space out of the SCIP_SOL from a sub-SCIP */ 704 static 705 SCIP_RETCODE createSolFromSubScipSol( 706 SCIP* scip, /**< SCIP data structure */ 707 SCIP_HEUR* heur, /**< heuristic data structure */ 708 SCIP_SOL** sol, /**< buffer to store solution value; if pointing to NULL, then a new solution is created, otherwise values in the given one are overwritten */ 709 SCIP_SOL* subsol, /**< solution of sub-SCIP */ 710 SCIP_HEUR* authorheur /**< the heuristic which should be registered as author of the solution */ 711 ) 712 { 713 SCIP_HEURDATA* heurdata; 714 SCIP_VAR** vars; 715 int nvars; 716 SCIP_VAR* var; 717 SCIP_VAR* subvar; 718 SCIP_Real solval; 719 int i; 720 721 assert(scip != NULL); 722 assert(heur != NULL); 723 assert(sol != NULL); 724 assert(subsol != NULL); 725 726 heurdata = SCIPheurGetData(heur); 727 assert(heurdata != NULL); 728 729 if( *sol == NULL ) 730 { 731 SCIP_CALL( SCIPcreateSol(scip, sol, authorheur) ); 732 } 733 else 734 { 735 SCIPsolSetHeur(*sol, authorheur); 736 } 737 738 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 739 740 assert(nvars >= heurdata->nvars); 741 for( i = 0; i < heurdata->nvars; ++i ) 742 { 743 var = vars[i]; 744 assert(var != NULL); 745 assert(SCIPvarIsActive(var)); 746 747 subvar = heurdata->var_scip2subscip[i]; 748 if( subvar == NULL ) 749 solval = MIN(MAX(0.0, SCIPvarGetLbLocal(var)), SCIPvarGetUbLocal(var)); /*lint !e666*/ 750 else 751 solval = SCIPgetSolVal(heurdata->subscip, subsol, subvar); 752 753 assert(solval != SCIP_INVALID); /*lint !e777*/ 754 SCIP_CALL( SCIPsetSolVal(scip, *sol, var, solval) ); 755 } 756 757 for( ; i < nvars; ++i ) 758 { 759 var = vars[i]; 760 assert(var != NULL); 761 assert(SCIPvarIsActive(var)); 762 763 solval = MIN(MAX(0.0, SCIPvarGetLbLocal(var)), SCIPvarGetUbLocal(var)); /*lint !e666*/ 764 SCIP_CALL( SCIPsetSolVal(scip, *sol, var, solval) ); 765 } 766 767 return SCIP_OKAY; 768 } 769 770 /** finds an iteration limit */ /*lint --e{715}*/ 771 static 772 int calcIterLimit( 773 SCIP* scip, /**< original SCIP data structure */ 774 SCIP_HEURDATA* heurdata /**< heuristic data */ 775 ) 776 { 777 /* if we hit more often an iterlimit than we were successful (termstatus=okay), then allow for more iterations: 778 * take twice the maximal iterusage on solves that hit the iterlimit 779 */ 780 if( heurdata->nnlpsolvesiterlim > heurdata->nnlpsolvesokay ) 781 return MAX(heurdata->itermin, 2 * heurdata->iterusediterlim); /*lint !e712*/ 782 783 /* if we had sufficiently many successful solves, then take twice the average of previous iterusages on successful solves */ 784 if( heurdata->nnlpsolvesokay >= heurdata->ninitsolves ) 785 return MAX(heurdata->itermin, 2 * heurdata->iterusedokay / heurdata->nnlpsolvesokay); /*lint !e712*/ 786 787 /* if we had too few successful solves, then still ensure that we allow for at least iterinit iterations */ 788 if( heurdata->nnlpsolvesokay > 0 ) 789 return MAX3(heurdata->itermin, heurdata->iterinit, 2 * heurdata->iterusedokay / heurdata->nnlpsolvesokay); /*lint !e712*/ 790 791 /* if we had no successful solve so far and none that hit an iterlimit, e.g., we are at the first NLP solve, then use iterinit */ 792 return MAX(heurdata->itermin, heurdata->iterinit); 793 } 794 795 /** solves the subNLP specified in subscip */ 796 static 797 SCIP_RETCODE solveSubNLP( 798 SCIP* scip, /**< original SCIP data structure */ 799 SCIP_HEUR* heur, /**< heuristic data structure */ 800 SCIP_RESULT* result, /**< buffer to store result, DIDNOTFIND, FOUNDSOL, or CUTOFF */ 801 SCIP_SOL* refpoint, /**< point to take fixation of discrete variables from, and startpoint for NLP solver; if NULL, then LP solution is used */ 802 SCIP_SOL* resultsol /**< a solution where to store found solution values, if any, or NULL if to try adding to SCIP */ 803 ) 804 { 805 SCIP_HEURDATA* heurdata = SCIPheurGetData(heur); 806 SCIP_RETCODE retcode; 807 SCIP_Real* startpoint; 808 SCIP_VAR* var; 809 SCIP_VAR* subvar; 810 int i; 811 SCIP_HEUR* authorheur; /* the heuristic which will be the author of a solution, if found */ 812 SCIP_Real timelimit; 813 SCIP_Bool expectinfeas; 814 SCIP_NLPSTATISTICS nlpstatistics; 815 816 assert(scip != NULL); 817 assert(heur != NULL); 818 assert(heurdata != NULL); 819 assert(result != NULL); 820 assert(SCIPisTransformed(heurdata->subscip)); 821 822 /* get remaining SCIP solve time; if no time left, then stop */ 823 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) ); 824 if( !SCIPisInfinity(scip, timelimit) ) 825 { 826 timelimit -= SCIPgetSolvingTime(scip); 827 if( timelimit <= 0.0 ) 828 return SCIP_OKAY; 829 } 830 /* set timelimit for NLP solve and in case presolve is unexpectedly expensive */ 831 SCIP_CALL( SCIPsetRealParam(heurdata->subscip, "limits/time", timelimit) ); 832 833 /* if the refpoint comes from a heuristic, then make it the author of a found solution, 834 * otherwise let the subNLP heuristic claim authorship 835 * TODO: I doubt that this has much effect; for the statistics, the number of solutions found by a heuristic 836 * seems to be computed as the increase in number of solutions before and after a heuristic is run 837 * check this and maybe change 838 */ 839 if( refpoint == NULL || SCIPsolGetHeur(refpoint) == NULL ) 840 authorheur = heur; 841 else 842 authorheur = SCIPsolGetHeur(refpoint); 843 844 if( !heurdata->continuous ) 845 { 846 /* presolve sub-SCIP 847 * set node limit to 1 so that presolve can go 848 */ 849 SCIP_CALL( SCIPsetLongintParam(heurdata->subscip, "limits/nodes", 1LL) ); 850 SCIP_CALL( SCIPpresolve(heurdata->subscip) ); 851 852 /* count one presolve round as on NLP iteration for now 853 * plus one extra for all the setup cost 854 * this is mainly to avoid that the primal heuristics runs all the time on instances that are solved in the subscip-presolve 855 */ 856 heurdata->iterused += 1 + SCIPgetNPresolRounds(scip); /*lint !e776*/ 857 858 if( SCIPgetStage(heurdata->subscip) == SCIP_STAGE_SOLVED ) 859 { 860 /* presolve probably found the subproblem infeasible */ 861 SCIPdebugMsg(scip, "SCIP returned from presolve in stage solved with status %d and %d sols\n", SCIPgetStatus(heurdata->subscip), SCIPgetNSols(heurdata->subscip)); 862 /* if presolve found subproblem infeasible, report this to caller by setting *result to cutoff */ 863 if( SCIPgetStatus(heurdata->subscip) == SCIP_STATUS_INFEASIBLE ) 864 *result = SCIP_CUTOFF; 865 } 866 else if( SCIPgetStage(heurdata->subscip) == SCIP_STAGE_PRESOLVING ) 867 { 868 /* presolve was stopped because some still existing limit was hit (e.g., memory) */ 869 SCIPdebugMsg(scip, "SCIP returned from presolve in stage presolving with status %d and %d sols\n", SCIPgetStatus(heurdata->subscip), SCIPgetNSols(heurdata->subscip)); 870 /* if presolve found subproblem infeasible, report this to caller by setting *result to cutoff */ 871 if( SCIPgetStatus(heurdata->subscip) == SCIP_STATUS_INFEASIBLE ) 872 *result = SCIP_CUTOFF; 873 } 874 else 875 { 876 assert(SCIPgetStage(heurdata->subscip) == SCIP_STAGE_PRESOLVED); 877 878 if( SCIPgetNVars(heurdata->subscip) > 0 ) 879 { 880 /* do initial solve, i.e., "solve" root node with node limit 0 (should do scip.c::initSolve and then stop immediately in solve.c::SCIPsolveCIP) */ 881 SCIP_CALL( SCIPsetLongintParam(heurdata->subscip, "limits/nodes", 0LL) ); 882 retcode = SCIPsolve(heurdata->subscip); 883 884 /* If no NLP was constructed, then there were no nonlinearities after presolve. 885 * So we increase the nodelimit to 1 and hope that SCIP will find some solution to this probably linear subproblem. 886 */ 887 if( retcode == SCIP_OKAY && SCIPgetStage(heurdata->subscip) != SCIP_STAGE_SOLVED && !SCIPisNLPConstructed(heurdata->subscip) ) 888 { 889 SCIP_CALL( SCIPsetLongintParam(heurdata->subscip, "limits/nodes", 1LL) ); 890 retcode = SCIPsolve(heurdata->subscip); 891 } 892 } 893 else 894 { 895 /* If all variables were removed by presolve, but presolve did not end with status SOLVED, 896 * then we run solve, still with nodelimit=1, and hope to find some (maybe trivial) solution. 897 */ 898 retcode = SCIPsolve(heurdata->subscip); 899 } 900 901 /* errors in solving the subproblem should not kill the overall solving process 902 * hence, the return code is caught and a warning is printed 903 */ 904 if( retcode != SCIP_OKAY ) 905 { 906 SCIPwarningMessage(scip, "Error while solving subproblem in subnlp heuristic; sub-SCIP terminated with code <%d>\n", retcode); 907 return SCIP_OKAY; 908 } 909 } 910 911 /* we should either have variables, or the problem was trivial, in which case it should have been presolved or solved */ 912 assert(SCIPgetNVars(heurdata->subscip) > 0 || SCIPgetStage(heurdata->subscip) == SCIP_STAGE_PRESOLVING || SCIPgetStage(heurdata->subscip) == SCIP_STAGE_SOLVED); 913 914 SCIPdebug( SCIP_CALL( SCIPprintStatistics(heurdata->subscip, NULL) ); ) 915 916 /* if sub-SCIP found solutions already, then pass them to main scip */ 917 for( i = 0; i < SCIPgetNSols(heurdata->subscip); ++i ) 918 { 919 if( resultsol == NULL ) 920 { 921 SCIP_Bool stored; 922 SCIP_SOL* sol; 923 924 sol = NULL; 925 SCIP_CALL( createSolFromSubScipSol(scip, heur, &sol, SCIPgetSols(heurdata->subscip)[i], authorheur) ); 926 927 heurdata->lastsol = sol; /* remember just the pointer so we might recognize if this solution comes back as startingpoint */ 928 SCIP_CALL( SCIPtrySolFree(scip, &sol, FALSE, FALSE, TRUE, FALSE, TRUE, &stored) ); 929 if( stored ) 930 { 931 if( heurdata->nlpverblevel >= 1 ) 932 { 933 SCIPinfoMessage(scip, NULL, "SCIP stored solution from sub-SCIP root node\n"); 934 } 935 else 936 { 937 SCIPdebugMsg(scip, "SCIP stored solution from sub-SCIP root node\n"); 938 } 939 *result = SCIP_FOUNDSOL; 940 break; 941 } 942 else 943 { 944 if( heurdata->nlpverblevel >= 1 ) 945 { 946 SCIPinfoMessage(scip, NULL, "SCIP did not store sub-SCIP optimal solution\n"); 947 } 948 else 949 { 950 SCIPdebugMsg(scip, "SCIP did not store sub-SCIP optimal solution\n"); 951 } 952 } 953 } 954 else 955 { 956 SCIP_Bool feasible; 957 958 SCIP_CALL( createSolFromSubScipSol(scip, heur, &resultsol, SCIPgetSols(heurdata->subscip)[i], authorheur) ); 959 960 heurdata->lastsol = resultsol; 961 SCIP_CALL( SCIPcheckSol(scip, resultsol, FALSE, FALSE, TRUE, FALSE, TRUE, &feasible) ); 962 if( feasible ) 963 { 964 if( heurdata->nlpverblevel >= 1 ) 965 { 966 SCIPinfoMessage(scip, NULL, "SCIP solution from sub-SCIP root node is feasible\n"); 967 } 968 else 969 { 970 SCIPdebugMsg(scip, "SCIP solution from sub-SCIP root node is feasible\n"); 971 } 972 *result = SCIP_FOUNDSOL; 973 break; 974 } 975 else 976 { 977 if( heurdata->nlpverblevel >= 1 ) 978 { 979 SCIPinfoMessage(scip, NULL, "SCIP solution from sub-SCIP root node is not feasible\n"); 980 } 981 else 982 { 983 SCIPdebugMsg(scip, "SCIP solution from sub-SCIP root node is not feasible\n"); 984 } 985 } 986 } 987 } 988 989 /* if subscip is infeasible here, we signal this to the caller */ 990 if( SCIPgetStatus(heurdata->subscip) == SCIP_STATUS_INFEASIBLE ) 991 { 992 if( heurdata->nlpverblevel >= 1 ) 993 { 994 SCIPinfoMessage(scip, NULL, "sub-SCIP detected infeasibility\n"); 995 } 996 else 997 { 998 SCIPdebugMsg(scip, "sub-SCIP detected infeasibility\n"); 999 } 1000 1001 assert(SCIPgetStage(heurdata->subscip) == SCIP_STAGE_SOLVED); 1002 *result = SCIP_CUTOFF; 1003 return SCIP_OKAY; 1004 } 1005 1006 /* if we stopped for some other reason, or there is no NLP, we also stop */ 1007 if( SCIPgetStage(heurdata->subscip) <= SCIP_STAGE_PRESOLVED || SCIPgetStage(heurdata->subscip) == SCIP_STAGE_SOLVED || !SCIPisNLPConstructed(heurdata->subscip) ) 1008 return SCIP_OKAY; 1009 1010 /* in most cases, the status should be nodelimit 1011 * in some cases, if the sub-SCIP is very easy, it may report optimal, so we do not need invoke an NLP solver 1012 * if the presolve found the problem infeasible, then there is no use in solving an NLP 1013 * if the user interrupted or a timelimit was reached, then we should also stop here 1014 * unbounded is very unlikely to happen, in most cases, it should have been concluded in the main scip already 1015 */ 1016 switch( SCIPgetStatus(heurdata->subscip) ) 1017 { 1018 case SCIP_STATUS_NODELIMIT: 1019 break; /* this is the status that is most likely happening */ 1020 case SCIP_STATUS_TOTALNODELIMIT: 1021 case SCIP_STATUS_STALLNODELIMIT: 1022 case SCIP_STATUS_GAPLIMIT: 1023 case SCIP_STATUS_SOLLIMIT: 1024 case SCIP_STATUS_BESTSOLLIMIT: 1025 /* these should not happen, but if one does, it's safe to return */ 1026 SCIPABORT(); /*lint -fallthrough*/ 1027 case SCIP_STATUS_OPTIMAL: 1028 case SCIP_STATUS_INFEASIBLE: 1029 case SCIP_STATUS_USERINTERRUPT: 1030 case SCIP_STATUS_TIMELIMIT: 1031 case SCIP_STATUS_MEMLIMIT: 1032 case SCIP_STATUS_UNBOUNDED: 1033 case SCIP_STATUS_INFORUNBD: 1034 return SCIP_OKAY; 1035 default: 1036 SCIPerrorMessage("unexpected status of sub-SCIP: <%d>\n", SCIPgetStatus(heurdata->subscip)); 1037 return SCIP_ERROR; 1038 } /*lint !e788*/ 1039 } 1040 else 1041 { 1042 /* for continuous problem, createSubSCIP() should have put us into a state where we can invoke the NLP solver */ 1043 assert(SCIPisNLPConstructed(heurdata->subscip)); 1044 assert(SCIPgetStage(heurdata->subscip) == SCIP_STAGE_SOLVING); 1045 assert(SCIPgetStatus(heurdata->subscip) == SCIP_STATUS_NODELIMIT); 1046 } 1047 1048 /* set starting values (=refpoint, if not NULL; otherwise LP solution (or pseudo solution)) */ 1049 SCIP_CALL( SCIPallocBufferArray(scip, &startpoint, SCIPgetNNLPVars(heurdata->subscip)) ); 1050 1051 if( heurdata->nlpverblevel >= 3 ) 1052 { 1053 SCIPinfoMessage(scip, NULL, "set NLP starting point\n"); 1054 } 1055 1056 for( i = 0; i < SCIPgetNNLPVars(heurdata->subscip); ++i ) 1057 { 1058 SCIP_Real scalar; 1059 SCIP_Real constant; 1060 1061 subvar = SCIPgetNLPVars(heurdata->subscip)[i]; 1062 1063 /* gets corresponding original variable */ 1064 scalar = 1.0; 1065 constant = 0.0; 1066 SCIP_CALL( SCIPvarGetOrigvarSum(&subvar, &scalar, &constant) ); 1067 if( subvar == NULL ) 1068 { 1069 startpoint[i] = constant; 1070 1071 if( heurdata->nlpverblevel >= 3 && !SCIPisZero(heurdata->subscip, startpoint[i]) ) 1072 { 1073 SCIPinfoMessage(scip, NULL, "%s = %e\n", SCIPvarGetName(SCIPgetNLPVars(heurdata->subscip)[i]), startpoint[i]); 1074 } 1075 1076 continue; 1077 } 1078 1079 assert(SCIPvarGetProbindex(subvar) >= 0); 1080 assert(SCIPvarGetProbindex(subvar) < heurdata->nsubvars); 1081 var = heurdata->var_subscip2scip[SCIPvarGetProbindex(subvar)]; 1082 if( var == NULL || REALABS(SCIPgetSolVal(scip, refpoint, var)) > 1.0e+12 ) 1083 startpoint[i] = MIN(MAX(0.0, SCIPvarGetLbGlobal(subvar)), SCIPvarGetUbGlobal(subvar)); /*lint !e666*/ 1084 else 1085 /* scalar*subvar+constant corresponds to nlpvar[i], so nlpvar[i] gets value scalar*varval+constant */ 1086 startpoint[i] = scalar * SCIPgetSolVal(scip, refpoint, var) + constant; 1087 1088 if( heurdata->nlpverblevel >= 3 && !SCIPisZero(heurdata->subscip, startpoint[i]) ) 1089 { 1090 SCIPinfoMessage(scip, NULL, "%s = %e\n", SCIPvarGetName(SCIPgetNLPVars(heurdata->subscip)[i]), startpoint[i]); 1091 } 1092 } 1093 SCIP_CALL( SCIPsetNLPInitialGuess(heurdata->subscip, startpoint) ); 1094 1095 SCIPfreeBufferArray(scip, &startpoint); 1096 1097 *result = SCIP_DIDNOTFIND; 1098 1099 /* if we had many (fraction > expectinfeas) infeasible NLPs, then tell NLP solver to expect an infeasible problem */ 1100 expectinfeas = FALSE; 1101 if( heurdata->expectinfeas == 0.0 ) /* to keep original behavior on default settings */ 1102 expectinfeas = TRUE; 1103 else if( heurdata->nnlpsolvesokay > heurdata->ninitsolves && heurdata->nnlpsolvesinfeas > heurdata->expectinfeas * heurdata->nnlpsolvesokay ) 1104 expectinfeas = TRUE; 1105 1106 /* let the NLP solver do its magic */ 1107 SCIPdebugMsg(scip, "start NLP solve with iteration limit %d\n", calcIterLimit(scip, heurdata)); 1108 SCIP_CALL( SCIPsolveNLP(heurdata->subscip, 1109 .iterlimit = calcIterLimit(scip, heurdata), 1110 .opttol = heurdata->opttol, 1111 .feastol = heurdata->feastol, 1112 .verblevel = (unsigned short)heurdata->nlpverblevel, 1113 .expectinfeas = expectinfeas 1114 ) ); /*lint !e666*/ 1115 1116 SCIPdebugMsg(scip, "NLP solver returned with termination status %d and solution status %d, objective value is %g\n", 1117 SCIPgetNLPTermstat(heurdata->subscip), SCIPgetNLPSolstat(heurdata->subscip), SCIPgetNLPObjval(heurdata->subscip)); 1118 1119 /* add NLP solve statistics from subscip to main SCIP, so they show up in final statistics 1120 * for continuous problems, we also ask to reset statistics, since we do not retransform subSCIP in the next run (which would reset all stats) 1121 * (merging statistics once in exitsol is too late, since they may be printed before) 1122 */ 1123 SCIPmergeNLPIStatistics(heurdata->subscip, scip, heurdata->continuous); 1124 1125 if( SCIPgetNLPTermstat(heurdata->subscip) >= SCIP_NLPTERMSTAT_OUTOFMEMORY ) 1126 { 1127 /* oops, something did not go well at all */ 1128 if( heurdata->nlpverblevel >= 1 ) 1129 { 1130 SCIPinfoMessage(scip, NULL, "NLP solver in subNLP heuristic for problem <%s> returned with bad termination status %d.\n", 1131 SCIPgetProbName(scip), SCIPgetNLPTermstat(heurdata->subscip)); 1132 } 1133 1134 ++(heurdata->nseriousnlpierror); 1135 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, 1136 "NLP solver in subNLP heuristic for problem <%s> returned with bad termination status %d. This was the %d%s successive time.\n", 1137 SCIPgetProbName(scip), SCIPgetNLPTermstat(heurdata->subscip), heurdata->nseriousnlpierror, 1138 heurdata->nseriousnlpierror == 1 ? "st" : heurdata->nseriousnlpierror == 2 ? "nd" : heurdata->nseriousnlpierror == 3 ? "rd" : "th"); 1139 if( heurdata->nseriousnlpierror >= 5 ) 1140 { 1141 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Will not run subNLP heuristic again for this run.\n"); 1142 SCIP_CALL( freeSubSCIP(scip, heurdata) ); 1143 } 1144 return SCIP_OKAY; 1145 } 1146 heurdata->nseriousnlpierror = 0; 1147 1148 SCIP_CALL( SCIPgetNLPStatistics(heurdata->subscip, &nlpstatistics) ); 1149 1150 SCIPdebugMsg(scip, "NLP solver used %d iterations and %g seconds; violation cons %g, bounds %g\n", 1151 nlpstatistics.niterations, nlpstatistics.totaltime, nlpstatistics.consviol, nlpstatistics.boundviol); 1152 1153 heurdata->iterused += nlpstatistics.niterations; 1154 ++heurdata->nnlpsolves; 1155 if( SCIPgetNLPTermstat(heurdata->subscip) == SCIP_NLPTERMSTAT_OKAY ) 1156 { 1157 ++heurdata->nnlpsolvesokay; 1158 heurdata->iterusedokay += nlpstatistics.niterations; 1159 1160 if( (SCIPgetNLPSolstat(heurdata->subscip) == SCIP_NLPSOLSTAT_GLOBINFEASIBLE) || (SCIPgetNLPSolstat(heurdata->subscip) == SCIP_NLPSOLSTAT_LOCINFEASIBLE) ) 1161 ++heurdata->nnlpsolvesinfeas; 1162 } 1163 else if( SCIPgetNLPTermstat(heurdata->subscip) == SCIP_NLPTERMSTAT_ITERLIMIT ) 1164 { 1165 ++heurdata->nnlpsolvesiterlim; 1166 heurdata->iterusediterlim = MAX(heurdata->iterusediterlim, nlpstatistics.niterations); 1167 } 1168 1169 if( SCIPgetNLPSolstat(heurdata->subscip) > SCIP_NLPSOLSTAT_FEASIBLE ) 1170 return SCIP_OKAY; 1171 1172 /* create SCIP solution, check whether feasible, and try adding to SCIP (if resultsol==NULL) */ 1173 SCIP_CALL( processNLPSol(scip, heur, authorheur, result, resultsol) ); 1174 1175 if( *result == SCIP_FOUNDSOL || !SCIPisLE(scip, SCIPgetNLPObjval(heurdata->subscip), SCIPgetUpperbound(scip)) ) 1176 return SCIP_OKAY; 1177 1178 /* if solution was not added to SCIP, then either 1179 * - the objective function value was not good enough, 1180 * - the NLP was missing some constraints of the original CIP, or 1181 * - the solution is feasible for the presolved CIP, but slightly infeasible for the unpresolved problem 1182 * 1183 * The first case we can check easily (see if() above). 1184 * For the last case, we try whether tightening the feasibility tolerance for the NLP solve may help. 1185 * If that doesn't help, we guess that we are in the second case and will not try a tighter feastol anymore. 1186 */ 1187 1188 /* if we tried with a tighter feastol before, but solution was still not accepted, then don't try again */ 1189 if( heurdata->tighterfeastolfailed ) 1190 return SCIP_OKAY; 1191 1192 /* if resolve with tighter feastol is disabled, then don't do anything */ 1193 if( heurdata->feastolfactor == 1.0 ) 1194 return SCIP_OKAY; 1195 1196 /* if we have already used a tighter feastol, then give up */ 1197 if( heurdata->feastol < SCIPfeastol(scip) ) 1198 return SCIP_OKAY; 1199 1200 /* if original CIP is continuous, then we have not done any presolve, so it shouldn't have caused problems */ 1201 if( heurdata->continuous ) 1202 return SCIP_OKAY; 1203 1204 /* if solution is NLP-feasible for a tightened tolerance already, then there is no use in resolving with that tighter feastol */ 1205 if( MAX(nlpstatistics.consviol, nlpstatistics.boundviol) <= heurdata->feastolfactor * heurdata->feastol ) 1206 return SCIP_OKAY; 1207 1208 /* let the NLP solver redo its magic 1209 * as iterlimit, we use the number of iterations it took for the first solve, or itermin 1210 */ 1211 SCIPdebugMsg(scip, "start NLP solve with iteration limit %d\n", calcIterLimit(scip, heurdata)); 1212 SCIP_CALL( SCIPsolveNLP(heurdata->subscip, 1213 .iterlimit = MAX(heurdata->itermin, nlpstatistics.niterations), 1214 .opttol = heurdata->opttol, 1215 .feastol = heurdata->feastolfactor * heurdata->feastol, 1216 .verblevel = (unsigned short)heurdata->nlpverblevel, 1217 .warmstart = TRUE 1218 ) ); /*lint !e666*/ 1219 1220 SCIPdebugMsg(scip, "NLP solver returned with termination status %d and solution status %d, objective value is %g\n", 1221 SCIPgetNLPTermstat(heurdata->subscip), SCIPgetNLPSolstat(heurdata->subscip), SCIPgetNLPObjval(heurdata->subscip)); 1222 1223 /* add NLP solve statistics from subscip to main SCIP again, so they show up in final statistics */ 1224 SCIPmergeNLPIStatistics(heurdata->subscip, scip, heurdata->continuous); 1225 1226 /* some serious problem: just pretend it didn't happen */ 1227 if( SCIPgetNLPTermstat(heurdata->subscip) >= SCIP_NLPTERMSTAT_OUTOFMEMORY ) 1228 return SCIP_OKAY; 1229 1230 SCIP_CALL( SCIPgetNLPStatistics(heurdata->subscip, &nlpstatistics) ); 1231 SCIPdebugMsg(scip, "NLP solver used %d iterations and %g seconds; violation cons %g, bounds %g\n", 1232 nlpstatistics.niterations, nlpstatistics.totaltime, nlpstatistics.consviol, nlpstatistics.boundviol); 1233 1234 /* we account only the extra iterations for this unusual NLP solve, but don't add anything else to our statistics (nnlpsolved, etc) */ 1235 heurdata->iterused += nlpstatistics.niterations; 1236 1237 /* if failed to get a feasible NLP solution now, then nothing to do */ 1238 if( SCIPgetNLPSolstat(heurdata->subscip) > SCIP_NLPSOLSTAT_FEASIBLE ) 1239 return SCIP_OKAY; 1240 1241 SCIP_CALL( processNLPSol(scip, heur, authorheur, result, resultsol) ); 1242 1243 /* if successful, then use tighter feastol for all NLP solves from now on 1244 * if still not accepted, then don't try this again 1245 * (maybe the NLP is incomplete; we could give up on running this heur completely, but for now let the successrate factor in heurExec take care of running it less often) 1246 */ 1247 if( *result == SCIP_FOUNDSOL ) 1248 heurdata->feastol *= heurdata->feastolfactor; 1249 else 1250 heurdata->tighterfeastolfailed = TRUE; 1251 1252 return SCIP_OKAY; 1253 } 1254 1255 1256 /** adds a set covering or bound disjunction constraint to the original problem */ 1257 static 1258 SCIP_RETCODE forbidFixation( 1259 SCIP* scip, /**< SCIP data structure */ 1260 SCIP_HEURDATA* heurdata /**< heuristic data */ 1261 ) 1262 { 1263 SCIP_VAR** subvars; 1264 int nsubvars; 1265 int nsubbinvars; 1266 int nsubintvars; 1267 SCIP_VAR* var; 1268 SCIP_VAR* subvar; 1269 SCIP_CONS* cons; 1270 SCIP_VAR** consvars; 1271 int nconsvars; 1272 char name[SCIP_MAXSTRLEN]; 1273 int i; 1274 SCIP_Real fixval; 1275 1276 assert(scip != NULL); 1277 1278 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nsubvars, &nsubbinvars, &nsubintvars, NULL, NULL) ); 1279 assert(nsubvars == heurdata->nsubvars); 1280 1281 if( nsubbinvars == 0 && nsubintvars == 0 ) 1282 { 1283 /* If we did not fix any discrete variables but found the "sub"CIP infeasible, then also the CIP is infeasible. */ 1284 SCIPdebugMsg(scip, "heur_subnlp found subCIP infeasible after fixing no variables, something is strange here...\n"); 1285 return SCIP_OKAY; 1286 } 1287 1288 /* initialize */ 1289 cons = NULL; 1290 consvars = NULL; 1291 1292 /* create constraint name */ 1293 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "subnlp_cutoff"); 1294 1295 /* if all discrete variables in the CIP are binary, then we create a set covering constraint 1296 * sum_{x_i fixed at 0} x_i + sum_{x_i fixed at 1} ~x_i >= 1 1297 */ 1298 if( nsubintvars == 0 ) 1299 { 1300 /* allocate memory for constraint variables */ 1301 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nsubbinvars) ); 1302 1303 /* get fixations of discrete variables 1304 * to be sure, we take the values that were put into the subCIP before 1305 */ 1306 nconsvars = 0; 1307 for( i = nsubbinvars - 1; i >= 0; --i ) 1308 { 1309 subvar = subvars[i]; 1310 assert(SCIPvarGetProbindex(subvar) == i); 1311 1312 var = heurdata->var_subscip2scip[i]; 1313 assert(var != NULL || SCIPisEQ(scip, SCIPvarGetLbGlobal(subvar), SCIPvarGetUbGlobal(subvar))); /* otherwise we should have exited in the variable fixation loop */ 1314 if( var == NULL ) 1315 continue; 1316 1317 fixval = SCIPvarGetLbGlobal(subvar); 1318 assert(fixval == SCIPvarGetUbGlobal(subvar)); /* variable should be fixed in sub-SCIP */ /*lint !e777*/ 1319 assert(fixval == 0.0 || fixval == 1.0); /* we have rounded values before fixing */ 1320 1321 if( fixval == 0.0 ) 1322 { 1323 /* variable fixed at lower bound */ 1324 consvars[nconsvars] = var; 1325 } 1326 else 1327 { 1328 SCIP_CALL( SCIPgetNegatedVar(scip, var, &consvars[nconsvars]) ); 1329 } 1330 1331 ++nconsvars; 1332 } 1333 1334 /* create conflict constraint 1335 * In undercover, ConsLogicor is used, since then the inequality is not added to the LP. 1336 * However, I may want to use Setcover to avoid that the same fixing is computed by some LP based heuristic again. 1337 */ 1338 SCIP_CALL( SCIPcreateConsSetcover(scip, &cons, name, nconsvars, consvars, 1339 FALSE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) ); 1340 } 1341 else 1342 { 1343 /* if there are also integer variable, then create a bound disjunction constraint 1344 * x_1 >= fixval_1 + 1 || x_1 <= fixval_1 - 1 || x_2 >= fixval_2 + 1 || x_2 <= fixval_2 - 1 || ... 1345 */ 1346 SCIP_BOUNDTYPE* boundtypes; 1347 SCIP_Real* bounds; 1348 1349 /* allocate memory for constraint variables, boundtypes, and bounds 1350 * (there should be at most two literals for each integer variable) 1351 */ 1352 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nsubbinvars + 2*nsubintvars) ); 1353 SCIP_CALL( SCIPallocBufferArray(scip, &boundtypes, nsubbinvars + 2*nsubintvars) ); 1354 SCIP_CALL( SCIPallocBufferArray(scip, &bounds, nsubbinvars + 2*nsubintvars) ); 1355 1356 /* get fixations of discrete variables 1357 * to be sure, we take the values that were put into the subCIP before 1358 */ 1359 nconsvars = 0; 1360 for( i = nsubbinvars + nsubintvars - 1; i >= 0; --i ) 1361 { 1362 subvar = subvars[i]; 1363 assert(SCIPvarGetProbindex(subvar) == i); 1364 1365 var = heurdata->var_subscip2scip[i]; 1366 assert(var != NULL || SCIPisEQ(scip, SCIPvarGetLbGlobal(subvar), SCIPvarGetUbGlobal(subvar))); /* otherwise we should have exited in the variable fixation loop */ 1367 1368 if( var == NULL ) 1369 continue; 1370 1371 fixval = SCIPvarGetLbGlobal(subvar); 1372 assert(fixval == SCIPvarGetUbGlobal(subvar)); /* variable should be fixed in sub-SCIP */ /*lint !e777*/ 1373 assert(SCIPceil(scip, fixval - 0.5) == fixval); /* we have rounded values before fixing */ /*lint !e777*/ 1374 assert(SCIPvarGetType(var) != SCIP_VARTYPE_BINARY || SCIPvarGetLbGlobal(var) == fixval || SCIPvarGetUbGlobal(var) == fixval); /* for binaries, the fixval should be either 0.0 or 1.0 */ /*lint !e777*/ 1375 1376 if( SCIPvarGetLbGlobal(var) < fixval ) 1377 { 1378 assert(nconsvars < nsubbinvars + 2*nsubintvars); 1379 1380 /* literal x_i <= fixval-1 */ 1381 boundtypes[nconsvars] = SCIP_BOUNDTYPE_UPPER; 1382 bounds[nconsvars] = fixval - 1.0; 1383 consvars[nconsvars] = var; 1384 ++nconsvars; 1385 } 1386 1387 if( SCIPvarGetUbGlobal(var) > fixval ) 1388 { 1389 assert(nconsvars < nsubbinvars + 2*nsubintvars); 1390 1391 /* literal x_i >= fixval+1 */ 1392 boundtypes[nconsvars] = SCIP_BOUNDTYPE_LOWER; 1393 bounds[nconsvars] = fixval + 1.0; 1394 consvars[nconsvars] = var; 1395 ++nconsvars; 1396 } 1397 } 1398 1399 /* create conflict constraint */ 1400 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &cons, name, nconsvars, consvars, boundtypes, bounds, 1401 FALSE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) ); 1402 1403 SCIPfreeBufferArray(scip, &bounds); 1404 SCIPfreeBufferArray(scip, &boundtypes); 1405 SCIPfreeBufferArray(scip, &consvars); 1406 } 1407 1408 /* add and release constraint if created successfully */ 1409 if( cons != NULL ) 1410 { 1411 SCIPdebugMsg(scip, "adding constraint to forbid fixation in main problem\n"); 1412 /* SCIPdebugPrintCons(scip, cons, NULL); */ 1413 SCIP_CALL( SCIPaddCons(scip, cons) ); 1414 SCIP_CALL( SCIPreleaseCons(scip, &cons) ); 1415 } 1416 1417 /* free memory */ 1418 SCIPfreeBufferArrayNull(scip, &consvars); 1419 1420 return SCIP_OKAY; 1421 } 1422 1423 1424 /* 1425 * Callback methods of primal heuristic 1426 */ 1427 1428 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 1429 static 1430 SCIP_DECL_HEURCOPY(heurCopySubNlp) 1431 { /*lint --e{715}*/ 1432 assert(scip != NULL); 1433 assert(heur != NULL); 1434 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 1435 1436 /* call inclusion method of primal heuristic */ 1437 SCIP_CALL( SCIPincludeHeurSubNlp(scip) ); 1438 1439 return SCIP_OKAY; 1440 } 1441 1442 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 1443 static 1444 SCIP_DECL_HEURFREE(heurFreeSubNlp) 1445 { 1446 SCIP_HEURDATA* heurdata; 1447 assert(scip != NULL); 1448 assert(heur != NULL); 1449 1450 heurdata = SCIPheurGetData(heur); 1451 assert(heurdata != NULL); 1452 assert(heurdata->subscip == NULL); 1453 assert(heurdata->var_subscip2scip == NULL); 1454 assert(heurdata->var_scip2subscip == NULL); 1455 assert(heurdata->startcand == NULL); 1456 1457 SCIPfreeBlockMemory(scip, &heurdata); 1458 1459 return SCIP_OKAY; 1460 } 1461 1462 /** initialization method of primal heuristic (called after problem was transformed) */ 1463 static 1464 SCIP_DECL_HEURINIT(heurInitSubNlp) 1465 { /*lint --e{715}*/ 1466 SCIP_HEURDATA* heurdata; 1467 1468 assert(scip != NULL); 1469 assert(heur != NULL); 1470 1471 heurdata = SCIPheurGetData(heur); 1472 assert(heurdata != NULL); 1473 assert(heurdata->subscip == NULL); 1474 1475 /* reset or initialize some flags and counters */ 1476 heurdata->feastol = SCIPfeastol(scip); 1477 heurdata->tighterfeastolfailed = FALSE; 1478 heurdata->triedsetupsubscip = FALSE; 1479 heurdata->nseriousnlpierror = 0; 1480 heurdata->iterused = 0; 1481 heurdata->iterusedokay = 0; 1482 heurdata->iterusediterlim = 0; 1483 heurdata->nnlpsolves = 0; 1484 heurdata->nnlpsolvesokay = 0; 1485 heurdata->nnlpsolvesiterlim = 0; 1486 heurdata->nnlpsolvesinfeas = 0; 1487 1488 return SCIP_OKAY; 1489 } 1490 1491 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */ 1492 static 1493 SCIP_DECL_HEURINITSOL(heurInitsolSubNlp) 1494 { 1495 assert(scip != NULL); 1496 assert(heur != NULL); 1497 1498 /* if the heuristic is called at the root node, we want to be called directly after the initial root LP solve */ 1499 if( SCIPheurGetFreqofs(heur) == 0 ) 1500 SCIPheurSetTimingmask(heur, SCIP_HEURTIMING_DURINGLPLOOP | HEUR_TIMING); 1501 1502 return SCIP_OKAY; 1503 } 1504 1505 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */ 1506 static 1507 SCIP_DECL_HEUREXITSOL(heurExitsolSubNlp) 1508 { 1509 SCIP_HEURDATA* heurdata; 1510 assert(scip != NULL); 1511 assert(heur != NULL); 1512 1513 /* get heuristic's data */ 1514 heurdata = SCIPheurGetData(heur); 1515 assert(heurdata != NULL); 1516 1517 if( heurdata->subscip != NULL ) 1518 { 1519 SCIP_CALL( freeSubSCIP(scip, heurdata) ); 1520 heurdata->triedsetupsubscip = FALSE; 1521 } 1522 1523 /* free start candidate */ 1524 if( heurdata->startcand != NULL ) 1525 { 1526 SCIP_CALL( SCIPfreeSol(scip, &heurdata->startcand) ); 1527 } 1528 1529 SCIPheurSetTimingmask(heur, HEUR_TIMING); 1530 1531 return SCIP_OKAY; 1532 } 1533 1534 1535 /** execution method of primal heuristic */ 1536 static 1537 SCIP_DECL_HEUREXEC(heurExecSubNlp) 1538 { /*lint --e{666,715}*/ 1539 SCIP_HEURDATA* heurdata; 1540 SCIP_Bool runheur; 1541 SCIP_Real itercontingent; 1542 1543 assert(scip != NULL); 1544 assert(heur != NULL); 1545 1546 /* obviously, we did not do anything yet */ 1547 *result = SCIP_DIDNOTRUN; 1548 1549 /* get heuristic's data */ 1550 heurdata = SCIPheurGetData(heur); 1551 assert(heurdata != NULL); 1552 1553 /* if triedsetupsubscip and keepcopy and subscip == NULL, then we tried to setup a subSCIP before, but failed due to some serious error 1554 * thus, we should do not need to try again 1555 * 1556 * otherwise, we continue and let SCIPapplyHeurSubNlp try to create subscip 1557 */ 1558 if( heurdata->subscip == NULL && heurdata->keepcopy && heurdata->triedsetupsubscip ) 1559 return SCIP_OKAY; 1560 1561 /* before we run the heuristic for the first time, check whether we want to run the heuristic at all */ 1562 if( SCIPheurGetNCalls(heur) == 0 ) 1563 { 1564 SCIP_CALL( runHeuristic(scip, &runheur) ); 1565 if( !runheur ) 1566 return SCIP_OKAY; 1567 } 1568 1569 if( heurdata->startcand == NULL ) 1570 { 1571 /* if no start candidate is given, we consider the LP solution of the current node */ 1572 1573 /* however, if the node was already detected to be infeasible, then there is no point to look at its LP solution */ 1574 if( nodeinfeasible ) 1575 return SCIP_OKAY; 1576 1577 /* at least if we are not called the first time, we call the heuristic only if an optimal LP solution is available 1578 * if we are called the first time and the LP is unbounded, then we are quite desperate and still give the NLP a try 1579 */ 1580 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL ) 1581 { 1582 if( SCIPgetNNodes(scip) > 1 || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_UNBOUNDEDRAY ) 1583 { 1584 *result = SCIP_DELAYED; 1585 SCIPdebugMsg(scip, "NLP heuristic delayed because no start candidate given and no LP solution available; LP status = %d\n", SCIPgetLPSolstat(scip)); 1586 return SCIP_OKAY; 1587 } 1588 else 1589 { 1590 SCIPdebugMsg(scip, "LP is unbounded in root node, so we are quite desperate; run NLP heuristic and pray\n"); 1591 } 1592 } 1593 else if( SCIPgetNLPBranchCands(scip) > 0 ) 1594 { 1595 /* only call heuristic, if there are no fractional variables */ 1596 *result = SCIP_DELAYED; 1597 SCIPdebugMsg(scip, "NLP heuristic delayed because no start candidate given and current LP solution is fractional\n"); 1598 return SCIP_OKAY; 1599 } 1600 else if( !SCIPisInfinity(scip, SCIPgetPrimalbound(scip)) && SCIPisEQ(scip, SCIPgetLocalDualbound(scip), SCIPgetPrimalbound(scip)) ) 1601 { 1602 /* only call heuristic, if there is still room for improvement in the current node */ 1603 SCIPdebugMsg(scip, "NLP heuristic delayed because lower and upper bound coincide in current node\n"); 1604 return SCIP_OKAY; 1605 } 1606 SCIPdebugMsg(scip, "using current LP solution as startcand\n"); 1607 } 1608 else 1609 { 1610 SCIPdebugMsg(scip, "have startcand from heur %s\n", SCIPsolGetHeur(heurdata->startcand) ? SCIPheurGetName(SCIPsolGetHeur(heurdata->startcand)) : "NULL"); 1611 } 1612 1613 /* check if enough nodes have been processed so that we want to run the heuristic again */ 1614 1615 /* compute the contingent on number of iterations that the NLP solver is allowed to use 1616 * we make it depending on the current number of processed nodes 1617 */ 1618 itercontingent = heurdata->nodesfactor * (SCIPgetNNodes(scip) + heurdata->nodesoffset); 1619 /* weight by previous success of heuristic if we have been running already 1620 * require at least ninitsolves many runs that didn't run into the NLP iterlimit 1621 * (so if we are still in the phase of finding a good iterlimit, do not consider success rate so far) 1622 */ 1623 if( heurdata->successrateexp > 0.0 && SCIPheurGetNCalls(heur) - heurdata->nnlpsolvesiterlim >= heurdata->ninitsolves ) 1624 itercontingent *= pow((SCIPheurGetNSolsFound(heur) + 1.0) / (SCIPheurGetNCalls(heur) + 1.0), heurdata->successrateexp); 1625 /* subtract the number of iterations used for all NLP solves so far */ 1626 itercontingent -= heurdata->iterused; 1627 1628 /* check whether the itercontingent is sufficient for the iteration limit we would use */ 1629 if( itercontingent < calcIterLimit(scip, heurdata) ) 1630 { 1631 /* not enough iterations left to start NLP solver */ 1632 SCIPdebugMsg(scip, "skip NLP heuristic; contingent=%f; iterlimit=%d; success ratio=%g\n", 1633 itercontingent, calcIterLimit(scip, heurdata), pow((SCIPheurGetNSolsFound(heur) + 1.0) / (SCIPheurGetNCalls(heur) + 1.0), heurdata->successrateexp)); 1634 return SCIP_OKAY; 1635 } 1636 1637 /* so far we have not found any solution, but now we are willing to search for one */ 1638 *result = SCIP_DIDNOTFIND; 1639 1640 if( heurdata->nlpverblevel >= 1 ) 1641 { 1642 SCIPinfoMessage(scip, NULL, "calling subnlp heuristic\n"); 1643 } 1644 1645 SCIP_CALL( SCIPapplyHeurSubNlp(scip, heur, result, heurdata->startcand, NULL) ); 1646 1647 /* SCIP does not like cutoff as return, so we say didnotfind, since we did not find a solution */ 1648 if( *result == SCIP_CUTOFF ) 1649 *result = SCIP_DIDNOTFIND; 1650 1651 /* forget startcand */ 1652 if( heurdata->startcand != NULL ) 1653 { 1654 SCIP_CALL( SCIPfreeSol(scip, &heurdata->startcand) ); 1655 } 1656 1657 /* reset timing, if it was changed temporary (at the root node) */ 1658 if( heurtiming != HEUR_TIMING ) 1659 SCIPheurSetTimingmask(heur, HEUR_TIMING); 1660 1661 return SCIP_OKAY; 1662 } 1663 1664 1665 /* 1666 * primal heuristic specific interface methods 1667 */ 1668 1669 /** creates the NLP local search primal heuristic and includes it in SCIP */ 1670 SCIP_RETCODE SCIPincludeHeurSubNlp( 1671 SCIP* scip /**< SCIP data structure */ 1672 ) 1673 { 1674 SCIP_HEURDATA* heurdata; 1675 SCIP_HEUR* heur; 1676 1677 /* create Nlp primal heuristic data */ 1678 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 1679 BMSclearMemory(heurdata); 1680 1681 /* include variable event handler */ 1682 heurdata->eventhdlr = NULL; 1683 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &heurdata->eventhdlr, HEUR_NAME, "propagates a global bound change to the sub-SCIP", 1684 processVarEvent, NULL) ); 1685 assert(heurdata->eventhdlr != NULL); 1686 1687 /* include primal heuristic */ 1688 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 1689 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 1690 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecSubNlp, heurdata) ); 1691 1692 assert(heur != NULL); 1693 1694 /* set non-NULL pointers to callback methods */ 1695 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopySubNlp) ); 1696 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeSubNlp) ); 1697 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitSubNlp) ); 1698 SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolSubNlp) ); 1699 SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolSubNlp) ); 1700 1701 /* add Nlp primal heuristic parameters */ 1702 SCIP_CALL( SCIPaddIntParam (scip, "heuristics/" HEUR_NAME "/nlpverblevel", 1703 "verbosity level of NLP solver", 1704 &heurdata->nlpverblevel, FALSE, 0, 0, USHRT_MAX, NULL, NULL) ); 1705 1706 SCIP_CALL( SCIPaddIntParam (scip, "heuristics/" HEUR_NAME "/nodesoffset", 1707 "number of nodes added to the current number of nodes when computing itercontingent (higher value runs heuristic more often in early search)", 1708 &heurdata->nodesoffset, FALSE, 1600, 0, INT_MAX, NULL, NULL) ); 1709 1710 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesfactor", 1711 "factor on number of nodes in SCIP (plus nodesoffset) to compute itercontingent (higher value runs heuristics more frequently)", 1712 &heurdata->nodesfactor, FALSE, 0.3, 0.0, SCIPinfinity(scip), NULL, NULL) ); 1713 1714 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/successrateexp", 1715 "exponent for power of success rate to be multiplied with itercontingent (lower value decreases impact of success rate)", 1716 &heurdata->successrateexp, FALSE, 1.0, 0.0, DBL_MAX, NULL, NULL) ); 1717 1718 SCIP_CALL( SCIPaddIntParam (scip, "heuristics/" HEUR_NAME "/iterinit", 1719 "number of iterations used for initial NLP solves", 1720 &heurdata->iterinit, FALSE, 300, 0, INT_MAX, NULL, NULL) ); 1721 1722 SCIP_CALL( SCIPaddIntParam (scip, "heuristics/" HEUR_NAME "/ninitsolves", 1723 "number of successful NLP solves until switching to iterlimit guess and using success rate", 1724 &heurdata->ninitsolves, FALSE, 2, 0, INT_MAX, NULL, NULL) ); 1725 1726 SCIP_CALL( SCIPaddIntParam (scip, "heuristics/" HEUR_NAME "/itermin", 1727 "minimal number of iterations for NLP solves", 1728 &heurdata->itermin, FALSE, 20, 0, INT_MAX, NULL, NULL) ); 1729 1730 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/opttol", 1731 "absolute optimality tolerance to use for NLP solves", 1732 &heurdata->opttol, TRUE, SCIPdualfeastol(scip), 0.0, 1.0, NULL, NULL) ); 1733 1734 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/feastolfactor", 1735 "factor on SCIP feasibility tolerance for NLP solves if resolving when NLP solution not feasible in CIP", 1736 &heurdata->feastolfactor, FALSE, 0.1, 0.0, 1.0, NULL, NULL) ); 1737 1738 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxpresolverounds", 1739 "limit on number of presolve rounds in sub-SCIP (-1 for unlimited, 0 for no presolve)", 1740 &heurdata->maxpresolverounds, FALSE, -1, -1, INT_MAX, NULL, NULL) ); 1741 1742 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/presolveemphasis", 1743 "presolve emphasis in sub-SCIP (0: default, 1: aggressive, 2: fast, 3: off)", 1744 &heurdata->presolveemphasis, FALSE, (int)SCIP_PARAMSETTING_FAST, (int)SCIP_PARAMSETTING_DEFAULT, (int)SCIP_PARAMSETTING_OFF, NULL, NULL) ); 1745 1746 SCIP_CALL( SCIPaddBoolParam (scip, "heuristics/" HEUR_NAME "/setcutoff", 1747 "whether to set cutoff in sub-SCIP to current primal bound", 1748 &heurdata->setcutoff, FALSE, TRUE, NULL, NULL) ); 1749 1750 SCIP_CALL( SCIPaddBoolParam (scip, "heuristics/" HEUR_NAME "/forbidfixings", 1751 "whether to add constraints that forbid specific fixings that turned out to be infeasible", 1752 &heurdata->forbidfixings, FALSE, FALSE, NULL, NULL) ); 1753 1754 SCIP_CALL( SCIPaddBoolParam (scip, "heuristics/" HEUR_NAME "/keepcopy", 1755 "whether to keep SCIP copy or to create new copy each time heuristic is applied", 1756 &heurdata->keepcopy, TRUE, TRUE, NULL, NULL) ); 1757 1758 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/expectinfeas", 1759 "percentage of NLP solves with infeasible status required to tell NLP solver to expect an infeasible NLP", 1760 &heurdata->expectinfeas, FALSE, 0.0, 0.0, 1.0, NULL, NULL) ); 1761 1762 return SCIP_OKAY; 1763 } 1764 1765 /** main procedure of the subNLP heuristic */ 1766 SCIP_RETCODE SCIPapplyHeurSubNlp( 1767 SCIP* scip, /**< original SCIP data structure */ 1768 SCIP_HEUR* heur, /**< heuristic data structure */ 1769 SCIP_RESULT* result, /**< pointer to store result of: did not run, solution found, no solution found, or fixing is infeasible (cutoff) */ 1770 SCIP_SOL* refpoint, /**< point to take fixation of discrete variables from, and startpoint for NLP solver; if NULL, then LP solution is used */ 1771 SCIP_SOL* resultsol /**< a solution where to store found solution values, if any, or NULL if to try adding to SCIP */ 1772 ) 1773 { 1774 SCIP_HEURDATA* heurdata; 1775 SCIP_VAR* var; 1776 SCIP_VAR* subvar; 1777 int i; 1778 SCIP_Real cutoff = SCIPinfinity(scip); 1779 1780 assert(scip != NULL); 1781 assert(heur != NULL); 1782 1783 /* get heuristic's data */ 1784 heurdata = SCIPheurGetData(heur); 1785 assert(heurdata != NULL); 1786 1787 /* try to setup NLP if not tried before */ 1788 if( heurdata->subscip == NULL && !heurdata->triedsetupsubscip ) 1789 { 1790 SCIP_CALL( createSubSCIP(scip, heurdata) ); 1791 } 1792 1793 *result = SCIP_DIDNOTRUN; 1794 1795 /* if subSCIP could not be created, then do not run */ 1796 if( heurdata->subscip == NULL ) 1797 return SCIP_OKAY; 1798 1799 assert(heurdata->nsubvars > 0); 1800 assert(heurdata->var_subscip2scip != NULL); 1801 1802 /* fix discrete variables in sub-SCIP */ 1803 if( !heurdata->continuous ) 1804 { 1805 SCIP_Real fixval; 1806 SCIP_VAR** subvars; 1807 int nsubvars; 1808 int nsubbinvars; 1809 int nsubintvars; 1810 SCIP_Bool infeas; 1811 SCIP_Bool tightened; 1812 1813 /* transform sub-SCIP, so variable fixing are easily undone by free-transform */ 1814 assert(!SCIPisTransformed(heurdata->subscip)); 1815 SCIP_CALL( SCIPtransformProb(heurdata->subscip) ); 1816 1817 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nsubvars, &nsubbinvars, &nsubintvars, NULL, NULL) ); 1818 assert(nsubvars == heurdata->nsubvars); 1819 1820 /* fix discrete variables to values in startpoint */ 1821 for( i = nsubbinvars + nsubintvars - 1; i >= 0; --i ) 1822 { 1823 subvar = subvars[i]; 1824 assert(SCIPvarGetProbindex(subvar) == i); 1825 1826 var = heurdata->var_subscip2scip[i]; 1827 assert(var != NULL); 1828 1829 /* at this point, variables in subscip and in our scip should have same bounds */ 1830 assert(SCIPisEQ(scip, SCIPvarGetLbGlobal(subvar), SCIPvarGetLbGlobal(var))); 1831 assert(SCIPisEQ(scip, SCIPvarGetUbGlobal(subvar), SCIPvarGetUbGlobal(var))); 1832 1833 fixval = SCIPgetSolVal(scip, refpoint, var); 1834 1835 /* only run heuristic on integer feasible points (unless we are on an unbounded LP) */ 1836 if( !SCIPisFeasIntegral(scip, fixval) ) 1837 { 1838 if( refpoint != NULL || SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL ) 1839 { 1840 SCIPdebugMsg(scip, "skip NLP heuristic because start candidate not integer feasible: var <%s> has value %g\n", SCIPvarGetName(var), fixval); 1841 goto CLEANUP; 1842 } 1843 } 1844 /* if we do not really have a startpoint, then we should take care that we do not fix variables to very large values 1845 * thus, we set to 0.0 here and project on bounds below 1846 */ 1847 if( REALABS(fixval) > 1E+10 && refpoint == NULL && SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL ) 1848 fixval = 0.0; 1849 1850 /* fixing variables to infinity causes problems, we should not have been passed such a solution as refpoint */ 1851 assert(!SCIPisInfinity(scip, REALABS(fixval))); 1852 1853 /* round fractional variables to the nearest integer */ 1854 fixval = SCIPround(scip, fixval); 1855 1856 /* adjust value to the global bounds of the corresponding SCIP variable */ 1857 fixval = MAX(fixval, SCIPvarGetLbGlobal(var)); /*lint !e666*/ 1858 fixval = MIN(fixval, SCIPvarGetUbGlobal(var)); /*lint !e666*/ 1859 1860 /* SCIPdebugMsg(scip, "fix variable <%s> to %g\n", SCIPvarGetName(var), fixval); */ 1861 SCIP_CALL( SCIPtightenVarLb(heurdata->subscip, subvar, fixval, TRUE, &infeas, &tightened) ); 1862 if( !infeas ) 1863 { 1864 SCIP_CALL( SCIPtightenVarUb(heurdata->subscip, subvar, fixval, TRUE, &infeas, &tightened) ); 1865 } 1866 if( infeas ) 1867 { 1868 SCIPdebugMsg(scip, "skip NLP heuristic because start candidate not feasible: fixing var <%s> to value %g is infeasible\n", SCIPvarGetName(var), fixval); 1869 goto CLEANUP; 1870 } 1871 } 1872 1873 /* if there is already a solution, possibly add an objective cutoff in sub-SCIP 1874 * we do this here only for problems with discrete variables, since the cutoff may be useful when presolving the subscip 1875 * for the NLP solver, a cutoff is useless at best 1876 */ 1877 if( SCIPgetNSols(scip) > 0 && heurdata->setcutoff ) 1878 { 1879 cutoff = SCIPgetUpperbound(scip); 1880 assert( !SCIPisInfinity(scip, cutoff) ); 1881 1882 SCIP_CALL( SCIPsetObjlimit(heurdata->subscip, cutoff) ); 1883 SCIPdebugMsg(scip, "set objective limit %g\n", cutoff); 1884 } 1885 } 1886 else 1887 { 1888 /* for continuous problems, we should already be in the transformed stage */ 1889 assert(SCIPisTransformed(heurdata->subscip)); 1890 } 1891 1892 /* solve the subNLP and try to add solution to SCIP */ 1893 SCIP_CALL( solveSubNLP(scip, heur, result, refpoint, resultsol) ); 1894 1895 if( heurdata->subscip == NULL ) 1896 { 1897 /* something horrible must have happened that we decided to give up completely on this heuristic */ 1898 *result = SCIP_DIDNOTFIND; 1899 return SCIP_OKAY; 1900 } 1901 1902 if( *result == SCIP_CUTOFF ) 1903 { 1904 if( heurdata->subscipisvalid && SCIPgetNActivePricers(scip) == 0 ) 1905 { 1906 /* if the subNLP is valid and turned out to be globally infeasible (i.e., proven by SCIP), then we forbid this fixation in the main problem */ 1907 if( SCIPisInfinity(scip, cutoff) && heurdata->forbidfixings ) 1908 { 1909 SCIP_CALL( forbidFixation(scip, heurdata) ); 1910 } 1911 } 1912 else 1913 { 1914 /* if the subNLP turned out to be globally infeasible but we are not sure that we have a valid copy, we change to DIDNOTFIND */ 1915 *result = SCIP_DIDNOTFIND; 1916 } 1917 } 1918 1919 CLEANUP: 1920 if( !heurdata->continuous ) 1921 { 1922 SCIP_CALL( SCIPfreeTransform(heurdata->subscip) ); 1923 } 1924 1925 /* if the heuristic was applied before solving has started, then destroy subSCIP, since EXITSOL may not be called 1926 * also if keepcopy is disabled, then destroy subSCIP 1927 */ 1928 if( SCIPgetStage(scip) < SCIP_STAGE_SOLVING || !heurdata->keepcopy ) 1929 { 1930 SCIP_CALL( freeSubSCIP(scip, heurdata) ); 1931 heurdata->triedsetupsubscip = FALSE; 1932 } 1933 1934 return SCIP_OKAY; 1935 } 1936 1937 /** updates the starting point for the NLP heuristic 1938 * 1939 * Is called by a constraint handler that handles nonlinear constraints when a check on feasibility of a solution fails. 1940 */ 1941 SCIP_RETCODE SCIPupdateStartpointHeurSubNlp( 1942 SCIP* scip, /**< SCIP data structure */ 1943 SCIP_HEUR* heur, /**< NLP heuristic */ 1944 SCIP_SOL* solcand, /**< solution candidate */ 1945 SCIP_Real violation /**< constraint violation of solution candidate */ 1946 ) 1947 { 1948 SCIP_HEURDATA* heurdata; 1949 1950 assert(scip != NULL); 1951 assert(heur != NULL); 1952 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 1953 assert(solcand != NULL); 1954 assert(SCIPisPositive(scip, violation)); 1955 1956 /* too early or the game is over already: no more interest in starting points */ 1957 if( SCIPgetStage(scip) != SCIP_STAGE_SOLVING ) 1958 return SCIP_OKAY; 1959 1960 heurdata = SCIPheurGetData(heur); 1961 assert(heurdata != NULL); 1962 1963 if( heurdata->subscip == NULL ) 1964 { 1965 /* if we do not have a sub-SCIP, but tried to set one up before or will never create a subSCIP, then do not need a starting point */ 1966 SCIP_Bool runheur; 1967 if( heurdata->triedsetupsubscip ) 1968 return SCIP_OKAY; 1969 if( SCIPheurGetFreq(heur) < 0 ) 1970 return SCIP_OKAY; 1971 SCIP_CALL( runHeuristic(scip, &runheur) ); 1972 if( !runheur ) 1973 return SCIP_OKAY; 1974 } 1975 1976 /* if the solution is the one we created (last), then it is useless to use it as starting point again 1977 * (we cannot check SCIPsolGetHeur()==heur, as subnlp may not be registered as author of the solution) 1978 */ 1979 if( heurdata->lastsol == solcand ) 1980 return SCIP_OKAY; 1981 1982 SCIPdebugMsg(scip, "consider solution candidate with violation %g and objective %g from %s\n", 1983 violation, SCIPgetSolTransObj(scip, solcand), SCIPsolGetHeur(solcand) ? SCIPheurGetName(SCIPsolGetHeur(solcand)) : "tree"); 1984 1985 /* if we have no point yet, or the new point has a lower constraint violation, or it has a better objective function value, then take the new point */ 1986 if( heurdata->startcand == NULL || violation < heurdata->startcandviol || 1987 SCIPisRelGT(scip, SCIPgetSolTransObj(scip, heurdata->startcand), SCIPgetSolTransObj(scip, solcand)) ) 1988 { 1989 if( heurdata->startcand != NULL ) 1990 { 1991 SCIP_CALL( SCIPfreeSol(scip, &heurdata->startcand) ); 1992 } 1993 SCIP_CALL( SCIPcreateSolCopy(scip, &heurdata->startcand, solcand) ); 1994 SCIP_CALL( SCIPunlinkSol(scip, heurdata->startcand) ); 1995 heurdata->startcandviol = violation; 1996 1997 /* remember which heuristic proposed the candidate */ 1998 SCIPsolSetHeur(heurdata->startcand, SCIPgetSolHeur(scip, solcand)); 1999 } 2000 2001 return SCIP_OKAY; 2002 } 2003 2004 /** gets startpoint candidate to be used in next call to NLP heuristic, or NULL if none */ 2005 SCIP_SOL* SCIPgetStartCandidateHeurSubNlp( 2006 SCIP* scip, /**< original SCIP data structure */ 2007 SCIP_HEUR* heur /**< heuristic data structure */ 2008 ) 2009 { 2010 SCIP_HEURDATA* heurdata; 2011 2012 assert(scip != NULL); 2013 assert(heur != NULL); 2014 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 2015 2016 heurdata = SCIPheurGetData(heur); 2017 assert(heurdata != NULL); 2018 2019 return heurdata->startcand; 2020 } 2021