{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/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 |
#define SEPA_NAME "zerohalf" |
Definition at line 62 of file sepa_zerohalf.c.
#define SEPA_DESC "{0,1/2}-cuts separator" |
Definition at line 63 of file sepa_zerohalf.c.
#define SEPA_PRIORITY -6000 |
Definition at line 64 of file sepa_zerohalf.c.
#define SEPA_FREQ 10 |
Definition at line 65 of file sepa_zerohalf.c.
#define SEPA_MAXBOUNDDIST 1.0 |
Definition at line 66 of file sepa_zerohalf.c.
#define SEPA_USESSUBSCIP FALSE |
Definition at line 67 of file sepa_zerohalf.c.
#define SEPA_DELAY FALSE |
Definition at line 68 of file sepa_zerohalf.c.
#define DEFAULT_MAXROUNDS 5 |
maximal number of zerohalf separation rounds per node (-1: unlimited)
Definition at line 70 of file sepa_zerohalf.c.
#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.
#define DEFAULT_MAXSEPACUTS 20 |
maximal number of zerohalf cuts separated per separation round
Definition at line 72 of file sepa_zerohalf.c.
#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.
#define DEFAULT_MAXCUTCANDS 2000 |
maximal number of zerohalf cuts considered per separation round
Definition at line 74 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 75 of file sepa_zerohalf.c.
#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.
#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 77 of file sepa_zerohalf.c.
#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.
#define DEFAULT_MINVIOL 0.1 |
minimal violation to generate zerohalfcut for
Definition at line 80 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 81 of file sepa_zerohalf.c.
#define DEFAULT_MAXROWDENSITY 0.05 |
maximal density of row to be used in aggregation
Definition at line 82 of file sepa_zerohalf.c.
#define DEFAULT_DENSITYOFFSET 100 |
additional number of variables allowed in row on top of density
Definition at line 83 of file sepa_zerohalf.c.
#define DEFAULT_INITSEED 0x5EED |
default initial seed used for random tie-breaking in cut selection
Definition at line 84 of file sepa_zerohalf.c.
#define DEFAULT_OBJPARALWEIGHT 0.0 |
weight of objective parallelism in cut score calculation
Definition at line 85 of file sepa_zerohalf.c.
#define DEFAULT_EFFICACYWEIGHT 1.0 |
weight of efficacy in cut score calculation
Definition at line 86 of file sepa_zerohalf.c.
#define DEFAULT_DIRCUTOFFDISTWEIGHT 0.0 |
weight of directed cutoff distance in cut score calculation
Definition at line 87 of file sepa_zerohalf.c.
#define DEFAULT_GOODMAXPARALL 0.1 |
maximum parallelism for good cuts
Definition at line 88 of file sepa_zerohalf.c.
#define DEFAULT_MAXPARALL 0.1 |
maximum parallelism for non-good cuts
Definition at line 89 of file sepa_zerohalf.c.
#define MAXDNOM 1000LL |
Definition at line 92 of file sepa_zerohalf.c.
#define MAXSCALE 1000.0 |
Definition at line 93 of file sepa_zerohalf.c.
#define MAXREDUCTIONROUNDS 100 |
maximum number of rounds to perform reductions on the mod 2 system
Definition at line 96 of file sepa_zerohalf.c.
Referenced by doSeparation().
#define BOUNDSWITCH 0.5 |
threshold for bound switching
Definition at line 97 of file sepa_zerohalf.c.
#define MAXAGGRLEN | ( | nvars | ) |
Definition at line 98 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 108 of file sepa_zerohalf.c.
Referenced by mod2MatrixAddOrigRow().
#define ORIG_RHS 0u |
Definition at line 109 of file sepa_zerohalf.c.
Referenced by buildMod2Matrix(), and generateZerohalfCut().
#define ORIG_LHS 1u |
Definition at line 110 of file sepa_zerohalf.c.
Referenced by buildMod2Matrix(), and generateZerohalfCut().
#define TRANSROW 2u |
Definition at line 111 of file sepa_zerohalf.c.
Referenced by generateZerohalfCut(), and mod2MatrixAddTransRow().
#define UNIQUE_INDEX | ( | rowind | ) |
Definition at line 114 of file sepa_zerohalf.c.
Referenced by mod2rowAddRow().
#define COLINFO_GET_MOD2COL | ( | x | ) |
Definition at line 209 of file sepa_zerohalf.c.
Referenced by mod2MatrixAddOrigRow(), and mod2MatrixAddTransRow().
#define COLINFO_GET_RHSOFFSET | ( | x | ) |
Definition at line 210 of file sepa_zerohalf.c.
Referenced by mod2MatrixAddOrigRow(), and mod2MatrixAddTransRow().
#define COLINFO_CREATE | ( | mod2col, | |
rhsoffset ) |
Definition at line 211 of file sepa_zerohalf.c.
Referenced by buildMod2Matrix(), and mod2MatrixAddCol().
#define NONZERO | ( | x | ) |
Definition at line 1461 of file sepa_zerohalf.c.
Referenced by addOrigRow(), and addTransRow().
Definition at line 100 of file sepa_zerohalf.c.
Definition at line 101 of file sepa_zerohalf.c.
typedef struct Mod2Matrix MOD2_MATRIX |
Definition at line 102 of file sepa_zerohalf.c.
typedef struct TransIntRow TRANSINTROW |
Definition at line 103 of file sepa_zerohalf.c.
Definition at line 104 of file sepa_zerohalf.c.
|
static |
Definition at line 216 of file sepa_zerohalf.c.
References assert(), i, Mod2Col::index, MAX, Mod2Row::maxsolval, Mod2Row::nnonzcols, Mod2Row::nonzcols, SCIP_Real, and Mod2Col::solval.
|
static |
compare to mod 2 columns by there index
Definition at line 238 of file sepa_zerohalf.c.
References Mod2Col::index.
|
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.
take integral real value modulo 2
scip | scip data structure |
val | value to take mod 2 |
Definition at line 294 of file sepa_zerohalf.c.
References assert(), REALABS, SCIP_Real, SCIPisFeasIntegral(), and SCIPround().
Referenced by buildMod2Matrix(), mod2MatrixAddOrigRow(), and mod2MatrixAddTransRow().
|
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 306 of file sepa_zerohalf.c.
References assert(), SCIP_Real, and SCIPrelDiff().
Referenced by transformNonIntegralRow().
|
static |
Tries to transform a non-integral row into an integral row that can be used in zerohalf separation
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 assert(), FALSE, getIntegralScalar(), i, 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, sol, TRUE, TransIntRow::vals, TransIntRow::varinds, and vars.
Referenced by mod2MatrixTransformContRows().
|
static |
Tries to transform non-integral rows into an integral form by using simple and variable bounds
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 assert(), i, 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(), sepadata, sol, transformNonIntegralRow(), and Mod2Matrix::transintrows.
Referenced by buildMod2Matrix().
|
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 721 of file sepa_zerohalf.c.
References assert(), COLINFO_CREATE, Mod2Matrix::cols, Mod2Matrix::colssize, Mod2Col::index, Mod2Matrix::ncols, Mod2Col::nonzrows, Mod2Col::pos, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPblkmem(), SCIPensureBlockMemoryArray, SCIPhashmapInsert(), SCIPhashsetCreate(), SCIPvarGetProbindex(), and Mod2Col::solval.
Referenced by buildMod2Matrix().
|
static |
links row to mod 2 column
blkmem | block memory shell |
col | mod 2 column |
row | mod 2 row |
Definition at line 754 of file sepa_zerohalf.c.
References assert(), MAX, Mod2Row::maxsolval, Mod2Col::nonzrows, SCIP_CALL, SCIP_OKAY, SCIPhashsetExists(), SCIPhashsetInsert(), and Mod2Col::solval.
Referenced by mod2MatrixAddOrigRow(), mod2MatrixAddTransRow(), and mod2rowAddRow().
|
static |
unlinks row from mod 2 column
col | mod 2 column |
row | mod 2 row |
Definition at line 771 of file sepa_zerohalf.c.
References assert(), i, Mod2Col::nonzrows, SCIP_CALL, SCIP_OKAY, SCIPhashsetExists(), SCIPhashsetGetNSlots(), SCIPhashsetGetSlots(), and SCIPhashsetRemove().
Referenced by mod2matrixRemoveRow(), and mod2rowAddRow().
unlinks row from mod 2 column
row | mod 2 row |
col | mod 2 column |
Definition at line 797 of file sepa_zerohalf.c.
References assert(), BMSmoveMemoryArray, i, MAX, Mod2Row::maxsolval, Mod2Row::nnonzcols, Mod2Row::nonzcols, NULL, SCIP_UNUSED, SCIPsortedvecFindPtr(), and Mod2Col::solval.
Referenced by 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 824 of file sepa_zerohalf.c.
References BMSallocBlockMemory, checkRow, COLINFO_GET_MOD2COL, COLINFO_GET_RHSOFFSET, i, Mod2Row::index, RowIndex::index, MAX, Mod2Row::maxsolval, mod2(), mod2colLinkRow(), Mod2Row::nnonzcols, Mod2Row::nonzcols, Mod2Row::nonzcolssize, Mod2Row::nrowinds, Mod2Matrix::nrows, NULL, Mod2Matrix::nzeroslackrows, Mod2Row::rhs, ROWIND_TYPE, 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().
|
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 909 of file sepa_zerohalf.c.
References checkRow, COLINFO_GET_MOD2COL, COLINFO_GET_RHSOFFSET, i, Mod2Row::index, RowIndex::index, TransIntRow::len, MAX, Mod2Row::maxsolval, mod2(), mod2colLinkRow(), Mod2Row::nnonzcols, Mod2Row::nonzcols, Mod2Row::nonzcolssize, Mod2Row::nrowinds, Mod2Matrix::nrows, NULL, Mod2Matrix::nzeroslackrows, Mod2Row::rhs, TransIntRow::rhs, Mod2Row::rowinds, Mod2Row::rowindssize, Mod2Matrix::rows, Mod2Matrix::rowssize, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPblkmem(), SCIPensureBlockMemoryArray, SCIPgetVars(), SCIPhashmapGetImage(), SCIPisZero(), SCIPsortPtr(), Mod2Row::slack, TransIntRow::slack, Mod2Matrix::transintrows, TRANSROW, RowIndex::type, TransIntRow::vals, TransIntRow::varinds, and vars.
Referenced by buildMod2Matrix().
|
static |
free all resources held by the mod 2 matrix
scip | scip data structure |
mod2matrix | pointer to mod2 matrix structure |
Definition at line 990 of file sepa_zerohalf.c.
References Mod2Matrix::cols, Mod2Matrix::colssize, i, 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().
|
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 |
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 assert(), BOUNDSWITCH, COLINFO_CREATE, Mod2Matrix::cols, Mod2Matrix::colssize, FALSE, i, MAX, mod2(), mod2MatrixAddCol(), mod2MatrixAddOrigRow(), mod2MatrixAddTransRow(), mod2MatrixTransformContRows(), Mod2Matrix::ncols, nintvars, Mod2Matrix::nrows, Mod2Matrix::ntransintrows, NULL, Mod2Matrix::nzeroslackrows, ORIG_LHS, ORIG_RHS, primsol, 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(), sepadata, sol, TRUE, and vars.
Referenced by doSeparation().
|
static |
Definition at line 1209 of file sepa_zerohalf.c.
References FALSE, i, Mod2Col::nonzrows, NULL, SCIPhashsetExists(), SCIPhashsetGetNElements(), SCIPhashsetGetNSlots(), SCIPhashsetGetSlots(), and TRUE.
|
static |
Definition at line 1236 of file sepa_zerohalf.c.
References i, Mod2Col::nonzrows, NULL, SCIPhashsetGetNSlots(), SCIPhashsetGetSlots(), and SCIPhashSignature64.
|
static |
Definition at line 1261 of file sepa_zerohalf.c.
References assert(), FALSE, i, Mod2Row::nnonzcols, Mod2Row::nonzcols, NULL, Mod2Row::rhs, and TRUE.
|
static |
Definition at line 1289 of file sepa_zerohalf.c.
References assert(), i, Mod2Col::index, Mod2Row::nnonzcols, Mod2Row::nonzcols, NULL, 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 1308 of file sepa_zerohalf.c.
References checkRow, i, 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().
|
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 1344 of file sepa_zerohalf.c.
References assert(), Mod2Matrix::cols, i, mod2rowUnlinkCol(), Mod2Matrix::ncols, Mod2Col::nonzrows, NULL, Mod2Col::pos, SCIPblkmem(), SCIPfreeBlockMemory, SCIPhashsetFree(), SCIPhashsetGetNSlots(), and SCIPhashsetGetSlots().
Referenced by doSeparation(), and mod2matrixPreprocessColumns().
|
static |
scip | scip data structure |
mod2matrix | mod 2 matrix |
sepadata | zerohalf separator data |
Definition at line 1384 of file sepa_zerohalf.c.
References assert(), checkRow, Mod2Matrix::cols, i, mod2matrixRemoveCol(), Mod2Matrix::ncols, Mod2Col::nonzrows, NULL, Mod2Matrix::nzeroslackrows, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPhashsetGetNElements(), SCIPhashsetGetSlots(), SCIPhashtableCreate(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRetrieve(), SCIPisZero(), sepadata, Mod2Row::slack, and Mod2Col::solval.
Referenced by doSeparation().
|
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 1465 of file sepa_zerohalf.c.
References assert(), i, NONZERO, SCIP_Bool, SCIP_Real, SCIPcolGetVarProbindex(), SCIPfeasCeil(), SCIPfeasFloor(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetNNonz(), SCIProwGetRank(), SCIProwGetRhs(), SCIProwGetVals(), and SCIProwIsLocal().
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 1519 of file sepa_zerohalf.c.
References i, TransIntRow::len, TransIntRow::local, MAX, NONZERO, TransIntRow::rank, TransIntRow::rhs, SCIP_Bool, SCIP_Real, TransIntRow::vals, and TransIntRow::varinds.
Referenced by generateZerohalfCut().
|
static |
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 assert(), i, MAX, NULL, SCIP_Real, SCIPgetSolVal(), SCIPgetVars(), SCIPgetVectorEfficacyNorm(), sol, and vars.
Referenced by generateZerohalfCut().
computes maximal violation that can be achieved for zerohalf cuts where this row particiaptes
row | mod 2 row |
Definition at line 1583 of file sepa_zerohalf.c.
References SCIP_Real, and Mod2Row::slack.
Referenced by doSeparation().
computes violation of zerohalf cut generated from given mod 2 row
row | mod 2 row |
Definition at line 1597 of file sepa_zerohalf.c.
References i, Mod2Row::nnonzcols, Mod2Row::nonzcols, SCIP_Real, Mod2Row::slack, and Mod2Col::solval.
Referenced by 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 |
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(), assert(), BOUNDSWITCH, calcEfficacy(), computeViolation(), FALSE, i, Mod2Row::index, RowIndex::index, TransIntRow::len, MAXAGGRLEN, Mod2Row::nrowinds, nvars, ORIG_LHS, ORIG_RHS, primsol, REALABS, Mod2Row::rhs, TransIntRow::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(), sepadata, TransIntRow::slack, sol, Mod2Matrix::transintrows, TRANSROW, TRUE, RowIndex::type, and vars.
Referenced by doSeparation(), and 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)
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 assert(), checkRow, computeMaxViolation(), generateZerohalfCut(), i, mod2matrixRemoveRow(), Mod2Row::nnonzcols, Mod2Row::nonzcols, Mod2Matrix::nrows, NULL, Mod2Row::pos, Mod2Row::rhs, Mod2Matrix::rows, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPhashtableCreate(), SCIPhashtableExists(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRemove(), SCIPhashtableRetrieve(), SCIPisLT(), SCIPswapInts(), SCIPswapPointers(), sepadata, Mod2Row::slack, and sol.
Referenced by doSeparation().
|
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 1963 of file sepa_zerohalf.c.
References assert(), BMScopyMemoryArray, checkRow, i, Mod2Col::index, MAX, Mod2Row::maxsolval, mod2colLinkRow(), mod2colUnlinkRow(), nlprows, 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().
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 2104 of file sepa_zerohalf.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaZerohalf(), SCIPsepaGetName(), and SEPA_NAME.
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 2118 of file sepa_zerohalf.c.
References assert(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), SEPA_NAME, and sepadata.
|
static |
Definition at line 2135 of file sepa_zerohalf.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPsepaGetData(), SCIPsepaGetName(), SEPA_NAME, sepadata, and TRUE.
|
static |
Definition at line 2152 of file sepa_zerohalf.c.
References assert(), NULL, SCIP_OKAY, SCIPfreeRandom(), SCIPsepaGetData(), SCIPsepaGetName(), SEPA_NAME, and sepadata.
|
static |
perform the zerohalf cut separation
Definition at line 2169 of file sepa_zerohalf.c.
References assert(), buildMod2Matrix(), computeMaxViolation(), depth, destroyMod2Matrix(), FALSE, generateZerohalfCut(), i, MAXREDUCTIONROUNDS, Mod2Row::maxsolval, mod2matrixPreprocessColumns(), mod2matrixPreprocessRows(), mod2matrixRemoveCol(), mod2rowAddRow(), ncalls, Mod2Matrix::ncols, Mod2Row::nnonzcols, Mod2Row::nonzcols, Mod2Col::nonzrows, Mod2Matrix::nrows, NULL, Mod2Matrix::nzeroslackrows, result, Mod2Row::rhs, Mod2Matrix::rows, SCIP_Bool, 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(), sepadata, Mod2Row::slack, sol, and Mod2Col::solval.
Referenced by SCIP_DECL_SEPAEXECLP(), and SCIP_DECL_SEPAEXECSOL().
|
static |
LP solution separation method of separator
Definition at line 2387 of file sepa_zerohalf.c.
References assert(), depth, doSeparation(), NULL, result, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIPgetLPSolstat(), SCIPgetNLPBranchCands(), SCIPisStopped(), SCIPsepaGetName(), and SEPA_NAME.
|
static |
custom solution separation method of separator
Definition at line 2414 of file sepa_zerohalf.c.
References assert(), depth, doSeparation(), NULL, result, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIPisStopped(), SCIPsepaGetName(), SEPA_NAME, and sol.