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

Cardinality Constrained Combinatorial Optimization: Complexity and Polyhedra

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-11026
  • Given a combinatorial optimization problem and a subset $N$ of natural numbers, we obtain a cardinality constrained version of this problem by permitting only those feasible solutions whose cardinalities are elements of $N$. In this paper we briefly touch on questions that addresses common grounds and differences of the complexity of a combinatorial optimization problem and its cardinality constrained version. Afterwards we focus on polytopes associated with cardinality constrained combinatorial optimization problems. Given an integer programming formulation for a combinatorial optimization problem, by essentially adding Grötschel's cardinality forcing inequalities, we obtain an integer programming formulation for its cardinality restricted version. Since the cardinality forcing inequalities in their original form are mostly not facet defining for the associated polyhedra, we discuss possibilities to strengthen them.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Rüdiger Stephan
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:Cardinality Constraints; Cardinality Forcing Inequalities; Combinatorial Optimization; Matroids
MSC-Klassifikation:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Bxx Designs and configurations (For applications of design theory, see 94C30) / 05B35 Matroids, geometric lattices [See also 52B40, 90C27]
05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C38 Paths and cycles [See also 90B10]
52-XX CONVEX AND DISCRETE GEOMETRY / 52Bxx Polytopes and polyhedra / 52B40 Matroids (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) [See also 05B35, 52Cxx]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
Datum der Erstveröffentlichung:10.12.2008
Schriftenreihe (Bandnummer):ZIB-Report (08-48)
ISSN:1438-0064
ZIB-Reportnummer:08-48
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.