Abstract
Given a configuration of parameters that satisfies a set of constraints, and given external changes that change and fix the value of some parameters making the configuration invalid, the problem of interactive reconfiguration is to assist a user to interactively reassign a subset of the parameters to reach a consistent configuration again. In this paper, we present two BDD-based algorithms for solving the problem, one based on a monolithic BDD-representation of the solution space and another using a set of BDDs. We carry out experiments on a set of power supply restoration benchmarks and show that the set-of-BDDs algorithm scales much better.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Binary Decision Diagram
- Partial Assignment
- Power Distribution Network
- Monolithic Approach
- Restoration Quality
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Hadzic, T., Subbarayan, S., Jensen, R.M., Andersen, H.R., Møller, J., Hulgaard, H.: Fast backtrack-free product configuration using a precompiled solution space representation. In: PETO Conference, DTU-tryk, pp. 131–138 (2004)
Subbarayan, S., Jensen, R.M., Hadzic, T., Andersen, H.R., Hulgaard, H., Møller, J.: Comparing two implementations of a complete and backtrack-free interactive configurator. In: CP 2004 CSPIA Workshop, pp. 97–111 (2004)
Bryant, R.E.: Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers 8, 677–691 (1986)
Hadzic, T., Andersen, H.R.: Interactive Reconfiguration in Power Supply Restoration. Technical Report ITU-TR-2004-68, IT University of Copenhagen (2005)
Subbarayan, S.: Integrating CSP decomposition techniques and BDDs for compiling configuration problems. In: Barták, R., Milano, M. (eds.) CPAIOR 2005. LNCS, vol. 3524, pp. 351–365. Springer, Heidelberg (2005)
Goldberg, E., Novikov, Y.: BerkMin: A fast and robust SAT-solver. In: Design, Automation, and Test in Europe (DATE 2002), pp. 142–149 (2002)
Moskewicz, M.W., Madigan, C.F., Zhao, Y., Zhang, L., Malik, S.: Chaff: Engineering an efficient SAT solver. In: Proceedings of the 38th Design Automation Conference (DAC 2001) (2001)
Lind-Nielsen, J.: BuDDy - A Binary Decision Diagram Package (online), http://sourceforge.net/projects/buddy
Thiébaux, S., Cordier, M.O.: Supply restoration in power distribution systems – a benchmark for planning under uncertainty
Bertoli, P., Cimatti, A., Slanley, J., Thiébaux, S.: Solving power supply restoration problems with planning via symbolic model checking. In: ECAI 2002 (2002)
Bak, T., Henney, S.: Power Supply Restoration - a Constraint-based Model for Reconfiguration of 10kv Electrical Distribution Networks. ITU (2004)
Sonne, L., Jensen, R.: Power Supply Restoration. Master’s thesis, Department of Innovation, IT University of Copenhagen (2005)
Nesa (online), http://www.nesa.dk
Power Supply Restoration Benchmarks (online), http://www.itu.dk/people/tarik/psr
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hadzic, T., Andersen, H.R. (2005). Interactive Reconfiguration in Power Supply Restoration. In: van Beek, P. (eds) Principles and Practice of Constraint Programming - CP 2005. CP 2005. Lecture Notes in Computer Science, vol 3709. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11564751_61
Download citation
DOI: https://doi.org/10.1007/11564751_61
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29238-8
Online ISBN: 978-3-540-32050-0
eBook Packages: Computer ScienceComputer Science (R0)