Network optimization

Many real-life optimization problems relate with transportation of items on a network. This is clearly a relevant class of problems in supply chain management, but also many telecommunications problems involve networks on which data flow, rather than physical commodities. More surprisingly, some dynamic problems may be represented as network models on which items flow in time, rather than space. In this section we describe two stylized models that are building blocks for dealing with more realistic problems. To begin with, we should formally define what we mean by a “network.”

DEFINITION 12.8 (Network) A network is a collection of nodes and arcs. Let N be the set of nodes, which are typically physical locations. Arcs represent links between pairs of locations and are actually pairs (i,j) of nodes. If the pair is ordered, we have a directed network; otherwise, we have an undirected network.²² In a directed network, arcs have a specific direction along which items flow. Let us denote the set of arcs by A, which is a subset of the Cartesian product of nodes, A ⊆ N × N. Numerical information may be attached to arcs, such as transportation capacity, and nodes, such as the maximum throughput of a logistic facility.

A very simple two-level network is depicted in Fig. 12.8. This is a kind of network considered in our first model, which is known as the transportation problem, even though it is actually a very simplified view of a real-life transportation problem. The network is two-level since we have two disjoint sets of nodes: the set S of source nodes and the set D of destination nodes. Referring to the figure, we have S = {A, B, C} and D = {1, 2, 3, 4, 5, 6}. Examples of (directed) arcs are (A, 1) and (C, 4); there is no (B, 6) arc. Also, when there is no arc connecting two sources or two destinations; we say that the network is bipartite. Destination nodes may represent retail stores, which are characterized by a demand d_j, j ∈ D, measured on a timespan of interest. In the prototype transportation model, only one type of commodity is considered. Source nodes might represent production plants, with a given limited capacity R_i, i ∈ S, measured over the same timespan as demand. For each source–destination pair, i.e., for each arc (i, j), i ∈ S, j ∈ D, we have a unit transportation cost c_ij. This is considered as a variable linear cost; clearly, this is just a very rough approximation of a real-life transportation cost. The transportation problem consists in finding the minimum-cost set of flows, over all of the links (i, j), such that demand is met and plant capacities are not exceeded.

Fig. 12.8 A two-level, bipartite network corresponding to a transportation problem.

To represent the transportation problem as a mathematical programming model, we have to find suitable decision variables first. In this case, it is fairly evident that we need one decision variable for each link (i, j); let x_ij be the flow on each arc. The resulting linear programming model is

The objective function (12.33) is a sum over all the pairs of nodes, and it amounts to the total transportation cost. The expression above assumes that there is an arc for any source–destination pair, which need not be the case. We could think of associating a suitably high cost c_ij with nonexistent arcs, so that they are never used. A possibly more elegant solution is to sum directly over the set A of arcs: . The constraint (12.34) ensures that demand is met at each destination node, by summing inflows from plants. The capacity constraint, limiting outflows from any source, is represented by Eq. (12.35). Notice the reversal of roles between subscripts i and j in constraints (12.34) and (12.35). This model is extremely simplistic and provides us with only a starting point for further modeling. To begin with, it is a static model ignoring time patterns in demand (demand variability). In principle, it is easy to extend the model to a dynamic one by introducing time-varying demand d_jt and inventory variables at nodes. By the same token, we could consider diversified production costs across the plants, different items or families, and a more realistic transportation cost structure, possibly including fixed charges and economies of scale.

Fig. 12.9 A network corresponding to a minimum-cost flow problem.

Another classical model is the minimum-cost flow problem, which features a multilevel network like the one depicted in Fig. 12.9. Sometimes, networks are arranged in well-defined layers, which may correspond to factories, warehouses, large distribution centers, and retail stores. To be as general as possible, let us deal with an unstructured network, in which one specific node denoted by s is the source of a given flow t, which must be routed to the destination node denoted by d. Each arc (i, j) in the network is directed and associated with a cost c_ij, and we want to route the flow from s to d at minimum cost. In a generic problem, we might have several commodities, more than one source and one destination, as well as capacities on both nodes and arcs. Let us consider a basic model, whereby flow on arc (i,j) cannot exceed an upper bound u_ij. Like in the transportation problem, we have one set of decision variables, the flow x_ij on arc (i, j). The only issue with this basic minimum-cost flow model is representing conservation of flows at each node: The flow going out of a node must equal the flow going into the node. When considering in- and outflows, we must account for arcs going into and out of a node, plus possible exogenous input and output flows. Let F_j be the net outflow of node j ∈ N. The conservation of flows at node j reads as follows:

Note that if the net outflow F_j is positive, it represents the flow absorbed at node j; if it is negative, it represents flow generated at node j. The left-hand side of the equality represents the node inflow, i.e., the sum of flows on all arcs (i,j) entering node j. The right-hand side includes the node outflow, i.e., the sum of flows on all arcs (j, i) going out of node j, plus the net outflow F_j. In the simple network of Fig. 12.9, F_j is zero for all nodes except source and destination. With our convention, F_s = −t and F_d = t, and we may write the model as follows:

We express the objective function (12.36) as a sum over the arc set A. We might also mention that not all of the flow balance constraints (12.37) need be written. Summing all of them, we get an identity 0 = 0, implying that they are not all linearly independent. We may get rid of any one of them, but this is not relevant with respect to model formulation and is accommodated by solution procedures.

The transportation and the minimum-cost flow problems may be solved by any linear programming solver. Actually, they have very specific structures that may be exploited by special purpose solution procedures. State-of-the-art commercial solvers offer such procedures, and are even able to detect network structure automatically. Such algorithmic tricks are beyond the scope but there is one more feature that is worth mentioning. The decision variables x_ij are not restricted to integer values. However, if all of the problem data are integers, it can be shown that the solution of the problem will be integer even if we apply a solver for continuous LPs. This depends on the peculiar structure of the constraint matrix, which defines a polyhedron whose vertices have integer coordinates. Unfortunately this nice property is lost when we introduce different commodities in the model, competing for limited transportation capacity.