Abstract
This paper describes a new hybrid algorithm for a multicast network design application. The problem consists of finding a minimum-cost topology and link dimensions subject to capacity and multicast routing constraints. The algorithm exploits Lagrange Decomposition (LD) to yield separable subproblems. Each subproblem has a Constraint Programming relaxation. We derive a sharper cost bound and stronger cost-based filtering rules. The results indicate that our solver outperforms the pure LD approach.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms and Applications. Prentice-Hall, New Jersey (1993)
Bienstock, D., Bley, A.: Capacitated network design with multicast commodities. Tech. Rep. ZIB 00–14, Konrad-Zuse-Zentrum für Inform., Berlin (2000)
Cronholm, W.: CP-based lagrange decomposition applied to multicast network design. PhD transfer thesis, IC-Parc, Imperial, London UK (2004)
ECLiPSe. Introduction. Tech. Rep. IC-PARC-03-01, Imperial, London UK (2002)
Guignard, M., Kim, S.: Lagrangean decomposition: A model yielding stronger Lagrangean bounds. Math. Program. 39 (1987)
Holmberg, K., Yuan, D.: A Lagrangian heuristic based branch-and-bound approach for the capacitated network design problem. Oper. Res. 48(3) (2000)
Koch, T., Martin, A.: Solving Steiner tree problems in graphs to optimality. Networks 32(3) (1998)
Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. John Wiley and Sons Ltd., Chichester (1990)
Milano, M. (ed.): Constraint and Integer Programming: Toward a Unified Methodology. Kluwer Academic Publishers, Dordrecht (2003)
Ouaja, W., Richards, B.: A hybrid multicommodity routing algorithm for traffic engineering. Networks 43(3) (2004)
Prytz, M., Forsgren, A.: Dimensioning multicast-enabled communications networks. Networks 39(4) (2002)
Sellmann, M., Fahle, T.: CP-based Lagrangian relaxation for the automatic recording problem. Ann. Oper. Res. 118(1) (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cronholm, W., Ajili, F. (2004). Strong Cost-Based Filtering for Lagrange Decomposition Applied to Network Design. In: Wallace, M. (eds) Principles and Practice of Constraint Programming – CP 2004. CP 2004. Lecture Notes in Computer Science, vol 3258. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30201-8_55
Download citation
DOI: https://doi.org/10.1007/978-3-540-30201-8_55
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23241-4
Online ISBN: 978-3-540-30201-8
eBook Packages: Springer Book Archive