-dimensional integer linear programs form an LP-type problem of combinatorial dimension
, and can be solved by certain generalizations of linear programming algorithms in an amount of time that is linear in the number of constraints of the problem and fixed-parameter tractable in its dimension.
It is named after Belgian mathematician and mathematical psychologist Jean-Paul Doignon, who published it in 1973.
Doignon credits Francis Buekenhout with posing the question answered by this theorem.
[2] It is also called the Doignon–Bell–Scarf theorem,[3] crediting mathematical economists David E. Bell and Herbert Scarf, who both rediscovered it in 1977[4][5] and pointed out its applications to integer programming.
[1] The result is tight: there exist systems of half-spaces for which every
Such a system can be obtained, for instance, by choosing halfspaces that contain all but one vertex of the unit cube.
Another way of phrasing the result is that the Helly number of convex subsets of the integers is exactly
More generally, the Helly number of any discrete set of Euclidean points equals the maximum number of points that can be chosen to form the vertices of a convex polytope that contains no other point from the set.