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