SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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-2023 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/* fundamental propagator properties */
49#define PROP_NAME "sync"
50#define PROP_DESC "propagator for synchronization of bound changes"
51#define PROP_PRIORITY (INT_MAX/4) /**< propagator priority */
52#define PROP_FREQ -1 /**< propagator frequency */
53#define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
54#define PROP_TIMING SCIP_PROPTIMING_ALWAYS /**< propagation timing mask */
55
56#define PROP_PRESOL_PRIORITY (INT_MAX/4) /**< priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers */
57#define PROP_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS /* timing of the presolving method (fast, medium, or exhaustive) */
58#define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no
59 * limit) */
60
61/*
62 * Data structures
63 */
64
65/** propagator data */
66struct SCIP_PropData
67{
68 SCIP_VAR** bndvar; /**< array of variables with a bound change */
69 SCIP_Real* bndval; /**< array of new bound values */
70 SCIP_BOUNDTYPE* bndtype; /**< array of bound types */
71 int nbnds; /**< number of boundchanges */
72 int bndsize; /**< current size of bound change array */
73 SCIP_Longint ntightened; /**< number of tightened bounds */
74 SCIP_Longint ntightenedint; /**< number of tightened bounds of integer variables */
75};
76
77
78/*
79 * Local methods
80 */
81
82/* put your local methods here, and declare them static */
83
84static
86 SCIP* scip,
87 SCIP_PROPDATA* data,
89 int* ntightened,
90 int* ntightenedint
91 )
92{
93 int i;
94
95 assert(data != NULL);
96 assert(ntightened != NULL);
97 assert(ntightenedint != NULL);
98
99 *ntightened = 0;
100 *ntightenedint = 0;
101
104
105 for( i = 0; i < data->nbnds; ++i )
106 {
107 SCIP_Bool infeas, tightened;
108 SCIP_CALL( SCIPvarGetProbvarBound(&data->bndvar[i], &data->bndval[i], &data->bndtype[i]) );
109
110 /* cannot change bounds of multi-aggregated variables so skip this bound-change */
111 if( SCIPvarGetStatus(data->bndvar[i]) == SCIP_VARSTATUS_MULTAGGR )
112 continue;
113
114 if( data->bndtype[i] == SCIP_BOUNDTYPE_LOWER )
115 {
116 SCIP_CALL( SCIPtightenVarLbGlobal(scip, data->bndvar[i], data->bndval[i], FALSE, &infeas, &tightened) );
117 }
118 else
119 {
120 assert(data->bndtype[i] == SCIP_BOUNDTYPE_UPPER);
121 SCIP_CALL( SCIPtightenVarUbGlobal(scip, data->bndvar[i], data->bndval[i], FALSE, &infeas, &tightened) );
122 }
123 if( tightened )
124 {
125 ++(*ntightened);
126 if( SCIPvarGetType(data->bndvar[i]) <= SCIP_VARTYPE_INTEGER )
127 ++(*ntightenedint);
128 }
129 if( infeas )
130 {
131#ifndef NDEBUG
132 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "sync propagator found cutoff in thread %i\n", SCIPtpiGetThreadNum());
133#endif
135 break;
136 }
137 }
138
139 data->nbnds = 0;
141
142 return SCIP_OKAY;
143}
144
145
146/*
147 * Callback methods of propagator
148 */
149
150/** destructor of propagator to free user data (called when SCIP is exiting) */
151static
153{ /*lint --e{715}*/
154 SCIP_PROPDATA* propdata;
155
156 assert(scip != NULL);
157 assert(prop != NULL);
159
160 propdata = SCIPpropGetData(prop);
161 assert(propdata != NULL);
162
163 SCIPfreeMemory(scip, &propdata);
164 SCIPpropSetData(prop, NULL);
165
166 return SCIP_OKAY;
167}
168
169/** initialization method of propagator (called after problem was transformed) */
170static
172{ /*lint --e{715}*/
173 SCIP_PROPDATA* data;
174
175 assert(prop != NULL);
177
178 data = SCIPpropGetData(prop);
179 assert(data != NULL);
180
181 data->bndsize = 0;
182 data->nbnds = 0;
183 data->bndvar = NULL;
184 data->bndval = NULL;
185 data->bndtype = NULL;
186 data->ntightened = 0;
187 data->ntightenedint = 0;
188
189 return SCIP_OKAY;
190}
191
192/** deinitialization method of propagator (called before transformed problem is freed) */
193static
195{ /*lint --e{715}*/
196 SCIP_PROPDATA* data;
197
198 assert(prop != NULL);
200
201 data = SCIPpropGetData(prop);
202 assert(data != NULL);
203
204 SCIPfreeBlockMemoryArrayNull(scip, &data->bndvar, data->bndsize);
205 SCIPfreeBlockMemoryArrayNull(scip, &data->bndval, data->bndsize);
206 SCIPfreeBlockMemoryArrayNull(scip, &data->bndtype, data->bndsize);
207
208 return SCIP_OKAY;
209}
210
211static
213{ /*lint --e{715}*/
214 SCIP_PROPDATA* data;
215 int ntightened;
216 int ntightenedint;
217
218 assert(prop != NULL);
220
221 data = SCIPpropGetData(prop);
222 assert(data != NULL);
223
225
226 if( data->nbnds == 0 || SCIPinProbing(scip) )
227 return SCIP_OKAY;
228
229 /* remember number of tightened bounds before applying new bound tightenings */
230
231 SCIP_CALL( applyBoundChanges(scip, data, result, &ntightened, &ntightenedint) );
232
233 /* add number of tightened bounds to the total number of presolving boundchanges */
234 if( ntightened > 0 )
235 {
236 *nchgbds += ntightened;
237 data->ntightened += ntightened;
238 data->ntightenedint += ntightened;
239 if( *result != SCIP_CUTOFF )
241 }
242
243 SCIPpropSetFreq(prop, -1);
244
245 return SCIP_OKAY;
246}
247
248/** execution method of propagator */
249static
251{ /*lint --e{715}*/
252 SCIP_PROPDATA* data;
253 int ntightened;
254 int ntightenedint;
255
256 assert(prop != NULL);
258
260
261 if( SCIPinProbing(scip) )
262 return SCIP_OKAY;
263
264 data = SCIPpropGetData(prop);
265 assert(data != NULL);
266
267 SCIP_CALL( applyBoundChanges(scip, data, result, &ntightened, &ntightenedint) );
268
269 if( ntightened > 0 )
270 {
271 data->ntightened += ntightened;
272 data->ntightenedint += ntightenedint;
273 if( *result != SCIP_CUTOFF )
275 }
276
277 SCIPpropSetFreq(prop, -1);
278
279 return SCIP_OKAY;
280}
281
282/*
283 * propagator specific interface methods
284 */
285
286/** creates the sync propagator and includes it in SCIP */
288 SCIP* scip /**< SCIP data structure */
289 )
290{
291 SCIP_PROPDATA* propdata;
292 SCIP_PROP* prop;
293
294 /* create xyz propagator data */
295 propdata = NULL;
296 /* create propagator specific data */
297 SCIP_CALL( SCIPallocMemory(scip, &propdata) );
298
299 prop = NULL;
300
301 /* include propagator */
302
303 /* use SCIPincludePropBasic() plus setter functions if you want to set callbacks one-by-one and your code should
304 * compile independent of new callbacks being added in future SCIP versions
305 */
307 propExecSync, propdata) );
308
309 assert(prop != NULL);
310
311 /* set optional callbacks via setter functions */
316
317 return SCIP_OKAY;
318}
319
320
321/** adds a boundchange to the sync propagator */
323 SCIP* scip, /**< SCIP data structure */
324 SCIP_PROP* prop, /**< sync propagator */
325 SCIP_VAR* var, /**< variable for bound */
326 SCIP_Real val, /**< value of bound */
327 SCIP_BOUNDTYPE bndtype /**< type of bound */
328 )
329{
330 SCIP_PROPDATA* data;
331
332 assert(prop != NULL);
334
335 data = SCIPpropGetData(prop);
336 assert(data != NULL);
337
338 if( data->nbnds + 1 > data->bndsize )
339 {
340 int newsize;
341 newsize = SCIPcalcMemGrowSize(scip, data->nbnds+1);
342 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &data->bndvar, data->bndsize, newsize) );
343 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &data->bndval, data->bndsize, newsize) );
344 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &data->bndtype, data->bndsize, newsize) );
345 data->bndsize = newsize;
346 }
347
348 data->bndvar[data->nbnds] = var;
349 data->bndval[data->nbnds] = val;
350 data->bndtype[data->nbnds] = bndtype;
351
352 if( data->nbnds == 0 )
353 {
354 SCIPpropSetFreq(prop, 1);
355 }
356 ++data->nbnds;
357
358 return SCIP_OKAY;
359}
360
361/** gives the total number of tightened bounds found by the sync propagator */
363 SCIP_PROP* prop /**< sync propagator */
364 )
365{
366 SCIP_PROPDATA* data;
367
368 assert(prop != NULL);
369
370 data = SCIPpropGetData(prop);
371 assert(data != NULL);
372
373 return data->ntightened;
374}
375
376/** gives the total number of tightened bounds for integer variables found by the sync propagator */
378 SCIP_PROP* prop /**< sync propagator */
379 )
380{
381 SCIP_PROPDATA* data;
382
383 assert(prop != NULL);
384
385 data = SCIPpropGetData(prop);
386 assert(data != NULL);
387
388 return data->ntightenedint;
389}
void SCIPenableConcurrentBoundStorage(SCIP *scip)
Definition concurrent.c:275
void SCIPdisableConcurrentBoundStorage(SCIP *scip)
Definition concurrent.c:263
helper functions for concurrent scip solvers
#define FALSE
Definition def.h:96
#define SCIP_CALL(x)
Definition def.h:388
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
SCIP_Longint SCIPpropSyncGetNTightenedBnds(SCIP_PROP *prop)
Definition prop_sync.c:362
SCIP_RETCODE SCIPpropSyncAddBndchg(SCIP *scip, SCIP_PROP *prop, SCIP_VAR *var, SCIP_Real val, SCIP_BOUNDTYPE bndtype)
Definition prop_sync.c:322
SCIP_Longint SCIPpropSyncGetNTightenedIntBnds(SCIP_PROP *prop)
Definition prop_sync.c:377
SCIP_RETCODE SCIPincludePropSync(SCIP *scip)
Definition prop_sync.c:287
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)
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 SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop,)
Definition scip_prop.c:167
void SCIPpropSetFreq(SCIP_PROP *prop, int freq)
Definition prop.c:1044
SCIP_RETCODE SCIPsetPropInit(SCIP *scip, SCIP_PROP *prop,)
Definition scip_prop.c:183
SCIP_RETCODE SCIPsetPropExit(SCIP *scip, SCIP_PROP *prop,)
Definition scip_prop.c:199
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:12458
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:17360
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17406
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
return SCIP_OKAY
assert(minobj< SCIPgetCutoffbound(scip))
SCIP_VAR * var
#define NULL
Definition lpi_spx1.cpp:161
memory allocation routines
#define PROP_PRESOL_MAXROUNDS
Definition prop_sync.c:58
#define PROP_PRESOLTIMING
Definition prop_sync.c:57
#define PROP_DESC
Definition prop_sync.c:50
#define PROP_NAME
Definition prop_sync.c:49
static SCIP_RETCODE applyBoundChanges(SCIP *scip, SCIP_PROPDATA *data, SCIP_RESULT *result, int *ntightened, int *ntightenedint)
Definition prop_sync.c:85
#define PROP_DELAY
Definition prop_sync.c:53
#define PROP_TIMING
Definition prop_sync.c:54
#define PROP_FREQ
Definition prop_sync.c:52
#define PROP_PRIORITY
Definition prop_sync.c:51
#define PROP_PRESOL_PRIORITY
Definition prop_sync.c:56
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_openmp.c:349
@ 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
#define SCIP_DECL_PROPINIT(x)
Definition type_prop.h:77
#define SCIP_DECL_PROPFREE(x)
Definition type_prop.h:69
#define SCIP_DECL_PROPEXIT(x)
Definition type_prop.h:85
#define SCIP_DECL_PROPPRESOL(x)
Definition type_prop.h:193
struct SCIP_PropData SCIP_PROPDATA
Definition type_prop.h:52
#define SCIP_DECL_PROPEXEC(x)
Definition type_prop.h:217
@ 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
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_INTEGER
Definition type_var.h:63
@ SCIP_VARSTATUS_MULTAGGR
Definition type_var.h:54