Plenary
Lecture
A Heuristic Algorithm for the Network Design Problem
Professor Milan Tuba
Megatrend University Belgrade
Faculty of Computer Science
Serbia
Email: tuba@ieee.org
Abstract:
The network design problem (NDP) is a well known problem
which can be applied to many different types of
networks. It was well investigated applied to computer
communications networks during the time of Internet
development. Today it is again very actual applied
mostly to the dynamic wireless networks (MANET – mobile
ad hoc networks). The network design problem is an
NPhard problem which involves topology selection
(subset of possible links) and routing determination
(paths for the offered traffic). Capacity assignment is
usually treated as a 01 problem and as such included it
in the topology problem. This does not make the network
design problem easier, just the opposite, it moves
optimization from continuous to integer. The goal is to
minimize the cost which can be a combination of the link
costs and delay penalties, under possible additional
constraints. Such hard combinatorial graph problems are
often treated by evolutionary metaheuristics. In many
cases better results and faster convergence are achieved
by hybrid algorithms where some local searcher that
utilizes particular knowledge about the corresponding
problem is included. Here we propose and analyze a
computationally feasible heuristic algorithm which
excludes underutilized links by a version of
flowdeviation method. A simplified queuing model is
developed for cost function estimate. Some theoretical
results are also established that direct initial
approximation. Proposed algorithm can dynamically be
adjusted for faster or better results. It is implemented
and computes a good solution that is robust with respect
to often required dynamic changes of the cost function.
Brief Biography of the Speaker:
Milan Tuba received B. S. in Mathematics, M. S. in
Mathematics, M. S. in Computer Science, M. Ph. in
Computer Science, Ph. D. in Computer Science from
University of Belgrade and New York University. From
1983 to 1994 he was in the U.S.A. first as a graduate
student and teaching and research assistant at
Vanderbilt University in Nashville and Courant Institute
of Mathematical Sciences, New York University and later
as an Assistant Professor of Electrical Engineering at
Cooper Union Graduate School of Engineering, New York.
During that time he was the founder and director of
Microprocessor Lab and VLSI Lab, leader of scientific
projects and supervisor of many theses. From 1994 he was
Associate professor of Computer Science and Director of
Computer Center at University of Belgrade, Faculty of
Mathematics, and from 2004 also a Professor of Computer
Science and Dean of the College of Computer Science,
Megatrend University Belgrade. He was teaching more than
20 graduate and undergraduate courses, from VLSI Design
and Computer Architecture to Computer Networks,
Operating Systems, Image Processing, Calculus and
Queuing Theory. His research interest includes
mathematical, queuing theory and heuristic optimizations
applied to computer networks, image processing and
combinatorial problems. He is the author of more than 90
scientific papers and a monograph. He is coeditor or
member of the editorial board or scientific committee of
number of scientific journals and conferences. Member of
the ACM since 1983, IEEE 1984, New York Academy of
Sciences 1987, AMS 1995, SIAM 2009. Participated in many
WSEAS Conferences with plenary lectures and articles in
Proceedings and Transactions.
