Network Design Problems In Graphs And On The Plane

Given points in the plane, connect them using minimum ink. Though the task seems simple, it turns out to be very time consuming. In fact, scientists believe that computers cannot efficiently solve it. So, do we have to resign? This book examines such NP-hard network-design problems, from connectivity problems in graphs to polygonal drawing problems on the plane. First, we observe why it is so hard to optimally solve these problems. Then, we go over to attack them anyway. We develop fast algorithms that find approximate solutions that are very close to the optimal ones. Hence, connecting points with slightly more ink is not hard.

Finally, we consider an optimization problem that integrates network design and broadcast domination decisions. Given an undirected graph, a feasible broadcast domination is a set of nonnegative integer powers f[subscript i] assigned to each node i, such that for any node j in the graph, there exists some node k having a positive f[subscript k]-value whose shortest distance to node j is no more than f[subscript k] . The cost of a broadcast domination solution is the sum of all node power values. The network design problem constructs edges that decrease the minimum broadcast domination cost on the graph. The overall problem we consider minimizes the sum of edge construction costs and broadcast domination costs. We show that this problem is NP-hard in the strong sense, even on unweighted graphs. A decomposition strategy will iteratively add valid inequalities based on optimal broadcast domination solutions corresponding to the first-stage network design solutions. We demonstrate that our decomposition approach is computationally superior to the solution of a monolithic MIP formulation.

Algorithmic discrete mathematics plays a key role in the development of information and communication technologies, and methods that arise in computer science, mathematics and operations research – in particular in algorithms, computational complexity, distributed computing and optimization – are vital to modern services such as mobile telephony, online banking and VoIP. This book examines communication networking from a mathematical viewpoint. The contributing authors took part in the European COST action 293 – a four-year program of multidisciplinary research on this subject. In this book they offer introductory overviews and state-of-the-art assessments of current and future research in the fields of broadband, optical, wireless and ad hoc networks. Particular topics of interest are design, optimization, robustness and energy consumption. The book will be of interest to graduate students, researchers and practitioners in the areas of networking, theoretical computer science, operations research, distributed computing and mathematics.

Network flow and network design problems arise in various application areas of combinatorial optimization, e.g., in transportation, production, or telecommunication. This thesis contributes new results to four different problem classes from this area, providing models and algorithms with immediate practical impact as well as theoretical insights into complexity and combinatorial structure of network optimization problems: (i) We introduce a new model for tactical transportation planning that employs a cyclic network expansion to integrate routing and inventory decisions into a unified capacitated network design formulation. We also devise several algorithmic approaches to solve the resulting optimization problem and demonstrate the applicability of our approach on a set of real-world logistic networks. (ii) We present approximation algorithms for combined location and network design problems, including the first constant factor approximation for capacitated location routing. (iii) We derive a max-flow/min-cut theorem for abstract flows over time, a generalization of the well-known work of Ford and Fulkerson that restricts to a minimal set of structural requirements. (iv) We devise algorithms for finding orientations of embedded graphs with degree constraints on vertices and faces, answering an open question by Frank.

The problem of designing a cost-efficient network that survives the failure of one or more nodes or edges of the network is critical to modern telecommunications engineering. The method developed in this book is designed to solve such problems to optimality. In particular, a cutting plane approach is described, based on polyhedral combinatorics, that is ableto solve real-world problems of this type in short computation time. These results are of interest for practitioners in the area of communication network design. The book is addressed especially to the combinatorial optimization community, but also to those who want to learn polyhedral methods. In addition, interesting new research problemsare formulated.

Combinatorial optimization is a fascinating topic. Combinatorial optimization problems arise in a wide variety of important fields such as transportation, telecommunications, computer networking, location, planning, distribution problems, etc. Important and significant results have been obtained on the theory, algorithms and applications over the last few decades. In combinatorial optimization, many network design problems can be generalized in a natural way by considering a related problem on a clustered graph, where the original problem's feasibility constraints are expressed in terms of the clusters, i.e., node sets instead of individual nodes. This class of problems is usually referred to as generalized network design problems (GNDPs) or generalized combinatorial optimization problems. The express purpose of this monograph is to describe a series of mathematical models, methods, propositions, algorithms developed in the last years on generalized network design problems in a unified manner. The book consists of seven chapters, where in addition to an introductory chapter, the following generalized network design problems are formulated and examined: the generalized minimum spanning tree problem, the generalized traveling salesman problem, the railway traveling salesman problem, the generalized vehicle routing problem, the generalized fixed-charge network design problem and the generalized minimum vertex-biconnected network problem. The book will be useful for researchers, practitioners, and graduate students in operations research, optimization, applied mathematics and computer science. Due to the substantial practical importance of some presented problems, researchers in other areas will find this book useful, too.

This book constitutes the refereed proceedings of the 11th Algorithms and Data Structures Symposium, WADS 2009, held in Banff, Canada, in August 2009. The Algorithms and Data Structures Symposium - WADS (formerly "Workshop on Algorithms and Data Structures") is intended as a forum for researchers in the area of design and analysis of algorithms and data structures. The 49 revised full papers presented in this volume were carefully reviewed and selected from 126 submissions. The papers present original research on algorithms and data structures in all areas, including bioinformatics, combinatorics, computational geometry, databases, graphics, and parallel and distributed computing.

Andreas Bärmann develops novel approaches for the solution of network design problems as they arise in various contexts of applied optimization. At the example of an optimal expansion of the German railway network until 2030, the author derives a tailor-made decomposition technique for multi-period network design problems. Next, he develops a general framework for the solution of network design problems via aggregation of the underlying graph structure. This approach is shown to save much computation time as compared to standard techniques. Finally, the author devises a modelling framework for the approximation of the robust counterpart under ellipsoidal uncertainty, an often-studied case in the literature. Each of these three approaches opens up a fascinating branch of research which promises a better theoretical understanding of the problem and an increasing range of solvable application settings at the same time.

Telecommunications - central to our daily lives - continues to change dramatically. These changes are the result of technological advances, deregulation, the proliferation of broadband service offers, and the spectacular popularity of the Internet and wireless services. In such adynamic technological and economic environment, competition is increasing among service providers and among equipment manufacturers. Consequently, optimization of the planning process is becoming essential. Although telecommunications network planning has been tackled by the Operations Research community for some time, many fundamental problems remain challenging. Through its fourteen chapters, this book covers some new and some still challenging older problems which arise in the planning of telecommunication networks. Telecommunications Network Planning will benefit both telecommunications practitioners looking for efficient methods to solve their problems and operations researchers interested in telecommunications. The book examines network design and dimensioning problems; it explores Operation Research issues related to a new standard Asynchronous Transfer Mode (ATM); it overviews problems that arise when designing survivable SDH/SONET Networks; it considers some broadband network problems; and it concludes with three chapters on wireless and mobile networks. Leading area researchers have contributed their recent research on the telecommunications and network topics treated in the volume.

One of the most frequently occurring types of optimization problems involves decision variables which have to take integer values. From a practical point of view, such problems occur in countless areas of management, engineering, administration, etc., and include such problems as location of plants or warehouses, scheduling of aircraft, cutting raw materials to prescribed dimensions, design of computer chips, increasing reliability or capacity of networks, etc. This is the class of problems known in the professional literature as "discrete optimization" problems. While these problems are of enormous applicability, they present many challenges from a computational point of view. This volume is an update on the impressive progress achieved by mathematicians, operations researchers, and computer scientists in solving discrete optimization problems of very large sizes. The surveys in this volume present a comprehensive overview of the state of the art in discrete optimization and are written by the most prominent researchers from all over the world. This volume describes the tremendous progress in discrete optimization achieved in the last 20 years since the publication of Discrete Optimization '77, Annals of Discrete Mathematics, volumes 4 and 5, 1979 (Elsevier). It contains surveys of the state of the art written by the most prominent researchers in the field from all over the world, and covers topics like neighborhood search techniques, lift and project for mixed 0-1 programming, pseudo-Boolean optimization, scheduling and assignment problems, production planning, location, bin packing, cutting planes, vehicle routing, and applications to graph theory, mechanics, chip design, etc. Key features: • state of the art surveys • comprehensiveness • prominent authors • theoretical, computational and applied aspects. This book is a reprint of Discrete Applied Mathematics Volume 23, Numbers 1-3