The tropical tiling of periodic timetable space and a dual modulo network simplex algorithm
- We propose a tropical interpretation of the solution space of the Periodic Event Scheduling Problem as a collection of polytropes, making use of the characterization of tropical cones as weighted digraph polyhedra. General and geometric properties of the polytropal collection are inspected and understood in connection with the combinatorial properties of the underlying periodic event scheduling instance. Novel algorithmic ideas are presented and tested, making use of the aforementioned theoretical results to solve and optimize the problem.
| Author: | Enrico BortolettoORCiD |
|---|---|
| Document Type: | Master's Thesis |
| MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING |
| CCS-Classification: | J. Computer Applications |
| Granting Institution: | Freie Universität Berlin |
| Advisor: | Ralf Borndörfer, Niels Lindner |
| Year of first publication: | 2021 |
