Optimization Online


Branch-and-Cut for Linear Programs with Overlapping SOS1 Constraints

Tobias Fischer(fischer***at***gsc.tu-darmstadt.de)
Marc E. Pfetsch(pfetsch***at***mathematik.tu-darmstadt.de)

Abstract: 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 mixed-integer programming formulation, if the variables appearing in SOS1 constraints are bounded.

Keywords: Complementarity constraints, Special ordered sets, Mixed-integer programming, Branch-and-cut, SOS1 branching, Bipartite branching

Category 1: Integer Programming

Citation: TU Darmstadt, Department of Mathematics, Research Group Optimization, Graduate School of Computational Engineering, Dolivostr. 15, 64293 Darmstadt, April 2015

Download: [PDF]

Entry Submitted: 04/01/2015
Entry Accepted: 04/01/2015
Entry Last Modified: 04/01/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society