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