EN|RU
Свободный доступ к полным текстам предоставляется после 1 июля года, следующего за годом публикации. Полный текст этой статьи можно приобрести на сайте elibrary.ru.

Том 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.

 © Институт математики им. С. Л. Соболева, 2015