Lagrangean relaxation for integer programming

A. M. Geoffrion

doi:10.1007/bfb0120690

book chapter Jan 01, 1974

Lagrangean relaxation for integer programming

A. M. Geoffrion

Mathematical Programming Studies pp. 82-114 · Springer Berlin Heidelberg

View at Publisher Save 10.1007/bfb0120690

Topics

No keywords indexed for this article. Browse by subject →

References

30

[1]

R.D. Armstrong and P. Sinha, “Improved penalty calculations for a mixed integer branch-and-bound algorithm”, Mathematical Programming 6 (1974) 212–223. 10.1007/bf01580237

[2]

R. Brooks and A. Geoffrion, “Finding Everett’s Lagrange multipliers by linear programming”, Operations Research 14 (1966) 1149–1153. 10.1287/opre.14.6.1149

[3]

Dakin, R.J., “A free search algorithm for mixed integer programming problems”, Computer Journal, 8 (1965) 250–255. 10.1093/comjnl/8.3.250

[4]

N.J. Driebeek, “An algorithm for the solution of mixed integer programming problems”, Management Science 12 (1966) 576–587. 10.1287/mnsc.12.7.576

[5]

Everett, H.M., “Generalized Lagrange multiplier method for solving problems of optimum allocation of resources”, Operations Research 11 (1966) 399–417. 10.1287/opre.11.3.399

[6]

M.L. Fisher, “Optimal solution of scheduling problems using Lagrange multipliers: Part I”, Operations Research 21 (1973) 1114–1127. 10.1287/opre.21.5.1114

[7]

M.L. Fisher, “A dual algorithm for the one-machine scheduling problem”, Graduate School of Business Rept., University of Chicago, Chicago, Ill. (1974).

[8]

M.L. Fisher, W.D. Northup and J.F. Shapiro, “Using duality to solve discrete optimization problems: Theory and computational experience”, Working Paper OR 030-74, Operations Research Center, M.I.T. (1974).

[9]

M.L. Fisher and L. Schrage, “Using Lagrange multipliers to schedule elective hospital admissions”, Working Paper, University of Chicago, Chicago, Ill. (1972).

[10]

M.L. Fisher and J.F. Shapiro, “Constructive duality in integer programming”, SIAM Journal on Applied Mathematics, to appear. 10.1137/0127003

[11]

J.J.H. Forrest, J.P.H. Hirst and J.A. Tomlin, “Practical solution of large mixed integer programming problems with UMPIRE”, Management Science 20 (1974) 733–773. 10.1287/mnsc.20.5.736

[12]

A.M. Geoffrion, “An improved implicit enumeration approach for integer programming”, Operations Research 17 (1969) 437–454. 10.1287/opre.17.3.437

[13]

A.M. Geoffrion, “Duality in nonlinear programming”, SIAM Review 13 (1971) 1–37. 10.1137/1013001

[14]

A.M. Geoffrion and R.E. Marsten, “Integer programming algorithms: A framework and state-of-the-art survey”, Management Science 18 (1972) 465–491. 10.1287/mnsc.18.9.465

[15]

A.M. Geoffrion and R.D. McBride, “The capacitated facility location problem with additional constraints”, paper presented to the Joint National Meeting of AIIE, ORSA, and TIMS, Atlantic City, November 8–10, 1972.

[16]

F. Glover, “A multiphase-dual algorithm for the zero-one integer programming problem”, Operations Research 13 (1965) 879–919. 10.1287/opre.13.6.879

[17]

F. Glover, “Surrogate constraints”, Operations Research 16 (1968) 741–749. 10.1287/opre.16.4.741

[18]

H.J. Greenberg and T.C. Robbins, “Finding Everett’s Lagrange multipliers by Generalized Linear Programming, Parts I, II, and III”, Tech. Rept. CP-70008, Computer Science/Operations Research Center, Southern Methodist University, Dallas, Tex. revised (June 1972).

[19]

W.C. Healy, Jr., “Multiple choice programming”, Operations Research 12 (1964) 122–138. 10.1287/opre.12.1.122

[20]

The Traveling-Salesman Problem and Minimum Spanning Trees

Michael Held, Richard M. Karp

Operations Research 1970 10.1287/opre.18.6.1138

[21]

The traveling-salesman problem and minimum spanning trees: Part II

Michael Held, Richard M. Karp

Mathematical Programming 1971 10.1007/bf01584070

[22]

M. Held, P. Wolfe and H.P. Crowder, “Validation of subgradient optimization”, Mathematical Sciences Department, IBM Watson Research Center, Yorktown Heights, N.Y. (August 1973).

[23]

W.W. Hogan, R.E. Marsten and J.W. Blankenship, “The BOXSTEP method for large scale optimization”, Working Paper 660-73, Sloan School of Management, M.I.T. (December 1973).

[24]

R.E. Marsten, private communication (August 22, 1973).

[25]

G.L. Nemhauser and Z. Ullman, “A note on the generalized Lagrange multiplier solution to an integer programming problem”, Operations Research 16 (1968) 450–452. 10.1287/opre.16.2.450

[26]

G.T. Ross and R.M. Soland, “A branch and bound algorithm for the generalized assignment problem”, Mathematical Programming, to appear. 10.1007/bf01580430

[27]

J.F. Shapiro, “Generalized Lagrange multipliers in integer programming”, Operations Research 19 (1971) 68–76. 10.1287/opre.19.1.68

[28]

J.A. Tomlin, “An improved branch and bound method for integer programming”, Operations Research 19 (1971) 1070–1075. 10.1287/opre.19.4.1070

[29]

J.A. Tomlin, “Branch and bound methods for integer and non-convex programming”, in: J. Abadie, ed., Integer and nonlinear programming (North-Holland, Amsterdam, 1970).

[30]

A.F. Veinott and G.B. Dantzig, “Integral extreme points”, SIAM Review 10 (1968) 371–372. 10.1137/1010063

Cited By

1,025

A survey for solving mixed integer programming via machine learning

Jiayi Zhang, Chang Liu · 2023

Neurocomputing

Cooperative lot sizing with transshipments and scarce capacities: solutions and fair cost allocations

J. Drechsel, A. Kimms · 2011

International Journal of Production...

Simultaneous Scheduling and Control of Multiproduct Continuous Parallel Lines

Antonio Flores-Tlacuahuac, Ignacio E. Grossmann · 2010