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 symmetry_orbitopal.c 26 * @ingroup OTHER_CFILES 27 * @brief methods for handling orbitopal symmetries 28 * @author Jasper van Doornmalen 29 * 30 * This implements orbitopal reducion, which generalizes full orbitope propagation to work for non-binary variable 31 * domains, and is dynamified. See cons_orbitope.c for the variant for binary variables, both the static and partially 32 * dynamic variant. 33 * Just as in orbital reduction (cf. symmetry_orbital.c), the variable order is chosen as the variables 34 * branched on from the root node to the focus node. 35 * 36 * See Section 4.2, Example 12 and Section 5.1 in [vD,H]:@n 37 * J. van Doornmalen, C. Hojny, "A Unified Framework for Symmetry Handling", preprint, 2023, 38 * https://doi.org/10.48550/arXiv.2211.01295. 39 * 40 * Orbitopal reduction can be used to handle symmetries of the following type. 41 * If the variables can be arranged in a matrix and the symmetries correspond to all column permutations of this matrix, 42 * then these symmetries are called orbitopal. 43 * Symmetry is completely handled by enforcing that the columns are lexicographically decreasing. 44 * If a reduction on a variable is applied, and if this variable is high up in the variable matrix, then this has a 45 * relatively large impact on the lexicographic ordering. Moreover, the ordering of the columns also matter. 46 * Dynamification allows for choosing a custom ordering of a subset of rows and a permutation of the columns. 47 * For every node, we maintain the ordered subset of rows and the column order. 48 * The root node assumes no rows and an arbitrary column order (we choose the identity). 49 * If towards a new node it is branched on a variable, that appears in a row which is not included in the subset of 50 * rows for the current node, then the row set of the new children is the ordered row set of the current node, appended 51 * by this new row. 52 * For the column order, if at the current node columns are symmetrically equivalent, then these can be permuted for 53 * the sake of symmetry handling. In the implementation, we only swap the column containing the branching variable 54 * with a symmetrically equivalent column elsewhere. We use one of the following heuristics: 55 * 56 * - None: Keep the column-order as-is. 57 * - First: Permute such that the column containing the branching variable is in the symmetrically equivalent column 58 * with minimal index. 59 * - Last: The same, but to the symmetrically equivalent column with maximal index. 60 * - Centre: The same, but to the symmetrically equivalent column closest to to the middlemost column among all columns. 61 * - Median: The same, but to the median of all symmetrically equivalent columns. (This is the default) 62 * 63 * Since the dynamic row and column ordering rule for a branch-and-bound tree node depends on the decisions made up to 64 * that branch-and-bound tree node, we compute and store the row and column order for the branch-and-bound tree children 65 * at the moment of branching. This is done by the eventhandler in this file. 66 * Instead of storing those, we could have chosen to reconstruct this row and column ordering to save memory. 67 * However, we cannot reliably reconstruct this order from the branch-and-bound tree itself, 68 * because the row and column ordering depends on symmetrical equivalence of columns in the orbitope matrix, 69 * and because SCIP can change the tree structure during solving that may re-write historic variable bound changes 70 * (for instance when global variable bound changes are found, or when the root node is moved down the tree to become 71 * the new effective root node). 72 * We are not concerned about storing the row and column ordering, since we only store the mutations with its parent. 73 * These are usually at most one column swap and usually at most one additional row. 74 * 75 * @todo Exploiting packing-partitioning structures 76 * @todo for packing-partitioning rows, use the FIRST column swap heuristic. 77 */ 78 79 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 80 81 #include "blockmemshell/memory.h" 82 #include "scip/symmetry_orbitopal.h" 83 #include "scip/pub_cons.h" 84 #include "scip/pub_message.h" 85 #include "scip/pub_var.h" 86 #include "scip/struct_var.h" 87 #include "scip/type_var.h" 88 #include "scip/scip.h" 89 #include "scip/scip_branch.h" 90 #include "scip/scip_conflict.h" 91 #include "scip/scip_cons.h" 92 #include "scip/scip_copy.h" 93 #include "scip/scip_cut.h" 94 #include "scip/scip_general.h" 95 #include "scip/scip_lp.h" 96 #include "scip/scip_mem.h" 97 #include "scip/scip_message.h" 98 #include "scip/scip_numerics.h" 99 #include "scip/scip_param.h" 100 #include "scip/scip_prob.h" 101 #include "scip/scip_probing.h" 102 #include "scip/scip_sol.h" 103 #include "scip/scip_var.h" 104 #include "scip/struct_scip.h" 105 #include "scip/struct_mem.h" 106 #include "scip/struct_tree.h" 107 #include "scip/symmetry.h" 108 #include "scip/debug.h" 109 #include <string.h> 110 #include <symmetry/type_symmetry.h> 111 112 113 /* symmetry handler properties */ 114 #define SYMHDLR_NAME "orbitopalreduction" 115 116 /* orbitopal symmetry handler properties */ 117 #define EVENTHDLR_NAME "symmetry_orbitopal_eventhdlr" 118 #define EVENTHDLR_DESC "event handler for maintaining the branch-and-bound tree" 119 #define DEFAULT_COLUMNORDERING SCIP_COLUMNORDERING_MEDIAN /**< the column ordering variant */ 120 121 /* 122 * Data structures 123 */ 124 125 /** orbitopal symmetry handling data for a single orbitope */ 126 struct OrbitopeData 127 { 128 SCIP_VAR** vars; /**< orbitope variable array representing orbitope matrix row-wise */ 129 int nrows; /**< number of rows */ 130 int ncols; /**< number of columns */ 131 int nbranchrows; /**< number of rows containing variables potentially used for branching */ 132 SCIP_HASHMAP* rowindexmap; /**< map of variables to row index in orbitope matrix */ 133 SCIP_HASHMAP* colindexmap; /**< map of variables to column index in orbitope matrix */ 134 #ifndef NDEBUG 135 SCIP_Longint lastnodenumber; /**< the last node number where the row and column order is computed */ 136 int dbghash; /**< a hash for the column order in the last iteration */ 137 #endif 138 SCIP_HASHTABLE* nodeinfos; /**< symmetry handling information per branch-and-bound tree node */ 139 SCIP_COLUMNORDERING columnordering; /**< policy for the column ordering */ 140 SCIP_ROWORDERING rowordering; /**< policy for the row ordering */ 141 }; 142 typedef struct OrbitopeData ORBITOPEDATA; /**< orbitopal symmetry handling data for a single orbitope */ 143 144 /** wrapper for all orbitopes in orbitopal symmetry handling data */ 145 struct SCIP_OrbitopalReductionData 146 { 147 SCIP_COLUMNORDERING defaultcolumnordering; /**< default policy for the column ordering */ 148 SCIP_EVENTHDLR* eventhdlr; /**< pointer to the event handler for managing the branching tree */ 149 ORBITOPEDATA** orbitopes; /**< array of pointers to orbitope data structs */ 150 int norbitopes; /**< number of orbitope data structs in array */ 151 int maxnorbitopes; /**< allocated orbitopes array size */ 152 SCIP_CONSHDLR* conshdlr_nonlinear; /**< nonlinear constraint handler, 153 * is used to determine if a variable is a branching variable */ 154 SCIP_Bool conshdlr_nonlinear_checked; /**< nonlinear constraint handler is already added? */ 155 int nred; /**< total number of reductions */ 156 int ncutoff; /**< total number of cutoffs */ 157 }; 158 159 /* 160 * Local methods 161 */ 162 163 /** gets whether a variable type is a branchrow-type */ 164 static 165 SCIP_Bool vartypeIsBranchRowType( 166 SCIP* scip, /**< SCIP data structure */ 167 SCIP_ORBITOPALREDDATA* orbireddata, /**< pointer to the dynamic orbitopal reduction data */ 168 SCIP_VARTYPE vartype /**< var type */ 169 ) 170 { 171 assert( scip != NULL ); 172 assert( orbireddata != NULL ); 173 assert( orbireddata->conshdlr_nonlinear_checked ); 174 175 switch (vartype) 176 { 177 case SCIP_VARTYPE_BINARY: 178 case SCIP_VARTYPE_INTEGER: 179 return TRUE; 180 case SCIP_VARTYPE_CONTINUOUS: 181 case SCIP_VARTYPE_IMPLINT: 182 /* potential branching variables if nonlinear constraints exist */ 183 assert( orbireddata->conshdlr_nonlinear_checked ); 184 return orbireddata->conshdlr_nonlinear == NULL ? FALSE : 185 SCIPconshdlrGetNActiveConss(orbireddata->conshdlr_nonlinear) > 0; 186 default: 187 SCIPerrorMessage("unknown vartype\n"); 188 SCIPABORT(); 189 /* resolve compiler warning: no asserts in optimized mode */ 190 return FALSE; 191 } 192 } 193 194 195 /** container for column index permutations */ 196 struct ColSwap 197 { 198 int from; /**< from which column ID */ 199 int to; /**< to which column ID */ 200 }; 201 typedef struct ColSwap COLSWAP; 202 203 /** information stored for branch-and-bound nodes */ 204 struct BnbNodeInfo 205 { 206 SCIP_Longint nodenumber; /**< node number of the branch-and-bound tree node */ 207 COLSWAP* colswaps; /**< list containing column swaps by node branching decisions */ 208 int ncolswaps; /**< number of elements in colswaps. ncolswaps == 0 <=> colswaps == NULL */ 209 int* rows; /**< list of new variable rows by node branching decisions */ 210 int nrows; /**< number of new variable rows added. nrows == 0 <=> rows == NULL */ 211 }; 212 typedef struct BnbNodeInfo BNBNODEINFO; 213 214 /** hash key for virtual branch and bound nodeinfo struct */ 215 static 216 SCIP_DECL_HASHGETKEY(hashGetKeyBnbnodeinfo) 217 { /*lint --e{715}*/ 218 return elem; 219 } 220 221 /** returns TRUE iff the indices of both node numbers are equal */ 222 static 223 SCIP_DECL_HASHKEYEQ(hashKeyEqBnbnodeinfo) 224 { /*lint --e{715}*/ 225 BNBNODEINFO* nodeinfo1 = (BNBNODEINFO*) key1; 226 BNBNODEINFO* nodeinfo2 = (BNBNODEINFO*) key2; 227 return nodeinfo1->nodenumber == nodeinfo2->nodenumber; 228 } 229 230 /** returns the hash value of the key */ 231 static 232 SCIP_DECL_HASHKEYVAL(hashKeyValBnbnodeinfo) 233 { /*lint --e{715}*/ 234 BNBNODEINFO* nodeinfo = (BNBNODEINFO*) key; 235 return (unsigned int) nodeinfo->nodenumber; 236 } 237 238 239 /** tests if two columns are symmetrically equivalent 240 * 241 * We test if the columns with index col1 and col2 have elementwise the same bounds. 242 * If all symmetry-compatible reductions are applied, then it suffices to check only as many rows as are selected 243 * for orbitopal reduction. However, to be resilient to reductions that are not symmetry-compatible, 244 * we test all variables in the columns. 245 */ 246 static 247 SCIP_Bool testColumnsAreSymmetricallyEquivalent( 248 SCIP* scip, /**< SCIP data structure */ 249 ORBITOPEDATA* orbidata, /**< orbitope information */ 250 int col1, /**< first column to compare */ 251 int col2 /**< second column to compare */ 252 ) 253 { 254 int i; 255 SCIP_VAR* var1; 256 SCIP_VAR* var2; 257 258 assert( scip != NULL ); 259 assert( orbidata != NULL ); 260 assert( col1 >= 0 ); 261 assert( col1 < orbidata->ncols ); 262 assert( col2 >= 0 ); 263 assert( col2 < orbidata->ncols ); 264 265 /* @todo test only for the selected rows (see function description) */ 266 for (i = 0; i < orbidata->nrows; ++i) 267 { 268 var1 = orbidata->vars[i * orbidata->ncols + col1]; 269 var2 = orbidata->vars[i * orbidata->ncols + col2]; 270 271 /* if variable bounds differ: columns c and origcolid are not the same */ 272 if ( 273 (! SCIPEQ(scip, SCIPvarGetLbLocal(var1), SCIPvarGetLbLocal(var2))) 274 || 275 (! SCIPEQ(scip, SCIPvarGetUbLocal(var1), SCIPvarGetUbLocal(var2))) 276 ) 277 return FALSE; 278 } 279 280 /* loop terminated, so columns are equal */ 281 return TRUE; 282 } 283 284 /** updates the column order with a bound change 285 * 286 * When it is branched on a variable in a column, update the column order for the children of the focusnode. 287 * Symmetrically equivalent columns, that is the columns where the variables have elementwise the same domain, 288 * at the focusnode at the moment of branching can be permuted. 289 * In this function, we select such a permutation, based on the column containing the branching variable(s). 290 * In all cases, we swap the column containing the branching variable with a symmetrically equivalent column, 291 * and the @param columnordering specifies if we prefer it to be the leftmost, rightmost, centermost symmetrically 292 * equivalent column, or the median column among the symmetrically equivalent columns. 293 * 294 * The column ordering is determined and stored at the moment of branching. 295 */ 296 static 297 SCIP_RETCODE updateColumnOrderWhenBranchingOnColumn( 298 SCIP* scip, /**< SCIP data structure */ 299 ORBITOPEDATA* orbidata, /**< orbitope data */ 300 int* colorder, /**< array to populate with column order, of size colorder */ 301 int* colorderinv, /**< inverse array of the column order, of size colorder */ 302 SCIP_VAR* var, /**< variable that we branch on */ 303 COLSWAP* thiscolswap /**< the colswap to populate */ 304 ) 305 { 306 int origcolid; 307 int swaporigcolid; 308 int c; 309 int ncols; 310 int* origequalcolids; 311 int norigequalcolids; 312 int middlecolumn = 0; 313 int positionorigcolidincolorder; 314 int positionswaporigcolidincolorder; 315 316 #ifndef NDEBUG 317 SCIP_VAR* var1; 318 SCIP_VAR* var2; 319 int i; 320 int nrows; 321 #endif 322 323 assert( scip != NULL ); 324 assert( orbidata != NULL ); 325 assert( colorder != NULL ); 326 assert( colorderinv != NULL ); 327 assert( var != NULL ); 328 assert( thiscolswap != NULL ); 329 assert( orbidata->ncols > 0 ); 330 assert( orbidata->nrows > 0 ); 331 332 ncols = orbidata->ncols; 333 assert( ncols > 0 ); 334 #ifndef NDEBUG 335 nrows = orbidata->nrows > 0; 336 assert( nrows > 0 ); 337 #endif 338 339 /* do not apply a column swap if no column permutations are applied */ 340 if ( orbidata->columnordering == SCIP_COLUMNORDERING_NONE ) 341 { 342 thiscolswap->from = 0; 343 thiscolswap->to = 0; 344 return SCIP_OKAY; 345 } 346 347 /* only variables from the orbitope matrix are of interest */ 348 origcolid = SCIPhashmapGetImageInt(orbidata->colindexmap, (void*) var); 349 if ( origcolid == INT_MAX ) 350 { 351 thiscolswap->from = 0; 352 thiscolswap->to = 0; 353 return SCIP_OKAY; 354 } 355 assert( origcolid >= 0 ); 356 assert( origcolid < ncols ); 357 358 /* policy: swap with identical column that is closest to the center in relabeled order */ 359 /* @todo other policies: If the variable is in a ppc-row, then select the minimal/second to minimal to branch on */ 360 swaporigcolid = origcolid; 361 362 switch (orbidata->columnordering) 363 { 364 case SCIP_COLUMNORDERING_CENTRE: 365 /* CENTRE uses the same code as FIRST and LAST, but requires that middlecolumn = ncols / 2 is set */ 366 middlecolumn = ncols / 2; 367 /*lint -fallthrough*/ 368 case SCIP_COLUMNORDERING_FIRST: 369 case SCIP_COLUMNORDERING_LAST: 370 /* for each column, test column ordering condition, then if the column is identical to the var-column */ 371 for (c = 0; c < ncols; ++c) 372 { 373 /* origcolid is not interesting */ 374 if ( c == origcolid ) 375 continue; 376 377 /* test if c is a better choice than swaporigcolid, 378 * otherwise continue to next iteration through CONDITIONFAIL 379 */ 380 switch (orbidata->columnordering) 381 { 382 case SCIP_COLUMNORDERING_FIRST: 383 /* only swap with c if c is earlier in column order than swaporigcolid */ 384 if ( colorderinv[c] >= colorderinv[swaporigcolid] ) 385 goto CONDITIONFAIL; 386 break; 387 case SCIP_COLUMNORDERING_LAST: 388 /* only swap with c if c is later in column order than swaporigcolid */ 389 if ( colorderinv[c] <= colorderinv[swaporigcolid] ) 390 goto CONDITIONFAIL; 391 break; 392 case SCIP_COLUMNORDERING_CENTRE: 393 /* if the column is not more central than swaporigcolid, ignore */ 394 if ( ABS(colorderinv[c] - middlecolumn) >= 395 ABS(colorderinv[swaporigcolid] - middlecolumn) ) 396 goto CONDITIONFAIL; 397 break; 398 default: 399 return SCIP_ERROR; 400 } 401 402 /* test: are c and origcolid the same columns w.r.t. the variable domain restrictions? */ 403 if ( !testColumnsAreSymmetricallyEquivalent(scip, orbidata, c, origcolid) ) 404 continue; 405 406 /* the variable domain reductions in c and origcolid are the same */ 407 swaporigcolid = c; 408 409 CONDITIONFAIL: 410 ; /* no-op for going to the next iteration */ 411 } 412 413 /* end switch */ 414 break; 415 416 case SCIP_COLUMNORDERING_MEDIAN: 417 /* collect columns identical to the var-column, then select column satisfying ordering condition */ 418 norigequalcolids = 0; 419 SCIP_CALL( SCIPallocBufferArray(scip, &origequalcolids, ncols) ); 420 421 /* collect equal columns */ 422 #ifdef SCIP_MORE_DEBUG 423 SCIPdebugMessage("Detect columns identical to original column %d: ", origcolid); 424 #endif 425 for (c = 0; c < ncols; ++c) 426 { 427 /* column origcolid is always equal to itself */ 428 if ( c == origcolid ) 429 { 430 origequalcolids[norigequalcolids++] = c; 431 #ifdef SCIP_MORE_DEBUG 432 SCIPdebugPrintf("%d ", c); 433 #endif 434 assert( norigequalcolids <= ncols ); 435 continue; 436 } 437 438 /* test: are c and origcolid the same columns w.r.t. the variable domain restrictions? */ 439 if ( !testColumnsAreSymmetricallyEquivalent(scip, orbidata, c, origcolid) ) 440 continue; 441 442 /* the variable domain reductions in c and origcolid are the same */ 443 origequalcolids[norigequalcolids++] = c; 444 #ifdef SCIP_MORE_DEBUG 445 SCIPdebugPrintf("%d ", c); 446 #endif 447 assert( norigequalcolids <= ncols ); 448 } 449 #ifdef SCIP_MORE_DEBUG 450 SCIPdebugPrintf("\n"); 451 #endif 452 453 /* we should have found origcolid, at least */ 454 assert( norigequalcolids >= 1 ); 455 456 /* from origequalcolids, select the column satisfying the column ordering policy */ 457 458 /* get median column; since colorder maps origcolids to our ordering, 459 * we need to use colorderinv as the argument. */ 460 /* @todo computing the median is O(n) by repeated median-of-medians (CLRS, Ch9), but let's just sort things */ 461 SCIPsortInd(origequalcolids, SCIPsortArgsortInt, colorderinv, norigequalcolids); 462 /* get the median, that is swaporigcolid */ 463 swaporigcolid = origequalcolids[norigequalcolids / 2]; 464 465 SCIPfreeBufferArray(scip, &origequalcolids); 466 467 /* end switch */ 468 break; 469 470 case SCIP_COLUMNORDERING_NONE: 471 /* already handled earlier in this function */ 472 default: 473 /* unknown column ordering variant */ 474 return SCIP_ERROR; 475 } 476 477 thiscolswap->from = swaporigcolid; 478 thiscolswap->to = origcolid; 479 480 /* if we do not replace origcolid */ 481 if ( swaporigcolid == origcolid ) 482 return SCIP_OKAY; 483 484 #ifndef NDEBUG 485 /* swapped columns should be equivalent */ 486 for (i = 0; i < nrows; ++i) 487 { 488 var1 = orbidata->vars[i * ncols + swaporigcolid]; 489 var2 = orbidata->vars[i * ncols + origcolid]; 490 assert( SCIPEQ(scip, SCIPvarGetLbLocal(var1), SCIPvarGetLbLocal(var2)) ); 491 assert( SCIPEQ(scip, SCIPvarGetUbLocal(var1), SCIPvarGetUbLocal(var2)) ); 492 } 493 #endif 494 495 /* now swap the permuted column indices of swaporigcolid and origcolid */ 496 497 /* at which column is origcolid? */ 498 positionorigcolidincolorder = colorderinv[origcolid]; 499 assert( positionorigcolidincolorder >= 0 ); 500 assert( positionorigcolidincolorder < ncols ); 501 assert( colorder[positionorigcolidincolorder] == origcolid ); 502 503 /* at which column is swaporigcolid? */ 504 positionswaporigcolidincolorder = colorderinv[swaporigcolid]; 505 assert( positionswaporigcolidincolorder >= 0 ); 506 assert( positionswaporigcolidincolorder < ncols ); 507 assert( colorder[positionswaporigcolidincolorder] == swaporigcolid ); 508 509 SCIPdebugMessage("Orbitope %p: Swapping column %d (at position %d) with column %d (at position %d)\n", 510 (void*) orbidata, origcolid, positionorigcolidincolorder, swaporigcolid, positionswaporigcolidincolorder); 511 512 /* swap them, also keep track of the inverses */ 513 colorder[positionswaporigcolidincolorder] = origcolid; 514 colorder[positionorigcolidincolorder] = swaporigcolid; 515 colorderinv[origcolid] = positionswaporigcolidincolorder; 516 colorderinv[swaporigcolid] = positionorigcolidincolorder; 517 518 return SCIP_OKAY; 519 } 520 521 522 /** yields entry at index in array, or returns entry if array is NULL */ 523 static 524 int getArrayEntryOrIndex( 525 int* arr, /**< array */ 526 int idx /**< index */ 527 ) 528 { 529 assert( idx >= 0 ); 530 if ( arr == NULL ) 531 return idx; 532 return arr[idx]; 533 } 534 535 /** frees the row order */ 536 static 537 void freeRowOrder( 538 SCIP* scip, /**< SCIP data structure */ 539 ORBITOPEDATA* orbidata, /**< orbitope data */ 540 int** roworder /**< roworder array that is initialized with the roworder in the dynamic 541 * case, and NULL in the static case */ 542 ) 543 { 544 assert( scip != NULL ); 545 assert( orbidata != NULL ); 546 assert( roworder != NULL ); 547 548 if ( orbidata->rowordering == SCIP_ROWORDERING_NONE ) 549 { 550 assert( *roworder == NULL ); 551 return; 552 } 553 554 assert( *roworder != NULL ); 555 assert( orbidata->rowordering == SCIP_ROWORDERING_BRANCHING ); 556 SCIPfreeBlockMemoryArray(scip, roworder, orbidata->nrows); 557 558 return; 559 } 560 561 /** gets the row order at the node 562 * 563 * this is NULL (i.e., the identity map) in the static (none) setting. 564 * this is an array of size orbidata->nrows in the dynamic (branching) setting. 565 * 566 * The row order is given in the order of the variables that is branched on. 567 * @todo combine with variant of cons_orbitope.c 568 */ 569 static 570 SCIP_RETCODE getRowOrder( 571 SCIP* scip, /**< SCIP data structure */ 572 ORBITOPEDATA* orbidata, /**< orbitope data */ 573 SCIP_NODE* node, /**< node for which the row order should be detected */ 574 int** roworder, /**< array to populate with row order */ 575 int* nselrows /**< pointer to populate with the number of rows part of the row order */ 576 ) 577 { 578 int i; 579 int j; 580 BNBNODEINFO* ancestornodeinfo; 581 BNBNODEINFO tmpnodeinfo; /* used for lookups in hash table */ 582 583 assert( orbidata != NULL ); 584 assert( orbidata->nrows > 0 ); 585 assert( orbidata->ncols > 0 ); 586 assert( node != NULL ); 587 assert( roworder != NULL ); 588 assert( nselrows != NULL ); 589 590 if ( orbidata->rowordering == SCIP_ROWORDERING_NONE ) 591 { 592 *roworder = NULL; 593 *nselrows = orbidata->nrows; 594 return SCIP_OKAY; 595 } 596 597 assert( orbidata->rowordering == SCIP_ROWORDERING_BRANCHING ); 598 599 /* allocate number of rows */ 600 SCIP_CALL( SCIPallocBlockMemoryArray(scip, roworder, orbidata->nrows) ); 601 602 *nselrows = 0; 603 604 /* get the present row order up to this node (excluding the node itself) */ 605 node = SCIPnodeGetParent(node); 606 while (node != NULL) 607 { 608 /* retrieve the nodeinfo of this ancestor node */ 609 tmpnodeinfo.nodenumber = SCIPnodeGetNumber(node); 610 ancestornodeinfo = (BNBNODEINFO*) SCIPhashtableRetrieve(orbidata->nodeinfos, (void*) &tmpnodeinfo); 611 if ( ancestornodeinfo != NULL ) 612 { 613 assert( ancestornodeinfo->nrows >= 0 ); 614 for (i = ancestornodeinfo->nrows - 1; i >= 0; --i) 615 { 616 (*roworder)[(*nselrows)++] = ancestornodeinfo->rows[i]; 617 #ifndef NDEBUG 618 { 619 /* check if this row is not featured earlier */ 620 for (j = 0; j < (*nselrows) - 1; ++j) 621 { 622 assert( ancestornodeinfo->rows[i] != (*roworder)[j] ); 623 } 624 } 625 #endif 626 } 627 } 628 629 node = SCIPnodeGetParent(node); 630 } 631 632 /* row order is in reverse order now, so reverse the array */ 633 for (i = 0; i < (*nselrows) / 2; ++i) 634 { 635 /* swap entry i with nselrows - 1 - i */ 636 j = (*roworder)[i]; 637 (*roworder)[i] = (*roworder)[(*nselrows) - 1 - i]; 638 (*roworder)[(*nselrows) - 1 - i] = j; 639 } 640 641 return SCIP_OKAY; 642 } 643 644 645 /** gets rooted path up to node and populates column ordering array */ 646 static 647 SCIP_RETCODE populateRootedPathColumnOrder( 648 ORBITOPEDATA* orbidata, /**< orbitope data */ 649 SCIP_NODE* node, /**< node considered */ 650 SCIP_NODE** rootedpath, /**< array to populate with the rooted path, must be sufficiently long */ 651 int* colorder, /**< array to populate with the column order, must be nvars long */ 652 int* colorderinv /**< array to populate with the inverse column order, must be nvars long */ 653 ) 654 { 655 int i; 656 int j; 657 int depth; 658 BNBNODEINFO* ancestornodeinfo; 659 BNBNODEINFO tmpnodeinfo; 660 COLSWAP* thiscolswap; 661 662 assert( orbidata != NULL ); 663 assert( node != NULL ); 664 assert( rootedpath != NULL ); 665 assert( colorder != NULL ); 666 assert( colorderinv != NULL ); 667 668 depth = SCIPnodeGetDepth(node); 669 i = depth; 670 while ( node != NULL ) 671 { 672 assert( SCIPnodeGetDepth(node) == i ); 673 rootedpath[i--] = node; 674 node = SCIPnodeGetParent(node); 675 } 676 assert( i == -1 ); 677 678 for (i = 0; i <= depth; ++i) 679 { 680 node = rootedpath[i]; 681 682 assert( SCIPnodeGetDepth(node) == i ); 683 684 /* get the node info of that node */ 685 tmpnodeinfo.nodenumber = SCIPnodeGetNumber(node); 686 ancestornodeinfo = (BNBNODEINFO*) SCIPhashtableRetrieve(orbidata->nodeinfos, (void*) &tmpnodeinfo); 687 688 /* skip nodes that do not imply any row or column swaps */ 689 if ( ancestornodeinfo == NULL ) 690 continue; 691 692 /* ncolswaps == 0 iff colswaps == NULL */ 693 assert( (ancestornodeinfo->ncolswaps == 0) != (ancestornodeinfo->colswaps != NULL) ); 694 695 for (j = 0; j < ancestornodeinfo->ncolswaps; ++j) 696 { 697 int positionfromincolorder; 698 int positiontoincolorder; 699 700 thiscolswap = &ancestornodeinfo->colswaps[j]; 701 assert( thiscolswap->from != thiscolswap->to ); /* there are no trivial swaps in the list */ 702 assert( thiscolswap->from >= 0 && thiscolswap->from < orbidata->ncols ); 703 assert( thiscolswap->to >= 0 && thiscolswap->to < orbidata->ncols ); 704 705 /* at which column is origcolid? */ 706 positionfromincolorder = colorderinv[thiscolswap->from]; 707 assert( positionfromincolorder >= 0 ); 708 assert( positionfromincolorder < orbidata->ncols ); 709 assert( colorder[positionfromincolorder] == thiscolswap->from ); 710 711 /* at which column is swaporigcolid? */ 712 positiontoincolorder = colorderinv[thiscolswap->to]; 713 assert( positiontoincolorder >= 0 ); 714 assert( positiontoincolorder < orbidata->ncols ); 715 assert( colorder[positiontoincolorder] == thiscolswap->to ); 716 717 /* swap them, also keep track of the inverses */ 718 colorder[positiontoincolorder] = thiscolswap->from; 719 colorder[positionfromincolorder] = thiscolswap->to; 720 colorderinv[thiscolswap->from] = positiontoincolorder; 721 colorderinv[thiscolswap->to] = positionfromincolorder; 722 } 723 } 724 725 return SCIP_OKAY; 726 } 727 728 /** at branching decisions, maintains the column swap and potential new rows in the orbitope */ 729 static 730 SCIP_DECL_EVENTEXEC(eventExecNodeBranched) 731 { 732 ORBITOPEDATA* orbidata; 733 SCIP_NODE* node; 734 SCIP_NODE* eventnode; 735 SCIP_NODE** children; 736 SCIP_NODE* childnode; 737 SCIP_DOMCHG* domchg; 738 SCIP_BOUNDCHG* boundchg; 739 SCIP_VAR* var; 740 SCIP_VAR** branchvars; 741 int maxnbranchvars; 742 int nbranchvars; 743 int nboundchgs; 744 int nchildren; 745 int i; 746 int j; 747 int c; 748 int rowid; 749 BNBNODEINFO* newnodeinfo; 750 SCIP_NODE** rootedpath; 751 752 assert( eventdata != NULL ); 753 assert( !SCIPinProbing(scip) ); 754 755 eventnode = SCIPeventGetNode(event); 756 assert( SCIPgetFocusNode(scip) == eventnode ); 757 758 orbidata = (ORBITOPEDATA*) eventdata; 759 assert( orbidata != NULL ); 760 assert( orbidata->nrows > 0 ); 761 assert( orbidata->ncols > 0 ); 762 assert( orbidata->vars != NULL ); 763 assert( orbidata->colindexmap != NULL ); 764 assert( orbidata->rowindexmap != NULL ); 765 766 SCIP_CALL( SCIPgetChildren(scip, &children, &nchildren) ); 767 768 /* arrays used within the loop */ 769 maxnbranchvars = 1; /* it's a good guess that there's one branching variable, because that's likely the number */ 770 SCIP_CALL( SCIPallocBufferArray(scip, &branchvars, maxnbranchvars) ); 771 SCIP_CALL( SCIPallocBufferArray(scip, &rootedpath, SCIPnodeGetDepth(eventnode)) ); 772 773 /* get all variables branched upon (check all branches) */ 774 nbranchvars = 0; 775 for (c = 0; c < nchildren; ++c) 776 { 777 childnode = children[c]; 778 domchg = SCIPnodeGetDomchg(childnode); 779 780 /* loop through all bound changes */ 781 nboundchgs = SCIPdomchgGetNBoundchgs(domchg); 782 for (i = 0; i < nboundchgs; ++i) 783 { 784 /* get bound change info */ 785 boundchg = SCIPdomchgGetBoundchg(domchg, i); 786 assert( boundchg != NULL ); 787 788 /* branching decisions have to be in the beginning of the bound change array */ 789 if ( SCIPboundchgGetBoundchgtype(boundchg) != SCIP_BOUNDCHGTYPE_BRANCHING ) 790 break; 791 792 /* get corresponding branching variable */ 793 var = SCIPboundchgGetVar(boundchg); 794 795 /* only variables from the orbitope matrix are of interest */ 796 if ( ! SCIPhashmapExists(orbidata->rowindexmap, (void*) var) ) 797 continue; 798 799 /* skip variables that are already stored */ 800 if ( nbranchvars > 0 ) 801 { 802 for (j = 0; j < nbranchvars; ++j) 803 { 804 if ( branchvars[j] == var ) 805 break; 806 } 807 /* if the loop above is stopped with `break`, `j < nbranchvars` is not satisfied. 808 * then, go to the next iteration 809 */ 810 if ( j < nbranchvars ) 811 continue; 812 } 813 814 /* the variable is not already in the array, so store it */ 815 if ( nbranchvars >= maxnbranchvars ) 816 { 817 assert( nbranchvars == maxnbranchvars ); 818 assert( maxnbranchvars > 0 ); 819 maxnbranchvars = SCIPcalcMemGrowSize(scip, maxnbranchvars + 1); 820 SCIP_CALL( SCIPreallocBufferArray(scip, &branchvars, maxnbranchvars) ); 821 } 822 assert( nbranchvars < maxnbranchvars ); 823 branchvars[nbranchvars++] = var; 824 } 825 } 826 827 /* skip orbitopes whose variable matrices do not contain any branching variable */ 828 if ( nbranchvars <= 0 ) 829 goto FREE; 830 831 SCIP_CALL( SCIPallocBlockMemory(scip, &newnodeinfo) ); 832 newnodeinfo->nodenumber = SCIPnodeGetNumber(eventnode); 833 newnodeinfo->colswaps = NULL; 834 newnodeinfo->ncolswaps = 0; 835 newnodeinfo->rows = NULL; 836 newnodeinfo->nrows = 0; 837 838 /* store data about row ordering */ 839 if ( orbidata->rowordering != SCIP_ROWORDERING_NONE ) 840 { 841 int* roworder; 842 int nselrows; 843 844 assert( orbidata->nrows > 0 ); 845 assert( orbidata->rowordering == SCIP_ROWORDERING_BRANCHING ); 846 847 /* get the present row order up to this node */ 848 SCIP_CALL( getRowOrder(scip, orbidata, eventnode, &roworder, &nselrows) ); 849 assert( roworder != NULL ); 850 851 /* extend the row fixings with the steps from this node */ 852 for (i = 0; i < nbranchvars; ++i) 853 { 854 var = branchvars[i]; 855 856 assert( SCIPhashmapExists(orbidata->rowindexmap, (void*) var) ); /* otherwise was not added to branchvars */ 857 rowid = SCIPhashmapGetImageInt(orbidata->rowindexmap, (void*) var); 858 assert( rowid >= 0 ); 859 assert( rowid < orbidata->nrows ); 860 861 /* avoid adding row to row order twice */ 862 if ( nselrows > 0 ) 863 { 864 for (j = 0; j < nselrows; ++j) 865 { 866 if ( rowid == roworder[j] ) 867 break; 868 } 869 if ( j < nselrows ) /* if the loop is interrupted */ 870 continue; 871 } 872 873 /* if we end up here, the row index does not appear for any ancestor or the present row order */ 874 875 /* append rowid to present roworder */ 876 roworder[nselrows++] = rowid; 877 878 /* mark that this row index is the new one in the node */ 879 if ( newnodeinfo->rows == NULL ) 880 { 881 assert( newnodeinfo->nrows == 0 ); 882 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &newnodeinfo->rows, newnodeinfo->nrows + 1) ); 883 } 884 else 885 { 886 /* reallocate with linear increments, because we expect 1 branching variable most of the time */ 887 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &newnodeinfo->rows, 888 newnodeinfo->nrows, newnodeinfo->nrows + 1) ); 889 } 890 newnodeinfo->rows[newnodeinfo->nrows++] = rowid; 891 } 892 893 freeRowOrder(scip, orbidata, &roworder); 894 } 895 896 /* store data about column ordering */ 897 if ( orbidata->columnordering != SCIP_COLUMNORDERING_NONE ) 898 { 899 int* colorder; 900 int* colorderinv; 901 COLSWAP* thiscolswap; 902 COLSWAP tmpcolswap; 903 904 assert( orbidata->ncols > 0 ); 905 SCIP_CALL( SCIPallocBufferArray(scip, &colorder, orbidata->ncols) ); 906 SCIP_CALL( SCIPallocBufferArray(scip, &colorderinv, orbidata->ncols) ); 907 908 /* populate colorder with standard ordering */ 909 for (i = 0; i < orbidata->ncols; ++i) 910 colorder[i] = i; 911 912 /* introduce inverse column ordering */ 913 for (i = 0; i < orbidata->ncols; ++i) 914 colorderinv[i] = i; 915 916 /* get the rooted path 917 * 918 * We want to iterate through the bound changes in the order of the rooted path to this node. 919 */ 920 node = SCIPnodeGetParent(eventnode); 921 if ( node != NULL ) 922 { 923 SCIP_CALL( populateRootedPathColumnOrder(orbidata, node, rootedpath, colorder, colorderinv) ); 924 } 925 926 /* get the swap for this node */ 927 for (i = 0; i < nbranchvars; ++i) 928 { 929 SCIP_CALL( updateColumnOrderWhenBranchingOnColumn(scip, orbidata, colorder, 930 colorderinv, branchvars[i], &tmpcolswap) ); 931 932 /* skip trivial swaps of columns */ 933 if ( tmpcolswap.from == tmpcolswap.to ) 934 continue; 935 936 /* mark that this row index is the new one in the node */ 937 if ( newnodeinfo->rows == NULL ) 938 { 939 assert( newnodeinfo->nrows == 0 ); 940 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &newnodeinfo->colswaps, newnodeinfo->ncolswaps + 1) ); 941 } 942 else 943 { 944 /* reallocate with linear increments, because we expect 1 branching variable most of the time */ 945 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &newnodeinfo->colswaps, newnodeinfo->ncolswaps, 946 newnodeinfo->ncolswaps + 1) ); 947 } 948 thiscolswap = &(newnodeinfo->colswaps[newnodeinfo->ncolswaps++]); 949 thiscolswap->from = tmpcolswap.from; 950 thiscolswap->to = tmpcolswap.to; 951 } 952 953 SCIPfreeBufferArray(scip, &colorder); 954 SCIPfreeBufferArray(scip, &colorderinv); 955 } 956 957 /* store updates of row/column order or free memory if no change applied */ 958 if ( newnodeinfo->nrows > 0 || newnodeinfo->ncolswaps > 0 ) 959 { 960 SCIP_CALL( SCIPhashtableSafeInsert(orbidata->nodeinfos, newnodeinfo) ); 961 } 962 else 963 { 964 SCIPfreeBlockMemory(scip, &newnodeinfo); 965 } 966 967 FREE: 968 SCIPfreeBufferArray(scip, &rootedpath); 969 SCIPfreeBufferArray(scip, &branchvars); 970 971 return SCIP_OKAY; 972 } /*lint !e715*/ 973 974 975 /** at branching decisions, maintains the column swap and potential new rows in the orbitope */ 976 static 977 SCIP_DECL_EVENTEXEC(eventExec) 978 { 979 switch (SCIPeventGetType(event)) 980 { 981 case SCIP_EVENTTYPE_NODEBRANCHED: 982 return eventExecNodeBranched(scip, eventhdlr, event, eventdata); 983 default: 984 SCIPerrorMessage("Eventhandler " EVENTHDLR_NAME " is called with an unsupported eventtype.\n"); 985 return SCIP_ERROR; 986 } 987 } 988 989 990 /** returns whether a row contains potential branching variables */ 991 static 992 SCIP_Bool rowIsBranchRow( 993 SCIP* scip, /**< SCIP data structure */ 994 SCIP_ORBITOPALREDDATA* orbireddata, /**< pointer to the dynamic orbitopal reduction data */ 995 ORBITOPEDATA* orbidata, /**< symmetry handling data for orbitopal structure */ 996 int rowid /**< row id for which to check */ 997 ) 998 { 999 SCIP_VAR* var; 1000 #ifndef NDEBUG 1001 int c; 1002 #endif 1003 1004 assert( scip != NULL ); 1005 assert( orbireddata != NULL ); 1006 assert( orbidata != NULL ); 1007 assert( orbidata->nrows > 0 ); 1008 assert( orbidata->ncols > 0 ); 1009 assert( rowid >= 0 ); 1010 assert( rowid < orbidata->nrows ); 1011 assert( orbidata->vars != NULL ); 1012 assert( orbidata->vars[rowid * orbidata->ncols] ); /* variable in first column must be set */ 1013 1014 /* get the first variable from the row */ 1015 var = orbidata->vars[rowid * orbidata->ncols]; 1016 1017 /* debugging: the variable types in a row should all be the same */ 1018 #ifndef NDEBUG 1019 for (c = 1; c < orbidata->ncols; ++c) 1020 { 1021 /* the actual vartypes can be different, 1022 * for example when an INTEGER vartype turns into BINARY due to bound changes 1023 */ 1024 assert( vartypeIsBranchRowType(scip, orbireddata, SCIPvarGetType(var)) == 1025 vartypeIsBranchRowType(scip, orbireddata, SCIPvarGetType(orbidata->vars[rowid * orbidata->ncols + c])) ); 1026 } 1027 #endif 1028 1029 return vartypeIsBranchRowType(scip, orbireddata, SCIPvarGetType(var)); 1030 } 1031 1032 1033 /** frees orbitope data */ 1034 static 1035 SCIP_RETCODE freeOrbitope( 1036 SCIP* scip, /**< SCIP data structure */ 1037 SCIP_ORBITOPALREDDATA* orbireddata, /**< pointer to the dynamic orbitopal reduction data */ 1038 ORBITOPEDATA** orbidata /**< pointer to orbitope data */ 1039 ) 1040 { 1041 BNBNODEINFO* nodeinfo; 1042 int i; 1043 int nentries; 1044 int nelem; 1045 1046 assert( scip != NULL ); 1047 assert( orbireddata != NULL ); 1048 assert( orbidata != NULL ); 1049 assert( *orbidata != NULL ); 1050 assert( (*orbidata)->vars != NULL ); 1051 assert( (*orbidata)->nrows > 0 ); 1052 assert( (*orbidata)->ncols > 0 ); 1053 assert( (*orbidata)->nrows * (*orbidata)->ncols > 0 ); 1054 assert( SCIPisTransformed(scip) ); 1055 1056 /* free data if orbitopal reduction is dynamic */ 1057 if ( (*orbidata)->columnordering != SCIP_COLUMNORDERING_NONE || (*orbidata)->rowordering != SCIP_ROWORDERING_NONE ) 1058 { 1059 /* drop event */ 1060 SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_NODEBRANCHED, orbireddata->eventhdlr, 1061 (SCIP_EVENTDATA*) *orbidata, -1 ) ); 1062 1063 /* free nodeinfos */ 1064 nentries = SCIPhashtableGetNEntries((*orbidata)->nodeinfos); 1065 for (i = 0; i < nentries; ++i) 1066 { 1067 /* @todo in principle, can deal with memory sparsity by first getting all nodeinfos, 1068 * then sorting by address and free them in descending order 1069 */ 1070 nodeinfo = (BNBNODEINFO*) (SCIPhashtableGetEntry((*orbidata)->nodeinfos, i)); 1071 if ( nodeinfo == NULL ) 1072 continue; 1073 1074 assert( nodeinfo != NULL ); 1075 assert( nodeinfo->nrows > 0 || nodeinfo->ncolswaps > 0 ); 1076 1077 assert( (nodeinfo->ncolswaps == 0) != (nodeinfo->colswaps != NULL) ); 1078 SCIPfreeBlockMemoryArrayNull(scip, &(nodeinfo->colswaps), nodeinfo->ncolswaps); 1079 1080 assert( (nodeinfo->nrows == 0) != (nodeinfo->rows != NULL) ); 1081 SCIPfreeBlockMemoryArrayNull(scip, &(nodeinfo->rows), nodeinfo->nrows); 1082 1083 SCIPfreeBlockMemory(scip, &nodeinfo); 1084 } 1085 SCIPhashtableFree(&((*orbidata)->nodeinfos)); 1086 } 1087 1088 /* free index lookup hashsets */ 1089 SCIPhashmapFree(&((*orbidata)->colindexmap)); 1090 SCIPhashmapFree(&((*orbidata)->rowindexmap)); 1091 1092 /* free and release vars */ 1093 nelem = (*orbidata)->nrows * (*orbidata)->ncols; 1094 assert( nelem > 0 ); 1095 for (i = 0; i < nelem; ++i) 1096 { 1097 SCIP_CALL( SCIPreleaseVar(scip, &(*orbidata)->vars[i]) ); 1098 } 1099 SCIPfreeBlockMemoryArray(scip, &((*orbidata)->vars), (*orbidata)->nrows * (*orbidata)->ncols); /*lint !e647*/ 1100 1101 SCIPfreeBlockMemory(scip, orbidata); 1102 1103 return SCIP_OKAY; 1104 } 1105 1106 1107 /** adds an orbitope to the orbitopal reduction data */ 1108 static 1109 SCIP_RETCODE addOrbitope( 1110 SCIP* scip, /**< SCIP data structure */ 1111 SCIP_ORBITOPALREDDATA* orbireddata, /**< pointer to the dynamic orbitopal reduction data */ 1112 SCIP_ROWORDERING rowordering, /**< specifies how rows of orbitope are ordered */ 1113 SCIP_COLUMNORDERING colordering, /**< specifies how columnss of orbitope are ordered */ 1114 SCIP_VAR** vars, /**< variables array, must have size nrows * ncols */ 1115 int nrows, /**< number of rows in orbitope */ 1116 int ncols, /**< number of columns in orbitope */ 1117 SCIP_Bool* success /**< to store whether the component is successfully added */ 1118 ) 1119 { 1120 ORBITOPEDATA* orbidata; 1121 SCIP_VAR* var; 1122 int i; 1123 int rowid; 1124 int colid; 1125 int nelem; 1126 1127 assert( scip != NULL ); 1128 assert( orbireddata != NULL ); 1129 assert( orbireddata->eventhdlr != NULL ); 1130 assert( vars != NULL ); 1131 assert( nrows >= 0 ); 1132 assert( ncols >= 0 ); 1133 1134 nelem = nrows * ncols; 1135 assert( nelem >= 0 ); 1136 1137 /* prevent trivial case with empty orbitope */ 1138 if ( nelem == 0 ) 1139 { 1140 *success = FALSE; 1141 return SCIP_OKAY; 1142 } 1143 1144 *success = TRUE; 1145 1146 SCIP_CALL( SCIPallocBlockMemory(scip, &orbidata) ); 1147 1148 orbidata->nrows = nrows; 1149 orbidata->ncols = ncols; 1150 orbidata->columnordering = colordering; 1151 orbidata->rowordering = rowordering; 1152 1153 #ifndef NDEBUG 1154 orbidata->lastnodenumber = -1; 1155 orbidata->dbghash = 0; 1156 #endif 1157 1158 /* variable array enumerates the orbitope matrix row-wise */ 1159 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &orbidata->vars, nelem) ); 1160 1161 /* create row and column index lookup maps */ 1162 SCIP_CALL( SCIPhashmapCreate(&orbidata->rowindexmap, SCIPblkmem(scip), nrows) ); 1163 SCIP_CALL( SCIPhashmapCreate(&orbidata->colindexmap, SCIPblkmem(scip), ncols) ); 1164 1165 SCIPdebugMessage("Orbitope variables for (%dx%d) orbitope with orbidata %p\n", nrows, ncols, (void*) orbidata); 1166 1167 /* populate variable array defining orbitope matrix for orbitope data */ 1168 for (i = 0, rowid = 0, colid = 0; i < nelem; ++i, ++colid) 1169 { 1170 if ( colid == ncols ) 1171 { 1172 colid = 0; 1173 ++rowid; 1174 } 1175 assert( nrows > 0 ); 1176 assert( ncols > 0 ); 1177 assert( rowid == i / ncols ); 1178 assert( colid == i % ncols ); 1179 1180 var = vars[i]; 1181 assert( var != NULL ); 1182 assert( SCIPvarIsTransformed(var) ); 1183 1184 SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, var) ); 1185 SCIP_CALL( SCIPcaptureVar(scip, var) ); 1186 1187 orbidata->vars[i] = var; 1188 1189 /* variables cannot be repeated in the variable matrix */ 1190 assert( ! SCIPhashmapExists(orbidata->rowindexmap, var) ); 1191 SCIP_CALL( SCIPhashmapInsertInt(orbidata->rowindexmap, var, rowid) ); 1192 1193 assert( ! SCIPhashmapExists(orbidata->colindexmap, var) ); 1194 SCIP_CALL( SCIPhashmapInsertInt(orbidata->colindexmap, var, colid) ); 1195 1196 SCIPdebugMessage("%4d %4d -> %s\n", rowid, colid, var->name); 1197 } 1198 1199 /* count number of branchable rows in orbitope */ 1200 orbidata->nbranchrows = 0; 1201 /* @todo at getRowData: If nselrows == nbranchrows, append the non-branch rows (like before) */ 1202 for (i = 0; i < nrows; ++i) 1203 { 1204 if ( rowIsBranchRow(scip, orbireddata, orbidata, i) ) 1205 ++orbidata->nbranchrows; 1206 } 1207 1208 /* cannot add orbitope when already branching */ 1209 assert( SCIPgetStage(scip) == SCIP_STAGE_SOLVING ? SCIPgetNNodes(scip) == 0 : TRUE ); 1210 1211 /* possibly create data needed for dynamic orbitopal reduction */ 1212 if ( orbidata->columnordering != SCIP_COLUMNORDERING_NONE || orbidata->rowordering != SCIP_ROWORDERING_NONE ) 1213 { 1214 /* add the event to store the row and column updates of nodes in the branch-and-bound tree */ 1215 SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_NODEBRANCHED, orbireddata->eventhdlr, 1216 (SCIP_EVENTDATA*) orbidata, NULL) ); 1217 1218 /* nodeinfos: every node that implies a column swap is represented 1219 * 1220 * Assuming at most one branching on every variable implying a column swap, initial hashtable size nelem. 1221 * In case that there are many more rows than columns, we do not expect too many column swaps. 1222 */ 1223 SCIP_CALL( SCIPhashtableCreate(&orbidata->nodeinfos, scip->mem->probmem, MIN(16 * ncols + 64, nelem), 1224 hashGetKeyBnbnodeinfo, hashKeyEqBnbnodeinfo, hashKeyValBnbnodeinfo, NULL) ); 1225 } 1226 1227 /* resize orbitope array if needed */ 1228 assert( orbireddata->norbitopes >= 0 ); 1229 assert( (orbireddata->norbitopes == 0) == (orbireddata->orbitopes == NULL) ); 1230 assert( orbireddata->norbitopes <= orbireddata->maxnorbitopes ); 1231 if ( orbireddata->norbitopes == orbireddata->maxnorbitopes ) 1232 { 1233 int newsize; 1234 1235 newsize = SCIPcalcMemGrowSize(scip, orbireddata->norbitopes + 1); 1236 assert( newsize >= 0 ); 1237 1238 if ( orbireddata->norbitopes == 0 ) 1239 { 1240 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &orbireddata->orbitopes, newsize) ); 1241 } 1242 else 1243 { 1244 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &orbireddata->orbitopes, orbireddata->norbitopes, newsize) ); 1245 } 1246 1247 orbireddata->maxnorbitopes = newsize; 1248 } 1249 assert( orbireddata->orbitopes != NULL ); 1250 assert( orbireddata->norbitopes < orbireddata->maxnorbitopes ); 1251 1252 /* add orbitope to orbitopal reduction data */ 1253 assert( orbireddata->norbitopes < orbireddata->maxnorbitopes ); 1254 orbireddata->orbitopes[orbireddata->norbitopes++] = orbidata; 1255 1256 SCIPdebugMsg(scip, "Added orbitope for orbitopal reduction of size %d by %d\n", nrows, ncols); 1257 1258 return SCIP_OKAY; 1259 } 1260 1261 1262 /** frees the column order */ 1263 static 1264 void freeColumnOrder( 1265 SCIP* scip, /**< SCIP data structure */ 1266 ORBITOPEDATA* orbidata, /**< orbitope data */ 1267 int** colorder, /**< colorder array that is initialized with the colorder in the dynamic 1268 * case, of size ncols, and NULL in the static case */ 1269 int** colorderinv /**< array with the inverse column order, of size ncols */ 1270 ) 1271 { 1272 assert( scip != NULL ); 1273 assert( orbidata != NULL ); 1274 assert( colorder != NULL ); 1275 assert( colorderinv != NULL ); 1276 1277 if ( orbidata->columnordering == SCIP_COLUMNORDERING_NONE ) 1278 { 1279 assert( *colorder == NULL ); 1280 assert( *colorderinv == NULL ); 1281 return; 1282 } 1283 assert( *colorder != NULL ); 1284 assert( *colorderinv != NULL ); 1285 1286 SCIPfreeBlockMemoryArray(scip, colorder, orbidata->ncols); 1287 SCIPfreeBlockMemoryArray(scip, colorderinv, orbidata->ncols); 1288 } 1289 1290 1291 /** gets the column order at the node 1292 * 1293 * The column order is (deterministically) dynamically decided based on the policy for column ordering. 1294 */ 1295 static 1296 SCIP_RETCODE getColumnOrder( 1297 SCIP* scip, /**< SCIP data structure */ 1298 ORBITOPEDATA* orbidata, /**< orbitope data */ 1299 SCIP_NODE* eventnode, /**< node where this should be determined at */ 1300 int* roworder, /**< array with the row order, of size nselrows */ 1301 int nselrows, /**< number of rows (required to be positive) */ 1302 int** colorder, /**< array to populate with column order, of size ncols */ 1303 int** colorderinv /**< array to populate with inverse column order, of size ncols */ 1304 ) 1305 { 1306 SCIP_NODE* node; 1307 SCIP_NODE** rootedpath; 1308 int i; 1309 int depth; 1310 int ncols; 1311 1312 assert( scip != NULL ); 1313 assert( orbidata != NULL ); 1314 assert( eventnode != NULL ); 1315 assert( roworder != NULL ); 1316 assert( nselrows > 0 ); 1317 assert( colorder != NULL ); 1318 assert( colorderinv != NULL ); 1319 1320 if ( orbidata->columnordering == SCIP_COLUMNORDERING_NONE ) 1321 { 1322 *colorder = NULL; 1323 *colorderinv = NULL; 1324 return SCIP_OKAY; 1325 } 1326 ncols = orbidata->ncols; 1327 assert( ncols > 0 ); 1328 1329 SCIP_CALL( SCIPallocBlockMemoryArray(scip, colorder, ncols) ); 1330 SCIP_CALL( SCIPallocBlockMemoryArray(scip, colorderinv, ncols) ); 1331 1332 /* populate colorder with standard ordering */ 1333 for (i = 0; i < ncols; ++i) 1334 (*colorder)[i] = i; 1335 1336 /* introduce inverse column ordering */ 1337 for (i = 0; i < ncols; ++i) 1338 (*colorderinv)[i] = i; 1339 1340 /* get the rooted path 1341 * 1342 * We want to iterate through the bound changes in the order of the rooted path to this node. 1343 */ 1344 node = SCIPnodeGetParent(eventnode); 1345 if ( node != NULL ) 1346 { 1347 depth = SCIPnodeGetDepth(node); 1348 SCIP_CALL( SCIPallocBufferArray(scip, &rootedpath, depth + 1) ); 1349 SCIP_CALL( populateRootedPathColumnOrder(orbidata, node, rootedpath, *colorder, *colorderinv) ); 1350 SCIPfreeBufferArray(scip, &rootedpath); 1351 } 1352 1353 return SCIP_OKAY; 1354 } 1355 1356 1357 #ifndef NDEBUG 1358 /** checks if the columns of the matrix are lexicographically decreasing, using the specified row and column ordering */ 1359 static 1360 void assertIsOrbitopeMatrix( 1361 SCIP* scip, /**< SCIP data structure */ 1362 ORBITOPEDATA* orbidata, /**< orbitope data */ 1363 int* roworder, /**< array with the row order */ 1364 int* colorder, /**< array with the column order */ 1365 SCIP_Real* matrix, /**< a matrix */ 1366 int nrows, /**< number of rows of matrix */ 1367 int ncols, /**< number of cols of matrix */ 1368 int* infinitesimal, /**< array specifying where the infinitesimals are at */ 1369 SCIP_Bool addinfinitesimals /**< whether infinitesimals are added (TRUE) or subtracted (FALSE) */ 1370 ) 1371 { 1372 int rowid; 1373 int colid; 1374 int idx; 1375 int origrowid; 1376 int origcolid; 1377 int origidx; 1378 SCIP_VAR* var; 1379 1380 assert( scip != NULL ); 1381 assert( matrix != NULL ); 1382 assert( orbidata != NULL ); 1383 assert( orbidata->vars != NULL ); 1384 assert( nrows >= 0 ); 1385 assert( nrows <= orbidata->nrows ); 1386 assert( ncols >= 0 ); 1387 assert( ncols <= orbidata->ncols ); 1388 assert( infinitesimal != NULL ); 1389 1390 /* respect variable bounds */ 1391 for (rowid = 0; rowid < nrows; ++rowid) 1392 { 1393 origrowid = getArrayEntryOrIndex(roworder, rowid); 1394 for (colid = 0; colid < ncols; ++colid) 1395 { 1396 origcolid = getArrayEntryOrIndex(colorder, colid); 1397 idx = rowid * ncols + colid; 1398 origidx = origrowid * ncols + origcolid; 1399 var = orbidata->vars[origidx]; 1400 assert( SCIPGE(scip, matrix[idx], SCIPvarGetLbLocal(var)) ); 1401 assert( SCIPLE(scip, matrix[idx], SCIPvarGetUbLocal(var)) ); 1402 } 1403 } 1404 1405 /* is orbitope */ 1406 for (colid = 0; colid < ncols - 1; ++colid) 1407 { 1408 /* compare column colid with colid + 1 */ 1409 for (rowid = 0; rowid < nrows; ++rowid) 1410 { 1411 /* entry is >= entry to the right */ 1412 assert( SCIPGE(scip, matrix[rowid * ncols + colid], matrix[rowid * ncols + colid + 1]) ); 1413 1414 if ( SCIPGT(scip, matrix[rowid * ncols + colid], matrix[rowid * ncols + colid + 1]) ) 1415 { 1416 /* critical row */ 1417 break; 1418 } 1419 else 1420 { 1421 /* check for infinitesimal values 1422 * If infinitesimals are added (lexminface case), then if the left column has a +epsilon, 1423 * it does not matter whether the right column has +epsilon or not, then the left column is >, 1424 * due to the axioms x + epsilon > x + epsilon and x + epsilon > x. 1425 * Analogously, x > x - epsilon and x - epsilon > x - epsilon. 1426 */ 1427 assert( SCIPEQ(scip, matrix[rowid * ncols + colid], matrix[rowid * ncols + colid + 1]) ); 1428 if ( addinfinitesimals 1429 ? (infinitesimal[colid] == rowid) /* left has +epsilon term */ 1430 : (infinitesimal[colid + 1] == rowid) /* right has -epsilon term */ 1431 ) 1432 { 1433 /* critical row */ 1434 break; 1435 } 1436 } 1437 } 1438 } 1439 } 1440 #endif 1441 1442 #ifndef NDEBUG 1443 /** to test if arrays are the same, generates some hash for an array of integers */ 1444 static 1445 int debugGetArrayHash( 1446 int* array, /** array */ 1447 int len /** array length */ 1448 ) 1449 { 1450 int i; 1451 unsigned int hash = 0; 1452 1453 assert( array != NULL ); 1454 assert( len >= 0 ); 1455 1456 for (i = 0; i < len; i++) 1457 { 1458 hash ^= (unsigned int) (array[i]); 1459 hash = (hash << 1) ^ (hash >> 1); 1460 } 1461 1462 return (int) hash; 1463 } 1464 #endif 1465 1466 #ifdef SCIP_MORE_DEBUG 1467 /** prints nrows × ncols matrix of floats with 2 decimals */ 1468 static 1469 void debugPrintMatrix( 1470 SCIP_Real* matrix, /** matrix, encoded as array enumerating the elements row-wise */ 1471 int nrows, /** number of rows */ 1472 int ncols /** number of rows */ 1473 ) 1474 { 1475 int row; 1476 int col; 1477 1478 assert( matrix != NULL ); 1479 assert( nrows >= 0 ); 1480 assert( ncols >= 0 ); 1481 1482 for (row = 0; row < nrows; ++row) 1483 { 1484 SCIPdebugPrintf("["); 1485 for (col = 0; col < ncols; ++col) 1486 { 1487 SCIPdebugPrintf(" %+10.2f", matrix[row * ncols + col]); 1488 } 1489 SCIPdebugPrintf(" ]\n"); 1490 } 1491 } 1492 #endif 1493 1494 1495 /** gets the column order at the node */ 1496 static 1497 SCIP_RETCODE propagateStaticOrbitope( 1498 SCIP* scip, /**< SCIP data structure */ 1499 ORBITOPEDATA* orbidata, /**< orbitope data */ 1500 int* roworder, /**< array with the row order (or NULL if identity function is used) */ 1501 int nselrows, /**< number of selected rows */ 1502 int* colorder, /**< array with the column order (or NULL if identity function is used) */ 1503 SCIP_Bool* infeasible, /**< pointer to store whether the problem is infeasible */ 1504 int* nfixedvars /**< pointer to counter of number of variable domain reductions */ 1505 ) 1506 { 1507 /* @todo also make "nselcols" to allow for colorders smaller than orbidata->ncols */ 1508 SCIP_Real* lexminface = NULL; 1509 int* lexminepsrow = NULL; 1510 SCIP_Real* lexmaxface = NULL; 1511 int* lexmaxepsrow = NULL; 1512 int nelem; 1513 int rowid; 1514 int colid; 1515 int ncols; 1516 int origrowid; 1517 int origcolid; 1518 int origidx; 1519 int i; 1520 int lastunfixed; 1521 SCIP_Real lb; 1522 SCIP_Real ub; 1523 SCIP_Bool iseq; 1524 SCIP_Bool success; 1525 SCIP_VAR* var; 1526 SCIP_VAR* othervar; 1527 1528 assert( scip != NULL ); 1529 assert( orbidata != NULL ); 1530 assert( orbidata->vars != NULL ); 1531 assert( nselrows >= 0 ); 1532 assert( infeasible != NULL ); 1533 assert( nfixedvars != NULL ); 1534 1535 *infeasible = FALSE; 1536 1537 assert( orbidata->nrows > 0 ); 1538 assert( orbidata->nrows >= nselrows ); 1539 ncols = orbidata->ncols; 1540 assert( ncols > 1 ); 1541 1542 /* nothing to propagate without any rows */ 1543 if ( nselrows <= 0 ) 1544 return SCIP_OKAY; 1545 1546 #ifdef SCIP_MORE_DEBUG 1547 /* print matrix for debugging purposes */ 1548 { 1549 int k; 1550 int r; 1551 SCIP_VAR* thisvar; 1552 SCIPdebugMessage("Start propagating static orbitope: \n"); 1553 SCIPdebugPrintf(">"); 1554 for (k = 0; k < ncols; ++k) 1555 { 1556 SCIPdebugPrintf("%12d ", colorder[k]); 1557 } 1558 SCIPdebugPrintf("< (IDs)\n"); 1559 1560 for (r = 0; r < nselrows; ++r) 1561 { 1562 SCIPdebugPrintf("["); 1563 for (k = 0; k < ncols; ++k) 1564 { 1565 thisvar = orbidata->vars[roworder[r] * ncols + colorder[k]]; 1566 SCIPdebugPrintf("%4s %+1.2f,%+1.2f ", SCIPvarGetName(thisvar), 1567 SCIPvarGetLbLocal(thisvar), SCIPvarGetUbLocal(thisvar)); 1568 } 1569 SCIPdebugPrintf("] (row %d)\n", roworder[r]); 1570 } 1571 } 1572 #endif 1573 1574 nelem = nselrows * ncols; 1575 1576 /* compute lexmin face */ 1577 SCIP_CALL( SCIPallocBufferArray(scip, &lexminface, nelem) ); 1578 1579 /* array to store for each column at which row we add an infinitesimal value, initially at none (-1) */ 1580 SCIP_CALL( SCIPallocBufferArray(scip, &lexminepsrow, ncols) ); 1581 for (colid = 0; colid < ncols; ++colid) 1582 lexminepsrow[colid] = -1; 1583 1584 /* last column takes the minimally possible values. */ 1585 colid = ncols - 1; 1586 origcolid = getArrayEntryOrIndex(colorder, colid); 1587 for (rowid = 0, i = colid; rowid < nselrows; ++rowid, i += ncols) 1588 { 1589 origrowid = getArrayEntryOrIndex(roworder, rowid); 1590 origidx = origrowid * ncols + origcolid; 1591 var = orbidata->vars[origidx]; 1592 1593 assert( i == rowid * ncols + colid ); 1594 assert( var != NULL ); 1595 1596 lexminface[i] = SCIPvarGetLbLocal(var); 1597 } 1598 /* all previous columns: One-column replacement algorithm */ 1599 for (colid = ncols - 2; colid >= 0; --colid) 1600 { 1601 /* "rowid" of the last unfixed entry whose domain allows for larger values than the current chosen. 1602 * If there is none, -1. */ 1603 lastunfixed = -1; 1604 /* whether column "colid" is the same as column "colid + 1" up (but excluding) to "rowid" */ 1605 iseq = TRUE; 1606 1607 origcolid = getArrayEntryOrIndex(colorder, colid); 1608 for (rowid = 0, i = colid; rowid < nselrows; ++rowid, i += ncols) 1609 { 1610 origrowid = getArrayEntryOrIndex(roworder, rowid); 1611 origidx = origrowid * ncols + origcolid; 1612 assert( i == rowid * ncols + colid ); 1613 1614 /* the entry one to the right is not the first column */ 1615 assert( (i + 1) % ncols > 0 ); 1616 1617 var = orbidata->vars[origidx]; 1618 assert( var != NULL ); 1619 1620 if ( iseq ) 1621 { 1622 /* equality holds up to this row 1623 * Compare to the entry value on the column immediately right. 1624 * The value we choose on the left must be at least this. 1625 * 2 Options: 1626 * Option 1: The upper bound is smaller. Then we're in an infeasible situation. Resolve as described below. 1627 * Option 2: The upper bound is greater or equal. 1628 */ 1629 ub = SCIPvarGetUbLocal(var); 1630 1631 /* compare to the value in the column right of it */ 1632 if ( SCIPLT(scip, ub, lexminface[i + 1]) || 1633 ( lexminepsrow[colid + 1] == rowid && SCIPEQ(scip, ub, lexminface[i + 1]) ) ) 1634 { 1635 /* value of this column can only be strictly smaller than the value in the column to its right 1636 * This may not be possible. 1637 * Try to repair: Go back to the last row with "room" left, and make the value minimally larger. 1638 */ 1639 if ( lastunfixed >= 0 ) 1640 { 1641 /* repair: return to the last row with "room", and increase the lexmin-value at that row. */ 1642 assert( SCIPEQ(scip, lexminface[lastunfixed * ncols + colid], 1643 lexminface[lastunfixed * ncols + colid + 1]) ); 1644 othervar = orbidata->vars[getArrayEntryOrIndex(roworder, lastunfixed) * ncols + origcolid]; 1645 switch (SCIPvarGetType(othervar)) 1646 { 1647 case SCIP_VARTYPE_BINARY: 1648 case SCIP_VARTYPE_IMPLINT: 1649 case SCIP_VARTYPE_INTEGER: 1650 /* discrete type with unit steps: Add one to the bound. */ 1651 /* @todo @question Are variable bounds for SCIP_VARTYPE_IMPLINT always integral? */ 1652 assert( SCIPisIntegral(scip, lexminface[lastunfixed * ncols + colid]) ); 1653 lexminface[lastunfixed * ncols + colid] += 1.0; 1654 assert( SCIPisIntegral(scip, lexminface[lastunfixed * ncols + colid]) ); 1655 assert( SCIPLE(scip, lexminface[lastunfixed * ncols + colid], SCIPvarGetUbLocal(othervar)) ); 1656 break; 1657 case SCIP_VARTYPE_CONTINUOUS: 1658 /* continuous type, so add an infinitesimal value to the bound */ 1659 assert( SCIPLE(scip, lexminface[lastunfixed * ncols + colid], SCIPvarGetUbLocal(othervar)) ); 1660 assert( lexminepsrow[colid] == -1 ); 1661 lexminepsrow[colid] = lastunfixed; 1662 break; 1663 default: 1664 return SCIP_ERROR; 1665 } 1666 /* now row "lastunfixed" is greater. Restart from here. */ 1667 iseq = FALSE; 1668 rowid = lastunfixed; /* the next iteration considers "lastunfixed + 1" */ 1669 i = rowid * ncols + colid; 1670 continue; 1671 } 1672 else 1673 { 1674 /* cannot repair. It is infeasible. */ 1675 *infeasible = TRUE; 1676 SCIPdebugMessage("Cannot repair infeasibility for column %d (original: %d), min\n", colid, origcolid); 1677 goto FREE; 1678 } 1679 } 1680 else 1681 { 1682 assert( SCIPGE(scip, ub, lexminface[i + 1]) ); 1683 lb = SCIPvarGetLbLocal(var); 1684 assert( SCIPLE(scip, lb, ub) ); 1685 lexminface[i] = MAX(lexminface[i + 1], lb); 1686 assert( SCIPGE(scip, lexminface[i], lexminface[i + 1]) ); 1687 1688 /* are we still equal? */ 1689 if ( SCIPGT(scip, lexminface[i], lexminface[i + 1]) ) 1690 iseq = FALSE; 1691 else if ( lexminepsrow[colid + 1] == rowid ) 1692 { 1693 assert( SCIPEQ(scip, lexminface[i], lexminface[i + 1]) ); 1694 assert( SCIPvarGetType(orbidata->vars[getArrayEntryOrIndex(roworder, rowid) * ncols + origcolid]) 1695 == SCIP_VARTYPE_CONTINUOUS ); 1696 assert( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS ); 1697 /* right column (colid+1) has value x + epsilon, left column (colid) has value x, now 1698 * must also become x + epsilon in order to be larger or equal 1699 * by axioms, we can squeeze infinitesimals between one other; epsilon > epsilon. 1700 */ 1701 iseq = FALSE; 1702 assert( lexminepsrow[colid] == -1 ); 1703 lexminepsrow[colid] = rowid; 1704 } 1705 1706 /* is there room left to increase this variable further? */ 1707 switch (SCIPvarGetType(var)) 1708 { 1709 case SCIP_VARTYPE_BINARY: 1710 case SCIP_VARTYPE_IMPLINT: 1711 case SCIP_VARTYPE_INTEGER: 1712 /* discrete type with unit steps: Add one to the bound. */ 1713 /* @todo @question Are variable bounds for SCIP_VARTYPE_IMPLINT always integral? */ 1714 /* @todo in principle, this can be made more tight using the hole-lists... */ 1715 assert( SCIPisIntegral(scip, lexminface[i]) ); 1716 if ( SCIPLE(scip, lexminface[i] + 1.0, ub) ) 1717 lastunfixed = rowid; 1718 break; 1719 case SCIP_VARTYPE_CONTINUOUS: 1720 /* continuous type: if we can add an infinitesimal value to the current lexminface[i] value, 1721 * mark row as 'lastunfixed' 1722 */ 1723 if ( SCIPLT(scip, lexminface[i], ub) ) 1724 lastunfixed = rowid; 1725 break; 1726 default: 1727 return SCIP_ERROR; 1728 } 1729 } 1730 } 1731 else 1732 { 1733 /* there had been a row before which breaks the equality-condition, choose minimally possible value */ 1734 lexminface[i] = SCIPvarGetLbLocal(var); 1735 } 1736 } 1737 } 1738 1739 #ifndef NDEBUG 1740 /* sanity checks */ 1741 assertIsOrbitopeMatrix(scip, orbidata, roworder, colorder, lexminface, nselrows, ncols, lexminepsrow, TRUE); 1742 #endif 1743 1744 /* compute lexmax face */ 1745 SCIP_CALL( SCIPallocBufferArray(scip, &lexmaxface, nelem) ); 1746 1747 /* array to store for each column at which row we subtract an infinitesimal value, initially at none (-1) */ 1748 SCIP_CALL( SCIPallocBufferArray(scip, &lexmaxepsrow, ncols) ); 1749 for (colid = 0; colid < ncols; ++colid) 1750 lexmaxepsrow[colid] = -1; 1751 1752 /* first column, fill all unfixed entries with maximally possible values */ 1753 colid = 0; 1754 origcolid = getArrayEntryOrIndex(colorder, colid); 1755 for (rowid = 0, i = colid; rowid < nselrows; ++rowid, i += ncols) 1756 { 1757 origrowid = getArrayEntryOrIndex(roworder, rowid); 1758 origidx = origrowid * ncols + origcolid; 1759 var = orbidata->vars[origidx]; 1760 1761 assert( i == rowid * ncols + colid ); 1762 assert( var != NULL ); 1763 1764 lexmaxface[i] = SCIPvarGetUbLocal(var); 1765 } 1766 /* all next columns: One-column replacement algorithm */ 1767 for (colid = 1; colid < ncols; ++colid) 1768 { 1769 /* "rowid" of the last unfixed entry whose domain allows for smaller values than the current chosen. 1770 * If there is none, -1. */ 1771 lastunfixed = -1; 1772 /* whether column "colid" is the same as column "colid - 1" up (but excluding) to "rowid" */ 1773 iseq = TRUE; 1774 1775 origcolid = getArrayEntryOrIndex(colorder, colid); 1776 for (rowid = 0, i = colid; rowid < nselrows; ++rowid, i += ncols) 1777 { 1778 origrowid = getArrayEntryOrIndex(roworder, rowid); 1779 origidx = origrowid * ncols + origcolid; 1780 assert( i == rowid * ncols + colid ); 1781 1782 /* the entry one to the left is not the last column, i.e., this column cannot be the first column */ 1783 assert( i % ncols > 0 ); 1784 1785 var = orbidata->vars[origidx]; 1786 assert( var != NULL ); 1787 1788 if ( iseq ) 1789 { 1790 /* equality holds up to this row 1791 * Compare to the entry value on the column immediately left. 1792 * The value we choose on the right must be at most this. 1793 * 2 Options: 1794 * Option 1: The lower bound is larger. Then we're in an infeasible situation. Resolve as described below. 1795 * Option 2: The lower bound is smaller or equal. 1796 */ 1797 lb = SCIPvarGetLbLocal(var); 1798 1799 /* compare to the value in the column left of it */ 1800 if ( SCIPGT(scip, lb, lexmaxface[i - 1]) || 1801 ( lexmaxepsrow[colid - 1] == rowid && SCIPEQ(scip, lb, lexmaxface[i - 1]) ) ) 1802 { 1803 /* value of this column can only be strictly larger than the value in the column to its left 1804 * This may not be possible. 1805 * Try to repair: Go back to the last row with "room" left, and make the value minimally smaller. 1806 */ 1807 if ( lastunfixed >= 0 ) 1808 { 1809 /* repair: return to the last row with "room", and decrease the lexmax-value at that row. */ 1810 assert( SCIPEQ(scip, lexmaxface[lastunfixed * ncols + colid], 1811 lexmaxface[lastunfixed * ncols + colid - 1]) ); 1812 othervar = orbidata->vars[getArrayEntryOrIndex(roworder, lastunfixed) * ncols + origcolid]; 1813 switch (SCIPvarGetType(othervar)) 1814 { 1815 case SCIP_VARTYPE_BINARY: 1816 case SCIP_VARTYPE_IMPLINT: 1817 case SCIP_VARTYPE_INTEGER: 1818 /* discrete type with unit steps: Remove one from the lexmax-value. */ 1819 /* @todo @question Are variable bounds for SCIP_VARTYPE_IMPLINT always integral? */ 1820 assert( SCIPisIntegral(scip, lexmaxface[lastunfixed * ncols + colid]) ); 1821 lexmaxface[lastunfixed * ncols + colid] -= 1.0; 1822 assert( SCIPisIntegral(scip, lexmaxface[lastunfixed * ncols + colid]) ); 1823 assert( SCIPGE(scip, lexmaxface[lastunfixed * ncols + colid], SCIPvarGetLbLocal(othervar)) ); 1824 assert( SCIPLE(scip, lexmaxface[lastunfixed * ncols + colid], SCIPvarGetUbLocal(othervar)) ); 1825 break; 1826 case SCIP_VARTYPE_CONTINUOUS: 1827 /* continuous type, so subtract an infinitesimal value to the bound */ 1828 assert( SCIPGE(scip, lexmaxface[lastunfixed * ncols + colid], SCIPvarGetLbLocal(othervar)) ); 1829 assert( SCIPLE(scip, lexmaxface[lastunfixed * ncols + colid], SCIPvarGetUbLocal(othervar)) ); 1830 assert( lexmaxepsrow[colid] == -1 ); 1831 lexmaxepsrow[colid] = lastunfixed; 1832 break; 1833 default: 1834 return SCIP_ERROR; 1835 } 1836 /* now row "lastunfixed" is greater. Restart from here. */ 1837 iseq = FALSE; 1838 rowid = lastunfixed; /* the next iteration considers "lastunfixed + 1" */ 1839 i = rowid * ncols + colid; 1840 continue; 1841 } 1842 else 1843 { 1844 /* cannot repair. It is infeasible. */ 1845 *infeasible = TRUE; 1846 SCIPdebugMessage("Cannot repair infeasibility for column %d (original: %d), max\n", colid, origcolid); 1847 goto FREE; 1848 } 1849 } 1850 else 1851 { 1852 assert( SCIPLE(scip, lb, lexmaxface[i - 1]) ); 1853 ub = SCIPvarGetUbLocal(var); 1854 assert( SCIPLE(scip, lb, ub) ); 1855 lexmaxface[i] = MIN(lexmaxface[i - 1], ub); 1856 assert( SCIPGE(scip, lexmaxface[i - 1], lexmaxface[i]) ); 1857 1858 /* are we still equal? */ 1859 if ( SCIPGT(scip, lexmaxface[i - 1], lexmaxface[i]) ) 1860 iseq = FALSE; 1861 else if ( lexmaxepsrow[colid - 1] == rowid ) 1862 { 1863 assert( SCIPEQ(scip, lexmaxface[i - 1], lexmaxface[i]) ); 1864 assert( SCIPvarGetType(orbidata->vars[getArrayEntryOrIndex(roworder, rowid) * ncols + origcolid]) 1865 == SCIP_VARTYPE_CONTINUOUS ); 1866 assert( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS ); 1867 /* left column (colid-1) has value x - epsilon, right column (colid) has value x, now 1868 * must also become x - epsilon in order to be larger or equal 1869 * by axioms, we can squeeze infinitesimals between one other; epsilon > epsilon. 1870 */ 1871 iseq = FALSE; 1872 assert( lexmaxepsrow[colid] == -1 ); 1873 lexmaxepsrow[colid] = rowid; 1874 } 1875 1876 /* is there room left to decrease this variable further? */ 1877 switch (SCIPvarGetType(var)) 1878 { 1879 case SCIP_VARTYPE_BINARY: 1880 case SCIP_VARTYPE_IMPLINT: 1881 case SCIP_VARTYPE_INTEGER: 1882 /* discrete type with unit steps: Remove one from the lexmax-value. */ 1883 /* @todo @question Are variable bounds for SCIP_VARTYPE_IMPLINT always integral? */ 1884 /* @todo in principle, this can be made more tight using the hole-lists... */ 1885 assert( SCIPisIntegral(scip, lexmaxface[i]) ); 1886 if ( SCIPGE(scip, lexmaxface[i] - 1.0, lb) ) 1887 lastunfixed = rowid; 1888 break; 1889 case SCIP_VARTYPE_CONTINUOUS: 1890 /* continuous type: if we can subtract an infinitesimal value to the current lexmaxface[i] value, 1891 * mark row as 'lastunfixed' 1892 */ 1893 if ( SCIPGT(scip, lexmaxface[i], lb) ) 1894 lastunfixed = rowid; 1895 break; 1896 default: 1897 return SCIP_ERROR; 1898 } 1899 } 1900 } 1901 else 1902 { 1903 /* there had been a row before which breaks the equality-condition, choose maximally possible value */ 1904 lexmaxface[i] = SCIPvarGetUbLocal(var); 1905 } 1906 } 1907 } 1908 1909 #ifndef NDEBUG 1910 /* sanity checks */ 1911 assertIsOrbitopeMatrix(scip, orbidata, roworder, colorder, lexmaxface, nselrows, ncols, lexmaxepsrow, FALSE); 1912 #endif 1913 1914 #ifdef SCIP_MORE_DEBUG 1915 /* show lexmin and lexmax face */ 1916 SCIPdebugMessage("Lex min face\n"); 1917 debugPrintMatrix(lexminface, nselrows, ncols); 1918 SCIPdebugMessage("Lex max face\n"); 1919 debugPrintMatrix(lexmaxface, nselrows, ncols); 1920 #endif 1921 1922 /* compare the two column-wise and apply domain reductions */ 1923 for (colid = 0; colid < ncols; ++colid) 1924 { 1925 for (rowid = 0, i = colid; rowid < nselrows; ++rowid, i += ncols) 1926 { 1927 assert( i == rowid * ncols + colid ); 1928 1929 /* get var */ 1930 origrowid = getArrayEntryOrIndex(roworder, rowid); 1931 origcolid = getArrayEntryOrIndex(colorder, colid); 1932 origidx = origrowid * ncols + origcolid; 1933 var = orbidata->vars[origidx]; 1934 1935 if ( SCIPEQ(scip, lexminface[i], lexmaxface[i]) ) 1936 { 1937 /* tighten LB and UB to same value (i.e. fixing) */ 1938 SCIP_CALL( SCIPtightenVarLb(scip, var, lexminface[i], FALSE, infeasible, &success) ); 1939 if ( success ) 1940 { 1941 SCIPdebugMessage("Fixing variable LB %12s (%3d,%3d) to %5.2f\n", var->name, rowid, colid, lexminface[i]); 1942 *nfixedvars += 1; 1943 } 1944 else 1945 { 1946 SCIPdebugMessage("Fixing variable LB %12s (%3d,%3d) to %5.2f (no success)\n", var->name, rowid, colid, 1947 lexminface[i]); 1948 } 1949 if ( *infeasible ) 1950 { 1951 SCIPdebugMessage("Detected infeasibility fixing variable %12s (%3d,%3d) to %5.2f\n", 1952 var->name, rowid, colid, lexminface[i]); 1953 goto FREE; 1954 } 1955 1956 SCIP_CALL( SCIPtightenVarUb(scip, var, lexminface[i], FALSE, infeasible, &success) ); 1957 if ( success ) 1958 { 1959 SCIPdebugMessage("Fixing variable UB %12s (%3d,%3d) to %5.2f\n", var->name, rowid, colid, lexminface[i]); 1960 *nfixedvars += 1; 1961 } 1962 else 1963 { 1964 SCIPdebugMessage("Fixing variable UB %12s (%3d,%3d) to %5.2f (no success)\n", var->name, rowid, colid, 1965 lexminface[i]); 1966 } 1967 if ( *infeasible ) 1968 { 1969 SCIPdebugMessage("Detected infeasibility fixing variable %12s (%3d,%3d) to %5.2f\n", 1970 var->name, rowid, colid, lexminface[i]); 1971 goto FREE; 1972 } 1973 } 1974 else 1975 { 1976 /* This is the row index where the min- and max-face have a different value for this column entry. 1977 * Update the lower bound and upper bound */ 1978 1979 /* lower bound, based on lexminface */ 1980 SCIP_CALL( SCIPtightenVarLb(scip, var, lexminface[i], FALSE, infeasible, &success) ); 1981 if ( success ) 1982 { 1983 SCIPdebugMessage("Restricting variable LB %12s (%3d,%3d) to %5.2f\n", var->name, rowid, colid, 1984 lexminface[i]); 1985 *nfixedvars += 1; 1986 } 1987 else 1988 { 1989 SCIPdebugMessage("Restricting variable LB %12s (%3d,%3d) to %5.2f (no success)\n", var->name, 1990 rowid, colid, lexminface[i]); 1991 } 1992 if ( *infeasible ) 1993 { 1994 SCIPdebugMessage("Detected infeasibility restricting variable LB %12s (%3d,%3d) to %5.2f\n", 1995 var->name, rowid, colid, lexminface[i]); 1996 goto FREE; 1997 } 1998 1999 /* upper bound, based on lexmaxface */ 2000 SCIP_CALL( SCIPtightenVarUb(scip, var, lexmaxface[i], FALSE, infeasible, &success) ); 2001 if ( success ) 2002 { 2003 SCIPdebugMessage("Restricting variable UB %12s (%3d,%3d) to %5.2f\n", var->name, rowid, colid, 2004 lexmaxface[i]); 2005 *nfixedvars += 1; 2006 } 2007 else 2008 { 2009 SCIPdebugMessage("Restricting variable UB %12s (%3d,%3d) to %5.2f (no success)\n", var->name, 2010 rowid, colid, lexmaxface[i]); 2011 } 2012 if ( *infeasible ) 2013 { 2014 SCIPdebugMessage("Detected infeasibility restricting variable UB %12s (%3d,%3d) to %5.2f\n", 2015 var->name, rowid, colid, lexmaxface[i]); 2016 goto FREE; 2017 } 2018 break; 2019 } 2020 } 2021 } 2022 2023 FREE: 2024 SCIPfreeBufferArrayNull(scip, &lexmaxepsrow); 2025 SCIPfreeBufferArrayNull(scip, &lexmaxface); 2026 SCIPfreeBufferArrayNull(scip, &lexminepsrow); 2027 SCIPfreeBufferArrayNull(scip, &lexminface); 2028 2029 return SCIP_OKAY; 2030 } 2031 2032 2033 /** propagation method for a single orbitope matrix */ 2034 static 2035 SCIP_RETCODE propagateOrbitope( 2036 SCIP* scip, /**< SCIP data structure */ 2037 ORBITOPEDATA* orbidata, /**< orbitope data */ 2038 SCIP_Bool* infeasible, /**< pointer to store whether the problem is infeasible */ 2039 int* nfixedvars /**< pointer to store the number of found domain reductions */ 2040 ) 2041 { 2042 SCIP_NODE* focusnode; 2043 int* roworder; 2044 int nselrows; 2045 int* colorder; 2046 int* colorderinv; 2047 2048 assert( scip != NULL ); 2049 assert( orbidata != NULL ); 2050 assert( infeasible != NULL ); 2051 assert( nfixedvars != NULL ); 2052 2053 *nfixedvars = 0; 2054 *infeasible = FALSE; 2055 2056 assert( orbidata->ncols > 0 ); 2057 assert( orbidata->nrows > 0 ); 2058 2059 focusnode = SCIPgetFocusNode(scip); 2060 assert( focusnode != NULL ); 2061 2062 /* get row order */ 2063 SCIP_CALL( getRowOrder(scip, orbidata, focusnode, &roworder, &nselrows) ); 2064 assert( nselrows >= 0 ); 2065 assert( nselrows <= orbidata->nrows ); 2066 if ( nselrows == 0 ) 2067 goto FREEROWS; 2068 2069 /* get column order */ 2070 SCIP_CALL( getColumnOrder(scip, orbidata, focusnode, roworder, nselrows, &colorder, &colorderinv) ); 2071 2072 #ifndef NDEBUG 2073 /* DEBUG: if propagation is repeated in the same node, the same column order and row order is needed */ 2074 /* @todo: performance: move roworder and colorder to orbidata, then re-use */ 2075 { 2076 int colhash = (colorder == NULL) ? 1 : debugGetArrayHash(colorder, orbidata->ncols); 2077 int rowhash = (roworder == NULL) ? 0 : debugGetArrayHash(roworder, nselrows); 2078 int hash = colhash ^ rowhash; 2079 2080 #ifdef SCIP_DEBUG 2081 SCIPdebugPrintf("Col hash %32d; Row hash %32d; Hash %32d\n", colhash, rowhash, hash); 2082 { 2083 SCIP_NODE* tmpnode; 2084 tmpnode = SCIPgetFocusNode(scip); 2085 while ( tmpnode != NULL ) 2086 { 2087 int nbranchings, nconsprop, nprop; 2088 SCIPnodeGetDomchg(tmpnode); 2089 SCIPnodeGetNDomchg(tmpnode, &nbranchings, &nconsprop, &nprop); 2090 SCIPdebugPrintf(" node %lld: (%d, %d, %d) \n", tmpnode->number, nbranchings, nconsprop, nprop); 2091 tmpnode = SCIPnodeGetParent(tmpnode); 2092 } 2093 } 2094 #endif 2095 2096 assert( SCIPgetCurrentNode(scip) == SCIPgetFocusNode(scip) ); /* no probing */ 2097 if ( orbidata->lastnodenumber == SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) ) 2098 { 2099 assert( orbidata->dbghash == hash ); 2100 } 2101 orbidata->dbghash = hash; 2102 } 2103 orbidata->lastnodenumber = SCIPnodeGetNumber(SCIPgetCurrentNode(scip)); 2104 #endif 2105 2106 SCIP_CALL( propagateStaticOrbitope(scip, orbidata, roworder, nselrows, colorder, infeasible, nfixedvars) ); 2107 2108 freeColumnOrder(scip, orbidata, &colorder, &colorderinv); 2109 FREEROWS: 2110 freeRowOrder(scip, orbidata, &roworder); 2111 2112 #ifdef SCIP_MORE_DEBUG 2113 SCIPdebugPrintf("\n\n"); 2114 #endif 2115 2116 return SCIP_OKAY; 2117 } 2118 2119 2120 /* 2121 * Interface methods 2122 */ 2123 2124 2125 /** gets the number of reductions */ 2126 SCIP_RETCODE SCIPorbitopalReductionGetStatistics( 2127 SCIP* scip, /**< SCIP data structure */ 2128 SCIP_ORBITOPALREDDATA* orbireddata, /**< orbitopal reduction data structure */ 2129 int* nred, /**< total number of reductions applied */ 2130 int* ncutoff /**< total number of cutoffs applied */ 2131 ) 2132 { 2133 assert( scip != NULL ); 2134 assert( orbireddata != NULL ); 2135 assert( nred != NULL ); 2136 2137 *nred = orbireddata->nred; 2138 *ncutoff = orbireddata->ncutoff; 2139 2140 return SCIP_OKAY; 2141 } 2142 2143 2144 /** prints orbitopal reduction data */ 2145 SCIP_RETCODE SCIPorbitopalReductionPrintStatistics( 2146 SCIP* scip, /**< SCIP data structure */ 2147 SCIP_ORBITOPALREDDATA* orbireddata /**< orbitopal reduction data structure */ 2148 ) 2149 { 2150 int i; 2151 2152 assert( scip != NULL ); 2153 assert( orbireddata != NULL ); 2154 2155 if ( orbireddata->norbitopes == 0 ) 2156 { 2157 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " orbitopal reduction: no components\n"); 2158 return SCIP_OKAY; 2159 } 2160 2161 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, 2162 " orbitopal reduction: %4d components: ", orbireddata->norbitopes); 2163 for (i = 0; i < orbireddata->norbitopes; ++i) 2164 { 2165 if ( i > 0 ) 2166 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, ", "); 2167 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, 2168 "%dx%d", orbireddata->orbitopes[i]->nrows, orbireddata->orbitopes[i]->ncols); 2169 } 2170 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "\n"); 2171 2172 return SCIP_OKAY; 2173 } 2174 2175 2176 /** propagates orbitopal reduction */ 2177 SCIP_RETCODE SCIPorbitopalReductionPropagate( 2178 SCIP* scip, /**< SCIP data structure */ 2179 SCIP_ORBITOPALREDDATA* orbireddata, /**< orbitopal reduction data structure */ 2180 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is found */ 2181 int* nred, /**< pointer to store the number of domain reductions */ 2182 SCIP_Bool* didrun /**< a global pointer maintaining if any symmetry propagator has run 2183 * only set this to TRUE when a reduction is found, never set to FALSE */ 2184 ) 2185 { 2186 ORBITOPEDATA* orbidata; 2187 int c; 2188 int thisfixedvars; 2189 2190 assert( scip != NULL ); 2191 assert( orbireddata != NULL ); 2192 assert( (orbireddata->norbitopes == 0) == (orbireddata->orbitopes == NULL) ); 2193 assert( infeasible != NULL ); 2194 assert( nred != NULL ); 2195 2196 *infeasible = FALSE; 2197 *nred = 0; 2198 2199 /* @todo Can the following be removed? */ 2200 /* @todo shouldn't this be SCIPallowWeakDualReds, since we do not regard the objective */ 2201 if ( ! SCIPallowStrongDualReds(scip) ) 2202 return SCIP_OKAY; 2203 2204 /* cannot do anything during probing 2205 * @todo can find deductions for the probing node, maybe? 2206 */ 2207 if ( SCIPinProbing(scip) ) 2208 return SCIP_OKAY; 2209 2210 /* propagate all orbitopes */ 2211 for (c = 0; c < orbireddata->norbitopes; ++c) 2212 { 2213 orbidata = orbireddata->orbitopes[c]; 2214 assert( orbidata != NULL ); 2215 2216 SCIP_CALL( propagateOrbitope(scip, orbidata, infeasible, &thisfixedvars) ); 2217 SCIPdebugMessage("Found %d reductions during orbitopal reduction for orbitope %d\n", thisfixedvars, c); 2218 *nred += thisfixedvars; 2219 2220 /* a symmetry propagator has ran, so set didrun to TRUE */ 2221 *didrun = TRUE; 2222 2223 /* stop if we find infeasibility in one of the methods */ 2224 if ( *infeasible ) 2225 { 2226 SCIPdebugMessage("Detected infeasibility during orbitopal reduction for orbitope %d\n", c); 2227 break; 2228 } 2229 } 2230 2231 orbireddata->nred += *nred; 2232 if ( *infeasible ) 2233 ++orbireddata->ncutoff; 2234 2235 return SCIP_OKAY; 2236 } 2237 2238 /** adds orbitopal component to orbitopal symmetry handler */ 2239 SCIP_RETCODE SCIPorbitopalReductionAddOrbitope( 2240 SCIP* scip, /**< SCIP data structure */ 2241 SCIP_ORBITOPALREDDATA* orbireddata, /**< orbitopal reduction data structure */ 2242 SCIP_ROWORDERING rowordering, /**< specifies how rows of orbitope are ordered */ 2243 SCIP_COLUMNORDERING colordering, /**< specifies how columnss of orbitope are ordered */ 2244 SCIP_VAR** vars, /**< matrix of variables on which the symmetry acts */ 2245 int nrows, /**< number of rows */ 2246 int ncols, /**< number of columns */ 2247 SCIP_Bool* success /**< to store whether the component is successfully added */ 2248 ) 2249 { 2250 assert( scip != NULL ); 2251 assert( orbireddata != NULL ); 2252 assert( vars != NULL ); 2253 assert( nrows > 0 ); 2254 assert( ncols > 0 ); 2255 2256 /* dynamic symmetry reductions cannot be performed on original problem */ 2257 assert( SCIPisTransformed(scip) ); 2258 2259 /* if this is the first time adding an orbitope, check if the nonlinear conshlr exists */ 2260 if ( !orbireddata->conshdlr_nonlinear_checked ) 2261 { 2262 orbireddata->conshdlr_nonlinear = SCIPfindConshdlr(scip, "nonlinear"); 2263 orbireddata->conshdlr_nonlinear_checked = TRUE; 2264 } 2265 2266 /* create orbitope data */ 2267 SCIP_CALL( addOrbitope(scip, orbireddata, rowordering, colordering, vars, nrows, ncols, success) ); 2268 2269 return SCIP_OKAY; 2270 } 2271 2272 2273 /** resets orbitopal reduction data structure (clears all orbitopes) */ 2274 SCIP_RETCODE SCIPorbitopalReductionReset( 2275 SCIP* scip, /**< SCIP data structure */ 2276 SCIP_ORBITOPALREDDATA* orbireddata /**< pointer to orbitopal reduction structure to populate */ 2277 ) 2278 { 2279 assert( scip != NULL ); 2280 assert( orbireddata != NULL ); 2281 assert( orbireddata->norbitopes >= 0 ); 2282 assert( (orbireddata->norbitopes == 0) == (orbireddata->orbitopes == NULL) ); 2283 assert( orbireddata->norbitopes <= orbireddata->maxnorbitopes ); 2284 assert( orbireddata->eventhdlr != NULL ); 2285 2286 /* free orbitopes that are added */ 2287 while (orbireddata->norbitopes > 0) 2288 { 2289 SCIP_CALL( freeOrbitope(scip, orbireddata, &(orbireddata->orbitopes[--orbireddata->norbitopes])) ); 2290 } 2291 assert( orbireddata->norbitopes == 0 ); 2292 SCIPfreeBlockMemoryArrayNull(scip, &orbireddata->orbitopes, orbireddata->maxnorbitopes); 2293 orbireddata->orbitopes = NULL; 2294 orbireddata->maxnorbitopes = 0; 2295 2296 return SCIP_OKAY; 2297 } 2298 2299 2300 /** frees orbitopal reduction data */ 2301 SCIP_RETCODE SCIPorbitopalReductionFree( 2302 SCIP* scip, /**< SCIP data structure */ 2303 SCIP_ORBITOPALREDDATA** orbireddata /**< pointer to orbitopal reduction structure to populate */ 2304 ) 2305 { 2306 assert( scip != NULL ); 2307 assert( orbireddata != NULL ); 2308 assert( *orbireddata != NULL ); 2309 2310 SCIP_CALL( SCIPorbitopalReductionReset(scip, *orbireddata) ); 2311 2312 SCIPfreeBlockMemory(scip, orbireddata); 2313 return SCIP_OKAY; 2314 } 2315 2316 2317 /** initializes structures needed for orbitopal reduction 2318 * 2319 * This is only done exactly once. 2320 */ 2321 SCIP_RETCODE SCIPincludeOrbitopalReduction( 2322 SCIP* scip, /**< SCIP data structure */ 2323 SCIP_ORBITOPALREDDATA** orbireddata /**< pointer to orbitopal reduction structure to populate */ 2324 ) 2325 { 2326 SCIP_EVENTHDLR* eventhdlr; 2327 2328 assert( scip != NULL ); 2329 assert( orbireddata != NULL ); 2330 2331 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeOrbitopalReduction", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, 2332 FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 2333 2334 /* create orbitope handler data */ 2335 SCIP_CALL( SCIPallocBlockMemory(scip, orbireddata) ); 2336 2337 /* default column ordering param */ 2338 SCIP_CALL( SCIPaddIntParam(scip, "propagating/symmetry/" SYMHDLR_NAME "/columnordering", 2339 "The column ordering variant, respects enum SCIP_ColumnOrdering.", 2340 (int*) &(*orbireddata)->defaultcolumnordering, TRUE, DEFAULT_COLUMNORDERING, 0, 4, 2341 NULL, NULL) ); /*lint !e641*/ 2342 2343 /* initialize event handler. */ 2344 assert( SCIPfindEventhdlr(scip, EVENTHDLR_NAME) == NULL ); 2345 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExec, NULL) ); 2346 assert( eventhdlr != NULL ); 2347 (*orbireddata)->eventhdlr = eventhdlr; 2348 2349 /* orbitopes array */ 2350 (*orbireddata)->orbitopes = NULL; 2351 (*orbireddata)->norbitopes = 0; 2352 (*orbireddata)->maxnorbitopes = 0; 2353 2354 /* conshdlr nonlinear */ 2355 (*orbireddata)->conshdlr_nonlinear = NULL; 2356 (*orbireddata)->conshdlr_nonlinear_checked = FALSE; 2357 2358 /* counter of total number of reductions and cutoffs */ 2359 (*orbireddata)->nred = 0; 2360 (*orbireddata)->ncutoff = 0; 2361 2362 return SCIP_OKAY; 2363 } 2364 2365 2366 /** returns the default column ordering */ 2367 SCIP_COLUMNORDERING SCIPorbitopalReductionGetDefaultColumnOrdering( 2368 SCIP_ORBITOPALREDDATA* orbireddata /**< pointer to orbitopal reduction structure to populate */ 2369 ) 2370 { 2371 assert( orbireddata != NULL ); 2372 2373 return orbireddata->defaultcolumnordering; 2374 } 2375