maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2014-4-25-34mais-95Research ArticleОригинальные статьиArticlesО нецелочисленных гранях метрического многогранникаSome Properties of Metric Polytope ConstraintsБондаренкоВладимир АлександровичBondarenkoV. A.

доктор физ.-мат. наук, профессор, зав. кафедрой дискретного анализа, 150000 Россия, г. Ярославль, ул. Советская, 14

доктор физ.-мат. наук, профессор, зав. кафедрой дискретного анализа, Sovetskaya str., 14, Yaroslavl, 150000, Russia

bond@bond.edu.yar.ruНиколаевАндрей ВалерьевичNikolaevA. V.

кандидат физ.-мат. наук, доцент кафедры дискретного анализа, 150000 Россия, г. Ярославль, ул. Советская, 14

кандидат физ.-мат. наук, доцент кафедры дискретного анализа, Sovetskaya str., 14, Yaroslavl, 150000, Russia

werdan.nik@gmail.comЯрославский государственный университет им. П.Г. ДемидоваРоссияP.G. Demidov Yaroslavl State UniversityRussian Federation2014200820142142534Copyright © Бондаренко В.А., Николаев А.В., 20142014Бондаренко В.А., Николаев А.В.Bondarenko V.A., Nikolaev A.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/95

На последовательности Mn,k вложенных релаксаций булева квадратичного многогранника, включающей корневой полуметрический Mn и метрический Mn,3 многогранники, рассматривается задача распознавания целочисленности. Ограничения метрического многогранника отсекают все грани корневого полуметрического многогранника, содержащие только нецелочисленные вершины, что позволяет решить задачу распознавания целочисленности на Mn за полиномиальное время. Для решения задачи распознавания целочисленности на метрическом многограннике исследуется возможность отсечения всех нецелочисленных граней Mn,3 некоторой релаксацией Mn,k. Координаты точек метрического многогранника представляются в однородном виде в форме трехмерной блочной матрицы. Показывается, что при исследовании вопроса отсечения нецелочисленных граней метрического многогранника достаточно учитывать только ограничения вида неравенств треугольника.  

The integrality recognition problem is considered on the sequence Mn,k of the nested Boolean quadric polytope relaxations, including the rooted semimetric Mn and the metric Mn,3 polytopes. Constraints of the metric polytope cut off all faces of the rooted semimetric polytope, containing only fractional vertices, that allows to solve the problem of integrality recognition on Mn in polynomial time. To solve the problem of integrality recognition on the metric polytope, we consider the possibility of cutting off all fractional faces of Mn,3 by some relaxation Mn,k. We represent the coordinates of the metric polytope in a homogeneous form by a three-dimensional block matrix. We show that to answer the question of the metric polytope fractional faces cutting off, it is sufficient to consider only constraints of the triangle inequalities form.

распознавание целочисленностикорневой полуметрический многогранникметрический многогранникрелаксационный многогранникintegrality recognitionrooted semimetric polytopemetric polytoperelaxation polytopeРФФИReferencesPadberg M. V. The Boolean quadratic polytope: some characteristics, facets and relatives // Mathematical Program. 1989. V. 45. P. 139–172.Padberg M. V. The Boolean quadratic polytope: some characteristics, facets and relatives // Mathematical Program. 1989. V. 45. P. 139–172.Бондаренко В. А., Урываев Б. В. Об одной задаче целочисленной оптимизации // АиТ. 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.)Бондаренко В. А., Урываев Б. В. Об одной задаче целочисленной оптимизации // АиТ. 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.)Бондаренко В. А., Максименко А. Н. Геометрические конструкции и сложность в комбинаторной оптимизации. М.: ЛКИ, 2008. 184 с. [Bondarenko V. A., Maksimenko A. N. Geometricheskie konstruktsii i slozhnost v kombinatornoy optimizatsii. Moscow: LKI, 2008 (in Russian)].Бондаренко В. А., Максименко А. Н. Геометрические конструкции и сложность в комбинаторной оптимизации. М.: ЛКИ, 2008. 184 с. [Bondarenko V. A., Maksimenko A. N. Geometricheskie konstruktsii i slozhnost v kombinatornoy optimizatsii. Moscow: LKI, 2008 (in Russian)].Бондаренко В. А., Николаев А. В. Об одном классе гиперграфов и о вершинах релаксаций разрезного многогранника // Докл. РАН. 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.)Бондаренко В. А., Николаев А. В. Об одном классе гиперграфов и о вершинах релаксаций разрезного многогранника // Докл. РАН. 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.)Christof T., Reinelt G. Efficient parallel facet enumeration for 0/1-polytopes. Technical report. Institut fur Angewandte Mathematik. Universitat Heidelberg. 1997.Christof T., Reinelt G. Efficient parallel facet enumeration for 0/1-polytopes. Technical report. Institut fur Angewandte Mathematik. Universitat Heidelberg. 1997.Deza M. M., Laurent M. Geometry of Cuts and Metrics (Algorithms and Combinatorics). 2nd ed. Springer, 2009.Deza M. M., Laurent M. Geometry of Cuts and Metrics (Algorithms and Combinatorics). 2nd ed. Springer, 2009.Бондаренко В. А., Николаев А. В. О подобии разных релаксаций разрезного многогранника // Научные исследования факультета информатики и вычислительной техники: Сборник статей к 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)].Бондаренко В. А., Николаев А. В. О подобии разных релаксаций разрезного многогранника // Научные исследования факультета информатики и вычислительной техники: Сборник статей к 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)].Николаев А.В. Гиперграфы специального вида и анализ свойств релаксаций разрезного многогранника // Моделирование и анализ информационных систем. 2011. Т. 18. № 3. С. 82–100.Николаев А.В. Гиперграфы специального вида и анализ свойств релаксаций разрезного многогранника // Моделирование и анализ информационных систем. 2011. Т. 18. № 3. С. 82–100.[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)].[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)].Бондаренко В. А., Николаев А. В. Некоторые свойства релаксаций разрезного многогранника // Ярославский педагогический вестник. 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)].Бондаренко В. А., Николаев А. В. Некоторые свойства релаксаций разрезного многогранника // Ярославский педагогический вестник. 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)].Laurent M. Graphic vertices of the metric polytope // Discrete Mathematics. 1996. Vol. 151. Iss. 1–3. P. 131—153.Laurent M. Graphic vertices of the metric polytope // Discrete Mathematics. 1996. Vol. 151. Iss. 1–3. P. 131—153.

The authors declare that there are no conflicts of interest present.