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 }
4049
4050 return SCIP_OKAY;
4051}
4052
4053/** check if we can upgrade to a set-packing constraint */
4054static
4056 SCIP* scip, /**< SCIP data structure */
4057 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
4058 SCIP_CONS** conss, /**< constraint set */
4059 int nconss, /**< number of constraints in constraint set */
4060 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */
4061 int* naggrvars, /**< pointer to count the number of aggregated variables */
4062 int* nchgbds, /**< pointer to count number of bound changes */
4063 int* nchgcoefs, /**< pointer to count the number of changed coefficients */
4064 int* nchgsides, /**< pointer to count the number of left and right hand sides */
4065 int* ndelconss, /**< pointer to count the number of deleted constraints */
4066 int* naddconss /**< pointer to count the number of added constraints */
4067 )
4068{
4069 SCIP_VAR* vars[2];
4070 SCIP_CONS* newcons;
4071 SCIP_CONS* cons;
4072 SCIP_CONSDATA* consdata;
4073 int c;
4074
4075 assert(scip != NULL);
4076 assert(conshdlrdata != NULL);
4077 assert(conss != NULL || nconss == 0);
4078 assert(cutoff != NULL);
4079 assert(naggrvars != NULL);
4080 assert(nchgbds != NULL);
4081 assert(nchgcoefs != NULL);
4082 assert(nchgsides != NULL);
4083 assert(ndelconss != NULL);
4084 assert(naddconss != NULL);
4085
4086 /* if we cannot find any constraint for upgrading, stop */
4088 return SCIP_OKAY;
4089
4090 if( nconss == 0 )
4091 return SCIP_OKAY;
4092
4093 assert(conss != NULL);
4094
4095 for( c = nconss - 1; c >= 0; --c )
4096 {
4097 cons = conss[c];
4098 assert(cons != NULL);
4099
4100 if( !SCIPconsIsActive(cons) )
4101 continue;
4102
4103 consdata = SCIPconsGetData(cons);
4104 assert(consdata != NULL);
4105 assert(SCIPisLE(scip, consdata->lhs, consdata->rhs));
4106
4107 if( !consdata->presolved )
4108 {
4109 /* incorporate fixings and aggregations in constraint */
4110 SCIP_CALL( applyFixings(scip, cons, conshdlrdata->eventhdlr, cutoff, nchgbds, ndelconss, naddconss) );
4111
4112 if( *cutoff )
4113 return SCIP_OKAY;
4114 if( !SCIPconsIsActive(cons) )
4115 continue;
4116 }
4117
4118 if( SCIPconsIsMarkedPropagate(cons) )
4119 {
4120 /* propagate constraint */
4121 SCIP_CALL( propagateCons(scip, cons, conshdlrdata->usebdwidening, cutoff, nchgbds, nchgsides, ndelconss) );
4122
4123 if( *cutoff )
4124 return SCIP_OKAY;
4125 if( !SCIPconsIsActive(cons) )
4126 continue;
4127 }
4128
4129 if( !consdata->tightened )
4130 {
4131 /* tighten variable bound coefficient */
4132 SCIP_CALL( tightenCoefs(scip, cons, nchgcoefs, nchgsides, ndelconss, cutoff, nchgbds) );
4133
4134 if( *cutoff )
4135 return SCIP_OKAY;
4136 if( !SCIPconsIsActive(cons) )
4137 continue;
4138
4139 assert(SCIPisLE(scip, consdata->lhs, consdata->rhs));
4140 }
4141
4142 /* check if both variables are of binary type */
4143 if( SCIPvarIsBinary(consdata->vbdvar) && SCIPvarIsBinary(consdata->var) )
4144 {
4145 /* coefficient and sides should be tightened and we assume that the constraint is not redundant */
4146 assert(SCIPisEQ(scip, REALABS(consdata->vbdcoef), 1.0));
4147 assert(SCIPisZero(scip, consdata->rhs) || SCIPisEQ(scip, consdata->rhs, 1.0) || SCIPisInfinity(scip, consdata->rhs));
4148 assert(SCIPisZero(scip, consdata->lhs) || SCIPisEQ(scip, consdata->lhs, 1.0) || SCIPisInfinity(scip, -consdata->lhs));
4149 assert(!SCIPisInfinity(scip, consdata->rhs) || !SCIPisInfinity(scip, -consdata->lhs));
4150
4151 /* the case x + y <= 1 or x + y >= 1 */
4152 if( consdata->vbdcoef > 0.0 )
4153 {
4154 if( SCIPisEQ(scip, consdata->rhs, 1.0) )
4155 {
4156 /* check for aggregations like x + y == 1 */
4157 if( SCIPisEQ(scip, consdata->lhs, 1.0) )
4158 {
4159 SCIP_Bool infeasible;
4160 SCIP_Bool redundant;
4161 SCIP_Bool aggregated;
4162
4163 SCIPdebugMsg(scip, "varbound constraint <%s>: aggregate <%s> + <%s> == 1\n",
4164 SCIPconsGetName(cons), SCIPvarGetName(consdata->var), SCIPvarGetName(consdata->vbdvar));
4165
4166 /* aggregate both variables */
4167 SCIP_CALL( SCIPaggregateVars(scip, consdata->var, consdata->vbdvar, 1.0, 1.0, 1.0, &infeasible, &redundant, &aggregated) );
4168 assert(!infeasible);
4169 ++(*naggrvars);
4170
4171 SCIP_CALL( SCIPdelCons(scip, cons) );
4172 ++(*ndelconss);
4173
4174 continue;
4175 }
4176 assert(consdata->lhs < 0.5);
4177
4178 vars[0] = consdata->var;
4179 vars[1] = consdata->vbdvar;
4180 }
4181 else
4182 {
4183 assert(SCIPisEQ(scip, consdata->lhs, 1.0));
4184
4185 SCIP_CALL( SCIPgetNegatedVar(scip, consdata->var, &vars[0]) );
4186 SCIP_CALL( SCIPgetNegatedVar(scip, consdata->vbdvar, &vars[1]) );
4187 }
4188 }
4189 /* the case x - y <= 0 or x - y >= 0 */
4190 else
4191 {
4192 /* the case x - y <= 0 */
4193 if( SCIPisZero(scip, consdata->rhs) )
4194 {
4195 /* check for aggregations like x - y == 0 */
4196 if( SCIPisZero(scip, consdata->lhs) )
4197 {
4198 SCIP_Bool infeasible;
4199 SCIP_Bool redundant;
4200 SCIP_Bool aggregated;
4201
4202 SCIPdebugMsg(scip, "varbound constraint <%s>: aggregate <%s> - <%s> == 0\n",
4203 SCIPconsGetName(cons), SCIPvarGetName(consdata->var), SCIPvarGetName(consdata->vbdvar));
4204
4205 /* aggregate both variables */
4206 SCIP_CALL( SCIPaggregateVars(scip, consdata->var, consdata->vbdvar, 1.0, -1.0, 0.0, &infeasible, &redundant, &aggregated) );
4207 assert(!infeasible);
4208 ++(*naggrvars);
4209
4210 SCIP_CALL( SCIPdelCons(scip, cons) );
4211 ++(*ndelconss);
4212
4213 continue;
4214 }
4215 assert(consdata->lhs < -0.5);
4216
4217 vars[0] = consdata->var;
4218 SCIP_CALL( SCIPgetNegatedVar(scip, consdata->vbdvar, &vars[1]) );
4219 }
4220 /* the case x - y >= 0 */
4221 else
4222 {
4223 assert(SCIPisZero(scip, consdata->lhs));
4224
4225 SCIP_CALL( SCIPgetNegatedVar(scip, consdata->var, &vars[0]) );
4226 vars[1] = consdata->vbdvar;
4227 }
4228 }
4229
4230 SCIP_CALL( SCIPcreateConsSetpack(scip, &newcons, SCIPconsGetName(cons), 2, vars,
4235
4236 SCIP_CALL( SCIPaddCons(scip, newcons) );
4237 SCIPdebugMsg(scip, "upgraded varbound constraint <%s> to a set-packing constraint\n", SCIPconsGetName(cons));
4238 SCIPdebugPrintCons(scip, newcons, NULL);
4239
4240 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
4241 ++(*naddconss);
4242
4243 SCIP_CALL( SCIPdelCons(scip, cons) );
4244 ++(*ndelconss);
4245 }
4246 }
4247
4248 return SCIP_OKAY;
4249}
4250
4251/**@} */
4252
4253
4254/**@name Linear constraint upgrading
4255 *
4256 * @{
4257 */
4258
4259/** tries to upgrade a linear constraint into a variable bound constraint */
4260static
4261SCIP_DECL_LINCONSUPGD(linconsUpgdVarbound)
4262{ /*lint --e{715}*/
4263 SCIP_Bool upgrade;
4264
4265 assert(upgdcons != NULL);
4266
4267 /* check, if linear constraint can be upgraded to a variable bound constraint lhs <= x + a*y <= rhs
4268 * - there are exactly two variables
4269 * - one of the variables is non-binary (called the bounded variable x)
4270 * - one of the variables is non-continuous (called the bounding variable y)
4271 */
4272 upgrade = (nvars == 2) && (nposbin + nnegbin <= 1) && (nposcont + nnegcont <= 1);
4273
4274 if( upgrade )
4275 {
4276 SCIP_VAR* var;
4277 SCIP_VAR* vbdvar;
4278 SCIP_Real vbdcoef;
4279 SCIP_Real vbdlhs;
4280 SCIP_Real vbdrhs;
4281 int vbdind;
4282
4283 /* decide which variable we want to use as bounding variable y */
4284 if( SCIPvarGetType(vars[0]) < SCIPvarGetType(vars[1]) )
4285 vbdind = 0;
4286 else if( SCIPvarGetType(vars[0]) > SCIPvarGetType(vars[1]) )
4287 vbdind = 1;
4288 else if( SCIPisIntegral(scip, vals[0]) && !SCIPisIntegral(scip, vals[1]) )
4289 vbdind = 0;
4290 else if( !SCIPisIntegral(scip, vals[0]) && SCIPisIntegral(scip, vals[1]) )
4291 vbdind = 1;
4292 else if( REALABS(REALABS(vals[0]) - 1.0) < REALABS(REALABS(vals[1]) - 1.0) )
4293 vbdind = 1;
4294 else
4295 vbdind = 0;
4296
4297 /* do not upgrade when it is numerical unstable */
4298 if( SCIPisZero(scip, vals[vbdind]/vals[1-vbdind]) )
4299 return SCIP_OKAY;
4300
4301 SCIPdebugMsg(scip, "upgrading constraint <%s> to variable bound constraint\n", SCIPconsGetName(cons));
4302
4303 var = vars[1-vbdind];
4304 vbdvar = vars[vbdind];
4305
4306 assert(!SCIPisZero(scip, vals[1-vbdind]));
4307 vbdcoef = vals[vbdind]/vals[1-vbdind];
4308
4309 if( vals[1-vbdind] > 0.0 )
4310 {
4311 vbdlhs = SCIPisInfinity(scip, -lhs) ? -SCIPinfinity(scip) : lhs/vals[1-vbdind];
4312 vbdrhs = SCIPisInfinity(scip, rhs) ? SCIPinfinity(scip) : rhs/vals[1-vbdind];
4313 }
4314 else
4315 {
4316 vbdlhs = SCIPisInfinity(scip, rhs) ? -SCIPinfinity(scip) : rhs/vals[1-vbdind];
4317 vbdrhs = SCIPisInfinity(scip, -lhs) ? SCIPinfinity(scip) : lhs/vals[1-vbdind];
4318 }
4319
4320 /* create the bin variable bound constraint (an automatically upgraded constraint is always unmodifiable) */
4321 assert(!SCIPconsIsModifiable(cons));
4322 SCIP_CALL( SCIPcreateConsVarbound(scip, upgdcons, SCIPconsGetName(cons), var, vbdvar, vbdcoef, vbdlhs, vbdrhs,
4327 }
4328
4329 return SCIP_OKAY;
4330}
4331
4332/** adds symmetry information of constraint to a symmetry detection graph */
4333static
4335 SCIP* scip, /**< SCIP pointer */
4336 SYM_SYMTYPE symtype, /**< type of symmetries that need to be added */
4337 SCIP_CONS* cons, /**< constraint */
4338 SYM_GRAPH* graph, /**< symmetry detection graph */
4339 SCIP_Bool* success /**< pointer to store whether symmetry information could be added */
4340 )
4341{
4342 SCIP_VAR** vars;
4343 SCIP_Real* vals;
4344 SCIP_Real constant = 0.0;
4345 SCIP_Real lhs;
4346 SCIP_Real rhs;
4347 int nlocvars;
4348 int nvars;
4349
4350 assert(scip != NULL);
4351 assert(cons != NULL);
4352 assert(graph != NULL);
4353 assert(success != NULL);
4354
4355 /* get active variables of the constraint */
4356 nvars = SCIPgetNVars(scip);
4357 nlocvars = 2;
4358
4359 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
4360 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) );
4361
4362 vars[0] = SCIPgetVarVarbound(scip, cons);
4363 vars[1] = SCIPgetVbdvarVarbound(scip, cons);
4364 vals[0] = 1.0;
4365 vals[1] = SCIPgetVbdcoefVarbound(scip, cons);
4366
4367 SCIP_CALL( SCIPgetSymActiveVariables(scip, symtype, &vars, &vals, &nlocvars, &constant, SCIPisTransformed(scip)) );
4368 lhs = SCIPgetLhsVarbound(scip, cons) - constant;
4369 rhs = SCIPgetRhsVarbound(scip, cons) - constant;
4370
4371 SCIP_CALL( SCIPextendPermsymDetectionGraphLinear(scip, graph, vars, vals, nlocvars,
4372 cons, lhs, rhs, success) );
4373
4374 SCIPfreeBufferArray(scip, &vals);
4375 SCIPfreeBufferArray(scip, &vars);
4376
4377 return SCIP_OKAY;
4378}
4379
4380/**@} */
4381
4382
4383/**@name Callback methods
4384 *
4385 * @{
4386 */
4387
4388/** copy method for constraint handler plugins (called when SCIP copies plugins) */
4389static
4390SCIP_DECL_CONSHDLRCOPY(conshdlrCopyVarbound)
4391{ /*lint --e{715}*/
4392 assert(scip != NULL);
4393 assert(conshdlr != NULL);
4394 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4395
4396 /* call inclusion method of constraint handler */
4398
4399 *valid = TRUE;
4400
4401 return SCIP_OKAY;
4402}
4403
4404/** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
4405static
4406SCIP_DECL_CONSFREE(consFreeVarbound)
4407{ /*lint --e{715}*/
4408 SCIP_CONSHDLRDATA* conshdlrdata;
4409
4410 assert(scip != NULL);
4411 assert(conshdlr != NULL);
4412 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4413
4414 /* free constraint handler data */
4415 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4416 assert(conshdlrdata != NULL);
4417
4418 conshdlrdataFree(scip, &conshdlrdata);
4419
4420 SCIPconshdlrSetData(conshdlr, NULL);
4421
4422 return SCIP_OKAY;
4423}
4424
4425/** solving process initialization method of constraint handler */
4426static
4427SCIP_DECL_CONSINITSOL(consInitsolVarbound)
4428{ /*lint --e{715}*/
4429 /* add nlrow representation to NLP, if NLP had been constructed */
4431 {
4432 int c;
4433 for( c = 0; c < nconss; ++c )
4434 {
4435 SCIP_CALL( addNlrow(scip, conss[c]) );
4436 }
4437 }
4438
4439 return SCIP_OKAY;
4440}
4441
4442/** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
4443static
4444SCIP_DECL_CONSEXITSOL(consExitsolVarbound)
4445{ /*lint --e{715}*/
4446 SCIP_CONSDATA* consdata;
4447 int c;
4448
4449 /* release the rows and nlrows of all constraints */
4450 for( c = 0; c < nconss; ++c )
4451 {
4452 consdata = SCIPconsGetData(conss[c]);
4453 assert(consdata != NULL);
4454
4455 if( consdata->row != NULL )
4456 {
4457 SCIP_CALL( SCIPreleaseRow(scip, &consdata->row) );
4458 }
4459
4460 if( consdata->nlrow != NULL )
4461 {
4462 SCIP_CALL( SCIPreleaseNlRow(scip, &consdata->nlrow) );
4463 }
4464 }
4465
4466 return SCIP_OKAY;
4467}
4468
4469
4470/** frees specific constraint data */
4471static
4472SCIP_DECL_CONSDELETE(consDeleteVarbound)
4473{ /*lint --e{715}*/
4474 SCIP_CONSHDLRDATA* conshdlrdata;
4475
4476 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4477 assert(conshdlrdata != NULL);
4478
4479 /* drop events */
4480 if( SCIPisTransformed(scip) )
4481 {
4482 SCIP_CALL( dropEvents(scip, cons, conshdlrdata->eventhdlr) );
4483 }
4484
4485 SCIP_CALL( consdataFree(scip, consdata) );
4486
4487 return SCIP_OKAY;
4488}
4489
4490
4491/** transforms constraint data into data belonging to the transformed problem */
4492static
4493SCIP_DECL_CONSTRANS(consTransVarbound)
4494{ /*lint --e{715}*/
4495 SCIP_CONSHDLRDATA* conshdlrdata;
4496 SCIP_CONSDATA* sourcedata;
4497 SCIP_CONSDATA* targetdata;
4498
4499 assert(conshdlr != NULL);
4500
4501 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4502 assert(conshdlrdata != NULL);
4503
4504 sourcedata = SCIPconsGetData(sourcecons);
4505 assert(sourcedata != NULL);
4506
4507 /* create target constraint data */
4508 SCIP_CALL( consdataCreate(scip, &targetdata,
4509 sourcedata->var, sourcedata->vbdvar, sourcedata->vbdcoef, sourcedata->lhs, sourcedata->rhs) );
4510
4511 /* create target constraint */
4512 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
4513 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
4514 SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
4515 SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
4516 SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
4517
4518 /* catch events for variables */
4519 SCIP_CALL( catchEvents(scip, *targetcons, conshdlrdata->eventhdlr) );
4520
4521 return SCIP_OKAY;
4522}
4523
4524
4525/** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
4526static
4527SCIP_DECL_CONSINITLP(consInitlpVarbound)
4528{ /*lint --e{715}*/
4529 int i;
4530
4531 *infeasible = FALSE;
4532
4533 for( i = 0; i < nconss && !(*infeasible); i++ )
4534 {
4535 assert(SCIPconsIsInitial(conss[i]));
4536 SCIP_CALL( addRelaxation(scip, conss[i], infeasible) );
4537 }
4538
4539 return SCIP_OKAY;
4540}
4541
4542
4543/** separation method of constraint handler for LP solutions */
4544static
4545SCIP_DECL_CONSSEPALP(consSepalpVarbound)
4546{ /*lint --e{715}*/
4547 SCIP_CONSHDLRDATA* conshdlrdata;
4548 int i;
4549
4550 assert(conshdlr != NULL);
4551
4552 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4553 assert(conshdlrdata != NULL);
4554
4555 *result = SCIP_DIDNOTFIND;
4556
4557 /* separate useful constraints */
4558 for( i = 0; i < nusefulconss; ++i )
4559 {
4560 SCIP_CALL( separateCons(scip, conss[i], conshdlrdata->usebdwidening, NULL, result) );
4561 }
4562
4563 /* separate remaining constraints */
4564 for( i = nusefulconss; i < nconss && *result == SCIP_DIDNOTFIND; ++i )
4565 {
4566 SCIP_CALL( separateCons(scip, conss[i], conshdlrdata->usebdwidening, NULL, result) );
4567 }
4568
4569 return SCIP_OKAY;
4570}
4571
4572
4573/** separation method of constraint handler for arbitrary primal solutions */
4574static
4575SCIP_DECL_CONSSEPASOL(consSepasolVarbound)
4576{ /*lint --e{715}*/
4577 SCIP_CONSHDLRDATA* conshdlrdata;
4578 int i;
4579
4580 assert(conshdlr != NULL);
4581
4582 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4583 assert(conshdlrdata != NULL);
4584
4585 *result = SCIP_DIDNOTFIND;
4586
4587 /* separate useful constraints */
4588 for( i = 0; i < nusefulconss; ++i )
4589 {
4590 SCIP_CALL( separateCons(scip, conss[i], conshdlrdata->usebdwidening, sol, result) );
4591 }
4592
4593 /* separate remaining constraints */
4594 for( i = nusefulconss; i < nconss && *result == SCIP_DIDNOTFIND; ++i )
4595 {
4596 SCIP_CALL( separateCons(scip, conss[i], conshdlrdata->usebdwidening, sol, result) );
4597 }
4598
4599 return SCIP_OKAY;
4600}
4601
4602
4603/** constraint enforcing method of constraint handler for LP solutions */
4604static
4605SCIP_DECL_CONSENFOLP(consEnfolpVarbound)
4606{ /*lint --e{715}*/
4607 SCIP_CONSHDLRDATA* conshdlrdata;
4608 int i;
4609
4610 assert(conshdlr != NULL);
4611
4612 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4613 assert(conshdlrdata != NULL);
4614
4615 *result = SCIP_FEASIBLE;
4616
4617 for( i = 0; i < nconss; i++ )
4618 {
4619 if( !checkCons(scip, conss[i], NULL, FALSE) )
4620 {
4621 assert((*result) == SCIP_INFEASIBLE || (*result) == SCIP_FEASIBLE);
4622 (*result) = SCIP_INFEASIBLE;
4623
4624 SCIP_CALL( SCIPresetConsAge(scip, conss[i]) );
4625
4626 SCIP_CALL( separateCons(scip, conss[i], conshdlrdata->usebdwidening, NULL, result) );
4627 assert((*result) != SCIP_FEASIBLE);
4628
4629 if( (*result) != SCIP_INFEASIBLE )
4630 break;
4631 }
4632 else
4633 {
4634 /* increase age of constraint */
4635 SCIP_CALL( SCIPincConsAge(scip, conss[i]) );
4636 }
4637 }
4638
4639 return SCIP_OKAY;
4640}
4641
4642
4643/** constraint enforcing method of constraint handler for relaxation solutions */
4644static
4645SCIP_DECL_CONSENFORELAX(consEnforelaxVarbound)
4646{ /*lint --e{715}*/
4647 SCIP_CONSHDLRDATA* conshdlrdata;
4648 int i;
4649
4650 assert(conshdlr != NULL);
4651
4652 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4653 assert(conshdlrdata != NULL);
4654
4655 *result = SCIP_FEASIBLE;
4656
4657 for( i = 0; i < nconss; i++ )
4658 {
4659 if( !checkCons(scip, conss[i], sol, FALSE) )
4660 {
4661 assert((*result) == SCIP_INFEASIBLE || (*result) == SCIP_FEASIBLE);
4662 (*result) = SCIP_INFEASIBLE;
4663
4664 SCIP_CALL( SCIPresetConsAge(scip, conss[i]) );
4665
4666 SCIP_CALL( separateCons(scip, conss[i], conshdlrdata->usebdwidening, sol, result) );
4667 assert((*result) != SCIP_FEASIBLE);
4668
4669 if( (*result) != SCIP_INFEASIBLE )
4670 break;
4671 }
4672 else
4673 {
4674 /* increase age of constraint */
4675 SCIP_CALL( SCIPincConsAge(scip, conss[i]) );
4676 }
4677 }
4678
4679 return SCIP_OKAY;
4680}
4681
4682
4683/** constraint enforcing method of constraint handler for pseudo solutions */
4684static
4685SCIP_DECL_CONSENFOPS(consEnfopsVarbound)
4686{ /*lint --e{715}*/
4687 int i;
4688
4689 for( i = 0; i < nconss; i++ )
4690 {
4691 if( !checkCons(scip, conss[i], NULL, TRUE) )
4692 {
4693 SCIP_CALL( SCIPresetConsAge(scip, conss[i]) );
4694
4695 *result = SCIP_INFEASIBLE;
4696 return SCIP_OKAY;
4697 }
4698 else
4699 {
4700 /* increase age of constraint */
4701 SCIP_CALL( SCIPincConsAge(scip, conss[i]) );
4702 }
4703 }
4704 *result = SCIP_FEASIBLE;
4705
4706 return SCIP_OKAY;
4707}
4708
4709
4710/** feasibility check method of constraint handler for integral solutions */
4711static
4712SCIP_DECL_CONSCHECK(consCheckVarbound)
4713{ /*lint --e{715}*/
4714 int i;
4715
4716 *result = SCIP_FEASIBLE;
4717
4718 for( i = 0; i < nconss && (*result == SCIP_FEASIBLE || completely); i++ )
4719 {
4720 if( !checkCons(scip, conss[i], sol, checklprows) )
4721 {
4722 *result = SCIP_INFEASIBLE;
4723
4724 if( printreason )
4725 {
4726 SCIP_CONSDATA* consdata;
4727 SCIP_Real sum;
4728
4729 consdata = SCIPconsGetData(conss[i]);
4730 assert( consdata != NULL );
4731
4732 sum = SCIPgetSolVal(scip, sol, consdata->var) + consdata->vbdcoef * SCIPgetSolVal(scip, sol, consdata->vbdvar);
4733
4734 SCIP_CALL( SCIPprintCons(scip, conss[i], NULL) );
4735 SCIPinfoMessage(scip, NULL, ";\n");
4736
4737 if( !SCIPisFeasGE(scip, sum, consdata->lhs) )
4738 {
4739 SCIPinfoMessage(scip, NULL, "violation: left hand side is violated by %.15g\n", consdata->lhs - sum);
4740 }
4741 if( !SCIPisFeasLE(scip, sum, consdata->rhs) )
4742 {
4743 SCIPinfoMessage(scip, NULL, "violation: right hand side is violated by %.15g\n", sum - consdata->rhs);
4744 }
4745 }
4746 }
4747 }
4748
4749 return SCIP_OKAY;
4750}
4751
4752
4753/** domain propagation method of constraint handler */
4754static
4755SCIP_DECL_CONSPROP(consPropVarbound)
4756{ /*lint --e{715}*/
4757 SCIP_CONSHDLRDATA* conshdlrdata;
4758 SCIP_Bool cutoff;
4759 int nchgbds = 0;
4760 int nchgsides = 0;
4761 int i;
4762
4763 assert(conshdlr != NULL);
4764
4765 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4766 assert(conshdlrdata != NULL);
4767
4768 cutoff = FALSE;
4769
4770 SCIPdebugMsg(scip, "propagating %d variable bound constraints\n", nmarkedconss);
4771
4772 /* process constraints marked for propagation */
4773 for( i = 0; i < nmarkedconss && !cutoff; i++ )
4774 {
4775 SCIP_CALL( propagateCons(scip, conss[i], conshdlrdata->usebdwidening, &cutoff, &nchgbds, &nchgsides, NULL) );
4776 }
4777
4778 if( cutoff )
4779 *result = SCIP_CUTOFF;
4780 else if( nchgbds > 0 )
4781 *result = SCIP_REDUCEDDOM;
4782 else
4783 *result = SCIP_DIDNOTFIND;
4784
4785 return SCIP_OKAY;
4786}
4787
4788
4789/** presolving method of constraint handler */
4790static
4791SCIP_DECL_CONSPRESOL(consPresolVarbound)
4792{ /*lint --e{715}*/
4793 SCIP_CONSHDLRDATA* conshdlrdata;
4794 SCIP_CONS* cons;
4795 SCIP_CONSDATA* consdata;
4796 SCIP_Bool cutoff;
4797 int oldnchgbds;
4798 int oldndelconss;
4799 int oldnaddconss;
4800 int oldnchgcoefs;
4801 int oldnchgsides;
4802 int oldnaggrvars;
4803 int i;
4804
4805 assert(scip != NULL);
4806 assert(conshdlr != NULL);
4807 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4808 assert(result != NULL);
4809
4810 /* get constraint handler data */
4811 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4812 assert(conshdlrdata != NULL);
4813
4814 cutoff = FALSE;
4815 oldnchgbds = *nchgbds;
4816 oldndelconss = *ndelconss;
4817 oldnaddconss = *naddconss;
4818 oldnchgcoefs = *nchgcoefs;
4819 oldnchgsides = *nchgsides;
4820 oldnaggrvars = *naggrvars;
4821
4822 for( i = 0; i < nconss; i++ )
4823 {
4824 cons = conss[i];
4825 assert(cons != NULL);
4826
4827 assert(!SCIPconsIsModifiable(cons));
4828
4829 consdata = SCIPconsGetData(cons);
4830 assert(consdata != NULL);
4831
4832 if( i % 1000 == 0 && SCIPisStopped(scip) )
4833 break;
4834
4835 /* force presolving the constraint in the initial round */
4836 if( nrounds == 0 )
4837 consdata->presolved = FALSE;
4838
4839 if( consdata->presolved )
4840 continue;
4841 consdata->presolved = TRUE;
4842
4843 /* incorporate fixings and aggregations in constraint */
4844 SCIP_CALL( applyFixings(scip, cons, conshdlrdata->eventhdlr, &cutoff, nchgbds, ndelconss, naddconss) );
4845
4846 if( cutoff )
4847 break;
4848 if( !SCIPconsIsActive(cons) )
4849 continue;
4850
4851 /* propagate constraint */
4852 SCIP_CALL( propagateCons(scip, cons, conshdlrdata->usebdwidening, &cutoff, nchgbds, nchgsides, ndelconss) );
4853
4854 if( cutoff )
4855 break;
4856 if( !SCIPconsIsActive(cons) )
4857 continue;
4858
4859 /* tighten variable bound coefficient */
4860 SCIP_CALL( tightenCoefs(scip, cons, nchgcoefs, nchgsides, ndelconss, &cutoff, nchgbds) );
4861 if( cutoff )
4862 break;
4863 if( !SCIPconsIsActive(cons) )
4864 continue;
4865
4866 /* informs once variable x about a globally valid variable lower or upper bound */
4867 if( !consdata->varboundsadded )
4868 {
4869 SCIP_Bool infeasible;
4870 int nlocalchgbds;
4871 int localoldnchgbds;
4872
4873 localoldnchgbds = *nchgbds;
4874
4875 /* if lhs is finite, we have a variable lower bound: lhs <= x + c*y => x >= -c*y + lhs */
4876 if( !SCIPisInfinity(scip, -consdata->lhs) && !SCIPisInfinity(scip, REALABS(consdata->vbdcoef)) )
4877 {
4878 SCIPdebugMsg(scip, "adding variable lower bound <%s> >= %g<%s> + %g (and potentially also <%s> %s %g<%s> + %g)\n",
4879 SCIPvarGetName(consdata->var), -consdata->vbdcoef, SCIPvarGetName(consdata->vbdvar), consdata->lhs,
4880 SCIPvarGetName(consdata->vbdvar), (consdata->vbdcoef > 0 ? ">=" : "<="), 1.0/-consdata->vbdcoef,
4881 SCIPvarGetName(consdata->var), consdata->lhs/consdata->vbdcoef);
4882
4883 SCIP_CALL( SCIPaddVarVlb(scip, consdata->var, consdata->vbdvar, -consdata->vbdcoef, consdata->lhs,
4884 &infeasible, &nlocalchgbds) );
4885 assert(!infeasible);
4886
4887 *nchgbds += nlocalchgbds;
4888 }
4889
4890 /* if rhs is finite, we have a variable upper bound: x + c*y <= rhs => x <= -c*y + rhs */
4891 if( !SCIPisInfinity(scip, consdata->rhs) && !SCIPisInfinity(scip, REALABS(consdata->vbdcoef)) )
4892 {
4893 SCIPdebugMsg(scip, "adding variable upper bound <%s> <= %g<%s> + %g (and potentially also <%s> %s %g<%s> + %g)\n",
4894 SCIPvarGetName(consdata->var), -consdata->vbdcoef, SCIPvarGetName(consdata->vbdvar), consdata->rhs,
4895 SCIPvarGetName(consdata->vbdvar), (consdata->vbdcoef > 0 ? "<=" : ">="), 1.0/-consdata->vbdcoef,
4896 SCIPvarGetName(consdata->var), consdata->rhs/consdata->vbdcoef);
4897
4898 SCIP_CALL( SCIPaddVarVub(scip, consdata->var, consdata->vbdvar, -consdata->vbdcoef, consdata->rhs,
4899 &infeasible, &nlocalchgbds) );
4900 assert(!infeasible);
4901
4902 *nchgbds += nlocalchgbds;
4903 }
4904 consdata->varboundsadded = TRUE;
4905
4906 if( *nchgbds > localoldnchgbds )
4907 {
4908 /* tighten variable bound coefficient */
4909 SCIP_CALL( tightenCoefs(scip, cons, nchgcoefs, nchgsides, ndelconss, &cutoff, nchgbds) );
4910 if( cutoff )
4911 break;
4912 }
4913 }
4914 }
4915
4916 if( !cutoff )
4917 {
4918 /* for varbound constraint with two integer variables make coefficients integral */
4919 prettifyConss(scip, conss, nconss, nchgcoefs, nchgsides);
4920
4921 /* check if we can upgrade to a set-packing constraint */
4922 SCIP_CALL( upgradeConss(scip, conshdlrdata, conss, nconss, &cutoff, naggrvars, nchgbds, nchgcoefs, nchgsides, ndelconss, naddconss) );
4923
4924 if( !cutoff && conshdlrdata->presolpairwise && (presoltiming & SCIP_PRESOLTIMING_MEDIUM) != 0 )
4925 {
4926 /* preprocess pairs of variable bound constraints */
4927 SCIP_CALL( preprocessConstraintPairs(scip, conss, nconss, &cutoff, nchgbds, ndelconss, nchgcoefs, nchgsides) );
4928 }
4929 }
4930
4931 /* return the correct result code */
4932 if( cutoff )
4933 *result = SCIP_CUTOFF;
4934 else if( *nchgbds > oldnchgbds || *ndelconss > oldndelconss || *naddconss > oldnaddconss
4935 || *nchgcoefs > oldnchgcoefs || *nchgsides > oldnchgsides || *naggrvars > oldnaggrvars )
4936 *result = SCIP_SUCCESS;
4937 else
4938 *result = SCIP_DIDNOTFIND;
4939
4940 return SCIP_OKAY;
4941}
4942
4943
4944/** propagation conflict resolving method of constraint handler */
4945static
4946SCIP_DECL_CONSRESPROP(consRespropVarbound)
4947{ /*lint --e{715}*/
4948 SCIP_CONSHDLRDATA* conshdlrdata;
4949
4950 assert(conshdlr != NULL);
4951
4952 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4953 assert(conshdlrdata != NULL);
4954
4955 SCIP_CALL( resolvePropagation(scip, cons, infervar, (PROPRULE)inferinfo, boundtype, bdchgidx, relaxedbd, conshdlrdata->usebdwidening) );
4956
4957 *result = SCIP_SUCCESS;
4958
4959 return SCIP_OKAY;
4960}
4961
4962
4963/** variable rounding lock method of constraint handler */
4964static
4965SCIP_DECL_CONSLOCK(consLockVarbound)
4966{ /*lint --e{715}*/
4967 SCIP_CONSDATA* consdata;
4968
4969 consdata = SCIPconsGetData(cons);
4970 assert(consdata != NULL);
4971
4972 if( !SCIPisInfinity(scip, -consdata->lhs) )
4973 {
4974 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->var, locktype, nlockspos, nlocksneg) );
4975 if( consdata->vbdcoef > 0.0 )
4976 {
4977 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vbdvar, locktype, nlockspos, nlocksneg) );
4978 }
4979 else
4980 {
4981 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vbdvar, locktype, nlocksneg, nlockspos) );
4982 }
4983 }
4984
4985 if( !SCIPisInfinity(scip, consdata->rhs) )
4986 {
4987 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->var, locktype, nlocksneg, nlockspos) );
4988 if( consdata->vbdcoef > 0.0 )
4989 {
4990 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vbdvar, locktype, nlocksneg, nlockspos) );
4991 }
4992 else
4993 {
4994 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vbdvar, locktype, nlockspos, nlocksneg) );
4995 }
4996 }
4997
4998 return SCIP_OKAY;
4999}
5000
5001/** constraint activation notification method of constraint handler */
5002static
5003SCIP_DECL_CONSACTIVE(consActiveVarbound)
5004{ /*lint --e{715}*/
5006 {
5007 SCIP_CALL( addNlrow(scip, cons) );
5008 }
5009
5010 return SCIP_OKAY;
5011}
5012
5013/** constraint deactivation notification method of constraint handler */
5014static
5015SCIP_DECL_CONSDEACTIVE(consDeactiveVarbound)
5016{ /*lint --e{715}*/
5017 SCIP_CONSDATA* consdata;
5018
5019 assert(cons != NULL);
5020
5021 consdata = SCIPconsGetData(cons);
5022 assert(consdata != NULL);
5023
5024 /* remove row from NLP, if still in solving
5025 * if we are in exitsolve, the whole NLP will be freed anyway
5026 */
5027 if( SCIPgetStage(scip) == SCIP_STAGE_SOLVING && consdata->nlrow != NULL )
5028 {
5029 SCIP_CALL( SCIPdelNlRow(scip, consdata->nlrow) );
5030 }
5031
5032 return SCIP_OKAY;
5033}
5034
5035/** constraint display method of constraint handler */
5036static
5037SCIP_DECL_CONSPRINT(consPrintVarbound)
5038{ /*lint --e{715}*/
5039 SCIP_CONSDATA* consdata;
5040
5041 assert(scip != NULL);
5042 assert(conshdlr != NULL);
5043 assert(cons != NULL);
5044
5045 consdata = SCIPconsGetData(cons);
5046 assert(consdata != NULL);
5047
5048 /* print left hand side for ranged rows */
5049 if( !SCIPisInfinity(scip, -consdata->lhs)
5050 && !SCIPisInfinity(scip, consdata->rhs)
5051 && !SCIPisEQ(scip, consdata->lhs, consdata->rhs) )
5052 SCIPinfoMessage(scip, file, "%.15g <= ", consdata->lhs);
5053
5054 /* print coefficients and variables */
5055 SCIPinfoMessage(scip, file, "<%s>[%c] %+.15g<%s>[%c]", SCIPvarGetName(consdata->var),
5059 consdata->vbdcoef, SCIPvarGetName(consdata->vbdvar),
5063
5064 /* print right hand side */
5065 if( SCIPisEQ(scip, consdata->lhs, consdata->rhs) )
5066 SCIPinfoMessage(scip, file, " == %.15g", consdata->rhs);
5067 else if( !SCIPisInfinity(scip, consdata->rhs) )
5068 SCIPinfoMessage(scip, file, " <= %.15g", consdata->rhs);
5069 else if( !SCIPisInfinity(scip, -consdata->lhs) )
5070 SCIPinfoMessage(scip, file, " >= %.15g", consdata->lhs);
5071 else
5072 SCIPinfoMessage(scip, file, " [free]");
5073
5074 return SCIP_OKAY;
5075}
5076
5077/** constraint copying method of constraint handler */
5078static
5079SCIP_DECL_CONSCOPY(consCopyVarbound)
5080{ /*lint --e{715}*/
5081 SCIP_VAR** vars;
5082 SCIP_Real* coefs;
5083 const char* consname;
5084
5085 SCIP_CALL( SCIPallocBufferArray(scip, &vars, 2) );
5086 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, 2) );
5087
5088 vars[0] = SCIPgetVarVarbound(sourcescip, sourcecons);
5089 vars[1] = SCIPgetVbdvarVarbound(sourcescip, sourcecons);
5090
5091 coefs[0] = 1.0;
5092 coefs[1] = SCIPgetVbdcoefVarbound(sourcescip, sourcecons);
5093
5094 if( name != NULL )
5095 consname = name;
5096 else
5097 consname = SCIPconsGetName(sourcecons);
5098
5099 /* copy the varbound using the linear constraint copy method */
5100 SCIP_CALL( SCIPcopyConsLinear(scip, cons, sourcescip, consname, 2, vars, coefs,
5101 SCIPgetLhsVarbound(sourcescip, sourcecons), SCIPgetRhsVarbound(sourcescip, sourcecons), varmap, consmap,
5102 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode, global, valid) );
5103
5104 SCIPfreeBufferArray(scip, &coefs);
5105 SCIPfreeBufferArray(scip, &vars);
5106
5107 return SCIP_OKAY;
5108}
5109
5110/** constraint parsing method of constraint handler */
5111static
5112SCIP_DECL_CONSPARSE(consParseVarbound)
5113{ /*lint --e{715}*/
5114 SCIP_VAR** vars;
5115 SCIP_Real* coefs;
5116 SCIP_Real lhs;
5117 SCIP_Real rhs;
5118 char* endstr;
5119 int requiredsize;
5120 int nvars;
5121
5122 assert(scip != NULL);
5123 assert(success != NULL);
5124 assert(str != NULL);
5125 assert(name != NULL);
5126 assert(cons != NULL);
5127
5128 /* set left and right hand side to their default values */
5129 lhs = -SCIPinfinity(scip);
5130 rhs = SCIPinfinity(scip);
5131
5132 (*success) = FALSE;
5133
5134 /* return of string empty */
5135 if( !*str )
5136 return SCIP_OKAY;
5137
5138 /* ignore whitespace */
5139 SCIP_CALL( SCIPskipSpace((char**)&str) );
5140
5141 if( isdigit(str[0]) || ((str[0] == '-' || str[0] == '+') && isdigit(str[1])) )
5142 {
5143 if( !SCIPparseReal(scip, str, &lhs, &endstr) )
5144 {
5145 SCIPerrorMessage("error parsing left hand side\n");
5146 return SCIP_OKAY;
5147 }
5148
5149 /* ignore whitespace */
5150 SCIP_CALL( SCIPskipSpace(&endstr) );
5151
5152 if( endstr[0] != '<' || endstr[1] != '=' )
5153 {
5154 SCIPerrorMessage("missing \"<=\" after left hand side(, found %c%c)\n", endstr[0], endstr[1]);
5155 return SCIP_OKAY;
5156 }
5157
5158 SCIPdebugMsg(scip, "found left hand side <%g>\n", lhs);
5159
5160 /* it was indeed a left-hand-side, so continue parsing after it */
5161 str = endstr + 2;
5162 }
5163
5164 /* pares x + c*y as linear sum */
5165 SCIP_CALL( SCIPallocBufferArray(scip, &vars, 2) );
5166 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, 2) );
5167
5168 /* parse linear sum to get variables and coefficients */
5169 SCIP_CALL( SCIPparseVarsLinearsum(scip, str, vars, coefs, &nvars, 2, &requiredsize, &endstr, success) );
5170
5171 if( requiredsize == 2 && *success )
5172 {
5173 SCIP_Real value;
5174
5175 assert(nvars == 2);
5176 assert(SCIPisEQ(scip, coefs[0], 1.0));
5177
5178 SCIPdebugMsg(scip, "found linear sum <%s> + %g <%s>\n", SCIPvarGetName(vars[0]), coefs[1], SCIPvarGetName(vars[1]));
5179
5180 /* ignore whitespace */
5181 SCIP_CALL( SCIPskipSpace(&endstr) );
5182
5183 str = endstr;
5184
5185 if( *str != '\0' && *(str+1) != '\0' && SCIPparseReal(scip, str+2, &value, &endstr) )
5186 {
5187 /* search for end of linear sum: either '<=', '>=', '==', or '[free]' */
5188 switch( *str )
5189 {
5190 case '<':
5191 assert(str[1] == '=');
5192 rhs = value;
5193 break;
5194 case '=':
5195 assert(str[1] == '=');
5196 assert(SCIPisInfinity(scip, -lhs));
5197 lhs = value;
5198 rhs = value;
5199 break;
5200 case '>':
5201 assert(str[1] == '=');
5202 assert(SCIPisInfinity(scip, -lhs));
5203 lhs = value;
5204 break;
5205 default:
5206 SCIPerrorMessage("missing relation symbol after linear sum\n");
5207 *success = FALSE;
5208 }
5209 }
5210 else if( strncmp(str, "[free]", 6) != 0 )
5211 *success = FALSE;
5212 }
5213
5214 if( *success )
5215 {
5216 SCIP_CALL( SCIPcreateConsVarbound(scip, cons, name, vars[0], vars[1], coefs[1], lhs, rhs,
5217 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
5218 }
5219
5220 /* free buffer arrays */
5221 SCIPfreeBufferArray(scip, &coefs);
5222 SCIPfreeBufferArray(scip, &vars);
5223
5224 return SCIP_OKAY;
5225}
5226
5227/** constraint method of constraint handler which returns the variables (if possible) */
5228static
5229SCIP_DECL_CONSGETVARS(consGetVarsVarbound)
5230{ /*lint --e{715}*/
5231 assert( success != NULL );
5232
5233 if( varssize < 2 )
5234 (*success) = FALSE;
5235 else
5236 {
5237 SCIP_CONSDATA* consdata;
5238 assert(cons != NULL);
5239 assert(vars != NULL);
5240
5241 consdata = SCIPconsGetData(cons);
5242 assert(consdata != NULL);
5243
5244 vars[0] = consdata->var;
5245 vars[1] = consdata->vbdvar;
5246 (*success) = TRUE;
5247 }
5248
5249 return SCIP_OKAY;
5250}
5251
5252/** constraint method of constraint handler which returns the number of variables (if possible) */
5253static
5254SCIP_DECL_CONSGETNVARS(consGetNVarsVarbound)
5255{ /*lint --e{715}*/
5256 (*nvars) = 2;
5257 (*success) = TRUE;
5258
5259 return SCIP_OKAY;
5260}
5261
5262/** constraint handler method which returns the permutation symmetry detection graph of a constraint */
5263static
5264SCIP_DECL_CONSGETPERMSYMGRAPH(consGetPermsymGraphVarbound)
5265{ /*lint --e{715}*/
5266 SCIP_CALL( addSymmetryInformation(scip, SYM_SYMTYPE_PERM, cons, graph, success) );
5267
5268 return SCIP_OKAY;
5269}
5270
5271/** constraint handler method which returns the signed permutation symmetry detection graph of a constraint */
5272static
5273SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(consGetSignedPermsymGraphVarbound)
5274{ /*lint --e{715}*/
5275 SCIP_CALL( addSymmetryInformation(scip, SYM_SYMTYPE_SIGNPERM, cons, graph, success) );
5276
5277 return SCIP_OKAY;
5278}
5279
5280/*
5281 * Event Handler
5282 */
5283
5284/** execution method of bound change event handler */
5285static
5286SCIP_DECL_EVENTEXEC(eventExecVarbound)
5287{ /*lint --e{715}*/
5288 SCIP_CONS* cons;
5289 SCIP_CONSDATA* consdata;
5290
5291 assert(event != NULL);
5292 cons = (SCIP_CONS*)eventdata;
5293 assert(cons != NULL);
5294 consdata = SCIPconsGetData(cons);
5295 assert(consdata != NULL);
5296
5298 {
5299 consdata->presolved = FALSE;
5300 }
5301 else
5302 {
5303 assert((SCIPeventGetType(event) & SCIP_EVENTTYPE_BOUNDTIGHTENED) != 0);
5304
5305 consdata->presolved = FALSE;
5306 consdata->tightened = FALSE;
5307
5309 }
5310
5311 return SCIP_OKAY;
5312}
5313
5314/**@} */
5315
5316
5317/** creates the handler for variable bound constraints and includes it in SCIP */
5319 SCIP* scip /**< SCIP data structure */
5320 )
5321{
5322 SCIP_CONSHDLRDATA* conshdlrdata;
5323 SCIP_EVENTHDLR* eventhdlr;
5324 SCIP_CONSHDLR* conshdlr;
5325
5326 /* include event handler for bound change events */
5328 eventExecVarbound, NULL) );
5329
5330 /* create variable bound constraint handler data */
5331 SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlr) );
5332
5333 /* include constraint handler */
5336 consEnfolpVarbound, consEnfopsVarbound, consCheckVarbound, consLockVarbound,
5337 conshdlrdata) );
5338 assert(conshdlr != NULL);
5339
5340 /* set non-fundamental callbacks via specific setter functions */
5341 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyVarbound, consCopyVarbound) );
5342 SCIP_CALL( SCIPsetConshdlrActive(scip, conshdlr, consActiveVarbound) );
5343 SCIP_CALL( SCIPsetConshdlrDeactive(scip, conshdlr, consDeactiveVarbound) );
5344 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteVarbound) );
5345 SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolVarbound) );
5346 SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolVarbound) );
5347 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeVarbound) );
5348 SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsVarbound) );
5349 SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsVarbound) );
5350 SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpVarbound) );
5351 SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseVarbound) );
5353 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintVarbound) );
5356 SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropVarbound) );
5357 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpVarbound, consSepasolVarbound, CONSHDLR_SEPAFREQ,
5359 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransVarbound) );
5360 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxVarbound) );
5361 SCIP_CALL( SCIPsetConshdlrGetPermsymGraph(scip, conshdlr, consGetPermsymGraphVarbound) );
5362 SCIP_CALL( SCIPsetConshdlrGetSignedPermsymGraph(scip, conshdlr, consGetSignedPermsymGraphVarbound) );
5363
5364 if( SCIPfindConshdlr(scip,"linear") != NULL )
5365 {
5366 /* include the linear constraint to varbound constraint upgrade in the linear constraint handler */
5368 }
5369
5370 /* add varbound constraint handler parameters */
5372 "constraints/" CONSHDLR_NAME "/presolpairwise",
5373 "should pairwise constraint comparison be performed in presolving?",
5374 &conshdlrdata->presolpairwise, TRUE, DEFAULT_PRESOLPAIRWISE, NULL, NULL) );
5376 "constraints/" CONSHDLR_NAME "/maxlpcoef",
5377 "maximum coefficient in varbound constraint to be added as a row into LP",
5378 &conshdlrdata->maxlpcoef, TRUE, DEFAULT_MAXLPCOEF, 0.0, 1e+20, NULL, NULL) );
5380 "constraints/" CONSHDLR_NAME "/usebdwidening", "should bound widening be used in conflict analysis?",
5381 &conshdlrdata->usebdwidening, FALSE, DEFAULT_USEBDWIDENING, NULL, NULL) );
5382
5383 return SCIP_OKAY;
5384}
5385
5386/** creates and captures a variable bound constraint: lhs <= x + c*y <= rhs
5387 *
5388 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5389 */
5391 SCIP* scip, /**< SCIP data structure */
5392 SCIP_CONS** cons, /**< pointer to hold the created constraint */
5393 const char* name, /**< name of constraint */
5394 SCIP_VAR* var, /**< variable x that has variable bound */
5395 SCIP_VAR* vbdvar, /**< binary, integer or implicit integer bounding variable y */
5396 SCIP_Real vbdcoef, /**< coefficient c of bounding variable y */
5397 SCIP_Real lhs, /**< left hand side of variable bound inequality */
5398 SCIP_Real rhs, /**< right hand side of variable bound inequality */
5399 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
5400 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
5401 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
5402 * Usually set to TRUE. */
5403 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
5404 * TRUE for model constraints, FALSE for additional, redundant constraints. */
5405 SCIP_Bool check, /**< should the constraint be checked for feasibility?
5406 * TRUE for model constraints, FALSE for additional, redundant constraints. */
5407 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
5408 * Usually set to TRUE. */
5409 SCIP_Bool local, /**< is constraint only valid locally?
5410 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
5411 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
5412 * Usually set to FALSE. In column generation applications, set to TRUE if pricing
5413 * adds coefficients to this constraint. */
5414 SCIP_Bool dynamic, /**< is constraint subject to aging?
5415 * Usually set to FALSE. Set to TRUE for own cuts which
5416 * are separated as constraints. */
5417 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
5418 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
5419 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
5420 * if it may be moved to a more global node?
5421 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
5422 )
5423{
5424 SCIP_CONSHDLR* conshdlr;
5425 SCIP_CONSHDLRDATA* conshdlrdata;
5426 SCIP_CONSDATA* consdata;
5427
5428 /* find the variable bound constraint handler */
5429 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
5430 if( conshdlr == NULL )
5431 {
5432 SCIPerrorMessage("variable bound constraint handler not found\n");
5433 return SCIP_PLUGINNOTFOUND;
5434 }
5435
5436 conshdlrdata = SCIPconshdlrGetData(conshdlr);
5437 assert(conshdlrdata != NULL);
5438
5439 /* create constraint data */
5440 SCIP_CALL( consdataCreate(scip, &consdata, var, vbdvar, vbdcoef, lhs, rhs) );
5441
5442 /* create constraint */
5443 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
5444 local, modifiable, dynamic, removable, stickingatnode) );
5445
5446 if( SCIPisTransformed(scip) )
5447 {
5448 /* catch events for variables */
5449 SCIP_CALL( catchEvents(scip, *cons, conshdlrdata->eventhdlr) );
5450 }
5451
5452 return SCIP_OKAY;
5453}
5454
5455/** creates and captures a variable bound constraint: lhs <= x + c*y <= rhs
5456 * with all constraint flags set to their default values
5457 *
5458 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5459 */
5461 SCIP* scip, /**< SCIP data structure */
5462 SCIP_CONS** cons, /**< pointer to hold the created constraint */
5463 const char* name, /**< name of constraint */
5464 SCIP_VAR* var, /**< variable x that has variable bound */
5465 SCIP_VAR* vbdvar, /**< binary, integer or implicit integer bounding variable y */
5466 SCIP_Real vbdcoef, /**< coefficient c of bounding variable y */
5467 SCIP_Real lhs, /**< left hand side of variable bound inequality */
5468 SCIP_Real rhs /**< right hand side of variable bound inequality */
5469 )
5470{
5471 SCIP_CALL( SCIPcreateConsVarbound(scip, cons, name, var, vbdvar,vbdcoef, lhs, rhs,
5473
5474 return SCIP_OKAY;
5475}
5476
5477/** gets left hand side of variable bound constraint lhs <= x + c*y <= rhs */
5479 SCIP* scip, /**< SCIP data structure */
5480 SCIP_CONS* cons /**< constraint data */
5481 )
5482{
5483 SCIP_CONSDATA* consdata;
5484
5485 assert(scip != NULL);
5486
5487 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5488 {
5489 SCIPerrorMessage("constraint is not a variable bound constraint\n");
5490 SCIPABORT();
5491 return SCIP_INVALID; /*lint !e527*/
5492 }
5493
5494 consdata = SCIPconsGetData(cons);
5495 assert(consdata != NULL);
5496
5497 return consdata->lhs;
5498}
5499
5500/** gets right hand side of variable bound constraint lhs <= x + c*y <= rhs */
5502 SCIP* scip, /**< SCIP data structure */
5503 SCIP_CONS* cons /**< constraint data */
5504 )
5505{
5506 SCIP_CONSDATA* consdata;
5507
5508 assert(scip != NULL);
5509
5510 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5511 {
5512 SCIPerrorMessage("constraint is not a variable bound constraint\n");
5513 SCIPABORT();
5514 return SCIP_INVALID; /*lint !e527*/
5515 }
5516
5517 consdata = SCIPconsGetData(cons);
5518 assert(consdata != NULL);
5519
5520 return consdata->rhs;
5521}
5522
5523/** gets bounded variable x of variable bound constraint lhs <= x + c*y <= rhs */
5525 SCIP* scip, /**< SCIP data structure */
5526 SCIP_CONS* cons /**< constraint data */
5527 )
5528{
5529 SCIP_CONSDATA* consdata;
5530
5531 assert(scip != NULL);
5532
5533 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5534 {
5535 SCIPerrorMessage("constraint is not a variable bound constraint\n");
5536 SCIPABORT();
5537 return NULL; /*lint !e527*/
5538 }
5539
5540 consdata = SCIPconsGetData(cons);
5541 assert(consdata != NULL);
5542
5543 return consdata->var;
5544}
5545
5546/** gets bounding variable y of variable bound constraint lhs <= x + c*y <= rhs */
5548 SCIP* scip, /**< SCIP data structure */
5549 SCIP_CONS* cons /**< constraint data */
5550 )
5551{
5552 SCIP_CONSDATA* consdata;
5553
5554 assert(scip != NULL);
5555
5556 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5557 {
5558 SCIPerrorMessage("constraint is not a variable bound constraint\n");
5559 SCIPABORT();
5560 return NULL; /*lint !e527*/
5561 }
5562
5563 consdata = SCIPconsGetData(cons);
5564 assert(consdata != NULL);
5565
5566 return consdata->vbdvar;
5567}
5568
5569/** gets bound coefficient c of variable bound constraint lhs <= x + c*y <= rhs */
5571 SCIP* scip, /**< SCIP data structure */
5572 SCIP_CONS* cons /**< constraint data */
5573 )
5574{
5575 SCIP_CONSDATA* consdata;
5576
5577 assert(scip != NULL);
5578
5579 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5580 {
5581 SCIPerrorMessage("constraint is not a variable bound constraint\n");
5582 SCIPABORT();
5583 return SCIP_INVALID; /*lint !e527*/
5584 }
5585
5586 consdata = SCIPconsGetData(cons);
5587 assert(consdata != NULL);
5588
5589 return consdata->vbdcoef;
5590}
5591
5592/** gets the dual solution of the variable bound constraint in the current LP */
5594 SCIP* scip, /**< SCIP data structure */
5595 SCIP_CONS* cons /**< constraint data */
5596 )
5597{
5598 SCIP_CONSDATA* consdata;
5599
5600 assert(scip != NULL);
5601
5602 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5603 {
5604 SCIPerrorMessage("constraint is not a variable bound constraint\n");
5605 SCIPABORT();
5606 return SCIP_INVALID; /*lint !e527*/
5607 }
5608
5609 consdata = SCIPconsGetData(cons);
5610 assert(consdata != NULL);
5611
5612 if( consdata->row != NULL )
5613 return SCIProwGetDualsol(consdata->row);
5614 else
5615 return 0.0;
5616}
5617
5618/** gets the dual Farkas value of the variable bound constraint in the current infeasible LP */
5620 SCIP* scip, /**< SCIP data structure */
5621 SCIP_CONS* cons /**< constraint data */
5622 )
5623{
5624 SCIP_CONSDATA* consdata;
5625
5626 assert(scip != NULL);
5627
5628 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5629 {
5630 SCIPerrorMessage("constraint is not a variable bound constraint\n");
5631 SCIPABORT();
5632 return SCIP_INVALID; /*lint !e527*/
5633 }
5634
5635 consdata = SCIPconsGetData(cons);
5636 assert(consdata != NULL);
5637
5638 if( consdata->row != NULL )
5639 return SCIProwGetDualfarkas(consdata->row);
5640 else
5641 return 0.0;
5642}
5643
5644/** returns the linear relaxation of the given variable bound constraint; may return NULL if no LP row was yet created;
5645 * the user must not modify the row!
5646 */
5648 SCIP* scip, /**< SCIP data structure */
5649 SCIP_CONS* cons /**< constraint data */
5650 )
5651{
5652 SCIP_CONSDATA* consdata;
5653
5654 assert(scip != NULL);
5655
5656 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5657 {
5658 SCIPerrorMessage("constraint is not a variable bound constraint\n");
5659 SCIPABORT();
5660 return NULL; /*lint !e527*/
5661 }
5662
5663 consdata = SCIPconsGetData(cons);
5664 assert(consdata != NULL);
5665
5666 return consdata->row;
5667}
5668
5669/** cleans up (multi-)aggregations and fixings from varbound constraints */
5671 SCIP* scip, /**< SCIP data structure */
5672 SCIP_Bool onlychecked, /**< should only checked constraints be cleaned up? */
5673 SCIP_Bool* infeasible, /**< pointer to return whether the problem was detected to be infeasible */
5674 int* naddconss, /**< pointer to count number of added (linear) constraints */
5675 int* ndelconss, /**< pointer to count number of deleted (varbound) constraints */
5676 int* nchgbds /**< pointer to count number of bound changes */
5677 )
5678{
5679 SCIP_CONSHDLR* conshdlr;
5680 SCIP_CONSHDLRDATA* conshdlrdata;
5681 SCIP_EVENTHDLR* eventhdlr;
5682 SCIP_CONS** conss;
5683 int nconss;
5684 int i;
5685
5686 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
5687 if( conshdlr == NULL )
5688 return SCIP_OKAY;
5689
5690 assert(infeasible != NULL);
5691 *infeasible = FALSE;
5692
5693 assert(naddconss != NULL);
5694 assert(ndelconss != NULL);
5695 assert(nchgbds != NULL);
5696
5697 conshdlrdata = SCIPconshdlrGetData(conshdlr);
5698 assert(conshdlrdata != NULL);
5699
5700 eventhdlr = conshdlrdata->eventhdlr;
5701 nconss = onlychecked ? SCIPconshdlrGetNCheckConss(conshdlr) : SCIPconshdlrGetNActiveConss(conshdlr);
5702 conss = onlychecked ? SCIPconshdlrGetCheckConss(conshdlr) : SCIPconshdlrGetConss(conshdlr);
5703
5704 /* loop backwards since then deleted constraints do not interfere with the loop */
5705 for( i = nconss - 1; i >= 0; --i )
5706 {
5707 SCIP_CALL( applyFixings(scip, conss[i], eventhdlr, infeasible, nchgbds, ndelconss, naddconss) );
5708
5709 if( *infeasible )
5710 break;
5711 }
5712
5713 return SCIP_OKAY;
5714}
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:267
#define SCIP_Longint
Definition: def.h:158
#define SCIP_VARTYPE_INTEGER_CHAR
Definition: def.h:145
#define SCIP_VARTYPE_IMPLINT_CHAR
Definition: def.h:146
#define SCIP_INVALID
Definition: def.h:193
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define SCIP_UNKNOWN
Definition: def.h:194
#define ABS(x)
Definition: def.h:235
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_VARTYPE_BINARY_CHAR
Definition: def.h:144
#define SCIP_VARTYPE_CONTINUOUS_CHAR
Definition: def.h:147
#define SCIPABORT()
Definition: def.h:346
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:374
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:9409
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:596
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:724
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
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:3474
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:9394
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition: misc.c:11184
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:1217
void SCIPupdateSolLPConsViolation(SCIP *scip, SCIP_SOL *sol, SCIP_Real absviol, SCIP_Real relviol)
Definition: scip_sol.c:141
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)
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:5203
SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:4351
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17599
SCIP_RETCODE SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6348
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4676
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17538
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3353
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
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:8401
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:5615
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4766
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17926
SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition: var.c:12218
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5320
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
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:18088
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:6720
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17758
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4259
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:6661
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:4437
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
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:4645
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:4613
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17610
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:18134
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8276
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:5501
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:6228
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
SCIP_RETCODE SCIPskipSpace(char **s)
Definition: misc.c:10866
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