When branching isn’t such a good idea

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.

Comments

  1. I use this example in class to illustrate how integer programming can get messed up. Fortunately (for pedagogic purposes), Excel’s Solver does do the whole branch and bound tree (without much bounding).

  2. I guess that in this case commercial mip solvers do well thanks to symmetry handling techniques. Indeed, all solutions can be obtained by one particular solution via permuting variables. It therefore means that once one leave of the branch and bound tree is reached, then the rest of the tree does not need to be explored.

    It would be interesting to find a variant of this problem that has no symmetry and see how it goes.

    • Jean-Francois: commercial MIP does well due to a simple cut. Divide by two and round-down the right hand side. No symmetry handling needs to come into play.

      • Thank you for your comments. I tried to disable all cutting planes in CPLEX 12.5, but it still found the optimal solution quickly through an heuristic. When I turned off both heuristics and cutting planes, it finally did perform as bad as the Excel solver (branching forever).
        So I guess you were both right about how commercial MIP can handle it efficiently.

  3. Happen to stump across this post. For this kind of constraints: SumOf( 2Xj) <= |J| + 1 while every Xj is binary, MIP presolve will try to strengthen it by doing Euclidean reduction (dividing both sides by the GCD of LHS, then rounding RHS.)

Speak Your Mind

*