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