A Survey of Lagrangian Techniques for Discrete Optimization.

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1977
Accession Number
ADA050791

Entities

People

  • Jeremy F. Shapiro

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Air Platforms
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Computational Complexity
  • Computer Programming
  • Dynamic Programming
  • Evolutionary Algorithms
  • Heuristic Methods
  • Integer Programming
  • Inventory
  • Inventory Control
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • Operations Research
  • Optimization
  • Production
  • Simplex Method

Readers

  • Business Analytics
  • Operations Research