Nogood Learning for Mixed Integer Programming

Nogood learning has proven to be an effective CSP technique critical to success in today's top SAT solvers. The authors extend the technique for use in integer programming and mixed integer programming. The technique generates globally valid cutting planes for the 0-1 IP search algorithm from information learned through constraint propagation (bounds propagation). Nogoods (cutting planes) are generated not only from infeasibility but also from bounding. All of the techniques are geared toward yielding tighter LP upper bounds, and thus smaller search trees. Experiments suggest that the nogood learning does not help in integer programming because few cutting planes are generated, and they are weak. They explain why, and identify problem characteristics that affect the effectiveness.