|
|
Seminar of Control System Department
May 28, 2015 12:00, Ekaterinburg, ul. S Kovalevskoi, 16, room 322
|
|
|
|
|
|
Branch-and-bound method in Dynamic Programming
Ya. V. Salii |
Number of views: |
This page: | 123 |
|
Abstract:
Probably many of those that apply dynamic programming to discrete optimization problems thought of omitting some states at a preferably early stage of construction of the Bellman function as 'certifiably useless;' obviously, this would saved both time and space. Turns out, in 1976 Morin and Marsten rigorously implemented this strategy for the traveling salesman problem and the nonlinear knapsack problem.
As far as the citations of the paper are concerned, nobody ever applied this method to Precedence Constrained TSP (also known as Sequential Ordering Problem), which, however, seems to be interesting due to the possibility of applying, say, Concorde to obtain the lower bounds for subproblems.
The original paper:
Branch-And-Bound Strategies for Dynamic Programming / Th.L.Morin, R.E.Marsten // Operations Research. – Vol. 24 – No. 4 (Jul. - Aug. 1976), pp. 611–627
|
|