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 sepa_zerohalf.c 26 * @ingroup DEFPLUGINS_SEPA 27 * @brief {0,1/2}-cuts separator 28 * @author Leona Gottwald 29 * @author Manuel Kutschka 30 * @author Kati Wolter 31 * 32 * {0,1/2}-Chvátal-Gomory cuts separator. It solves the following separation problem: 33 * Consider an integer program 34 * \f[ 35 * \min \{ c^T x : Ax \leq b, x \geq 0, x \mbox{ integer} \} 36 * \f] 37 * and a fractional solution \f$x^*\f$ of its LP relaxation. Find a weightvector \f$u\f$ whose entries \f$u_i\f$ are either 0 or 38 * \f$\frac{1}{2}\f$ such that the following inequality is valid for all integral solutions and violated by \f$x^*\f$: 39 * \f[ 40 * \lfloor(u^T A) x \rfloor \leq \lfloor u^T b\rfloor 41 * \f] 42 * 43 * References: 44 * - Alberto Caprara, Matteo Fischetti. {0,1/2}-Chvatal-Gomory cuts. Math. Programming, Volume 74, p221--235, 1996. 45 * - Arie M. C. A. Koster, Adrian Zymolka and Manuel Kutschka. \n 46 * Algorithms to separate {0,1/2}-Chvatal-Gomory cuts. 47 * Algorithms - ESA 2007: 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, \n 48 * Proceedings. Lecture Notes in Computer Science, Volume 4698, p. 693--704, 2007. 49 * - Arie M. C. A. Koster, Adrian Zymolka and Manuel Kutschka. \n 50 * Algorithms to separate {0,1/2}-Chvatal-Gomory cuts (Extended Version). \n 51 * ZIB Report 07-10, Zuse Institute Berlin, 2007. http://www.zib.de/Publications/Reports/ZR-07-10.pdf 52 * - Manuel Kutschka. Algorithmen zur Separierung von {0,1/2}-Schnitten. Diplomarbeit. Technische Universitaet Berlin, 2007. 53 */ 54 55 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 56 57 #include "string.h" 58 #include "scip/sepa_zerohalf.h" 59 #include "scip/scipdefplugins.h" 60 #include "scip/cutsel_hybrid.h" 61 62 #define SEPA_NAME "zerohalf" 63 #define SEPA_DESC "{0,1/2}-cuts separator" 64 #define SEPA_PRIORITY -6000 65 #define SEPA_FREQ 10 66 #define SEPA_MAXBOUNDDIST 1.0 67 #define SEPA_USESSUBSCIP FALSE 68 #define SEPA_DELAY FALSE 69 70 #define DEFAULT_MAXROUNDS 5 /**< maximal number of zerohalf separation rounds per node (-1: unlimited) */ 71 #define DEFAULT_MAXROUNDSROOT 20 /**< maximal number of zerohalf separation rounds in the root node (-1: unlimited) */ 72 #define DEFAULT_MAXSEPACUTS 20 /**< maximal number of zerohalf cuts separated per separation round */ 73 #define DEFAULT_MAXSEPACUTSROOT 100 /**< maximal number of zerohalf cuts separated per separation round in root node */ 74 #define DEFAULT_MAXCUTCANDS 2000 /**< maximal number of zerohalf cuts considered per separation round */ 75 #define DEFAULT_MAXSLACK 0.0 /**< maximal slack of rows to be used in aggregation */ 76 #define DEFAULT_MAXSLACKROOT 0.0 /**< maximal slack of rows to be used in aggregation in the root node */ 77 #define DEFAULT_GOODSCORE 1.0 /**< threshold for score of cut relative to best score to be considered good, 78 * so that less strict filtering is applied */ 79 #define DEFAULT_BADSCORE 0.5 /**< threshold for score of cut relative to best score to be discarded */ 80 #define DEFAULT_MINVIOL 0.1 /**< minimal violation to generate zerohalfcut for */ 81 #define DEFAULT_DYNAMICCUTS TRUE /**< should generated cuts be removed from the LP if they are no longer tight? */ 82 #define DEFAULT_MAXROWDENSITY 0.05 /**< maximal density of row to be used in aggregation */ 83 #define DEFAULT_DENSITYOFFSET 100 /**< additional number of variables allowed in row on top of density */ 84 #define DEFAULT_INITSEED 0x5EED /**< default initial seed used for random tie-breaking in cut selection */ 85 #define DEFAULT_OBJPARALWEIGHT 0.0 /**< weight of objective parallelism in cut score calculation */ 86 #define DEFAULT_EFFICACYWEIGHT 1.0 /**< weight of efficacy in cut score calculation */ 87 #define DEFAULT_DIRCUTOFFDISTWEIGHT 0.0 /**< weight of directed cutoff distance in cut score calculation */ 88 #define DEFAULT_GOODMAXPARALL 0.1 /**< maximum parallelism for good cuts */ 89 #define DEFAULT_MAXPARALL 0.1 /**< maximum parallelism for non-good cuts */ 90 91 /* SCIPcalcRowIntegralScalar parameters */ 92 #define MAXDNOM 1000LL 93 #define MAXSCALE 1000.0 94 95 /* other defines */ 96 #define MAXREDUCTIONROUNDS 100 /**< maximum number of rounds to perform reductions on the mod 2 system */ 97 #define BOUNDSWITCH 0.5 /**< threshold for bound switching */ 98 #define MAXAGGRLEN(nvars) ((int)(0.1*(nvars)+1000)) 99 100 typedef struct Mod2Col MOD2_COL; 101 typedef struct Mod2Row MOD2_ROW; 102 typedef struct Mod2Matrix MOD2_MATRIX; 103 typedef struct TransIntRow TRANSINTROW; 104 typedef struct RowIndex ROWINDEX; 105 106 /** enum for different types of row indices in ROWINDEX structure */ 107 108 #define ROWIND_TYPE unsigned int 109 #define ORIG_RHS 0u 110 #define ORIG_LHS 1u 111 #define TRANSROW 2u 112 113 /* macro to get a unique index from the rowindex */ 114 #define UNIQUE_INDEX(rowind) (3*(rowind).index + (rowind).type) 115 116 struct RowIndex 117 { 118 unsigned int type:2; /**< type of row index; 0 means lp row using the right hand side, 119 * 1 means lp row using the left hand side, and 2 means a 120 * transformed integral row */ 121 unsigned int index:30; /**< lp position of original row, or index of transformed integral row */ 122 }; 123 124 /** structure containing a transformed integral row obtained by relaxing an lp row */ 125 struct TransIntRow 126 { 127 SCIP_Real slack; /**< slack of row after transformation */ 128 SCIP_Real rhs; /**< right hand side value of integral row after transformation */ 129 SCIP_Real* vals; /**< values of row */ 130 int* varinds; /**< problem variable indices of row */ 131 int size; /**< alloc size of row */ 132 int len; /**< length of row */ 133 int rank; /**< rank of row */ 134 SCIP_Bool local; /**< is row local? */ 135 }; 136 137 /** structure representing a row in the mod 2 system */ 138 struct Mod2Row 139 { 140 ROWINDEX* rowinds; /**< index set of rows associated with the mod 2 row */ 141 MOD2_COL** nonzcols; /**< sorted array of non-zero mod 2 columns in this mod 2 row */ 142 SCIP_Real slack; /**< slack of mod 2 row */ 143 SCIP_Real maxsolval; /**< maximum solution value of columns in mod 2 row */ 144 int index; /**< unique index of mod 2 row */ 145 int pos; /**< position of mod 2 row in mod 2 matrix rows array */ 146 int rhs; /**< rhs of row */ 147 int nrowinds; /**< number of elements in rowinds */ 148 int rowindssize; /**< size of rowinds array */ 149 int nnonzcols; /**< number of columns in nonzcols */ 150 int nonzcolssize; /**< size of nonzcols array */ 151 }; 152 153 /** structure representing a column in the mod 2 system */ 154 struct Mod2Col 155 { 156 SCIP_HASHSET* nonzrows; /**< the set of rows that contain this column */ 157 SCIP_Real solval; /**< solution value of the column */ 158 int pos; /**< position of column in matrix */ 159 int index; /**< index of SCIP column associated to this column */ 160 }; 161 162 /** matrix representing the modulo 2 system */ 163 struct Mod2Matrix 164 { 165 MOD2_COL** cols; /**< columns of the matrix */ 166 MOD2_ROW** rows; /**< rows of the matrix */ 167 TRANSINTROW* transintrows; /**< transformed integral rows obtained from non-integral lp rows */ 168 int ntransintrows; /**< number of transformed integral rows obtained from non-integral lp rows */ 169 int nzeroslackrows; /**< number of rows with zero slack */ 170 int nrows; /**< number of rows of the matrix; number of elements in rows */ 171 int ncols; /**< number of cols of the matrix; number of elements in cols */ 172 int rowssize; /**< length of rows array */ 173 int colssize; /**< length of cols array */ 174 }; 175 176 /** data of separator */ 177 struct SCIP_SepaData 178 { 179 SCIP_RANDNUMGEN* randnumgen; /**< random generator for tiebreaking */ 180 SCIP_AGGRROW* aggrrow; /**< aggregation row used for generating cuts */ 181 SCIP_ROW** cuts; /**< generated in the current call */ 182 SCIP_Real minviol; /**< minimal violation to generate zerohalfcut for */ 183 SCIP_Real maxslack; /**< maximal slack of rows to be used in aggregation */ 184 SCIP_Real maxslackroot; /**< maximal slack of rows to be used in aggregation in the root node */ 185 SCIP_Real maxrowdensity; /**< maximal density of row to be used in aggregation */ 186 SCIP_Real goodscore; /**< threshold for score of cut relative to best score to be considered good, 187 * so that less strict filtering is applied */ 188 SCIP_Real badscore; /**< threshold for score of cut relative to best score to be discarded */ 189 SCIP_Real objparalweight; /**< weight of objective parallelism in cut score calculation */ 190 SCIP_Real efficacyweight; /**< weight of efficacy in cut score calculation */ 191 SCIP_Real dircutoffdistweight;/**< weight of directed cutoff distance in cut score calculation */ 192 SCIP_Real goodmaxparall; /**< maximum parallelism for good cuts */ 193 SCIP_Real maxparall; /**< maximum parallelism for non-good cuts */ 194 SCIP_Bool infeasible; /**< infeasibility was detected after adding a zerohalf cut */ 195 SCIP_Bool dynamiccuts; /**< should generated cuts be removed from the LP if they are no longer tight? */ 196 int maxrounds; /**< maximal number of zerohalf separation rounds per node (-1: unlimited) */ 197 int maxroundsroot; /**< maximal number of zerohalf separation rounds in the root node (-1: unlimited) */ 198 int maxsepacuts; /**< maximal number of zerohalf cuts separated per separation round */ 199 int maxsepacutsroot; /**< maximal number of zerohalf cuts separated per separation round in root node */ 200 int maxcutcands; /**< maximal number of zerohalf cuts considered per separation round */ 201 int densityoffset; /**< additional number of variables allowed in row on top of density */ 202 int initseed; /**< initial seed used for random tie-breaking in cut selection */ 203 int cutssize; /**< size of cuts and cutscores arrays */ 204 int ncuts; /**< number of cuts generated in the current call */ 205 int nreductions; /**< number of reductions to the mod 2 system found so far */ 206 }; 207 208 209 #define COLINFO_GET_MOD2COL(x) ((MOD2_COL*) (((uintptr_t)(x)) & ~((uintptr_t)1))) 210 #define COLINFO_GET_RHSOFFSET(x) ((int) (((uintptr_t)(x)) & ((uintptr_t)1))) 211 #define COLINFO_CREATE(mod2col, rhsoffset) ((void*) (((uintptr_t)(mod2col)) | ((uintptr_t)(rhsoffset)))) 212 213 214 #ifndef NDEBUG 215 static 216 void checkRow(MOD2_ROW* row) 217 { 218 int i; 219 SCIP_Real maxsolval = 0.0; 220 221 for( i = 0; i < row->nnonzcols; ++i ) 222 { 223 assert(row->nonzcols[i]->solval > 0.0); 224 maxsolval = MAX(maxsolval, row->nonzcols[i]->solval); 225 226 if( i + 1 < row->nnonzcols ) 227 assert(row->nonzcols[i]->index < row->nonzcols[i+1]->index); 228 } 229 230 assert(row->maxsolval == maxsolval); /*lint !e777*/ 231 } 232 #else 233 #define checkRow(x) 234 #endif 235 236 /** compare to mod 2 columns by there index */ 237 static 238 SCIP_DECL_SORTPTRCOMP(compareColIndex) 239 { 240 MOD2_COL* col1; 241 MOD2_COL* col2; 242 243 col1 = (MOD2_COL*) elem1; 244 col2 = (MOD2_COL*) elem2; 245 246 if( col1->index < col2->index ) 247 return -1; 248 if( col2->index < col1->index ) 249 return 1; 250 251 return 0; 252 } 253 254 /** comparison function for slack of mod 2 rows */ 255 static 256 SCIP_DECL_SORTPTRCOMP(compareRowSlack) 257 { 258 MOD2_ROW* row1; 259 MOD2_ROW* row2; 260 SCIP_Bool slack1iszero; 261 SCIP_Bool slack2iszero; 262 263 row1 = (MOD2_ROW*) elem1; 264 row2 = (MOD2_ROW*) elem2; 265 266 slack1iszero = EPSZ(row1->slack, SCIP_DEFAULT_EPSILON); 267 slack2iszero = EPSZ(row2->slack, SCIP_DEFAULT_EPSILON); 268 269 /* zero slack comes first */ 270 if( slack1iszero && !slack2iszero ) 271 return -1; 272 if( slack2iszero && !slack1iszero ) 273 return 1; 274 if( !slack1iszero && !slack2iszero ) 275 return 0; 276 277 /* prefer rows that contain columns with large solution value */ 278 if( row1->maxsolval > row2->maxsolval ) 279 return -1; 280 if( row2->maxsolval > row1->maxsolval ) 281 return 1; 282 283 /* rows with less non-zeros come first rows */ 284 if( row1->nnonzcols < row2->nnonzcols ) 285 return -1; 286 if( row2->nnonzcols < row1->nnonzcols ) 287 return 1; 288 289 return 0; 290 } 291 292 /** take integral real value modulo 2 */ 293 static 294 int mod2( 295 SCIP* scip, /**< scip data structure */ 296 SCIP_Real val /**< value to take mod 2 */ 297 ) 298 { 299 assert(SCIPisFeasIntegral(scip, val)); 300 val *= 0.5; 301 return (REALABS(SCIPround(scip, val) - val) > 0.1) ? 1 : 0; 302 } 303 304 /** returns the integral value for the given scaling parameters, see SCIPcalcIntegralScalar() */ 305 static 306 void getIntegralScalar( 307 SCIP_Real val, /**< value that should be scaled to an integral value */ 308 SCIP_Real scalar, /**< scalar that should be tried */ 309 SCIP_Real mindelta, /**< minimal relative allowed difference of scaled coefficient s*c and integral i */ 310 SCIP_Real maxdelta, /**< maximal relative allowed difference of scaled coefficient s*c and integral i */ 311 SCIP_Real* sval, /**< pointer to store the scaled value */ 312 SCIP_Real* intval /**< pointer to store the scaled integral value */ 313 ) 314 { 315 SCIP_Real upviol; 316 SCIP_Real downviol; 317 SCIP_Real downval; 318 SCIP_Real upval; 319 320 assert(mindelta <= 0.0); 321 assert(maxdelta >= 0.0); 322 323 *sval = val * scalar; 324 downval = floor(*sval); 325 upval = ceil(*sval); 326 327 downviol = SCIPrelDiff(*sval, downval) - maxdelta; 328 upviol = mindelta - SCIPrelDiff(*sval, upval); 329 330 if( downviol < upviol ) 331 *intval = downval; 332 else 333 *intval = upval; 334 } 335 336 /** Tries to transform a non-integral row into an integral row that can be used in zerohalf separation */ 337 static 338 SCIP_RETCODE transformNonIntegralRow( 339 SCIP* scip, /**< scip data structure */ 340 SCIP_SOL* sol, /**< solution to separate, or NULL for LP solution */ 341 SCIP_Bool allowlocal, /**< should local cuts be allowed */ 342 SCIP_Real maxslack, /**< maximum slack allowed for transformed row */ 343 int sign, /**< +1 or -1 scale to select the side of the row */ 344 SCIP_Bool local, /**< is the row only valid locally? */ 345 int rank, /**< rank of row */ 346 int rowlen, /**< length of row */ 347 SCIP_Real* rowvals, /**< coefficients of columns in row */ 348 SCIP_COL** rowcols, /**< columns of row */ 349 SCIP_Real rhs, /**< right hand side of row */ 350 int* intvarpos, /**< clean buffer array of size SCIPgetNVars that will be clean when the function returns */ 351 TRANSINTROW* introw, /**< pointer to return transformed row */ 352 SCIP_Bool* success /**< pointer to return whether the transformation succeeded */ 353 ) 354 { 355 int i; 356 int transrowlen; 357 SCIP_Real transrowrhs; 358 int* transrowvars; 359 SCIP_Real* transrowvals; 360 361 assert(scip != NULL); 362 assert(sign == +1 || sign == -1); 363 assert(rowvals != NULL || rowlen == 0); 364 assert(rowcols != NULL || rowlen == 0); 365 assert(intvarpos != NULL); 366 assert(introw != NULL); 367 assert(success != NULL); 368 369 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &transrowvars, rowlen) ); 370 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &transrowvals, rowlen) ); 371 transrowlen = 0; 372 transrowrhs = rhs; 373 374 /* first add all integral variables to the transformed row and remember their positions in the row */ 375 for( i = 0; i < rowlen; ++i ) 376 { 377 int probindex; 378 379 if( !SCIPcolIsIntegral(rowcols[i]) ) /*lint !e613*/ 380 continue; 381 382 probindex = SCIPcolGetVarProbindex(rowcols[i]); 383 transrowvars[transrowlen] = probindex; 384 transrowvals[transrowlen] = sign * rowvals[i]; 385 intvarpos[probindex] = ++transrowlen; 386 } 387 388 /* now loop over the non-integral columns of the row and project them out using simple or variable bounds */ 389 *success = TRUE; 390 391 for( i = 0; i < rowlen; ++i ) 392 { 393 int closestvbdind; 394 SCIP_Real closestbound; 395 SCIP_VAR* vbdvar; 396 SCIP_Real vbdcoef; 397 SCIP_Real vbdconst; 398 SCIP_VAR* colvar; 399 SCIP_Real val; 400 SCIP_Real closestvbd; 401 SCIP_Bool localbound; 402 403 if( SCIPcolIsIntegral(rowcols[i]) ) /*lint !e613*/ 404 continue; 405 406 localbound = FALSE; 407 408 colvar = SCIPcolGetVar(rowcols[i]); /*lint !e613*/ 409 410 val = sign * rowvals[i]; /*lint !e613*/ 411 412 /* if the value is positive we need to use a lower bound constraint */ 413 if( val > 0.0 ) 414 { 415 /* retrieve simple variable bound */ 416 closestbound = SCIPvarGetLbGlobal(colvar); 417 if( allowlocal && SCIPisSumGT(scip, SCIPvarGetLbLocal(colvar), closestbound) ) 418 { 419 /* only use local bound if it is better thatn the global bound */ 420 closestbound = SCIPvarGetLbLocal(colvar); 421 localbound = TRUE; 422 } 423 424 /* retrieve closest variable bound */ 425 SCIP_CALL( SCIPgetVarClosestVlb(scip, colvar, NULL, &closestvbd, &closestvbdind) ); 426 427 /* if a suitable variable bound exists which is at least as good as a local simple bound 428 * or better than a global simple bound we use it 429 */ 430 if( closestvbdind >= 0 && (SCIPisGT(scip, closestvbd, closestbound) || (localbound && SCIPisSumEQ(scip, closestvbd, closestbound))) ) 431 { 432 vbdcoef = SCIPvarGetVlbCoefs(colvar)[closestvbdind]; 433 vbdvar = SCIPvarGetVlbVars(colvar)[closestvbdind]; 434 vbdconst = SCIPvarGetVlbConstants(colvar)[closestvbdind]; 435 closestbound = closestvbd; 436 } 437 else 438 { 439 closestvbdind = -1; 440 } 441 } 442 else 443 { 444 /* retrieve simple variable bound */ 445 closestbound = SCIPvarGetUbGlobal(colvar); 446 if( allowlocal && SCIPisSumLT(scip, SCIPvarGetUbLocal(colvar), closestbound) ) 447 { 448 closestbound = SCIPvarGetUbLocal(colvar); 449 localbound = TRUE; 450 } 451 452 /* retrieve closest variable bound */ 453 SCIP_CALL( SCIPgetVarClosestVub(scip, colvar, NULL, &closestvbd, &closestvbdind) ); 454 455 /* if a suitable variable bound exists which is at least as good as a local simple bound 456 * or better than a global simple bound we use it 457 */ 458 if( closestvbdind >= 0 && (SCIPisLT(scip, closestvbd, closestbound) || (localbound && SCIPisSumEQ(scip, closestvbd, closestbound))) ) 459 { 460 vbdcoef = SCIPvarGetVubCoefs(colvar)[closestvbdind]; 461 vbdvar = SCIPvarGetVubVars(colvar)[closestvbdind]; 462 vbdconst = SCIPvarGetVubConstants(colvar)[closestvbdind]; 463 closestbound = closestvbd; 464 } 465 else 466 { 467 closestvbdind = -1; 468 } 469 } 470 471 if( closestvbdind >= 0 ) 472 { 473 SCIP_Real coef; 474 int pos; 475 476 coef = val * vbdcoef; /*lint !e644*/ 477 transrowrhs -= val * vbdconst; /*lint !e644*/ 478 479 pos = intvarpos[SCIPvarGetProbindex(vbdvar)] - 1; /*lint !e644*/ 480 if( pos >= 0 ) 481 { 482 transrowvals[pos] += coef; 483 } 484 else 485 { 486 transrowvars[transrowlen] = SCIPvarGetProbindex(vbdvar); 487 transrowvals[transrowlen] = coef; 488 intvarpos[SCIPvarGetProbindex(vbdvar)] = ++transrowlen; 489 } 490 } 491 else if( !SCIPisInfinity(scip, REALABS(closestbound)) ) 492 { 493 local = local || localbound; 494 transrowrhs -= val * closestbound; 495 } 496 else 497 { 498 *success = FALSE; 499 break; 500 } 501 } 502 503 for( i = 0; i < transrowlen;) 504 { 505 intvarpos[transrowvars[i]] = 0; 506 if( SCIPisZero(scip, transrowvals[i]) ) 507 { 508 --transrowlen; 509 transrowvals[i] = transrowvals[transrowlen]; 510 transrowvars[i] = transrowvars[transrowlen]; 511 } 512 else 513 ++i; 514 } 515 516 if( transrowlen <= 1 ) 517 *success = FALSE; 518 519 if( *success ) 520 { 521 SCIP_Real mindelta; 522 SCIP_Real maxdelta; 523 SCIP_Real intscalar; 524 int nchgcoefs; 525 526 SCIP_VAR** vars = SCIPgetVars(scip); 527 528 *success = ! SCIPcutsTightenCoefficients(scip, local, transrowvals, &transrowrhs, transrowvars, &transrowlen, &nchgcoefs); 529 530 mindelta = -SCIPepsilon(scip); 531 maxdelta = SCIPsumepsilon(scip); 532 533 if( *success ) 534 { 535 SCIP_CALL( SCIPcalcIntegralScalar(transrowvals, transrowlen, mindelta, maxdelta, MAXDNOM, MAXSCALE, &intscalar, success) ); 536 537 if( *success ) 538 { 539 SCIP_Real floorrhs; 540 SCIP_Real slack; 541 542 transrowrhs *= intscalar; /*lint !e644*/ 543 544 /* slack is initialized to zero since the transrowrhs can still change due to bound usage in the loop below; 545 * the floored right hand side is then added afterwards 546 */ 547 slack = 0.0; 548 for( i = 0; i < transrowlen; ++i ) 549 { 550 SCIP_Real solval = SCIPgetSolVal(scip, sol, vars[transrowvars[i]]); 551 SCIP_Real intval; 552 SCIP_Real newval; 553 554 getIntegralScalar(transrowvals[i], intscalar, mindelta, maxdelta, &newval, &intval); 555 556 if( !SCIPisEQ(scip, intval, newval) ) 557 { 558 if( intval < newval ) 559 { 560 SCIP_Real lb = local ? SCIPvarGetLbLocal(vars[transrowvars[i]]) : SCIPvarGetLbGlobal(vars[transrowvars[i]]); 561 562 if( SCIPisInfinity(scip, -lb) ) 563 { 564 *success = FALSE; 565 break; 566 } 567 568 transrowrhs += (intval - newval) * lb; 569 } 570 else 571 { 572 SCIP_Real ub = local ? SCIPvarGetUbLocal(vars[transrowvars[i]]) : SCIPvarGetUbGlobal(vars[transrowvars[i]]); 573 574 if( SCIPisInfinity(scip, ub) ) 575 { 576 *success = FALSE; 577 break; 578 } 579 580 transrowrhs += (intval - newval) * ub; 581 } 582 } 583 584 slack -= solval * intval; 585 transrowvals[i] = intval; 586 } 587 588 if( *success ) 589 { 590 floorrhs = SCIPfeasFloor(scip, transrowrhs); 591 slack += floorrhs; 592 593 if( slack <= maxslack ) 594 { 595 introw->rhs = floorrhs; 596 introw->slack = slack; 597 introw->vals = transrowvals; 598 introw->varinds = transrowvars; 599 introw->len = transrowlen; 600 introw->size = rowlen; 601 introw->local = local; 602 introw->rank = rank; 603 604 if( !SCIPisEQ(scip, floorrhs, transrowrhs) ) 605 introw->rank += 1; 606 } 607 else 608 { 609 *success = FALSE; 610 } 611 } 612 } 613 } 614 } 615 616 if( !(*success) ) 617 { 618 SCIPfreeBlockMemoryArray(scip, &transrowvals, rowlen); 619 SCIPfreeBlockMemoryArray(scip, &transrowvars, rowlen); 620 } 621 622 return SCIP_OKAY; 623 } 624 625 626 /** Tries to transform non-integral rows into an integral form by using simple and variable bounds */ 627 static 628 SCIP_RETCODE mod2MatrixTransformContRows( 629 SCIP* scip, /**< scip data structure */ 630 SCIP_SOL* sol, /**< solution to separate, or NULL for LP solution */ 631 SCIP_SEPADATA* sepadata, /**< zerohalf separator data */ 632 MOD2_MATRIX* mod2matrix, /**< mod2 matrix structure */ 633 SCIP_Bool allowlocal, /**< should local cuts be allowed */ 634 SCIP_Real maxslack /**< maximum slack allowed for mod 2 rows */ 635 ) 636 { 637 SCIP_ROW** rows; 638 int nrows; 639 int* intvarpos; 640 int i; 641 int maxnonzeros; 642 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) ); 643 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &mod2matrix->transintrows, 2*nrows) ); 644 mod2matrix->ntransintrows = 0; 645 646 SCIP_CALL( SCIPallocCleanBufferArray(scip, &intvarpos, SCIPgetNVars(scip)) ); 647 648 maxnonzeros = (int)(SCIPgetNLPCols(scip) * sepadata->maxrowdensity) + sepadata->densityoffset; 649 650 for( i = 0; i < nrows; ++i ) 651 { 652 int rowlen; 653 SCIP_Real activity; 654 SCIP_Real lhs; 655 SCIP_Real rhs; 656 SCIP_Real lhsslack; 657 SCIP_Real rhsslack; 658 SCIP_Real* rowvals; 659 SCIP_COL** rowcols; 660 661 /* skip integral rows and rows not suitable for generating cuts */ 662 if( SCIProwIsModifiable(rows[i]) || SCIProwIsIntegral(rows[i]) || (SCIProwIsLocal(rows[i]) && !allowlocal) || SCIProwGetNNonz(rows[i]) > maxnonzeros ) 663 continue; 664 665 lhs = SCIProwGetLhs(rows[i]) - SCIProwGetConstant(rows[i]); 666 rhs = SCIProwGetRhs(rows[i]) - SCIProwGetConstant(rows[i]); 667 activity = SCIPgetRowSolActivity(scip, rows[i], sol) - SCIProwGetConstant(rows[i]); 668 669 /* compute lhsslack: activity - lhs */ 670 if( SCIPisInfinity(scip, -SCIProwGetLhs(rows[i])) ) 671 lhsslack = SCIPinfinity(scip); 672 else 673 { 674 lhsslack = activity - lhs; 675 } 676 677 /* compute rhsslack: rhs - activity */ 678 if( SCIPisInfinity(scip, SCIProwGetRhs(rows[i])) ) 679 rhsslack = SCIPinfinity(scip); 680 else 681 rhsslack = rhs - activity; 682 683 if( rhsslack > maxslack && lhsslack > maxslack ) 684 continue; 685 686 rowlen = SCIProwGetNLPNonz(rows[i]); 687 rowvals = SCIProwGetVals(rows[i]); 688 rowcols = SCIProwGetCols(rows[i]); 689 690 if( rhsslack <= maxslack ) 691 { 692 SCIP_Bool success; 693 TRANSINTROW* introw = &mod2matrix->transintrows[mod2matrix->ntransintrows]; 694 SCIP_CALL( transformNonIntegralRow(scip, sol, allowlocal, maxslack, 1, SCIProwIsLocal(rows[i]), SCIProwGetRank(rows[i]), \ 695 rowlen, rowvals, rowcols, rhs, intvarpos, introw, &success) ); 696 697 assert(success == 1 || success == 0); 698 mod2matrix->ntransintrows += (int)success; 699 } 700 701 if( lhsslack <= maxslack ) 702 { 703 SCIP_Bool success; 704 TRANSINTROW* introw = &mod2matrix->transintrows[mod2matrix->ntransintrows]; 705 SCIP_CALL( transformNonIntegralRow(scip, sol, allowlocal, maxslack, -1, SCIProwIsLocal(rows[i]), SCIProwGetRank(rows[i]), \ 706 rowlen, rowvals, rowcols, -lhs, intvarpos, introw, &success) ); 707 708 assert(success == 1 || success == 0); 709 mod2matrix->ntransintrows += (int)success; 710 } 711 } 712 713 SCIPfreeCleanBufferArray(scip, &intvarpos); 714 715 return SCIP_OKAY; 716 } 717 718 719 /** adds new column to the mod 2 matrix */ 720 static 721 SCIP_RETCODE mod2MatrixAddCol( 722 SCIP* scip, /**< SCIP datastructure */ 723 MOD2_MATRIX* mod2matrix, /**< mod 2 matrix */ 724 SCIP_HASHMAP* origvar2col, /**< hash map for mapping of problem variables to mod 2 columns */ 725 SCIP_VAR* origvar, /**< problem variable to create mod 2 column for */ 726 SCIP_Real solval, /**< solution value of problem variable */ 727 int rhsoffset /**< offset in right hand side due complementation (mod 2) */ 728 ) 729 { 730 MOD2_COL* col; 731 732 /* allocate memory */ 733 SCIP_CALL( SCIPallocBlockMemory(scip, &col) ); 734 735 /* initialize fields */ 736 col->pos = mod2matrix->ncols++; 737 col->index = SCIPvarGetProbindex(origvar); 738 col->solval = solval; 739 SCIP_CALL( SCIPhashsetCreate(&col->nonzrows, SCIPblkmem(scip), 1) ); 740 741 /* add column to mod 2 matrix */ 742 SCIP_CALL( SCIPensureBlockMemoryArray(scip, &mod2matrix->cols, &mod2matrix->colssize, mod2matrix->ncols) ); 743 mod2matrix->cols[col->pos] = col; 744 745 /* create mapping of problem variable to mod 2 column with its right hand side offset */ 746 assert(rhsoffset >= 0); 747 SCIP_CALL( SCIPhashmapInsert(origvar2col, (void*) origvar, COLINFO_CREATE(col, rhsoffset)) ); /*lint !e571*/ 748 749 return SCIP_OKAY; 750 } 751 752 /** links row to mod 2 column */ 753 static 754 SCIP_RETCODE mod2colLinkRow( 755 BMS_BLKMEM* blkmem, /**< block memory shell */ 756 MOD2_COL* col, /**< mod 2 column */ 757 MOD2_ROW* row /**< mod 2 row */ 758 ) 759 { 760 SCIP_CALL( SCIPhashsetInsert(col->nonzrows, blkmem, (void*)row) ); 761 762 assert(SCIPhashsetExists(col->nonzrows, (void*)row)); 763 764 row->maxsolval = MAX(col->solval, row->maxsolval); 765 766 return SCIP_OKAY; 767 } 768 769 /** unlinks row from mod 2 column */ 770 static 771 SCIP_RETCODE mod2colUnlinkRow( 772 MOD2_COL* col, /**< mod 2 column */ 773 MOD2_ROW* row /**< mod 2 row */ 774 ) 775 { 776 SCIP_CALL( SCIPhashsetRemove(col->nonzrows, (void*)row) ); 777 778 assert(!SCIPhashsetExists(col->nonzrows, (void*)row)); 779 #ifndef NDEBUG 780 { 781 int nslots = SCIPhashsetGetNSlots(col->nonzrows); 782 MOD2_ROW** rows = (MOD2_ROW**) SCIPhashsetGetSlots(col->nonzrows); 783 int i; 784 785 for( i = 0; i < nslots; ++i ) 786 { 787 assert(rows[i] != row); 788 } 789 } 790 #endif 791 792 return SCIP_OKAY; 793 } 794 795 /** unlinks row from mod 2 column */ 796 static 797 void mod2rowUnlinkCol( 798 MOD2_ROW* row /**< mod 2 row */, 799 MOD2_COL* col /**< mod 2 column */ 800 ) 801 { 802 int i; 803 804 assert(row->nnonzcols == 0 || row->nonzcols != NULL); 805 806 SCIP_UNUSED( SCIPsortedvecFindPtr((void**) row->nonzcols, compareColIndex, col, row->nnonzcols, &i) ); 807 assert(row->nonzcols[i] == col); 808 809 --row->nnonzcols; 810 BMSmoveMemoryArray(row->nonzcols + i, row->nonzcols + i + 1, row->nnonzcols - i); /*lint !e866*/ 811 812 if( col->solval >= row->maxsolval ) 813 { 814 row->maxsolval = 0.0; 815 for( i = 0; i < row->nnonzcols; ++i ) 816 { 817 row->maxsolval = MAX(row->nonzcols[i]->solval, row->maxsolval); 818 } 819 } 820 } 821 822 /** adds a SCIP_ROW to the mod 2 matrix */ 823 static 824 SCIP_RETCODE mod2MatrixAddOrigRow( 825 SCIP* scip, /**< scip data structure */ 826 BMS_BLKMEM* blkmem, /**< block memory shell */ 827 MOD2_MATRIX* mod2matrix, /**< modulo 2 matrix */ 828 SCIP_HASHMAP* origcol2col, /**< hashmap to retrieve the mod 2 column from a SCIP_COL */ 829 SCIP_ROW* origrow, /**< original SCIP row */ 830 SCIP_Real slack, /**< slack of row */ 831 ROWIND_TYPE side, /**< side of row that is used for mod 2 row, must be ORIG_RHS or ORIG_LHS */ 832 int rhsmod2 /**< modulo 2 value of the row's right hand side */ 833 ) 834 { 835 SCIP_Real* rowvals; 836 SCIP_COL** rowcols; 837 int rowlen; 838 int i; 839 MOD2_ROW* row; 840 841 SCIP_ALLOC( BMSallocBlockMemory(blkmem, &row) ); 842 843 row->index = mod2matrix->nrows++; 844 SCIP_CALL( SCIPensureBlockMemoryArray(scip, &mod2matrix->rows, &mod2matrix->rowssize, mod2matrix->nrows) ); 845 mod2matrix->rows[row->index] = row; 846 847 row->slack = MAX(0.0, slack); 848 row->maxsolval = 0.0; 849 row->rhs = rhsmod2; 850 row->nrowinds = 1; 851 row->rowinds = NULL; 852 row->rowindssize = 0; 853 854 if( SCIPisZero(scip, row->slack) ) 855 ++mod2matrix->nzeroslackrows; 856 857 SCIP_CALL( SCIPensureBlockMemoryArray(scip, &row->rowinds, &row->rowindssize, row->nrowinds) ); 858 row->rowinds[0].type = side; 859 row->rowinds[0].index = (unsigned int)SCIProwGetLPPos(origrow); 860 861 row->nnonzcols = 0; 862 row->nonzcolssize = 0; 863 row->nonzcols = NULL; 864 865 rowlen = SCIProwGetNNonz(origrow); 866 rowvals = SCIProwGetVals(origrow); 867 rowcols = SCIProwGetCols(origrow); 868 869 for( i = 0; i < rowlen; ++i ) 870 { 871 if( mod2(scip, rowvals[i]) == 1 ) 872 { 873 void* colinfo; 874 MOD2_COL* col; 875 int rhsoffset; 876 877 colinfo = SCIPhashmapGetImage(origcol2col, (void*)SCIPcolGetVar(rowcols[i])); 878 879 /* extract the righthand side offset from the colinfo and update the righthand side */ 880 rhsoffset = COLINFO_GET_RHSOFFSET(colinfo); 881 row->rhs = (row->rhs + rhsoffset) % 2; 882 883 /* extract the column pointer from the colinfo */ 884 col = COLINFO_GET_MOD2COL(colinfo); 885 886 if( col != NULL ) 887 { 888 int k; 889 890 k = row->nnonzcols++; 891 892 SCIP_CALL( SCIPensureBlockMemoryArray(scip, &row->nonzcols, &row->nonzcolssize, row->nnonzcols) ); 893 row->nonzcols[k] = col; 894 895 SCIP_CALL( mod2colLinkRow(blkmem, col, row) ); 896 } 897 } 898 } 899 900 SCIPsortPtr((void**)row->nonzcols, compareColIndex, row->nnonzcols); 901 902 checkRow(row); 903 904 return SCIP_OKAY; 905 } 906 907 /** adds a transformed integral row to the mod 2 matrix */ 908 static 909 SCIP_RETCODE mod2MatrixAddTransRow( 910 SCIP* scip, /**< scip data structure */ 911 MOD2_MATRIX* mod2matrix, /**< modulo 2 matrix */ 912 SCIP_HASHMAP* origcol2col, /**< hashmap to retrieve the mod 2 column from a SCIP_COL */ 913 int transrowind /**< index to transformed int row */ 914 ) 915 { 916 int i; 917 SCIP_VAR** vars; 918 BMS_BLKMEM* blkmem; 919 MOD2_ROW* row; 920 TRANSINTROW* introw; 921 922 SCIP_CALL( SCIPallocBlockMemory(scip, &row) ); 923 924 vars = SCIPgetVars(scip); 925 introw = &mod2matrix->transintrows[transrowind]; 926 927 blkmem = SCIPblkmem(scip); 928 row->index = mod2matrix->nrows++; 929 SCIP_CALL( SCIPensureBlockMemoryArray(scip, &mod2matrix->rows, &mod2matrix->rowssize, mod2matrix->nrows) ); 930 mod2matrix->rows[row->index] = row; 931 932 row->slack = MAX(0.0, introw->slack); 933 row->rhs = mod2(scip, introw->rhs); 934 row->nrowinds = 1; 935 row->rowinds = NULL; 936 row->rowindssize = 0; 937 row->maxsolval = 0.0; 938 939 if( SCIPisZero(scip, row->slack) ) 940 ++mod2matrix->nzeroslackrows; 941 942 SCIP_CALL( SCIPensureBlockMemoryArray(scip, &row->rowinds, &row->rowindssize, row->nrowinds) ); 943 row->rowinds[0].type = TRANSROW; 944 row->rowinds[0].index = (unsigned int)transrowind; 945 946 row->nnonzcols = 0; 947 row->nonzcolssize = 0; 948 row->nonzcols = NULL; 949 950 for( i = 0; i < introw->len; ++i ) 951 { 952 if( mod2(scip, introw->vals[i]) == 1 ) 953 { 954 void* colinfo; 955 MOD2_COL* col; 956 int rhsoffset; 957 958 colinfo = SCIPhashmapGetImage(origcol2col, (void*)vars[introw->varinds[i]]); 959 960 /* extract the righthand side offset from the colinfo and update the righthand side */ 961 rhsoffset = COLINFO_GET_RHSOFFSET(colinfo); 962 row->rhs = (row->rhs + rhsoffset) % 2; 963 964 /* extract the column pointer from the colinfo */ 965 col = COLINFO_GET_MOD2COL(colinfo); 966 967 if( col != NULL ) 968 { 969 int k; 970 971 k = row->nnonzcols++; 972 973 SCIP_CALL( SCIPensureBlockMemoryArray(scip, &row->nonzcols, &row->nonzcolssize, row->nnonzcols) ); 974 row->nonzcols[k] = col; 975 976 SCIP_CALL( mod2colLinkRow(blkmem, col, row) ); 977 } 978 } 979 } 980 981 SCIPsortPtr((void**)row->nonzcols, compareColIndex, row->nnonzcols); 982 983 checkRow(row); 984 985 return SCIP_OKAY; 986 } 987 988 /** free all resources held by the mod 2 matrix */ 989 static 990 void destroyMod2Matrix( 991 SCIP* scip, /**< scip data structure */ 992 MOD2_MATRIX* mod2matrix /**< pointer to mod2 matrix structure */ 993 ) 994 { 995 int i; 996 997 for( i = 0; i < mod2matrix->ncols; ++i ) 998 { 999 SCIPhashsetFree(&mod2matrix->cols[i]->nonzrows, SCIPblkmem(scip)); 1000 SCIPfreeBlockMemory(scip, &mod2matrix->cols[i]); /*lint !e866*/ 1001 } 1002 1003 for( i = 0; i < mod2matrix->nrows; ++i ) 1004 { 1005 SCIPfreeBlockMemoryArrayNull(scip, &mod2matrix->rows[i]->nonzcols, mod2matrix->rows[i]->nonzcolssize); 1006 SCIPfreeBlockMemoryArrayNull(scip, &mod2matrix->rows[i]->rowinds, mod2matrix->rows[i]->rowindssize); 1007 SCIPfreeBlockMemory(scip, &mod2matrix->rows[i]); /*lint !e866*/ 1008 } 1009 1010 for( i = 0; i < mod2matrix->ntransintrows; ++i ) 1011 { 1012 SCIPfreeBlockMemoryArray(scip, &mod2matrix->transintrows[i].vals, mod2matrix->transintrows[i].size); 1013 SCIPfreeBlockMemoryArray(scip, &mod2matrix->transintrows[i].varinds, mod2matrix->transintrows[i].size); 1014 } 1015 1016 SCIPfreeBlockMemoryArray(scip, &mod2matrix->transintrows, 2*SCIPgetNLPRows(scip)); /*lint !e647*/ 1017 1018 SCIPfreeBlockMemoryArrayNull(scip, &mod2matrix->rows, mod2matrix->rowssize); 1019 SCIPfreeBlockMemoryArrayNull(scip, &mod2matrix->cols, mod2matrix->colssize); 1020 } 1021 1022 /** build the modulo 2 matrix from all integral rows in the LP, and non-integral rows 1023 * if the transformation to an integral row succeeds 1024 */ 1025 static 1026 SCIP_RETCODE buildMod2Matrix( 1027 SCIP* scip, /**< scip data structure */ 1028 SCIP_SOL* sol, /**< solution to separate, or NULL for LP solution */ 1029 SCIP_SEPADATA* sepadata, /**< zerohalf separator data */ 1030 BMS_BLKMEM* blkmem, /**< block memory shell */ 1031 MOD2_MATRIX* mod2matrix, /**< mod 2 matrix */ 1032 SCIP_Bool allowlocal, /**< should local cuts be allowed */ 1033 SCIP_Real maxslack /**< maximum slack allowed for mod 2 rows */ 1034 ) 1035 { 1036 SCIP_VAR** vars; 1037 SCIP_ROW** rows; 1038 SCIP_COL** cols; 1039 SCIP_HASHMAP* origcol2col; 1040 int ncols; 1041 int nrows; 1042 int nintvars; 1043 int maxnonzeros; 1044 int i; 1045 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) ); 1046 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) ); 1047 1048 nintvars = SCIPgetNVars(scip) - SCIPgetNContVars(scip); 1049 vars = SCIPgetVars(scip); 1050 1051 /* initialize fields */ 1052 mod2matrix->cols = NULL; 1053 mod2matrix->colssize = 0; 1054 mod2matrix->ncols = 0; 1055 mod2matrix->rows = NULL; 1056 mod2matrix->rowssize = 0; 1057 mod2matrix->nrows = 0; 1058 mod2matrix->nzeroslackrows = 0; 1059 1060 SCIP_CALL( SCIPhashmapCreate(&origcol2col, SCIPblkmem(scip), 1) ); 1061 1062 /* add all integral vars if they are not at their bound */ 1063 for( i = 0; i < nintvars; ++i ) 1064 { 1065 SCIP_Real lb; 1066 SCIP_Real ub; 1067 SCIP_Real lbsol; 1068 SCIP_Real ubsol; 1069 SCIP_Real primsol; 1070 SCIP_Bool useub; 1071 1072 primsol = SCIPgetSolVal(scip, sol, vars[i]); 1073 1074 lb = allowlocal ? SCIPvarGetLbLocal(vars[i]) : SCIPvarGetLbGlobal(vars[i]); 1075 lbsol = MAX(0.0, primsol - lb); 1076 if( SCIPisZero(scip, lbsol) ) 1077 { 1078 SCIP_CALL( SCIPhashmapInsert(origcol2col, (void*) vars[i], COLINFO_CREATE(NULL, mod2(scip, lb))) ); /*lint !e571*/ 1079 continue; 1080 } 1081 1082 ub = allowlocal ? SCIPvarGetUbLocal(vars[i]) : SCIPvarGetUbGlobal(vars[i]); 1083 ubsol = MAX(0.0, ub - primsol); 1084 if( SCIPisZero(scip, ubsol) ) 1085 { 1086 SCIP_CALL( SCIPhashmapInsert(origcol2col, (void*) vars[i], COLINFO_CREATE(NULL, mod2(scip, ub))) ); /*lint !e571*/ 1087 continue; 1088 } 1089 1090 if( SCIPisInfinity(scip, ub) ) /* if there is no ub, use lb */ 1091 useub = FALSE; 1092 else if( SCIPisInfinity(scip, -lb) ) /* if there is no lb, use ub */ 1093 useub = TRUE; 1094 else if( SCIPisLT(scip, primsol, (1.0 - BOUNDSWITCH) * lb + BOUNDSWITCH * ub) ) 1095 useub = FALSE; 1096 else 1097 useub = TRUE; 1098 1099 if( useub ) 1100 { 1101 assert(ubsol > 0.0); 1102 1103 /* coverity[var_deref_model] */ 1104 SCIP_CALL( mod2MatrixAddCol(scip, mod2matrix, origcol2col, vars[i], ubsol, mod2(scip, ub)) ); 1105 } 1106 else 1107 { 1108 assert(lbsol > 0.0); 1109 1110 /* coverity[var_deref_model] */ 1111 SCIP_CALL( mod2MatrixAddCol(scip, mod2matrix, origcol2col, vars[i], lbsol, mod2(scip, lb)) ); 1112 } 1113 } 1114 1115 maxnonzeros = (int)(SCIPgetNLPCols(scip) * sepadata->maxrowdensity) + sepadata->densityoffset; 1116 1117 /* add all integral rows using the created columns */ 1118 for( i = 0; i < nrows; ++i ) 1119 { 1120 SCIP_Real lhs; 1121 SCIP_Real rhs; 1122 SCIP_Real activity; 1123 SCIP_Real lhsslack; 1124 SCIP_Real rhsslack; 1125 int lhsmod2; 1126 int rhsmod2; 1127 1128 /* skip non-integral rows and rows not suitable for generating cuts */ 1129 if( SCIProwIsModifiable(rows[i]) || !SCIProwIsIntegral(rows[i]) || (SCIProwIsLocal(rows[i]) && !allowlocal) || SCIProwGetNNonz(rows[i]) > maxnonzeros ) 1130 continue; 1131 1132 lhsmod2 = 0; 1133 rhsmod2 = 0; 1134 activity = SCIPgetRowSolActivity(scip, rows[i], sol) - SCIProwGetConstant(rows[i]); 1135 1136 /* since row is integral we can ceil/floor the lhs/rhs after subtracting the constant */ 1137 lhs = SCIPfeasCeil(scip, SCIProwGetLhs(rows[i]) - SCIProwGetConstant(rows[i])); 1138 rhs = SCIPfeasFloor(scip, SCIProwGetRhs(rows[i]) - SCIProwGetConstant(rows[i])); 1139 1140 /* compute lhsslack: activity - lhs */ 1141 if( SCIPisInfinity(scip, -SCIProwGetLhs(rows[i])) ) 1142 lhsslack = SCIPinfinity(scip); 1143 else 1144 { 1145 lhsslack = activity - lhs; 1146 lhsmod2 = mod2(scip, lhs); 1147 } 1148 1149 /* compute rhsslack: rhs - activity */ 1150 if( SCIPisInfinity(scip, SCIProwGetRhs(rows[i])) ) 1151 rhsslack = SCIPinfinity(scip); 1152 else 1153 { 1154 rhsslack = rhs - activity; 1155 rhsmod2 = mod2(scip, rhs); 1156 } 1157 1158 if( rhsslack <= maxslack && lhsslack <= maxslack ) 1159 { 1160 if( lhsmod2 == rhsmod2 ) 1161 { 1162 /* maxslack < 1 implies rhs - lhs = rhsslack + lhsslack < 2. Therefore lhs = rhs (mod2) can only hold if they 1163 * are equal 1164 */ 1165 assert(SCIPisEQ(scip, lhs, rhs)); 1166 1167 /* use rhs */ 1168 /* coverity[var_deref_model] */ 1169 SCIP_CALL( mod2MatrixAddOrigRow(scip, blkmem, mod2matrix, origcol2col, rows[i], rhsslack, ORIG_RHS, rhsmod2) ); 1170 } 1171 else 1172 { 1173 /* use both */ 1174 /* coverity[var_deref_model] */ 1175 SCIP_CALL( mod2MatrixAddOrigRow(scip, blkmem, mod2matrix, origcol2col, rows[i], lhsslack, ORIG_LHS, lhsmod2) ); 1176 SCIP_CALL( mod2MatrixAddOrigRow(scip, blkmem, mod2matrix, origcol2col, rows[i], rhsslack, ORIG_RHS, rhsmod2) ); 1177 } 1178 } 1179 else if( rhsslack <= maxslack ) 1180 { 1181 /* use rhs */ 1182 /* coverity[var_deref_model] */ 1183 SCIP_CALL( mod2MatrixAddOrigRow(scip, blkmem, mod2matrix, origcol2col, rows[i], rhsslack, ORIG_RHS, rhsmod2) ); 1184 } 1185 else if( lhsslack <= maxslack ) 1186 { 1187 /* use lhs */ 1188 /* coverity[var_deref_model] */ 1189 SCIP_CALL( mod2MatrixAddOrigRow(scip, blkmem, mod2matrix, origcol2col, rows[i], lhsslack, ORIG_LHS, lhsmod2) ); 1190 } 1191 } 1192 1193 /* transform non-integral rows */ 1194 SCIP_CALL( mod2MatrixTransformContRows(scip, sol, sepadata, mod2matrix, allowlocal, maxslack) ); 1195 1196 /* add all transformed integral rows using the created columns */ 1197 for( i = 0; i < mod2matrix->ntransintrows; ++i ) 1198 { 1199 SCIP_CALL( mod2MatrixAddTransRow(scip, mod2matrix, origcol2col, i) ); 1200 } 1201 1202 SCIPhashmapFree(&origcol2col); 1203 1204 return SCIP_OKAY; 1205 } 1206 1207 /* compare two mod 2 columns for equality */ 1208 static 1209 SCIP_DECL_HASHKEYEQ(columnsEqual) 1210 { /*lint --e{715}*/ 1211 MOD2_COL* col1; 1212 MOD2_COL* col2; 1213 int nslotscol1; 1214 MOD2_ROW** col1rows; 1215 int i; 1216 1217 col1 = (MOD2_COL*) key1; 1218 col2 = (MOD2_COL*) key2; 1219 1220 if( SCIPhashsetGetNElements(col1->nonzrows) != SCIPhashsetGetNElements(col2->nonzrows) ) 1221 return FALSE; 1222 1223 nslotscol1 = SCIPhashsetGetNSlots(col1->nonzrows); 1224 col1rows = (MOD2_ROW**) SCIPhashsetGetSlots(col1->nonzrows); 1225 for( i = 0; i < nslotscol1; ++i ) 1226 { 1227 if( col1rows[i] != NULL && !SCIPhashsetExists(col2->nonzrows, (void*)col1rows[i]) ) 1228 return FALSE; 1229 } 1230 1231 return TRUE; 1232 } 1233 1234 /* compute a signature of the rows in a mod 2 matrix as hash value */ 1235 static 1236 SCIP_DECL_HASHKEYVAL(columnGetSignature) 1237 { /*lint --e{715}*/ 1238 MOD2_COL* col; 1239 MOD2_ROW** rows; 1240 uint64_t signature; 1241 int i; 1242 int nslots; 1243 1244 col = (MOD2_COL*) key; 1245 1246 nslots = SCIPhashsetGetNSlots(col->nonzrows); 1247 rows = (MOD2_ROW**) SCIPhashsetGetSlots(col->nonzrows); 1248 1249 signature = 0; 1250 for( i = 0; i < nslots; ++i ) 1251 { 1252 if( rows[i] != NULL ) 1253 signature |= SCIPhashSignature64(rows[i]->index); 1254 } 1255 1256 return signature; 1257 } 1258 1259 /* compare two mod 2 rows for equality */ 1260 static 1261 SCIP_DECL_HASHKEYEQ(rowsEqual) 1262 { /*lint --e{715}*/ 1263 MOD2_ROW* row1; 1264 MOD2_ROW* row2; 1265 int i; 1266 1267 row1 = (MOD2_ROW*) key1; 1268 row2 = (MOD2_ROW*) key2; 1269 1270 assert(row1 != NULL); 1271 assert(row2 != NULL); 1272 assert(row1->nnonzcols == 0 || row1->nonzcols != NULL); 1273 assert(row2->nnonzcols == 0 || row2->nonzcols != NULL); 1274 1275 if( row1->nnonzcols != row2->nnonzcols || row1->rhs != row2->rhs ) 1276 return FALSE; 1277 1278 for( i = 0; i < row1->nnonzcols; ++i ) 1279 { 1280 if( row1->nonzcols[i] != row2->nonzcols[i] ) 1281 return FALSE; 1282 } 1283 1284 return TRUE; 1285 } 1286 1287 /* compute a signature of a mod 2 row as hash value */ 1288 static 1289 SCIP_DECL_HASHKEYVAL(rowGetSignature) 1290 { /*lint --e{715}*/ 1291 MOD2_ROW* row; 1292 int i; 1293 uint64_t signature; 1294 1295 row = (MOD2_ROW*) key; 1296 assert(row->nnonzcols == 0 || row->nonzcols != NULL); 1297 1298 signature = row->rhs; /*lint !e732*/ 1299 1300 for( i = 0; i < row->nnonzcols; ++i ) 1301 signature |= SCIPhashSignature64(row->nonzcols[i]->index); 1302 1303 return signature; 1304 } 1305 1306 /** removes a row from the mod 2 matrix */ 1307 static 1308 SCIP_RETCODE mod2matrixRemoveRow( 1309 SCIP* scip, /**< scip data structure */ 1310 MOD2_MATRIX* mod2matrix, /**< the mod 2 matrix */ 1311 MOD2_ROW* row /**< mod 2 row */ 1312 ) 1313 { 1314 int i; 1315 int position = row->pos; 1316 1317 checkRow(row); 1318 1319 /* update counter for zero slack rows */ 1320 if( SCIPisZero(scip, row->slack) ) 1321 --mod2matrix->nzeroslackrows; 1322 1323 /* remove the row from the array */ 1324 --mod2matrix->nrows; 1325 mod2matrix->rows[position] = mod2matrix->rows[mod2matrix->nrows]; 1326 mod2matrix->rows[position]->pos = position; 1327 1328 /* unlink columns from row */ 1329 for( i = 0; i < row->nnonzcols; ++i ) 1330 { 1331 SCIP_CALL( mod2colUnlinkRow(row->nonzcols[i], row) ); 1332 } 1333 1334 /* free row */ 1335 SCIPfreeBlockMemoryArrayNull(scip, &row->nonzcols, row->nonzcolssize); 1336 SCIPfreeBlockMemoryArray(scip, &row->rowinds, row->rowindssize); 1337 SCIPfreeBlockMemory(scip, &row); 1338 1339 return SCIP_OKAY; 1340 } 1341 1342 /** removes a column from the mod 2 matrix */ 1343 static 1344 void mod2matrixRemoveCol( 1345 SCIP* scip, /**< scip data structure */ 1346 MOD2_MATRIX* mod2matrix, /**< the mod 2 matrix */ 1347 MOD2_COL* col /**< a column in the mod 2 matrix */ 1348 ) 1349 { 1350 int i; 1351 int nslots; 1352 MOD2_ROW** rows; 1353 int position; 1354 1355 assert(col != NULL); 1356 1357 /* cppcheck-suppress nullPointer */ 1358 position = col->pos; 1359 1360 /* remove column from arrays */ 1361 --mod2matrix->ncols; 1362 mod2matrix->cols[position] = mod2matrix->cols[mod2matrix->ncols]; 1363 mod2matrix->cols[position]->pos = position; 1364 1365 /* cppcheck-suppress nullPointer */ 1366 nslots = SCIPhashsetGetNSlots(col->nonzrows); 1367 /* cppcheck-suppress nullPointer */ 1368 rows = (MOD2_ROW**) SCIPhashsetGetSlots(col->nonzrows); 1369 1370 /* adjust rows of column */ 1371 for( i = 0; i < nslots; ++i ) 1372 { 1373 if( rows[i] != NULL ) 1374 mod2rowUnlinkCol(rows[i], col); 1375 } 1376 1377 /* free column */ 1378 SCIPhashsetFree(&col->nonzrows, SCIPblkmem(scip)); 1379 SCIPfreeBlockMemory(scip, &col); 1380 } 1381 1382 /* remove columns that are (Prop3 iii) zero (Prop3 iv) identify indentical columns (Prop3 v) unit vector columns */ 1383 static 1384 SCIP_RETCODE mod2matrixPreprocessColumns( 1385 SCIP* scip, /**< scip data structure */ 1386 MOD2_MATRIX* mod2matrix, /**< mod 2 matrix */ 1387 SCIP_SEPADATA* sepadata /**< zerohalf separator data */ 1388 ) 1389 { 1390 int i; 1391 SCIP_HASHTABLE* columntable; 1392 1393 SCIP_CALL( SCIPhashtableCreate(&columntable, SCIPblkmem(scip), mod2matrix->ncols, 1394 SCIPhashGetKeyStandard, columnsEqual, columnGetSignature, NULL) ); 1395 1396 for( i = 0; i < mod2matrix->ncols; ) 1397 { 1398 MOD2_COL* col = mod2matrix->cols[i]; 1399 int nnonzrows = SCIPhashsetGetNElements(col->nonzrows); 1400 if( nnonzrows == 0 ) 1401 { /* Prop3 iii */ 1402 mod2matrixRemoveCol(scip, mod2matrix, col); 1403 } 1404 else if( nnonzrows == 1 ) 1405 { /* Prop3 v */ 1406 MOD2_ROW* row; 1407 1408 { 1409 int j = 0; 1410 MOD2_ROW** rows; 1411 rows = (MOD2_ROW**) SCIPhashsetGetSlots(col->nonzrows); 1412 while( rows[j] == NULL ) 1413 ++j; 1414 1415 row = rows[j]; 1416 } 1417 1418 checkRow(row); 1419 1420 /* column is unit vector, so add its solution value to the rows slack and remove it */ 1421 if( SCIPisZero(scip, row->slack) ) 1422 --mod2matrix->nzeroslackrows; 1423 1424 row->slack += col->solval; 1425 assert(!SCIPisZero(scip, row->slack)); 1426 1427 mod2matrixRemoveCol(scip, mod2matrix, col); 1428 ++sepadata->nreductions; 1429 1430 checkRow(row); 1431 } 1432 else 1433 { 1434 MOD2_COL* identicalcol; 1435 identicalcol = (MOD2_COL*)SCIPhashtableRetrieve(columntable, col); 1436 if( identicalcol != NULL ) 1437 { 1438 assert(identicalcol != col); 1439 1440 /* column is identical to other column so add its solution value to the other one and then remove and free it */ 1441 identicalcol->solval += col->solval; 1442 1443 /* also adjust the solval of the removed column so that the maxsolval of each row is properly updated */ 1444 col->solval = identicalcol->solval; 1445 1446 mod2matrixRemoveCol(scip, mod2matrix, col); 1447 } 1448 else 1449 { 1450 SCIP_CALL( SCIPhashtableInsert(columntable, (void*)col) ); 1451 ++i; 1452 } 1453 } 1454 } 1455 1456 SCIPhashtableFree(&columntable); 1457 1458 return SCIP_OKAY; 1459 } 1460 1461 #define NONZERO(x) (COPYSIGN(1e-100, (x)) + (x)) 1462 1463 /** add original row to aggregation with weight 0.5 */ 1464 static 1465 void addOrigRow( 1466 SCIP* scip, /**< SCIP datastructure */ 1467 SCIP_Real* tmpcoefs, /**< array to add coefficients to */ 1468 SCIP_Real* cutrhs, /**< pointer to add right hand side */ 1469 int* nonzeroinds, /**< array of non-zeros in the aggregation */ 1470 int* nnz, /**< pointer to update number of non-zeros */ 1471 int* cutrank, /**< pointer to update cut rank */ 1472 SCIP_Bool* cutislocal, /**< pointer to update local flag */ 1473 SCIP_ROW* row, /**< row to add */ 1474 int sign /**< sign for weight, i.e. +1 to use right hand side or -1 to use left hand side */ 1475 ) 1476 { 1477 int i; 1478 SCIP_Real weight = 0.5 * sign; 1479 SCIP_COL** rowcols; 1480 SCIP_Real* rowvals; 1481 int rowlen; 1482 1483 rowlen = SCIProwGetNNonz(row); 1484 rowcols = SCIProwGetCols(row); 1485 rowvals = SCIProwGetVals(row); 1486 for( i = 0; i < rowlen; ++i ) 1487 { 1488 SCIP_Real val; 1489 int probindex; 1490 1491 probindex = SCIPcolGetVarProbindex(rowcols[i]); 1492 val = tmpcoefs[probindex]; 1493 if( val == 0.0 ) 1494 { 1495 nonzeroinds[(*nnz)++] = probindex; 1496 } 1497 1498 val += weight * rowvals[i]; 1499 tmpcoefs[probindex] = NONZERO(val); 1500 } 1501 1502 if( sign == +1 ) 1503 { 1504 *cutrhs += weight * SCIPfeasFloor(scip, SCIProwGetRhs(row) - SCIProwGetConstant(row)); 1505 } 1506 else 1507 { 1508 assert(sign == -1); 1509 *cutrhs += weight * SCIPfeasCeil(scip, SCIProwGetLhs(row) - SCIProwGetConstant(row)); 1510 } 1511 1512 if( SCIProwGetRank(row) > *cutrank ) 1513 *cutrank = SCIProwGetRank(row); 1514 *cutislocal = *cutislocal || SCIProwIsLocal(row); 1515 } 1516 1517 /** add transformed integral row to aggregation with weight 0.5 */ 1518 static 1519 void addTransRow( 1520 SCIP_Real* tmpcoefs, /**< array to add coefficients to */ 1521 SCIP_Real* cutrhs, /**< pointer to add right hand side */ 1522 int* nonzeroinds, /**< array of non-zeros in the aggregation */ 1523 int* nnz, /**< pointer to update number of non-zeros */ 1524 int* cutrank, /**< pointer to update cut rank */ 1525 SCIP_Bool* cutislocal, /**< pointer to update local flag */ 1526 TRANSINTROW* introw /**< transformed integral row to add to the aggregation */ 1527 ) 1528 { 1529 int i; 1530 1531 for( i = 0; i < introw->len; ++i ) 1532 { 1533 int probindex = introw->varinds[i]; 1534 SCIP_Real val = tmpcoefs[probindex]; 1535 1536 if( val == 0.0 ) 1537 { 1538 nonzeroinds[(*nnz)++] = probindex; 1539 } 1540 1541 val += 0.5 * introw->vals[i]; 1542 tmpcoefs[probindex] = NONZERO(val); 1543 } 1544 1545 *cutrhs += 0.5 * introw->rhs; 1546 1547 *cutrank = MAX(*cutrank, introw->rank); 1548 *cutislocal = *cutislocal || introw->local; 1549 } 1550 1551 /* calculates the cuts efficacy of cut */ 1552 static 1553 SCIP_Real calcEfficacy( 1554 SCIP* scip, /**< SCIP data structure */ 1555 SCIP_SOL* sol, /**< solution to separate, or NULL for LP solution */ 1556 SCIP_Real* cutcoefs, /**< array of the non-zero coefficients in the cut */ 1557 SCIP_Real cutrhs, /**< the right hand side of the cut */ 1558 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */ 1559 int cutnnz /**< the number of non-zeros in the cut */ 1560 ) 1561 { 1562 SCIP_VAR** vars; 1563 SCIP_Real norm; 1564 SCIP_Real activity; 1565 int i; 1566 1567 assert(scip != NULL); 1568 assert(cutcoefs != NULL); 1569 assert(cutinds != NULL); 1570 1571 norm = SCIPgetVectorEfficacyNorm(scip, cutcoefs, cutnnz); 1572 vars = SCIPgetVars(scip); 1573 1574 activity = 0.0; 1575 for( i = 0; i < cutnnz; ++i ) 1576 activity += cutcoefs[i] * SCIPgetSolVal(scip, sol, vars[cutinds[i]]); 1577 1578 return (activity - cutrhs) / MAX(1e-6, norm); 1579 } 1580 1581 /** computes maximal violation that can be achieved for zerohalf cuts where this row particiaptes */ 1582 static 1583 SCIP_Real computeMaxViolation( 1584 MOD2_ROW* row /**< mod 2 row */ 1585 ) 1586 { 1587 SCIP_Real viol; 1588 1589 viol = 1.0 - row->slack; 1590 viol *= 0.5; 1591 1592 return viol; 1593 } 1594 1595 /** computes violation of zerohalf cut generated from given mod 2 row */ 1596 static 1597 SCIP_Real computeViolation( 1598 MOD2_ROW* row /**< mod 2 row */ 1599 ) 1600 { 1601 int i; 1602 SCIP_Real viol; 1603 1604 viol = 1.0 - row->slack; 1605 1606 for( i = 0; i < row->nnonzcols; ++i ) 1607 { 1608 viol -= row->nonzcols[i]->solval; 1609 } 1610 1611 viol *= 0.5; 1612 1613 return viol; 1614 } 1615 1616 /** generate a zerohalf cut from a given mod 2 row, i.e., try if aggregations of rows of the 1617 * mod2 matrix give violated cuts 1618 */ 1619 static 1620 SCIP_RETCODE generateZerohalfCut( 1621 SCIP* scip, /**< scip data structure */ 1622 SCIP_SOL* sol, /**< solution to separate, or NULL for LP solution */ 1623 MOD2_MATRIX* mod2matrix, /**< mod 2 matrix */ 1624 SCIP_SEPA* sepa, /**< zerohalf separator */ 1625 SCIP_SEPADATA* sepadata, /**< zerohalf separator data */ 1626 SCIP_Bool allowlocal, /**< should local cuts be allowed */ 1627 MOD2_ROW* row /**< mod 2 row */ 1628 ) 1629 { 1630 SCIP_Bool cutislocal; 1631 int i; 1632 int cutnnz; 1633 int cutrank; 1634 int nvars; 1635 int maxaggrlen; 1636 int nchgcoefs; 1637 int* cutinds; 1638 SCIP_ROW** rows; 1639 SCIP_VAR** vars; 1640 SCIP_Real* tmpcoefs; 1641 SCIP_Real* cutcoefs; 1642 SCIP_Real cutrhs; 1643 SCIP_Real cutefficacy; 1644 1645 if( computeViolation(row) < sepadata->minviol ) 1646 return SCIP_OKAY; 1647 1648 rows = SCIPgetLPRows(scip); 1649 nvars = SCIPgetNVars(scip); 1650 vars = SCIPgetVars(scip); 1651 1652 maxaggrlen = MAXAGGRLEN(SCIPgetNLPCols(scip)); 1653 1654 /* right hand side must be odd, otherwise no cut can be generated */ 1655 assert(row->rhs == 1); 1656 1657 /* perform the summation of the rows defined by the mod 2 row*/ 1658 SCIP_CALL( SCIPallocCleanBufferArray(scip, &tmpcoefs, nvars) ); 1659 SCIP_CALL( SCIPallocBufferArray(scip, &cutinds, nvars) ); 1660 SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nvars) ); 1661 1662 /* the right hand side of the zerohalf cut will be rounded down by 0.5 1663 * thus we can instead subtract 0.5 directly 1664 */ 1665 cutrhs = -0.5; 1666 cutnnz = 0; 1667 cutrank = 0; 1668 cutislocal = FALSE; 1669 1670 /* compute the aggregation of the rows with weight 0.5 */ 1671 for( i = 0; i < row->nrowinds; ++i ) 1672 { 1673 switch( row->rowinds[i].type ) 1674 { 1675 case ORIG_RHS: 1676 addOrigRow(scip, tmpcoefs, &cutrhs, cutinds, &cutnnz, &cutrank, &cutislocal, rows[row->rowinds[i].index], 1); 1677 break; 1678 case ORIG_LHS: 1679 addOrigRow(scip, tmpcoefs, &cutrhs, cutinds, &cutnnz, &cutrank, &cutislocal, rows[row->rowinds[i].index], -1); 1680 break; 1681 case TRANSROW: { 1682 TRANSINTROW* introw = &mod2matrix->transintrows[row->rowinds[i].index]; 1683 SCIPdebugMsg(scip, "using transformed row %i of length %i with slack %f and rhs %f for cut\n", row->rowinds[i].index, introw->len, introw->slack, introw->rhs); 1684 addTransRow(tmpcoefs, &cutrhs, cutinds, &cutnnz, &cutrank, &cutislocal, introw); 1685 break; 1686 } 1687 default: 1688 SCIPABORT(); 1689 } 1690 } 1691 1692 /* abort if aggregation is too long */ 1693 if( cutnnz > maxaggrlen ) 1694 { 1695 /* clean buffer array must be set to zero before jumping to the terminate label */ 1696 for( i = 0; i < cutnnz; ++i ) 1697 { 1698 int k = cutinds[i]; 1699 tmpcoefs[k] = 0.0; 1700 } 1701 goto TERMINATE; 1702 } 1703 1704 /* compute the cut coefficients and update right handside due to complementation if necessary */ 1705 for( i = 0; i < cutnnz; ) 1706 { 1707 int k = cutinds[i]; 1708 SCIP_Real coef = tmpcoefs[k]; 1709 SCIP_Real floorcoef = SCIPfeasFloor(scip, coef); 1710 tmpcoefs[k] = 0.0; 1711 1712 /* only check complementation if the coefficient was rounded down */ 1713 if( REALABS(coef - floorcoef) > 0.1 ) 1714 { 1715 SCIP_Real lb; 1716 SCIP_Real ub; 1717 SCIP_Bool loclb; 1718 SCIP_Bool locub; 1719 SCIP_Real primsol; 1720 SCIP_Bool useub; 1721 1722 /* complement with closest bound */ 1723 primsol = SCIPgetSolVal(scip, sol, vars[k]); 1724 lb = SCIPvarGetLbGlobal(vars[k]); 1725 ub = SCIPvarGetUbGlobal(vars[k]); 1726 loclb = FALSE; 1727 locub = FALSE; 1728 1729 /* use local bounds if better */ 1730 if( allowlocal ) 1731 { 1732 if( SCIPisGT(scip, SCIPvarGetLbLocal(vars[k]), lb) ) 1733 { 1734 loclb = TRUE; 1735 lb = SCIPvarGetLbLocal(vars[k]); 1736 } 1737 1738 if( SCIPisLT(scip, SCIPvarGetUbLocal(vars[k]), ub) ) 1739 { 1740 locub = TRUE; 1741 ub = SCIPvarGetUbLocal(vars[k]); 1742 } 1743 } 1744 1745 if( SCIPisInfinity(scip, ub) ) /* if there is no ub, use lb */ 1746 useub = FALSE; 1747 else if( SCIPisInfinity(scip, -lb) ) /* if there is no lb, use ub */ 1748 useub = TRUE; 1749 else if( SCIPisLT(scip, primsol, (1.0 - BOUNDSWITCH) * lb + BOUNDSWITCH * ub) ) 1750 useub = FALSE; 1751 else 1752 useub = TRUE; 1753 1754 if( useub ) 1755 { 1756 /* set local flag if local bound was used */ 1757 if( locub ) 1758 cutislocal = TRUE; 1759 1760 /* upper bound was used so floor was the wrong direction to round, coefficient must be ceiled instead */ 1761 floorcoef += 1.0; 1762 1763 assert(SCIPisFeasEQ(scip, floorcoef - coef, 0.5)); 1764 1765 /* add delta of complementing then rounding by 0.5 and complementing back to the right hand side */ 1766 cutrhs += 0.5 * ub; 1767 } 1768 else 1769 { 1770 /* set local flag if local bound was used */ 1771 if( loclb ) 1772 cutislocal = TRUE; 1773 1774 assert(SCIPisFeasEQ(scip, coef - floorcoef, 0.5)); 1775 1776 /* add delta of complementing then rounding by 0.5 and complementing back to the right hand side */ 1777 cutrhs -= 0.5 * lb; 1778 } 1779 } 1780 1781 /* make coefficient exactly integral */ 1782 assert(SCIPisFeasIntegral(scip, floorcoef)); 1783 floorcoef = SCIPfeasRound(scip, floorcoef); 1784 1785 /* if coefficient is zero remove entry, otherwise set to floorcoef */ 1786 if( floorcoef == 0.0 ) 1787 { 1788 --cutnnz; 1789 cutinds[i] = cutinds[cutnnz]; 1790 } 1791 else 1792 { 1793 cutcoefs[i] = floorcoef; 1794 ++i; 1795 } 1796 } 1797 1798 /* make right hand side exactly integral */ 1799 assert(SCIPisFeasIntegral(scip, cutrhs)); 1800 cutrhs = SCIPfeasRound(scip, cutrhs); 1801 1802 if( ! SCIPcutsTightenCoefficients(scip, cutislocal, cutcoefs, &cutrhs, cutinds, &cutnnz, &nchgcoefs) ) 1803 { 1804 /* calculate efficacy */ 1805 cutefficacy = calcEfficacy(scip, sol, cutcoefs, cutrhs, cutinds, cutnnz); 1806 1807 if( SCIPisEfficacious(scip, cutefficacy) ) 1808 { 1809 SCIP_ROW* cut; 1810 char cutname[SCIP_MAXSTRLEN]; 1811 int v; 1812 1813 /* increase rank by 1 */ 1814 cutrank += 1; 1815 1816 assert(allowlocal || !cutislocal); 1817 1818 /* create the cut */ 1819 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "zerohalf%" SCIP_LONGINT_FORMAT "_x%d", SCIPgetNLPs(scip), row->index); 1820 1821 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, sepadata->dynamiccuts) ); 1822 1823 SCIProwChgRank(cut, cutrank); 1824 1825 /* cache the row extension and only flush them if the cut gets added */ 1826 SCIP_CALL( SCIPcacheRowExtensions(scip, cut) ); 1827 1828 /* collect all non-zero coefficients */ 1829 for( v = 0; v < cutnnz; ++v ) 1830 { 1831 SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[v]], cutcoefs[v]) ); 1832 } 1833 1834 /* flush all changes before adding the cut */ 1835 SCIP_CALL( SCIPflushRowExtensions(scip, cut) ); 1836 1837 if( SCIPisCutNew(scip, cut) ) 1838 { 1839 int pos = sepadata->ncuts++; 1840 1841 if( sepadata->ncuts > sepadata->cutssize ) 1842 { 1843 int newsize = SCIPcalcMemGrowSize(scip, sepadata->ncuts); 1844 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &sepadata->cuts, sepadata->cutssize, newsize) ); 1845 sepadata->cutssize = newsize; 1846 } 1847 1848 sepadata->cuts[pos] = cut; 1849 } 1850 else 1851 { 1852 /* release the row */ 1853 SCIP_CALL( SCIPreleaseRow(scip, &cut) ); 1854 } 1855 } 1856 } 1857 1858 TERMINATE: 1859 SCIPfreeBufferArray(scip, &cutcoefs); 1860 SCIPfreeBufferArray(scip, &cutinds); 1861 SCIPfreeCleanBufferArray(scip, &tmpcoefs); 1862 1863 return SCIP_OKAY; 1864 } 1865 1866 1867 /** remove rows that are (a) zero (b) identical to other rows (keep the one with smallest slack) (c) have slack greater 1868 * than 1 (d) for zero rows with 1 as rhs and slack less than 1, we can directly generate a cut and remove the row (Lemma 4) 1869 */ 1870 static 1871 SCIP_RETCODE mod2matrixPreprocessRows( 1872 SCIP* scip, /**< scip data structure */ 1873 SCIP_SOL* sol, /**< solution to separate, or NULL for LP solution */ 1874 MOD2_MATRIX* mod2matrix, /**< the mod 2 matrix */ 1875 SCIP_SEPA* sepa, /**< the zerohalf separator */ 1876 SCIP_SEPADATA* sepadata, /**< data of the zerohalf separator */ 1877 SCIP_Bool allowlocal /**< should local cuts be allowed */ 1878 ) 1879 { 1880 int i; 1881 SCIP_HASHTABLE* rowtable; 1882 1883 SCIP_CALL( SCIPhashtableCreate(&rowtable, SCIPblkmem(scip), mod2matrix->nrows, 1884 SCIPhashGetKeyStandard, rowsEqual, rowGetSignature, NULL) ); 1885 1886 for( i = 0; i < mod2matrix->nrows; ) 1887 { 1888 MOD2_ROW* row = mod2matrix->rows[i]; 1889 row->pos = i; 1890 1891 checkRow(row); 1892 1893 assert(row->nnonzcols == 0 || row->nonzcols != NULL); 1894 1895 if( (row->nnonzcols == 0 && row->rhs == 0) || computeMaxViolation(row) < sepadata->minviol ) 1896 { /* (a) and (c) */ 1897 sepadata->nreductions += row->nnonzcols; 1898 SCIP_CALL( mod2matrixRemoveRow(scip, mod2matrix, row) ); 1899 } 1900 else if( row->nnonzcols > 0 ) 1901 { /* (b) */ 1902 MOD2_ROW* identicalrow; 1903 identicalrow = (MOD2_ROW*)SCIPhashtableRetrieve(rowtable, (void*)row); 1904 if( identicalrow != NULL ) 1905 { 1906 assert(identicalrow != row); 1907 assert(identicalrow->nnonzcols == 0 || identicalrow->nonzcols != NULL); 1908 1909 checkRow(identicalrow); 1910 1911 /* row is identical to other row; only keep the one with smaller slack */ 1912 if( identicalrow->slack <= row->slack ) 1913 { 1914 SCIP_CALL( mod2matrixRemoveRow(scip, mod2matrix, row) ); 1915 } 1916 else 1917 { 1918 assert(SCIPhashtableExists(rowtable, (void*)identicalrow)); 1919 1920 SCIP_CALL( SCIPhashtableRemove(rowtable, (void*)identicalrow) ); 1921 assert(!SCIPhashtableExists(rowtable, (void*)identicalrow)); 1922 1923 SCIP_CALL( SCIPhashtableInsert(rowtable, (void*)row) ); 1924 1925 SCIPswapPointers((void**) &mod2matrix->rows[row->pos], (void**) &mod2matrix->rows[identicalrow->pos]); 1926 SCIPswapInts(&row->pos, &identicalrow->pos); 1927 1928 assert(mod2matrix->rows[row->pos] == row && mod2matrix->rows[identicalrow->pos] == identicalrow); 1929 assert(identicalrow->pos == i); 1930 assert(row->pos < i); 1931 1932 SCIP_CALL( mod2matrixRemoveRow(scip, mod2matrix, identicalrow) ); 1933 } 1934 } 1935 else 1936 { 1937 SCIP_CALL( SCIPhashtableInsert(rowtable, (void*)row) ); 1938 ++i; 1939 } 1940 } 1941 else 1942 { 1943 /* (d) */ 1944 assert(row->nnonzcols == 0 && row->rhs == 1 && SCIPisLT(scip, row->slack, 1.0)); 1945 1946 SCIP_CALL( generateZerohalfCut(scip, sol, mod2matrix, sepa, sepadata, allowlocal, row) ); 1947 1948 if( sepadata->infeasible ) 1949 goto TERMINATE; 1950 1951 SCIP_CALL( mod2matrixRemoveRow(scip, mod2matrix, row) ); 1952 ++i; 1953 } 1954 } 1955 TERMINATE: 1956 SCIPhashtableFree(&rowtable); 1957 1958 return SCIP_OKAY; 1959 } 1960 1961 /** add a mod2 row to another one */ 1962 static 1963 SCIP_RETCODE mod2rowAddRow( 1964 SCIP* scip, /**< scip data structure */ 1965 BMS_BLKMEM* blkmem, /**< block memory shell */ 1966 MOD2_MATRIX* mod2matrix, /**< mod 2 matrix */ 1967 MOD2_ROW* row, /**< mod 2 row */ 1968 MOD2_ROW* rowtoadd /**< mod 2 row that is added to the other mod 2 row */ 1969 ) 1970 { 1971 SCIP_Shortbool* contained; 1972 int i; 1973 int j; 1974 int k; 1975 int nnewentries; 1976 int nlprows; 1977 MOD2_COL** newnonzcols; 1978 SCIP_Real newslack; 1979 1980 checkRow(row); 1981 checkRow(rowtoadd); 1982 1983 assert(row->nnonzcols == 0 || row->nonzcols != NULL); 1984 assert(rowtoadd->nnonzcols == 0 || rowtoadd->nonzcols != NULL); 1985 1986 nlprows = SCIPgetNLPRows(scip); 1987 row->rhs ^= rowtoadd->rhs; 1988 1989 newslack = row->slack + rowtoadd->slack; 1990 blkmem = SCIPblkmem(scip); 1991 1992 if( SCIPisZero(scip, row->slack) && !SCIPisZero(scip, newslack) ) 1993 --mod2matrix->nzeroslackrows; 1994 1995 row->slack = newslack; 1996 1997 { 1998 /* the maximum index return by the UNIQUE_INDEX macro is 3 times 1999 * the maximum index value in the ROWINDEX struct. The index value could 2000 * be the lp position of an original row or the index of a transformed row. 2001 * Hence we need to allocate 3 times the maximum of these two possible 2002 * index types. 2003 */ 2004 int allocsize = 3 * MAX(nlprows, mod2matrix->ntransintrows); 2005 SCIP_CALL( SCIPallocCleanBufferArray(scip, &contained, allocsize) ); 2006 } 2007 2008 /* remember entries that are in the row to add */ 2009 for( i = 0; i < rowtoadd->nrowinds; ++i ) 2010 { 2011 contained[UNIQUE_INDEX(rowtoadd->rowinds[i])] = 1; 2012 } 2013 2014 /* remove the entries that are in both rows from the row (1 + 1 = 0 (mod 2)) */ 2015 nnewentries = rowtoadd->nrowinds; 2016 for( i = 0; i < row->nrowinds; ) 2017 { 2018 if( contained[UNIQUE_INDEX(row->rowinds[i])] ) 2019 { 2020 --nnewentries; 2021 contained[UNIQUE_INDEX(row->rowinds[i])] = 0; 2022 --row->nrowinds; 2023 row->rowinds[i] = row->rowinds[row->nrowinds]; 2024 } 2025 else 2026 { 2027 ++i; 2028 } 2029 } 2030 2031 SCIP_CALL( SCIPensureBlockMemoryArray(scip, &row->rowinds, &row->rowindssize, row->nrowinds + nnewentries) ); 2032 2033 /* add remaining entries of row to add */ 2034 for ( i = 0; i < rowtoadd->nrowinds; ++i ) 2035 { 2036 if( contained[UNIQUE_INDEX(rowtoadd->rowinds[i])] ) 2037 { 2038 contained[UNIQUE_INDEX(rowtoadd->rowinds[i])] = 0; 2039 row->rowinds[row->nrowinds++] = rowtoadd->rowinds[i]; 2040 } 2041 } 2042 2043 SCIPfreeCleanBufferArray(scip, &contained); 2044 2045 SCIP_CALL( SCIPallocBufferArray(scip, &newnonzcols, row->nnonzcols + rowtoadd->nnonzcols) ); 2046 2047 i = 0; 2048 j = 0; 2049 k = 0; 2050 row->maxsolval = 0.0; 2051 2052 /* since columns are sorted we can merge them */ 2053 while( i < row->nnonzcols && j < rowtoadd->nnonzcols ) 2054 { 2055 if( row->nonzcols[i] == rowtoadd->nonzcols[j] ) 2056 { 2057 SCIP_CALL( mod2colUnlinkRow(row->nonzcols[i], row) ); 2058 ++i; 2059 ++j; 2060 } 2061 else if( row->nonzcols[i]->index < rowtoadd->nonzcols[j]->index ) 2062 { 2063 row->maxsolval = MAX(row->maxsolval, row->nonzcols[i]->solval); 2064 newnonzcols[k++] = row->nonzcols[i++]; 2065 } 2066 else 2067 { 2068 SCIP_CALL( mod2colLinkRow(blkmem, rowtoadd->nonzcols[j], row) ); 2069 newnonzcols[k++] = rowtoadd->nonzcols[j++]; 2070 } 2071 } 2072 2073 while( i < row->nnonzcols ) 2074 { 2075 row->maxsolval = MAX(row->maxsolval, row->nonzcols[i]->solval); 2076 newnonzcols[k++] = row->nonzcols[i++]; 2077 } 2078 2079 while( j < rowtoadd->nnonzcols ) 2080 { 2081 SCIP_CALL( mod2colLinkRow(blkmem, rowtoadd->nonzcols[j], row) ); 2082 newnonzcols[k++] = rowtoadd->nonzcols[j++]; 2083 } 2084 2085 row->nnonzcols = k; 2086 SCIP_CALL( SCIPensureBlockMemoryArray(scip, &row->nonzcols, &row->nonzcolssize, row->nnonzcols) ); 2087 BMScopyMemoryArray(row->nonzcols, newnonzcols, row->nnonzcols); 2088 2089 SCIPfreeBufferArray(scip, &newnonzcols); 2090 2091 assert(row->nnonzcols == 0 || row->nonzcols != NULL); 2092 checkRow(row); 2093 checkRow(rowtoadd); 2094 2095 return SCIP_OKAY; 2096 } 2097 2098 /* -------------------------------------------------------------------------------------------------------------------- 2099 * callback methods of separator 2100 * -------------------------------------------------------------------------------------------------------------------- */ 2101 2102 /** copy method for separator plugins (called when SCIP copies plugins) */ 2103 static 2104 SCIP_DECL_SEPACOPY(sepaCopyZerohalf) 2105 { /*lint --e{715}*/ 2106 assert(scip != NULL); 2107 assert(sepa != NULL); 2108 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0); 2109 2110 /* call inclusion method of constraint handler */ 2111 SCIP_CALL( SCIPincludeSepaZerohalf(scip) ); 2112 2113 return SCIP_OKAY; 2114 } 2115 2116 /** destructor of separator to free user data (called when SCIP is exiting) */ 2117 static 2118 SCIP_DECL_SEPAFREE(sepaFreeZerohalf) 2119 { 2120 SCIP_SEPADATA* sepadata; 2121 2122 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0); 2123 2124 /* free separator data */ 2125 sepadata = SCIPsepaGetData(sepa); 2126 assert(sepadata != NULL); 2127 2128 SCIPfreeBlockMemory(scip, &sepadata); 2129 SCIPsepaSetData(sepa, NULL); 2130 2131 return SCIP_OKAY; 2132 } 2133 2134 static 2135 SCIP_DECL_SEPAINITSOL(sepaInitsolZerohalf) 2136 { 2137 SCIP_SEPADATA* sepadata; 2138 2139 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0); 2140 2141 /* allocate random generator */ 2142 sepadata = SCIPsepaGetData(sepa); 2143 assert(sepadata != NULL); 2144 2145 assert(sepadata->randnumgen == NULL); 2146 SCIP_CALL( SCIPcreateRandom(scip, &sepadata->randnumgen, (unsigned int)sepadata->initseed, TRUE) ); 2147 2148 return SCIP_OKAY; 2149 } 2150 2151 static 2152 SCIP_DECL_SEPAEXITSOL(sepaExitsolZerohalf) 2153 { 2154 SCIP_SEPADATA* sepadata; 2155 2156 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0); 2157 2158 /* free random generator */ 2159 sepadata = SCIPsepaGetData(sepa); 2160 assert(sepadata != NULL); 2161 2162 SCIPfreeRandom(scip, &sepadata->randnumgen); 2163 2164 return SCIP_OKAY; 2165 } 2166 2167 /** perform the zerohalf cut separation */ 2168 static 2169 SCIP_RETCODE doSeparation( 2170 SCIP* scip, 2171 SCIP_SEPA* sepa, 2172 SCIP_SOL* sol, 2173 SCIP_RESULT* result, 2174 SCIP_Bool allowlocal, 2175 int depth /* current depth */ 2176 ) 2177 { 2178 int i; 2179 int k; 2180 int maxsepacuts; 2181 SCIP_Real maxslack; 2182 SCIP_SEPADATA* sepadata; 2183 MOD2_MATRIX mod2matrix; 2184 MOD2_ROW** nonzrows; 2185 2186 assert(result != NULL); 2187 assert(sepa != NULL); 2188 2189 sepadata = SCIPsepaGetData(sepa); 2190 assert(sepadata != NULL); 2191 2192 { 2193 int ncalls = SCIPsepaGetNCallsAtNode(sepa); 2194 2195 /* only call the zerohalf cut separator a given number of times at each node */ 2196 if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot) 2197 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) ) 2198 return SCIP_OKAY; 2199 2200 maxsepacuts = depth == 0 ? sepadata->maxsepacutsroot : sepadata->maxsepacuts; 2201 maxslack = depth == 0 ? sepadata->maxslackroot : sepadata->maxslack; 2202 maxslack += 2 * SCIPfeastol(scip); 2203 } 2204 2205 *result = SCIP_DIDNOTFIND; 2206 2207 SCIP_CALL( SCIPaggrRowCreate(scip, &sepadata->aggrrow) ); 2208 sepadata->ncuts = 0; 2209 sepadata->cutssize = 0; 2210 sepadata->cuts = NULL; 2211 sepadata->infeasible = FALSE; 2212 2213 SCIP_CALL( buildMod2Matrix(scip, sol, sepadata, SCIPblkmem(scip), &mod2matrix, allowlocal, maxslack) ); 2214 2215 SCIPdebugMsg(scip, "built mod2 matrix (%i rows, %i cols)\n", mod2matrix.nrows, mod2matrix.ncols); 2216 2217 SCIP_CALL( SCIPallocBufferArray(scip, &nonzrows, mod2matrix.nrows) ); 2218 2219 for( k = 0; k < MAXREDUCTIONROUNDS; ++k ) 2220 { 2221 int ncancel; 2222 2223 sepadata->nreductions = 0; 2224 2225 assert(mod2matrix.nzeroslackrows <= mod2matrix.nrows); 2226 SCIP_CALL( mod2matrixPreprocessRows(scip, sol, &mod2matrix, sepa, sepadata, allowlocal) ); 2227 assert(mod2matrix.nzeroslackrows <= mod2matrix.nrows); 2228 2229 SCIPdebugMsg(scip, "preprocessed rows (%i rows, %i cols, %i cuts) \n", mod2matrix.nrows, mod2matrix.ncols, 2230 sepadata->ncuts); 2231 2232 if( mod2matrix.nrows == 0 ) 2233 break; 2234 2235 if( sepadata->ncuts >= sepadata->maxcutcands ) 2236 { 2237 SCIPdebugMsg(scip, "enough cuts, stopping (%i rows, %i cols)\n", mod2matrix.nrows, mod2matrix.ncols); 2238 break; 2239 } 2240 2241 SCIP_CALL( mod2matrixPreprocessColumns(scip, &mod2matrix, sepadata) ); 2242 2243 SCIPdebugMsg(scip, "preprocessed columns (%i rows, %i cols)\n", mod2matrix.nrows, mod2matrix.ncols); 2244 2245 ncancel = mod2matrix.nrows; 2246 if( ncancel > 100 ) 2247 { 2248 ncancel = 100; 2249 SCIPselectPtr((void**) mod2matrix.rows, compareRowSlack, ncancel, mod2matrix.nrows); 2250 } 2251 2252 SCIPsortPtr((void**) mod2matrix.rows, compareRowSlack, ncancel); 2253 2254 if( mod2matrix.ncols == 0 ) 2255 break; 2256 2257 assert(mod2matrix.nzeroslackrows <= mod2matrix.nrows); 2258 2259 /* apply Prop5 */ 2260 for( i = 0; i < ncancel; ++i ) 2261 { 2262 int j; 2263 MOD2_COL* col = NULL; 2264 MOD2_ROW* row = mod2matrix.rows[i]; 2265 2266 if( SCIPisPositive(scip, row->slack) || row->nnonzcols == 0 ) 2267 continue; 2268 2269 SCIPdebugMsg(scip, "processing row %i/%i (%i/%i cuts)\n", i, mod2matrix.nrows, sepadata->ncuts, sepadata->maxcutcands); 2270 2271 for( j = 0; j < row->nnonzcols; ++j ) 2272 { 2273 if( row->nonzcols[j]->solval == row->maxsolval ) /*lint !e777*/ 2274 { 2275 col = row->nonzcols[j]; 2276 break; 2277 } 2278 } 2279 2280 assert( col != NULL ); 2281 2282 { 2283 int nslots; 2284 int nnonzrows; 2285 MOD2_ROW** rows; 2286 2287 ++sepadata->nreductions; 2288 2289 nnonzrows = 0; 2290 /* cppcheck-suppress nullPointer */ 2291 nslots = SCIPhashsetGetNSlots(col->nonzrows); 2292 /* cppcheck-suppress nullPointer */ 2293 rows = (MOD2_ROW**) SCIPhashsetGetSlots(col->nonzrows); 2294 2295 for( j = 0; j < nslots; ++j ) 2296 { 2297 if( rows[j] != NULL && rows[j] != row ) 2298 nonzrows[nnonzrows++] = rows[j]; 2299 } 2300 2301 for( j = 0; j < nnonzrows; ++j ) 2302 { 2303 SCIP_CALL( mod2rowAddRow(scip, SCIPblkmem(scip), &mod2matrix, nonzrows[j], row) ); 2304 } 2305 2306 /* cppcheck-suppress nullPointer */ 2307 row->slack = col->solval; 2308 --mod2matrix.nzeroslackrows; 2309 2310 mod2matrixRemoveCol(scip, &mod2matrix, col); 2311 } 2312 } 2313 2314 SCIPdebugMsg(scip, "applied proposition five (%i rows, %i cols)\n", mod2matrix.nrows, mod2matrix.ncols); 2315 2316 if( sepadata->nreductions == 0 ) 2317 { 2318 SCIPdebugMsg(scip, "no change, stopping (%i rows, %i cols)\n", mod2matrix.nrows, mod2matrix.ncols); 2319 break; 2320 } 2321 } 2322 2323 for( i = 0; i < mod2matrix.nrows && sepadata->ncuts < sepadata->maxcutcands; ++i ) 2324 { 2325 MOD2_ROW* row = mod2matrix.rows[i]; 2326 2327 if( computeMaxViolation(row) < sepadata->minviol ) 2328 break; 2329 2330 if( row->rhs == 0 ) 2331 continue; 2332 2333 SCIP_CALL( generateZerohalfCut(scip, sol, &mod2matrix, sepa, sepadata, allowlocal, row) ); 2334 } 2335 2336 SCIPdebugMsg(scip, "total number of cuts found: %i\n", sepadata->ncuts); 2337 2338 /* If cuts where found we apply a filtering procedure using the scores and the orthogonalities, 2339 * similar to the sepastore. We only add the cuts that make it through this process and discard 2340 * the rest. 2341 */ 2342 if( sepadata->ncuts > 0 ) 2343 { 2344 int nselectedcuts; 2345 2346 SCIP_CALL( SCIPselectCutsHybrid(scip, sepadata->cuts, NULL, sepadata->randnumgen, sepadata->goodscore, sepadata->badscore, 2347 sepadata->goodmaxparall, sepadata->maxparall, sepadata->dircutoffdistweight, sepadata->efficacyweight, sepadata->objparalweight, 0.0, 2348 sepadata->ncuts, 0, maxsepacuts, &nselectedcuts) ); 2349 2350 for( i = 0; i < sepadata->ncuts; ++i ) 2351 { 2352 if( i < nselectedcuts ) 2353 { 2354 /* if selected, add global cuts to the pool and local cuts to the sepastore */ 2355 if( SCIProwIsLocal(sepadata->cuts[i]) ) 2356 { 2357 SCIP_CALL( SCIPaddRow(scip, sepadata->cuts[i], FALSE, &sepadata->infeasible) ); 2358 } 2359 else 2360 { 2361 SCIP_CALL( SCIPaddPoolCut(scip, sepadata->cuts[i]) ); 2362 } 2363 } 2364 2365 /* release current cut */ 2366 SCIP_CALL( SCIPreleaseRow(scip, &sepadata->cuts[i]) ); 2367 } 2368 2369 SCIPfreeBlockMemoryArray(scip, &sepadata->cuts, sepadata->cutssize); 2370 2371 if( sepadata->infeasible ) 2372 *result = SCIP_CUTOFF; 2373 else 2374 *result = SCIP_SEPARATED; 2375 } 2376 2377 SCIPfreeBufferArray(scip, &nonzrows); 2378 SCIPaggrRowFree(scip, &sepadata->aggrrow); 2379 2380 destroyMod2Matrix(scip, &mod2matrix); 2381 2382 return SCIP_OKAY; 2383 } 2384 2385 /** LP solution separation method of separator */ 2386 static 2387 SCIP_DECL_SEPAEXECLP(sepaExeclpZerohalf) 2388 { 2389 assert(result != NULL); 2390 assert(sepa != NULL); 2391 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0); 2392 2393 *result = SCIP_DIDNOTRUN; 2394 2395 /* only call separator, if we are not close to terminating */ 2396 if( SCIPisStopped(scip) ) 2397 return SCIP_OKAY; 2398 2399 /* only call separator, if an optimal LP solution is at hand */ 2400 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL ) 2401 return SCIP_OKAY; 2402 2403 /* only call separator, if there are fractional variables */ 2404 if( SCIPgetNLPBranchCands(scip) == 0 ) 2405 return SCIP_OKAY; 2406 2407 SCIP_CALL( doSeparation(scip, sepa, NULL, result, allowlocal, depth) ); 2408 2409 return SCIP_OKAY; 2410 } 2411 2412 /** custom solution separation method of separator */ 2413 static 2414 SCIP_DECL_SEPAEXECSOL(sepaExecsolZerohalf) 2415 { 2416 assert(result != NULL); 2417 assert(sepa != NULL); 2418 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0); 2419 2420 *result = SCIP_DIDNOTRUN; 2421 2422 /* only call separator, if we are not close to terminating */ 2423 if( SCIPisStopped(scip) ) 2424 return SCIP_OKAY; 2425 2426 SCIP_CALL( doSeparation(scip, sepa, sol, result, allowlocal, depth) ); 2427 2428 return SCIP_OKAY; 2429 } 2430 2431 /** creates the zerohalf separator and includes it in SCIP */ 2432 SCIP_RETCODE SCIPincludeSepaZerohalf( 2433 SCIP* scip /**< SCIP data structure */ 2434 ) 2435 { 2436 SCIP_SEPADATA* sepadata; 2437 SCIP_SEPA* sepa; 2438 2439 /* create zerohalf separator data */ 2440 SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) ); 2441 BMSclearMemory(sepadata); 2442 2443 /* include separator */ 2444 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST, 2445 SEPA_USESSUBSCIP, SEPA_DELAY, sepaExeclpZerohalf, sepaExecsolZerohalf, sepadata) ); 2446 2447 assert(sepa != NULL); 2448 2449 /* set non-NULL pointers to callback methods */ 2450 SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyZerohalf) ); 2451 SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeZerohalf) ); 2452 SCIP_CALL( SCIPsetSepaInitsol(scip, sepa, sepaInitsolZerohalf) ); 2453 SCIP_CALL( SCIPsetSepaExitsol(scip, sepa, sepaExitsolZerohalf) ); 2454 2455 /* add zerohalf separator parameters */ 2456 SCIP_CALL( SCIPaddIntParam(scip, 2457 "separating/" SEPA_NAME "/maxrounds", 2458 "maximal number of zerohalf separation rounds per node (-1: unlimited)", 2459 &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) ); 2460 SCIP_CALL( SCIPaddIntParam(scip, 2461 "separating/" SEPA_NAME "/maxroundsroot", 2462 "maximal number of zerohalf separation rounds in the root node (-1: unlimited)", 2463 &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) ); 2464 SCIP_CALL( SCIPaddIntParam(scip, 2465 "separating/" SEPA_NAME "/maxsepacuts", 2466 "maximal number of zerohalf cuts separated per separation round", 2467 &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, 0, INT_MAX, NULL, NULL) ); 2468 SCIP_CALL( SCIPaddIntParam(scip, 2469 "separating/" SEPA_NAME "/initseed", 2470 "initial seed used for random tie-breaking in cut selection", 2471 &sepadata->initseed, FALSE, DEFAULT_INITSEED, 0, INT_MAX, NULL, NULL) ); 2472 SCIP_CALL( SCIPaddIntParam(scip, 2473 "separating/" SEPA_NAME "/maxsepacutsroot", 2474 "maximal number of zerohalf cuts separated per separation round in the root node", 2475 &sepadata->maxsepacutsroot, FALSE, DEFAULT_MAXSEPACUTSROOT, 0, INT_MAX, NULL, NULL) ); 2476 SCIP_CALL( SCIPaddIntParam(scip, 2477 "separating/" SEPA_NAME "/maxcutcands", 2478 "maximal number of zerohalf cuts considered per separation round", 2479 &sepadata->maxcutcands, FALSE, DEFAULT_MAXCUTCANDS, 0, INT_MAX, NULL, NULL) ); 2480 SCIP_CALL( SCIPaddRealParam(scip, 2481 "separating/" SEPA_NAME "/maxslack", 2482 "maximal slack of rows to be used in aggregation", 2483 &sepadata->maxslack, TRUE, DEFAULT_MAXSLACK, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 2484 SCIP_CALL( SCIPaddRealParam(scip, 2485 "separating/" SEPA_NAME "/maxslackroot", 2486 "maximal slack of rows to be used in aggregation in the root node", 2487 &sepadata->maxslackroot, TRUE, DEFAULT_MAXSLACKROOT, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 2488 SCIP_CALL( SCIPaddRealParam(scip, 2489 "separating/" SEPA_NAME "/goodscore", 2490 "threshold for score of cut relative to best score to be considered good, so that less strict filtering is applied", 2491 &sepadata->goodscore, TRUE, DEFAULT_GOODSCORE, 0.0, 1.0, NULL, NULL) ); 2492 SCIP_CALL( SCIPaddRealParam(scip, 2493 "separating/" SEPA_NAME "/badscore", 2494 "threshold for score of cut relative to best score to be discarded", 2495 &sepadata->badscore, TRUE, DEFAULT_BADSCORE, 0.0, 1.0, NULL, NULL) ); 2496 SCIP_CALL( SCIPaddRealParam(scip, 2497 "separating/" SEPA_NAME "/objparalweight", 2498 "weight of objective parallelism in cut score calculation", 2499 &sepadata->objparalweight, TRUE, DEFAULT_OBJPARALWEIGHT, 0.0, 1.0, NULL, NULL) ); 2500 SCIP_CALL( SCIPaddRealParam(scip, 2501 "separating/" SEPA_NAME "/efficacyweight", 2502 "weight of efficacy in cut score calculation", 2503 &sepadata->efficacyweight, TRUE, DEFAULT_EFFICACYWEIGHT, 0.0, 1.0, NULL, NULL) ); 2504 SCIP_CALL( SCIPaddRealParam(scip, 2505 "separating/" SEPA_NAME "/dircutoffdistweight", 2506 "weight of directed cutoff distance in cut score calculation", 2507 &sepadata->dircutoffdistweight, TRUE, DEFAULT_DIRCUTOFFDISTWEIGHT, 0.0, 1.0, NULL, NULL) ); 2508 SCIP_CALL( SCIPaddRealParam(scip, 2509 "separating/" SEPA_NAME "/goodmaxparall", 2510 "maximum parallelism for good cuts", 2511 &sepadata->goodmaxparall, TRUE, DEFAULT_GOODMAXPARALL, 0.0, 1.0, NULL, NULL) ); 2512 SCIP_CALL( SCIPaddRealParam(scip, 2513 "separating/" SEPA_NAME "/maxparall", 2514 "maximum parallelism for non-good cuts", 2515 &sepadata->maxparall, TRUE, DEFAULT_MAXPARALL, 0.0, 1.0, NULL, NULL) ); 2516 SCIP_CALL( SCIPaddRealParam(scip, 2517 "separating/" SEPA_NAME "/minviol", 2518 "minimal violation to generate zerohalfcut for", 2519 &sepadata->minviol, TRUE, DEFAULT_MINVIOL, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 2520 SCIP_CALL( SCIPaddBoolParam(scip, 2521 "separating/" SEPA_NAME "/dynamiccuts", 2522 "should generated cuts be removed from the LP if they are no longer tight?", 2523 &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) ); 2524 SCIP_CALL( SCIPaddRealParam(scip, 2525 "separating/" SEPA_NAME "/maxrowdensity", 2526 "maximal density of row to be used in aggregation", 2527 &sepadata->maxrowdensity, TRUE, DEFAULT_MAXROWDENSITY, 0.0, 1.0, NULL, NULL) ); 2528 SCIP_CALL( SCIPaddIntParam(scip, 2529 "separating/" SEPA_NAME "/densityoffset", 2530 "additional number of variables allowed in row on top of density", 2531 &sepadata->densityoffset, TRUE, DEFAULT_DENSITYOFFSET, 0, INT_MAX, NULL, NULL) ); 2532 2533 return SCIP_OKAY; 2534 } 2535