Scippy

SCIP

Solving Constraint Integer Programs

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-2024 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
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 */
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
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)
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 */
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 */
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 */
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 */
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,
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:267
public methods for SCIP parameter handling
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for memory management
SCIP_RETCODE SCIPgetReoptSolsRun(SCIP *scip, int run, SCIP_SOL **sols, int solssize, int *nsols)
Definition: scip_solve.c:3498
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:307
#define HEUR_PRIORITY
SCIP_RETCODE SCIPrecomputeSolObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1378
public solving methods
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1866
#define FALSE
Definition: def.h:94
#define TRUE
Definition: def.h:93
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
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
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
static SCIP_DECL_HEURINIT(heurInitReoptsols)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1374
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
#define SCIPdebugMsg
Definition: scip_message.h:78
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
static SCIP_DECL_HEUREXEC(heurExecReoptsols)
public methods for numerical tolerances
public methods for querying solving statistics
#define HEUR_FREQ
SCIP_Bool SCIPisReoptEnabled(SCIP *scip)
Definition: scip_solve.c:3488
void SCIPresetReoptSolMarks(SCIP *scip)
Definition: scip_solve.c:3524
public methods for reoptimization
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1453
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip_heur.c:258
#define HEUR_DISPCHAR
int SCIPreoptsolsGetNCheckedsols(SCIP *scip)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1254
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol, SCIP_Bool *success)
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:250
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1347
#define SCIP_CALL(x)
Definition: def.h:380
#define HEUR_USESSUBSCIP
SCIP_RETCODE SCIPincludeHeurReoptsols(SCIP *scip)
public methods for primal heuristic plugins and divesets
int SCIPreoptsolsGetNImprovingsols(SCIP *scip)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIP_Bool
Definition: def.h:91
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:3050
static SCIP_DECL_HEURCOPY(heurCopyReoptsols)
SCIP_Real SCIPgetReoptSimilarity(SCIP *scip, int run1, int run2)
Definition: scip_reopt.c:407
reoptsols primal heuristic
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
#define HEUR_NAME
#define HEUR_TIMING
#define MAX(x, y)
Definition: def.h:239
public methods for solutions
int SCIPgetNReoptRuns(SCIP *scip)
#define HEUR_MAXDEPTH
public methods for message output
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:194
#define HEUR_FREQOFS
#define SCIP_Real
Definition: def.h:173
public methods for message handling
#define SCIP_INVALID
Definition: def.h:193
static SCIP_DECL_HEURFREE(heurFreeReoptsols)
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1119
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
public methods for primal heuristics
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1364
public methods for global and local (sub)problems
#define HEUR_DESC
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:184
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128
memory allocation routines