Automating Idealness Proofs for Binary Programs with Application to Rectangle Packing
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929411381526528 |
|---|---|
| author | Fravel, Jamie Hildebrand, Robert |
| author_facet | Fravel, Jamie Hildebrand, Robert |
| contents | We develop an optimization framework for identifying ideal Mixed Binary Linear Programs (MBLP) which is linear when using known input data and nonconvex quadratic over parametric input data. These techniques are applied to various formulations for rectangle packing, conjectured to be pairwise-ideal. Additionally, we address a variation of the rectangle packing problem which incorporates clearances along selected edges of the packed objects. We present both existing and novel MBLP formulations for the underlying disjunctive program and investigate the poor performance of Gurobi's default branch-and-cut methodology. We operate under a strip-packing objective that aims to minimize the overall height of the packed objects. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_04867 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Automating Idealness Proofs for Binary Programs with Application to Rectangle Packing Fravel, Jamie Hildebrand, Robert Optimization and Control We develop an optimization framework for identifying ideal Mixed Binary Linear Programs (MBLP) which is linear when using known input data and nonconvex quadratic over parametric input data. These techniques are applied to various formulations for rectangle packing, conjectured to be pairwise-ideal. Additionally, we address a variation of the rectangle packing problem which incorporates clearances along selected edges of the packed objects. We present both existing and novel MBLP formulations for the underlying disjunctive program and investigate the poor performance of Gurobi's default branch-and-cut methodology. We operate under a strip-packing objective that aims to minimize the overall height of the packed objects. |
| title | Automating Idealness Proofs for Binary Programs with Application to Rectangle Packing |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2407.04867 |