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_undercover.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief Undercover primal heuristic for MINLPs 28 * @author Timo Berthold 29 * @author Ambros Gleixner 30 * 31 * The undercover heuristic is designed for mixed-integer nonlinear programs and tries to fix a subset of variables such 32 * as to make each constraint linear or convex. For this purpose it solves a binary program to automatically determine 33 * the minimum number of variable fixings necessary. As fixing values, we use values from the LP relaxation, the NLP 34 * relaxation, or the incumbent solution. 35 * 36 * @todo use the conflict analysis to analyze the infeasibility which arise after the probing of the cover worked and 37 * solve returned infeasible, instead of adding the Nogood/Conflict by hand; that has the advantage that the SCIP 38 * takes care of creating the conflict and might shrink the initial reason 39 * 40 * @todo do not use LP and NLP fixing values in the same run, e.g., fixingalts = "lni", but start a second dive if LP 41 * values fail 42 */ 43 44 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 45 46 #include "blockmemshell/memory.h" 47 #include "scip/cons_and.h" 48 #include "scip/cons_bounddisjunction.h" 49 #include "scip/cons_nonlinear.h" 50 #include "scip/cons_indicator.h" 51 #include "scip/cons_linear.h" 52 #include "scip/cons_logicor.h" 53 #include "scip/cons_setppc.h" 54 #include "scip/heur_subnlp.h" 55 #include "scip/heur_undercover.h" 56 #include "scip/pub_cons.h" 57 #include "scip/pub_expr.h" 58 #include "scip/pub_heur.h" 59 #include "scip/pub_message.h" 60 #include "scip/pub_misc.h" 61 #include "scip/pub_misc_sort.h" 62 #include "scip/pub_nlp.h" 63 #include "scip/pub_var.h" 64 #include "scip/scip_branch.h" 65 #include "scip/scip_cons.h" 66 #include "scip/scip_copy.h" 67 #include "scip/scipdefplugins.h" 68 #include "scip/scip_general.h" 69 #include "scip/scip_heur.h" 70 #include "scip/scip_lp.h" 71 #include "scip/scip_mem.h" 72 #include "scip/scip_message.h" 73 #include "scip/scip_nlp.h" 74 #include "scip/scip_numerics.h" 75 #include "scip/scip_param.h" 76 #include "scip/scip_prob.h" 77 #include "scip/scip_probing.h" 78 #include "scip/scip_randnumgen.h" 79 #include "scip/scip_sol.h" 80 #include "scip/scip_solve.h" 81 #include "scip/scip_solvingstats.h" 82 #include "scip/scip_timing.h" 83 #include "scip/scip_tree.h" 84 #include "scip/scip_var.h" 85 #include <string.h> 86 87 #define HEUR_NAME "undercover" 88 #define HEUR_DESC "solves a sub-CIP determined by a set covering approach" 89 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS 90 #define HEUR_PRIORITY -1110000 91 #define HEUR_FREQ 0 92 #define HEUR_FREQOFS 0 93 #define HEUR_MAXDEPTH -1 94 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE 95 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */ 96 97 /* default values for user parameters, grouped by parameter type */ 98 #define DEFAULT_FIXINGALTS "li" /**< sequence of fixing values used: 'l'p relaxation, 'n'lp relaxation, 'i'ncumbent solution */ 99 100 #define DEFAULT_MAXNODES (SCIP_Longint)500/**< maximum number of nodes to regard in the subproblem */ 101 #define DEFAULT_MINNODES (SCIP_Longint)500/**< minimum number of nodes to regard in the subproblem */ 102 #define DEFAULT_NODESOFS (SCIP_Longint)500/**< number of nodes added to the contingent of the total nodes */ 103 104 #define DEFAULT_CONFLICTWEIGHT 1000.0 /**< weight for conflict score in fixing order */ 105 #define DEFAULT_CUTOFFWEIGHT 1.0 /**< weight for cutoff score in fixing order */ 106 #define DEFAULT_INFERENCEWEIGHT 1.0 /**< weight for inference score in fixing order */ 107 #define DEFAULT_MAXCOVERSIZEVARS 1.0 /**< maximum coversize (as fraction of total number of variables) */ 108 #define DEFAULT_MAXCOVERSIZECONSS SCIP_REAL_MAX /**< maximum coversize (as ratio to the percentage of non-affected constraints) */ 109 #define DEFAULT_MINCOVEREDREL 0.15 /**< minimum percentage of nonlinear constraints in the original problem */ 110 #define DEFAULT_MINCOVEREDABS 5 /**< minimum number of nonlinear constraints in the original problem */ 111 #define DEFAULT_MINIMPROVE 0.0 /**< factor by which heuristic should at least improve the incumbent */ 112 #define DEFAULT_NODESQUOT 0.1 /**< subproblem nodes in relation to nodes of the original problem */ 113 #define DEFAULT_RECOVERDIV 0.9 /**< fraction of covering variables in the last cover which need to change their value when recovering */ 114 115 #define DEFAULT_MAXBACKTRACKS 6 /**< maximum number of backtracks */ 116 #define DEFAULT_MAXRECOVERS 0 /**< maximum number of recoverings */ 117 #define DEFAULT_MAXREORDERS 1 /**< maximum number of reorderings of the fixing order */ 118 119 #define DEFAULT_COVERINGOBJ 'u' /**< objective function of the covering problem */ 120 #define DEFAULT_FIXINGORDER 'v' /**< order in which variables should be fixed */ 121 122 #define DEFAULT_BEFORECUTS TRUE /**< should undercover called at root node before cut separation? */ 123 #define DEFAULT_FIXINTFIRST FALSE /**< should integer variables in the cover be fixed first? */ 124 #define DEFAULT_LOCKSROUNDING TRUE /**< shall LP values for integer vars be rounded according to locks? */ 125 #define DEFAULT_ONLYCONVEXIFY FALSE /**< should we only fix/dom.red. variables creating nonconvexity? */ 126 #define DEFAULT_POSTNLP TRUE /**< should the NLP heuristic be called to polish a feasible solution? */ 127 #define DEFAULT_COVERAND TRUE /**< should and constraints be covered (or just copied)? */ 128 #define DEFAULT_COVERBD FALSE /**< should bounddisjunction constraints be covered (or just copied)? */ 129 #define DEFAULT_COVERIND FALSE /**< should indicator constraints be covered (or just copied)? */ 130 #define DEFAULT_COVERNL TRUE /**< should nonlinear constraints be covered (or just copied)? */ 131 #define DEFAULT_REUSECOVER FALSE /**< shall the cover be re-used if a conflict was added after an infeasible subproblem? */ 132 #define DEFAULT_COPYCUTS TRUE /**< should all active cuts from the cutpool of the original scip be copied 133 * to constraints of the subscip 134 */ 135 #define DEFAULT_RANDSEED 43 /* initial random seed */ 136 137 /* local defines */ 138 #define COVERINGOBJS "cdlmtu" /**< list of objective functions of the covering problem */ 139 #define FIXINGORDERS "CcVv" /**< list of orders in which variables can be fixed */ 140 #define MAXNLPFAILS 1 /**< maximum number of fails after which we give up solving the NLP relaxation */ 141 #define MAXPOSTNLPFAILS 1 /**< maximum number of fails after which we give up calling NLP local search */ 142 #define MINTIMELEFT 1.0 /**< don't start expensive parts of the heuristics if less than this amount of time left */ 143 #define SUBMIPSETUPCOSTS 200 /**< number of nodes equivalent for the costs for setting up the sub-CIP */ 144 145 146 /* 147 * Data structures 148 */ 149 150 /** primal heuristic data */ 151 struct SCIP_HeurData 152 { 153 SCIP_CONSHDLR** nlconshdlrs; /**< array of nonlinear constraint handlers */ 154 SCIP_HEUR* nlpheur; /**< pointer to NLP local search heuristics */ 155 SCIP_RANDNUMGEN* randnumgen; /**< random number generator */ 156 char* fixingalts; /**< sequence of fixing values used: 'l'p relaxation, 'n'lp relaxation, 'i'ncumbent solution */ 157 SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */ 158 SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */ 159 SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */ 160 SCIP_Longint nusednodes; /**< nodes already used by heuristic in earlier calls */ 161 SCIP_Real conflictweight; /**< weight for conflict score in fixing order */ 162 SCIP_Real cutoffweight; /**< weight for cutoff score in fixing order */ 163 SCIP_Real inferenceweight; /**< weight for inference score in foxing order */ 164 SCIP_Real maxcoversizevars; /**< maximum coversize (as fraction of total number of variables) */ 165 SCIP_Real maxcoversizeconss; /**< maximum coversize (as ratio to the percentage of non-affected constraints) */ 166 SCIP_Real mincoveredrel; /**< minimum percentage of nonlinear constraints in the original problem */ 167 SCIP_Real minimprove; /**< factor by which heuristic should at least improve the incumbent */ 168 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */ 169 SCIP_Real recoverdiv; /**< fraction of covering variables in the last cover which need to change their value when recovering */ 170 int mincoveredabs; /**< minimum number of nonlinear constraints in the original problem */ 171 int maxbacktracks; /**< maximum number of backtracks */ 172 int maxrecovers; /**< maximum number of recoverings */ 173 int maxreorders; /**< maximum number of reorderings of the fixing order */ 174 int nfixingalts; /**< number of fixing alternatives */ 175 int nnlpfails; /**< number of fails when solving the NLP relaxation after last success */ 176 int npostnlpfails; /**< number of fails of the NLP local search after last success */ 177 int nnlconshdlrs; /**< number of nonlinear constraint handlers */ 178 char coveringobj; /**< objective function of the covering problem */ 179 char fixingorder; /**< order in which variables should be fixed */ 180 SCIP_Bool beforecuts; /**< should undercover be called at root node before cut separation? */ 181 SCIP_Bool fixintfirst; /**< should integer variables in the cover be fixed first? */ 182 SCIP_Bool globalbounds; /**< should global bounds on variables be used instead of local bounds at focus node? */ 183 SCIP_Bool locksrounding; /**< shall LP values for integer vars be rounded according to locks? */ 184 SCIP_Bool nlpsolved; /**< has current NLP relaxation already been solved successfully? */ 185 SCIP_Bool nlpfailed; /**< has solving the NLP relaxation failed? */ 186 SCIP_Bool onlyconvexify; /**< should we only fix/dom.red. variables creating nonconvexity? */ 187 SCIP_Bool postnlp; /**< should the NLP heuristic be called to polish a feasible solution? */ 188 SCIP_Bool coverand; /**< should and constraints be covered (or just copied)? */ 189 SCIP_Bool coverbd; /**< should bounddisjunction constraints be covered (or just copied)? */ 190 SCIP_Bool coverind; /**< should indicator constraints be covered (or just copied)? */ 191 SCIP_Bool covernl; /**< should nonlinear constraints be covered (or just copied)? */ 192 SCIP_Bool reusecover; /**< shall the cover be re-used if a conflict was added after an infeasible subproblem? */ 193 SCIP_Bool copycuts; /**< should all active cuts from cutpool be copied to constraints in 194 * subproblem? */ 195 }; 196 197 /* 198 * Local methods 199 */ 200 201 202 /** determines, whether a variable is fixed to the given value */ 203 static 204 SCIP_Bool varIsFixed( 205 SCIP* scip, /**< SCIP data structure */ 206 SCIP_VAR* var, /**< variable to check */ 207 SCIP_Real val, /**< value to check */ 208 SCIP_Bool global /**< should global bounds be used? */ 209 ) 210 { 211 SCIP_Bool isfixed; 212 213 if( global ) 214 isfixed = SCIPisFeasEQ(scip, val, SCIPvarGetLbGlobal(var)) && SCIPisFeasEQ(scip, val, SCIPvarGetUbGlobal(var)); 215 else 216 isfixed = SCIPisFeasEQ(scip, val, SCIPvarGetLbLocal(var)) && SCIPisFeasEQ(scip, val, SCIPvarGetUbLocal(var)); 217 218 return isfixed; 219 } 220 221 222 /** determines, whether a term is already constant, because the variable is fixed or the coefficient is zero */ 223 static 224 SCIP_Bool termIsConstant( 225 SCIP* scip, /**< SCIP data structure */ 226 SCIP_VAR* var, /**< variable to check */ 227 SCIP_Real coeff, /**< coefficient to check */ 228 SCIP_Bool global /**< should global bounds be used? */ 229 ) 230 { 231 /* if the variable has zero coefficient in the original problem, the term is linear */ 232 if( SCIPisZero(scip, coeff) ) 233 return TRUE; 234 235 /* if the variable is fixed in the original problem, the term is linear */ 236 if( global ) 237 return SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var)); 238 else 239 return SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)); 240 } 241 242 243 /** determines, whether a term is convex */ 244 static 245 SCIP_Bool termIsConvex( 246 SCIP* scip, /**< SCIP data structure */ 247 SCIP_Real lhs, /**< left hand side of the constraint */ 248 SCIP_Real rhs, /**< right hand side of the constraint */ 249 SCIP_Bool sign /**< signature of the term */ 250 ) 251 { 252 return sign ? SCIPisInfinity(scip, -lhs) : SCIPisInfinity(scip, rhs); 253 } 254 255 256 /** increases counters */ 257 static 258 void incCounters( 259 int* termcounter, /**< array to count in how many nonlinear terms a variable appears */ 260 int* conscounter, /**< array to count in how many constraints a variable appears */ 261 SCIP_Bool* consmarker, /**< was this variable already counted for this constraint? */ 262 int idx /**< problem index of the variable */ 263 ) 264 { 265 termcounter[idx]++; 266 if( !consmarker[idx] ) 267 { 268 conscounter[idx]++; 269 consmarker[idx] = TRUE; 270 } 271 return; 272 } 273 274 275 /** update time limit */ 276 static 277 SCIP_RETCODE updateTimelimit( 278 SCIP* scip, /**< SCIP data structure */ 279 SCIP_CLOCK* clck, /**< clock timer */ 280 SCIP_Real* timelimit /**< time limit */ 281 ) 282 { 283 *timelimit -= SCIPgetClockTime(scip, clck); 284 SCIP_CALL( SCIPresetClock(scip, clck) ); 285 SCIP_CALL( SCIPstartClock(scip, clck) ); 286 287 return SCIP_OKAY; 288 } 289 290 291 /** analyzes a nonlinear row and adds constraints and fixings to the covering problem */ 292 static 293 SCIP_RETCODE processNlRow( 294 SCIP* scip, /**< original SCIP data structure */ 295 SCIP_NLROW* nlrow, /**< nonlinear row representation of a nonlinear constraint */ 296 SCIP* coveringscip, /**< SCIP data structure for the covering problem */ 297 int nvars, /**< number of variables */ 298 SCIP_VAR** coveringvars, /**< array to store the covering problem's variables */ 299 int* termcounter, /**< counter array for number of nonlinear nonzeros per variable */ 300 int* conscounter, /**< counter array for number of nonlinear constraints per variable */ 301 SCIP_Bool* consmarker, /**< marker array if constraint has been counted in conscounter */ 302 SCIP_Bool globalbounds, /**< should global bounds on variables be used instead of local bounds at focus node? */ 303 SCIP_Bool onlyconvexify, /**< should we only fix/dom.red. variables creating nonconvexity? */ 304 SCIP_Bool* success /**< pointer to store whether row was processed successfully */ 305 ) 306 { 307 SCIP_EXPR* expr; 308 SCIP_Bool infeas; 309 SCIP_Bool fixed; 310 int t; 311 char name[SCIP_MAXSTRLEN]; 312 313 assert(scip != NULL); 314 assert(nlrow != NULL); 315 assert(coveringscip != NULL); 316 assert(nvars >= 1); 317 assert(coveringvars != NULL); 318 assert(termcounter != NULL); 319 assert(conscounter != NULL); 320 assert(consmarker != NULL); 321 assert(success != NULL); 322 323 *success = FALSE; 324 325 /* if we only want to convexify and curvature and bounds prove already convexity, nothing to do */ 326 if( onlyconvexify 327 && ( SCIPnlrowGetCurvature(nlrow) == SCIP_EXPRCURV_LINEAR 328 || (SCIPisInfinity(scip, -SCIPnlrowGetLhs(nlrow)) && SCIPnlrowGetCurvature(nlrow) == SCIP_EXPRCURV_CONVEX ) 329 || (SCIPisInfinity(scip, SCIPnlrowGetRhs(nlrow)) && SCIPnlrowGetCurvature(nlrow) == SCIP_EXPRCURV_CONCAVE)) ) 330 { 331 *success = TRUE; 332 return SCIP_OKAY; 333 } 334 335 BMSclearMemoryArray(consmarker, nvars); 336 337 /* go through expression */ 338 expr = SCIPnlrowGetExpr(nlrow); 339 if( expr != NULL ) 340 { 341 SCIP_Bool isquadratic; 342 343 SCIP_CALL( SCIPcheckExprQuadratic(scip, expr, &isquadratic) ); 344 if( isquadratic && SCIPexprAreQuadraticExprsVariables(expr) ) 345 { 346 int nquadexprs; 347 int nbilinexprs; 348 349 SCIPexprGetQuadraticData(expr, NULL, NULL, NULL, NULL, &nquadexprs, &nbilinexprs, NULL, NULL); 350 351 /* go through all quadratic terms */ 352 for( t = 0; t < nquadexprs; ++t ) 353 { 354 SCIP_EXPR* varexpr; 355 SCIP_Real sqrcoef; 356 int probidx; 357 358 SCIPexprGetQuadraticQuadTerm(expr, t, &varexpr, NULL, &sqrcoef, 0, NULL, NULL); 359 360 /* term is constant, nothing to do */ 361 if( termIsConstant(scip, SCIPgetVarExprVar(varexpr), sqrcoef, globalbounds) ) 362 continue; 363 364 /* if we only convexify and term is convex considering the bounds of the nlrow, nothing to do */ 365 if( onlyconvexify && termIsConvex(scip, SCIPnlrowGetLhs(nlrow), SCIPnlrowGetRhs(nlrow), sqrcoef >= 0) ) 366 continue; 367 368 probidx = SCIPvarGetProbindex(SCIPgetVarExprVar(varexpr)); 369 if( probidx == -1 ) 370 { 371 SCIPdebugMsg(scip, "inactive variable detected in nonlinear row <%s>\n", SCIPnlrowGetName(nlrow)); 372 return SCIP_OKAY; 373 } 374 assert(coveringvars[probidx] != NULL); 375 376 /* otherwise variable has to be in the cover */ 377 SCIP_CALL( SCIPfixVar(coveringscip, coveringvars[probidx], 1.0, &infeas, &fixed) ); 378 assert(!infeas); 379 assert(fixed); 380 381 /* update counters */ 382 incCounters(termcounter, conscounter, consmarker, probidx); 383 384 SCIPdebugMsg(scip, "fixing var <%s> in covering problem to 1\n", SCIPvarGetName(coveringvars[probidx])); 385 } 386 387 /* go through all bilinear terms */ 388 for( t = 0; t < nbilinexprs; ++t ) 389 { 390 SCIP_EXPR* varexpr1; 391 SCIP_EXPR* varexpr2; 392 SCIP_Real bilincoef; 393 int probidx1; 394 int probidx2; 395 SCIP_CONS* coveringcons; 396 SCIP_VAR* coveringconsvars[2]; 397 398 SCIPexprGetQuadraticBilinTerm(expr, t, &varexpr1, &varexpr2, &bilincoef, NULL, NULL); 399 400 /* if the term is linear because one of the variables is fixed or the coefficient is zero, nothing to do */ 401 if( termIsConstant(scip, SCIPgetVarExprVar(varexpr1), bilincoef, globalbounds) 402 || termIsConstant(scip, SCIPgetVarExprVar(varexpr2), bilincoef, globalbounds) ) 403 continue; 404 405 probidx1 = SCIPvarGetProbindex(SCIPgetVarExprVar(varexpr1)); 406 probidx2 = SCIPvarGetProbindex(SCIPgetVarExprVar(varexpr2)); 407 if( probidx1 == -1 || probidx2 == -1 ) 408 { 409 SCIPdebugMsg(scip, "inactive variables detected in nonlinear row <%s>\n", SCIPnlrowGetName(nlrow)); 410 return SCIP_OKAY; 411 } 412 assert(coveringvars[probidx1] != NULL); 413 assert(coveringvars[probidx2] != NULL); 414 415 /* create covering constraint */ 416 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering%d", SCIPnlrowGetName(nlrow), t); 417 coveringconsvars[0] = coveringvars[probidx1]; 418 coveringconsvars[1] = coveringvars[probidx2]; 419 SCIP_CALL( SCIPcreateConsSetcover(coveringscip, &coveringcons, name, 2, coveringconsvars, 420 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) ); 421 422 if( coveringcons == NULL ) 423 { 424 SCIPdebugMsg(scip, "failed to create set covering constraint <%s>\n", name); 425 return SCIP_OKAY; 426 } 427 428 /* add and release covering constraint */ 429 SCIP_CALL( SCIPaddCons(coveringscip, coveringcons) ); 430 SCIP_CALL( SCIPreleaseCons(coveringscip, &coveringcons) ); 431 432 /* update counters for both variables */ 433 incCounters(termcounter, conscounter, consmarker, probidx1); 434 incCounters(termcounter, conscounter, consmarker, probidx2); 435 } 436 } 437 else 438 { 439 /* fix all variables contained in the expression */ 440 SCIP_EXPRITER* it; 441 int probidx; 442 443 SCIP_CALL( SCIPcreateExpriter(scip, &it) ); 444 SCIP_CALL( SCIPexpriterInit(it, expr, SCIP_EXPRITER_DFS, FALSE) ); 445 for( ; !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) ) /*lint !e441*/ /*lint !e440*/ 446 { 447 if( !SCIPisExprVar(scip, expr) ) 448 continue; 449 450 /* if constraints with inactive variables are present, we will have difficulties creating the sub-CIP later */ 451 probidx = SCIPvarGetProbindex(SCIPgetVarExprVar(expr)); 452 if( probidx == -1 ) 453 { 454 SCIPdebugMsg(scip, "strange: inactive variable <%s> detected in nonlinear row <%s>\n", 455 SCIPvarGetName(SCIPgetVarExprVar(expr)), SCIPnlrowGetName(nlrow)); 456 return SCIP_OKAY; 457 } 458 assert(coveringvars[probidx] != NULL); 459 460 /* term is constant, nothing to do */ 461 if( termIsConstant(scip, SCIPgetVarExprVar(expr), 1.0, globalbounds) ) 462 continue; 463 464 /* otherwise fix variable */ 465 SCIP_CALL( SCIPfixVar(coveringscip, coveringvars[probidx], 1.0, &infeas, &fixed) ); 466 assert(!infeas); 467 assert(fixed); 468 469 /* update counters */ 470 incCounters(termcounter, conscounter, consmarker, probidx); 471 472 SCIPdebugMsg(scip, "fixing var <%s> in covering problem to 1\n", SCIPvarGetName(coveringvars[probidx])); 473 } 474 SCIPfreeExpriter(&it); 475 } 476 } 477 *success = TRUE; 478 479 return SCIP_OKAY; 480 } 481 482 483 /** creates the covering problem to determine a number of variables to be fixed */ 484 static 485 SCIP_RETCODE createCoveringProblem( 486 SCIP* scip, /**< original SCIP data structure */ 487 SCIP* coveringscip, /**< SCIP data structure for the covering problem */ 488 SCIP_VAR** coveringvars, /**< array to store the covering problem's variables */ 489 SCIP_Bool globalbounds, /**< should global bounds on variables be used instead of local bounds at focus node? */ 490 SCIP_Bool onlyconvexify, /**< should we only fix/dom.red. variables creating nonconvexity? */ 491 SCIP_Bool coverand, /**< should and constraints be covered (or just copied)? */ 492 SCIP_Bool coverbd, /**< should bounddisjunction constraints be covered (or just copied)? */ 493 SCIP_Bool coverind, /**< should indicator constraints be covered (or just copied)? */ 494 SCIP_Bool covernl, /**< should nonlinear constraints be covered (or just copied)? */ 495 char coveringobj, /**< objective function of the covering problem */ 496 SCIP_Bool* success /**< pointer to store whether the problem was created successfully */ 497 ) 498 { 499 SCIP_VAR** vars; 500 SCIP_CONSHDLR* conshdlr; 501 SCIP_Bool* consmarker; 502 int* conscounter; 503 int* termcounter; 504 505 int nlocksup; 506 int nlocksdown; 507 int nvars; 508 int i; 509 int probindex; 510 char name[SCIP_MAXSTRLEN]; 511 512 assert(scip != NULL); 513 assert(coveringscip != NULL); 514 assert(coveringvars != NULL); 515 assert(success != NULL); 516 517 *success = FALSE; 518 519 /* get required data of the original problem */ 520 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 521 522 /* create problem data structure */ 523 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering", SCIPgetProbName(scip)); 524 SCIP_CALL( SCIPcreateProb(coveringscip, name, NULL, NULL, NULL, NULL, NULL, NULL, NULL) ); 525 SCIPsetSubscipDepth(coveringscip, SCIPgetSubscipDepth(scip) + 1); 526 527 /* allocate and initialize to zero counter arrays for weighted objectives */ 528 SCIP_CALL( SCIPallocBufferArray(scip, &consmarker, nvars) ); 529 SCIP_CALL( SCIPallocBufferArray(scip, &conscounter, nvars) ); 530 SCIP_CALL( SCIPallocBufferArray(scip, &termcounter, nvars) ); 531 BMSclearMemoryArray(conscounter, nvars); 532 BMSclearMemoryArray(termcounter, nvars); 533 534 /* create covering variable for each variable in the original problem (fix it or not?) in the same order as in the 535 * original problem 536 */ 537 for( i = 0; i < nvars; i++ ) 538 { 539 SCIP_Real ub = 1.0; 540 541 if( SCIPvarIsRelaxationOnly(vars[i]) ) 542 { 543 /* skip relaxation-only variables; they cannot appear in constraints */ 544 coveringvars[i] = NULL; 545 continue; 546 } 547 548 /* if the variable in the original problem is fixed, then the corresponding cover variable cannot be 1 in any 549 * optimal solution of the covering problem (see special termIsConstant treatment below) 550 * since some calling code may assume that no fixed variables will appear in the cover (see #1845), but we 551 * might not compute an optimal cover here, we fix these variable to 0 here 552 */ 553 if( globalbounds ) 554 { 555 if( SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(vars[i]), SCIPvarGetUbGlobal(vars[i])) ) 556 ub = 0.0; 557 } 558 else 559 { 560 if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i])) ) 561 ub = 0.0; 562 } 563 564 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering", SCIPvarGetName(vars[i])); 565 SCIP_CALL( SCIPcreateVar(coveringscip, &coveringvars[i], name, 0.0, ub, 1.0, SCIP_VARTYPE_BINARY, 566 TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) ); 567 assert(coveringvars[i] != NULL); 568 SCIP_CALL( SCIPaddVar(coveringscip, coveringvars[i]) ); 569 } 570 571 /* go through all AND constraints in the original problem */ 572 conshdlr = SCIPfindConshdlr(scip, "and"); 573 if( conshdlr != NULL && coverand ) 574 { 575 int c; 576 577 for( c = SCIPconshdlrGetNActiveConss(conshdlr)-1; c >= 0; c-- ) 578 { 579 SCIP_CONS* andcons; 580 SCIP_CONS* coveringcons; 581 SCIP_VAR** andvars; 582 SCIP_VAR* andres; 583 SCIP_VAR** coveringconsvars; 584 SCIP_Real* coveringconsvals; 585 SCIP_Bool negated; 586 587 int ntofix; 588 int v; 589 590 /* get constraint and variables */ 591 andcons = SCIPconshdlrGetConss(conshdlr)[c]; 592 assert(andcons != NULL); 593 andvars = SCIPgetVarsAnd(scip, andcons); 594 assert(andvars != NULL); 595 596 /* allocate memory for covering constraint */ 597 SCIP_CALL( SCIPallocBufferArray(coveringscip, &coveringconsvars, SCIPgetNVarsAnd(scip, andcons)+1) ); 598 SCIP_CALL( SCIPallocBufferArray(coveringscip, &coveringconsvals, SCIPgetNVarsAnd(scip, andcons)+1) ); 599 600 /* collect unfixed variables */ 601 BMSclearMemoryArray(consmarker, nvars); 602 ntofix = 0; 603 for( v = SCIPgetNVarsAnd(scip, andcons)-1; v >= 0; v-- ) 604 { 605 assert(andvars[v] != NULL); 606 negated = FALSE; 607 608 /* if variable is fixed to 0, entire constraint can be linearized */ 609 if( varIsFixed(scip, andvars[v], 0.0, globalbounds) ) 610 { 611 ntofix = 0; 612 break; 613 } 614 615 /* if variable is fixed, nothing to do */ 616 if( termIsConstant(scip, andvars[v], 1.0, globalbounds) ) 617 { 618 continue; 619 } 620 621 /* if constraints with inactive variables are present, we have to find the corresponding active variable */ 622 probindex = SCIPvarGetProbindex(andvars[v]); 623 if( probindex == -1 ) 624 { 625 SCIP_VAR* repvar; 626 627 /* get binary representative of variable */ 628 SCIP_CALL( SCIPgetBinvarRepresentative(scip, andvars[v], &repvar, &negated) ); 629 assert(repvar != NULL); 630 assert(SCIPvarGetStatus(repvar) != SCIP_VARSTATUS_FIXED); 631 632 if( SCIPvarGetStatus(repvar) == SCIP_VARSTATUS_MULTAGGR ) 633 { 634 SCIPdebugMsg(scip, "strange: multiaggregated variable found <%s>\n", SCIPvarGetName(andvars[v])); 635 SCIPdebugMsg(scip, "inactive variables detected in constraint <%s>\n", SCIPconsGetName(andcons)); 636 SCIPfreeBufferArray(coveringscip, &coveringconsvals); 637 SCIPfreeBufferArray(coveringscip, &coveringconsvars); 638 goto TERMINATE; 639 } 640 641 /* check for negation */ 642 if( SCIPvarIsNegated(repvar) ) 643 { 644 probindex = SCIPvarGetProbindex(SCIPvarGetNegationVar(repvar)); 645 negated = TRUE; 646 } 647 else 648 { 649 assert(SCIPvarIsActive(repvar)); 650 probindex = SCIPvarGetProbindex(repvar); 651 negated = FALSE; 652 } 653 } 654 assert(probindex >= 0); 655 assert(coveringvars[probindex] != NULL); 656 657 /* add covering variable for unfixed original variable */ 658 if( negated ) 659 { 660 SCIP_CALL( SCIPgetNegatedVar(coveringscip, coveringvars[probindex], &coveringconsvars[ntofix]) ); 661 } 662 else 663 coveringconsvars[ntofix] = coveringvars[probindex]; 664 coveringconsvals[ntofix] = 1.0; 665 ntofix++; 666 } 667 negated = FALSE; 668 669 /* if constraints with inactive variables are present, we have to find the corresponding active variable */ 670 andres = SCIPgetResultantAnd(scip, andcons); 671 assert(andres != NULL); 672 probindex = SCIPvarGetProbindex(andres); 673 674 /* if resultant is fixed this constraint can be either linearized or is redundant because all operands can be fixed */ 675 if( termIsConstant(scip, andres, 1.0, globalbounds) ) 676 { 677 /* free memory for covering constraint */ 678 SCIPfreeBufferArray(coveringscip, &coveringconsvals); 679 SCIPfreeBufferArray(coveringscip, &coveringconsvars); 680 681 continue; 682 } 683 684 if( probindex == -1 ) 685 { 686 SCIP_VAR* repvar; 687 688 /* get binary representative of variable */ 689 SCIP_CALL( SCIPgetBinvarRepresentative(scip, SCIPgetResultantAnd(scip, andcons), &repvar, &negated) ); 690 assert(repvar != NULL); 691 assert(SCIPvarGetStatus(repvar) != SCIP_VARSTATUS_FIXED); 692 693 if( SCIPvarGetStatus(repvar) == SCIP_VARSTATUS_MULTAGGR ) 694 { 695 SCIPdebugMsg(scip, "strange: multiaggregated variable found <%s>\n", SCIPvarGetName(SCIPgetResultantAnd(scip, andcons))); 696 SCIPdebugMsg(scip, "inactive variables detected in constraint <%s>\n", SCIPconsGetName(andcons)); 697 SCIPfreeBufferArray(coveringscip, &coveringconsvals); 698 SCIPfreeBufferArray(coveringscip, &coveringconsvars); 699 goto TERMINATE; 700 } 701 702 /* check for negation */ 703 if( SCIPvarIsNegated(repvar) ) 704 { 705 probindex = SCIPvarGetProbindex(SCIPvarGetNegationVar(repvar)); 706 negated = TRUE; 707 } 708 else 709 { 710 assert(SCIPvarIsActive(repvar)); 711 probindex = SCIPvarGetProbindex(repvar); 712 negated = FALSE; 713 } 714 } 715 else if( SCIPvarGetLbGlobal(andres) > 0.5 || SCIPvarGetUbGlobal(andres) < 0.5 ) 716 { 717 /* free memory for covering constraint */ 718 SCIPfreeBufferArray(coveringscip, &coveringconsvals); 719 SCIPfreeBufferArray(coveringscip, &coveringconsvars); 720 721 continue; 722 } 723 assert(probindex >= 0); 724 assert(coveringvars[probindex] != NULL); 725 assert(!termIsConstant(scip, (negated ? SCIPvarGetNegatedVar(vars[probindex]) : vars[probindex]), 1.0, globalbounds)); 726 727 /* if less than two variables are unfixed or the resultant variable is fixed, the entire constraint can be linearized anyway */ 728 if( ntofix >= 2 ) 729 { 730 assert(ntofix <= SCIPgetNVarsAnd(scip, andcons)); 731 732 /* add covering variable for unfixed resultant */ 733 if( negated ) 734 { 735 SCIP_CALL( SCIPgetNegatedVar(coveringscip, coveringvars[probindex], &coveringconsvars[ntofix]) ); 736 } 737 else 738 coveringconsvars[ntofix] = coveringvars[probindex]; 739 coveringconsvals[ntofix] = (SCIP_Real)(ntofix - 1); 740 ntofix++; 741 742 /* create covering constraint */ 743 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering", SCIPconsGetName(andcons)); 744 SCIP_CALL( SCIPcreateConsLinear(coveringscip, &coveringcons, name, ntofix, coveringconsvars, coveringconsvals, 745 (SCIP_Real)(ntofix - 1), SCIPinfinity(coveringscip), 746 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) ); 747 748 if( coveringcons == NULL ) 749 { 750 SCIPdebugMsg(scip, "failed to create linear constraint <%s>\n", name); 751 SCIPfreeBufferArray(coveringscip, &coveringconsvals); 752 SCIPfreeBufferArray(coveringscip, &coveringconsvars); 753 goto TERMINATE; 754 } 755 756 /* add and release covering constraint */ 757 SCIP_CALL( SCIPaddCons(coveringscip, coveringcons) ); 758 SCIP_CALL( SCIPreleaseCons(coveringscip, &coveringcons) ); 759 760 /* update counters */ 761 for( v = ntofix-1; v >= 0; v-- ) 762 if( SCIPvarIsNegated(coveringconsvars[v]) ) 763 incCounters(termcounter, conscounter, consmarker, SCIPvarGetProbindex(SCIPvarGetNegationVar(coveringconsvars[v]))); 764 else 765 incCounters(termcounter, conscounter, consmarker, SCIPvarGetProbindex(coveringconsvars[v])); 766 } 767 768 /* free memory for covering constraint */ 769 SCIPfreeBufferArray(coveringscip, &coveringconsvals); 770 SCIPfreeBufferArray(coveringscip, &coveringconsvars); 771 } 772 } 773 774 /* go through all bounddisjunction constraints in the original problem */ 775 conshdlr = SCIPfindConshdlr(scip, "bounddisjunction"); 776 if( conshdlr != NULL && coverbd ) 777 { 778 int c; 779 780 for( c = SCIPconshdlrGetNActiveConss(conshdlr)-1; c >= 0; c-- ) 781 { 782 SCIP_CONS* bdcons; 783 SCIP_CONS* coveringcons; 784 SCIP_VAR** bdvars; 785 SCIP_VAR** coveringconsvars; 786 SCIP_Real* coveringconsvals; 787 788 int nbdvars; 789 int ntofix; 790 int v; 791 792 /* get constraint and variables */ 793 bdcons = SCIPconshdlrGetConss(conshdlr)[c]; 794 assert(bdcons != NULL); 795 bdvars = SCIPgetVarsBounddisjunction(scip, bdcons); 796 assert(bdvars != NULL); 797 nbdvars = SCIPgetNVarsBounddisjunction(scip, bdcons); 798 799 /* bounddisjunction constraints are not passed to the NLP, hence nothing to store in the hash map */ 800 801 /* allocate memory for covering constraint */ 802 SCIP_CALL( SCIPallocBufferArray(coveringscip, &coveringconsvars, nbdvars) ); 803 SCIP_CALL( SCIPallocBufferArray(coveringscip, &coveringconsvals, nbdvars) ); 804 805 /* collect unfixed variables */ 806 BMSclearMemoryArray(consmarker, nvars); 807 ntofix = 0; 808 for( v = nbdvars-1; v >= 0; v-- ) 809 { 810 SCIP_Bool negated; 811 812 assert(bdvars[v] != NULL); 813 negated = FALSE; 814 815 /* if variable is fixed, nothing to do */ 816 if( varIsFixed(scip, bdvars[v], globalbounds ? SCIPvarGetLbGlobal(bdvars[v]) : SCIPvarGetLbLocal(bdvars[v]), 817 globalbounds) ) 818 { 819 continue; 820 } 821 822 /* if constraints with inactive variables are present, we have to find the corresponding active variable */ 823 probindex = SCIPvarGetProbindex(bdvars[v]); 824 if( probindex == -1 ) 825 { 826 SCIP_VAR* repvar; 827 828 /* get binary representative of variable */ 829 SCIP_CALL( SCIPgetBinvarRepresentative(scip, bdvars[v], &repvar, &negated) ); 830 assert(repvar != NULL); 831 assert(SCIPvarGetStatus(repvar) != SCIP_VARSTATUS_FIXED); 832 833 if( SCIPvarGetStatus(repvar) == SCIP_VARSTATUS_MULTAGGR ) 834 { 835 SCIPdebugMsg(scip, "strange: multiaggregated variable found <%s>\n", SCIPvarGetName(bdvars[v])); 836 SCIPdebugMsg(scip, "inactive variables detected in constraint <%s>\n", SCIPconsGetName(bdcons)); 837 SCIPfreeBufferArray(coveringscip, &coveringconsvals); 838 SCIPfreeBufferArray(coveringscip, &coveringconsvars); 839 goto TERMINATE; 840 } 841 842 /* check for negation */ 843 if( SCIPvarIsNegated(repvar) ) 844 { 845 probindex = SCIPvarGetProbindex(SCIPvarGetNegationVar(repvar)); 846 negated = TRUE; 847 } 848 else 849 { 850 assert(SCIPvarIsActive(repvar)); 851 probindex = SCIPvarGetProbindex(repvar); 852 negated = FALSE; 853 } 854 } 855 assert(probindex >= 0); 856 assert(coveringvars[probindex] != NULL); 857 858 /* add covering variable for unfixed original variable */ 859 if( negated ) 860 { 861 SCIP_CALL( SCIPgetNegatedVar(coveringscip, coveringvars[probindex], &coveringconsvars[ntofix]) ); 862 } 863 else 864 coveringconsvars[ntofix] = coveringvars[probindex]; 865 coveringconsvals[ntofix] = 1.0; 866 ntofix++; 867 } 868 869 /* if less than two variables are unfixed, the entire constraint can be linearized anyway */ 870 if( ntofix >= 2 ) 871 { 872 assert(ntofix <= nbdvars); 873 874 /* create covering constraint */ 875 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering", SCIPconsGetName(bdcons)); 876 SCIP_CALL( SCIPcreateConsLinear(coveringscip, &coveringcons, name, ntofix, coveringconsvars, coveringconsvals, 877 (SCIP_Real)(ntofix - 1), SCIPinfinity(coveringscip), 878 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) ); 879 880 if( coveringcons == NULL ) 881 { 882 SCIPdebugMsg(scip, "failed to create linear constraint <%s>\n", name); 883 SCIPfreeBufferArray(coveringscip, &coveringconsvals); 884 SCIPfreeBufferArray(coveringscip, &coveringconsvars); 885 goto TERMINATE; 886 } 887 888 /* add and release covering constraint */ 889 SCIP_CALL( SCIPaddCons(coveringscip, coveringcons) ); 890 SCIP_CALL( SCIPreleaseCons(coveringscip, &coveringcons) ); 891 892 /* update counters */ 893 for( v = ntofix-1; v >= 0; v-- ) 894 if( SCIPvarIsNegated(coveringconsvars[v]) ) 895 incCounters(termcounter, conscounter, consmarker, SCIPvarGetProbindex(SCIPvarGetNegationVar(coveringconsvars[v]))); 896 else 897 incCounters(termcounter, conscounter, consmarker, SCIPvarGetProbindex(coveringconsvars[v])); 898 } 899 900 /* free memory for covering constraint */ 901 SCIPfreeBufferArray(coveringscip, &coveringconsvals); 902 SCIPfreeBufferArray(coveringscip, &coveringconsvars); 903 } 904 } 905 906 /* go through all indicator constraints in the original problem; fix the binary variable */ 907 conshdlr = SCIPfindConshdlr(scip, "indicator"); 908 if( conshdlr != NULL && coverind ) 909 { 910 int c; 911 912 for( c = SCIPconshdlrGetNActiveConss(conshdlr)-1; c >= 0; c-- ) 913 { 914 SCIP_CONS* indcons; 915 SCIP_VAR* binvar; 916 SCIP_VAR* coveringvar; 917 918 /* get constraint and variables */ 919 indcons = SCIPconshdlrGetConss(conshdlr)[c]; 920 assert(indcons != NULL); 921 binvar = SCIPgetBinaryVarIndicator(indcons); 922 assert(binvar != NULL); 923 924 /* indicator constraints are not passed to the NLP, hence nothing to store in the hash map */ 925 926 /* if variable is fixed, nothing to do */ 927 if( varIsFixed(scip, binvar, globalbounds ? SCIPvarGetLbGlobal(binvar) : SCIPvarGetLbLocal(binvar), globalbounds) ) 928 { 929 continue; 930 } 931 932 /* if constraints with inactive variables are present, we have to find the corresponding active variable */ 933 probindex = SCIPvarGetProbindex(binvar); 934 if( probindex == -1 ) 935 { 936 SCIP_VAR* repvar; 937 SCIP_Bool negated; 938 939 /* get binary representative of variable */ 940 negated = FALSE; 941 SCIP_CALL( SCIPgetBinvarRepresentative(scip, binvar, &repvar, &negated) ); 942 assert(repvar != NULL); 943 assert(SCIPvarGetStatus(repvar) != SCIP_VARSTATUS_FIXED); 944 945 if( SCIPvarGetStatus(repvar) == SCIP_VARSTATUS_MULTAGGR ) 946 { 947 SCIPdebugMsg(scip, "strange: multiaggregated variable found <%s>\n", SCIPvarGetName(binvar)); 948 SCIPdebugMsg(scip, "inactive variables detected in constraint <%s>\n", SCIPconsGetName(indcons)); 949 goto TERMINATE; 950 } 951 952 /* check for negation */ 953 if( SCIPvarIsNegated(repvar) ) 954 probindex = SCIPvarGetProbindex(SCIPvarGetNegationVar(repvar)); 955 else 956 { 957 assert(SCIPvarIsActive(repvar)); 958 probindex = SCIPvarGetProbindex(repvar); 959 } 960 } 961 assert(probindex >= 0); 962 assert(coveringvars[probindex] != NULL); 963 964 /* get covering variable for unfixed binary variable in indicator constraint */ 965 coveringvar = coveringvars[probindex]; 966 967 /* require covering variable to be fixed such that indicator is linearized */ 968 SCIP_CALL( SCIPchgVarLb(coveringscip, coveringvar, 1.0) ); 969 970 /* update counters */ 971 BMSclearMemoryArray(consmarker, nvars); 972 incCounters(termcounter, conscounter, consmarker, probindex); 973 } 974 } 975 976 /* go through all nonlinear constraints in the original problem 977 * @todo: some expr constraints might be SOC and these only need to have all but one variable fixed in order to be 978 * linear; however, by just looking at the nlrow representation of a soc constraint, processNlRow doesn't realize 979 * this. if more specific information is accessible from expr constrains, then this can be improved 980 */ 981 conshdlr = SCIPfindConshdlr(scip, "nonlinear"); 982 if( conshdlr != NULL && covernl ) 983 { 984 int c; 985 986 for( c = SCIPconshdlrGetNActiveConss(conshdlr)-1; c >= 0; c-- ) 987 { 988 SCIP_CONS* exprcons; 989 SCIP_NLROW* nlrow; 990 991 /* get constraint */ 992 exprcons = SCIPconshdlrGetConss(conshdlr)[c]; 993 assert(exprcons != NULL); 994 995 /* get nlrow representation and store it in hash map */ 996 SCIP_CALL( SCIPgetNlRowNonlinear(scip, exprcons, &nlrow) ); 997 assert(nlrow != NULL); 998 999 /* process nlrow */ 1000 *success = FALSE; 1001 SCIP_CALL( processNlRow(scip, nlrow, coveringscip, nvars, coveringvars, 1002 termcounter, conscounter, consmarker, globalbounds, onlyconvexify, success) ); 1003 1004 if( *success == FALSE ) 1005 goto TERMINATE; 1006 } 1007 1008 *success = FALSE; 1009 } 1010 1011 /* set objective function of covering problem */ 1012 switch( coveringobj ) 1013 { 1014 case 'c': /* number of influenced nonlinear constraints */ 1015 for( i = nvars-1; i >= 0; i-- ) 1016 { 1017 if( coveringvars[i] == NULL ) 1018 continue; 1019 SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i], (SCIP_Real) conscounter[i]) ); 1020 } 1021 break; 1022 case 'd': /* domain size */ 1023 for( i = nvars-1; i >= 0; i-- ) 1024 { 1025 if( coveringvars[i] == NULL ) 1026 continue; 1027 SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i], 1028 (globalbounds ? SCIPvarGetUbGlobal(vars[i]) - SCIPvarGetLbGlobal(vars[i]) : SCIPvarGetUbLocal(vars[i]) - SCIPvarGetLbLocal(vars[i]))) ); 1029 } 1030 break; 1031 case 'l': /* number of locks */ 1032 for( i = nvars-1; i >= 0; i-- ) 1033 { 1034 if( coveringvars[i] == NULL ) 1035 continue; 1036 nlocksup = SCIPvarGetNLocksUpType(vars[i], SCIP_LOCKTYPE_MODEL); 1037 nlocksdown = SCIPvarGetNLocksDownType(vars[i], SCIP_LOCKTYPE_MODEL); 1038 SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i], (SCIP_Real) (nlocksup+nlocksdown+1)) ); 1039 } 1040 break; 1041 case 'm': /* min(up locks, down locks)+1 */ 1042 for( i = nvars-1; i >= 0; i-- ) 1043 { 1044 if( coveringvars[i] == NULL ) 1045 continue; 1046 nlocksup = SCIPvarGetNLocksUpType(vars[i], SCIP_LOCKTYPE_MODEL); 1047 nlocksdown = SCIPvarGetNLocksDownType(vars[i], SCIP_LOCKTYPE_MODEL); 1048 SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i], (SCIP_Real) (MIN(nlocksup, nlocksdown)+1)) ); 1049 } 1050 break; 1051 case 't': /* number of influenced nonlinear terms */ 1052 for( i = nvars-1; i >= 0; i-- ) 1053 { 1054 if( coveringvars[i] == NULL ) 1055 continue; 1056 SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i], (SCIP_Real) termcounter[i]) ); 1057 } 1058 break; 1059 case 'u': /* unit penalties */ 1060 for( i = nvars-1; i >= 0; i-- ) 1061 { 1062 if( coveringvars[i] == NULL ) 1063 continue; 1064 SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i], 1.0) ); 1065 } 1066 break; 1067 default: 1068 SCIPerrorMessage("invalid choice <%c> for covering objective\n", coveringobj); 1069 goto TERMINATE; 1070 } 1071 1072 /* covering problem successfully set up */ 1073 *success = TRUE; 1074 1075 TERMINATE: 1076 SCIPstatistic( 1077 { 1078 int nnonzs; 1079 nnonzs = 0; 1080 for( i = 0; i < nvars; ++i) 1081 nnonzs += termcounter[i]; 1082 SCIPstatisticPrintf("UCstats nnz/var: %9.6f\n", nnonzs/(SCIP_Real)nvars); 1083 nnonzs = 0; 1084 for( i = 0; i < nvars; ++i) 1085 if( conscounter[i] > 0 ) 1086 nnonzs++; 1087 SCIPstatisticPrintf("UCstats nlvars: %6d\n", nnonzs); 1088 } 1089 ); 1090 1091 /* free counter arrays for weighted objectives */ 1092 SCIPfreeBufferArray(scip, &termcounter); 1093 SCIPfreeBufferArray(scip, &conscounter); 1094 SCIPfreeBufferArray(scip, &consmarker); 1095 1096 return SCIP_OKAY; 1097 } 1098 1099 1100 /** adds a constraint to the covering problem to forbid the given cover */ 1101 static 1102 SCIP_RETCODE forbidCover( 1103 SCIP* scip, /**< SCIP data structure of the covering problem */ 1104 int nvars, /**< number of variables */ 1105 SCIP_VAR** vars, /**< variable array */ 1106 int coversize, /**< size of the cover */ 1107 int* cover, /**< problem indices of the variables in the cover */ 1108 int diversification, /**< how many unfixed variables have to change their value? */ 1109 SCIP_Bool* success, /**< pointer to store whether the cutoff constraint was created successfully */ 1110 SCIP_Bool* infeas /**< pointer to store whether the cutoff proves (local or global) infeasibility */ 1111 ) 1112 { 1113 SCIP_CONS* cons; 1114 SCIP_VAR** consvars; 1115 1116 char name[SCIP_MAXSTRLEN]; 1117 int nconsvars; 1118 int i; 1119 1120 assert(scip != NULL); 1121 assert(vars != NULL); 1122 assert(nvars >= 1); 1123 assert(cover != NULL); 1124 assert(coversize >= 1); 1125 assert(coversize <= nvars); 1126 assert(diversification >= 1); 1127 assert(success != NULL); 1128 assert(infeas != NULL); 1129 1130 *success = FALSE; 1131 *infeas = FALSE; 1132 1133 /* allocate memory for constraint variables */ 1134 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, coversize) ); 1135 nconsvars = 0; 1136 cons = NULL; 1137 1138 /* create constraint name */ 1139 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "forbid_cover_assignment"); 1140 1141 /* if all variables in the cover are binary and we require only one variable to change its value, then we create a 1142 * set covering constraint 1143 */ 1144 if( diversification == 1 ) 1145 { 1146 /* build up constraint */ 1147 for( i = coversize-1; i >= 0; i-- ) 1148 { 1149 if( vars[cover[i]] != NULL && !SCIPisFeasGE(scip, SCIPvarGetLbLocal(vars[cover[i]]), 1.0) ) 1150 { 1151 SCIP_CALL( SCIPgetNegatedVar(scip, vars[cover[i]], &consvars[nconsvars]) ); 1152 nconsvars++; 1153 } 1154 } 1155 1156 /* if all covering variables are fixed to one, the constraint cannot be satisfied */ 1157 if( nconsvars == 0 ) 1158 { 1159 *infeas = TRUE; 1160 } 1161 else 1162 { 1163 /* create constraint */ 1164 SCIP_CALL( SCIPcreateConsSetcover(scip, &cons, name, nconsvars, consvars, 1165 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) ); 1166 } 1167 } 1168 /* if all variables in the cover are binary and we require more variables to change their value, then we create a 1169 * linear constraint 1170 */ 1171 else 1172 { 1173 SCIP_Real* consvals; 1174 SCIP_Real rhs; 1175 1176 /* build up constraint */ 1177 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, coversize) ); 1178 for( i = coversize-1; i >= 0; i-- ) 1179 { 1180 if( vars[cover[i]] != NULL && !SCIPisFeasGE(scip, SCIPvarGetLbLocal(vars[cover[i]]), 1.0) ) 1181 { 1182 consvars[nconsvars] = vars[cover[i]]; 1183 consvals[nconsvars] = 1.0; 1184 nconsvars++; 1185 } 1186 } 1187 rhs = (SCIP_Real) (nconsvars-diversification); 1188 1189 /* if too many covering variables are fixed to 1, the constraint cannot be satisfied */ 1190 if( rhs < 0 ) 1191 { 1192 *infeas = TRUE; 1193 } 1194 else 1195 { 1196 /* create constraint */ 1197 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name, 1198 nconsvars, consvars, consvals, -SCIPinfinity(scip), rhs, 1199 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) ); 1200 } 1201 1202 /* free memory */ 1203 SCIPfreeBufferArray(scip, &consvals); 1204 } 1205 1206 /* free memory */ 1207 SCIPfreeBufferArray(scip, &consvars); 1208 1209 /* if proven infeasible, we do not even add the constraint; otherwise we add and release the constraint if created 1210 * successfully 1211 */ 1212 if( !(*infeas) && cons != NULL ) 1213 { 1214 SCIP_CALL( SCIPaddCons(scip, cons) ); 1215 SCIP_CALL( SCIPreleaseCons(scip, &cons) ); 1216 *success = TRUE; 1217 } 1218 1219 return SCIP_OKAY; 1220 } 1221 1222 1223 /** adds a set covering or bound disjunction constraint to the original problem */ 1224 static 1225 SCIP_RETCODE createConflict( 1226 SCIP* scip, /**< SCIP data structure */ 1227 int bdlen, /**< length of bound disjunction */ 1228 SCIP_VAR** bdvars, /**< array of variables in bound disjunction */ 1229 SCIP_BOUNDTYPE* bdtypes, /**< array of bound types in bound disjunction */ 1230 SCIP_Real* bdbounds, /**< array of bounds in bound disjunction */ 1231 SCIP_Bool local, /**< is constraint valid only locally? */ 1232 SCIP_Bool dynamic, /**< is constraint subject to aging? */ 1233 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? */ 1234 SCIP_Bool* success /**< pointer to store whether the cutoff constraint was created successfully */ 1235 ) 1236 { 1237 SCIP_CONS* cons; 1238 SCIP_VAR** consvars; 1239 SCIP_Bool isbinary; 1240 char name[SCIP_MAXSTRLEN]; 1241 int i; 1242 1243 assert(scip != NULL); 1244 assert(bdlen >= 1); 1245 assert(bdvars != NULL); 1246 assert(bdtypes != NULL); 1247 assert(bdbounds != NULL); 1248 assert(success != NULL); 1249 1250 /* initialize */ 1251 *success = FALSE; 1252 cons = NULL; 1253 consvars = NULL; 1254 1255 /* create constraint name */ 1256 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "undercover_cutoff"); 1257 1258 /* check if all variables in the cover are binary */ 1259 isbinary = TRUE; 1260 for( i = bdlen-1; i >= 0 && isbinary; i-- ) 1261 { 1262 isbinary = SCIPvarIsBinary(bdvars[i]); 1263 } 1264 1265 /* if all variables in the cover are binary, then we create a logicor constraint */ 1266 if( isbinary ) 1267 { 1268 /* allocate memory for constraint variables */ 1269 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, bdlen) ); 1270 1271 /* build up constraint */ 1272 for( i = bdlen-1; i >= 0; i-- ) 1273 { 1274 assert(bdtypes[i] == SCIP_BOUNDTYPE_LOWER || SCIPisFeasZero(scip, bdbounds[i])); 1275 assert(bdtypes[i] == SCIP_BOUNDTYPE_UPPER || SCIPisFeasEQ(scip, bdbounds[i], 1.0)); 1276 1277 if( bdtypes[i] == SCIP_BOUNDTYPE_LOWER ) 1278 { 1279 consvars[i] = bdvars[i]; 1280 } 1281 else 1282 { 1283 assert(bdtypes[i] == SCIP_BOUNDTYPE_UPPER); 1284 SCIP_CALL( SCIPgetNegatedVar(scip, bdvars[i], &consvars[i]) ); 1285 } 1286 } 1287 1288 /* create conflict constraint */ 1289 SCIP_CALL( SCIPcreateConsLogicor(scip, &cons, name, bdlen, consvars, 1290 FALSE, TRUE, FALSE, FALSE, TRUE, local, FALSE, dynamic, removable, FALSE) ); 1291 } 1292 /* otherwise we create a bound disjunction constraint as given */ 1293 else 1294 { 1295 /* create conflict constraint */ 1296 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &cons, name, bdlen, bdvars, bdtypes, bdbounds, 1297 FALSE, TRUE, FALSE, FALSE, TRUE, local, FALSE, dynamic, removable, FALSE) ); 1298 } 1299 1300 /* add and release constraint if created successfully */ 1301 if( cons != NULL ) 1302 { 1303 if( local ) 1304 { 1305 SCIP_CALL( SCIPaddConsLocal(scip, cons, NULL) ); 1306 } 1307 else 1308 { 1309 SCIP_CALL( SCIPaddCons(scip, cons) ); 1310 } 1311 1312 SCIP_CALL( SCIPreleaseCons(scip, &cons) ); 1313 *success = TRUE; 1314 } 1315 1316 /* free memory */ 1317 SCIPfreeBufferArrayNull(scip, &consvars); 1318 1319 return SCIP_OKAY; 1320 } 1321 1322 1323 /** solve covering problem */ 1324 static 1325 SCIP_RETCODE solveCoveringProblem( 1326 SCIP* coveringscip, /**< SCIP data structure for the covering problem */ 1327 int ncoveringvars, /**< number of the covering problem's variables */ 1328 SCIP_VAR** coveringvars, /**< array of the covering problem's variables */ 1329 int* coversize, /**< size of the computed cover */ 1330 int* cover, /**< array to store indices of the variables in the computed cover 1331 * (should be ready to hold ncoveringvars entries) */ 1332 SCIP_Real timelimit, /**< time limit */ 1333 SCIP_Real memorylimit, /**< memory limit */ 1334 SCIP_Real objlimit, /**< upper bound on the cover size */ 1335 SCIP_Bool* success /**< feasible cover found? */ 1336 ) 1337 { 1338 SCIP_Real totalpenalty; 1339 SCIP_RETCODE retcode; 1340 int i; 1341 1342 assert(coveringscip != NULL); 1343 assert(coveringvars != NULL); 1344 assert(cover != NULL); 1345 assert(coversize != NULL); 1346 assert(timelimit > 0.0); 1347 assert(memorylimit > 0.0); 1348 assert(success != NULL); 1349 1350 *success = FALSE; 1351 1352 /* forbid call of heuristics and separators solving sub-CIPs */ 1353 SCIP_CALL( SCIPsetSubscipsOff(coveringscip, TRUE) ); 1354 1355 /* set presolving and separation to fast */ 1356 SCIP_CALL( SCIPsetSeparating(coveringscip, SCIP_PARAMSETTING_FAST, TRUE) ); 1357 SCIP_CALL( SCIPsetPresolving(coveringscip, SCIP_PARAMSETTING_FAST, TRUE) ); 1358 1359 /* use inference branching */ 1360 if( SCIPfindBranchrule(coveringscip, "inference") != NULL && !SCIPisParamFixed(coveringscip, "branching/inference/priority") ) 1361 { 1362 SCIP_CALL( SCIPsetIntParam(coveringscip, "branching/inference/priority", INT_MAX/4) ); 1363 } 1364 1365 /* only solve root */ 1366 SCIP_CALL( SCIPsetLongintParam(coveringscip, "limits/nodes", 1LL) ); 1367 1368 SCIPdebugMsg(coveringscip, "timelimit = %g, memlimit = %g\n", timelimit, memorylimit); 1369 1370 /* set time, memory, and objective limit */ 1371 SCIP_CALL( SCIPsetRealParam(coveringscip, "limits/time", timelimit) ); 1372 SCIP_CALL( SCIPsetRealParam(coveringscip, "limits/memory", memorylimit) ); 1373 SCIP_CALL( SCIPsetObjlimit(coveringscip, objlimit) ); 1374 1375 /* do not abort on CTRL-C */ 1376 SCIP_CALL( SCIPsetBoolParam(coveringscip, "misc/catchctrlc", FALSE) ); 1377 1378 /* disable output to console in optimized mode, enable in SCIP's debug mode */ 1379 #ifdef SCIP_DEBUG 1380 SCIP_CALL( SCIPsetIntParam(coveringscip, "display/verblevel", 5) ); 1381 SCIP_CALL( SCIPsetIntParam(coveringscip, "display/freq", 100000) ); 1382 #else 1383 SCIP_CALL( SCIPsetIntParam(coveringscip, "display/verblevel", 0) ); 1384 #endif 1385 1386 /* solve covering problem */ 1387 retcode = SCIPsolve(coveringscip); 1388 1389 /* errors in solving the covering problem should not kill the overall solving process; 1390 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. 1391 */ 1392 if( retcode != SCIP_OKAY ) 1393 { 1394 #ifndef NDEBUG 1395 SCIP_CALL( retcode ); 1396 #endif 1397 SCIPwarningMessage(coveringscip, "Error while solving covering problem in Undercover heuristic; sub-SCIP terminated with code <%d>\n",retcode); 1398 return SCIP_OKAY; 1399 } 1400 1401 /* check, whether a feasible cover was found */ 1402 if( SCIPgetNSols(coveringscip) == 0 ) 1403 return SCIP_OKAY; 1404 1405 /* store solution */ 1406 *coversize = 0; 1407 totalpenalty = 0.0; 1408 for( i = 0; i < ncoveringvars; i++ ) 1409 { 1410 if( coveringvars[i] == NULL ) 1411 continue; 1412 1413 if( SCIPgetSolVal(coveringscip, SCIPgetBestSol(coveringscip), coveringvars[i]) > 0.5 ) 1414 { 1415 cover[*coversize] = i; 1416 (*coversize)++; 1417 } 1418 totalpenalty += SCIPvarGetObj(coveringvars[i]); 1419 } 1420 1421 /* print solution if we are in SCIP's debug mode */ 1422 assert(SCIPgetBestSol(coveringscip) != NULL); 1423 SCIPdebugMsg(coveringscip, "found a feasible cover: %d/%d variables fixed, normalized penalty=%g\n\n", 1424 *coversize, SCIPgetNOrigVars(coveringscip), SCIPgetSolOrigObj(coveringscip, SCIPgetBestSol(coveringscip))/(totalpenalty+SCIPsumepsilon(coveringscip))); 1425 SCIPdebug( SCIP_CALL( SCIPprintSol(coveringscip, SCIPgetBestSol(coveringscip), NULL, FALSE) ) ); 1426 SCIPdebugMsg(coveringscip, "\r \n"); 1427 1428 *success = TRUE; 1429 1430 return SCIP_OKAY; 1431 } 1432 1433 1434 /** computes fixing order and returns whether order has really been changed */ 1435 static 1436 SCIP_RETCODE computeFixingOrder( 1437 SCIP* scip, /**< original SCIP data structure */ 1438 SCIP_HEURDATA* heurdata, /**< heuristic data */ 1439 int nvars, /**< number of variables in the original problem */ 1440 SCIP_VAR** vars, /**< variables in the original problem */ 1441 int coversize, /**< size of the cover */ 1442 int* cover, /**< problem indices of the variables in the cover */ 1443 int lastfailed, /**< position in cover array of the variable the fixing of which yielded 1444 * infeasibility in last dive (or >= coversize, in which case *success 1445 * is always TRUE) */ 1446 SCIP_Bool* success /**< has order really been changed? */ 1447 ) 1448 { 1449 SCIP_Real* scores; 1450 SCIP_Real bestscore; 1451 SCIP_Bool sortdown; 1452 int i; 1453 1454 assert(scip != NULL); 1455 assert(heurdata != NULL); 1456 assert(nvars >= 1); 1457 assert(vars != NULL); 1458 assert(coversize >= 1); 1459 assert(cover != NULL); 1460 assert(lastfailed >= 0); 1461 1462 *success = FALSE; 1463 1464 /* if fixing the first variable had failed, do not try with another order */ 1465 if( lastfailed == 0 ) 1466 return SCIP_OKAY; 1467 1468 /* allocate buffer array for score values */ 1469 SCIP_CALL( SCIPallocBufferArray(scip, &scores, coversize) ); 1470 1471 /* initialize best score to infinite value */ 1472 sortdown = (heurdata->fixingorder == 'c' || heurdata->fixingorder == 'v' ); 1473 bestscore = sortdown ? -SCIPinfinity(scip) : +SCIPinfinity(scip); 1474 1475 /* compute score values */ 1476 for( i = coversize-1; i >= 0; i-- ) 1477 { 1478 SCIP_VAR* var; 1479 1480 /* get variable in the cover */ 1481 assert(cover[i] >= 0); 1482 assert(cover[i] < nvars); 1483 var = vars[cover[i]]; 1484 1485 if( heurdata->fixingorder == 'C' || heurdata->fixingorder == 'c' ) 1486 { 1487 /* add a small pertubation value to the score to reduce performance variability */ 1488 scores[i] = heurdata->conflictweight * SCIPgetVarConflictScore(scip, var) 1489 + heurdata->inferenceweight * SCIPgetVarAvgInferenceCutoffScore(scip, var, heurdata->cutoffweight) 1490 + SCIPrandomGetReal(heurdata->randnumgen, 0.0, SCIPepsilon(scip)); 1491 } 1492 else if( heurdata->fixingorder == 'V' || heurdata->fixingorder == 'v' ) 1493 scores[i] = cover[i]; 1494 else 1495 return SCIP_PARAMETERWRONGVAL; 1496 1497 assert(scores[i] >= 0.0); 1498 1499 /* update best score */ 1500 if( sortdown ) 1501 bestscore = MAX(bestscore, scores[i]); 1502 else 1503 bestscore = MIN(bestscore, scores[i]); 1504 } 1505 1506 /* put integers to the front */ 1507 if( heurdata->fixintfirst ) 1508 { 1509 for( i = coversize-1; i >= 0; i-- ) 1510 { 1511 if( SCIPvarIsIntegral(vars[cover[i]]) ) 1512 { 1513 if( sortdown ) 1514 scores[i] += bestscore+1.0; 1515 else 1516 scores[i] = bestscore - 1.0/(scores[i]+1.0); 1517 } 1518 } 1519 } 1520 1521 /* put last failed variable to the front */ 1522 if( lastfailed < coversize ) 1523 { 1524 if( sortdown ) 1525 scores[lastfailed] += bestscore+2.0; 1526 else 1527 scores[lastfailed] = bestscore - 2.0/(scores[lastfailed]+1.0); 1528 i = cover[lastfailed]; 1529 } 1530 1531 /* sort by non-decreasing (negative) score */ 1532 if( sortdown ) 1533 SCIPsortDownRealInt(scores, cover, coversize); 1534 else 1535 SCIPsortRealInt(scores, cover, coversize); 1536 1537 assert(lastfailed >= coversize || cover[0] == i); 1538 1539 /* free buffer memory */ 1540 SCIPfreeBufferArray(scip, &scores); 1541 1542 *success = TRUE; 1543 1544 return SCIP_OKAY; 1545 } 1546 1547 1548 /** gets fixing value */ 1549 static 1550 SCIP_RETCODE getFixingValue( 1551 SCIP* scip, /**< original SCIP data structure */ 1552 SCIP_HEURDATA* heurdata, /**< heuristic data */ 1553 SCIP_VAR* var, /**< variable in the original problem */ 1554 SCIP_Real* val, /**< buffer for returning fixing value */ 1555 char fixalt, /**< source of the fixing value: 'l'p relaxation, 'n'lp relaxation, 'i'ncumbent solution */ 1556 SCIP_Bool* success, /**< could value be retrieved successfully? */ 1557 int bdlen, /**< current length of probing path */ 1558 SCIP_VAR** bdvars, /**< array of variables with bound changes along probing path */ 1559 SCIP_BOUNDTYPE* bdtypes, /**< array of bound types in bound disjunction */ 1560 SCIP_Real* oldbounds /**< array of bounds before fixing */ 1561 ) 1562 { 1563 assert(scip != NULL); 1564 assert(heurdata != NULL); 1565 assert(var != NULL); 1566 assert(val != NULL); 1567 assert(success != NULL); 1568 1569 *success = FALSE; 1570 1571 switch( fixalt ) 1572 { 1573 case 'l': 1574 /* get the last LP solution value */ 1575 *val = SCIPvarGetLPSol(var); 1576 *success = TRUE; 1577 break; 1578 case 'n': 1579 /* only call this function if NLP relaxation is available */ 1580 assert(SCIPisNLPConstructed(scip)); 1581 1582 /* the solution values are already available */ 1583 if( heurdata->nlpsolved ) 1584 { 1585 assert(!heurdata->nlpfailed); 1586 1587 /* retrieve NLP solution value */ 1588 *val = SCIPvarGetNLPSol(var); 1589 *success = TRUE; 1590 } 1591 /* solve NLP relaxation unless it has not failed too often before */ 1592 else if( !heurdata->nlpfailed ) 1593 { /*lint --e{850}*/ 1594 SCIP_NLPSOLSTAT stat; 1595 int i; 1596 1597 /* restore bounds at start of probing, since otherwise, if in backtrack mode, NLP solver becomes most likely 1598 * locally infeasible 1599 */ 1600 SCIP_CALL( SCIPstartDiveNLP(scip) ); 1601 1602 for( i = bdlen-1; i >= 0; i-- ) 1603 { 1604 SCIP_VAR* relaxvar; 1605 SCIP_Real lb; 1606 SCIP_Real ub; 1607 1608 relaxvar = bdvars[i]; 1609 1610 /* both bounds were tightened */ 1611 if( i > 0 && bdvars[i-1] == relaxvar ) 1612 { 1613 assert(bdtypes[i] != bdtypes[i-1]); 1614 1615 lb = bdtypes[i] == SCIP_BOUNDTYPE_UPPER ? oldbounds[i] : oldbounds[i-1]; 1616 ub = bdtypes[i] == SCIP_BOUNDTYPE_UPPER ? oldbounds[i-1] : oldbounds[i]; 1617 i--; 1618 } 1619 /* lower bound was tightened */ 1620 else if( bdtypes[i] == SCIP_BOUNDTYPE_UPPER ) 1621 { 1622 lb = oldbounds[i]; 1623 ub = SCIPvarGetUbLocal(relaxvar); 1624 } 1625 /* upper bound was tightened */ 1626 else 1627 { 1628 lb = SCIPvarGetLbLocal(relaxvar); 1629 ub = oldbounds[i]; 1630 } 1631 1632 assert(SCIPisLE(scip, lb, SCIPvarGetLbLocal(relaxvar))); 1633 assert(SCIPisGE(scip, ub, SCIPvarGetUbLocal(relaxvar))); 1634 1635 /* relax bounds */ 1636 SCIP_CALL( SCIPchgVarBoundsDiveNLP(scip, relaxvar, lb, ub) ); 1637 } 1638 1639 /* set starting point to lp solution */ 1640 SCIP_CALL( SCIPsetNLPInitialGuessSol(scip, NULL) ); 1641 1642 /* solve NLP relaxation */ 1643 SCIP_CALL( SCIPsolveNLP(scip) ); /*lint !e666*/ 1644 stat = SCIPgetNLPSolstat(scip); 1645 *success = stat == SCIP_NLPSOLSTAT_GLOBOPT || stat == SCIP_NLPSOLSTAT_LOCOPT || stat == SCIP_NLPSOLSTAT_FEASIBLE; 1646 1647 SCIPdebugMsg(scip, "solving NLP relaxation to obtain fixing values %s (stat=%d)\n", *success ? "successful" : "failed", stat); 1648 1649 if( *success ) 1650 { 1651 /* solving succeeded */ 1652 heurdata->nnlpfails = 0; 1653 heurdata->nlpsolved = TRUE; 1654 1655 /* retrieve NLP solution value */ 1656 *val = SCIPvarGetNLPSol(var); 1657 } 1658 else 1659 { 1660 /* solving failed */ 1661 heurdata->nnlpfails++; 1662 heurdata->nlpfailed = TRUE; 1663 heurdata->nlpsolved = FALSE; 1664 1665 SCIPdebugMsg(scip, "solving NLP relaxation failed (%d time%s%s)\n", 1666 heurdata->nnlpfails, heurdata->nnlpfails > 1 ? "s" : "", heurdata->nnlpfails >= MAXNLPFAILS ? ", will not be called again" : ""); 1667 } 1668 } 1669 break; 1670 case 'i': 1671 /* only call this function if a feasible solution is available */ 1672 assert(SCIPgetBestSol(scip) != NULL); 1673 1674 /* get value in the incumbent solution */ 1675 *val = SCIPgetSolVal(scip, SCIPgetBestSol(scip), var); 1676 *success = TRUE; 1677 break; 1678 default: 1679 break; 1680 } 1681 1682 /* due to propagation (during probing) it might happen that the LP and NLP solution value of var might be outside of 1683 * its bounds 1684 */ 1685 *val = MAX(*val, SCIPvarGetLbLocal(var)); /*lint !e666*/ 1686 *val = MIN(*val, SCIPvarGetUbLocal(var)); /*lint !e666*/ 1687 1688 return SCIP_OKAY; 1689 } 1690 1691 1692 /** calculates up to four alternative values for backtracking, if fixing the variable failed. 1693 * The alternatives are the two bounds of the variable, and the averages of the bounds and the fixing value. 1694 * For infinite bounds, fixval +/- abs(fixval) will be used instead. 1695 */ 1696 static 1697 void calculateAlternatives( 1698 SCIP* scip, /**< original SCIP data structure */ 1699 SCIP_VAR* var, /**< variable to calculate alternatives for */ 1700 SCIP_Real fixval, /**< reference fixing value */ 1701 int* nalternatives, /**< number of fixing values computed */ 1702 SCIP_Real* alternatives /**< array to store the alternative fixing values */ 1703 ) 1704 { 1705 SCIP_Real lb; 1706 SCIP_Real ub; 1707 1708 /* for binary variables, there is only two possible fixing values */ 1709 if( SCIPvarIsBinary(var) ) 1710 { 1711 if( SCIPisFeasEQ(scip, fixval, 0.0) || SCIPisFeasEQ(scip, fixval, 1.0) ) 1712 { 1713 alternatives[0] = 1.0 - fixval; 1714 *nalternatives = 1; 1715 } 1716 else 1717 { 1718 alternatives[0] = 0.0; 1719 alternatives[1] = 1.0; 1720 *nalternatives = 2; 1721 } 1722 return; 1723 } 1724 1725 /* get bounds */ 1726 lb = SCIPvarGetLbLocal(var); 1727 ub = SCIPvarGetUbLocal(var); 1728 1729 /* if lower bound is infinite, use x'-|x'|; if x' is zero, use -1.0 instead */ 1730 if( SCIPisInfinity(scip, -lb) ) 1731 lb = SCIPisFeasZero(scip, fixval) ? -1.0 : fixval - ABS(fixval); 1732 1733 /* if upper bound is infinite, use x'+|x'|; if x' is zero, use 1.0 instead */ 1734 if( SCIPisInfinity(scip, ub) ) 1735 ub = SCIPisFeasZero(scip, fixval) ? 1.0 : fixval + ABS(fixval); 1736 1737 assert(!SCIPisEQ(scip, lb, ub)); 1738 1739 /* collect alternatives */ 1740 *nalternatives = 0; 1741 1742 /* use lower bound if not equal to x' */ 1743 if( !SCIPisFeasEQ(scip, lb, fixval) ) 1744 { 1745 alternatives[*nalternatives] = lb; 1746 (*nalternatives)++; 1747 } 1748 1749 /* use upper bound if not equal to x' */ 1750 if( !SCIPisFeasEQ(scip, ub, fixval) ) 1751 { 1752 alternatives[*nalternatives] = ub; 1753 (*nalternatives)++; 1754 } 1755 1756 /* use the average of x' and lower bound as alternative value, if this is not equal to any of the other values */ 1757 if( !SCIPisFeasEQ(scip, lb, fixval) && (!SCIPvarIsIntegral(var) || !SCIPisFeasEQ(scip, lb, fixval-1)) ) 1758 { 1759 alternatives[*nalternatives] = (lb+fixval)/2.0; 1760 (*nalternatives)++; 1761 } 1762 1763 /* use the average of x' and upper bound as alternative value, if this is not equal to any of the other values */ 1764 if( !SCIPisFeasEQ(scip, ub, fixval) && (!SCIPvarIsIntegral(var) || !SCIPisFeasEQ(scip, ub, fixval+1)) ) 1765 { 1766 alternatives[*nalternatives] = (ub+fixval)/2.0; 1767 (*nalternatives)++; 1768 } 1769 1770 assert(*nalternatives <= 4); 1771 1772 return; 1773 } 1774 1775 1776 /** rounds the given fixing value */ 1777 static 1778 SCIP_RETCODE roundFixingValue( 1779 SCIP* scip, /**< original SCIP data structure */ 1780 SCIP_Real* val, /**< fixing value to be rounded */ 1781 SCIP_VAR* var, /**< corresponding variable */ 1782 SCIP_Bool locksrounding /**< shall we round according to locks? (otherwise to nearest integer) */ 1783 ) 1784 { 1785 SCIP_Real x; 1786 1787 x = *val; 1788 1789 /* if integral within feasibility tolerance, only shift to nearest integer */ 1790 if( SCIPisFeasIntegral(scip, x) ) 1791 x = SCIPfeasFrac(scip, x) < 0.5 ? SCIPfeasFloor(scip, x) : SCIPfeasCeil(scip, x); 1792 1793 /* round in the direction of least locks with fractionality as tie breaker */ 1794 else if( locksrounding ) 1795 { 1796 if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) < SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) ) 1797 x = SCIPfeasFloor(scip, x); 1798 else if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) > SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) ) 1799 x = SCIPfeasCeil(scip, x); 1800 else 1801 x = SCIPfeasFrac(scip, x) < 0.5 ? SCIPfeasFloor(scip, x) : SCIPfeasCeil(scip, x); 1802 } 1803 /* round in the direction of least fractionality with locks as tie breaker */ 1804 else 1805 { 1806 if( SCIPfeasFrac(scip, x) < 0.5) 1807 x = SCIPfeasFloor(scip, x); 1808 else if( SCIPfeasFrac(scip, x) > 0.5 ) 1809 x = SCIPfeasCeil(scip, x); 1810 else 1811 x = SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) < SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) ? SCIPfeasFloor(scip, x) : SCIPfeasCeil(scip, x); 1812 } 1813 1814 /* return rounded fixing value */ 1815 *val = x; 1816 1817 return SCIP_OKAY; 1818 } 1819 1820 /** solve subproblem and pass best feasible solution to original SCIP instance */ 1821 static 1822 SCIP_RETCODE solveSubproblem( 1823 SCIP* scip, /**< SCIP data structure of the original problem */ 1824 SCIP_HEUR* heur, /**< heuristic data structure */ 1825 int coversize, /**< size of the cover */ 1826 int* cover, /**< problem indices of the variables in the cover */ 1827 SCIP_Real* fixedvals, /**< fixing values for the variables in the cover */ 1828 SCIP_Real timelimit, /**< time limit */ 1829 SCIP_Real memorylimit, /**< memory limit */ 1830 SCIP_Longint nodelimit, /**< node limit */ 1831 SCIP_Longint nstallnodes, /**< number of stalling nodes for the subproblem */ 1832 SCIP_Bool* validsolved, /**< was problem constructed from a valid copy and solved (proven optimal or infeasible)? */ 1833 SCIP_SOL** sol, /**< best solution found in subproblem (if feasible); *sol must be NULL, solution will be created */ 1834 SCIP_Longint* nusednodes /**< number of nodes used for solving the subproblem */ 1835 ) 1836 { 1837 SCIP_HEURDATA* heurdata; 1838 SCIP* subscip; 1839 SCIP_VAR** subvars; 1840 SCIP_VAR** vars; 1841 SCIP_HASHMAP* varmap; 1842 SCIP_VAR** fixedvars; 1843 int nfixedvars; 1844 1845 SCIP_RETCODE retcode; 1846 1847 int nvars; 1848 int i; 1849 1850 assert(scip != NULL); 1851 assert(heur != NULL); 1852 assert(cover != NULL); 1853 assert(fixedvals != NULL); 1854 assert(coversize >= 1); 1855 assert(timelimit > 0.0); 1856 assert(memorylimit > 0.0); 1857 assert(nodelimit >= 1); 1858 assert(nstallnodes >= 1); 1859 assert(validsolved != NULL); 1860 assert(sol != NULL); 1861 assert(*sol == NULL); 1862 assert(nusednodes != NULL); 1863 1864 *validsolved = FALSE; 1865 *nusednodes = 0; 1866 1867 /* get heuristic data */ 1868 heurdata = SCIPheurGetData(heur); 1869 assert(heurdata != NULL); 1870 1871 /* get required data of the original problem */ 1872 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 1873 1874 SCIP_CALL( SCIPallocBufferArray(scip, &fixedvars, coversize) ); 1875 nfixedvars = coversize; 1876 /* fix subproblem variables in the cover */ 1877 SCIPdebugMsg(scip, "fixing variables\n"); 1878 for( i = coversize-1; i >= 0; i-- ) 1879 { 1880 assert(cover[i] >= 0); 1881 assert(cover[i] < nvars); 1882 1883 fixedvars[i] = vars[cover[i]]; 1884 } 1885 1886 /* create subproblem */ 1887 SCIP_CALL( SCIPcreate(&subscip) ); 1888 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) ); 1889 1890 /* create the variable mapping hash map */ 1891 SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(subscip), nvars) ); 1892 1893 /* copy original problem to subproblem; do not copy pricers */ 1894 SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmap, NULL, "undercoversub", fixedvars, fixedvals, nfixedvars, 1895 heurdata->globalbounds, FALSE, FALSE, TRUE, validsolved) ); 1896 1897 if( heurdata->copycuts ) 1898 { 1899 /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */ 1900 SCIP_CALL( SCIPcopyCuts(scip, subscip, varmap, NULL, heurdata->globalbounds, NULL) ); 1901 } 1902 1903 SCIPdebugMsg(scip, "problem copied, copy %svalid\n", *validsolved ? "" : "in"); 1904 1905 /* store subproblem variables */ 1906 for( i = nvars-1; i >= 0; i-- ) 1907 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[i]); 1908 1909 /* free variable mapping hash map */ 1910 SCIPhashmapFree(&varmap); 1911 1912 /* set the parameters such that good solutions are found fast */ 1913 SCIPdebugMsg(scip, "setting subproblem parameters\n"); 1914 SCIP_CALL( SCIPsetEmphasis(subscip, SCIP_PARAMEMPHASIS_FEASIBILITY, TRUE) ); 1915 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) ); 1916 SCIP_CALL( SCIPsetHeuristics(subscip, SCIP_PARAMSETTING_AGGRESSIVE, TRUE) ); 1917 1918 /* deactivate expensive pre-root heuristics, since it may happen that the lp relaxation of the subproblem is already 1919 * infeasible; in this case, we do not want to waste time on heuristics before solving the root lp */ 1920 if( !SCIPisParamFixed(subscip, "heuristics/shiftandpropagate/freq") ) 1921 { 1922 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/shiftandpropagate/freq", -1) ); 1923 } 1924 if( !SCIPisParamFixed(subscip, "heuristics/zeroobj/freq") ) 1925 { 1926 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/zeroobj/freq", -1) ); 1927 } 1928 1929 /* forbid recursive call of undercover heuristic */ 1930 if( SCIPisParamFixed(subscip, "heuristics/" HEUR_NAME "/freq") ) 1931 { 1932 SCIPwarningMessage(scip, "unfixing parameter heuristics/" HEUR_NAME "/freq in subscip of undercover heuristic to avoid recursive calls\n"); 1933 SCIP_CALL( SCIPunfixParam(subscip, "heuristics/" HEUR_NAME "/freq") ); 1934 } 1935 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/" HEUR_NAME "/freq", -1) ); 1936 1937 SCIPdebugMsg(scip, "timelimit = %g, memlimit = %g, nodelimit = %" SCIP_LONGINT_FORMAT ", nstallnodes = %" SCIP_LONGINT_FORMAT "\n", timelimit, memorylimit, nodelimit, nstallnodes); 1938 1939 SCIPdebugMsg(scip, "timelimit = %g, memlimit = %g, nodelimit = %" SCIP_LONGINT_FORMAT ", nstallnodes = %" SCIP_LONGINT_FORMAT "\n", timelimit, memorylimit, nodelimit, nstallnodes); 1940 1941 /* disable statistic timing inside sub SCIP */ 1942 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) ); 1943 1944 /* set time, memory and node limits */ 1945 SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) ); 1946 SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) ); 1947 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelimit) ); 1948 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) ); 1949 1950 /* do not abort subproblem on CTRL-C */ 1951 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) ); 1952 1953 /* disable output to console in optimized mode, enable in SCIP's debug mode */ 1954 #ifdef SCIP_DEBUG 1955 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) ); 1956 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000) ); 1957 #else 1958 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) ); 1959 #endif 1960 1961 /* if there is already a solution, add an objective cutoff; note: this does not affect the validity of the subproblem 1962 * if we find solutions later, thus we do not set *validsolved to FALSE */ 1963 if( SCIPgetNSols(scip) > 0 ) 1964 { 1965 SCIP_Real cutoff; 1966 SCIP_Real upperbound; 1967 1968 assert(!SCIPisInfinity(scip, SCIPgetUpperbound(scip))); 1969 upperbound = SCIPgetUpperbound(scip); 1970 1971 if( SCIPisInfinity(scip, -SCIPgetLowerbound(scip)) ) 1972 cutoff = (upperbound >= 0 ? 1.0 - heurdata->minimprove : 1.0 + heurdata->minimprove) * upperbound; 1973 else 1974 cutoff = (1.0 - heurdata->minimprove) * upperbound + heurdata->minimprove * SCIPgetLowerbound(scip); 1975 1976 cutoff = MIN(upperbound, cutoff); 1977 SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) ); 1978 1979 SCIPdebugMsg(scip, "adding objective cutoff=%g (minimprove=%g)\n", cutoff, heurdata->minimprove); 1980 } 1981 1982 /* solve subproblem */ 1983 SCIPdebugMsg(scip, "solving subproblem started\n"); 1984 retcode = SCIPsolve(subscip); 1985 1986 /* Errors in solving the subproblem should not kill the overall solving process 1987 * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. 1988 */ 1989 if( retcode != SCIP_OKAY ) 1990 { 1991 #ifndef NDEBUG 1992 SCIP_CALL( retcode ); 1993 #endif 1994 SCIPwarningMessage(scip, "Error while solving subproblem in Undercover heuristic; sub-SCIP terminated with code <%d>\n",retcode); 1995 /* free array of subproblem variables, and subproblem */ 1996 SCIPfreeBufferArray(scip, &subvars); 1997 SCIPfreeBufferArray(scip, &fixedvars); 1998 SCIP_CALL( SCIPfree(&subscip) ); 1999 return SCIP_OKAY; 2000 } 2001 2002 /* print solving statistics of subproblem if we are in SCIP's debug mode */ 2003 SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) ); 2004 2005 /* store solving status; note: if we proved infeasibility in presence of an objective cutoff beyond the primal bound, 2006 * the subproblem was not a valid copy */ 2007 *validsolved = *validsolved && (SCIPgetStatus(subscip) == SCIP_STATUS_OPTIMAL 2008 || (SCIPgetStatus(subscip) == SCIP_STATUS_INFEASIBLE && (SCIPgetNSols(scip) == 0 || heurdata->minimprove <= 0.0))); 2009 *nusednodes = SCIPgetNNodes(subscip); 2010 2011 /* if a solution was found for the subproblem, create corresponding solution in the original problem */ 2012 if( SCIPgetNSols(subscip) > 0 && (SCIPgetStatus(subscip) != SCIP_STATUS_INFEASIBLE || heurdata->minimprove > 0.0) ) 2013 { 2014 SCIP_SOL** subsols; 2015 SCIP_Bool success = FALSE; 2016 int nsubsols; 2017 2018 /* check, whether a solution was found; 2019 * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted */ 2020 nsubsols = SCIPgetNSols(subscip); 2021 subsols = SCIPgetSols(subscip); 2022 assert(subsols != NULL); 2023 2024 for( i = 0; i < nsubsols; i++ ) 2025 { 2026 /* transform solution to original problem */ 2027 SCIP_CALL( SCIPtranslateSubSol(scip, subscip, subsols[i], heur, subvars, sol) ); 2028 2029 /* try to add new solution to scip */ 2030 SCIP_CALL( SCIPtrySol(scip, *sol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) ); 2031 2032 if( success ) 2033 { 2034 SCIPdebugMsg(scip, "heuristic found %d solutions in subproblem; solution %d feasible in original problem\n", nsubsols, i); 2035 break; 2036 } 2037 else 2038 { 2039 /* free solution structure, since SCIPtranslateSubSol would recreate in the next round */ 2040 SCIP_CALL( SCIPfreeSol(scip, sol) ); 2041 assert(*sol == NULL); 2042 } 2043 } 2044 2045 /* if the best subproblem solution was not accepted in the original problem, then we do not trust the solving status */ 2046 if( !success || i > 0 ) 2047 *validsolved = FALSE; 2048 } 2049 2050 if( *validsolved ) 2051 { 2052 SCIP_CALL( SCIPmergeVariableStatistics(subscip, scip, subvars, vars, nvars) ); 2053 } 2054 2055 /* free array of subproblem variables, and subproblem */ 2056 SCIPfreeBufferArray(scip, &subvars); 2057 SCIPfreeBufferArray(scip, &fixedvars); 2058 SCIP_CALL( SCIPfree(&subscip) ); 2059 2060 return SCIP_OKAY; 2061 } 2062 2063 2064 /** perform fixing of a variable and record bound disjunction information */ 2065 static 2066 SCIP_RETCODE performFixing( 2067 SCIP* scip, /**< SCIP data structure */ 2068 SCIP_VAR* var, /**< variable to fix */ 2069 SCIP_Real val, /**< fixing value */ 2070 SCIP_Bool* infeas, /**< pointer to store whether the fixing lead to infeasibility */ 2071 int* bdlen, /**< current length of bound disjunction */ 2072 SCIP_VAR** bdvars, /**< array of variables in bound disjunction */ 2073 SCIP_BOUNDTYPE* bdtypes, /**< array of bound types in bound disjunction */ 2074 SCIP_Real* bdbounds, /**< array of bounds in bound disjunction */ 2075 SCIP_Real* oldbounds /**< array of bounds before fixing */ 2076 ) 2077 { 2078 SCIP_Longint ndomredsfound; 2079 SCIP_Real oldlb; 2080 SCIP_Real oldub; 2081 int oldbdlen; 2082 2083 assert(scip != NULL); 2084 assert(var != NULL); 2085 assert(val >= SCIPvarGetLbLocal(var)); 2086 assert(val <= SCIPvarGetUbLocal(var)); 2087 assert(infeas != NULL); 2088 assert(bdlen != NULL); 2089 assert(*bdlen >= 0); 2090 assert(*bdlen < 2*SCIPgetNVars(scip)-1); 2091 assert(bdvars != NULL); 2092 assert(bdtypes != NULL); 2093 assert(bdbounds != NULL); 2094 2095 assert(!SCIPvarIsIntegral(var) || SCIPisFeasIntegral(scip, val)); 2096 2097 /* remember length of probing path */ 2098 oldbdlen = *bdlen; 2099 2100 /* get bounds of the variable to fix */ 2101 oldlb = SCIPvarGetLbLocal(var); 2102 oldub = SCIPvarGetUbLocal(var); 2103 2104 /* decrease upper bound to fixing value */ 2105 *infeas = FALSE; 2106 if( SCIPisUbBetter(scip, val, oldlb, oldub) ) 2107 { 2108 /* we only want to open a new probing node if we do not exceed the maximal tree depth */ 2109 if( SCIPgetDepth(scip) < SCIP_MAXTREEDEPTH ) 2110 { 2111 /* create next probing node */ 2112 SCIP_CALL( SCIPnewProbingNode(scip) ); 2113 } 2114 SCIP_CALL( SCIPchgVarUbProbing(scip, var, val) ); 2115 2116 SCIPdebugMsg(scip, "tentatively decreasing upper bound of variable <%s> to %g for probing\n", 2117 SCIPvarGetName(var), val); 2118 2119 /* store bound disjunction information */ 2120 bdvars[*bdlen] = var; 2121 bdtypes[*bdlen] = SCIP_BOUNDTYPE_LOWER; 2122 bdbounds[*bdlen] = SCIPvarIsIntegral(var) ? SCIPfeasCeil(scip, val)+1.0 : val; 2123 oldbounds[*bdlen] = oldub; 2124 (*bdlen)++; 2125 2126 /* propagate the bound change; conflict analysis is performed automatically */ 2127 SCIP_CALL( SCIPpropagateProbing(scip, 0, infeas, &ndomredsfound) ); 2128 SCIPdebugMsg(scip, " --> propagation reduced %" SCIP_LONGINT_FORMAT " further domains\n", ndomredsfound); 2129 2130 /* if propagation led to a cutoff, we backtrack immediately */ 2131 if( *infeas ) 2132 { 2133 *bdlen = oldbdlen; 2134 return SCIP_OKAY; 2135 } 2136 2137 /* store bound before propagation */ 2138 oldbounds[*bdlen] = oldlb; 2139 2140 /* move fixing value into the new domain, since it may be outside due to numerical issues or previous propagation */ 2141 oldlb = SCIPvarGetLbLocal(var); 2142 oldub = SCIPvarGetUbLocal(var); 2143 val = MIN(val, oldub); 2144 val = MAX(val, oldlb); 2145 2146 assert(!SCIPvarIsIntegral(var) || SCIPisFeasIntegral(scip, val)); 2147 } 2148 2149 /* update lower bound to fixing value */ 2150 *infeas = FALSE; 2151 if( SCIPisLbBetter(scip, val, oldlb, oldub) ) 2152 { 2153 /* we only want to open a new probing node if we do not exceed the maximal tree depth */ 2154 if( SCIPgetDepth(scip) < SCIP_MAXTREEDEPTH ) 2155 { 2156 /* create next probing node */ 2157 SCIP_CALL( SCIPnewProbingNode(scip) ); 2158 } 2159 SCIP_CALL( SCIPchgVarLbProbing(scip, var, val) ); 2160 2161 SCIPdebugMsg(scip, "tentatively increasing lower bound of variable <%s> to %g for probing\n", 2162 SCIPvarGetName(var), val); 2163 2164 /* store bound disjunction information */ 2165 bdvars[*bdlen] = var; 2166 bdtypes[*bdlen] = SCIP_BOUNDTYPE_UPPER; 2167 bdbounds[*bdlen] = SCIPvarIsIntegral(var) ? SCIPfeasCeil(scip, val)-1.0 : val; 2168 (*bdlen)++; 2169 2170 /* propagate the bound change */ 2171 SCIP_CALL( SCIPpropagateProbing(scip, 0, infeas, &ndomredsfound) ); 2172 SCIPdebugMsg(scip, " --> propagation reduced %" SCIP_LONGINT_FORMAT " further domains\n", ndomredsfound); 2173 2174 /* if propagation led to a cutoff, we backtrack immediately */ 2175 if( *infeas ) 2176 { 2177 *bdlen = oldbdlen; 2178 return SCIP_OKAY; 2179 } 2180 } 2181 2182 return SCIP_OKAY; 2183 } 2184 2185 static 2186 SCIP_RETCODE fixAndPropagate( 2187 SCIP* scip, /**< original SCIP data structure */ 2188 SCIP_HEURDATA* heurdata, /**< heuristic data structure */ 2189 int* cover, /**< array with indices of the variables in the computed cover */ 2190 int coversize, /**< size of the cover */ 2191 SCIP_Real* fixingvals, /**< fixing values for the variables in the cover */ 2192 int* bdlen, /**< current length of bound disjunction along the probing path */ 2193 SCIP_VAR** bdvars, /**< array of variables in bound disjunction */ 2194 SCIP_BOUNDTYPE* bdtypes, /**< array of bound types in bound disjunction */ 2195 SCIP_Real* bdbounds, /**< array of bounds in bound disjunction */ 2196 SCIP_Real* oldbounds, /**< array of bounds before fixing */ 2197 int* nfixedints, /**< pointer to store number of fixed integer variables */ 2198 int* nfixedconts, /**< pointer to store number of fixed continuous variables */ 2199 int* lastfailed, /**< position in cover array of the variable the fixing of which yielded 2200 * infeasibility */ 2201 SCIP_Bool* infeas /**< pointer to store whether fix-and-propagate led to an infeasibility */ 2202 ) 2203 { 2204 SCIP_VAR** vars; /* original problem's variables */ 2205 2206 int i; 2207 SCIP_Bool lpsolved; 2208 2209 /* start probing in original problem */ 2210 lpsolved = SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL; 2211 SCIP_CALL( SCIPstartProbing(scip) ); 2212 2213 /* initialize data */ 2214 *nfixedints = 0; 2215 *nfixedconts = 0; 2216 *bdlen = 0; 2217 vars = SCIPgetVars(scip); 2218 2219 /* round-fix-propagate-analyze-backtrack for each variable in the cover 2220 * TODO doing a fix-and-propagate for one variable at a time can be very expensive for large covers 2221 * (try, e.g., junkturn with maxcoversizevars=1) 2222 * consider splitting the cover into at most, say, 100 batches, and fix a complete batch before propagating 2223 */ 2224 for( i = 0; i < coversize && !(*infeas); i++ ) 2225 { 2226 SCIP_Real* boundalts; 2227 SCIP_Real* usedvals; 2228 SCIP_Real val; 2229 int nbacktracks; 2230 int nboundalts; 2231 int nfailedvals; 2232 int nusedvals; 2233 int probingdepth; 2234 int idx; 2235 2236 /* get probindex of next variable in the cover */ 2237 idx = cover[i]; 2238 2239 /* nothing to do if the variable was already fixed, e.g., by propagation */ 2240 if( SCIPisEQ(scip, SCIPvarGetLbLocal(vars[idx]), SCIPvarGetUbLocal(vars[idx])) ) 2241 { 2242 fixingvals[i] = SCIPvarGetLbLocal(vars[idx]); 2243 continue; 2244 } 2245 2246 /* we will store the fixing values already used to avoid try the same value twice */ 2247 SCIP_CALL( SCIPallocBufferArray(scip, &usedvals, heurdata->maxbacktracks+1) ); 2248 nusedvals = 0; 2249 2250 /* backtracking loop */ 2251 *infeas = TRUE; 2252 nfailedvals = 0; 2253 nboundalts = 0; 2254 boundalts = NULL; 2255 val = 0.0; 2256 for( nbacktracks = 0; nbacktracks <= heurdata->maxbacktracks+nfailedvals && *infeas; nbacktracks++ ) 2257 { 2258 SCIP_Real oldlb; 2259 SCIP_Real oldub; 2260 SCIP_Bool usedbefore; 2261 int j; 2262 2263 probingdepth = SCIPgetProbingDepth(scip); 2264 2265 /* get fixing value */ 2266 if( nbacktracks < heurdata->nfixingalts ) 2267 { 2268 SCIP_Bool success; 2269 2270 /* if the lp relaxation is not solved, we do not even try to retrieve the lp solution value; 2271 * if the NLP relaxation is not constructed, we do not even try to retrieve the NLP solution value; 2272 * if there is no feasible solution yet, we do not even try to obtain the value in the incumbent */ 2273 success = FALSE; 2274 if( (heurdata->fixingalts[nbacktracks] != 'l' || lpsolved) 2275 && (heurdata->fixingalts[nbacktracks] != 'n' || !heurdata->nlpfailed) 2276 && (heurdata->fixingalts[nbacktracks] != 'i' || SCIPgetBestSol(scip) != NULL) ) 2277 { 2278 SCIP_CALL( getFixingValue(scip, heurdata, vars[idx], &val, heurdata->fixingalts[nbacktracks], &success, *bdlen, bdvars, bdtypes, oldbounds) ); 2279 } 2280 2281 if( !success ) 2282 { 2283 SCIPdebugMsg(scip, "retrieving fixing value '%c' for variable <%s> failed, trying next in the list\n", 2284 heurdata->fixingalts[nbacktracks], SCIPvarGetName(vars[idx])); 2285 nfailedvals++; 2286 continue; 2287 } 2288 2289 /* for the first (successfully retrieved) fixing value, compute (at most 4) bound dependent 2290 * alternative fixing values */ 2291 if( boundalts == NULL ) 2292 { 2293 SCIP_CALL( SCIPallocBufferArray(scip, &boundalts, 4) ); 2294 nboundalts = 0; 2295 calculateAlternatives(scip, vars[idx], val, &nboundalts, boundalts); 2296 assert(nboundalts >= 0); 2297 assert(nboundalts <= 4); 2298 } 2299 } 2300 /* get alternative fixing value */ 2301 else if( boundalts != NULL && nbacktracks < heurdata->nfixingalts+nboundalts ) 2302 { 2303 assert(nbacktracks-heurdata->nfixingalts >= 0); 2304 val = boundalts[nbacktracks-heurdata->nfixingalts]; 2305 } 2306 else 2307 break; 2308 2309 /* round fixing value */ 2310 if( SCIPvarIsIntegral(vars[idx]) && !SCIPisIntegral(scip, val) ) 2311 { 2312 SCIP_CALL( roundFixingValue(scip, &val, vars[idx], heurdata->locksrounding) ); 2313 assert(SCIPisIntegral(scip, val)); 2314 } 2315 2316 /* move value into the domain, since it may be outside due to numerical issues or previous propagation */ 2317 oldlb = SCIPvarGetLbLocal(vars[idx]); 2318 oldub = SCIPvarGetUbLocal(vars[idx]); 2319 val = MIN(val, oldub); 2320 val = MAX(val, oldlb); 2321 2322 assert(!SCIPvarIsIntegral(vars[idx]) || SCIPisFeasIntegral(scip, val)); 2323 2324 /* check if this fixing value was already used */ 2325 usedbefore = FALSE; 2326 for( j = nusedvals-1; j >= 0 && !usedbefore; j-- ) 2327 usedbefore = SCIPisFeasEQ(scip, val, usedvals[j]); 2328 2329 if( usedbefore ) 2330 { 2331 nfailedvals++; 2332 continue; 2333 } 2334 2335 /* store fixing value */ 2336 assert(nusedvals < heurdata->maxbacktracks); 2337 usedvals[nusedvals] = val; 2338 nusedvals++; 2339 2340 /* fix-propagate-analyze */ 2341 SCIP_CALL( performFixing(scip, vars[idx], val, infeas, bdlen, bdvars, bdtypes, bdbounds, oldbounds) ); 2342 2343 /* if infeasible, backtrack and try alternative fixing value */ 2344 if( *infeas ) 2345 { 2346 SCIPdebugMsg(scip, " --> cutoff detected - backtracking\n"); 2347 SCIP_CALL( SCIPbacktrackProbing(scip, probingdepth) ); 2348 } 2349 } 2350 2351 /* free array of alternative backtracking values */ 2352 if( boundalts != NULL) 2353 SCIPfreeBufferArray(scip, &boundalts); 2354 SCIPfreeBufferArray(scip, &usedvals); 2355 2356 /* backtracking loop unsuccessful */ 2357 if( *infeas ) 2358 { 2359 SCIPdebugMsg(scip, "no feasible fixing value found for variable <%s> in fixing order\n", 2360 SCIPvarGetName(vars[idx])); 2361 break; 2362 } 2363 /* fixing successful */ 2364 else 2365 { 2366 /* store successful fixing value */ 2367 fixingvals[i] = val; 2368 2369 /* statistics */ 2370 if( SCIPvarGetType(vars[idx]) == SCIP_VARTYPE_CONTINUOUS ) 2371 (*nfixedconts)++; 2372 else 2373 (*nfixedints)++; 2374 } 2375 } 2376 assert(*infeas || i == coversize); 2377 assert(!(*infeas) || i < coversize); 2378 2379 /* end of dive */ 2380 SCIP_CALL( SCIPendProbing(scip) ); 2381 2382 *lastfailed = i; 2383 2384 return SCIP_OKAY; 2385 } 2386 2387 /** main procedure of the undercover heuristic */ 2388 static 2389 SCIP_RETCODE SCIPapplyUndercover( 2390 SCIP* scip, /**< original SCIP data structure */ 2391 SCIP_HEUR* heur, /**< heuristic data structure */ 2392 SCIP_RESULT* result, /**< result data structure */ 2393 SCIP_Real timelimit, /**< time limit */ 2394 SCIP_Real memorylimit, /**< memory limit */ 2395 SCIP_Longint nstallnodes /**< number of stalling nodes for the subproblem */ 2396 ) 2397 { 2398 SCIP_HEURDATA* heurdata; /* heuristic data */ 2399 SCIP_VAR** vars; /* original problem's variables */ 2400 SCIP_CLOCK* clock; /* clock for updating time limit */ 2401 2402 SCIP* coveringscip; /* SCIP data structure for covering problem */ 2403 SCIP_VAR** coveringvars; /* covering variables */ 2404 SCIP_Real* fixingvals; /* array for storing fixing values used */ 2405 int* cover; /* array to store problem indices of variables in the computed cover */ 2406 2407 SCIP_VAR** bdvars; /* array of variables in bound disjunction along the probing path */ 2408 SCIP_BOUNDTYPE* bdtypes; /* array of bound types in bound disjunction along the probing path */ 2409 SCIP_Real* bdbounds; /* array of bounds in bound disjunction along the probing path */ 2410 SCIP_Real* oldbounds; /* array of bounds before fixing along the probing path */ 2411 2412 SCIP_Real maxcoversize; 2413 2414 int coversize; 2415 int nvars; 2416 int ncovers; 2417 int nunfixeds; 2418 int nnlconss; 2419 int i; 2420 2421 SCIP_Bool success; 2422 SCIP_Bool reusecover; 2423 2424 assert(scip != NULL); 2425 assert(heur != NULL); 2426 assert(result != NULL); 2427 assert(*result == SCIP_DIDNOTFIND); 2428 2429 /* create and start timing */ 2430 SCIP_CALL( SCIPcreateClock(scip, &clock) ); 2431 SCIP_CALL( SCIPstartClock(scip, clock) ); 2432 2433 /* initialize */ 2434 fixingvals = NULL; 2435 cover = NULL; 2436 bdvars = NULL; 2437 bdtypes = NULL; 2438 bdbounds = NULL; 2439 oldbounds = NULL; 2440 coversize = 0; 2441 2442 /* get heuristic data */ 2443 heurdata = SCIPheurGetData(heur); 2444 assert(heurdata != NULL); 2445 2446 /* NLP relaxation has not been solved yet (only solve once, not again for each cover or dive, because it is expensive) */ 2447 heurdata->nlpsolved = FALSE; 2448 2449 /* if solving the NLP relaxation has failed too often in previous runs, or NLP and NLP solver is not available, we do 2450 * not even try 2451 */ 2452 heurdata->nlpfailed = heurdata->nnlpfails >= MAXNLPFAILS || !SCIPisNLPConstructed(scip) || SCIPgetNNlpis(scip) == 0; 2453 2454 /* get variable data of original problem */ 2455 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 2456 2457 /* get number of nonlinear constraints */ 2458 nnlconss = 0; 2459 for( i = 0; i < heurdata->nnlconshdlrs; ++i ) 2460 nnlconss += SCIPconshdlrGetNActiveConss(heurdata->nlconshdlrs[i]); 2461 assert(nnlconss >= 0); 2462 assert(nnlconss <= SCIPgetNConss(scip)); 2463 2464 /* run only if problem is sufficiently nonlinear */ 2465 if( nnlconss < (SCIP_Real) SCIPgetNConss(scip) * heurdata->mincoveredrel || nnlconss < heurdata->mincoveredabs ) 2466 { 2467 SCIPdebugMsg(scip, "too few nonlinear constraints present, not running\n"); 2468 2469 /* free clock */ 2470 SCIP_CALL( SCIPfreeClock(scip, &clock) ); 2471 2472 return SCIP_OKAY; 2473 } 2474 2475 /* calculate upper bound for cover size */ 2476 if( heurdata->maxcoversizevars < 1.0 ) 2477 { 2478 maxcoversize = 0.0; 2479 for( i = 0; i < nvars; ++i ) 2480 if( !SCIPvarIsRelaxationOnly(vars[i]) ) 2481 maxcoversize += 1.0; 2482 maxcoversize *= heurdata->maxcoversizevars; 2483 } 2484 else 2485 { 2486 /* if maxcoversizevars == 1.0, then there is no limit derived from number of variables */ 2487 maxcoversize = (SCIP_Real)nvars; 2488 } 2489 if( heurdata->maxcoversizeconss < SCIP_REAL_MAX ) 2490 { 2491 SCIP_Real maxcoversizeconss; 2492 maxcoversizeconss = heurdata->maxcoversizeconss * nnlconss / ((SCIP_Real) SCIPgetNConss(scip)); 2493 maxcoversize = MIN(maxcoversize, maxcoversizeconss); 2494 } 2495 2496 /* create covering problem */ 2497 success = FALSE; 2498 SCIP_CALL( SCIPcreate(&coveringscip) ); 2499 SCIP_CALL( SCIPincludeDefaultPlugins(coveringscip) ); 2500 SCIP_CALL( SCIPallocBufferArray(scip, &coveringvars, nvars) ); 2501 SCIP_CALL( createCoveringProblem(scip, coveringscip, coveringvars, heurdata->globalbounds, heurdata->onlyconvexify, 2502 heurdata->coverand, heurdata->coverbd, heurdata->coverind, heurdata->covernl, heurdata->coveringobj, 2503 &success) ); 2504 2505 if( !success ) 2506 { 2507 SCIPdebugMsg(scip, "creating covering problem failed, terminating\n"); 2508 goto TERMINATE; 2509 } 2510 else 2511 { 2512 SCIPdebugMsg(scip, "covering problem created successfully\n"); 2513 } 2514 2515 /* count number of unfixed covering variables */ 2516 nunfixeds = 0; 2517 for( i = nvars-1; i >= 0; i-- ) 2518 { 2519 if( coveringvars[i] != NULL && SCIPisFeasEQ(coveringscip, SCIPvarGetLbGlobal(coveringvars[i]), 1.0) ) 2520 nunfixeds++; 2521 } 2522 2523 /* update time limit */ 2524 SCIP_CALL( updateTimelimit(scip, clock, &timelimit) ); 2525 2526 if( timelimit <= MINTIMELEFT ) 2527 { 2528 SCIPdebugMsg(scip, "time limit hit, terminating\n"); 2529 goto TERMINATE; 2530 } 2531 2532 /* update memory left */ 2533 memorylimit -= SCIPgetMemUsed(coveringscip)/1048576.0; 2534 memorylimit -= SCIPgetMemExternEstim(coveringscip)/1048576.0; 2535 2536 /* allocate memory for storing bound disjunction information along probing path */ 2537 SCIP_CALL( SCIPallocBufferArray(scip, &bdvars, 2*nvars) ); 2538 SCIP_CALL( SCIPallocBufferArray(scip, &bdtypes, 2*nvars) ); 2539 SCIP_CALL( SCIPallocBufferArray(scip, &bdbounds, 2*nvars) ); 2540 SCIP_CALL( SCIPallocBufferArray(scip, &oldbounds, 2*nvars) ); 2541 2542 /* initialize data for recovering loop */ 2543 SCIP_CALL( SCIPallocBufferArray(scip, &cover, nvars) ); 2544 SCIP_CALL( SCIPallocBufferArray(scip, &fixingvals, nvars) ); 2545 ncovers = 0; 2546 success = FALSE; 2547 reusecover = FALSE; 2548 2549 heurdata->nfixingalts = (int) strlen(heurdata->fixingalts); 2550 assert(heurdata->nfixingalts >= 1); 2551 2552 /* recovering loop */ 2553 while( (ncovers <= heurdata->maxrecovers || reusecover) && !success ) 2554 { 2555 int lastfailed; 2556 int ndives; 2557 int nfixedints; 2558 int nfixedconts; 2559 int bdlen; /* current length of bound disjunction along the probing path */ 2560 2561 SCIP_Bool conflictcreated; 2562 2563 SCIPdebugMsg(scip, "solving covering problem\n\n"); 2564 success = FALSE; 2565 bdlen = 0; 2566 conflictcreated = FALSE; 2567 2568 /* solve covering problem */ 2569 if( !reusecover ) 2570 { 2571 SCIP_CALL( solveCoveringProblem(coveringscip, nvars, coveringvars, &coversize, cover, 2572 timelimit, memorylimit + (SCIPgetMemExternEstim(coveringscip)+SCIPgetMemUsed(coveringscip))/1048576.0, maxcoversize, &success) ); 2573 2574 SCIPstatistic( 2575 if( ncovers == 0 && success ) 2576 SCIPstatisticPrintf("UCstats coversize abs: %6d rel: %9.6f\n", coversize, 100.0*coversize /(SCIP_Real)nvars); 2577 ); 2578 2579 assert(coversize >= 0); 2580 assert(coversize <= nvars); 2581 ncovers++; 2582 2583 /* free transformed covering problem immediately */ 2584 SCIP_CALL( SCIPfreeTransform(coveringscip) ); 2585 2586 /* terminate if no feasible cover was found */ 2587 if( !success ) 2588 { 2589 SCIPdebugMsg(scip, "no feasible cover found in covering problem %d, terminating\n", ncovers); 2590 goto TERMINATE; 2591 } 2592 2593 /* terminate, if cover is empty or too large */ 2594 if( coversize == 0 || coversize > maxcoversize ) 2595 { 2596 SCIPdebugMsg(scip, "terminating due to coversize=%d\n", coversize); 2597 goto TERMINATE; 2598 } 2599 2600 /* terminate, if cover too large for the ratio of nonlinear constraints */ 2601 if( heurdata->maxcoversizeconss < SCIP_REAL_MAX && coversize > heurdata->maxcoversizeconss * nnlconss / (SCIP_Real) SCIPgetNConss(scip) ) 2602 { 2603 SCIPdebugMsg(scip, "terminating due to coversize=%d\n", coversize); 2604 goto TERMINATE; 2605 } 2606 } 2607 2608 /* data setup */ 2609 ndives = 0; 2610 nfixedints = 0; 2611 nfixedconts = 0; 2612 success = FALSE; 2613 lastfailed = reusecover ? MAX(1, coversize-1) : coversize; 2614 2615 /* round-fix-propagate-analyze-backtrack-reorder loop */ 2616 while( ndives <= heurdata->maxreorders && !success ) 2617 { 2618 SCIP_Bool reordered; 2619 SCIP_Bool infeas; 2620 2621 /* compute fixing order */ 2622 SCIP_CALL( computeFixingOrder(scip, heurdata, nvars, vars, coversize, cover, lastfailed, &reordered) ); 2623 reordered = reordered || ndives == 0; 2624 SCIPdebugMsg(scip, "%sordering variables in cover %s\n", ndives == 0 ? "" : "re", reordered ? "" : "failed"); 2625 2626 /* stop if order has not changed */ 2627 if( !reordered ) 2628 break; 2629 2630 infeas = FALSE; 2631 SCIP_CALL( fixAndPropagate(scip, heurdata, cover, coversize, fixingvals, &bdlen, bdvars, bdtypes, bdbounds, oldbounds, 2632 &nfixedints, &nfixedconts, &lastfailed, &infeas) ); 2633 ndives++; 2634 success = !infeas; 2635 } 2636 2637 /* update time limit */ 2638 SCIPdebugMsg(scip, "%d dive%s of fix-and-propagate for cover %d took %.1f seconds\n", ndives, ndives > 1 ? "s" : "", ncovers, SCIPgetClockTime(scip, clock)); 2639 SCIP_CALL( updateTimelimit(scip, clock, &timelimit) ); 2640 2641 if( timelimit <= MINTIMELEFT ) 2642 { 2643 SCIPdebugMsg(scip, "time limit hit, terminating\n"); 2644 goto TERMINATE; 2645 } 2646 2647 /* no feasible fixing could be found for the current cover */ 2648 if( !success ) 2649 { 2650 SCIPdebugMsg(scip, "no feasible fixing values found for cover %d\n", ncovers); 2651 } 2652 else 2653 { 2654 SCIP_SOL* sol; 2655 SCIP_Longint nsubnodes; 2656 SCIP_Bool validsolved; 2657 2658 SCIPdebugMsg(scip, "heuristic successfully fixed %d variables (%d integral, %d continuous) during probing\n", 2659 nfixedints+nfixedconts, nfixedints, nfixedconts); /*lint !e771*/ 2660 2661 /* solve sub-CIP and pass feasible solutions to original problem */ 2662 success = FALSE; 2663 validsolved = FALSE; 2664 sol = NULL; 2665 nsubnodes = 0; 2666 2667 SCIP_CALL( solveSubproblem(scip, heur, coversize, cover, fixingvals, 2668 timelimit, memorylimit, heurdata->maxnodes, nstallnodes, &validsolved, &sol, &nsubnodes) ); 2669 2670 /* update number of sub-CIP nodes used by heuristic so far */ 2671 heurdata->nusednodes += nsubnodes; 2672 2673 /* if the subproblem was constructed from a valid copy and solved, try to forbid the assignment of fixing 2674 * values to variables in the cover 2675 */ 2676 if( validsolved ) 2677 { 2678 SCIP_Real maxvarsfac; 2679 SCIP_Bool useconf; 2680 int minmaxvars; 2681 2682 SCIP_CALL( SCIPgetIntParam(scip, "conflict/minmaxvars", &minmaxvars) ); 2683 SCIP_CALL( SCIPgetRealParam(scip, "conflict/maxvarsfac", &maxvarsfac) ); 2684 2685 useconf = bdlen > 0 && (bdlen <= minmaxvars || bdlen < maxvarsfac*nvars); 2686 2687 if( useconf ) 2688 { 2689 /* even if we had reset the global bounds at start of probing, the constraint might be only locally valid due to local constraints/cuts */ 2690 SCIP_CALL( createConflict(scip, bdlen, bdvars, bdtypes, bdbounds, SCIPgetDepth(scip) > 0, TRUE, TRUE, &success) ); 2691 conflictcreated = success; 2692 } 2693 2694 SCIPdebugMsg(scip, "subproblem solved (%s), forbidding assignment in original problem %s, %sconflict length=%d\n", 2695 sol == NULL ? "infeasible" : "optimal", 2696 success ? "successful" : "failed", useconf ? "" : "skipped due to ", bdlen); 2697 } 2698 2699 /* heuristic succeeded */ 2700 success = (sol != NULL); 2701 if( success ) 2702 { 2703 *result = SCIP_FOUNDSOL; 2704 success = TRUE; 2705 2706 /* call NLP local search heuristic unless it has failed too often */ 2707 if( heurdata->postnlp && heurdata->npostnlpfails < MAXPOSTNLPFAILS ) 2708 { 2709 if( nfixedconts == 0 && validsolved ) 2710 { 2711 SCIPdebugMsg(scip, "subproblem solved to optimality while all covering variables are integral, hence skipping NLP local search\n"); 2712 } 2713 else if( heurdata->nlpheur == NULL ) 2714 { 2715 SCIPdebugMsg(scip, "NLP heuristic not found, skipping NLP local search\n"); 2716 } 2717 else 2718 { 2719 SCIP_RESULT nlpresult; 2720 2721 SCIP_CALL( SCIPapplyHeurSubNlp(scip, heurdata->nlpheur, &nlpresult, sol, NULL) ); 2722 SCIPdebugMsg(scip, "NLP local search %s\n", nlpresult == SCIP_FOUNDSOL ? "successful" : "failed"); 2723 2724 if( nlpresult == SCIP_FOUNDSOL ) 2725 heurdata->npostnlpfails = 0; 2726 else 2727 heurdata->npostnlpfails++; 2728 } 2729 } 2730 2731 /* free solution */ 2732 SCIP_CALL( SCIPfreeSol(scip, &sol) ); 2733 } 2734 } 2735 2736 /* heuristic failed but we have another recovering try, hence we forbid the current cover in the covering problem */ 2737 if( !success && ncovers <= heurdata->maxrecovers ) 2738 { 2739 SCIP_Bool infeas; 2740 int diversification; 2741 2742 /* compute minimal number of unfixed covering variables (in the cover) which have to change their value */ 2743 diversification = (int) SCIPfeasCeil(scip, (heurdata->recoverdiv) * (SCIP_Real) nunfixeds); 2744 diversification = MAX(diversification, 1); 2745 2746 /* forbid unsuccessful cover globally in covering problem */ 2747 SCIP_CALL( forbidCover(coveringscip, nvars, coveringvars, coversize, cover, diversification, &success, &infeas) ); 2748 2749 if( infeas ) 2750 { 2751 SCIPdebugMsg(scip, "recovering problem infeasible (diversification=%d), terminating\n", diversification); 2752 goto TERMINATE; 2753 } 2754 else if( !success ) 2755 { 2756 SCIPdebugMsg(scip, "failed to forbid current cover in the covering problem, terminating\n"); 2757 goto TERMINATE; 2758 } 2759 else 2760 { 2761 SCIPdebugMsg(scip, "added constraint to the covering problem in order to forbid current cover\n"); 2762 success = FALSE; 2763 } 2764 } 2765 2766 /* try to re-use the same cover at most once */ 2767 if( heurdata->reusecover && !reusecover && conflictcreated ) 2768 reusecover = TRUE; 2769 else 2770 reusecover = FALSE; 2771 } 2772 2773 TERMINATE: 2774 if( *result != SCIP_FOUNDSOL && *result != SCIP_DELAYED ) 2775 { 2776 SCIPdebugMsg(scip, "heuristic terminating unsuccessfully\n"); 2777 } 2778 2779 /* we must remain in NLP diving mode until here to be able to retrieve NLP solution values easily */ 2780 /* assert((SCIPisNLPConstructed(scip) == FALSE && heurdata->nlpsolved == FALSE) || 2781 * (SCIPisNLPConstructed(scip) == TRUE && heurdata->nlpsolved == SCIPnlpIsDiving(SCIPgetNLP(scip)))); 2782 */ 2783 if( heurdata->nlpsolved ) 2784 { 2785 SCIP_CALL( SCIPendDiveNLP(scip) ); 2786 } 2787 2788 /* free arrays for storing the cover */ 2789 SCIPfreeBufferArrayNull(scip, &fixingvals); 2790 SCIPfreeBufferArrayNull(scip, &cover); 2791 2792 /* free arrays for storing bound disjunction information along probing path */ 2793 SCIPfreeBufferArrayNull(scip, &oldbounds); 2794 SCIPfreeBufferArrayNull(scip, &bdbounds); 2795 SCIPfreeBufferArrayNull(scip, &bdtypes); 2796 SCIPfreeBufferArrayNull(scip, &bdvars); 2797 2798 /* free covering problem */ 2799 for( i = nvars-1; i >= 0; i-- ) 2800 { 2801 if( coveringvars[i] == NULL ) 2802 continue; 2803 SCIP_CALL( SCIPreleaseVar(coveringscip, &coveringvars[i]) ); 2804 } 2805 SCIPfreeBufferArray(scip, &coveringvars); 2806 SCIP_CALL( SCIPfree(&coveringscip) ); 2807 2808 /* free clock */ 2809 SCIP_CALL( SCIPfreeClock(scip, &clock) ); 2810 2811 return SCIP_OKAY; 2812 } 2813 2814 2815 /* 2816 * Callback methods of primal heuristic 2817 */ 2818 2819 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 2820 static 2821 SCIP_DECL_HEURCOPY(heurCopyUndercover) 2822 { /*lint --e{715}*/ 2823 assert(scip != NULL); 2824 assert(heur != NULL); 2825 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 2826 2827 /* call inclusion method of primal heuristic */ 2828 SCIP_CALL( SCIPincludeHeurUndercover(scip) ); 2829 2830 return SCIP_OKAY; 2831 } 2832 2833 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 2834 static 2835 SCIP_DECL_HEURFREE(heurFreeUndercover) 2836 { /*lint --e{715}*/ 2837 SCIP_HEURDATA* heurdata; 2838 2839 assert(scip != NULL); 2840 assert(heur != NULL); 2841 2842 /* get heuristic data */ 2843 heurdata = SCIPheurGetData(heur); 2844 assert(heurdata != NULL); 2845 2846 /* free heuristic data */ 2847 SCIPfreeBlockMemory(scip, &heurdata); 2848 SCIPheurSetData(heur, NULL); 2849 2850 return SCIP_OKAY; 2851 } 2852 2853 /** initialization method of primal heuristic (called after problem was transformed) */ 2854 static 2855 SCIP_DECL_HEURINIT(heurInitUndercover) 2856 { /*lint --e{715}*/ 2857 SCIP_HEURDATA* heurdata; 2858 2859 assert(heur != NULL); 2860 assert(scip != NULL); 2861 2862 /* get heuristic's data */ 2863 heurdata = SCIPheurGetData(heur); 2864 assert(heurdata != NULL); 2865 2866 /* create random number generator */ 2867 SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen, 2868 DEFAULT_RANDSEED, TRUE) ); 2869 2870 return SCIP_OKAY; 2871 } 2872 2873 /** deinitialization method of primal heuristic */ 2874 static 2875 SCIP_DECL_HEUREXIT(heurExitUndercover) 2876 { /*lint --e{715}*/ 2877 SCIP_HEURDATA* heurdata; 2878 2879 assert(heur != NULL); 2880 assert(scip != NULL); 2881 2882 /* get heuristic's data */ 2883 heurdata = SCIPheurGetData(heur); 2884 assert(heurdata != NULL); 2885 2886 /* free random number generator */ 2887 SCIPfreeRandom(scip, &heurdata->randnumgen); 2888 2889 return SCIP_OKAY; 2890 } 2891 2892 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */ 2893 static 2894 SCIP_DECL_HEURINITSOL(heurInitsolUndercover) 2895 { /*lint --e{715}*/ 2896 SCIP_HEURDATA* heurdata; 2897 int h; 2898 2899 assert(heur != NULL); 2900 assert(scip != NULL); 2901 2902 /* get heuristic's data */ 2903 heurdata = SCIPheurGetData(heur); 2904 assert(heurdata != NULL); 2905 2906 /* initialize counters to zero */ 2907 heurdata->nusednodes = 0; 2908 heurdata->npostnlpfails = 0; 2909 heurdata->nnlpfails = 0; 2910 2911 /* if the heuristic is called at the root node, we may want to be called directly after the initial root LP solve */ 2912 if( heurdata->beforecuts && SCIPheurGetFreqofs(heur) == 0 ) 2913 SCIPheurSetTimingmask(heur, SCIP_HEURTIMING_DURINGLPLOOP); 2914 2915 /* find nonlinear constraint handlers */ 2916 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->nlconshdlrs, 4) );/*lint !e506*/ 2917 h = 0; 2918 2919 if( heurdata->coverand ) 2920 { 2921 heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "and"); 2922 if( heurdata->nlconshdlrs[h] != NULL ) 2923 h++; 2924 } 2925 if( heurdata->coverbd ) 2926 { 2927 heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "bounddisjunction"); 2928 if( heurdata->nlconshdlrs[h] != NULL ) 2929 h++; 2930 } 2931 if( heurdata->coverind ) 2932 { 2933 heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "indicator"); 2934 if( heurdata->nlconshdlrs[h] != NULL ) 2935 h++; 2936 } 2937 if( heurdata->covernl ) 2938 { 2939 heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "nonlinear"); 2940 if( heurdata->nlconshdlrs[h] != NULL ) 2941 h++; 2942 } 2943 heurdata->nnlconshdlrs = h; 2944 assert( heurdata->nnlconshdlrs <= 4 ); 2945 2946 /* find NLP local search heuristic */ 2947 heurdata->nlpheur = SCIPfindHeur(scip, "subnlp"); 2948 2949 return SCIP_OKAY; 2950 } 2951 2952 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */ 2953 static 2954 SCIP_DECL_HEUREXITSOL(heurExitsolUndercover) 2955 { 2956 SCIP_HEURDATA* heurdata; 2957 2958 assert(heur != NULL); 2959 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 2960 2961 /* get heuristic's data */ 2962 heurdata = SCIPheurGetData(heur); 2963 assert(heurdata != NULL); 2964 2965 /* free array of nonlinear constraint handlers */ 2966 SCIPfreeBlockMemoryArray(scip, &heurdata->nlconshdlrs, 4); 2967 2968 /* reset timing, if it was changed temporary (at the root node) */ 2969 SCIPheurSetTimingmask(heur, HEUR_TIMING); 2970 2971 return SCIP_OKAY; 2972 } 2973 2974 /** execution method of primal heuristic */ 2975 static 2976 SCIP_DECL_HEUREXEC(heurExecUndercover) 2977 { /*lint --e{715}*/ 2978 SCIP_HEURDATA* heurdata; /* heuristic data */ 2979 SCIP_Real timelimit; /* time limit for the subproblem */ 2980 SCIP_Real memorylimit; /* memory limit for the subproblem */ 2981 SCIP_Longint nstallnodes; /* number of stalling nodes for the subproblem */ 2982 SCIP_Bool run; 2983 SCIP_Bool avoidmemout; 2984 2985 int h; 2986 2987 assert(heur != NULL); 2988 assert(scip != NULL); 2989 assert(result != NULL); 2990 2991 *result = SCIP_DIDNOTRUN; 2992 2993 /* do not call heuristic of node was already detected to be infeasible */ 2994 if( nodeinfeasible ) 2995 return SCIP_OKAY; 2996 2997 /* get heuristic's data */ 2998 heurdata = SCIPheurGetData(heur); 2999 assert(heurdata != NULL); 3000 3001 /* only call heuristic once at the root */ 3002 if( SCIPgetDepth(scip) == 0 && SCIPheurGetNCalls(heur) > 0 ) 3003 return SCIP_OKAY; 3004 3005 /* if we want to use NLP fixing values exclusively and no NLP solver is available, we cannot run */ 3006 if( strcmp(heurdata->fixingalts, "n") == 0 && SCIPgetNNlpis(scip) == 0 ) 3007 { 3008 SCIPdebugMsg(scip, "skipping undercover heuristic: want to use NLP fixing values exclusively, but no NLP solver available\n"); 3009 return SCIP_OKAY; 3010 } 3011 3012 /* calculate stallnode limit */ 3013 nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip)); 3014 3015 /* reward heuristic if it succeeded often */ 3016 nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur) + 1.0)/(SCIPheurGetNCalls(heur) + 1.0)); 3017 nstallnodes -= SUBMIPSETUPCOSTS * SCIPheurGetNCalls(heur); /* account for the setup costs of the sub-CIP */ 3018 nstallnodes += heurdata->nodesofs; 3019 3020 /* determine the node limit for the current process */ 3021 nstallnodes -= heurdata->nusednodes; 3022 nstallnodes = MIN(nstallnodes, heurdata->maxnodes); 3023 nstallnodes = MAX(nstallnodes, 1); 3024 3025 /* only call heuristics if we have enough nodes left to call sub-CIP solving */ 3026 if( nstallnodes < heurdata->minnodes ) 3027 { 3028 SCIPdebugMsg(scip, "skipping undercover heuristic: nstallnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->minnodes); 3029 return SCIP_OKAY; 3030 } 3031 3032 /* only call heuristics if we have enough time left */ 3033 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) ); 3034 if( !SCIPisInfinity(scip, timelimit) ) 3035 timelimit -= SCIPgetSolvingTime(scip); 3036 if( timelimit <= 2*MINTIMELEFT ) 3037 { 3038 SCIPdebugMsg(scip, "skipping undercover heuristic: time left=%g\n", timelimit); 3039 return SCIP_OKAY; 3040 } 3041 3042 /* only call heuristics if we have enough memory left */ 3043 SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) ); 3044 SCIP_CALL( SCIPgetBoolParam(scip, "misc/avoidmemout", &avoidmemout) ); 3045 if( !SCIPisInfinity(scip, memorylimit) ) 3046 { 3047 memorylimit -= SCIPgetMemUsed(scip)/1048576.0; 3048 memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0; 3049 } 3050 3051 if( avoidmemout && memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 ) 3052 { 3053 SCIPdebugMsg(scip, "skipping undercover heuristic: too little memory\n"); 3054 return SCIP_OKAY; 3055 } 3056 3057 /* only call heuristic if nonlinear constraints are present */ 3058 run = FALSE; 3059 for( h = heurdata->nnlconshdlrs-1; h >= 0 && !run; h-- ) 3060 { 3061 run = (SCIPconshdlrGetNActiveConss(heurdata->nlconshdlrs[h]) > 0); 3062 } 3063 3064 /* go through all nlrows and check for general nonlinearities */ 3065 if( !run && SCIPisNLPConstructed(scip) ) 3066 { 3067 SCIP_NLROW** nlrows; 3068 int nnlrows; 3069 int i; 3070 3071 /* get nlrows */ 3072 nnlrows = SCIPgetNNLPNlRows(scip); 3073 nlrows = SCIPgetNLPNlRows(scip); 3074 3075 /* check for a nonlinear nlrow; start from the end since we expect the linear nlrows at the end */ 3076 for( i = nnlrows-1; i >= 0 && !run; i-- ) 3077 { 3078 assert(nlrows[i] != NULL); 3079 run = SCIPnlrowGetExpr(nlrows[i]) != NULL; 3080 } 3081 } 3082 3083 if( !run ) 3084 { 3085 SCIPdebugMsg(scip, "skipping undercover heuristic: no nonlinear constraints found\n"); 3086 return SCIP_OKAY; 3087 } 3088 3089 /* only call heuristics if solving has not stopped yet */ 3090 if( SCIPisStopped(scip) ) 3091 return SCIP_OKAY; 3092 3093 /* reset timing, if it was changed temporary (at the root node) */ 3094 if( heurtiming != HEUR_TIMING ) 3095 SCIPheurSetTimingmask(heur, HEUR_TIMING); 3096 3097 /* call heuristic */ 3098 *result = SCIP_DIDNOTFIND; 3099 SCIPdebugMsg(scip, "calling undercover heuristic for <%s> at depth %d\n", SCIPgetProbName(scip), SCIPgetDepth(scip)); 3100 3101 SCIP_CALL( SCIPapplyUndercover(scip, heur, result, timelimit, memorylimit, nstallnodes) ); 3102 3103 return SCIP_OKAY; 3104 } 3105 3106 3107 /* 3108 * primal heuristic specific interface methods 3109 */ 3110 3111 /** creates the undercover primal heuristic and includes it in SCIP */ 3112 SCIP_RETCODE SCIPincludeHeurUndercover( 3113 SCIP* scip /**< SCIP data structure */ 3114 ) 3115 { 3116 SCIP_HEURDATA* heurdata; 3117 SCIP_HEUR* heur; 3118 3119 /* create undercover primal heuristic data */ 3120 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 3121 3122 /* always use local bounds */ 3123 heurdata->globalbounds = FALSE; 3124 3125 /* include primal heuristic */ 3126 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 3127 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 3128 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecUndercover, heurdata) ); 3129 3130 assert(heur != NULL); 3131 3132 /* set non-NULL pointers to callback methods */ 3133 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyUndercover) ); 3134 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeUndercover) ); 3135 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitUndercover) ); 3136 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitUndercover) ); 3137 SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolUndercover) ); 3138 SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolUndercover) ); 3139 3140 /* add string parameters */ 3141 heurdata->fixingalts = NULL; 3142 SCIP_CALL( SCIPaddStringParam(scip, "heuristics/" HEUR_NAME "/fixingalts", 3143 "prioritized sequence of fixing values used ('l'p relaxation, 'n'lp relaxation, 'i'ncumbent solution)", 3144 &heurdata->fixingalts, FALSE, DEFAULT_FIXINGALTS, NULL, NULL) ); 3145 3146 /* add longint parameters */ 3147 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes", 3148 "maximum number of nodes to regard in the subproblem", 3149 &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 3150 3151 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes", 3152 "minimum number of nodes required to start the subproblem", 3153 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 3154 3155 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs", 3156 "number of nodes added to the contingent of the total nodes", 3157 &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 3158 3159 /* add real parameters */ 3160 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/conflictweight", 3161 "weight for conflict score in fixing order", 3162 &heurdata->conflictweight, TRUE, DEFAULT_CONFLICTWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) ); 3163 3164 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/cutoffweight", 3165 "weight for cutoff score in fixing order", 3166 &heurdata->cutoffweight, TRUE, DEFAULT_CUTOFFWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 3167 3168 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/inferenceweight", 3169 "weight for inference score in fixing order", 3170 &heurdata->inferenceweight, TRUE, DEFAULT_INFERENCEWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) ); 3171 3172 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxcoversizevars", 3173 "maximum coversize (as fraction of total number of variables)", 3174 &heurdata->maxcoversizevars, TRUE, DEFAULT_MAXCOVERSIZEVARS, 0.0, 1.0, NULL, NULL) ); 3175 3176 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxcoversizeconss", 3177 "maximum coversize (as ratio to the percentage of non-affected constraints)", 3178 &heurdata->maxcoversizeconss, TRUE, DEFAULT_MAXCOVERSIZECONSS, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 3179 3180 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/mincoveredrel", 3181 "minimum percentage of nonlinear constraints in the original problem", 3182 &heurdata->mincoveredrel, TRUE, DEFAULT_MINCOVEREDREL, 0.0, 1.0, NULL, NULL) ); 3183 3184 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove", 3185 "factor by which the heuristic should at least improve the incumbent", 3186 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, -1.0, 1.0, NULL, NULL) ); 3187 3188 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot", 3189 "contingent of sub problem nodes in relation to the number of nodes of the original problem", 3190 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) ); 3191 3192 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/recoverdiv", 3193 "fraction of covering variables in the last cover which need to change their value when recovering", 3194 &heurdata->recoverdiv, TRUE, DEFAULT_RECOVERDIV, 0.0, 1.0, NULL, NULL) ); 3195 3196 /* add int parameters */ 3197 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/mincoveredabs", 3198 "minimum number of nonlinear constraints in the original problem", 3199 &heurdata->mincoveredabs, TRUE, DEFAULT_MINCOVEREDABS, 0, INT_MAX, NULL, NULL) ); 3200 3201 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxbacktracks", 3202 "maximum number of backtracks in fix-and-propagate", 3203 &heurdata->maxbacktracks, TRUE, DEFAULT_MAXBACKTRACKS, 0, INT_MAX, NULL, NULL) ); 3204 3205 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxrecovers", 3206 "maximum number of recoverings", 3207 &heurdata->maxrecovers, TRUE, DEFAULT_MAXRECOVERS, 0, INT_MAX, NULL, NULL) ); 3208 3209 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxreorders", 3210 "maximum number of reorderings of the fixing order", 3211 &heurdata->maxreorders, TRUE, DEFAULT_MAXREORDERS, 0, INT_MAX, NULL, NULL) ); 3212 3213 /* add char parameters */ 3214 SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/coveringobj", 3215 "objective function of the covering problem (influenced nonlinear 'c'onstraints/'t'erms, 'd'omain size, 'l'ocks, 'm'in of up/down locks, 'u'nit penalties)", 3216 &heurdata->coveringobj, TRUE, DEFAULT_COVERINGOBJ, COVERINGOBJS, NULL, NULL) ); 3217 3218 SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/fixingorder", 3219 "order in which variables should be fixed (increasing 'C'onflict score, decreasing 'c'onflict score, increasing 'V'ariable index, decreasing 'v'ariable index", 3220 &heurdata->fixingorder, TRUE, DEFAULT_FIXINGORDER, FIXINGORDERS, NULL, NULL) ); 3221 3222 /* add bool parameters */ 3223 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/beforecuts", 3224 "should the heuristic be called at root node before cut separation?", 3225 &heurdata->beforecuts, TRUE, DEFAULT_BEFORECUTS, NULL, NULL) ); 3226 3227 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/fixintfirst", 3228 "should integer variables in the cover be fixed first?", 3229 &heurdata->fixintfirst, TRUE, DEFAULT_FIXINTFIRST, NULL, NULL) ); 3230 3231 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/locksrounding", 3232 "shall LP values for integer vars be rounded according to locks?", 3233 &heurdata->locksrounding, TRUE, DEFAULT_LOCKSROUNDING, NULL, NULL) ); 3234 3235 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlyconvexify", 3236 "should we only fix variables in order to obtain a convex problem?", 3237 &heurdata->onlyconvexify, FALSE, DEFAULT_ONLYCONVEXIFY, NULL, NULL) ); 3238 3239 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/postnlp", 3240 "should the NLP heuristic be called to polish a feasible solution?", 3241 &heurdata->postnlp, FALSE, DEFAULT_POSTNLP, NULL, NULL) ); 3242 3243 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/coverand", 3244 "should and constraints be covered (or just copied)?", 3245 &heurdata->coverand, TRUE, DEFAULT_COVERAND, NULL, NULL) ); 3246 3247 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/coverbd", 3248 "should bounddisjunction constraints be covered (or just copied)?", 3249 &heurdata->coverbd, TRUE, DEFAULT_COVERBD, NULL, NULL) ); 3250 3251 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/coverind", 3252 "should indicator constraints be covered (or just copied)?", 3253 &heurdata->coverind, TRUE, DEFAULT_COVERIND, NULL, NULL) ); 3254 3255 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/covernl", 3256 "should nonlinear constraints be covered (or just copied)?", 3257 &heurdata->covernl, TRUE, DEFAULT_COVERNL, NULL, NULL) ); 3258 3259 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts", 3260 "should all active cuts from cutpool be copied to constraints in subproblem?", 3261 &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) ); 3262 3263 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/reusecover", 3264 "shall the cover be reused if a conflict was added after an infeasible subproblem?", 3265 &heurdata->reusecover, TRUE, DEFAULT_REUSECOVER, NULL, NULL) ); 3266 3267 return SCIP_OKAY; 3268 } 3269 3270 /** create and solve covering problem */ 3271 static 3272 SCIP_RETCODE computeCoverUndercover( 3273 SCIP* scip, /**< SCIP data structure */ 3274 SCIP* coveringscip, /**< SCIP instance for covering problem */ 3275 int* coversize, /**< buffer for the size of the computed cover */ 3276 SCIP_VAR** cover, /**< pointer to store the variables (of the original SCIP) in the computed cover 3277 * (should be ready to hold SCIPgetNVars(scip) entries) */ 3278 SCIP_Real timelimit, /**< time limit */ 3279 SCIP_Real memorylimit, /**< memory limit */ 3280 SCIP_Real objlimit, /**< objective limit: upper bound on coversize */ 3281 SCIP_Bool globalbounds, /**< should global bounds on variables be used instead of local bounds at focus node? */ 3282 SCIP_Bool onlyconvexify, /**< should we only fix/dom.red. variables creating nonconvexity? */ 3283 SCIP_Bool coverand, /**< should and constraints be covered (or just copied)? */ 3284 SCIP_Bool coverbd, /**< should bounddisjunction constraints be covered (or just copied)? */ 3285 SCIP_Bool coverind, /**< should indicator constraints be covered (or just copied)? */ 3286 SCIP_Bool covernl, /**< should nonlinear constraints be covered (or just copied)? */ 3287 char coveringobj, /**< objective function of the covering problem ('b'ranching status, 3288 * influenced nonlinear 'c'onstraints/'t'erms, 'd'omain size, 'l'ocks, 3289 * 'm'in of up/down locks, 'u'nit penalties, constraint 'v'iolation) */ 3290 SCIP_Bool* success /**< feasible cover found? */ 3291 ) 3292 { 3293 SCIP_VAR** coveringvars; /* covering variables */ 3294 SCIP_VAR** vars; /* original variables */ 3295 int* coverinds; /* indices of variables in the cover */ 3296 int nvars; /* number of original variables */ 3297 int i; 3298 3299 assert(scip != NULL); 3300 assert(coveringscip != NULL); 3301 3302 SCIP_CALL( SCIPincludeDefaultPlugins(coveringscip) ); 3303 3304 /* allocate memory for variables of the covering problem */ 3305 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL ) ); 3306 SCIP_CALL( SCIPallocBufferArray(scip, &coveringvars, nvars) ); 3307 SCIP_CALL( SCIPallocBufferArray(scip, &coverinds, nvars) ); 3308 3309 SCIP_CALL( createCoveringProblem(scip, coveringscip, coveringvars, globalbounds, onlyconvexify, 3310 coverand, coverbd, coverind, covernl, coveringobj, success) ); 3311 3312 if( *success ) 3313 { 3314 /* solve covering problem */ 3315 SCIPdebugMsg(scip, "solving covering problem\n\n"); 3316 3317 SCIP_CALL( solveCoveringProblem(coveringscip, nvars, coveringvars, coversize, coverinds, 3318 timelimit, memorylimit + (SCIPgetMemExternEstim(coveringscip)+SCIPgetMemUsed(coveringscip))/1048576.0, objlimit, success) ); 3319 3320 if( *success ) 3321 { 3322 assert(*coversize >= 0); 3323 assert(*coversize <= nvars); 3324 3325 /* return original variables in the cover */ 3326 for( i = *coversize-1; i >= 0; i-- ) 3327 { 3328 assert(coverinds[i] >= 0); 3329 assert(coverinds[i] < nvars); 3330 cover[i] = vars[coverinds[i]]; 3331 } 3332 } 3333 } 3334 else 3335 { 3336 SCIPdebugMsg(scip, "failure: covering problem could not be created\n"); 3337 } 3338 3339 /* free covering problem */ 3340 for( i = nvars-1; i >= 0; i-- ) 3341 { 3342 if( coveringvars[i] == NULL ) 3343 continue; 3344 SCIP_CALL( SCIPreleaseVar(coveringscip, &coveringvars[i]) ); 3345 } 3346 SCIPfreeBufferArray(scip, &coverinds); 3347 SCIPfreeBufferArray(scip, &coveringvars); 3348 3349 return SCIP_OKAY; 3350 } 3351 3352 /** computes a minimal set of covering variables */ 3353 SCIP_RETCODE SCIPcomputeCoverUndercover( 3354 SCIP* scip, /**< SCIP data structure */ 3355 int* coversize, /**< buffer for the size of the computed cover */ 3356 SCIP_VAR** cover, /**< pointer to store the variables (of the original SCIP) in the computed cover 3357 * (should be ready to hold SCIPgetNVars(scip) entries) */ 3358 SCIP_Real timelimit, /**< time limit */ 3359 SCIP_Real memorylimit, /**< memory limit */ 3360 SCIP_Real objlimit, /**< objective limit: upper bound on coversize */ 3361 SCIP_Bool globalbounds, /**< should global bounds on variables be used instead of local bounds at focus node? */ 3362 SCIP_Bool onlyconvexify, /**< should we only fix/dom.red. variables creating nonconvexity? */ 3363 SCIP_Bool coverand, /**< should and constraints be covered (or just copied)? */ 3364 SCIP_Bool coverbd, /**< should bounddisjunction constraints be covered (or just copied)? */ 3365 SCIP_Bool coverind, /**< should indicator constraints be covered (or just copied)? */ 3366 SCIP_Bool covernl, /**< should nonlinear constraints be covered (or just copied)? */ 3367 char coveringobj, /**< objective function of the covering problem ('b'ranching status, 3368 * influenced nonlinear 'c'onstraints/'t'erms, 'd'omain size, 'l'ocks, 3369 * 'm'in of up/down locks, 'u'nit penalties, constraint 'v'iolation) */ 3370 SCIP_Bool* success /**< feasible cover found? */ 3371 ) 3372 { 3373 SCIP* coveringscip; /* SCIP instance for covering problem */ 3374 SCIP_RETCODE retcode; 3375 3376 assert(scip != NULL); 3377 assert(coversize != NULL); 3378 assert(success != NULL); 3379 3380 *success = FALSE; 3381 3382 /* create covering problem */ 3383 SCIP_CALL( SCIPcreate(&coveringscip) ); 3384 3385 retcode = computeCoverUndercover(scip, coveringscip, coversize, cover, 3386 timelimit, memorylimit, objlimit, 3387 globalbounds, onlyconvexify, coverand, coverbd, coverind, covernl, 3388 coveringobj, success); 3389 3390 /* free the covering problem scip instance before reacting on potential errors */ 3391 SCIP_CALL( SCIPfree(&coveringscip) ); 3392 3393 SCIP_CALL( retcode ); 3394 3395 return SCIP_OKAY; 3396 } 3397