Please use this identifier to cite or link to this item:
Title: Persistence in discrete optimization under data uncertainty
Authors: Bertsimas, D.
Natarajan, K. 
Teo, C.-P. 
Keywords: Discrete optimization
Semidefinite programming
Issue Date: 2006
Citation: 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.
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
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.


checked on Sep 26, 2022


checked on Sep 26, 2022

Page view(s)

checked on Sep 22, 2022

Google ScholarTM



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