6

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.

Alberto Santini
  • 2,113
  • 9
  • 23

1 Answers1

4

The knapsack problem. Obviously not the best way to solve it (through branch and cut) but it has many of the same characteristics as the TSP:

  1. It's easy to understand
  2. It's easy to construct reasonably good heuristics
  3. Separating cover inequalities exactly is another knapsack problem (so we can naturally discuss separation vs optimization)
  4. Cover inequalities are easy to understand and easy to strengthen by extending the cover
  5. You may introduce lifting of the cover cut by introducing general lifted cover inequalities.
  6. Heuristically separating cover inequalities can be done using the heuristic invented/used in 2.
Sune
  • 6,457
  • 2
  • 17
  • 31