Some Properties of Metric Polytope Constraints
https://doi.org/10.18255/1818-1015-2014-4-25-34
Abstract
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.
About the Authors
V. A. Bondarenko
P.G. Demidov Yaroslavl State University
Russian Federation
доктор физ.-мат. наук, профессор, зав. кафедрой дискретного анализа, Sovetskaya str., 14, Yaroslavl, 150000, Russia
Russian Federation
доктор физ.-мат. наук, профессор, зав. кафедрой дискретного анализа, Sovetskaya str., 14, Yaroslavl, 150000, Russia
A. V. Nikolaev
P.G. Demidov Yaroslavl State University
Russian Federation
кандидат физ.-мат. наук, доцент кафедры дискретного анализа, Sovetskaya str., 14, Yaroslavl, 150000, Russia
Russian Federation
кандидат физ.-мат. наук, доцент кафедры дискретного анализа, Sovetskaya str., 14, Yaroslavl, 150000, Russia
References
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.
Review
For citations:
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
Views:
870
Email this article 