4.3 Multicommodity Network Flow: Three-Node Example
4.3.1 Minimum Cost Routing Case
For the multicommodity case in a three-node network, all three demand pairs can have pos- itive demand volumes. For clarity, we will use a subscript with demand volume notationh to identify different demands; thus, the demand volume between nodes 1 and 2 will be iden- tified ash12, between 1 and 3 ash13, and between 2 and 3 ash23. For each demand pair, the volume of demand can be accommodated using two paths: one is the direct link path and the other is the alternate path through the third node. In Figure 4.4, we show all the possible paths for each demand pair. The amount of flow on each path is the unknown that is to be determined based on an objective; we denote the unknowns asx12 for path1-2 for demand pair1:2, andx132for path1-3-2, and so on.
F I G U R E 4.4 Three node example with all possible paths.
Much as shown earlier for the single-commodity flow problem, we can write that the demand volume for a node pair must be carried over the two paths. Thus, for demand pair 1:2, we can write
x12+x132=h12. (4.3.1a)
Similarly, for demand pairs1:3and2:3, we can write the following:
x13+x123=h13 (4.3.1b)
x23+x213=h23. (4.3.1c)
These unknown flow amounts, while satisfying the demand volume requirements, must also satisfy capacity limits on any link. We denote capacities of links1-2,1-3, and2-3 byc12,c13, andc23, respectively.
By following the paths listed in Figure 4.4, we note that three different paths from three different demand pairs use link 1-2; they are paths 1-2, 1-2-3, and2-1-3 (see Figure 4.5). Since the sum of the flow over these three paths cannot exceed the capacity,c12, of link1-2, we can write the following inequality (constraint):
x12+x123+x213≤c12. (4.3.2a)
Similarly, for the other two links1-3 and 2-3, we can write
x13+x132+x213≤c13 (4.3.2b)
x23+x132+x123≤c23. (4.3.2c)
We next consider the objective function for minimum cost routing. If the unit costs of routing on paths 1-2, 1-3-2, 1-3, 1-2-3, 2-3, and 2-1-3 are denoted by ξ12,ξ132,ξ13,ξ123,ξ23, andξ213, respectively, then the total routing cost can be written as
total cost=ξ12x12+ξ132x132+ξ13x13+ξ123x123+ξ23x23+ξ213x213. (4.3.3)
F I G U R E 4.5 Link flow on link1-2 for paths for different demand pairs.
Thus, the entire problem can be formulated as follows:
minimize{x} F=ξ12x12+ξ132x132+ξ13x13+ξ123x123+ξ23x23+ξ213x213 subject to x12+x132=h12
x13+x123=h13 x23+x213=h23 x12+x123+x213≤c12 x13+x132+x213≤c13 x23+x132+x123≤c23
x12≥0,x132≥0,x13≥0, x123≥0, x23≥0, x213≥0.
(4.3.4)
The above problem has six nonnegative variables, and six constraints.
Example 4.1 Illustration of solution for Eq. (4.3.4).
Consider demand volumes to be h12=5, h13 =10, and h23 =7, and capacities to be c12=10,c13=10,c23=15(see Figure 4.6). If the unit cost is based on the number of links a flow traverses, that is, 1 for a single-link path and 2 for a two-link path, then we can write ξ12=ξ13=ξ23=1, ξ132=ξ123=ξ213=2. Clearly, the optimal solution to Eq. (4.3.4) is to flow demand volume for each demand pair on the respective direct link path, i.e., we setx∗12=5, x∗13=10,x∗23=7with the other variables taking the value zero since all constraints are satis- fied; here, the total cost at optimality is 22.
However, if the unit costs are different, such as a single link path costing twice that of a two-link path, i.e., ξ12=ξ13=ξ23=2,ξ132=ξ123=ξ213=1, then the optimal solution that satisfies all the constraints would be:x∗12=1,x∗132=4,x∗13=3.5,x∗123=6.5,x∗23=4.5,x∗213=
2.5, with the total cost being 31.
Unlike the ease with which we were able to determine the optimal solution for the single- commodity network flow problem given by Eq. (4.2.3), it is not so easy to do so for the multi- commodity network flow problem given by Eq. (4.3.4) since the latter problem has six vari- ables and six constraints. Thus, we need to resort to an algorithmic approach to solving this problem.
First, recall that problems such as Eq. (4.3.4) are classified as linear programming (LP) prob- lems since all constraints as well as the objective function are linear. LP problems can be solved using the well-known simplex method, and other methods such as the interior point method;
for example, see [164], [515], [711]. While these methods work well in practice, they are fairly complicated algorithms, and their description is beyond the scope of this book. Fortunately, there are many software packages for solving LP problems; for example, see [237] for a sur- vey of LP solvers. Such a package allows a user to enter the problem almost in the way it is described in Eq. (4.3.4).
Example 4.2 Solving Eq. (4.3.4) using CPLEX.
We will illustrate here how to solve Eq. (4.3.4) when the alternate path is cheaper than the direct path, i.e.,ξ12=2,ξ132=1, and so on. We will use CPLEX [158], a popular LP solver for this illustration. In CPLEX, you can enter the data for the second case of Example 4.1 as given below (see Appendix B.5 for additional information):
F I G U R E 4.6 Demand volume and capacity data for three-node network.
Minimize 2 x12 + x132 + 2 x13 + x123 + 2 x23 + x213 subject to
d12: x12 + x132 = 5 d13: x13 + x123 = 10 d23: x23 + x213 = 7
c12: x12 + x123 + x213 <= 10 c13: x132 + x13 + x213 <= 10 c23: x132 + x123 + x23 <= 15 Bounds
0 <= x12 0 <= x132 0 <= x13 0 <= x123 0 <= x23 0 <= x213 End
The above representation is very similar to Formulation (4.3.4). Problem data in CPLEX are entered in the ASCII-based text format; thus, subscripts are directly tagged on to the variables; similarly, note the use of<=instead of≤.
Using CPLEX, we can find the optimal solution to Eq. (4.3.4). Solutions can be displayed by giving the display command as follows:
CPLEX> display solution variables - Variable Name Solution Value
x12 1.000000
x132 4.000000
x13 3.500000
x123 6.500000
x23 4.500000
x213 2.500000
Thus, we have x∗12=1,x∗132=4,x∗13=3.5,x∗123=6.5,x∗23=4.5,x∗213=2.5.
It may be noted that the above solution gives fractional values, which is the case in gen- eral for an LP problem. That is, the multicommodity flow model as given by Eq. (4.3.4) is for variables taking values in the real number space. Sometimes we do have restrictions; for example, some or all variables are allowed to take only integer values. If some of the vari- ables take integral values, then such problems are labeled as mixed integer linear programming (MILP) problems; if all variables take integral values, then such problems are referred to as integer linear programming (ILP) problems. Many real-world communication network problems
are appropriately modeled as MILP or ILP problems; we will illustrate such real examples later in this book.
If variables take only integral values, then this is in fact a form of constraints; thus, they need to be explicitly stated as part of the problem definition. If we do in fact require Eq. (4.3.4) to include the requirement that all variables take integral values, then we can rewrite it as follows:
minimize{x} F=ξ12x12+ξ132x132+ξ13x13+ξ123x123+ξ23x23+ξ213x213 subject to x12+x132=h12
x13+x123=h13 x23+x213=h23 x12+x123+x213≤c12 x13+x132+x213≤c13 x23+x132+x123≤c23
x12≥0,x132≥0,x13≥0, x123≥0, x23≥0, x213≥0 allxs integer.
(4.3.5)
Example 4.3 Multicommodity network flow with integer solution.
Considering again demand volumes to beh12=5,h13=10, andh23=7, and capacities to bec12=10,c13=10,c23=15, in CPLEX, we can enter the above ILP problem in the following way where integrality of variables is explicitly listed:
Minimize 2 x12 + x132 + 2 x13 + x123 + 2 x23 + x213 subject to
d1: x12 + x132 = 5 d2: x13 + x123 = 10 d3: x23 + x213 = 7
c1: x12 + x123 + x213 <= 10 c2: x132 + x13 + x213 <= 10 c3: x132 + x123 + x23 <= 15 Bounds
0 <= x12 <= 10 0 <= x132 <= 10 0 <= x13 <= 10 0 <= x123 <= 10 0 <= x23 <= 10 0 <= x213 <= 10 Integer
x12 x132 x13 x123 x23 x213 End
An important point to note here is that when variables are explicitly declared as integers, an upper bound for these variables is required to be specified since CPLEX assumes that the default for the upper bound is 1. In the above case, we have artificially set the upper bound at 10 since from demand volume values we know that no variables will take more than 10 units of flow at optimality. The optimal solution with integrality requirement is obtained as
x∗12=1,x∗132=4,x∗13=4,x∗123=6,x∗23=5,x∗213=2
and the total cost at optimality is 32.
You may note that the optimal objective cost is higher when the variables take integral values compared to the counterpart when variables are allowed to take real values. It is in- deed true that for a minimization problem, the optimal cost for the integral-valued problem is always higher than or equal to the counterpart problem when the variables take real val- ues, i.e., when integrality is relaxed. Note that the integrality requirement can be thought of as additional constraints to a problem; any time additional constraints are added to a base problem, the optimal objective cost goes up as long as the objective is minimization based.
Finally, note that problems with integrality constraints are in general harder to solve, i.e., more time-consuming in general. Furthermore, a problem with integrality constraints cannot be solved by the simplex method; instead, methods such as branch-and-bound and branch- and-cut are used. Tools such as CPLEX support these methods in addition to the simplex method; this is exactly what happened when we solved Eq. (4.3.5). For very large problems (with many variables and constraints), sometimes commercial solvers are not effective; thus, we resort to developing specialized algorithms by exploiting the structure of a problem; for various approaches to solving large communication network optimization problems, refer to [564].