Fischer, Tobias ; Pfetsch, Marc E. (2018)
Branch-and-cut for linear programs with overlapping SOS1 constraints.
In: Mathematical Programming Computation, 10 (1)
doi: 10.1007/s12532-017-0122-5
Artikel, Bibliographie
Kurzbeschreibung (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.
| Typ des Eintrags: | Artikel |
|---|---|
| Erschienen: | 2018 |
| Autor(en): | Fischer, Tobias ; Pfetsch, Marc E. |
| Art des Eintrags: | Bibliographie |
| Titel: | Branch-and-cut for linear programs with overlapping SOS1 constraints |
| Sprache: | Englisch |
| Publikationsjahr: | März 2018 |
| Titel der Zeitschrift, Zeitung oder Schriftenreihe: | Mathematical Programming Computation |
| Jahrgang/Volume einer Zeitschrift: | 10 |
| (Heft-)Nummer: | 1 |
| DOI: | 10.1007/s12532-017-0122-5 |
| URL / URN: | https://doi.org/10.1007/s12532-017-0122-5 |
| Kurzbeschreibung (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. |
| Fachbereich(e)/-gebiet(e): | Exzellenzinitiative Exzellenzinitiative > Graduiertenschulen Exzellenzinitiative > Graduiertenschulen > Graduate School of Computational Engineering (CE) 04 Fachbereich Mathematik 04 Fachbereich Mathematik > Optimierung 04 Fachbereich Mathematik > Optimierung > Discrete Optimization |
| Hinterlegungsdatum: | 19 Sep 2019 11:36 |
| Letzte Änderung: | 19 Sep 2019 11:36 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum