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_dualcomp.c 26 * @ingroup DEFPLUGINS_PRESOL 27 * @brief dual compensation presolver 28 * @author Dieter Weninger 29 * 30 * This presolver looks for variables with 31 * i) objcoef >= 0 and exactly one downlock 32 * ii) objcoef <= 0 and exactly one uplock 33 * and fixes the variable in case i) at the lower bound and in case ii) at the 34 * upper bound if a combination of singleton continuous variables can compensate 35 * the downlock in case i) and the uplock in case ii). 36 */ 37 38 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 39 40 #include "blockmemshell/memory.h" 41 #include "scip/presol_dualcomp.h" 42 #include "scip/pub_matrix.h" 43 #include "scip/pub_message.h" 44 #include "scip/pub_presol.h" 45 #include "scip/pub_var.h" 46 #include "scip/scip_general.h" 47 #include "scip/scip_mem.h" 48 #include "scip/scip_message.h" 49 #include "scip/scip_nlp.h" 50 #include "scip/scip_numerics.h" 51 #include "scip/scip_param.h" 52 #include "scip/scip_presol.h" 53 #include "scip/scip_pricer.h" 54 #include "scip/scip_prob.h" 55 #include "scip/scip_probing.h" 56 #include "scip/scip_var.h" 57 #include <string.h> 58 59 #define PRESOL_NAME "dualcomp" 60 #define PRESOL_DESC "compensate single up-/downlocks by singleton continuous variables" 61 62 /* we need singleton continuous variables for the lock compensation, 63 * thus it is presumably a good idea to call this presolver before stuffing, which 64 * fixes singleton continuous variables 65 */ 66 #define PRESOL_PRIORITY -50 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */ 67 #define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */ 68 #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ 69 70 #define DEFAULT_COMP_ONLY_DIS_VARS FALSE /**< should only discrete variables be compensated? */ 71 72 /* 73 * Data structures 74 */ 75 76 /** control parameters */ 77 struct SCIP_PresolData 78 { 79 SCIP_Bool componlydisvars; /**< flag indicating if only discrete variables should be compensated */ 80 }; 81 82 /** type of fixing direction */ 83 enum Fixingdirection 84 { 85 FIXATLB = -1, /**< fix variable at lower bound */ 86 NOFIX = 0, /**< do not fix variable */ 87 FIXATUB = 1 /**< fix variable at upper bound */ 88 }; 89 typedef enum Fixingdirection FIXINGDIRECTION; 90 91 /** type of variable lock compensation */ 92 enum Lockcompensation 93 { 94 COMPENSATE_DOWNLOCK = 0, 95 COMPENSATE_UPLOCK = 1 96 }; 97 typedef enum Lockcompensation LOCKCOMPENSATION; 98 99 /* 100 * Local methods 101 */ 102 103 /** try to compensate a variable with a single opposite lock 104 by using singleton continuous variables */ 105 static 106 SCIP_RETCODE compensateVarLock( 107 SCIP* scip, /**< SCIP main data structure */ 108 SCIP_MATRIX* matrix, /**< matrix containing the constraints */ 109 int col, /**< variable fixing candidate */ 110 int row, /**< row index with opposite lock */ 111 SCIP_Real val, /**< value of fixing candidate in the opposite lock constraint */ 112 SCIP_Bool twosides, /**< flag indicating that two sides are present */ 113 LOCKCOMPENSATION compensation, /**< type of lock compensation */ 114 FIXINGDIRECTION* varstofix, /**< array holding fixing information */ 115 int* nfixings /**< number of possible fixings */ 116 ) 117 { 118 SCIP_Real* valpnt; 119 int* rowpnt; 120 int* rowend; 121 SCIP_VAR* var; 122 int colidx; 123 SCIP_Real coef; 124 SCIP_Real lhs; 125 SCIP_Real delta; 126 SCIP_Bool trytofix; 127 SCIP_Real lb; 128 SCIP_Real ub; 129 SCIP_Bool deltaisinf; 130 SCIP_Real ratio; 131 SCIP_Bool multrowbyminusone; 132 SCIP_Bool singleton; 133 SCIP_Real offset; 134 135 assert(scip != NULL); 136 assert(matrix != NULL); 137 assert(0 <= col && col < SCIPmatrixGetNColumns(matrix)); 138 assert(0 <= row && row < SCIPmatrixGetNRows(matrix)); 139 assert(compensation == COMPENSATE_DOWNLOCK || compensation == COMPENSATE_UPLOCK); 140 assert(varstofix != NULL); 141 assert(nfixings != NULL); 142 143 /* the variable for compensation should not be a compensation variable itself */ 144 assert(!(SCIPmatrixGetColNNonzs(matrix,col) == 1 && SCIPvarGetType(SCIPmatrixGetVar(matrix,col)) == SCIP_VARTYPE_CONTINUOUS)); 145 146 /* try lock compensation only if minimum one singleton continuous variable is present */ 147 singleton = FALSE; 148 rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row); 149 rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row); 150 for( ; rowpnt < rowend; rowpnt++ ) 151 { 152 var = SCIPmatrixGetVar(matrix, *rowpnt); 153 154 if( SCIPmatrixGetColNNonzs(matrix, *rowpnt) == 1 && 155 SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS && 156 SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == SCIPmatrixGetColNUplocks(matrix, *rowpnt) && 157 SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == SCIPmatrixGetColNDownlocks(matrix, *rowpnt) 158 ) 159 { 160 /* minimal one valid compensation variable is present in this row */ 161 singleton = TRUE; 162 break; 163 } 164 } 165 166 /* return if no compensation variable is available */ 167 if( !singleton ) 168 return SCIP_OKAY; 169 170 /* we perform the following transformations afterwards: 171 * 172 * lhs <= a1 x1 + a2 x2 + ... an xn <= rhs 173 * with a1, a2, ..., an >= 0. 174 * 175 * for the downlock case we multiply the constraint in thought by (-1) 176 * if the corresponding coefficient is negative. 177 * 178 * we attribute the uplock case to the downlock case by multiplying 179 * in thought the corresponding column by (-1). 180 */ 181 multrowbyminusone = FALSE; 182 if( compensation == COMPENSATE_DOWNLOCK ) 183 { 184 if( SCIPisLT(scip,val,0.0) ) 185 multrowbyminusone = TRUE; 186 } 187 else 188 { 189 assert(compensation == COMPENSATE_UPLOCK); 190 191 /* in the uplock case we multiply the column in thought by (-1) and 192 * thus we need to multiply the constraint by (-1) to get a positive coefficient 193 */ 194 if( SCIPisGT(scip,val,0.0) ) 195 multrowbyminusone = TRUE; 196 } 197 198 /* we need the objective coefficient and constraint coefficient ratio 199 * to later preserve optimality. 200 * further we need to consider multiplications of the constraint by (-1). 201 * for ranged rows and equalities we switch to the rhs. 202 */ 203 lhs = SCIPmatrixGetRowLhs(matrix, row); 204 ratio = SCIPvarGetObj( SCIPmatrixGetVar(matrix,col) ) / val; 205 if( multrowbyminusone ) 206 { 207 if( twosides ) 208 lhs = -SCIPmatrixGetRowRhs(matrix, row); 209 else 210 lhs = -lhs; 211 212 ratio = -ratio; 213 } 214 215 offset = 0.0; 216 trytofix = TRUE; 217 delta = 0; 218 deltaisinf = FALSE; 219 220 rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row); 221 rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row); 222 valpnt = SCIPmatrixGetRowValPtr(matrix, row); 223 224 for( ; rowpnt < rowend; rowpnt++, valpnt++ ) 225 { 226 colidx = *rowpnt; 227 coef = *valpnt; 228 var = SCIPmatrixGetVar(matrix, colidx); 229 lb = SCIPvarGetLbGlobal(var); 230 ub = SCIPvarGetUbGlobal(var); 231 232 if( colidx == col ) 233 { 234 /* this is the variable which we want to compensate */ 235 236 if( compensation == COMPENSATE_DOWNLOCK ) 237 { 238 if( SCIPisInfinity(scip, -lb) ) 239 { 240 trytofix = FALSE; 241 break; 242 } 243 else 244 { 245 if( multrowbyminusone ) 246 offset += (-coef) * lb; 247 else 248 offset += coef * lb; 249 } 250 } 251 else 252 { 253 if( SCIPisInfinity(scip, ub) ) 254 { 255 trytofix = FALSE; 256 break; 257 } 258 else 259 { 260 /* for the uplock case we have opposed sign for the coefficient as 261 * in the downlock case. 262 * the multiplication of the column results in swapping the negative bounds. 263 */ 264 if( multrowbyminusone ) 265 offset += coef * (-ub); 266 else 267 offset += (-coef) * (-ub); 268 } 269 } 270 } 271 else if( SCIPmatrixGetColNNonzs(matrix, colidx) == 1 && 272 SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == SCIPmatrixGetColNUplocks(matrix, colidx) && 273 SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == SCIPmatrixGetColNDownlocks(matrix, colidx) && 274 SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS ) 275 { 276 /* this is singleton continuous variable and 277 * thus a valid compensation candidate 278 */ 279 280 if( SCIPisLT(scip,coef,0.0) ) 281 { 282 /* coef < 0 */ 283 284 if( multrowbyminusone ) 285 { 286 if( SCIPisInfinity(scip, -lb) ) 287 { 288 trytofix = FALSE; 289 break; 290 } 291 292 /* we have a negative coefficient and the row is multiplied by (-1) 293 * thus actually we have a positive coefficient 294 */ 295 offset += (-coef) * lb; 296 297 /* only consider singleton continuous variables with a better or the same 298 * obj/coef ratio for preserving optimality 299 */ 300 if( SCIPisLE(scip,SCIPvarGetObj(SCIPmatrixGetVar(matrix, colidx))/(-coef), ratio) ) 301 { 302 if( SCIPisInfinity(scip, ub) ) 303 { 304 deltaisinf = TRUE; 305 break; 306 } 307 308 /* calculate the contribution to the compensation value */ 309 delta += (-coef) * (ub - lb); 310 } 311 } 312 else 313 { 314 if( SCIPisInfinity(scip, ub) ) 315 { 316 trytofix = FALSE; 317 break; 318 } 319 320 /* we have a negative coefficient and hence need to multiply the column by (-1). 321 * this means the bounds swap and change the sign 322 */ 323 offset += (-coef) * (-ub); 324 325 /* only consider singleton continuous variables with a better or the same 326 * obj/coef ratio for preserving optimality 327 */ 328 if( SCIPisLE(scip,SCIPvarGetObj(SCIPmatrixGetVar(matrix, colidx))/coef, ratio) ) 329 { 330 if( SCIPisInfinity(scip, -lb) ) 331 { 332 deltaisinf = TRUE; 333 break; 334 } 335 336 /* calculate the contribution to the compensation value */ 337 delta += (-coef) * (ub - lb); 338 } 339 } 340 } 341 else 342 { 343 /* coef >= 0 */ 344 345 if( multrowbyminusone ) 346 { 347 /* we have a positive or zero coefficient and the row is multiplied by (-1) */ 348 if( SCIPisInfinity(scip, ub) ) 349 { 350 trytofix = FALSE; 351 break; 352 } 353 354 /* we have a positive or zero coefficient and multiply in thought the constraint 355 * by (-1) thus we have actually a negative coefficient and multiply the column by (-1). 356 * therefore the sign of the coefficient does not change but the bounds swap and change 357 * the sign. 358 */ 359 offset += coef * (-ub); 360 361 /* we have a positive or zero coefficient and multiply in thought the constraint 362 * by (-1) which delivers the ratio. 363 * a further multiplication of the column does not change anything. 364 */ 365 if( SCIPisLE(scip,SCIPvarGetObj(SCIPmatrixGetVar(matrix, colidx))/(-coef), ratio) ) 366 { 367 if( SCIPisInfinity(scip, -lb) ) 368 { 369 deltaisinf = TRUE; 370 break; 371 } 372 373 /* calculate the contribution to the compensation value */ 374 delta += coef * (ub - lb); 375 } 376 } 377 else 378 { 379 if( SCIPisInfinity(scip, -lb) ) 380 { 381 trytofix = FALSE; 382 break; 383 } 384 385 /* we have positive coefficient and do not need to multiply anything by (-1) */ 386 offset += coef * lb; 387 388 if( SCIPisLE(scip,SCIPvarGetObj(SCIPmatrixGetVar(matrix, colidx))/coef, ratio) ) 389 { 390 if( SCIPisInfinity(scip, ub) ) 391 { 392 deltaisinf = TRUE; 393 break; 394 } 395 396 /* calculate the contribution to the compensation value */ 397 delta += coef * (ub - lb); 398 } 399 } 400 } 401 } 402 else 403 { 404 /* remaining variables */ 405 406 /* the reasons for the following signs are the same as for the singleton 407 * continuous variables 408 */ 409 if( SCIPisLT(scip,coef,0.0) ) 410 { 411 if( multrowbyminusone ) 412 { 413 if( SCIPisInfinity(scip, -lb) ) 414 { 415 trytofix = FALSE; 416 break; 417 } 418 419 offset += (-coef) * lb; 420 } 421 else 422 { 423 if( SCIPisInfinity(scip, ub) ) 424 { 425 trytofix = FALSE; 426 break; 427 } 428 429 offset += (-coef) * (-ub); 430 } 431 } 432 else 433 { 434 if( multrowbyminusone ) 435 { 436 if( SCIPisInfinity(scip, ub) ) 437 { 438 trytofix = FALSE; 439 break; 440 } 441 442 offset += coef * (-ub); 443 } 444 else 445 { 446 if( SCIPisInfinity(scip, -lb) ) 447 { 448 trytofix = FALSE; 449 break; 450 } 451 452 offset += coef * lb; 453 } 454 } 455 } 456 } 457 458 /* avoid fixings to infinite values or fixings of already fixed variables */ 459 if( trytofix && varstofix[col] == NOFIX) 460 { 461 /* feasibility is secured if the compensation value delta 462 * is large enough to compensate the value lhs-offset 463 */ 464 if( deltaisinf || SCIPisLE(scip, lhs-offset, delta) ) 465 { 466 if( compensation == COMPENSATE_UPLOCK ) 467 { 468 if( !SCIPisInfinity(scip,SCIPvarGetUbGlobal(SCIPmatrixGetVar(matrix, col))) ) 469 { 470 varstofix[col] = FIXATUB; 471 (*nfixings)++; 472 473 #ifdef SCIP_MORE_DEBUG 474 SCIPmatrixPrintRow(scip, matrix, row); 475 SCIPdebugMsg(scip, "%s, bds=[%.2f,%.2f], obj=%.2f, nnonzs=%d, type=%s, fix=ub, %.1f <= %.1f\n", 476 SCIPvarGetName(SCIPmatrixGetVar(matrix, col)),SCIPvarGetLbGlobal(SCIPmatrixGetVar(matrix, col)), 477 SCIPvarGetUbGlobal(SCIPmatrixGetVar(matrix, col)), SCIPvarGetObj(SCIPmatrixGetVar(matrix, col)), 478 SCIPmatrixGetColNNonzs(matrix, col), 479 SCIPvarGetType(SCIPmatrixGetVar(matrix, col))==SCIP_VARTYPE_CONTINUOUS ? "con" : "dis", 480 lhs-offset, delta); 481 #endif 482 } 483 } 484 else 485 { 486 if( !SCIPisInfinity(scip,-SCIPvarGetLbGlobal(SCIPmatrixGetVar(matrix, col))) ) 487 { 488 varstofix[col] = FIXATLB; 489 (*nfixings)++; 490 491 #ifdef SCIP_MORE_DEBUG 492 SCIPmatrixPrintRow(scip, matrix, row); 493 SCIPdebugMsg(scip, "%s, bds=[%.2f,%.2f], obj=%.2f, nnonzs=%d, type=%s, fix=lb, %.1f <= %.1f\n", 494 SCIPvarGetName(SCIPmatrixGetVar(matrix, col)),SCIPvarGetLbGlobal(SCIPmatrixGetVar(matrix, col)), 495 SCIPvarGetUbGlobal(SCIPmatrixGetVar(matrix, col)), SCIPvarGetObj(SCIPmatrixGetVar(matrix, col)), 496 SCIPmatrixGetColNNonzs(matrix, col), 497 SCIPvarGetType(SCIPmatrixGetVar(matrix, col))==SCIP_VARTYPE_CONTINUOUS ? "con" : "dis", 498 lhs-offset, delta); 499 #endif 500 } 501 } 502 } 503 } 504 505 return SCIP_OKAY; 506 } 507 508 /* 509 * Callback methods of presolver 510 */ 511 512 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 513 static 514 SCIP_DECL_PRESOLCOPY(presolCopyDualcomp) 515 { /*lint --e{715}*/ 516 assert(scip != NULL); 517 assert(presol != NULL); 518 assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0); 519 520 /* call inclusion method of presolver */ 521 SCIP_CALL( SCIPincludePresolDualcomp(scip) ); 522 523 return SCIP_OKAY; 524 } 525 526 /** execution method of presolver */ 527 static 528 SCIP_DECL_PRESOLEXEC(presolExecDualcomp) 529 { /*lint --e{715}*/ 530 SCIP_PRESOLDATA* presoldata; 531 SCIP_MATRIX* matrix; 532 SCIP_Bool initialized; 533 SCIP_Bool complete; 534 SCIP_Bool infeasible; 535 536 assert(result != NULL); 537 *result = SCIP_DIDNOTRUN; 538 539 if( (SCIPgetStage(scip) != SCIP_STAGE_PRESOLVING) || SCIPinProbing(scip) || SCIPisNLPEnabled(scip) ) 540 return SCIP_OKAY; 541 542 if( SCIPisStopped(scip) || SCIPgetNActivePricers(scip) > 0 ) 543 return SCIP_OKAY; 544 545 /* don't run if no compensation variables are present */ 546 if( SCIPgetNContVars(scip) == 0 ) 547 return SCIP_OKAY; 548 549 if( !SCIPallowStrongDualReds(scip) ) 550 return SCIP_OKAY; 551 552 *result = SCIP_DIDNOTFIND; 553 554 presoldata = SCIPpresolGetData(presol); 555 assert(presoldata != NULL); 556 557 matrix = NULL; 558 559 SCIP_CALL( SCIPmatrixCreate(scip, &matrix, TRUE, &initialized, &complete, &infeasible, 560 naddconss, ndelconss, nchgcoefs, nchgbds, nfixedvars) ); 561 562 /* if infeasibility was detected during matrix creation, return here */ 563 if( infeasible ) 564 { 565 if( initialized ) 566 SCIPmatrixFree(scip, &matrix); 567 568 *result = SCIP_CUTOFF; 569 return SCIP_OKAY; 570 } 571 572 /* we only work on pure MIPs currently */ 573 if( initialized && complete ) 574 { 575 int ncols; 576 int i; 577 SCIP_Real* valpnt; 578 int* colpnt; 579 int* colend; 580 int row; 581 SCIP_VAR* var; 582 SCIP_Bool inspect; 583 SCIP_Real val; 584 FIXINGDIRECTION* varstofix; 585 int nfixings; 586 SCIP_Real lhs; 587 SCIP_Real rhs; 588 SCIP_Bool twosides; 589 590 ncols = SCIPmatrixGetNColumns(matrix); 591 nfixings = 0; 592 593 SCIP_CALL( SCIPallocBufferArray(scip, &varstofix, ncols) ); 594 BMSclearMemoryArray(varstofix, ncols); 595 596 for(i = 0; i < ncols; i++) 597 { 598 var = SCIPmatrixGetVar(matrix, i); 599 600 /* exclude compensation variables itself for compensation */ 601 if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS && 602 SCIPmatrixGetColNNonzs(matrix, i) == 1 ) 603 continue; 604 605 /* if requested exclude continuous variables for compensation */ 606 if( presoldata->componlydisvars && SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS ) 607 continue; 608 609 /* verifiy that this variable has one uplock and that the uplocks are consistent */ 610 if( SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == 1 && 611 SCIPmatrixGetColNUplocks(matrix, i) == 1 && 612 SCIPisLE(scip, SCIPvarGetObj(var), 0.0) ) 613 { 614 row = -1; 615 val = 0.0; 616 inspect = FALSE; 617 twosides = FALSE; 618 colpnt = SCIPmatrixGetColIdxPtr(matrix, i); 619 colend = colpnt + SCIPmatrixGetColNNonzs(matrix, i); 620 valpnt = SCIPmatrixGetColValPtr(matrix, i); 621 622 /* search row which causes the uplock */ 623 for( ; (colpnt < colend); colpnt++, valpnt++ ) 624 { 625 row = *colpnt; 626 val = *valpnt; 627 lhs = SCIPmatrixGetRowLhs(matrix, row); 628 rhs = SCIPmatrixGetRowRhs(matrix, row); 629 630 if( SCIPisEQ(scip, lhs, rhs) ) 631 { 632 /* equation */ 633 inspect = TRUE; 634 twosides = TRUE; 635 break; 636 } 637 else if( SCIPmatrixIsRowRhsInfinity(matrix, row) ) 638 { 639 /* >= */ 640 if( SCIPisLT(scip, val, 0.0) ) 641 { 642 inspect = TRUE; 643 break; 644 } 645 } 646 else if( !SCIPisInfinity(scip, -lhs) && !SCIPisInfinity(scip, rhs) ) 647 { 648 /* ranged row */ 649 inspect = TRUE; 650 twosides = TRUE; 651 break; 652 } 653 } 654 655 assert(inspect); 656 657 if( inspect ) /*lint !e774*/ 658 { 659 assert(row >= 0); 660 assert(!SCIPisZero(scip, val)); 661 662 /* try to fix variable i at the upper bound */ 663 SCIP_CALL( compensateVarLock(scip, matrix, i, row, val, 664 twosides, COMPENSATE_UPLOCK, varstofix, &nfixings) ); 665 } 666 } 667 /* verifiy that this variable has one downlock and that the downlocks are consistent */ 668 else if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == 1 && 669 SCIPmatrixGetColNDownlocks(matrix, i) == 1 && 670 SCIPisGE(scip, SCIPvarGetObj(var), 0.0) ) 671 { 672 row = -1; 673 val = 0.0; 674 inspect = FALSE; 675 twosides = FALSE; 676 colpnt = SCIPmatrixGetColIdxPtr(matrix, i); 677 colend = colpnt + SCIPmatrixGetColNNonzs(matrix, i); 678 valpnt = SCIPmatrixGetColValPtr(matrix, i); 679 680 /* search row which causes the downlock */ 681 for( ; (colpnt < colend); colpnt++, valpnt++ ) 682 { 683 row = *colpnt; 684 val = *valpnt; 685 lhs = SCIPmatrixGetRowLhs(matrix, row); 686 rhs = SCIPmatrixGetRowRhs(matrix, row); 687 688 if( SCIPisEQ(scip, lhs, rhs) ) 689 { 690 /* equation */ 691 inspect = TRUE; 692 twosides = TRUE; 693 break; 694 } 695 else if( SCIPmatrixIsRowRhsInfinity(matrix, row) ) 696 { 697 /* >= */ 698 if( SCIPisGT(scip, val, 0.0) ) 699 { 700 inspect = TRUE; 701 break; 702 } 703 } 704 else if( !SCIPisInfinity(scip, -lhs) && !SCIPisInfinity(scip, rhs) ) 705 { 706 /* ranged row */ 707 inspect = TRUE; 708 twosides = TRUE; 709 break; 710 } 711 } 712 713 assert(inspect); 714 715 if( inspect ) /*lint !e774*/ 716 { 717 assert(row >= 0); 718 assert(!SCIPisZero(scip, val)); 719 720 /* try to fix variable i at the lower bound */ 721 SCIP_CALL( compensateVarLock(scip, matrix, i, row, val, 722 twosides, COMPENSATE_DOWNLOCK, varstofix, &nfixings) ); 723 } 724 } 725 } 726 727 if( nfixings > 0 ) 728 { 729 int v; 730 int oldnfixedvars; 731 int numupperboundfixings; 732 int numlowerboundfixings; 733 int numcontinuousfixings; 734 int numdiscretefixings; 735 736 oldnfixedvars = *nfixedvars; 737 numupperboundfixings = 0; 738 numlowerboundfixings = 0; 739 numcontinuousfixings = 0; 740 numdiscretefixings = 0; 741 742 /* look for fixable variables */ 743 for( v = ncols - 1; v >= 0; --v ) 744 { 745 SCIP_Bool fixed; 746 747 var = SCIPmatrixGetVar(matrix, v); 748 749 if( varstofix[v] == FIXATLB ) 750 { 751 SCIP_Real lb; 752 753 lb = SCIPvarGetLbGlobal(var); 754 755 /* avoid fixings to infinite values */ 756 assert(!SCIPisInfinity(scip, -lb)); 757 758 SCIPdebugMsg(scip, "Fix variable %s at lower bound %.15g\n", SCIPvarGetName(var), lb); 759 760 /* fix at lower bound */ 761 SCIP_CALL( SCIPfixVar(scip, var, lb, &infeasible, &fixed) ); 762 if( infeasible ) 763 { 764 SCIPdebugMsg(scip, " -> infeasible fixing\n"); 765 *result = SCIP_CUTOFF; 766 767 break; 768 } 769 assert(fixed); 770 (*nfixedvars)++; 771 numlowerboundfixings++; 772 773 if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS ) 774 numcontinuousfixings++; 775 else 776 numdiscretefixings++; 777 } 778 else if( varstofix[v] == FIXATUB ) 779 { 780 SCIP_Real ub; 781 782 ub = SCIPvarGetUbGlobal(var); 783 784 /* avoid fixings to infinite values */ 785 assert(!SCIPisInfinity(scip, ub)); 786 787 SCIPdebugMsg(scip, "Fix variable %s at upper bound %.15g\n", SCIPvarGetName(var), ub); 788 789 /* fix at upper bound */ 790 SCIP_CALL( SCIPfixVar(scip, var, ub, &infeasible, &fixed) ); 791 if( infeasible ) 792 { 793 SCIPdebugMsg(scip, " -> infeasible fixing\n"); 794 *result = SCIP_CUTOFF; 795 796 break; 797 } 798 assert(fixed); 799 (*nfixedvars)++; 800 numupperboundfixings++; 801 802 if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS ) 803 numcontinuousfixings++; 804 else 805 numdiscretefixings++; 806 } 807 } 808 809 if( *result != SCIP_CUTOFF && *nfixedvars > oldnfixedvars ) 810 *result = SCIP_SUCCESS; 811 812 SCIPdebugMsg(scip, "### lbfixes: %d, ubfixes: %d, con: %d, dis: %d\n", 813 numlowerboundfixings, numupperboundfixings, 814 numcontinuousfixings, numdiscretefixings); 815 } 816 817 SCIPfreeBufferArray(scip, &varstofix); 818 } 819 820 SCIPmatrixFree(scip, &matrix); 821 822 return SCIP_OKAY; 823 } 824 825 /* 826 * presolver specific interface methods 827 */ 828 829 /** destructor of presolver to free user data (called when SCIP is exiting) */ 830 static 831 SCIP_DECL_PRESOLFREE(presolFreeDualcomp) 832 { /*lint --e{715}*/ 833 SCIP_PRESOLDATA* presoldata; 834 835 /* free presolver data */ 836 presoldata = SCIPpresolGetData(presol); 837 assert(presoldata != NULL); 838 839 SCIPfreeBlockMemory(scip, &presoldata); 840 SCIPpresolSetData(presol, NULL); 841 842 return SCIP_OKAY; 843 } 844 845 /** creates the dualcomp presolver and includes it in SCIP */ 846 SCIP_RETCODE SCIPincludePresolDualcomp( 847 SCIP* scip /**< SCIP data structure */ 848 ) 849 { 850 SCIP_PRESOLDATA* presoldata; 851 SCIP_PRESOL* presol; 852 853 /* create dualcomp presolver data */ 854 SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) ); 855 856 /* include presolver */ 857 SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS, 858 PRESOL_TIMING, presolExecDualcomp, presoldata) ); 859 SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyDualcomp) ); 860 SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeDualcomp) ); 861 862 SCIP_CALL( SCIPaddBoolParam(scip, 863 "presolving/dualcomp/componlydisvars", 864 "should only discrete variables be compensated?", 865 &presoldata->componlydisvars, FALSE, DEFAULT_COMP_ONLY_DIS_VARS, NULL, NULL) ); 866 867 return SCIP_OKAY; 868 } 869