Pacheco, M., Gendron, B., Lurkin, V., Sharif Azadeh, S., and Bierlaire, M. (2018)

A Lagrangian relaxation technique for the demand-based benefit maximization problem

18th Swiss Transport Research Conference, Ascona, Switzerland

The integration of discrete choice models with Mixed Integer Linear Programming (MILP) models provides a better understanding of customers' preferences to operators while planning for their systems. However, the formulations associated with the former are highly nonlinear and non convex. To overcome this limitation, we propose a linear formulation of a general discrete choice model that can be embedded in any MILP model by relying on simulation. We characterize a demand-based benefit maximization problem to illustrate the use of this approach. Despite the clear advantages of this integration, the size of the resulting formulation is high, which makes it computationally expensive. Given its underlying structure, we use Lagrangian relaxation to decompose it into two separable subproblems: one concerning the decisions of the operator, that can be written as a Capacitated Facility Location Problem (CFLP), and the other the choices of the customers, for which we need to develop additional strategies to decompose it along the two dimensions that, by design, decompose the problem (the customers and the draws). Finally, we consider a subgradient method to optimize the Lagrangian dual.