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_guideddiving.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief LP diving heuristic that chooses fixings in direction of incumbent solutions 28 * @author Tobias Achterberg 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include "scip/heur_guideddiving.h" 34 #include "scip/heuristics.h" 35 #include "scip/pub_heur.h" 36 #include "scip/pub_message.h" 37 #include "scip/pub_sol.h" 38 #include "scip/pub_var.h" 39 #include "scip/scip_heur.h" 40 #include "scip/scip_lp.h" 41 #include "scip/scip_mem.h" 42 #include "scip/scip_numerics.h" 43 #include "scip/scip_prob.h" 44 #include "scip/scip_sol.h" 45 #include <string.h> 46 47 #define HEUR_NAME "guideddiving" 48 #define HEUR_DESC "LP diving heuristic that chooses fixings in direction of incumbent solutions" 49 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING 50 #define HEUR_PRIORITY -1007000 51 #define HEUR_FREQ 10 52 #define HEUR_FREQOFS 7 53 #define HEUR_MAXDEPTH -1 54 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE 55 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */ 56 #define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY /**< bit mask that represents all supported dive types */ 57 #define DIVESET_ISPUBLIC TRUE /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */ 58 59 60 /* 61 * Default parameter settings 62 */ 63 64 #define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */ 65 #define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */ 66 #define DEFAULT_MAXLPITERQUOT 0.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */ 67 #define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */ 68 #define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) 69 * where diving is performed (0.0: no limit) */ 70 #define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) 71 * where diving is performed (0.0: no limit) */ 72 #define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */ 73 #define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 /**< percentage of immediate domain changes during probing to trigger LP resolve */ 74 #define DEFAULT_LPSOLVEFREQ 0 /**< LP solve frequency for diving heuristics */ 75 #define DEFAULT_ONLYLPBRANCHCANDS FALSE /**< should only LP branching candidates be considered instead of the slower but 76 * more general constraint handler diving variable selection? */ 77 #define DEFAULT_RANDSEED 127 /**< initial seed for random number generation */ 78 79 /* locally defined heuristic data */ 80 struct SCIP_HeurData 81 { 82 SCIP_SOL* sol; /**< working solution */ 83 }; 84 85 /* 86 * local methods 87 */ 88 89 /* 90 * Callback methods 91 */ 92 93 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 94 static 95 SCIP_DECL_HEURCOPY(heurCopyGuideddiving) 96 { /*lint --e{715}*/ 97 assert(scip != NULL); 98 assert(heur != NULL); 99 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 100 101 /* call inclusion method of primal heuristic */ 102 SCIP_CALL( SCIPincludeHeurGuideddiving(scip) ); 103 104 return SCIP_OKAY; 105 } 106 107 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 108 static 109 SCIP_DECL_HEURFREE(heurFreeGuideddiving) /*lint --e{715}*/ 110 { /*lint --e{715}*/ 111 SCIP_HEURDATA* heurdata; 112 113 assert(heur != NULL); 114 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 115 assert(scip != NULL); 116 117 /* free heuristic data */ 118 heurdata = SCIPheurGetData(heur); 119 assert(heurdata != NULL); 120 121 SCIPfreeBlockMemory(scip, &heurdata); 122 SCIPheurSetData(heur, NULL); 123 124 return SCIP_OKAY; 125 } 126 127 128 /** initialization method of primal heuristic (called after problem was transformed) */ 129 static 130 SCIP_DECL_HEURINIT(heurInitGuideddiving) /*lint --e{715}*/ 131 { /*lint --e{715}*/ 132 SCIP_HEURDATA* heurdata; 133 134 assert(heur != NULL); 135 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 136 137 /* get heuristic data */ 138 heurdata = SCIPheurGetData(heur); 139 assert(heurdata != NULL); 140 141 /* create working solution */ 142 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) ); 143 144 return SCIP_OKAY; 145 } 146 147 148 /** deinitialization method of primal heuristic (called before transformed problem is freed) */ 149 static 150 SCIP_DECL_HEUREXIT(heurExitGuideddiving) /*lint --e{715}*/ 151 { /*lint --e{715}*/ 152 SCIP_HEURDATA* heurdata; 153 154 assert(heur != NULL); 155 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 156 157 /* get heuristic data */ 158 heurdata = SCIPheurGetData(heur); 159 assert(heurdata != NULL); 160 161 /* free working solution */ 162 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) ); 163 164 return SCIP_OKAY; 165 } 166 167 168 /** execution method of primal heuristic */ 169 static 170 SCIP_DECL_HEUREXEC(heurExecGuideddiving) /*lint --e{715}*/ 171 { /*lint --e{715}*/ 172 SCIP_HEURDATA* heurdata; 173 SCIP_DIVESET* diveset; 174 175 assert(heur != NULL); 176 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 177 assert(scip != NULL); 178 assert(result != NULL); 179 assert(SCIPhasCurrentNodeLP(scip)); 180 181 *result = SCIP_DIDNOTRUN; 182 183 /* don't dive, if no feasible solutions exist */ 184 if( SCIPgetNSols(scip) == 0 ) 185 return SCIP_OKAY; 186 187 /* get best solution that should guide the search; if this solution lives in the original variable space, 188 * we cannot use it since it might violate the global bounds of the current problem 189 */ 190 if( SCIPsolIsOriginal(SCIPgetBestSol(scip)) ) 191 return SCIP_OKAY; 192 193 /* get heuristic's data */ 194 heurdata = SCIPheurGetData(heur); 195 assert(heurdata != NULL); 196 197 /* if there are no integer variables (note that, e.g., SOS1 variables may be present) */ 198 if ( SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) == 0 ) 199 return SCIP_OKAY; 200 201 assert(SCIPheurGetNDivesets(heur) > 0); 202 assert(SCIPheurGetDivesets(heur) != NULL); 203 diveset = SCIPheurGetDivesets(heur)[0]; 204 assert(diveset != NULL); 205 206 /* call generic diving algorithm */ 207 SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, -1L, -1, -1.0, SCIP_DIVECONTEXT_SINGLE) ); 208 209 return SCIP_OKAY; 210 } 211 212 /* callbacks for diving */ 213 214 /** calculate score and preferred rounding direction for the candidate variable; the best candidate maximizes the 215 * score 216 */ 217 static 218 SCIP_DECL_DIVESETGETSCORE(divesetGetScoreGuideddiving) 219 { 220 SCIP_SOL* bestsol; 221 SCIP_Real bestsolval; 222 SCIP_Real obj; 223 SCIP_Real objnorm; 224 SCIP_Real objgain; 225 226 bestsol = SCIPgetBestSol(scip); 227 assert(bestsol != NULL); 228 assert(!SCIPsolIsOriginal(bestsol)); 229 230 bestsolval = SCIPgetSolVal(scip, bestsol, cand); 231 232 /* variable should be rounded (guided) into the direction of its incumbent solution value */ 233 if( candsol < bestsolval ) 234 *roundup = TRUE; 235 else 236 *roundup = FALSE; 237 238 obj = SCIPvarGetObj(cand); 239 objnorm = SCIPgetObjNorm(scip); 240 241 /* divide by objective norm to normalize obj into [-1,1] */ 242 if( SCIPisPositive(scip, objnorm) ) 243 obj /= objnorm; 244 245 /* calculate objective gain and fractionality for the selected rounding direction */ 246 if( *roundup ) 247 { 248 candsfrac = 1.0 - candsfrac; 249 objgain = obj * candsfrac; 250 } 251 else 252 objgain = -obj * candsfrac; 253 254 assert(objgain >= -1.0 && objgain <= 1.0); 255 256 /* penalize too small fractions */ 257 if( candsfrac < 0.01 ) 258 candsfrac *= 0.1; 259 260 /* prefer decisions on binary variables */ 261 if( !SCIPvarIsBinary(cand) ) 262 candsfrac *= 0.1; 263 264 /* prefer variables which cannot be rounded by scoring their fractionality */ 265 if( !(SCIPvarMayRoundDown(cand) || SCIPvarMayRoundUp(cand)) ) 266 *score = -candsfrac; 267 else 268 *score = -2.0 - objgain; 269 270 return SCIP_OKAY; 271 } 272 273 /** callback to check preconditions for diving, e.g., if an incumbent solution is available */ 274 static 275 SCIP_DECL_DIVESETAVAILABLE(divesetAvailableGuideddiving) 276 { 277 /* don't dive with guided diving if no feasible solutions exists or 278 * if this solution lives in the original variable space, 279 * because it might violate the global bounds of the current problem 280 */ 281 if( SCIPgetNSols(scip) == 0 || SCIPsolIsOriginal(SCIPgetBestSol(scip))) 282 *available = FALSE; 283 else 284 *available = TRUE; 285 286 return SCIP_OKAY; 287 } 288 289 /* 290 * heuristic specific interface methods 291 */ 292 293 /** creates the guideddiving heuristic and includes it in SCIP */ 294 SCIP_RETCODE SCIPincludeHeurGuideddiving( 295 SCIP* scip /**< SCIP data structure */ 296 ) 297 { 298 SCIP_HEURDATA* heurdata; 299 SCIP_HEUR* heur; 300 301 /* create Guideddiving primal heuristic data */ 302 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 303 304 /* include primal heuristic */ 305 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 306 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 307 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecGuideddiving, heurdata) ); 308 309 assert(heur != NULL); 310 311 /* set non-NULL pointers to callback methods */ 312 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyGuideddiving) ); 313 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeGuideddiving) ); 314 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitGuideddiving) ); 315 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitGuideddiving) ); 316 317 /* create a diveset (this will automatically install some additional parameters for the heuristic)*/ 318 SCIP_CALL( SCIPcreateDiveset(scip, NULL, heur, HEUR_NAME, DEFAULT_MINRELDEPTH, DEFAULT_MAXRELDEPTH, DEFAULT_MAXLPITERQUOT, 319 DEFAULT_MAXDIVEUBQUOT, DEFAULT_MAXDIVEAVGQUOT, 1.0, 1.0, DEFAULT_LPRESOLVEDOMCHGQUOT, DEFAULT_LPSOLVEFREQ, 320 DEFAULT_MAXLPITEROFS, DEFAULT_RANDSEED, DEFAULT_BACKTRACK, DEFAULT_ONLYLPBRANCHCANDS, DIVESET_ISPUBLIC, DIVESET_DIVETYPES, 321 divesetGetScoreGuideddiving, divesetAvailableGuideddiving) ); 322 323 return SCIP_OKAY; 324 } 325