On étudie ici une version continue du problème de dimensionnement et routage dans un réseau de communications, dans lequel les coûts de conception sont combinés aux mesures de délai moyen d'acheminement, engendrant un problème de multiflots avec une fonction objectif non convexe. On propose un encadrement de la valeur optimale par convexification séparable sur les arcs, d'une part, et par calcul d'optima locaux issus d'un modèle DC (différence de fonctions convexes) des fonctions de coût. Cette dernière technique permet de réduire la distance à la valeur optimale et on illustre son efficacité sur des problèmes d'expansion de capacités.
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.
@article{RO_2001__35_2_269_0,
author = {Mahey, P. and Phong, Thai Q. and Luna, H. P. L.},
title = {Separable convexification and {DCA} techniques for capacity and flow assignment problems},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {269--281},
publisher = {EDP-Sciences},
volume = {35},
number = {2},
year = {2001},
mrnumber = {1868872},
zbl = {1048.90047},
language = {en},
url = {http://www.numdam.org/item/RO_2001__35_2_269_0/}
}
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 SP - 269 EP - 281 VL - 35 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/item/RO_2001__35_2_269_0/ LA - en ID - RO_2001__35_2_269_0 ER -
%0 Journal Article %A Mahey, P. %A Phong, Thai Q. %A Luna, H. P. L. %T Separable convexification and DCA techniques for capacity and flow assignment problems %J RAIRO - Operations Research - Recherche Opérationnelle %D 2001 %P 269-281 %V 35 %N 2 %I EDP-Sciences %U http://www.numdam.org/item/RO_2001__35_2_269_0/ %G en %F RO_2001__35_2_269_0
Mahey, P.; Phong, Thai Q.; Luna, H. P. L. Separable convexification and DCA techniques for capacity and flow assignment problems. RAIRO - Operations Research - Recherche Opérationnelle, Tome 35 (2001) no. 2, pp. 269-281. http://www.numdam.org/item/RO_2001__35_2_269_0/
[1] and, A composite algorithm for a concave-cost network flow problem. Networks 19 (1989) 175-202. | MR | Zbl
[2] and, Data Networks. Prentice-Hall (1987). | Zbl
[3] , Lagrange multipliers and nonconvex programs. SIAM J. Control Optim. 7 (1969) 534-545. | MR | Zbl
[4] , and, The flow deviation method: an approach to store-and-forward communication network design. Networks 3 (1973) 97-133. | MR | Zbl
[5] , Augmented Lagrangian based bounds for centralized network design. IEEE Trans. Comm. 33 (1985) 1247-1257.
[6] and, Backbone network design tools with economic tradeoffs. ORSA J. Comput. 2/3 (1990) 236-252. | Zbl
[7] and, A system for routing and capacity assignment in computer communication networks. IEEE Trans. Comm. 37 (1989) 360-366.
[8] , The Design of Store-and-forward Networks for Computer Communications. Ph.D. Thesis, UCLA (1973).
[9] and, On the topological design of distributed computer networks. IEEE Trans. Comm. 25 (1977) 48-60. | MR
[10] , and, Topology design and bandwith allocation in ATM nets. IEEE J. Selected Areas in Communications 7 (1989) 1253-1261.
[11] and, Convex Analysis and Minimization Algorithms. Springer-Verlag (1993). | Zbl
[12] , and, Optimization on Low Rank Nonconvex Structures. Kluwer Academic Publishers, Dordrecht (1997). | MR | Zbl
[13] and, Bounds for global optimization of capacity expansion and flow assignment problems. Oper. Res. Lett. 26 (2000) 211-216. | MR | Zbl
[14] , and, Capacity and flow assignment of data networks by generalized Benders decomposition. J. Global Optim. (to appear). | MR | Zbl
[15] ,, and, A new proximal decomposition algorithm for routing in telecommunications networks. Networks 31 (1998) 227-238. | Zbl
[16] , and, A survey of algorithms for convex multicommodity flow problems. Management Sci. 46 (2000) 126-147.
[17] and, Convex analysis approach to dc programming: Theory, algorithms and applications. Acta Math. Vietnam. 22 (1997) 289-355. | MR | Zbl
[18] , Une approche dc en optimisation dans les réseaux. Algorithmes, codes et simulations numériques. Doct. Thesis, Univ. Rouen (1999).
[19] , and, An algorithm for network dimensioning under reliability considerations. Ann. Oper. Res. 36 (1992) 263-274. | Zbl
[20] ,, and, A strongly polynomial algorithm for a concave production-transportation problem with a fixed number of nonlinear variables. Math. Programming 72 (1996) 229-258. | MR | Zbl
[21] , Introduction and recent advances in network design: Models and algorithms, in Transportation Planning Models, edited by M. Florian. Elsevier-North-Holland Publ. (1984). | Zbl
