Exact Decomposition Branching exploiting Lattice Structures
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912093470457856 |
|---|---|
| author | Halbig, Katrin Oertel, Timm Weninger, Dieter |
| author_facet | Halbig, Katrin Oertel, Timm Weninger, Dieter |
| contents | Strict inequalities in mixed-integer linear optimization can cause difficulties in guaranteeing convergence and exactness. Utilizing that optimal vertex solutions follow a lattice structure we propose a rounding rule for strict inequalities that guaranties exactness. The lattice used is generated by $Δ$-regularity of the constraint matrix belonging to the continuous variables. We apply this rounding rule to Decomposition Branching by Yildiz et al., which uses strict inequalities in its branching rule. We prove that the enhanced algorithm terminates after finite many steps with an exact solution. To validate our approach, we conduct computational experiments for two different models for which $Δ$-regularity is easily detectable. The results confirm the exactness of our enhanced algorithm and demonstrate that it typically generates smaller branch-and-bound trees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_22147 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Exact Decomposition Branching exploiting Lattice Structures Halbig, Katrin Oertel, Timm Weninger, Dieter Optimization and Control 90C11, 90C57 Strict inequalities in mixed-integer linear optimization can cause difficulties in guaranteeing convergence and exactness. Utilizing that optimal vertex solutions follow a lattice structure we propose a rounding rule for strict inequalities that guaranties exactness. The lattice used is generated by $Δ$-regularity of the constraint matrix belonging to the continuous variables. We apply this rounding rule to Decomposition Branching by Yildiz et al., which uses strict inequalities in its branching rule. We prove that the enhanced algorithm terminates after finite many steps with an exact solution. To validate our approach, we conduct computational experiments for two different models for which $Δ$-regularity is easily detectable. The results confirm the exactness of our enhanced algorithm and demonstrate that it typically generates smaller branch-and-bound trees. |
| title | Exact Decomposition Branching exploiting Lattice Structures |
| topic | Optimization and Control 90C11, 90C57 |
| url | https://arxiv.org/abs/2410.22147 |