7.6 Duality of the MCNF Problem
7.6.2 General Case: Minimum Cost Routing
Recall that minimum cost routing for the MCNF problem was discussed earlier in Sec- tion 4.3.1 in its index-based formulation presented in Section 4.4. Notations for this and other related problems are summarized in Table 7.1. Thus, we start with the general formulation corresponding to Eq. (7.6.1):
minimize{x} F= K
k=1 Pk
p=1
ξkpxkp subject to
Pk
p=1xkp=hk, k=1,2, ...,K K
k=1 Pk
p=1
δkp xkp≤c, =1,2, ...,L
xkp≥0, p=1,2, ...,Pk, k=1,2, ...,K.
(7.6.5)
The above LP problem is then the network flow relaxation of the following MCSPRF problem:
minimize{w} F=K
k=1 Pk
p=1
ξkpxkp(w) subject to
Pk
p=1xkp(w)=hk, k=1,2, ...,K K
k=1 Pk
p=1
δkp xkp(w)≤c, =1,2, ...,L w1,w2, ...,wL∈W
xkp(w)≥0, p=1,2, ...,Pk, k=1,2, ...,K.
(7.6.6)
We consider the unit path flow costξkpto be the summation of the unit flow cost on links that make up the path. Suppose we denote the unit link-flow cost to beξˆ on link ( =1,2, ...,L).
Then,ξkpfor pathpfor demandkcan be given by
ξkp= L
=1
δkp ξˆ. (7.6.7)
To apply LP duality, we associate dual variablesνkwith demandk(k=1,2, ...,K), and dual variablesπ with each link . First, we rearrange the capacity constraints as greater-than-or- equal-to constraints; due to LP duality theory, this then makes the associated dual variables π non-negative. In a similar manner for equality constraints, LP duality theory says that dual variables become unrestricted. Also note that all terms associated with a variable are written on the left-hand side of the constraint while constants are written on the right-hand side of
the constraints; this helps in properly identifying and writing the dual. Thus, we rewrite Eq. (7.6.5) as
minimize{x} F= K
k=1 Pk
p=1
( L
=1
δkp ξˆ )xkp subject to
Pk
p=1xkp=hk, k=1,2, ...,K (νk)
−K
k=1 Pk
p=1
δkp xkp≥ −c , =1,2, ...,L (π) xkp≥0, p=1,2, ...,Pk,
k=1,2, ...,K.
(7.6.8)
You may compare this problem with the counterpart for the three-node network given in Eq. (7.6.2). The original problem when discussed with its dual problem is referred to as the primal problem; thus, we will refer to Eq. (7.6.8) as the primal problem. Then the dual LP problem of primal problem Eq. (7.6.8) can be written as the following maximization prob- lem:
maximize{ν,π} FD=K
k=1hkνk−L
=1cπ subject to νk−L
=1
δkp π ≤ L
=1
δkp ξˆ , p=1,2, ...,Pk, k=1,2, ...,K νkunrestricted, k=1,2, ...,K
π ≥0, =1,2, ...,L.
(7.6.9)
This general formulation then corresponds to the dual formulation for the three-node net- work example given in Eq. (7.6.3). Note that with duality, coefficients ξˆ from the original problem show up on the right-hand side of the constraint in the dual problem and vice versa.
The information about coefficient in the constraints appears in transposed form in the dual.
By rearranging, we can write the dual as
maximize{ν,π} FD=K
k=1hkνk−L
=1cπ subject to νk≤L
=1
δkp (ˆξ +π ), p=1,2, ...,Pk, k=1,2, ...,K νkunrestricted, k=1,2, ...,K
π ≥0, =1,2, ...,L.
(7.6.10)
Note that this formulation is corresponding the model shown for the three-node network example in Eq. (7.6.4).
There is an important relation between the objective function value of the primal and the dual. Note that
F= K
k=1 Pk
p=1
( L
=1
δkp ξˆ )xkp
≥ K
k=1 Pk
p=1
(νk−L
=1
δkp π )xkp
= K
k=1
νk
Pk
p=1xkp−L
=1
( K k=1
Pk
p=1
δkp xkp)π
≥ K
k=1hkνk−L
=1cπ
=FD.
(7.6.11)
That is, the primal objective is greater than or equal to the dual objective; in fact, this property holds for any LP problem and is known as the weak duality theorem. In light of the MCSPRF problem and its LP relaxation MCNF problem, and now to the above duality result, and by denoting the objective function values asFMCSPRF,FMCNF, andFDual-of-MCNF, respectively, we can writeFDUAL-of-MCNF≤FMCNF≤FMCSPRF. Furthermore, at optimality, assuming that the primal problem is feasible, the following holds:
FDUAL∗ -of-MCNF=FMCNF∗ ≤FMCSPRF∗ . (7.6.12)
Since the dual is a maximization problem, this means that for any dual variable values that satisfy the constraints in the dual problem, we can compute the objective function, which can serve as a lower bound to the MCSPRF problem, and we can determine the gap by determin- ing the difference.
We now go back to the general formulations: Eq. (7.6.8) and its dual Eq. (7.6.10). Why is the dual important to consider? The optimality conditions for LP problems state that ifx∗is op- timal for primal problem Eq. (7.6.8), andν∗andπ∗are optimal for dual problem Eq. (7.6.10), then the following must be satisfied:
1. Primal solutionsx∗must satisfy constraints in Eq. (7.6.8).
2. Dual solutionsν∗,π∗must satisfy constraints in Eq. (7.6.10).
3. The following complementary slackness condition must be satisfied:
xkp
νk−L
=1
δkp (ˆξ +π )
=0, p=1,2, ...,Pk, k=1,2, ...,K. (7.6.13a)
π
c −K
k=1 Pk
p=1
δkp xkp
=0, =1,2, ...,L. (7.6.13b)
That is, the product of a primal (dual) constraint and its associated dual (primal) vari- able is zero. Here, the first one is shown for primal variablexkpand its associated dual constraint and the second one for dual variableπ and its associated primal constraint.
Note that there is none listed for dual variablesν since its associated primal constraints are equality constraints (Pk
p=1xkp=hk); thus, the product is zero and does not need to be listed.
First note that due to the second condition, that is, satisfying dual constraints in Eq. (7.6.10), we can say that the modified path cost, L
=1δkp (ˆξ +π∗), for each path for demandkmust be at least as large as the commodity cost reflected by dual variableνkfor de- mandk. Furthermore, condition (7.6.13a) indicates that ifx∗kpfor any pathpfor demandkis positive, i.e., if a path for a demand has a positive flow, then the path cost,L
=1δkp (ˆξ +π∗), for this path must be equal to the commodity costνk∗. Note thatδkp defines which links are using this optimal path; thus,ξˆ +π is the modified link cost for link . This modified link cost then takes us back to the link weight,w , for the original shortest path routing problem. To summarize, we have the following important result [6]:
Result 7.1. For the MCNF problem given by Eq. (7.6.8) and its corresponding dual, Eq. (7.6.10), the commodity cost,νk∗, is the shortest distance for demandkwith respect to the link weightw = ˆξ +π∗, and at optimality, every path for demandkthat carries a positive flow must be a shortest path with respect to the link cost system given by
w = ˆξ +π∗ (7.6.14)
for =1,2, ...,L.
Based on the above result, we make the following important remark:
Remark 7.3. Implications of Result 7.1.
We have the following observations:
1. If we can find the dual optimal solutionπ∗, we then have a link weight system available, given byw = ˆξ +π∗, for =1,2, ...,Lfor the MCSPRF problem.
2. In most LP solvers, it is in fact not necessary to transform Problem (7.6.8) to its dual. Prob- lem Eq. (7.6.8) can be directly solved and the dual solution,π∗, is readily available, which can be used in turn to obtainw∗.
3. If two paths for the same demand identifierkhave positive flows, it does not mean that they will be equal in the primal MCNF problem where optimal flows can be propor- tional. On the other hand, if flow is allocated based on the solution of the dual problem, this flow allocation will follow the MCSPRF problem, with ECMP being an added fea- ture.
4. Multiple flows being positive for a demandkdoes not mean that the flows would be equal since optimal MCNF can result in proportional flows; this is an important difference com-
pared to the MCSPRF problem sincew would tell the MCSPRF problem to allocate flow
based on shortest path routing (along with ECMP).