Scippy

SCIP

Solving Constraint Integer Programs

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