Facial reduction for semidefinite relaxations of combinatorial problems
Abstract
The project is to develop new preprocessing techniques for the purpose of solving combinatorial optimization (CO) problems more efficiently. CO problems have broad applications in a variety of areas that include transportation science, scheduling, logistics planning, and resource allocation. Efficient algorithms for solving semidefinite programming (SDP) relaxations are a key ingredient for optimally solving CO problems. There is, however, a critical bottleneck in using SDP relaxations; the formulations are required to satisfy certain regularity conditions, and these conditions are not easy to meet. This bottleneck obstructs the generic application of SDP approaches. This project will develop an effective method to restore certain regularity conditions for SDP relaxations of CO problems. The proposed method uses a technique called facial reduction (FR). The intent is to develop a fully automated method that can be applied to SDP relaxations, and require the user to have no background knowledge of FR. It will be designed to exploit underlying structures of CO problems and will be integrated within a branch-and-bound scheme.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Mar 06, 2024
- Source ID
- FA95502310508
Entities
People
- Hao Hu
Organizations
- Air Force Office of Scientific Research
- Clemson University
- Office of the Secretary of Defense