Mathematics of Operations Research Vol. 40, No. 2, May 2015, pp. 276–301
en_US
Identifier
dc.identifier.other
DOI: 10.1287/moor.2014.0670
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/132902
General note
dc.description
Artículo de publicación ISI
en_US
Abstract
dc.description.abstract
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 into perspective a number of existing works on S-free sets; in particular, we show how CGF's recover the celebrated Gomory cuts.