Some Properties of Metric Polytope Constraints

V. A. Bondarenko ; A. V. Nikolaev

Modelirovanie i analiz informacionnyh sistem, Tome 21 (2014) no. 4, pp. 25-34

Résumé

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.

Détail

Keywords: integrality recognition, rooted semimetric polytope, metric polytope, relaxation polytope.