Search

The article 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. A special feature of this linear program is that there can never be a loop in the basis, because the vectors corresponding to the variables of a loop are linearly dependent. The last comment is related to the dynamic programming algorithm. One is allowed to pass through a node more than once in the shortest route . The proposed method for solving this program consists of converting it into a shortest route problem containing exactly q arcs. But for some arbitrary reason, the dynamic program is formulated in such a way that one can never have starting node 1 more than once in the final solution.