COWLES FOUNDATION FOR RESEARCH IN ECONOMICS
AT YALE UNIVERSITY

Box 208281
New Haven, CT 06520-8281

COWLES FOUNDATION DISCUSSION PAPER NO. 916

"Neighbors of the Origin for Four by Three Matrices"

David F. Shallcross

June 1989

Scarf has defined a neighborhood system for families of integer programs where the right-hand side is allowed to vary. This system depends on a matrix A of constraint and objective function coefficients of the integer programs. This paper characterizes the set of neighbors of the origin when A is four by three; showing that it may be described as the set of integer vectors in a union of two-dimensional polyhedra, where the number of polyhedra is quadratic in the bit size of A.

Keywords: Integer programming, neighborhood systems

JEL Classification: 213