Branch and cut #

Branch and cut is an algorithm (or family of algorithms) to solve integer linear programs.

Algorithm #

  1. Solve the linear relaxation of the ILP.
  2. Use branch and bound to find a cutting plane and use this to add an additional inequality to the linear relaxation. Non-integral solutions to the relaxed LP constitute upper bounds.
  3. Solve again until we have an optimal solution.

Column generation #

According to Wikipedia, column generation (which is a method that I keep reading about) is the same as finding cutting planes in the dual problem. Need to understand this a little better.

  • A good resource on ILPs in general with a good explanation on cutting planes.
  • Coursera lecture on cutting planes from a particularly enthusiastic lecturer.
  • Explicit example.