Is the Simplex Method an exact, approximate or a heuristic method?

Question

I'd like to understand whether the simplex method is an exact method (like Branch&Bound, Branch&Cut...), an approximate method or a heuristic method.

Answer 1

Yes, the simplex algorithm is an exact method, when applied to a linear programming problem in canonical form; i.e. it finds a vertex where the objective function is maximum.
(cf. https://en.wikipedia.org/wiki/Simplex_algorithm for example)

Limitations in exactitude, that you may have heard of:

• There may be more than one vertex where the objective function is maximum. The simplex algorithm only finds one. The other ones are however connected to the one found by simplex, due to convexity, so it is straigthforward to complement the method to detect them.
• Similarly, if there are more than one vertex where objective function is maximum, the entire facet defined by those vertices has same objective function value, i.e. the maximum is also reached there. The simplex does not detect this of course because it only uses vertices, but as above this is straightforward.
• Selecting the variable to pivot, at each step, is an operation for which various heuristics have been devised. Unfortunately some obvious ones can loop indefinitely around the same facet. But heuristics that do not have this drawback are well-known.
• Of course if conditions are only approximated, i.e. the real problem is only approximatively linear, solutions may not be exact. This is often the case in practice, but is not a problem with the algorithm itself, rather with the modelization.
• Many real-world problems are integer linear programming, or mixed integer linear programming, rather than pure linear programming problems. Then the simplex method may be used on a linear relaxation of the problem, and of course the solution will not be exact (except when the matrix is totally unimodular).