article

An approximation scheme for stochastic linear programming and its application to stochastic integer programs

Authors:

David B. Shmoys,

Chaitanya SwamyAuthors Info & Claims

Journal of the ACM (JACM), Volume 53, Issue 6

Pages 978 - 1012

https://doi.org/10.1145/1217856.1217860

Published: 01 November 2006 Publication History

Abstract

Stochastic optimization problems attempt to model uncertainty in the data by assuming that the input is specified by a probability distribution. We consider the well-studied paradigm of 2-stage models with recourse: first, given only distributional information about (some of) the data one commits on initial actions, and then once the actual data is realized (according to the distribution), further (recourse) actions can be taken. We show that for a broad class of 2-stage linear models with recourse, one can, for any ϵ > 0, in time polynomial in 1/ϵ and the size of the input, compute a solution of value within a factor (1+ϵ) of the optimum, in spite of the fact that exponentially many second-stage scenarios may occur. In conjunction with a suitable rounding scheme, this yields the first approximation algorithms for 2-stage stochastic integer optimization problems where the underlying random data is given by a “black box” and no restrictions are placed on the costs in the two stages. Our rounding approach for stochastic integer programs shows that an approximation algorithm for a deterministic analogue yields, with a small constant-factor loss, provably near-optimal solutions for the stochastic generalization. Among the range of applications, we consider are stochastic versions of the multicommodity flow, set cover, vertex cover, and facility location problems.

References

[1]

Beale, E. M. L. 1955. On minimizing a convex function subject to linear inequalities. J. Roy. Stat. Soc. Ser. B 17, 173--184.

[2]

Bertsimas, D., and Sim, M. 2003. Robust discrete optimization and network flows. Math. Prog. Ser. B 98, 49--71.

Digital Library

[3]

Birge, J. R., and Louveaux, F. V. 1997. Introduction to Stochastic Programming. Springer-Verlag, New York.

[4]

Borwein, J., and Lewis, A. S. 2000. Convex Analysis and Nonlinear Optimization. Springer-Verlag, New York.

[5]

Charikar, M., Chekuri, C., and Pál, M. 2005. Sampling bounds for stochastic optimization. In Proceedings of the 9th International Workshop on Randomization and Computation. 257--269.

Digital Library

[6]

Chvátal, V. 1979. A greedy heuristic for the set-covering problem. Math. Oper. Res. 4, 233--235.

Digital Library

[7]

Dantzig, G. B. 1955. Linear programming under uncertainty. Manage. Sci. 1, 197--206.

Digital Library

[8]

Dye, S., Stougie, L., and Tomasgard, A. 2003. The stochastic single resource service-provision problem. Naval Res. Logi. 50, 869--887. (Also appeared as “The stochastic single node service provision problem”, COSOR-Memorandum 99-13, Dept. of Mathematics and Computer Science, Eindhoven, Technical University, Eindhoven, 1999.)

[9]

Dyer, M., Kannan, R., and Stougie, L. 2002. A simple randomised algorithm for convex optimisation. Tech. Rep. SPOR-Report 2002-05, Dept. of Mathematics and Computer Science, Eindhoven Technical University, Eindhoven.

[10]

Dyer, M., and Stougie, L. 2006. Computational complexity of stochastic programming problems. Math. Prog. 106, 423--432.

Digital Library

[11]

Garg, N., Vazirani, V., and Yannakakis, M. 1997. Primal dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18, 3--20.

Digital Library

[12]

Grötschel, M., Lovász, L., and Schrijver, A. 1988. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, New York.

[13]

Gupta, A., Pál, M., Ravi, R., and Sinha, A. 2004. Boosted sampling: approximation algorithms for stochastic optimization. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing. ACM, New York. 417--426.

Digital Library

[14]

Immorlica, N., Karger, D., Minkoff, M., and Mirrokni, V. 2004. On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms. 684--693.

Digital Library

[15]

Kleywegt, A. J., Shapiro, A., and Homem-De-Mello, T. 2001. The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12, 479--502.

Digital Library

[16]

Kolliopoulos, S., and Young, N. 2005. Approximation algorithms for covering/packing integer programs. J. Comput. Syst. Sci. 71, 495--505.

Digital Library

[17]

Linderoth, J., Shapiro, A., and Wright, R. K. 2006. The empirical behavior of sampling methods for stochastic programming. Ann. Oper. Res. 142, 215--241.

[18]

Mahdian, M. 2004. Facility location and the analysis of algorithms through factor-revealing programs. Ph.D. dissertation, MIT, Cambridge, MA.

Digital Library

[19]

Mahdian, M., Ye, Y., and Zhang, J. 2006. Approximation algorithms for metric facility location problems. SIAM J. Comput. 36, 411--432.

Digital Library

[20]

Nemirovski, A., and Shapiro, A. 2006. On complexity of Shmoys-Swamy class of two-stage linear stochastic programming problems. Optim. Online. http://www.optimization-online.org/DB_FILE/2006/07/1434.pdf.

[21]

Nesterov, Y., and Vial, J.-P. 2000. Confidence level solutions for stochastic programming. Tech. Rep., CORE Discussion Papers. http://www.core.ucl.ac.be/services/psfiles/dp00/dp2000-13.pdf.

[22]

Ravi, R., and Sinha, A. 2006. Hedging uncertainty: approximation algorithms for stochastic optimization problems. Math. Prog. Ser. A 108, 97--114.

Digital Library

[23]

Shapiro, A. 2003. Monte carlo sampling methods. In Stochastic Programming, A. Ruszczynski and A. Shapiro, Eds. Handbooks in Operations Research and Management Science, vol. 10. North-Holland, Amsterdam, The Netherlands.

[24]

Shapiro, A., and Nemirovski, A. 2005. On complexity of stochastic programming problems. In Continuous Optimization: Current Trends and Modern Applications, V. Jeyakumar and A. Rubinov, Eds. Applied Optimization, vol. 99. Springer-Verlag, New York. (Also published electronically in Optimization Online, 2004. http://www.optimization-online.org/DB_FILE/2004/10/978.pdf).

[25]

Shmoys, D. B., and Swamy, C. 2004. Stochastic optimization is (almost) as easy as deterministic optimization. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 228--237.

Digital Library

[26]

Shmoys, D. B., Tardos, É., and Aardal, K. I. 1997. Approximation algorithms for facility location problems. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing. ACM, New York, 265--274.

Digital Library

[27]

Swamy, C. 2004. Approximation algorithms for clustering problems. Ph.D. dissertation, Cornell University, Ithaca, New York. http://www.math.uwaterloo.ca/~cswamy/theses/master.pdf.

Digital Library

[28]

Swamy, C., and Shmoys, D. B. 2004. The sample average approximation method for 2-stage stochastic optimization. http://www.math.uwaterloo.ca/~cswamy/papers/SAAproof.pdf.

[29]

Swamy, C., and Shmoys, D. B. 2005. Sampling-based approximation algorithms for multi-stage stochastic optimization. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 357--366.

Digital Library

[30]

Verweij, B., Ahmed, S., Kleywegt, A. J., Nemhauser, G. L., and Shapiro, A. 2003. The sample average approximation method applied to stochastic routing problems: A computational study. Computat. Optim. Appl. 24, 289--333.

Digital Library

Cited By

Klein KReuter J(2024)Collapsing the Tower—On the Complexity of Multistage Stochastic IPsACM Transactions on Algorithms10.1145/360455420:3(1-21)Online publication date: 21-Jun-2024
https://dl.acm.org/doi/10.1145/3604554
Forcier MGaubert SLeclère V(2024)Exact Quantization of Multistage Stochastic Linear ProblemsSIAM Journal on Optimization10.1137/22M150800534:1(533-562)Online publication date: 5-Feb-2024
https://doi.org/10.1137/22M1508005
Martínez Mori JSperanza MSamaranayake S(2023)On the Value of Dynamism in Transit NetworksTransportation Science10.1287/trsc.2022.119357:3(578-593)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1287/trsc.2022.1193
Show More Cited By

Index Terms

An approximation scheme for stochastic linear programming and its application to stochastic integer programs
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Stochastic control and optimization
  2. Probability and statistics
    1. Probabilistic algorithms
    2. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
      2. Sequential Monte Carlo methods
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Continuous optimization
        Stochastic control and optimization
  2. Randomness, geometry and discrete structures

Recommendations

Discounted Stochastic Fluid Programs

We consider optimal control problems for stochastic fluid models of the following type: Suppose (Z_t) is a continuous-time Markov chain with finite state space. As long as Z_t = z, the dynamics of the system at time t are given by a function b^z(u(·)), where ...
Stochastic dual dynamic integer programming

Multistage stochastic integer programming (MSIP) combines the difficulty of uncertainty, dynamics, and non-convexity, and constitutes a class of extremely challenging problems. A common formulation for these problems is a dynamic programming formulation ...
Improved Bounds in Stochastic Matching and Optimization

Real-world problems often have parameters that are uncertain during the optimization phase; stochastic optimization or stochastic programming is a key approach introduced by Beale and by Dantzig in the 1950s to address such uncertainty. Matching is a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 53, Issue 6

November 2006

132 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/1217856

Issue’s Table of Contents

Copyright © 2006 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 2006

Published in JACM Volume 53, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

87
Total Citations
View Citations
1,022
Total Downloads

Downloads (Last 12 months)35
Downloads (Last 6 weeks)2

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Klein KReuter J(2024)Collapsing the Tower—On the Complexity of Multistage Stochastic IPsACM Transactions on Algorithms10.1145/360455420:3(1-21)Online publication date: 21-Jun-2024
https://dl.acm.org/doi/10.1145/3604554
Forcier MGaubert SLeclère V(2024)Exact Quantization of Multistage Stochastic Linear ProblemsSIAM Journal on Optimization10.1137/22M150800534:1(533-562)Online publication date: 5-Feb-2024
https://doi.org/10.1137/22M1508005
Martínez Mori JSperanza MSamaranayake S(2023)On the Value of Dynamism in Transit NetworksTransportation Science10.1287/trsc.2022.119357:3(578-593)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1287/trsc.2022.1193
Baveja AChavan ANikiforov ASrinivasan AXu P(2023)Technical Note—Improved Sample-Complexity Bounds in Stochastic OptimizationOperations Research10.1287/opre.2018.0340Online publication date: 17-Oct-2023
https://doi.org/10.1287/opre.2018.0340
Ganesh AMaggs BPanigrahi D(2023)Universal Algorithms for Clustering ProblemsACM Transactions on Algorithms10.1145/357284019:2(1-46)Online publication date: 9-Mar-2023
https://dl.acm.org/doi/10.1145/3572840
Göke AMarx DMnich M(2022)Parameterized algorithms for generalizations of Directed Feedback Vertex SetDiscrete Optimization10.1016/j.disopt.2022.10074046:COnline publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1016/j.disopt.2022.100740
Wojciechowski PWilliamson MSubramani K(2022)On the analysis of optimization problems in arc-dependent networksDiscrete Optimization10.1016/j.disopt.2022.10072945:COnline publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1016/j.disopt.2022.100729
Grover SGupta NKhuller S(2022)LP-based approximation for uniform capacitated facility location problemDiscrete Optimization10.1016/j.disopt.2022.10072345:COnline publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1016/j.disopt.2022.100723
Mulati MFukasawa RMiyazawa F(2022)The Arc-Item-Load and Related Formulations for the Cumulative Vehicle Routing ProblemDiscrete Optimization10.1016/j.disopt.2022.10071045:COnline publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1016/j.disopt.2022.100710
Rodrigues de Sousa VAnjos MLe Digabel S(2022)Computational study of a branching algorithm for the maximum k-cut problemDiscrete Optimization10.1016/j.disopt.2021.10065644:P2Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1016/j.disopt.2021.100656
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents