  A connected matching in a graph G consists of a set of pairwise disjoint
edges whose covered vertices induce a connected subgraph of G. While finding a
connected matching of maximum cardinality is a well-solved problem, it is
NP-hard to determine an optimal connected matching in an edge-weighted graph,
even in the planar bipartite case. We present two mixed integer programming
formulations and a sophisticated branch-and-cut scheme to find weighted
connected matchings in general graphs. The formulations explore different
polyhedra associated to this problem, including strong valid inequalities both
from the matching polytope and from the connected subgraph polytope. We
conjecture that one attains a tight approximation of the convex hull of
connected matchings using our strongest formulation, and report encouraging
computational results over DIMACS Implementation Challenge benchmark instances.
The source code of the complete implementation is also made available.
