Cette recherche s'applique uniquement aux ressources en bibliothèque.
84 résultats
Trier par:
Ajouter à la liste:
    • Plusieurs versions

    Convex polytopes

    Grünbaum, Branko
    • Article
    Sélectionner

    Extended Formulations in Combinatorial Optimization

    Kaibel, Volker
    arXiv.org, Apr 6, 2011
    © ProQuest LLC All rights reserved, Engineering Database, Publicly Available Content Database, ProQuest Engineering Collection, ProQuest Technology Collection, ProQuest SciTech Collection, Materials Science & Engineering Database, ProQuest Central (new), ProQuest Central Korea, SciTech Premium Collection, Technology Collection, ProQuest Central Essentials, ProQuest One Academic, Engineering Collection (ProQuest)
    Disponible
    Plus…
    Titre: Extended Formulations in Combinatorial Optimization
    Auteur: Kaibel, Volker
    Contributeur: Kaibel, Volker (pacrepositoryorg)
    Sujet: Newsletters ; Lower Bounds ; Combinatorial Analysis ; Optimization ; Formulations ; Combinatorics ; Optimization and Control
    Description: The concept of representing a polytope that is associated with some combinatorial optimization problem as a linear projection of a higher-dimensional polyhedron has recently received increasing attention. In this paper (written for the newsletter Optima of the Mathematical Optimization Society), we provide a brief introduction to this topic and sketch some of the recent developments with respect to both tools for constructing such extended formulations as well as lower bounds on their sizes.
    Fait partie de: arXiv.org, Apr 6, 2011
    Identifiant: 2331-8422 (E-ISSN)

    • Article
    Sélectionner

    Extended Formulations in Combinatorial Optimization

    Kaibel, Volker
    Cornell University
    Disponible
    Plus…
    Titre: Extended Formulations in Combinatorial Optimization
    Auteur: Kaibel, Volker
    Sujet: Mathematics - Combinatorics ; Mathematics - Optimization And Control ; 90c10, 90c57, 52b12
    Description: The concept of representing a polytope that is associated with some combinatorial optimization problem as a linear projection of a higher-dimensional polyhedron has recently received increasing attention. In this paper (written for the newsletter Optima of the Mathematical Optimization Society), we provide a brief introduction to this topic and sketch some of the recent developments with respect to both tools for constructing such extended formulations as well as lower bounds on their sizes. Comment: 14 pages, 1 figure; Optima 85, 2011
    Identifiant: 1104.1023 (ARXIV ID)

    • Article
    Sélectionner

    Lower bounds on the sizes of integer programs without additional variables

    Kaibel, Volker, Weltge, Stefan
    Mathematical Programming, 2015, Vol.154(1), pp.407-425 [Revue évaluée par les pairs]
    Springer Science & Business Media B.V.
    Disponible
    Plus…
    Titre: Lower bounds on the sizes of integer programs without additional variables
    Auteur: Kaibel, Volker; Weltge, Stefan
    Sujet: Integer programming ; Relaxations ; Auxiliary variables ; TSP
    Description: Let $$ X $$ X be the set of integer points in some polyhedron. We investigate the smallest number of facets of any polyhedron whose set of integer points is $$ X $$ X . This quantity, which we call the relaxation complexity of $$ X $$ X , corresponds to the smallest number of linear inequalities of any integer program having $$ X $$ X as the set of feasible solutions that does not use auxiliary variables. We show that the use of auxiliary variables is essential for constructing polynomial size integer programming formulations in many relevant cases. In particular, we provide asymptotically tight exponential lower bounds on the relaxation complexity of the integer points of several well-known combinatorial polytopes, including the traveling salesman polytope and the spanning tree polytope. In addition to the material in the extended abstract Kaibel and Weltge (2014) we include omitted proofs, supporting figures, discussions about properties of coefficients in such formulations, and facts about the complexity of formulations in more general settings.
    Fait partie de: Mathematical Programming, 2015, Vol.154(1), pp.407-425
    Identifiant: 0025-5610 (ISSN); 1436-4646 (E-ISSN); 10.1007/s10107-014-0855-0 (DOI)

    • Plusieurs versions

    A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially

    Kaibel, Volker, Weltge, Stefan
    Discrete & Computational Geometry, 2015, Vol.53(2), pp.397-401 [Revue évaluée par les pairs]

    • Article
    Sélectionner

    Simple extensions of polytopes

    Kaibel, Volker, Walter, Matthias
    Mathematical Programming, 2015, Vol.154(1), pp.381-406 [Revue évaluée par les pairs]
    Springer Science & Business Media B.V.
    Disponible
    Plus…
    Titre: Simple extensions of polytopes
    Auteur: Kaibel, Volker; Walter, Matthias
    Sujet: Extended formulations ; Simple polytopes ; Matching polytopes ; Flow polytopes ; Spanning tree polytopes
    Description: We introduce the simple extension complexity of a polytope $$P$$ P as the smallest number of facets of any simple (i.e., non-degenerate in the sense of linear programming) polytope which can be projected onto $$P$$ P . We devise a combinatorial method to establish lower bounds on the simple extension complexity and show for several polytopes that they have large simple extension complexities. These examples include both the spanning tree and the perfect matching polytopes of complete graphs, uncapacitated flow polytopes for non-trivially decomposable directed acyclic graphs, hypersimplices, and random 0/1-polytopes with vertex numbers within a certain range. On our way to obtain the result on perfect matching polytopes we generalize a result of Padberg and Rao’s on the adjacency structures of those polytopes. In addition to the material in the extended abstract (Kaibel and Walter in Integer programming and combinatorial optimization. Lecture Notes in Computer Science, vol 8494. Springer, Berlin, 2014) we include omitted proofs, supporting figures, and an analysis of known upper bounding techniques.
    Fait partie de: Mathematical Programming, 2015, Vol.154(1), pp.381-406
    Identifiant: 0025-5610 (ISSN); 1436-4646 (E-ISSN); 10.1007/s10107-015-0885-2 (DOI)

    • Article
    Sélectionner

    Basic Polyhedral Theory

    Kaibel, Volker
    arXiv.org, Jan 13, 2010
    © ProQuest LLC All rights reserved, Engineering Database, Publicly Available Content Database, ProQuest Engineering Collection, ProQuest Technology Collection, ProQuest SciTech Collection, Materials Science & Engineering Database, ProQuest Central (new), ProQuest Central Korea, SciTech Premium Collection, Technology Collection, ProQuest Central Essentials, ProQuest One Academic, Engineering Collection (ProQuest)
    Disponible
    Plus…
    Titre: Basic Polyhedral Theory
    Auteur: Kaibel, Volker
    Contributeur: Kaibel, Volker (pacrepositoryorg)
    Sujet: Cones ; Operations Research ; Optimization ; Encyclopedias ; Polyhedra ; Combinatorics ; Optimization and Control
    Description: This is a chapter (planned to appear in Wiley's upcoming Encyclopedia of Operations Research and Management Science) describing parts of the theory of convex polyhedra that are particularly important for optimization. The topics include polyhedral and finitely generated cones, the Weyl-Minkowski Theorem, faces of polyhedra, projections of polyhedra, integral polyhedra, total dual integrality, and total unimodularity.
    Fait partie de: arXiv.org, Jan 13, 2010
    Identifiant: 2331-8422 (E-ISSN)

    • Article
    Sélectionner

    Basic Polyhedral Theory

    Kaibel, Volker
    Cornell University
    Disponible
    Plus…
    Titre: Basic Polyhedral Theory
    Auteur: Kaibel, Volker
    Sujet: Mathematics - Combinatorics ; Mathematics - Optimization And Control ; 90c10 ; 90c57 ; 52b12
    Description: This is a chapter (planned to appear in Wiley's upcoming Encyclopedia of Operations Research and Management Science) describing parts of the theory of convex polyhedra that are particularly important for optimization. The topics include polyhedral and finitely generated cones, the Weyl-Minkowski Theorem, faces of polyhedra, projections of polyhedra, integral polyhedra, total dual integrality, and total unimodularity. Comment: 14 pages
    Identifiant: 1001.2161 (ARXIV ID)

    • Article
    Sélectionner

    Neue Bücher aus Oberwolfach

    Kaibel, Volker
    Mitteilungen der Deutschen Mathematiker-Vereinigung, 2010, Vol.18(3), pp.136-136
    Walter de Gruyter GmbH
    Disponible
    Plus…
    Titre: Neue Bücher aus Oberwolfach
    Auteur: Kaibel, Volker
    Editeur: De Gruyter
    Fait partie de: Mitteilungen der Deutschen Mathematiker-Vereinigung, 2010, Vol.18(3), pp.136-136
    Identifiant: 0947-4471 (ISSN); 0942-5977 (E-ISSN); 10.1515/dmvm-2010-0053 (DOI)

    • Article
    Sélectionner

    Finding Descriptions of Polytopes via Extended Formulations and Liftings

    Kaibel, Volker, Loos, Andreas
    Cornell University
    Disponible
    Plus…
    Titre: Finding Descriptions of Polytopes via Extended Formulations and Liftings
    Auteur: Kaibel, Volker; Loos, Andreas
    Sujet: Mathematics - Combinatorics ; Mathematics - Optimization And Control ; 90c10, 90c57, 52b12
    Description: We describe a technique to obtain linear descriptions for polytopes from extended formulations. The simple idea is to first define a suitable lifting function and then to find linear constraints that are valid for the polytope and guarantee lifted points to be contained in the extension. We explain the technique at an example from the literature (matching polytopes), obtain new simple proofs of results on path-set polytopes and small-cliques polytopes, and finally exploit the technique in order to derive linear descriptions of orbisacks, which are special Knapsack polytopes arising in the context of symmetry breaking in integer programming problems. Comment: 20 pages, 2 figures
    Identifiant: 1109.0815 (ARXIV ID)