Research Project with EU Funding

Research project with EU funding

Background

The majority of KSB's products have to be configured and are manufactured as individual assemblies for a specific customer order. Systems for product configuration therefore play a major role at KSB.

KSB is conducting a research project to develop new methods, algorithms and software programs for efficient configuration and selection of highly complex product systems (hydraulic pump and valve systems). Funding from the European Union has been applied for under the IWB-ERDF program for Rhineland-Palatina.

Constraint Programming

A configured product is described with technical and commercial features, each of which has a (finite) number of acceptable values ​​in their domain. Pump size, material of the pump casing and the impeller, as well as the language of the provided operating instructions and the data sheets, are some of the many examples.

Not every combination of feature values is allowed. For example, the pump housing and pressure cover should be made of the same material, and the mechanical seal must match the design of the selected cover. These rules can be of a technical nature (would not work or could not be built), due to standards and laws (e.g. pressure limits according to flange standards or operating instructions in the national language), through decisions on logistics or rationalization (selection from a series of pre-assembled stock options assemblies) or commercial (only certain variants should be sold).

A simple method of product modeling is the use of so-called restriction tables. Such a table contains all permissible combinations for a set of the characteristics, typically 3 to 5 columns. The characteristics represent the columns in the table, the permitted combinations the rows. An extension is the "conditional restriction table", which only restricts characteristic values ​​if certain conditions are true, e.g. rhe material of the gland packing and rings should only take values ​​from the table if the shaft seal was selected as the gland packing and not as the mechanical seal.

For customer-specific assembly, a product is individually configured and offered for each customer request. Fast configuration is therefore extremely important so that the quotation and processing process can be made time-efficient and cost-effective.

A KSB product typically requires approx. 500 characteristics and 600 restriction tables in the modeling. With this number, it is hardly possible for a user to carry out the evaluation completely manually. The attempt usually leads to rule violations (e.g. the rule violation: the combination of values ​​does not occur in an active table). In the effort to resolve these conflicts, other, new conflicts arise.

An automated feature evaluation solves this problem and can also help to favor preferred variants by setting preferred default values. Every feature that has not been explicitly assigned a value by the user should have a value in the automated feature evaluation so that all rules are observed and as many features as possible assume their preferred default value.

The automated consistent feature evaluation is highly complex and therefore belongs to the so-called "NP-Complete" problems. The research area of ​​"constraint programming" deals with the solution of these problems. There are now a number of generic "solvers" that work with standard algorithms.

Standard solvers often work with an algorithm in which the "constraint propagation" is followed by a "decision", which in the event of infeasibility revises the last decision ("backtracking") and otherwise continues with propagation and decisions until all features have been evaluated. The constraint propagation determines which values have to be removed ​​from the domains of the characteristics based on the restriction table. After the constraint propagation, many characteristics already have a clear, single allowed value.

With the first characteristic which still has choices available, a decision is made for one of the values. The constraint propagation phase is then initiated again. Should the domain of a characteristic become empty, i.e. there is no longer a valid value, the decision must be revised and another of the possible values ​​used. If none of the values ​​lead to a solution, the previous decision must be revised ("backtracking") and the propagation continued with another value. In the end, either a solution is found or it is determined that there is no solution; in this case there is a conflict ("failure" or "infeasibility").

The following objectives should therefore be addressed in the project:

1. Optimization of constraint propagation for conditional restriction tables

It is known that generic standard solvers do not offer a solution for every problem, and if they do offer a solution, they do not offer the fastest possible solution runtime. Constraint propagation plays a major role in the runtime behavior of the solution and the order of the decisions is decisive for the efficiency of the solution procedure. A constraint propagation tailored and optimized for conditional restriction tables will most likely bring a performance gain. A criteria indexing and an optimization of the compilation time would be conceivable for this - in principle, standard solvers build the problem from scratch for every solution request.

2. Determination of the remaining value domain

If a user evaluates several characteristics, this limits the set of permitted values ​​for the other characteristics. In order for the user to be able to communicate which values ​​for the remaining characteristics still lead to a valid solution, the domain must be determined. This is related to the topic of constraint propagation. A sufficiently strong constraint propagation (after its application no backtracking is necessary for wrong decisions) provides the correct remaining value domains, which can then be communicated to the user.

3. Development of conflict solutions

If the user has already made feature evaluations that make a solution impossible, he must undo one or more of them in order to come to a solution. In order to save the user a trial and error strategy, the system should tell which ratings can be released in order to come to a solution. Junker [2] describes an algorithm to find such solutions on the assumption that the characteristics can be prioritized. The method offers the user a (single) solution, which often amounts to "take back the last rating" - this is not satisfactory for the user. There are several alternatives to certain assumptions about model consistency; This objective is to determine this performantly.

4. Declaration of conflicts

If the constraint propagation ends in failure (a characteristic no longer has valid values), this is determined using a specific table. Previously, however, the domains of the characteristics might already have been restricted by using other tables. Information about the shortest chaining of tables for domain restriction is extremely important for the product modeler who expects a solution for the property evaluation. This way, modeling errors and inconsistencies in the model can be better identified. Standard solvers do not provide such explanations. Therefore, a methodology has to be developed to generate this information.

Literature

[1] Nikolaj van Omme, Laurent Perron, Vincent Furnon, "or-tools User's Manual", Google, 2014 (Originally under http://or-tools.googlecode.com/svn/trunk/documentation/documentation_hub.html but apparently removed; old version available eg under https://acrogenesis.com/or-tools/documentation/user_manual/index.html)
[2] Ulrich Junker, "QUICKXPLAIN: Preferred Explanations and Relaxations for Over-Constrained Problems", Constraint Satisfaction & Satisfiability, Proceedings AAAI'04 Proceedings of the 19th national conference on Artifical intelligence, Pages 167-172, San Jose, California - July 25-29, 2004, Copyright © 2004, American Association for Artificial Intelligence (www.aaai.org).