Nogood learning has proven to be an effective CSP technique critical to success in today's top SAT solvers. We extend the technique for use in integer programming and mixed integer programming. Our 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 our techniques are geared toward yielding tighter LP upper bounds, and thus smaller search trees. Experiments suggest that our nogood learning does not help in integer programming because few cutting planes are generated, and they are weak. We explain why, and identify problem characteristics that affect the effectiveness. We show how problem structure, such as mutual exclusivity of indicator variables, or at least one of a set of indicator variables having to be "on", can be used to enhance the technique. We show this also for instances that exhibit multiple occurrences of each of the two structures. We then generalize the technique to mixed-integer programming. Then we compare our techniques to Achterberg's parallel invention of an almost identical approach. This comparison yields conclusions about what techniques within the nogood learning framework for (mixed) integer programming are essential for obtaining speedup. Finally, we lay out several directions for future research down this new and potentially promising avenue.

26 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu