**Probability**

**Optimization**

Activity network

Activity network

Uncertainty

Dependence

Univariate

Marginal

Moments

Multivariate

Marginal Moments

Complexity

s

t

s

t

Constraint based

formulation

Find the longest path in the directed acyclic graph from node s to t where arcs denote activities and arc lengths denote time to complete activities.

i

j

c

ij

Mixed 0-1 linear program

Mixed 0-1 linear programming is NP-hard.

Common techniques:

- Finding polynomial time solvable instances

- Exact algorithms: Branch & bound, Cutting planes

- Approximation algorithms: SDP, Rounding

- Heuristics

Jaynes 1957, Cover & Thomas 1991: This is the joint distribution that ``maximizes'' the entropy which is a measure of unpredictability:

for a given set of univariate marginals.

Ruschendorf 1983: This is the joint distribution

that ``maximizes'' the expected sum excess of T:

for a given set of univariate marginals.

Independence

Doan & Natarajan 2012

**This talk is based on a review article in the European Journal of Operational Research (2013):**

Distributionally Robust Mixed Integer Linear Programs: Persistency Models with Applications

Li Xiaobo (SUTD), Karthik Natarajan (SUTD), Teo Chung-Piaw (NUS) and Zheng Zhichao (SMU)

Distributionally Robust Mixed Integer Linear Programs: Persistency Models with Applications

Li Xiaobo (SUTD), Karthik Natarajan (SUTD), Teo Chung-Piaw (NUS) and Zheng Zhichao (SMU)

Expected Optimal Objective Value

Distributionally Robust Bound on the

Expected Optimal Objective Value

**Main Message:**

Tools of convex conic programming are useful in the probabilistic analysis of discrete optimization with distributional uncertainty.

Tools of convex conic programming are useful in the probabilistic analysis of discrete optimization with distributional uncertainty.

Cross

Moments

Weighted vertex packing

Given a graph with weights on vertices, find a subset of vertices of total maximum weight such that no two vertices are adjacent.

Stochastic optimization (Expected value):

- Independent distributions

- Dependence using copulas, scenarios

Robust optimization (Worst-case value):

- Uncertainty set using polytopes, ellipsoids

Distributional robust optimization

(Worst-case expected value):

- Moments (FOCUS OF THIS TALK)

- Relative entropy

LINEAR ASSIGNMENT PROBLEM:

(i) Hagstrom 1989:

For a directed acyclic graph with independent arc lengths and restricted to taking two possible values each, MEAN is #P-complete.

Furthermore it cannot be computed in time polynomial in the number of points in the range of the longest path unless P = NP.

(ii) Ball 1995, Mohring 2001:

The two-state version of MEAN for a series-parallel graph is NP-hard in the weak sense.

For a series-parallel graph with arc lengths restricted to {0,1,2,...,q} MEAN can be computed in time polynomial in the size of the network and q.

Persistency and the Proof Technique

i) Identify decision variables using moments of c and x(c).

ii) Identify ``necessary'' conditions that is conic representable for the

variables to satisfy for all distributions in the set.

iii) Show that the constraints are sufficient by constructing a

distribution (or a sequence of distributions) that attains the bound.

Polynomial time solvable

NP-hard

Lai & Robbins 1976: This is the joint distribution

that ``maximizes'' the expected maximum:

for a given set of univariate marginals.

Perfect positive dependence

Almost perfect negative dependence

Mean, variance and covariance representation:

Moment cone

Cone of nonnegative polynomials

Moment cone and its dual for R = Positive semidefinite cone

(Computationally tractable)

Moment cone and its dual for R = Completely positive and Copositive cone

(Computationally intractable)

n

DUALITY

n

+

ACTIVITY NETWORK:

(i) Aldous 2001, Mezard and Parisi 1985:

For i.i.d exponentially distributed random variables with mean 1, the asymptotic MEAN for the linear assignment problem is:

(ii) Linussion and Wastlund 2004, Nair Prabhakar and Sharma 2005: Finite MEAN for i.i.d exponential with mean 1:

i) For every realization of uncertainty, we need to solve a mixed 0-1 linear program.

ii) Notions of dependence is explicitly captured with correlations.

iii) MEAN-UB is distributionally robust - Worst case expected network completion time.

iv) A distribution (or a limiting sequence of distributions) that attains the bound.

Vertex based formulation

Complexity

Marginal distribution

i) Murty & Kabadi & 1987, Dickinson & Gibjen 2012:

Checking if there exists multivariate nonnegative random variables with given mean-covariance is NP-hard.

ii) Bertsimas, Doan, Natarajan & Teo 2010:

MEAN-UB is NP-hard for linear programs with mean-covariance and support R

n

MEAN-UB is computable in polynomial time for R

when number of vertices K is polynomial in size n

n

For 0-1 linear programs with a compact convex hull this problem can be solved in polynomial time.

Example: Activity network crashing problem is solvable in polynomial time under this model.

Independence

Extremal distribution

Activity network

Weighted vertex packing

Random walk

Newsvendor & Extensions

(i) Decision variables (ii) Objective & constraints (iii) Tightness

Meiljson & Nadas 1979, Bertsimas, Natarajan & Teo 2006

Linear assignment problem: Exponential with mean 1

For the activity network with partition formed by set of activities (arcs) entering a node and support R

MEAN-UB can be solved in polynomial time.

n

MEAN-UB

Weaker upper bound

Deterministic WVP

Generic Approach:

s

t

APPLICATIONS

x = Persistency or criticality index of arc (1,3)

13

n = 5

PERSISTENCY

Arc sine law

Density function as

n approaches infinity

Single item newsvendor (Scarf 1958)

Multi-dimensional newsvendor

Cost

Revenue

Revenue

Cost

2-stage distributionally robust linear program

Copositive program

Second stage cost

Moment representation

While CP and CO computationally intractable cones, there exists a sequence or hierarchy of positive semidefinite cones & nonnegative cones that asymptotically approach these cones.

DISTRIBUTIONAL ROBUST MIXED 0-1 LINEAR PROGRAMS

MEAN-UB

MEAN-UB

MEAN-UB