A Branch-and-Cut Algorithm for the Undirected Traveling Purchaser Problem
- 1 December 2003
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 51 (6) , 940-951
Abstract
The purpose of this paper 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 defining. A branch-and-cut procedure is developed and tested over four classes of randomly generated instances. Results show that the proposed algorithm outperforms all previous approaches and can optimally solve instances containing up to 200 markets.Keywords
This publication has 14 references indexed in Scilit:
- Introduction to ABACUS – a branch-and-cut systemOperations Research Letters, 1998
- A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman ProblemOperations Research, 1997
- The Circuit Polytope: FacetsMathematics of Operations Research, 1997
- The symmetric generalized traveling salesman polytopeNetworks, 1995
- On the set covering polytope: I. All the facets with coefficients in {0, 1, 2}Mathematical Programming, 1989
- Solving Large-Scale Zero-One Linear Programming ProblemsOperations Research, 1983
- Two generalizations of the traveling salesman problemOmega, 1981
- Sequencing many jobs on a multi-purpose facilityNaval Research Logistics Quarterly, 1971
- A Heuristic Method for a Job-Scheduling ProblemJournal of the Operational Research Society, 1966
- A Heuristic Approach to Solving Travelling Salesman ProblemsManagement Science, 1964