TU Darmstadt / ULB / TUbiblio

On the Structure of Linear Programs with Overlapping Cardinality Constraints

Fischer, Tobias ; Pfetsch, Marc E. (2017)
On the Structure of Linear Programs with Overlapping Cardinality Constraints.
Report, Bibliographie

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.

Item Type: Report
Erschienen: 2017
Creators: Fischer, Tobias ; Pfetsch, Marc E.
Type of entry: Bibliographie
Title: On the Structure of Linear Programs with Overlapping Cardinality Constraints
Language: English
Date: 25 January 2017
Publisher: Optimization Online
URL / URN: http://www.optimization-online.org/DB_HTML/2017/01/5833.html
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.

Divisions: Exzellenzinitiative
Exzellenzinitiative > Graduate Schools
Exzellenzinitiative > Graduate Schools > Graduate School of Computational Engineering (CE)
04 Department of Mathematics
04 Department of Mathematics > Optimization
Date Deposited: 26 Jan 2017 12:57
Last Modified: 15 Aug 2023 11:14
PPN:
Export:
Suche nach Titel in: TUfind oder in Google
Send an inquiry Send an inquiry

Options (only for editors)
Show editorial Details Show editorial Details