Fischer, Tobias ; Pfetsch, Marc E. (2017)
On the Structure of Linear Programs with Overlapping Cardinality Constraints.
Report, Bibliographie
Kurzbeschreibung (Abstract)
Cardinality constraints enforce an upper bound on the number of variables that can be nonzero. This article investigates linear programs with cardinality constraints that mutually overlap, i.e., share variables. We present the components of a branch-and-cut solution approach, including new branching rules that exploit the structure of the corresponding conflict hypergraph. We also investigate valid or facet defining cutting planes for the convex hull of the feasible solution set. Our approach can be seen as a continuous analogue of independence system polytopes. We study three different classes of cutting planes: hyperclique bound cuts, implied bound cuts, and flow cover cuts. In a computational study, we examine the effectiveness of an implementation based on the presented concepts.
| Typ des Eintrags: | Report |
|---|---|
| Erschienen: | 2017 |
| Autor(en): | Fischer, Tobias ; Pfetsch, Marc E. |
| Art des Eintrags: | Bibliographie |
| Titel: | On the Structure of Linear Programs with Overlapping Cardinality Constraints |
| Sprache: | Englisch |
| Publikationsjahr: | 25 Januar 2017 |
| Verlag: | Optimization Online |
| URL / URN: | http://www.optimization-online.org/DB_HTML/2017/01/5833.html |
| Kurzbeschreibung (Abstract): | Cardinality constraints enforce an upper bound on the number of variables that can be nonzero. This article investigates linear programs with cardinality constraints that mutually overlap, i.e., share variables. We present the components of a branch-and-cut solution approach, including new branching rules that exploit the structure of the corresponding conflict hypergraph. We also investigate valid or facet defining cutting planes for the convex hull of the feasible solution set. Our approach can be seen as a continuous analogue of independence system polytopes. We study three different classes of cutting planes: hyperclique bound cuts, implied bound cuts, and flow cover cuts. In a computational study, we examine the effectiveness of an implementation based on the presented concepts. |
| Fachbereich(e)/-gebiet(e): | Exzellenzinitiative Exzellenzinitiative > Graduiertenschulen Exzellenzinitiative > Graduiertenschulen > Graduate School of Computational Engineering (CE) 04 Fachbereich Mathematik 04 Fachbereich Mathematik > Optimierung |
| Hinterlegungsdatum: | 26 Jan 2017 12:57 |
| Letzte Änderung: | 15 Aug 2023 11:14 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum