Accession Number:

ADA036860

Title:

The Value Function of a Mixed Integer Program: II.

Descriptive Note:

Research rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

Report Date:

1976-12-01

Pagination or Media Count:

29.0

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.

Subject Categories:

  • Theoretical Mathematics
  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE