Branch-and-cut (-and-price) algorithms belong to the most successful techniques for solving mixed integer linear programs
and combinatorial optimization problems to optimality (or, at least, with certified quality). In this unit, we concentrate
on sequential branch-and-cut for hard combinatorial optimization problems, while branch-and-cut for general mixed integer
linear programming is treated in [→ Martin] and parallel branch-and-cut is treated in [→ Ladányi/Ralphs/Trotter]. After telling
our most recent story ofa successful application ofbranc hand-cut in Section [1], we give in Section [2] a briefreview ofthe history, including the contributions ofpioneers with an emphasis on the computational aspects oftheir
work. In Section [3], the components ofa generic branch-and-cut algorithm are described and illustrated on the traveling salesman problem. In
Section [4], we first elaborate a bit on the important separation problem where we use the traveling salesman problem and the maximum
cut problem as examples, then we show how branchand- cut can be applied to problems with a very large number ofv ariables
(branch-and-cut-and-price). Section [5] is devoted to the design and applications ofthe ABACUS software framework for the implementation ofbranc h-and-cut algorithms. Finally, in Section [6], we make a few remarks on the solution ofthe exercise consisting ofthe design ofa simple TSP-solver in ABACUS.