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_pscostdiving.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief LP diving heuristic that chooses fixings w.r.t. the pseudo cost values 28 * @author Tobias Achterberg 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include "scip/heuristics.h" 34 #include "scip/heur_pscostdiving.h" 35 #include "scip/pub_heur.h" 36 #include "scip/pub_message.h" 37 #include "scip/pub_misc.h" 38 #include "scip/pub_var.h" 39 #include "scip/scip_heur.h" 40 #include "scip/scip_mem.h" 41 #include "scip/scip_numerics.h" 42 #include "scip/scip_prob.h" 43 #include "scip/scip_sol.h" 44 #include "scip/scip_var.h" 45 #include <string.h> 46 47 #define HEUR_NAME "pscostdiving" 48 #define HEUR_DESC "LP diving heuristic that chooses fixings w.r.t. the pseudo cost values" 49 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING 50 #define HEUR_PRIORITY -1002000 51 #define HEUR_FREQ 10 52 #define HEUR_FREQOFS 2 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_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */ 73 #define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */ 74 #define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */ 75 #define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 /**< percentage of immediate domain changes during probing to trigger LP resolve */ 76 #define DEFAULT_LPSOLVEFREQ 0 /**< LP solve frequency for diving heuristics */ 77 #define DEFAULT_ONLYLPBRANCHCANDS TRUE /**< should only LP branching candidates be considered instead of the slower but 78 * more general constraint handler diving variable selection? */ 79 #define DEFAULT_RANDSEED 103 /**< initial random seed */ 80 81 82 /* locally defined heuristic data */ 83 struct SCIP_HeurData 84 { 85 SCIP_SOL* sol; /**< working solution */ 86 }; 87 88 /* 89 * local methods 90 */ 91 92 /* 93 * Callback methods 94 */ 95 96 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 97 static 98 SCIP_DECL_HEURCOPY(heurCopyPscostdiving) 99 { /*lint --e{715}*/ 100 assert(scip != NULL); 101 assert(heur != NULL); 102 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 103 104 /* call inclusion method of primal heuristic */ 105 SCIP_CALL( SCIPincludeHeurPscostdiving(scip) ); 106 107 return SCIP_OKAY; 108 } 109 110 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 111 static 112 SCIP_DECL_HEURFREE(heurFreePscostdiving) /*lint --e{715}*/ 113 { /*lint --e{715}*/ 114 SCIP_HEURDATA* heurdata; 115 116 assert(heur != NULL); 117 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 118 assert(scip != NULL); 119 120 /* free heuristic data */ 121 heurdata = SCIPheurGetData(heur); 122 assert(heurdata != NULL); 123 SCIPfreeBlockMemory(scip, &heurdata); 124 SCIPheurSetData(heur, NULL); 125 126 return SCIP_OKAY; 127 } 128 129 130 /** initialization method of primal heuristic (called after problem was transformed) */ 131 static 132 SCIP_DECL_HEURINIT(heurInitPscostdiving) /*lint --e{715}*/ 133 { /*lint --e{715}*/ 134 SCIP_HEURDATA* heurdata; 135 136 assert(heur != NULL); 137 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 138 139 /* get heuristic data */ 140 heurdata = SCIPheurGetData(heur); 141 assert(heurdata != NULL); 142 143 /* create working solution */ 144 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) ); 145 146 return SCIP_OKAY; 147 } 148 149 150 /** deinitialization method of primal heuristic (called before transformed problem is freed) */ 151 static 152 SCIP_DECL_HEUREXIT(heurExitPscostdiving) /*lint --e{715}*/ 153 { /*lint --e{715}*/ 154 SCIP_HEURDATA* heurdata; 155 156 assert(heur != NULL); 157 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 158 159 /* get heuristic data */ 160 heurdata = SCIPheurGetData(heur); 161 assert(heurdata != NULL); 162 163 /* free working solution */ 164 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) ); 165 166 return SCIP_OKAY; 167 } 168 169 /** execution method of primal heuristic */ 170 static 171 SCIP_DECL_HEUREXEC(heurExecPscostdiving) /*lint --e{715}*/ 172 { /*lint --e{715}*/ 173 SCIP_HEURDATA* heurdata; 174 SCIP_DIVESET* diveset; 175 176 heurdata = SCIPheurGetData(heur); 177 assert(heurdata != NULL); 178 assert(SCIPheurGetNDivesets(heur) > 0); 179 assert(SCIPheurGetDivesets(heur) != NULL); 180 diveset = SCIPheurGetDivesets(heur)[0]; 181 assert(diveset != NULL); 182 183 *result = SCIP_DIDNOTRUN; 184 185 /* terminate if there are no integer variables (note that, e.g., SOS1 variables may be present) */ 186 if( SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) == 0 ) 187 return SCIP_OKAY; 188 189 SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, -1L, -1, -1.0, SCIP_DIVECONTEXT_SINGLE) ); 190 191 return SCIP_OKAY; 192 } 193 194 195 /** returns a score for the given candidate -- the best candidate maximizes the diving score */ 196 static 197 SCIP_DECL_DIVESETGETSCORE(divesetGetScorePscostdiving) 198 { 199 SCIP_Real pscostdown; 200 SCIP_Real pscostup; 201 SCIP_Real pscostquot; 202 203 SCIP_Bool mayrounddown; 204 SCIP_Bool mayroundup; 205 206 mayrounddown = SCIPvarMayRoundDown(cand); 207 mayroundup = SCIPvarMayRoundUp(cand); 208 209 /* bound fractions to not prefer variables that are nearly integral */ 210 candsfrac = MAX(candsfrac, 0.1); 211 candsfrac = MIN(candsfrac, 0.9); 212 213 pscostdown = SCIPgetVarPseudocostVal(scip, cand, 0.0 - candsfrac); 214 pscostup = SCIPgetVarPseudocostVal(scip, cand, 1.0 - candsfrac); 215 216 /* determine the candidate direction. if the variable may be trivially rounded in one direction, take the other direction; 217 * otherwise, consider first the direction from the root solution, second the candidate fractionality, and 218 * last the direction of smaller pseudo costs 219 * 220 * to avoid performance variability caused by numerics we use random numbers to decide whether we want to roundup or 221 * round down if the values to compare are equal within tolerances. 222 */ 223 assert(pscostdown >= 0.0 && pscostup >= 0.0); 224 if( mayrounddown != mayroundup ) 225 *roundup = mayrounddown; 226 else if( SCIPisLT(scip, candsol, SCIPvarGetRootSol(cand) - 0.4) 227 || (SCIPisEQ(scip, candsol, SCIPvarGetRootSol(cand) - 0.4) && SCIPrandomGetInt(SCIPdivesetGetRandnumgen(diveset), 0, 1) == 0) ) 228 *roundup = FALSE; 229 else if( SCIPisGT(scip, candsol, SCIPvarGetRootSol(cand) + 0.4) 230 || (SCIPisEQ(scip, candsol, SCIPvarGetRootSol(cand) + 0.4) && SCIPrandomGetInt(SCIPdivesetGetRandnumgen(diveset), 0, 1) == 0) ) 231 *roundup = TRUE; 232 else if( SCIPisLT(scip, candsfrac, 0.3) 233 || (SCIPisEQ(scip, candsfrac, 0.3) && SCIPrandomGetInt(SCIPdivesetGetRandnumgen(diveset), 0, 1) == 0) ) 234 *roundup = FALSE; 235 else if( SCIPisGT(scip, candsfrac, 0.7) 236 || (SCIPisEQ(scip, candsfrac, 0.7) && SCIPrandomGetInt(SCIPdivesetGetRandnumgen(diveset), 0, 1) == 0) ) 237 *roundup = TRUE; 238 else if( SCIPisEQ(scip, pscostdown, pscostup) ) 239 *roundup = (SCIPrandomGetInt(SCIPdivesetGetRandnumgen(diveset), 0, 1) == 0); 240 else if( pscostdown > pscostup ) 241 *roundup = TRUE; 242 else 243 *roundup = FALSE; 244 245 if( *roundup ) 246 pscostquot = sqrt(candsfrac) * (1.0 + pscostdown) / (1.0 + pscostup); 247 else 248 pscostquot = sqrt(1.0 - candsfrac) * (1.0 + pscostup) / (1.0 + pscostdown); 249 250 /* prefer decisions on binary variables */ 251 if( SCIPvarIsBinary(cand) && !(SCIPvarMayRoundDown(cand) || SCIPvarMayRoundUp(cand))) 252 pscostquot *= 1000.0; 253 254 assert(pscostquot >= 0); 255 *score = pscostquot; 256 257 return SCIP_OKAY; 258 } 259 260 #define divesetAvailablePscostdiving NULL 261 262 /* 263 * heuristic specific interface methods 264 */ 265 266 /** creates the pscostdiving heuristic and includes it in SCIP */ 267 SCIP_RETCODE SCIPincludeHeurPscostdiving( 268 SCIP* scip /**< SCIP data structure */ 269 ) 270 { 271 SCIP_HEURDATA* heurdata; 272 SCIP_HEUR* heur; 273 274 /* create Pscostdiving primal heuristic data */ 275 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 276 277 /* include primal heuristic */ 278 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 279 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 280 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecPscostdiving, heurdata) ); 281 282 assert(heur != NULL); 283 284 /* set non-NULL pointers to callback methods */ 285 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyPscostdiving) ); 286 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreePscostdiving) ); 287 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitPscostdiving) ); 288 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitPscostdiving) ); 289 290 /* create a diveset (this will automatically install some additional parameters for the heuristic)*/ 291 SCIP_CALL( SCIPcreateDiveset(scip, NULL, heur, HEUR_NAME, DEFAULT_MINRELDEPTH, DEFAULT_MAXRELDEPTH, DEFAULT_MAXLPITERQUOT, 292 DEFAULT_MAXDIVEUBQUOT, DEFAULT_MAXDIVEAVGQUOT, DEFAULT_MAXDIVEUBQUOTNOSOL, DEFAULT_MAXDIVEAVGQUOTNOSOL, DEFAULT_LPRESOLVEDOMCHGQUOT, 293 DEFAULT_LPSOLVEFREQ, DEFAULT_MAXLPITEROFS, DEFAULT_RANDSEED, DEFAULT_BACKTRACK, DEFAULT_ONLYLPBRANCHCANDS, 294 DIVESET_ISPUBLIC, DIVESET_DIVETYPES, divesetGetScorePscostdiving, divesetAvailablePscostdiving) ); 295 296 return SCIP_OKAY; 297 } 298 299