On the polyhedrality of cross and quadrilateral closures

Split cuts form a well-known class of valid inequalities for mixed-integer programming problems. Cook et al. (Math Program 47:155–174, 1990 ) showed that the split closure of a rational polyhedron P is again a polyhedron. In this paper, we extend this result from a single rational polyhedron to the...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2016-11, Vol.160 (1-2), p.245-270
Main Authors: Dash, Sanjeeb, Günlük, Oktay, Morán R., Diego A.
Format: Article
Language:English
Subjects:
Calculus of Variations and Optimal Control
Optimization
Closures
Combinatorics
Full Length Paper
Inequalities
Integer programming
Mathematical analysis
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematics
Mathematics and Statistics
Mathematics of Computing
Numerical Analysis
Polyhedra
Polyhedrons
Programming
Quadrilaterals
Studies
Theoretical
Unions
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Split cuts form a well-known class of valid inequalities for mixed-integer programming problems. Cook et al. (Math Program 47:155–174, 1990 ) showed that the split closure of a rational polyhedron P is again a polyhedron. In this paper, we extend this result from a single rational polyhedron to the union of a finite number of rational polyhedra. We then use this result to prove that cross cuts yield closures that are rational polyhedra. Cross cuts are a generalization of split cuts introduced by Dash et al. (Math Program 135:221–254, 2012 ). Finally, we show that the quadrilateral closure of the two-row continuous group relaxation is a polyhedron, answering an open question in Basu et al. (Math Program 126:281–314, 2011 ).
ISSN:0025-5610
1436-4646
DOI:10.1007/s10107-016-0982-x