Abstract
This paper presents an extension of Tomlin's penalties for the branch-and-bound linear mixed integer programming algorithm of Beale and Small. Penalties which are uniformly stronger are obtained by jointly conditioning on a basic variable and the non-basic variable yielding the Tomlin penalty.
It is shown that this penalty can be computed with a little additional arithmetic and some extra bookkeeping. The improvement is easy to incorporate for the normal case as well as when the variables are grouped into ordered sets with generalized upper bounds. Computational experience bears out the usefulness of the extra effort for predominantly integer problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
E.M.L. Beale and R.E. Small, “Mixed integer programming by a branch-and-bound technique”,Proceedings of the 3 rd IFIP Congress 2 (1965) 450–451.
E.M.L. Beale and J.A. Tomlin, “Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables”, in:Proceedings of the 5 th international conference on operations research (Wiley, New York, 1969).
J.F. Benders, “Partitioning procedures for solving mixed-variables programming problems”,Numerische Mathematik 4 (1962) 238–252.
M. Bénichou, J.M. Gauther, P. Girodet, G. Hentgès, G. Ribière and O. Vincent, “Experiments in mixed integer linear programming”,Mathematical Programming 1 (1971) 76–94.
H.P. Crowder and E.L. Johnson, “Cyclic group methods in branch and bound”, in:Mathematical programming Eds. T.C. Hu and S.M. Robinson (Academic Press, New York, 1973) pp. 213–226.
G.B. Dantzig and R.M. Van Slyke, “Generalized upper bounding techniques”,Journal of Computer Systems Science 1 (1967) 213–226.
R.E. Davis, D.A. Kendrick and M. Weitzman, “A branch-and-bound algorithm for 0–1 mixed integer programming problems”,Operations Research 19 (1971) 1036–1044.
A.M. Geoffrion, “Lagrangian relaxation and its uses in integer programming”, Working paper No. 195, Western Management Science Institute, University of California, Los Angeles, Calif. (December 1972).
A.M. Geoffrion and R.E. Marsten, “Integer programming algorithms: A framework and state-of-the-art survey”,Management Science 18 (9) (1972) 465–491.
R.E. Gomory, “An algorithm for the mixed integer problem”, RM-2597, The Rand Corporation, Santa Monica, Calif. (1960).
W.C. Healy, “Multiple choice programming”,Operations Reserach 12 (1964) 122–138.
E.R. Lawler and D.E. Wood, “Branch-and-bound methods: A survey”,Operations Research 14 (4) (1966) 699–719.
F. Noonan, “Optimal investment planning for electrical power generation”, Dissertation, Department of Industrial Engineering and Operations Research, University of Massachusetts, Amherst, Mass. (1973).
C.C. Petersen, “Computational experience with variants of the Balas algorithm applied to the selection of R & D projects”,Management Science 13 (1967) 736–750.
B. Roy, R. Benayoun and J. Tergny, “From S.E.P. procedure to OPHELIE program”, in:Integer and nonlinear programming Ed. J. Abadie (North-Holland, Amsterdam, 1970)pp. 419–436.
J.A. Tomlin, “Branch-and-bound methods for integer and non-convex programming”, in:Integer and nonlinear programming Ed. J. Abadie (North-Holland, Amsterdam, 1970) pp. 437–450.
Author information
Authors and Affiliations
Additional information
This work was supported in part by ONR Contract N00014-67-A-0230-0006.
Rights and permissions
About this article
Cite this article
Armstrong, R.D., Sinha, P. Improved penalty calculations for a mixed integer branch-and-bound algorithm. Mathematical Programming 6, 212–223 (1974). https://doi.org/10.1007/BF01580237
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01580237