=Paper=
{{Paper
|id=Vol-2467/paper-12
|storemode=property
|title=Constraint Solver Requirements for Interactive Configuration
|pdfUrl=https://ceur-ws.org/Vol-2467/paper-12.pdf
|volume=Vol-2467
|authors=Andreas Falkner,Alois Haselböck,Gerfried Krames,Gottfried Schenner,Richard Taupe
|dblpUrl=https://dblp.org/rec/conf/confws/FalknerHKST19
}}
==Constraint Solver Requirements for Interactive Configuration==
https://ceur-ws.org/Vol-2467/paper-12.pdf
Constraint Solver Requirements
for Interactive Configuration
Andreas Falkner and Alois Haselböck and Gerfried Krames and Gottfried Schenner and Richard Taupe1
Abstract. Interactive configuration includes the user as an essen- parameter, propagation of information, checking the consistency for
tial factor in the configuration process. The main two components of a value, checking a configuration, autocompletion, explanation, and
an interactive configurator are a user interface on the front-end and backtracking.
a knowledge representation and reasoning (KRR) framework on the Matthieu Queva et al. describe in [17] requirements on interac-
back-end. In this paper we discuss important requirements for the tive configurators mainly from the modelling perspective and call
underlying KRR system to support an interactive configuration pro- for high-level, expressive languages like UML or SysML. They also
cess while focusing on classical constraint satisfaction as one of the mention constraint modelling as an important aspect of configura-
most prominent KRR technologies for configuration problems. We tion. From the viewpoint of constraint reasoning, Jeppe Madsen iden-
evaluate several freely available constraint systems with respect to tified three fundamental interactivity operations in his master the-
the identified requirements for interactive configuration and observe sis [14]: add constraint, remove constraint, and restoration.
that many of those requirements are not well supported. 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
1 INTRODUCTION a component. An alternative would be to implement a special UI for
Constraint satisfaction [18] is often used as an underlying reason- an integrated configuration system such as a commercial CPQ tool
ing system for product configuration problems [12]. Product config- or sales configurator suite, but that bears the risk of vendor-lock-in.
uration is usually an interactive task: Iteratively, the user makes a Figure 1 gives an overview of the addressed scenario: Users in-
decision and the configurator computes the consequences of this de- teract with the configurator to achieve their goals, thus putting chal-
cision. In his PhD thesis [6], David Ferrucci summarized the inherent lenges to user interface functionality. Those challenges pose reason-
interactivity of configurators as follows: ing interaction requirements on the API of the used constraint solver.
The solver is an off-the-shelf product (open-source or commercial)
“Interactive configuration is a view of the configuration task and has a general API, partly dedicated to configuration problems.
which includes the user as an essential component of a dy- Together with a domain-specific product model (or knowledge base,
namic process. The interactive configurator is designed to as- KB), it forms the KRR component. This back-end is called by the
sist the user in an interactive and incremental exploration of the control component which first hands over product model and user-
configuration space. It may guide or advise the user’s decision set values for decision variables from the UI to the API and then
making but it must communicate requirements or inconsisten- sends the solver results back to the UI.
cies effected by the constraints in response to the user’s choices.
This feedback helps the user to refine the configuration space
toward a satisfying solution.
The key component of an interactive configurator is the con- user interaction
straint manager which is responsible for incrementally main- User
taining the relationship between choices and constraint viola- Interface
Configurator
tions. [. . . ] The requirement to deliver meaningful and timely reasoner
interaction
feedback imposes significant demands on the flexibility, effi- Control Configuration API
ciency and explainability of constraint management.”
Pieter van Hertum et al. studied in [9] how the knowledge base Product Model Constraint Solver
paradigm – the separation of concerns between information and
problem solving – could hold in the context of interactive config-
uration. They identified a set of subtasks that overlaps well with
Figure 1. Components of an interactive configurator
the set of requirements we propose in this paper in Section 4: Ac-
quiring information from the user, generating consistent values for a
The configurator shall help a user to configure a product accord-
1 Siemens AG Österreich, Corporate Technology, Vienna, Austria
ing to his/her needs and in full compliance to the product model. The
andreas.a.falkner@siemens.com, alois.haselboeck@siemens.com,
gerfried.krames@siemens.com, gottfried.schenner@siemens.com,
user expects the configurator to show all necessary decisions (vari-
richard.taupe@siemens.com ations) in a clear and well-arranged way, to highlight or preset the
Author names are ordered alphabetically. “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 the UML classes to arrays of variables and some other implemen-
(preferably instantaneously) to user inputs. tation decisions, e.g., special handling of the “dynamic” parts, i.e.,
The remainder of this paper is organized as follows: In Section 2, number of seats dependent on the expected load and length – see the
an example for interactive configuration is introduced. In Section 3, MiniZinc program in Listing 1.
we give a problem definition of interactive configuration. We define
the requirements for an interactive configuration API in Section 4 Listing 1. MiniZinc program for the Wagon example
and investigate in Section 5 how some typical constraint solvers sat- % C o n s t a n t s , Domains
i n t : m i n _ l e n g t h = 10000 ;
isfy these requirements. We conclude the paper in Section 6 with a i n t : m a x _ l e n g t h = 20000 ;
summary and future work. 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 , r e d , w h i t e , n o C o l o r } ;
2 EXAMPLE enum Type = { s t a n d a r d , premium , s p e c i a l , noType } ;
% Wagon
We show the challenges of interactive configuration in a small ex- var m i n _ l e n g t h . . m a x _ l e n g t h : length_mm ;
ample for a configurable product with components that can occur 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 ;
multiple times (similar to generative constraint satisfaction [7] or 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 ;
cardinality-based feature modelling [3]).
A Metro train wagon has as configurable attributes the size (length % Seats
a r r a y [ 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 ;
in millimetres: 10000..20000) and the expected load (number of pas- a r r a y [ 1 . . m a x _ s e a t s ] o f var Type : s e a t _ t y p e ;
sengers: 50..200) which can be realized as seats or standing room. As % Handrail
components we consider only seats (max. 4 per meter of length) and var Type : h a n d r a i l _ t y p e ;
handrails, and their number is configurable. % C o n s t r a i n numbers
constraint n r _ s e a t s + standing_room = nr_passengers ;
There is at most one handrail in a wagon (mandatory if there is 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 <=
standing room) and it has a configurable type: “standard” or “pre- ,→ length_mm * 4 / 1 0 0 0 ;
mium”. % 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 ;
A single seat consumes standing room for 3 persons and has as constraint handrail_type != special ;
configurable attributes the type (“standard”, “premium”, “special”) 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
and the color (“blue”, “red”, “white”). The type is constrained such ,→ 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 ] ) ;
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 % 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 )
seats which have to be “red”. ,→ ( s e a t _ c o l o r [ i ] = n o C o l o r ) ;
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 )
Users expect the following (static) default values: type = standard, ,→ ( s e a t _ t y p e [ i ] = noType ) ;
color = blue. Furthermore, they prefer to use all available space (as c o n s t r a i n t f o r a l l ( i , j i n 1 . . n r _ s e a t s where i < j )
,→ ( s e a t _ t y p e [ i ] ! = s p e c i a l / \ s e a t _ t y p e [ j ] ! =
defined by the length) for passengers (i.e., maximize the load factor). ,→ s p e c i a l −> s e a t _ t y p e [ i ] = s e a t _ t y p e [ j ] ) ;
c o n s t r a i n t f o r a l l ( i , j i n 1 . . n r _ s e a t s where i < j )
,→ ( s e a t _ t y p e [ i ] ! = s p e c i a l / \ s e a t _ t y p e [ j ] ! =
Wagon ,→ s p e c i a l −> s e a t _ c o l o r [ i ] = s e a t _ c o l o r [ j ] ) ;
constraint f o r a l l ( i in 1 . . n r _ s e a t s ) ( s e a t _ t y p e [ i ] =
length_mm: 10000...20000 ,→ s p e c i a l −> s e a t _ c o l o r [ i ] = r e d ) ;
nr_passengers: 50..200 % 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 )
nr_seats: 0..200 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
standing_room: 0..200
nr_seats + standing_room = nr_passengers
nr_seats + standing_room/3 ≤
4*length_mm/1000 3 PROBLEM DEFINITION
nr_seats = count(Seat)
standing_room>0 → count(Handrail)=1 The main two parties in interactive configuration are the user and
all-equal-type()
all-equal-color()
the configurator. The user’s goal is to configure a product such that
maximize nr_passengers/length_mm it is a valid and complete product variant that meets all his/her in-
dividual requirements. The configurator is a digital companion that
0..1 0..80 supports the configuration process by deriving consequences of the
Handrail Seat user’s choices and by assisting to avoid and resolve conflicts.
type: {standard, premium} type: {standard, premium, special} The simplest type of a user interaction is to set the value of a
color: {blue, red, white} configuration parameter. This can be seen as answering a question
type=special → color=red that the configuration tool asked. Example: For how many passen-
gers should the wagon provide seats? Of course, the user should also
Figure 2. Class diagram of the Wagon example. Default values are be able to withdraw his/her decision, which corresponds to unsetting
underlined. Wagon.all-equal-type() stands for a constraint that all sub-parts a configuration parameter. The value of the parameter will then be
must have the same type except for special. Wagon.all-equal-color() stands either undefined or the default value or set by solving.
for a constraint that all associated seats (except if type=special) must have In most non-trivial configuration problems, a dynamic number of
the same color. configuration objects plays an important role. Some authors of this
paper have developed configurators for large industrial products for
Figure 2 shows a UML class diagram for this sample specification, more than 25 years and always faced problems that could not be rep-
including pseudo code for all constraints. A modelling in a standard resented as simple, static lists of configuration parameters (see [4]).
constraint solver is more verbose because it requires the mapping of Therefore, another important type of user interaction is the creation
and deletion of configuration objects. In the example problem in Sec-
tion 2, seats are configuration objects whose number is not known User action 1:
beforehand, and where each seat can be configured individually (seat Set nr_passengers = 160
Solver changes:
color and type). Typically, there are two different ways how the user domain(length_mm) = [13334,20000]
manipulates the number of individual configuration objects in the domain(nr_seats) = [0,40]
user interface: either by creating them one by one, or by specifying domain(standing_room) = [120,160]
the number of objects and letting the configuration tool create the create handrail with
type = standard
individual objects. But in both cases, the result is a set of configu-
ration objects whose number was not known beforehand and whose User action 2:
properties can be configured further. This is not the case for the rep- Set nr_seats = 30
Solver changes:
resentation of standing_room in our example. The user can set only domain(length_mm) = [18334,20000]
the capacity as a number but no further individual properties. Thus, standing_room = 130
standing room need not to be modelled as configuration objects in create 30 seats with
our example. type = standard
color = blue
Definition (User Interaction). The main types of user interactions User action 3:
in interactive configuration are: (i) create configuration object, (ii) Set standing_room = 140
delete configuration object, (iii) set/unset configuration object at- Solver proposes alternative conflict resolutions:
tribute, (iv) set/unset association between configuration objects. 1. nr_passengers = 170
2. nr_seats = 20
We are aware that various approaches to interactive configuration User action 4:
may define the list of main types of user interactions differently. For Unset nr_seats (accept proposal 2)
example, structure-based configuration considers the following types Solver changes:
of user interaction: parametrization, decomposition, integration, and domain(length_mm) = [16667,20000]
nr_seats = 20
specialization [10]. Due to the limited scope of this paper, we focus delete 10 seats
on types of user interaction that are most relevant in our experience.
User interactions change the state of the configuration by mak- User action 5:
ing decisions. Solver interactions make implicit knowledge explicit Set first seat’s type = special
Solver changes:
to assist the user. For instance, the consequence of a user set- first seat’s color = red
ting the attribute type of a seat to special is that the solver
will automatically set its attribute color to red because of the User action 6:
Autocomplete (with optimization)
according constraint – see, e.g., user action 5 in Figure 3. An- Solver changes:
other typical solver interaction is domain filtering. If, e.g., the length_mm = 16667 (maximize load factor)
nr_passengers was set to 160 as by user action 1 in Fig-
ure 3, then the lower bound of length_mm would change to 13334 User action 7:
Set handrail’s type = premium
because of the constraint nr_seats + standing_room/3 ≤ Solver changes:
4*length_mm/1000 (for the case that nr_seats is 0) and anal- for all seats except first, type = premium
ogously, 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). Figure 3. Example of a configuration dialog for the configuration problem
This knowledge was already implicitly contained in the configura- in Section 2
tion model of the problem, as described above, but the solver made
its consequences explicit, thus creating a distinct benefit to the user. learned from previous configuration sessions or the support of group
decisions.
Definition (Solver Interaction). A solver interaction is a set of con-
sequences following a user interaction. Typical solver interactions Definition (Interactive Configuration). An interactive configuration
are: is an alternating sequence of user and solver interactions.
• Set or change the value of a variable not yet set by the user
• Remove or add a value to a variable domain An example of a typical configuration dialog between user and
• Create or delete a configuration object because of resource de- configurator is shown in Figure 3.
mands by the user (such as the number of seats) Having set up the definition of interactive configuration, we can
• Explain a conflict in variable values sharpen our research question: To what extent do existing solver
• Propose alternative solutions to a conflict frameworks support the different types of solver interactions in in-
• Automatically complete a partial configuration (autocompletion) teractive configuration? This question is relevant both for compa-
nies which sell configurable products/solutions and for solver tool
Many of the solver interactions mentioned above must distinguish providers (which often originate from academia). Product vendors
whether a configuration parameter has no value or a default value, or want to use solvers which cover as many requirements as possible
whether it has been set by the user or by the solver, because user-set to avoid cumbersome workarounds or proprietary implementations.
values are typically not allowed to be overwritten by the solver. Tool providers are interested in this question to better focus on those
With the current rise of data analytics and machine learning tech- features of their tools that customers really need. Presently, solvers
niques and tools, additional types of solver interactions will become seem to concentrate mainly on optimizing the performance of search
state-of-the-art in the future, like recommendation of input values for a solution. An indicator for this is the high number of perfor-
mance challenges and competitions, such as the MiniZinc Challenge2 Requirement (StaticDefaults). Static default values are the most
or the international SAT competitions.3 common form with built-in support by database systems and pro-
Our contribution in this paper is the definition of the main require- gramming languages. See, e.g., solver changes after user actions 1
ments on an interactive configurator and a survey to which extent ex- and 2 in Figure 3.
isting, non-commercial solvers fulfill those requirements. However,
Requirement (DynamicDefaults). Dynamic default values can be
we do not claim to be exhaustive, neither in requirements nor in eval-
computed by almost arbitrary functions, which may use as input
uated tools.
other variables of the same configuration (similar to the constraint
of Seat in Figure 2) as well as variable values from historic configu-
4 REQUIREMENTS rations (e.g., most popular value).
In this section we summarize the most important requirements on Requirement (UnsetVariable). Support Undo and Unset (i.e., set to
a configuration API for constraint solvers with the aim to facilitate UNDEF) of an earlier user decision, as, for example, in user action
interactive product configuration. 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
4.1 Basic interactions the paved path from which they got lost.
The most basic interaction between the front-end (UI) and the config-
Requirement (SoftConstraints). An essential property of default
uration API is to set or unset a configuration parameter. Usually, the
values is that they can be overridden by solvers without loss of data.
configuration domain is modelled in an object-oriented way, where
If user-provided input values are regarded as constraints, then de-
configuration parameters correspond to attributes of configuration
fault values are soft constraints.
objects. Creation and deletion of configuration objects and relation-
ships between them are also fundamental user actions. For example, given that the default color of a seat is blue, but spe-
cial seats are only available in red, then the solver overrides the de-
Requirement (SetAttributeOrAssociation). The user can set or
fault color selection with red for all special seats – see user action 5
change an attribute of a configuration object (e.g., the length of a
in Figure 3. Usually this would not be perceived as data loss. On the
Wagon) or an association link between two configuration objects.
other hand, if color blue has been chosen by a deliberate user action,
The constraint solver model must be updated to be in sync with the
and the seat type is changed to “special”, then the configuration is
front-end model.
inconsistent. In this case, the user must be notified and prompted for
Requirement (CreateOrDeleteConfigurationObject). The user can a corrective action as discussed in Section 4.5 – the color must not
create or delete configuration objects (e.g., create an instance of be changed without prior confirmation by the user.
Handrail). The constraint solver model must be updated to be in sync
with the front-end model. 4.3 Filtering
rd
Our assumption to use a 3 -party constraint solver as underlying In an interactive configuration session, a user may be faced with
reasoning system makes a transformation from the domain model to many possible choices. For example, the number of configuration
the solver model necessary. Most constraint solvers are optimized in parameters for which the user can choose a value can be very high,
dealing with flat (i.e., not object-oriented) integer-valued variable do- and the number of possible values that can be chosen for a given pa-
mains. This mapping from the object model to the constraint model rameter can also be very high. A user might consecutively set several
is often cumbersome. Especially the encoding of objects and links parameters to values which at the end, possibly after several further
between objects is not trivial (for instance see [20]). steps of interaction between solver and user, do not allow a valid so-
lution compatible to all those choices. The goal of filtering is to offer
Requirement (ModelTransformation). The configuration API to the user as few alternatives as possible which do not lead to a valid
should support mapping between a high-level, object-oriented do- solution.
main model to the constraint model. Filtering can be used to grey-out values in the UI that are incon-
sistent with already user-set values (or communicate to the user in
Requirement (ExpressivenessOfConstraintLanguage). Constraints another proper way that they are infeasible) so that the user cannot
are the central tool for expressing dependencies between configu- choose them and end up in an invalid solution, e.g., the domains after
ration objects. The language of the constraint solver must be rich user actions 1 and 2 in Figure 3.
enough to allow the formulation of all necessary integrity/consisten- Hiding those inconsistent values completely from the user, e.g.,
cy/resource constraints of the configuration domain. 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 flex-
4.2 Preferred and default solutions ibility (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
Default values are an essential means for enhanced usability, because 12000, for example (see Section 4.5 for more details).
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 Requirement (Filtering). The solver shall be able to filter invalid
most common configuration. We distinguish static and dynamic (or values from domains (up to a certain degree of consistency) and to
computed) default values. return the current domain of a given variable on request.
2 https://www.minizinc.org/challenge.html The challenge is to efficiently find all inconsistent values and show
3 https://www.satcompetition.org/
those for variables in the window that the user currently sees, even
for complicated constraints. Besides the computational performance 4.5 Explanation
(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 Unless the solver maintains global consistency after each user inter-
integer number variable show all even values greater than 100 except action (which is too expensive especially when fast response times
2000. are required, cf. Section 4.3), users can reach a dead end, i.e., a state
Filtering, which is also found as propagation or constraint infer- where they have to revise a decision to be able to find a solution. It
ence in the literature, is one of the techniques which constraint solv- may also happen that a conflict is produced because the user delib-
ing uses to tackle its underlying computational complexity. While erately sets a value that has already been filtered away by the solver,
search explores a solution space opened up by variables for which like in user action 3 in Figure 3.
several possible value assignments exist, propagation deals with de- The goal of explanation is to assist the user in this situation by
terministic assignments that are forced by constraints. It may be in- suggesting previously made choices to be undone. For a good user
terleaved with search or done as a preprocessing step [2, 19]. experience it is important that these suggestions are understandable,
Constraint propagation algorithms usually assume the domains of i.e., violated constraints should be explained by descriptive prose.
the variables to be finite. They also assume constraints to be binary, Requirement (Explanation). The solver shall be able to explain in
i.e., to involve exactly two variables. However, all n-ary constraints understandable terms why a current state cannot be extended to a
can be transformed to binary ones [2, 19]. If a CSP (in which some valid solution.
domains may already have been tightened down) can be extended to
a solution, it is called globally consistent. Since global consistency Usually we distinguish between background constraints and user
is very expensive to maintain, various forms of local consistency – constraints. Background constraints originate from the problem spec-
mainly arc consistency – are used in practice [2, 19]. Another ap- ification, cannot be changed and are assumed to be correct. Only user
proach is to compile a CSP into a data structure that can maintain constraints, i.e., constraints originating from user interactions, can be
global consistency, such as an automaton [1] or a binary decision part of explanations. A subset of user constraints is a conflict if the
diagram (BDD) [15]. problem obtained by combining this subset with background con-
straints has no solution. There might be an exponential number of
conflicts that explain the inconsistency of an over-constrained prob-
4.4 Solving lem. For this reason, QuickXPlain [11] can be used to compute pre-
After having decided values for “important” variables, a user expects ferred explanations. Conflict diagnosis like QuickXPlain can be com-
the system to automatically complete the partial solution (i.e., the bined with a hitting-set algorithm to compute minimal diagnoses,
user-set values) to a valid solution. As an alternative, the commercial i.e., minimal sets of faulty constraints. A diagnosis is a subset of user
configurator Tacton CPQ4 offers a complete solution to the user all constraints so that the problem becomes consistent when this subset
the time. In general, the following user actions shall be supported by is removed from it [5].
the API of a constraint solver. While methods like QuickXPlain focus on conflicts, i.e., on what
has gone wrong, corrective explanations have been proposed to fo-
Requirement (ValidSolution). Computation of a valid solution for cus on how to proceed in interactive solving towards a valid solution.
the current state of the UI, i.e., user-set values are to be treated as A corrective explanation is more than a diagnosis in the sense that
fixed. The implementation of this requirement can also be used for it does not just point out constraints (i.e., assignments of values to
checking whether there is a valid solution or not. variables) that have to be retracted, but also proposes alternative as-
signments that guarantee to yield a solution [16].
Requirement (OptimalSolution). Computation of an optimal solu-
tion, preferably with multiple optimization criteria. Requirement (CorrectiveExplanation). The solver shall be able to
suggest user actions suitable to correct a current state that cannot be
User action 6 in Figure 3 is an example for a simple objective
extended to a valid solution.
function: maximizing the load factor minimizes the length_mm if
the nr_passengers is already set.
4.6 Integrability
Requirement (NextSolution). Computation of the next solution:
In the case of Requirement (ValidSolution), this should be no- Today’s typical enterprise IT landscape is a system of systems with
ticeably distinct from previous solutions so that the user gets many internal and external interfaces. It must be possible to integrate
the full bandwidth of potential solutions. In the case of Require- a newly developed configurator into the existing infrastructure in or-
ment (OptimalSolution), it will be equally good as the previous solu- der to be accepted and used. While the configurator will use other
tions or – for multiple optimization criteria – another instance in the components such as a generic solver or a persistence service to fulfil
Pareto front. its tasks, it will also itself be invoked by other components. In order
to get widely adopted, a constraint solver should help companies to
ClaferMOO Visualizer5 is an example for an optimizer which sup- meet the challenges of integration, or at least it should not impose
ports handling the Pareto front. new ones.
Requirement (IncrementalSolving). In an interactive configuration Requirement (LanguageAPI). The constraint solver shall provide
scenario, the user sets one variable after the other – without a prede- a well-documented API to a programming language that is widely
fined order. Performance might be increased if the solver supported accepted and used by companies, such as Java.
incremental solving, i.e., continue with the latest state and not start
Command-line interfaces to the solver are appreciated for testing,
from scratch after each user input.
but using them for integration is a potential source of problems for
4 http://www.tacton.com/tacton-cpq/
integration and long-term maintenance. For this reason, a command-
5 http://www.clafer.org/p/software.html
line interface alone is not deemed sufficient.
Requirement (TestSupport). The constraint solver shall support de- To make our findings easily reproducible we have chosen freely
bugging and automated testing. available systems, each representing a different constraint solving
paradigm: One offers a standardized constraint modelling language,
This can be implemented by compatibility with existing debug- one is propagation-based, one is a representative of constraint logic
gers and testing tools of the host language as well as tool-specific programming, and one is SAT-based. All systems allow the definition
facilities. of classical static constraint problems with variables and constraints
Requirement (MaintainanceSupport). The constraint solver shall and provide basic solving capability (solving, optimization), but they
support long-term maintenance of the configurator. differ in their support for interactive solving. We use a simplified ver-
sion of the running example to illustrate the different ways to realize
While the exact requirements cannot be anticipated, contributing user inputs and domain filtering.
factors could be: We are aware that there are integrated configuration systems on
the market that fulfil the requirements posed in this paper at least
• type-safe API language partially. However, as already mentioned in Section 1, we focus on
• portable, standardized language for implementation and API pure constraint systems that can be integrated into other applications
• use of standard and well-established tools without bearing the risk of vendor-lock-in.
Requirement (NotificationAPI). The constraint solver API shall
support a notification concept, such as listeners or callbacks. Given 5.1 MiniZinc
the change of one input variable, which output variables change their
MiniZinc is a solver-independent constraint modelling language.
values? What previously violated constraints are now fulfilled and
The MiniZinc system is free and open-source. It includes various
vice versa?
command line tools and the MiniZinc IDE for editing and solv-
Requirement (ConstraintLanguage). The constraint solver shall ing MiniZinc models. For solving, the high-level MiniZinc mod-
support a well-established language for constraint definition, such els are compiled into FlatZinc, which is a low-level standard for
as MiniZinc or XCSP. defining constraint problems supported by most current constraint
solvers. One reason for this is the annual MiniZinc challenge, which
This requirement is not a replacement but complements Require- is the most popular solving competition for constraint solvers. As
ment (LanguageAPI). MiniZinc is a de-facto standard for representing constraint prob-
lems, it is a possible solution for a system satisfying Require-
Requirement (LicenseCompatibility). The license model shall be
ment (ConstraintLanguage).
friendly in order to encourage industrial usage.
Currently there is no way to directly access the domain filtering ca-
Companies are reluctant to adopt open-source components with pabilities of a solver from MiniZinc. However, users can use solving
“sticky” licenses such as GPL, because they fear the legal risks im- to emulate domain filtering. For example, to compute the bounds of a
posed on the own intellectual property. A commercial license at a variable domain the optimization statement of the original Listing 1
fair price is more likely to be accepted than a sticky open-source li- can be replaced with the following solve statements to determine the
cense. In general, industry-friendly licenses such as BSD and MIT lower and upper bounds of a variable.
style licenses will be appreciated. # d e t e r m i n e l o w e r bound
Note that this also applies to the components depending on the s o l v e minimize s t a n d i n g _ r o o m ;
solver: a dependency on a 3rd -party component with restrictive li- # 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 ;
cense 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 MiniZinc does not provide default reasoning out of the box, but
liberal license than the constraint solver component. it can be implemented with optimization or special heuristics all of
which can be expressed in MiniZinc. Another option would be to use
Requirement (MinimumDependencies). The list of dependencies
a system like MiniBrass6 which adds soft constraints and preferences
(libraries but also other resources) of the solver shall be as short
to the MiniZinc system.
as possible, because each added dependency is also regarded as an
To integrate MiniZinc into a software system, various approaches
additional burden in terms of version management, license and secu-
are possible. One such approach consists of manipulating the Mini-
rity assessment, and long-term maintenance.
Zinc files programmatically and call the various tools (MiniZinc to
In this section we concentrated on the integration of a constraint FlatZinc compiler, solver executable) via system calls and standard
solver into a product configurator application via a configuration I/O. A more efficient way for manipulating MiniZinc models is using
API. There are many other aspects for integration of configurators, libraries like JMiniZinc7 or PyMzn.8
e.g., interfaces to customer relation management (CRM), product Another integration option would be to compile the MiniZinc file
data management (PDM), enterprise resource planning (ERP) sys- to FlatZinc and use the FlatZinc parser of the used solver. This has
tems and the like, or generation of quotations and other documents. the benefit that solving can be controlled by the solver API, but the
Despite being considered more important by product managers and downside is that it is not always straightforward to map the low-level
consuming much more effort in configurator solutions than product FlatZinc constraints and variables to that of the high-level MiniZinc
modeling itself, such aspects are out of scope of this work. 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 SURVEY OF EXISTING SOLVERS
6 https://isse.uni-augsburg.de/software/minibrass
In this chapter we will investigate how some constraint systems sat- 7 https://github.com/siemens/JMiniZinc
8 http://paolodragone.com/pymzn/
isfy our proposed requirements for an interactive configuration API.
5.2 Choco P i c a t > NR_SEATS : : 0 . . 8 0 ,
STANDING_ROOM: : 0 . . 2 0 0 ,
NR_PASSENGERS : : 50 . . 2 0 0 ,
Choco is a well-established constraint library written in Java. It sup- NR_SEATS + STANDING_ROOM #= NR_PASSENGERS ,
ports integer, boolean, set and real variables as well as basic con- NR_SEATS #= 4 0 .
/ / output :
straint expressions and global constraints. Constraint problems are / / NR_SEATS = 40
/ / STANDING_ROOM = DV_015c90_10 . . 160
defined using Choco’s Java API. / / NR_PASSENGERS = DV_015d28_50 . . 200
The following example shows how interactive configuration can
be realized with Choco’s API. A user input is simulated by post- Using the concept of action rules, it is possible to get notified of
ing a constraint containing the assignment selected by the user. The domain changes of constraint variables. Action rules have the form
Choco constraint solver is based on constraint propagation [13]. Con- Head, Cond, {Event} => Body. Examples for events are:
straint propagation can not only be utilized during solving, but also
to compute the current domains of the constraint variables. The ex- • ins(X), when a variable gets instantiated
ample shows how variable domains are narrowed down by propaga- • bound(X), when the bounds of a variable change
tion after calling Solver.propagate(), i.e., Choco satisfies Require- • dom(X,T), when a value T gets excluded from the domain of X
ment (Filtering).
/ / I n i t i a l domains :
Therefore it is possible to trace all variable domains that have been
/ / n r _ s e a t s = {0 . . 80} effected by a user interaction, cf. Requirement (NotificationAPI).
/ / s t a n d i n g _ r o o m = { 0 . . 200}
/ / n r _ p a s s e n g e r s = { 50 . . 200} Picat programs can be executed as shell scripts. Picat allows to
/ / post constraint define predicates by C functions. Unfortunately, it is currently not
m. a r i t h m ( 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 ) . p o s t ( ) ; possible to call Picat from C, so integration must be done via standard
/ / User i n p u t I/O.
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 d o m a i n s 5.4 CP-SAT Solver
/ / 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} As an example of a constraint solver based on a non-constraint prop-
agation paradigm we have chosen the SAT-based Google CP-SAT
If the propagation engine encounters an inconsistency, a
Solver, which is part of Google OR-Tools.11
ContradictionException is raised. Choco provides an expla-
As the CP-SAT Solver is SAT-based, it does not provide an API
nation engine based on [22] for generating explanations for contra-
for accessing the current domain of variables. Therefore it is best
dictions found during solving. Unfortunately, the explanation engine
treated as a black-box solver, i.e., by defining the constraint prob-
is by default not active during propagation. As an alternative a solver-
lem and solving it. Domain filtering can be simulated by calling the
independent algorithm like QuickXPlain can be adapted for Choco.
solver for a specific domain value or, as in the example below for
Choco does not support default values out of the box. One light-
bounded domains, calling minimize/maximize for a variable to com-
weight implementation of default values is to use search strategies
pute its lower and upper bound. In the example the lower bound of
similar to the approach in [8].
the variable standing_room is computed. Of course this strategy
Choco is implemented in Java and therefore easy to integrate into
only works for constraint problems where efficient solving is pos-
an enterprise IT landscape. The source code of Choco is available on
sible, otherwise the response time of the interactive system would
GitHub9 and pre-built libraries are available for Maven.10 As Choco
deteriorate.
is open source, missing features can be easily added to the current
code base. On the downside the implementation of the features often from o r t o o l s . s a t . p y t h o n import cp_model
requires detailed knowledge of the API and must be maintained when model = cp_model . CpModel ( )
n r _ s e a t s = model . NewIntVar ( 0 , 8 0 , " " )
the API changes considerably (which has occurred in the past). 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 , " " )
5.3 Picat 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 :
Picat is a logic-based multi-paradigm language well-suited for solv- # Calling minimize for a variable
ing constraint problems. Most that will be said about Picat and in- # f i n d s t h e l o w e r bound
teractive constraint solving will also apply to other constraint logic model . M i n i m i z e ( 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 ( )
programming systems. s t a t u s = s o l v e r . S o l v e ( model )
In Picat, constraint programming support is added through the cp p r i n t ( s o l v e r . Value ( standing_room ) )
# O u t p u t : 10
module. After importing the cp module, constraint variables can be
declared with VAR::DOMAIN. Constraints can be formulated with
The CP-SAT solver is written in C++, but via SWIG12 also an
variable expressions (using special operators preceded with #), pred-
API in Java, C# and Python is provided, which makes it one of
icates and global constraints like all_different etc. The fol-
the few constraint solvers available in Python. Regarding Require-
lowing shows the Picat implementation of the aforementioned exam-
ment (LanguageAPI) this provides a very good integrability for the
ple. In Picat every additional constraint expression triggers constraint
basic functionality of the solver, although some special features can
propagation and the variable domains are adapted accordingly.
only be accessed through the C++ API.
9 https://github.com/chocoteam/choco-solver
10 11 https://github.com/google/or-tools/
https://search.maven.org/artifact/org.
choco-solver/choco-solver/ 12 http://www.swig.org/
5.5 Preliminary findings REFERENCES
This brief survey of currently available constraint solvers is by no [1] Jérôme Amilhastre, Hélène Fargier, and Pierre Marquis, ‘Consistency
restoration and explanations in dynamic csps application to configura-
means complete. Its main purpose was to illustrate the diversity of tion’, Artif. Intell., 135(1-2), 199–234, (2002).
systems available for constraint solving and how each has particular [2] Christian Bessiere, ‘Constraint propagation’, In Rossi et al. [18], 29–83.
strengths and weaknesses when it comes to satisfying the proposed [3] Krzysztof Czarnecki, Simon Helsen, and Ulrich W. Eisenecker, ‘For-
requirements for interactive solving. malizing cardinality-based feature models and their specialization’,
The focus of most constraint systems is on modelling and effi- Software Process: Improvement and Practice, 10(1), 7–29, (2005).
[4] Andreas A. Falkner, Gerhard Friedrich, Alois Haselböck, Gottfried
cient solving. Only few solvers contain special features for interac- Schenner, and Herwig Schreiner, ‘Twenty-five years of successful ap-
tive solving. Even in the case of solvers based on constraint prop- plication of constraint technologies at Siemens’, AI Magazine, 37(4),
agation, the main purpose of constraint propagation is to assist the 67–80, (2016).
solver during search. Another indicator that features like domain fil- [5] Alexander Felfernig, Monika Schubert, and Christoph Zehentner,
‘An efficient diagnosis algorithm for inconsistent constraint sets’, AI
tering are sometimes less important than performance is the fact that EDAM, 26(1), 53–62, (2012).
Google recommends to use the new SAT-based constraint solver in- [6] David Angelo Ferrucci, Interactive configuration: a logic
stead of the legacy constraint propagation based solver contained in programming-based approach, Ph.D. dissertation, Rensselaer Poly-
Google’s OR-Tools due to performance.13 Only one system (Picat) technic Institute Troy, NY, USA, 1994.
provides a documented mechanism how to get notified about domain [7] Gerhard Fleischanderl, Gerhard Friedrich, Alois Haselböck, Herwig
Schreiner, and Markus Stumptner, ‘Configuring large systems using
changes of constraints variables. Some solvers like Choco include generative constraint satisfaction’, IEEE Intelligent Systems, 13(4), 59–
an explanation engine. None of the solvers we are aware of supports 68, (1998).
default reasoning out of the box. All in all this supports our initial [8] Alois Haselböck and Gottfried Schenner, ‘A heuristic, replay-based ap-
suspicion that interactive solving is a neglected aspect of constraint proach for reconfiguration’, in Proceedings of the 17th International
Configuration Workshop, Vienna, Austria, September 10-11, 2015.,
systems. eds., Juha Tiihonen, Andreas A. Falkner, and Tomas Axling, volume
Of course, the decision which solver to use is complex and will 1453 of CEUR Workshop Proceedings, pp. 73–80. CEUR-WS.org,
not be driven by interactive features alone. Most of the interactive (2015).
features can be implemented (although sometimes less efficiently) [9] Pieter Van Hertum, Ingmar Dasseville, Gerda Janssens, and Marc De-
by treating the solver as a black box. necker, ‘The KB paradigm and its application to interactive configura-
tion’, TPLP, 17(1), 91–117, (2017).
As can be seen even in our simple example, it is not trivial to trans- [10] Lothar Hotz, Thorsten Krebs, and Katharina Wolter, ‘Combining soft-
late a constraint problem from one solver to another. To avoid the risk ware product lines and structure-based configuration – methods and ex-
of getting locked-in to a specific solver API, it might be better to use periences’, in Workshop on Software Variability Management for Prod-
a solver-independent constraint modelling language like MiniZinc. uct Derivation – Towards Tool Support, (2014).
[11] Ulrich Junker, ‘QUICKXPLAIN: preferred explanations and relax-
ations for over-constrained problems’, in Proceedings of the Nineteenth
6 CONCLUSION National Conference on Artificial Intelligence, Sixteenth Conference on
Innovative Applications of Artificial Intelligence, July 25-29, 2004, San
Real-world configuration problems are often interactive in nature, Jose, California, USA, eds., Deborah L. McGuinness and George Fer-
guson, pp. 167–172. AAAI Press / The MIT Press, (2004).
i.e., they include the user as an essential factor in the configuration [12] Ulrich Junker, ‘Configuration’, In Rossi et al. [18], 837–873.
process. To solve configuration problems, constraint satisfaction is [13] Narendra Jussien and Olivier Lhomme, ‘Unifying search algorithms for
often used as an underlying reasoning system. In this paper, we have CSP’, Rapport technique, École des Mines de Nantes, (2002).
made two contributions: First, we have proposed a set of require- [14] Jeppe Nejsum Madsen, Methods for Interactive Constraint Satisfac-
tion, Master’s thesis, Department of Computer Science, University of
ments that a constraint solver should fulfil to support interactive con-
Copenhagen, 2003.
figuration. Second, we have presented the results of a small survey [15] Andreas Hau Nørgaard, Morten Riiskjær Boysen, Rune Møller Jensen,
covering a selected set of non-commercial off-the-shelf constraint and Peter Tiedemann, ‘Combining binary decision diagrams and back-
systems. tracking search for scalable backtrack-free interactive product configu-
Our findings show that interactive aspects of configuration are ne- ration’, In Stumptner and Albert [21], pp. 31–38.
[16] Barry O’Callaghan, Barry O’Sullivan, and Eugene C. Freuder, ‘Gener-
glected by most constraint systems. They also show that the land- ating corrective explanations for interactive constraint satisfaction’, in
scape of available system is highly diverse and that each solver has Principles and Practice of Constraint Programming - CP 2005, 11th
its own strengths and weaknesses when it comes to satisfying the International Conference, CP 2005, Sitges, Spain, October 1-5, 2005,
requirements proposed in this work. Proceedings, ed., Peter van Beek, volume 3709 of Lecture Notes in
Computer Science, pp. 445–459. Springer, (2005).
This is preliminary work. Neither our list of user and solver inter-
[17] Matthieu Stéphane Benoit Queva, Christian W. Probst, and Per Vikkel-
actions nor our list of requirements nor our survey is exhaustive. We søe, ‘Industrial requirements for interactive product configurators’, In
focused here on those requirements and tools that we experienced as Stumptner and Albert [21], pp. 39–46.
most important in our daily work on industrial product configuration. [18] Handbook of Constraint Programming, eds., Francesca Rossi, Peter van
Future work should extend this study to cover more requirements Beek, and Toby Walsh, volume 2 of Foundations of Artificial Intelli-
gence, Elsevier, 2006.
(like aspects of guided selling, prediction of default values, recom- [19] Stuart J. Russell and Peter Norvig, Artificial Intelligence - A Modern
mender features) and more constraint systems. Assessment of each Approach (3. internat. ed.), Pearson Education, 2010.
constraint system shall be done in a more systematic and complete [20] Gottfried Schenner and Richard Taupe, ‘Encoding object-oriented mod-
way and summarized in tables. els in MiniZinc’, in Fifteenth International Workshop on Constraint
Modelling and Reformulation, (2016).
We invite the configuration and constraints communities to pro-
[21] Markus Stumptner and Patrick Albert, eds. Proceedings of the IJ-
pose implementations of constraint systems that are suitable to sup- CAI–09 Workshop on Configuration (ConfWS–09), 2009.
port interactive configuration. [22] Michael Veksler and Ofer Strichman, ‘A proof-producing CSP solver’,
in Proceedings of the Twenty-Fourth AAAI Conference on Artificial In-
13 https://developers.google.com/optimization/cp/cp_
telligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010, eds.,
solver Maria Fox and David Poole. AAAI Press, (2010).