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-2020 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
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
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 */
121 
122  return SCIP_OKAY;
123 }
124 
125 /* free data of the heuristic */
126 static
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 */
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
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
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 
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 */
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 */
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 */
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 */
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,
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 }
int SCIPreoptsolsGetNImprovingsols(SCIP *scip)
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1429
public methods for SCIP parameter handling
void SCIPresetReoptSolMarks(SCIP *scip)
Definition: scip_solve.c:3482
public methods for memory management
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1340
SCIP_Bool SCIPisReoptEnabled(SCIP *scip)
Definition: scip_solve.c:3446
SCIP_Real SCIPgetReoptSimilarity(SCIP *scip, int run1, int run2)
Definition: scip_reopt.c:398
#define HEUR_PRIORITY
public solving methods
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:241
#define FALSE
Definition: def.h:73
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPrecomputeSolObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1514
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
#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:185
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:249
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:320
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:108
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:1350
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:364
#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:298
#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:1255
#define SCIP_Bool
Definition: def.h:70
#define MAX(x, y)
Definition: tclique_def.h:83
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:1390
#define HEUR_NAME
SCIP_RETCODE SCIPgetReoptSolsRun(SCIP *scip, int run, SCIP_SOL **sols, int solssize, int *nsols)
Definition: scip_solve.c:3456
#define HEUR_TIMING
public methods for solutions
#define HEUR_MAXDEPTH
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
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:1860
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1483
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:74
#define HEUR_FREQOFS
#define SCIP_Real
Definition: def.h:163
public methods for message handling
#define SCIP_INVALID
Definition: def.h:183
static SCIP_DECL_HEURFREE(heurFreeReoptsols)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
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:3231
public methods for global and local (sub)problems
#define HEUR_DESC
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
memory allocation routines