Open Access. Powered by Scholars. Published by Universities.®
- File Type
Articles 1 - 2 of 2
Full-Text Articles in Industrial Organization
Approximate Compilation Of Constraints Into Multivalued Decision Diagrams, Tarik Hadzic, John Hooker, Barry O'Sullivan, Peter Tiedemann
Approximate Compilation Of Constraints Into Multivalued Decision Diagrams, Tarik Hadzic, John Hooker, Barry O'Sullivan, Peter Tiedemann
John Hooker
We present an incremental refinement algorithm for approximate compilation of constraint satisfaction models into multivalued decision diagrams (MDDs). The algorithm uses a vertex splitting operation that relies on detection of equivalent paths in the MDD. Although the algorithm is quite general, it can be adapted to exploit constraint structure by specializing the path equivalence test to particular constraints.We show how to modify the algorithm in a principled way to obtain an approximate MDD when the exact MDD is too large for practical purposes. This is done by replacing the equivalence test with a constraint-specific measure of distance. We demonstrate the …
Postoptimality Analysis For Integer Programming Using Binary Decision Diagrams, Tarik Hadzic, John N. Hooker
Postoptimality Analysis For Integer Programming Using Binary Decision Diagrams, Tarik Hadzic, John N. Hooker
John Hooker
We show how binary decision diagrams (BDDs) can be used to solve and obtain postoptimality analysis for linear and nonlinear integer programming problems with binary or general integer variables. The constraint set corresponds to a unique reduced BDD that represents all feasible or near-optimal solutions, and in which optimal solutions correspond to certain shortest paths. The BDD can be queried in real time for in-depth postoptimality reasoning. The approach is equally effective for linear and nonlinear problems. There are currently no other methods for obtaining such an analysis, short of repeatedly re-solving the problem. We illustrate the analysis on capital …