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