Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem

Betül Ahat (), T?naz Ekim () and Z. Caner Taşkın ()
Additional contact information
Betül Ahat: Department of Industrial Engineering, Boğaziçi University, Istanbul 34342, Turkey
T?naz Ekim: Department of Industrial Engineering, Boğaziçi University, Istanbul 34342, Turkey
Z. Caner Taşkın: Department of Industrial Engineering, Boğaziçi University, Istanbul 34342, Turkey

INFORMS Journal on Computing, 2018, vol. 30, issue 1, 43-56

Abstract: 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.

Keywords: integer programming; Benders decomposition; maximum induced matching; distance-2 matching; strong matching (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2017.0764 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:30:y:2018:i:1:p:43-56

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().