Two-index formulations for the traveling purchaser problem with incompatibility constraints
研究了带物品不相容约束的旅行购买者问题，提出基于相容图的双指标混合整数线性规划模型，并设计分支切割算法求解，实验表明新模型比三指标模型线性规划松弛值更高，能求解更多基准实例。
• Two-index formulations for the traveling purchaser problem with incompatibilities. • Valid inequalities based on the incompatibilities between items. • Theoretical and empirical comparison between the proposed two-index formulations. • Branch-and-cut algorithm to solve the non-compact models. 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.