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_nlpdiving.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief NLP diving heuristic that chooses fixings w.r.t. the fractionalities 28 * @author Timo Berthold 29 * @author Stefan Vigerske 30 */ 31 32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 33 34 #include "blockmemshell/memory.h" 35 #include "scip/heur_nlpdiving.h" 36 #include "scip/heur_subnlp.h" 37 #include "scip/heur_undercover.h" 38 #include "scip/pub_event.h" 39 #include "scip/pub_heur.h" 40 #include "scip/pub_message.h" 41 #include "scip/pub_misc.h" 42 #include "scip/pub_sol.h" 43 #include "scip/pub_var.h" 44 #include "scip/scip_branch.h" 45 #include "scip/scip_copy.h" 46 #include "scip/scip_event.h" 47 #include "scip/scip_general.h" 48 #include "scip/scip_heur.h" 49 #include "scip/scip_lp.h" 50 #include "scip/scip_mem.h" 51 #include "scip/scip_message.h" 52 #include "scip/scip_nlp.h" 53 #include "scip/scip_nlpi.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_probing.h" 59 #include "scip/scip_randnumgen.h" 60 #include "scip/scip_sol.h" 61 #include "scip/scip_solve.h" 62 #include "scip/scip_solvingstats.h" 63 #include "scip/scip_timing.h" 64 #include "scip/scip_tree.h" 65 #include "scip/scip_var.h" 66 #include <string.h> 67 68 #define HEUR_NAME "nlpdiving" 69 #define HEUR_DESC "NLP diving heuristic that chooses fixings w.r.t. the fractionalities" 70 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING 71 #define HEUR_PRIORITY -1003010 72 #define HEUR_FREQ 10 73 #define HEUR_FREQOFS 3 74 #define HEUR_MAXDEPTH -1 75 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE 76 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */ 77 78 /* event handler properties */ 79 #define EVENTHDLR_NAME "Nlpdiving" 80 #define EVENTHDLR_DESC "bound change event handler for " HEUR_NAME " heuristic" 81 82 83 /* 84 * Default parameter settings 85 */ 86 87 #define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */ 88 #define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */ 89 #define DEFAULT_MAXNLPITERABS 200 /**< minimial absolute number of allowed NLP iterations */ 90 #define DEFAULT_MAXNLPITERREL 10 /**< additional allowed number of NLP iterations relative to successfully found solutions */ 91 #define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) 92 * where diving is performed (0.0: no limit) */ 93 #define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) 94 * where diving is performed (0.0: no limit) */ 95 #define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */ 96 #define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */ 97 #define DEFAULT_MINSUCCQUOT 0.1 /**< heuristic will not run if less then this percentage of calls succeeded (0.0: no limit) */ 98 #define DEFAULT_MAXFEASNLPS 10 /**< maximal number of NLPs with feasible solution to solve during one dive */ 99 #define DEFAULT_FIXQUOT 0.2 /**< percentage of fractional variables that should be fixed before the next NLP solve */ 100 #define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */ 101 #define DEFAULT_LP FALSE /**< should the LP relaxation be solved before the NLP relaxation? */ 102 #define DEFAULT_PREFERLPFRACS FALSE /**< prefer variables that are also fractional in LP solution? */ 103 #define DEFAULT_PREFERCOVER TRUE /**< should variables in a minimal cover be preferred? */ 104 #define DEFAULT_SOLVESUBMIP FALSE /**< should a sub-MIP be solved if all cover variables are fixed? */ 105 #define DEFAULT_NLPSTART 's' /**< which point should be used as starting point for the NLP solver? */ 106 #define DEFAULT_VARSELRULE 'd' /**< which variable selection should be used? ('f'ractionality, 'c'oefficient, 107 * 'p'seudocost, 'g'uided, 'd'ouble) 108 */ 109 #define DEFAULT_NLPFASTFAIL TRUE /**< should the NLP solver stop early if it converges slow? */ 110 #define DEFAULT_RANDSEED 97 /**< initial random seed */ 111 112 #define MINNLPITER 10 /**< minimal number of NLP iterations allowed in each NLP solving call */ 113 114 /* locally defined heuristic data */ 115 struct SCIP_HeurData 116 { 117 SCIP_SOL* sol; /**< working solution */ 118 SCIP_Real minreldepth; /**< minimal relative depth to start diving */ 119 SCIP_Real maxreldepth; /**< maximal relative depth to start diving */ 120 int maxnlpiterabs; /**< minimial absolute number of allowed NLP iterations */ 121 int maxnlpiterrel; /**< additional allowed number of NLP iterations relative to successfully found solutions */ 122 SCIP_Real maxdiveubquot; /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) 123 * where diving is performed (0.0: no limit) */ 124 SCIP_Real maxdiveavgquot; /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) 125 * where diving is performed (0.0: no limit) */ 126 SCIP_Real maxdiveubquotnosol; /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */ 127 SCIP_Real maxdiveavgquotnosol;/**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */ 128 int maxfeasnlps; /**< maximal number of NLPs with feasible solution to solve during one dive */ 129 SCIP_Real minsuccquot; /**< heuristic will not run if less then this percentage of calls succeeded (0.0: no limit) */ 130 SCIP_Real fixquot; /**< percentage of fractional variables that should be fixed before the next NLP solve */ 131 SCIP_Bool backtrack; /**< use one level of backtracking if infeasibility is encountered? */ 132 SCIP_Bool lp; /**< should the LP relaxation be solved before the NLP relaxation? */ 133 SCIP_Bool preferlpfracs; /**< prefer variables that are also fractional in LP solution? */ 134 SCIP_Bool prefercover; /**< should variables in a minimal cover be preferred? */ 135 SCIP_Bool solvesubmip; /**< should a sub-MIP be solved if all cover variables are fixed? */ 136 SCIP_Bool nlpfastfail; /**< should the NLP solver stop early if it converges slow? */ 137 char nlpstart; /**< which point should be used as starting point for the NLP solver? */ 138 char varselrule; /**< which variable selection should be used? ('f'ractionality, 'c'oefficient, 139 * 'p'seudocost, 'g'uided, 'd'ouble) 140 */ 141 142 int nnlpiterations; /**< NLP iterations used in this heuristic */ 143 int nsuccess; /**< number of runs that produced at least one feasible solution */ 144 int nfixedcovervars; /**< number of variables in the cover that are already fixed */ 145 #ifdef SCIP_STATISTIC 146 int nnlpsolves; /**< number of NLP solves */ 147 int nfailcutoff; /**< number of fails due to cutoff */ 148 int nfaildepth; /**< number of fails due to too deep */ 149 int nfailnlperror; /**< number of fails due to NLP error */ 150 #endif 151 SCIP_EVENTHDLR* eventhdlr; /**< event handler for bound change events */ 152 SCIP_RANDNUMGEN* randnumgen; /**< random number generator */ 153 }; 154 155 156 /* 157 * local methods 158 */ 159 160 /** gets fractional variables of last NLP solution along with solution values and fractionalities 161 * 162 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 163 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 164 * 165 * @pre This method can be called if SCIP is in one of the following stages: 166 * - \ref SCIP_STAGE_INITSOLVE 167 * - \ref SCIP_STAGE_SOLVING 168 */ 169 static 170 SCIP_RETCODE getNLPFracVars( 171 SCIP* scip, /**< SCIP data structure */ 172 SCIP_HEURDATA* heurdata, /**< heuristic data structure */ 173 SCIP_VAR*** nlpcands, /**< pointer to store the array of NLP fractional variables, or NULL */ 174 SCIP_Real** nlpcandssol, /**< pointer to store the array of NLP fractional variables solution values, or NULL */ 175 SCIP_Real** nlpcandsfrac, /**< pointer to store the array of NLP fractional variables fractionalities, or NULL */ 176 int* nnlpcands /**< pointer to store the number of NLP fractional variables , or NULL */ 177 ) 178 { 179 int c; 180 181 assert(scip != NULL); 182 assert(heurdata != NULL); 183 assert(nlpcands != NULL); 184 assert(nlpcandssol != NULL); 185 assert(nlpcandsfrac != NULL); 186 assert(nnlpcands != NULL); 187 188 /* get fractional variables that should be integral */ 189 SCIP_CALL( SCIPgetNLPFracVars(scip, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, NULL) ); 190 191 /* values may be outside the domain in exact arithmetic, but inside the domain within relative tolerance, and still 192 * slightly fractional, because SCIPisFeasIntegral() uses absolute tolerance; project value onto domain to avoid this 193 * (example: primsol=29.99999853455704, lower bound = 30) 194 */ 195 for( c = 0; c < *nnlpcands; ++c ) 196 { 197 assert(!SCIPisFeasIntegral(scip, (*nlpcandssol)[c])); 198 199 if( (*nlpcandssol)[c] < SCIPvarGetLbLocal((*nlpcands)[c]) || (*nlpcandssol)[c] > SCIPvarGetUbLocal((*nlpcands)[c]) ) 200 { 201 SCIP_Real newval; 202 203 newval = ((*nlpcandssol)[c] < SCIPvarGetLbLocal((*nlpcands)[c])) 204 ? SCIPvarGetLbLocal((*nlpcands)[c]) - 0.5*SCIPfeastol(scip) 205 : SCIPvarGetUbLocal((*nlpcands)[c]) + 0.5*SCIPfeastol(scip); 206 207 assert(SCIPisFeasIntegral(scip, newval)); 208 209 SCIP_CALL( SCIPsetSolVal(scip, heurdata->sol, (*nlpcands)[c], newval) ); 210 211 (*nnlpcands)--; 212 213 if( c < *nnlpcands ) 214 { 215 (*nlpcands)[c] = (*nlpcands)[*nnlpcands]; 216 (*nlpcandssol)[c] = (*nlpcandssol)[*nnlpcands]; 217 (*nlpcandsfrac)[c] = (*nlpcandsfrac)[*nnlpcands]; 218 } 219 } 220 } 221 222 /* prefer decisions on variables which are also fractional in LP solution */ 223 if( heurdata->preferlpfracs && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL ) 224 { 225 for( c = 0; c < *nnlpcands; ++c ) 226 { 227 if( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, NULL, (*nlpcands)[c])) ) 228 (*nlpcandsfrac)[c] *= 100.0; 229 } 230 } 231 232 return SCIP_OKAY; 233 } 234 235 /** finds best candidate variable w.r.t. fractionality: 236 * - prefer variables that may not be rounded without destroying NLP feasibility: 237 * - of these variables, round least fractional variable in corresponding direction 238 * - if all remaining fractional variables may be rounded without destroying NLP feasibility: 239 * - round variable with least increasing objective value 240 * - binary variables are prefered 241 * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might 242 * also be prefered if a correpsonding parameter is set 243 */ 244 static 245 SCIP_RETCODE chooseFracVar( 246 SCIP* scip, /**< original SCIP data structure */ 247 SCIP_HEURDATA* heurdata, /**< heuristic data structure */ 248 SCIP_VAR** nlpcands, /**< array of NLP fractional variables */ 249 SCIP_Real* nlpcandssol, /**< array of NLP fractional variables solution values */ 250 SCIP_Real* nlpcandsfrac, /**< array of NLP fractional variables fractionalities */ 251 int nnlpcands, /**< number of NLP fractional variables */ 252 SCIP_HASHMAP* varincover, /**< hash map for variables */ 253 SCIP_Bool covercomputed, /**< has a minimal cover been computed? */ 254 int* bestcand, /**< pointer to store the index of the best candidate variable */ 255 SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */ 256 SCIP_Bool* bestcandroundup /**< pointer to store whether best candidate should be rounded up */ 257 ) 258 { 259 SCIP_Real bestobjgain; 260 SCIP_Real bestfrac; 261 SCIP_Bool bestcandmayrounddown; 262 SCIP_Bool bestcandmayroundup; 263 int c; 264 265 /* check preconditions */ 266 assert(scip != NULL); 267 assert(heurdata != NULL); 268 assert(nlpcands != NULL); 269 assert(nlpcandssol != NULL); 270 assert(nlpcandsfrac != NULL); 271 assert(covercomputed == (varincover != NULL)); 272 assert(bestcand != NULL); 273 assert(bestcandmayround != NULL); 274 assert(bestcandroundup != NULL); 275 276 bestcandmayrounddown = TRUE; 277 bestcandmayroundup = TRUE; 278 bestobjgain = SCIPinfinity(scip); 279 bestfrac = SCIP_INVALID; 280 281 for( c = 0; c < nnlpcands; ++c ) 282 { 283 SCIP_VAR* var; 284 SCIP_Bool mayrounddown; 285 SCIP_Bool mayroundup; 286 SCIP_Bool roundup; 287 SCIP_Real frac; 288 SCIP_Real obj; 289 SCIP_Real objgain; 290 291 var = nlpcands[c]; 292 293 mayrounddown = SCIPvarMayRoundDown(var); 294 mayroundup = SCIPvarMayRoundUp(var); 295 frac = nlpcandsfrac[c]; 296 obj = SCIPvarGetObj(var); 297 298 /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */ 299 if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) ) 300 continue; 301 302 if( mayrounddown || mayroundup ) 303 { 304 /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */ 305 if( bestcandmayrounddown || bestcandmayroundup ) 306 { 307 /* choose rounding direction: 308 * - if variable may be rounded in both directions, round corresponding to the fractionality 309 * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding 310 * the current fractional solution 311 */ 312 if( mayrounddown && mayroundup ) 313 { 314 if( SCIPisEQ(scip, frac, 0.5) ) 315 roundup = (SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0); 316 else 317 roundup = (frac > 0.5); 318 } 319 else 320 roundup = mayrounddown; 321 322 if( roundup ) 323 { 324 frac = 1.0 - frac; 325 objgain = frac*obj; 326 } 327 else 328 objgain = -frac*obj; 329 330 /* penalize too small fractions */ 331 if( SCIPisEQ(scip, frac, 0.01) ) 332 { 333 /* try to avoid variability; decide randomly if the LP solution can contain some noise. 334 * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score. 335 */ 336 if( SCIPrandomGetInt(heurdata->randnumgen, 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 ) 337 objgain *= 1000.0; 338 } 339 else if( frac < 0.01 ) 340 objgain *= 1000.0; 341 342 /* prefer decisions on binary variables */ 343 if( !SCIPvarIsBinary(var) ) 344 objgain *= 1000.0; 345 346 /* prefer decisions on cover variables */ 347 if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) ) 348 objgain *= 1000.0; 349 350 /* check, if candidate is new best candidate */ 351 if( SCIPisLT(scip, objgain, bestobjgain) || (SCIPisEQ(scip, objgain, bestobjgain) && frac < bestfrac) ) 352 { 353 *bestcand = c; 354 bestobjgain = objgain; 355 bestfrac = frac; 356 bestcandmayrounddown = mayrounddown; 357 bestcandmayroundup = mayroundup; 358 *bestcandroundup = roundup; 359 } 360 } 361 } 362 else 363 { 364 /* the candidate may not be rounded */ 365 if( SCIPisEQ(scip, frac, 0.5) ) 366 roundup = (SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0); 367 else if( frac < 0.5 ) 368 roundup = FALSE; 369 else 370 roundup = TRUE; 371 372 /* adjust fractional part */ 373 if( roundup ) 374 frac = 1.0 - frac; 375 376 /* penalize too small fractions */ 377 if( SCIPisEQ(scip, frac, 0.01) ) 378 { 379 /* try to avoid variability; decide randomly if the LP solution can contain some noise. 380 * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score. 381 */ 382 if( SCIPrandomGetInt(heurdata->randnumgen, 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 ) 383 frac += 10.0; 384 } 385 else if( frac < 0.01 ) 386 frac += 10.0; 387 388 /* prefer decisions on binary variables */ 389 if( !SCIPvarIsBinary(var) ) 390 frac *= 1000.0; 391 392 /* prefer decisions on cover variables */ 393 if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) ) 394 frac *= 1000.0; 395 396 /* check, if candidate is new best candidate: prefer unroundable candidates in any case */ 397 if( bestcandmayrounddown || bestcandmayroundup || frac < bestfrac ) 398 { 399 *bestcand = c; 400 bestfrac = frac; 401 bestcandmayrounddown = FALSE; 402 bestcandmayroundup = FALSE; 403 *bestcandroundup = roundup; 404 } 405 assert(bestfrac < SCIP_INVALID); 406 } 407 } 408 409 *bestcandmayround = bestcandmayroundup || bestcandmayrounddown; 410 411 return SCIP_OKAY; 412 } 413 414 /** finds best candidate variable w.r.t. vector length: 415 * - round variable with a small ratio between the increase in the objective and the locking numbers 416 * - binary variables are prefered 417 * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might 418 * also be prefered if a corresponding parameter is set 419 */ 420 static 421 SCIP_RETCODE chooseVeclenVar( 422 SCIP* scip, /**< original SCIP data structure */ 423 SCIP_HEURDATA* heurdata, /**< heuristic data structure */ 424 SCIP_VAR** nlpcands, /**< array of NLP fractional variables */ 425 SCIP_Real* nlpcandssol, /**< array of NLP fractional variables solution values */ 426 SCIP_Real* nlpcandsfrac, /**< array of NLP fractional variables fractionalities */ 427 int nnlpcands, /**< number of NLP fractional variables */ 428 SCIP_HASHMAP* varincover, /**< hash map for variables */ 429 SCIP_Bool covercomputed, /**< has a minimal cover been computed? */ 430 int* bestcand, /**< pointer to store the index of the best candidate variable */ 431 SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */ 432 SCIP_Bool* bestcandroundup /**< pointer to store whether best candidate should be rounded up */ 433 ) 434 { 435 SCIP_Real bestscore; 436 int c; 437 438 /* check preconditions */ 439 assert(scip != NULL); 440 assert(heurdata != NULL); 441 assert(nlpcands != NULL); 442 assert(nlpcandsfrac != NULL); 443 assert(nlpcandssol != NULL); 444 assert(bestcand != NULL); 445 assert(bestcandmayround != NULL); 446 assert(bestcandroundup != NULL); 447 448 *bestcandmayround = TRUE; 449 bestscore = SCIP_REAL_MAX; 450 451 /* get best candidate */ 452 for( c = 0; c < nnlpcands; ++c ) 453 { 454 SCIP_VAR* var; 455 456 SCIP_Real obj; 457 SCIP_Real objdelta; 458 SCIP_Real frac; 459 SCIP_Real score; 460 461 int nlocks; 462 463 SCIP_Bool roundup; 464 465 var = nlpcands[c]; 466 467 /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */ 468 if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) ) 469 continue; 470 471 frac = nlpcandsfrac[c]; 472 obj = SCIPvarGetObj(var); 473 roundup = (obj >= 0.0); 474 objdelta = (roundup ? (1.0-frac)*obj : -frac * obj); 475 assert(objdelta >= 0.0); 476 477 /* check whether the variable is roundable */ 478 *bestcandmayround = *bestcandmayround && (SCIPvarMayRoundDown(var) || SCIPvarMayRoundUp(var)); 479 nlocks = SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) + SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL); 480 481 /* smaller score is better */ 482 score = (objdelta + SCIPsumepsilon(scip))/((SCIP_Real)nlocks+1.0); 483 484 /* prefer decisions on binary variables */ 485 if( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY ) 486 score *= 1000.0; 487 488 /* prefer decisions on cover variables */ 489 if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) ) 490 score *= 1000; 491 492 /* check, if candidate is new best candidate */ 493 if( score < bestscore ) 494 { 495 *bestcand = c; 496 bestscore = score; 497 *bestcandroundup = roundup; 498 } 499 } 500 501 return SCIP_OKAY; 502 } 503 504 505 /** finds best candidate variable w.r.t. locking numbers: 506 * - prefer variables that may not be rounded without destroying LP feasibility: 507 * - of these variables, round variable with least number of locks in corresponding direction 508 * - if all remaining fractional variables may be rounded without destroying LP feasibility: 509 * - round variable with least number of locks in opposite of its feasible rounding direction 510 * - binary variables are prefered 511 * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might 512 * also be prefered if a correpsonding parameter is set 513 */ 514 static 515 SCIP_RETCODE chooseCoefVar( 516 SCIP* scip, /**< original SCIP data structure */ 517 SCIP_HEURDATA* heurdata, /**< heuristic data structure */ 518 SCIP_VAR** nlpcands, /**< array of NLP fractional variables */ 519 SCIP_Real* nlpcandssol, /**< array of NLP fractional variables solution values */ 520 SCIP_Real* nlpcandsfrac, /**< array of NLP fractional variables fractionalities */ 521 int nnlpcands, /**< number of NLP fractional variables */ 522 SCIP_HASHMAP* varincover, /**< hash map for variables */ 523 SCIP_Bool covercomputed, /**< has a minimal cover been computed? */ 524 int* bestcand, /**< pointer to store the index of the best candidate variable */ 525 SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */ 526 SCIP_Bool* bestcandroundup /**< pointer to store whether best candidate should be rounded up */ 527 ) 528 { 529 SCIP_Bool bestcandmayrounddown; 530 SCIP_Bool bestcandmayroundup; 531 int bestnviolrows; /* number of violated rows for best candidate */ 532 SCIP_Real bestcandfrac; /* fractionality of best candidate */ 533 int c; 534 535 /* check preconditions */ 536 assert(scip != NULL); 537 assert(heurdata != NULL); 538 assert(nlpcands != NULL); 539 assert(nlpcandsfrac != NULL); 540 assert(nlpcandssol != NULL); 541 assert(bestcand != NULL); 542 assert(bestcandmayround != NULL); 543 assert(bestcandroundup != NULL); 544 545 bestcandmayrounddown = TRUE; 546 bestcandmayroundup = TRUE; 547 bestnviolrows = INT_MAX; 548 bestcandfrac = SCIP_INVALID; 549 550 /* get best candidate */ 551 for( c = 0; c < nnlpcands; ++c ) 552 { 553 SCIP_VAR* var; 554 555 int nlocksdown; 556 int nlocksup; 557 int nviolrows; 558 559 SCIP_Bool mayrounddown; 560 SCIP_Bool mayroundup; 561 SCIP_Bool roundup; 562 SCIP_Real frac; 563 564 var = nlpcands[c]; 565 mayrounddown = SCIPvarMayRoundDown(var); 566 mayroundup = SCIPvarMayRoundUp(var); 567 frac = nlpcandsfrac[c]; 568 569 /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */ 570 if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) ) 571 continue; 572 573 if( mayrounddown || mayroundup ) 574 { 575 /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */ 576 if( bestcandmayrounddown || bestcandmayroundup ) 577 { 578 /* choose rounding direction: 579 * - if variable may be rounded in both directions, round corresponding to the fractionality 580 * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding 581 * the current fractional solution 582 */ 583 if( mayrounddown && mayroundup ) 584 { 585 if( SCIPisEQ(scip, frac, 0.5) ) 586 roundup = (SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0); 587 else 588 roundup = (frac > 0.5); 589 } 590 else 591 roundup = mayrounddown; 592 593 if( roundup ) 594 { 595 frac = 1.0 - frac; 596 nviolrows = SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL); 597 } 598 else 599 nviolrows = SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL); 600 601 /* penalize too small fractions */ 602 if( SCIPisEQ(scip, frac, 0.01) ) 603 { 604 /* try to avoid variability; decide randomly if the LP solution can contain some noise. 605 * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score. 606 */ 607 if( SCIPrandomGetInt(heurdata->randnumgen, 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 ) 608 nviolrows *= 100; 609 } 610 else if( frac < 0.01 ) 611 nviolrows *= 100; 612 613 /* prefer decisions on binary variables */ 614 if( !SCIPvarIsBinary(var) ) 615 nviolrows *= 1000; 616 617 /* prefer decisions on cover variables */ 618 if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) ) 619 nviolrows *= 1000; 620 621 /* check, if candidate is new best candidate */ 622 assert( (0.0 < frac && frac < 1.0) || SCIPvarIsBinary(var) ); 623 if( nviolrows + frac < bestnviolrows + bestcandfrac ) 624 { 625 *bestcand = c; 626 bestnviolrows = nviolrows; 627 bestcandfrac = frac; 628 bestcandmayrounddown = mayrounddown; 629 bestcandmayroundup = mayroundup; 630 *bestcandroundup = roundup; 631 } 632 } 633 } 634 else 635 { 636 /* the candidate may not be rounded */ 637 nlocksdown = SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL); 638 nlocksup = SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL); 639 640 roundup = (nlocksdown > nlocksup); 641 if( !roundup ) 642 { 643 roundup = (nlocksdown == nlocksup); 644 if( SCIPisEQ(scip, frac, 0.5) ) 645 roundup = (roundup && (SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0)); 646 else 647 roundup = (roundup && frac > 0.5); 648 } 649 650 if( roundup ) 651 { 652 nviolrows = nlocksup; 653 frac = 1.0 - frac; 654 } 655 else 656 nviolrows = nlocksdown; 657 658 /* penalize too small fractions */ 659 if( SCIPisEQ(scip, frac, 0.01) ) 660 { 661 /* try to avoid variability; decide randomly if the LP solution can contain some noise. 662 * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score. 663 */ 664 if( SCIPrandomGetInt(heurdata->randnumgen, 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 ) 665 nviolrows *= 100; 666 } 667 else if( frac < 0.01 ) 668 nviolrows *= 100; 669 670 /* prefer decisions on binary variables */ 671 if( !SCIPvarIsBinary(var) ) 672 nviolrows *= 100; 673 674 /* prefer decisions on cover variables */ 675 if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) ) 676 nviolrows *= 1000; 677 678 /* check, if candidate is new best candidate: prefer unroundable candidates in any case */ 679 assert((0.0 < frac && frac < 1.0) || SCIPvarIsBinary(var)); 680 if( bestcandmayrounddown || bestcandmayroundup || nviolrows + frac < bestnviolrows + bestcandfrac ) 681 { 682 *bestcand = c; 683 bestnviolrows = nviolrows; 684 bestcandfrac = frac; 685 bestcandmayrounddown = FALSE; 686 bestcandmayroundup = FALSE; 687 *bestcandroundup = roundup; 688 } 689 assert(bestcandfrac < SCIP_INVALID); 690 } 691 } 692 693 *bestcandmayround = bestcandmayroundup || bestcandmayrounddown; 694 695 return SCIP_OKAY; 696 } 697 698 /** calculates the pseudocost score for a given variable w.r.t. a given solution value and a given rounding direction */ 699 static 700 void calcPscostQuot( 701 SCIP* scip, /**< SCIP data structure */ 702 SCIP_HEURDATA* heurdata, /**< heuristic data structure */ 703 SCIP_VAR* var, /**< problem variable */ 704 SCIP_Real primsol, /**< primal solution of variable */ 705 SCIP_Real frac, /**< fractionality of variable */ 706 int rounddir, /**< -1: round down, +1: round up, 0: select due to pseudo cost values */ 707 SCIP_Real* pscostquot, /**< pointer to store pseudo cost quotient */ 708 SCIP_Bool* roundup, /**< pointer to store whether the variable should be rounded up */ 709 SCIP_Bool prefvar /**< should this variable be preferred because it is in a minimal cover? */ 710 ) 711 { 712 SCIP_Real pscostdown; 713 SCIP_Real pscostup; 714 715 assert(heurdata != NULL); 716 assert(pscostquot != NULL); 717 assert(roundup != NULL); 718 assert(SCIPisEQ(scip, frac, primsol - SCIPfeasFloor(scip, primsol))); 719 720 /* bound fractions to not prefer variables that are nearly integral */ 721 frac = MAX(frac, 0.1); 722 frac = MIN(frac, 0.9); 723 724 /* get pseudo cost quotient */ 725 pscostdown = SCIPgetVarPseudocostVal(scip, var, 0.0-frac); 726 pscostup = SCIPgetVarPseudocostVal(scip, var, 1.0-frac); 727 assert(pscostdown >= 0.0 && pscostup >= 0.0); 728 729 /* choose rounding direction 730 * 731 * to avoid performance variability caused by numerics we use random numbers to decide whether we want to roundup or 732 * round down if the values to compare are equal within tolerances. 733 */ 734 if( rounddir == -1 ) 735 *roundup = FALSE; 736 else if( rounddir == +1 ) 737 *roundup = TRUE; 738 else if( SCIPisLT(scip, primsol, SCIPvarGetRootSol(var) - 0.4) 739 || (SCIPisEQ(scip, primsol, SCIPvarGetRootSol(var) - 0.4) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) ) 740 *roundup = FALSE; 741 else if( SCIPisGT(scip, primsol, SCIPvarGetRootSol(var) + 0.4) 742 || (SCIPisEQ(scip, primsol, SCIPvarGetRootSol(var) + 0.4) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) ) 743 *roundup = TRUE; 744 else if( SCIPisLT(scip, frac, 0.3) || (SCIPisEQ(scip, frac, 0.3) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) ) 745 *roundup = FALSE; 746 else if( SCIPisGT(scip, frac, 0.7) || (SCIPisEQ(scip, frac, 0.7) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) ) 747 *roundup = TRUE; 748 else if( SCIPisLT(scip, pscostdown, pscostup) 749 || (SCIPisEQ(scip, pscostdown, pscostup) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0)) 750 *roundup = FALSE; 751 else 752 *roundup = TRUE; 753 754 /* calculate pseudo cost quotient */ 755 if( *roundup ) 756 *pscostquot = sqrt(frac) * (1.0+pscostdown) / (1.0+pscostup); 757 else 758 *pscostquot = sqrt(1.0-frac) * (1.0+pscostup) / (1.0+pscostdown); 759 760 /* prefer decisions on binary variables */ 761 if( SCIPvarIsBinary(var) ) 762 (*pscostquot) *= 1000.0; 763 764 /* prefer decisions on cover variables */ 765 if( prefvar ) 766 (*pscostquot) *= 1000.0; 767 } 768 769 /** finds best candidate variable w.r.t. pseudo costs: 770 * - prefer variables that may not be rounded without destroying LP feasibility: 771 * - of these variables, round variable with largest rel. difference of pseudo cost values in corresponding 772 * direction 773 * - if all remaining fractional variables may be rounded without destroying LP feasibility: 774 * - round variable in the objective value direction 775 * - binary variables are prefered 776 * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might 777 * also be prefered if a correpsonding parameter is set 778 */ 779 static 780 SCIP_RETCODE choosePscostVar( 781 SCIP* scip, /**< original SCIP data structure */ 782 SCIP_HEURDATA* heurdata, /**< heuristic data structure */ 783 SCIP_VAR** nlpcands, /**< array of NLP fractional variables */ 784 SCIP_Real* nlpcandssol, /**< array of NLP fractional variables solution values */ 785 SCIP_Real* nlpcandsfrac, /**< array of NLP fractional variables fractionalities */ 786 int nnlpcands, /**< number of NLP fractional variables */ 787 SCIP_HASHMAP* varincover, /**< hash map for variables */ 788 SCIP_Bool covercomputed, /**< has a minimal cover been computed? */ 789 int* bestcand, /**< pointer to store the index of the best candidate variable */ 790 SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */ 791 SCIP_Bool* bestcandroundup /**< pointer to store whether best candidate should be rounded up */ 792 ) 793 { 794 SCIP_Bool bestcandmayrounddown; 795 SCIP_Bool bestcandmayroundup; 796 SCIP_Real bestpscostquot; 797 int c; 798 799 /* check preconditions */ 800 assert(scip != NULL); 801 assert(heurdata != NULL); 802 assert(nlpcands != NULL); 803 assert(nlpcandsfrac != NULL); 804 assert(nlpcandssol != NULL); 805 assert(bestcand != NULL); 806 assert(bestcandmayround != NULL); 807 assert(bestcandroundup != NULL); 808 809 bestcandmayrounddown = TRUE; 810 bestcandmayroundup = TRUE; 811 bestpscostquot = -1.0; 812 813 for( c = 0; c < nnlpcands; ++c ) 814 { 815 SCIP_VAR* var; 816 SCIP_Real primsol; 817 818 SCIP_Bool mayrounddown; 819 SCIP_Bool mayroundup; 820 SCIP_Bool roundup; 821 SCIP_Bool prefvar; 822 SCIP_Real frac; 823 SCIP_Real pscostquot; 824 825 var = nlpcands[c]; 826 mayrounddown = SCIPvarMayRoundDown(var); 827 mayroundup = SCIPvarMayRoundUp(var); 828 primsol = nlpcandssol[c]; 829 frac = nlpcandsfrac[c]; 830 prefvar = covercomputed && heurdata->prefercover && SCIPhashmapExists(varincover, var); 831 pscostquot = SCIP_INVALID; 832 833 if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) ) 834 continue; 835 836 if( mayrounddown || mayroundup ) 837 { 838 /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */ 839 if( bestcandmayrounddown || bestcandmayroundup ) 840 { 841 /* choose rounding direction: 842 * - if variable may be rounded in both directions, round corresponding to the pseudo cost values 843 * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding 844 * the current fractional solution 845 */ 846 roundup = FALSE; 847 if( mayrounddown && mayroundup ) 848 calcPscostQuot(scip, heurdata, var, primsol, frac, 0, &pscostquot, &roundup, prefvar); 849 else if( mayrounddown ) 850 calcPscostQuot(scip, heurdata, var, primsol, frac, +1, &pscostquot, &roundup, prefvar); 851 else 852 calcPscostQuot(scip, heurdata, var, primsol, frac, -1, &pscostquot, &roundup, prefvar); 853 854 assert(!SCIPisInfinity(scip,ABS(pscostquot))); 855 856 /* check, if candidate is new best candidate */ 857 if( pscostquot > bestpscostquot ) 858 { 859 *bestcand = c; 860 bestpscostquot = pscostquot; 861 bestcandmayrounddown = mayrounddown; 862 bestcandmayroundup = mayroundup; 863 *bestcandroundup = roundup; 864 } 865 } 866 } 867 else 868 { 869 /* the candidate may not be rounded: calculate pseudo cost quotient and preferred direction */ 870 calcPscostQuot(scip, heurdata, var, primsol, frac, 0, &pscostquot, &roundup, prefvar); 871 assert(!SCIPisInfinity(scip,ABS(pscostquot))); 872 873 /* check, if candidate is new best candidate: prefer unroundable candidates in any case */ 874 if( bestcandmayrounddown || bestcandmayroundup || pscostquot > bestpscostquot ) 875 { 876 *bestcand = c; 877 bestpscostquot = pscostquot; 878 bestcandmayrounddown = FALSE; 879 bestcandmayroundup = FALSE; 880 *bestcandroundup = roundup; 881 } 882 } 883 } 884 885 *bestcandmayround = bestcandmayroundup || bestcandmayrounddown; 886 887 return SCIP_OKAY; 888 } 889 890 /** finds best candidate variable w.r.t. the incumbent solution: 891 * - prefer variables that may not be rounded without destroying LP feasibility: 892 * - of these variables, round a variable to its value in direction of incumbent solution, and choose the 893 * variable that is closest to its rounded value 894 * - if all remaining fractional variables may be rounded without destroying LP feasibility: 895 * - round variable in direction that destroys LP feasibility (other direction is checked by SCIProundSol()) 896 * - round variable with least increasing objective value 897 * - binary variables are prefered 898 * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might 899 * also be prefered if a correpsonding parameter is set 900 */ 901 static 902 SCIP_RETCODE chooseGuidedVar( 903 SCIP* scip, /**< original SCIP data structure */ 904 SCIP_HEURDATA* heurdata, /**< heuristic data structure */ 905 SCIP_VAR** nlpcands, /**< array of NLP fractional variables */ 906 SCIP_Real* nlpcandssol, /**< array of NLP fractional variables solution values */ 907 SCIP_Real* nlpcandsfrac, /**< array of NLP fractional variables fractionalities */ 908 int nnlpcands, /**< number of NLP fractional variables */ 909 SCIP_SOL* bestsol, /**< incumbent solution */ 910 SCIP_HASHMAP* varincover, /**< hash map for variables */ 911 SCIP_Bool covercomputed, /**< has a minimal cover been computed? */ 912 int* bestcand, /**< pointer to store the index of the best candidate variable */ 913 SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */ 914 SCIP_Bool* bestcandroundup /**< pointer to store whether best candidate should be rounded up */ 915 ) 916 { 917 SCIP_Real bestobjgain; 918 SCIP_Real bestfrac; 919 SCIP_Bool bestcandmayrounddown; 920 SCIP_Bool bestcandmayroundup; 921 int c; 922 923 /* check preconditions */ 924 assert(scip != NULL); 925 assert(heurdata != NULL); 926 assert(nlpcands != NULL); 927 assert(nlpcandsfrac != NULL); 928 assert(nlpcandssol != NULL); 929 assert(bestcand != NULL); 930 assert(bestcandmayround != NULL); 931 assert(bestcandroundup != NULL); 932 933 bestcandmayrounddown = TRUE; 934 bestcandmayroundup = TRUE; 935 bestobjgain = SCIPinfinity(scip); 936 bestfrac = SCIP_INVALID; 937 938 for( c = 0; c < nnlpcands; ++c ) 939 { 940 SCIP_VAR* var; 941 SCIP_Real bestsolval; 942 SCIP_Real solval; 943 SCIP_Real obj; 944 SCIP_Real frac; 945 SCIP_Real objgain; 946 947 SCIP_Bool mayrounddown; 948 SCIP_Bool mayroundup; 949 SCIP_Bool roundup; 950 951 var = nlpcands[c]; 952 mayrounddown = SCIPvarMayRoundDown(var); 953 mayroundup = SCIPvarMayRoundUp(var); 954 solval = nlpcandssol[c]; 955 frac = nlpcandsfrac[c]; 956 obj = SCIPvarGetObj(var); 957 bestsolval = SCIPgetSolVal(scip, bestsol, var); 958 959 /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */ 960 if( SCIPisLT(scip, solval, SCIPvarGetLbLocal(var)) || SCIPisGT(scip, solval, SCIPvarGetUbLocal(var)) ) 961 continue; 962 963 /* select default rounding direction 964 * try to avoid variability; decide randomly if the LP solution can contain some noise 965 */ 966 if( SCIPisEQ(scip, solval, bestsolval) ) 967 roundup = (SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0); 968 else 969 roundup = (solval < bestsolval); 970 971 if( mayrounddown || mayroundup ) 972 { 973 /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */ 974 if( bestcandmayrounddown || bestcandmayroundup ) 975 { 976 /* choose rounding direction: 977 * - if variable may be rounded in both directions, round corresponding to its value in incumbent solution 978 * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding 979 * the current fractional solution with SCIProundSol() 980 */ 981 if( !mayrounddown || !mayroundup ) 982 roundup = mayrounddown; 983 984 if( roundup ) 985 { 986 frac = 1.0 - frac; 987 objgain = frac*obj; 988 } 989 else 990 objgain = -frac*obj; 991 992 /* penalize too small fractions */ 993 if( SCIPisEQ(scip, frac, 0.01) ) 994 { 995 /* try to avoid variability; decide randomly if the LP solution can contain some noise. 996 * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score. 997 */ 998 if( SCIPrandomGetInt(heurdata->randnumgen, 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 ) 999 objgain *= 1000.0; 1000 } 1001 else if( frac < 0.01 ) 1002 objgain *= 1000.0; 1003 1004 /* prefer decisions on binary variables */ 1005 if( !SCIPvarIsBinary(var) ) 1006 objgain *= 1000.0; 1007 1008 /* prefer decisions on cover variables */ 1009 if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) ) 1010 objgain *= 1000.0; 1011 1012 /* check, if candidate is new best candidate */ 1013 if( SCIPisLT(scip, objgain, bestobjgain) || (SCIPisEQ(scip, objgain, bestobjgain) && frac < bestfrac) ) 1014 { 1015 *bestcand = c; 1016 bestobjgain = objgain; 1017 bestfrac = frac; 1018 bestcandmayrounddown = mayrounddown; 1019 bestcandmayroundup = mayroundup; 1020 *bestcandroundup = roundup; 1021 } 1022 } 1023 } 1024 else 1025 { 1026 /* the candidate may not be rounded */ 1027 if( roundup ) 1028 frac = 1.0 - frac; 1029 1030 /* penalize too small fractions */ 1031 if( SCIPisEQ(scip, frac, 0.01) ) 1032 { 1033 /* try to avoid variability; decide randomly if the LP solution can contain some noise. 1034 * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score. 1035 */ 1036 if( SCIPrandomGetInt(heurdata->randnumgen, 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 ) 1037 frac += 10.0; 1038 } 1039 else if( frac < 0.01 ) 1040 frac += 10.0; 1041 1042 /* prefer decisions on binary variables */ 1043 if( !SCIPvarIsBinary(var) ) 1044 frac *= 1000.0; 1045 1046 /* prefer decisions on cover variables */ 1047 if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) ) 1048 frac *= 1000.0; 1049 1050 /* check, if candidate is new best candidate: prefer unroundable candidates in any case */ 1051 if( bestcandmayrounddown || bestcandmayroundup || frac < bestfrac ) 1052 { 1053 *bestcand = c; 1054 bestfrac = frac; 1055 bestcandmayrounddown = FALSE; 1056 bestcandmayroundup = FALSE; 1057 *bestcandroundup = roundup; 1058 } 1059 } 1060 } 1061 1062 *bestcandmayround = bestcandmayroundup || bestcandmayrounddown; 1063 1064 return SCIP_OKAY; 1065 } 1066 1067 /** finds best candidate variable w.r.t. both, the LP and the NLP solution: 1068 * - choose a variable for which the sum of the distances from the relaxations' solutions to a common 1069 * integer value is minimal 1070 * - binary variables are prefered 1071 * - variables in a minimal cover might be prefered if a corresponding parameter is set 1072 */ 1073 static 1074 SCIP_RETCODE chooseDoubleVar( 1075 SCIP* scip, /**< original SCIP data structure */ 1076 SCIP_HEURDATA* heurdata, /**< heuristic data structure */ 1077 SCIP_VAR** pseudocands, /**< array of non-fixed variables */ 1078 SCIP_Real* pseudocandsnlpsol, /**< array of NLP solution values */ 1079 SCIP_Real* pseudocandslpsol, /**< array of LP solution values */ 1080 int npseudocands, /**< number of NLP fractional variables */ 1081 SCIP_HASHMAP* varincover, /**< hash map for variables */ 1082 SCIP_Bool covercomputed, /**< has a minimal cover been computed? */ 1083 int* bestcand, /**< pointer to store the index of the best candidate variable */ 1084 SCIP_Real* bestboundval, /**< pointer to store the bound, the best candidate should be rounded to */ 1085 SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */ 1086 SCIP_Bool* bestcandroundup /**< pointer to store whether best candidate should be rounded up */ 1087 ) 1088 { 1089 SCIP_Real bestfrac; 1090 int c; 1091 1092 /* check preconditions */ 1093 assert(scip != NULL); 1094 assert(heurdata != NULL); 1095 assert(pseudocands != NULL); 1096 assert(pseudocandsnlpsol != NULL); 1097 assert(pseudocandslpsol != NULL); 1098 assert(covercomputed == (varincover != NULL)); 1099 assert(bestcand != NULL); 1100 assert(bestcandmayround != NULL); 1101 assert(bestcandroundup != NULL); 1102 1103 bestfrac = SCIP_INVALID; 1104 1105 for( c = 0; c < npseudocands; ++c ) 1106 { 1107 SCIP_VAR* var; 1108 SCIP_Bool mayround; 1109 SCIP_Bool roundup; 1110 1111 SCIP_Real frac; 1112 SCIP_Real lpsol; 1113 SCIP_Real nlpsol; 1114 SCIP_Real lpsolfloor; 1115 SCIP_Real nlpsolfloor; 1116 SCIP_Real lpsolceil; 1117 SCIP_Real nlpsolceil; 1118 SCIP_Real boundval; 1119 SCIP_Real floorval; 1120 SCIP_Real ceilval; 1121 1122 var = pseudocands[c]; 1123 lpsol = pseudocandslpsol[c]; 1124 nlpsol = pseudocandsnlpsol[c]; 1125 1126 assert(SCIPvarGetUbLocal(var)-SCIPvarGetLbLocal(var) > 0.5); 1127 assert(SCIPisLE(scip, SCIPvarGetLbLocal(var), lpsol) && SCIPisLE(scip, lpsol, SCIPvarGetUbLocal(var))); 1128 1129 /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */ 1130 if( SCIPisLT(scip, nlpsol, SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpsol, SCIPvarGetUbLocal(var)) ) 1131 continue; 1132 1133 mayround = SCIPvarMayRoundDown(var) || SCIPvarMayRoundUp(var); 1134 1135 /* if this candidate is trivially roundable, and we already know a candidate that is not, continue */ 1136 if( mayround && !(*bestcandmayround) ) 1137 continue; 1138 1139 if( SCIPisFeasEQ(scip, lpsol, nlpsol) && SCIPisFeasIntegral(scip, lpsol)) 1140 continue; 1141 1142 lpsolfloor = SCIPfeasFloor(scip, lpsol); 1143 nlpsolfloor = SCIPfeasFloor(scip, nlpsol); 1144 lpsolceil = SCIPfeasCeil(scip, lpsol); 1145 nlpsolceil = SCIPfeasCeil(scip, nlpsol); 1146 floorval = MIN(lpsolfloor,nlpsolfloor); 1147 ceilval = MAX(lpsolceil,nlpsolceil); 1148 1149 /* if both values are in the same interval, find out which integer is (in sum) the closer one, this will be the 1150 * new bound. The minima and maxima are necessary since one or both values with be integer 1151 */ 1152 if( SCIPvarIsBinary(var) || ceilval-floorval < 1.5 ) 1153 { 1154 frac = 0.33*(lpsol-floorval) + 0.67*(nlpsol-floorval); 1155 if( frac < 0.5 ) 1156 { 1157 roundup = FALSE; 1158 boundval = MIN(lpsolfloor,nlpsolfloor); 1159 } 1160 else 1161 { 1162 roundup = TRUE; 1163 frac = 1.0-frac; 1164 boundval = MAX(nlpsolceil,lpsolceil); 1165 } 1166 } 1167 else 1168 { 1169 /* determine new bound in the middle of both relaxations, such that the NLP stays feasible */ 1170 SCIP_Real midval; 1171 midval = (nlpsol+lpsol)/2.0; 1172 roundup = nlpsol > lpsol; 1173 frac = ABS(nlpsol-lpsol); 1174 1175 if( roundup ) 1176 boundval = SCIPfeasCeil(scip, midval); 1177 else 1178 boundval = SCIPfeasFloor(scip, midval); 1179 1180 assert(roundup == SCIPisGT(scip, nlpsol, boundval)); 1181 } 1182 1183 /* penalize too small fractions */ 1184 if( SCIPisEQ(scip, frac, 0.01) ) 1185 { 1186 /* try to avoid variability; decide randomly if the LP solution can contain some noise. 1187 * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score. 1188 */ 1189 if( SCIPrandomGetInt(heurdata->randnumgen, 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 ) 1190 frac += 10.0; 1191 } 1192 else if( frac < 0.01 ) 1193 frac += 10.0; 1194 1195 /* prefer decisions on binary variables */ 1196 if( !SCIPvarIsBinary(var) ) 1197 frac *= 1000.0; 1198 1199 /* prefer decisions on cover variables */ 1200 if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) ) 1201 frac *= 1000.0; 1202 1203 /* check, if candidate is new best candidate: prefer unroundable candidates in any case */ 1204 if( frac < bestfrac || (*bestcandmayround && !mayround) ) 1205 { 1206 *bestcand = c; 1207 bestfrac = frac; 1208 *bestcandmayround = FALSE; 1209 *bestcandroundup = roundup; 1210 *bestboundval = boundval; 1211 } 1212 assert(bestfrac < SCIP_INVALID); 1213 } 1214 1215 if( *bestcandroundup ) 1216 *bestboundval -= 0.5; 1217 else 1218 *bestboundval += 0.5; 1219 1220 return SCIP_OKAY; 1221 } 1222 1223 /** creates a new solution for the original problem by copying the solution of the subproblem */ 1224 static 1225 SCIP_RETCODE createNewSol( 1226 SCIP* scip, /**< original SCIP data structure */ 1227 SCIP* subscip, /**< SCIP structure of the subproblem */ 1228 SCIP_HEUR* heur, /**< heuristic structure */ 1229 SCIP_HASHMAP* varmap, /**< hash map for variables */ 1230 SCIP_SOL* subsol, /**< solution of the subproblem */ 1231 SCIP_Bool* success /**< used to store whether new solution was found or not */ 1232 ) 1233 { 1234 SCIP_VAR** vars; /* the original problem's variables */ 1235 SCIP_Real* subsolvals; /* solution values of the subproblem */ 1236 SCIP_SOL* newsol; /* solution to be created for the original problem */ 1237 int nvars; /* the original problem's number of variables */ 1238 SCIP_VAR* subvar; 1239 int i; 1240 1241 assert(scip != NULL); 1242 assert(subscip != NULL); 1243 assert(subsol != NULL); 1244 1245 /* get variables' data */ 1246 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 1247 1248 SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) ); 1249 1250 /* copy the solution */ 1251 for( i = 0; i < nvars; ++i ) 1252 { 1253 subvar = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[i]); 1254 if( subvar == NULL ) 1255 subsolvals[i] = MIN(MAX(0.0, SCIPvarGetLbLocal(vars[i])), SCIPvarGetUbLocal(vars[i])); /*lint !e666*/ 1256 else 1257 subsolvals[i] = SCIPgetSolVal(subscip, subsol, subvar); 1258 } 1259 1260 /* create new solution for the original problem */ 1261 SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) ); 1262 SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) ); 1263 1264 /* try to add new solution to scip and free it immediately */ 1265 SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) ); 1266 1267 SCIPfreeBufferArray(scip, &subsolvals); 1268 1269 return SCIP_OKAY; 1270 } 1271 1272 /** todo setup and solve the subMIP */ 1273 static 1274 SCIP_RETCODE doSolveSubMIP( 1275 SCIP* scip, /**< SCIP data structure */ 1276 SCIP* subscip, /**< NLP diving subscip */ 1277 SCIP_HEUR* heur, /**< heuristic data structure */ 1278 SCIP_VAR** covervars, /**< variables in the cover, should be fixed locally */ 1279 int ncovervars, /**< number of variables in the cover */ 1280 SCIP_Bool* success /**< pointer to store whether a solution was found */ 1281 ) 1282 { 1283 SCIP_HASHMAP* varmap; 1284 SCIP_SOL** subsols; 1285 int c; 1286 int nsubsols; 1287 1288 assert(subscip != NULL); 1289 assert(scip != NULL); 1290 assert(heur != NULL); 1291 1292 /* create the variable mapping hash map */ 1293 SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(subscip), SCIPgetNVars(scip)) ); 1294 1295 *success = FALSE; 1296 1297 /* copy original problem to subproblem; do not copy pricers */ 1298 SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmap, NULL, "undercoversub", NULL, NULL, 0, FALSE, FALSE, FALSE, 1299 TRUE, NULL) ); 1300 1301 /* assert that cover variables are fixed in source and target SCIP */ 1302 for( c = 0; c < ncovervars; c++) 1303 { 1304 assert(SCIPhashmapGetImage(varmap, covervars[c]) != NULL); /* cover variable cannot be relaxation-only, thus must have been copied */ 1305 assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(covervars[c]), SCIPvarGetUbLocal(covervars[c]))); 1306 assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal((SCIP_VAR*) SCIPhashmapGetImage(varmap, covervars[c])), 1307 SCIPvarGetUbGlobal((SCIP_VAR*) SCIPhashmapGetImage(varmap, covervars[c])))); 1308 } 1309 1310 /* set parameters for sub-SCIP */ 1311 1312 /* do not abort subproblem on CTRL-C */ 1313 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) ); 1314 1315 #ifdef SCIP_DEBUG 1316 /* for debugging, enable full output */ 1317 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) ); 1318 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) ); 1319 #else 1320 /* disable statistic timing inside sub SCIP and output to console */ 1321 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) ); 1322 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) ); 1323 #endif 1324 1325 /* set limits for the subproblem */ 1326 SCIP_CALL( SCIPcopyLimits(scip, subscip) ); 1327 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", (SCIP_Longint)100) ); 1328 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", (SCIP_Longint)500) ); 1329 1330 /* forbid recursive call of heuristics and separators solving sub-SCIPs */ 1331 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) ); 1332 1333 /* disable cutting plane separation */ 1334 SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) ); 1335 1336 /* disable expensive presolving */ 1337 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) ); 1338 1339 /* use best estimate node selection */ 1340 if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") ) 1341 { 1342 SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) ); 1343 } 1344 1345 /* use inference branching */ 1346 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") ) 1347 { 1348 SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) ); 1349 } 1350 1351 /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */ 1352 if( !SCIPisParamFixed(subscip, "conflict/enable") ) 1353 { 1354 SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) ); 1355 } 1356 if( !SCIPisParamFixed(subscip, "conflict/useboundlp") ) 1357 { 1358 SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') ); 1359 } 1360 if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") ) 1361 { 1362 SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) ); 1363 } 1364 1365 if( SCIPgetNSols(scip) > 0 ) 1366 { 1367 SCIP_Real upperbound; 1368 SCIP_Real cutoffbound; 1369 SCIP_Real minimprove; 1370 1371 assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) ); 1372 1373 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip); 1374 minimprove = 0.01; 1375 1376 if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(scip)) ) 1377 { 1378 cutoffbound = (1-minimprove)*SCIPgetUpperbound(scip) + minimprove*SCIPgetLowerbound(scip); 1379 } 1380 else 1381 { 1382 if( SCIPgetUpperbound(scip) >= 0 ) 1383 cutoffbound = (1 - minimprove)*SCIPgetUpperbound(scip); 1384 else 1385 cutoffbound = (1 + minimprove)*SCIPgetUpperbound(scip); 1386 } 1387 cutoffbound = MIN(upperbound, cutoffbound); 1388 SCIP_CALL( SCIPsetObjlimit(subscip, cutoffbound) ); 1389 } 1390 1391 SCIP_CALL_ABORT( SCIPsolve(subscip) ); 1392 1393 /* check, whether a solution was found; 1394 * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted 1395 */ 1396 nsubsols = SCIPgetNSols(subscip); 1397 subsols = SCIPgetSols(subscip); 1398 for( c = 0; c < nsubsols && !(*success); ++c ) 1399 { 1400 SCIP_CALL( createNewSol(scip, subscip, heur, varmap, subsols[c], success) ); 1401 } 1402 1403 SCIPhashmapFree(&varmap); 1404 1405 return SCIP_OKAY; 1406 } 1407 1408 1409 /** solves subproblem and passes best feasible solution to original SCIP instance */ 1410 static 1411 SCIP_RETCODE solveSubMIP( 1412 SCIP* scip, /**< SCIP data structure of the original problem */ 1413 SCIP_HEUR* heur, /**< heuristic data structure */ 1414 SCIP_VAR** covervars, /**< variables in the cover, should be fixed locally */ 1415 int ncovervars, /**< number of variables in the cover */ 1416 SCIP_Bool* success /**< pointer to store whether a solution was found */ 1417 ) 1418 { 1419 SCIP* subscip; 1420 SCIP_RETCODE retcode; 1421 1422 /* check whether there is enough time and memory left */ 1423 SCIP_CALL( SCIPcheckCopyLimits(scip, success) ); 1424 1425 if( !(*success) ) 1426 return SCIP_OKAY; 1427 1428 /* create subproblem */ 1429 SCIP_CALL( SCIPcreate(&subscip) ); 1430 1431 retcode = doSolveSubMIP(scip, subscip, heur, covervars, ncovervars, success); 1432 1433 /* free sub-SCIP even if an error occurred during the subscip solve */ 1434 SCIP_CALL( SCIPfree(&subscip) ); 1435 1436 SCIP_CALL( retcode ); 1437 1438 return SCIP_OKAY; 1439 } 1440 1441 /* ---------------- Callback methods of event handler ---------------- */ 1442 1443 /* exec the event handler 1444 * 1445 * We update the number of variables fixed in the cover 1446 */ 1447 static 1448 SCIP_DECL_EVENTEXEC(eventExecNlpdiving) 1449 { 1450 SCIP_EVENTTYPE eventtype; 1451 SCIP_HEURDATA* heurdata; 1452 SCIP_VAR* var; 1453 1454 SCIP_Real oldbound; 1455 SCIP_Real newbound; 1456 SCIP_Real otherbound; 1457 1458 assert(eventhdlr != NULL); 1459 assert(eventdata != NULL); 1460 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0); 1461 assert(event != NULL); 1462 1463 heurdata = (SCIP_HEURDATA*)eventdata; 1464 assert(heurdata != NULL); 1465 assert(0 <= heurdata->nfixedcovervars && heurdata->nfixedcovervars <= SCIPgetNVars(scip)); 1466 1467 oldbound = SCIPeventGetOldbound(event); 1468 newbound = SCIPeventGetNewbound(event); 1469 var = SCIPeventGetVar(event); 1470 1471 eventtype = SCIPeventGetType(event); 1472 otherbound = (eventtype & SCIP_EVENTTYPE_LBCHANGED) ? SCIPvarGetUbLocal(var) : SCIPvarGetLbLocal(var); 1473 1474 switch( eventtype ) 1475 { 1476 case SCIP_EVENTTYPE_LBTIGHTENED: 1477 case SCIP_EVENTTYPE_UBTIGHTENED: 1478 /* if cover variable is now fixed */ 1479 if( SCIPisFeasEQ(scip, newbound, otherbound) && !SCIPisFeasEQ(scip, oldbound, otherbound) ) 1480 { 1481 assert(!SCIPisEQ(scip, oldbound, otherbound)); 1482 ++(heurdata->nfixedcovervars); 1483 } 1484 break; 1485 case SCIP_EVENTTYPE_LBRELAXED: 1486 case SCIP_EVENTTYPE_UBRELAXED: 1487 /* if cover variable is now unfixed */ 1488 if( SCIPisFeasEQ(scip, oldbound, otherbound) && !SCIPisFeasEQ(scip, newbound, otherbound) ) 1489 { 1490 assert(!SCIPisEQ(scip, newbound, otherbound)); 1491 --(heurdata->nfixedcovervars); 1492 } 1493 break; 1494 default: 1495 SCIPerrorMessage("invalid event type.\n"); 1496 return SCIP_INVALIDDATA; 1497 } 1498 assert(0 <= heurdata->nfixedcovervars && heurdata->nfixedcovervars <= SCIPgetNVars(scip)); 1499 1500 /* SCIPdebugMsg(scip, "changed bound of cover variable <%s> from %f to %f (nfixedcovervars: %d).\n", SCIPvarGetName(var), 1501 oldbound, newbound, heurdata->nfixedcovervars); */ 1502 1503 return SCIP_OKAY; 1504 } 1505 1506 1507 /* 1508 * Callback methods 1509 */ 1510 1511 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 1512 static 1513 SCIP_DECL_HEURCOPY(heurCopyNlpdiving) 1514 { /*lint --e{715}*/ 1515 assert(scip != NULL); 1516 assert(heur != NULL); 1517 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 1518 1519 /* call inclusion method of primal heuristic */ 1520 SCIP_CALL( SCIPincludeHeurNlpdiving(scip) ); 1521 1522 return SCIP_OKAY; 1523 } 1524 1525 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 1526 static 1527 SCIP_DECL_HEURFREE(heurFreeNlpdiving) /*lint --e{715}*/ 1528 { /*lint --e{715}*/ 1529 SCIP_HEURDATA* heurdata; 1530 1531 assert(heur != NULL); 1532 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 1533 assert(scip != NULL); 1534 1535 /* free heuristic data */ 1536 heurdata = SCIPheurGetData(heur); 1537 assert(heurdata != NULL); 1538 SCIPfreeBlockMemory(scip, &heurdata); 1539 SCIPheurSetData(heur, NULL); 1540 1541 return SCIP_OKAY; 1542 } 1543 1544 1545 /** initialization method of primal heuristic (called after problem was transformed) */ 1546 static 1547 SCIP_DECL_HEURINIT(heurInitNlpdiving) /*lint --e{715}*/ 1548 { /*lint --e{715}*/ 1549 SCIP_HEURDATA* heurdata; 1550 1551 assert(heur != NULL); 1552 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 1553 1554 /* get heuristic data */ 1555 heurdata = SCIPheurGetData(heur); 1556 assert(heurdata != NULL); 1557 1558 /* create working solution */ 1559 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) ); 1560 1561 /* create random number generator */ 1562 SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE) ); 1563 1564 /* initialize data */ 1565 heurdata->nnlpiterations = 0; 1566 heurdata->nsuccess = 0; 1567 heurdata->nfixedcovervars = 0; 1568 SCIPstatistic( 1569 heurdata->nnlpsolves = 0; 1570 heurdata->nfailcutoff = 0; 1571 heurdata->nfaildepth = 0; 1572 heurdata->nfailnlperror = 0; 1573 ); 1574 1575 return SCIP_OKAY; 1576 } 1577 1578 1579 /** deinitialization method of primal heuristic (called before transformed problem is freed) */ 1580 static 1581 SCIP_DECL_HEUREXIT(heurExitNlpdiving) /*lint --e{715}*/ 1582 { /*lint --e{715}*/ 1583 SCIP_HEURDATA* heurdata; 1584 1585 assert(heur != NULL); 1586 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 1587 1588 /* get heuristic data */ 1589 heurdata = SCIPheurGetData(heur); 1590 assert(heurdata != NULL); 1591 1592 /* free random number generator */ 1593 SCIPfreeRandom(scip, &heurdata->randnumgen); 1594 1595 /* free working solution */ 1596 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) ); 1597 1598 SCIPstatistic( 1599 if( strstr(SCIPgetProbName(scip), "_covering") == NULL && SCIPheurGetNCalls(heur) > 0 ) 1600 { 1601 SCIPstatisticMessage("%-30s %5" SCIP_LONGINT_FORMAT " sols in %5" SCIP_LONGINT_FORMAT " runs, %6.1fs, %7d NLP iters in %5d NLP solves, %5.1f avg., %3d%% success %3d%% cutoff %3d%% depth %3d%% nlperror\n", 1602 SCIPgetProbName(scip), SCIPheurGetNSolsFound(heur), SCIPheurGetNCalls(heur), SCIPheurGetTime(heur), 1603 heurdata->nnlpiterations, heurdata->nnlpsolves, heurdata->nnlpiterations/MAX(1.0,(SCIP_Real)heurdata->nnlpsolves), 1604 (100*heurdata->nsuccess) / (int)SCIPheurGetNCalls(heur), (100*heurdata->nfailcutoff) / (int)SCIPheurGetNCalls(heur), (100*heurdata->nfaildepth) / (int)SCIPheurGetNCalls(heur), (100*heurdata->nfailnlperror) / (int)SCIPheurGetNCalls(heur) 1605 ); 1606 } 1607 ); 1608 1609 return SCIP_OKAY; 1610 } 1611 1612 /** execution method of primal heuristic */ 1613 static 1614 SCIP_DECL_HEUREXEC(heurExecNlpdiving) 1615 { /*lint --e{715}*/ 1616 SCIP_HEURDATA* heurdata; 1617 SCIP_NLPSOLSTAT nlpsolstat; 1618 SCIP_LPSOLSTAT lpsolstat; 1619 SCIP_SOL* nlpstartsol; 1620 SCIP_SOL* bestsol; 1621 SCIP_VAR** nlpcands; 1622 SCIP_VAR** covervars; 1623 SCIP_Real* nlpcandssol; 1624 SCIP_Real* nlpcandsfrac; 1625 SCIP_Real* pseudocandslpsol; 1626 SCIP_Real* pseudocandsnlpsol; 1627 SCIP_HASHMAP* varincover; 1628 SCIP_Real searchubbound; 1629 SCIP_Real searchavgbound; 1630 SCIP_Real searchbound; 1631 SCIP_Real objval; 1632 SCIP_Real oldobjval; 1633 SCIP_Real fixquot; 1634 SCIP_Real bestboundval; 1635 SCIP_Bool bestcandmayround; 1636 SCIP_Bool bestcandroundup; 1637 SCIP_Bool nlperror; 1638 SCIP_Bool lperror; 1639 SCIP_Bool cutoff; 1640 SCIP_Bool backtracked; 1641 SCIP_Bool solvenlp; 1642 SCIP_Bool covercomputed; 1643 SCIP_Bool solvesubmip; 1644 SCIP_Longint ncalls; 1645 SCIP_Longint nsolsfound; 1646 int avgnnlpiterations; 1647 int maxnnlpiterations; 1648 int npseudocands; 1649 int nlpbranchcands; 1650 int ncovervars; 1651 int nnlpcands; 1652 int startnnlpcands; 1653 int depth; 1654 int maxdepth; 1655 int maxdivedepth; 1656 int divedepth; 1657 int lastnlpsolvedepth; 1658 int nfeasnlps; 1659 int bestcand; 1660 int c; 1661 int backtrackdepth; /* depth where to go when backtracking */ 1662 SCIP_VAR* backtrackvar; /* (first) variable to fix differently in backtracking */ 1663 SCIP_Real backtrackvarval; /* (fractional) value of backtrack variable */ 1664 SCIP_Bool backtrackroundup; /* whether variable should be rounded up in backtracking */ 1665 1666 backtrackdepth = -1; 1667 backtrackvar = NULL; 1668 backtrackvarval = 0.0; 1669 backtrackroundup = FALSE; 1670 bestsol = NULL; 1671 pseudocandsnlpsol = NULL; 1672 pseudocandslpsol = NULL; 1673 covervars = NULL; 1674 1675 assert(heur != NULL); 1676 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 1677 assert(scip != NULL); 1678 assert(result != NULL); 1679 /* assert(SCIPhasCurrentNodeLP(scip)); */ 1680 1681 *result = SCIP_DIDNOTRUN; 1682 1683 /* do not call heuristic of node was already detected to be infeasible */ 1684 if( nodeinfeasible ) 1685 return SCIP_OKAY; 1686 1687 /* only call heuristic, if an NLP relaxation has been constructed */ 1688 if( !SCIPisNLPConstructed(scip) || SCIPgetNNlpis(scip) == 0 ) 1689 return SCIP_OKAY; 1690 1691 /* only call heuristic, if the current node will not be cutoff, e.g., due to a (integer and NLP-)feasible LP solution */ 1692 if( SCIPisFeasGE(scip, SCIPgetLocalLowerbound(scip), SCIPgetUpperbound(scip)) ) 1693 return SCIP_OKAY; 1694 1695 /* get heuristic's data */ 1696 heurdata = SCIPheurGetData(heur); 1697 assert(heurdata != NULL); 1698 1699 /* do not call heuristic, if it barely succeded */ 1700 if( (SCIPheurGetNSolsFound(heur) + 1.0) / (SCIP_Real)(SCIPheurGetNCalls(heur) + 1.0) < heurdata->minsuccquot ) 1701 return SCIP_OKAY; 1702 1703 *result = SCIP_DELAYED; 1704 1705 /* don't dive two times at the same node */ 1706 if( SCIPgetLastDivenode(scip) == SCIPgetNNodes(scip) && SCIPgetDepth(scip) > 0 ) 1707 return SCIP_OKAY; 1708 1709 *result = SCIP_DIDNOTRUN; 1710 1711 /* only try to dive, if we are in the correct part of the tree, given by minreldepth and maxreldepth */ 1712 depth = SCIPgetDepth(scip); 1713 maxdepth = SCIPgetMaxDepth(scip); 1714 maxdepth = MAX(maxdepth, 30); 1715 if( depth < heurdata->minreldepth*maxdepth || depth > heurdata->maxreldepth*maxdepth ) 1716 return SCIP_OKAY; 1717 1718 /* calculate the maximal number of NLP iterations until heuristic is aborted 1719 * maximal number is maxnlpiterabs plus a success-depending multiplier of maxnlpiterrel 1720 */ 1721 ncalls = SCIPheurGetNCalls(heur); 1722 nsolsfound = 10*SCIPheurGetNBestSolsFound(heur) + heurdata->nsuccess; 1723 maxnnlpiterations = heurdata->maxnlpiterabs; 1724 maxnnlpiterations += (int)((1.0 + 10.0*(nsolsfound+1.0)/(ncalls+1.0)) * heurdata->maxnlpiterrel); 1725 1726 /* don't try to dive, if we took too many NLP iterations during diving */ 1727 if( heurdata->nnlpiterations >= maxnnlpiterations ) 1728 return SCIP_OKAY; 1729 1730 /* allow at least a bit more than the so far average number of NLP iterations per dive */ 1731 avgnnlpiterations = (int)(heurdata->nnlpiterations / MAX(ncalls, 1.0)); 1732 maxnnlpiterations = (int)MAX((SCIP_Real) maxnnlpiterations, (SCIP_Real) heurdata->nnlpiterations + 1.2*avgnnlpiterations); 1733 1734 /* don't try to dive, if there are no unfixed discrete variables */ 1735 SCIP_CALL( SCIPgetPseudoBranchCands(scip, NULL, &npseudocands, NULL) ); 1736 if( npseudocands == 0 ) 1737 return SCIP_OKAY; 1738 1739 *result = SCIP_DIDNOTFIND; 1740 1741 /* set starting point to lp solution */ 1742 SCIP_CALL( SCIPsetNLPInitialGuessSol(scip, NULL) ); 1743 1744 /* solve NLP relaxation, if not solved already */ 1745 nlpsolstat = SCIPgetNLPSolstat(scip); 1746 if( nlpsolstat > SCIP_NLPSOLSTAT_FEASIBLE ) 1747 { 1748 SCIP_NLPSTATISTICS nlpstatistics; 1749 1750 /* cppcheck-suppress syntaxError */ 1751 SCIP_CALL( SCIPsolveNLP(scip, 1752 .iterlimit = maxnnlpiterations - heurdata->nnlpiterations, 1753 .fastfail = heurdata->nlpfastfail ? SCIP_NLPPARAM_FASTFAIL_AGGRESSIVE : SCIP_NLPPARAM_FASTFAIL_CONSERVATIVE) ); /*lint !e666*/ 1754 SCIPstatistic( ++heurdata->nnlpsolves ); 1755 1756 /* update iteration count */ 1757 if( SCIPgetNLPTermstat(scip) < SCIP_NLPTERMSTAT_NUMERICERROR ) 1758 { 1759 SCIP_CALL( SCIPgetNLPStatistics(scip, &nlpstatistics) ); 1760 heurdata->nnlpiterations += nlpstatistics.niterations; 1761 } 1762 1763 nlpsolstat = SCIPgetNLPSolstat(scip); 1764 1765 /* give up, if no feasible solution found */ 1766 if( nlpsolstat >= SCIP_NLPSOLSTAT_LOCINFEASIBLE ) 1767 { 1768 SCIPdebugMsg(scip, "initial NLP infeasible or not solvable --> stop\n"); 1769 1770 SCIPstatistic( 1771 if( SCIPgetNLPTermstat(scip) < SCIP_NLPTERMSTAT_NUMERICERROR ) 1772 heurdata->nfailcutoff++; 1773 else 1774 heurdata->nfailnlperror++; 1775 ) 1776 1777 return SCIP_OKAY; 1778 } 1779 } 1780 1781 /* get NLP solution */ 1782 SCIP_CALL( SCIPlinkNLPSol(scip, heurdata->sol) ); 1783 1784 /* get fractional variables that should be integral */ 1785 SCIP_CALL( getNLPFracVars(scip, heurdata, &nlpcands, &nlpcandssol, &nlpcandsfrac, &nnlpcands) ); 1786 assert(nnlpcands <= npseudocands); 1787 1788 /* get LP candidates if LP solution is optimal */ 1789 lpsolstat = SCIPgetLPSolstat(scip); 1790 if( lpsolstat == SCIP_LPSOLSTAT_OPTIMAL ) 1791 nlpbranchcands = SCIPgetNLPBranchCands(scip); 1792 else 1793 nlpbranchcands = 0; 1794 1795 /* don't try to dive, if there are no fractional variables */ 1796 if( nnlpcands == 0 ) 1797 { 1798 SCIP_Bool success; 1799 1800 /* check, if solution was feasible and good enough 1801 * 1802 * Note that even if the NLP solver found a feasible solution it does not mean that is satisfy the integrality 1803 * conditions for fixed variables. This happens because the NLP solver uses relative tolerances for the bound 1804 * constraints but SCIP uses absolute tolerances for checking the integrality conditions. 1805 */ 1806 #ifdef SCIP_DEBUG 1807 SCIP_CALL( SCIPtrySol(scip, heurdata->sol, TRUE, TRUE, FALSE, TRUE, TRUE, &success) ); 1808 #else 1809 SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, TRUE, TRUE, &success) ); 1810 #endif 1811 if( success ) 1812 { 1813 SCIPdebugMsg(scip, " -> solution of first NLP was integral, feasible, and good enough\n"); 1814 *result = SCIP_FOUNDSOL; 1815 } 1816 1817 return SCIP_OKAY; 1818 } 1819 1820 /* for guided diving: don't dive, if no feasible solutions exist */ 1821 if( heurdata->varselrule == 'g' && SCIPgetNSols(scip) == 0 ) 1822 return SCIP_OKAY; 1823 1824 /* for guided diving: get best solution that should guide the search; if this solution lives in the original variable space, 1825 * we cannot use it since it might violate the global bounds of the current problem 1826 */ 1827 if( heurdata->varselrule == 'g' && SCIPsolIsOriginal(SCIPgetBestSol(scip)) ) 1828 return SCIP_OKAY; 1829 1830 nlpstartsol = NULL; 1831 assert(nlpcandsfrac != NULL); 1832 assert(nlpcands != NULL); 1833 assert(nlpcandssol != NULL); 1834 1835 /* save solution of first NLP, if we may use it later */ 1836 if( heurdata->nlpstart != 'n' ) 1837 { 1838 SCIP_CALL( SCIPcreateNLPSol(scip, &nlpstartsol, heur) ); 1839 SCIP_CALL( SCIPunlinkSol(scip, nlpstartsol) ); 1840 } 1841 1842 /* calculate the objective search bound */ 1843 if( SCIPgetNSolsFound(scip) == 0 ) 1844 { 1845 if( heurdata->maxdiveubquotnosol > 0.0 ) 1846 searchubbound = SCIPgetLowerbound(scip) 1847 + heurdata->maxdiveubquotnosol * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip)); 1848 else 1849 searchubbound = SCIPinfinity(scip); 1850 if( heurdata->maxdiveavgquotnosol > 0.0 ) 1851 searchavgbound = SCIPgetLowerbound(scip) 1852 + heurdata->maxdiveavgquotnosol * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip)); 1853 else 1854 searchavgbound = SCIPinfinity(scip); 1855 } 1856 else 1857 { 1858 if( heurdata->maxdiveubquot > 0.0 ) 1859 searchubbound = SCIPgetLowerbound(scip) 1860 + heurdata->maxdiveubquot * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip)); 1861 else 1862 searchubbound = SCIPinfinity(scip); 1863 if( heurdata->maxdiveavgquot > 0.0 ) 1864 searchavgbound = SCIPgetLowerbound(scip) 1865 + heurdata->maxdiveavgquot * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip)); 1866 else 1867 searchavgbound = SCIPinfinity(scip); 1868 } 1869 searchbound = MIN(searchubbound, searchavgbound); 1870 if( SCIPisObjIntegral(scip) ) 1871 searchbound = SCIPceil(scip, searchbound); 1872 1873 /* calculate the maximal diving depth: 10 * min{number of integer variables, max depth} */ 1874 maxdivedepth = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip); 1875 maxdivedepth = MIN(maxdivedepth, maxdepth); 1876 maxdivedepth *= 10; 1877 1878 covercomputed = FALSE; 1879 varincover = NULL; 1880 1881 /* compute cover, if required */ 1882 if( heurdata->prefercover || heurdata->solvesubmip ) 1883 { 1884 SCIP_Real timelimit; 1885 SCIP_Real memorylimit; 1886 1887 /* get limits */ 1888 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) ); 1889 SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) ); 1890 if( !SCIPisInfinity(scip, timelimit) ) 1891 timelimit -= SCIPgetSolvingTime(scip); 1892 1893 /* substract the memory already used by the main SCIP and the estimated memory usage of external software */ 1894 if( !SCIPisInfinity(scip, memorylimit) ) 1895 { 1896 memorylimit -= SCIPgetMemUsed(scip)/1048576.0; 1897 memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0; 1898 } 1899 1900 /* compute cover; use local bounds; only cover "and" and nonlinear constraints (no bounddisjunction or indicator), 1901 * including convex constraints */ 1902 ncovervars = -1; 1903 SCIP_CALL( SCIPallocBufferArray(scip, &covervars, SCIPgetNVars(scip)) ); 1904 if( memorylimit > 2.0*SCIPgetMemExternEstim(scip)/1048576.0 && timelimit > 0.05 ) 1905 { 1906 SCIP_CALL( SCIPcomputeCoverUndercover(scip, &ncovervars, covervars, timelimit, memorylimit, SCIPinfinity(scip), 1907 FALSE, FALSE, TRUE, FALSE, FALSE, TRUE, 'u', &covercomputed) ); 1908 } 1909 1910 if( covercomputed ) 1911 { 1912 /* a cover can be empty, if the cover computation reveals that all nonlinear constraints are linear w.r.t. current variable fixations */ 1913 assert(ncovervars >= 0); 1914 1915 /* create hash map */ 1916 SCIP_CALL( SCIPhashmapCreate(&varincover, SCIPblkmem(scip), ncovervars) ); 1917 1918 /* process variables in the cover */ 1919 for( c = 0; c < ncovervars; c++ ) 1920 { 1921 /* insert variable into hash map */ 1922 if( SCIPvarGetType(covervars[c]) < SCIP_VARTYPE_IMPLINT ) 1923 { 1924 assert(!SCIPhashmapExists(varincover, covervars[c])); 1925 SCIP_CALL( SCIPhashmapInsertInt(varincover, covervars[c], c+1) ); 1926 } 1927 1928 /* catch bound change events of cover variables */ 1929 assert(heurdata->eventhdlr != NULL); 1930 SCIP_CALL( SCIPcatchVarEvent(scip, covervars[c], SCIP_EVENTTYPE_BOUNDCHANGED, heurdata->eventhdlr, 1931 (SCIP_EVENTDATA*) heurdata, NULL) ); 1932 assert(!SCIPisFeasEQ(scip, SCIPvarGetLbLocal(covervars[c]), SCIPvarGetUbLocal(covervars[c]))); 1933 } 1934 } 1935 } 1936 else 1937 { 1938 covervars = NULL; 1939 ncovervars = 0; 1940 } 1941 1942 /* start diving */ 1943 SCIP_CALL( SCIPstartProbing(scip) ); 1944 1945 /* enables collection of variable statistics during probing */ 1946 SCIPenableVarHistory(scip); 1947 1948 /* get NLP objective value*/ 1949 objval = SCIPgetNLPObjval(scip); 1950 1951 SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") executing nlpdiving heuristic: depth=%d, %d fractionals, dualbound=%g, searchbound=%g\n", 1952 SCIPgetNNodes(scip), SCIPgetDepth(scip), nnlpcands, SCIPgetDualbound(scip), SCIPretransformObj(scip, searchbound)); 1953 1954 /* store a copy of the best solution, if guided diving should be used */ 1955 if( heurdata->varselrule == 'g' ) 1956 { 1957 assert(SCIPgetNSols(scip) > 0); 1958 assert(!SCIPsolIsOriginal(SCIPgetBestSol(scip))); 1959 1960 SCIP_CALL( SCIPcreateSolCopy(scip, &bestsol, SCIPgetBestSol(scip)) ); 1961 } 1962 1963 /* if double diving should be used, create arrays to hold to entire LP and NLP solution */ 1964 if( heurdata->varselrule == 'd' ) 1965 { 1966 SCIP_CALL( SCIPallocBufferArray(scip, &pseudocandslpsol, npseudocands) ); 1967 SCIP_CALL( SCIPallocBufferArray(scip, &pseudocandsnlpsol, npseudocands) ); 1968 } 1969 1970 /* dive as long we are in the given objective, depth and iteration limits and fractional variables exist, but 1971 * - if possible, we dive at least with the depth 10 1972 * - if the number of fractional variables decreased at least with 1 variable per 2 dive depths, we continue diving 1973 */ 1974 nlperror = FALSE; 1975 lperror = FALSE; 1976 cutoff = FALSE; 1977 divedepth = 0; 1978 lastnlpsolvedepth = 0; 1979 backtracked = FALSE; /* whether we are in backtracking */ 1980 fixquot = heurdata->fixquot; 1981 nfeasnlps = 1; 1982 startnnlpcands = nnlpcands; 1983 solvesubmip = heurdata->solvesubmip; 1984 1985 while( !nlperror && !cutoff && (nlpsolstat <= SCIP_NLPSOLSTAT_FEASIBLE || nlpsolstat == SCIP_NLPSOLSTAT_UNKNOWN) && nnlpcands > 0 1986 && (nfeasnlps < heurdata->maxfeasnlps 1987 || nnlpcands <= startnnlpcands - divedepth/2 1988 || (nfeasnlps < maxdivedepth && heurdata->nnlpiterations < maxnnlpiterations && objval < searchbound)) 1989 && !SCIPisStopped(scip) ) 1990 { 1991 SCIP_VAR* var; 1992 SCIP_Bool updatepscost; 1993 1994 /* open a new probing node if this will not exceed the maximal tree depth, otherwise stop here */ 1995 if( SCIPgetDepth(scip) < SCIP_MAXTREEDEPTH ) 1996 { 1997 SCIP_CALL( SCIPnewProbingNode(scip) ); 1998 divedepth++; 1999 } 2000 else 2001 break; 2002 2003 bestcand = -1; 2004 bestcandmayround = TRUE; 2005 bestcandroundup = FALSE; 2006 bestboundval = SCIP_INVALID; 2007 updatepscost = TRUE; 2008 var = NULL; 2009 2010 /* find best candidate variable */ 2011 switch( heurdata->varselrule ) 2012 { 2013 case 'c': 2014 SCIP_CALL( chooseCoefVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, varincover, covercomputed, 2015 &bestcand, &bestcandmayround, &bestcandroundup) ); 2016 if( bestcand >= 0 ) 2017 { 2018 var = nlpcands[bestcand]; 2019 bestboundval = nlpcandssol[bestcand]; 2020 } 2021 break; 2022 case 'v': 2023 SCIP_CALL( chooseVeclenVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, varincover, covercomputed, 2024 &bestcand, &bestcandmayround, &bestcandroundup) ); 2025 if( bestcand >= 0 ) 2026 { 2027 var = nlpcands[bestcand]; 2028 bestboundval = nlpcandssol[bestcand]; 2029 } 2030 break; 2031 case 'p': 2032 SCIP_CALL( choosePscostVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, varincover, covercomputed, 2033 &bestcand, &bestcandmayround, &bestcandroundup) ); 2034 if( bestcand >= 0 ) 2035 { 2036 var = nlpcands[bestcand]; 2037 bestboundval = nlpcandssol[bestcand]; 2038 } 2039 break; 2040 case 'g': 2041 SCIP_CALL( chooseGuidedVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, bestsol, varincover, covercomputed, 2042 &bestcand, &bestcandmayround, &bestcandroundup) ); 2043 if( bestcand >= 0 ) 2044 { 2045 var = nlpcands[bestcand]; 2046 bestboundval = nlpcandssol[bestcand]; 2047 } 2048 break; 2049 case 'd': 2050 /* double diving only works if we have both relaxations at hand, otherwise we fall back to fractional diving */ 2051 if( lpsolstat == SCIP_LPSOLSTAT_OPTIMAL ) 2052 { 2053 SCIP_VAR** pseudocands; 2054 2055 SCIP_CALL( SCIPgetPseudoBranchCands(scip, &pseudocands, &npseudocands, NULL) ); 2056 assert(backtrackdepth > 0 || nnlpcands <= npseudocands); 2057 assert(SCIPgetNLPBranchCands(scip) <= npseudocands); 2058 SCIP_CALL( SCIPgetSolVals(scip, NULL, npseudocands, pseudocands, pseudocandslpsol) ); 2059 SCIP_CALL( SCIPgetSolVals(scip, heurdata->sol, npseudocands, pseudocands, pseudocandsnlpsol) ); 2060 SCIP_CALL( chooseDoubleVar(scip, heurdata, pseudocands, pseudocandsnlpsol, pseudocandslpsol, npseudocands, 2061 varincover, covercomputed, &bestcand, &bestboundval, &bestcandmayround, &bestcandroundup) ); 2062 if( bestcand >= 0 ) 2063 var = pseudocands[bestcand]; 2064 break; 2065 } 2066 else 2067 updatepscost = FALSE; 2068 /*lint -fallthrough*/ 2069 case 'f': 2070 SCIP_CALL( chooseFracVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, varincover, covercomputed, 2071 &bestcand, &bestcandmayround, &bestcandroundup) ); 2072 if( bestcand >= 0 ) 2073 { 2074 var = nlpcands[bestcand]; 2075 bestboundval = nlpcandssol[bestcand]; 2076 } 2077 break; 2078 default: 2079 SCIPerrorMessage("invalid variable selection rule\n"); 2080 return SCIP_INVALIDDATA; 2081 } 2082 2083 /* if all candidates are roundable, try to round the solution 2084 * if var == NULL (i.e., bestcand == -1), then all solution candidates are outside bounds 2085 * this should only happen if they are slightly outside bounds (i.e., still within feastol, relative tolerance), 2086 * but far enough out to be considered as fractional (within feastol, but using absolute tolerance) 2087 * in this case, we also try our luck with rounding 2088 */ 2089 if( (var == NULL || bestcandmayround) && backtrackdepth == -1 ) 2090 { 2091 SCIP_Bool success; 2092 2093 /* create solution from diving NLP and try to round it */ 2094 SCIP_CALL( SCIProundSol(scip, heurdata->sol, &success) ); 2095 2096 if( success ) 2097 { 2098 SCIPdebugMsg(scip, "nlpdiving found roundable primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol)); 2099 2100 /* try to add solution to SCIP */ 2101 #ifdef SCIP_DEBUG 2102 SCIP_CALL( SCIPtrySol(scip, heurdata->sol, TRUE, TRUE, FALSE, FALSE, TRUE, &success) ); 2103 #else 2104 SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, TRUE, &success) ); 2105 #endif 2106 2107 /* check, if solution was feasible and good enough */ 2108 if( success ) 2109 { 2110 SCIPdebugMsg(scip, " -> solution was feasible and good enough\n"); 2111 *result = SCIP_FOUNDSOL; 2112 } 2113 } 2114 } 2115 2116 /* if all variables have been found to be essentially integral (even though there is some numerical doubt, see comment above), then stop */ 2117 if( var == NULL ) 2118 break; 2119 2120 do 2121 { 2122 SCIP_Real frac; 2123 frac = SCIP_INVALID; 2124 2125 if( backtracked && backtrackdepth > 0 ) 2126 { 2127 assert(backtrackvar != NULL); 2128 2129 /* if the variable is already fixed or if the solution value is outside the domain, numerical troubles may have 2130 * occured or variable was fixed by propagation while backtracking => Abort diving! 2131 */ 2132 if( SCIPvarGetLbLocal(backtrackvar) >= SCIPvarGetUbLocal(backtrackvar) - 0.5 ) 2133 { 2134 SCIPdebugMsg(scip, "Selected variable <%s> already fixed to [%g,%g] (solval: %.9f), diving aborted \n", 2135 SCIPvarGetName(backtrackvar), SCIPvarGetLbLocal(backtrackvar), SCIPvarGetUbLocal(backtrackvar), backtrackvarval); 2136 cutoff = TRUE; 2137 break; 2138 } 2139 if( SCIPisFeasLT(scip, backtrackvarval, SCIPvarGetLbLocal(backtrackvar)) || SCIPisFeasGT(scip, backtrackvarval, SCIPvarGetUbLocal(backtrackvar)) ) 2140 { 2141 SCIPdebugMsg(scip, "selected variable's <%s> solution value is outside the domain [%g,%g] (solval: %.9f), diving aborted\n", 2142 SCIPvarGetName(backtrackvar), SCIPvarGetLbLocal(backtrackvar), SCIPvarGetUbLocal(backtrackvar), backtrackvarval); 2143 assert(backtracked); 2144 break; 2145 } 2146 2147 /* round backtrack variable up or down */ 2148 if( backtrackroundup ) 2149 { 2150 SCIPdebugMsg(scip, " dive %d/%d, NLP iter %d/%d: var <%s>, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n", 2151 divedepth, maxdivedepth, heurdata->nnlpiterations, maxnnlpiterations, 2152 SCIPvarGetName(backtrackvar), backtrackvarval, SCIPvarGetLbLocal(backtrackvar), SCIPvarGetUbLocal(backtrackvar), 2153 SCIPfeasCeil(scip, backtrackvarval), SCIPvarGetUbLocal(backtrackvar)); 2154 SCIP_CALL( SCIPchgVarLbProbing(scip, backtrackvar, SCIPfeasCeil(scip, backtrackvarval)) ); 2155 } 2156 else 2157 { 2158 SCIPdebugMsg(scip, " dive %d/%d, NLP iter %d/%d: var <%s>, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n", 2159 divedepth, maxdivedepth, heurdata->nnlpiterations, maxnnlpiterations, 2160 SCIPvarGetName(backtrackvar), backtrackvarval, SCIPvarGetLbLocal(backtrackvar), SCIPvarGetUbLocal(backtrackvar), 2161 SCIPvarGetLbLocal(backtrackvar), SCIPfeasFloor(scip, backtrackvarval)); 2162 SCIP_CALL( SCIPchgVarUbProbing(scip, backtrackvar, SCIPfeasFloor(scip, backtrackvarval)) ); 2163 } 2164 2165 /* forget about backtrack variable */ 2166 backtrackdepth = -1; 2167 2168 /* for pseudo cost computation */ 2169 bestcandroundup = backtrackroundup; 2170 frac = SCIPfrac(scip, backtrackvarval); 2171 var = backtrackvar; 2172 } 2173 else 2174 { 2175 assert(var != NULL); 2176 2177 /* if the variable is already fixed or if the solution value is outside the domain, numerical troubles may have 2178 * occured or variable was fixed by propagation while backtracking => Abort diving! 2179 */ 2180 if( SCIPvarGetLbLocal(var) >= SCIPvarGetUbLocal(var) - 0.5 ) 2181 { 2182 SCIPdebugMsg(scip, "Selected variable <%s> already fixed to [%g,%g] (solval: %.9f), diving aborted \n", 2183 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bestboundval); 2184 cutoff = TRUE; 2185 break; 2186 } 2187 if( SCIPisFeasLT(scip, bestboundval, SCIPvarGetLbLocal(var)) || SCIPisFeasGT(scip, bestboundval, SCIPvarGetUbLocal(var)) ) 2188 { 2189 SCIPdebugMsg(scip, "selected variable's <%s> solution value is outside the domain [%g,%g] (solval: %.9f), diving aborted\n", 2190 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bestboundval); 2191 assert(backtracked); 2192 break; 2193 } 2194 2195 /* apply rounding of best candidate */ 2196 if( bestcandroundup == !backtracked ) 2197 { 2198 /* round variable up */ 2199 SCIPdebugMsg(scip, " dive %d/%d, NLP iter %d/%d: var <%s>, round=%u, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n", 2200 divedepth, maxdivedepth, heurdata->nnlpiterations, maxnnlpiterations, 2201 SCIPvarGetName(var), bestcandmayround, 2202 bestboundval, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), 2203 SCIPfeasCeil(scip, bestboundval), SCIPvarGetUbLocal(var)); 2204 SCIP_CALL( SCIPchgVarLbProbing(scip, var, SCIPfeasCeil(scip, bestboundval)) ); 2205 2206 /* remember variable for backtracking, if we have none yet (e.g., we are just after NLP solve) or we are half way to the next NLP solve */ 2207 if( backtrackdepth == -1 || (divedepth - lastnlpsolvedepth == (int)(MIN(fixquot * nnlpcands, nlpbranchcands)/2.0)) ) 2208 { 2209 backtrackdepth = divedepth; 2210 backtrackvar = var; 2211 backtrackvarval = bestboundval; 2212 backtrackroundup = FALSE; 2213 } 2214 } 2215 else 2216 { 2217 /* round variable down */ 2218 SCIPdebugMsg(scip, " dive %d/%d, NLP iter %d/%d: var <%s>, round=%u, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n", 2219 divedepth, maxdivedepth, heurdata->nnlpiterations, maxnnlpiterations, 2220 SCIPvarGetName(var), bestcandmayround, 2221 bestboundval, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), 2222 SCIPvarGetLbLocal(var), SCIPfeasFloor(scip, bestboundval)); 2223 SCIP_CALL( SCIPchgVarUbProbing(scip, var, SCIPfeasFloor(scip, bestboundval)) ); 2224 2225 /* remember variable for backtracking, if we have none yet (e.g., we are just after NLP solve) or we are half way to the next NLP solve */ 2226 if( backtrackdepth == -1 || (divedepth - lastnlpsolvedepth == (int)(MIN(fixquot * nnlpcands, nlpbranchcands)/2.0)) ) 2227 { 2228 backtrackdepth = divedepth; 2229 backtrackvar = var; 2230 backtrackvarval = bestboundval; 2231 backtrackroundup = TRUE; 2232 } 2233 } 2234 2235 /* for pseudo-cost computation */ 2236 if( updatepscost && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL ) 2237 { 2238 if( heurdata->varselrule == 'd' ) 2239 { 2240 assert(pseudocandsnlpsol != NULL); 2241 assert(0 <= bestcand && bestcand < npseudocands); 2242 frac = SCIPfrac(scip, pseudocandsnlpsol[bestcand]); 2243 } 2244 else 2245 frac = nlpcandsfrac[bestcand]; 2246 } 2247 } 2248 2249 /* apply domain propagation */ 2250 SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, NULL) ); 2251 if( cutoff ) 2252 { 2253 SCIPdebugMsg(scip, " *** cutoff detected in propagation at level %d\n", SCIPgetProbingDepth(scip)); 2254 } 2255 2256 /* if all variables in the cover are fixed or there is no fractional variable in the cover, 2257 * then solve a sub-MIP 2258 */ 2259 if( !cutoff && solvesubmip && covercomputed && 2260 (heurdata->nfixedcovervars == ncovervars || 2261 (heurdata->nfixedcovervars >= (ncovervars+1)/2 && !SCIPhashmapExists(varincover, var))) ) 2262 { 2263 int probingdepth; 2264 2265 solvesubmip = FALSE; 2266 probingdepth = SCIPgetProbingDepth(scip); 2267 assert(probingdepth >= 1); 2268 assert(covervars != NULL); 2269 2270 if( heurdata->nfixedcovervars != ncovervars ) 2271 { 2272 /* fix all remaining cover variables */ 2273 for( c = 0; c < ncovervars && !cutoff ; c++ ) 2274 { 2275 SCIP_Real lb; 2276 SCIP_Real ub; 2277 lb = SCIPvarGetLbLocal(covervars[c]); 2278 ub = SCIPvarGetUbLocal(covervars[c]); 2279 if( !SCIPisFeasEQ(scip, lb, ub) ) 2280 { 2281 SCIP_Real nlpsolval; 2282 2283 /* adopt lpsolval w.r.t. intermediate bound changes by propagation */ 2284 nlpsolval = SCIPvarGetNLPSol(covervars[c]); 2285 nlpsolval = MIN(nlpsolval,ub); 2286 nlpsolval = MAX(nlpsolval,lb); 2287 assert(SCIPvarGetType(covervars[c]) >= SCIP_VARTYPE_IMPLINT || SCIPisFeasIntegral(scip, nlpsolval)); 2288 2289 /* open a new probing node if this will not exceed the maximal tree depth, 2290 * otherwise fix all the remaining variables at the same probing node 2291 * @todo do we need a new probing node for each fixing? if one of these fixings leads to a cutoff 2292 * we backtrack to the last probing node before we started to fix the covervars (and we do 2293 * not solve the probing LP). thus, it would be less work load in SCIPendProbing 2294 * and SCIPbacktrackProbing. 2295 */ 2296 if( SCIP_MAXTREEDEPTH > SCIPgetDepth(scip) ) 2297 { 2298 SCIP_CALL( SCIPnewProbingNode(scip) ); 2299 } 2300 2301 /* fix and propagate */ 2302 assert(SCIPisLbBetter(scip, nlpsolval, lb, ub) || SCIPisUbBetter(scip, nlpsolval, lb, ub)); 2303 2304 if( SCIPisLbBetter(scip, nlpsolval, lb, ub) ) 2305 { 2306 SCIP_CALL( SCIPchgVarLbProbing(scip, covervars[c], nlpsolval) ); 2307 /* if covervar was implicit integer and fractional, then nlpsolval may be below lower bound now, so adjust to new bound */ 2308 nlpsolval = MAX(nlpsolval, SCIPvarGetLbLocal(covervars[c])); /*lint !e666*/ 2309 } 2310 if( SCIPisUbBetter(scip, nlpsolval, lb, ub) ) 2311 { 2312 SCIP_CALL( SCIPchgVarUbProbing(scip, covervars[c], nlpsolval) ); 2313 } 2314 2315 SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, NULL) ); 2316 } 2317 } 2318 } 2319 2320 /* solve sub-MIP or return to standard diving */ 2321 if( cutoff ) 2322 { 2323 SCIP_CALL( SCIPbacktrackProbing(scip, probingdepth) ); 2324 } 2325 else 2326 { 2327 SCIP_Bool success; 2328 success = FALSE; 2329 2330 SCIP_CALL( solveSubMIP(scip, heur, covervars, ncovervars, &success)); 2331 if( success ) 2332 *result = SCIP_FOUNDSOL; 2333 backtracked = TRUE; /* to avoid backtracking */ 2334 nnlpcands = 0; /* to force termination */ 2335 cutoff = TRUE; 2336 } 2337 } 2338 2339 /* resolve the diving LP */ 2340 if( !cutoff && !lperror && (heurdata->lp || heurdata->varselrule == 'd') 2341 && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL && SCIPisLPSolBasic(scip) ) 2342 { 2343 SCIP_CALL( SCIPsolveProbingLP(scip, 100, &lperror, &cutoff) ); 2344 2345 /* get LP solution status, objective value, and fractional variables, that should be integral */ 2346 lpsolstat = SCIPgetLPSolstat(scip); 2347 assert(cutoff || (lpsolstat != SCIP_LPSOLSTAT_OBJLIMIT && lpsolstat != SCIP_LPSOLSTAT_INFEASIBLE && 2348 (lpsolstat != SCIP_LPSOLSTAT_OPTIMAL || SCIPisLT(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip))))); 2349 2350 if( lpsolstat == SCIP_LPSOLSTAT_OPTIMAL ) 2351 { 2352 nlpbranchcands = SCIPgetNLPBranchCands(scip); 2353 2354 /* get new objective value */ 2355 oldobjval = objval; 2356 objval = SCIPgetLPObjval(scip); 2357 2358 /* update pseudo cost values */ 2359 if( updatepscost && SCIPisGT(scip, objval, oldobjval) ) 2360 { 2361 assert(frac != SCIP_INVALID); /*lint !e777*/ 2362 if( bestcandroundup ) 2363 { 2364 SCIP_CALL( SCIPupdateVarPseudocost(scip, var, 1.0-frac, objval - oldobjval, 1.0) ); 2365 } 2366 else 2367 { 2368 SCIP_CALL( SCIPupdateVarPseudocost(scip, var, 0.0-frac, objval - oldobjval, 1.0) ); 2369 } 2370 } 2371 } 2372 else 2373 { 2374 nlpbranchcands = 0; 2375 } 2376 2377 if( cutoff ) 2378 { 2379 SCIPdebugMsg(scip, " *** cutoff detected in LP solving at level %d, lpsolstat = %d\n", SCIPgetProbingDepth(scip), lpsolstat); 2380 } 2381 } 2382 else 2383 lpsolstat = SCIP_LPSOLSTAT_NOTSOLVED; 2384 2385 /* check whether we want to solve the NLP, which is the case if 2386 * - we are in backtracking, or 2387 * - we have (actively) fixed/rounded fixquot*nnlpcands variables 2388 * - all fractional variables were rounded/fixed (due to fixing and domain propagation) 2389 */ 2390 solvenlp = backtracked; 2391 if( !solvenlp && !cutoff ) 2392 { 2393 solvenlp = (lastnlpsolvedepth < divedepth - fixquot * nnlpcands); 2394 if( !solvenlp ) 2395 { 2396 /* check if fractional NLP variables are left (some may have been fixed by propagation) */ 2397 for( c = 0; c < nnlpcands; ++c ) 2398 { 2399 var = nlpcands[c]; 2400 if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) ) 2401 continue; 2402 else 2403 break; 2404 } 2405 if( c == nnlpcands ) 2406 solvenlp = TRUE; 2407 } 2408 } 2409 2410 nlpsolstat = SCIP_NLPSOLSTAT_UNKNOWN; 2411 2412 /* resolve the diving NLP */ 2413 if( !cutoff && solvenlp ) 2414 { 2415 SCIP_NLPTERMSTAT termstat; 2416 SCIP_NLPSTATISTICS nlpstatistics; 2417 2418 /* set start solution, if we are in backtracking (previous NLP solve was infeasible) */ 2419 if( heurdata->nlpstart != 'n' && backtracked ) 2420 { 2421 assert(nlpstartsol != NULL); 2422 2423 SCIPdebugMsg(scip, "setting NLP initial guess\n"); 2424 2425 SCIP_CALL( SCIPsetNLPInitialGuessSol(scip, nlpstartsol) ); 2426 } 2427 2428 /* solve NLP; allow at least MINNLPITER many iterations */ 2429 SCIP_CALL( SCIPsolveNLP(scip, 2430 .iterlimit = MAX(maxnnlpiterations - heurdata->nnlpiterations, MINNLPITER)) ); /*lint !e666*/ 2431 SCIPstatistic( ++heurdata->nnlpsolves ); 2432 2433 termstat = SCIPgetNLPTermstat(scip); 2434 if( termstat >= SCIP_NLPTERMSTAT_NUMERICERROR ) 2435 { 2436 if( termstat >= SCIP_NLPTERMSTAT_LICENSEERROR ) 2437 { 2438 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, 2439 "Error while solving NLP in nlpdiving heuristic; NLP solve terminated with code <%d>\n", termstat); 2440 } 2441 nlperror = TRUE; 2442 break; 2443 } 2444 2445 /* update iteration count */ 2446 SCIP_CALL( SCIPgetNLPStatistics(scip, &nlpstatistics) ); 2447 heurdata->nnlpiterations += nlpstatistics.niterations; 2448 2449 /* get NLP solution status, objective value, and fractional variables, that should be integral */ 2450 nlpsolstat = SCIPgetNLPSolstat(scip); 2451 cutoff = (nlpsolstat > SCIP_NLPSOLSTAT_FEASIBLE); 2452 2453 if( cutoff ) 2454 { 2455 SCIPdebugMsg(scip, " *** cutoff detected in NLP solving at level %d, nlpsolstat: %d\n", SCIPgetProbingDepth(scip), nlpsolstat); 2456 } 2457 else 2458 { 2459 SCIP_CALL( SCIPlinkNLPSol(scip, heurdata->sol) ); 2460 2461 /* remember that we have solve NLP on this depth successfully */ 2462 lastnlpsolvedepth = divedepth; 2463 /* forget previous backtrack variable, we will never go back to a depth before the current one */ 2464 backtrackdepth = -1; 2465 /* store NLP solution for warmstarting, if nlpstart is 'f' */ 2466 if( heurdata->nlpstart == 'f' ) 2467 { 2468 assert(nlpstartsol != NULL); 2469 2470 /* copy NLP solution values into nlpstartsol, is there a better way to do this???? */ 2471 SCIP_CALL( SCIPlinkNLPSol(scip, nlpstartsol) ); 2472 SCIP_CALL( SCIPunlinkSol(scip, nlpstartsol) ); 2473 } 2474 /* increase counter on number of NLP solves with feasible solution */ 2475 ++nfeasnlps; 2476 } 2477 } 2478 2479 /* perform backtracking if a cutoff was detected */ 2480 if( cutoff && !backtracked && heurdata->backtrack ) 2481 { 2482 if( backtrackdepth == -1 ) 2483 { 2484 /* backtrack one step */ 2485 SCIPdebugMsg(scip, " *** cutoff detected at level %d - backtracking one step\n", SCIPgetProbingDepth(scip)); 2486 SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip)-1) ); 2487 2488 /* after backtracking there has to be at least one open node without exceeding the maximal tree depth */ 2489 assert(SCIP_MAXTREEDEPTH > SCIPgetDepth(scip)); 2490 2491 SCIP_CALL( SCIPnewProbingNode(scip) ); 2492 } 2493 else 2494 { 2495 /* if we have a stored a depth for backtracking, go there */ 2496 SCIPdebugMsg(scip, " *** cutoff detected at level %d - backtracking to depth %d\n", SCIPgetProbingDepth(scip), backtrackdepth); 2497 SCIP_CALL( SCIPbacktrackProbing(scip, backtrackdepth-1) ); 2498 2499 /* after backtracking there has to be at least one open node without exceeding the maximal tree depth */ 2500 assert(SCIP_MAXTREEDEPTH > SCIPgetDepth(scip)); 2501 2502 SCIP_CALL( SCIPnewProbingNode(scip) ); 2503 divedepth = backtrackdepth; 2504 2505 /* do not update pseudocosts if backtracking by more than one level */ 2506 updatepscost = FALSE; 2507 2508 /* in case, we are feasible after backtracking, fix less variables at once in continuing diving 2509 * @todo should we remember the fixquot in heurdata for the next run? 2510 */ 2511 fixquot *= 0.5; 2512 } 2513 /* remember that we are backtracking now */ 2514 backtracked = TRUE; 2515 } 2516 else 2517 backtracked = FALSE; 2518 } 2519 while( backtracked ); 2520 2521 if( !nlperror && !cutoff && nlpsolstat <= SCIP_NLPSOLSTAT_FEASIBLE ) 2522 { 2523 /* get new fractional variables */ 2524 SCIP_CALL( getNLPFracVars(scip, heurdata, &nlpcands, &nlpcandssol, &nlpcandsfrac, &nnlpcands) ); 2525 } 2526 SCIPdebugMsg(scip, " -> nlpsolstat=%d, objval=%g/%g, nfrac nlp=%d lp=%d\n", nlpsolstat, objval, searchbound, nnlpcands, nlpbranchcands); 2527 } 2528 2529 /*lint --e{774}*/ 2530 SCIPdebugMsg(scip, "NLP nlpdiving ABORT due to "); 2531 if( nlperror || (nlpsolstat > SCIP_NLPSOLSTAT_LOCINFEASIBLE && nlpsolstat != SCIP_NLPSOLSTAT_UNKNOWN) ) 2532 { 2533 SCIPdebugMsgPrint(scip, "NLP bad status - nlperror: %ud nlpsolstat: %d \n", nlperror, nlpsolstat); 2534 SCIPstatistic( heurdata->nfailnlperror++ ); 2535 } 2536 else if( SCIPisStopped(scip) || cutoff ) 2537 { 2538 SCIPdebugMsgPrint(scip, "LIMIT hit - stop: %ud cutoff: %ud \n", SCIPisStopped(scip), cutoff); 2539 SCIPstatistic( heurdata->nfailcutoff++ ); 2540 } 2541 else if(! (divedepth < 10 2542 || nnlpcands <= startnnlpcands - divedepth/2 2543 || (divedepth < maxdivedepth && heurdata->nnlpiterations < maxnnlpiterations && objval < searchbound) ) ) 2544 { 2545 SCIPdebugMsgPrint(scip, "TOO DEEP - divedepth: %4d cands halfed: %d ltmaxdepth: %d ltmaxiter: %d bound: %d\n", divedepth, 2546 (nnlpcands > startnnlpcands - divedepth/2), (divedepth >= maxdivedepth), (heurdata->nnlpiterations >= maxnnlpiterations), 2547 (objval >= searchbound)); 2548 SCIPstatistic( heurdata->nfaildepth++ ); 2549 } 2550 else if( nnlpcands == 0 && !nlperror && !cutoff && nlpsolstat <= SCIP_NLPSOLSTAT_FEASIBLE ) 2551 { 2552 SCIPdebugMsgPrint(scip, "SUCCESS\n"); 2553 } 2554 else 2555 { 2556 SCIPdebugMsgPrint(scip, "UNKNOWN, very mysterical reason\n"); /* see also special case var == NULL (bestcand == -1) after choose*Var above */ 2557 } 2558 2559 /* check if a solution has been found */ 2560 if( nnlpcands == 0 && !nlperror && !cutoff && nlpsolstat <= SCIP_NLPSOLSTAT_FEASIBLE ) 2561 { 2562 SCIP_Bool success; 2563 2564 /* create solution from diving NLP */ 2565 SCIPdebugMsg(scip, "nlpdiving found primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol)); 2566 2567 /* try to add solution to SCIP 2568 * 2569 * Note that even if the NLP solver found a feasible solution it does not mean that is satisfy the integrality 2570 * conditions for fixed variables. This happens because the NLP solver uses relative tolerances for the bound 2571 * constraints but SCIP uses absolute tolerances for checking the integrality conditions. 2572 */ 2573 #ifdef SCIP_DEBUG 2574 SCIP_CALL( SCIPtrySol(scip, heurdata->sol, TRUE, TRUE, FALSE, TRUE, TRUE, &success) ); 2575 #else 2576 SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, TRUE, TRUE, &success) ); 2577 #endif 2578 2579 /* check, if solution was feasible and good enough */ 2580 if( success ) 2581 { 2582 SCIPdebugMsg(scip, " -> solution was feasible and good enough\n"); 2583 *result = SCIP_FOUNDSOL; 2584 } 2585 else 2586 { 2587 SCIPdebugMsg(scip, " -> solution was not accepted\n"); 2588 } 2589 } 2590 2591 /* end diving */ 2592 SCIP_CALL( SCIPendProbing(scip) ); 2593 2594 /* free hash map and drop variable bound change events */ 2595 if( covercomputed ) 2596 { 2597 assert(heurdata->eventhdlr != NULL); 2598 assert(heurdata->nfixedcovervars >= 0); /* variables might have been globally fixed in propagation */ 2599 assert(varincover != NULL); 2600 assert(covervars != NULL); 2601 2602 SCIPhashmapFree(&varincover); 2603 2604 /* drop bound change events of cover variables */ 2605 for( c = 0; c < ncovervars; c++ ) 2606 { 2607 SCIP_CALL( SCIPdropVarEvent(scip, covervars[c], SCIP_EVENTTYPE_BOUNDCHANGED, heurdata->eventhdlr, (SCIP_EVENTDATA*)heurdata, -1) ); 2608 } 2609 } 2610 else 2611 assert(varincover == NULL); 2612 2613 /* free NLP start solution */ 2614 if( nlpstartsol != NULL ) 2615 { 2616 SCIP_CALL( SCIPfreeSol(scip, &nlpstartsol) ); 2617 } 2618 2619 /* free copied best solution */ 2620 if( heurdata->varselrule == 'g' ) 2621 { 2622 assert(bestsol != NULL); 2623 SCIP_CALL( SCIPfreeSol(scip, &bestsol) ); 2624 } 2625 else 2626 assert(bestsol == NULL); 2627 2628 /* free arrays of LP and NLP solution */ 2629 if( heurdata->varselrule == 'd' ) 2630 { 2631 assert(pseudocandsnlpsol != NULL); 2632 assert(pseudocandsnlpsol != NULL); 2633 SCIPfreeBufferArray(scip, &pseudocandsnlpsol); 2634 SCIPfreeBufferArray(scip, &pseudocandslpsol); 2635 } 2636 else 2637 { 2638 assert(pseudocandsnlpsol == NULL); 2639 assert(pseudocandsnlpsol == NULL); 2640 } 2641 2642 /* free array of cover variables */ 2643 if( heurdata->prefercover || heurdata->solvesubmip ) 2644 { 2645 assert(covervars != NULL || !covercomputed); 2646 if( covervars != NULL ) 2647 SCIPfreeBufferArray(scip, &covervars); 2648 } 2649 else 2650 assert(covervars == NULL); 2651 2652 if( *result == SCIP_FOUNDSOL ) 2653 heurdata->nsuccess++; 2654 2655 SCIPdebugMsg(scip, "nlpdiving heuristic finished\n"); 2656 2657 return SCIP_OKAY; /*lint !e438*/ 2658 } 2659 2660 2661 /* 2662 * heuristic specific interface methods 2663 */ 2664 2665 /** creates the nlpdiving heuristic and includes it in SCIP */ 2666 SCIP_RETCODE SCIPincludeHeurNlpdiving( 2667 SCIP* scip /**< SCIP data structure */ 2668 ) 2669 { 2670 SCIP_HEURDATA* heurdata; 2671 SCIP_HEUR* heur = NULL; 2672 2673 /* create heuristic data */ 2674 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 2675 2676 /* include heuristic */ 2677 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 2678 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecNlpdiving, heurdata) ); 2679 2680 assert(heur != NULL); 2681 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyNlpdiving) ); 2682 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeNlpdiving) ); 2683 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitNlpdiving) ); 2684 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitNlpdiving) ); 2685 2686 /* get event handler for bound change events */ 2687 heurdata->eventhdlr = NULL; 2688 /* create event handler for bound change events */ 2689 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &heurdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, 2690 eventExecNlpdiving, NULL) ); 2691 if ( heurdata->eventhdlr == NULL ) 2692 { 2693 SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n"); 2694 return SCIP_PLUGINNOTFOUND; 2695 } 2696 2697 /* nlpdiving heuristic parameters */ 2698 SCIP_CALL( SCIPaddRealParam(scip, 2699 "heuristics/" HEUR_NAME "/minreldepth", 2700 "minimal relative depth to start diving", 2701 &heurdata->minreldepth, TRUE, DEFAULT_MINRELDEPTH, 0.0, 1.0, NULL, NULL) ); 2702 SCIP_CALL( SCIPaddRealParam(scip, 2703 "heuristics/" HEUR_NAME "/maxreldepth", 2704 "maximal relative depth to start diving", 2705 &heurdata->maxreldepth, TRUE, DEFAULT_MAXRELDEPTH, 0.0, 1.0, NULL, NULL) ); 2706 SCIP_CALL( SCIPaddIntParam(scip, 2707 "heuristics/" HEUR_NAME "/maxnlpiterabs", 2708 "minimial absolute number of allowed NLP iterations", 2709 &heurdata->maxnlpiterabs, FALSE, DEFAULT_MAXNLPITERABS, 0, INT_MAX, NULL, NULL) ); 2710 SCIP_CALL( SCIPaddIntParam(scip, 2711 "heuristics/" HEUR_NAME "/maxnlpiterrel", 2712 "additional allowed number of NLP iterations relative to successfully found solutions", 2713 &heurdata->maxnlpiterrel, FALSE, DEFAULT_MAXNLPITERREL, 0, INT_MAX, NULL, NULL) ); 2714 SCIP_CALL( SCIPaddRealParam(scip, 2715 "heuristics/" HEUR_NAME "/maxdiveubquot", 2716 "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)", 2717 &heurdata->maxdiveubquot, TRUE, DEFAULT_MAXDIVEUBQUOT, 0.0, 1.0, NULL, NULL) ); 2718 SCIP_CALL( SCIPaddRealParam(scip, 2719 "heuristics/" HEUR_NAME "/maxdiveavgquot", 2720 "maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)", 2721 &heurdata->maxdiveavgquot, TRUE, DEFAULT_MAXDIVEAVGQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 2722 SCIP_CALL( SCIPaddRealParam(scip, 2723 "heuristics/" HEUR_NAME "/maxdiveubquotnosol", 2724 "maximal UBQUOT when no solution was found yet (0.0: no limit)", 2725 &heurdata->maxdiveubquotnosol, TRUE, DEFAULT_MAXDIVEUBQUOTNOSOL, 0.0, 1.0, NULL, NULL) ); 2726 SCIP_CALL( SCIPaddRealParam(scip, 2727 "heuristics/" HEUR_NAME "/maxdiveavgquotnosol", 2728 "maximal AVGQUOT when no solution was found yet (0.0: no limit)", 2729 &heurdata->maxdiveavgquotnosol, TRUE, DEFAULT_MAXDIVEAVGQUOTNOSOL, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 2730 SCIP_CALL( SCIPaddIntParam(scip, 2731 "heuristics/" HEUR_NAME "/maxfeasnlps", 2732 "maximal number of NLPs with feasible solution to solve during one dive", 2733 &heurdata->maxfeasnlps, FALSE, DEFAULT_MAXFEASNLPS, 1, INT_MAX, NULL, NULL) ); 2734 SCIP_CALL( SCIPaddBoolParam(scip, 2735 "heuristics/" HEUR_NAME "/backtrack", 2736 "use one level of backtracking if infeasibility is encountered?", 2737 &heurdata->backtrack, FALSE, DEFAULT_BACKTRACK, NULL, NULL) ); 2738 SCIP_CALL( SCIPaddBoolParam(scip, 2739 "heuristics/" HEUR_NAME "/lp", 2740 "should the LP relaxation be solved before the NLP relaxation?", 2741 &heurdata->lp, TRUE, DEFAULT_LP, NULL, NULL) ); 2742 SCIP_CALL( SCIPaddBoolParam(scip, 2743 "heuristics/" HEUR_NAME "/preferlpfracs", 2744 "prefer variables that are also fractional in LP solution?", 2745 &heurdata->preferlpfracs, TRUE, DEFAULT_PREFERLPFRACS, NULL, NULL) ); 2746 SCIP_CALL( SCIPaddRealParam(scip, 2747 "heuristics/" HEUR_NAME "/minsuccquot", 2748 "heuristic will not run if less then this percentage of calls succeeded (0.0: no limit)", 2749 &heurdata->minsuccquot, FALSE, DEFAULT_MINSUCCQUOT, 0.0, 1.0, NULL, NULL) ); 2750 SCIP_CALL( SCIPaddRealParam(scip, 2751 "heuristics/" HEUR_NAME "/fixquot", 2752 "percentage of fractional variables that should be fixed before the next NLP solve", 2753 &heurdata->fixquot, FALSE, DEFAULT_FIXQUOT, 0.0, 1.0, NULL, NULL) ); 2754 SCIP_CALL( SCIPaddBoolParam(scip, 2755 "heuristics/" HEUR_NAME "/prefercover", 2756 "should variables in a minimal cover be preferred?", 2757 &heurdata->prefercover, FALSE, DEFAULT_PREFERCOVER, NULL, NULL) ); 2758 SCIP_CALL( SCIPaddBoolParam(scip, 2759 "heuristics/" HEUR_NAME "/solvesubmip", 2760 "should a sub-MIP be solved if all cover variables are fixed?", 2761 &heurdata->solvesubmip, FALSE, DEFAULT_SOLVESUBMIP, NULL, NULL) ); 2762 SCIP_CALL( SCIPaddBoolParam(scip, 2763 "heuristics/" HEUR_NAME "/nlpfastfail", 2764 "should the NLP solver stop early if it converges slow?", 2765 &heurdata->nlpfastfail, FALSE, DEFAULT_NLPFASTFAIL, NULL, NULL) ); 2766 SCIP_CALL( SCIPaddCharParam(scip, 2767 "heuristics/" HEUR_NAME "/nlpstart", 2768 "which point should be used as starting point for the NLP solver? ('n'one, last 'f'easible, from dive's'tart)", 2769 &heurdata->nlpstart, TRUE, DEFAULT_NLPSTART, "fns", NULL, NULL) ); 2770 SCIP_CALL( SCIPaddCharParam(scip, 2771 "heuristics/" HEUR_NAME "/varselrule", 2772 "which variable selection should be used? ('f'ractionality, 'c'oefficient, 'p'seudocost, 'g'uided, 'd'ouble, 'v'eclen)", 2773 &heurdata->varselrule, FALSE, DEFAULT_VARSELRULE, "fcpgdv", NULL, NULL) ); 2774 2775 return SCIP_OKAY; 2776 } 2777