О нецелочисленных гранях метрического многогранника
https://doi.org/10.18255/1818-1015-2014-4-25-34
Аннотация
На последовательности Mn,k вложенных релаксаций булева квадратичного многогранника, включающей корневой полуметрический Mn и метрический Mn,3 многогранники, рассматривается задача распознавания целочисленности. Ограничения метрического многогранника отсекают все грани корневого полуметрического многогранника, содержащие только нецелочисленные вершины, что позволяет решить задачу распознавания целочисленности на Mn за полиномиальное время. Для решения задачи распознавания целочисленности на метрическом многограннике исследуется возможность отсечения всех нецелочисленных граней Mn,3 некоторой релаксацией Mn,k. Координаты точек метрического многогранника представляются в однородном виде в форме трехмерной блочной матрицы. Показывается, что при исследовании вопроса отсечения нецелочисленных граней метрического многогранника достаточно учитывать только ограничения вида неравенств треугольника.
Ключевые слова
распознавание целочисленности,
корневой полуметрический многогранник,
метрический многогранник,
релаксационный многогранник
При поддержке: РФФИ
Об авторах
Владимир Александрович Бондаренко
Ярославский государственный университет им. П.Г. Демидова
Россия
доктор физ.-мат. наук, профессор, зав. кафедрой дискретного анализа, 150000 Россия, г. Ярославль, ул. Советская, 14
Россия
доктор физ.-мат. наук, профессор, зав. кафедрой дискретного анализа, 150000 Россия, г. Ярославль, ул. Советская, 14
Андрей Валерьевич Николаев
Ярославский государственный университет им. П.Г. Демидова
Россия
кандидат физ.-мат. наук, доцент кафедры дискретного анализа, 150000 Россия, г. Ярославль, ул. Советская, 14
Россия
кандидат физ.-мат. наук, доцент кафедры дискретного анализа, 150000 Россия, г. Ярославль, ул. Советская, 14
Список литературы
1. Padberg M. V. The Boolean quadratic polytope: some characteristics, facets and relatives // Mathematical Program. 1989. V. 45. P. 139–172.
2. Бондаренко В. А., Урываев Б. В. Об одной задаче целочисленной оптимизации // АиТ. 2007. № 6. С. 18–23. (English transl.: Bondarenko V. A., Uryvaev B. V. On One Problem of Integer Optimization // Autom. Remote Control. 2007. V. 68. Iss. 6. P. 948–953.)
3. Бондаренко В. А., Максименко А. Н. Геометрические конструкции и сложность в комбинаторной оптимизации. М.: ЛКИ, 2008. 184 с. [Bondarenko V. A., Maksimenko A. N. Geometricheskie konstruktsii i slozhnost v kombinatornoy optimizatsii. Moscow: LKI, 2008 (in Russian)].
4. Бондаренко В. А., Николаев А. В. Об одном классе гиперграфов и о вершинах релаксаций разрезного многогранника // Докл. РАН. 2012. Т. 442. № 3. С. 300–302. (English transl.: Bondarenko V. A., Nikolaev A. V. A Class of Hypergraphs and Vertices of Cut Polytope Relaxations // Doklady Mathematics. 2012. V. 85. Iss. 1. P. 46–47.)
5. Christof T., Reinelt G. Efficient parallel facet enumeration for 0/1-polytopes. Technical report. Institut fur Angewandte Mathematik. Universitat Heidelberg. 1997.
6. Deza M. M., Laurent M. Geometry of Cuts and Metrics (Algorithms and Combinatorics). 2nd ed. Springer, 2009.
7. Бондаренко В. А., Николаев А. В. О подобии разных релаксаций разрезного многогранника // Научные исследования факультета информатики и вычислительной техники: Сборник статей к 25-летию факультета. Ярославль, 2011. С. 17–21. [Bondarenko V. A., Nikolaev A. V. O podobii raznykh relaksatsiy razreznogo mnogogrannika // Nauchnye issledovanija fakulteta informatiki i vychislitelnoj tehniki: Sbornik statej k 25-letiju fakulteta. Yaroslavl, 2011. S. 17–21 (in Russian)].
8. Николаев А.В. Гиперграфы специального вида и анализ свойств релаксаций разрезного многогранника // Моделирование и анализ информационных систем. 2011. Т. 18. № 3. С. 82–100.
9. [Nikolaev A. V. Hypergraphs of Special Type and CUT Polytope Relaxations Properties Analysis // Model. and Anal. Inform. Sist. 2011. Vol. 18. № 3. P. 82–100 (in Russian)].
10. Бондаренко В. А., Николаев А. В. Некоторые свойства релаксаций разрезного многогранника // Ярославский педагогический вестник. 2011. Т. 3 (Естественные науки). № 2. С. 23–29. [Bondarenko V. A., Nikolaev A. V. Some Properties of Cut Polytope Relaxations // Yaroslavl Pedagogical Bulletin. 2011. Vol. 3. № 2. P. 23–29 (in Russian)].
11. Laurent M. Graphic vertices of the metric polytope // Discrete Mathematics. 1996. Vol. 151. Iss. 1–3. P. 131—153.
Рецензия
Для цитирования:
Бондаренко В.А., Николаев А.В. О нецелочисленных гранях метрического многогранника. Моделирование и анализ информационных систем. 2014;21(4):25-34. https://doi.org/10.18255/1818-1015-2014-4-25-34
For citation:
Bondarenko V.A., Nikolaev A.V. Some Properties of Metric Polytope Constraints. Modeling and Analysis of Information Systems. 2014;21(4):25-34. (In Russ.) https://doi.org/10.18255/1818-1015-2014-4-25-34
Просмотров:
861
Послать статью по эл. почте 