Report Number: CS-TR-68-102
Institution: Stanford University, Department of Computer Science
Title: Integer programming over a cone
Author: Pnueli, Amir
Date: July 1968
Abstract: The properties of a special form integer programming problem
are discussed. We restrict ourselves to optimization over a
cone (a set of n constraints in n unconstrained variables)
with a square matrix of positive diagonal and non positive
off-diagonal elements. (Called a bounding form by F. Glover
It is shown that a simple iterational process gives the
optimal integer solution in a finite number of steps.
It is then shown that any cone problem with bounded rational
solution can be transformed to the bounding form and hence
solved by the outlined method.
Some extensions to more than n constraints are discussed and
a numerical example is shown to solve a bigger problem.