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_trysol.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief primal heuristic that tries a given solution 28 * @author Marc Pfetsch 29 * 30 * This heuristic takes a solution from somewhere else via the function SCIPheurPassSolTrySol(). It 31 * then tries to commit this solution. It is mainly used by cons_indicator, which tries to correct a 32 * given solution, but cannot directly submit this solution, because it is a constraint handler and 33 * not a heuristic. 34 */ 35 36 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 37 38 #include "scip/heur_trysol.h" 39 #include "scip/pub_heur.h" 40 #include "scip/pub_message.h" 41 #include "scip/pub_sol.h" 42 #include "scip/scip_heur.h" 43 #include "scip/scip_mem.h" 44 #include "scip/scip_message.h" 45 #include "scip/scip_numerics.h" 46 #include "scip/scip_prob.h" 47 #include "scip/scip_sol.h" 48 #include <string.h> 49 50 #define HEUR_NAME "trysol" 51 #define HEUR_DESC "try solution heuristic" 52 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_TRIVIAL 53 #define HEUR_PRIORITY -3000010 /* should process after all other heuristics */ 54 #define HEUR_FREQ 1 55 #define HEUR_FREQOFS 0 56 #define HEUR_MAXDEPTH -1 57 #define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_BEFOREPRESOL | SCIP_HEURTIMING_BEFORENODE 58 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */ 59 60 61 /* 62 * Data structures 63 */ 64 65 66 /** primal heuristic data */ 67 struct SCIP_HeurData 68 { 69 SCIP_SOL* trysol; /**< storing solution passed to heuristic which has to tried (NULL if none) */ 70 SCIP_SOL* addsol; /**< storing solution passed to heuristic which can be added without checking (NULL if none) */ 71 SCIP_Bool rec; /**< whether we are within our own call */ 72 }; 73 74 75 /* 76 * Callback methods of primal heuristic 77 */ 78 79 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 80 static 81 SCIP_DECL_HEURCOPY(heurCopyTrySol) 82 { /*lint --e{715}*/ 83 assert(scip != NULL); 84 assert(heur != NULL); 85 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 86 87 /* call inclusion method of primal heuristic */ 88 SCIP_CALL( SCIPincludeHeurTrySol(scip) ); 89 90 return SCIP_OKAY; 91 } 92 93 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 94 static 95 SCIP_DECL_HEURFREE(heurFreeTrySol) 96 { /*lint --e{715}*/ 97 SCIP_HEURDATA* heurdata; 98 99 assert( heur != NULL ); 100 assert( strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0 ); 101 assert( scip != NULL ); 102 103 SCIPdebugMsg(scip, "free method of trysol primal heuristic.\n"); 104 105 /* get heuristic data */ 106 heurdata = SCIPheurGetData(heur); 107 assert(heurdata != NULL); 108 109 SCIPfreeBlockMemory(scip, &heurdata); 110 111 return SCIP_OKAY; 112 } 113 114 115 /** deinitialization method of primal heuristic (called before transformed problem is freed) */ 116 static 117 SCIP_DECL_HEUREXITSOL(heurExitTrySol) 118 { /*lint --e{715}*/ 119 SCIP_HEURDATA* heurdata; 120 121 assert( heur != NULL ); 122 assert( strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0 ); 123 assert( scip != NULL ); 124 125 SCIPdebugMsg(scip, "exit method of trysol primal heuristic.\n"); 126 127 /* get heuristic data */ 128 heurdata = SCIPheurGetData(heur); 129 assert(heurdata != NULL); 130 131 /* free solution if one is still present */ 132 if( heurdata->trysol != NULL ) 133 SCIP_CALL( SCIPfreeSol(scip, &heurdata->trysol) ); 134 assert( heurdata->trysol == NULL ); 135 136 /* free solution if one is still present */ 137 if( heurdata->addsol != NULL ) 138 SCIP_CALL( SCIPfreeSol(scip, &heurdata->addsol) ); 139 assert( heurdata->trysol == NULL ); 140 141 return SCIP_OKAY; 142 } 143 144 145 /** execution method of primal heuristic */ 146 static 147 SCIP_DECL_HEUREXEC(heurExecTrySol) 148 { /*lint --e{715}*/ 149 SCIP_HEURDATA* heurdata; 150 SCIP_Bool stored; 151 #ifdef SCIP_DEBUG 152 SCIP_Real obj; 153 #endif 154 155 assert( heur != NULL ); 156 assert( strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0 ); 157 assert( scip != NULL ); 158 assert( result != NULL ); 159 160 *result = SCIP_DIDNOTRUN; 161 162 /* get heuristic data */ 163 heurdata = SCIPheurGetData(heur); 164 assert(heurdata != NULL); 165 166 /* only run if solution present */ 167 if( heurdata->addsol == NULL && heurdata->trysol == NULL ) 168 return SCIP_OKAY; 169 170 SCIPdebugMsg(scip, "exec method of trysol primal heuristic.\n"); 171 *result = SCIP_DIDNOTFIND; 172 heurdata->rec = TRUE; 173 174 if( heurdata->trysol != NULL ) 175 { 176 /* try solution and free it - check everything, because we are not sure */ 177 #ifdef SCIP_DEBUG 178 obj = SCIPgetSolOrigObj(scip, heurdata->trysol); 179 #endif 180 181 SCIP_CALL( SCIPtrySolFree(scip, &heurdata->trysol, FALSE, FALSE, TRUE, TRUE, TRUE, &stored) ); 182 183 if( stored ) 184 { 185 #ifdef SCIP_DEBUG 186 SCIPdebugMsg(scip, "Found feasible solution of value %g.\n", obj); 187 #endif 188 *result = SCIP_FOUNDSOL; 189 } 190 } 191 192 if( heurdata->addsol != NULL ) 193 { 194 #ifdef SCIP_DEBUG 195 obj = SCIPgetSolOrigObj(scip, heurdata->addsol); 196 #endif 197 198 SCIP_CALL( SCIPaddSolFree(scip, &heurdata->addsol, &stored) ); 199 200 if( stored ) 201 { 202 #ifdef SCIP_DEBUG 203 SCIPdebugMsg(scip, "Found feasible solution of value %g.\n", obj); 204 #endif 205 *result = SCIP_FOUNDSOL; 206 } 207 } 208 209 assert( heurdata->trysol == NULL ); 210 assert( heurdata->addsol == NULL ); 211 212 heurdata->rec = FALSE; 213 214 return SCIP_OKAY; 215 } 216 217 /* 218 * primal heuristic specific interface methods 219 */ 220 221 /** creates the trysol primal heuristic and includes it in SCIP */ 222 SCIP_RETCODE SCIPincludeHeurTrySol( 223 SCIP* scip /**< SCIP data structure */ 224 ) 225 { 226 SCIP_HEURDATA* heurdata; 227 SCIP_HEUR* heur; 228 229 /* create heuristic data */ 230 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 231 heurdata->trysol = NULL; 232 heurdata->addsol = NULL; 233 heurdata->rec = FALSE; 234 235 /* include primal heuristic */ 236 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 237 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 238 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecTrySol, heurdata) ); 239 240 assert(heur != NULL); 241 242 /* set non-NULL pointers to callback methods */ 243 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyTrySol) ); 244 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeTrySol) ); 245 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitTrySol) ); 246 247 return SCIP_OKAY; 248 } 249 250 251 /** pass solution to trysol heuristic */ 252 SCIP_RETCODE SCIPheurPassSolTrySol( 253 SCIP* scip, /**< SCIP data structure */ 254 SCIP_HEUR* heur, /**< trysol heuristic */ 255 SCIP_SOL* sol /**< solution to be passed */ 256 ) 257 { 258 SCIP_HEURDATA* heurdata; 259 260 assert( scip != NULL ); 261 assert( heur != NULL ); 262 assert( sol != NULL ); 263 assert( strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0 ); 264 265 /* get heuristic data */ 266 heurdata = SCIPheurGetData(heur); 267 assert(heurdata != NULL); 268 269 /* only store solution if we are not within our own SCIPtrySol() call */ 270 if( ! heurdata->rec ) 271 { 272 if( heurdata->trysol == NULL || (SCIPgetObjsense(scip) == SCIP_OBJSENSE_MAXIMIZE && 273 SCIPisGT(scip, SCIPgetSolOrigObj(scip, sol), SCIPgetSolOrigObj(scip, heurdata->trysol))) || 274 SCIPisLT(scip, SCIPgetSolOrigObj(scip, sol), SCIPgetSolOrigObj(scip, heurdata->trysol)) ) 275 { 276 if( heurdata->trysol != NULL ) 277 { 278 /* free previous solution */ 279 SCIP_CALL( SCIPfreeSol(scip, &heurdata->trysol) ); 280 } 281 282 SCIPdebugMsg(scip, "Received solution of value %g.\n", SCIPgetSolOrigObj(scip, sol)); 283 SCIP_CALL( SCIPcreateSolCopy(scip, &heurdata->trysol, sol) ); 284 SCIP_CALL( SCIPunlinkSol(scip, heurdata->trysol) ); 285 SCIPsolSetHeur(heurdata->trysol, heur); 286 } 287 } 288 289 return SCIP_OKAY; 290 } 291 292 /** pass solution to trysol heuristic which just gets added (without checking feasibility */ 293 SCIP_RETCODE SCIPheurPassSolAddSol( 294 SCIP* scip, /**< SCIP data structure */ 295 SCIP_HEUR* heur, /**< trysol heuristic */ 296 SCIP_SOL* sol /**< solution to be passed */ 297 ) 298 { 299 SCIP_HEURDATA* heurdata; 300 301 assert( scip != NULL ); 302 assert( heur != NULL ); 303 assert( sol != NULL ); 304 assert( strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0 ); 305 306 /* get heuristic data */ 307 heurdata = SCIPheurGetData(heur); 308 assert(heurdata != NULL); 309 310 /* only store solution if we are not within our own SCIPtrySol() call */ 311 if( ! heurdata->rec ) 312 { 313 if( heurdata->addsol == NULL || (SCIPgetObjsense(scip) == SCIP_OBJSENSE_MAXIMIZE && 314 SCIPisGT(scip, SCIPgetSolOrigObj(scip, sol), SCIPgetSolOrigObj(scip, heurdata->addsol))) || 315 SCIPisLT(scip, SCIPgetSolOrigObj(scip, sol), SCIPgetSolOrigObj(scip, heurdata->addsol)) ) 316 { 317 if( heurdata->addsol != NULL ) 318 { 319 /* free previous solution */ 320 SCIP_CALL( SCIPfreeSol(scip, &heurdata->addsol) ); 321 } 322 323 SCIPdebugMsg(scip, "Received solution of value %g.\n", SCIPgetSolOrigObj(scip, sol)); 324 SCIP_CALL( SCIPcreateSolCopy(scip, &heurdata->addsol, sol) ); 325 SCIP_CALL( SCIPunlinkSol(scip, heurdata->addsol) ); 326 SCIPsolSetHeur(heurdata->addsol, heur); 327 } 328 } 329 330 return SCIP_OKAY; 331 } 332