VALUE FUNCTION OF A MIXED INTEGER-PROGRAM .2.

被引：31

作者：

BLAIR, CE ^{[1
]}

JEROSLOW, RG ^{[1
]}

机构：

[1] GEORGIA INST TECHNOL,COLL IND MANAGEMENT,ATLANTA,GA 30332

来源：

DISCRETE MATHEMATICS | 1979年 / 25卷 / 01期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/0012-365X(79)90147-X

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove 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. © 1979.

引用

页码：7 / 19

页数：13

共 15 条

[1] VALUE FUNCTION OF A MIXED INTEGER-PROGRAM .1. [J].

BLAIR, CE ;

JEROSLOW, RG .

DISCRETE MATHEMATICS, 1977, 19 (02) :121-138

[2]

BLAIR CE, 1974, MSRR360 CARN MELL U

[3]

BLAIR CE, 1976, MSRR397 CARN MELL U

[4]

Dijkstra E., 1959, NUMER MATH, V1, P269

[5]

Gomory R. E., 1969, Linear Algebra and Its Applications, V2, P451, DOI 10.1016/0024-3795(69)90017-2

[6]

JEROSLOW RG, 1975, MSRR362 CARN MELL U

[7]

JEROSLOW RG, 1974, PRINCIPLES CUTTING 1

[8]

JEROSLOW RG, 1976, MSRR392 CARN MELL U

[9]

Johnson E.L., 1974, MATH PROGRAM STUD, P137, DOI 10.1007/BFb0120692

[10]

Meyer R. R., 1974, Mathematical Programming, V7, P223, DOI 10.1007/BF01585518

← 1 2 →