Abstract
Recently, Andersen et al. [1] and Borozan and Cornuéjols [3] characterized the minimal inequalities of a system of two rows with two free integer variables and nonnegative continuous variables. These inequalities are either split cuts or intersection cuts derived using maximal lattice-free convex sets. In order to use these minimal inequalities to obtain cuts from two rows of a general simplex tableau, it is necessary to extend the system to include integer variables (giving the two-dimensional mixed integer infinite group problem), and to develop lifting functions giving the coefficients of the integer variables in the corresponding inequalities. In this paper, we analyze the lifting of minimal inequalities derived from lattice-free triangles.
Maximal lattice-free triangles in ℝ2 can be classified into three categories: those with multiple integral points in the relative interior of one of its sides, those with integral vertices and one integral point in the relative interior of each side, and those with non integral vertices and one integral point in the relative interior of each side. We prove that the lifting functions are unique for each of the first two categories such that the resultant inequality is minimal for the mixed integer infinite group problem, and characterize them. We show that the lifting function is not necessarily unique in the third category. For this category we show that a fill-in inequality (Johnson [11]) yields minimal inequalities for mixed integer infinite group problem under certain sufficiency conditions. Finally, we present conditions for the fill-in inequality to be extreme.
This text presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister’s Office, Science Policy Programming. The scientific responsibility is assumed by the authors.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Andersen, K., Louveaux, Q., Weismantel, R., Wolsey, L.: Cutting planes from two rows of a simplex tableau. In: Fischetti, M., Williamson, D.P. (eds.) Proceedings 12th Conference on Integer and Combinatorial Optimization, pp. 30–42. Springer, Heidelberg (2007)
Balas, E.: Intersection cuts - a new type of cutting planes for integer programming. Operations Research 19, 19–39 (1971)
Borozan, V., Cornuéjols, G.: Minimal inequalities for integer constraints (2007), http://integer.tepper.cmu.edu
Cook, W.J., Kannan, R., Schrijver, A.: Chvátal closures for mixed integer programming problems. Mathematical Programming 58, 155–174 (1990)
Cornuéjols, G., Margot, F.: On the facets of mixed integer programs with two integer variables and two constraints (2007), http://wpweb2.tepper.cmu.edu/fmargot/rec_pub.html
Gomory, R.E.: Some polyhedra related to combinatorial problems. Linear Algebra and Applications 2, 341–375 (1969)
Gomory, R.E., Johnson, E.L.: Some continuous functions related to corner polyhedra, part I. Mathematical Programming 3, 23–85 (1972)
Gomory, R.E., Johnson, E.L.: Some continuous functions related to corner polyhedra, part II. Mathematical Programming 3, 359–389 (1972)
Gomory, R.E., Johnson, E.L.: T-space and cutting planes. Mathematical Programming 96, 341–375 (2003)
Gomory, R.E., Johnson, E.L., Evans, L.: Corner polyhedra and their connection with cutting planes. Mathematical Programming 96, 321–339 (2003)
Johnson, E.L.: On the group problem for mixed integer programming. Mathematical Programming Study 2, 137–179 (1974)
Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley-Interscience, New York (1988)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dey, S.S., Wolsey, L.A. (2008). Lifting Integer Variables in Minimal Inequalities Corresponding to Lattice-Free Triangles. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds) Integer Programming and Combinatorial Optimization. IPCO 2008. Lecture Notes in Computer Science, vol 5035. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-68891-4_32
Download citation
DOI: https://doi.org/10.1007/978-3-540-68891-4_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-68886-0
Online ISBN: 978-3-540-68891-4
eBook Packages: Computer ScienceComputer Science (R0)