Tree-based formulation for the multi-commodity flow problem
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_ | 1866911188472823808 |
|---|---|
| author | Spoorendonk, Simon Petersen, Bjørn |
| author_facet | Spoorendonk, Simon Petersen, Bjørn |
| contents | We introduce a tree-based formulation for the minimum-cost multi-commodity flow problem that addresses large-scale instances. The method decomposes the source-based model by representing flows as convex combinations of trees rooted at source nodes, and solves the resulting formulation with column generation. The number of demand constraints now depends on the number of sources $|S|$, not commodities $|K|$, yielding a compact master problem when $|S| \ll |K|$. We conduct a computational study comparing tree-based decomposition against path-based column generation and direct LP solving. The results show speed-ups of up to one order of magnitude over direct LP solving, and improved scalability compared to path-based formulations. Tree-based decomposition enables solving instances with millions of commodities and hundreds of thousands of nodes. This makes it well-suited for applications in transportation and logistics networks where multiple demands often share common origins. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_24656 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tree-based formulation for the multi-commodity flow problem Spoorendonk, Simon Petersen, Bjørn Optimization and Control Discrete Mathematics We introduce a tree-based formulation for the minimum-cost multi-commodity flow problem that addresses large-scale instances. The method decomposes the source-based model by representing flows as convex combinations of trees rooted at source nodes, and solves the resulting formulation with column generation. The number of demand constraints now depends on the number of sources $|S|$, not commodities $|K|$, yielding a compact master problem when $|S| \ll |K|$. We conduct a computational study comparing tree-based decomposition against path-based column generation and direct LP solving. The results show speed-ups of up to one order of magnitude over direct LP solving, and improved scalability compared to path-based formulations. Tree-based decomposition enables solving instances with millions of commodities and hundreds of thousands of nodes. This makes it well-suited for applications in transportation and logistics networks where multiple demands often share common origins. |
| title | Tree-based formulation for the multi-commodity flow problem |
| topic | Optimization and Control Discrete Mathematics |
| url | https://arxiv.org/abs/2509.24656 |