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   	
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
86   	SCIP_RETCODE applyBoundChanges(
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  	
103  	   SCIPdisableConcurrentBoundStorage(scip);
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;
141  	   SCIPenableConcurrentBoundStorage(scip);
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 */
288  	SCIP_RETCODE SCIPincludePropSync(
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  	    */
307  	   SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING,
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) );
316  	   SCIP_CALL( SCIPsetPropPresol(scip, prop, propPresolSync, PROP_PRESOL_PRIORITY, PROP_PRESOL_MAXROUNDS, PROP_PRESOLTIMING) );
317  	
318  	   return SCIP_OKAY;
319  	}
320  	
321  	
322  	/** adds a boundchange to the sync propagator */
323  	SCIP_RETCODE SCIPpropSyncAddBndchg(
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 */
363  	SCIP_Longint SCIPpropSyncGetNTightenedBnds(
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 */
378  	SCIP_Longint SCIPpropSyncGetNTightenedIntBnds(
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  	}
391