Innovative Techniques for Combinatorial Disjunctive Constraints (Tracking number: 23-000005160)
Abstract
Approved for Public ReleaseProject SummaryThe study of disjunctive constraints originated in the late 1970s from Balas, where he obtained extended formulations for general disjunctive programming, studied cutting plane methods, and characterized the convex hull of feasible points. Thereafter, modeling disjunctive constraints has become an important topic in mixed integer programming (MIP) with numerous applications, such as chemical engineering, robotics, portfolio optimization, and scheduling. The overall goal of the proposed plan is the development of tools and techniques in combinatorial optimization for problems that arise in disjunctive convex programs utilizing combinatorial disjunctive constraints (CDCs). CDCs provide a way to model disjunctive programs where instead of using disjunctions to improve dual bounds via adding disjunctive cuts within a cutting plane framework, the idea is to improve the dual bounds by building a strong formulation from the beginning using CDCs. The main benefit is that the combinatorial structure is much simpler to reason about and formulate as it is #data independent# as compared to a big-M formulation where the M-values are solely dependent upon the rest of the problem data. As a result, CDC techniques are more tractable to derive strong formulations. As partof the proposed work, the PI plans to investigate the connections between CDCs and hypergraphs (graphs); develop new techniques utilizing CDCs for quadratic and bilinear constraints; explore the connection between CDCs and path-planning; investigate CDC techniques for general convex disjunctions; and evaluate the computational efficacy of these proposed techniques. Hence, extending the knowledge base in discrete optimization while contributing to applications in the aforementioned fields.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Nov 09, 2024
- Source ID
- N000142412648
Entities
People
- Illya V. Hicks
Organizations
- Office of Naval Research
- Rice University
- United States Navy