Scippy

SCIP

Solving Constraint Integer Programs

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