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_fixandinfer.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief fix-and-infer primal heuristic 28 * @author Tobias Achterberg 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include "scip/heur_fixandinfer.h" 34 #include "scip/pub_heur.h" 35 #include "scip/pub_message.h" 36 #include "scip/pub_var.h" 37 #include "scip/scip_branch.h" 38 #include "scip/scip_general.h" 39 #include "scip/scip_heur.h" 40 #include "scip/scip_mem.h" 41 #include "scip/scip_message.h" 42 #include "scip/scip_numerics.h" 43 #include "scip/scip_param.h" 44 #include "scip/scip_prob.h" 45 #include "scip/scip_probing.h" 46 #include "scip/scip_sol.h" 47 #include "scip/scip_tree.h" 48 #include "scip/scip_var.h" 49 #include <string.h> 50 51 #define HEUR_NAME "fixandinfer" 52 #define HEUR_DESC "iteratively fixes variables and propagates inferences" 53 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_PROP 54 #define HEUR_PRIORITY -500000 55 #define HEUR_FREQ -1 /* at the moment, the heuristic seems to be useless */ 56 #define HEUR_FREQOFS 0 57 #define HEUR_MAXDEPTH -1 58 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE 59 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */ 60 61 #define MAXDIVEDEPTH 100 62 63 64 /* 65 * Default parameter settings 66 */ 67 68 #define DEFAULT_PROPROUNDS 0 /**< maximal number of propagation rounds in probing subproblems */ 69 #define DEFAULT_MINFIXINGS 100 /**< minimal number of fixings to apply before dive may be aborted */ 70 71 72 /* 73 * Data structures 74 */ 75 76 /** primal heuristic data */ 77 struct SCIP_HeurData 78 { 79 int proprounds; /**< maximal number of propagation rounds in probing subproblems */ 80 int minfixings; /**< minimal number of fixings to apply before dive may be aborted */ 81 }; 82 83 84 /* 85 * Local methods 86 */ 87 88 /** selects a variable and fixes it to its current pseudo solution value */ 89 static 90 SCIP_RETCODE fixVariable( 91 SCIP* scip, /**< SCIP data structure */ 92 SCIP_VAR** pseudocands, /**< array of unfixed variables */ 93 int npseudocands, /**< number of unfixed variables */ 94 SCIP_Real large /**< large value to be used instead of infinity */ 95 ) 96 { 97 SCIP_VAR* var; 98 SCIP_Real bestscore; 99 SCIP_Real score; 100 SCIP_Real solval; 101 int bestcand; 102 int ncands; 103 int c; 104 105 assert(pseudocands != NULL); 106 assert(npseudocands > 0); 107 108 /* if existing, choose one of the highest priority binary variables; if no high priority binary variables 109 * exist, choose a variable among all unfixed integral variables 110 */ 111 ncands = SCIPgetNPrioPseudoBranchBins(scip); 112 if( ncands == 0 ) 113 ncands = npseudocands; 114 115 /* select variable to tighten the domain for */ 116 bestscore = -SCIPinfinity(scip); 117 bestcand = -1; 118 for( c = 0; c < ncands; ++c ) 119 { 120 score = SCIPgetVarAvgInferenceScore(scip, pseudocands[c]); 121 if( score > bestscore ) 122 { 123 bestscore = score; 124 bestcand = c; 125 } 126 } 127 assert(bestcand != -1); 128 129 /* fix variable to its current pseudo solution value */ 130 var = pseudocands[bestcand]; 131 solval = SCIPgetVarSol(scip, var); 132 133 /* adapt solution value if it is infinite */ 134 if( SCIPisInfinity(scip, solval) ) 135 { 136 SCIP_Real lb; 137 assert(SCIPisInfinity(scip, SCIPvarGetUbLocal(var))); 138 lb = SCIPvarGetLbLocal(var); 139 140 /* adapt fixing value by changing it to a large value */ 141 if( SCIPisInfinity(scip, -lb) ) 142 solval = SCIPceil(scip, large); 143 else if( !SCIPisInfinity(scip, SCIPceil(scip, lb+large)) ) 144 solval = SCIPceil(scip, lb+large); 145 } 146 else if( SCIPisInfinity(scip, -solval) ) 147 { 148 SCIP_Real ub; 149 assert(SCIPisInfinity(scip, -SCIPvarGetLbLocal(var))); 150 ub = SCIPvarGetUbLocal(var); 151 152 /* adapt fixing value by changing it to a large negative value */ 153 if( SCIPisInfinity(scip, ub) ) 154 solval = SCIPfloor(scip, -large); 155 else if( !SCIPisInfinity(scip, -SCIPfloor(scip, ub-large)) ) 156 solval = SCIPfloor(scip, ub-large); 157 } 158 159 assert(SCIPisFeasIntegral(scip, solval)); /* in probing, we always have the pseudo solution */ 160 SCIPdebugMsg(scip, " -> fixed variable <%s>[%g,%g] = %g (%d candidates left)\n", 161 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), solval, npseudocands - 1); 162 SCIP_CALL( SCIPfixVarProbing(scip, var, solval) ); 163 164 return SCIP_OKAY; 165 } 166 167 168 /* 169 * Callback methods of primal heuristic 170 */ 171 172 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 173 static 174 SCIP_DECL_HEURCOPY(heurCopyFixandinfer) 175 { /*lint --e{715}*/ 176 assert(scip != NULL); 177 assert(heur != NULL); 178 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 179 180 /* call inclusion method of primal heuristic */ 181 SCIP_CALL( SCIPincludeHeurFixandinfer(scip) ); 182 183 return SCIP_OKAY; 184 } 185 186 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 187 static 188 SCIP_DECL_HEURFREE(heurFreeFixandinfer) /*lint --e{715}*/ 189 { /*lint --e{715}*/ 190 SCIP_HEURDATA* heurdata; 191 192 /* free heuristic data */ 193 heurdata = SCIPheurGetData(heur); 194 assert(heurdata != NULL); 195 SCIPfreeBlockMemory(scip, &heurdata); 196 SCIPheurSetData(heur, NULL); 197 198 return SCIP_OKAY; 199 } 200 201 202 /** execution method of primal heuristic */ 203 static 204 SCIP_DECL_HEUREXEC(heurExecFixandinfer) 205 { /*lint --e{715}*/ 206 SCIP_HEURDATA* heurdata; 207 SCIP_VAR** cands; 208 int ncands; 209 int startncands; 210 int divedepth; 211 SCIP_Bool cutoff; 212 SCIP_Real large; 213 214 *result = SCIP_DIDNOTRUN; 215 216 /* do not call heuristic of node was already detected to be infeasible */ 217 if( nodeinfeasible ) 218 return SCIP_OKAY; 219 220 /* we cannot run on problems with continuous variables */ 221 if( SCIPgetNContVars(scip) > 0 ) 222 return SCIP_OKAY; 223 224 /* get unfixed variables */ 225 SCIP_CALL( SCIPgetPseudoBranchCands(scip, &cands, &ncands, NULL) ); 226 if( ncands == 0 ) 227 return SCIP_OKAY; 228 229 /* get heuristic data */ 230 heurdata = SCIPheurGetData(heur); 231 assert(heurdata != NULL); 232 233 /* fix variables and propagate inferences as long as the problem is still feasible and there are 234 * unfixed integral variables 235 */ 236 cutoff = FALSE; 237 divedepth = 0; 238 startncands = ncands; 239 240 /* start probing */ 241 SCIP_CALL( SCIPstartProbing(scip) ); 242 243 if( SCIP_MAXTREEDEPTH <= SCIPgetDepth(scip) ) 244 { 245 SCIP_CALL( SCIPendProbing(scip) ); 246 return SCIP_OKAY; 247 } 248 249 SCIPdebugMsg(scip, "starting fix-and-infer heuristic with %d unfixed integral variables\n", ncands); 250 251 *result = SCIP_DIDNOTFIND; 252 253 /* create next probing node */ 254 SCIP_CALL( SCIPnewProbingNode(scip) ); 255 256 /* determine large value to set variables to */ 257 large = SCIPinfinity(scip); 258 if( !SCIPisInfinity(scip, 0.1 / SCIPfeastol(scip)) ) 259 large = 0.1 / SCIPfeastol(scip); 260 261 while( !cutoff && ncands > 0 262 && (divedepth < heurdata->minfixings || (startncands - ncands) * 2 * MAXDIVEDEPTH >= startncands * divedepth) 263 && !SCIPisStopped(scip) ) 264 { 265 divedepth++; 266 267 /* fix next variable */ 268 SCIP_CALL( fixVariable(scip, cands, ncands, large) ); 269 270 /* propagate the fixing */ 271 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->proprounds, &cutoff, NULL) ); 272 273 /* get remaining unfixed variables */ 274 if( !cutoff ) 275 { 276 SCIP_CALL( SCIPgetPseudoBranchCands(scip, &cands, &ncands, NULL) ); 277 } 278 } 279 280 /* check, if we are still feasible */ 281 if( cutoff ) 282 { 283 SCIPdebugMsg(scip, "propagation detected a cutoff\n"); 284 } 285 else if( ncands == 0 ) 286 { 287 SCIP_Bool success; 288 289 success = FALSE; 290 291 /* try to add solution to SCIP */ 292 SCIP_CALL( SCIPtryCurrentSol(scip, heur, FALSE, FALSE, FALSE, TRUE, &success) ); 293 294 if( success ) 295 { 296 SCIPdebugMsg(scip, "found primal feasible solution\n"); 297 *result = SCIP_FOUNDSOL; 298 } 299 else 300 { 301 SCIPdebugMsg(scip, "primal solution was rejected\n"); 302 } 303 } 304 else 305 { 306 SCIPdebugMsg(scip, "probing was aborted (probing depth: %d, fixed: %d/%d)", divedepth, startncands - ncands, startncands); 307 } 308 309 /* end probing */ 310 SCIP_CALL( SCIPendProbing(scip) ); 311 312 return SCIP_OKAY; 313 } 314 315 316 /* 317 * primal heuristic specific interface methods 318 */ 319 320 /** creates the fix-and-infer primal heuristic and includes it in SCIP */ 321 SCIP_RETCODE SCIPincludeHeurFixandinfer( 322 SCIP* scip /**< SCIP data structure */ 323 ) 324 { 325 SCIP_HEURDATA* heurdata; 326 SCIP_HEUR* heur; 327 328 /* create Fixandinfer primal heuristic data */ 329 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 330 331 /* include primal heuristic */ 332 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 333 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 334 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecFixandinfer, heurdata) ); 335 336 assert(heur != NULL); 337 338 /* set non-NULL pointers to callback methods */ 339 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyFixandinfer) ); 340 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeFixandinfer) ); 341 342 /* fixandinfer heuristic parameters */ 343 SCIP_CALL( SCIPaddIntParam(scip, 344 "heuristics/fixandinfer/proprounds", 345 "maximal number of propagation rounds in probing subproblems (-1: no limit, 0: auto)", 346 &heurdata->proprounds, TRUE, DEFAULT_PROPROUNDS, -1, INT_MAX, NULL, NULL) ); 347 SCIP_CALL( SCIPaddIntParam(scip, 348 "heuristics/fixandinfer/minfixings", 349 "minimal number of fixings to apply before dive may be aborted", 350 &heurdata->minfixings, TRUE, DEFAULT_MINFIXINGS, 0, INT_MAX, NULL, NULL) ); 351 352 return SCIP_OKAY; 353 } 354