Lagrangian relaxation for the demand-based benefit maximization problem

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 and by discerning the decisions of the two sides involved in the problem: the operator and the customers.