Here is one toy problem that was given to me by professor Mikael Rönnqvist:
Max SumOf(Xj) (for each j in J)
subject to SumOf( 2Xj) <= |J| + 1 while every Xj is binary.
A few observations about this toy model:
- Finding an optimal solution is pretty obvious, since it implies the selection of 50% of the elements in J.
- There are J! /[(J/2)!(J/2)!] optimal solutions to this problem (this number can get pretty huge).
- A pure branch-and-bound algorithm will need to enumerate a lot of nodes before proving the optimality of any solution.
- However, preprocessing can lead to an optimal solution.
- The cutting plane 2Xj <= |J| also leads to an optimal solution.
In this case, a pure branching strategy would lead you to believe that this model is very difficult. Obviously, modern solvers are not fooled by such simple models. Cplex, Gurobi and many other solvers are well equipped to handle large knapsack-type constraints efficiently. Relatively large models can be solved at the root node or with a very small branch-and-bound tree using a combination of bound strengthening and cutting planes.