Cette recherche s'applique uniquement aux ressources en bibliothèque.
154 résultats
Trier par:
Ajouter à la liste:
Étendre à toutes les références (sans texte intégral)
    • Article
    Sélectionner

    Disjunctive programming and relaxations of polyhedra

    Conforti, Michele
    Del Pia, Alberto
    Mathematical Programming. - 2014/144/1-2/307-314
    Disponible
    Plus…
    Titre: Disjunctive programming and relaxations of polyhedra
    Auteur: Conforti, Michele
    Contributeur: Del Pia, Alberto
    Sujet: Mixed integer programming - Disjunctive programming - Polyhedral relaxations
    Description: Given a polyhedron $$L$$ with $$h$$ facets, whose interior contains no integral points, and a polyhedron $$P$$ , recent work in integer programming has focused on characterizing the convex hull of $$P$$ minus the interior of $$L$$ . We show that to obtain such a characterization it suffices to consider all relaxations of $$P$$ defined by at most $$n(h-1)$$ among the inequalities defining $$P$$ . This extends a result by Andersen, Cornuéjols, and Li.
    Publication en relation: Mathematical Programming. - 2014/144/1-2/307-314
    Document hôte: Mathematical Programming
    Identifiant: 10.1007/s10107-013-0634-3 (DOI)

    • Plusieurs versions

    A geometric approach to cut-generating functions

    Basu, Amitabh, Conforti, Michele, Di Summa, Marco
    Mathematical Programming, 2015, Vol.151(1), pp.153-189 [Revue évaluée par les pairs]

    • Plusieurs versions

    The projected faces property and polyhedral relations

    Conforti, Michele, Pashkovich, Kanstantsin
    Mathematical Programming, 2016, Vol.156(1), pp.331-342 [Revue évaluée par les pairs]

    • Article
    Sélectionner

    Maximal $S$-Free Convex Sets and the Helly Number

    Conforti, Michele, Summa, Marco Di
    SIAM Journal on Discrete Mathematics, 2016, Vol.30(4), pp.2206-2216 [Revue évaluée par les pairs]
    SIAM Journals (Society for Industrial and Applied Mathematics), Copyright �� by the Society of Industrial and Applied Mathematics, Philadelphia, PA
    Disponible
    Plus…
    Titre: Maximal $S$-Free Convex Sets and the Helly Number
    Auteur: Conforti, Michele; Summa, Marco Di
    Sujet: $S$-Free Convex Sets ; Helly Number ; Cut-Generating Functions ; 52c07 ; 90c10
    Description: Given a subset $S$ of $\mathbb{R}^d$, the Helly number $h(S)$ is the largest size of an inclusionwise minimal family of convex sets whose intersection is disjoint from $S$. A convex set is $S$-free if its interior contains no point of $S$. The parameter $f(S)$ is the largest number of maximal faces in an inclusionwise maximal $S$-free convex set. We study the relation between the parameters $h(S)$ and $f(S)$. Our main result is that $h(S)\le (d+1)f(S)$ for every nonempty proper closed subset $S$ of $\mathbb{R}^d$. We also study the Helly number of the Cartesian product of two discrete sets.
    Fait partie de: SIAM Journal on Discrete Mathematics, 2016, Vol.30(4), pp.2206-2216
    Identifiant: 0895-4801 (ISSN); 1095-7146 (E-ISSN); 10.1137/16M1063484 (DOI)

    • Plusieurs versions

    Disjunctive programming and relaxations of polyhedra

    Conforti, Michele, Del Pia, Alberto
    Mathematical Programming, 2014, Vol.144(1), pp.307-314 [Revue évaluée par les pairs]

    • Article
    Sélectionner

    The Projected Faces Property and Polyhedral Relations

    Conforti, Michele, Pashkovich, Kanstantsin
    Cornell University
    Disponible
    Plus…
    Titre: The Projected Faces Property and Polyhedral Relations
    Auteur: Conforti, Michele; Pashkovich, Kanstantsin
    Sujet: Mathematics - Combinatorics
    Description: Margot (1994) in his doctoral dissertation studied extended formulations of combinatorial polytopes that arise from "smaller" polytopes via some composition rule. He introduced the "projected faces property" of a polytope and showed that this property suffices to iteratively build extended formulations of composed polytopes. For the composed polytopes, we show that an extended formulation of the type studied in this paper is always possible only if the smaller polytopes have the projected faces property. Therefore, this produces a characterization of the projected faces property. Affinely generated polyhedral relations were introduced by Kaibel and Pashkovich (2011) to construct extended formulations for the convex hull of the images of a point under the action of some finite group of reflections. In this paper we prove that the projected faces property and affinely generated polyhedral relation are equivalent conditions.
    Identifiant: 1305.3782 (ARXIV ID)

    • Article
    Sélectionner

    The Projected Faces Property and Polyhedral Relations

    Conforti, Michele, Pashkovich, Kanstantsin
    arXiv.org, Oct 10, 2014
    © 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: The Projected Faces Property and Polyhedral Relations
    Auteur: Conforti, Michele; Pashkovich, Kanstantsin
    Contributeur: Pashkovich, Kanstantsin (pacrepositoryorg)
    Sujet: Hulls (Structures) ; Polytopes ; Combinatorial Analysis ; Convexity ; Formulations
    Description: Margot (1994) in his doctoral dissertation studied extended formulations of combinatorial polytopes that arise from "smaller" polytopes via some composition rule. He introduced the "projected faces property" of a polytope and showed that this property suffices to iteratively build extended formulations of composed polytopes. For the composed polytopes, we show that an extended formulation of the type studied in this paper is always possible only if the smaller polytopes have the projected faces property. Therefore, this produces a characterization of the projected faces property. Affinely generated polyhedral relations were introduced by Kaibel and Pashkovich (2011) to construct extended formulations for the convex hull of the images of a point under the action of some finite group of reflections. In this paper we prove that the projected faces property and affinely generated polyhedral relation are equivalent conditions.
    Fait partie de: arXiv.org, Oct 10, 2014
    Identifiant: 2331-8422 (E-ISSN)

    • Article
    Sélectionner

    An extreme function which is nonnegative and discontinuous everywhere

    Basu, Amitabh, Conforti, Michele
    arXiv.org, Feb 5, 2018
    © 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: An extreme function which is nonnegative and discontinuous everywhere
    Auteur: Basu, Amitabh; Conforti, Michele
    Contributeur: Conforti, Michele (pacrepositoryorg)
    Sujet: Mathematical Models ; Optimization and Control ; Functional Analysis
    Description: We consider Gomory and Johnson's infinite group model with a single row. Valid inequalities for this model are expressed by valid functions and it has been recently shown that any valid function is dominated by some nonnegative valid function, modulo the affine hull of the model. Within the set of nonnegative valid functions, extreme functions are the ones that cannot be expressed as convex combinations of two distinct valid functions. In this paper we construct an extreme function \(\pi:\mathbb{R} \to [0,1]\) whose graph is dense in \(\mathbb{R} \times [0,1]\). Therefore, \(\pi\) is discontinuous everywhere.
    Fait partie de: arXiv.org, Feb 5, 2018
    Identifiant: 2331-8422 (E-ISSN)

    • Article
    Sélectionner

    Balas formulation for the union of polytopes is optimal

    Conforti, Michele, Faenza, Yuri
    arXiv.org, Nov 2, 2017
    © 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: Balas formulation for the union of polytopes is optimal
    Auteur: Conforti, Michele; Faenza, Yuri
    Contributeur: Faenza, Yuri (pacrepositoryorg)
    Sujet: Hulls (Structures) ; Polytopes ; Inequalities ; Convexity ; Polynomials
    Description: A celebrated theorem of Balas gives a linear mixed-integer formulation for the union of two nonempty polytopes whose relaxation gives the convex hull of this union. The number of inequalities in Balas formulation is linear in the number of inequalities that describe the two polytopes and the number of variables is doubled. In this paper we show that this is best possible: in every dimension there exist two nonempty polytopes such that if a formulation for the convex hull of their union has a number of inequalities that is polynomial in the number of inequalities that describe the two polytopes, then the number of additional variables is at least linear in the dimension of the polytopes. We then show that this result essentially carries over if one wants to approximate the convex hull of the union of two polytopes and also in the more restrictive setting of lift-and-project.
    Fait partie de: arXiv.org, Nov 2, 2017
    Identifiant: 2331-8422 (E-ISSN)

    • Article
    Sélectionner

    Reverse Split Rank

    Conforti, Michele, Faenza, Yuri
    arXiv.org, Oct 12, 2014
    © 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: Reverse Split Rank
    Auteur: Conforti, Michele; Faenza, Yuri
    Contributeur: Faenza, Yuri (pacrepositoryorg)
    Sujet: Stock Splits ; Stock Market Delistings ; Polyhedra ; Polyhedrons ; Integrals ; Optimization and Control ; Discrete Mathematics
    Description: The reverse split rank of an integral polyhedron P is defined as the supremum of the split ranks of all rational polyhedra whose integer hull is P. Already in R^3 there exist polyhedra with infinite reverse split rank. We give a geometric characterization of the integral polyhedra in R^n with infinite reverse split rank.
    Fait partie de: arXiv.org, Oct 12, 2014
    Identifiant: 2331-8422 (E-ISSN)