IE-OPIM Joint Graduate Seminar
  • FENS
  • IE-OPIM Joint Graduate Seminar

You are here


IE-OPIM Joint Graduate Seminar: Caner Taşkın (Boğaziçi University)

 Integer Programming Formulations and Decomposition Algorithms for Maximum Induced Matching Problem

Date: Wednesday, April 6, 2016
Time: 13:40 – 14:30
Location: FENS G032

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, 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 an associate 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 Engineers (IIE). His research is mainly focused on integer programming and hybrid decomposition algorithms with applications in medicine, telecommunications, 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 received the best IE/OR Application Award at YA/EM 2012 and has been selected as a finalist for EURO Excellence in Practice Award in 2015.