Can a generic ILP solver find graph matchings as fast as a specialized algorithm?

Question

Finding a maximum matching, or a maximum-weight matching, is a well-known problem, which has polynomial-time combinatorial algorithms. It can also be formulated as an integer linear program. In general, an integer linear program might require exponential time. However, the particular ILP corresponding to a maximum matching problem can be solved in polynomial time.

My question is: are there generic ILP solvers that can identify this special structure, and solve matching-related ILPs as fast as solvers that are specially written for matching (e.g. the ones in the Python networkx library)?

The motivation for this question is that having a general ILP formulation allows us to easily add problem-specific constraints and modifications. For example, it is easy to solve one-to-many matching, or add other kinds of constraints, that are less easy to do with a specialized graph-matching solver. So the question is: how much do we "pay" for the added generality, in terms of run-time?

Answer 1

This is where decomposition algorithms (specifically Dantzig-Wolfe can be quite useful).

My thesis work and subsequent OSS in COIN provides APIs to do this kind of thing: https://projects.coin-or.org/Dip

The basic idea is that the oracle is the graph implementation while the side constraints are modeled as the master constraints in the decomposition reformulation.

Answer 2

In general ILP solvers are not as efficient in solving the Maximum Matching problem. A comparison of efficient matching algorithm implementations, as well as an ILP formulation for the Maximum Cardinality Matching Problem and the Minimum Weight perfect matching problem can be found in Figures 5 and 6 of this paper:

Dimitrios Michail, Joris Kinable, Barak Naveh, and John V. Sichi. 2020. JGraphT—A Java Library for Graph Data Structures and Algorithms. ACM Trans. Math. Softw. 46, 2, Article 16 (June 2020). DOI:https://doi.org/10.1145/3381449

The ILP model is one or two orders of magnitude slower than the dedicated algorithmic implementations.

Implementing Matching algorithms for general graphs is actually hard and very labor intensive (that's why only a few graph libraries have implementations for these problems). Modifying an existing implementation to include a side constraint could be even harder. My recommendation is to use a dedicated implementation when possible, and to try an ILP formulation if you need side constraints. Implementing the ILP formulation is typically very easy for matchings and the ILP's performance is often adequate for most applications.