Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 5 von 65
Zurück zur Trefferliste

A Branch-And-Cut for the Maximum Feasible Subsystem Problem

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-8797
  • We present a branch-and-cut algorithm for the NP-hard maximum feasible subsystem problem: For a given infeasible linear inequality system, determine a feasible subsystem containing as many inequalities as possible. The complementary problem, where one has to remove as few inequalities as possible in order to render the system feasible, can be formulated as a set covering problem. The rows of this formulation correspond to irreducible infeasible subsystems, which can be exponentially many. The main issue of a branch-and-cut algorithm for MaxFS is to efficiently find such infeasible subsystems. We present three heuristics for the corresponding NP-hard separation problem and discuss further cutting planes. This paper contains an extensive computational study of our implementation on a variety of instances arising in a number of applications.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Marc PfetschORCiD
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:(IIS) maximum feasible subsystem problem; branch-and-cut; infeasible linear inequality system; irreducible infeasible subsystem; minimum IIS-cover
MSC-Klassifikation:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
Datum der Erstveröffentlichung:11.11.2005
Schriftenreihe (Bandnummer):ZIB-Report (05-46)
ZIB-Reportnummer:05-46
Verlagspublikation:Appeared in: SIAM J. Optimization 19 (2008) 21-38
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.