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_bounddisjunction.c 26 * @ingroup DEFPLUGINS_CONS 27 * @brief constraint handler for bound disjunction constraints \f$(x_1 \{\leq,\geq\} b_1) \vee \ldots \vee (x_n \{\leq,\geq\} b_n)\f$ 28 * @author Tobias Achterberg 29 * @author Marc Pfetsch 30 */ 31 32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 33 34 #include "blockmemshell/memory.h" 35 #include "scip/cons_bounddisjunction.h" 36 #include "scip/cons_linear.h" 37 #include "scip/cons_logicor.h" 38 #include "scip/cons_setppc.h" 39 #include "scip/expr_pow.h" 40 #include "scip/expr_var.h" 41 #include "scip/pub_conflict.h" 42 #include "scip/pub_cons.h" 43 #include "scip/pub_event.h" 44 #include "scip/pub_lp.h" 45 #include "scip/pub_message.h" 46 #include "scip/pub_misc.h" 47 #include "scip/pub_var.h" 48 #include "scip/scip_branch.h" 49 #include "scip/scip_conflict.h" 50 #include "scip/scip_cons.h" 51 #include "scip/scip_copy.h" 52 #include "scip/scip_event.h" 53 #include "scip/scip_expr.h" 54 #include "scip/scip_general.h" 55 #include "scip/scip_mem.h" 56 #include "scip/scip_message.h" 57 #include "scip/scip_nlp.h" 58 #include "scip/scip_numerics.h" 59 #include "scip/scip_param.h" 60 #include "scip/scip_prob.h" 61 #include "scip/scip_probing.h" 62 #include "scip/scip_sol.h" 63 #include "scip/scip_solvingstats.h" 64 #include "scip/scip_tree.h" 65 #include "scip/scip_var.h" 66 #include "scip/symmetry_graph.h" 67 #include "symmetry/struct_symmetry.h" 68 #include <string.h> 69 70 /**@name Constraint handler properties 71 * 72 * @{ 73 */ 74 #define CONSHDLR_NAME "bounddisjunction" 75 #define CONSHDLR_DESC "bound disjunction constraints" 76 #define CONSHDLR_ENFOPRIORITY -3000000 /**< priority of the constraint handler for constraint enforcing */ 77 #define CONSHDLR_CHECKPRIORITY -3000000 /**< priority of the constraint handler for checking feasibility */ 78 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */ 79 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation, 80 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */ 81 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */ 82 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */ 83 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */ 84 85 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FAST 86 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP 87 88 /**@} */ 89 90 /**@name Event handler properties 91 * 92 * @{ 93 */ 94 95 #define EVENTHDLR_NAME "bounddisjunction" 96 #define EVENTHDLR_DESC "event handler for bound disjunction constraints" 97 98 /**@} */ 99 100 /**@name Conflict handler properties 101 * 102 * @{ 103 */ 104 105 #define CONFLICTHDLR_NAME "bounddisjunction" 106 #define CONFLICTHDLR_DESC "conflict handler creating bound disjunction constraints" 107 #define CONFLICTHDLR_PRIORITY -3000000 108 109 /**@} */ 110 111 /**@name Default parameter values 112 * 113 * @{ 114 */ 115 116 #define DEFAULT_CONTINUOUSFRAC 0.4 /**< maximal percantage of continuous variables within a conflict */ 117 118 /**@} */ 119 120 /**@name Age increase defines 121 * 122 * @{ 123 */ 124 125 /* @todo make this a parameter setting */ 126 #if 1 /* @todo test which AGEINCREASE formula is better! */ 127 #define AGEINCREASE(n) (1.0 + 0.2*n) 128 #else 129 #define AGEINCREASE(n) (0.1*n) 130 #endif 131 132 /**@} */ 133 134 135 /**@name Comparison for two values 136 * 137 * @{ 138 */ 139 140 #ifdef SCIP_DISABLED_CODE /* These only work if one also passes integral values in case of integral variables. This is not always the case and not even asserted. */ 141 /** use defines for numeric compare methods to be slightly faster for integral values */ 142 #define isFeasLT(scip, var, val1, val2) (SCIPvarIsIntegral(var) ? (val2) - (val1) > 0.5 : SCIPisFeasLT(scip, val1, val2)) 143 #define isFeasLE(scip, var, val1, val2) (SCIPvarIsIntegral(var) ? (val2) - (val1) > -0.5 : SCIPisFeasLE(scip, val1, val2)) 144 #define isFeasGT(scip, var, val1, val2) (SCIPvarIsIntegral(var) ? (val1) - (val2) > 0.5 : SCIPisFeasGT(scip, val1, val2)) 145 #define isFeasGE(scip, var, val1, val2) (SCIPvarIsIntegral(var) ? (val1) - (val2) > -0.5 : SCIPisFeasGE(scip, val1, val2)) 146 #else 147 #define isFeasLT(scip, var, val1, val2) SCIPisFeasLT(scip, val1, val2) 148 #define isFeasLE(scip, var, val1, val2) SCIPisFeasLE(scip, val1, val2) 149 #define isFeasGT(scip, var, val1, val2) SCIPisFeasGT(scip, val1, val2) 150 #define isFeasGE(scip, var, val1, val2) SCIPisFeasGE(scip, val1, val2) 151 #endif 152 /**@} */ 153 154 155 /** constraint handler data */ 156 struct SCIP_ConshdlrData 157 { 158 SCIP_EVENTHDLR* eventhdlr; /**< event handler for events on watched variables */ 159 }; 160 161 /** bound disjunction constraint data */ 162 struct SCIP_ConsData 163 { 164 SCIP_VAR** vars; /**< variables of the literals in the constraint */ 165 SCIP_BOUNDTYPE* boundtypes; /**< types of bounds of the literals (lower or upper bounds) */ 166 SCIP_Real* bounds; /**< bounds of the literals */ 167 int varssize; /**< size of vars, boundtypes, and bounds arrays */ 168 int nvars; /**< number of variables in the constraint */ 169 int watchedvar1; /**< position of the first watched variable */ 170 int watchedvar2; /**< position of the second watched variable */ 171 int filterpos1; /**< event filter position of first watched variable */ 172 int filterpos2; /**< event filter position of second watched variable */ 173 }; 174 175 /**@name Local methods 176 * 177 * @{ 178 */ 179 180 /** adds rounding locks for the given variable in the given bound disjunction constraint */ 181 static 182 SCIP_RETCODE lockRounding( 183 SCIP* scip, /**< SCIP data structure */ 184 SCIP_CONS* cons, /**< bound disjunction constraint */ 185 SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */ 186 int pos /**< position of the variable in the constraint */ 187 ) 188 { 189 assert(consdata != NULL); 190 assert(0 <= pos && pos < consdata->nvars); 191 192 if( consdata->boundtypes[pos] == SCIP_BOUNDTYPE_LOWER ) 193 { 194 SCIP_CALL( SCIPlockVarCons(scip, consdata->vars[pos], cons, TRUE, FALSE) ); 195 } 196 else 197 { 198 SCIP_CALL( SCIPlockVarCons(scip, consdata->vars[pos], cons, FALSE, TRUE) ); 199 } 200 201 return SCIP_OKAY; 202 } 203 204 /** removes rounding locks for the given variable in the given bound disjunction constraint */ 205 static 206 SCIP_RETCODE unlockRounding( 207 SCIP* scip, /**< SCIP data structure */ 208 SCIP_CONS* cons, /**< bound disjunction constraint */ 209 SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */ 210 int pos /**< position of the variable in the constraint */ 211 ) 212 { 213 assert(consdata != NULL); 214 assert(0 <= pos && pos < consdata->nvars); 215 216 if( consdata->boundtypes[pos] == SCIP_BOUNDTYPE_LOWER ) 217 { 218 SCIP_CALL( SCIPunlockVarCons(scip, consdata->vars[pos], cons, TRUE, FALSE) ); 219 } 220 else 221 { 222 SCIP_CALL( SCIPunlockVarCons(scip, consdata->vars[pos], cons, FALSE, TRUE) ); 223 } 224 225 return SCIP_OKAY; 226 } 227 228 /** catches the events on a single variable of the bound disjunction constraint */ 229 static 230 SCIP_RETCODE catchEvents( 231 SCIP* scip, /**< SCIP data structure */ 232 SCIP_CONS* cons, /**< bound disjunction constraint */ 233 SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */ 234 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */ 235 int pos, /**< position of the variable in the constraint */ 236 int* filterpos /**< pointer to store position of event filter entry, or NULL */ 237 ) 238 { 239 assert(consdata != NULL); 240 assert(0 <= pos && pos < consdata->nvars); 241 242 if( consdata->boundtypes[pos] == SCIP_BOUNDTYPE_LOWER ) 243 { 244 SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[pos], SCIP_EVENTTYPE_UBTIGHTENED | SCIP_EVENTTYPE_LBRELAXED, 245 eventhdlr, (SCIP_EVENTDATA*)cons, filterpos) ); 246 } 247 else 248 { 249 SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[pos], SCIP_EVENTTYPE_LBTIGHTENED | SCIP_EVENTTYPE_UBRELAXED, 250 eventhdlr, (SCIP_EVENTDATA*)cons, filterpos) ); 251 } 252 253 return SCIP_OKAY; 254 } 255 256 /** drops the events on a single variable of the bound disjunction constraint */ 257 static 258 SCIP_RETCODE dropEvents( 259 SCIP* scip, /**< SCIP data structure */ 260 SCIP_CONS* cons, /**< bound disjunction constraint */ 261 SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */ 262 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */ 263 int pos, /**< position of the variable in the constraint */ 264 int filterpos /**< position of event filter entry returned by SCIPcatchVarEvent(), or -1 */ 265 ) 266 { 267 assert(consdata != NULL); 268 assert(0 <= pos && pos < consdata->nvars); 269 270 if( consdata->boundtypes[pos] == SCIP_BOUNDTYPE_LOWER ) 271 { 272 SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[pos], SCIP_EVENTTYPE_UBTIGHTENED | SCIP_EVENTTYPE_LBRELAXED, 273 eventhdlr, (SCIP_EVENTDATA*)cons, filterpos) ); 274 } 275 else 276 { 277 SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[pos], SCIP_EVENTTYPE_LBTIGHTENED | SCIP_EVENTTYPE_UBRELAXED, 278 eventhdlr, (SCIP_EVENTDATA*)cons, filterpos) ); 279 } 280 281 return SCIP_OKAY; 282 } 283 284 /** creates constraint handler data for bound disjunction constraint handler */ 285 static 286 SCIP_RETCODE conshdlrdataCreate( 287 SCIP* scip, /**< SCIP data structure */ 288 SCIP_CONSHDLRDATA** conshdlrdata, /**< pointer to store the constraint handler data */ 289 SCIP_EVENTHDLR* eventhdlr /**< event handler */ 290 ) 291 { 292 assert(scip != NULL); 293 assert(conshdlrdata != NULL); 294 assert(eventhdlr != NULL); 295 296 SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) ); 297 298 /* set event handler for catching events on watched variables */ 299 (*conshdlrdata)->eventhdlr = eventhdlr; 300 301 return SCIP_OKAY; 302 } 303 304 /** frees constraint handler data for bound disjunction constraint handler */ 305 static 306 void conshdlrdataFree( 307 SCIP* scip, /**< SCIP data structure */ 308 SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to the constraint handler data */ 309 ) 310 { 311 assert(conshdlrdata != NULL); 312 assert(*conshdlrdata != NULL); 313 314 SCIPfreeBlockMemory(scip, conshdlrdata); 315 } 316 317 /** creates a bound disjunction constraint data object */ 318 static 319 SCIP_RETCODE consdataCreate( 320 SCIP* scip, /**< SCIP data structure */ 321 SCIP_CONSDATA** consdata, /**< pointer to store the bound disjunction constraint data */ 322 int nvars, /**< number of variables in the constraint */ 323 SCIP_VAR** vars, /**< variables of the literals in the constraint */ 324 SCIP_BOUNDTYPE* boundtypes, /**< types of bounds of the literals (lower or upper bounds) */ 325 SCIP_Real* bounds /**< bounds of the literals */ 326 ) 327 { 328 assert(consdata != NULL); 329 assert(nvars == 0 || vars != NULL); 330 assert(nvars == 0 || boundtypes != NULL); 331 assert(nvars == 0 || bounds != NULL); 332 333 SCIP_CALL( SCIPallocBlockMemory(scip, consdata) ); 334 335 if( nvars > 0 ) 336 { 337 if( SCIPisConsCompressionEnabled(scip) ) 338 { 339 int k; 340 int v; 341 #ifndef NDEBUG 342 int nviolations = 0; 343 #endif 344 SCIP_Bool redundant; 345 SCIP_VAR** varsbuffer; 346 SCIP_BOUNDTYPE* boundtypesbuffer; 347 SCIP_Real* boundsbuffer; 348 349 SCIP_CALL( SCIPallocBufferArray(scip, &varsbuffer, nvars) ); 350 SCIP_CALL( SCIPallocBufferArray(scip, &boundtypesbuffer, nvars) ); 351 SCIP_CALL( SCIPallocBufferArray(scip, &boundsbuffer, nvars) ); 352 353 k = 0; 354 redundant = FALSE; 355 /* loop over variables, compare fixed ones against its bound disjunction */ 356 for( v = 0; v < nvars && !redundant; ++v ) 357 { 358 SCIP_VAR* var = vars[v]; 359 SCIP_BOUNDTYPE boundtype = boundtypes[v]; 360 SCIP_Real bound = bounds[v]; 361 362 /* is the variable fixed? */ 363 if( SCIPisEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var)) ) 364 { 365 if( (boundtype == SCIP_BOUNDTYPE_LOWER && isFeasGE(scip, var, SCIPvarGetLbLocal(var), bound)) 366 || (boundtype == SCIP_BOUNDTYPE_UPPER && isFeasLE(scip, var, SCIPvarGetUbLocal(var), bound)) ) 367 { 368 /* save this feasible assignment at the first position */ 369 varsbuffer[0] = var; 370 boundtypesbuffer[0] = boundtype; 371 boundsbuffer[0] = bound; 372 k = 1; 373 redundant = TRUE; 374 } 375 #ifndef NDEBUG 376 else 377 ++nviolations; 378 #endif 379 } 380 else 381 { 382 /* append unfixed variable to buffer */ 383 varsbuffer[k] = var; 384 boundtypesbuffer[k] = boundtype; 385 boundsbuffer[k] = bound; 386 ++k; 387 } 388 } 389 390 /* duplicate a single, infeasible assignment, wlog the first one */ 391 if( k == 0 ) 392 { 393 assert(nviolations == nvars); 394 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, vars, 1) ); 395 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->boundtypes, boundtypes, 1) ); 396 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->bounds, bounds, 1) ); 397 (*consdata)->varssize = 1; 398 (*consdata)->nvars = 1; 399 } 400 else 401 { 402 /* if the bound disjunction is already trivially satisfied, we keep only a single feasible assignment */ 403 assert(!redundant || k == 1); 404 405 /* we only copy the buffered variables required to represent the constraint */ 406 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, varsbuffer, k) ); 407 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->boundtypes, boundtypesbuffer, k) ); 408 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->bounds, boundsbuffer, k) ); 409 (*consdata)->varssize = k; 410 (*consdata)->nvars = k; 411 } 412 413 /* free buffer storage */ 414 SCIPfreeBufferArray(scip, &boundsbuffer); 415 SCIPfreeBufferArray(scip, &boundtypesbuffer); 416 SCIPfreeBufferArray(scip, &varsbuffer); 417 } 418 else 419 { 420 /* without problem compression, the entire vars array is copied */ 421 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, vars, nvars) ); 422 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->boundtypes, boundtypes, nvars) ); 423 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->bounds, bounds, nvars) ); 424 (*consdata)->varssize = nvars; 425 (*consdata)->nvars = nvars; 426 } 427 } 428 else 429 { 430 (*consdata)->vars = NULL; 431 (*consdata)->boundtypes = NULL; 432 (*consdata)->bounds = NULL; 433 (*consdata)->varssize = 0; 434 (*consdata)->nvars = 0; 435 } 436 (*consdata)->watchedvar1 = -1; 437 (*consdata)->watchedvar2 = -1; 438 (*consdata)->filterpos1 = -1; 439 (*consdata)->filterpos2 = -1; 440 441 /* get transformed variables, if we are in the transformed problem */ 442 if( SCIPisTransformed(scip) ) 443 { 444 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) ); 445 } 446 447 return SCIP_OKAY; 448 } 449 450 /** creates a bound disjunction constraint data object with possibly redundant literals */ 451 static 452 SCIP_RETCODE consdataCreateRedundant( 453 SCIP* scip, /**< SCIP data structure */ 454 SCIP_CONSDATA** consdata, /**< pointer to store the bound disjunction constraint data */ 455 int nvars, /**< number of variables in the constraint */ 456 SCIP_VAR** vars, /**< variables of the literals in the constraint */ 457 SCIP_BOUNDTYPE* boundtypes, /**< types of bounds of the literals (lower or upper bounds) */ 458 SCIP_Real* bounds /**< bounds of the literals */ 459 ) 460 { 461 assert(consdata != NULL); 462 assert(nvars == 0 || vars != NULL); 463 assert(nvars == 0 || boundtypes != NULL); 464 assert(nvars == 0 || bounds != NULL); 465 466 SCIP_CALL( SCIPallocBlockMemory(scip, consdata) ); 467 468 if( nvars > 0 ) 469 { 470 SCIP_BOUNDTYPE* boundtypesbuffer; 471 SCIP_Real* boundsbuffer; 472 SCIP_VAR** varsbuffer; 473 SCIP_VAR* var; 474 int nvarsbuffer = 0; 475 int nviolated = 0; 476 int v; 477 478 SCIP_CALL( SCIPduplicateBufferArray(scip, &varsbuffer, vars, nvars) ); 479 SCIP_CALL( SCIPduplicateBufferArray(scip, &boundtypesbuffer, boundtypes, nvars) ); 480 SCIP_CALL( SCIPduplicateBufferArray(scip, &boundsbuffer, bounds, nvars) ); 481 482 /* sort variables according to index; this allows us to check for redundancy easily below because duplicate 483 * variables must now appear consecutively */ 484 SCIPsortPtrRealInt((void**)varsbuffer, boundsbuffer, (int*) boundtypesbuffer, SCIPvarComp, nvars); 485 486 /* filter out redundant literals */ 487 for( v = 0; v < nvars; ++v ) 488 { 489 int w; 490 491 /* if we should compress fixed variables */ 492 if( SCIPisConsCompressionEnabled(scip) && varsbuffer[v] != NULL ) 493 { 494 var = varsbuffer[v]; 495 496 /* if the variable is fixed */ 497 if( SCIPisEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var)) ) 498 { 499 /* If the literal is feasible for the fixed variable, then the whole constraint is feasible. In this 500 * case, we reduce the constraint to only this literal. */ 501 if( (boundtypesbuffer[v] == SCIP_BOUNDTYPE_LOWER && isFeasGE(scip, var, SCIPvarGetLbLocal(var), boundsbuffer[v])) 502 || (boundtypesbuffer[v] == SCIP_BOUNDTYPE_UPPER && isFeasLE(scip, var, SCIPvarGetUbLocal(var), boundsbuffer[v])) ) 503 { 504 /* save this feasible assignment at the first position */ 505 varsbuffer[0] = var; 506 boundtypesbuffer[0] = boundtypesbuffer[v]; 507 boundsbuffer[0] = boundsbuffer[v]; 508 nvarsbuffer = 1; 509 break; 510 } 511 else 512 { 513 /* otherwise the literal is violated - we skip the literal */ 514 ++nviolated; 515 continue; 516 } 517 } 518 } 519 520 /* check subsequent variables with the same variable for redundancy */ 521 for( w = v + 1; w < nvars && varsbuffer[v] == varsbuffer[w]; ++w ) 522 { 523 if( boundtypesbuffer[v] == boundtypesbuffer[w] ) 524 { 525 if( boundtypesbuffer[v] == SCIP_BOUNDTYPE_LOWER ) 526 { 527 /* check whether current bound is as strong */ 528 if( SCIPisLE(scip, boundsbuffer[v], boundsbuffer[w]) ) 529 varsbuffer[v] = NULL; /* skip current bound */ 530 else 531 varsbuffer[w] = NULL; /* remove later bound */ 532 } 533 else 534 { 535 assert(boundtypesbuffer[v] == SCIP_BOUNDTYPE_UPPER); 536 537 /* check whether current bound is as strong */ 538 if( SCIPisGE(scip, boundsbuffer[v], boundsbuffer[w]) ) 539 varsbuffer[v] = NULL; /* skip current bound */ 540 else 541 varsbuffer[w] = NULL; /* remove later bound */ 542 } 543 } 544 } 545 546 /* keep current bound if it is not redundant (possibly redundant variable w is treated later) */ 547 if( varsbuffer[v] != NULL ) 548 { 549 /* switch last and current bound */ 550 varsbuffer[nvarsbuffer] = varsbuffer[v]; 551 boundtypesbuffer[nvarsbuffer] = boundtypesbuffer[v]; 552 boundsbuffer[nvarsbuffer] = boundsbuffer[v]; 553 ++nvarsbuffer; 554 } 555 } 556 assert( nvarsbuffer > 0 || SCIPisConsCompressionEnabled(scip) ); /* no variables can only happen if compression is enabled */ 557 558 #ifndef NDEBUG 559 /* if there are no variables left, this is because all literals are infeasible */ 560 if( nvarsbuffer == 0 ) 561 { 562 for( v = 0; v < nvars; v++ ) 563 { 564 var = vars[v]; 565 assert( SCIPisEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var)) ); 566 assert( (boundtypes[v] == SCIP_BOUNDTYPE_LOWER && isFeasLT(scip, var, SCIPvarGetLbLocal(var), bounds[v])) 567 || (boundtypes[v] == SCIP_BOUNDTYPE_UPPER && isFeasGT(scip, var, SCIPvarGetUbLocal(var), bounds[v])) ); 568 } 569 } 570 else 571 { 572 /* check that the literals are not redundant */ 573 for( v = 0; v < nvarsbuffer; v++ ) 574 { 575 int v2; 576 assert(varsbuffer[v] != NULL); 577 for( v2 = v+1; v2 < nvarsbuffer; v2++ ) 578 assert(varsbuffer[v] != varsbuffer[v2] || boundtypesbuffer[v] != boundtypesbuffer[v2]); 579 } 580 } 581 #endif 582 583 /* if all literals are infeasible, we keep the first */ 584 if( SCIPisConsCompressionEnabled(scip) && nviolated > 0 && nvarsbuffer == 0 ) 585 nvarsbuffer = 1; 586 587 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, varsbuffer, nvarsbuffer) ); 588 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->boundtypes, boundtypesbuffer, nvarsbuffer) ); 589 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->bounds, boundsbuffer, nvarsbuffer) ); 590 (*consdata)->varssize = nvarsbuffer; 591 (*consdata)->nvars = nvarsbuffer; 592 593 /* free buffer storage */ 594 SCIPfreeBufferArray(scip, &boundsbuffer); 595 SCIPfreeBufferArray(scip, &boundtypesbuffer); 596 SCIPfreeBufferArray(scip, &varsbuffer); 597 } 598 else 599 { 600 (*consdata)->vars = NULL; 601 (*consdata)->boundtypes = NULL; 602 (*consdata)->bounds = NULL; 603 (*consdata)->varssize = 0; 604 (*consdata)->nvars = 0; 605 } 606 (*consdata)->watchedvar1 = -1; 607 (*consdata)->watchedvar2 = -1; 608 (*consdata)->filterpos1 = -1; 609 (*consdata)->filterpos2 = -1; 610 611 /* get transformed variables, if we are in the transformed problem */ 612 if( SCIPisTransformed(scip) ) 613 { 614 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) ); 615 } 616 617 return SCIP_OKAY; 618 } 619 620 /** frees a bound disjunction constraint data */ 621 static 622 void consdataFree( 623 SCIP* scip, /**< SCIP data structure */ 624 SCIP_CONSDATA** consdata /**< pointer to the bound disjunction constraint */ 625 ) 626 { 627 assert(consdata != NULL); 628 assert(*consdata != NULL); 629 630 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->vars, (*consdata)->varssize); 631 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->boundtypes, (*consdata)->varssize); 632 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->bounds, (*consdata)->varssize); 633 SCIPfreeBlockMemory(scip, consdata); 634 } 635 636 /** prints bound disjunction constraint to file stream */ 637 static 638 void consdataPrint( 639 SCIP* scip, /**< SCIP data structure */ 640 SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */ 641 FILE* file, /**< output file (or NULL for standard output) */ 642 SCIP_Bool endline /**< should an endline be set? */ 643 ) 644 { 645 int v; 646 647 assert(consdata != NULL); 648 649 /* print coefficients */ 650 SCIPinfoMessage(scip, file, "bounddisjunction("); 651 for( v = 0; v < consdata->nvars; ++v ) 652 { 653 assert(consdata->vars[v] != NULL); 654 if( v > 0 ) 655 SCIPinfoMessage(scip, file, ", "); 656 SCIPinfoMessage(scip, file, "<%s> %s %.15g", SCIPvarGetName(consdata->vars[v]), 657 consdata->boundtypes[v] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", consdata->bounds[v]); 658 } 659 SCIPinfoMessage(scip, file, ")"); 660 661 if( endline ) 662 SCIPinfoMessage(scip, file, "\n"); 663 } 664 665 /** stores the given variable numbers as watched variables, and updates the event processing */ 666 static 667 SCIP_RETCODE switchWatchedvars( 668 SCIP* scip, /**< SCIP data structure */ 669 SCIP_CONS* cons, /**< bound disjunction constraint */ 670 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */ 671 int watchedvar1, /**< new first watched variable */ 672 int watchedvar2 /**< new second watched variable */ 673 ) 674 { 675 SCIP_CONSDATA* consdata; 676 677 consdata = SCIPconsGetData(cons); 678 assert(consdata != NULL); 679 assert(watchedvar1 == -1 || watchedvar1 != watchedvar2); 680 assert(watchedvar1 != -1 || watchedvar2 == -1); 681 assert(watchedvar1 == -1 || (0 <= watchedvar1 && watchedvar1 < consdata->nvars)); 682 assert(watchedvar2 == -1 || (0 <= watchedvar2 && watchedvar2 < consdata->nvars)); 683 684 /* don't watch variables for non active constraints */ 685 if( !SCIPconsIsActive(cons) ) 686 return SCIP_OKAY; 687 688 /* if one watched variable is equal to the old other watched variable, just switch positions */ 689 if( watchedvar1 == consdata->watchedvar2 || watchedvar2 == consdata->watchedvar1 ) 690 { 691 int tmp; 692 693 tmp = consdata->watchedvar1; 694 consdata->watchedvar1 = consdata->watchedvar2; 695 consdata->watchedvar2 = tmp; 696 tmp = consdata->filterpos1; 697 consdata->filterpos1 = consdata->filterpos2; 698 consdata->filterpos2 = tmp; 699 } 700 assert(watchedvar1 == -1 || watchedvar1 != consdata->watchedvar2); 701 assert(watchedvar2 == -1 || watchedvar2 != consdata->watchedvar1); 702 703 /* drop events on old watched variables */ 704 if( consdata->watchedvar1 != -1 && consdata->watchedvar1 != watchedvar1 ) 705 { 706 assert(consdata->filterpos1 != -1); 707 SCIP_CALL( dropEvents(scip, cons, consdata, eventhdlr, consdata->watchedvar1, consdata->filterpos1) ); 708 consdata->watchedvar1 = -1; 709 } 710 if( consdata->watchedvar2 != -1 && consdata->watchedvar2 != watchedvar2 ) 711 { 712 assert(consdata->filterpos2 != -1); 713 SCIP_CALL( dropEvents(scip, cons, consdata, eventhdlr, consdata->watchedvar2, consdata->filterpos2) ); 714 consdata->watchedvar2 = -1; 715 } 716 717 /* catch events on new watched variables */ 718 if( watchedvar1 != -1 && watchedvar1 != consdata->watchedvar1 ) 719 { 720 SCIP_CALL( catchEvents(scip, cons, consdata, eventhdlr, watchedvar1, &consdata->filterpos1) ); 721 } 722 if( watchedvar2 != -1 && watchedvar2 != consdata->watchedvar2 ) 723 { 724 SCIP_CALL( catchEvents(scip, cons, consdata, eventhdlr, watchedvar2, &consdata->filterpos2) ); 725 } 726 727 /* set the new watched variables */ 728 consdata->watchedvar1 = watchedvar1; 729 consdata->watchedvar2 = watchedvar2; 730 731 return SCIP_OKAY; 732 } 733 734 /** check whether two intervals overlap */ 735 static 736 SCIP_Bool isOverlapping( 737 SCIP* scip, 738 SCIP_VAR* var, 739 SCIP_BOUNDTYPE boundtype1, 740 SCIP_Real bound1, 741 SCIP_BOUNDTYPE boundtype2, 742 SCIP_Real bound2 743 ) 744 { 745 SCIP_Bool overlapping = FALSE; 746 747 if( boundtype1 == SCIP_BOUNDTYPE_LOWER ) 748 { 749 assert(boundtype2 == SCIP_BOUNDTYPE_UPPER); 750 751 if( SCIPisLE(scip, bound1 - bound2, (SCIP_Real)SCIPvarIsIntegral(var)) ) 752 overlapping = TRUE; 753 } 754 else 755 { 756 assert(boundtype2 == SCIP_BOUNDTYPE_LOWER); 757 758 if( SCIPisLE(scip, bound2 - bound1, (SCIP_Real)SCIPvarIsIntegral(var)) ) 759 overlapping = TRUE; 760 } 761 762 return overlapping; 763 } 764 765 /** deletes coefficient at given position from bound disjunction constraint data */ 766 static 767 SCIP_RETCODE delCoefPos( 768 SCIP* scip, /**< SCIP data structure */ 769 SCIP_CONS* cons, /**< bound disjunction constraint */ 770 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */ 771 int pos /**< position of coefficient to delete */ 772 ) 773 { 774 SCIP_CONSDATA* consdata; 775 776 assert(eventhdlr != NULL); 777 778 consdata = SCIPconsGetData(cons); 779 assert(consdata != NULL); 780 assert(0 <= pos && pos < consdata->nvars); 781 assert(SCIPconsIsTransformed(cons) == SCIPvarIsTransformed(consdata->vars[pos])); 782 783 /* remove the rounding locks of variable */ 784 SCIP_CALL( unlockRounding(scip, cons, consdata, pos) ); 785 786 if( SCIPconsIsTransformed(cons) ) 787 { 788 /* if the position is watched, stop watching the position */ 789 if( consdata->watchedvar1 == pos ) 790 { 791 SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, consdata->watchedvar2, -1) ); 792 } 793 if( consdata->watchedvar2 == pos ) 794 { 795 SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, consdata->watchedvar1, -1) ); 796 } 797 } 798 assert(pos != consdata->watchedvar1); 799 assert(pos != consdata->watchedvar2); 800 801 /* move the last variable to the free slot */ 802 consdata->vars[pos] = consdata->vars[consdata->nvars-1]; 803 consdata->boundtypes[pos] = consdata->boundtypes[consdata->nvars-1]; 804 consdata->bounds[pos] = consdata->bounds[consdata->nvars-1]; 805 consdata->nvars--; 806 807 /* if the last variable (that moved) was watched, update the watched position */ 808 if( consdata->watchedvar1 == consdata->nvars ) 809 consdata->watchedvar1 = pos; 810 if( consdata->watchedvar2 == consdata->nvars ) 811 consdata->watchedvar2 = pos; 812 813 SCIP_CALL( SCIPenableConsPropagation(scip, cons) ); 814 815 return SCIP_OKAY; 816 } 817 818 /** adds literal to bound disjunction constraint data */ 819 static 820 SCIP_RETCODE addCoef( 821 SCIP* scip, /**< SCIP data structure */ 822 SCIP_CONS* cons, /**< bound disjunction constraint */ 823 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */ 824 SCIP_VAR* var, /**< variable in literal */ 825 SCIP_BOUNDTYPE boundtype, /**< boundtype of literal */ 826 SCIP_Real bound, /**< bound of literal */ 827 SCIP_Bool* redundant /**< flag to indicate whether constraint has been bound redundant */ 828 ) 829 { 830 SCIP_CONSDATA* consdata; 831 int samebndidx; 832 int v; 833 834 assert(eventhdlr != NULL); 835 836 consdata = SCIPconsGetData(cons); 837 assert(consdata != NULL); 838 assert(var != NULL); 839 assert(!SCIPisInfinity(scip, REALABS(bound))); 840 assert(SCIPconsIsTransformed(cons) == SCIPvarIsTransformed(var)); 841 842 /* ensure enough memory in consdata arrays */ 843 if( consdata->varssize == consdata->nvars ) 844 { 845 int newsize; 846 847 newsize = SCIPcalcMemGrowSize(scip, consdata->nvars + 1); 848 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, consdata->varssize, newsize) ); 849 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->boundtypes, consdata->varssize, newsize) ); 850 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->bounds, consdata->varssize, newsize) ); 851 consdata->varssize = newsize; 852 } 853 assert(consdata->varssize > consdata->nvars); 854 855 /* remember the position of the literal in the constraint that has the same bound type on the same variable 856 * 857 * example: (x >= 5) or (x <= 2) and literal (x >= 2) should be added. 858 * if we see (x >= 5) first, we cannot stop immediately because only in combination with the second literal 859 * we see that the constraint is redundant. 860 */ 861 samebndidx = -1; 862 863 for( v = 0; v < consdata->nvars; v++ ) 864 { 865 /* check if the variable is already part of the constraint */ 866 if( consdata->vars[v] == var ) 867 { 868 if( consdata->boundtypes[v] == boundtype ) 869 samebndidx = v; 870 else if( isOverlapping(scip, var, consdata->boundtypes[v], consdata->bounds[v], boundtype, bound) ) 871 { 872 *redundant = TRUE; 873 return SCIP_OKAY; 874 } 875 } 876 } 877 878 /* the combination of variable and boundtype is already part of the constraint; check whether the clause 879 * can be relaxed 880 */ 881 if( samebndidx > -1 ) 882 { 883 if( (boundtype == SCIP_BOUNDTYPE_LOWER && SCIPisLT(scip, bound, consdata->bounds[samebndidx])) 884 || (boundtype == SCIP_BOUNDTYPE_UPPER && SCIPisGT(scip, bound, consdata->bounds[samebndidx])) ) 885 { 886 SCIPdebugMsg(scip, "relax clause of <%s>: (<%s> %s %.15g) -> (<%s> %s %.15g)\n", SCIPconsGetName(cons), 887 SCIPvarGetName(var), boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", consdata->bounds[samebndidx], 888 SCIPvarGetName(var), boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", bound); 889 consdata->bounds[samebndidx] = bound; 890 } 891 } 892 else 893 { 894 /* add the variable to the end of the array */ 895 consdata->vars[consdata->nvars] = var; 896 consdata->boundtypes[consdata->nvars] = boundtype; 897 consdata->bounds[consdata->nvars] = bound; 898 consdata->nvars++; 899 900 if( SCIPconsIsTransformed(cons) ) 901 { 902 /* add rounding lock of variable */ 903 SCIP_CALL( lockRounding(scip, cons, consdata, consdata->nvars-1) ); 904 905 /* if less than 2 variables are watched, add the new one to the watched variables */ 906 if( consdata->watchedvar1 == -1 ) 907 { 908 assert(consdata->watchedvar2 == -1); 909 SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, consdata->nvars-1, -1) ); 910 } 911 else if( consdata->watchedvar2 == -1 ) 912 { 913 SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, consdata->watchedvar1, consdata->nvars-1) ); 914 } 915 } 916 } 917 918 SCIP_CALL( SCIPenableConsPropagation(scip, cons) ); 919 920 return SCIP_OKAY; 921 } 922 923 /** deletes all variables with global bounds violating the literal, checks for global bounds satisfying the literal */ 924 static 925 SCIP_RETCODE applyGlobalBounds( 926 SCIP* scip, /**< SCIP data structure */ 927 SCIP_CONS* cons, /**< bound disjunction constraint */ 928 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */ 929 SCIP_Bool* redundant /**< returns whether a variable fixed to one exists in the constraint */ 930 ) 931 { 932 SCIP_CONSDATA* consdata; 933 int v; 934 SCIP_Real bnd; 935 936 assert(eventhdlr != NULL); 937 assert(redundant != NULL); 938 939 consdata = SCIPconsGetData(cons); 940 assert(consdata != NULL); 941 assert(consdata->nvars == 0 || consdata->vars != NULL); 942 943 *redundant = FALSE; 944 v = 0; 945 while( v < consdata->nvars ) 946 { 947 SCIP_VAR* var; 948 949 var = consdata->vars[v]; 950 951 if( consdata->boundtypes[v] == SCIP_BOUNDTYPE_LOWER ) 952 { 953 bnd = SCIPcomputeVarLbGlobal(scip, var); 954 if( isFeasGE(scip, var, bnd, consdata->bounds[v]) ) 955 { 956 *redundant = TRUE; 957 return SCIP_OKAY; 958 } 959 else 960 { 961 bnd = SCIPcomputeVarUbGlobal(scip, var); 962 if( isFeasLT(scip, var, bnd, consdata->bounds[v]) ) 963 { 964 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) ); 965 } 966 else 967 ++v; 968 } 969 } 970 else 971 { 972 assert(consdata->boundtypes[v] == SCIP_BOUNDTYPE_UPPER); 973 bnd = SCIPcomputeVarUbGlobal(scip, var); 974 if( isFeasLE(scip, var, bnd, consdata->bounds[v]) ) 975 { 976 *redundant = TRUE; 977 return SCIP_OKAY; 978 } 979 else 980 { 981 bnd = SCIPcomputeVarLbGlobal(scip, var); 982 if( isFeasGT(scip, var, bnd, consdata->bounds[v]) ) 983 { 984 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) ); 985 } 986 else 987 ++v; 988 } 989 } 990 } 991 992 SCIPdebugMsg(scip, "after global bounds: "); 993 SCIPdebug(consdataPrint(scip, consdata, NULL, TRUE)); 994 995 return SCIP_OKAY; 996 } 997 998 /** returns whether literal at the given position is satisfied in the local bounds */ 999 static 1000 SCIP_Bool isLiteralSatisfied( 1001 SCIP* scip, /**< SCIP data structure */ 1002 SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */ 1003 int pos /**< position of the literal */ 1004 ) 1005 { 1006 SCIP_Real bnd; 1007 1008 assert(consdata != NULL); 1009 assert(0 <= pos && pos < consdata->nvars); 1010 1011 if( consdata->boundtypes[pos] == SCIP_BOUNDTYPE_LOWER ) 1012 { 1013 bnd = SCIPcomputeVarLbLocal(scip, consdata->vars[pos]); 1014 return isFeasGE(scip, consdata->vars[pos], bnd, consdata->bounds[pos]); 1015 } 1016 else 1017 { 1018 bnd = SCIPcomputeVarUbLocal(scip, consdata->vars[pos]); 1019 return isFeasLE(scip, consdata->vars[pos], bnd, consdata->bounds[pos]); 1020 } 1021 } 1022 1023 /** returns whether literal at the given position is violated in the local bounds */ 1024 static 1025 SCIP_Bool isLiteralViolated( 1026 SCIP* scip, /**< SCIP data structure */ 1027 SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */ 1028 int pos /**< position of the literal */ 1029 ) 1030 { 1031 SCIP_Real bnd; 1032 1033 assert(consdata != NULL); 1034 assert(0 <= pos && pos < consdata->nvars); 1035 1036 if( consdata->boundtypes[pos] == SCIP_BOUNDTYPE_LOWER ) 1037 { 1038 bnd = SCIPcomputeVarUbLocal(scip, consdata->vars[pos]); 1039 return isFeasLT(scip, consdata->vars[pos], bnd, consdata->bounds[pos]); 1040 } 1041 else 1042 { 1043 bnd = SCIPcomputeVarLbLocal(scip, consdata->vars[pos]); 1044 return isFeasGT(scip, consdata->vars[pos], bnd, consdata->bounds[pos]); 1045 } 1046 } 1047 1048 /** replace variables by their representative active (or multi-aggregated) variables */ 1049 static 1050 SCIP_RETCODE removeFixedVariables( 1051 SCIP* scip, /**< SCIP data structure */ 1052 SCIP_CONS* cons, /**< bound disjunction constraint */ 1053 SCIP_EVENTHDLR* eventhdlr, /**< event handler */ 1054 SCIP_Bool* redundant /**< flag to indicate whether constraint has been bound redundant */ 1055 ) 1056 { 1057 SCIP_CONSDATA* consdata; 1058 SCIP_VAR* var; 1059 SCIP_BOUNDTYPE boundtype; 1060 SCIP_Real bound; 1061 int v; 1062 1063 assert(scip != NULL); 1064 assert(cons != NULL); 1065 assert(eventhdlr != NULL); 1066 1067 consdata = SCIPconsGetData(cons); 1068 assert(consdata != NULL); 1069 1070 v = 0; 1071 while( v < consdata->nvars ) 1072 { 1073 #ifndef NDEBUG 1074 SCIP_VAR* oldvar; 1075 #endif 1076 var = consdata->vars[v]; 1077 assert(var != NULL); 1078 1079 #ifndef NDEBUG 1080 oldvar = var; 1081 #endif 1082 1083 if( SCIPvarIsActive(var) || SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR ) 1084 { 1085 /* check whether the literal is satisfied and the constraint is thus redundant */ 1086 if( isLiteralSatisfied(scip, consdata, v) ) 1087 { 1088 *redundant = TRUE; 1089 break; 1090 } 1091 if( isLiteralViolated(scip, consdata, v) ) 1092 { 1093 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) ); 1094 continue; 1095 } 1096 1097 ++v; 1098 1099 continue; 1100 } 1101 1102 /* get active/fixed/multiaggr equivalent of v'th literal */ 1103 bound = consdata->bounds[v]; 1104 boundtype = consdata->boundtypes[v]; 1105 SCIP_CALL( SCIPvarGetProbvarBound(&var, &bound, &boundtype) ); 1106 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED || oldvar != var); 1107 1108 SCIPdebugMsg(scip, "in <%s>, replace <%s>[%g,%g] %c= %g by <%s>[%g,%g] %c= %g\n", SCIPconsGetName(cons), 1109 SCIPvarGetName(consdata->vars[v]), SCIPvarGetLbGlobal(consdata->vars[v]), SCIPvarGetUbGlobal(consdata->vars[v]), (consdata->boundtypes[v] == SCIP_BOUNDTYPE_LOWER ? '>' : '<'), consdata->bounds[v], 1110 SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), (boundtype == SCIP_BOUNDTYPE_LOWER ? '>' : '<'), bound); 1111 1112 /* if literal is satisfied, then constraint is redundant and we can stop */ 1113 if( (boundtype == SCIP_BOUNDTYPE_LOWER && isFeasLE(scip, var, bound, SCIPvarGetLbGlobal(var))) || /*lint !e666*/ 1114 (boundtype == SCIP_BOUNDTYPE_UPPER && isFeasGE(scip, var, bound, SCIPvarGetUbGlobal(var))) ) /*lint !e666*/ 1115 { 1116 *redundant = TRUE; 1117 break; 1118 } 1119 1120 /* if literal is not fixed, replace it */ 1121 if( SCIPvarGetStatus(var) != SCIP_VARSTATUS_FIXED ) 1122 { 1123 /* add new literal */ 1124 SCIP_CALL( addCoef(scip, cons, eventhdlr, var, boundtype, bound, redundant) ); 1125 } 1126 1127 /* remove old literal */ 1128 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) ); 1129 } 1130 1131 return SCIP_OKAY; 1132 } 1133 1134 /** try to upgrade the bounddisjunction constraint 1135 * 1136 * if only binary variables are left, we can upgrade a bounddisjunction to a logicor constraint(, if only two variables 1137 * are left, this logicor constraint can be formulated as set-packing constraint as well) 1138 * 1139 * e.g.: bounddisjunction( x1 >= 1, x2 <= 0; x3 >= 1; x4 <= 0 ) => x1 + ~x2 + x3 + ~x4 >= 1 1140 */ 1141 static 1142 SCIP_RETCODE upgradeCons( 1143 SCIP* scip, /**< SCIP data structure */ 1144 SCIP_CONS* cons, /**< bound disjunction constraint that detected the conflict */ 1145 int* ndelconss, /**< pointer to store the number of delete constraint */ 1146 int* naddconss /**< pointer to store the number of added constraint */ 1147 ) 1148 { 1149 SCIP_CONSDATA* consdata; 1150 SCIP_VAR** newvars; 1151 SCIP_Bool allbinary; 1152 int nvars; 1153 int v; 1154 1155 assert(scip != NULL); 1156 assert(cons != NULL); 1157 assert(ndelconss != NULL); 1158 assert(naddconss != NULL); 1159 assert(naddconss != NULL); 1160 assert(!SCIPconsIsModifiable(cons)); 1161 1162 consdata = SCIPconsGetData(cons); 1163 assert(consdata != NULL); 1164 1165 nvars = consdata->nvars; 1166 assert(nvars >= 2); 1167 assert(consdata->vars != NULL); 1168 1169 allbinary = TRUE; 1170 1171 SCIP_CALL( SCIPallocBufferArray(scip, &newvars, nvars) ); 1172 1173 for( v = nvars - 1; v >= 0; --v ) 1174 { 1175 if( !SCIPvarIsBinary(consdata->vars[v]) ) 1176 { 1177 allbinary = FALSE; 1178 break; 1179 } 1180 else 1181 { 1182 if( consdata->boundtypes[v] == SCIP_BOUNDTYPE_LOWER ) 1183 { 1184 assert(SCIPisFeasGT(scip, consdata->bounds[v], 0.0)); 1185 1186 if( nvars == 2 ) 1187 { 1188 SCIP_CALL( SCIPgetNegatedVar(scip, consdata->vars[v], &(newvars[v])) ); 1189 } 1190 else 1191 newvars[v] = consdata->vars[v]; 1192 } 1193 else 1194 { 1195 assert(consdata->boundtypes[v] == SCIP_BOUNDTYPE_UPPER); 1196 assert(SCIPisFeasLT(scip, consdata->bounds[v], 1.0)); 1197 1198 if( nvars > 2 ) 1199 { 1200 SCIP_CALL( SCIPgetNegatedVar(scip, consdata->vars[v], &(newvars[v])) ); 1201 } 1202 else 1203 newvars[v] = consdata->vars[v]; 1204 } 1205 } 1206 } 1207 1208 if( allbinary ) 1209 { 1210 SCIP_CONS* newcons; 1211 1212 if( nvars == 2 ) 1213 { 1214 SCIP_CALL( SCIPcreateConsSetpack(scip, &newcons, SCIPconsGetName(cons), nvars, newvars, 1215 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), 1216 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), 1217 SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), 1218 SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) ); 1219 } 1220 else 1221 { 1222 SCIP_CALL( SCIPcreateConsLogicor(scip, &newcons, SCIPconsGetName(cons), nvars, newvars, 1223 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), 1224 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), 1225 SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), 1226 SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) ); 1227 } 1228 1229 SCIPdebugMsg(scip, "updated constraint <%s> to the following %s constraint\n", SCIPconsGetName(cons), (nvars == 2 ? "setppc" : "logicor")); 1230 SCIPdebugPrintCons(scip, newcons, NULL); 1231 SCIP_CALL( SCIPaddCons(scip, newcons) ); 1232 SCIP_CALL( SCIPreleaseCons(scip, &newcons) ); 1233 ++(*naddconss); 1234 1235 SCIP_CALL( SCIPdelCons(scip, cons) ); 1236 ++(*ndelconss); 1237 } 1238 1239 SCIPfreeBufferArray(scip, &newvars); 1240 1241 return SCIP_OKAY; 1242 } 1243 1244 /** analyzes conflicting assignment on given constraint, and adds conflict constraint to problem */ 1245 static 1246 SCIP_RETCODE analyzeConflict( 1247 SCIP* scip, /**< SCIP data structure */ 1248 SCIP_CONS* cons /**< bound disjunction constraint that detected the conflict */ 1249 ) 1250 { 1251 SCIP_CONSDATA* consdata; 1252 int v; 1253 1254 /* conflict analysis can only be applied in solving stage and if it is turned on */ 1255 if( (SCIPgetStage(scip) != SCIP_STAGE_SOLVING && !SCIPinProbing(scip)) || !SCIPisConflictAnalysisApplicable(scip) ) 1256 return SCIP_OKAY; 1257 1258 consdata = SCIPconsGetData(cons); 1259 assert(consdata != NULL); 1260 1261 /* initialize conflict analysis, and add all bounds of infeasible constraint to conflict candidate queue */ 1262 SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) ); 1263 1264 for( v = 0; v < consdata->nvars; ++v ) 1265 { 1266 /* the opposite bound is in conflict with this literal */ 1267 SCIP_CALL( SCIPaddConflictBd(scip, consdata->vars[v], SCIPboundtypeOpposite(consdata->boundtypes[v]), NULL) ); 1268 } 1269 1270 /* analyze the conflict */ 1271 SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) ); 1272 1273 return SCIP_OKAY; 1274 } 1275 1276 /** disables or deletes the given constraint, depending on the current depth */ 1277 static 1278 SCIP_RETCODE disableCons( 1279 SCIP* scip, /**< SCIP data structure */ 1280 SCIP_CONS* cons /**< bound disjunction constraint to be disabled */ 1281 ) 1282 { 1283 assert(SCIPconsGetValidDepth(cons) <= SCIPgetDepth(scip)); 1284 1285 if( SCIPgetDepth(scip) == SCIPconsGetValidDepth(cons) ) 1286 { 1287 SCIP_CALL( SCIPdelCons(scip, cons) ); 1288 } 1289 else 1290 { 1291 SCIP_CALL( SCIPdisableCons(scip, cons) ); 1292 } 1293 1294 return SCIP_OKAY; 1295 } 1296 1297 /** checks constraint for violation only looking at the watched variables, applies bound changes if possible */ 1298 static 1299 SCIP_RETCODE processWatchedVars( 1300 SCIP* scip, /**< SCIP data structure */ 1301 SCIP_CONS* cons, /**< bound disjunction constraint to be processed */ 1302 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */ 1303 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */ 1304 SCIP_Bool* infeasible, /**< pointer to store TRUE, if the constraint is infeasible in current bounds */ 1305 SCIP_Bool* reduceddom, /**< pointer to store TRUE, if a domain reduction was found */ 1306 SCIP_Bool* mustcheck /**< pointer to store whether this constraint must be checked for feasibility */ 1307 ) 1308 { 1309 SCIP_CONSDATA* consdata; 1310 SCIP_VAR** vars; 1311 SCIP_BOUNDTYPE* boundtypes; 1312 SCIP_Real* bounds; 1313 SCIP_Longint nbranchings1; 1314 SCIP_Longint nbranchings2; 1315 int nvars; 1316 int watchedvar1; 1317 int watchedvar2; 1318 1319 assert(cons != NULL); 1320 assert(SCIPconsGetHdlr(cons) != NULL); 1321 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0); 1322 assert(cutoff != NULL); 1323 assert(reduceddom != NULL); 1324 assert(mustcheck != NULL); 1325 1326 consdata = SCIPconsGetData(cons); 1327 assert(consdata != NULL); 1328 assert(consdata->watchedvar1 == -1 || consdata->watchedvar1 != consdata->watchedvar2); 1329 1330 /* init bools */ 1331 *cutoff = FALSE; 1332 *infeasible = FALSE; 1333 *reduceddom = FALSE; 1334 *mustcheck = FALSE; 1335 1336 SCIPdebugMsg(scip, "processing watched variables of constraint <%s>\n", SCIPconsGetName(cons)); 1337 1338 nvars = consdata->nvars; 1339 vars = consdata->vars; 1340 boundtypes = consdata->boundtypes; 1341 bounds = consdata->bounds; 1342 assert(nvars == 0 || vars != NULL); 1343 assert(nvars == 0 || boundtypes != NULL); 1344 assert(nvars == 0 || bounds != NULL); 1345 1346 /* check watched variables if they are satisfying the literal */ 1347 if( consdata->watchedvar1 >= 0 && isLiteralSatisfied(scip, consdata, consdata->watchedvar1) ) 1348 { 1349 /* the literal is satisfied, making the constraint redundant */ 1350 SCIPdebugMsg(scip, " -> disabling constraint <%s> (watchedvar1 satisfied)\n", SCIPconsGetName(cons)); 1351 SCIP_CALL( disableCons(scip, cons) ); 1352 return SCIP_OKAY; 1353 } 1354 if( consdata->watchedvar2 >= 0 && isLiteralSatisfied(scip, consdata, consdata->watchedvar2) ) 1355 { 1356 /* the literal is satisfied, making the constraint redundant */ 1357 SCIPdebugMsg(scip, " -> disabling constraint <%s> (watchedvar2 satisfied)\n", SCIPconsGetName(cons)); 1358 SCIP_CALL( disableCons(scip, cons) ); 1359 return SCIP_OKAY; 1360 } 1361 1362 /* check if watched variables are still undecided */ 1363 watchedvar1 = -1; 1364 watchedvar2 = -1; 1365 nbranchings1 = SCIP_LONGINT_MAX; 1366 nbranchings2 = SCIP_LONGINT_MAX; 1367 if( consdata->watchedvar1 >= 0 && !isLiteralViolated(scip, consdata, consdata->watchedvar1) ) 1368 { 1369 watchedvar1 = consdata->watchedvar1; 1370 nbranchings1 = -1; /* prefer keeping the watched variable */ 1371 } 1372 if( consdata->watchedvar2 >= 0 && !isLiteralViolated(scip, consdata, consdata->watchedvar2) ) 1373 { 1374 if( watchedvar1 == -1 ) 1375 { 1376 watchedvar1 = consdata->watchedvar2; 1377 nbranchings1 = -1; /* prefer keeping the watched variable */ 1378 } 1379 else 1380 { 1381 watchedvar2 = consdata->watchedvar2; 1382 nbranchings2 = -1; /* prefer keeping the watched variable */ 1383 } 1384 } 1385 assert(watchedvar1 >= 0 || watchedvar2 == -1); 1386 assert(nbranchings1 <= nbranchings2); 1387 assert(watchedvar1 != -1 || nbranchings1 == SCIP_LONGINT_MAX); 1388 assert(watchedvar2 != -1 || nbranchings2 == SCIP_LONGINT_MAX); 1389 1390 /* search for new watched variables */ 1391 if( watchedvar2 == -1 ) 1392 { 1393 int v; 1394 1395 for( v = 0; v < nvars; ++v ) 1396 { 1397 SCIP_Longint nbranchings; 1398 1399 /* don't process the watched variables again */ 1400 if( v == consdata->watchedvar1 || v == consdata->watchedvar2 ) 1401 continue; 1402 1403 /* check, if the literal is violated */ 1404 if( isLiteralViolated(scip, consdata, v) ) 1405 continue; 1406 1407 /* check, if the literal is satisfied */ 1408 if( isLiteralSatisfied(scip, consdata, v) ) 1409 { 1410 assert(v != consdata->watchedvar1); 1411 assert(v != consdata->watchedvar2); 1412 1413 /* the literal is satisfied, making the constraint redundant; 1414 * make sure, the feasible variable is watched and disable the constraint 1415 */ 1416 SCIPdebugMsg(scip, " -> disabling constraint <%s> (variable <%s> fixed to 1.0)\n", 1417 SCIPconsGetName(cons), SCIPvarGetName(vars[v])); 1418 if( consdata->watchedvar1 != -1 ) 1419 { 1420 SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, consdata->watchedvar1, v) ); 1421 } 1422 else 1423 { 1424 SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, v, consdata->watchedvar2) ); 1425 } 1426 SCIP_CALL( disableCons(scip, cons) ); 1427 return SCIP_OKAY; 1428 } 1429 1430 /* the literal is still undecided and can be used as watched variable */ 1431 nbranchings = SCIPvarGetNBranchingsCurrentRun(vars[v], 1432 boundtypes[v] == SCIP_BOUNDTYPE_LOWER ? SCIP_BRANCHDIR_DOWNWARDS : SCIP_BRANCHDIR_UPWARDS); 1433 if( nbranchings < nbranchings2 ) 1434 { 1435 if( nbranchings < nbranchings1 ) 1436 { 1437 watchedvar2 = watchedvar1; 1438 nbranchings2 = nbranchings1; 1439 watchedvar1 = v; 1440 nbranchings1 = nbranchings; 1441 } 1442 else 1443 { 1444 watchedvar2 = v; 1445 nbranchings2 = nbranchings; 1446 } 1447 } 1448 } 1449 } 1450 assert(nbranchings1 <= nbranchings2); 1451 assert(watchedvar1 >= 0 || watchedvar2 == -1); 1452 1453 if( watchedvar1 == -1 ) 1454 { 1455 /* there is no undecided literal left -> the constraint is infeasible 1456 * - a modifiable constraint is infeasible 1457 * - an unmodifiable constraint is infeasible and the node can be cut off 1458 */ 1459 assert(watchedvar2 == -1); 1460 1461 SCIPdebugMsg(scip, " -> constraint <%s> is infeasible\n", SCIPconsGetName(cons)); 1462 *infeasible = TRUE; 1463 1464 SCIP_CALL( SCIPresetConsAge(scip, cons) ); 1465 if( !SCIPconsIsModifiable(cons) ) 1466 { 1467 /* use conflict analysis to get a conflict constraint out of the conflicting assignment */ 1468 SCIP_CALL( analyzeConflict(scip, cons) ); 1469 1470 /* mark the node to be cut off */ 1471 *cutoff = TRUE; 1472 } 1473 } 1474 else if( watchedvar2 == -1 ) 1475 { 1476 /* there is only one undecided literal: 1477 * - a modifiable constraint must be checked manually 1478 * - we cannot change bounds of multi-aggregated variables and have to check manually 1479 * - an unmodifiable constraint is feasible and can be disabled after the remaining literal is satisfied 1480 */ 1481 assert(0 <= watchedvar1 && watchedvar1 < nvars); 1482 assert(!isLiteralViolated(scip, consdata, watchedvar1)); 1483 assert(!isLiteralSatisfied(scip, consdata, watchedvar1)); 1484 if( SCIPconsIsModifiable(cons) 1485 || SCIPvarGetStatus(SCIPvarGetProbvar(vars[watchedvar1])) == SCIP_VARSTATUS_MULTAGGR ) 1486 *mustcheck = TRUE; 1487 else 1488 { 1489 SCIP_Bool infbdchg; 1490 1491 #ifndef NDEBUG 1492 int v; 1493 1494 /* check whether all other literals are violated */ 1495 for (v = 0; v < nvars; ++v) 1496 { 1497 if ( v != watchedvar1 ) 1498 { 1499 assert( isLiteralViolated(scip, consdata, v) ); 1500 } 1501 } 1502 #endif 1503 1504 /* satisfy remaining literal and disable constraint; make sure, the fixed-to-one variable is watched */ 1505 SCIPdebugMsg(scip, " -> single-literal constraint <%s> (change bound <%s> %s %g) at depth %d\n", 1506 SCIPconsGetName(cons), SCIPvarGetName(vars[watchedvar1]), 1507 boundtypes[watchedvar1] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", bounds[watchedvar1], SCIPgetDepth(scip)); 1508 1509 if( boundtypes[watchedvar1] == SCIP_BOUNDTYPE_LOWER ) 1510 { 1511 SCIP_CALL( SCIPinferVarLbCons(scip, vars[watchedvar1], bounds[watchedvar1], cons, watchedvar1, TRUE, 1512 &infbdchg, NULL) ); 1513 } 1514 else 1515 { 1516 SCIP_CALL( SCIPinferVarUbCons(scip, vars[watchedvar1], bounds[watchedvar1], cons, watchedvar1, TRUE, 1517 &infbdchg, NULL) ); 1518 } 1519 assert(!infbdchg); 1520 SCIP_CALL( SCIPresetConsAge(scip, cons) ); 1521 if( watchedvar1 != consdata->watchedvar1 ) /* keep one of the watched variables */ 1522 { 1523 SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, watchedvar1, consdata->watchedvar1) ); 1524 } 1525 SCIP_CALL( disableCons(scip, cons) ); 1526 *reduceddom = TRUE; 1527 } 1528 } 1529 else 1530 { 1531 SCIPdebugMsg(scip, " -> new watched variables <%s> and <%s> of constraint <%s> are still undecided\n", 1532 SCIPvarGetName(vars[watchedvar1]), SCIPvarGetName(vars[watchedvar2]), SCIPconsGetName(cons)); 1533 1534 /* switch to the new watched variables */ 1535 SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, watchedvar1, watchedvar2) ); 1536 1537 /* there are at least two undecided variables -> the constraint must be checked manually */ 1538 *mustcheck = TRUE; 1539 1540 /* disable propagation of constraint until the corresponding bound of a watched variable changed */ 1541 SCIP_CALL( SCIPdisableConsPropagation(scip, cons) ); 1542 1543 /* increase aging counter */ 1544 SCIP_CALL( SCIPaddConsAge(scip, cons, AGEINCREASE(consdata->nvars)) ); 1545 } 1546 1547 return SCIP_OKAY; 1548 } 1549 1550 /** checks constraint for violation, returns TRUE iff constraint is violated */ 1551 static 1552 SCIP_Bool isConsViolated( 1553 SCIP* scip, /**< SCIP data structure */ 1554 SCIP_CONS* cons, /**< bound disjunction constraint to be checked */ 1555 SCIP_SOL* sol /**< primal CIP solution */ 1556 ) 1557 { 1558 SCIP_CONSDATA* consdata; 1559 SCIP_VAR** vars; 1560 SCIP_BOUNDTYPE* boundtypes; 1561 SCIP_Real* bounds; 1562 SCIP_Real solval; 1563 SCIP_Real viol; 1564 SCIP_Real absviol; 1565 int violpos; 1566 int nvars; 1567 int v; 1568 1569 consdata = SCIPconsGetData(cons); 1570 assert(consdata != NULL); 1571 1572 nvars = consdata->nvars; 1573 vars = consdata->vars; 1574 boundtypes = consdata->boundtypes; 1575 bounds = consdata->bounds; 1576 assert(nvars == 0 || vars != NULL); 1577 assert(nvars == 0 || boundtypes != NULL); 1578 assert(nvars == 0 || bounds != NULL); 1579 1580 /* check the given solution */ 1581 absviol = SCIP_REAL_MAX; 1582 violpos = -1; 1583 for( v = 0; v < nvars; ++v ) 1584 { 1585 solval = SCIPgetSolVal(scip, sol, vars[v]); 1586 1587 /* update absolute violation if needed */ 1588 viol = (boundtypes[v] == SCIP_BOUNDTYPE_LOWER) ? bounds[v] - solval : solval - bounds[v]; 1589 if( viol < absviol ) 1590 { 1591 absviol = viol; 1592 violpos = v; 1593 } 1594 1595 if( (boundtypes[v] == SCIP_BOUNDTYPE_LOWER && isFeasGE(scip, vars[v], solval, bounds[v])) 1596 || (boundtypes[v] == SCIP_BOUNDTYPE_UPPER && isFeasLE(scip, vars[v], solval, bounds[v])) ) 1597 { 1598 return FALSE; 1599 } 1600 } 1601 /* update constraint violation in solution */ 1602 if( sol != NULL ) 1603 { 1604 SCIP_Real relviol; 1605 1606 assert(0 == nvars || -1 != violpos); 1607 1608 if( 0 == nvars ) 1609 relviol = SCIP_REAL_MAX; 1610 else 1611 relviol = SCIPrelDiff(SCIPgetSolVal(scip, sol, vars[violpos]), bounds[violpos]); 1612 1613 SCIPupdateSolConsViolation(scip, sol, absviol, relviol); 1614 } 1615 return TRUE; 1616 } 1617 1618 /* registers variables of a constraint as branching candidates 1619 * indicates whether an n-ary branch is necessary to enforce this constraint, 1620 * because all active literals are w.r.t. continuous variables which bound (in the literal) is at the variable's bound 1621 */ 1622 static 1623 SCIP_RETCODE registerBranchingCandidates( 1624 SCIP* scip, /**< SCIP data structure */ 1625 SCIP_CONS* cons, /**< bound disjunction constraint which variables should be registered for branching */ 1626 SCIP_SOL* sol, /**< solution (NULL for LP solution) */ 1627 SCIP_Bool* cutoff, /**< pointer to store whether the constraint cannot be made feasible by branching */ 1628 SCIP_Bool* neednarybranch /**< pointer to store TRUE, if n-ary branching is necessary to enforce this constraint */ 1629 ) 1630 { 1631 SCIP_CONSDATA* consdata; 1632 SCIP_VAR** vars; 1633 SCIP_BOUNDTYPE* boundtypes; 1634 SCIP_Real* bounds; 1635 SCIP_Real violation; 1636 SCIP_Real varlb; 1637 SCIP_Real varub; 1638 int nvars; 1639 int v; 1640 1641 assert(cons != NULL); 1642 assert(SCIPconsGetHdlr(cons) != NULL); 1643 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0); 1644 assert(cutoff != NULL); 1645 assert(neednarybranch != NULL); 1646 1647 consdata = SCIPconsGetData(cons); 1648 assert(consdata != NULL); 1649 nvars = consdata->nvars; 1650 vars = consdata->vars; 1651 boundtypes = consdata->boundtypes; 1652 bounds = consdata->bounds; 1653 assert(nvars == 0 || vars != NULL); 1654 assert(nvars == 0 || boundtypes != NULL); 1655 assert(nvars == 0 || bounds != NULL); 1656 1657 *cutoff = TRUE; 1658 *neednarybranch = TRUE; 1659 1660 for( v = 0; v < nvars; ++v ) 1661 { 1662 SCIP_VAR* var; 1663 1664 var = vars[v]; 1665 assert(var != NULL); 1666 1667 /* constraint should be violated, so all bounds in the constraint have to be violated */ 1668 assert( !(boundtypes[v] == SCIP_BOUNDTYPE_LOWER && SCIPisFeasGE(scip, SCIPgetSolVal(scip, sol, var), bounds[v])) && 1669 !(boundtypes[v] == SCIP_BOUNDTYPE_UPPER && SCIPisFeasLE(scip, SCIPgetSolVal(scip, sol, var), bounds[v])) ); 1670 1671 varlb = SCIPcomputeVarLbLocal(scip, var); 1672 varub = SCIPcomputeVarUbLocal(scip, var); 1673 1674 /* if literal is x >= varlb, but upper bound on x is < varlb, then this literal can never be satisfied, 1675 * thus there is no use for branching 1676 */ 1677 if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER && isFeasLT(scip, var, varub, bounds[v]) ) 1678 continue; 1679 1680 /* if literal is x <= varub, but lower bound on x is > varub, then this literal can never be satisfied, 1681 * thus there is no use for branching 1682 */ 1683 if( boundtypes[v] == SCIP_BOUNDTYPE_UPPER && isFeasGT(scip, var, varlb, bounds[v]) ) 1684 continue; 1685 1686 /* if literal is always satisfied, then no need to branch on it may happen if propagation is disabled for some 1687 * reason and due to numerics current solution does not satisfy literal, but variable bounds do 1688 */ 1689 if( isLiteralSatisfied(scip, consdata, v) ) 1690 continue; 1691 1692 violation = SCIPgetSolVal(scip, sol, var) - bounds[v]; 1693 1694 /* if variable is continuous, then we cannot branch on one of the variable bounds */ 1695 if( SCIPvarGetType(vars[v]) != SCIP_VARTYPE_CONTINUOUS || 1696 ((SCIPisInfinity(scip, -varlb) || !SCIPisFeasEQ(scip, bounds[v], varlb)) && 1697 (SCIPisInfinity(scip, varub) || !SCIPisFeasEQ(scip, bounds[v], varub))) ) 1698 { 1699 SCIP_CALL( SCIPaddExternBranchCand(scip, var, REALABS(violation), bounds[v]) ); 1700 *neednarybranch = FALSE; 1701 } 1702 *cutoff = FALSE; 1703 } 1704 1705 return SCIP_OKAY; 1706 } 1707 1708 /** enforces the pseudo or LP solution on the given constraint */ 1709 static 1710 SCIP_RETCODE enforceCurrentSol( 1711 SCIP* scip, /**< SCIP data structure */ 1712 SCIP_CONS* cons, /**< bound disjunction constraint to be separated */ 1713 SCIP_SOL* sol, /**< solution which should be enforced (NULL for LP solution) */ 1714 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */ 1715 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */ 1716 SCIP_Bool* infeasible, /**< pointer to store TRUE, if the constraint was infeasible */ 1717 SCIP_Bool* reduceddom, /**< pointer to store TRUE, if a domain reduction was found */ 1718 SCIP_Bool* registeredbrcand /**< pointer to store TRUE, if branching variable candidates were registered or was already true */ 1719 ) 1720 { 1721 SCIP_Bool mustcheck; 1722 SCIP_Bool neednarybranch; 1723 1724 assert(cons != NULL); 1725 assert(SCIPconsGetHdlr(cons) != NULL); 1726 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0); 1727 assert(cutoff != NULL); 1728 assert(infeasible != NULL); 1729 assert(reduceddom != NULL); 1730 assert(registeredbrcand != NULL); 1731 1732 SCIPdebugMsg(scip, "enforce bound disjunction constraint <%s>\n", SCIPconsGetName(cons)); 1733 1734 /* update and check the watched variables, if they were changed since last processing */ 1735 if( SCIPconsIsPropagationEnabled(cons) ) 1736 { 1737 SCIP_CALL( processWatchedVars(scip, cons, eventhdlr, cutoff, infeasible, reduceddom, &mustcheck) ); 1738 } 1739 else 1740 mustcheck = TRUE; 1741 1742 if( mustcheck ) 1743 { 1744 if( isConsViolated(scip, cons, sol) ) 1745 { 1746 /* constraint was infeasible -> reset age */ 1747 SCIP_CALL( SCIPresetConsAge(scip, cons) ); 1748 *infeasible = TRUE; 1749 1750 /* register branching candidates */ 1751 SCIP_CALL( registerBranchingCandidates(scip, cons, sol, cutoff, &neednarybranch) ); 1752 1753 if( !neednarybranch ) 1754 *registeredbrcand = TRUE; 1755 } 1756 } 1757 1758 return SCIP_OKAY; 1759 } 1760 1761 /** enforces a constraint by creating an n-ary branch consisting of a set of child nodes, each enforcing one literal 1762 */ 1763 static 1764 SCIP_RETCODE createNAryBranch( 1765 SCIP* scip, /**< SCIP data structure */ 1766 SCIP_CONS* cons, /**< bound disjunction constraint to branch on */ 1767 SCIP_SOL* sol /**< solution which should be enforced (NULL for LP solution) */ 1768 ) 1769 { 1770 SCIP_CONSDATA* consdata; 1771 SCIP_VAR** vars; 1772 SCIP_BOUNDTYPE* boundtypes; 1773 SCIP_Real* bounds; 1774 SCIP_Real varlb; 1775 SCIP_Real varub; 1776 int nvars; 1777 int v; 1778 1779 SCIP_Real priority; 1780 SCIP_Real estimate; 1781 SCIP_NODE* node; 1782 1783 assert(cons != NULL); 1784 assert(SCIPconsGetHdlr(cons) != NULL); 1785 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0); 1786 1787 consdata = SCIPconsGetData(cons); 1788 assert(consdata != NULL); 1789 nvars = consdata->nvars; 1790 vars = consdata->vars; 1791 boundtypes = consdata->boundtypes; 1792 bounds = consdata->bounds; 1793 assert(nvars == 0 || vars != NULL); 1794 assert(nvars == 0 || boundtypes != NULL); 1795 assert(nvars == 0 || bounds != NULL); 1796 1797 for( v = 0; v < nvars; ++v ) 1798 { 1799 SCIP_VAR* var; 1800 1801 var = vars[v]; 1802 assert(var != NULL); 1803 1804 /* constraint should be violated, so all bounds in the constraint have to be violated */ 1805 assert( !(boundtypes[v] == SCIP_BOUNDTYPE_LOWER && isFeasGE(scip, var, SCIPgetSolVal(scip, sol, var), bounds[v])) && /*lint !e666*/ 1806 !(boundtypes[v] == SCIP_BOUNDTYPE_UPPER && isFeasLE(scip, var, SCIPgetSolVal(scip, sol, var), bounds[v])) ); /*lint !e666*/ 1807 1808 varlb = SCIPcomputeVarLbLocal(scip, var); 1809 varub = SCIPcomputeVarUbLocal(scip, var); 1810 1811 /* if literal is x >= varlb, but upper bound on x is < varlb, then this literal can never be satisfied, 1812 * thus there is no use in creating an extra child for it 1813 */ 1814 if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER && isFeasLT(scip, var, varub, bounds[v]) ) 1815 continue; 1816 /* if literal is x <= varub, but lower bound on x is > varub, then this literal can never be satisfied, 1817 * thus there is no use in creating an extra child for it 1818 */ 1819 if( boundtypes[v] == SCIP_BOUNDTYPE_UPPER && isFeasGT(scip, var, varlb, bounds[v]) ) 1820 continue; 1821 /* if literal is always satisfied, then no need to branch on it */ 1822 if( isLiteralSatisfied(scip, consdata, v) ) 1823 continue; 1824 1825 /* create a child that enforces the current literal */ 1826 priority = SCIPcalcNodeselPriority(scip, var, boundtypes[v] == SCIP_BOUNDTYPE_LOWER ? 1827 SCIP_BRANCHDIR_UPWARDS : SCIP_BRANCHDIR_DOWNWARDS, bounds[v]); 1828 estimate = SCIPcalcChildEstimate (scip, var, bounds[v]); 1829 1830 SCIPdebugMsg(scip, " -> creating child to enforce: <%s> %c= %g (priority: %g, estimate: %g)\n", 1831 SCIPvarGetName(vars[v]), boundtypes[v] == SCIP_BOUNDTYPE_LOWER ? '>' : '<', bounds[v], priority, estimate); 1832 1833 SCIP_CALL( SCIPcreateChild(scip, &node, priority, estimate) ); 1834 1835 /* enforce current literal */ 1836 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR ) 1837 { 1838 SCIP_CONS* brcons; 1839 SCIP_Real one; 1840 1841 one = 1.0; 1842 1843 if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER ) 1844 { 1845 SCIP_CALL( SCIPcreateConsLinear(scip, &brcons, "bounddisjbranch", 1, &var, &one, bounds[v], SCIPinfinity(scip), 1846 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), 1847 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons), 1848 SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), 1849 SCIPconsIsStickingAtNode(cons)) ); 1850 } 1851 else 1852 { 1853 SCIP_CALL( SCIPcreateConsLinear(scip, &brcons, "bounddisjbranch", 1, &var, &one, -SCIPinfinity(scip), bounds[v], 1854 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), 1855 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons), 1856 SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), 1857 SCIPconsIsStickingAtNode(cons)) ); 1858 } 1859 SCIP_CALL( SCIPaddConsNode(scip, node, brcons, NULL) ); 1860 SCIP_CALL( SCIPreleaseCons(scip, &brcons) ); 1861 } 1862 else 1863 { 1864 assert(SCIPvarIsActive(var)); 1865 if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER ) 1866 { 1867 SCIP_CALL( SCIPchgVarLbNode(scip, node, var, bounds[v]) ); 1868 } 1869 else 1870 { 1871 SCIP_CALL( SCIPchgVarUbNode(scip, node, var, bounds[v]) ); 1872 } 1873 } 1874 1875 /* delete bound disjunction constraint from child node */ 1876 SCIP_CALL( SCIPdelConsNode(scip, node, cons) ); 1877 } 1878 1879 return SCIP_OKAY; 1880 } 1881 1882 /** helper function to enforce constraints */ 1883 static 1884 SCIP_RETCODE enforceConstraint( 1885 SCIP* scip, /**< SCIP data structure */ 1886 SCIP_CONSHDLR* conshdlr, /**< constraint handler */ 1887 SCIP_CONS** conss, /**< constraints to process */ 1888 int nconss, /**< number of constraints */ 1889 SCIP_SOL* sol, /**< solution to enforce (NULL for the LP solution) */ 1890 SCIP_RESULT* result /**< pointer to store the result of the enforcing call */ 1891 ) 1892 { 1893 SCIP_CONSHDLRDATA* conshdlrdata; 1894 SCIP_Bool cutoff; 1895 SCIP_Bool infeasible; 1896 SCIP_Bool reduceddom; 1897 SCIP_Bool registeredbrcand; 1898 SCIP_Bool infeasiblecons; 1899 int c; 1900 int nnarybranchconsvars; 1901 SCIP_CONS* narybranchcons; /* constraint that is a candidate for an n-ary branch */ 1902 1903 assert(conshdlr != NULL); 1904 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 1905 assert(nconss == 0 || conss != NULL); 1906 assert(result != NULL); 1907 1908 SCIPdebugMsg(scip, "Enforcing %d bound disjunction constraints for %s solution\n", nconss, sol == NULL ? "LP" : "relaxation"); 1909 1910 *result = SCIP_FEASIBLE; 1911 1912 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1913 assert(conshdlrdata != NULL); 1914 1915 cutoff = FALSE; 1916 infeasible = FALSE; 1917 reduceddom = FALSE; 1918 registeredbrcand = FALSE; 1919 narybranchcons = NULL; 1920 nnarybranchconsvars = INT_MAX; 1921 1922 /* check all bound disjunction constraints for feasibility */ 1923 for( c = 0; c < nconss && !cutoff && !reduceddom; ++c ) 1924 { 1925 infeasiblecons = FALSE; 1926 SCIP_CALL( enforceCurrentSol(scip, conss[c], sol, conshdlrdata->eventhdlr, &cutoff, &infeasiblecons, &reduceddom, 1927 ®isteredbrcand) ); 1928 infeasible |= infeasiblecons; 1929 if( infeasiblecons && !registeredbrcand ) 1930 { 1931 /* if cons. c has less literals than the previous candidate for an n-ary branch, then keep cons. c as candidate for n-ary branch */ 1932 if( narybranchcons == NULL || SCIPconsGetData(conss[c])->nvars < nnarybranchconsvars ) 1933 { 1934 narybranchcons = conss[c]; 1935 nnarybranchconsvars = SCIPconsGetData(narybranchcons)->nvars; 1936 assert(nnarybranchconsvars > 0); 1937 } 1938 } 1939 } 1940 1941 if( cutoff ) 1942 *result = SCIP_CUTOFF; 1943 else if( reduceddom ) 1944 *result = SCIP_REDUCEDDOM; 1945 else if( infeasible ) 1946 { 1947 if( registeredbrcand ) 1948 { 1949 *result = SCIP_INFEASIBLE; 1950 } 1951 else 1952 { 1953 SCIP_CALL( createNAryBranch(scip, narybranchcons, sol) ); 1954 *result = SCIP_BRANCHED; 1955 } 1956 } 1957 1958 return SCIP_OKAY; 1959 } 1960 1961 /** adds symmetry information of constraint to a symmetry detection graph */ 1962 static 1963 SCIP_RETCODE addSymmetryInformation( 1964 SCIP* scip, /**< SCIP pointer */ 1965 SYM_SYMTYPE symtype, /**< type of symmetries that need to be added */ 1966 SCIP_CONS* cons, /**< constraint */ 1967 SYM_GRAPH* graph, /**< symmetry detection graph */ 1968 SCIP_Bool* success /**< pointer to store whether symmetry information could be added */ 1969 ) 1970 { 1971 SCIP_CONSDATA* consdata; 1972 SCIP_VAR** vars; 1973 SCIP_Real* vals; 1974 SCIP_Real constant; 1975 SCIP_Real bound = 0.0; 1976 int consnodeidx; 1977 int opnodeidx; 1978 int nodeidx; 1979 int nconsvars; 1980 int nlocvars; 1981 int nvars; 1982 int i; 1983 1984 assert(scip != NULL); 1985 assert(cons != NULL); 1986 assert(graph != NULL); 1987 assert(success != NULL); 1988 1989 *success = TRUE; 1990 1991 consdata = SCIPconsGetData(cons); 1992 assert(consdata != NULL); 1993 1994 /* add node initializing constraint (with artificial rhs) */ 1995 SCIP_CALL( SCIPaddSymgraphConsnode(scip, graph, cons, 0.0, 0.0, &consnodeidx) ); 1996 1997 /* create nodes and edges for each literal in the bounddisjunction */ 1998 nvars = SCIPgetNVars(scip); 1999 nconsvars = consdata->nvars; 2000 2001 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) ); 2002 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) ); 2003 2004 for( i = 0; i < nconsvars; ++i ) 2005 { 2006 /* add node and edge for bound expression of literal */ 2007 SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_BDDISJ, &opnodeidx) ); /*lint !e641*/ 2008 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, consnodeidx, opnodeidx, FALSE, 0.0) ); 2009 2010 /* get active variables */ 2011 vars[0] = consdata->vars[i]; 2012 vals[0] = consdata->boundtypes[i] == SCIP_BOUNDTYPE_UPPER ? 1.0 : -1.0; 2013 nlocvars = 1; 2014 constant = 0.0; 2015 2016 SCIP_CALL( SCIPgetActiveVariables(scip, symtype, &vars, &vals, &nlocvars, &constant, SCIPisTransformed(scip)) ); 2017 2018 /* add node and edge for bound on literal (bound adapted by constant) */ 2019 bound = consdata->boundtypes[i] == SCIP_BOUNDTYPE_UPPER ? consdata->bounds[i] : -consdata->bounds[i]; 2020 bound -= constant; 2021 2022 SCIP_CALL( SCIPaddSymgraphValnode(scip, graph, bound, &nodeidx) ); 2023 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, opnodeidx, nodeidx, FALSE, 0.0) ); 2024 2025 /* check whether variable is (multi-)aggregated */ 2026 nodeidx = opnodeidx; 2027 if( nlocvars > 1 ) 2028 { 2029 /* encode aggregation by a sum-expression and connect it to bdexpr node */ 2030 SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_SUM, &nodeidx) ); /*lint !e641*/ 2031 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, opnodeidx, nodeidx, FALSE, 0.0) ); 2032 } 2033 2034 /* add nodes and edges for variables in aggregation (ignore constant, has been treated above) */ 2035 SCIP_CALL( SCIPaddSymgraphVarAggegration(scip, graph, nodeidx, vars, vals, nlocvars, 0.0) ); 2036 } 2037 2038 SCIPfreeBufferArray(scip, &vals); 2039 SCIPfreeBufferArray(scip, &vars); 2040 2041 return SCIP_OKAY; 2042 } 2043 2044 /**@} */ 2045 2046 /**@name Callback methods of constraint handler 2047 * 2048 * @{ 2049 */ 2050 2051 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 2052 static 2053 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBounddisjunction) 2054 { /*lint --e{715}*/ 2055 assert(scip != NULL); 2056 assert(conshdlr != NULL); 2057 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2058 2059 /* call inclusion method of constraint handler */ 2060 SCIP_CALL( SCIPincludeConshdlrBounddisjunction(scip) ); 2061 2062 *valid = TRUE; 2063 2064 return SCIP_OKAY; 2065 } 2066 2067 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */ 2068 static 2069 SCIP_DECL_CONSFREE(consFreeBounddisjunction) 2070 { /*lint --e{715}*/ 2071 SCIP_CONSHDLRDATA* conshdlrdata; 2072 2073 assert(conshdlr != NULL); 2074 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2075 assert(scip != NULL); 2076 2077 /* free constraint handler data */ 2078 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2079 assert(conshdlrdata != NULL); 2080 2081 conshdlrdataFree(scip, &conshdlrdata); 2082 2083 SCIPconshdlrSetData(conshdlr, NULL); 2084 2085 return SCIP_OKAY; 2086 } 2087 2088 2089 /** presolving deinitialization method of constraint handler (called after presolving has been finished) */ 2090 static 2091 SCIP_DECL_CONSEXITPRE(consExitpreBounddisjunction) 2092 { /*lint --e{715}*/ 2093 SCIP_CONSHDLRDATA* conshdlrdata; 2094 SCIP_CONS* cons; 2095 SCIP_Bool redundant; 2096 int c; 2097 2098 assert(conshdlr != NULL); 2099 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2100 assert(scip != NULL); 2101 2102 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2103 assert(conshdlrdata != NULL); 2104 2105 /* fast processing of constraints, apply global bounds and remove fixed variables */ 2106 for( c = 0; c < nconss; ++c ) 2107 { 2108 cons = conss[c]; 2109 assert(cons != NULL); 2110 2111 SCIPdebugMsg(scip, "exit-presolving bound disjunction constraint <%s>\n", SCIPconsGetName(cons)); 2112 2113 if( SCIPconsIsDeleted(cons) ) 2114 continue; 2115 2116 /* remove all literals that are violated in global bounds, check redundancy due to global bounds */ 2117 SCIP_CALL( applyGlobalBounds(scip, cons, conshdlrdata->eventhdlr, &redundant) ); 2118 2119 if( !redundant ) 2120 { 2121 /* replace variables by their representative active (or multi-aggregated) variables */ 2122 SCIP_CALL( removeFixedVariables(scip, cons, conshdlrdata->eventhdlr, &redundant) ); 2123 } 2124 2125 if( redundant && SCIPconsIsAdded(cons) ) 2126 { 2127 SCIPdebugMsg(scip, "bound disjunction constraint <%s> is redundant\n", SCIPconsGetName(cons)); 2128 SCIP_CALL( SCIPdelCons(scip, cons) ); 2129 } 2130 } 2131 2132 return SCIP_OKAY; 2133 } 2134 2135 /** solving process initialization method of constraint handler */ 2136 static 2137 SCIP_DECL_CONSINITSOL(consInitsolBounddisjunction) 2138 { /*lint --e{715}*/ 2139 /* add nlrow representation to NLP, if NLP had been constructed and disjunction is simple enough */ 2140 if( SCIPisNLPConstructed(scip) ) 2141 { 2142 SCIP_CONSDATA* consdata; 2143 SCIP_NLROW* nlrow; 2144 SCIP_EXPR* expr; 2145 SCIP_EXPR* exprvar; 2146 SCIP_Real lincoef; 2147 SCIP_Real a, b; 2148 int c; 2149 2150 for( c = 0; c < nconss; ++c ) 2151 { 2152 /* skip deactivated or redundant constraints */ 2153 if( !SCIPconsIsActive(conss[c]) || !SCIPconsIsChecked(conss[c]) ) 2154 return SCIP_OKAY; 2155 2156 assert(!SCIPconsIsLocal(conss[c])); /* we are at the root node (or short before) */ 2157 2158 consdata = SCIPconsGetData(conss[c]); 2159 assert(consdata != NULL); 2160 2161 /* look for a bounddisjunction of the form 2162 * x <= a or x >= b with a < b 2163 * only one of the inequalities can be strictly satisfied, so we can reformulate as 2164 * (x-a)*(b-x) <= 0 2165 * this should be sufficient to get bounddisjunction constraints that represent semi-continuous variables into the NLP 2166 */ 2167 2168 if( consdata->nvars != 2 ) 2169 continue; 2170 2171 if( consdata->vars[0] != consdata->vars[1] ) 2172 continue; 2173 2174 if( consdata->boundtypes[0] == SCIP_BOUNDTYPE_UPPER && consdata->boundtypes[1] == SCIP_BOUNDTYPE_LOWER ) 2175 { 2176 a = consdata->bounds[0]; 2177 b = consdata->bounds[1]; 2178 } 2179 else if( consdata->boundtypes[0] == SCIP_BOUNDTYPE_LOWER && consdata->boundtypes[1] == SCIP_BOUNDTYPE_UPPER ) 2180 { 2181 a = consdata->bounds[1]; 2182 b = consdata->bounds[0]; 2183 } 2184 else 2185 { 2186 continue; 2187 } 2188 2189 if( a >= b ) 2190 continue; 2191 2192 SCIP_CALL( SCIPcreateExprVar(scip, &exprvar, consdata->vars[0], NULL, NULL) ); 2193 SCIP_CALL( SCIPcreateExprPow(scip, &expr, exprvar, 2.0, NULL, NULL) ); 2194 2195 /* add xb-xx-ab+ax <= 0 as -ab <= -(a+b)x + x^2 */ 2196 lincoef = -a - b; 2197 SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[c]), 2198 0.0, 1, consdata->vars, &lincoef, expr, -a*b, SCIPinfinity(scip), SCIP_EXPRCURV_CONVEX) ); 2199 2200 SCIP_CALL( SCIPreleaseExpr(scip, &expr) ); 2201 SCIP_CALL( SCIPreleaseExpr(scip, &exprvar) ); 2202 2203 SCIP_CALL( SCIPaddNlRow(scip, nlrow) ); 2204 SCIP_CALL( SCIPreleaseNlRow(scip, &nlrow) ); 2205 } 2206 } 2207 2208 return SCIP_OKAY; 2209 } 2210 2211 /** frees specific constraint data */ 2212 static 2213 SCIP_DECL_CONSDELETE(consDeleteBounddisjunction) 2214 { /*lint --e{715}*/ 2215 assert(conshdlr != NULL); 2216 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2217 assert(consdata != NULL); 2218 assert(*consdata != NULL); 2219 2220 /* free LP row and bound disjunction constraint */ 2221 consdataFree(scip, consdata); 2222 2223 return SCIP_OKAY; 2224 } 2225 2226 2227 /** transforms constraint data into data belonging to the transformed problem */ 2228 static 2229 SCIP_DECL_CONSTRANS(consTransBounddisjunction) 2230 { /*lint --e{715}*/ 2231 SCIP_CONSDATA* sourcedata; 2232 SCIP_CONSDATA* targetdata; 2233 2234 /*debugMsg(scip, "Trans method of bound disjunction constraints\n");*/ 2235 2236 assert(conshdlr != NULL); 2237 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2238 assert(SCIPgetStage(scip) == SCIP_STAGE_TRANSFORMING); 2239 assert(sourcecons != NULL); 2240 assert(targetcons != NULL); 2241 2242 sourcedata = SCIPconsGetData(sourcecons); 2243 assert(sourcedata != NULL); 2244 2245 /* create constraint data for target constraint */ 2246 SCIP_CALL( consdataCreate(scip, &targetdata, sourcedata->nvars, sourcedata->vars, 2247 sourcedata->boundtypes, sourcedata->bounds) ); 2248 2249 /* create target constraint */ 2250 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata, 2251 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons), 2252 SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons), 2253 SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons), 2254 SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) ); 2255 2256 return SCIP_OKAY; 2257 } 2258 2259 2260 /** constraint enforcing method of constraint handler for LP solutions */ 2261 static 2262 SCIP_DECL_CONSENFOLP(consEnfolpBounddisjunction) 2263 { /*lint --e{715}*/ 2264 SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, NULL, result) ); 2265 2266 return SCIP_OKAY; 2267 } 2268 2269 2270 /** constraint enforcing method of constraint handler for relaxation solutions */ 2271 static 2272 SCIP_DECL_CONSENFORELAX(consEnforelaxBounddisjunction) 2273 { /*lint --e{715}*/ 2274 SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, sol, result) ); 2275 2276 return SCIP_OKAY; 2277 } 2278 2279 2280 /** constraint enforcing method of constraint handler for pseudo solutions */ 2281 static 2282 SCIP_DECL_CONSENFOPS(consEnfopsBounddisjunction) 2283 { /*lint --e{715}*/ 2284 SCIP_CONSHDLRDATA* conshdlrdata; 2285 SCIP_Bool cutoff; 2286 SCIP_Bool infeasible; 2287 SCIP_Bool reduceddom; 2288 SCIP_Bool registeredbrcand; 2289 int c; 2290 SCIP_CONS* narybranchcons; /* constraint that is a candidate for an n-ary branch */ 2291 2292 assert(conshdlr != NULL); 2293 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2294 assert(nconss == 0 || conss != NULL); 2295 assert(result != NULL); 2296 2297 SCIPdebugMsg(scip, "pseudo enforcing %d bound disjunction constraints\n", nconss); 2298 2299 *result = SCIP_FEASIBLE; 2300 2301 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2302 assert(conshdlrdata != NULL); 2303 2304 cutoff = FALSE; 2305 infeasible = FALSE; 2306 reduceddom = FALSE; 2307 registeredbrcand = FALSE; 2308 narybranchcons = NULL; 2309 2310 /* check all bound disjunction constraints for feasibility */ 2311 for( c = 0; c < nconss && !cutoff && !reduceddom; ++c ) 2312 { 2313 SCIP_CALL( enforceCurrentSol(scip, conss[c], NULL, conshdlrdata->eventhdlr, &cutoff, &infeasible, &reduceddom, 2314 ®isteredbrcand) ); 2315 if( infeasible && !registeredbrcand ) 2316 { 2317 /* if cons. c has less literals than the previous candidate for an n-ary branch, then keep cons. c as candidate for n-ary branch */ 2318 if( !narybranchcons || SCIPconsGetData(conss[c])->nvars < SCIPconsGetData(narybranchcons)->nvars ) 2319 narybranchcons = conss[c]; 2320 } 2321 } 2322 2323 if( cutoff ) 2324 *result = SCIP_CUTOFF; 2325 else if( reduceddom ) 2326 *result = SCIP_REDUCEDDOM; 2327 else if( infeasible ) 2328 { 2329 if( registeredbrcand ) 2330 { 2331 *result = SCIP_INFEASIBLE; 2332 } 2333 else 2334 { 2335 SCIP_CALL( createNAryBranch(scip, narybranchcons, NULL) ); 2336 *result = SCIP_BRANCHED; 2337 } 2338 } 2339 2340 return SCIP_OKAY; 2341 } 2342 2343 2344 /** feasibility check method of constraint handler for integral solutions */ 2345 static 2346 SCIP_DECL_CONSCHECK(consCheckBounddisjunction) 2347 { /*lint --e{715}*/ 2348 SCIP_CONS* cons; 2349 SCIP_CONSDATA* consdata; 2350 int c; 2351 2352 assert(conshdlr != NULL); 2353 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2354 assert(nconss == 0 || conss != NULL); 2355 assert(result != NULL); 2356 2357 *result = SCIP_FEASIBLE; 2358 2359 /* check all bound disjunction constraints for feasibility */ 2360 for( c = 0; c < nconss && (*result == SCIP_FEASIBLE || completely); ++c ) 2361 { 2362 cons = conss[c]; 2363 consdata = SCIPconsGetData(cons); 2364 assert(consdata != NULL); 2365 2366 if( isConsViolated(scip, cons, sol) ) 2367 { 2368 if( printreason ) 2369 { 2370 int v; 2371 2372 SCIP_CALL( SCIPprintCons(scip, cons, NULL) ); 2373 SCIPinfoMessage(scip, NULL, ";\nviolation: "); 2374 for( v = 0; v < consdata->nvars; ++v ) 2375 { 2376 assert(consdata->vars[v] != NULL); 2377 if( v > 0 ) 2378 SCIPinfoMessage(scip, NULL, ", "); 2379 SCIPinfoMessage(scip, NULL, "<%s> = %.15g", 2380 SCIPvarGetName(consdata->vars[v]), SCIPgetSolVal(scip, sol, consdata->vars[v])); 2381 } 2382 SCIPinfoMessage(scip, NULL, ")\n"); 2383 } 2384 2385 /* constraint is violated */ 2386 *result = SCIP_INFEASIBLE; 2387 } 2388 } 2389 2390 return SCIP_OKAY; 2391 } 2392 2393 2394 /** domain propagation method of constraint handler */ 2395 static 2396 SCIP_DECL_CONSPROP(consPropBounddisjunction) 2397 { /*lint --e{715}*/ 2398 SCIP_CONSHDLRDATA* conshdlrdata; 2399 SCIP_Bool cutoff; 2400 SCIP_Bool infeasible; 2401 SCIP_Bool reduceddom; 2402 SCIP_Bool mustcheck; 2403 SCIP_Bool consreduceddom; 2404 int c; 2405 2406 assert(conshdlr != NULL); 2407 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2408 assert(nconss == 0 || conss != NULL); 2409 assert(result != NULL); 2410 2411 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2412 assert(conshdlrdata != NULL); 2413 2414 cutoff = FALSE; 2415 infeasible = FALSE; 2416 reduceddom = FALSE; 2417 2418 /* propagate all useful bound disjunction constraints */ 2419 for( c = 0; c < nusefulconss && !cutoff; ++c ) 2420 { 2421 SCIP_CALL( processWatchedVars(scip, conss[c], conshdlrdata->eventhdlr, 2422 &cutoff, &infeasible, &consreduceddom, &mustcheck) ); 2423 reduceddom = reduceddom || consreduceddom; 2424 } 2425 2426 /* return the correct result */ 2427 if( cutoff ) 2428 *result = SCIP_CUTOFF; 2429 else if( reduceddom ) 2430 *result = SCIP_REDUCEDDOM; 2431 else 2432 *result = SCIP_DIDNOTFIND; 2433 2434 return SCIP_OKAY; /*lint !e438*/ 2435 } 2436 2437 2438 /** presolving method of constraint handler */ 2439 static 2440 SCIP_DECL_CONSPRESOL(consPresolBounddisjunction) 2441 { /*lint --e{715}*/ 2442 SCIP_CONSHDLRDATA* conshdlrdata; 2443 SCIP_CONS* cons; 2444 SCIP_CONSDATA* consdata; 2445 SCIP_Bool infeasible; 2446 SCIP_Bool redundant; 2447 SCIP_Bool tightened; 2448 int c; 2449 2450 assert(conshdlr != NULL); 2451 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2452 assert(scip != NULL); 2453 assert(result != NULL); 2454 2455 *result = SCIP_DIDNOTFIND; 2456 2457 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2458 assert(conshdlrdata != NULL); 2459 2460 /* process constraints */ 2461 for( c = 0; c < nconss && *result != SCIP_CUTOFF && !SCIPisStopped(scip); ++c ) 2462 { 2463 cons = conss[c]; 2464 assert(cons != NULL); 2465 consdata = SCIPconsGetData(cons); 2466 assert(consdata != NULL); 2467 2468 SCIPdebugMsg(scip, "presolving bound disjunction constraint <%s>\n", SCIPconsGetName(cons)); 2469 2470 /* force presolving the constraint in the initial round */ 2471 if( nrounds == 0 ) 2472 { 2473 SCIP_CALL( SCIPenableConsPropagation(scip, cons) ); 2474 } 2475 2476 /* remove all literals that are violated in global bounds, check redundancy due to global bounds */ 2477 SCIP_CALL( applyGlobalBounds(scip, cons, conshdlrdata->eventhdlr, &redundant) ); 2478 2479 if( !redundant ) 2480 { 2481 /* replace variables by their representative active (or multi-aggregated) variables */ 2482 SCIP_CALL( removeFixedVariables(scip, cons, conshdlrdata->eventhdlr, &redundant) ); 2483 } 2484 2485 /**@todo find pairs of negated variables in constraint: constraint is redundant */ 2486 /**@todo find sets of equal variables in constraint: multiple entries of variable can be replaced by single entry */ 2487 2488 if( redundant ) 2489 { 2490 SCIPdebugMsg(scip, "bound disjunction constraint <%s> is redundant\n", SCIPconsGetName(cons)); 2491 SCIP_CALL( SCIPdelCons(scip, cons) ); 2492 (*ndelconss)++; 2493 *result = SCIP_SUCCESS; 2494 continue; 2495 } 2496 else if( !SCIPconsIsModifiable(cons) ) 2497 { 2498 /* if unmodifiable constraint has no variables, it is infeasible, 2499 * if unmodifiable constraint has only one variable, the literal can be satisfied and the constraint deleted 2500 */ 2501 if( consdata->nvars == 0 ) 2502 { 2503 SCIPdebugMsg(scip, "bound disjunction constraint <%s> is infeasible\n", SCIPconsGetName(cons)); 2504 *result = SCIP_CUTOFF; 2505 return SCIP_OKAY; 2506 } 2507 else if( consdata->nvars == 1 ) 2508 { 2509 SCIPdebugMsg(scip, "bound disjunction constraint <%s> has only one undecided literal\n", 2510 SCIPconsGetName(cons)); 2511 2512 assert(consdata->vars != NULL); 2513 assert(!isLiteralSatisfied(scip, consdata, 0)); 2514 assert(!isLiteralViolated(scip, consdata, 0)); 2515 2516 if( SCIPvarIsActive(consdata->vars[0]) ) 2517 { 2518 if( consdata->boundtypes[0] == SCIP_BOUNDTYPE_LOWER ) 2519 { 2520 SCIP_CALL( SCIPtightenVarLb(scip, consdata->vars[0], consdata->bounds[0], TRUE, &infeasible, &tightened) ); 2521 } 2522 else 2523 { 2524 SCIP_CALL( SCIPtightenVarUb(scip, consdata->vars[0], consdata->bounds[0], TRUE, &infeasible, &tightened) ); 2525 } 2526 if( infeasible ) 2527 { 2528 SCIPdebugMsg(scip, " -> infeasible fixing\n"); 2529 *result = SCIP_CUTOFF; 2530 return SCIP_OKAY; 2531 } 2532 assert(tightened); 2533 (*nchgbds)++; 2534 } 2535 else 2536 { 2537 /* upgrade to a linear constraint, if vars[0] is multi-aggregated */ 2538 SCIP_CONS* lincons; 2539 SCIP_Real one; 2540 2541 assert(SCIPvarGetStatus(consdata->vars[0]) == SCIP_VARSTATUS_MULTAGGR); 2542 2543 one = 1.0; 2544 if( consdata->boundtypes[0] == SCIP_BOUNDTYPE_LOWER ) 2545 { 2546 SCIP_CALL( SCIPcreateConsLinear(scip, &lincons, SCIPconsGetName(cons), 2547 1, &consdata->vars[0], &one, consdata->bounds[0], SCIPinfinity(scip), 2548 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), 2549 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons), 2550 SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), 2551 SCIPconsIsStickingAtNode(cons)) ); 2552 } 2553 else 2554 { 2555 SCIP_CALL( SCIPcreateConsLinear(scip, &lincons, SCIPconsGetName(cons), 2556 1, &consdata->vars[0], &one, -SCIPinfinity(scip), consdata->bounds[0], 2557 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), 2558 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons), 2559 SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), 2560 SCIPconsIsStickingAtNode(cons)) ); 2561 } 2562 SCIP_CALL( SCIPaddCons(scip, lincons) ); 2563 SCIP_CALL( SCIPreleaseCons(scip, &lincons) ); 2564 (*nupgdconss)++; 2565 } 2566 2567 SCIP_CALL( SCIPdelCons(scip, cons) ); 2568 (*ndelconss)++; 2569 *result = SCIP_SUCCESS; 2570 continue; 2571 } 2572 else 2573 { 2574 /* try to upgrade the bounddisjunction constraint */ 2575 SCIP_CALL( upgradeCons(scip, cons, ndelconss, naddconss) ); 2576 } 2577 } 2578 } 2579 2580 /**@todo preprocess pairs of bound disjunction constraints */ 2581 2582 return SCIP_OKAY; 2583 } 2584 2585 2586 /** propagation conflict resolving method of constraint handler */ 2587 static 2588 SCIP_DECL_CONSRESPROP(consRespropBounddisjunction) 2589 { /*lint --e{715}*/ 2590 SCIP_CONSDATA* consdata; 2591 SCIP_VAR** vars; 2592 SCIP_BOUNDTYPE* boundtypes; 2593 #ifndef NDEBUG 2594 SCIP_Real* bounds; 2595 #endif 2596 int v; 2597 2598 assert(conshdlr != NULL); 2599 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2600 assert(cons != NULL); 2601 assert(infervar != NULL); 2602 assert(result != NULL); 2603 2604 consdata = SCIPconsGetData(cons); 2605 assert(consdata != NULL); 2606 assert(consdata->vars != NULL); 2607 assert(consdata->nvars > 0); 2608 assert(0 <= inferinfo && inferinfo < consdata->nvars); 2609 assert(consdata->vars[inferinfo] == infervar); 2610 2611 vars = consdata->vars; 2612 boundtypes = consdata->boundtypes; 2613 #ifndef NDEBUG 2614 bounds = consdata->bounds; 2615 assert(bounds != NULL); 2616 #endif 2617 assert(boundtypes != NULL); 2618 2619 SCIPdebugMsg(scip, "conflict resolving method of bound disjunction constraint handler\n"); 2620 2621 /* the only deductions are bounds tightened to a literal's bound on bound disjunction constraints where all other 2622 * literals are violated 2623 */ 2624 assert((boundtypes[inferinfo] == SCIP_BOUNDTYPE_LOWER 2625 && SCIPisFeasGE(scip, SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE), bounds[inferinfo])) 2626 || (boundtypes[inferinfo] == SCIP_BOUNDTYPE_UPPER 2627 && SCIPisFeasLE(scip, SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE), bounds[inferinfo]))); 2628 2629 for( v = 0; v < consdata->nvars; ++v ) 2630 { 2631 if( v != inferinfo ) 2632 { 2633 assert(consdata->vars[v] != infervar || consdata->boundtypes[v] != consdata->boundtypes[inferinfo]); 2634 2635 /* the reason literal must have been violated 2636 * we do not check for multi-aggregated variables, since SCIPvarGetXbAtIndex is not implemented for them */ 2637 /* Use a weaker comparison to SCIPvarGetXbAtIndex here (i.e., SCIPisXT instead of SCIPisFeasXT), 2638 * because SCIPvarGetXbAtIndex might differ from the local bound at time bdchgidx by epsilon. */ 2639 assert(SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_MULTAGGR 2640 || (boundtypes[v] == SCIP_BOUNDTYPE_LOWER 2641 && SCIPisLT(scip, SCIPgetVarUbAtIndex(scip, vars[v], bdchgidx, TRUE), bounds[v])) 2642 || (boundtypes[v] == SCIP_BOUNDTYPE_UPPER 2643 && SCIPisGT(scip, SCIPgetVarLbAtIndex(scip, vars[v], bdchgidx, TRUE), bounds[v]))); 2644 SCIP_CALL( SCIPaddConflictBd(scip, vars[v], SCIPboundtypeOpposite(boundtypes[v]), bdchgidx) ); 2645 } 2646 } 2647 2648 *result = SCIP_SUCCESS; 2649 2650 return SCIP_OKAY; 2651 } 2652 2653 2654 /** variable rounding lock method of constraint handler */ 2655 static 2656 SCIP_DECL_CONSLOCK(consLockBounddisjunction) 2657 { /*lint --e{715}*/ 2658 SCIP_CONSDATA* consdata; 2659 int i; 2660 2661 consdata = SCIPconsGetData(cons); 2662 assert(consdata != NULL); 2663 2664 /* lock every single coefficient */ 2665 for( i = 0; i < consdata->nvars; ++i ) 2666 { 2667 if( consdata->boundtypes[i] == SCIP_BOUNDTYPE_LOWER ) 2668 { 2669 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[i], locktype, nlockspos, nlocksneg) ); 2670 } 2671 else 2672 { 2673 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[i], locktype, nlocksneg, nlockspos) ); 2674 } 2675 } 2676 2677 return SCIP_OKAY; 2678 } 2679 2680 2681 /** constraint activation notification method of constraint handler */ 2682 static 2683 SCIP_DECL_CONSACTIVE(consActiveBounddisjunction) 2684 { /*lint --e{715}*/ 2685 SCIP_CONSHDLRDATA* conshdlrdata; 2686 SCIP_CONSDATA* consdata; 2687 2688 assert(conshdlr != NULL); 2689 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2690 assert(cons != NULL); 2691 assert(SCIPconsIsTransformed(cons)); 2692 2693 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2694 assert(conshdlrdata != NULL); 2695 consdata = SCIPconsGetData(cons); 2696 assert(consdata != NULL); 2697 assert(consdata->watchedvar1 == -1 || consdata->watchedvar1 != consdata->watchedvar2); 2698 2699 SCIPdebugMsg(scip, "activating information for bound disjunction constraint <%s>\n", SCIPconsGetName(cons)); 2700 SCIPdebug(consdataPrint(scip, consdata, NULL, TRUE)); 2701 2702 /* catch events on watched variables */ 2703 if( consdata->watchedvar1 != -1 ) 2704 { 2705 SCIP_CALL( catchEvents(scip, cons, consdata, conshdlrdata->eventhdlr, consdata->watchedvar1, 2706 &consdata->filterpos1) ); 2707 } 2708 if( consdata->watchedvar2 != -1 ) 2709 { 2710 SCIP_CALL( catchEvents(scip, cons, consdata, conshdlrdata->eventhdlr, consdata->watchedvar2, 2711 &consdata->filterpos2) ); 2712 } 2713 2714 return SCIP_OKAY; 2715 } 2716 2717 2718 /** constraint deactivation notification method of constraint handler */ 2719 static 2720 SCIP_DECL_CONSDEACTIVE(consDeactiveBounddisjunction) 2721 { /*lint --e{715}*/ 2722 SCIP_CONSHDLRDATA* conshdlrdata; 2723 SCIP_CONSDATA* consdata; 2724 2725 assert(conshdlr != NULL); 2726 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2727 assert(cons != NULL); 2728 assert(SCIPconsIsTransformed(cons)); 2729 2730 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2731 assert(conshdlrdata != NULL); 2732 consdata = SCIPconsGetData(cons); 2733 assert(consdata != NULL); 2734 assert(consdata->watchedvar1 == -1 || consdata->watchedvar1 != consdata->watchedvar2); 2735 2736 SCIPdebugMsg(scip, "deactivating information for bound disjunction constraint <%s>\n", SCIPconsGetName(cons)); 2737 SCIPdebug(consdataPrint(scip, consdata, NULL, TRUE)); 2738 2739 /* drop events on watched variables */ 2740 if( consdata->watchedvar1 != -1 ) 2741 { 2742 assert(consdata->filterpos1 != -1); 2743 SCIP_CALL( dropEvents(scip, cons, consdata, conshdlrdata->eventhdlr, consdata->watchedvar1, consdata->filterpos1) ); 2744 consdata->watchedvar1 = -1; 2745 } 2746 if( consdata->watchedvar2 != -1 ) 2747 { 2748 assert(consdata->filterpos2 != -1); 2749 SCIP_CALL( dropEvents(scip, cons, consdata, conshdlrdata->eventhdlr, consdata->watchedvar2, consdata->filterpos2) ); 2750 consdata->watchedvar2 = -1; 2751 } 2752 2753 return SCIP_OKAY; 2754 } 2755 2756 2757 /** constraint display method of constraint handler */ 2758 static 2759 SCIP_DECL_CONSPRINT(consPrintBounddisjunction) 2760 { /*lint --e{715}*/ 2761 assert( scip != NULL ); 2762 assert( conshdlr != NULL ); 2763 assert( cons != NULL ); 2764 2765 consdataPrint(scip, SCIPconsGetData(cons), file, FALSE); 2766 2767 return SCIP_OKAY; 2768 } 2769 2770 /** constraint copying method of constraint handler */ 2771 static 2772 SCIP_DECL_CONSCOPY(consCopyBounddisjunction) 2773 { /*lint --e{715}*/ 2774 SCIP_VAR** sourcevars; 2775 SCIP_VAR** targetvars; 2776 SCIP_BOUNDTYPE* boundtypes; 2777 SCIP_Real* bounds; 2778 int nvars; 2779 int v; 2780 2781 assert(valid != NULL); 2782 2783 *valid = TRUE; 2784 2785 /* get source data */ 2786 sourcevars = SCIPgetVarsBounddisjunction(sourcescip, sourcecons); 2787 nvars = SCIPgetNVarsBounddisjunction(sourcescip, sourcecons); 2788 boundtypes = SCIPgetBoundtypesBounddisjunction(sourcescip, sourcecons); 2789 bounds = SCIPgetBoundsBounddisjunction(sourcescip, sourcecons); 2790 2791 SCIP_CALL( SCIPallocBufferArray(scip, &targetvars, nvars) ); 2792 2793 /* map source variables to active variables of the target SCIP */ 2794 for( v = 0; v < nvars && *valid; ++v ) 2795 { 2796 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &targetvars[v], varmap, consmap, global, valid) ); 2797 assert(!(*valid) || targetvars[v] != NULL); 2798 } 2799 2800 /* only create the target constraint, if all variables could be copied */ 2801 if( *valid ) 2802 { 2803 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, cons, name ? name : SCIPconsGetName(sourcecons), nvars, targetvars, boundtypes, 2804 bounds, initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) ); 2805 } 2806 2807 SCIPfreeBufferArray(scip, &targetvars); 2808 2809 return SCIP_OKAY; 2810 } 2811 2812 /** constraint parsing method of constraint handler */ 2813 static 2814 SCIP_DECL_CONSPARSE(consParseBounddisjunction) 2815 { /*lint --e{715}*/ 2816 SCIP_BOUNDTYPE* boundtypes; 2817 SCIP_Real* bounds; 2818 SCIP_VAR** vars; 2819 char* endptr; 2820 int varssize; 2821 int nvars; 2822 2823 assert( success != NULL ); 2824 *success = TRUE; 2825 2826 SCIPdebugMsg(scip, "parse <%s> as bounddisjunction constraint\n", str); 2827 2828 /* skip white space */ 2829 SCIP_CALL( SCIPskipSpace((char**)&str) ); 2830 2831 /* check for string "bounddisjunction" */ 2832 if( strncmp(str, "bounddisjunction(", 16) != 0 ) 2833 { 2834 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "error during parsing: expected \"bounddisjunction(\" in <%s>.\n", str); 2835 *success = FALSE; 2836 return SCIP_OKAY; 2837 } 2838 2839 /* skip "bounddisjunction(" */ 2840 str += 17; 2841 2842 varssize = 100; 2843 nvars = 0; 2844 2845 /* allocate buffer array for variables */ 2846 SCIP_CALL( SCIPallocBufferArray(scip, &vars, varssize) ); 2847 SCIP_CALL( SCIPallocBufferArray(scip, &boundtypes, varssize) ); 2848 SCIP_CALL( SCIPallocBufferArray(scip, &bounds, varssize) ); 2849 2850 /* parse string until ")" */ 2851 while( *str != ')' ) 2852 { 2853 SCIP_VAR* var; 2854 2855 /* parse variable name */ 2856 SCIP_CALL( SCIPparseVarName(scip, str, &var, &endptr) ); 2857 2858 if( var == NULL ) 2859 { 2860 endptr = strchr(endptr, ')'); 2861 2862 if( endptr == NULL ) 2863 { 2864 *success = FALSE; 2865 goto TERMINATE; 2866 } 2867 2868 break; 2869 } 2870 2871 str = endptr; 2872 2873 /* skip white space */ 2874 SCIP_CALL( SCIPskipSpace((char**)&str) ); 2875 2876 /* parse bound type */ 2877 switch( *str ) 2878 { 2879 case '<': 2880 boundtypes[nvars] = SCIP_BOUNDTYPE_UPPER; 2881 break; 2882 case '>': 2883 boundtypes[nvars] = SCIP_BOUNDTYPE_LOWER; 2884 break; 2885 default: 2886 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "variable with name <%s> does not exist\n", SCIPvarGetName(var)); 2887 *success = FALSE; 2888 goto TERMINATE; 2889 } 2890 2891 ++str; 2892 if( *str != '=' ) 2893 { 2894 SCIPdebugMsg(scip, "expected '=': %s\n", str); 2895 *success = FALSE; 2896 goto TERMINATE; 2897 } 2898 2899 /* skip '=' */ 2900 ++str; 2901 2902 /* parse bound value */ 2903 if( !SCIPparseReal(scip, str, &bounds[nvars], &endptr) ) 2904 { 2905 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Syntax error during parsing of the weight: %s\n", str); 2906 *success = FALSE; 2907 goto TERMINATE; 2908 } 2909 2910 str = endptr; 2911 2912 /* set variable */ 2913 vars[nvars++] = var; 2914 2915 /* check if the size of the variable array was big enough */ 2916 if( nvars > varssize ) 2917 { 2918 /* reallocate memory */ 2919 varssize *= 2; 2920 SCIP_CALL( SCIPreallocBufferArray(scip, &vars, varssize) ); 2921 SCIP_CALL( SCIPreallocBufferArray(scip, &boundtypes, varssize) ); 2922 SCIP_CALL( SCIPreallocBufferArray(scip, &bounds, varssize) ); 2923 } 2924 2925 /* skip white space */ 2926 SCIP_CALL( SCIPskipSpace((char**)&str) ); 2927 2928 /* skip ',' */ 2929 if( *str == ',' ) 2930 ++str; 2931 } 2932 2933 /* add bounddisjunction */ 2934 if( *success && nvars > 0 ) 2935 { 2936 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, cons, name, nvars, vars, boundtypes, bounds, 2937 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) ); 2938 } 2939 2940 TERMINATE: 2941 /* free variable buffer */ 2942 SCIPfreeBufferArray(scip, &bounds); 2943 SCIPfreeBufferArray(scip, &boundtypes); 2944 SCIPfreeBufferArray(scip, &vars); 2945 2946 return SCIP_OKAY; 2947 } 2948 2949 /** constraint method of constraint handler which returns the variables (if possible) */ 2950 static 2951 SCIP_DECL_CONSGETVARS(consGetVarsBounddisjunction) 2952 { /*lint --e{715}*/ 2953 SCIP_CONSDATA* consdata; 2954 2955 assert(cons != NULL); 2956 2957 consdata = SCIPconsGetData(cons); 2958 assert(consdata != NULL); 2959 2960 if( varssize < consdata->nvars ) 2961 (*success) = FALSE; 2962 else 2963 { 2964 assert(vars != NULL); 2965 2966 BMScopyMemoryArray(vars, consdata->vars, consdata->nvars); 2967 (*success) = TRUE; 2968 } 2969 2970 return SCIP_OKAY; 2971 } 2972 2973 /** constraint method of constraint handler which returns the number of variables (if possible) */ 2974 static 2975 SCIP_DECL_CONSGETNVARS(consGetNVarsBounddisjunction) 2976 { /*lint --e{715}*/ 2977 SCIP_CONSDATA* consdata; 2978 2979 assert(cons != NULL); 2980 2981 consdata = SCIPconsGetData(cons); 2982 assert(consdata != NULL); 2983 2984 (*nvars) = consdata->nvars; 2985 (*success) = TRUE; 2986 2987 return SCIP_OKAY; 2988 } 2989 2990 /** constraint handler method which returns the permutation symmetry detection graph of a constraint */ 2991 static 2992 SCIP_DECL_CONSGETPERMSYMGRAPH(consGetPermsymGraphBounddisjunction) 2993 { /*lint --e{715}*/ 2994 SCIP_CALL( addSymmetryInformation(scip, SYM_SYMTYPE_PERM, cons, graph, success) ); 2995 2996 return SCIP_OKAY; 2997 } 2998 2999 /** constraint handler method which returns the signed permutation symmetry detection graph of a constraint */ 3000 static 3001 SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(consGetSignedPermsymGraphBounddisjunction) 3002 { /*lint --e{715}*/ 3003 SCIP_CALL( addSymmetryInformation(scip, SYM_SYMTYPE_SIGNPERM, cons, graph, success) ); 3004 3005 return SCIP_OKAY; 3006 } 3007 3008 /**@} */ 3009 3010 /**@name Callback methods of event handler 3011 * 3012 * @{ 3013 */ 3014 3015 static 3016 SCIP_DECL_EVENTEXEC(eventExecBounddisjunction) 3017 { /*lint --e{715}*/ 3018 assert(eventhdlr != NULL); 3019 assert(eventdata != NULL); 3020 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0); 3021 assert(event != NULL); 3022 3023 /*SCIPdebugMsg(scip, "exec method of event handler for bound disjunction constraints\n");*/ 3024 3025 assert(SCIPconsGetData((SCIP_CONS*)eventdata) != NULL); 3026 assert(SCIPconsIsActive((SCIP_CONS*)eventdata) || SCIPconsIsUpdatedeactivate((SCIP_CONS*)eventdata)); 3027 3028 if( (SCIPeventGetType(event) & SCIP_EVENTTYPE_BOUNDRELAXED) != 0 ) 3029 { 3030 SCIP_CALL( SCIPenableCons(scip, (SCIP_CONS*)eventdata) ); 3031 } 3032 else 3033 assert((SCIPeventGetType(event) & SCIP_EVENTTYPE_BOUNDTIGHTENED) != 0); 3034 3035 SCIP_CALL( SCIPenableConsPropagation(scip, (SCIP_CONS*)eventdata) ); 3036 3037 return SCIP_OKAY; 3038 } 3039 3040 /**@} */ 3041 3042 /**@name Callback methods of conflict handler 3043 * 3044 * @{ 3045 */ 3046 3047 /** conflict handler data struct */ 3048 struct SCIP_ConflicthdlrData 3049 { 3050 SCIP_Real continuousfrac; /**< maximal percantage of continuous variables within a conflict */ 3051 }; 3052 3053 /** conflict processing method of conflict handler (called when conflict was found) */ 3054 static 3055 SCIP_DECL_CONFLICTEXEC(conflictExecBounddisjunction) 3056 { /*lint --e{715}*/ 3057 SCIP_VAR** vars; 3058 SCIP_CONFLICTHDLRDATA* conflicthdlrdata; 3059 SCIP_BOUNDTYPE* boundtypes; 3060 SCIP_Real* bounds; 3061 SCIP_CONS* cons; 3062 char consname[SCIP_MAXSTRLEN]; 3063 int nliterals; 3064 int ncontinuous; 3065 int i; 3066 3067 assert(conflicthdlr != NULL); 3068 assert(strcmp(SCIPconflicthdlrGetName(conflicthdlr), CONFLICTHDLR_NAME) == 0); 3069 assert(bdchginfos != NULL || nbdchginfos == 0); 3070 assert(result != NULL); 3071 3072 /* don't process already resolved conflicts */ 3073 if( resolved ) 3074 { 3075 *result = SCIP_DIDNOTRUN; 3076 return SCIP_OKAY; 3077 } 3078 3079 conflicthdlrdata = SCIPconflicthdlrGetData(conflicthdlr); 3080 assert(conflicthdlrdata != NULL); 3081 3082 *result = SCIP_DIDNOTFIND; 3083 ncontinuous = 0; 3084 3085 /* create array of variables, boundtypes, and bound values in conflict constraint */ 3086 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nbdchginfos) ); 3087 SCIP_CALL( SCIPallocBufferArray(scip, &boundtypes, nbdchginfos) ); 3088 SCIP_CALL( SCIPallocBufferArray(scip, &bounds, nbdchginfos) ); 3089 3090 nliterals = 0; 3091 3092 for( i = 0; i < nbdchginfos; ++i ) 3093 { 3094 SCIP_VAR* var; 3095 SCIP_Real bound; 3096 SCIP_BOUNDTYPE boundtype; 3097 int j; 3098 3099 assert(bdchginfos != NULL); 3100 3101 var = SCIPbdchginfoGetVar(bdchginfos[i]); 3102 assert(var != NULL); 3103 3104 boundtype = SCIPboundtypeOpposite(SCIPbdchginfoGetBoundtype(bdchginfos[i])); 3105 bound = relaxedbds[i]; 3106 3107 /* for continuous variables, we can only use the relaxed version of the bounds negation: !(x <= u) -> x >= u */ 3108 if( SCIPvarIsIntegral(var) ) 3109 bound += (boundtype == SCIP_BOUNDTYPE_LOWER ? +1.0 : -1.0); 3110 3111 /* check whether we have seen the variable before */ 3112 for( j = nliterals-1; j >= 0; --j ) 3113 { 3114 if( vars[j] != var ) 3115 continue; 3116 3117 /* check whether both literals contribute with the same bound type */ 3118 if( boundtypes[j] == boundtype ) 3119 { 3120 /* check whether the lower bound can be relaxed */ 3121 if( boundtype == SCIP_BOUNDTYPE_LOWER && SCIPisLT(scip, bound, bounds[j]) ) 3122 { 3123 SCIPdebugMsg(scip, "relax lower bound of variable <%s> from %g to %g in bounddisjunction conflict\n", 3124 SCIPvarGetName(var), bounds[j], bound); 3125 bounds[j] = bound; 3126 } 3127 /* check whether the upper bound can be relaxed */ 3128 else if( boundtype == SCIP_BOUNDTYPE_UPPER && SCIPisGT(scip, bound, bounds[j]) ) 3129 { 3130 SCIPdebugMsg(scip, "relax upper bound of variable <%s> from %g to %g in bounddisjunction conflict\n", 3131 SCIPvarGetName(var), bounds[j], bound); 3132 bounds[j] = bound; 3133 } 3134 3135 continue; 3136 } 3137 /* check whether the bounds are overlapping */ 3138 else if( isOverlapping(scip, var, boundtype, bound, boundtypes[j], bounds[j]) ) 3139 { 3140 /* the conflict is redundant -> discard the conflict constraint */ 3141 SCIPdebugMsg(scip, "redundant bounddisjunction conflict due to overlapping\n"); 3142 goto DISCARDCONFLICT; 3143 } 3144 } 3145 3146 vars[nliterals] = var; 3147 boundtypes[nliterals] = boundtype; 3148 bounds[nliterals] = bound; 3149 3150 /* check if the relaxed bound is really a relaxed bound */ 3151 assert(SCIPbdchginfoGetBoundtype(bdchginfos[i]) == SCIP_BOUNDTYPE_LOWER || SCIPisGE(scip, relaxedbds[i], SCIPbdchginfoGetNewbound(bdchginfos[i]))); 3152 assert(SCIPbdchginfoGetBoundtype(bdchginfos[i]) == SCIP_BOUNDTYPE_UPPER || SCIPisLE(scip, relaxedbds[i], SCIPbdchginfoGetNewbound(bdchginfos[i]))); 3153 3154 /* for continuous variables, we can only use the relaxed version of the bounds negation: !(x <= u) -> x >= u */ 3155 if( !SCIPvarIsIntegral(vars[nliterals]) ) 3156 { 3157 if( (boundtypes[i] == SCIP_BOUNDTYPE_LOWER && SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(var), bounds[nliterals])) 3158 || (boundtypes[i] == SCIP_BOUNDTYPE_UPPER && SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(var), bounds[nliterals])) ) 3159 { 3160 /* the literal is satisfied in global bounds (may happen due to weak "negation" of continuous variables) 3161 * -> discard the conflict constraint 3162 */ 3163 SCIPdebugMsg(scip, "redundant bounddisjunction conflict due to globally fulfilled literal\n"); 3164 goto DISCARDCONFLICT; 3165 } 3166 else 3167 ncontinuous++; 3168 } 3169 3170 nliterals++; 3171 } 3172 3173 /* create a constraint out of the conflict set */ 3174 if( i == nbdchginfos && ncontinuous < conflicthdlrdata->continuousfrac * nbdchginfos + 0.5 ) 3175 { 3176 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "cf%d_%" SCIP_LONGINT_FORMAT, SCIPgetNRuns(scip), SCIPgetNConflictConssApplied(scip)); 3177 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &cons, consname, nliterals, vars, boundtypes, bounds, 3178 FALSE, FALSE, FALSE, FALSE, TRUE, local, FALSE, dynamic, removable, FALSE) ); 3179 3180 /* add conflict to SCIP */ 3181 SCIP_CALL( SCIPaddConflict(scip, node, cons, validnode, conftype, cutoffinvolved) ); 3182 SCIPdebugMsg(scip, "added conflict\n"); 3183 *result = SCIP_CONSADDED; 3184 } 3185 3186 DISCARDCONFLICT: 3187 /* free temporary memory */ 3188 SCIPfreeBufferArray(scip, &bounds); 3189 SCIPfreeBufferArray(scip, &boundtypes); 3190 SCIPfreeBufferArray(scip, &vars); 3191 3192 return SCIP_OKAY; 3193 } 3194 3195 /** free method of conflict handler */ 3196 static 3197 SCIP_DECL_CONFLICTFREE(conflictFreeBounddisjunction) 3198 { 3199 SCIP_CONFLICTHDLRDATA* conflicthdlrdata; 3200 3201 assert(conflicthdlr != NULL); 3202 3203 /* get conflict handler data */ 3204 conflicthdlrdata = SCIPconflicthdlrGetData(conflicthdlr); 3205 assert(conflicthdlrdata != NULL); 3206 3207 /* free conflict handler structure */ 3208 SCIPfreeBlockMemory(scip, &conflicthdlrdata); 3209 3210 return SCIP_OKAY; 3211 } 3212 3213 /**@} */ 3214 3215 /** creates the handler for bound disjunction constraints and includes it in SCIP */ 3216 SCIP_RETCODE SCIPincludeConshdlrBounddisjunction( 3217 SCIP* scip /**< SCIP data structure */ 3218 ) 3219 { 3220 SCIP_CONSHDLRDATA* conshdlrdata; 3221 SCIP_CONFLICTHDLRDATA* conflicthdlrdata; 3222 SCIP_CONFLICTHDLR* conflicthdlr; 3223 SCIP_CONSHDLR* conshdlr; 3224 SCIP_EVENTHDLR* eventhdlr; 3225 3226 /* create event handler for events on watched variables */ 3227 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, 3228 eventExecBounddisjunction, NULL) ); 3229 3230 /* allocate memory for conflict handler data */ 3231 SCIP_CALL( SCIPallocBlockMemory(scip, &conflicthdlrdata) ); 3232 3233 /* create conflict handler parameter */ 3234 SCIP_CALL( SCIPaddRealParam(scip, 3235 "conflict/" CONSHDLR_NAME "/continuousfrac", "maximal percantage of continuous variables within a conflict", 3236 &conflicthdlrdata->continuousfrac, FALSE, DEFAULT_CONTINUOUSFRAC, 0.0, 1.0, NULL, NULL) ); 3237 3238 /* create conflict handler for bound disjunction constraints */ 3239 SCIP_CALL( SCIPincludeConflicthdlrBasic(scip, &conflicthdlr, CONFLICTHDLR_NAME, CONFLICTHDLR_DESC, CONFLICTHDLR_PRIORITY, 3240 conflictExecBounddisjunction, conflicthdlrdata) ); 3241 3242 SCIP_CALL( SCIPsetConflicthdlrFree(scip, conflicthdlr, conflictFreeBounddisjunction) ); 3243 3244 /* create constraint handler data */ 3245 SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlr) ); 3246 3247 /* include constraint handler */ 3248 SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC, 3249 CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS, 3250 consEnfolpBounddisjunction, consEnfopsBounddisjunction, consCheckBounddisjunction, consLockBounddisjunction, 3251 conshdlrdata) ); 3252 3253 assert(conshdlr != NULL); 3254 3255 /* set non-fundamental callbacks via specific setter functions */ 3256 SCIP_CALL( SCIPsetConshdlrActive(scip, conshdlr, consActiveBounddisjunction) ); 3257 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyBounddisjunction, consCopyBounddisjunction) ); 3258 SCIP_CALL( SCIPsetConshdlrDeactive(scip, conshdlr, consDeactiveBounddisjunction) ); 3259 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteBounddisjunction) ); 3260 SCIP_CALL( SCIPsetConshdlrExitpre(scip, conshdlr, consExitpreBounddisjunction) ); 3261 SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolBounddisjunction) ); 3262 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeBounddisjunction) ); 3263 SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsBounddisjunction) ); 3264 SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsBounddisjunction) ); 3265 SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseBounddisjunction) ); 3266 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolBounddisjunction, CONSHDLR_MAXPREROUNDS, 3267 CONSHDLR_PRESOLTIMING) ); 3268 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintBounddisjunction) ); 3269 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropBounddisjunction, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, 3270 CONSHDLR_PROP_TIMING) ); 3271 SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropBounddisjunction) ); 3272 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransBounddisjunction) ); 3273 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxBounddisjunction) ); 3274 SCIP_CALL( SCIPsetConshdlrGetPermsymGraph(scip, conshdlr, consGetPermsymGraphBounddisjunction) ); 3275 SCIP_CALL( SCIPsetConshdlrGetSignedPermsymGraph(scip, conshdlr, consGetSignedPermsymGraphBounddisjunction) ); 3276 3277 return SCIP_OKAY; 3278 } 3279 3280 3281 /** creates and captures a bound disjunction constraint 3282 * 3283 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 3284 */ 3285 SCIP_RETCODE SCIPcreateConsBounddisjunction( 3286 SCIP* scip, /**< SCIP data structure */ 3287 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 3288 const char* name, /**< name of constraint */ 3289 int nvars, /**< number of variables in the constraint */ 3290 SCIP_VAR** vars, /**< variables of the literals in the constraint */ 3291 SCIP_BOUNDTYPE* boundtypes, /**< types of bounds of the literals (lower or upper bounds) */ 3292 SCIP_Real* bounds, /**< bounds of the literals */ 3293 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? 3294 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */ 3295 SCIP_Bool separate, /**< should the constraint be separated during LP processing? 3296 * Usually set to TRUE. */ 3297 SCIP_Bool enforce, /**< should the constraint be enforced during node processing? 3298 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 3299 SCIP_Bool check, /**< should the constraint be checked for feasibility? 3300 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 3301 SCIP_Bool propagate, /**< should the constraint be propagated during node processing? 3302 * Usually set to TRUE. */ 3303 SCIP_Bool local, /**< is constraint only valid locally? 3304 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */ 3305 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? 3306 * Usually set to FALSE. In column generation applications, set to TRUE if pricing 3307 * adds coefficients to this constraint. */ 3308 SCIP_Bool dynamic, /**< is constraint subject to aging? 3309 * Usually set to FALSE. Set to TRUE for own cuts which 3310 * are separated as constraints. */ 3311 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? 3312 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */ 3313 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even 3314 * if it may be moved to a more global node? 3315 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */ 3316 ) 3317 { 3318 SCIP_CONSHDLR* conshdlr; 3319 SCIP_CONSDATA* consdata; 3320 3321 assert(scip != NULL); 3322 3323 /* find the bounddisjunction constraint handler */ 3324 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME); 3325 if( conshdlr == NULL ) 3326 { 3327 SCIPerrorMessage("bound disjunction constraint handler not found\n"); 3328 return SCIP_PLUGINNOTFOUND; 3329 } 3330 3331 #ifndef NDEBUG 3332 { 3333 int v1; 3334 /* ensure that the given data neither contains overlapping nor redundant literals */ 3335 for( v1 = 0; v1 < nvars; v1++ ) 3336 { 3337 int v2; 3338 for( v2 = v1+1; v2 < nvars; v2++ ) 3339 { 3340 assert(vars[v1] != vars[v2] || (SCIPboundtypeOpposite(boundtypes[v1]) == boundtypes[v2] 3341 && !isOverlapping(scip, vars[v1], boundtypes[v1], bounds[v1], boundtypes[v2], bounds[v2]))); 3342 } 3343 } 3344 } 3345 #endif 3346 3347 /* create the constraint specific data */ 3348 SCIP_CALL( consdataCreate(scip, &consdata, nvars, vars, boundtypes, bounds) ); 3349 3350 /* create constraint */ 3351 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate, 3352 local, modifiable, dynamic, removable, stickingatnode) ); 3353 3354 return SCIP_OKAY; 3355 } 3356 3357 /** creates and captures a bound disjunction constraint 3358 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the 3359 * method SCIPcreateConsBounddisjunction(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h 3360 * 3361 * @see SCIPcreateConsBounddisjunction() for information about the basic constraint flag configuration 3362 * 3363 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 3364 */ 3365 SCIP_RETCODE SCIPcreateConsBasicBounddisjunction( 3366 SCIP* scip, /**< SCIP data structure */ 3367 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 3368 const char* name, /**< name of constraint */ 3369 int nvars, /**< number of variables in the constraint */ 3370 SCIP_VAR** vars, /**< variables of the literals in the constraint */ 3371 SCIP_BOUNDTYPE* boundtypes, /**< types of bounds of the literals (lower or upper bounds) */ 3372 SCIP_Real* bounds /**< bounds of the literals */ 3373 ) 3374 { 3375 assert(scip != NULL); 3376 3377 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, cons, name, nvars, vars, boundtypes, bounds, 3378 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 3379 3380 return SCIP_OKAY; 3381 } 3382 3383 /** creates and captures a bound disjunction constraint with possibly redundant literals 3384 * 3385 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 3386 */ 3387 SCIP_RETCODE SCIPcreateConsBounddisjunctionRedundant( 3388 SCIP* scip, /**< SCIP data structure */ 3389 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 3390 const char* name, /**< name of constraint */ 3391 int nvars, /**< number of variables in the constraint */ 3392 SCIP_VAR** vars, /**< variables of the literals in the constraint */ 3393 SCIP_BOUNDTYPE* boundtypes, /**< types of bounds of the literals (lower or upper bounds) */ 3394 SCIP_Real* bounds, /**< bounds of the literals */ 3395 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? 3396 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */ 3397 SCIP_Bool separate, /**< should the constraint be separated during LP processing? 3398 * Usually set to TRUE. */ 3399 SCIP_Bool enforce, /**< should the constraint be enforced during node processing? 3400 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 3401 SCIP_Bool check, /**< should the constraint be checked for feasibility? 3402 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 3403 SCIP_Bool propagate, /**< should the constraint be propagated during node processing? 3404 * Usually set to TRUE. */ 3405 SCIP_Bool local, /**< is constraint only valid locally? 3406 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */ 3407 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? 3408 * Usually set to FALSE. In column generation applications, set to TRUE if pricing 3409 * adds coefficients to this constraint. */ 3410 SCIP_Bool dynamic, /**< is constraint subject to aging? 3411 * Usually set to FALSE. Set to TRUE for own cuts which 3412 * are separated as constraints. */ 3413 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? 3414 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */ 3415 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even 3416 * if it may be moved to a more global node? 3417 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */ 3418 ) 3419 { 3420 SCIP_CONSHDLR* conshdlr; 3421 SCIP_CONSDATA* consdata; 3422 3423 assert(scip != NULL); 3424 3425 /* find the bounddisjunction constraint handler */ 3426 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME); 3427 if( conshdlr == NULL ) 3428 { 3429 SCIPerrorMessage("bound disjunction constraint handler not found\n"); 3430 return SCIP_PLUGINNOTFOUND; 3431 } 3432 3433 /* create the constraint specific data */ 3434 SCIP_CALL( consdataCreateRedundant(scip, &consdata, nvars, vars, boundtypes, bounds) ); 3435 3436 /* create constraint */ 3437 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate, 3438 local, modifiable, dynamic, removable, stickingatnode) ); 3439 3440 return SCIP_OKAY; 3441 } 3442 3443 /** creates and captures a bound disjunction constraint with possibly redundant literals 3444 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the 3445 * method SCIPcreateConsBounddisjunction(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h 3446 * 3447 * @see SCIPcreateConsBounddisjunction() for information about the basic constraint flag configuration 3448 * 3449 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 3450 */ 3451 SCIP_RETCODE SCIPcreateConsBasicBounddisjunctionRedundant( 3452 SCIP* scip, /**< SCIP data structure */ 3453 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 3454 const char* name, /**< name of constraint */ 3455 int nvars, /**< number of variables in the constraint */ 3456 SCIP_VAR** vars, /**< variables of the literals in the constraint */ 3457 SCIP_BOUNDTYPE* boundtypes, /**< types of bounds of the literals (lower or upper bounds) */ 3458 SCIP_Real* bounds /**< bounds of the literals */ 3459 ) 3460 { 3461 assert(scip != NULL); 3462 3463 SCIP_CALL( SCIPcreateConsBounddisjunctionRedundant(scip, cons, name, nvars, vars, boundtypes, bounds, 3464 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 3465 3466 return SCIP_OKAY; 3467 } 3468 3469 /** gets number of variables in bound disjunction constraint */ /*lint -e{715}*/ 3470 int SCIPgetNVarsBounddisjunction( 3471 SCIP* scip, /**< SCIP data structure */ 3472 SCIP_CONS* cons /**< constraint data */ 3473 ) 3474 { 3475 SCIP_CONSDATA* consdata; 3476 3477 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 ) 3478 { 3479 SCIPerrorMessage("constraint is not a bound disjunction constraint\n"); 3480 SCIPABORT(); 3481 return 0; /*lint !e527*/ 3482 } 3483 3484 consdata = SCIPconsGetData(cons); 3485 assert(consdata != NULL); 3486 3487 return consdata->nvars; 3488 } 3489 3490 /** gets array of variables in bound disjunction constraint */ /*lint -e{715}*/ 3491 SCIP_VAR** SCIPgetVarsBounddisjunction( 3492 SCIP* scip, /**< SCIP data structure */ 3493 SCIP_CONS* cons /**< constraint data */ 3494 ) 3495 { 3496 SCIP_CONSDATA* consdata; 3497 3498 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 ) 3499 { 3500 SCIPerrorMessage("constraint is not a bound disjunction constraint\n"); 3501 SCIPABORT(); 3502 return NULL; /*lint !e527*/ 3503 } 3504 3505 consdata = SCIPconsGetData(cons); 3506 assert(consdata != NULL); 3507 3508 return consdata->vars; 3509 } 3510 3511 /** gets array of bound types in bound disjunction constraint */ /*lint -e{715}*/ 3512 SCIP_BOUNDTYPE* SCIPgetBoundtypesBounddisjunction( 3513 SCIP* scip, /**< SCIP data structure */ 3514 SCIP_CONS* cons /**< constraint data */ 3515 ) 3516 { 3517 SCIP_CONSDATA* consdata; 3518 3519 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 ) 3520 { 3521 SCIPerrorMessage("constraint is not a bound disjunction constraint\n"); 3522 SCIPABORT(); 3523 return NULL; /*lint !e527*/ 3524 } 3525 3526 consdata = SCIPconsGetData(cons); 3527 assert(consdata != NULL); 3528 3529 return consdata->boundtypes; 3530 } 3531 3532 /** gets array of bounds in bound disjunction constraint */ /*lint -e{715}*/ 3533 SCIP_Real* SCIPgetBoundsBounddisjunction( 3534 SCIP* scip, /**< SCIP data structure */ 3535 SCIP_CONS* cons /**< constraint data */ 3536 ) 3537 { 3538 SCIP_CONSDATA* consdata; 3539 3540 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 ) 3541 { 3542 SCIPerrorMessage("constraint is not a bound disjunction constraint\n"); 3543 SCIPABORT(); 3544 return NULL; /*lint !e527*/ 3545 } 3546 3547 consdata = SCIPconsGetData(cons); 3548 assert(consdata != NULL); 3549 3550 return consdata->bounds; 3551 } 3552