Abstract
This paper presents an investigation on the computational complexity of stochastic optimization problems. We discuss a scenario-based model which captures the important classes of two-stage stochastic combinatorial optimization, two-stage stochastic linear programming, and two-stage stochastic integer linear programming. This model can also be used to handle chance constraints, which are used in many stochastic optimization problems. We derive general upper bounds for the complexity of computational problems related to this model, which hold under very mild conditions. Additionally, we show that these upper bounds are matched for some stochastic combinatorial optimization problems arising in the field of transportation and logistics.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
That means \(p\) and \(k\) have one additional input which specifies the number of output bits that are required. In this way \(p\) and \(k\) are providing the numbers to any desired accuracy in polynomial time with respect to the input and the number of output bits.
- 2.
In fact, we can even handle problems which do not fulfill this assumption by truncating the objective function and the constraints after a certain number of at most polynomially many bits. The resulting problem is then a slight perturbation of the original problem which should not incur any difference for practical purposes.
- 3.
We use the following convention for all the \(x\) customers in the reduction: A group of customers with the same label is either completely present or none of those customers is present. Customers with a label of \(x_i\) are present if and only if the customers with the label \(\bar{x_i}\) are absent.
- 4.
In fact, there are four and not two possible paths, since the order of \(x_i\) and \(\bar{x_i}\) can be changed without affecting the quality of the solution, but they are analogous.
- 5.
Additionally, we save some travel time going from \(v_1\) over \(x_1\) / \(\bar{x_1}\) to \(\text {true}\) / \(\text {false}\). Again, this does not incur in relevant changes, for the very same reasons.
References
Birge, J.R., Louveaux, F.V.: Introduction to Stochastic Programming. Springer, Berlin (1997)
de Campos, C., Stamoulis, G., Weyland, D.: A structured view on weighted counting with relations to quantum computation and applications. Technical report, Electronic Colloquium on Computational Complexity, TR13-133 (2013)
Dyer, M., Stougie, L.: Computational complexity of stochastic programming problems. Math. Program. 106(3), 423–432 (2006)
Fortnow, L., Reingold, N.: PP is closed under truth-table reductions. Inf. Comput. 124(1), 1–6 (1996)
Jaillet, P.: A priori solution of a traveling salesman problem in which a random subset of the customers are visited. Oper. Res. 36(6), 929–936 (1988)
Littman, M.L., Goldsmith, J., Mundhenk, M.: The computational complexity of probabilistic planning. J. Artif. Intell. Res. 9(1), 36 (1998)
Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8, 189–201 (1979)
Weyland, D., Montemanni, R., Gambardella, L.M.: Hardness results for the probabilistic traveling salesman problem with deadlines. In: Mahjoub, A.R., Markakis, V., Milis, I., Paschos, V.T. (eds.) ISCO 2012. LNCS, vol. 7422, pp. 392–403. Springer, Heidelberg (2012)
Weyland, D., Montemanni, R., Gambardella, L.M.: An improved heuristic for the probabilistic traveling salesman problem with deadlines based on GPGPU. In: Moreno-Díaz, R., Pichler, F., Quesada-Arencibia, A. (eds.) EUROCAST 2013, Part I. LNCS, vol. 8111, pp. 332–339. Springer, Heidelberg (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
de Campos, C.P., Stamoulis, G., Weyland, D. (2014). The Computational Complexity of Stochastic Optimization. In: Fouilhoux, P., Gouveia, L., Mahjoub, A., Paschos, V. (eds) Combinatorial Optimization. ISCO 2014. Lecture Notes in Computer Science(), vol 8596. Springer, Cham. https://doi.org/10.1007/978-3-319-09174-7_15
Download citation
DOI: https://doi.org/10.1007/978-3-319-09174-7_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-09173-0
Online ISBN: 978-3-319-09174-7
eBook Packages: Computer ScienceComputer Science (R0)