Scippy

SCIP

Solving Constraint Integer Programs

cons_varbound.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-2016 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_varbound.c
17  * @brief Constraint handler for variable bound constraints \f$lhs \le x + c y \le rhs\f$.
18  * @author Tobias Achterberg
19  * @author Timo Berthold
20  * @author Michael Winkler
21  * @author Gerald Gamrath
22  * @author Stefan Heinz
23  *
24  * This constraint handler handles a special type of linear constraints, namely variable bound constraints.
25  * A variable bound constraint has the form
26  * \f[
27  * lhs \leq x + c y \leq rhs
28  * \f]
29  * with coefficient \f$c \in Q\f$, \f$lhs\in Q \cup \{-\infty\}\f$, \f$rhs\in Q \cup \{\infty\}\f$,
30  * and decision variables \f$x\f$ (non-binary) and \f$y\f$ (binary or integer).
31  *
32  * @note Although x must be non-binary when the constraint is created, it can happen that x is upgraded to a binary
33  * variable, e.g. due to aggregations or bound changes in presolving.
34  */
35 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
36 
37 #include <assert.h>
38 #include <string.h>
39 #include <limits.h>
40 #include <ctype.h>
41 
42 #include "scip/cons_varbound.h"
43 #include "scip/cons_linear.h"
44 #include "scip/cons_setppc.h"
45 
46 
47 /**@name Constraint handler properties
48  *
49  * @{
50  */
51 
52 /* constraint handler properties */
53 #define CONSHDLR_NAME "varbound"
54 #define CONSHDLR_DESC "variable bounds lhs <= x + c*y <= rhs, x non-binary, y non-continuous"
55 #define CONSHDLR_SEPAPRIORITY +900000 /**< priority of the constraint handler for separation */
56 #define CONSHDLR_ENFOPRIORITY -500000 /**< priority of the constraint handler for constraint enforcing */
57 #define CONSHDLR_CHECKPRIORITY -500000 /**< priority of the constraint handler for checking feasibility */
58 #define CONSHDLR_SEPAFREQ 0 /**< frequency for separating cuts; zero means to separate only in the root node */
59 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
60 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
61  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
62 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
63 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
64 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
65 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
66 
67 #define CONSHDLR_PRESOLTIMING (SCIP_PRESOLTIMING_FAST | SCIP_PRESOLTIMING_MEDIUM)
68 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
69 
70 #define EVENTHDLR_NAME "varbound"
71 #define EVENTHDLR_DESC "bound change event handler for variable bound constraints"
72 
73 #define LINCONSUPGD_PRIORITY +50000 /**< priority of the constraint handler for upgrading of linear constraints */
74 
75 /**@} */
76 
77 /**@name Default parameter values
78  *
79  * @{
80  */
81 
82 #define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
83 #define DEFAULT_MAXLPCOEF 1e+09 /**< maximum coefficient in varbound constraint to be added as a row into LP */
84 #define DEFAULT_USEBDWIDENING TRUE /**< should bound widening be used to initialize conflict analysis? */
85 
86 
87 #define MAXSCALEDCOEF 1000LL /**< maximal coefficient value after scaling */
88 
89 /**@} */
90 
91 /** variable bound constraint data */
92 struct SCIP_ConsData
93 {
94  SCIP_Real vbdcoef; /**< coefficient c of bounding variable y */
95  SCIP_Real lhs; /**< left hand side of variable bound inequality */
96  SCIP_Real rhs; /**< right hand side of variable bound inequality */
97  SCIP_VAR* var; /**< variable x that has variable bound */
98  SCIP_VAR* vbdvar; /**< binary, integer or implicit integer bounding variable y */
99  SCIP_ROW* row; /**< LP row, if constraint is already stored in LP row format */
100  unsigned int propagated:1; /**< is the variable bound constraint already propagated? */
101  unsigned int presolved:1; /**< is the variable bound constraint already presolved? */
102  unsigned int varboundsadded:1; /**< are the globally valid variable bounds added? */
103  unsigned int changed:1; /**< was constraint changed since last aggregation round in preprocessing? */
104  unsigned int tightened:1; /**< were the vbdcoef and all sides already tightened? */
105 };
106 
107 /** constraint handler data */
108 struct SCIP_ConshdlrData
109 {
110  SCIP_EVENTHDLR* eventhdlr; /**< event handler for bound change events */
111  SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */
112  SCIP_Real maxlpcoef; /**< maximum coefficient in varbound constraint to be added as a row into LP */
113  SCIP_Bool usebdwidening; /**< should bound widening be used to in conflict analysis? */
114 };
115 
116 /** Propagation rules */
117 enum Proprule
118 {
119  PROPRULE_1, /**< left hand side and bounds on y -> lower bound on x */
120  PROPRULE_2, /**< left hand side and upper bound on x -> bound on y */
121  PROPRULE_3, /**< right hand side and bounds on y -> upper bound on x */
122  PROPRULE_4 /**< right hand side and lower bound on x -> bound on y */
123 };
124 typedef enum Proprule PROPRULE;
125 
126 
127 /**@name Local methods
128  *
129  */
130 
131 /** compares two varbound constraints cons1: \f$ lhs1 \le x1 + c1 y1 \le rhs1 \f$ and cons2: \f$ lhs2 \le x2 + c2 y2 \le rhs2 \f$
132  * w.r.t. the indices of the contained variables
133  *
134  * returns -1 if:
135  * - the index of x1 is smaller than the index of x2 or
136  * - x1 = x2 and the index of y1 is smaller than the index of y2 or
137  * - x1 = x2 and y1 = y2 and cons2 was recently changed, but cons1 not
138  *
139  * returns 0 if x1 = x2, y1 = y2, and the changed status of both constraints is the same
140  *
141  * and returns +1 otherwise
142  */
143 static
144 SCIP_DECL_SORTPTRCOMP(consVarboundComp)
145 {
146  SCIP_CONSDATA* consdata1;
147  SCIP_CONSDATA* consdata2;
148 
149  assert(elem1 != NULL);
150  assert(elem2 != NULL);
151 
152  consdata1 = SCIPconsGetData((SCIP_CONS*) elem1);
153  consdata2 = SCIPconsGetData((SCIP_CONS*) elem2);
154 
155  assert(consdata1 != NULL);
156  assert(consdata2 != NULL);
157 
158  /* comparison is done over 3 ordered criteria:
159  * (i) variable index of variable 1
160  * (ii) variable index of variable 2.
161  * (iii) changed status
162  */
163  if( SCIPvarGetIndex(consdata1->var) < SCIPvarGetIndex(consdata2->var)
164  || (SCIPvarGetIndex(consdata1->var) == SCIPvarGetIndex(consdata2->var)
165  && SCIPvarGetIndex(consdata1->vbdvar) < SCIPvarGetIndex(consdata2->vbdvar))
166  || (SCIPvarGetIndex(consdata1->var) == SCIPvarGetIndex(consdata2->var)
167  && SCIPvarGetIndex(consdata1->vbdvar) == SCIPvarGetIndex(consdata2->vbdvar)
168  && !consdata1->changed && consdata2->changed) )
169  return -1;
170  else if( SCIPvarGetIndex(consdata1->var) == SCIPvarGetIndex(consdata2->var)
171  && SCIPvarGetIndex(consdata1->vbdvar) == SCIPvarGetIndex(consdata2->vbdvar)
172  && (consdata1->changed == consdata2->changed) )
173  return 0;
174  else
175  return +1;
176 }
177 
178 /** creates constraint handler data for varbound constraint handler */
179 static
180 SCIP_RETCODE conshdlrdataCreate(
181  SCIP* scip, /**< SCIP data structure */
182  SCIP_CONSHDLRDATA** conshdlrdata, /**< pointer to store the constraint handler data */
183  SCIP_EVENTHDLR* eventhdlr /**< event handler */
184  )
185 {
186  assert(scip != NULL);
187  assert(conshdlrdata != NULL);
188 
189  SCIP_CALL( SCIPallocMemory(scip, conshdlrdata) );
190 
191  /* set event handler for bound change events */
192  (*conshdlrdata)->eventhdlr = eventhdlr;
193 
194  return SCIP_OKAY;
195 }
196 
197 /** frees constraint handler data for varbound constraint handler */
198 static
199 void conshdlrdataFree(
200  SCIP* scip, /**< SCIP data structure */
201  SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to the constraint handler data */
202  )
203 {
204  assert(scip != NULL);
205  assert(conshdlrdata != NULL);
206  assert(*conshdlrdata != NULL);
207 
208  SCIPfreeMemory(scip, conshdlrdata);
209 }
210 
211 /** catches events for variables
212  *
213  * @todo if lhs or rhs is infinite, catch only changes of the bound that could lead to propagation
214  */
215 static
216 SCIP_RETCODE catchEvents(
217  SCIP* scip, /**< SCIP data structure */
218  SCIP_CONS* cons, /**< variable bound constraint */
219  SCIP_EVENTHDLR* eventhdlr /**< event handler */
220  )
221 {
222  SCIP_CONSDATA* consdata;
223  assert(cons != NULL);
224  assert(eventhdlr != NULL);
225  consdata = SCIPconsGetData(cons);
226  assert(consdata != NULL);
227 
228  SCIP_CALL( SCIPcatchVarEvent(scip, consdata->var, SCIP_EVENTTYPE_BOUNDTIGHTENED | SCIP_EVENTTYPE_VARFIXED, eventhdlr, (SCIP_EVENTDATA*)cons, NULL) );
229  SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vbdvar, SCIP_EVENTTYPE_BOUNDTIGHTENED | SCIP_EVENTTYPE_VARFIXED, eventhdlr, (SCIP_EVENTDATA*)cons, NULL) );
230 
231  return SCIP_OKAY;
232 }
233 
234 /** drops events for variables */
235 static
236 SCIP_RETCODE dropEvents(
237  SCIP* scip, /**< SCIP data structure */
238  SCIP_CONS* cons, /**< variable bound constraint */
239  SCIP_EVENTHDLR* eventhdlr /**< event handler */
240  )
241 {
242  SCIP_CONSDATA* consdata;
243  assert(cons != NULL);
244  assert(eventhdlr != NULL);
245  consdata = SCIPconsGetData(cons);
246  assert(consdata != NULL);
247 
248  SCIP_CALL( SCIPdropVarEvent(scip, consdata->var, SCIP_EVENTTYPE_BOUNDTIGHTENED | SCIP_EVENTTYPE_VARFIXED, eventhdlr, (SCIP_EVENTDATA*)cons, -1) );
249  SCIP_CALL( SCIPdropVarEvent(scip, consdata->vbdvar, SCIP_EVENTTYPE_BOUNDTIGHTENED | SCIP_EVENTTYPE_VARFIXED, eventhdlr, (SCIP_EVENTDATA*)cons, -1) );
250 
251  return SCIP_OKAY;
252 }
253 
254 /** creates a variable bound constraint data object */
255 static
256 SCIP_RETCODE consdataCreate(
257  SCIP* scip, /**< SCIP data structure */
258  SCIP_CONSDATA** consdata, /**< pointer to store the variable bound constraint data */
259  SCIP_VAR* var, /**< variable x that has variable bound */
260  SCIP_VAR* vbdvar, /**< binary, integer or implicit integer bounding variable y */
261  SCIP_Real vbdcoef, /**< coefficient c of bounding variable y */
262  SCIP_Real lhs, /**< left hand side of variable bound inequality */
263  SCIP_Real rhs /**< right hand side of variable bound inequality */
264  )
265 {
266  assert(consdata != NULL);
267  assert(SCIPvarGetType(vbdvar) != SCIP_VARTYPE_CONTINUOUS);
268 
269  SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
270 
271  if( SCIPisInfinity(scip, rhs) )
272  rhs = SCIPinfinity(scip);
273  else if( SCIPisInfinity(scip, -rhs) )
274  rhs = -SCIPinfinity(scip);
275 
276  if( SCIPisInfinity(scip, -lhs) )
277  lhs = -SCIPinfinity(scip);
278  else if( SCIPisInfinity(scip, lhs) )
279  lhs = SCIPinfinity(scip);
280 
281  if( SCIPisGT(scip, lhs, rhs) )
282  {
283  SCIPerrorMessage("left hand side of varbound constraint greater than right hand side\n");
284  SCIPerrorMessage(" -> lhs=%g, rhs=%g\n", lhs, rhs);
285  return SCIP_INVALIDDATA;
286  }
287 
288  if( SCIPisInfinity(scip, vbdcoef) )
289  vbdcoef = SCIPinfinity(scip);
290  else if( SCIPisInfinity(scip, -vbdcoef) )
291  vbdcoef = -SCIPinfinity(scip);
292 
293  (*consdata)->var = var;
294  (*consdata)->vbdvar = vbdvar;
295  (*consdata)->vbdcoef = vbdcoef;
296  (*consdata)->lhs = lhs;
297  (*consdata)->rhs = rhs;
298  (*consdata)->row = NULL;
299  (*consdata)->propagated = FALSE;
300  (*consdata)->presolved = FALSE;
301  (*consdata)->varboundsadded = FALSE;
302  (*consdata)->changed = TRUE;
303  (*consdata)->tightened = FALSE;
304 
305  /* if we are in the transformed problem, get transformed variables, add variable bound information, and catch events */
306  if( SCIPisTransformed(scip) )
307  {
308  SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->var, &(*consdata)->var) );
309  SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->vbdvar, &(*consdata)->vbdvar) );
310 
311 #ifndef NDEBUG
312  assert(SCIPvarGetStatus(SCIPvarGetProbvar((*consdata)->var)) != SCIP_VARSTATUS_MULTAGGR);
313  assert(SCIPvarGetStatus(SCIPvarGetProbvar((*consdata)->vbdvar)) != SCIP_VARSTATUS_MULTAGGR);
314 #endif
315  }
316 
317  /* capture variables */
318  SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->var) );
319  SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vbdvar) );
320 
321  return SCIP_OKAY;
322 }
323 
324 /** frees a variable bound constraint data */
325 static
326 SCIP_RETCODE consdataFree(
327  SCIP* scip, /**< SCIP data structure */
328  SCIP_CONSDATA** consdata /**< pointer to the variable bound constraint */
329  )
330 {
331  assert(consdata != NULL);
332  assert(*consdata != NULL);
333 
334  /* release the row */
335  if( (*consdata)->row != NULL )
336  {
337  SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->row) );
338  }
339 
340  /* release variables */
341  SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->var) );
342  SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->vbdvar) );
343 
344  SCIPfreeBlockMemory(scip, consdata);
345 
346  return SCIP_OKAY;
347 }
348 
349 /** creates LP row corresponding to variable bound constraint */
350 static
351 SCIP_RETCODE createRelaxation(
352  SCIP* scip, /**< SCIP data structure */
353  SCIP_CONS* cons /**< variable bound constraint */
354  )
355 {
356  SCIP_CONSDATA* consdata;
357 
358  consdata = SCIPconsGetData(cons);
359  assert(consdata != NULL);
360  assert(consdata->row == NULL);
361 
362  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->row, SCIPconsGetHdlr(cons), SCIPconsGetName(cons), consdata->lhs, consdata->rhs,
363  SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), SCIPconsIsRemovable(cons)) );
364  SCIP_CALL( SCIPaddVarToRow(scip, consdata->row, consdata->var, 1.0) );
365  SCIP_CALL( SCIPaddVarToRow(scip, consdata->row, consdata->vbdvar, consdata->vbdcoef) );
366 
367  return SCIP_OKAY;
368 }
369 
370 /** adds linear relaxation of variable bound constraint to the LP */
371 static
372 SCIP_RETCODE addRelaxation(
373  SCIP* scip, /**< SCIP data structure */
374  SCIP_CONS* cons /**< variable bound constraint */
375  )
376 {
377  SCIP_CONSHDLR* conshdlr;
378  SCIP_CONSHDLRDATA* conshdlrdata;
379  SCIP_CONSDATA* consdata;
380 
381  consdata = SCIPconsGetData(cons);
382  assert(consdata != NULL);
383 
384  /* find the variable bound constraint handler */
385  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
386  if( conshdlr == NULL )
387  {
388  SCIPerrorMessage("variable bound constraint handler not found\n");
389  return SCIP_PLUGINNOTFOUND;
390  }
391 
392  conshdlrdata = SCIPconshdlrGetData(conshdlr);
393  assert(conshdlrdata != NULL);
394 
395  assert(SCIPvarGetType(consdata->vbdvar) != SCIP_VARTYPE_CONTINUOUS);
396 
397  /* check whether the coefficient is too large to put the row into the LP */
398  if( SCIPisGT(scip, REALABS(consdata->vbdcoef), conshdlrdata->maxlpcoef) )
399  return SCIP_OKAY;
400 
401  if( consdata->row == NULL )
402  {
403  SCIP_CALL( createRelaxation(scip, cons) );
404  }
405  assert(consdata->row != NULL);
406 
407  if( !SCIProwIsInLP(consdata->row) )
408  {
409  SCIP_Bool infeasible;
410 
411  SCIPdebugMessage("adding relaxation of variable bound constraint <%s>: ", SCIPconsGetName(cons));
412  SCIPdebug( SCIP_CALL( SCIPprintRow(scip, consdata->row, NULL)) );
413  SCIP_CALL( SCIPaddCut(scip, NULL, consdata->row, FALSE, &infeasible) );
414  assert( ! infeasible ); /* this function is only called from initlp -> row should be feasible */
415  }
416 
417  return SCIP_OKAY;
418 }
419 
420 /** returns whether the given solution is feasible for the given variable bound constraint */
421 static
422 SCIP_Bool checkCons(
423  SCIP* scip, /**< SCIP data structure */
424  SCIP_CONS* cons, /**< variable bound constraint */
425  SCIP_SOL* sol, /**< solution to check, NULL for current solution */
426  SCIP_Bool checklprows /**< Do constraints represented by rows in the current LP have to be checked? */
427  )
428 {
429  SCIP_CONSDATA* consdata;
430  SCIP_Real solval;
431 
432  consdata = SCIPconsGetData(cons);
433  assert(consdata != NULL);
434 
435  SCIPdebugMessage("checking variable bound constraint <%s> for feasibility of solution %p (lprows=%u)\n",
436  SCIPconsGetName(cons), (void*)sol, checklprows);
437 
438  solval = SCIPgetSolVal(scip, sol, consdata->var);
439 
440  if( SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, consdata->vbdvar)) && (!SCIPisFeasLE(scip, solval, consdata->rhs) || !SCIPisFeasGE(scip, solval, consdata->lhs)) )
441  return FALSE;
442 
443 
444  if( checklprows || consdata->row == NULL || !SCIProwIsInLP(consdata->row) )
445  {
446  SCIP_Real sum;
447 
448  sum = solval + consdata->vbdcoef * SCIPgetSolVal(scip, sol, consdata->vbdvar);
449 
450  return (SCIPisInfinity(scip, -consdata->lhs) || SCIPisFeasGE(scip, sum, consdata->lhs))
451  && (SCIPisInfinity(scip, consdata->rhs) || SCIPisFeasLE(scip, sum, consdata->rhs));
452  }
453  else
454  return TRUE;
455 }
456 
457 
458 /** resolves a propagation on the given variable by supplying the variables needed for applying the corresponding
459  * propagation rule (see propagateCons()):
460  * (1) left hand side and bounds on y -> lower bound on x
461  * (2) left hand side and upper bound on x -> bound on y
462  * (3) right hand side and bounds on y -> upper bound on x
463  * (4) right hand side and lower bound on x -> bound on y
464  */
465 static
466 SCIP_RETCODE resolvePropagation(
467  SCIP* scip, /**< SCIP data structure */
468  SCIP_CONS* cons, /**< constraint that inferred the bound change */
469  SCIP_VAR* infervar, /**< variable that was deduced */
470  PROPRULE proprule, /**< propagation rule that deduced the bound change */
471  SCIP_BOUNDTYPE boundtype, /**< the type of the changed bound (lower or upper bound) */
472  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
473  SCIP_Real inferbd, /**< inference bound which needs to be explained */
474  SCIP_Bool usebdwidening /**< should bound widening be used to in conflict analysis? */
475  )
476 {
477  SCIP_CONSDATA* consdata;
478  SCIP_VAR* vbdvar;
479  SCIP_VAR* var;
480  SCIP_Real vbdcoef;
481 
482  consdata = SCIPconsGetData(cons);
483  assert(consdata != NULL);
484  assert(!SCIPisZero(scip, consdata->vbdcoef));
485 
486  var = consdata->var;
487  assert(var != NULL);
488 
489  vbdvar = consdata->vbdvar;
490  assert(vbdvar != NULL);
491 
492  vbdcoef = consdata->vbdcoef;
493  assert(!SCIPisZero(scip, vbdcoef));
494 
495  switch( proprule )
496  {
497  case PROPRULE_1:
498  /* lhs <= x + c*y: left hand side and bounds on y -> lower bound on x */
499  assert(infervar == var);
500  assert(boundtype == SCIP_BOUNDTYPE_LOWER);
501  assert(!SCIPisInfinity(scip, -consdata->lhs));
502 
503  if( usebdwidening )
504  {
505  SCIP_Real relaxedbd;
506 
507  /* For integer variables, we can reduce the inferbound by 1 - 2eps, because this will be adjusted
508  * to the bound we need; however, if inferbound has a large value, adding 2*eps might be lost
509  * due to fixed precision floating point arithmetics, so we explicitly check this here.
510  */
511  if( SCIPvarIsIntegral(var) && inferbd < SCIPgetHugeValue(scip) * SCIPfeastol(scip))
512  relaxedbd = (consdata->lhs - (inferbd - 1.0 + 2*SCIPfeastol(scip))) / vbdcoef;
513  else
514  relaxedbd = (consdata->lhs - inferbd) / vbdcoef;
515 
516  /* check the computed relaxed lower/upper bound is a proper reason for the inference bound which has to be explained */
517  assert(SCIPisEQ(scip, inferbd, SCIPadjustedVarLb(scip, var, consdata->lhs - relaxedbd * vbdcoef)));
518 
519  if( vbdcoef > 0.0 )
520  {
521  SCIP_CALL( SCIPaddConflictRelaxedUb(scip, vbdvar, bdchgidx, relaxedbd) );
522  }
523  else
524  {
525  SCIP_CALL( SCIPaddConflictRelaxedLb(scip, vbdvar, bdchgidx, relaxedbd) );
526  }
527  }
528  else
529  {
530  if( vbdcoef > 0.0 )
531  {
532  SCIP_CALL( SCIPaddConflictUb(scip, vbdvar, bdchgidx) );
533  }
534  else
535  {
536  SCIP_CALL( SCIPaddConflictLb(scip, vbdvar, bdchgidx) );
537  }
538  }
539 
540  break;
541 
542  case PROPRULE_2:
543  /* lhs <= x + c*y: left hand side and upper bound on x -> bound on y */
544  assert(infervar == vbdvar);
545  assert(SCIPvarGetType(vbdvar) != SCIP_VARTYPE_CONTINUOUS);
546  assert(!SCIPisInfinity(scip, -consdata->lhs));
547 
548  if( usebdwidening )
549  {
550  SCIP_Real relaxedub;
551 
552  /* compute the relaxed upper bound of the variable which would be sufficient to reach one less (greater) than the
553  * inference bound
554  */
555  if( vbdcoef > 0.0 )
556  {
557  relaxedub = consdata->lhs - (inferbd - 1.0 + 2*SCIPfeastol(scip)) * vbdcoef;
558 
559  /* check the computed relaxed upper bound is a proper reason for the inference bound which has to be explained */
560  assert(SCIPisEQ(scip, inferbd, SCIPadjustedVarLb(scip, vbdvar, (consdata->lhs - relaxedub) / vbdcoef)));
561  }
562  else
563  {
564  relaxedub = consdata->lhs - (inferbd + 1.0 - 2*SCIPfeastol(scip)) * vbdcoef;
565 
566  /* check the computed relaxed upper bound is a proper reason for the inference bound which has to be explained */
567  assert(SCIPisEQ(scip, inferbd, SCIPadjustedVarUb(scip, vbdvar, (consdata->lhs - relaxedub) / vbdcoef)));
568  }
569 
570  /* decrease the compute relaxed upper bound by an epsilon; that ensure that we get the actual inference bound due
571  * to the integral condition of the variable bound variable
572  */
573  relaxedub -= SCIPfeastol(scip);
574 
575  SCIP_CALL( SCIPaddConflictRelaxedUb(scip, var, bdchgidx, relaxedub) );
576  }
577  else
578  {
579  SCIP_CALL( SCIPaddConflictUb(scip, var, bdchgidx) );
580  }
581 
582  break;
583 
584  case PROPRULE_3:
585  /* x + c*y <= rhs: right hand side and bounds on y -> upper bound on x */
586  assert(infervar == var);
587  assert(boundtype == SCIP_BOUNDTYPE_UPPER);
588  assert(!SCIPisInfinity(scip, consdata->rhs));
589 
590  if( usebdwidening )
591  {
592  SCIP_Real relaxedbd;
593 
594  if( SCIPvarIsIntegral(var) )
595  relaxedbd = (consdata->rhs - (inferbd + 1.0 - 2*SCIPfeastol(scip))) / vbdcoef;
596  else
597  relaxedbd = (consdata->rhs - inferbd) / vbdcoef;
598 
599  /* check the computed relaxed lower/upper bound is a proper reason for the inference bound which has to be explained */
600  assert(SCIPisEQ(scip, inferbd, SCIPadjustedVarUb(scip, var, consdata->rhs - relaxedbd * vbdcoef)));
601 
602  if( vbdcoef > 0.0 )
603  {
604  SCIP_CALL( SCIPaddConflictRelaxedLb(scip, vbdvar, bdchgidx, relaxedbd) );
605  }
606  else
607  {
608  SCIP_CALL( SCIPaddConflictRelaxedUb(scip, vbdvar, bdchgidx, relaxedbd) );
609  }
610  }
611  else
612  {
613  if( vbdcoef > 0.0 )
614  {
615  SCIP_CALL( SCIPaddConflictLb(scip, vbdvar, bdchgidx) );
616  }
617  else
618  {
619  SCIP_CALL( SCIPaddConflictUb(scip, vbdvar, bdchgidx) );
620  }
621  }
622 
623  break;
624 
625  case PROPRULE_4:
626  /* x + c*y <= rhs: right hand side and lower bound on x -> bound on y */
627  assert(infervar == vbdvar);
628  assert(SCIPvarGetType(vbdvar) != SCIP_VARTYPE_CONTINUOUS);
629  assert(!SCIPisInfinity(scip, consdata->rhs));
630 
631  if( usebdwidening )
632  {
633  SCIP_Real relaxedlb;
634 
635  /* compute the relaxed lower bound of the variable which would be sufficient to reach one greater (less) than the
636  * inference bound
637  */
638  if( vbdcoef > 0.0 )
639  {
640  relaxedlb = consdata->rhs - (inferbd + 1.0 - 2*SCIPfeastol(scip)) * vbdcoef;
641 
642  /* check the computed relaxed lower bound is a proper reason for the inference bound which has to be explained */
643  assert(SCIPisEQ(scip, inferbd, SCIPadjustedVarUb(scip, vbdvar, (consdata->rhs - relaxedlb) / vbdcoef)));
644  }
645  else
646  {
647  relaxedlb = consdata->rhs - (inferbd - 1.0 + 2*SCIPfeastol(scip)) * vbdcoef;
648 
649  /* check the computed relaxed lower bound is a proper reason for the inference bound which has to be explained */
650  assert(SCIPisEQ(scip, inferbd, SCIPadjustedVarLb(scip, vbdvar, (consdata->rhs - relaxedlb) / vbdcoef)));
651  }
652 
653  /* inccrease the compute relaxed lower bound by an epsilon; that ensure that we get the actual inference bound due
654  * to the integral condition of the variable bound variable
655  */
656  relaxedlb += SCIPfeastol(scip);
657 
658  SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, relaxedlb) );
659  }
660  else
661  {
662  SCIP_CALL( SCIPaddConflictLb(scip, var, bdchgidx) );
663  }
664 
665  break;
666 
667  default:
668  SCIPerrorMessage("invalid inference information %d in variable bound constraint <%s>\n", proprule, SCIPconsGetName(cons));
669  return SCIP_INVALIDDATA;
670  }
671 
672  return SCIP_OKAY;
673 }
674 
675 /** analyze infeasibility */
676 static
677 SCIP_RETCODE analyzeConflict(
678  SCIP* scip, /**< SCIP data structure */
679  SCIP_CONS* cons, /**< variable bound constraint */
680  SCIP_VAR* infervar, /**< variable that was deduced */
681  SCIP_Real inferbd, /**< bound which led to infeasibility */
682  PROPRULE proprule, /**< propagation rule that deduced the bound change */
683  SCIP_BOUNDTYPE boundtype, /**< the type of the changed bound (lower or upper bound) */
684  SCIP_Bool usebdwidening /**< should bound widening be used to in conflict analysis? */
685  )
686 {
687  /* conflict analysis can only be applied in solving stage and if it is applicable */
688  if( (SCIPgetStage(scip) != SCIP_STAGE_SOLVING && !SCIPinProbing(scip)) || !SCIPisConflictAnalysisApplicable(scip) )
689  return SCIP_OKAY;
690 
691  /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
692  SCIP_CALL( SCIPinitConflictAnalysis(scip) );
693 
694  /* add the bound which got violated */
695  if( boundtype == SCIP_BOUNDTYPE_LOWER )
696  {
697  if( usebdwidening )
698  {
699  SCIP_Real relaxedub;
700 
701  /* adjust lower bound */
702  inferbd = SCIPadjustedVarLb(scip, infervar, inferbd);
703 
704  /* compute a relaxed upper bound which would be sufficient to be still infeasible */
705  if( SCIPvarIsIntegral(infervar) )
706  relaxedub = inferbd - 1.0;
707  else
708  {
709  SCIP_CONSDATA* consdata;
710  SCIP_Real abscoef;
711 
712  consdata = SCIPconsGetData(cons);
713  assert(consdata != NULL);
714 
715  /* vbdvar can never be of non-integral type */
716  assert(infervar == consdata->var);
717 
718  abscoef = REALABS(consdata->vbdcoef);
719 
720  /* due to resolving a the propagation and dividing by the vbdcoef we need to make sure the the relaxed bound
721  * is big enough, therefore we multiply here with the vbdcoef
722  *
723  * @note it does not matter if we deceed the current local upper bound, because SCIPaddConflictRelaxedUb()
724  * is correcting the bound afterwards
725  */
726  relaxedub = inferbd - 2*SCIPfeastol(scip) * MAX(1, abscoef);
727  }
728 
729  /* try to relax inference variable upper bound such that the infeasibility is still given */
730  SCIP_CALL( SCIPaddConflictRelaxedUb(scip, infervar, NULL, relaxedub) );
731 
732  /* collect the upper bound which is reported to the conflict analysis */
733  inferbd = SCIPgetConflictVarUb(scip, infervar);
734 
735  /* adjust inference bound with respect to the upper bound reported to the conflict analysis */
736  if( SCIPvarIsIntegral(infervar) )
737  inferbd = inferbd + 1.0;
738  else
739  {
740  SCIP_CONSDATA* consdata;
741  SCIP_Real abscoef;
742 
743  consdata = SCIPconsGetData(cons);
744  assert(consdata != NULL);
745 
746  /* vbdvar can never be of non-integral type */
747  assert(infervar == consdata->var);
748 
749  abscoef = REALABS(consdata->vbdcoef);
750 
751  /* due to resolving a the propagation and dividing by the vbdcoef we need to make sure the the relaxed bound
752  * is big enough, therefore we multiply here with the vbdcoef
753  */
754  inferbd = inferbd + 2*SCIPfeastol(scip) * MAX(1, abscoef);
755  }
756  }
757  else
758  {
759  SCIP_CALL( SCIPaddConflictUb(scip, infervar, NULL) );
760  }
761  }
762  else
763  {
764  if( usebdwidening )
765  {
766  SCIP_Real relaxedlb;
767 
768  assert(boundtype == SCIP_BOUNDTYPE_UPPER);
769 
770  /* adjust upper bound */
771  inferbd = SCIPadjustedVarUb(scip, infervar, inferbd);
772 
773  /* compute a relaxed lower bound which would be sufficient to be still infeasible */
774  if( SCIPvarIsIntegral(infervar) )
775  relaxedlb = inferbd + 1.0;
776  else
777  {
778  SCIP_CONSDATA* consdata;
779  SCIP_Real abscoef;
780 
781  consdata = SCIPconsGetData(cons);
782  assert(consdata != NULL);
783 
784  /* vbdvar can never be of non-integral type */
785  assert(infervar == consdata->var);
786 
787  abscoef = REALABS(consdata->vbdcoef);
788 
789  /* due to resolving a the propagation and dividing by the vbdcoef we need to make sure the the relaxed bound
790  * is big enough, therefore we multiply here with the vbdcoef
791  *
792  * @note it does not matter if we exceed the current local lower bound, because SCIPaddConflictRelaxedLb()
793  * is correcting the bound afterwards
794  */
795  relaxedlb = inferbd + 2*SCIPfeastol(scip) * MAX(1, abscoef);
796  }
797 
798  /* try to relax inference variable upper bound such that the infeasibility is still given */
799  SCIP_CALL( SCIPaddConflictRelaxedLb(scip, infervar, NULL, relaxedlb) );
800 
801  /* collect the lower bound which is reported to the conflict analysis */
802  inferbd = SCIPgetConflictVarLb(scip, infervar);
803 
804  /* adjust inference bound with respect to the lower bound reported to the conflict analysis */
805  if( SCIPvarIsIntegral(infervar) )
806  inferbd = inferbd - 1.0;
807  else
808  {
809  SCIP_CONSDATA* consdata;
810  SCIP_Real abscoef;
811 
812  consdata = SCIPconsGetData(cons);
813  assert(consdata != NULL);
814 
815  /* vbdvar can never be of non-integral type */
816  assert(infervar == consdata->var);
817 
818  abscoef = REALABS(consdata->vbdcoef);
819 
820  /* due to resolving a the propagation and dividing by the vbdcoef we need to make sure the the relaxed bound
821  * is big enough, therefore we multiply here with the vbdcoef
822  */
823  inferbd = inferbd - 2*SCIPfeastol(scip) * MAX(1, abscoef);
824  }
825  }
826  else
827  {
828  SCIP_CALL( SCIPaddConflictLb(scip, infervar, NULL) );
829  }
830  }
831 
832  /* add the reason for the violated of the bound */
833  SCIP_CALL( resolvePropagation(scip, cons, infervar, proprule, boundtype, NULL, inferbd, usebdwidening) );
834 
835  /* analyze the conflict */
836  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
837 
838  return SCIP_OKAY;
839 }
840 
841 /** separates the given variable bound constraint */
842 static
843 SCIP_RETCODE separateCons(
844  SCIP* scip, /**< SCIP data structure */
845  SCIP_CONS* cons, /**< variable bound constraint */
846  SCIP_Bool usebdwidening, /**< should bound widening be used to in conflict analysis? */
847  SCIP_SOL* sol, /**< primal CIP solution, NULL for current LP solution */
848  SCIP_RESULT* result /**< pointer to store the result of the separation call */
849  )
850 {
851  SCIP_CONSHDLR* conshdlr;
852  SCIP_CONSDATA* consdata;
853  SCIP_VAR* vbdvar;
854  SCIP_VAR* var;
855  SCIP_Real vbdcoef;
856  SCIP_Real feasibility;
857 
858  assert(cons != NULL);
859  assert(result != NULL);
860 
861  consdata = SCIPconsGetData(cons);
862  assert(consdata != NULL);
863 
864  /* find the variable bound constraint handler */
865  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
866  if( conshdlr == NULL )
867  {
868  SCIPerrorMessage("variable bound constraint handler not found\n");
869  return SCIP_PLUGINNOTFOUND;
870  }
871 
872  SCIPdebugMessage("separating variable bound constraint <%s>\n", SCIPconsGetName(cons));
873 
874  var = consdata->var;
875  vbdvar = consdata->vbdvar;
876  vbdcoef = consdata->vbdcoef;
877  assert(SCIPvarGetType(vbdvar) != SCIP_VARTYPE_CONTINUOUS);
878 
879  if( SCIPvarGetLbLocal(vbdvar) + 0.5 > SCIPvarGetUbLocal(vbdvar) )
880  {
881  assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(vbdvar), SCIPvarGetUbLocal(vbdvar)));
882 
883  if( !SCIPisInfinity(scip, -consdata->lhs) )
884  {
885  SCIP_Real newlb;
886  SCIP_Bool cutoff;
887  SCIP_Bool tightened;
888 
889  newlb = consdata->lhs - vbdcoef * SCIPvarGetLbLocal(vbdvar);
890 
891  SCIP_CALL( SCIPinferVarLbCons(scip, var, newlb, cons, (int)PROPRULE_1, TRUE,
892  &cutoff, &tightened) );
893 
894  if( cutoff )
895  {
896  assert(SCIPisGT(scip, newlb, SCIPvarGetUbLocal(var)));
897 
898  /* analyze infeasibility */
899  SCIP_CALL( analyzeConflict(scip, cons, var, newlb, PROPRULE_1, SCIP_BOUNDTYPE_LOWER, usebdwidening) );
900  *result = SCIP_CUTOFF;
901 
902  return SCIP_OKAY;
903  }
904  else if( tightened )
905  {
906  *result = SCIP_REDUCEDDOM;
907  }
908  }
909 
910  if( !SCIPisInfinity(scip, consdata->rhs) )
911  {
912  SCIP_Real newub;
913  SCIP_Bool cutoff;
914  SCIP_Bool tightened;
915 
916  newub = consdata->rhs - vbdcoef * SCIPvarGetLbLocal(vbdvar);
917 
918  SCIP_CALL( SCIPinferVarUbCons(scip, var, newub, cons, (int)PROPRULE_3, TRUE,
919  &cutoff, &tightened) );
920 
921  if( cutoff )
922  {
923  assert(SCIPisLT(scip, newub, SCIPvarGetLbLocal(var)));
924 
925  /* analyze infeasibility */
926  SCIP_CALL( analyzeConflict(scip, cons, var, newub, PROPRULE_3, SCIP_BOUNDTYPE_UPPER, usebdwidening) );
927  *result = SCIP_CUTOFF;
928 
929  return SCIP_OKAY;
930  }
931  else if( tightened )
932  {
933  *result = SCIP_REDUCEDDOM;
934  }
935  }
936  }
937 
938  /* if we already changed a bound or the coefficient is too large to put the row into the LP, stop here */
939  if( *result == SCIP_REDUCEDDOM )
940  return SCIP_OKAY;
941 
942  /* check constraint for feasibility and create row if constraint is violated */
943  if( !checkCons(scip, cons, sol, (sol != NULL)) )
944  {
945  /* create LP relaxation if not yet existing */
946  if( consdata->row == NULL )
947  {
948  SCIP_CALL( createRelaxation(scip, cons) );
949  }
950  assert(consdata->row != NULL);
951 
952  /* check non-LP rows for feasibility and add them as cut, if violated */
953  if( !SCIProwIsInLP(consdata->row) )
954  {
955  feasibility = SCIPgetRowSolFeasibility(scip, consdata->row, sol);
956  if( SCIPisFeasNegative(scip, feasibility) )
957  {
958  SCIP_Bool infeasible;
959 
960  SCIP_CALL( SCIPaddCut(scip, sol, consdata->row, FALSE, &infeasible) );
961  if ( infeasible )
962  *result = SCIP_CUTOFF;
963  else
964  *result = SCIP_SEPARATED;
965  }
966  }
967  }
968 
969  return SCIP_OKAY;
970 }
971 
972 /** sets left hand side of varbound constraint */
973 static
974 SCIP_RETCODE chgLhs(
975  SCIP* scip, /**< SCIP data structure */
976  SCIP_CONS* cons, /**< linear constraint */
977  SCIP_Real lhs /**< new left hand side */
978  )
979 {
980  SCIP_CONSDATA* consdata;
981 
982  assert(scip != NULL);
983  assert(cons != NULL);
984  assert(!SCIPisInfinity(scip, lhs));
985 
986  /* adjust value to not be smaller than -inf */
987  if( SCIPisInfinity(scip, -lhs) )
988  lhs = -SCIPinfinity(scip);
989 
990  consdata = SCIPconsGetData(cons);
991  assert(consdata != NULL);
992  assert(consdata->var != NULL && consdata->vbdvar != NULL);
993  assert(!SCIPisInfinity(scip, consdata->lhs));
994 
995  /* check whether the side is not changed */
996  if( SCIPisEQ(scip, consdata->lhs, lhs) )
997  return SCIP_OKAY;
998 
999  assert(consdata->row == NULL);
1000 
1001  /* ensure that rhs >= lhs is satisfied without numerical tolerance */
1002  if( SCIPisEQ(scip, lhs, consdata->rhs) )
1003  consdata->rhs = lhs;
1004 
1005  /* if necessary, update the rounding locks of variables */
1006  if( SCIPconsIsLocked(cons) )
1007  {
1008  assert(SCIPconsIsTransformed(cons));
1009 
1010  /* the left hand side switched from -infinity to a non-infinite value -> install rounding locks */
1011  if( SCIPisInfinity(scip, -consdata->lhs) && !SCIPisInfinity(scip, -lhs) )
1012  {
1013  SCIP_CALL( SCIPlockVarCons(scip, consdata->var, cons, TRUE, FALSE) );
1014 
1015  if( SCIPisPositive(scip, consdata->vbdcoef) )
1016  {
1017  SCIP_CALL( SCIPlockVarCons(scip, consdata->vbdvar, cons, TRUE, FALSE) );
1018  }
1019  else
1020  {
1021  SCIP_CALL( SCIPlockVarCons(scip, consdata->vbdvar, cons, FALSE, TRUE) );
1022  }
1023  }
1024  /* the left hand side switched from a non-infinite value to -infinity -> remove rounding locks */
1025  else if( !SCIPisInfinity(scip, -consdata->lhs) && SCIPisInfinity(scip, -lhs) )
1026  {
1027  SCIP_CALL( SCIPunlockVarCons(scip, consdata->var, cons, TRUE, FALSE) );
1028  if( SCIPisPositive(scip, consdata->vbdcoef) )
1029  {
1030  SCIP_CALL( SCIPunlockVarCons(scip, consdata->vbdvar, cons, TRUE, FALSE) );
1031  }
1032  else
1033  {
1034  SCIP_CALL( SCIPunlockVarCons(scip, consdata->vbdvar, cons, FALSE, TRUE) );
1035  }
1036  }
1037  }
1038 
1039  /* if left hand side got tighter, we want to do additional presolving on this constraint */
1040  if( SCIPisLT(scip, consdata->lhs, lhs) )
1041  {
1042  consdata->propagated = FALSE;
1043  consdata->varboundsadded = FALSE;
1044  consdata->tightened = FALSE;
1045  }
1046 
1047  consdata->presolved = FALSE;
1048  consdata->lhs = lhs;
1049  consdata->changed = TRUE;
1050 
1051  return SCIP_OKAY;
1052 }
1053 
1054 /** sets right hand side of varbound constraint */
1055 static
1056 SCIP_RETCODE chgRhs(
1057  SCIP* scip, /**< SCIP data structure */
1058  SCIP_CONS* cons, /**< linear constraint */
1059  SCIP_Real rhs /**< new right hand side */
1060  )
1061 {
1062  SCIP_CONSDATA* consdata;
1063 
1064  assert(scip != NULL);
1065  assert(cons != NULL);
1066  assert(!SCIPisInfinity(scip, -rhs));
1067 
1068  /* adjust value to not be larger than inf */
1069  if( SCIPisInfinity(scip, rhs) )
1070  rhs = SCIPinfinity(scip);
1071 
1072  consdata = SCIPconsGetData(cons);
1073  assert(consdata != NULL);
1074  assert(consdata->var != NULL && consdata->vbdvar != NULL);
1075  assert(!SCIPisInfinity(scip, -consdata->rhs));
1076 
1077  /* check whether the side is not changed */
1078  if( SCIPisEQ(scip, consdata->rhs, rhs) )
1079  return SCIP_OKAY;
1080 
1081  assert(consdata->row == NULL);
1082 
1083  /* ensure that rhs >= lhs is satisfied without numerical tolerance */
1084  if( SCIPisEQ(scip, rhs, consdata->lhs) )
1085  consdata->lhs = rhs;
1086 
1087  /* if necessary, update the rounding locks of variables */
1088  if( SCIPconsIsLocked(cons) )
1089  {
1090  assert(SCIPconsIsTransformed(cons));
1091 
1092  /* the right hand side switched from infinity to a non-infinite value -> install rounding locks */
1093  if( SCIPisInfinity(scip, consdata->rhs) && !SCIPisInfinity(scip, rhs) )
1094  {
1095  SCIP_CALL( SCIPlockVarCons(scip, consdata->var, cons, FALSE, TRUE) );
1096 
1097  if( SCIPisPositive(scip, consdata->vbdcoef) )
1098  {
1099  SCIP_CALL( SCIPlockVarCons(scip, consdata->vbdvar, cons, FALSE, TRUE) );
1100  }
1101  else
1102  {
1103  SCIP_CALL( SCIPlockVarCons(scip, consdata->vbdvar, cons, TRUE, FALSE) );
1104  }
1105  }
1106  /* the right hand side switched from a non-infinite value to infinity -> remove rounding locks */
1107  else if( !SCIPisInfinity(scip, consdata->rhs) && SCIPisInfinity(scip, rhs) )
1108  {
1109  SCIP_CALL( SCIPunlockVarCons(scip, consdata->var, cons, FALSE, TRUE) );
1110  if( SCIPisPositive(scip, consdata->vbdcoef) )
1111  {
1112  SCIP_CALL( SCIPunlockVarCons(scip, consdata->vbdvar, cons, FALSE, TRUE) );
1113  }
1114  else
1115  {
1116  SCIP_CALL( SCIPunlockVarCons(scip, consdata->vbdvar, cons, TRUE, FALSE) );
1117  }
1118  }
1119  }
1120 
1121  /* if right hand side got tighter, we want to do additional presolving on this constraint */
1122  if( SCIPisGT(scip, consdata->rhs, rhs) )
1123  {
1124  consdata->propagated = FALSE;
1125  consdata->varboundsadded = FALSE;
1126  consdata->tightened = FALSE;
1127  }
1128 
1129  consdata->presolved = FALSE;
1130  consdata->rhs = rhs;
1131  consdata->changed = TRUE;
1132 
1133  return SCIP_OKAY;
1134 }
1135 
1136 /** propagation method for variable bound constraint */
1137 static
1138 SCIP_RETCODE propagateCons(
1139  SCIP* scip, /**< SCIP data structure */
1140  SCIP_CONS* cons, /**< variable bound constraint */
1141  SCIP_Bool usebdwidening, /**< should bound widening be used to in conflict analysis? */
1142  SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
1143  int* nchgbds, /**< pointer to count number of bound changes */
1144  int* nchgsides, /**< pointer to count number of side changes */
1145  int* ndelconss /**< pointer to count number of deleted constraints, or NULL */
1146  )
1147 {
1148  SCIP_CONSDATA* consdata;
1149  SCIP_Real xlb;
1150  SCIP_Real xub;
1151  SCIP_Real ylb;
1152  SCIP_Real yub;
1153  SCIP_Real newlb;
1154  SCIP_Real newub;
1155  SCIP_Bool tightened;
1156  SCIP_Bool tightenedround;
1157 
1158  assert(cutoff != NULL);
1159  assert(nchgbds != NULL);
1160 
1161  consdata = SCIPconsGetData(cons);
1162  assert(consdata != NULL);
1163 
1164  SCIPdebugMessage("propagating variable bound constraint <%s>: %.15g <= <%s>[%.9g, %.9g] + %.15g<%s>[%.9g, %.9g] <= %.15g\n",
1165  SCIPconsGetName(cons), consdata->lhs, SCIPvarGetName(consdata->var), SCIPvarGetLbLocal(consdata->var),
1166  SCIPvarGetUbLocal(consdata->var), consdata->vbdcoef, SCIPvarGetName(consdata->vbdvar),
1167  SCIPvarGetLbLocal(consdata->vbdvar), SCIPvarGetUbLocal(consdata->vbdvar), consdata->rhs);
1168 
1169  *cutoff = FALSE;
1170 
1171  /* increase age of constraint; age is reset to zero, if a conflict or a propagation was found */
1172  if( !SCIPinRepropagation(scip) )
1173  {
1174  SCIP_CALL( SCIPincConsAge(scip, cons) );
1175  }
1176 
1177  /* check, if constraint is already propagated */
1178  if( consdata->propagated )
1179  return SCIP_OKAY;
1180 
1181  /* get current bounds of variables */
1182  xlb = SCIPvarGetLbLocal(consdata->var);
1183  xub = SCIPvarGetUbLocal(consdata->var);
1184  ylb = SCIPvarGetLbLocal(consdata->vbdvar);
1185  yub = SCIPvarGetUbLocal(consdata->vbdvar);
1186 
1187  /* tighten bounds of variables as long as possible */
1188  do
1189  {
1190  tightenedround = FALSE;
1191 
1192  /* propagate left hand side inequality: lhs <= x + c*y */
1193  if( !SCIPisInfinity(scip, -consdata->lhs) )
1194  {
1195  assert(!(*cutoff));
1196 
1197  /* propagate bounds on x:
1198  * (1) left hand side and bounds on y -> lower bound on x
1199  */
1200  if( SCIPvarGetStatus(consdata->var) != SCIP_VARSTATUS_MULTAGGR ) /* cannot change bounds of multaggr vars */
1201  {
1202  if( consdata->vbdcoef > 0.0 )
1203  {
1204  if( !SCIPisInfinity(scip, yub) )
1205  newlb = SCIPadjustedVarLb(scip, consdata->var, consdata->lhs - consdata->vbdcoef * yub);
1206  else
1207  newlb = -SCIPinfinity(scip);
1208  }
1209  else
1210  {
1211  if( !SCIPisInfinity(scip, -ylb) )
1212  newlb = SCIPadjustedVarLb(scip, consdata->var, consdata->lhs - consdata->vbdcoef * ylb);
1213  else
1214  newlb = -SCIPinfinity(scip);
1215  }
1216 
1217  SCIP_CALL( SCIPinferVarLbCons(scip, consdata->var, newlb, cons, (int)PROPRULE_1, yub < ylb + 0.5, cutoff, &tightened) );
1218 
1219  if( *cutoff )
1220  {
1221  SCIPdebugMessage("cutoff while tightening <%s>[%.15g,%.15g] -> [%.15g,%.15g]\n", SCIPvarGetName(consdata->var), xlb, xub, newlb, xub);
1222  assert( SCIPisInfinity(scip, newlb) || SCIPisGT(scip, newlb, SCIPvarGetUbLocal(consdata->var)) );
1223 
1224  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1225 
1226  /* analyze infeasibility */
1227  SCIP_CALL( analyzeConflict(scip, cons, consdata->var, newlb, PROPRULE_1, SCIP_BOUNDTYPE_LOWER, usebdwidening) );
1228  break;
1229  }
1230 
1231  if( tightened )
1232  {
1233  SCIPdebugMessage(" -> tighten <%s>[%.15g,%.15g] -> [%.15g,%.15g]\n", SCIPvarGetName(consdata->var), xlb, xub, newlb, xub);
1234  tightenedround = TRUE;
1235  (*nchgbds)++;
1236  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1237  }
1238  xlb = SCIPvarGetLbLocal(consdata->var);
1239  }
1240 
1241  assert(!*cutoff);
1242 
1243  /* propagate bounds on y:
1244  * (2) left hand side and upper bound on x -> bound on y
1245  */
1246  if( SCIPvarGetStatus(consdata->vbdvar) != SCIP_VARSTATUS_MULTAGGR && !SCIPisInfinity(scip, xub) ) /* cannot change bounds of multaggr vars */
1247  {
1248  if( consdata->vbdcoef > 0.0 )
1249  {
1250  newlb = SCIPadjustedVarLb(scip, consdata->vbdvar, (consdata->lhs - xub)/consdata->vbdcoef);
1251  if( newlb > ylb + 0.5 )
1252  {
1253  SCIP_CALL( SCIPinferVarLbCons(scip, consdata->vbdvar, newlb, cons, (int)PROPRULE_2, FALSE, cutoff, &tightened) );
1254 
1255  if( *cutoff )
1256  {
1257  SCIPdebugMessage("cutoff while tightening <%s>[%.15g,%.15g] -> [%.15g,%.15g]\n", SCIPvarGetName(consdata->vbdvar), ylb, yub, newlb, yub);
1258  assert( SCIPisInfinity(scip, newlb) || SCIPisGT(scip, newlb, SCIPvarGetUbLocal(consdata->vbdvar)) );
1259 
1260  /* analyze infeasibility */
1261  SCIP_CALL( analyzeConflict(scip, cons, consdata->vbdvar, newlb, PROPRULE_2, SCIP_BOUNDTYPE_LOWER, usebdwidening) );
1262  break;
1263  }
1264 
1265  if( tightened )
1266  {
1267  SCIPdebugMessage(" -> tighten <%s>[%.15g,%.15g] -> [%.15g,%.15g]\n", SCIPvarGetName(consdata->vbdvar), ylb, yub, newlb, yub);
1268  tightenedround = TRUE;
1269  (*nchgbds)++;
1270  }
1271  ylb = SCIPvarGetLbLocal(consdata->vbdvar);
1272  }
1273  }
1274  else
1275  {
1276  newub = SCIPadjustedVarUb(scip, consdata->vbdvar, (consdata->lhs - xub)/consdata->vbdcoef);
1277  if( newub < yub - 0.5 )
1278  {
1279  SCIP_CALL( SCIPinferVarUbCons(scip, consdata->vbdvar, newub, cons, (int)PROPRULE_2, FALSE, cutoff, &tightened) );
1280 
1281  if( *cutoff )
1282  {
1283  SCIPdebugMessage("cutoff while tightening <%s>[%.15g,%.15g] -> [%.15g,%.15g]\n", SCIPvarGetName(consdata->vbdvar), ylb, yub, ylb, newub);
1284  assert( SCIPisInfinity(scip, -newub) || SCIPisLT(scip, newub, SCIPvarGetLbLocal(consdata->vbdvar)) );
1285 
1286  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1287 
1288  /* analyze infeasibility */
1289  SCIP_CALL( analyzeConflict(scip, cons, consdata->vbdvar, newub, PROPRULE_2, SCIP_BOUNDTYPE_UPPER, usebdwidening) );
1290  break;
1291  }
1292 
1293  if( tightened )
1294  {
1295  SCIPdebugMessage(" -> tighten <%s>[%.15g,%.15g] -> [%.15g,%.15g]\n", SCIPvarGetName(consdata->vbdvar), ylb, yub, ylb, newub);
1296  tightenedround = TRUE;
1297  (*nchgbds)++;
1298  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1299  }
1300  yub = SCIPvarGetUbLocal(consdata->vbdvar);
1301  }
1302  }
1303  }
1304  }
1305 
1306  assert(!*cutoff);
1307 
1308  /* propagate right hand side inequality: x + c*y <= rhs */
1309  if( !SCIPisInfinity(scip, consdata->rhs) )
1310  {
1311  /* propagate bounds on x:
1312  * (3) right hand side and bounds on y -> upper bound on x
1313  */
1314  if( SCIPvarGetStatus(consdata->var) != SCIP_VARSTATUS_MULTAGGR ) /* cannot change bounds of multaggr vars */
1315  {
1316  if( consdata->vbdcoef > 0.0 )
1317  {
1318  if( !SCIPisInfinity(scip, -ylb) )
1319  newub = SCIPadjustedVarUb(scip, consdata->var, consdata->rhs - consdata->vbdcoef * ylb);
1320  else
1321  newub = SCIPinfinity(scip);
1322  }
1323  else
1324  {
1325  if( !SCIPisInfinity(scip, yub) )
1326  newub = SCIPadjustedVarUb(scip, consdata->var, consdata->rhs - consdata->vbdcoef * yub);
1327  else
1328  newub = SCIPinfinity(scip);
1329  }
1330 
1331  SCIP_CALL( SCIPinferVarUbCons(scip, consdata->var, newub, cons, (int)PROPRULE_3, yub < ylb + 0.5, cutoff, &tightened) );
1332 
1333  if( *cutoff )
1334  {
1335  SCIPdebugMessage("cutoff while tightening <%s>[%.15g,%.15g] -> [%.15g,%.15g]\n", SCIPvarGetName(consdata->var), xlb, xub, xlb, newub);
1336  assert( SCIPisInfinity(scip, -newub) || SCIPisLT(scip, newub, SCIPvarGetLbLocal(consdata->var)) );
1337 
1338  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1339 
1340  /* analyze infeasibility */
1341  SCIP_CALL( analyzeConflict(scip, cons, consdata->var, newub, PROPRULE_3, SCIP_BOUNDTYPE_UPPER, usebdwidening) );
1342  break;
1343  }
1344 
1345  if( tightened )
1346  {
1347  SCIPdebugMessage(" -> tighten <%s>[%.15g,%.15g] -> [%.15g,%.15g]\n", SCIPvarGetName(consdata->var), xlb, xub, xlb, newub);
1348  tightenedround = TRUE;
1349  (*nchgbds)++;
1350  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1351  }
1352  xub = SCIPvarGetUbLocal(consdata->var);
1353  }
1354 
1355  assert(!*cutoff);
1356 
1357  /* propagate bounds on y:
1358  * (4) right hand side and lower bound on x -> bound on y
1359  */
1360  if( SCIPvarGetStatus(consdata->vbdvar) != SCIP_VARSTATUS_MULTAGGR && !SCIPisInfinity(scip, -xlb) ) /* cannot change bounds of multaggr vars */
1361  {
1362  if( consdata->vbdcoef > 0.0 )
1363  {
1364  newub = SCIPadjustedVarUb(scip, consdata->vbdvar, (consdata->rhs - xlb)/consdata->vbdcoef);
1365  if( newub < yub - 0.5 )
1366  {
1367  SCIP_CALL( SCIPinferVarUbCons(scip, consdata->vbdvar, newub, cons, (int)PROPRULE_4, FALSE, cutoff, &tightened) );
1368 
1369  if( *cutoff )
1370  {
1371  SCIPdebugMessage("cutoff while tightening <%s>[%.15g,%.15g] -> [%.15g,%.15g]\n", SCIPvarGetName(consdata->vbdvar), ylb, yub, ylb, newub);
1372  assert(SCIPisLT(scip, newub, SCIPvarGetLbLocal(consdata->vbdvar)));
1373 
1374  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1375 
1376  /* analyze infeasibility */
1377  SCIP_CALL( analyzeConflict(scip, cons, consdata->vbdvar, newub, PROPRULE_4, SCIP_BOUNDTYPE_UPPER, usebdwidening) );
1378  break;
1379  }
1380 
1381  if( tightened )
1382  {
1383  SCIPdebugMessage(" -> tighten <%s>[%.15g,%.15g] -> [%.15g,%.15g]\n", SCIPvarGetName(consdata->vbdvar), ylb, yub, ylb, newub);
1384  tightenedround = TRUE;
1385  (*nchgbds)++;
1386  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1387  }
1388  yub = SCIPvarGetUbLocal(consdata->vbdvar);
1389  }
1390  }
1391  else
1392  {
1393  newlb = SCIPadjustedVarLb(scip, consdata->vbdvar, (consdata->rhs - xlb)/consdata->vbdcoef);
1394  if( newlb > ylb + 0.5 )
1395  {
1396  SCIP_CALL( SCIPinferVarLbCons(scip, consdata->vbdvar, newlb, cons, (int)PROPRULE_4, FALSE, cutoff, &tightened) );
1397 
1398  if( *cutoff )
1399  {
1400  SCIPdebugMessage("cutoff while tightening <%s>[%.15g,%.15g] -> [%.15g,%.15g]\n", SCIPvarGetName(consdata->vbdvar), ylb, yub, newlb, yub);
1401  assert(SCIPisGT(scip, newlb, SCIPvarGetUbLocal(consdata->vbdvar)));
1402 
1403  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1404 
1405  /* analyze infeasibility */
1406  SCIP_CALL( analyzeConflict(scip, cons, consdata->vbdvar, newlb, PROPRULE_4, SCIP_BOUNDTYPE_LOWER, usebdwidening) );
1407  break;
1408  }
1409 
1410  if( tightened )
1411  {
1412  SCIPdebugMessage(" -> tighten <%s>[%.15g,%.15g] -> [%.15g,%.15g]\n", SCIPvarGetName(consdata->vbdvar), ylb, yub, newlb, yub);
1413  tightenedround = TRUE;
1414  (*nchgbds)++;
1415  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1416  }
1417  ylb = SCIPvarGetLbLocal(consdata->vbdvar);
1418  }
1419  }
1420  }
1421  }
1422  assert(!(*cutoff));
1423  }
1424  while( tightenedround );
1425 
1426  /* check for redundant sides */
1427  if( !(*cutoff) && SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING && !SCIPinProbing(scip) )
1428  {
1429  /* check left hand side for redundancy */
1430  if( !SCIPisInfinity(scip, -consdata->lhs) &&
1431  ((consdata->vbdcoef > 0.0 && SCIPisFeasGE(scip, xlb + consdata->vbdcoef * ylb, consdata->lhs))
1432  || (consdata->vbdcoef < 0.0 && SCIPisFeasGE(scip, xlb + consdata->vbdcoef * yub, consdata->lhs))) )
1433  {
1434  SCIPdebugMessage("left hand side of variable bound constraint <%s> is redundant\n", SCIPconsGetName(cons));
1435 
1436  SCIP_CALL( chgLhs(scip, cons, -SCIPinfinity(scip)) );
1437  ++(*nchgsides);
1438  }
1439 
1440  /* check right hand side for redundancy */
1441  if( !SCIPisInfinity(scip, consdata->rhs) &&
1442  ((consdata->vbdcoef > 0.0 && SCIPisFeasLE(scip, xub + consdata->vbdcoef * yub, consdata->rhs))
1443  || (consdata->vbdcoef < 0.0 && SCIPisFeasLE(scip, xub + consdata->vbdcoef * ylb, consdata->rhs))) )
1444  {
1445  SCIPdebugMessage("right hand side of variable bound constraint <%s> is redundant\n", SCIPconsGetName(cons));
1446 
1447  SCIP_CALL( chgRhs(scip, cons, SCIPinfinity(scip)) );
1448  ++(*nchgsides);
1449  }
1450  }
1451  /* check varbound constraint for redundancy */
1452  if( !(*cutoff) && (SCIPisInfinity(scip, -consdata->lhs)
1453  || (consdata->vbdcoef > 0.0 && SCIPisFeasGE(scip, xlb + consdata->vbdcoef * ylb, consdata->lhs))
1454  || (consdata->vbdcoef < 0.0 && SCIPisFeasGE(scip, xlb + consdata->vbdcoef * yub, consdata->lhs)))
1455  && (SCIPisInfinity(scip, consdata->rhs)
1456  || (consdata->vbdcoef > 0.0 && SCIPisFeasLE(scip, xub + consdata->vbdcoef * yub, consdata->rhs))
1457  || (consdata->vbdcoef < 0.0 && SCIPisFeasLE(scip, xub + consdata->vbdcoef * ylb, consdata->rhs))) )
1458  {
1459  SCIPdebugMessage("variable bound constraint <%s> is redundant: <%s>[%.15g,%.15g], <%s>[%.15g,%.15g]\n",
1460  SCIPconsGetName(cons),
1461  SCIPvarGetName(consdata->var), SCIPvarGetLbLocal(consdata->var), SCIPvarGetUbLocal(consdata->var),
1462  SCIPvarGetName(consdata->vbdvar), SCIPvarGetLbLocal(consdata->vbdvar), SCIPvarGetUbLocal(consdata->vbdvar));
1463  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
1464 
1465  if( ndelconss != NULL )
1466  (*ndelconss)++;
1467  }
1468 
1469  /* mark the constraint propagated */
1470  consdata->propagated = TRUE;
1471 
1472  return SCIP_OKAY;
1473 }
1474 
1475 /* check whether one constraints side is redundant to another constraints side by calculating extreme values for
1476  * variables
1477  */
1478 static
1479 void checkRedundancySide(
1480  SCIP* scip, /**< SCIP data structure */
1481  SCIP_VAR* var, /**< variable x that has variable bound */
1482  SCIP_VAR* vbdvar, /**< binary, integer or implicit integer bounding variable y */
1483  SCIP_Real coef0, /**< coefficient c0 of bounding variable y for constraint 0 */
1484  SCIP_Real coef1, /**< coefficient c1 of bounding variable y for constraint 1 */
1485  SCIP_Real side0, /**< one side of variable bound inequality for constraint 0 */
1486  SCIP_Real side1, /**< one side of variable bound inequality for constraint 1 */
1487  SCIP_Bool* sideequal, /**< pointer to store if both constraints have the same redundancy on the
1488  * given side */
1489  SCIP_Bool* cons0sidered, /**< pointer to store if side of constraint 0 is redundant */
1490  SCIP_Bool* cons1sidered, /**< pointer to store if side of constraint 1 is redundant */
1491  SCIP_Bool islhs /**< do we check the left or the right hand side */
1492  )
1493 {
1494  SCIP_Real lbvar;
1495  SCIP_Real ubvar;
1496  SCIP_Real lbvbdvar;
1497  SCIP_Real ubvbdvar;
1498  SCIP_Real boundxlb1;
1499  SCIP_Real boundxlb2;
1500  SCIP_Real boundylb1;
1501  SCIP_Real boundylb2;
1502  SCIP_Real boundxub1;
1503  SCIP_Real boundxub2;
1504  SCIP_Real boundyub1;
1505  SCIP_Real boundyub2;
1506  SCIP_Real boundvaluex1;
1507  SCIP_Real boundvaluex2;
1508  SCIP_Real boundvaluey1;
1509  SCIP_Real boundvaluey2;
1510  SCIP_Real valuex1;
1511  SCIP_Real valuex2;
1512  SCIP_Real valuey1;
1513  SCIP_Real valuey2;
1514  SCIP_Bool* redundant0;
1515  SCIP_Bool* redundant1;
1516  SCIP_Real eps = SCIPepsilon(scip);
1517 
1518  assert(scip != NULL);
1519  assert(var != NULL);
1520  assert(vbdvar != NULL);
1521  assert(sideequal != NULL);
1522  assert(cons0sidered != NULL);
1523  assert(cons1sidered != NULL);
1524 
1525  *cons0sidered = SCIPisInfinity(scip, REALABS(side0));
1526  *cons1sidered = SCIPisInfinity(scip, REALABS(side1));
1527  *sideequal = FALSE;
1528 
1529  if( islhs )
1530  {
1531  redundant0 = cons1sidered;
1532  redundant1 = cons0sidered;
1533  }
1534  else
1535  {
1536  redundant0 = cons0sidered;
1537  redundant1 = cons1sidered;
1538  }
1539 
1540  lbvar = SCIPvarGetLbGlobal(var);
1541  ubvar = SCIPvarGetUbGlobal(var);
1542  lbvbdvar = SCIPvarGetLbGlobal(vbdvar);
1543  ubvbdvar = SCIPvarGetUbGlobal(vbdvar);
1544 
1545  /* if both constraint have this side */
1546  if( !*redundant0 && !*redundant1 )
1547  {
1548  /* calculate extreme values, which are reached by setting the other variable to their lower/upper bound */
1549  boundxlb1 = side0 - lbvbdvar*coef0;
1550  boundxlb2 = side1 - lbvbdvar*coef1;
1551  boundylb1 = (side0 - lbvar)/coef0;
1552  boundylb2 = (side1 - lbvar)/coef1;
1553 
1554  boundxub1 = side0 - ubvbdvar*coef0;
1555  boundxub2 = side1 - ubvbdvar*coef1;
1556  boundyub1 = (side0 - ubvar)/coef0;
1557  boundyub2 = (side1 - ubvar)/coef1;
1558 
1559  if( islhs )
1560  {
1561  boundvaluex1 = MAX(boundxlb1, boundxlb2);
1562  boundvaluex2 = MAX(boundxub1, boundxub2);
1563  }
1564  else
1565  {
1566  boundvaluex1 = MIN(boundxlb1, boundxlb2);
1567  boundvaluex2 = MIN(boundxub1, boundxub2);
1568  }
1569 
1570  /* calculate important values for variables */
1571  if( SCIPisPositive(scip, coef0) )
1572  {
1573  valuex1 = MIN(boundvaluex1, ubvar);
1574  valuex1 = MAX(valuex1, lbvar);
1575  valuex2 = MAX(boundvaluex2, lbvar);
1576  valuex2 = MIN(valuex2, ubvar);
1577 
1578  /* if variable is of integral type make values integral too */
1579  if( SCIPvarGetType(var) < SCIP_VARTYPE_CONTINUOUS )
1580  {
1581  if( !SCIPisFeasIntegral(scip, valuex1) )
1582  valuex1 = SCIPfeasFloor(scip, valuex1);
1583  if( !SCIPisFeasIntegral(scip, valuex2) )
1584  valuex2 = SCIPfeasCeil(scip, valuex2);
1585  }
1586  }
1587  else
1588  {
1589  valuex1 = MAX(boundvaluex1, lbvar);
1590  valuex1 = MIN(valuex1, ubvar);
1591  valuex2 = MIN(boundvaluex2, ubvar);
1592  valuex2 = MAX(valuex2, lbvar);
1593 
1594  /* if variable is of integral type make values integral too */
1595  if( SCIPvarGetType(var) < SCIP_VARTYPE_CONTINUOUS )
1596  {
1597  if( !SCIPisFeasIntegral(scip, valuex1) )
1598  valuex1 = SCIPfeasCeil(scip, valuex1);
1599  if( !SCIPisFeasIntegral(scip, valuex2) )
1600  valuex2 = SCIPfeasFloor(scip, valuex2);
1601  }
1602  }
1603 
1604  /* calculate resulting values of variable y by setting x to valuex1 */
1605  valuey1 = (side0 - valuex1)/coef0;
1606  valuey2 = (side1 - valuex1)/coef1;
1607 
1608  /* determine redundancy of one constraints side */
1609  if( valuey1 - valuey2 <= eps )
1610  *sideequal = TRUE;
1611  else if( SCIPisPositive(scip, coef0) )
1612  {
1613  if( valuey1 < valuey2 )
1614  *redundant1 = TRUE;
1615  else
1616  *redundant0 = TRUE;
1617  }
1618  else
1619  {
1620  if( valuey1 < valuey2 )
1621  *redundant0 = TRUE;
1622  else
1623  *redundant1 = TRUE;
1624  }
1625 
1626  /* calculate resulting values of variable y by setting x to valuex2 */
1627  valuey1 = (side0 - valuex2)/coef0;
1628  valuey2 = (side1 - valuex2)/coef1;
1629 
1630  /* determine redundancy of one constraints side by checking for the first valuex2 */
1631  if( SCIPisPositive(scip, coef0) )
1632  {
1633  /* if both constraints are weaker than the other on one value, we have no redundancy */
1634  if( (*redundant1 && valuey1 > valuey2) || (*redundant0 && valuey1 < valuey2) )
1635  {
1636  *sideequal = FALSE;
1637  *redundant0 = FALSE;
1638  *redundant1 = FALSE;
1639  return;
1640  }
1641  else if( *sideequal )
1642  {
1643  if( valuey1 + eps < valuey2 )
1644  {
1645  *sideequal = FALSE;
1646  *redundant1 = TRUE;
1647  }
1648  else if( valuey1 + eps > valuey2 )
1649  {
1650  *sideequal = FALSE;
1651  *redundant0 = TRUE;
1652  }
1653  }
1654  }
1655  else
1656  {
1657  /* if both constraints are weaker than the other one on one value, we have no redundancy */
1658  if( (*redundant1 && valuey1 < valuey2) || (*redundant0 && valuey1 > valuey2) )
1659  {
1660  *sideequal = FALSE;
1661  *redundant0 = FALSE;
1662  *redundant1 = FALSE;
1663  return;
1664  }
1665  else if( *sideequal )
1666  {
1667  if( valuey1 + eps < valuey2 )
1668  {
1669  *sideequal = FALSE;
1670  *redundant0 = TRUE;
1671  }
1672  else if( valuey1 + eps > valuey2 )
1673  {
1674  *sideequal = FALSE;
1675  *redundant1 = TRUE;
1676  }
1677  }
1678  }
1679  assert(*sideequal || *redundant0 || *redundant1);
1680 
1681  /* calculate feasibility domain values for variable y concerning these both constraints */
1682  if( SCIPisPositive(scip, coef0) )
1683  {
1684  if( islhs )
1685  {
1686  boundvaluey1 = MAX(boundylb1, boundylb2);
1687  boundvaluey2 = MAX(boundyub1, boundyub2);
1688  }
1689  else
1690  {
1691  boundvaluey1 = MIN(boundylb1, boundylb2);
1692  boundvaluey2 = MIN(boundyub1, boundyub2);
1693  }
1694 
1695  valuey1 = MIN(boundvaluey1, ubvbdvar);
1696  valuey1 = MAX(valuey1, lbvbdvar);
1697  valuey2 = MAX(boundvaluey2, lbvbdvar);
1698  valuey2 = MIN(valuey2, ubvbdvar);
1699 
1700  if( !SCIPisFeasIntegral(scip, valuey1) )
1701  valuey1 = SCIPfeasFloor(scip, valuey1);
1702  if( !SCIPisFeasIntegral(scip, valuey2) )
1703  valuey2 = SCIPfeasCeil(scip, valuey2);
1704  }
1705  else
1706  {
1707  if( islhs )
1708  {
1709  boundvaluey1 = MIN(boundylb1, boundylb2);
1710  boundvaluey2 = MIN(boundyub1, boundyub2);
1711  }
1712  else
1713  {
1714  boundvaluey1 = MAX(boundylb1, boundylb2);
1715  boundvaluey2 = MAX(boundyub1, boundyub2);
1716  }
1717 
1718  valuey1 = MAX(boundvaluey1, lbvbdvar);
1719  valuey1 = MIN(valuey1, ubvbdvar);
1720  valuey2 = MIN(boundvaluey2, ubvbdvar);
1721  valuey2 = MAX(valuey2, lbvbdvar);
1722 
1723  /* if variable is of integral type make values integral too */
1724  if( !SCIPisFeasIntegral(scip, valuey1) )
1725  valuey1 = SCIPfeasCeil(scip, valuey1);
1726  if( !SCIPisFeasIntegral(scip, valuey2) )
1727  valuey2 = SCIPfeasFloor(scip, valuey2);
1728  }
1729 
1730  /* calculate resulting values of variable x by setting y to valuey1 */
1731  valuex1 = side0 - valuey1*coef0;
1732  valuex2 = side1 - valuey1*coef1;
1733 
1734  /* determine redundancy of one constraints side by checking for the first valuey1 */
1735  if( (*redundant1 && valuex1 > valuex2) || (*redundant0 && valuex1 < valuex2) )
1736  {
1737  *sideequal = FALSE;
1738  *redundant0 = FALSE;
1739  *redundant1 = FALSE;
1740  return;
1741  }
1742  if( *sideequal )
1743  {
1744  if( valuex1 + eps < valuex2 )
1745  {
1746  *sideequal = FALSE;
1747  *redundant1 = TRUE;
1748  }
1749  else if( valuex1 + eps > valuex2 )
1750  {
1751  *sideequal = FALSE;
1752  *redundant0 = TRUE;
1753  }
1754  }
1755 
1756  /* calculate resulting values of variable x by setting y to valuey2 */
1757  valuex1 = side0 - valuey2*coef0;
1758  valuex2 = side1 - valuey2*coef1;
1759 
1760  /* determine redundancy of one constraints side by checking for the first valuey1 */
1761  if( (*redundant1 && valuex1 > valuex2) || (*redundant0 && valuex1 < valuex2) )
1762  {
1763  *sideequal = FALSE;
1764  *redundant0 = FALSE;
1765  *redundant1 = FALSE;
1766  return;
1767  }
1768  if( *sideequal )
1769  {
1770  if( valuex1 + eps < valuex2 )
1771  {
1772  *sideequal = FALSE;
1773  *redundant1 = TRUE;
1774  }
1775  else if( valuex1 + eps > valuex2 )
1776  {
1777  *sideequal = FALSE;
1778  *redundant0 = TRUE;
1779  }
1780  }
1781  assert(*redundant0 || *redundant1 || *sideequal);
1782  }
1783 }
1784 
1785 /** compares each constraint with all other constraints for possible redundancy and removes or changes constraint
1786  *
1787  * we will order all constraint to have constraints with same variables next to each other to speed up presolving
1788  *
1789  * consider two constraints like lhs1 <= x + b1*y <= rhs1 and lhs2 <= x + b2*y <= rhs2
1790  * we are doing the following presolving steps:
1791  *
1792  * if( b1 == b2 )
1793  * newlhs = MAX(lhs1, lhs2)
1794  * newrhs = MIN(rhs1, rhs2)
1795  * updateSides
1796  * delete one constraint
1797  * else if( ((b1 > 0) == (b2 > 0)) && (lhs1 != -inf && lhs2 != -inf) || (rhs1 != inf && rhs2 != inf) )
1798  *
1799  * (i.e. both constraint have either a valid lhs or a valid rhs and infinity is on the same side and the
1800  * coeffcients have the same size )
1801  *
1802  * if( y is binary )
1803  * if( lhs1 != -inf )
1804  * newlhs = MAX(lhs1, lhs2)
1805  * newb = newlhs - MAX(lhs1 - b1, lhs2 - b2)
1806  * else
1807  * newrhs = MIN(lhs1, lhs2)
1808  * newb = newrhs - MIN(rhs1 - b1, rhs2 - b2)
1809  * updateSidesAndCoef
1810  * delete one constraint
1811  * else
1812  * we calculate possible values for both variables and check which constraint is tighter
1813  * else
1814  * nothing possible
1815  *
1816  * We also try to tighten bounds in the case of two constraints lhs1 <= x + b1*y <= rhs1 and lhs2 <= y + b2*x <= rhs2.
1817  * Eliminiating one variable and inserting into the second yields the following bounds:
1818  * If b2 > 0:
1819  * (1 - b1 * b2) * y >= lhs2 - b2 * rhs1
1820  * (1 - b1 * b2) * y <= rhs2 - b2 * lhs1
1821  * If b2 < 0:
1822  * (1 - b1 * b2) * y >= lhs2 - b2 * lhs1
1823  * (1 - b1 * b2) * y <= rhs2 - b2 * rhs1
1824  * The case of x is similar.
1825  */
1826 static
1827 SCIP_RETCODE preprocessConstraintPairs(
1828  SCIP* scip, /**< SCIP data structure */
1829  SCIP_CONS** conss, /**< constraint set */
1830  int nconss, /**< number of constraints in constraint set */
1831  SCIP_Bool* cutoff, /**< pointer to store TRUE, if a cutoff was found */
1832  int* nchgbds, /**< pointer to count number of bound changes */
1833  int* ndelconss, /**< pointer to count number of deleted constraints */
1834  int* nchgcoefs, /**< pointer to count the number of changed coefficients */
1835  int* nchgsides /**< pointer to count number of changed left/right hand sides */
1836  )
1837 {
1838  SCIP_CONS** sortedconss;
1839  int c;
1840  int s;
1841 
1842  assert(scip != NULL);
1843  assert(conss != NULL);
1844  assert(cutoff != NULL);
1845  assert(nchgbds != NULL);
1846  assert(ndelconss != NULL);
1847  assert(nchgcoefs != NULL);
1848  assert(nchgsides != NULL);
1849 
1850  /* create our temporary working array */
1851  SCIP_CALL( SCIPduplicateBufferArray(scip, &sortedconss, conss, nconss) );
1852 
1853  /* sort all constraints, so that all constraints with same variables stand next to each other */
1854  SCIPsortPtr((void**)sortedconss, consVarboundComp, nconss);
1855 
1856  /* check all constraints for redundancy */
1857  for( c = nconss - 1; c > 0 && !(*cutoff); --c )
1858  {
1859  SCIP_CONS* cons0;
1860  SCIP_CONSDATA* consdata0;
1861 
1862  cons0 = sortedconss[c];
1863 
1864  if( !SCIPconsIsActive(cons0) || SCIPconsIsModifiable(cons0) )
1865  continue;
1866 
1867  consdata0 = SCIPconsGetData(cons0);
1868  assert(consdata0 != NULL);
1869  assert(consdata0->var != NULL);
1870  assert(consdata0->vbdvar != NULL);
1871 
1872  /* do not check for already redundant constraints */
1873  assert(!SCIPisZero(scip, consdata0->vbdcoef));
1874  assert(!SCIPisInfinity(scip, -consdata0->lhs) || !SCIPisInfinity(scip, consdata0->rhs));
1875 
1876  if( !consdata0->changed )
1877  continue;
1878 
1879  consdata0->changed = FALSE;
1880 
1881  for( s = c - 1; s >= 0; --s )
1882  {
1883  SCIP_CONS* cons1;
1884  SCIP_CONSDATA* consdata1;
1885  SCIP_Real lhs;
1886  SCIP_Real rhs;
1887  SCIP_Real coef;
1888  SCIP_Bool deletecons1;
1889 
1890  cons1 = sortedconss[s];
1891 
1892  if( !SCIPconsIsActive(cons1) || SCIPconsIsModifiable(cons1) )
1893  continue;
1894 
1895  consdata1 = SCIPconsGetData(cons1);
1896  assert(consdata1 != NULL);
1897  assert(consdata1->var != NULL);
1898  assert(consdata1->vbdvar != NULL);
1899 
1900  /* do not check for already redundant constraints */
1901  assert(!SCIPisZero(scip, consdata1->vbdcoef));
1902  assert(!SCIPisInfinity(scip, -consdata1->lhs) || !SCIPisInfinity(scip, consdata1->rhs));
1903 
1904  lhs = consdata0->lhs;
1905  rhs = consdata0->rhs;
1906  coef = consdata0->vbdcoef;
1907 
1908  /* check for propagation in the case: lhs1 <= x + b1*y <= rhs1 and lhs2 <= y + b2*x <= rhs2. */
1909  if ( consdata0->var == consdata1->vbdvar && consdata0->vbdvar == consdata1->var &&
1910  !SCIPisFeasZero(scip, 1.0 - coef * consdata1->vbdcoef) )
1911  {
1912  SCIP_Bool tightened = FALSE;
1913  SCIP_Real bnd = SCIP_UNKNOWN;
1914  SCIP_Real scalar;
1915  SCIP_Real newbnd;
1916 
1917  scalar = (1.0 - coef * consdata1->vbdcoef);
1918 
1919  assert( ! SCIPisInfinity(scip, REALABS(scalar)) );
1920  assert( ! SCIPisZero(scip, consdata0->vbdcoef) );
1921  assert( ! SCIPisZero(scip, consdata1->vbdcoef) );
1922 
1923  /* lower bounds for consdata0->var */
1924  if ( ! SCIPisInfinity(scip, -lhs) )
1925  {
1926  if ( SCIPisPositive(scip, coef) )
1927  {
1928  if ( ! SCIPisInfinity(scip, consdata1->rhs) )
1929  bnd = (lhs - coef * consdata1->rhs)/scalar;
1930  }
1931  else
1932  {
1933  assert( SCIPisNegative(scip, coef) );
1934  if ( ! SCIPisInfinity(scip, consdata1->lhs) )
1935  bnd = (lhs - coef * consdata1->lhs)/scalar;
1936  }
1937 
1938  if ( bnd != SCIP_UNKNOWN ) /*lint !e777*/
1939  {
1940  if ( SCIPisFeasPositive(scip, scalar) )
1941  {
1942  newbnd = SCIPadjustedVarLb(scip, consdata0->var, bnd);
1943  SCIP_CALL( SCIPtightenVarLb(scip, consdata0->var, newbnd, FALSE, cutoff, &tightened) );
1944  if ( tightened )
1945  {
1946  SCIPdebugMessage("<%s>, <%s> -> tightened lower bound: <%s> >= %.15g\n", SCIPconsGetName(cons0), SCIPconsGetName(cons1),
1947  SCIPvarGetName(consdata0->var), SCIPvarGetLbGlobal(consdata0->var));
1948  (*nchgbds)++;
1949  }
1950  }
1951  else if ( SCIPisFeasNegative(scip, scalar) )
1952  {
1953  newbnd = SCIPadjustedVarUb(scip, consdata0->var, bnd);
1954  SCIP_CALL( SCIPtightenVarUb(scip, consdata0->var, newbnd, FALSE, cutoff, &tightened) );
1955  if ( tightened )
1956  {
1957  SCIPdebugMessage("<%s>, <%s> -> tightened upper bound: <%s> >= %.15g\n", SCIPconsGetName(cons0), SCIPconsGetName(cons1),
1958  SCIPvarGetName(consdata0->var), SCIPvarGetUbGlobal(consdata0->var));
1959  (*nchgbds)++;
1960  }
1961  }
1962  }
1963  }
1964 
1965  /* upper bound for consdata0>var */
1966  if ( ! SCIPisInfinity(scip, rhs) )
1967  {
1968  bnd = SCIP_UNKNOWN;
1969  if ( SCIPisPositive(scip, coef) )
1970  {
1971  if ( ! SCIPisInfinity(scip, consdata1->lhs) )
1972  bnd = (rhs - coef * consdata1->lhs)/scalar;
1973  }
1974  else
1975  {
1976  assert( SCIPisNegative(scip, coef) );
1977  if ( ! SCIPisInfinity(scip, consdata1->rhs) )
1978  bnd = (rhs - coef * consdata1->rhs)/scalar;
1979  }
1980 
1981  if ( bnd != SCIP_UNKNOWN ) /*lint !e777*/
1982  {
1983  if ( SCIPisFeasPositive(scip, scalar) )
1984  {
1985  newbnd = SCIPadjustedVarUb(scip, consdata0->var, bnd);
1986  SCIP_CALL( SCIPtightenVarUb(scip, consdata0->var, newbnd, FALSE, cutoff, &tightened) );
1987  if ( tightened )
1988  {
1989  SCIPdebugMessage("<%s>, <%s> -> tightened upper bound: <%s> >= %.15g\n", SCIPconsGetName(cons0), SCIPconsGetName(cons1),
1990  SCIPvarGetName(consdata0->var), SCIPvarGetUbGlobal(consdata0->var));
1991  (*nchgbds)++;
1992  }
1993  }
1994  else if ( SCIPisFeasNegative(scip, scalar) )
1995  {
1996  newbnd = SCIPadjustedVarLb(scip, consdata0->var, bnd);
1997  SCIP_CALL( SCIPtightenVarLb(scip, consdata0->var, newbnd, FALSE, cutoff, &tightened) );
1998  if ( tightened )
1999  {
2000  SCIPdebugMessage("<%s>, <%s> -> tightened lower bound: <%s> >= %.15g\n", SCIPconsGetName(cons0), SCIPconsGetName(cons1),
2001  SCIPvarGetName(consdata0->var), SCIPvarGetLbGlobal(consdata0->var));
2002  (*nchgbds)++;
2003  }
2004  }
2005  }
2006  }
2007 
2008 
2009  /* lower bounds for consdata1->var */
2010  if ( ! SCIPisInfinity(scip, -consdata1->lhs) )
2011  {
2012  bnd = SCIP_UNKNOWN;
2013  if ( SCIPisPositive(scip, consdata1->vbdcoef) )
2014  {
2015  if ( ! SCIPisInfinity(scip, rhs) )
2016  bnd = (consdata1->lhs - consdata1->vbdcoef * rhs)/scalar;
2017  }
2018  else
2019  {
2020  assert( SCIPisNegative(scip, consdata1->vbdcoef) );
2021  if ( ! SCIPisInfinity(scip, lhs) )
2022  bnd = (consdata1->lhs - consdata1->vbdcoef * lhs)/scalar;
2023  }
2024 
2025  if ( bnd != SCIP_UNKNOWN ) /*lint !e777*/
2026  {
2027  if ( SCIPisFeasPositive(scip, scalar) )
2028  {
2029  newbnd = SCIPadjustedVarLb(scip, consdata1->var, bnd);
2030  SCIP_CALL( SCIPtightenVarLb(scip, consdata1->var, newbnd, FALSE, cutoff, &tightened) );
2031  if ( tightened )
2032  {
2033  SCIPdebugMessage("<%s>, <%s> -> tightened lower bound: <%s> >= %.15g\n", SCIPconsGetName(cons0), SCIPconsGetName(cons1),
2034  SCIPvarGetName(consdata1->var), SCIPvarGetLbGlobal(consdata1->var));
2035  (*nchgbds)++;
2036  }
2037  }
2038  else if ( SCIPisFeasNegative(scip, scalar) )
2039  {
2040  newbnd = SCIPadjustedVarUb(scip, consdata1->var, bnd);
2041  SCIP_CALL( SCIPtightenVarUb(scip, consdata1->var, newbnd, FALSE, cutoff, &tightened) );
2042  if ( tightened )
2043  {
2044  SCIPdebugMessage("<%s>, <%s> -> tightened upper bound: <%s> >= %.15g\n", SCIPconsGetName(cons0), SCIPconsGetName(cons1),
2045  SCIPvarGetName(consdata1->var), SCIPvarGetUbGlobal(consdata1->var));
2046  (*nchgbds)++;
2047  }
2048  }
2049  }
2050  }
2051 
2052  /* upper bound for consdata1->var */
2053  if ( ! SCIPisInfinity(scip, consdata1->rhs) )
2054  {
2055  bnd = SCIP_UNKNOWN;
2056  if ( SCIPisPositive(scip, consdata1->vbdcoef) )
2057  {
2058  if ( ! SCIPisInfinity(scip, lhs) )
2059  bnd = (consdata1->rhs - consdata1->vbdcoef * lhs)/scalar;
2060  }
2061  else
2062  {
2063  assert( SCIPisNegative(scip, consdata1->vbdcoef) );
2064  if ( ! SCIPisInfinity(scip, rhs) )
2065  bnd = (consdata1->rhs - consdata1->vbdcoef * rhs)/scalar;
2066  }
2067 
2068  if ( bnd != SCIP_UNKNOWN ) /*lint !e777*/
2069  {
2070  if ( SCIPisFeasPositive(scip, scalar) )
2071  {
2072  newbnd = SCIPadjustedVarUb(scip, consdata1->var, bnd);
2073  SCIP_CALL( SCIPtightenVarUb(scip, consdata1->var, newbnd, FALSE, cutoff, &tightened) );
2074  if ( tightened )
2075  {
2076  SCIPdebugMessage("<%s>, <%s> -> tightened upper bound: <%s> >= %.15g\n", SCIPconsGetName(cons0), SCIPconsGetName(cons1),
2077  SCIPvarGetName(consdata1->var), SCIPvarGetUbGlobal(consdata1->var));
2078  (*nchgbds)++;
2079  }
2080  }
2081  else if ( SCIPisFeasNegative(scip, scalar) )
2082  {
2083  newbnd = SCIPadjustedVarLb(scip, consdata1->var, bnd);
2084  SCIP_CALL( SCIPtightenVarLb(scip, consdata1->var, newbnd, FALSE, cutoff, &tightened) );
2085  if ( tightened )
2086  {
2087  SCIPdebugMessage("<%s>, <%s> -> tightened lower bound: <%s> >= %.15g\n", SCIPconsGetName(cons0), SCIPconsGetName(cons1),
2088  SCIPvarGetName(consdata1->var), SCIPvarGetLbGlobal(consdata1->var));
2089  (*nchgbds)++;
2090  }
2091  }
2092  }
2093  }
2094  }
2095 
2096  /* check for equal variables */
2097  if( consdata0->var != consdata1->var || consdata0->vbdvar != consdata1->vbdvar )
2098  break;
2099 
2100  /* mark constraint1 for deletion if possible */
2101  deletecons1 = TRUE;
2102 
2103  /* the coefficients of both constraints are equal */
2104  if( SCIPisEQ(scip, coef, consdata1->vbdcoef) )
2105  {
2106  lhs = MAX(consdata1->lhs, lhs);
2107  rhs = MIN(consdata1->rhs, rhs);
2108  }
2109  /* now only one side and in both constraints the same side should be infinity and the vbdvar should be binary
2110  * then we neither do not need to have the same side nor the same coefficient
2111  */
2112  else if( SCIPvarIsBinary(consdata0->vbdvar)
2113  && (SCIPisInfinity(scip, -lhs) || SCIPisInfinity(scip, rhs))
2114  && (SCIPisInfinity(scip, -consdata1->lhs) || SCIPisInfinity(scip, consdata1->rhs))
2115  && (SCIPisInfinity(scip, -lhs) == SCIPisInfinity(scip, -consdata1->lhs)) )
2116  {
2117  /* lhs <= x + b*y <= +inf */
2118  if( !SCIPisInfinity(scip, -lhs) )
2119  {
2120  lhs = MAX(consdata1->lhs, lhs);
2121  coef = lhs - MAX(consdata1->lhs - consdata1->vbdcoef, consdata0->lhs - coef);
2122  }
2123  /* -inf <= x + b*y <= rhs */
2124  else
2125  {
2126  rhs = MIN(consdata1->rhs, rhs);
2127  coef = rhs - MIN(consdata1->rhs - consdata1->vbdcoef, consdata0->rhs - coef);
2128  }
2129  consdata0->propagated = FALSE;
2130  }
2131  else if( SCIPisPositive(scip, coef) == SCIPisPositive(scip, consdata1->vbdcoef)
2132  && ((!SCIPisInfinity(scip, -lhs) && !SCIPisInfinity(scip, -consdata1->lhs))
2133  || (!SCIPisInfinity(scip, rhs) && !SCIPisInfinity(scip, consdata1->rhs))) )
2134  {
2135  SCIP_Bool cons0lhsred;
2136  SCIP_Bool cons0rhsred;
2137  SCIP_Bool cons1lhsred;
2138  SCIP_Bool cons1rhsred;
2139  SCIP_Bool lhsequal;
2140  SCIP_Bool rhsequal;
2141 
2142  assert(!SCIPisInfinity(scip, lhs));
2143  assert(!SCIPisInfinity(scip, consdata1->lhs));
2144  assert(!SCIPisInfinity(scip, -rhs));
2145  assert(!SCIPisInfinity(scip, -consdata1->rhs));
2146 
2147  /* check if a left hand side of one constraints is redundant */
2148  checkRedundancySide(scip, consdata0->var, consdata0->vbdvar, coef, consdata1->vbdcoef, lhs, consdata1->lhs, &lhsequal, &cons0lhsred, &cons1lhsred, TRUE);
2149 
2150  /* check if a right hand side of one constraints is redundant */
2151  checkRedundancySide(scip, consdata0->var, consdata0->vbdvar, coef, consdata1->vbdcoef, rhs, consdata1->rhs, &rhsequal, &cons0rhsred, &cons1rhsred, FALSE);
2152 
2153  /* if cons0 is redundant, update cons1 and delete cons0 */
2154  if( (lhsequal || cons0lhsred) && (rhsequal || cons0rhsred) )
2155  {
2156  /* update flags of constraint which caused the redundancy s.t. nonredundant information doesn't get lost */
2157  SCIP_CALL( SCIPupdateConsFlags(scip, cons1, cons0) );
2158 
2159  SCIPdebugMessage("constraint: ");
2160  SCIPdebugPrintCons(scip, cons0, NULL);
2161  SCIPdebugMessage("is redundant to constraint: ");
2162  SCIPdebugPrintCons(scip, cons1, NULL);
2163 
2164  SCIP_CALL( SCIPdelCons(scip, cons0) );
2165  ++(*ndelconss);
2166 
2167  /* get next cons0 */
2168  break;
2169  }
2170  /* if cons1 is redundant, update cons0 and delete cons1 */
2171  else if( cons1lhsred && cons1rhsred )
2172  {
2173  /* update flags of constraint which caused the redundancy s.t. nonredundant information doesn't get lost */
2174  SCIP_CALL( SCIPupdateConsFlags(scip, cons0, cons1) );
2175 
2176  SCIPdebugMessage("constraint: ");
2177  SCIPdebugPrintCons(scip, cons1, NULL);
2178  SCIPdebugMessage("is redundant to constraint: ");
2179  SCIPdebugPrintCons(scip, cons0, NULL);
2180 
2181  SCIP_CALL( SCIPdelCons(scip, cons1) );
2182  ++(*ndelconss);
2183 
2184  /* get next cons1 */
2185  continue;
2186  }
2187  /* if left hand side of cons0 is redundant set it to -infinity */
2188  else if( (lhsequal || cons0lhsred) && !SCIPisInfinity(scip, -lhs) )
2189  {
2190  lhs = -SCIPinfinity(scip);
2191 
2192  /* if right hand side of cons1 is redundant too, set it to infinity */
2193  if( cons1rhsred && !SCIPisInfinity(scip, consdata1->rhs) )
2194  {
2195  SCIP_CALL( chgRhs(scip, cons1, SCIPinfinity(scip)) );
2196  ++(*nchgsides);
2197 
2198  SCIPdebugMessage("deleted rhs of constraint: ");
2199  SCIPdebugPrintCons(scip, cons1, NULL);
2200  SCIPdebugMessage("due to constraint: ");
2201  SCIPdebugPrintCons(scip, cons0, NULL);
2202  }
2203 
2204  /* later on we cannot not want to delete cons1 */
2205  deletecons1 = FALSE;
2206  }
2207  /* if right hand side of cons0 is redundant set it to infinity */
2208  else if( (rhsequal || cons0rhsred) && !SCIPisInfinity(scip, rhs) )
2209  {
2210  rhs = SCIPinfinity(scip);
2211 
2212  /* if left hand side of cons1 is redundant too, set it to -infinity */
2213  if( cons1lhsred && !SCIPisInfinity(scip, -consdata1->lhs) )
2214  {
2215  SCIP_CALL( chgLhs(scip, cons1, -SCIPinfinity(scip)) );
2216  ++(*nchgsides);
2217 
2218  SCIPdebugMessage("deleted lhs of constraint: ");
2219  SCIPdebugPrintCons(scip, cons1, NULL);
2220  SCIPdebugMessage("due to constraint: ");
2221  SCIPdebugPrintCons(scip, cons0, NULL);
2222  }
2223 
2224  /* later on we cannot not want to delete cons1 */
2225  deletecons1 = FALSE;
2226  }
2227  /* if left hand side of cons1 is redundant set it to -infinity */
2228  else if( cons1lhsred && !SCIPisInfinity(scip, -consdata1->lhs) )
2229  {
2230  SCIP_CALL( chgLhs(scip, cons1, -SCIPinfinity(scip)) );
2231  ++(*nchgsides);
2232 
2233  SCIPdebugMessage("deleted lhs of constraint: ");
2234  SCIPdebugPrintCons(scip, cons1, NULL);
2235  SCIPdebugMessage("due to constraint: ");
2236  SCIPdebugPrintCons(scip, cons0, NULL);
2237 
2238  continue;
2239  }
2240  /* if right hand side of cons1 is redundant set it to infinity */
2241  else if( cons1rhsred && !SCIPisInfinity(scip, consdata1->rhs) )
2242  {
2243  SCIP_CALL( chgRhs(scip, cons1, SCIPinfinity(scip)) );
2244  ++(*nchgsides);
2245 
2246  SCIPdebugMessage("deleted rhs of constraint: ");
2247  SCIPdebugPrintCons(scip, cons1, NULL);
2248  SCIPdebugMessage("due to constraint: ");
2249  SCIPdebugPrintCons(scip, cons0, NULL);
2250 
2251  continue;
2252  }
2253  else /* nothing was redundant */
2254  continue;
2255  }
2256  else
2257  {
2258  /* there is no redundancy in both constraints with same variables */
2259  continue;
2260  }
2261 
2262  if( SCIPisFeasLT(scip, rhs, lhs) )
2263  {
2264  SCIPdebugMessage("constraint <%s> and <%s> lead to infeasibility due to their sides\n", SCIPconsGetName(cons0), SCIPconsGetName(cons1));
2265  *cutoff = TRUE;
2266  break;
2267  }
2268 
2269  /* ensure that lhs <= rhs holds without tolerances as we only allow such rows to enter the LP */
2270  if( lhs > rhs )
2271  {
2272  rhs = (lhs + rhs)/2;
2273  lhs = rhs;
2274  }
2275 
2276  /* we decide to let constraint cons0 stay, so update data structure consdata0 */
2277 
2278  /* update coefficient of cons0 */
2279 
2280  /* special case if new coefficient becomes zero, both constraints are redundant but we may tighten the bounds */
2281  if( SCIPisZero(scip, coef) )
2282  {
2283  SCIP_Bool infeasible;
2284  SCIP_Bool tightened;
2285 
2286  SCIPdebugMessage("constraint: ");
2287  SCIPdebugPrintCons(scip, cons1, NULL);
2288  SCIPdebugMessage("and constraint: ");
2289  SCIPdebugPrintCons(scip, cons0, NULL);
2290  SCIPdebugMessage("are both redundant and lead to bounding of <%s> in [%g, %g]\n", SCIPvarGetName(consdata0->var), lhs, rhs);
2291 
2292  /* delete cons1 */
2293  SCIP_CALL( SCIPdelCons(scip, cons1) );
2294  ++(*ndelconss);
2295 
2296  /* update upper bound if possible
2297  *
2298  * @note we need to force the bound change since we are deleting the constraint afterwards
2299  */
2300  SCIP_CALL( SCIPtightenVarUb(scip, consdata0->var, rhs, TRUE, &infeasible, &tightened) );
2301  assert(!infeasible);
2302  if( tightened )
2303  ++(*nchgbds);
2304 
2305  /* update lower bound if possible
2306  *
2307  * @note we need to force the bound change since we are deleting the constraint afterwards
2308  */
2309  SCIP_CALL( SCIPtightenVarLb(scip, consdata0->var, lhs, TRUE, &infeasible, &tightened) );
2310  assert(!infeasible);
2311  if( tightened )
2312  ++(*nchgbds);
2313 
2314  /* delete cons0 */
2315  SCIP_CALL( SCIPdelCons(scip, cons0) );
2316  ++(*ndelconss);
2317 
2318  /* get next cons0 */
2319  break;
2320  }
2321 
2322  SCIPdebugMessage("constraint: ");
2323  SCIPdebugPrintCons(scip, cons1, NULL);
2324  SCIPdebugMessage("and constraint: ");
2325  SCIPdebugPrintCons(scip, cons0, NULL);
2326 
2327  /* if sign of coefficient switches, update the rounding locks of the variable */
2328  if( SCIPconsIsLocked(cons0) && consdata0->vbdcoef * coef < 0.0 )
2329  {
2330  assert(SCIPconsIsTransformed(cons0));
2331 
2332  /* remove rounding locks for variable with old coefficient and install rounding locks for variable with new
2333  * coefficient
2334  */
2335  if( SCIPisPositive(scip, consdata0->vbdcoef) )
2336  {
2337  SCIP_CALL( SCIPunlockVarCons(scip, consdata0->vbdvar, cons0,
2338  !SCIPisInfinity(scip, -consdata0->lhs), !SCIPisInfinity(scip, consdata0->rhs)) );
2339  SCIP_CALL( SCIPlockVarCons(scip, consdata0->vbdvar, cons0,
2340  !SCIPisInfinity(scip, consdata0->rhs), !SCIPisInfinity(scip, -consdata0->lhs)) );
2341  }
2342  else
2343  {
2344  SCIP_CALL( SCIPunlockVarCons(scip, consdata0->vbdvar, cons0,
2345  !SCIPisInfinity(scip, consdata0->rhs), !SCIPisInfinity(scip, -consdata0->lhs)) );
2346  SCIP_CALL( SCIPlockVarCons(scip, consdata0->vbdvar, cons0,
2347  !SCIPisInfinity(scip, -consdata0->lhs), !SCIPisInfinity(scip, consdata0->rhs)) );
2348  }
2349  }
2350 
2351  /* now change the coefficient */
2352  if( !SCIPisEQ(scip, consdata0->vbdcoef, coef) )
2353  {
2354  ++(*nchgcoefs);
2355 
2356  /* mark to add new varbound information */
2357  consdata0->varboundsadded = FALSE;
2358  consdata0->tightened = FALSE;
2359  consdata0->propagated = FALSE;
2360  consdata0->presolved = FALSE;
2361  consdata0->changed = FALSE;
2362 
2363  consdata0->vbdcoef = coef;
2364  }
2365 
2366  /* update lhs and rhs of cons0 */
2367  if( !SCIPisEQ(scip, consdata0->lhs, lhs) )
2368  {
2369  SCIP_CALL( chgLhs(scip, cons0, lhs) );
2370  ++(*nchgsides);
2371  }
2372  if( !SCIPisEQ(scip, consdata0->rhs, rhs) )
2373  {
2374  SCIP_CALL( chgRhs(scip, cons0, rhs) );
2375  ++(*nchgsides);
2376  }
2377 
2378  /* update flags of constraint which caused the redundancy s.t. nonredundant information doesn't get lost */
2379  SCIP_CALL( SCIPupdateConsFlags(scip, cons0, cons1) );
2380 
2381  SCIPdebugMessage("lead to new constraint: ");
2382  SCIPdebugPrintCons(scip, cons0, NULL);
2383 
2384  /* if cons1 is still marked for deletion, delete it */
2385  if( deletecons1 )
2386  {
2387  /* delete cons1 */
2388  SCIP_CALL( SCIPdelCons(scip, cons1) );
2389  ++(*ndelconss);
2390  }
2391 
2392  assert(SCIPconsIsActive(cons0));
2393  }
2394  }
2395 
2396  /* free temporary memory */
2397  SCIPfreeBufferArray(scip, &sortedconss);
2398 
2399  return SCIP_OKAY;
2400 }
2401 
2402 /** for all varbound constraints with two integer variables make the coefficients integral */
2403 static
2404 SCIP_RETCODE prettifyConss(
2405  SCIP* scip, /**< SCIP data structure */
2406  SCIP_CONS** conss, /**< constraint set */
2407  int nconss, /**< number of constraints in constraint set */
2408  int* nchgcoefs, /**< pointer to count the number of changed coefficients */
2409  int* nchgsides /**< pointer to count number of changed left/right hand sides */
2410  )
2411 {
2412  SCIP_CONSDATA* consdata;
2413  int c;
2414 
2415  assert(scip != NULL);
2416  assert(conss != NULL || nconss == 0);
2417  assert(nchgcoefs != NULL);
2418  assert(nchgsides != NULL);
2419 
2420  /* if we cannot find any constraint for prettifying, stop */
2421  if( SCIPgetNIntVars(scip) + SCIPgetNImplVars(scip) < 1 )
2422  return SCIP_OKAY;
2423 
2424  for( c = nconss - 1; c >= 0; --c )
2425  {
2426  assert(conss != NULL);
2427 
2428  if( SCIPconsIsDeleted(conss[c]) )
2429  continue;
2430 
2431  consdata = SCIPconsGetData(conss[c]);
2432  assert(consdata != NULL);
2433 
2434  /* check for integer variables and one coefficient with an absolute value smaller than 1 */
2435  /* @note: we allow that the variable type of the bounded variable can be smaller than the variable type of the
2436  * bounding variable
2437  */
2438  if( (SCIPvarGetType(consdata->var) == SCIP_VARTYPE_BINARY || SCIPvarGetType(consdata->var) == SCIP_VARTYPE_INTEGER
2439  || SCIPvarGetType(consdata->var) == SCIP_VARTYPE_IMPLINT)
2440  && (SCIPvarGetType(consdata->vbdvar) == SCIP_VARTYPE_INTEGER || SCIPvarGetType(consdata->vbdvar) == SCIP_VARTYPE_IMPLINT)
2441  && SCIPisLT(scip, REALABS(consdata->vbdcoef), 1.0) )
2442  {
2443  SCIP_Real epsilon;
2444  SCIP_Longint nominator;
2445  SCIP_Longint denominator;
2446  SCIP_Longint maxmult;
2447  SCIP_Bool success;
2448 
2449  epsilon = SCIPepsilon(scip) * 0.9; /* slightly decrease epsilon to be safe in rational conversion below */
2450  maxmult = (SCIP_Longint)(SCIPfeastol(scip)/epsilon + SCIPfeastol(scip));
2451  maxmult = MIN(maxmult, MAXSCALEDCOEF);
2452 
2453  success = SCIPrealToRational(consdata->vbdcoef, -epsilon, epsilon , maxmult, &nominator, &denominator);
2454 
2455  if( success )
2456  {
2457  /* it is possible that the dominator is a multiple of the nominator */
2458  if( SCIPisIntegral(scip, (SCIP_Real) denominator / (SCIP_Real) nominator) )
2459  {
2460  denominator /= nominator;
2461  nominator = 1;
2462  }
2463 
2464  success = success && (denominator <= maxmult);
2465 
2466  /* scale the constraint denominator/nominator */
2467  if( success && ABS(denominator) > 1 && nominator == 1)
2468  {
2469  SCIP_VAR* swapvar;
2470 
2471  /* print constraint before scaling */
2472  SCIPdebugPrintCons(scip, conss[c], NULL);
2473 
2474  assert(SCIPisEQ(scip, consdata->vbdcoef * denominator, 1.0));
2475 
2476  /* need to switch sides if coefficient is smaller then 0 */
2477  if( consdata->vbdcoef < 0 )
2478  {
2479  assert(denominator < 0);
2480 
2481  /* compute new sides */
2482 
2483  /* only right hand side exists */
2484  if( SCIPisInfinity(scip, -consdata->lhs) )
2485  {
2486  consdata->lhs = consdata->rhs * denominator;
2487  assert(!SCIPisInfinity(scip, -consdata->lhs) && !SCIPisInfinity(scip, consdata->lhs));
2488 
2489  consdata->rhs = SCIPinfinity(scip);
2490  }
2491  /* only left hand side exists */
2492  else if( SCIPisInfinity(scip, consdata->rhs) )
2493  {
2494  consdata->rhs = consdata->lhs * denominator;
2495  assert(!SCIPisInfinity(scip, consdata->rhs) && !SCIPisInfinity(scip, -consdata->rhs));
2496 
2497  consdata->lhs = -SCIPinfinity(scip);
2498  }
2499  /* both sides exist */
2500  else
2501  {
2502  SCIP_Real tmp;
2503 
2504  tmp = consdata->lhs;
2505  consdata->lhs = consdata->rhs * denominator;
2506  consdata->rhs = tmp * denominator;
2507  consdata->tightened = FALSE;
2508 
2509  assert(!SCIPisInfinity(scip, consdata->lhs) && !SCIPisInfinity(scip, -consdata->lhs));
2510  assert(SCIPisGE(scip, consdata->rhs, consdata->lhs) && !SCIPisInfinity(scip, consdata->rhs));
2511  }
2512  *nchgsides += 2;
2513  }
2514  /* coefficient > 0 */
2515  else
2516  {
2517  assert(denominator > 0);
2518 
2519  /* compute new left hand side */
2520  if( !SCIPisInfinity(scip, -consdata->lhs) )
2521  {
2522  consdata->lhs *= denominator;
2523  assert(!SCIPisInfinity(scip, consdata->lhs) && !SCIPisInfinity(scip, -consdata->lhs));
2524  ++(*nchgsides);
2525  }
2526 
2527  /* compute new right hand side */
2528  if( !SCIPisInfinity(scip, consdata->rhs) )
2529  {
2530  consdata->rhs *= denominator;
2531  assert(!SCIPisInfinity(scip, consdata->rhs) && !SCIPisInfinity(scip, -consdata->rhs));
2532  ++(*nchgsides);
2533  }
2534 
2535  assert(SCIPisGE(scip, consdata->rhs, consdata->lhs));
2536  }
2537 
2538  /* swap both variables */
2539  swapvar = consdata->var;
2540  consdata->var = consdata->vbdvar;
2541  consdata->vbdvar = swapvar;
2542 
2543  /* swap coefficient */
2544  consdata->vbdcoef = (SCIP_Real)denominator;
2545  ++(*nchgcoefs);
2546 
2547  /* mark to add new varbound information */
2548  consdata->varboundsadded = FALSE;
2549  consdata->tightened = FALSE;
2550 
2551  /* print constraint after scaling */
2552  SCIPdebugMessage("transformed into:");
2553  SCIPdebugPrintCons(scip, conss[c], NULL);
2554  }
2555  }
2556  }
2557  }
2558 
2559  return SCIP_OKAY;
2560 }
2561 
2562 /** replaces fixed and aggregated variables in variable bound constraint by active problem variables */
2563 static
2564 SCIP_RETCODE applyFixings(
2565  SCIP* scip, /**< SCIP data structure */
2566  SCIP_CONS* cons, /**< variable bound constraint */
2567  SCIP_EVENTHDLR* eventhdlr, /**< event handler */
2568  SCIP_Bool* cutoff, /**< pointer to store whether an infeasibility was detected */
2569  int* nchgbds, /**< pointer to count number of bound changes */
2570  int* ndelconss, /**< pointer to count number of deleted constraints */
2571  int* naddconss /**< pointer to count number of added constraints */
2572  )
2573 {
2574  SCIP_CONSDATA* consdata;
2575  SCIP_VAR* var;
2576  SCIP_Real varscalar;
2577  SCIP_Real varconstant;
2578  SCIP_VAR* vbdvar;
2579  SCIP_Real vbdvarscalar;
2580  SCIP_Real vbdvarconstant;
2581  SCIP_Bool varschanged;
2582  SCIP_Bool redundant;
2583 
2584  assert(scip != NULL);
2585  assert(cons != NULL);
2586  assert(cutoff != NULL);
2587  assert(nchgbds != NULL);
2588  assert(ndelconss != NULL);
2589  assert(naddconss != NULL);
2590 
2591  *cutoff = FALSE;
2592  redundant = FALSE;
2593 
2594  /* the variable bound constraint is: lhs <= x + c*y <= rhs */
2595  consdata = SCIPconsGetData(cons);
2596  assert(consdata != NULL);
2597 
2598  /* get active problem variables of x and y */
2599  var = consdata->var;
2600  varscalar = 1.0;
2601  varconstant = 0.0;
2602  SCIP_CALL( SCIPgetProbvarSum(scip, &var, &varscalar, &varconstant) );
2603  vbdvar = consdata->vbdvar;
2604  vbdvarscalar = 1.0;
2605  vbdvarconstant = 0.0;
2606  SCIP_CALL( SCIPgetProbvarSum(scip, &vbdvar, &vbdvarscalar, &vbdvarconstant) );
2607  varschanged = (var != consdata->var || vbdvar != consdata->vbdvar);
2608 
2609  /* if the variables are equal, the variable bound constraint reduces to standard bounds on the single variable */
2610  if( var == vbdvar && SCIPvarGetStatus(var) != SCIP_VARSTATUS_MULTAGGR )
2611  {
2612  SCIP_Real scalar;
2613  SCIP_Real constant;
2614 
2615  SCIPdebugMessage("variable bound constraint <%s> has equal variable and vbd variable <%s>\n",
2616  SCIPconsGetName(cons), SCIPvarGetName(var));
2617 
2618  /* lhs <= a1*z + b1 + c(a2*z + b2) <= rhs
2619  * <=> lhs <= (a1 + c*a2)z + (b1 + c*b2) <= rhs
2620  */
2621  scalar = varscalar + consdata->vbdcoef * vbdvarscalar;
2622  constant = varconstant + consdata->vbdcoef * vbdvarconstant;
2623  if( SCIPisZero(scip, scalar) )
2624  {
2625  /* no variable is left: the constraint is redundant or infeasible */
2626  if( SCIPisFeasLT(scip, constant, consdata->lhs) || SCIPisFeasGT(scip, constant, consdata->rhs) )
2627  *cutoff = TRUE;
2628  }
2629  else if( scalar > 0.0 )
2630  {
2631  if( !SCIPisInfinity(scip, -consdata->lhs) && !(*cutoff) )
2632  {
2633  SCIP_Bool tightened;
2634 
2635  SCIP_CALL( SCIPtightenVarLb(scip, var, (consdata->lhs - constant)/scalar, TRUE, cutoff, &tightened) );
2636  if( tightened )
2637  {
2638  SCIPdebugMessage(" -> tightened lower bound: <%s> >= %.15g\n",
2639  SCIPvarGetName(var), SCIPvarGetLbGlobal(var));
2640  (*nchgbds)++;
2641  }
2642  }
2643  if( !SCIPisInfinity(scip, consdata->rhs) && !(*cutoff) )
2644  {
2645  SCIP_Bool tightened;
2646 
2647  SCIP_CALL( SCIPtightenVarUb(scip, var, (consdata->rhs - constant)/scalar, TRUE, cutoff, &tightened) );
2648  if( tightened )
2649  {
2650  SCIPdebugMessage(" -> tightened upper bound: <%s> <= %.15g\n",
2651  SCIPvarGetName(var), SCIPvarGetUbGlobal(var));
2652  (*nchgbds)++;
2653  }
2654  }
2655  }
2656  else
2657  {
2658  if( !SCIPisInfinity(scip, -consdata->lhs) && !(*cutoff) )
2659  {
2660  SCIP_Bool tightened;
2661 
2662  SCIP_CALL( SCIPtightenVarUb(scip, var, (consdata->lhs - constant)/scalar, TRUE, cutoff, &tightened) );
2663  if( tightened )
2664  {
2665  SCIPdebugMessage(" -> tightened upper bound: <%s> <= %.15g\n",
2666  SCIPvarGetName(var), SCIPvarGetUbGlobal(var));
2667  (*nchgbds)++;
2668  }
2669  }
2670  if( !SCIPisInfinity(scip, consdata->rhs) && !(*cutoff) )
2671  {
2672  SCIP_Bool tightened;
2673 
2674  SCIP_CALL( SCIPtightenVarLb(scip, var, (consdata->rhs - constant)/scalar, TRUE, cutoff, &tightened) );
2675  if( tightened )
2676  {
2677  SCIPdebugMessage(" -> tightened lower bound: <%s> >= %.15g\n",
2678  SCIPvarGetName(var), SCIPvarGetLbGlobal(var));
2679  (*nchgbds)++;
2680  }
2681  }
2682  }
2683  redundant = TRUE;
2684  }
2685  else
2686  {
2687  /* if the variables should be replaced, drop the events and catch the events on the new variables afterwards */
2688  if( varschanged )
2689  {
2690  SCIP_CALL( dropEvents(scip, cons, eventhdlr) );
2691  }
2692 
2693  /* apply aggregation on x */
2694  if( SCIPisZero(scip, varscalar) )
2695  {
2696  SCIPdebugMessage("variable bound constraint <%s>: variable <%s> is fixed to %.15g\n",
2697  SCIPconsGetName(cons), SCIPvarGetName(consdata->var), varconstant);
2698 
2699  /* cannot change bounds on multi-aggregated variables */
2700  if( SCIPvarGetStatus(vbdvar) != SCIP_VARSTATUS_MULTAGGR )
2701  {
2702  /* x is fixed to varconstant: update bounds of y and delete the variable bound constraint */
2703  if( !SCIPisInfinity(scip, -consdata->lhs) && !(*cutoff) )
2704  {
2705  if( consdata->vbdcoef > 0.0 )
2706  {
2707  SCIP_Bool tightened;
2708 
2709  SCIP_CALL( SCIPtightenVarLb(scip, consdata->vbdvar, (consdata->lhs - varconstant)/consdata->vbdcoef,
2710  TRUE, cutoff, &tightened) );
2711  if( tightened )
2712  {
2713  SCIPdebugMessage(" -> tightened lower bound: <%s> >= %.15g\n",
2714  SCIPvarGetName(consdata->vbdvar), SCIPvarGetLbGlobal(consdata->vbdvar));
2715  (*nchgbds)++;
2716  }
2717  }
2718  else
2719  {
2720  SCIP_Bool tightened;
2721 
2722  SCIP_CALL( SCIPtightenVarUb(scip, consdata->vbdvar, (consdata->lhs - varconstant)/consdata->vbdcoef,
2723  TRUE, cutoff, &tightened) );
2724  if( tightened )
2725  {
2726  SCIPdebugMessage(" -> tightened upper bound: <%s> <= %.15g\n",
2727  SCIPvarGetName(consdata->vbdvar), SCIPvarGetUbGlobal(consdata->vbdvar));
2728  (*nchgbds)++;
2729  }
2730  }
2731  }
2732  if( !SCIPisInfinity(scip, consdata->rhs) && !(*cutoff) )
2733  {
2734  if( consdata->vbdcoef > 0.0 )
2735  {
2736  SCIP_Bool tightened;
2737 
2738  SCIP_CALL( SCIPtightenVarUb(scip, consdata->vbdvar, (consdata->rhs - varconstant)/consdata->vbdcoef,
2739  TRUE, cutoff, &tightened) );
2740  if( tightened )
2741  {
2742  SCIPdebugMessage(" -> tightened upper bound: <%s> <= %.15g\n",
2743  SCIPvarGetName(consdata->vbdvar), SCIPvarGetUbGlobal(consdata->vbdvar));
2744  (*nchgbds)++;
2745  }
2746  }
2747  else
2748  {
2749  SCIP_Bool tightened;
2750 
2751  SCIP_CALL( SCIPtightenVarLb(scip, consdata->vbdvar, (consdata->rhs - varconstant)/consdata->vbdcoef,
2752  TRUE, cutoff, &tightened) );
2753  if( tightened )
2754  {
2755  SCIPdebugMessage(" -> tightened lower bound: <%s> >= %.15g\n",
2756  SCIPvarGetName(consdata->vbdvar), SCIPvarGetLbGlobal(consdata->vbdvar));
2757  (*nchgbds)++;
2758  }
2759  }
2760  }
2761  redundant = TRUE;
2762  }
2763  }
2764  else if( var != consdata->var )
2765  {
2766  /* replace aggregated variable x in the constraint by its aggregation */
2767  if( varscalar > 0.0 )
2768  {
2769  /* lhs := (lhs - varconstant) / varscalar
2770  * rhs := (rhs - varconstant) / varscalar
2771  * c := c / varscalar
2772  */
2773  if( !SCIPisInfinity(scip, -consdata->lhs) )
2774  consdata->lhs = (consdata->lhs - varconstant)/varscalar;
2775  if( !SCIPisInfinity(scip, consdata->rhs) )
2776  consdata->rhs = (consdata->rhs - varconstant)/varscalar;
2777  consdata->vbdcoef /= varscalar;
2778 
2779  consdata->tightened = FALSE;
2780  }
2781  else
2782  {
2783  SCIP_Real lhs;
2784 
2785  assert(varscalar != 0.0);
2786 
2787  /* lhs := (rhs - varconstant) / varscalar
2788  * rhs := (lhs - varconstant) / varscalar
2789  * c := c / varscalar
2790  */
2791  lhs = consdata->lhs;
2792  consdata->lhs = -consdata->rhs;
2793  consdata->rhs = -lhs;
2794  if( !SCIPisInfinity(scip, -consdata->lhs) )
2795  consdata->lhs = (consdata->lhs + varconstant)/(-varscalar);
2796  if( !SCIPisInfinity(scip, consdata->rhs) )
2797  consdata->rhs = (consdata->rhs + varconstant)/(-varscalar);
2798  consdata->vbdcoef /= varscalar;
2799 
2800  consdata->tightened = FALSE;
2801  }
2802  /* release old variable */
2803  SCIP_CALL( SCIPreleaseVar(scip, &(consdata->var)) );
2804  consdata->var = var;
2805  /* capture new variable */
2806  SCIP_CALL( SCIPcaptureVar(scip, consdata->var) );
2807  }
2808 
2809  /* apply aggregation on y */
2810  if( SCIPisZero(scip, vbdvarscalar) )
2811  {
2812  SCIPdebugMessage("variable bound constraint <%s>: vbd variable <%s> is fixed to %.15g\n",
2813  SCIPconsGetName(cons), SCIPvarGetName(consdata->vbdvar), vbdvarconstant);
2814 
2815  /* cannot change bounds on multi-aggregated variables */
2816  if( SCIPvarGetStatus(var) != SCIP_VARSTATUS_MULTAGGR )
2817  {
2818  /* y is fixed to vbdvarconstant: update bounds of x and delete the variable bound constraint */
2819  if( !SCIPisInfinity(scip, -consdata->lhs) && !(*cutoff) )
2820  {
2821  SCIP_Bool tightened;
2822 
2823  SCIP_CALL( SCIPtightenVarLb(scip, consdata->var, consdata->lhs - consdata->vbdcoef * vbdvarconstant,
2824  TRUE, cutoff, &tightened) );
2825  if( tightened )
2826  {
2827  SCIPdebugMessage(" -> tightened lower bound: <%s> >= %.15g\n",
2828  SCIPvarGetName(consdata->var), SCIPvarGetLbGlobal(consdata->var));
2829  (*nchgbds)++;
2830  }
2831  }
2832  if( !SCIPisInfinity(scip, consdata->rhs) && !(*cutoff) )
2833  {
2834  SCIP_Bool tightened;
2835 
2836  SCIP_CALL( SCIPtightenVarUb(scip, consdata->var, consdata->rhs - consdata->vbdcoef * vbdvarconstant,
2837  TRUE, cutoff, &tightened) );
2838  if( tightened )
2839  {
2840  SCIPdebugMessage(" -> tightened upper bound: <%s> <= %.15g\n",
2841  SCIPvarGetName(consdata->var), SCIPvarGetUbGlobal(consdata->var));
2842  (*nchgbds)++;
2843  }
2844  }
2845  redundant = TRUE;
2846  }
2847  }
2848  else if( vbdvar != consdata->vbdvar )
2849  {
2850  /* replace aggregated variable y in the constraint by its aggregation:
2851  * lhs := lhs - c * vbdvarconstant
2852  * rhs := rhs - c * vbdvarconstant
2853  * c := c * vbdvarscalar
2854  */
2855  if( !SCIPisInfinity(scip, -consdata->lhs) )
2856  consdata->lhs -= consdata->vbdcoef * vbdvarconstant;
2857  if( !SCIPisInfinity(scip, consdata->rhs) )
2858  consdata->rhs -= consdata->vbdcoef * vbdvarconstant;
2859  consdata->vbdcoef *= vbdvarscalar;
2860 
2861  consdata->tightened = FALSE;
2862 
2863  /* release old variable */
2864  SCIP_CALL( SCIPreleaseVar(scip, &(consdata->vbdvar)) );
2865  consdata->vbdvar = vbdvar;
2866  /* capture new variable */
2867  SCIP_CALL( SCIPcaptureVar(scip, consdata->vbdvar) );
2868  }
2869 
2870  /* catch the events again on the new variables */
2871  if( varschanged )
2872  {
2873  SCIP_CALL( catchEvents(scip, cons, eventhdlr) );
2874  }
2875  }
2876 
2877  /* mark constraint changed, if a variable was exchanged */
2878  if( varschanged )
2879  {
2880  consdata->changed = TRUE;
2881  }
2882 
2883  /* active multi aggregations are now resolved by creating a new linear constraint */
2884  if( !(*cutoff) && !redundant && (SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR || SCIPvarGetStatus(vbdvar) == SCIP_VARSTATUS_MULTAGGR) )
2885  {
2886  SCIP_CONS* newcons;
2887  SCIP_Real lhs;
2888  SCIP_Real rhs;
2889 
2890  lhs = consdata->lhs;
2891  rhs = consdata->rhs;
2892 
2893  /* create upgraded linear constraint */
2894  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, SCIPconsGetName(cons), 0, NULL, NULL, lhs, rhs,
2895  SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
2896  SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),
2897  SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons),
2898  SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
2899 
2900  /* if var was fixed, then the case that vbdvar was multi-aggregated, was not yet resolved */
2901  if( var != consdata->var )
2902  {
2903  assert(SCIPvarGetStatus(vbdvar) == SCIP_VARSTATUS_MULTAGGR);
2904  assert(SCIPisZero(scip, varscalar)); /* this means that var was fixed */
2905 
2906  /* add offset that results of the fixed variable */
2907  if( SCIPisZero(scip, varconstant) != 0 )
2908  {
2909  if( !SCIPisInfinity(scip, rhs) )
2910  {
2911  SCIP_CALL( SCIPchgRhsLinear(scip, newcons, rhs - varconstant) );
2912  }
2913  if( !SCIPisInfinity(scip, -lhs) )
2914  {
2915  SCIP_CALL( SCIPchgLhsLinear(scip, newcons, lhs - varconstant) );
2916  }
2917  }
2918  }
2919  else
2920  {
2921  assert(var == consdata->var);
2922 
2923  SCIP_CALL( SCIPaddCoefLinear(scip, newcons, consdata->var, 1.0) );
2924  }
2925 
2926  /* if vbdvar was fixed, then the case that var was multi-aggregated, was not yet resolved */
2927  if( vbdvar != consdata->vbdvar )
2928  {
2929  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR);
2930  assert(SCIPisZero(scip, vbdvarscalar)); /* this means that var was fixed */
2931 
2932  /* add offset that results of the fixed variable */
2933  if( SCIPisZero(scip, vbdvarconstant) != 0 )
2934  {
2935  if( !SCIPisInfinity(scip, rhs) )
2936  {
2937  SCIP_CALL( SCIPchgRhsLinear(scip, newcons, rhs - vbdvarconstant) );
2938  }
2939  if( !SCIPisInfinity(scip, -lhs) )
2940  {
2941  SCIP_CALL( SCIPchgLhsLinear(scip, newcons, lhs - vbdvarconstant) );
2942  }
2943  }
2944  }
2945  else
2946  {
2947  assert(vbdvar == consdata->vbdvar);
2948 
2949  SCIP_CALL( SCIPaddCoefLinear(scip, newcons, consdata->vbdvar, consdata->vbdcoef) );
2950  }
2951 
2952  SCIP_CALL( SCIPaddCons(scip, newcons) );
2953 
2954  SCIPdebugMessage("resolved multi aggregation in varbound constraint <%s> by creating a new linear constraint\n", SCIPconsGetName(cons));
2955  SCIPdebugPrintCons(scip, newcons, NULL);
2956 
2957  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
2958 
2959  redundant = TRUE;
2960  ++(*naddconss);
2961  }
2962 
2963  /* delete a redundant constraint */
2964  if( !(*cutoff) && redundant )
2965  {
2966  SCIPdebugMessage(" -> variable bound constraint <%s> is redundant\n", SCIPconsGetName(cons));
2967  SCIP_CALL( SCIPdelCons(scip, cons) );
2968  (*ndelconss)++;
2969  }
2970 
2971  return SCIP_OKAY;
2972 }
2973 
2974 /** tightens variable bound coefficient by inspecting the global bounds of the involved variables; note: this is also
2975  * performed by the linear constraint handler - only necessary if the user directly creates variable bound constraints
2976  */
2977 static
2978 SCIP_RETCODE tightenCoefs(
2979  SCIP* scip, /**< SCIP data structure */
2980  SCIP_CONS* cons, /**< variable bound constraint */
2981  int* nchgcoefs, /**< pointer to count the number of changed coefficients */
2982  int* nchgsides, /**< pointer to count the number of left and right hand sides */
2983  int* ndelconss /**< pointer to count number of deleted constraints */
2984  )
2985 {
2986  SCIP_CONSDATA* consdata;
2987  SCIP_Real xlb;
2988  SCIP_Real xub;
2989  int oldnchgcoefs;
2990  int oldnchgsides;
2991 
2992  assert(nchgcoefs != NULL);
2993  assert(nchgsides != NULL);
2994  assert(ndelconss != NULL);
2995 
2996  consdata = SCIPconsGetData(cons);
2997  assert(consdata != NULL);
2998 
2999  /* tightening already done */
3000  if( consdata->tightened )
3001  return SCIP_OKAY;
3002 
3003  SCIPdebugMessage("tightening coefficients on variable bound constraint <%s>\n", SCIPconsGetName(cons));
3004 
3005  consdata->tightened = TRUE;
3006 
3007  /* if values and variable are integral the sides should it be too */
3008  if( SCIPvarGetType(consdata->var) <= SCIP_VARTYPE_IMPLINT
3009  && SCIPvarGetType(consdata->vbdvar) <= SCIP_VARTYPE_IMPLINT
3010  && SCIPisIntegral(scip, consdata->vbdcoef) )
3011  {
3012  if( !SCIPisFeasIntegral(scip, consdata->lhs) )
3013  {
3014  consdata->lhs = SCIPfeasCeil(scip, consdata->lhs);
3015  ++(*nchgsides);
3016  consdata->changed = TRUE;
3017  }
3018  if( !SCIPisFeasIntegral(scip, consdata->rhs) )
3019  {
3020  consdata->rhs = SCIPfeasFloor(scip, consdata->rhs);
3021  ++(*nchgsides);
3022  consdata->changed = TRUE;
3023  }
3024  }
3025 
3026  /* coefficient tightening only works for binary bound variable */
3027  if( !SCIPvarIsBinary(consdata->vbdvar) )
3028  return SCIP_OKAY;
3029 
3030  oldnchgcoefs = *nchgcoefs;
3031  oldnchgsides = *nchgsides;
3032 
3033  /* coefficients tightening when all variables are integer */
3034  /* we consider the following varbound constraint: lhs <= x + b*y <= rhs (sides are possibly infinity)
3035  * y should always be binary and x of integral type and b not integral, we also need at least one side with infinity
3036  * or not integral value.
3037  *
3038  * 1. if( (lhs is integral and not -infinity) and ((rhs is infinity) or (b - floor(b) <= rhs - floor(rhs))) ):
3039  *
3040  * lhs <= x + b*y <= rhs => lhs <= x + floor(b)*y <= floor(rhs)
3041  *
3042  * 2. if( (rhs is integral and not infinity) and ((lhs is -infinity) or (b - floor(b) >= lhs - floor(lhs))) ):
3043  *
3044  * lhs <= x + b*y <= rhs => ceil(lhs) <= x + ceil(b)*y <= rhs
3045  *
3046  * 3. if( ((lhs is -infinity) or (b - floor(b) >= lhs - floor(lhs)))
3047  * and ((rhs is infinity) or (b - floor(b) > rhs - floor(rhs))) ):
3048  *
3049  * lhs <= x + b*y <= rhs => ceil(lhs) <= x + ceil(b)*y <= floor(rhs)
3050  *
3051  * 4. if( ((lhs is -infinity) or (b - floor(b) < lhs - floor(lhs)))
3052  * and ((rhs is infinity) or (b - floor(b) <= rhs - floor(rhs))) ):
3053  *
3054  * lhs <= x + b*y <= rhs => ceil(lhs) <= x + floor(b)*y <= floor(rhs)
3055  *
3056  * 5. if( (lhs is not integral) or (rhs is not integral) )
3057  *
3058  * if (lhs is not -infinity)
3059  * if (b - floor(b) < lhs - floor(lhs)):
3060  *
3061  * lhs <= x + b*y => ceil(lhs) <= x + b*y
3062  *
3063  * else if (b - floor(b) > lhs - floor(lhs)):
3064  *
3065  * lhs <= x + b*y => floor(lhs) + b - floor(b) <= x + b*y
3066  *
3067  * if (rhs is not infinity)
3068  * if (b - floor(b) < rhs - floor(rhs)):
3069  *
3070  * x + b*y <= rhs => x + b*y <= floor(rhs) + b - floor(b)
3071  *
3072  * else if (b - floor(b) > rhs - floor(rhs)):
3073  *
3074  * x + b*y <= rhs => x + b*y <= floor(rhs)
3075  */
3076  if( (SCIPvarGetType(consdata->var) == SCIP_VARTYPE_INTEGER || SCIPvarGetType(consdata->var) == SCIP_VARTYPE_IMPLINT || SCIPvarGetType(consdata->var) == SCIP_VARTYPE_BINARY)
3077  && !SCIPisIntegral(scip, consdata->vbdcoef)
3078  && (!SCIPisIntegral(scip, consdata->lhs) || SCIPisInfinity(scip, -consdata->lhs)
3079  || !SCIPisIntegral(scip, consdata->rhs) || SCIPisInfinity(scip, consdata->rhs)) )
3080  {
3081  /* infinity should be an integral value */
3082  assert(!SCIPisInfinity(scip, -consdata->lhs) || SCIPisIntegral(scip, consdata->lhs));
3083  assert(!SCIPisInfinity(scip, consdata->rhs) || SCIPisIntegral(scip, consdata->rhs));
3084 
3085  /* should not be a redundant constraint */
3086  assert(!SCIPisInfinity(scip, consdata->rhs) || !SCIPisInfinity(scip, -consdata->lhs));
3087 
3088  /* case 1 */
3089  if( SCIPisIntegral(scip, consdata->lhs) && !SCIPisInfinity(scip, -consdata->lhs) &&
3090  (SCIPisInfinity(scip, consdata->rhs) || SCIPisFeasLE(scip, consdata->vbdcoef - SCIPfeasFloor(scip, consdata->vbdcoef), consdata->rhs - SCIPfeasFloor(scip, consdata->rhs))) )
3091  {
3092  consdata->vbdcoef = SCIPfeasFloor(scip, consdata->vbdcoef);
3093  ++(*nchgcoefs);
3094 
3095  if( !SCIPisFeasIntegral(scip, consdata->rhs) )
3096  {
3097  consdata->rhs = SCIPfeasFloor(scip, consdata->rhs);
3098  ++(*nchgsides);
3099  }
3100  }
3101  /* case 2 */
3102  else if( SCIPisIntegral(scip, consdata->rhs) && !SCIPisInfinity(scip, consdata->rhs) &&
3103  (SCIPisInfinity(scip, -consdata->lhs) || SCIPisFeasGE(scip, consdata->vbdcoef - SCIPfeasFloor(scip, consdata->vbdcoef), consdata->lhs - SCIPfeasFloor(scip, consdata->lhs))) )
3104 
3105  {
3106  consdata->vbdcoef = SCIPfeasCeil(scip, consdata->vbdcoef);
3107  ++(*nchgcoefs);
3108 
3109  if( !SCIPisFeasIntegral(scip, consdata->lhs) )
3110  {
3111  consdata->lhs = SCIPfeasCeil(scip, consdata->lhs);
3112  ++(*nchgsides);
3113  }
3114  }
3115  /* case 3 */
3116  else if( (SCIPisInfinity(scip, -consdata->lhs) || SCIPisFeasGE(scip, consdata->vbdcoef - SCIPfeasFloor(scip, consdata->vbdcoef), consdata->lhs - SCIPfeasFloor(scip, consdata->lhs))) && (SCIPisInfinity(scip, consdata->rhs) || SCIPisFeasGT(scip, consdata->vbdcoef - SCIPfeasFloor(scip, consdata->vbdcoef), consdata->rhs - SCIPfeasFloor(scip, consdata->rhs))) )
3117  {
3118  consdata->vbdcoef = SCIPfeasCeil(scip, consdata->vbdcoef);
3119  ++(*nchgcoefs);
3120 
3121  if( !SCIPisFeasIntegral(scip, consdata->lhs) )
3122  {
3123  consdata->lhs = SCIPfeasCeil(scip, consdata->lhs);
3124  ++(*nchgsides);
3125  }
3126  if( !SCIPisFeasIntegral(scip, consdata->rhs) )
3127  {
3128  consdata->rhs = SCIPfeasFloor(scip, consdata->rhs);
3129  ++(*nchgsides);
3130  }
3131  }
3132  /* case 4 */
3133  else if( (SCIPisInfinity(scip, -consdata->lhs) || SCIPisFeasLT(scip, consdata->vbdcoef - SCIPfeasFloor(scip, consdata->vbdcoef), consdata->lhs - SCIPfeasFloor(scip, consdata->lhs))) && (SCIPisInfinity(scip, consdata->rhs) || SCIPisFeasLE(scip, consdata->vbdcoef - SCIPfeasFloor(scip, consdata->vbdcoef), consdata->rhs - SCIPfeasFloor(scip, consdata->rhs))) )
3134  {
3135  consdata->vbdcoef = SCIPfeasFloor(scip, consdata->vbdcoef);
3136  ++(*nchgcoefs);
3137 
3138  if( !SCIPisFeasIntegral(scip, consdata->lhs) )
3139  {
3140  consdata->lhs = SCIPfeasCeil(scip, consdata->lhs);
3141  ++(*nchgsides);
3142  }
3143  if( !SCIPisFeasIntegral(scip, consdata->rhs) )
3144  {
3145  consdata->rhs = SCIPfeasFloor(scip, consdata->rhs);
3146  ++(*nchgsides);
3147  }
3148  }
3149  /* case 5 */
3150  if( !SCIPisFeasIntegral(scip, consdata->lhs) || !SCIPisFeasIntegral(scip, consdata->rhs) )
3151  {
3152  if( !SCIPisInfinity(scip, -consdata->lhs) )
3153  {
3154  if( SCIPisFeasLT(scip, consdata->vbdcoef - SCIPfeasFloor(scip, consdata->vbdcoef), consdata->lhs - SCIPfeasFloor(scip, consdata->lhs)) )
3155  {
3156  consdata->lhs = SCIPfeasCeil(scip, consdata->lhs);
3157  ++(*nchgsides);
3158  }
3159  else if( SCIPisFeasGT(scip, consdata->vbdcoef - SCIPfeasFloor(scip, consdata->vbdcoef), consdata->lhs - SCIPfeasFloor(scip, consdata->lhs)) )
3160  {
3161  consdata->lhs = SCIPfeasFloor(scip, consdata->lhs) + (consdata->vbdcoef - SCIPfeasFloor(scip, consdata->vbdcoef));
3162  ++(*nchgsides);
3163  }
3164  }
3165  if( !SCIPisInfinity(scip, consdata->rhs) )
3166  {
3167  if( SCIPisFeasLT(scip, consdata->vbdcoef - SCIPfeasFloor(scip, consdata->vbdcoef), consdata->rhs - SCIPfeasFloor(scip, consdata->rhs)) )
3168  {
3169  consdata->rhs = SCIPfeasFloor(scip, consdata->rhs) + (consdata->vbdcoef - SCIPfeasFloor(scip, consdata->vbdcoef));
3170  ++(*nchgsides);
3171  }
3172  else if( SCIPisFeasGT(scip, consdata->vbdcoef - SCIPfeasFloor(scip, consdata->vbdcoef), consdata->rhs - SCIPfeasFloor(scip, consdata->rhs)) )
3173  {
3174  consdata->rhs = SCIPfeasFloor(scip, consdata->rhs);
3175  ++(*nchgsides);
3176  }
3177  }
3178  }
3179  }
3180 
3181  /* check if due to tightening the constraint got redundant */
3182  if( SCIPisZero(scip, consdata->vbdcoef) )
3183  {
3184  assert(SCIPisGE(scip, SCIPvarGetLbGlobal(consdata->var), consdata->lhs));
3185  assert(SCIPisLE(scip, SCIPvarGetUbGlobal(consdata->var), consdata->rhs));
3186 
3187  SCIPdebugMessage(" -> variable bound constraint <%s> is redundant\n", SCIPconsGetName(cons));
3188  SCIP_CALL( SCIPdelCons(scip, cons) );
3189  ++(*ndelconss);
3190 
3191  return SCIP_OKAY;
3192  }
3193 
3194  /* get bounds of variable x */
3195  xlb = SCIPvarGetLbGlobal(consdata->var);
3196  xub = SCIPvarGetUbGlobal(consdata->var);
3197 
3198  /* it can happen that var is not of varstatus SCIP_VARSTATUS_FIXED but the bounds are equal, in this case we need to
3199  * stop
3200  */
3201  if( SCIPisEQ(scip, xlb, xub) )
3202  return SCIP_OKAY;
3203 
3204  /* modification of coefficient checking for slack in constraints */
3205  if( !SCIPisInfinity(scip, -consdata->lhs) && !SCIPisInfinity(scip, consdata->rhs) )
3206  {
3207  /* lhs <= x + c*y <= rhs => lhs - c*y <= x <= rhs - c*y */
3208  if( consdata->vbdcoef > 0.0 && SCIPisFeasGT(scip, xlb, consdata->lhs - consdata->vbdcoef) && SCIPisFeasLT(scip, xub, consdata->rhs) )
3209  {
3210  SCIP_Real newcoef;
3211  SCIP_Real newrhs;
3212  SCIP_Real oldrhs;
3213 
3214  oldrhs = consdata->rhs;
3215 
3216  /* constraint has positive slack for both non-restricting cases y = 0, or y = 1, respectively
3217  * -> modify coefficients such that constraint is tight in at least one of the non-restricting cases
3218  * -> c' = MAX(c - rhs + xub, lhs - xlb), rhs' = rhs - c + c'
3219  */
3220  newcoef = MAX(consdata->vbdcoef - consdata->rhs + xub, consdata->lhs - xlb);
3221  newrhs = consdata->rhs - consdata->vbdcoef + newcoef;
3222 
3223  SCIPdebugMessage("tighten varbound %.15g <= <%s>[%.15g,%.15g] %+.15g<%s> <= %.15g to %.15g <= <%s> %+.15g<%s> <= %.15g\n",
3224  consdata->lhs, SCIPvarGetName(consdata->var), xlb, xub, consdata->vbdcoef, SCIPvarGetName(consdata->vbdvar), consdata->rhs,
3225  consdata->lhs, SCIPvarGetName(consdata->var), newcoef, SCIPvarGetName(consdata->vbdvar), newrhs);
3226 
3227  /* we cannot allow that the coefficient changes the sign because of the rounding locks */
3228  assert(consdata->vbdcoef * newcoef > 0);
3229 
3230  consdata->vbdcoef = newcoef;
3231  consdata->rhs = newrhs;
3232  (*nchgcoefs)++;
3233  (*nchgsides)++;
3234 
3235  /* some of the cases 1. to 5. might be applicable after changing the rhs to an integral value; one example is
3236  * the varbound constraint 0.225 <= x - 1.225 y <= 0.775 for which none of the above cases apply but after
3237  * tightening the lhs to 0.0 it is possible to reduce the rhs by applying the 1. reduction
3238  */
3239  if( !SCIPisFeasIntegral(scip, oldrhs) && SCIPisFeasIntegral(scip, newrhs) )
3240  {
3241  consdata->tightened = FALSE;
3242  SCIP_CALL( tightenCoefs(scip, cons, nchgcoefs, nchgsides, ndelconss) );
3243  assert(consdata->tightened);
3244  }
3245  }
3246  else if( consdata->vbdcoef < 0.0 && SCIPisFeasGT(scip, xlb, consdata->lhs) && SCIPisFeasLT(scip, xub, consdata->rhs - consdata->vbdcoef) )
3247  {
3248  SCIP_Real newcoef;
3249  SCIP_Real newlhs;
3250  SCIP_Real oldlhs;
3251 
3252  oldlhs = consdata->lhs;
3253 
3254  /* constraint has positive slack for both non-restricting cases y = 0, or y = 1, respectively
3255  * -> modify coefficients such that constraint is tight in at least one of the non-restricting cases
3256  * -> c' = MIN(c - lhs + xlb, rhs - xub), lhs' = lhs - c + c'
3257  */
3258  newcoef = MIN(consdata->vbdcoef - consdata->lhs + xlb, consdata->rhs - xub);
3259  newlhs = consdata->lhs - consdata->vbdcoef + newcoef;
3260 
3261  SCIPdebugMessage("tighten varbound %.15g <= <%s>[%.15g,%.15g] %+.15g<%s> <= %.15g to %.15g <= <%s> %+.15g<%s> <= %.15g\n",
3262  consdata->lhs, SCIPvarGetName(consdata->var), xlb, xub, consdata->vbdcoef, SCIPvarGetName(consdata->vbdvar), consdata->rhs,
3263  newlhs, SCIPvarGetName(consdata->var), newcoef, SCIPvarGetName(consdata->vbdvar), consdata->rhs);
3264 
3265  /* we cannot allow that the coefficient changes the sign because of the rounding locks */
3266  assert(consdata->vbdcoef * newcoef > 0);
3267 
3268  consdata->vbdcoef = newcoef;
3269  consdata->lhs = newlhs;
3270  (*nchgcoefs)++;
3271  (*nchgsides)++;
3272 
3273  /* some of the cases 1. to 5. might be applicable after changing the rhs to an integral value; one example is
3274  * the varbound constraint 0.225 <= x - 1.225 y <= 0.775 for which none of the above cases apply but after
3275  * tightening the lhs to 0.0 it is possible to reduce the rhs by applying the 1. reduction
3276  */
3277  if( !SCIPisFeasIntegral(scip, oldlhs) && SCIPisFeasIntegral(scip, newlhs) )
3278  {
3279  consdata->tightened = FALSE;
3280  SCIP_CALL( tightenCoefs(scip, cons, nchgcoefs, nchgsides, ndelconss) );
3281  assert(consdata->tightened);
3282  }
3283  }
3284  }
3285  else if( !SCIPisInfinity(scip, -consdata->lhs) && SCIPisInfinity(scip, consdata->rhs) )
3286  {
3287  /* lhs <= x + c*y => x >= lhs - c*y */
3288  if( consdata->vbdcoef > 0.0 && SCIPisFeasGT(scip, xlb, consdata->lhs - consdata->vbdcoef) )
3289  {
3290  /* constraint has positive slack for the non-restricting case y = 1
3291  * -> modify coefficients such that constraint is tight in the non-restricting case y = 1 and equivalent in the restricting case y = 0
3292  * -> c' = lhs - xlb
3293  */
3294  SCIPdebugMessage("tighten binary VLB <%s>[%.15g,%.15g] %+.15g<%s> >= %.15g to <%s> %+.15g<%s> >= %.15g\n",
3295  SCIPvarGetName(consdata->var), xlb, xub, consdata->vbdcoef, SCIPvarGetName(consdata->vbdvar), consdata->lhs,
3296  SCIPvarGetName(consdata->var), consdata->lhs - xlb, SCIPvarGetName(consdata->vbdvar), consdata->lhs);
3297 
3298  /* we cannot allow that the coefficient changes the sign because of the rounding locks */
3299  assert(consdata->vbdcoef * (consdata->lhs - xlb) > 0);
3300 
3301  consdata->vbdcoef = consdata->lhs - xlb;
3302  (*nchgcoefs)++;
3303  }
3304  else if( consdata->vbdcoef < 0.0 && SCIPisFeasGT(scip, xlb, consdata->lhs) )
3305  {
3306  /* constraint has positive slack for the non-restricting case y = 0
3307  * -> modify coefficients such that constraint is tight in the non-restricting case y = 0 and equivalent in the restricting case y = 1
3308  * -> c' = c - lhs + xlb, lhs' = xlb
3309  */
3310  SCIPdebugMessage("tighten binary VLB <%s>[%.15g,%.15g] %+.15g<%s> >= %.15g to <%s> %+.15g<%s> >= %.15g\n",
3311  SCIPvarGetName(consdata->var), xlb, xub, consdata->vbdcoef, SCIPvarGetName(consdata->vbdvar), consdata->lhs,
3312  SCIPvarGetName(consdata->var), consdata->vbdcoef - consdata->lhs + xlb, SCIPvarGetName(consdata->vbdvar), xlb);
3313 
3314  /* we cannot allow that the coefficient changes the sign because of the rounding locks */
3315  assert(consdata->vbdcoef * (consdata->vbdcoef - consdata->lhs + xlb) > 0);
3316 
3317  consdata->vbdcoef = consdata->vbdcoef - consdata->lhs + xlb;
3318  consdata->lhs = xlb;
3319  (*nchgcoefs)++;
3320  (*nchgsides)++;
3321  }
3322  }
3323  else if( SCIPisInfinity(scip, -consdata->lhs) && !SCIPisInfinity(scip, consdata->rhs) )
3324  {
3325  /* x + c*y <= rhs => x <= rhs - c*y */
3326  if( consdata->vbdcoef < 0.0 && SCIPisFeasLT(scip, xub, consdata->rhs - consdata->vbdcoef) )
3327  {
3328  /* constraint has positive slack for the non-restricting case y = 1
3329  * -> modify coefficients such that constraint is tight in the non-restricting case y = 1 and equivalent in the restricting case y = 0
3330  * -> c' = rhs - xub
3331  */
3332  SCIPdebugMessage("tighten binary VUB <%s>[%.15g,%.15g] %+.15g<%s> <= %.15g to <%s> %+.15g<%s> <= %.15g\n",
3333  SCIPvarGetName(consdata->var), xlb, xub, consdata->vbdcoef, SCIPvarGetName(consdata->vbdvar), consdata->rhs,
3334  SCIPvarGetName(consdata->var), consdata->rhs - xub, SCIPvarGetName(consdata->vbdvar), consdata->rhs);
3335 
3336  /* we cannot allow that the coefficient changes the sign because of the rounding locks */
3337  assert(consdata->vbdcoef * (consdata->rhs - xub) > 0);
3338 
3339  consdata->vbdcoef = consdata->rhs - xub;
3340  (*nchgcoefs)++;
3341  }
3342  else if( consdata->vbdcoef > 0.0 && SCIPisFeasLT(scip, xub, consdata->rhs) )
3343  {
3344  /* constraint has positive slack for the non-restricting case y = 0
3345  * -> modify coefficients such that constraint is tight in the non-restricting case y = 0 and equivalent in the restricting case y = 1
3346  * -> c' = c - rhs + xub, rhs' = xub
3347  */
3348  SCIPdebugMessage("tighten binary VUB <%s>[%.15g,%.15g] %+.15g<%s> <= %.15g to <%s> %+.15g<%s> <= %.15g\n",
3349  SCIPvarGetName(consdata->var), xlb, xub, consdata->vbdcoef, SCIPvarGetName(consdata->vbdvar), consdata->rhs,
3350  SCIPvarGetName(consdata->var), consdata->vbdcoef - consdata->rhs + xub, SCIPvarGetName(consdata->vbdvar), xub);
3351 
3352  /* we cannot allow that the coefficient changes the sign because of the rounding locks */
3353  assert(consdata->vbdcoef * (consdata->vbdcoef - consdata->rhs + xub) > 0);
3354 
3355  consdata->vbdcoef = consdata->vbdcoef - consdata->rhs + xub;
3356  consdata->rhs = xub;
3357  (*nchgcoefs)++;
3358  (*nchgsides)++;
3359  }
3360  }
3361 
3362  /* if something a coefficient or side of the varbound constraint was changed, ensure that the variable lower or
3363  * upper bounds of the variables are informed
3364  */
3365  if( *nchgcoefs > oldnchgcoefs || *nchgsides > oldnchgsides )
3366  {
3367  consdata->varboundsadded = FALSE;
3368  consdata->changed = TRUE;
3369  }
3370 
3371  return SCIP_OKAY;
3372 }
3373 
3374 /** check if we can upgrade to a set-packing constraint */
3375 static
3376 SCIP_RETCODE upgradeConss(
3377  SCIP* scip, /**< SCIP data structure */
3378  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
3379  SCIP_CONS** conss, /**< constraint set */
3380  int nconss, /**< number of constraints in constraint set */
3381  SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
3382  int* naggrvars, /**< pointer to count the number of aggregated variables */
3383  int* nchgbds, /**< pointer to count number of bound changes */
3384  int* nchgcoefs, /**< pointer to count the number of changed coefficients */
3385  int* nchgsides, /**< pointer to count the number of left and right hand sides */
3386  int* ndelconss, /**< pointer to count the number of deleted constraints */
3387  int* naddconss /**< pointer to count the number of added constraints */
3388  )
3389 {
3390  SCIP_VAR* vars[2];
3391  SCIP_CONS* newcons;
3392  SCIP_CONS* cons;
3393  SCIP_CONSDATA* consdata;
3394  int c;
3395 
3396  assert(scip != NULL);
3397  assert(conshdlrdata != NULL);
3398  assert(conss != NULL || nconss == 0);
3399  assert(cutoff != NULL);
3400  assert(naggrvars != NULL);
3401  assert(nchgbds != NULL);
3402  assert(nchgcoefs != NULL);
3403  assert(nchgsides != NULL);
3404  assert(ndelconss != NULL);
3405  assert(naddconss != NULL);
3406 
3407  /* if we cannot find any constraint for upgrading, stop */
3408  if( SCIPgetNBinVars(scip) + SCIPgetNImplVars(scip) <= 1 )
3409  return SCIP_OKAY;
3410 
3411  if( nconss == 0 )
3412  return SCIP_OKAY;
3413 
3414  assert(conss != NULL);
3415 
3416  for( c = nconss - 1; c >= 0; --c )
3417  {
3418  cons = conss[c];
3419  assert(cons != NULL);
3420 
3421  if( !SCIPconsIsActive(cons) )
3422  continue;
3423 
3424  consdata = SCIPconsGetData(cons);
3425  assert(consdata != NULL);
3426  assert(SCIPisLE(scip, consdata->lhs, consdata->rhs));
3427 
3428  if( !consdata->presolved )
3429  {
3430  /* incorporate fixings and aggregations in constraint */
3431  SCIP_CALL( applyFixings(scip, cons, conshdlrdata->eventhdlr, cutoff, nchgbds, ndelconss, naddconss) );
3432 
3433  if( *cutoff )
3434  return SCIP_OKAY;
3435  if( !SCIPconsIsActive(cons) )
3436  continue;
3437  }
3438 
3439  if( !consdata->propagated )
3440  {
3441  /* propagate constraint */
3442  SCIP_CALL( propagateCons(scip, cons, conshdlrdata->usebdwidening, cutoff, nchgbds, nchgsides, ndelconss) );
3443 
3444  if( *cutoff )
3445  return SCIP_OKAY;
3446  if( !SCIPconsIsActive(cons) )
3447  continue;
3448  }
3449 
3450  if( !consdata->tightened )
3451  {
3452  /* tighten variable bound coefficient */
3453  SCIP_CALL( tightenCoefs(scip, cons, nchgcoefs, nchgsides, ndelconss) );
3454 
3455  if( !SCIPconsIsActive(cons) )
3456  continue;
3457 
3458  assert(SCIPisLE(scip, consdata->lhs, consdata->rhs));
3459  }
3460 
3461  /* check if both variables are of binary type */
3462  if( SCIPvarIsBinary(consdata->vbdvar) && SCIPvarIsBinary(consdata->var) )
3463  {
3464  /* coefficient and sides should be tightened and we assume that the constraint is not redundant */
3465  assert(SCIPisEQ(scip, REALABS(consdata->vbdcoef), 1.0));
3466  assert(SCIPisZero(scip, consdata->rhs) || SCIPisEQ(scip, consdata->rhs, 1.0) || SCIPisInfinity(scip, consdata->rhs));
3467  assert(SCIPisZero(scip, consdata->lhs) || SCIPisEQ(scip, consdata->lhs, 1.0) || SCIPisInfinity(scip, -consdata->lhs));
3468  assert(!SCIPisInfinity(scip, consdata->rhs) || !SCIPisInfinity(scip, -consdata->lhs));
3469 
3470  /* the case x + y <= 1 or x + y >= 1 */
3471  if( consdata->vbdcoef > 0.0 )
3472  {
3473  if( SCIPisEQ(scip, consdata->rhs, 1.0) )
3474  {
3475  /* check for aggregations like x + y == 1 */
3476  if( SCIPisEQ(scip, consdata->lhs, 1.0) )
3477  {
3478  SCIP_Bool infeasible;
3479  SCIP_Bool redundant;
3480  SCIP_Bool aggregated;
3481 
3482  SCIPdebugMessage("varbound constraint <%s>: aggregate <%s> + <%s> == 1\n",
3483  SCIPconsGetName(cons), SCIPvarGetName(consdata->var), SCIPvarGetName(consdata->vbdvar));
3484 
3485  /* aggregate both variables */
3486  SCIP_CALL( SCIPaggregateVars(scip, consdata->var, consdata->vbdvar, 1.0, 1.0, 1.0, &infeasible, &redundant, &aggregated) );
3487  assert(!infeasible);
3488  ++(*naggrvars);
3489 
3490  SCIP_CALL( SCIPdelCons(scip, cons) );
3491  ++(*ndelconss);
3492 
3493  continue;
3494  }
3495  assert(consdata->lhs < 0.5);
3496 
3497  vars[0] = consdata->var;
3498  vars[1] = consdata->vbdvar;
3499  }
3500  else
3501  {
3502  assert(SCIPisEQ(scip, consdata->lhs, 1.0));
3503 
3504  SCIP_CALL( SCIPgetNegatedVar(scip, consdata->var, &vars[0]) );
3505  SCIP_CALL( SCIPgetNegatedVar(scip, consdata->vbdvar, &vars[1]) );
3506  }
3507  }
3508  /* the case x - y <= 0 or x - y >= 0 */
3509  else
3510  {
3511  /* the case x - y <= 0 */
3512  if( SCIPisZero(scip, consdata->rhs) )
3513  {
3514  /* check for aggregations like x - y == 0 */
3515  if( SCIPisZero(scip, consdata->lhs) )
3516  {
3517  SCIP_Bool infeasible;
3518  SCIP_Bool redundant;
3519  SCIP_Bool aggregated;
3520 
3521  SCIPdebugMessage("varbound constraint <%s>: aggregate <%s> - <%s> == 0\n",
3522  SCIPconsGetName(cons), SCIPvarGetName(consdata->var), SCIPvarGetName(consdata->vbdvar));
3523 
3524  /* aggregate both variables */
3525  SCIP_CALL( SCIPaggregateVars(scip, consdata->var, consdata->vbdvar, 1.0, -1.0, 0.0, &infeasible, &redundant, &aggregated) );
3526  assert(!infeasible);
3527  ++(*naggrvars);
3528 
3529  SCIP_CALL( SCIPdelCons(scip, cons) );
3530  ++(*ndelconss);
3531 
3532  continue;
3533  }
3534  assert(consdata->lhs < -0.5);
3535 
3536  vars[0] = consdata->var;
3537  SCIP_CALL( SCIPgetNegatedVar(scip, consdata->vbdvar, &vars[1]) );
3538  }
3539  /* the case x - y >= 0 */
3540  else
3541  {
3542  assert(SCIPisZero(scip, consdata->lhs));
3543 
3544  SCIP_CALL( SCIPgetNegatedVar(scip, consdata->var, &vars[0]) );
3545  vars[1] = consdata->vbdvar;
3546  }
3547  }
3548 
3549  SCIP_CALL( SCIPcreateConsSetpack(scip, &newcons, SCIPconsGetName(cons), 2, vars,
3550  SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
3551  SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),
3552  SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons),
3553  SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3554 
3555  SCIP_CALL( SCIPaddCons(scip, newcons) );
3556  SCIPdebugMessage("upgraded varbound constraint <%s> to a set-packing constraint\n", SCIPconsGetName(cons));
3557  SCIPdebugPrintCons(scip, newcons, NULL);
3558 
3559  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
3560  ++(*naddconss);
3561 
3562  SCIP_CALL( SCIPdelCons(scip, cons) );
3563  ++(*ndelconss);
3564  }
3565  }
3566 
3567  return SCIP_OKAY;
3568 }
3569 
3570 /**@} */
3571 
3572 
3573 /**@name Linear constraint upgrading
3574  *
3575  */
3576 
3577 /** tries to upgrade a linear constraint into a variable bound constraint */
3578 static
3579 SCIP_DECL_LINCONSUPGD(linconsUpgdVarbound)
3580 { /*lint --e{715}*/
3581  SCIP_Bool upgrade;
3582 
3583  assert(upgdcons != NULL);
3584 
3585  /* check, if linear constraint can be upgraded to a variable bound constraint lhs <= x + a*y <= rhs
3586  * - there are exactly two variables
3587  * - one of the variables is non-binary (called the bounded variable x)
3588  * - one of the variables is non-continuous (called the bounding variable y)
3589  */
3590  upgrade = (nvars == 2) && (nposbin + nnegbin <= 1) && (nposcont + nnegcont <= 1);
3591 
3592  if( upgrade )
3593  {
3594  SCIP_VAR* var;
3595  SCIP_VAR* vbdvar;
3596  SCIP_Real vbdcoef;
3597  SCIP_Real vbdlhs;
3598  SCIP_Real vbdrhs;
3599  int vbdind;
3600 
3601  SCIPdebugMessage("upgrading constraint <%s> to variable bound constraint\n", SCIPconsGetName(cons));
3602 
3603  /* decide which variable we want to use as bounding variable y */
3604  if( SCIPvarGetType(vars[0]) < SCIPvarGetType(vars[1]) )
3605  vbdind = 0;
3606  else if( SCIPvarGetType(vars[0]) > SCIPvarGetType(vars[1]) )
3607  vbdind = 1;
3608  else if( SCIPisIntegral(scip, vals[0]) && !SCIPisIntegral(scip, vals[1]) )
3609  vbdind = 0;
3610  else if( !SCIPisIntegral(scip, vals[0]) && SCIPisIntegral(scip, vals[1]) )
3611  vbdind = 1;
3612  else if( REALABS(REALABS(vals[0]) - 1.0) < REALABS(REALABS(vals[1]) - 1.0) )
3613  vbdind = 1;
3614  else
3615  vbdind = 0;
3616 
3617  var = vars[1-vbdind];
3618  vbdvar = vars[vbdind];
3619 
3620  assert(!SCIPisZero(scip, vals[1-vbdind]));
3621  vbdcoef = vals[vbdind]/vals[1-vbdind];
3622 
3623  if( vals[1-vbdind] > 0.0 )
3624  {
3625  vbdlhs = SCIPisInfinity(scip, -lhs) ? -SCIPinfinity(scip) : lhs/vals[1-vbdind];
3626  vbdrhs = SCIPisInfinity(scip, rhs) ? SCIPinfinity(scip) : rhs/vals[1-vbdind];
3627  }
3628  else
3629  {
3630  vbdlhs = SCIPisInfinity(scip, rhs) ? -SCIPinfinity(scip) : rhs/vals[1-vbdind];
3631  vbdrhs = SCIPisInfinity(scip, -lhs) ? SCIPinfinity(scip) : lhs/vals[1-vbdind];
3632  }
3633 
3634  /* create the bin variable bound constraint (an automatically upgraded constraint is always unmodifiable) */
3635  assert(!SCIPconsIsModifiable(cons));
3636  SCIP_CALL( SCIPcreateConsVarbound(scip, upgdcons, SCIPconsGetName(cons), var, vbdvar, vbdcoef, vbdlhs, vbdrhs,
3637  SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
3638  SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),
3639  SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons),
3640  SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3641  }
3642 
3643  return SCIP_OKAY;
3644 }
3645 
3646 /**@} */
3647 
3648 
3649 /**@name Callback methods
3650  *
3651  * @{
3652  */
3653 
3654 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
3655 static
3656 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyVarbound)
3657 { /*lint --e{715}*/
3658  assert(scip != NULL);
3659  assert(conshdlr != NULL);
3660  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
3661 
3662  /* call inclusion method of constraint handler */
3663  SCIP_CALL( SCIPincludeConshdlrVarbound(scip) );
3664 
3665  *valid = TRUE;
3666 
3667  return SCIP_OKAY;
3668 }
3669 
3670 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
3671 static
3672 SCIP_DECL_CONSFREE(consFreeVarbound)
3673 { /*lint --e{715}*/
3674  SCIP_CONSHDLRDATA* conshdlrdata;
3675 
3676  assert(scip != NULL);
3677  assert(conshdlr != NULL);
3678  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
3679 
3680  /* free constraint handler data */
3681  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3682  assert(conshdlrdata != NULL);
3683 
3684  conshdlrdataFree(scip, &conshdlrdata);
3685 
3686  SCIPconshdlrSetData(conshdlr, NULL);
3687 
3688  return SCIP_OKAY;
3689 }
3690 
3691 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
3692 static
3693 SCIP_DECL_CONSEXITSOL(consExitsolVarbound)
3694 { /*lint --e{715}*/
3695  SCIP_CONSDATA* consdata;
3696  int c;
3697 
3698  /* release the rows of all constraints */
3699  for( c = 0; c < nconss; ++c )
3700  {
3701  consdata = SCIPconsGetData(conss[c]);
3702  assert(consdata != NULL);
3703 
3704  if( consdata->row != NULL )
3705  {
3706  SCIP_CALL( SCIPreleaseRow(scip, &consdata->row) );
3707  }
3708  }
3709 
3710  return SCIP_OKAY;
3711 }
3712 
3713 
3714 /** frees specific constraint data */
3715 static
3716 SCIP_DECL_CONSDELETE(consDeleteVarbound)
3717 { /*lint --e{715}*/
3718  SCIP_CONSHDLRDATA* conshdlrdata;
3719 
3720  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3721  assert(conshdlrdata != NULL);
3722 
3723  /* drop events */
3724  if( SCIPisTransformed(scip) )
3725  {
3726  SCIP_CALL( dropEvents(scip, cons, conshdlrdata->eventhdlr) );
3727  }
3728 
3729  SCIP_CALL( consdataFree(scip, consdata) );
3730 
3731  return SCIP_OKAY;
3732 }
3733 
3734 
3735 /** transforms constraint data into data belonging to the transformed problem */
3736 static
3737 SCIP_DECL_CONSTRANS(consTransVarbound)
3738 { /*lint --e{715}*/
3739  SCIP_CONSHDLRDATA* conshdlrdata;
3740  SCIP_CONSDATA* sourcedata;
3741  SCIP_CONSDATA* targetdata;
3742 
3743  assert(conshdlr != NULL);
3744 
3745  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3746  assert(conshdlrdata != NULL);
3747 
3748  sourcedata = SCIPconsGetData(sourcecons);
3749  assert(sourcedata != NULL);
3750 
3751  /* create target constraint data */
3752  SCIP_CALL( consdataCreate(scip, &targetdata,
3753  sourcedata->var, sourcedata->vbdvar, sourcedata->vbdcoef, sourcedata->lhs, sourcedata->rhs) );
3754 
3755  /* create target constraint */
3756  SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
3757  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
3758  SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
3759  SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
3760  SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
3761 
3762  /* catch events for variables */
3763  SCIP_CALL( catchEvents(scip, *targetcons, conshdlrdata->eventhdlr) );
3764 
3765  return SCIP_OKAY;
3766 }
3767 
3768 
3769 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
3770 static
3771 SCIP_DECL_CONSINITLP(consInitlpVarbound)
3772 { /*lint --e{715}*/
3773  int i;
3774 
3775  for( i = 0; i < nconss; i++ )
3776  {
3777  assert(SCIPconsIsInitial(conss[i]));
3778  SCIP_CALL( addRelaxation(scip, conss[i]) );
3779  }
3780 
3781  return SCIP_OKAY;
3782 }
3783 
3784 
3785 /** separation method of constraint handler for LP solutions */
3786 static
3787 SCIP_DECL_CONSSEPALP(consSepalpVarbound)
3788 { /*lint --e{715}*/
3789  SCIP_CONSHDLRDATA* conshdlrdata;
3790  int i;
3791 
3792  assert(conshdlr != NULL);
3793 
3794  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3795  assert(conshdlrdata != NULL);
3796 
3797  *result = SCIP_DIDNOTFIND;
3798 
3799  /* separate useful constraints */
3800  for( i = 0; i < nusefulconss; ++i )
3801  {
3802  SCIP_CALL( separateCons(scip, conss[i], conshdlrdata->usebdwidening, NULL, result) );
3803  }
3804 
3805  /* separate remaining constraints */
3806  for( i = nusefulconss; i < nconss && *result == SCIP_DIDNOTFIND; ++i )
3807  {
3808  SCIP_CALL( separateCons(scip, conss[i], conshdlrdata->usebdwidening, NULL, result) );
3809  }
3810 
3811  return SCIP_OKAY;
3812 }
3813 
3814 
3815 /** separation method of constraint handler for arbitrary primal solutions */
3816 static
3817 SCIP_DECL_CONSSEPASOL(consSepasolVarbound)
3818 { /*lint --e{715}*/
3819  SCIP_CONSHDLRDATA* conshdlrdata;
3820  int i;
3821 
3822  assert(conshdlr != NULL);
3823 
3824  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3825  assert(conshdlrdata != NULL);
3826 
3827  *result = SCIP_DIDNOTFIND;
3828 
3829  /* separate useful constraints */
3830  for( i = 0; i < nusefulconss; ++i )
3831  {
3832  SCIP_CALL( separateCons(scip, conss[i], conshdlrdata->usebdwidening, sol, result) );
3833  }
3834 
3835  /* separate remaining constraints */
3836  for( i = nusefulconss; i < nconss && *result == SCIP_DIDNOTFIND; ++i )
3837  {
3838  SCIP_CALL( separateCons(scip, conss[i], conshdlrdata->usebdwidening, sol, result) );
3839  }
3840 
3841  return SCIP_OKAY;
3842 }
3843 
3844 
3845 /** constraint enforcing method of constraint handler for LP solutions */
3846 static
3847 SCIP_DECL_CONSENFOLP(consEnfolpVarbound)
3848 { /*lint --e{715}*/
3849  SCIP_CONSHDLRDATA* conshdlrdata;
3850  int i;
3851 
3852  assert(conshdlr != NULL);
3853 
3854  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3855  assert(conshdlrdata != NULL);
3856 
3857  *result = SCIP_FEASIBLE;
3858 
3859  for( i = 0; i < nconss; i++ )
3860  {
3861  if( !checkCons(scip, conss[i], NULL, FALSE) )
3862  {
3863  assert((*result) == SCIP_INFEASIBLE || (*result) == SCIP_FEASIBLE);
3864  (*result) = SCIP_INFEASIBLE;
3865 
3866  SCIP_CALL( SCIPresetConsAge(scip, conss[i]) );
3867 
3868  SCIP_CALL( separateCons(scip, conss[i], conshdlrdata->usebdwidening, NULL, result) );
3869  assert((*result) != SCIP_FEASIBLE);
3870 
3871  if( (*result) != SCIP_INFEASIBLE )
3872  break;
3873  }
3874  else
3875  {
3876  /* increase age of constraint */
3877  SCIP_CALL( SCIPincConsAge(scip, conss[i]) );
3878  }
3879  }
3880 
3881  return SCIP_OKAY;
3882 }
3883 
3884 
3885 /** constraint enforcing method of constraint handler for pseudo solutions */
3886 static
3887 SCIP_DECL_CONSENFOPS(consEnfopsVarbound)
3888 { /*lint --e{715}*/
3889  int i;
3890 
3891  for( i = 0; i < nconss; i++ )
3892  {
3893  if( !checkCons(scip, conss[i], NULL, TRUE) )
3894  {
3895  SCIP_CALL( SCIPresetConsAge(scip, conss[i]) );
3896 
3897  *result = SCIP_INFEASIBLE;
3898  return SCIP_OKAY;
3899  }
3900  else
3901  {
3902  /* increase age of constraint */
3903  SCIP_CALL( SCIPincConsAge(scip, conss[i]) );
3904  }
3905  }
3906  *result = SCIP_FEASIBLE;
3907 
3908  return SCIP_OKAY;
3909 }
3910 
3911 
3912 /** feasibility check method of constraint handler for integral solutions */
3913 static
3914 SCIP_DECL_CONSCHECK(consCheckVarbound)
3915 { /*lint --e{715}*/
3916  int i;
3917 
3918  for( i = 0; i < nconss; i++ )
3919  {
3920  if( !checkCons(scip, conss[i], sol, checklprows) )
3921  {
3922  *result = SCIP_INFEASIBLE;
3923 
3924  if( printreason )
3925  {
3926  SCIP_CONSDATA* consdata;
3927  SCIP_Real sum;
3928 
3929  consdata = SCIPconsGetData(conss[i]);
3930  assert( consdata != NULL );
3931 
3932  sum = SCIPgetSolVal(scip, sol, consdata->var) + consdata->vbdcoef * SCIPgetSolVal(scip, sol, consdata->vbdvar);
3933 
3934  SCIP_CALL( SCIPprintCons(scip, conss[i], NULL) );
3935  SCIPinfoMessage(scip, NULL, ";\n");
3936 
3937  if( !SCIPisFeasGE(scip, sum, consdata->lhs) )
3938  {
3939  SCIPinfoMessage(scip, NULL, "violation: left hand side is violated by %.15g\n", consdata->lhs - sum);
3940  }
3941  if( !SCIPisFeasLE(scip, sum, consdata->rhs) )
3942  {
3943  SCIPinfoMessage(scip, NULL, "violation: right hand side is violated by %.15g\n", sum - consdata->rhs);
3944  }
3945  }
3946  return SCIP_OKAY;
3947  }
3948  }
3949  *result = SCIP_FEASIBLE;
3950 
3951  return SCIP_OKAY;
3952 }
3953 
3954 
3955 /** domain propagation method of constraint handler */
3956 static
3957 SCIP_DECL_CONSPROP(consPropVarbound)
3958 { /*lint --e{715}*/
3959  SCIP_CONSHDLRDATA* conshdlrdata;
3960  SCIP_Bool cutoff;
3961  int nchgbds;
3962  int nchgsides;
3963  int i;
3964 
3965  assert(conshdlr != NULL);
3966 
3967  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3968  assert(conshdlrdata != NULL);
3969 
3970  cutoff = FALSE;
3971  nchgbds = 0;
3972 
3973  /* process constraints marked for propagation */
3974  for( i = 0; i < nmarkedconss && !cutoff; i++ )
3975  {
3976  SCIP_CALL( propagateCons(scip, conss[i], conshdlrdata->usebdwidening, &cutoff, &nchgbds, &nchgsides, NULL) );
3977  SCIP_CALL( SCIPunmarkConsPropagate(scip, conss[i]) );
3978  }
3979 
3980  if( cutoff )
3981  *result = SCIP_CUTOFF;
3982  else if( nchgbds > 0 )
3983  *result = SCIP_REDUCEDDOM;
3984  else
3985  *result = SCIP_DIDNOTFIND;
3986 
3987  return SCIP_OKAY;
3988 }
3989 
3990 
3991 /** presolving method of constraint handler */
3992 static
3993 SCIP_DECL_CONSPRESOL(consPresolVarbound)
3994 { /*lint --e{715}*/
3995  SCIP_CONSHDLRDATA* conshdlrdata;
3996  SCIP_CONS* cons;
3997  SCIP_CONSDATA* consdata;
3998  SCIP_Bool cutoff;
3999  int oldnchgbds;
4000  int oldndelconss;
4001  int oldnaddconss;
4002  int oldnchgcoefs;
4003  int oldnchgsides;
4004  int oldnaggrvars;
4005  int i;
4006 
4007  assert(scip != NULL);
4008  assert(conshdlr != NULL);
4009  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4010  assert(result != NULL);
4011 
4012  /* get constraint handler data */
4013  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4014  assert(conshdlrdata != NULL);
4015 
4016  cutoff = FALSE;
4017  oldnchgbds = *nchgbds;
4018  oldndelconss = *ndelconss;
4019  oldnaddconss = *naddconss;
4020  oldnchgcoefs = *nchgcoefs;
4021  oldnchgsides = *nchgsides;
4022  oldnaggrvars = *naggrvars;
4023 
4024  for( i = 0; i < nconss; i++ )
4025  {
4026  cons = conss[i];
4027  assert(cons != NULL);
4028 
4029  assert(!SCIPconsIsModifiable(cons));
4030 
4031  consdata = SCIPconsGetData(cons);
4032  assert(consdata != NULL);
4033 
4034  if( i % 1000 == 0 && SCIPisStopped(scip) )
4035  break;
4036 
4037  /* force presolving the constraint in the initial round */
4038  if( nrounds == 0 )
4039  consdata->presolved = FALSE;
4040 
4041  if( consdata->presolved )
4042  continue;
4043  consdata->presolved = TRUE;
4044 
4045  /* make sure that the constraint is propagated */
4046  consdata->propagated = FALSE;
4047 
4048  /* incorporate fixings and aggregations in constraint */
4049  SCIP_CALL( applyFixings(scip, cons, conshdlrdata->eventhdlr, &cutoff, nchgbds, ndelconss, naddconss) );
4050 
4051  if( cutoff )
4052  break;
4053  if( !SCIPconsIsActive(cons) )
4054  continue;
4055 
4056  /* propagate constraint */
4057  SCIP_CALL( propagateCons(scip, cons, conshdlrdata->usebdwidening, &cutoff, nchgbds, nchgsides, ndelconss) );
4058 
4059  if( cutoff )
4060  break;
4061  if( !SCIPconsIsActive(cons) )
4062  continue;
4063 
4064  /* tighten variable bound coefficient */
4065  SCIP_CALL( tightenCoefs(scip, cons, nchgcoefs, nchgsides, ndelconss) );
4066  if( !SCIPconsIsActive(cons) )
4067  continue;
4068 
4069  /* informs once variable x about a globally valid variable lower or upper bound */
4070  if( !consdata->varboundsadded )
4071  {
4072  SCIP_Bool infeasible;
4073  int nlocalchgbds;
4074  int localoldnchgbds;
4075 
4076  localoldnchgbds = *nchgbds;
4077 
4078  /* if lhs is finite, we have a variable lower bound: lhs <= x + c*y => x >= -c*y + lhs */
4079  if( !SCIPisInfinity(scip, -consdata->lhs) )
4080  {
4081  SCIPdebugMessage("adding variable lower bound <%s> >= %g<%s> + %g (and potentially also <%s> %s %g<%s> + %g)\n",
4082  SCIPvarGetName(consdata->var), -consdata->vbdcoef, SCIPvarGetName(consdata->vbdvar), consdata->lhs,
4083  SCIPvarGetName(consdata->vbdvar), (consdata->vbdcoef > 0 ? ">=" : "<="), 1.0/-consdata->vbdcoef,
4084  SCIPvarGetName(consdata->var), consdata->lhs/consdata->vbdcoef);
4085 
4086  SCIP_CALL( SCIPaddVarVlb(scip, consdata->var, consdata->vbdvar, -consdata->vbdcoef, consdata->lhs,
4087  &infeasible, &nlocalchgbds) );
4088  assert(!infeasible);
4089 
4090  *nchgbds += nlocalchgbds;
4091  }
4092 
4093  /* if rhs is finite, we have a variable upper bound: x + c*y <= rhs => x <= -c*y + rhs */
4094  if( !SCIPisInfinity(scip, consdata->rhs) )
4095  {
4096  SCIPdebugMessage("adding variable upper bound <%s> <= %g<%s> + %g (and potentially also <%s> %s %g<%s> + %g)\n",
4097  SCIPvarGetName(consdata->var), -consdata->vbdcoef, SCIPvarGetName(consdata->vbdvar), consdata->rhs,
4098  SCIPvarGetName(consdata->vbdvar), (consdata->vbdcoef > 0 ? "<=" : ">="), 1.0/-consdata->vbdcoef,
4099  SCIPvarGetName(consdata->var), consdata->rhs/consdata->vbdcoef);
4100 
4101  SCIP_CALL( SCIPaddVarVub(scip, consdata->var, consdata->vbdvar, -consdata->vbdcoef, consdata->rhs,
4102  &infeasible, &nlocalchgbds) );
4103  assert(!infeasible);
4104 
4105  *nchgbds += nlocalchgbds;
4106  }
4107  consdata->varboundsadded = TRUE;
4108 
4109  if( *nchgbds > localoldnchgbds )
4110  {
4111  /* tighten variable bound coefficient */
4112  SCIP_CALL( tightenCoefs(scip, cons, nchgcoefs, nchgsides, ndelconss) );
4113  }
4114  }
4115  }
4116 
4117  if( !cutoff )
4118  {
4119  /* for varbound constraint with two integer variables make coefficients integral */
4120  SCIP_CALL( prettifyConss(scip, conss, nconss, nchgcoefs, nchgsides) );
4121 
4122  /* check if we can upgrade to a set-packing constraint */
4123  SCIP_CALL( upgradeConss(scip, conshdlrdata, conss, nconss, &cutoff, naggrvars, nchgbds, nchgcoefs, nchgsides, ndelconss, naddconss) );
4124 
4125  if( !cutoff && conshdlrdata->presolpairwise && (presoltiming & SCIP_PRESOLTIMING_MEDIUM) != 0 )
4126  {
4127  /* preprocess pairs of variable bound constraints */
4128  SCIP_CALL( preprocessConstraintPairs(scip, conss, nconss, &cutoff, nchgbds, ndelconss, nchgcoefs, nchgsides) );
4129  }
4130  }
4131 
4132  /* return the correct result code */
4133  if( cutoff )
4134  *result = SCIP_CUTOFF;
4135  else if( *nchgbds > oldnchgbds || *ndelconss > oldndelconss || *naddconss > oldnaddconss
4136  || *nchgcoefs > oldnchgcoefs || *nchgsides > oldnchgsides || *naggrvars > oldnaggrvars )
4137  *result = SCIP_SUCCESS;
4138  else
4139  *result = SCIP_DIDNOTFIND;
4140 
4141  return SCIP_OKAY;
4142 }
4143 
4144 
4145 /** propagation conflict resolving method of constraint handler */
4146 static
4147 SCIP_DECL_CONSRESPROP(consRespropVarbound)
4148 { /*lint --e{715}*/
4149  SCIP_CONSHDLRDATA* conshdlrdata;
4150 
4151  assert(conshdlr != NULL);
4152 
4153  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4154  assert(conshdlrdata != NULL);
4155 
4156  SCIP_CALL( resolvePropagation(scip, cons, infervar, (PROPRULE)inferinfo, boundtype, bdchgidx, relaxedbd, conshdlrdata->usebdwidening) );
4157 
4158  *result = SCIP_SUCCESS;
4159 
4160  return SCIP_OKAY;
4161 }
4162 
4163 
4164 /** variable rounding lock method of constraint handler */
4165 static
4166 SCIP_DECL_CONSLOCK(consLockVarbound)
4167 { /*lint --e{715}*/
4168  SCIP_CONSDATA* consdata;
4169 
4170  consdata = SCIPconsGetData(cons);
4171  assert(consdata != NULL);
4172 
4173  if( !SCIPisInfinity(scip, -consdata->lhs) )
4174  {
4175  SCIP_CALL( SCIPaddVarLocks(scip, consdata->var, nlockspos, nlocksneg) );
4176  if( consdata->vbdcoef > 0.0 )
4177  {
4178  SCIP_CALL( SCIPaddVarLocks(scip, consdata->vbdvar, nlockspos, nlocksneg) );
4179  }
4180  else
4181  {
4182  SCIP_CALL( SCIPaddVarLocks(scip, consdata->vbdvar, nlocksneg, nlockspos) );
4183  }
4184  }
4185 
4186  if( !SCIPisInfinity(scip, consdata->rhs) )
4187  {
4188  SCIP_CALL( SCIPaddVarLocks(scip, consdata->var, nlocksneg, nlockspos) );
4189  if( consdata->vbdcoef > 0.0 )
4190  {
4191  SCIP_CALL( SCIPaddVarLocks(scip, consdata->vbdvar, nlocksneg, nlockspos) );
4192  }
4193  else
4194  {
4195  SCIP_CALL( SCIPaddVarLocks(scip, consdata->vbdvar, nlockspos, nlocksneg) );
4196  }
4197  }
4198 
4199  return SCIP_OKAY;
4200 }
4201 
4202 /** constraint display method of constraint handler */
4203 static
4204 SCIP_DECL_CONSPRINT(consPrintVarbound)
4205 { /*lint --e{715}*/
4206  SCIP_CONSDATA* consdata;
4207 
4208  assert(scip != NULL);
4209  assert(conshdlr != NULL);
4210  assert(cons != NULL);
4211 
4212  consdata = SCIPconsGetData(cons);
4213  assert(consdata != NULL);
4214 
4215  /* print left hand side for ranged rows */
4216  if( !SCIPisInfinity(scip, -consdata->lhs)
4217  && !SCIPisInfinity(scip, consdata->rhs)
4218  && !SCIPisEQ(scip, consdata->lhs, consdata->rhs) )
4219  SCIPinfoMessage(scip, file, "%.15g <= ", consdata->lhs);
4220 
4221  /* print coefficients and variables */
4222  SCIPinfoMessage(scip, file, "<%s>[%c] %+.15g<%s>[%c]", SCIPvarGetName(consdata->var),
4223  SCIPvarGetType(consdata->var) == SCIP_VARTYPE_BINARY ? SCIP_VARTYPE_BINARY_CHAR :
4224  SCIPvarGetType(consdata->var) == SCIP_VARTYPE_INTEGER ? SCIP_VARTYPE_INTEGER_CHAR :
4225  SCIPvarGetType(consdata->var) == SCIP_VARTYPE_IMPLINT ? SCIP_VARTYPE_IMPLINT_CHAR : SCIP_VARTYPE_CONTINUOUS_CHAR,
4226  consdata->vbdcoef, SCIPvarGetName(consdata->vbdvar),
4227  SCIPvarGetType(consdata->vbdvar) == SCIP_VARTYPE_BINARY ? SCIP_VARTYPE_BINARY_CHAR :
4228  SCIPvarGetType(consdata->vbdvar) == SCIP_VARTYPE_INTEGER ? SCIP_VARTYPE_INTEGER_CHAR :
4229  SCIPvarGetType(consdata->vbdvar) == SCIP_VARTYPE_IMPLINT ? SCIP_VARTYPE_IMPLINT_CHAR : SCIP_VARTYPE_CONTINUOUS_CHAR);
4230 
4231  /* print right hand side */
4232  if( SCIPisEQ(scip, consdata->lhs, consdata->rhs) )
4233  SCIPinfoMessage(scip, file, " == %.15g", consdata->rhs);
4234  else if( !SCIPisInfinity(scip, consdata->rhs) )
4235  SCIPinfoMessage(scip, file, " <= %.15g", consdata->rhs);
4236  else if( !SCIPisInfinity(scip, -consdata->lhs) )
4237  SCIPinfoMessage(scip, file, " >= %.15g", consdata->lhs);
4238  else
4239  SCIPinfoMessage(scip, file, " [free]");
4240 
4241  return SCIP_OKAY;
4242 }
4243 
4244 /** constraint copying method of constraint handler */
4245 static
4246 SCIP_DECL_CONSCOPY(consCopyVarbound)
4247 { /*lint --e{715}*/
4248  SCIP_VAR** vars;
4249  SCIP_Real* coefs;
4250  const char* consname;
4251 
4252  SCIP_CALL( SCIPallocBufferArray(scip, &vars, 2) );
4253  SCIP_CALL( SCIPallocBufferArray(scip, &coefs, 2) );
4254 
4255  vars[0] = SCIPgetVarVarbound(sourcescip, sourcecons);
4256  vars[1] = SCIPgetVbdvarVarbound(sourcescip, sourcecons);
4257 
4258  coefs[0] = 1.0;
4259  coefs[1] = SCIPgetVbdcoefVarbound(sourcescip, sourcecons);
4260 
4261  if( name != NULL )
4262  consname = name;
4263  else
4264  consname = SCIPconsGetName(sourcecons);
4265 
4266  /* copy the varbound using the linear constraint copy method */
4267  SCIP_CALL( SCIPcopyConsLinear(scip, cons, sourcescip, consname, 2, vars, coefs,
4268  SCIPgetLhsVarbound(sourcescip, sourcecons), SCIPgetRhsVarbound(sourcescip, sourcecons), varmap, consmap,
4269  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode, global, valid) );
4270 
4271  SCIPfreeBufferArray(scip, &coefs);
4272  SCIPfreeBufferArray(scip, &vars);
4273 
4274  return SCIP_OKAY;
4275 }
4276 
4277 /** constraint parsing method of constraint handler */
4278 static
4279 SCIP_DECL_CONSPARSE(consParseVarbound)
4280 { /*lint --e{715}*/
4281  SCIP_VAR** vars;
4282  SCIP_Real* coefs;
4283  SCIP_Real lhs;
4284  SCIP_Real rhs;
4285  char* endstr;
4286  int requiredsize;
4287  int nvars;
4288 
4289  assert(scip != NULL);
4290  assert(success != NULL);
4291  assert(str != NULL);
4292  assert(name != NULL);
4293  assert(cons != NULL);
4294 
4295  /* set left and right hand side to their default values */
4296  lhs = -SCIPinfinity(scip);
4297  rhs = SCIPinfinity(scip);
4298 
4299  (*success) = FALSE;
4300 
4301  /* return of string empty */
4302  if( !*str )
4303  return SCIP_OKAY;
4304 
4305  /* ignore whitespace */
4306  while( isspace(*str) )
4307  ++str;
4308 
4309  if( isdigit(str[0]) || ((str[0] == '-' || str[0] == '+') && isdigit(str[1])) )
4310  {
4311  if( !SCIPstrToRealValue(str, &lhs, &endstr) )
4312  {
4313  SCIPerrorMessage("error parsing left hand side\n");
4314  return SCIP_OKAY;
4315  }
4316 
4317  /* ignore whitespace */
4318  while( isspace(*endstr) )
4319  ++endstr;
4320 
4321  if( endstr[0] != '<' || endstr[1] != '=' )
4322  {
4323  SCIPerrorMessage("missing \"<=\" after left hand side(, found %c%c)\n", endstr[0], endstr[1]);
4324  return SCIP_OKAY;
4325  }
4326 
4327  SCIPdebugMessage("found left hand side <%g>\n", lhs);
4328 
4329  /* it was indeed a left-hand-side, so continue parsing after it */
4330  str = endstr + 2;
4331  }
4332 
4333  /* pares x + c*y as linear sum */
4334  SCIP_CALL( SCIPallocBufferArray(scip, &vars, 2) );
4335  SCIP_CALL( SCIPallocBufferArray(scip, &coefs, 2) );
4336 
4337  /* parse linear sum to get variables and coefficients */
4338  SCIP_CALL( SCIPparseVarsLinearsum(scip, str, vars, coefs, &nvars, 2, &requiredsize, &endstr, success) );
4339 
4340  if( requiredsize == 2 && *success )
4341  {
4342  SCIP_Bool foundvalue;
4343  SCIP_Real value;
4344 
4345  assert(nvars == 2);
4346  assert(SCIPisEQ(scip, coefs[0], 1.0));
4347 
4348  SCIPdebugMessage("found linear sum <%s> + %g <%s>\n", SCIPvarGetName(vars[0]), coefs[1], SCIPvarGetName(vars[1]));
4349 
4350  /* ignore whitespace */
4351  while( isspace(*endstr) )
4352  ++endstr;
4353 
4354  str = endstr;
4355 
4356  foundvalue = SCIPstrToRealValue(str+2, &value, &endstr);
4357 
4358  if( foundvalue )
4359  {
4360  /* search for end of linear sum: either '<=', '>=', '==', or '[free]' */
4361  switch( *str )
4362  {
4363  case '<':
4364  assert(str[1] == '=');
4365  rhs = value;
4366  break;
4367  case '=':
4368  assert(str[1] == '=');
4369  assert(SCIPisInfinity(scip, -lhs));
4370  lhs = value;
4371  rhs = value;
4372  break;
4373  case '>':
4374  assert(str[1] == '=');
4375  assert(SCIPisInfinity(scip, -lhs));
4376  lhs = value;
4377  break;
4378  default:
4379  SCIPerrorMessage("missing relation symbol after linear sum\n");
4380  *success = FALSE;
4381  }
4382  }
4383  else if( strncmp(str, "[free]", 6) != 0 )
4384  *success = FALSE;
4385  }
4386 
4387  if( *success )
4388  {
4389  SCIP_CALL( SCIPcreateConsVarbound(scip, cons, name, vars[0], vars[1], coefs[1], lhs, rhs,
4390  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
4391  }
4392 
4393  /* free buffer arrays */
4394  SCIPfreeBufferArray(scip, &coefs);
4395  SCIPfreeBufferArray(scip, &vars);
4396 
4397  return SCIP_OKAY;
4398 }
4399 
4400 /** constraint method of constraint handler which returns the variables (if possible) */
4401 static
4402 SCIP_DECL_CONSGETVARS(consGetVarsVarbound)
4403 { /*lint --e{715}*/
4404 
4405  if( varssize < 2 )
4406  (*success) = FALSE;
4407  else
4408  {
4409  SCIP_CONSDATA* consdata;
4410  assert(cons != NULL);
4411  assert(vars != NULL);
4412 
4413  consdata = SCIPconsGetData(cons);
4414  assert(consdata != NULL);
4415 
4416  vars[0] = consdata->var;
4417  vars[1] = consdata->vbdvar;
4418  (*success) = TRUE;
4419  }
4420 
4421  return SCIP_OKAY;
4422 }
4423 
4424 /** constraint method of constraint handler which returns the number of variables (if possible) */
4425 static
4426 SCIP_DECL_CONSGETNVARS(consGetNVarsVarbound)
4427 { /*lint --e{715}*/
4428  (*nvars) = 2;
4429  (*success) = TRUE;
4430 
4431  return SCIP_OKAY;
4432 }
4433 
4434 /*
4435  * Event Handler
4436  */
4437 
4438 /** execution method of bound change event handler */
4439 static
4440 SCIP_DECL_EVENTEXEC(eventExecVarbound)
4441 { /*lint --e{715}*/
4442  SCIP_CONS* cons;
4443  SCIP_CONSDATA* consdata;
4444 
4445  assert(event != NULL);
4446  cons = (SCIP_CONS*)eventdata;
4447  assert(cons != NULL);
4448  consdata = SCIPconsGetData(cons);
4449  assert(consdata != NULL);
4450 
4451  if( SCIPeventGetType(event) == SCIP_EVENTTYPE_VARFIXED )
4452  {
4453  consdata->presolved = FALSE;
4454  }
4455  else
4456  {
4457  assert((SCIPeventGetType(event) & SCIP_EVENTTYPE_BOUNDTIGHTENED) != 0);
4458 
4459  consdata->propagated = FALSE;
4460  consdata->presolved = FALSE;
4461  consdata->tightened = FALSE;
4462 
4463  SCIP_CALL( SCIPmarkConsPropagate(scip, cons) );
4464  }
4465 
4466  return SCIP_OKAY;
4467 }
4468 
4469 /**@} */
4470 
4471 
4472 /**@name Interface methods
4473  *
4474  * @{
4475  */
4476 
4477 /** creates the handler for variable bound constraints and includes it in SCIP */
4478 SCIP_RETCODE SCIPincludeConshdlrVarbound(
4479  SCIP* scip /**< SCIP data structure */
4480  )
4481 {
4482  SCIP_CONSHDLRDATA* conshdlrdata;
4483  SCIP_EVENTHDLR* eventhdlr;
4484  SCIP_CONSHDLR* conshdlr;
4485 
4486  /* include event handler for bound change events */
4487  SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
4488  eventExecVarbound, NULL) );
4489 
4490  /* create variable bound constraint handler data */
4491  SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlr) );
4492 
4493  /* include constraint handler */
4494  SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC,
4495  CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS,
4496  consEnfolpVarbound, consEnfopsVarbound, consCheckVarbound, consLockVarbound,
4497  conshdlrdata) );
4498  assert(conshdlr != NULL);
4499 
4500  /* set non-fundamental callbacks via specific setter functions */
4501  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyVarbound, consCopyVarbound) );
4502  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteVarbound) );
4503  SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolVarbound) );
4504  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeVarbound) );
4505  SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsVarbound) );
4506  SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsVarbound) );
4507  SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpVarbound) );
4508  SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseVarbound) );
4509  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolVarbound, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
4510  SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintVarbound) );
4511  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropVarbound, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
4512  CONSHDLR_PROP_TIMING) );
4513  SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropVarbound) );
4514  SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpVarbound, consSepasolVarbound, CONSHDLR_SEPAFREQ,
4515  CONSHDLR_SEPAPRIORITY, CONSHDLR_DELAYSEPA) );
4516  SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransVarbound) );
4517 
4518  if( SCIPfindConshdlr(scip,"linear") != NULL )
4519  {
4520  /* include the linear constraint to varbound constraint upgrade in the linear constraint handler */
4521  SCIP_CALL( SCIPincludeLinconsUpgrade(scip, linconsUpgdVarbound, LINCONSUPGD_PRIORITY, CONSHDLR_NAME) );
4522  }
4523 
4524  /* add varbound constraint handler parameters */
4525  SCIP_CALL( SCIPaddBoolParam(scip,
4526  "constraints/" CONSHDLR_NAME "/presolpairwise",
4527  "should pairwise constraint comparison be performed in presolving?",
4528  &conshdlrdata->presolpairwise, TRUE, DEFAULT_PRESOLPAIRWISE, NULL, NULL) );
4529  SCIP_CALL( SCIPaddRealParam(scip,
4530  "constraints/" CONSHDLR_NAME "/maxlpcoef",
4531  "maximum coefficient in varbound constraint to be added as a row into LP",
4532  &conshdlrdata->maxlpcoef, TRUE, DEFAULT_MAXLPCOEF, 0.0, 1e+20, NULL, NULL) );
4533  SCIP_CALL( SCIPaddBoolParam(scip,
4534  "constraints/" CONSHDLR_NAME "/usebdwidening", "should bound widening be used in conflict analysis?",
4535  &conshdlrdata->usebdwidening, FALSE, DEFAULT_USEBDWIDENING, NULL, NULL) );
4536 
4537  return SCIP_OKAY;
4538 }
4539 
4540 /** creates and captures a variable bound constraint: lhs <= x + c*y <= rhs
4541  *
4542  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
4543  */
4544 SCIP_RETCODE SCIPcreateConsVarbound(
4545  SCIP* scip, /**< SCIP data structure */
4546  SCIP_CONS** cons, /**< pointer to hold the created constraint */
4547  const char* name, /**< name of constraint */
4548  SCIP_VAR* var, /**< variable x that has variable bound */
4549  SCIP_VAR* vbdvar, /**< binary, integer or implicit integer bounding variable y */
4550  SCIP_Real vbdcoef, /**< coefficient c of bounding variable y */
4551  SCIP_Real lhs, /**< left hand side of variable bound inequality */
4552  SCIP_Real rhs, /**< right hand side of variable bound inequality */
4553  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
4554  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
4555  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
4556  * Usually set to TRUE. */
4557  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
4558  * TRUE for model constraints, FALSE for additional, redundant constraints. */
4559  SCIP_Bool check, /**< should the constraint be checked for feasibility?
4560  * TRUE for model constraints, FALSE for additional, redundant constraints. */
4561  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
4562  * Usually set to TRUE. */
4563  SCIP_Bool local, /**< is constraint only valid locally?
4564  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
4565  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
4566  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
4567  * adds coefficients to this constraint. */
4568  SCIP_Bool dynamic, /**< is constraint subject to aging?
4569  * Usually set to FALSE. Set to TRUE for own cuts which
4570  * are separated as constraints. */
4571  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
4572  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
4573  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
4574  * if it may be moved to a more global node?
4575  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
4576  )
4577 {
4578  SCIP_CONSHDLR* conshdlr;
4579  SCIP_CONSHDLRDATA* conshdlrdata;
4580  SCIP_CONSDATA* consdata;
4581 
4582  /* find the variable bound constraint handler */
4583  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
4584  if( conshdlr == NULL )
4585  {
4586  SCIPerrorMessage("variable bound constraint handler not found\n");
4587  return SCIP_PLUGINNOTFOUND;
4588  }
4589 
4590  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4591  assert(conshdlrdata != NULL);
4592 
4593  /* create constraint data */
4594  SCIP_CALL( consdataCreate(scip, &consdata, var, vbdvar, vbdcoef, lhs, rhs) );
4595 
4596  /* create constraint */
4597  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
4598  local, modifiable, dynamic, removable, stickingatnode) );
4599 
4600  if( SCIPisTransformed(scip) )
4601  {
4602  /* catch events for variables */
4603  SCIP_CALL( catchEvents(scip, *cons, conshdlrdata->eventhdlr) );
4604  }
4605 
4606  return SCIP_OKAY;
4607 }
4608 
4609 /** creates and captures a variable bound constraint: lhs <= x + c*y <= rhs
4610  * with all constraint flags set to their default values
4611  *
4612  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
4613  */
4614 SCIP_RETCODE SCIPcreateConsBasicVarbound(
4615  SCIP* scip, /**< SCIP data structure */
4616  SCIP_CONS** cons, /**< pointer to hold the created constraint */
4617  const char* name, /**< name of constraint */
4618  SCIP_VAR* var, /**< variable x that has variable bound */
4619  SCIP_VAR* vbdvar, /**< binary, integer or implicit integer bounding variable y */
4620  SCIP_Real vbdcoef, /**< coefficient c of bounding variable y */
4621  SCIP_Real lhs, /**< left hand side of variable bound inequality */
4622  SCIP_Real rhs /**< right hand side of variable bound inequality */
4623  )
4624 {
4625  SCIP_CALL( SCIPcreateConsVarbound(scip, cons, name, var, vbdvar,vbdcoef, lhs, rhs,
4626  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
4627 
4628  return SCIP_OKAY;
4629 }
4630 
4631 /** gets left hand side of variable bound constraint lhs <= x + c*y <= rhs */
4632 SCIP_Real SCIPgetLhsVarbound(
4633  SCIP* scip, /**< SCIP data structure */
4634  SCIP_CONS* cons /**< constraint data */
4635  )
4636 {
4637  SCIP_CONSDATA* consdata;
4638 
4639  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
4640  {
4641  SCIPerrorMessage("constraint is not a variable bound constraint\n");
4642  SCIPABORT();
4643  return SCIP_INVALID; /*lint !e527*/
4644  }
4645 
4646  consdata = SCIPconsGetData(cons);
4647  assert(consdata != NULL);
4648 
4649  return consdata->lhs;
4650 }
4651 
4652 /** gets right hand side of variable bound constraint lhs <= x + c*y <= rhs */
4653 SCIP_Real SCIPgetRhsVarbound(
4654  SCIP* scip, /**< SCIP data structure */
4655  SCIP_CONS* cons /**< constraint data */
4656  )
4657 {
4658  SCIP_CONSDATA* consdata;
4659 
4660  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
4661  {
4662  SCIPerrorMessage("constraint is not a variable bound constraint\n");
4663  SCIPABORT();
4664  return SCIP_INVALID; /*lint !e527*/
4665  }
4666 
4667  consdata = SCIPconsGetData(cons);
4668  assert(consdata != NULL);
4669 
4670  return consdata->rhs;
4671 }
4672 
4673 /** gets bounded variable x of variable bound constraint lhs <= x + c*y <= rhs */
4674 SCIP_VAR* SCIPgetVarVarbound(
4675  SCIP* scip, /**< SCIP data structure */
4676  SCIP_CONS* cons /**< constraint data */
4677  )
4678 {
4679  SCIP_CONSDATA* consdata;
4680 
4681  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
4682  {
4683  SCIPerrorMessage("constraint is not a variable bound constraint\n");
4684  SCIPABORT();
4685  return NULL; /*lint !e527*/
4686  }
4687 
4688  consdata = SCIPconsGetData(cons);
4689  assert(consdata != NULL);
4690 
4691  return consdata->var;
4692 }
4693 
4694 /** gets bounding variable y of variable bound constraint lhs <= x + c*y <= rhs */
4695 SCIP_VAR* SCIPgetVbdvarVarbound(
4696  SCIP* scip, /**< SCIP data structure */
4697  SCIP_CONS* cons /**< constraint data */
4698  )
4699 {
4700  SCIP_CONSDATA* consdata;
4701 
4702  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
4703  {
4704  SCIPerrorMessage("constraint is not a variable bound constraint\n");
4705  SCIPABORT();
4706  return NULL; /*lint !e527*/
4707  }
4708 
4709  consdata = SCIPconsGetData(cons);
4710  assert(consdata != NULL);
4711 
4712  return consdata->vbdvar;
4713 }
4714 
4715 /** gets bound coefficient c of variable bound constraint lhs <= x + c*y <= rhs */
4716 SCIP_Real SCIPgetVbdcoefVarbound(
4717  SCIP* scip, /**< SCIP data structure */
4718  SCIP_CONS* cons /**< constraint data */
4719  )
4720 {
4721  SCIP_CONSDATA* consdata;
4722 
4723  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
4724  {
4725  SCIPerrorMessage("constraint is not a variable bound constraint\n");
4726  SCIPABORT();
4727  return SCIP_INVALID; /*lint !e527*/
4728  }
4729 
4730  consdata = SCIPconsGetData(cons);
4731  assert(consdata != NULL);
4732 
4733  return consdata->vbdcoef;
4734 }
4735 
4736 /** gets the dual solution of the variable bound constraint in the current LP */
4737 SCIP_Real SCIPgetDualsolVarbound(
4738  SCIP* scip, /**< SCIP data structure */
4739  SCIP_CONS* cons /**< constraint data */
4740  )
4741 {
4742  SCIP_CONSDATA* consdata;
4743 
4744  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
4745  {
4746  SCIPerrorMessage("constraint is not a variable bound constraint\n");
4747  SCIPABORT();
4748  return SCIP_INVALID; /*lint !e527*/
4749  }
4750 
4751  consdata = SCIPconsGetData(cons);
4752  assert(consdata != NULL);
4753 
4754  if( consdata->row != NULL )
4755  return SCIProwGetDualsol(consdata->row);
4756  else
4757  return 0.0;
4758 }
4759 
4760 /** gets the dual Farkas value of the variable bound constraint in the current infeasible LP */
4761 SCIP_Real SCIPgetDualfarkasVarbound(
4762  SCIP* scip, /**< SCIP data structure */
4763  SCIP_CONS* cons /**< constraint data */
4764  )
4765 {
4766  SCIP_CONSDATA* consdata;
4767 
4768  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
4769  {
4770  SCIPerrorMessage("constraint is not a variable bound constraint\n");
4771  SCIPABORT();
4772  return SCIP_INVALID; /*lint !e527*/
4773  }
4774 
4775  consdata = SCIPconsGetData(cons);
4776  assert(consdata != NULL);
4777 
4778  if( consdata->row != NULL )
4779  return SCIProwGetDualfarkas(consdata->row);
4780  else
4781  return 0.0;
4782 }
4783 
4784 /** returns the linear relaxation of the given variable bound constraint; may return NULL if no LP row was yet created;
4785  * the user must not modify the row!
4786  */
4787 SCIP_ROW* SCIPgetRowVarbound(
4788  SCIP* scip, /**< SCIP data structure */
4789  SCIP_CONS* cons /**< constraint data */
4790  )
4791 {
4792  SCIP_CONSDATA* consdata;
4793 
4794  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
4795  {
4796  SCIPerrorMessage("constraint is not a variable bound constraint\n");
4797  SCIPABORT();
4798  return NULL; /*lint !e527*/
4799  }
4800 
4801  consdata = SCIPconsGetData(cons);
4802  assert(consdata != NULL);
4803 
4804  return consdata->row;
4805 }
4806 
4807 /**@} */
SCIP_RESULT
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:51
SCIPisEQ
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41572
SCIP_BOUNDTYPE
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
CONSHDLR_PROP_TIMING
#define CONSHDLR_PROP_TIMING
Definition: cons_varbound.c:69
SCIPisZero
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:41685
SCIPgetRowSolFeasibility
SCIP_Real SCIPgetRowSolFeasibility(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip.c:28308
SCIPfindConshdlr
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:5878
SCIP_INFEASIBLE
Definition: type_result.h:37
SCIPallocMemory
#define SCIPallocMemory(scip, ptr)
Definition: scip.h:20526
SCIPconsIsLocked
SCIP_Bool SCIPconsIsLocked(SCIP_CONS *cons)
Definition: cons.c:7939
SCIPsetConshdlrTrans
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip.c:5588
separateCons
static SCIP_RETCODE separateCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool usebdwidening, SCIP_SOL *sol, SCIP_RESULT *result)
Definition: cons_varbound.c:844
conshdlrdataFree
static void conshdlrdataFree(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata)
Definition: cons_varbound.c:200
SCIPresetConsAge
SCIP_RETCODE SCIPresetConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:25588
SCIP_BdChgIdx
Definition: struct_var.h:97
SCIPvarGetName
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16443
SCIP_DECL_CONSPROP
static SCIP_DECL_CONSPROP(consPropVarbound)
Definition: cons_varbound.c:3958
PROPRULE
enum Proprule PROPRULE
Definition: cons_varbound.c:125
CONSHDLR_DELAYSEPA
#define CONSHDLR_DELAYSEPA
Definition: cons_varbound.c:64
chgLhs
static SCIP_RETCODE chgLhs(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
Definition: cons_varbound.c:975
SCIP_EVENTTYPE_VARFIXED
#define SCIP_EVENTTYPE_VARFIXED
Definition: type_event.h:48
CONSHDLR_DESC
#define CONSHDLR_DESC
Definition: cons_varbound.c:54
SCIPaggregateVars
SCIP_RETCODE SCIPaggregateVars(SCIP *scip, SCIP_VAR *varx, SCIP_VAR *vary, SCIP_Real scalarx, SCIP_Real scalary, SCIP_Real rhs, SCIP_Bool *infeasible, SCIP_Bool *redundant, SCIP_Bool *aggregated)
Definition: scip.c:22886
consdataCreate
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_VAR *var, SCIP_VAR *vbdvar, SCIP_Real vbdcoef, SCIP_Real lhs, SCIP_Real rhs)
Definition: cons_varbound.c:257
cons_varbound.h
Constraint handler for variable bound constraints .
SCIPisInfinity
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:41648
resolvePropagation
static SCIP_RETCODE resolvePropagation(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *infervar, PROPRULE proprule, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real inferbd, SCIP_Bool usebdwidening)
Definition: cons_varbound.c:467
SCIPdelCons
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:11540
SCIPvarIsBinary
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16623
SCIP_DECL_CONSSEPALP
static SCIP_DECL_CONSSEPALP(consSepalpVarbound)
Definition: cons_varbound.c:3788
SCIPisFeasLT
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41920
SCIP_DECL_CONSINITLP
static SCIP_DECL_CONSINITLP(consInitlpVarbound)
Definition: cons_varbound.c:3772
SCIPsetConshdlrResprop
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip.c:5634
chgRhs
static SCIP_RETCODE chgRhs(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
Definition: cons_varbound.c:1057
SCIPsetConshdlrSepa
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
Definition: scip.c:5246
SCIP_DECL_CONSENFOLP
static SCIP_DECL_CONSENFOLP(consEnfolpVarbound)
Definition: cons_varbound.c:3848
SCIP_VARTYPE_INTEGER_CHAR
#define SCIP_VARTYPE_INTEGER_CHAR
Definition: def.h:99
SCIP_SUCCESS
Definition: type_result.h:49
NULL
#define NULL
Definition: lpi_spx.cpp:130
addRelaxation
static SCIP_RETCODE addRelaxation(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:373
SCIPvarGetLbLocal
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17113
CONSHDLR_SEPAFREQ
#define CONSHDLR_SEPAFREQ
Definition: cons_varbound.c:58
SCIPisStopped
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1125
SCIPfeasFloor
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:42032
SCIPconsIsModifiable
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:7849
SCIPconsIsActive
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition: cons.c:7681
SCIPsetConshdlrCopy
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip.c:5334
SCIPvarGetUbGlobal
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17067
SCIP_Var
Definition: struct_var.h:196
SCIPgetHugeValue
SCIP_Real SCIPgetHugeValue(SCIP *scip)
Definition: scip.c:41674
CONSHDLR_MAXPREROUNDS
#define CONSHDLR_MAXPREROUNDS
Definition: cons_varbound.c:63
SCIPisConflictAnalysisApplicable
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
Definition: scip.c:24320
PROPRULE_1
Definition: cons_varbound.c:120
SCIPgetProbvarSum
SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: scip.c:17429
SCIPsetConshdlrGetVars
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip.c:5818
SCIPcreateConsSetpack
SCIP_RETCODE SCIPcreateConsSetpack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, 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)
Definition: cons_setppc.c:8948
SCIP_DECL_CONSTRANS
static SCIP_DECL_CONSTRANS(consTransVarbound)
Definition: cons_varbound.c:3738
SCIPconsIsTransformed
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
Definition: cons.c:7909
FALSE
#define FALSE
Definition: def.h:56
SCIPgetDualsolVarbound
SCIP_Real SCIPgetDualsolVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:4738
SCIPgetNBinVars
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:10743
SCIPgetLhsVarbound
SCIP_Real SCIPgetLhsVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:4633
SCIPincludeEventhdlrBasic
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip.c:7778
TRUE
#define TRUE
Definition: def.h:55
SCIPconsGetHdlr
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:7640
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
PROPRULE
enum Proprule PROPRULE
Definition: cons_abspower.c:170
SCIP_VARTYPE_BINARY
Definition: type_var.h:53
SCIPsetConshdlrParse
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
Definition: scip.c:5795
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:266
SCIP_DECL_CONSGETVARS
static SCIP_DECL_CONSGETVARS(consGetVarsVarbound)
Definition: cons_varbound.c:4403
conshdlrdataCreate
static SCIP_RETCODE conshdlrdataCreate(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_varbound.c:181
SCIPisFeasZero
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:41972
SCIPparseVarsLinearsum
SCIP_RETCODE SCIPparseVarsLinearsum(SCIP *scip, const char *str, SCIP_VAR **vars, SCIP_Real *vals, int *nvars, int varssize, int *requiredsize, char **endptr, SCIP_Bool *success)
Definition: scip.c:16332
SCIPisFeasIntegral
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:42008
SCIPmarkConsPropagate
SCIP_RETCODE SCIPmarkConsPropagate(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:25786
SCIPdebugMessage
#define SCIPdebugMessage
Definition: pub_message.h:77
SCIPgetSolVal
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:34983
SCIP_SEPARATED
Definition: type_result.h:40
CONSHDLR_NAME
#define CONSHDLR_NAME
Definition: cons_varbound.c:53
DEFAULT_PRESOLPAIRWISE
#define DEFAULT_PRESOLPAIRWISE
Definition: cons_varbound.c:83
SCIPconsIsLocal
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:7839
SCIPconsIsSeparated
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:7779
SCIPprintCons
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip.c:26237
SCIPaddCut
SCIP_RETCODE SCIPaddCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip.c:30967
cons_setppc.h
Constraint handler for the set partitioning / packing / covering constraints .
SCIPreleaseCons
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip.c:24949
SCIP_DECL_LINCONSUPGD
static SCIP_DECL_LINCONSUPGD(linconsUpgdVarbound)
Definition: cons_varbound.c:3580
SCIP_DECL_CONSPARSE
static SCIP_DECL_CONSPARSE(consParseVarbound)
Definition: cons_varbound.c:4280
SCIPallocBlockMemory
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:20554
SCIPfeasCeil
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip.c:42044
SCIPcreateConsBasicVarbound
SCIP_RETCODE SCIPcreateConsBasicVarbound(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *var, SCIP_VAR *vbdvar, SCIP_Real vbdcoef, SCIP_Real lhs, SCIP_Real rhs)
Definition: cons_varbound.c:4615
SCIPsetConshdlrFree
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip.c:5359
SCIPconsIsInitial
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:7769
SCIPcreateConsVarbound
SCIP_RETCODE SCIPcreateConsVarbound(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *var, SCIP_VAR *vbdvar, SCIP_Real vbdcoef, 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)
Definition: cons_varbound.c:4545
SCIPinferVarUbCons
SCIP_RETCODE SCIPinferVarUbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:20572
SCIPanalyzeConflictCons
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: scip.c:24720
SCIP_Sol
Definition: struct_sol.h:50
SCIPaddBoolParam
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:3547
CONSHDLR_SEPAPRIORITY
#define CONSHDLR_SEPAPRIORITY
Definition: cons_varbound.c:55
SCIPvarGetStatus
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16562
SCIPvarIsIntegral
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16634
SCIPrealToRational
SCIP_Bool SCIPrealToRational(SCIP_Real val, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Longint *nominator, SCIP_Longint *denominator)
Definition: misc.c:7215
SCIPconshdlrGetData
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:3917
SCIP_DECL_CONSEXITSOL
static SCIP_DECL_CONSEXITSOL(consExitsolVarbound)
Definition: cons_varbound.c:3694
SCIP_DECL_EVENTEXEC
static SCIP_DECL_EVENTEXEC(eventExecVarbound)
Definition: cons_varbound.c:4441
SCIPcatchVarEvent
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip.c:36622
SCIPfreeMemory
#define SCIPfreeMemory(scip, ptr)
Definition: scip.h:20542
SCIPinitConflictAnalysis
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip)
Definition: scip.c:24342
SCIPisLT
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41585
SCIPincConsAge
SCIP_RETCODE SCIPincConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:25560
SCIP_PRESOLTIMING_MEDIUM
#define SCIP_PRESOLTIMING_MEDIUM
Definition: type_timing.h:44
SCIPisFeasPositive
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:41984
SCIPisNegative
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:41709
SCIPgetTransformedVar
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip.c:17075
SCIPconsIsStickingAtNode
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:7879
SCIP_DIDNOTFIND
Definition: type_result.h:35
preprocessConstraintPairs
static SCIP_RETCODE preprocessConstraintPairs(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_Bool *cutoff, int *nchgbds, int *ndelconss, int *nchgcoefs, int *nchgsides)
Definition: cons_varbound.c:1828
SCIP_Cons
Definition: struct_cons.h:36
SCIPerrorMessage
#define SCIPerrorMessage
Definition: pub_message.h:45
CONSHDLR_PRESOLTIMING
#define CONSHDLR_PRESOLTIMING
Definition: cons_varbound.c:68
SCIPunlockVarCons
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip.c:19526
SCIPupdateConsFlags
SCIP_RETCODE SCIPupdateConsFlags(SCIP *scip, SCIP_CONS *cons0, SCIP_CONS *cons1)
Definition: scip.c:25300
SCIP_DECL_CONSHDLRCOPY
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyVarbound)
Definition: cons_varbound.c:3657
SCIP_Conshdlr
Definition: struct_cons.h:116
SCIPisFeasNegative
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:41996
SCIP_DECL_SORTPTRCOMP
static SCIP_DECL_SORTPTRCOMP(consVarboundComp)
Definition: cons_varbound.c:145
SCIPconshdlrGetName
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:3897
SCIP_BOUNDTYPE_LOWER
Definition: type_lp.h:47
SCIPepsilon
SCIP_Real SCIPepsilon(SCIP *scip)
Definition: scip.c:41118
EVENTHDLR_NAME
#define EVENTHDLR_NAME
Definition: cons_varbound.c:71
SCIPgetDualfarkasVarbound
SCIP_Real SCIPgetDualfarkasVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:4762
SCIPisLE
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41598
SCIPgetNegatedVar
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip.c:17163
SCIPsetConshdlrPresol
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip.c:5527
SCIP_FEASIBLE
Definition: type_result.h:36
SCIPadjustedVarUb
SCIP_Real SCIPadjustedVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real ub)
Definition: scip.c:19717
SCIPconsGetName
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:7620
SCIPdebugPrintCons
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:83
SCIPisFeasEQ
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41907
SCIProwIsInLP
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:19126
SCIP_EVENTDATA
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:146
SCIP_DECL_CONSCHECK
static SCIP_DECL_CONSCHECK(consCheckVarbound)
Definition: cons_varbound.c:3915
SCIP_OKAY
Definition: type_retcode.h:33
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:41637
SCIPsortPtr
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
SCIPsetConshdlrProp
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip.c:5292
EVENTHDLR_DESC
#define EVENTHDLR_DESC
Definition: cons_varbound.c:72
SCIPgetRhsVarbound
SCIP_Real SCIPgetRhsVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:4654
SCIPincludeConshdlrVarbound
SCIP_RETCODE SCIPincludeConshdlrVarbound(SCIP *scip)
Definition: cons_varbound.c:4479
SCIPincludeConshdlrBasic
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip.c:5192
propagateCons
static SCIP_RETCODE propagateCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool usebdwidening, SCIP_Bool *cutoff, int *nchgbds, int *nchgsides, int *ndelconss)
Definition: cons_varbound.c:1139
SCIP_REDUCEDDOM
Definition: type_result.h:42
SCIPinProbing
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:32131
SCIPisFeasGT
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41946
SCIPgetVbdcoefVarbound
SCIP_Real SCIPgetVbdcoefVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:4717
DEFAULT_MAXLPCOEF
#define DEFAULT_MAXLPCOEF
Definition: cons_varbound.c:84
checkRedundancySide
static void checkRedundancySide(SCIP *scip, SCIP_VAR *var, SCIP_VAR *vbdvar, SCIP_Real coef0, SCIP_Real coef1, SCIP_Real side0, SCIP_Real side1, SCIP_Bool *sideequal, SCIP_Bool *cons0sidered, SCIP_Bool *cons1sidered, SCIP_Bool islhs)
Definition: cons_varbound.c:1480
SCIP_CONSDATA
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:50
SCIP_EVENTTYPE_BOUNDTIGHTENED
#define SCIP_EVENTTYPE_BOUNDTIGHTENED
Definition: type_event.h:97
SCIPconsGetData
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:7650
SCIPreleaseVar
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip.c:16884
CONSHDLR_DELAYPROP
#define CONSHDLR_DELAYPROP
Definition: cons_varbound.c:65
SCIPdelConsLocal
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:12080
SCIPisGT
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41611
SCIPtightenVarLb
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:20193
SCIPcaptureVar
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:16850
SCIP_UNKNOWN
#define SCIP_UNKNOWN
Definition: def.h:148
SCIPvarGetUbLocal
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17123
SCIPisTransformed
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip.c:997
SCIP_DECL_CONSFREE
static SCIP_DECL_CONSFREE(consFreeVarbound)
Definition: cons_varbound.c:3673
SCIPcreateCons
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, 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)
Definition: scip.c:24772
SCIPvarGetIndex
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:16740
SCIP_Bool
#define SCIP_Bool
Definition: def.h:53
SCIP_VARTYPE_IMPLINT
Definition: type_var.h:55
PROPRULE_4
Definition: cons_varbound.c:123
CONSHDLR_CHECKPRIORITY
#define CONSHDLR_CHECKPRIORITY
Definition: cons_varbound.c:57
SCIPgetStage
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:801
SCIPconsIsDynamic
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:7859
analyzeConflict
static SCIP_RETCODE analyzeConflict(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *infervar, SCIP_Real inferbd, PROPRULE proprule, SCIP_BOUNDTYPE boundtype, SCIP_Bool usebdwidening)
Definition: cons_varbound.c:678
SCIP_VARTYPE_INTEGER
Definition: type_var.h:54
MAX
#define MAX(x, y)
Definition: tclique_def.h:75
SCIPstrToRealValue
SCIP_Bool SCIPstrToRealValue(const char *str, SCIP_Real *value, char **endptr)
Definition: misc.c:8245
SCIPaddConflictLb
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip.c:24369
SCIP_Row
Definition: struct_lp.h:189
SCIP_DECL_CONSRESPROP
static SCIP_DECL_CONSRESPROP(consRespropVarbound)
Definition: cons_varbound.c:4148
SCIP_STAGE_PRESOLVING
Definition: type_set.h:38
SCIPconsIsRemovable
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:7869
SCIPconsIsDeleted
SCIP_Bool SCIPconsIsDeleted(SCIP_CONS *cons)
Definition: cons.c:7739
SCIPaddVarVlb
SCIP_RETCODE SCIPaddVarVlb(SCIP *scip, SCIP_VAR *var, SCIP_VAR *vlbvar, SCIP_Real vlbcoef, SCIP_Real vlbconstant, SCIP_Bool *infeasible, int *nbdchgs)
Definition: scip.c:21563
SCIP_VARSTATUS_MULTAGGR
Definition: type_var.h:45
SCIPaddConflictRelaxedLb
SCIP_RETCODE SCIPaddConflictRelaxedLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedlb)
Definition: scip.c:24403
SCIPsetConshdlrInitlp
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip.c:5611
SCIPgetVbdvarVarbound
SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:4696
DEFAULT_USEBDWIDENING
#define DEFAULT_USEBDWIDENING
Definition: cons_varbound.c:85
CONSHDLR_PROPFREQ
#define CONSHDLR_PROPFREQ
Definition: cons_varbound.c:59
cons_linear.h
Constraint handler for linear constraints in their most general form, .
MAXSCALEDCOEF
#define MAXSCALEDCOEF
Definition: cons_varbound.c:88
Proprule
Proprule
Definition: cons_abspower.c:162
LINCONSUPGD_PRIORITY
#define LINCONSUPGD_PRIORITY
Definition: cons_varbound.c:74
applyFixings
static SCIP_RETCODE applyFixings(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *cutoff, int *nchgbds, int *ndelconss, int *naddconss)
Definition: cons_varbound.c:2565
SCIPisGE
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41624
SCIPaddCoefLinear
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
Definition: cons_linear.c:16436
SCIPinferVarLbCons
SCIP_RETCODE SCIPinferVarLbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:20469
tightenCoefs
static SCIP_RETCODE tightenCoefs(SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, int *nchgsides, int *ndelconss)
Definition: cons_varbound.c:2979
SCIPdropVarEvent
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip.c:36668
SCIPsetConshdlrDelete
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip.c:5565
SCIPaddCons
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:11477
PROPRULE_3
Definition: cons_varbound.c:122
SCIPvarGetType
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16608
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:20585
SCIPvarGetLbGlobal
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17057
SCIP_VARTYPE_IMPLINT_CHAR
#define SCIP_VARTYPE_IMPLINT_CHAR
Definition: def.h:100
SCIPchgLhsLinear
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
Definition: cons_linear.c:16729
SCIPsetConshdlrPrint
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip.c:5772
SCIProwGetDualsol
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
Definition: lp.c:18935
SCIPinfoMessage
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip.c:1281
REALABS
#define REALABS(x)
Definition: def.h:151
SCIP_DECL_CONSCOPY
static SCIP_DECL_CONSCOPY(consCopyVarbound)
Definition: cons_varbound.c:4247
SCIP_VARTYPE_CONTINUOUS_CHAR
#define SCIP_VARTYPE_CONTINUOUS_CHAR
Definition: def.h:101
SCIP_BOUNDTYPE_UPPER
Definition: type_lp.h:48
SCIPgetNIntVars
int SCIPgetNIntVars(SCIP *scip)
Definition: scip.c:10788
SCIPcreateConsLinear
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)
Definition: cons_linear.c:16099
SCIPisIntegral
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:41721
SCIP_DECL_CONSSEPASOL
static SCIP_DECL_CONSSEPASOL(consSepasolVarbound)
Definition: cons_varbound.c:3818
SCIP_DECL_CONSENFOPS
static SCIP_DECL_CONSENFOPS(consEnfopsVarbound)
Definition: cons_varbound.c:3888
SCIPduplicateBufferArray
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip.h:20593
SCIPsetConshdlrExitsol
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip.c:5455
SCIPisFeasLE
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41933
SCIPlockVarCons
SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip.c:19453
SCIPunmarkConsPropagate
SCIP_RETCODE SCIPunmarkConsPropagate(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:25812
SCIP_Real
#define SCIP_Real
Definition: def.h:127
SCIPconsIsChecked
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:7799
SCIPgetConflictVarLb
SCIP_Real SCIPgetConflictVarLb(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:24635
SCIPtightenVarUb
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:20299
MIN
#define MIN(x, y)
Definition: memory.c:67
SCIPchgRhsLinear
SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
Definition: cons_linear.c:16750
CONSHDLR_NEEDSCONS
#define CONSHDLR_NEEDSCONS
Definition: cons_varbound.c:66
SCIPcreateEmptyRowCons
SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip.c:27600
SCIPprintRow
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip.c:28334
SCIPisFeasGE
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41959
checkCons
static SCIP_Bool checkCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool checklprows)
Definition: cons_varbound.c:423
SCIPgetRowVarbound
SCIP_ROW * SCIPgetRowVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:4788
SCIP_INVALID
#define SCIP_INVALID
Definition: def.h:147
SCIPfeastol
SCIP_Real SCIPfeastol(SCIP *scip)
Definition: scip.c:41146
prettifyConss
static SCIP_RETCODE prettifyConss(SCIP *scip, SCIP_CONS **conss, int nconss, int *nchgcoefs, int *nchgsides)
Definition: cons_varbound.c:2405
SCIPreleaseRow
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip.c:27738
SCIP_DECL_CONSDELETE
static SCIP_DECL_CONSDELETE(consDeleteVarbound)
Definition: cons_varbound.c:3717
CONSHDLR_ENFOPRIORITY
#define CONSHDLR_ENFOPRIORITY
Definition: cons_varbound.c:56
SCIPaddConflictRelaxedUb
SCIP_RETCODE SCIPaddConflictRelaxedUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedub)
Definition: scip.c:24471
SCIP_Longint
#define SCIP_Longint
Definition: def.h:112
SCIP_PLUGINNOTFOUND
Definition: type_retcode.h:45
SCIPadjustedVarLb
SCIP_Real SCIPadjustedVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real lb)
Definition: scip.c:19685
SCIPeventGetType
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:917
SCIPfreeBlockMemory
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:20571
SCIP_STAGE_SOLVING
Definition: type_set.h:42
SCIP_VARTYPE_BINARY_CHAR
#define SCIP_VARTYPE_BINARY_CHAR
Definition: def.h:98
SCIPaddVarLocks
SCIP_RETCODE SCIPaddVarLocks(SCIP *scip, SCIP_VAR *var, int nlocksdown, int nlocksup)
Definition: scip.c:19399
consdataFree
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata)
Definition: cons_varbound.c:327
SCIPincludeLinconsUpgrade
SCIP_RETCODE SCIPincludeLinconsUpgrade(SCIP *scip, SCIP_DECL_LINCONSUPGD((*linconsupgd)), int priority, const char *conshdlrname)
Definition: cons_linear.c:16047
SCIP_CONSHDLRDATA
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:49
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:20597
SCIPdebug
#define SCIPdebug(x)
Definition: pub_message.h:74
upgradeConss
static SCIP_RETCODE upgradeConss(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS **conss, int nconss, SCIP_Bool *cutoff, int *naggrvars, int *nchgbds, int *nchgcoefs, int *nchgsides, int *ndelconss, int *naddconss)
Definition: cons_varbound.c:3377
createRelaxation
static SCIP_RETCODE createRelaxation(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:352
SCIPaddConflictUb
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip.c:24436
SCIP_DECL_CONSLOCK
static SCIP_DECL_CONSLOCK(consLockVarbound)
Definition: cons_varbound.c:4167
SCIPgetNImplVars
int SCIPgetNImplVars(SCIP *scip)
Definition: scip.c:10833
SCIProwGetDualfarkas
SCIP_Real SCIProwGetDualfarkas(SCIP_ROW *row)
Definition: lp.c:18948
SCIP_DECL_CONSPRESOL
static SCIP_DECL_CONSPRESOL(consPresolVarbound)
Definition: cons_varbound.c:3994
SCIP_INVALIDDATA
Definition: type_retcode.h:43
SCIPgetConflictVarUb
SCIP_Real SCIPgetConflictVarUb(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:24659
SCIPisPositive
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:41697
dropEvents
static SCIP_RETCODE dropEvents(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_varbound.c:237
SCIP_DECL_CONSPRINT
static SCIP_DECL_CONSPRINT(consPrintVarbound)
Definition: cons_varbound.c:4205
SCIPgetVarVarbound
SCIP_VAR * SCIPgetVarVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:4675
SCIPaddRealParam
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:3629
SCIPsetConshdlrGetNVars
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip.c:5841
SCIPvarGetProbvar
SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition: var.c:11481
SCIPaddVarToRow
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:27864
SCIPABORT
#define SCIPABORT()
Definition: def.h:238
SCIPaddVarVub
SCIP_RETCODE SCIPaddVarVub(SCIP *scip, SCIP_VAR *var, SCIP_VAR *vubvar, SCIP_Real vubcoef, SCIP_Real vubconstant, SCIP_Bool *infeasible, int *nbdchgs)
Definition: scip.c:21622
catchEvents
static SCIP_RETCODE catchEvents(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_varbound.c:217
SCIPconsIsEnforced
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:7789
PROPRULE_2
Definition: cons_varbound.c:121
CONSHDLR_EAGERFREQ
#define CONSHDLR_EAGERFREQ
Definition: cons_varbound.c:60
SCIPconsIsPropagated
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:7819
SCIPcopyConsLinear
SCIP_RETCODE SCIPcopyConsLinear(SCIP *scip, SCIP_CONS **cons, SCIP *sourcescip, const char *name, int nvars, SCIP_VAR **sourcevars, SCIP_Real *sourcecoefs, SCIP_Real lhs, SCIP_Real rhs, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, 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 global, SCIP_Bool *valid)
Definition: cons_linear.c:16311
SCIPconshdlrSetData
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
Definition: cons.c:3927
SCIPinRepropagation
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip.c:36834
SCIP_CUTOFF
Definition: type_result.h:39
SCIP_Eventhdlr
Definition: struct_event.h:185
SCIP_DECL_CONSGETNVARS
static SCIP_DECL_CONSGETNVARS(consGetNVarsVarbound)
Definition: cons_varbound.c:4427
SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:56