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>
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"
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 */
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 */
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
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
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
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
266
267 return SCIP_OKAY;
268}
269
270/** drops events for variables */
271static
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
286
287 return SCIP_OKAY;
288}
289
290/** creates a variable bound constraint data object */
291static
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 */
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
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
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,
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
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 */
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 {
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
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
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
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);
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);
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);
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
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);
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);
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
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 */
993 return SCIP_OKAY;
994
995 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
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 */
1143
1144 return SCIP_OKAY;
1145}
1146
1147/** separates the given variable bound constraint */
1148static
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 {
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
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
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
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
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
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 */
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
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)++;
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
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)++;
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
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)++;
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
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)++;
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
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)++;
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
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));
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
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
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;
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 */
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 */
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
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
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
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
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 */
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
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
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,
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 {
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
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
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
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
4050 }
4051
4052 return SCIP_OKAY;
4053}
4054
4055/** check if we can upgrade to a set-packing constraint */
4056static
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 */
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,
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,
4329 }
4330
4331 return SCIP_OKAY;
4332}
4333
4334/** adds symmetry information of constraint to a symmetry detection graph */
4335static
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 */
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 */
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
4987 if( !SCIPisInfinity(scip, consdata->rhs) )
4988 {
4989 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->var, locktype, nlocksneg, nlockspos) );
4990 if( consdata->vbdcoef > 0.0 )
4991 {
4992 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vbdvar, locktype, nlocksneg, nlockspos) );
4993 }
4994 else
4995 {
4996 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vbdvar, locktype, nlockspos, nlocksneg) );
4997 }
4998 }
4999
5000 return SCIP_OKAY;
5001}
5002
5003/** constraint activation notification method of constraint handler */
5004static
5005SCIP_DECL_CONSACTIVE(consActiveVarbound)
5006{ /*lint --e{715}*/
5008 {
5009 SCIP_CALL( addNlrow(scip, cons) );
5010 }
5011
5012 return SCIP_OKAY;
5013}
5014
5015/** constraint deactivation notification method of constraint handler */
5016static
5017SCIP_DECL_CONSDEACTIVE(consDeactiveVarbound)
5018{ /*lint --e{715}*/
5019 SCIP_CONSDATA* consdata;
5020
5021 assert(cons != NULL);
5022
5023 consdata = SCIPconsGetData(cons);
5024 assert(consdata != NULL);
5025
5026 /* remove row from NLP, if still in solving
5027 * if we are in exitsolve, the whole NLP will be freed anyway
5028 */
5029 if( SCIPgetStage(scip) == SCIP_STAGE_SOLVING && consdata->nlrow != NULL )
5030 {
5031 SCIP_CALL( SCIPdelNlRow(scip, consdata->nlrow) );
5032 }
5033
5034 return SCIP_OKAY;
5035}
5036
5037/** constraint display method of constraint handler */
5038static
5039SCIP_DECL_CONSPRINT(consPrintVarbound)
5040{ /*lint --e{715}*/
5041 SCIP_CONSDATA* consdata;
5042
5043 assert(scip != NULL);
5044 assert(conshdlr != NULL);
5045 assert(cons != NULL);
5046
5047 consdata = SCIPconsGetData(cons);
5048 assert(consdata != NULL);
5049
5050 /* print left hand side for ranged rows */
5051 if( !SCIPisInfinity(scip, -consdata->lhs)
5052 && !SCIPisInfinity(scip, consdata->rhs)
5053 && !SCIPisEQ(scip, consdata->lhs, consdata->rhs) )
5054 SCIPinfoMessage(scip, file, "%.15g <= ", consdata->lhs);
5055
5056 /* print coefficients and variables */
5057 SCIPinfoMessage(scip, file, "<%s>[%c] %+.15g<%s>[%c]", SCIPvarGetName(consdata->var),
5061 consdata->vbdcoef, SCIPvarGetName(consdata->vbdvar),
5065
5066 /* print right hand side */
5067 if( SCIPisEQ(scip, consdata->lhs, consdata->rhs) )
5068 SCIPinfoMessage(scip, file, " == %.15g", consdata->rhs);
5069 else if( !SCIPisInfinity(scip, consdata->rhs) )
5070 SCIPinfoMessage(scip, file, " <= %.15g", consdata->rhs);
5071 else if( !SCIPisInfinity(scip, -consdata->lhs) )
5072 SCIPinfoMessage(scip, file, " >= %.15g", consdata->lhs);
5073 else
5074 SCIPinfoMessage(scip, file, " [free]");
5075
5076 return SCIP_OKAY;
5077}
5078
5079/** constraint copying method of constraint handler */
5080static
5081SCIP_DECL_CONSCOPY(consCopyVarbound)
5082{ /*lint --e{715}*/
5083 SCIP_VAR** vars;
5084 SCIP_Real* coefs;
5085 const char* consname;
5086
5087 SCIP_CALL( SCIPallocBufferArray(scip, &vars, 2) );
5088 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, 2) );
5089
5090 vars[0] = SCIPgetVarVarbound(sourcescip, sourcecons);
5091 vars[1] = SCIPgetVbdvarVarbound(sourcescip, sourcecons);
5092
5093 coefs[0] = 1.0;
5094 coefs[1] = SCIPgetVbdcoefVarbound(sourcescip, sourcecons);
5095
5096 if( name != NULL )
5097 consname = name;
5098 else
5099 consname = SCIPconsGetName(sourcecons);
5100
5101 /* copy the varbound using the linear constraint copy method */
5102 SCIP_CALL( SCIPcopyConsLinear(scip, cons, sourcescip, consname, 2, vars, coefs,
5103 SCIPgetLhsVarbound(sourcescip, sourcecons), SCIPgetRhsVarbound(sourcescip, sourcecons), varmap, consmap,
5104 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode, global, valid) );
5105
5106 SCIPfreeBufferArray(scip, &coefs);
5107 SCIPfreeBufferArray(scip, &vars);
5108
5109 return SCIP_OKAY;
5110}
5111
5112/** constraint parsing method of constraint handler */
5113static
5114SCIP_DECL_CONSPARSE(consParseVarbound)
5115{ /*lint --e{715}*/
5116 SCIP_VAR** vars;
5117 SCIP_Real* coefs;
5118 SCIP_Real lhs;
5119 SCIP_Real rhs;
5120 char* endstr;
5121 int requiredsize;
5122 int nvars;
5123
5124 assert(scip != NULL);
5125 assert(success != NULL);
5126 assert(str != NULL);
5127 assert(name != NULL);
5128 assert(cons != NULL);
5129
5130 /* set left and right hand side to their default values */
5131 lhs = -SCIPinfinity(scip);
5132 rhs = SCIPinfinity(scip);
5133
5134 (*success) = FALSE;
5135
5136 /* return of string empty */
5137 if( !*str )
5138 return SCIP_OKAY;
5139
5140 /* ignore whitespace */
5141 SCIP_CALL( SCIPskipSpace((char**)&str) );
5142
5143 if( isdigit(str[0]) || ((str[0] == '-' || str[0] == '+') && isdigit(str[1])) )
5144 {
5145 if( !SCIPparseReal(scip, str, &lhs, &endstr) )
5146 {
5147 SCIPerrorMessage("error parsing left hand side\n");
5148 return SCIP_OKAY;
5149 }
5150
5151 /* ignore whitespace */
5152 SCIP_CALL( SCIPskipSpace(&endstr) );
5153
5154 if( endstr[0] != '<' || endstr[1] != '=' )
5155 {
5156 SCIPerrorMessage("missing \"<=\" after left hand side(, found %c%c)\n", endstr[0], endstr[1]);
5157 return SCIP_OKAY;
5158 }
5159
5160 SCIPdebugMsg(scip, "found left hand side <%g>\n", lhs);
5161
5162 /* it was indeed a left-hand-side, so continue parsing after it */
5163 str = endstr + 2;
5164 }
5165
5166 /* pares x + c*y as linear sum */
5167 SCIP_CALL( SCIPallocBufferArray(scip, &vars, 2) );
5168 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, 2) );
5169
5170 /* parse linear sum to get variables and coefficients */
5171 SCIP_CALL( SCIPparseVarsLinearsum(scip, str, vars, coefs, &nvars, 2, &requiredsize, &endstr, success) );
5172
5173 if( requiredsize == 2 && *success )
5174 {
5175 SCIP_Real value;
5176
5177 assert(nvars == 2);
5178 assert(SCIPisEQ(scip, coefs[0], 1.0));
5179
5180 SCIPdebugMsg(scip, "found linear sum <%s> + %g <%s>\n", SCIPvarGetName(vars[0]), coefs[1], SCIPvarGetName(vars[1]));
5181
5182 /* ignore whitespace */
5183 SCIP_CALL( SCIPskipSpace(&endstr) );
5184
5185 str = endstr;
5186
5187 if( *str != '\0' && *(str+1) != '\0' && SCIPparseReal(scip, str+2, &value, &endstr) )
5188 {
5189 /* search for end of linear sum: either '<=', '>=', '==', or '[free]' */
5190 switch( *str )
5191 {
5192 case '<':
5193 assert(str[1] == '=');
5194 rhs = value;
5195 break;
5196 case '=':
5197 assert(str[1] == '=');
5198 assert(SCIPisInfinity(scip, -lhs));
5199 lhs = value;
5200 rhs = value;
5201 break;
5202 case '>':
5203 assert(str[1] == '=');
5204 assert(SCIPisInfinity(scip, -lhs));
5205 lhs = value;
5206 break;
5207 default:
5208 SCIPerrorMessage("missing relation symbol after linear sum\n");
5209 *success = FALSE;
5210 }
5211 }
5212 else if( strncmp(str, "[free]", 6) != 0 )
5213 *success = FALSE;
5214 }
5215
5216 if( *success )
5217 {
5218 SCIP_CALL( SCIPcreateConsVarbound(scip, cons, name, vars[0], vars[1], coefs[1], lhs, rhs,
5219 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
5220 }
5221
5222 /* free buffer arrays */
5223 SCIPfreeBufferArray(scip, &coefs);
5224 SCIPfreeBufferArray(scip, &vars);
5225
5226 return SCIP_OKAY;
5227}
5228
5229/** constraint method of constraint handler which returns the variables (if possible) */
5230static
5231SCIP_DECL_CONSGETVARS(consGetVarsVarbound)
5232{ /*lint --e{715}*/
5233 assert( success != NULL );
5234
5235 if( varssize < 2 )
5236 (*success) = FALSE;
5237 else
5238 {
5239 SCIP_CONSDATA* consdata;
5240 assert(cons != NULL);
5241 assert(vars != NULL);
5242
5243 consdata = SCIPconsGetData(cons);
5244 assert(consdata != NULL);
5245
5246 vars[0] = consdata->var;
5247 vars[1] = consdata->vbdvar;
5248 (*success) = TRUE;
5249 }
5250
5251 return SCIP_OKAY;
5252}
5253
5254/** constraint method of constraint handler which returns the number of variables (if possible) */
5255static
5256SCIP_DECL_CONSGETNVARS(consGetNVarsVarbound)
5257{ /*lint --e{715}*/
5258 (*nvars) = 2;
5259 (*success) = TRUE;
5260
5261 return SCIP_OKAY;
5262}
5263
5264/** constraint handler method which returns the permutation symmetry detection graph of a constraint */
5265static
5266SCIP_DECL_CONSGETPERMSYMGRAPH(consGetPermsymGraphVarbound)
5267{ /*lint --e{715}*/
5268 SCIP_CALL( addSymmetryInformation(scip, SYM_SYMTYPE_PERM, cons, graph, success) );
5269
5270 return SCIP_OKAY;
5271}
5272
5273/** constraint handler method which returns the signed permutation symmetry detection graph of a constraint */
5274static
5275SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(consGetSignedPermsymGraphVarbound)
5276{ /*lint --e{715}*/
5277 SCIP_CALL( addSymmetryInformation(scip, SYM_SYMTYPE_SIGNPERM, cons, graph, success) );
5278
5279 return SCIP_OKAY;
5280}
5281
5282/*
5283 * Event Handler
5284 */
5285
5286/** execution method of bound change event handler */
5287static
5288SCIP_DECL_EVENTEXEC(eventExecVarbound)
5289{ /*lint --e{715}*/
5290 SCIP_CONS* cons;
5291 SCIP_CONSDATA* consdata;
5292
5293 assert(event != NULL);
5294 cons = (SCIP_CONS*)eventdata;
5295 assert(cons != NULL);
5296 consdata = SCIPconsGetData(cons);
5297 assert(consdata != NULL);
5298
5300 {
5301 consdata->presolved = FALSE;
5302 }
5303 else
5304 {
5305 assert((SCIPeventGetType(event) & SCIP_EVENTTYPE_BOUNDTIGHTENED) != 0);
5306
5307 consdata->presolved = FALSE;
5308 consdata->tightened = FALSE;
5309
5311 }
5312
5313 return SCIP_OKAY;
5314}
5315
5316/**@} */
5317
5318
5319/** creates the handler for variable bound constraints and includes it in SCIP */
5321 SCIP* scip /**< SCIP data structure */
5322 )
5323{
5324 SCIP_CONSHDLRDATA* conshdlrdata;
5325 SCIP_EVENTHDLR* eventhdlr;
5326 SCIP_CONSHDLR* conshdlr;
5327
5328 /* include event handler for bound change events */
5330 eventExecVarbound, NULL) );
5331
5332 /* create variable bound constraint handler data */
5333 SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlr) );
5334
5335 /* include constraint handler */
5338 consEnfolpVarbound, consEnfopsVarbound, consCheckVarbound, consLockVarbound,
5339 conshdlrdata) );
5340 assert(conshdlr != NULL);
5341
5342 /* set non-fundamental callbacks via specific setter functions */
5343 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyVarbound, consCopyVarbound) );
5344 SCIP_CALL( SCIPsetConshdlrActive(scip, conshdlr, consActiveVarbound) );
5345 SCIP_CALL( SCIPsetConshdlrDeactive(scip, conshdlr, consDeactiveVarbound) );
5346 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteVarbound) );
5347 SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolVarbound) );
5348 SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolVarbound) );
5349 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeVarbound) );
5350 SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsVarbound) );
5351 SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsVarbound) );
5352 SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpVarbound) );
5353 SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseVarbound) );
5355 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintVarbound) );
5358 SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropVarbound) );
5359 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpVarbound, consSepasolVarbound, CONSHDLR_SEPAFREQ,
5361 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransVarbound) );
5362 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxVarbound) );
5363 SCIP_CALL( SCIPsetConshdlrGetPermsymGraph(scip, conshdlr, consGetPermsymGraphVarbound) );
5364 SCIP_CALL( SCIPsetConshdlrGetSignedPermsymGraph(scip, conshdlr, consGetSignedPermsymGraphVarbound) );
5365
5366 if( SCIPfindConshdlr(scip,"linear") != NULL )
5367 {
5368 /* include the linear constraint to varbound constraint upgrade in the linear constraint handler */
5370 }
5371
5372 /* add varbound constraint handler parameters */
5374 "constraints/" CONSHDLR_NAME "/presolpairwise",
5375 "should pairwise constraint comparison be performed in presolving?",
5376 &conshdlrdata->presolpairwise, TRUE, DEFAULT_PRESOLPAIRWISE, NULL, NULL) );
5378 "constraints/" CONSHDLR_NAME "/maxlpcoef",
5379 "maximum coefficient in varbound constraint to be added as a row into LP",
5380 &conshdlrdata->maxlpcoef, TRUE, DEFAULT_MAXLPCOEF, 0.0, 1e+20, NULL, NULL) );
5382 "constraints/" CONSHDLR_NAME "/usebdwidening", "should bound widening be used in conflict analysis?",
5383 &conshdlrdata->usebdwidening, FALSE, DEFAULT_USEBDWIDENING, NULL, NULL) );
5384
5385 return SCIP_OKAY;
5386}
5387
5388/** creates and captures a variable bound constraint: lhs <= x + c*y <= rhs
5389 *
5390 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5391 */
5393 SCIP* scip, /**< SCIP data structure */
5394 SCIP_CONS** cons, /**< pointer to hold the created constraint */
5395 const char* name, /**< name of constraint */
5396 SCIP_VAR* var, /**< variable x that has variable bound */
5397 SCIP_VAR* vbdvar, /**< binary, integer or implicit integer bounding variable y */
5398 SCIP_Real vbdcoef, /**< coefficient c of bounding variable y */
5399 SCIP_Real lhs, /**< left hand side of variable bound inequality */
5400 SCIP_Real rhs, /**< right hand side of variable bound inequality */
5401 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
5402 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
5403 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
5404 * Usually set to TRUE. */
5405 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
5406 * TRUE for model constraints, FALSE for additional, redundant constraints. */
5407 SCIP_Bool check, /**< should the constraint be checked for feasibility?
5408 * TRUE for model constraints, FALSE for additional, redundant constraints. */
5409 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
5410 * Usually set to TRUE. */
5411 SCIP_Bool local, /**< is constraint only valid locally?
5412 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
5413 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
5414 * Usually set to FALSE. In column generation applications, set to TRUE if pricing
5415 * adds coefficients to this constraint. */
5416 SCIP_Bool dynamic, /**< is constraint subject to aging?
5417 * Usually set to FALSE. Set to TRUE for own cuts which
5418 * are separated as constraints. */
5419 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
5420 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
5421 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
5422 * if it may be moved to a more global node?
5423 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
5424 )
5425{
5426 SCIP_CONSHDLR* conshdlr;
5427 SCIP_CONSHDLRDATA* conshdlrdata;
5428 SCIP_CONSDATA* consdata;
5429
5430 /* find the variable bound constraint handler */
5431 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
5432 if( conshdlr == NULL )
5433 {
5434 SCIPerrorMessage("variable bound constraint handler not found\n");
5435 return SCIP_PLUGINNOTFOUND;
5436 }
5437
5438 conshdlrdata = SCIPconshdlrGetData(conshdlr);
5439 assert(conshdlrdata != NULL);
5440
5441 /* create constraint data */
5442 SCIP_CALL( consdataCreate(scip, &consdata, var, vbdvar, vbdcoef, lhs, rhs) );
5443
5444 /* create constraint */
5445 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
5446 local, modifiable, dynamic, removable, stickingatnode) );
5447
5448 if( SCIPisTransformed(scip) )
5449 {
5450 /* catch events for variables */
5451 SCIP_CALL( catchEvents(scip, *cons, conshdlrdata->eventhdlr) );
5452 }
5453
5454 return SCIP_OKAY;
5455}
5456
5457/** creates and captures a variable bound constraint: lhs <= x + c*y <= rhs
5458 * with all constraint flags set to their default values
5459 *
5460 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5461 */
5463 SCIP* scip, /**< SCIP data structure */
5464 SCIP_CONS** cons, /**< pointer to hold the created constraint */
5465 const char* name, /**< name of constraint */
5466 SCIP_VAR* var, /**< variable x that has variable bound */
5467 SCIP_VAR* vbdvar, /**< binary, integer or implicit integer bounding variable y */
5468 SCIP_Real vbdcoef, /**< coefficient c of bounding variable y */
5469 SCIP_Real lhs, /**< left hand side of variable bound inequality */
5470 SCIP_Real rhs /**< right hand side of variable bound inequality */
5471 )
5472{
5473 SCIP_CALL( SCIPcreateConsVarbound(scip, cons, name, var, vbdvar,vbdcoef, lhs, rhs,
5475
5476 return SCIP_OKAY;
5477}
5478
5479/** gets left hand side of variable bound constraint lhs <= x + c*y <= rhs */
5481 SCIP* scip, /**< SCIP data structure */
5482 SCIP_CONS* cons /**< constraint data */
5483 )
5484{
5485 SCIP_CONSDATA* consdata;
5486
5487 assert(scip != NULL);
5488
5489 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5490 {
5491 SCIPerrorMessage("constraint is not a variable bound constraint\n");
5492 SCIPABORT();
5493 return SCIP_INVALID; /*lint !e527*/
5494 }
5495
5496 consdata = SCIPconsGetData(cons);
5497 assert(consdata != NULL);
5498
5499 return consdata->lhs;
5500}
5501
5502/** gets right hand side of variable bound constraint lhs <= x + c*y <= rhs */
5504 SCIP* scip, /**< SCIP data structure */
5505 SCIP_CONS* cons /**< constraint data */
5506 )
5507{
5508 SCIP_CONSDATA* consdata;
5509
5510 assert(scip != NULL);
5511
5512 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5513 {
5514 SCIPerrorMessage("constraint is not a variable bound constraint\n");
5515 SCIPABORT();
5516 return SCIP_INVALID; /*lint !e527*/
5517 }
5518
5519 consdata = SCIPconsGetData(cons);
5520 assert(consdata != NULL);
5521
5522 return consdata->rhs;
5523}
5524
5525/** gets bounded variable x of variable bound constraint lhs <= x + c*y <= rhs */
5527 SCIP* scip, /**< SCIP data structure */
5528 SCIP_CONS* cons /**< constraint data */
5529 )
5530{
5531 SCIP_CONSDATA* consdata;
5532
5533 assert(scip != NULL);
5534
5535 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5536 {
5537 SCIPerrorMessage("constraint is not a variable bound constraint\n");
5538 SCIPABORT();
5539 return NULL; /*lint !e527*/
5540 }
5541
5542 consdata = SCIPconsGetData(cons);
5543 assert(consdata != NULL);
5544
5545 return consdata->var;
5546}
5547
5548/** gets bounding variable y of variable bound constraint lhs <= x + c*y <= rhs */
5550 SCIP* scip, /**< SCIP data structure */
5551 SCIP_CONS* cons /**< constraint data */
5552 )
5553{
5554 SCIP_CONSDATA* consdata;
5555
5556 assert(scip != NULL);
5557
5558 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5559 {
5560 SCIPerrorMessage("constraint is not a variable bound constraint\n");
5561 SCIPABORT();
5562 return NULL; /*lint !e527*/
5563 }
5564
5565 consdata = SCIPconsGetData(cons);
5566 assert(consdata != NULL);
5567
5568 return consdata->vbdvar;
5569}
5570
5571/** gets bound coefficient c of variable bound constraint lhs <= x + c*y <= rhs */
5573 SCIP* scip, /**< SCIP data structure */
5574 SCIP_CONS* cons /**< constraint data */
5575 )
5576{
5577 SCIP_CONSDATA* consdata;
5578
5579 assert(scip != NULL);
5580
5581 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5582 {
5583 SCIPerrorMessage("constraint is not a variable bound constraint\n");
5584 SCIPABORT();
5585 return SCIP_INVALID; /*lint !e527*/
5586 }
5587
5588 consdata = SCIPconsGetData(cons);
5589 assert(consdata != NULL);
5590
5591 return consdata->vbdcoef;
5592}
5593
5594/** gets the dual solution of the variable bound constraint in the current LP */
5596 SCIP* scip, /**< SCIP data structure */
5597 SCIP_CONS* cons /**< constraint data */
5598 )
5599{
5600 SCIP_CONSDATA* consdata;
5601
5602 assert(scip != NULL);
5603
5604 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5605 {
5606 SCIPerrorMessage("constraint is not a variable bound constraint\n");
5607 SCIPABORT();
5608 return SCIP_INVALID; /*lint !e527*/
5609 }
5610
5611 consdata = SCIPconsGetData(cons);
5612 assert(consdata != NULL);
5613
5614 if( consdata->row != NULL )
5615 return SCIProwGetDualsol(consdata->row);
5616 else
5617 return 0.0;
5618}
5619
5620/** gets the dual Farkas value of the variable bound constraint in the current infeasible LP */
5622 SCIP* scip, /**< SCIP data structure */
5623 SCIP_CONS* cons /**< constraint data */
5624 )
5625{
5626 SCIP_CONSDATA* consdata;
5627
5628 assert(scip != NULL);
5629
5630 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5631 {
5632 SCIPerrorMessage("constraint is not a variable bound constraint\n");
5633 SCIPABORT();
5634 return SCIP_INVALID; /*lint !e527*/
5635 }
5636
5637 consdata = SCIPconsGetData(cons);
5638 assert(consdata != NULL);
5639
5640 if( consdata->row != NULL )
5641 return SCIProwGetDualfarkas(consdata->row);
5642 else
5643 return 0.0;
5644}
5645
5646/** returns the linear relaxation of the given variable bound constraint; may return NULL if no LP row was yet created;
5647 * the user must not modify the row!
5648 */
5650 SCIP* scip, /**< SCIP data structure */
5651 SCIP_CONS* cons /**< constraint data */
5652 )
5653{
5654 SCIP_CONSDATA* consdata;
5655
5656 assert(scip != NULL);
5657
5658 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5659 {
5660 SCIPerrorMessage("constraint is not a variable bound constraint\n");
5661 SCIPABORT();
5662 return NULL; /*lint !e527*/
5663 }
5664
5665 consdata = SCIPconsGetData(cons);
5666 assert(consdata != NULL);
5667
5668 return consdata->row;
5669}
5670
5671/** cleans up (multi-)aggregations and fixings from varbound constraints */
5673 SCIP* scip, /**< SCIP data structure */
5674 SCIP_Bool onlychecked, /**< should only checked constraints be cleaned up? */
5675 SCIP_Bool* infeasible, /**< pointer to return whether the problem was detected to be infeasible */
5676 int* naddconss, /**< pointer to count number of added (linear) constraints */
5677 int* ndelconss, /**< pointer to count number of deleted (varbound) constraints */
5678 int* nchgbds /**< pointer to count number of bound changes */
5679 )
5680{
5681 SCIP_CONSHDLR* conshdlr;
5682 SCIP_CONSHDLRDATA* conshdlrdata;
5683 SCIP_EVENTHDLR* eventhdlr;
5684 SCIP_CONS** conss;
5685 int nconss;
5686 int i;
5687
5688 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
5689 if( conshdlr == NULL )
5690 return SCIP_OKAY;
5691
5692 assert(infeasible != NULL);
5693 *infeasible = FALSE;
5694
5695 assert(naddconss != NULL);
5696 assert(ndelconss != NULL);
5697 assert(nchgbds != NULL);
5698
5699 conshdlrdata = SCIPconshdlrGetData(conshdlr);
5700 assert(conshdlrdata != NULL);
5701
5702 eventhdlr = conshdlrdata->eventhdlr;
5703 nconss = onlychecked ? SCIPconshdlrGetNCheckConss(conshdlr) : SCIPconshdlrGetNActiveConss(conshdlr);
5704 conss = onlychecked ? SCIPconshdlrGetCheckConss(conshdlr) : SCIPconshdlrGetConss(conshdlr);
5705
5706 /* loop backwards since then deleted constraints do not interfere with the loop */
5707 for( i = nconss - 1; i >= 0; --i )
5708 {
5709 SCIP_CALL( applyFixings(scip, conss[i], eventhdlr, infeasible, nchgbds, ndelconss, naddconss) );
5710
5711 if( *infeasible )
5712 break;
5713 }
5714
5715 return SCIP_OKAY;
5716}
enum Proprule PROPRULE
Definition: cons_and.c:179
Proprule
Definition: cons_and.c:172
Constraint handler for linear constraints in their most general form, .
Constraint handler for the set partitioning / packing / covering constraints .
static SCIP_DECL_CONSCHECK(consCheckVarbound)
static SCIP_RETCODE addRelaxation(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible)
static SCIP_DECL_CONSRESPROP(consRespropVarbound)
enum Proprule PROPRULE
static SCIP_DECL_SORTPTRCOMP(consVarboundComp)
static SCIP_RETCODE dropEvents(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr)
#define DEFAULT_USEBDWIDENING
#define CONSHDLR_NEEDSCONS
#define CONSHDLR_SEPAFREQ
Definition: cons_varbound.c:93
static SCIP_DECL_EVENTEXEC(eventExecVarbound)
static SCIP_DECL_CONSGETPERMSYMGRAPH(consGetPermsymGraphVarbound)
static SCIP_DECL_CONSACTIVE(consActiveVarbound)
#define CONSHDLR_CHECKPRIORITY
Definition: cons_varbound.c:92
#define CONSHDLR_DESC
Definition: cons_varbound.c:89
static SCIP_DECL_CONSINITSOL(consInitsolVarbound)
static SCIP_DECL_CONSPROP(consPropVarbound)
static SCIP_DECL_CONSLOCK(consLockVarbound)
static SCIP_RETCODE upgradeConss(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS **conss, int nconss, SCIP_Bool *cutoff, int *naggrvars, int *nchgbds, int *nchgcoefs, int *nchgsides, int *ndelconss, int *naddconss)
static SCIP_RETCODE applyFixings(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *cutoff, int *nchgbds, int *ndelconss, int *naddconss)
static SCIP_DECL_CONSPRESOL(consPresolVarbound)
static SCIP_DECL_CONSGETNVARS(consGetNVarsVarbound)
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_VAR *var, SCIP_VAR *vbdvar, SCIP_Real vbdcoef, SCIP_Real lhs, SCIP_Real rhs)
static SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(consGetSignedPermsymGraphVarbound)
static SCIP_RETCODE tightenCoefs(SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, int *nchgsides, int *ndelconss, SCIP_Bool *cutoff, int *nchgbds)
static SCIP_RETCODE createRelaxation(SCIP *scip, SCIP_CONS *cons)
static SCIP_DECL_CONSEXITSOL(consExitsolVarbound)
#define CONSHDLR_PROP_TIMING
static void checkRedundancySide(SCIP *scip, SCIP_VAR *var, SCIP_VAR *vbdvar, SCIP_Real coef0, SCIP_Real coef1, SCIP_Real side0, SCIP_Real side1, SCIP_Bool *sideequal, SCIP_Bool *cons0sidered, SCIP_Bool *cons1sidered, SCIP_Bool islhs)
static void conshdlrdataFree(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata)
static SCIP_DECL_CONSGETVARS(consGetVarsVarbound)
static SCIP_DECL_CONSCOPY(consCopyVarbound)
#define CONSHDLR_MAXPREROUNDS
Definition: cons_varbound.c:97
static SCIP_Bool checkCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool checklprows)
#define DEFAULT_PRESOLPAIRWISE
static SCIP_DECL_CONSSEPASOL(consSepasolVarbound)
static SCIP_DECL_CONSFREE(consFreeVarbound)
#define CONSHDLR_SEPAPRIORITY
Definition: cons_varbound.c:90
#define DEFAULT_MAXLPCOEF
static SCIP_DECL_CONSPRINT(consPrintVarbound)
static void prettifyConss(SCIP *scip, SCIP_CONS **conss, int nconss, int *nchgcoefs, int *nchgsides)
static SCIP_RETCODE addSymmetryInformation(SCIP *scip, SYM_SYMTYPE symtype, SCIP_CONS *cons, SYM_GRAPH *graph, SCIP_Bool *success)
static SCIP_RETCODE preprocessConstraintPairs(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_Bool *cutoff, int *nchgbds, int *ndelconss, int *nchgcoefs, int *nchgsides)
static SCIP_RETCODE chgLhs(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
static SCIP_DECL_CONSDEACTIVE(consDeactiveVarbound)
@ PROPRULE_2
@ PROPRULE_1
@ PROPRULE_3
@ PROPRULE_4
static SCIP_DECL_CONSSEPALP(consSepalpVarbound)
static SCIP_DECL_CONSDELETE(consDeleteVarbound)
static SCIP_RETCODE analyzeConflict(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *infervar, SCIP_Real inferbd, PROPRULE proprule, SCIP_BOUNDTYPE boundtype, SCIP_Bool usebdwidening)
static SCIP_DECL_CONSTRANS(consTransVarbound)
static SCIP_RETCODE chgRhs(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
#define CONSHDLR_PROPFREQ
Definition: cons_varbound.c:94
static SCIP_DECL_CONSPARSE(consParseVarbound)
static SCIP_DECL_CONSENFOPS(consEnfopsVarbound)
static SCIP_RETCODE resolvePropagation(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *infervar, PROPRULE proprule, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real inferbd, SCIP_Bool usebdwidening)
static SCIP_DECL_CONSENFORELAX(consEnforelaxVarbound)
static SCIP_RETCODE propagateCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool usebdwidening, SCIP_Bool *cutoff, int *nchgbds, int *nchgsides, int *ndelconss)
#define CONSHDLR_PRESOLTIMING
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata)
static SCIP_DECL_LINCONSUPGD(linconsUpgdVarbound)
static SCIP_DECL_CONSINITLP(consInitlpVarbound)
static SCIP_RETCODE addNlrow(SCIP *scip, SCIP_CONS *cons)
#define CONSHDLR_EAGERFREQ
Definition: cons_varbound.c:95
#define EVENTHDLR_DESC
static SCIP_RETCODE conshdlrdataCreate(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata, SCIP_EVENTHDLR *eventhdlr)
static SCIP_DECL_CONSENFOLP(consEnfolpVarbound)
#define CONSHDLR_ENFOPRIORITY
Definition: cons_varbound.c:91
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyVarbound)
static SCIP_RETCODE catchEvents(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr)
#define LINCONSUPGD_PRIORITY
static SCIP_RETCODE separateCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool usebdwidening, SCIP_SOL *sol, SCIP_RESULT *result)
#define CONSHDLR_DELAYSEPA
Definition: cons_varbound.c:98
#define MAXSCALEDCOEF
#define CONSHDLR_NAME
Definition: cons_varbound.c:88
#define EVENTHDLR_NAME
#define CONSHDLR_DELAYPROP
Definition: cons_varbound.c:99
Constraint handler for variable bound constraints .
defines macros for basic operations in double-double arithmetic giving roughly twice the precision of...
#define SCIPquadprecDivQD(r, a, b)
Definition: dbldblarith.h:65
#define SCIPquadprecProdDD(r, a, b)
Definition: dbldblarith.h:58
#define SCIPquadprecProdQD(r, a, b)
Definition: dbldblarith.h:63
#define SCIPquadprecSumQD(r, a, b)
Definition: dbldblarith.h:62
#define QUAD_ASSIGN(a, constant)
Definition: dbldblarith.h:51
#define QUAD(x)
Definition: dbldblarith.h:47
#define SCIPquadprecSumDD(r, a, b)
Definition: dbldblarith.h:60
#define SCIPquadprecSumQQ(r, a, b)
Definition: dbldblarith.h:67
#define QUAD_TO_DBL(x)
Definition: dbldblarith.h:49
#define NULL
Definition: def.h:266
#define SCIP_Longint
Definition: def.h:157
#define SCIP_VARTYPE_INTEGER_CHAR
Definition: def.h:144
#define SCIP_VARTYPE_IMPLINT_CHAR
Definition: def.h:145
#define SCIP_INVALID
Definition: def.h:192
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:242
#define SCIP_Real
Definition: def.h:172
#define SCIP_UNKNOWN
Definition: def.h:193
#define ABS(x)
Definition: def.h:234
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:238
#define SCIP_VARTYPE_BINARY_CHAR
Definition: def.h:143
#define SCIP_VARTYPE_CONTINUOUS_CHAR
Definition: def.h:146
#define SCIPABORT()
Definition: def.h:345
#define REALABS(x)
Definition: def.h:196
#define SCIP_CALL(x)
Definition: def.h:373
SCIP_RETCODE SCIPincludeLinconsUpgrade(SCIP *scip, SCIP_DECL_LINCONSUPGD((*linconsupgd)), int priority, const char *conshdlrname)
SCIP_Real SCIPgetVbdcoefVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
SCIP_Real SCIPgetDualfarkasVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPcreateConsBasicVarbound(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *var, SCIP_VAR *vbdvar, SCIP_Real vbdcoef, SCIP_Real lhs, SCIP_Real rhs)
SCIP_ROW * SCIPgetRowVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsSetpack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_setppc.c:9426
SCIP_RETCODE SCIPcleanupConssVarbound(SCIP *scip, SCIP_Bool onlychecked, SCIP_Bool *infeasible, int *naddconss, int *ndelconss, int *nchgbds)
SCIP_VAR * SCIPgetVarVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcopyConsLinear(SCIP *scip, SCIP_CONS **cons, SCIP *sourcescip, const char *name, int nvars, SCIP_VAR **sourcevars, SCIP_Real *sourcecoefs, SCIP_Real lhs, SCIP_Real rhs, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode, SCIP_Bool global, SCIP_Bool *valid)
SCIP_Real SCIPgetLhsVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_Real SCIPgetRhsVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetDualsolVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsVarbound(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *var, SCIP_VAR *vbdvar, SCIP_Real vbdcoef, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
SCIP_RETCODE SCIPincludeConshdlrVarbound(SCIP *scip)
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip_general.c:606
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:734
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:390
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2082
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2127
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2770
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2843
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:3475
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_Bool SCIPrealToRational(SCIP_Real val, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Longint *nominator, SCIP_Longint *denominator)
Definition: misc.c:9397
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition: misc.c:11215
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_RETCODE SCIPaddConflictRelaxedLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedlb)
SCIP_RETCODE SCIPaddConflictRelaxedUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedub)
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
SCIP_Real SCIPgetConflictVarUb(SCIP *scip, SCIP_VAR *var)
SCIP_Real SCIPgetConflictVarLb(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
int SCIPconshdlrGetNCheckConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4656
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
Definition: scip_cons.c:808
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
Definition: cons.c:4227
SCIP_CONS ** SCIPconshdlrGetCheckConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4613
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:540
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip_cons.c:831
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
Definition: scip_cons.c:235
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:281
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip_cons.c:181
SCIP_RETCODE SCIPsetConshdlrDeactive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDEACTIVE((*consdeactive)))
Definition: scip_cons.c:693
SCIP_RETCODE SCIPsetConshdlrGetPermsymGraph(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETPERMSYMGRAPH((*consgetpermsymgraph)))
Definition: scip_cons.c:900
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:578
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:372
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:323
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4197
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:347
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
SCIP_RETCODE SCIPsetConshdlrGetSignedPermsymGraph(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH((*consgetsignedpermsymgraph)))
Definition: scip_cons.c:924
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip_cons.c:468
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip_cons.c:624
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:444
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4217
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:601
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip_cons.c:647
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4670
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip_cons.c:854
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4593
SCIP_RETCODE SCIPsetConshdlrActive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSACTIVE((*consactive)))
Definition: scip_cons.c:670
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip_cons.c:785
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8244
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8473
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8234
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8383
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2537
SCIP_Bool SCIPconsIsMarkedPropagate(SCIP_CONS *cons)
Definition: cons.c:8423
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8413
SCIP_Bool SCIPconsIsDeleted(SCIP_CONS *cons)
Definition: cons.c:8343
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
Definition: cons.c:8523
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8403
SCIP_RETCODE SCIPunmarkConsPropagate(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:2043
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition: cons.c:8275
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: scip_cons.c:998
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8433
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8453
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8214
SCIP_RETCODE SCIPresetConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1813
SCIP_RETCODE SCIPmarkConsPropagate(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:2015
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8463
SCIP_RETCODE SCIPupdateConsFlags(SCIP *scip, SCIP_CONS *cons0, SCIP_CONS *cons1)
Definition: scip_cons.c:1525
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8493
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8393
SCIP_RETCODE SCIPincConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1785
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8483
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:250
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:104
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:1030
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:354
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:400
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_RETCODE SCIPdelNlRow(SCIP *scip, SCIP_NLROW *nlrow)
Definition: scip_nlp.c:424
SCIP_RETCODE SCIPaddNlRow(SCIP *scip, SCIP_NLROW *nlrow)
Definition: scip_nlp.c:396
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip_nlp.c:110
SCIP_RETCODE SCIPreleaseNlRow(SCIP *scip, SCIP_NLROW **nlrow)
Definition: scip_nlp.c:1058
SCIP_Bool SCIPnlrowIsInNLP(SCIP_NLROW *nlrow)
Definition: nlp.c:1956
SCIP_RETCODE SCIPcreateNlRow(SCIP *scip, SCIP_NLROW **nlrow, const char *name, SCIP_Real constant, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, SCIP_EXPR *expr, SCIP_Real lhs, SCIP_Real rhs, SCIP_EXPRCURV curvature)
Definition: scip_nlp.c:954
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:97
SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONS *cons, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1422
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1701
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2212
SCIP_Real SCIPgetRowSolFeasibility(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip_lp.c:2167
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1562
SCIP_Real SCIProwGetDualfarkas(SCIP_ROW *row)
Definition: lp.c:17325
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:17523
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
Definition: lp.c:17312
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1213
void SCIPupdateSolLPConsViolation(SCIP *scip, SCIP_SOL *sol, SCIP_Real absviol, SCIP_Real relviol)
Definition: scip_sol.c:137
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPround(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Real SCIPgetHugeValue(SCIP *scip)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPparseReal(SCIP *scip, const char *str, SCIP_Real *value, char **endptr)
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip_tree.c:146
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5326
SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:4474
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17598
SCIP_RETCODE SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6471
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4799
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17537
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3353
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18143
SCIP_RETCODE SCIPaggregateVars(SCIP *scip, SCIP_VAR *varx, SCIP_VAR *vary, SCIP_Real scalarx, SCIP_Real scalary, SCIP_Real rhs, SCIP_Bool *infeasible, SCIP_Bool *redundant, SCIP_Bool *aggregated)
Definition: scip_var.c:8524
SCIP_RETCODE SCIPinferVarUbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5738
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4889
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17925
SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition: var.c:12217
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5443
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17583
SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: scip_var.c:1794
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18087
SCIP_RETCODE SCIPaddVarVub(SCIP *scip, SCIP_VAR *var, SCIP_VAR *vubvar, SCIP_Real vubcoef, SCIP_Real vubconstant, SCIP_Bool *infeasible, int *nbdchgs)
Definition: scip_var.c:6843
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17757
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4382
SCIP_RETCODE SCIPaddVarVlb(SCIP *scip, SCIP_VAR *var, SCIP_VAR *vlbvar, SCIP_Real vlbcoef, SCIP_Real vlbconstant, SCIP_Bool *infeasible, int *nbdchgs)
Definition: scip_var.c:6784
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:4560
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17418
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1248
SCIP_Real SCIPadjustedVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real ub)
Definition: scip_var.c:4768
SCIP_RETCODE SCIPparseVarsLinearsum(SCIP *scip, const char *str, SCIP_VAR **vars, SCIP_Real *vals, int *nvars, int varssize, int *requiredsize, char **endptr, SCIP_Bool *success)
Definition: scip_var.c:704
SCIP_Real SCIPadjustedVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real lb)
Definition: scip_var.c:4736
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17609
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip_var.c:1527
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18133
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18077
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8399
SCIP_RETCODE SCIPinferVarLbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5624
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3295
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1439
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1214
SCIP_RETCODE SCIPtightenVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6351
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
SCIP_RETCODE SCIPskipSpace(char **s)
Definition: misc.c:10869
SCIP_RETCODE SCIPgetSymActiveVariables(SCIP *scip, SYM_SYMTYPE symtype, SCIP_VAR ***vars, SCIP_Real **scalars, int *nvars, SCIP_Real *constant, SCIP_Bool transformed)
SCIP_RETCODE SCIPextendPermsymDetectionGraphLinear(SCIP *scip, SYM_GRAPH *graph, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_CONS *cons, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool *success)
memory allocation routines
real eps
public methods for managing constraints
public methods for managing events
public methods for LP management
public methods for message output
#define SCIPerrorMessage
Definition: pub_message.h:64
#define SCIPdebug(x)
Definition: pub_message.h:93
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:102
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for problem variables
public methods for conflict handler plugins and conflict analysis
public methods for constraint handler plugins and constraints
public methods for cuts and aggregation rows
public methods for event handler plugins and event handlers
general public methods
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for nonlinear relaxation
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for solutions
public methods for the branch-and-bound tree
public methods for SCIP variables
structs for symmetry computations
methods for dealing with symmetry detection graphs
@ SCIP_CONFTYPE_PROPAGATION
Definition: type_conflict.h:60
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:64
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:65
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:173
#define SCIP_EVENTTYPE_VARFIXED
Definition: type_event.h:72
#define SCIP_EVENTTYPE_BOUNDTIGHTENED
Definition: type_event.h:123
@ SCIP_EXPRCURV_LINEAR
Definition: type_expr.h:65
@ SCIP_BOUNDTYPE_UPPER
Definition: type_lp.h:57
@ SCIP_BOUNDTYPE_LOWER
Definition: type_lp.h:56
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_FEASIBLE
Definition: type_result.h:45
@ SCIP_REDUCEDDOM
Definition: type_result.h:51
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_SEPARATED
Definition: type_result.h:49
@ SCIP_SUCCESS
Definition: type_result.h:58
@ SCIP_INFEASIBLE
Definition: type_result.h:46
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_INVALIDDATA
Definition: type_retcode.h:52
@ SCIP_PLUGINNOTFOUND
Definition: type_retcode.h:54
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_STAGE_PRESOLVING
Definition: type_set.h:49
@ SCIP_STAGE_SOLVING
Definition: type_set.h:53
enum SYM_Symtype SYM_SYMTYPE
Definition: type_symmetry.h:64
@ SYM_SYMTYPE_SIGNPERM
Definition: type_symmetry.h:62
@ SYM_SYMTYPE_PERM
Definition: type_symmetry.h:61
#define SCIP_PRESOLTIMING_MEDIUM
Definition: type_timing.h:53
@ SCIP_VARTYPE_INTEGER
Definition: type_var.h:63
@ SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:71
@ SCIP_VARTYPE_IMPLINT
Definition: type_var.h:64
@ SCIP_VARTYPE_BINARY
Definition: type_var.h:62
@ SCIP_VARSTATUS_FIXED
Definition: type_var.h:52
@ SCIP_VARSTATUS_MULTAGGR
Definition: type_var.h:54
@ SCIP_LOCKTYPE_MODEL
Definition: type_var.h:97