# 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_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 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)

## ◆ 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.

Referenced by SCIPincludeSepaZerohalf().

## ◆ SEPA_PRIORITY

 #define SEPA_PRIORITY   -6000

Definition at line 64 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

## ◆ SEPA_FREQ

 #define SEPA_FREQ   10

Definition at line 65 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

## ◆ SEPA_MAXBOUNDDIST

 #define SEPA_MAXBOUNDDIST   1.0

Definition at line 66 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

## ◆ SEPA_USESSUBSCIP

 #define SEPA_USESSUBSCIP   FALSE

Definition at line 67 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

## ◆ SEPA_DELAY

 #define SEPA_DELAY   FALSE

Definition at line 68 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 70 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 71 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 72 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 73 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 74 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 75 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 76 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

## ◆ 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 77 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

threshold for score of cut relative to best score to be discarded

Definition at line 80 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

## ◆ DEFAULT_MINVIOL

 #define DEFAULT_MINVIOL   0.1

minimal violation to generate zerohalfcut for

Definition at line 81 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 82 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 83 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 84 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

## ◆ DEFAULT_INITSEED

 #define DEFAULT_INITSEED   0x5EED

default initial seed used for random tie-breaking in cut selection

Definition at line 85 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

## ◆ DEFAULT_OBJPARALWEIGHT

 #define DEFAULT_OBJPARALWEIGHT   0.0

weight of objective parallelism in cut score calculation

Definition at line 86 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

## ◆ DEFAULT_EFFICACYWEIGHT

 #define DEFAULT_EFFICACYWEIGHT   1.0

weight of efficacy in cut score calculation

Definition at line 87 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

## ◆ DEFAULT_DIRCUTOFFDISTWEIGHT

 #define DEFAULT_DIRCUTOFFDISTWEIGHT   0.0

weight of directed cutoff distance in cut score calculation

Definition at line 88 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

## ◆ DEFAULT_GOODMAXPARALL

 #define DEFAULT_GOODMAXPARALL   0.1

maximum parallelism for good cuts

Definition at line 89 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

## ◆ DEFAULT_MAXPARALL

 #define DEFAULT_MAXPARALL   0.1

maximum parallelism for non-good cuts

Definition at line 90 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

## ◆ MAXDNOM

 #define MAXDNOM   1000LL

Definition at line 93 of file sepa_zerohalf.c.

Referenced by transformNonIntegralRow().

## ◆ MAXSCALE

 #define MAXSCALE   1000.0

Definition at line 94 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 97 of file sepa_zerohalf.c.

Referenced by doSeparation().

## ◆ BOUNDSWITCH

 #define BOUNDSWITCH   0.5

threshold for bound switching

Definition at line 98 of file sepa_zerohalf.c.

Referenced by buildMod2Matrix(), and generateZerohalfCut().

## ◆ MAXAGGRLEN

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

Definition at line 99 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 109 of file sepa_zerohalf.c.

## ◆ ORIG_RHS

 #define ORIG_RHS   0u

Definition at line 110 of file sepa_zerohalf.c.

Referenced by buildMod2Matrix(), and generateZerohalfCut().

## ◆ ORIG_LHS

 #define ORIG_LHS   1u

Definition at line 111 of file sepa_zerohalf.c.

Referenced by buildMod2Matrix(), and generateZerohalfCut().

## ◆ TRANSROW

 #define TRANSROW   2u

Definition at line 112 of file sepa_zerohalf.c.

## ◆ UNIQUE_INDEX

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

Definition at line 115 of file sepa_zerohalf.c.

## ◆ COLINFO_GET_MOD2COL

 #define COLINFO_GET_MOD2COL ( x ) ((MOD2_COL*) (((uintptr_t)(x)) & ~((uintptr_t)1)))

Definition at line 210 of file sepa_zerohalf.c.

## ◆ COLINFO_GET_RHSOFFSET

 #define COLINFO_GET_RHSOFFSET ( x ) ((int) (((uintptr_t)(x)) & ((uintptr_t)1)))

Definition at line 211 of file sepa_zerohalf.c.

## ◆ COLINFO_CREATE

 #define COLINFO_CREATE ( mod2col, rhsoffset ) ((void*) (((uintptr_t)(mod2col)) | ((uintptr_t)(rhsoffset))))

Definition at line 212 of file sepa_zerohalf.c.

## ◆ NONZERO

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

Definition at line 1462 of file sepa_zerohalf.c.

## ◆ MOD2_COL

 typedef struct Mod2Col MOD2_COL

Definition at line 101 of file sepa_zerohalf.c.

## ◆ MOD2_ROW

 typedef struct Mod2Row MOD2_ROW

Definition at line 102 of file sepa_zerohalf.c.

## ◆ MOD2_MATRIX

 typedef struct Mod2Matrix MOD2_MATRIX

Definition at line 103 of file sepa_zerohalf.c.

## ◆ TRANSINTROW

 typedef struct TransIntRow TRANSINTROW

Definition at line 104 of file sepa_zerohalf.c.

## ◆ ROWINDEX

 typedef struct RowIndex ROWINDEX

Definition at line 105 of file sepa_zerohalf.c.

## ◆ checkRow()

 static void checkRow ( MOD2_ROW * row )
static

Definition at line 217 of file sepa_zerohalf.c.

## ◆ SCIP_DECL_SORTPTRCOMP() [1/2]

 static SCIP_DECL_SORTPTRCOMP ( compareColIndex )
static

compare to mod 2 columns by there index

Definition at line 239 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 257 of file sepa_zerohalf.c.

## ◆ mod2()

 static int mod2 ( SCIP * scip, SCIP_Real val )
static

take integral real value modulo 2

Parameters
 scip scip data structure val value to take mod 2

Definition at line 295 of file sepa_zerohalf.c.

References getIntegralScalar(), REALABS, SCIPisFeasIntegral(), and SCIPround().

## ◆ 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
 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 307 of file sepa_zerohalf.c.

References SCIP_Real, SCIPrelDiff(), and transformNonIntegralRow().

Referenced by mod2(), and transformNonIntegralRow().

## ◆ transformNonIntegralRow()

 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

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 339 of file sepa_zerohalf.c.

Referenced by getIntegralScalar(), and mod2MatrixTransformContRows().

## ◆ mod2MatrixTransformContRows()

 static SCIP_RETCODE mod2MatrixTransformContRows ( SCIP * scip, SCIP_SOL * sol, 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
 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 629 of file sepa_zerohalf.c.

Referenced by buildMod2Matrix(), and transformNonIntegralRow().

 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
 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 722 of file sepa_zerohalf.c.

Referenced by buildMod2Matrix(), and mod2MatrixTransformContRows().

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

links row to mod 2 column

Parameters
 blkmem block memory shell col mod 2 column row mod 2 row

Definition at line 755 of file sepa_zerohalf.c.

 static SCIP_RETCODE mod2colUnlinkRow ( MOD2_COL * col, MOD2_ROW * row )
static

unlinks row from mod 2 column

Parameters
 col mod 2 column row mod 2 row

Definition at line 772 of file sepa_zerohalf.c.

 static void mod2rowUnlinkCol ( MOD2_ROW * row, MOD2_COL * col )
static

unlinks row from mod 2 column

Parameters
 row mod 2 row col mod 2 column

Definition at line 798 of file sepa_zerohalf.c.

 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
 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 825 of file sepa_zerohalf.c.

 static SCIP_RETCODE mod2MatrixAddTransRow ( SCIP * scip, MOD2_MATRIX * mod2matrix, SCIP_HASHMAP * origcol2col, int transrowind )
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 910 of file sepa_zerohalf.c.

## ◆ destroyMod2Matrix()

 static void destroyMod2Matrix ( SCIP * scip, MOD2_MATRIX * mod2matrix )
static

free all resources held by the mod 2 matrix

Parameters
 scip scip data structure mod2matrix pointer to mod2 matrix structure

Definition at line 991 of file sepa_zerohalf.c.

## ◆ buildMod2Matrix()

 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

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 1027 of file sepa_zerohalf.c.

Referenced by destroyMod2Matrix(), and doSeparation().

## ◆ SCIP_DECL_HASHKEYEQ() [1/2]

 static SCIP_DECL_HASHKEYEQ ( columnsEqual )
static

Definition at line 1210 of file sepa_zerohalf.c.

Referenced by buildMod2Matrix(), and SCIP_DECL_HASHKEYVAL().

## ◆ SCIP_DECL_HASHKEYVAL() [1/2]

 static SCIP_DECL_HASHKEYVAL ( columnGetSignature )
static

Definition at line 1237 of file sepa_zerohalf.c.

Referenced by SCIP_DECL_HASHKEYEQ().

## ◆ SCIP_DECL_HASHKEYEQ() [2/2]

 static SCIP_DECL_HASHKEYEQ ( rowsEqual )
static

## ◆ SCIP_DECL_HASHKEYVAL() [2/2]

 static SCIP_DECL_HASHKEYVAL ( rowGetSignature )
static

Definition at line 1290 of file sepa_zerohalf.c.

## ◆ mod2matrixRemoveRow()

 static SCIP_RETCODE mod2matrixRemoveRow ( SCIP * scip, MOD2_MATRIX * mod2matrix, MOD2_ROW * row )
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 1309 of file sepa_zerohalf.c.

Referenced by mod2matrixPreprocessRows(), and SCIP_DECL_HASHKEYVAL().

## ◆ mod2matrixRemoveCol()

 static void mod2matrixRemoveCol ( SCIP * scip, MOD2_MATRIX * mod2matrix, MOD2_COL * col )
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 1345 of file sepa_zerohalf.c.

Referenced by doSeparation(), mod2matrixPreprocessColumns(), and mod2matrixRemoveRow().

## ◆ mod2matrixPreprocessColumns()

 static SCIP_RETCODE mod2matrixPreprocessColumns ( SCIP * scip, MOD2_MATRIX * mod2matrix, SCIP_SEPADATA * sepadata )
static
Parameters
 scip scip data structure mod2matrix mod 2 matrix sepadata zerohalf separator data

Definition at line 1385 of file sepa_zerohalf.c.

Referenced by doSeparation(), and mod2matrixRemoveCol().

 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
 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 1466 of file sepa_zerohalf.c.

Referenced by generateZerohalfCut().

 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
 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 1520 of file sepa_zerohalf.c.

## ◆ calcEfficacy()

 static SCIP_Real calcEfficacy ( SCIP * scip, SCIP_SOL * sol, SCIP_Real * cutcoefs, SCIP_Real cutrhs, int * cutinds, int cutnnz )
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 1554 of file sepa_zerohalf.c.

## ◆ computeMaxViolation()

 static SCIP_Real computeMaxViolation ( MOD2_ROW * row )
static

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

Parameters
 row mod 2 row

Definition at line 1584 of file sepa_zerohalf.c.

References computeViolation(), SCIP_Real, and Mod2Row::slack.

Referenced by calcEfficacy(), doSeparation(), and mod2matrixPreprocessRows().

## ◆ computeViolation()

 static SCIP_Real computeViolation ( MOD2_ROW * row )
static

computes violation of zerohalf cut generated from given mod 2 row

Parameters
 row mod 2 row

Definition at line 1598 of file sepa_zerohalf.c.

Referenced by computeMaxViolation(), and generateZerohalfCut().

## ◆ generateZerohalfCut()

 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

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 1621 of file sepa_zerohalf.c.

Referenced by computeViolation(), doSeparation(), and mod2matrixPreprocessRows().

## ◆ mod2matrixPreprocessRows()

 static SCIP_RETCODE mod2matrixPreprocessRows ( SCIP * scip, SCIP_SOL * sol, 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
 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 1872 of file sepa_zerohalf.c.

Referenced by doSeparation(), and generateZerohalfCut().

 static SCIP_RETCODE mod2rowAddRow ( SCIP * scip, BMS_BLKMEM * blkmem, MOD2_MATRIX * mod2matrix, MOD2_ROW * row, MOD2_ROW * rowtoadd )
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 1964 of file sepa_zerohalf.c.

Referenced by doSeparation(), and mod2matrixPreprocessRows().

## ◆ SCIP_DECL_SEPACOPY()

 static SCIP_DECL_SEPACOPY ( sepaCopyZerohalf )
static

copy method for separator plugins (called when SCIP copies plugins)

Definition at line 2105 of file sepa_zerohalf.c.

## ◆ SCIP_DECL_SEPAFREE()

 static SCIP_DECL_SEPAFREE ( sepaFreeZerohalf )
static

destructor of separator to free user data (called when SCIP is exiting)

Definition at line 2119 of file sepa_zerohalf.c.

Referenced by SCIP_DECL_SEPACOPY().

## ◆ SCIP_DECL_SEPAINITSOL()

 static SCIP_DECL_SEPAINITSOL ( sepaInitsolZerohalf )
static

Definition at line 2136 of file sepa_zerohalf.c.

Referenced by SCIP_DECL_SEPAFREE().

## ◆ SCIP_DECL_SEPAEXITSOL()

 static SCIP_DECL_SEPAEXITSOL ( sepaExitsolZerohalf )
static

Definition at line 2153 of file sepa_zerohalf.c.

Referenced by SCIP_DECL_SEPAINITSOL().

## ◆ doSeparation()

 static SCIP_RETCODE doSeparation ( SCIP * scip, SCIP_SEPA * sepa, SCIP_SOL * sol, SCIP_RESULT * result, SCIP_Bool allowlocal, int depth )
static

## ◆ SCIP_DECL_SEPAEXECLP()

 static SCIP_DECL_SEPAEXECLP ( sepaExeclpZerohalf )
static

LP solution separation method of separator

Definition at line 2388 of file sepa_zerohalf.c.

Referenced by doSeparation().

## ◆ SCIP_DECL_SEPAEXECSOL()

 static SCIP_DECL_SEPAEXECSOL ( sepaExecsolZerohalf )
static

custom solution separation method of separator

Definition at line 2415 of file sepa_zerohalf.c.

Referenced by SCIP_DECL_SEPAEXECLP().