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_disjunction.c 26 * @ingroup DEFPLUGINS_CONS 27 * @brief constraint handler for disjunction constraints 28 * @author Stefan Heinz 29 * @author Michael Winkler 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_disjunction.h" 36 #include "scip/pub_cons.h" 37 #include "scip/pub_message.h" 38 #include "scip/pub_tree.h" 39 #include "scip/scip_branch.h" 40 #include "scip/scip_cons.h" 41 #include "scip/scip_copy.h" 42 #include "scip/scip_general.h" 43 #include "scip/scip_mem.h" 44 #include "scip/scip_message.h" 45 #include "scip/scip_param.h" 46 #include "scip/scip_prob.h" 47 #include "scip/scip_probing.h" 48 #include "scip/scip_sol.h" 49 #include "scip/scip_solvingstats.h" 50 #include "scip/scip_tree.h" 51 #include <string.h> 52 53 54 /* constraint handler properties */ 55 #define CONSHDLR_NAME "disjunction" 56 #define CONSHDLR_DESC "disjunction of constraints (or(cons1, cons2, ..., consn))" 57 #define CONSHDLR_ENFOPRIORITY -950000 /**< priority of the constraint handler for constraint enforcing */ 58 #define CONSHDLR_CHECKPRIORITY -900000 /**< priority of the constraint handler for checking feasibility */ 59 #define CONSHDLR_PROPFREQ -1 /**< frequency for propagating domains; zero means only preprocessing propagation */ 60 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation, 61 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */ 62 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in 63 * (-1: no limit) */ 64 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */ 65 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */ 66 67 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FAST 68 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP 69 70 71 #define DEFAULT_ALWAYSBRANCH TRUE /**< alawys perform branching if one of the constraints is violated, otherwise only if all integers are fixed */ 72 73 /* 74 * Data structures 75 */ 76 77 /** constraint data for disjunction constraints */ 78 struct SCIP_ConsData 79 { 80 SCIP_CONS** conss; /**< constraints in disjunction */ 81 SCIP_CONS* relaxcons; /**< a conjunction constraint containing the linear relaxation of the 82 * disjunction constraint, or NULL 83 */ 84 int consssize; /**< size of conss array */ 85 int nconss; /**< number of constraints in disjunction */ 86 }; 87 88 /** constraint handler data */ 89 struct SCIP_ConshdlrData 90 { 91 SCIP_Bool alwaysbranch; /**< alawys perform branching if one of the constraints is violated, otherwise only if all integers are fixed */ 92 }; 93 94 /* 95 * Local methods 96 */ 97 98 /** creates disjunction constraint data, captures initial constraints of disjunction */ 99 static 100 SCIP_RETCODE consdataCreate( 101 SCIP* scip, /**< SCIP data structure */ 102 SCIP_CONSDATA** consdata, /**< pointer to constraint data */ 103 SCIP_CONS** conss, /**< initial constraint in disjunction */ 104 int nconss, /**< number of initial constraints in disjunction */ 105 SCIP_CONS* relaxcons /**< a conjunction constraint containing the liner relaxation of the disjunction constraint, or NULL */ 106 ) 107 { 108 assert(scip != NULL); 109 assert(consdata != NULL); 110 111 SCIP_CALL( SCIPallocBlockMemory(scip, consdata) ); 112 if( nconss > 0 ) 113 { 114 assert(conss != NULL); 115 116 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->conss, conss, nconss) ); 117 118 (*consdata)->consssize = nconss; 119 (*consdata)->nconss = nconss; 120 (*consdata)->relaxcons = relaxcons; 121 122 /* we need to capture the constraints to avoid that SCIP deletes them since they are not (yet) added to the 123 * problem 124 */ 125 if( SCIPisTransformed(scip) ) 126 { 127 SCIP_CALL( SCIPtransformConss(scip, nconss, (*consdata)->conss, (*consdata)->conss) ); 128 129 if( (*consdata)->relaxcons != NULL ) 130 { 131 SCIP_CALL( SCIPtransformCons(scip, (*consdata)->relaxcons, &(*consdata)->relaxcons) ); 132 } 133 } 134 else 135 { 136 int c; 137 138 for( c = 0; c < nconss; ++c ) 139 { 140 assert(conss[c] != NULL); 141 SCIP_CALL( SCIPcaptureCons(scip, conss[c]) ); 142 } 143 144 if( (*consdata)->relaxcons != NULL ) 145 { 146 SCIP_CALL( SCIPcaptureCons(scip, (*consdata)->relaxcons) ); 147 } 148 } 149 } 150 else 151 { 152 (*consdata)->conss = NULL; 153 (*consdata)->consssize = 0; 154 (*consdata)->nconss = 0; 155 (*consdata)->relaxcons = NULL; 156 } 157 158 return SCIP_OKAY; 159 } 160 161 /** frees constraint data and releases all constraints in disjunction */ 162 static 163 SCIP_RETCODE consdataFree( 164 SCIP* scip, /**< SCIP data structure */ 165 SCIP_CONSDATA** consdata /**< pointer to constraint data */ 166 ) 167 { 168 int c; 169 170 assert(scip != NULL); 171 assert(consdata != NULL); 172 assert(*consdata != NULL); 173 174 /* release constraints */ 175 for( c = 0; c < (*consdata)->nconss; ++c ) 176 { 177 SCIP_CALL( SCIPreleaseCons(scip, &(*consdata)->conss[c]) ); 178 } 179 180 /* release relaxation constraint */ 181 if( (*consdata)->relaxcons != NULL ) 182 { 183 SCIP_CALL( SCIPreleaseCons(scip, &(*consdata)->relaxcons) ); 184 } 185 186 /* free memory */ 187 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->conss, (*consdata)->consssize); 188 SCIPfreeBlockMemory(scip, consdata); 189 190 return SCIP_OKAY; 191 } 192 193 /** adds constraint to disjunction */ 194 static 195 SCIP_RETCODE consdataAddCons( 196 SCIP* scip, /**< SCIP data structure */ 197 SCIP_CONSDATA* consdata, /**< constraint data */ 198 SCIP_CONS* cons /**< constraint to add to the disjunction */ 199 ) 200 { 201 assert(scip != NULL); 202 assert(consdata != NULL); 203 assert(cons != NULL); 204 205 /* get memory for additional constraint */ 206 SCIP_CALL( SCIPensureBlockMemoryArray(scip, &consdata->conss, &consdata->consssize, consdata->nconss+1) ); 207 assert(consdata->conss != NULL); 208 assert(consdata->nconss < consdata->consssize); 209 210 /* insert constraint in array */ 211 consdata->conss[consdata->nconss] = cons; 212 consdata->nconss++; 213 214 if( SCIPisTransformed(scip) ) 215 { 216 SCIP_CALL( SCIPtransformCons(scip, consdata->conss[consdata->nconss - 1], &(consdata->conss[consdata->nconss - 1]))); 217 } 218 else 219 { 220 /* capture constraint */ 221 SCIP_CALL( SCIPcaptureCons(scip, cons) ); 222 } 223 224 return SCIP_OKAY; 225 } 226 227 /** branches on disjunctive constraint */ 228 static 229 SCIP_RETCODE branchCons( 230 SCIP* scip, /**< SCIP data structure */ 231 SCIP_CONS* cons, /**< active disjunction constraint */ 232 SCIP_RESULT* result /**< pointer to store the result */ 233 ) 234 { 235 SCIP_CONSDATA* consdata; 236 SCIP_CONS** conss; 237 SCIP_NODE* child; 238 SCIP_Real estimate; 239 int nconss; 240 int i; 241 242 assert(result != NULL); 243 244 /* cannot branch on modifiable constraint */ 245 if( SCIPconsIsModifiable(cons) ) 246 return SCIP_OKAY; 247 248 consdata = SCIPconsGetData(cons); 249 assert(consdata != NULL); 250 251 conss = consdata->conss; 252 assert(conss != NULL); 253 254 nconss = consdata->nconss; 255 assert(nconss > 0); 256 257 estimate = SCIPgetLocalTransEstimate(scip); 258 259 /* add all inactive constraints to local subproblem */ 260 for( i = 0; i < nconss; ++i ) 261 { 262 /* create the branch-and-bound tree child nodes of the current node */ 263 SCIP_CALL( SCIPcreateChild(scip, &child, 0.0, estimate) ); 264 265 /* if disjunctive constraint needs to be checked, the upgraded constraint also needs to be checked */ 266 if( SCIPconsIsChecked(cons) ) 267 { 268 SCIP_CALL( SCIPsetConsChecked(scip, conss[i], TRUE) ); 269 } 270 271 /* mark constraint to be local; otherwise during INITLP the (global) row of all constraints of the disjunction 272 * constrtaint will enter the LP 273 */ 274 SCIP_CALL( SCIPsetConsLocal(scip, conss[i], TRUE) ); 275 276 /* add constraints to nodes */ 277 SCIP_CALL( SCIPaddConsNode(scip, child, conss[i], NULL) ); 278 SCIPdebugMsg(scip, "add cons %s to node %lld from %lld\n", SCIPconsGetName(conss[i]), SCIPnodeGetNumber(child), 279 SCIPnodeGetNumber(SCIPgetCurrentNode(scip))); 280 281 /* remove disjunction constraint, from child node */ 282 SCIP_CALL( SCIPdelConsNode(scip, child, cons) ); 283 } 284 285 SCIPdebugMsg(scip, "disjunction constraint <%s> branched %d childs\n", SCIPconsGetName(cons), nconss); 286 287 /* reset constraint age */ 288 SCIP_CALL( SCIPresetConsAge(scip, cons) ); 289 290 *result = SCIP_BRANCHED; 291 292 return SCIP_OKAY; 293 } 294 295 /** checks disjunction constraints if at least one is feasible */ 296 static 297 SCIP_RETCODE checkCons( 298 SCIP* scip, /**< SCIP data structure */ 299 SCIP_CONS* cons, /**< active disjunction constraint */ 300 SCIP_SOL* sol, /**< solution to check */ 301 SCIP_Bool checkintegrality, /**< Has integrality to be checked? */ 302 SCIP_Bool checklprows, /**< Do constraints represented by rows in the current LP have to be checked? */ 303 SCIP_Bool printreason, /**< Should the reason for the violation be printed? */ 304 SCIP_RESULT* result /**< pointer to store the result */ 305 ) 306 { 307 SCIP_CONSDATA* consdata; 308 SCIP_CONS** conss; 309 int nconss; 310 int i; 311 312 assert(result != NULL); 313 314 consdata = SCIPconsGetData(cons); 315 assert(consdata != NULL); 316 317 conss = consdata->conss; 318 assert(conss != NULL); 319 320 nconss = consdata->nconss; 321 assert(nconss > 0); 322 323 *result = SCIP_INFEASIBLE; 324 325 SCIPdeactivateSolViolationUpdates(scip); 326 327 /* check all constraints */ 328 for( i = 0; i < nconss && *result != SCIP_FEASIBLE; ++i ) 329 { 330 SCIP_CALL( SCIPcheckCons(scip, conss[i], sol, checkintegrality, checklprows, FALSE, result) ); 331 assert(*result == SCIP_FEASIBLE || *result == SCIP_INFEASIBLE); 332 } 333 334 SCIPactivateSolViolationUpdates(scip); 335 336 if( *result == SCIP_INFEASIBLE ) 337 { 338 if( sol != NULL ) 339 SCIPupdateSolConsViolation(scip, sol, 1.0, 1.0); 340 341 if( printreason ) 342 { 343 SCIPinfoMessage(scip, NULL, "constraint %s is violated, all sub-constraints in this disjunction are violated by this given solution\n", SCIPconsGetName(cons)); 344 SCIPdebug( SCIP_CALL( SCIPprintCons(scip, cons, NULL) ) ); 345 } 346 } 347 348 return SCIP_OKAY; 349 } 350 351 /** propagation method for disjunction constraint */ 352 static 353 SCIP_RETCODE propagateCons( 354 SCIP* scip, /**< SCIP data structure */ 355 SCIP_CONS* cons, /**< disjunctive constraint */ 356 int* ndelconss /**< pointer to count number of deleted constraints */ 357 ) 358 { 359 SCIP_CONSDATA* consdata; 360 SCIP_CONS** conss; 361 int nconss; 362 int c; 363 364 assert(scip != NULL); 365 assert(cons != NULL); 366 assert(ndelconss != NULL); 367 368 consdata = SCIPconsGetData(cons); 369 assert(consdata != NULL); 370 371 conss = consdata->conss; 372 assert(conss != NULL); 373 374 nconss = consdata->nconss; 375 assert(nconss >= 1); 376 377 for( c = 0; c < nconss; ++c ) 378 { 379 /* if a constraint of the disjunction is already active, the disjunction is enforce by this constraint and 380 * therefore redundant and can be locally deleted 381 */ 382 if( SCIPconsIsActive(conss[c]) ) 383 { 384 /* if we can globally delete the whole disjunctive constraint, because one constraint is already active, we 385 * might need to update the check stage 386 */ 387 if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING || SCIPgetNNodes(scip) == 0 ) 388 { 389 /* if disjunctive constraint needs to be checked, the upgraded constraint also needs to be checked */ 390 if( SCIPconsIsChecked(cons) ) 391 { 392 SCIP_CALL( SCIPsetConsChecked(scip, conss[c], TRUE) ); 393 } 394 } 395 396 (*ndelconss)++; 397 SCIP_CALL( SCIPdelConsLocal(scip, cons) ); 398 break; 399 } 400 /* if a sub-constraint is globally deleted, it means that this constraint is redundant and always fulfilled and 401 * this makes also this disjunction redundant 402 */ 403 else if( SCIPconsIsDeleted(conss[c]) ) 404 { 405 (*ndelconss)++; 406 SCIP_CALL( SCIPdelCons(scip, cons) ); 407 break; 408 } 409 } 410 411 return SCIP_OKAY; 412 } 413 414 /** helper function to enforce constraints */ 415 static 416 SCIP_RETCODE enforceConstraint( 417 SCIP* scip, /**< SCIP data structure */ 418 SCIP_CONSHDLR* conshdlr, /**< constraint handler */ 419 SCIP_CONS** conss, /**< constraints to process */ 420 int nconss, /**< number of constraints */ 421 SCIP_SOL* sol, /**< solution to enforce (NULL for LP solution) */ 422 SCIP_RESULT* result /**< pointer to store the result of the enforcing call */ 423 ) 424 { 425 SCIP_CONSHDLRDATA* conshdlrdata; 426 SCIP_Bool branch; 427 int c; 428 429 *result = SCIP_FEASIBLE; 430 431 conshdlrdata = SCIPconshdlrGetData(conshdlr); 432 assert(conshdlrdata != NULL); 433 434 branch = SCIPgetNPseudoBranchCands(scip) == 0 || conshdlrdata->alwaysbranch; 435 436 for( c = 0; c < nconss && *result != SCIP_BRANCHED; ++c ) 437 { 438 /* check the disjunction */ 439 SCIP_CALL( checkCons(scip, conss[c], sol, FALSE, FALSE, FALSE, result) ); 440 441 if( *result == SCIP_INFEASIBLE && branch ) 442 { 443 SCIP_CALL( branchCons(scip, conss[c], result) ); 444 } 445 } 446 447 return SCIP_OKAY; 448 } 449 450 /* 451 * Callback methods of constraint handler 452 */ 453 454 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 455 static 456 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyDisjunction) 457 { /*lint --e{715}*/ 458 assert(scip != NULL); 459 assert(conshdlr != NULL); 460 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 461 462 /* call inclusion method of constraint handler */ 463 SCIP_CALL( SCIPincludeConshdlrDisjunction(scip) ); 464 465 *valid = TRUE; 466 467 return SCIP_OKAY; 468 } 469 470 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */ 471 static 472 SCIP_DECL_CONSFREE(consFreeDisjunction) 473 { 474 SCIP_CONSHDLRDATA* conshdlrdata; 475 476 assert(scip != NULL); 477 assert(conshdlr != NULL); 478 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 479 480 /* free constraint handler data */ 481 conshdlrdata = SCIPconshdlrGetData(conshdlr); 482 assert(conshdlrdata != NULL); 483 484 SCIPfreeBlockMemory(scip, &conshdlrdata); 485 486 SCIPconshdlrSetData(conshdlr, NULL); 487 488 return SCIP_OKAY; 489 } 490 491 /** frees specific constraint data */ 492 static 493 SCIP_DECL_CONSDELETE(consDeleteDisjunction) 494 { /*lint --e{715}*/ 495 SCIP_CALL( consdataFree(scip, consdata) ); 496 497 return SCIP_OKAY; 498 } 499 500 501 /** transforms constraint data into data belonging to the transformed problem */ 502 static 503 SCIP_DECL_CONSTRANS(consTransDisjunction) 504 { /*lint --e{715}*/ 505 SCIP_CONSDATA* sourcedata; 506 SCIP_CONSDATA* targetdata; 507 508 /* get constraint data of source constraint */ 509 sourcedata = SCIPconsGetData(sourcecons); 510 assert(sourcedata != NULL); 511 512 SCIP_CALL( consdataCreate(scip, &targetdata, sourcedata->conss, sourcedata->nconss, sourcedata->relaxcons) ); 513 514 /* create target constraint */ 515 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata, 516 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons), 517 SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons), 518 SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons), 519 SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) ); 520 521 return SCIP_OKAY; 522 } 523 524 /** LP initialization method of constraint handler */ 525 static 526 SCIP_DECL_CONSINITLP(consInitlpDisjunction) 527 { /*lint --e{715}*/ 528 SCIP_CONSDATA* consdata; 529 int c; 530 531 *infeasible = FALSE; 532 533 for( c = 0; c < nconss; ++c ) 534 { 535 consdata = SCIPconsGetData(conss[c]); 536 assert(consdata != NULL); 537 538 /* if we have a relaxation constraint and it is not active, then we add it locally */ 539 if( consdata->relaxcons != NULL && !SCIPconsIsActive(consdata->relaxcons) ) 540 { 541 SCIP_CALL( SCIPaddConsLocal(scip, consdata->relaxcons, NULL) ); 542 } 543 } 544 545 return SCIP_OKAY; 546 } 547 548 549 /** constraint enforcing method of constraint handler for LP solutions */ 550 static 551 SCIP_DECL_CONSENFOLP(consEnfolpDisjunction) 552 { /*lint --e{715}*/ 553 SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, NULL, result) ); 554 555 return SCIP_OKAY; 556 } 557 558 559 /** constraint enforcing method of constraint handler for relaxation solutions */ 560 static 561 SCIP_DECL_CONSENFORELAX(consEnforelaxDisjunction) 562 { /*lint --e{715}*/ 563 SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, sol, result) ); 564 565 return SCIP_OKAY; 566 } 567 568 569 /** constraint enforcing method of constraint handler for pseudo solutions */ 570 static 571 SCIP_DECL_CONSENFOPS(consEnfopsDisjunction) 572 { /*lint --e{715}*/ 573 SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, NULL, result) ); 574 575 return SCIP_OKAY; 576 } 577 578 579 /** feasibility check method of constraint handler for integral solutions */ 580 static 581 SCIP_DECL_CONSCHECK(consCheckDisjunction) 582 { /*lint --e{715}*/ 583 int c; 584 585 *result = SCIP_FEASIBLE; 586 587 for( c = 0; c < nconss && (*result == SCIP_FEASIBLE || completely); ++c ) 588 { 589 SCIP_RESULT tmpres; 590 591 /* check the disjunction */ 592 SCIP_CALL( checkCons(scip, conss[c], sol, checkintegrality, checklprows, printreason, &tmpres) ); 593 assert(tmpres == SCIP_FEASIBLE || tmpres == SCIP_INFEASIBLE); 594 595 if( tmpres == SCIP_INFEASIBLE ) 596 *result = SCIP_INFEASIBLE; 597 } 598 599 return SCIP_OKAY; 600 } 601 602 603 /** domain propagation method of constraint handler */ 604 static 605 SCIP_DECL_CONSPROP(consPropDisjunction) 606 { /*lint --e{715}*/ 607 int ndelconss; 608 int c; 609 610 ndelconss = 0; 611 612 /* in probing mode we do not for deletable constraints */ 613 if( !SCIPinProbing(scip) ) 614 { 615 for( c = 0; c < nconss; ++c ) 616 { 617 /* propagate constraint */ 618 SCIP_CALL( propagateCons(scip, conss[c], &ndelconss) ); 619 } 620 } 621 622 /* adjust result code */ 623 if( ndelconss > 0 ) 624 *result = SCIP_REDUCEDDOM; 625 else 626 *result = SCIP_DIDNOTFIND; 627 628 return SCIP_OKAY; 629 } 630 631 632 /** presolving method of constraint handler */ 633 static 634 SCIP_DECL_CONSPRESOL(consPresolDisjunction) 635 { /*lint --e{715}*/ 636 SCIP_CONSDATA* consdata; 637 int oldndelconss; 638 int c; 639 640 assert(result != NULL); 641 642 *result = SCIP_DIDNOTFIND; 643 oldndelconss = *ndelconss; 644 645 /* all disjunction constraints with one constraint can be replaced with that corresponding constraint */ 646 for( c = 0; c < nconss; ++c ) 647 { 648 consdata = SCIPconsGetData(conss[c]); 649 assert(consdata != NULL); 650 651 if( !SCIPconsIsModifiable(conss[c]) && consdata->nconss == 1 ) 652 { 653 /* add constraint to the problem */ 654 if( !SCIPconsIsActive(consdata->conss[0]) ) 655 { 656 SCIP_CONS* subcons = consdata->conss[0]; 657 658 /* if disjunctive constraint needs to be checked, the upgraded constraint also needs to be checked */ 659 if( SCIPconsIsChecked(conss[c]) ) 660 { 661 SCIP_CALL( SCIPsetConsChecked(scip, subcons, TRUE) ); 662 } 663 664 SCIP_CALL( SCIPaddCons(scip, subcons) ); 665 } 666 667 /* remove disjunction constraint */ 668 SCIP_CALL( SCIPdelCons(scip, conss[c]) ); 669 670 *result = SCIP_SUCCESS; 671 672 continue; 673 } 674 675 /* propagate constraint */ 676 SCIP_CALL( propagateCons(scip, conss[c], ndelconss) ); 677 } 678 679 if( *ndelconss > oldndelconss ) 680 *result = SCIP_SUCCESS; 681 682 return SCIP_OKAY; 683 } 684 685 686 /** variable rounding lock method of constraint handler */ 687 static 688 SCIP_DECL_CONSLOCK(consLockDisjunction) 689 { /*lint --e{715}*/ 690 SCIP_CONSDATA* consdata; 691 int c; 692 693 assert(locktype == SCIP_LOCKTYPE_MODEL); 694 695 consdata = SCIPconsGetData(cons); 696 assert(consdata != NULL); 697 698 /* lock sub constraints */ 699 for( c = 0; c < consdata->nconss; ++c ) 700 { 701 SCIP_CALL( SCIPaddConsLocksType(scip, consdata->conss[c], locktype, nlockspos, nlocksneg) ); 702 } 703 704 return SCIP_OKAY; 705 } 706 707 708 /** constraint display method of constraint handler */ 709 static 710 SCIP_DECL_CONSPRINT(consPrintDisjunction) 711 { /*lint --e{715}*/ 712 SCIP_CONSDATA* consdata; 713 int i; 714 715 assert(scip != NULL); 716 assert(conshdlr != NULL); 717 assert(cons != NULL); 718 719 consdata = SCIPconsGetData(cons); 720 assert(consdata != NULL); 721 722 SCIPinfoMessage(scip, file, "disjunction("); 723 724 for( i = 0; i < consdata->nconss; ++i ) 725 { 726 if( i > 0 ) 727 SCIPinfoMessage(scip, file, ", "); 728 SCIP_CALL( SCIPprintCons(scip, consdata->conss[i], file) ); 729 } 730 731 /* print relaxation */ 732 if( consdata->relaxcons != NULL ) 733 { 734 SCIPinfoMessage(scip, file, ",, "); 735 SCIP_CALL( SCIPprintCons(scip, consdata->relaxcons, file) ); 736 } 737 738 SCIPinfoMessage(scip, file, ")"); 739 740 return SCIP_OKAY; 741 } 742 743 /** constraint parsing method of constraint handler */ 744 static 745 SCIP_DECL_CONSPARSE(consParseDisjunction) 746 { /*lint --e{715}*/ 747 SCIP_CONS** conss; 748 SCIP_Bool relaxed = FALSE; 749 int nconss; 750 int sconss; 751 char* token; 752 char* saveptr; 753 char* nexttokenstart; 754 char* copystr; 755 756 assert(scip != NULL); 757 assert(conshdlr != NULL); 758 assert(cons != NULL); 759 assert(success != NULL); 760 assert(str != NULL); 761 assert(name != NULL); 762 763 SCIPdebugMsg(scip, "parsing disjunction <%s>\n", name); 764 765 *success = TRUE; 766 767 /* allocate memory for constraint in disjunction, initial size is set to 10 */ 768 nconss = 0; 769 sconss = 10; 770 SCIP_CALL( SCIPallocBufferArray(scip, &conss, sconss) ); 771 SCIP_CALL( SCIPduplicateBufferArray(scip, ©str, str, (int)strlen(str)+1) ); 772 773 /* find '(' at the beginning, string should start with 'disjunction(' */ 774 saveptr = strpbrk(copystr, "("); /*lint !e158*/ 775 776 if( saveptr == NULL ) 777 { 778 SCIPdebugMsg(scip, "error parsing disjunctive constraint: \"%s\"\n", str); 779 *success = FALSE; 780 goto TERMINATE; 781 } 782 assert(saveptr != NULL); /* for lint */ 783 784 /* skip '(' */ 785 ++saveptr; 786 /* remember token start position */ 787 nexttokenstart = saveptr; 788 789 /* brackets '(' and ')' can exist co we check for them and the constraint delimeter */ 790 saveptr = strpbrk(saveptr, "(,"); 791 792 /* brackets '(' and ')' can exist in the rest of the string so we need to skip them to find the end of the first 793 * sub-constraint marked by a ',' 794 */ 795 if( saveptr != NULL ) 796 { 797 do 798 { 799 int bracketcounter = 0; 800 801 if( *saveptr == '(' ) 802 { 803 do 804 { 805 ++bracketcounter; 806 ++saveptr; 807 808 /* find last ending bracket */ 809 while( bracketcounter > 0 ) 810 { 811 saveptr = strpbrk(saveptr, "()"); 812 813 if( saveptr != NULL ) 814 { 815 if( *saveptr == '(' ) 816 ++bracketcounter; 817 else 818 --bracketcounter; 819 820 ++saveptr; 821 } 822 else 823 { 824 SCIPdebugMsg(scip, "error parsing disjunctive constraint: \"%s\"\n", str); 825 *success = FALSE; 826 goto TERMINATE; 827 } 828 } 829 830 saveptr = strpbrk(saveptr, "(,"); 831 } 832 while( saveptr != NULL && *saveptr == '(' ); 833 } 834 835 /* we found a ',' so the end of the first sub-constraint is determined */ 836 if( saveptr != NULL ) 837 { 838 assert(*saveptr == ','); 839 840 /* resize constraint array if necessary */ 841 if( nconss == sconss ) 842 { 843 sconss = SCIPcalcMemGrowSize(scip, nconss+1); 844 assert(nconss < sconss); 845 846 SCIP_CALL( SCIPreallocBufferArray(scip, &conss, sconss) ); 847 } 848 849 assert(saveptr > nexttokenstart); 850 851 /* extract token for parsing */ 852 SCIP_CALL( SCIPduplicateBufferArray(scip, &token, nexttokenstart, saveptr - nexttokenstart + 1) ); 853 token[saveptr - nexttokenstart] = '\0'; 854 855 SCIPdebugMsg(scip, "disjunctive parsing token(constraint): %s\n", token); 856 857 /* parsing a constraint, part of the disjunction */ 858 SCIP_CALL( SCIPparseCons(scip, &(conss[nconss]), token, initial, separate, enforce, FALSE, propagate, TRUE, modifiable, dynamic, removable, stickingatnode, success) ); 859 860 SCIPfreeBufferArray(scip, &token); 861 862 if( *success ) 863 ++nconss; 864 else 865 { 866 SCIPdebugMsg(scip, "error parsing disjunctive constraint: \"%s\"\n", str); 867 goto TERMINATE; 868 } 869 /* skip ',' delimeter */ 870 ++saveptr; 871 /* remember token start position */ 872 nexttokenstart = saveptr; 873 874 /* check if we found the last constraint, which is a conjunctive relaxation of the disjunction, and in the 875 * CIP format marked by two consecutive ',' 876 */ 877 if( *nexttokenstart == ',' ) 878 { 879 /* remember token start position */ 880 nexttokenstart = saveptr+1; 881 882 relaxed = TRUE; 883 break; 884 } 885 886 saveptr = strpbrk(saveptr, "(,"); 887 } 888 } 889 while( saveptr != NULL ); 890 } 891 892 /* find end of disjunction constraint */ 893 saveptr = strrchr(nexttokenstart, ')'); 894 895 if( saveptr == NULL ) 896 { 897 SCIPdebugMsg(scip, "error parsing disjunctive constraint: \"%s\"\n", str); 898 *success = FALSE; 899 goto TERMINATE; 900 } 901 /* parse last sub-constraint */ 902 else 903 { 904 /* resize constraint array if necessary */ 905 if( nconss == sconss ) 906 { 907 ++sconss; 908 SCIP_CALL( SCIPreallocBufferArray(scip, &conss, sconss) ); 909 } 910 911 assert(saveptr > nexttokenstart); 912 913 /* extract token for parsing */ 914 SCIP_CALL( SCIPduplicateBufferArray(scip, &token, nexttokenstart, saveptr - nexttokenstart + 1) ); 915 token[saveptr - nexttokenstart] = '\0'; 916 917 SCIPdebugMsg(scip, "disjunctive parsing token(constraint): %s\n", token); 918 919 /* parsing a constraint, part of the disjunction */ 920 SCIP_CALL( SCIPparseCons(scip, &(conss[nconss]), token, initial, separate, enforce, FALSE, propagate, TRUE, modifiable, dynamic, removable, stickingatnode, success) ); 921 922 if( *success ) 923 ++nconss; 924 925 SCIPfreeBufferArray(scip, &token); 926 } 927 assert(nconss > 0 || !(*success)); 928 929 /* if parsing sub-constraints was fine, create the disjunctive constraint */ 930 if( *success ) 931 { 932 /* create disjunctive constraint */ 933 SCIP_CALL( SCIPcreateConsDisjunction(scip, cons, name, relaxed ? nconss - 1: nconss, conss, relaxed ? conss[nconss - 1] : NULL, 934 initial, enforce, check, local, modifiable, dynamic) ); 935 } 936 937 /* free parsed constraints */ 938 for( --nconss; nconss >= 0; --nconss ) 939 { 940 SCIP_CALL( SCIPreleaseCons(scip, &conss[nconss]) ); 941 } 942 943 TERMINATE: 944 /* free temporary memory */ 945 SCIPfreeBufferArray(scip, ©str); 946 SCIPfreeBufferArray(scip, &conss); 947 948 return SCIP_OKAY; 949 } 950 951 952 /** constraint copying method of constraint handler */ 953 static 954 SCIP_DECL_CONSCOPY(consCopyDisjunction) 955 { /*lint --e{715}*/ 956 SCIP_CONSDATA* sourcedata; 957 SCIP_CONS** sourceconss; 958 SCIP_CONS** conss; 959 int nconss; 960 int c; 961 962 *valid = TRUE; 963 964 sourcedata = SCIPconsGetData(sourcecons); 965 assert(sourcedata != NULL); 966 967 nconss = sourcedata->nconss; 968 969 SCIP_CALL( SCIPallocBufferArray(scip, &conss, nconss) ); 970 sourceconss = sourcedata->conss; 971 972 /* copy each constraint one by one */ 973 for( c = 0; c < nconss && (*valid); ++c ) 974 { 975 SCIP_CALL( SCIPgetConsCopy(sourcescip, scip, sourceconss[c], &conss[c], SCIPconsGetHdlr(sourceconss[c]), 976 varmap, consmap, SCIPconsGetName(sourceconss[c]), 977 SCIPconsIsInitial(sourceconss[c]), SCIPconsIsSeparated(sourceconss[c]), SCIPconsIsEnforced(sourceconss[c]), 978 SCIPconsIsChecked(sourceconss[c]), SCIPconsIsPropagated(sourceconss[c]), 979 SCIPconsIsLocal(sourceconss[c]), SCIPconsIsModifiable(sourceconss[c]), 980 SCIPconsIsDynamic(sourceconss[c]), SCIPconsIsRemovable(sourceconss[c]), SCIPconsIsStickingAtNode(sourceconss[c]), 981 global, valid) ); 982 assert(!(*valid) || conss[c] != NULL); 983 } 984 985 if( *valid ) 986 { 987 SCIP_CONS* sourcerelaxcons; 988 SCIP_CONS* targetrelaxcons; 989 990 sourcerelaxcons = sourcedata->relaxcons; 991 targetrelaxcons = NULL; 992 993 if( sourcerelaxcons != NULL ) 994 { 995 SCIP_CALL( SCIPgetConsCopy(sourcescip, scip, sourcerelaxcons, &targetrelaxcons, SCIPconsGetHdlr(sourcerelaxcons), 996 varmap, consmap, SCIPconsGetName(sourcerelaxcons), 997 SCIPconsIsInitial(sourcerelaxcons), SCIPconsIsSeparated(sourcerelaxcons), SCIPconsIsEnforced(sourcerelaxcons), 998 SCIPconsIsChecked(sourcerelaxcons), SCIPconsIsPropagated(sourcerelaxcons), 999 SCIPconsIsLocal(sourcerelaxcons), SCIPconsIsModifiable(sourcerelaxcons), 1000 SCIPconsIsDynamic(sourcerelaxcons), SCIPconsIsRemovable(sourcerelaxcons), 1001 SCIPconsIsStickingAtNode(sourcerelaxcons), 1002 global, valid) ); 1003 } 1004 1005 if( *valid ) 1006 { 1007 if( name == NULL ) 1008 { 1009 SCIP_CALL( SCIPcreateConsDisjunction(scip, cons, SCIPconsGetName(sourcecons), nconss, conss, targetrelaxcons, 1010 initial, enforce, check, local, modifiable, dynamic) ); 1011 } 1012 else 1013 { 1014 SCIP_CALL( SCIPcreateConsDisjunction(scip, cons, name, nconss, conss, targetrelaxcons, 1015 initial, enforce, check, local, modifiable, dynamic) ); 1016 } 1017 1018 if( targetrelaxcons != NULL ) 1019 { 1020 SCIP_CALL( SCIPreleaseCons(scip, &targetrelaxcons) ); 1021 } 1022 } 1023 } 1024 1025 /* release the copied constraints */ 1026 for( c = (*valid ? c - 1 : c - 2); c >= 0; --c ) 1027 { 1028 assert(conss[c] != NULL); 1029 SCIP_CALL( SCIPreleaseCons(scip, &conss[c]) ); 1030 } 1031 1032 SCIPfreeBufferArray(scip, &conss); 1033 1034 return SCIP_OKAY; 1035 } 1036 1037 1038 /* 1039 * constraint specific interface methods 1040 */ 1041 1042 /** creates the handler for disjunction constraints and includes it in SCIP */ 1043 SCIP_RETCODE SCIPincludeConshdlrDisjunction( 1044 SCIP* scip /**< SCIP data structure */ 1045 ) 1046 { 1047 SCIP_CONSHDLRDATA* conshdlrdata; 1048 SCIP_CONSHDLR* conshdlr; 1049 1050 /* create disjunction constraint handler data */ 1051 SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) ); 1052 1053 /* include constraint handler */ 1054 SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC, 1055 CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS, 1056 consEnfolpDisjunction, consEnfopsDisjunction, consCheckDisjunction, consLockDisjunction, 1057 conshdlrdata) ); 1058 1059 assert(conshdlr != NULL); 1060 1061 /* set non-fundamental callbacks via specific setter functions */ 1062 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyDisjunction, consCopyDisjunction) ); 1063 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeDisjunction) ); 1064 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteDisjunction) ); 1065 SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpDisjunction) ); 1066 SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseDisjunction) ); 1067 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolDisjunction, CONSHDLR_MAXPREROUNDS, 1068 CONSHDLR_PRESOLTIMING) ); 1069 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintDisjunction) ); 1070 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropDisjunction, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, 1071 CONSHDLR_PROP_TIMING) ); 1072 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransDisjunction) ); 1073 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxDisjunction) ); 1074 1075 SCIP_CALL( SCIPaddBoolParam(scip, 1076 "constraints/" CONSHDLR_NAME "/alwaysbranch", 1077 "alawys perform branching if one of the constraints is violated, otherwise only if all integers are fixed", 1078 &conshdlrdata->alwaysbranch, FALSE, DEFAULT_ALWAYSBRANCH, NULL, NULL) ); 1079 1080 return SCIP_OKAY; 1081 } 1082 1083 /** creates and captures a disjunction constraint 1084 * 1085 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 1086 */ 1087 SCIP_RETCODE SCIPcreateConsDisjunction( 1088 SCIP* scip, /**< SCIP data structure */ 1089 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 1090 const char* name, /**< name of constraint */ 1091 int nconss, /**< number of initial constraints in disjunction */ 1092 SCIP_CONS** conss, /**< initial constraint in disjunction */ 1093 SCIP_CONS* relaxcons, /**< a conjunction constraint containing the linear relaxation of the disjunction constraint, or NULL */ 1094 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? 1095 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */ 1096 SCIP_Bool enforce, /**< should the constraint be enforced during node processing? 1097 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 1098 SCIP_Bool check, /**< should the constraint be checked for feasibility? 1099 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 1100 SCIP_Bool local, /**< is constraint only valid locally? 1101 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */ 1102 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? 1103 * Usually set to FALSE. In column generation applications, set to TRUE if pricing 1104 * adds coefficients to this constraint. */ 1105 SCIP_Bool dynamic /**< is constraint subject to aging? 1106 * Usually set to FALSE. Set to TRUE for own cuts which 1107 * are separated as constraints. */ 1108 ) 1109 { 1110 SCIP_CONSHDLR* conshdlr; 1111 SCIP_CONSDATA* consdata; 1112 1113 /* find the disjunction constraint handler */ 1114 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME); 1115 if( conshdlr == NULL ) 1116 { 1117 SCIPerrorMessage("disjunction constraint handler not found\n"); 1118 return SCIP_PLUGINNOTFOUND; 1119 } 1120 1121 /* create constraint data */ 1122 SCIP_CALL( consdataCreate(scip, &consdata, conss, nconss, relaxcons) ); 1123 1124 /* create constraint */ 1125 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, FALSE, enforce, check, FALSE, 1126 local, modifiable, dynamic, FALSE, FALSE) ); 1127 1128 return SCIP_OKAY; 1129 } 1130 1131 /** creates and captures a cumulative constraint 1132 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the 1133 * method SCIPcreateConsDisjunction(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h 1134 * 1135 * @see SCIPcreateConsDisjunction() for information about the basic constraint flag configuration 1136 * 1137 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 1138 */ 1139 SCIP_RETCODE SCIPcreateConsBasicDisjunction( 1140 SCIP* scip, /**< SCIP data structure */ 1141 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 1142 const char* name, /**< name of constraint */ 1143 int nconss, /**< number of initial constraints in disjunction */ 1144 SCIP_CONS** conss, /**< initial constraint in disjunction */ 1145 SCIP_CONS* relaxcons /**< a conjunction constraint containing the linear relaxation of the disjunction constraint, or NULL */ 1146 ) 1147 { 1148 assert(scip != NULL); 1149 1150 SCIP_CALL( SCIPcreateConsDisjunction(scip, cons, name, nconss, conss, relaxcons, 1151 TRUE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 1152 1153 return SCIP_OKAY; 1154 } 1155 1156 1157 /** adds constraint to the disjunction of constraints */ 1158 SCIP_RETCODE SCIPaddConsElemDisjunction( 1159 SCIP* scip, /**< SCIP data structure */ 1160 SCIP_CONS* cons, /**< disjunction constraint */ 1161 SCIP_CONS* addcons /**< additional constraint in disjunction */ 1162 ) 1163 { 1164 SCIP_CONSDATA* consdata; 1165 1166 assert(cons != NULL); 1167 assert(addcons != NULL); 1168 1169 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 ) 1170 { 1171 SCIPerrorMessage("constraint is not a disjunction constraint\n"); 1172 return SCIP_INVALIDDATA; 1173 } 1174 1175 consdata = SCIPconsGetData(cons); 1176 assert(consdata != NULL); 1177 1178 SCIP_CALL( consdataAddCons(scip, consdata, addcons) ); 1179 1180 return SCIP_OKAY; 1181 } 1182 1183