Scippy

SCIP

Solving Constraint Integer Programs

prop_sync.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 prop_sync.c
17  * @brief propagator for applying global bound changes that were communicated by other
18  * concurrent solvers
19  * @author Robert Lion Gottwald
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include <assert.h>
25 #include <string.h>
26 #include "scip/prop_sync.h"
27 #include "scip/concurrent.h"
28 #include "tpi/tpi.h"
29 
30 /* fundamental propagator properties */
31 #define PROP_NAME "sync"
32 #define PROP_DESC "propagator for synchronization of bound changes"
33 #define PROP_PRIORITY (INT_MAX/4) /**< propagator priority */
34 #define PROP_FREQ -1 /**< propagator frequency */
35 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
36 #define PROP_TIMING SCIP_PROPTIMING_ALWAYS /**< propagation timing mask */
37 
38 #define PROP_PRESOL_PRIORITY (INT_MAX/4) /**< priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers */
39 #define PROP_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS /* timing of the presolving method (fast, medium, or exhaustive) */
40 #define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no
41  * limit) */
42 
43 /*
44  * Data structures
45  */
46 
47 /** propagator data */
48 struct SCIP_PropData
49 {
50  SCIP_VAR** bndvar; /**< array of variables with a bound change */
51  SCIP_Real* bndval; /**< array of new bound values */
52  SCIP_BOUNDTYPE* bndtype; /**< array of bound types */
53  int nbnds; /**< number of boundchanges */
54  int bndsize; /**< current size of bound change array */
55  SCIP_Longint ntightened; /**< number of tightened bounds */
56  SCIP_Longint ntightenedint; /**< number of tightened bounds of integer variables */
57 };
58 
59 
60 /*
61  * Local methods
62  */
63 
64 /* put your local methods here, and declare them static */
65 
66 static
69  SCIP_PROPDATA* data,
70  SCIP_RESULT* result,
71  int* ntightened,
72  int* ntightenedint
73  )
74 {
75  int i;
76 
77  assert(data != NULL);
78  assert(ntightened != NULL);
79  assert(ntightenedint != NULL);
80 
81  *ntightened = 0;
82  *ntightenedint = 0;
83 
85  *result = SCIP_DIDNOTFIND;
86 
87  for( i = 0; i < data->nbnds; ++i )
88  {
89  SCIP_Bool infeas, tightened;
90  SCIP_CALL( SCIPvarGetProbvarBound(&data->bndvar[i], &data->bndval[i], &data->bndtype[i]) );
91 
92  /* cannot change bounds of multi-aggregated variables so skip this bound-change */
93  if( SCIPvarGetStatus(data->bndvar[i]) == SCIP_VARSTATUS_MULTAGGR )
94  continue;
95 
96  if( data->bndtype[i] == SCIP_BOUNDTYPE_LOWER )
97  {
98  SCIP_CALL( SCIPtightenVarLbGlobal(scip, data->bndvar[i], data->bndval[i], FALSE, &infeas, &tightened) );
99  }
100  else
101  {
102  assert(data->bndtype[i] == SCIP_BOUNDTYPE_UPPER);
103  SCIP_CALL( SCIPtightenVarUbGlobal(scip, data->bndvar[i], data->bndval[i], FALSE, &infeas, &tightened) );
104  }
105  if( tightened )
106  {
107  ++(*ntightened);
108  if( SCIPvarGetType(data->bndvar[i]) <= SCIP_VARTYPE_INTEGER )
109  ++(*ntightenedint);
110  }
111  if( infeas )
112  {
113 #ifndef NDEBUG
114  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "sync propagator found cutoff in thread %i\n", SCIPtpiGetThreadNum());
115 #endif
116  *result = SCIP_CUTOFF;
117  break;
118  }
119  }
120 
121  data->nbnds = 0;
123 
124  return SCIP_OKAY;
125 }
126 
127 
128 /*
129  * Callback methods of propagator
130  */
131 
132 /** destructor of propagator to free user data (called when SCIP is exiting) */
133 static
134 SCIP_DECL_PROPFREE(propFreeSync)
135 { /*lint --e{715}*/
136  SCIP_PROPDATA* propdata;
137 
138  assert(scip != NULL);
139  assert(prop != NULL);
140  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
141 
142  propdata = SCIPpropGetData(prop);
143  assert(propdata != NULL);
144 
145  SCIPfreeMemory(scip, &propdata);
146  SCIPpropSetData(prop, NULL);
147 
148  return SCIP_OKAY;
149 }
150 
151 /** initialization method of propagator (called after problem was transformed) */
152 static
153 SCIP_DECL_PROPINIT(propInitSync)
154 { /*lint --e{715}*/
155  SCIP_PROPDATA* data;
156 
157  assert(prop != NULL);
158  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
159 
160  data = SCIPpropGetData(prop);
161  assert(data != NULL);
162 
163  data->bndsize = 0;
164  data->nbnds = 0;
165  data->bndvar = NULL;
166  data->bndval = NULL;
167  data->bndtype = NULL;
168  data->ntightened = 0;
169  data->ntightenedint = 0;
170 
171  return SCIP_OKAY;
172 }
173 
174 /** deinitialization method of propagator (called before transformed problem is freed) */
175 static
176 SCIP_DECL_PROPEXIT(propExitSync)
177 { /*lint --e{715}*/
178  SCIP_PROPDATA* data;
179 
180  assert(prop != NULL);
181  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
182 
183  data = SCIPpropGetData(prop);
184  assert(data != NULL);
185 
186  SCIPfreeBlockMemoryArrayNull(scip, &data->bndvar, data->bndsize);
187  SCIPfreeBlockMemoryArrayNull(scip, &data->bndval, data->bndsize);
188  SCIPfreeBlockMemoryArrayNull(scip, &data->bndtype, data->bndsize);
189 
190  return SCIP_OKAY;
191 }
192 
193 static
194 SCIP_DECL_PROPPRESOL(propPresolSync)
195 { /*lint --e{715}*/
196  SCIP_PROPDATA* data;
197  int ntightened;
198  int ntightenedint;
199 
200  assert(prop != NULL);
201  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
202 
203  data = SCIPpropGetData(prop);
204  assert(data != NULL);
205 
206  *result = SCIP_DIDNOTRUN;
207 
208  if( data->nbnds == 0 || SCIPinProbing(scip) )
209  return SCIP_OKAY;
210 
211  /* remember number of tightened bounds before applying new bound tightenings */
212 
213  SCIP_CALL( applyBoundChanges(scip, data, result, &ntightened, &ntightenedint) );
214 
215  /* add number of tightened bounds to the total number of presolving boundchanges */
216  if( ntightened > 0 )
217  {
218  *nchgbds += ntightened;
219  data->ntightened += ntightened;
220  data->ntightenedint += ntightened;
221  if( *result != SCIP_CUTOFF )
222  *result = SCIP_SUCCESS;
223  }
224 
225  SCIPpropSetFreq(prop, -1);
226 
227  return SCIP_OKAY;
228 }
229 
230 /** execution method of propagator */
231 static
232 SCIP_DECL_PROPEXEC(propExecSync)
233 { /*lint --e{715}*/
234  SCIP_PROPDATA* data;
235  int ntightened;
236  int ntightenedint;
237 
238  assert(prop != NULL);
239  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
240 
241  *result = SCIP_DIDNOTRUN;
242 
243  if( SCIPinProbing(scip) )
244  return SCIP_OKAY;
245 
246  data = SCIPpropGetData(prop);
247  assert(data != NULL);
248 
249  SCIP_CALL( applyBoundChanges(scip, data, result, &ntightened, &ntightenedint) );
250 
251  if( ntightened > 0 )
252  {
253  data->ntightened += ntightened;
254  data->ntightenedint += ntightenedint;
255  if( *result != SCIP_CUTOFF )
256  *result = SCIP_REDUCEDDOM;
257  }
258 
259  SCIPpropSetFreq(prop, -1);
260 
261  return SCIP_OKAY;
262 }
263 
264 /*
265  * propagator specific interface methods
266  */
267 
268 /** creates the sync propagator and includes it in SCIP */
270  SCIP* scip /**< SCIP data structure */
271  )
272 {
273  SCIP_PROPDATA* propdata;
274  SCIP_PROP* prop;
275 
276  /* create xyz propagator data */
277  propdata = NULL;
278  /* create propagator specific data */
279  SCIP_CALL( SCIPallocMemory(scip, &propdata) );
280 
281  prop = NULL;
282 
283  /* include propagator */
284 
285  /* use SCIPincludePropBasic() plus setter functions if you want to set callbacks one-by-one and your code should
286  * compile independent of new callbacks being added in future SCIP versions
287  */
289  propExecSync, propdata) );
290 
291  assert(prop != NULL);
292 
293  /* set optional callbacks via setter functions */
294  SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeSync) );
295  SCIP_CALL( SCIPsetPropInit(scip, prop, propInitSync) );
296  SCIP_CALL( SCIPsetPropExit(scip, prop, propExitSync) );
298 
299  return SCIP_OKAY;
300 }
301 
302 
303 /** adds a boundchange to the sync propagator */
305  SCIP* scip, /**< SCIP data structure */
306  SCIP_PROP* prop, /**< sync propagator */
307  SCIP_VAR* var, /**< variable for bound */
308  SCIP_Real val, /**< value of bound */
309  SCIP_BOUNDTYPE bndtype /**< type of bound */
310  )
311 {
312  SCIP_PROPDATA* data;
313 
314  assert(prop != NULL);
315  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
316 
317  data = SCIPpropGetData(prop);
318  assert(data != NULL);
319 
320  if( data->nbnds + 1 > data->bndsize )
321  {
322  int newsize;
323  newsize = SCIPcalcMemGrowSize(scip, data->nbnds+1);
324  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &data->bndvar, data->bndsize, newsize) );
325  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &data->bndval, data->bndsize, newsize) );
326  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &data->bndtype, data->bndsize, newsize) );
327  data->bndsize = newsize;
328  }
329 
330  data->bndvar[data->nbnds] = var;
331  data->bndval[data->nbnds] = val;
332  data->bndtype[data->nbnds] = bndtype;
333 
334  if( data->nbnds == 0 )
335  {
336  SCIPpropSetFreq(prop, 1);
337  }
338  ++data->nbnds;
339 
340  return SCIP_OKAY;
341 }
342 
343 /** gives the total number of tightened bounds found by the sync propagator */
345  SCIP_PROP* prop /**< sync propagator */
346  )
347 {
348  SCIP_PROPDATA* data;
349 
350  assert(prop != NULL);
351 
352  data = SCIPpropGetData(prop);
353  assert(data != NULL);
354 
355  return data->ntightened;
356 }
357 
358 /** gives the total number of tightened bounds for integer variables found by the sync propagator */
360  SCIP_PROP* prop /**< sync propagator */
361  )
362 {
363  SCIP_PROPDATA* data;
364 
365  assert(prop != NULL);
366 
367  data = SCIPpropGetData(prop);
368  assert(data != NULL);
369 
370  return data->ntightenedint;
371 }
#define PROP_PRESOLTIMING
Definition: prop_sync.c:39
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip.c:7773
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip.h:21964
#define PROP_TIMING
Definition: prop_sync.c:36
SCIP_Longint SCIPpropSyncGetNTightenedBnds(SCIP_PROP *prop)
Definition: prop_sync.c:345
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip.c:45835
#define PROP_NAME
Definition: prop_sync.c:31
#define FALSE
Definition: def.h:64
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define PROP_PRESOL_MAXROUNDS
Definition: prop_sync.c:40
static SCIP_DECL_PROPFREE(propFreeSync)
Definition: prop_sync.c:135
static SCIP_DECL_PROPEXEC(propExecSync)
Definition: prop_sync.c:233
void SCIPdisableConcurrentBoundStorage(SCIP *scip)
Definition: concurrent.c:254
#define SCIPallocMemory(scip, ptr)
Definition: scip.h:21922
the type definitions for the SCIP parallel interface
SCIP_RETCODE SCIPtightenVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:23229
#define NULL
Definition: lpi_spx1.cpp:137
#define SCIP_CALL(x)
Definition: def.h:316
SCIP_RETCODE SCIPincludePropSync(SCIP *scip)
Definition: prop_sync.c:270
SCIP_RETCODE SCIPpropSyncAddBndchg(SCIP *scip, SCIP_PROP *prop, SCIP_VAR *var, SCIP_Real val, SCIP_BOUNDTYPE bndtype)
Definition: prop_sync.c:305
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip.c:1353
SCIP_RETCODE SCIPsetPropInit(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINIT((*propinit)))
Definition: scip.c:7677
#define SCIP_Bool
Definition: def.h:61
#define PROP_FREQ
Definition: prop_sync.c:34
void SCIPenableConcurrentBoundStorage(SCIP *scip)
Definition: concurrent.c:266
propagator for applying global bound changes that were communicated by other concurrent solvers ...
static SCIP_DECL_PROPEXIT(propExitSync)
Definition: prop_sync.c:177
helper functions for concurrent scip solvers
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:35163
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:887
static SCIP_RETCODE applyBoundChanges(SCIP *scip, SCIP_PROPDATA *data, SCIP_RESULT *result, int *ntightened, int *ntightenedint)
Definition: prop_sync.c:68
static SCIP_DECL_PROPPRESOL(propPresolSync)
Definition: prop_sync.c:195
SCIP_RETCODE SCIPvarGetProbvarBound(SCIP_VAR **var, SCIP_Real *bound, SCIP_BOUNDTYPE *boundtype)
Definition: var.c:11775
void SCIPpropSetFreq(SCIP_PROP *prop, int freq)
Definition: prop.c:990
#define SCIPfreeMemory(scip, ptr)
Definition: scip.h:21938
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16674
SCIP_Longint SCIPpropSyncGetNTightenedIntBnds(SCIP_PROP *prop)
Definition: prop_sync.c:360
#define SCIP_Real
Definition: def.h:145
static SCIP_DECL_PROPINIT(propInitSync)
Definition: prop_sync.c:154
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:38
#define PROP_DESC
Definition: prop_sync.c:32
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip.c:7661
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
Definition: prop.c:735
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
Definition: prop.c:745
int SCIPtpiGetThreadNum(void)
Definition: tpi_openmp.c:331
#define SCIP_Longint
Definition: def.h:130
#define PROP_PRESOL_PRIORITY
Definition: prop_sync.c:38
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16720
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip.h:21976
SCIP_RETCODE SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:23349
#define PROP_DELAY
Definition: prop_sync.c:35
SCIP_RETCODE SCIPsetPropExit(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXIT((*propexit)))
Definition: scip.c:7693
SCIP_RETCODE SCIPincludePropBasic(SCIP *scip, SCIP_PROP **propptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool delay, SCIP_PROPTIMING timingmask, SCIP_DECL_PROPEXEC((*propexec)), SCIP_PROPDATA *propdata)
Definition: scip.c:7608
#define PROP_PRIORITY
Definition: prop_sync.c:33