Ваш браузер устарел.

Для того, чтобы использовать все возможности сайта, загрузите и установите один из этих браузеров.

скрыть

Article

  • Title

    Comparative characteristic of branch and bound method algorithms for solving the problems of integer linear programming

  • Authors

    Yukhimenko B. I.
    Kozina Yu. Yu.

  • Subject

    FUNDAMENTAL AND APPLIED SCIENCES PROBLEMS

  • Year 2005
    Issue 2(24)
    UDC 519.852: 004.424.27.021
    DOI
    Pages 199 - 203
  • Abstract

    The results of studying some branch and bound method algorithms for convergence speed are pre-sented. The algorithms are alike by the methods of estimating the variants set of problems solving and are different by the ways of branching. Estimation is performed by solving several one-dimensional knap-sack problems, assuming, however, that the variable accepts the value 0 or a so-called standard unit, that is calculated on the basis of the task restrictions system. There are two ways of branching: by sequential varia-ble selection and a combined one, when the number of a concretized variable is calculated in a special way.

  • Keywords
  • Viewed: 1235 Dowloaded: 4
  • Download Article
  • References

    1.    Land A.H. An Automatic method of solving discrete programming problems / Land A.H., Doig A.G. // Econometrica. — 1960. — Vol. 28, № 3. — P. 497 — 520.
    2.    Корбут А.А. Метод ветвей и границ (обзор теории, алгоритмов, программ и приложений) / Кор-бут А.А. Сигал И.Х., Финкельштейн Ю.Ю. // Math. Operationsforsch. Statist. Ser.Optimization. —1997. —Vol. 20, № 2. — P. 253 — 280.
    3.    Balas E. An additive algorithm for solving linear programs with zero – one variables // Oper. Res. — 1965. — Vol. 13, № 4. —  P.517 — 546.
    4.    Корбут А.А. Дискретное программирование / Корбут А.А., Финкельштейн Ю.Ю. — М.: Наука, 1969. — 320 с.
    5.    Юхименко Б.І. Вибір ефективного алгоритму розв’язання задач цілочисельного лінійного про-грамування // Тр. Одес. политехн. ун-та. — 2003. — Вып. 2. — С. 172 — 176.
    6.    Юхименко Б.И. Разработка и обоснование некоторых схем и методов дискретной оптимизации в автоматизации функций распределения – размещения в АСУ: Автореф дис… канд. экон. наук. — Одесса, 1982. — 20 с.
    7.    Юхименко Б.И. Ускоренный алгоритм метода ветвей и границ для решения задачи целочислен-ного линейного программирования // Тр. Одес. политехн. ун-та. — 2004. — Вып. 2. — С. 223 — 226.
    8.    Михалевич В.С. Последовательные алгоритмы оптимизации и их применение // Кибернетика. — 1965, № 1. — C. 45 — 55.

  • Creative Commons License by Author(s)