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_symresack.c 26 * @ingroup DEFPLUGINS_CONS 27 * @brief constraint handler for symresack constraints 28 * @author Christopher Hojny 29 * @author Jasper van Doornmalen 30 * 31 * The type of constraints of this constraint handler is described in cons_symresack.h. 32 * 33 * The details of the method implemented here are described in the following papers: 34 * 35 * Fundamental Domains for Integer Programs with Symmetries@n 36 * Eric J. Friedman,@n 37 * Combinatorial Optimization, volume 4616 of LNCS, 146-153 (2007) 38 * 39 * This paper describes an inequality to handle symmetries of a single permutation. This 40 * so-called FD-inequality is the basic for the propagation routine of our implementation. 41 * 42 * Polytopes Associated with Symmetry Handling@n 43 * Christopher Hojny and Marc E. Pfetsch,@n 44 * Mathematical Programming 175, No. 1, 197-240, 2019 45 * 46 * This paper describes an almost linear time separation routine for so-called cover 47 * inequalities of symresacks. A slight modification of this algorithm allows for a linear 48 * running time, which is used in this implementation. 49 * 50 * Packing, Partitioning, and Covering Symresacks@n 51 * Christopher Hojny,@n 52 * (2020), available at https://doi.org/10.1016/j.dam.2020.03.002 53 * Discrete Applied Mathematics, volume 283, 689-717 (2020) 54 * 55 * This paper introduces linearly many inequalities with ternary coefficients that suffice to 56 * characterize the binary points contained in a packing and partitioning symresack completely. 57 */ 58 59 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 60 61 #include "blockmemshell/memory.h" 62 #include "scip/cons_orbisack.h" 63 #include "scip/cons_setppc.h" 64 #include "scip/cons_symresack.h" 65 #include "scip/pub_cons.h" 66 #include "scip/pub_message.h" 67 #include "scip/pub_misc.h" 68 #include "scip/pub_var.h" 69 #include "scip/scip.h" 70 #include "scip/scip_branch.h" 71 #include "scip/scip_conflict.h" 72 #include "scip/scip_cons.h" 73 #include "scip/scip_cut.h" 74 #include "scip/scip_general.h" 75 #include "scip/scip_lp.h" 76 #include "scip/scip_mem.h" 77 #include "scip/scip_message.h" 78 #include "scip/scip_numerics.h" 79 #include "scip/scip_param.h" 80 #include "scip/scip_prob.h" 81 #include "scip/scip_sol.h" 82 #include "scip/scip_var.h" 83 84 85 /* constraint handler properties */ 86 #define CONSHDLR_NAME "symresack" 87 #define CONSHDLR_DESC "symmetry breaking constraint handler relying on symresacks" 88 #define CONSHDLR_SEPAPRIORITY +40100 /**< priority of the constraint handler for separation */ 89 #define CONSHDLR_ENFOPRIORITY -1005200 /**< priority of the constraint handler for constraint enforcing */ 90 #define CONSHDLR_CHECKPRIORITY -1005200 /**< priority of the constraint handler for checking feasibility */ 91 #define CONSHDLR_SEPAFREQ 5 /**< frequency for separating cuts; zero means to separate only in the root node */ 92 #define CONSHDLR_PROPFREQ 5 /**< frequency for propagating domains; zero means only preprocessing propagation */ 93 #define CONSHDLR_EAGERFREQ -1 /**< frequency for using all instead of only the useful constraints in separation, 94 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */ 95 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */ 96 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */ 97 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */ 98 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */ 99 100 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP 101 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE 102 103 #define DEFAULT_PPSYMRESACK TRUE /**< whether we allow upgrading to packing/partitioning symresacks */ 104 #define DEFAULT_CHECKMONOTONICITY TRUE /**< check whether permutation is monotone when upgrading to packing/partitioning symresacks */ 105 #define DEFAULT_FORCECONSCOPY FALSE /**< whether symresack constraints should be forced to be copied to sub SCIPs */ 106 107 /* Constants to store fixings */ 108 #define FIXED0 1 /* When a variable is fixed to 0. */ 109 #define FIXED1 2 /* When a variable is fixed to 1. */ 110 #define UNFIXED 3 /* When a variable is neither fixed to 0 or to 1. */ 111 #define NOINIT 0 /* A dummy entry for non-initialized variables. 112 * Must have value 0 because of SCIPallocCleanBufferArray. */ 113 /* A macro for checking if a variable was fixed during a bound change */ 114 #define ISFIXED(x, bdchgidx) (SCIPvarGetUbAtIndex(x, bdchgidx, FALSE) - SCIPvarGetLbAtIndex(x, bdchgidx, FALSE) < 0.5) 115 116 117 118 /* 119 * Data structures 120 */ 121 122 /** constraint handler data */ 123 struct SCIP_ConshdlrData 124 { 125 SCIP_Bool checkppsymresack; /**< whether we allow upgrading to packing/partitioning symresacks */ 126 SCIP_Bool checkmonotonicity; /**< check whether permutation is monotone when upgrading to packing/partitioning symresacks */ 127 int maxnvars; /**< maximal number of variables in a symresack constraint */ 128 SCIP_Bool forceconscopy; /**< whether symresack constraints should be forced to be copied to sub SCIPs */ 129 }; 130 131 132 /** constraint data for symresack constraints */ 133 struct SCIP_ConsData 134 { 135 SCIP_VAR** vars; /**< variables */ 136 int nvars; /**< number of variables */ 137 int* perm; /**< permutation associated to the symresack */ 138 int* invperm; /**< inverse permutation */ 139 SCIP_Bool ppupgrade; /**< whether constraint is upgraded to packing/partitioning symresack */ 140 SCIP_Bool ismodelcons; /**< whether the symresack is a model constraint */ 141 #ifdef SCIP_DEBUG 142 int debugcnt; /**< counter to store number of added cover inequalities */ 143 #endif 144 145 /* data for upgraded symresack constraints */ 146 int ncycles; /**< number of cycles in permutation */ 147 int** cycledecomposition; /**< cycle decomposition */ 148 int ndescentpoints; /**< number of descent points in perm (only used if perm is not monotone) */ 149 int* descentpoints; /**< descent points in perm (only used if perm is not monotone) */ 150 }; 151 152 153 /* 154 * Local methods 155 */ 156 157 /** frees a symresack constraint data */ 158 static 159 SCIP_RETCODE consdataFree( 160 SCIP* scip, /**< SCIP data structure */ 161 SCIP_CONSDATA** consdata /**< pointer to symresack constraint data */ 162 ) 163 { 164 int nvars; 165 int i; 166 167 assert( consdata != NULL ); 168 assert( *consdata != NULL ); 169 170 nvars = (*consdata)->nvars; 171 172 if ( nvars == 0 ) 173 { 174 assert( (*consdata)->vars == NULL ); 175 assert( (*consdata)->perm == NULL ); 176 assert( (*consdata)->invperm == NULL ); 177 assert( (*consdata)->ncycles == 0 ); 178 assert( (*consdata)->cycledecomposition == NULL ); 179 180 SCIPfreeBlockMemory(scip, consdata); 181 182 return SCIP_OKAY; 183 } 184 185 if ( (*consdata)->ndescentpoints > 0 ) 186 { 187 assert( (*consdata)->descentpoints != NULL ); 188 189 SCIPfreeBlockMemoryArray(scip, &((*consdata)->descentpoints), (*consdata)->ndescentpoints); 190 } 191 192 if ( (*consdata)->ppupgrade ) 193 { 194 for (i = 0; i < (*consdata)->ncycles; ++i) 195 { 196 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cycledecomposition[i]), nvars + 1); 197 } 198 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cycledecomposition), (*consdata)->ncycles); 199 } 200 201 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->invperm), nvars); 202 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->perm), nvars); 203 204 for (i = 0; i < nvars; ++i) 205 { 206 SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->vars[i]) ); 207 } 208 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars), nvars); 209 210 SCIPfreeBlockMemory(scip, consdata); 211 212 return SCIP_OKAY; 213 } 214 215 216 /** check whether constraint can be upgraded to packing/partitioning symresack */ 217 static 218 SCIP_RETCODE packingUpgrade( 219 SCIP* scip, /**< SCIP data structure */ 220 SCIP_CONSDATA** consdata, /**< pointer to store constraint data */ 221 int* perm, /**< permutation */ 222 SCIP_VAR** vars, /**< variables affected by permutation */ 223 int nvars, /**< length of permutation */ 224 SCIP_Bool checkmonotonicity, /**< check whether permutation is monotone */ 225 SCIP_Bool* upgrade /**< pointer to store whether upgrade was successful */ 226 ) 227 { 228 SCIP_Bool* covered; 229 SCIP_Bool descent; 230 SCIP_CONSHDLR* setppcconshdlr; 231 SCIP_CONS** setppcconss; 232 SCIP_VAR* var; 233 SCIP_Bool terminated = FALSE; 234 int** cycledecomposition; 235 int* indicesincycle; 236 int nsetppcconss; 237 int curcycle; 238 int maxcyclelength; 239 int ncycles = 0; 240 int c; 241 int i; 242 int j; 243 int ndescentpoints = 0; 244 int* descentpoints; 245 246 assert( scip != NULL ); 247 assert( perm != NULL ); 248 assert( vars != NULL ); 249 assert( nvars > 0 ); 250 assert( upgrade != NULL ); 251 252 *upgrade = FALSE; 253 254 SCIP_CALL( SCIPallocBufferArray(scip, &covered, nvars) ); 255 256 for (i = 0; i < nvars; ++i) 257 covered[i] = FALSE; 258 259 /* get number of cycles in permutation */ 260 for (i = 0; i < nvars; ++i) 261 { 262 /* skip checked indices */ 263 if ( covered[i] ) 264 continue; 265 266 ++ncycles; 267 j = i; 268 descent = FALSE; 269 270 do 271 { 272 covered[j] = TRUE; 273 274 if ( perm[j] < j ) 275 { 276 ++ndescentpoints; 277 278 if ( ! descent ) 279 descent = TRUE; 280 else if ( checkmonotonicity ) 281 break; 282 } 283 284 j = perm[j]; 285 } 286 while ( j != i ); 287 288 /* if cycle is not monotone and we require the cycle to be monotone */ 289 if ( j != i ) 290 { 291 assert( checkmonotonicity ); 292 SCIPfreeBufferArray(scip, &covered); 293 294 return SCIP_OKAY; 295 } 296 } 297 assert( ncycles <= nvars / 2 ); 298 299 /* check for packing/partitioning type */ 300 for (i = 0; i < nvars; ++i) 301 covered[i] = FALSE; 302 303 /* compute cycle decomposition: row i stores in entry 0 the length of the cycle, 304 * the remaining entries are the coordinates in the cycle; 305 * store descent points as well if permutation is not monotone */ 306 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &cycledecomposition, ncycles) ); 307 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &descentpoints, ndescentpoints) ); 308 for (i = 0; i < ncycles; ++i) 309 { 310 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &cycledecomposition[i], nvars + 1) ); 311 } 312 313 curcycle = 0; 314 maxcyclelength = 0; 315 c = 0; 316 for (i = 0; i < nvars; ++i) 317 { 318 int cyclelength = 0; 319 320 /* skip checked indices */ 321 if ( covered[i] ) 322 continue; 323 324 j = i; 325 do 326 { 327 if ( perm[j] < j ) 328 descentpoints[c++] = j; 329 330 covered[j] = TRUE; 331 cycledecomposition[curcycle][++cyclelength] = j; 332 j = perm[j]; 333 } 334 while ( j != i ); 335 336 cycledecomposition[curcycle][0] = cyclelength; 337 ++curcycle; 338 339 if ( maxcyclelength < cyclelength ) 340 maxcyclelength = cyclelength; 341 } 342 assert( c == ndescentpoints ); 343 344 /* permutation can be upgraded -> check whether the symresack is of packing/partitioning type */ 345 setppcconshdlr = SCIPfindConshdlr(scip, "setppc"); 346 if ( setppcconshdlr == NULL ) 347 { 348 SCIPerrorMessage("Setppc constraint handler not found.\n"); 349 return SCIP_PLUGINNOTFOUND; 350 } 351 setppcconss = SCIPconshdlrGetConss(setppcconshdlr); 352 nsetppcconss = SCIPconshdlrGetNConss(setppcconshdlr); 353 354 /* Check whether each cycle of the symresack is contained in a set packing/partitioning constraint. 355 * To this end, we have to guarantee that all affected variables are not negated since permutations 356 * are given w.r.t. original variables. */ 357 *upgrade = TRUE; 358 359 SCIP_CALL( SCIPallocBufferArray(scip, &indicesincycle, maxcyclelength) ); 360 361 for (i = 0; i < ncycles && *upgrade && ! terminated; ++i) 362 { 363 int cyclelength; 364 365 /* get indices of variables in current cycle */ 366 for (j = 0; j < cycledecomposition[i][0]; ++ j) 367 { 368 var = vars[cycledecomposition[i][j + 1]]; 369 370 if ( SCIPvarIsNegated(var) ) 371 { 372 terminated = TRUE; 373 break; 374 } 375 376 indicesincycle[j] = SCIPvarGetProbindex(var); 377 } 378 379 cyclelength = cycledecomposition[i][0]; 380 381 /* iterate over constraints 382 * 383 * @todo Improve the check by sorting the constraints in the setppcconss array 384 * by type and number of contained variables. */ 385 for (c = 0; c < nsetppcconss; ++c) 386 { 387 int nsetppcvars; 388 SCIP_VAR** setppcvars; 389 int varidx; 390 int nfound = 0; 391 int k; 392 393 /* check type */ 394 if ( SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_COVERING ) 395 continue; 396 assert( SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_PARTITIONING || SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_PACKING ); 397 398 /* get set packing/partitioning variables */ 399 nsetppcvars = SCIPgetNVarsSetppc(scip, setppcconss[c]); 400 401 /* skip empty constraints (might not have been removed by presolving yet) */ 402 if ( nsetppcvars == 0 ) 403 continue; 404 assert( nsetppcvars > 0 ); 405 406 setppcvars = SCIPgetVarsSetppc(scip, setppcconss[c]); 407 assert( setppcvars != NULL ); 408 409 /* check whether all variables of the cycle are contained in setppc constraint */ 410 for (j = 0; j < nsetppcvars && nfound < cyclelength; ++j) 411 { 412 var = setppcvars[j]; 413 414 if ( SCIPvarIsNegated(var) ) 415 continue; 416 417 varidx = SCIPvarGetProbindex(var); 418 419 for (k = 0; k < cyclelength; ++k) 420 { 421 if ( varidx == indicesincycle[k] ) 422 { 423 ++nfound; 424 break; 425 } 426 } 427 } 428 assert( nfound <= cyclelength ); 429 430 if ( nfound == cyclelength ) 431 break; 432 } 433 434 /* row is not contained in a set packing/partitioning constraint */ 435 if ( c >= nsetppcconss ) 436 *upgrade = FALSE; 437 } 438 439 if ( *upgrade ) 440 { 441 (*consdata)->ncycles = ncycles; 442 (*consdata)->cycledecomposition = cycledecomposition; 443 (*consdata)->ndescentpoints = ndescentpoints; 444 (*consdata)->descentpoints = descentpoints; 445 SCIPdebugMsg(scip, "added monotone PP symresack.\n"); 446 447 SCIPfreeBufferArray(scip, &indicesincycle); 448 SCIPfreeBufferArray(scip, &covered); 449 } 450 else 451 { 452 SCIPfreeBlockMemoryArray(scip, &descentpoints, ndescentpoints); 453 SCIPfreeBufferArray(scip, &indicesincycle); 454 SCIPfreeBufferArray(scip, &covered); 455 for (i = 0; i < ncycles; ++i) 456 { 457 SCIPfreeBlockMemoryArray(scip, &cycledecomposition[i], nvars + 1); 458 } 459 SCIPfreeBlockMemoryArray(scip, &cycledecomposition, ncycles); 460 } 461 462 return SCIP_OKAY; 463 } 464 465 466 /** creates symresack constraint data 467 * 468 * If the input data contains non-binary variables or fixed 469 * points, we delete these variables in a preprocessing step. 470 */ 471 static 472 SCIP_RETCODE consdataCreate( 473 SCIP* scip, /**< SCIP data structure */ 474 SCIP_CONSHDLR* conshdlr, /**< symresack constraint handler */ 475 SCIP_CONSDATA** consdata, /**< pointer to store constraint data */ 476 SCIP_VAR*const* inputvars, /**< input variables of the constraint handler */ 477 int inputnvars, /**< input number of variables of the constraint handler*/ 478 int* inputperm, /**< input permutation of the constraint handler */ 479 SCIP_Bool ismodelcons /**< whether the symresack is a model constraint */ 480 ) 481 { 482 SCIP_CONSHDLRDATA* conshdlrdata; 483 SCIP_VAR** vars; 484 SCIP_Bool upgrade; 485 int* indexcorrection; 486 int* invperm; 487 int* perm; 488 int naffectedvariables; 489 int i; 490 int j = 0; 491 492 assert( consdata != NULL ); 493 assert( conshdlr != NULL ); 494 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 495 496 SCIP_CALL( SCIPallocBlockMemory(scip, consdata) ); 497 498 #ifdef SCIP_DEBUG 499 (*consdata)->debugcnt = 0; 500 #endif 501 502 (*consdata)->ndescentpoints = 0; 503 (*consdata)->descentpoints = NULL; 504 (*consdata)->ismodelcons = ismodelcons; 505 506 /* count the number of binary variables which are affected by the permutation */ 507 SCIP_CALL( SCIPallocBufferArray(scip, &indexcorrection, inputnvars) ); 508 indexcorrection[0] = -1; 509 for (i = 0; i < inputnvars; ++i) 510 { 511 if ( inputperm[i] != i && SCIPvarIsBinary(inputvars[i]) ) 512 { 513 if ( i == 0 ) 514 indexcorrection[i] = 0; 515 else 516 indexcorrection[i] = indexcorrection[i - 1] + 1; 517 } 518 else 519 { 520 if ( i > 0 ) 521 indexcorrection[i] = indexcorrection[i - 1]; 522 } 523 } 524 naffectedvariables = indexcorrection[inputnvars - 1] + 1; 525 526 (*consdata)->nvars = naffectedvariables; 527 528 /* Stop if we detect that the permutation fixes each binary point. */ 529 if ( naffectedvariables == 0 ) 530 { 531 SCIPfreeBufferArrayNull(scip, &indexcorrection); 532 533 (*consdata)->vars = NULL; 534 (*consdata)->perm = NULL; 535 (*consdata)->invperm = NULL; 536 (*consdata)->ppupgrade = FALSE; 537 (*consdata)->ncycles = 0; 538 (*consdata)->cycledecomposition = NULL; 539 return SCIP_OKAY; 540 } 541 542 /* remove fixed points from permutation representation */ 543 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vars, naffectedvariables) ); 544 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &perm, naffectedvariables) ); 545 for (i = 0; i < inputnvars; ++i) 546 { 547 if ( i == 0 ) 548 { 549 if ( indexcorrection[i] > -1 ) 550 { 551 vars[j] = inputvars[i]; 552 perm[j++] = indexcorrection[inputperm[i]]; 553 } 554 } 555 else 556 { 557 if ( indexcorrection[i] > indexcorrection[i - 1] ) 558 { 559 vars[j] = inputvars[i]; 560 perm[j++] = indexcorrection[inputperm[i]]; 561 } 562 } 563 } 564 SCIPfreeBufferArrayNull(scip, &indexcorrection); 565 566 (*consdata)->vars = vars; 567 (*consdata)->perm = perm; 568 569 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &invperm, naffectedvariables) ); 570 for (i = 0; i < naffectedvariables; ++i) 571 { 572 SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars[i]) ); 573 invperm[perm[i]] = i; 574 } 575 (*consdata)->invperm = invperm; 576 577 /* check for upgrade to packing/partitioning symresacks*/ 578 conshdlrdata = SCIPconshdlrGetData(conshdlr); 579 upgrade = FALSE; 580 if ( conshdlrdata->checkppsymresack ) 581 { 582 SCIP_CALL( packingUpgrade(scip, consdata, perm, vars, naffectedvariables, conshdlrdata->checkmonotonicity, &upgrade) ); 583 } 584 585 (*consdata)->ppupgrade = upgrade; 586 587 /* get transformed variables, if we are in the transformed problem */ 588 if ( SCIPisTransformed(scip) ) 589 { 590 /* Make sure that all variables cannot be multiaggregated (cannot be handled by cons_symresack, since one cannot 591 * easily eliminate single variables from a symresack constraint. */ 592 for (i = 0; i < naffectedvariables; ++i) 593 { 594 SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->vars[i], &(*consdata)->vars[i]) ); 595 SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars[i]) ); 596 } 597 } 598 599 return SCIP_OKAY; 600 } 601 602 603 /** generate initial LP cut 604 * 605 * We generate the ordering inequality for the pair \f$(1, \gamma^{-1}(1))\f$, i.e., 606 * the inequality \f$-x_{1} + x_{\gamma^{-1}(1)} \leq 0\f$. This inequality is valid, 607 * because we guaranteed in a preprocessing step that all variables are binary. 608 * 609 * Furthermore, we add facet inequalities of packing/partitioning symresacks if 610 * we deal with packing/partitioning symresacks. 611 */ 612 static 613 SCIP_RETCODE initLP( 614 SCIP* scip, /**< SCIP pointer */ 615 SCIP_CONS* cons, /**< constraint */ 616 SCIP_Bool checkmonotonicity, /**< has it been checked whether permutation is monotone for packing/partitioning symresacks? */ 617 SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */ 618 ) 619 { 620 SCIP_CONSDATA* consdata; 621 SCIP_VAR** vars; 622 SCIP_ROW* row; 623 int nvars; 624 #ifdef SCIP_DEBUG 625 char name[SCIP_MAXSTRLEN]; 626 #endif 627 int i; 628 int j; 629 int k; 630 631 assert( scip != NULL ); 632 assert( cons != NULL ); 633 assert( infeasible != NULL ); 634 635 *infeasible = FALSE; 636 637 consdata = SCIPconsGetData(cons); 638 assert( consdata != NULL ); 639 640 nvars = consdata->nvars; 641 642 /* avoid stupid problems */ 643 if ( nvars <= 1 ) 644 return SCIP_OKAY; 645 646 assert( consdata->vars != NULL ); 647 vars = consdata->vars; 648 649 /* there are no fixed points */ 650 assert( consdata->invperm[0] != 0 ); 651 652 /* add ordering inequality */ 653 #ifdef SCIP_DEBUG 654 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "symresack_init_%s", SCIPconsGetName(cons)); 655 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) ); 656 #else 657 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) ); 658 #endif 659 SCIP_CALL( SCIPaddVarToRow(scip, row, vars[0], -1.0) ); 660 SCIP_CALL( SCIPaddVarToRow(scip, row, vars[consdata->invperm[0]], 1.0) ); 661 662 SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) ); 663 664 SCIP_CALL( SCIPreleaseRow(scip, &row) ); 665 666 /* check whether we have a packing/partioning symresack */ 667 if ( consdata->ppupgrade && ! *infeasible ) 668 { 669 if ( checkmonotonicity ) 670 { 671 SCIP_VAR** varsincons; 672 SCIP_Real* coeffs; 673 int** cycledecomposition; 674 int ncycles; 675 int nvarsincons; 676 int nvarsincycle; 677 int firstelemincycle; 678 679 ncycles = consdata->ncycles; 680 cycledecomposition = consdata->cycledecomposition; 681 682 SCIP_CALL( SCIPallocBufferArray(scip, &varsincons, nvars) ); 683 SCIP_CALL( SCIPallocBufferArray(scip, &coeffs, nvars) ); 684 685 coeffs[0] = 1.0; 686 687 /* add packing/partitioning symresack constraints */ 688 for (i = 0; i < ncycles; ++i) 689 { 690 assert( cycledecomposition[i][0] > 0 ); 691 692 nvarsincycle = cycledecomposition[i][0]; 693 varsincons[0] = vars[cycledecomposition[i][nvarsincycle]]; 694 firstelemincycle = cycledecomposition[i][1]; 695 696 assert( firstelemincycle == consdata->perm[cycledecomposition[i][nvarsincycle]] ); 697 698 nvarsincons = 1; 699 700 /* add variables of other cycles to the constraint */ 701 for (j = 0; j < i; ++j) 702 { 703 nvarsincycle = cycledecomposition[j][0]; 704 for (k = 1; k <= nvarsincycle; ++k) 705 { 706 if ( cycledecomposition[j][k] < firstelemincycle ) 707 { 708 varsincons[nvarsincons] = vars[cycledecomposition[j][k]]; 709 coeffs[nvarsincons++] = -1.0; 710 } 711 else 712 continue; 713 } 714 } 715 716 #ifdef SCIP_DEBUG 717 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "ppSymresack_%d_%s", i, SCIPconsGetName(cons)); 718 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) ); 719 #else 720 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) ); 721 #endif 722 SCIP_CALL( SCIPaddVarsToRow(scip, row, nvarsincons, varsincons, coeffs) ); 723 724 SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) ); 725 SCIP_CALL( SCIPreleaseRow(scip, &row) ); 726 727 if ( *infeasible ) 728 break; 729 } 730 731 SCIPfreeBufferArray(scip, &coeffs); 732 SCIPfreeBufferArray(scip, &varsincons); 733 } 734 else 735 { 736 SCIP_Real* coeffs; 737 SCIP_VAR** varsincons; 738 int* imgdescentpoints; 739 int* descentpoints; 740 int* perm; 741 int ndescentpoints; 742 int lastascent = 0; 743 int newlastascent = 0; 744 int nvarsincons = 1; 745 746 descentpoints = consdata->descentpoints; 747 ndescentpoints = consdata->ndescentpoints; 748 perm = consdata->perm; 749 750 assert( descentpoints != NULL ); 751 assert( ndescentpoints > 0 ); 752 assert( perm != NULL ); 753 assert( vars != NULL ); 754 assert( nvars > 0 ); 755 756 SCIP_CALL( SCIPallocBufferArray(scip, &imgdescentpoints, ndescentpoints) ); 757 758 /* get images of descentpoints */ 759 for (j = 0; j < ndescentpoints; ++j) 760 imgdescentpoints[j] = perm[descentpoints[j]]; 761 762 /* sort descent points increasingly w.r.t. the corresponding image */ 763 SCIPsortIntInt(imgdescentpoints, descentpoints, ndescentpoints); 764 765 /* iteratively generate coefficient vector: the first entry is the descent point j and the remaining entries 766 * are the corresponding ascent points less than perm[j] 767 */ 768 SCIP_CALL( SCIPallocClearBufferArray(scip, &coeffs, nvars) ); 769 SCIP_CALL( SCIPallocClearBufferArray(scip, &varsincons, nvars) ); 770 coeffs[0] = 1.0; 771 for (j = 0; j < ndescentpoints; ++j) 772 { 773 varsincons[0] = vars[descentpoints[j]]; 774 for (i = lastascent; i < imgdescentpoints[j]; ++i) 775 { 776 if ( perm[i] > i ) 777 { 778 coeffs[nvarsincons] = -1.0; 779 varsincons[nvarsincons++] = vars[i]; 780 newlastascent = i; 781 } 782 } 783 lastascent = newlastascent; 784 785 #ifdef SCIP_DEBUG 786 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "ppSymresack_%d_%s", j, SCIPconsGetName(cons)); 787 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) ); 788 #else 789 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) ); 790 #endif 791 SCIP_CALL( SCIPaddVarsToRow(scip, row, nvarsincons, varsincons, coeffs) ); 792 793 SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) ); 794 SCIP_CALL( SCIPreleaseRow(scip, &row) ); 795 796 if ( *infeasible ) 797 break; 798 } 799 800 SCIPfreeBufferArray(scip, &varsincons); 801 SCIPfreeBufferArray(scip, &coeffs); 802 SCIPfreeBufferArray(scip, &imgdescentpoints); 803 } 804 } 805 806 return SCIP_OKAY; 807 } 808 809 810 /** Determines if a vector with additional fixings could exist that is lexicographically larger than its image. 811 * 812 * Given a vector of variables, a permutation, and a set of additional (virtual) fixings. 813 * If a vector adhering to the local variable bounds (local fixings) and to the virtual fixings exists, 814 * then infeasible is FALSE, otherwise TRUE. 815 */ 816 static 817 SCIP_RETCODE checkFeasible( 818 SCIP* scip, /**< SCIP pointer */ 819 SCIP_VAR** vars, /**< array of variables affected by permutation */ 820 int* invperm, /**< inverse of permutation */ 821 int nvars, /**< number of variables */ 822 int start, /**< at which position to start (assuming previous positions are equal) */ 823 int* tempfixings, /**< array with at entry i the virtual fixing of variable vars[i] */ 824 int* tempfixentries, /**< the entries i that are virtually fixed until numfixentriesinit */ 825 int numfixentriesinit, /**< the number of virtually fixed entries */ 826 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is detected in these fixings */ 827 int* infeasibleentry /**< pointer to store at which entry a (0, 1) pattern is found */ 828 ) 829 { 830 SCIP_VAR* var1; 831 SCIP_VAR* var2; 832 int var1fix; 833 int var2fix; 834 835 int i; 836 int numfixentries; 837 838 /* avoid trivial problems */ 839 if ( nvars < 2 ) 840 return SCIP_OKAY; 841 842 assert( scip != NULL ); 843 assert( vars != NULL ); 844 assert( invperm != NULL ); 845 assert( tempfixings != NULL ); 846 assert( tempfixentries != NULL ); 847 assert( infeasible != NULL ); 848 849 /* A counter for how many virtual fixings we have. */ 850 numfixentries = numfixentriesinit; 851 852 *infeasible = FALSE; 853 854 for (i = start; i < nvars; ++i) 855 { 856 /* there are no fixed points */ 857 assert( invperm[i] != i ); 858 859 /* get variables of first and second column */ 860 var1 = vars[i]; 861 var2 = vars[invperm[i]]; 862 863 assert( var1 != NULL ); 864 assert( var2 != NULL ); 865 866 /* Get virtual fixing of variable in left column */ 867 var1fix = tempfixings[i]; 868 if ( var1fix == NOINIT ) 869 { 870 if ( SCIPvarGetUbLocal(var1) < 0.5 ) 871 { 872 var1fix = FIXED0; 873 assert( SCIPvarGetLbLocal(var1) <= 0.5 ); 874 } 875 else if ( SCIPvarGetLbLocal(var1) > 0.5 ) 876 var1fix = FIXED1; 877 else 878 var1fix = UNFIXED; 879 } 880 assert( var1fix != NOINIT ); 881 882 /* Get virtual fixing of variable in right column */ 883 var2fix = tempfixings[invperm[i]]; 884 if ( var2fix == NOINIT ) 885 { 886 if ( SCIPvarGetUbLocal(var2) < 0.5 ) 887 { 888 var2fix = FIXED0; 889 assert( SCIPvarGetLbLocal(var2) <= 0.5 ); 890 } 891 else if ( SCIPvarGetLbLocal(var2) > 0.5 ) 892 var2fix = FIXED1; 893 else 894 var2fix = UNFIXED; 895 } 896 assert( var2fix != NOINIT ); 897 898 /* Encounter one of (_, _), (_, 0), (1, _), (1, 0). In all cases (1, 0) can be constructed. Thus feasible. */ 899 if ( var1fix != FIXED0 && var2fix != FIXED1 ) 900 break; 901 /* Encounter (0, 1). Infeasible. */ 902 else if ( var1fix == FIXED0 && var2fix == FIXED1 ) 903 { 904 *infeasible = TRUE; 905 *infeasibleentry = i; 906 break; 907 } 908 /* Encounter (0, _). Virtually fix var2 to 0. */ 909 else if ( var1fix == FIXED0 && var2fix == UNFIXED ) 910 { 911 tempfixings[invperm[i]] = FIXED0; 912 /* Mark that we have fixed invperm[i]. */ 913 tempfixentries[numfixentries++] = invperm[i]; 914 } 915 /* Encounter (_, 1). Virtually fix var1 to 1. */ 916 else if(var1fix == UNFIXED && var2fix == FIXED1 ) 917 { 918 tempfixings[i] = FIXED0; 919 /* Mark that we have fixed invperm[i]. */ 920 tempfixentries[numfixentries++] = i; 921 } 922 /* Remaining cases are (0, 0) and (1, 1). In both cases: continue. */ 923 } 924 925 /* Undo virtual fixings made in this function */ 926 for (i = numfixentriesinit; i < numfixentries; ++i) 927 { 928 tempfixings[tempfixentries[i]] = NOINIT; 929 tempfixentries[i] = 0; 930 } 931 932 return SCIP_OKAY; 933 } 934 935 936 /** perform propagation of symresack constraint */ 937 static 938 SCIP_RETCODE propVariables( 939 SCIP* scip, /**< SCIP pointer */ 940 SCIP_CONS* cons, /**< constraint to be propagated */ 941 SCIP_Bool* infeasible, /**< pointer to store whether it was detected that the node is infeasible */ 942 int* ngen /**< pointer to store number of generated bound strengthenings */ 943 ) 944 { 945 SCIP_CONSDATA* consdata; 946 SCIP_VAR** vars; 947 int* invperm; 948 int nvars; 949 int i; 950 int r; 951 SCIP_VAR* var1; 952 SCIP_VAR* var2; 953 int var1fix; 954 int var2fix; 955 SCIP_Bool tightened; 956 SCIP_Bool peekinfeasible; 957 int peekinfeasibleentry; 958 int* tempfixings; 959 int* tempfixentries; 960 961 assert( scip != NULL ); 962 assert( cons != NULL ); 963 assert( infeasible != NULL ); 964 assert( ngen != NULL ); 965 966 SCIPdebugMsg(scip, "Propagating variables of constraint <%s>.\n", SCIPconsGetName(cons)); 967 968 *ngen = 0; 969 *infeasible = FALSE; 970 971 /* get data of constraint */ 972 consdata = SCIPconsGetData(cons); 973 assert( consdata != NULL ); 974 nvars = consdata->nvars; 975 976 /* avoid trivial problems */ 977 if ( nvars < 2 ) 978 return SCIP_OKAY; 979 980 assert( consdata->vars != NULL ); 981 assert( consdata->invperm != NULL ); 982 vars = consdata->vars; 983 invperm = consdata->invperm; 984 985 /* loop through all variables */ 986 for (i = 0; i < nvars; ++i) 987 { 988 /* there are no fixed points */ 989 assert( invperm[i] != i ); 990 991 /* get variables of first and second column */ 992 var1 = vars[i]; 993 var2 = vars[invperm[i]]; 994 assert( var1 != NULL ); 995 assert( var2 != NULL ); 996 997 /* Get the fixing status of the left column variable var1 */ 998 if ( SCIPvarGetUbLocal(var1) < 0.5 ) 999 { 1000 var1fix = FIXED0; 1001 assert( SCIPvarGetLbLocal(var1) <= 0.5 ); 1002 } 1003 else if ( SCIPvarGetLbLocal(var1) > 0.5 ) 1004 var1fix = FIXED1; 1005 else 1006 var1fix = UNFIXED; 1007 1008 /* Get the fixing status of the right column variable var2 */ 1009 if ( SCIPvarGetUbLocal(var2) < 0.5 ) 1010 { 1011 var2fix = FIXED0; 1012 assert( SCIPvarGetLbLocal(var2) <= 0.5 ); 1013 } 1014 else if ( SCIPvarGetLbLocal(var2) > 0.5 ) 1015 var2fix = FIXED1; 1016 else 1017 var2fix = UNFIXED; 1018 1019 /* Encounter one of (_, _), (_, 0), (1, _), (1, 0). Check if (1, 1) or (0, 0) are possible, otherwise fix. */ 1020 if ( var1fix != FIXED0 && var2fix != FIXED1 ) 1021 { 1022 assert( SCIPvarGetUbLocal(var1) > 0.5 ); 1023 assert( SCIPvarGetLbLocal(var2) < 0.5 ); 1024 1025 SCIPdebugMsg(scip, "Check variable pair (%d,%d).\n", i, invperm[i]); 1026 SCIPdebugMsg(scip, " -> node is feasible (could set pair to (1,0) and every earlier pair is constant).\n"); 1027 1028 if ( var1fix == UNFIXED || var2fix == UNFIXED ) 1029 { 1030 /* Create arrays tempfixings and tempfixentries to store virtual fixings. */ 1031 SCIP_CALL( SCIPallocCleanBufferArray(scip, &tempfixings, nvars) ); 1032 SCIP_CALL( SCIPallocCleanBufferArray(scip, &tempfixentries, nvars) ); 1033 1034 if ( var1fix == UNFIXED ) 1035 { 1036 assert( SCIPvarGetLbLocal(var1) < 0.5 ); 1037 1038 /* Peek whether a lexicographical larger-or-equal vector can be created with var1 fixed to 0 */ 1039 SCIPdebugMsg(scip, " -> First entry is not fixed. Check if 0 is feasible.\n"); 1040 tempfixings[i] = FIXED0; 1041 tempfixentries[0] = i; 1042 SCIP_CALL( checkFeasible(scip, vars, invperm, nvars, i, tempfixings, tempfixentries, 1, 1043 &peekinfeasible, &peekinfeasibleentry) ); 1044 1045 if ( peekinfeasible ) 1046 { 1047 /* No feasible vector exists with var1 set to 0, so it must be a 1-fixing. */ 1048 SCIPdebugMsg(scip, " -> First entry is not fixed. 0 is not feasible. Fixing to 1.\n"); 1049 SCIP_CALL( SCIPinferVarLbCons(scip, var1, 1.0, cons, i + nvars * peekinfeasibleentry, 1050 FALSE, infeasible, &tightened) ); /*lint !e713*/ 1051 assert( ! *infeasible ); 1052 1053 if ( tightened ) 1054 ++(*ngen); 1055 } 1056 1057 tempfixings[i] = NOINIT; 1058 tempfixentries[0] = 0; 1059 } 1060 1061 if ( var2fix == UNFIXED ) 1062 { 1063 assert( SCIPvarGetUbLocal(var2) > 0.5 ); 1064 1065 /* Peek whether a lexicographical larger-or-equal vector can be created with var2 fixed to 1 */ 1066 SCIPdebugMsg(scip, " -> Second entry is not fixed. Check if 1 is feasible.\n"); 1067 tempfixings[invperm[i]] = FIXED1; 1068 tempfixentries[0] = invperm[i]; 1069 SCIP_CALL( checkFeasible(scip, vars, invperm, nvars, i, tempfixings, tempfixentries, 1, 1070 &peekinfeasible, &peekinfeasibleentry) ); 1071 1072 if ( peekinfeasible ) 1073 { 1074 /* No feasible vector exists with var2 set to 1, so it must be a 1-fixing. */ 1075 SCIPdebugMsg(scip, " -> Second entry is not fixed. 1 is not feasible. Fixing to 0.\n"); 1076 SCIP_CALL( SCIPinferVarUbCons(scip, var2, 0.0, cons, i + nvars * peekinfeasibleentry, 1077 FALSE, infeasible, &tightened) ); /*lint !e713*/ 1078 assert( ! *infeasible ); 1079 1080 if ( tightened ) 1081 ++(*ngen); 1082 } 1083 1084 tempfixings[invperm[i]] = NOINIT; 1085 tempfixentries[0] = 0; 1086 } 1087 1088 SCIPfreeCleanBufferArray(scip, &tempfixentries); 1089 SCIPfreeCleanBufferArray(scip, &tempfixings); 1090 } 1091 1092 /* Can stop here, because this row can become (1, 0). Therefore all next rows can take arbitrary values. */ 1093 break; 1094 } 1095 /* Encounter (0, 1): If first part of variable pair fixed to 0 and second part is fixed to 1 */ 1096 else if ( var1fix == FIXED0 && var2fix == FIXED1 ) 1097 { 1098 SCIPdebugMsg(scip, "Check variable pair (%d,%d).\n", i, invperm[i]); 1099 1100 SCIPdebugMsg(scip, " -> node infeasible (pair was fixed to (0,1) but there was no pair of type (1,0) before) ---> lexicographical order violated, infeasible.\n"); 1101 1102 /* perform conflict analysis */ 1103 if ( SCIPisConflictAnalysisApplicable(scip) ) 1104 { 1105 SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) ); 1106 1107 for (r = 0; r <= i; ++r) 1108 { 1109 /* there are no fixed points */ 1110 assert( invperm[r] != r ); 1111 1112 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[r]) ); 1113 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[invperm[r]]) ); 1114 } 1115 1116 SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) ); 1117 } 1118 1119 *infeasible = TRUE; 1120 break; 1121 } 1122 /* Encounter (0, _): Fix second part to 0 */ 1123 else if ( var1fix == FIXED0 && var2fix != FIXED0 ) 1124 { 1125 assert( SCIPvarGetUbLocal(var1) < 0.5 ); 1126 assert( SCIPvarGetLbLocal(var2) < 0.5 ); 1127 assert( SCIPvarGetUbLocal(var2) > 0.5 ); 1128 1129 SCIPdebugMsg(scip, "Check variable pair (%d,%d).\n", i, invperm[i]); 1130 1131 assert( SCIPvarGetLbLocal(var2) < 0.5 ); 1132 SCIP_CALL( SCIPinferVarUbCons(scip, var2, 0.0, cons, i, FALSE, infeasible, &tightened) ); /*lint !e713*/ 1133 assert( ! *infeasible ); 1134 1135 if ( tightened ) 1136 ++(*ngen); 1137 } 1138 /* Encounter (_, 1): fix first part to 1 */ 1139 else if ( var1fix != FIXED1 && var2fix == FIXED1 ) 1140 { 1141 assert( SCIPvarGetLbLocal(var1) < 0.5 ); 1142 assert( SCIPvarGetUbLocal(var1) > 0.5 ); 1143 assert( SCIPvarGetLbLocal(var2) > 0.5 ); 1144 1145 SCIPdebugMsg(scip, "Check variable pair (%d,%d).\n", i, invperm[i]); 1146 1147 assert( SCIPvarGetUbLocal(var1) > 0.5 ); 1148 SCIP_CALL( SCIPinferVarLbCons(scip, var1, 1.0, cons, i, FALSE, infeasible, &tightened) ); /*lint !e713*/ 1149 assert( ! *infeasible ); 1150 1151 if ( tightened ) 1152 ++(*ngen); 1153 } 1154 /* Remaining cases are (0, 0) and (1, 1). In these cases we can continue! */ 1155 } 1156 1157 return SCIP_OKAY; 1158 } 1159 1160 1161 /** add symresack cover inequality */ 1162 static 1163 SCIP_RETCODE addSymresackInequality( 1164 SCIP* scip, /**< SCIP pointer */ 1165 SCIP_CONS* cons, /**< constraint */ 1166 int nvars, /**< number of variables */ 1167 SCIP_VAR** vars, /**< variables */ 1168 int* coeffs, /**< coefficient vector of inequality to be added */ 1169 SCIP_Real rhs, /**< right-hand side of inequality to be added */ 1170 SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */ 1171 ) 1172 { 1173 SCIP_ROW* row; 1174 int i; 1175 #ifdef SCIP_DEBUG 1176 SCIP_CONSDATA* consdata; 1177 char name[SCIP_MAXSTRLEN]; 1178 #endif 1179 1180 assert( scip != NULL ); 1181 assert( cons != NULL ); 1182 assert( nvars > 0 ); 1183 assert( vars != NULL ); 1184 assert( coeffs != NULL ); 1185 assert( infeasible != NULL ); 1186 1187 *infeasible = FALSE; 1188 1189 #ifdef SCIP_DEBUG 1190 consdata = SCIPconsGetData(cons); 1191 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "symresack_cover_%s_%d", SCIPconsGetName(cons), consdata->debugcnt); 1192 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) ); 1193 ++consdata->debugcnt; 1194 #else 1195 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "", -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) ); 1196 #endif 1197 SCIP_CALL( SCIPcacheRowExtensions(scip, row) ); 1198 1199 for (i = 0; i < nvars; ++i) 1200 { 1201 if ( coeffs[i] == 1 || coeffs[i] == -1 ) 1202 { 1203 SCIP_CALL( SCIPaddVarToRow(scip, row, vars[i], (SCIP_Real) coeffs[i]) ); 1204 } 1205 } 1206 SCIP_CALL( SCIPflushRowExtensions(scip, row) ); 1207 SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) ); 1208 SCIP_CALL( SCIPreleaseRow(scip, &row) ); 1209 1210 return SCIP_OKAY; 1211 } 1212 1213 1214 /** Maximize a linear function on a "strict" symresack, 1215 * that is a symresack where we do not allow the solution x = gamma(x). 1216 */ 1217 static 1218 SCIP_RETCODE maximizeObjectiveSymresackStrict( 1219 SCIP* scip, /**< SCIP pointer */ 1220 int nvars, /**< number of variables in symresack */ 1221 SCIP_Real* objective, /**< the objective vector */ 1222 int* perm, /**< the permutation (without fixed points) as an array */ 1223 int* invperm, /**< the inverse permutation as an array */ 1224 int* maxcrit, /**< pointer to the critical entry where optimality is found at */ 1225 SCIP_Real* maxsoluval /**< pointer to store the optimal objective value */ 1226 ) 1227 { 1228 /* The maximal objective in every iteration. */ 1229 SCIP_Real tmpobj; 1230 /* The new value of componentobj when combining two components. */ 1231 SCIP_Real tmpnewcompobj; 1232 /* helperobj is the sum of all positive objective-sums for all components. */ 1233 SCIP_Real helperobj = 0.0; 1234 1235 int crit; 1236 int critinv; 1237 int i; 1238 1239 /* For every vertex of degree < 2 we maintain componentends and componentobj. */ 1240 int* componentends; 1241 SCIP_Real* componentobj; 1242 1243 assert( scip != NULL ); 1244 assert( nvars > 0 ); 1245 assert( objective != NULL ); 1246 assert( perm != NULL ); 1247 assert( invperm != NULL ); 1248 assert( maxcrit != NULL ); 1249 assert( maxsoluval != NULL ); 1250 1251 /* The current best known critical entry and objective */ 1252 *maxcrit = -1; 1253 *maxsoluval = -SCIP_DEFAULT_INFINITY; 1254 1255 SCIP_CALL( SCIPallocBufferArray(scip, &componentends, nvars) ); 1256 SCIP_CALL( SCIPallocBufferArray(scip, &componentobj, nvars) ); 1257 1258 /* Initialization: Every entry is a component in the graph, 1259 * having the corresponding objective 1260 */ 1261 for (i = 0; i < nvars; ++i) 1262 { 1263 componentends[i] = i; 1264 componentobj[i] = objective[i]; 1265 if ( SCIPisGT(scip, objective[i], 0.0) ) 1266 helperobj += objective[i]; 1267 } 1268 1269 /* Iterate over all critical rows, and of the graph maintain the components on the vertices of degree < 2. */ 1270 for (crit = 0; crit < nvars; ++crit) 1271 { 1272 critinv = invperm[crit]; 1273 1274 /* Do not allow fixed points. */ 1275 assert( crit != critinv ); 1276 1277 /* If the other end of the component of crit is critinv, then crit cannot be a critical entry. */ 1278 if ( componentends[crit] == critinv ) 1279 continue; 1280 1281 /* Compute objective for crit as critical entry. Update if it is better than the best found objective */ 1282 tmpobj = helperobj; 1283 if ( SCIPisLT(scip, componentobj[crit], 0.0) ) 1284 tmpobj += componentobj[crit]; 1285 if ( SCIPisGT(scip, componentobj[critinv], 0.0) ) 1286 tmpobj -= componentobj[critinv]; 1287 if ( SCIPisGT(scip, tmpobj, *maxsoluval) ) 1288 { 1289 *maxsoluval = tmpobj; 1290 *maxcrit = crit; 1291 } 1292 1293 /* Update helperobj */ 1294 tmpnewcompobj = componentobj[crit] + componentobj[critinv]; 1295 if ( SCIPisGT(scip, componentobj[crit], 0.0) ) 1296 helperobj -= componentobj[crit]; 1297 if ( SCIPisGT(scip, componentobj[critinv], 0.0) ) 1298 helperobj -= componentobj[critinv]; 1299 if ( SCIPisGT(scip, tmpnewcompobj, 0.0) ) 1300 helperobj += tmpnewcompobj; 1301 1302 /* Update the objective of a component */ 1303 componentobj[componentends[crit]] = tmpnewcompobj; 1304 componentobj[componentends[critinv]] = tmpnewcompobj; 1305 1306 /* Connect the endpoints of the newly created path */ 1307 if ( componentends[crit] == crit ) 1308 { 1309 componentends[crit] = componentends[critinv]; 1310 componentends[componentends[critinv]] = crit; 1311 } 1312 else 1313 { 1314 componentends[componentends[crit]] = componentends[critinv]; 1315 componentends[componentends[critinv]] = componentends[crit]; 1316 } 1317 1318 /* Early termination criterion. helperobj is upper bound to tmpobj for every next iteration, 1319 * so if helperobj <= maxsoluval then we can terminate earlier. 1320 */ 1321 if ( SCIPisGE(scip, *maxsoluval, helperobj) ) 1322 break; 1323 } 1324 1325 /* It is always possible to make the first entry critical. */ 1326 assert( *maxcrit >= 0 ); 1327 1328 SCIPfreeBufferArray(scip, &componentobj); 1329 SCIPfreeBufferArray(scip, &componentends); 1330 1331 return SCIP_OKAY; 1332 } 1333 1334 1335 /** For a symresack, determine a maximizer for optimizing linear function 1336 * over a symresack, where the critical entry is fixed. 1337 */ 1338 static 1339 SCIP_RETCODE maximizeObjectiveSymresackCriticalEntry( 1340 SCIP* scip, /**< SCIP pointer */ 1341 int nvars, /**< number of variables in symresack */ 1342 SCIP_Real* objective, /**< the objective vector */ 1343 int* perm, /**< the permutation (without fixed points) as an array */ 1344 int* invperm, /**< the inverse permutation as an array */ 1345 int crit, /**< critical entry where optimality is found at */ 1346 int* maxsolu /**< pointer to the optimal objective array */ 1347 ) 1348 { 1349 /* Compute to which components all entries belong. */ 1350 int* entrycomponent; 1351 SCIP_Real* componentobjective; 1352 1353 int i; 1354 int c; 1355 1356 assert( scip != NULL ); 1357 assert( nvars > 0 ); 1358 assert( objective != NULL ); 1359 assert( perm != NULL ); 1360 assert( invperm != NULL ); 1361 assert( maxsolu != NULL ); 1362 assert( crit >= 0 ); 1363 assert( crit <= nvars ); 1364 1365 SCIP_CALL( SCIPallocBufferArray(scip, &entrycomponent, nvars) ); 1366 SCIP_CALL( SCIPallocBufferArray(scip, &componentobjective, nvars) ); 1367 1368 /* Initially: Everything forms its own component */ 1369 for (i = 0; i < nvars; ++i) 1370 { 1371 entrycomponent[i] = i; 1372 componentobjective[i] = objective[i]; 1373 } 1374 for (i = 0; i < crit; ++i) 1375 { 1376 /* The graph with arcs {i, invperm[i]} if i < c is a collection of paths, cycles and singletons. 1377 * Label the vertices to the lowest entry in the component, and store the value of that in this component. 1378 * Every inner while-loop labels one new vertex per iteration, and a vertex is relabeled exactly once. 1379 */ 1380 if ( entrycomponent[i] < i ) 1381 { 1382 /* This entry is already included in a component. */ 1383 continue; 1384 } 1385 1386 /* Follow the path forward: Take edges {c, invperm[c]} until c >= crit, or a cycle is found. */ 1387 c = i; 1388 while( c < crit ) 1389 { 1390 /* c < crit, so edge {c, invperm[c]} exists. Label invperm[c] as part of component of i */ 1391 c = invperm[c]; 1392 1393 /* Stop if we find a cycle. */ 1394 if ( entrycomponent[c] != c ) 1395 break; 1396 1397 entrycomponent[c] = i; 1398 componentobjective[i] += objective[c]; 1399 } 1400 1401 /* Follow the path backward: Take edges {c, perm[c]} until perm[c] >= crit, or a cycle is found. */ 1402 c = perm[i]; 1403 while( c < crit ) 1404 { 1405 /* c < crit, so edge {c, invperm[c]} exists. Label c as part of component of i */ 1406 1407 /* Stop if we find a cycle. */ 1408 if ( entrycomponent[c] != c ) 1409 break; 1410 1411 entrycomponent[c] = i; 1412 componentobjective[i] += objective[c]; 1413 /* For next iteration: We do another step back */ 1414 c = perm[c]; 1415 } 1416 } 1417 1418 /* Now fill the objective vector. 1419 * For the component containing crit, set the value to 1. 1420 * For the component contraining invperm[crit], set the value to 0. 1421 * For the other components, set the value to 1 if the objective sum is positive. 1422 * Otherwise to 0. 1423 */ 1424 for (i = 0; i < nvars; ++i) 1425 { 1426 if ( entrycomponent[i] == entrycomponent[crit] ) 1427 maxsolu[i] = 1; 1428 else if ( entrycomponent[i] == entrycomponent[invperm[crit]] ) 1429 maxsolu[i] = 0; 1430 else if ( SCIPisGT(scip, componentobjective[entrycomponent[i]], 0.0) ) 1431 maxsolu[i] = 1; 1432 else 1433 maxsolu[i] = 0; 1434 } 1435 1436 SCIPfreeBufferArray(scip, &componentobjective); 1437 SCIPfreeBufferArray(scip, &entrycomponent); 1438 1439 return SCIP_OKAY; 1440 } 1441 1442 1443 /** separate symresack cover inequalities 1444 * 1445 * We currently do NOT enter cuts into the pool. 1446 */ 1447 static 1448 SCIP_RETCODE separateSymresackCovers( 1449 SCIP* scip, /**< SCIP pointer */ 1450 SCIP_CONS* cons, /**< constraint */ 1451 const SCIP_CONSDATA* consdata, /**< constraint data */ 1452 SCIP_Real* vals, /**< solution values of variables */ 1453 int* ngen, /**< pointer to store the number of separated covers */ 1454 SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */ 1455 ) 1456 { 1457 SCIP_Real constobjective; 1458 SCIP_Real* sepaobjective; 1459 SCIP_Real maxsoluobj = 0.0; 1460 int* maxsolu; 1461 int* invperm; 1462 int* perm; 1463 int nvars; 1464 int maxcrit; 1465 int i; 1466 1467 *infeasible = FALSE; 1468 *ngen = 0; 1469 1470 assert( scip != NULL ); 1471 assert( consdata != NULL ); 1472 1473 /* we do not have to take care of trivial constraints */ 1474 if ( consdata->nvars < 2 ) 1475 return SCIP_OKAY; 1476 1477 assert( consdata->vars != NULL ); 1478 assert( consdata->perm != NULL ); 1479 assert( consdata->invperm != NULL ); 1480 assert( infeasible != NULL ); 1481 assert( ngen != NULL ); 1482 1483 nvars = consdata->nvars; 1484 perm = consdata->perm; 1485 invperm = consdata->invperm; 1486 1487 /* initialize objective */ 1488 SCIP_CALL( SCIPallocBufferArray(scip, &sepaobjective, nvars) ); 1489 1490 constobjective = 1.0; /* constant part of separation objective */ 1491 for (i = 0; i < nvars; ++i) 1492 { 1493 if ( i < perm[i] ) 1494 sepaobjective[i] = - vals[i]; 1495 else 1496 { 1497 sepaobjective[i] = 1.0 - vals[i]; 1498 constobjective += vals[i] - 1.0; 1499 } 1500 } 1501 1502 /* allocate memory for temporary and global solution */ 1503 SCIP_CALL( SCIPallocBufferArray(scip, &maxsolu, nvars) ); 1504 1505 /* Find critical row of a maximally violated cover */ 1506 SCIP_CALL( maximizeObjectiveSymresackStrict(scip, nvars, sepaobjective, perm, invperm, &maxcrit, &maxsoluobj) ); 1507 assert( maxcrit >= 0 ); 1508 SCIPdebugMsg(scip, "Critical row %d found; Computing maximally violated cover.\n", maxcrit); 1509 SCIP_CALL( maximizeObjectiveSymresackCriticalEntry(scip, nvars, sepaobjective, perm, invperm, maxcrit, maxsolu) ); 1510 1511 /* Add constant to maxsoluobj to get the real objective */ 1512 maxsoluobj += constobjective; 1513 1514 /* Check whether the separation objective is positive, i.e., a violated cover was found. */ 1515 if ( SCIPisEfficacious(scip, maxsoluobj) ) 1516 { 1517 /* Now add the cut. Reuse array maxsolu as coefficient vector for the constraint. */ 1518 SCIP_Real rhs = -1.0; 1519 for (i = 0; i < nvars; ++i) 1520 { 1521 if ( i < perm[i] ) 1522 maxsolu[i] = -maxsolu[i]; 1523 else 1524 { 1525 if ( maxsolu[i] == 0 ) 1526 rhs += 1.0; 1527 maxsolu[i] = 1 - maxsolu[i]; 1528 } 1529 } 1530 1531 /* add cover inequality */ 1532 SCIP_CALL( addSymresackInequality(scip, cons, nvars, consdata->vars, maxsolu, rhs, infeasible) ); 1533 1534 if ( ! *infeasible ) 1535 ++(*ngen); 1536 } 1537 1538 SCIPfreeBufferArrayNull(scip, &maxsolu); 1539 SCIPfreeBufferArrayNull(scip, &sepaobjective); 1540 1541 return SCIP_OKAY; 1542 } 1543 1544 1545 /** check whether solution is feasible for symresacks */ 1546 static 1547 SCIP_RETCODE checkSymresackSolution( 1548 SCIP* scip, /**< SCIP pointer */ 1549 SCIP_CONS* cons, /**< constrained for which we check the solution */ 1550 SCIP_SOL* sol, /**< solution to be checked */ 1551 SCIP_RESULT* result, /**< pointer to store whether we detected infeasibility */ 1552 SCIP_Bool printreason /**< whether reason for infeasibility should be printed */ 1553 ) 1554 { 1555 SCIP_CONSDATA* consdata; 1556 SCIP_VAR** vars; 1557 int* invperm; 1558 int nvars; 1559 int i; 1560 1561 assert( cons != NULL ); 1562 consdata = SCIPconsGetData(cons); 1563 assert( consdata != NULL); 1564 1565 /* we do not have to take care of trivial constraints */ 1566 if ( consdata->nvars < 2 ) 1567 return SCIP_OKAY; 1568 1569 assert( consdata->vars != NULL ); 1570 assert( consdata->invperm != NULL ); 1571 1572 SCIPdebugMsg(scip, "Check method for symresack constraint <%s> (%d rows) ...\n", SCIPconsGetName(cons), consdata->nvars); 1573 1574 nvars = consdata->nvars; 1575 vars = consdata->vars; 1576 invperm = consdata->invperm; 1577 1578 /* detect first non-constant pair of variables */ 1579 for (i = 0; i < nvars; ++i) 1580 { 1581 SCIP_Real solval; 1582 int val1; 1583 int val2; 1584 1585 /* there are no fixed points */ 1586 assert( invperm[i] != i ); 1587 1588 /* get value of variable i and its inverse */ 1589 solval = SCIPgetSolVal(scip, sol, vars[i]); 1590 assert( SCIPisFeasIntegral(scip, solval) ); 1591 if ( solval > 0.5 ) 1592 val1 = 1; 1593 else 1594 val1 = 0; 1595 1596 solval = SCIPgetSolVal(scip, sol, vars[invperm[i]]); 1597 assert( SCIPisFeasIntegral(scip, solval) ); 1598 if ( solval > 0.5 ) 1599 val2 = 1; 1600 else 1601 val2 = 0; 1602 1603 /* if we detected a constant pair */ 1604 if ( val1 == val2 ) 1605 continue; 1606 /* pair is (1,0) --> lexicographically maximal */ 1607 else if ( val1 > val2 ) 1608 break; 1609 1610 /* pair is (0,1) --> solution is infeasible */ 1611 assert( val2 > val1 ); 1612 SCIPdebugMsg(scip, "Solution is infeasible.\n"); 1613 *result = SCIP_INFEASIBLE; 1614 1615 if ( printreason ) 1616 SCIPinfoMessage(scip, NULL, "First non-constant pair (%d, %d) of variables has pattern (0,1).\n", i, invperm[i]); 1617 1618 break; 1619 } 1620 1621 return SCIP_OKAY; 1622 } 1623 1624 1625 /** Upgrade symresack constraints to orbisacks */ 1626 static 1627 SCIP_RETCODE orbisackUpgrade( 1628 SCIP* scip, /**< SCIP pointer */ 1629 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 1630 const char* name, /**< name of constraint */ 1631 int* perm, /**< permutation */ 1632 SCIP_VAR** inputvars, /**< permuted variables array */ 1633 int nvars, /**< size of perm array */ 1634 SCIP_Bool* upgrade, /**< whether constraint was upgraded */ 1635 SCIP_Bool ismodelcons, /**< whether the symresack is a model constraint */ 1636 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? 1637 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */ 1638 SCIP_Bool separate, /**< should the constraint be separated during LP processing? 1639 * Usually set to TRUE. */ 1640 SCIP_Bool enforce, /**< should the constraint be enforced during node processing? 1641 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 1642 SCIP_Bool check, /**< should the constraint be checked for feasibility? 1643 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 1644 SCIP_Bool propagate, /**< should the constraint be propagated during node processing? 1645 * Usually set to TRUE. */ 1646 SCIP_Bool local, /**< is constraint only valid locally? 1647 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */ 1648 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? 1649 * Usually set to FALSE. In column generation applications, set to TRUE if pricing 1650 * adds coefficients to this constraint. */ 1651 SCIP_Bool dynamic, /**< is constraint subject to aging? 1652 * Usually set to FALSE. Set to TRUE for own cuts which 1653 * are separated as constraints. */ 1654 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? 1655 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */ 1656 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even 1657 * if it may be moved to a more global node? 1658 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */ 1659 ) 1660 { 1661 SCIP_CONSHDLR* conshdlr; 1662 SCIP_VAR** vars1; 1663 SCIP_VAR** vars2; 1664 int nrows = 0; 1665 int i; 1666 1667 assert( scip != NULL ); 1668 assert( perm != NULL ); 1669 assert( nvars > 0 ); 1670 assert( inputvars != NULL ); 1671 assert( upgrade != NULL ); 1672 1673 *upgrade = TRUE; 1674 1675 /* check whether orbisack conshdlr is available */ 1676 conshdlr = SCIPfindConshdlr(scip, "orbisack"); 1677 if ( conshdlr == NULL ) 1678 { 1679 *upgrade = FALSE; 1680 SCIPdebugMsg(scip, "Cannot check whether symresack constraint can be upgraded to orbisack constraint. "); 1681 SCIPdebugMsg(scip, "---> Orbisack constraint handler not found.\n"); 1682 1683 return SCIP_OKAY; 1684 } 1685 1686 SCIP_CALL( SCIPallocBufferArray(scip, &vars1, nvars) ); 1687 SCIP_CALL( SCIPallocBufferArray(scip, &vars2, nvars) ); 1688 1689 /* check whether permutation is a composition of 2-cycles */ 1690 for (i = 0; i < nvars; ++i) 1691 { 1692 /* ignore non-binary variables */ 1693 if ( ! SCIPvarIsBinary(inputvars[i]) ) 1694 continue; 1695 1696 if ( perm[perm[i]] != i ) 1697 { 1698 *upgrade = FALSE; 1699 break; 1700 } 1701 1702 if ( perm[i] > i ) 1703 { 1704 vars1[nrows] = inputvars[i]; 1705 vars2[nrows++] = inputvars[perm[i]]; 1706 1707 assert( nrows <= nvars ); 1708 } 1709 } 1710 1711 /* if permutation can be upgraded to an orbisack */ 1712 if ( nrows == 0 ) 1713 *upgrade = FALSE; 1714 else if ( *upgrade ) 1715 { 1716 SCIP_CALL( SCIPcreateConsOrbisack(scip, cons, name, vars1, vars2, nrows, FALSE, FALSE, ismodelcons, 1717 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) ); 1718 } 1719 1720 SCIPfreeBufferArray(scip, &vars2); 1721 SCIPfreeBufferArray(scip, &vars1); 1722 1723 return SCIP_OKAY; 1724 } 1725 1726 1727 /** creates a symmetry breaking constraint 1728 * 1729 * Depending on the given permutation, either an orbisack or symresack constraint 1730 * is created. 1731 */ 1732 SCIP_RETCODE SCIPcreateSymbreakCons( 1733 SCIP* scip, /**< SCIP data structure */ 1734 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 1735 const char* name, /**< name of constraint */ 1736 int* perm, /**< permutation */ 1737 SCIP_VAR** vars, /**< variables */ 1738 int nvars, /**< number of variables in vars array */ 1739 SCIP_Bool ismodelcons, /**< whether the added constraint is a model constraint */ 1740 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? 1741 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */ 1742 SCIP_Bool separate, /**< should the constraint be separated during LP processing? 1743 * Usually set to TRUE. */ 1744 SCIP_Bool enforce, /**< should the constraint be enforced during node processing? 1745 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 1746 SCIP_Bool check, /**< should the constraint be checked for feasibility? 1747 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 1748 SCIP_Bool propagate, /**< should the constraint be propagated during node processing? 1749 * Usually set to TRUE. */ 1750 SCIP_Bool local, /**< is constraint only valid locally? 1751 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */ 1752 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? 1753 * Usually set to FALSE. In column generation applications, set to TRUE if pricing 1754 * adds coefficients to this constraint. */ 1755 SCIP_Bool dynamic, /**< is constraint subject to aging? 1756 * Usually set to FALSE. Set to TRUE for own cuts which 1757 * are separated as constraints. */ 1758 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? 1759 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */ 1760 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even 1761 * if it may be moved to a more global node? 1762 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */ 1763 ) 1764 { 1765 SCIP_Bool upgrade = FALSE; 1766 1767 assert( scip != NULL ); 1768 assert( cons != NULL ); 1769 assert( perm != NULL ); 1770 assert( vars != NULL ); 1771 assert( nvars > 0 ); 1772 1773 SCIP_CALL( orbisackUpgrade(scip, cons, name, perm, vars, nvars, &upgrade, ismodelcons, 1774 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) ); 1775 1776 if ( ! upgrade ) 1777 { 1778 SCIP_CALL( SCIPcreateConsSymresack(scip, cons, name, perm, vars, nvars, ismodelcons, 1779 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) ); 1780 } 1781 1782 return SCIP_OKAY; 1783 } 1784 1785 1786 /*-------------------------------------------------------------------------------------------- 1787 *--------------------------------- SCIP functions ------------------------------------------- 1788 *--------------------------------------------------------------------------------------------*/ 1789 1790 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 1791 static 1792 SCIP_DECL_CONSHDLRCOPY(conshdlrCopySymresack) 1793 { /*lint --e{715}*/ 1794 assert(scip != NULL); 1795 assert(conshdlr != NULL); 1796 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 1797 1798 /* call inclusion method of constraint handler */ 1799 SCIP_CALL( SCIPincludeConshdlrSymresack(scip) ); 1800 1801 *valid = TRUE; 1802 1803 return SCIP_OKAY; 1804 } 1805 1806 1807 /** frees specific constraint data */ 1808 static 1809 SCIP_DECL_CONSDELETE(consDeleteSymresack) 1810 { /*lint --e{715}*/ 1811 assert( scip != NULL ); 1812 assert( conshdlr != NULL ); 1813 assert( consdata != NULL ); 1814 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1815 1816 SCIP_CALL( consdataFree(scip, consdata) ); 1817 1818 return SCIP_OKAY; 1819 } 1820 1821 1822 /** frees constraint handler */ 1823 static 1824 SCIP_DECL_CONSFREE(consFreeSymresack) 1825 { /*lint --e{715}*/ 1826 SCIP_CONSHDLRDATA* conshdlrdata; 1827 1828 assert( scip != NULL ); 1829 assert( conshdlr != NULL ); 1830 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1831 1832 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1833 assert( conshdlrdata != NULL ); 1834 1835 SCIPfreeBlockMemory(scip, &conshdlrdata); 1836 1837 return SCIP_OKAY; 1838 } 1839 1840 1841 /** transforms constraint data into data belonging to the transformed problem */ 1842 static 1843 SCIP_DECL_CONSTRANS(consTransSymresack) 1844 { 1845 SCIP_CONSDATA* sourcedata; 1846 SCIP_CONSDATA* consdata = NULL; 1847 int nvars; 1848 int i; 1849 1850 assert( scip != NULL ); 1851 assert( conshdlr != NULL ); 1852 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1853 assert( sourcecons != NULL ); 1854 assert( targetcons != NULL ); 1855 1856 SCIPdebugMsg(scip, "Transforming constraint.\n"); 1857 1858 /* get data of original constraint */ 1859 sourcedata = SCIPconsGetData(sourcecons); 1860 assert( sourcedata != NULL); 1861 1862 /* constraint might be empty and not deleted if no presolving took place */ 1863 assert( sourcedata->nvars == 0 || sourcedata->vars != NULL ); 1864 assert( sourcedata->nvars == 0 || sourcedata->perm != NULL ); 1865 assert( sourcedata->nvars == 0 || sourcedata->invperm != NULL ); 1866 #ifndef NDEBUG 1867 if ( sourcedata->ppupgrade ) 1868 { 1869 assert( sourcedata->nvars > 0 ); 1870 assert( sourcedata->ncycles != 0 ); 1871 assert( sourcedata->cycledecomposition != NULL ); 1872 for (i = 0; i < sourcedata->ncycles; ++i) 1873 { 1874 assert( sourcedata->cycledecomposition[i] != NULL ); 1875 assert( sourcedata->cycledecomposition[i][0] != 0 ); 1876 } 1877 } 1878 #endif 1879 1880 /* create transformed constraint data 1881 * 1882 * do NOT call consdataCreate() again to avoid doing the packing-upgrade check twice 1883 */ 1884 nvars = sourcedata->nvars; 1885 1886 SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) ); 1887 1888 consdata->vars = NULL; 1889 consdata->nvars = nvars; 1890 consdata->perm = NULL; 1891 consdata->invperm = NULL; 1892 consdata->ppupgrade = sourcedata->ppupgrade; 1893 consdata->ismodelcons = sourcedata->ismodelcons; 1894 #ifdef SCIP_DEBUG 1895 consdata->debugcnt = 0; 1896 #endif 1897 consdata->ncycles = 0; 1898 consdata->cycledecomposition = NULL; 1899 consdata->ndescentpoints = 0; 1900 consdata->descentpoints = NULL; 1901 1902 if ( nvars > 0 ) 1903 { 1904 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->vars, nvars) ); 1905 SCIP_CALL( SCIPgetTransformedVars(scip, nvars, sourcedata->vars, consdata->vars) ); 1906 for (i = 0; i < nvars; ++i) 1907 { 1908 SCIP_CALL( SCIPcaptureVar(scip, consdata->vars[i]) ); 1909 } 1910 1911 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->perm, sourcedata->perm, nvars) ); 1912 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->invperm, sourcedata->invperm, nvars) ); 1913 1914 if ( sourcedata->ppupgrade ) 1915 { 1916 consdata->ncycles = sourcedata->ncycles; 1917 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->cycledecomposition, sourcedata->cycledecomposition, sourcedata->ncycles) ); 1918 for (i = 0; i < sourcedata->ncycles; ++i) 1919 { 1920 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->cycledecomposition[i], sourcedata->cycledecomposition[i], nvars + 1) ); /*lint !e866*/ 1921 } 1922 1923 consdata->ndescentpoints = sourcedata->ndescentpoints; 1924 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->descentpoints, sourcedata->descentpoints, sourcedata->ndescentpoints) ); 1925 } 1926 1927 /* Make sure that all variables cannot be multiaggregated (this cannot be handled by cons_symresack, since one cannot 1928 * easily eliminate single variables from a symresack constraint). 1929 * 1930 * We need to call this again to ensure that multiaggregation is forbidden also if the constraint was part 1931 * of the original problem. 1932 */ 1933 for (i = 0; i < sourcedata->nvars; ++i) 1934 { 1935 SCIP_CALL( SCIPgetTransformedVar(scip, consdata->vars[i], &consdata->vars[i]) ); 1936 SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, consdata->vars[i]) ); 1937 } 1938 } 1939 1940 /* create transformed constraint */ 1941 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, consdata, 1942 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), 1943 SCIPconsIsEnforced(sourcecons), SCIPconsIsChecked(sourcecons), 1944 SCIPconsIsPropagated(sourcecons), SCIPconsIsLocal(sourcecons), 1945 SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons), 1946 SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) ); 1947 1948 return SCIP_OKAY; 1949 } 1950 1951 1952 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */ 1953 static 1954 SCIP_DECL_CONSINITLP(consInitlpSymresack) 1955 { 1956 int c; 1957 SCIP_CONSHDLRDATA* conshdlrdata; 1958 1959 assert( infeasible != NULL ); 1960 *infeasible = FALSE; 1961 1962 assert( scip != NULL ); 1963 assert( conshdlr != NULL ); 1964 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1965 1966 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1967 assert( conshdlrdata != NULL ); 1968 1969 /* loop through constraints */ 1970 for (c = 0; c < nconss; ++c) 1971 { 1972 assert( conss[c] != NULL ); 1973 1974 SCIPdebugMsg(scip, "Generating initial symresack cut for constraint <%s> ...\n", SCIPconsGetName(conss[c])); 1975 1976 SCIP_CALL( initLP(scip, conss[c], conshdlrdata->checkmonotonicity, infeasible) ); 1977 if ( *infeasible ) 1978 break; 1979 } 1980 SCIPdebugMsg(scip, "Generated initial symresack cuts.\n"); 1981 1982 return SCIP_OKAY; 1983 } 1984 1985 1986 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */ 1987 static 1988 SCIP_DECL_CONSINITSOL(consInitsolSymresack) 1989 { 1990 SCIP_CONSHDLRDATA* conshdlrdata; 1991 int c; 1992 1993 assert( scip != NULL ); 1994 assert( conshdlr != NULL ); 1995 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1996 1997 /* determine maximum number of vars in a symresack constraint */ 1998 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1999 assert( conshdlrdata != NULL ); 2000 2001 conshdlrdata->maxnvars = 0; 2002 2003 /* loop through constraints */ 2004 for (c = 0; c < nconss; ++c) 2005 { 2006 SCIP_CONSDATA* consdata; 2007 2008 assert( conss[c] != NULL ); 2009 2010 consdata = SCIPconsGetData(conss[c]); 2011 assert( consdata != NULL ); 2012 2013 /* update conshdlrdata if necessary */ 2014 if ( consdata->nvars > conshdlrdata->maxnvars ) 2015 conshdlrdata->maxnvars = consdata->nvars; 2016 } 2017 2018 return SCIP_OKAY; 2019 } 2020 2021 2022 /** separation method of constraint handler for LP solution */ 2023 static 2024 SCIP_DECL_CONSSEPALP(consSepalpSymresack) 2025 { /*lint --e{715}*/ 2026 SCIP_CONSHDLRDATA* conshdlrdata; 2027 SCIP_CONSDATA* consdata; 2028 SCIP_Real* vals; 2029 int maxnvars; 2030 int c; 2031 2032 assert( scip != NULL ); 2033 assert( conshdlr != NULL ); 2034 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 2035 assert( result != NULL ); 2036 2037 SCIPdebugMsg(scip, "Separation method for symresack constraints\n"); 2038 2039 *result = SCIP_DIDNOTRUN; 2040 2041 /* if solution is not integer */ 2042 if ( SCIPgetNLPBranchCands(scip) == 0 ) 2043 return SCIP_OKAY; 2044 2045 if ( nconss == 0 ) 2046 return SCIP_OKAY; 2047 2048 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2049 assert( conshdlrdata != NULL ); 2050 2051 maxnvars = conshdlrdata->maxnvars; 2052 assert( maxnvars > 0 ); 2053 2054 SCIP_CALL( SCIPallocBufferArray(scip, &vals, maxnvars) ); 2055 2056 /* loop through constraints */ 2057 for (c = 0; c < nconss; ++c) 2058 { 2059 SCIP_Bool infeasible = FALSE; 2060 int ngen = 0; 2061 2062 SCIPdebugMsg(scip, "Separating symresack constraint <%s> ...\n", SCIPconsGetName(conss[c])); 2063 2064 /* get data of constraint */ 2065 assert( conss[c] != NULL ); 2066 consdata = SCIPconsGetData(conss[c]); 2067 2068 if ( consdata->nvars == 0 ) 2069 continue; 2070 2071 /* get solution */ 2072 assert( consdata->nvars <= maxnvars ); 2073 SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nvars, consdata->vars, vals) ); 2074 SCIP_CALL( separateSymresackCovers(scip, conss[c], consdata, vals, &ngen, &infeasible) ); 2075 2076 if ( infeasible ) 2077 { 2078 *result = SCIP_CUTOFF; 2079 SCIPfreeBufferArray(scip, &vals); 2080 2081 return SCIP_OKAY; 2082 } 2083 2084 if ( ngen > 0 ) 2085 *result = SCIP_SEPARATED; 2086 2087 if ( *result == SCIP_DIDNOTRUN ) 2088 *result = SCIP_DIDNOTFIND; 2089 } 2090 SCIPfreeBufferArray(scip, &vals); 2091 2092 return SCIP_OKAY; 2093 } 2094 2095 2096 /** separation method of constraint handler for arbitrary primal solution */ 2097 static 2098 SCIP_DECL_CONSSEPASOL(consSepasolSymresack) 2099 { /*lint --e{715}*/ 2100 SCIP_CONSHDLRDATA* conshdlrdata; 2101 SCIP_CONSDATA* consdata; 2102 SCIP_Real* vals; 2103 int maxnvars; 2104 int c; 2105 2106 assert( scip != NULL ); 2107 assert( conshdlr != NULL ); 2108 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 2109 assert( result != NULL ); 2110 2111 SCIPdebugMsg(scip, "Separation method for symresack constraints\n"); 2112 2113 *result = SCIP_DIDNOTRUN; 2114 2115 if ( nconss == 0 ) 2116 return SCIP_OKAY; 2117 2118 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2119 assert( conshdlrdata != NULL ); 2120 2121 maxnvars = conshdlrdata->maxnvars; 2122 assert( maxnvars > 0 ); 2123 2124 SCIP_CALL( SCIPallocBufferArray(scip, &vals, maxnvars) ); 2125 2126 /* loop through constraints */ 2127 for (c = 0; c < nconss; ++c) 2128 { 2129 SCIP_Bool infeasible = FALSE; 2130 int ngen = 0; 2131 2132 SCIPdebugMsg(scip, "Separating symresack constraint <%s> ...\n", SCIPconsGetName(conss[c])); 2133 2134 /* get data of constraint */ 2135 assert( conss[c] != NULL ); 2136 consdata = SCIPconsGetData(conss[c]); 2137 2138 if ( consdata->nvars == 0 ) 2139 continue; 2140 2141 /* get solution */ 2142 assert( consdata->nvars <= maxnvars ); 2143 SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nvars, consdata->vars, vals) ); 2144 SCIP_CALL( separateSymresackCovers(scip, conss[c], consdata, vals, &ngen, &infeasible) ); 2145 2146 if ( infeasible ) 2147 { 2148 *result = SCIP_CUTOFF; 2149 SCIPfreeBufferArray(scip, &vals); 2150 2151 return SCIP_OKAY; 2152 } 2153 2154 if ( ngen > 0 ) 2155 *result = SCIP_SEPARATED; 2156 2157 if ( *result == SCIP_DIDNOTRUN ) 2158 *result = SCIP_DIDNOTFIND; 2159 } 2160 SCIPfreeBufferArray(scip, &vals); 2161 2162 return SCIP_OKAY; 2163 } 2164 2165 2166 /** constraint enforcing method of constraint handler for LP solutions. 2167 * 2168 * To check feasibility, we separate cover inequalities. 2169 * 2170 * @pre It is assumed that the solution is integral (this can be ensured by appropriate priorities). 2171 */ 2172 static 2173 SCIP_DECL_CONSENFOLP(consEnfolpSymresack) 2174 { /*lint --e{715}*/ 2175 SCIP_CONSDATA* consdata; 2176 int c; 2177 2178 assert( scip != NULL ); 2179 assert( conshdlr != NULL ); 2180 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 2181 assert( result != NULL ); 2182 2183 SCIPdebugMsg(scip, "Enforcing method for symresack constraints (lp solutions) ...\n"); 2184 2185 /* we have a negative priority, so we should come after the integrality conshdlr. */ 2186 assert( SCIPgetNLPBranchCands(scip) == 0 ); 2187 2188 *result = SCIP_FEASIBLE; 2189 2190 if ( nconss > 0 ) 2191 { 2192 SCIP_CONSHDLRDATA* conshdlrdata; 2193 SCIP_Real* vals; 2194 int maxnvars; 2195 2196 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2197 assert( conshdlrdata != NULL ); 2198 2199 maxnvars = conshdlrdata->maxnvars; 2200 assert( maxnvars > 0 ); 2201 2202 SCIP_CALL( SCIPallocBufferArray(scip, &vals, maxnvars) ); 2203 2204 /* loop through constraints */ 2205 for (c = 0; c < nconss; ++c) 2206 { 2207 SCIP_Bool infeasible = FALSE; 2208 int ngen = 0; 2209 2210 SCIPdebugMsg(scip, "Enforcing symresack constraint <%s> ...\n", SCIPconsGetName(conss[c])); 2211 2212 /* get data of constraint */ 2213 assert( conss[c] != NULL ); 2214 consdata = SCIPconsGetData(conss[c]); 2215 assert( consdata != NULL ); 2216 2217 /* do not enforce non-model constraints */ 2218 if ( !consdata->ismodelcons ) 2219 continue; 2220 2221 if ( consdata->nvars == 0 ) 2222 continue; 2223 2224 /* get solution */ 2225 assert( consdata->nvars <= maxnvars ); 2226 SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nvars, consdata->vars, vals) ); 2227 SCIP_CALL( separateSymresackCovers(scip, conss[c], consdata, vals, &ngen, &infeasible) ); 2228 2229 if ( infeasible ) 2230 { 2231 *result = SCIP_CUTOFF; 2232 SCIPfreeBufferArray(scip, &vals); 2233 2234 return SCIP_OKAY; 2235 } 2236 2237 /* SCIPdebugMsg(scip, "Generated symresack inequalities for <%s>: %d\n", SCIPconsGetName(conss[c]), ngen); */ 2238 2239 if ( ngen > 0 ) 2240 *result = SCIP_SEPARATED; 2241 } 2242 SCIPfreeBufferArray(scip, &vals); 2243 } 2244 2245 return SCIP_OKAY; 2246 } 2247 2248 2249 /** constraint enforcing method of constraint handler for pseudo solutions */ 2250 static 2251 SCIP_DECL_CONSENFOPS(consEnfopsSymresack) 2252 { /*lint --e{715}*/ 2253 SCIP_CONSDATA* consdata; 2254 int c; 2255 2256 assert( scip != NULL ); 2257 assert( conshdlr != NULL ); 2258 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 2259 assert( result != NULL ); 2260 2261 SCIPdebugMsg(scip, "Enforcing method for symresack constraints (pseudo solutions) ...\n"); 2262 2263 *result = SCIP_FEASIBLE; 2264 2265 if ( objinfeasible || solinfeasible ) 2266 return SCIP_OKAY; 2267 2268 /* loop through constraints */ 2269 for (c = 0; c < nconss; ++c) 2270 { 2271 consdata = SCIPconsGetData(conss[c]); 2272 assert( consdata != NULL ); 2273 2274 /* do not enforce non-model constraints */ 2275 if ( !consdata->ismodelcons ) 2276 continue; 2277 2278 SCIP_CALL( checkSymresackSolution(scip, conss[c], NULL, result, FALSE) ); 2279 2280 if ( *result == SCIP_INFEASIBLE ) 2281 break; 2282 } 2283 2284 return SCIP_OKAY; 2285 } 2286 2287 2288 /** constraint enforcing method of constraint handler for relaxation solutions 2289 * 2290 * To check feasibility, we separate cover inequalities. 2291 * 2292 */ 2293 static 2294 SCIP_DECL_CONSENFORELAX(consEnforelaxSymresack) 2295 { /*lint --e{715}*/ 2296 SCIP_CONSDATA* consdata; 2297 int c; 2298 2299 assert( scip != NULL ); 2300 assert( conshdlr != NULL ); 2301 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 2302 assert( result != NULL ); 2303 2304 SCIPdebugMsg(scip, "Enforcing method for symresack constraints (relaxation solutions) ...\n"); 2305 2306 /* we have a negative priority, so we should come after the integrality conshdlr. */ 2307 assert( SCIPgetNLPBranchCands(scip) == 0 ); 2308 2309 *result = SCIP_FEASIBLE; 2310 2311 if ( nconss > 0 ) 2312 { 2313 SCIP_CONSHDLRDATA* conshdlrdata; 2314 SCIP_Real* vals; 2315 int maxnvars; 2316 2317 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2318 assert( conshdlrdata != NULL ); 2319 2320 maxnvars = conshdlrdata->maxnvars; 2321 assert( maxnvars > 0 ); 2322 2323 SCIP_CALL( SCIPallocBufferArray(scip, &vals, maxnvars) ); 2324 2325 /* loop through constraints */ 2326 for (c = 0; c < nconss; ++c) 2327 { 2328 SCIP_Bool infeasible = FALSE; 2329 int ngen = 0; 2330 2331 SCIPdebugMsg(scip, "Enforcing symresack constraint <%s> ...\n", SCIPconsGetName(conss[c])); 2332 2333 /* get data of constraint */ 2334 assert( conss[c] != NULL ); 2335 consdata = SCIPconsGetData(conss[c]); 2336 assert( consdata != NULL ); 2337 2338 /* do not enforce non-model constraints */ 2339 if ( !consdata->ismodelcons ) 2340 continue; 2341 2342 if ( consdata->nvars == 0 ) 2343 continue; 2344 2345 /* get solution */ 2346 assert( consdata->nvars <= maxnvars ); 2347 SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nvars, consdata->vars, vals) ); 2348 SCIP_CALL( separateSymresackCovers(scip, conss[c], consdata, vals, &ngen, &infeasible) ); 2349 2350 if ( infeasible ) 2351 { 2352 *result = SCIP_CUTOFF; 2353 SCIPfreeBufferArray(scip, &vals); 2354 2355 return SCIP_OKAY; 2356 } 2357 2358 if ( ngen > 0 ) 2359 *result = SCIP_SEPARATED; 2360 } 2361 SCIPfreeBufferArray(scip, &vals); 2362 } 2363 2364 return SCIP_OKAY; 2365 } 2366 2367 2368 /** feasibility check method of constraint handler for integral solutions */ 2369 static 2370 SCIP_DECL_CONSCHECK(consCheckSymresack) 2371 { /*lint --e{715}*/ 2372 SCIP_CONSDATA* consdata; 2373 int c; 2374 2375 assert( scip != NULL ); 2376 assert( conshdlr != NULL ); 2377 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 2378 assert( result != NULL ); 2379 2380 *result = SCIP_FEASIBLE; 2381 2382 /* loop through constraints */ 2383 for (c = 0; c < nconss; ++c) 2384 { 2385 consdata = SCIPconsGetData(conss[c]); 2386 assert( consdata != NULL ); 2387 2388 /* do not check non-model constraints */ 2389 if ( !consdata->ismodelcons ) 2390 continue; 2391 2392 SCIP_CALL( checkSymresackSolution(scip, conss[c], sol, result, printreason) ); 2393 2394 if ( *result == SCIP_INFEASIBLE ) 2395 break; 2396 } 2397 2398 if ( *result == SCIP_FEASIBLE ) 2399 SCIPdebugMsg(scip, "Solution is feasible.\n"); 2400 2401 return SCIP_OKAY; 2402 } 2403 2404 2405 /** domain propagation method of constraint handler */ 2406 static 2407 SCIP_DECL_CONSPROP(consPropSymresack) 2408 { /*lint --e{715}*/ 2409 int c; 2410 SCIP_Bool success = FALSE; 2411 2412 assert( scip != NULL ); 2413 assert( conshdlr != NULL ); 2414 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 2415 assert( result != NULL ); 2416 2417 *result = SCIP_DIDNOTRUN; 2418 2419 SCIPdebugMsg(scip, "Propagation method of symresack constraint handler.\n"); 2420 2421 /* loop through constraints */ 2422 for (c = 0; c < nconss; ++c) 2423 { 2424 SCIP_Bool infeasible = FALSE; 2425 int ngen = 0; 2426 2427 assert( conss[c] != NULL ); 2428 2429 SCIP_CALL( propVariables(scip, conss[c], &infeasible, &ngen) ); 2430 2431 if ( infeasible ) 2432 { 2433 *result = SCIP_CUTOFF; 2434 return SCIP_OKAY; 2435 } 2436 2437 success = success || ( ngen > 0 ); 2438 2439 *result = SCIP_DIDNOTFIND; 2440 } 2441 2442 if ( success ) 2443 { 2444 *result = SCIP_REDUCEDDOM; 2445 return SCIP_OKAY; 2446 } 2447 2448 return SCIP_OKAY; 2449 } 2450 2451 2452 /** presolving method of constraint handler */ 2453 static 2454 SCIP_DECL_CONSPRESOL(consPresolSymresack) 2455 { /*lint --e{715}*/ 2456 int c; 2457 SCIP_Bool success = FALSE; 2458 int oldndelconss; 2459 2460 assert( scip != NULL ); 2461 assert( conshdlr != NULL ); 2462 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 2463 assert( result != NULL ); 2464 2465 oldndelconss = *ndelconss; 2466 2467 SCIPdebugMsg(scip, "Presolving method of symresack constraint handler. Propagating symresack inequalities.\n"); 2468 *result = SCIP_DIDNOTRUN; 2469 2470 /* loop through constraints */ 2471 for (c = 0; c < nconss; ++c) 2472 { 2473 SCIP_Bool infeasible = FALSE; 2474 SCIP_CONSDATA* consdata; 2475 int ngen = 0; 2476 2477 assert( conss[c] != NULL ); 2478 2479 consdata = SCIPconsGetData(conss[c]); 2480 assert( consdata != NULL ); 2481 2482 /* avoid trivial problems */ 2483 if ( consdata->nvars == 0 ) 2484 { 2485 SCIP_CALL( SCIPdelCons(scip, conss[c]) ); 2486 (*ndelconss)++; 2487 } 2488 else 2489 { 2490 SCIP_CALL( propVariables(scip, conss[c], &infeasible, &ngen) ); 2491 } 2492 2493 if ( infeasible ) 2494 { 2495 *result = SCIP_CUTOFF; 2496 break; 2497 } 2498 2499 if ( ngen > 0 ) 2500 { 2501 *nfixedvars += ngen; 2502 success = TRUE; 2503 } 2504 2505 *result = SCIP_DIDNOTFIND; 2506 } 2507 2508 if ( *ndelconss > oldndelconss || success ) 2509 *result = SCIP_SUCCESS; 2510 2511 return SCIP_OKAY; 2512 } 2513 2514 2515 /** Propagation resolution for conflict analysis */ 2516 static 2517 SCIP_DECL_CONSRESPROP(consRespropSymresack) 2518 { /*lint --e{715}*/ 2519 SCIP_CONSDATA* consdata; 2520 SCIP_VAR** vars; 2521 int* perm; 2522 int* invperm; 2523 int nvars; 2524 int i; 2525 int varrow; 2526 int infrow; 2527 2528 assert( scip != NULL ); 2529 assert( conshdlr != NULL ); 2530 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 2531 assert( cons != NULL ); 2532 assert( infervar != NULL ); 2533 assert( bdchgidx != NULL ); 2534 assert( result != NULL ); 2535 2536 SCIPdebugMsg(scip, "Propagation resolution method of symresack constraint handler.\n"); 2537 2538 *result = SCIP_DIDNOTFIND; 2539 2540 consdata = SCIPconsGetData(cons); 2541 assert( consdata != NULL ); 2542 2543 /* we do not have to take care of trivial constraints */ 2544 if ( consdata->nvars < 2 ) 2545 return SCIP_OKAY; 2546 2547 assert( consdata->vars != NULL ); 2548 assert( consdata->invperm != NULL ); 2549 2550 vars = consdata->vars; 2551 nvars = consdata->nvars; 2552 perm = consdata->perm; 2553 invperm = consdata->invperm; 2554 2555 /* inferinfo == varrow + infrow * nvars. 2556 * infrow is 0 if the fixing is not caused by a lookahead. 2557 */ 2558 varrow = inferinfo % nvars; 2559 infrow = inferinfo / nvars; 2560 2561 assert( varrow >= 0 ); 2562 assert( varrow < nvars ); 2563 assert( infrow >= 0 ); 2564 assert( infrow < nvars ); 2565 assert( vars[varrow] == infervar || vars[invperm[varrow]] == infervar ); 2566 2567 /* Up to entry varrow the vectors x and perm[x] are equal. */ 2568 for (i = 0; i < varrow; ++i) 2569 { 2570 /* Conflict caused by bounds of x[i] and perm(x)[i] = x[invperm[i]]. */ 2571 2572 /* No fixed points in the permutation. */ 2573 assert( i != invperm[i] ); 2574 2575 /* Up to entry varrow the vectors x and perm[x] are fixed to the same value. */ 2576 assert( ISFIXED(vars[i], bdchgidx) ); 2577 assert( ISFIXED(vars[invperm[i]], bdchgidx) ); 2578 assert( REALABS(SCIPvarGetUbAtIndex(vars[i], bdchgidx, FALSE) - 2579 SCIPvarGetUbAtIndex(vars[invperm[i]], bdchgidx, FALSE)) < 0.5 ); 2580 assert( REALABS(SCIPvarGetLbAtIndex(vars[i], bdchgidx, FALSE) - 2581 SCIPvarGetLbAtIndex(vars[invperm[i]], bdchgidx, FALSE)) < 0.5 ); 2582 2583 /* At iteration i the vars x[i] and x[invperm[i]] are fixed. 2584 * So only new information is received if i < perm[i] (i.e. there is no j < i with j = invperm[i]) 2585 * Or if invperm[i] > i. 2586 */ 2587 if ( i < perm[i] ) 2588 { 2589 assert( vars[i] != infervar ); 2590 SCIP_CALL( SCIPaddConflictUb(scip, vars[i], bdchgidx) ); 2591 SCIP_CALL( SCIPaddConflictLb(scip, vars[i], bdchgidx) ); 2592 } 2593 if ( invperm[i] > i ) 2594 { 2595 assert( vars[invperm[i]] != infervar ); 2596 SCIP_CALL( SCIPaddConflictUb(scip, vars[invperm[i]], bdchgidx) ); 2597 SCIP_CALL( SCIPaddConflictLb(scip, vars[invperm[i]], bdchgidx) ); 2598 } 2599 } 2600 2601 /* Case distinction: Fixing due to propagation or due to lookahead */ 2602 if ( infrow > 0 ) 2603 { 2604 /* The fixing of infervar is caused by a lookahead (checkFeasible) 2605 * Up to row "varrow" the entries x[i] and perm(x)[i] are forced to be equal 2606 * If x[varrow] = perm(x)[varrow] is assumed, then until infrow we find x[i] = perm(x)[i] ( = x[invperm[i]] ) 2607 * and (x[infrow], perm(x)[infrow]) = (0, 1). 2608 */ 2609 2610 /* Everything after varrow to infrow is forced to a constant, and row infrow is (0, 1) */ 2611 for (i = varrow + 1; i <= infrow; ++i) 2612 { 2613 /* Conflict caused by bounds of x[i] and perm(x)[i] = x[invperm[i]]. */ 2614 2615 /* No fixed points in the permutation. */ 2616 assert( i != invperm[i] ); 2617 2618 /* The fixing are applied 'virtually', i.e. if varrow is considered constant, then fixings will follow. 2619 * Thus, between entries varrow and infrow of vectorx x and gamma(x) the entries do not have to be fixed. 2620 * For conflict analysis, only the fixed entries matter. 2621 */ 2622 if ( ( i < perm[i] || i == invperm[varrow] ) && ISFIXED(vars[i], bdchgidx) ) 2623 { 2624 assert( vars[i] != infervar ); 2625 SCIP_CALL( SCIPaddConflictUb(scip, vars[i], bdchgidx) ); 2626 SCIP_CALL( SCIPaddConflictLb(scip, vars[i], bdchgidx) ); 2627 } 2628 if ( ( invperm[i] > i || invperm[i] == varrow ) && ISFIXED(vars[invperm[i]], bdchgidx) ) 2629 { 2630 assert( vars[invperm[i]] != infervar ); 2631 SCIP_CALL( SCIPaddConflictUb(scip, vars[invperm[i]], bdchgidx) ); 2632 SCIP_CALL( SCIPaddConflictLb(scip, vars[invperm[i]], bdchgidx) ); 2633 } 2634 } 2635 } 2636 else 2637 { 2638 /* This is not a fixing caused by lookahead (checkFeasible), 2639 * so row "varrow" was (0, _) or (_, 1) and for i < varrow x[i] = perm(x)[i]. 2640 */ 2641 if ( boundtype == SCIP_BOUNDTYPE_LOWER ) 2642 { 2643 /* Changed the lower bound of infervar to 1. That means that this fixing is due to (_, 1) */ 2644 assert( infervar == vars[varrow] ); 2645 assert( ISFIXED(vars[invperm[varrow]], bdchgidx) ); 2646 2647 if ( invperm[varrow] > varrow ) 2648 { 2649 SCIP_CALL( SCIPaddConflictUb(scip, vars[invperm[varrow]], bdchgidx) ); 2650 SCIP_CALL( SCIPaddConflictLb(scip, vars[invperm[varrow]], bdchgidx) ); 2651 } 2652 } 2653 else 2654 { 2655 /* Changed the lower bound of infervar to 0. That means that this fixing is due to (0, _) */ 2656 assert( infervar == vars[invperm[varrow]] ); 2657 assert( ISFIXED(vars[varrow], bdchgidx) ); 2658 2659 if ( varrow < perm[varrow] ) 2660 { 2661 SCIP_CALL( SCIPaddConflictUb(scip, vars[varrow], bdchgidx) ); 2662 SCIP_CALL( SCIPaddConflictLb(scip, vars[varrow], bdchgidx) ); 2663 } 2664 } 2665 } 2666 2667 *result = SCIP_SUCCESS; 2668 2669 return SCIP_OKAY; 2670 } 2671 2672 2673 /** lock variables 2674 * 2675 * We assume we have only one global (void) constraint and lock all binary variables 2676 * which do not correspond to fixed points of the permutation. 2677 * 2678 * - Symresack constraints may get violated if the variables with a negative coefficient 2679 * in the FD inequality are rounded down, we therefor call 2680 * SCIPaddVarLocksType(..., nlockspos, nlocksneg). 2681 * - Symresack constraints may get violated if the variables with a positive coefficient 2682 * in the FD inequality are rounded up, we therefor call 2683 * SCIPaddVarLocksType(..., nlocksneg, nlockspo ). 2684 */ 2685 static 2686 SCIP_DECL_CONSLOCK(consLockSymresack) 2687 { /*lint --e{715}*/ 2688 SCIP_CONSDATA* consdata; 2689 SCIP_VAR** vars; 2690 int* perm; 2691 int nvars; 2692 int i; 2693 2694 assert( scip != NULL ); 2695 assert( conshdlr != NULL ); 2696 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 2697 assert( cons != NULL ); 2698 2699 SCIPdebugMsg(scip, "Locking method for symresack constraint handler.\n"); 2700 2701 /* get data of original constraint */ 2702 consdata = SCIPconsGetData(cons); 2703 assert( consdata != NULL ); 2704 2705 /* we do not have to take care of trivial constraints */ 2706 if ( consdata->nvars < 2 ) 2707 return SCIP_OKAY; 2708 2709 assert( consdata->vars != NULL ); 2710 assert( consdata->perm != NULL ); 2711 2712 nvars = consdata->nvars; 2713 vars = consdata->vars; 2714 perm = consdata->perm; 2715 2716 for (i = 0; i < nvars; ++i) 2717 { 2718 /* due to clean-up in consdataCreate, there are no fixed points */ 2719 assert( perm[i] != i ); 2720 2721 if ( perm[i] > i ) 2722 { 2723 SCIP_CALL( SCIPaddVarLocksType(scip, vars[i], locktype, nlockspos, nlocksneg) ); 2724 } 2725 else 2726 { 2727 SCIP_CALL( SCIPaddVarLocksType(scip, vars[i], locktype, nlocksneg, nlockspos) ); 2728 } 2729 } 2730 2731 return SCIP_OKAY; 2732 } 2733 2734 2735 /** constraint copying method of constraint handler */ 2736 static 2737 SCIP_DECL_CONSCOPY(consCopySymresack) 2738 { 2739 SCIP_CONSHDLRDATA* conshdlrdata; 2740 SCIP_CONSDATA* sourcedata; 2741 SCIP_VAR** sourcevars; 2742 SCIP_VAR** vars; 2743 int nvars; 2744 int i; 2745 2746 assert( scip != NULL ); 2747 assert( cons != NULL ); 2748 assert( sourcescip != NULL ); 2749 assert( sourceconshdlr != NULL ); 2750 assert( strcmp(SCIPconshdlrGetName(sourceconshdlr), CONSHDLR_NAME) == 0 ); 2751 assert( sourcecons != NULL ); 2752 assert( varmap != NULL ); 2753 assert( valid != NULL ); 2754 2755 *valid = TRUE; 2756 2757 SCIPdebugMsg(scip, "Copying method for symresack constraint handler.\n"); 2758 2759 sourcedata = SCIPconsGetData(sourcecons); 2760 assert( sourcedata != NULL ); 2761 assert( sourcedata->vars != NULL ); 2762 assert( sourcedata->perm != NULL ); 2763 assert( sourcedata->nvars > 0 ); 2764 2765 conshdlrdata = SCIPconshdlrGetData(sourceconshdlr); 2766 assert( conshdlrdata != NULL ); 2767 2768 /* do not copy non-model constraints */ 2769 if ( !sourcedata->ismodelcons && !conshdlrdata->forceconscopy ) 2770 { 2771 *valid = FALSE; 2772 2773 return SCIP_OKAY; 2774 } 2775 2776 sourcevars = sourcedata->vars; 2777 nvars = sourcedata->nvars; 2778 2779 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) ); 2780 2781 for (i = 0; i < nvars && *valid; ++i) 2782 { 2783 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[i], &(vars[i]), varmap, consmap, global, valid) ); 2784 assert( !(*valid) || vars[i] != NULL ); 2785 } 2786 2787 /* only create the target constraint, if all variables could be copied */ 2788 if ( *valid ) 2789 { 2790 /* create copied constraint */ 2791 if ( name == NULL ) 2792 name = SCIPconsGetName(sourcecons); 2793 2794 SCIP_CALL( SCIPcreateConsSymresack(scip, cons, name, sourcedata->perm, vars, nvars, sourcedata->ismodelcons, 2795 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) ); 2796 } 2797 2798 SCIPfreeBufferArray(scip, &vars); 2799 2800 return SCIP_OKAY; 2801 } 2802 2803 2804 /** constraint parsing method of constraint handler */ 2805 static 2806 SCIP_DECL_CONSPARSE(consParseSymresack) 2807 { /*lint --e{715}*/ 2808 const char* s; 2809 char* endptr; 2810 SCIP_VAR** vars; 2811 SCIP_VAR* var; 2812 int* perm; 2813 int val; 2814 int nvars = 0; 2815 int cnt = 0; 2816 int nfoundpermidx = 0; 2817 int maxnvars = 128; 2818 2819 assert( success != NULL ); 2820 2821 *success = TRUE; 2822 s = str; 2823 2824 /* skip white space */ 2825 SCIP_CALL( SCIPskipSpace((char**)&s) ); 2826 2827 if( strncmp(s, "symresack(", 10) != 0 ) 2828 { 2829 SCIPerrorMessage("Syntax error - expected \"symresack(\", but got '%s'", s); 2830 *success = FALSE; 2831 return SCIP_OKAY; 2832 } 2833 s += 10; 2834 2835 /* loop through string */ 2836 SCIP_CALL( SCIPallocBufferArray(scip, &vars, maxnvars) ); 2837 SCIP_CALL( SCIPallocBufferArray(scip, &perm, maxnvars) ); 2838 2839 do 2840 { 2841 if( cnt > 1 ) 2842 { 2843 SCIPerrorMessage("expected two arrays, but got more\n"); 2844 *success = FALSE; 2845 break; 2846 } 2847 2848 /* skip whitespace */ 2849 SCIP_CALL( SCIPskipSpace((char**)&s) ); 2850 2851 /* skip ',' */ 2852 if( *s == ',' ) 2853 ++s; 2854 2855 /* skip whitespace */ 2856 SCIP_CALL( SCIPskipSpace((char**)&s) ); 2857 2858 /* if we could not find starting indicator of array */ 2859 if( *s != '[' ) 2860 { 2861 SCIPerrorMessage("expected '[' to start new array\n"); 2862 *success = FALSE; 2863 break; 2864 } 2865 ++s; 2866 2867 /* read array, cnt = 0: variables; cnt = 1: permutation*/ 2868 if( cnt == 0 ) 2869 { 2870 do 2871 { 2872 /* parse variable name */ 2873 SCIP_CALL( SCIPparseVarName(scip, s, &var, &endptr) ); 2874 2875 if( var == NULL ) 2876 { 2877 endptr = strchr(endptr, ']'); 2878 2879 if( endptr == NULL ) 2880 { 2881 SCIPerrorMessage("closing ']' missing\n"); 2882 *success = FALSE; 2883 } 2884 else 2885 s = endptr; 2886 2887 break; 2888 } 2889 2890 s = endptr; 2891 assert( s != NULL ); 2892 ++nvars; 2893 2894 if( nvars > maxnvars ) 2895 { 2896 maxnvars = SCIPcalcMemGrowSize(scip, nvars); 2897 SCIP_CALL( SCIPreallocBufferArray(scip, &vars, maxnvars) ); 2898 SCIP_CALL( SCIPreallocBufferArray(scip, &perm, maxnvars) ); 2899 assert( nvars <= maxnvars ); 2900 } 2901 2902 vars[nvars-1] = var; 2903 2904 /* skip white space */ 2905 SCIP_CALL( SCIPskipSpace((char**)&s) ); 2906 2907 /* skip ',' */ 2908 if( *s == ',' ) 2909 ++s; 2910 } 2911 while( *s != ']' ); 2912 } 2913 else 2914 { 2915 do 2916 { 2917 /* skip whitespace */ 2918 SCIP_CALL( SCIPskipSpace((char**)&s) ); 2919 2920 /* parse integer value */ 2921 if( !SCIPstrToIntValue(s, &val, &endptr) ) 2922 { 2923 SCIPerrorMessage("could not extract int from string '%s'\n", str); 2924 *success = FALSE; 2925 break; 2926 } 2927 2928 s = endptr; 2929 assert( s != NULL ); 2930 ++nfoundpermidx; 2931 2932 if( nfoundpermidx > nvars ) 2933 { 2934 SCIPerrorMessage("permutation is longer than vars array\n"); 2935 *success = FALSE; 2936 break; 2937 } 2938 2939 perm[nfoundpermidx-1] = val; 2940 2941 /* skip whitespace */ 2942 SCIP_CALL( SCIPskipSpace((char**)&s) ); 2943 2944 /* skip ',' */ 2945 if( *s == ',' ) 2946 ++s; 2947 } 2948 while( *s != ']' ); 2949 2950 if( nfoundpermidx != nvars ) 2951 { 2952 SCIPerrorMessage("length of permutation is not equal to number of given variables.\n"); 2953 *success = FALSE; 2954 break; 2955 } 2956 } 2957 2958 if( !*success ) 2959 break; 2960 2961 ++s; 2962 ++cnt; 2963 } 2964 while( *s != ')' ); 2965 2966 if( *success && cnt < 2 ) 2967 { 2968 SCIPerrorMessage("permutation is missing.\n"); 2969 *success = FALSE; 2970 } 2971 2972 if( *success ) 2973 SCIP_CALL( SCIPcreateConsBasicSymresack(scip, cons, name, perm, vars, nvars, TRUE) ); 2974 2975 SCIPfreeBufferArray(scip, &perm); 2976 SCIPfreeBufferArray(scip, &vars); 2977 2978 return SCIP_OKAY; 2979 } 2980 2981 2982 /** constraint display method of constraint handler 2983 * 2984 * The constraint handler should output a representation of the constraint into the given text file. 2985 */ 2986 static 2987 SCIP_DECL_CONSPRINT(consPrintSymresack) 2988 { /*lint --e{715}*/ 2989 SCIP_CONSDATA* consdata; 2990 SCIP_VAR** vars; 2991 int* perm; 2992 int nvars; 2993 int i; 2994 2995 assert( scip != NULL ); 2996 assert( conshdlr != NULL ); 2997 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 2998 assert( cons != NULL ); 2999 3000 consdata = SCIPconsGetData(cons); 3001 assert( consdata != NULL ); 3002 3003 SCIPdebugMsg(scip, "Printing method for symresack constraint handler\n"); 3004 3005 /* we do not have to take care of trivial constraints */ 3006 if ( consdata->nvars < 2 ) 3007 return SCIP_OKAY; 3008 3009 assert( consdata->vars != NULL ); 3010 assert( consdata->perm != NULL ); 3011 3012 vars = consdata->vars; 3013 nvars = consdata->nvars; 3014 perm = consdata->perm; 3015 3016 SCIPinfoMessage(scip, file, "symresack(["); 3017 SCIP_CALL( SCIPwriteVarName(scip, file, vars[0], TRUE) ); 3018 3019 for (i = 1; i < nvars; ++i) 3020 { 3021 SCIPinfoMessage(scip, file, ","); 3022 SCIP_CALL( SCIPwriteVarName(scip, file, vars[i], TRUE) ); 3023 } 3024 SCIPinfoMessage(scip, file, "],[%d", perm[0]); 3025 for (i = 1; i < nvars; ++i) 3026 SCIPinfoMessage(scip, file, ",%d", perm[i]); 3027 SCIPinfoMessage(scip, file, "])"); 3028 3029 return SCIP_OKAY; 3030 } 3031 3032 3033 /** constraint method of constraint handler which returns the variables (if possible) */ 3034 static 3035 SCIP_DECL_CONSGETVARS(consGetVarsSymresack) 3036 { /*lint --e{715}*/ 3037 SCIP_CONSDATA* consdata; 3038 3039 assert( cons != NULL ); 3040 assert( success != NULL ); 3041 assert( vars != NULL ); 3042 3043 consdata = SCIPconsGetData(cons); 3044 assert( consdata != NULL ); 3045 3046 if ( varssize < consdata->nvars ) 3047 (*success) = FALSE; 3048 else 3049 { 3050 int cnt = 0; 3051 int i; 3052 3053 for (i = 0; i < consdata->nvars; ++i) 3054 vars[cnt++] = consdata->vars[i]; 3055 (*success) = TRUE; 3056 } 3057 3058 return SCIP_OKAY; 3059 } 3060 3061 3062 /** constraint method of constraint handler which returns the number of variables (if possible) */ 3063 static 3064 SCIP_DECL_CONSGETNVARS(consGetNVarsSymresack) 3065 { /*lint --e{715}*/ 3066 SCIP_CONSDATA* consdata; 3067 3068 assert( cons != NULL ); 3069 assert( success != NULL ); 3070 assert( nvars != NULL ); 3071 3072 consdata = SCIPconsGetData(cons); 3073 assert( consdata != NULL ); 3074 3075 (*nvars) = consdata->nvars; 3076 (*success) = TRUE; 3077 3078 return SCIP_OKAY; 3079 } 3080 3081 3082 /** creates the handler for symresack constraints and includes it in SCIP */ 3083 SCIP_RETCODE SCIPincludeConshdlrSymresack( 3084 SCIP* scip /**< SCIP data structure */ 3085 ) 3086 { 3087 SCIP_CONSHDLRDATA* conshdlrdata = NULL; 3088 SCIP_CONSHDLR* conshdlr; 3089 3090 SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) ); 3091 3092 /* include constraint handler */ 3093 SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC, 3094 CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS, 3095 consEnfolpSymresack, consEnfopsSymresack, consCheckSymresack, consLockSymresack, 3096 conshdlrdata) ); 3097 assert( conshdlr != NULL ); 3098 3099 /* set non-fundamental callbacks via specific setter functions */ 3100 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopySymresack, consCopySymresack) ); 3101 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxSymresack) ); 3102 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeSymresack) ); 3103 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteSymresack) ); 3104 SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsSymresack) ); 3105 SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsSymresack) ); 3106 SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseSymresack) ); 3107 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolSymresack, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) ); 3108 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintSymresack) ); 3109 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropSymresack, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, CONSHDLR_PROP_TIMING) ); 3110 SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropSymresack) ); 3111 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpSymresack, consSepasolSymresack, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, CONSHDLR_DELAYSEPA) ); 3112 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransSymresack) ); 3113 SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpSymresack) ); 3114 SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolSymresack) ); 3115 3116 /* whether we allow upgrading to packing/partioning symresack constraints*/ 3117 SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/ppsymresack", 3118 "Upgrade symresack constraints to packing/partioning symresacks?", 3119 &conshdlrdata->checkppsymresack, TRUE, DEFAULT_PPSYMRESACK, NULL, NULL) ); 3120 3121 /* whether we check for monotonicity of perm when upgrading to packing/partioning symresacks */ 3122 SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/checkmonotonicity", 3123 "Check whether permutation is monotone when upgrading to packing/partioning symresacks?", 3124 &conshdlrdata->checkmonotonicity, TRUE, DEFAULT_CHECKMONOTONICITY, NULL, NULL) ); 3125 3126 SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/forceconscopy", 3127 "Whether symresack constraints should be forced to be copied to sub SCIPs.", 3128 &conshdlrdata->forceconscopy, TRUE, DEFAULT_FORCECONSCOPY, NULL, NULL) ); 3129 3130 return SCIP_OKAY; 3131 } 3132 3133 3134 /* 3135 * constraint specific interface methods 3136 */ 3137 3138 /** creates and captures a symresack constraint 3139 * 3140 * In a presolving step, we check whether the permutation acts only on binary points. Otherwise, we eliminate 3141 * the non-binary variables from the permutation. 3142 * 3143 * @note The constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons(). 3144 */ 3145 SCIP_RETCODE SCIPcreateConsSymresack( 3146 SCIP* scip, /**< SCIP data structure */ 3147 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 3148 const char* name, /**< name of constraint */ 3149 int* perm, /**< permutation */ 3150 SCIP_VAR** vars, /**< variables */ 3151 int nvars, /**< number of variables in vars array */ 3152 SCIP_Bool ismodelcons, /**< whether the symresack is a model constraint */ 3153 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? 3154 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */ 3155 SCIP_Bool separate, /**< should the constraint be separated during LP processing? 3156 * Usually set to TRUE. */ 3157 SCIP_Bool enforce, /**< should the constraint be enforced during node processing? 3158 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 3159 SCIP_Bool check, /**< should the constraint be checked for feasibility? 3160 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 3161 SCIP_Bool propagate, /**< should the constraint be propagated during node processing? 3162 * Usually set to TRUE. */ 3163 SCIP_Bool local, /**< is constraint only valid locally? 3164 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */ 3165 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? 3166 * Usually set to FALSE. In column generation applications, set to TRUE if pricing 3167 * adds coefficients to this constraint. */ 3168 SCIP_Bool dynamic, /**< is constraint subject to aging? 3169 * Usually set to FALSE. Set to TRUE for own cuts which 3170 * are separated as constraints. */ 3171 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? 3172 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */ 3173 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even 3174 * if it may be moved to a more global node? 3175 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */ 3176 ) 3177 { 3178 SCIP_CONSHDLR* conshdlr; 3179 SCIP_CONSDATA* consdata; 3180 3181 assert( cons != NULL ); 3182 assert( nvars > 0 ); 3183 3184 /* find the symresack constraint handler */ 3185 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME); 3186 if ( conshdlr == NULL ) 3187 { 3188 SCIPerrorMessage("Symresack constraint handler not found.\n"); 3189 return SCIP_PLUGINNOTFOUND; 3190 } 3191 3192 /* create constraint data */ 3193 SCIP_CALL( consdataCreate(scip, conshdlr, &consdata, vars, nvars, perm, ismodelcons) ); 3194 3195 /* create constraint */ 3196 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate && (! consdata->ppupgrade), enforce, check, propagate, 3197 local, modifiable, dynamic, removable, stickingatnode) ); 3198 3199 return SCIP_OKAY; 3200 } 3201 3202 3203 /** creates and captures a symresack constraint 3204 * in its most basic variant, i.e., with all constraint flags set to their default values 3205 * 3206 * In a presolving step, we remove all fixed points and cycles that act on non-binary variables of the permutation 3207 * 3208 * @note The constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons(). 3209 */ 3210 SCIP_RETCODE SCIPcreateConsBasicSymresack( 3211 SCIP* scip, /**< SCIP data structure */ 3212 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 3213 const char* name, /**< name of constraint */ 3214 int* perm, /**< permutation */ 3215 SCIP_VAR** vars, /**< variables */ 3216 int nvars, /**< number of variables in vars array */ 3217 SCIP_Bool ismodelcons /**< whether the symresack is a model constraint */ 3218 ) 3219 { 3220 SCIP_CALL( SCIPcreateConsSymresack(scip, cons, name, perm, vars, nvars, ismodelcons, 3221 TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 3222 3223 return SCIP_OKAY; 3224 } 3225