Optimization Online


On the effectiveness of primal and dual heuristics for the transportation problem

Jonas Schwinn(jonas.schwinn***at***math.uni-augsburg.de)
Ralf Werner(ralf.werner***at***math.uni-augsburg.de)

Abstract: The transportation problem is one of the most popular problems in linear programming. Over the course of time a multitude of exact solution methods and heuristics have been proposed. Due to substantial progress of exact solvers since the mid of the last century, the interest in heuristics for the transportation problem over the last few decades has been reduced to their potential as starting methods for exact algorithms. In the context of ever increasing problem dimensions, this paper contributes an in-depth study of heuristics with respect to their performance in terms of computation time and objective value. Furthermore, we consider to the best of our knowledge for the first time some simple efficient dual heuristics to obtain performance certificates based on weak duality without the need to solve the problem exactly. We test these heuristics in conjunction with state-of-the-art solvers on a variety of test problems. Thus we especially close the gap to almost outdated comparative studies from the last century, as for example Srinivasan & Thompson (1973); Glover et al. (1974); Gass (1990). For one class of random test problems, we extend previous approaches to provide a consistent and flexible problem generator with known solution. Based on our numerical results, it can be concluded that primal and dual heuristics are able to rapidly generate good approximations for specific randomly generated problem instances but as expected are not able to yield satisfactory performance in most cases.

Keywords: transportation problem; primal heuristic; dual heuristic; problem generator for transportation problems

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Optimization Software and Modeling Systems (Optimization Software Benchmark )

Citation: Working Paper, Augsburg University, 08/2017

Download: [PDF]

Entry Submitted: 08/31/2017
Entry Accepted: 08/31/2017
Entry Last Modified: 08/31/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society