Networks: A study in Analysis and Design

In this dissertation, we will look at two fundamental aspects of Networks: Network Analysis and Network Design. In part A, we look at Network Analysis area of the dissertation which involves finding the densest subgraph in each graph. The densest subgraph extraction problem is fundamentally a non-linear optimization problem. Nevertheless, it can be solved in polynomial time by an exact algorithm based on the iterative solution of a series of max-flow sub-problems. To approach graphs with millions of vertices and edges, one must resort to heuristic algorithms. We provide an efficient implementation of a greedy heuristic from the literature that is extremely fast and has some nice theoretical properties. An extensive computational analysis shows that the proposed heuristic algorithm proved very effective on many test instances, often providing either the optimal solution or near-optimal solution within short computing times. In part-B, we discuss Network design, which is a cornerstone of mathematical optimization, is about defining the main characteristics of a network satisfying requirements on connectivity, capacity, and level-of-service. In multi-commodity network design, one is required to design a network minimizing the installation cost of its arcs and the operational cost to serve a set of point-to-point connections. This prototypical problem was recently enriched by additional constraints imposing that each origin-destination of a connection is served by a single path satisfying one or more level-of-service requirements, thus defining the Network Design with Service Requirements. These constraints are crucial, e.g., in telecommunications and computer networks, in order to ensure reliable and low-latency communication. We provide a new formulation for the problem, where variables are associated with paths satisfying the end-to-end service requirements. A fast algorithm for enumerating all the exponentially-many feasible paths and, when this is not viable, a column generation scheme that is embedded into a branch-and-cut-and-price algorithm is provided.