Decomposition Methods for Choice-Based Optimization Models

Shadi Sharif Azadeh (), Meritxell Pacheco Paneque () and Michel Bierlaire ()
Additional contact information
Shadi Sharif Azadeh: Delft University of Technology
Meritxell Pacheco Paneque: University of Fribourg
Michel Bierlaire: École Polytechnique Fédérale de Lausanne

A chapter in Combinatorial Optimization and Applications, 2024, pp 277-307 from Springer

Abstract: Abstract 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.

Date: 2024
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:isochp:978-3-031-57603-4_13

Ordering information: This item can be ordered from
http://www.springer.com/9783031576034

DOI: 10.1007/978-3-031-57603-4_13

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().