Papers

Author(s)
Thomas Saaty
Joseph M. Katz Graduate School of Business
University of Pittsburgh
United States

Publication date: Mar, 1968

Journal: Naval Research Logistics Quarterly
Vol.: 15- Issue: 1- Pages: 1-22

Abstract: The purpose of this paper is to give some elementary theorems on optimization in integers of nonlinear expressions subject to simple equality constraints. Other than the complicated algorithms of integer linear-programming, there is a dirth of examples and a tradition to follow which might help improve one's intuition or confidence about how to approach a problem (perhaps nonlinear) which requires a solution in integers. Continuous approximations through Lagrange multiplier techniques, at best, serve as a starting point or conjecture in the search for the optimum and nearest integer approximations usually violate the constraints and must be successively altered in order to become feasible. Sometimes, as one may reasonably expect, such nearest integer approximations, with slight effort, yield the answer. However, this is the exception since for many problems the solution point is remote from the nearest integer approximation to the multiplier approach. In any case one must prove that one has the optimum solution. The techniques required to carry out such a proof are considerably different from those used in the continuous case.

Keywords: Linear programming, Optimization

URL: https://onlinelibrary.wiley.com/doi/pdf/10.1002/nav.3800150102