New finite relaxation hierarchies for concavo-convex, disjoint bilinear programs, and facial disjunctions
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912731262615552 |
|---|---|
| author | Tawarmalani, Mohit |
| author_facet | Tawarmalani, Mohit |
| contents | This paper introduces novel relaxation hierarchies for concavo-convex programs (CXP), a class of problems that includes disjoint bilinear programming (DBP) and concave minimization (CM) as special cases. At the core of these hierarchies is an algorithm based on double-description (DD) that computes the barycentric coordinates of a polyhedral cone as rational, non-negative functions representing multipliers associated with the cone's rays. These hierarchies combine geometric structure derived from barycentric coordinates with algebraic techniques via rational functions, achieving the convex hull in $m$ iterations, where $m$ is the number of inequalities that a subset of the variables must satisfy. Our framework offers the first unified approach to analyze and tighten relaxations from disjunctive programming (DP) and reformulation-linearization technique (RLT) for CXP. We also demonstrate that our methods extend to facial disjunctive programs (FDP), where solutions are constrained to lie on faces of a Cartesian product of polytopes, generalizing known hierarchies for 0-1 programs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_11068 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | New finite relaxation hierarchies for concavo-convex, disjoint bilinear programs, and facial disjunctions Tawarmalani, Mohit Optimization and Control 65K05, 90C26, 90C11, 90C57 This paper introduces novel relaxation hierarchies for concavo-convex programs (CXP), a class of problems that includes disjoint bilinear programming (DBP) and concave minimization (CM) as special cases. At the core of these hierarchies is an algorithm based on double-description (DD) that computes the barycentric coordinates of a polyhedral cone as rational, non-negative functions representing multipliers associated with the cone's rays. These hierarchies combine geometric structure derived from barycentric coordinates with algebraic techniques via rational functions, achieving the convex hull in $m$ iterations, where $m$ is the number of inequalities that a subset of the variables must satisfy. Our framework offers the first unified approach to analyze and tighten relaxations from disjunctive programming (DP) and reformulation-linearization technique (RLT) for CXP. We also demonstrate that our methods extend to facial disjunctive programs (FDP), where solutions are constrained to lie on faces of a Cartesian product of polytopes, generalizing known hierarchies for 0-1 programs. |
| title | New finite relaxation hierarchies for concavo-convex, disjoint bilinear programs, and facial disjunctions |
| topic | Optimization and Control 65K05, 90C26, 90C11, 90C57 |
| url | https://arxiv.org/abs/2405.11068 |