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