Compatibility analysis#

The compatibility analysis considers an exploration and optimization problem, most often encountered when developing product families. It assumes a product or system consists of various functional modules or components for which multiple variants exist. The goal is to find an optimal configuration, or variant selection for each component, given a set of performance criteria and performance ratings for each variant.

Some variants might be incompatible with each other, which is where the computation of feasible configurations comes into play. Finding a solution therefore becomes a two-step process:

  1. What are the feasible configurations of variants given their compatibility?

  2. What is the performance of each configuration, if there are any?

Modeling the problem#

The problem can be visualized using a Compatibility Matrix. To this end, we model a Graph equivalent with the following contents:

  • A node for each component variant.

    • A variant node may include any number of performance weights, which can later be combined into a performance score per node.

  • An edge between variants that are compatible, with a predefined weight to signal this. Here, we’ll use “compatibility”.

For an absolute minimal example, see the “compatibility” dataset:

>>> from ragraph import datasets
>>> graph = datasets.get("compatibility")
>>> print(datasets.info("compatibility"))
Minimal example to illustrate the compatibility analysis.

Contains 6 component variant nodes. They are divided in three node kinds (e.g.
components), which correspond to the first character in their node names: A1, B1, B2,
C1, C2, C3. For ease of usage, the "performance" weight of each node is set to it's node
name's second character.

Compatibility between nodes is signalled using edges with a "compatibility" kind.

>>> graph.get_ascii_art()
  ┌───┬───┬───┬───┬───┬───┐
A1┥ ■ │ X │ X │   │ X │ X │
  ├───┼───┼───┼───┼───┼───┤
B1┥ X │ ■ │   │ X │ X │ X │
  ├───┼───┼───┼───┼───┼───┤
B2┥ X │   │ ■ │ X │ X │ X │
  ├───┼───┼───┼───┼───┼───┤
C1┥   │ X │ X │ ■ │   │   │
  ├───┼───┼───┼───┼───┼───┤
C2┥ X │ X │ X │   │ ■ │   │
  ├───┼───┼───┼───┼───┼───┤
C3┥ X │ X │ X │   │   │ ■ │
  └───┴───┴───┴───┴───┴───┘

E.g., there are three components for which variants exist. For component “A” we only have a single variant, for “B” we have two, and for “C” we have three. A configuration would therefore be represented by (A1, B2, C1). But is that the only feasible one?

Feasible configurations#

Using the ragraph.analysis.compatibility module, we can generate feasible configurations for this problem. First we create a dictionary of elements (A, B, C) to their respective variant nodes, which we can pass into a CompatibilityAnalysis:

>>> from ragraph.analysis import compatibility as comp
>>> from collections import defaultdict
>>> variants_by_element = defaultdict(list)
>>> for n in graph.nodes:
...     variants_by_element[n.name[0]].append(n)
>>> # variants_by_element = {'A': [Node('A1')], 'B': [Node('B1'), Node('B2')], ...}
>>> ca = comp.CompatibilityAnalysis(
...     graph,
...     variants=variants_by_element,
...     compatibility_method=comp.get_compatibility_method(
...         compatibility_kind="compatibility", incompatibility_kind=None
...     )
... )
>>> configs = ca.yield_feasible_configurations()
>>> # Display names instead of full nodes:
>>> [tuple(n.name for n in config) for config in configs]
[('A1', 'B2', 'C3'), ('A1', 'B2', 'C2'), ('A1', 'B1', 'C3'), ('A1', 'B1', 'C2')]

So currently, there’s four feasible configurations. These are feasible since the compatibility_method with the given arguments checks for edges with an edge kind of “compatibility” between the given variant nodes. The variants of all elements have to be compatible with each other element’s variant in order to achieve a feasible configuration.

Note that the configs variable has been set with a generator rather than a direct list (note the yield instead of get in the method’s name). Using a generator you could find and parse one configuration at a time, which is helpful as these problems tend to get computationally expensive to calculate all at once.

Configuration performance#

Generating feasible configurations is one thingraph, but which configuration is the most performant one? Let’s find out! In the example’s dataset the performance of each variant is equal to the digit in its name. By default, the scoring method takes the sum of all node weights for each component variant node to calculate a variant’s performance. The score for a configuration is the aggregated sum of all variants used.

>>> ca = comp.CompatibilityAnalysis(
...     graph,
...     variants=variants_by_element,
...     compatibility_method=comp.get_compatibility_method(
...         compatibility_kind="compatibility", incompatibility_kind=None
...     ),
...     score_method = comp.get_score_method(
...         variant_agg="sum", config_agg="sum", weights=None
...     )
... )
>>> scored_configs = ca.yield_scored_configurations()
>>> [(tuple(n.name for n in result[0]), result[1]) for result in scored_configs]
[(('A1', 'B2', 'C3'), 6.0), (('A1', 'B2', 'C2'), 5.0), (('A1', 'B1', 'C3'), 5.0), (('A1', 'B1', 'C2'), 4.0)]

From which we can conclude that configuration (A1, B2, C3) is the most performant with a score of 6.

If you would want to generate a complete sorted list of all feasible variants, that is possible as well. Although this might take a while for larger problems:

>>> ca = comp.CompatibilityAnalysis(
...     graph,
...     variants=variants_by_element,
...     compatibility_method=comp.get_compatibility_method(
...         compatibility_kind="compatibility", incompatibility_kind=None
...     ),
...     score_method = comp.get_score_method(
...         variant_agg="sum", config_agg="sum", weights=None
...     )
... )
>>> ranked_configs = ca.get_ranked_configurations(descending=True)  # This is a sorted list, now.
>>> [(tuple(n.name for n in result[0]), result[1]) for result in ranked_configs]
[(('A1', 'B2', 'C3'), 6.0), (('A1', 'B2', 'C2'), 5.0), (('A1', 'B1', 'C3'), 5.0), (('A1', 'B1', 'C2'), 4.0)]

So that’s the same result, but as a sorted list. If your performance metric is a penalty, you can set descending=False.

Adding constraints#

Especially in the context of product platforms you might want to add constraints to the element variants to accomodate for different scenario’s. For instance, in case of bridges and waterway locks the soil might be different, or the waterway that needs to be crossed exceeds a certain width, which excludes certain variants of being applicable.

This can be modeled by adding constraint nodes, to which we could add applicability edges or inapplicability edges, depending on what suits the modeling approach best. Let’s discuss adding a constraint in our example that disables C3 when it’s active.

>>> from ragraph.node import Node
>>> from ragraph.edge import Edge
>>> constraint = Node(name="C3-not-suitable", kind="constraint")
>>> graph.add_node(constraint)
>>> graph.add_edge(Edge(source=constraint, target=graph["C3"], kind="inapplicability"))
>>> ca = comp.CompatibilityAnalysis(
...     graph,
...     variants=variants_by_element,
...     compatibility_method=comp.get_compatibility_method(
...         compatibility_kind="compatibility", incompatibility_kind=None
...     ),
...     score_method = comp.get_score_method(
...         variant_agg="sum", config_agg="sum", weights=None
...     ),
...     constraints=[constraint],
...     applicability_method=comp.get_applicability_method(
...         applicability_kind=None, inapplicability_kind="inapplicability"
...     )
... )
>>> ranked_configs = ca.get_ranked_configurations(descending=True)
>>> [(tuple(n.name for n in result[0]), result[1]) for result in ranked_configs]
[(('A1', 'B2', 'C2'), 5.0), (('A1', 'B1', 'C2'), 4.0)]

Which shows that we have succesfully disabled C3 in this scenario. Note that disabling all variants of an element just disables the entire element without warning. Make sure to check whether disabled_elements does not hold any element you would deem essential while trying to satisfy your current constraints:

>>> assert ca.disabled_elements == [], "Should be an empty list in this example."

Further customization#

The analysis can be tailored to work with your data model in the following ways:

  • Setting a different (in)compatibility method. Please refer to get_compatibility_method for the built-in options. Type: Callable[[Graph, Node, Node], bool].

  • Setting a different scoring method. Please refer to get_score_method for the built-in options. Type: Callable[[Tuple[Node, …]], float].

  • Setting a different applicability method to filter variants. Please refer to get_applicability_method for the built-in options. Type: Callable[[Graph, Node, Node], bool].

All of these method getters return some preset methods that do rudimentary things. Providing your own could be as an inline lambda function that satisfies the call signatures. For instance, some custom methods could look like this:

>>> my_compat = lambda graph, var1, var2: len(graph[var1, var2]) + len(graph[var2, var1]) > 0  # at least one edge between nodes
>>> my_score = lambda config: sum(var.weights['penalty'] for variant in config)  # just sum the penalty weight
>>> my_appli = lambda graph, var, con: not(len(graph[var, con]) + len(graph[con, var]))  # no edges with any constraint

Write to CSV#

If you would like to let the calculations run for a while and generate a CSV file with all results, please refer to the write_csv method.

Design space estimate#

To get an idea of the maximum number of configurations that would have to be checked of an exhaustive search, take the product of your element variation counts:

>>> from math import prod
>>> prod(ca.element_nums)  # Note, C3 is still disabled! So we expect 4, not 5.
4

Luckily, concept compatibility exploration is invalidated as soon as an incompatible concept combination is encountered.