Publication Type

Journal Article

Version

acceptedVersion

Publication Date

3-2014

Abstract

In this paper, we review recent advances in the distributional analysis of mixed integer linear programs with random objective coefficients. Suppose that the probability distribution of the objective coefficients is incompletely specified and characterized through partial moment information. Conic programming methods have been recently used to find distributionally robust bounds for the expected optimal value of mixed integer linear programs over the set of all distributions with the given moment information. These methods also provide additional information on the probability that a binary variable attains a value of 1 in the optimal solution for 0–1 integer linear programs. This probability is defined as the persistency of a binary variable. In this paper, we provide an overview of the complexity results for these models, conic programming formulations that are readily implementable with standard solvers and important applications of persistency models. The main message that we hope to convey through this review is that tools of conic programming provide important insights in the probabilistic analysis of discrete optimization problems. These tools lead to distributionally robust bounds with applications in activity networks, vertex packing, discrete choice models, random walks and sequencing problems, and newsvendor problems.

Keywords

Distributionally robust bounds, Mixed integer linear program, Conic program

Discipline

Operations and Supply Chain Management

Research Areas

Operations Management

Publication

European Journal of Operational Research

Volume

233

Issue

3

First Page

459

Last Page

473

ISSN

0377-2217

Identifier

10.1016/j.ejor.2013.07.009

Publisher

Elsevier

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1016/j.ejor.2013.07.009

Download

Share

COinS