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