1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 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
applyBoundChanges(SCIP * scip,SCIP_PROPDATA * data,SCIP_RESULT * result,int * ntightened,int * ntightenedint)76 SCIP_RETCODE applyBoundChanges(
77 SCIP* scip,
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
93 SCIPdisableConcurrentBoundStorage(scip);
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;
131 SCIPenableConcurrentBoundStorage(scip);
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
SCIP_DECL_PROPFREE(propFreeSync)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
SCIP_DECL_PROPINIT(propInitSync)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
SCIP_DECL_PROPEXIT(propExitSync)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
SCIP_DECL_PROPPRESOL(propPresolSync)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
SCIP_DECL_PROPEXEC(propExecSync)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 */
SCIPincludePropSync(SCIP * scip)278 SCIP_RETCODE SCIPincludePropSync(
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 */
297 SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING,
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) );
306 SCIP_CALL( SCIPsetPropPresol(scip, prop, propPresolSync, PROP_PRESOL_PRIORITY, PROP_PRESOL_MAXROUNDS, PROP_PRESOLTIMING) );
307
308 return SCIP_OKAY;
309 }
310
311
312 /** adds a boundchange to the sync propagator */
SCIPpropSyncAddBndchg(SCIP * scip,SCIP_PROP * prop,SCIP_VAR * var,SCIP_Real val,SCIP_BOUNDTYPE bndtype)313 SCIP_RETCODE SCIPpropSyncAddBndchg(
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 */
SCIPpropSyncGetNTightenedBnds(SCIP_PROP * prop)353 SCIP_Longint SCIPpropSyncGetNTightenedBnds(
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 */
SCIPpropSyncGetNTightenedIntBnds(SCIP_PROP * prop)368 SCIP_Longint SCIPpropSyncGetNTightenedIntBnds(
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 }
381