Models for Network Flow and Network Design Problems with Piecewise Linear Costs

In modeling real-world applications of network design, a difficulty often encountered is the fact that capacity on the arcs are not ”all-or-nothing” but incur a more complex cost. Often, the associated cost function can be approximated with a piecewise linear function (possibly non-convex). We review in this chapter some pioneering work of Bernard Gendron on multicommodity flow and network design problems with piecewise linear costs, and we also briefly address related recent works that build on the ideas developed by Bernard Gendron.