Note on solving linear programs in integers
作者:
G. B. Dantzig,
期刊:
Naval Research Logistics Quarterly
(WILEY Available online 1959)
卷期:
Volume 6,
issue 1
页码: 75-76
ISSN:0028-1441
年代: 1959
DOI:10.1002/nav.3800060109
出版商: Wiley Subscription Services, Inc., A Wiley Company
数据来源: WILEY
摘要:
AbstractA recent result of Gomory (Princeton) solved an outstanding problem, namely that of solving linear programs in integers. Gomory showed how to add linear inequality constraints to a linear programming problem automatically in such a way that the extreme points of the resulting convex contain only integral solutions in the neighborhood of the minimum. In this paper an alternative method is given for generating these additional constraints in a way easy to justify and to apply. However it is not known whether these conditions will lead to a solution in a finite number of iterations of the simplex method as is true for the stronger Gomory conditions. Thus anyone considering their practical use should weigh the ease of generation against the extra number of iterations that will undoubtedly be required for convergence.
点击下载:
PDF
(121KB)
返 回