A GLANCE AT SOLUTION METHODS

In this section we outline two standard solution methods:

1. The simplex method for continuous LP problems (Section 12.6.1)
2. The LP-based branch and bound method for MILP problems (Section 12.6.2)

Both are widely available in commercial software packages, but even a cursory knowledge of their internal working may be a useful asset; nevertheless, readers may safely skip this section. We should also stress the fact that we are going to describe basic solution strategies, leaving aside a lot of issues concerning robustness and efficiency. They should be regarded as useful starting points to understand what commercial tool achieve, as well as their potential pitfalls.

The simplex method is a remarkably fast method, able to solve rather large-scale problem instances, and it was invented in 1947 by George Dantzig. More recently, alternative algorithms have been proposed, generally labeled interior-point methods, which may be more efficient for some problems. The state of the art for branch and bound methods is a bit less happy, because they are generally slower and there are some kind of problems that are very difficult to solve to optimality. One possible alternative is the development of heuristic approaches to find a satisfactory solution, possibly a near-optimal one. Heuristics can be quite powerful but are typically problem-specific and are beyond the scope. Another issue is that, more often than not, they require ad hoc software development. Since branch and bound code is available on the shelves, it may be more advisable to make the best of it, when possible. In fact, branch and bound methods may be applied as heuristics, if we give up the guarantee of finding an optimal solution. Furthermore, we may sometimes reformulate the model in order to improve its solvability; this is where model building and model solving meet each other. We illustrate the idea in Section 12.6.3.