Letter to the Editor—Finding Minimal Cost-Time Ratio Circuits

In the treatment of routing problems, other authors have used column generators to introduce, into the basis of the master problem, the solution that corresponds to a cycle in a graph with minimal cost-to-time ratio. This subproblem is of independent interest and corresponds to deterministic Markov renewal programming; this note presents an efficient method for its solution, intuitive basis for which is a search for a way to route flow so that the cost-time trade-off is optimal. This flow-circulation problem is solved parametrically by the out-of-kilter algorithm.