Name
Abstract | ||
|---|---|---|
Branch & 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 datastructure 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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11427186_39 | WEA |
Keywords | Field | DocType |
cut framework,state-of-the-art mip-solvers,computational result,strong valid inequality,max-ones problem,valid inequality,1-integer linear program,binary decision diagrams,state-of-the-art method,linear programming relaxation,computational logic,branch and cut,cutting plane,binary decision diagram,data structure | Computational logic,Discrete mathematics,Cutting-plane method,Computer science,Branch and cut,Binary decision diagram,Algorithm,Directed acyclic graph,Linear programming,Linear programming relaxation,Search tree | Conference |
Volume | ISSN | ISBN |
3503 | 0302-9743 | 3-540-25920-1 |
Citations | PageRank | References |
12 | 0.85 | 11 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bernd Becker | 1 | 855 | 73.74 |
| markus behle | 2 | 34 | 2.43 |
| Friedrich Eisenbrand | 3 | 726 | 53.74 |
| Ralf Wimmer | 4 | 407 | 34.28 |