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