Proceedings of the RHSAS

PROCEEDINGS OF THE RUSSIAN HIGHER SCHOOL
ACADEMY OF SCIENCES

Print ISSN: 1727-2769    Online ISSN: 2658-3747
English | Русский

Recent issue
№2(67) April - June 2025

BRANCH AND BINARY CUTS APPROACH OF INTEGER PROGRAMMING

Issue No 1 (16) January-June 2011
Authors:

Mesentsev Yuriy
Abstract

The numerical method of solving of LP problems with Boolean variables is offered. The method is based on iterative application of procedure of designing of cutting planes taking into account properties of LP problems with Boolean variables as much as possible.



Heuristic procedures of synthesis of the cuts, which have entailed expediency use of a tree of solutions, are applied.


Keywords: Integer programming, Binary cuts, Effective algorithm, Decision tree.

References

[1]       Леонтьев В. К. Дискретная оптимизация // Журнал вычислительной математики и математической физики. – 2007. – Том 47. – № 2. – С. 338–352.



[2]       Korte B., Vygen J. Combinatorial optimization. Theory and algorithms. Springer, 2002. – 572 р.



[3]       Du D., Pardalos P. (eds.) Handbook of combinatorial optimization. Supplement vol. A, Kluwer academic publishers, 1999. – 649p.



[4]       Du D., Pardalos P. (eds.) Handbook of combinatorial optimization. Supplement vol. B. Springer, 2005. – 403p.



[5]       Заславский А.А., Лебедев С.С. Метод узловых векторов целочисленного программирования // Препринт # WP/2000/94. – М.: ЦЭМИ РАН 2000. – 81 с.



[6]       Glover F., Kochenberger G.A. eds. Handbook of metaheuristics // Kluwer academic publishers, 2003. – 560 p.



[7]       IBM ILOG CPLEX V12.1 User's Manual for CPLEX. IBM Corporation, 2009. – 952 c.



[8]       Мезенцев Ю.А. Эффективный алгоритм целочисленного программирования. // Научный вестник НГТУ. – 2009. – № 2(35). – С. 91–114.



[9]       Хохлюк В. И. Параллельные алгоритмы целочисленной оптимизации. – М.: Радио и связь, 1987. – 224 c.



[10]    Ху Т. Целочисленное программирование и потоки в сетях. – М.: Мир, 1974. – 520 с.



[11]    Кнут Д. Искусство программирования для ЭВМ, том 3: Сортировка и поиск. – М.: Мир, 1978. – 812 с.



[12]    Муртаф Б. Современное линейное программирование. – М.: Мир, 1984. – 224 с.



[13]    Лихтенштейн В.Е. Дискретность и случайность в экономико-математических задачах. – М.: Наука, 1973. – 375 с.

Views: 1404