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

An algorithm for the construction of convex hulls in simple integer recourse programming

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

We consider the objective function of a simple integer recourse problem with fixed technology matrix and discretely distributed right-hand sides. Exploiting the special structure of this problem, we devise an algorithm that determines the convex hull of this function efficiently. The results are improvements over those in a previous paper. In the first place, the convex hull of many objective functions in the class is covered, instead of only one-dimensional versions. In the second place, the algorithm is faster than the one in the previous paper. Moreover, some new results on the structure of the objective function are presented.

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. R.L. Graham, An efficient algorithm for determining the convex hull of a finite planar set, Information Processing Letters 1, 1972, 132–133.

    Article  Google Scholar 

  2. W.K. Klein Haneveld, L. Stougie and M.H. van der Vlerk, On the convex hull of the simple integer recourse objective function, Annals of Operations Research 56, 1995, 209–224.

    Article  Google Scholar 

  3. W.K. Klein Haneveld, L. Stougie and M.H. van der Vlerk, Some theorems on the convex hull of a function with an application to stochastic integer programming, Discussion Paper TI 94-81, Tinbergen Institute, Amsterdam-Rotterdam, 1994.

    Google Scholar 

  4. F.V. Louveaux and M.H. van der Vlerk, Stochastic programming with simple integer recourse, Mathematical Programming 61, 1993, 301–325.

    Article  Google Scholar 

  5. R.T. Rockafellar,Convex Analysis, Princeton University Press, Princeton, NJ, 1970.

    Google Scholar 

  6. R.T. Rockafellar and R.J-B Wets,Variational Analysis, Springer, Berlin, in preparation.

  7. R. Schultz, Continuity and stability in two-stage stochastic integer programming, inLecture Notes in Economics and Mathematical Systems, vol. 379, K. Marti, ed., Springer, Berlin, 1992, pp. 81–92.

    Google Scholar 

  8. M.H. van der Vlerk, Stochastic programming with integer recourse, Ph.D. Thesis, University of Groningen, The Netherlands, 1995.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Econometrics, University of Groningen, Groningen, The Netherlands

    Willem K. Klein Haneveld

  2. Institute for Actuarial Sciences and Econometrics, University of Amsterdam, Amsterdam, The Netherlands

    Leen Stougie

  3. CORE, Université Catholique de Louvain, Louvain-la-Neuve, Belgium

    Maarten H. van der Vlerk

Authors
  1. Willem K. Klein Haneveld
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Leen Stougie
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Maarten H. van der Vlerk
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Haneveld, W.K.K., Stougie, L. & van der Vlerk, M.H. An algorithm for the construction of convex hulls in simple integer recourse programming. Ann Oper Res 64, 67–81 (1996). https://doi.org/10.1007/BF02187641

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02187641

Keywords

Search

Navigation