Structural Investigation of Piecewise Linearized Network Flow Problems

Beitrag in einer Fachzeitschrift

Details zur Publikation

Autor(en): Liers F, Merkert M
Zeitschrift: SIAM Journal on Optimization
Verlag: Society for Industrial and Applied Mathematics
Jahr der Veröffentlichung: 2016
Band: 26
Heftnummer: 4
Seitenbereich: 2863-2886
ISSN: 1052-6234
Sprache: Englisch


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-Autoren / FAU-Herausgeber

Liers-Bergmann, Frauke Prof. Dr.
Professur für Diskrete Optimierung in den Ingenieurwissenschaften
Merkert, Maximilian
Lehrstuhl für Wirtschaftsmathematik

Zusätzliche Organisationseinheit(en)
Lehrstuhl für Wirtschaftsmathematik


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.


Zuletzt aktualisiert 2018-18-10 um 03:20