Метод ветвей и границ в динамическом программировании

Вероятно, многим из применявших динамическое программирование в задачах дискретной оптимизации приходила в голову идея отбрасывать часть состояний (позиций) как бесперспективные на по возможности раннем этапе построения функции Беллмана — ведь так можно сэкономить и память и вычисления. Оказывается, в 1976 году эта идея была строго оформлена Мориным и Марстеном в применении к задаче коммивояжера и нелинейной задаче о рюкзаке. Судя по цитированиям статьи, никто не успел применить этот метод к задаче курьера, между тем, он кажется достаточно интересным, ведь нижние границы можно получать через Конкорд. Оригинальная статья: 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