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