Interactive Configuration Based on Linear Programming

Interactive configuration denotes a process of a userinteractively specifying a product (or a service) using asupporting program called a configurator. Choices for eachavailable product component are usually modelled as variablesover finite domains, and the knowledge about the valid productspecifications is encoded as propositional constraints over thesevariables. Interactive configuration over finite domains is NP-hard. Most solution approaches therefore either give up on someinteractive requirements or move the NP-hard part to an offlinephase by first compiling the set of valid assignments to efficientstructures (such as reduced ordered BDDs) and then performingpolynomial interactions online.
In this paper we consider the case when all the constraintsare linear inequalities and when the variable domains are the setof real numbers. Using results from the field of linearprogramming (LP) we show that in this case the interactiveconfiguration can be performed in polynomial time. We moreovershow how the simplex algorithm (in worst-case exponential butperforming very well in practice), can be efficiently adapted tosupport interactive configuration. We also identify and implementsome new, LP-specific configuration functionalities, andillustrate how the concept of interactive configuration can beused in classical LP problems, especially to provide support forinteractively selecting values for variables.