The reduced cost branch and bound algorithm for mixed integer programming. (English) Zbl 0606.90098
A different branch and bound algorithm for mixed integer programming is presented. Unlike standard linear programming based branch and bound algorithms, where a single fractional variable (or Special Ordered Set) is selected for problem separation, the proposed method selects groups of variables for separation on the basis of their reduced cost in an LP relaxation. The proposed method restricts a large portion of the integer variables to zero on one branch. The net effect is that the original integer program is solved by optimizing a series of smaller, more tightly restricted, integer programs. The authors have programmed the algorithm using the Extended Control Language of the IBM MPSX/370-MIP/370 mixed integer programming package. Computational results are presented that demonstrate the efficiency of the method on problems where the 0/1 variables are partitioned into multiple choice constraints containing special ordered sets of variables. While the computational results are limited to this class of problems the algorithm can, in theory, be applied to any mixed integer programming problem.
Software:
LINDOReferences:
| [1] | Balas, E.; Zamal, E., An algorithm for large zero-one knapsack problems, Ops Res., 28, 1130-1154 (1980) · Zbl 0449.90064 |
| [2] | Beale, E. M.L.; Tomlin, J. A., Special facilities in a general mathematical programming system for nonconvex problems using ordered sets of variables, (Lawrence, J., Proceedings of the Fifth International Conference on Operational Research (1970), Tavistock: Tavistock London) · Zbl 0249.90052 |
| [3] | Dembo, R.; Mulvey, J., On the analysis and comparison of mathematical programming techniques, (White, W., Computers and Mathematical Programming. Computers and Mathematical Programming, National Bureau of Standards Special Publication 502 (1978)), Washington, D.C. |
| [4] | Forrest, J. J.H.; Hirst, J. P.H.; Tomlin, J. A., Practical solution of large mixed integer programming problems with UMPIRE, Management Sci., 20, 736-773 (1974) · Zbl 0304.90079 |
| [5] | Garfinkel, R.; Nemhauser, G., Integer Programming (1972), Wiley: Wiley New York · Zbl 0259.90022 |
| [6] | Gauthier, J. M.; Ribiere, G., Experiments in mixed-integer linear programming using pseudo-costs, Math. Prog., 12, 26-47 (1977) · Zbl 0362.90070 |
| [7] | Geoffrion, A. M.; Marsten, R. E., Integer programming algorithms: a framework and state-of-the-art survey, Management Sci., 16, 652-691 (1970) · Zbl 0238.90043 |
| [8] | Johnson, E.; Powell, S., Integer programming codes, (Greenberg, H., Design and Implementation of Optimization Software (1978), Sijthoff & Noordhoff: Sijthoff & Noordhoff Alphen aan den Rijn) |
| [9] | Martin, K., The optimization of integer programs with special ordered sets of variables, (Ph.D. Dissertation (1980), University of Cincinnati: University of Cincinnati Cincinnati, Ohio) |
| [10] | Martin, K.; Sweeney, D., An ideal column algorithm for integer programs with special ordered sets of variables, Math. Prog., 26, 48-63 (1983) · Zbl 0517.90050 |
| [11] | Schrage, L., (User’s Manual for LINDO (1981), Scientific Press: Scientific Press California) |
| [12] | Soyster, A. L.; Lev, B.; Slivka, W., Zero-one programming with many variables and few constraints, Europ. J. Op. Res., 2, 195-201 (1978) · Zbl 0381.90076 |
| [13] | Sweeney, D.; Murphy, R., Branch and bound methods for multi-item scheduling, Ops Res., 29, 853-864 (1981) · Zbl 0467.90035 |
| [14] | Tomlin, J. A., Branch and bound methods for integer and nonconvex programming, (Abadie, J., Integer and Nonlinear Programming (1970), North-Holland: North-Holland Amsterdam) · Zbl 0336.90038 |
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.
