Branch and cut methods for network optimization (Q5936762)

This paper contains a survey on the use of the Branch and Cut technique for solving network related combinatorial optimization problems. After an introductory section, a description in general terms is given of the Branch and Cut methodology and of the ``separation problem'', including also a discussion on advantages and disadvantages of the technique. Then, a few applications are considered in some detail where the methodology has proved effective. In particular, the use of cutting planes related to ``good'' linear programming formulations through suitable separation routines are exemplified for the Traveling Salesman Problem, the Vehicle Routing Problem, and the Degree Constrained Minimum Spanning Tree Problem. Moreover, the development of general cutting plane methods applicable when good formulations or efficient separation routines are not available is also reported.