Back to Search
Start Over
New finite relaxation hierarchies for concavo-convex, disjoint bilinear programs, and facial disjunctions
- Publication Year :
- 2024
-
Abstract
- We introduce new relaxation hierarchies for facial disjunctive programs (FD) and concavo-convex programs, where the latter class of problems includes disjoint bilinear programming (DBP) and concave minimization (CM) as special cases. Meanwhile, FD restricts that feasible solutions belong to a collection of faces of a Cartesian product of polytopes and generalizes 0-1 programs. We construct these relaxation hierarchies by utilizing rational functions that are barycentric coordinates for polytopes and derive these expressions using the double-description (DD) procedure. The hierarchies, which have geometric and algebraic underpinnings, converge to the convex hull for these problems at a finite level. Our hierarchy provides the first unifying framework to analyze and tighten relaxations from disjunctive programming (DP) and reformulation-linearization technique (RLT) for these problem classes.
- Subjects :
- Mathematics - Optimization and Control
65K05, 90C26, 90C11, 90C57
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2405.11068
- Document Type :
- Working Paper