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