Structural Investigation of Piecewise Linearized Network Flow Problems
研究了每条弧的流量落在多个预定义区间内的网络流问题，通过线性不等式强化多弧子结构的公式，并给出度数为2的节点路径的完整多面体描述，计算表明切割平面能显著提升求解器性能。
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.