Interactive configuration includes the user as an essential factor in the configuration process. The main two components of an interactive configurator are a user interface on the front-end and a knowledge representation and reasoning (KRR) framework on the back-end. In this paper we discuss important requirements for the underlying KRR system to support an interactive configuration process while focusing on classical constraint satisfaction as one of the most prominent KRR technologies for configuration problems. We evaluate several freely available constraint systems with respect to the identified requirements for interactive configuration and observe that many of those requirements are not well supported.
Constraint satisfaction [
This feedback helps the user to refine the configuration space toward a satisfying solution.
The key component of an interactive configurator is the constraint manager which is responsible for incrementally maintaining the relationship between choices and constraint violations. [. . . ] The requirement to deliver meaningful and timely feedback imposes significant demands on the flexibility, efficiency and explainability of constraint management.”
Pieter van Hertum et al. studied in [
Matthieu Queva et al. describe in [
In this paper, we concretize those ideas and focus on applications where a tailor-made user interface (UI) or legacy system is enhanced with solving capabilities, i.e., by calling a general constraint solver as a component. An alternative would be to implement a special UI for an integrated configuration system such as a commercial CPQ tool or sales configurator suite, but that bears the risk of vendor-lock-in.
Figure 1 gives an overview of the addressed scenario: Users interact with the configurator to achieve their goals, thus putting challenges to user interface functionality. Those challenges pose reasoning interaction requirements on the API of the used constraint solver.
The solver is an off-the-shelf product (open-source or commercial) and has a general API, partly dedicated to configuration problems.
Together with a domain-specific product model (or knowledge base, KB), it forms the KRR component. This back-end is called by the control component which first hands over product model and userset values for decision variables from the UI to the API and then sends the solver results back to the UI.
user interaction
User Interface reasoner interaction
Control Product Model
Configurator Configuration API
Constraint Solver
The configurator shall help a user to configure a product according to his/her needs and in full compliance to the product model. The user expects the configurator to show all necessary decisions (variations) in a clear and well-arranged way, to highlight or preset the “best” alternative (value), to filter or grey-out infeasible values, to Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). recommend alternatives in case of conflicts, and to respond quickly (preferably instantaneously) to user inputs.
The remainder of this paper is organized as follows: In Section 2, an example for interactive configuration is introduced. In Section 3, we give a problem definition of interactive configuration. We define the requirements for an interactive configuration API in Section 4 and investigate in Section 5 how some typical constraint solvers satisfy these requirements. We conclude the paper in Section 6 with a summary and future work. 2
We show the challenges of interactive configuration in a small
example for a configurable product with components that can occur
multiple times (similar to generative constraint satisfaction [
A Metro train wagon has as configurable attributes the size (length in millimetres: 10000::20000) and the expected load (number of passengers: 50::200) which can be realized as seats or standing room. As components we consider only seats (max. 4 per meter of length) and handrails, and their number is configurable.
There is at most one handrail in a wagon (mandatory if there is standing room) and it has a configurable type: “standard” or “premium”.
A single seat consumes standing room for 3 persons and has as configurable attributes the type (“standard”, “premium”, “special”) and the color (“blue”, “red”, “white”). The type is constrained such that standard is not allowed to be mixed with premium (for seats and handrails). The color of all seats must be the same, except for special seats which have to be “red”.
Users expect the following (static) default values: type = standard, color = blue. Furthermore, they prefer to use all available space (as defined by the length) for passengers (i.e., maximize the load factor).
Wagon length_mm: 10000...20000 nr_passengers: 50..200 nr_seats: 0..200 standing_room: 0..200 nr_seats + standing_room = nr_passengers nr_seats + standing_room/3 4*length_mm/1000 nr_seats = count(Seat) standing_room>0 ! count(Handrail)=1 all-equal-type() all-equal-color() maximize nr_passengers/length_mm
0..1 0..80
Handrail Seat type: {standard, premium} type: {standard, premium, special} color: {blue, red, white} type=special ! color=red the UML classes to arrays of variables and some other implementation decisions, e.g., special handling of the “dynamic” parts, i.e., number of seats dependent on the expected load and length – see the MiniZinc program in Listing 1.
Listing 1. MiniZinc program for the Wagon example % C o n s t a n t s , Domains i n t : m i n _ l e n g t h = 10000 ; i n t : m a x _ l e n g t h = 20000 ; i n t : m a x _ s e a t s = m a x _ l e n g t h *4 d i v 1000 ; i n t : m i n _ l o a d = 50 ; i n t : max_load = 200 ; enum C o l o r = { b l u e , re d , w h i t e , n o C o l o r } ; enum Type = { s t a n d a r d , premium , s p e c i a l , noType } ; % Wagon var m i n _ l e n g t h . . m a x _ l e n g t h : length_mm ; var m i n _ l o a d . . max_load : n r _ p a s s e n g e r s ; var 0 . . m a x _ s e a t s : n r _ s e a t s ; var 0 . . max_load : s t a n d i n g _ r o o m ; var 0 . . 1 : n r _ h a n d r a i l s ; % S e a t s array [ 1 . . m a x _ s e a t s ] o f var C o l o r : s e a t _ c o l o r ; array [ 1 . . m a x _ s e a t s ] o f var Type : s e a t _ t y p e ; % H a n d r a i l var Type : h a n d r a i l _ t y p e ; % C o n s t r a i n numbers c o n s t r a i n t n r _ s e a t s + s t a n d i n g _ r o o m = n r _ p a s s e n g e r s ; c o n s t r a i n t n r _ s e a t s + s t a n d i n g _ r o o m / 3 <=
,! length_mm * 4 / 1 0 0 0 ; % Mandatory h a n d r a i l f o r s t a n d i n g room w i t h p r o p e r t y p e c o n s t r a i n t s t a n d i n g _ r o o m > 0 > n r _ h a n d r a i l s = 1 ; c o n s t r a i n t h a n d r a i l _ t y p e ! = s p e c i a l ; c o n s t r a i n t n r _ h a n d r a i l s = 0 < > h a n d r a i l _ t y p e = noType ; c o n s t r a i n t n r _ h a n d r a i l s > 0 > f o r a l l ( i i n 1 . . n r _ s e a t s ,! where s e a t _ t y p e [ i ] ! = s p e c i a l ) ( h a n d r a i l _ t y p e = ,! s e a t _ t y p e [ i ] ) ; % Same c o l o r and t y p e f o r a l l s e a t s b u t s p e c i a l c o n s t r a i n t f o r a l l ( i i n n r _ s e a t s +1 . . m a x _ s e a t s ) c o n s t,!ra i(nst e afto_rcaolllo r([i i ]i n= nnro_Cs oe laot rs )+;1 . . m a x _ s e a t s ) c o n s t,!ra i(nste afto_rtaylple [( ii ], j= innoT1y.p. en)r;_ s e a t s where i < j ) c o n s t,,!!ra i(snpsteeacftio_artlaylple> [( isi e], aj t!_=itnyspp1ee.[c.iina]rl_=s/e\saetass et_awttyh_eptryeep[ eji ][<)jj ;]) ! = c o n s t,,!!ra i(snpsteeacftio_artlaylple> [( isi e] ai n!t_=c1os. pl.oenrcr[i_ais]le a=/t\s s)es ea( ats_te_catoty_lpot eyr p[[ jje ]][)i ;!]= = ,! s p e c i a l > s e a t _ c o l o r [ i ] = r e d ) ; % Use f u l l l e n g t h f o r p a s s e n g e r s ( a v o i d dead s p a c e ) s o l v e maximize n r _ p a s s e n g e r s / length_mm ; % l o a d f a c t o r 3
The main two parties in interactive configuration are the user and the configurator. The user’s goal is to configure a product such that it is a valid and complete product variant that meets all his/her individual requirements. The configurator is a digital companion that supports the configuration process by deriving consequences of the user’s choices and by assisting to avoid and resolve conflicts.
The simplest type of a user interaction is to set the value of a configuration parameter. This can be seen as answering a question that the configuration tool asked. Example: For how many passengers should the wagon provide seats? Of course, the user should also be able to withdraw his/her decision, which corresponds to unsetting a configuration parameter. The value of the parameter will then be either undefined or the default value or set by solving.
In most non-trivial configuration problems, a dynamic number of
configuration objects plays an important role. Some authors of this
paper have developed configurators for large industrial products for
more than 25 years and always faced problems that could not be
represented as simple, static lists of configuration parameters (see [
Definition (User Interaction). The main types of user interactions in interactive configuration are: (i) create configuration object, (ii) delete configuration object, (iii) set/unset configuration object attribute, (iv) set/unset association between configuration objects.
We are aware that various approaches to interactive configuration
may define the list of main types of user interactions differently. For
example, structure-based configuration considers the following types
of user interaction: parametrization, decomposition, integration, and
specialization [
User interactions change the state of the configuration by making decisions. Solver interactions make implicit knowledge explicit to assist the user. For instance, the consequence of a user setting the attribute type of a seat to special is that the solver will automatically set its attribute color to red because of the according constraint – see, e.g., user action 5 in Figure 3. Another typical solver interaction is domain filtering. If, e.g., the nr_passengers was set to 160 as by user action 1 in Figure 3, then the lower bound of length_mm would change to 13334 because of the constraint nr_seats + standing_room/3 4*length_mm/1000 (for the case that nr_seats is 0) and analogously, for the case that length_mm is 20000, the upper bound of nr_seats would be 40 (not more because the lower bound of standing_room must be 120 to achieve the 160 passengers). This knowledge was already implicitly contained in the configuration model of the problem, as described above, but the solver made its consequences explicit, thus creating a distinct benefit to the user. Definition (Solver Interaction). A solver interaction is a set of consequences following a user interaction. Typical solver interactions are:
Set or change the value of a variable not yet set by the user Remove or add a value to a variable domain Create or delete a configuration object because of resource demands by the user (such as the number of seats) Explain a conflict in variable values Propose alternative solutions to a conflict Automatically complete a partial configuration (autocompletion) Many of the solver interactions mentioned above must distinguish whether a configuration parameter has no value or a default value, or whether it has been set by the user or by the solver, because user-set values are typically not allowed to be overwritten by the solver.
With the current rise of data analytics and machine learning techniques and tools, additional types of solver interactions will become state-of-the-art in the future, like recommendation of input values
Set nr_passengers = 160
domain(length_mm) = [13334,20000] domain(nr_seats) = [0,40] domain(standing_room) = [120,160] create handrail with
type = standard
Set nr_seats = 30
domain(length_mm) = [18334,20000] standing_room = 130 create 30 seats with type = standard color = blue
Set standing_room = 140
Set first seat’s type = special
Set handrail’s type = premium
learned from previous configuration sessions or the support of group decisions.
Definition (Interactive Configuration). An interactive configuration is an alternating sequence of user and solver interactions.
An example of a typical configuration dialog between user and configurator is shown in Figure 3.
Having set up the definition of interactive configuration, we can sharpen our research question: To what extent do existing solver frameworks support the different types of solver interactions in interactive configuration? This question is relevant both for companies which sell configurable products/solutions and for solver tool providers (which often originate from academia). Product vendors want to use solvers which cover as many requirements as possible to avoid cumbersome workarounds or proprietary implementations. Tool providers are interested in this question to better focus on those features of their tools that customers really need. Presently, solvers seem to concentrate mainly on optimizing the performance of search for a solution. An indicator for this is the high number of performance challenges and competitions, such as the MiniZinc Challenge2 or the international SAT competitions.3
Our contribution in this paper is the definition of the main requirements on an interactive configurator and a survey to which extent existing, non-commercial solvers fulfill those requirements. However, we do not claim to be exhaustive, neither in requirements nor in evaluated tools. 4
In this section we summarize the most important requirements on a configuration API for constraint solvers with the aim to facilitate interactive product configuration. 4.1
The most basic interaction between the front-end (UI) and the configuration API is to set or unset a configuration parameter. Usually, the configuration domain is modelled in an object-oriented way, where configuration parameters correspond to attributes of configuration objects. Creation and deletion of configuration objects and relationships between them are also fundamental user actions.
Requirement (SetAttributeOrAssociation). The user can set or change an attribute of a configuration object (e.g., the length of a Wagon) or an association link between two configuration objects. The constraint solver model must be updated to be in sync with the front-end model.
Requirement (CreateOrDeleteConfigurationObject). The user can create or delete configuration objects (e.g., create an instance of Handrail). The constraint solver model must be updated to be in sync with the front-end model.
Our assumption to use a 3rd-party constraint solver as underlying
reasoning system makes a transformation from the domain model to
the solver model necessary. Most constraint solvers are optimized in
dealing with flat (i.e., not object-oriented) integer-valued variable
domains. This mapping from the object model to the constraint model
is often cumbersome. Especially the encoding of objects and links
between objects is not trivial (for instance see [
Requirement (ModelTransformation). The configuration API should support mapping between a high-level, object-oriented domain model to the constraint model.
Requirement (ExpressivenessOfConstraintLanguage). Constraints are the central tool for expressing dependencies between configuration objects. The language of the constraint solver must be rich enough to allow the formulation of all necessary integrity/consistency/resource constraints of the configuration domain. 4.2
Default values are an essential means for enhanced usability, because the user is not forced to type in each parameter. In practice, default values are also a means of recommendation, guiding the user to the most common configuration. We distinguish static and dynamic (or computed) default values.
Requirement (StaticDefaults). Static default values are the most common form with built-in support by database systems and programming languages. See, e.g., solver changes after user actions 1 and 2 in Figure 3.
Requirement (DynamicDefaults). Dynamic default values can be computed by almost arbitrary functions, which may use as input other variables of the same configuration (similar to the constraint of Seat in Figure 2) as well as variable values from historic configurations (e.g., most popular value).
Requirement (UnsetVariable). Support Undo and Unset (i.e., set to UNDEF) of an earlier user decision, as, for example, in user action 4 in Figure 3. The user interface shall support overriding the default value as well as reverting to the default value. A “revert to default” capability is essential for good usability, guiding the users back to the paved path from which they got lost.
Requirement (SoftConstraints). An essential property of default values is that they can be overridden by solvers without loss of data. If user-provided input values are regarded as constraints, then default values are soft constraints.
For example, given that the default color of a seat is blue, but special seats are only available in red, then the solver overrides the default color selection with red for all special seats – see user action 5 in Figure 3. Usually this would not be perceived as data loss. On the other hand, if color blue has been chosen by a deliberate user action, and the seat type is changed to “special”, then the configuration is inconsistent. In this case, the user must be notified and prompted for a corrective action as discussed in Section 4.5 – the color must not be changed without prior confirmation by the user. 4.3
In an interactive configuration session, a user may be faced with many possible choices. For example, the number of configuration parameters for which the user can choose a value can be very high, and the number of possible values that can be chosen for a given parameter can also be very high. A user might consecutively set several parameters to values which at the end, possibly after several further steps of interaction between solver and user, do not allow a valid solution compatible to all those choices. The goal of filtering is to offer to the user as few alternatives as possible which do not lead to a valid solution.
Filtering can be used to grey-out values in the UI that are inconsistent with already user-set values (or communicate to the user in another proper way that they are infeasible) so that the user cannot choose them and end up in an invalid solution, e.g., the domains after user actions 1 and 2 in Figure 3.
Hiding those inconsistent values completely from the user, e.g., not showing values < 13334 for length_mm after user action 2 in Figure 3, is often not a good option as it reduces information and flexibility (i.e., the possibility to change decisions) of the user too much because the user would not know that he/she can set length_mm to 12000, for example (see Section 4.5 for more details).
Requirement (Filtering). The solver shall be able to filter invalid values from domains (up to a certain degree of consistency) and to return the current domain of a given variable on request.
The challenge is to efficiently find all inconsistent values and show those for variables in the window that the user currently sees, even for complicated constraints. Besides the computational performance (the problem is NP-hard in general), it may also be difficult to present them to the user in a clear and understandable way – e.g., for an integer number variable show all even values greater than 100 except 2000.
Filtering, which is also found as propagation or constraint
inference in the literature, is one of the techniques which constraint
solving uses to tackle its underlying computational complexity. While
search explores a solution space opened up by variables for which
several possible value assignments exist, propagation deals with
deterministic assignments that are forced by constraints. It may be
interleaved with search or done as a preprocessing step [
Constraint propagation algorithms usually assume the domains of
the variables to be finite. They also assume constraints to be binary,
i.e., to involve exactly two variables. However, all n-ary constraints
can be transformed to binary ones [
After having decided values for “important” variables, a user expects the system to automatically complete the partial solution (i.e., the user-set values) to a valid solution. As an alternative, the commercial configurator Tacton CPQ4 offers a complete solution to the user all the time. In general, the following user actions shall be supported by the API of a constraint solver.
Requirement (ValidSolution). Computation of a valid solution for the current state of the UI, i.e., user-set values are to be treated as fixed. The implementation of this requirement can also be used for checking whether there is a valid solution or not.
Requirement (OptimalSolution). Computation of an optimal solution, preferably with multiple optimization criteria.
User action 6 in Figure 3 is an example for a simple objective function: maximizing the load factor minimizes the length_mm if the nr_passengers is already set.
Requirement (NextSolution). Computation of the next solution: In the case of Requirement (ValidSolution), this should be noticeably distinct from previous solutions so that the user gets the full bandwidth of potential solutions. In the case of Requirement (OptimalSolution), it will be equally good as the previous solutions or – for multiple optimization criteria – another instance in the Pareto front.
ClaferMOO Visualizer5 is an example for an optimizer which supports handling the Pareto front.
Requirement (IncrementalSolving). In an interactive configuration scenario, the user sets one variable after the other – without a predefined order. Performance might be increased if the solver supported incremental solving, i.e., continue with the latest state and not start from scratch after each user input.
4.5
Unless the solver maintains global consistency after each user interaction (which is too expensive especially when fast response times are required, cf. Section 4.3), users can reach a dead end, i.e., a state where they have to revise a decision to be able to find a solution. It may also happen that a conflict is produced because the user deliberately sets a value that has already been filtered away by the solver, like in user action 3 in Figure 3.
The goal of explanation is to assist the user in this situation by suggesting previously made choices to be undone. For a good user experience it is important that these suggestions are understandable, i.e., violated constraints should be explained by descriptive prose. Requirement (Explanation). The solver shall be able to explain in understandable terms why a current state cannot be extended to a valid solution.
Usually we distinguish between background constraints and user
constraints. Background constraints originate from the problem
specification, cannot be changed and are assumed to be correct. Only user
constraints, i.e., constraints originating from user interactions, can be
part of explanations. A subset of user constraints is a conflict if the
problem obtained by combining this subset with background
constraints has no solution. There might be an exponential number of
conflicts that explain the inconsistency of an over-constrained
problem. For this reason, QuickXPlain [
While methods like QuickXPlain focus on conflicts, i.e., on what
has gone wrong, corrective explanations have been proposed to
focus on how to proceed in interactive solving towards a valid solution.
A corrective explanation is more than a diagnosis in the sense that
it does not just point out constraints (i.e., assignments of values to
variables) that have to be retracted, but also proposes alternative
assignments that guarantee to yield a solution [
Requirement (CorrectiveExplanation). The solver shall be able to suggest user actions suitable to correct a current state that cannot be extended to a valid solution. 4.6
Today’s typical enterprise IT landscape is a system of systems with many internal and external interfaces. It must be possible to integrate a newly developed configurator into the existing infrastructure in order to be accepted and used. While the configurator will use other components such as a generic solver or a persistence service to fulfil its tasks, it will also itself be invoked by other components. In order to get widely adopted, a constraint solver should help companies to meet the challenges of integration, or at least it should not impose new ones.
Requirement (LanguageAPI). The constraint solver shall provide a well-documented API to a programming language that is widely accepted and used by companies, such as Java.
Command-line interfaces to the solver are appreciated for testing, but using them for integration is a potential source of problems for integration and long-term maintenance. For this reason, a commandline interface alone is not deemed sufficient.
Requirement (TestSupport). The constraint solver shall support debugging and automated testing.
This can be implemented by compatibility with existing debuggers and testing tools of the host language as well as tool-specific facilities.
Requirement (MaintainanceSupport). The constraint solver shall support long-term maintenance of the configurator.
While the exact requirements cannot be anticipated, contributing factors could be: type-safe API language portable, standardized language for implementation and API use of standard and well-established tools Requirement (NotificationAPI). The constraint solver API shall support a notification concept, such as listeners or callbacks. Given the change of one input variable, which output variables change their values? What previously violated constraints are now fulfilled and vice versa? Requirement (ConstraintLanguage). The constraint solver shall support a well-established language for constraint definition, such as MiniZinc or XCSP.
This requirement is not a replacement but complements Requirement (LanguageAPI).
Requirement (LicenseCompatibility). The license model shall be friendly in order to encourage industrial usage.
Companies are reluctant to adopt open-source components with “sticky” licenses such as GPL, because they fear the legal risks imposed on the own intellectual property. A commercial license at a fair price is more likely to be accepted than a sticky open-source license. In general, industry-friendly licenses such as BSD and MIT style licenses will be appreciated.
Note that this also applies to the components depending on the solver: a dependency on a 3rd-party component with restrictive license conditions is very likely to inhibit the adoption of the solver. As a rule of thumb, all dependencies shall have the same or a more liberal license than the constraint solver component.
Requirement (MinimumDependencies). The list of dependencies (libraries but also other resources) of the solver shall be as short as possible, because each added dependency is also regarded as an additional burden in terms of version management, license and security assessment, and long-term maintenance.
In this section we concentrated on the integration of a constraint solver into a product configurator application via a configuration API. There are many other aspects for integration of configurators, e.g., interfaces to customer relation management (CRM), product data management (PDM), enterprise resource planning (ERP) systems and the like, or generation of quotations and other documents. Despite being considered more important by product managers and consuming much more effort in configurator solutions than product modeling itself, such aspects are out of scope of this work. 5
In this chapter we will investigate how some constraint systems satisfy our proposed requirements for an interactive configuration API. To make our findings easily reproducible we have chosen freely available systems, each representing a different constraint solving paradigm: One offers a standardized constraint modelling language, one is propagation-based, one is a representative of constraint logic programming, and one is SAT-based. All systems allow the definition of classical static constraint problems with variables and constraints and provide basic solving capability (solving, optimization), but they differ in their support for interactive solving. We use a simplified version of the running example to illustrate the different ways to realize user inputs and domain filtering.
We are aware that there are integrated configuration systems on the market that fulfil the requirements posed in this paper at least partially. However, as already mentioned in Section 1, we focus on pure constraint systems that can be integrated into other applications without bearing the risk of vendor-lock-in. 5.1
MiniZinc is a solver-independent constraint modelling language. The MiniZinc system is free and open-source. It includes various command line tools and the MiniZinc IDE for editing and solving MiniZinc models. For solving, the high-level MiniZinc models are compiled into FlatZinc, which is a low-level standard for defining constraint problems supported by most current constraint solvers. One reason for this is the annual MiniZinc challenge, which is the most popular solving competition for constraint solvers. As MiniZinc is a de-facto standard for representing constraint problems, it is a possible solution for a system satisfying Requirement (ConstraintLanguage).
Currently there is no way to directly access the domain filtering capabilities of a solver from MiniZinc. However, users can use solving to emulate domain filtering. For example, to compute the bounds of a variable domain the optimization statement of the original Listing 1 can be replaced with the following solve statements to determine the lower and upper bounds of a variable. # d e t e r m i n e l o w e r bound s o l v e minimize s t a n d i n g _ r o o m ; # d e t e r m i n e u p p e r bound s o l v e maximize s t a n d i n g _ r o o m ;
MiniZinc does not provide default reasoning out of the box, but it can be implemented with optimization or special heuristics all of which can be expressed in MiniZinc. Another option would be to use a system like MiniBrass6 which adds soft constraints and preferences to the MiniZinc system.
To integrate MiniZinc into a software system, various approaches are possible. One such approach consists of manipulating the MiniZinc files programmatically and call the various tools (MiniZinc to FlatZinc compiler, solver executable) via system calls and standard I/O. A more efficient way for manipulating MiniZinc models is using libraries like JMiniZinc7 or PyMzn.8
Another integration option would be to compile the MiniZinc file to FlatZinc and use the FlatZinc parser of the used solver. This has the benefit that solving can be controlled by the solver API, but the downside is that it is not always straightforward to map the low-level FlatZinc constraints and variables to that of the high-level MiniZinc model. This mapping is essential for interactive solving as the user interface must provide feedback in terms of the high-level constraints and variables.
5.2 Choco is a well-established constraint library written in Java. It supports integer, boolean, set and real variables as well as basic constraint expressions and global constraints. Constraint problems are defined using Choco’s Java API.
The following example shows how interactive configuration can
be realized with Choco’s API. A user input is simulated by
posting a constraint containing the assignment selected by the user. The
Choco constraint solver is based on constraint propagation [
,! n r _ p a s s e n g e r s ) . p o s t ( ) ; / / User i n p u t m. a r i t h m ( n r _ s e a t s , " = " , 4 0 ) . p o s t ( ) ; / / Domain f i l t e r i n g m. g e t S o l v e r ( ) . p r o p a g a t e ( ) ; / / Updated domains / / n r _ s e a t s = 40 / / s t a n d i n g _ r o o m = {10 . . 160} / / n r _ p a s s e n g e r s = {50 . . 200}
If the propagation engine encounters an inconsistency, a
ContradictionException is raised. Choco provides an
explanation engine based on [
Choco does not support default values out of the box. One
lightweight implementation of default values is to use search strategies
similar to the approach in [
Choco is implemented in Java and therefore easy to integrate into an enterprise IT landscape. The source code of Choco is available on GitHub9 and pre-built libraries are available for Maven.10 As Choco is open source, missing features can be easily added to the current code base. On the downside the implementation of the features often requires detailed knowledge of the API and must be maintained when the API changes considerably (which has occurred in the past). 5.3
Picat is a logic-based multi-paradigm language well-suited for solving constraint problems. Most that will be said about Picat and interactive constraint solving will also apply to other constraint logic programming systems.
In Picat, constraint programming support is added through the cp module. After importing the cp module, constraint variables can be declared with VAR::DOMAIN. Constraints can be formulated with variable expressions (using special operators preceded with #), predicates and global constraints like all_different etc. The following shows the Picat implementation of the aforementioned example. In Picat every additional constraint expression triggers constraint propagation and the variable domains are adapted accordingly.
10 https://search.maven.org/artifact/org. choco-solver/choco-solver/ P i c a t > NR_SEATS : : 0 . . 8 0 ,
STANDING_ROOM: : 0 . . 2 0 0 , NR_PASSENGERS : : 50 . . 2 0 0 , NR_SEATS + STANDING_ROOM #= NR_PASSENGERS ,
NR_SEATS #= 4 0 . / / o u t p u t : / / NR_SEATS = 40 / / STANDING_ROOM = DV_015c90_10 . . 160 / / NR_PASSENGERS = DV_015d28_50 . . 200
Using the concept of action rules, it is possible to get notified of domain changes of constraint variables. Action rules have the form Head, Cond, {Event} => Body. Examples for events are: ins(X), when a variable gets instantiated bound(X), when the bounds of a variable change dom(X,T), when a value T gets excluded from the domain of X Therefore it is possible to trace all variable domains that have been effected by a user interaction, cf. Requirement (NotificationAPI).
Picat programs can be executed as shell scripts. Picat allows to define predicates by C functions. Unfortunately, it is currently not possible to call Picat from C, so integration must be done via standard I/O. 5.4
As an example of a constraint solver based on a non-constraint propagation paradigm we have chosen the SAT-based Google CP-SAT Solver, which is part of Google OR-Tools.11
As the CP-SAT Solver is SAT-based, it does not provide an API for accessing the current domain of variables. Therefore it is best treated as a black-box solver, i.e., by defining the constraint problem and solving it. Domain filtering can be simulated by calling the solver for a specific domain value or, as in the example below for bounded domains, calling minimize/maximize for a variable to compute its lower and upper bound. In the example the lower bound of the variable standing_room is computed. Of course this strategy only works for constraint problems where efficient solving is possible, otherwise the response time of the interactive system would deteriorate. from o r t o o l s . s a t . p y t h o n import cp_model model = cp_model . CpModel ( ) n r _ s e a t s = model . NewIntVar ( 0 , 8 0 , " " ) s t a n d i n g _ r o o m = model . NewIntVar ( 0 , 2 0 0 , " " ) n r _ p a s s e n g e r s = model . NewIntVar ( 5 0 , 2 0 0 , " " ) model . Add ( sum ( [ n r _ s e a t s , s t a n d i n g _ r o o m ] ) == n r _ p a s s e n g e r s ) u i = model . NewIntVar ( 4 0 , 4 0 , " " ) model . Add ( n r _ s e a t s == u i ) # S i m u l a t e domain f i l t e r i n g : # C a l l i n g m i n i m i z e f o r a v a r i a b l e # f i n d s t h e l o w e r bound model . Minimize ( s t a n d i n g _ r o o m ) s o l v e r = cp_model . C p S o l v e r ( ) s t a t u s = s o l v e r . S o l v e ( model ) p r i n t ( s o l v e r . Value ( s t a n d i n g _ r o o m ) ) # O u t p u t : 10
The CP-SAT solver is written in C++, but via SWIG12 also an API in Java, C# and Python is provided, which makes it one of the few constraint solvers available in Python. Regarding Requirement (LanguageAPI) this provides a very good integrability for the basic functionality of the solver, although some special features can only be accessed through the C++ API. 11 https://github.com/google/or-tools/ 12 http://www.swig.org/
This brief survey of currently available constraint solvers is by no means complete. Its main purpose was to illustrate the diversity of systems available for constraint solving and how each has particular strengths and weaknesses when it comes to satisfying the proposed requirements for interactive solving.
The focus of most constraint systems is on modelling and efficient solving. Only few solvers contain special features for interactive solving. Even in the case of solvers based on constraint propagation, the main purpose of constraint propagation is to assist the solver during search. Another indicator that features like domain filtering are sometimes less important than performance is the fact that Google recommends to use the new SAT-based constraint solver instead of the legacy constraint propagation based solver contained in Google’s OR-Tools due to performance.13 Only one system (Picat) provides a documented mechanism how to get notified about domain changes of constraints variables. Some solvers like Choco include an explanation engine. None of the solvers we are aware of supports default reasoning out of the box. All in all this supports our initial suspicion that interactive solving is a neglected aspect of constraint systems.
Of course, the decision which solver to use is complex and will not be driven by interactive features alone. Most of the interactive features can be implemented (although sometimes less efficiently) by treating the solver as a black box.
As can be seen even in our simple example, it is not trivial to translate a constraint problem from one solver to another. To avoid the risk of getting locked-in to a specific solver API, it might be better to use a solver-independent constraint modelling language like MiniZinc. 6
Real-world configuration problems are often interactive in nature, i.e., they include the user as an essential factor in the configuration process. To solve configuration problems, constraint satisfaction is often used as an underlying reasoning system. In this paper, we have made two contributions: First, we have proposed a set of requirements that a constraint solver should fulfil to support interactive configuration. Second, we have presented the results of a small survey covering a selected set of non-commercial off-the-shelf constraint systems.
Our findings show that interactive aspects of configuration are neglected by most constraint systems. They also show that the landscape of available system is highly diverse and that each solver has its own strengths and weaknesses when it comes to satisfying the requirements proposed in this work.
This is preliminary work. Neither our list of user and solver interactions nor our list of requirements nor our survey is exhaustive. We focused here on those requirements and tools that we experienced as most important in our daily work on industrial product configuration. Future work should extend this study to cover more requirements (like aspects of guided selling, prediction of default values, recommender features) and more constraint systems. Assessment of each constraint system shall be done in a more systematic and complete way and summarized in tables.
We invite the configuration and constraints communities to propose implementations of constraint systems that are suitable to support interactive configuration. 13 https://developers.google.com/optimization/cp/cp_ solver