Branch and cut #
Branch and cut is an algorithm (or family of algorithms) to solve integer linear programs.
- Solve the linear relaxation of the ILP.
- 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.
- 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.