Decomposition Methods for Choice-Based Optimization Models

Transportation and mobility service providers face challenges when designing their services to ensure that resources align with demand effectively. To address this problem, one approach is to integrate individual preferences directly into operational decisions using a mixed-integer linear model. The integration of these models introduces non-convexity and non-linearity into the mathematical frameworks. Attempts have been made to manage these complexities by approximating the choice model through simulation, aiming for linearization. Established exact methods and leading commercial solvers struggle to effectively resolve relevant instances. This chapter provides a Lagrangian decomposition method coupled with scenario decomposition and scenario grouping to address choice-based optimization problems. We devise a custom algorithm to generate viable solutions for the original problem from the solution of the Lagrangian subproblem. Consequently, at each iteration of the subgradient method (used to solve the Lagrangian dual), we offer both an upper and a lower bound to the original problem. This facilitates the computation of the duality gap to evaluate solution quality. In addition, we argue what decomposition methods are suitable for the framework and present potential extensions and future work.