Two-index formulations for the traveling purchaser problem with incompatibility constraints

In this article, 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.