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