Given a discrete optimization problem $Z(\mb{\tilde{c}})=\max\{\mb{\tilde{c}}'\mb{x}:\mb{x}\in \mathcal{X}\}$, with objective coefficients $\mb{\tilde{c}}$ chosen randomly from a distribution ${\mathcal{\theta}}$, we would like to evaluate the expected value $E_\theta(Z(\mb{\tilde{c}}))$ and the probability $P_{\mathcal{\theta}}(x^*_i(\mb{\tilde{c}})=k)$ where $x^*(\mb{\tilde{c}})$ is an optimal solution to $Z(\mb{\tilde{c}})$. We call this the persistency problem for a discrete optimization problem under uncertain objective, and $P_{\mathcal{\theta}}(x^*_i(\mb{\tilde{c}})=k)$, the persistence value of the variable $x_i$ at $k$. In general, this is a difficult problem to solve, even if ${\mathcal{\theta}}$ is well specified. In this paper, we show that a subclass of this problem can be solved in polynomial time. In particular, we assume that ${\mathcal{\theta}}$ belongs to the class of distributions ${\Theta}$ with given marginal distributions, or given marginal moments conditions. Under these models, we show that the persistency problem for $\theta^* \in \argmax_{\mathcal{\theta}\in {\Theta}}E_{\mathcal{\theta}}[Z(\mb{\tilde{c}})]$ can be solved via a concave maximization problem. The persistency model solved using this formulation can be used to obtain important qualitative insights to the behaviour 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 the persistency model is capable of obtaining estimates which 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. Numerical results again suggest that our model is able to obtain good estimates of the choice probabilities for this problem.
Article
View A Persistency Model and Its Applications in Choice Modeling