Exact Methods for Fixed-Charge Network Design

Teodor Gabriel Crainic () and Bernard Gendron ()
Additional contact information
Teodor Gabriel Crainic: Université du Québec à Montréal
Bernard Gendron: Université de Montréal

Chapter Chapter 3 in Network Design with Applications to Transportation and Logistics, 2021, pp 29-89 from Springer

Abstract: Abstract This chapter is dedicated to exact algorithms for single-commodity and multicommodity fixed-charge network design. These problems are notoriously difficult, since they are in general strongly N P $$\mathcal {N}\mathcal {P}$$ -hard. In addition, their objective function includes both fixed design costs and variable transportation costs, which results in complex tradeoffs that complicate the task of finding optimal solutions. Multicommodity capacitated fixed-charge problems are particularly challenging, since even their LP relaxations are difficult to solve, as they are often highly degenerate. In addition, the formulations of these problems display a large number of both variables and constraints. In this context, decomposition methods that exploit subproblem structures are useful to seek optimal solutions for such problems. This chapter is divided into three parts. Part I presents relaxations that can improve the quality of the lower bounds, while exploiting the subproblem structures. Part II focuses on enumeration algorithms that use the modeling techniques covered in Part I. Part III is dedicated to the solution of large-scale instances by combining the advanced enumeration algorithms of Part II with heuristic methods and by exploiting parallel computing.

Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (2)

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:sprchp:978-3-030-64018-7_3

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

DOI: 10.1007/978-3-030-64018-7_3

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().