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_redvub.c 26 * @ingroup DEFPLUGINS_PRESOL 27 * @brief remove redundant variable upper bound constraints 28 * @author Dieter Weninger 29 * 30 * This presolver looks for dominating variable bound constraints 31 * on the same continuous variable and discards them. For example let x be a 32 * continuous variable and y, y' are binary variables. In addition, let two variable 33 * upper bound constraints ax - by <= e and cx - dy' <= f are given. If 34 * ax - by <= e implies cx - dy' <= f, then we can remove the second constraint 35 * and substitute/aggregate y' := y. The same can be done with variable lower 36 * bound constraints. 37 * 38 */ 39 40 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 41 42 #include "blockmemshell/memory.h" 43 #include "scip/presol_redvub.h" 44 #include "scip/pub_matrix.h" 45 #include "scip/pub_message.h" 46 #include "scip/pub_var.h" 47 #include "scip/scip_cons.h" 48 #include "scip/scip_general.h" 49 #include "scip/scip_mem.h" 50 #include "scip/scip_message.h" 51 #include "scip/scip_nlp.h" 52 #include "scip/scip_numerics.h" 53 #include "scip/scip_presol.h" 54 #include "scip/scip_pricer.h" 55 #include "scip/scip_prob.h" 56 #include "scip/scip_probing.h" 57 #include "scip/scip_var.h" 58 59 #define PRESOL_NAME "redvub" 60 #define PRESOL_DESC "detect redundant variable bound constraints" 61 #define PRESOL_PRIORITY -9000000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */ 62 #define PRESOL_MAXROUNDS 0 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */ 63 #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ 64 65 #define MAXPAIRCOMP 1000 /**< maximal number of pairwise comparisons */ 66 67 /* 68 * Local methods 69 */ 70 71 /** verify if the constraint is a variable upper bound constraint */ 72 static 73 SCIP_Bool isVub( 74 SCIP* scip, /**< SCIP main data structure */ 75 SCIP_MATRIX* matrix, /**< matrix instance */ 76 int row, /**< row index */ 77 SCIP_Real* lowthreshold, /**< low switching threshold */ 78 SCIP_Real* highthreshold, /**< high switching threshold */ 79 int* conidx, /**< variable index of continuous variable */ 80 int* binidx /**< variable index of binary variable */ 81 ) 82 { 83 SCIP_Real* valpnt; 84 int* rowpnt; 85 SCIP_Bool isvub; 86 87 assert(scip != NULL); 88 assert(matrix != NULL); 89 assert(0 <= row && row < SCIPmatrixGetNRows(matrix)); 90 assert(lowthreshold != NULL); 91 assert(highthreshold != NULL); 92 assert(conidx != NULL); 93 assert(binidx != NULL); 94 95 isvub = FALSE; 96 97 if( SCIPmatrixGetRowNNonzs(matrix, row) == 2 && SCIPmatrixIsRowRhsInfinity(matrix, row) ) 98 { 99 SCIP_VARTYPE type1; 100 SCIP_VARTYPE type2; 101 int idx1; 102 int idx2; 103 SCIP_VAR* var1; 104 SCIP_VAR* var2; 105 SCIP_Real val1; 106 SCIP_Real val2; 107 108 rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row); 109 valpnt = SCIPmatrixGetRowValPtr(matrix, row); 110 111 idx1 = *rowpnt; 112 val1 = *valpnt; 113 var1 = SCIPmatrixGetVar(matrix, idx1); 114 type1 = SCIPvarGetType(var1); 115 116 rowpnt++; 117 valpnt++; 118 119 idx2 = *rowpnt; 120 val2 = *valpnt; 121 var2 = SCIPmatrixGetVar(matrix, idx2); 122 type2 = SCIPvarGetType(var2); 123 124 /* we claim that the vub has the structure ax + cy >= b 125 * with a<0, c>0, x continuous, x>=0, y binary and obj(y)>=0 126 */ 127 if( (type1 == SCIP_VARTYPE_CONTINUOUS && type2 == SCIP_VARTYPE_BINARY) 128 && val1 < 0.0 && val2 > 0.0 && SCIPisGE(scip, SCIPvarGetLbGlobal(var1), 0.0) 129 && SCIPisGE(scip, SCIPvarGetObj(var2), 0.0) ) 130 { 131 *lowthreshold = SCIPmatrixGetRowLhs(matrix, row) / val1; 132 *highthreshold = (SCIPmatrixGetRowLhs(matrix, row) - val2) / val1; 133 *conidx = idx1; 134 *binidx = idx2; 135 isvub = TRUE; 136 } 137 else if( (type1 == SCIP_VARTYPE_BINARY && type2 == SCIP_VARTYPE_CONTINUOUS) 138 && val1 > 0.0 && val2 < 0.0 && SCIPisGE(scip, SCIPvarGetLbGlobal(var2), 0.0) 139 && SCIPisGE(scip, SCIPvarGetObj(var1), 0.0) ) 140 { 141 *lowthreshold = SCIPmatrixGetRowLhs(matrix, row) / val2; 142 *highthreshold = (SCIPmatrixGetRowLhs(matrix, row) - val1) / val2; 143 *conidx = idx2; 144 *binidx = idx1; 145 isvub = TRUE; 146 } 147 } 148 149 return isvub; 150 } 151 152 /** verify if the constraint is a variable lower bound constraint */ 153 static 154 SCIP_Bool isVlb( 155 SCIP* scip, /**< SCIP main data structure */ 156 SCIP_MATRIX* matrix, /**< matrix instance */ 157 int row, /**< row index */ 158 SCIP_Real* lowthreshold, /**< low switching threshold */ 159 SCIP_Real* highthreshold, /**< high switching threshold */ 160 int* conidx, /**< variable index of continuous variable */ 161 int* binidx /**< variable index of binary variable */ 162 ) 163 { 164 SCIP_Real* valpnt; 165 int* rowpnt; 166 SCIP_Bool isvlb; 167 168 assert(scip != NULL); 169 assert(matrix != NULL); 170 assert(0 <= row && row < SCIPmatrixGetNRows(matrix)); 171 assert(lowthreshold != NULL); 172 assert(highthreshold != NULL); 173 assert(conidx != NULL); 174 assert(binidx != NULL); 175 176 isvlb = FALSE; 177 178 if( SCIPmatrixGetRowNNonzs(matrix, row) == 2 && SCIPmatrixIsRowRhsInfinity(matrix, row) ) 179 { 180 SCIP_VARTYPE type1; 181 SCIP_VARTYPE type2; 182 int idx1; 183 int idx2; 184 SCIP_VAR* var1; 185 SCIP_VAR* var2; 186 SCIP_Real val1; 187 SCIP_Real val2; 188 189 rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row); 190 valpnt = SCIPmatrixGetRowValPtr(matrix, row); 191 192 idx1 = *rowpnt; 193 val1 = *valpnt; 194 var1 = SCIPmatrixGetVar(matrix, idx1); 195 type1 = SCIPvarGetType(var1); 196 197 rowpnt++; 198 valpnt++; 199 200 idx2 = *rowpnt; 201 val2 = *valpnt; 202 var2 = SCIPmatrixGetVar(matrix, idx2); 203 type2 = SCIPvarGetType(var2); 204 205 /* we claim that the vlb has the structure ax + cy >= b 206 * with a>0, c<0, x continuous, x>=0, y binary and obj(y)>=0 207 */ 208 if( (type1 == SCIP_VARTYPE_CONTINUOUS && type2 == SCIP_VARTYPE_BINARY) 209 && val1 > 0.0 && val2 < 0.0 && SCIPisGE(scip, SCIPvarGetLbGlobal(var1), 0.0) 210 && SCIPisGE(scip, SCIPvarGetObj(var2), 0.0) ) 211 { 212 *lowthreshold = SCIPmatrixGetRowLhs(matrix, row) / val1; 213 *highthreshold = (SCIPmatrixGetRowLhs(matrix, row) - val2) / val1; 214 *conidx = idx1; 215 *binidx = idx2; 216 isvlb = TRUE; 217 } 218 else if( (type1 == SCIP_VARTYPE_BINARY && type2 == SCIP_VARTYPE_CONTINUOUS) 219 && val1 < 0.0 && val2 > 0.0 && SCIPisGE(scip, SCIPvarGetLbGlobal(var2), 0.0) 220 && SCIPisGE(scip, SCIPvarGetObj(var1), 0.0) ) 221 { 222 *lowthreshold = SCIPmatrixGetRowLhs(matrix, row) / val2; 223 *highthreshold = (SCIPmatrixGetRowLhs(matrix, row) - val1) / val2; 224 *conidx = idx2; 225 *binidx = idx1; 226 isvlb = TRUE; 227 } 228 } 229 230 return isvlb; 231 } 232 233 234 /** searches for variable upper bound constraints on the same continuous variable with a dominance relation */ 235 static 236 SCIP_RETCODE detectDominatingVubs( 237 SCIP* scip, /**< SCIP main data structure */ 238 SCIP_MATRIX* matrix, /**< matrix containing the constraints */ 239 int nvubs, /**< number of vubs */ 240 int* vubs, /**< row indices of the vubs */ 241 SCIP_Real* lowthresholds, /**< low switching thresholds */ 242 SCIP_Real* highthresholds, /**< high switching thresholds */ 243 int* conidxs, /**< variable indexes of continuous variable */ 244 int* binidxs, /**< variable indexes of binary variable */ 245 int* nvaragg, /**< number of variables for aggregation */ 246 SCIP_Bool* isvartoagg, /**< flags indicating if variable could be aggregated */ 247 SCIP_VAR** aggvars, /**< pointers to the variables by which the aggregation should be done */ 248 int* ndeletecons, /**< number of deleteable constraints */ 249 SCIP_Bool* deletecons /**< flags which constraints could be deleted */ 250 ) 251 { 252 int i; 253 int j; 254 SCIP_Bool uselinearscan; 255 256 assert(scip != NULL); 257 assert(matrix != NULL); 258 assert(vubs != NULL); 259 assert(nvubs >= 2); 260 assert(lowthresholds != NULL); 261 assert(highthresholds != NULL); 262 assert(conidxs != NULL); 263 assert(binidxs != NULL); 264 assert(nvaragg != NULL); 265 assert(isvartoagg != NULL); 266 assert(aggvars != NULL); 267 assert(ndeletecons != NULL); 268 assert(deletecons != NULL); 269 270 /* use pairwise comparison only for a small number of vub constraints */ 271 if( nvubs >= MAXPAIRCOMP ) 272 uselinearscan = TRUE; 273 else 274 uselinearscan = FALSE; 275 276 for( i = 0; i < nvubs; i++ ) 277 { 278 for( j = i+1; j < nvubs; j++ ) 279 { 280 SCIP_VAR* var1; 281 SCIP_VAR* var2; 282 283 if( !SCIPisEQ(scip, lowthresholds[i], lowthresholds[j]) ) 284 continue; 285 286 var1 = SCIPmatrixGetVar(matrix, binidxs[i]); 287 var2 = SCIPmatrixGetVar(matrix, binidxs[j]); 288 289 /* make sure that the binary variables switch synchronously */ 290 if((SCIPmatrixGetColNDownlocks(matrix, binidxs[j]) == 1 && 291 SCIPmatrixGetColNDownlocks(matrix, binidxs[i]) == 1 && 292 SCIPmatrixGetColNUplocks(matrix, binidxs[j]) == 0 && 293 SCIPmatrixGetColNUplocks(matrix, binidxs[i]) == 0) || 294 (SCIPvarsHaveCommonClique(var1, FALSE, var2, TRUE, TRUE) && 295 SCIPvarsHaveCommonClique(var1, TRUE, var2, FALSE, TRUE)) ) 296 { 297 if( SCIPisLE(scip, highthresholds[i], highthresholds[j]) ) 298 { 299 #ifdef SCIP_DEBUG 300 SCIPdebugMsg(scip, "Aggregate variable %s by %s\n", SCIPvarGetName(var2), SCIPvarGetName(var1)); 301 SCIPdebugMsg(scip, "Delete variable upper bound constraint:\n"); 302 SCIP_CALL( SCIPprintCons(scip, SCIPmatrixGetCons(matrix, vubs[j]), NULL)); 303 SCIPinfoMessage(scip, NULL, "\n"); 304 #endif 305 306 isvartoagg[binidxs[j]] = TRUE; 307 aggvars[binidxs[j]] = SCIPmatrixGetVar(matrix, binidxs[i]); 308 (*nvaragg)++; 309 310 deletecons[vubs[j]] = TRUE; 311 (*ndeletecons)++; 312 } 313 else 314 { 315 assert(SCIPisGT(scip, highthresholds[i], highthresholds[j])); 316 #ifdef SCIP_DEBUG 317 SCIPdebugMsg(scip, "Aggregate variable %s by %s\n", SCIPvarGetName(var1), SCIPvarGetName(var2)); 318 SCIPdebugMsg(scip, "Delete variable upper bound constraint:\n"); 319 SCIP_CALL( SCIPprintCons(scip, SCIPmatrixGetCons(matrix, vubs[i]), NULL)); 320 SCIPinfoMessage(scip, NULL, "\n"); 321 #endif 322 323 isvartoagg[binidxs[i]] = TRUE; 324 aggvars[binidxs[i]] = SCIPmatrixGetVar(matrix, binidxs[j]); 325 (*nvaragg)++; 326 327 deletecons[vubs[i]] = TRUE; 328 (*ndeletecons)++; 329 } 330 } 331 332 if( uselinearscan ) 333 break; 334 } 335 } 336 337 return SCIP_OKAY; 338 } 339 340 /** searches for variable lower bound constraints on the same continuous variable with a dominance relation */ 341 static 342 SCIP_RETCODE detectDominatingVlbs( 343 SCIP* scip, /**< SCIP main data structure */ 344 SCIP_MATRIX* matrix, /**< matrix containing the constraints */ 345 int nvlbs, /**< number of vlbs */ 346 int* vlbs, /**< row indices of the vlbs */ 347 SCIP_Real* lowthresholds, /**< low switching thresholds */ 348 SCIP_Real* highthresholds, /**< high switching thresholds */ 349 int* conidxs, /**< variable indexes of continuous variable */ 350 int* binidxs, /**< variable indexes of binary variable */ 351 int* nvaragg, /**< number of variables for aggregation */ 352 SCIP_Bool* isvartoagg, /**< flags indicating if variable could be aggregated */ 353 SCIP_VAR** aggvars, /**< pointers to the variables by which the aggregation should be done */ 354 int* ndeletecons, /**< number of deleteable constraints */ 355 SCIP_Bool* deletecons /**< flags which constraints could be deleted */ 356 357 ) 358 { 359 int i; 360 int j; 361 SCIP_Bool uselinearscan; 362 363 assert(scip != NULL); 364 assert(matrix != NULL); 365 assert(vlbs != NULL); 366 assert(nvlbs >= 2); 367 assert(lowthresholds != NULL); 368 assert(highthresholds != NULL); 369 assert(conidxs != NULL); 370 assert(binidxs != NULL); 371 assert(nvaragg != NULL); 372 assert(isvartoagg != NULL); 373 assert(aggvars != NULL); 374 assert(ndeletecons != NULL); 375 assert(deletecons != NULL); 376 377 /* use pairwise comparison only for a small number of vlb constraints */ 378 if( nvlbs >= MAXPAIRCOMP ) 379 uselinearscan = TRUE; 380 else 381 uselinearscan = FALSE; 382 383 for( i = 0; i < nvlbs; i++ ) 384 { 385 for( j = i+1; j < nvlbs; j++ ) 386 { 387 SCIP_VAR* var1; 388 SCIP_VAR* var2; 389 390 if( !SCIPisEQ(scip, lowthresholds[i], lowthresholds[j]) ) 391 continue; 392 393 var1 = SCIPmatrixGetVar(matrix, binidxs[i]); 394 var2 = SCIPmatrixGetVar(matrix, binidxs[j]); 395 396 /* make sure that the binary variables switch synchronously */ 397 if((SCIPmatrixGetColNUplocks(matrix, binidxs[j]) == 1 && 398 SCIPmatrixGetColNUplocks(matrix, binidxs[i]) == 1 && 399 SCIPmatrixGetColNDownlocks(matrix, binidxs[j]) == 0 && 400 SCIPmatrixGetColNDownlocks(matrix, binidxs[i]) == 0) || 401 (SCIPvarsHaveCommonClique(var1, FALSE, var2, TRUE, TRUE) && 402 SCIPvarsHaveCommonClique(var1, TRUE, var2, FALSE, TRUE)) ) 403 { 404 if( SCIPisGE(scip, highthresholds[i], highthresholds[j]) ) 405 { 406 #ifdef SCIP_DEBUG 407 SCIPdebugMsg(scip, "Aggregate variable %s by %s\n", SCIPvarGetName(var2), SCIPvarGetName(var1)); 408 SCIPdebugMsg(scip, "Delete variable lower bound constraint:\n"); 409 SCIP_CALL( SCIPprintCons(scip, SCIPmatrixGetCons(matrix, vlbs[j]), NULL)); 410 SCIPinfoMessage(scip, NULL, "\n"); 411 #endif 412 413 isvartoagg[binidxs[j]] = TRUE; 414 aggvars[binidxs[j]] = SCIPmatrixGetVar(matrix, binidxs[i]); 415 (*nvaragg)++; 416 417 deletecons[vlbs[j]] = TRUE; 418 (*ndeletecons)++; 419 } 420 else 421 { 422 assert(SCIPisLT(scip, highthresholds[i], highthresholds[j])); 423 #ifdef SCIP_DEBUG 424 SCIPdebugMsg(scip, "Aggregate variable %s by %s\n", SCIPvarGetName(var1), SCIPvarGetName(var2)); 425 SCIPdebugMsg(scip, "Delete variable lower bound constraint:\n"); 426 SCIP_CALL( SCIPprintCons(scip, SCIPmatrixGetCons(matrix, vlbs[i]), NULL)); 427 SCIPinfoMessage(scip, NULL, "\n"); 428 #endif 429 430 isvartoagg[binidxs[i]] = TRUE; 431 aggvars[binidxs[i]] = SCIPmatrixGetVar(matrix, binidxs[j]); 432 (*nvaragg)++; 433 434 deletecons[vlbs[i]] = TRUE; 435 (*ndeletecons)++; 436 } 437 } 438 439 if( uselinearscan ) 440 break; 441 } 442 } 443 444 return SCIP_OKAY; 445 } 446 447 /** find variable aggregations and redundant variable bound constraints */ 448 static 449 SCIP_RETCODE findVarAggrRedVbcons( 450 SCIP* scip, /**< SCIP main data structure */ 451 SCIP_MATRIX* matrix, /**< constraint matrix */ 452 int* nvaragg, /**< number of redundant variables */ 453 SCIP_Bool* isvartoagg, /**< flags indicating which variables could be substituted/aggregated */ 454 SCIP_VAR** aggvars, /**< pointers to the variables by which the aggregation should be done */ 455 int* ndeletecons, /**< number of redundant constraints */ 456 SCIP_Bool* deletecons /**< flags indicating which constraints could be deleted */ 457 ) 458 { 459 int c; 460 int* colpnt; 461 int* colend; 462 int* vbcons; 463 int nvbcons; 464 int ncols; 465 int nrows; 466 SCIP_Real* lowthresholds; 467 SCIP_Real* highthresholds; 468 int* conidxs; 469 int* binidxs; 470 471 ncols = SCIPmatrixGetNColumns(matrix); 472 nrows = SCIPmatrixGetNRows(matrix); 473 474 SCIP_CALL( SCIPallocBufferArray(scip, &binidxs, nrows) ); 475 SCIP_CALL( SCIPallocBufferArray(scip, &conidxs, nrows) ); 476 SCIP_CALL( SCIPallocBufferArray(scip, &lowthresholds, nrows) ); 477 SCIP_CALL( SCIPallocBufferArray(scip, &highthresholds, nrows) ); 478 SCIP_CALL( SCIPallocBufferArray(scip, &vbcons, nrows) ); 479 480 for( c = 0; c < ncols; c++ ) 481 { 482 SCIP_VAR* var; 483 484 var = SCIPmatrixGetVar(matrix, c); 485 486 if( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS ) 487 continue; 488 489 /* search vubs per variable */ 490 nvbcons = 0; 491 colpnt = SCIPmatrixGetColIdxPtr(matrix, c); 492 colend = colpnt + SCIPmatrixGetColNNonzs(matrix, c); 493 for( ; (colpnt < colend); colpnt++ ) 494 { 495 SCIP_Real lowthreshold; 496 SCIP_Real highthreshold; 497 int conidx; 498 int binidx; 499 500 if( isVub(scip, matrix, *colpnt, &lowthreshold, &highthreshold, &conidx, &binidx) ) 501 { 502 vbcons[nvbcons] = *colpnt; 503 lowthresholds[nvbcons] = lowthreshold; 504 highthresholds[nvbcons] = highthreshold; 505 conidxs[nvbcons] = conidx; 506 binidxs[nvbcons] = binidx; 507 nvbcons++; 508 } 509 } 510 if( nvbcons >= 2 ) 511 { 512 SCIP_CALL( detectDominatingVubs(scip, matrix, nvbcons, vbcons, 513 lowthresholds, highthresholds, conidxs, binidxs, 514 nvaragg, isvartoagg, aggvars, ndeletecons, deletecons) ); 515 } 516 517 /* search vlbs per variable */ 518 nvbcons = 0; 519 colpnt = SCIPmatrixGetColIdxPtr(matrix, c); 520 colend = colpnt + SCIPmatrixGetColNNonzs(matrix, c); 521 for( ; (colpnt < colend); colpnt++ ) 522 { 523 SCIP_Real lowthreshold; 524 SCIP_Real highthreshold; 525 int conidx; 526 int binidx; 527 528 if( isVlb(scip, matrix, *colpnt, &lowthreshold, &highthreshold, &conidx, &binidx) ) 529 { 530 vbcons[nvbcons] = *colpnt; 531 lowthresholds[nvbcons] = lowthreshold; 532 highthresholds[nvbcons] = highthreshold; 533 conidxs[nvbcons] = conidx; 534 binidxs[nvbcons] = binidx; 535 nvbcons++; 536 } 537 } 538 if( nvbcons >= 2 ) 539 { 540 SCIP_CALL( detectDominatingVlbs(scip, matrix, nvbcons, vbcons, 541 lowthresholds, highthresholds, conidxs, binidxs, 542 nvaragg, isvartoagg, aggvars, ndeletecons, deletecons) ); 543 } 544 } 545 546 SCIPfreeBufferArray(scip, &vbcons); 547 SCIPfreeBufferArray(scip, &highthresholds); 548 SCIPfreeBufferArray(scip, &lowthresholds); 549 SCIPfreeBufferArray(scip, &conidxs); 550 SCIPfreeBufferArray(scip, &binidxs); 551 552 return SCIP_OKAY; 553 } 554 555 556 /* 557 * Callback methods of presolver 558 */ 559 560 561 /** execution method of presolver */ 562 static 563 SCIP_DECL_PRESOLEXEC(presolExecRedvub) 564 { /*lint --e{715}*/ 565 SCIP_MATRIX* matrix; 566 SCIP_Bool initialized; 567 SCIP_Bool complete; 568 SCIP_Bool infeasible; 569 570 assert(result != NULL); 571 *result = SCIP_DIDNOTRUN; 572 573 if( (SCIPgetStage(scip) != SCIP_STAGE_PRESOLVING) || SCIPinProbing(scip) || SCIPisNLPEnabled(scip) ) 574 return SCIP_OKAY; 575 576 if( SCIPgetNContVars(scip) == 0 || SCIPisStopped(scip) || SCIPgetNActivePricers(scip) > 0 ) 577 return SCIP_OKAY; 578 579 *result = SCIP_DIDNOTFIND; 580 581 matrix = NULL; 582 SCIP_CALL( SCIPmatrixCreate(scip, &matrix, TRUE, &initialized, &complete, &infeasible, 583 naddconss, ndelconss, nchgcoefs, nchgbds, nfixedvars) ); 584 585 /* if infeasibility was detected during matrix creation, return here */ 586 if( infeasible ) 587 { 588 if( initialized ) 589 SCIPmatrixFree(scip, &matrix); 590 591 *result = SCIP_CUTOFF; 592 return SCIP_OKAY; 593 } 594 595 if( initialized && complete ) 596 { 597 int nvaragg; 598 SCIP_Bool* isvartoagg; 599 int ndeletecons; 600 SCIP_Bool* deletecons; 601 SCIP_VAR** aggvars; 602 int ncols; 603 int nrows; 604 605 ncols = SCIPmatrixGetNColumns(matrix); 606 nrows = SCIPmatrixGetNRows(matrix); 607 608 nvaragg = 0; 609 ndeletecons = 0; 610 611 SCIP_CALL( SCIPallocBufferArray(scip, &isvartoagg, ncols) ); 612 BMSclearMemoryArray(isvartoagg, ncols); 613 614 SCIP_CALL( SCIPallocBufferArray(scip, &deletecons, nrows) ); 615 BMSclearMemoryArray(deletecons, nrows); 616 617 SCIP_CALL( SCIPallocBufferArray(scip, &aggvars, ncols) ); 618 BMSclearMemoryArray(aggvars, ncols); 619 620 SCIP_CALL( findVarAggrRedVbcons(scip, matrix, &nvaragg, isvartoagg, aggvars, &ndeletecons, deletecons) ); 621 622 if( nvaragg > 0 ) 623 { 624 int v; 625 for( v = 0; v < ncols; v++ ) 626 { 627 if( isvartoagg[v] ) 628 { 629 SCIP_Bool redundant; 630 SCIP_Bool aggregated; 631 632 /* substitute/aggregate binary variable */ 633 assert(aggvars[v] != NULL); 634 SCIP_CALL( SCIPaggregateVars(scip, SCIPmatrixGetVar(matrix,v), aggvars[v], 1.0, -1.0, 635 0.0, &infeasible, &redundant, &aggregated) ); 636 637 if( infeasible ) 638 { 639 SCIPdebugMsg(scip, " -> infeasible aggregation\n"); 640 *result = SCIP_CUTOFF; 641 return SCIP_OKAY; 642 } 643 644 if( aggregated ) 645 { 646 (*naggrvars)++; 647 648 /* set result pointer */ 649 if( (*result) == SCIP_DIDNOTFIND ) 650 *result = SCIP_SUCCESS; 651 } 652 } 653 } 654 } 655 656 if( ndeletecons > 0 ) 657 { 658 int r; 659 for( r = 0; r < nrows; r++ ) 660 { 661 if( deletecons[r] ) 662 { 663 SCIP_CONS* cons; 664 665 /* remove redundant variable bound constraint */ 666 cons = SCIPmatrixGetCons(matrix, r); 667 SCIP_CALL( SCIPdelCons(scip, cons) ); 668 669 (*ndelconss)++; 670 671 /* set result pointer */ 672 if( (*result) == SCIP_DIDNOTFIND ) 673 *result = SCIP_SUCCESS; 674 } 675 } 676 } 677 678 SCIPfreeBufferArray(scip, &aggvars); 679 SCIPfreeBufferArray(scip, &deletecons); 680 SCIPfreeBufferArray(scip, &isvartoagg); 681 } 682 683 SCIPmatrixFree(scip, &matrix); 684 685 return SCIP_OKAY; 686 } 687 688 /* 689 * presolver specific interface methods 690 */ 691 692 /** creates the redvub presolver and includes it in SCIP */ 693 SCIP_RETCODE SCIPincludePresolRedvub( 694 SCIP* scip /**< SCIP data structure */ 695 ) 696 { 697 SCIP_PRESOL* presol; 698 699 /* include presolver */ 700 SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS, 701 PRESOL_TIMING, presolExecRedvub, NULL) ); 702 703 return SCIP_OKAY; 704 } 705