×

Distributionally robust mixed integer linear programs: persistency models with applications. (English) Zbl 1339.90248

Summary: In this paper, we review recent advances in the distributional analysis of mixed integer linear programs with random objective coefficients. Suppose that the probability distribution of the objective coefficients is incompletely specified and characterized through partial moment information. Conic programming methods have been recently used to find distributionally robust bounds for the expected optimal value of mixed integer linear programs over the set of all distributions with the given moment information. These methods also provide additional information on the probability that a binary variable attains a value of 1 in the optimal solution for \(0-1\) integer linear programs. This probability is defined as the persistency of a binary variable. In this paper, we provide an overview of the complexity results for these models, conic programming formulations that are readily implementable with standard solvers and important applications of persistency models. The main message that we hope to convey through this review is that tools of conic programming provide important insights in the probabilistic analysis of discrete optimization problems. These tools lead to distributionally robust bounds with applications in activity networks, vertex packing, discrete choice models, random walks and sequencing problems, and newsvendor problems.

MSC:

90C11 Mixed integer programming
90C31 Sensitivity, stability, parametric optimization
90C20 Quadratic programming

Software:

ROME
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Adams, W. P.; Lassiter, J. B.; Sherali, H. D., Persistency in 0-1 polynomial programming, Mathematics of Operations Research, 23, 2, 359-389 (1998) · Zbl 0977.90025
[2] Aldous, D., The \(ζ(2)\) limit in the random assignment problem, Random Structures and Algorithms, 18, 4, 381-418 (2001) · Zbl 0993.60018
[3] Aldous, D.; Steele, J. M., The objective method: Probabilistic combinatorial optimization and local weak convergence, (Kesten, H., Probability on discrete structures (2003), Springer), 1-72 · Zbl 1037.60008
[4] Beardwood, J.; Halton, J. H.; Hammersley, J. M., The shortest path through many points, Proceedings of the Cambridge Philosophical Society, 55, 4, 299-327 (1959) · Zbl 0118.35601
[5] Berman, A.; Shaked-Monderer, N., Completely positive matrices (2003), World Scientific: World Scientific Singapore · Zbl 1030.15022
[6] Bertsimas, D.; Doan, X. V.; Natarajan, K.; Teo, C. P., Models for minimax stochastic linear optimization problems with risk aversion, Mathematics of Operations Research, 35, 3, 580-602 (2010) · Zbl 1218.90215
[7] Bertsimas, D.; Natarajan, K.; Teo, C. P., Probabilistic combinatorial optimization: Moments, semidefinite programming and asymptotic bounds, SIAM Journal of Optimization, 15, 1, 185-209 (2004) · Zbl 1077.90047
[8] Bertsimas, D.; Natarajan, K.; Teo, C. P., Persistence in discrete optimization under data uncertainty, Mathematical Programming, Series B, Issue on Opimization under Uncertainty, 108, 2-3, 251-274 (2006) · Zbl 1130.90365
[9] Bertsimas, D.; Popescu, I., On the relation between option and stock prices: A convex optimization approach, Operations Research, 50, 2, 358-374 (2002) · Zbl 1163.91382
[10] Birge, J. R.; Maddox, M. J., Bounds on expected project tardiness, Operations Research, 43, 5, 838-850 (1995) · Zbl 0841.90071
[11] Bomze, I. M., Copositive optimization: Recent developments and applications, European Journal of Operational Research, 126, 3, 509-520 (2012), Invited review · Zbl 1262.90129
[12] Bomze, I. M.; de Klerk, E., Solving standard quadratic optimization problems via linear, semidefinite and copositive programming, Journal of Global Optimization, 24, 2, 163-185 (2002) · Zbl 1047.90038
[13] Bowman, R. A., Efficient estimation of arc criticalities in stochastic activity networks, Management Science, 41, 1, 58-67 (1995) · Zbl 0829.90056
[14] Boyle, P. P.; Lin, X. S., Bounds on contingent claims based on several assets, Journal of Financial Economics, 46, 3, 383-400 (1997)
[15] Burer, S., On the copositive representation of binary and continuous nonconvex quadratic programs, Mathematical Programming, 120, 2, 479-495 (2009) · Zbl 1180.90234
[16] Chen, W.; Sim, M.; Sun, J.; Teo, C. P., From CVaR to uncertainty set: Implications in joint chance constrained optimization, Operations Research, 58, 470-485 (2010) · Zbl 1226.90051
[17] Diananda, P. H., On nonnegative forms in real variables some or all of which are nonnegative, Mathematical Proceedings of the Cambridge Philosophical Society, 58, 17-25 (1962) · Zbl 0108.04803
[18] Delage, E.; Ye, Y., Distributionally robust optimization under moment uncertainty with application to data-driven problems, Operations Research, 58, 3, 596-612 (2010) · Zbl 1228.90064
[19] Doan, X. V.; Natarajan, K., On the complexity of non-overlapping multivariate marginal bounds for probabilistic combinatorial optimization problems, Operations Research, 60, 1, 138-149 (2011), 2012 · Zbl 1245.90099
[20] Dodin, B., Bounding the project completion time distribution in PERT networks, Operations Research, 33, 4, 862-881 (1985) · Zbl 0579.90055
[21] Dodin, B.; Elmaghraby, S. E., Approximating the criticality indices of activities in PERT networks, Management Science, 31, 2, 207-223 (1985) · Zbl 0607.90044
[22] Dür, M., Copositive programming: A survey, (Diehl, M.; Glineur, F.; Jarlebring, E.; Michiels, W., Recent advances in optimization and its applications in engineering (2010), Springer: Springer Berlin Heidelberg), 3-20
[23] Fulkerson, D. R., Expected critical path length in PERT networks, Operations Research, 10, 6, 808-817 (1962) · Zbl 0124.36304
[24] Grötschel, M.; Lovász, L.; Schrijver, A., Geometric algorithms and combinatorial optimization (1988), Springer: Springer Berlin, Heidelberg · Zbl 0634.05001
[25] Goh, J.; Sim, M., Distributionally robust optimization and its tractable approximations, Operations Research, 58, 4, 902-917 (2010) · Zbl 1228.90067
[26] Hagstrom, J. N., Computational complexity of PERT problems, Networks, 18, 2, 139-147 (1988)
[27] Hammer, P. L.; Hansen, P.; Simeone, B., Roof duality, complementation and persistency in quadratic 0-1 optimization, Mathematical Programming, 28, 2, 121-155 (1984) · Zbl 0574.90066
[28] Harrison, J. M.; Van Mieghem, J. A., Multi-resource investment strategies: Operational hedging under demand uncertainty, European Journal of Operational Research, 113, 17-29 (1999) · Zbl 0933.91011
[29] Hiriart-Urruty, J.-B.; Seeger, A., A variational approach to copositive matrices, SIAM Review, 52, 4, 593-629 (2010) · Zbl 1207.15037
[30] Hochbaum, D. S.; Megiddo, N.; Naor, J.; Tamir, A., Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality, Mathematical Programming, 62, 1-3, 69-83 (1993) · Zbl 0802.90080
[31] Kantorovich, L., On the translocation of masses, Management Science, 5, 1, 1-4 (1958) · Zbl 0995.90585
[32] Karlin, S.; Studden, W. J., Tchebycheff systems: With applications in analysis and statistics (pure and applied mathematics) (1966), Interscience Publishers · Zbl 0153.38902
[33] Karp, R. M., A patching algorithm for the nonsymmetric traveling-salesman problem, SIAM Journal on Computing, 8, 4, 561-573 (1979) · Zbl 0427.90064
[34] Kemperman, J. H.B.; Skibinsky, M., Covariance spaces for measures on polyhedral sets, Stochastic Inequalities, IMS Lecture Notes - Monograph Series, 22, 182-195 (1992) · Zbl 1400.60019
[35] Klein Haneveld, W. K., Robustness against dependence in PERT: An application of duality and distributions with known marginals, Mathematical Programming Studies, 27, 153-182 (1986) · Zbl 0592.90048
[36] Kleindorfer, G. B., Bounding distributions for a stochastic acyclic network, Operations Research, 19, 7, 1586-1601 (1971) · Zbl 0247.90026
[37] Krokhmal, P.; Pardalos, P., Random assignment problems, European Journal of Operational Research, 194, 1, 1-17 (2009) · Zbl 1179.90212
[38] Kong, Q.; Lee, C. Y.; Teo, C. P.; Zheng, Z., Scheduling arrivals to a stochastic service delivery system using copositive cones, Operations Research, 61, 3, 711-726 (2013) · Zbl 1273.90090
[39] Lasserre, J. B., Global optimization with polynomials and the problem of moments, SIAM Journal on Optimization, 11, 3, 796-817 (2001) · Zbl 1010.90061
[40] Lasserre, J. B., Bounds on measures satisfying moment conditions, Annals of Applied Probability, 12, 3, 1114-1137 (2002) · Zbl 1073.90534
[41] Lasserre, J. B., Moments, positive polynomials and their applications (2009), Imperial College Press
[42] Lasserre, J. B., A “joint<ce:hsp sp=”0.25“/>+<ce:hsp sp=”0.25“/>marginal” approach to parametric polynomial optimization, SIAM Journal of Optimization, 20, 1995-2022 (2010) · Zbl 1204.65067
[43] Laurent, M., A comparison of the Sherali-Adams, Lovász-Schrijver and Lasserre relaxations for 0-1 programming, Mathematics of Operations Research, 28, 470-496 (2003) · Zbl 1082.90084
[44] Linusson, S.; Wästlund, J., A proof of Parisi’s conjecture on the random assignment problem, Probability Theory and Related Fields, 128, 3, 419-440 (2004) · Zbl 1055.90056
[45] Lovász, L., Energy of convex sets, shortest paths and resistance, Journal of Combinatorial Theory, Series A, 94, 363-382 (2001) · Zbl 0993.05094
[46] Lu, S. H.; Williams, A. C., Roof duality for polynomial 0-1 optimization, Mathematical Programming, 37, 3, 357-360 (1987) · Zbl 0632.90044
[47] Lyons, R.; Pemantle, R.; Peres, Y., Resistance bounds for first-passage percolation and maximum flow, Journal of Combinatorial Theory, Series A, 86, 1, 158-168 (1999) · Zbl 0918.60089
[48] Malcolm, D. G.; Roseboom, J. H.; Clark, C. E.; Fazar, W., Application of a technique for research and development program evaluation, Operations Research, 7, 5, 646-669 (1959) · Zbl 1255.90070
[49] Mangasarian, O. J.; Shiau, T. H., A variable-complexity norm maximization problem, SIAM Journal on Algebraic and Discrete Methods, 7, 3, 455-461 (1986) · Zbl 0589.68033
[50] Marshall, A. W.; Olkin, I., Multivariate Chebyshev inequalities, Annals of Mathematical Statistics, 31, 4, 1001-1014 (1960) · Zbl 0244.60013
[51] Meilijson, I.; Nadas, A., Convex majorization with an application to the length of critical path, Journal of Applied Probability, 16, 3, 671-677 (1979) · Zbl 0417.60025
[52] Mézard, M.; Parisi, G., Replicas and optimization, Journal de Physique Lettres, 46, 771-778 (1985)
[53] Mishra, V. K.; Natarajan, K.; Tao, H.; Teo, C. P., Choice prediction with semidefinite optimization when utilities are correlated, IEEE Transactions on Automatic Control, 57, 10, 2450-2463 (2012) · Zbl 1369.90119
[54] Möhring, R. H.M., Scheduling under uncertainty: Bounding the makespan distribution, (Alt, H., Computational discrete mathematics: Advanced lectures. Computational discrete mathematics: Advanced lectures, Lecture notes in computer science, vol. 2122 (2001), Springer), 7997 · Zbl 0978.00022
[56] Murty, K. G.; Kabadi, S. N., Some NP-complete problems in quadratic and nonlinear programming, Mathematical Programming, 39, 2, 117-129 (1987) · Zbl 0637.90078
[57] Nair, C.; Prabhakar, B.; Sharma, M., Proofs of the Parisi and Coppersmith-Sorkin random assignment conjectures, Random Structures and Algorithms, 27, 4, 413-444 (2005) · Zbl 1125.90026
[58] Natarajan, K.; Song, M.; Teo, C. P., Persistency model and its applications in choice modeling, Management Science, 55, 3, 453-469 (2009) · Zbl 1232.91139
[59] Natarajan, K.; Teo, C. P.; Zheng, Z., Mixed zero-one linear programs under ojective uncertainty: A completely positive representation, Operations Research, 59, 3, 713-728 (2011) · Zbl 1231.90304
[60] Nemhauser, G. L.; Trotter, L. E., Vertex packings: Structural properties and algorithms, Mathematical Programming, 8, 1, 232-248 (1975) · Zbl 0314.90059
[63] Popescu, I., Robust mean-covariance solutions for stochastic optimization, Operations Research, 55, 1, 98-112 (2007) · Zbl 1167.90611
[64] Rachev, S. Z.; Rüschendorf, L., Mass transportation problems (probability and its applications) (1998), Springer · Zbl 0990.60500
[65] Scarf, H., A min-max solution of an inventory problem, (Studies in the mathematical theory of inventory and production (1958), Stanford University Press: Stanford University Press California), 201-209
[66] Shapiro, A., On duality theory of conic linear problems, (Goberna, M. A.; Lṕpez, M. A., Semi-infinite programming: Recent advances (2001), Kluwer Academic Publishers), 135-165 · Zbl 1055.90088
[67] Smith, J. E., Generalized Chebychev inequalities: Theory and applications in decision analysis, Operations Research, 43, 5, 807-825 (1995) · Zbl 0842.90002
[68] Steele, J. M., Probability theory and combinatorial optimization, CBMS-NSF Regional Conference Series in Applied Mathematics, 69 (1997) · Zbl 0916.90233
[69] Sturm, J. F.; Zhang, S., On cones of nonnegative quadratic functions, Mathematics of Operations Research, 28, 2, 246-267 (2003) · Zbl 1082.90086
[70] Vandenberghe, L.; Boyd, S.; Comanor, K., Generalized Chebyshev bounds via semidefinite programming, SIAM Review, 49, 1, 52-64 (2007) · Zbl 1151.90512
[71] Van Slyke, R. M., Monte Carlo methods and the PERT problem, Operations Research, 11, 5, 839-860 (1963)
[72] Weiss, G., Stochastic bounds on distributions of optimal value function with applications to PERT, network flows and reliability, Operations Research, 34, 4, 595-605 (1986) · Zbl 0609.90093
[73] Whitt, W., On approximations for queues, I. Extremal distributions, AT&T Bell Labs Technical Journal, 63, 115138 (1984) · Zbl 0598.90040
[74] Zuluaga, L.; Pena, J. F., A conic programming approach to generalized tchebycheff inequalities, Mathematics of Operations Research, 30, 2, 369-388 (2005) · Zbl 1082.90089
[75] Zymler, S.; Kuhn, D.; Rustem, B., Distributionally robust joint chance constraints with second-order moment information, Mathematical Programming, 137, 1-2, 167-198 (2013) · Zbl 1286.90103
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.