Abstract:
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.