sepa_zerohalf.c File Reference

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.

Referenced by SCIP_DECL_SEPACOPY(), SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAFREE(), and SCIPincludeSepaZerohalf().

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

Definition at line 64 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

#define SEPA_PRIORITY   -6000

Definition at line 65 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

#define SEPA_FREQ   -1

Definition at line 66 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

#define SEPA_MAXBOUNDDIST   0.0

Definition at line 67 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

#define SEPA_USESSUBSCIP   TRUE

Definition at line 68 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

#define SEPA_DELAY   FALSE

Definition at line 69 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

#define DEFAULT_MAXROUNDS   5

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

Definition at line 71 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

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

Referenced by SCIPincludeSepaZerohalf().

#define DEFAULT_MAXSEPACUTS   50

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

Definition at line 73 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

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

Referenced by SCIPincludeSepaZerohalf().

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

Referenced by SCIPincludeSepaZerohalf().

#define DEFAULT_DECOMPOSEPROBLEM   FALSE

should problem be decomposed into subproblems (if possible)?

Definition at line 76 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

#define DEFAULT_MAXDEPTH   -1

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

Definition at line 77 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

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

Referenced by SCIPincludeSepaZerohalf().

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

Referenced by SCIPincludeSepaZerohalf().

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

Referenced by SCIPincludeSepaZerohalf().

#define DEFAULT_MAXCUTS   100

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

Definition at line 82 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

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

Referenced by SCIPincludeSepaZerohalf().

#define DEFAULT_SUBSCIPOBJECTIVE   'v'

auxiliary IP objective function type

Definition at line 86 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

#define DEFAULT_RELAXCONTVARS   FALSE

should continuous variables be relaxed by adding variable bounds?

Definition at line 87 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

#define DEFAULT_SCALEFRACCOEFFS   TRUE

should rows be scaled to make fractional coefficients integer?

Definition at line 88 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

#define DEFAULT_SUBSCIPSETTINGS   "-"

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

Definition at line 89 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

#define DEFAULT_SUBSCIPSOLLIMIT   -1

limits/solutions setting of the auxiliary IP

Definition at line 90 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

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

Referenced by SCIPincludeSepaZerohalf().

#define DEFAULT_PPDELTA   0.500

value of delta parameter used in preprocessing method 'd'

Definition at line 93 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

#define DEFAULT_SUBSCIPOBJPEN   0.001

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

Definition at line 94 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

#define DEFAULT_PPMETHODS   "CXGXIM"

preprocessing methods and ordering

Definition at line 96 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

#define DEFAULT_SEPAMETHODS   "2g"

preprocessing methods and ordering

Definition at line 97 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

#define DEFAULT_MAXNCALLS   -1LL

maximal number of calls (-1: unlimited)

Definition at line 98 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

#define DEFAULT_IGNOREPREVIOUSZHCUTS   FALSE

should zerohalf cuts found in previous callbacks be ignored?

Definition at line 99 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

#define DEFAULT_ONLYORIGROWS   FALSE

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

Definition at line 100 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

#define DEFAULT_USEZHCUTPOOL   TRUE

should zerohalf cuts be filtered using a cutpool

Definition at line 101 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

#define DEFAULT_DELAYEDCUTS   TRUE

should cuts be added to the delayed cut pool?

Definition at line 102 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

#define DEFAULT_MAXTESTDELTA   10

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

Definition at line 103 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

#define DEFAULT_TRYNEGSCALING   TRUE

should negative values also be tested in scaling for cmir?

Definition at line 104 of file sepa_zerohalf.c.

Referenced by SCIPincludeSepaZerohalf().

#define ORTHOFUNC   'e'

Definition at line 107 of file sepa_zerohalf.c.

Referenced by SCIP_DECL_SEPAEXECLP().

#define MINORTHO   0.5

Definition at line 108 of file sepa_zerohalf.c.

Referenced by SCIP_DECL_SEPAEXECLP().

#define NNONZOFFSET   500

Definition at line 111 of file sepa_zerohalf.c.

Referenced by SCIP_DECL_SEPAEXECLP().

#define BOUNDSWITCH   0.50

Definition at line 112 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define USEVBDS   TRUE

Definition at line 113 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define ALLOWLOCAL   TRUE

Definition at line 114 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define FIXINTEGRALRHS   TRUE

Definition at line 115 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define BOUNDSFORTRANS   NULL

Definition at line 116 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define BOUNDTYPESFORTRANS   NULL

Definition at line 117 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define MAXWEIGHTRANGE   10000.00

Definition at line 118 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define MINFRAC   0.05

Definition at line 119 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define MAXFRAC   1.00

Definition at line 120 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define MAXDNOM   1000

Definition at line 123 of file sepa_zerohalf.c.

Referenced by getRelevantRows().

#define MAXSCALE   1000.0

Definition at line 124 of file sepa_zerohalf.c.

Referenced by getRelevantRows().

#define USEVARBOUNDS   TRUE

Definition at line 127 of file sepa_zerohalf.c.

Referenced by findClosestLb(), findClosestUb(), and storeMod2Data().

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

is value even?

Definition at line 182 of file sepa_zerohalf.c.

Referenced by decomposeProblem(), getRelevantRows(), and storeMod2Data().

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

is value odd?

Definition at line 183 of file sepa_zerohalf.c.

Referenced by decomposeProblem(), getRelevantColumns(), and storeMod2Data().

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

Definition at line 184 of file sepa_zerohalf.c.

Referenced by decomposeProblem(), preprocessModGaussElim(), separateByGaussHeuristics(), and storeMod2Data().

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

integer division using a power of 2 as divisor

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

#define IRRELEVANT   -1

row or column is irrelevant

Definition at line 236 of file sepa_zerohalf.c.

Referenced by decomposeProblem(), getRelevantColumns(), getRelevantRows(), and storeMod2Data().

#define ZERO_ROW   -100

row has no nonzero entries

Definition at line 239 of file sepa_zerohalf.c.

Referenced by preprocessRows(), and storeMod2Data().

#define IDENT_TO_ROW_WITH_SMALLER_SLACK   -101

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

Definition at line 240 of file sepa_zerohalf.c.

Referenced by preprocessRows().

#define SLACK_GREATER_THAN_MAXSLACK   -102

row has a slack value > maxslack

Definition at line 241 of file sepa_zerohalf.c.

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

#define DEFINES_VIOLATED_ZEROHALF_CUT   -103

row defines a violated zerohalf cut

Definition at line 242 of file sepa_zerohalf.c.

Referenced by SCIP_DECL_SEPAEXECLP().

#define NONEXISTENT_ROW   -105

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

Definition at line 246 of file sepa_zerohalf.c.

Referenced by getRelevantRows().

#define NO_RELEVANT_COLUMNS   -106

row does not contain relevant columns

Definition at line 247 of file sepa_zerohalf.c.

Referenced by getRelevantRows().

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

Referenced by preprocessConsiderMinSlack().

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

Referenced by preprocessConsiderMinSlack().

#define ZERO_COLUMN   -200

column has no nonzero entries

Definition at line 255 of file sepa_zerohalf.c.

Referenced by preprocessColumns().

#define IDENT_TO_ANOTHER_COLUMN   -201

column is identical to another column

Definition at line 256 of file sepa_zerohalf.c.

Referenced by preprocessIdenticalColums().

#define ZERO_LP_SOL   -202

column corresponds to a variable whose LP solution is zero

Definition at line 257 of file sepa_zerohalf.c.

Referenced by getRelevantColumns().

#define LP_SOL_EQUALS_EVEN_LB   -203

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

Definition at line 258 of file sepa_zerohalf.c.

Referenced by getRelevantColumns().

#define LP_SOL_EQUALS_ODD_LB   -204

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

Definition at line 259 of file sepa_zerohalf.c.

Referenced by decomposeProblem(), getRelevantColumns(), getRelevantRows(), and storeMod2Data().

#define LP_SOL_EQUALS_EVEN_UB   -205

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

Definition at line 260 of file sepa_zerohalf.c.

Referenced by getRelevantColumns().

#define LP_SOL_EQUALS_ODD_UB   -206

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

Definition at line 261 of file sepa_zerohalf.c.

Referenced by decomposeProblem(), getRelevantColumns(), getRelevantRows(), and storeMod2Data().

#define SINGLETON_COLUMN   -207

column has only one nonzero entry

Definition at line 262 of file sepa_zerohalf.c.

Referenced by preprocessColumns().

#define CONTINUOUS_VARIABLE   -208

column corresponds to a non-integer variable

Definition at line 263 of file sepa_zerohalf.c.

Referenced by getRelevantColumns().

#define SMALL_FRACSOL_HEUR   -209

column has been omitted (see preprocessColumnsWithSmallFracsol)

Definition at line 264 of file sepa_zerohalf.c.

Referenced by preprocessColumnsWithSmallFracsol().

#define ALL_MATRIX_ROWS_DELETED   -210

all rows (of the current subproblem) have been deleted

Definition at line 265 of file sepa_zerohalf.c.

Referenced by preprocessConsiderMinSlack().

#define BITARRAYBASETYPE   unsigned int

base type used for the bitarray data structures

Definition at line 276 of file sepa_zerohalf.c.

#define BITARRAYBITMASKTYPE   BITARRAYBASETYPE

Definition at line 277 of file sepa_zerohalf.c.

Referenced by createSubscip(), markColAsRemovedAndClearCol(), preprocessColumns(), preprocessConsiderMinSlack(), preprocessIdenticalColums(), preprocessModGaussElim(), and separateByGaussHeuristics().

#define BITARRAY   BITARRAYBASETYPE*

Definition at line 286 of file sepa_zerohalf.c.

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

#define BITMASK

(

pos

)

((unsigned int)(1 << (pos)))

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

Definition at line 289 of file sepa_zerohalf.c.

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

set the pos-th bit of var

Definition at line 292 of file sepa_zerohalf.c.

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

is the pos-th bit of var set?

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

Referenced by decomposeProblem(), and storeMod2Data().

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

Referenced by calcInnerProductOfRowAndFracsol(), calcObjWeight(), decomposeProblem(), getZerohalfWeightvectorFromSelectedRowsBitarray(), hasMatrixMax2EntriesPerRow(), preprocessColumns(), separateByAuxGraph(), and storeMod2Data().

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

clear bitarray

Definition at line 306 of file sepa_zerohalf.c.

Referenced by getBitarrayOfSelectedRows(), separateByAuxGraph(), separateByEnumerationHeuristics(), and storeMod2Data().

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

Referenced by decomposeProblem(), and storeMod2Data().

#define GETBITARRAYINDEX

(

pos

)

DIV((pos),Zerohalf_bitarraybasetypesize_nbits)

get the corresponding array element of a bitarray position

Definition at line 315 of file sepa_zerohalf.c.

Referenced by createSubscip(), markColAsRemovedAndClearCol(), preprocessColumns(), preprocessConsiderMinSlack(), preprocessIdenticalColums(), preprocessModGaussElim(), 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 318 of file sepa_zerohalf.c.

Referenced by createSubscip(), markColAsRemovedAndClearCol(), preprocessColumns(), preprocessConsiderMinSlack(), preprocessIdenticalColums(), preprocessModGaussElim(), 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 321 of file sepa_zerohalf.c.

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

barray2 = barray1 XOR barray2

Definition at line 331 of file sepa_zerohalf.c.

Referenced by getBitarrayOfSelectedRows(), preprocessModGaussElim(), 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 334 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 4872 of file sepa_zerohalf.c.

Referenced by createSubscip().

#define BRANCHPRIORITY__PREFER_BRANCHING   0

Definition at line 4873 of file sepa_zerohalf.c.

Referenced by createSubscip().

Typedef Documentation

typedef enum cutseparatedby CUTSEPARATEDBY

Definition at line 174 of file sepa_zerohalf.c.

typedef struct Zerohalf_SubLPData ZEROHALF_SUBLPDATA

Definition at line 439 of file sepa_zerohalf.c.

typedef struct Zerohalf_LPData ZEROHALF_LPDATA

Definition at line 479 of file sepa_zerohalf.c.

typedef struct Zerohalf_AuxIPData ZEROHALF_AUXIPDATA

Definition at line 525 of file sepa_zerohalf.c.

typedef struct Zerohalf_Mod2Data ZEROHALF_MOD2DATA

Definition at line 555 of file sepa_zerohalf.c.

typedef struct Zerohalf_CutData ZEROHALF_CUTDATA

Definition at line 585 of file sepa_zerohalf.c.

typedef struct Zerohalf_AuxGraph_Node ZEROHALF_AUXGRAPH_NODE

Definition at line 591 of file sepa_zerohalf.c.

typedef struct Zerohalf_AuxGraph ZEROHALF_AUXGRAPH

Definition at line 611 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 135 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 155 of file sepa_zerohalf.c.

enum cutseparatedby

statistics: "origin" of separated cut

Enumerator:

AUXIP
DECOMPOSITION
PPZEROONEROW
HEURISTICSENUM
HEURISTICSGAUSS
AUXGRAPH

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

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemory.

Referenced by decomposeProblem(), and getRelevantColumns().

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

References NULL, SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by decomposeProblem(), and ZerohalfLPDataFree().

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

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemory.

Referenced by SCIP_DECL_SEPAEXECLP().

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

References NULL, SCIP_OKAY, SCIPfreeMemory, SCIPfreeMemoryArray, and ZerohalfSubLPDataFree().

Referenced by SCIP_DECL_SEPAEXECLP().

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

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemory.

Referenced by SCIP_DECL_SEPAEXECLP().

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

References NULL, SCIP_OKAY, SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by SCIP_DECL_SEPAEXECLP().

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

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemory.

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

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

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

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

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

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

Referenced by SCIP_DECL_SEPAEXECLP().

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

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemory.

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

References NULL, SCIP_OKAY, SCIPfreeMemory, and 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 1074 of file sepa_zerohalf.c.

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemory.

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

References NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeMemory, 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 1483 of file sepa_zerohalf.c.

References SCIP_Real.

static SCIP_DECL_SORTINDCOMP ( compRealNonIncreasing  )

static

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

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

References BMSclearMemoryArray, CONTINUOUS_VARIABLE, IRRELEVANT, ISODD, LP_SOL_EQUALS_EVEN_LB, LP_SOL_EQUALS_EVEN_UB, LP_SOL_EQUALS_ODD_LB, LP_SOL_EQUALS_ODD_UB, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPallocMemoryArray, SCIPcolGetLb(), SCIPcolGetPrimsol(), SCIPcolGetUb(), SCIPcolGetVar(), SCIPgetVarSol(), SCIPisFeasEQ(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisLE(), SCIPisNegative(), SCIPisZero(), SCIPvarGetType(), ZERO_LP_SOL, and ZerohalfSubLPDataCreate().

Referenced by SCIP_DECL_SEPAEXECLP().

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 1696 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.

Referenced by getRelevantRows(), and storeMod2Data().

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 1803 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.

Referenced by getRelevantRows(), and storeMod2Data().

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

References BMSclearMemoryArray, FALSE, findClosestLb(), findClosestUb(), IRRELEVANT, ISEVEN, LP_SOL_EQUALS_ODD_LB, LP_SOL_EQUALS_ODD_UB, MAXDNOM, MAXSCALE, NO_RELEVANT_COLUMNS, NONEXISTENT_ROW, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPcalcIntegralScalar(), SCIPcolGetLPPos(), SCIPcolGetPrimsol(), SCIPcolGetVar(), SCIPepsilon(), SCIPfreeBufferArray, SCIPgetRowLPActivity(), SCIPgetRowMaxCoef(), SCIPgetRowMinCoef(), SCIPisFeasZero(), SCIPisGE(), SCIPisInfinity(), SCIPisIntegral(), SCIPisLE(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetIndex(), SCIProwGetLhs(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetSumNorm(), SCIProwGetVals(), SCIPvarGetCol(), SCIPvarGetType(), SLACK_GREATER_THAN_MAXSLACK, and TRUE.

Referenced by SCIP_DECL_SEPAEXECLP().

static SCIP_Bool hasMatrixMax2EntriesPerRow ( ZEROHALF_MOD2DATA *  mod2data )

static

Parameters

mod2data

considered mod 2 data

Definition at line 2384 of file sepa_zerohalf.c.

References BITARRAYBITISSET, FALSE, NULL, and TRUE.

Referenced by preprocess(), separateByAuxGraph(), and storeMod2Data().

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

References BITARRAY, BITARRAYBITISSET, BITARRAYBITSET, BITARRAYCLEAR, BMSclearMemoryArray, BMScopyMemoryArray, FALSE, findClosestLb(), findClosestUb(), GETREQUIREDBITARRAYSIZE, hasMatrixMax2EntriesPerRow(), IRRELEVANT, ISEVEN, ISODD, LP_SOL_EQUALS_ODD_LB, LP_SOL_EQUALS_ODD_UB, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPceil(), SCIPcolGetLb(), SCIPcolGetLPPos(), SCIPcolGetPrimsol(), SCIPcolGetUb(), SCIPcolGetVar(), SCIPfloor(), SCIPfreeBufferArray, SCIPfreeMemoryArray, SCIPisFeasZero(), SCIPisIntegral(), SCIPisLE(), SCIPisZero(), SCIProwGetCols(), SCIProwGetNLPNonz(), SCIProwGetVals(), SCIPvarGetCol(), SCIPvarGetType(), TRUE, USEVARBOUNDS, XOR, and ZERO_ROW.

Referenced by SCIP_DECL_SEPAEXECLP().

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

References NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_ERROR, SCIP_OKAY, SCIP_SEPARATED, SCIPaddCut(), SCIPaddPoolCut(), SCIPdebug, SCIPerrorMessage, SCIPisEfficacious(), SCIPisPositive(), SCIPprintRow(), and TRUE.

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

References NULL.

Referenced by preprocessColumns(), preprocessConsiderMinSlack(), 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 3037 of file sepa_zerohalf.c.

References BITARRAYBITMASKTYPE, GETBITARRAYINDEX, GETBITARRAYMASK, and NULL.

Referenced by preprocessColumns(), preprocessColumnsWithSmallFracsol(), preprocessConsiderMinSlack(), and preprocessIdenticalColums().

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 3072 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 3146 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(), SCIP_DECL_SEPAEXECLP(), 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 3311 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 3445 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(), preprocessModGaussElim(), 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 3582 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(), preprocessModGaussElim(), 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 3760 of file sepa_zerohalf.c.

References BITARRAYBITMASKTYPE, BITARRAYSXOR, FALSE, GETBITARRAYINDEX, GETBITARRAYMASK, NULL, preprocessColumns(), preprocessRows(), SCIP_CALL, SCIP_OKAY, SCIPisZero(), SCIPsortInd(), TRUE, and XOR.

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

References BITARRAY, BITARRAYBITISSET, BITARRAYBITSET, BMSclearMemoryArray, FALSE, GETREQUIREDBITARRAYSIZE, IRRELEVANT, ISEVEN, ISODD, LP_SOL_EQUALS_ODD_LB, LP_SOL_EQUALS_ODD_UB, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPcolGetLb(), SCIPcolGetLPPos(), SCIPcolGetNNonz(), SCIPcolGetRows(), SCIPcolGetUb(), SCIPcolGetVals(), SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeMemoryArray, SCIPisInfinity(), SCIPisLE(), SCIProwGetCols(), SCIProwGetLPPos(), SCIProwGetNLPNonz(), SCIProwGetVals(), XOR, ZerohalfSubLPDataCreate(), and ZerohalfSubLPDataFree().

Referenced by SCIP_DECL_SEPAEXECLP().

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

References markColAsRemovedAndClearCol(), NULL, SCIP_OKAY, SCIP_Real, SCIPisGT(), SCIPisPositive(), SCIPsortInd(), and SMALL_FRACSOL_HEUR.

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

References ALL_MATRIX_ROWS_DELETED, BITARRAYBITMASKTYPE, BMSclearMemoryArray, GETBITARRAYINDEX, GETBITARRAYMASK, LARGE_COL_EXISTS, markColAsRemovedAndClearCol(), markRowAsRemoved(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisFeasZero(), SCIPisGT(), SCIPisLT(), SCIPsortInd(), SLACK_GREATER_THAN_MSL_MINUS_SODD, and TRUE.

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

References BITARRAYBITMASKTYPE, BMSclearMemoryArray, GETBITARRAYINDEX, GETBITARRAYMASK, IDENT_TO_ANOTHER_COLUMN, markColAsRemovedAndClearCol(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and TRUE.

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 4607 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.

Referenced by SCIP_DECL_SEPAEXECLP().

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

References BITARRAYBITISSET, NULL, and SCIP_Real.

Referenced by createSubscip().

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

References BITARRAYBITMASKTYPE, BMSclearMemoryArray, BRANCHPRIORITY__AVOID_BRANCHING, BRANCHPRIORITY__PREFER_BRANCHING, calcObjWeight(), FALSE, GETBITARRAYINDEX, GETBITARRAYMASK, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPaddCons(), SCIPaddVar(), SCIPallocBufferArray, SCIPallocMemoryArray, SCIPchgVarBranchPriority(), SCIPcopyPlugins(), SCIPcreate(), SCIPcreateConsLinear(), SCIPcreateProb(), SCIPcreateVar(), SCIPdebug, SCIPdebugMessage, SCIPfeastol(), SCIPfreeBufferArray, SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPinfinity(), SCIPisFeasNegative(), SCIPisInfinity(), SCIPprintOrigProblem(), SCIPreadParams(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetObjlimit(), SCIPsetRealParam(), SCIPsnprintf(), and TRUE.

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

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_STAGE_SOLVED, SCIP_STAGE_SOLVING, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPdebug, SCIPfreeBufferArray, SCIPgetNSols(), SCIPgetSolOrigObj(), SCIPgetSols(), SCIPgetSolVal(), SCIPgetStage(), SCIPisGT(), SCIPisLE(), SCIPprintStatistics(), SCIPsolve(), SCIPwarningMessage(), and TRUE.

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

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

Referenced by SCIP_DECL_SEPAEXECLP().

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

References BITARRAYCLEAR, BITARRAYSXOR, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, SCIPgetSolVal(), and SCIPisZero().

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

References BITARRAYBITISSET, NULL, SCIP_OKAY, and SCIPisGT().

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 5639 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 5924 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 6040 of file sepa_zerohalf.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGT(), and SCIPisLT().

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 6138 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 6398 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 6535 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.

Referenced by SCIP_DECL_SEPAEXECLP().

static SCIP_DECL_SEPACOPY ( sepaCopyZerohalf  )

static

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

Definition at line 6815 of file sepa_zerohalf.c.

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

static SCIP_DECL_SEPAFREE ( sepaFreeZerohalf  )

static

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

Definition at line 6829 of file sepa_zerohalf.c.

References NULL, SCIP_OKAY, SCIPfreeMemory, SCIPfreeMemoryArray, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), and SEPA_NAME.

static SCIP_DECL_SEPAEXECLP ( sepaExeclpZerohalf  )

static

LP solution separation method of separator

Definition at line 6893 of file sepa_zerohalf.c.

References addZerohalfCutToLP(), BMSclearMemoryArray, createZerohalfCutFromZerohalfWeightvector(), decomposeProblem(), DECOMPOSITION, DEFINES_VIOLATED_ZEROHALF_CUT, FALSE, getRelevantColumns(), getRelevantRows(), getZerohalfWeightvectorForSingleRow(), MIN, MINORTHO, NNONZOFFSET, NULL, ORTHOFUNC, preprocess(), process(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_REAL_MIN, SCIPaddCut(), SCIPaddDelayedPoolCut(), SCIPaddPoolCut(), SCIPallocBufferArray, SCIPallocMemoryArray, SCIPdebugMessage, SCIPfloor(), SCIPfreeBufferArray, SCIPfreeMemoryArray, SCIPgetCharParam(), SCIPgetDepth(), SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPgetLPSolstat(), SCIPgetNLPBranchCands(), SCIPgetVarsData(), SCIPisLT(), SCIPisStopped(), SCIProwGetIndex(), SCIProwGetNLPNonz(), SCIProwGetOrthogonality(), SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaGetNCalls(), SCIPsepaGetNCallsAtNode(), SCIPsortDownRealInt(), SCIPsortRealInt(), SEPA_NAME, storeMod2Data(), TRUE, ZerohalfCutDataCreate(), ZerohalfCutDataFree(), ZerohalfLPDataCreate(), ZerohalfLPDataFree(), ZerohalfMod2DataCreate(), and ZerohalfMod2DataFree().

SCIP_RETCODE SCIPincludeSepaZerohalf

(

SCIP *

scip

)

creates the zerohalf separator and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 7441 of file sepa_zerohalf.c.

References DEFAULT_DECOMPOSEPROBLEM, DEFAULT_DELAYEDCUTS, DEFAULT_DYNAMICCUTS, DEFAULT_FORCECUTSTOLP, DEFAULT_FORCECUTSTOSEPASTORE, DEFAULT_IGNOREPREVIOUSZHCUTS, DEFAULT_MAXCUTS, DEFAULT_MAXCUTSROOT, DEFAULT_MAXDEPTH, DEFAULT_MAXNCALLS, DEFAULT_MAXROUNDS, DEFAULT_MAXROUNDSROOT, DEFAULT_MAXSEPACUTS, DEFAULT_MAXSEPACUTSROOT, DEFAULT_MAXTESTDELTA, DEFAULT_MINVIOLATION, DEFAULT_ONLYORIGROWS, DEFAULT_PPDELTA, DEFAULT_PPMETHODS, DEFAULT_RELAXCONTVARS, DEFAULT_SCALEFRACCOEFFS, DEFAULT_SEPAMETHODS, DEFAULT_SUBSCIPOBJECTIVE, DEFAULT_SUBSCIPOBJPEN, DEFAULT_SUBSCIPSETTINGS, DEFAULT_SUBSCIPSOLLIMIT, DEFAULT_SUBSCIPUSEALLSOLS, DEFAULT_TRYNEGSCALING, DEFAULT_USEZHCUTPOOL, FALSE, NULL, SCIP_CALL, SCIP_LONGINT_MAX, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddCharParam(), SCIPaddIntParam(), SCIPaddLongintParam(), SCIPaddRealParam(), SCIPaddStringParam(), SCIPallocMemory, SCIPincludeSepaBasic(), SCIPmemccpy(), SCIPsetSepaCopy(), SCIPsetSepaFree(), SEPA_DELAY, SEPA_DESC, SEPA_FREQ, SEPA_MAXBOUNDDIST, SEPA_NAME, SEPA_PRIORITY, SEPA_USESSUBSCIP, and TRUE.

Referenced by SCIP_DECL_SEPACOPY(), and SCIPincludeDefaultPlugins().

Variable Documentation

const unsigned int Zerohalf_bitarraybasetypesize = sizeof(BITARRAYBASETYPE)

static

size of BITARRAYBASETYPE

Definition at line 280 of file sepa_zerohalf.c.

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

static

number of bits per BITARRAYBASETYPE

Definition at line 283 of file sepa_zerohalf.c.