Article ID: | iaor1999359 |
Country: | United Kingdom |
Volume: | 25 |
Issue: | 1 |
Start Page Number: | 67 |
End Page Number: | 81 |
Publication Date: | Jan 1998 |
Journal: | Computers and Operations Research |
Authors: | Mateus G.R., Smith J. MacGregor, Cruz F.R.B. |
Keywords: | programming: branch and bound |
We present the uncapacitated fixed-charge network flow problem and two mathematical programming formulations. We use an exact approach to solve the problem, the well-known branch-and-bound algorithm. We derive bounds for the algorithm using Lagrangean Relaxation and also propose an efficient branching strategy which is based on an important property of the optimal solution. We also use a Lagrangean Relaxation of the problem to develop a new reduction test. The practical efficiency of all the procedures is demonstrated through a comprehensive set of computational experiments.