Detailed Description

{0,1/2}-cuts separator

< print statistics

Author: Manuel Kutschka; Kati Wolter

{0,1/2}-Chv'atal-Gomory cuts separator. It solves the following separation problem:

Given an integer program

min { c^T x : Ax <= b, x >= 0, x integer }

and a fractional solution x* of its LP relaxation.

Find a weightvector u whose entries u_i are either 0 or 1/2 such that the following inequality is valid for all integral solutions and violated by x*

floor(u^T A) x <= floor(u^T b)

or (if exact methods are used) give a proof that no such inequality exists

References:

Alberto Caprara, Matteo Fischetti. {0,1/2}-Chvatal-Gomory cuts. Math. Programming, Volume 74, p221–235, 1996.
Arie M. C. A. Koster, Adrian Zymolka and Manuel Kutschka.
Algorithms to separate {0,1/2}-Chvatal-Gomory cuts. Algorithms - ESA 2007: 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007,
Proceedings. Lecture Notes in Computer Science, Volume 4698, p. 693–704, 2007.
Arie M. C. A. Koster, Adrian Zymolka and Manuel Kutschka.
Algorithms to separate {0,1/2}-Chvatal-Gomory cuts (Extended Version).
ZIB Report 07-10, Zuse Institute Berlin, 2007. http://www.zib.de/Publications/Reports/ZR-07-10.pdf
Manuel Kutschka. Algorithmen zur Separierung von {0,1/2}-Schnitten. Diplomarbeit. Technische Universitaet Berlin, 2007.

Definition in file sepa_zerohalf.c.

#include "string.h"
#include "scip/sepa_zerohalf.h"
#include "scip/cons_linear.h"
#include "scip/scipdefplugins.h"

Go to the source code of this file.

Macros
#define	SEPA_NAME "zerohalf"

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

#define	SEPA_PRIORITY -6000

#define	SEPA_FREQ -1

#define	SEPA_MAXBOUNDDIST 0.0

#define	SEPA_USESSUBSCIP TRUE

#define	SEPA_DELAY FALSE

#define	DEFAULT_MAXROUNDS 5

#define	DEFAULT_MAXROUNDSROOT 10

#define	DEFAULT_MAXSEPACUTS 50

#define	DEFAULT_MAXSEPACUTSROOT 500

#define	DEFAULT_DYNAMICCUTS TRUE

#define	DEFAULT_DECOMPOSEPROBLEM FALSE

#define	DEFAULT_MAXDEPTH -1

#define	DEFAULT_MINVIOLATION 0.30

#define	DEFAULT_FORCECUTSTOLP FALSE

#define	DEFAULT_FORCECUTSTOSEPASTORE FALSE

#define	DEFAULT_MAXCUTS 100

#define	DEFAULT_MAXCUTSROOT 1000

#define	DEFAULT_SUBSCIPOBJECTIVE 'v'

#define	DEFAULT_RELAXCONTVARS FALSE

#define	DEFAULT_SCALEFRACCOEFFS TRUE

#define	DEFAULT_SUBSCIPSETTINGS "-"

#define	DEFAULT_SUBSCIPSOLLIMIT -1

#define	DEFAULT_SUBSCIPUSEALLSOLS TRUE

#define	DEFAULT_PPDELTA 0.500

#define	DEFAULT_SUBSCIPOBJPEN 0.001

#define	DEFAULT_PPMETHODS "CXGXIM"

#define	DEFAULT_SEPAMETHODS "2g"

#define	DEFAULT_MAXNCALLS -1LL

#define	DEFAULT_IGNOREPREVIOUSZHCUTS FALSE

#define	DEFAULT_ONLYORIGROWS FALSE

#define	DEFAULT_USEZHCUTPOOL TRUE

#define	DEFAULT_DELAYEDCUTS TRUE

#define	DEFAULT_MAXTESTDELTA 10

#define	DEFAULT_TRYNEGSCALING TRUE

#define	ORTHOFUNC 'e'

#define	MINORTHO 0.5

#define	NNONZOFFSET 500

#define	BOUNDSWITCH 0.50

#define	USEVBDS TRUE

#define	ALLOWLOCAL TRUE

#define	FIXINTEGRALRHS TRUE

#define	BOUNDSFORTRANS NULL

#define	BOUNDTYPESFORTRANS NULL

#define	MAXWEIGHTRANGE 10000.00

#define	MINFRAC 0.05

#define	MAXFRAC 1.00

#define	MAXDNOM 1000

#define	MAXSCALE 1000.0

#define	USEVARBOUNDS TRUE

#define	ISEVEN(scip, value) (SCIPisEQ((scip) , SCIPfloor(scip , (value) / 2) , (value) / 2))

#define	ISODD(scip, value) (!(ISEVEN((scip), (value))))

#define	XOR(bool1, bool2) ((bool1) ^ (bool2))

#define	DIV(value1, powerof2value) (((unsigned int)(value1)) / ((unsigned int)(powerof2value)))

#define	MOD(value1, powerof2value) (((unsigned int)(value1)) % ((unsigned int)(powerof2value)))

#define	IRRELEVANT -1

#define	ZERO_ROW -100

#define	IDENT_TO_ROW_WITH_SMALLER_SLACK -101

#define	SLACK_GREATER_THAN_MAXSLACK -102

#define	DEFINES_VIOLATED_ZEROHALF_CUT -103

#define	NONEXISTENT_ROW -105

#define	NO_RELEVANT_COLUMNS -106

#define	SLACK_GREATER_THAN_MSL_MINUS_SODD -107

#define	LARGE_COL_EXISTS -108

#define	ZERO_COLUMN -200

#define	IDENT_TO_ANOTHER_COLUMN -201

#define	ZERO_LP_SOL -202

#define	LP_SOL_EQUALS_EVEN_LB -203

#define	LP_SOL_EQUALS_ODD_LB -204

#define	LP_SOL_EQUALS_EVEN_UB -205

#define	LP_SOL_EQUALS_ODD_UB -206

#define	SINGLETON_COLUMN -207

#define	CONTINUOUS_VARIABLE -208

#define	SMALL_FRACSOL_HEUR -209

#define	ALL_MATRIX_ROWS_DELETED -210

#define	BITARRAYBASETYPE unsigned int

#define	BITARRAYBITMASKTYPE BITARRAYBASETYPE

#define	BITARRAY BITARRAYBASETYPE*

#define	BITMASK(pos) ((unsigned int)(1 << (pos)))

#define	BITSET(var, pos) (var) \|= BITMASK(pos)

#define	BITISSET(var, pos) (var & BITMASK(pos))

#define	BITARRAYBITSET(barray, pos)

#define	BITARRAYBITISSET(barray, pos)

#define	BITARRAYCLEAR(barray, barraysize) BMSclearMemoryArray(barray,barraysize)

#define	GETREQUIREDBITARRAYSIZE(nvalstostore)

#define	GETBITARRAYINDEX(pos) DIV((pos),Zerohalf_bitarraybasetypesize_nbits)

#define	GETBITARRAYMASK(pos) BITMASK(MOD((pos),Zerohalf_bitarraybasetypesize_nbits))

#define	BITARRAYSFOREACH(barray1, barray2, size, op)

#define	BITARRAYSXOR(barray1, barray2, size) BITARRAYSFOREACH(barray1,barray2,size,^=)

#define	BITARRAYSAREEQUAL(barray1, barray2, size) (memcmp((void)(barray1), (void)(barray2), (size_t)((size) * (Zerohalf_bitarraybasetypesize))) == 0)

#define	BRANCHPRIORITY__AVOID_BRANCHING 0

#define	BRANCHPRIORITY__PREFER_BRANCHING 0

Typedefs
typedef enum cutseparatedby	CUTSEPARATEDBY

typedef struct Zerohalf_SubLPData	ZEROHALF_SUBLPDATA

typedef struct Zerohalf_LPData	ZEROHALF_LPDATA

typedef struct Zerohalf_AuxIPData	ZEROHALF_AUXIPDATA

typedef struct Zerohalf_Mod2Data	ZEROHALF_MOD2DATA

typedef struct Zerohalf_CutData	ZEROHALF_CUTDATA

typedef struct Zerohalf_AuxGraph_Node	ZEROHALF_AUXGRAPH_NODE

typedef struct Zerohalf_AuxGraph	ZEROHALF_AUXGRAPH

Enumerations
enum	preprocessingmethods { MODGAUSSIANELIMINATION = 'G', DELETEZEROROWS = 'Z', DELETEZEROCOLS = 'z', DELETECOLSINGLETONS = 's', ADDTRIVIALCUTS = 'X', DELETEIDENTROWS = 'I', MERGEIDENTCOLS = 'i', DELETELARGESLACKROWS = 'L', DELETESMALLFRACSOLCOLS = 'd', DELETEROWSWRTMINSLACK = 'M', PPCOLUMNS = 'C', PPROWS = 'R' }

enum	sepamethods { STOPIFCUTWASFOUND = '!', SOLVEAUXSCIP = 's', SOLVEAUXSCIPEXACT = 'S', ENUMHEURNMAX1 = 'e', ENUMHEURNMAX2 = 'E', GAUSSHEUR = 'g', MAX2ODDENTRIESPERROW = '2' }

enum	cutseparatedby { AUXIP, DECOMPOSITION, PPZEROONEROW, HEURISTICSENUM, HEURISTICSGAUSS, AUXGRAPH }

Functions
static SCIP_RETCODE	ZerohalfSubLPDataCreate (SCIP scip, ZEROHALF_SUBLPDATA *subproblem)

static void	ZerohalfSubLPDataFree (SCIP scip, ZEROHALF_SUBLPDATA *subproblem)

static SCIP_RETCODE	ZerohalfLPDataCreate (SCIP scip, ZEROHALF_LPDATA *lpdata)

static SCIP_RETCODE	ZerohalfLPDataFree (SCIP scip, ZEROHALF_LPDATA *lpdata)

static SCIP_RETCODE	ZerohalfMod2DataCreate (SCIP scip, ZEROHALF_MOD2DATA *mod2data)

static SCIP_RETCODE	ZerohalfMod2DataFree (SCIP scip, ZEROHALF_MOD2DATA *mod2data)

static SCIP_RETCODE	ZerohalfAuxIPDataCreate (SCIP scip, ZEROHALF_AUXIPDATA *auxipdata)

static SCIP_RETCODE	ZerohalfAuxIPDataFree (SCIP scip, ZEROHALF_AUXIPDATA *auxipdata)

static SCIP_RETCODE	ZerohalfCutDataCreate (SCIP scip, ZEROHALF_CUTDATA cutdata, ZEROHALF_SUBLPDATA relatedsubproblem, ZEROHALF_MOD2DATA *relatedmod2data, int nrrowsincut, int nrowsincut, CUTSEPARATEDBY separatedby)

static SCIP_RETCODE	ZerohalfCutDataFree (SCIP scip, ZEROHALF_CUTDATA *cutdata)

static SCIP_RETCODE	ZerohalfAuxGraphNodeCreate (SCIP scip, ZEROHALF_AUXGRAPH_NODE *node)

static SCIP_RETCODE	ZerohalfAuxGraphNodeFree (SCIP scip, ZEROHALF_AUXGRAPH_NODE *node)

static SCIP_RETCODE	ZerohalfAuxGraphCreate (SCIP scip, ZEROHALF_AUXGRAPH *auxgraph)

static SCIP_RETCODE	ZerohalfAuxGraphFree (SCIP scip, ZEROHALF_AUXGRAPH *auxgraph)

static	SCIP_DECL_SORTINDCOMP (compRealNonDecreasing)

static	SCIP_DECL_SORTINDCOMP (compRealNonIncreasing)

static SCIP_RETCODE	getRelevantColumns (SCIP scip, ZEROHALF_LPDATA lpdata)

static void	findClosestLb (SCIP scip, ZEROHALF_LPDATA lpdata, SCIP_COL col, SCIP_Real bestlbsol, int bestlbtype, SCIP_VAR bestzvlb, SCIP_Real bestbvlb, SCIP_Real *bestdvlb)

static void	findClosestUb (SCIP scip, ZEROHALF_LPDATA lpdata, SCIP_COL col, SCIP_Real bestubsol, int bestubtype, SCIP_VAR bestzvub, SCIP_Real bestbvub, SCIP_Real *bestdvub)

static SCIP_RETCODE	getRelevantRows (SCIP scip, SCIP_SEPADATA sepadata, ZEROHALF_LPDATA *lpdata)

static SCIP_Bool	hasMatrixMax2EntriesPerRow (ZEROHALF_MOD2DATA *mod2data)

static SCIP_RETCODE	storeMod2Data (SCIP scip, SCIP_SEPADATA sepadata, ZEROHALF_LPDATA lpdata, int subproblemindex, ZEROHALF_MOD2DATA mod2data)

static SCIP_RETCODE	storeCutInArrays (SCIP scip, int nvars, SCIP_VAR vars, SCIP_Real cutcoefs, SCIP_Real varsolvals, char normtype, SCIP_VAR cutvars, SCIP_Real cutvals, int cutlen, SCIP_Real cutact, SCIP_Real *cutnorm)

static SCIP_RETCODE	addZerohalfCutToLP (SCIP scip, SCIP_SEPADATA sepadata, ZEROHALF_CUTDATA cutdata, int nsepacuts, SCIP_RESULT *result)

static void	markRowAsRemoved (ZEROHALF_MOD2DATA *mod2data, int r, int flag)

static void	markColAsRemovedAndClearCol (ZEROHALF_MOD2DATA *mod2data, int c, int flag)

static SCIP_RETCODE	getZerohalfWeightvectorFromSelectedRowsBitarray (SCIP scip, SCIP_SEPADATA sepadata, ZEROHALF_LPDATA lpdata, ZEROHALF_MOD2DATA mod2data, BITARRAY rrowsincut, SCIP_Real *weights, int nrowsincut)

static SCIP_RETCODE	createZerohalfCutFromZerohalfWeightvector (SCIP scip, SCIP_SEPA sepa, SCIP_SEPADATA sepadata, ZEROHALF_LPDATA lpdata, SCIP_Real weights, char normtype, int nzerohalfcuts, SCIP_Real varsolvals, ZEROHALF_CUTDATA cutdata, SCIP_Bool *cutoff)

static SCIP_RETCODE	preprocessTrivialZerohalfCuts (SCIP scip, SCIP_SEPA sepa, SCIP_SEPADATA sepadata, ZEROHALF_LPDATA lpdata, ZEROHALF_MOD2DATA mod2data, int firstrowsind, int lastrowsind, char normtype, int maxsepacuts, int maxcuts, int nsepacuts, int nzerohalfcuts, ZEROHALF_CUTDATA zerohalfcuts, SCIP_Real varsolvals, CUTSEPARATEDBY cutseparatedby, SCIP_RESULT result)

static SCIP_RETCODE	preprocessRows (SCIP scip, SCIP_SEPADATA sepadata, ZEROHALF_LPDATA lpdata, ZEROHALF_MOD2DATA mod2data, int firstrowsind, int lastrowsind, SCIP_Bool removezerorows, SCIP_Bool removelargeslackrows, SCIP_Bool removeidenticalrows)

static SCIP_RETCODE	preprocessColumns (SCIP scip, SCIP_SEPADATA sepadata, ZEROHALF_LPDATA lpdata, ZEROHALF_MOD2DATA mod2data, int firstcolsind, int lastcolsind, SCIP_Bool removezerocols, SCIP_Bool removecolsingletons, SCIP_Bool checkresultingrows)

static SCIP_RETCODE	preprocessModGaussElim (SCIP scip, SCIP_SEPADATA sepadata, ZEROHALF_LPDATA lpdata, ZEROHALF_MOD2DATA mod2data)

static SCIP_RETCODE	decomposeProblem (SCIP scip, SCIP_SEPADATA sepadata, ZEROHALF_LPDATA *lpdata)

static SCIP_RETCODE	preprocessColumnsWithSmallFracsol (SCIP scip, SCIP_SEPADATA sepadata, ZEROHALF_MOD2DATA *mod2data, SCIP_Real delta)

static SCIP_RETCODE	preprocessConsiderMinSlack (SCIP scip, SCIP_SEPADATA sepadata, ZEROHALF_LPDATA lpdata, ZEROHALF_MOD2DATA mod2data, SCIP_Bool removelargeslackrows, SCIP_Bool removelargecolrows)

static SCIP_RETCODE	preprocessIdenticalColums (SCIP scip, ZEROHALF_MOD2DATA mod2data)

static SCIP_RETCODE	preprocess (SCIP scip, SCIP_SEPA sepa, SCIP_SEPADATA sepadata, ZEROHALF_LPDATA lpdata, ZEROHALF_MOD2DATA mod2data, char normtype, int maxsepacuts, int maxcuts, int nsepacuts, int nzerohalfcuts, ZEROHALF_CUTDATA zerohalfcuts, SCIP_Real varsolvals, SCIP_RESULT result)

static SCIP_Real	calcObjWeight (BITARRAY rowaggregation, int nrrows)

static SCIP_RETCODE	createSubscip (SCIP scip, SCIP_SEPADATA sepadata, ZEROHALF_LPDATA lpdata, ZEROHALF_MOD2DATA mod2data, ZEROHALF_AUXIPDATA *auxipdata, SCIP_Bool setnodelimit)

static SCIP_RETCODE	solveSubscip (SCIP scip, SCIP_SEPADATA sepadata, ZEROHALF_MOD2DATA mod2data, ZEROHALF_AUXIPDATA auxipdata, SCIP_SOL **sols, int nsols)

static SCIP_RETCODE	getZerohalfWeightvectorForSingleRow (SCIP scip, SCIP_SEPADATA sepadata, ZEROHALF_LPDATA lpdata, int rowsindex, int rrowsindex, SCIP_Real *weights)

static SCIP_RETCODE	getBitarrayOfSelectedRows (SCIP scip, ZEROHALF_MOD2DATA mod2data, ZEROHALF_AUXIPDATA auxipdata, SCIP_SOL solution, BITARRAY rrowsincut, int nrrowsincut)

static SCIP_RETCODE	separateBySolvingAuxIP (SCIP scip, SCIP_SEPA sepa, SCIP_SEPADATA sepadata, ZEROHALF_LPDATA lpdata, ZEROHALF_MOD2DATA mod2data, char normtype, int maxsepacuts, int maxcuts, SCIP_Bool setnodelimit, int nsepacuts, int nzerohalfcuts, ZEROHALF_CUTDATA zerohalfcuts, SCIP_Real varsolvals, SCIP_RESULT result)

static SCIP_RETCODE	calcInnerProductOfRowAndFracsol (SCIP scip, ZEROHALF_MOD2DATA mod2data, BITARRAY row, SCIP_Real maxinnerproduct, SCIP_Real *innerproduct)

static SCIP_RETCODE	separateByEnumerationHeuristics (SCIP scip, SCIP_SEPA sepa, SCIP_SEPADATA sepadata, ZEROHALF_LPDATA lpdata, ZEROHALF_MOD2DATA mod2data, char normtype, int maxsepacuts, int maxcuts, int nsepacuts, int nzerohalfcuts, ZEROHALF_CUTDATA zerohalfcuts, SCIP_Real varsolvals, SCIP_RESULT result, int maxncombinedrows)

static SCIP_RETCODE	addEdgeToAuxGraph (SCIP scip, ZEROHALF_AUXGRAPH graph, int node1index, int node2index, SCIP_Bool isodd, SCIP_Real weight, int relatedrow)

static SCIP_RETCODE	dijkstra (SCIP scip, ZEROHALF_AUXGRAPH graph, ZEROHALF_AUXGRAPH_NODE sourcenode, ZEROHALF_AUXGRAPH_NODE targetnode, SCIP_Real maxdistance)

static SCIP_RETCODE	separateByAuxGraph (SCIP scip, SCIP_SEPA sepa, SCIP_SEPADATA sepadata, ZEROHALF_LPDATA lpdata, ZEROHALF_MOD2DATA mod2data, char normtype, int maxsepacuts, int maxcuts, int nsepacuts, int nzerohalfcuts, ZEROHALF_CUTDATA zerohalfcuts, SCIP_Real varsolvals, SCIP_RESULT result, SCIP_Bool *wrongstructure)

static SCIP_RETCODE	separateByGaussHeuristics (SCIP scip, SCIP_SEPA sepa, SCIP_SEPADATA sepadata, ZEROHALF_LPDATA lpdata, ZEROHALF_MOD2DATA mod2data, char normtype, int maxsepacuts, int maxcuts, int nsepacuts, int nzerohalfcuts, ZEROHALF_CUTDATA zerohalfcuts, SCIP_Real varsolvals, SCIP_RESULT result)

static SCIP_RETCODE	process (SCIP scip, SCIP_SEPA sepa, SCIP_SEPADATA sepadata, ZEROHALF_LPDATA lpdata, ZEROHALF_MOD2DATA mod2data, char normtype, int maxsepacuts, int maxcuts, int nsepacuts, int nzerohalfcuts, ZEROHALF_CUTDATA zerohalfcuts, SCIP_Real varsolvals, SCIP_RESULT result)

static	SCIP_DECL_SEPACOPY (sepaCopyZerohalf)

static	SCIP_DECL_SEPAFREE (sepaFreeZerohalf)

static	SCIP_DECL_SEPAEXECLP (sepaExeclpZerohalf)

SCIP_RETCODE	SCIPincludeSepaZerohalf (SCIP *scip)

Variables
static const unsigned int	Zerohalf_bitarraybasetypesize = sizeof(BITARRAYBASETYPE)

static const unsigned int	Zerohalf_bitarraybasetypesize_nbits = sizeof(BITARRAYBASETYPE) << 3

Macro Definition Documentation

#define SEPA_NAME "zerohalf"

Definition at line 63 of file sepa_zerohalf.c.

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

Definition at line 64 of file sepa_zerohalf.c.

#define SEPA_PRIORITY -6000

Definition at line 65 of file sepa_zerohalf.c.

#define SEPA_FREQ -1

Definition at line 66 of file sepa_zerohalf.c.

#define SEPA_MAXBOUNDDIST 0.0

Definition at line 67 of file sepa_zerohalf.c.

#define SEPA_USESSUBSCIP TRUE

Definition at line 68 of file sepa_zerohalf.c.

#define SEPA_DELAY FALSE

Definition at line 69 of file sepa_zerohalf.c.

#define DEFAULT_MAXROUNDS 5

maximal number of zerohalf separation rounds per node (-1: unlimited)

Definition at line 71 of file sepa_zerohalf.c.

#define DEFAULT_MAXROUNDSROOT 10

maximal number of zerohalf separation rounds in the root node (-1: unlimited)

Definition at line 72 of file sepa_zerohalf.c.

#define DEFAULT_MAXSEPACUTS 50

maximal number of {0,1/2}-cuts separated per separation round

Definition at line 73 of file sepa_zerohalf.c.

#define DEFAULT_MAXSEPACUTSROOT 500

maximal number of {0,1/2}-cuts separated per separation round in root node

Definition at line 74 of file sepa_zerohalf.c.

#define DEFAULT_DYNAMICCUTS TRUE

should generated cuts be removed from the LP if they are no longer tight?

Definition at line 75 of file sepa_zerohalf.c.

#define DEFAULT_DECOMPOSEPROBLEM FALSE

should problem be decomposed into subproblems (if possible)?

Definition at line 76 of file sepa_zerohalf.c.

#define DEFAULT_MAXDEPTH -1

separating cuts only if depth <= maxdepth (-1: unlimited)

Definition at line 77 of file sepa_zerohalf.c.

#define DEFAULT_MINVIOLATION 0.30

minimal violation of a {0,1/2}-cut to be separated

Definition at line 78 of file sepa_zerohalf.c.

#define DEFAULT_FORCECUTSTOLP FALSE

should the cuts be forced to enter the LP? (bypassing SCIPefficacy criteria)

Definition at line 79 of file sepa_zerohalf.c.

#define DEFAULT_FORCECUTSTOSEPASTORE FALSE

should the cuts be forced to enter SCIP's sepastore? (bypassing SCIPefficicacy criteria, if no other cut is found)

Definition at line 80 of file sepa_zerohalf.c.

#define DEFAULT_MAXCUTS 100

maximal number of {0,1/2}-cuts determined per separation round (this includes separated but inefficacious cuts)

Definition at line 83 of file sepa_zerohalf.c.

#define DEFAULT_MAXCUTSROOT 1000

maximal number of {0,1/2}-cuts determined per separation round in the root node (this includes separated but inefficacious cuts)

Definition at line 86 of file sepa_zerohalf.c.

#define DEFAULT_SUBSCIPOBJECTIVE 'v'

auxiliary IP objective function type

Definition at line 89 of file sepa_zerohalf.c.

#define DEFAULT_RELAXCONTVARS FALSE

should continuous variables be relaxed by adding variable bounds?

Definition at line 90 of file sepa_zerohalf.c.

#define DEFAULT_SCALEFRACCOEFFS TRUE

should rows be scaled to make fractional coefficients integer?

Definition at line 91 of file sepa_zerohalf.c.

#define DEFAULT_SUBSCIPSETTINGS "-"

optional settings file of the auxiliary IP (-: none)

Definition at line 92 of file sepa_zerohalf.c.

#define DEFAULT_SUBSCIPSOLLIMIT -1

limits/solutions setting of the auxiliary IP

Definition at line 93 of file sepa_zerohalf.c.

#define DEFAULT_SUBSCIPUSEALLSOLS TRUE

should all (proper) solutions of the auxiliary IP be used to generate cuts instead of using only the best?

Definition at line 94 of file sepa_zerohalf.c.

#define DEFAULT_PPDELTA 0.500

value of delta parameter used in preprocessing method 'd'

Definition at line 97 of file sepa_zerohalf.c.

#define DEFAULT_SUBSCIPOBJPEN 0.001

penalty factor used with objective function 'p' of auxiliary IP

Definition at line 98 of file sepa_zerohalf.c.

#define DEFAULT_PPMETHODS "CXGXIM"

preprocessing methods and ordering

Definition at line 100 of file sepa_zerohalf.c.

#define DEFAULT_SEPAMETHODS "2g"

preprocessing methods and ordering

Definition at line 101 of file sepa_zerohalf.c.

#define DEFAULT_MAXNCALLS -1LL

maximal number of calls (-1: unlimited)

Definition at line 102 of file sepa_zerohalf.c.

#define DEFAULT_IGNOREPREVIOUSZHCUTS FALSE

should zerohalf cuts found in previous callbacks be ignored?

Definition at line 103 of file sepa_zerohalf.c.

#define DEFAULT_ONLYORIGROWS FALSE

should only original LP rows be considered (i.e. ignore previously added LP rows)?

Definition at line 104 of file sepa_zerohalf.c.

#define DEFAULT_USEZHCUTPOOL TRUE

should zerohalf cuts be filtered using a cutpool

Definition at line 105 of file sepa_zerohalf.c.

#define DEFAULT_DELAYEDCUTS TRUE

should cuts be added to the delayed cut pool?

Definition at line 106 of file sepa_zerohalf.c.

#define DEFAULT_MAXTESTDELTA 10

maximal number of different deltas to try for cmir (-1: unlimited, 0: delta=1)

Definition at line 107 of file sepa_zerohalf.c.

#define DEFAULT_TRYNEGSCALING TRUE

should negative values also be tested in scaling for cmir?

Definition at line 108 of file sepa_zerohalf.c.

#define ORTHOFUNC 'e'

Definition at line 111 of file sepa_zerohalf.c.

#define MINORTHO 0.5

Definition at line 112 of file sepa_zerohalf.c.

#define NNONZOFFSET 500

Definition at line 115 of file sepa_zerohalf.c.

#define BOUNDSWITCH 0.50

Definition at line 116 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define USEVBDS TRUE

Definition at line 117 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define ALLOWLOCAL TRUE

Definition at line 118 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define FIXINTEGRALRHS TRUE

Definition at line 119 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define BOUNDSFORTRANS NULL

Definition at line 120 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define BOUNDTYPESFORTRANS NULL

Definition at line 121 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define MAXWEIGHTRANGE 10000.00

Definition at line 122 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define MINFRAC 0.05

Definition at line 123 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define MAXFRAC 1.00

Definition at line 124 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define MAXDNOM 1000

Definition at line 127 of file sepa_zerohalf.c.

#define MAXSCALE 1000.0

Definition at line 128 of file sepa_zerohalf.c.

#define USEVARBOUNDS TRUE

Definition at line 131 of file sepa_zerohalf.c.

Referenced by findClosestLb(), and findClosestUb().

#define ISEVEN	(	scip,
		value
	)	(SCIPisEQ((scip) , SCIPfloor(scip , (value) / 2) , (value) / 2))

is value even?

Definition at line 186 of file sepa_zerohalf.c.

#define ISODD	(	scip,
		value
	)	(!(ISEVEN((scip), (value))))

is value odd?

Definition at line 187 of file sepa_zerohalf.c.

#define XOR	(	bool1,
		bool2
	)	((bool1) ^ (bool2))

Definition at line 188 of file sepa_zerohalf.c.

Referenced by separateByGaussHeuristics().

#define DIV	(	value1,
		powerof2value
	)	(((unsigned int)(value1)) / ((unsigned int)(powerof2value)))

integer division using a power of 2 as divisor

Definition at line 189 of file sepa_zerohalf.c.

#define MOD	(	value1,
		powerof2value
	)	(((unsigned int)(value1)) % ((unsigned int)(powerof2value)))

remainder of integer division using a power of 2 as divisor

Definition at line 190 of file sepa_zerohalf.c.

#define IRRELEVANT -1

row or column is irrelevant

Definition at line 242 of file sepa_zerohalf.c.

#define ZERO_ROW -100

row has no nonzero entries

Definition at line 245 of file sepa_zerohalf.c.

Referenced by preprocessRows().

#define IDENT_TO_ROW_WITH_SMALLER_SLACK -101

row is identical to another row but has a larger slack value

Definition at line 246 of file sepa_zerohalf.c.

Referenced by preprocessRows().

#define SLACK_GREATER_THAN_MAXSLACK -102

row has a slack value > maxslack

Definition at line 247 of file sepa_zerohalf.c.

Referenced by preprocessColumns(), and preprocessRows().

#define DEFINES_VIOLATED_ZEROHALF_CUT -103

row defines a violated zerohalf cut

Definition at line 248 of file sepa_zerohalf.c.

#define NONEXISTENT_ROW -105

row does not exist (lhs is -infinity or rhs is infinity)

Definition at line 252 of file sepa_zerohalf.c.

#define NO_RELEVANT_COLUMNS -106

row does not contain relevant columns

Definition at line 253 of file sepa_zerohalf.c.

#define SLACK_GREATER_THAN_MSL_MINUS_SODD -107

row has even rhs and the sum of its slack value and the minimum slack value of a odd-rhs-row exceeds maxslack

Definition at line 254 of file sepa_zerohalf.c.

#define LARGE_COL_EXISTS -108

row contains a column which rounding penalty exceeds maxslack and the sum of this row's slack and the minimum slack of another row with the proper columns exceeds maxslack as well

Definition at line 257 of file sepa_zerohalf.c.

#define ZERO_COLUMN -200

column has no nonzero entries

Definition at line 264 of file sepa_zerohalf.c.

Referenced by preprocessColumns().

#define IDENT_TO_ANOTHER_COLUMN -201

column is identical to another column

Definition at line 265 of file sepa_zerohalf.c.

#define ZERO_LP_SOL -202

column corresponds to a variable whose LP solution is zero

Definition at line 266 of file sepa_zerohalf.c.

#define LP_SOL_EQUALS_EVEN_LB -203

column corresponds to a variable whose LP solution equals its even lb

Definition at line 267 of file sepa_zerohalf.c.

#define LP_SOL_EQUALS_ODD_LB -204

column corresponds to a variable whose LP solution equals its odd lb

Definition at line 268 of file sepa_zerohalf.c.

#define LP_SOL_EQUALS_EVEN_UB -205

column corresponds to a variable whose LP solution equals its even ub

Definition at line 269 of file sepa_zerohalf.c.

#define LP_SOL_EQUALS_ODD_UB -206

column corresponds to a variable whose LP solution equals its odd ub

Definition at line 270 of file sepa_zerohalf.c.

#define SINGLETON_COLUMN -207

column has only one nonzero entry

Definition at line 271 of file sepa_zerohalf.c.

Referenced by preprocessColumns().

#define CONTINUOUS_VARIABLE -208

column corresponds to a non-integer variable

Definition at line 272 of file sepa_zerohalf.c.

#define SMALL_FRACSOL_HEUR -209

column has been omitted (see preprocessColumnsWithSmallFracsol)

Definition at line 273 of file sepa_zerohalf.c.

#define ALL_MATRIX_ROWS_DELETED -210

all rows (of the current subproblem) have been deleted

Definition at line 274 of file sepa_zerohalf.c.

#define BITARRAYBASETYPE unsigned int

base type used for the bitarray data structures

Definition at line 285 of file sepa_zerohalf.c.

#define BITARRAYBITMASKTYPE BITARRAYBASETYPE

Definition at line 286 of file sepa_zerohalf.c.

Referenced by preprocessColumns(), and separateByGaussHeuristics().

#define BITARRAY BITARRAYBASETYPE*

Definition at line 295 of file sepa_zerohalf.c.

Referenced by preprocessRows(), preprocessTrivialZerohalfCuts(), separateByAuxGraph(), separateByEnumerationHeuristics(), and separateBySolvingAuxIP().

#define BITMASK ( pos ) ((unsigned int)(1 << (pos)))

get the bit mask where the pos-th bit is set

Definition at line 298 of file sepa_zerohalf.c.

#define BITSET	(	var,
		pos
	)	(var) \|= BITMASK(pos)

set the pos-th bit of var

Definition at line 301 of file sepa_zerohalf.c.

#define BITISSET	(	var,
		pos
	)	(var & BITMASK(pos))

is the pos-th bit of var set?

Definition at line 304 of file sepa_zerohalf.c.

#define BITARRAYBITSET	(	barray,
		pos
	)

Value:

BITSET(barray[DIV((pos),Zerohalf_bitarraybasetypesize_nbits)], \

MOD(pos,Zerohalf_bitarraybasetypesize_nbits))

MOD

#define MOD(value1, powerof2value)

Definition: sepa_zerohalf.c:190

Zerohalf_bitarraybasetypesize_nbits

static const unsigned int Zerohalf_bitarraybasetypesize_nbits

Definition: sepa_zerohalf.c:292

DIV

#define DIV(value1, powerof2value)

Definition: sepa_zerohalf.c:189

BITSET

#define BITSET(var, pos)

Definition: sepa_zerohalf.c:301

set the pos-th bit of bitarray barray

Definition at line 307 of file sepa_zerohalf.c.

#define BITARRAYBITISSET	(	barray,
		pos
	)

Value:

BITISSET(barray[DIV(pos,Zerohalf_bitarraybasetypesize_nbits)], \

MOD(pos,Zerohalf_bitarraybasetypesize_nbits))

MOD

#define MOD(value1, powerof2value)

Definition: sepa_zerohalf.c:190

Zerohalf_bitarraybasetypesize_nbits

static const unsigned int Zerohalf_bitarraybasetypesize_nbits

Definition: sepa_zerohalf.c:292

DIV

#define DIV(value1, powerof2value)

Definition: sepa_zerohalf.c:189

BITISSET

#define BITISSET(var, pos)

Definition: sepa_zerohalf.c:304

is the pos-th bit of bitarray barray set?

Definition at line 311 of file sepa_zerohalf.c.

Referenced by getZerohalfWeightvectorFromSelectedRowsBitarray(), hasMatrixMax2EntriesPerRow(), preprocessColumns(), and separateByAuxGraph().

#define BITARRAYCLEAR	(	barray,
		barraysize
	)	BMSclearMemoryArray(barray,barraysize)

clear bitarray

Definition at line 315 of file sepa_zerohalf.c.

Referenced by separateByAuxGraph(), and separateByEnumerationHeuristics().

#define GETREQUIREDBITARRAYSIZE ( nvalstostore )

Value:

((((unsigned int)(nvalstostore)) % (Zerohalf_bitarraybasetypesize_nbits) == 0) \
      ? (((unsigned int)(nvalstostore)) / (Zerohalf_bitarraybasetypesize_nbits)) \
      : ((((unsigned int)(nvalstostore)) / (Zerohalf_bitarraybasetypesize_nbits)) + 1))

calculates the number of array elements (w.r.t. the bitarray base type) required to create the bitarray

Definition at line 318 of file sepa_zerohalf.c.

#define GETBITARRAYINDEX ( pos ) DIV((pos),Zerohalf_bitarraybasetypesize_nbits)

get the corresponding array element of a bitarray position

Definition at line 324 of file sepa_zerohalf.c.

Referenced by preprocessColumns(), and separateByGaussHeuristics().

#define GETBITARRAYMASK ( pos ) BITMASK(MOD((pos),Zerohalf_bitarraybasetypesize_nbits))

get the bitmask to mask all bits except the pos-th bit of an array element

Definition at line 327 of file sepa_zerohalf.c.

Referenced by preprocessColumns(), and separateByGaussHeuristics().

#define BITARRAYSFOREACH	(	barray1,
		barray2,
		size,
		op
	)

Value:

{                                                                    \
      int idx__;                                                        \
      for( idx__ = 0 ; idx__ < (size) ; ++idx__)                        \
      {                                                                 \
         barray2[idx__] op barray1[idx__];                              \
      }                                                                 \
   }

apply operation op for all array elements of bitarray barray1 and barray2

Definition at line 330 of file sepa_zerohalf.c.

#define BITARRAYSXOR	(	barray1,
		barray2,
		size
	)	BITARRAYSFOREACH(barray1,barray2,size,^=)

barray2 = barray1 XOR barray2

Definition at line 340 of file sepa_zerohalf.c.

Referenced by separateByAuxGraph(), separateByEnumerationHeuristics(), and separateByGaussHeuristics().

#define BITARRAYSAREEQUAL	(	barray1,
		barray2,
		size
	)	(memcmp((void)(barray1), (void)(barray2), (size_t)((size) * (Zerohalf_bitarraybasetypesize))) == 0)

are barray1 and barray2 equal?

Definition at line 343 of file sepa_zerohalf.c.

Referenced by preprocessRows(), and preprocessTrivialZerohalfCuts().

#define BRANCHPRIORITY__AVOID_BRANCHING 0

creates a "subscip" representing the following auxiliary IP (AuxIP): min z := s^T v + x^T y s.t. (b (mod 2))^T v - 2q = 1 (A (mod 2))^T v - y - -2r = 0

v \in {0,1}^nrowsind y \in {0,1}^ncolsind r \in Z^ncolsind_+ q \in Z_+

Definition at line 4881 of file sepa_zerohalf.c.

#define BRANCHPRIORITY__PREFER_BRANCHING 0

Definition at line 4882 of file sepa_zerohalf.c.

Typedef Documentation

typedef enum cutseparatedby CUTSEPARATEDBY

Definition at line 178 of file sepa_zerohalf.c.

typedef struct Zerohalf_SubLPData ZEROHALF_SUBLPDATA

Definition at line 448 of file sepa_zerohalf.c.

typedef struct Zerohalf_LPData ZEROHALF_LPDATA

Definition at line 488 of file sepa_zerohalf.c.

typedef struct Zerohalf_AuxIPData ZEROHALF_AUXIPDATA

Definition at line 534 of file sepa_zerohalf.c.

typedef struct Zerohalf_Mod2Data ZEROHALF_MOD2DATA

Definition at line 564 of file sepa_zerohalf.c.

typedef struct Zerohalf_CutData ZEROHALF_CUTDATA

Definition at line 594 of file sepa_zerohalf.c.

typedef struct Zerohalf_AuxGraph_Node ZEROHALF_AUXGRAPH_NODE

Definition at line 600 of file sepa_zerohalf.c.

typedef struct Zerohalf_AuxGraph ZEROHALF_AUXGRAPH

Definition at line 620 of file sepa_zerohalf.c.

Enumeration Type Documentation

enum preprocessingmethods

preprocessing methods, usable within the ppmethods parameter

Enumerator
MODGAUSSIANELIMINATION
DELETEZEROROWS
DELETEZEROCOLS
DELETECOLSINGLETONS
ADDTRIVIALCUTS
DELETEIDENTROWS
MERGEIDENTCOLS
DELETELARGESLACKROWS
DELETESMALLFRACSOLCOLS
DELETEROWSWRTMINSLACK
PPCOLUMNS
PPROWS

Definition at line 139 of file sepa_zerohalf.c.

enum sepamethods

separation methods, usable within the sepamethods parameter

Enumerator
STOPIFCUTWASFOUND
SOLVEAUXSCIP
SOLVEAUXSCIPEXACT
ENUMHEURNMAX1
ENUMHEURNMAX2
GAUSSHEUR
MAX2ODDENTRIESPERROW

Definition at line 159 of file sepa_zerohalf.c.

enum cutseparatedby

statistics: "origin" of separated cut

Enumerator
AUXIP
DECOMPOSITION
PPZEROONEROW
HEURISTICSENUM
HEURISTICSGAUSS
AUXGRAPH

Definition at line 174 of file sepa_zerohalf.c.

Function Documentation

static SCIP_RETCODE ZerohalfSubLPDataCreate	(	SCIP *	scip,
		ZEROHALF_SUBLPDATA **	subproblem
	)

static

creates and initializes sub LP data structures

Parameters

scip	SCIP data structure
subproblem	pointer to store pointer to created data structure

Definition at line 630 of file sepa_zerohalf.c.

static void ZerohalfSubLPDataFree	(	SCIP *	scip,
		ZEROHALF_SUBLPDATA **	subproblem
	)

static

frees sub LP data structures

Parameters

scip	SCIP data structure
subproblem	pointer to pointer of data structure

Definition at line 655 of file sepa_zerohalf.c.

References SCIPfreeMemoryArray.

static SCIP_RETCODE ZerohalfLPDataCreate	(	SCIP *	scip,
		ZEROHALF_LPDATA **	lpdata
	)

static

creates and initializes LP data structures

Parameters

scip	SCIP data structure
lpdata	pointer to store pointer to created data structure

Definition at line 695 of file sepa_zerohalf.c.

static SCIP_RETCODE ZerohalfLPDataFree	(	SCIP *	scip,
		ZEROHALF_LPDATA **	lpdata
	)

static

frees LP data structures

Parameters

scip	SCIP data structure
lpdata	pointer to pointer of data structure

Definition at line 730 of file sepa_zerohalf.c.

static SCIP_RETCODE ZerohalfMod2DataCreate	(	SCIP *	scip,
		ZEROHALF_MOD2DATA **	mod2data
	)

static

creates and initializes mod 2 data structures

Parameters

scip	SCIP data structure
mod2data	pointer to store pointer to created data structure

Definition at line 798 of file sepa_zerohalf.c.

static SCIP_RETCODE ZerohalfMod2DataFree	(	SCIP *	scip,
		ZEROHALF_MOD2DATA **	mod2data
	)

static

frees data structures

Parameters

scip	SCIP data structure
mod2data	pointer to pointer of data structure

Definition at line 829 of file sepa_zerohalf.c.

static SCIP_RETCODE ZerohalfAuxIPDataCreate	(	SCIP *	scip,
		ZEROHALF_AUXIPDATA **	auxipdata
	)

static

creates and initializes auxiliary IP data structures

Parameters

scip	SCIP data structure
auxipdata	pointer to store pointer to created data structure

Definition at line 897 of file sepa_zerohalf.c.

Referenced by separateBySolvingAuxIP().

static SCIP_RETCODE ZerohalfAuxIPDataFree	(	SCIP *	scip,
		ZEROHALF_AUXIPDATA **	auxipdata
	)

static

frees auxiliary IP data structures

Parameters

scip	SCIP data structure
auxipdata	pointer to pointer of data structure

Definition at line 924 of file sepa_zerohalf.c.

References SCIP_CALL, and SCIPfree().

Referenced by separateBySolvingAuxIP().

static SCIP_RETCODE ZerohalfCutDataCreate	(	SCIP *	scip,
		ZEROHALF_CUTDATA **	cutdata,
		ZEROHALF_SUBLPDATA *	relatedsubproblem,
		ZEROHALF_MOD2DATA *	relatedmod2data,
		int	nrrowsincut,
		int	nrowsincut,
		CUTSEPARATEDBY	separatedby
	)

static

creates and initializes cut data structures

Parameters

scip	SCIP data structure
cutdata	pointer to pointer of data structure
relatedsubproblem	pointer to corresponding subproblem
relatedmod2data	pointer to corresponding mod 2 data
nrrowsincut	number of preprocessed / mod 2 rows in cut
nrowsincut	number of original / LP rows in cut
separatedby	flag storing the method that separated this cut

Definition at line 963 of file sepa_zerohalf.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, and TRUE.

Referenced by preprocessTrivialZerohalfCuts(), separateByAuxGraph(), separateByEnumerationHeuristics(), and separateBySolvingAuxIP().

static SCIP_RETCODE ZerohalfCutDataFree	(	SCIP *	scip,
		ZEROHALF_CUTDATA **	cutdata
	)

static

frees cut data structures

Parameters

scip	SCIP data structure
cutdata	pointer to pointer of data structure

Definition at line 1008 of file sepa_zerohalf.c.

References SCIP_CALL, and SCIPreleaseRow().

static SCIP_RETCODE ZerohalfAuxGraphNodeCreate	(	SCIP *	scip,
		ZEROHALF_AUXGRAPH_NODE **	node
	)

static

creates and initializes auxiliary graph node data structures

Parameters

scip	SCIP data structure
node	pointer to store pointer to created data structure

Definition at line 1030 of file sepa_zerohalf.c.

Referenced by separateByAuxGraph().

static SCIP_RETCODE ZerohalfAuxGraphNodeFree	(	SCIP *	scip,
		ZEROHALF_AUXGRAPH_NODE **	node
	)

static

frees auxiliary graph node data structures

Parameters

scip	SCIP data structure
node	pointer to pointer of data structure

Definition at line 1054 of file sepa_zerohalf.c.

References SCIPfreeMemoryArray.

Referenced by ZerohalfAuxGraphFree().

static SCIP_RETCODE ZerohalfAuxGraphCreate	(	SCIP *	scip,
		ZEROHALF_AUXGRAPH **	auxgraph
	)

static

creates and initializes auxiliary graph data structures

Parameters

scip	SCIP data structure
auxgraph	pointer to store pointer to created data structure

Definition at line 1083 of file sepa_zerohalf.c.

Referenced by separateByAuxGraph().

static SCIP_RETCODE ZerohalfAuxGraphFree	(	SCIP *	scip,
		ZEROHALF_AUXGRAPH **	auxgraph
	)

static

frees auxiliary graph data structures

Parameters

scip	SCIP data structure
auxgraph	pointer to pointer of data structure

Definition at line 1104 of file sepa_zerohalf.c.

References NULL, SCIP_CALL, SCIPfreeMemoryArray, and ZerohalfAuxGraphNodeFree().

Referenced by separateByAuxGraph().

static SCIP_DECL_SORTINDCOMP ( compRealNonDecreasing )

static

comparator function for sorting an index array non-decreasingly according to a real array

Definition at line 1492 of file sepa_zerohalf.c.

static SCIP_DECL_SORTINDCOMP ( compRealNonIncreasing )

static

comparator function for sorting an index array non-increasingly according to a real array

Definition at line 1509 of file sepa_zerohalf.c.

static SCIP_RETCODE getRelevantColumns	(	SCIP *	scip,
		ZEROHALF_LPDATA *	lpdata
	)

static

searches for relevant columns, i.e., columns that cannot be deleted because of basic preprocessing methods

Parameters

scip	SCIP data structure
lpdata	data of current LP relaxation

Definition at line 1531 of file sepa_zerohalf.c.

static void findClosestLb	(	SCIP *	scip,
		ZEROHALF_LPDATA *	lpdata,
		SCIP_COL *	col,
		SCIP_Real *	bestlbsol,
		int *	bestlbtype,
		SCIP_VAR **	bestzvlb,
		SCIP_Real *	bestbvlb,
		SCIP_Real *	bestdvlb
	)

static

finds closest lower bound of col and stores it within lpdata; the bound can be the lower bound or the best variable lower bound with nonnegative column variable

Parameters

scip	SCIP data structure
lpdata	data of current LP relaxation
col	column to get closest lower bound
bestlbsol	pointer to store value of closest lower bound
bestlbtype	pointer to store type of closest lower bound
bestzvlb	pointer to store variable z in closest variable lower bound b*z + d
bestbvlb	pointer to store coefficient b in closest variable lower bound b*z + d
bestdvlb	pointer to store constant d in closest variable lower bound b*z + d

Definition at line 1705 of file sepa_zerohalf.c.

References NULL, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIP_VARTYPE_CONTINUOUS, SCIPcolGetLb(), SCIPcolGetLPPos(), SCIPcolGetPrimsol(), SCIPcolGetVar(), SCIPcolIsInLP(), SCIPisNegative(), SCIPvarGetCol(), SCIPvarGetNVlbs(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), and USEVARBOUNDS.

static void findClosestUb	(	SCIP *	scip,
		ZEROHALF_LPDATA *	lpdata,
		SCIP_COL *	col,
		SCIP_Real *	bestubsol,
		int *	bestubtype,
		SCIP_VAR **	bestzvub,
		SCIP_Real *	bestbvub,
		SCIP_Real *	bestdvub
	)

static

finds closest upper bound of col and stores it within lpdata; the bound can be the upper bound or the best variable upper bound with nonnegative column variable

Parameters

scip	SCIP data structure
lpdata	data of current LP relaxation
col	column to get closest upper bound
bestubsol	pointer to store value of closest upper bound
bestubtype	pointer to store type of closest upper bound
bestzvub	pointer to store variable z in closest variable upper bound b*z + d
bestbvub	pointer to store coefficient b in closest variable upper bound b*z + d
bestdvub	pointer to store constant d in closest variable upper bound b*z + d

Definition at line 1812 of file sepa_zerohalf.c.

References NULL, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIP_VARTYPE_CONTINUOUS, SCIPcolGetLPPos(), SCIPcolGetPrimsol(), SCIPcolGetUb(), SCIPcolGetVar(), SCIPcolIsInLP(), SCIPisNegative(), SCIPvarGetCol(), SCIPvarGetNVubs(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), and USEVARBOUNDS.

static SCIP_RETCODE getRelevantRows	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		ZEROHALF_LPDATA *	lpdata
	)

static

searches for relevant rows, i.e., rows containing relevant columns that cannot be deleted because of basic preprocessing methods

Parameters

scip	SCIP data structure
sepadata	separator data
lpdata	data of current LP relaxation

Definition at line 1916 of file sepa_zerohalf.c.

static SCIP_Bool hasMatrixMax2EntriesPerRow ( ZEROHALF_MOD2DATA * mod2data )

static

Parameters

mod2data considered mod 2 data

Definition at line 2393 of file sepa_zerohalf.c.

References BITARRAYBITISSET, and FALSE.

Referenced by preprocess(), and separateByAuxGraph().

static SCIP_RETCODE storeMod2Data	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		ZEROHALF_LPDATA *	lpdata,
		int	subproblemindex,
		ZEROHALF_MOD2DATA *	mod2data
	)

static

Parameters

scip	SCIP data structure
sepadata	separator data
lpdata	data of current LP relaxation
subproblemindex	index of considered subproblem
mod2data	data (mod 2)

Definition at line 2469 of file sepa_zerohalf.c.

static SCIP_RETCODE storeCutInArrays	(	SCIP *	scip,
		int	nvars,
		SCIP_VAR **	vars,
		SCIP_Real *	cutcoefs,
		SCIP_Real *	varsolvals,
		char	normtype,
		SCIP_VAR **	cutvars,
		SCIP_Real *	cutvals,
		int *	cutlen,
		SCIP_Real *	cutact,
		SCIP_Real *	cutnorm
	)

static

stores nonzero elements of dense coefficient vector as sparse vector, and calculates activity and norm

Parameters

scip	SCIP data structure
nvars	number of problem variables
vars	problem variables
cutcoefs	dense coefficient vector
varsolvals	dense variable LP solution vector
normtype	type of norm to use for efficacy norm calculation
cutvars	array to store variables of sparse cut vector
cutvals	array to store coefficients of sparse cut vector
cutlen	pointer to store number of nonzero entries in cut
cutact	pointer to store activity of cut
cutnorm	pointer to store norm of cut vector

Definition at line 2850 of file sepa_zerohalf.c.

References MAX, NULL, REALABS, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIPerrorMessage, and SCIPisZero().

Referenced by createZerohalfCutFromZerohalfWeightvector().

static SCIP_RETCODE addZerohalfCutToLP	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		ZEROHALF_CUTDATA *	cutdata,
		int *	nsepacuts,
		SCIP_RESULT *	result
	)

static

adds a separated zerohalf cut to SCIP if it was successfully created and is efficacious

Parameters

scip	SCIP data structure
sepadata	separator data
cutdata	separated zerohalf cut
nsepacuts	pointer to store number of separated (efficacious) zerohalf cuts
result	pointer to store return code

Definition at line 2961 of file sepa_zerohalf.c.

Referenced by preprocessTrivialZerohalfCuts(), separateByAuxGraph(), separateByEnumerationHeuristics(), and separateBySolvingAuxIP().

static void markRowAsRemoved	(	ZEROHALF_MOD2DATA *	mod2data,
		int	r,
		int	flag
	)

static

marks a row as "removed" and stores why it has been removed using a flag

Parameters

mod2data	considered mod 2 data
r	mod2data->rows index of row that shall be removed
flag	flag (cause of removal)

Definition at line 3027 of file sepa_zerohalf.c.

Referenced by preprocessColumns(), and preprocessRows().

static void markColAsRemovedAndClearCol	(	ZEROHALF_MOD2DATA *	mod2data,
		int	c,
		int	flag
	)

static

marks a row as "removed" and stores why it has been removed using a flag. in addition it clears this column's mod 2 data

Parameters

mod2data	considered mod 2 data
c	mod2data->relatedsubproblem->rcols index of column that shall be removed
flag	flag (cause of removal)

Definition at line 3046 of file sepa_zerohalf.c.

Referenced by preprocessColumns().

static SCIP_RETCODE getZerohalfWeightvectorFromSelectedRowsBitarray	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		ZEROHALF_LPDATA *	lpdata,
		ZEROHALF_MOD2DATA *	mod2data,
		BITARRAY	rrowsincut,
		SCIP_Real **	weights,
		int *	nrowsincut
	)

static

given a subset of mod 2 rows it returns a {0,1/2} weight vector used to combine the (original) LP rows. Note: original rows a stored as lhs <= a^Tx <= rhs by SCIP. Positive weights refer to "right half-rows" a^Tx <= rhs and negative weights to "left half-rows" -a^Tx <= -lhs

Parameters

scip	SCIP data structure
sepadata	separator data
lpdata	data of current LP relaxation
mod2data	considered mod 2 data
rrowsincut	subset of selected mod2data->rows
weights	pointer to store the {-0.5,0,0.5} weights vector
nrowsincut	pointer to store the number of combined original LP rows

Definition at line 3081 of file sepa_zerohalf.c.

References BITARRAYBITISSET, BMSclearMemoryArray, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, SCIPdebugMessage, SCIPfreeMemoryArray, SCIProwGetName(), and SCIProwGetNLPNonz().

Referenced by preprocessTrivialZerohalfCuts(), separateByAuxGraph(), separateByEnumerationHeuristics(), and separateBySolvingAuxIP().

static SCIP_RETCODE createZerohalfCutFromZerohalfWeightvector	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SEPADATA *	sepadata,
		ZEROHALF_LPDATA *	lpdata,
		SCIP_Real *	weights,
		char	normtype,
		int	nzerohalfcuts,
		SCIP_Real **	varsolvals,
		ZEROHALF_CUTDATA *	cutdata,
		SCIP_Bool *	cutoff
	)

static

creates a zerohalf cut from a given weightvector

Parameters

scip	SCIP data structure
sepa	separator
sepadata	separator data
lpdata	data of current LP relaxation
weights	weightvector
normtype	SCIP normtype
nzerohalfcuts	number of zerohalf cuts (used for naming the cut)
varsolvals	pointer to array of LP solution values of variables
cutdata	pointer to data structure used for storing the cut
cutoff	whether a cutoff has been detected

Definition at line 3155 of file sepa_zerohalf.c.

References ALLOWLOCAL, BOUNDSFORTRANS, BOUNDSWITCH, BOUNDTYPESFORTRANS, FALSE, FIXINTEGRALRHS, MAXFRAC, MAXWEIGHTRANGE, MINFRAC, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarsToRow(), SCIPallocBufferArray, SCIPallocMemoryArray, SCIPcalcMIR(), SCIPcreateEmptyRowSepa(), SCIPcutGenerationHeuristicCmir(), SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetNLPs(), SCIPgetSolVals(), SCIPinfinity(), SCIPisEfficacious(), SCIPisFeasGT(), SCIPisPositive(), SCIProwChgRank(), SCIPsnprintf(), SCIPvarGetProbindex(), storeCutInArrays(), TRUE, and USEVBDS.

Referenced by preprocessTrivialZerohalfCuts(), separateByAuxGraph(), separateByEnumerationHeuristics(), and separateBySolvingAuxIP().

static SCIP_RETCODE preprocessTrivialZerohalfCuts	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SEPADATA *	sepadata,
		ZEROHALF_LPDATA *	lpdata,
		ZEROHALF_MOD2DATA *	mod2data,
		int	firstrowsind,
		int	lastrowsind,
		char	normtype,
		int	maxsepacuts,
		int	maxcuts,
		int *	nsepacuts,
		int *	nzerohalfcuts,
		ZEROHALF_CUTDATA **	zerohalfcuts,
		SCIP_Real **	varsolvals,
		CUTSEPARATEDBY	cutseparatedby,
		SCIP_RESULT *	result
	)

static

searches for trivial zerohalf cuts, given as (0,..0) row with rhs=1 and slack <= maxslack

Parameters

scip	SCIP data structure
sepa	separator
sepadata	separator data
lpdata	data of current LP relaxation
mod2data	considered (preprocessed) subproblem mod 2
firstrowsind	first mod2data->rows index to be considered
lastrowsind	last mod2data->rows index to be considered
normtype	SCIP normtype
maxsepacuts	maximal number of zerohalf cuts separated per separation round
maxcuts	maximal number of zerohalf cuts found per separation round (incl. ineff. cuts)
nsepacuts	pointer to store current number of separated zerohalf cuts
nzerohalfcuts	pointer to store current number of found zerohalf cuts
zerohalfcuts	pointer to store a found zerohalf cut
varsolvals	dense variable LP solution vector
cutseparatedby	flag
result	pointer to SCIP result value of separation

Definition at line 3320 of file sepa_zerohalf.c.

References addZerohalfCutToLP(), BITARRAY, BITARRAYSAREEQUAL, BMSclearMemoryArray, createZerohalfCutFromZerohalfWeightvector(), FALSE, getZerohalfWeightvectorFromSelectedRowsBitarray(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPfreeMemoryArray, SCIPisLE(), TRUE, and ZerohalfCutDataCreate().

Referenced by preprocess(), and separateByGaussHeuristics().

static SCIP_RETCODE preprocessRows	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		ZEROHALF_LPDATA *	lpdata,
		ZEROHALF_MOD2DATA *	mod2data,
		int	firstrowsind,
		int	lastrowsind,
		SCIP_Bool	removezerorows,
		SCIP_Bool	removelargeslackrows,
		SCIP_Bool	removeidenticalrows
	)

static

applies some row reductions

Parameters

scip	SCIP data structure
sepadata	separator data
lpdata	data of current LP relaxation
mod2data	considered (preprocessed) subproblem mod 2
firstrowsind	first mod2data->rows index to be considered
lastrowsind	last mod2data->rows index to be considered
removezerorows	should zero rows be removed?
removelargeslackrows	should rows with slack > maxslack be removed?
removeidenticalrows	should identical rows be removed?

Definition at line 3454 of file sepa_zerohalf.c.

References BITARRAY, BITARRAYSAREEQUAL, BMSclearMemoryArray, FALSE, IDENT_TO_ROW_WITH_SMALLER_SLACK, markRowAsRemoved(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGT(), SCIPisLT(), SLACK_GREATER_THAN_MAXSLACK, TRUE, and ZERO_ROW.

Referenced by preprocess(), and separateByGaussHeuristics().

static SCIP_RETCODE preprocessColumns	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		ZEROHALF_LPDATA *	lpdata,
		ZEROHALF_MOD2DATA *	mod2data,
		int	firstcolsind,
		int	lastcolsind,
		SCIP_Bool	removezerocols,
		SCIP_Bool	removecolsingletons,
		SCIP_Bool	checkresultingrows
	)

static

applies some column reductions

Parameters

scip	SCIP data structure
sepadata	separator data
lpdata	data of current LP relaxation
mod2data	considered (preprocessed) subproblem mod 2
firstcolsind	first mod2data->rows index to be considered
lastcolsind	last mod2data->rows index to be considered
removezerocols	should zero columns be removed?
removecolsingletons	should column singletons be removed?
checkresultingrows	should rows whose slack becomes larger than maxslack be removed?

Definition at line 3591 of file sepa_zerohalf.c.

References BITARRAYBITISSET, BITARRAYBITMASKTYPE, BMSclearMemoryArray, BMSmoveMemoryArray, FALSE, GETBITARRAYINDEX, GETBITARRAYMASK, markColAsRemovedAndClearCol(), markRowAsRemoved(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGT(), SINGLETON_COLUMN, SLACK_GREATER_THAN_MAXSLACK, TRUE, and ZERO_COLUMN.

Referenced by preprocess(), and separateByGaussHeuristics().

static SCIP_RETCODE preprocessModGaussElim	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		ZEROHALF_LPDATA *	lpdata,
		ZEROHALF_MOD2DATA *	mod2data
	)

static

applies modified Gaussian Elimination reduction

Parameters

scip	SCIP data structure
sepadata	separator data
lpdata	data of current LP relaxation
mod2data	considered (preprocessed) subproblem mod 2

Definition at line 3769 of file sepa_zerohalf.c.

Referenced by preprocess().

static SCIP_RETCODE decomposeProblem	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		ZEROHALF_LPDATA *	lpdata
	)

static

decomposes the problem into subproblems which can be considered separately

Parameters

scip	SCIP data structure
sepadata	separator data
lpdata	data of current LP relaxation

Definition at line 3905 of file sepa_zerohalf.c.

static SCIP_RETCODE preprocessColumnsWithSmallFracsol	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		ZEROHALF_MOD2DATA *	mod2data,
		SCIP_Real	delta
	)

static

removes the largest number of columns such that the sum of the corresponding variables is at most delta

Parameters

scip	SCIP data structure
sepadata	separator data
mod2data	considered (preprocessed) subproblem mod 2
delta	delta value

Definition at line 4294 of file sepa_zerohalf.c.

Referenced by preprocess().

static SCIP_RETCODE preprocessConsiderMinSlack	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		ZEROHALF_LPDATA *	lpdata,
		ZEROHALF_MOD2DATA *	mod2data,
		SCIP_Bool	removelargeslackrows,
		SCIP_Bool	removelargecolrows
	)

static

removes some rows that cannot be combined because the resulting slack would be larger than maxslack

Parameters

scip	SCIP data structure
sepadata	separator data
lpdata	data of current LP relaxation
mod2data	considered (preprocessed) subproblem mod 2
removelargeslackrows	should rows with slack + minslack > maxslack be removed?
removelargecolrows	should rows with "large valued" columns that cannot be negated be removed?

Definition at line 4355 of file sepa_zerohalf.c.

Referenced by preprocess().

static SCIP_RETCODE preprocessIdenticalColums	(	SCIP *	scip,
		ZEROHALF_MOD2DATA *	mod2data
	)

static

aggregates identical columns into one column whose (artificial) LP solution is the sum of the aggregated columns

Parameters

scip	SCIP data structure
mod2data	considered (preprocessed) subproblem mod 2

Definition at line 4537 of file sepa_zerohalf.c.

Referenced by preprocess().

static SCIP_RETCODE preprocess	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SEPADATA *	sepadata,
		ZEROHALF_LPDATA *	lpdata,
		ZEROHALF_MOD2DATA *	mod2data,
		char	normtype,
		int	maxsepacuts,
		int	maxcuts,
		int *	nsepacuts,
		int *	nzerohalfcuts,
		ZEROHALF_CUTDATA **	zerohalfcuts,
		SCIP_Real **	varsolvals,
		SCIP_RESULT *	result
	)

static

preprocess subproblem

Parameters

scip	SCIP data structure
sepa	separator
sepadata	separator data
lpdata	data of current LP relaxation
mod2data	considered (preprocessed) subproblem mod 2
normtype	type of norm to use for efficacy norm calculation
maxsepacuts	maximal number of zerohalf cuts separated per separation round
maxcuts	maximal number of zerohalf cuts found per separation round (incl. ineff. cuts)
nsepacuts	pointer to store current number of separated zerohalf cuts
nzerohalfcuts	pointer to store current number of found zerohalf cuts
zerohalfcuts	array to store found zerohalf cuts
varsolvals	dense variable LP solution vector
result	pointer to SCIP result value of separation

Definition at line 4616 of file sepa_zerohalf.c.

References ADDTRIVIALCUTS, DELETECOLSINGLETONS, DELETEIDENTROWS, DELETELARGESLACKROWS, DELETEROWSWRTMINSLACK, DELETESMALLFRACSOLCOLS, DELETEZEROCOLS, DELETEZEROROWS, FALSE, hasMatrixMax2EntriesPerRow(), MERGEIDENTCOLS, MODGAUSSIANELIMINATION, NULL, PPCOLUMNS, PPROWS, PPZEROONEROW, preprocessColumns(), preprocessColumnsWithSmallFracsol(), preprocessConsiderMinSlack(), preprocessIdenticalColums(), preprocessModGaussElim(), preprocessRows(), preprocessTrivialZerohalfCuts(), SCIP_CALL, SCIP_INVALIDDATA, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPallocMemoryArray, SCIPerrorMessage, and TRUE.

static SCIP_Real calcObjWeight	(	BITARRAY	rowaggregation,
		int	nrrows
	)

static

returns the objective weights for the weighted feasibility AuxIP

Parameters

rowaggregation	row aggregation bitarray
nrrows	number of relevant rows

Definition at line 4851 of file sepa_zerohalf.c.

static SCIP_RETCODE createSubscip	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		ZEROHALF_LPDATA *	lpdata,
		ZEROHALF_MOD2DATA *	mod2data,
		ZEROHALF_AUXIPDATA *	auxipdata,
		SCIP_Bool	setnodelimit
	)

static

Parameters

scip	SCIP data structure
sepadata	separator data
lpdata	data of current LP relaxation
mod2data	considered (preprocessed) subproblem mod 2
auxipdata	pointer to data structure to store the auxiliary IP data
setnodelimit	should a node limit be set?

Definition at line 4884 of file sepa_zerohalf.c.

Referenced by separateBySolvingAuxIP().

static SCIP_RETCODE solveSubscip	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		ZEROHALF_MOD2DATA *	mod2data,
		ZEROHALF_AUXIPDATA *	auxipdata,
		SCIP_SOL ***	sols,
		int *	nsols
	)

static

solves the auxiliary IP given as subscip

Parameters

scip	SCIP data structure
sepadata	separator data
mod2data	considered (preprocessed) subproblem mod 2
auxipdata	auxiliary IP data
sols	pointer to store array of solutions
nsols	pointer to store number of solutions

Definition at line 5235 of file sepa_zerohalf.c.

Referenced by separateBySolvingAuxIP().

static SCIP_RETCODE getZerohalfWeightvectorForSingleRow	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		ZEROHALF_LPDATA *	lpdata,
		int	rowsindex,
		int	rrowsindex,
		SCIP_Real **	weights
	)

static

determines the weightvector for a single row

Parameters

scip	SCIP data structure
sepadata	separator data
lpdata	data of current LP relaxation
rowsindex	lpdata->rows index
rrowsindex	"subproblem"->rrows index
weights	pointer to store the weight vector

Definition at line 5368 of file sepa_zerohalf.c.

static SCIP_RETCODE getBitarrayOfSelectedRows	(	SCIP *	scip,
		ZEROHALF_MOD2DATA *	mod2data,
		ZEROHALF_AUXIPDATA *	auxipdata,
		SCIP_SOL *	solution,
		BITARRAY *	rrowsincut,
		int *	nrrowsincut
	)

static

gets the subset of rows that should be combined to a violated zerohalf cut

Parameters

scip	SCIP data structure
mod2data	considered (preprocessed) subproblem mod 2
auxipdata	auxiliary IP data
solution	considered solution
rrowsincut	pointer to store the subset of rows as bitarray (length: number of relevant rows)
nrrowsincut	number of combined relevant rows

Definition at line 5413 of file sepa_zerohalf.c.

Referenced by separateBySolvingAuxIP().

static SCIP_RETCODE separateBySolvingAuxIP	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SEPADATA *	sepadata,
		ZEROHALF_LPDATA *	lpdata,
		ZEROHALF_MOD2DATA *	mod2data,
		char	normtype,
		int	maxsepacuts,
		int	maxcuts,
		SCIP_Bool	setnodelimit,
		int *	nsepacuts,
		int *	nzerohalfcuts,
		ZEROHALF_CUTDATA **	zerohalfcuts,
		SCIP_Real **	varsolvals,
		SCIP_RESULT *	result
	)

static

separates violated zerohalf cuts by solving an auxiliary IP. (exact method; exponential time)

Parameters

scip	SCIP data structure
sepa	separator
sepadata	separator data
lpdata	data of current LP relaxation
mod2data	considered (preprocessed) subproblem mod 2
normtype	SCIP normtype
maxsepacuts	maximal number of zerohalf cuts separated per separation round
maxcuts	maximal number of zerohalf cuts found per separation round (incl. ineff. cuts)
setnodelimit	should a node limit be set for solving the auxiliary IP?
nsepacuts	pointer to store current number of separated zerohalf cuts
nzerohalfcuts	pointer to store current number of found zerohalf cuts
zerohalfcuts	array to store found zerohalf cuts
varsolvals	dense variable LP solution vector
result	pointer to SCIP result value of separation

Definition at line 5458 of file sepa_zerohalf.c.

References addZerohalfCutToLP(), AUXIP, BITARRAY, createSubscip(), createZerohalfCutFromZerohalfWeightvector(), FALSE, getBitarrayOfSelectedRows(), getZerohalfWeightvectorFromSelectedRowsBitarray(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPfreeMemoryArray, SCIPprintBestSol(), SCIPprintOrigProblem(), solveSubscip(), TRUE, ZerohalfAuxIPDataCreate(), ZerohalfAuxIPDataFree(), and ZerohalfCutDataCreate().

Referenced by process().

static SCIP_RETCODE calcInnerProductOfRowAndFracsol	(	SCIP *	scip,
		ZEROHALF_MOD2DATA *	mod2data,
		BITARRAY	row,
		SCIP_Real	maxinnerproduct,
		SCIP_Real *	innerproduct
	)

static

calculates the inner product of mod2data->row and the LP solution

Parameters

scip	SCIP data structure
mod2data	considered (preprocessed) subproblem mod 2
row	considered mod2data->row
maxinnerproduct	calculation is aborted if innerproduct >= maxinnerproduct
innerproduct	pointer to store the inner product

Definition at line 5607 of file sepa_zerohalf.c.

Referenced by separateByEnumerationHeuristics().

static SCIP_RETCODE separateByEnumerationHeuristics	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SEPADATA *	sepadata,
		ZEROHALF_LPDATA *	lpdata,
		ZEROHALF_MOD2DATA *	mod2data,
		char	normtype,
		int	maxsepacuts,
		int	maxcuts,
		int *	nsepacuts,
		int *	nzerohalfcuts,
		ZEROHALF_CUTDATA **	zerohalfcuts,
		SCIP_Real **	varsolvals,
		SCIP_RESULT *	result,
		int	maxncombinedrows
	)

static

separate violated zerohalf cuts by enumerating possible row combinations. (heuristic; polynomial time)

Parameters

scip	SCIP data structure
sepa	separator
sepadata	separator data
lpdata	data of current LP relaxation
mod2data	considered (preprocessed) subproblem mod 2
normtype	SCIP normtype
maxsepacuts	maximal number of zerohalf cuts separated per separation round
maxcuts	maximal number of zerohalf cuts found per separation round (incl. ineff. cuts)
nsepacuts	pointer to store current number of separated zerohalf cuts
nzerohalfcuts	pointer to store current number of found zerohalf cuts
zerohalfcuts	array to store found zerohalf cuts
varsolvals	dense variable LP solution vector
result	pointer to SCIP result value of separation
maxncombinedrows	maximal number of combined rows; currently only 1 or 2 is supported

Definition at line 5648 of file sepa_zerohalf.c.

References addZerohalfCutToLP(), BITARRAY, BITARRAYCLEAR, BITARRAYSXOR, BMScopyMemoryArray, calcInnerProductOfRowAndFracsol(), createZerohalfCutFromZerohalfWeightvector(), FALSE, getZerohalfWeightvectorFromSelectedRowsBitarray(), HEURISTICSENUM, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPerrorMessage, SCIPfreeBufferArray, SCIPfreeMemoryArray, SCIPisGT(), SCIPisLE(), SCIPsortInd(), and ZerohalfCutDataCreate().

Referenced by process(), separateByAuxGraph(), and separateByGaussHeuristics().

static SCIP_RETCODE addEdgeToAuxGraph	(	SCIP *	scip,
		ZEROHALF_AUXGRAPH *	graph,
		int	node1index,
		int	node2index,
		SCIP_Bool	isodd,
		SCIP_Real	weight,
		int	relatedrow
	)

static

adds an edge (and its "copy" w.r.t. the node copies) to the auxiliary graph

Parameters

scip	SCIP data structure
graph	auxiliary graph
node1index	start node of edge
node2index	end node of edge
isodd	is the rhs value of the corresponding mod2data->row odd?
weight	weight of the edge
relatedrow	corresponding mod2data->row

Definition at line 5933 of file sepa_zerohalf.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, SCIPisLT(), and SCIPisNegative().

Referenced by separateByAuxGraph().

static SCIP_RETCODE dijkstra	(	SCIP *	scip,
		ZEROHALF_AUXGRAPH *	graph,
		ZEROHALF_AUXGRAPH_NODE *	sourcenode,
		ZEROHALF_AUXGRAPH_NODE *	targetnode,
		SCIP_Real	maxdistance
	)

static

Dijkstra's shortest path algorithm. Calculates the shortest path between sourcenode and targetnode. The calculation is aborted if the shortest path cannot be shorter than maxdistance

Parameters

scip	SCIP data structure
graph	auxiliary graph
sourcenode	start node
targetnode	end node
maxdistance	calculation will be aborted if a proof is found that no shortest path with length less than maxdistance exists

Definition at line 6049 of file sepa_zerohalf.c.

Referenced by separateByAuxGraph().

static SCIP_RETCODE separateByAuxGraph	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SEPADATA *	sepadata,
		ZEROHALF_LPDATA *	lpdata,
		ZEROHALF_MOD2DATA *	mod2data,
		char	normtype,
		int	maxsepacuts,
		int	maxcuts,
		int *	nsepacuts,
		int *	nzerohalfcuts,
		ZEROHALF_CUTDATA **	zerohalfcuts,
		SCIP_Real **	varsolvals,
		SCIP_RESULT *	result,
		SCIP_Bool *	wrongstructure
	)

static

separates violated zerohalf cuts by searching for minweight odd-valued cycles within an auxiliary graph. (exact method, but only applicable if each row contains at most two odd entries; polynomial time)

Parameters

scip	SCIP data structure
sepa	separator
sepadata	separator data
lpdata	data of current LP relaxation
mod2data	considered (preprocessed) subproblem mod 2
normtype	SCIP normtype
maxsepacuts	maximal number of zerohalf cuts separated per separation round
maxcuts	maximal number of zerohalf cuts found per separation round (incl. ineff. cuts)
nsepacuts	pointer to store current number of separated zerohalf cuts
nzerohalfcuts	pointer to store current number of found zerohalf cuts
zerohalfcuts	array to store found zerohalf cuts
varsolvals	dense variable LP solution vector
result	pointer to SCIP result value of separation
wrongstructure	pointer to store if there is a row with more than two odd entries

Definition at line 6147 of file sepa_zerohalf.c.

References addEdgeToAuxGraph(), addZerohalfCutToLP(), AUXGRAPH, BITARRAY, BITARRAYBITISSET, BITARRAYCLEAR, BITARRAYSXOR, createZerohalfCutFromZerohalfWeightvector(), dijkstra(), FALSE, getZerohalfWeightvectorFromSelectedRowsBitarray(), hasMatrixMax2EntriesPerRow(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPfreeBufferArray, SCIPfreeMemoryArray, SCIPisLE(), separateByEnumerationHeuristics(), TRUE, ZerohalfAuxGraphCreate(), ZerohalfAuxGraphFree(), ZerohalfAuxGraphNodeCreate(), and ZerohalfCutDataCreate().

Referenced by process().

static SCIP_RETCODE separateByGaussHeuristics	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SEPADATA *	sepadata,
		ZEROHALF_LPDATA *	lpdata,
		ZEROHALF_MOD2DATA *	mod2data,
		char	normtype,
		int	maxsepacuts,
		int	maxcuts,
		int *	nsepacuts,
		int *	nzerohalfcuts,
		ZEROHALF_CUTDATA **	zerohalfcuts,
		SCIP_Real **	varsolvals,
		SCIP_RESULT *	result
	)

static

separates violated zerohalf cuts using an extended Gaussian elimination. (heuristic; polynomial time)

Parameters

scip	SCIP data structure
sepa	separator
sepadata	separator data
lpdata	data of current LP relaxation
mod2data	considered (preprocessed) subproblem mod 2
normtype	SCIP normtype
maxsepacuts	maximal number of zerohalf cuts separated per separation round
maxcuts	maximal number of zerohalf cuts found per separation round (incl. ineff. cuts)
nsepacuts	pointer to store current number of separated zerohalf cuts
nzerohalfcuts	pointer to store current number of found zerohalf cuts
zerohalfcuts	array to store found zerohalf cuts
varsolvals	dense variable LP solution vector
result	pointer to SCIP result value of separation

Definition at line 6407 of file sepa_zerohalf.c.

References BITARRAYBITMASKTYPE, BITARRAYSXOR, FALSE, GETBITARRAYINDEX, GETBITARRAYMASK, HEURISTICSGAUSS, NULL, preprocessColumns(), preprocessRows(), preprocessTrivialZerohalfCuts(), SCIP_CALL, SCIP_OKAY, SCIPisGT(), SCIPisLE(), SCIPsortInd(), separateByEnumerationHeuristics(), TRUE, and XOR.

Referenced by process().

static SCIP_RETCODE process	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SEPADATA *	sepadata,
		ZEROHALF_LPDATA *	lpdata,
		ZEROHALF_MOD2DATA *	mod2data,
		char	normtype,
		int	maxsepacuts,
		int	maxcuts,
		int *	nsepacuts,
		int *	nzerohalfcuts,
		ZEROHALF_CUTDATA **	zerohalfcuts,
		SCIP_Real **	varsolvals,
		SCIP_RESULT *	result
	)

static

processes subproblem (i.e. runs separation algorithms)

Parameters

scip	SCIP data structure
sepa	separator
sepadata	separator data
lpdata	data of current LP relaxation
mod2data	considered (preprocessed) subproblem mod 2
normtype	SCIP normtype
maxsepacuts	maximal number of zerohalf cuts separated per separation round
maxcuts	maximal number of zerohalf cuts found per separation round (incl. ineff. cuts)
nsepacuts	pointer to store current number of separated zerohalf cuts
nzerohalfcuts	pointer to store current number of found zerohalf cuts
zerohalfcuts	array to store found zerohalf cuts
varsolvals	dense variable LP solution vector
result	pointer to SCIP result value of separation

Definition at line 6544 of file sepa_zerohalf.c.

References BMSclearMemoryArray, ENUMHEURNMAX1, ENUMHEURNMAX2, FALSE, GAUSSHEUR, MAX2ODDENTRIESPERROW, NULL, SCIP_Bool, SCIP_CALL, SCIP_INVALIDDATA, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPallocMemoryArray, SCIPerrorMessage, separateByAuxGraph(), separateByEnumerationHeuristics(), separateByGaussHeuristics(), separateBySolvingAuxIP(), SOLVEAUXSCIP, SOLVEAUXSCIPEXACT, STOPIFCUTWASFOUND, and TRUE.

static SCIP_DECL_SEPACOPY ( sepaCopyZerohalf )

static

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

Definition at line 6824 of file sepa_zerohalf.c.

static SCIP_DECL_SEPAFREE ( sepaFreeZerohalf )

static

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

Definition at line 6838 of file sepa_zerohalf.c.

References SCIPfreeMemoryArray.

static SCIP_DECL_SEPAEXECLP ( sepaExeclpZerohalf )

static

LP solution separation method of separator

Definition at line 6902 of file sepa_zerohalf.c.

SCIP_RETCODE SCIPincludeSepaZerohalf ( SCIP * scip )

creates the zerohalf separator and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 7450 of file sepa_zerohalf.c.

Referenced by SCIPincludeDefaultPlugins().

Variable Documentation

const unsigned int Zerohalf_bitarraybasetypesize = sizeof(BITARRAYBASETYPE)

static

size of BITARRAYBASETYPE

Definition at line 289 of file sepa_zerohalf.c.

const unsigned int Zerohalf_bitarraybasetypesize_nbits = sizeof(BITARRAYBASETYPE) << 3

static

number of bits per BITARRAYBASETYPE

Definition at line 292 of file sepa_zerohalf.c.

SCIP

Detailed Description

Macros

Typedefs

Enumerations

Functions

Variables

Macro Definition Documentation

Typedef Documentation

Enumeration Type Documentation

Function Documentation

Variable Documentation