Back to Search
Start Over
Letter to the Editor—Comments on a Paper By Romesh Saigal: 'A Constrained Shortest Route Problem'
- Source :
- Operations Research. 16:1232-1234
- Publication Year :
- 1968
- Publisher :
- Institute for Operations Research and the Management Sciences (INFORMS), 1968.
-
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.
- Subjects :
- Dynamic programming
Combinatorics
Route problem
Linear programming
Node (networking)
Minor (linear algebra)
Computer Science::Programming Languages
Linear programming formulation
Extension (predicate logic)
Management Science and Operations Research
Computer Science Applications
Mathematics
Subjects
Details
- ISSN :
- 15265463 and 0030364X
- Volume :
- 16
- Database :
- OpenAIRE
- Journal :
- Operations Research
- Accession number :
- edsair.doi...........39023a3005aa1c5ba33d6d64986a2cc2