Lagrangean Relaxation and Its Uses in Integer Programming

Abstract

Taking a subset of the constraints of a general mixed integer linear program up into the objective function in a Lagrangean fashion (with fixed multipliers) yields what the author calls a Lagrangean relaxation of the original program. The paper gives a reasonably comprehensive development of the use of this simple device in the context of branch- and-bound. The selective application of these ideas can yield significant improvements in performance for special classes of problems.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1972
Accession Number
AD0755118

Entities

People

  • Arthur M. Geoffrion

Organizations

  • University of California, Los Angeles

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • California
  • Classification
  • Coefficients
  • Computations
  • Computer Programming
  • Computers
  • Contractors
  • Contracts
  • Digital Computers
  • Integer Programming
  • Linear Programming
  • Optimization
  • Scheduling (Production)
  • Security
  • Simplex Method

Readers

  • Operations Research