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.

+More

constraints nested boolean quadric polytope relaxations metric polytope fractional faces cutting threedimensional block relaxation triangle inequalities sequence mnk of integrality recognition problem rooted semimetric polytope

V. A. Bondarenko,A. V. Nikolaev,.Some Properties of Metric Polytope Constraints. 21 (4),.

V. A. Bondarenko,A. V. Nikolaev,"Some Properties of Metric Polytope Constraints" 21

V. A. Bondarenko,A. V. Nikolaev,"Some Properties of Metric Polytope Constraints"