Том 24, номер 4, 2017 г., Стр. 95-110

УДК 519.8
Симанчёв Р. Ю.
О неравенствах, порождающих фасеты комбинаторных многогранников

Аннотация:
Одним из центральных вопросов полиэдральной комбинаторики является вопрос об алгоритмической взаимосвязи вершинного и фасетного описаний выпуклых многогранников. С точки зрения комбинаторной оптимизации основной причиной актуальности этого вопроса является возможность применения методов выпуклого анализа к решению экстремальных комбинаторных задач. В настоящей работе рассматриваются комбинаторные многогранники достаточно общего вида. Получен ряд необходимых и достаточное условия фасетности опорных к многограннику неравенств, дана иллюстрация применения разработанной техники к многограннику задачи аппроксимации графа.
Библиогр. 20.

Ключевые слова: многогранник, фасета, $M$-граф, опорное неравенство.

DOI: 10.17377/daio.2017.24.563

Симанчёв Руслан Юрьевич ^1,2
1. Омский научный центр СО РАН,
пр. Карла Маркса, 15, 644024 Омск, Россия
2. Омский гос. университет им. Ф. М. Достоевского,
пр. Мира, 55А, 644077 Омск, Россия
е-mail: osiman@rambler.ru

Статья поступила 18 января 2017 г.
Исправленный вариант — 12 мая 2017 г.

Литература

[1] Агеев А. А., Ильев В. П., Кононов А. В., Талевнин А. С. Вычислительная сложность задачи аппроксимации графа // Дискрет. анализ и исслед. операций. 2006. Т. 13, № 1. С. 3–15.

[2] Бастраков С. И., Золотых Н. Ю. Быстрый способ проверки правила Черникова в методе исключения Фурье — Моцкина // Журн. вычисл. математики и мат. физики. 2015. Т. 55, № 1. С. 165–172.

[3] Емеличев В. А., Ковалёв М. М., Кравцов М. К. Многогранники. Графы. Оптимизация. М.: Наука, 1981.

[4] Ильев В. П., Ильева С. Д., Навроцкая А. А. Приближённые алгоритмы для задач аппроксимации графов // Дискрет. анализ и исслед. операций. 2011. Т. 18, № 1. С. 41–60.

[5] Симанчёв Р. Ю. О ранговых неравенствах, порождающих фасеты многогранника связных $k$-факторов // Дискрет. анализ и исслед. операций. 1996. Т. 3, № 3. С. 84–110.

[6] Симанчёв Р. Ю., Уразова И. В. Целочисленная модель задачи минимизации общего времени обслуживания параллельными приборами единичных требований с предшествованиями // Автоматика и телемеханика. 2010. № 10. С. 100–106.

[7] Симанчёв Р. Ю., Уразова И. В. О гранях многогранника задачи аппроксимации графа // Дискрет. анализ и исслед. операций. 2015. Т. 22, № 2. C. 86–101.

[8] Шевченко В. Н. Качественные вопросы целочисленного программирования. М.: Физматлит, 1995.

[9] Crowder H., Johnson E. L., Padberg M.W. Solving large-scale zero-one linear programming problems // Oper. Res. 1983. Vol. 31, No. 5. P. 803–834.

[10] Gottlieb E. S., Rao M. R. The generalized assignment problem: Valid inequalities and facets // Math. Program. 1990. Vol. 46, No. 1–3. P. 31–52.

[11] Grötschel M., Holland O. Solution of large-scale symmetric traveling salesman problems // Math. Program. 1991. Vol. 51, No. 1–3. P. 141–202.

[12] Grötschel M., Pulleyblank W. R. Clique tree inequalities and the symmetric traveling salesman problem // Math. Oper. Res. 1986. Vol. 11, No. 4. P. 537–569.

[13] Korte B., Vygen J. Combinatorial optimization: Theory and algorithms. Heidelberg: Springer, 2006.

[14] Krivánek M., Morávek J. NP-hard problems in hierarchical-tree clustering // Acta Inf. 1986. V. 23, No. 3. P. 311–323.

[15] Padberg M. W. (1, $k$)-Configurations and facets for packing problems // Math. Program. 1980. Vol. 18.
P. 94–99.

[16] Padberg M. W., Rinaldi G. Facet identification for the symmetric traveling salesman polytope // Math. Program. 1990. Vol. 47. P. 219–257.

[17] Padberg M. W., Rinaldi G. A branch and cut algorithm for the resolution of large-scale symmetric traveling salesman problems // SIAM Rev. 1991. Vol. 33. P. 60–100.

[18] Schrijver A. Combinatorial optimization. Polyhedra and efficiency. Heidelberg: Springer, 2004. (Algorithms Comb.; Vol. 24).

[19] Simanchev R. Yu., Urazova I. V. On the facets of combinatorial polytopes // Discrete Optimization and Operations Research. Proc. 9th Int. Conf. (Vladivostok, Russia, Sept. 19–23, 2016). P. 233–243. Cham: Springer, 2016. (Lect. Notes Comput. Sci.; Vol. 9869).

[20] Wolsey L. A. Valid inequalities for 0-1 knapsacks and MIPs with generalised upper bound constraints // Discrete App. Math. 1990. Vol. 29, No. 2–3. P. 251–261.