TY - JOUR
T1 - A Lagrangian decomposition scheme for choice-based optimization
AU - Pacheco Paneque, Meritxell
AU - Gendron, Bernard
AU - Sharif Azadeh, Shadi
AU - Bierlaire, Michel
PY - 2022
Y1 - 2022
N2 - Choice-based optimization problems are the family of optimization problems that incorporate the stochasticity of individual preferences according to discrete choice models to make planning decisions. This integration brings non-convexity and nonlinearity to the associated mathematical formulations. Previously, the authors have tackled these issues by introducing a simulation-based approximation of the choice model with the aim of linearizing it. Nevertheless, already existing exact methods and state-of-the-art commercial solvers fail to solve relevant instances. In this paper, we propose a novel Lagrangian decomposition method inspired by scenario decomposition and scenario grouping in the stochastic programming framework for the purpose of solving choice-based optimization problems. In addition, we develop a tailored algorithm to generate feasible solutions to the original problem from the solution of the Lagrangian subproblem. Hence, at each iteration of the subgradient method, which is used to solve the Lagrangian dual, 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 also show that scenario grouping leads to high-quality feasible solutions and lower duality gaps.
AB - Choice-based optimization problems are the family of optimization problems that incorporate the stochasticity of individual preferences according to discrete choice models to make planning decisions. This integration brings non-convexity and nonlinearity to the associated mathematical formulations. Previously, the authors have tackled these issues by introducing a simulation-based approximation of the choice model with the aim of linearizing it. Nevertheless, already existing exact methods and state-of-the-art commercial solvers fail to solve relevant instances. In this paper, we propose a novel Lagrangian decomposition method inspired by scenario decomposition and scenario grouping in the stochastic programming framework for the purpose of solving choice-based optimization problems. In addition, we develop a tailored algorithm to generate feasible solutions to the original problem from the solution of the Lagrangian subproblem. Hence, at each iteration of the subgradient method, which is used to solve the Lagrangian dual, 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 also show that scenario grouping leads to high-quality feasible solutions and lower duality gaps.
KW - Choice-based optimization
KW - Combinatorial optimization
KW - Lagrangian decomposition
KW - Random utility models
KW - Scenario decomposition
KW - Scenario grouping
UR - http://www.scopus.com/inward/record.url?scp=85135957758&partnerID=8YFLogxK
U2 - 10.1016/j.cor.2022.105985
DO - 10.1016/j.cor.2022.105985
M3 - Article
AN - SCOPUS:85135957758
SN - 0305-0548
VL - 148
JO - Computers and Operations Research
JF - Computers and Operations Research
M1 - 105985
ER -