The Value Function of a Mixed Integer Program: II.

Abstract

It is proved that the gap in optimal value, between a mixed-integer program in rationals and its corresponding linear programming relaxation, is bounded as the right-hand-side is varied. In addition, a variant of value iteration is shown to construct subadditive functions which resolve a pure-integer program when no dual degeneracy occurs. These subadditive functions provide solutions to subadditive dual programs for integer programs which are given here, and for which the values of primal and dual problems are equal.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1976
Accession Number
ADA036860

Entities

People

  • C. E. Blair
  • Robert G. Jeroslow

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms
  • C4I

DTIC Thesaurus Topics

  • Computer Programming
  • Dynamic Programming
  • Inequalities
  • Integer Programming
  • Integrals
  • Iterations
  • Linear Algebra
  • Linear Programming
  • Mathematical Programming
  • Military Research
  • New York
  • Nonlinear Programming
  • Optimization
  • Students
  • Universities

Readers

  • Operations Research