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

Discrete choice models are the state-of-the-art of demand modeling at the disaggregate level. Their integration 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 discrete choice models are highly nonlinear and non convex, and therefore difficult to include in MILP models. 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. This approach can be used to model numerous applications, such as the design of a train timetable in transportation or the shelf space allocation problem in retail. For the sake of illustration, we characterize a demand-based benefit maximization problem where an operator that sells services to a market, each of them at a certain price and with a certain capacity (both to be decided), aims at maximizing its benefit, understood as the difference between the generated revenues and the operating costs. Despite the clear advantages of this integration, the size of the resulting formulation is high, which makes it computationally expensive. Given the underlying structure of the demand-based benefit maximization problem, 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 referring to the choices of customers, for which we need to develop additional strategies to further decompose the resulting formulation along the two dimensions that, by design, allow to decompose the problem (the customers and the draws). Indeed, each customer solves aims at maximizing their own utility, and each draw represents an independent behavioral scenario. However, we notice that it cannot be directly decomposed in independent subproblems for each customer n and scenario r, as all the customers are combined together in the objective function and in the constraints managing capacity allocation, and the draws are also coupled in the objective function. Finally, we consider an iterative method called subgradient method to optimize the Lagrangian dual.