Semidefinite Relaxations for Dynamic Combinatorial Optimization
Abstract
Motivated by the success of semidefinite relaxations in deterministic combinatorial optimization, the project will investigate semidefinite relaxation techniques for dynamic combinatorial optimization problems. In these models, the decision maker has only probabilistic information about a problem instance beforehand, and must make decisions sequentially, with partial information revealed in between consecutive decisions. The potential applications of such models include scheduling, resource allocation, real-time routing and surveillance, among others. Methodologically, the project will investigate both primal and dual approaches. On the primal side, the focus will be on deriving valid linear and non-linear constraints on a problem s achievable probabilities, which can be captured or relaxed using semidefinite techniques to obtain an efficient bound. On the dual side, we will study bounds derived from value function approximations defined by positive semidefinite matrices; value function approximations have the advantage of defining heuristic policies whose performance we will also investigate. In both approaches, we will explore the possibility of obtaining tight bounds for special cases, and we will additionally pursue the derivation of semidefinite relaxation hierarchies on the primal side, and dual-based exact algorithms based on dynamic basis generation for value function approximation. As a concrete focus, the project willinitially study a dynamic version of the classical node packing problem, also called the stable set or independent set problem, because of the fundamental importance of node packing in discrete optimization, and because the well-known semidefinite relaxation of deterministic node packing illustrates the technique s potential benefit over linear relaxation. Approved for public release.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jul 24, 2023
- Source ID
- N000142312631
Entities
People
- Alejandro Toriello
Organizations
- Georgia Tech Research Corporation
- Office of Naval Research
- United States Navy