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