{0,1/2}-cuts separator
{0,1/2}-Chvátal-Gomory cuts separator. It solves the following separation problem: Consider an integer program
\[ \min \{ c^T x : Ax \leq b, x \geq 0, x \mbox{ integer} \} \]
and a fractional solution \(x^*\) of its LP relaxation. Find a weightvector \(u\) whose entries \(u_i\) are either 0 or \(\frac{1}{2}\) such that the following inequality is valid for all integral solutions and violated by \(x^*\):
\[ \lfloor(u^T A) x \rfloor \leq \lfloor u^T b\rfloor \]
or (if exact methods are used) give a proof that no such inequality exists.
References:
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.
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 *graph, 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 |
#define SEPA_NAME "zerohalf" |
< print statistics
Definition at line 55 of file sepa_zerohalf.c.
Referenced by process(), and SCIP_DECL_SEPACOPY().
#define SEPA_DESC "{0,1/2}-cuts separator" |
Definition at line 56 of file sepa_zerohalf.c.
#define SEPA_PRIORITY -6000 |
Definition at line 57 of file sepa_zerohalf.c.
#define SEPA_FREQ -1 |
Definition at line 58 of file sepa_zerohalf.c.
#define SEPA_MAXBOUNDDIST 0.0 |
Definition at line 59 of file sepa_zerohalf.c.
#define SEPA_USESSUBSCIP TRUE |
Definition at line 60 of file sepa_zerohalf.c.
#define SEPA_DELAY FALSE |
Definition at line 61 of file sepa_zerohalf.c.
#define DEFAULT_MAXROUNDS 5 |
maximal number of zerohalf separation rounds per node (-1: unlimited)
Definition at line 63 of file sepa_zerohalf.c.
#define DEFAULT_MAXROUNDSROOT 10 |
maximal number of zerohalf separation rounds in the root node (-1: unlimited)
Definition at line 64 of file sepa_zerohalf.c.
#define DEFAULT_MAXSEPACUTS 50 |
maximal number of {0,1/2}-cuts separated per separation round
Definition at line 65 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 66 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 67 of file sepa_zerohalf.c.
#define DEFAULT_DECOMPOSEPROBLEM FALSE |
should problem be decomposed into subproblems (if possible)?
Definition at line 68 of file sepa_zerohalf.c.
#define DEFAULT_MAXDEPTH -1 |
separating cuts only if depth <= maxdepth (-1: unlimited)
Definition at line 69 of file sepa_zerohalf.c.
#define DEFAULT_MINVIOLATION 0.30 |
minimal violation of a {0,1/2}-cut to be separated
Definition at line 70 of file sepa_zerohalf.c.
#define DEFAULT_FORCECUTSTOLP FALSE |
should the cuts be forced to enter the LP? (bypassing SCIPefficacy criteria)
Definition at line 71 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 72 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 75 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 78 of file sepa_zerohalf.c.
#define DEFAULT_SUBSCIPOBJECTIVE 'v' |
auxiliary IP objective function type
Definition at line 81 of file sepa_zerohalf.c.
#define DEFAULT_RELAXCONTVARS FALSE |
should continuous variables be relaxed by adding variable bounds?
Definition at line 82 of file sepa_zerohalf.c.
#define DEFAULT_SCALEFRACCOEFFS TRUE |
should rows be scaled to make fractional coefficients integer?
Definition at line 83 of file sepa_zerohalf.c.
#define DEFAULT_SUBSCIPSETTINGS "-" |
optional settings file of the auxiliary IP (-: none)
Definition at line 84 of file sepa_zerohalf.c.
#define DEFAULT_SUBSCIPSOLLIMIT -1 |
limits/solutions setting of the auxiliary IP
Definition at line 85 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 86 of file sepa_zerohalf.c.
#define DEFAULT_PPDELTA 0.500 |
value of delta parameter used in preprocessing method 'd'
Definition at line 89 of file sepa_zerohalf.c.
#define DEFAULT_SUBSCIPOBJPEN 0.001 |
penalty factor used with objective function 'p' of auxiliary IP
Definition at line 90 of file sepa_zerohalf.c.
#define DEFAULT_PPMETHODS "CXGXIM" |
preprocessing methods and ordering
Definition at line 92 of file sepa_zerohalf.c.
#define DEFAULT_SEPAMETHODS "2g" |
preprocessing methods and ordering
Definition at line 93 of file sepa_zerohalf.c.
#define DEFAULT_MAXNCALLS -1LL |
maximal number of calls (-1: unlimited)
Definition at line 94 of file sepa_zerohalf.c.
#define DEFAULT_IGNOREPREVIOUSZHCUTS FALSE |
should zerohalf cuts found in previous callbacks be ignored?
Definition at line 95 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 96 of file sepa_zerohalf.c.
#define DEFAULT_USEZHCUTPOOL TRUE |
should zerohalf cuts be filtered using a cutpool
Definition at line 97 of file sepa_zerohalf.c.
#define DEFAULT_DELAYEDCUTS TRUE |
should cuts be added to the delayed cut pool?
Definition at line 98 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 99 of file sepa_zerohalf.c.
#define DEFAULT_TRYNEGSCALING TRUE |
should negative values also be tested in scaling for cmir?
Definition at line 100 of file sepa_zerohalf.c.
#define ORTHOFUNC 'e' |
Definition at line 103 of file sepa_zerohalf.c.
#define MINORTHO 0.5 |
Definition at line 104 of file sepa_zerohalf.c.
#define NNONZOFFSET 500 |
Definition at line 107 of file sepa_zerohalf.c.
#define BOUNDSWITCH 0.50 |
Definition at line 108 of file sepa_zerohalf.c.
Referenced by createZerohalfCutFromZerohalfWeightvector().
#define USEVBDS TRUE |
Definition at line 109 of file sepa_zerohalf.c.
Referenced by createZerohalfCutFromZerohalfWeightvector().
#define ALLOWLOCAL TRUE |
Definition at line 110 of file sepa_zerohalf.c.
Referenced by createZerohalfCutFromZerohalfWeightvector().
#define FIXINTEGRALRHS TRUE |
Definition at line 111 of file sepa_zerohalf.c.
Referenced by createZerohalfCutFromZerohalfWeightvector().
#define BOUNDSFORTRANS NULL |
Definition at line 112 of file sepa_zerohalf.c.
Referenced by createZerohalfCutFromZerohalfWeightvector().
#define BOUNDTYPESFORTRANS NULL |
Definition at line 113 of file sepa_zerohalf.c.
Referenced by createZerohalfCutFromZerohalfWeightvector().
#define MAXWEIGHTRANGE 10000.00 |
Definition at line 114 of file sepa_zerohalf.c.
Referenced by createZerohalfCutFromZerohalfWeightvector().
#define MINFRAC 0.05 |
Definition at line 115 of file sepa_zerohalf.c.
Referenced by createZerohalfCutFromZerohalfWeightvector().
#define MAXFRAC 1.00 |
Definition at line 116 of file sepa_zerohalf.c.
Referenced by createZerohalfCutFromZerohalfWeightvector().
#define MAXDNOM 1000 |
Definition at line 119 of file sepa_zerohalf.c.
#define MAXSCALE 1000.0 |
Definition at line 120 of file sepa_zerohalf.c.
#define USEVARBOUNDS TRUE |
Definition at line 123 of file sepa_zerohalf.c.
Referenced by findClosestLb(), and findClosestUb().
is value even?
Definition at line 178 of file sepa_zerohalf.c.
#define ISODD | ( | scip, | |
value | |||
) | (!(ISEVEN((scip), (value)))) |
is value odd?
Definition at line 179 of file sepa_zerohalf.c.
#define XOR | ( | bool1, | |
bool2 | |||
) | ((bool1) ^ (bool2)) |
Definition at line 180 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 181 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 182 of file sepa_zerohalf.c.
#define IRRELEVANT -1 |
row or column is irrelevant
Definition at line 234 of file sepa_zerohalf.c.
Referenced by ZerohalfAuxGraphFree().
#define ZERO_ROW -100 |
row has no nonzero entries
Definition at line 237 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 238 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 239 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 240 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 244 of file sepa_zerohalf.c.
Referenced by ZerohalfAuxGraphFree().
#define NO_RELEVANT_COLUMNS -106 |
row does not contain relevant columns
Definition at line 245 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 246 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 249 of file sepa_zerohalf.c.
Referenced by ZerohalfAuxGraphFree().
#define ZERO_COLUMN -200 |
column has no nonzero entries
Definition at line 256 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 257 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 258 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 259 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 260 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 261 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 262 of file sepa_zerohalf.c.
Referenced by ZerohalfAuxGraphFree().
#define SINGLETON_COLUMN -207 |
column has only one nonzero entry
Definition at line 263 of file sepa_zerohalf.c.
Referenced by preprocessColumns(), and ZerohalfAuxGraphFree().
#define CONTINUOUS_VARIABLE -208 |
column corresponds to a non-integer variable
Definition at line 264 of file sepa_zerohalf.c.
Referenced by ZerohalfAuxGraphFree().
#define SMALL_FRACSOL_HEUR -209 |
column has been omitted (see preprocessColumnsWithSmallFracsol)
Definition at line 265 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 266 of file sepa_zerohalf.c.
Referenced by ZerohalfAuxGraphFree().
#define BITARRAYBASETYPE unsigned int |
base type used for the bitarray data structures
Definition at line 277 of file sepa_zerohalf.c.
#define BITARRAYBITMASKTYPE BITARRAYBASETYPE |
Definition at line 278 of file sepa_zerohalf.c.
Referenced by preprocessColumns(), and separateByGaussHeuristics().
#define BITARRAY BITARRAYBASETYPE* |
Definition at line 287 of file sepa_zerohalf.c.
Referenced by preprocess(), preprocessRows(), preprocessTrivialZerohalfCuts(), separateByAuxGraph(), separateByEnumerationHeuristics(), and separateBySolvingAuxIP().
#define BITMASK | ( | pos | ) | ((unsigned int)(1u << (pos))) |
get the bit mask where the pos-th bit is set
Definition at line 290 of file sepa_zerohalf.c.
#define BITSET | ( | var, | |
pos | |||
) | (var) |= BITMASK(pos) |
set the pos-th bit of var
Definition at line 293 of file sepa_zerohalf.c.
#define BITISSET | ( | var, | |
pos | |||
) | (var & BITMASK(pos)) |
is the pos-th bit of var set?
Definition at line 296 of file sepa_zerohalf.c.
#define BITARRAYBITSET | ( | barray, | |
pos | |||
) |
set the pos-th bit of bitarray barray
Definition at line 299 of file sepa_zerohalf.c.
#define BITARRAYBITISSET | ( | barray, | |
pos | |||
) |
is the pos-th bit of bitarray barray set?
Definition at line 303 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 307 of file sepa_zerohalf.c.
Referenced by separateByAuxGraph(), and separateByEnumerationHeuristics().
#define GETREQUIREDBITARRAYSIZE | ( | nvalstostore | ) |
calculates the number of array elements (w.r.t. the bitarray base type) required to create the bitarray
Definition at line 310 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 316 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 319 of file sepa_zerohalf.c.
Referenced by preprocessColumns(), and separateByGaussHeuristics().
#define BITARRAYSFOREACH | ( | barray1, | |
barray2, | |||
size, | |||
op | |||
) |
apply operation op for all array elements of bitarray barray1 and barray2
Definition at line 322 of file sepa_zerohalf.c.
#define BITARRAYSXOR | ( | barray1, | |
barray2, | |||
size | |||
) | BITARRAYSFOREACH(barray1,barray2,size,^=) |
barray2 = barray1 XOR barray2
Definition at line 332 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 335 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 4808 of file sepa_zerohalf.c.
#define BRANCHPRIORITY__PREFER_BRANCHING 0 |
Definition at line 4809 of file sepa_zerohalf.c.
typedef enum cutseparatedby CUTSEPARATEDBY |
Definition at line 170 of file sepa_zerohalf.c.
typedef struct Zerohalf_SubLPData ZEROHALF_SUBLPDATA |
Definition at line 442 of file sepa_zerohalf.c.
typedef struct Zerohalf_LPData ZEROHALF_LPDATA |
Definition at line 482 of file sepa_zerohalf.c.
typedef struct Zerohalf_AuxIPData ZEROHALF_AUXIPDATA |
Definition at line 528 of file sepa_zerohalf.c.
typedef struct Zerohalf_Mod2Data ZEROHALF_MOD2DATA |
Definition at line 560 of file sepa_zerohalf.c.
typedef struct Zerohalf_CutData ZEROHALF_CUTDATA |
Definition at line 590 of file sepa_zerohalf.c.
typedef struct Zerohalf_AuxGraph_Node ZEROHALF_AUXGRAPH_NODE |
Definition at line 596 of file sepa_zerohalf.c.
typedef struct Zerohalf_AuxGraph ZEROHALF_AUXGRAPH |
Definition at line 616 of file sepa_zerohalf.c.
enum preprocessingmethods |
preprocessing methods, usable within the ppmethods parameter
Definition at line 131 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 151 of file sepa_zerohalf.c.
enum cutseparatedby |
statistics: "origin" of separated cut
Enumerator | |
---|---|
AUXIP | |
DECOMPOSITION | |
PPZEROONEROW | |
HEURISTICSENUM | |
HEURISTICSGAUSS | |
AUXGRAPH |
Definition at line 166 of file sepa_zerohalf.c.
|
static |
creates and initializes sub LP data structures
scip | SCIP data structure |
subproblem | pointer to store pointer to created data structure |
Definition at line 626 of file sepa_zerohalf.c.
References NULL.
|
static |
frees sub LP data structures
scip | SCIP data structure |
subproblem | pointer to pointer of data structure |
Definition at line 653 of file sepa_zerohalf.c.
|
static |
creates and initializes LP data structures
scip | SCIP data structure |
lpdata | pointer to store pointer to created data structure |
Definition at line 676 of file sepa_zerohalf.c.
References NULL.
|
static |
frees LP data structures
scip | SCIP data structure |
lpdata | pointer to pointer of data structure |
Definition at line 711 of file sepa_zerohalf.c.
|
static |
creates and initializes mod 2 data structures
scip | SCIP data structure |
mod2data | pointer to store pointer to created data structure |
Definition at line 753 of file sepa_zerohalf.c.
References NULL.
|
static |
frees data structures
scip | SCIP data structure |
mod2data | pointer to pointer of data structure |
Definition at line 787 of file sepa_zerohalf.c.
|
static |
creates and initializes auxiliary IP data structures
scip | SCIP data structure |
auxipdata | pointer to store pointer to created data structure |
Definition at line 837 of file sepa_zerohalf.c.
References NULL.
Referenced by separateBySolvingAuxIP().
|
static |
frees auxiliary IP data structures
scip | SCIP data structure |
auxipdata | pointer to pointer of data structure |
Definition at line 864 of file sepa_zerohalf.c.
References SCIP_CALL, SCIP_OKAY, SCIPfree(), SCIPfreeBlockMemory, SCIPfreeBlockMemoryArrayNull, and ZerohalfCutDataCreate().
Referenced by separateBySolvingAuxIP().
|
static |
creates and initializes cut data structures
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 891 of file sepa_zerohalf.c.
References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, TRUE, and ZerohalfCutDataFree().
Referenced by preprocessTrivialZerohalfCuts(), separateByAuxGraph(), separateByEnumerationHeuristics(), separateBySolvingAuxIP(), and ZerohalfAuxIPDataFree().
|
static |
frees cut data structures
scip | SCIP data structure |
cutdata | pointer to pointer of data structure |
Definition at line 936 of file sepa_zerohalf.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPfreeBlockMemory, SCIPreleaseRow(), and ZerohalfAuxGraphNodeCreate().
Referenced by ZerohalfCutDataCreate().
|
static |
creates and initializes auxiliary graph node data structures
scip | SCIP data structure |
node | pointer to store pointer to created data structure |
Definition at line 957 of file sepa_zerohalf.c.
References NULL.
Referenced by separateByAuxGraph(), and ZerohalfCutDataFree().
|
static |
frees auxiliary graph node data structures
scip | SCIP data structure |
graph | graph |
node | pointer to pointer of data structure |
Definition at line 981 of file sepa_zerohalf.c.
Referenced by ZerohalfAuxGraphFree().
|
static |
creates and initializes auxiliary graph data structures
scip | SCIP data structure |
auxgraph | pointer to store pointer to created data structure |
Definition at line 1007 of file sepa_zerohalf.c.
References NULL.
Referenced by separateByAuxGraph().
|
static |
frees auxiliary graph data structures
scip | SCIP data structure |
auxgraph | pointer to pointer of data structure |
Definition at line 1028 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(), SCIPdebugMsg, SCIPdebugMsgPrint, SCIPerrorMessage, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, 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 |
comparator function for sorting an index array non-decreasingly according to a real array
Definition at line 1426 of file sepa_zerohalf.c.
References SCIP_Real.
Referenced by ZerohalfAuxGraphFree().
|
static |
comparator function for sorting an index array non-increasingly according to a real array
Definition at line 1443 of file sepa_zerohalf.c.
References SCIP_Real.
|
static |
searches for relevant columns, i.e., columns that cannot be deleted because of basic preprocessing methods
scip | SCIP data structure |
lpdata | data of current LP relaxation |
Definition at line 1465 of file sepa_zerohalf.c.
|
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
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 1640 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 |
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
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 1747 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 |
searches for relevant rows, i.e., rows containing relevant columns that cannot be deleted because of basic preprocessing methods
scip | SCIP data structure |
sepadata | separator data |
lpdata | data of current LP relaxation |
Definition at line 1851 of file sepa_zerohalf.c.
Referenced by findClosestUb().
|
static |
mod2data | considered mod 2 data |
Definition at line 2333 of file sepa_zerohalf.c.
References BITARRAYBITISSET, FALSE, NULL, SCIP_Bool, storeMod2Data(), and TRUE.
Referenced by preprocess(), and separateByAuxGraph().
|
static |
stores relevant data into bit arrays (mod 2 data structure)
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 2409 of file sepa_zerohalf.c.
Referenced by hasMatrixMax2EntriesPerRow().
|
static |
stores nonzero elements of dense coefficient vector as sparse vector, and calculates activity and norm
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 2785 of file sepa_zerohalf.c.
References addZerohalfCutToLP(), MAX, NULL, REALABS, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIPerrorMessage, and SCIPisZero().
Referenced by createZerohalfCutFromZerohalfWeightvector().
|
static |
adds a separated zerohalf cut to SCIP if it was successfully created and is efficacious
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 2896 of file sepa_zerohalf.c.
Referenced by preprocessTrivialZerohalfCuts(), separateByAuxGraph(), separateByEnumerationHeuristics(), separateBySolvingAuxIP(), and storeCutInArrays().
|
static |
marks a row as "removed" and stores why it has been removed using a flag
mod2data | considered mod 2 data |
r | mod2data->rows index of row that shall be removed |
flag | flag (cause of removal) |
Definition at line 2962 of file sepa_zerohalf.c.
Referenced by preprocessColumns(), and preprocessRows().
|
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
mod2data | considered mod 2 data |
c | mod2data->relatedsubproblem->rcols index of column that shall be removed |
flag | flag (cause of removal) |
Definition at line 2981 of file sepa_zerohalf.c.
Referenced by preprocessColumns().
|
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
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 3016 of file sepa_zerohalf.c.
References BITARRAYBITISSET, BMSclearMemoryArray, createZerohalfCutFromZerohalfWeightvector(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPdebugMsg, SCIPfreeBlockMemoryArray, SCIProwGetName(), and SCIProwGetNLPNonz().
Referenced by preprocessTrivialZerohalfCuts(), separateByAuxGraph(), separateByEnumerationHeuristics(), and separateBySolvingAuxIP().
|
static |
creates a zerohalf cut from a given weightvector
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 3087 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(), SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPcalcMIR(), SCIPcreateEmptyRowSepa(), SCIPcutGenerationHeuristicCmir(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNLPs(), SCIPgetSolVals(), SCIPinfinity(), SCIPisEfficacious(), SCIPisFeasGT(), SCIPisPositive(), SCIProwChgRank(), SCIPsnprintf(), SCIPvarGetProbindex(), storeCutInArrays(), TRUE, and USEVBDS.
Referenced by getZerohalfWeightvectorFromSelectedRowsBitarray(), preprocessTrivialZerohalfCuts(), separateByAuxGraph(), separateByEnumerationHeuristics(), and separateBySolvingAuxIP().
|
static |
searches for trivial zerohalf cuts, given as (0,..0) row with rhs=1 and slack <= maxslack
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 3252 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, SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPisLE(), TRUE, and ZerohalfCutDataCreate().
Referenced by createZerohalfCutFromZerohalfWeightvector(), preprocess(), and separateByGaussHeuristics().
|
static |
applies some row reductions
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 3381 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 |
applies some column reductions
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 3518 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 |
applies modified Gaussian Elimination reduction
scip | SCIP data structure |
sepadata | separator data |
lpdata | data of current LP relaxation |
mod2data | considered (preprocessed) subproblem mod 2 |
Definition at line 3695 of file sepa_zerohalf.c.
Referenced by preprocess(), and preprocessColumns().
|
static |
decomposes the problem into subproblems which can be considered separately
scip | SCIP data structure |
sepadata | separator data |
lpdata | data of current LP relaxation |
Definition at line 3831 of file sepa_zerohalf.c.
|
static |
removes the largest number of columns such that the sum of the corresponding variables is at most delta
scip | SCIP data structure |
sepadata | separator data |
mod2data | considered (preprocessed) subproblem mod 2 |
delta | delta value |
Definition at line 4221 of file sepa_zerohalf.c.
Referenced by preprocess().
|
static |
removes some rows that cannot be combined because the resulting slack would be larger than maxslack
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 4282 of file sepa_zerohalf.c.
Referenced by preprocess().
|
static |
aggregates identical columns into one column whose (artificial) LP solution is the sum of the aggregated columns
scip | SCIP data structure |
mod2data | considered (preprocessed) subproblem mod 2 |
Definition at line 4464 of file sepa_zerohalf.c.
Referenced by preprocess().
|
static |
preprocess subproblem
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 4543 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, SCIPallocBlockMemoryArray, SCIPerrorMessage, and TRUE.
returns the objective weights for the weighted feasibility AuxIP
rowaggregation | row aggregation bitarray |
nrrows | number of relevant rows |
Definition at line 4778 of file sepa_zerohalf.c.
Referenced by preprocess().
|
static |
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 4811 of file sepa_zerohalf.c.
Referenced by separateBySolvingAuxIP().
|
static |
solves the auxiliary IP given as subscip
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 5161 of file sepa_zerohalf.c.
Referenced by separateBySolvingAuxIP().
|
static |
determines the weightvector for a single row
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 5294 of file sepa_zerohalf.c.
|
static |
gets the subset of rows that should be combined to a violated zerohalf cut
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 5337 of file sepa_zerohalf.c.
Referenced by separateBySolvingAuxIP().
|
static |
separates violated zerohalf cuts by solving an auxiliary IP. (exact method; exponential time)
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 5382 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, SCIPdebugMsg, SCIPfreeBlockMemoryArray, SCIPprintBestSol(), SCIPprintOrigProblem(), solveSubscip(), TRUE, ZerohalfAuxIPDataCreate(), ZerohalfAuxIPDataFree(), and ZerohalfCutDataCreate().
Referenced by process().
|
static |
calculates the inner product of mod2data->row and the LP solution
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 5527 of file sepa_zerohalf.c.
Referenced by separateByEnumerationHeuristics(), and separateBySolvingAuxIP().
|
static |
separate violated zerohalf cuts by enumerating possible row combinations. (heuristic; polynomial time)
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 5567 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, SCIPdebugMsg, SCIPerrorMessage, SCIPfreeBlockMemoryArray, SCIPfreeBufferArrayNull, SCIPisGT(), SCIPisLE(), SCIPsortInd(), and ZerohalfCutDataCreate().
Referenced by process(), separateByAuxGraph(), and separateByGaussHeuristics().
|
static |
adds an edge (and its "copy" w.r.t. the node copies) to the auxiliary graph
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 5841 of file sepa_zerohalf.c.
References dijkstra(), nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPisLT(), and SCIPisNegative().
Referenced by separateByAuxGraph(), and separateByEnumerationHeuristics().
|
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
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 5957 of file sepa_zerohalf.c.
Referenced by addEdgeToAuxGraph(), and separateByAuxGraph().
|
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)
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 6054 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, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPisLE(), separateByEnumerationHeuristics(), separateByGaussHeuristics(), TRUE, ZerohalfAuxGraphCreate(), ZerohalfAuxGraphFree(), ZerohalfAuxGraphNodeCreate(), and ZerohalfCutDataCreate().
Referenced by process().
|
static |
separates violated zerohalf cuts using an extended Gaussian elimination. (heuristic; polynomial time)
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 6314 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 |
processes subproblem (i.e. runs separation algorithms)
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 6451 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, SCIPallocBlockMemoryArray, SCIPerrorMessage, SCIPincludeSepaZerohalf(), SCIPisEfficacious(), SCIPsepaGetName(), SEPA_NAME, separateByAuxGraph(), separateByEnumerationHeuristics(), separateByGaussHeuristics(), separateBySolvingAuxIP(), SOLVEAUXSCIP, SOLVEAUXSCIPEXACT, STOPIFCUTWASFOUND, and TRUE.
Referenced by separateByGaussHeuristics().
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 6731 of file sepa_zerohalf.c.
References NULL, SCIPsepaGetData(), SCIPsepaGetName(), and SEPA_NAME.
Referenced by process().
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 6745 of file sepa_zerohalf.c.
References NULL, SCIP_DECL_SEPAEXECLP(), SCIP_OKAY, SCIP_Real, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, and SCIPsepaSetData().
|
static |
LP solution separation method of separator
Definition at line 6800 of file sepa_zerohalf.c.
Referenced by SCIP_DECL_SEPAFREE().
|
static |
size of BITARRAYBASETYPE
Definition at line 281 of file sepa_zerohalf.c.
|
static |
number of bits per BITARRAYBASETYPE
Definition at line 284 of file sepa_zerohalf.c.