An application of mathematical logic to the integer linear programming problem
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.
- Logic applied to integer programming and integer programming applied to logic
- A characterisation of all feasible solutions to an integer program
- Fourier-Motzkin elimination extension to integer programming problems
- ``Outline of an algorithm for integer solutions to linear programs and ``An algorithm for the mixed integer problem
- scientific article; zbMATH DE number 4102512 (Why is no real title available?)
- scientific article; zbMATH DE number 1256705 (Why is no real title available?)
This page was built for publication: An application of mathematical logic to the integer linear programming problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2540177)
