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