  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.
