Please use this identifier to cite or link to this item:
|Title:||Persistence in discrete optimization under data uncertainty|
|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. 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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 13, 2018
WEB OF SCIENCETM
checked on Nov 28, 2018
checked on Jul 27, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.