Detailed Description

{0,1/2}-cuts separator

Author: Leona 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/scipdefplugins.h"
#include "scip/struct_lp.h"

Go to the source code of this file.

Data Structures
struct	RowIndex

struct	TransIntRow

struct	Mod2Row

struct	Mod2Col

struct	Mod2Matrix

Macros
#define	SEPA_NAME "zerohalf"

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

#define	SEPA_PRIORITY -6000

#define	SEPA_FREQ 10

#define	SEPA_MAXBOUNDDIST 1.0

#define	SEPA_USESSUBSCIP FALSE

#define	SEPA_DELAY FALSE

#define	DEFAULT_MAXROUNDS 5

#define	DEFAULT_MAXROUNDSROOT 20

#define	DEFAULT_MAXSEPACUTS 20

#define	DEFAULT_MAXSEPACUTSROOT 100

#define	DEFAULT_MAXCUTCANDS 2000

#define	DEFAULT_MAXSLACK 0.0

#define	DEFAULT_MAXSLACKROOT 0.0

#define	DEFAULT_GOODSCORE 1.0

#define	DEFAULT_BADSCORE 0.5

#define	DEFAULT_MINVIOL 0.1

#define	DEFAULT_DYNAMICCUTS TRUE

#define	DEFAULT_MAXROWDENSITY 0.05

#define	DEFAULT_DENSITYOFFSET 100

#define	DEFAULT_INITSEED 0x5EED

#define	DEFAULT_OBJPARALWEIGHT 0.0

#define	DEFAULT_EFFICACYWEIGHT 1.0

#define	DEFAULT_DIRCUTOFFDISTWEIGHT 0.0

#define	DEFAULT_GOODMAXPARALL 0.1

#define	DEFAULT_MAXPARALL 0.1

#define	MAXDNOM 1000LL

#define	MAXSCALE 1000.0

#define	MAXREDUCTIONROUNDS 100

#define	BOUNDSWITCH 0.5

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

#define	ROWIND_TYPE unsigned int

#define	ORIG_RHS 0u

#define	ORIG_LHS 1u

#define	TRANSROW 2u

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

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

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

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

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

Typedefs
typedef struct Mod2Col	MOD2_COL

typedef struct Mod2Row	MOD2_ROW

typedef struct Mod2Matrix	MOD2_MATRIX

typedef struct TransIntRow	TRANSINTROW

typedef struct RowIndex	ROWINDEX

Functions
static void	checkRow (MOD2_ROW *row)

static	SCIP_DECL_SORTPTRCOMP (compareColIndex)

static	SCIP_DECL_SORTPTRCOMP (compareRowSlack)

static int	mod2 (SCIP *scip, SCIP_Real val)

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

static SCIP_RETCODE	transformNonIntegralRow (SCIP scip, SCIP_SOL sol, SCIP_Bool allowlocal, SCIP_Real maxslack, int sign, SCIP_Bool local, int rank, int rowlen, SCIP_Real rowvals, SCIP_COL rowcols, SCIP_Real rhs, int intvarpos, TRANSINTROW introw, SCIP_Bool success)

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

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

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

static SCIP_RETCODE	mod2colUnlinkRow (MOD2_COL col, MOD2_ROW row)

static void	mod2rowUnlinkCol (MOD2_ROW row, MOD2_COL col)

static SCIP_RETCODE	mod2MatrixAddOrigRow (SCIP scip, BMS_BLKMEM blkmem, MOD2_MATRIX mod2matrix, SCIP_HASHMAP origcol2col, SCIP_ROW *origrow, SCIP_Real slack, ROWIND_TYPE side, int rhsmod2)

static SCIP_RETCODE	mod2MatrixAddTransRow (SCIP scip, MOD2_MATRIX mod2matrix, SCIP_HASHMAP *origcol2col, int transrowind)

static void	destroyMod2Matrix (SCIP scip, MOD2_MATRIX mod2matrix)

static SCIP_RETCODE	buildMod2Matrix (SCIP scip, SCIP_SOL sol, SCIP_SEPADATA sepadata, BMS_BLKMEM blkmem, MOD2_MATRIX *mod2matrix, SCIP_Bool allowlocal, SCIP_Real maxslack)

static	SCIP_DECL_HASHKEYEQ (columnsEqual)

static	SCIP_DECL_HASHKEYVAL (columnGetSignature)

static	SCIP_DECL_HASHKEYEQ (rowsEqual)

static	SCIP_DECL_HASHKEYVAL (rowGetSignature)

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

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

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

static void	addOrigRow (SCIP scip, SCIP_Real tmpcoefs, SCIP_Real cutrhs, int nonzeroinds, int nnz, int cutrank, SCIP_Bool cutislocal, SCIP_ROW row, int sign)

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

static SCIP_Real	calcEfficacy (SCIP scip, SCIP_SOL sol, SCIP_Real cutcoefs, SCIP_Real cutrhs, int cutinds, int cutnnz)

static SCIP_Real	computeMaxViolation (MOD2_ROW *row)

static SCIP_Real	computeViolation (MOD2_ROW *row)

static SCIP_RETCODE	generateZerohalfCut (SCIP scip, SCIP_SOL sol, MOD2_MATRIX mod2matrix, SCIP_SEPA sepa, SCIP_SEPADATA sepadata, SCIP_Bool allowlocal, MOD2_ROW row)

static SCIP_RETCODE	mod2matrixPreprocessRows (SCIP scip, SCIP_SOL sol, MOD2_MATRIX mod2matrix, SCIP_SEPA sepa, SCIP_SEPADATA *sepadata, SCIP_Bool allowlocal)

static SCIP_RETCODE	mod2rowAddRow (SCIP scip, BMS_BLKMEM blkmem, MOD2_MATRIX mod2matrix, MOD2_ROW row, MOD2_ROW *rowtoadd)

static	SCIP_DECL_SEPACOPY (sepaCopyZerohalf)

static	SCIP_DECL_SEPAFREE (sepaFreeZerohalf)

static	SCIP_DECL_SEPAINITSOL (sepaInitsolZerohalf)

static	SCIP_DECL_SEPAEXITSOL (sepaExitsolZerohalf)

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

static	SCIP_DECL_SEPAEXECLP (sepaExeclpZerohalf)

static	SCIP_DECL_SEPAEXECSOL (sepaExecsolZerohalf)

SCIP_RETCODE	SCIPincludeSepaZerohalf (SCIP *scip)

Macro Definition Documentation

◆ SEPA_NAME

#define SEPA_NAME "zerohalf"

Definition at line 53 of file sepa_zerohalf.c.

Referenced by SCIP_DECL_SEPACOPY(), SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAEXECSOL(), SCIP_DECL_SEPAEXITSOL(), SCIP_DECL_SEPAFREE(), SCIP_DECL_SEPAINITSOL(), and SCIPincludeSepaZerohalf().

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

◆ DEFAULT_INITSEED

#define DEFAULT_INITSEED 0x5EED

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

Definition at line 76 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 77 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 78 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 79 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

◆ DEFAULT_GOODMAXPARALL

#define DEFAULT_GOODMAXPARALL 0.1

maximum parallelism for good cuts

Definition at line 80 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

◆ DEFAULT_MAXPARALL

#define DEFAULT_MAXPARALL 0.1

maximum parallelism for non-good cuts

Definition at line 81 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

◆ MAXDNOM

#define MAXDNOM 1000LL

Definition at line 84 of file sepa_zerohalf.c.

Referenced by transformNonIntegralRow().

◆ MAXSCALE

#define MAXSCALE 1000.0

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

Referenced by doSeparation().

◆ BOUNDSWITCH

#define BOUNDSWITCH 0.5

threshold for bound switching

Definition at line 89 of file sepa_zerohalf.c.

Referenced by buildMod2Matrix(), and generateZerohalfCut().

◆ MAXAGGRLEN

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

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

◆ ORIG_RHS

#define ORIG_RHS 0u

Definition at line 101 of file sepa_zerohalf.c.

Referenced by buildMod2Matrix(), and generateZerohalfCut().

◆ ORIG_LHS

#define ORIG_LHS 1u

Definition at line 102 of file sepa_zerohalf.c.

Referenced by buildMod2Matrix(), and generateZerohalfCut().

◆ TRANSROW

#define TRANSROW 2u

Definition at line 103 of file sepa_zerohalf.c.

Referenced by generateZerohalfCut(), and mod2MatrixAddTransRow().

◆ UNIQUE_INDEX

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

Definition at line 106 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 201 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 202 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 203 of file sepa_zerohalf.c.

Referenced by buildMod2Matrix(), and mod2MatrixAddCol().

◆ NONZERO

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

Definition at line 1450 of file sepa_zerohalf.c.

Referenced by addOrigRow(), and addTransRow().

Typedef Documentation

◆ MOD2_COL

typedef struct Mod2Col MOD2_COL

Definition at line 92 of file sepa_zerohalf.c.

◆ MOD2_ROW

typedef struct Mod2Row MOD2_ROW

Definition at line 93 of file sepa_zerohalf.c.

◆ MOD2_MATRIX

typedef struct Mod2Matrix MOD2_MATRIX

Definition at line 94 of file sepa_zerohalf.c.

◆ TRANSINTROW

typedef struct TransIntRow TRANSINTROW

Definition at line 95 of file sepa_zerohalf.c.

◆ ROWINDEX

typedef struct RowIndex ROWINDEX

Definition at line 96 of file sepa_zerohalf.c.

Function Documentation

◆ checkRow()

static void checkRow ( MOD2_ROW * row )

static

Definition at line 208 of file sepa_zerohalf.c.

References Mod2Col::index, MAX, Mod2Row::maxsolval, Mod2Row::nnonzcols, Mod2Row::nonzcols, SCIP_DECL_SORTPTRCOMP(), SCIP_Real, and Mod2Col::solval.

Referenced by mod2MatrixAddOrigRow(), mod2MatrixAddTransRow(), mod2matrixPreprocessColumns(), mod2matrixPreprocessRows(), mod2matrixRemoveRow(), and mod2rowAddRow().

◆ SCIP_DECL_SORTPTRCOMP() [1/2]

static SCIP_DECL_SORTPTRCOMP ( compareColIndex )

static

compare to mod 2 columns by there index

Definition at line 230 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 248 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

scip	scip data structure
val	value to take mod 2

Definition at line 286 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

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

References FALSE, getIntegralScalar(), TransIntRow::len, TransIntRow::local, MAXDNOM, MAXSCALE, mod2MatrixTransformContRows(), NULL, TransIntRow::rank, REALABS, TransIntRow::rhs, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPcalcIntegralScalar(), SCIPcolGetVar(), 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(), 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_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 617 of file sepa_zerohalf.c.

References mod2MatrixAddCol(), Mod2Matrix::ntransintrows, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPallocCleanBufferArray, SCIPfreeCleanBufferArray, SCIPgetLPRowsData(), SCIPgetNLPCols(), SCIPgetNVars(), SCIPgetRowSolActivity(), SCIPinfinity(), SCIPisInfinity(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetNLPNonz(), SCIProwGetNNonz(), SCIProwGetRank(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsIntegral(), SCIProwIsLocal(), SCIProwIsModifiable(), transformNonIntegralRow(), and Mod2Matrix::transintrows.

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

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 710 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

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

Definition at line 743 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

col	mod 2 column
row	mod 2 row

Definition at line 760 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

row	mod 2 row
col	mod 2 column

Definition at line 786 of file sepa_zerohalf.c.

References BMSmoveMemoryArray, MAX, Mod2Row::maxsolval, mod2MatrixAddOrigRow(), Mod2Row::nnonzcols, Mod2Row::nonzcols, NULL, 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

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 813 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, NULL, Mod2Matrix::nzeroslackrows, Mod2Row::rhs, Mod2Row::rowinds, Mod2Row::rowindssize, Mod2Matrix::rows, Mod2Matrix::rowssize, SCIP_ALLOC, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcolGetVar(), SCIPensureBlockMemoryArray, SCIPhashmapGetImage(), SCIPisZero(), SCIProwGetCols(), SCIProwGetLPPos(), SCIProwGetNNonz(), SCIProwGetVals(), SCIPsortPtr(), Mod2Row::slack, and RowIndex::type.

Referenced by buildMod2Matrix(), and mod2rowUnlinkCol().

◆ mod2MatrixAddTransRow()

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

References checkRow(), COLINFO_GET_MOD2COL, COLINFO_GET_RHSOFFSET, destroyMod2Matrix(), RowIndex::index, Mod2Row::index, TransIntRow::len, MAX, Mod2Row::maxsolval, mod2(), mod2colLinkRow(), Mod2Row::nnonzcols, Mod2Row::nonzcols, Mod2Row::nonzcolssize, Mod2Row::nrowinds, Mod2Matrix::nrows, NULL, Mod2Matrix::nzeroslackrows, TransIntRow::rhs, Mod2Row::rhs, Mod2Row::rowinds, Mod2Row::rowindssize, Mod2Matrix::rows, Mod2Matrix::rowssize, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPblkmem(), SCIPensureBlockMemoryArray, SCIPgetVars(), SCIPhashmapGetImage(), SCIPisZero(), SCIPsortPtr(), TransIntRow::slack, Mod2Row::slack, Mod2Matrix::transintrows, TRANSROW, RowIndex::type, TransIntRow::vals, and TransIntRow::varinds.

Referenced by buildMod2Matrix(), and mod2MatrixAddOrigRow().

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

References buildMod2Matrix(), Mod2Matrix::cols, Mod2Matrix::colssize, Mod2Matrix::ncols, Mod2Row::nonzcols, Mod2Row::nonzcolssize, Mod2Col::nonzrows, Mod2Matrix::nrows, Mod2Matrix::ntransintrows, Mod2Row::rowinds, Mod2Row::rowindssize, Mod2Matrix::rows, Mod2Matrix::rowssize, SCIPblkmem(), SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPgetNLPRows(), SCIPhashsetFree(), TransIntRow::size, Mod2Matrix::transintrows, TransIntRow::vals, and TransIntRow::varinds.

Referenced by doSeparation(), and mod2MatrixAddTransRow().

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

References BOUNDSWITCH, COLINFO_CREATE, Mod2Matrix::cols, Mod2Matrix::colssize, FALSE, MAX, mod2(), mod2MatrixAddCol(), mod2MatrixAddOrigRow(), mod2MatrixAddTransRow(), mod2MatrixTransformContRows(), Mod2Matrix::ncols, Mod2Matrix::nrows, Mod2Matrix::ntransintrows, NULL, Mod2Matrix::nzeroslackrows, ORIG_LHS, ORIG_RHS, Mod2Matrix::rows, Mod2Matrix::rowssize, SCIP_Bool, SCIP_CALL, SCIP_DECL_HASHKEYEQ(), SCIP_OKAY, SCIP_Real, SCIPblkmem(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPgetNContVars(), SCIPgetNLPCols(), SCIPgetNVars(), SCIPgetRowSolActivity(), SCIPgetSolVal(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapInsert(), SCIPinfinity(), SCIPisEQ(), SCIPisInfinity(), SCIPisLT(), SCIPisZero(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwIsIntegral(), SCIProwIsLocal(), SCIProwIsModifiable(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by destroyMod2Matrix(), and doSeparation().

◆ SCIP_DECL_HASHKEYEQ() [1/2]

static SCIP_DECL_HASHKEYEQ ( columnsEqual )

static

Definition at line 1198 of file sepa_zerohalf.c.

References FALSE, Mod2Col::nonzrows, NULL, SCIP_DECL_HASHKEYVAL(), SCIPhashsetExists(), SCIPhashsetGetNElements(), SCIPhashsetGetNSlots(), SCIPhashsetGetSlots(), and TRUE.

Referenced by buildMod2Matrix(), and SCIP_DECL_HASHKEYVAL().

◆ SCIP_DECL_HASHKEYVAL() [1/2]

static SCIP_DECL_HASHKEYVAL ( columnGetSignature )

static

Definition at line 1225 of file sepa_zerohalf.c.

References RowIndex::index, Mod2Col::nonzrows, NULL, SCIP_DECL_HASHKEYEQ(), SCIPhashsetGetNSlots(), SCIPhashsetGetSlots(), and SCIPhashSignature64.

Referenced by SCIP_DECL_HASHKEYEQ().

◆ SCIP_DECL_HASHKEYEQ() [2/2]

static SCIP_DECL_HASHKEYEQ ( rowsEqual )

static

Definition at line 1250 of file sepa_zerohalf.c.

References FALSE, Mod2Row::nnonzcols, Mod2Row::nonzcols, NULL, Mod2Row::rhs, SCIP_DECL_HASHKEYVAL(), and TRUE.

◆ SCIP_DECL_HASHKEYVAL() [2/2]

static SCIP_DECL_HASHKEYVAL ( rowGetSignature )

static

Definition at line 1278 of file sepa_zerohalf.c.

References Mod2Col::index, mod2matrixRemoveRow(), Mod2Row::nnonzcols, Mod2Row::nonzcols, NULL, Mod2Row::rhs, and SCIPhashSignature64.

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

References checkRow(), mod2colUnlinkRow(), mod2matrixRemoveCol(), 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(), 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 1333 of file sepa_zerohalf.c.

References Mod2Matrix::cols, mod2matrixPreprocessColumns(), mod2rowUnlinkCol(), Mod2Matrix::ncols, Mod2Col::nonzrows, NULL, Mod2Col::pos, SCIPblkmem(), SCIPfreeBlockMemory, SCIPhashsetFree(), SCIPhashsetGetNSlots(), and SCIPhashsetGetSlots().

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

References checkRow(), Mod2Matrix::cols, mod2matrixRemoveCol(), Mod2Matrix::ncols, Mod2Col::nonzrows, NULL, Mod2Matrix::nzeroslackrows, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPhashsetGetNElements(), SCIPhashsetGetSlots(), SCIPhashtableCreate(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRetrieve(), SCIPisZero(), Mod2Row::slack, and Mod2Col::solval.

Referenced by doSeparation(), and mod2matrixRemoveCol().

◆ 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

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 1454 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

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 1499 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_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 1533 of file sepa_zerohalf.c.

References computeMaxViolation(), MAX, NULL, SCIP_Real, SCIPgetSolVal(), SCIPgetVars(), 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

row mod 2 row

Definition at line 1563 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 1577 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,
		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 1600 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(), SCIPgetSolVal(), SCIPgetVars(), SCIPinfinity(), SCIPisCutNew(), SCIPisEfficacious(), SCIPisFeasEQ(), SCIPisFeasIntegral(), SCIPisGT(), SCIPisInfinity(), SCIPisLT(), SCIPreallocBlockMemoryArray, SCIPreleaseRow(), SCIProwChgRank(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TransIntRow::slack, Mod2Matrix::transintrows, TRANSROW, TRUE, and RowIndex::type.

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

References checkRow(), computeMaxViolation(), generateZerohalfCut(), mod2matrixRemoveRow(), mod2rowAddRow(), Mod2Row::nnonzcols, Mod2Row::nonzcols, Mod2Matrix::nrows, NULL, Mod2Row::pos, Mod2Row::rhs, Mod2Matrix::rows, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPhashtableCreate(), SCIPhashtableExists(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRemove(), SCIPhashtableRetrieve(), SCIPisLT(), SCIPswapInts(), SCIPswapPointers(), and Mod2Row::slack.

Referenced by doSeparation(), and generateZerohalfCut().

◆ mod2rowAddRow()

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

References BMScopyMemoryArray, checkRow(), Mod2Col::index, MAX, Mod2Row::maxsolval, mod2colLinkRow(), mod2colUnlinkRow(), Mod2Row::nnonzcols, Mod2Row::nonzcols, Mod2Row::nonzcolssize, Mod2Row::nrowinds, Mod2Matrix::ntransintrows, NULL, Mod2Matrix::nzeroslackrows, Mod2Row::rhs, Mod2Row::rowinds, Mod2Row::rowindssize, SCIP_CALL, SCIP_DECL_SEPACOPY(), SCIP_OKAY, SCIP_Real, SCIP_Shortbool, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPblkmem(), SCIPensureBlockMemoryArray, SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPgetNLPRows(), SCIPisZero(), Mod2Row::slack, Mod2Col::solval, and UNIQUE_INDEX.

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

References NULL, 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 2098 of file sepa_zerohalf.c.

References NULL, SCIP_DECL_SEPAINITSOL(), SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), and SEPA_NAME.

Referenced by SCIP_DECL_SEPACOPY().

◆ SCIP_DECL_SEPAINITSOL()

static SCIP_DECL_SEPAINITSOL ( sepaInitsolZerohalf )

static

Definition at line 2115 of file sepa_zerohalf.c.

References NULL, SCIP_CALL, SCIP_DECL_SEPAEXITSOL(), SCIP_OKAY, SCIPcreateRandom(), SCIPsepaGetData(), SCIPsepaGetName(), SEPA_NAME, and TRUE.

Referenced by SCIP_DECL_SEPAFREE().

◆ SCIP_DECL_SEPAEXITSOL()

static SCIP_DECL_SEPAEXITSOL ( sepaExitsolZerohalf )

static

Definition at line 2132 of file sepa_zerohalf.c.

References doSeparation(), NULL, SCIP_OKAY, SCIPfreeRandom(), SCIPsepaGetData(), SCIPsepaGetName(), and SEPA_NAME.

Referenced by SCIP_DECL_SEPAINITSOL().

◆ doSeparation()

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

static

perform the zerohalf cut separation

Definition at line 2149 of file sepa_zerohalf.c.

References buildMod2Matrix(), computeMaxViolation(), destroyMod2Matrix(), FALSE, generateZerohalfCut(), MAXREDUCTIONROUNDS, Mod2Row::maxsolval, mod2matrixPreprocessColumns(), mod2matrixPreprocessRows(), mod2matrixRemoveCol(), mod2rowAddRow(), Mod2Matrix::ncols, Mod2Row::nnonzcols, Mod2Row::nonzcols, Mod2Col::nonzrows, Mod2Matrix::nrows, NULL, Mod2Matrix::nzeroslackrows, Mod2Row::rhs, Mod2Matrix::rows, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_SEPAEXECLP(), SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPaddPoolCut(), SCIPaddRow(), SCIPaggrRowCreate(), SCIPaggrRowFree(), SCIPallocBufferArray, SCIPblkmem(), SCIPdebugMsg, SCIPfeastol(), SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPgetDepth(), SCIPhashsetGetNSlots(), SCIPhashsetGetSlots(), SCIPisPositive(), SCIPreleaseRow(), SCIProwIsLocal(), SCIPselectCuts(), SCIPselectPtr(), SCIPsepaGetData(), SCIPsepaGetNCallsAtNode(), SCIPsortPtr(), Mod2Row::slack, and Mod2Col::solval.

Referenced by SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAEXECSOL(), and SCIP_DECL_SEPAEXITSOL().

◆ SCIP_DECL_SEPAEXECLP()

static SCIP_DECL_SEPAEXECLP ( sepaExeclpZerohalf )

static

LP solution separation method of separator

Definition at line 2367 of file sepa_zerohalf.c.

References doSeparation(), NULL, SCIP_CALL, SCIP_DECL_SEPAEXECSOL(), SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIPgetLPSolstat(), SCIPgetNLPBranchCands(), SCIPisStopped(), SCIPsepaGetName(), and SEPA_NAME.

Referenced by doSeparation().

◆ SCIP_DECL_SEPAEXECSOL()

static SCIP_DECL_SEPAEXECSOL ( sepaExecsolZerohalf )

static

custom solution separation method of separator

Definition at line 2394 of file sepa_zerohalf.c.

References doSeparation(), NULL, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIPincludeSepaZerohalf(), SCIPisStopped(), SCIPsepaGetName(), and SEPA_NAME.

Referenced by SCIP_DECL_SEPAEXECLP().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ SEPA_NAME

◆ SEPA_DESC

◆ SEPA_PRIORITY

◆ SEPA_FREQ

◆ SEPA_MAXBOUNDDIST

◆ SEPA_USESSUBSCIP

◆ SEPA_DELAY

◆ DEFAULT_MAXROUNDS

◆ DEFAULT_MAXROUNDSROOT

◆ DEFAULT_MAXSEPACUTS

◆ DEFAULT_MAXSEPACUTSROOT

◆ DEFAULT_MAXCUTCANDS

◆ DEFAULT_MAXSLACK

◆ DEFAULT_MAXSLACKROOT

◆ DEFAULT_GOODSCORE

◆ DEFAULT_BADSCORE

◆ DEFAULT_MINVIOL

◆ DEFAULT_DYNAMICCUTS

◆ DEFAULT_MAXROWDENSITY

◆ DEFAULT_DENSITYOFFSET

◆ DEFAULT_INITSEED

◆ DEFAULT_OBJPARALWEIGHT

◆ DEFAULT_EFFICACYWEIGHT

◆ DEFAULT_DIRCUTOFFDISTWEIGHT

◆ DEFAULT_GOODMAXPARALL

◆ DEFAULT_MAXPARALL

◆ MAXDNOM

◆ MAXSCALE

◆ MAXREDUCTIONROUNDS

◆ BOUNDSWITCH

◆ MAXAGGRLEN

◆ ROWIND_TYPE

◆ ORIG_RHS

◆ ORIG_LHS

◆ TRANSROW

◆ UNIQUE_INDEX

◆ COLINFO_GET_MOD2COL

◆ COLINFO_GET_RHSOFFSET

◆ COLINFO_CREATE

◆ NONZERO

Typedef Documentation

◆ MOD2_COL

◆ MOD2_ROW

◆ MOD2_MATRIX

◆ TRANSINTROW

◆ ROWINDEX

Function Documentation

◆ checkRow()

◆ SCIP_DECL_SORTPTRCOMP() [1/2]

◆ SCIP_DECL_SORTPTRCOMP() [2/2]

◆ mod2()

◆ getIntegralScalar()

◆ transformNonIntegralRow()

◆ mod2MatrixTransformContRows()

◆ mod2MatrixAddCol()

◆ mod2colLinkRow()

◆ mod2colUnlinkRow()

◆ mod2rowUnlinkCol()

◆ mod2MatrixAddOrigRow()

◆ mod2MatrixAddTransRow()

◆ destroyMod2Matrix()

◆ buildMod2Matrix()

◆ SCIP_DECL_HASHKEYEQ() [1/2]

◆ SCIP_DECL_HASHKEYVAL() [1/2]

◆ SCIP_DECL_HASHKEYEQ() [2/2]

◆ SCIP_DECL_HASHKEYVAL() [2/2]

◆ mod2matrixRemoveRow()

◆ mod2matrixRemoveCol()

◆ mod2matrixPreprocessColumns()

◆ addOrigRow()

◆ addTransRow()

◆ calcEfficacy()

◆ computeMaxViolation()