Integer Programming Models and Heuristics for Non-crossing Euclidean 3-Matchings

摘要

Given a set P of 3k points in general position in the plane, a Euclidean 3-matching is a partition of P into k triplets, such that the cost of each triplet («, v, w) is the sum of the lengths of the segments uv and wv, and the cost of the 3-matching is the sum of the costs of its triplets. We are interested in finding non-crossing Euclidean 3-matchings of minimum and maximum cost. As these are hard combinatorial problems, we present and evaluate three integer programming models and three heuristics for them.