ISyE Seminar Series: Joseph Paat

"On Delta-Modular Matrices and Integer Programs"

Joseph Paat

Associate Professor in the Operations and Logistics Division of the Sauder School of Business
University of British Columbia

About the Seminar:

Integer linear programs (IPs) are NP-hard to solve, in general. However, certain classes of IPs can be solved efficiently, e.g., those defined by totally unimodular (TU) matrices. In this talk, we discuss IPs whose constraint matrices are `Delta-modular’, which is a notion that generalizes TU. It remains an open question whether Delta-modular IPs can be solved efficiently. Motivated by this, we study structural properties of constraint matrices and IPs in this Delta-modular regime. Among these properties, we consider questions like distance to the LP relaxation and the so-called column number. Throughout the talk, we list open questions in this line of work.

Related Paper:

• The Column Number for 3-modular Matrices 
• On the Column Number and Forbidden Submatrices for Δ-modular Matrices
• Proximity and Flatness Bounds for Linear Integer Optimization

About the Speaker:

Joe earned a PhD in Applied Mathematics and Statistics from Johns Hopkins University in 2017. After that, he was a postdoc at the Institute for Operations Research at ETH Zürich. Since 2020, he has been a faculty in the Operations and Logistics Division of the Sauder School of Business at the University of British Columbia. Joe’s primary research interest is in the theory of mixed integer optimization.

If you wish to be added to the ISyE Graduate Seminar Series emailing list, please email Event Coordinator Emily Rice at [email protected].