Accession Number:

ADA050791

Title:

A Survey of Lagrangian Techniques for Discrete Optimization.

Descriptive Note:

Technical rept.,

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE OPERATIONS RESEARCH CENTER

Personal Author(s):

Report Date:

1977-05-01

Pagination or Media Count:

45.0

Abstract:

This survey covers the theory and application of Lagrangian techniques to discrete optimization problems. A discussion of the applications includes integer programming special structures which can be exploited by Lagrangean techniques, multi-item production scheduling and inventory control problems, and the traveling salesman problem. The relationship of Lagrangean techniques to duality theory and convex analysis is given including a discussion of algorithms to solve the dual problems. Duality theory for integer programming and its relationship to the cutting plane method is reviewed. The use of Lagrangean techniques in conjunction with branch and bound is presented in a general framework for solving discrete optimization problems. Author

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE