Optimization Online


A Persistency Model and Its Applications in Choice Modeling

Karthik Natarajan(matkbn***at***nus.edu.sg)
Song Miao(miao.song***at***gmail.com)
Teo Chung-Piaw(bizteocp***at***nus.edu.sg)

Abstract: 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.

Keywords: Discrete choice models, Persistency

Category 1: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 03/20/2007
Entry Accepted: 03/21/2007
Entry Last Modified: 03/20/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society