SCIP
Solving Constraint Integer Programs
sepa_zerohalf.c File Reference
Detailed Description
{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:
- Alberto Caprara, Matteo Fischetti. {0,1/2}-Chvatal-Gomory cuts. Math. Programming, Volume 74, p221–235, 1996.
- Arie M. C. A. Koster, Adrian Zymolka and Manuel Kutschka.
Algorithms to separate {0,1/2}-Chvatal-Gomory cuts. Algorithms - ESA 2007: 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007,
Proceedings. Lecture Notes in Computer Science, Volume 4698, p. 693–704, 2007. - Arie M. C. A. Koster, Adrian Zymolka and Manuel Kutschka.
Algorithms to separate {0,1/2}-Chvatal-Gomory cuts (Extended Version).
ZIB Report 07-10, Zuse Institute Berlin, 2007. http://www.zib.de/Publications/Reports/ZR-07-10.pdf - Manuel Kutschka. Algorithmen zur Separierung von {0,1/2}-Schnitten. Diplomarbeit. Technische Universitaet Berlin, 2007.
Definition in file sepa_zerohalf.c.
#include "string.h"#include "scip/sepa_zerohalf.h"#include "scip/scipdefplugins.h"#include "scip/cutsel_hybrid.h"Go to the source code of this file.
Data Structures | |
| struct | RowIndex |
| struct | TransIntRow |
| struct | Mod2Row |
| struct | Mod2Col |
| struct | Mod2Matrix |
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 1.0 |
| #define | DEFAULT_BADSCORE 0.5 |
| #define | DEFAULT_MINVIOL 0.1 |
| #define | DEFAULT_DYNAMICCUTS TRUE |
| #define | DEFAULT_MAXROWDENSITY 0.05 |
| #define | DEFAULT_DENSITYOFFSET 100 |
| #define | DEFAULT_INITSEED 0x5EED |
| #define | DEFAULT_OBJPARALWEIGHT 0.0 |
| #define | DEFAULT_EFFICACYWEIGHT 1.0 |
| #define | DEFAULT_DIRCUTOFFDISTWEIGHT 0.0 |
| #define | DEFAULT_GOODMAXPARALL 0.1 |
| #define | DEFAULT_MAXPARALL 0.1 |
| #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_SOL *sol, 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_SOL *sol, 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_SOL *sol, 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_SOL *sol, 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, SCIP_SOL *sol, MOD2_MATRIX *mod2matrix, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_Bool allowlocal, MOD2_ROW *row) |
| static SCIP_RETCODE | mod2matrixPreprocessRows (SCIP *scip, SCIP_SOL *sol, 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_SEPAINITSOL (sepaInitsolZerohalf) |
| static | SCIP_DECL_SEPAEXITSOL (sepaExitsolZerohalf) |
| static SCIP_RETCODE | doSeparation (SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_Bool allowlocal, int depth) |
| static | SCIP_DECL_SEPAEXECLP (sepaExeclpZerohalf) |
| static | SCIP_DECL_SEPAEXECSOL (sepaExecsolZerohalf) |
| SCIP_RETCODE | SCIPincludeSepaZerohalf (SCIP *scip) |
Macro Definition Documentation
◆ SEPA_NAME
| #define SEPA_NAME "zerohalf" |
Definition at line 62 of file sepa_zerohalf.c.
◆ SEPA_DESC
| #define SEPA_DESC "{0,1/2}-cuts separator" |
Definition at line 63 of file sepa_zerohalf.c.
◆ SEPA_PRIORITY
| #define SEPA_PRIORITY -6000 |
Definition at line 64 of file sepa_zerohalf.c.
◆ SEPA_FREQ
| #define SEPA_FREQ 10 |
Definition at line 65 of file sepa_zerohalf.c.
◆ SEPA_MAXBOUNDDIST
| #define SEPA_MAXBOUNDDIST 1.0 |
Definition at line 66 of file sepa_zerohalf.c.
◆ SEPA_USESSUBSCIP
| #define SEPA_USESSUBSCIP FALSE |
Definition at line 67 of file sepa_zerohalf.c.
◆ SEPA_DELAY
| #define SEPA_DELAY FALSE |
Definition at line 68 of file sepa_zerohalf.c.
◆ DEFAULT_MAXROUNDS
| #define DEFAULT_MAXROUNDS 5 |
maximal number of zerohalf separation rounds per node (-1: unlimited)
Definition at line 70 of file sepa_zerohalf.c.
◆ DEFAULT_MAXROUNDSROOT
| #define DEFAULT_MAXROUNDSROOT 20 |
maximal number of zerohalf separation rounds in the root node (-1: unlimited)
Definition at line 71 of file sepa_zerohalf.c.
◆ DEFAULT_MAXSEPACUTS
| #define DEFAULT_MAXSEPACUTS 20 |
maximal number of zerohalf cuts separated per separation round
Definition at line 72 of file sepa_zerohalf.c.
◆ DEFAULT_MAXSEPACUTSROOT
| #define DEFAULT_MAXSEPACUTSROOT 100 |
maximal number of zerohalf cuts separated per separation round in root node
Definition at line 73 of file sepa_zerohalf.c.
◆ DEFAULT_MAXCUTCANDS
| #define DEFAULT_MAXCUTCANDS 2000 |
maximal number of zerohalf cuts considered per separation round
Definition at line 74 of file sepa_zerohalf.c.
◆ DEFAULT_MAXSLACK
| #define DEFAULT_MAXSLACK 0.0 |
maximal slack of rows to be used in aggregation
Definition at line 75 of file sepa_zerohalf.c.
◆ DEFAULT_MAXSLACKROOT
| #define DEFAULT_MAXSLACKROOT 0.0 |
maximal slack of rows to be used in aggregation in the root node
Definition at line 76 of file sepa_zerohalf.c.
◆ DEFAULT_GOODSCORE
| #define DEFAULT_GOODSCORE 1.0 |
threshold for score of cut relative to best score to be considered good, so that less strict filtering is applied
Definition at line 78 of file sepa_zerohalf.c.
◆ DEFAULT_BADSCORE
| #define DEFAULT_BADSCORE 0.5 |
threshold for score of cut relative to best score to be discarded
Definition at line 79 of file sepa_zerohalf.c.
◆ DEFAULT_MINVIOL
| #define DEFAULT_MINVIOL 0.1 |
minimal violation to generate zerohalfcut for
Definition at line 80 of file sepa_zerohalf.c.
◆ DEFAULT_DYNAMICCUTS
| #define DEFAULT_DYNAMICCUTS TRUE |
should generated cuts be removed from the LP if they are no longer tight?
Definition at line 81 of file sepa_zerohalf.c.
◆ DEFAULT_MAXROWDENSITY
| #define DEFAULT_MAXROWDENSITY 0.05 |
maximal density of row to be used in aggregation
Definition at line 82 of file sepa_zerohalf.c.
◆ DEFAULT_DENSITYOFFSET
| #define DEFAULT_DENSITYOFFSET 100 |
additional number of variables allowed in row on top of density
Definition at line 83 of file sepa_zerohalf.c.
◆ DEFAULT_INITSEED
| #define DEFAULT_INITSEED 0x5EED |
default initial seed used for random tie-breaking in cut selection
Definition at line 84 of file sepa_zerohalf.c.
◆ DEFAULT_OBJPARALWEIGHT
| #define DEFAULT_OBJPARALWEIGHT 0.0 |
weight of objective parallelism in cut score calculation
Definition at line 85 of file sepa_zerohalf.c.
◆ DEFAULT_EFFICACYWEIGHT
| #define DEFAULT_EFFICACYWEIGHT 1.0 |
weight of efficacy in cut score calculation
Definition at line 86 of file sepa_zerohalf.c.
◆ DEFAULT_DIRCUTOFFDISTWEIGHT
| #define DEFAULT_DIRCUTOFFDISTWEIGHT 0.0 |
weight of directed cutoff distance in cut score calculation
Definition at line 87 of file sepa_zerohalf.c.
◆ DEFAULT_GOODMAXPARALL
| #define DEFAULT_GOODMAXPARALL 0.1 |
maximum parallelism for good cuts
Definition at line 88 of file sepa_zerohalf.c.
◆ DEFAULT_MAXPARALL
| #define DEFAULT_MAXPARALL 0.1 |
maximum parallelism for non-good cuts
Definition at line 89 of file sepa_zerohalf.c.
◆ MAXDNOM
| #define MAXDNOM 1000LL |
Definition at line 92 of file sepa_zerohalf.c.
◆ MAXSCALE
| #define MAXSCALE 1000.0 |
Definition at line 93 of file sepa_zerohalf.c.
◆ MAXREDUCTIONROUNDS
| #define MAXREDUCTIONROUNDS 100 |
maximum number of rounds to perform reductions on the mod 2 system
Definition at line 96 of file sepa_zerohalf.c.
◆ BOUNDSWITCH
| #define BOUNDSWITCH 0.5 |
threshold for bound switching
Definition at line 97 of file sepa_zerohalf.c.
◆ MAXAGGRLEN
| #define MAXAGGRLEN | ( | nvars | ) | ((int)(0.1*(nvars)+1000)) |
Definition at line 98 of file sepa_zerohalf.c.
◆ ROWIND_TYPE
| #define ROWIND_TYPE unsigned int |
enum for different types of row indices in ROWINDEX structure
Definition at line 108 of file sepa_zerohalf.c.
◆ ORIG_RHS
| #define ORIG_RHS 0u |
Definition at line 109 of file sepa_zerohalf.c.
◆ ORIG_LHS
| #define ORIG_LHS 1u |
Definition at line 110 of file sepa_zerohalf.c.
◆ TRANSROW
| #define TRANSROW 2u |
Definition at line 111 of file sepa_zerohalf.c.
◆ UNIQUE_INDEX
| #define UNIQUE_INDEX | ( | rowind | ) | (3*(rowind).index + (rowind).type) |
Definition at line 114 of file sepa_zerohalf.c.
◆ COLINFO_GET_MOD2COL
Definition at line 209 of file sepa_zerohalf.c.
◆ COLINFO_GET_RHSOFFSET
Definition at line 210 of file sepa_zerohalf.c.
◆ COLINFO_CREATE
| #define COLINFO_CREATE | ( | mod2col, | |
| rhsoffset | |||
| ) | ((void*) (((uintptr_t)(mod2col)) | ((uintptr_t)(rhsoffset)))) |
Definition at line 211 of file sepa_zerohalf.c.
◆ NONZERO
Typedef Documentation
◆ MOD2_COL
Definition at line 100 of file sepa_zerohalf.c.
◆ MOD2_ROW
Definition at line 101 of file sepa_zerohalf.c.
◆ MOD2_MATRIX
| typedef struct Mod2Matrix MOD2_MATRIX |
Definition at line 102 of file sepa_zerohalf.c.
◆ TRANSINTROW
| typedef struct TransIntRow TRANSINTROW |
Definition at line 103 of file sepa_zerohalf.c.
◆ ROWINDEX
Definition at line 104 of file sepa_zerohalf.c.
Function Documentation
◆ checkRow()
|
static |
Definition at line 216 of file sepa_zerohalf.c.
References Mod2Col::index, MAX, Mod2Row::maxsolval, Mod2Row::nnonzcols, Mod2Row::nonzcols, SCIP_Real, and Mod2Col::solval.
Referenced by mod2MatrixAddOrigRow(), mod2MatrixAddTransRow(), mod2matrixPreprocessColumns(), mod2matrixPreprocessRows(), mod2matrixRemoveRow(), and mod2rowAddRow().
◆ SCIP_DECL_SORTPTRCOMP() [1/2]
|
static |
compare to mod 2 columns by there index
Definition at line 238 of file sepa_zerohalf.c.
References Mod2Col::index.
◆ SCIP_DECL_SORTPTRCOMP() [2/2]
|
static |
comparison function for slack of mod 2 rows
Definition at line 256 of file sepa_zerohalf.c.
References EPSZ, Mod2Row::maxsolval, Mod2Row::nnonzcols, SCIP_Bool, SCIP_DEFAULT_EPSILON, and Mod2Row::slack.
◆ mod2()
take integral real value modulo 2
- Parameters
-
scip scip data structure val value to take mod 2
Definition at line 294 of file sepa_zerohalf.c.
References REALABS, SCIPisFeasIntegral(), and SCIPround().
Referenced by buildMod2Matrix(), mod2MatrixAddOrigRow(), and mod2MatrixAddTransRow().
◆ getIntegralScalar()
|
static |
returns the integral value for the given scaling parameters, see SCIPcalcIntegralScalar()
- Parameters
-
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 306 of file sepa_zerohalf.c.
References SCIP_Real, and SCIPrelDiff().
Referenced by transformNonIntegralRow().
◆ transformNonIntegralRow()
|
static |
Tries to transform a non-integral row into an integral row that can be used in zerohalf separation
- Parameters
-
scip scip data structure sol solution to separate, or NULL for LP solution 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 338 of file sepa_zerohalf.c.
References FALSE, getIntegralScalar(), TransIntRow::len, TransIntRow::local, MAXDNOM, MAXSCALE, NULL, TransIntRow::rank, REALABS, TransIntRow::rhs, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPcalcIntegralScalar(), SCIPcolGetVar(), SCIPcolGetVarProbindex(), SCIPcolIsIntegral(), SCIPcutsTightenCoefficients(), SCIPepsilon(), SCIPfeasFloor(), SCIPfreeBlockMemoryArray, SCIPgetSolVal(), SCIPgetVarClosestVlb(), SCIPgetVarClosestVub(), SCIPgetVars(), SCIPisEQ(), SCIPisGT(), SCIPisInfinity(), SCIPisLT(), SCIPisSumEQ(), SCIPisSumGT(), SCIPisSumLT(), SCIPisZero(), SCIPsumepsilon(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), TransIntRow::size, TransIntRow::slack, TRUE, TransIntRow::vals, and TransIntRow::varinds.
Referenced by mod2MatrixTransformContRows().
◆ mod2MatrixTransformContRows()
|
static |
Tries to transform non-integral rows into an integral form by using simple and variable bounds
- Parameters
-
scip scip data structure sol solution to separate, or NULL for LP solution 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 628 of file sepa_zerohalf.c.
References Mod2Matrix::ntransintrows, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPallocCleanBufferArray, SCIPfreeCleanBufferArray, SCIPgetLPRowsData(), SCIPgetNLPCols(), SCIPgetNVars(), SCIPgetRowSolActivity(), SCIPinfinity(), SCIPisInfinity(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetNLPNonz(), SCIProwGetNNonz(), SCIProwGetRank(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsIntegral(), SCIProwIsLocal(), SCIProwIsModifiable(), transformNonIntegralRow(), and Mod2Matrix::transintrows.
Referenced by buildMod2Matrix().
◆ mod2MatrixAddCol()
|
static |
adds new column to the mod 2 matrix
- Parameters
-
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 721 of file sepa_zerohalf.c.
References COLINFO_CREATE, Mod2Matrix::cols, Mod2Matrix::colssize, Mod2Col::index, Mod2Matrix::ncols, Mod2Col::nonzrows, Mod2Col::pos, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPblkmem(), SCIPensureBlockMemoryArray, SCIPhashmapInsert(), SCIPhashsetCreate(), SCIPvarGetProbindex(), and Mod2Col::solval.
Referenced by buildMod2Matrix().
◆ mod2colLinkRow()
|
static |
links row to mod 2 column
- Parameters
-
blkmem block memory shell col mod 2 column row mod 2 row
Definition at line 754 of file sepa_zerohalf.c.
References MAX, Mod2Row::maxsolval, Mod2Col::nonzrows, SCIP_CALL, SCIP_OKAY, SCIPhashsetExists(), SCIPhashsetInsert(), and Mod2Col::solval.
Referenced by mod2MatrixAddOrigRow(), mod2MatrixAddTransRow(), and mod2rowAddRow().
◆ mod2colUnlinkRow()
|
static |
unlinks row from mod 2 column
- Parameters
-
col mod 2 column row mod 2 row
Definition at line 771 of file sepa_zerohalf.c.
References Mod2Col::nonzrows, SCIP_CALL, SCIP_OKAY, SCIPhashsetExists(), SCIPhashsetGetNSlots(), SCIPhashsetGetSlots(), and SCIPhashsetRemove().
Referenced by mod2matrixRemoveRow(), and mod2rowAddRow().
◆ mod2rowUnlinkCol()
unlinks row from mod 2 column
- Parameters
-
row mod 2 row col mod 2 column
Definition at line 797 of file sepa_zerohalf.c.
References BMSmoveMemoryArray, MAX, Mod2Row::maxsolval, Mod2Row::nnonzcols, Mod2Row::nonzcols, NULL, SCIP_UNUSED, SCIPsortedvecFindPtr(), and Mod2Col::solval.
Referenced by mod2matrixRemoveCol().
◆ mod2MatrixAddOrigRow()
|
static |
adds a SCIP_ROW to the mod 2 matrix
- Parameters
-
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 824 of file sepa_zerohalf.c.
References BMSallocBlockMemory, checkRow(), COLINFO_GET_MOD2COL, COLINFO_GET_RHSOFFSET, RowIndex::index, Mod2Row::index, MAX, Mod2Row::maxsolval, mod2(), mod2colLinkRow(), Mod2Row::nnonzcols, Mod2Row::nonzcols, Mod2Row::nonzcolssize, Mod2Row::nrowinds, Mod2Matrix::nrows, NULL, 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().
◆ mod2MatrixAddTransRow()
|
static |
adds a transformed integral row to the mod 2 matrix
- Parameters
-
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 909 of file sepa_zerohalf.c.
References checkRow(), COLINFO_GET_MOD2COL, COLINFO_GET_RHSOFFSET, RowIndex::index, Mod2Row::index, TransIntRow::len, MAX, Mod2Row::maxsolval, mod2(), mod2colLinkRow(), Mod2Row::nnonzcols, Mod2Row::nonzcols, Mod2Row::nonzcolssize, Mod2Row::nrowinds, Mod2Matrix::nrows, NULL, 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().
◆ destroyMod2Matrix()
|
static |
free all resources held by the mod 2 matrix
- Parameters
-
scip scip data structure mod2matrix pointer to mod2 matrix structure
Definition at line 990 of file sepa_zerohalf.c.
References 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 doSeparation().
◆ buildMod2Matrix()
|
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
- Parameters
-
scip scip data structure sol solution to separate, or NULL for LP solution 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 1026 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, NULL, Mod2Matrix::nzeroslackrows, ORIG_LHS, ORIG_RHS, Mod2Matrix::rows, Mod2Matrix::rowssize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPblkmem(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPgetNContVars(), SCIPgetNLPCols(), SCIPgetNVars(), SCIPgetRowSolActivity(), SCIPgetSolVal(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapInsert(), SCIPinfinity(), SCIPisEQ(), SCIPisInfinity(), SCIPisLT(), SCIPisZero(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwIsIntegral(), SCIProwIsLocal(), SCIProwIsModifiable(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by doSeparation().
◆ SCIP_DECL_HASHKEYEQ() [1/2]
|
static |
Definition at line 1209 of file sepa_zerohalf.c.
References FALSE, Mod2Col::nonzrows, NULL, SCIPhashsetExists(), SCIPhashsetGetNElements(), SCIPhashsetGetNSlots(), SCIPhashsetGetSlots(), and TRUE.
◆ SCIP_DECL_HASHKEYVAL() [1/2]
|
static |
Definition at line 1236 of file sepa_zerohalf.c.
References Mod2Col::nonzrows, NULL, SCIPhashsetGetNSlots(), SCIPhashsetGetSlots(), and SCIPhashSignature64.
◆ SCIP_DECL_HASHKEYEQ() [2/2]
|
static |
Definition at line 1261 of file sepa_zerohalf.c.
References FALSE, Mod2Row::nnonzcols, Mod2Row::nonzcols, NULL, Mod2Row::rhs, and TRUE.
◆ SCIP_DECL_HASHKEYVAL() [2/2]
|
static |
Definition at line 1289 of file sepa_zerohalf.c.
References Mod2Col::index, Mod2Row::nnonzcols, Mod2Row::nonzcols, NULL, Mod2Row::rhs, and SCIPhashSignature64.
◆ mod2matrixRemoveRow()
|
static |
removes a row from the mod 2 matrix
- Parameters
-
scip scip data structure mod2matrix the mod 2 matrix row mod 2 row
Definition at line 1308 of file sepa_zerohalf.c.
References checkRow(), mod2colUnlinkRow(), 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().
◆ mod2matrixRemoveCol()
|
static |
removes a column from the mod 2 matrix
- Parameters
-
scip scip data structure mod2matrix the mod 2 matrix col a column in the mod 2 matrix
Definition at line 1344 of file sepa_zerohalf.c.
References Mod2Matrix::cols, mod2rowUnlinkCol(), Mod2Matrix::ncols, Mod2Col::nonzrows, NULL, Mod2Col::pos, SCIPblkmem(), SCIPfreeBlockMemory, SCIPhashsetFree(), SCIPhashsetGetNSlots(), and SCIPhashsetGetSlots().
Referenced by doSeparation(), and mod2matrixPreprocessColumns().
◆ mod2matrixPreprocessColumns()
|
static |
- Parameters
-
scip scip data structure mod2matrix mod 2 matrix sepadata zerohalf separator data
Definition at line 1384 of file sepa_zerohalf.c.
References checkRow(), Mod2Matrix::cols, mod2matrixRemoveCol(), Mod2Matrix::ncols, Mod2Col::nonzrows, NULL, Mod2Matrix::nzeroslackrows, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPhashsetGetNElements(), SCIPhashsetGetSlots(), SCIPhashtableCreate(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRetrieve(), SCIPisZero(), Mod2Row::slack, and Mod2Col::solval.
Referenced by doSeparation().
◆ addOrigRow()
|
static |
add original row to aggregation with weight 0.5
- Parameters
-
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 1465 of file sepa_zerohalf.c.
References NONZERO, SCIP_Real, SCIPcolGetVarProbindex(), SCIPfeasCeil(), SCIPfeasFloor(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetNNonz(), SCIProwGetRank(), SCIProwGetRhs(), SCIProwGetVals(), and SCIProwIsLocal().
Referenced by generateZerohalfCut().
◆ addTransRow()
|
static |
add transformed integral row to aggregation with weight 0.5
- Parameters
-
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 1519 of file sepa_zerohalf.c.
References TransIntRow::len, TransIntRow::local, MAX, NONZERO, TransIntRow::rank, TransIntRow::rhs, SCIP_Real, TransIntRow::vals, and TransIntRow::varinds.
Referenced by generateZerohalfCut().
◆ calcEfficacy()
|
static |
- Parameters
-
scip SCIP data structure sol solution to separate, or NULL for LP solution 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 1553 of file sepa_zerohalf.c.
References MAX, NULL, SCIP_Real, SCIPgetSolVal(), SCIPgetVars(), and SCIPgetVectorEfficacyNorm().
Referenced by generateZerohalfCut().
◆ computeMaxViolation()
computes maximal violation that can be achieved for zerohalf cuts where this row particiaptes
- Parameters
-
row mod 2 row
Definition at line 1583 of file sepa_zerohalf.c.
References SCIP_Real, and Mod2Row::slack.
Referenced by doSeparation(), and mod2matrixPreprocessRows().
◆ computeViolation()
computes violation of zerohalf cut generated from given mod 2 row
- Parameters
-
row mod 2 row
Definition at line 1597 of file sepa_zerohalf.c.
References Mod2Row::nnonzcols, Mod2Row::nonzcols, SCIP_Real, Mod2Row::slack, and Mod2Col::solval.
Referenced by generateZerohalfCut().
◆ 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
- Parameters
-
scip scip data structure sol solution to separate, or NULL for LP solution mod2matrix mod 2 matrix sepa zerohalf separator sepadata zerohalf separator data allowlocal should local cuts be allowed row mod 2 row
Definition at line 1620 of file sepa_zerohalf.c.
References addOrigRow(), addTransRow(), BOUNDSWITCH, calcEfficacy(), computeViolation(), FALSE, RowIndex::index, Mod2Row::index, TransIntRow::len, MAXAGGRLEN, Mod2Row::nrowinds, ORIG_LHS, ORIG_RHS, REALABS, TransIntRow::rhs, Mod2Row::rhs, Mod2Row::rowinds, SCIP_Bool, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPABORT, SCIPaddVarToRow(), SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPcacheRowExtensions(), SCIPcalcMemGrowSize(), SCIPcreateEmptyRowSepa(), SCIPcutsTightenCoefficients(), SCIPdebugMsg, SCIPfeasFloor(), SCIPfeasRound(), SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPgetLPRows(), SCIPgetNLPCols(), SCIPgetNLPs(), SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPinfinity(), SCIPisCutNew(), SCIPisEfficacious(), SCIPisFeasEQ(), SCIPisFeasIntegral(), SCIPisGT(), SCIPisInfinity(), SCIPisLT(), SCIPreallocBlockMemoryArray, SCIPreleaseRow(), SCIProwChgRank(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TransIntRow::slack, Mod2Matrix::transintrows, TRANSROW, TRUE, and RowIndex::type.
Referenced by doSeparation(), and mod2matrixPreprocessRows().
◆ mod2matrixPreprocessRows()
|
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)
- Parameters
-
scip scip data structure sol solution to separate, or NULL for LP solution mod2matrix the mod 2 matrix sepa the zerohalf separator sepadata data of the zerohalf separator allowlocal should local cuts be allowed
Definition at line 1871 of file sepa_zerohalf.c.
References checkRow(), computeMaxViolation(), generateZerohalfCut(), mod2matrixRemoveRow(), Mod2Row::nnonzcols, Mod2Row::nonzcols, Mod2Matrix::nrows, NULL, 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 doSeparation().
◆ mod2rowAddRow()
|
static |
add a mod2 row to another one
- Parameters
-
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 1963 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, NULL, Mod2Matrix::nzeroslackrows, Mod2Row::rhs, Mod2Row::rowinds, Mod2Row::rowindssize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_Shortbool, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPblkmem(), SCIPensureBlockMemoryArray, SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPgetNLPRows(), SCIPisZero(), Mod2Row::slack, Mod2Col::solval, and UNIQUE_INDEX.
Referenced by doSeparation().
◆ SCIP_DECL_SEPACOPY()
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 2104 of file sepa_zerohalf.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaZerohalf(), SCIPsepaGetName(), and SEPA_NAME.
◆ SCIP_DECL_SEPAFREE()
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 2118 of file sepa_zerohalf.c.
References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), and SEPA_NAME.
◆ SCIP_DECL_SEPAINITSOL()
|
static |
Definition at line 2135 of file sepa_zerohalf.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPsepaGetData(), SCIPsepaGetName(), SEPA_NAME, and TRUE.
◆ SCIP_DECL_SEPAEXITSOL()
|
static |
Definition at line 2152 of file sepa_zerohalf.c.
References NULL, SCIP_OKAY, SCIPfreeRandom(), SCIPsepaGetData(), SCIPsepaGetName(), and SEPA_NAME.
◆ doSeparation()
|
static |
perform the zerohalf cut separation
Definition at line 2169 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, NULL, Mod2Matrix::nzeroslackrows, Mod2Row::rhs, Mod2Matrix::rows, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPaddPoolCut(), SCIPaddRow(), SCIPaggrRowCreate(), SCIPaggrRowFree(), SCIPallocBufferArray, SCIPblkmem(), SCIPdebugMsg, SCIPfeastol(), SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPhashsetGetNSlots(), SCIPhashsetGetSlots(), SCIPisPositive(), SCIPreleaseRow(), SCIProwIsLocal(), SCIPselectCutsHybrid(), SCIPselectPtr(), SCIPsepaGetData(), SCIPsepaGetNCallsAtNode(), SCIPsortPtr(), Mod2Row::slack, and Mod2Col::solval.
Referenced by SCIP_DECL_SEPAEXECLP(), and SCIP_DECL_SEPAEXECSOL().
◆ SCIP_DECL_SEPAEXECLP()
|
static |
LP solution separation method of separator
Definition at line 2387 of file sepa_zerohalf.c.
References doSeparation(), NULL, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIPgetLPSolstat(), SCIPgetNLPBranchCands(), SCIPisStopped(), SCIPsepaGetName(), and SEPA_NAME.
◆ SCIP_DECL_SEPAEXECSOL()
|
static |
custom solution separation method of separator
Definition at line 2414 of file sepa_zerohalf.c.
References doSeparation(), NULL, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIPisStopped(), SCIPsepaGetName(), and SEPA_NAME.