Geometry of the Reformulation-Linearization-Technique: Domination of Disjunctions
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915623718617088 |
|---|---|
| author | Hof, Hugo A. Walter, Matthias |
| author_facet | Hof, Hugo A. Walter, Matthias |
| contents | The reformulation-linearization-technique (RLT) is a well-known strengthening technique for binary mixed-integer optimization. It is well known to dominate lift-and-project strengthening, which is based on disjunctive programming (DP) for single-variable disjunctions. In contrast to the latter, the geometry of RLT is not understood completely. We provide some insights by characterizing the points in the corresponding RLT closure geometrically. We exploit this insight to show that RLT even dominates DP approaches based on cardinality equations with right-hand side 1. This is in contrast to cardinality inequalities with right-hand side 1, whose DPs are not dominated. Our results have applications in the strength comparison for the quadratic assignment problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_13805 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Geometry of the Reformulation-Linearization-Technique: Domination of Disjunctions Hof, Hugo A. Walter, Matthias Optimization and Control Discrete Mathematics The reformulation-linearization-technique (RLT) is a well-known strengthening technique for binary mixed-integer optimization. It is well known to dominate lift-and-project strengthening, which is based on disjunctive programming (DP) for single-variable disjunctions. In contrast to the latter, the geometry of RLT is not understood completely. We provide some insights by characterizing the points in the corresponding RLT closure geometrically. We exploit this insight to show that RLT even dominates DP approaches based on cardinality equations with right-hand side 1. This is in contrast to cardinality inequalities with right-hand side 1, whose DPs are not dominated. Our results have applications in the strength comparison for the quadratic assignment problem. |
| title | Geometry of the Reformulation-Linearization-Technique: Domination of Disjunctions |
| topic | Optimization and Control Discrete Mathematics |
| url | https://arxiv.org/abs/2511.13805 |