Minimum Cost b-Matching Problems with Nonconvex Neighborhoods

Resumen

Matching problems are among the most well studied problems in combinatorial optimization. Many applications of the matching problemscan be formulated as optimization problems defined on networks. In many real world applications, the exact location of the nodes is unknown and the assumption of modelling the nodes by points should be revised. In this sense, we propose to consider uncertainty regions or neighborhoods in which we are assured the points will lie. In this talk, we deal with minimum cost b-matching problems on graphs where nodes are represented by non-necessarily convex neighborhoods and the costs represent distances between neighborhoods. The goal is twofold. On the one hand, find a b-matching in the graph and on the second hand, a point should be identified in each neighborhood to be connection point among the edges determining the b-matching. In addition, these points should verify that the sum of the length (cost) of the edges defining the b-matching is minimized. Different variants of the minimum cost b-matching problem are considered depending on the criteria of matching: perfect matching problem, maximum cardinality matching problem, maximal matching problem and the a-b matching problem. The theoretical complexities of solving each one of these problems are analyzed. Different mixed integer non linear programming formulations are proposed for each of the considered problems and then reformulated as SOC formulations. An extensive computational experience shows the efficiency of the formulations to solve the proposed problems.