TY - JOUR A1 - Liers, Frauke A1 - Merkert, Maximilian T1 - Structural Investigation of Piecewise Linearized Network Flow Problems N2 - 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. KW - Combinatorial optimization KW - Complete description KW - Network flow problems KW - Piecewise linear functions Y1 - 2016 U6 - https://doi.org/10.1137/15M1006751 VL - 26 SP - 2863 EP - 2886 ER - TY - JOUR A1 - Bärmann, Andreas A1 - Liers, Frauke A1 - Martin, Alexander A1 - Merkert, Maximilian A1 - Thurner, Christoph A1 - Weninger, Dieter T1 - Solving network design problems via iterative aggregation JF - Mathematical Programming Computation N2 - In this work, we present an exact approach for solving network design problems that is based on an iterative graph aggregation procedure. The scheme allows existing preinstalled capacities. Starting with an initial aggregation, we solve a sequence of network design master problems over increasingly fine-grained representations of the original network. In each step, a subproblem is solved that either proves optimality of the solution or gives a directive where to refine the representation of the network in the subsequent iteration. The algorithm terminates with a globally optimal solution to the original problem. Our implementation uses a standard integer programming solver for solving the master problems as well as the subproblems. The computational results on random and realistic instances confirm the profitable use of the iterative aggregation technique. The computing time often reduces drastically when our method is compared to solving the original problem from scratch. KW - Aggregation KW - Network design KW - Combinatorial optimization KW - Mixed-integer programming KW - Branch-and-cut Y1 - 2015 U6 - https://doi.org/10.1007/s12532-015-0079-1 VL - 7 IS - 2 SP - 189 EP - 217 ER -