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