Better Integrality Gaps for Network Optimization Problems
Abstract
This proposal aims to study strengthening mathematical programming relaxations for NP-hard combinatorial optimization problems using two broad thrusts. We will evaluate the strength of a relaxation by the notion of its integrality gap, and prefer formulations where the provable bound on the integrality gap is small. The first thrust is on large formulations that typically contain an exponential number of valid constraints where the goal is to identify the relevant smaller (polynomial sized) subset of these constraints that are sufficient to bound the integrality gap. This is the idea behind what we might call semicompact formulations where our goal is to find these relevantconstraints (i) by using the objective coefficients and (ii) in time faster than actually solving the full relaxation to optimality. The second thrust is to advance our understanding of the integrality gapsfor graph connectivity problems. Our investigations will cover a broad range of Combinatorial Optimization problems while focusing on connectivity problems in networks such as the Traveling Salesman Problem (TSP) and its close relative, the two-edge-connected subgraph problem (2EC).The technical heart of the proposal consists of developing two sets of techniques. In the search for semicompact formulations, our goal is to select a subset of constraints of a well-studied large relaxation, based on the objective coefficients in the given instance; the challenge is to show a bound on the integrality gap with just the selected constraints without spending as much computational effort (time and space) as a full approximation algorithm constructively proving the gap or a solver that finds the optimal relaxation solution for the given instance. In this way, we want to exploit the costs in theinstance and the power of nonconstructive proofs of integrality gaps for computational benefit. In our second thrust, we want to deepen our understanding of existing techniques and develop new ones for the TSP and 2EC for which known upper bounds on the integrality gap are far from the conjectured targets.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Apr 06, 2021
- Source ID
- N000142112243
Entities
People
- Ramamoorthi Ravi
Organizations
- Carnegie Mellon University
- Office of Naval Research
- United States Navy