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