Three-phase time minimization transportation problem with non-idle phases: a polynomial two-witness algorithm
math.OC, cs.DS
Submitted: 2026-11-01
Updated: 2026-11-01
Comments: 44 pages (37-page main article and 7-page supplement), 0 figures; reproducibility code and data included as ancillary files
Code: https://github.com/ERGO-Code/HiGHS
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
The gist: The three-phase time minimization transportation problem partitions the origin-terminal links into three sets used in consecutive phases and minimizes the sum of the phase shipment times.
Abstract
The three-phase time minimization transportation problem partitions the origin-terminal links into three sets used in consecutive phases and minimizes the sum of the phase shipment times. Optimal solutions may leave a phase idle, as in the main example of the original study. We require every phase to carry a positive integer quantity while leaving the split of the total requirement across phases free. Discarding idle solutions from the original algorithm does not, in general, solve this variant. We prove that the optimum is attained by fixing one witness link in each of two phases and deciding the third phase by a single network flow computation, with the optimal Phase-3 time of each witness pair located by binary search. The resulting exact algorithm is strongly polynomial. It extends to any fixed number of phases, whereas, when the number of phases is part of the input, even non-idle feasibility is strongly NP-complete; feasibility alone is fixed-parameter tractable in the number of phases via known rainbow-matching results. We also characterize the minimum time of each phase. On the main example, non-idleness raises the optimum from 38 to 41. On 3,650 random instances with up to 50 times50 links the algorithm took at most 50.2 seconds, and non-idleness raised the optimal value in 41% of the 2,250 instances with equal phase sizes; on 90 sampled instances it was faster than a mixed integer programming solver on 80 with a direct formulation and on 65 with a tighter threshold formulation.
Sources
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise