Branch & Solve for Hub Location
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908478106238976 |
|---|---|
| author | Fernández, Elena Zerega, Nicolás |
| author_facet | Fernández, Elena Zerega, Nicolás |
| contents | This paper introduces a new formulation and solution framework for hub location problems. The formulation is based on 2-index aggregated flow variables and incorporates a set of aggregated demand constraints, which are novel in hub location. With minor adaptations, the approach applies to a large class of single- and multiple-allocation models, possibly incorporating flow bounds on activated arcs. General-purpose feasibility and optimality inequalities are also developed. Because of the small number of continuous variables, there is no need to project them out, differentiating the method from solution algorithms that rely heavily on feasibility and optimality cuts. The proposed Branch & Solve solution framework leverages the nested structure of the problems, by solving auxiliary subproblems at selected nodes of the enumeration tree. Extensive computational experiments on benchmark instances from the literature confirm the good performance of the proposal: the basic version of the algorithm is able to solve to proven optimality instances with up to 200 nodes for several hub location families. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_02665 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Branch & Solve for Hub Location Fernández, Elena Zerega, Nicolás Optimization and Control This paper introduces a new formulation and solution framework for hub location problems. The formulation is based on 2-index aggregated flow variables and incorporates a set of aggregated demand constraints, which are novel in hub location. With minor adaptations, the approach applies to a large class of single- and multiple-allocation models, possibly incorporating flow bounds on activated arcs. General-purpose feasibility and optimality inequalities are also developed. Because of the small number of continuous variables, there is no need to project them out, differentiating the method from solution algorithms that rely heavily on feasibility and optimality cuts. The proposed Branch & Solve solution framework leverages the nested structure of the problems, by solving auxiliary subproblems at selected nodes of the enumeration tree. Extensive computational experiments on benchmark instances from the literature confirm the good performance of the proposal: the basic version of the algorithm is able to solve to proven optimality instances with up to 200 nodes for several hub location families. |
| title | Branch & Solve for Hub Location |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2508.02665 |