arXiv preprint ·
Three-phase time minimization transportation problem with non-idle phases: a polynomial two-witness algorithm
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Optimization & Control
Benign population landscapes do not transfer to empirical risk minimization in nonsmooth optimization
Conditional stopping guarantees for a folded parametrization of reduced Stokes vectors
Optimal Annuitization, Consumption, and Investment with Costly Capital Injections
Dual Path Following for an Aerial Manipulator Under State and Input Constraints via Transverse Feedback Linearization
The Staged Pandora's Box: Reservation Indices for Multi-Fidelity Bayesian Optimization
Get the few papers worth your time in Optimization & Control every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.