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