A simplex-based tabu search method for capacitated network design

The fixed charge capacitated multicommodity network design problem is a wel l-known problem, of both practical and theoretical significance. This paper presents an efficient procedure to determine tight upper bounds on the opt imal solution of realistically sized problem instances. Feasible solutions are obtained by using a tabu search framework that explores the space of th e continuous flow variables by combining pivot moves with column generation , while evaluating the actual mixed integer objective. Computational experi ments on a large set of randomly generated test problems show that this pro cedure outperforms the other available methods and is particularly suited t o large problem instances with many commodities.