A computational study of using preprocessing and stronger formulations to solve large general fixed charge problems. (English) Zbl 0681.90061
Summary: The application of traditional branch-and-bound (B&B) procedures to the standard formulation of the general fixed charge problem (GFCP) has not proven to be an acceptable approach to solving this well-known problem. It has been suggested by various authors that preprocessing the data and/or adding constraints to the GFCP might lead to improved B&B performance. In this paper, we present extensive computational results to test these hypotheses using the MPSX/MIP/370 package. The results demonstrate that while preprocessing the data is not always effective, simple constraints may be added to the problem allowing us to solve randomly generated GFCPs that are significantly larger than any previously reported in the literature. Results are also presented which give insight into the effectiveness of a frequently used heuristic for the GFCP.
Keywords:
additional constraints; data preprocessing; branch-and-bound; fixed charge problem; computational results; heuristicReferences:
| [1] | Barr, R. S.; Glover, F.; Klingman, D., A new optimization method for large scale fixed charge transportation problems, Op/is Res., 29, 448-463 (1981) · Zbl 0455.90055 |
| [2] | Brown, G. G.; Graves, G. W.; Honczarenko, M. D., Design and operation of a multicommodity production/distribution system using primal goal decomposition, Mgmt Sci., 33, 1469-1480 (1987) |
| [3] | Kennington, J. L.; Unger, V. E., A new branch and bound algorithm for the fixed charge transportation problem, Mgmt Sci., 22, 1116-1126 (1976) · Zbl 0329.90039 |
| [4] | Kennington, J. L.; Unger, V. E., The fixed charge transportation problem: a computational study with a branch-and-bound code, IIE Trans., 8, 241-247 (1976) |
| [5] | McKeown, P. G., A vertex ranking procedure for linear fixed charge problems, Opns Rex., 23, 1183-1191 (1975) · Zbl 0329.90041 |
| [6] | McKeown, P. G., A branch-and-bound algorithm for solving fixed charge problems, Naval Res. Log. Q., 28, 607-617 (1981) · Zbl 0535.90066 |
| [7] | Steinberg, D. I., The fixed charge problem, (Report No. C00-1493-15 (1969), Department of Applied Mathematics and Computer Science, Washington University) · Zbl 0203.52301 |
| [8] | Steinberg, D. I., The fixed charge problem, Naval Res. Log. Q., 17, 217-236 (1970) · Zbl 0203.52301 |
| [9] | Taha, H., Concave minimization over a convex polyhedron, Naval Res. Log. Q., 20, 533-547 (1973) · Zbl 0286.90052 |
| [10] | Cabot, A. V.; Erenguc, S. S., Improved penalties for fixed cost linear programs using Lagrangean relaxation, Mgmt Sci., 27, 856-869 (1986) · Zbl 0599.90084 |
| [11] | Wright, D. D.; von Lanzenauer, C. H., Solving the fixed charge problem with Lagrangean relaxation and cost allocation heuristics, (Working Paper No. 85-21 (1985), School of Business Administration, The University of Western Ontario: School of Business Administration, The University of Western Ontario London, Canada) · Zbl 0679.90045 |
| [12] | Erenguc, S. S.; Benson, H. P., The interactive fixed charge linear programming problem, Naval Res. Log. Q., 33, 157-177 (1986) · Zbl 0597.90057 |
| [13] | Johnson, E., (Lecture Notes (1979), The University of Georgia: The University of Georgia Athens, Ga) |
| [14] | Nemhauser, G. L.; Wolsey, L. A., Integer and Combinatorial Optimization (1988), Wiley: Wiley New York · Zbl 0469.90052 |
| [15] | Walker, W. E., A heuristic adjacent extreme point algorithm for the fixed charge problem, Mgmt Sci., 22, 587-596 (1976) · Zbl 0316.90041 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
