Optimization Online


Operations that preserve the covering property of the lifting region

Amitabh Basu (basu.amitabh***at***jhu.edu)
Joe Paat (jpaat1***at***jhu.edu)

Abstract: We contribute to the theory for minimal liftings of cut-generating functions. In particular, we give three operations that preserve the so-called covering property of certain structured cut-generating functions. This has the consequence of vastly expanding the set of undominated cut generating functions which can be used computationally, compared to known examples from the literature. The results of this paper are not only significant generalizations of previous results from the literature on such operations, but also use completely different proof techniques which we feel are more suitable for attacking future research questions in this area. Finally, we complete the classification of two dimensional $S$-free convex sets when $S$ is the intersection of a translated lattice and a polyhedron, thus settling the covering question in two dimensions for such $S$.

Keywords: cutting planes; cut generating functions; integer lifting; unique minimal lifting

Category 1: Integer Programming (Cutting Plane Approaches )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )


Download: [PDF]

Entry Submitted: 10/06/2014
Entry Accepted: 10/06/2014
Entry Last Modified: 07/02/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society