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 presol_tworowbnd.c 26 * @ingroup DEFPLUGINS_PRESOL 27 * @brief do bound tightening by using two rows 28 * @author Dieter Weninger 29 * @author Patrick Gemander 30 * 31 * Perform bound tightening on two inequalities with some common variables. 32 * Two possible methods are being used. 33 * 34 * 1. LP-bound 35 * Let two constraints be given: 36 * \f{eqnarray*}{ 37 * A_{iR} x_R + A_{iS} x_S \geq b_i\\ 38 * A_{kR} x_R + A_{kT} x_T \geq b_k 39 * \f} 40 * with \f$N\f$ the set of variable indexes, \f$R \subseteq N\f$, \f$S \subseteq N\f$, \f$T \subseteq N\f$, 41 * \f$R \cap S = \emptyset\f$, \f$R \cap T = \emptyset\f$, \f$S \cap T = \emptyset\f$ and row indices \f$i \not= k\f$. 42 * 43 * Let \f$\ell\f$ and \f$u\f$ be bound vectors for x and solve the following two LPs 44 * \f{eqnarray*}{ 45 * L = \min \{ A_{kR} x_R : A_{iR} x_R + A_{iS} x_S \geq b_i, \ell \leq x \leq u \}\\ 46 * U = \max \{ A_{kR} x_R : A_{iR} x_R + A_{iS} x_S \geq b_i, \ell \leq x \leq u \} 47 * \f} 48 * and use \f$L\f$ and \f$U\f$ for getting bounds on \f$x_T\f$. 49 * 50 * If \f$L + \mbox{infimum}(A_{kT}x_T) \geq b_k\f$, then the second constraint above is redundant. 51 * 52 * More details can be found in 53 * - Chen W. et. al "Two-row and two-column mixed-integer presolve using hashing-based pairing methods" 54 */ 55 56 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 57 58 /* 59 * Additional debug defines in this presolver 60 * SCIP_DEBUG_HASHING 61 * SCIP_DEBUG_BOUNDS 62 * SCIP_DEBUG_SINGLEROWLP 63 */ 64 65 #include <assert.h> 66 67 #include "scip/cons_linear.h" 68 #include "scip/scipdefplugins.h" 69 #include "scip/pub_matrix.h" 70 #include "scip/presol_tworowbnd.h" 71 #include <string.h> 72 73 #define PRESOL_NAME "tworowbnd" 74 #define PRESOL_DESC "do bound tigthening by using two rows" 75 #define PRESOL_PRIORITY -2000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers); combined with propagators */ 76 #define PRESOL_MAXROUNDS 0 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */ 77 #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ 78 79 #define DEFAULT_ENABLECOPY TRUE /**< should tworowbnd presolver be copied to sub-SCIPs? */ 80 #define DEFAULT_MAXCONSIDEREDNONZEROS 100 /**< maximal number of considered non-zeros within one row (-1: no limit) */ 81 #define DEFAULT_MAXRETRIEVEFAILS 1000 /**< maximal number of consecutive useless hashtable retrieves */ 82 #define DEFAULT_MAXCOMBINEFAILS 1000 /**< maximal number of consecutive useless row combines */ 83 #define DEFAULT_MAXHASHFAC 10 /**< maximal number of hashlist entries as multiple of number of rows in the problem (-1: no limit) */ 84 #define DEFAULT_MAXPAIRFAC 1 /**< maximal number of processed row pairs as multiple of the number of rows in the problem (-1: no limit) */ 85 86 /* 87 * Data structures 88 */ 89 90 /** presolver data */ 91 struct SCIP_PresolData 92 { 93 int maxpairfac; /**< maximal number of processed row pairs as multiple of the number of rows in the problem (-1: no limit) */ 94 int maxhashfac; /**< maximal number of hashlist entries as multiple of number of rows in the problem (-1: no limit) */ 95 int maxretrievefails; /**< maximal number of consecutive useless hashtable retrieves */ 96 int maxcombinefails; /**< maximal number of consecutive useless row combines */ 97 int maxconsiderednonzeros; /**< maximal number of considered non-zeros within one row (-1: no limit) */ 98 int nchgbnds; /**< number of variable bounds changed by this presolver */ 99 int nuselessruns; /**< number of runs where this presolver did not apply any changes */ 100 SCIP_Bool enablecopy; /**< should tworowbnd presolver be copied to sub-SCIPs? */ 101 }; 102 103 /** structure representing a pair of row indices; used for lookup in a hashtable */ 104 struct RowPair 105 { 106 int row1idx; /**< first row index */ 107 int row2idx; /**< second row index */ 108 }; 109 110 typedef struct RowPair ROWPAIR; 111 112 113 /* 114 * Local methods 115 */ 116 117 /** encode contents of a rowpair as void* pointer */ 118 static 119 void* encodeRowPair( 120 ROWPAIR* rowpair /**< pointer to rowpair */ 121 ) 122 { 123 uint64_t a = (uint64_t)(long)rowpair->row1idx; 124 uint64_t b = (uint64_t)(long)rowpair->row2idx; 125 return (void*)((a << 32) | b); 126 } 127 128 /** compute single positive int hashvalue for two ints */ 129 static 130 int hashIndexPair( 131 int idx1, /**< first integer index */ 132 int idx2 /**< second integer index */ 133 ) 134 { 135 uint32_t hash = SCIPhashTwo(idx1, idx2); 136 return (int)(hash >> 1); 137 } 138 139 /** add hash/rowidx pair to hashlist/rowidxlist */ 140 static 141 SCIP_RETCODE addEntry( 142 SCIP* scip, /**< SCIP datastructure */ 143 int* pos, /**< position of last entry added */ 144 int* listsize, /**< size of hashlist and rowidxlist */ 145 int** hashlist, /**< block memory array containing hashes */ 146 int** rowidxlist, /**< block memory array containing row indices */ 147 int hash, /**< hash to be inserted */ 148 int rowidx /**< row index to be inserted */ 149 ) 150 { 151 if( (*pos) >= (*listsize) ) 152 { 153 int newsize = SCIPcalcMemGrowSize(scip, (*pos) + 1); 154 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, hashlist, (*listsize), newsize) ); 155 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, rowidxlist, (*listsize), newsize) ); 156 (*listsize) = newsize; 157 } 158 159 (*hashlist)[(*pos)] = hash; 160 (*rowidxlist)[(*pos)] = rowidx; 161 (*pos)++; 162 163 return SCIP_OKAY; 164 } 165 166 /* Within a sorted list, get next block with same value 167 * E.g. for [h1, h1, h1, h2, h2, h2, h2, h3,...] and end = 0 168 * returns start = 0, end = 3 169 * and on a second call with end = 3 on the same list 170 * returns start = 3, end = 7. 171 */ 172 static 173 void findNextBlock( 174 int* list, /**< list of integers */ 175 int len, /**< length of list */ 176 int* start, /**< variable to contain start index of found block */ 177 int* end /**< variable to contain end index of found block */ 178 ) 179 { 180 int i; 181 (*start) = (*end); 182 i = (*end) + 1; 183 while( i < len && list[i] == list[i - 1] ) 184 i++; 185 186 (*end) = i; 187 } 188 189 /* Solve single-row LP of the form 190 * min c^T x 191 * s.t. a^T x >= b 192 * lbs <= x <= ubs 193 * 194 * First, the problem is transformed such that 195 * SCIPselectWeightedReal() can be applied, which 196 * then solves the problem as a continuous knapsack 197 * in linear time. 198 */ 199 static 200 SCIP_RETCODE solveSingleRowLP( 201 SCIP* scip, /**< SCIP data structure */ 202 SCIP_Real* a, /**< constraint coefficients */ 203 SCIP_Real b, /**< right hand side */ 204 SCIP_Real* c, /**< objective coefficients */ 205 SCIP_Real* lbs, /**< lower variable bounds */ 206 SCIP_Real* ubs, /**< upper variable bounds */ 207 int len, /**< length of arrays */ 208 SCIP_Real* obj, /**< objective value of solution */ 209 SCIP_Bool* solvable /**< status whether LP was solvable */ 210 ) 211 { 212 int i; 213 int k; 214 int nvars; 215 SCIP_Real lb; 216 SCIP_Real ub; 217 SCIP_Real mincost; 218 SCIP_Real maxgain; 219 220 #ifdef SCIP_DEBUG_SINGLEROWLP 221 SCIPdebugMsg(scip, "solving single row LP with %d variables\n", len); 222 #endif 223 224 nvars = 0; 225 (*obj) = 0; 226 (*solvable) = TRUE; 227 mincost = SCIPinfinity(scip); 228 maxgain = 0; 229 for( i = 0; i < len; i++) 230 { 231 /* Handle variables with zero weight */ 232 if( SCIPisZero(scip, a[i]) ) 233 { 234 /* a[i] = 0, c[i] > 0 */ 235 if( SCIPisPositive(scip, c[i]) ) 236 { 237 if( SCIPisInfinity(scip, -lbs[i]) ) 238 { 239 (*solvable) = FALSE; 240 return SCIP_OKAY; 241 } 242 else 243 (*obj) += c[i] * lbs[i]; 244 } 245 /* a[i] = 0, c[i] < 0 */ 246 else if( SCIPisNegative(scip, c[i]) ) 247 { 248 if( SCIPisInfinity(scip, ubs[i]) ) 249 { 250 (*solvable) = FALSE; 251 return SCIP_OKAY; 252 } 253 else 254 (*obj) += c[i] * ubs[i]; 255 } 256 /* Note that variables with a[i] = 0, c[i] = 0 can be ignored */ 257 continue; 258 } 259 260 /* Handle free variables */ 261 if( SCIPisInfinity(scip, -lbs[i]) && SCIPisInfinity(scip, ubs[i]) ) 262 { 263 /* The problem is unbounded */ 264 if( (SCIPisPositive(scip, c[i]) && SCIPisNegative(scip, a[i])) || 265 (SCIPisNegative(scip, c[i]) && SCIPisPositive(scip, a[i])) ) 266 { 267 (*solvable) = FALSE; 268 return SCIP_OKAY; 269 } 270 else 271 { 272 mincost = MIN(mincost, c[i] / a[i]); 273 maxgain = MAX(maxgain, c[i] / a[i]); 274 } 275 continue; 276 } 277 278 /* Swap variable orientation if lower bound is infinite */ 279 if( SCIPisInfinity(scip, -lbs[i]) ) 280 { 281 c[i] = -c[i]; 282 a[i] = -a[i]; 283 lb = -ubs[i]; 284 ub = -lbs[i]; 285 } 286 else 287 { 288 lb = lbs[i]; 289 ub = ubs[i]; 290 } 291 292 /* Handle variables with infinite upper bound */ 293 if( SCIPisInfinity(scip, ub) ) 294 { 295 if( SCIPisPositive(scip, a[i]) ) 296 { 297 /* a[i] > 0, c[i] >= 0 */ 298 if( !SCIPisNegative(scip, c[i]) ) 299 { 300 mincost = MIN(mincost, c[i]/a[i]); 301 } 302 /* a[i] > 0, c[i] < 0 */ 303 else 304 { 305 (*solvable) = FALSE; 306 return SCIP_OKAY; 307 } 308 } 309 /* a[i] < 0, c[i] < 0 */ 310 else if( SCIPisNegative(scip, c[i]) ) 311 { 312 maxgain = MAX(maxgain, c[i] / a[i]); 313 } 314 /* a[i] < 0, c[i] >= 0 results in dual fixing of this variable, which is included in the bound shift below */ 315 316 /* Shift lower bound to zero */ 317 if( !SCIPisZero(scip, lb) ) 318 { 319 (*obj) += c[i] * lb; 320 b -= a[i] * lb; 321 } 322 continue; 323 } 324 325 /* Handle fixed variables */ 326 if( SCIPisEQ(scip, lb, ub) ) 327 { 328 (*obj) += c[i] * lb; 329 b -= a[i] * lb; 330 continue; 331 } 332 333 /* Dual fixing for variables with finite bounds */ 334 if( !SCIPisNegative(scip, c[i]) && SCIPisNegative(scip, a[i]) ) 335 { 336 (*obj) += c[i] * lb; 337 b -= a[i] * lb; 338 continue; 339 } 340 else if( !SCIPisPositive(scip, c[i]) && SCIPisPositive(scip, a[i]) ) 341 { 342 (*obj) += c[i] * ub; 343 b -= a[i] * ub; 344 continue; 345 } 346 347 assert(!SCIPisInfinity(scip, -lb)); 348 assert(!SCIPisInfinity(scip, ub)); 349 350 /* At this point the variable has finite bounds and a[i],c[i] are both positive or both negative. 351 * Normalize variable such that 352 * 1. x_i \in [0,1] 353 * 2. a[i] > 0 354 * 3. c[i] >= 0 355 * and calculate its "unit price" c[i]/a[i]. 356 */ 357 if( SCIPisNegative(scip, a[i]) ) 358 { 359 c[i] = -c[i]; 360 a[i] = -a[i]; 361 lb = -ubs[i]; 362 ub = -lbs[i]; 363 } 364 365 /* All variables with a <= 0 have been handled and variables with a[i] = 0, c[i] = 0 ignored */ 366 assert(SCIPisPositive(scip, a[i]) && SCIPisPositive(scip, c[i])); 367 368 /* Adjust objective offset and b to shift lower bound to zero */ 369 (*obj) += c[i] * lb; 370 b -= a[i] * lb; 371 372 /* Calculate unit price */ 373 c[nvars] = c[i] / a[i]; 374 375 /* Normalize bound [0, ub] to [0,1] */ 376 a[nvars] = (ub - lb) * a[i]; 377 nvars++; 378 } 379 380 #ifdef SCIP_DEBUG_SINGLEROWLP 381 SCIPdebugMsg(scip, "After preprocessing: obj = %g, b = %g, nvars = %d, mincost = %g, maxgain = %g\n", (*obj), b, nvars, mincost, maxgain); 382 #endif 383 384 /* Actual solving starts here. 385 * If maxgain > 0 holds, we have a variable that can relax the constraint to an arbitrary degree while yielding 386 * a certain profit per unit. This will be called downslack. If mincost < inf holds, we have a variable that can 387 * always satisfy the constraint at a certain unit price. This will be called upslack. 388 */ 389 390 /* Problem is unbounded since the downslack variable yields higher gains than the upslack variable costs */ 391 if( SCIPisLT(scip, mincost, maxgain) ) 392 { 393 (*solvable) = FALSE; 394 return SCIP_OKAY; 395 } 396 /* Solution is trivial as we have slack variables of equal price for both directions */ 397 else if( SCIPisEQ(scip, mincost, maxgain) ) 398 { 399 /* Use all elements with cost smaller than maxgain */ 400 for( i = 0; i < nvars; i++ ) 401 { 402 if( SCIPisLT(scip, c[i], maxgain) ) 403 { 404 (*obj) += c[i] * a[i]; 405 b -= a[i]; 406 } 407 } 408 /* Use slack variable to satisfy constraint */ 409 (*obj) += mincost * b; 410 return SCIP_OKAY; 411 } 412 /* mincost > maxgain 413 * In this case we need to solve the problem for the remaining variables with mincost > c[i] > maxgain. 414 */ 415 else 416 { 417 /* Only keep variables that are cheaper than the upslack variable */ 418 if( !SCIPisInfinity(scip, mincost) ) 419 { 420 k = 0; 421 for( i = 0; i < nvars; i++ ) 422 { 423 if( SCIPisLT(scip, c[i], mincost) ) 424 { 425 c[k] = c[i]; 426 a[k] = a[i]; 427 k++; 428 } 429 } 430 nvars = k; 431 } 432 433 /* Exploit all variables that are cheaper than the downslack variable */ 434 if( !SCIPisZero(scip, maxgain) ) 435 { 436 k = 0; 437 for( i = 0; i < nvars; i++ ) 438 { 439 if( SCIPisLE(scip, c[i], maxgain) ) 440 { 441 (*obj) += c[i] * a[i]; 442 b -= a[i]; 443 } 444 else 445 { 446 c[k] = c[i]; 447 a[k] = a[i]; 448 k++; 449 } 450 } 451 if( !SCIPisPositive(scip, b) ) 452 { 453 (*obj) += maxgain * b; 454 return SCIP_OKAY; 455 } 456 nvars = k; 457 } 458 459 #ifdef SCIP_DEBUG_SINGLEROWLP 460 SCIPdebugMsg(scip, "After exploiting slacks: obj = %g, nvars = %d\n", (*obj), nvars); 461 #endif 462 463 /* If there are no variables left we can trivially put together a solution or determine infeasibility */ 464 if( nvars == 0 ) 465 { 466 if( !SCIPisInfinity(scip, mincost) ) 467 { 468 (*obj) += mincost * b; 469 return SCIP_OKAY; 470 } 471 else 472 { 473 (*solvable) = FALSE; 474 return SCIP_OKAY; 475 } 476 } 477 /* Solve the remaining part of the problem */ 478 else 479 { 480 assert(nvars > 0); 481 #ifdef SCIP_DEBUG_SINGLEROWLP 482 for( i = 0; i < nvars; i++ ) 483 SCIPdebugMsg(scip, "c[%d] = %g, a[%d] = %g\n", i, c[i], i, a[i]); 484 #endif 485 486 SCIPselectWeightedReal(c, a, b, nvars, &k); 487 488 #ifdef SCIP_DEBUG_SINGLEROWLP 489 SCIPdebugMsg(scip, "k-mean = %g at index %d\n", c[k], k, b); 490 for( i = 0; i < nvars; i++ ) 491 SCIPdebugMsg(scip, "c[%d] = %g, a[%d] = %g\n", i, c[i], i, a[i]); 492 #endif 493 494 /* Finalize objective value of solution. First we use all elements cheaper than the k-median */ 495 for( i = 0; i < k; i++ ) 496 { 497 (*obj) += c[i] * a[i]; 498 b -= a[i]; 499 } 500 501 #ifdef SCIP_DEBUG_SINGLEROWLP 502 SCIPdebugMsg(scip, "LP is solved: b = %g\n", b); 503 #endif 504 505 /* If the constraint is not yet satisfied, we have to fix that */ 506 if( SCIPisPositive(scip, b) ) 507 { 508 /* There exists an element to satisfy the constraint */ 509 if( k < nvars ) 510 { 511 (*obj) += c[k] * b; 512 return SCIP_OKAY; 513 } 514 /* There is an upslack variable to satisfy the constraint */ 515 else if( !SCIPisInfinity(scip, mincost) ) 516 { 517 #ifdef SCIP_DEBUG_SINGLEROWLP 518 SCIPdebugMsg(scip, "We use %g units of upslack to satisfy the constraint\n", b); 519 #endif 520 (*obj) += mincost * b; 521 return SCIP_OKAY; 522 } 523 /* We cannot satisfy the constraint so the problem is infeasible */ 524 else 525 { 526 (*solvable) = FALSE; 527 return SCIP_OKAY; 528 } 529 } 530 /* The constraint is already satisfied, i.e. b <= 0 */ 531 else 532 { 533 return SCIP_OKAY; 534 } 535 } 536 } 537 } 538 539 /** Transform rows into single row LPs, solve them and and tighten bounds 540 * 541 * During transformation, create coefficient arrays where variables with a zero coefficient in both rows are ignored 542 * and bring the LP in the form min c^T x, s.t. a^T x >= b, lbs <= x <= ubs. 543 * These LPs are then solved and bounds tightened as described in LP-bound (see above). 544 */ 545 static 546 SCIP_RETCODE transformAndSolve( 547 SCIP* scip, /**< SCIP data structure */ 548 SCIP_MATRIX* matrix, /**< constraint matrix object, rows specified by row1idx/row2idx must be sorted */ 549 int row1idx, /**< index of first row */ 550 int row2idx, /**< index of second row */ 551 SCIP_Bool swaprow1, /**< should row1 <= rhs be used in addition to lhs <= row1 */ 552 SCIP_Bool swaprow2, /**< should row2 <= rhs be used in addition to lhs <= row2 */ 553 SCIP_Real* aoriginal, /**< buffer array for original constraint coefficients */ 554 SCIP_Real* acopy, /**< buffer array for coefficients adjusted to single-row LP to be solved */ 555 SCIP_Real* coriginal, /**< buffer array for original objective coefficients */ 556 SCIP_Real* ccopy, /**< buffer array for coefficients adjusted to single-row LP to be solved */ 557 SCIP_Bool* cangetbnd, /**< buffer array for flags of which variables a bound can be generated */ 558 SCIP_Real* lbs, /**< buffer array for lower bounds for single-row LP */ 559 SCIP_Real* ubs, /**< buffer array for upper bounds for single-row LP */ 560 SCIP_Real* newlbsoriginal, /**< buffer array for new lower bounds not adjusted to individual single-row LPs */ 561 SCIP_Real* newlbscopy, /**< buffer array for adjusted lower bounds */ 562 SCIP_Real* newubsoriginal, /**< buffer array for new upper bounds not adjusted to individual single-row LPs */ 563 SCIP_Real* newubscopy, /**< buffer array for adjusted upper bounds */ 564 SCIP_Bool* success, /**< return (success || "found better bounds") */ 565 SCIP_Bool* infeasible /**< we return (infeasible || "detected infeasibility") */ 566 ) 567 { 568 int i; 569 int j; 570 int idx1; 571 int idx2; 572 int row1len; 573 int row2len; 574 int* row1idxptr; 575 int* row2idxptr; 576 SCIP_Real* row1valptr; 577 SCIP_Real* row2valptr; 578 int nvars; 579 SCIP_Real minact; 580 SCIP_Real maxact; 581 int maxinfs; 582 int mininfs; 583 584 SCIP_Bool minsolvable; 585 SCIP_Real minobj = SCIP_INVALID; 586 SCIP_Bool maxsolvable; 587 SCIP_Real maxobj; 588 SCIP_Bool minswapsolvable; 589 SCIP_Real minswapobj = 0.0; 590 SCIP_Bool maxswapsolvable; 591 SCIP_Real maxswapobj; 592 593 SCIP_Real newbnd; 594 595 assert(!swaprow1 || (swaprow1 && !SCIPisInfinity(scip, SCIPmatrixGetRowRhs(matrix, row1idx)))); 596 assert(!swaprow2 || (swaprow2 && !SCIPisInfinity(scip, SCIPmatrixGetRowRhs(matrix, row2idx)))); 597 598 row1len = SCIPmatrixGetRowNNonzs(matrix, row1idx); 599 row2len = SCIPmatrixGetRowNNonzs(matrix, row2idx); 600 row1idxptr = SCIPmatrixGetRowIdxPtr(matrix, row1idx); 601 row2idxptr = SCIPmatrixGetRowIdxPtr(matrix, row2idx); 602 row1valptr = SCIPmatrixGetRowValPtr(matrix, row1idx); 603 row2valptr = SCIPmatrixGetRowValPtr(matrix, row2idx); 604 605 /* Preprocess rows: 606 * 1. Calculate minimal and maximal activity of variables not appearing in both rows, 607 * as this represents the right-hand sides of the single-row LPs to be solved. 608 * 2. Transform rows into format required by solveSingleRowLP where 609 * first row represents the objective vector c and second row represents the constraint vector a. 610 * 3. Determine for which variables new bounds can be calculated. 611 */ 612 i = 0; 613 j = 0; 614 nvars = 0; 615 mininfs = 0; 616 maxinfs = 0; 617 minact = 0; 618 maxact = 0; 619 while( i < row1len && j < row2len ) 620 { 621 idx1 = row1idxptr[i]; 622 idx2 = row2idxptr[j]; 623 624 if( idx1 == idx2 ) 625 { 626 coriginal[nvars] = row1valptr[i]; 627 aoriginal[nvars] = row2valptr[j]; 628 newlbsoriginal[nvars] = lbs[idx1]; 629 newubsoriginal[nvars] = ubs[idx1]; 630 cangetbnd[idx1] = FALSE; 631 nvars++; 632 #ifdef SCIP_DEBUG_2RB 633 SCIPdebugMsg(scip, "%g <= (%s) <= %g has coefs %g and %g, %d LP vars\n", 634 lbs[idx1], SCIPvarGetName(SCIPmatrixGetVar(matrix, idx1)), 635 ubs[idx1], row1valptr[i], row2valptr[j], nvars); 636 #endif 637 i++; 638 j++; 639 } 640 else if( idx1 < idx2 ) 641 { 642 if( SCIPisPositive(scip, row1valptr[i]) ) 643 { 644 if( SCIPisInfinity(scip, ubs[idx1]) ) 645 maxinfs++; 646 else 647 maxact -= row1valptr[i] * ubs[idx1]; 648 649 if( SCIPisInfinity(scip, -lbs[idx1]) ) 650 mininfs++; 651 else 652 minact -= row1valptr[i] * lbs[idx1]; 653 } 654 else 655 { 656 if( SCIPisInfinity(scip, -lbs[idx1]) ) 657 maxinfs++; 658 else 659 maxact -= row1valptr[i] * lbs[idx1]; 660 661 if( SCIPisInfinity(scip, ubs[idx1]) ) 662 mininfs++; 663 else 664 minact -= row1valptr[i] * ubs[idx1]; 665 666 cangetbnd[idx1] = TRUE; 667 } 668 if( maxinfs > 1 && mininfs > 1 ) 669 { 670 (*success) = FALSE; 671 return SCIP_OKAY; 672 } 673 i++; 674 #ifdef SCIP_DEBUG_2RB 675 SCIPdebugMsg(scip, "%g <= (%s) <= %g has coefs %g and 0.0, minact = %g, maxact = %g\n", 676 lbs[idx1], SCIPvarGetName(SCIPmatrixGetVar(matrix, idx1)), 677 ubs[idx1], row1valptr[i], minact, maxact); 678 #endif 679 } 680 else 681 { 682 coriginal[nvars] = 0.0; 683 aoriginal[nvars] = row2valptr[j]; 684 newlbsoriginal[nvars] = lbs[idx2]; 685 newubsoriginal[nvars] = ubs[idx2]; 686 cangetbnd[idx2] = FALSE; 687 nvars++; 688 #ifdef SCIP_DEBUG_2RB 689 SCIPdebugMsg(scip, "%g <= (%s) <= %g has coefs 0.0 and %g, %d LP vars\n", 690 lbs[idx2], SCIPvarGetName(SCIPmatrixGetVar(matrix, idx2)), 691 ubs[idx2], row2valptr[j], nvars); 692 #endif 693 j++; 694 } 695 } 696 while( i < row1len ) 697 { 698 idx1 = row1idxptr[i]; 699 if( SCIPisPositive(scip, row1valptr[i]) ) 700 { 701 if( SCIPisInfinity(scip, ubs[idx1]) ) 702 maxinfs++; 703 else 704 maxact -= row1valptr[i] * ubs[idx1]; 705 706 if( SCIPisInfinity(scip, -lbs[idx1]) ) 707 mininfs++; 708 else 709 minact -= row1valptr[i] * lbs[idx1]; 710 } 711 else 712 { 713 if( SCIPisInfinity(scip, -lbs[idx1]) ) 714 maxinfs++; 715 else 716 maxact -= row1valptr[i] * lbs[idx1]; 717 718 if( SCIPisInfinity(scip, ubs[idx1]) ) 719 mininfs++; 720 else 721 minact -= row1valptr[i] * ubs[idx1]; 722 } 723 cangetbnd[idx1] = TRUE; 724 #ifdef SCIP_DEBUG_2RB 725 SCIPdebugMsg(scip, "%g <= (%s) <= %g has coefs %g and 0.0, minact = %g, maxact = %g\n", 726 lbs[idx1], SCIPvarGetName(SCIPmatrixGetVar(matrix, idx1)), 727 ubs[idx1], row1valptr[i], minact, maxact); 728 #endif 729 i++; 730 } 731 while( j < row2len ) 732 { 733 idx2 = row2idxptr[j]; 734 coriginal[nvars] = 0.0; 735 aoriginal[nvars] = row2valptr[j]; 736 newlbsoriginal[nvars] = lbs[idx2]; 737 newubsoriginal[nvars] = ubs[idx2]; 738 nvars++; 739 #ifdef SCIP_DEBUG_2RB 740 SCIPdebugMsg(scip, "%g <= (%s) <= %g has coefs 0.0 and %g, %d LP vars\n", 741 lbs[idx2], SCIPvarGetName(SCIPmatrixGetVar(matrix, idx2)), 742 ubs[idx2], row2valptr[j], nvars); 743 #endif 744 j++; 745 } 746 747 #ifdef SCIP_DEBUG_2RB 748 SCIPdebugMsg(scip, "right hand sides: %g and %g\n", 749 SCIPmatrixGetRowLhs(matrix, row1idx), SCIPmatrixGetRowLhs(matrix, row2idx)); 750 #endif 751 752 /* solve single-row LPs */ 753 maxsolvable = FALSE; 754 minsolvable = FALSE; 755 maxswapsolvable = FALSE; 756 minswapsolvable = FALSE; 757 /* maximize overlap in first row with lhs <= row2 as constraint */ 758 if( maxinfs <= 1 ) 759 { 760 for( i = 0; i < nvars; i++ ) 761 { 762 acopy[i] = aoriginal[i]; 763 ccopy[i] = -coriginal[i]; 764 newlbscopy[i] = newlbsoriginal[i]; 765 newubscopy[i] = newubsoriginal[i]; 766 } 767 SCIP_CALL( solveSingleRowLP(scip, acopy, SCIPmatrixGetRowLhs(matrix, row2idx), 768 ccopy, newlbscopy, newubscopy, nvars, &maxobj, &maxsolvable) ); 769 #ifdef SCIP_DEBUG_2RB 770 SCIPdebugMsg(scip, "max-LP solved: obj = %g\n", maxobj); 771 #endif 772 } 773 774 /* minimize overlap in first row with lhs <= row2 as constraint */ 775 if( mininfs == 0 || (mininfs == 1 && swaprow1) ) 776 { 777 /* copy coefficients */ 778 for( i = 0; i < nvars; i++ ) 779 { 780 acopy[i] = aoriginal[i]; 781 ccopy[i] = coriginal[i]; 782 newlbscopy[i] = newlbsoriginal[i]; 783 newubscopy[i] = newubsoriginal[i]; 784 } 785 SCIP_CALL( solveSingleRowLP(scip, acopy, SCIPmatrixGetRowLhs(matrix, row2idx), 786 ccopy, newlbscopy, newubscopy, nvars, &minobj, &minsolvable) ); 787 #ifdef SCIP_DEBUG_2RB 788 SCIPdebugMsg(scip, "min-LP solved: obj = %g\n", minobj); 789 #endif 790 } 791 792 if( swaprow2 ) 793 { 794 /* maximize overlap in first row with row2 <= rhs as constraint */ 795 if( maxinfs <= 1 ) 796 { 797 /* copy coefficients */ 798 for( i = 0; i < nvars; i++ ) 799 { 800 acopy[i] = -aoriginal[i]; 801 ccopy[i] = -coriginal[i]; 802 newlbscopy[i] = newlbsoriginal[i]; 803 newubscopy[i] = newubsoriginal[i]; 804 } 805 SCIP_CALL( solveSingleRowLP(scip, acopy, -SCIPmatrixGetRowRhs(matrix, row2idx), 806 ccopy, newlbscopy, newubscopy, nvars, &maxswapobj, &maxswapsolvable) ); 807 #ifdef SCIP_DEBUG_2RB 808 SCIPdebugMsg(scip, "maxswap-LP solved: obj = %g\n", maxswapobj); 809 #endif 810 } 811 812 /* minimize overlap in first row with row2 <= rhs as constraint */ 813 if( mininfs == 0 || (mininfs == 1 && swaprow1) ) 814 { 815 /* copy coefficients */ 816 for( i = 0; i < nvars; i++ ) 817 { 818 acopy[i] = -aoriginal[i]; 819 ccopy[i] = coriginal[i]; 820 newlbscopy[i] = newlbsoriginal[i]; 821 newubscopy[i] = newubsoriginal[i]; 822 } 823 SCIP_CALL( solveSingleRowLP(scip, acopy, -SCIPmatrixGetRowRhs(matrix, row2idx), 824 ccopy, newlbscopy, newubscopy, nvars, &minswapobj, &minswapsolvable) ); 825 #ifdef SCIP_DEBUG_2RB 826 SCIPdebugMsg(scip, "minswap-LP solved: obj = %g\n", minswapobj); 827 #endif 828 } 829 } 830 831 /* perform bound tightening, infeasibility checks and redundancy checks */ 832 if( maxinfs <= 1 && (maxsolvable || maxswapsolvable) ) 833 { 834 SCIP_Real activity; 835 836 if( maxsolvable && maxswapsolvable ) 837 activity = MAX(maxobj, maxswapobj) + SCIPmatrixGetRowLhs(matrix, row1idx) + maxact; /*lint !e644*/ 838 else if( maxsolvable ) 839 activity = maxobj + SCIPmatrixGetRowLhs(matrix, row1idx) + maxact; /*lint !e644*/ 840 else 841 activity = maxswapobj + SCIPmatrixGetRowLhs(matrix, row1idx) + maxact; /*lint !e644*/ 842 843 /* infeasibility check */ 844 if( maxinfs == 0 && SCIPisPositive(scip, activity) ) 845 { 846 (*infeasible) = TRUE; 847 (*success) = TRUE; 848 return SCIP_OKAY; 849 } 850 /* strengthen bounds of all variables outside overlap */ 851 else if( maxinfs == 0 ) 852 { 853 for( i = 0; i < row1len; i++ ) 854 { 855 idx1 = row1idxptr[i]; 856 if( cangetbnd[idx1] ) 857 { 858 if( SCIPisPositive(scip, row1valptr[i]) ) 859 { 860 if( SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_BINARY 861 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_INTEGER 862 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_IMPLINT ) 863 newbnd = SCIPceil(scip, (activity + row1valptr[i] * ubs[idx1]) / row1valptr[i]); 864 else 865 newbnd = (activity + row1valptr[i] * ubs[idx1]) / row1valptr[i]; 866 867 if( SCIPisGT(scip, newbnd, lbs[idx1]) ) 868 { 869 #ifdef SCIP_DEBUG_BOUNDS 870 SCIPdebugMsg(scip, "%g <= %g <= %s <= %g\n", 871 lbs[idx1], newbnd, SCIPmatrixGetColName(matrix, idx1), ubs[idx1]); 872 #endif 873 lbs[idx1] = newbnd; 874 (*success) = TRUE; 875 } 876 } 877 else 878 { 879 assert(SCIPisNegative(scip, row1valptr[i])); 880 if( SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_BINARY 881 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_INTEGER 882 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_IMPLINT ) 883 newbnd = SCIPfloor(scip, (activity + row1valptr[i] * lbs[idx1]) / row1valptr[i]); 884 else 885 newbnd = (activity + row1valptr[i] * lbs[idx1]) / row1valptr[i]; 886 887 if( SCIPisLT(scip, newbnd, ubs[idx1]) ) 888 { 889 #ifdef SCIP_DEBUG_BOUNDS 890 SCIPdebugMsg(scip, "%g <= %s <= %g <= %g\n", 891 lbs[idx1], SCIPmatrixGetColName(matrix, idx1), newbnd, ubs[idx1]); 892 #endif 893 ubs[idx1] = newbnd; 894 (*success) = TRUE; 895 } 896 } 897 } 898 } 899 } 900 /* strengthen bound of the single variable contributing the infinity */ 901 else 902 { 903 assert(maxinfs == 1); 904 for( i = 0; i < row1len; i++ ) 905 { 906 idx1 = row1idxptr[i]; 907 if( cangetbnd[idx1] ) 908 { 909 if( SCIPisPositive(scip, row1valptr[i]) && SCIPisInfinity(scip, ubs[idx1]) ) 910 { 911 if( SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_BINARY 912 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_INTEGER 913 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_IMPLINT ) 914 newbnd = SCIPceil(scip, activity / row1valptr[i]); 915 else 916 newbnd = activity / row1valptr[i]; 917 918 if( SCIPisGT(scip, newbnd, lbs[idx1]) ) 919 { 920 #ifdef SCIP_DEBUG_BOUNDS 921 SCIPdebugMsg(scip, "%g <= %g <= %s <= %g\n", 922 lbs[idx1], newbnd, SCIPmatrixGetColName(matrix, idx1), ubs[idx1]); 923 #endif 924 lbs[idx1] = newbnd; 925 (*success) = TRUE; 926 } 927 } 928 else if( SCIPisInfinity(scip, -lbs[idx1]) ) 929 { 930 assert(SCIPisNegative(scip, row1valptr[i])); 931 if( SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_BINARY 932 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_INTEGER 933 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_IMPLINT ) 934 newbnd = SCIPfloor(scip, activity / row1valptr[i]); 935 else 936 newbnd = activity / row1valptr[i]; 937 938 if( SCIPisLT(scip, newbnd, ubs[idx1]) ) 939 { 940 #ifdef SCIP_DEBUG_BOUNDS 941 SCIPdebugMsg(scip, "%g <= %s <= %g <= %g\n", 942 lbs[idx1], SCIPmatrixGetColName(matrix, idx1), newbnd, ubs[idx1]); 943 #endif 944 ubs[idx1] = newbnd; 945 (*success) = TRUE; 946 } 947 } 948 } 949 } 950 } 951 } 952 953 /* in this case the objective is swapped. therefore the minimum and the maximum of the support switch roles */ 954 if( swaprow1 ) 955 { 956 /* perform bound tightening, infeasibility checks and redundancy checks */ 957 if( mininfs <= 1 && (minsolvable || minswapsolvable) ) 958 { 959 SCIP_Real activity; 960 961 assert(minobj != SCIP_INVALID); /*lint !e777*/ 962 if( minsolvable && minswapsolvable ) 963 activity = MAX(minobj, minswapobj) - SCIPmatrixGetRowRhs(matrix, row1idx) - minact; 964 else if( minsolvable ) 965 activity = minobj - SCIPmatrixGetRowRhs(matrix, row1idx) - minact; 966 else 967 activity = minswapobj - SCIPmatrixGetRowRhs(matrix, row1idx) - minact; 968 969 /* infeasibility check */ 970 if( mininfs == 0 && SCIPisPositive(scip, activity) ) 971 { 972 (*infeasible) = TRUE; 973 (*success) = TRUE; 974 return SCIP_OKAY; 975 } 976 /* strengthen bounds of all variables outside overlap */ 977 else if( mininfs == 0 ) 978 { 979 for( i = 0; i < row1len; i++ ) 980 { 981 idx1 = row1idxptr[i]; 982 if( cangetbnd[idx1] ) 983 { 984 if( SCIPisNegative(scip, row1valptr[i]) ) /* since we look at the swapped case, this represents a positive coefficient */ 985 { 986 if( SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_BINARY 987 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_INTEGER 988 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_IMPLINT ) 989 newbnd = SCIPceil(scip, (activity - row1valptr[i] * ubs[idx1]) / (-row1valptr[i])); 990 else 991 newbnd = (activity - row1valptr[i] * ubs[idx1]) / (-row1valptr[i]); 992 993 if( SCIPisGT(scip, newbnd, lbs[idx1]) ) 994 { 995 #ifdef SCIP_DEBUG_BOUNDS 996 SCIPdebugMsg(scip, "%g <= %g <= %s <= %g\n", 997 lbs[idx1], newbnd, SCIPmatrixGetColName(matrix, idx1), ubs[idx1]); 998 #endif 999 lbs[idx1] = newbnd; 1000 (*success) = TRUE; 1001 } 1002 } 1003 else 1004 { 1005 /* since we look at the swapped case, this represents a negative coefficient */ 1006 assert(SCIPisPositive(scip, row1valptr[i])); 1007 if( SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_BINARY 1008 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_INTEGER 1009 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_IMPLINT ) 1010 newbnd = SCIPfloor(scip, (activity - row1valptr[i] * lbs[idx1]) / (-row1valptr[i])); 1011 else 1012 newbnd = (activity - row1valptr[i] * lbs[idx1]) / (-row1valptr[i]); 1013 1014 if( SCIPisLT(scip, newbnd, ubs[idx1]) ) 1015 { 1016 #ifdef SCIP_DEBUG_BOUNDS 1017 SCIPdebugMsg(scip, "%g <= %s <= %g <= %g\n", 1018 lbs[idx1], SCIPmatrixGetColName(matrix, idx1), newbnd, ubs[idx1]); 1019 #endif 1020 ubs[idx1] = newbnd; 1021 (*success) = TRUE; 1022 } 1023 } 1024 } 1025 } 1026 } 1027 /* strengthen bound of the single variable contributing the infinity */ 1028 else 1029 { 1030 assert(mininfs == 1); 1031 for( i = 0; i < row1len; i++ ) 1032 { 1033 idx1 = row1idxptr[i]; 1034 if( cangetbnd[idx1] ) 1035 { 1036 /* since we look at the swapped case, this represents a positive coefficient */ 1037 if( SCIPisNegative(scip, row1valptr[i]) && SCIPisInfinity(scip, ubs[idx1]) ) 1038 { 1039 if( SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_BINARY 1040 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_INTEGER 1041 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_IMPLINT ) 1042 newbnd = SCIPceil(scip, activity / (-row1valptr[i])); 1043 else 1044 newbnd = activity / (-row1valptr[i]); 1045 1046 if( SCIPisGT(scip, newbnd, lbs[idx1]) ) 1047 { 1048 #ifdef SCIP_DEBUG_BOUNDS 1049 SCIPdebugMsg(scip, "%g <= %g <= %s <= %g\n", lbs[idx1], newbnd, SCIPmatrixGetColName(matrix, idx1), ubs[idx1]); 1050 #endif 1051 lbs[idx1] = newbnd; 1052 (*success) = TRUE; 1053 } 1054 } 1055 else if( SCIPisInfinity(scip, -lbs[idx1]) ) 1056 { 1057 /* since we look at the swapped case, this represents a negative coefficient */ 1058 assert(SCIPisPositive(scip, row1valptr[i])); 1059 if( SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_BINARY 1060 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_INTEGER 1061 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_IMPLINT ) 1062 newbnd = SCIPfloor(scip, activity / (-row1valptr[i])); 1063 else 1064 newbnd = activity / (-row1valptr[i]); 1065 1066 if( SCIPisLT(scip, newbnd, ubs[idx1]) ) 1067 { 1068 #ifdef SCIP_DEBUG_BOUNDS 1069 SCIPdebugMsg(scip, "%g <= %s <= %g <= %g\n", 1070 lbs[idx1], SCIPmatrixGetColName(matrix, idx1), newbnd, ubs[idx1]); 1071 #endif 1072 ubs[idx1] = newbnd; 1073 (*success) = TRUE; 1074 } 1075 } 1076 } 1077 } 1078 } 1079 } 1080 } 1081 1082 return SCIP_OKAY; 1083 } 1084 1085 /** create required buffer arrays and apply LP-based bound tightening in both directions */ 1086 static 1087 SCIP_RETCODE applyLPboundTightening( 1088 SCIP* scip, /**< SCIP data structure */ 1089 SCIP_MATRIX* matrix, /**< constraint matrix object */ 1090 int row1, /**< index of first row */ 1091 int row2, /**< index of seond row */ 1092 SCIP_Bool swaprow1, /**< should row1 <= rhs be used in addition to lhs <= row1 */ 1093 SCIP_Bool swaprow2, /**< should row2 <= rhs be used in addition to lhs <= row2 */ 1094 SCIP_Real* lbs, /**< lower variable bounds */ 1095 SCIP_Real* ubs, /**< upper variable bounds */ 1096 SCIP_Bool* success /**< return (success || "found better bounds") */ 1097 ) 1098 { 1099 SCIP_Real* aoriginal; 1100 SCIP_Real* acopy; 1101 SCIP_Real* coriginal; 1102 SCIP_Real* ccopy; 1103 SCIP_Real* newlbsoriginal; 1104 SCIP_Real* newlbscopy; 1105 SCIP_Real* newubsoriginal; 1106 SCIP_Real* newubscopy; 1107 SCIP_Bool* cangetbnd; 1108 SCIP_Bool infeasible; 1109 1110 #ifdef SCIP_DEBUG_2RB 1111 SCIPdebugMsg(scip, "combining rows %d (%s) and %d (%s)\n", 1112 row1, SCIPmatrixGetRowName(matrix, row1), row2, SCIPmatrixGetRowName(matrix, row2)); 1113 #endif 1114 1115 SCIP_CALL( SCIPallocBufferArray(scip, &aoriginal, SCIPmatrixGetNColumns(matrix)) ); 1116 SCIP_CALL( SCIPallocBufferArray(scip, &acopy, SCIPmatrixGetNColumns(matrix)) ); 1117 SCIP_CALL( SCIPallocBufferArray(scip, &coriginal, SCIPmatrixGetNColumns(matrix)) ); 1118 SCIP_CALL( SCIPallocBufferArray(scip, &ccopy, SCIPmatrixGetNColumns(matrix)) ); 1119 SCIP_CALL( SCIPallocBufferArray(scip, &newlbsoriginal, SCIPmatrixGetNColumns(matrix)) ); 1120 SCIP_CALL( SCIPallocBufferArray(scip, &newlbscopy, SCIPmatrixGetNColumns(matrix)) ); 1121 SCIP_CALL( SCIPallocBufferArray(scip, &newubsoriginal, SCIPmatrixGetNColumns(matrix)) ); 1122 SCIP_CALL( SCIPallocBufferArray(scip, &newubscopy, SCIPmatrixGetNColumns(matrix)) ); 1123 SCIP_CALL( SCIPallocBufferArray(scip, &cangetbnd, SCIPmatrixGetNColumns(matrix)) ); 1124 1125 /* Sort matrix rows */ 1126 SCIPsortIntReal(SCIPmatrixGetRowIdxPtr(matrix, row1), SCIPmatrixGetRowValPtr(matrix, row1), 1127 SCIPmatrixGetRowNNonzs(matrix, row1)); 1128 SCIPsortIntReal(SCIPmatrixGetRowIdxPtr(matrix, row2), SCIPmatrixGetRowValPtr(matrix, row2), 1129 SCIPmatrixGetRowNNonzs(matrix, row2)); 1130 1131 /* Use row2 to strengthen row1 */ 1132 infeasible = FALSE; 1133 SCIP_CALL( transformAndSolve(scip, matrix, row1, row2, swaprow1, swaprow2, aoriginal, acopy, 1134 coriginal, ccopy, cangetbnd, lbs, ubs, newlbsoriginal, newlbscopy, 1135 newubsoriginal, newubscopy, success, &infeasible) ); 1136 1137 /* Switch roles and use row1 to strengthen row2 */ 1138 SCIP_CALL( transformAndSolve(scip, matrix, row2, row1, swaprow2, swaprow1, aoriginal, acopy, 1139 coriginal, ccopy, cangetbnd, lbs, ubs, newlbsoriginal, newlbscopy, 1140 newubsoriginal, newubscopy, success, &infeasible) ); 1141 1142 SCIPfreeBufferArray(scip, &cangetbnd); 1143 SCIPfreeBufferArray(scip, &newubscopy); 1144 SCIPfreeBufferArray(scip, &newubsoriginal); 1145 SCIPfreeBufferArray(scip, &newlbscopy); 1146 SCIPfreeBufferArray(scip, &newlbsoriginal); 1147 SCIPfreeBufferArray(scip, &ccopy); 1148 SCIPfreeBufferArray(scip, &coriginal); 1149 SCIPfreeBufferArray(scip, &acopy); 1150 SCIPfreeBufferArray(scip, &aoriginal); 1151 1152 return SCIP_OKAY; 1153 } 1154 1155 /* Find hashes contained in both hashlists, and apply LP-bound 1156 * on their corresponding rows. Both hashlists must be sorted. 1157 */ 1158 static 1159 SCIP_RETCODE processHashlists( 1160 SCIP* scip, /**< SCIP data structure */ 1161 SCIP_PRESOLDATA* presoldata, /**< presolver data structure */ 1162 SCIP_MATRIX* matrix, /**< constraint matrix object */ 1163 int* hashlist1, /**< first list of hashes */ 1164 int* hashlist2, /**< second list of hashes */ 1165 int lenhashlist1, /**< length of first hashlist */ 1166 int lenhashlist2, /**< length of second hashlist */ 1167 int* rowidxlist1, /**< list of row indices corresponding to hashes in hashlist1 */ 1168 int* rowidxlist2, /**< list of row indices corresponding to hashes in hashlist2 */ 1169 SCIP_Real* newlbs, /**< lower variable bounds, new bounds will be written here */ 1170 SCIP_Real* newubs /**< upper variable bounds, new bound will be written here */ 1171 ) 1172 { 1173 int i; 1174 int j; 1175 int block1start; 1176 int block1end; 1177 int block2start; 1178 int block2end; 1179 SCIP_Longint maxcombines; 1180 SCIP_Bool finished; 1181 SCIP_Bool success; 1182 SCIP_Bool swaprow1; 1183 SCIP_Bool swaprow2; 1184 int ncombines; 1185 int combinefails; 1186 int retrievefails; 1187 ROWPAIR rowpair; 1188 SCIP_HASHSET* pairhashset; 1189 1190 SCIP_CALL( SCIPhashsetCreate(&pairhashset, SCIPblkmem(scip), 1) ); 1191 1192 finished = FALSE; 1193 block1start = 0; 1194 block1end = 0; 1195 block2start = 0; 1196 block2end = 0; 1197 maxcombines = presoldata->maxpairfac == -1 ? SCIP_LONGINT_MAX : (((SCIP_Longint)SCIPmatrixGetNRows(matrix)) * presoldata->maxpairfac); 1198 1199 ncombines = 0; 1200 combinefails = 0; 1201 retrievefails = 0; 1202 findNextBlock(hashlist1, lenhashlist1, &block1start, &block1end); 1203 findNextBlock(hashlist2, lenhashlist2, &block2start, &block2end); 1204 while( !finished ) 1205 { 1206 if( hashlist1[block1start] == hashlist2[block2start] ) 1207 { 1208 for( i = block1start; i < block1end; i++ ) 1209 { 1210 for( j = block2start; j < block2end; j++ ) 1211 { 1212 if( rowidxlist1[i] != rowidxlist2[j] ) 1213 { 1214 rowpair.row1idx = MIN(rowidxlist1[i], rowidxlist2[j]); 1215 rowpair.row2idx = MAX(rowidxlist1[i], rowidxlist2[j]); 1216 if( !SCIPhashsetExists(pairhashset, encodeRowPair(&rowpair)) ) 1217 { 1218 assert(!SCIPisInfinity(scip, -SCIPmatrixGetRowLhs(matrix, rowpair.row1idx))); 1219 assert(!SCIPisInfinity(scip, -SCIPmatrixGetRowLhs(matrix, rowpair.row2idx))); 1220 1221 success = FALSE; 1222 1223 /* apply lp-based bound tightening */ 1224 swaprow1 = !SCIPisInfinity(scip, SCIPmatrixGetRowRhs(matrix, rowpair.row1idx)); 1225 swaprow2 = !SCIPisInfinity(scip, SCIPmatrixGetRowRhs(matrix, rowpair.row2idx)); 1226 1227 SCIP_CALL( applyLPboundTightening(scip, matrix, rowpair.row1idx, rowpair.row2idx, 1228 swaprow1, swaprow2, newlbs, newubs, &success) ); 1229 1230 if( success ) 1231 combinefails = 0; 1232 else 1233 combinefails++; 1234 1235 SCIP_CALL( SCIPhashsetInsert(pairhashset, SCIPblkmem(scip), encodeRowPair(&rowpair)) ); 1236 ncombines++; 1237 1238 if( ncombines >= maxcombines || combinefails >= presoldata->maxcombinefails ) 1239 finished = TRUE; 1240 1241 retrievefails = 0; 1242 } 1243 else if( retrievefails < presoldata->maxretrievefails ) 1244 retrievefails++; 1245 else 1246 finished = TRUE; 1247 } 1248 /* check if SCIP ran into a time limit already */ 1249 if( j % 10 == 0 && SCIPisStopped(scip) ) 1250 finished = TRUE; 1251 if( finished ) 1252 break; 1253 } 1254 /* check if SCIP ran into a time limit already */ 1255 if( SCIPisStopped(scip) ) 1256 finished = TRUE; 1257 if( finished ) 1258 break; 1259 } 1260 1261 if( block1end < lenhashlist1 && block2end < lenhashlist2 ) 1262 { 1263 findNextBlock(hashlist1, lenhashlist1, &block1start, &block1end); 1264 findNextBlock(hashlist2, lenhashlist2, &block2start, &block2end); 1265 } 1266 else 1267 finished = TRUE; 1268 } 1269 else if( hashlist1[block1start] < hashlist2[block2start] && block1end < lenhashlist1 ) 1270 findNextBlock(hashlist1, lenhashlist1, &block1start, &block1end); 1271 else if( hashlist1[block1start] > hashlist2[block2start] && block2end < lenhashlist2 ) 1272 findNextBlock(hashlist2, lenhashlist2, &block2start, &block2end); 1273 else 1274 finished = TRUE; 1275 } 1276 1277 SCIPhashsetFree(&pairhashset, SCIPblkmem(scip)); 1278 1279 return SCIP_OKAY; 1280 } 1281 1282 1283 /* 1284 * Callback methods of presolver 1285 */ 1286 1287 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 1288 static 1289 SCIP_DECL_PRESOLCOPY(presolCopyTworowbnd) 1290 { 1291 SCIP_PRESOLDATA* presoldata; 1292 1293 assert(scip != NULL); 1294 assert(presol != NULL); 1295 assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0); 1296 1297 /* call inclusion method of presolver if copying is enabled */ 1298 presoldata = SCIPpresolGetData(presol); 1299 assert(presoldata != NULL); 1300 if( presoldata->enablecopy ) 1301 { 1302 SCIP_CALL( SCIPincludePresolTworowbnd(scip) ); 1303 } 1304 1305 return SCIP_OKAY; 1306 } 1307 1308 /** destructor of presolver to free user data (called when SCIP is exiting) */ 1309 static 1310 SCIP_DECL_PRESOLFREE(presolFreeTworowbnd) 1311 { /*lint --e{715}*/ 1312 SCIP_PRESOLDATA* presoldata; 1313 1314 /* free presolver data */ 1315 presoldata = SCIPpresolGetData(presol); 1316 assert(presoldata != NULL); 1317 1318 SCIPfreeBlockMemory(scip, &presoldata); 1319 SCIPpresolSetData(presol, NULL); 1320 1321 return SCIP_OKAY; 1322 } 1323 1324 /** initialization method of presolver (called after problem was transformed) */ 1325 static 1326 SCIP_DECL_PRESOLINIT(presolInitTworowbnd) 1327 { 1328 SCIP_PRESOLDATA* presoldata; 1329 1330 presoldata = SCIPpresolGetData(presol); 1331 presoldata->nchgbnds = 0; 1332 presoldata->nuselessruns = 0; 1333 1334 return SCIP_OKAY; 1335 } 1336 1337 /** execution method of presolver */ 1338 static 1339 SCIP_DECL_PRESOLEXEC(presolExecTworowbnd) 1340 { /*lint --e{715}*/ 1341 SCIP_MATRIX* matrix; 1342 SCIP_Bool initialized; 1343 SCIP_Bool complete; 1344 SCIP_Bool infeasible; 1345 SCIP_PRESOLDATA* presoldata; 1346 int oldnchgbds; 1347 int oldnfixedvars; 1348 int nrows; 1349 int ncols; 1350 SCIP_Real* oldlbs; 1351 SCIP_Real* oldubs; 1352 SCIP_Real* newlbs; 1353 SCIP_Real* newubs; 1354 int* rowidxptr; 1355 SCIP_Real* rowvalptr; 1356 SCIP_VAR* var; 1357 1358 SCIP_Longint maxhashes; 1359 1360 int maxlen; 1361 int pospp; 1362 int listsizepp; 1363 int posmm; 1364 int listsizemm; 1365 int pospm; 1366 int listsizepm; 1367 int posmp; 1368 int listsizemp; 1369 1370 int* hashlistpp; 1371 int* hashlistmm; 1372 int* hashlistpm; 1373 int* hashlistmp; 1374 1375 int* rowidxlistpp; 1376 int* rowidxlistmm; 1377 int* rowidxlistpm; 1378 int* rowidxlistmp; 1379 1380 SCIP_Bool finiterhs; 1381 1382 int i; 1383 int j; 1384 int k; 1385 1386 assert(result != NULL); 1387 *result = SCIP_DIDNOTRUN; 1388 infeasible = FALSE; 1389 1390 if( SCIPisStopped(scip) ) 1391 return SCIP_OKAY; 1392 1393 presoldata = SCIPpresolGetData(presol); 1394 assert(presoldata != NULL); 1395 1396 if( presoldata->nuselessruns >= 5 ) 1397 return SCIP_OKAY; 1398 1399 *result = SCIP_DIDNOTFIND; 1400 1401 matrix = NULL; 1402 SCIP_CALL( SCIPmatrixCreate(scip, &matrix, TRUE, &initialized, &complete, &infeasible, 1403 naddconss, ndelconss, nchgcoefs, nchgbds, nfixedvars) ); 1404 1405 /* if infeasibility was detected during matrix creation, return here */ 1406 if( infeasible ) 1407 { 1408 if( initialized ) 1409 SCIPmatrixFree(scip, &matrix); 1410 1411 *result = SCIP_CUTOFF; 1412 return SCIP_OKAY; 1413 } 1414 1415 if( !initialized ) 1416 return SCIP_OKAY; 1417 1418 nrows = SCIPmatrixGetNRows(matrix); 1419 ncols = SCIPmatrixGetNColumns(matrix); 1420 1421 if( nrows <= 1 ) 1422 { 1423 SCIPmatrixFree(scip, &matrix); 1424 return SCIP_OKAY; 1425 } 1426 1427 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &hashlistpp, nrows) ); 1428 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &hashlistmm, nrows) ); 1429 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &hashlistpm, nrows) ); 1430 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &hashlistmp, nrows) ); 1431 1432 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &rowidxlistpp, nrows) ); 1433 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &rowidxlistmm, nrows) ); 1434 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &rowidxlistpm, nrows) ); 1435 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &rowidxlistmp, nrows) ); 1436 1437 pospp = 0; 1438 posmm = 0; 1439 pospm = 0; 1440 posmp = 0; 1441 listsizepp = nrows; 1442 listsizemm = nrows; 1443 listsizepm = nrows; 1444 listsizemp = nrows; 1445 maxhashes = presoldata->maxhashfac == -1 ? SCIP_LONGINT_MAX : (((SCIP_Longint)nrows) * presoldata->maxhashfac); 1446 1447 /* skim through the problem and create hashlists for combination candidates */ 1448 for( i = 0; i < nrows; i++) 1449 { 1450 if( ((SCIP_Longint)pospp) + posmm + pospm + posmp > maxhashes ) 1451 break; 1452 1453 rowvalptr = SCIPmatrixGetRowValPtr(matrix, i); 1454 rowidxptr = SCIPmatrixGetRowIdxPtr(matrix, i); 1455 finiterhs = !SCIPisInfinity(scip, SCIPmatrixGetRowRhs(matrix, i)); 1456 maxlen = MIN(presoldata->maxconsiderednonzeros, SCIPmatrixGetRowNNonzs(matrix, i)); /*lint !e666*/ 1457 for( j = 0; j < maxlen; j++) 1458 { 1459 for( k = j+1; k < maxlen; k++) 1460 { 1461 if( SCIPisPositive(scip, rowvalptr[j]) ) 1462 { 1463 if(SCIPisPositive(scip, rowvalptr[k]) ) 1464 { 1465 SCIP_CALL( addEntry(scip, &pospp, &listsizepp, &hashlistpp, &rowidxlistpp, 1466 hashIndexPair(rowidxptr[j],rowidxptr[k]), i) ); 1467 if( finiterhs ) 1468 SCIP_CALL( addEntry(scip, &posmm, &listsizemm, &hashlistmm, &rowidxlistmm, 1469 hashIndexPair(rowidxptr[j],rowidxptr[k]), i) ); 1470 } 1471 else 1472 { 1473 SCIP_CALL( addEntry(scip, &pospm, &listsizepm, &hashlistpm, &rowidxlistpm, 1474 hashIndexPair(rowidxptr[j],rowidxptr[k]), i) ); 1475 if( finiterhs ) 1476 SCIP_CALL( addEntry(scip, &posmp, &listsizemp, &hashlistmp, &rowidxlistmp, 1477 hashIndexPair(rowidxptr[j],rowidxptr[k]), i) ); 1478 } 1479 } 1480 else 1481 { 1482 if(SCIPisPositive(scip, rowvalptr[k]) ) 1483 { 1484 SCIP_CALL( addEntry(scip, &posmp, &listsizemp, &hashlistmp, &rowidxlistmp, 1485 hashIndexPair(rowidxptr[j],rowidxptr[k]), i) ); 1486 if( finiterhs ) 1487 SCIP_CALL( addEntry(scip, &pospm, &listsizepm, &hashlistpm, &rowidxlistpm, 1488 hashIndexPair(rowidxptr[j],rowidxptr[k]), i) ); 1489 } 1490 else 1491 { 1492 SCIP_CALL( addEntry(scip, &posmm, &listsizemm, &hashlistmm, &rowidxlistmm, 1493 hashIndexPair(rowidxptr[j],rowidxptr[k]), i) ); 1494 if( finiterhs ) 1495 SCIP_CALL( addEntry(scip, &pospp, &listsizepp, &hashlistpp, &rowidxlistpp, 1496 hashIndexPair(rowidxptr[j],rowidxptr[k]), i) ); 1497 } 1498 } 1499 } 1500 } 1501 } 1502 1503 #ifdef SCIP_DEBUG_HASHING 1504 SCIPdebugMsg(scip, "pp\n"); 1505 for( i = 0; i < pospp; i++) 1506 SCIPdebugMsg(scip, "%d: hash = %d, rowidx = %d\n", i, hashlistpp[i], rowidxlistpp[i]); 1507 SCIPdebugMsg(scip, "mm\n"); 1508 for( i = 0; i < posmm; i++) 1509 SCIPdebugMsg(scip, "%d: hash = %d, rowidx = %d\n", i, hashlistmm[i], rowidxlistmm[i]); 1510 SCIPdebugMsg(scip, "pm\n"); 1511 for( i = 0; i < pospm; i++) 1512 SCIPdebugMsg(scip, "%d: hash = %d, rowidx = %d\n", i, hashlistpm[i], rowidxlistpm[i]); 1513 SCIPdebugMsg(scip, "mp\n"); 1514 for( i = 0; i < posmp; i++) 1515 SCIPdebugMsg(scip, "%d: hash = %d, rowidx = %d\n", i, hashlistmp[i], rowidxlistmp[i]); 1516 #endif 1517 SCIPdebugMsg(scip, "hashlist sizes: pp %d, mm %d, pm %d, mp %d \n", pospp, posmm, pospm, posmp); 1518 1519 SCIPsortIntInt(hashlistpp, rowidxlistpp, pospp); 1520 SCIPsortIntInt(hashlistmm, rowidxlistmm, posmm); 1521 SCIPsortIntInt(hashlistpm, rowidxlistpm, pospm); 1522 SCIPsortIntInt(hashlistmp, rowidxlistmp, posmp); 1523 1524 #ifdef SCIP_DEBUG_HASHING 1525 SCIPdebugMsg(scip, "sorted pp\n"); 1526 for( i = 0; i < pospp; i++) 1527 SCIPdebugMsg(scip, "%d: hash = %d, rowidx = %d\n", i, hashlistpp[i], rowidxlistpp[i]); 1528 SCIPdebugMsg(scip, "sorted mm\n"); 1529 for( i = 0; i < posmm; i++) 1530 SCIPdebugMsg(scip, "%d: hash = %d, rowidx = %d\n", i, hashlistmm[i], rowidxlistmm[i]); 1531 SCIPdebugMsg(scip, "sorted pm\n"); 1532 for( i = 0; i < pospm; i++) 1533 SCIPdebugMsg(scip, "%d: hash = %d, rowidx = %d\n", i, hashlistpm[i], rowidxlistpm[i]); 1534 SCIPdebugMsg(scip, "sorted mp\n"); 1535 for( i = 0; i < posmp; i++) 1536 SCIPdebugMsg(scip, "%d: hash = %d, rowidx = %d\n", i, hashlistmp[i], rowidxlistmp[i]); 1537 #endif 1538 1539 SCIP_CALL( SCIPallocBufferArray(scip, &oldlbs, ncols) ); 1540 SCIP_CALL( SCIPallocBufferArray(scip, &oldubs, ncols) ); 1541 SCIP_CALL( SCIPallocBufferArray(scip, &newlbs, ncols) ); 1542 SCIP_CALL( SCIPallocBufferArray(scip, &newubs, ncols) ); 1543 1544 for( i = 0; i < SCIPmatrixGetNColumns(matrix); i++ ) 1545 { 1546 var = SCIPmatrixGetVar(matrix, i); 1547 oldlbs[i] = SCIPvarGetLbLocal(var); 1548 oldubs[i] = SCIPvarGetUbLocal(var); 1549 newlbs[i] = oldlbs[i]; 1550 newubs[i] = oldubs[i]; 1551 } 1552 1553 /* Process pp and mm hashlists */ 1554 if( pospp > 0 && posmm > 0 ) 1555 { 1556 SCIPdebugMsg(scip, "processing pp and mm\n"); 1557 SCIP_CALL( processHashlists(scip, presoldata, matrix, hashlistpp, hashlistmm, pospp, posmm, rowidxlistpp, 1558 rowidxlistmm, newlbs, newubs) ); 1559 } 1560 1561 /* Process pm and mp hashlists */ 1562 if( pospm > 0 && posmp > 0 ) 1563 { 1564 SCIPdebugMsg(scip, "processing pm and mp\n"); 1565 SCIP_CALL( processHashlists(scip, presoldata, matrix, hashlistpm, hashlistmp, pospm, posmp, rowidxlistpm, 1566 rowidxlistmp, newlbs, newubs) ); 1567 } 1568 1569 /* Apply reductions */ 1570 oldnchgbds = *nchgbds; 1571 oldnfixedvars = *nfixedvars; 1572 for( i = 0; i < SCIPmatrixGetNColumns(matrix); i++ ) 1573 { 1574 SCIP_Bool bndwastightened; 1575 SCIP_Bool fixed; 1576 1577 var = SCIPmatrixGetVar(matrix, i); 1578 1579 assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT 1580 || (SCIPisEQ(scip, newlbs[i], SCIPceil(scip, newlbs[i])) && (SCIPisEQ(scip, newubs[i], SCIPfloor(scip, newubs[i]))))); 1581 1582 if( SCIPisEQ(scip, newlbs[i], newubs[i]) ) 1583 { 1584 SCIP_CALL( SCIPfixVar(scip, var, newlbs[i], &infeasible, &fixed) ); 1585 1586 if( infeasible ) 1587 { 1588 SCIPdebugMessage(" -> infeasible fixing of variable %s\n", SCIPvarGetName(var)); 1589 break; 1590 } 1591 1592 if( fixed ) 1593 { 1594 SCIPdebugMessage("variable %s fixed to %g\n", SCIPvarGetName(var), newlbs[i]); 1595 (*nfixedvars)++; 1596 } 1597 } 1598 1599 if( SCIPisLT(scip, oldlbs[i], newlbs[i]) ) 1600 { 1601 SCIP_CALL( SCIPtightenVarLb(scip, var, newlbs[i], FALSE, &infeasible, &bndwastightened) ); 1602 1603 if( infeasible ) 1604 { 1605 SCIPdebugMessage(" -> infeasible lower bound tightening: %s >= %g\n", SCIPvarGetName(var), newlbs[i]); 1606 break; 1607 } 1608 1609 if( bndwastightened ) 1610 { 1611 SCIPdebugMessage("lower bound of %s changed from %g to %g\n", SCIPvarGetName(var), oldlbs[i], newlbs[i]); 1612 (*nchgbds)++; 1613 } 1614 } 1615 1616 if( SCIPisGT(scip, oldubs[i], newubs[i]) ) 1617 { 1618 SCIP_CALL( SCIPtightenVarUb(scip, var, newubs[i], FALSE, &infeasible, &bndwastightened) ); 1619 1620 if( infeasible ) 1621 { 1622 SCIPdebugMessage(" -> infeasible upper bound tightening: %s <= %g\n", SCIPvarGetName(var), newubs[i]); 1623 break; 1624 } 1625 1626 if( bndwastightened ) 1627 { 1628 SCIPdebugMessage("upper bound of %s changed from %g to %g\n", SCIPvarGetName(var), oldubs[i], newubs[i]); 1629 (*nchgbds)++; 1630 } 1631 } 1632 } 1633 1634 /* set result */ 1635 if( *nchgbds > oldnchgbds || *nfixedvars > oldnfixedvars ) 1636 { 1637 *result = SCIP_SUCCESS; 1638 presoldata->nuselessruns = 0; 1639 } 1640 else if( infeasible ) 1641 { 1642 *result = SCIP_CUTOFF; 1643 } 1644 else 1645 { 1646 presoldata->nuselessruns++; 1647 } 1648 1649 SCIPfreeBufferArray(scip, &newubs); 1650 SCIPfreeBufferArray(scip, &newlbs); 1651 SCIPfreeBufferArray(scip, &oldubs); 1652 SCIPfreeBufferArray(scip, &oldlbs); 1653 SCIPfreeBlockMemoryArray(scip, &rowidxlistmp, listsizemp); 1654 SCIPfreeBlockMemoryArray(scip, &rowidxlistpm, listsizepm); 1655 SCIPfreeBlockMemoryArray(scip, &rowidxlistmm, listsizemm); 1656 SCIPfreeBlockMemoryArray(scip, &rowidxlistpp, listsizepp); 1657 SCIPfreeBlockMemoryArray(scip, &hashlistmp, listsizemp); 1658 SCIPfreeBlockMemoryArray(scip, &hashlistpm, listsizepm); 1659 SCIPfreeBlockMemoryArray(scip, &hashlistmm, listsizemm); 1660 SCIPfreeBlockMemoryArray(scip, &hashlistpp, listsizepp); 1661 1662 SCIPmatrixFree(scip, &matrix); 1663 1664 return SCIP_OKAY; 1665 } 1666 1667 1668 /* 1669 * presolver specific interface methods 1670 */ 1671 1672 /** creates the tworowbndb presolver and includes it in SCIP */ 1673 SCIP_RETCODE SCIPincludePresolTworowbnd( 1674 SCIP* scip /**< SCIP data structure */ 1675 ) 1676 { 1677 SCIP_PRESOLDATA* presoldata; 1678 SCIP_PRESOL* presol; 1679 1680 /* create tworowbnd presolver data */ 1681 SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) ); 1682 1683 presol = NULL; 1684 1685 /* include presolver */ 1686 SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS, PRESOL_TIMING, 1687 presolExecTworowbnd, 1688 presoldata) ); 1689 1690 assert(presol != NULL); 1691 1692 SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyTworowbnd) ); 1693 SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeTworowbnd) ); 1694 SCIP_CALL( SCIPsetPresolInit(scip, presol, presolInitTworowbnd) ); 1695 1696 /* add tworowbnd presolver parameters */ 1697 SCIP_CALL( SCIPaddBoolParam(scip, 1698 "presolving/tworowbnd/enablecopy", 1699 "should tworowbnd presolver be copied to sub-SCIPs?", 1700 &presoldata->enablecopy, TRUE, DEFAULT_ENABLECOPY, NULL, NULL) ); 1701 SCIP_CALL( SCIPaddIntParam(scip, 1702 "presolving/tworowbnd/maxconsiderednonzeros", 1703 "maximal number of considered non-zeros within one row (-1: no limit)", 1704 &presoldata->maxconsiderednonzeros, FALSE, DEFAULT_MAXCONSIDEREDNONZEROS, -1, INT_MAX, NULL, NULL) ); 1705 SCIP_CALL( SCIPaddIntParam(scip, 1706 "presolving/tworowbnd/maxretrievefails", 1707 "maximal number of consecutive useless hashtable retrieves", 1708 &presoldata->maxretrievefails, FALSE, DEFAULT_MAXRETRIEVEFAILS, -1, INT_MAX, NULL, NULL) ); 1709 SCIP_CALL( SCIPaddIntParam(scip, 1710 "presolving/tworowbnd/maxcombinefails", 1711 "maximal number of consecutive useless row combines", 1712 &presoldata->maxcombinefails, FALSE, DEFAULT_MAXCOMBINEFAILS, -1, INT_MAX, NULL, NULL) ); 1713 SCIP_CALL( SCIPaddIntParam(scip, 1714 "presolving/tworowbnd/maxhashfac", 1715 "Maximum number of hashlist entries as multiple of number of rows in the problem (-1: no limit)", 1716 &presoldata->maxhashfac, FALSE, DEFAULT_MAXHASHFAC, -1, INT_MAX, NULL, NULL) ); 1717 SCIP_CALL( SCIPaddIntParam(scip, 1718 "presolving/tworowbnd/maxpairfac", 1719 "Maximum number of processed row pairs as multiple of the number of rows in the problem (-1: no limit)", 1720 &presoldata->maxpairfac, FALSE, DEFAULT_MAXPAIRFAC, -1, INT_MAX, NULL, NULL) ); 1721 1722 return SCIP_OKAY; 1723 } 1724