Optimization Problems in Telecommunications with Military Applications
Clayton W. Commander · 2007
In recent decades, optimization problems in telecommunication systems have been the focus of an intensive amount of research. These problems are important for several reasons including speed and quality of communication among others. In this dissertation, we present several problems arising in telecommunication networks in military applications. Several problems we consider involve wireless communication networks. These networks are an extraordinarily convenient method of communication. However, along with this convenience comes a myriad of complicated problems that must be addressed to preserve the attractive features of the networks. Furthermore, problems arising in adversarial environments differ from those in conventional settings, in that time is usually a critically constrained factor. This is troublesome because many of the problems are difficult to solve and would require a tremendous amount of time to compute the optimal solution. However in a battlespace environment, time spent computing a solution and not fighting the enemy leads to a potential loss of materiel and lives. Thus for the problems studied, we will focus a great deal of attention on designing heuristic algorithms which are capable of computing near optimal solutions very efficiently. We will consider two classes of problems involving telecommunication networks. The first class focuses on denying communication on a network and destroying its functionality. The other class has the objective of guaranteeing communication on a network. At first glance, these two sets appear to be polar opposites of one another. However, with any emerging technology studies which assess both vulnerabilities and capabilities must be performed in order to achieve a system which will not fail in its intended operational environment. Our goal is to show how these problems can be formulated and solved using tools from global and combinatorial optimization. For the problems considered, we examine the computational complexity and examine several mathematical programming formulations. Then we present several algorithms and examine extensive computational results comparing their effectiveness. Finally, we conclude by summarizing our work and indicating future directions of research. ( en )