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