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
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 */
67struct 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
85static
87 SCIP* scip,
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) */
152static
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) */
171static
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) */
194static
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
212static
213SCIP_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 */
250static
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}
void SCIPenableConcurrentBoundStorage(SCIP *scip)
Definition: concurrent.c:276
void SCIPdisableConcurrentBoundStorage(SCIP *scip)
Definition: concurrent.c:264
helper functions for concurrent scip solvers
#define NULL
Definition: def.h:267
#define SCIP_Longint
Definition: def.h:158
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define FALSE
Definition: def.h:94
#define SCIP_CALL(x)
Definition: def.h:374
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
SCIP_Longint SCIPpropSyncGetNTightenedBnds(SCIP_PROP *prop)
Definition: prop_sync.c:363
SCIP_RETCODE SCIPpropSyncAddBndchg(SCIP *scip, SCIP_PROP *prop, SCIP_VAR *var, SCIP_Real val, SCIP_BOUNDTYPE bndtype)
Definition: prop_sync.c:323
SCIP_Longint SCIPpropSyncGetNTightenedIntBnds(SCIP_PROP *prop)
Definition: prop_sync.c:378
SCIP_RETCODE SCIPincludePropSync(SCIP *scip)
Definition: prop_sync.c:288
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:60
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:78
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:97
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
Definition: prop.c:799
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
Definition: prop.c:789
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_prop.c:279
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:941
SCIP_RETCODE SCIPsetPropExit(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXIT((*propexit)))
Definition: scip_prop.c:199
void SCIPpropSetFreq(SCIP_PROP *prop, int freq)
Definition: prop.c:1044
SCIP_RETCODE SCIPsetPropInit(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINIT((*propinit)))
Definition: scip_prop.c:183
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:167
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
SCIP_RETCODE SCIPvarGetProbvarBound(SCIP_VAR **var, SCIP_Real *bound, SCIP_BOUNDTYPE *boundtype)
Definition: var.c:12469
SCIP_RETCODE SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6348
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17538
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
SCIP_RETCODE SCIPtightenVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6228
memory allocation routines
#define PROP_PRESOL_MAXROUNDS
Definition: prop_sync.c:59
#define PROP_PRESOLTIMING
Definition: prop_sync.c:58
#define PROP_DESC
Definition: prop_sync.c:51
static SCIP_DECL_PROPFREE(propFreeSync)
Definition: prop_sync.c:153
static SCIP_DECL_PROPEXEC(propExecSync)
Definition: prop_sync.c:251
#define PROP_NAME
Definition: prop_sync.c:50
static SCIP_DECL_PROPINIT(propInitSync)
Definition: prop_sync.c:172
static SCIP_DECL_PROPEXIT(propExitSync)
Definition: prop_sync.c:195
static SCIP_RETCODE applyBoundChanges(SCIP *scip, SCIP_PROPDATA *data, SCIP_RESULT *result, int *ntightened, int *ntightenedint)
Definition: prop_sync.c:86
#define PROP_DELAY
Definition: prop_sync.c:54
static SCIP_DECL_PROPPRESOL(propPresolSync)
Definition: prop_sync.c:213
#define PROP_TIMING
Definition: prop_sync.c:55
#define PROP_FREQ
Definition: prop_sync.c:53
#define PROP_PRIORITY
Definition: prop_sync.c:52
#define PROP_PRESOL_PRIORITY
Definition: prop_sync.c:57
propagator for applying global bound changes that were communicated by other concurrent solvers
public methods for message output
public methods for propagators
public methods for problem variables
public methods for memory management
public methods for message handling
public methods for the probing mode
public methods for propagator plugins
public methods for SCIP variables
the type definitions for the SCIP parallel interface
int SCIPtpiGetThreadNum(void)
Definition: tpi_none.c:141
@ SCIP_BOUNDTYPE_UPPER
Definition: type_lp.h:57
@ SCIP_BOUNDTYPE_LOWER
Definition: type_lp.h:56
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
@ SCIP_VERBLEVEL_FULL
Definition: type_message.h:57
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:52
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_REDUCEDDOM
Definition: type_result.h:51
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_SUCCESS
Definition: type_result.h:58
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_VARTYPE_INTEGER
Definition: type_var.h:63
@ SCIP_VARSTATUS_MULTAGGR
Definition: type_var.h:54