Scippy

SCIP

Solving Constraint Integer Programs

prop_genvbounds.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_genvbounds.c
26  * @ingroup DEFPLUGINS_PROP
27  * @brief generalized variable bounds propagator
28  * @author Stefan Weltge
29  * @author Ambros Gleixner
30  * @author Benjamin Mueller
31  */
32 
33 /**@todo should we only discard events catched from nodes that are not the current node's ancestors? */
34 /**@todo improve computation of minactivity */
35 /**@todo for multaggr vars on left-hand side, create a linear constraint, probably in exitpre */
36 
37 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
38 
39 #include "blockmemshell/memory.h"
40 #include "scip/cons_linear.h"
41 #include "scip/debug.h"
42 #include "scip/prop_genvbounds.h"
43 #include "scip/pub_event.h"
44 #include "scip/pub_message.h"
45 #include "scip/pub_misc.h"
46 #include "scip/pub_prop.h"
47 #include "scip/pub_var.h"
48 #include "scip/scip_conflict.h"
49 #include "scip/scip_cons.h"
51 #include "scip/scip_event.h"
52 #include "scip/scip_general.h"
53 #include "scip/scip_mem.h"
54 #include "scip/scip_message.h"
55 #include "scip/scip_numerics.h"
56 #include "scip/scip_param.h"
57 #include "scip/scip_prob.h"
58 #include "scip/scip_probing.h"
59 #include "scip/scip_prop.h"
60 #include "scip/scip_sol.h"
61 #include "scip/scip_solve.h"
62 #include "scip/scip_solvingstats.h"
63 #include "scip/scip_tree.h"
64 #include "scip/scip_var.h"
65 #include <string.h>
66 
67 #define PROP_NAME "genvbounds"
68 #define PROP_DESC "generalized variable bounds propagator"
69 #define PROP_TIMING SCIP_PROPTIMING_ALWAYS
70 #define PROP_PRIORITY 3000000 /**< propagator priority */
71 #define PROP_FREQ 1 /**< propagator frequency */
72 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators
73  * found reductions? */
74 #define PROP_PRESOL_PRIORITY -2000000 /**< priority of the presolving method (>= 0: before, < 0: after
75  * constraint handlers); combined with presolvers */
76 #define PROP_PRESOLTIMING SCIP_PRESOLTIMING_FAST /* timing of the presolving method (fast, medium, or exhaustive) */
77 #define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates
78  * in (-1: no limit) */
79 #define DEFAULT_GLOBAL_PROPAGATION TRUE /**< apply global propagation? */
80 #define DEFAULT_PROPAGATE_IN_ROOT_NODE TRUE /**< apply genvbounds in root node if no new incumbent was found? */
81 #define DEFAULT_SORT TRUE /**< sort genvbounds and wait for bound change events? (otherwise all
82  * genvbounds are applied in each node) */
83 #define DEFAULT_PROPASCONSS FALSE /**< should genvbounds be transformed to (linear) constraints? */
84 
85 #define EVENTHDLR_NAME "genvbounds"
86 #define EVENTHDLR_DESC "event handler for generalized variable bounds propagator"
87 
88 
89 /*
90  * Data structures
91  */
92 
93 /** GenVBound data */
94 struct GenVBound
95 {
96  SCIP_VAR** vars; /**< pointers to variables x_j occurring in this generalized variable
97  * bound */
98  SCIP_VAR* var; /**< pointer to variable x_i */
99  SCIP_Real* coefs; /**< coefficients a_j of the variables listed in vars */
100  SCIP_Real constant; /**< constant term in generalized variable bound */
101  SCIP_Real cutoffcoef; /**< cutoff bound's coefficient */
102  int coefssize; /**< size of coefs array */
103  int index; /**< index of this genvbound in genvboundstore array */
104  int ncoefs; /**< number of nonzero coefficients a_j */
105  SCIP_BOUNDTYPE boundtype; /**< type of bound provided by the genvbound, SCIP_BOUNDTYPE_LOWER/UPPER
106  * if +/- x_i on left-hand side */
107  SCIP_Bool relaxonly; /**< contains a relaxation-only variable */
108 };
109 typedef struct GenVBound GENVBOUND;
110 
111 /** starting indices data structure */
112 struct SCIP_EventData
113 {
114  SCIP_PROP* prop; /**< pointer to genvbounds propagator */
115  SCIP_VAR* var; /**< variable */
116  int* startindices; /**< array to store the first indices of genvbounds in components that are
117  * impacted by a change of this bound */
118  int* startcomponents; /**< array to store the components corresponding to startindices array */
119  int nstarts; /**< number of indices stored in startindices array */
120  int startindicessize; /**< size of the startindices and startcomponents arrays */
121 };
122 
123 /** propagator data */
124 struct SCIP_PropData
125 {
126  GENVBOUND** genvboundstore; /**< array to store genvbounds; fast access is provided by hashmaps
127  * lbgenvbounds and ubgenvbounds */
128  SCIP_EVENTDATA** lbevents; /**< array of lower bound event data */
129  SCIP_EVENTDATA** ubevents; /**< array of upper bound event data */
130  SCIP_EVENTHDLR* eventhdlr; /**< genvbounds propagator event handler */
131  SCIP_HASHMAP* lbgenvbounds; /**< hashmap to provide fast access to lower bound genvbounds in
132  * genvboundstore array */
133  SCIP_HASHMAP* ubgenvbounds; /**< hashmap to provide fast access to upper bound genvbounds in
134  * genvboundstore array */
135  SCIP_HASHMAP* lbeventsmap; /**< hashmap to provide fast access to lbevents array */
136  SCIP_HASHMAP* ubeventsmap; /**< hashmap to provide fast access to ubevents array */
137  SCIP_HASHMAP* startmap; /**< hashmap to provide fast access to startindices array */
138  SCIP_PROP* prop; /**< pointer to genvbounds propagator */
139  SCIP_NODE* lastnodecaught; /**< last node where events for starting indices were caught */
140  SCIP_VAR* cutoffboundvar; /**< artificial variable representing primal cutoff bound */
141  int* componentsstart; /**< stores the components starting indices in genvboundstore array; the
142  * entry componentsstart[ncomponents] is equal to ngenvbounds, which
143  * makes it easier to iterate over all components */
144  int componentsstartsize;/**< size of componentsstart array */
145  int* startindices; /**< storing indices of components where local propagation should start */
146  int* startcomponents; /**< components corresponding to indices stored in startindices array */
147  int startindicessize; /**< size of startindices and startcomponents arrays */
148  int* gstartindices; /**< storing indices of components where global propagation, i.e.,
149  * propagation of an improved primal bound, should start */
150  int* gstartcomponents; /**< components corresponding to indices stored in gstartindices array */
151  int gstartindicessize; /**< size of gstartindices and gstartcomponents arrays */
152  SCIP_Real lastcutoff; /**< cutoff bound's value last time genvbounds propagator was called */
153  int genvboundstoresize; /**< size of genvboundstore array */
154  int ngenvbounds; /**< number of genvbounds stored in genvboundstore array */
155  int ncomponents; /**< number of components in genvboundstore array */
156  int nindices; /**< number of indices stored in startindices array */
157  int ngindices; /**< number of indices stored in gstartindices array */
158  int nlbevents; /**< number of data entries in lbevents array */
159  int nubevents; /**< number of data entries in ubevents array */
160  SCIP_Bool issorted; /**< stores wether array genvboundstore is topologically sorted */
161  SCIP_Bool global; /**< apply global propagation? */
162  SCIP_Bool propinrootnode; /**< apply genvbounds in root node if no new incumbent was found? */
163  SCIP_Bool sort; /**< sort genvbounds and wait for bound change events? (otherwise all
164  * genvbounds are applied in each node) */
165  SCIP_Bool propasconss; /**< should genvbounds be transformed to (linear) constraints? */
166 };
167 
168 
169 /*
170  * Local methods
171  */
172 
173 /** returns correct cutoff bound value */
174 static
176  SCIP* scip /**< SCIP data structure */
177  )
178 {
179  assert(scip != NULL);
180 
181  SCIPdebugMsg(scip, "cutoff = %.9g (%.9g + %.9g * %.9g)\n",
184 
185  /* the cutoff bound is valid w.r.t. the current objective function in the transformed problem; during presolving,
186  * however, the objective function can change (e.g., when a variable is fixed, its contribution in the objective is
187  * subtracted from the cutoff bound and added to the objective offset); we solve this by transforming the
188  * contribution of the cutoff bound in the generalized variable bound to the original problem as described in
189  * function SCIPgenVBoundAdd()
190  */
191  return (SCIPgetCutoffbound(scip) + SCIPgetTransObjoffset(scip)) * SCIPgetTransObjscale(scip);
192 }
193 
194 /** returns corresponding genvbound in genvboundstore if there is one, NULL otherwise */
195 static
197  SCIP* scip, /**< SCIP data structure */
198  SCIP_PROPDATA* propdata, /**< data of the genvbounds propagator */
199  SCIP_VAR* var, /**< bounds variable */
200  SCIP_BOUNDTYPE boundtype /**< bounds type */
201  )
202 {
203  SCIP_HASHMAP* hashmap;
204 
205  assert(scip != NULL);
206  assert(propdata != NULL);
207  assert(var != NULL);
208 
209  hashmap = boundtype == SCIP_BOUNDTYPE_LOWER ? propdata->lbgenvbounds : propdata->ubgenvbounds;
210 
211  return (GENVBOUND*) SCIPhashmapGetImage(hashmap, var);
212 }
213 
214 #ifdef SCIP_DEBUG
215 /** prints a genvbound as debug message */
216 static
217 void printGenVBound(
218  SCIP* scip, /**< SCIP data structure */
219  GENVBOUND* genvbound /**< genvbound to be printed */
220  )
221 {
222  SCIP_Bool first;
223  int i;
224 
225  assert(genvbound != NULL);
226 
227  if( genvbound->boundtype == SCIP_BOUNDTYPE_UPPER )
228  {
229  SCIPdebugMsgPrint(scip, "- ");
230  }
231 
232  SCIPdebugMsgPrint(scip, "<%s> >= ", SCIPvarGetName(genvbound->var));
233 
234  first = TRUE;
235  for( i = 0; i < genvbound->ncoefs; i++ )
236  {
237  if( !first )
238  {
239  SCIPdebugMsgPrint(scip, " + ");
240  }
241 
242  SCIPdebugMsgPrint(scip, "%g * <%s>", genvbound->coefs[i], SCIPvarGetName(genvbound->vars[i]));
243 
244  first = FALSE;
245  }
246 
247  if( !SCIPisZero(scip, genvbound->cutoffcoef) )
248  {
249  SCIPdebugMsgPrint(scip, " + %g * cutoff_bound", genvbound->cutoffcoef);
250  }
251 
252  if( !SCIPisZero(scip, genvbound->constant) )
253  {
254  SCIPdebugMsgPrint(scip, " + %g", genvbound->constant);
255  }
256 
257  SCIPdebugMsgPrint(scip, "\n");
258 }
259 #endif
260 
261 /** calculates the minactivity of a linear combination of variables stored in an array */
262 static
264  SCIP* scip, /**< SCIP data structure */
265  SCIP_VAR** vars, /**< array of variables */
266  SCIP_Real* coefs, /**< array of coefficients */
267  int nvars, /**< number of variables */
268  SCIP_Bool global /**< use global variable bounds? */
269  )
270 {
271  SCIP_Real minval;
272  int i;
273 
274  assert(scip != NULL);
275  assert(vars != NULL);
276  assert(coefs != NULL);
277  assert(nvars >= 0);
278 
279  minval = 0.0;
280 
281  for( i = 0; i < nvars; i++ )
282  {
284 
285  /* get global or local bound */
286  if( global )
287  bound = coefs[i] > 0.0 ? SCIPvarGetLbGlobal(vars[i]) : SCIPvarGetUbGlobal(vars[i]);
288  else
289  bound = coefs[i] > 0.0 ? SCIPvarGetLbLocal(vars[i]) : SCIPvarGetUbLocal(vars[i]);
290 
291  /* with infinite bounds we cannot compute a valid minactivity and return minus infinity */
292  if( SCIPisInfinity(scip, bound) || SCIPisInfinity(scip, -bound) )
293  return -SCIPinfinity(scip);
294 
295  /* add contribution to minactivity */
296  minval += coefs[i] * bound;
297  }
298 
299  return minval;
300 }
301 
302 /** calculates the minactivity of a linear combination of variables stored in the current conflict set */
303 static
305  SCIP* scip, /**< SCIP data structure */
306  SCIP_VAR** vars, /**< array of variables */
307  SCIP_Real* coefs, /**< array of coefficients */
308  int nvars, /**< number of variables */
309  SCIP_BDCHGIDX* bdchgidx /**< bound change at which minactivity should be computed; if NULL use local bounds */
310  )
311 {
312  SCIP_Real minval;
313  int i;
314 
315  assert(scip != NULL);
316  assert(vars != NULL);
317  assert(coefs != NULL);
318  assert(nvars >= 0);
319 
320  minval = 0.0;
321 
322  for( i = 0; i < nvars; i++ )
323  {
325 
326  if( coefs[i] > 0.0 )
327  {
328  /* get bound at current bound change */
329  bound = SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, TRUE);
330 
331  /* if bdchgidx is NULL, assert that we use local bounds */
332  assert(bdchgidx != NULL || SCIPisEQ(scip, bound, SCIPvarGetLbLocal(vars[i])));
333 
334  /* if bdchgidx is not NULL, use the possibly tighter bound already in the current conflict set */
335  if( bdchgidx != NULL && SCIPgetConflictVarLb(scip, vars[i]) > bound )
336  bound = SCIPgetConflictVarLb(scip, vars[i]);
337  }
338  else
339  {
340  /* get bound at current bound change */
341  bound = SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, TRUE);
342 
343  /* if bdchgidx is NULL, assert that we use local bounds */
344  assert(bdchgidx != NULL || SCIPisEQ(scip, bound, SCIPvarGetUbLocal(vars[i])));
345 
346  /* if bdchgidx is not NULL, use the possibly tighter bound already in the current conflict set */
347  if( bdchgidx != NULL && SCIPgetConflictVarUb(scip, vars[i]) < bound )
348  bound = SCIPgetConflictVarUb(scip, vars[i]);
349  }
350 
351  /* with infinite bounds we cannot compute a valid minactivity and return minus infinity */
352  if( SCIPisInfinity(scip, bound) || SCIPisInfinity(scip, -bound) )
353  return -SCIPinfinity(scip);
354 
355  /* add contribution to minactivity */
356  minval += coefs[i] * bound;
357  }
358 
359  return minval;
360 }
361 
362 /** returns a valid bound given by a generalized variable bound */
363 static
365  SCIP* scip, /**< SCIP data structure */
366  GENVBOUND* genvbound, /**< generalized variable bound */
367  SCIP_Bool global /**< use global variable bounds? */
368  )
369 {
370  SCIP_Real boundval;
371 
372  assert(scip != NULL);
373  assert(genvbound != NULL);
374 
375  boundval = getGenVBoundsMinActivity(scip, genvbound->vars, genvbound->coefs, genvbound->ncoefs, global);
376 
377  if( SCIPisInfinity(scip, -boundval) )
378  return (genvbound->boundtype == SCIP_BOUNDTYPE_LOWER) ? -SCIPinfinity(scip) : SCIPinfinity(scip);
379 
380  if( genvbound->cutoffcoef != 0.0 )
381  boundval += genvbound->cutoffcoef * getCutoffboundGenVBound(scip);
382 
383  boundval += genvbound->constant;
384 
385  if( genvbound->boundtype == SCIP_BOUNDTYPE_UPPER )
386  boundval *= -1.0;
387 
388  return boundval;
389 }
390 
391 #ifdef WITH_DEBUG_SOLUTION
392 /** checks whether a generalized variable bound violates the debug solution */
393 static
394 SCIP_RETCODE checkDebugSolutionGenVBound(
395  SCIP* scip, /**< SCIP data structure */
396  GENVBOUND* genvbound /**< generalized variable bound */
397  )
398 {
399  SCIP_SOL* debugsol;
400  SCIP_Real activity;
401  SCIP_Real solval;
402  int i;
403 
404  assert(scip != NULL);
405  assert(genvbound != NULL);
406 
407  if( !SCIPdebugIsMainscip(scip) )
408  return SCIP_OKAY;
409 
410  /* the genvbound must be valid for all cutoff bounds greater equal the objective value of the debug solution */
411  SCIP_CALL( SCIPdebugGetSol(scip, &debugsol) );
412 
413  /* check whether a debug solution is available */
414  if( debugsol == NULL )
415  return SCIP_OKAY;
416 
417  activity = 0.0;
418  for( i = 0; i < genvbound->ncoefs; i++ )
419  {
420  SCIP_CALL( SCIPdebugGetSolVal(scip, genvbound->vars[i], &solval) );
421  if( solval != SCIP_UNKNOWN || solval != SCIP_INVALID )
422  activity += genvbound->coefs[i] * solval;
423  else
424  printf("***** debug: ignoring variable with %s value in debug solution\n",
425  solval == SCIP_UNKNOWN ? "unknown" : "invalid");
426  }
427 
428  activity += genvbound->cutoffcoef *
429  (SCIPgetSolTransObj(scip, debugsol) + SCIPgetTransObjoffset(scip)) * SCIPgetTransObjscale(scip);
430  activity += genvbound->constant;
431 
432  SCIP_CALL( SCIPdebugGetSolVal(scip, genvbound->var, &solval) );
433  if( solval != SCIP_UNKNOWN || solval != SCIP_INVALID )
434  {
435  if( genvbound->boundtype == SCIP_BOUNDTYPE_LOWER )
436  {
437  SCIP_CALL( SCIPdebugCheckLbGlobal(scip, genvbound->var, activity) );
438  }
439  else if( genvbound->boundtype == SCIP_BOUNDTYPE_UPPER )
440  {
441  SCIP_CALL( SCIPdebugCheckUbGlobal(scip, genvbound->var, -activity) );
442  }
443  }
444 
445  return SCIP_OKAY;
446 }
447 #endif
448 
449 /** allocate local and global startindices, startcomponents and startmap */
450 static
452  SCIP* scip, /**< SCIP data structure */
453  SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */
454  )
455 {
456  assert(scip != NULL);
457  assert(propdata != NULL);
458 
459  assert(propdata->startcomponents == NULL);
460  assert(propdata->startindices == NULL);
461  assert(propdata->startmap == NULL);
462  assert(propdata->nindices == -1);
463 
464  assert(propdata->gstartindices == NULL);
465  assert(propdata->gstartcomponents == NULL);
466  assert(propdata->ngindices == -1);
467 
468  assert(propdata->ngenvbounds >= 1);
469  assert(propdata->ncomponents >= 1);
470 
471  SCIPdebugMsg(scip, "create starting data\n");
472 
473  /* allocate memory for arrays */
474  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->startindices), propdata->ncomponents) );
475  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->startcomponents), propdata->ncomponents) );
476  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->gstartindices), propdata->ncomponents) );
477  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->gstartcomponents), propdata->ncomponents) );
478  propdata->startindicessize = propdata->ncomponents;
479  propdata->gstartindicessize = propdata->ncomponents;
480 
481  /* create hashmap */
482  SCIP_CALL( SCIPhashmapCreate(&(propdata->startmap), SCIPblkmem(scip), propdata->ncomponents) );
483 
484  propdata->nindices = 0;
485  propdata->ngindices = 0;
486 
487  return SCIP_OKAY;
488 }
489 
490 /** free local and global startindices, startcomponents and startmap */
491 static
493  SCIP* scip, /**< SCIP data structure */
494  SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */
495  )
496 {
497  assert(scip != NULL);
498  assert(propdata != NULL);
499 
500  SCIPdebugMsg(scip, "free starting data\n");
501 
502  if( propdata->startcomponents != NULL )
503  {
504  assert(propdata->startindices != NULL);
505  assert(propdata->startmap != NULL);
506  assert(propdata->nindices >= 0);
507 
508  SCIPfreeBlockMemoryArray(scip, &(propdata->startindices), propdata->startindicessize);
509  SCIPfreeBlockMemoryArray(scip, &(propdata->startcomponents), propdata->startindicessize);
510  propdata->startindicessize = 0;
511  SCIPhashmapFree(&(propdata->startmap));
512  propdata->nindices = -1;
513 
514  assert(propdata->gstartindices != NULL);
515  assert(propdata->gstartcomponents != NULL);
516  assert(propdata->ngindices >= 0);
517 
518  SCIPfreeBlockMemoryArray(scip, &(propdata->gstartindices), propdata->gstartindicessize);
519  SCIPfreeBlockMemoryArray(scip, &(propdata->gstartcomponents), propdata->gstartindicessize);
520  propdata->gstartindicessize = 0;
521  propdata->ngindices = -1;
522  }
523 
524  assert(propdata->startcomponents == NULL);
525  assert(propdata->startindices == NULL);
526  assert(propdata->startmap == NULL);
527  assert(propdata->nindices == -1);
528 
529  assert(propdata->gstartindices == NULL);
530  assert(propdata->gstartcomponents == NULL);
531  assert(propdata->ngindices == -1);
532 
533  return SCIP_OKAY;
534 }
535 
536 static
538  SCIP* scip, /**< SCIP data structure */
539  SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */
540  )
541 {
542  int i;
543 
544  assert(scip != NULL);
545  assert(propdata != NULL);
546 
547  assert(propdata->gstartindices != NULL);
548  assert(propdata->gstartcomponents != NULL);
549  assert(propdata->ngindices == 0);
550 
551  SCIPdebugMsg(scip, "fill global starting data\n");
552 
553  for( i = 0; i < propdata->ncomponents; i++ )
554  {
555  int j;
556 
557  for( j = propdata->componentsstart[i]; j < propdata->componentsstart[i+1]; j++ ) /*lint !e679*/
558  {
559  assert(j < propdata->ngenvbounds);
560 
561  if( !SCIPisZero(scip, propdata->genvboundstore[j]->cutoffcoef) )
562  {
563  assert(SCIPisNegative(scip, propdata->genvboundstore[j]->cutoffcoef));
564 
565  propdata->gstartcomponents[propdata->ngindices] = i;
566  propdata->gstartindices[propdata->ngindices] = j;
567 
568  /* go to next component */
569  propdata->ngindices++;
570  break;
571  }
572  }
573  }
574 
575  /* resize arrays */
576  if( propdata->gstartindicessize != propdata->ngindices )
577  {
578  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(propdata->gstartindices), propdata->gstartindicessize, \
579  propdata->ngindices) );
580  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(propdata->gstartcomponents), propdata->gstartindicessize, \
581  propdata->ngindices) );
582  propdata->gstartindicessize = propdata->ngindices;
583  }
584 
585  return SCIP_OKAY;
586 }
587 
588 
589 /** resets local starting data */
590 static
592  SCIP* scip, /**< SCIP data structure */
593  SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */
594  )
595 {
596  assert(scip != NULL);
597  assert(propdata != NULL);
598  assert(propdata->startcomponents != NULL);
599  assert(propdata->startindices != NULL);
600  assert(propdata->startmap != NULL);
601  assert(propdata->nindices >= 0);
602 
603  SCIP_CALL( SCIPhashmapRemoveAll(propdata->startmap) );
604  propdata->nindices = 0;
605 
606  return SCIP_OKAY;
607 }
608 
609 /** frees sorted components data */
610 static
612  SCIP* scip, /**< SCIP data structure */
613  SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */
614  )
615 {
616  assert(scip != NULL);
617  assert(propdata != NULL);
618 
619  SCIPdebugMsg(scip, "free components data\n");
620 
621  if( propdata->componentsstart != NULL )
622  {
623  assert(propdata->ncomponents > 0);
624 
625  SCIPfreeBlockMemoryArray(scip, &(propdata->componentsstart), propdata->componentsstartsize);
626  propdata->componentsstartsize = 0;
627  propdata->ncomponents = -1;
628  }
629 
630  assert(propdata->componentsstart == NULL);
631  assert(propdata->ncomponents == -1);
632 
633  return SCIP_OKAY;
634 }
635 
636 /** frees memory allocated for a generalized variable bound */
637 static
639  SCIP* scip,
640  GENVBOUND* genvbound
641  )
642 {
643  int i;
644 
645  assert(scip != NULL);
646  assert(genvbound != NULL);
647  assert(genvbound->coefs != NULL);
648  assert(genvbound->vars != NULL);
649  assert(genvbound->var != NULL);
650 
651  /* release variables */
652  for( i = 0; i < genvbound->ncoefs; ++i )
653  {
654  assert(genvbound->vars[i] != NULL);
655  SCIP_CALL( SCIPreleaseVar(scip, &(genvbound->vars[i])) );
656  }
657  SCIP_CALL( SCIPreleaseVar(scip, &genvbound->var) );
658 
659  /* free memory */
660  SCIPfreeBlockMemoryArray(scip, &(genvbound->coefs), genvbound->coefssize);
661  SCIPfreeBlockMemoryArray(scip, &(genvbound->vars), genvbound->coefssize);
662  SCIPfreeBlockMemory(scip, &genvbound);
663 
664  return SCIP_OKAY;
665 }
666 
667 /** helper function to release all genvbounds */
668 static
670  SCIP* scip,
671  SCIP_PROPDATA* propdata
672  )
673 {
674  int i;
675 
676  assert(scip != NULL);
677  assert(propdata != NULL);
678 
679  if( propdata->genvboundstore != NULL )
680  {
681  /* free genvbounds */
682  for( i = propdata->ngenvbounds - 1; i >= 0; i-- )
683  {
684  SCIP_CALL( freeGenVBound(scip, propdata->genvboundstore[i]) );
685  }
686 
687  /* free genvboundstore hashmaps */
688  SCIPhashmapFree(&(propdata->lbgenvbounds));
689  SCIPhashmapFree(&(propdata->ubgenvbounds));
690 
691  /* free genvboundstore array */
692  SCIPfreeBlockMemoryArray(scip, &(propdata->genvboundstore), propdata->genvboundstoresize);
693 
694  /* set the number of genvbounds to zero */
695  propdata->ngenvbounds = 0;
696 
697  /* free componentsstart array */
698  SCIP_CALL( freeComponentsData(scip, propdata) );
699 
700  /* free starting indices data */
701  SCIP_CALL( freeStartingData(scip, propdata) );
702 
703  /* release the cutoffboundvar and undo the locks */
704  if( propdata->cutoffboundvar != NULL )
705  {
706  SCIP_CALL( SCIPaddVarLocksType(scip, propdata->cutoffboundvar, SCIP_LOCKTYPE_MODEL, -1, -1) );
707  SCIP_CALL( SCIPreleaseVar(scip, &(propdata->cutoffboundvar)) );
708  propdata->cutoffboundvar = NULL;
709  SCIPdebugMsg(scip, "release cutoffboundvar!\n");
710  }
711  }
712 
713  return SCIP_OKAY;
714 }
715 
716 /** helper function to release relax-only genvbounds */
717 static
719  SCIP* scip,
720  SCIP_PROPDATA* propdata
721  )
722 {
723  SCIP_Bool freedgenvbound;
724  int i;
725 
726  assert(scip != NULL);
727  assert(propdata != NULL);
728 
729  if( propdata->genvboundstore == NULL )
730  return SCIP_OKAY;
731 
732  /* free genvbounds */
733  freedgenvbound = FALSE;
734  for( i = 0 ; i < propdata->ngenvbounds; )
735  {
736  if( propdata->genvboundstore[i]->relaxonly )
737  {
738  SCIP_CALL( SCIPhashmapRemove(propdata->genvboundstore[i]->boundtype == SCIP_BOUNDTYPE_LOWER ? propdata->lbgenvbounds : propdata->ubgenvbounds,
739  propdata->genvboundstore[i]->var) );
740 
741  SCIP_CALL( freeGenVBound(scip, propdata->genvboundstore[i]) );
742  if( i != propdata->ngenvbounds-1 )
743  {
744  propdata->genvboundstore[i] = propdata->genvboundstore[propdata->ngenvbounds-1];
745  propdata->genvboundstore[i]->index = i;
746  }
747  --propdata->ngenvbounds;
748 
749  propdata->issorted = FALSE;
750  freedgenvbound = TRUE;
751  }
752  else
753  ++i;
754  }
755 
756  if( freedgenvbound )
757  {
758  /* free componentsstart array */
759  SCIP_CALL( freeComponentsData(scip, propdata) );
760 
761  /* free starting indices data */
762  SCIP_CALL( freeStartingData(scip, propdata) );
763  }
764 
765  return SCIP_OKAY;
766 }
767 
768 /** resolves propagation of lower bound on +/- left-hand side variable of a generalized variable bound */
769 static
771  SCIP* scip, /**< SCIP data structure */
772  GENVBOUND* genvbound, /**< genvbound data structure */
773  SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
774  SCIP_Real* boundval, /**< pointer to lower bound value on +/- left-hand side variable */
775  SCIP_Bool* success /**< was the explanation succesful? */
776  )
777 {
778  SCIP_VAR* lhsvar;
779  SCIP_VAR** vars;
780  SCIP_Real minactivity;
781  SCIP_Real tmpboundval;
782  SCIP_Real slack;
783  int nvars;
784  int i;
785 
786  assert(scip != NULL);
787  assert(genvbound != NULL);
788  assert(boundval != NULL);
789  assert(success != NULL);
790 
791  *success = FALSE;
792 
793  /* get left-hand side variable */
794  lhsvar = genvbound->var;
795  assert(lhsvar != NULL);
796 
797  /* get right-hand side variables */
798  vars = genvbound->vars;
799  nvars = genvbound->ncoefs;
800  assert(vars != NULL);
801 
802  /* if only the primal bound participates in the propagation, it is globally valid and should not be analyzed */
803  assert(nvars > 0);
804 
805  /* when resolving a propagation, bdchgidx is not NULL and boundval should be the bound change performed for the
806  * left-hand side variable
807  */
808  assert(bdchgidx == NULL || genvbound->boundtype != SCIP_BOUNDTYPE_LOWER || SCIPisEQ(scip,
809  SCIPvarIsIntegral(genvbound->var) ? SCIPfeasCeil(scip, *boundval) : *boundval, SCIPgetVarLbAtIndex(scip, lhsvar, bdchgidx, TRUE)));
810  assert(bdchgidx == NULL || genvbound->boundtype != SCIP_BOUNDTYPE_UPPER || SCIPisEQ(scip,
811  SCIPvarIsIntegral(genvbound->var) ? SCIPfeasCeil(scip, *boundval) : *boundval, -SCIPgetVarUbAtIndex(scip, lhsvar, bdchgidx, TRUE)));
812 
813  /* when creating an initial conflict, bdchgidx is NULL and +/-boundval must exceed the upper/lower bound of the
814  * left-hand side variable
815  */
816  assert(bdchgidx != NULL || genvbound->boundtype != SCIP_BOUNDTYPE_LOWER
817  || SCIPisGT(scip, *boundval, SCIPvarGetUbLocal(lhsvar)));
818  assert(bdchgidx != NULL || genvbound->boundtype != SCIP_BOUNDTYPE_UPPER
819  || SCIPisGT(scip, *boundval, -SCIPvarGetLbLocal(lhsvar)));
820 
821  SCIPdebugMsg(scip, "resolving genvbound propagation: lhs=%s<%s> >= boundval=%.15g\n",
822  genvbound->boundtype == SCIP_BOUNDTYPE_LOWER ? "+" : "-", SCIPvarGetName(lhsvar), *boundval);
823 
824  /* subtract constant terms from bound value */
825  tmpboundval = *boundval;
826  tmpboundval -= genvbound->cutoffcoef * getCutoffboundGenVBound(scip);
827  tmpboundval -= genvbound->constant;
828 
829  SCIPdebugMsg(scip, "subtracting constant terms gives boundval=%.15g\n", tmpboundval);
830 
831  /* compute minimal activity; if bdchgidx is NULL, we create the initial conflict and use local bounds */
832  minactivity = getGenVBoundsMinActivityConflict(scip, genvbound->vars, genvbound->coefs, genvbound->ncoefs, bdchgidx);
833 
834  SCIPdebugMsg(scip, "minactivity of right-hand side is minactivity=%.15g\n", minactivity);
835 
836  /* a genvbound might have been replaced since the propagation took place, hence we have to check that the current
837  * genvbound can explain the propagation at the given bound change index; note that by now, with smaller cutoff
838  * bound, we might even perform a stronger propagation
839  */
840  if( SCIPisLT(scip, minactivity, tmpboundval) )
841  {
842  SCIPdebugMsg(scip, "minactivity is too small to explain propagation; was genvbound replaced?\n");
843  return SCIP_OKAY;
844  }
845 
846  /* if bdchgidx is NULL, i.e., we create the initial conflict, we should be able to explain the bound change */
847  assert(SCIPisGE(scip, minactivity, tmpboundval));
848 
849  slack = MAX(minactivity - tmpboundval, 0.0);
850 
851  SCIPdebugMsg(scip, "slack=%.15g\n", slack);
852 
853  /* add variables on the right-hand side as reasons for propagation */
854  for( i = 0; i < nvars; i++ )
855  {
856  assert(vars[i] != NULL);
857  assert(SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE)));
858  assert(SCIPisEQ(scip, SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE)));
859 
860  /* coefficient is positive */
861  if( genvbound->coefs[i] > 0.0 )
862  {
863  SCIP_Real lbatindex;
864  SCIP_Real conflictlb;
865 
866  /* get bound at current bound change */
867  lbatindex = SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, TRUE);
868 
869  /* get bound already enforced by conflict set */
870  conflictlb = SCIPgetConflictVarLb(scip, genvbound->vars[i]);
871  assert(SCIPisGE(scip, conflictlb, SCIPvarGetLbGlobal(genvbound->vars[i])));
872 
873  SCIPdebugMsg(scip, "lower bound of variable <%s> (genvbound->vars[%d]) in conflict set / at index is %.15g / %.15g\n",
874  SCIPvarGetName(genvbound->vars[i]), i, conflictlb, lbatindex);
875 
876  /* if bound is already enforced by conflict set we do not need to add the bound change; since we used the
877  * tighest bound already when computing the initial minactivity, the slack is already correct
878  */
879  if( SCIPisLE(scip, lbatindex, conflictlb) )
880  {
881  SCIPdebugMsg(scip, "skipping lower bound of variable <%s> (genvbound->vars[%d]) already enforced in conflict set\n",
882  SCIPvarGetName(genvbound->vars[i]), i);
883  }
884  else
885  {
886  SCIP_Real relaxedlb;
887 
888  /* compute relaxed bound that would suffice to explain the bound change */
889  relaxedlb = lbatindex - (slack / genvbound->coefs[i]);
890  assert(relaxedlb <= lbatindex);
891 
892  /* add variable to conflict set */
893  SCIP_CALL( SCIPaddConflictRelaxedLb(scip, genvbound->vars[i], bdchgidx, relaxedlb ) );
894 
895  /* get new bound of variable in conflict set; after possible bound widening in SCIPaddConflictLbRelaxed(),
896  * it should be between conflictlb and lbatindex
897  */
898  relaxedlb = SCIPgetConflictVarLb(scip, genvbound->vars[i]);
899  assert(SCIPisGE(scip, relaxedlb, conflictlb));
900  assert(SCIPisLE(scip, relaxedlb, lbatindex));
901 
902  /* update slack and ensure that its nonegative */
903  slack -= genvbound->coefs[i] * (lbatindex - relaxedlb);
904  slack = MAX(slack, 0.0);
905 
906  SCIPdebugMsg(scip, "added lower bound of variable <%s> (genvbound->vars[%d]); new slack=%.15g\n",
907  SCIPvarGetName(genvbound->vars[i]), i, slack);
908  }
909  }
910  /* coefficient is negative */
911  else
912  {
913  SCIP_Real ubatindex;
914  SCIP_Real conflictub;
915 
916  /* get bound at current bound change */
917  ubatindex = SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, TRUE);
918 
919  /* get bound already enforced by conflict set */
920  conflictub = SCIPgetConflictVarUb(scip, genvbound->vars[i]);
921  assert(SCIPisLE(scip, conflictub, SCIPvarGetUbGlobal(genvbound->vars[i])));
922 
923  SCIPdebugMsg(scip, "upper bound of variable <%s> (genvbound->vars[%d]) in conflict set / at index is %.15g / %.15g\n",
924  SCIPvarGetName(genvbound->vars[i]), i, conflictub, ubatindex);
925 
926  /* if bound is already enforced by conflict set we do not need to add the bound change; since we used the
927  * tighest bound already when computing the initial minactivity, the slack is already correct
928  */
929  if( SCIPisGE(scip, ubatindex, conflictub) )
930  {
931  SCIPdebugMsg(scip, "skipping upper bound of variable <%s> (genvbound->vars[%d]) already enforced in conflict set\n",
932  SCIPvarGetName(genvbound->vars[i]), i);
933  }
934  else
935  {
936  SCIP_Real relaxedub;
937 
938  /* compute relaxed bound that would suffice to explain the bound change */
939  relaxedub = ubatindex - (slack / genvbound->coefs[i]);
940  assert(relaxedub >= ubatindex);
941 
942  /* add variable to conflict set */
943  SCIP_CALL( SCIPaddConflictRelaxedUb(scip, genvbound->vars[i], bdchgidx, relaxedub ) );
944 
945  /* get new bound of variable in conflict set; after possible bound widening in SCIPaddConflictUbRelaxed(),
946  * it should be between conflictub and ubatindex
947  */
948  relaxedub = SCIPgetConflictVarUb(scip, genvbound->vars[i]);
949  assert(SCIPisLE(scip, relaxedub, conflictub));
950  assert(SCIPisGE(scip, relaxedub, ubatindex));
951 
952  /* update slack and ensure that its nonegative */
953  slack -= genvbound->coefs[i] * (ubatindex - relaxedub);
954  slack = MAX(slack, 0.0);
955 
956  SCIPdebugMsg(scip, "added upper bound of variable <%s> (genvbound->vars[%d]); new slack=%.15g\n",
957  SCIPvarGetName(genvbound->vars[i]), i, slack);
958  }
959  }
960  }
961 
962  /* if slack is positive, return increased boundval */
963  if( SCIPisPositive(scip, slack) )
964  tmpboundval += slack;
965 
966  /* add constant terms again */
967  tmpboundval += genvbound->cutoffcoef * getCutoffboundGenVBound(scip);
968  tmpboundval += genvbound->constant;
969 
970  /* boundval should not have been decreased; if this happened nevertheless, maybe due to numerical errors, we quit
971  * without success
972  */
973  if( SCIPisLT(scip, tmpboundval, *boundval) )
974  {
975  SCIPdebugMsg(scip, "boundval was reduced from %.15g to %.15g; propagation not resolved\n", *boundval, tmpboundval);
976  return SCIP_OKAY;
977  }
978 
979  /* return widened boundval */
980  *boundval = tmpboundval;
981  *success = TRUE;
982 
983  return SCIP_OKAY;
984 }
985 
986 /** create initial conflict */
987 static
989  SCIP* scip, /**< SCIP data structure */
990  GENVBOUND* genvbound /**< genvbound data structure */
991  )
992 {
993  SCIP_Bool success;
994 
995  assert(scip != NULL);
996  assert(genvbound != NULL);
997 
998  /* check if conflict analysis is applicable */
1000  return SCIP_OKAY;
1001 
1002  /* initialize conflict analysis */
1004 
1005  /* left-hand side variable >= ... */
1006  if( genvbound->boundtype == SCIP_BOUNDTYPE_LOWER )
1007  {
1008  SCIP_Real infeasthreshold;
1009  SCIP_Real bound;
1010 
1011  /* get minimal right-hand side bound that leads to infeasibility; first try with a factor of 2 for robustness */
1012  bound = REALABS(SCIPvarGetUbLocal(genvbound->var));
1013  infeasthreshold = MAX(bound, 1.0) * 2 * SCIPfeastol(scip);
1014  bound = SCIPvarGetUbLocal(genvbound->var) + infeasthreshold;
1015 
1016  /* add right-hand side variables that force the lower bound of the left-hand side variable above its upper bound
1017  * to conflict set
1018  */
1019  SCIP_CALL( resolveGenVBoundPropagation(scip, genvbound, NULL, &bound, &success) );
1020  assert(!success || SCIPisFeasGT(scip, bound, SCIPvarGetUbLocal(genvbound->var)));
1021 
1022  /* if infeasibility cannot be proven with the tighter bound, try with actual bound */
1023  if( !success )
1024  {
1025  bound = REALABS(SCIPvarGetUbLocal(genvbound->var));
1026  infeasthreshold = MAX(bound, 1.0) * SCIPfeastol(scip);
1027  bound = SCIPvarGetUbLocal(genvbound->var) + infeasthreshold;
1028 
1029  SCIP_CALL( resolveGenVBoundPropagation(scip, genvbound, NULL, &bound, &success) );
1030  success = success && SCIPisFeasGT(scip, bound, SCIPvarGetUbLocal(genvbound->var));
1031  }
1032 
1033  /* compute upper bound on left-hand side variable that leads to infeasibility */
1034  bound -= infeasthreshold;
1035  success = success && SCIPisGE(scip, bound, SCIPvarGetUbLocal(genvbound->var));
1036 
1037  /* initial reason could not be constructed, maybe due to numerics; do not apply conflict analysis */
1038  if( !success )
1039  {
1040  SCIPdebugMsg(scip, "strange: could not create initial reason to start conflict analysis\n");
1041  return SCIP_OKAY;
1042  }
1043 
1044  /* if bound is already enforced by conflict set we do not have to add it */
1045  if( SCIPisGE(scip, bound, SCIPgetConflictVarUb(scip, genvbound->var)) )
1046  {
1047  SCIPdebugMsg(scip, "skipping upper bound of left-hand side variable <%s> already enforced in conflict set\n",
1048  SCIPvarGetName(genvbound->var));
1049  }
1050  else
1051  {
1052  SCIPdebugMsg(scip, "adding upper bound of left-hand side variable <%s>\n", SCIPvarGetName(genvbound->var));
1053 
1054  SCIP_CALL( SCIPaddConflictRelaxedUb(scip, genvbound->var, NULL, bound) );
1055  }
1056  }
1057  /* left-hand side variable <= ..., i.e., - left-hand side variable >= ... */
1058  else
1059  {
1060  SCIP_Real infeasthreshold;
1061  SCIP_Real bound;
1062 
1063  /* get minimal right-hand side bound that leads to infeasibility; try with a factor of 2 first for robustness */
1064  bound = REALABS(SCIPvarGetLbLocal(genvbound->var));
1065  infeasthreshold = MAX(bound, 1.0) * 2 * SCIPfeastol(scip);
1066  bound = -SCIPvarGetLbLocal(genvbound->var) + infeasthreshold;
1067 
1068  /* add right-hand side variables that force the upper bound of the left-hand side variable below its lower bound
1069  * to conflict set
1070  */
1071  SCIP_CALL( resolveGenVBoundPropagation(scip, genvbound, NULL, &bound, &success) );
1072  assert(!success || SCIPisFeasLT(scip, -bound, SCIPvarGetLbLocal(genvbound->var)));
1073 
1074  /* if infeasibility cannot be proven with the tighter bound, try with actual bound */
1075  if( !success )
1076  {
1077  bound = REALABS(SCIPvarGetLbLocal(genvbound->var));
1078  infeasthreshold = MAX(bound, 1.0) * SCIPfeastol(scip);
1079  bound = -SCIPvarGetLbLocal(genvbound->var) + infeasthreshold;
1080 
1081  SCIP_CALL( resolveGenVBoundPropagation(scip, genvbound, NULL, &bound, &success) );
1082  success = success && SCIPisFeasLT(scip, -bound, SCIPvarGetLbLocal(genvbound->var));
1083  }
1084 
1085  /* compute lower bound on left-hand side variable that leads to infeasibility */
1086  bound = -bound + infeasthreshold;
1087  success = success && SCIPisLE(scip, bound, SCIPvarGetLbLocal(genvbound->var));
1088 
1089  /* initial reason could not be constructed, maybe due to numerics; do not apply conflict analysis */
1090  if( !success )
1091  {
1092  SCIPdebugMsg(scip, "strange: could not create initial reason to start conflict analysis\n");
1093  return SCIP_OKAY;
1094  }
1095 
1096  /* if bound is already enforced by conflict set we do not have to add it */
1097  if( SCIPisLE(scip, bound, SCIPgetConflictVarLb(scip, genvbound->var)) )
1098  {
1099  SCIPdebugMsg(scip, "skipping lower bound of left-hand side variable <%s> already enforced in conflict set\n",
1100  SCIPvarGetName(genvbound->var));
1101  }
1102  else
1103  {
1104  SCIPdebugMsg(scip, "adding lower bound of left-hand side variable <%s>\n", SCIPvarGetName(genvbound->var));
1105 
1106  SCIP_CALL( SCIPaddConflictRelaxedLb(scip, genvbound->var, NULL, bound) );
1107  }
1108  }
1109 
1110  /* analyze the conflict */
1111  SCIP_CALL( SCIPanalyzeConflict(scip, 0, NULL) );
1112 
1113  return SCIP_OKAY;
1114 }
1115 
1116 /** apply propagation for one generalized variable bound; also if the left-hand side variable is locally fixed, we
1117  * compute the right-hand side minactivity to possibly detect infeasibility
1118  */
1119 static
1121  SCIP* scip, /**< SCIP data structure */
1122  SCIP_PROP* prop, /**< genvbounds propagator */
1123  GENVBOUND* genvbound, /**< genvbound data structure */
1124  SCIP_Bool global, /**< apply global bound changes? (global: true, local: false)*/
1125  SCIP_RESULT* result, /**< result pointer */
1126  int* nchgbds /**< counter to increment if bound was tightened */
1127  )
1128 {
1129  SCIP_Real boundval;
1130  SCIP_Bool infeas;
1131  SCIP_Bool tightened;
1132 
1133  assert(scip != NULL);
1134  assert(genvbound != NULL);
1135  assert(genvbound->var != NULL);
1136  assert(SCIPvarGetStatus(genvbound->var) != SCIP_VARSTATUS_MULTAGGR);
1137  assert(result != NULL);
1138  assert(*result != SCIP_DIDNOTRUN);
1139 
1140  /* get bound value provided by genvbound */
1141  boundval = getGenVBoundsBound(scip, genvbound, global);
1142 
1143  if( SCIPisInfinity(scip, REALABS(boundval)) )
1144  return SCIP_OKAY;
1145 
1146 #ifdef SCIP_DEBUG
1147  {
1148  SCIP_Real lb;
1149  SCIP_Real ub;
1150  SCIP_Real new_lb;
1151  SCIP_Real new_ub;
1152 
1153  lb = global ? SCIPvarGetLbGlobal(genvbound->var) : SCIPvarGetLbLocal(genvbound->var);
1154  ub = global ? SCIPvarGetUbGlobal(genvbound->var) : SCIPvarGetUbLocal(genvbound->var);
1155  new_lb = genvbound->boundtype == SCIP_BOUNDTYPE_LOWER ? boundval : lb;
1156  new_ub = genvbound->boundtype == SCIP_BOUNDTYPE_UPPER ? boundval : ub;
1157 
1158  SCIPdebugMsg(scip, " %s genvbound propagation for <%s>\n", global ?
1159  "global" : "local", SCIPvarGetName(genvbound->var));
1160  SCIPdebugMsg(scip, " genvbound: ");
1161  printGenVBound(scip, genvbound);
1162  SCIPdebugMsg(scip, " [%.15g,%.15g] -> [%.15g,%.15g]\n", lb, ub, new_lb, new_ub);
1163  }
1164 #endif
1165 
1166  /* tighten bound globally */
1167  if( global || genvbound->ncoefs <= 0 )
1168  {
1169  if( genvbound->boundtype == SCIP_BOUNDTYPE_LOWER )
1170  {
1171  SCIP_CALL( SCIPtightenVarLbGlobal(scip, genvbound->var, boundval, FALSE, &infeas, &tightened) );
1172  }
1173  else
1174  {
1175  SCIP_CALL( SCIPtightenVarUbGlobal(scip, genvbound->var, boundval, FALSE, &infeas, &tightened) );
1176  }
1177  }
1178  /* tighten bound locally and start conflict analysis in case of infeasibility; as inferinfo we pass the index of the
1179  * genvbound that was used for propagation
1180  */
1181  else
1182  {
1183  if( genvbound->boundtype == SCIP_BOUNDTYPE_LOWER )
1184  {
1185  SCIP_CALL( SCIPinferVarLbProp(scip, genvbound->var, boundval, prop, genvbound->index, FALSE, &infeas, &tightened) );
1186 
1187  /* initialize conflict analysis if infeasible */
1188  if( infeas )
1189  {
1190  SCIPdebugMsg(scip, " -> lower bound tightening on variable <%s> led to infeasibility\n",
1191  SCIPvarGetName(genvbound->var));
1192 
1193  SCIP_CALL( analyzeGenVBoundConflict(scip, genvbound) );
1194  }
1195  }
1196  else
1197  {
1198  SCIP_CALL( SCIPinferVarUbProp(scip, genvbound->var, boundval, prop, genvbound->index, FALSE, &infeas, &tightened) );
1199 
1200  /* initialize conflict analysis if infeasible */
1201  if( infeas )
1202  {
1203  SCIPdebugMsg(scip, " -> upper bound tightening on variable <%s> led to infeasibility\n",
1204  SCIPvarGetName(genvbound->var));
1205 
1206  SCIP_CALL( analyzeGenVBoundConflict(scip, genvbound) );
1207  }
1208  }
1209  }
1210 
1211  /* handle result */
1212  if( infeas )
1213  {
1214  *result = SCIP_CUTOFF;
1215  SCIPdebugMsg(scip, " cutoff!\n");
1216  }
1217  else if( tightened )
1218  {
1220  if( nchgbds != NULL )
1221  ++(*nchgbds);
1222  SCIPdebugMsg(scip, " tightened!\n");
1223  }
1224 
1225  return SCIP_OKAY;
1226 }
1227 
1228 #ifdef SCIP_DEBUG
1229 /** prints event data as debug message */
1230 static
1231 void printEventData(
1232  SCIP_EVENTDATA* eventdata,
1234  )
1235 {
1236  int i;
1237 
1238  SCIPdebugMessage("event data: %s bound of <%s> tightened ==> start propagating at ",
1239  boundtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper", SCIPvarGetName(eventdata->var));
1240 
1241  /* if there is eventdata it should contain at least one starting index */
1242  assert(eventdata->nstarts > 0);
1243 
1244  for( i = 0; i < eventdata->nstarts; i++ )
1245  {
1246  SCIPdebugPrintf("(component %d, index %d) ", eventdata->startcomponents[i], eventdata->startindices[i]);
1247  }
1248  SCIPdebugPrintf("\n");
1249 }
1250 #endif
1251 
1252 /** frees event data */
1253 static
1255  SCIP* scip, /**< SCIP data structure */
1256  SCIP_EVENTDATA** eventdata /**< event data to be freed */
1257  )
1259  assert(scip != NULL);
1260  assert(eventdata != NULL);
1261  assert(*eventdata != NULL);
1262 
1263  SCIPfreeBlockMemoryArray(scip, &((*eventdata)->startcomponents), (*eventdata)->startindicessize);
1264  SCIPfreeBlockMemoryArray(scip, &((*eventdata)->startindices), (*eventdata)->startindicessize);
1265 
1266  (*eventdata)->startindicessize = 0;
1267  (*eventdata)->nstarts = -1;
1268  (*eventdata)->var = NULL;
1269  (*eventdata)->prop = NULL;
1270 
1271  SCIPfreeBlockMemory(scip, eventdata);
1272 
1273  return SCIP_OKAY;
1274 }
1275 
1276 /** frees all eventdata stored */
1277 static
1279  SCIP* scip, /**< SCIP data structure */
1280  SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */
1281  )
1283  int i;
1284 
1285  assert(scip != NULL);
1286  assert(propdata != NULL);
1287 
1288  if( propdata->lbevents != NULL )
1289  {
1290  assert(propdata->ubevents != NULL);
1291  assert(propdata->lbeventsmap != NULL);
1292  assert(propdata->ubeventsmap != NULL);
1293 
1294  SCIPhashmapFree(&(propdata->lbeventsmap));
1295  SCIPhashmapFree(&(propdata->ubeventsmap));
1296 
1297  for( i = propdata->nlbevents - 1; i >= 0; i-- )
1298  {
1299  SCIP_CALL( freeEventData(scip, &(propdata->lbevents[i])) );
1300  }
1301 
1302  for( i = propdata->nubevents - 1; i >= 0; i-- )
1303  {
1304  SCIP_CALL( freeEventData(scip, &(propdata->ubevents[i])) );
1305  }
1306 
1307  SCIPfreeBlockMemoryArray(scip, &(propdata->ubevents), propdata->nubevents);
1308  SCIPfreeBlockMemoryArray(scip, &(propdata->lbevents), propdata->nlbevents);
1309  propdata->nlbevents = -1;
1310  propdata->nubevents = -1;
1311  }
1312 
1313  assert(propdata->lbevents == NULL);
1314  assert(propdata->ubevents == NULL);
1315  assert(propdata->lbeventsmap == NULL);
1316  assert(propdata->ubeventsmap == NULL);
1317  assert(propdata->nlbevents == -1);
1318  assert(propdata->nubevents == -1);
1319 
1320  return SCIP_OKAY;
1321 }
1322 
1323 /** drops all events caught by genvbounds propagator and frees their data */
1324 static
1326  SCIP* scip, /**< SCIP data structure */
1327  SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */
1328  )
1330  int i;
1331 
1332  SCIPdebugMsg(scip, "drop and free events\n");
1333 
1334  assert(scip != NULL);
1335  assert(propdata != NULL);
1336  assert(propdata->eventhdlr != NULL);
1337 
1338  if( propdata->lbevents != NULL )
1339  {
1340  assert(propdata->ubevents != NULL);
1341  assert(propdata->nlbevents >= 0);
1342  assert(propdata->nubevents >= 0);
1343 
1344  for( i = propdata->nlbevents - 1; i >= 0; i-- )
1345  {
1346  /* drop event */
1347  SCIP_CALL( SCIPdropVarEvent(scip, propdata->lbevents[i]->var, SCIP_EVENTTYPE_LBTIGHTENED, propdata->eventhdlr,
1348  propdata->lbevents[i], -1) );
1349  }
1350 
1351  for( i = propdata->nubevents - 1; i >= 0; i-- )
1352  {
1353  /* drop event */
1354  SCIP_CALL( SCIPdropVarEvent(scip, propdata->ubevents[i]->var, SCIP_EVENTTYPE_UBTIGHTENED, propdata->eventhdlr,
1355  propdata->ubevents[i], -1) );
1356  }
1357 
1358  /* free event data */
1359  SCIP_CALL( freeAllEventData(scip, propdata) );
1360  }
1361 
1362  assert(propdata->lbevents == NULL);
1363  assert(propdata->ubevents == NULL);
1364  assert(propdata->nlbevents == -1);
1365  assert(propdata->nubevents == -1);
1366 
1367  return SCIP_OKAY;
1368 }
1369 
1370 /** returns the corresponding event data entry in the corresponding array, if there is one; if not: allocates a new
1371  * event data entry, stores it in the array and returns its adress
1372  */
1373 static
1375  SCIP* scip, /**< SCIP data structure */
1376  SCIP_PROPDATA* propdata, /**< data of the genvbounds propagator */
1377  SCIP_VAR* var, /**< variable */
1378  SCIP_BOUNDTYPE boundtype, /**< type of bound */
1379  SCIP_EVENTDATA** eventdata /**< event data to return */
1380  )
1381 {
1382  SCIP_HASHMAP* hashmap;
1383 
1384  assert(scip != NULL);
1385  assert(propdata != NULL);
1386  assert(var != NULL);
1387 
1388  hashmap = boundtype == SCIP_BOUNDTYPE_LOWER ? propdata->lbeventsmap : propdata->ubeventsmap;
1389 
1390  if( SCIPhashmapExists(hashmap, var) )
1391  *eventdata = (SCIP_EVENTDATA*) SCIPhashmapGetImage(hashmap, var);
1392  else
1393  {
1394  /* set up new eventdata entry */
1395  SCIP_CALL( SCIPallocBlockMemory(scip, eventdata) );
1396  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*eventdata)->startcomponents), propdata->ncomponents) );
1397  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*eventdata)->startindices), propdata->ncomponents) );
1398  (*eventdata)->startindicessize = propdata->ncomponents;
1399  (*eventdata)->nstarts = 0;
1400  (*eventdata)->var = var;
1401  (*eventdata)->prop = propdata->prop;
1402 
1403  /* store event data in eventarray */
1404  if( boundtype == SCIP_BOUNDTYPE_LOWER )
1405  {
1406  propdata->lbevents[propdata->nlbevents] = *eventdata;
1407  propdata->nlbevents++;
1408  }
1409  else
1410  {
1411  propdata->ubevents[propdata->nubevents] = *eventdata;
1412  propdata->nubevents++;
1413  }
1414 
1415  /* store hashmap entry */
1416  SCIP_CALL( SCIPhashmapInsert(hashmap, var, (*eventdata)) );
1417  }
1418 
1419  return SCIP_OKAY;
1420 }
1421 
1422 /** adds an event to the event array lbevents (if boundtype == SCIP_BOUNDTYPE_LOWER) or ubevents (if boundtype ==
1423  * SCIP_BOUNDTYPE_UPPER)
1424  */
1425 static
1427  SCIP* scip, /**< SCIP data structure */
1428  SCIP_PROPDATA* propdata, /**< data of the genvbounds propagator */
1429  SCIP_VAR* var, /**< variable thats event to be added */
1430  int startindex, /**< starting index */
1431  int startcomponent, /**< starting components index */
1432  SCIP_BOUNDTYPE boundtype /**< type of bound */
1433  )
1434 {
1435  SCIP_EVENTDATA* eventdata;
1436 
1437  assert(scip != NULL);
1438  assert(propdata != NULL);
1439  assert(var != NULL);
1440  assert(startindex >= 0);
1441  assert(startcomponent >= 0);
1442 
1443  /* get eventdata entry */
1444  SCIP_CALL( getEventData(scip, propdata, var, boundtype, &eventdata) );
1445  assert(eventdata != NULL);
1446 
1447  if( eventdata->nstarts > 0 && eventdata->startcomponents[eventdata->nstarts - 1] == startcomponent )
1448  {
1449  /* if there is already a starting index for startcomponent stored at the last entry of eventdata->startindices,
1450  * it should be smaller; this relies on the implementation of setUpEvents(), calling addEventData() in
1451  * topological order
1452  */
1453  assert(eventdata->startindices[eventdata->nstarts - 1] < startindex);
1454  }
1455  else
1456  {
1457  /* append starting information */
1458  eventdata->startcomponents[eventdata->nstarts] = startcomponent;
1459  eventdata->startindices[eventdata->nstarts] = startindex;
1460 
1461  /* increase counter */
1462  eventdata->nstarts++;
1463  }
1464 
1465  return SCIP_OKAY;
1466 }
1467 
1468 static
1470  SCIP* scip, /**< SCIP data structure */
1471  SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */
1472  )
1474  int nprobvars;
1475  int i;
1476 
1477  assert(scip != NULL);
1478  assert(propdata != NULL);
1479  assert(propdata->eventhdlr != NULL);
1480  assert(propdata->lbevents == NULL);
1481  assert(propdata->ubevents == NULL);
1482  assert(propdata->issorted);
1483  assert(propdata->nlbevents == -1);
1484  assert(propdata->nubevents == -1);
1485 
1486  SCIPdebugMsg(scip, "set up events\n");
1487 
1488  /* allocate lbevents, ubevents, and their hashmaps */
1489  nprobvars = SCIPgetNVars(scip) + SCIPgetNFixedVars(scip);
1490  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->lbevents), nprobvars) );
1491  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->ubevents), nprobvars) );
1492  SCIP_CALL( SCIPhashmapCreate(&(propdata->lbeventsmap), SCIPblkmem(scip), nprobvars) );
1493  SCIP_CALL( SCIPhashmapCreate(&(propdata->ubeventsmap), SCIPblkmem(scip), nprobvars) );
1494  propdata->nlbevents = 0;
1495  propdata->nubevents = 0;
1496 
1497  /* loop over all components of genvboundstore */
1498  for( i = 0; i < propdata->ncomponents; i++ )
1499  {
1500  int j;
1501 
1502  /* loop over all genvbounds in this component */
1503  for( j = propdata->componentsstart[i]; j < propdata->componentsstart[i+1]; j++ ) /*lint !e679*/
1504  {
1505  GENVBOUND* genvbound;
1506  int k;
1507 
1508  assert(j < propdata->ngenvbounds);
1509 
1510  genvbound = propdata->genvboundstore[j];
1511  assert(genvbound != NULL);
1512 
1513  /* loop over all coefficients in this genvbound */
1514  for( k = 0; k < genvbound->ncoefs; k++ )
1515  {
1516  if( SCIPisPositive(scip, genvbound->coefs[k]) )
1517  {
1518  SCIP_CALL( addEventData(scip, propdata, genvbound->vars[k], j, i, SCIP_BOUNDTYPE_LOWER) );
1519  }
1520  else
1521  {
1522  SCIP_CALL( addEventData(scip, propdata, genvbound->vars[k], j, i, SCIP_BOUNDTYPE_UPPER) );
1523  }
1524  }
1525  }
1526  }
1527 
1528  /* resize lbevents and ubevents array */
1529  assert(propdata->nlbevents <= nprobvars);
1530  assert(propdata->nubevents <= nprobvars);
1531  if( propdata->nlbevents < nprobvars )
1532  {
1533  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(propdata->lbevents), nprobvars, propdata->nlbevents) );
1534  }
1535  if( propdata->nubevents < nprobvars )
1536  {
1537  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(propdata->ubevents), nprobvars, propdata->nubevents) );
1538  }
1539 
1540  /* resize and register lower bound events */
1541  for( i = 0; i < propdata->nlbevents; i++ )
1542  {
1543  SCIP_EVENTDATA* eventdata = propdata->lbevents[i];
1544 
1545  assert(eventdata != NULL);
1546  assert(eventdata->nstarts > 0);
1547  assert(eventdata->startcomponents != NULL);
1548  assert(eventdata->startindices != NULL);
1549 
1550  /* resize arrays stored in eventdata */
1551  if( eventdata->startindicessize != eventdata->nstarts )
1552  {
1553  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(eventdata->startcomponents), eventdata->startindicessize, \
1554  eventdata->nstarts) );
1555  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(eventdata->startindices), eventdata->startindicessize, \
1556  eventdata->nstarts) );
1557  eventdata->startindicessize = eventdata->nstarts;
1558  }
1559 
1560  /* register event */
1561  SCIP_CALL( SCIPcatchVarEvent(scip, eventdata->var, SCIP_EVENTTYPE_LBTIGHTENED, propdata->eventhdlr, eventdata, \
1562  NULL) );
1563  }
1564 
1565  /* resize and register upper bound events */
1566  for( i = 0; i < propdata->nubevents; i++ )
1567  {
1568  SCIP_EVENTDATA* eventdata = propdata->ubevents[i];
1569 
1570  assert(eventdata != NULL);
1571  assert(eventdata->nstarts > 0);
1572  assert(eventdata->startcomponents != NULL);
1573  assert(eventdata->startindices != NULL);
1574 
1575  /* resize arrays stored in eventdata */
1576  if( eventdata->startindicessize != eventdata->nstarts )
1577  {
1578  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(eventdata->startcomponents), eventdata->startindicessize, \
1579  eventdata->nstarts) );
1580  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(eventdata->startindices), eventdata->startindicessize, \
1581  eventdata->nstarts) );
1582  eventdata->startindicessize = eventdata->nstarts;
1583  }
1584  /* register event */
1585  SCIP_CALL( SCIPcatchVarEvent(scip, eventdata->var, SCIP_EVENTTYPE_UBTIGHTENED, propdata->eventhdlr, eventdata,
1586  NULL) );
1587  }
1588 
1589  return SCIP_OKAY;
1590 }
1591 
1592 /** performs a topological sort on genvboundstore array
1593  *
1594  * The genvbounds graph is defined as follows: Given two genvbounds
1595  *
1596  * (genvbound1) c1 * x_i1 >= RHS1
1597  *
1598  * and
1599  *
1600  * (genvbound2) c2 * x_i2 >= RHS2,
1601  *
1602  * there is an arc from genvbound1 to genvbound2 iff c1 = +1 and x_i1 appears with positive coefficient in RHS2 or
1603  * c1 = -1 and x_i1 appears with negative coefficient in RHS2; in this case, a bound change of x_i1 deduced from
1604  * genvbound1 improves genvbound2's minactivity in RHS2.
1605  *
1606  * The method computes the strongly connected components and sorts them topologically. The order of the nodes in an
1607  * strongly connected component is arbitrary.
1608  */
1609 static
1611  SCIP* scip, /**< SCIP data structure */
1612  SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */
1613  )
1615  GENVBOUND** genvboundssorted; /* array to store the sorted genvbounds */
1616  SCIP_DIGRAPH* graph;
1617  int* strongcomponents;
1618  int* strongcompstartidx;
1619  int sortedindex;
1620  int i;
1621 
1622  assert(scip != NULL);
1623  assert(propdata != NULL);
1624  assert(propdata->componentsstart == NULL);
1625 
1626  SCIPdebugMsg(scip, "(re-)sort genvbounds topologically\n");
1627 
1628  /* create digraph */
1629  SCIP_CALL( SCIPcreateDigraph(scip, &graph, propdata->ngenvbounds) );
1630 
1631  /* add outgoing arcs for each genvbound */
1632  for( i = 0; i < propdata->ngenvbounds; i++ )
1633  {
1634  GENVBOUND* genvbound;
1635  int j;
1636 
1637  assert(i < propdata->ngenvbounds);
1638 
1639  genvbound = propdata->genvboundstore[i];
1640 
1641  for( j = 0; j < genvbound->ncoefs; j++ )
1642  {
1643  if( SCIPisPositive(scip, genvbound->coefs[j]) &&
1644  SCIPhashmapExists(propdata->lbgenvbounds, genvbound->vars[j]) )
1645  {
1646  int from = ((GENVBOUND*) SCIPhashmapGetImage(propdata->lbgenvbounds, genvbound->vars[j]))->index;
1647  SCIP_CALL( SCIPdigraphAddArc(graph, from, i, NULL) );
1648  }
1649  else if( SCIPisNegative(scip, genvbound->coefs[j]) &&
1650  SCIPhashmapExists(propdata->ubgenvbounds, genvbound->vars[j]) )
1651  {
1652  int from = ((GENVBOUND*) SCIPhashmapGetImage(propdata->ubgenvbounds, genvbound->vars[j]))->index;
1653  SCIP_CALL( SCIPdigraphAddArc(graph, from, i, NULL) );
1654  }
1655  }
1656  }
1657 
1658  /* perform the topological sort */
1659  SCIP_CALL( SCIPdigraphComputeUndirectedComponents(graph, 1, NULL, &(propdata->ncomponents)) );
1661  assert(SCIPdigraphGetNComponents(graph) == propdata->ncomponents);
1662 
1663  /* allocate memory for genvboundssorted and componentsstart array */
1664  SCIP_CALL( SCIPallocBufferArray(scip, &genvboundssorted, propdata->ngenvbounds) );
1665  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->componentsstart), propdata->ncomponents + 1) );
1666  propdata->componentsstartsize = propdata->ncomponents + 1;
1667 
1668  /* allocate memory for strong component arrays */
1669  SCIP_CALL( SCIPallocBufferArray(scip, &strongcomponents, SCIPdigraphGetNNodes(graph)) ); /*lint !e666*/
1670  SCIP_CALL( SCIPallocBufferArray(scip, &strongcompstartidx, SCIPdigraphGetNNodes(graph) + 1) ); /*lint !e666*/
1671 
1672  /* compute sorted genvbounds array, fill componentsstart array */
1673  sortedindex = 0;
1674  propdata->componentsstart[propdata->ncomponents] = propdata->ngenvbounds;
1675  for( i = 0; i < propdata->ncomponents; i++ )
1676  {
1677  int j;
1678  int *nodes;
1679  int nnodes;
1680  int nstrongcomponents;
1681 
1682  SCIPdigraphGetComponent(graph, i, &nodes, &nnodes);
1683  propdata->componentsstart[i] = sortedindex;
1684 
1685  /* compute the strong components of the i-th undirected component */
1686  if( nnodes > 2 )
1687  {
1688  SCIP_CALL( SCIPdigraphComputeDirectedComponents(graph, i, strongcomponents, strongcompstartidx,
1689  &nstrongcomponents) );
1690 
1691  for( j = 0; j < nnodes; ++j )
1692  {
1693  int node;
1694 
1695  /* take the nodes at the end of the strong components array first to respect the topological
1696  * order of the different strong components
1697  */
1698  node = strongcomponents[nnodes - j - 1];
1699 
1700  assert(node < propdata->ngenvbounds);
1701  genvboundssorted[sortedindex] = propdata->genvboundstore[node];
1702  sortedindex++;
1703  }
1704  }
1705  else
1706  {
1707  for( j = 0; j < nnodes; j++ )
1708  {
1709  assert(nodes[j] < propdata->ngenvbounds);
1710  genvboundssorted[sortedindex] = propdata->genvboundstore[nodes[j]];
1711  sortedindex++;
1712  }
1713  }
1714  }
1715  assert(sortedindex == propdata->ngenvbounds);
1716 
1717  /* copy sorted genvbounds into genvboundstore */
1718  for( i = 0; i < propdata->ngenvbounds; i++ )
1719  {
1720  assert(genvboundssorted[i] != NULL);
1721 
1722  propdata->genvboundstore[i] = genvboundssorted[i];
1723  propdata->genvboundstore[i]->index = i;
1724  }
1725 
1726  /* free strong component arrays */
1727  SCIPfreeBufferArray(scip, &strongcompstartidx);
1728  SCIPfreeBufferArray(scip, &strongcomponents);
1729 
1730  SCIPfreeBufferArray(scip, &(genvboundssorted));
1731 
1732  /* free digraph */
1733  SCIPdigraphFree(&graph);
1734 
1735  /* remember genvboundstore as sorted */
1736  propdata->issorted = TRUE;
1737 
1738 #ifdef SCIP_DEBUG
1739  SCIPdebugMsg(scip, "genvbounds got: %d\n", propdata->ngenvbounds);
1740  for( i = 0; i < propdata->ncomponents; i++ )
1741  {
1742  int j;
1743 
1744  SCIPdebugMsg(scip, "{\n");
1745 
1746  for( j = propdata->componentsstart[i]; j < propdata->componentsstart[i+1]; j++ )
1747  {
1748  SCIPdebugMsg(scip, " [%d] ", j);
1749  printGenVBound(scip, propdata->genvboundstore[j]);
1750  }
1751 
1752  SCIPdebugMsg(scip, "}\n");
1753  }
1754 #endif
1755 
1756  return SCIP_OKAY;
1757 }
1758 
1759 /** apply propagation of generalized variable bounds */
1760 static
1762  SCIP* scip, /**< SCIP data structure */
1763  SCIP_PROP* prop, /**< genvbounds propagator */
1764  SCIP_Bool global, /**< use global variable bounds for propagation? */
1765  SCIP_RESULT* result, /**< result pointer */
1766  int* nchgbds /**< counter to increase by the number of changed bounds */
1767  )
1768 {
1769  SCIP_PROPDATA* propdata;
1770  int* startingcomponents;
1771  int* startingindices;
1772  int nindices;
1773  int i;
1774 
1775  SCIPdebugMsg(scip, "applying %s genvbound propagation in depth %d\n", global ?
1776  "global" : "local", SCIPgetDepth(scip));
1777 
1778  assert(scip != NULL);
1779  assert(prop != NULL);
1780  assert(result != NULL);
1781 
1782  propdata = SCIPpropGetData(prop);
1783  assert(propdata != NULL);
1784  assert(propdata->genvboundstore != NULL);
1785 
1786  if( *result == SCIP_DIDNOTRUN )
1787  *result = SCIP_DIDNOTFIND;
1788 
1789  /* if the genvbounds are not sorted, i.e. if root node processing has not been finished, yet, we just propagate in
1790  * the order in which they have been added to genvboundstore
1791  */
1792  if( !propdata->issorted )
1793  {
1794  int j;
1795 
1796  assert(!propdata->sort || SCIPinProbing(scip) || SCIPgetDepth(scip) == 0);
1797 
1798  for( j = 0; j < propdata->ngenvbounds && *result != SCIP_CUTOFF; j++ )
1799  {
1800  if( ! SCIPvarIsActive(propdata->genvboundstore[j]->var) )
1801  {
1802  /**@todo resolve multiaggregation in exitpre */
1803  }
1804  else
1805  {
1806  SCIPdebugMsg(scip, "applying genvbound with index %d (unsorted mode)\n", j);
1807  SCIP_CALL( applyGenVBound(scip, prop, propdata->genvboundstore[j], global, result, nchgbds) );
1808  }
1809  }
1810 
1811  return SCIP_OKAY;
1812  }
1813 
1814  /* otherwise, we propagate only components affected by the latest bound changes */
1815  startingcomponents = global ? propdata->gstartcomponents : propdata->startcomponents;
1816  startingindices = global ? propdata->gstartindices : propdata->startindices;
1817  nindices = global ? propdata->ngindices : propdata->nindices;
1818 
1819  for( i = 0; i < nindices && *result != SCIP_CUTOFF; i++ )
1820  {
1821  int j;
1822 
1823  SCIPdebugMsg(scip, "starting in component %d at index %d\n", startingcomponents[i], startingindices[i]);
1824  for( j = startingindices[i]; j < propdata->componentsstart[startingcomponents[i] + 1] &&
1825  *result != SCIP_CUTOFF; j++ ) /*lint !e679*/
1826  {
1827  assert(j < propdata->ngenvbounds);
1828 
1829  if( ! SCIPvarIsActive(propdata->genvboundstore[j]->var) )
1830  {
1831  /**@todo resolve multiaggregation in exitpre */
1832  }
1833  else
1834  {
1835  SCIPdebugMsg(scip, "applying genvbound with index %d, component %d\n", j, startingcomponents[i]);
1836  SCIP_CALL( applyGenVBound(scip, prop, propdata->genvboundstore[j], global, result, nchgbds) );
1837  }
1838  }
1839  }
1840 
1841  /* we dont want to run again caused by this starting data */
1842  if( !global )
1843  {
1844  SCIP_CALL( resetLocalStartingData(scip, propdata) );
1845  }
1846 
1847  return SCIP_OKAY;
1848 }
1849 
1850 /** initialize propagator data */
1851 static
1853  SCIP* scip, /**< SCIP data structure */
1854  SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */
1855  )
1857  int nprobvars;
1858 
1859  assert(scip != NULL);
1860  assert(propdata != NULL);
1861  assert(propdata->eventhdlr != NULL);
1862 
1863  SCIPdebugMsg(scip, "init propdata\n");
1864 
1865  nprobvars = SCIPgetNVars(scip);
1866 
1867  /* init genvboundstore */
1868  propdata->genvboundstoresize = 2 * nprobvars;
1869  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->genvboundstore), propdata->genvboundstoresize) );
1870  BMSclearMemoryArray(propdata->genvboundstore, propdata->genvboundstoresize);
1871  propdata->ngenvbounds = 0;
1872 
1873  /* init genvboundstore hashmaps */
1874  SCIP_CALL( SCIPhashmapCreate(&(propdata->lbgenvbounds), SCIPblkmem(scip), nprobvars) );
1875  SCIP_CALL( SCIPhashmapCreate(&(propdata->ubgenvbounds), SCIPblkmem(scip), nprobvars) );
1876 
1877  return SCIP_OKAY;
1878 }
1879 
1880 /** adds a new genvbound to genvboundstore array and sets a hashmap entry */
1881 static
1883  SCIP* scip, /**< SCIP data structure */
1884  SCIP_PROPDATA* propdata, /**< data of the genvbounds propagator */
1885  GENVBOUND* genvbound /**< genvbound to be added */
1886  )
1887 {
1888  SCIP_HASHMAP* hashmap;
1889 
1890  assert(scip != NULL);
1891  assert(propdata != NULL);
1892  assert(genvbound != NULL);
1893  assert(getGenVBound(scip, propdata, genvbound->var, genvbound->boundtype) == NULL);
1894 
1895  hashmap = genvbound->boundtype == SCIP_BOUNDTYPE_LOWER ? propdata->lbgenvbounds : propdata->ubgenvbounds;
1896 
1897  /* e.g., during presolving after a restart, new variables might have been created; in this case, we need to extend
1898  * the genvboundstore; the new size may even exceed 2*SCIPgetNVars() if we have genvbounds with nonactive left-hand
1899  * side variables
1900  */
1901  assert(propdata->ngenvbounds <= propdata->genvboundstoresize);
1902  if( propdata->ngenvbounds == propdata->genvboundstoresize )
1903  {
1904  int oldsize = propdata->genvboundstoresize;
1905  propdata->genvboundstoresize = 2*propdata->genvboundstoresize + 1;
1906  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(propdata->genvboundstore), oldsize, propdata->genvboundstoresize) );
1907  }
1908 
1909  /* new index is propdata->ngenvbounds */
1910  SCIP_CALL( SCIPhashmapInsert(hashmap, genvbound->var, genvbound) );
1911  propdata->genvboundstore[propdata->ngenvbounds] = genvbound;
1912  genvbound->index = propdata->ngenvbounds;
1913  propdata->ngenvbounds++;
1914 
1915  assert(propdata->ngenvbounds <= propdata->genvboundstoresize);
1916 
1917  return SCIP_OKAY;
1918 }
1919 
1920 /** runs propagation routine */
1921 static
1923  SCIP* scip, /**< SCIP data structure */
1924  SCIP_PROPDATA* propdata, /**< data of the genvbounds propagator */
1925  SCIP_RESULT* result, /**< result pointer */
1926  SCIP_Bool local, /**< should local propagation be applied? */
1927  int* nchgbds /**< counter to increase by the number of changed bounds */
1928  )
1929 {
1930  assert(scip != NULL);
1931  assert(propdata != NULL);
1932  assert(propdata->prop != NULL);
1933  assert(result != NULL);
1934 
1935  /* we only sort after the root node is finished; this avoids having to sort again after adding more genvbounds; if
1936  * the genvbounds are not sorted, we will simply propagate all of them in the order given
1937  */
1938  if( propdata->sort && !SCIPinProbing(scip) && SCIPgetDepth(scip) > 0 )
1939  {
1940  if( !propdata->issorted )
1941  {
1942  *result = SCIP_DIDNOTFIND;
1943 
1944  SCIPdebugMsg(scip, "genvbounds are not sorted\n");
1945 
1946  /* drop and free old events */
1947  SCIP_CALL( dropAndFreeEvents(scip, propdata) );
1948 
1949  /* free old starting data */
1950  SCIP_CALL( freeStartingData(scip, propdata) );
1951 
1952  /* free sorted components data */
1953  SCIP_CALL( freeComponentsData(scip, propdata) );
1954 
1955  /* sort genvbounds */
1956  SCIP_CALL( sortGenVBounds(scip, propdata) );
1957 
1958  /* create starting data */
1959  SCIP_CALL( createStartingData(scip, propdata) );
1960 
1961  /* fill global starting data */
1962  SCIP_CALL( fillGlobalStartingData(scip, propdata) );
1963  }
1964 
1965  /* set up new events to catch (if not done so far) */
1966  if( propdata->lbevents == NULL )
1967  {
1968  SCIP_CALL( setUpEvents(scip, propdata) );
1969  }
1970  }
1971 
1972  /* apply global propagation if primal bound has improved */
1973  if( propdata->global && SCIPgetDepth(scip) > 0 && SCIPisFeasLT(scip, SCIPgetCutoffbound(scip), propdata->lastcutoff) )
1974  {
1975  if( propdata->ngindices > 0 )
1976  {
1977  SCIP_CALL( applyGenVBounds(scip, propdata->prop, TRUE, result, nchgbds) );
1978  assert(*result != SCIP_DIDNOTRUN);
1979  }
1980 
1981  /* within the tree, the objective function should not change anymore, hence the cutoff bound should be a stable
1982  * point of reference
1983  */
1984  propdata->lastcutoff = SCIPgetCutoffbound(scip);
1985  }
1986 
1987  /* apply local propagation if allowed */
1988  if( local && *result != SCIP_CUTOFF )
1989  {
1990  /* check if local propagation in root node is allowed */
1991  if( SCIPgetDepth(scip) > 0 || propdata->propinrootnode )
1992  {
1993  /* if genvbounds are already sorted, check if bound change events were caught; otherwise apply all genvbounds */
1994  if( !propdata->issorted || ( SCIPgetCurrentNode(scip) == propdata->lastnodecaught && propdata->nindices > 0 ) )
1995  {
1996  SCIP_CALL( applyGenVBounds(scip, propdata->prop, FALSE, result, nchgbds) );
1997  assert(*result != SCIP_DIDNOTRUN);
1998  }
1999  }
2000  }
2001 
2002  return SCIP_OKAY;
2003 }
2004 
2005 /* adds all genvbounds in the genvboundstore as constraints to the problem; afterwards clears the genvboundstore */
2006 static
2008  SCIP* scip, /**< SCIP data structure */
2009  SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */
2010  )
2012  int i;
2013 
2014  assert(scip != NULL);
2015  assert(propdata != NULL);
2016  assert(propdata->propasconss);
2017 
2018  /* ensure that the cutoffboundvar is available */
2019  if( propdata->cutoffboundvar == NULL )
2020  {
2021  SCIP_Real ub;
2022  char name[16];
2023 
2024  /* set the upper bound to the best primal value in the original problem */
2025  ub = getCutoffboundGenVBound(scip);
2026 
2027  SCIPdebugMsg(scip, "initialize cutoffboundvar with UB = %e\n", ub);
2028 
2029  (void) SCIPsnprintf(name, 16, "cutoffboundvar");
2030  SCIP_CALL( SCIPcreateVarBasic(scip, &propdata->cutoffboundvar, name, -SCIPinfinity(scip), ub, 0.0, SCIP_VARTYPE_CONTINUOUS) );
2031  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, propdata->cutoffboundvar) );
2032 
2033  SCIP_CALL( SCIPaddVar(scip, propdata->cutoffboundvar) );
2034 
2035  /* lock the variable because it should not be subject to dual presolving reductions; because we create the
2036  * linear constraints as non-check constraints, the cutoffboundvar will not be locked by the linear constraint
2037  * handler
2038  */
2039  SCIP_CALL( SCIPaddVarLocksType(scip, propdata->cutoffboundvar, SCIP_LOCKTYPE_MODEL, 1, 1) );
2040  }
2041 
2042  assert(propdata->cutoffboundvar != NULL);
2043 
2044  /* now iterate over all genvbounds in the store and construct a linear constraint for each of them */
2045  for( i = 0; i < propdata->ngenvbounds; ++i )
2046  {
2047  GENVBOUND* genvbound;
2048  SCIP_CONS* cons;
2049  SCIP_VAR** vars;
2050  SCIP_Real* vals;
2051  char name[SCIP_MAXSTRLEN];
2052  int nvars;
2053  int j;
2054 
2055  genvbound = propdata->genvboundstore[i];
2056  assert(genvbound != NULL);
2057 
2058  nvars = genvbound->ncoefs + 2;
2059  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
2060  SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) );
2061 
2062  SCIPdebugMsgPrint(scip, "add cons: ");
2063 
2064  /* copy the coefs/vars array */
2065  for( j = 0; j < genvbound->ncoefs; j++ )
2066  {
2067  vars[j] = genvbound->vars[j];
2068  vals[j] = genvbound->coefs[j];
2069  SCIPdebugMsgPrint(scip, "%e%s + ", vals[j], SCIPvarGetName(vars[j]));
2070  }
2071 
2072  /* add the variable and the coefficient of the genvbound */
2073  vars[genvbound->ncoefs] = genvbound->var;
2074  vals[genvbound->ncoefs] = (genvbound->boundtype == SCIP_BOUNDTYPE_LOWER) ? -1.0 : 1.0;
2075 
2076  SCIPdebugMsgPrint(scip, "%e%s + ", vals[genvbound->ncoefs], SCIPvarGetName(vars[genvbound->ncoefs]));
2077 
2078  /* add cutoffcoef * cutoffboundvar */
2079  vars[genvbound->ncoefs + 1] = propdata->cutoffboundvar;
2080  vals[genvbound->ncoefs + 1] = genvbound->cutoffcoef;
2081 
2082  SCIPdebugMsgPrint(scip, "%e%s <= %e\n", vals[genvbound->ncoefs + 1], SCIPvarGetName(vars[genvbound->ncoefs + 1]), -1.0*genvbound->constant);
2083 
2084  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "genvbound_cons%d", genvbound->index);
2085 
2086  /* create linear constraint with only propagate flag as TRUE */
2087  SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name, nvars, vars, vals, -SCIPinfinity(scip), -genvbound->constant,
2089 
2090  SCIP_CALL( SCIPaddCons(scip, cons) );
2091  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
2092 
2093  /* free memory */
2094  SCIPfreeBufferArray(scip, &vars);
2095  SCIPfreeBufferArray(scip, &vals);
2096  }
2097 
2098  /* now delete all genvbounds in the genvboundstore */
2099  if( propdata->ngenvbounds > 0 )
2100  {
2101  assert(propdata->genvboundstore != NULL);
2102 
2103  for( i = propdata->ngenvbounds - 1; i >= 0; i-- )
2104  {
2105  SCIP_CALL( freeGenVBound(scip, propdata->genvboundstore[i]) );
2106  }
2107 
2108  /* free genvboundstore hashmaps */
2109  SCIPhashmapFree(&(propdata->lbgenvbounds));
2110  SCIPhashmapFree(&(propdata->ubgenvbounds));
2111 
2112  /* drop and free all events */
2113  SCIP_CALL( dropAndFreeEvents(scip, propdata) );
2114 
2115  /* free componentsstart array */
2116  SCIP_CALL( freeComponentsData(scip, propdata) );
2117 
2118  /* free starting indices data */
2119  SCIP_CALL( freeStartingData(scip, propdata) );
2120 
2121  SCIPfreeBlockMemoryArray(scip, &(propdata->genvboundstore), propdata->genvboundstoresize);
2122  propdata->genvboundstore = NULL;
2123  propdata->genvboundstoresize = 0;
2124  propdata->ngenvbounds = 0;
2125  }
2126 
2127  return SCIP_OKAY;
2128 }
2129 
2130 
2131 
2132 /*
2133  * Public methods
2134  */
2135 
2136 /** adds a generalized variable bound to the genvbounds propagator; if there is already a genvbound for the bound
2137  * "boundtype" of variable "var", it will be replaced
2138  */
2140  SCIP* scip, /**< SCIP data structure */
2141  SCIP_PROP* genvboundprop, /**< genvbound propagator */
2142  SCIP_VAR** vars, /**< array of RHSs variables */
2143  SCIP_VAR* var, /**< LHSs variable */
2144  SCIP_Real* coefs, /**< array of coefficients for the RHSs variables */
2145  int ncoefs, /**< size of coefs array */
2146  SCIP_Real coefcutoffbound, /**< nonpositive value of the cutoff bounds multiplier */
2147  SCIP_Real constant, /**< constant term */
2148  SCIP_BOUNDTYPE boundtype /**< type of bound provided by the genvbound */
2149  )
2150 {
2151  /**@todo in debug mode: check if genvbound is nontrivial */
2152 
2153  SCIP_PROPDATA* propdata;
2154  GENVBOUND* genvbound;
2155  SCIP_Bool newgenvbound;
2156  int i;
2157 
2158  assert(scip != NULL);
2159  assert(genvboundprop != NULL);
2160  assert(strcmp(SCIPpropGetName(genvboundprop), PROP_NAME) == 0);
2161  assert(vars != NULL);
2162  assert(var != NULL);
2163  assert(coefs != NULL);
2164  assert(ncoefs >= 0);
2165  assert(coefcutoffbound <= 0.0);
2166  assert(!SCIPisInfinity(scip, -constant));
2167 
2168  if( ncoefs < 0 || coefcutoffbound > 0.0 || SCIPisInfinity(scip, -constant) )
2169  {
2170  SCIPerrorMessage("cannot create generalized variable bound from invalid data\n");
2171  return SCIP_INVALIDDATA;
2172  }
2173 
2174  propdata = SCIPpropGetData(genvboundprop);
2175  assert(propdata != NULL);
2176 
2177  /* initialize propdata if not done yet */
2178  if( propdata->genvboundstore == NULL )
2179  {
2180  SCIP_CALL( initPropdata(scip, propdata) );
2181  }
2182 
2183  genvbound = getGenVBound(scip, propdata, var, boundtype);
2184  newgenvbound = (genvbound == NULL);
2185 
2186  /* release previous variables */
2187  if( !newgenvbound )
2188  {
2189  for( i = 0; i < genvbound->ncoefs; ++i )
2190  {
2191  assert(genvbound->vars[i] != NULL);
2192  SCIP_CALL( SCIPreleaseVar(scip, &(genvbound->vars[i])) );
2193  }
2194  }
2195 
2196  /* check if there already is a genvbound corresponding to this bound, freeing its data and overwriting it */
2197  if( !newgenvbound && genvbound->ncoefs < ncoefs )
2198  {
2199  /* do not realloc since we do not want to keep and possibly copy the old entries */
2200  SCIPfreeBlockMemoryArray(scip, &(genvbound->coefs), genvbound->coefssize);
2201  SCIPfreeBlockMemoryArray(scip, &(genvbound->vars), genvbound->coefssize);
2202 
2203  /* allocate and copy arrays in genvbound */
2204  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(genvbound->coefs), coefs, ncoefs) );
2205  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(genvbound->vars), vars, ncoefs) );
2206  genvbound->coefssize = ncoefs;
2207  }
2208  else if( !newgenvbound && genvbound->ncoefs == ncoefs )
2209  {
2210  /* just update entries */
2211  for( i = 0; i < ncoefs; i++ )
2212  {
2213  genvbound->coefs[i] = coefs[i];
2214  genvbound->vars[i] = vars[i];
2215  }
2216  }
2217  else if( !newgenvbound && genvbound->ncoefs > ncoefs )
2218  {
2219  /* reallocate memory for arrays in genvbound to free unused memory */
2220  if( genvbound->coefssize < ncoefs )
2221  {
2222  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(genvbound->coefs), genvbound->coefssize, ncoefs) );
2223  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(genvbound->vars), genvbound->coefssize, ncoefs) );
2224  genvbound->coefssize = ncoefs;
2225  }
2226 
2227  /* update entries */
2228  for( i = 0; i < ncoefs; i++ )
2229  {
2230  genvbound->coefs[i] = coefs[i];
2231  genvbound->vars[i] = vars[i];
2232  }
2233  }
2234  else if( newgenvbound )
2235  {
2236  /* allocate memory for genvbound data */
2237  SCIP_CALL( SCIPallocBlockMemory(scip, &genvbound) );
2238 
2239  /* allocate and copy arrays in genvbound */
2240  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(genvbound->coefs), coefs, ncoefs) );
2241  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(genvbound->vars), vars, ncoefs) );
2242  genvbound->coefssize = ncoefs;
2243  }
2244 
2245  /* set up data for genvbound */
2246  genvbound->boundtype = boundtype;
2247  genvbound->var = var;
2248  genvbound->ncoefs = ncoefs;
2249  genvbound->constant = constant;
2250  genvbound->relaxonly = SCIPvarIsRelaxationOnly(genvbound->var);
2251 
2252  /* capture variables and check for relax-only vars */
2253  for( i = 0; i < genvbound->ncoefs; ++i )
2254  {
2255  assert(genvbound->vars[i] != NULL);
2256  SCIP_CALL( SCIPcaptureVar(scip, genvbound->vars[i]) );
2257  if( SCIPvarIsRelaxationOnly(genvbound->vars[i]) )
2258  genvbound->relaxonly = TRUE;
2259  }
2260  if( newgenvbound )
2261  {
2262  assert(genvbound->var != NULL);
2263  SCIP_CALL( SCIPcaptureVar(scip, genvbound->var) );
2264  }
2265 
2266  /* the cutoff bound is valid w.r.t. the current objective function in the transformed problem; during presolving,
2267  * however, the objective function can change (e.g., when a variable is fixed, its contribution in the objective
2268  * is subtracted from the cutoff bound and added to the objective offset); we solve this by transforming the
2269  * contribution of the cutoff bound in the generalized variable bound to the original problem as follows:
2270  *
2271  * +/- var >= ... + z * SCIPgetCutoffbound() + constant
2272  *
2273  * becomes
2274  *
2275  * +/- var >= ... + (z / SCIPgetTransObjscale()) * origcutoffbound + (constant - z * SCIPgetTransObjoffset())
2276  *
2277  * with SCIPgetCutoffbound() = origcutoffbound / SCIPgetTransObjscale() - SCIPgetTransObjoffset(); in the
2278  * propagation later, we will use (SCIPgetCutoffbound() + SCIPgetTransObjoffset()) * SCIPgetTransObjscale(), see
2279  * function getCutoffboundGenVBound()
2280  */
2281  if( SCIPisNegative(scip, coefcutoffbound) )
2282  {
2283  assert(SCIPisPositive(scip, SCIPgetTransObjscale(scip)));
2284  genvbound->cutoffcoef = coefcutoffbound / SCIPgetTransObjscale(scip);
2285  genvbound->constant -= (coefcutoffbound * SCIPgetTransObjoffset(scip));
2286  }
2287  else
2288  genvbound->cutoffcoef = 0.0;
2289 
2290  /* if genvbound is not overwritten, create a new entry in genvboundstore */
2291  if( newgenvbound )
2292  {
2293  SCIP_CALL( addNewGenVBound(scip, propdata, genvbound) );
2294  }
2295 
2296  /* mark genvbounds array to be resorted */
2297  propdata->issorted = FALSE;
2298 
2299  /* debug message */
2300  SCIPdebugMsg(scip, "added genvbound ");
2301  SCIPdebug( printGenVBound(scip, genvbound) );
2302 #ifdef WITH_DEBUG_SOLUTION
2303  SCIP_CALL( checkDebugSolutionGenVBound(scip, genvbound) );
2304 #endif
2305 
2306  return SCIP_OKAY;
2307 }
2308 
2309 
2310 /*
2311  * Callback methods of propagator
2312  */
2313 
2314 /** copy method for propagator plugins (called when SCIP copies plugins)
2315  *
2316  * @note The UG framework assumes that all default plug-ins of SCIP implement a copy callback.
2317  */
2318 static
2319 SCIP_DECL_PROPCOPY(propCopyGenvbounds)
2320 { /*lint --e{715}*/
2321  assert(scip != NULL);
2322  assert(prop != NULL);
2323  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2324 
2325  /* call inclusion method of constraint handler */
2327 
2328  return SCIP_OKAY;
2329 }
2330 
2331 /** initialization method of propagator (called after problem was transformed) */
2332 static
2333 SCIP_DECL_PROPINIT(propInitGenvbounds)
2334 { /*lint --e{715}*/
2335  SCIP_PROPDATA* propdata;
2336 
2337  assert(scip != NULL);
2338  assert(prop != NULL);
2339  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2340 
2341  /* get propagator data */
2342  propdata = SCIPpropGetData(prop);
2343  assert(propdata != NULL);
2344 
2345  propdata->genvboundstore = NULL;
2346  propdata->genvboundstoresize = 0;
2347  propdata->lbevents = NULL;
2348  propdata->ubevents = NULL;
2349  propdata->lbgenvbounds = NULL;
2350  propdata->ubgenvbounds = NULL;
2351  propdata->lbeventsmap = NULL;
2352  propdata->ubeventsmap = NULL;
2353  propdata->startmap = NULL;
2354  propdata->componentsstart = NULL;
2355  propdata->startindices = NULL;
2356  propdata->startcomponents = NULL;
2357  propdata->gstartindices = NULL;
2358  propdata->gstartcomponents = NULL;
2359  propdata->lastcutoff = SCIPinfinity(scip);
2360  propdata->lastnodecaught = NULL;
2361  propdata->cutoffboundvar = NULL;
2362  propdata->ngenvbounds = -1;
2363  propdata->ncomponents = -1;
2364  propdata->nindices = -1;
2365  propdata->ngindices = -1;
2366  propdata->nlbevents = -1;
2367  propdata->nubevents = -1;
2368  propdata->issorted = FALSE;
2369 
2370  propdata->prop = prop;
2371 
2372  return SCIP_OKAY;
2373 }
2374 
2375 
2376 /** presolving method of propagator */
2377 static
2378 SCIP_DECL_PROPPRESOL(propPresolGenvbounds)
2379 { /*lint --e{715}*/
2380  SCIP_PROPDATA* propdata;
2381 
2382  assert(scip != NULL);
2383  assert(prop != NULL);
2384  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2385 
2386  *result = SCIP_DIDNOTRUN;
2387 
2388  if( !SCIPallowStrongDualReds(scip) )
2389  return SCIP_OKAY;
2390 
2391  /* get propagator data */
2392  propdata = SCIPpropGetData(prop);
2393  assert(propdata != NULL);
2394 
2395  SCIPdebugMsg(scip, "proppresol in problem <%s>\n", SCIPgetProbName(scip));
2396 
2397  /* do not run if no genvbounds were added yet */
2398  if( propdata->ngenvbounds < 1 )
2399  {
2400  SCIPdebugMsg(scip, "no bounds were added yet\n");
2401  return SCIP_OKAY;
2402  }
2403 
2404  /* propagate */
2405  SCIP_CALL( execGenVBounds(scip, propdata, result, TRUE, nchgbds) );
2406 
2407  return SCIP_OKAY;
2408 }
2409 
2410 
2411 /** presolving initialization method of propagator (called when presolving is about to begin) */
2412 static
2413 SCIP_DECL_PROPINITPRE(propInitpreGenvbounds)
2414 { /*lint --e{715}*/
2415  SCIP_PROPDATA* propdata;
2416 
2417  assert(scip != NULL);
2418  assert(prop != NULL);
2419  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2420 
2421  /* get propagator data */
2422  propdata = SCIPpropGetData(prop);
2423  assert(propdata != NULL);
2424 
2425  /* lock the variable because it should not be deleted after a restart */
2426  if( propdata->cutoffboundvar != NULL )
2427  {
2428  SCIPdebugMsg(scip, "propinitpre in problem <%s>: locking cutoffboundvar (current downlocks=%d, uplocks=%d)\n",
2429  SCIPgetProbName(scip), SCIPvarGetNLocksDownType(propdata->cutoffboundvar, SCIP_LOCKTYPE_MODEL),
2430  SCIPvarGetNLocksUpType(propdata->cutoffboundvar, SCIP_LOCKTYPE_MODEL));
2431 
2432  SCIP_CALL( SCIPaddVarLocksType(scip, propdata->cutoffboundvar, SCIP_LOCKTYPE_MODEL, 1, 1) );
2433  }
2434 
2435  return SCIP_OKAY;
2436 }
2437 
2438 
2439 /** presolving deinitialization method of propagator (called after presolving has been finished) */
2440 static
2441 SCIP_DECL_PROPEXITPRE(propExitpreGenvbounds)
2442 { /*lint --e{715}*/
2443  SCIP_VAR** vars;
2444  SCIP_PROPDATA* propdata;
2445  int i;
2446 
2447  assert(scip != NULL);
2448  assert(prop != NULL);
2449  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2450 
2451  SCIPdebugMsg(scip, "propexitpre in problem <%s>: removing fixed, aggregated, negated, and multi-aggregated variables from right-hand side\n",
2452  SCIPgetProbName(scip));
2453 
2454  /* get propagator data */
2455  propdata = SCIPpropGetData(prop);
2456  assert(propdata != NULL);
2457 
2458  /* there should be no events on the right-hand side variables */
2459  assert(propdata->lbevents == NULL);
2460  assert(propdata->ubevents == NULL);
2461 
2462  /* allocate memory to store new variables */
2463  SCIP_CALL( SCIPallocBufferArray(scip, &vars, SCIPgetNTotalVars(scip)) );
2464 
2465  for( i = 0; i < propdata->ngenvbounds; )
2466  {
2467  GENVBOUND* genvbound;
2468  int requiredsize;
2469  int nvars;
2470  int j;
2471 
2472  genvbound = propdata->genvboundstore[i];
2473  assert(genvbound != NULL);
2474 
2475  /* store variables of the genvbound to release them properly */
2476  assert(genvbound->ncoefs <= SCIPgetNTotalVars(scip));
2477  BMScopyMemoryArray(vars, genvbound->vars, genvbound->ncoefs);
2478  nvars = genvbound->ncoefs;
2479 
2480  /* replace non-active by active variables and update constant; note that this may result in coefficients where
2481  * SCIPisZero() is true; this should not create any problems
2482  */
2483  SCIP_CALL( SCIPgetProbvarLinearSum(scip, genvbound->vars, genvbound->coefs, &genvbound->ncoefs, genvbound->ncoefs, &genvbound->constant, &requiredsize, TRUE) );
2484 
2485  /* if space was not enough we need to resize the buffers */
2486  if( requiredsize > genvbound->ncoefs )
2487  {
2488  /* reallocate memory for arrays in genvbound to free unused memory */
2489  if( genvbound->coefssize < requiredsize )
2490  {
2491  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(genvbound->coefs), genvbound->coefssize, requiredsize) );
2492  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(genvbound->vars), genvbound->coefssize, requiredsize) );
2493  genvbound->coefssize = requiredsize;
2494  }
2495 
2496  SCIP_CALL( SCIPgetProbvarLinearSum(scip, genvbound->vars, genvbound->coefs, &genvbound->ncoefs, requiredsize, &genvbound->constant, &requiredsize, TRUE) );
2497  assert(requiredsize <= genvbound->ncoefs);
2498  }
2499 
2500  /* capture new and release old variables */
2501  for( j = 0; j < genvbound->ncoefs; ++j )
2502  {
2503  assert(genvbound->vars[j] != NULL);
2504  SCIP_CALL( SCIPcaptureVar(scip, genvbound->vars[j]) );
2505  }
2506  for( j = 0; j < nvars; ++j )
2507  {
2508  assert(vars[j] != NULL);
2509  SCIP_CALL( SCIPreleaseVar(scip, &vars[j]) );
2510  }
2511 
2512  /* if the resulting genvbound is trivial, remove it */
2513  /* we remove all genvbounds with an aggregated or multi-aggregated genvbound->var; tightening aggregated variables
2514  * might lead to some asserts in tree.c if the active variable has been already tightened (see !398);
2515  *
2516  * @todo replace aggregated variable by their active part
2517  */
2518  if( (genvbound->ncoefs == 0 && SCIPisZero(scip, genvbound->cutoffcoef))
2519  || SCIPvarGetStatus(genvbound->var) == SCIP_VARSTATUS_MULTAGGR
2520  || SCIPvarGetStatus(genvbound->var) == SCIP_VARSTATUS_AGGREGATED )
2521  {
2522  SCIP_HASHMAP* hashmap;
2523 
2524  hashmap = genvbound->boundtype == SCIP_BOUNDTYPE_LOWER ? propdata->lbgenvbounds : propdata->ubgenvbounds;
2525 
2526  /* remove genvbound from hashmap */
2527  assert(SCIPhashmapExists(hashmap, genvbound->var));
2528  SCIP_CALL( SCIPhashmapRemove(hashmap, genvbound->var) );
2529 
2530  /* free genvbound and fill gap */
2531  SCIP_CALL( freeGenVBound(scip, propdata->genvboundstore[i]) );
2532  --(propdata->ngenvbounds);
2533 
2534  /* move the last genvbound to the i-th position */
2535  if( i < propdata->ngenvbounds )
2536  {
2537  propdata->genvboundstore[i] = propdata->genvboundstore[propdata->ngenvbounds];
2538  propdata->genvboundstore[i]->index = i;
2539 
2540  /* mark genvbounds array to be resorted */
2541  propdata->issorted = FALSE;
2542  }
2543  }
2544  else
2545  ++i;
2546  }
2547 
2548  SCIPfreeBufferArray(scip, &vars);
2549 
2550  return SCIP_OKAY;
2551 }
2552 
2553 /** deinitialization method of propagator (called before transformed problem is freed) */
2554 static
2555 SCIP_DECL_PROPEXIT(propExitGenvbounds)
2556 {
2557  SCIP_PROPDATA* propdata;
2558 
2559  assert(scip != NULL);
2560  assert(prop != NULL);
2561  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2562 
2563  /* get propagator data */
2564  propdata = SCIPpropGetData(prop);
2565  assert(propdata != NULL);
2566 
2567  /* free remaining genvbounds */
2568  SCIP_CALL( freeGenVBounds(scip, propdata) );
2569 
2570  return SCIP_OKAY;
2571 }
2572 
2573 /** execution method of propagator */
2574 static
2575 SCIP_DECL_PROPEXEC(propExecGenvbounds)
2576 { /*lint --e{715}*/
2577  SCIP_PROPDATA* propdata;
2578 
2579  assert(scip != NULL);
2580  assert(prop != NULL);
2581  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2582 
2583  *result = SCIP_DIDNOTRUN;
2584 
2585  /* do not run if propagation w.r.t. current objective is not allowed */
2586  if( !SCIPallowWeakDualReds(scip) )
2587  return SCIP_OKAY;
2588 
2589  /* get propagator data */
2590  propdata = SCIPpropGetData(prop);
2591  assert(propdata != NULL);
2592 
2593  /* update upper bound of the cutoffboundvar */
2594  if( propdata->cutoffboundvar != NULL )
2595  {
2596  SCIP_Real newub;
2597  SCIP_Real oldub;
2598  SCIP_Bool infeasible;
2599  SCIP_Bool tightened;
2600 
2601  assert(propdata->propasconss);
2602 
2603  /* compute the primal bound in the original problem */
2604  newub = getCutoffboundGenVBound(scip);
2605  oldub = SCIPvarGetUbLocal(propdata->cutoffboundvar);
2606 
2607  if( SCIPisInfinity(scip, newub) == FALSE && SCIPisFeasLT(scip, newub, oldub) )
2608  {
2609  SCIP_CALL( SCIPtightenVarUbGlobal(scip, propdata->cutoffboundvar, newub, FALSE, &infeasible, &tightened) );
2610 
2611  if( tightened )
2612  {
2613  SCIPdebugMsg(scip, "tightened UB of cutoffboundvar to %e (old: %e, infeas: %u, tightened: %u)\n",
2614  newub, oldub, infeasible, tightened);
2615  }
2616 
2617  assert(infeasible == FALSE);
2618  }
2619  }
2620 
2621  SCIPdebugMsg(scip, "propexec in problem <%s> at depth %d%s\n", SCIPgetProbName(scip), SCIPgetDepth(scip),
2622  SCIPinProbing(scip) ? " in probing" : "");
2623 
2624  /* do not run if no genvbounds were added yet */
2625  if( propdata->ngenvbounds < 1 )
2626  {
2627  /**@todo is it really no performance issue to be called each time when there are no genvbounds, e.g., for MIPs? */
2628  SCIPdebugMsg(scip, "no bounds were added yet\n");
2629  return SCIP_OKAY;
2630  }
2631 
2632  /* add the genvbounds in the genvboundstore as constraints to the problem; afterwards clear the genvboundstore */
2633  if( propdata->propasconss )
2634  {
2635  SCIP_CALL( createConstraints(scip, propdata) );
2636  return SCIP_OKAY;
2637  }
2638 
2639  /* propagate locally and globally */
2640  SCIP_CALL( execGenVBounds(scip, propdata, result, !SCIPinProbing(scip), NULL) );
2641 
2642  /* when called in presolving stage the result is set to SCIP_SUCCESS instead of SCIP_REDUCEDDOM, this is corrected
2643  * here
2644  */
2645  if( *result == SCIP_SUCCESS )
2646  *result = SCIP_REDUCEDDOM;
2647 
2648  SCIPdebugMsg(scip, "end of exec\n");
2649 
2650  return SCIP_OKAY;
2651 }
2652 
2653 /** propagation conflict resolving method of propagator */
2654 static
2655 SCIP_DECL_PROPRESPROP(propRespropGenvbounds)
2656 { /*lint --e{715}*/
2657  SCIP_PROPDATA* propdata;
2658  GENVBOUND* genvbound;
2659  SCIP_Real boundval;
2660  SCIP_Bool success;
2661 
2662  SCIPdebugMsg(scip, "explain %s bound change of variable <%s>\n",
2663  boundtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper", SCIPvarGetName(infervar));
2664 
2665  /* get propagator data */
2666  propdata = SCIPpropGetData(prop);
2667  assert(propdata != NULL);
2668  assert(propdata->genvboundstore != NULL);
2669 
2670  /* as inferinfo we passed the index of the genvbound that was used for propagation; the genvbound might have been
2671  * replaced, but also the new genvbound at this position has the same variable on the left-hand side
2672  */
2673  assert(inferinfo >= 0);
2674  assert(inferinfo < propdata->ngenvbounds);
2675 
2676  *result = SCIP_DIDNOTFIND;
2677 
2678  /* check also in optimized mode that inferinfo is correct */
2679  if( inferinfo >= propdata->ngenvbounds)
2680  {
2681  SCIPerrorMessage("generalized variable bounds propagator received inferinfo out of range; propagation not resolved, safe to continue\n");
2682  return SCIP_OKAY;
2683  }
2684 
2685  /* get genvbound responsible for the bound change */
2686  genvbound = propdata->genvboundstore[inferinfo];
2687  assert(genvbound != NULL);
2688  assert(genvbound->var == infervar);
2689 
2690  /* check also in optimized mode that inferinfo is correct */
2691  if( genvbound->var != infervar )
2692  {
2693  SCIPerrorMessage("generalized variable bounds propagator received incorrect inferinfo; propagation not resolved, but it's safe to continue\n");
2694  return SCIP_OKAY;
2695  }
2696 
2697  /* get value of bound change on left-hand side */
2698  boundval = genvbound->boundtype == SCIP_BOUNDTYPE_LOWER
2699  ? SCIPgetVarLbAtIndex(scip, genvbound->var, bdchgidx, TRUE)
2700  : -SCIPgetVarUbAtIndex(scip, genvbound->var, bdchgidx, TRUE);
2701 
2702  /* if left-hand side variable is integral, it suffices to explain a bound change greater than boundval - 1 */
2703  if( SCIPvarIsIntegral(genvbound->var) )
2704  {
2705  SCIP_Real roundedboundval;
2706 
2707  assert(SCIPisIntegral(scip, boundval));
2708 
2709  roundedboundval = SCIPfeasCeil(scip, boundval - 1.0) + 2 * SCIPfeastol(scip);
2710  boundval = MIN(boundval, roundedboundval);
2711  }
2712 
2713  /* resolve propagation */
2714  SCIP_CALL( resolveGenVBoundPropagation(scip, genvbound, bdchgidx, &boundval, &success) );
2715 
2716  if( success )
2717  *result = SCIP_SUCCESS;
2718 
2719  return SCIP_OKAY;
2720 }
2721 
2722 /** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
2723 static
2724 SCIP_DECL_PROPEXITSOL(propExitsolGenvbounds)
2725 { /*lint --e{715}*/
2726  SCIP_PROPDATA* propdata;
2727 
2728  assert(scip != NULL);
2729  assert(prop != NULL);
2730  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2731 
2732  SCIPdebugMsg(scip, "propexitsol in problem <%s>\n", SCIPgetProbName(scip));
2733 
2734  /* get propagator data */
2735  propdata = SCIPpropGetData(prop);
2736  assert(propdata != NULL);
2737 
2738  if( !SCIPisInRestart(scip) )
2739  {
2740  /* free all genvbounds if we are not in a restart */
2741  SCIP_CALL( freeGenVBounds(scip, propdata) );
2742  }
2743  else
2744  {
2745  /* free all genvbounds that use relax-only variables if we are in a restart */
2746  SCIP_CALL( freeGenVBoundsRelaxOnly(scip, propdata) );
2747  }
2748 
2749  /* drop and free all events */
2750  SCIP_CALL( dropAndFreeEvents(scip, propdata) );
2751 
2752  return SCIP_OKAY;
2753 }
2754 
2755 /** destructor of propagator to free user data (called when SCIP is exiting) */
2756 static
2757 SCIP_DECL_PROPFREE(propFreeGenvbounds)
2758 { /*lint --e{715}*/
2759  SCIP_PROPDATA* propdata;
2760 
2761  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2762 
2763  /* free propagator data */
2764  propdata = SCIPpropGetData(prop);
2765  assert(propdata != NULL);
2766 
2767  SCIPfreeBlockMemory(scip, &propdata);
2768 
2769  SCIPpropSetData(prop, NULL);
2770 
2771  return SCIP_OKAY;
2772 }
2773 
2774 
2775 /*
2776  * Callback methods of event handler
2777  */
2778 
2779 static
2780 SCIP_DECL_EVENTEXEC(eventExecGenvbounds)
2781 { /*lint --e{715}*/
2782  SCIP_PROPDATA* propdata;
2783  int i;
2785  assert(scip != NULL);
2786  assert(eventdata != NULL);
2787 
2788  assert(SCIPeventGetType(event) == SCIP_EVENTTYPE_LBTIGHTENED || SCIPeventGetType(event) ==
2790 
2791  assert(eventdata->startcomponents != NULL);
2792  assert(eventdata->startindices != NULL);
2793  assert(eventdata->nstarts > 0);
2794  assert(eventdata->prop != NULL);
2795 
2796  propdata = SCIPpropGetData(eventdata->prop);
2797  assert(propdata != NULL);
2798 
2799  assert(propdata->startcomponents != NULL);
2800  assert(propdata->startmap != NULL);
2801  assert(propdata->startindices != NULL);
2802 
2803  SCIPdebugMsg(scip, "catching eventdata:\n");
2804  SCIPdebug( printEventData(eventdata, SCIPeventGetType(event) == SCIP_EVENTTYPE_LBTIGHTENED ?
2806 
2807  /* check if we need to reset old local starting indices data */
2808  if( SCIPgetCurrentNode(scip) != propdata->lastnodecaught )
2809  {
2810  SCIP_CALL( resetLocalStartingData(scip, propdata) );
2811  propdata->lastnodecaught = SCIPgetCurrentNode(scip);
2812  }
2813 
2814  for( i = 0; i < eventdata->nstarts; i++ )
2815  {
2816  int component;
2817  int startidx;
2818 
2819  component = eventdata->startcomponents[i];
2820  assert(component >= 0);
2821  startidx = eventdata->startindices[i];
2822 
2823  /* there is already an entry for this component */
2824  if( SCIPhashmapExists(propdata->startmap, (void*)(size_t) (component + 1)) )
2825  {
2826  int componentidx;
2827 
2828  /* get its index */
2829  componentidx = (SCIPhashmapGetImageInt(propdata->startmap, (void*)(size_t) (component + 1))) - 1; /*lint !e571 !e776*/
2830  assert(componentidx >= 0);
2831  assert(propdata->startcomponents[componentidx] == component);
2832 
2833  if( propdata->startindices[componentidx] > startidx )
2834  propdata->startindices[componentidx] = startidx;
2835  }
2836  else
2837  {
2838  /* get a new entry */
2839  int componentidx;
2840  componentidx = propdata->nindices;
2841 
2842  /* store index */
2843  propdata->startcomponents[componentidx] = component;
2844  propdata->startindices[componentidx] = startidx;
2845 
2846  /* store component in hashmap */
2847  SCIP_CALL( SCIPhashmapInsertInt(propdata->startmap, (void*)(size_t) (component + 1), componentidx + 1) ); /*lint !e571 !e776*/
2848 
2849  /* increase number of starting indices */
2850  propdata->nindices++;
2851  }
2852  }
2853 
2854  return SCIP_OKAY;
2855 }
2856 
2857 /*
2858  * propagator specific interface methods
2859  */
2860 
2861 /** creates the genvbounds propagator and includes it in SCIP */
2863  SCIP* scip /**< SCIP data structure */
2864  )
2865 {
2866  SCIP_PROPDATA* propdata;
2867  SCIP_PROP* prop;
2868 
2869  /* create genvbounds propagator data */
2870  SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) );
2871 
2872  /* include propagator */
2874  propExecGenvbounds, propdata) );
2875 
2876  SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyGenvbounds) );
2877  SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeGenvbounds) );
2878  SCIP_CALL( SCIPsetPropInit(scip, prop, propInitGenvbounds) );
2879  SCIP_CALL( SCIPsetPropInitpre(scip, prop, propInitpreGenvbounds) );
2880  SCIP_CALL( SCIPsetPropExitpre(scip, prop, propExitpreGenvbounds) );
2881  SCIP_CALL( SCIPsetPropExit(scip, prop, propExitGenvbounds) );
2882  SCIP_CALL( SCIPsetPropExitsol(scip, prop, propExitsolGenvbounds) );
2883  SCIP_CALL( SCIPsetPropPresol(scip, prop, propPresolGenvbounds, PROP_PRESOL_PRIORITY,
2885  SCIP_CALL( SCIPsetPropResprop(scip, prop, propRespropGenvbounds) );
2886 
2887  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/global",
2888  "apply global propagation?",
2889  &propdata->global, TRUE, DEFAULT_GLOBAL_PROPAGATION, NULL, NULL) );
2890 
2891  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/propinrootnode",
2892  "apply genvbounds in root node if no new incumbent was found?",
2893  &propdata->propinrootnode, TRUE, DEFAULT_PROPAGATE_IN_ROOT_NODE, NULL, NULL) );
2894 
2895  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/sort",
2896  "sort genvbounds and wait for bound change events?",
2897  &propdata->sort, TRUE, DEFAULT_SORT, NULL, NULL) );
2898 
2899  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/propasconss",
2900  "should genvbounds be transformed to (linear) constraints?",
2901  &propdata->propasconss, TRUE, DEFAULT_PROPASCONSS, NULL, NULL) );
2902 
2903  /* include event handler */
2904  SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &propdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecGenvbounds, NULL) );
2905 
2906  return SCIP_OKAY;
2907 }
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
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
static SCIP_RETCODE applyGenVBound(SCIP *scip, SCIP_PROP *prop, GENVBOUND *genvbound, SCIP_Bool global, SCIP_RESULT *result, int *nchgbds)
SCIP_Real SCIPfeastol(SCIP *scip)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2128
public methods for SCIP parameter handling
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3299
static SCIP_RETCODE freeComponentsData(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:91
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:365
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1992
static SCIP_RETCODE freeGenVBound(SCIP *scip, GENVBOUND *genvbound)
static SCIP_RETCODE execGenVBounds(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_RESULT *result, SCIP_Bool local, int *nchgbds)
public methods for memory management
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:354
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
static SCIP_RETCODE initPropdata(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17923
static SCIP_RETCODE applyGenVBounds(SCIP *scip, SCIP_PROP *prop, SCIP_Bool global, SCIP_RESULT *result, int *nchgbds)
#define SCIP_MAXSTRLEN
Definition: def.h:302
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3357
public methods for conflict handler plugins and conflict analysis
static SCIP_RETCODE dropAndFreeEvents(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_RETCODE SCIPdigraphComputeUndirectedComponents(SCIP_DIGRAPH *digraph, int minsize, int *components, int *ncomponents)
Definition: misc.c:8001
static long bound
#define PROP_PRESOL_MAXROUNDS
#define PROP_DESC
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17979
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPinferVarLbProp(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_PROP *inferprop, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5895
public solving methods
static SCIP_DECL_PROPEXEC(propExecGenvbounds)
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:104
static SCIP_RETCODE freeAllEventData(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1248
static SCIP_RETCODE analyzeGenVBoundConflict(SCIP *scip, GENVBOUND *genvbound)
static SCIP_RETCODE freeEventData(SCIP *scip, SCIP_EVENTDATA **eventdata)
#define PROP_NAME
#define PROP_FREQ
SCIP_VAR * var
#define FALSE
Definition: def.h:96
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3024
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10788
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:95
#define SCIPdebug(x)
Definition: pub_message.h:93
SCIP_Real SCIPgetConflictVarUb(SCIP *scip, SCIP_VAR *var)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
static SCIP_DECL_PROPEXITSOL(propExitsolGenvbounds)
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3142
static GENVBOUND * getGenVBound(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype)
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition: scip_var.c:194
public methods for problem variables
SCIP_RETCODE SCIPaddConflictRelaxedLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedlb)
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
int SCIPdigraphGetNComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:8196
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPdebugMessage
Definition: pub_message.h:96
static SCIP_RETCODE resetLocalStartingData(SCIP *scip, SCIP_PROPDATA *propdata)
#define PROP_PRESOLTIMING
void SCIPdigraphGetComponent(SCIP_DIGRAPH *digraph, int compidx, int **nodes, int *nnodes)
Definition: misc.c:8209
static SCIP_Real getGenVBoundsMinActivity(SCIP *scip, SCIP_VAR **vars, SCIP_Real *coefs, int nvars, SCIP_Bool global)
#define DEFAULT_PROPASCONSS
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3211
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
public methods for SCIP variables
static SCIP_RETCODE fillGlobalStartingData(SCIP *scip, SCIP_PROPDATA *propdata)
#define SCIPdebugMsgPrint
Definition: scip_message.h:79
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPdigraphTopoSortComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:8130
SCIP_RETCODE SCIPcreateDigraph(SCIP *scip, SCIP_DIGRAPH **digraph, int nnodes)
static SCIP_DECL_PROPEXITPRE(propExitpreGenvbounds)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
static SCIP_RETCODE addEventData(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, int startindex, int startcomponent, SCIP_BOUNDTYPE boundtype)
public methods for numerical tolerances
public methods for querying solving statistics
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1075
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3373
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4259
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
public methods for the branch-and-bound tree
#define PROP_TIMING
int SCIPdigraphGetNNodes(SCIP_DIGRAPH *digraph)
Definition: misc.c:7658
int SCIPgetNFixedVars(SCIP *scip)
Definition: scip_prob.c:2317
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17933
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
SCIP_RETCODE SCIPsetPropExitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITPRE((*propexitpre)))
Definition: scip_prop.c:263
static SCIP_RETCODE addNewGenVBound(SCIP *scip, SCIP_PROPDATA *propdata, GENVBOUND *genvbound)
#define SCIPerrorMessage
Definition: pub_message.h:64
SCIP_Bool relaxonly
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2778
#define SCIPdebugPrintf
Definition: pub_message.h:99
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for event handler plugins and event handlers
static SCIP_RETCODE freeGenVBoundsRelaxOnly(SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_Real getGenVBoundsBound(SCIP *scip, GENVBOUND *genvbound, SCIP_Bool global)
static SCIP_RETCODE resolveGenVBoundPropagation(SCIP *scip, GENVBOUND *genvbound, SCIP_BDCHGIDX *bdchgidx, SCIP_Real *boundval, SCIP_Bool *success)
#define PROP_PRIORITY
static SCIP_DECL_EVENTEXEC(eventExecGenvbounds)
SCIP_RETCODE SCIPgenVBoundAdd(SCIP *scip, SCIP_PROP *genvboundprop, SCIP_VAR **vars, SCIP_VAR *var, SCIP_Real *coefs, int ncoefs, SCIP_Real coefcutoffbound, SCIP_Real constant, SCIP_BOUNDTYPE boundtype)
#define DEFAULT_PROPAGATE_IN_ROOT_NODE
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
SCIP_Real SCIPgetConflictVarLb(SCIP *scip, SCIP_VAR *var)
static SCIP_DECL_PROPEXIT(propExitGenvbounds)
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8715
static SCIP_Real getGenVBoundsMinActivityConflict(SCIP *scip, SCIP_VAR **vars, SCIP_Real *coefs, int nvars, SCIP_BDCHGIDX *bdchgidx)
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:173
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17264
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3058
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
SCIP_Real * coefs
#define NULL
Definition: lpi_spx1.cpp:164
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1491
#define REALABS(x)
Definition: def.h:210
#define SCIP_CALL(x)
Definition: def.h:394
#define SCIP_EVENTTYPE_LBTIGHTENED
Definition: type_event.h:77
int SCIPgetNTotalVars(SCIP *scip)
Definition: scip_prob.c:2577
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPinferVarUbProp(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_PROP *inferprop, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6010
SCIP_RETCODE SCIPgetProbvarLinearSum(SCIP *scip, SCIP_VAR **vars, SCIP_Real *scalars, int *nvars, int varssize, SCIP_Real *constant, int *requiredsize, SCIP_Bool mergemultiples)
Definition: scip_var.c:1738
SCIP_Bool SCIPvarIsRelaxationOnly(SCIP_VAR *var)
Definition: var.c:17551
SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
Definition: misc.c:7574
#define SCIPdebugCheckLbGlobal(scip, var, lb)
Definition: debug.h:285
#define SCIPdebugGetSolVal(scip, var, val)
Definition: debug.h:299
static SCIP_RETCODE freeGenVBounds(SCIP *scip, SCIP_PROPDATA *propdata)
#define SCIPdebugCheckUbGlobal(scip, var, ub)
Definition: debug.h:286
#define PROP_PRESOL_PRIORITY
public methods for constraint handler plugins and constraints
static SCIP_RETCODE createConstraints(SCIP *scip, SCIP_PROPDATA *propdata)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIP_UNKNOWN
Definition: def.h:207
SCIP_RETCODE SCIPsetPropInit(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINIT((*propinit)))
Definition: scip_prop.c:183
public data structures and miscellaneous methods
static SCIP_RETCODE setUpEvents(SCIP *scip, SCIP_PROPDATA *propdata)
#define SCIP_Bool
Definition: def.h:93
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:1030
SCIP_BOUNDTYPE boundtype
SCIP_RETCODE SCIPhashmapRemoveAll(SCIP_HASHMAP *hashmap)
Definition: misc.c:3583
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
SCIP_VAR ** vars
#define EVENTHDLR_NAME
#define MAX(x, y)
Definition: tclique_def.h:92
methods for debugging
SCIP_RETCODE SCIPaddConflictRelaxedUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedub)
static SCIP_Real getCutoffboundGenVBound(SCIP *scip)
#define DEFAULT_SORT
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip_prop.c:151
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:400
SCIP_RETCODE SCIPdigraphComputeDirectedComponents(SCIP_DIGRAPH *digraph, int compidx, int *strongcomponents, int *strongcompstartidx, int *nstrongcomponents)
Definition: misc.c:8341
SCIP_Bool SCIPallowWeakDualReds(SCIP *scip)
Definition: scip_var.c:8656
SCIP_Real cutoffcoef
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:136
static SCIP_DECL_PROPFREE(propFreeGenvbounds)
static SCIP_DECL_PROPINITPRE(propInitpreGenvbounds)
#define SCIP_EVENTTYPE_UBTIGHTENED
Definition: type_event.h:79
Constraint handler for linear constraints in their most general form, .
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPgetTransObjscale(SCIP *scip)
Definition: scip_prob.c:1398
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
Definition: scip_prop.c:231
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:97
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:941
#define EVENTHDLR_DESC
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:2000
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_Real SCIPgetTransObjoffset(SCIP *scip)
Definition: scip_prob.c:1375
public methods for managing events
SCIP_RETCODE SCIPhashmapRemove(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3389
general public methods
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip_prop.c:312
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
public methods for solutions
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1676
public methods for the probing mode
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1119
SCIP_Real constant
public methods for message output
static SCIP_RETCODE createStartingData(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17383
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1214
#define SCIP_Real
Definition: def.h:186
static SCIP_RETCODE getEventData(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_EVENTDATA **eventdata)
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:52
static SCIP_RETCODE sortGenVBounds(SCIP *scip, SCIP_PROPDATA *propdata)
public methods for message handling
public methods for data structures
#define SCIP_INVALID
Definition: def.h:206
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
public methods for propagator plugins
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define PROP_DELAY
#define DEFAULT_GLOBAL_PROPAGATION
#define nnodes
Definition: gastrans.c:74
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17989
static SCIP_DECL_PROPCOPY(propCopyGenvbounds)
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_RETCODE SCIPincludePropGenvbounds(SCIP *scip)
static SCIP_DECL_PROPRESPROP(propRespropGenvbounds)
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3106
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:132
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3231
SCIP_RETCODE SCIPsetPropInitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITPRE((*propinitpre)))
Definition: scip_prop.c:247
void SCIPdigraphFree(SCIP_DIGRAPH **digraph)
Definition: misc.c:7480
SCIP_RETCODE SCIPsetPropExit(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXIT((*propexit)))
Definition: scip_prop.c:199
public methods for global and local (sub)problems
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17455
static SCIP_RETCODE freeStartingData(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_Bool SCIPisInRestart(SCIP *scip)
Definition: scip_solve.c:3714
static SCIP_DECL_PROPPRESOL(propPresolGenvbounds)
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
Definition: scip_var.c:8629
SCIP_RETCODE SCIPanalyzeConflict(SCIP *scip, int validdepth, SCIP_Bool *success)
static SCIP_DECL_PROPINIT(propInitGenvbounds)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17593
public methods for propagators
generalized variable bounds propagator
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