The Overflow Model for Network Optimization Problems with Piecewise Linear Costs

Consider a complete graph( directed or undirected) with the node set N and the link set E. It is assumed that a nonnegative traffic matrix T = (tij j(i; j) 2 E)and a nonnegative capacity matrix r = (rij j(i; j) 2 E) are given. So inthe undirected case these matrices are symmetric. The overflow variables, ¸(ij)k, indicate how much flow on the link(i; j) overflows via a third node k. Obviously ¸(ij)k ¸ 0 must hold. Also the flow from (or between) i to j is equal to xij = tij + P k6=i;j(¸(ik)j +¸(kj)i¡¸(ij)k): This flow includes the offered traffic for the corresponding origin–destination (OD) pair and also the negative or positive effects of all the routing decisions. It is necessary to bound the aboveexpression not to be greater than the capacity, rij ; 0 · tij ¡P k ¸(ij)k + P k ¸(ik)j + P k ¸(kj)i · rij If there is a lower bound lij on the flow, then for a feasible flow : P k6=i;j(¸(ij)k ¡ ¸(ik)j ¡ ¸(kj)i) · tij ¡ lij ; 8(i; j) 2 E:It is preferred to formulate the problem using these variables because it is not necessary to define an index indicating commodities for the variables. For a feasible set of overflow variables, there would be a corresponding multicommodityflow, not necessarily uniquely determined. One can easily calculate the flow on different paths for each commodityusing the values of the overflow variables ¸(ij)k[3]. The other advantage of this model over the link–path model is thepolynomial number of the variables[1]. The cost of the flow on each link is assumed to be a piecewise linear function of the flow. Every nonlinear orstepwise function can be approximated by piecewise linear functions, the larger the number of line segments, the moreexact the approximation