Letter to the Editor—Comments on a Paper By Romesh Saigal: “A Constrained Shortest Route Problem”

Abstract

Romesh Saigal presents a zero-one linear program and a dynamic programming algorithm for finding the shortest route containing exactly q arcs from node 1 to node n in a network ( N , A ) with distances c ( i,j ). This note shows that the linear programming formulation and his extension based on it are defective, and that the dynamic programming algorithm can lead to suboptimal solutions, but a minor change in the dynamic programming formulation relieves the difficulty.