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