Abstract
One-dimensional infinite group problems have been extensively studied and have yielded strong cutting planes for mixed integer programs. Although numerical and theoretical studies suggest that group cuts can be significantly improved by considering higher-dimensional groups, there are no known facets for infinite group problems whose dimension is larger than two. In this paper, we introduce an operation that we call sequential-merge. We prove that the sequential-merge operator creates a very large family of facet-defining inequalities for high-dimensional infinite group problems using facet-defining inequalities of lower-dimensional group problems. Further, they exhibit two properties that reflect the benefits of using facets of high-dimensional group problems: they have continuous variables’ coefficients that are not dominated by those of the constituent low-dimensional cuts and they can produce cutting planes that do not belong to the first split closure of MIPs. Further, we introduce a general scheme for generating valid inequalities for lower-dimensional group problems using valid inequalities of higher-dimensional group problems. We present conditions under which this construction generates facet-defining inequalities when applied to sequential-merge inequalities. We show that this procedure yields some two-step MIR inequalities of Dash and Günlük.
Similar content being viewed by others
References
Aardal K., Weismantel R., Wolsey L.A.: Non-standard approaches to integer programming. Discret. Appl. Math. 123, 5–74 (2002)
Aczél J.: Lectures on Functional Equations and their Applications. Academic Press, New York (1966)
Aráoz J., Evans L., Gomory R.E., Johnson E.L.: Cyclic groups and knapsack facets. Math. Program. 96, 377–408 (2003)
Bixby, R.E., Fenelon, M., Gu, Z., Rothberg, E.E., Wunderling, R.: Mip: theory and practice—closing the gap. In: Powell, S., Scholtes M.J.D. (eds.) System Modelling and Optimization: Methods, Theory, and Applications, pp. 19–49. Kluwer Academic Publishers, Dordrecht (2000)
Bixby R.E., Rothberg E.E.: Progress in computational mixed integer programming—a look back from the other side of the tipping point. Ann. Oper. Res. 149, 37–41 (2007)
Dash, S., Goycoolea, M., Günlük, O.: Two step MIR inequalities for mixed integer programs. (2006) http://www.optimization-online.org/DB_HTML/2006/07/1422.html
Dash S., Günlük O.: Valid inequalities based on simple mixed integer set. Math. Program. 106, 29–53 (2006)
Dash S., Günlük O.: On the strength of gomory mixed integer cuts as group cuts. Math. Program. 115, 387–407 (2008)
Dey, S.S.: Strong cutting planes for unstructured mixed integer programs using multiple constraints. Ph.D. thesis, Purdue University, West Lafayette (2007)
Dey, S.S., Richard, J.P.P.: Sequential-merge facets for two-dimensional group problems. In: Fischetti, M., Williamson, D.P. (eds.) Proceedings 12th Conference on Integer and Combinatorial Optimization, pp. 30–42. Springer (2007)
Dey S.S., Richard J.P.P.: Facets of the two-dimensional infinite group problems. Math. Oper. Res. 33, 140–166 (2008)
Dey S.S., Richard J.P.P., Li Y., Miller L.A.: On the extreme inequalities of infinite group problems. Math. Program. 121, 145–170 (2010)
Fischetti M., Saturni C.: Mixed integer cuts from cyclic groups. Math. Program. 109, 27–53 (2007)
Gomory R.E.: Some polyhedra related to combinatorial problems. Linear Algebra Appl. 2, 341–375 (1969)
Gomory R.E., Johnson E.L.: Some continuous functions related to corner polyhedra, part I. Math. Program. 3, 23–85 (1972)
Gomory R.E., Johnson E.L.: Some continuous functions related to corner polyhedra, part II. Math. Program. 3, 359–389 (1972)
Gomory R.E., Johnson E.L.: T-space and cutting planes. Math. Program. 96, 341–375 (2003)
Gomory R.E., Johnson E.L., Evans L.: Corner polyhedra and their connection with cutting planes. Math. Program. 96, 321–339 (2003)
Johnson E.L.: On the group problem for mixed integer programming. Math. Program. Study 2, 137–179 (1974)
Johnson E.L., Nemhauser G.L., Savelsbergh M.W.P.: Progress in linear programming-based algorithms for integer programming: an exposition. INFORMS J. Comput. 12, 2–23 (2000)
Marchand H., Martin A., Weismantel R., Wolsey L.A.: Cutting planes in integer and mixed integer programming. Discret. Appl. Math. 123, 397–446 (2002)
Miller L.A., Li Y., Richard J.P.P.: New facets for finite and infinite group problems from approximate lifting. Nav. Res. Log. 55, 172–191 (2008)
Richard J.P.P., Li Y., Miller L.A.: Valid inequalities for MIPs and group polyhedra from approximate liftings. Math. Program. 118, 253–277 (2009)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was supported by NSF Grant DMI-03-48611.
Rights and permissions
About this article
Cite this article
Dey, S.S., Richard, JP.P. Relations between facets of low- and high-dimensional group problems. Math. Program. 123, 285–313 (2010). https://doi.org/10.1007/s10107-009-0303-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-009-0303-8
Keywords
- Mixed integer programming
- High-dimensional infinite group problem
- Facet-defining inequalities
- Cutting planes