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

A data-driven distributionally robust bound on the expected optimal value of uncertain mixed 0-1 linear programming

  • Original Paper
  • Published:
Computational Management Science Aims and scope Submit manuscript

Abstract

This paper studies the expected optimal value of a mixed 0-1 programming problem with uncertain objective coefficients following a joint distribution. We assume that the true distribution is not known exactly, but a set of independent samples can be observed. Using the Wasserstein metric, we construct an ambiguity set centered at the empirical distribution from the observed samples and containing the true distribution with a high statistical guarantee. The problem of interest is to investigate the bound on the expected optimal value over the Wasserstein ambiguity set. Under standard assumptions, we reformulate the problem into a copositive program, which naturally leads to a tractable semidefinite-based approximation. We compare our approach with a moment-based approach from the literature on three applications. Numerical results illustrate the effectiveness of our approach.

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Notes

  1. This process is to solve a linear program or integer program corresponding to each sample in the validation dataset and then to take the average of the optimal values.

  2. From preliminary experiments, the largest element 2.0 in set \(\mathcal E\) returned 1 as the empirical confidence level for all the experiments we conducted. Thus, we believe it is sufficient to have 2.0 as the largest element here.

References

  • Aldous DJ (2001) The \(\zeta \) (2) limit in the random assignment problem. Random Struct Algorithms 18(4):381–418

    Article  Google Scholar 

  • Anstreicher KM (2009) Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming. J Glob Optim 43(2–3):471–484

    Article  Google Scholar 

  • Ben-Tal A, Den Hertog D, De Waegenaere A, Melenberg B, Rennen G (2013) Robust solutions of optimization problems affected by uncertain probabilities. Manag Sci 59(2):341–357

    Article  Google Scholar 

  • Bertsimas D, Popescu I (2005) Optimal inequalities in probability theory: a convex optimization approach. SIAM J Optim 15(3):780–804

    Article  Google Scholar 

  • Bertsimas D, Natarajan K, Teo C-P (2004) Probabilistic combinatorial optimization: moments, semidefinite programming, and asymptotic bounds. SIAM J Optim 15(1):185–209

    Article  Google Scholar 

  • Bertsimas D, Natarajan K, Teo C-P (2006) Persistence in discrete optimization under data uncertainty. Math Program 108(2):251–274

    Article  Google Scholar 

  • Bertsimas D, Gupta V, Kallus N (2013) Data-driven robust optimization. arXiv preprint arXiv:1401.0212

  • Bertsimas D, Gupta V, Kallus N (2014) Robust SAA. arXiv preprint arXiv:1408.4445

  • Bowman RA (1995) Efficient estimation of arc criticalities in stochastic activity networks. Manag Sci 41(1):58–67

    Article  Google Scholar 

  • Burer S (2009) On the copositive representation of binary and continuous nonconvex quadratic programs. Math Program 120(2):479–495

    Article  Google Scholar 

  • Burer S (2012) Copositive programming. In: Handbook on semidefinite, conic and polynomial optimization, Springer, pp 201–218

  • Burer S (2015) A gentle, geometric introduction to copositive optimization. Math Program 151(1):89–116

    Article  Google Scholar 

  • Burer S, Dong H (2012) Representing quadratically constrained quadratic programs as generalized copositive programs. Oper Res Lett 40:203–206

    Article  Google Scholar 

  • Calafiore GC, Ghaoui LEl (2006) On distributionally robust chance-constrained linear programs. J Optim Theory Appl 130(1):1–22

    Article  Google Scholar 

  • Chen Z, Sim M, Xu H (2016) Distributionally robust optimization with infinitely constrained ambiguity sets. Working Paper

  • Delage E, Ye Y (2010) Distributionally robust optimization under moment uncertainty with application to data-driven problems. Oper Res 58(3):595–612

    Article  Google Scholar 

  • Dodin B (1985) Bounding the project completion time distribution in pert networks. Oper Res 33(4):862–881

    Article  Google Scholar 

  • Duchi J, Glynn P, Namkoong H (2016) Statistics of robust optimization: a generalized empirical likelihood approach. arXiv preprint arXiv:1610.03425

  • Dupačová J (1987) The minimax approach to stochastic programming and an illustrative application. Stoch Int J Probab Stoch Process 20(1):73–88

    Google Scholar 

  • Eichfelder G, Jahn J (2008) Set-semidefinite optimization. J Convex Anal 15:767–801

    Google Scholar 

  • El Ghaoui L, Oks M, Oustry F (2003) Worst-case value-at-risk and robust portfolio optimization: a conic programming approach. Oper Res 51(4):543–556

    Article  Google Scholar 

  • Erdoğan E, Iyengar G (2006) Ambiguous chance constrained problems and robust optimization. Math Program 107(1–2):37–61

    Article  Google Scholar 

  • Esfahani PM, Kuhn D (2015) Data-driven distributionally robust optimization using the wasserstein metric: performance guarantees and tractable reformulations. arXiv preprint arXiv:1505.05116

  • Grötschel M, Lovász L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2):169–197

    Article  Google Scholar 

  • Hagstrom JN (1988) Computational complexity of pert problems. Networks 18(2):139–147

    Article  Google Scholar 

  • Halliwell LJ (2015) The lognormal random multivariate. In: Casualty actuarial society E-Forum, Spring

  • Hanasusanto GA, Kuhn D (2016) Conic programming reformulations of two-stage distributionally robust linear programs over wasserstein balls. arXiv preprint arXiv:1609.07505

  • Hanasusanto GA, Kuhn D, Wallace SW, Zymler S (2015) Distributionally robust multi-item newsvendor problems with multimodal demand distributions. Math Program 152(1):1–32

    Article  Google Scholar 

  • Hanasusanto GA, Roitch V, Kuhn D, Wiesemann W (2017) Ambiguous joint chance constraints under mean and dispersion information. Oper Res 65(3):751–767

    Article  Google Scholar 

  • Hu Z, Hong LJ (2013) Kullback-leibler divergence constrained distributionally robust optimization. Available at Optimization Online

  • Jiang R, Guan Y (2016) Data-driven chance constrained stochastic program. Math Program 158(1–2):291–327

  • Klabjan D, Simchi-Levi D, Song M (2013) Robust stochastic lot-sizing by means of histograms. Prod Oper Manag 22(3):691–710

    Article  Google Scholar 

  • Lam H (2016) Recovering best statistical guarantees via the empirical divergence-based distributionally robust optimization. arXiv preprint arXiv:1605.09349

  • Lofberg J (2004) Yalmip: a toolbox for modeling and optimization in matlab. In: 2004 IEEE international symposium on computer aided control systems design, pp 284–289

  • Martello S, Toth P (1990) Knapsack problems: algorithms and computer implementations. Wiley, New York

    Google Scholar 

  • Möhring RH (2001) Scheduling under uncertainty: bounding the makespan distribution. In: Computational discrete mathematics, Springer, pp 79–97

  • MOSEK ApS. The MOSEK optimization toolbox for MATLAB manual. Version 8.0., 2016

  • Natarajan K, Teo CP (2017) On reduced semidefinite programs for second order moment bounds with applications. Math Program 161(1):487–518

    Article  Google Scholar 

  • Natarajan K, Song M, Teo C-P (2009) Persistency model and its applications in choice modeling. Manag Sci 55(3):453–469

    Article  Google Scholar 

  • Natarajan K, Teo CP, Zheng Z (2011) Mixed 0–1 linear programs under objective uncertainty: a completely positive representation. Oper Res 59(3):713–728

    Article  Google Scholar 

  • Pflug G, Wozabal D (2007) Ambiguity in portfolio selection. Quant Finance 7(4):435–442

    Article  Google Scholar 

  • Rubner Y, Tomasi C, Guibas LJ (2000) The earth mover’s distance as a metric for image retrieval. Int J Comput Vis 40(2):99–121

    Article  Google Scholar 

  • Shapiro A (2001) On duality theory of conic linear problems. In: Semi-infinite programming. Springer, pp 135–165

  • Sherali HD, Adams WP (2013) A reformulation-linearization technique for solving discrete and continuous nonconvex problems, vol 31. Springer, Berlin

    Google Scholar 

  • Sturm JF, Zhang S (2003) On cones of nonnegative quadratic functions. Math Oper Res 28(2):246–267

    Article  Google Scholar 

  • Vandenberghe L, Boyd S, Comanor K (2007) Generalized chebyshev bounds via semidefinite programming. SIAM Rev 49(1):52–64

    Article  Google Scholar 

  • Wiesemann W, Kuhn D, Sim M (2014) Distributionally robust convex optimization. Oper Res 62(6):1358–1376

    Article  Google Scholar 

  • Wolsey LA (1998) Integer programming, vol 42. Wiley, New York

    Google Scholar 

  • Zymler S, Kuhn D, Rustem B (2013a) Distributionally robust joint chance constraints with second-order moment information. Math Program 137(1–2):167–198

    Article  Google Scholar 

  • Zymler S, Kuhn D, Rustem B (2013b) Worst-case value at risk of nonlinear portfolios. Manag Sci 59(1):172–188

    Article  Google Scholar 

Download references

Acknowledgements

The authors sincerely thank Kurt Anstreicher, Qihang Lin, Luis Zuluaga, and Tianbao Yang for many useful suggestions, which help us improve the results of the paper. The authors are sincerely grateful to anonymous referees for their comments that have improved the paper.

Author information

Authors and Affiliations

  1. Department of Management Sciences, University of Iowa, Iowa City, IA, 52242-1994, USA

    Guanglin Xu & Samuel Burer

Authors
  1. Guanglin Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Samuel Burer
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Guanglin Xu.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Xu, G., Burer, S. A data-driven distributionally robust bound on the expected optimal value of uncertain mixed 0-1 linear programming. Comput Manag Sci 15, 111–134 (2018). https://doi.org/10.1007/s10287-018-0298-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10287-018-0298-9

Keywords

Search

Navigation