Structural Investigation of Piecewise Linearized Network Flow Problems

Journal article
(Original article)

Publication Details

Author(s): Liers F, Merkert M
Journal: SIAM Journal on Optimization
Publisher: Society for Industrial and Applied Mathematics
Publication year: 2016
Volume: 26
Journal issue: 4
Pages range: 2863-2886
ISSN: 1052-6234
Language: English


In this work we study polyhedra in the context of network flow problems, in which the flow value on each arc lies in one of several predefined intervals. This is motivated by nonlinear problems on transportation networks, where nonlinearities are handled by piecewise linear approximation or relaxation—a common and established approach in many applications. Several methods for modeling piecewise linear functions which provide a complete description for a single network arc are known. However, in general this property is lost when considering multiple arcs. We show how to strengthen the formulation for specific substructures consisting of multiple arcs by linear inequalities. For the case of paths of degree-two nodes we give a complete description of the polyhedron projected to the integer variables. Our model is based on—but not limited to—the connection between binary variables and flow variables that is used in the multiple choice method or the convex combination method; we also show how to transfer our results to a formulation based on the incremental method. Computational results show that a state-of-the-art mixed-integer program solver greatly benefits from using our cutting planes for random and realistic network topologies.

FAU Authors / FAU Editors

Liers-Bergmann, Frauke Prof. Dr.
Professur für Angewandte Mathematik (Ganzzahlige und robuste Optimierung)
Merkert, Maximilian
Economics - Discrete Optimization - Mathematics (EDOM)

Additional Organisation
Economics - Discrete Optimization - Mathematics (EDOM)

How to cite

Liers, F., & Merkert, M. (2016). Structural Investigation of Piecewise Linearized Network Flow Problems. SIAM Journal on Optimization, 26(4), 2863-2886.

Liers, Frauke, and Maximilian Merkert. "Structural Investigation of Piecewise Linearized Network Flow Problems." SIAM Journal on Optimization 26.4 (2016): 2863-2886.


Last updated on 2018-18-10 at 03:20