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