Abstract: 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, the complexity of solving which is related to characterizing a suitable projection of the convex hull of the set {(x, xx’ ) : x ∈ X } where 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 the newsvendor problem, Project Evaluation and Review Technique (PERT) networks and linear assignment problems.

Biography: Karthik Natarajan is a Professor at the Engineering Systems and Design pillar at the Singapore University of Technology and Design. His research interest lie primarily in operations research and solving optimization problems where uncertainty plays a key role. He serves as the Associate Head of the Pillar (Undergraduate Studies) and serves as an Associate Editor for the journals – Operations Research and Management Science.