Efficiently Strengthening Disjunctive Cutting Planes
Abstract
The effort is to theoretically and computationally investigate the efficient generation, strengthening, and deployment of cuts from large disjunctions for general mixed-integer linear programs. Traditionally, such disjunctive cuts are obtained by solving a cut-generating linear program containing variables not only for the cut coefficients, but also for multipliers that certify the validity of the cut. These extra variable values are needed to apply a posteriori monoidal strengthening on the cuts, but solving the extended formulation is computationally prohibitive for larger disjunctions. As an alternative, the V-polyhedral perspective yields a linear program with only cut coefficients as variables. The resulting cuts are called VPCs. In early experiments, VPCs provide bound improvement when incorporated with common inequalities such as Gomory mixed-integer cuts (GMICs). However, individually, VPCs are on average outperformed by GMICs, even when VPCs are derived from much stronger disjunctions. One conjectured reason for this discrepancy is that VPCs cannot immediately benefit from monoidal strengthening. The proposed research will enable disjunctive cut generation through the VPC framework, while efficiently computing the values of the missing variables needed for strengthening. In experiments with a specialized version of the proposed strengthening, VPCs from two-term disjunctions benefit considerably from strengthening, but the results also highlight key challenges. These challenges motivate the current effort. Specifically, the research is to (1) build efficient cut strengthening for more general classes of VPCs and for larger disjunctions, (2) theoretically compare the properties of strong disjunctive cuts to GMICs, and (3) develop a theoretical model for selecting whether to apply strong but dense VPCs or weak but sparse GMICs. This work will offer a deeper understanding of strengthened cuts for mathematical optimization to improve algorithms for solving complex discrete problems.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Mar 06, 2024
- Source ID
- FA95502310340
Entities
People
- Aleksandr Kazachkov
Organizations
- Air Force Office of Scientific Research
- United States Air Force
- University of Florida