Premium
A Lagrangean Approach to Network Design Problems
Author(s) -
Holmberg K.,
Yuan D.
Publication year - 1998
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.1998.tb00135.x
Subject(s) - subgradient method , heuristics , computer science , mathematical optimization , network planning and design , heuristic , survivability , relaxation (psychology) , optimization problem , mathematics , algorithm , computer network , psychology , social psychology
Network design is a very important issue in the area of telecommunications and computer networks, where there is a large need for construction of new networks. This is due to technological development (fiber optics for telecommunication) and new ways of usage (Internet for computer networks). Optimal design of such networks requires formulation and solution of new optimization models. In this paper, we formulate several fixed charge network design models, capacitated or uncapacitated, directed or undirected, possibly with staircase costs, and survivability requirements. We propose a common solution approach for all these problems, based on Lagrangean relaxation, subgradient optimization and primal heuristics, which together form a Lagrangean heuristic. The Lagrangean heuristic can be incorporated into a branch‐and‐bound framework, if the exact optimal solution must be found. The approach has been tested on problems of various structures and sizes, and computational results are presented.