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_linesearchdiving.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief LP diving heuristic that fixes variables with a large difference to their root solution 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_linesearchdiving.h" 35 #include "scip/pub_heur.h" 36 #include "scip/pub_message.h" 37 #include "scip/pub_var.h" 38 #include "scip/scip_heur.h" 39 #include "scip/scip_mem.h" 40 #include "scip/scip_numerics.h" 41 #include "scip/scip_sol.h" 42 #include <string.h> 43 44 #define HEUR_NAME "linesearchdiving" 45 #define HEUR_DESC "LP diving heuristic that chooses fixings following the line from root solution to current solution" 46 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING 47 #define HEUR_PRIORITY -1006000 48 #define HEUR_FREQ 10 49 #define HEUR_FREQOFS 6 50 #define HEUR_MAXDEPTH -1 51 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE 52 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */ 53 #define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY | SCIP_DIVETYPE_SOS1VARIABLE /**< bit mask that represents all supported dive types */ 54 #define DIVESET_ISPUBLIC TRUE /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */ 55 56 57 /* 58 * Default parameter settings 59 */ 60 61 #define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */ 62 #define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */ 63 #define DEFAULT_MAXLPITERQUOT 0.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */ 64 #define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */ 65 #define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) 66 * where diving is performed (0.0: no limit) */ 67 #define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) 68 * where diving is performed (0.0: no limit) */ 69 #define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */ 70 #define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */ 71 #define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */ 72 #define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 /**< percentage of immediate domain changes during probing to trigger LP resolve */ 73 #define DEFAULT_LPSOLVEFREQ 0 /**< LP solve frequency for diving heuristics */ 74 #define DEFAULT_ONLYLPBRANCHCANDS FALSE /**< should only LP branching candidates be considered instead of the slower but 75 * more general constraint handler diving variable selection? */ 76 #define DEFAULT_RANDSEED 137 /**< default initialization for random seed number generation */ 77 /* 78 * Data structures 79 */ 80 81 /** primal heuristic data */ 82 struct SCIP_HeurData 83 { 84 SCIP_SOL* sol; /**< working solution */ 85 }; 86 87 88 /* 89 * Local methods 90 */ 91 92 93 /* 94 * Callback methods of primal heuristic 95 */ 96 97 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 98 static 99 SCIP_DECL_HEURCOPY(heurCopyLinesearchdiving) 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 primal heuristic */ 106 SCIP_CALL( SCIPincludeHeurLinesearchdiving(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(heurFreeLinesearchdiving) 114 { /*lint --e{715}*/ 115 SCIP_HEURDATA* heurdata; 116 117 assert(heur != NULL); 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(heurInitLinesearchdiving) 133 { /*lint --e{715}*/ 134 SCIP_HEURDATA* heurdata; 135 136 assert(heur != NULL); 137 138 /* get heuristic data */ 139 heurdata = SCIPheurGetData(heur); 140 assert(heurdata != NULL); 141 142 /* create working solution */ 143 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) ); 144 145 return SCIP_OKAY; 146 } 147 148 149 /** deinitialization method of primal heuristic (called before transformed problem is freed) */ 150 static 151 SCIP_DECL_HEUREXIT(heurExitLinesearchdiving) 152 { /*lint --e{715}*/ 153 SCIP_HEURDATA* heurdata; 154 155 assert(heur != NULL); 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(heurExecLinesearchdiving) 171 { /*lint --e{715}*/ 172 SCIP_HEURDATA* heurdata; 173 SCIP_DIVESET* diveset; 174 175 heurdata = SCIPheurGetData(heur); 176 assert(SCIPheurGetNDivesets(heur) > 0); 177 assert(SCIPheurGetDivesets(heur) != NULL); 178 diveset = SCIPheurGetDivesets(heur)[0]; 179 assert(diveset != NULL); 180 181 *result = SCIP_DIDNOTRUN; 182 183 SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, -1L, -1, -1.0, SCIP_DIVECONTEXT_SINGLE) ); 184 185 return SCIP_OKAY; 186 } 187 188 /* diving setting callbacks */ 189 190 /** returns a score for the given candidate -- the best candidate maximizes the diving score */ 191 static 192 SCIP_DECL_DIVESETGETSCORE(divesetGetScoreLinesearchdiving) 193 { /*lint --e{715}*/ 194 SCIP_Real rootsolval; 195 SCIP_Real distquot; 196 197 rootsolval = SCIPvarGetRootSol(cand); 198 199 /* preferred branching direction is further away from the root LP solution */ 200 if( SCIPisLT(scip, candsol, rootsolval) ) 201 { 202 /* round down*/ 203 *roundup = FALSE; 204 205 switch( divetype ) 206 { 207 case SCIP_DIVETYPE_INTEGRALITY: 208 distquot = (candsfrac + SCIPsumepsilon(scip)) / (rootsolval - candsol); 209 break; 210 case SCIP_DIVETYPE_SOS1VARIABLE: 211 if ( SCIPisFeasPositive(scip, candsol) ) 212 distquot = (candsfrac + SCIPsumepsilon(scip)) / (rootsolval - candsol); 213 else 214 distquot = (1.0 - candsfrac + SCIPsumepsilon(scip)) / (candsol - rootsolval); 215 break; 216 default: 217 SCIPerrorMessage("Error: Unsupported diving type\n"); 218 SCIPABORT(); 219 return SCIP_INVALIDDATA; /*lint !e527*/ 220 } /*lint !e788*/ 221 222 /* avoid roundable candidates */ 223 if( SCIPvarMayRoundDown(cand) ) 224 distquot *= 1000.0; 225 } 226 else if( SCIPisGT(scip, candsol, rootsolval) ) 227 { 228 /* round up */ 229 switch( divetype ) 230 { 231 case SCIP_DIVETYPE_INTEGRALITY: 232 distquot = (1.0 - candsfrac + SCIPsumepsilon(scip)) / (candsol - rootsolval); 233 break; 234 case SCIP_DIVETYPE_SOS1VARIABLE: 235 if ( SCIPisFeasPositive(scip, candsol) ) 236 distquot = (1.0 - candsfrac + SCIPsumepsilon(scip)) / (candsol - rootsolval); 237 else 238 distquot = (candsfrac + SCIPsumepsilon(scip)) / (rootsolval - candsol); 239 break; 240 default: 241 SCIPerrorMessage("Error: Unsupported diving type\n"); 242 SCIPABORT(); 243 return SCIP_INVALIDDATA; /*lint !e527*/ 244 } /*lint !e788*/ 245 246 /* avoid roundable candidates */ 247 if( SCIPvarMayRoundUp(cand) ) 248 distquot *= 1000.0; 249 *roundup = TRUE; 250 } 251 else 252 { 253 /* if the solution values are equal, we arbitrarily select branching downwards; 254 * candidates with equal LP solution values are penalized with an infinite score 255 */ 256 *roundup = FALSE; 257 distquot = SCIPinfinity(scip); 258 } 259 260 *score = -distquot; 261 262 return SCIP_OKAY; 263 } 264 265 #define divesetAvailableLinesearchdiving NULL 266 267 /* 268 * primal heuristic specific interface methods 269 */ 270 271 /** creates the linesearchdiving primal heuristic and includes it in SCIP */ 272 SCIP_RETCODE SCIPincludeHeurLinesearchdiving( 273 SCIP* scip /**< SCIP data structure */ 274 ) 275 { 276 SCIP_HEURDATA* heurdata; 277 SCIP_HEUR* heur; 278 279 /* create Linesearchdiving primal heuristic data */ 280 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 281 282 /* include primal heuristic */ 283 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 284 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 285 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecLinesearchdiving, heurdata) ); 286 287 assert(heur != NULL); 288 289 /* set non-NULL pointers to callback methods */ 290 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyLinesearchdiving) ); 291 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeLinesearchdiving) ); 292 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitLinesearchdiving) ); 293 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitLinesearchdiving) ); 294 295 /* create a diveset (this will automatically install some additional parameters for the heuristic)*/ 296 SCIP_CALL( SCIPcreateDiveset(scip, NULL, heur, HEUR_NAME, DEFAULT_MINRELDEPTH, DEFAULT_MAXRELDEPTH, DEFAULT_MAXLPITERQUOT, 297 DEFAULT_MAXDIVEUBQUOT, DEFAULT_MAXDIVEAVGQUOT, DEFAULT_MAXDIVEUBQUOTNOSOL, DEFAULT_MAXDIVEAVGQUOTNOSOL, 298 DEFAULT_LPRESOLVEDOMCHGQUOT, DEFAULT_LPSOLVEFREQ, DEFAULT_MAXLPITEROFS, DEFAULT_RANDSEED, 299 DEFAULT_BACKTRACK, DEFAULT_ONLYLPBRANCHCANDS, 300 DIVESET_ISPUBLIC, DIVESET_DIVETYPES, divesetGetScoreLinesearchdiving, divesetAvailableLinesearchdiving) ); 301 302 return SCIP_OKAY; 303 } 304