A Local Iterative Linear Approximation Framework to Integrate Discrete Choice and Mathematical Optimization Models

We consider a class of optimization problems having the following common feature: user demands appear as a term, whose values depend on the discrete choice made by each individual in a certain population. This type of problems arise frequently, for instance in revenue management applications of transportation systems. In the literature, discrete choice models and mathematical programming are known to be effective, respectively in describing users behaviour, and formulating optimization problems. Their integration, to account for user choices which depend on optimization decisions, is however an issue.We introduce an algorithmic methodology to perform such an integration. Its main idea is to perform local approximations of the choice probabilities in terms of simplified functions, to formulate them as terms of a mixed integer program representing the optimization problem, and to exploit the solutions obtained by the optimization process to refine the local approximation.We evaluate its applicability and effectiveness through experiments on a revenue maximization problem from the literature, and a few of its variants, exploiting two real world discrete choice models.Our experiments show our approach to outperform recent ones from the literature by orders of magnitude in terms of computing time, improving solutions accuracy as well.