Revisiting Mixed-Integer Programming Formulations for the Stable Set Problem

Time: 2.00pm-4.00pm (Beijing Time), May 28th
Venue: MB537
Speaker: Prof. Abraham P. Punnen (Simon Fraser University)
Inviter: Dr. Min Wen

Title: Revisiting Mixed-Integer Programming Formulations for the Stable Set Problem

Abstract:
The Maximum Weight Stable Set Problem (MWSP) is one of the classic problems in combinatorial optimization, with a rich history and many elegant formulations. In this talk, I will revisit the problem from a fresh modeling perspective and describe a unified framework for constructing compact mixed-integer linear programming (MILP) formulations based on structured neighborhood aggregation and weighted combinations of constraints.
Rather than focusing solely on formulation size, I will emphasize the structural ideas behind these models and how they influence the strength of the resulting relaxations and their computational behavior. I will also share insights from a systematic set of computational experiments that compare these formulations in practice.

Bio:
Abraham P. Punnen is a Professor in the Department of Mathematics at Simon Fraser University, Canada. He received his Ph.D. in Operations Research and has held academic appointments in several countries, contributing significantly to research and graduate education in combinatorial optimization.
Professor Punnen’s research interests lie in discrete and combinatorial optimization, with particular emphasis on network optimization, location theory, and fundamental optimization problems such as the quadratic assignment problem, the travelling salesman problem, and the maximum weight stable set problem. His work has led to important theoretical advances as well as algorithmic developments with broad applicability.
He has published extensively in leading international journals and is a co-author of influential research monographs. He is also the co-editor (with Gregory Gutin) of the well-known volume The Traveling Salesman Problem and Its Variations, and the editor of the recent volume The Quadratic Unconstrained Binary Optimization Problem (2022), both of which are widely regarded as important references in the field.
In addition, he has served on the editorial boards of several prominent journals and has played an active role in the organization of international conferences and scholarly activities in operations research and optimization.