Optimization Online


Exploiting Partial Correlations in Distributionally Robust Optimization

Divya Padmanabhan (divya_padmanabhan***at***sutd.edu.sg)
Karthik Natarajan (karthik_natarajan***at***sutd.edu.sg)
Karthyek Murthy (karthyek_murthy***at***sutd.edu.sg)

Abstract: In this paper, 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, the complexity of solving which is related to characterizing a suitable projection of the convex hull of the set $\{(\bold{x}, \bold{x}\bold{x}'): \bold{x} \in \mathcal{X}\}$ where $\mathcal{X}$ is the feasible region. 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 Project Evaluation and Review Technique (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.

Keywords: Distributionally Robust Optimization, Correlations, Appointment Scheduling, Tractable,

Category 1: Robust Optimization

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Combinatorial Optimization (Polyhedra )

Citation: Singapore University of Technology and Design, October 2018

Download: [PDF]

Entry Submitted: 10/21/2018
Entry Accepted: 10/22/2018
Entry Last Modified: 12/02/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society