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