Please use this identifier to cite or link to this item: https://doi.org/10.1007/s10107-006-0710-z
Title: Persistence in discrete optimization under data uncertainty
Authors: Bertsimas, D.
Natarajan, K. 
Teo, C.-P. 
Keywords: Discrete optimization
Persistence
Semidefinite programming
Issue Date: 2006
Source: Bertsimas, D., Natarajan, K., Teo, C.-P. (2006). Persistence in discrete optimization under data uncertainty. Mathematical Programming 108 (2-3) : 251-274. ScholarBank@NUS Repository. https://doi.org/10.1007/s10107-006-0710-z
Abstract: An important question in discrete optimization under uncertainty is to understand the persistency of a decision variable, i.e., the probability that it is part of an optimal solution. For instance, in project management, when the task activity times are random, the challenge is to determine a set of critical activities that will potentially lie on the longest path. In the spanning tree and shortest path network problems, when the arc lengths are random, the challenge is to pre-process the network and determine a smaller set of arcs that will most probably be a part of the optimal solution under different realizations of the arc lengths. Building on a characterization of moment cones for single variate problems, and its associated semidefinite constraint representation, we develop a limited marginal moment model to compute the persistency of a decision variable. Under this model, we show that finding the persistency is tractable for zero-one optimization problems with a polynomial sized representation of the convex hull of the feasible region. Through extensive experiments, we show that the persistency computed under the limited marginal moment model is often close to the simulated persistency value under various distributions that satisfy the prescribed marginal moments and are generated independently.
Source Title: Mathematical Programming
URI: http://scholarbank.nus.edu.sg/handle/10635/44206
ISSN: 00255610
DOI: 10.1007/s10107-006-0710-z
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

21
checked on Dec 7, 2017

WEB OF SCIENCETM
Citations

15
checked on Nov 23, 2017

Page view(s)

51
checked on Dec 11, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.