On a Generalization of the Master Cyclic Group Polyhedron | SpringerLink
Skip to main content
Springer Nature Link
Log in

On a Generalization of the Master Cyclic Group Polyhedron

  • Conference paper
Integer Programming and Combinatorial Optimization (IPCO 2007)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4513))

Abstract

We study the Master Equality Polyhedron (MEP) which generalizes the Master Cyclic Group Polyhedron and the Master Knapsack Polyhedron.

We present an explicit characterization of the nontrivial facet-defining inequalities for MEP. This result generalizes similar results for the Master Cyclic Group Polyhedron by Gomory [9] and for the Master Knapsack Polyhedron by Araoz [1]. Furthermore, this characterization also gives a polynomial time algorithm for separating an arbitrary point from the MEP.

We describe how facet defining inequalities for the Master Cyclic Group Polyhedron can be lifted to obtain facet defining inequalities for the MEP, and also present facet defining inequalities for the MEP that cannot be obtained in such a way. Finally, we study the mixed-integer extension of the MEP and present an interpolation theorem that produces valid inequalities for general Mixed Integer Programming Problems using facets of the MEP.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Araoz, J.: Polyhedral Neopolarities. Phd thesis, University of Waterloo, Department of Computer Sciences (1974)

    Google Scholar 

  2. Araoz, J., Evans, L., Gomory, R.E., Johnson, E.: Cyclic group and knapsack facets. Mathematical Programming Ser. B 96(2), 377–408 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  3. Balas, E., Zemel, E.: Facets of the knapsack polytope from minimal covers. SIAM Journal of Applied Mathematics 34, 119–148 (1978)

    Article  MATH  MathSciNet  Google Scholar 

  4. Dash, S., Günlük, O.: On the strength of gomory mixed-integer cuts as group cuts. Technical Report RC23967, IBM Research Division, Yorktown Heights, NY (2006)

    Google Scholar 

  5. Dash, S., Günlük, O.: Valid inequalities based on simple mixed-integer sets. Mathematical Programming 105, 29–53 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  6. Dash, S., Günlük, O.: Valid inequalities based on the interpolation procedure. Mathematical Programming 106, 111–136 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  7. Fischetti, M., Monaci, M.: How tight is the corner relaxation? Discrete Optimization, To appear (2007)

    Google Scholar 

  8. Fischetti, M., Saturni, C.: Mixed-integer cuts from cyclic groups. Mathematical Programming A 109(1), 27–53 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  9. Gomory, R.: Some polyhedra related to combinatorial problems. Journal of Linear Algebra and its Applications 2, 451–558 (1969)

    Article  MATH  MathSciNet  Google Scholar 

  10. Gomory, R., Johnson, E.: Some continuous functions related to corner polyhedra I. Mathematical Programming 3, 23–85 (1972)

    Article  MATH  MathSciNet  Google Scholar 

  11. Gomory, R., Johnson, E.: Some continuous functions related to corner polyhedra II. Mathematical Programming 3, 359–389 (1972)

    Article  MATH  MathSciNet  Google Scholar 

  12. Gomory, R., Johnson, E.: T-space and cutting planes. Mathematical Programming 96, 341–375 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  13. Gomory, R., Johnson, E., Evans, L.: Cyclic group and knapsack facets. Mathematical Programming 96, 321–339 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  14. Uchoa, E.: Robust branch-and-cut-and-price for the CMST problem and extended capacity cuts. Presentation in the MIP 2005 Workshop, Minneapolis (2005), Available at http://www.ima.umn.edu/matter/W7.25-29.05/activities/Uchoa-Eduardo/cmst-ecc-IMA.pdf

  15. Uchoa, E., Fukasawa, R., Lysgaard, J., Pessoa, A., Poggi de Aragão, M., Andrade, D.: Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation. Mathematical Programming, To appear

    Google Scholar 

  16. Wolsey, L.: Facets and strong valid inequalities for integer programs. Oper. Res. 24, 367–372 (1976)

    Article  MATH  MathSciNet  Google Scholar 

  17. Nemhauser, G., Gu, Z., Savelsbergh, M.: Sequence independent lifting in mixed integer programming. J. Comb. Optim. 4, 109–129 (2000)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Mathematical Sciences Department, IBM T. J. Watson Research Center, Yorktown Heights, NY, 10598,  

    Sanjeeb Dash & Oktay Günlük

  2. H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, 30332,  

    Ricardo Fukasawa

Authors
  1. Sanjeeb Dash
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ricardo Fukasawa
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Oktay Günlük
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Matteo Fischetti David P. Williamson

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer Berlin Heidelberg

About this paper

Cite this paper

Dash, S., Fukasawa, R., Günlük, O. (2007). On a Generalization of the Master Cyclic Group Polyhedron. In: Fischetti, M., Williamson, D.P. (eds) Integer Programming and Combinatorial Optimization. IPCO 2007. Lecture Notes in Computer Science, vol 4513. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72792-7_16

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-72792-7_16

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-72791-0

  • Online ISBN: 978-3-540-72792-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics