Capacity improvement, penalties, and the fixed charge transportation problem

Capacity improvement, penalties, and the fixed charge transportation problem

0.00 Avg rating0 Votes
Article ID: iaor2000531
Country: United States
Volume: 46
Issue: 4
Start Page Number: 341
End Page Number: 355
Publication Date: Jun 1999
Journal: Naval Research Logistics
Authors: , ,
Keywords: programming: multiple criteria, facilities
Abstract:

Capacity improvement and conditional penalties are two computational aids for fathoming subproblems in a branch-and-bound procedure. In this paper, we apply these techniques to the fixed charge transportation problem (FCTP) and show how relaxations of the FCTP subproblems can be posed as concave minimization problems (rather than LP relaxations). Using the concave relaxations, we propose a new conditional penalty and three new types of capacity improvement techniques for the FCTP. Based on computational experiments using a standard set of FCTP test problems, the new capacity improvement and penalty techniques are responsible for a three-fold reduction in the CPU time for the branch-and-bound algorithm and nearly a tenfold reduction in the number of subproblems that need to be evaluated in the branch-and-bound enumeration tree.

Reviews

Required fields are marked *. Your email address will not be published.