Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Tight formulations for some simple mixed integer programs and convex objective integer programs

  • Published:
Mathematical Programming Submit manuscript

Abstract.

We study the polyhedral structure of simple mixed integer sets that generalize the two variable set {(s,z)R 1 + ×ℤ1:s≥z−b}. These sets form basic building blocks that can be used to derive tight formulations for more complicated mixed integer programs. For four such sets we give a complete description by valid inequalities and/or an integral extended formulation, and we also indicate what constraints can be added without destroying integrality. We apply these results to provide tight formulations for certain piecewise–linear convex objective integer programs, and in a companion paper we exploit them to provide polyhedral descriptions and computationally effective mixed integer programming formulations for discrete lot-sizing problems.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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. Agra, A., Constantino, M.: Polyhedral description of basic knapsack problems with a continuous variable, University of Lisbon. 2001

  2. Ahuja, R.L., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs, NJ. 1993

  3. Atamtürk, A., Nemhauser, G.L., Savelsbergh, M.W.P.: The Mixed Vertex Packing Problem. Math. Program. 89, 35–53 (2000)

    Google Scholar 

  4. Atamtürk, A., Rajan, D.: On splittable and unsplittable flow capacitated network design arc–set polyhedra. Mathematical Programming 92, 315–333 (2002)

    Google Scholar 

  5. Constantino, M.: Private communication, 2002

  6. Fleischmann, B.: The discrete lot–sizing and scheduling problem. Eur. J. Oper. Res. 44, 337–348 (1990)

    Google Scholar 

  7. Gomory, R.E.: An algorithm for the mixed integer problem. The RAND Corporation. American Mathematical Society, RM-2597. 1960

  8. Günlük, O., Pochet, Y.: Mixing MIR inequalities for mixed integer programs. Math. Program. 90, 429–458 (2001)

    Google Scholar 

  9. Hochbaum, D.S., Shantikumar, J.G.: Convex separable optimization is not much harder than linear optimization. Journal of ACM 37, 843–862 (1990)

    Google Scholar 

  10. Magnanti, T.L., Mirchandani, P., Vachani, R.: The convex hull of two core capacitated network design problems. Math. Program. 60, 233–250 (1993)

    Google Scholar 

  11. Marchand, H., Wolsey, L.A.: Aggregation and Mixed Integer Rounding to solve MIPs. Oper. Res. 49, 363–371 (2001)

    Google Scholar 

  12. Miller, A., Wolsey, L.A.: Tight MIP Formulations for Multi–Item Discrete Lot–Sizing Problems, CORE, Louvain-la-Neuve, Belgium. To appear in Operations Research. (2002)

  13. Pereira, O., Wolsey, L.A.: On the Wagner–Whitin lot–sizing polyhedron. Math. of Oper. Res. 26, 591–600 (2001)

    Google Scholar 

  14. Pochet, Y., Wolsey, L.A.: Polyhedra for lot–sizing with Wagner–Whitin costs. Math. Program. 67, 297–323 (1994)

    Google Scholar 

  15. Pochet, Y., Wolsey, L.A.: Integer Knapsacks and Flow Covers with Divisible Coefficients: Polyhedra, Optimization and Separation. Discrete Applied Mathematics 59, 57–74 (1995)

  16. Salkin, H.M.: Integer Programming. Addison Wesley, Reading, Mass. 1975

  17. van Eijl, C.A., van Hoesel, C.P.M.: On the discrete lot–sizing and scheduling problem with Wagner–Whitin costs, Operations Research Letters 20, 7–13 (1997)

    Google Scholar 

  18. van Hoesel, C.P.M., Kuik, R., Salomon, M., van Wassenhove, L.N.: The single item discrete lot–sizing and scheduling problem: optimization by linear and dynamic programming. Discrete Appl. Math. 48, 289–303 (1994)

    Google Scholar 

  19. White, W.: On Gomory's mixed integer algorithm. Senior's thesis, Princeton University. 1961

Download references

Author information

Author notes

  1. Andrew J. Miller

    Present address: Dept. of Industrial Engineering, University of Wisconsin-Madison,

Authors and Affiliations

  1. Work carried out at CORE, Université Catholique de Louvain, Belgium

    Andrew J. Miller

  2. CORE and INMA, Université Catholique de Louvain, Belgium

    Laurence A. Wolsey

Authors
  1. Andrew J. Miller
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Laurence A. Wolsey
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Laurence A. Wolsey.

Additional information

This paper 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 research was also supported by the European Commission GROWTH Programme, Research Project LISCOS, Large Scale Integrated Supply Chain Optimization Software Based on Branch–and–Cut and Constraint Programming Methods, Contract No. GRDI–1999–10056.

Mathematics Subject Classification (2000): 90C11, 90C57

Rights and permissions

Reprints and permissions

About this article

Cite this article

Miller, A., Wolsey, L. Tight formulations for some simple mixed integer programs and convex objective integer programs. Math. Program., Ser. B 98, 73–88 (2003). https://doi.org/10.1007/s10107-003-0397-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-003-0397-3

Keywords

Search

Navigation