I am willing to bet that the problem most often used to teach students about branch-and-cut is the Travelling Salesman Problem (TSP). It has a number of nice characteristics which make it appropriate for this task:
- The problem itself is easy to explain and understand, its formulation requires little notation, it is trivial to come up with feasible solutions and to experiment with intuitive heuristics.
- There are at least two easy-to-explain formulations for the problem. The MTZ formulation is useful in showing how big-M constraints work. The DFJ formulation can be used to introduce (row-)extended formulations in general. Furthermore, there is an easy proof that the DFJ formulation is tighter than the MTZ. In short, it offers a lot of possible "learning moments".
- There are also multiple ways to introduce branch-and-cut for the TSP. One can start with the "integer version": separating subtour-elimination constraints for infeasible integer solutions only. Because such infeasibility can be found by inspection, this is also very easy to implement in lab classes. Next, one can talk about separation in the fractional case. This again provides other learning opportunities (Max-flow problem, Min-cut problem, duality, unimodularity, etc) and implementation challenges.
- It allows to introduce the concept of valid inequalities (VIs), exact and heuristic separation for VIs, faced-defining inequalities, etc. It also have an extensive library of well-understood inequalities (comb, etc).
I was wondering whether someone has ideas about other problems which share at least some of these characteristics with the TSP and can, thus, be given to students as additional material, homework material, etc.