An application of mathematical logic to the integer linear programming problem (Q2540177)

The general integer linear programming problem, namely optimising a linear function subject to nonnegative integer solutions of a set of simultaneous linear inequalities was, until the solution in 1958 by \textit{R. E. Gomory} [Bull. Am. Math. Soc. 64, 275--278 (1958; Zbl 0085.35807)], one of the major unsolved problems in linear programming theory. This paper demonstrates that, with minimal adaptation, the decision procedure published by M. Presburger in 1930 [C. R. Congrès Math. Pays slaves, 92--101, addendum, 395 (1930; JFM 56.0825.04)], for the fragment of formal arithmetic containing just addition (i.e., Hilbert's system Z without the multiplication function and axioms for multiplication) solves this problem. The significant fact is that Presburger's algorithm was available as early as 1930.