|
Abstract : |
The purpose of this article is to present a branch-and-cut algorithm for the undirected Traveling Purchaser Problem which consists of determining a minimum-cost route through a subset of markets, where the cost is the sum of travel and purchase costs. The problem is formulated as an integer linear program and several families of valid inequalities are derived to strengthen the linear relaxation. The polyhedral structure of the formulation is analyzed and several classes of valid inequalities are proved to be facet-dening. A branch-and-cut procedure is developed and tested over several classes of randomly generated instances. Results show that the proposed algorithm outperform all previous approaches and can solve optimally instances containing up to 200 markets., |
