• search hit 7 of 24
Back to Result List

Structural Investigation of Piecewise Linearized Network Flow Problems

Submission Status:published
  • In this work we study polyhedra in the context of network flow problems, where 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 are known which provide a complete description for a single network arc. 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 multiple choice 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 MIP-solver greatly benefits from using our cutting planes for random and realistic network topologies.

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Frauke Liers, Maximilian Merkert
DOI:https://doi.org/10.1137/15M1006751
Document Type:Article
Language:English
Date of Publication (online):2016/12/21
Date of first Publication:2016/09/27
Release Date:2016/09/27
Tag:Combinatorial optimization; Complete description; Network flow problems; Piecewise linear functions
Volume:26
First Page:2863
Last Page:2886
Institutes:Friedrich-Alexander-Universität Erlangen-Nürnberg
Subprojects:B06
B07