On the Polyhedron of the Overflow Model for the Network Flow Problem with Piecewise Linear Costs

It is well known that the network flow costs can be approximated with piecewise linear function. The network optimization problem with piecewise linear separable costs is formulated as a mixed integer programming. The fixedcharge problem is a special case of this problem. The polyhedral approach to mixed integer programming is an outerconvexification scheme, which capitalizes on the fact that convex relaxationsmore precisely polyhedral relaxations ofmixed integer programming are easier to solve than MIP. In this approach one attempts to solve successively stronger linear programming relaxations of MIP.Let S denote the feasible set of MIP and P denote the linear programming (LP) relaxation of S, Let conv(S) denote the convex hull of S. Since the coefficient and right hand side matrices are rational, conv(S) or P is a rationalpolyhedron, that is, the intersection of a finite number of halfspaces defined by inequalities with rational coefficients.However, in general, describing the constraints of conv(S) as an explicit system of linear inequalities is difficult