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

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

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

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

Definition at line 209 of file sepa_zerohalf.c.

## ◆ COLINFO_GET_RHSOFFSET

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

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

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

Definition at line 1461 of file sepa_zerohalf.c.

## ◆ MOD2_COL

 typedef struct Mod2Col MOD2_COL

Definition at line 100 of file sepa_zerohalf.c.

## ◆ MOD2_ROW

 typedef struct Mod2Row 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

 typedef struct RowIndex ROWINDEX

Definition at line 104 of file sepa_zerohalf.c.

## ◆ checkRow()

 static void checkRow ( MOD2_ROW * row )
static

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

References Mod2Col::index.

## ◆ SCIP_DECL_SORTPTRCOMP() [2/2]

 static SCIP_DECL_SORTPTRCOMP ( compareRowSlack )
static

comparison function for slack of mod 2 rows

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

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

References SCIP_Real, and SCIPrelDiff().

Referenced by 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 338 of file sepa_zerohalf.c.

Referenced by 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 628 of file sepa_zerohalf.c.

Referenced by buildMod2Matrix().

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

Referenced by buildMod2Matrix().

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

Referenced by mod2matrixRemoveRow(), and mod2rowAddRow().

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

Referenced by mod2matrixRemoveCol().

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

Referenced by buildMod2Matrix().

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

Referenced by buildMod2Matrix().

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

Referenced by doSeparation().

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

Referenced by doSeparation().

## ◆ SCIP_DECL_HASHKEYEQ() [1/2]

 static SCIP_DECL_HASHKEYEQ ( columnsEqual )
static

Definition at line 1209 of file sepa_zerohalf.c.

## ◆ SCIP_DECL_HASHKEYVAL() [1/2]

 static SCIP_DECL_HASHKEYVAL ( columnGetSignature )
static

Definition at line 1236 of file sepa_zerohalf.c.

## ◆ SCIP_DECL_HASHKEYEQ() [2/2]

 static SCIP_DECL_HASHKEYEQ ( rowsEqual )
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 SCIP_DECL_HASHKEYVAL ( rowGetSignature )
static

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

Referenced by mod2matrixPreprocessRows().

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

Referenced by doSeparation(), and mod2matrixPreprocessColumns().

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

Referenced by doSeparation().

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

Referenced by generateZerohalfCut().

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

References MAX, NULL, SCIP_Real, SCIPgetSolVal(), SCIPgetVars(), and SCIPgetVectorEfficacyNorm().

Referenced by 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
 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()

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

References Mod2Row::nnonzcols, Mod2Row::nonzcols, SCIP_Real, Mod2Row::slack, and Mod2Col::solval.

Referenced by 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 1620 of file sepa_zerohalf.c.

Referenced by 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 1871 of file sepa_zerohalf.c.

Referenced by doSeparation().

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

Referenced by doSeparation().

## ◆ SCIP_DECL_SEPACOPY()

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

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

Definition at line 2118 of file sepa_zerohalf.c.

## ◆ SCIP_DECL_SEPAINITSOL()

 static SCIP_DECL_SEPAINITSOL ( sepaInitsolZerohalf )
static

## ◆ SCIP_DECL_SEPAEXITSOL()

 static SCIP_DECL_SEPAEXITSOL ( sepaExitsolZerohalf )
static

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

## ◆ SCIP_DECL_SEPAEXECSOL()

 static SCIP_DECL_SEPAEXECSOL ( sepaExecsolZerohalf )
static

custom solution separation method of separator

Definition at line 2414 of file sepa_zerohalf.c.