Skip to main content

Advertisement

SpringerLink
Log in

Relations between facets of low- and high-dimensional group problems

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aardal K., Weismantel R., Wolsey L.A.: Non-standard approaches to integer programming. Discret. Appl. Math. 123, 5–74 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  2. Aczél J.: Lectures on Functional Equations and their Applications. Academic Press, New York (1966)

    MATH  Google Scholar 

  3. Aráoz J., Evans L., Gomory R.E., Johnson E.L.: Cyclic groups and knapsack facets. Math. Program. 96, 377–408 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  4. 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)

  5. 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)

    Article  MathSciNet  Google Scholar 

  6. 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

  7. Dash S., Günlük O.: Valid inequalities based on simple mixed integer set. Math. Program. 106, 29–53 (2006)

    Article  Google Scholar 

  8. Dash S., Günlük O.: On the strength of gomory mixed integer cuts as group cuts. Math. Program. 115, 387–407 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  9. Dey, S.S.: Strong cutting planes for unstructured mixed integer programs using multiple constraints. Ph.D. thesis, Purdue University, West Lafayette (2007)

  10. 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)

  11. Dey S.S., Richard J.P.P.: Facets of the two-dimensional infinite group problems. Math. Oper. Res. 33, 140–166 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  12. 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)

    Article  MATH  MathSciNet  Google Scholar 

  13. Fischetti M., Saturni C.: Mixed integer cuts from cyclic groups. Math. Program. 109, 27–53 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  14. Gomory R.E.: Some polyhedra related to combinatorial problems. Linear Algebra Appl. 2, 341–375 (1969)

    Article  MathSciNet  Google Scholar 

  15. Gomory R.E., Johnson E.L.: Some continuous functions related to corner polyhedra, part I. Math. Program. 3, 23–85 (1972)

    Article  MATH  MathSciNet  Google Scholar 

  16. Gomory R.E., Johnson E.L.: Some continuous functions related to corner polyhedra, part II. Math. Program. 3, 359–389 (1972)

    Article  MATH  MathSciNet  Google Scholar 

  17. Gomory R.E., Johnson E.L.: T-space and cutting planes. Math. Program. 96, 341–375 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  18. Gomory R.E., Johnson E.L., Evans L.: Corner polyhedra and their connection with cutting planes. Math. Program. 96, 321–339 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  19. Johnson E.L.: On the group problem for mixed integer programming. Math. Program. Study 2, 137–179 (1974)

    Google Scholar 

  20. 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)

    Article  MATH  MathSciNet  Google Scholar 

  21. Marchand H., Martin A., Weismantel R., Wolsey L.A.: Cutting planes in integer and mixed integer programming. Discret. Appl. Math. 123, 397–446 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  22. 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)

    Article  MATH  MathSciNet  Google Scholar 

  23. 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)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Industrial Engineering, Purdue University, West Lafayette, IN, USA

    Santanu S. Dey & Jean-Philippe P. Richard

Authors
  1. Santanu S. Dey
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jean-Philippe P. Richard
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Santanu S. Dey.

Additional information

This research was supported by NSF Grant DMI-03-48611.

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-009-0303-8

Keywords

Mathematics Subject Classification (2000)

Search

Navigation