Testing a given matrix for membership in the family of Bernoulli matrices is a longstanding problem, the many applications of Bernoulli vectors in computer science, finance, medicine, and operations research emphasize its practical relevance. A novel approach towards this problem was taken by [Fiebig et al., 2017] for lowdimensional settings d <= 6. For the first time, they exploit the close relationship between the Bernoulli polytope (also known as correlation polytope) and the well-studied cut polytope, which plays a central role in membership testing of Bernoulli matrices. Inspired by this approach, we use results from [Deza and Laurent, 1997, Embrechts et al., 2016, Fiebig et al., 2017] in a pre-phase of our algorithm to check necessary and sufficient conditions, before actually testing a matrix on Bernoulli compatibility. In our main approach, we however build upon an early attempt by [Lee, 1993] based on the vertex representation of the correlation polytope and directly solve the corresponding linear program. To appropriately deal with the issue of exponentially many primal variables, we propose a specifically taylored column generation method. A straightforward, yet novel, analysis of the arising subproblem of determining the most violated dual constraint in the column generation process leads to an exact algorithm for membership testing. Although the membership problem is known to be NP-complete, we observe very promising performance up to dimension d = 40 on a broad variety of test problems.
Citation
Working Paper, Institute of Mathematics, Augsburg University, August 2017.