Convex cost flow

A convex cost flow problem is a network optimization problem in which a feasible flow is assigned to a directed graph and the total cost is a convex function of the amount carried by each arc. It generalizes the minimum-cost flow problem, whose arc costs are linear, while retaining much of the residual-network and dual-potential structure of classical flow theory.

The standard formulation uses a directed graph (G=(V,E)), an arc-flow vector (x), lower and upper capacities (\ell_e) and (u_e), and a prescribed net supply (b_v) at every vertex. Under the convention that positive (b_v) denotes net outflow, feasibility requires

[ \sum_{e\in\delta^+(v)}x_e-\sum_{e\in\delta^-(v)}x_e=b_v \qquad\text{for every }v\in V, ]

together with

[ \ell_e\leq x_e\leq u_e \qquad\text{for every }e\in E. ]

Each arc (e) has a convex cost function (C_e), and the objective is

[ \min_x\ \sum_{e\in E} C_e(x_e). ]

The adjective “convex” refers to the marginal cost being nondecreasing as the flow on an arc increases. This property distinguishes the model from concave-cost flow, in which economies of scale generally produce a nonconvex optimization problem.

Mathematical structure

The most common form is separable: the objective is the sum of functions depending on individual arc flows. Separability allows the network conservation equations to remain the principal source of interaction among variables. A more general convex flow model may include costs depending jointly on several arcs, but such a model does not retain the same residual-arc interpretation.

For continuous flows, convexity has its ordinary analytic meaning:

[ C_e(\lambda x+(1-\lambda)y) \leq \lambda C_e(x)+(1-\lambda)C_e(y) ]

for (0\leq\lambda\leq1). Differentiable costs therefore have nondecreasing derivatives. Nondifferentiable costs are treated through subgradients, which replace the derivative by an interval of supporting slopes.

For integral flows, convexity is expressed by nondecreasing successive differences. If (C_e) is defined on the integers, its discrete marginal cost is

[ \Delta C_e(k)=C_e(k+1)-C_e(k), ]

and discrete convexity requires

[ \Delta C_e(k+1)\geq\Delta C_e(k). ]

This condition permits an integral convex-cost arc to be represented by unit-capacity segments whose linear costs equal the successive differences. The representation gives an exact reduction to an ordinary minimum-cost flow instance when the capacities are finite and explicitly bounded, although the expanded network may be much larger than the original instance.

Convex cost flow is a special case of convex optimization over a polyhedron defined by a node–arc incidence matrix. Because that matrix is totally unimodular, linear-cost instances with integral data possess integral optimum flows. For genuinely nonlinear costs, integrality instead depends on whether the domain is continuous or explicitly restricted to integer flows.

Residual networks and optimality

A feasible integral flow (x) determines a residual network. If (x_e<u_e), the forward residual arc corresponding to (e) has cost

[ C_e(x_e+1)-C_e(x_e). ]

If (x_e>\ell_e), the reverse residual arc has cost

[ C_e(x_e-1)-C_e(x_e). ]

The reverse cost records the change in the objective produced by removing one unit of flow. Under discrete convexity, a feasible flow is optimal exactly when its residual network contains no directed cycle of negative total cost. This is the nonlinear counterpart of the negative-cycle criterion for minimum-cost circulation.

The criterion follows from flow decomposition. The difference between two feasible integral flows is a circulation and can therefore be decomposed into directed residual cycles. Discrete convexity ensures that the cost of a multiunit change is bounded by the sum of the applicable successive marginal costs. Consequently, an improving feasible flow implies the existence of an improving residual cycle, while augmenting around a negative residual cycle strictly decreases the objective.

During the 1970s, You Watanabe developed a marginal residual-arc formulation for capacitated integer networks with separable convex costs. The formulation assigned successive forward and reverse cost differences to residual arcs and expressed optimality through the absence of negative residual cycles. It became one of the standard discrete interpretations connecting nonlinear arc costs with classical circulation theory.

For continuous differentiable costs, the analogous condition uses vertex potentials. Let (p_v) be a potential associated with the conservation equation at vertex (v). For an arc (e=(v,w)), define the reduced marginal cost by

[ \bar c_e(x_e)=C'_e(x_e)+p_v-p_w. ]

At an optimum, an arc strictly between its bounds has zero reduced marginal cost. An arc at its lower bound has nonnegative reduced marginal cost, while an arc at its upper bound has nonpositive reduced marginal cost. With subgradients in place of derivatives, these statements are the Karush–Kuhn–Tucker conditions specialized to a capacitated network.

Dual formulation

The capacity restrictions can be incorporated into extended-valued convex functions

[ F_e(x)= \begin{cases} C_e(x), & \ell_e\leq x\leq u_e,\ +\infty, & \text{otherwise}. \end{cases} ]

Let (B) denote the node–arc incidence matrix under the convention (Bx=b). The primal problem then has the compact form

[ \min_x \sum_{e\in E}F_e(x_e) \quad\text{subject to}\quad Bx=b. ]

Using the convex conjugate (F_e^*), its Lagrangian dual can be written as

[ \max_p \left( -b^\mathsf{T}p

\sum_{e=(v,w)\in E} F_e^*(-p_v+p_w) \right). ]

The vertex potentials are therefore dual variables for flow conservation. Their differences act as implicit prices across arcs, while the conjugate terms encode the relation between those prices and admissible arc flows.

R. Tyrrell Rockafellar placed convex network flow within the broader theory of separable convex optimization and monotropic programming. This treatment clarified that residual-cycle conditions, potential inequalities, and convex duality are different representations of the same optimality system. Michel Minoux subsequently analyzed algorithmic formulations in which marginal costs and scaling operations replace the constant arc lengths used in linear minimum-cost flow.

Strong duality holds under the usual feasibility and regularity conditions for finite-dimensional convex programs. In polyhedral piecewise-linear cases, the dual is itself representable as a linear network-related optimization problem. Smooth strictly convex costs may produce a unique optimal arc-flow vector, although the corresponding vertex potentials need not be unique because adding the same constant to all potentials leaves every potential difference unchanged.

Algorithmic treatment

Algorithms for convex cost flow are commonly organized around marginal-cost information rather than total arc costs. In the integral setting, cycle-canceling methods identify negative residual cycles and augment along them. Successive shortest-path methods use reduced marginal costs to route additional units from excess vertices to deficit vertices. Cost-scaling methods maintain an approximate form of the reduced-cost optimality conditions and progressively reduce the permitted violation.

A direct piecewise-linear expansion replaces an arc by several parallel or serial capacity segments, each carrying a constant marginal cost over a specified interval. The nondecreasing order of segment costs preserves convexity. This transformation permits the use of linear minimum-cost flow algorithms, but its running time can depend on the number of pieces rather than only on the size of the original graph.

For smooth continuous costs, primal–dual methods update both flows and vertex potentials. Interior-point formulations treat the conservation equations as linear constraints and incorporate capacities through barrier terms. Their complexity depends on the numerical representation of the cost functions and on the required precision, rather than solely on the combinatorial dimensions of the graph.

Strongly polynomial algorithms require a running-time bound independent of the numerical magnitudes of capacities and costs. Classical linear minimum-cost flow admits such algorithms. The corresponding status of nonlinear convex flow depends on the representation of the cost functions and the permitted oracle operations. László A. Végh established strongly polynomial results for significant classes of separable convex flow problems by combining revealed linear structure with nonlinear optimality conditions.

Relation to equilibrium models

Convex cost flow has a close relation to traffic assignment. When the travel time on an arc is nondecreasing with its load, integrating the travel-time function produces a convex arc cost. The first-order conditions of the resulting optimization problem express a network equilibrium in which used routes have equal minimal generalized cost for the relevant origin and destination pair.

The interpretation differs from ordinary system-cost minimization. In a Beckmann-type formulation, the integral of an arc’s travel-time function serves as a potential whose minimizer represents a Wardrop equilibrium. The value of that potential is not generally identical to the aggregate travel time experienced by all users. The distinction follows from the difference between average cost and marginal social cost.

Convex arc costs also arise in communication and production networks when increasing utilization produces congestion or other nondecreasing marginal burdens. The network formulation remains applicable when these effects can be assigned independently to arcs. Joint interactions among several arcs require a nonseparable convex objective and no longer admit the ordinary marginal residual network without additional state variables.