Integer Programming Formulations and Benders Decomposition for Maximum Induced Matching Problem

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, which is more compact compared to edge-based formulations in the literature. We also introduce vertex- and edge-weighted versions of MIM. We formulate the weighted problem as a quadratic integer programming problem based on our vertex-based formulation. We then linearize our quadratic programming formulation, and propose a decomposition algorithm that exploits a special structure of the linearized formulation. Our computational experiments show that our decomposition approach significantly improves solvability of the problem, especially on dense graphs.

Bio:

Dr. Z. Caner Taşkın is a professor in the Department of Industrial Engineering at Boğaziçi University. He received his B.S. and M.S. degrees in industrial engineering from Boğaziçi University in 2003 and 2005, respectively, and his Ph.D. degree in Industrial and Systems Engineering from the University of Florida in 2009. He has been named the recipient of the 2010 Pritsker Doctoral Dissertation Award given by the Institute of Industrial and Systems Engineers (IISE). His research is mainly focused on integer programming and hybrid decomposition algorithms with applications in medicine, telecommunications, graph theory and large-scale planning/scheduling. Dr. Taşkın is also involved in the design and development of ICRON Advanced Planning and Scheduling (APS) software. His work on real-world industrial applications has been selected as a finalist for EURO Excellence in Practice Award in 2015.