Open Collections

Exploiting Partial Correlations in Distributionally Robust Optimization

Banff International Research Station for Mathematical Innovation and Discovery

In this work, we identify partial correlation information structures that allow for simpler reformulations in evaluating the maximum expected value of mixed integer linear programs with random objective coefficients. To this end, assuming only the knowledge of the mean and the covariance matrix entries restricted to block-diagonal patterns, we develop a reduced semidefinite programming formulation. In some cases, this lends itself to efficient representations that result in polynomial-time solvable instances, most notably for the distributionally robust appointment scheduling problem with random job durations as well as for computing tight bounds in PERT networks and linear assignment problems. To the best of our knowledge, this is the first example of a distributionally robust optimization formulation for appointment scheduling that permits a tight polynomial-time solvable semidefinite programming reformulation which explicitly captures partially known correlation information between uncertain processing times of the jobs to be scheduled. This is joint work with Divya Padmanabhan and Karthyek Murthy at SUTD.

Mathematics; Operations research, mathematical programming; Computer science; Applied computer science

video/mp4

Author affiliation: Singapore University of Technology and Design

2019-07-15

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/70978

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/