Solving Unsplittable Network Flow Problems with Decision Diagrams
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917621873508352 |
|---|---|
| author | Salemi, Hosseinali Davarnia, Danial |
| author_facet | Salemi, Hosseinali Davarnia, Danial |
| contents | In unsplittable network flow problems, certain nodes must satisfy a combinatorial requirement that the incoming arc flows cannot be split or merged when routed through outgoing arcs. This so-called "no-split no-merge" requirement arises in unit train scheduling where train consists should remain intact at stations that lack necessary equipment and manpower to attach/detach them. Solving the unsplittable network flow problems with standard mixed-integer programming formulations is computationally difficult due to the large number of binary variables needed to determine matching pairs between incoming and outgoing arcs of nodes with no-split no-merge constraint. In this paper, we study a stochastic variant of the unit train scheduling problem where the demand is uncertain. We develop a novel decision diagram (DD)-based framework that decomposes the underlying two-stage formulation into a master problem that contains the combinatorial requirements, and a subproblem that models a continuous network flow problem. The master problem is modeled by a DD in a transformed space of variables with a smaller dimension, leading to a substantial improvement in solution time. Similarly to the Benders decomposition technique, the subproblems output cutting planes that are used to refine the master DD. Computational experiments show a significant improvement in solution time of the DD framework compared with that of standard methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_01844 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Solving Unsplittable Network Flow Problems with Decision Diagrams Salemi, Hosseinali Davarnia, Danial Optimization and Control In unsplittable network flow problems, certain nodes must satisfy a combinatorial requirement that the incoming arc flows cannot be split or merged when routed through outgoing arcs. This so-called "no-split no-merge" requirement arises in unit train scheduling where train consists should remain intact at stations that lack necessary equipment and manpower to attach/detach them. Solving the unsplittable network flow problems with standard mixed-integer programming formulations is computationally difficult due to the large number of binary variables needed to determine matching pairs between incoming and outgoing arcs of nodes with no-split no-merge constraint. In this paper, we study a stochastic variant of the unit train scheduling problem where the demand is uncertain. We develop a novel decision diagram (DD)-based framework that decomposes the underlying two-stage formulation into a master problem that contains the combinatorial requirements, and a subproblem that models a continuous network flow problem. The master problem is modeled by a DD in a transformed space of variables with a smaller dimension, leading to a substantial improvement in solution time. Similarly to the Benders decomposition technique, the subproblems output cutting planes that are used to refine the master DD. Computational experiments show a significant improvement in solution time of the DD framework compared with that of standard methods. |
| title | Solving Unsplittable Network Flow Problems with Decision Diagrams |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2301.01844 |