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_coefdiving.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief LP diving heuristic that chooses fixings w.r.t. the matrix coefficients 28 * @author Tobias Achterberg 29 * @author Marc Pfetsch 30 * 31 * Indicator constraints are taken into account if present. 32 */ 33 34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 35 36 #include "scip/heur_coefdiving.h" 37 #include "scip/heuristics.h" 38 #include "scip/pub_heur.h" 39 #include "scip/pub_message.h" 40 #include "scip/pub_misc.h" 41 #include "scip/pub_var.h" 42 #include "scip/scip_heur.h" 43 #include "scip/scip_lp.h" 44 #include "scip/scip_mem.h" 45 #include "scip/scip_numerics.h" 46 #include "scip/scip_sol.h" 47 #include <string.h> 48 49 #define HEUR_NAME "coefdiving" 50 #define HEUR_DESC "LP diving heuristic that chooses fixings w.r.t. the matrix coefficients" 51 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING 52 #define HEUR_PRIORITY -1001000 53 #define HEUR_FREQ -1 54 #define HEUR_FREQOFS 1 55 #define HEUR_MAXDEPTH -1 56 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE 57 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */ 58 #define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY | SCIP_DIVETYPE_SOS1VARIABLE /**< bit mask that represents all supported dive types */ 59 #define DIVESET_ISPUBLIC TRUE /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */ 60 61 62 /* 63 * Default parameter settings 64 */ 65 66 #define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */ 67 #define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */ 68 #define DEFAULT_MAXLPITERQUOT 0.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */ 69 #define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */ 70 #define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) 71 * where diving is performed (0.0: no limit) */ 72 #define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) 73 * where diving is performed (0.0: no limit) */ 74 #define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */ 75 #define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */ 76 #define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */ 77 #define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 /**< percentage of immediate domain changes during probing to trigger LP resolve */ 78 #define DEFAULT_LPSOLVEFREQ 0 /**< LP solve frequency for diving heuristics */ 79 #define DEFAULT_ONLYLPBRANCHCANDS FALSE /**< should only LP branching candidates be considered instead of the slower but 80 * more general constraint handler diving variable selection? */ 81 #define DEFAULT_RANDSEED 83 /**< default random seed */ 82 83 /* locally defined heuristic data */ 84 struct SCIP_HeurData 85 { 86 SCIP_SOL* sol; /**< working solution */ 87 }; 88 89 /* 90 * local methods 91 */ 92 93 /* 94 * Callback methods 95 */ 96 97 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 98 static 99 SCIP_DECL_HEURCOPY(heurCopyCoefdiving) 100 { /*lint --e{715}*/ 101 assert(scip != NULL); 102 assert(heur != NULL); 103 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 104 105 /* call inclusion method of constraint handler */ 106 SCIP_CALL( SCIPincludeHeurCoefdiving(scip) ); 107 108 return SCIP_OKAY; 109 } 110 111 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 112 static 113 SCIP_DECL_HEURFREE(heurFreeCoefdiving) /*lint --e{715}*/ 114 { /*lint --e{715}*/ 115 SCIP_HEURDATA* heurdata; 116 117 assert(heur != NULL); 118 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 119 assert(scip != NULL); 120 121 /* free heuristic data */ 122 heurdata = SCIPheurGetData(heur); 123 assert(heurdata != NULL); 124 SCIPfreeBlockMemory(scip, &heurdata); 125 SCIPheurSetData(heur, NULL); 126 127 return SCIP_OKAY; 128 } 129 130 131 /** initialization method of primal heuristic (called after problem was transformed) */ 132 static 133 SCIP_DECL_HEURINIT(heurInitCoefdiving) /*lint --e{715}*/ 134 { /*lint --e{715}*/ 135 SCIP_HEURDATA* heurdata; 136 137 assert(heur != NULL); 138 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 139 140 /* get heuristic data */ 141 heurdata = SCIPheurGetData(heur); 142 assert(heurdata != NULL); 143 144 /* create working solution */ 145 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) ); 146 147 return SCIP_OKAY; 148 } 149 150 151 /** deinitialization method of primal heuristic (called before transformed problem is freed) */ 152 static 153 SCIP_DECL_HEUREXIT(heurExitCoefdiving) /*lint --e{715}*/ 154 { /*lint --e{715}*/ 155 SCIP_HEURDATA* heurdata; 156 157 assert(heur != NULL); 158 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 159 160 /* get heuristic data */ 161 heurdata = SCIPheurGetData(heur); 162 assert(heurdata != NULL); 163 164 /* free working solution */ 165 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) ); 166 167 return SCIP_OKAY; 168 } 169 170 171 /** execution method of primal heuristic */ 172 static 173 SCIP_DECL_HEUREXEC(heurExecCoefdiving) /*lint --e{715}*/ 174 { /*lint --e{715}*/ 175 SCIP_HEURDATA* heurdata; 176 SCIP_DIVESET* diveset; 177 178 heurdata = SCIPheurGetData(heur); 179 assert(heurdata != NULL); 180 181 assert(SCIPheurGetNDivesets(heur) > 0); 182 assert(SCIPheurGetDivesets(heur) != NULL); 183 diveset = SCIPheurGetDivesets(heur)[0]; 184 assert(diveset != NULL); 185 186 SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, -1L, -1, -1.0, SCIP_DIVECONTEXT_SINGLE) ); 187 188 return SCIP_OKAY; 189 } 190 191 /** returns a score for the given candidate -- the best candidate maximizes the diving score */ 192 static 193 SCIP_DECL_DIVESETGETSCORE(divesetGetScoreCoefdiving) 194 { 195 SCIP_Bool mayrounddown = SCIPvarMayRoundDown(cand); 196 SCIP_Bool mayroundup = SCIPvarMayRoundUp(cand); 197 198 if( mayrounddown || mayroundup ) 199 { 200 /* choose rounding direction: 201 * - if variable may be rounded in both directions, round corresponding to the fractionality 202 * - otherwise, round in the infeasible direction 203 */ 204 if( mayrounddown && mayroundup ) 205 { 206 assert( divetype != SCIP_DIVETYPE_SOS1VARIABLE ); 207 208 /* try to avoid variability; decide randomly if the LP solution can contain some noise */ 209 if( SCIPisEQ(scip, candsfrac, 0.5) ) 210 *roundup = (SCIPrandomGetInt(SCIPdivesetGetRandnumgen(diveset), 0, 1) == 0); 211 else 212 *roundup = (candsfrac > 0.5); 213 } 214 else 215 *roundup = mayrounddown; 216 } 217 else 218 { 219 /* the candidate may not be rounded */ 220 int nlocksdown = SCIPvarGetNLocksDownType(cand, SCIP_LOCKTYPE_MODEL); 221 int nlocksup = SCIPvarGetNLocksUpType(cand, SCIP_LOCKTYPE_MODEL); 222 *roundup = (nlocksdown > nlocksup || (nlocksdown == nlocksup && candsfrac > 0.5)); 223 } 224 225 if( *roundup ) 226 { 227 switch( divetype ) 228 { 229 case SCIP_DIVETYPE_INTEGRALITY: 230 candsfrac = 1.0 - candsfrac; 231 break; 232 case SCIP_DIVETYPE_SOS1VARIABLE: 233 if ( SCIPisFeasPositive(scip, candsol) ) 234 candsfrac = 1.0 - candsfrac; 235 break; 236 default: 237 SCIPerrorMessage("Error: Unsupported diving type\n"); 238 SCIPABORT(); 239 return SCIP_INVALIDDATA; /*lint !e527*/ 240 } /*lint !e788*/ 241 *score = SCIPvarGetNLocksUpType(cand, SCIP_LOCKTYPE_MODEL); 242 } 243 else 244 { 245 if ( divetype == SCIP_DIVETYPE_SOS1VARIABLE && SCIPisFeasNegative(scip, candsol) ) 246 candsfrac = 1.0 - candsfrac; 247 *score = SCIPvarGetNLocksDownType(cand, SCIP_LOCKTYPE_MODEL); 248 } 249 250 /* penalize too small fractions */ 251 if( SCIPisEQ(scip, candsfrac, 0.01) ) 252 { 253 /* try to avoid variability; decide randomly if the LP solution can contain some noise. 254 * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for scaling the score 255 */ 256 if( SCIPrandomGetInt(SCIPdivesetGetRandnumgen(diveset), 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 ) 257 (*score) *= 0.01; 258 } 259 else if( candsfrac < 0.01 ) 260 (*score) *= 0.01; 261 262 /* prefer decisions on binary variables */ 263 if( !SCIPvarIsBinary(cand) ) 264 (*score) *= 0.1; 265 266 /* penalize the variable if it may be rounded. */ 267 if( mayrounddown || mayroundup ) 268 (*score) -= SCIPgetNLPRows(scip); 269 270 /* check, if candidate is new best candidate: prefer unroundable candidates in any case */ 271 assert( (0.0 < candsfrac && candsfrac < 1.0) || SCIPvarIsBinary(cand) || divetype == SCIP_DIVETYPE_SOS1VARIABLE ); 272 273 return SCIP_OKAY; 274 } 275 276 /* 277 * heuristic specific interface methods 278 */ 279 280 #define divesetAvailableCoefdiving NULL 281 282 /** creates the coefdiving heuristic and includes it in SCIP */ 283 SCIP_RETCODE SCIPincludeHeurCoefdiving( 284 SCIP* scip /**< SCIP data structure */ 285 ) 286 { 287 SCIP_HEURDATA* heurdata; 288 SCIP_HEUR* heur; 289 290 /* create coefdiving primal heuristic data */ 291 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 292 293 /* include primal heuristic */ 294 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 295 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 296 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecCoefdiving, heurdata) ); 297 298 assert(heur != NULL); 299 300 /* set non-NULL pointers to callback methods */ 301 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyCoefdiving) ); 302 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeCoefdiving) ); 303 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitCoefdiving) ); 304 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitCoefdiving) ); 305 306 /* create a diveset (this will automatically install some additional parameters for the heuristic)*/ 307 SCIP_CALL( SCIPcreateDiveset(scip, NULL, heur, HEUR_NAME, DEFAULT_MINRELDEPTH, DEFAULT_MAXRELDEPTH, DEFAULT_MAXLPITERQUOT, 308 DEFAULT_MAXDIVEUBQUOT, DEFAULT_MAXDIVEAVGQUOT, DEFAULT_MAXDIVEUBQUOTNOSOL, DEFAULT_MAXDIVEAVGQUOTNOSOL, DEFAULT_LPRESOLVEDOMCHGQUOT, 309 DEFAULT_LPSOLVEFREQ, DEFAULT_MAXLPITEROFS, DEFAULT_RANDSEED, DEFAULT_BACKTRACK, DEFAULT_ONLYLPBRANCHCANDS, 310 DIVESET_ISPUBLIC, DIVESET_DIVETYPES, divesetGetScoreCoefdiving, divesetAvailableCoefdiving) ); 311 312 return SCIP_OKAY; 313 } 314 315