Special‐Purpose Algorithms
George L. Nemhauser, Laurence A. Wolsey · 1988
The three major reasons why a problem class may not be solved satisfactorily by a general algorithm are: (1) size of the formulation; (2) weakness of the bounds; and (3) speed of the algorithm. This chapter shows how structure can be used either to devise special-purpose algorithms or to improve the performance of general algorithms for several classes of problems. It presents some methods that take advantage of structure. First, the chapter discusses strong cutting plane (or constraint generation) algorithms. Then, it presents some ways of quickly finding nearly optimal dual and primal feasible solutions. Next, the chapter discusses the algorithms that can be used in combination with Lagrangian and Benders' decomposition, as well as some of the problems that arise in their implementation. Finally, it describes dynamic programming and illustrates its application to certain discrete optimization problems.