Abstract

In this paper we consider a capacity sizing and routing problem in synchronous digital hierarchy/wavelength division multiplexing networks with nodes having switching capabilities. This problem is well known in the literature as the multi-hop traffic grooming problem and is generally formulated as an integer linear program, which is especially hard to solve when the demand channels are unsplittable and nonuniform. To overcome this difficulty we develop a branching strategy, using a lower bound that is close to the optimal solution. We also devise a reformulation which accelerates branch-and-bound-based solvers. The computational results clearly show that our method is effective in reducing execution time as well as memory consumption, in comparison to traditional methods based on branch-and-bound.

© 2011 OSA

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. B. Mukherjee, K. Zhu, and H. Zhu, Traffic Grooming in Optical WDM Mesh Networks, Springer, 2006.
  2. A. L. Chiu and E. H. Modiano, "Traffic grooming algorithms for reducing electronic multiplexing costs in WDM ring networks," J. Lightwave Technol. 18, (1), 2‒10 (2000).
    [CrossRef]
  3. T. Y. Chow and P. J. Lin, "The ring grooming problem," Networks 44, (3), 194‒202 (2004).
    [CrossRef]
  4. R. Dutta and G. N. Rouskas, "On optimal traffic grooming in WDM rings," IEEE J. Sel. Areas Commun. 20, (1), 110‒121 (2002).
    [CrossRef]
  5. E. Modiano and P. J. Lin, "Traffic grooming in WDM networks," IEEE Commun. Mag. 9, (2), 124‒129 (2001).
    [CrossRef]
  6. X. Zhang and C. Qiao, "An effective and comprehensive approach for traffic grooming and wavelength assignment in SONET/WDM rings," IEEE/ACM Trans. Netw. 8, (5), 608‒617 (2000).
    [CrossRef]
  7. F. Alvelos and J. M. Valerio de Carvalho, "Comparing branch-and-price algorithms for the unsplittable multicommodity flow problem," Proc. INOC’03, 2003, pp. 7‒12.
  8. H. Holler and S. Vob, "A heuristic approach for combined equipment-planning and routing in multilayer SDH/WDM networks," Eur. J. Oper. Res. 171, 787‒796 (2006).
    [CrossRef]
  9. H. Liu and F. A. Tobagi, "Traffic grooming in WDM SONET UPSR rings with multiple line speeds," Proc. IEEE INFOCOM’05, 2005, pp. 718‒729.
  10. J. Q. Hu, "Traffic grooming in WDM ring networks: a linear programming solution," J. Opt. Netw. 1, (11), 397‒408 (2002).
  11. J. Q. Hu and B. Leida, "Traffic grooming, routing and wavelength assignment in optical WDM mesh networks," Proc. IEEE INFOCOM’04, 2004, pp. 495‒501.
  12. R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory Algorithms and Applications, Prentice Hall, Englewood Cliffs, NJ, 1993.
  13. V. Gabrel, A. Knippel, and M. Minoux, "Exact solutions of multicommodity network optimization problems with general step cost function," Oper. Res. Lett. 25, 13‒23 (1999).
    [CrossRef]
  14. S. Ketabi and F. Salzborn, "Network optimization with piecewise linear convex costs," Proc. INOC’03, 2003, pp. 326‒330.
  15. S. Ketabi, "The overflow model for network optimization problems with piecewise linear costs," Proc. INOC’03, 2003, pp. 323‒325.
  16. M. Tornatore, G. Maier, and A. Pattavina, "WDM network optimization by ILP models based on flow aggregation," IEEE/ACM Trans. Netw. 15, (3), 709‒720 (2007).
    [CrossRef]
  17. M. Tornatore, G. Maier, and A. Pattavina, "WDM network optimization by ILP based on source formulation," Proc. IEEE INFOCOM, 2004, pp. 1813‒1821.
  18. D. Bienstock, S. Chopra, O. Gunluk, and C. Y. Tsai, "Minimum cost capacity installation for multicommodity network flows," Math. Program. 81, 177‒199 (1998).
  19. W. Yao, G. Sahin, M. Li, and B. Ramamurthy, "Analysis of multi-hop traffic grooming in WDM mesh networks," Opt. Switching Netw. 6, 64‒75 (2009).
    [CrossRef]
  20. S. Thiagarajan and A. K. Somani, "A capacity correlation model for WDM networks with constrained grooming capabilities," Proc. IEEE ICC, 2001, pp. 1592‒1596.
  21. A. E. Ozdaglar and D. P. Bertsekas, "Routing and wavelength assignment in optical networks," IEEE/ACM Trans. Netw. 11, (2), 259‒272 (2003).
    [CrossRef]
  22. M. Pioro and D. Medhi, Routing, Flow and Capacity Design in Communication and Computer Networks, Morgan Kaufmann, 2004.
  23. J. F. Tsai, M. H. Lin, and Y. C. Hu, "Finding multiple solutions to general integer linear programs," Eur. J. Oper. Res. 184, 802‒809 (2008).
    [CrossRef]
  24. R. M. Krishnaswamy and K. N. Sivarajan, "Design of logical lopologies: a linear formulation for wavelength-routed optical networks with no wavelength changers," IEEE/ACM Trans. Netw. 9, (2), 186‒198 (2001).
    [CrossRef]

2009

W. Yao, G. Sahin, M. Li, and B. Ramamurthy, "Analysis of multi-hop traffic grooming in WDM mesh networks," Opt. Switching Netw. 6, 64‒75 (2009).
[CrossRef]

2008

J. F. Tsai, M. H. Lin, and Y. C. Hu, "Finding multiple solutions to general integer linear programs," Eur. J. Oper. Res. 184, 802‒809 (2008).
[CrossRef]

2007

M. Tornatore, G. Maier, and A. Pattavina, "WDM network optimization by ILP models based on flow aggregation," IEEE/ACM Trans. Netw. 15, (3), 709‒720 (2007).
[CrossRef]

2006

H. Holler and S. Vob, "A heuristic approach for combined equipment-planning and routing in multilayer SDH/WDM networks," Eur. J. Oper. Res. 171, 787‒796 (2006).
[CrossRef]

2004

T. Y. Chow and P. J. Lin, "The ring grooming problem," Networks 44, (3), 194‒202 (2004).
[CrossRef]

2003

A. E. Ozdaglar and D. P. Bertsekas, "Routing and wavelength assignment in optical networks," IEEE/ACM Trans. Netw. 11, (2), 259‒272 (2003).
[CrossRef]

2002

R. Dutta and G. N. Rouskas, "On optimal traffic grooming in WDM rings," IEEE J. Sel. Areas Commun. 20, (1), 110‒121 (2002).
[CrossRef]

J. Q. Hu, "Traffic grooming in WDM ring networks: a linear programming solution," J. Opt. Netw. 1, (11), 397‒408 (2002).

2001

E. Modiano and P. J. Lin, "Traffic grooming in WDM networks," IEEE Commun. Mag. 9, (2), 124‒129 (2001).
[CrossRef]

R. M. Krishnaswamy and K. N. Sivarajan, "Design of logical lopologies: a linear formulation for wavelength-routed optical networks with no wavelength changers," IEEE/ACM Trans. Netw. 9, (2), 186‒198 (2001).
[CrossRef]

2000

A. L. Chiu and E. H. Modiano, "Traffic grooming algorithms for reducing electronic multiplexing costs in WDM ring networks," J. Lightwave Technol. 18, (1), 2‒10 (2000).
[CrossRef]

X. Zhang and C. Qiao, "An effective and comprehensive approach for traffic grooming and wavelength assignment in SONET/WDM rings," IEEE/ACM Trans. Netw. 8, (5), 608‒617 (2000).
[CrossRef]

1999

V. Gabrel, A. Knippel, and M. Minoux, "Exact solutions of multicommodity network optimization problems with general step cost function," Oper. Res. Lett. 25, 13‒23 (1999).
[CrossRef]

1998

D. Bienstock, S. Chopra, O. Gunluk, and C. Y. Tsai, "Minimum cost capacity installation for multicommodity network flows," Math. Program. 81, 177‒199 (1998).

Ahuja, R. K.

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory Algorithms and Applications, Prentice Hall, Englewood Cliffs, NJ, 1993.

Alvelos, F.

F. Alvelos and J. M. Valerio de Carvalho, "Comparing branch-and-price algorithms for the unsplittable multicommodity flow problem," Proc. INOC’03, 2003, pp. 7‒12.

Bertsekas, D. P.

A. E. Ozdaglar and D. P. Bertsekas, "Routing and wavelength assignment in optical networks," IEEE/ACM Trans. Netw. 11, (2), 259‒272 (2003).
[CrossRef]

Bienstock, D.

D. Bienstock, S. Chopra, O. Gunluk, and C. Y. Tsai, "Minimum cost capacity installation for multicommodity network flows," Math. Program. 81, 177‒199 (1998).

Chiu, A. L.

Chopra, S.

D. Bienstock, S. Chopra, O. Gunluk, and C. Y. Tsai, "Minimum cost capacity installation for multicommodity network flows," Math. Program. 81, 177‒199 (1998).

Chow, T. Y.

T. Y. Chow and P. J. Lin, "The ring grooming problem," Networks 44, (3), 194‒202 (2004).
[CrossRef]

Dutta, R.

R. Dutta and G. N. Rouskas, "On optimal traffic grooming in WDM rings," IEEE J. Sel. Areas Commun. 20, (1), 110‒121 (2002).
[CrossRef]

Gabrel, V.

V. Gabrel, A. Knippel, and M. Minoux, "Exact solutions of multicommodity network optimization problems with general step cost function," Oper. Res. Lett. 25, 13‒23 (1999).
[CrossRef]

Gunluk, O.

D. Bienstock, S. Chopra, O. Gunluk, and C. Y. Tsai, "Minimum cost capacity installation for multicommodity network flows," Math. Program. 81, 177‒199 (1998).

Holler, H.

H. Holler and S. Vob, "A heuristic approach for combined equipment-planning and routing in multilayer SDH/WDM networks," Eur. J. Oper. Res. 171, 787‒796 (2006).
[CrossRef]

Hu, J. Q.

J. Q. Hu, "Traffic grooming in WDM ring networks: a linear programming solution," J. Opt. Netw. 1, (11), 397‒408 (2002).

J. Q. Hu and B. Leida, "Traffic grooming, routing and wavelength assignment in optical WDM mesh networks," Proc. IEEE INFOCOM’04, 2004, pp. 495‒501.

Hu, Y. C.

J. F. Tsai, M. H. Lin, and Y. C. Hu, "Finding multiple solutions to general integer linear programs," Eur. J. Oper. Res. 184, 802‒809 (2008).
[CrossRef]

Ketabi, S.

S. Ketabi and F. Salzborn, "Network optimization with piecewise linear convex costs," Proc. INOC’03, 2003, pp. 326‒330.

S. Ketabi, "The overflow model for network optimization problems with piecewise linear costs," Proc. INOC’03, 2003, pp. 323‒325.

Knippel, A.

V. Gabrel, A. Knippel, and M. Minoux, "Exact solutions of multicommodity network optimization problems with general step cost function," Oper. Res. Lett. 25, 13‒23 (1999).
[CrossRef]

Krishnaswamy, R. M.

R. M. Krishnaswamy and K. N. Sivarajan, "Design of logical lopologies: a linear formulation for wavelength-routed optical networks with no wavelength changers," IEEE/ACM Trans. Netw. 9, (2), 186‒198 (2001).
[CrossRef]

Leida, B.

J. Q. Hu and B. Leida, "Traffic grooming, routing and wavelength assignment in optical WDM mesh networks," Proc. IEEE INFOCOM’04, 2004, pp. 495‒501.

Li, M.

W. Yao, G. Sahin, M. Li, and B. Ramamurthy, "Analysis of multi-hop traffic grooming in WDM mesh networks," Opt. Switching Netw. 6, 64‒75 (2009).
[CrossRef]

Lin, M. H.

J. F. Tsai, M. H. Lin, and Y. C. Hu, "Finding multiple solutions to general integer linear programs," Eur. J. Oper. Res. 184, 802‒809 (2008).
[CrossRef]

Lin, P. J.

T. Y. Chow and P. J. Lin, "The ring grooming problem," Networks 44, (3), 194‒202 (2004).
[CrossRef]

E. Modiano and P. J. Lin, "Traffic grooming in WDM networks," IEEE Commun. Mag. 9, (2), 124‒129 (2001).
[CrossRef]

Liu, H.

H. Liu and F. A. Tobagi, "Traffic grooming in WDM SONET UPSR rings with multiple line speeds," Proc. IEEE INFOCOM’05, 2005, pp. 718‒729.

Magnanti, T. L.

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory Algorithms and Applications, Prentice Hall, Englewood Cliffs, NJ, 1993.

Maier, G.

M. Tornatore, G. Maier, and A. Pattavina, "WDM network optimization by ILP models based on flow aggregation," IEEE/ACM Trans. Netw. 15, (3), 709‒720 (2007).
[CrossRef]

M. Tornatore, G. Maier, and A. Pattavina, "WDM network optimization by ILP based on source formulation," Proc. IEEE INFOCOM, 2004, pp. 1813‒1821.

Medhi, D.

M. Pioro and D. Medhi, Routing, Flow and Capacity Design in Communication and Computer Networks, Morgan Kaufmann, 2004.

Minoux, M.

V. Gabrel, A. Knippel, and M. Minoux, "Exact solutions of multicommodity network optimization problems with general step cost function," Oper. Res. Lett. 25, 13‒23 (1999).
[CrossRef]

Modiano, E.

E. Modiano and P. J. Lin, "Traffic grooming in WDM networks," IEEE Commun. Mag. 9, (2), 124‒129 (2001).
[CrossRef]

Modiano, E. H.

Mukherjee, B.

B. Mukherjee, K. Zhu, and H. Zhu, Traffic Grooming in Optical WDM Mesh Networks, Springer, 2006.

Orlin, J. B.

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory Algorithms and Applications, Prentice Hall, Englewood Cliffs, NJ, 1993.

Ozdaglar, A. E.

A. E. Ozdaglar and D. P. Bertsekas, "Routing and wavelength assignment in optical networks," IEEE/ACM Trans. Netw. 11, (2), 259‒272 (2003).
[CrossRef]

Pattavina, A.

M. Tornatore, G. Maier, and A. Pattavina, "WDM network optimization by ILP models based on flow aggregation," IEEE/ACM Trans. Netw. 15, (3), 709‒720 (2007).
[CrossRef]

M. Tornatore, G. Maier, and A. Pattavina, "WDM network optimization by ILP based on source formulation," Proc. IEEE INFOCOM, 2004, pp. 1813‒1821.

Pioro, M.

M. Pioro and D. Medhi, Routing, Flow and Capacity Design in Communication and Computer Networks, Morgan Kaufmann, 2004.

Qiao, C.

X. Zhang and C. Qiao, "An effective and comprehensive approach for traffic grooming and wavelength assignment in SONET/WDM rings," IEEE/ACM Trans. Netw. 8, (5), 608‒617 (2000).
[CrossRef]

Ramamurthy, B.

W. Yao, G. Sahin, M. Li, and B. Ramamurthy, "Analysis of multi-hop traffic grooming in WDM mesh networks," Opt. Switching Netw. 6, 64‒75 (2009).
[CrossRef]

Rouskas, G. N.

R. Dutta and G. N. Rouskas, "On optimal traffic grooming in WDM rings," IEEE J. Sel. Areas Commun. 20, (1), 110‒121 (2002).
[CrossRef]

Sahin, G.

W. Yao, G. Sahin, M. Li, and B. Ramamurthy, "Analysis of multi-hop traffic grooming in WDM mesh networks," Opt. Switching Netw. 6, 64‒75 (2009).
[CrossRef]

Salzborn, F.

S. Ketabi and F. Salzborn, "Network optimization with piecewise linear convex costs," Proc. INOC’03, 2003, pp. 326‒330.

Sivarajan, K. N.

R. M. Krishnaswamy and K. N. Sivarajan, "Design of logical lopologies: a linear formulation for wavelength-routed optical networks with no wavelength changers," IEEE/ACM Trans. Netw. 9, (2), 186‒198 (2001).
[CrossRef]

Somani, A. K.

S. Thiagarajan and A. K. Somani, "A capacity correlation model for WDM networks with constrained grooming capabilities," Proc. IEEE ICC, 2001, pp. 1592‒1596.

Thiagarajan, S.

S. Thiagarajan and A. K. Somani, "A capacity correlation model for WDM networks with constrained grooming capabilities," Proc. IEEE ICC, 2001, pp. 1592‒1596.

Tobagi, F. A.

H. Liu and F. A. Tobagi, "Traffic grooming in WDM SONET UPSR rings with multiple line speeds," Proc. IEEE INFOCOM’05, 2005, pp. 718‒729.

Tornatore, M.

M. Tornatore, G. Maier, and A. Pattavina, "WDM network optimization by ILP models based on flow aggregation," IEEE/ACM Trans. Netw. 15, (3), 709‒720 (2007).
[CrossRef]

M. Tornatore, G. Maier, and A. Pattavina, "WDM network optimization by ILP based on source formulation," Proc. IEEE INFOCOM, 2004, pp. 1813‒1821.

Tsai, C. Y.

D. Bienstock, S. Chopra, O. Gunluk, and C. Y. Tsai, "Minimum cost capacity installation for multicommodity network flows," Math. Program. 81, 177‒199 (1998).

Tsai, J. F.

J. F. Tsai, M. H. Lin, and Y. C. Hu, "Finding multiple solutions to general integer linear programs," Eur. J. Oper. Res. 184, 802‒809 (2008).
[CrossRef]

Valerio de Carvalho, J. M.

F. Alvelos and J. M. Valerio de Carvalho, "Comparing branch-and-price algorithms for the unsplittable multicommodity flow problem," Proc. INOC’03, 2003, pp. 7‒12.

Vob, S.

H. Holler and S. Vob, "A heuristic approach for combined equipment-planning and routing in multilayer SDH/WDM networks," Eur. J. Oper. Res. 171, 787‒796 (2006).
[CrossRef]

Yao, W.

W. Yao, G. Sahin, M. Li, and B. Ramamurthy, "Analysis of multi-hop traffic grooming in WDM mesh networks," Opt. Switching Netw. 6, 64‒75 (2009).
[CrossRef]

Zhang, X.

X. Zhang and C. Qiao, "An effective and comprehensive approach for traffic grooming and wavelength assignment in SONET/WDM rings," IEEE/ACM Trans. Netw. 8, (5), 608‒617 (2000).
[CrossRef]

Zhu, H.

B. Mukherjee, K. Zhu, and H. Zhu, Traffic Grooming in Optical WDM Mesh Networks, Springer, 2006.

Zhu, K.

B. Mukherjee, K. Zhu, and H. Zhu, Traffic Grooming in Optical WDM Mesh Networks, Springer, 2006.

Eur. J. Oper. Res.

H. Holler and S. Vob, "A heuristic approach for combined equipment-planning and routing in multilayer SDH/WDM networks," Eur. J. Oper. Res. 171, 787‒796 (2006).
[CrossRef]

J. F. Tsai, M. H. Lin, and Y. C. Hu, "Finding multiple solutions to general integer linear programs," Eur. J. Oper. Res. 184, 802‒809 (2008).
[CrossRef]

IEEE Commun. Mag.

E. Modiano and P. J. Lin, "Traffic grooming in WDM networks," IEEE Commun. Mag. 9, (2), 124‒129 (2001).
[CrossRef]

IEEE J. Sel. Areas Commun.

R. Dutta and G. N. Rouskas, "On optimal traffic grooming in WDM rings," IEEE J. Sel. Areas Commun. 20, (1), 110‒121 (2002).
[CrossRef]

IEEE/ACM Trans. Netw.

X. Zhang and C. Qiao, "An effective and comprehensive approach for traffic grooming and wavelength assignment in SONET/WDM rings," IEEE/ACM Trans. Netw. 8, (5), 608‒617 (2000).
[CrossRef]

M. Tornatore, G. Maier, and A. Pattavina, "WDM network optimization by ILP models based on flow aggregation," IEEE/ACM Trans. Netw. 15, (3), 709‒720 (2007).
[CrossRef]

R. M. Krishnaswamy and K. N. Sivarajan, "Design of logical lopologies: a linear formulation for wavelength-routed optical networks with no wavelength changers," IEEE/ACM Trans. Netw. 9, (2), 186‒198 (2001).
[CrossRef]

A. E. Ozdaglar and D. P. Bertsekas, "Routing and wavelength assignment in optical networks," IEEE/ACM Trans. Netw. 11, (2), 259‒272 (2003).
[CrossRef]

J. Lightwave Technol.

J. Opt. Netw.

Math. Program.

D. Bienstock, S. Chopra, O. Gunluk, and C. Y. Tsai, "Minimum cost capacity installation for multicommodity network flows," Math. Program. 81, 177‒199 (1998).

Networks

T. Y. Chow and P. J. Lin, "The ring grooming problem," Networks 44, (3), 194‒202 (2004).
[CrossRef]

Oper. Res. Lett.

V. Gabrel, A. Knippel, and M. Minoux, "Exact solutions of multicommodity network optimization problems with general step cost function," Oper. Res. Lett. 25, 13‒23 (1999).
[CrossRef]

Opt. Switching Netw.

W. Yao, G. Sahin, M. Li, and B. Ramamurthy, "Analysis of multi-hop traffic grooming in WDM mesh networks," Opt. Switching Netw. 6, 64‒75 (2009).
[CrossRef]

Other

S. Thiagarajan and A. K. Somani, "A capacity correlation model for WDM networks with constrained grooming capabilities," Proc. IEEE ICC, 2001, pp. 1592‒1596.

M. Tornatore, G. Maier, and A. Pattavina, "WDM network optimization by ILP based on source formulation," Proc. IEEE INFOCOM, 2004, pp. 1813‒1821.

S. Ketabi and F. Salzborn, "Network optimization with piecewise linear convex costs," Proc. INOC’03, 2003, pp. 326‒330.

S. Ketabi, "The overflow model for network optimization problems with piecewise linear costs," Proc. INOC’03, 2003, pp. 323‒325.

J. Q. Hu and B. Leida, "Traffic grooming, routing and wavelength assignment in optical WDM mesh networks," Proc. IEEE INFOCOM’04, 2004, pp. 495‒501.

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory Algorithms and Applications, Prentice Hall, Englewood Cliffs, NJ, 1993.

B. Mukherjee, K. Zhu, and H. Zhu, Traffic Grooming in Optical WDM Mesh Networks, Springer, 2006.

F. Alvelos and J. M. Valerio de Carvalho, "Comparing branch-and-price algorithms for the unsplittable multicommodity flow problem," Proc. INOC’03, 2003, pp. 7‒12.

H. Liu and F. A. Tobagi, "Traffic grooming in WDM SONET UPSR rings with multiple line speeds," Proc. IEEE INFOCOM’05, 2005, pp. 718‒729.

M. Pioro and D. Medhi, Routing, Flow and Capacity Design in Communication and Computer Networks, Morgan Kaufmann, 2004.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (4)

Fig. 1
Fig. 1

Logical view of the typical setup of SDH/WDM equipment at a node.

Fig. 2
Fig. 2

An example on channel splittability.

Fig. 3
Fig. 3

NSFNet topology.

Fig. 4
Fig. 4

EON topology.

Tables (7)

Tables Icon

Table I Comparison of Size Between RILP a g ( κ ) and RILP n w ( κ )

Tables Icon

Table II Types of Channel for the NSFNet

Tables Icon

Table III Channels for the EON

Tables Icon

Table IV Computational Results for the NSFNet With Symmetric Traffic

Tables Icon

Table V Computational Results for the NSFNet With Asymmetric Traffic

Tables Icon

Table VI Computational Results for the EON With Symmetric Traffic

Tables Icon

Table VII Computational Results for the EON With Asymmetric Traffic

Equations (36)

Equations on this page are rendered with MathJax. Learn more.

Min e E λ e
e ( i ) x e c e + ( i ) x e c = 1 if  i = s c , ( a ) 1 if  i = t c , ( b ) 0 otherwise , ( c )
c C a k ̃ ( c ) x e c λ e   c a p λ , e E ,
x e c { 0 , 1 } , e E , c C ,
λ e  integer , e E .
x e k d = c C d k x e c e E , k K , d D .
Min e E λ e
e ( i ) x e k d e + ( i ) x e k d = Q d k if  i = s ( d ) , ( a ) Q d k if  i = t ( d ) , ( b ) 0 otherwise , ( c )
d D k K a k x e k d λ e   c a p λ , e E ,
x e k d  integer , e E , k K , d D ,
λ e  integer , e E .
p P c f p c = 1 , c C ,
c C ( e p ) a k ̃ ( c ) f p c λ ¯ e   c a p λ , e E ,
f p c 0 , p P c , c C .
l e = d D x ¯ e 0 d , e E .
l e + d D ( a 1 x e 1 d + a 2 x e 2 d ) λ e ( 1 )   c a p λ , e E .
l e l e + d D a 1 x ¯ e 1 d , e E .
Min e E λ e ( κ )
e ( i ) x e κ d e + ( i ) x e κ d = Q d κ if  i = s ( d ) , ( a ) Q d κ if  i = t ( d ) , ( b ) 0 otherwise , ( c )
e ( i ) x e k d e + ( i ) x e k d = Q d k if  i = s ( d ) , ( a ) Q d k if  i = t ( d ) , ( b ) 0 otherwise , ( c )
d D k K { 0 , 1 , , κ } a k x e k d + d D a κ x e κ d + l e λ e ( κ )   c a p λ , e E ,
x e κ d , λ e ( κ )  integer , e E ,
x e k d 0 e E , d D , k K { 0 , 1 , , κ } .
k K d D e E | x e k d x ˆ e k d | + e E | λ e ( κ ) λ ˆ e ( κ ) | 1 ,
x e i = k K { 0 , 1 ,   , κ } d D ( i ) a k x e k d , i N , e E .
Q ̃ d = k K { 0 , 1 ,   , κ } Q d k , d D .
Min e E λ e ( κ )
e ( i ) x e κ d e + ( i ) x e κ d = Q d κ if  i = s ( d ) , ( a ) Q d κ if  i = t ( d ) , ( b ) 0 otherwise , ( c )
e ( i ) x e i e + ( j ) x e i = Q ̃ d if  j = t ( d ) , ( a ) 0 otherwise , ( b )
i N x e i + d D a κ x e κ d + l e λ e ( κ )   c a p λ e E ,
x e κ d , λ e ( κ )  integer , x e i 0 , e E , i N , d D .
λ e ( κ )   c a p λ l e d D a κ x e κ d , e E
e ( i ) x e k d e + ( i ) x e k d = Q d k if  i = s ( d ) , Q d k if  i = t ( d ) , 0 otherwise ,
k K { 0 , 1 ,   , κ } d D a k x e k d λ e ( κ )   c a p λ d D a κ x e κ d + l e
e ( i ) x e i e + ( j ) x e i = Q ̃ d if  j = t ( d ) , 0 otherwise ,
i N x e i λ e ( κ )   c a p λ d D a κ x e κ d + l e .