Algorithm that solves every Mixed Integer Linear Program (to optimality)?

Question

Given a Mixed Integer Linear Program with rational coefficients (both for the objective functions and all constraints), is it always possible to solve it algorithmically?

I know that you usually solve these problems by applying a Branch-and-X strategy and solving the subproblems as Linear Programs. But it is not clear to me whether a the branching tree has always finitely many nodes and whether you can solve any LP (e.g. given the situation that it is very hard to determine an initial feasible solution).

Answer 1

I sometimes read the claim that Gomory cuts alone (without any branch-and-X) are sufficient for finding integer solutions to linear programs in a finite number of steps. E.g. at the bottom of page 2:

Gomory showed that alternately applying the simplex method and adding cutting planes eventually leads to a system for which the simplex method will give an integer optimum.

It gives three references to papers by Gomory, and I checked that "R.E. Gomory, An algorithm for integer solutions to linear programs, in: Recent Advances in Mathematical Programming, R.L. Graves & P. Wolfe, eds., McGraw-Hill, New York, 1963, pp. 269–302." indeed contains a mathematical proof of this statement.

---

This doesn't address the case of mixed-integer linear programs, but I guess my textbooks would have mentioned it explicitly, if this technique could not be adapted to mixed-integer linear programs.

You implicitly also pose the question whether branch-and-X alone would be sufficient for finding mixed-integer solutions to linear programs, even for completely stupid X. At least it seems possible to construct linear programs without valid integer solution for which such a sufficiently stupid branch-and-X algorithm would continue branching forever.

---

I hope it is clear to you that no known algorithm for integer programing is efficient in the sense that it runs in polynomial time, because integer programing is known to be NP-complete.