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_reoptsols.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief reoptsols primal heuristic 28 * @author Jakob Witzig 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include "blockmemshell/memory.h" 34 #include "scip/heur_reoptsols.h" 35 #include "scip/pub_heur.h" 36 #include "scip/pub_message.h" 37 #include "scip/scip_heur.h" 38 #include "scip/scip_mem.h" 39 #include "scip/scip_message.h" 40 #include "scip/scip_numerics.h" 41 #include "scip/scip_param.h" 42 #include "scip/scip_prob.h" 43 #include "scip/scip_reopt.h" 44 #include "scip/scip_sol.h" 45 #include "scip/scip_solve.h" 46 #include "scip/scip_solvingstats.h" 47 #include <string.h> 48 49 50 #define HEUR_NAME "reoptsols" 51 #define HEUR_DESC "primal heuristic updating solutions found in a previous optimization round" 52 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_PROP 53 #define HEUR_PRIORITY 40000 54 #define HEUR_FREQ 0 55 #define HEUR_FREQOFS 0 56 #define HEUR_MAXDEPTH 0 57 #define HEUR_TIMING 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 /* TODO: fill in the necessary primal heuristic data */ 66 67 /** primal heuristic data */ 68 struct SCIP_HeurData 69 { 70 int maxsols; /**< maximal number of solution to update per run */ 71 int maxruns; /**< check solutions of the last k runs only */ 72 73 /* statistics */ 74 int ncheckedsols; /**< number of updated solutions */ 75 int nimprovingsols; /**< number of improving solutions */ 76 }; 77 78 79 /* 80 * Local methods 81 */ 82 83 84 /** creates a new solution for the original problem by copying the solution of the subproblem */ 85 static 86 SCIP_RETCODE createNewSol( 87 SCIP* scip, /**< original SCIP data structure */ 88 SCIP_HEUR* heur, /**< the current heuristic */ 89 SCIP_SOL* sol, /**< solution of the subproblem */ 90 SCIP_Bool* success /**< used to store whether new solution was found or not */ 91 ) 92 { 93 SCIP_VAR** vars; /* the original problem's variables */ 94 int nvars; /* the original problem's number of variables */ 95 SCIP_Real* solvals; /* solution values of the subproblem */ 96 SCIP_SOL* newsol; /* solution to be created for the original problem */ 97 98 assert(scip != NULL); 99 100 /* get variables' data */ 101 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 102 103 SCIP_CALL( SCIPallocBufferArray(scip, &solvals, nvars) ); 104 105 /* copy the solution */ 106 SCIP_CALL( SCIPgetSolVals(scip, sol, nvars, vars, solvals) ); 107 108 /* create new solution for the original problem */ 109 SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) ); 110 SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, solvals) ); 111 112 /* try to add new solution to scip and free it immediately */ 113 SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) ); 114 115 SCIPfreeBufferArray(scip, &solvals); 116 117 return SCIP_OKAY; 118 } 119 120 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 121 static 122 SCIP_DECL_HEURCOPY(heurCopyReoptsols) 123 { /*lint --e{715}*/ 124 assert(scip != NULL); 125 assert(heur != NULL); 126 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 127 128 /* call inclusion method of primal heuristic */ 129 SCIP_CALL( SCIPincludeHeurReoptsols(scip) ); 130 131 return SCIP_OKAY; 132 } 133 134 /* free data of the heuristic */ 135 static 136 SCIP_DECL_HEURFREE(heurFreeReoptsols) 137 { 138 SCIP_HEURDATA* heurdata; 139 140 assert(scip != NULL ); 141 assert(heur != NULL ); 142 143 heurdata = SCIPheurGetData(heur); 144 assert(heurdata != NULL ); 145 146 SCIPfreeBlockMemory(scip, &heurdata); 147 SCIPheurSetData(heur, NULL); 148 149 return SCIP_OKAY; 150 } 151 152 153 /* initialize the heuristic */ 154 static SCIP_DECL_HEURINIT(heurInitReoptsols) 155 { 156 SCIP_HEURDATA* heurdata; 157 158 assert(scip != NULL ); 159 assert(heur != NULL ); 160 161 heurdata = SCIPheurGetData(heur); 162 assert(heurdata != NULL ); 163 164 heurdata->ncheckedsols = 0; 165 heurdata->nimprovingsols = 0; 166 167 return SCIP_OKAY; 168 } 169 170 /** execution method of primal heuristic */ 171 static 172 SCIP_DECL_HEUREXEC(heurExecReoptsols) 173 {/*lint --e{715}*/ 174 SCIP_HEURDATA* heurdata; 175 176 SCIP_SOL** sols; 177 SCIP_Real objsimsol; 178 SCIP_Bool sepabestsol; 179 int allocmem; 180 int nchecksols; 181 int nsolsadded; 182 #ifdef SCIP_MORE_DEBUG 183 int nsolsaddedrun; 184 #endif 185 int run; 186 int max_run; 187 188 assert(heur != NULL); 189 assert(scip != NULL); 190 191 *result = SCIP_DIDNOTRUN; 192 193 if( !SCIPisReoptEnabled(scip) ) 194 return SCIP_OKAY; 195 196 heurdata = SCIPheurGetData(heur); 197 assert(heurdata != NULL); 198 199 max_run = heurdata->maxruns == -1 ? 0 : MAX(0, SCIPgetNReoptRuns(scip)-1-heurdata->maxruns); /*lint !e666*/ 200 nchecksols = heurdata->maxsols == -1 ? INT_MAX : heurdata->maxsols; 201 202 SCIP_CALL( SCIPgetRealParam(scip, "reoptimization/objsimsol", &objsimsol) ); 203 SCIP_CALL( SCIPgetBoolParam(scip, "reoptimization/sepabestsol", &sepabestsol) ); 204 205 /* allocate a buffer array to store the solutions */ 206 allocmem = 20; 207 SCIP_CALL( SCIPallocBufferArray(scip, &sols, allocmem) ); 208 209 nsolsadded = 0; 210 211 for( run = SCIPgetNReoptRuns(scip); run > max_run && nchecksols > 0; run-- ) 212 { 213 SCIP_Real sim; 214 int nsols; 215 216 #ifdef SCIP_MORE_DEBUG 217 nsolsaddedrun = 0; 218 #endif 219 nsols = 0; 220 221 if( objsimsol == -1 ) 222 sim = 1; 223 else 224 sim = SCIPgetReoptSimilarity(scip, run, SCIPgetNReoptRuns(scip)-1); 225 226 if( sim == SCIP_INVALID ) /*lint !e777*/ 227 return SCIP_INVALIDRESULT; 228 229 if( sim >= objsimsol ) 230 { 231 int s; 232 233 /* get solutions of a specific run */ 234 SCIP_CALL( SCIPgetReoptSolsRun(scip, run, sols, allocmem, &nsols) ); 235 236 /* check memory and reallocate */ 237 if( nsols >= allocmem ) 238 { 239 allocmem = nsols; 240 SCIP_CALL( SCIPreallocBufferArray(scip, &sols, allocmem) ); 241 242 SCIP_CALL( SCIPgetReoptSolsRun(scip, run, sols, allocmem, &nsols) ); 243 } 244 assert(nsols <= allocmem); 245 246 /* update the solutions 247 * stop, if the maximal number of solutions to be checked is reached 248 */ 249 for( s = 0; s < nsols && nchecksols > 0; s++ ) 250 { 251 SCIP_SOL* sol; 252 SCIP_Real objsol; 253 254 sol = sols[s]; 255 256 SCIP_CALL( SCIPrecomputeSolObj(scip, sol) ); 257 objsol = SCIPgetSolTransObj(scip, sol); 258 259 /* we do not want to add solutions with objective value +infinity. 260 * moreover, the solution should improve the current primal bound 261 */ 262 if( !SCIPisInfinity(scip, objsol) && !SCIPisInfinity(scip, -objsol) 263 && SCIPisFeasLT(scip, objsol, SCIPgetCutoffbound(scip)) ) 264 { 265 SCIP_Bool stored; 266 267 /* create a new solution */ 268 SCIP_CALL( createNewSol(scip, heur, sol, &stored) ); 269 270 if( stored ) 271 { 272 nsolsadded++; 273 #ifdef SCIP_MORE_DEBUG 274 nsolsaddedrun++; 275 #endif 276 heurdata->nimprovingsols++; 277 } 278 } 279 280 nchecksols--; 281 heurdata->ncheckedsols++; 282 } 283 } 284 #ifdef SCIP_MORE_DEBUG 285 printf(">> heuristic <%s> found %d of %d improving solutions from run %d.\n", HEUR_NAME, nsolsaddedrun, nsols, run); 286 #endif 287 } 288 289 SCIPdebugMsg(scip, ">> heuristic <%s> found %d improving solutions.\n", HEUR_NAME, nsolsadded); 290 291 if( nsolsadded > 0 ) 292 *result = SCIP_FOUNDSOL; 293 else 294 *result = SCIP_DIDNOTFIND; 295 296 /* reset the marks of the checked solutions */ 297 SCIPresetReoptSolMarks(scip); 298 299 /* free the buffer array */ 300 SCIPfreeBufferArray(scip, &sols); 301 302 return SCIP_OKAY; 303 } 304 305 306 /* 307 * primal heuristic specific interface methods 308 */ 309 310 /* returns the number of checked solutions */ 311 int SCIPreoptsolsGetNCheckedsols( 312 SCIP* scip 313 ) 314 { 315 SCIP_HEUR* heur; 316 SCIP_HEURDATA* heurdata; 317 318 assert(scip != NULL); 319 320 heur = SCIPfindHeur(scip, HEUR_NAME); 321 assert(heur != NULL); 322 323 heurdata = SCIPheurGetData(heur); 324 assert(heurdata != NULL); 325 326 return heurdata->ncheckedsols; 327 } 328 329 /* returns the number of found improving solutions */ 330 int SCIPreoptsolsGetNImprovingsols( 331 SCIP* scip 332 ) 333 { 334 SCIP_HEUR* heur; 335 SCIP_HEURDATA* heurdata; 336 337 assert(scip != NULL); 338 339 heur = SCIPfindHeur(scip, HEUR_NAME); 340 assert(heur != NULL); 341 342 heurdata = SCIPheurGetData(heur); 343 assert(heurdata != NULL); 344 345 return heurdata->nimprovingsols; 346 } 347 348 /** creates the reoptsols primal heuristic and includes it in SCIP */ 349 SCIP_RETCODE SCIPincludeHeurReoptsols( 350 SCIP* scip /**< SCIP data structure */ 351 ) 352 { 353 SCIP_HEURDATA* heurdata; 354 SCIP_HEUR* heur; 355 356 /* create reoptsols primal heuristic data */ 357 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 358 359 /* include primal heuristic */ 360 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 361 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 362 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecReoptsols, heurdata) ); 363 364 assert(heur != NULL); 365 366 /* set non fundamental callbacks via setter functions */ 367 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyReoptsols) ); 368 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeReoptsols) ); 369 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitReoptsols) ); 370 371 /* parameters */ 372 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxsols", "maximal number solutions which should be checked. (-1: all)", 373 &heurdata->maxsols, TRUE, 1000, -1, INT_MAX, NULL, NULL) ); 374 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxruns", "check solutions of the last k runs. (-1: all)", 375 &heurdata->maxruns, TRUE, -1, -1, INT_MAX, NULL, NULL) ); 376 377 return SCIP_OKAY; 378 } 379