Abstract
This note presents an efficient method for the routine solution of the subproblem associated with the Lagrangian dual of discrete programming problems having separable non-linear objective function and linear constraints. An additional advantage for subgradient methods is described.
Similar content being viewed by others
References
A.V. Aho, J.E. Hopcroft and J.D. Ullman,The design and analysis of computer algorithms (Addison-Wesley, Reading, MA, 1974).
M.E. Dyer, “Vertex enumeration in mathematical programming”, Ph.D. Thesis, University of Leeds (1979).
M.L. Fisher, “The Lagrangian relaxation method for solving integer programming problems”,Management Science 27 (1981) 1–18.
N. Katoh, T. Ibaraki and H. Mine, “Notes on the problem of the allocation of resources to activities in discrete quantities”,Journal of the Operational Research Society 31 (1980) 595–598.
T.L. Morin and R.E. Marsten, “An algorithm for nonlinear knapsack problems”,Management Science 22 (1976) 1147–1158.
F.A. Tillman, C-L. Hwang and W. Kuo,Optimization of systems reliability (Marcel Dekker, New York, 1980).
J. Walker, “Multi-criteria programming with applications to the redundancy allocation problem”, Ph.D. Thesis, CNAA, Teesside Polytechnic, Middlesbrough (1980).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Dyer, M.E., Walker, J. Solving the subproblem in the lagrangian dual of separable discrete programs with linear constraints. Mathematical Programming 24, 107–112 (1982). https://doi.org/10.1007/BF01585097
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01585097