Integer programming formulations and benders decomposition for maximum induced matching problem

Abstract

In this thesis, we investigate Maximum Induced Matching problem (MIM), nding an induced matching having the largest cardinality. The problem is NP-hard for general graphs. We develop a binary integer programming formulation with less decision variables compared to other formulations in the literature. Then, we extend the problem for vertex-weighted graphs and introduce Maximum Vertex-Weighted Induced Matching problem (MVWIM). We introduce edge-weighted version of MIM and call it Maximum Edge-Weighted Induced Matching problem (MEWIM). We adapt formulations found in the literature and our formulation to solve MVWIM and MEWIM instances. In generalized version of Maximum Weighted Induced Matching problem (MWIM), we assume both vertices and edges have weights, and give a binary integer programming formulation for it. Since it has many decision variables and constraints, we implement Benders decomposition approach to partition the problem into smaller problems. Then, we add some valid inequalities to our formulation to improve the e ciency of our algorithm. To test the performance of our methodology, we generate random graphs with di erent densities. By looking at computational results, it can be seen that our approach solves instances with medium and large densities signi cantly faster than other methods in the literature.