Pacheco, M., Gendron, B., Lurkin, V., Sharif Azadeh, S., and Gendron, B.

Lagrangian relaxation for the demand-based benefit maximization problem

Speaker: Pacheco Meritxell

Workshop on Discrete Choice Models 2018, EPFL

June 22, 2018

The integration of discrete choice models in 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 choice models are highly nonlinear and non convex. In order 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. We consider Lagrangian relaxation to decompose the demand-based benefit maximization problem by taking advantage of the underlying structure of the model, i.e., by considering the two dimensions along which it is possible to decompose the formulation: the customers and the draws from the simulation. Indeed, the former aim at maximizing their own utility whereas the latter represent an independent behavioral scenario. In both cases, all customers and draws are coupled in the objective function, and customers are also linked via the capacity constraints, preventing a direct decomposition of the model.