Interactive Reconfiguration in Power Supply Restoration

Interactive configuration is the problem of assisting a user inselecting values for parameters that respect given constraints. Theproblem was introduced as a problem of productconfiguration with the emergence of the mass-customizationparadigm in product manufacturing but has also been applied toother application areas. Examples include specifying a product (aPC or a car), a service (a plane ticket or an insurance) orsetting up equipment (a VCR or heating controller). Intuition isthat in these situations, there is no definable unique bestsolution, and therefore a user should instead be guided inselecting the appropriate values for the parameters while at thesame time obeying the constraints and meeting user preferences.The guidance takes the form of immediate feedback on theconsequences of choices. There are three main important featuresrequired of an implementation of interactive configuration: Itshould be complete, backtrack-free, and provide real-timeperformance. It is a computational challenge to obtain all threesimultaneously.
In this paper we look at interactive reconfiguration,where the starting point is a full valid configuration, which forexternal reasons becomes inconsistent and therefore has to bechanged back to a consistent configuration. We take the approach ofdetermining a small set of parameters that need to bechanged and on these perform interactive configuration to get backto a consistent configuration. We present two BDD-basedprecompilation algorithms for solving the problem. One based on amonolithic BDD-representation of the solution space and anotherusing a set of BDDs. Wecarry out experiments on a set of power supply restorationbenchmarks and show that the set-of-BDDs algorithm scales well. Infact, we are able to perform interactive reconfiguration onexamples where interactive configuration is not possible due toexplosions in the size of the corresponding monolithic BDDs. Thisshows that even systems that are too large for full interactiveconfiguration could be amenable to reconfiguration.