Geodesic
Some Properties of Metric Polytope Constraints
Modelirovanie i analiz informacionnyh sistem, Tome 21 (2014) no. 4, pp. 25-34.

Voir la notice de l'article provenant de la source Math-Net.Ru

The integrality recognition problem is considered on the sequence $M_{n, k}$ of the nested Boolean quadric polytope relaxations, including the rooted semimetric $M_{n}$ and the metric $M_{n,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 $M_{n}$ 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 $M_{n, 3}$ by some relaxation $M_{n,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.
Keywords: integrality recognition, rooted semimetric polytope, metric polytope, relaxation polytope. 
@article{MAIS_2014_21_4_a2,
     author = {V. A. Bondarenko and A. V. Nikolaev},
     title = {Some {Properties} of {Metric} {Polytope} {Constraints}},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {25--34},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2014_21_4_a2/}
}
TY  - JOUR
AU  - V. A. Bondarenko
AU  - A. V. Nikolaev
TI  - Some Properties of Metric Polytope Constraints
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2014
SP  - 25
EP  - 34
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2014_21_4_a2/
LA  - ru
ID  - MAIS_2014_21_4_a2
ER  - 
%0 Journal Article
%A V. A. Bondarenko
%A A. V. Nikolaev
%T Some Properties of Metric Polytope Constraints
%J Modelirovanie i analiz informacionnyh sistem
%D 2014
%P 25-34
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2014_21_4_a2/
%G ru
%F MAIS_2014_21_4_a2
V. A. Bondarenko; A. V. Nikolaev. Some Properties of Metric Polytope Constraints. Modelirovanie i analiz informacionnyh sistem, Tome 21 (2014) no. 4, pp. 25-34. http://geodesic.mathdoc.fr/item/MAIS_2014_21_4_a2/

[1] M. V. Padberg, “The Boolean quadratic polytope: some characteristics, facets and relatives”, Mathematical Program, 45 (1989), 139–172 | DOI | MR | Zbl

[2] V. A. Bondarenko, B. V. Uryvaev, “On One Problem of Integer Optimization”, Autom. Remote Control, 68:6 (2007), 948–953 | DOI | MR | Zbl

[3] Bondarenko V. A., Maksimenko A. N., Geometricheskie konstruktsii i slozhnost v kombinatornoy optimizatsii, LKI, M., 2008 (in Russian)

[4] V. A. Bondarenko, A. V. Nikolaev, “A Class of Hypergraphs and Vertices of Cut Polytope Relaxations”, Doklady Mathematics, 85:1 (2012), 46–47 | DOI | MR | Zbl

[5] T. Christof, G. Reinelt, Efficient parallel facet enumeration for 0/1-polytopes, Technical report, Institut fur Angewandte Mathematik, Universitat Heidelberg, 1997

[6] M. M. Deza, M. Laurent, Geometry of Cuts and Metrics, Algorithms and Combinatorics, 2nd ed., Springer, 2009 | MR

[7] 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, 17–21 (in Russian)

[8] Nikolaev A. V., “Hypergraphs of Special Type and CUT Polytope Relaxations Properties Analysis”, Model. and Anal. Inform. Sist., 18:3 (2011), 82–100 (in Russian)

[9] Bondarenko V. A., Nikolaev A. V., “Some Properties of Cut Polytope Relaxations”, Yaroslavl Pedagogical Bulletin, 3:2 (2011), 23–29 (in Russian)

[10] M. Laurent, “Graphic vertices of the metric polytope”, Discrete Mathematics, 151:1-3 (1996), 131–153 | DOI | MR | Zbl