Scippy

SCIP

Solving Constraint Integer Programs

sepa_zerohalf.c File Reference

Detailed Description

{0,1/2}-cuts separator

Author
Robert Lion Gottwald
Manuel Kutschka
Kati Wolter

{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/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)
 

Macro Definition Documentation

◆ SEPA_NAME

#define SEPA_NAME   "zerohalf"

◆ SEPA_DESC

#define SEPA_DESC   "{0,1/2}-cuts separator"

Definition at line 54 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

◆ SEPA_PRIORITY

#define SEPA_PRIORITY   -6000

Definition at line 55 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

◆ SEPA_FREQ

#define SEPA_FREQ   10

Definition at line 56 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST   1.0

Definition at line 57 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP   FALSE

Definition at line 58 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

◆ SEPA_DELAY

#define SEPA_DELAY   FALSE

Definition at line 59 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

◆ DEFAULT_MAXROUNDS

#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().

◆ DEFAULT_MAXROUNDSROOT

#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().

◆ DEFAULT_MAXSEPACUTS

#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().

◆ DEFAULT_MAXSEPACUTSROOT

#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().

◆ DEFAULT_MAXCUTCANDS

#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().

◆ DEFAULT_MAXSLACK

#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().

◆ DEFAULT_MAXSLACKROOT

#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().

◆ DEFAULT_GOODSCORE

#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().

◆ DEFAULT_BADSCORE

#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().

◆ DEFAULT_MINVIOL

#define DEFAULT_MINVIOL   0.1

minimal violation to generate zerohalfcut for

Definition at line 72 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

◆ DEFAULT_DYNAMICCUTS

#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().

◆ DEFAULT_MAXROWDENSITY

#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().

◆ DEFAULT_DENSITYOFFSET

#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().

◆ MAXDNOM

#define MAXDNOM   1000LL

Definition at line 78 of file sepa_zerohalf.c.

Referenced by transformNonIntegralRow().

◆ MAXSCALE

#define MAXSCALE   1000.0

Definition at line 79 of file sepa_zerohalf.c.

Referenced by transformNonIntegralRow().

◆ MAXREDUCTIONROUNDS

#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().

◆ BOUNDSWITCH

#define BOUNDSWITCH   0.5

threshold for bound switching

Definition at line 83 of file sepa_zerohalf.c.

Referenced by buildMod2Matrix(), and generateZerohalfCut().

◆ MAXAGGRLEN

#define MAXAGGRLEN (   nvars)    ((int)(0.1*(nvars)+1000))

Definition at line 84 of file sepa_zerohalf.c.

Referenced by generateZerohalfCut().

◆ ROWIND_TYPE

#define ROWIND_TYPE   unsigned int

enum for different types of row indices in ROWINDEX structure

Definition at line 94 of file sepa_zerohalf.c.

◆ ORIG_RHS

#define ORIG_RHS   0u

Definition at line 95 of file sepa_zerohalf.c.

Referenced by buildMod2Matrix(), and generateZerohalfCut().

◆ ORIG_LHS

#define ORIG_LHS   1u

Definition at line 96 of file sepa_zerohalf.c.

Referenced by buildMod2Matrix(), and generateZerohalfCut().

◆ TRANSROW

#define TRANSROW   2u

Definition at line 97 of file sepa_zerohalf.c.

Referenced by generateZerohalfCut(), and mod2MatrixAddTransRow().

◆ UNIQUE_INDEX

#define UNIQUE_INDEX (   rowind)    (3*(rowind).index + (rowind).type)

Definition at line 100 of file sepa_zerohalf.c.

Referenced by mod2rowAddRow().

◆ COLINFO_GET_MOD2COL

#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().

◆ COLINFO_GET_RHSOFFSET

#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().

◆ COLINFO_CREATE

#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().

◆ NONZERO

#define NONZERO (   x)    (COPYSIGN(1e-100, (x)) + (x))

Definition at line 1426 of file sepa_zerohalf.c.

Referenced by addOrigRow(), and addTransRow().

Typedef Documentation

◆ MOD2_COL

typedef struct Mod2Col MOD2_COL

Definition at line 86 of file sepa_zerohalf.c.

◆ MOD2_ROW

typedef struct Mod2Row MOD2_ROW

Definition at line 87 of file sepa_zerohalf.c.

◆ MOD2_MATRIX

typedef struct Mod2Matrix MOD2_MATRIX

Definition at line 88 of file sepa_zerohalf.c.

◆ TRANSINTROW

typedef struct TransIntRow TRANSINTROW

Definition at line 89 of file sepa_zerohalf.c.

◆ ROWINDEX

typedef struct RowIndex ROWINDEX

Definition at line 90 of file sepa_zerohalf.c.

Function Documentation

◆ checkRow()

◆ SCIP_DECL_SORTPTRCOMP() [1/2]

static SCIP_DECL_SORTPTRCOMP ( compareColIndex  )
static

compare to mod 2 columns by there index

Definition at line 218 of file sepa_zerohalf.c.

References Mod2Col::index.

Referenced by checkRow().

◆ SCIP_DECL_SORTPTRCOMP() [2/2]

static SCIP_DECL_SORTPTRCOMP ( compareRowSlack  )
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.

◆ mod2()

static int mod2 ( SCIP scip,
SCIP_Real  val 
)
static

take integral real value modulo 2

Parameters
scipscip data structure
valvalue 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().

◆ getIntegralScalar()

static void getIntegralScalar ( SCIP_Real  val,
SCIP_Real  scalar,
SCIP_Real  mindelta,
SCIP_Real  maxdelta,
SCIP_Real sval,
SCIP_Real intval 
)
static

returns the integral value for the given scaling parameters, see SCIPcalcIntegralScalar()

Parameters
valvalue that should be scaled to an integral value
scalarscalar that should be tried
mindeltaminimal relative allowed difference of scaled coefficient s*c and integral i
maxdeltamaximal relative allowed difference of scaled coefficient s*c and integral i
svalpointer to store the scaled value
intvalpointer 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().

◆ transformNonIntegralRow()

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

Tries to transform a non-integral row into an integral row that can be used in zerohalf separation

Parameters
scipscip data structure
allowlocalshould local cuts be allowed
maxslackmaximum slack allowed for transformed row
sign+1 or -1 scale to select the side of the row
localis the row only valid locally?
rankrank of row
rowlenlength of row
rowvalscoefficients of columns in row
rowcolscolumns of row
rhsright hand side of row
intvarposclean buffer array of size SCIPgetNVars that will be clean when the function returns
introwpointer to return transformed row
successpointer 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().

◆ mod2MatrixTransformContRows()

static SCIP_RETCODE mod2MatrixTransformContRows ( SCIP scip,
SCIP_SEPADATA sepadata,
MOD2_MATRIX mod2matrix,
SCIP_Bool  allowlocal,
SCIP_Real  maxslack 
)
static

Tries to transform non-integral rows into an integral form by using simple and variable bounds

Parameters
scipscip data structure
sepadatazerohalf separator data
mod2matrixmod2 matrix structure
allowlocalshould local cuts be allowed
maxslackmaximum 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().

◆ mod2MatrixAddCol()

static SCIP_RETCODE mod2MatrixAddCol ( SCIP scip,
MOD2_MATRIX mod2matrix,
SCIP_HASHMAP origvar2col,
SCIP_VAR origvar,
SCIP_Real  solval,
int  rhsoffset 
)
static

adds new column to the mod 2 matrix

Parameters
scipSCIP datastructure
mod2matrixmod 2 matrix
origvar2colhash map for mapping of problem variables to mod 2 columns
origvarproblem variable to create mod 2 column for
solvalsolution value of problem variable
rhsoffsetoffset 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().

◆ mod2colLinkRow()

static SCIP_RETCODE mod2colLinkRow ( BMS_BLKMEM blkmem,
MOD2_COL col,
MOD2_ROW row 
)
static

links row to mod 2 column

Parameters
blkmemblock memory shell
colmod 2 column
rowmod 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().

◆ mod2colUnlinkRow()

static SCIP_RETCODE mod2colUnlinkRow ( MOD2_COL col,
MOD2_ROW row 
)
static

unlinks row from mod 2 column

Parameters
colmod 2 column
rowmod 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().

◆ mod2rowUnlinkCol()

static void mod2rowUnlinkCol ( MOD2_ROW row,
MOD2_COL col 
)
static

unlinks row from mod 2 column

Parameters
rowmod 2 row
colmod 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().

◆ mod2MatrixAddOrigRow()

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

adds a SCIP_ROW to the mod 2 matrix

Parameters
scipscip data structure
blkmemblock memory shell
mod2matrixmodulo 2 matrix
origcol2colhashmap to retrieve the mod 2 column from a SCIP_COL
origroworiginal SCIP row
slackslack of row
sideside of row that is used for mod 2 row, must be ORIG_RHS or ORIG_LHS
rhsmod2modulo 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().

◆ mod2MatrixAddTransRow()

◆ destroyMod2Matrix()

◆ buildMod2Matrix()

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() [1/2]

static SCIP_DECL_HASHKEYEQ ( columnsEqual  )
static

◆ SCIP_DECL_HASHKEYVAL() [1/2]

static SCIP_DECL_HASHKEYVAL ( columnGetSignature  )
static

◆ SCIP_DECL_HASHKEYEQ() [2/2]

static SCIP_DECL_HASHKEYEQ ( rowsEqual  )
static

◆ SCIP_DECL_HASHKEYVAL() [2/2]

static SCIP_DECL_HASHKEYVAL ( rowGetSignature  )
static

◆ mod2matrixRemoveRow()

static SCIP_RETCODE mod2matrixRemoveRow ( SCIP scip,
MOD2_MATRIX mod2matrix,
MOD2_ROW row 
)
static

◆ mod2matrixRemoveCol()

static void mod2matrixRemoveCol ( SCIP scip,
MOD2_MATRIX mod2matrix,
MOD2_COL col 
)
static

removes a column from the mod 2 matrix

Parameters
scipscip data structure
mod2matrixthe mod 2 matrix
cola 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().

◆ mod2matrixPreprocessColumns()

static SCIP_RETCODE mod2matrixPreprocessColumns ( SCIP scip,
MOD2_MATRIX mod2matrix,
SCIP_SEPADATA sepadata 
)
static

◆ addOrigRow()

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

add original row to aggregation with weight 0.5

Parameters
scipSCIP datastructure
tmpcoefsarray to add coefficients to
cutrhspointer to add right hand side
nonzeroindsarray of non-zeros in the aggregation
nnzpointer to update number of non-zeros
cutrankpointer to update cut rank
cutislocalpointer to update local flag
rowrow to add
signsign 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().

◆ addTransRow()

static void addTransRow ( SCIP_Real tmpcoefs,
SCIP_Real cutrhs,
int *  nonzeroinds,
int *  nnz,
int *  cutrank,
SCIP_Bool cutislocal,
TRANSINTROW introw 
)
static

add transformed integral row to aggregation with weight 0.5

Parameters
tmpcoefsarray to add coefficients to
cutrhspointer to add right hand side
nonzeroindsarray of non-zeros in the aggregation
nnzpointer to update number of non-zeros
cutrankpointer to update cut rank
cutislocalpointer to update local flag
introwtransformed 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().

◆ calcEfficacy()

static SCIP_Real calcEfficacy ( SCIP scip,
SCIP_Real cutcoefs,
SCIP_Real  cutrhs,
int *  cutinds,
int  cutnnz 
)
static
Parameters
scipSCIP data structure
cutcoefsarray of the non-zero coefficients in the cut
cutrhsthe right hand side of the cut
cutindsarray of the problem indices of variables with a non-zero coefficient in the cut
cutnnzthe 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().

◆ computeMaxViolation()

static SCIP_Real computeMaxViolation ( MOD2_ROW row)
static

computes maximal violation that can be achieved for zerohalf cuts where this row particiaptes

Parameters
rowmod 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().

◆ computeViolation()

static SCIP_Real computeViolation ( MOD2_ROW row)
static

computes violation of zerohalf cut generated from given mod 2 row

Parameters
rowmod 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().

◆ generateZerohalfCut()

static SCIP_RETCODE generateZerohalfCut ( SCIP scip,
MOD2_MATRIX mod2matrix,
SCIP_SEPA sepa,
SCIP_SEPADATA sepadata,
SCIP_Bool  allowlocal,
MOD2_ROW row 
)
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
scipscip data structure
mod2matrixmod 2 matrix
sepazerohalf separator
sepadatazerohalf separator data
allowlocalshould local cuts be allowed
rowmod 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().

◆ mod2matrixPreprocessRows()

static SCIP_RETCODE mod2matrixPreprocessRows ( SCIP scip,
MOD2_MATRIX mod2matrix,
SCIP_SEPA sepa,
SCIP_SEPADATA sepadata,
SCIP_Bool  allowlocal 
)
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
scipscip data structure
mod2matrixthe mod 2 matrix
sepathe zerohalf separator
sepadatadata of the zerohalf separator
allowlocalshould 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().

◆ mod2rowAddRow()

◆ SCIP_DECL_SEPACOPY()

static SCIP_DECL_SEPACOPY ( sepaCopyZerohalf  )
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().

◆ SCIP_DECL_SEPAFREE()

static SCIP_DECL_SEPAFREE ( sepaFreeZerohalf  )
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().

◆ SCIP_DECL_SEPAEXECLP()