[NOVA Math] Seminar of Operations Research

The Center of Mathematics and Applications (NOVA Math), promote the Seminar of Operations Research with the title: “Two-index formulations for the traveling purchaser problem with incompatibility constraints”. Daniel Santos (CEGIST, Engineering and Management Department – IST) is the speaker.

Abstract: In this work, we study the Traveling Purchaser Problem with Incompatibility Constraints (TPP-IC), an NP-hard combinatorial optimization problem that extends the classical Traveling Purchaser Problem (TPP) by introducing incompatibilities between items. These prohibit incompatible items from being transported on the same route. We model the TPP-IC using structures called compatibility graphs, which ensure, by construction, that any feasible route does not transport incompatible items. To address the problem, we propose several two-index mixed-integer linear programming (MILP) formulations, including both item-based and market-based approaches. We present a theoretical and computational comparison of these models. In addition, we introduce a family of valid inequalities that exploit the incompatibility constraints. These inequalities strengthen the formulations and are incorporated into a branch-and-cut algorithm. Our computational experiments show that the two-index formulations based on the compatibility graphs yield significantly higher linear programming relaxation values compared to the three-index formulations in the literature. They also solve more benchmark instances. Our results also highlight the main factors that contribute to the difficulty of solving TPP-IC instances and reveal the limitations of exact solution methods in instances with a high degree of item incompatibility.

Short bio: Daniel Santos is an Assistant Professor at the Engineering and Management Department of Instituto Superior Técnico and the current Vice President of CEGIST. He concluded his PhD in Optimization from Faculdade de Ciências da Universidade de Lisboa in April 2019, with a thesis titled "Models for multi-depot routing problems". Daniel's primary research areas are routing and health care, with a focus on developing models, algorithms and tools to support decision-making. He is a co-author of over 15 articles in indexed international peer-reviewed journals, and frequently collaborates with national and international researchers. Daniel currently supervises(d) 7 PhD students in health care applications and combinatorial optimization, on topics such as home hospitalization, emergency medical services, blood supply chain, operating room planning and scheduling, university timetabling, and districting and routing, and has supervised over 60 MSc students. He is the Principal Investigator of the FCT-funded projects "LAIfeBlood+ - Data Science for Blood Management" and "SUPPORT-HH: Decision support tools for Home Hospitalization management".

February 11| 14h30 | Room 4.17 - Building IX