The Lagrangian Relaxation Method for Solving Integer Programming Problems

References

• Balas E., Christofides N. (1976) Talk presented at the Ninth International Symposium on Mathematical Programming, BudapestGoogle Scholar
• Balinski M. L., Wolfe P. Nondifferentiable optimization. Math. Programming Stud. (1975) 3(NovemberGoogle Scholar
• Bazarra M. S., Goode J. J. The traveling salesman problem: A duality approach. Math. Programming (1977) 13:221–237Crossref, Google Scholar
• Bilde O., Krarup J. Sharp lower bounds and efficient algorithms for the simple plant location problem. Ann. Discrete Math. (1977) 1:79–97Crossref, Google Scholar
• Burdet C. A., Johnson E. L. A subadditive approach to solve linear integer programs. Ann. Discrete Math. (1977) 1:117–143Crossref, Google Scholar
• Camerini P. M., Fratta L., Maffioli F. On improving relaxation methods by modified gradient techniques. Math. Programming Stud. (1975) 3:26–34Crossref, Google Scholar
• Camerini P. M., Maffioli F. Heuristically guided algorithms for K-parity matroid problems. Discrete Math (1978) 103–116Crossref, Google Scholar
• Chalmet L. G., Gelders L. F. Lagrangian relaxations for a generalized assignment-type problem. Proc. Second Eur. Congress Oper. Res. (1976) (North-Holland, Amsterdam) 103–109Google Scholar
• Christofides N., Whitlock C. An LP-based TSP algorithm. (1978) 78–79Imperial College ReportGoogle Scholar
• Cornuejols G., Fisher M. L., Nemhauser G. L. Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms. Management Sci. (1977) 23:789–810Link, Google Scholar
• Erlenkotter D. A dual-based procedure for uncapacitated facility location. Oper. Res. (1978) 26(1):992–1009Link, Google Scholar
• Etcheberry J. The set-covering problem: A new implicit enumeration algorithm. Oper. Res. (1977) 25:760–772Link, Google Scholar
• Etcheberry J., Conca C., Stacchetti E. An implicit enumeration approach for integer programming using subgradient optimization. (1978) (Universidad de Chile, Santiago, Chile) . Pub. No. 78/04/cGoogle Scholar
• Everett H. Generalized Lagrange multiplier method for solving problems of optimum allocation of resources. Oper. Res. (1963) 11:399–417Link, Google Scholar
• Fisher M. L. Optimal solution of scheduling problems using Lagrange multipliers: Part I. Oper. Res. (1973) 21:1114–1127Link, Google Scholar
• Fisher M. L., Shapiro J. F. Constructive duality in integer programming. SIAM J. Appl. Math. (1974) 27:31–52Crossref, Google Scholar
• Fisher M. L., Northup W. D., Shapiro J. F. Using duality to solve discrete optimization problems: Theory and computational experience. Math. Programming Stud. (1975) 3:56–94Crossref, Google Scholar
• Fisher M. L. A dual algorithm for the one-machine scheduling problem. Math. Programming (1976) 11:229–251Crossref, Google Scholar
• Fisher M. L., Hochbaum D. S. Database location in computer networks. J. Assoc. Comput. Mach. (1980) 27(4):718–735Crossref, Google Scholar
• Fisher M. L., Nemhauser G. L., Wolsey L. A. An analysis of approximations for finding a maximum weight Hamiltonian circuit. Oper. Res. (1979) 27(4):799–809Link, Google Scholar
• Fisher M. L., Jaikumar R., Van Wassenhove L. A multiplier adjustment method for the generalized assignment problem. (1980) . Decision Sciences Working paper, University of PennsylvaniaGoogle Scholar
• Geoffrion A. M. Lagrangian relaxation and its uses in integer programming. Math. Programming Stud. (1974) 2:82–114Crossref, Google Scholar
• Geoffrion A. M., McBridge R. Lagrangian relaxation applied to capacitated facility location problems. AIIE Trans. (1978) 10:40–47Crossref, Google Scholar
• Gilmore P. C., Gomory R. E. A linear programming approach to the cutting-stock problem, Part II. Oper. Res. (1963) 11:863–888Link, Google Scholar
• Goffin J. L. On the convergence rates of subgradient optimization methods. Math. Programming (1977) 13:329–347Crossref, Google Scholar
• Helbig Hansen K., Krarup J. Improvements of the Held-Karp algorithm for the symmetric traveling-salesman problem. Math. Programming (1974) 7:87–96Crossref, Google Scholar
• Held M., Karp R. M. The traveling salesman problem and minimum spanning trees. Oper. Res. (1970) 18:1138–1162Link, Google Scholar
• Held M., Karp R. M. The traveling salesman problem and minimum spanning trees: Part II. Math. Programming (1971) 1:6–25Crossref, Google Scholar
• Held M., Wolfe P., Crowder H. D. Validation of subgradient optimization. Math. Programming (1974) 6:62–88Crossref, Google Scholar
• Hogan W. W., Marsten R. E., Blankenship J. W. The boxstep method for large scale optimization. Oper. Res. (1975) 23:3Google Scholar
• Lorie J., Savage L. J. Three problems in capital rationing. J. Bus. (1955) 229–239Crossref, Google Scholar
• Mairs T. G., Wakefield G. W., Johnson E. L., Spielberg K. On a production allocation and distribution problem. Management Sci. (1978) 24(15):1622–1630Link, Google Scholar
• Marsten R. The use of the boxstep method in discrete optimization. Math. Programming Stud. (1975) 3:127–144Crossref, Google Scholar
• Miliotis T. Integer programming approaches to the travelling salesman problem. Math. Programming (1976a) 10:367–378Crossref, Google Scholar
• Miliotis T. An all-integer arithmetic LP-cutting planes code applied to the travelling salesman problem. (1976b) . Working paper, London School of Economics, London, U.K.Google Scholar
• Muckstadt J., Koenig S. A. An application of Lagrangian relaxation to scheduling in power generation systems. Oper. Res. (1977) 25:387–403Link, Google Scholar
• Mulvey J., Crowder H. Cluster analysis: An application of Lagrangian relaxation. Management Sci. (1979) 25:329–340Link, Google Scholar
• Nemhauser G. L., Weber G. >Optimal set partitioning, matchings and Lagrangian duality. (1978) Talk delivered at the New York ORSA/TIMS Meeting (May)Google Scholar
• Polak B. T. A general method for solving extremum problems. Soviet Math. Dokl. (1967) 8:593–597Google Scholar
• Ross G. T., Soland R. M. A branch and bound algorithm for the generalized assignment problem. Math. Programming (1975) 8:91–103Crossref, Google Scholar
• Schrage L. Implicit representation of variable upper bounds in linear programming. Math. Programming Stud. (1975) 4:118–132Crossref, Google Scholar
• Shapiro J. F. Generalized Lagrange multipliers in integer programming. Oper. Res. (1971) 19:68–76Link, Google Scholar
• Shapiro J. F. A survey of Lagrangian techniques for discrete optimization. Ann. Discrete Math. (1979a) 5:113–138Crossref, Google Scholar
• Shapiro J. F.Mathematical Programming: Structures and Algorithms (1979b) (Wiley, New York) Google Scholar
• Williams H. P. Experiments in the formulation of integer programming problems. Math. Programming Stud. (1974) 2:180–197Crossref, Google Scholar
• Williams H. P. The reformulation of two mixed integer programming problems. Math. Programming (1975) 14:325–331Crossref, Google Scholar