A Lagrangian relaxation technique 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 the preferences of the customers to the operators while planning for their systems. However, the formulations associated with 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 formulation 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 formulation, the size of the resulting problem is high, which makes it computationally expensive. Given its underlying structure, we consider Lagrangian relaxation to decompose it into two separable subproblems: one concerning the decisions of the operator and the other the choices of the customers. We can write the former as a Capacitated Facility Location Problem (CFLP), for which well-known solution methods can be used. We develop a tailored algorithm to solve the latter by assuming that the utility function is decreasing as a function of the price. We then define a subgradient method to optimize the problem on the Lagrangian multipliers (Lagrangian dual)