Acoplamientos óptimos de caminos de longitud dos

Abstract

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 Euclidean 3-matching problem consists on finding a minimum cost 3-matching of P under the Euclidean metric. In the usual formulation of the Euclidean 3- matching problem we need to find a minimum cost 3-matching of P. This problem has several applications, especially in the insertion of components on a printed circuit board. Johnsson, Magyar, and Nevalainen introduced two integer programming formulations for this problem, and proved that its decision version is NP-complete if each triplet has an arbitrary positive cost (i.e., not necessarily Euclidean). The problem remains NP-complete even if the points of P correspond to vertices of a unit distance graph (a metric cost function). In this work, we prove that the linear programming relaxations of these two models are equivalent. Then we introduce three new integer programming models that use fewer variables than those from Johnsson, Magyar, and Nevalainen. We also compare the linear programming relaxations of the models. Besides the minimization problem, we are also interested in a similar maximization problem: finding a maximum cost non-crossing Euclidean 3-matching of P, where noncrossing means that no two segments intersect in a common interior point. Both problems, minimum cost and maximum cost non-crossing, are challenging, and we believe that both are NP-hard. Exact solutions to both problems can be attained through integer programming; however, in order to obtain good solutions in feasible times, we fix our attention to heuristics. We present three heuristics specially designed for our problems and compare their solutions and execution times against solving the exact models.