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_domcol.c 26 * @ingroup DEFPLUGINS_PRESOL 27 * @brief dominated column presolver 28 * @author Dieter Weninger 29 * @author Gerald Gamrath 30 * 31 * This presolver looks for dominance relations between variable pairs. 32 * From a dominance relation and certain bound/clique-constellations 33 * variable fixings mostly at the lower bound of the dominated variable can be derived. 34 * Additionally it is possible to improve bounds by predictive bound strengthening. 35 * 36 * @todo Also run on general CIPs, if the number of locks of the investigated variables comes only from (upgraded) 37 * linear constraints. 38 * 39 * @todo Instead of choosing variables for comparison out of one row, we should try to use 'hashvalues' for columns that 40 * indicate in which constraint type (<=, >=, or ranged row / ==) they are existing. Then sort the variables (and 41 * corresponding data) after the ranged row/equation hashvalue and only try to derive dominance on variables with 42 * the same hashvalue on ranged row/equation and fitting hashvalues for the other constraint types. 43 * @todo run on incomplete matrices; in order to do so, check at the time when dominance is detected that the locks are 44 * consistent; probably, it is sufficient to check one lock direction for each of the two variables 45 * 46 */ 47 48 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 49 50 #include "blockmemshell/memory.h" 51 #include "scip/presol_domcol.h" 52 #include "scip/pub_matrix.h" 53 #include "scip/pub_message.h" 54 #include "scip/pub_misc_sort.h" 55 #include "scip/pub_presol.h" 56 #include "scip/pub_var.h" 57 #include "scip/scip_general.h" 58 #include "scip/scip_mem.h" 59 #include "scip/scip_message.h" 60 #include "scip/scip_nlp.h" 61 #include "scip/scip_numerics.h" 62 #include "scip/scip_param.h" 63 #include "scip/scip_presol.h" 64 #include "scip/scip_pricer.h" 65 #include "scip/scip_prob.h" 66 #include "scip/scip_probing.h" 67 #include "scip/scip_var.h" 68 #include <string.h> 69 70 #define PRESOL_NAME "domcol" 71 #define PRESOL_DESC "dominated column presolver" 72 #define PRESOL_PRIORITY -1000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */ 73 #define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */ 74 #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ 75 76 #define DEFAULT_NUMMINPAIRS 1024 /**< minimal number of pair comparisons */ 77 #define DEFAULT_NUMMAXPAIRS 1048576 /**< maximal number of pair comparisons */ 78 79 #define DEFAULT_PREDBNDSTR FALSE /**< should predictive bound strengthening be applied? */ 80 #define DEFAULT_CONTINUOUS_RED TRUE /**< should reductions for continuous variables be carried out? */ 81 82 83 84 /* 85 * Data structures 86 */ 87 88 /** control parameters */ 89 struct SCIP_PresolData 90 { 91 int numminpairs; /**< minimal number of pair comparisons */ 92 int nummaxpairs; /**< maximal number of pair comparisons */ 93 int numcurrentpairs; /**< current number of pair comparisons */ 94 SCIP_Bool predbndstr; /**< flag indicating if predictive bound strengthening should be applied */ 95 SCIP_Bool continuousred; /**< flag indicating if reductions for continuous variables should be performed */ 96 }; 97 98 /** type of fixing direction */ 99 enum Fixingdirection 100 { 101 FIXATLB = -1, /**< fix variable at lower bound */ 102 NOFIX = 0, /**< do not fix variable */ 103 FIXATUB = 1 /**< fix variable at upper bound */ 104 }; 105 typedef enum Fixingdirection FIXINGDIRECTION; 106 107 108 /* 109 * Local methods 110 */ 111 #ifdef SCIP_DEBUG 112 /** print a row from the constraint matrix */ 113 static 114 void printRow( 115 SCIP* scip, /**< SCIP main data structure */ 116 SCIP_MATRIX* matrix, /**< matrix containing the constraints */ 117 int row /**< row index for printing */ 118 ) 119 { 120 int* rowpnt; 121 int* rowend; 122 int c; 123 SCIP_Real val; 124 SCIP_Real* valpnt; 125 char relation; 126 SCIP_VAR* var; 127 128 relation='-'; 129 if( !SCIPmatrixIsRowRhsInfinity(matrix, row) && 130 SCIPisEQ(scip, SCIPmatrixGetRowLhs(matrix, row), SCIPmatrixGetRowRhs(matrix, row)) ) 131 { 132 relation='e'; 133 } 134 else if( !SCIPmatrixIsRowRhsInfinity(matrix, row) && 135 !SCIPisEQ(scip, SCIPmatrixGetRowLhs(matrix, row), SCIPmatrixGetRowRhs(matrix, row)) ) 136 { 137 relation='r'; 138 } 139 else 140 { 141 relation='g'; 142 } 143 144 rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row); 145 rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row); 146 valpnt = SCIPmatrixGetRowValPtr(matrix, row); 147 148 SCIPdebugMsgPrint(scip, "\n(L:%g) [%c] %g <=", 149 (SCIPmatrixGetRowNMinActPosInf(matrix, row) + SCIPmatrixGetRowNMinActNegInf(matrix,row) > 0) ? 150 -SCIPinfinity(scip) : 151 SCIPmatrixGetRowMinActivity(matrix, row), relation, SCIPmatrixGetRowLhs(matrix, row)); 152 for(; (rowpnt < rowend); rowpnt++, valpnt++) 153 { 154 c = *rowpnt; 155 val = *valpnt; 156 var = SCIPmatrixGetVar(matrix, c); 157 SCIPdebugMsgPrint(scip, " %g{%s[idx:%d][bnd:%g,%g]}", 158 val, SCIPvarGetName(var), c, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var)); 159 } 160 SCIPdebugMsgPrint(scip, " <= %g (U:%g)", (SCIPmatrixGetRowNMaxActPosInf(matrix, row) + SCIPmatrixGetRowNMaxActNegInf(matrix, row) > 0) ? 161 SCIPinfinity(scip) : 162 SCIPmatrixGetRowRhs(matrix, row), SCIPmatrixGetRowMaxActivity(matrix , row)); 163 } 164 165 /** print all rows from the constraint matrix containing a variable */ 166 static 167 SCIP_RETCODE printRowsOfCol( 168 SCIP* scip, /**< SCIP main data structure */ 169 SCIP_MATRIX* matrix, /**< matrix containing the constraints */ 170 int col /**< column index for printing */ 171 ) 172 { 173 int numrows; 174 int* rows; 175 int i; 176 int* colpnt; 177 int* colend; 178 179 numrows = SCIPmatrixGetColNNonzs(matrix, col); 180 181 SCIP_CALL( SCIPallocBufferArray(scip, &rows, numrows) ); 182 183 colpnt = SCIPmatrixGetColIdxPtr(matrix, col); 184 colend = colpnt + SCIPmatrixGetColNNonzs(matrix, col); 185 for( i = 0; (colpnt < colend); colpnt++, i++ ) 186 { 187 rows[i] = *colpnt; 188 } 189 190 SCIPdebugMsgPrint(scip, "\n-------"); 191 SCIPdebugMsgPrint(scip, "\ncol %d number rows: %d",col,numrows); 192 for( i = 0; i < numrows; i++ ) 193 { 194 printRow(scip, matrix, rows[i]); 195 } 196 SCIPdebugMsgPrint(scip, "\n-------"); 197 198 SCIPfreeBufferArray(scip, &rows); 199 200 return SCIP_OKAY; 201 } 202 203 /** print information about a dominance relation */ 204 static 205 SCIP_RETCODE printDomRelInfo( 206 SCIP* scip, /**< SCIP main data structure */ 207 SCIP_MATRIX* matrix, /**< matrix containing the constraints */ 208 SCIP_VAR* dominatingvar, /**< dominating variable */ 209 int dominatingidx, /**< index of dominating variable */ 210 SCIP_VAR* dominatedvar, /**< dominated variable */ 211 int dominatedidx, /**< index of dominated variable */ 212 SCIP_Real dominatingub, /**< predicted upper bound of dominating variable */ 213 SCIP_Real dominatingwclb /**< worst case lower bound of dominating variable */ 214 ) 215 { 216 char type; 217 218 assert(SCIPvarGetType(dominatingvar)==SCIPvarGetType(dominatedvar)); 219 220 switch(SCIPvarGetType(dominatingvar)) 221 { 222 case SCIP_VARTYPE_CONTINUOUS: 223 type='C'; 224 break; 225 case SCIP_VARTYPE_BINARY: 226 type='B'; 227 break; 228 case SCIP_VARTYPE_INTEGER: 229 case SCIP_VARTYPE_IMPLINT: 230 type='I'; 231 break; 232 default: 233 SCIPerrorMessage("unknown variable type\n"); 234 SCIPABORT(); 235 return SCIP_INVALIDDATA; /*lint !e527*/ 236 } 237 238 SCIPdebugMsgPrint(scip, "\n\n### [%c], obj:%g->%g,\t%s[idx:%d](nrows:%d)->%s[idx:%d](nrows:%d)\twclb=%g, ub'=%g, ub=%g", 239 type, SCIPvarGetObj(dominatingvar), SCIPvarGetObj(dominatedvar), 240 SCIPvarGetName(dominatingvar), dominatingidx, SCIPmatrixGetColNNonzs(matrix, dominatingidx), 241 SCIPvarGetName(dominatedvar), dominatedidx, SCIPmatrixGetColNNonzs(matrix, dominatedidx), 242 dominatingwclb, dominatingub, SCIPvarGetUbGlobal(dominatingvar)); 243 244 SCIP_CALL( printRowsOfCol(scip, matrix, dominatingidx) ); 245 246 return SCIP_OKAY; 247 } 248 #endif 249 250 251 /** get minimum/maximum residual activity for the specified variable and with another variable set to its upper bound */ 252 static 253 void getActivityResidualsUpperBound( 254 SCIP* scip, 255 SCIP_MATRIX* matrix, 256 int row, 257 int col, 258 SCIP_Real coef, 259 int upperboundcol, 260 SCIP_Real upperboundcoef, 261 SCIP_Real* minresactivity, 262 SCIP_Real* maxresactivity, 263 SCIP_Bool* success 264 ) 265 { 266 SCIP_VAR* var; 267 SCIP_VAR* upperboundvar; 268 SCIP_Real lb; 269 SCIP_Real ub; 270 SCIP_Real lbupperboundvar; 271 SCIP_Real ubupperboundvar; 272 SCIP_Real tmpmaxact; 273 SCIP_Real tmpminact; 274 int maxactinf; 275 int minactinf; 276 277 assert(scip != NULL); 278 assert(matrix != NULL); 279 assert(row < SCIPmatrixGetNRows(matrix)); 280 assert(minresactivity != NULL); 281 assert(maxresactivity != NULL); 282 283 var = SCIPmatrixGetVar(matrix, col); 284 upperboundvar = SCIPmatrixGetVar(matrix, upperboundcol); 285 assert(var != NULL); 286 assert(upperboundvar != NULL); 287 288 lb = SCIPvarGetLbGlobal(var); 289 ub = SCIPvarGetUbGlobal(var); 290 291 maxactinf = SCIPmatrixGetRowNMaxActPosInf(matrix, row) + SCIPmatrixGetRowNMaxActNegInf(matrix, row); 292 minactinf = SCIPmatrixGetRowNMinActPosInf(matrix, row) + SCIPmatrixGetRowNMinActNegInf(matrix, row); 293 294 assert(!SCIPisInfinity(scip, lb)); 295 assert(!SCIPisInfinity(scip, -ub)); 296 297 lbupperboundvar = SCIPvarGetLbGlobal(upperboundvar); 298 ubupperboundvar = SCIPvarGetUbGlobal(upperboundvar); 299 300 assert(!SCIPisInfinity(scip, lbupperboundvar)); 301 assert(!SCIPisInfinity(scip, -ubupperboundvar)); 302 303 tmpminact = SCIPmatrixGetRowMinActivity(matrix, row); 304 tmpmaxact = SCIPmatrixGetRowMaxActivity(matrix, row); 305 306 /* first, adjust min and max activity such that upperboundvar is always set to its upper bound */ 307 308 /* abort if the upper bound is infty */ 309 if( SCIPisInfinity(scip, ubupperboundvar) ) 310 { 311 *success = FALSE; 312 return; 313 } 314 else 315 { 316 /* coef > 0 --> the lower bound is used for the minactivity --> update the minactivity */ 317 if( upperboundcoef > 0.0 ) 318 { 319 if( SCIPisInfinity(scip, -lbupperboundvar) ) 320 { 321 assert(minactinf > 0); 322 minactinf--; 323 tmpminact += (upperboundcoef * ubupperboundvar); 324 } 325 else 326 { 327 tmpminact = tmpminact - (upperboundcoef * lbupperboundvar) + (upperboundcoef * ubupperboundvar); 328 } 329 } 330 /* coef < 0 --> the lower bound is used for the maxactivity --> update the maxactivity */ 331 else 332 { 333 if( SCIPisInfinity(scip, -lbupperboundvar) ) 334 { 335 assert(maxactinf > 0); 336 maxactinf--; 337 tmpmaxact += (upperboundcoef * ubupperboundvar); 338 } 339 else 340 { 341 tmpmaxact = tmpmaxact - (upperboundcoef * lbupperboundvar) + (upperboundcoef * ubupperboundvar); 342 } 343 } 344 } 345 346 *success = TRUE; 347 348 /* the coefficient is positive, so the upper bound contributed to the maxactivity and the lower bound to the minactivity */ 349 if( coef >= 0.0 ) 350 { 351 if( SCIPisInfinity(scip, ub) ) 352 { 353 assert(maxactinf >= 1); 354 if( maxactinf == 1 ) 355 { 356 *maxresactivity = tmpmaxact; 357 } 358 else 359 *maxresactivity = SCIPinfinity(scip); 360 } 361 else 362 { 363 if( maxactinf > 0 ) 364 *maxresactivity = SCIPinfinity(scip); 365 else 366 *maxresactivity = tmpmaxact - coef * ub; 367 } 368 369 if( SCIPisInfinity(scip, -lb) ) 370 { 371 assert(minactinf >= 1); 372 if( minactinf == 1 ) 373 { 374 *minresactivity = tmpminact; 375 } 376 else 377 *minresactivity = -SCIPinfinity(scip); 378 } 379 else 380 { 381 if( minactinf > 0 ) 382 *minresactivity = -SCIPinfinity(scip); 383 else 384 *minresactivity = tmpminact - coef * lb; 385 } 386 } 387 /* the coefficient is negative, so the lower bound contributed to the maxactivity and the upper bound to the minactivity */ 388 else 389 { 390 if( SCIPisInfinity(scip, -lb) ) 391 { 392 assert(maxactinf >= 1); 393 if( maxactinf == 1 ) 394 { 395 *maxresactivity = tmpmaxact; 396 } 397 else 398 *maxresactivity = SCIPinfinity(scip); 399 } 400 else 401 { 402 if( maxactinf > 0 ) 403 *maxresactivity = SCIPinfinity(scip); 404 else 405 *maxresactivity = tmpmaxact - coef * lb; 406 } 407 408 if( SCIPisInfinity(scip, ub) ) 409 { 410 assert(minactinf >= 1); 411 if( minactinf == 1 ) 412 { 413 *minresactivity = tmpminact; 414 } 415 else 416 *minresactivity = -SCIPinfinity(scip); 417 } 418 else 419 { 420 if( minactinf > 0 ) 421 *minresactivity = -SCIPinfinity(scip); 422 else 423 *minresactivity = tmpminact - coef * ub; 424 } 425 } 426 } 427 428 /** get minimum/maximum residual activity for the specified variable and with another variable set to its lower bound */ 429 static 430 void getActivityResidualsLowerBound( 431 SCIP* scip, /**< SCIP main data structure */ 432 SCIP_MATRIX* matrix, /**< matrix containing the constraints */ 433 int row, /**< row index */ 434 int col, /**< column index */ 435 SCIP_Real coef, /**< coefficient of the column in this row */ 436 int lowerboundcol, /**< column index of variable to set to its lower bound */ 437 SCIP_Real lowerboundcoef, /**< coefficient in this row of the column to be set to its lower bound */ 438 SCIP_Real* minresactivity, /**< minimum residual activity of this row */ 439 SCIP_Real* maxresactivity, /**< maximum residual activity of this row */ 440 SCIP_Bool* success /**< pointer to store whether the computation was successful */ 441 ) 442 { 443 SCIP_VAR* var; 444 SCIP_VAR* lowerboundvar; 445 SCIP_Real lb; 446 SCIP_Real ub; 447 SCIP_Real lblowerboundvar; 448 SCIP_Real ublowerboundvar; 449 SCIP_Real tmpmaxact; 450 SCIP_Real tmpminact; 451 int maxactinf; 452 int minactinf; 453 454 assert(scip != NULL); 455 assert(matrix != NULL); 456 assert(row < SCIPmatrixGetNRows(matrix)); 457 assert(minresactivity != NULL); 458 assert(maxresactivity != NULL); 459 460 var = SCIPmatrixGetVar(matrix, col);; 461 lowerboundvar = SCIPmatrixGetVar(matrix, lowerboundcol); 462 assert(var != NULL); 463 assert(lowerboundvar != NULL); 464 465 lb = SCIPvarGetLbGlobal(var); 466 ub = SCIPvarGetUbGlobal(var); 467 468 maxactinf = SCIPmatrixGetRowNMaxActPosInf(matrix, row) + SCIPmatrixGetRowNMaxActNegInf(matrix, row); 469 minactinf = SCIPmatrixGetRowNMinActPosInf(matrix, row) + SCIPmatrixGetRowNMinActNegInf(matrix, row); 470 471 assert(!SCIPisInfinity(scip, lb)); 472 assert(!SCIPisInfinity(scip, -ub)); 473 474 lblowerboundvar = SCIPvarGetLbGlobal(lowerboundvar); 475 ublowerboundvar = SCIPvarGetUbGlobal(lowerboundvar); 476 477 assert(!SCIPisInfinity(scip, lblowerboundvar)); 478 assert(!SCIPisInfinity(scip, -ublowerboundvar)); 479 480 tmpminact = SCIPmatrixGetRowMinActivity(matrix, row); 481 tmpmaxact = SCIPmatrixGetRowMaxActivity(matrix, row); 482 483 /* first, adjust min and max activity such that lowerboundvar is always set to its lower bound */ 484 485 /* abort if the lower bound is -infty */ 486 if( SCIPisInfinity(scip, -lblowerboundvar) ) 487 { 488 *success = FALSE; 489 return; 490 } 491 else 492 { 493 /* coef > 0 --> the upper bound is used for the maxactivity --> update the maxactivity */ 494 if( lowerboundcoef > 0.0 ) 495 { 496 if( SCIPisInfinity(scip, ublowerboundvar) ) 497 { 498 assert(maxactinf > 0); 499 maxactinf--; 500 tmpmaxact += (lowerboundcoef * lblowerboundvar); 501 } 502 else 503 { 504 tmpmaxact = tmpmaxact - (lowerboundcoef * ublowerboundvar) + (lowerboundcoef * lblowerboundvar); 505 } 506 } 507 /* coef < 0 --> the upper bound is used for the minactivity --> update the minactivity */ 508 else 509 { 510 if( SCIPisInfinity(scip, ublowerboundvar) ) 511 { 512 assert(minactinf > 0); 513 minactinf--; 514 tmpminact += (lowerboundcoef * lblowerboundvar); 515 } 516 else 517 { 518 tmpminact = tmpminact - (lowerboundcoef * ublowerboundvar) + (lowerboundcoef * lblowerboundvar); 519 } 520 } 521 } 522 523 *success = TRUE; 524 525 /* the coefficient is positive, so the upper bound contributed to the maxactivity and the lower bound to the minactivity */ 526 if( coef >= 0.0 ) 527 { 528 if( SCIPisInfinity(scip, ub) ) 529 { 530 assert(maxactinf >= 1); 531 if( maxactinf == 1 ) 532 { 533 *maxresactivity = tmpmaxact; 534 } 535 else 536 *maxresactivity = SCIPinfinity(scip); 537 } 538 else 539 { 540 if( maxactinf > 0 ) 541 *maxresactivity = SCIPinfinity(scip); 542 else 543 *maxresactivity = tmpmaxact - coef * ub; 544 } 545 546 if( SCIPisInfinity(scip, -lb) ) 547 { 548 assert(minactinf >= 1); 549 if( minactinf == 1 ) 550 { 551 *minresactivity = tmpminact; 552 } 553 else 554 *minresactivity = -SCIPinfinity(scip); 555 } 556 else 557 { 558 if( minactinf > 0 ) 559 *minresactivity = -SCIPinfinity(scip); 560 else 561 *minresactivity = tmpminact - coef * lb; 562 } 563 } 564 /* the coefficient is negative, so the lower bound contributed to the maxactivity and the upper bound to the minactivity */ 565 else 566 { 567 if( SCIPisInfinity(scip, -lb) ) 568 { 569 assert(maxactinf >= 1); 570 if( maxactinf == 1 ) 571 { 572 *maxresactivity = tmpmaxact; 573 } 574 else 575 *maxresactivity = SCIPinfinity(scip); 576 } 577 else 578 { 579 if( maxactinf > 0 ) 580 *maxresactivity = SCIPinfinity(scip); 581 else 582 *maxresactivity = tmpmaxact - coef * lb; 583 } 584 585 if( SCIPisInfinity(scip, ub) ) 586 { 587 assert(minactinf >= 1); 588 if( minactinf == 1 ) 589 { 590 *minresactivity = tmpminact; 591 } 592 else 593 *minresactivity = -SCIPinfinity(scip); 594 } 595 else 596 { 597 if( minactinf > 0 ) 598 *minresactivity = -SCIPinfinity(scip); 599 else 600 *minresactivity = tmpminact - coef * ub; 601 } 602 } 603 } 604 605 /** Calculate bounds of the dominated variable by rowbound analysis. 606 * We use a special kind of predictive rowbound analysis by first setting the dominating variable to its upper bound. 607 */ 608 static 609 SCIP_RETCODE calcVarBoundsDominated( 610 SCIP* scip, /**< SCIP main data structure */ 611 SCIP_MATRIX* matrix, /**< matrix containing the constraints */ 612 int row, /**< current row index */ 613 int coldominating, /**< column index of dominating variable */ 614 SCIP_Real valdominating, /**< row coefficient of dominating variable */ 615 int coldominated, /**< column index of dominated variable */ 616 SCIP_Real valdominated, /**< row coefficient of dominated variable */ 617 SCIP_Bool* ubcalculated, /**< was a upper bound calculated? */ 618 SCIP_Real* calculatedub, /**< predicted upper bound */ 619 SCIP_Bool* wclbcalculated, /**< was a lower worst case bound calculated? */ 620 SCIP_Real* calculatedwclb, /**< predicted worst case lower bound */ 621 SCIP_Bool* lbcalculated, /**< was a lower bound calculated? */ 622 SCIP_Real* calculatedlb, /**< predicted lower bound */ 623 SCIP_Bool* wcubcalculated, /**< was a worst case upper bound calculated? */ 624 SCIP_Real* calculatedwcub /**< calculated worst case upper bound */ 625 ) 626 { 627 SCIP_Real minresactivity; 628 SCIP_Real maxresactivity; 629 SCIP_Real lhs; 630 SCIP_Real rhs; 631 SCIP_Bool success; 632 633 assert(scip != NULL); 634 assert(matrix != NULL); 635 assert(0 <= row && row < SCIPmatrixGetNRows(matrix)); 636 assert(0 <= coldominating && coldominating < SCIPmatrixGetNColumns(matrix)); 637 assert(0 <= coldominated && coldominated < SCIPmatrixGetNColumns(matrix)); 638 639 assert(ubcalculated != NULL); 640 assert(calculatedub != NULL); 641 assert(wclbcalculated != NULL); 642 assert(calculatedwclb != NULL); 643 assert(lbcalculated != NULL); 644 assert(calculatedlb != NULL); 645 assert(wcubcalculated != NULL); 646 assert(calculatedwcub != NULL); 647 648 assert(!SCIPisZero(scip, valdominated)); 649 assert(SCIPmatrixGetVar(matrix, coldominated) != NULL); 650 651 *ubcalculated = FALSE; 652 *wclbcalculated = FALSE; 653 *lbcalculated = FALSE; 654 *wcubcalculated = FALSE; 655 656 /* no rowbound analysis for multiaggregated variables, which should not exist, because the matrix only consists of 657 * active variables 658 */ 659 assert(SCIPvarGetStatus(SCIPmatrixGetVar(matrix, coldominating)) != SCIP_VARSTATUS_MULTAGGR); 660 assert(SCIPvarGetStatus(SCIPmatrixGetVar(matrix, coldominated)) != SCIP_VARSTATUS_MULTAGGR); 661 662 lhs = SCIPmatrixGetRowLhs(matrix, row); 663 rhs = SCIPmatrixGetRowRhs(matrix, row); 664 assert(!SCIPisInfinity(scip, lhs)); 665 assert(!SCIPisInfinity(scip, -rhs)); 666 667 /* get minimum/maximum activity of this row without the dominated variable */ 668 getActivityResidualsUpperBound(scip, matrix, row, coldominated, valdominated, coldominating, valdominating, 669 &minresactivity, &maxresactivity, &success); 670 671 if( !success ) 672 return SCIP_OKAY; 673 674 assert(!SCIPisInfinity(scip, minresactivity)); 675 assert(!SCIPisInfinity(scip, -maxresactivity)); 676 677 *calculatedub = SCIPinfinity(scip); 678 *calculatedwclb = -SCIPinfinity(scip); 679 *calculatedlb = -SCIPinfinity(scip); 680 *calculatedwcub = SCIPinfinity(scip); 681 682 /* predictive rowbound analysis */ 683 684 if( valdominated > 0.0 ) 685 { 686 /* lower bound calculation */ 687 if( !SCIPisInfinity(scip, maxresactivity) ) 688 { 689 *calculatedlb = (lhs - maxresactivity)/valdominated; 690 *lbcalculated = TRUE; 691 } 692 693 /* worst case calculation of lower bound */ 694 if( !SCIPisInfinity(scip, -minresactivity) ) 695 { 696 *calculatedwclb = (lhs - minresactivity)/valdominated; 697 *wclbcalculated = TRUE; 698 } 699 else 700 { 701 /* worst case lower bound is infinity */ 702 *calculatedwclb = SCIPinfinity(scip); 703 *wclbcalculated = TRUE; 704 } 705 706 /* we can only calculate upper bounds, of the right hand side is finite */ 707 if( !SCIPmatrixIsRowRhsInfinity(matrix, row) ) 708 { 709 /* upper bound calculation */ 710 if( !SCIPisInfinity(scip, -minresactivity) ) 711 { 712 *calculatedub = (rhs - minresactivity)/valdominated; 713 *ubcalculated = TRUE; 714 } 715 716 /* worst case calculation of upper bound */ 717 if( !SCIPisInfinity(scip, maxresactivity) ) 718 { 719 *calculatedwcub = (rhs - maxresactivity)/valdominated; 720 *wcubcalculated = TRUE; 721 } 722 else 723 { 724 /* worst case upper bound is -infinity */ 725 *calculatedwcub = -SCIPinfinity(scip); 726 *wcubcalculated = TRUE; 727 } 728 } 729 } 730 else 731 { 732 /* upper bound calculation */ 733 if( !SCIPisInfinity(scip, maxresactivity) ) 734 { 735 *calculatedub = (lhs - maxresactivity)/valdominated; 736 *ubcalculated = TRUE; 737 } 738 739 /* worst case calculation of upper bound */ 740 if( !SCIPisInfinity(scip, -minresactivity) ) 741 { 742 *calculatedwcub = (lhs - minresactivity)/valdominated; 743 *wcubcalculated = TRUE; 744 } 745 else 746 { 747 /* worst case upper bound is -infinity */ 748 *calculatedwcub = -SCIPinfinity(scip); 749 *wcubcalculated = TRUE; 750 } 751 752 /* we can only calculate lower bounds, of the right hand side is finite */ 753 if( !SCIPmatrixIsRowRhsInfinity(matrix, row) ) 754 { 755 /* lower bound calculation */ 756 if( !SCIPisInfinity(scip, -minresactivity) ) 757 { 758 *calculatedlb = (rhs - minresactivity)/valdominated; 759 *lbcalculated = TRUE; 760 } 761 762 /* worst case calculation of lower bound */ 763 if( !SCIPisInfinity(scip, maxresactivity) ) 764 { 765 *calculatedwclb = (rhs - maxresactivity)/valdominated; 766 *wclbcalculated = TRUE; 767 } 768 else 769 { 770 /* worst case lower bound is infinity */ 771 *calculatedwclb = SCIPinfinity(scip); 772 *wclbcalculated = TRUE; 773 } 774 } 775 } 776 777 return SCIP_OKAY; 778 } 779 780 /** Calculate bounds of the dominating variable by rowbound analysis. 781 * We use a special kind of predictive rowbound analysis by first setting the dominated variable to its lower bound. 782 */ 783 static 784 SCIP_RETCODE calcVarBoundsDominating( 785 SCIP* scip, /**< SCIP main data structure */ 786 SCIP_MATRIX* matrix, /**< matrix containing the constraints */ 787 int row, /**< current row index */ 788 int coldominating, /**< column index of dominating variable */ 789 SCIP_Real valdominating, /**< row coefficient of dominating variable */ 790 int coldominated, /**< column index of dominated variable */ 791 SCIP_Real valdominated, /**< row coefficient of dominated variable */ 792 SCIP_Bool* ubcalculated, /**< was a upper bound calculated? */ 793 SCIP_Real* calculatedub, /**< predicted upper bound */ 794 SCIP_Bool* wclbcalculated, /**< was a lower worst case bound calculated? */ 795 SCIP_Real* calculatedwclb, /**< predicted worst case lower bound */ 796 SCIP_Bool* lbcalculated, /**< was a lower bound calculated? */ 797 SCIP_Real* calculatedlb, /**< predicted lower bound */ 798 SCIP_Bool* wcubcalculated, /**< was a worst case upper bound calculated? */ 799 SCIP_Real* calculatedwcub /**< calculated worst case upper bound */ 800 ) 801 { 802 SCIP_Real minresactivity; 803 SCIP_Real maxresactivity; 804 SCIP_Real lhs; 805 SCIP_Real rhs; 806 SCIP_Bool success; 807 808 assert(scip != NULL); 809 assert(matrix != NULL); 810 assert(0 <= row && row < SCIPmatrixGetNRows(matrix) ); 811 assert(0 <= coldominating && coldominating < SCIPmatrixGetNColumns(matrix)); 812 assert(0 <= coldominated && coldominated < SCIPmatrixGetNColumns(matrix)); 813 814 assert(ubcalculated != NULL); 815 assert(calculatedub != NULL); 816 assert(wclbcalculated != NULL); 817 assert(calculatedwclb != NULL); 818 assert(lbcalculated != NULL); 819 assert(calculatedlb != NULL); 820 assert(wcubcalculated != NULL); 821 assert(calculatedwcub != NULL); 822 823 assert(!SCIPisZero(scip, valdominating)); 824 assert(SCIPmatrixGetVar(matrix, coldominating) != NULL); 825 826 *ubcalculated = FALSE; 827 *wclbcalculated = FALSE; 828 *lbcalculated = FALSE; 829 *wcubcalculated = FALSE; 830 831 /* no rowbound analysis for multiaggregated variables, which should not exist, because the matrix only consists of 832 * active variables 833 */ 834 assert(SCIPvarGetStatus(SCIPmatrixGetVar(matrix, coldominating)) != SCIP_VARSTATUS_MULTAGGR); 835 assert(SCIPvarGetStatus(SCIPmatrixGetVar(matrix, coldominated)) != SCIP_VARSTATUS_MULTAGGR); 836 837 lhs = SCIPmatrixGetRowLhs(matrix, row); 838 rhs = SCIPmatrixGetRowRhs(matrix, row); 839 assert(!SCIPisInfinity(scip, lhs)); 840 assert(!SCIPisInfinity(scip, -rhs)); 841 842 /* get minimum/maximum activity of this row without the dominating variable */ 843 getActivityResidualsLowerBound(scip, matrix, row, coldominating, valdominating, coldominated, valdominated, 844 &minresactivity, &maxresactivity, &success); 845 846 if( !success ) 847 return SCIP_OKAY; 848 849 assert(!SCIPisInfinity(scip, minresactivity)); 850 assert(!SCIPisInfinity(scip, -maxresactivity)); 851 852 *calculatedub = SCIPinfinity(scip); 853 *calculatedwclb = -SCIPinfinity(scip); 854 *calculatedlb = -SCIPinfinity(scip); 855 *calculatedwcub = SCIPinfinity(scip); 856 857 /* predictive rowbound analysis */ 858 859 if( valdominating > 0.0 ) 860 { 861 /* lower bound calculation */ 862 if( !SCIPisInfinity(scip, maxresactivity) ) 863 { 864 *calculatedlb = (lhs - maxresactivity)/valdominating; 865 *lbcalculated = TRUE; 866 } 867 868 /* worst case calculation of lower bound */ 869 if( !SCIPisInfinity(scip, -minresactivity) ) 870 { 871 *calculatedwclb = (lhs - minresactivity)/valdominating; 872 *wclbcalculated = TRUE; 873 } 874 else 875 { 876 /* worst case lower bound is infinity */ 877 *calculatedwclb = SCIPinfinity(scip); 878 *wclbcalculated = TRUE; 879 } 880 881 /* we can only calculate upper bounds, of the right hand side is finite */ 882 if( !SCIPmatrixIsRowRhsInfinity(matrix, row) ) 883 { 884 /* upper bound calculation */ 885 if( !SCIPisInfinity(scip, -minresactivity) ) 886 { 887 *calculatedub = (rhs - minresactivity)/valdominating; 888 *ubcalculated = TRUE; 889 } 890 891 /* worst case calculation of upper bound */ 892 if( !SCIPisInfinity(scip, maxresactivity) ) 893 { 894 *calculatedwcub = (rhs - maxresactivity)/valdominating; 895 *wcubcalculated = TRUE; 896 } 897 else 898 { 899 /* worst case upper bound is -infinity */ 900 *calculatedwcub = -SCIPinfinity(scip); 901 *wcubcalculated = TRUE; 902 } 903 } 904 } 905 else 906 { 907 /* upper bound calculation */ 908 if( !SCIPisInfinity(scip, maxresactivity) ) 909 { 910 *calculatedub = (lhs - maxresactivity)/valdominating; 911 *ubcalculated = TRUE; 912 } 913 914 /* worst case calculation of upper bound */ 915 if( !SCIPisInfinity(scip, -minresactivity) ) 916 { 917 *calculatedwcub = (lhs - minresactivity)/valdominating; 918 *wcubcalculated = TRUE; 919 } 920 else 921 { 922 /* worst case upper bound is -infinity */ 923 *calculatedwcub = -SCIPinfinity(scip); 924 *wcubcalculated = TRUE; 925 } 926 927 /* we can only calculate lower bounds, of the right hand side is finite */ 928 if( !SCIPmatrixIsRowRhsInfinity(matrix, row) ) 929 { 930 /* lower bound calculation */ 931 if( !SCIPisInfinity(scip, -minresactivity) ) 932 { 933 *calculatedlb = (rhs - minresactivity)/valdominating; 934 *lbcalculated = TRUE; 935 } 936 937 /* worst case calculation of lower bound */ 938 if( !SCIPisInfinity(scip, maxresactivity) ) 939 { 940 *calculatedwclb = (rhs - maxresactivity)/valdominating; 941 *wclbcalculated = TRUE; 942 } 943 else 944 { 945 /* worst case lower bound is infinity */ 946 *calculatedwclb = SCIPinfinity(scip); 947 *wclbcalculated = TRUE; 948 } 949 } 950 } 951 952 return SCIP_OKAY; 953 } 954 955 /** try to find new variable bounds and update them when they are better then the old bounds */ 956 static 957 SCIP_RETCODE updateBounds( 958 SCIP* scip, /**< SCIP main data structure */ 959 SCIP_MATRIX* matrix, /**< matrix containing the constraints */ 960 int row, /**< row index */ 961 int col1, /**< dominating variable index */ 962 SCIP_Real val1, /**< dominating variable coefficient */ 963 int col2, /**< dominated variable index */ 964 SCIP_Real val2, /**< dominated variable coefficient */ 965 SCIP_Bool predictdominating, /**< flag indicating if bounds of dominating or dominated variable are predicted */ 966 SCIP_Real* upperbound, /**< predicted upper bound */ 967 SCIP_Real* wclowerbound, /**< predicted worst case lower bound */ 968 SCIP_Real* lowerbound, /**< predicted lower bound */ 969 SCIP_Real* wcupperbound /**< predicted worst case upper bound */ 970 ) 971 { 972 SCIP_Bool ubcalculated; 973 SCIP_Bool wclbcalculated; 974 SCIP_Bool lbcalculated; 975 SCIP_Bool wcubcalculated; 976 SCIP_Real newub; 977 SCIP_Real newwclb; 978 SCIP_Real newlb; 979 SCIP_Real newwcub; 980 981 assert(scip != NULL); 982 assert(matrix != NULL); 983 assert(upperbound != NULL); 984 assert(wclowerbound != NULL); 985 assert(lowerbound != NULL); 986 assert(wcupperbound != NULL); 987 988 newub = SCIPinfinity(scip); 989 newlb = -SCIPinfinity(scip); 990 newwcub = newub; 991 newwclb = newlb; 992 993 if( predictdominating ) 994 { 995 /* do predictive rowbound analysis for the dominating variable */ 996 SCIP_CALL( calcVarBoundsDominating(scip, matrix, row, col1, val1, col2, val2, 997 &ubcalculated, &newub, &wclbcalculated, &newwclb, 998 &lbcalculated, &newlb, &wcubcalculated, &newwcub) ); 999 } 1000 else 1001 { 1002 /* do predictive rowbound analysis for the dominated variable */ 1003 SCIP_CALL( calcVarBoundsDominated(scip, matrix, row, col1, val1, col2, val2, 1004 &ubcalculated, &newub, &wclbcalculated, &newwclb, 1005 &lbcalculated, &newlb, &wcubcalculated, &newwcub) ); 1006 } 1007 1008 /* update bounds in case if they are better */ 1009 if( ubcalculated ) 1010 { 1011 if( newub < *upperbound ) 1012 *upperbound = newub; 1013 } 1014 if( wclbcalculated ) 1015 { 1016 if( newwclb > *wclowerbound ) 1017 *wclowerbound = newwclb; 1018 } 1019 if( lbcalculated ) 1020 { 1021 if( newlb > *lowerbound ) 1022 *lowerbound = newlb; 1023 } 1024 if( wcubcalculated ) 1025 { 1026 if( newwcub < *wcupperbound ) 1027 *wcupperbound = newwcub; 1028 } 1029 1030 return SCIP_OKAY; 1031 } 1032 1033 /** detect parallel columns by using the algorithm of Bixby and Wagner 1034 * see paper: "A note on Detecting Simple Redundancies in Linear Systems", June 1986 1035 */ 1036 static 1037 SCIP_RETCODE detectParallelCols( 1038 SCIP* scip, /**< SCIP main data structure */ 1039 SCIP_MATRIX* matrix, /**< matrix containing the constraints */ 1040 int* pclass, /**< parallel column classes */ 1041 SCIP_Bool* varineq /**< indicating if variable is within an equation */ 1042 ) 1043 { 1044 SCIP_Real* valpnt; 1045 SCIP_Real* values; 1046 SCIP_Real* scale; 1047 int* classsizes; 1048 int* pcset; 1049 int* rowpnt; 1050 int* rowend; 1051 int* colindices; 1052 int* pcs; 1053 SCIP_Real startval; 1054 SCIP_Real aij; 1055 int startpc; 1056 int startk; 1057 int startt; 1058 int pcsetfill; 1059 int colidx; 1060 int k; 1061 int t; 1062 int m; 1063 int i; 1064 int r; 1065 int newpclass; 1066 int pc; 1067 int nrows; 1068 int ncols; 1069 1070 assert(scip != NULL); 1071 assert(matrix != NULL); 1072 assert(pclass != NULL); 1073 assert(varineq != NULL); 1074 1075 nrows = SCIPmatrixGetNRows(matrix); 1076 ncols = SCIPmatrixGetNColumns(matrix); 1077 1078 SCIP_CALL( SCIPallocBufferArray(scip, &classsizes, ncols) ); 1079 SCIP_CALL( SCIPallocBufferArray(scip, &scale, ncols) ); 1080 SCIP_CALL( SCIPallocBufferArray(scip, &pcset, ncols) ); 1081 SCIP_CALL( SCIPallocBufferArray(scip, &values, ncols) ); 1082 SCIP_CALL( SCIPallocBufferArray(scip, &colindices, ncols) ); 1083 SCIP_CALL( SCIPallocBufferArray(scip, &pcs, ncols) ); 1084 1085 BMSclearMemoryArray(scale, ncols); 1086 BMSclearMemoryArray(pclass, ncols); 1087 BMSclearMemoryArray(classsizes, ncols); 1088 1089 classsizes[0] = ncols; 1090 pcsetfill = 0; 1091 for( t = 1; t < ncols; ++t ) 1092 pcset[pcsetfill++] = t; 1093 1094 /* loop over all rows */ 1095 for( r = 0; r < nrows; ++r ) 1096 { 1097 /* we consider only non-empty equations or ranged rows */ 1098 if( !SCIPmatrixIsRowRhsInfinity(matrix, r) && SCIPmatrixGetRowNNonzs(matrix, r) > 0 ) 1099 { 1100 rowpnt = SCIPmatrixGetRowIdxPtr(matrix, r); 1101 rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, r); 1102 valpnt = SCIPmatrixGetRowValPtr(matrix, r); 1103 1104 i = 0; 1105 for( ; (rowpnt < rowend); rowpnt++, valpnt++ ) 1106 { 1107 aij = *valpnt; 1108 colidx = *rowpnt; 1109 1110 /* remember variable was part of an equation or ranged row */ 1111 varineq[colidx] = TRUE; 1112 1113 if( scale[colidx] == 0.0 ) 1114 scale[colidx] = aij; 1115 assert(scale[colidx] != 0.0); 1116 1117 colindices[i] = colidx; 1118 values[i] = aij / scale[colidx]; 1119 pc = pclass[colidx]; 1120 assert(pc < ncols); 1121 1122 /* update class sizes and pclass set */ 1123 assert(classsizes[pc] > 0); 1124 classsizes[pc]--; 1125 if( classsizes[pc] == 0 ) 1126 { 1127 assert(pcsetfill < ncols); 1128 pcset[pcsetfill++] = pc; 1129 } 1130 pcs[i] = pc; 1131 1132 i++; 1133 } 1134 1135 assert(i > 0); 1136 1137 /* sort on the pclass values */ 1138 if( i > 1 ) 1139 { 1140 SCIPsortIntIntReal(pcs, colindices, values, i); 1141 } 1142 1143 k = 0; 1144 while( TRUE ) /*lint !e716*/ 1145 { 1146 assert(k < i); 1147 startpc = pcs[k]; 1148 startk = k; 1149 1150 /* find pclass-sets */ 1151 while( k < i && pcs[k] == startpc ) 1152 k++; 1153 1154 /* sort on the A values which have equal pclass values */ 1155 if( k - startk > 1 ) 1156 SCIPsortRealInt(&(values[startk]), &(colindices[startk]), k - startk); 1157 1158 t = 0; 1159 while( TRUE ) /*lint !e716*/ 1160 { 1161 assert(startk + t < i); 1162 startval = values[startk + t]; 1163 startt = t; 1164 1165 /* find A-sets */ 1166 while( t < k - startk && SCIPisEQ(scip, startval, values[startk + t]) ) 1167 t++; 1168 1169 /* get new pclass */ 1170 newpclass = pcset[0]; 1171 assert(pcsetfill > 0); 1172 pcset[0] = pcset[--pcsetfill]; 1173 1174 /* renumbering */ 1175 for( m = startk + startt; m < startk + t; m++ ) 1176 { 1177 assert(m < i); 1178 assert(colindices[m] < ncols); 1179 assert(newpclass < ncols); 1180 1181 pclass[colindices[m]] = newpclass; 1182 classsizes[newpclass]++; 1183 } 1184 1185 if( t == k - startk ) 1186 break; 1187 } 1188 1189 if( k == SCIPmatrixGetRowNNonzs(matrix, r) ) 1190 break; 1191 } 1192 } 1193 } 1194 1195 SCIPfreeBufferArray(scip, &pcs); 1196 SCIPfreeBufferArray(scip, &colindices); 1197 SCIPfreeBufferArray(scip, &values); 1198 SCIPfreeBufferArray(scip, &pcset); 1199 SCIPfreeBufferArray(scip, &scale); 1200 SCIPfreeBufferArray(scip, &classsizes); 1201 1202 return SCIP_OKAY; 1203 } 1204 1205 1206 /** try to improve variable bounds by predictive bound strengthening */ 1207 static 1208 SCIP_RETCODE predBndStr( 1209 SCIP* scip, /**< SCIP main data structure */ 1210 SCIP_VAR* dominatingvar, /**< dominating variable */ 1211 int dominatingidx, /**< column index of the dominating variable */ 1212 SCIP_Real dominatingub, /**< predicted upper bound of the dominating variable */ 1213 SCIP_Real dominatinglb, /**< predicted lower bound of the dominating variable */ 1214 SCIP_Real dominatingwcub, /**< predicted worst case upper bound of the dominating variable */ 1215 SCIP_VAR* dominatedvar, /**< dominated variable */ 1216 int dominatedidx, /**< column index of the dominated variable */ 1217 SCIP_Real dominatedub, /**< predicted upper bound of the dominated variable */ 1218 SCIP_Real dominatedwclb, /**< predicted worst case lower bound of the dominated variable */ 1219 SCIP_Real dominatedlb, /**< predicted lower bound of the dominated variable */ 1220 FIXINGDIRECTION* varstofix, /**< array holding fixing information */ 1221 int* nchgbds /**< count number of bound changes */ 1222 ) 1223 { 1224 /* we compare only variables from the same type */ 1225 if( !(SCIPvarGetType(dominatingvar) == SCIPvarGetType(dominatedvar) || 1226 SCIPvarIsBinary(dominatingvar) == SCIPvarIsBinary(dominatedvar) || 1227 (SCIPvarGetType(dominatingvar) == SCIP_VARTYPE_INTEGER && SCIPvarGetType(dominatedvar) == SCIP_VARTYPE_IMPLINT) || 1228 (SCIPvarGetType(dominatedvar) == SCIP_VARTYPE_INTEGER && SCIPvarGetType(dominatingvar) == SCIP_VARTYPE_IMPLINT)) ) 1229 { 1230 return SCIP_OKAY; 1231 } 1232 1233 if( varstofix[dominatingidx] == NOFIX ) 1234 { 1235 /* assume x dominates y (x->y). we get this bound from a positive coefficient 1236 * of the dominating variable. because x->y the dominated variable y has 1237 * a positive coefficient too. thus y contributes to the minactivity with its 1238 * lower bound. but this case is considered within predictive bound analysis. 1239 * thus the dominating upper bound is a common upper bound. 1240 */ 1241 if( !SCIPisInfinity(scip, dominatingub) ) 1242 { 1243 SCIP_Real newub; 1244 SCIP_Real oldub; 1245 SCIP_Real lb; 1246 1247 newub = dominatingub; 1248 oldub = SCIPvarGetUbGlobal(dominatingvar); 1249 lb = SCIPvarGetLbGlobal(dominatingvar); 1250 1251 /* if( SCIPvarGetType(dominatingvar) != SCIP_VARTYPE_CONTINUOUS ) 1252 newub = SCIPceil(scip, newub); */ 1253 1254 if( SCIPisLE(scip, lb, newub) && SCIPisLT(scip, newub, oldub) ) 1255 { 1256 SCIPdebugMsg(scip, "[ub]\tupper bound for dominating variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n", 1257 SCIPvarGetName(dominatingvar), lb, oldub, lb, newub); 1258 SCIP_CALL( SCIPchgVarUb(scip, dominatingvar, newub) ); 1259 (*nchgbds)++; 1260 } 1261 } 1262 1263 /* assume x dominates y (x->y). we get this lower bound of the dominating variable 1264 * from a negative coefficient within a <= relation. if y has a positive coefficient 1265 * we get a common lower bound of x from predictive bound analysis. if y has a 1266 * negative coefficient we get an improved lower bound of x because the minactivity 1267 * is greater. for discrete variables we have to round down the lower bound. 1268 */ 1269 if( !SCIPisInfinity(scip, -dominatinglb) ) 1270 { 1271 SCIP_Real newlb; 1272 SCIP_Real oldlb; 1273 SCIP_Real ub; 1274 1275 newlb = dominatinglb; 1276 oldlb = SCIPvarGetLbGlobal(dominatingvar); 1277 ub = SCIPvarGetUbGlobal(dominatingvar); 1278 1279 if( SCIPvarGetType(dominatingvar) != SCIP_VARTYPE_CONTINUOUS ) 1280 newlb = SCIPfloor(scip, newlb); 1281 1282 if( SCIPisLT(scip, oldlb, newlb) && SCIPisLE(scip, newlb, ub) ) 1283 { 1284 SCIPdebugMsg(scip, "[lb]\tlower bound of dominating variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n", 1285 SCIPvarGetName(dominatingvar), oldlb, ub, newlb, ub); 1286 SCIP_CALL( SCIPchgVarLb(scip, dominatingvar, newlb) ); 1287 (*nchgbds)++; 1288 } 1289 } 1290 1291 /* assume x dominates y (x->y). we get this bound from a positive coefficient 1292 * of x within a <= relation. from x->y it follows, that y has a positive 1293 * coefficient in this row too. the worst case upper bound of x is an estimation 1294 * of how great x can be in every case. if the objective coefficient of x is 1295 * negative we get thus a lower bound of x. for discrete variables we have 1296 * to round down the lower bound before. 1297 */ 1298 if( !SCIPisInfinity(scip, dominatingwcub) && SCIPisNegative(scip, SCIPvarGetObj(dominatingvar))) 1299 { 1300 SCIP_Real newlb; 1301 SCIP_Real oldlb; 1302 SCIP_Real ub; 1303 1304 newlb = dominatingwcub; 1305 oldlb = SCIPvarGetLbGlobal(dominatingvar); 1306 ub = SCIPvarGetUbGlobal(dominatingvar); 1307 1308 if( SCIPvarGetType(dominatingvar) != SCIP_VARTYPE_CONTINUOUS ) 1309 newlb = SCIPfloor(scip, newlb); 1310 1311 if( SCIPisLT(scip, oldlb, newlb) && SCIPisLE(scip, newlb, ub) ) 1312 { 1313 SCIPdebugMsg(scip, "[wcub]\tlower bound of dominating variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n", 1314 SCIPvarGetName(dominatingvar), oldlb, ub, newlb, ub); 1315 SCIP_CALL( SCIPchgVarLb(scip, dominatingvar, newlb) ); 1316 (*nchgbds)++; 1317 } 1318 } 1319 } 1320 1321 if( varstofix[dominatedidx] == NOFIX ) 1322 { 1323 /* assume x dominates y (x->y). we get this bound for a positive coefficient of y 1324 * within a <= relation. if x has a negative coefficient we get a common upper 1325 * bound of y. if x has a positive coefficient we get an improved upper bound 1326 * of y because the minactivity is greater. 1327 */ 1328 if( !SCIPisInfinity(scip, dominatedub) ) 1329 { 1330 SCIP_Real newub; 1331 SCIP_Real oldub; 1332 SCIP_Real lb; 1333 1334 newub = dominatedub; 1335 oldub = SCIPvarGetUbGlobal(dominatedvar); 1336 lb = SCIPvarGetLbGlobal(dominatedvar); 1337 1338 if( SCIPisLE(scip, lb, newub) && SCIPisLT(scip, newub, oldub) ) 1339 { 1340 SCIPdebugMsg(scip, "[ub]\tupper bound of dominated variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n", 1341 SCIPvarGetName(dominatedvar), lb, oldub, lb, newub); 1342 SCIP_CALL( SCIPchgVarUb(scip, dominatedvar, newub) ); 1343 (*nchgbds)++; 1344 } 1345 } 1346 1347 /* assume x dominates y (x->y). we get this bound only from a negative 1348 * coefficient of y within a <= relation. because of x->y then x has a negative 1349 * coefficient too. the worst case lower bound is an estimation what property 1350 * the dominated variable must have if the dominating variable is at its upper bound. 1351 * to get an upper bound of the dominated variable we need to consider a positive 1352 * objective coefficient. for discrete variables we have to round up the upper bound. 1353 */ 1354 if( !SCIPisInfinity(scip, -dominatedwclb) && SCIPisPositive(scip, SCIPvarGetObj(dominatedvar)) ) 1355 { 1356 SCIP_Real newub; 1357 SCIP_Real oldub; 1358 SCIP_Real lb; 1359 1360 newub = dominatedwclb; 1361 oldub = SCIPvarGetUbGlobal(dominatedvar); 1362 lb = SCIPvarGetLbGlobal(dominatedvar); 1363 1364 if( SCIPvarGetType(dominatedvar) != SCIP_VARTYPE_CONTINUOUS ) 1365 newub = SCIPceil(scip, newub); 1366 1367 if( SCIPisLE(scip, lb, newub) && SCIPisLT(scip, newub, oldub) ) 1368 { 1369 SCIPdebugMsg(scip, "[wclb]\tupper bound of dominated variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n", 1370 SCIPvarGetName(dominatedvar), lb, oldub, lb, newub); 1371 SCIP_CALL( SCIPchgVarUb(scip, dominatedvar, newub) ); 1372 (*nchgbds)++; 1373 } 1374 } 1375 1376 /* assume x dominates y (x->y). we get a lower bound of y from a negative 1377 * coefficient within a <= relation. but if x->y then x has a negative 1378 * coefficient too and contributes with its upper bound to the minactivity. 1379 * thus in all we have a common lower bound calculation and no rounding is necessary. 1380 */ 1381 if( !SCIPisInfinity(scip, -dominatedlb) ) 1382 { 1383 SCIP_Real newlb; 1384 SCIP_Real oldlb; 1385 SCIP_Real ub; 1386 1387 newlb = dominatedlb; 1388 oldlb = SCIPvarGetLbGlobal(dominatedvar); 1389 ub = SCIPvarGetUbGlobal(dominatedvar); 1390 1391 if( SCIPisLT(scip, oldlb, newlb) && SCIPisLE(scip, newlb, ub) ) 1392 { 1393 SCIPdebugMsg(scip, "[lb]\tlower bound of dominated variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n", 1394 SCIPvarGetName(dominatedvar), oldlb, ub, newlb, ub); 1395 SCIP_CALL( SCIPchgVarLb(scip, dominatedvar, newlb) ); 1396 (*nchgbds)++; 1397 } 1398 } 1399 } 1400 1401 return SCIP_OKAY; 1402 } 1403 1404 /** try to find variable fixings */ 1405 static 1406 SCIP_RETCODE findFixings( 1407 SCIP* scip, /**< SCIP main data structure */ 1408 SCIP_MATRIX* matrix, /**< constraint matrix structure */ 1409 SCIP_VAR* dominatingvar, /**< dominating variable */ 1410 int dominatingidx, /**< column index of the dominating variable */ 1411 SCIP_Real dominatingub, /**< predicted upper bound of the dominating variable */ 1412 SCIP_Real dominatingwclb, /**< predicted worst case lower bound of the dominating variable */ 1413 SCIP_Real dominatinglb, /**< predicted lower bound of the dominating variable */ 1414 SCIP_Real dominatingwcub, /**< predicted worst case upper bound of the dominating variable */ 1415 SCIP_VAR* dominatedvar, /**< dominated variable */ 1416 int dominatedidx, /**< column index of the dominated variable */ 1417 FIXINGDIRECTION* varstofix, /**< array holding fixing information */ 1418 SCIP_Bool onlybinvars, /**< flag indicating only binary variables are present */ 1419 SCIP_Bool onlyoneone, /**< when onlybinvars is TRUE, flag indicates if both binary variables are in clique */ 1420 int* nfixings /**< counter for possible fixings */ 1421 ) 1422 { 1423 /* we compare only variables from the same type */ 1424 if( !(SCIPvarGetType(dominatingvar) == SCIPvarGetType(dominatedvar) || 1425 SCIPvarIsBinary(dominatingvar) == SCIPvarIsBinary(dominatedvar) || 1426 (SCIPvarGetType(dominatingvar) == SCIP_VARTYPE_INTEGER && SCIPvarGetType(dominatedvar) == SCIP_VARTYPE_IMPLINT) || 1427 (SCIPvarGetType(dominatedvar) == SCIP_VARTYPE_INTEGER && SCIPvarGetType(dominatingvar) == SCIP_VARTYPE_IMPLINT)) ) 1428 { 1429 return SCIP_OKAY; 1430 } 1431 1432 if( varstofix[dominatedidx] == NOFIX && SCIPmatrixGetColNNonzs(matrix, dominatingidx) == 1 1433 && SCIPmatrixGetColNNonzs(matrix, dominatedidx) == 1 ) 1434 { 1435 /* We have a x->y dominance relation and only one equality constraint 1436 * where the dominating variable x with an infinity upper bound and the 1437 * dominated variable y are present. Then the dominated variable y 1438 * can be fixed at its lower bound. 1439 */ 1440 int row; 1441 row = *(SCIPmatrixGetColIdxPtr(matrix, dominatedidx)); 1442 1443 if( SCIPisEQ(scip, SCIPmatrixGetRowLhs(matrix, row), SCIPmatrixGetRowRhs(matrix, row)) && 1444 SCIPisInfinity(scip, SCIPvarGetUbGlobal(dominatingvar)) ) 1445 { 1446 varstofix[dominatedidx] = FIXATLB; 1447 (*nfixings)++; 1448 1449 return SCIP_OKAY; 1450 } 1451 } 1452 1453 if( varstofix[dominatedidx] == NOFIX && !SCIPisNegative(scip, SCIPvarGetObj(dominatedvar)) ) 1454 { 1455 if( !SCIPisInfinity(scip, -dominatingwclb) && 1456 SCIPisLE(scip, dominatingwclb, SCIPvarGetUbGlobal(dominatingvar)) ) 1457 { 1458 /* we have a x->y dominance relation with a positive obj coefficient 1459 * of the dominated variable y. we need to secure feasibility 1460 * by testing if the predicted lower worst case bound is less equal the 1461 * current upper bound. it is possible, that the lower worst case bound 1462 * is infinity and the upper bound of the dominating variable x is 1463 * infinity too. 1464 */ 1465 varstofix[dominatedidx] = FIXATLB; 1466 (*nfixings)++; 1467 } 1468 } 1469 1470 if( varstofix[dominatedidx] == NOFIX && !SCIPisInfinity(scip, dominatingub) && 1471 SCIPisLE(scip, dominatingub, SCIPvarGetUbGlobal(dominatingvar)) ) 1472 { 1473 /* we have a x->y dominance relation with an arbitrary obj coefficient 1474 * of the dominating variable x. in all cases we have to look 1475 * if the predicted upper bound of the dominating variable is great enough. 1476 * by testing, that the predicted upper bound is not infinity we avoid problems 1477 * with x->y e.g. 1478 * min -x -y 1479 * s.t. -x -y <= -1 1480 * 0<=x<=1, 0<=y<=1 1481 * where y is not at their lower bound. 1482 */ 1483 varstofix[dominatedidx] = FIXATLB; 1484 (*nfixings)++; 1485 } 1486 1487 if( varstofix[dominatingidx] == NOFIX && !SCIPisPositive(scip, SCIPvarGetObj(dominatingvar)) ) 1488 { 1489 /* we have a x->y dominance relation with a negative obj coefficient 1490 * of the dominating variable x. if the worst case upper bound is 1491 * greater equal than upper bound, we fix x at the upper bound 1492 */ 1493 if( !SCIPisInfinity(scip, dominatingwcub) && 1494 SCIPisGE(scip, dominatingwcub, SCIPvarGetUbGlobal(dominatingvar)) ) 1495 { 1496 varstofix[dominatingidx] = FIXATUB; 1497 (*nfixings)++; 1498 } 1499 } 1500 1501 if( varstofix[dominatingidx] == NOFIX && !SCIPisInfinity(scip, -dominatinglb) && 1502 SCIPisGE(scip, dominatinglb, SCIPvarGetUbGlobal(dominatingvar)) ) 1503 { 1504 /* we have a x->y dominance relation with an arbitrary obj coefficient 1505 * of the dominating variable x. if the predicted lower bound is greater 1506 * equal than upper bound, we fix x at the upper bound. 1507 */ 1508 varstofix[dominatingidx] = FIXATUB; 1509 (*nfixings)++; 1510 } 1511 1512 if( onlybinvars ) 1513 { 1514 if( varstofix[dominatedidx] == NOFIX && (onlyoneone || SCIPvarsHaveCommonClique(dominatingvar, TRUE, dominatedvar, TRUE, TRUE)) ) 1515 { 1516 /* We have a (1->1)-clique with dominance relation (x->y) (x dominates y). 1517 * From this dominance relation, we know (1->0) is possible and not worse than (0->1) 1518 * concerning the objective function. It follows that only (1->0) or (0->0) are possible, 1519 * but in both cases y has the value 0 => y=0. 1520 */ 1521 varstofix[dominatedidx] = FIXATLB; 1522 (*nfixings)++; 1523 } 1524 1525 if( varstofix[dominatingidx] == NOFIX && SCIPvarsHaveCommonClique(dominatingvar, FALSE, dominatedvar, FALSE, TRUE) ) 1526 { 1527 /* We have a (0->0)-clique with dominance relation x->y (x dominates y). 1528 * From this dominance relation, we know (1->0) is possible and not worse than (0->1) 1529 * concerning the objective function. It follows that only (1->0) or (1->1) are possible, 1530 * but in both cases x has the value 1 => x=1 1531 */ 1532 varstofix[dominatingidx] = FIXATUB; 1533 (*nfixings)++; 1534 } 1535 } 1536 else 1537 assert(!onlyoneone); 1538 1539 return SCIP_OKAY; 1540 } 1541 1542 /** find dominance relation between variable pairs */ 1543 static 1544 SCIP_RETCODE findDominancePairs( 1545 SCIP* scip, /**< SCIP main data structure */ 1546 SCIP_MATRIX* matrix, /**< matrix containing the constraints */ 1547 SCIP_PRESOLDATA* presoldata, /**< presolver data */ 1548 int* searchcols, /**< indexes of variables for pair comparisons */ 1549 int searchsize, /**< number of variables for pair comparisons */ 1550 SCIP_Bool onlybinvars, /**< flag indicating searchcols contains only binary variable indexes */ 1551 FIXINGDIRECTION* varstofix, /**< array holding information for later upper/lower bound fixing */ 1552 int* nfixings, /**< found number of possible fixings */ 1553 SCIP_Longint* ndomrelations, /**< found number of dominance relations */ 1554 int* nchgbds /**< number of changed bounds */ 1555 ) 1556 { 1557 SCIP_Real* vals1; 1558 SCIP_Real* vals2; 1559 SCIP_Real tmpupperbounddominatingcol1; 1560 SCIP_Real tmpupperbounddominatingcol2; 1561 SCIP_Real tmpwclowerbounddominatingcol1; 1562 SCIP_Real tmpwclowerbounddominatingcol2; 1563 SCIP_Real tmplowerbounddominatingcol1; 1564 SCIP_Real tmplowerbounddominatingcol2; 1565 SCIP_Real tmpwcupperbounddominatingcol1; 1566 SCIP_Real tmpwcupperbounddominatingcol2; 1567 int* rows1; 1568 int* rows2; 1569 int nrows1; 1570 int nrows2; 1571 SCIP_Real tmpupperbounddominatedcol1; 1572 SCIP_Real tmpupperbounddominatedcol2; 1573 SCIP_Real tmpwclowerbounddominatedcol1; 1574 SCIP_Real tmpwclowerbounddominatedcol2; 1575 SCIP_Real tmplowerbounddominatedcol1; 1576 SCIP_Real tmplowerbounddominatedcol2; 1577 SCIP_Real tmpwcupperbounddominatedcol1; 1578 SCIP_Real tmpwcupperbounddominatedcol2; 1579 SCIP_Real obj1; 1580 SCIP_Bool col1domcol2; 1581 SCIP_Bool col2domcol1; 1582 SCIP_Bool onlyoneone; 1583 int cnt1; 1584 int cnt2; 1585 int col1; 1586 int col2; 1587 int r1; 1588 int r2; 1589 int paircnt; 1590 int oldnfixings; 1591 1592 assert(scip != NULL); 1593 assert(matrix != NULL); 1594 assert(presoldata != NULL); 1595 assert(searchcols != NULL); 1596 assert(varstofix != NULL); 1597 assert(nfixings != NULL); 1598 assert(ndomrelations != NULL); 1599 assert(nchgbds != NULL); 1600 1601 paircnt = 0; 1602 oldnfixings = *nfixings; 1603 1604 /* pair comparisons */ 1605 for( cnt1 = 0; cnt1 < searchsize; cnt1++ ) 1606 { 1607 SCIP_VAR* varcol1; 1608 SCIP_VAR* varcol2; 1609 1610 /* get index of the first variable */ 1611 col1 = searchcols[cnt1]; 1612 1613 if( varstofix[col1] == FIXATLB ) 1614 continue; 1615 1616 varcol1 = SCIPmatrixGetVar(matrix, col1); 1617 obj1 = SCIPvarGetObj(varcol1); 1618 1619 for( cnt2 = cnt1+1; cnt2 < searchsize; cnt2++ ) 1620 { 1621 /* get index of the second variable */ 1622 col2 = searchcols[cnt2]; 1623 varcol2 = SCIPmatrixGetVar(matrix, col2); 1624 onlyoneone = FALSE; 1625 1626 /* we always have minimize as obj sense */ 1627 1628 /* column 1 dominating column 2 */ 1629 col1domcol2 = (obj1 <= SCIPvarGetObj(varcol2)); 1630 1631 /* column 2 dominating column 1 */ 1632 col2domcol1 = (SCIPvarGetObj(varcol2) <= obj1); 1633 1634 /* search only if nothing was found yet */ 1635 col1domcol2 = col1domcol2 && (varstofix[col2] == NOFIX); 1636 col2domcol1 = col2domcol1 && (varstofix[col1] == NOFIX); 1637 1638 /* we only search for a dominance relation if the lower bounds are not negative */ 1639 if( !onlybinvars ) 1640 { 1641 if( SCIPisLT(scip, SCIPvarGetLbGlobal(varcol1), 0.0) || 1642 SCIPisLT(scip, SCIPvarGetLbGlobal(varcol2), 0.0) ) 1643 { 1644 col1domcol2 = FALSE; 1645 col2domcol1 = FALSE; 1646 } 1647 } 1648 1649 /* pair comparison control */ 1650 if( paircnt == presoldata->numcurrentpairs ) 1651 { 1652 assert(*nfixings >= oldnfixings); 1653 if( *nfixings == oldnfixings ) 1654 { 1655 /* not enough fixings found, decrement number of comparisons */ 1656 presoldata->numcurrentpairs >>= 1; /*lint !e702*/ 1657 if( presoldata->numcurrentpairs < presoldata->numminpairs ) 1658 presoldata->numcurrentpairs = presoldata->numminpairs; 1659 1660 /* stop searching in this row */ 1661 return SCIP_OKAY; 1662 } 1663 oldnfixings = *nfixings; 1664 paircnt = 0; 1665 1666 /* increment number of comparisons */ 1667 presoldata->numcurrentpairs <<= 1; /*lint !e701*/ 1668 if( presoldata->numcurrentpairs > presoldata->nummaxpairs ) 1669 presoldata->numcurrentpairs = presoldata->nummaxpairs; 1670 } 1671 paircnt++; 1672 1673 if( !col1domcol2 && !col2domcol1 ) 1674 continue; 1675 1676 /* get the data for both columns */ 1677 vals1 = SCIPmatrixGetColValPtr(matrix, col1); 1678 rows1 = SCIPmatrixGetColIdxPtr(matrix, col1); 1679 nrows1 = SCIPmatrixGetColNNonzs(matrix, col1); 1680 r1 = 0; 1681 vals2 = SCIPmatrixGetColValPtr(matrix, col2); 1682 rows2 = SCIPmatrixGetColIdxPtr(matrix, col2); 1683 nrows2 = SCIPmatrixGetColNNonzs(matrix, col2); 1684 r2 = 0; 1685 1686 /* do we have a obj constant? */ 1687 if( nrows1 == 0 || nrows2 == 0 ) 1688 continue; 1689 1690 /* initialize temporary bounds of dominating variable */ 1691 tmpupperbounddominatingcol1 = SCIPinfinity(scip); 1692 tmpupperbounddominatingcol2 = tmpupperbounddominatingcol1; 1693 tmpwclowerbounddominatingcol1 = -SCIPinfinity(scip); 1694 tmpwclowerbounddominatingcol2 = tmpwclowerbounddominatingcol1; 1695 tmplowerbounddominatingcol1 = -SCIPinfinity(scip); 1696 tmplowerbounddominatingcol2 = tmplowerbounddominatingcol1; 1697 tmpwcupperbounddominatingcol1 = SCIPinfinity(scip); 1698 tmpwcupperbounddominatingcol2 = tmpwcupperbounddominatingcol1; 1699 1700 /* initialize temporary bounds of dominated variable */ 1701 tmpupperbounddominatedcol1 = SCIPinfinity(scip); 1702 tmpupperbounddominatedcol2 = tmpupperbounddominatedcol1; 1703 tmpwclowerbounddominatedcol1 = -SCIPinfinity(scip); 1704 tmpwclowerbounddominatedcol2 = tmpwclowerbounddominatedcol1; 1705 tmplowerbounddominatedcol1 = -SCIPinfinity(scip); 1706 tmplowerbounddominatedcol2 = tmplowerbounddominatedcol1; 1707 tmpwcupperbounddominatedcol1 = SCIPinfinity(scip); 1708 tmpwcupperbounddominatedcol2 = tmpwcupperbounddominatedcol1; 1709 1710 /* compare rows of this column pair */ 1711 while( (col1domcol2 || col2domcol1) && (r1 < nrows1 || r2 < nrows2) ) 1712 { 1713 assert((r1 >= nrows1-1) || (rows1[r1] < rows1[r1+1])); 1714 assert((r2 >= nrows2-1) || (rows2[r2] < rows2[r2+1])); 1715 1716 /* there is a nonredundant row containing column 1 but not column 2 */ 1717 if( r1 < nrows1 && (r2 == nrows2 || rows1[r1] < rows2[r2]) ) 1718 { 1719 /* dominance depends on the type of relation */ 1720 if( !SCIPmatrixIsRowRhsInfinity(matrix, rows1[r1]) ) 1721 { 1722 /* no dominance relation for equations or ranged rows */ 1723 col2domcol1 = FALSE; 1724 col1domcol2 = FALSE; 1725 } 1726 else 1727 { 1728 /* >= relation, larger coefficients dominate smaller ones */ 1729 if( vals1[r1] > 0.0 ) 1730 col2domcol1 = FALSE; 1731 else 1732 col1domcol2 = FALSE; 1733 } 1734 1735 r1++; 1736 } 1737 /* there is a nonredundant row containing column 2, but not column 1 */ 1738 else if( r2 < nrows2 && (r1 == nrows1 || rows1[r1] > rows2[r2]) ) 1739 { 1740 /* dominance depends on the type of relation */ 1741 if( !SCIPmatrixIsRowRhsInfinity(matrix, rows2[r2]) ) 1742 { 1743 /* no dominance relation for equations or ranged rows */ 1744 col2domcol1 = FALSE; 1745 col1domcol2 = FALSE; 1746 } 1747 else 1748 { 1749 /* >= relation, larger coefficients dominate smaller ones */ 1750 if( vals2[r2] < 0.0 ) 1751 col2domcol1 = FALSE; 1752 else 1753 col1domcol2 = FALSE; 1754 } 1755 1756 r2++; 1757 } 1758 /* if both columns appear in a common row, compare the coefficients */ 1759 else 1760 { 1761 assert(r1 < nrows1 && r2 < nrows2); 1762 assert(rows1[r1] == rows2[r2]); 1763 1764 /* if both columns are binary variables we check if they have a common clique 1765 * and do not calculate any bounds 1766 */ 1767 if( onlybinvars && !onlyoneone ) 1768 { 1769 if( vals1[r1] < 0 && vals2[r2] < 0 ) 1770 { 1771 if( (SCIPmatrixGetRowNMaxActPosInf(matrix, rows1[r1]) + SCIPmatrixGetRowNMaxActNegInf(matrix, rows1[r1]) == 0) 1772 && SCIPisFeasLE(scip, SCIPmatrixGetRowMaxActivity(matrix, rows1[r1]) + MAX(vals1[r1], vals2[r2]), 1773 SCIPmatrixGetRowLhs(matrix, rows1[r1])) ) 1774 { 1775 onlyoneone = TRUE; 1776 } 1777 } 1778 1779 if( !onlyoneone && !SCIPmatrixIsRowRhsInfinity(matrix, rows1[r1]) ) 1780 { 1781 if ( vals1[r1] > 0 && vals2[r2] > 0 ) 1782 { 1783 if( (SCIPmatrixGetRowNMinActPosInf(matrix, rows1[r1]) + SCIPmatrixGetRowNMinActNegInf(matrix, rows1[r1]) == 0) 1784 && SCIPisFeasGE(scip, SCIPmatrixGetRowMinActivity(matrix, rows1[r1]) + MIN(vals1[r1], vals2[r2]), 1785 SCIPmatrixGetRowRhs(matrix, rows1[r1])) ) 1786 { 1787 onlyoneone = TRUE; 1788 } 1789 } 1790 } 1791 1792 if( onlyoneone ) 1793 { 1794 /* reset bounds */ 1795 tmpupperbounddominatingcol1 = SCIPinfinity(scip); 1796 tmpupperbounddominatingcol2 = tmpupperbounddominatingcol1; 1797 tmpwclowerbounddominatingcol1 = -SCIPinfinity(scip); 1798 tmpwclowerbounddominatingcol2 = tmpwclowerbounddominatingcol1; 1799 tmplowerbounddominatingcol1 = -SCIPinfinity(scip); 1800 tmplowerbounddominatingcol2 = tmplowerbounddominatingcol1; 1801 tmpwcupperbounddominatingcol1 = SCIPinfinity(scip); 1802 tmpwcupperbounddominatingcol2 = tmpwcupperbounddominatingcol1; 1803 1804 tmpupperbounddominatedcol1 = SCIPinfinity(scip); 1805 tmpupperbounddominatedcol2 = tmpupperbounddominatedcol1; 1806 tmpwclowerbounddominatedcol1 = -SCIPinfinity(scip); 1807 tmpwclowerbounddominatedcol2 = tmpwclowerbounddominatedcol1; 1808 tmplowerbounddominatedcol1 = -SCIPinfinity(scip); 1809 tmplowerbounddominatedcol2 = tmplowerbounddominatedcol1; 1810 tmpwcupperbounddominatedcol1 = SCIPinfinity(scip); 1811 tmpwcupperbounddominatedcol2 = tmpwcupperbounddominatedcol1; 1812 } 1813 } 1814 1815 /* dominance depends on the type of inequality */ 1816 if( !SCIPmatrixIsRowRhsInfinity(matrix, rows1[r1]) ) 1817 { 1818 /* no dominance relation if coefficients differ for equations or ranged rows */ 1819 if( !SCIPisEQ(scip, vals1[r1], vals2[r2]) ) 1820 { 1821 col2domcol1 = FALSE; 1822 col1domcol2 = FALSE; 1823 } 1824 } 1825 else 1826 { 1827 /* >= relation, larger coefficients dominate smaller ones */ 1828 if( vals1[r1] > vals2[r2] ) 1829 col2domcol1 = FALSE; 1830 else if( vals1[r1] < vals2[r2] ) 1831 col1domcol2 = FALSE; 1832 } 1833 1834 /* we do not use bound calulations if two binary variable are in one common clique. 1835 * for the other cases we claim the same sign for the coefficients to 1836 * achieve monotonically decreasing predictive bound functions. 1837 */ 1838 if( !onlyoneone && 1839 ((vals1[r1] < 0 && vals2[r2] < 0) || (vals1[r1] > 0 && vals2[r2] > 0)) ) 1840 { 1841 if( col1domcol2 ) 1842 { 1843 /* update bounds of dominating variable for column 1 */ 1844 SCIP_CALL( updateBounds(scip, matrix, rows1[r1], 1845 col1, vals1[r1], col2, vals2[r2], TRUE, 1846 &tmpupperbounddominatingcol1, &tmpwclowerbounddominatingcol1, 1847 &tmplowerbounddominatingcol1, &tmpwcupperbounddominatingcol1) ); 1848 1849 /* update bounds of dominated variable for column 1 */ 1850 SCIP_CALL( updateBounds(scip, matrix, rows1[r1], 1851 col1, vals1[r1], col2, vals2[r2], FALSE, 1852 &tmpupperbounddominatedcol1, &tmpwclowerbounddominatedcol1, 1853 &tmplowerbounddominatedcol1, &tmpwcupperbounddominatedcol1) ); 1854 } 1855 1856 if( col2domcol1 ) 1857 { 1858 /* update bounds of dominating variable for column 2 */ 1859 SCIP_CALL( updateBounds(scip, matrix, rows2[r2], 1860 col2, vals2[r2], col1, vals1[r1], TRUE, 1861 &tmpupperbounddominatingcol2, &tmpwclowerbounddominatingcol2, 1862 &tmplowerbounddominatingcol2, &tmpwcupperbounddominatingcol2) ); 1863 1864 /* update bounds of dominated variable for column 2 */ 1865 SCIP_CALL( updateBounds(scip, matrix, rows2[r2], 1866 col2, vals2[r2], col1, vals1[r1], FALSE, 1867 &tmpupperbounddominatedcol2, &tmpwclowerbounddominatedcol2, 1868 &tmplowerbounddominatedcol2, &tmpwcupperbounddominatedcol2) ); 1869 } 1870 } 1871 1872 r1++; 1873 r2++; 1874 } 1875 } 1876 1877 /* a column is only dominated, if there are no more rows in which it is contained */ 1878 col1domcol2 = col1domcol2 && r2 == nrows2; 1879 col2domcol1 = col2domcol1 && r1 == nrows1; 1880 1881 if( !col1domcol2 && !col2domcol1 ) 1882 continue; 1883 1884 /* no dominance relation for left equations or ranged rows */ 1885 while( r1 < nrows1 ) 1886 { 1887 if( !SCIPmatrixIsRowRhsInfinity(matrix, rows1[r1]) ) 1888 { 1889 col2domcol1 = FALSE; 1890 col1domcol2 = FALSE; 1891 break; 1892 } 1893 r1++; 1894 } 1895 if( !col1domcol2 && !col2domcol1 ) 1896 continue; 1897 while( r2 < nrows2 ) 1898 { 1899 if( !SCIPmatrixIsRowRhsInfinity(matrix, rows2[r2]) ) 1900 { 1901 col2domcol1 = FALSE; 1902 col1domcol2 = FALSE; 1903 break; 1904 } 1905 r2++; 1906 } 1907 1908 if( col1domcol2 || col2domcol1 ) 1909 (*ndomrelations)++; 1910 1911 if( col1domcol2 && col2domcol1 ) 1912 { 1913 /* prefer the variable as dominating variable with the greater upper bound */ 1914 if( SCIPisGE(scip, SCIPvarGetUbGlobal(varcol1), SCIPvarGetUbGlobal(varcol2)) ) 1915 col2domcol1 = FALSE; 1916 else 1917 col1domcol2 = FALSE; 1918 } 1919 1920 /* use dominance relation and clique/bound-information 1921 * to find variable fixings. additionally try to strengthen 1922 * variable bounds by predictive bound strengthening. 1923 */ 1924 if( col1domcol2 ) 1925 { 1926 SCIP_CALL( findFixings(scip, matrix, varcol1, col1, 1927 tmpupperbounddominatingcol1, tmpwclowerbounddominatingcol1, 1928 tmplowerbounddominatingcol1, tmpwcupperbounddominatingcol1, 1929 varcol2, col2, 1930 varstofix, onlybinvars, onlyoneone, nfixings) ); 1931 1932 if( presoldata->predbndstr ) 1933 { 1934 SCIP_CALL( predBndStr(scip, varcol1, col1, 1935 tmpupperbounddominatingcol1, 1936 tmplowerbounddominatingcol1, tmpwcupperbounddominatingcol1, 1937 varcol2, col2, 1938 tmpupperbounddominatedcol1, tmpwclowerbounddominatedcol1, 1939 tmplowerbounddominatedcol1, 1940 varstofix, nchgbds) ); 1941 } 1942 } 1943 else if( col2domcol1 ) 1944 { 1945 SCIP_CALL( findFixings(scip, matrix, varcol2, col2, 1946 tmpupperbounddominatingcol2, tmpwclowerbounddominatingcol2, 1947 tmplowerbounddominatingcol2, tmpwcupperbounddominatingcol2, 1948 varcol1, col1, 1949 varstofix, onlybinvars, onlyoneone, nfixings) ); 1950 1951 if( presoldata->predbndstr ) 1952 { 1953 SCIP_CALL( predBndStr(scip, varcol2, col2, 1954 tmpupperbounddominatingcol2, 1955 tmplowerbounddominatingcol2, tmpwcupperbounddominatingcol2, 1956 varcol1, col1, 1957 tmpupperbounddominatedcol2, tmpwclowerbounddominatedcol2, 1958 tmplowerbounddominatedcol2, 1959 varstofix, nchgbds) ); 1960 } 1961 } 1962 if( varstofix[col1] == FIXATLB ) 1963 break; 1964 } 1965 } 1966 1967 return SCIP_OKAY; 1968 } 1969 1970 1971 /* 1972 * Callback methods of presolver 1973 */ 1974 1975 1976 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 1977 static 1978 SCIP_DECL_PRESOLCOPY(presolCopyDomcol) 1979 { /*lint --e{715}*/ 1980 assert(scip != NULL); 1981 assert(presol != NULL); 1982 assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0); 1983 1984 /* call inclusion method of presolver */ 1985 SCIP_CALL( SCIPincludePresolDomcol(scip) ); 1986 1987 return SCIP_OKAY; 1988 } 1989 1990 /** destructor of presolver to free user data (called when SCIP is exiting) */ 1991 static 1992 SCIP_DECL_PRESOLFREE(presolFreeDomcol) 1993 { /*lint --e{715}*/ 1994 SCIP_PRESOLDATA* presoldata; 1995 1996 /* free presolver data */ 1997 presoldata = SCIPpresolGetData(presol); 1998 assert(presoldata != NULL); 1999 2000 SCIPfreeBlockMemory(scip, &presoldata); 2001 SCIPpresolSetData(presol, NULL); 2002 2003 return SCIP_OKAY; 2004 } 2005 2006 /** execution method of presolver */ 2007 static 2008 SCIP_DECL_PRESOLEXEC(presolExecDomcol) 2009 { /*lint --e{715}*/ 2010 SCIP_PRESOLDATA* presoldata; 2011 SCIP_MATRIX* matrix; 2012 SCIP_Bool initialized; 2013 SCIP_Bool complete; 2014 SCIP_Bool infeasible; 2015 int nfixings; 2016 SCIP_Longint ndomrelations; 2017 int v; 2018 int r; 2019 FIXINGDIRECTION* varstofix; 2020 SCIP_Bool* varsprocessed; 2021 int nrows; 2022 int ncols; 2023 int* rowidxsorted; 2024 int* rowsparsity; 2025 int varcount; 2026 int* consearchcols; 2027 int* intsearchcols; 2028 int* binsearchcols; 2029 int nconfill; 2030 int nintfill; 2031 int nbinfill; 2032 #ifdef SCIP_DEBUG 2033 int nconvarsfixed = 0; 2034 int nintvarsfixed = 0; 2035 int nbinvarsfixed = 0; 2036 #endif 2037 int* pclass; 2038 int* colidx; 2039 int pclassstart; 2040 int pc; 2041 SCIP_Bool* varineq; 2042 2043 assert(result != NULL); 2044 *result = SCIP_DIDNOTRUN; 2045 2046 if( !SCIPallowStrongDualReds(scip) || SCIPisStopped(scip) ) 2047 return SCIP_OKAY; 2048 2049 presoldata = SCIPpresolGetData(presol); 2050 assert(presoldata != NULL); 2051 2052 /* don't run for pure LPs */ 2053 if( !presoldata->continuousred && (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) == 0) ) 2054 return SCIP_OKAY; 2055 2056 *result = SCIP_DIDNOTFIND; 2057 2058 matrix = NULL; 2059 SCIP_CALL( SCIPmatrixCreate(scip, &matrix, TRUE, &initialized, &complete, &infeasible, 2060 naddconss, ndelconss, nchgcoefs, nchgbds, nfixedvars) ); 2061 2062 /* if infeasibility was detected during matrix creation, return here */ 2063 if( infeasible ) 2064 { 2065 if( initialized ) 2066 SCIPmatrixFree(scip, &matrix); 2067 2068 *result = SCIP_CUTOFF; 2069 return SCIP_OKAY; 2070 } 2071 2072 if( !initialized ) 2073 return SCIP_OKAY; 2074 2075 nfixings = 0; 2076 ndomrelations = 0; 2077 nrows = SCIPmatrixGetNRows(matrix); 2078 ncols = SCIPmatrixGetNColumns(matrix); 2079 assert(SCIPgetNVars(scip) == ncols); 2080 2081 SCIP_CALL( SCIPallocBufferArray(scip, &varstofix, ncols) ); 2082 BMSclearMemoryArray(varstofix, ncols); 2083 2084 SCIP_CALL( SCIPallocBufferArray(scip, &varsprocessed, ncols) ); 2085 2086 /* do not process columns that do not have all locks represented in the matrix */ 2087 for( v = 0; v < ncols; ++v ) 2088 varsprocessed[v] = SCIPmatrixUplockConflict(matrix, v) || SCIPmatrixDownlockConflict(matrix, v); 2089 2090 SCIP_CALL( SCIPallocBufferArray(scip, &consearchcols, ncols) ); 2091 SCIP_CALL( SCIPallocBufferArray(scip, &intsearchcols, ncols) ); 2092 SCIP_CALL( SCIPallocBufferArray(scip, &binsearchcols, ncols) ); 2093 2094 SCIP_CALL( SCIPallocBufferArray(scip, &rowidxsorted, nrows) ); 2095 SCIP_CALL( SCIPallocBufferArray(scip, &rowsparsity, nrows) ); 2096 for( r = 0; r < nrows; ++r ) 2097 { 2098 rowidxsorted[r] = r; 2099 rowsparsity[r] = SCIPmatrixGetRowNNonzs(matrix, r); 2100 } 2101 2102 SCIP_CALL( SCIPallocBufferArray(scip, &pclass, ncols) ); 2103 SCIP_CALL( SCIPallocBufferArray(scip, &colidx, ncols) ); 2104 SCIP_CALL( SCIPallocBufferArray(scip, &varineq, ncols) ); 2105 for( v = 0; v < ncols; v++ ) 2106 { 2107 colidx[v] = v; 2108 varineq[v] = FALSE; 2109 } 2110 2111 /* init pair comparision control */ 2112 presoldata->numcurrentpairs = presoldata->nummaxpairs; 2113 2114 varcount = 0; 2115 2116 /* 1.stage: search dominance relations of parallel columns 2117 * within equalities and ranged rows 2118 */ 2119 if( (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 ) 2120 { 2121 SCIP_CALL( detectParallelCols(scip, matrix, pclass, varineq) ); 2122 SCIPsortIntInt(pclass, colidx, ncols); 2123 2124 pc = 0; 2125 while( pc < ncols ) 2126 { 2127 int varidx; 2128 2129 varidx = 0; 2130 nconfill = 0; 2131 nintfill = 0; 2132 nbinfill = 0; 2133 2134 pclassstart = pclass[pc]; 2135 while( pc < ncols && pclassstart == pclass[pc] ) 2136 { 2137 SCIP_VAR* var; 2138 2139 varidx = colidx[pc]; 2140 var = SCIPmatrixGetVar(matrix, varidx); 2141 2142 /* we only regard variables which were not processed yet and 2143 * are present within equalities or ranged rows 2144 */ 2145 if( !varsprocessed[varidx] && varineq[varidx] ) 2146 { 2147 /* we search only for dominance relations between the same variable type */ 2148 if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS ) 2149 { 2150 consearchcols[nconfill++] = varidx; 2151 } 2152 else if( SCIPvarIsBinary(var) ) 2153 { 2154 binsearchcols[nbinfill++] = varidx; 2155 } 2156 else 2157 { 2158 assert(SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER || SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT); 2159 intsearchcols[nintfill++] = varidx; 2160 } 2161 } 2162 ++pc; 2163 } 2164 2165 /* continuous variables */ 2166 if( nconfill > 1 && presoldata->continuousred ) 2167 { 2168 SCIP_CALL( findDominancePairs(scip, matrix, presoldata, consearchcols, nconfill, FALSE, 2169 varstofix, &nfixings, &ndomrelations, nchgbds) ); 2170 2171 for( v = 0; v < nconfill; ++v ) 2172 varsprocessed[consearchcols[v]] = TRUE; 2173 2174 varcount += nconfill; 2175 } 2176 else if( nconfill == 1 ) 2177 { 2178 if( varineq[varidx] ) 2179 varsprocessed[consearchcols[0]] = TRUE; 2180 } 2181 2182 /* integer and impl-integer variables */ 2183 if( nintfill > 1 ) 2184 { 2185 SCIP_CALL( findDominancePairs(scip, matrix, presoldata, intsearchcols, nintfill, FALSE, 2186 varstofix, &nfixings, &ndomrelations, nchgbds) ); 2187 2188 for( v = 0; v < nintfill; ++v ) 2189 varsprocessed[intsearchcols[v]] = TRUE; 2190 2191 varcount += nintfill; 2192 } 2193 else if( nintfill == 1 ) 2194 { 2195 if( varineq[varidx] ) 2196 varsprocessed[intsearchcols[0]] = TRUE; 2197 } 2198 2199 /* binary variables */ 2200 if( nbinfill > 1 ) 2201 { 2202 SCIP_CALL( findDominancePairs(scip, matrix, presoldata, binsearchcols, nbinfill, TRUE, 2203 varstofix, &nfixings, &ndomrelations, nchgbds) ); 2204 2205 for( v = 0; v < nbinfill; ++v ) 2206 varsprocessed[binsearchcols[v]] = TRUE; 2207 2208 varcount += nbinfill; 2209 } 2210 else if( nbinfill == 1 ) 2211 { 2212 if( varineq[varidx] ) 2213 varsprocessed[binsearchcols[0]] = TRUE; 2214 } 2215 2216 if( varcount >= ncols ) 2217 break; 2218 } 2219 } 2220 2221 /* 2.stage: search dominance relations for the remaining columns 2222 * by increasing row-sparsity 2223 */ 2224 if( (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 ) 2225 { 2226 SCIPsortIntInt(rowsparsity, rowidxsorted, nrows); 2227 2228 for( r = 0; r < nrows; ++r ) 2229 { 2230 int rowidx; 2231 int* rowpnt; 2232 int* rowend; 2233 2234 /* break if the time limit was reached; since the check is expensive, 2235 * we only check all 1000 constraints 2236 */ 2237 if( (r % 1000 == 0) && SCIPisStopped(scip) ) 2238 break; 2239 2240 rowidx = rowidxsorted[r]; 2241 rowpnt = SCIPmatrixGetRowIdxPtr(matrix, rowidx); 2242 rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, rowidx); 2243 2244 if( SCIPmatrixGetRowNNonzs(matrix, rowidx) == 1 ) 2245 continue; 2246 2247 nconfill = 0; 2248 nintfill = 0; 2249 nbinfill = 0; 2250 2251 for( ; rowpnt < rowend; rowpnt++ ) 2252 { 2253 if( !(varsprocessed[*rowpnt]) ) 2254 { 2255 int varidx; 2256 SCIP_VAR* var; 2257 2258 varidx = *rowpnt; 2259 var = SCIPmatrixGetVar(matrix, varidx); 2260 2261 /* we search only for dominance relations between the same variable type */ 2262 if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS ) 2263 { 2264 consearchcols[nconfill++] = varidx; 2265 } 2266 else if( SCIPvarIsBinary(var) ) 2267 { 2268 binsearchcols[nbinfill++] = varidx; 2269 } 2270 else 2271 { 2272 assert(SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER || SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT); 2273 intsearchcols[nintfill++] = varidx; 2274 } 2275 } 2276 } 2277 2278 /* continuous variables */ 2279 if( nconfill > 1 && presoldata->continuousred ) 2280 { 2281 SCIP_CALL( findDominancePairs(scip, matrix, presoldata, consearchcols, nconfill, FALSE, 2282 varstofix, &nfixings, &ndomrelations, nchgbds) ); 2283 2284 for( v = 0; v < nconfill; ++v ) 2285 varsprocessed[consearchcols[v]] = TRUE; 2286 2287 varcount += nconfill; 2288 } 2289 2290 /* integer and impl-integer variables */ 2291 if( nintfill > 1 ) 2292 { 2293 SCIP_CALL( findDominancePairs(scip, matrix, presoldata, intsearchcols, nintfill, FALSE, 2294 varstofix, &nfixings, &ndomrelations, nchgbds) ); 2295 2296 for( v = 0; v < nintfill; ++v ) 2297 varsprocessed[intsearchcols[v]] = TRUE; 2298 2299 varcount += nintfill; 2300 } 2301 2302 /* binary variables */ 2303 if( nbinfill > 1 ) 2304 { 2305 SCIP_CALL( findDominancePairs(scip, matrix, presoldata, binsearchcols, nbinfill, TRUE, 2306 varstofix, &nfixings, &ndomrelations, nchgbds) ); 2307 2308 for( v = 0; v < nbinfill; ++v ) 2309 varsprocessed[binsearchcols[v]] = TRUE; 2310 2311 varcount += nbinfill; 2312 } 2313 2314 if( varcount >= ncols ) 2315 break; 2316 } 2317 } 2318 2319 if( nfixings > 0 ) 2320 { 2321 int oldnfixedvars; 2322 2323 oldnfixedvars = *nfixedvars; 2324 2325 for( v = ncols - 1; v >= 0; --v ) 2326 { 2327 SCIP_Bool fixed; 2328 SCIP_VAR* var; 2329 2330 var = SCIPmatrixGetVar(matrix,v); 2331 2332 /* there should be no fixings for variables with lock conflicts, 2333 * since they where marked as processed and therefore should be skipped 2334 */ 2335 assert(varstofix[v] == NOFIX || (!SCIPmatrixUplockConflict(matrix, v) && !SCIPmatrixDownlockConflict(matrix, v)) ); 2336 2337 if( varstofix[v] == FIXATLB ) 2338 { 2339 SCIP_Real lb; 2340 2341 lb = SCIPvarGetLbGlobal(var); 2342 assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || SCIPisFeasIntegral(scip, lb)); 2343 2344 /* fix at lower bound */ 2345 SCIP_CALL( SCIPfixVar(scip, var, lb, &infeasible, &fixed) ); 2346 if( infeasible ) 2347 { 2348 SCIPdebugMsg(scip, " -> infeasible fixing\n"); 2349 *result = SCIP_CUTOFF; 2350 2351 break; 2352 } 2353 assert(fixed); 2354 (*nfixedvars)++; 2355 2356 #ifdef SCIP_DEBUG 2357 if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS ) 2358 nconvarsfixed++; 2359 else if( SCIPvarIsBinary(var) ) 2360 nbinvarsfixed++; 2361 else 2362 nintvarsfixed++; 2363 #endif 2364 } 2365 else if( varstofix[v] == FIXATUB ) 2366 { 2367 SCIP_Real ub; 2368 2369 ub = SCIPvarGetUbGlobal(var); 2370 assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || SCIPisFeasIntegral(scip, ub)); 2371 2372 /* fix at upper bound */ 2373 SCIP_CALL( SCIPfixVar(scip, var, ub, &infeasible, &fixed) ); 2374 if( infeasible ) 2375 { 2376 SCIPdebugMsg(scip, " -> infeasible fixing\n"); 2377 *result = SCIP_CUTOFF; 2378 2379 break; 2380 } 2381 assert(fixed); 2382 (*nfixedvars)++; 2383 2384 #ifdef SCIP_DEBUG 2385 if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS ) 2386 nconvarsfixed++; 2387 else if( SCIPvarIsBinary(var) ) 2388 nbinvarsfixed++; 2389 else 2390 nintvarsfixed++; 2391 #endif 2392 } 2393 } 2394 2395 if( *result != SCIP_CUTOFF && *nfixedvars > oldnfixedvars ) 2396 *result = SCIP_SUCCESS; 2397 } 2398 2399 SCIPfreeBufferArray(scip, &varineq); 2400 SCIPfreeBufferArray(scip, &colidx); 2401 SCIPfreeBufferArray(scip, &pclass); 2402 SCIPfreeBufferArray(scip, &rowsparsity); 2403 SCIPfreeBufferArray(scip, &rowidxsorted); 2404 SCIPfreeBufferArray(scip, &binsearchcols); 2405 SCIPfreeBufferArray(scip, &intsearchcols); 2406 SCIPfreeBufferArray(scip, &consearchcols); 2407 SCIPfreeBufferArray(scip, &varsprocessed); 2408 SCIPfreeBufferArray(scip, &varstofix); 2409 2410 #ifdef SCIP_DEBUG 2411 if( (nconvarsfixed + nintvarsfixed + nbinvarsfixed) > 0 ) 2412 { 2413 SCIPdebugMsg(scip, "### %d vars [%" SCIP_LONGINT_FORMAT " dom] => fixed [cont: %d, int: %d, bin: %d], %scutoff detected\n", 2414 ncols, ndomrelations, nconvarsfixed, nintvarsfixed, nbinvarsfixed, (*result != SCIP_CUTOFF) ? "no " : ""); 2415 } 2416 #endif 2417 2418 SCIPmatrixFree(scip, &matrix); 2419 2420 return SCIP_OKAY; 2421 } 2422 2423 /* 2424 * presolver specific interface methods 2425 */ 2426 2427 /** creates the domcol presolver and includes it in SCIP */ 2428 SCIP_RETCODE SCIPincludePresolDomcol( 2429 SCIP* scip /**< SCIP data structure */ 2430 ) 2431 { 2432 SCIP_PRESOLDATA* presoldata; 2433 SCIP_PRESOL* presol; 2434 2435 /* create domcol presolver data */ 2436 SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) ); 2437 2438 /* include presolver */ 2439 SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS, 2440 PRESOL_TIMING, presolExecDomcol, presoldata) ); 2441 SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyDomcol) ); 2442 SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeDomcol) ); 2443 2444 SCIP_CALL( SCIPaddIntParam(scip, 2445 "presolving/domcol/numminpairs", 2446 "minimal number of pair comparisons", 2447 &presoldata->numminpairs, FALSE, DEFAULT_NUMMINPAIRS, 100, DEFAULT_NUMMAXPAIRS, NULL, NULL) ); 2448 2449 SCIP_CALL( SCIPaddIntParam(scip, 2450 "presolving/domcol/nummaxpairs", 2451 "maximal number of pair comparisons", 2452 &presoldata->nummaxpairs, FALSE, DEFAULT_NUMMAXPAIRS, DEFAULT_NUMMINPAIRS, 1000000000, NULL, NULL) ); 2453 2454 SCIP_CALL( SCIPaddBoolParam(scip, 2455 "presolving/domcol/predbndstr", 2456 "should predictive bound strengthening be applied?", 2457 &presoldata->predbndstr, FALSE, DEFAULT_PREDBNDSTR, NULL, NULL) ); 2458 2459 SCIP_CALL( SCIPaddBoolParam(scip, 2460 "presolving/domcol/continuousred", 2461 "should reductions for continuous variables be performed?", 2462 &presoldata->continuousred, FALSE, DEFAULT_CONTINUOUS_RED, NULL, NULL) ); 2463 2464 return SCIP_OKAY; 2465 } 2466