Given a discrete maximization problem with a linear objective function where the coefficients are chosen randomly from a distribution, we would like to evaluate the expected optimal value and the marginal distribution of the optimal solution. We call this the persistency problem for a discrete optimization problem under uncertain objective, and the marginal probability mass function of the optimal solution is named the persistence value. In general, this is a difficult problem to solve, even if the distribution of the objective coefficient is well specified. In this paper, we solve a subclass of this problem when the distribution is assumed to belong to the class of distributions defined by given marginal distributions, or given marginal moment conditions. Under this model, we show that the persistency problem maximizing the expected objective value over the set of distributions can be solved via a concave maximization model. The persistency model solved using this formulation can be used to obtain important qualitative insights to the behavior of stochastic discrete optimization problems. We demonstrate how the approach can be used to obtain insights to problems in discrete choice modeling. Using a set of survey data from a transport choice modeling study, we calibrate the random utility model with choice probabilities obtained from the persistency model. Numerical results suggest that our persistency model is capable of obtaining estimates that perform as well, if not better, than classical methods, such as logit and cross-nested logit models. We can also use the persistency model to obtain choice probability estimates for more complex choice problems. We illustrate this on a stochastic knapsack problem, which is essentially a discrete choice problem under budget constraint.
Stored only when both papers are in the corpus — 109 citations exist upstream.
Imported from OpenAlex (CC0) — nothing here is generated.