Given a generic m by n matrix A, a lattice point h in Z is a neighbor of the origin if the body {x : Ax < b}, with bi = max{0, aih}, i = 1, …, m, contains no lattice point other than 0 and h. The set of neighbors, N(A), is finite and Asymmetric. We show that if A’ is another matrix of the same size with the property that sign aih = sign ai’ h for every i and every h in N(A), then A’ has precisely the same set of neighbors as A. The collection of such matrices is a polyhedral cone, described by a finite set of linear inequalities, each such inequality corresponding to a generator of one of the cones Ci = pos(h in N(A): aih < 0}. Computational experience shows that Ci has “few” generators. We demonstrate this in the first nontrivial case n = 3, m = 4.
Given a generic m x n matrix A, the simplicial complex K(A) is defined to be the collection of simplices representing maximal lattice point free convex bodies of the form {x: Ax < b}. The main result of this paper is that the topological space associated with K(A) is homeomorphic with Rm-1.
The pricing tests for optimality in a convex programming problem are not available when the production possibility set displays economies of scale. The paper argues that indivisibilities in production are one of the major causes of such economies. The constrained optimization problems arising in the presence of indivisibilities are integer programs, and it is proposed that the unique, minimal quantity tests for such problems may shed some light on the internal organization of a large firm.
The pricing tests for optimality in a convex programming problem are not available when the production possibility set displays economies of scale. The paper argues that indivisibilities in production are one of the major causes of such economies. The constrained optimization problems arising in the presence of indivisibilities are integer programs, and it is proposed that the unique, minimal quantity tests for such problems may shed some light on the internal organization of a large firm.
The simplicial complex K(A) is defined to be the collection of simplices, and their proper subsimplices, representing maximal lattice free bodies of the form {x: Ax < b}, with A a fixed (n + 1) × n matrix. The topological space associated with K(A) is shown to be homeomorphic to Rn, and the space obtained by identifying lattice translates of these simplices is homeomorphic to the n-torus.
Tjalling C. Koopmans made fundamental contributions to economics. This paper, prepared for a National Academy of Sciences volume of memoirs, provides a biographical sketch of this extraordinary individual.
Tjalling C. Koopmans made fundamental contributions to economics. This paper, prepared for a National Academy of Sciences volume of memoirs, provides a biographical sketch of this extraordinary individual.
In recent years many advances have been made in solution techniques for specially structured 0–1 integer programming problems. In contrast, very little progress has been made on solving general (mixed integer) problems. This, of course, is not true when viewed from the theoretical side: Lenstra (1981) made a major breakthrough, obtaining a polynomial-time algorithm when the number of integer variables is fixed. We discuss a practical implementation of a Lenstra-like algorithm, based on the generalized basis reduction method of Lovasz and Scarf (1988). This method allows us to avoid the ellipsoidal approximations required in Lenstra’s algorithm. We report on the solution of a number of small (but difficult) examples, up to 100 integer variables. Our computer code uses the linear programming optimizer CPlex as a subroutine to solve the linear programming problems that arise.
The paper, prepared for a Roundtable on Major Economic Problems in the U.S. and the U.S.S.R., discusses some aspects of price theory — in particular, the theory of general equilibrium — which may offer some theoretical insights about the economic problems to be encountered during the transition from Socialism to private markets in the Soviet Union.
The paper, prepared for a Roundtable on Major Economic Problems in the U.S. and the U.S.S.R., discusses some aspects of price theory — in particular, the theory of general equilibrium — which may offer some theoretical insights about the economic problems to be encountered during the transition from Socialism to private markets in the Soviet Union.
Keywords: Socialism, scale economies, general equilibrium, market structures, prices, price theory
Let A be a fixed integer matrix of size m by n and consider all b for which the body is full dimensional. We examine the set of shortest non-zero integral vectors with respect to the family of norms. We show that the number of such shortest vectors is polynomial in the bit size of A, for fixed n. We also show the existence, for any n, of a family of matrices M for which the number of shortest vectors has as a lower bound a polynomial in the bit size of M of the same degree at the polynomial bound.