TU Darmstadt / ULB / TUbiblio

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

Fischer, Tobias and Pfetsch, Marc E. (2018):
Branch-and-cut for linear programs with overlapping SOS1 constraints.
In: Mathematical Programming Computation, pp. 33-68, 10, (1), ISSN 1867-2957,
DOI: 10.1007/s12532-017-0122-5,
[Online-Edition: https://doi.org/10.1007/s12532-017-0122-5],
[Article]

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 ar bounded.

Item Type: Article
Erschienen: 2018
Creators: Fischer, Tobias and Pfetsch, Marc E.
Title: Branch-and-cut for linear programs with overlapping SOS1 constraints
Language: English
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 ar bounded.

Journal or Publication Title: Mathematical Programming Computation
Volume: 10
Number: 1
Divisions: Exzellenzinitiative
Exzellenzinitiative > Graduate Schools
Exzellenzinitiative > Graduate Schools > Graduate School of Computational Engineering (CE)
04 Department of Mathematics
04 Department of Mathematics > Optimization
04 Department of Mathematics > Optimization > Discrete Optimization
Date Deposited: 19 Sep 2019 11:36
DOI: 10.1007/s12532-017-0122-5
Official URL: https://doi.org/10.1007/s12532-017-0122-5
Export:
Suche nach Titel in: TUfind oder in Google

Optionen (nur für Redakteure)

View Item View Item