Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Distributionally robust mixed integer linear programs: Persistency models with applications

Presented at IMS
by

Karthik Natarajan

on 15 July 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Distributionally robust mixed integer linear programs: Persistency models with applications

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)

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.

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
Full transcript