Name
Abstract | ||
|---|---|---|
<P>We explore the idea of obtaining bounds on the value of an optimization problem from a discrete relaxation based on binary decision diagrams (BDDs). We show how to construct a BDD that represents a relaxation of a 0-1 optimization problem, and how to obtain a bound for a separable objective function by solving a shortest (or longest) path problem in the BDD. As a test case we apply the method to the maximum independent set problem on a graph. We find that for most problem instances, it delivers tighter bounds in less computation time, than state-of-the-art integer programming software obtains by solving a continuous relaxation augmented with cutting planes.</P> |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1287/ijoc.2013.0561 | INFORMS Journal on Computing |
Keywords | DocType | Volume |
binary decision diagrams,independent set,relaxations | Journal | 26 |
Issue | ISSN | Citations |
2 | 1091-9856 | 17 |
PageRank | References | Authors |
0.67 | 18 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| David Bergman | 1 | 37 | 7.54 |
| André A. Ciré | 2 | 94 | 12.87 |
| Willem Jan Van Hoeve | 3 | 517 | 39.54 |
| J. N. Hooker | 4 | 1566 | 211.17 |