SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
heur_reoptsols.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2025 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
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"
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 */
68struct 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 */
85static
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 */
102
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) */
121static
122SCIP_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 */
130
131 return SCIP_OKAY;
132}
133
134/* free data of the heuristic */
135static
136SCIP_DECL_HEURFREE(heurFreeReoptsols)
137{
139
140 assert(scip != NULL );
141 assert(heur != NULL );
142
144 assert(heurdata != NULL );
145
147 SCIPheurSetData(heur, NULL);
148
149 return SCIP_OKAY;
150}
151
152
153/* initialize the heuristic */
154static SCIP_DECL_HEURINIT(heurInitReoptsols)
155{
157
158 assert(scip != NULL );
159 assert(heur != NULL );
160
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 */
171static
172SCIP_DECL_HEUREXEC(heurExecReoptsols)
173{/*lint --e{715}*/
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
192
194 return SCIP_OKAY;
195
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
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
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)
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 )
293 else
295
296 /* reset the marks of the checked solutions */
298
299 /* free the buffer array */
301
302 return SCIP_OKAY;
303}
304
305
306/*
307 * primal heuristic specific interface methods
308 */
309
310/* returns the number of checked solutions */
312 SCIP* scip
313 )
314{
315 SCIP_HEUR* heur;
317
318 assert(scip != NULL);
319
320 heur = SCIPfindHeur(scip, HEUR_NAME);
321 assert(heur != NULL);
322
324 assert(heurdata != NULL);
325
326 return heurdata->ncheckedsols;
327}
328
329/* returns the number of found improving solutions */
331 SCIP* scip
332 )
333{
334 SCIP_HEUR* heur;
336
337 assert(scip != NULL);
338
339 heur = SCIPfindHeur(scip, HEUR_NAME);
340 assert(heur != NULL);
341
343 assert(heurdata != NULL);
344
345 return heurdata->nimprovingsols;
346}
347
348/** creates the reoptsols primal heuristic and includes it in SCIP */
350 SCIP* scip /**< SCIP data structure */
351 )
352{
354 SCIP_HEUR* heur;
355
356 /* create reoptsols primal heuristic data */
358
359 /* include primal heuristic */
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}
#define NULL
Definition def.h:266
#define SCIP_INVALID
Definition def.h:192
#define SCIP_Bool
Definition def.h:91
#define SCIP_Real
Definition def.h:172
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define MAX(x, y)
Definition def.h:238
#define SCIP_CALL(x)
Definition def.h:373
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition scip_prob.c:1866
#define SCIPdebugMsg
int SCIPreoptsolsGetNCheckedsols(SCIP *scip)
int SCIPreoptsolsGetNImprovingsols(SCIP *scip)
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition scip_param.c:250
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:83
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition scip_param.c:307
SCIP_RETCODE SCIPincludeHeurReoptsols(SCIP *scip)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:178
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition heur.c:1364
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition scip_heur.c:117
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:162
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition scip_heur.c:258
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:194
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition heur.c:1453
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition heur.c:1374
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPreallocBufferArray(scip, ptr, num)
Definition scip_mem.h:128
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
void SCIPresetReoptSolMarks(SCIP *scip)
SCIP_Bool SCIPisReoptEnabled(SCIP *scip)
SCIP_RETCODE SCIPgetReoptSolsRun(SCIP *scip, int run, SCIP_SOL **sols, int solssize, int *nsols)
SCIP_Real SCIPgetReoptSimilarity(SCIP *scip, int run1, int run2)
Definition scip_reopt.c:407
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition scip_sol.c:1250
SCIP_RETCODE SCIPrecomputeSolObj(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1374
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition scip_sol.c:1115
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition scip_sol.c:3046
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1343
int SCIPgetNReoptRuns(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define HEUR_TIMING
return SCIP_OKAY
#define HEUR_FREQOFS
#define HEUR_DESC
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
#define HEUR_NAME
#define HEUR_FREQ
#define HEUR_USESSUBSCIP
SCIPcreateSol(scip, &heurdata->sol, heur))
static SCIP_SOL * sol
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol, SCIP_Bool *success)
reoptsols primal heuristic
static SCIP_VAR ** vars
memory allocation routines
public methods for primal heuristics
public methods for message output
public methods for primal heuristic plugins and divesets
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for reoptimization
public methods for solutions
public solving methods
public methods for querying solving statistics
#define SCIP_DECL_HEURCOPY(x)
Definition type_heur.h:97
struct SCIP_HeurData SCIP_HEURDATA
Definition type_heur.h:77
struct SCIP_Heur SCIP_HEUR
Definition type_heur.h:76
#define SCIP_DECL_HEURINIT(x)
Definition type_heur.h:113
#define SCIP_DECL_HEURFREE(x)
Definition type_heur.h:105
#define SCIP_DECL_HEUREXEC(x)
Definition type_heur.h:163
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_DIDNOTFIND
Definition type_result.h:44
@ SCIP_FOUNDSOL
Definition type_result.h:56
@ SCIP_INVALIDRESULT
enum SCIP_Retcode SCIP_RETCODE
struct Scip SCIP
Definition type_scip.h:39
struct SCIP_Sol SCIP_SOL
Definition type_sol.h:57
struct SCIP_Var SCIP_VAR
Definition type_var.h:119