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_orbitope.c 26 * @ingroup DEFPLUGINS_CONS 27 * @brief constraint handler for (partitioning/packing/full) orbitope constraints w.r.t. the full symmetric group 28 * @author Timo Berthold 29 * @author Marc Pfetsch 30 * @author Christopher Hojny 31 * 32 * The type of constraints of this constraint handler is described in cons_orbitope.h. 33 * 34 * The details of the method implemented here are described in the following papers. 35 * 36 * Packing and Partitioning Orbitopes@n 37 * Volker Kaibel and Marc E. Pfetsch,@n 38 * Math. Program. 114, No. 1, 1-36 (2008) 39 * 40 * Among other things, this paper describes so-called shifted column inequalities of the following 41 * form \f$x(S) \leq x(B)\f$, where \f$S\f$ is a so-called shifted column and \f$B\f$ is a so-called 42 * bar. These inequalities can be used to handle symmetry and they are separated in this constraint 43 * handler. We use the linear time separation algorithm of the paper.@par 44 * 45 * Orbitopal Fixing@n 46 * Volker Kaibel, Matthias Peinhardt, and Marc E. Pfetsch,@n 47 * Discrete Optimization 8, No. 4, 595-610 (2011) 48 * (A preliminary version appears in Proc. IPCO 2007.) 49 * 50 * In this paper a linear time propagation algorithm is described, a variant of which is implemented 51 * here. The implemented variant does not run in linear time, but is very fast in practice. 52 * 53 * <table> 54 * <caption>translation table</caption> 55 * <tr><td>here</td><td>paper</td></tr> 56 * <tr><td></td><td></td></tr> 57 * <tr><td>nspcons </td><td>p </td></tr> 58 * <tr><td>nblocks </td><td>q </td></tr> 59 * <tr><td>vars </td><td>x </td></tr> 60 * <tr><td>vals </td><td>A^\\star</td></tr> 61 * <tr><td>weights </td><td>\\omega </td></tr> 62 * <tr><td>cases </td><td>\\tau </td></tr> 63 * <tr><td>fixtriangle </td><td>-- </td></tr> 64 * <tr><td>resolveprop </td><td>-- </td></tr> 65 * <tr><td>firstnonzeros</td><td>\\mu </td></tr> 66 * <tr><td>lastones </td><td>\\alpha </td></tr> 67 * <tr><td>frontiersteps</td><td>\\Gamma </td></tr> 68 * </table> 69 * 70 * Orbitopal fixing for the full (sub-)orbitope and application to the Unit Commitment Problem@n 71 * Pascale Bendotti, Pierre Fouilhoux, and Cecile Rottner,@n 72 * Optimization Online: http://www.optimization-online.org/DB_HTML/2017/10/6301.html 73 * 74 * Two linear time propagation algorithms for full orbitopes are described in this paper, a static 75 * version and a dynamic one. While the static version uses a fixed variable order, the dynamic 76 * version determines the variable order during the solving process via branching descisions. 77 * We implemented the static version as well as a modified version of the dynamic one. The reason 78 * for the latter is to simplify the compatibility with full orbitope cutting planes. 79 * 80 * Note, however, that the dynamic version may lead to conflicts if orbitopes are copied to subSCIPs. 81 * Since the dynamic version is based on branching decisions, which may be different in main SCIP 82 * and subSCIPs, orbitopes using the dynamic algorithm are not allowed to be copied. However, as a 83 * user might use orbitopes to enforce a certain variable ordering in a solution, we distinguish 84 * whether an orbitope is a model constraint or not. If it is a model constraint, we assume that 85 * a variable order has already been fixed and disable the dynamic algorithm. In this case, orbitope 86 * constraints are copied to subSCIPs. If it is not a model constraint, the orbitope was added to 87 * handle symmetries but not to enforce a solution to have a certain structure. In this case, the 88 * dynamic algorithm can be used and we do not copy orbitope constraints to subSCIPs. 89 * 90 * Polytopes associated with symmetry handling@n 91 * Christopher Hojny and Marc E. Pfetsch,@n 92 * Math. Program. (2018) 93 * 94 * In this paper, a linear time separation algorithm for orbisacks (full orbitopes with two columnes) 95 * is described. We use this algorithm for every pair of adjacent columns within the orbitope as well 96 * as a version that is adapted to the reordering based on the dynamic full orbitope propagation 97 * algorithm to ensure validity of binary points via cutting planes. 98 */ 99 100 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 101 102 #include "blockmemshell/memory.h" 103 #include "scip/cons_orbisack.h" 104 #include "scip/cons_orbitope.h" 105 #include "scip/cons_setppc.h" 106 #include "scip/pub_cons.h" 107 #include "scip/pub_message.h" 108 #include "scip/pub_var.h" 109 #include "scip/scip.h" 110 #include "scip/scip_branch.h" 111 #include "scip/scip_conflict.h" 112 #include "scip/scip_cons.h" 113 #include "scip/scip_copy.h" 114 #include "scip/scip_cut.h" 115 #include "scip/scip_general.h" 116 #include "scip/scip_lp.h" 117 #include "scip/scip_mem.h" 118 #include "scip/scip_message.h" 119 #include "scip/scip_numerics.h" 120 #include "scip/scip_param.h" 121 #include "scip/scip_prob.h" 122 #include "scip/scip_probing.h" 123 #include "scip/scip_sol.h" 124 #include "scip/scip_var.h" 125 #include "scip/symmetry.h" 126 #include <symmetry/type_symmetry.h> 127 128 /* constraint handler properties */ 129 #define CONSHDLR_NAME "orbitope" 130 #define CONSHDLR_DESC "symmetry breaking constraint handler relying on (partitioning/packing) orbitopes" 131 #define CONSHDLR_SEPAPRIORITY +40100 /**< priority of the constraint handler for separation */ 132 #define CONSHDLR_ENFOPRIORITY -1005200 /**< priority of the constraint handler for constraint enforcing */ 133 #define CONSHDLR_CHECKPRIORITY -1005200 /**< priority of the constraint handler for checking feasibility */ 134 #define CONSHDLR_SEPAFREQ -1 /**< frequency for separating cuts; zero means to separate only in the root node */ 135 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */ 136 #define CONSHDLR_EAGERFREQ -1 /**< frequency for using all instead of only the useful constraints in separation, 137 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */ 138 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */ 139 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */ 140 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */ 141 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */ 142 143 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP /**< propagation timing mask of the constraint handler */ 144 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */ 145 146 #define DEFAULT_PPORBITOPE TRUE /**< whether we check if full orbitopes can be strengthened to packing/partitioning orbitopes */ 147 #define DEFAULT_SEPAFULLORBITOPE FALSE /**< whether we separate inequalities for full orbitopes */ 148 #define DEFAULT_FORCECONSCOPY FALSE /**< whether orbitope constraints should be forced to be copied to sub SCIPs */ 149 150 /* 151 * Data structures 152 */ 153 154 /** constraint handler data */ 155 struct SCIP_ConshdlrData 156 { 157 SCIP_Bool checkpporbitope; /**< whether we allow upgrading to packing/partitioning orbitopes */ 158 SCIP_Bool sepafullorbitope; /**< whether we separate inequalities for full orbitopes orbitopes */ 159 SCIP_Bool forceconscopy; /**< whether orbitope constraints should be forced to be copied to sub SCIPs */ 160 }; 161 162 /** constraint data for orbitope constraints */ 163 struct SCIP_ConsData 164 { 165 SCIP_VAR*** vars; /**< matrix of variables on which the symmetry acts */ 166 SCIP_VAR** tmpvars; /**< temporary storage for variables */ 167 SCIP_HASHMAP* rowindexmap; /**< map of variables to row index in orbitope matrix */ 168 SCIP_Real** vals; /**< LP-solution for those variables */ 169 SCIP_Real* tmpvals; /**< temporary storage for values */ 170 SCIP_Real** weights; /**< SC weight table */ 171 int** cases; /**< indicator of the SC cases */ 172 int nspcons; /**< number of set partitioning/packing constraints <=> p */ 173 int nblocks; /**< number of symmetric variable blocks <=> q */ 174 SCIP_ORBITOPETYPE orbitopetype; /**< type of orbitope constraint */ 175 SCIP_Bool resolveprop; /**< should propagation be resolved? */ 176 SCIP_Bool istrianglefixed; /**< has the upper right triangle already globally been fixed to zero? */ 177 int* roworder; /**< order of orbitope rows if dynamic propagation for full orbitopes 178 * is used. */ 179 SCIP_Bool* rowused; /**< whether a row has been considered in roworder */ 180 int nrowsused; /**< number of rows that have already been considered in roworder */ 181 SCIP_Bool ismodelcons; /**< whether the orbitope is a model constraint */ 182 SCIP_Bool mayinteract; /**< whether symmetries corresponding to orbitope might interact 183 * with symmetries handled by other routines */ 184 SCIP_Bool usedynamicprop; /**< whether we use a dynamic version of the propagation routine */ 185 }; 186 187 188 /* 189 * Local methods 190 */ 191 192 /** frees an orbitope constraint data */ 193 static 194 SCIP_RETCODE consdataFree( 195 SCIP* scip, /**< SCIP data structure */ 196 SCIP_CONSDATA** consdata /**< pointer to orbitope constraint data */ 197 ) 198 { 199 int i; 200 int j; 201 int p; 202 int q; 203 204 assert( consdata != NULL ); 205 assert( *consdata != NULL ); 206 207 if ( (*consdata)->usedynamicprop && (*consdata)->rowindexmap != NULL ) 208 { 209 SCIPhashmapFree(&((*consdata)->rowindexmap)); 210 } 211 212 p = (*consdata)->nspcons; 213 q = (*consdata)->nblocks; 214 for (i = 0; i < p; ++i) 215 { 216 /* release variables in vars array */ 217 for (j = 0; j < q; ++j) 218 { 219 assert( (*consdata)->vars[i] != NULL ); 220 SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->vars[i][j]) ); 221 } 222 223 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cases[i]), q); /*lint !e866*/ 224 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars[i]), q); /*lint !e866*/ 225 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->weights[i]), q); /*lint !e866*/ 226 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vals[i]), q); /*lint !e866*/ 227 } 228 229 if ( (*consdata)->usedynamicprop ) 230 { 231 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->rowused), p); 232 } 233 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->roworder), p); 234 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cases), p); 235 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars), p); 236 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->weights), p); 237 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vals), p); 238 239 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->tmpvals), p + q); 240 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->tmpvars), p + q); 241 242 SCIPfreeBlockMemory(scip, consdata); 243 244 return SCIP_OKAY; 245 } 246 247 248 /** creates orbitope constraint data */ 249 static 250 SCIP_RETCODE consdataCreate( 251 SCIP* scip, /**< SCIP data structure */ 252 SCIP_CONSDATA** consdata, /**< pointer to store constraint data */ 253 SCIP_VAR*** vars, /**< variables array, must have size nspcons x nblocks */ 254 int nspcons, /**< number of set partitioning (packing) constraints <=> p */ 255 int nblocks, /**< number of symmetric variable blocks <=> q */ 256 SCIP_ORBITOPETYPE orbitopetype, /**< type of orbitope constraint */ 257 SCIP_Bool resolveprop, /**< should propagation be resolved? */ 258 SCIP_Bool usedynamicprop, /**< whether we use a dynamic version of the propagation routine */ 259 SCIP_Bool ismodelcons, /**< whether the orbitope is a model constraint */ 260 SCIP_Bool mayinteract /**< whether symmetries corresponding to orbitope might interact 261 * with symmetries handled by other routines */ 262 ) 263 { 264 int i; 265 int j; 266 267 assert(consdata != NULL); 268 #ifndef NDEBUG 269 if ( usedynamicprop ) 270 { 271 assert( ! mayinteract ); 272 } 273 #endif 274 275 SCIP_CALL( SCIPallocBlockMemory(scip, consdata) ); 276 277 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->vals, nspcons) ); 278 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->weights, nspcons) ); 279 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->vars, nspcons) ); 280 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->cases, nspcons) ); 281 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->roworder, nspcons) ); 282 283 /* if orbitope might interact with other symmetries, we cannot adapt the row order of orbitopes dynamically */ 284 if ( usedynamicprop ) 285 { 286 SCIP_CALL( SCIPhashmapCreate(&(*consdata)->rowindexmap, SCIPblkmem(scip), nspcons) ); 287 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->rowused, nspcons) ); 288 } 289 290 for (i = 0; i < nspcons; ++i) 291 { 292 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->vals[i], nblocks) ); /*lint !e866*/ 293 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->weights[i], nblocks) ); /*lint !e866*/ 294 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars[i], vars[i], nblocks) ); /*lint !e866*/ 295 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->cases[i], nblocks) ); /*lint !e866*/ 296 (*consdata)->roworder[i] = i; 297 298 if ( usedynamicprop ) 299 { 300 (*consdata)->rowused[i] = FALSE; 301 } 302 } 303 (*consdata)->nrowsused = 0; 304 305 (*consdata)->tmpvals = NULL; 306 (*consdata)->tmpvars = NULL; 307 (*consdata)->nspcons = nspcons; 308 (*consdata)->nblocks = nblocks; 309 (*consdata)->orbitopetype = orbitopetype; 310 (*consdata)->resolveprop = resolveprop; 311 (*consdata)->istrianglefixed = FALSE; 312 (*consdata)->ismodelcons = ismodelcons; 313 (*consdata)->mayinteract = mayinteract; 314 (*consdata)->usedynamicprop = usedynamicprop; 315 316 /* get transformed variables, if we are in the transformed problem */ 317 if ( SCIPisTransformed(scip) ) 318 { 319 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->tmpvals, nspcons + nblocks) ); 320 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->tmpvars, nspcons + nblocks) ); 321 322 for (i = 0; i < nspcons; ++i) 323 { 324 /* make sure that no variable gets multiaggregated (cannot be handled by cons_orbitope, since one cannot easily 325 * eliminate single variables from an orbitope constraint). 326 */ 327 for (j = 0; j < nblocks; ++j) 328 { 329 SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->vars[i][j], &(*consdata)->vars[i][j]) ); 330 SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars[i][j]) ); 331 if ( usedynamicprop ) 332 { 333 SCIP_CALL( SCIPhashmapInsert((*consdata)->rowindexmap, (*consdata)->vars[i][j], (void*) (size_t) i) ); 334 } 335 } 336 } 337 } 338 339 /* capture vars contained in vars array */ 340 for (i = 0; i < nspcons; ++i) 341 { 342 for (j = 0; j < nblocks; ++j) 343 { 344 assert( (*consdata)->vars[i][j] != NULL ); 345 SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars[i][j]) ); 346 } 347 } 348 349 return SCIP_OKAY; 350 } 351 352 353 /** strengthen full orbitopes to packing/partitioning orbitopes if possible */ 354 static 355 SCIP_RETCODE strengthenOrbitopeConstraint( 356 SCIP* scip, /**< SCIP data structure */ 357 SCIP_VAR*** vars, /**< variable matrix of orbitope constraint */ 358 int* nrows, /**< pointer to number of rows of variable matrix */ 359 int ncols, /**< number of columns of variable matrix */ 360 SCIP_ORBITOPETYPE* type, /**< pointer to store type of orbitope constraint after strengthening */ 361 SCIP_Bool mayinteract /**< whether symmetries corresponding to orbitope might interact 362 * with symmetries handled by other routines */ 363 ) 364 { 365 SCIP_Bool* pprows = NULL; 366 int npprows; 367 int nrowsorig; 368 369 assert( scip != NULL ); 370 assert( vars != NULL ); 371 assert( vars != NULL ); 372 assert( *nrows > 0 ); 373 assert( ncols > 0 ); 374 assert( type != NULL ); 375 376 nrowsorig = *nrows; 377 SCIP_CALL( SCIPisPackingPartitioningOrbitope(scip, vars, *nrows, ncols, &pprows, &npprows, type) ); 378 379 /* If only some rows are contained in set packing/partitioning constraints, it may still be worth it 380 * to exploit the packing/partitioning structure on these rows, because packing/partitioning orbitopes 381 * or more restrictive than full orbitopes. If at least three rows have this property, we discard 382 * all rows not contained in set packing/partitioning constraints and add the smaller sub packing orbitope. 383 * This is only possible if the orbitope's symmetries do not interact with other symmetry handling 384 * methods (otherwise, dropping rows might change the variable order). 385 */ 386 if ( npprows >= 3 && ! mayinteract ) 387 { 388 int r = *nrows - 1; 389 int i; 390 391 assert( pprows != NULL ); 392 393 while ( r >= 0 ) 394 { 395 if ( ! pprows[r] ) 396 { 397 for (i = r; i < *nrows - 1; ++i) 398 { 399 SCIP_VAR** row; 400 row = vars[i]; 401 vars[i] = vars[i+1]; 402 vars[i+1] = row; 403 } 404 *nrows -= 1; 405 } 406 --r; 407 } 408 *type = SCIP_ORBITOPETYPE_PACKING; 409 } 410 411 /* pprows might not have been initialized if there are no setppc conss */ 412 if ( pprows != NULL ) 413 { 414 SCIPfreeBlockMemoryArray(scip, &pprows, nrowsorig); 415 } 416 417 return SCIP_OKAY; 418 } 419 420 #ifdef PRINT_MATRIX 421 /** debug method, prints variable matrix */ 422 static 423 void printMatrix( 424 SCIP* scip, /**< SCIP data structure */ 425 SCIP_CONSDATA* consdata /**< the constraint data */ 426 ) 427 { 428 int i; 429 int j; 430 431 assert( consdata != NULL ); 432 assert( consdata->nspcons > 0 ); 433 assert( consdata->nblocks > 0 ); 434 assert( consdata->vars != NULL ); 435 436 for (j = 0; j < consdata->nblocks; ++j) 437 SCIPinfoMessage(scip, NULL, "-"); 438 439 SCIPinfoMessage(scip, NULL, "\n"); 440 for (i = 0; i < consdata->nspcons; ++i) 441 { 442 for (j = 0; j < consdata->nblocks; ++j) 443 { 444 if ( SCIPvarGetUbLocal(consdata->vars[i][j]) - SCIPvarGetLbLocal(consdata->vars[i][j]) < 0.5 ) 445 SCIPinfoMessage(scip, NULL, "%1.0f", REALABS(SCIPvarGetUbLocal(consdata->vars[i][j]))); 446 else 447 SCIPinfoMessage(scip, NULL, " "); 448 } 449 SCIPinfoMessage(scip, NULL, "|\n"); 450 } 451 for (j = 0; j < consdata->nblocks; ++j) 452 SCIPinfoMessage(scip, NULL, "-"); 453 SCIPinfoMessage(scip, NULL, "\n"); 454 } 455 #endif 456 457 458 #ifdef SHOW_SCI 459 /** Print SCI in nice form for debugging */ 460 static 461 SCIP_RETCODE printSCI( 462 SCIP* scip, /**< SCIP pointer */ 463 int p, /**< number of rows */ 464 int q, /**< number of columns */ 465 int** cases, /**< SCI dynamic programming table */ 466 int i, /**< row position of bar */ 467 int j /**< column position of bar */ 468 ) 469 { 470 int k; 471 int l; 472 int** M; 473 int p1; 474 int p2; 475 476 SCIP_CALL( SCIPallocBufferArray(scip, &M, p) ); 477 for (k = 0; k < p; ++k) 478 { 479 SCIP_CALL( SCIPallocBufferArray(scip, &M[k], q) ); /*lint !e866*/ 480 for (l = 0; l < q; ++l) 481 M[k][l] = 0; 482 } 483 484 /* first add bar */ 485 for (l = j; l < q; ++l) 486 { 487 assert( M[i][l] == 0 ); 488 M[i][l] = 1; 489 } 490 491 /* then add shifted column */ 492 p1 = i-1; 493 p2 = j-1; 494 do 495 { 496 assert( cases[p1][p2] != -1 ); 497 assert( p1 >= 0 && p1 < i ); 498 assert( p2 >= 0 && p2 < j ); 499 500 /* if case 1 */ 501 if ( cases[p1][p2] == 1 ) 502 --p2; /* decrease column */ 503 else 504 { 505 /* case 2 or 3: */ 506 assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 ); 507 assert( M[p1][p2] == 0 ); 508 M[p1][p2] = -1; 509 if ( cases[p1][p2] == 3 ) 510 break; 511 } 512 --p1; /* decrease row */ 513 } 514 while ( p1 >= 0 ); /* should always be true, i.e. the break should end the loop */ 515 assert( cases[p1][p2] == 3 ); 516 517 /* now output matrix M */ 518 for (l = 0; l < q; ++l) 519 SCIPinfoMessage(scip, NULL, "-"); 520 SCIPinfoMessage(scip, NULL, "\n"); 521 522 for (k = 0; k < p; ++k) 523 { 524 for (l = 0; l < q; ++l) 525 { 526 if ( l > k ) 527 SCIPinfoMessage(scip, NULL, "*"); 528 else 529 { 530 switch (M[k][l]) 531 { 532 case 1: 533 SCIPinfoMessage(scip, NULL, "+"); 534 break; 535 case -1: 536 SCIPinfoMessage(scip, NULL, "-"); 537 break; 538 case 0: 539 SCIPinfoMessage(scip, NULL, "#"); 540 break; 541 default: 542 SCIPerrorMessage("unexpected matrix entry <%d>: should be -1, 0 or +1\n", M[k][l]); 543 SCIPABORT(); 544 } 545 } 546 } 547 SCIPinfoMessage(scip, NULL, "\n"); 548 } 549 550 for (l = 0; l < q; ++l) 551 SCIPinfoMessage(scip, NULL, "-"); 552 SCIPinfoMessage(scip, NULL, "\n"); 553 554 for (k = 0; k < p; ++k) 555 SCIPfreeBufferArray(scip, &M[k]); 556 SCIPfreeBufferArray(scip, &M); 557 558 return SCIP_OKAY; 559 } 560 #endif 561 562 563 /** copies the variables values from the solution to the constraint data structure */ 564 static 565 void copyValues( 566 SCIP* scip, /**< the SCIP data structure */ 567 SCIP_CONSDATA* consdata, /**< the constraint data */ 568 SCIP_SOL* sol /**< a primal solution or NULL for the current LP optimum */ 569 ) 570 { 571 int i; 572 int j; 573 574 assert( scip != NULL ); 575 assert( consdata != NULL ); 576 assert( consdata->nspcons > 0 ); 577 assert( consdata->nblocks > 0 ); 578 assert( consdata->vars != NULL ); 579 assert( consdata->vals != NULL ); 580 581 for (i = 0; i < consdata->nspcons; ++i) 582 { 583 for (j = 0; j < consdata->nblocks; ++j) 584 consdata->vals[i][j] = SCIPgetSolVal(scip, sol, consdata->vars[i][j]); 585 } 586 } 587 588 589 /** compute the dynamic programming table for SC 590 * 591 * Build up dynamic programming table in order to find SCs with minimum weight. 592 * 593 * The values of the minimal SCIs are stored in @a weights. 594 * The array @a cases[i][j] stores which of the cases were applied to get @a weights[i][j]. 595 * Here, 3 means that we have reached the upper limit. 596 * 597 * We assume that the upper right triangle is fixed to 0. Hence we can perform the computation a 598 * bit more efficient. 599 */ 600 static 601 void computeSCTable( 602 SCIP* scip, /**< SCIP pointer */ 603 int nspcons, /**< number of set partitioning (packing) constraints <=> p */ 604 int nblocks, /**< number of symmetric variable blocks <=> q */ 605 SCIP_Real** weights, /**< SC weight table */ 606 int** cases, /**< indicator of the SC cases */ 607 SCIP_Real** vals /**< current solution */ 608 ) 609 { 610 SCIP_Real minvalue; 611 int diagsize; 612 int i; 613 int j; 614 615 assert( weights != NULL ); 616 assert( cases != NULL ); 617 assert( vals != NULL ); 618 619 #ifndef NDEBUG 620 /* for debugging */ 621 for (i = 0; i < nspcons; ++i) 622 { 623 for (j = 0; j < nblocks; ++j) 624 { 625 if ( i >= j ) 626 { 627 weights[i][j] = -1.0; 628 cases[i][j] = -1; 629 } 630 } 631 } 632 #endif 633 634 /* initialize diagonal */ 635 minvalue = vals[0][0]; 636 weights[0][0] = minvalue; 637 cases[0][0] = 3; 638 639 /* get last row of triangle */ 640 diagsize = nblocks; 641 if ( nspcons < nblocks ) 642 diagsize = nspcons; 643 644 for (j = 1; j < diagsize; ++j) 645 { 646 /* use LT to move entry as far to the left as possible */ 647 if ( SCIPisLT(scip, vals[j][j], minvalue) ) 648 { 649 minvalue = vals[j][j]; 650 cases[j][j] = 3; 651 } 652 else 653 cases[j][j] = 1; 654 weights[j][j] = minvalue; 655 } 656 657 /* initialize first column */ 658 for (i = 1; i < nspcons; ++i) 659 { 660 weights[i][0] = weights[i-1][0] + vals[i][0]; 661 cases[i][0] = 2; /* second case */ 662 } 663 664 /* build the table */ 665 for (i = 2; i < nspcons; ++i) 666 { 667 for (j = 1; j < nblocks && j < i; ++j) 668 { 669 SCIP_Real weightleft; 670 SCIP_Real weightright; 671 672 assert( cases[i-1][j] != -1 ); 673 assert( cases[i-1][j-1] != -1 ); 674 675 weightleft = weights[i-1][j-1]; 676 weightright = vals[i][j] + weights[i-1][j]; 677 678 /* For first column: cannot take left possibility */ 679 if ( SCIPisLT(scip, weightleft, weightright) ) 680 { 681 weights[i][j] = weightleft; 682 cases[i][j] = 1; 683 } 684 else 685 { 686 weights[i][j] = weightright; 687 cases[i][j] = 2; 688 } 689 } 690 } 691 } 692 693 694 /** fix upper right triangle if necessary */ 695 static 696 SCIP_RETCODE fixTriangle( 697 SCIP* scip, /**< SCIP data structure */ 698 SCIP_CONS* cons, /**< constraint to be processed */ 699 SCIP_Bool* infeasible, /**< pointer to store TRUE, if the node can be cut off */ 700 int* nfixedvars /**< pointer to add up the number of found domain reductions */ 701 ) 702 { 703 SCIP_CONSDATA* consdata; 704 SCIP_VAR*** vars; 705 SCIP_Bool fixedglobal; 706 SCIP_Bool fixed; 707 int diagsize; 708 int nspcons; 709 int nblocks; 710 int i; 711 int j; 712 713 assert( scip != NULL ); 714 assert( cons != NULL ); 715 assert( infeasible != NULL ); 716 assert( nfixedvars != NULL ); 717 718 consdata = SCIPconsGetData(cons); 719 assert( consdata != NULL ); 720 assert( consdata->nspcons > 0 ); 721 assert( consdata->nblocks > 0 ); 722 assert( consdata->vars != NULL ); 723 724 *infeasible = FALSE; 725 *nfixedvars = 0; 726 727 if ( consdata->istrianglefixed ) 728 return SCIP_OKAY; 729 730 nspcons = consdata->nspcons; 731 nblocks = consdata->nblocks; 732 vars = consdata->vars; 733 fixedglobal = TRUE; 734 735 /* get last row of triangle */ 736 diagsize = nblocks; 737 if ( nspcons < nblocks ) 738 diagsize = nspcons; 739 740 /* fix variables to 0 */ 741 for (i = 0; i < diagsize; ++i) 742 { 743 for (j = i+1; j < nblocks; ++j) 744 { 745 /* fix variable, if not in the root the fixation is local */ 746 SCIP_CALL( SCIPfixVar(scip, vars[i][j], 0.0, infeasible, &fixed) ); 747 748 if ( *infeasible ) 749 { 750 SCIPdebugMsg(scip, "The problem is infeasible: some variable in the upper right triangle is fixed to 1.\n"); 751 return SCIP_OKAY; 752 } 753 754 if ( fixed ) 755 ++(*nfixedvars); 756 757 if ( SCIPvarGetUbGlobal(vars[i][j]) > 0.5 ) 758 fixedglobal = FALSE; 759 } 760 } 761 if ( *nfixedvars > 0 ) 762 { 763 SCIPdebugMsg(scip, "<%s>: %s fixed upper right triangle to 0 (fixed vars: %d).\n", SCIPconsGetName(cons), fixedglobal ? "globally" : "locally", *nfixedvars); 764 } 765 else 766 { 767 SCIPdebugMsg(scip, "<%s>: Upper right triangle already fixed to 0.\n", SCIPconsGetName(cons)); 768 } 769 770 if ( fixedglobal ) 771 consdata->istrianglefixed = TRUE; 772 773 return SCIP_OKAY; 774 } 775 776 777 /** separates shifted column inequalities according to the solution stored in consdata->vals */ 778 static 779 SCIP_RETCODE separateSCIs( 780 SCIP* scip, /**< the SCIP data structure */ 781 SCIP_CONSHDLR* conshdlr, /**< constraint handler */ 782 SCIP_CONS* cons, /**< constraint */ 783 SCIP_CONSDATA* consdata, /**< the constraint data */ 784 SCIP_Bool* infeasible, /**< whether we detected infeasibility */ 785 int* nfixedvars, /**< pointer to store the number of variables fixed */ 786 int* ncuts /**< pointer to store number of separated SCIs */ 787 ) 788 { 789 SCIP_Real** vals; 790 SCIP_Real** weights; 791 SCIP_Real* tmpvals; 792 SCIP_VAR*** vars; 793 SCIP_VAR** tmpvars; 794 int** cases; 795 int nspcons; 796 int nblocks; 797 int i; 798 int j; 799 int l; 800 801 assert( scip != NULL ); 802 assert( conshdlr != NULL ); 803 assert( cons != NULL ); 804 assert( infeasible != NULL); 805 assert( nfixedvars != NULL ); 806 assert( ncuts != NULL ); 807 808 assert( consdata != NULL ); 809 assert( consdata->nspcons > 0 ); 810 assert( consdata->nblocks > 0 ); 811 assert( consdata->vars != NULL ); 812 assert( consdata->vals != NULL ); 813 assert( consdata->tmpvars != NULL ); 814 assert( consdata->tmpvals != NULL ); 815 assert( consdata->weights != NULL ); 816 assert( consdata->cases != NULL ); 817 818 *infeasible = FALSE; 819 *nfixedvars = 0; 820 *ncuts = 0; 821 822 nspcons = consdata->nspcons; 823 nblocks = consdata->nblocks; 824 vars = consdata->vars; 825 vals = consdata->vals; 826 tmpvars = consdata->tmpvars; 827 tmpvals = consdata->tmpvals; 828 weights = consdata->weights; 829 cases = consdata->cases; 830 831 /* check for upper right triangle */ 832 if ( ! consdata->istrianglefixed ) 833 { 834 SCIP_CALL( fixTriangle(scip, cons, infeasible, nfixedvars) ); 835 if ( *infeasible ) 836 return SCIP_OKAY; 837 if ( *nfixedvars > 0 ) 838 return SCIP_OKAY; 839 } 840 841 /* compute table if necessary (i.e., not computed before) */ 842 computeSCTable(scip, nspcons, nblocks, weights, cases, vals); 843 844 /* loop through rows */ 845 for (i = 1; i < nspcons && ! (*infeasible); ++i) 846 { 847 SCIP_Real bar; /* value of bar: */ 848 int lastcolumn; /* last column considered as part of the bar */ 849 850 bar = 0.0; 851 lastcolumn = nblocks - 1; 852 if ( lastcolumn > i ) 853 lastcolumn = i; 854 855 /* traverse row from right to left: */ 856 /* j >= 1, since for j = 0, i.e., the bar is a complete row, there does not exist an SCI */ 857 for (j = lastcolumn; j > 0; --j) 858 { 859 bar += vals[i][j]; 860 861 /* check whether weights[i-1][j-1] < bar (<=> bar - weights[i-1][j-1] > 0), i.e. cut is violated) */ 862 if ( SCIPisEfficacious(scip, bar - weights[i-1][j-1]) ) 863 { 864 #ifndef NDEBUG 865 SCIP_Real weight = 0.0; 866 #endif 867 SCIP_ROW* row; 868 #ifdef SCIP_DEBUG 869 char name[SCIP_MAXSTRLEN]; 870 #endif 871 int nvars; 872 int p1; 873 int p2; 874 875 nvars = 0; 876 p1 = i-1; 877 p2 = j-1; 878 879 /* first add bar */ 880 for (l = j; l <= lastcolumn; ++l) 881 { 882 tmpvars[nvars] = vars[i][l]; 883 tmpvals[nvars] = 1.0; 884 nvars++; 885 } 886 887 /* then add shifted column */ 888 do 889 { 890 assert( cases[p1][p2] != -1 ); 891 assert( p1 >= 0 && p1 < i ); 892 assert( p2 >= 0 && p2 < j ); 893 894 /* if case 1 */ 895 if (cases[p1][p2] == 1) 896 p2--; /* decrease column */ 897 else 898 { 899 /* case 2 or 3: */ 900 assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 ); 901 tmpvars[nvars] = vars[p1][p2]; 902 tmpvals[nvars] = -1.0; 903 nvars++; 904 #ifndef NDEBUG 905 weight += vals[p1][p2]; 906 #endif 907 if ( cases[p1][p2] == 3 ) 908 break; 909 } 910 p1--; /* decrease row */ 911 } 912 while ( p1 >= 0 ); /* should always be true, i.e. the break should end the loop */ 913 assert( cases[p1][p2] == 3 ); 914 915 /* generate cut */ 916 #ifdef SCIP_DEBUG 917 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "sci_%d_%d", i, j); 918 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, name, -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) ); 919 #else 920 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, "", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) ); 921 #endif 922 SCIP_CALL( SCIPaddVarsToRow(scip, row, nvars, tmpvars, tmpvals) ); 923 /*SCIP_CALL( SCIPprintRow(scip, row, NULL) ); */ 924 SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) ); 925 SCIP_CALL( SCIPreleaseRow(scip, &row) ); 926 ++(*ncuts); 927 928 #ifdef SHOW_SCI 929 SCIP_CALL( printSCI(scip, nspcons, nblocks, cases, i, j) ); 930 #endif 931 932 assert( SCIPisSumEQ(scip, weights[i-1][j-1], weight) ); 933 } 934 } 935 } 936 return SCIP_OKAY; 937 } 938 939 940 /** propagation method for a single packing or partitioning orbitope constraint */ 941 static 942 SCIP_RETCODE propagatePackingPartitioningCons( 943 SCIP* scip, /**< SCIP data structure */ 944 SCIP_CONS* cons, /**< constraint to be processed */ 945 SCIP_Bool* infeasible, /**< pointer to store TRUE, if the node can be cut off */ 946 int* nfixedvars /**< pointer to add up the number of found domain reductions */ 947 ) 948 { 949 SCIP_CONSDATA* consdata; 950 SCIP_VAR*** vars; 951 SCIP_ORBITOPETYPE orbitopetype; 952 int* firstnonzeros; 953 int* lastones; 954 int* frontiersteps; 955 int lastoneprevrow; 956 int nspcons; 957 int nblocks; 958 int nsteps; 959 int i; 960 int j; 961 962 assert( scip != NULL ); 963 assert( cons != NULL ); 964 assert( infeasible != NULL ); 965 assert( nfixedvars != NULL ); 966 967 *nfixedvars = 0; 968 969 if( !SCIPallowStrongDualReds(scip) ) 970 return SCIP_OKAY; 971 972 consdata = SCIPconsGetData(cons); 973 assert( consdata != NULL ); 974 assert( consdata->nspcons > 0 ); 975 assert( consdata->nblocks > 0 ); 976 assert( consdata->vars != NULL ); 977 978 nspcons = consdata->nspcons; 979 nblocks = consdata->nblocks; 980 vars = consdata->vars; 981 orbitopetype = consdata->orbitopetype; 982 983 assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING ); 984 985 /* fix upper right triangle if still necessary */ 986 if ( ! consdata->istrianglefixed ) 987 { 988 int nfixed = 0; 989 SCIP_CALL( fixTriangle(scip, cons, infeasible, &nfixed) ); 990 *nfixedvars += nfixed; 991 } 992 993 /* prepare further propagation */ 994 SCIP_CALL( SCIPallocBufferArray(scip, &firstnonzeros, nspcons) ); 995 SCIP_CALL( SCIPallocBufferArray(scip, &lastones, nspcons) ); 996 SCIP_CALL( SCIPallocBufferArray(scip, &frontiersteps, nblocks) ); 997 998 #ifdef PRINT_MATRIX 999 SCIPdebugMsg(scip, "Matrix:\n"); 1000 printMatrix(scip, consdata); 1001 #endif 1002 1003 /* propagate */ 1004 lastoneprevrow = 0; 1005 lastones[0] = 0; 1006 1007 if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING ) 1008 { 1009 /* packing case: if entry (0,0) is fixed to 0 */ 1010 if ( SCIPvarGetUbLocal(vars[0][0]) < 0.5 ) 1011 { 1012 lastoneprevrow = -1; 1013 lastones[0] = -1; 1014 } 1015 } 1016 nsteps = 0; 1017 1018 for (i = 1; i < nspcons; ++i) 1019 { 1020 int lastcolumn; 1021 int firstnonzeroinrow; 1022 int lastoneinrow; 1023 SCIP_Bool infrontier; 1024 1025 /* last column considered as part of the bar: */ 1026 lastcolumn = nblocks - 1; 1027 if ( lastcolumn > i ) 1028 lastcolumn = i; 1029 1030 /* find first position not fixed to 0 (partitioning) or fixed to 1 (packing) */ 1031 firstnonzeroinrow = -1; 1032 for (j = 0; j <= lastcolumn; ++j) 1033 { 1034 if ( orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING ) 1035 { 1036 /* partitioning case: if variable is not fixed to 0 */ 1037 if ( SCIPvarGetUbLocal(vars[i][j]) > 0.5 ) 1038 { 1039 firstnonzeroinrow = j; 1040 break; 1041 } 1042 } 1043 else 1044 { 1045 /* packing case: if variable is fixed to 1 */ 1046 if ( SCIPvarGetLbLocal(vars[i][j]) > 0.5 ) 1047 { 1048 firstnonzeroinrow = j; 1049 break; 1050 } 1051 } 1052 } 1053 /* if all variables are fixed to 0 in the partitioning case - should not happen */ 1054 if ( firstnonzeroinrow == -1 && orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING ) 1055 { 1056 SCIPdebugMsg(scip, " -> Infeasible node: all variables in row %d are fixed to 0.\n", i); 1057 *infeasible = TRUE; 1058 /* conflict should be analyzed by setppc constraint handler */ 1059 goto TERMINATE; 1060 } 1061 firstnonzeros[i] = firstnonzeroinrow; 1062 assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || firstnonzeroinrow >= 0 ); 1063 assert( -1 <= firstnonzeroinrow && firstnonzeroinrow <= lastcolumn ); 1064 1065 /* compute rightmost possible position for a 1 */ 1066 assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || 0 <= lastoneprevrow ); 1067 assert( lastoneprevrow <= lastcolumn ); 1068 1069 /* if we are at right border or if entry in column lastoneprevrow+1 is fixed to 0 */ 1070 infrontier = FALSE; 1071 assert( lastoneprevrow + 1 >= 0 ); 1072 if ( lastoneprevrow == nblocks-1 || SCIPvarGetUbLocal(vars[i][lastoneprevrow+1]) < 0.5 ) /*lint !e679*/ 1073 lastoneinrow = lastoneprevrow; 1074 else 1075 { 1076 lastoneinrow = lastoneprevrow + 1; 1077 frontiersteps[nsteps++] = i; 1078 infrontier = TRUE; 1079 } 1080 1081 /* store lastoneinrow */ 1082 assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || 0 <= lastoneinrow ); 1083 assert( lastoneinrow <= lastcolumn ); 1084 lastones[i] = lastoneinrow; 1085 1086 /* check whether we are infeasible */ 1087 if ( firstnonzeroinrow > lastoneinrow ) 1088 { 1089 int k; 1090 1091 #ifdef SCIP_DEBUG 1092 if ( orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING ) 1093 { 1094 SCIPdebugMsg(scip, " -> Infeasible node: row %d, leftmost nonzero at %d, rightmost 1 at %d\n", 1095 i, firstnonzeroinrow, lastoneinrow); 1096 } 1097 else 1098 { 1099 SCIPdebugMsg(scip, " -> Infeasible node: row %d, 1 at %d, rightmost position for 1 at %d\n", 1100 i, firstnonzeroinrow, lastoneinrow); 1101 } 1102 #endif 1103 /* check if conflict analysis is applicable */ 1104 if ( SCIPisConflictAnalysisApplicable(scip) ) 1105 { 1106 /* conflict analysis only applicable in SOLVING stage */ 1107 assert( SCIPgetStage(scip) == SCIP_STAGE_SOLVING || SCIPinProbing(scip) ); 1108 1109 /* perform conflict analysis */ 1110 SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) ); 1111 1112 if ( orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING ) 1113 { 1114 /* add bounds (variables fixed to 0) that result in the first nonzero entry */ 1115 for (j = 0; j <= lastcolumn; ++j) 1116 { 1117 /* add varaibles in row up to the first variable fixed to 0 */ 1118 if ( SCIPvarGetUbLocal(vars[i][j]) > 0.5 ) 1119 break; 1120 1121 assert( SCIPvarGetUbLocal(vars[i][j]) < 0.5 ); 1122 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][j]) ); 1123 } 1124 } 1125 else 1126 { 1127 /* add bounds that result in the last one - check top left entry for packing case */ 1128 if ( lastones[0] == -1 ) 1129 { 1130 assert( SCIPvarGetUbLocal(vars[0][0]) < 0.5 ); 1131 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[0][0]) ); 1132 } 1133 1134 /* mark variable fixed to 1 */ 1135 assert( SCIPvarGetLbLocal(vars[i][firstnonzeroinrow]) > 0.5 ); 1136 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][firstnonzeroinrow]) ); 1137 } 1138 1139 /* add bounds that result in the last one - pass through rows */ 1140 for (k = 1; k < i; ++k) 1141 { 1142 int l; 1143 l = lastones[k] + 1; 1144 1145 /* if the frontier has not moved and we are not beyond the matrix boundaries */ 1146 if ( l <= nblocks-1 && l <= k && lastones[k-1] == lastones[k] ) 1147 { 1148 assert( SCIPvarGetUbLocal(vars[k][l]) < 0.5 ); 1149 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[k][l]) ); 1150 } 1151 } 1152 SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) ); 1153 } 1154 1155 *infeasible = TRUE; 1156 goto TERMINATE; 1157 } 1158 1159 /* fix entries beyond the last possible position for a 1 in the row to 0 (see Lemma 1 in the paper) */ 1160 for (j = lastoneinrow+1; j <= lastcolumn; ++j) 1161 { 1162 /* if the entry is not yet fixed to 0 */ 1163 if ( SCIPvarGetUbLocal(vars[i][j]) > 0.5 ) 1164 { 1165 SCIP_Bool tightened; 1166 int inferInfo; 1167 1168 SCIPdebugMsg(scip, " -> Fixing entry (%d,%d) to 0.\n", i, j); 1169 1170 tightened = FALSE; 1171 1172 /* fix variable to 0 and store position of (i,lastoneinrow+1) for conflict resolution */ 1173 inferInfo = i * nblocks + lastoneinrow + 1; 1174 /* correction according to Lemma 1 in the paper (second part): store (i,lastoneinrow+2) */ 1175 if ( !infrontier ) 1176 ++inferInfo; 1177 SCIP_CALL( SCIPinferBinvarCons(scip, vars[i][j], FALSE, cons, inferInfo, infeasible, &tightened) ); 1178 1179 /* if entry is fixed to one -> infeasible node */ 1180 if ( *infeasible ) 1181 { 1182 SCIPdebugMsg(scip, " -> Infeasible node: row %d, 1 in column %d beyond rightmost position %d\n", i, j, lastoneinrow); 1183 /* check if conflict analysis is applicable */ 1184 if( SCIPisConflictAnalysisApplicable(scip) ) 1185 { 1186 int k; 1187 1188 /* conflict analysis only applicable in SOLVING stage */ 1189 assert(SCIPgetStage(scip) == SCIP_STAGE_SOLVING || SCIPinProbing(scip)); 1190 1191 /* perform conflict analysis */ 1192 SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) ); 1193 1194 /* add current bound */ 1195 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][j]) ); 1196 1197 /* add bounds that result in the last one - check top left entry for packing case */ 1198 if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING && lastones[0] == -1 ) 1199 { 1200 assert( SCIPvarGetUbLocal(vars[0][0]) < 0.5 ); 1201 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[0][0]) ); 1202 } 1203 1204 /* add bounds that result in the last one - pass through rows */ 1205 for (k = 1; k < i; ++k) 1206 { 1207 int l; 1208 l = lastones[k] + 1; 1209 1210 /* if the frontier has not moved and we are not beyond the matrix boundaries */ 1211 if ( l <= nblocks-1 && l <= k && lastones[k-1] == lastones[k] ) 1212 { 1213 assert( SCIPvarGetUbLocal(vars[k][l]) < 0.5 ); 1214 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[k][l]) ); 1215 } 1216 } 1217 SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) ); 1218 } 1219 1220 goto TERMINATE; 1221 } 1222 if ( tightened ) 1223 ++(*nfixedvars); 1224 } 1225 } 1226 1227 lastoneprevrow = lastoneinrow; 1228 } 1229 1230 /* check whether fixing any entry to 0 results in a contradiction -> loop through rows in frontiersteps (a.k.a. gamma) */ 1231 for (j = 0; j < nsteps; ++j) 1232 { 1233 int s; 1234 int lastoneinrow; 1235 1236 s = frontiersteps[j]; 1237 lastoneinrow = lastones[s]; 1238 /* note for packing case: if we are in a frontier step then lastoneinrow >= 0 */ 1239 assert( 0 <= lastoneinrow && lastoneinrow < nblocks ); 1240 1241 /* if entry is not fixed */ 1242 if ( SCIPvarGetLbLocal(vars[s][lastoneinrow]) < 0.5 && SCIPvarGetUbLocal(vars[s][lastoneinrow]) > 0.5 ) 1243 { 1244 int betaprev; 1245 betaprev = lastoneinrow - 1; 1246 1247 /* loop through rows below s */ 1248 for (i = s+1; i < nspcons; ++i) 1249 { 1250 int beta; 1251 1252 assert( betaprev + 1 >= 0 ); 1253 if ( betaprev == nblocks-1 || SCIPvarGetUbLocal(vars[i][betaprev+1]) < 0.5 ) /*lint !e679*/ 1254 beta = betaprev; 1255 else 1256 beta = betaprev + 1; 1257 assert( -1 <= beta && beta < nblocks ); 1258 1259 if ( firstnonzeros[i] > beta ) 1260 { 1261 SCIP_Bool tightened; 1262 int inferInfo; 1263 1264 /* can fix (s,lastoneinrow) (a.k.a (s,alpha)) to 1 1265 * (do not need to fix other entries to 0, since they will be 1266 * automatically fixed by SCIPtightenVarLb.) 1267 */ 1268 assert( SCIPvarGetLbLocal(vars[s][lastoneinrow]) < 0.5 ); 1269 SCIPdebugMsg(scip, " -> Fixing entry (%d,%d) to 1.\n", s, lastoneinrow); 1270 1271 tightened = FALSE; 1272 1273 /* store position (i,firstnonzeros[i]) */ 1274 inferInfo = nblocks * nspcons + i * nblocks + firstnonzeros[i]; 1275 SCIP_CALL( SCIPinferBinvarCons(scip, vars[s][lastoneinrow], TRUE, cons, inferInfo, infeasible, &tightened) ); 1276 1277 assert( !(*infeasible) ); 1278 if ( tightened ) 1279 ++(*nfixedvars); 1280 break; 1281 } 1282 betaprev = beta; 1283 } 1284 } 1285 } 1286 1287 TERMINATE: 1288 SCIPfreeBufferArray(scip, &frontiersteps); 1289 SCIPfreeBufferArray(scip, &lastones); 1290 SCIPfreeBufferArray(scip, &firstnonzeros); 1291 1292 return SCIP_OKAY; 1293 } 1294 1295 1296 /* Compute dynamic order of rows based on the branching decisions, i.e., the row of the first branching variable 1297 * determines the first row in the new ordering, the row of the second branching variable determines the second 1298 * row in the new ordering if it differs from the row of the first branching variable, and so on. 1299 * 1300 * The roworder array stores this reordering, where acutally only the first maxrowlabel entries encode the 1301 * reordering. 1302 */ 1303 static 1304 SCIP_RETCODE computeDynamicRowOrder( 1305 SCIP* scip, /**< SCIP pointer */ 1306 SCIP_HASHMAP* rowindexmap, /**< map of variables to indices in orbitope vars matrix */ 1307 SCIP_Bool* rowused, /**< bitset marking whether a row has been considered in the new order */ 1308 int* roworder, /**< reordering of the rows w.r.t. branching decisions */ 1309 int nrows, /**< number of rows in orbitope */ 1310 int ncols, /**< number of columns in orbitope */ 1311 int* maxrowlabel /**< maximum row label in ordering */ 1312 ) 1313 { 1314 int i; 1315 SCIP_NODE* node; 1316 int* branchdecisions; 1317 int nbranchdecision; 1318 1319 assert( scip != NULL ); 1320 assert( rowindexmap != NULL ); 1321 assert( roworder != NULL ); 1322 assert( nrows > 0 ); 1323 assert( maxrowlabel != NULL ); 1324 1325 SCIP_CALL( SCIPallocBufferArray(scip, &branchdecisions, nrows * ncols) ); 1326 nbranchdecision = 0; 1327 1328 /* get current node */ 1329 node = SCIPgetCurrentNode(scip); 1330 1331 /* follow path to the root (in the root no domains were changed due to branching) */ 1332 while ( SCIPnodeGetDepth(node) != 0 ) 1333 { 1334 SCIP_BOUNDCHG* boundchg; 1335 SCIP_DOMCHG* domchg; 1336 SCIP_VAR* branchvar; 1337 int nboundchgs; 1338 1339 /* get domain changes of current node */ 1340 domchg = SCIPnodeGetDomchg(node); 1341 assert( domchg != NULL ); 1342 1343 /* loop through all bound changes */ 1344 nboundchgs = SCIPdomchgGetNBoundchgs(domchg); 1345 for (i = 0; i < nboundchgs; ++i) 1346 { 1347 /* get bound change info */ 1348 boundchg = SCIPdomchgGetBoundchg(domchg, i); 1349 assert( boundchg != NULL ); 1350 1351 /* branching decisions have to be in the beginning of the bound change array */ 1352 if ( SCIPboundchgGetBoundchgtype(boundchg) != SCIP_BOUNDCHGTYPE_BRANCHING ) 1353 break; 1354 1355 /* get corresponding branching variable */ 1356 branchvar = SCIPboundchgGetVar(boundchg); 1357 1358 /* we only consider binary variables */ 1359 if ( SCIPvarGetType(branchvar) == SCIP_VARTYPE_BINARY ) 1360 { 1361 int rowidx; 1362 1363 /* make sure that branching variable is present in the orbitope */ 1364 if ( ! SCIPhashmapExists(rowindexmap, (void*) branchvar) ) 1365 continue; 1366 1367 rowidx = (int) (size_t) SCIPhashmapGetImage(rowindexmap, (void*) branchvar); 1368 branchdecisions[nbranchdecision++] = rowidx; 1369 } 1370 } 1371 1372 node = SCIPnodeGetParent(node); 1373 } 1374 1375 /* Insert branching decisions of current path into global row order. 1376 * Iterate in reverse order over branching decisions to get the path 1377 * from the root to the current node. 1378 */ 1379 for (i = nbranchdecision - 1; i >= 0; --i) 1380 { 1381 if ( ! rowused[branchdecisions[i]] ) 1382 { 1383 roworder[*maxrowlabel] = branchdecisions[i]; 1384 rowused[branchdecisions[i]] = TRUE; 1385 *maxrowlabel += 1; 1386 } 1387 } 1388 1389 SCIPfreeBufferArray(scip, &branchdecisions); 1390 1391 return SCIP_OKAY; 1392 } 1393 1394 1395 /* Compute lexicographically minimal face of the hypercube w.r.t. some coordinate fixing */ 1396 static 1397 SCIP_RETCODE findLexMinFace( 1398 SCIP_VAR*** vars, /**< variable matrix */ 1399 int** lexminfixes, /**< fixings characterzing lex-min face */ 1400 int* minfixedrowlexmin, /**< index of minimum fixed row for each column or 1401 * NULL (if in prop) */ 1402 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility has been 1403 * detected or NULL (if in resprop) */ 1404 int m, /**< number of rows in vars */ 1405 int n, /**< number of columns in vars */ 1406 int nrowsused, /**< number of rows considered in propagation */ 1407 SCIP_Bool resprop /**< whether we are in resprop (TRUE) or prop (FALSE) */ 1408 ) 1409 { 1410 int i; 1411 int j; 1412 *infeasible = FALSE; 1413 1414 assert( vars != NULL ); 1415 assert( lexminfixes != NULL ); 1416 assert( !resprop || minfixedrowlexmin != NULL ); 1417 assert( m > 0 ); 1418 assert( n > 0 ); 1419 assert( nrowsused > 0 ); 1420 assert( nrowsused <= m ); 1421 assert( infeasible != NULL ); 1422 1423 /* iterate over columns in reverse order and find the lexicographically minimal face 1424 * of the hypercube containing lexminfixes 1425 */ 1426 for (j = n - 2; j >= 0; --j) 1427 { 1428 int maxdiscriminating = m; 1429 int minfixed = -1; 1430 1431 /* fix free entries in column j to the corresponding value in column j + 1 and collect some information */ 1432 for (i = 0; i < nrowsused; ++i) 1433 { 1434 /* is row i j-discriminating? */ 1435 if ( minfixed == -1 && lexminfixes[i][j] != 0 && lexminfixes[i][j + 1] != 1 ) 1436 { 1437 assert( lexminfixes[i][j + 1] == 0 ); 1438 1439 maxdiscriminating = i; 1440 } 1441 1442 /* is row i j-fixed? */ 1443 if ( minfixed == -1 && lexminfixes[i][j] != lexminfixes[i][j + 1] && lexminfixes[i][j] != 2 ) 1444 { 1445 assert( lexminfixes[i][j + 1] != 2 ); 1446 1447 minfixed = i; 1448 1449 /* detect infeasibility */ 1450 if ( maxdiscriminating > minfixed ) 1451 { 1452 *infeasible = TRUE; 1453 1454 return SCIP_OKAY; 1455 } 1456 } 1457 } 1458 1459 /* ensure that column j is lexicographically not smaller than column j + 1 */ 1460 for (i = 0; i < nrowsused; ++i) 1461 { 1462 if ( lexminfixes[i][j] == 2 ) 1463 { 1464 if ( i < maxdiscriminating || minfixed == -1 ) 1465 lexminfixes[i][j] = lexminfixes[i][j + 1]; 1466 else if ( i == maxdiscriminating ) 1467 lexminfixes[i][j] = 1; 1468 else 1469 lexminfixes[i][j] = 0; 1470 } 1471 } 1472 1473 if ( resprop ) 1474 { 1475 assert( minfixedrowlexmin != NULL ); 1476 1477 /* store minimum fixed row */ 1478 if ( minfixed == -1 ) 1479 minfixedrowlexmin[j] = nrowsused - 1; 1480 else 1481 minfixedrowlexmin[j] = minfixed; 1482 1483 /* columns 1, ..., n-2 are contained in two columns (take the minimum) and 1484 * the minimum fixed row of column n-1 is determined by column n-2 */ 1485 if ( minfixedrowlexmin[j + 1] < minfixedrowlexmin[j] ) 1486 minfixedrowlexmin[j + 1] = minfixedrowlexmin[j]; 1487 } 1488 } 1489 1490 return SCIP_OKAY; 1491 } 1492 1493 1494 /* Compute lexicographically maximal face of the hypercube w.r.t. some coordinate fixing */ 1495 static 1496 SCIP_RETCODE findLexMaxFace( 1497 SCIP_VAR*** vars, /**< variable matrix */ 1498 int** lexmaxfixes, /**< fixings characterzing lex-max face */ 1499 int* minfixedrowlexmax, /**< index of minimum fixed row for each column or 1500 * NULL (if in prop) */ 1501 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility has been 1502 * detected or NULL (if in resprop) */ 1503 int m, /**< number of rows in vars */ 1504 int n, /**< number of columns in vars */ 1505 int nrowsused, /**< number of rows considered in propagation */ 1506 SCIP_Bool resprop /**< whether we are in resprop (TRUE) or prop (FALSE) */ 1507 ) 1508 { 1509 int i; 1510 int j; 1511 *infeasible = FALSE; 1512 1513 assert( vars != NULL ); 1514 assert( lexmaxfixes != NULL ); 1515 assert( !resprop || minfixedrowlexmax != NULL ); 1516 assert( m > 0 ); 1517 assert( n > 0 ); 1518 assert( nrowsused > 0 ); 1519 assert( nrowsused <= m ); 1520 assert( infeasible != NULL ); 1521 1522 for (j = 1; j < n; ++j) 1523 { 1524 int maxdiscriminating = m; 1525 int minfixed = -1; 1526 1527 /* fix free entries in column j to the corresponding value in column j - 1 and collect some information */ 1528 for (i = 0; i < nrowsused; ++i) 1529 { 1530 /* is row i j-discriminating? */ 1531 if ( minfixed == -1 && lexmaxfixes[i][j - 1] != 0 && lexmaxfixes[i][j] != 1 ) 1532 { 1533 assert( lexmaxfixes[i][j - 1] == 1 ); 1534 1535 maxdiscriminating = i; 1536 } 1537 1538 /* is row i j-fixed? */ 1539 if ( minfixed == -1 && lexmaxfixes[i][j - 1] != lexmaxfixes[i][j] && lexmaxfixes[i][j] != 2 ) 1540 { 1541 assert( lexmaxfixes[i][j - 1] != 2 ); 1542 1543 minfixed = i; 1544 1545 /* detect infeasibility */ 1546 if ( maxdiscriminating > minfixed ) 1547 { 1548 *infeasible = TRUE; 1549 1550 return SCIP_OKAY; 1551 } 1552 } 1553 } 1554 1555 /* ensure that column j is lexicographically not greater than column j - 1 */ 1556 for (i = 0; i < nrowsused; ++i) 1557 { 1558 if ( lexmaxfixes[i][j] == 2 ) 1559 { 1560 if ( i < maxdiscriminating || minfixed == -1 ) 1561 lexmaxfixes[i][j] = lexmaxfixes[i][j - 1]; 1562 else if ( i == maxdiscriminating ) 1563 lexmaxfixes[i][j] = 0; 1564 else 1565 lexmaxfixes[i][j] = 1; 1566 } 1567 } 1568 1569 if ( resprop ) 1570 { 1571 assert( minfixedrowlexmax != NULL ); 1572 1573 /* store minimum fixed row */ 1574 if ( minfixed == -1 ) 1575 minfixedrowlexmax[j] = nrowsused - 1; 1576 else 1577 minfixedrowlexmax[j] = minfixed; 1578 1579 /* columns 1, ..., n-2 are contained in two columns (take the minimum) and 1580 * the minimum fixed row of column 0 is determined by column 1 */ 1581 if ( minfixedrowlexmax[j - 1] < minfixedrowlexmax[j] ) 1582 minfixedrowlexmax[j - 1] = minfixedrowlexmax[j]; 1583 } 1584 } 1585 1586 return SCIP_OKAY; 1587 } 1588 1589 1590 /** propagation method for a single packing or partitioning orbitope constraint */ 1591 static 1592 SCIP_RETCODE propagateFullOrbitopeCons( 1593 SCIP* scip, /**< SCIP data structure */ 1594 SCIP_CONS* cons, /**< constraint to be processed */ 1595 SCIP_Bool* infeasible, /**< pointer to store TRUE, if the node can be cut off */ 1596 int* nfixedvars, /**< pointer to add up the number of found domain reductions */ 1597 SCIP_Bool dynamic /**< whether we use a dynamic propagation routine */ 1598 ) 1599 { 1600 SCIP_CONSDATA* consdata; 1601 SCIP_VAR*** vars; 1602 int** lexminfixes; 1603 int** lexmaxfixes; 1604 int* roworder; 1605 int nrowsused; 1606 int i; 1607 int j; 1608 int m; 1609 int n; 1610 1611 assert( scip != NULL ); 1612 assert( cons != NULL ); 1613 assert( infeasible != NULL ); 1614 assert( nfixedvars != NULL ); 1615 1616 *nfixedvars = 0; 1617 *infeasible = FALSE; 1618 1619 /* @todo Can the following be removed? */ 1620 if ( ! SCIPallowStrongDualReds(scip) ) 1621 return SCIP_OKAY; 1622 1623 /* do nothing if we use dynamic propagation and if we are in a probing node */ 1624 if ( dynamic && SCIPinProbing(scip) ) 1625 return SCIP_OKAY; 1626 1627 consdata = SCIPconsGetData(cons); 1628 assert( consdata != NULL ); 1629 assert( consdata->nspcons > 0 ); 1630 assert( consdata->nblocks > 0 ); 1631 assert( consdata->vars != NULL ); 1632 assert( consdata->orbitopetype == SCIP_ORBITOPETYPE_FULL ); 1633 1634 m = consdata->nspcons; 1635 n = consdata->nblocks; 1636 vars = consdata->vars; 1637 1638 /* determine order of orbitope rows dynamically by branching decisions */ 1639 if ( dynamic ) 1640 { 1641 SCIP_CALL( computeDynamicRowOrder(scip, consdata->rowindexmap, consdata->rowused, 1642 consdata->roworder, m, n, &(consdata->nrowsused)) ); 1643 1644 /* if no branching variable is contained in the full orbitope */ 1645 if ( consdata->nrowsused == 0 ) 1646 return SCIP_OKAY; 1647 1648 nrowsused = consdata->nrowsused; 1649 } 1650 else 1651 nrowsused = m; 1652 roworder = consdata->roworder; 1653 1654 /* Initialize lexicographically minimal matrix by fixed entries at the current node. 1655 * Free entries in the last column are set to 0. 1656 */ 1657 SCIP_CALL( SCIPallocBufferArray(scip, &lexminfixes, nrowsused) ); 1658 for (i = 0; i < nrowsused; ++i) 1659 { 1660 SCIP_CALL( SCIPallocBufferArray(scip, &lexminfixes[i], n) ); /*lint !e866*/ 1661 } 1662 1663 for (i = 0; i < nrowsused; ++i) 1664 { 1665 int origrow; 1666 1667 origrow = roworder[i]; 1668 1669 for (j = 0; j < n; ++j) 1670 { 1671 if ( SCIPvarGetLbLocal(vars[origrow][j]) > 0.5 ) 1672 lexminfixes[i][j] = 1; 1673 else if ( SCIPvarGetUbLocal(vars[origrow][j]) < 0.5 || j == n - 1 ) 1674 lexminfixes[i][j] = 0; 1675 else 1676 lexminfixes[i][j] = 2; 1677 } 1678 } 1679 1680 /* find lexicographically minimal face of hypercube containing lexmin fixes */ 1681 SCIP_CALL( findLexMinFace(vars, lexminfixes, NULL, infeasible, m, n, nrowsused, FALSE) ); 1682 1683 if ( *infeasible == TRUE ) 1684 goto FREELEXMIN; 1685 1686 /* Initialize lexicographically maximal matrix by fixed entries at the current node. 1687 * Free entries in the first column are set to 1. 1688 */ 1689 SCIP_CALL( SCIPallocBufferArray(scip, &lexmaxfixes, nrowsused) ); 1690 for (i = 0; i < nrowsused; ++i) 1691 { 1692 SCIP_CALL( SCIPallocBufferArray(scip, &lexmaxfixes[i], n) ); /*lint !e866*/ 1693 } 1694 1695 for (i = 0; i < nrowsused; ++i) 1696 { 1697 int origrow; 1698 1699 origrow = roworder[i]; 1700 1701 for (j = 0; j < n; ++j) 1702 { 1703 if ( SCIPvarGetUbLocal(vars[origrow][j]) < 0.5 ) 1704 lexmaxfixes[i][j] = 0; 1705 else if ( SCIPvarGetLbLocal(vars[origrow][j]) > 0.5 || j == 0 ) 1706 lexmaxfixes[i][j] = 1; 1707 else 1708 lexmaxfixes[i][j] = 2; 1709 } 1710 } 1711 1712 /* find lexicographically maximal face of hypercube containing lexmax fixes */ 1713 SCIP_CALL( findLexMaxFace(vars, lexmaxfixes, NULL, infeasible, m, n, nrowsused, FALSE) ); 1714 1715 if ( *infeasible ) 1716 goto FREELEXMAX; 1717 1718 /* Find for each column j the minimal row in which lexminfixes and lexmaxfixes differ. Fix all entries above this 1719 * row to the corresponding value in lexminfixes (or lexmaxfixes). 1720 */ 1721 for (j = 0; j < n; ++j) 1722 { 1723 for (i = 0; i < nrowsused; ++i) 1724 { 1725 int origrow; 1726 1727 origrow = roworder[i]; 1728 1729 if ( lexminfixes[i][j] != lexmaxfixes[i][j] ) 1730 break; 1731 1732 if ( SCIPvarGetLbLocal(vars[origrow][j]) < 0.5 && SCIPvarGetUbLocal(vars[origrow][j]) > 0.5 ) 1733 { 1734 SCIP_Bool success; 1735 1736 SCIP_CALL( SCIPinferBinvarCons(scip, vars[origrow][j], (SCIP_Bool) lexminfixes[i][j], 1737 cons, 0, infeasible, &success) ); 1738 1739 if ( success ) 1740 *nfixedvars += 1; 1741 } 1742 } 1743 } 1744 1745 FREELEXMAX: 1746 for (i = 0; i < nrowsused; ++i) 1747 SCIPfreeBufferArray(scip, &lexmaxfixes[i]); 1748 SCIPfreeBufferArray(scip, &lexmaxfixes); 1749 1750 FREELEXMIN: 1751 for (i = 0; i < nrowsused; ++i) 1752 SCIPfreeBufferArray(scip, &lexminfixes[i]); 1753 SCIPfreeBufferArray(scip, &lexminfixes); 1754 1755 return SCIP_OKAY; 1756 } 1757 1758 1759 /** propagation method for a single orbitope constraint */ 1760 static 1761 SCIP_RETCODE propagateCons( 1762 SCIP* scip, /**< SCIP data structure */ 1763 SCIP_CONS* cons, /**< constraint to be processed */ 1764 SCIP_Bool* infeasible, /**< pointer to store TRUE, if the node can be cut off */ 1765 int* nfixedvars /**< pointer to add up the number of found domain reductions */ 1766 ) 1767 { 1768 SCIP_CONSDATA* consdata; 1769 SCIP_ORBITOPETYPE orbitopetype; 1770 1771 assert( scip != NULL ); 1772 assert( cons != NULL ); 1773 assert( infeasible != NULL ); 1774 assert( nfixedvars != NULL ); 1775 1776 consdata = SCIPconsGetData(cons); 1777 assert( consdata != NULL ); 1778 1779 orbitopetype = consdata->orbitopetype; 1780 1781 if ( orbitopetype == SCIP_ORBITOPETYPE_FULL ) 1782 { 1783 SCIP_CALL( propagateFullOrbitopeCons(scip, cons, infeasible, nfixedvars, 1784 consdata->usedynamicprop && !consdata->ismodelcons) ); 1785 } 1786 else 1787 { 1788 assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING ); 1789 SCIP_CALL( propagatePackingPartitioningCons(scip, cons, infeasible, nfixedvars) ); 1790 } 1791 1792 return SCIP_OKAY; 1793 } 1794 1795 1796 /** Propagation conflict resolving method of propagator 1797 * 1798 * In this function we use that all variable reductions that can be found by the propagation algorithm 1799 * are only due to the fixed variables that are in or above the minimum fixed row of each pair of adjacent 1800 * columns of the lexmin and lexmax matrices. 1801 * 1802 * Since the storage of an integer is not enough to store the complete information about the fixing, 1803 * we have to use the linear time algorithm for finding the lexmin and lexmax 1804 * matrices and determine from this the minimum fixed rows. 1805 */ 1806 static 1807 SCIP_RETCODE resolvePropagationFullOrbitope( 1808 SCIP* scip, /**< SCIP data structure */ 1809 SCIP_CONSHDLR* conshdlr, /**< constraint handler of the corresponding constraint */ 1810 SCIP_CONS* cons, /**< constraint that inferred the bound change */ 1811 int inferinfo, /**< inference information */ 1812 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */ 1813 SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */ 1814 ) 1815 { /*lint --e{715}*/ 1816 SCIP_CONSDATA* consdata; 1817 SCIP_VAR*** vars; 1818 int** lexminfixes; 1819 int** lexmaxfixes; 1820 int* roworder; 1821 int* minfixedrowlexmin; 1822 int* minfixedrowlexmax; 1823 int i; 1824 int j; 1825 int m; 1826 int n; 1827 int nrowsused; 1828 SCIP_Bool dynamic; 1829 SCIP_Bool terminate; 1830 1831 *result = SCIP_DIDNOTFIND; 1832 1833 assert( scip != NULL ); 1834 assert( conshdlr != NULL ); 1835 assert( cons != NULL ); 1836 assert( result != NULL ); 1837 1838 consdata = SCIPconsGetData(cons); 1839 assert( consdata != NULL ); 1840 assert( consdata->nspcons > 0 ); 1841 assert( consdata->nblocks > 0 ); 1842 assert( consdata->vars != NULL ); 1843 assert( consdata->orbitopetype == SCIP_ORBITOPETYPE_FULL ); 1844 1845 dynamic = consdata->usedynamicprop && !consdata->ismodelcons; 1846 m = consdata->nspcons; 1847 n = consdata->nblocks; 1848 vars = consdata->vars; 1849 1850 if ( dynamic ) 1851 { 1852 assert( consdata->roworder != NULL ); 1853 assert( consdata->nrowsused > 0 ); 1854 1855 nrowsused = consdata->nrowsused; 1856 } 1857 else 1858 nrowsused = m; 1859 roworder = consdata->roworder; 1860 1861 assert( inferinfo <= consdata->nspcons ); 1862 1863 /* Initialize lexicographically minimal matrix by fixed entries at the current node. 1864 * Free entries in the last column are set to 0. 1865 */ 1866 SCIP_CALL( SCIPallocBufferArray(scip, &lexminfixes, nrowsused) ); 1867 for (i = 0; i < nrowsused; ++i) 1868 { 1869 SCIP_CALL( SCIPallocBufferArray(scip, &lexminfixes[i], n) ); /*lint !e866*/ 1870 } 1871 1872 /* store minimum fixed row for each column */ 1873 SCIP_CALL( SCIPallocBufferArray(scip, &minfixedrowlexmin, n) ); 1874 minfixedrowlexmin[n - 1] = -1; 1875 1876 for (i = 0; i < nrowsused; ++i) 1877 { 1878 int origrow; 1879 1880 origrow = roworder[i]; 1881 1882 for (j = 0; j < n; ++j) 1883 { 1884 if ( SCIPvarGetLbAtIndex(vars[origrow][j], bdchgidx, FALSE) > 0.5 ) 1885 lexminfixes[i][j] = 1; 1886 else if ( SCIPvarGetUbAtIndex(vars[origrow][j], bdchgidx, FALSE) < 0.5 || j == n - 1 ) 1887 lexminfixes[i][j] = 0; 1888 else 1889 lexminfixes[i][j] = 2; 1890 } 1891 } 1892 1893 /* find lexicographically minimal face of hypercube containing lexmin fixes */ 1894 SCIP_CALL( findLexMinFace(vars, lexminfixes, minfixedrowlexmin, &terminate, m, n, nrowsused, TRUE) ); 1895 1896 if ( terminate ) 1897 goto FREELEXMIN; 1898 1899 /* Initialize lexicographically maximal matrix by fixed entries at the current node. 1900 * Free entries in the first column are set to 1. 1901 */ 1902 SCIP_CALL( SCIPallocBufferArray(scip, &lexmaxfixes, nrowsused) ); 1903 for (i = 0; i < nrowsused; ++i) 1904 { 1905 SCIP_CALL( SCIPallocBufferArray(scip, &lexmaxfixes[i], n) ); /*lint !e866*/ 1906 } 1907 1908 /* store minimum fixed row for each column */ 1909 SCIP_CALL( SCIPallocBufferArray(scip, &minfixedrowlexmax, n) ); 1910 minfixedrowlexmax[0] = -1; 1911 1912 for (i = 0; i < nrowsused; ++i) 1913 { 1914 int origrow; 1915 1916 origrow = roworder[i]; 1917 1918 for (j = 0; j < n; ++j) 1919 { 1920 if ( SCIPvarGetUbAtIndex(vars[origrow][j], bdchgidx, FALSE) < 0.5 ) 1921 lexmaxfixes[i][j] = 0; 1922 else if ( SCIPvarGetLbAtIndex(vars[origrow][j], bdchgidx, FALSE) > 0.5 || j == 0 ) 1923 lexmaxfixes[i][j] = 1; 1924 else 1925 lexmaxfixes[i][j] = 2; 1926 } 1927 } 1928 1929 /* find lexicographically maximal face of hypercube containing lexmax fixes */ 1930 SCIP_CALL( findLexMaxFace(vars, lexmaxfixes, minfixedrowlexmax, &terminate, m, n, nrowsused, TRUE) ); 1931 1932 if ( terminate ) 1933 goto FREELEXMAX; 1934 1935 /* Find for each column j the minimal row in which lexminfixes and lexmaxfixes differ. Fix all entries above this 1936 * row to the corresponding value in lexminfixes (or lexmaxfixes). 1937 */ 1938 for (j = 0; j < n; ++j) 1939 { 1940 int ub = MAX(minfixedrowlexmin[j], minfixedrowlexmax[j]); 1941 1942 for (i = 0; i <= ub; ++i) 1943 { 1944 int origrow; 1945 1946 origrow = roworder[i]; 1947 1948 if ( SCIPvarGetLbAtIndex(vars[origrow][j], bdchgidx, FALSE) > 0.5 || 1949 SCIPvarGetUbAtIndex(vars[origrow][j], bdchgidx, FALSE) < 0.5 ) 1950 { 1951 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[origrow][j]) ); 1952 *result = SCIP_SUCCESS; 1953 } 1954 } 1955 } 1956 1957 FREELEXMAX: 1958 SCIPfreeBufferArray(scip, &minfixedrowlexmax); 1959 for (i = 0; i < nrowsused; ++i) 1960 SCIPfreeBufferArray(scip, &lexmaxfixes[i]); 1961 SCIPfreeBufferArray(scip, &lexmaxfixes); 1962 1963 FREELEXMIN: 1964 SCIPfreeBufferArray(scip, &minfixedrowlexmin); 1965 for (i = 0; i < nrowsused; ++i) 1966 SCIPfreeBufferArray(scip, &lexminfixes[i]); 1967 SCIPfreeBufferArray(scip, &lexminfixes); 1968 1969 return SCIP_OKAY; 1970 } 1971 1972 1973 /** Propagation conflict resolving method of propagator 1974 * 1975 * In this function we use that the propagation method above implicitly propagates SCIs, i.e., every 1976 * fixing can also be gotten via an SCI-fixing. 1977 * 1978 * Since the storage of an integer is not enough to store the complete information about the fixing 1979 * nor a complete shifted column, we have to use the linear time algorithm for SCIs. 1980 * 1981 * The inferinfo integer is set as follows: 1982 * 1983 * - If a shifted column is fixed to 0 and the corresponding bar does not necessarily has value 1 1984 * then we fix these entries to 0 and inferinfo is i * nblocks + j, where (i,j) is the leader of the 1985 * bar. The SCI depends on whether i is in Gamma or not (see Lemma 1 in the paper and the comments 1986 * above). 1987 * 1988 * - If a bar has value 1 and the shifted column has one entry that is not fixed, it can be fixed to 1989 * 1 and inferinfo is (nspcons*nblocks) + i * nblocks + j, where (i,j) is the leader of the bar; see 1990 * Proposition 1 (2c). 1991 */ 1992 static 1993 SCIP_RETCODE resolvePropagation( 1994 SCIP* scip, /**< SCIP data structure */ 1995 SCIP_CONS* cons, /**< constraint that inferred the bound change */ 1996 int inferinfo, /**< inference information */ 1997 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */ 1998 SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */ 1999 ) 2000 { /*lint --e{715}*/ 2001 SCIP_CONSDATA* consdata; 2002 SCIP_Real** vals; 2003 SCIP_Real** weights; 2004 SCIP_VAR*** vars; 2005 SCIP_ORBITOPETYPE orbitopetype; 2006 int** cases; 2007 2008 int i; 2009 int j; 2010 int nspcons; 2011 int nblocks; 2012 2013 assert( scip != NULL ); 2014 assert( cons != NULL ); 2015 assert( result != NULL ); 2016 2017 consdata = SCIPconsGetData(cons); 2018 assert( consdata != NULL ); 2019 assert( consdata->nspcons > 0 ); 2020 assert( consdata->nblocks > 0 ); 2021 assert( consdata->vars != NULL ); 2022 assert( consdata->vals != NULL ); 2023 assert( consdata->weights != NULL ); 2024 assert( consdata->cases != NULL ); 2025 assert( consdata->istrianglefixed ); 2026 2027 *result = SCIP_DIDNOTFIND; 2028 if ( ! consdata->resolveprop ) 2029 return SCIP_OKAY; 2030 2031 nspcons = consdata->nspcons; 2032 nblocks = consdata->nblocks; 2033 vars = consdata->vars; 2034 vals = consdata->vals; 2035 weights = consdata->weights; 2036 orbitopetype = consdata->orbitopetype; 2037 cases = consdata->cases; 2038 2039 SCIPdebugMsg(scip, "Propagation resolution method of orbitope constraint using orbitopal fixing\n"); 2040 2041 /* fill table */ 2042 for (i = 0; i < nspcons; ++i) 2043 { 2044 int lastcolumn; 2045 2046 /* last column considered as part of the bar: */ 2047 lastcolumn = nblocks - 1; 2048 if ( lastcolumn > i ) 2049 lastcolumn = i; 2050 for (j = 0; j <= lastcolumn; ++j) 2051 { 2052 /* if the variable was fixed to zero at conflict time */ 2053 if ( SCIPgetVarUbAtIndex(scip, vars[i][j], bdchgidx, FALSE) < 0.5 ) 2054 vals[i][j] = 0.0; 2055 else 2056 { 2057 /* if the variable was fixed to one at conflict time */ 2058 if ( SCIPgetVarLbAtIndex(scip, vars[i][j], bdchgidx, FALSE) > 0.5 ) 2059 vals[i][j] = 2.0; 2060 else 2061 vals[i][j] = 1.0; 2062 } 2063 } 2064 } 2065 2066 #ifdef PRINT_MATRIX 2067 SCIPdebugMsg(scip, "Matrix:\n"); 2068 printMatrix(scip, consdata); 2069 #endif 2070 2071 /* computation of table: this now minimizes the value of the shifted column */ 2072 assert( consdata->istrianglefixed ); 2073 computeSCTable(scip, nspcons, nblocks, weights, cases, vals); 2074 2075 /* if we fixed variables in the bar to zero */ 2076 assert( inferinfo >= 0 && inferinfo < 2 * nspcons * nblocks ); 2077 if ( inferinfo < nspcons * nblocks ) 2078 { 2079 int p1; 2080 int p2; 2081 #ifdef SCIP_DEBUG 2082 char str[SCIP_MAXSTRLEN]; 2083 char tmpstr[SCIP_MAXSTRLEN]; 2084 #endif 2085 2086 i = (int) (inferinfo / nblocks); 2087 j = inferinfo % nblocks; 2088 assert( 0 <= i && i < nspcons ); 2089 assert( 0 <= j && j < nblocks ); 2090 2091 /* find SCI with value 0 */ 2092 assert( weights[i-1][j-1] < 0.5 ); 2093 2094 SCIPdebugMsg(scip, " -> reason for x[%d][%d] = ... = x[%d][%d] = 0 was the following SC:\n", i, j, i, MIN(i,nblocks)); 2095 #ifdef SCIP_DEBUG 2096 str[0] = '\0'; 2097 #endif 2098 2099 p1 = i-1; 2100 p2 = j-1; 2101 do 2102 { 2103 assert( cases[p1][p2] != -1 ); 2104 assert( p1 >= 0 && p1 < i ); 2105 assert( p2 >= 0 && p2 < j ); 2106 2107 /* if case 1 */ 2108 if ( cases[p1][p2] == 1 ) 2109 --p2; /* decrease column */ 2110 else 2111 { 2112 /* case 2 or 3: */ 2113 assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 ); 2114 assert( SCIPgetVarUbAtIndex(scip, vars[p1][p2], bdchgidx, FALSE) < 0.5 ); 2115 SCIP_CALL( SCIPaddConflictUb(scip, vars[p1][p2], bdchgidx) ); 2116 *result = SCIP_SUCCESS; 2117 2118 #ifdef SCIP_DEBUG 2119 (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " (%d,%d)", p1, p2); 2120 (void) strncat(str, tmpstr, SCIP_MAXSTRLEN-1); 2121 #endif 2122 2123 if ( cases[p1][p2] == 3 ) 2124 break; 2125 } 2126 --p1; /* decrease row */ 2127 } 2128 while ( p1 >= 0 ); /* should always be true, i.e. the break should end the loop */ 2129 assert( cases[p1][p2] == 3 ); 2130 2131 #ifdef SCIP_DEBUG 2132 SCIPdebugMsg(scip, "%s\n", str); 2133 #endif 2134 } 2135 else 2136 { 2137 int k; 2138 int p1; 2139 int p2; 2140 #ifndef NDEBUG 2141 int pos1; 2142 int pos2; 2143 #endif 2144 #ifdef SCIP_DEBUG 2145 char str[SCIP_MAXSTRLEN]; 2146 char tmpstr[SCIP_MAXSTRLEN]; 2147 #endif 2148 2149 /* if we fixed a variable in the SC to 1 */ 2150 inferinfo -= nspcons * nblocks; 2151 i = (int) inferinfo / nblocks; 2152 j = inferinfo % nblocks; 2153 assert( 0 <= i && i < nspcons ); 2154 assert( 0 <= j && j < nblocks ); 2155 2156 /* In rare cases it might happen that we fixed a variable to 1, but the node later becomes infeasible by globally 2157 * fixing variables to 0. In this case, it might happen that we find a SC with value 0 instead of 1. We then 2158 * cannot use this SC to repropagate (and do not know how to reconstruct the original reasoning). */ 2159 if ( weights[i-1][j-1] > 0.5 && weights[i-1][j-1] < 1.5 ) 2160 { 2161 SCIPdebugMsg(scip, " -> reason for x[%d][%d] = 1 was the following SC:\n", i, j); 2162 #ifdef SCIP_DEBUG 2163 (void) SCIPsnprintf(str, SCIP_MAXSTRLEN, "SC:"); 2164 #endif 2165 2166 p1 = i-1; 2167 p2 = j-1; 2168 #ifndef NDEBUG 2169 pos1 = -1; 2170 pos2 = -1; 2171 #endif 2172 do 2173 { 2174 assert( cases[p1][p2] != -1 ); 2175 assert( p1 >= 0 && p1 < i ); 2176 assert( p2 >= 0 && p2 < j ); 2177 2178 /* if case 1 */ 2179 if ( cases[p1][p2] == 1 ) 2180 --p2; /* decrease column */ 2181 else 2182 { 2183 /* case 2 or 3: reason are formed by variables in SC fixed to 0 */ 2184 assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 ); 2185 if ( SCIPgetVarUbAtIndex(scip, vars[p1][p2], bdchgidx, FALSE) < 0.5 ) 2186 { 2187 SCIP_CALL( SCIPaddConflictUb(scip, vars[p1][p2], bdchgidx) ); 2188 *result = SCIP_SUCCESS; 2189 2190 #ifdef SCIP_DEBUG 2191 (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " (%d,%d)", p1, p2); 2192 (void) strncat(str, tmpstr, SCIP_MAXSTRLEN-1); 2193 #endif 2194 } 2195 #ifndef NDEBUG 2196 else 2197 { 2198 assert( SCIPgetVarLbAtIndex(scip, vars[p1][p2], bdchgidx, FALSE) < 0.5 ); 2199 assert( pos1 == -1 && pos2 == -1 ); 2200 pos1 = p1; 2201 pos2 = p2; 2202 } 2203 #endif 2204 if ( cases[p1][p2] == 3 ) 2205 break; 2206 } 2207 --p1; /* decrease row */ 2208 } 2209 while ( p1 >= 0 ); /* should always be true, i.e., the break should end the loop */ 2210 assert( cases[p1][p2] == 3 ); 2211 assert( pos1 >= 0 && pos2 >= 0 ); 2212 2213 /* distinguish partitioning/packing */ 2214 if ( orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING ) 2215 { 2216 /* partitioning case */ 2217 #ifdef SCIP_DEBUG 2218 (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " before bar: "); 2219 (void) strncat(str, tmpstr, SCIP_MAXSTRLEN-1); 2220 #endif 2221 /* add variables before the bar in the partitioning case */ 2222 for (k = 0; k < j; ++k) 2223 { 2224 assert( SCIPgetVarUbAtIndex(scip, vars[i][k], bdchgidx, FALSE) < 0.5 ); 2225 SCIP_CALL( SCIPaddConflictUb(scip, vars[i][k], bdchgidx) ); 2226 *result = SCIP_SUCCESS; 2227 #ifdef SCIP_DEBUG 2228 (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " (%d,%d)", i, k); 2229 (void) strncat(str, tmpstr, SCIP_MAXSTRLEN-1); 2230 #endif 2231 } 2232 2233 #ifdef SCIP_DEBUG 2234 SCIPdebugMsg(scip, "%s\n", str); 2235 #endif 2236 } 2237 else 2238 { 2239 /* packing case */ 2240 int lastcolumn; 2241 2242 /* last column considered as part of the bar: */ 2243 lastcolumn = nblocks - 1; 2244 if ( lastcolumn > i ) 2245 lastcolumn = i; 2246 2247 /* search for variable in the bar that is fixed to 1 in the packing case */ 2248 for (k = j; k <= lastcolumn; ++k) 2249 { 2250 if ( SCIPgetVarLbAtIndex(scip, vars[i][k], bdchgidx, FALSE) > 0.5 ) 2251 { 2252 SCIP_CALL( SCIPaddConflictLb(scip, vars[i][k], bdchgidx) ); 2253 *result = SCIP_SUCCESS; 2254 SCIPdebugMsg(scip, " and variable x[%d][%d] fixed to 1.\n", i, k); 2255 break; 2256 } 2257 } 2258 } 2259 } 2260 } 2261 2262 return SCIP_OKAY; 2263 } 2264 2265 2266 /** check packing/partitioning orbitope solution for feasibility */ 2267 static 2268 SCIP_RETCODE enfopsPackingPartitioningOrbitopeSolution( 2269 SCIP* scip, /**< SCIP data structure */ 2270 SCIP_CONS* cons, /**< pointer to orbitope constraint */ 2271 SCIP_RESULT* result /**< pointer to store the result of the enforcing call */ 2272 ) 2273 { 2274 SCIP_CONSDATA* consdata; 2275 SCIP_Real** weights; 2276 SCIP_Real** vals; 2277 int** cases; 2278 int nspcons; 2279 int nblocks; 2280 int i; 2281 int j; 2282 2283 assert( cons != NULL ); 2284 2285 consdata = SCIPconsGetData(cons); 2286 2287 assert( scip != NULL ); 2288 assert( consdata != NULL ); 2289 assert( consdata->nspcons > 0 ); 2290 assert( consdata->nblocks > 0 ); 2291 assert( consdata->vals != NULL ); 2292 assert( consdata->weights != NULL ); 2293 assert( consdata->cases != NULL ); 2294 2295 /* check for upper right triangle */ 2296 if ( ! consdata->istrianglefixed ) 2297 { 2298 SCIP_Bool infeasible = FALSE; 2299 int nfixedvars = 0; 2300 2301 SCIP_CALL( fixTriangle(scip, cons, &infeasible, &nfixedvars) ); 2302 if ( infeasible ) 2303 { 2304 *result = SCIP_CUTOFF; 2305 return SCIP_OKAY; 2306 } 2307 if ( nfixedvars > 0 ) 2308 { 2309 *result = SCIP_REDUCEDDOM; 2310 return SCIP_OKAY; 2311 } 2312 } 2313 2314 nspcons = consdata->nspcons; 2315 nblocks = consdata->nblocks; 2316 vals = consdata->vals; 2317 weights = consdata->weights; 2318 cases = consdata->cases; 2319 2320 /* get solution */ 2321 copyValues(scip, consdata, NULL); 2322 SCIPdebugMsg(scip, "Enforcing (pseudo solutions) for orbitope constraint <%s>\n", SCIPconsGetName(cons)); 2323 2324 /* compute table */ 2325 assert( consdata->istrianglefixed ); 2326 computeSCTable(scip, nspcons, nblocks, weights, cases, vals); 2327 2328 /* loop through rows */ 2329 for (i = 1; i < nspcons; ++i) 2330 { 2331 SCIP_Real bar = 0.0; 2332 int lastcolumn; 2333 2334 lastcolumn = nblocks - 1; 2335 2336 /* last column considered as part of the bar: */ 2337 if ( lastcolumn > i ) 2338 lastcolumn = i; 2339 2340 /* traverse row from right to left */ 2341 for (j = lastcolumn; j > 0; --j) 2342 { 2343 bar += vals[i][j]; 2344 assert( SCIPisIntegral(scip, vals[i][j]) ); 2345 2346 /* check whether weights[i-1][j-1] < bar (<=> bar - weights[i-1][j-1] > 0), i.e. cut is violated) */ 2347 if ( SCIPisGT(scip, bar - weights[i-1][j-1], 0.0) ) 2348 { 2349 SCIPdebugMsg(scip, "Solution is infeasible.\n"); 2350 *result = SCIP_INFEASIBLE; 2351 return SCIP_OKAY; 2352 } 2353 } 2354 } 2355 2356 return SCIP_OKAY; 2357 } 2358 2359 2360 /** check packing/partitioning orbitope solution for feasibility */ 2361 static 2362 SCIP_RETCODE checkPackingPartitioningOrbitopeSolution( 2363 SCIP* scip, /**< SCIP data structure */ 2364 SCIP_CONS* cons, /**< pointer to orbitope constraint */ 2365 SCIP_SOL* sol, /**< solution to be checked */ 2366 SCIP_RESULT* result, /**< pointer to store the result of the enforcing call */ 2367 SCIP_Bool printreason /**< whether reason for infeasibility should be printed */ 2368 ) 2369 { 2370 SCIP_CONSDATA* consdata; 2371 SCIP_VAR*** vars; 2372 SCIP_Real** vals; 2373 SCIP_Real** weights; 2374 int** cases; 2375 int nspcons; 2376 int nblocks; 2377 int i; 2378 int j; 2379 2380 /* get data of constraint */ 2381 assert( cons != 0 ); 2382 consdata = SCIPconsGetData(cons); 2383 2384 assert( consdata != NULL ); 2385 assert( consdata->nspcons > 0 ); 2386 assert( consdata->nblocks > 0 ); 2387 assert( consdata->vars != NULL ); 2388 assert( consdata->vals != NULL ); 2389 assert( consdata->weights != NULL ); 2390 assert( consdata->cases != NULL ); 2391 2392 nspcons = consdata->nspcons; 2393 nblocks = consdata->nblocks; 2394 vars = consdata->vars; 2395 vals = consdata->vals; 2396 weights = consdata->weights; 2397 cases = consdata->cases; 2398 2399 /* get solution */ 2400 copyValues(scip, consdata, sol); 2401 SCIPdebugMsg(scip, "Checking orbitope constraint <%s> ...\n", SCIPconsGetName(cons)); 2402 2403 /* check upper right triangle (if not yet fixed to zero or in debug mode */ 2404 #ifdef NDEBUG 2405 if ( ! consdata->istrianglefixed ) 2406 #endif 2407 { 2408 int diagsize; 2409 2410 /* get last row of triangle */ 2411 diagsize = nblocks; 2412 if ( nspcons < nblocks ) 2413 diagsize = nspcons; 2414 2415 /* check variables */ 2416 for (i = 0; i < diagsize; ++i) 2417 { 2418 for (j = i+1; j < nblocks; ++j) 2419 { 2420 if ( ! SCIPisFeasZero(scip, vals[i][j]) ) 2421 { 2422 if ( printreason ) 2423 SCIPinfoMessage(scip, NULL, "variable x[%d][%d] = %f on upper right nonzero.\n", i, j, vals[i][j]); 2424 *result = SCIP_INFEASIBLE; 2425 } 2426 } 2427 } 2428 } 2429 2430 /* compute table */ 2431 computeSCTable(scip, nspcons, nblocks, weights, cases, vals); 2432 2433 /* loop through rows */ 2434 for (i = 1; i < nspcons; ++i) 2435 { 2436 SCIP_Real bar; 2437 int lastcolumn; 2438 2439 lastcolumn = nblocks - 1; 2440 bar = 0.0; 2441 /* last column considered as part of the bar: */ 2442 if ( lastcolumn > i ) 2443 lastcolumn = i; 2444 2445 /* traverse row from right to left */ 2446 for (j = lastcolumn; j > 0; --j) 2447 { 2448 bar += vals[i][j]; 2449 assert( SCIPisFeasIntegral(scip, vals[i][j]) ); 2450 2451 /* check whether weights[i-1][j-1] < bar (<=> bar - weights[i-1][j-1] > 0), i.e. cut is violated) */ 2452 if ( SCIPisGT(scip, bar - weights[i-1][j-1], 0.0) ) 2453 { 2454 SCIPdebugMsg(scip, "Solution is infeasible.\n"); 2455 *result = SCIP_INFEASIBLE; 2456 2457 if ( printreason ) 2458 { 2459 int l; 2460 int p1; 2461 int p2; 2462 2463 SCIPinfoMessage(scip, NULL, "violated SCI: bar("); 2464 2465 /* first output bar */ 2466 for (l = j; l < nblocks; ++l) 2467 SCIPinfoMessage(scip, NULL, "<%s> (%f)", SCIPvarGetName(vars[i][l]), consdata->vals[i][l]); 2468 2469 SCIPinfoMessage(scip, NULL, ") SC("); 2470 2471 /* output shifted column */ 2472 p1 = i-1; 2473 p2 = j-1; 2474 do 2475 { 2476 assert( cases[p1][p2] != -1 ); 2477 assert( p1 >= 0 && p1 < i ); 2478 assert( p2 >= 0 && p2 < j ); 2479 2480 /* if case 1 */ 2481 if (cases[p1][p2] == 1) 2482 --p2; /* decrease column */ 2483 else 2484 { 2485 /* case 2 or 3: */ 2486 assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 ); 2487 SCIPinfoMessage(scip, NULL, "<%s> (%f)", SCIPvarGetName(vars[p1][p2]), consdata->vals[p1][p2]); 2488 if ( cases[p1][p2] == 3 ) 2489 break; 2490 } 2491 --p1; /* decrease row */ 2492 } 2493 while ( p1 >= 0 ); /* should always be true, i.e. the break should end the loop */ 2494 assert( cases[p1][p2] == 3 ); 2495 2496 SCIPinfoMessage(scip, NULL, ")"); 2497 } 2498 } 2499 } 2500 } 2501 2502 return SCIP_OKAY; 2503 } 2504 2505 2506 /** check full orbitope solution for feasibility */ 2507 static 2508 SCIP_RETCODE checkFullOrbitopeSolution( 2509 SCIP* scip, /**< SCIP data structure */ 2510 SCIP_CONS* cons, /**< constraint to process */ 2511 SCIP_SOL* sol, /**< solution to be checked */ 2512 SCIP_Bool printreason, /**< whether reason for infeasibility should be printed */ 2513 SCIP_Bool* feasible /**< memory address to store whether solution is feasible */ 2514 ) 2515 { 2516 SCIP_CONSDATA* consdata; 2517 SCIP_VAR*** vars; 2518 SCIP_VAR** vars1; 2519 SCIP_VAR** vars2; 2520 int nrows; 2521 int ncols; 2522 int j; 2523 int i; 2524 2525 assert( scip != NULL ); 2526 assert( cons != NULL ); 2527 assert( feasible != NULL ); 2528 2529 consdata = SCIPconsGetData(cons); 2530 2531 assert( consdata != NULL ); 2532 assert( consdata->vars != NULL ); 2533 assert( consdata->nspcons > 0 ); 2534 assert( consdata->nblocks > 0 ); 2535 assert( ! consdata->ismodelcons ); /* non-model constraints are never checked */ 2536 2537 vars = consdata->vars; 2538 nrows = consdata->nspcons; 2539 ncols = consdata->nblocks; 2540 2541 SCIP_CALL( SCIPallocBufferArray(scip, &vars1, nrows) ); 2542 SCIP_CALL( SCIPallocBufferArray(scip, &vars2, nrows) ); 2543 2544 /* iterate over adjacent columns of orbitope and check whether the first column in this 2545 * column pair is lexicographically not smaller than the second column in the pair */ 2546 *feasible = TRUE; 2547 for (j = 1; j < ncols && *feasible; ++j) 2548 { 2549 for (i = 0; i < nrows; ++i) 2550 { 2551 vars1[i] = vars[i][j - 1]; 2552 vars2[i] = vars[i][j]; 2553 } 2554 2555 SCIP_CALL( SCIPcheckSolutionOrbisack(scip, sol, vars1, vars2, nrows, printreason, feasible) ); 2556 } 2557 2558 SCIPfreeBufferArray(scip, &vars2); 2559 SCIPfreeBufferArray(scip, &vars1); 2560 2561 return SCIP_OKAY; 2562 } 2563 2564 2565 /** separate orbisack cover inequalities */ 2566 static 2567 SCIP_RETCODE separateCoversOrbisack( 2568 SCIP* scip, /**< SCIP data structure */ 2569 SCIP_CONS* cons, /**< constraint to process */ 2570 SCIP_SOL* sol, /**< solution to separate (NULL for the LP solution) */ 2571 SCIP_Bool dynamic, /**< whether we use a dynamic row order */ 2572 int* ngen, /**< pointer to store number of generated cuts */ 2573 SCIP_Bool* infeasible /**< pointer to store whether infeasibility has been detected */ 2574 ) 2575 { 2576 SCIP_CONSDATA* consdata; 2577 SCIP_VAR*** vars; 2578 int* roworder; 2579 int nrowsused; 2580 int nrows; 2581 int ncols; 2582 int i; 2583 int j; 2584 int origrow; 2585 SCIP_Real rhs; 2586 SCIP_Real lhs; 2587 SCIP_Real* coeffs1; 2588 SCIP_Real* coeffs2; 2589 2590 assert( scip != NULL ); 2591 assert( cons != NULL ); 2592 assert( ngen != NULL ); 2593 assert( infeasible != NULL ); 2594 2595 *ngen = 0; 2596 *infeasible = FALSE; 2597 2598 /* get basic data */ 2599 consdata = SCIPconsGetData(cons); 2600 assert( consdata != NULL ); 2601 2602 vars = consdata->vars; 2603 nrows = consdata->nspcons; 2604 ncols = consdata->nblocks; 2605 nrowsused = dynamic ? consdata->nrowsused : nrows; 2606 roworder = consdata->roworder; 2607 2608 /* allocate memory for cover inequalities */ 2609 SCIP_CALL( SCIPallocBufferArray(scip, &coeffs1, nrowsused) ); 2610 SCIP_CALL( SCIPallocBufferArray(scip, &coeffs2, nrowsused) ); 2611 2612 lhs = 0.0; 2613 rhs = 0.0; 2614 2615 /* separate orbisack cover inequalities for adjacent columns */ 2616 for (j = 0; j < ncols - 1 && ! *infeasible; ++j) 2617 { 2618 SCIP_Real rowval; 2619 2620 for (i = 0; i < nrowsused; ++i) 2621 { 2622 origrow = roworder[i]; 2623 2624 assert( origrow >= 0 ); 2625 assert( origrow < nrows ); 2626 2627 rowval = SCIPgetSolVal(scip, sol, vars[origrow][j + 1]) - SCIPgetSolVal(scip, sol, vars[origrow][j]); 2628 2629 /* check whether cover inequality is violated */ 2630 if ( SCIPisEfficacious(scip, rowval + lhs - rhs) ) 2631 { 2632 SCIP_ROW* row; 2633 int k; 2634 2635 /* set coefficients for current inequality */ 2636 coeffs1[i] = -1.0; 2637 coeffs2[i] = 1.0; 2638 2639 /* add violated orbisack cover inequality */ 2640 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "orbisackcover", -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) ); 2641 SCIP_CALL( SCIPcacheRowExtensions(scip, row) ); 2642 2643 for (k = 0; k <= i; ++k) 2644 { 2645 int origrow2; 2646 2647 origrow2 = roworder[k]; 2648 2649 SCIP_CALL( SCIPaddVarToRow(scip, row, vars[origrow2][j], coeffs1[k]) ); 2650 SCIP_CALL( SCIPaddVarToRow(scip, row, vars[origrow2][j + 1], coeffs2[k]) ); 2651 } 2652 SCIP_CALL( SCIPflushRowExtensions(scip, row) ); 2653 2654 SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) ); 2655 #ifdef SCIP_DEBUG 2656 SCIP_CALL( SCIPprintRow(scip, row, NULL) ); 2657 #endif 2658 SCIP_CALL( SCIPreleaseRow(scip, &row) ); 2659 2660 *ngen += 1; 2661 if ( *infeasible ) 2662 break; 2663 2664 /* reset coefficients for next inequality */ 2665 coeffs1[i] = 0.0; 2666 coeffs2[i] = 0.0; 2667 } 2668 2669 /* add argmax( 1 - vals[i][0], vals[i][1] ) as coefficient and ensure that both vars1[0] and vars2[0] are 2670 * contained in the LIFTED cover inequality */ 2671 rowval = SCIPgetSolVal(scip, sol, vars[origrow][j]) + SCIPgetSolVal(scip, sol, vars[origrow][j + 1]); 2672 if ( SCIPisEfficacious(scip, 1.0 - rowval) ) 2673 { 2674 coeffs1[i] = -1.0; 2675 coeffs2[i] = 0.0; 2676 lhs -= SCIPgetSolVal(scip, sol, vars[origrow][j]); 2677 2678 /* apply lifting? */ 2679 if ( i == 0 ) 2680 { 2681 coeffs2[i] = 1.0; 2682 lhs += SCIPgetSolVal(scip, sol, vars[origrow][j + 1]); 2683 } 2684 } 2685 else 2686 { 2687 coeffs1[i] = 0.0; 2688 coeffs2[i] = 1.0; 2689 lhs += SCIPgetSolVal(scip, sol, vars[origrow][j]); 2690 rhs += 1.0; 2691 2692 /* apply lifting? */ 2693 if ( i == 0 ) 2694 { 2695 coeffs1[i] = -1.0; 2696 lhs -= SCIPgetSolVal(scip, sol, vars[origrow][j]); 2697 rhs -= 1.0; 2698 } 2699 } 2700 } 2701 } 2702 2703 SCIPfreeBufferArray(scip, &coeffs1); 2704 SCIPfreeBufferArray(scip, &coeffs2); 2705 2706 return SCIP_OKAY; 2707 } 2708 2709 2710 /** separate or enforce constraints */ 2711 static 2712 SCIP_RETCODE separateConstraints( 2713 SCIP* scip, /**< SCIP data structure */ 2714 SCIP_CONSHDLR* conshdlr, /**< constraint handler */ 2715 SCIP_CONS** conss, /**< constraints to process */ 2716 int nconss, /**< number of constraints */ 2717 int nusefulconss, /**< number of useful (non-obsolete) constraints to process */ 2718 SCIP_SOL* sol, /**< solution to separate (NULL for the LP solution) */ 2719 SCIP_RESULT* result, /**< pointer to store the result (should be initialized) */ 2720 SCIP_Bool enforce /**< whether we enforce orbitope constraints */ 2721 ) 2722 { 2723 SCIP_Bool infeasible = FALSE; 2724 int nfixedvars = 0; 2725 int ncuts = 0; 2726 int c; 2727 2728 assert( scip != NULL ); 2729 assert( conshdlr != NULL ); 2730 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 2731 assert( result != NULL ); 2732 2733 /* loop through constraints */ 2734 for (c = 0; c < nconss && ! infeasible; c++) 2735 { 2736 SCIP_CONSHDLRDATA* conshdlrdata; 2737 SCIP_CONSDATA* consdata; 2738 int nconsfixedvars = 0; 2739 int nconscuts = 0; 2740 SCIP_ORBITOPETYPE orbitopetype; 2741 2742 assert( conss[c] != NULL ); 2743 2744 /* get data of constraint */ 2745 consdata = SCIPconsGetData(conss[c]); 2746 assert( consdata != NULL ); 2747 2748 /* do not enforce non-model constraints */ 2749 if ( enforce && !consdata->ismodelcons ) 2750 continue; 2751 2752 /* get solution */ 2753 copyValues(scip, consdata, sol); 2754 2755 /* separate */ 2756 orbitopetype = consdata->orbitopetype; 2757 2758 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2759 if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING ) 2760 { 2761 SCIP_CALL( separateSCIs(scip, conshdlr, conss[c], consdata, &infeasible, &nconsfixedvars, &nconscuts) ); 2762 nfixedvars += nconsfixedvars; 2763 } 2764 else if ( conshdlrdata->sepafullorbitope ) 2765 { 2766 SCIP_CALL( separateCoversOrbisack(scip, conss[c], sol, consdata->usedynamicprop && !consdata->ismodelcons, &nconscuts, &infeasible) ); 2767 } 2768 ncuts += nconscuts; 2769 2770 /* stop after the useful constraints if we found cuts of fixed variables */ 2771 if ( c >= nusefulconss && (ncuts > 0 || nfixedvars > 0) ) 2772 break; 2773 } 2774 2775 if ( infeasible ) 2776 { 2777 SCIPdebugMsg(scip, "Infeasible node.\n"); 2778 *result = SCIP_CUTOFF; 2779 } 2780 else if ( nfixedvars > 0 ) 2781 { 2782 SCIPdebugMsg(scip, "Fixed %d variables.\n", nfixedvars); 2783 *result = SCIP_REDUCEDDOM; 2784 } 2785 else if ( ncuts > 0 ) 2786 { 2787 SCIPdebugMsg(scip, "Separated %dinequalities.\n", ncuts); 2788 *result = SCIP_SEPARATED; 2789 } 2790 else 2791 { 2792 SCIPdebugMsg(scip, "No violated inequality found during separation.\n"); 2793 } 2794 2795 return SCIP_OKAY; 2796 } 2797 2798 2799 /** check whether all variables in an orbitope constraint are fixed */ 2800 static 2801 SCIP_RETCODE checkRedundantCons( 2802 SCIP* scip, /**< SCIP data structure */ 2803 SCIP_CONS* cons, /**< constraint to be processed */ 2804 SCIP_Bool* redundant /**< pointer to store whether constraint is redundant (contains no active vars) */ 2805 ) 2806 { 2807 SCIP_CONSDATA* consdata; 2808 SCIP_VAR*** vars; 2809 int i; 2810 int j; 2811 int nrows; 2812 int ncols; 2813 2814 assert( scip != NULL ); 2815 assert( cons != NULL ); 2816 assert( redundant != NULL ); 2817 2818 *redundant = FALSE; 2819 2820 consdata = SCIPconsGetData(cons); 2821 assert( consdata != NULL ); 2822 assert( consdata->vars != NULL ); 2823 assert( consdata->nspcons > 0 ); 2824 assert( consdata->nblocks > 0 ); 2825 2826 vars = consdata->vars; 2827 nrows = consdata->nspcons; 2828 ncols = consdata->nblocks; 2829 2830 /* check whether there exists an active variable in the orbitope */ 2831 for (i = 0; i < nrows; ++i) 2832 { 2833 for (j = 0; j < ncols; ++j) 2834 { 2835 if ( SCIPvarIsActive(vars[i][j]) ) 2836 return SCIP_OKAY; 2837 } 2838 } 2839 2840 *redundant = TRUE; 2841 2842 return SCIP_OKAY; 2843 } 2844 2845 2846 /* 2847 * Callback methods of constraint handler 2848 */ 2849 2850 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 2851 static 2852 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyOrbitope) 2853 { /*lint --e{715}*/ 2854 assert(scip != NULL); 2855 assert(conshdlr != NULL); 2856 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2857 2858 /* call inclusion method of constraint handler */ 2859 SCIP_CALL( SCIPincludeConshdlrOrbitope(scip) ); 2860 2861 *valid = TRUE; 2862 2863 return SCIP_OKAY; 2864 } 2865 2866 /** frees constraint handler */ 2867 static 2868 SCIP_DECL_CONSFREE(consFreeOrbitope) 2869 { /*lint --e{715}*/ 2870 SCIP_CONSHDLRDATA* conshdlrdata; 2871 2872 assert( scip != 0 ); 2873 assert( conshdlr != 0 ); 2874 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 2875 2876 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2877 assert( conshdlrdata != NULL ); 2878 2879 SCIPfreeBlockMemory(scip, &conshdlrdata); 2880 2881 return SCIP_OKAY; 2882 } 2883 2884 /** frees specific constraint data */ 2885 static 2886 SCIP_DECL_CONSDELETE(consDeleteOrbitope) 2887 { /*lint --e{715}*/ 2888 assert(conshdlr != NULL); 2889 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2890 2891 SCIP_CALL( consdataFree(scip, consdata) ); 2892 2893 return SCIP_OKAY; 2894 } 2895 2896 /** transforms constraint data into data belonging to the transformed problem */ 2897 static 2898 SCIP_DECL_CONSTRANS(consTransOrbitope) 2899 { /*lint --e{715}*/ 2900 SCIP_CONSDATA* sourcedata; 2901 SCIP_CONSDATA* targetdata; 2902 2903 assert(conshdlr != NULL); 2904 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2905 assert(SCIPgetStage(scip) == SCIP_STAGE_TRANSFORMING); 2906 assert(sourcecons != NULL); 2907 assert(targetcons != NULL); 2908 2909 sourcedata = SCIPconsGetData(sourcecons); 2910 assert(sourcedata != NULL); 2911 2912 /* create linear constraint data for target constraint */ 2913 SCIP_CALL( consdataCreate(scip, &targetdata, sourcedata->vars, sourcedata->nspcons, sourcedata->nblocks, 2914 sourcedata->orbitopetype, sourcedata->resolveprop, sourcedata->usedynamicprop, sourcedata->ismodelcons, 2915 sourcedata->mayinteract) ); 2916 2917 /* create target constraint */ 2918 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata, 2919 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons), 2920 SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons), 2921 SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons), 2922 SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) ); 2923 2924 return SCIP_OKAY; 2925 } 2926 2927 /** separation method of constraint handler for LP solutions */ 2928 static 2929 SCIP_DECL_CONSSEPALP(consSepalpOrbitope) 2930 { /*lint --e{715}*/ 2931 assert( scip != NULL ); 2932 assert( result != NULL ); 2933 2934 SCIPdebugMsg(scip, "Separation of orbitope constraint handler <%s> for LP solution.\n", SCIPconshdlrGetName(conshdlr)); 2935 2936 *result = SCIP_DIDNOTRUN; 2937 2938 /* if solution is integer, skip separation */ 2939 if ( SCIPgetNLPBranchCands(scip) <= 0 ) 2940 return SCIP_OKAY; 2941 2942 *result = SCIP_DIDNOTFIND; 2943 2944 /* separate constraints */ 2945 SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, NULL, result, FALSE) ); 2946 2947 return SCIP_OKAY; 2948 } 2949 2950 /** separation method of constraint handler for arbitrary primal solutions */ 2951 static 2952 SCIP_DECL_CONSSEPASOL(consSepasolOrbitope) 2953 { /*lint --e{715}*/ 2954 assert( scip != NULL ); 2955 assert( result != NULL ); 2956 2957 SCIPdebugMsg(scip, "Separation of orbitope constraint handler <%s> for primal solution.\n", SCIPconshdlrGetName(conshdlr)); 2958 2959 *result = SCIP_DIDNOTFIND; 2960 2961 /* separate constraints */ 2962 SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, sol, result, FALSE) ); 2963 2964 return SCIP_OKAY; 2965 } 2966 2967 2968 /** constraint enforcing method of constraint handler for LP solutions */ 2969 static 2970 SCIP_DECL_CONSENFOLP(consEnfolpOrbitope) 2971 { /*lint --e{715}*/ 2972 assert( scip != NULL ); 2973 assert( result != NULL ); 2974 2975 /* we have a negative priority, so we should come after the integrality conshdlr */ 2976 assert( SCIPgetNLPBranchCands(scip) == 0 ); 2977 2978 SCIPdebugMsg(scip, "Enforcement for orbitope constraint handler <%s> for LP solution.\n", SCIPconshdlrGetName(conshdlr)); 2979 2980 *result = SCIP_FEASIBLE; 2981 2982 /* separate constraints */ 2983 SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, NULL, result, TRUE) ); 2984 2985 return SCIP_OKAY; 2986 } 2987 2988 2989 /** constraint enforcing method of constraint handler for relaxation solutions */ 2990 static 2991 SCIP_DECL_CONSENFORELAX(consEnforelaxOrbitope) 2992 { /*lint --e{715}*/ 2993 assert( result != NULL ); 2994 assert( scip != NULL ); 2995 2996 SCIPdebugMsg(scip, "Enforcement for orbitope constraint handler <%s> for relaxation solution.\n", SCIPconshdlrGetName(conshdlr)); 2997 2998 *result = SCIP_FEASIBLE; 2999 3000 /* separate constraints */ 3001 SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, sol, result, TRUE) ); 3002 3003 return SCIP_OKAY; 3004 } 3005 3006 3007 /** constraint enforcing method of constraint handler for pseudo solutions */ 3008 static 3009 SCIP_DECL_CONSENFOPS(consEnfopsOrbitope) 3010 { /*lint --e{715}*/ 3011 int c; 3012 3013 assert( scip != NULL ); 3014 assert( conshdlr != NULL ); 3015 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 3016 assert( result != NULL ); 3017 3018 *result = SCIP_FEASIBLE; 3019 if ( objinfeasible || solinfeasible ) 3020 return SCIP_OKAY; 3021 3022 /* loop through constraints */ 3023 for (c = 0; c < nconss; ++c) 3024 { 3025 SCIP_CONS* cons; 3026 SCIP_CONSDATA* consdata; 3027 SCIP_ORBITOPETYPE orbitopetype; 3028 SCIP_Bool feasible; 3029 3030 /* get data of constraint */ 3031 cons = conss[c]; 3032 assert( cons != 0 ); 3033 consdata = SCIPconsGetData(cons); 3034 3035 assert( consdata != NULL ); 3036 3037 /* do not enforce non-model constraints */ 3038 if ( !consdata->ismodelcons ) 3039 continue; 3040 3041 orbitopetype = consdata->orbitopetype; 3042 3043 if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING ) 3044 { 3045 SCIP_CALL( enfopsPackingPartitioningOrbitopeSolution(scip, cons, result) ); 3046 } 3047 else 3048 { 3049 SCIP_CALL( checkFullOrbitopeSolution(scip, cons, NULL, FALSE, &feasible) ); 3050 3051 if ( ! feasible ) 3052 *result = SCIP_INFEASIBLE; 3053 } 3054 3055 if ( *result == SCIP_INFEASIBLE ) 3056 break; 3057 } 3058 3059 return SCIP_OKAY; 3060 } 3061 3062 3063 /** feasibility check method of constraint handler for integral solutions */ 3064 static 3065 SCIP_DECL_CONSCHECK(consCheckOrbitope) 3066 { /*lint --e{715}*/ 3067 int c; 3068 SCIP_CONSDATA* consdata; 3069 SCIP_ORBITOPETYPE orbitopetype; 3070 SCIP_Bool feasible; 3071 3072 assert( scip != NULL ); 3073 assert( conshdlr != NULL ); 3074 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 3075 assert( result != NULL ); 3076 3077 *result = SCIP_FEASIBLE; 3078 3079 /* loop through constraints */ 3080 for( c = 0; c < nconss && (*result == SCIP_FEASIBLE || completely); ++c ) 3081 { 3082 assert( conss[c] != 0 ); 3083 consdata = SCIPconsGetData(conss[c]); 3084 3085 assert( consdata != NULL ); 3086 3087 /* do not check non-model constraints */ 3088 if ( !consdata->ismodelcons ) 3089 continue; 3090 3091 orbitopetype = consdata->orbitopetype; 3092 3093 if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING ) 3094 { 3095 SCIP_CALL( checkPackingPartitioningOrbitopeSolution(scip, conss[c], sol, result, printreason) ); 3096 } 3097 else 3098 { 3099 SCIP_CALL( checkFullOrbitopeSolution(scip, conss[c], sol, printreason, &feasible) ); 3100 3101 if ( ! feasible ) 3102 *result = SCIP_INFEASIBLE; 3103 } 3104 } 3105 SCIPdebugMsg(scip, "Solution is feasible.\n"); 3106 3107 return SCIP_OKAY; 3108 } 3109 3110 3111 /** domain propagation method of constraint handler */ 3112 static 3113 SCIP_DECL_CONSPROP(consPropOrbitope) 3114 { /*lint --e{715}*/ 3115 SCIP_Bool infeasible = FALSE; 3116 int nfixedvars = 0; 3117 int c; 3118 3119 assert( scip != NULL ); 3120 assert( conshdlr != NULL ); 3121 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 3122 assert( result != NULL ); 3123 3124 *result = SCIP_DIDNOTRUN; 3125 3126 /* propagate all useful constraints */ 3127 for (c = 0; c < nusefulconss && !infeasible; ++c) 3128 { 3129 assert( conss[c] != 0 ); 3130 3131 SCIPdebugMsg(scip, "Propagation of orbitope constraint <%s> ...\n", SCIPconsGetName(conss[c])); 3132 3133 SCIP_CALL( propagateCons(scip, conss[c], &infeasible, &nfixedvars) ); 3134 } 3135 3136 /* return the correct result */ 3137 if ( infeasible ) 3138 { 3139 *result = SCIP_CUTOFF; 3140 SCIPdebugMsg(scip, "Propagation via orbitopal fixing proved node to be infeasible.\n"); 3141 } 3142 else if ( nfixedvars > 0 ) 3143 { 3144 *result = SCIP_REDUCEDDOM; 3145 SCIPdebugMsg(scip, "Propagated %d variables via orbitopal fixing.\n", nfixedvars); 3146 } 3147 else if ( nusefulconss > 0 ) 3148 { 3149 *result = SCIP_DIDNOTFIND; 3150 SCIPdebugMsg(scip, "Propagation via orbitopal fixing did not find anything.\n"); 3151 } 3152 3153 return SCIP_OKAY; 3154 } 3155 3156 3157 /** presolving method of constraint handler */ 3158 static 3159 SCIP_DECL_CONSPRESOL(consPresolOrbitope) 3160 { /*lint --e{715}*/ 3161 SCIP_Bool infeasible = FALSE; 3162 int noldfixedvars; 3163 int c; 3164 SCIP_Bool redundant; 3165 3166 assert( scip != NULL ); 3167 assert( conshdlr != NULL ); 3168 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 3169 assert( result != NULL ); 3170 3171 *result = SCIP_DIDNOTRUN; 3172 noldfixedvars = *nfixedvars; 3173 3174 /* propagate all useful constraints 3175 * 3176 * @todo use an event handler to only propagate if a variable in the orbitope has been fixed 3177 */ 3178 for (c = 0; c < nconss && !infeasible; ++c) 3179 { 3180 int nfixed = 0; 3181 3182 assert( conss[c] != 0 ); 3183 3184 SCIPdebugMsg(scip, "Presolving of orbitope constraint <%s> ...\n", SCIPconsGetName(conss[c])); 3185 3186 /* first propagate */ 3187 SCIP_CALL( propagateCons(scip, conss[c], &infeasible, &nfixed) ); 3188 *nfixedvars += nfixed; 3189 3190 if ( ! infeasible ) 3191 { 3192 SCIP_CALL( checkRedundantCons(scip, conss[c], &redundant) ); 3193 3194 if ( redundant ) 3195 { 3196 SCIPdebugMsg(scip, "Orbitope constraint <%s> is redundant: it does not contain active variables\n", 3197 SCIPconsGetName(conss[c])); 3198 SCIP_CALL( SCIPdelCons(scip, conss[c]) ); 3199 assert( ! SCIPconsIsActive(conss[c]) ); 3200 (*ndelconss)++; 3201 continue; 3202 } 3203 } 3204 } 3205 3206 if ( infeasible ) 3207 { 3208 *result = SCIP_CUTOFF; 3209 SCIPdebugMsg(scip, "Presolving detected infeasibility.\n"); 3210 } 3211 else if ( *nfixedvars > noldfixedvars ) 3212 { 3213 *result = SCIP_SUCCESS; 3214 } 3215 else if ( nconss > 0 ) 3216 { 3217 *result = SCIP_DIDNOTFIND; 3218 SCIPdebugMsg(scip, "Presolving via orbitopal fixing did not find anything.\n"); 3219 } 3220 3221 return SCIP_OKAY; 3222 } 3223 3224 3225 /** propagation conflict resolving method of constraint handler */ 3226 static 3227 SCIP_DECL_CONSRESPROP(consRespropOrbitope) 3228 { /*lint --e{715}*/ 3229 SCIP_CONSDATA* consdata; 3230 SCIP_ORBITOPETYPE orbitopetype; 3231 3232 assert( scip != NULL ); 3233 assert( cons != NULL ); 3234 assert( infervar != NULL ); 3235 assert( bdchgidx != NULL ); 3236 assert( result != NULL ); 3237 3238 consdata = SCIPconsGetData(cons); 3239 assert( consdata != NULL ); 3240 3241 orbitopetype = consdata->orbitopetype; 3242 3243 /* resolution for full orbitopes not availabe yet */ 3244 if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING ) 3245 { 3246 SCIP_CALL( resolvePropagation(scip, cons, inferinfo, bdchgidx, result) ); 3247 } 3248 else 3249 { 3250 SCIP_CALL( resolvePropagationFullOrbitope(scip, conshdlr, cons, inferinfo, bdchgidx, result) ); 3251 } 3252 3253 return SCIP_OKAY; 3254 } 3255 3256 3257 /** variable rounding lock method of constraint handler */ 3258 static 3259 SCIP_DECL_CONSLOCK(consLockOrbitope) 3260 { /*lint --e{715}*/ 3261 SCIP_CONSDATA* consdata; 3262 SCIP_VAR*** vars; 3263 int i; 3264 int j; 3265 int nspcons; 3266 int nblocks; 3267 3268 assert( scip != NULL ); 3269 assert( conshdlr != NULL ); 3270 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 3271 assert( cons != NULL ); 3272 assert( locktype == SCIP_LOCKTYPE_MODEL ); 3273 3274 consdata = SCIPconsGetData(cons); 3275 assert( consdata != NULL ); 3276 assert( consdata->nspcons > 0 ); 3277 assert( consdata->nblocks > 0 ); 3278 assert( consdata->vars != NULL ); 3279 3280 SCIPdebugMsg(scip, "Locking method for orbitope constraint handler\n"); 3281 3282 nspcons = consdata->nspcons; 3283 nblocks = consdata->nblocks; 3284 vars = consdata->vars; 3285 3286 /* add up locks and down locks on each variable */ 3287 for (i = 0; i < nspcons; ++i) 3288 { 3289 for (j = 0; j < nblocks; ++j) 3290 SCIP_CALL( SCIPaddVarLocksType(scip, vars[i][j], locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) ); 3291 } 3292 3293 return SCIP_OKAY; 3294 } 3295 3296 3297 /** constraint display method of constraint handler */ 3298 static 3299 SCIP_DECL_CONSPRINT(consPrintOrbitope) 3300 { 3301 SCIP_CONSDATA* consdata; 3302 SCIP_VAR*** vars; 3303 int i; 3304 int j; 3305 int nspcons; 3306 int nblocks; 3307 SCIP_ORBITOPETYPE orbitopetype; 3308 3309 assert( scip != NULL ); 3310 assert( conshdlr != NULL ); 3311 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 3312 assert( cons != NULL ); 3313 3314 consdata = SCIPconsGetData(cons); 3315 assert( consdata != NULL ); 3316 assert( consdata->nspcons > 0 ); 3317 assert( consdata->nblocks > 0 ); 3318 assert( consdata->vars != NULL ); 3319 3320 nspcons = consdata->nspcons; 3321 nblocks = consdata->nblocks; 3322 vars = consdata->vars; 3323 orbitopetype = consdata->orbitopetype; 3324 3325 SCIPdebugMsg(scip, "Printing method for orbitope constraint handler\n"); 3326 3327 switch ( orbitopetype ) 3328 { 3329 case SCIP_ORBITOPETYPE_PARTITIONING: 3330 SCIPinfoMessage(scip, file, "partOrbitope("); 3331 break; 3332 case SCIP_ORBITOPETYPE_PACKING: 3333 SCIPinfoMessage(scip, file, "packOrbitope("); 3334 break; 3335 case SCIP_ORBITOPETYPE_FULL: 3336 SCIPinfoMessage(scip, file, "fullOrbitope("); 3337 break; 3338 default: 3339 SCIPABORT(); 3340 } 3341 3342 for (i = 0; i < nspcons; ++i) 3343 { 3344 for (j = 0; j < nblocks; ++j) 3345 { 3346 if ( j > 0 ) 3347 SCIPinfoMessage(scip, file, ","); 3348 SCIP_CALL( SCIPwriteVarName(scip, file, vars[i][j], TRUE) ); 3349 } 3350 if ( i < nspcons-1 ) 3351 SCIPinfoMessage(scip, file, "."); 3352 } 3353 SCIPinfoMessage(scip, file, ")"); 3354 3355 return SCIP_OKAY; 3356 } 3357 3358 3359 /** constraint copying method of constraint handler */ 3360 static 3361 SCIP_DECL_CONSCOPY(consCopyOrbitope) 3362 { 3363 SCIP_CONSHDLRDATA* conshdlrdata; 3364 SCIP_CONSDATA* sourcedata; 3365 SCIP_VAR*** sourcevars; 3366 SCIP_VAR*** vars; 3367 int nspcons; 3368 int nblocks; 3369 int i; 3370 int k; 3371 int j; 3372 3373 assert( scip != NULL ); 3374 assert( cons != NULL ); 3375 assert( sourcescip != NULL ); 3376 assert( sourceconshdlr != NULL ); 3377 assert( strcmp(SCIPconshdlrGetName(sourceconshdlr), CONSHDLR_NAME) == 0 ); 3378 assert( sourcecons != NULL ); 3379 assert( varmap != NULL ); 3380 assert( valid != NULL ); 3381 3382 *valid = TRUE; 3383 3384 SCIPdebugMsg(scip, "Copying method for orbitope constraint handler.\n"); 3385 3386 sourcedata = SCIPconsGetData(sourcecons); 3387 assert( sourcedata != NULL ); 3388 assert( sourcedata->nspcons > 0 ); 3389 assert( sourcedata->nblocks > 0 ); 3390 assert( sourcedata->vars != NULL ); 3391 3392 conshdlrdata = SCIPconshdlrGetData(sourceconshdlr); 3393 assert( conshdlrdata != NULL ); 3394 3395 /* do not copy non-model constraints */ 3396 if ( !sourcedata->ismodelcons && !conshdlrdata->forceconscopy ) 3397 { 3398 *valid = FALSE; 3399 3400 return SCIP_OKAY; 3401 } 3402 3403 nspcons = sourcedata->nspcons; 3404 nblocks = sourcedata->nblocks; 3405 sourcevars = sourcedata->vars; 3406 3407 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nspcons) ); 3408 for (i = 0; i < nspcons && *valid; ++i) 3409 { 3410 SCIP_CALL( SCIPallocBufferArray(scip, &(vars[i]), nblocks) ); /*lint !e866*/ 3411 3412 for (j = 0; j < nblocks && *valid; ++j) 3413 { 3414 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[i][j], &(vars[i][j]), varmap, consmap, global, valid) ); 3415 assert( !(*valid) || vars[i][j] != NULL ); 3416 } 3417 } 3418 3419 /* only create the target constraint, if all variables could be copied */ 3420 if ( *valid ) 3421 { 3422 /* create copied constraint */ 3423 if ( name == NULL ) 3424 name = SCIPconsGetName(sourcecons); 3425 3426 SCIP_CALL( SCIPcreateConsOrbitope(scip, cons, name, 3427 vars, sourcedata->orbitopetype, nspcons, nblocks, sourcedata->usedynamicprop, 3428 sourcedata->resolveprop, sourcedata->ismodelcons, sourcedata->mayinteract, 3429 initial, separate, enforce, check, propagate, 3430 local, modifiable, dynamic, removable, stickingatnode) ); 3431 } 3432 3433 /* free space; only up to row i if copying failed */ 3434 assert( 0 <= i && i <= nspcons ); 3435 for (k = i - 1; k >= 0; --k) 3436 SCIPfreeBufferArray(scip, &vars[k]); 3437 SCIPfreeBufferArray(scip, &vars); 3438 3439 return SCIP_OKAY; 3440 } 3441 3442 3443 /** constraint parsing method of constraint handler */ 3444 static 3445 SCIP_DECL_CONSPARSE(consParseOrbitope) 3446 { /*lint --e{715}*/ 3447 const char* s; 3448 char* endptr; 3449 SCIP_ORBITOPETYPE orbitopetype; 3450 SCIP_VAR*** vars; 3451 SCIP_VAR* var; 3452 int nspcons; 3453 int maxnspcons; 3454 int nblocks; 3455 int maxnblocks; 3456 int k; 3457 int j; 3458 3459 assert( success != NULL ); 3460 3461 *success = TRUE; 3462 s = str; 3463 3464 /* skip white space */ 3465 SCIP_CALL( SCIPskipSpace((char**)&s) ); 3466 3467 if( strncmp(s, "partOrbitope(", 13) == 0 ) 3468 orbitopetype = SCIP_ORBITOPETYPE_PARTITIONING; 3469 else if( strncmp(s, "packOrbitope(", 13) == 0 ) 3470 orbitopetype = SCIP_ORBITOPETYPE_PACKING; 3471 else 3472 { 3473 if( strncmp(s, "fullOrbitope(", 13) != 0 ) 3474 { 3475 SCIPerrorMessage("Syntax error - expected \"fullOrbitope(\", \"partOrbitope\" or \"packOrbitope\": %s\n", s); 3476 *success = FALSE; 3477 return SCIP_OKAY; 3478 } 3479 orbitopetype = SCIP_ORBITOPETYPE_FULL; 3480 } 3481 s += 13; 3482 3483 /* loop through string */ 3484 nspcons = 0; 3485 nblocks = 0; 3486 maxnspcons = 10; 3487 maxnblocks = 10; 3488 3489 SCIP_CALL( SCIPallocBufferArray(scip, &vars, maxnspcons) ); 3490 3491 j = 0; 3492 do 3493 { 3494 /* parse variable name */ 3495 SCIP_CALL( SCIPparseVarName(scip, s, &var, &endptr) ); 3496 3497 if( var == NULL ) 3498 { 3499 endptr = strchr(endptr, ')'); 3500 3501 if( endptr == NULL || j > 0 ) 3502 { 3503 SCIPerrorMessage("not enough variables.\n"); 3504 *success = FALSE; 3505 } 3506 3507 break; 3508 } 3509 3510 s = endptr; 3511 assert( s != NULL ); 3512 3513 /* skip white space */ 3514 SCIP_CALL( SCIPskipSpace((char**)&s) ); 3515 3516 /* begin new row if required */ 3517 if( j == 0 ) 3518 { 3519 ++nspcons; 3520 3521 if( nspcons > maxnspcons ) 3522 { 3523 maxnspcons = SCIPcalcMemGrowSize(scip, nspcons); 3524 SCIP_CALL( SCIPreallocBufferArray(scip, &vars, maxnspcons) ); 3525 assert( nspcons <= maxnspcons ); 3526 } 3527 3528 SCIP_CALL( SCIPallocBufferArray(scip, &(vars[nspcons-1]), nspcons == 1 ? maxnblocks : nblocks) ); /*lint !e866*/ 3529 } 3530 3531 /* determine number of columns */ 3532 if( nspcons == 1 ) 3533 { 3534 nblocks = j+1; 3535 3536 if( *s == '.' || *s == ')' ) 3537 SCIP_CALL( SCIPreallocBufferArray(scip, &(vars[nspcons-1]), nblocks) ); /*lint !e866*/ 3538 else if( nblocks > maxnblocks ) 3539 { 3540 maxnblocks = SCIPcalcMemGrowSize(scip, nblocks); 3541 SCIP_CALL( SCIPreallocBufferArray(scip, &(vars[nspcons-1]), maxnblocks) ); /*lint !e866*/ 3542 assert( nblocks <= maxnblocks ); 3543 } 3544 } 3545 else if( ( j < nblocks-1 ) == ( *s == '.' || *s == ')' ) ) 3546 { 3547 SCIPerrorMessage("variables per row do not match.\n"); 3548 *success = FALSE; 3549 break; 3550 } 3551 3552 vars[nspcons-1][j] = var; 3553 3554 if( *s == '.' ) 3555 j = 0; 3556 else 3557 ++j; 3558 3559 /* skip ',' or '.' */ 3560 if( *s == ',' || *s == '.' ) 3561 ++s; 3562 } 3563 while( *s != ')' ); 3564 3565 /* to ensure consistency, we disable dynamic propagation and tell SCIP that the orbitope could potentially 3566 * interact with other symmetry handling constraints 3567 */ 3568 if( *success ) 3569 SCIP_CALL( SCIPcreateConsOrbitope(scip, cons, name, vars, orbitopetype, nspcons, nblocks, FALSE, TRUE, TRUE, TRUE, 3570 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) ); 3571 3572 for( k = nspcons - 1; k >= 0; --k ) 3573 SCIPfreeBufferArray(scip, &vars[k]); 3574 SCIPfreeBufferArray(scip, &vars); 3575 3576 return SCIP_OKAY; 3577 } 3578 3579 3580 /** constraint method of constraint handler which returns the variables (if possible) */ 3581 static 3582 SCIP_DECL_CONSGETVARS(consGetVarsOrbitope) 3583 { /*lint --e{715}*/ 3584 SCIP_CONSDATA* consdata; 3585 3586 assert( cons != NULL ); 3587 assert( success != NULL ); 3588 assert( vars != NULL ); 3589 3590 consdata = SCIPconsGetData(cons); 3591 assert( consdata != NULL ); 3592 3593 if ( varssize < consdata->nblocks * consdata->nspcons ) 3594 (*success) = FALSE; 3595 else 3596 { 3597 int cnt = 0; 3598 int i; 3599 int j; 3600 3601 for (i = 0; i < consdata->nspcons; ++i) 3602 { 3603 for (j = 0; j < consdata->nblocks; ++j) 3604 vars[cnt++] = consdata->vars[i][j]; 3605 } 3606 (*success) = TRUE; 3607 } 3608 3609 return SCIP_OKAY; 3610 } 3611 3612 3613 /** constraint method of constraint handler which returns the number of variables (if possible) */ 3614 static 3615 SCIP_DECL_CONSGETNVARS(consGetNVarsOrbitope) 3616 { /*lint --e{715}*/ 3617 SCIP_CONSDATA* consdata; 3618 3619 assert( cons != NULL ); 3620 3621 consdata = SCIPconsGetData(cons); 3622 assert( consdata != NULL ); 3623 3624 (*nvars) = consdata->nblocks * consdata->nspcons; 3625 (*success) = TRUE; 3626 3627 return SCIP_OKAY; 3628 } 3629 3630 3631 /* 3632 * constraint specific interface methods 3633 */ 3634 3635 /** creates the handler for orbitope constraints and includes it in SCIP */ 3636 SCIP_RETCODE SCIPincludeConshdlrOrbitope( 3637 SCIP* scip /**< SCIP data structure */ 3638 ) 3639 { 3640 SCIP_CONSHDLRDATA* conshdlrdata; 3641 SCIP_CONSHDLR* conshdlr; 3642 3643 /* create orbitope constraint handler data */ 3644 SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) ); 3645 3646 /* include constraint handler */ 3647 SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC, 3648 CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, 3649 CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS, 3650 consEnfolpOrbitope, consEnfopsOrbitope, consCheckOrbitope, consLockOrbitope, 3651 conshdlrdata) ); 3652 assert(conshdlr != NULL); 3653 3654 /* set non-fundamental callbacks via specific setter functions */ 3655 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyOrbitope, consCopyOrbitope) ); 3656 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeOrbitope) ); 3657 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteOrbitope) ); 3658 SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsOrbitope) ); 3659 SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsOrbitope) ); 3660 SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseOrbitope) ); 3661 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolOrbitope, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) ); 3662 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintOrbitope) ); 3663 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropOrbitope, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, 3664 CONSHDLR_PROP_TIMING) ); 3665 SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropOrbitope) ); 3666 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpOrbitope, consSepasolOrbitope, CONSHDLR_SEPAFREQ, 3667 CONSHDLR_SEPAPRIORITY, CONSHDLR_DELAYSEPA) ); 3668 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransOrbitope) ); 3669 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxOrbitope) ); 3670 3671 SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/checkpporbitope", 3672 "Strengthen orbitope constraints to packing/partioning orbitopes?", 3673 &conshdlrdata->checkpporbitope, TRUE, DEFAULT_PPORBITOPE, NULL, NULL) ); 3674 3675 SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/sepafullorbitope", 3676 "Whether we separate inequalities for full orbitopes?", 3677 &conshdlrdata->sepafullorbitope, TRUE, DEFAULT_SEPAFULLORBITOPE, NULL, NULL) ); 3678 3679 SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/forceconscopy", 3680 "Whether orbitope constraints should be forced to be copied to sub SCIPs.", 3681 &conshdlrdata->forceconscopy, TRUE, DEFAULT_FORCECONSCOPY, NULL, NULL) ); 3682 3683 return SCIP_OKAY; 3684 } 3685 3686 3687 /** creates and captures a orbitope constraint 3688 * 3689 * @pre If packing/partitioning orbitopes are used, this constraint handler assumes that constraints which enforce 3690 * the packing/partitioning constraints are contained in the problem. It does not implement, e.g., separation and 3691 * propagation of set packing/partitioning constraints, since this would just copy large parts of the code of the 3692 * setppc constraint handler. 3693 * 3694 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 3695 */ 3696 SCIP_RETCODE SCIPcreateConsOrbitope( 3697 SCIP* scip, /**< SCIP data structure */ 3698 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 3699 const char* name, /**< name of constraint */ 3700 SCIP_VAR*** vars, /**< matrix of variables on which the symmetry acts */ 3701 SCIP_ORBITOPETYPE orbitopetype, /**< type of orbitope constraint */ 3702 int nspcons, /**< number of set partitioning/packing constraints <=> p */ 3703 int nblocks, /**< number of symmetric variable blocks <=> q */ 3704 SCIP_Bool usedynamicprop, /**< whether dynamic propagation should be used */ 3705 SCIP_Bool mayinteract, /**< whether symmetries corresponding to orbitope might interact 3706 * with symmetries handled by other routines */ 3707 SCIP_Bool resolveprop, /**< should propagation be resolved? */ 3708 SCIP_Bool ismodelcons, /**< whether the orbitope is a model constraint */ 3709 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? 3710 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */ 3711 SCIP_Bool separate, /**< should the constraint be separated during LP processing? 3712 * Usually set to TRUE. */ 3713 SCIP_Bool enforce, /**< should the constraint be enforced during node processing? 3714 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 3715 SCIP_Bool check, /**< should the constraint be checked for feasibility? 3716 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 3717 SCIP_Bool propagate, /**< should the constraint be propagated during node processing? 3718 * Usually set to TRUE. */ 3719 SCIP_Bool local, /**< is constraint only valid locally? 3720 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */ 3721 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? 3722 * Usually set to FALSE. In column generation applications, set to TRUE if pricing 3723 * adds coefficients to this constraint. */ 3724 SCIP_Bool dynamic, /**< is constraint subject to aging? 3725 * Usually set to FALSE. Set to TRUE for own cuts which 3726 * are separated as constraints. */ 3727 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? 3728 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */ 3729 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even 3730 * if it may be moved to a more global node? 3731 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */ 3732 ) 3733 { 3734 SCIP_CONSHDLRDATA* conshdlrdata; 3735 SCIP_CONSHDLR* conshdlr; 3736 SCIP_CONSDATA* consdata; 3737 3738 /* find the orbitope constraint handler */ 3739 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME); 3740 if ( conshdlr == NULL ) 3741 { 3742 SCIPerrorMessage("orbitope constraint handler not found\n"); 3743 return SCIP_PLUGINNOTFOUND; 3744 } 3745 3746 /* check for consistency */ 3747 if ( usedynamicprop && mayinteract ) 3748 { 3749 SCIPwarningMessage(scip, "Dynamic propagation is only possible if orbitope does not interact with \ 3750 other symmetry handling constraints. Ignore value of <usedynamicprop>.\n"); 3751 } 3752 3753 assert( nspcons > 0 ); 3754 assert( nblocks > 0 ); 3755 3756 /* run some checks */ 3757 #ifndef NDEBUG 3758 { 3759 SCIP_Real obj; 3760 int i; 3761 int j; 3762 for (i = 0; i < nspcons; ++i) 3763 { 3764 /* initialize obj to infinity */ 3765 obj = SCIPinfinity(scip); 3766 for (j = 0; j < nblocks; ++j) 3767 { 3768 SCIP_Bool fixedZero; 3769 SCIP_VAR* var; 3770 3771 var = vars[i][j]; 3772 assert(var != NULL); 3773 3774 if ( SCIPvarIsNegated(var) ) 3775 var = SCIPvarGetNegatedVar(var); 3776 3777 /* all variables need to be binary */ 3778 assert( SCIPvarIsBinary(var) ); 3779 3780 /* fixed variables have obj = 0; for variables fixed to 0, we assume that there is no 3781 problem (but we cannot always check it, e.g., when in the original problem 3782 variables were fixed and this problem was copied.) */ 3783 fixedZero = ( SCIPisZero(scip, SCIPvarGetLbGlobal(var)) && SCIPisZero(scip, SCIPvarGetUbGlobal(var)) ); 3784 3785 /* @todo adapt correctness of the following check for sub-scips */ 3786 if ( SCIPgetSubscipDepth(scip) == 0 ) 3787 { 3788 /* check whether all variables in a row have the same objective */ 3789 if ( ! fixedZero && SCIPisInfinity(scip, obj) ) 3790 obj = SCIPvarGetObj(var); 3791 else 3792 { 3793 assert( fixedZero || ! SCIPvarIsActive(var) || SCIPisEQ(scip, obj, SCIPvarGetObj(var)) ); 3794 } 3795 } 3796 } 3797 } 3798 } 3799 #endif 3800 3801 conshdlrdata = SCIPconshdlrGetData(conshdlr); 3802 if ( conshdlrdata->checkpporbitope && orbitopetype != SCIP_ORBITOPETYPE_PARTITIONING 3803 && orbitopetype != SCIP_ORBITOPETYPE_PACKING ) 3804 { 3805 SCIP_CALL( strengthenOrbitopeConstraint(scip, vars, &nspcons, nblocks, &orbitopetype, mayinteract) ); 3806 } 3807 3808 /* create constraint data */ 3809 SCIP_CALL( consdataCreate(scip, &consdata, vars, nspcons, nblocks, orbitopetype, 3810 resolveprop, usedynamicprop && ! mayinteract, ismodelcons, mayinteract) ); 3811 3812 /* create constraint */ 3813 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate, 3814 local, modifiable, dynamic, removable, stickingatnode) ); 3815 3816 return SCIP_OKAY; 3817 } 3818 3819 /** creates and captures an orbitope constraint 3820 * in its most basic variant, i. e., with all constraint flags set to their default values 3821 * 3822 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 3823 */ 3824 SCIP_RETCODE SCIPcreateConsBasicOrbitope( 3825 SCIP* scip, /**< SCIP data structure */ 3826 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 3827 const char* name, /**< name of constraint */ 3828 SCIP_VAR*** vars, /**< matrix of variables on which the symmetry acts */ 3829 SCIP_ORBITOPETYPE orbitopetype, /**< type of orbitope constraint */ 3830 int nspcons, /**< number of set partitioning/packing constraints <=> p */ 3831 int nblocks, /**< number of symmetric variable blocks <=> q */ 3832 SCIP_Bool usedynamicprop, /**< whether dynamic propagation should be used */ 3833 SCIP_Bool resolveprop, /**< should propagation be resolved? */ 3834 SCIP_Bool ismodelcons, /**< whether the orbitope is a model constraint */ 3835 SCIP_Bool mayinteract /**< whether symmetries corresponding to orbitope might interact 3836 * with symmetries handled by other routines */ 3837 ) 3838 { 3839 SCIP_CALL( SCIPcreateConsOrbitope(scip, cons, name, vars, orbitopetype, nspcons, nblocks, usedynamicprop, 3840 resolveprop, ismodelcons, mayinteract, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 3841 3842 return SCIP_OKAY; 3843 } 3844