Cut-generating functions and S-free sets
Type de document :
Compte-rendu et recension critique d'ouvrage
DOI :
Titre :
Cut-generating functions and S-free sets
Auteur(s) :
Conforti, Michele [Auteur]
Laboratoire de Physique des Lasers, Atomes et Molécules - UMR 8523 [PhLAM]
Cornuéjols, Gérard [Auteur]
Tepper School of Business
Daniilidis, Aris [Auteur]
Departament de Matemàtiques [Barcelona] [UAB]
Lemaréchal, Claude [Auteur]
Modelling, Simulation, Control and Optimization of Non-Smooth Dynamical Systems [BIPOP]
Malick, Jérôme [Auteur]
Modelling, Simulation, Control and Optimization of Non-Smooth Dynamical Systems [BIPOP]
Laboratoire de Physique des Lasers, Atomes et Molécules - UMR 8523 [PhLAM]
Cornuéjols, Gérard [Auteur]
Tepper School of Business
Daniilidis, Aris [Auteur]
Departament de Matemàtiques [Barcelona] [UAB]
Lemaréchal, Claude [Auteur]
Modelling, Simulation, Control and Optimization of Non-Smooth Dynamical Systems [BIPOP]
Malick, Jérôme [Auteur]
Modelling, Simulation, Control and Optimization of Non-Smooth Dynamical Systems [BIPOP]
Titre de la revue :
Mathematics of Operations Research
Pagination :
276 - 391
Éditeur :
INFORMS
Date de publication :
2014-08
ISSN :
0364-765X
Mot(s)-clé(s) en anglais :
Integer programming
Convex analysis
Separation
Generalized gauges
S-free sets
Convex analysis
Separation
Generalized gauges
S-free sets
Discipline(s) HAL :
Mathématiques [math]/Optimisation et contrôle [math.OC]
Computer Science [cs]/Operations Research [math.OC]
Informatique [cs]/Mathématique discrète [cs.DM]
Mathématiques [math]/Analyse numérique [math.NA]
Computer Science [cs]/Operations Research [math.OC]
Informatique [cs]/Mathématique discrète [cs.DM]
Mathématiques [math]/Analyse numérique [math.NA]
Résumé en anglais : [en]
We consider the separation problem for sets X that are pre-images of a given set S by a linear mapping. Classical examples occur in integer programming, as well as in other optimization problems such as complementarity. ...
Lire la suite >We consider the separation problem for sets X that are pre-images of a given set S by a linear mapping. Classical examples occur in integer programming, as well as in other optimization problems such as complementarity. One would like to generate valid inequalities that cut off some point not lying in X, without reference to the linear mapping. To this aim, we introduce a concept: cut-generating functions (cgf) and we develop a formal theory for them, largely based on convex analysis. They are intimately related to S-free sets and we study this relation, disclosing several definitions for minimal cgf's and maximal S-free sets. Our work unifies and puts in perspective a number of existing works on S-free sets; in particular, we show how cgf's recover the celebrated Gomory cuts.Lire moins >
Lire la suite >We consider the separation problem for sets X that are pre-images of a given set S by a linear mapping. Classical examples occur in integer programming, as well as in other optimization problems such as complementarity. One would like to generate valid inequalities that cut off some point not lying in X, without reference to the linear mapping. To this aim, we introduce a concept: cut-generating functions (cgf) and we develop a formal theory for them, largely based on convex analysis. They are intimately related to S-free sets and we study this relation, disclosing several definitions for minimal cgf's and maximal S-free sets. Our work unifies and puts in perspective a number of existing works on S-free sets; in particular, we show how cgf's recover the celebrated Gomory cuts.Lire moins >
Langue :
Anglais
Vulgarisation :
Non
Source :
Fichiers
- https://hal.archives-ouvertes.fr/hal-01123860/document
- Accès libre
- Accéder au document
- http://integer.tepper.cmu.edu/webpub/taskforce.pdf
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-01123860/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-01123860/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- cut-generating-functions.pdf
- Accès libre
- Accéder au document
- taskforce.pdf
- Accès libre
- Accéder au document