The Structure of the Infinite Models in Integer Programming

The infinite models in integer programming can be described as the convex hull of some points or as the intersection of halfspaces derived from valid functions. In this paper, we study the relationships between these two descriptions. Our results have implications for corner polyhedra. One consequen...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics of operations research 2019-11, Vol.44 (4), p.1412-1430
Main Authors: Basu, Amitabh, Conforti, Michele, Di Summa, Marco, Paat, Joseph
Format: Article
Language:English
Subjects:
Continuity (mathematics)
Convex analysis
Convexity
cut-generating functions
Gomory–Johnson infinite relaxation
Hulls
Integer programming
Integers
Mathematical functions
Mathematical models
Operations research
Polyhedra
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The infinite models in integer programming can be described as the convex hull of some points or as the intersection of halfspaces derived from valid functions. In this paper, we study the relationships between these two descriptions. Our results have implications for corner polyhedra. One consequence is that nonnegative, continuous valid functions suffice to describe corner polyhedra (with or without rational data).
ISSN:0364-765X
1526-5471
DOI:10.1287/moor.2018.0977