Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.15345 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915122801278976 |
|---|---|
| author | Papageorgiou, Dimitri J. Trespalacios, Francisco |
| author_facet | Papageorgiou, Dimitri J. Trespalacios, Francisco |
| contents | An elementary, but fundamental, operation in disjunctive programming is a basic step, which is the intersection of two disjunctions to form a new disjunction. Basic steps bring a disjunctive set in regular form closer to its disjunctive normal form and, in turn, produce relaxations that are at least as tight. An open question is: What are guaranteed bounds on the improvement from a basic step? In this paper, using properties of a convex disjunctive program's hull reformulation and multipliers from Lagrangian decomposition, we introduce an operation called a pseudo basic step and use it to provide provable bounds on this improvement along with techniques to exploit this information when solving a disjunctive program as a convex MINLP. Numerical examples illustrate the practical benefits of these bounds. In particular, on a set of K-means clustering instances, we make significant bound improvements relative to state-of-the-art commercial mixed-integer programming solvers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_15345 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Pseudo basic steps: Bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming Papageorgiou, Dimitri J. Trespalacios, Francisco Optimization and Control An elementary, but fundamental, operation in disjunctive programming is a basic step, which is the intersection of two disjunctions to form a new disjunction. Basic steps bring a disjunctive set in regular form closer to its disjunctive normal form and, in turn, produce relaxations that are at least as tight. An open question is: What are guaranteed bounds on the improvement from a basic step? In this paper, using properties of a convex disjunctive program's hull reformulation and multipliers from Lagrangian decomposition, we introduce an operation called a pseudo basic step and use it to provide provable bounds on this improvement along with techniques to exploit this information when solving a disjunctive program as a convex MINLP. Numerical examples illustrate the practical benefits of these bounds. In particular, on a set of K-means clustering instances, we make significant bound improvements relative to state-of-the-art commercial mixed-integer programming solvers. |
| title | Pseudo basic steps: Bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2501.15345 |