6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.
$\endgroup$
2
  • $\begingroup$ Thanks for the answer. I should note that I found this paper to be very informative on this topic. $\endgroup$ Oct 21 at 8:13
  • $\begingroup$ @AlbertoSantini Jep, that's one of the papers I have used for the topic as well. $\endgroup$
    – Sune
    Oct 21 at 9:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.