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.
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.
Keywords: Linear programming, mixed integer problems
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.
Let p = (p1,…,pn) be a vector of positive integers whose greatest common divisor is unity. The Frobenius problem is to find the largest integer f* which cannot be written as a non-negative integral combination of the pi. In this note we relate the Frobenius problem to the topic of maximal lattice free bodies and describe an algorithm for n = 3.