sepa_zerohalf.c File Reference

Detailed Description

{0,1/2}-cuts separator

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"

< print statistics

Definition at line 61 of file sepa_zerohalf.c.

Referenced by process(), and SCIP_DECL_SEPACOPY().

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

Definition at line 62 of file sepa_zerohalf.c.

#define SEPA_PRIORITY   -6000

Definition at line 63 of file sepa_zerohalf.c.

#define SEPA_FREQ   -1

Definition at line 64 of file sepa_zerohalf.c.

#define SEPA_MAXBOUNDDIST   0.0

Definition at line 65 of file sepa_zerohalf.c.

#define SEPA_USESSUBSCIP   TRUE

Definition at line 66 of file sepa_zerohalf.c.

#define SEPA_DELAY   FALSE

Definition at line 67 of file sepa_zerohalf.c.

#define DEFAULT_MAXROUNDS   5

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

Definition at line 69 of file sepa_zerohalf.c.

#define DEFAULT_MAXROUNDSROOT   10

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

Definition at line 70 of file sepa_zerohalf.c.

#define DEFAULT_MAXSEPACUTS   50

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

Definition at line 71 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 72 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 73 of file sepa_zerohalf.c.

#define DEFAULT_DECOMPOSEPROBLEM   FALSE

should problem be decomposed into subproblems (if possible)?

Definition at line 74 of file sepa_zerohalf.c.

#define DEFAULT_MAXDEPTH   -1

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

Definition at line 75 of file sepa_zerohalf.c.

#define DEFAULT_MINVIOLATION   0.30

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

Definition at line 76 of file sepa_zerohalf.c.

#define DEFAULT_FORCECUTSTOLP   FALSE

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

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

#define DEFAULT_SUBSCIPOBJECTIVE   'v'

auxiliary IP objective function type

Definition at line 87 of file sepa_zerohalf.c.

#define DEFAULT_RELAXCONTVARS   FALSE

should continuous variables be relaxed by adding variable bounds?

Definition at line 88 of file sepa_zerohalf.c.

#define DEFAULT_SCALEFRACCOEFFS   TRUE

should rows be scaled to make fractional coefficients integer?

Definition at line 89 of file sepa_zerohalf.c.

#define DEFAULT_SUBSCIPSETTINGS   "-"

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

Definition at line 90 of file sepa_zerohalf.c.

#define DEFAULT_SUBSCIPSOLLIMIT   -1

limits/solutions setting of the auxiliary IP

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

#define DEFAULT_PPDELTA   0.500

value of delta parameter used in preprocessing method 'd'

Definition at line 95 of file sepa_zerohalf.c.

#define DEFAULT_SUBSCIPOBJPEN   0.001

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

Definition at line 96 of file sepa_zerohalf.c.

#define DEFAULT_PPMETHODS   "CXGXIM"

preprocessing methods and ordering

Definition at line 98 of file sepa_zerohalf.c.

#define DEFAULT_SEPAMETHODS   "2g"

preprocessing methods and ordering

Definition at line 99 of file sepa_zerohalf.c.

#define DEFAULT_MAXNCALLS   -1LL

maximal number of calls (-1: unlimited)

Definition at line 100 of file sepa_zerohalf.c.

#define DEFAULT_IGNOREPREVIOUSZHCUTS   FALSE

should zerohalf cuts found in previous callbacks be ignored?

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

#define DEFAULT_USEZHCUTPOOL   TRUE

should zerohalf cuts be filtered using a cutpool

Definition at line 103 of file sepa_zerohalf.c.

#define DEFAULT_DELAYEDCUTS   TRUE

should cuts be added to the delayed cut pool?

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

#define DEFAULT_TRYNEGSCALING   TRUE

should negative values also be tested in scaling for cmir?

Definition at line 106 of file sepa_zerohalf.c.

#define ORTHOFUNC   'e'

Definition at line 109 of file sepa_zerohalf.c.

#define MINORTHO   0.5

Definition at line 110 of file sepa_zerohalf.c.

#define NNONZOFFSET   500

Definition at line 113 of file sepa_zerohalf.c.

#define BOUNDSWITCH   0.50

Definition at line 114 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define USEVBDS   TRUE

Definition at line 115 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define ALLOWLOCAL   TRUE

Definition at line 116 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define FIXINTEGRALRHS   TRUE

Definition at line 117 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define BOUNDSFORTRANS   NULL

Definition at line 118 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define BOUNDTYPESFORTRANS   NULL

Definition at line 119 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define MAXWEIGHTRANGE   10000.00

Definition at line 120 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define MINFRAC   0.05

Definition at line 121 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define MAXFRAC   1.00

Definition at line 122 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define MAXDNOM   1000

Definition at line 125 of file sepa_zerohalf.c.

#define MAXSCALE   1000.0

Definition at line 126 of file sepa_zerohalf.c.

#define USEVARBOUNDS   TRUE

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

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

is value odd?

Definition at line 185 of file sepa_zerohalf.c.

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

Definition at line 186 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 187 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 188 of file sepa_zerohalf.c.

#define IRRELEVANT   -1

row or column is irrelevant

Definition at line 240 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define ZERO_ROW   -100

row has no nonzero entries

Definition at line 243 of file sepa_zerohalf.c.

Referenced by preprocessRows(), and ZerohalfAuxGraphFree().

#define IDENT_TO_ROW_WITH_SMALLER_SLACK   -101

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

Definition at line 244 of file sepa_zerohalf.c.

Referenced by preprocessRows(), and ZerohalfAuxGraphFree().

#define SLACK_GREATER_THAN_MAXSLACK   -102

row has a slack value > maxslack

Definition at line 245 of file sepa_zerohalf.c.

Referenced by preprocessColumns(), preprocessRows(), and ZerohalfAuxGraphFree().

#define DEFINES_VIOLATED_ZEROHALF_CUT   -103

row defines a violated zerohalf cut

Definition at line 246 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define NONEXISTENT_ROW   -105

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

Definition at line 250 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define NO_RELEVANT_COLUMNS   -106

row does not contain relevant columns

Definition at line 251 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

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

Referenced by ZerohalfAuxGraphFree().

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

Referenced by ZerohalfAuxGraphFree().

#define ZERO_COLUMN   -200

column has no nonzero entries

Definition at line 262 of file sepa_zerohalf.c.

Referenced by preprocessColumns(), and ZerohalfAuxGraphFree().

#define IDENT_TO_ANOTHER_COLUMN   -201

column is identical to another column

Definition at line 263 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define ZERO_LP_SOL   -202

column corresponds to a variable whose LP solution is zero

Definition at line 264 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define LP_SOL_EQUALS_EVEN_LB   -203

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

Definition at line 265 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define LP_SOL_EQUALS_ODD_LB   -204

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

Definition at line 266 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define LP_SOL_EQUALS_EVEN_UB   -205

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

Definition at line 267 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define LP_SOL_EQUALS_ODD_UB   -206

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

Definition at line 268 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define SINGLETON_COLUMN   -207

column has only one nonzero entry

Definition at line 269 of file sepa_zerohalf.c.

Referenced by preprocessColumns(), and ZerohalfAuxGraphFree().

#define CONTINUOUS_VARIABLE   -208

column corresponds to a non-integer variable

Definition at line 270 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define SMALL_FRACSOL_HEUR   -209

column has been omitted (see preprocessColumnsWithSmallFracsol)

Definition at line 271 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define ALL_MATRIX_ROWS_DELETED   -210

all rows (of the current subproblem) have been deleted

Definition at line 272 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define BITARRAYBASETYPE   unsigned int

base type used for the bitarray data structures

Definition at line 283 of file sepa_zerohalf.c.

#define BITARRAYBITMASKTYPE   BITARRAYBASETYPE

Definition at line 284 of file sepa_zerohalf.c.

Referenced by preprocessColumns(), and separateByGaussHeuristics().

#define BITARRAY   BITARRAYBASETYPE*

Definition at line 293 of file sepa_zerohalf.c.

Referenced by preprocess(), 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 296 of file sepa_zerohalf.c.

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

set the pos-th bit of var

Definition at line 299 of file sepa_zerohalf.c.

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

is the pos-th bit of var set?

Definition at line 302 of file sepa_zerohalf.c.

#define BITARRAYBITSET	(		barray,
			pos
	)

Value:

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

set the pos-th bit of bitarray barray

Definition at line 305 of file sepa_zerohalf.c.

#define BITARRAYBITISSET	(		barray,
			pos
	)

Value:

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

is the pos-th bit of bitarray barray set?

Definition at line 309 of file sepa_zerohalf.c.

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

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

clear bitarray

Definition at line 313 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 316 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 322 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 325 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 328 of file sepa_zerohalf.c.

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

barray2 = barray1 XOR barray2

Definition at line 338 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 341 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 4879 of file sepa_zerohalf.c.

#define BRANCHPRIORITY__PREFER_BRANCHING   0

Definition at line 4880 of file sepa_zerohalf.c.

Typedef Documentation

typedef enum cutseparatedby CUTSEPARATEDBY

Definition at line 176 of file sepa_zerohalf.c.

typedef struct Zerohalf_SubLPData ZEROHALF_SUBLPDATA

Definition at line 446 of file sepa_zerohalf.c.

typedef struct Zerohalf_LPData ZEROHALF_LPDATA

Definition at line 486 of file sepa_zerohalf.c.

typedef struct Zerohalf_AuxIPData ZEROHALF_AUXIPDATA

Definition at line 532 of file sepa_zerohalf.c.

typedef struct Zerohalf_Mod2Data ZEROHALF_MOD2DATA

Definition at line 562 of file sepa_zerohalf.c.

typedef struct Zerohalf_CutData ZEROHALF_CUTDATA

Definition at line 592 of file sepa_zerohalf.c.

typedef struct Zerohalf_AuxGraph_Node ZEROHALF_AUXGRAPH_NODE

Definition at line 598 of file sepa_zerohalf.c.

typedef struct Zerohalf_AuxGraph ZEROHALF_AUXGRAPH

Definition at line 618 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 137 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 157 of file sepa_zerohalf.c.

enum cutseparatedby

statistics: "origin" of separated cut

Enumerator
AUXIP
DECOMPOSITION
PPZEROONEROW
HEURISTICSENUM
HEURISTICSGAUSS
AUXGRAPH

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

References NULL.

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

References NULL, SCIP_CALL, SCIPallocMemory, SCIPfreeMemory, SCIPfreeMemoryArray, and ZerohalfLPDataCreate().

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

References NULL.

Referenced by ZerohalfSubLPDataFree().

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

References NULL.

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

References NULL.

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

References NULL, SCIP_CALL, SCIP_OKAY, SCIPfree(), SCIPfreeMemory, SCIPfreeMemoryArray, and ZerohalfCutDataCreate().

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

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, TRUE, and ZerohalfCutDataFree().

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

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

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPfreeMemory, SCIPreleaseRow(), and ZerohalfAuxGraphNodeCreate().

Referenced by ZerohalfCutDataCreate().

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

References NULL.

Referenced by separateByAuxGraph(), and ZerohalfCutDataFree().

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

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPfreeMemory, SCIPfreeMemoryArray, and ZerohalfAuxGraphCreate().

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

References NULL.

Referenced by separateByAuxGraph(), and ZerohalfAuxGraphNodeFree().

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

References ALL_MATRIX_ROWS_DELETED, BITARRAYBITISSET, CONTINUOUS_VARIABLE, DEFINES_VIOLATED_ZEROHALF_CUT, IDENT_TO_ANOTHER_COLUMN, IDENT_TO_ROW_WITH_SMALLER_SLACK, IRRELEVANT, LARGE_COL_EXISTS, LP_SOL_EQUALS_EVEN_LB, LP_SOL_EQUALS_EVEN_UB, LP_SOL_EQUALS_ODD_LB, LP_SOL_EQUALS_ODD_UB, NO_RELEVANT_COLUMNS, NONEXISTENT_ROW, NULL, SCIP_Bool, SCIP_CALL, SCIP_DECL_SORTINDCOMP(), SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPABORT, SCIPcolGetPrimsol(), SCIPcolGetVar(), SCIPdebugMessage, SCIPdebugPrintf, SCIPerrorMessage, SCIPfreeMemory, SCIPfreeMemoryArray, SCIPprintRow(), SCIProwGetName(), SCIPsnprintf(), SCIPvarGetName(), SINGLETON_COLUMN, SLACK_GREATER_THAN_MAXSLACK, SLACK_GREATER_THAN_MSL_MINUS_SODD, SMALL_FRACSOL_HEUR, ZERO_COLUMN, ZERO_LP_SOL, ZERO_ROW, 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 1490 of file sepa_zerohalf.c.

References SCIP_Real.

Referenced by ZerohalfAuxGraphFree().

static SCIP_DECL_SORTINDCOMP ( compRealNonIncreasing  )

static

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

Definition at line 1507 of file sepa_zerohalf.c.

References SCIP_Real.

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

References findClosestUb(), 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 1810 of file sepa_zerohalf.c.

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

Referenced by findClosestLb().

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

Referenced by findClosestUb().

static SCIP_Bool hasMatrixMax2EntriesPerRow ( ZEROHALF_MOD2DATA *  mod2data )

static

Parameters

mod2data

considered mod 2 data

Definition at line 2391 of file sepa_zerohalf.c.

References BITARRAYBITISSET, FALSE, NULL, SCIP_Bool, storeMod2Data(), and TRUE.

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

Referenced by hasMatrixMax2EntriesPerRow().

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

References addZerohalfCutToLP(), 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 2959 of file sepa_zerohalf.c.

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

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 3025 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 3044 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 3079 of file sepa_zerohalf.c.

References BITARRAYBITISSET, BMSclearMemoryArray, createZerohalfCutFromZerohalfWeightvector(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, 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 3153 of file sepa_zerohalf.c.

References ALLOWLOCAL, BOUNDSFORTRANS, BOUNDSWITCH, BOUNDTYPESFORTRANS, FALSE, FIXINTEGRALRHS, MAXFRAC, MAXWEIGHTRANGE, MINFRAC, NULL, preprocessTrivialZerohalfCuts(), 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 getZerohalfWeightvectorFromSelectedRowsBitarray(), 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 3318 of file sepa_zerohalf.c.

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

Referenced by createZerohalfCutFromZerohalfWeightvector(), 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 3452 of file sepa_zerohalf.c.

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

Referenced by preprocess(), preprocessTrivialZerohalfCuts(), 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 3589 of file sepa_zerohalf.c.

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

Referenced by preprocess(), preprocessRows(), 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 3767 of file sepa_zerohalf.c.

Referenced by preprocess(), and preprocessColumns().

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 3903 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 4292 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 4353 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 4535 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 4614 of file sepa_zerohalf.c.

References ADDTRIVIALCUTS, BITARRAY, calcObjWeight(), 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, SCIP_Real, 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 4849 of file sepa_zerohalf.c.

Referenced by preprocess().

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 4882 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 5233 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 5366 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 5411 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 5456 of file sepa_zerohalf.c.

References addZerohalfCutToLP(), AUXIP, BITARRAY, calcInnerProductOfRowAndFracsol(), 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 5605 of file sepa_zerohalf.c.

Referenced by separateByEnumerationHeuristics(), and separateBySolvingAuxIP().

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

References addEdgeToAuxGraph(), addZerohalfCutToLP(), BITARRAY, BITARRAYCLEAR, BITARRAYSXOR, BMScopyMemoryArray, calcInnerProductOfRowAndFracsol(), createZerohalfCutFromZerohalfWeightvector(), FALSE, getZerohalfWeightvectorFromSelectedRowsBitarray(), HEURISTICSENUM, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, 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 5931 of file sepa_zerohalf.c.

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

Referenced by separateByAuxGraph(), and separateByEnumerationHeuristics().

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

Referenced by addEdgeToAuxGraph(), and 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 6145 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(), separateByGaussHeuristics(), 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 6405 of file sepa_zerohalf.c.

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

Referenced by process(), and separateByAuxGraph().

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

References AUXGRAPH, AUXIP, BMSclearMemoryArray, DECOMPOSITION, ENUMHEURNMAX1, ENUMHEURNMAX2, FALSE, GAUSSHEUR, HEURISTICSENUM, HEURISTICSGAUSS, MAX2ODDENTRIESPERROW, NULL, PPZEROONEROW, SCIP_Bool, SCIP_CALL, SCIP_DECL_SEPACOPY(), SCIP_INVALIDDATA, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPallocMemoryArray, SCIPerrorMessage, SCIPincludeSepaZerohalf(), SCIPisEfficacious(), SCIPsepaGetName(), SEPA_NAME, separateByAuxGraph(), separateByEnumerationHeuristics(), separateByGaussHeuristics(), separateBySolvingAuxIP(), SOLVEAUXSCIP, SOLVEAUXSCIPEXACT, STOPIFCUTWASFOUND, and TRUE.

Referenced by separateByGaussHeuristics().

static SCIP_DECL_SEPACOPY ( sepaCopyZerohalf  )

static

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

Definition at line 6822 of file sepa_zerohalf.c.

References NULL, SCIPsepaGetData(), SCIPsepaGetName(), and SEPA_NAME.

Referenced by process().

static SCIP_DECL_SEPAFREE ( sepaFreeZerohalf  )

static

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

Definition at line 6836 of file sepa_zerohalf.c.

References NULL, SCIP_DECL_SEPAEXECLP(), SCIP_OKAY, SCIP_Real, SCIPfreeMemory, SCIPfreeMemoryArray, and SCIPsepaSetData().

static SCIP_DECL_SEPAEXECLP ( sepaExeclpZerohalf  )

static

LP solution separation method of separator

Definition at line 6900 of file sepa_zerohalf.c.

Referenced by SCIP_DECL_SEPAFREE().

SCIP_RETCODE SCIPincludeSepaZerohalf

(

SCIP *

scip

)

creates the zerohalf separator and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 7448 of file sepa_zerohalf.c.

Referenced by process(), and SCIPincludeDefaultPlugins().

Variable Documentation

const unsigned int Zerohalf_bitarraybasetypesize = sizeof(BITARRAYBASETYPE)

static

size of BITARRAYBASETYPE

Definition at line 287 of file sepa_zerohalf.c.

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

static

number of bits per BITARRAYBASETYPE

Definition at line 290 of file sepa_zerohalf.c.