BDDs in a branch and cut framework

Branch and cut is today's state-of-the-art method to solve 0/1-integer linear programs. Important for the success of this method is the generation of strong valid inequalities, which tighten the linear programming relaxation of 0/1-IPs and thus allow for early pruning of parts of the search tree. In this paper we present a novel approach to generate valid inequalities for 0/1-IPs which is based on binary decision diagrams (BDDs). BDDs are a data-structure which represents 0/1-vectors as paths of a certain acyclic graph. They have been successfully applied in computational logic, hardware verification and synthesis. We implemented our BDD cutting plane generator in a branch-and-cut framework and tested it on several instances of the MAX-ONES problem and randomly generated 0/1-IPs. Our computational results show that we have developed competitive code for these problems, on which state-of-the-art MIP-solvers fall short


Published in:
Experimental and Efficient Algorithms. 4th International Workshop, WEA 2005. Proceedings (Lecture Notes in Computer Science Vol. 3503), 452 - 63
Presented at:
Santorini Island, Greece
Year:
2005
Laboratories:




 Record created 2008-05-13, last modified 2018-03-17

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)