Mathematical Programming Computation, Volume 10, Issue 1, March 2018

Font Size:  Small  Medium  Large

Branch-and-cut for linear programs with overlapping SOS1 constraints

Tobias Fischer, Marc E. Pfetsch


SOS1 constraints require that at most one of a given set of variables is nonzero. In this article, we investigate a branch-and-cut algorithm to solve linear programs with SOS1 constraints. We focus on the case in which the SOS1 constraints overlap. The corresponding conflict graph can algorithmically be exploited, for instance, for improved branching rules, preprocessing, primal heuristics, and cutting planes. In an extensive computational study, we evaluate the components of our implementation on instances for three different applications. We also demonstrate the effectiveness of this approach by comparing it to the solution of a mixedinteger programming formulation, if the variables appearing in SOS1 constraints arbounded.

Full Text: PDF

mpc footer
© MPS 2008-2018