Pacheco, M., Gendron, B., Sharif Azadeh, S., and Bierlaire, M. (2021)

A Lagrangian decomposition scheme for choice-based optimization

We consider a family of mixed-integer linear programming (MILP) problems that explicitly includes choice models using the random utiity paradigm. In order to use behavioral models published in the literature, the specification relies on a simulation-based approximation to linearize the choice model. The price to pay is the large size of the approximation. To enhance the tractability of the problem, we propose a Lagrangian decomposition methodology inspired by scenario decomposition and scenario grouping in the stochastic programming framework. In addition, we develop an algorithm that exploits the properties of choice-based optimization in order to generate feasible solutions to the original problem from the solution of the Lagrangian problem. Hence, at each iteration of the subgradient method, we provide both an upper and a lower bound to the original problem. This enables the calculation of the duality gap to assess the quality of the generated solutions. Computational results show that the decomposition method provides solutions with optimality gaps below 0.5\% and restricted duality gaps within low computational times. We show that scenario grouping leads to high quality feasible solutions and lower duality gaps.