Integrality Gaps for Hard Network Optimization Problems
Abstract
Network optimization problems that arise in a variety of applications such as logistics, communications and distribution have served" as canonical workhorses for the development of new methods for solving discrete optimization problems. Most of these methods involv"e devising natural mathematical programming relaxations for fundamental network designproblems, and using their solution as a guide"" to find near-optimal discrete solutions. An important measure of the effectiveness of such relaxations is their integrality gap, th""e worst-case ratio between the optimal values of the integral solutions and their continuous relaxation, over all possible cost inst""ances.This proposal aims to study integrality gaps for computationally hard network optimization problems from two angles, for the" computational design of new approximation algorithms and for understanding the strength of the formulation structurally. In the for"mer, the goal is to design new algorithms that give improved proofs of integrality gaps for NP-hard problems thereby deriving new ap""proximation algorithms. In the latter, the goal is to devise new non-constructiveproofs of improved integrality gaps that shed ligh""t on the strength of these relaxations both for exact computational methods like branch-and-bound, as well as in other problems that" use these relaxations as their basis. The motivation for the computational study of integrality gaps comes from the success of su"ch investigations in developing new techniques for rounding the LP relaxations for NP-hard problems. In particular, the adaptations"" of primal-dual algorithms, randomized rounding and the recent iterative rounding methods are all examples of new tools that were ad""ded to the approximation algorithm design toolkit motivated by such computational integrality gap proofs. On the other hand, the stu"dy of existential proofs of integrality gaps that are non constructive have shed light on the use of such relaxations in effective s"earch for exact computational methods for solving them, as well as in strengthening these relaxations with stronger valid inequaliti""es. As a byproduct, our search for computational and structural insights can be integrated into a general purpose tool that works on" finding convex decomposition of scaled linear-programming relaxations and provides a suite of integer solutions for large classes of network optimization problems.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jan 23, 2018
- Source ID
- N000141812099
Entities
People
- Ramamoorthi Ravi
Organizations
- Massachusetts Institute of Technology
- Office of Naval Research
- United States Navy