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_bound.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief heuristic which fixes all integer variables to a bound (lower/upper) and solves the remaining LP 28 * @author Gerald Gamrath 29 * 30 */ 31 32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 33 34 #include "scip/heur_bound.h" 35 #include "scip/pub_heur.h" 36 #include "scip/pub_message.h" 37 #include "scip/pub_tree.h" 38 #include "scip/pub_var.h" 39 #include "scip/scip_branch.h" 40 #include "scip/scip_general.h" 41 #include "scip/scip_heur.h" 42 #include "scip/scip_lp.h" 43 #include "scip/scip_mem.h" 44 #include "scip/scip_message.h" 45 #include "scip/scip_numerics.h" 46 #include "scip/scip_param.h" 47 #include "scip/scip_prob.h" 48 #include "scip/scip_probing.h" 49 #include "scip/scip_sol.h" 50 #include "scip/scip_solvingstats.h" 51 #include "scip/scip_timing.h" 52 #include "scip/scip_tree.h" 53 #include <string.h> 54 55 #ifdef SCIP_STATISTIC 56 #include "scip/clock.h" 57 #endif 58 59 #define HEUR_NAME "bound" 60 #define HEUR_DESC "heuristic which fixes all integer variables to a bound and solves the remaining LP" 61 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_PROP 62 #define HEUR_PRIORITY -1107000 63 #define HEUR_FREQ -1 64 #define HEUR_FREQOFS 0 65 #define HEUR_MAXDEPTH -1 66 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE 67 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */ 68 69 #define DEFAULT_ONLYWITHOUTSOL TRUE /**< Should heuristic only be executed if no primal solution was found, yet? */ 70 #define DEFAULT_MAXPROPROUNDS 0 /* maximum number of propagation rounds during probing */ 71 #define DEFAULT_BOUND 'l' /**< to which bound should integer variables be fixed? */ 72 73 74 /* 75 * Data structures 76 */ 77 78 /** primal heuristic data */ 79 struct SCIP_HeurData 80 { 81 SCIP_Bool onlywithoutsol; /**< Should heuristic only be executed if no primal solution was found, yet? */ 82 int maxproprounds; /**< maximum number of propagation rounds during probing */ 83 char bound; /**< to which bound should integer variables be fixed? */ 84 }; 85 86 /* 87 * Local methods 88 */ 89 90 /** main procedure of the bound heuristic */ 91 static 92 SCIP_RETCODE applyBoundHeur( 93 SCIP* scip, /**< original SCIP data structure */ 94 SCIP_HEUR* heur, /**< heuristic */ 95 SCIP_HEURDATA* heurdata, /**< heuristic data structure */ 96 SCIP_Bool lower, /**< should integer variables be fixed to their lower bound? */ 97 SCIP_RESULT* result /**< pointer to store the result */ 98 ) 99 { 100 SCIP_VAR** vars; 101 SCIP_VAR* var; 102 SCIP_Bool infeasible = FALSE; 103 int maxproprounds; 104 int nbinvars; 105 int nintvars; 106 int nvars; 107 int v; 108 109 /* get variable data of original problem */ 110 SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) ); 111 112 maxproprounds = heurdata->maxproprounds; 113 if( maxproprounds == -2 ) 114 maxproprounds = 0; 115 116 /* only look at binary and integer variables */ 117 nvars = nbinvars + nintvars; 118 119 /* stop if we would have infinite fixings */ 120 if( lower ) 121 { 122 for( v = 0; v < nvars; ++v ) 123 { 124 if( SCIPisInfinity(scip, -SCIPvarGetLbLocal(vars[v])) ) 125 return SCIP_OKAY; 126 } 127 } 128 else 129 { 130 for( v = 0; v < nvars; ++v ) 131 { 132 if( SCIPisInfinity(scip, SCIPvarGetUbLocal(vars[v])) ) 133 return SCIP_OKAY; 134 } 135 } 136 137 /* start probing */ 138 SCIP_CALL( SCIPstartProbing(scip) ); 139 140 for( v = 0; v < nvars; ++v ) 141 { 142 var = vars[v]; 143 144 assert(SCIPvarGetType(var) < SCIP_VARTYPE_IMPLINT); 145 146 /* skip variables which are already fixed */ 147 if( SCIPvarGetLbLocal(var) + 0.5 > SCIPvarGetUbLocal(var) ) 148 continue; 149 150 /* fix variable to lower bound */ 151 if( lower ) 152 { 153 SCIP_CALL( SCIPfixVarProbing(scip, var, SCIPvarGetLbLocal(var)) ); 154 SCIPdebugMsg(scip, "fixing %d: variable <%s> to lower bound <%g> (%d pseudo cands)\n", 155 v, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPgetNPseudoBranchCands(scip)); 156 } 157 /* fix variable to upper bound */ 158 else 159 { 160 SCIP_CALL( SCIPfixVarProbing(scip, var, SCIPvarGetUbLocal(var)) ); 161 SCIPdebugMsg(scip, "fixing %d: variable <%s> to upper bound <%g> (%d pseudo cands)\n", 162 v, SCIPvarGetName(var), SCIPvarGetUbLocal(var), SCIPgetNPseudoBranchCands(scip)); 163 } 164 165 /* propagate fixings */ 166 if( heurdata->maxproprounds != 0 ) 167 { 168 SCIP_CALL( SCIPpropagateProbing(scip, maxproprounds, &infeasible, NULL) ); 169 } 170 171 /* try to repair probing */ 172 if( infeasible ) 173 { 174 #if 0 175 SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip) - 1) ); 176 177 /* fix the last variable, which was fixed the reverse bound */ 178 SCIP_CALL( SCIPfixVarProbing(scip, var, SCIPvarGetUbLocal(var)) ); 179 180 /* propagate fixings */ 181 SCIP_CALL( SCIPpropagateProbing(scip, maxproprounds, &infeasible, NULL) ); 182 183 SCIPdebugMsg(scip, "backtracking ended with %sfeasible problem\n", (infeasible ? "in" : "")); 184 185 if( infeasible ) 186 #endif 187 break; 188 } 189 } 190 191 SCIPdebugMsg(scip, "probing ended with %sfeasible problem\n", infeasible ? "in" : ""); 192 193 /*************************** Probing LP Solving ***************************/ 194 195 /* solve lp only if the problem is still feasible */ 196 if( !infeasible ) 197 { 198 char strbuf[SCIP_MAXSTRLEN]; 199 SCIP_LPSOLSTAT lpstatus; 200 SCIP_Bool lperror; 201 int ncols; 202 203 /* print message if relatively large LP is solved from scratch, since this could lead to a longer period during 204 * which the user sees no output; more detailed probing stats only in debug mode */ 205 ncols = SCIPgetNLPCols(scip); 206 if( !SCIPisLPSolBasic(scip) && ncols > 1000 ) 207 { 208 int nunfixedcols = SCIPgetNUnfixedLPCols(scip); 209 210 if( nunfixedcols > 0.5 * ncols ) 211 { 212 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, 213 "Heuristic " HEUR_NAME " solving LP from scratch with %.1f %% unfixed columns (%d of %d) ...\n", 214 100.0 * (nunfixedcols / (SCIP_Real)ncols), nunfixedcols, ncols); 215 } 216 } 217 SCIPdebugMsg(scip, "Heuristic " HEUR_NAME " probing LP: %s\n", 218 SCIPsnprintfProbingStats(scip, strbuf, SCIP_MAXSTRLEN)); 219 220 /* solve LP; errors in the LP solver should not kill the overall solving process, if the LP is just needed for a 221 * heuristic. hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, 222 * SCIP will stop. 223 */ 224 SCIPdebugMsg(scip, "starting solving bound-heur LP at time %g, LP iterations: %" SCIP_LONGINT_FORMAT "\n", 225 SCIPgetSolvingTime(scip), SCIPgetNLPIterations(scip)); 226 #ifdef NDEBUG 227 { 228 SCIP_Bool retstat; 229 retstat = SCIPsolveProbingLP(scip, -1, &lperror, NULL); 230 if( retstat != SCIP_OKAY ) 231 { 232 SCIPwarningMessage(scip, "Error while solving LP in bound heuristic; LP solve terminated with code <%d>\n", 233 retstat); 234 } 235 } 236 #else 237 SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, NULL) ); 238 #endif 239 SCIPdebugMsg(scip, "ending solving bound-heur LP at time %g\n", SCIPgetSolvingTime(scip)); 240 241 lpstatus = SCIPgetLPSolstat(scip); 242 243 SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip)); 244 SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, lpstatus); 245 246 /* check if this is a feasible solution */ 247 if( lpstatus == SCIP_LPSOLSTAT_OPTIMAL && !lperror ) 248 { 249 SCIP_SOL* newsol; 250 SCIP_Bool stored; 251 SCIP_Bool success; 252 253 /* create temporary solution */ 254 SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) ); 255 256 /* copy the current LP solution to the working solution */ 257 SCIP_CALL( SCIPlinkLPSol(scip, newsol) ); 258 259 SCIP_CALL( SCIProundSol(scip, newsol, &success) ); 260 261 if( success ) 262 { 263 SCIPdebugMsg(scip, "bound heuristic found roundable primal solution: obj=%g\n", 264 SCIPgetSolOrigObj(scip, newsol)); 265 266 /* check solution for feasibility, and add it to solution store if possible. 267 * Neither integrality nor feasibility of LP rows have to be checked, because they 268 * are guaranteed by the heuristic at this stage. 269 */ 270 #ifdef SCIP_DEBUG 271 SCIP_CALL( SCIPtrySol(scip, newsol, TRUE, TRUE, TRUE, TRUE, TRUE, &stored) ); 272 #else 273 SCIP_CALL( SCIPtrySol(scip, newsol, FALSE, FALSE, TRUE, FALSE, FALSE, &stored) ); 274 #endif 275 276 if( stored ) 277 { 278 SCIPdebugMsg(scip, "found feasible solution:\n"); 279 *result = SCIP_FOUNDSOL; 280 } 281 } 282 283 /* free solution */ 284 SCIP_CALL( SCIPfreeSol(scip, &newsol) ); 285 } 286 } 287 288 /* exit probing mode */ 289 SCIP_CALL( SCIPendProbing(scip) ); 290 291 return SCIP_OKAY; 292 } 293 294 295 /* 296 * Callback methods of primal heuristic 297 */ 298 299 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 300 static 301 SCIP_DECL_HEURCOPY(heurCopyBound) 302 { /*lint --e{715}*/ 303 assert(scip != NULL); 304 assert(heur != NULL); 305 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 306 307 /* call inclusion method of heuristic */ 308 SCIP_CALL( SCIPincludeHeurBound(scip) ); 309 310 return SCIP_OKAY; 311 } 312 313 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 314 static 315 SCIP_DECL_HEURFREE(heurFreeBound) 316 { /*lint --e{715}*/ 317 SCIP_HEURDATA* heurdata; 318 319 /* free heuristic data */ 320 heurdata = SCIPheurGetData(heur); 321 322 SCIPfreeBlockMemory(scip, &heurdata); 323 SCIPheurSetData(heur, NULL); 324 325 return SCIP_OKAY; 326 } 327 328 /** execution method of primal heuristic */ 329 static 330 SCIP_DECL_HEUREXEC(heurExecBound) 331 { /*lint --e{715}*/ 332 SCIP_HEURDATA* heurdata; 333 334 assert(heur != NULL); 335 assert(scip != NULL); 336 assert(result != NULL); 337 338 *result = SCIP_DIDNOTRUN; 339 340 if( SCIPgetNPseudoBranchCands(scip) == 0 ) 341 return SCIP_OKAY; 342 343 if( !SCIPhasCurrentNodeLP(scip) ) 344 return SCIP_OKAY; 345 346 heurdata = SCIPheurGetData(heur); 347 assert(heurdata != NULL); 348 349 *result = SCIP_DIDNOTFIND; 350 351 if( SCIPisStopped(scip) ) 352 return SCIP_OKAY; 353 354 /* stop execution method if there is already a primal feasible solution at hand */ 355 if( SCIPgetBestSol(scip) != NULL && heurdata->onlywithoutsol ) 356 return SCIP_OKAY; 357 358 SCIPdebugMsg(scip, "apply bound heuristic at node %lld\n", 359 SCIPnodeGetNumber(SCIPgetCurrentNode(scip))); 360 361 if( !SCIPisLPConstructed(scip) ) 362 { 363 SCIP_Bool cutoff; 364 365 SCIP_CALL( SCIPconstructLP(scip, &cutoff) ); 366 367 /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */ 368 if( cutoff ) 369 { 370 SCIP_CALL( SCIPcutoffNode(scip, SCIPgetCurrentNode(scip)) ); 371 return SCIP_OKAY; 372 } 373 374 SCIP_CALL( SCIPflushLP(scip) ); 375 } 376 377 if( heurdata->bound == 'l' || heurdata->bound == 'b' ) 378 { 379 SCIP_CALL(applyBoundHeur(scip, heur, heurdata, TRUE, result) ); 380 } 381 if( heurdata->bound == 'u' || heurdata->bound == 'b' ) 382 { 383 SCIP_CALL(applyBoundHeur(scip, heur, heurdata, FALSE, result) ); 384 } 385 386 return SCIP_OKAY; 387 } 388 389 /* 390 * primal heuristic specific interface methods 391 */ 392 393 /** creates the bound primal heuristic and includes it in SCIP */ 394 SCIP_RETCODE SCIPincludeHeurBound( 395 SCIP* scip /**< SCIP data structure */ 396 ) 397 { 398 SCIP_HEURDATA* heurdata; 399 SCIP_HEUR* heur; 400 401 /* create bound primal heuristic data */ 402 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 403 404 /* include primal heuristic */ 405 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 406 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 407 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecBound, heurdata) ); 408 409 assert(heur != NULL); 410 411 /* set non-NULL pointers to callback methods */ 412 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyBound) ); 413 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeBound) ); 414 415 /* add bound heuristic parameters */ 416 417 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlywithoutsol", 418 "Should heuristic only be executed if no primal solution was found, yet?", 419 &heurdata->onlywithoutsol, TRUE, DEFAULT_ONLYWITHOUTSOL, NULL, NULL) ); 420 421 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxproprounds", 422 "maximum number of propagation rounds during probing (-1 infinity, -2 parameter settings)", 423 &heurdata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -1, INT_MAX/4, NULL, NULL) ); 424 425 SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/bound", 426 "to which bound should integer variables be fixed? ('l'ower, 'u'pper, or 'b'oth)", 427 &heurdata->bound, FALSE, DEFAULT_BOUND, "lub", NULL, NULL) ); 428 429 return SCIP_OKAY; 430 } 431