Imposing Connectivity Constraints in Large-Scale Network Problems

Oklahoma State University, Stillwater OK

Investigators

Abstract

The design and analysis of networks constitute one of the most important classes of problems in the field of optimization. In practice, network models are used to address such diverse applications as wireless communication, energy distribution, and conservation planning. A network consists essentially of a set of "nodes", linked in some fashion by "arcs". Connectedness is often a critical feature of a functioning network. However, enforcing connectivity in standard network optimization formulations remains a significant computational challenge. This project considers new formulations that address node-connectivity constraints directly. Results from this project are expected to allow for the solution of large-scale instances of these problems to optimality in a reasonable amount of time. The PI will mentor graduate and undergraduate students, and through collaboration with the Oklahoma Louis Stokes Alliance for Minority Participation (OK-LSAMP), students from underrepresented populations will be provided the opportunity to participate in the research activities. Results from the project will be integrated into undergraduate and graduate courses. This project aims to develop fundamental theoretical and algorithmic advances for effectively imposing connectivity constraints in mixed integer programming (MIP) models in which the key decisions are at the vertex (i.e., node) level. Previous MIP-based approaches to solve vertex-centric connectivity problems use additional edge (and possibly flow) variables, which overburden commercial solvers, or rely on simple, weak inequalities, leading to the exploration of a large number of branch-and-bound nodes. This research is expected to overcome these limitations through two broad research tasks: (1) developing a rich body of knowledge about connectivity polyhedra in the space of vertex variables, and (2) designing efficient algorithms for solving related problems by exploiting this polyhedral information. It is expected that the research will also allow for significant improvements in solving hop-constrained and survivable network design problems.