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