Piecewise Linear Cost Network Design

Antonio Frangioni () and Bernard Gendron ()
Additional contact information
Antonio Frangioni: Università di Pisa
Bernard Gendron: Université de Montréal

Chapter Chapter 6 in Network Design with Applications to Transportation and Logistics, 2021, pp 167-185 from Springer

Abstract: Abstract This chapter considers one of the most important extensions to “basic” network design models required to accurately model real-world applications: the fact that the capacity on the arcs does not come in an “all-or-nothing” fashion, but with a more complex cost. This often corresponds to the fact that providing capacity actually boils down to provisioning appropriate facilities on the arc. In some simple cases, such as when the facilities can be installed independently from one another or when they are all identical, the models of the previous chapters can be adapted via the simple trick of replicating the arcs. This leads to replicating the flow variables, which might be disadvantageous. Furthermore, in general, the shape of the cost-of-capacity function can be much more complex due to nontrivial interactions between installation of different facilities. However, every reasonable cost-of-capacity function can be approximated as a piecewise linear (possibly, non-convex) one, where the extent of the approximation can be tightly controlled at the cost of the number of breakpoints, and therefore are appropriate for a large variety of real-world applications. This chapter focuses on such models, considering both a very general case and some more restricted ones that serve to illustrate the main concepts. We show that the best models in terms of tightness of the continuous relaxation bound suffer from a significant increase in the number of variables, even more so than the already rather large ones corresponding to simpler cases. Because of this, we review the use of techniques that allow to efficiently solve very large formulations by dynamically generating smaller portions of them. These techniques are instrumental for the practical solution of network design problems with piecewise linear costs.

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

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_6

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

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

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 ().