A triplet integer programming model for the Euclidean 3-matching problem
Gualberto Vazquez Casas, Rodrigo Alexander Castro Campos, Marco A. Heredia, Francisco Javier Zaragoza Martínez · 2015
Let P be a set of 3k points in the Euclidean plane. A 3-matching is a partition of P into k subsets of 3 points each, called triplets. The cost of each triplet {a, b, c} is given by min{|ab| + |bc|, |bc| + |ca|, |ca| + |ab|}, and the cost of the 3-matching is the sum of the costs of its triplets. The problem of finding a minimum cost Euclidean 3-matching is known to be NP-hard. Two integer programming formulations for this problem were introduced by Johnsson, Magyar, and Nevalainen. First, we prove that the linear programming relaxations of these two models are equivalent. Second, we introduce a new triplet integer programming model. Third, we compare the linear programming relaxations of these three models.