SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
{0,1/2}-cuts separator
{0,1/2}-Chvátal-Gomory cuts separator. It solves the following separation problem: Consider an integer program
\[ \min \{ c^T x : Ax \leq b, x \geq 0, x \mbox{ integer} \} \]
and a fractional solution \(x^*\) of its LP relaxation. Find a weightvector \(u\) whose entries \(u_i\) are either 0 or \(\frac{1}{2}\) such that the following inequality is valid for all integral solutions and violated by \(x^*\):
\[ \lfloor(u^T A) x \rfloor \leq \lfloor u^T b\rfloor \]
References:
Definition in file sepa_zerohalf.c.
#include "string.h"#include "scip/sepa_zerohalf.h"#include "scip/cons_linear.h"#include "scip/scipdefplugins.h"#include "scip/struct_lp.h"Go to the source code of this file.
Macros | |
| #define | SEPA_NAME "zerohalf" |
| #define | SEPA_DESC "{0,1/2}-cuts separator" |
| #define | SEPA_PRIORITY -6000 |
| #define | SEPA_FREQ 10 |
| #define | SEPA_MAXBOUNDDIST 1.0 |
| #define | SEPA_USESSUBSCIP FALSE |
| #define | SEPA_DELAY FALSE |
| #define | DEFAULT_MAXROUNDS 5 |
| #define | DEFAULT_MAXROUNDSROOT 20 |
| #define | DEFAULT_MAXSEPACUTS 20 |
| #define | DEFAULT_MAXSEPACUTSROOT 100 |
| #define | DEFAULT_MAXCUTCANDS 2000 |
| #define | DEFAULT_MAXSLACK 0.0 |
| #define | DEFAULT_MAXSLACKROOT 0.0 |
| #define | DEFAULT_GOODSCORE 0.9 |
| #define | DEFAULT_BADSCORE 0.5 |
| #define | DEFAULT_MINVIOL 0.1 |
| #define | DEFAULT_DYNAMICCUTS TRUE |
| #define | DEFAULT_MAXROWDENSITY 0.05 |
| #define | DEFAULT_DENSITYOFFSET 100 |
| #define | MAXDNOM 1000LL |
| #define | MAXSCALE 1000.0 |
| #define | MAXREDUCTIONROUNDS 100 |
| #define | BOUNDSWITCH 0.5 |
| #define | MAXAGGRLEN(nvars) ((int)(0.1*(nvars)+1000)) |
| #define | ROWIND_TYPE unsigned int |
| #define | ORIG_RHS 0u |
| #define | ORIG_LHS 1u |
| #define | TRANSROW 2u |
| #define | UNIQUE_INDEX(rowind) (3*(rowind).index + (rowind).type) |
| #define | COLINFO_GET_MOD2COL(x) ((MOD2_COL*) (((uintptr_t)(x)) & ~((uintptr_t)1))) |
| #define | COLINFO_GET_RHSOFFSET(x) ((int) (((uintptr_t)(x)) & ((uintptr_t)1))) |
| #define | COLINFO_CREATE(mod2col, rhsoffset) ((void*) (((uintptr_t)(mod2col)) | ((uintptr_t)(rhsoffset)))) |
| #define | NONZERO(x) (COPYSIGN(1e-100, (x)) + (x)) |
Typedefs | |
| typedef struct Mod2Col | MOD2_COL |
| typedef struct Mod2Row | MOD2_ROW |
| typedef struct Mod2Matrix | MOD2_MATRIX |
| typedef struct TransIntRow | TRANSINTROW |
| typedef struct RowIndex | ROWINDEX |
Functions | |
| static void | checkRow (MOD2_ROW *row) |
| static | SCIP_DECL_SORTPTRCOMP (compareColIndex) |
| static | SCIP_DECL_SORTPTRCOMP (compareRowSlack) |
| static int | mod2 (SCIP *scip, SCIP_Real val) |
| static void | getIntegralScalar (SCIP_Real val, SCIP_Real scalar, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Real *sval, SCIP_Real *intval) |
| static SCIP_RETCODE | transformNonIntegralRow (SCIP *scip, SCIP_Bool allowlocal, SCIP_Real maxslack, int sign, SCIP_Bool local, int rank, int rowlen, SCIP_Real *rowvals, SCIP_COL **rowcols, SCIP_Real rhs, int *intvarpos, TRANSINTROW *introw, SCIP_Bool *success) |
| static SCIP_RETCODE | mod2MatrixTransformContRows (SCIP *scip, SCIP_SEPADATA *sepadata, MOD2_MATRIX *mod2matrix, SCIP_Bool allowlocal, SCIP_Real maxslack) |
| static SCIP_RETCODE | mod2MatrixAddCol (SCIP *scip, MOD2_MATRIX *mod2matrix, SCIP_HASHMAP *origvar2col, SCIP_VAR *origvar, SCIP_Real solval, int rhsoffset) |
| static SCIP_RETCODE | mod2colLinkRow (BMS_BLKMEM *blkmem, MOD2_COL *col, MOD2_ROW *row) |
| static SCIP_RETCODE | mod2colUnlinkRow (MOD2_COL *col, MOD2_ROW *row) |
| static void | mod2rowUnlinkCol (MOD2_ROW *row, MOD2_COL *col) |
| static SCIP_RETCODE | mod2MatrixAddOrigRow (SCIP *scip, BMS_BLKMEM *blkmem, MOD2_MATRIX *mod2matrix, SCIP_HASHMAP *origcol2col, SCIP_ROW *origrow, SCIP_Real slack, ROWIND_TYPE side, int rhsmod2) |
| static SCIP_RETCODE | mod2MatrixAddTransRow (SCIP *scip, MOD2_MATRIX *mod2matrix, SCIP_HASHMAP *origcol2col, int transrowind) |
| static void | destroyMod2Matrix (SCIP *scip, MOD2_MATRIX *mod2matrix) |
| static SCIP_RETCODE | buildMod2Matrix (SCIP *scip, SCIP_SEPADATA *sepadata, BMS_BLKMEM *blkmem, MOD2_MATRIX *mod2matrix, SCIP_Bool allowlocal, SCIP_Real maxslack) |
| static | SCIP_DECL_HASHKEYEQ (columnsEqual) |
| static | SCIP_DECL_HASHKEYVAL (columnGetSignature) |
| static | SCIP_DECL_HASHKEYEQ (rowsEqual) |
| static | SCIP_DECL_HASHKEYVAL (rowGetSignature) |
| static SCIP_RETCODE | mod2matrixRemoveRow (SCIP *scip, MOD2_MATRIX *mod2matrix, MOD2_ROW *row) |
| static void | mod2matrixRemoveCol (SCIP *scip, MOD2_MATRIX *mod2matrix, MOD2_COL *col) |
| static SCIP_RETCODE | mod2matrixPreprocessColumns (SCIP *scip, MOD2_MATRIX *mod2matrix, SCIP_SEPADATA *sepadata) |
| static void | addOrigRow (SCIP *scip, SCIP_Real *tmpcoefs, SCIP_Real *cutrhs, int *nonzeroinds, int *nnz, int *cutrank, SCIP_Bool *cutislocal, SCIP_ROW *row, int sign) |
| static void | addTransRow (SCIP_Real *tmpcoefs, SCIP_Real *cutrhs, int *nonzeroinds, int *nnz, int *cutrank, SCIP_Bool *cutislocal, TRANSINTROW *introw) |
| static SCIP_Real | calcEfficacy (SCIP *scip, SCIP_Real *cutcoefs, SCIP_Real cutrhs, int *cutinds, int cutnnz) |
| static SCIP_Real | computeMaxViolation (MOD2_ROW *row) |
| static SCIP_Real | computeViolation (MOD2_ROW *row) |
| static SCIP_RETCODE | generateZerohalfCut (SCIP *scip, MOD2_MATRIX *mod2matrix, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_Bool allowlocal, MOD2_ROW *row) |
| static SCIP_RETCODE | mod2matrixPreprocessRows (SCIP *scip, MOD2_MATRIX *mod2matrix, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_Bool allowlocal) |
| static SCIP_RETCODE | mod2rowAddRow (SCIP *scip, BMS_BLKMEM *blkmem, MOD2_MATRIX *mod2matrix, MOD2_ROW *row, MOD2_ROW *rowtoadd) |
| static | SCIP_DECL_SEPACOPY (sepaCopyZerohalf) |
| static | SCIP_DECL_SEPAFREE (sepaFreeZerohalf) |
| static | SCIP_DECL_SEPAEXECLP (sepaExeclpZerohalf) |
| SCIP_RETCODE | SCIPincludeSepaZerohalf (SCIP *scip) |
| #define SEPA_NAME "zerohalf" |
Definition at line 53 of file sepa_zerohalf.c.
Referenced by SCIP_DECL_SEPACOPY(), SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAFREE(), and SCIPincludeSepaZerohalf().
| #define SEPA_DESC "{0,1/2}-cuts separator" |
Definition at line 54 of file sepa_zerohalf.c.
Referenced by SCIPincludeSepaZerohalf().
| #define SEPA_PRIORITY -6000 |
Definition at line 55 of file sepa_zerohalf.c.
Referenced by SCIPincludeSepaZerohalf().
| #define SEPA_FREQ 10 |
Definition at line 56 of file sepa_zerohalf.c.
Referenced by SCIPincludeSepaZerohalf().
| #define SEPA_MAXBOUNDDIST 1.0 |
Definition at line 57 of file sepa_zerohalf.c.
Referenced by SCIPincludeSepaZerohalf().
| #define SEPA_USESSUBSCIP FALSE |
Definition at line 58 of file sepa_zerohalf.c.
Referenced by SCIPincludeSepaZerohalf().
| #define SEPA_DELAY FALSE |
Definition at line 59 of file sepa_zerohalf.c.
Referenced by SCIPincludeSepaZerohalf().
| #define DEFAULT_MAXROUNDS 5 |
maximal number of zerohalf separation rounds per node (-1: unlimited)
Definition at line 61 of file sepa_zerohalf.c.
Referenced by SCIPincludeSepaZerohalf().
| #define DEFAULT_MAXROUNDSROOT 20 |
maximal number of zerohalf separation rounds in the root node (-1: unlimited)
Definition at line 62 of file sepa_zerohalf.c.
Referenced by SCIPincludeSepaZerohalf().
| #define DEFAULT_MAXSEPACUTS 20 |
maximal number of zerohalf cuts separated per separation round
Definition at line 63 of file sepa_zerohalf.c.
Referenced by SCIPincludeSepaZerohalf().
| #define DEFAULT_MAXSEPACUTSROOT 100 |
maximal number of zerohalf cuts separated per separation round in root node
Definition at line 64 of file sepa_zerohalf.c.
Referenced by SCIPincludeSepaZerohalf().
| #define DEFAULT_MAXCUTCANDS 2000 |
maximal number of zerohalf cuts considered per separation round
Definition at line 65 of file sepa_zerohalf.c.
Referenced by SCIPincludeSepaZerohalf().
| #define DEFAULT_MAXSLACK 0.0 |
maximal slack of rows to be used in aggregation
Definition at line 66 of file sepa_zerohalf.c.
Referenced by SCIPincludeSepaZerohalf().
| #define DEFAULT_MAXSLACKROOT 0.0 |
maximal slack of rows to be used in aggregation in the root node
Definition at line 67 of file sepa_zerohalf.c.
Referenced by SCIPincludeSepaZerohalf().
| #define DEFAULT_GOODSCORE 0.9 |
threshold for score of cut relative to best score to be considered good, so that less strict filtering is applied
Definition at line 68 of file sepa_zerohalf.c.
Referenced by SCIPincludeSepaZerohalf().
| #define DEFAULT_BADSCORE 0.5 |
threshold for score of cut relative to best score to be discarded
Definition at line 71 of file sepa_zerohalf.c.
Referenced by SCIPincludeSepaZerohalf().
| #define DEFAULT_MINVIOL 0.1 |
minimal violation to generate zerohalfcut for
Definition at line 72 of file sepa_zerohalf.c.
Referenced by SCIPincludeSepaZerohalf().
| #define DEFAULT_DYNAMICCUTS TRUE |
should generated cuts be removed from the LP if they are no longer tight?
Definition at line 73 of file sepa_zerohalf.c.
Referenced by SCIPincludeSepaZerohalf().
| #define DEFAULT_MAXROWDENSITY 0.05 |
maximal density of row to be used in aggregation
Definition at line 74 of file sepa_zerohalf.c.
Referenced by SCIPincludeSepaZerohalf().
| #define DEFAULT_DENSITYOFFSET 100 |
additional number of variables allowed in row on top of density
Definition at line 75 of file sepa_zerohalf.c.
Referenced by SCIPincludeSepaZerohalf().
| #define MAXDNOM 1000LL |
Definition at line 78 of file sepa_zerohalf.c.
Referenced by transformNonIntegralRow().
| #define MAXSCALE 1000.0 |
Definition at line 79 of file sepa_zerohalf.c.
Referenced by transformNonIntegralRow().
| #define MAXREDUCTIONROUNDS 100 |
maximum number of rounds to perform reductions on the mod 2 system
Definition at line 82 of file sepa_zerohalf.c.
Referenced by SCIP_DECL_SEPAEXECLP().
| #define BOUNDSWITCH 0.5 |
threshold for bound switching
Definition at line 83 of file sepa_zerohalf.c.
Referenced by buildMod2Matrix(), and generateZerohalfCut().
| #define MAXAGGRLEN | ( | nvars | ) | ((int)(0.1*(nvars)+1000)) |
Definition at line 84 of file sepa_zerohalf.c.
Referenced by generateZerohalfCut().
| #define ROWIND_TYPE unsigned int |
enum for different types of row indices in ROWINDEX structure
Definition at line 94 of file sepa_zerohalf.c.
| #define ORIG_RHS 0u |
Definition at line 95 of file sepa_zerohalf.c.
Referenced by buildMod2Matrix(), and generateZerohalfCut().
| #define ORIG_LHS 1u |
Definition at line 96 of file sepa_zerohalf.c.
Referenced by buildMod2Matrix(), and generateZerohalfCut().
| #define TRANSROW 2u |
Definition at line 97 of file sepa_zerohalf.c.
Referenced by generateZerohalfCut(), and mod2MatrixAddTransRow().
| #define UNIQUE_INDEX | ( | rowind | ) | (3*(rowind).index + (rowind).type) |
Definition at line 100 of file sepa_zerohalf.c.
Referenced by mod2rowAddRow().
| #define COLINFO_GET_MOD2COL | ( | x | ) | ((MOD2_COL*) (((uintptr_t)(x)) & ~((uintptr_t)1))) |
Definition at line 189 of file sepa_zerohalf.c.
Referenced by mod2MatrixAddOrigRow(), and mod2MatrixAddTransRow().
| #define COLINFO_GET_RHSOFFSET | ( | x | ) | ((int) (((uintptr_t)(x)) & ((uintptr_t)1))) |
Definition at line 190 of file sepa_zerohalf.c.
Referenced by mod2MatrixAddOrigRow(), and mod2MatrixAddTransRow().
| #define COLINFO_CREATE | ( | mod2col, | |
| rhsoffset | |||
| ) | ((void*) (((uintptr_t)(mod2col)) | ((uintptr_t)(rhsoffset)))) |
Definition at line 191 of file sepa_zerohalf.c.
Referenced by buildMod2Matrix(), and mod2MatrixAddCol().
| #define NONZERO | ( | x | ) | (COPYSIGN(1e-100, (x)) + (x)) |
Definition at line 1426 of file sepa_zerohalf.c.
Referenced by addOrigRow(), and addTransRow().
Definition at line 86 of file sepa_zerohalf.c.
Definition at line 87 of file sepa_zerohalf.c.
| typedef struct Mod2Matrix MOD2_MATRIX |
Definition at line 88 of file sepa_zerohalf.c.
| typedef struct TransIntRow TRANSINTROW |
Definition at line 89 of file sepa_zerohalf.c.
Definition at line 90 of file sepa_zerohalf.c.
|
static |
Definition at line 196 of file sepa_zerohalf.c.
References Mod2Col::index, MAX, Mod2Row::maxsolval, Mod2Row::nnonzcols, Mod2Row::nonzcols, SCIP_DECL_SORTPTRCOMP(), SCIP_Real, and Mod2Col::solval.
Referenced by mod2MatrixAddOrigRow(), mod2MatrixAddTransRow(), mod2matrixPreprocessColumns(), mod2matrixPreprocessRows(), mod2matrixRemoveRow(), and mod2rowAddRow().
|
static |
compare to mod 2 columns by there index
Definition at line 218 of file sepa_zerohalf.c.
References Mod2Col::index.
Referenced by checkRow().
|
static |
comparison function for slack of mod 2 rows
Definition at line 236 of file sepa_zerohalf.c.
References EPSZ, Mod2Row::maxsolval, mod2(), Mod2Row::nnonzcols, SCIP_Bool, SCIP_DEFAULT_EPSILON, and Mod2Row::slack.
take integral real value modulo 2
| scip | scip data structure |
| val | value to take mod 2 |
Definition at line 274 of file sepa_zerohalf.c.
References getIntegralScalar(), REALABS, SCIPisFeasIntegral(), and SCIPround().
Referenced by buildMod2Matrix(), mod2MatrixAddOrigRow(), mod2MatrixAddTransRow(), and SCIP_DECL_SORTPTRCOMP().
|
static |
returns the integral value for the given scaling parameters, see SCIPcalcIntegralScalar()
| val | value that should be scaled to an integral value |
| scalar | scalar that should be tried |
| mindelta | minimal relative allowed difference of scaled coefficient s*c and integral i |
| maxdelta | maximal relative allowed difference of scaled coefficient s*c and integral i |
| sval | pointer to store the scaled value |
| intval | pointer to store the scaled integral value |
Definition at line 286 of file sepa_zerohalf.c.
References SCIP_Real, SCIPrelDiff(), and transformNonIntegralRow().
Referenced by mod2(), and transformNonIntegralRow().
|
static |
Tries to transform a non-integral row into an integral row that can be used in zerohalf separation
| scip | scip data structure |
| allowlocal | should local cuts be allowed |
| maxslack | maximum slack allowed for transformed row |
| sign | +1 or -1 scale to select the side of the row |
| local | is the row only valid locally? |
| rank | rank of row |
| rowlen | length of row |
| rowvals | coefficients of columns in row |
| rowcols | columns of row |
| rhs | right hand side of row |
| intvarpos | clean buffer array of size SCIPgetNVars that will be clean when the function returns |
| introw | pointer to return transformed row |
| success | pointer to return whether the transformation succeeded |
Definition at line 318 of file sepa_zerohalf.c.
References FALSE, getIntegralScalar(), TransIntRow::len, TransIntRow::local, MAXDNOM, MAXSCALE, mod2MatrixTransformContRows(), TransIntRow::rank, REALABS, TransIntRow::rhs, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPcalcIntegralScalar(), SCIPcolGetVar(), SCIPcolIsIntegral(), SCIPcutsTightenCoefficients(), SCIPepsilon(), SCIPfeasFloor(), SCIPfreeBlockMemoryArray, SCIPgetVarClosestVlb(), SCIPgetVarClosestVub(), SCIPgetVars(), SCIPgetVarSol(), SCIPisEQ(), SCIPisGT(), SCIPisInfinity(), SCIPisLT(), SCIPisSumEQ(), SCIPisSumGT(), SCIPisSumLT(), SCIPisZero(), SCIPsumepsilon(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), sign(), TransIntRow::size, TransIntRow::slack, TRUE, TransIntRow::vals, SCIP_Col::var_probindex, and TransIntRow::varinds.
Referenced by getIntegralScalar(), and mod2MatrixTransformContRows().
|
static |
Tries to transform non-integral rows into an integral form by using simple and variable bounds
| scip | scip data structure |
| sepadata | zerohalf separator data |
| mod2matrix | mod2 matrix structure |
| allowlocal | should local cuts be allowed |
| maxslack | maximum slack allowed for mod 2 rows |
Definition at line 604 of file sepa_zerohalf.c.
References mod2MatrixAddCol(), Mod2Matrix::ntransintrows, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPallocCleanBufferArray, SCIPfreeCleanBufferArray, SCIPgetLPRowsData(), SCIPgetNLPCols(), SCIPgetNVars(), SCIPgetRowLPActivity(), SCIPinfinity(), SCIPisInfinity(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetNLPNonz(), SCIProwGetNNonz(), SCIProwGetRank(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsIntegral(), SCIProwIsLocal(), SCIProwIsModifiable(), transformNonIntegralRow(), and Mod2Matrix::transintrows.
Referenced by buildMod2Matrix(), and transformNonIntegralRow().
|
static |
adds new column to the mod 2 matrix
| scip | SCIP datastructure |
| mod2matrix | mod 2 matrix |
| origvar2col | hash map for mapping of problem variables to mod 2 columns |
| origvar | problem variable to create mod 2 column for |
| solval | solution value of problem variable |
| rhsoffset | offset in right hand side due complementation (mod 2) |
Definition at line 696 of file sepa_zerohalf.c.
References COLINFO_CREATE, Mod2Matrix::cols, Mod2Matrix::colssize, Mod2Col::index, mod2colLinkRow(), Mod2Matrix::ncols, Mod2Col::nonzrows, Mod2Col::pos, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPblkmem(), SCIPensureBlockMemoryArray, SCIPhashmapInsert(), SCIPhashsetCreate(), SCIPvarGetProbindex(), and Mod2Col::solval.
Referenced by buildMod2Matrix(), and mod2MatrixTransformContRows().
|
static |
links row to mod 2 column
| blkmem | block memory shell |
| col | mod 2 column |
| row | mod 2 row |
Definition at line 728 of file sepa_zerohalf.c.
References MAX, Mod2Row::maxsolval, mod2colUnlinkRow(), Mod2Col::nonzrows, SCIP_CALL, SCIP_OKAY, SCIPhashsetExists(), SCIPhashsetInsert(), and Mod2Col::solval.
Referenced by mod2MatrixAddCol(), mod2MatrixAddOrigRow(), mod2MatrixAddTransRow(), and mod2rowAddRow().
|
static |
unlinks row from mod 2 column
| col | mod 2 column |
| row | mod 2 row |
Definition at line 745 of file sepa_zerohalf.c.
References mod2rowUnlinkCol(), Mod2Col::nonzrows, SCIP_CALL, SCIP_OKAY, SCIPhashsetExists(), SCIPhashsetGetNSlots(), SCIPhashsetGetSlots(), and SCIPhashsetRemove().
Referenced by mod2colLinkRow(), mod2matrixRemoveRow(), and mod2rowAddRow().
unlinks row from mod 2 column
| row | mod 2 row |
| col | mod 2 column |
Definition at line 771 of file sepa_zerohalf.c.
References BMSmoveMemoryArray, MAX, Mod2Row::maxsolval, mod2MatrixAddOrigRow(), Mod2Row::nnonzcols, Mod2Row::nonzcols, SCIP_UNUSED, SCIPsortedvecFindPtr(), and Mod2Col::solval.
Referenced by mod2colUnlinkRow(), and mod2matrixRemoveCol().
|
static |
adds a SCIP_ROW to the mod 2 matrix
| scip | scip data structure |
| blkmem | block memory shell |
| mod2matrix | modulo 2 matrix |
| origcol2col | hashmap to retrieve the mod 2 column from a SCIP_COL |
| origrow | original SCIP row |
| slack | slack of row |
| side | side of row that is used for mod 2 row, must be ORIG_RHS or ORIG_LHS |
| rhsmod2 | modulo 2 value of the row's right hand side |
Definition at line 798 of file sepa_zerohalf.c.
References BMSallocBlockMemory, checkRow(), COLINFO_GET_MOD2COL, COLINFO_GET_RHSOFFSET, RowIndex::index, Mod2Row::index, MAX, Mod2Row::maxsolval, mod2(), mod2colLinkRow(), mod2MatrixAddTransRow(), Mod2Row::nnonzcols, Mod2Row::nonzcols, Mod2Row::nonzcolssize, Mod2Row::nrowinds, Mod2Matrix::nrows, Mod2Matrix::nzeroslackrows, Mod2Row::rhs, Mod2Row::rowinds, Mod2Row::rowindssize, Mod2Matrix::rows, Mod2Matrix::rowssize, SCIP_ALLOC, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcolGetVar(), SCIPensureBlockMemoryArray, SCIPhashmapGetImage(), SCIPisZero(), SCIProwGetCols(), SCIProwGetLPPos(), SCIProwGetNNonz(), SCIProwGetVals(), SCIPsortPtr(), Mod2Row::slack, and RowIndex::type.
Referenced by buildMod2Matrix(), and mod2rowUnlinkCol().
|
static |
adds a transformed integral row to the mod 2 matrix
| scip | scip data structure |
| mod2matrix | modulo 2 matrix |
| origcol2col | hashmap to retrieve the mod 2 column from a SCIP_COL |
| transrowind | index to transformed int row |
Definition at line 883 of file sepa_zerohalf.c.
References checkRow(), COLINFO_GET_MOD2COL, COLINFO_GET_RHSOFFSET, destroyMod2Matrix(), RowIndex::index, Mod2Row::index, TransIntRow::len, MAX, Mod2Row::maxsolval, mod2(), mod2colLinkRow(), Mod2Row::nnonzcols, Mod2Row::nonzcols, Mod2Row::nonzcolssize, Mod2Row::nrowinds, Mod2Matrix::nrows, Mod2Matrix::nzeroslackrows, TransIntRow::rhs, Mod2Row::rhs, Mod2Row::rowinds, Mod2Row::rowindssize, Mod2Matrix::rows, Mod2Matrix::rowssize, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPblkmem(), SCIPensureBlockMemoryArray, SCIPgetVars(), SCIPhashmapGetImage(), SCIPisZero(), SCIPsortPtr(), TransIntRow::slack, Mod2Row::slack, Mod2Matrix::transintrows, TRANSROW, RowIndex::type, TransIntRow::vals, and TransIntRow::varinds.
Referenced by buildMod2Matrix(), and mod2MatrixAddOrigRow().
|
static |
free all resources held by the mod 2 matrix
| scip | scip data structure |
| mod2matrix | pointer to mod2 matrix structure |
Definition at line 964 of file sepa_zerohalf.c.
References buildMod2Matrix(), Mod2Matrix::cols, Mod2Matrix::colssize, Mod2Matrix::ncols, Mod2Row::nonzcols, Mod2Row::nonzcolssize, Mod2Col::nonzrows, Mod2Matrix::nrows, Mod2Matrix::ntransintrows, Mod2Row::rowinds, Mod2Row::rowindssize, Mod2Matrix::rows, Mod2Matrix::rowssize, SCIPblkmem(), SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPgetNLPRows(), SCIPhashsetFree(), TransIntRow::size, Mod2Matrix::transintrows, TransIntRow::vals, and TransIntRow::varinds.
Referenced by mod2MatrixAddTransRow(), and SCIP_DECL_SEPAEXECLP().
|
static |
build the modulo 2 matrix from all integral rows in the LP, and non-integral rows if the transformation to an integral row succeeds
| scip | scip data structure |
| sepadata | zerohalf separator data |
| blkmem | block memory shell |
| mod2matrix | mod 2 matrix |
| allowlocal | should local cuts be allowed |
| maxslack | maximum slack allowed for mod 2 rows |
Definition at line 1000 of file sepa_zerohalf.c.
References BOUNDSWITCH, COLINFO_CREATE, Mod2Matrix::cols, Mod2Matrix::colssize, FALSE, MAX, mod2(), mod2MatrixAddCol(), mod2MatrixAddOrigRow(), mod2MatrixAddTransRow(), mod2MatrixTransformContRows(), Mod2Matrix::ncols, Mod2Matrix::nrows, Mod2Matrix::ntransintrows, Mod2Matrix::nzeroslackrows, ORIG_LHS, ORIG_RHS, Mod2Matrix::rows, Mod2Matrix::rowssize, SCIP_Bool, SCIP_CALL, SCIP_DECL_HASHKEYEQ(), SCIP_OKAY, SCIP_Real, SCIPblkmem(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPgetNContVars(), SCIPgetNLPCols(), SCIPgetNVars(), SCIPgetRowLPActivity(), SCIPgetVars(), SCIPgetVarSol(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapInsert(), SCIPinfinity(), SCIPisEQ(), SCIPisInfinity(), SCIPisLT(), SCIPisZero(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwIsIntegral(), SCIProwIsLocal(), SCIProwIsModifiable(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by destroyMod2Matrix(), and SCIP_DECL_SEPAEXECLP().
|
static |
Definition at line 1174 of file sepa_zerohalf.c.
References FALSE, Mod2Col::nonzrows, SCIP_DECL_HASHKEYVAL(), SCIPhashsetExists(), SCIPhashsetGetNElements(), SCIPhashsetGetNSlots(), SCIPhashsetGetSlots(), and TRUE.
Referenced by buildMod2Matrix(), and SCIP_DECL_HASHKEYVAL().
|
static |
Definition at line 1201 of file sepa_zerohalf.c.
References RowIndex::index, Mod2Col::nonzrows, SCIP_DECL_HASHKEYEQ(), SCIPhashsetGetNSlots(), SCIPhashsetGetSlots(), and SCIPhashSignature64.
Referenced by SCIP_DECL_HASHKEYEQ().
|
static |
Definition at line 1226 of file sepa_zerohalf.c.
References FALSE, Mod2Row::nnonzcols, Mod2Row::nonzcols, Mod2Row::rhs, SCIP_DECL_HASHKEYVAL(), and TRUE.
|
static |
Definition at line 1254 of file sepa_zerohalf.c.
References Mod2Col::index, mod2matrixRemoveRow(), Mod2Row::nnonzcols, Mod2Row::nonzcols, Mod2Row::rhs, and SCIPhashSignature64.
|
static |
removes a row from the mod 2 matrix
| scip | scip data structure |
| mod2matrix | the mod 2 matrix |
| row | mod 2 row |
Definition at line 1273 of file sepa_zerohalf.c.
References checkRow(), mod2colUnlinkRow(), mod2matrixRemoveCol(), Mod2Row::nnonzcols, Mod2Row::nonzcols, Mod2Row::nonzcolssize, Mod2Matrix::nrows, Mod2Matrix::nzeroslackrows, Mod2Row::pos, Mod2Row::rowinds, Mod2Row::rowindssize, Mod2Matrix::rows, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPisZero(), and Mod2Row::slack.
Referenced by mod2matrixPreprocessRows(), and SCIP_DECL_HASHKEYVAL().
|
static |
removes a column from the mod 2 matrix
| scip | scip data structure |
| mod2matrix | the mod 2 matrix |
| col | a column in the mod 2 matrix |
Definition at line 1309 of file sepa_zerohalf.c.
References Mod2Matrix::cols, mod2matrixPreprocessColumns(), mod2rowUnlinkCol(), Mod2Matrix::ncols, Mod2Col::nonzrows, Mod2Col::pos, SCIPblkmem(), SCIPfreeBlockMemory, SCIPhashsetFree(), SCIPhashsetGetNSlots(), and SCIPhashsetGetSlots().
Referenced by mod2matrixPreprocessColumns(), mod2matrixRemoveRow(), and SCIP_DECL_SEPAEXECLP().
|
static |
| scip | scip data structure |
| mod2matrix | mod 2 matrix |
| sepadata | zerohalf separator data |
Definition at line 1349 of file sepa_zerohalf.c.
References checkRow(), Mod2Matrix::cols, mod2matrixRemoveCol(), Mod2Matrix::ncols, Mod2Col::nonzrows, Mod2Matrix::nzeroslackrows, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPhashsetGetNElements(), SCIPhashsetGetSlots(), SCIPhashtableCreate(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRetrieve(), SCIPisZero(), Mod2Row::slack, and Mod2Col::solval.
Referenced by mod2matrixRemoveCol(), and SCIP_DECL_SEPAEXECLP().
|
static |
add original row to aggregation with weight 0.5
| scip | SCIP datastructure |
| tmpcoefs | array to add coefficients to |
| cutrhs | pointer to add right hand side |
| nonzeroinds | array of non-zeros in the aggregation |
| nnz | pointer to update number of non-zeros |
| cutrank | pointer to update cut rank |
| cutislocal | pointer to update local flag |
| row | row to add |
| sign | sign for weight, i.e. +1 to use right hand side or -1 to use left hand side |
Definition at line 1430 of file sepa_zerohalf.c.
References addTransRow(), SCIP_Row::cols, SCIP_Row::constant, SCIP_Row::len, SCIP_Row::lhs, SCIP_Row::local, MAX, NONZERO, SCIP_Row::rank, SCIP_Row::rhs, SCIP_Real, SCIPfeasCeil(), SCIPfeasFloor(), sign(), SCIP_Row::vals, and SCIP_Col::var_probindex.
Referenced by generateZerohalfCut().
|
static |
add transformed integral row to aggregation with weight 0.5
| tmpcoefs | array to add coefficients to |
| cutrhs | pointer to add right hand side |
| nonzeroinds | array of non-zeros in the aggregation |
| nnz | pointer to update number of non-zeros |
| cutrank | pointer to update cut rank |
| cutislocal | pointer to update local flag |
| introw | transformed integral row to add to the aggregation |
Definition at line 1475 of file sepa_zerohalf.c.
References calcEfficacy(), TransIntRow::len, TransIntRow::local, MAX, NONZERO, TransIntRow::rank, TransIntRow::rhs, SCIP_Real, TransIntRow::vals, and TransIntRow::varinds.
Referenced by addOrigRow(), and generateZerohalfCut().
|
static |
| scip | SCIP data structure |
| cutcoefs | array of the non-zero coefficients in the cut |
| cutrhs | the right hand side of the cut |
| cutinds | array of the problem indices of variables with a non-zero coefficient in the cut |
| cutnnz | the number of non-zeros in the cut |
Definition at line 1509 of file sepa_zerohalf.c.
References computeMaxViolation(), MAX, SCIP_Real, SCIPgetVars(), SCIPgetVarSol(), and SCIPgetVectorEfficacyNorm().
Referenced by addTransRow(), and generateZerohalfCut().
computes maximal violation that can be achieved for zerohalf cuts where this row particiaptes
| row | mod 2 row |
Definition at line 1538 of file sepa_zerohalf.c.
References computeViolation(), SCIP_Real, and Mod2Row::slack.
Referenced by calcEfficacy(), mod2matrixPreprocessRows(), and SCIP_DECL_SEPAEXECLP().
computes violation of zerohalf cut generated from given mod 2 row
| row | mod 2 row |
Definition at line 1552 of file sepa_zerohalf.c.
References generateZerohalfCut(), Mod2Row::nnonzcols, Mod2Row::nonzcols, SCIP_Real, Mod2Row::slack, and Mod2Col::solval.
Referenced by computeMaxViolation(), and generateZerohalfCut().
|
static |
generate a zerohalf cut from a given mod 2 row, i.e., try if aggregations of rows of the mod2 matrix give violated cuts
| scip | scip data structure |
| mod2matrix | mod 2 matrix |
| sepa | zerohalf separator |
| sepadata | zerohalf separator data |
| allowlocal | should local cuts be allowed |
| row | mod 2 row |
Definition at line 1575 of file sepa_zerohalf.c.
References addOrigRow(), addTransRow(), BOUNDSWITCH, calcEfficacy(), computeViolation(), FALSE, RowIndex::index, Mod2Row::index, TransIntRow::len, MAXAGGRLEN, mod2matrixPreprocessRows(), Mod2Row::nrowinds, ORIG_LHS, ORIG_RHS, REALABS, TransIntRow::rhs, Mod2Row::rhs, Mod2Row::rowinds, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPABORT, SCIPaddVarToRow(), SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPcacheRowExtensions(), SCIPcalcMemGrowSize(), SCIPcreateEmptyRowSepa(), SCIPcutsTightenCoefficients(), SCIPdebugMsg, SCIPfeasFloor(), SCIPfeasRound(), SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPgetLPRows(), SCIPgetNLPCols(), SCIPgetNLPs(), SCIPgetNVars(), SCIPgetVars(), SCIPgetVarSol(), SCIPinfinity(), SCIPisCutNew(), SCIPisEfficacious(), SCIPisFeasEQ(), SCIPisFeasIntegral(), SCIPisGT(), SCIPisInfinity(), SCIPisLT(), SCIPreallocBlockMemoryArray, SCIPreleaseRow(), SCIProwChgRank(), SCIProwIsLocal(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TransIntRow::slack, Mod2Matrix::transintrows, TRANSROW, TRUE, and RowIndex::type.
Referenced by computeViolation(), mod2matrixPreprocessRows(), and SCIP_DECL_SEPAEXECLP().
|
static |
remove rows that are (a) zero (b) identical to other rows (keep the one with smallest slack) (c) have slack greater 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)
| scip | scip data structure |
| mod2matrix | the mod 2 matrix |
| sepa | the zerohalf separator |
| sepadata | data of the zerohalf separator |
| allowlocal | should local cuts be allowed |
Definition at line 1827 of file sepa_zerohalf.c.
References checkRow(), computeMaxViolation(), generateZerohalfCut(), mod2matrixRemoveRow(), mod2rowAddRow(), Mod2Row::nnonzcols, Mod2Row::nonzcols, Mod2Matrix::nrows, Mod2Row::pos, Mod2Row::rhs, Mod2Matrix::rows, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPhashtableCreate(), SCIPhashtableExists(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRemove(), SCIPhashtableRetrieve(), SCIPisLT(), SCIPswapInts(), SCIPswapPointers(), and Mod2Row::slack.
Referenced by generateZerohalfCut(), and SCIP_DECL_SEPAEXECLP().
|
static |
add a mod2 row to another one
| scip | scip data structure |
| blkmem | block memory shell |
| mod2matrix | mod 2 matrix |
| row | mod 2 row |
| rowtoadd | mod 2 row that is added to the other mod 2 row |
Definition at line 1918 of file sepa_zerohalf.c.
References BMScopyMemoryArray, checkRow(), Mod2Col::index, MAX, Mod2Row::maxsolval, mod2colLinkRow(), mod2colUnlinkRow(), Mod2Row::nnonzcols, Mod2Row::nonzcols, Mod2Row::nonzcolssize, Mod2Row::nrowinds, Mod2Matrix::ntransintrows, Mod2Matrix::nzeroslackrows, Mod2Row::rhs, Mod2Row::rowinds, Mod2Row::rowindssize, SCIP_CALL, SCIP_DECL_SEPACOPY(), SCIP_OKAY, SCIP_Real, SCIP_Shortbool, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPblkmem(), SCIPensureBlockMemoryArray, SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPgetNLPRows(), SCIPisZero(), Mod2Row::slack, Mod2Col::solval, and UNIQUE_INDEX.
Referenced by mod2matrixPreprocessRows(), and SCIP_DECL_SEPAEXECLP().
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 2059 of file sepa_zerohalf.c.
References SCIP_CALL, SCIP_DECL_SEPAFREE(), SCIP_OKAY, SCIPincludeSepaZerohalf(), SCIPsepaGetName(), and SEPA_NAME.
Referenced by mod2rowAddRow().
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 2073 of file sepa_zerohalf.c.
References SCIP_DECL_SEPAEXECLP(), SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), and SEPA_NAME.
Referenced by SCIP_DECL_SEPACOPY().
|
static |
LP solution separation method of separator
Definition at line 2091 of file sepa_zerohalf.c.
References buildMod2Matrix(), computeMaxViolation(), destroyMod2Matrix(), FALSE, generateZerohalfCut(), MAXREDUCTIONROUNDS, Mod2Row::maxsolval, mod2matrixPreprocessColumns(), mod2matrixPreprocessRows(), mod2matrixRemoveCol(), mod2rowAddRow(), Mod2Matrix::ncols, Mod2Row::nnonzcols, Mod2Row::nonzcols, Mod2Col::nonzrows, Mod2Matrix::nrows, Mod2Matrix::nzeroslackrows, Mod2Row::rhs, Mod2Matrix::rows, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPaddPoolCut(), SCIPaddRow(), SCIPaggrRowCreate(), SCIPaggrRowFree(), SCIPallocBufferArray, SCIPblkmem(), SCIPdebugMsg, SCIPfeastol(), SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPgetDepth(), SCIPgetLPSolstat(), SCIPgetNLPBranchCands(), SCIPhashsetGetNSlots(), SCIPhashsetGetSlots(), SCIPincludeSepaZerohalf(), SCIPisPositive(), SCIPisStopped(), SCIPreleaseRow(), SCIProwGetOrthogonality(), SCIProwIsLocal(), SCIPselectPtr(), SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaGetNCallsAtNode(), SCIPsortDownRealPtr(), SCIPsortPtr(), SEPA_NAME, Mod2Row::slack, and Mod2Col::solval.
Referenced by SCIP_DECL_SEPAFREE().