Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem
研究了在无向图中寻找最大基数诱导匹配的问题，提出了更紧凑的顶点基整数规划公式，并针对带权版本设计了Benders分解算法，显著提升了稠密图上的求解效率。
We investigate the maximum induced matching problem (MIM), which is the problem of finding an induced matching having the largest cardinality on an undirected graph. The problem is known to be NP-hard for general graphs. We first propose a vertex-based integer programming formulation for MIM, which is more compact compared to an edge-based formulation found in the literature. We also introduce the maximum weight induced matching problem (MWIM), which generalizes MIM so that vertices and edges have weights. We adapt the edge-based formulation to MWIM, and propose a quadratic programming formulation of MWIM based on our vertex-based formulation. We then linearize our quadratic programming formulation, and devise a Benders decomposition algorithm that exploits a special structure of the linearized formulation. We also propose valid inequalities and formulation tightening procedures to improve the efficiency of our approach. Our computational tests on a large suite of randomly generated graphs show that our vertex-based formulation and decomposition approach significantly improve the solvability of MIM and MWIM, especially on dense graphs. The online appendix and data are available at https://doi.org/10.1287/ijoc.2017.0764 .