Scippy

SCIP

Solving Constraint Integer Programs

sepa_zerohalf.c File Reference

Detailed Description

{0,1/2}-cuts separator

Author
Manuel Kutschka
Kati Wolter

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

Given an integer program

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

and a fractional solution x* of its LP relaxation.

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

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

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

References:

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

Definition in file sepa_zerohalf.c.

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

Go to the source code of this file.

Macros

#define SEPA_NAME   "zerohalf"
 
#define SEPA_DESC   "{0,1/2}-cuts separator"
 
#define SEPA_PRIORITY   -6000
 
#define SEPA_FREQ   -1
 
#define SEPA_MAXBOUNDDIST   0.0
 
#define SEPA_USESSUBSCIP   TRUE
 
#define SEPA_DELAY   FALSE
 
#define DEFAULT_MAXROUNDS   5
 
#define DEFAULT_MAXROUNDSROOT   10
 
#define DEFAULT_MAXSEPACUTS   50
 
#define DEFAULT_MAXSEPACUTSROOT   500
 
#define DEFAULT_DYNAMICCUTS   TRUE
 
#define DEFAULT_DECOMPOSEPROBLEM   FALSE
 
#define DEFAULT_MAXDEPTH   -1
 
#define DEFAULT_MINVIOLATION   0.30
 
#define DEFAULT_FORCECUTSTOLP   FALSE
 
#define DEFAULT_FORCECUTSTOSEPASTORE   FALSE
 
#define DEFAULT_MAXCUTS   100
 
#define DEFAULT_MAXCUTSROOT   1000
 
#define DEFAULT_SUBSCIPOBJECTIVE   'v'
 
#define DEFAULT_RELAXCONTVARS   FALSE
 
#define DEFAULT_SCALEFRACCOEFFS   TRUE
 
#define DEFAULT_SUBSCIPSETTINGS   "-"
 
#define DEFAULT_SUBSCIPSOLLIMIT   -1
 
#define DEFAULT_SUBSCIPUSEALLSOLS   TRUE
 
#define DEFAULT_PPDELTA   0.500
 
#define DEFAULT_SUBSCIPOBJPEN   0.001
 
#define DEFAULT_PPMETHODS   "CXGXIM"
 
#define DEFAULT_SEPAMETHODS   "2g"
 
#define DEFAULT_MAXNCALLS   -1LL
 
#define DEFAULT_IGNOREPREVIOUSZHCUTS   FALSE
 
#define DEFAULT_ONLYORIGROWS   FALSE
 
#define DEFAULT_USEZHCUTPOOL   TRUE
 
#define DEFAULT_DELAYEDCUTS   TRUE
 
#define DEFAULT_MAXTESTDELTA   10
 
#define DEFAULT_TRYNEGSCALING   TRUE
 
#define ORTHOFUNC   'e'
 
#define MINORTHO   0.5
 
#define NNONZOFFSET   500
 
#define BOUNDSWITCH   0.50
 
#define USEVBDS   TRUE
 
#define ALLOWLOCAL   TRUE
 
#define FIXINTEGRALRHS   TRUE
 
#define BOUNDSFORTRANS   NULL
 
#define BOUNDTYPESFORTRANS   NULL
 
#define MAXWEIGHTRANGE   10000.00
 
#define MINFRAC   0.05
 
#define MAXFRAC   1.00
 
#define MAXDNOM   1000
 
#define MAXSCALE   1000.0
 
#define USEVARBOUNDS   TRUE
 
#define ISEVEN(scip, value)   (SCIPisEQ((scip) , SCIPfloor(scip , (value) / 2) , (value) / 2))
 
#define ISODD(scip, value)   (!(ISEVEN((scip), (value))))
 
#define XOR(bool1, bool2)   ((bool1) ^ (bool2))
 
#define DIV(value1, powerof2value)   (((unsigned int)(value1)) / ((unsigned int)(powerof2value)))
 
#define MOD(value1, powerof2value)   (((unsigned int)(value1)) % ((unsigned int)(powerof2value)))
 
#define IRRELEVANT   -1
 
#define ZERO_ROW   -100
 
#define IDENT_TO_ROW_WITH_SMALLER_SLACK   -101
 
#define SLACK_GREATER_THAN_MAXSLACK   -102
 
#define DEFINES_VIOLATED_ZEROHALF_CUT   -103
 
#define NONEXISTENT_ROW   -105
 
#define NO_RELEVANT_COLUMNS   -106
 
#define SLACK_GREATER_THAN_MSL_MINUS_SODD   -107
 
#define LARGE_COL_EXISTS   -108
 
#define ZERO_COLUMN   -200
 
#define IDENT_TO_ANOTHER_COLUMN   -201
 
#define ZERO_LP_SOL   -202
 
#define LP_SOL_EQUALS_EVEN_LB   -203
 
#define LP_SOL_EQUALS_ODD_LB   -204
 
#define LP_SOL_EQUALS_EVEN_UB   -205
 
#define LP_SOL_EQUALS_ODD_UB   -206
 
#define SINGLETON_COLUMN   -207
 
#define CONTINUOUS_VARIABLE   -208
 
#define SMALL_FRACSOL_HEUR   -209
 
#define ALL_MATRIX_ROWS_DELETED   -210
 
#define BITARRAYBASETYPE   unsigned int
 
#define BITARRAYBITMASKTYPE   BITARRAYBASETYPE
 
#define BITARRAY   BITARRAYBASETYPE*
 
#define BITMASK(pos)    ((unsigned int)(1 << (pos)))
 
#define BITSET(var, pos)    (var) |= BITMASK(pos)
 
#define BITISSET(var, pos)    (var & BITMASK(pos))
 
#define BITARRAYBITSET(barray, pos)
 
#define BITARRAYBITISSET(barray, pos)
 
#define BITARRAYCLEAR(barray, barraysize)    BMSclearMemoryArray(barray,barraysize)
 
#define GETREQUIREDBITARRAYSIZE(nvalstostore)
 
#define GETBITARRAYINDEX(pos)    DIV((pos),Zerohalf_bitarraybasetypesize_nbits)
 
#define GETBITARRAYMASK(pos)    BITMASK(MOD((pos),Zerohalf_bitarraybasetypesize_nbits))
 
#define BITARRAYSFOREACH(barray1, barray2, size, op)
 
#define BITARRAYSXOR(barray1, barray2, size)   BITARRAYSFOREACH(barray1,barray2,size,^=)
 
#define BITARRAYSAREEQUAL(barray1, barray2, size)    (memcmp((void*)(barray1), (void*)(barray2), (size_t)((size) * (Zerohalf_bitarraybasetypesize))) == 0)
 
#define BRANCHPRIORITY__AVOID_BRANCHING   0
 
#define BRANCHPRIORITY__PREFER_BRANCHING   0
 

Typedefs

typedef enum cutseparatedby CUTSEPARATEDBY
 
typedef struct Zerohalf_SubLPData ZEROHALF_SUBLPDATA
 
typedef struct Zerohalf_LPData ZEROHALF_LPDATA
 
typedef struct Zerohalf_AuxIPData ZEROHALF_AUXIPDATA
 
typedef struct Zerohalf_Mod2Data ZEROHALF_MOD2DATA
 
typedef struct Zerohalf_CutData ZEROHALF_CUTDATA
 
typedef struct Zerohalf_AuxGraph_Node ZEROHALF_AUXGRAPH_NODE
 
typedef struct Zerohalf_AuxGraph ZEROHALF_AUXGRAPH
 

Enumerations

enum  preprocessingmethods {
  MODGAUSSIANELIMINATION = 'G',
  DELETEZEROROWS = 'Z',
  DELETEZEROCOLS = 'z',
  DELETECOLSINGLETONS = 's',
  ADDTRIVIALCUTS = 'X',
  DELETEIDENTROWS = 'I',
  MERGEIDENTCOLS = 'i',
  DELETELARGESLACKROWS = 'L',
  DELETESMALLFRACSOLCOLS = 'd',
  DELETEROWSWRTMINSLACK = 'M',
  PPCOLUMNS = 'C',
  PPROWS = 'R'
}
 
enum  sepamethods {
  STOPIFCUTWASFOUND = '!',
  SOLVEAUXSCIP = 's',
  SOLVEAUXSCIPEXACT = 'S',
  ENUMHEURNMAX1 = 'e',
  ENUMHEURNMAX2 = 'E',
  GAUSSHEUR = 'g',
  MAX2ODDENTRIESPERROW = '2'
}
 
enum  cutseparatedby {
  AUXIP,
  DECOMPOSITION,
  PPZEROONEROW,
  HEURISTICSENUM,
  HEURISTICSGAUSS,
  AUXGRAPH
}
 

Functions

static SCIP_RETCODE ZerohalfSubLPDataCreate (SCIP *scip, ZEROHALF_SUBLPDATA **subproblem)
 
static void ZerohalfSubLPDataFree (SCIP *scip, ZEROHALF_SUBLPDATA **subproblem)
 
static SCIP_RETCODE ZerohalfLPDataCreate (SCIP *scip, ZEROHALF_LPDATA **lpdata)
 
static SCIP_RETCODE ZerohalfLPDataFree (SCIP *scip, ZEROHALF_LPDATA **lpdata)
 
static SCIP_RETCODE ZerohalfMod2DataCreate (SCIP *scip, ZEROHALF_MOD2DATA **mod2data)
 
static SCIP_RETCODE ZerohalfMod2DataFree (SCIP *scip, ZEROHALF_MOD2DATA **mod2data)
 
static SCIP_RETCODE ZerohalfAuxIPDataCreate (SCIP *scip, ZEROHALF_AUXIPDATA **auxipdata)
 
static SCIP_RETCODE ZerohalfAuxIPDataFree (SCIP *scip, ZEROHALF_AUXIPDATA **auxipdata)
 
static SCIP_RETCODE ZerohalfCutDataCreate (SCIP *scip, ZEROHALF_CUTDATA **cutdata, ZEROHALF_SUBLPDATA *relatedsubproblem, ZEROHALF_MOD2DATA *relatedmod2data, int nrrowsincut, int nrowsincut, CUTSEPARATEDBY separatedby)
 
static SCIP_RETCODE ZerohalfCutDataFree (SCIP *scip, ZEROHALF_CUTDATA **cutdata)
 
static SCIP_RETCODE ZerohalfAuxGraphNodeCreate (SCIP *scip, ZEROHALF_AUXGRAPH_NODE **node)
 
static SCIP_RETCODE ZerohalfAuxGraphNodeFree (SCIP *scip, ZEROHALF_AUXGRAPH_NODE **node)
 
static SCIP_RETCODE ZerohalfAuxGraphCreate (SCIP *scip, ZEROHALF_AUXGRAPH **auxgraph)
 
static SCIP_RETCODE ZerohalfAuxGraphFree (SCIP *scip, ZEROHALF_AUXGRAPH **auxgraph)
 
static SCIP_DECL_SORTINDCOMP (compRealNonDecreasing)
 
static SCIP_DECL_SORTINDCOMP (compRealNonIncreasing)
 
static SCIP_RETCODE getRelevantColumns (SCIP *scip, ZEROHALF_LPDATA *lpdata)
 
static void findClosestLb (SCIP *scip, ZEROHALF_LPDATA *lpdata, SCIP_COL *col, SCIP_Real *bestlbsol, int *bestlbtype, SCIP_VAR **bestzvlb, SCIP_Real *bestbvlb, SCIP_Real *bestdvlb)
 
static void findClosestUb (SCIP *scip, ZEROHALF_LPDATA *lpdata, SCIP_COL *col, SCIP_Real *bestubsol, int *bestubtype, SCIP_VAR **bestzvub, SCIP_Real *bestbvub, SCIP_Real *bestdvub)
 
static SCIP_RETCODE getRelevantRows (SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata)
 
static SCIP_Bool hasMatrixMax2EntriesPerRow (ZEROHALF_MOD2DATA *mod2data)
 
static SCIP_RETCODE storeMod2Data (SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, int subproblemindex, ZEROHALF_MOD2DATA *mod2data)
 
static SCIP_RETCODE storeCutInArrays (SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_Real *cutcoefs, SCIP_Real *varsolvals, char normtype, SCIP_VAR **cutvars, SCIP_Real *cutvals, int *cutlen, SCIP_Real *cutact, SCIP_Real *cutnorm)
 
static SCIP_RETCODE addZerohalfCutToLP (SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_CUTDATA *cutdata, int *nsepacuts, SCIP_RESULT *result)
 
static void markRowAsRemoved (ZEROHALF_MOD2DATA *mod2data, int r, int flag)
 
static void markColAsRemovedAndClearCol (ZEROHALF_MOD2DATA *mod2data, int c, int flag)
 
static SCIP_RETCODE getZerohalfWeightvectorFromSelectedRowsBitarray (SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, BITARRAY rrowsincut, SCIP_Real **weights, int *nrowsincut)
 
static SCIP_RETCODE createZerohalfCutFromZerohalfWeightvector (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, SCIP_Real *weights, char normtype, int nzerohalfcuts, SCIP_Real **varsolvals, ZEROHALF_CUTDATA *cutdata, SCIP_Bool *cutoff)
 
static SCIP_RETCODE preprocessTrivialZerohalfCuts (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, int firstrowsind, int lastrowsind, char normtype, int maxsepacuts, int maxcuts, int *nsepacuts, int *nzerohalfcuts, ZEROHALF_CUTDATA **zerohalfcuts, SCIP_Real **varsolvals, CUTSEPARATEDBY cutseparatedby, SCIP_RESULT *result)
 
static SCIP_RETCODE preprocessRows (SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, int firstrowsind, int lastrowsind, SCIP_Bool removezerorows, SCIP_Bool removelargeslackrows, SCIP_Bool removeidenticalrows)
 
static SCIP_RETCODE preprocessColumns (SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, int firstcolsind, int lastcolsind, SCIP_Bool removezerocols, SCIP_Bool removecolsingletons, SCIP_Bool checkresultingrows)
 
static SCIP_RETCODE preprocessModGaussElim (SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data)
 
static SCIP_RETCODE decomposeProblem (SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata)
 
static SCIP_RETCODE preprocessColumnsWithSmallFracsol (SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_MOD2DATA *mod2data, SCIP_Real delta)
 
static SCIP_RETCODE preprocessConsiderMinSlack (SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, SCIP_Bool removelargeslackrows, SCIP_Bool removelargecolrows)
 
static SCIP_RETCODE preprocessIdenticalColums (SCIP *scip, ZEROHALF_MOD2DATA *mod2data)
 
static SCIP_RETCODE preprocess (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, char normtype, int maxsepacuts, int maxcuts, int *nsepacuts, int *nzerohalfcuts, ZEROHALF_CUTDATA **zerohalfcuts, SCIP_Real **varsolvals, SCIP_RESULT *result)
 
static SCIP_Real calcObjWeight (BITARRAY rowaggregation, int nrrows)
 
static SCIP_RETCODE createSubscip (SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, ZEROHALF_AUXIPDATA *auxipdata, SCIP_Bool setnodelimit)
 
static SCIP_RETCODE solveSubscip (SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_MOD2DATA *mod2data, ZEROHALF_AUXIPDATA *auxipdata, SCIP_SOL ***sols, int *nsols)
 
static SCIP_RETCODE getZerohalfWeightvectorForSingleRow (SCIP *scip, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, int rowsindex, int rrowsindex, SCIP_Real **weights)
 
static SCIP_RETCODE getBitarrayOfSelectedRows (SCIP *scip, ZEROHALF_MOD2DATA *mod2data, ZEROHALF_AUXIPDATA *auxipdata, SCIP_SOL *solution, BITARRAY *rrowsincut, int *nrrowsincut)
 
static SCIP_RETCODE separateBySolvingAuxIP (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, char normtype, int maxsepacuts, int maxcuts, SCIP_Bool setnodelimit, int *nsepacuts, int *nzerohalfcuts, ZEROHALF_CUTDATA **zerohalfcuts, SCIP_Real **varsolvals, SCIP_RESULT *result)
 
static SCIP_RETCODE calcInnerProductOfRowAndFracsol (SCIP *scip, ZEROHALF_MOD2DATA *mod2data, BITARRAY row, SCIP_Real maxinnerproduct, SCIP_Real *innerproduct)
 
static SCIP_RETCODE separateByEnumerationHeuristics (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, char normtype, int maxsepacuts, int maxcuts, int *nsepacuts, int *nzerohalfcuts, ZEROHALF_CUTDATA **zerohalfcuts, SCIP_Real **varsolvals, SCIP_RESULT *result, int maxncombinedrows)
 
static SCIP_RETCODE addEdgeToAuxGraph (SCIP *scip, ZEROHALF_AUXGRAPH *graph, int node1index, int node2index, SCIP_Bool isodd, SCIP_Real weight, int relatedrow)
 
static SCIP_RETCODE dijkstra (SCIP *scip, ZEROHALF_AUXGRAPH *graph, ZEROHALF_AUXGRAPH_NODE *sourcenode, ZEROHALF_AUXGRAPH_NODE *targetnode, SCIP_Real maxdistance)
 
static SCIP_RETCODE separateByAuxGraph (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, char normtype, int maxsepacuts, int maxcuts, int *nsepacuts, int *nzerohalfcuts, ZEROHALF_CUTDATA **zerohalfcuts, SCIP_Real **varsolvals, SCIP_RESULT *result, SCIP_Bool *wrongstructure)
 
static SCIP_RETCODE separateByGaussHeuristics (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, char normtype, int maxsepacuts, int maxcuts, int *nsepacuts, int *nzerohalfcuts, ZEROHALF_CUTDATA **zerohalfcuts, SCIP_Real **varsolvals, SCIP_RESULT *result)
 
static SCIP_RETCODE process (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, ZEROHALF_LPDATA *lpdata, ZEROHALF_MOD2DATA *mod2data, char normtype, int maxsepacuts, int maxcuts, int *nsepacuts, int *nzerohalfcuts, ZEROHALF_CUTDATA **zerohalfcuts, SCIP_Real **varsolvals, SCIP_RESULT *result)
 
static SCIP_DECL_SEPACOPY (sepaCopyZerohalf)
 
static SCIP_DECL_SEPAFREE (sepaFreeZerohalf)
 
static SCIP_DECL_SEPAEXECLP (sepaExeclpZerohalf)
 
SCIP_RETCODE SCIPincludeSepaZerohalf (SCIP *scip)
 

Variables

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

Macro Definition Documentation

#define SEPA_NAME   "zerohalf"

< print statistics

Definition at line 61 of file sepa_zerohalf.c.

Referenced by process(), and SCIP_DECL_SEPACOPY().

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

Definition at line 62 of file sepa_zerohalf.c.

#define SEPA_PRIORITY   -6000

Definition at line 63 of file sepa_zerohalf.c.

#define SEPA_FREQ   -1

Definition at line 64 of file sepa_zerohalf.c.

#define SEPA_MAXBOUNDDIST   0.0

Definition at line 65 of file sepa_zerohalf.c.

#define SEPA_USESSUBSCIP   TRUE

Definition at line 66 of file sepa_zerohalf.c.

#define SEPA_DELAY   FALSE

Definition at line 67 of file sepa_zerohalf.c.

#define DEFAULT_MAXROUNDS   5

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

Definition at line 69 of file sepa_zerohalf.c.

#define DEFAULT_MAXROUNDSROOT   10

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

Definition at line 70 of file sepa_zerohalf.c.

#define DEFAULT_MAXSEPACUTS   50

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

Definition at line 71 of file sepa_zerohalf.c.

#define DEFAULT_MAXSEPACUTSROOT   500

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

Definition at line 72 of file sepa_zerohalf.c.

#define DEFAULT_DYNAMICCUTS   TRUE

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

Definition at line 73 of file sepa_zerohalf.c.

#define DEFAULT_DECOMPOSEPROBLEM   FALSE

should problem be decomposed into subproblems (if possible)?

Definition at line 74 of file sepa_zerohalf.c.

#define DEFAULT_MAXDEPTH   -1

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

Definition at line 75 of file sepa_zerohalf.c.

#define DEFAULT_MINVIOLATION   0.30

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

Definition at line 76 of file sepa_zerohalf.c.

#define DEFAULT_FORCECUTSTOLP   FALSE

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

Definition at line 77 of file sepa_zerohalf.c.

#define DEFAULT_FORCECUTSTOSEPASTORE   FALSE

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

Definition at line 78 of file sepa_zerohalf.c.

#define DEFAULT_MAXCUTS   100

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

Definition at line 81 of file sepa_zerohalf.c.

#define DEFAULT_MAXCUTSROOT   1000

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

Definition at line 84 of file sepa_zerohalf.c.

#define DEFAULT_SUBSCIPOBJECTIVE   'v'

auxiliary IP objective function type

Definition at line 87 of file sepa_zerohalf.c.

#define DEFAULT_RELAXCONTVARS   FALSE

should continuous variables be relaxed by adding variable bounds?

Definition at line 88 of file sepa_zerohalf.c.

#define DEFAULT_SCALEFRACCOEFFS   TRUE

should rows be scaled to make fractional coefficients integer?

Definition at line 89 of file sepa_zerohalf.c.

#define DEFAULT_SUBSCIPSETTINGS   "-"

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

Definition at line 90 of file sepa_zerohalf.c.

#define DEFAULT_SUBSCIPSOLLIMIT   -1

limits/solutions setting of the auxiliary IP

Definition at line 91 of file sepa_zerohalf.c.

#define DEFAULT_SUBSCIPUSEALLSOLS   TRUE

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

Definition at line 92 of file sepa_zerohalf.c.

#define DEFAULT_PPDELTA   0.500

value of delta parameter used in preprocessing method 'd'

Definition at line 95 of file sepa_zerohalf.c.

#define DEFAULT_SUBSCIPOBJPEN   0.001

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

Definition at line 96 of file sepa_zerohalf.c.

#define DEFAULT_PPMETHODS   "CXGXIM"

preprocessing methods and ordering

Definition at line 98 of file sepa_zerohalf.c.

#define DEFAULT_SEPAMETHODS   "2g"

preprocessing methods and ordering

Definition at line 99 of file sepa_zerohalf.c.

#define DEFAULT_MAXNCALLS   -1LL

maximal number of calls (-1: unlimited)

Definition at line 100 of file sepa_zerohalf.c.

#define DEFAULT_IGNOREPREVIOUSZHCUTS   FALSE

should zerohalf cuts found in previous callbacks be ignored?

Definition at line 101 of file sepa_zerohalf.c.

#define DEFAULT_ONLYORIGROWS   FALSE

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

Definition at line 102 of file sepa_zerohalf.c.

#define DEFAULT_USEZHCUTPOOL   TRUE

should zerohalf cuts be filtered using a cutpool

Definition at line 103 of file sepa_zerohalf.c.

#define DEFAULT_DELAYEDCUTS   TRUE

should cuts be added to the delayed cut pool?

Definition at line 104 of file sepa_zerohalf.c.

#define DEFAULT_MAXTESTDELTA   10

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

Definition at line 105 of file sepa_zerohalf.c.

#define DEFAULT_TRYNEGSCALING   TRUE

should negative values also be tested in scaling for cmir?

Definition at line 106 of file sepa_zerohalf.c.

#define ORTHOFUNC   'e'

Definition at line 109 of file sepa_zerohalf.c.

#define MINORTHO   0.5

Definition at line 110 of file sepa_zerohalf.c.

#define NNONZOFFSET   500

Definition at line 113 of file sepa_zerohalf.c.

#define BOUNDSWITCH   0.50

Definition at line 114 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define USEVBDS   TRUE

Definition at line 115 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define ALLOWLOCAL   TRUE

Definition at line 116 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define FIXINTEGRALRHS   TRUE

Definition at line 117 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define BOUNDSFORTRANS   NULL

Definition at line 118 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define BOUNDTYPESFORTRANS   NULL

Definition at line 119 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define MAXWEIGHTRANGE   10000.00

Definition at line 120 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define MINFRAC   0.05

Definition at line 121 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define MAXFRAC   1.00

Definition at line 122 of file sepa_zerohalf.c.

Referenced by createZerohalfCutFromZerohalfWeightvector().

#define MAXDNOM   1000

Definition at line 125 of file sepa_zerohalf.c.

#define MAXSCALE   1000.0

Definition at line 126 of file sepa_zerohalf.c.

#define USEVARBOUNDS   TRUE

Definition at line 129 of file sepa_zerohalf.c.

Referenced by findClosestLb(), and findClosestUb().

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

is value even?

Definition at line 184 of file sepa_zerohalf.c.

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

is value odd?

Definition at line 185 of file sepa_zerohalf.c.

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

Definition at line 186 of file sepa_zerohalf.c.

Referenced by separateByGaussHeuristics().

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

integer division using a power of 2 as divisor

Definition at line 187 of file sepa_zerohalf.c.

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

remainder of integer division using a power of 2 as divisor

Definition at line 188 of file sepa_zerohalf.c.

#define IRRELEVANT   -1

row or column is irrelevant

Definition at line 240 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define ZERO_ROW   -100

row has no nonzero entries

Definition at line 243 of file sepa_zerohalf.c.

Referenced by preprocessRows(), and ZerohalfAuxGraphFree().

#define IDENT_TO_ROW_WITH_SMALLER_SLACK   -101

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

Definition at line 244 of file sepa_zerohalf.c.

Referenced by preprocessRows(), and ZerohalfAuxGraphFree().

#define SLACK_GREATER_THAN_MAXSLACK   -102

row has a slack value > maxslack

Definition at line 245 of file sepa_zerohalf.c.

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

#define DEFINES_VIOLATED_ZEROHALF_CUT   -103

row defines a violated zerohalf cut

Definition at line 246 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define NONEXISTENT_ROW   -105

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

Definition at line 250 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define NO_RELEVANT_COLUMNS   -106

row does not contain relevant columns

Definition at line 251 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define SLACK_GREATER_THAN_MSL_MINUS_SODD   -107

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

Definition at line 252 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define LARGE_COL_EXISTS   -108

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

Definition at line 255 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define ZERO_COLUMN   -200

column has no nonzero entries

Definition at line 262 of file sepa_zerohalf.c.

Referenced by preprocessColumns(), and ZerohalfAuxGraphFree().

#define IDENT_TO_ANOTHER_COLUMN   -201

column is identical to another column

Definition at line 263 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define ZERO_LP_SOL   -202

column corresponds to a variable whose LP solution is zero

Definition at line 264 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define LP_SOL_EQUALS_EVEN_LB   -203

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

Definition at line 265 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define LP_SOL_EQUALS_ODD_LB   -204

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

Definition at line 266 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define LP_SOL_EQUALS_EVEN_UB   -205

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

Definition at line 267 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define LP_SOL_EQUALS_ODD_UB   -206

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

Definition at line 268 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define SINGLETON_COLUMN   -207

column has only one nonzero entry

Definition at line 269 of file sepa_zerohalf.c.

Referenced by preprocessColumns(), and ZerohalfAuxGraphFree().

#define CONTINUOUS_VARIABLE   -208

column corresponds to a non-integer variable

Definition at line 270 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define SMALL_FRACSOL_HEUR   -209

column has been omitted (see preprocessColumnsWithSmallFracsol)

Definition at line 271 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define ALL_MATRIX_ROWS_DELETED   -210

all rows (of the current subproblem) have been deleted

Definition at line 272 of file sepa_zerohalf.c.

Referenced by ZerohalfAuxGraphFree().

#define BITARRAYBASETYPE   unsigned int

base type used for the bitarray data structures

Definition at line 283 of file sepa_zerohalf.c.

#define BITARRAYBITMASKTYPE   BITARRAYBASETYPE

Definition at line 284 of file sepa_zerohalf.c.

Referenced by preprocessColumns(), and separateByGaussHeuristics().

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

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

Definition at line 296 of file sepa_zerohalf.c.

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

set the pos-th bit of var

Definition at line 299 of file sepa_zerohalf.c.

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

is the pos-th bit of var set?

Definition at line 302 of file sepa_zerohalf.c.

#define BITARRAYBITSET (   barray,
  pos 
)
Value:
#define MOD(value1, powerof2value)
static const unsigned int Zerohalf_bitarraybasetypesize_nbits
#define DIV(value1, powerof2value)
#define BITSET(var, pos)

set the pos-th bit of bitarray barray

Definition at line 305 of file sepa_zerohalf.c.

#define BITARRAYBITISSET (   barray,
  pos 
)
Value:
#define MOD(value1, powerof2value)
static const unsigned int Zerohalf_bitarraybasetypesize_nbits
#define BITISSET(var, pos)
#define DIV(value1, powerof2value)

is the pos-th bit of bitarray barray set?

Definition at line 309 of file sepa_zerohalf.c.

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

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

clear bitarray

Definition at line 313 of file sepa_zerohalf.c.

Referenced by separateByAuxGraph(), and separateByEnumerationHeuristics().

#define GETREQUIREDBITARRAYSIZE (   nvalstostore)
Value:
((((unsigned int)(nvalstostore)) % (Zerohalf_bitarraybasetypesize_nbits) == 0) \
? (((unsigned int)(nvalstostore)) / (Zerohalf_bitarraybasetypesize_nbits)) \
: ((((unsigned int)(nvalstostore)) / (Zerohalf_bitarraybasetypesize_nbits)) + 1))
static const unsigned int Zerohalf_bitarraybasetypesize_nbits

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

Definition at line 316 of file sepa_zerohalf.c.

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

get the corresponding array element of a bitarray position

Definition at line 322 of file sepa_zerohalf.c.

Referenced by preprocessColumns(), and separateByGaussHeuristics().

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

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

Definition at line 325 of file sepa_zerohalf.c.

Referenced by preprocessColumns(), and separateByGaussHeuristics().

#define BITARRAYSFOREACH (   barray1,
  barray2,
  size,
  op 
)
Value:
{ \
int idx__; \
for( idx__ = 0 ; idx__ < (size) ; ++idx__) \
{ \
barray2[idx__] op barray1[idx__]; \
} \
}

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

Definition at line 328 of file sepa_zerohalf.c.

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

barray2 = barray1 XOR barray2

Definition at line 338 of file sepa_zerohalf.c.

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

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

are barray1 and barray2 equal?

Definition at line 341 of file sepa_zerohalf.c.

Referenced by preprocessRows(), and preprocessTrivialZerohalfCuts().

#define BRANCHPRIORITY__AVOID_BRANCHING   0

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

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

Definition at line 4879 of file sepa_zerohalf.c.

#define BRANCHPRIORITY__PREFER_BRANCHING   0

Definition at line 4880 of file sepa_zerohalf.c.

Typedef Documentation

Definition at line 176 of file sepa_zerohalf.c.

typedef struct Zerohalf_SubLPData ZEROHALF_SUBLPDATA

Definition at line 446 of file sepa_zerohalf.c.

typedef struct Zerohalf_LPData ZEROHALF_LPDATA

Definition at line 486 of file sepa_zerohalf.c.

typedef struct Zerohalf_AuxIPData ZEROHALF_AUXIPDATA

Definition at line 532 of file sepa_zerohalf.c.

typedef struct Zerohalf_Mod2Data ZEROHALF_MOD2DATA

Definition at line 562 of file sepa_zerohalf.c.

typedef struct Zerohalf_CutData ZEROHALF_CUTDATA

Definition at line 592 of file sepa_zerohalf.c.

typedef struct Zerohalf_AuxGraph_Node ZEROHALF_AUXGRAPH_NODE

Definition at line 598 of file sepa_zerohalf.c.

typedef struct Zerohalf_AuxGraph ZEROHALF_AUXGRAPH

Definition at line 618 of file sepa_zerohalf.c.

Enumeration Type Documentation

preprocessing methods, usable within the ppmethods parameter

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

Definition at line 137 of file sepa_zerohalf.c.

separation methods, usable within the sepamethods parameter

Enumerator
STOPIFCUTWASFOUND 
SOLVEAUXSCIP 
SOLVEAUXSCIPEXACT 
ENUMHEURNMAX1 
ENUMHEURNMAX2 
GAUSSHEUR 
MAX2ODDENTRIESPERROW 

Definition at line 157 of file sepa_zerohalf.c.

statistics: "origin" of separated cut

Enumerator
AUXIP 
DECOMPOSITION 
PPZEROONEROW 
HEURISTICSENUM 
HEURISTICSGAUSS 
AUXGRAPH 

Definition at line 172 of file sepa_zerohalf.c.

Function Documentation

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

creates and initializes sub LP data structures

Parameters
scipSCIP data structure
subproblempointer to store pointer to created data structure

Definition at line 628 of file sepa_zerohalf.c.

References NULL.

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

frees sub LP data structures

Parameters
scipSCIP data structure
subproblempointer to pointer of data structure

Definition at line 653 of file sepa_zerohalf.c.

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

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

creates and initializes LP data structures

Parameters
scipSCIP data structure
lpdatapointer to store pointer to created data structure

Definition at line 693 of file sepa_zerohalf.c.

References NULL.

Referenced by ZerohalfSubLPDataFree().

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

frees LP data structures

Parameters
scipSCIP data structure
lpdatapointer to pointer of data structure

Definition at line 728 of file sepa_zerohalf.c.

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

creates and initializes mod 2 data structures

Parameters
scipSCIP data structure
mod2datapointer to store pointer to created data structure

Definition at line 796 of file sepa_zerohalf.c.

References NULL.

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

frees data structures

Parameters
scipSCIP data structure
mod2datapointer to pointer of data structure

Definition at line 827 of file sepa_zerohalf.c.

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

creates and initializes auxiliary IP data structures

Parameters
scipSCIP data structure
auxipdatapointer to store pointer to created data structure

Definition at line 895 of file sepa_zerohalf.c.

References NULL.

Referenced by separateBySolvingAuxIP().

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

frees auxiliary IP data structures

Parameters
scipSCIP data structure
auxipdatapointer to pointer of data structure

Definition at line 922 of file sepa_zerohalf.c.

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

Referenced by separateBySolvingAuxIP().

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

creates and initializes cut data structures

Parameters
scipSCIP data structure
cutdatapointer to pointer of data structure
relatedsubproblempointer to corresponding subproblem
relatedmod2datapointer to corresponding mod 2 data
nrrowsincutnumber of preprocessed / mod 2 rows in cut
nrowsincutnumber of original / LP rows in cut
separatedbyflag storing the method that separated this cut

Definition at line 961 of file sepa_zerohalf.c.

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

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

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

frees cut data structures

Parameters
scipSCIP data structure
cutdatapointer to pointer of data structure

Definition at line 1006 of file sepa_zerohalf.c.

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

Referenced by ZerohalfCutDataCreate().

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

creates and initializes auxiliary graph node data structures

Parameters
scipSCIP data structure
nodepointer to store pointer to created data structure

Definition at line 1028 of file sepa_zerohalf.c.

References NULL.

Referenced by separateByAuxGraph(), and ZerohalfCutDataFree().

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

frees auxiliary graph node data structures

Parameters
scipSCIP data structure
nodepointer to pointer of data structure

Definition at line 1052 of file sepa_zerohalf.c.

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

Referenced by ZerohalfAuxGraphFree().

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

creates and initializes auxiliary graph data structures

Parameters
scipSCIP data structure
auxgraphpointer to store pointer to created data structure

Definition at line 1081 of file sepa_zerohalf.c.

References NULL.

Referenced by separateByAuxGraph(), and ZerohalfAuxGraphNodeFree().

static SCIP_DECL_SORTINDCOMP ( compRealNonDecreasing  )
static

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

Definition at line 1490 of file sepa_zerohalf.c.

References SCIP_Real.

Referenced by ZerohalfAuxGraphFree().

static SCIP_DECL_SORTINDCOMP ( compRealNonIncreasing  )
static

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

Definition at line 1507 of file sepa_zerohalf.c.

References SCIP_Real.

static SCIP_RETCODE getRelevantColumns ( SCIP scip,
ZEROHALF_LPDATA lpdata 
)
static

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

Parameters
scipSCIP data structure
lpdatadata of current LP relaxation

Definition at line 1529 of file sepa_zerohalf.c.

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

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

Parameters
scipSCIP data structure
lpdatadata of current LP relaxation
colcolumn to get closest lower bound
bestlbsolpointer to store value of closest lower bound
bestlbtypepointer to store type of closest lower bound
bestzvlbpointer to store variable z in closest variable lower bound b*z + d
bestbvlbpointer to store coefficient b in closest variable lower bound b*z + d
bestdvlbpointer to store constant d in closest variable lower bound b*z + d

Definition at line 1703 of file sepa_zerohalf.c.

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

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

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

Parameters
scipSCIP data structure
lpdatadata of current LP relaxation
colcolumn to get closest upper bound
bestubsolpointer to store value of closest upper bound
bestubtypepointer to store type of closest upper bound
bestzvubpointer to store variable z in closest variable upper bound b*z + d
bestbvubpointer to store coefficient b in closest variable upper bound b*z + d
bestdvubpointer to store constant d in closest variable upper bound b*z + d

Definition at line 1810 of file sepa_zerohalf.c.

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

Referenced by findClosestLb().

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

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

Parameters
scipSCIP data structure
sepadataseparator data
lpdatadata of current LP relaxation

Definition at line 1914 of file sepa_zerohalf.c.

Referenced by findClosestUb().

static SCIP_Bool hasMatrixMax2EntriesPerRow ( ZEROHALF_MOD2DATA mod2data)
static
Parameters
mod2dataconsidered mod 2 data

Definition at line 2391 of file sepa_zerohalf.c.

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

Referenced by preprocess(), and separateByAuxGraph().

static SCIP_RETCODE storeMod2Data ( SCIP scip,
SCIP_SEPADATA sepadata,
ZEROHALF_LPDATA lpdata,
int  subproblemindex,
ZEROHALF_MOD2DATA mod2data 
)
static
Parameters
scipSCIP data structure
sepadataseparator data
lpdatadata of current LP relaxation
subproblemindexindex of considered subproblem
mod2datadata (mod 2)

Definition at line 2467 of file sepa_zerohalf.c.

Referenced by hasMatrixMax2EntriesPerRow().

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

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

Parameters
scipSCIP data structure
nvarsnumber of problem variables
varsproblem variables
cutcoefsdense coefficient vector
varsolvalsdense variable LP solution vector
normtypetype of norm to use for efficacy norm calculation
cutvarsarray to store variables of sparse cut vector
cutvalsarray to store coefficients of sparse cut vector
cutlenpointer to store number of nonzero entries in cut
cutactpointer to store activity of cut
cutnormpointer to store norm of cut vector

Definition at line 2848 of file sepa_zerohalf.c.

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

Referenced by createZerohalfCutFromZerohalfWeightvector().

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

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

Parameters
scipSCIP data structure
sepadataseparator data
cutdataseparated zerohalf cut
nsepacutspointer to store number of separated (efficacious) zerohalf cuts
resultpointer to store return code

Definition at line 2959 of file sepa_zerohalf.c.

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

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

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

Parameters
mod2dataconsidered mod 2 data
rmod2data->rows index of row that shall be removed
flagflag (cause of removal)

Definition at line 3025 of file sepa_zerohalf.c.

Referenced by preprocessColumns(), and preprocessRows().

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

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

Parameters
mod2dataconsidered mod 2 data
cmod2data->relatedsubproblem->rcols index of column that shall be removed
flagflag (cause of removal)

Definition at line 3044 of file sepa_zerohalf.c.

Referenced by preprocessColumns().

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

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

Parameters
scipSCIP data structure
sepadataseparator data
lpdatadata of current LP relaxation
mod2dataconsidered mod 2 data
rrowsincutsubset of selected mod2data->rows
weightspointer to store the {-0.5,0,0.5} weights vector
nrowsincutpointer to store the number of combined original LP rows

Definition at line 3079 of file sepa_zerohalf.c.

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

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

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

creates a zerohalf cut from a given weightvector

Parameters
scipSCIP data structure
sepaseparator
sepadataseparator data
lpdatadata of current LP relaxation
weightsweightvector
normtypeSCIP normtype
nzerohalfcutsnumber of zerohalf cuts (used for naming the cut)
varsolvalspointer to array of LP solution values of variables
cutdatapointer to data structure used for storing the cut
cutoffwhether a cutoff has been detected

Definition at line 3153 of file sepa_zerohalf.c.

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

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

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

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

Parameters
scipSCIP data structure
sepaseparator
sepadataseparator data
lpdatadata of current LP relaxation
mod2dataconsidered (preprocessed) subproblem mod 2
firstrowsindfirst mod2data->rows index to be considered
lastrowsindlast mod2data->rows index to be considered
normtypeSCIP normtype
maxsepacutsmaximal number of zerohalf cuts separated per separation round
maxcutsmaximal number of zerohalf cuts found per separation round (incl. ineff. cuts)
nsepacutspointer to store current number of separated zerohalf cuts
nzerohalfcutspointer to store current number of found zerohalf cuts
zerohalfcutspointer to store a found zerohalf cut
varsolvalsdense variable LP solution vector
cutseparatedbyflag
resultpointer to SCIP result value of separation

Definition at line 3318 of file sepa_zerohalf.c.

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

Referenced by createZerohalfCutFromZerohalfWeightvector(), preprocess(), and separateByGaussHeuristics().

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

applies some row reductions

Parameters
scipSCIP data structure
sepadataseparator data
lpdatadata of current LP relaxation
mod2dataconsidered (preprocessed) subproblem mod 2
firstrowsindfirst mod2data->rows index to be considered
lastrowsindlast mod2data->rows index to be considered
removezerorowsshould zero rows be removed?
removelargeslackrowsshould rows with slack > maxslack be removed?
removeidenticalrowsshould identical rows be removed?

Definition at line 3452 of file sepa_zerohalf.c.

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

Referenced by preprocess(), preprocessTrivialZerohalfCuts(), and separateByGaussHeuristics().

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

applies some column reductions

Parameters
scipSCIP data structure
sepadataseparator data
lpdatadata of current LP relaxation
mod2dataconsidered (preprocessed) subproblem mod 2
firstcolsindfirst mod2data->rows index to be considered
lastcolsindlast mod2data->rows index to be considered
removezerocolsshould zero columns be removed?
removecolsingletonsshould column singletons be removed?
checkresultingrowsshould rows whose slack becomes larger than maxslack be removed?

Definition at line 3589 of file sepa_zerohalf.c.

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

Referenced by preprocess(), preprocessRows(), and separateByGaussHeuristics().

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

applies modified Gaussian Elimination reduction

Parameters
scipSCIP data structure
sepadataseparator data
lpdatadata of current LP relaxation
mod2dataconsidered (preprocessed) subproblem mod 2

Definition at line 3767 of file sepa_zerohalf.c.

Referenced by preprocess(), and preprocessColumns().

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

decomposes the problem into subproblems which can be considered separately

Parameters
scipSCIP data structure
sepadataseparator data
lpdatadata of current LP relaxation

Definition at line 3903 of file sepa_zerohalf.c.

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

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

Parameters
scipSCIP data structure
sepadataseparator data
mod2dataconsidered (preprocessed) subproblem mod 2
deltadelta value

Definition at line 4292 of file sepa_zerohalf.c.

Referenced by preprocess().

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

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

Parameters
scipSCIP data structure
sepadataseparator data
lpdatadata of current LP relaxation
mod2dataconsidered (preprocessed) subproblem mod 2
removelargeslackrowsshould rows with slack + minslack > maxslack be removed?
removelargecolrowsshould rows with "large valued" columns that cannot be negated be removed?

Definition at line 4353 of file sepa_zerohalf.c.

Referenced by preprocess().

static SCIP_RETCODE preprocessIdenticalColums ( SCIP scip,
ZEROHALF_MOD2DATA mod2data 
)
static

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

Parameters
scipSCIP data structure
mod2dataconsidered (preprocessed) subproblem mod 2

Definition at line 4535 of file sepa_zerohalf.c.

Referenced by preprocess().

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

preprocess subproblem

Parameters
scipSCIP data structure
sepaseparator
sepadataseparator data
lpdatadata of current LP relaxation
mod2dataconsidered (preprocessed) subproblem mod 2
normtypetype of norm to use for efficacy norm calculation
maxsepacutsmaximal number of zerohalf cuts separated per separation round
maxcutsmaximal number of zerohalf cuts found per separation round (incl. ineff. cuts)
nsepacutspointer to store current number of separated zerohalf cuts
nzerohalfcutspointer to store current number of found zerohalf cuts
zerohalfcutsarray to store found zerohalf cuts
varsolvalsdense variable LP solution vector
resultpointer to SCIP result value of separation

Definition at line 4614 of file sepa_zerohalf.c.

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

static SCIP_Real calcObjWeight ( BITARRAY  rowaggregation,
int  nrrows 
)
static

returns the objective weights for the weighted feasibility AuxIP

Parameters
rowaggregationrow aggregation bitarray
nrrowsnumber of relevant rows

Definition at line 4849 of file sepa_zerohalf.c.

Referenced by preprocess().

static SCIP_RETCODE createSubscip ( SCIP scip,
SCIP_SEPADATA sepadata,
ZEROHALF_LPDATA lpdata,
ZEROHALF_MOD2DATA mod2data,
ZEROHALF_AUXIPDATA auxipdata,
SCIP_Bool  setnodelimit 
)
static
Parameters
scipSCIP data structure
sepadataseparator data
lpdatadata of current LP relaxation
mod2dataconsidered (preprocessed) subproblem mod 2
auxipdatapointer to data structure to store the auxiliary IP data
setnodelimitshould a node limit be set?

Definition at line 4882 of file sepa_zerohalf.c.

Referenced by separateBySolvingAuxIP().

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

solves the auxiliary IP given as subscip

Parameters
scipSCIP data structure
sepadataseparator data
mod2dataconsidered (preprocessed) subproblem mod 2
auxipdataauxiliary IP data
solspointer to store array of solutions
nsolspointer to store number of solutions

Definition at line 5233 of file sepa_zerohalf.c.

Referenced by separateBySolvingAuxIP().

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

determines the weightvector for a single row

Parameters
scipSCIP data structure
sepadataseparator data
lpdatadata of current LP relaxation
rowsindexlpdata->rows index
rrowsindex"subproblem"->rrows index
weightspointer to store the weight vector

Definition at line 5366 of file sepa_zerohalf.c.

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

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

Parameters
scipSCIP data structure
mod2dataconsidered (preprocessed) subproblem mod 2
auxipdataauxiliary IP data
solutionconsidered solution
rrowsincutpointer to store the subset of rows as bitarray (length: number of relevant rows)
nrrowsincutnumber of combined relevant rows

Definition at line 5411 of file sepa_zerohalf.c.

Referenced by separateBySolvingAuxIP().

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

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

Parameters
scipSCIP data structure
sepaseparator
sepadataseparator data
lpdatadata of current LP relaxation
mod2dataconsidered (preprocessed) subproblem mod 2
normtypeSCIP normtype
maxsepacutsmaximal number of zerohalf cuts separated per separation round
maxcutsmaximal number of zerohalf cuts found per separation round (incl. ineff. cuts)
setnodelimitshould a node limit be set for solving the auxiliary IP?
nsepacutspointer to store current number of separated zerohalf cuts
nzerohalfcutspointer to store current number of found zerohalf cuts
zerohalfcutsarray to store found zerohalf cuts
varsolvalsdense variable LP solution vector
resultpointer to SCIP result value of separation

Definition at line 5456 of file sepa_zerohalf.c.

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

Referenced by process().

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

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

Parameters
scipSCIP data structure
mod2dataconsidered (preprocessed) subproblem mod 2
rowconsidered mod2data->row
maxinnerproductcalculation is aborted if innerproduct >= maxinnerproduct
innerproductpointer to store the inner product

Definition at line 5605 of file sepa_zerohalf.c.

Referenced by separateByEnumerationHeuristics(), and separateBySolvingAuxIP().

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

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

Parameters
scipSCIP data structure
sepaseparator
sepadataseparator data
lpdatadata of current LP relaxation
mod2dataconsidered (preprocessed) subproblem mod 2
normtypeSCIP normtype
maxsepacutsmaximal number of zerohalf cuts separated per separation round
maxcutsmaximal number of zerohalf cuts found per separation round (incl. ineff. cuts)
nsepacutspointer to store current number of separated zerohalf cuts
nzerohalfcutspointer to store current number of found zerohalf cuts
zerohalfcutsarray to store found zerohalf cuts
varsolvalsdense variable LP solution vector
resultpointer to SCIP result value of separation
maxncombinedrowsmaximal number of combined rows; currently only 1 or 2 is supported

Definition at line 5646 of file sepa_zerohalf.c.

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

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

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

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

Parameters
scipSCIP data structure
graphauxiliary graph
node1indexstart node of edge
node2indexend node of edge
isoddis the rhs value of the corresponding mod2data->row odd?
weightweight of the edge
relatedrowcorresponding mod2data->row

Definition at line 5931 of file sepa_zerohalf.c.

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

Referenced by separateByAuxGraph(), and separateByEnumerationHeuristics().

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

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

Parameters
scipSCIP data structure
graphauxiliary graph
sourcenodestart node
targetnodeend node
maxdistancecalculation will be aborted if a proof is found that no shortest path with length less than maxdistance exists

Definition at line 6047 of file sepa_zerohalf.c.

Referenced by addEdgeToAuxGraph(), and separateByAuxGraph().

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

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

Parameters
scipSCIP data structure
sepaseparator
sepadataseparator data
lpdatadata of current LP relaxation
mod2dataconsidered (preprocessed) subproblem mod 2
normtypeSCIP normtype
maxsepacutsmaximal number of zerohalf cuts separated per separation round
maxcutsmaximal number of zerohalf cuts found per separation round (incl. ineff. cuts)
nsepacutspointer to store current number of separated zerohalf cuts
nzerohalfcutspointer to store current number of found zerohalf cuts
zerohalfcutsarray to store found zerohalf cuts
varsolvalsdense variable LP solution vector
resultpointer to SCIP result value of separation
wrongstructurepointer to store if there is a row with more than two odd entries

Definition at line 6145 of file sepa_zerohalf.c.

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

Referenced by process().

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

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

Parameters
scipSCIP data structure
sepaseparator
sepadataseparator data
lpdatadata of current LP relaxation
mod2dataconsidered (preprocessed) subproblem mod 2
normtypeSCIP normtype
maxsepacutsmaximal number of zerohalf cuts separated per separation round
maxcutsmaximal number of zerohalf cuts found per separation round (incl. ineff. cuts)
nsepacutspointer to store current number of separated zerohalf cuts
nzerohalfcutspointer to store current number of found zerohalf cuts
zerohalfcutsarray to store found zerohalf cuts
varsolvalsdense variable LP solution vector
resultpointer to SCIP result value of separation

Definition at line 6405 of file sepa_zerohalf.c.

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

Referenced by process(), and separateByAuxGraph().

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

processes subproblem (i.e. runs separation algorithms)

Parameters
scipSCIP data structure
sepaseparator
sepadataseparator data
lpdatadata of current LP relaxation
mod2dataconsidered (preprocessed) subproblem mod 2
normtypeSCIP normtype
maxsepacutsmaximal number of zerohalf cuts separated per separation round
maxcutsmaximal number of zerohalf cuts found per separation round (incl. ineff. cuts)
nsepacutspointer to store current number of separated zerohalf cuts
nzerohalfcutspointer to store current number of found zerohalf cuts
zerohalfcutsarray to store found zerohalf cuts
varsolvalsdense variable LP solution vector
resultpointer to SCIP result value of separation

Definition at line 6542 of file sepa_zerohalf.c.

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

Referenced by separateByGaussHeuristics().

static SCIP_DECL_SEPACOPY ( sepaCopyZerohalf  )
static

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

Definition at line 6822 of file sepa_zerohalf.c.

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

Referenced by process().

static SCIP_DECL_SEPAFREE ( sepaFreeZerohalf  )
static

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

Definition at line 6836 of file sepa_zerohalf.c.

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

static SCIP_DECL_SEPAEXECLP ( sepaExeclpZerohalf  )
static

LP solution separation method of separator

Definition at line 6900 of file sepa_zerohalf.c.

Referenced by SCIP_DECL_SEPAFREE().

SCIP_RETCODE SCIPincludeSepaZerohalf ( SCIP scip)

creates the zerohalf separator and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 7448 of file sepa_zerohalf.c.

Referenced by process(), and SCIPincludeDefaultPlugins().

Variable Documentation

const unsigned int Zerohalf_bitarraybasetypesize = sizeof(BITARRAYBASETYPE)
static

size of BITARRAYBASETYPE

Definition at line 287 of file sepa_zerohalf.c.

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

number of bits per BITARRAYBASETYPE

Definition at line 290 of file sepa_zerohalf.c.