Editing Integer programming (section)

===Exact algorithms===
When the matrix <math>A</math> is not totally unimodular, there are a variety of algorithms that can be used to solve integer linear programs exactly.  One class of algorithms are [[Cutting-plane method|cutting plane methods]], which work by solving the LP relaxation and then adding linear constraints that drive the solution towards being integer without excluding any integer feasible points.

Another class of algorithms are variants of the [[branch and bound]] method.  For example, the [[branch and cut]] method that combines both branch and bound and cutting plane methods.  Branch and bound algorithms have a number of advantages over algorithms that only use cutting planes.  One advantage is that the algorithms can be terminated early and as long as at least one integral solution has been found, a feasible, although not necessarily optimal, solution can be returned.  Further, the solutions of the LP relaxations can be used to provide a worst-case estimate of how far from optimality the returned solution is.  Finally, branch and bound methods can be used to return multiple optimal solutions.