Separable convexification and DCA techniques for capacity and flow assignment problems

P. Mahey; Thai Q. Phong; H. P. L. Luna

RAIRO - Operations Research - Recherche Opérationnelle (2001)

  • Volume: 35, Issue: 2, page 269-281
  • ISSN: 0399-0559

Abstract

top
We study a continuous version of the capacity and flow assignment problem (CFA) where the design cost is combined with an average delay measure to yield a non convex objective function coupled with multicommodity flow constraints. A separable convexification of each arc cost function is proposed to obtain approximate feasible solutions within easily computable gaps from optimality. On the other hand, DC (difference of convex functions) programming can be used to compute accurate upper bounds and reduce the gap. The technique is shown to be effective when topology is assumed fixed and capacity expansion on some arcs is considered.

How to cite

top

Mahey, P., Phong, Thai Q., and Luna, H. P. L.. "Separable convexification and DCA techniques for capacity and flow assignment problems." RAIRO - Operations Research - Recherche Opérationnelle 35.2 (2001): 269-281. <http://eudml.org/doc/105246>.

@article{Mahey2001,
abstract = {We study a continuous version of the capacity and flow assignment problem (CFA) where the design cost is combined with an average delay measure to yield a non convex objective function coupled with multicommodity flow constraints. A separable convexification of each arc cost function is proposed to obtain approximate feasible solutions within easily computable gaps from optimality. On the other hand, DC (difference of convex functions) programming can be used to compute accurate upper bounds and reduce the gap. The technique is shown to be effective when topology is assumed fixed and capacity expansion on some arcs is considered.},
author = {Mahey, P., Phong, Thai Q., Luna, H. P. L.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {network design; DC optimization; capacity and flow assignment},
language = {eng},
number = {2},
pages = {269-281},
publisher = {EDP-Sciences},
title = {Separable convexification and DCA techniques for capacity and flow assignment problems},
url = {http://eudml.org/doc/105246},
volume = {35},
year = {2001},
}

TY - JOUR
AU - Mahey, P.
AU - Phong, Thai Q.
AU - Luna, H. P. L.
TI - Separable convexification and DCA techniques for capacity and flow assignment problems
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 2001
PB - EDP-Sciences
VL - 35
IS - 2
SP - 269
EP - 281
AB - We study a continuous version of the capacity and flow assignment problem (CFA) where the design cost is combined with an average delay measure to yield a non convex objective function coupled with multicommodity flow constraints. A separable convexification of each arc cost function is proposed to obtain approximate feasible solutions within easily computable gaps from optimality. On the other hand, DC (difference of convex functions) programming can be used to compute accurate upper bounds and reduce the gap. The technique is shown to be effective when topology is assumed fixed and capacity expansion on some arcs is considered.
LA - eng
KW - network design; DC optimization; capacity and flow assignment
UR - http://eudml.org/doc/105246
ER -

References

top
  1. [1] A. Balakrishnan and S.C. Graves, A composite algorithm for a concave-cost network flow problem. Networks 19 (1989) 175-202. Zbl0673.90034MR984565
  2. [2] D.P. Bertsekas and R.G. Gallager, Data Networks. Prentice-Hall (1987). Zbl0734.68006
  3. [3] J.E. Falk, Lagrange multipliers and nonconvex programs. SIAM J. Control Optim. 7 (1969) 534-545. Zbl0184.44404MR270749
  4. [4] L. Fratta, M. Gerla and L. Kleinrock, The flow deviation method: an approach to store-and-forward communication network design. Networks 3 (1973) 97-133. Zbl1131.90321MR312994
  5. [5] B. Gavish, Augmented Lagrangian based bounds for centralized network design. IEEE Trans. Comm. 33 (1985) 1247-1257. 
  6. [6] B. Gavish and K. Altinkemer, Backbone network design tools with economic tradeoffs. ORSA J. Comput. 2/3 (1990) 236-252. Zbl0755.90024
  7. [7] B. Gavish and I. Neuman, A system for routing and capacity assignment in computer communication networks. IEEE Trans. Comm. 37 (1989) 360-366. 
  8. [8] M. Gerla, The Design of Store-and-forward Networks for Computer Communications. Ph.D. Thesis, UCLA (1973). 
  9. [9] M. Gerla and L. Kleinrock, On the topological design of distributed computer networks. IEEE Trans. Comm. 25 (1977) 48-60. MR449892
  10. [10] M. Gerla, J.A.S. Monteiro and R. Pazos, Topology design and bandwith allocation in ATM nets. IEEE J. Selected Areas in Communications 7 (1989) 1253-1261. 
  11. [11] J.B. Hiriart–Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms. Springer-Verlag (1993). Zbl0795.49002
  12. [12] H. Konno, P.T. Thach and H. Tuy, Optimization on Low Rank Nonconvex Structures. Kluwer Academic Publishers, Dordrecht (1997). Zbl0879.90171MR1480917
  13. [13] H.P.L. Luna and P. Mahey, Bounds for global optimization of capacity expansion and flow assignment problems. Oper. Res. Lett. 26 (2000) 211-216. Zbl0960.90055MR1784600
  14. [14] P. Mahey, A. Benchakroun and F. Boyer, Capacity and flow assignment of data networks by generalized Benders decomposition. J. Global Optim. (to appear). Zbl1002.90082MR1841079
  15. [15] P. Mahey, A. Ouorou, L. LeBlanc and J. Chifflet, A new proximal decomposition algorithm for routing in telecommunications networks. Networks 31 (1998) 227-238. Zbl1015.90020
  16. [16] A. Ouorou, P. Mahey and J.P. Vial, A survey of algorithms for convex multicommodity flow problems. Management Sci. 46 (2000) 126-147. Zbl1231.90110
  17. [17] P.D. Tao and L.T.H. An, Convex analysis approach to dc programming: Theory, algorithms and applications. Acta Math. Vietnam. 22 (1997) 289-355. Zbl0895.90152MR1479751
  18. [18] N.T. Quang, Une approche dc en optimisation dans les réseaux. Algorithmes, codes et simulations numériques. Doct. Thesis, Univ. Rouen (1999). 
  19. [19] B. Sanso, M. Gendreau and F. Soumis, An algorithm for network dimensioning under reliability considerations. Ann. Oper. Res. 36 (1992) 263-274. Zbl0825.90377
  20. [20] H. Tuy, S. Ghannadan, A. Migdalas and P. Varbrand, A strongly polynomial algorithm for a concave production-transportation problem with a fixed number of nonlinear variables. Math. Programming 72 (1996) 229-258. Zbl0853.90116MR1387761
  21. [21] R. Wong, Introduction and recent advances in network design: Models and algorithms, in Transportation Planning Models, edited by M. Florian. Elsevier-North-Holland Publ. (1984). Zbl0594.90086

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.