Speaker
Description
The Traveling Purchaser Problem with Incompatibility Constraints (TPP-IC) generalizes the classical Traveling Purchaser Problem (TPP) by introducing constraints that prevent certain items from being transported together. This problem arises in various real-world applications, such as hazardous materials transportation, where incompatible products must be handled separately to ensure safety and compliance.
In this study, we propose a novel mixed-integer programming (MIP) formulation that models item incompatibilities using compatibility graphs. Compatibility graphs are used to model the incompatibility constraints implicitly, which makes it possible to use two-index formulations rather than a traditional three-index formulation to formulate the TPP-IC. Several compact and non-compact formulations are proposed for the TPP-IC, which are compared both theoretically and empirically. Additionally, valid inequalities are used to improve the quality of the linear programming relaxation values obtained by the formulations. A branch-and-cut framework is used to address the non-compact models.
Preliminary computational results show that the two-index formulations provide better linear programming relaxation values than the three-index formulation, which we hope will contribute to the two-index models being more efficient than the three-index models in obtaining the optimal values.
