<figure><img src="image_26.png" /><figcaption>**Figure 1:** Distribution of processing times and the relationship between time and energy</figcaption></figure>

$f(x; \mu, \sigma) = \frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{(x-\mu)^2}{2\sigma^2}}$. This distribution represents naturally occurring variations in processing times or delays. The uniform distribution generates values evenly within a specified range, defined by the probability density function $f(x; a, b) = \frac{1}{b-a}$, where a and b are the lower and upper bounds, respectively. It provides a straightforward way to explore a range of scenarios without bias towards any particular value. These distributions were selected due to their unique properties and common use in modeling different real-world data types, enhancing the diversity and comprehensiveness of the generated instances [15].

Additionally, a random start is chosen for each job within a specified range for the release and due date intervals. The time interval between release and due dates is determined based on the median processing time. A random value within the corresponding interval is generated depending on the chosen distribution. This comprehensive approach ensures the creation of instances encompassing a wide range of scenarios, facilitating robust analyses and evaluations.

These steps culminate in constructing a JSP instance (Line 8), incorporating the generated data. Finally, the algorithm returns the list *G* containing the generated instances. This systematic approach ensures the creation of instances that cover diverse scenarios, which is crucial for comprehensive analyses and evaluations.

### 3. Generated Problems

A comprehensive set of random instances has been generated following the procedure described in Algorithm 1. These instances exhibit diverse characteristics: the number of jobs ranges from thirty to two hundred fifty, and the number of machines ranges from three to twenty. Normal, exponential, and uniform distributions were utilized in the generation process.

Each instance was extended by relaxing release and due date restrictions. Leveraging three different speed scales, variations of each problem were created, maintaining

identical data but with different operational speeds. Specifically, two additional instances were derived from each original: one incorporating the first, third, and fifth-speed scaling and another utilizing only the third-speed scaling.

In addition to varying job and machine counts, the instances encompass different operational complexities and constraints. For instance, some involve jobs with precedence constraints, necessitating certain jobs to be finished before others begin. This complexity challenges algorithms to find optimal solutions efficiently. The chosen distributions—normal, exponential, and uniform—offer a spectrum of scenarios, ranging from predictable and evenly spread job times to highly variable and unpredictable duration. This diversity ensures that the generated instances serve as robust benchmarks to evaluate the performance of scheduling algorithms under varied conditions.

Moreover, a collection of 500 test instances has been generated and made publicly accessible through [16]. These instances incorporate mixed distributions and speed scalings, providing researchers with a comprehensive dataset to evaluate the efficacy of scheduling algorithms. The research group aims to foster collaboration and innovation in planning and scheduling research by facilitating access to these instances. Researchers can use these standardized problems to compare methods and contribute to advancing scheduling solutions.

In summary, the generated instances cover a wide range of job and machine configurations, distribution types, and speed variations, making them suitable for diverse scheduling and planning research applications. Their availability for public use enhances their utility, promoting collaboration and enabling continuous improvement and benchmarking in the field.

### 4. Acknowledgments

The authors gratefully acknowledge the financial support of the European Social Fund (Investing In Your Future)
ture), the Spanish Ministry of Science (project PID2021-125919NB-I00), and valgrAI - Valencian Graduate School and Research Network of Artificial Intelligence and the Generalitat Valenciana, and co-funded by the European Union.

## References

[1] H. Xiong, S. Shi, D. Ren, J. Hu, A survey of job shop scheduling problem: The types and models, Computers & Operations Research 142 (2022) 105731. doi: https://doi.org/10.1016/j.cor.2022.105731.

[2] D. B. M. M. Fontes, S. M. Homayouni, J. F. Gonçalves, A hybrid particle swarm optimization and simulated annealing algorithm for the job shop scheduling problem with transport resources, European Journal of Operational Research 306 (2023) 1140-1157. doi: https://doi.org/10.1016/j.ejor.2022.09.006.

[3] D. M. Torres, F. Barber, M. A. Salido, Psplib-energy: a extension of psplib library to assess the energy optimization in the rcpsp, Inteligencia Artificial 17 (2014) 48-61. doi: 10.4114/intartif.vol17iss54pp48-61.

[4] M. M. S. El-Kholany, M. Gebser, K. Schekotihin, Problem decomposition and multi-shot asp solving for job-shop scheduling, 2022.

[5] C. Perez, M. A. Salido, D. Gurrea, A metaheuristic search technique for solving the warehouse stock management problem and the routing problem in a real company, in: Artificial Intelligence XXXVII, Springer International Publishing, Cham, 2020, pp. 187-201.

[6] M. Dai, D. Tang, A. Giret, M. A. Salido, Multi-objective optimization for energy-efficient flexible job shop scheduling problem with transportation constraints, Robotics and Computer-Integrated Manufacturing 59 (2019) 143-157. doi: https://doi.org/10.1016/j.rcim.2019.04.006.

[7] C. Pérez, L. Climent, G. Nicoló, A. Arbelaez, M. A. Salido, A hybrid metaheuristic with learning for a real supply chain scheduling problem, Engineering Applications of Artificial Intelligence 126 (2023) 107188. doi: https://doi.org/10.1016/j.engappai.2023.107188.

[8] M. A. Salido, J. Escamilla, A. Giret, F. Barber, A genetic algorithm for energy-efficiency in job-shop scheduling, Int J Adv Manuf Technol 85 (2016) 1303-1314. doi: https://doi.org/10.1007/s00170-015-7987-0.

[9] K. Jyothi, R. B. Dubey, Minimizing non-processing energy consumption/total weighted tardiness & earliness, and makespan into typical

production scheduling model-the job shop scheduling problem, Journal of Intelligent & Fuzzy Systems 45 (2023) 6959-6981. doi: 10.3233/JIFS-222362.

[10] A. Ham, M.-J. Park, K. M. Kim, Energy-aware flexible job shop scheduling using mixed integer programming and constraint programming, Mathematical Problems in Engineering 2021 (2021) 1-12. doi: 10.1155/2021/8035806.

[11] J. Kotary, F. Fioretto, P. V. Hentenryck, Fast approximations for job shop scheduling: A Lagrangian dual deep learning method, AAAI 36 (2022) 7239-7246. doi: 10.1609/aaai.v36i7.20685.

[12] L. Toma, M. Zajac, U. Störl, Solving distributed flexible job shop scheduling problems in the wool textile industry with quantum annealing, 2024. arXiv:2403.06699.

[13] J. Hoorn, The current state of bounds on benchmark instances of the job-shop scheduling problem, Journal of Scheduling 21 (2017) 127-128. doi: 10.1007/s10951-017-0547-8.

[14] D. Morillo Torres, F. Barber Sanchís, M. A. Salido Gregorio, Psplib-energy: Una extension de la libreria psplib para la evaluacion de la optimizacion energetica en el rcpsp, Inteligencia Artificial. Revista Iberoamericana de Inteligencia Artificial 17 (2014) 35-48.

[15] L. Gui, X. Li, Q. Zhang, L. Gao, Domain knowledge used in meta-heuristic algorithms for the job-shop scheduling problem: Review and analysis, Tsinghua Science and Technology null (2024) doi: 10.26599/tst.2023.9010140.

[16] Planning, S. R. Group, Energy Instances for Sustainable Job Shop Scheduling, 2024. doi: 10.5281/zenodo.11640130.
# Product visualization in configurators: laying the foundations for a comparative description

Andrea Petterle¹,†, Enrico Sandrin¹,*,† and Cipriano Forza¹,†

¹ University of Padova, Stradella San Nicola 3, 36100 Vicenza, Italy

## Abstract

Visualization plays a critical role in the purchasing process, particularly for customized products, as it improves customer engagement and decision-making. Despite the importance of product configurators in presenting customized products, there is limited research on the characteristics of visualization modes that configurators employ. This study aims to address this gap by developing an evaluation framework consisting of 11 descriptive variables: embodiment, presence, interactivity, authenticity, realism, media richness, avatar similarity, functional control, visual control, interaction richness, and vividness. Each variable of the framework is defined and exemplified by practical examples. These variables, derived from the literature on e-commerce and customer experience, offer a structured framework to describe and compare product visualization modes in configurators.

## Keywords

configurator, product visualization, virtual reality, augmented reality

## 1. Introduction

Visualization is a crucial element in the purchasing process, especially for customized products. The configuration process demands effort from the customer but ultimately strengthens their bond with the product. According to Di et al. [1: 550], images enhance attention, trust, and conversion rates in the purchasing process. More images provide a more complete visual representation of the product, which is effective in boosting sales. Interactive and visually appealing configurators help customers make informed decisions aligned with their expectations. Thus, visualization may reduce choice complexity and improve consumer benefits from customization.

Effective visualization is a powerful tool for knowledge transfer and assimilation, having been used since ancient times [2, 3, 4]. The transfer and assimilation of visual knowledge is simpler and faster than that of textual knowledge [3, 4]. The textual representation of a system of relationships through, for example, a table may also be extremely accurate, but the absence of visualization makes the passage of

information hermetic and tedious. This is an example of why highly valuable work without visualization can be difficult to understand, even for experts in the same field, not to mention professionals from other scientific areas [3]. In the case of customized products, the variant may be novel and difficult to understand to the customer, thus the use of visualization may reduce the cognitive complexity borne by the customer at the stage of selecting the most suitable configuration to satisfy his/her needs.

Visualization technologies are undergoing significant advancements. For example, Apple's Vision Pro revolutionizes visual representation by projecting high-resolution output directly into the eyes, controlled by eye tracking and gestures, eliminating traditional peripherals such as mouse and keyboards [5]. Advanced visualization methods such as augmented reality (AR), virtual reality (VR), and mixed reality (MR) are becoming more and more widespread. The AR, VR, and MR market was valued at approximately $26 billion in 2021 and is expected to reach $242 billion by 2028 [6]. Consumer trends indicate that 71% would shop more frequently using AR, 61% prefer AR-equipped stores,

ConfWS'24: 26th International Workshop on Configuration, Sep 2-3,
2024, Girona, Spain

* Corresponding author.

† These authors contributed equally.

✉ andrea.petterle@studenti.unipd.it (A. Petterle); enrico.sandrin@unipd.it (E. Sandrin); cipriano.forza@unipd.it (C. Forza)

<figure><img src="image_27.png" /></figure>

0009-0000-0041-0112 (A. Petterle);

0000-0001-9170-0683 (E. Sandrin);

0000-0003-4583-2962 (C. Forza)

<figure><img src="image_28.png" /></figure>

<figure><img src="image_29.png" /></figure>

© 2024 Copyright for this paper by its authors. Use permitted under
Creative Commons License Attribution 4.0 International (CC BY 4.0).
and 55% find that AR makes shopping more enjoyable [7].

An important tool for presenting and selling customized products is the configurator. However, research on the visualization of configurable products is limited and a comprehensive and comparative description of the various product visualization modes in configurators is lacking [8].

This research starts to fill this gap by proposing an evaluation framework composed of 11 descriptive variables. These 11 variables, derived from customer experience and e-commerce literature, enable a systematic description of the product visualization modes that a configurator can adopt. The framework defines the 11 descriptive variables according to the literature and presents examples of their modality. The proposed framework is designed to evaluate all visualization modes used in product configurators, encompassing both traditional (e.g., 2D and 3D images) and new modes (e.g., VR, AR, and MR), serving as a consistent tool for describing and comparing different visualization modes in configurators.

## 2. Theoretical background

There is a need for comparative descriptions of product visualization modes in configurators. To be able to describe and compare in a structured way these product visualization modes, a framework that includes a set of description variables that allow to describe in a structured way the visualization modes is needed. With the goal of finding the dimensions of the framework along which to describe and evaluate visualization modes in configurators, the relevant literature was searched, although it did not refer to product configurators. Three sources [9, 10, 11] and their references are taken as a starting point for our research.

Zeng and Richardson [9] conducted a review of the literature on product presentation characteristics in e-commerce. This literature review synthesizes existing research findings, explores key theoretical foundations, and highlights the predominant research theories and methodologies employed in the field. It also categorizes the constructs used to describe the characteristics of presentation formats, consumer reactions and performance, as well as marketing effects, such as attitudes towards the product and purchase intention.

Flavián et al. [10] discussed the impact of VR, AR, and MR on the integration of physical and virtual objects, leading to new hybrid customer experiences. They highlighted the lack of clear boundaries between these technologies and experiences, proposing a new taxonomy, the 'EPI Cube,' to classify current and potential technologies that enhance customer experiences. The 'EPI Cube' is based on three dimensions

of description: (technological) embodiment, (psychological) presence, and (behavioral) interactivity.

Recently, Hsu et al. [11] empirically investigated how key variables (interactivity, authenticity, vividness, product presence, and instant gratification) affect impulsive purchasing intentions using AR.

## 3. Framework for visualization description

The framework variables are taken from the work of Zeng and Richardson [9], Flavián et al. [10], and Hsu et al. [11] and the references cited in these papers. Furthermore, focused searches of literature on specific variables and real applications were performed to clearly define or to exemplify the variables considered in the present framework. Through this process, 11 key variables have been identified:

1. Embodiment

2. Presence

3. Interactivity

4. Authenticity

5. Realism

6. Media richness

7. Avatar similarity

8. Functional control

9. Visual control

10. Interaction richness

11. Vividness

Each variable in the framework is defined and exemplified by practical examples. By integrating and extending previous works, this framework provides a more comprehensive set of variables, scientifically justified by its potential to offer a more complete and nuanced understanding of diverse aspects of product visualization modes for evaluating configurators.

### 3.1. Embodiment

#### 3.1.1. Definitions

"Ihde [12] regarded embodiment as situations in which technological devices mediate the user's experience and, as a consequence, the technology becomes an extension of the human body and helps to interpret, perceive and interact with one's immediate surroundings" [10: 550].

Technological embodiment involves two important factors: sensory stimulation [10, 13, 14], i.e., the process of activating and responding to the body's senses through received stimuli [13, 14]; and immersion [10, 13, 15], i.e., the ability of the technology to allow users to better focus on what is in front of them and to extend their perception of time; it can have positive effects on experience satisfaction [10, 16].
### 3.1.2. Examples

Intraocular lenses, which belong to the category of devices implanted in the human body, guarantee a maximum level of embodiment. They are small contact lenses that are permanently implanted in the eye in order to restore the visual capacity that has been impaired as a result of operations or pathologies affecting this apparatus [17]. Embodiment is maximized because the user is unaware that he or she is wearing a device, but benefits from countless advantages in daily life; in this case, the technology is in complete symbiosis with the human body and acts as an extension of it.

<figure><img src="image_30.png" /><figcaption>**Figure 1:** Intraocular lens. Photograph: Frank C. Müller [Public domain], via Wikimedia Commons. (https://commons.wikimedia.org/wiki/File:Hinterkamm erlinse_01_(fcm).jpg).</figcaption></figure>

## 3.2. Presence

### 3.2.1. Definitions

Vonkeman et al. [18: 1039] define presence as "the degree to which an online product experience appears to be unmediated, rather than mediated". They build upon the definition of Waterworth et al. [19], which describe "presence as a concept that provides the user with the illusion of nonmediation, is driven by external technological sensory cues, and is subjective in nature by focusing on the experience of the user" [18: 1039].

Flavián et al. [10: 551] regard presence "as a psychological stage (not related to a specific technology) and the medium is simply the way to arrive at that stage [20]". They define presence as "the user's sensation of being transported to a distinct environment outside the real human body [13]" [10: 551].

### 3.2.2. Examples

Presence is a highly subjective sensation and can therefore be evoked in different ways depending on the user in question. This perception can be evoked by reading a book, listening to a song, and interacting with

video games [10, 21]. Books and video games allow one to identify with the story: in a detective story, one can identify with the investigator, while in an adventure game, one plays the role of the protagonist directly. Music allows us to abstract from the real world through lyrics or specific sounds, such as the rhythm in South American music, which can make us imagine being in those faraway places.

Presence can be provoked in a virtual environment when there is a sense of 'illusion of place' [10, 22]. Virtual reality systems, such as visors, can facilitate this factor by providing deep sensory stimulation that is so immersive that they can cause a nausea-like disturbance related to perceived movement within the device [23].

## 3.3. Interactivity

### 3.3.1. Definitions

Interactivity is defined as "the extent to which users can participate in modifying the form and content of a mediated environment in real time" [24: 84]. It regards "the users' capacity to modify and receive feedback to their actions in the reality where the experience is taking place [25, 26]. [...] Interactivity is a behavioral factor in that users have the ability to control and manipulate the environment that is in front of them [27]" [10: 552].

The mechanistic or structuralist approach [28] "considers interactivity as the response to the attributes of the technology and proposes that it can be enhanced through the development of these technologies" [10: 552].

Interactivity is not a yes/no property: it is a matter of degree. "Degree to which users of a medium can manipulate the form or content of the mediated environment" [9: 5] [e.g., 18, 29]. In the case of AR, Hsu et al. [11: 5] define interactivity as the "degree to which users can choose, browse, and look up product information and provide feedback through an AR app [24, 30]".

### 3.3.2. Examples

The characteristic of interactivity is easily found in the everyday life of each individual; just think of the use of a computer or a smartphone, where a multitude of interactions take place, consisting of making changes to the system and receiving feedback on them.

In virtual reality devices, it turns out that the control of navigation is the basic level of interactivity present; think of the first prototype 'Sensorama,' which played short films and multimedia content with the involvement of multiple senses [31].

An internal tool such as the viewer can present both levels of interactivity: while watching a film, the device allows viewing in a controlled navigation mode; on the other hand, while playing a video game, using the
joystick and tactile devices (such as suits and gloves), one can modify and monitor the state of the objects presented [10, 22]. The same is true for an external tool such as a computer. When buying a product on Amazon, the process is controlled and the consumer simply follows the predetermined steps. In contrast, when using a product configurator such as Nike's, the customer is able to manipulate and configure the product as he or she wishes.

## 3.4. Authenticity

### 3.4.1. Definitions

Authenticity is the “degree to which users understand a product based on their prior consumption experience, knowledge, or time and space in an AR app environment” [11: 5]. The concept of authenticity by Grayson and Martinec [32] is examined in relation to consumers’ evaluation of market offerings. This approach distinguishes the two types of authenticity:

* Indexical authenticity gives the term 'authentic' the meaning of describing "something that is thought not to be a copy or an imitation [33: 400, 34: 157]" [32: 297].

* Iconic authenticity gives the term 'authentic' the meaning of describing "something whose physical manifestation resembles something that is indexically authentic. Authors sometimes distinguish this sense of authenticity from indexical authenticity by using phrases such as 'authentic reproduction' or 'authentic recreation' [33: 399, 35: 421-422, 36: 208]" [32: 297].

Algharabat and Dennis [37: 6] propose the following definition of “perceived authenticity in a computer-mediated environment: Authenticity is a psychological state in which virtual objects presented in 3D in a computer-mediated environment are perceived as actual objects in a sensory way” [37: 6].

### 3.4.2. Examples

According to the definition of indexical authenticity, Jimmy Stewart's handprints in the concrete of Grauman's Chinese Theatre in Los Angeles are considered authentic if they are perceived to be the actor's original and genuine handprints [32, 38]. According to the description of iconic authenticity, silver pieces available in a museum gift shop are considered authentic because they are believed to bear remarkable similarities to coins produced by Spanish colonies in the 16th century [32, 39]. Furthermore, to judge the authenticity of a Victorian-era chair, a

consumer must have some basic or more detailed idea of how it looks and how it is used [32].

In general, a product image that can be considered authentic is a photograph of it, as it allows the user to see the actual condition and characteristics of the item. The product configurator of the company Design Italian Shoes [40], thanks to its 3D model animation, allows the buyer to perceive the displayed article as tangible. Due to this function, the visual sense processes a concrete image of the item to be purchased.

<figure><img src="image_31.png" /><figcaption>**Figure 2:** Shoe configurator [40]. Screenshot from https://www.designitalianshoes.com/apps/zakeke/c/verdi-custom?sku=120A00020106XX_353535, with permission from DIS - Design Italian Shoes.</figcaption></figure>

## 3.5. Realism

### 3.5.1. Definitions

"Realism refers to the extent to which one believes the virtual environment is real [41] – the degree to which one feels the virtual space represents the actual physical space" [29: 1055]. It also "refers to the perceived correspondence between a technology-mediated experience and a similar experience not mediated by technology [42]" [43: 3].

### 3.5.2. Examples

When designing a building, architects take advantage of 3D virtual environments, software with a high degree of realism, in which physical spaces that do not yet exist can be created and experienced [29].

<figure><img src="image_32.png" /><figcaption>**Figure 3:** Three visual presentations of an apartment [29: 1058]. Reprinted from Computers in Human Behavior, 29, S. van der Land, A. P. Schouten, F. Feldberg, B. van den Hooff, M. Huysman, Lost in space? Cognitive fit and cognitive load in 3D virtual environments, 1054-1064, Copyright (2013), with permission from Elsevier.</figcaption></figure>
Van der Land et al. [29] state that when the degree of realism of a virtual environment reaches the affinity of the real world, the user is assisted by the technology in the process of making decisions and understanding their concrete problem.

The 'Street View' feature of Google Maps provides a realistic visualization of the route or location that the individual is searching for. Thanks to this feature, the user can get an idea of what he or she will be facing in the real future, helping to increase safety. Manufacturers of in-car navigation assistance devices offer reality visualization features that help drivers. For example, they provide high-quality images when approaching a motorway exit or give advice on which lane to take in situations with complex arterial roads [44].

## 3.6. Media richness

### 3.6.1. Definitions

Media richness regards the “extent to which interface facilitates communication [45]” [9: 5]. “Media can be characterized as high or low in 'richness' based on their capacity to facilitate shared meaning” [46: 358]. According to Daft et al. [46], this factor is based on a combination of four criteria.

1. Feedback: instant feedback that allows for specific questions and corrections during the interaction;

2. Multiple cues: a range of cues from which a message can be composed, including physical presence, body gestures, graphic symbols, numbers, and words;

3. Language variety: the range of meanings that can be conveyed by language symbols. For example: numbers convey greater precision than natural language, while the latter helps to convey understanding of a wider range of ideas and concepts [46, 47];

4. Personal focus: a message is conveyed more fully when its communication evokes personal feelings and emotions.

### 3.6.2. Examples

The following four media channels (unaddressed documents, addressed documents, telephone, and face-to-face) are based on the hierarchy proposed by Daft et al. [46] and are presented in ascending order of media richness, from low to high.

Examples of unaddressed documents are fliers, bulletins, and standard quantitative reports. They mainly use messages consisting of three signals: graphic symbols, words, and numbers. They are useful for communicating quantifiable information, but they lack the ability to convey articulated ideas and concepts.

They also lack personalization because they are delivered to a large audience and it is impossible to get feedback.

Addressed documents, such as letters, express written information. They are suitable for presenting personalized content tailored to the individual, thus creating a psychological connection with the reader. Despite this positive criterion, the feedback is still slow.

The telephone call has the ability to provide feedback quickly. Interlocutors rely on their own voice, tone, and language skills to convey messages. This type of channel, which uses natural language communication in real time, is quite rich. A rich communication tool facilitates intuition and allows for rapid understanding of the content presented.

The 'face-to-face' conversation is considered to be the form of interaction with the highest level of this factor. It allows for a rapid exchange of feedback and the creation of a direct connection with the interlocutor. The sender sends multiple signals, making the message comprehensive; the receiver develops empathy more quickly and the content may evoke emotions in him/her.

## 3.7. Avatar similarity

### 3.7.1. Definitions

The avatar is everyone's technological alter ego and the digital representation that each user chooses to identify themselves in an online community.

Avatar similarity is defined “as the perceived similarity between the avatar's physical appearance and the user's physical appearance; the extent of an avatar's similarity is regarded as the degree of reflection of self-concept” [48: 715]. The construction of this virtual element involves the creation of a bond with it, as it is seen as a representation of oneself within the simulated environment [48, 49, 50].

### 3.7.2. Examples

Suh et al. [48] highlight methods that allow the generation of an avatar in its likeness. We begin with the production of an avatar that incorporates the feature of facial similarity. Two production methods are presented: a three-dimensional facial scan and the selection of a generic face among those proposed, with modifications of the features considered significant. A 3D scanner makes it possible to obtain the precise shape of the face; during the scan, several high-resolution digital photographs are taken, resulting in a virtual face. The subject will undoubtedly perceive a closer resemblance to the first process described. In a very similar way, body similarity has been achieved using three-dimensional body scanning and the use of the body mass index. Although it is clear that the first technique gives a better result, it has a number of
limitations, such as the cost of the machine and a
difficult detection procedure. The second method
requires the subject to enter values such as height,
weight, and age, and to select the body shape that most
resembles their own from those presented. One hundred
body shapes are included in the database, and the system
processes the most suitable according to the data
received; the user can then model the features that he or
she considers most important.

3.8. Functional control

3.8.1. Definitions

"Functional control enables consumers to explore and experience different features and functions of products" [51: 111]. Functional control regards the "manipulation of product functionality to understand how a product works [51]" [9: 5].

3.8.2. Examples

The functional control enabled by software such as
Shockwave allows consumers to test different attributes
of products on their computers [51].

An obvious demonstration is online interaction with
some product configurators, such as those for electronic
watches [51]. As the user adds new features, such as
buttons to the item, the cyber product is updated, and its
virtual operation mirrors real behavior. Reactions, such
as the sound produced by pressing a button, can be
reproduced by the sound emitted by clicking on the
virtual representation of that particular item.

It is worth mentioning PhET's website for creating
simulated electrical circuits, as it clearly implements this
factor. By simply clicking on the various objects
presented in the interface, it is possible to create an
electrical circuit and simulate it so that the user can
understand how it works in order to implement it in
practice.

3.9. Visual control

3.9.1. Definitions

"Visual control enables consumers to manipulate Web product images, to view products from various angles and distances" [51: 111]. It regards the "manipulation of product images to understand product looks by moving, rotating and zooming [51]" [9: 5].

3.9.2. Examples

Functionalities such as panning, rotating and zooming a
virtual product image allow the user to enjoy visual
control. The latter, implemented in software such as
QuickTime and Flash, allows consumers to manage
visual operations using the mouse and keyboard [51].

This factor is particularly noticeable when
interacting with the graphical representations in online
configurators. Ikea's virtual environment allows for an
extremely detailed visual experience for the consumer
[52]. Once the room has been configured, it is possible
to move around the room using the mouse to view any
details.

3.10. Interaction richness

3.10.1. Definitions

Interaction richness is the “possibility of interaction with products and seller [53]” [9: 5]. It is also useful to quote the definition of ComputerLanguage.com [54], where ‘rich interaction’ is described as a beneficial and pleasant user experience when using an electronic device. It is worth pointing out that the concept of ‘rich’ is constantly evolving according to the technologies available; in fact, today it means software with a very intuitive and easy-to-use interface, while in the future it will be through tools such as automatic assistance and voice recognition.

3.10.2. Examples

The experiment by Jahng et al. [53] provides two
examples with different levels of interaction richness for
each of the dimensions mentioned above. The richness
of interaction with the salesperson can be achieved
through two means of communication: email and an
interface implementing real-time two-way audio and
one-way video. It is clear that the second interaction is
richer because it makes the product presentation more
effective and the communication support to the
customer more direct.

On the other hand, the richness of the interaction
with the product can take the form of a simple static
image associated with a textual description of the
specifications, or an interactive three-dimensional test
of the product features accompanied by an explanation.

The effectiveness of the latter is obvious, as it allows
better manipulation to understand the features and
overall functioning of the product. Banking service sites
such as Fineco offer a feature such as 'live chat'. Live chat
is a type of customer service software that allows
visitors to interact with operators in real time and
through a chat window [55]. It is clear that effective
customer service is provided through interactive
interfaces that allow the user to engage in profitable
communication before and after purchase.

3.11. Vividness

3.11.1. Definitions

"Vividness means the representational richness of a
mediated environment as defined by its formal features,
that is, the way in which an environment presents
information to the senses" [24: 75]. "Vividness refers to
the abundance of information that an external
environment (e.g., AR app) gives to the human senses,
of which perceptual breadth and perceptual depth are
the two primary variables [24]" [11: 4]. "Perceptual
breadth refers to the extent to which an individual
utilizes multiple sensory modalities to perceive
information simultaneously" [11: 4]. "Perceptual depth
is defined as the measure of both the quantity and
quality of information received by the senses" [11: 4].

3.11.2. Examples

"The quality of the media directly impacts perceptual depth, and more advanced technology (e.g., AR) generally has better perceptual depth performance" [11: 4]. Vonkeman et al. [18] present interesting examples of vividness while investigating the effect of different product (in the specific case sunglasses) display formats, namely: static images, 360-degree rotation tool and virtual mirror.

<figure><img src="image_33.png" /><figcaption>**Figure 4:** Virtual mirror [18: 1046]. Reprinted from Information & Management, 54, C. Vonkeman, T. Verhagen, W. van Dolen, Role of local presence in online impulse buying, 1038-1048, Copyright (2017), with permission from Elsevier.</figcaption></figure>

The static images are captured by a simple camera
and are noninteractive, whereas the 360-degree rotation
tool allows the displays to be rotated by clicking and
dragging the mouse. A webcam captures the
participants' faces and transfers them to the screen via a
'virtual mirror' application by placing the product on it.
The three presentation modes differ in terms of
vividness, particularly in terms of depth, i.e., the quality
of sensory stimulation provided. Static images provide
fixed visual input and elicit the lowest level, while the
360-degree rotation tool and the 'virtual mirror' provide
higher levels through real-time manipulation. The latter,
in particular, through the captured image of the face,
provides a higher quality of representation, and thus a
higher level of vividness.

4. Discussion and conclusion

This paper continues the line of research regarding visualization in configurators [e.g., 8, 56]. In particular, it contributes to that line by distinguishing dimensions for describing and evaluating product visualization modes by drawing on literature from e-commerce and customer experience. Based on literature on e-commerce and customer experience we identified a list of 11 variables that can be used as a framework for describing and evaluating all product visualization modes in configurators. Each variable of the framework is defined and exemplified by practical examples.

While this study provides a starting point for
evaluating product visualization modes in configurators,
it predominantly draws from the e-commerce domain.
Consequently, certain aspects specifically related to the
VR/AR/MR domain may not be fully captured. For
example, in immersive environments, flow, motion
sickness, dizziness due to avatar similarity, and the
uncanny valley effect may arise. Future research could
integrate insights from related disciplines, particularly
those focusing on immersive technologies, to enrich the
framework or to identify relationships among the
framework's variables and other relevant outcome
variables.

Additionally, we acknowledge that some of the
proposed 11 variables may be correlated. However, at
this stage, there is no empirical or theoretical basis to
reduce them to a smaller set. We believe it is beneficial
to present all variables and address potential
consolidation in future research.

Regarding the practical contributions of this study,
the identified dimensions can serve as valuable tools for
managers who need to select visualization alternatives
and for designers responsible for developing product
visualization interfaces in configurators. The proposed
framework, when applied to describe and compare
different visualization modes, allows the presentation
and comparison of the unique features, advantages, and
disadvantages of the modes. This detailed description is
effective for managers and designers who are choosing
the most suitable product visualization mode for their
specific context, providing crucial support during the
evaluation process. Additionally, this framework allows
one to systematically compare these visualization
modes, simplifying the decision-making process.

However, the study did not apply these evaluation
dimensions to the various visualization modes in
configurators, which would further benefit both
managers and designers. Therefore, the next step
involves characterizing these visualization modes on the
basis of the 11 dimensions that comprise the proposed
framework. To achieve this, it is necessary to develop
appropriate measurement metrics. While some metrics
have already been proposed in the literature, others will
need to be developed. In any case, it is crucial to adapt
these metrics and test their effectiveness within the
context of configurators.

Finally, new technologies come with limitations in
costs and benefits. High development and
implementation costs, including hardware and software,
can be significant barriers. User accessibility and the
need for specialized equipment could also limit
adoption. For products not requiring spatial interaction
or immersive experiences, traditional visualizations can
still provide a satisfactory configuration experience at a
lower cost. Future research should explore cost-benefit
analyses to identify scenarios where advanced
visualization modes offer distinct advantages over
conventional approaches.

## Acknowledgements

The authors thank the University of Padova for funding
projects DOR2334949 and DTG SID 2024.

## References

[1] W. Di, N. Sundaresan, R. Piramuthu, A. Bhardwaj, Is a picture really worth a thousand words? - on the role of images in e-commerce, Proceedings of the 7th ACM international conference on Web search and data mining, New York, New York, USA, Association for Computing Machinery, 2014, pp. 633–642. doi: 10.1145/2556195.2556226.

[2] S. Christianson, 100 diagrams that changed the world, Penguin, New York, NY, 2012.

[3] J. Opila, Role of visualization in a knowledge transfer process, Business Systems Research Journal 10 (2019) 164-179. doi: 10.2478/bsrj-2019-0012.

[4] J. van Biljon, K.-M. Osei-Bryson, The communicative power of knowledge visualizations in mobilizing information and communication technology research, Information Technology for Development 26 (2020) 637-652. doi: 10.1080/02681102.2020.1821954.

[5] J. Gans, A. Nagaraj, What is Apple's vision pro really for, Harvard Business Review June 14 (2023).

[6] SkyQuest Technology, Global AR/VR/MR market, 2022. URL: https://www.skyquestt.com/report/ar-vr-mr-market.

[7] H. Ebbesen, C. Machholdt, Digital reality changes everything: step into the future, Deloitte Development LLC (2019).

[8] E. Sandrin, C. Forza, Visualization in configurators: reflections for future research, in J. M. Horcas, J. Á. Galindo, R. Comploi-Taupe, L. Fuentes (Eds.), Proceedings of the 25th International Workshop on Configuration (ConfWS 2023), Málaga, Spain, September 6-7, CEUR Workshop Proceedings, 2023, pp. 8-11.

[9] W. Zeng, A. Richardson, Beyond 2D product presentation in e-commerce: a literature review, ACIS 2017 Proceedings: 35, 2017.

[10] C. Flavián, S. Ibáñez-Sánchez, C. Orús, The impact of virtual, augmented and mixed reality technologies on the customer experience, Journal of Business Research 100 (2019) 547-560. doi: 10.1016/j.jbusres.2018.10.050.

[11] W.-C. Hsu, M.-H. Lee, K.-W. Zheng, From virtual to reality: the power of augmented reality in triggering impulsive purchases, Journal of Retailing and Consumer Services 76 (2024) 1-13. doi: 10.1016/j.jretconser.2023.103604.

[12] D. Ihde, Technology and the lifeworld: From garden to earth, Indiana University Press, Bloomington, IN, 1990.

[13] F. Biocca, The cyborg's dilemma: progressive embodiment in virtual environments, Journal of Computer-Mediated Communication 3 (1997). doi: 10.1111/j.1083-6101.1997.tb00070.x.

[14] I. Tussyadiah, Expectation of travel experiences with wearable computing devices, in Z. Xiang, I. Tussyadiah (Eds.), Information and Communication Technologies in Tourism, Proceedings of the International Conference in Dublin, January 21-24, Springer, Cham, Switzerland, 2014, pp. 539-552. doi: 10.1007/978-3-319-03973-2_39.

[15] D.-H. Shin, The role of affordance in the experience of virtual reality learning: technological and affective affordances in virtual reality, Telematics and Informatics 34 (2017) 1826-1836. doi: 10.1016/j.tele.2017.05.013.

[16] M. Rudd, K. D. Vohs, J. Aaker, Awe expands people's perception of time, alters decision making, and enhances well-being, Psychological Science 23 (2012) 1130-1136. doi: 10.1177/0956797612438731.

[17] G. Giordano, Lenti intraoculari, 2018. URL: https://oculistagiordano.it/lenti-intraoculari/.

[18] C. Vonkeman, T. Verhagen, W. van Dolen, Role of local presence in online impulse buying, Information & Management 54 (2017) 1038-1048. doi: 10.1016/j.im.2017.02.008.

[19] J. A. Waterworth, E. L. Waterworth, G. Riva, F. Mantovani, Presence: form, content and consciousness, in M. Lombard, F. Biocca, J. Freeman, W. Ijsselsteijn, R. J. Schaevitz (Eds.), Immersed in Media: Telepresence Theory, Measurement & Technology, Springer, Cham, Switzerland, 2015, pp. 35-58. doi: 10.1007/978-3-319-10190-3_3.

[20] C. A. Thornson, B. F. Goldiez, H. Le, Predicting presence: constructing the tendency toward presence inventory, International Journal of Human-Computer Studies 67 (2009) 62-78. doi: 10.1016/j.ijhcs.2008.08.006.

[21] C. Coelho, J. Tichon, T. J. Hine, G. Wallis, G. Riva, Media presence and inner presence: the sense of presence in virtual reality technologies, in G. Riva, M. T. Anguera, B. K. Wiederhold, F. Mantovani
(Eds.), From Communication to Presence: Cognition, Emotions and Culture Towards the Ultimate Communicative Experience, IOS Press, Amsterdam, Netherlands, 2006, pp. 25-45.

[22] M. Slater, Place illusion and plausibility can lead to realistic behaviour in immersive virtual environments, Philosophical Transactions of the Royal Society B: Biological Sciences 364 (2009) 3549-3557. doi: 10.1098/rstb.2009.0138.

[23] S. Ang, J. Quarles, Reduction of cybersickness in head mounted displays use: a systematic review and taxonomy of current strategies, Frontiers in Virtual Reality 4 (2023). doi: 10.3389/frvir.2023.1027552.

[24] J. Steuer, Defining virtual reality: dimensions determining telepresence, Journal of Communication 42 (1992) 73-93. doi: 10.1111/j.1460-2466.1992.tb00812.x.

[25] M. Carrozzino, M. Bergamasco, Beyond virtual museums: experiencing immersive virtual reality in real museums, Journal of Cultural Heritage 11 (2010) 452-458. doi: 10.1016/j.culher.2010.04.001.

[26] M. A. Muhanna, Virtual reality and the CAVE: taxonomy, interaction challenges and research directions, Journal of King Saud University - Computer and Information Sciences 27 (2015) 344-361. doi: 10.1016/j.jksuci.2014.03.023.

[27] D. Sohn, Anatomy of interaction experience: distinguishing sensory, semantic, and behavioral dimensions of interactivity, New Media & Society 13 (2011) 1320-1335. doi: 10.1177/1461444811405806.

[28] A. Mollen, H. Wilson, Engagement, telepresence and interactivity in online consumer experience: reconciling scholastic and managerial perspectives, Journal of Business Research 63 (2010) 919-925. doi: 10.1016/j.jbusres.2009.05.014.

[29] S. van der Land, A. P. Schouten, F. Feldberg, B. van den Hooff, M. Huysman, Lost in space? Cognitive fit and cognitive load in 3D virtual environments, Computers in Human Behavior 29 (2013) 1054-1064. doi: 10.1016/j.chb.2012.09.006.

[30] S. J. McMillan, J.-S. Hwang, Measures of perceived interactivity: an exploration of the role of direction of communication, user control, and time in shaping perceptions of interactivity, Journal of Advertising 31 (2002) 29-42. doi: 10.1080/00913367.2002.10673674.

[31] M. L. Heilig, Sensorama simulator, 1962.

[32] K. Grayson, R. Martinec, Consumer perceptions of iconicity and indexicality and their influence on assessments of authentic market offerings, Journal of Consumer Research 31 (2004) 296-312. doi: 10.1086/422109.

[33] E. M. Bruner, Abraham Lincoln as authentic reproduction: a critique of postmodernism, American Anthropologist 96 (1994) 397-415.

[34] J. Huntington, Philip K. Dick: authenticity and insincerity, Science Fiction Studies 15 (1988) 152-160.

[35] M. Crang, Magic kingdom or a quixotic quest for authenticity?, Annals of Tourism Research 23 (1996) 415-431. doi: 10.1016/0160-7383(95)00070-4.

[36] R. A. Peterson, Creating country music: fabricating authenticity, University of Chicago Press, Chicago, IL, 2013.

[37] R. Algharabat, C. Dennis, Using authentic 3D product visualisation for an electrical online retailer, Journal of Customer Behaviour 9 (2010) 97-115. doi: 10.1362/147539210X511326.

[38] T. C. O'Guinn, Touching greatness: the central midwest Barry Manilow fan club, in R. Belk (Ed.), Highways and Buyways: Naturalistic Research from the Consumer Behavior Odyssey, Association for Consumer Research, Provo, UT, 1991, pp. 102-111.

[39] J. A. Costa, G. J. Bamossy, Culture and the marketing of culture: the museum retail context, in J. A. Costa, G. J. Bamossy (Eds.), Marketing in a multicultural world: Ethnicity, nationalism, and cultural identity, SAGE, Thousand Oaks, CA, 1995, pp. 299-328.

[40] DIS - Design Italian Shoes, Verdi custom, 2024. URL: https://www.designitalianshoes.com/en/apps/zake/ke/c/verdi-custom?sku=120A00020106XX_353535.

[41] A. Davis, J. Murphy, D. Owens, D. Khazanchi, I. Zigurs, Avatars, people, and virtual worlds: foundations for research in metaverses, Journal of the Association for Information Systems 10 (2009) 90-117. doi: 10.17705/1jais.00183.

[42] M. Lombard, M. T. Jones, Defining presence, in M. Lombard, F. Biocca, J. Freeman, W. Ijsselsteijn, R. J. Schaevitz (Eds.), Immersed in Media: Telepresence Theory, Measurement & Technology, Springer, Cham, Switzerland, 2015, pp. 13-34. doi: 10.1007/978-3-319-10190-3_2.

[43] M. Daassi, S. Debbabi, Intention to reuse AR-based apps: the combined role of the sense of immersion, product presence and perceived realism, Information & Management 58 (2021) 1-12. doi: 10.1016/j.im.2021.103453.

[44] P. Fröhlich, M. Baldauf, M. Hagen, S. Suette, D. Schabus, A. L. Kun, Investigating safety services on the motorway: the role of realistic visualization, in M. Tscheligi, M. Kranz, G. Weinberg, A. Meschtscherjakov, M. Murer, D. Wilfinger (Eds.), Proceedings of the 3rd International Conference on Automotive User Interfaces and Interactive Vehicular Applications, 30 November - 2 December, Salzburg, Austria, Association for Computing Machinery, New York, NY, 2011, pp. 143-150. doi: 10.1145/2381416.2381440.

[45] H. Kim, K.-S. Suh, U.-K. Lee, Effects of collaborative online shopping on shopping experience through social and relational perspectives, Information & Management 50 (2013) 169-180. doi: 10.1016/j.im.2013.02.003.

[46] R. L. Daft, R. H. Lengel, L. K. Trevino, Message equivocality, media selection, and manager performance: implications for information systems, MIS Quarterly 11 (1987) 355-366. doi: 10.2307/248682.
[47] R. L. Daft, J. C. Wiginton, Language and organization, Academy of Management Review 4 (1979) 179-191. doi: 10.5465/amr.1979.4289017.

[48] K.-S. Suh, H. Kim, E. K. Suh, What if your avatar looks like you? Dual-congruity perspectives for avatar use, MIS Quarterly 35 (2011) 711-729. doi: 10.2307/23042805.

[49] T. Jordan, Cyberpower: The Culture and Politics of the Internet and Cyberspace, Routledge, London, UK, 1999.

[50] Y. B. Kafai, D. A. Fields, M. S. Cook, Your second selves: player-designed avatars, Games and Culture 5 (2010) 23-42. doi: 10.1177/1555412009351260.

[51] Z. Jiang, I. Benbasat, Virtual product experience: effects of visual and functional control of products on perceived diagnosticity and flow in electronic shopping, Journal of Management Information Systems 21 (2004) 111-147. doi: 10.1080/07421222.2004.11045817.

[52] Ikea, BESTÅ planner, 2024. URL: https://www.ikea.com/addon-app/storageone/besta/web/latest/at/en/#/planner.

[53] J. Jahng, H. Jain, K. Ramamurthy, Effects of interaction richness on consumer attitudes and behavioral intentions in e-commerce: some experimental results, European Journal of Information Systems 16 (2007) 254-269. doi: 10.1057/palgrave.ejis.3000665.

[54] ComputerLanguage.com, Definition: rich interaction, 2024. URL: https://www.computerlanguage.com/results.php?definition=rich+interaction.

[55] G. McLean, K. Osei-Frimpong, Chat now... Examining the variables influencing the use of online live chat, Technological Forecasting and Social Change 146 (2019) 55-67. doi: 10.1016/j.techfore.2019.05.017.

[56] L. Hvam, K. Ladeby, An approach for the development of visual configuration systems, Computers & Industrial Engineering 53 (2007) 401-419. doi: 10.1016/j.cie.2007.05.004.
# Using Answer Set Programming for Assigning Tasks to Computing Nodes

Franz Wotawa¹,*,

¹Graz University of Technology (TU Graz), Institute of Software Technology, Inffeldgasse 16b/2, A-8010 Graz, Austria

## Abstract

Allocating tasks to computing nodes in a network is an important configuration problem. In the case of fail-safe networks, such configuration must be changed during operation if a computing node fails. Hence, a fast configuration is required. In this paper, we formulate a tasks-to-computing-nodes assignment problem and its constraints using answer set programming. We performed an initial experimental evaluation utilizing several smaller to mid-size problem instances to show whether logic reasoning based on answer set programming is feasible for practical applications. We discovered that reasoning is fast if a solution exists but not when there is no solution. Further constraints help to decide that a problem instance is unsolvable early in the search, which improves the outcome.

## Keywords

Configuring computing nodes, ASP models for configuration, Experimental analysis

## 1. Introduction

There has been plenty of work in the area of configuration and recommender systems, including service configuration [1], governance systems [2], or product configuration [3] to refer to recent work. However, answer set programming for representing models used for configuration and reasoning to obtain valid configuration has recently gained more attention, e.g., see [3, 4, 5]. In this paper, we contribute to this research direction and introduce a model and an evaluation for configuring networks comprising computing nodes for executing pre-defined tasks. The underlying problem is related to scheduling and shift designs [6].

The main motivation behind our work comes from practical applications, where, for example, tasks, i.e., programs, have to be deployed on computing nodes in a network. Although this problem can be seen as a static one that must only be solved before the operation, we may require to re-configure such a task assignment during operation whenever a computing node fails (see, e.g., [7]). Such re-configuration tasks have to be carried out under time restrictions. To evaluate whether modern reasoning methods like answer set programming can be used for this task, we conduct an experimental evaluation. This evaluation comprises several instances of the corresponding task to computing node assignment problems considering various sizes of nodes and tasks. The evaluation utilizes the answer set programming solver

clingo [8]. The question we want to answer is regarding the approach's limitations regarding the problem size. Can we use answer set programming (and in particular clingo) to provide task assignments fast enough to be used during operation?

We structure this paper as follows. First, we introduce the underlying configuration problem and clingo implementation. Afterward, we discuss the experimental evaluation, i.e., the basic setup and the results obtained. Finally, we conclude the paper.

## 2. Problem description

We start defining the task to node assignment problem. We assume we have k computing nodes $n_1, \dots, n_k$ and n tasks $t_1, \dots, t_n$ to be assigned to the nodes. For each node $n_i$, we know the maximum number of tasks $c(n_i)$ it can hold and the available memory $m(n_i)$. For each task $t_j$, we know its memory consumption $m(t_j)$. From this knowledge, we obtain several constraints an assignment must fulfill to be valid. In the following, we formalize these constraints assuming that the function assigned($n_i$) returns a set of tasks that is assigned to a node $n_i$.

First, the required memory from the tasks assigned to a node shall never exceed the available memory of this node. These constraints can be formalized as follows:

$$ \forall i \in \{1, \dots, k\} : \left( \sum_{t_j \in \text{assigned}(n_i)} m(t_j) \leq m(n_i) \right) \quad (1) $$

Second, the number of tasks assigned to a node shall never exceed the maximum number of tasks the node can hold, i.e., formally, we write:

$$ \forall i \in \{1, \dots, k\} : (|\text{assigned}(n_i)| \leq c(n_i)) \quad (2) $$

ConfWS'24: 26th International Workshop on Configuration, Sep 2-3, 2024, Girona, Spain

*Corresponding author.

wotawa@ist.tugraz.at (F. Wotawa)

https://www.tugraz.at/ (F. Wotawa)

0000-0002-0462-2283 (F. Wotawa)

<figure><img src="image_34.png" /></figure>

© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
A solution to the tasks to computing nodes assignment problem is an assignment of all tasks to all nodes such that $\forall j \in \{1,...,k\} : \exists i \in \{1,...,n\} : t_j \in assigned(n_i)$, there is no tasks assigned to two different nodes, i.e., $\forall i, j \in \{1,...,k\}, i \neq j : assigned(n_i) \cap assigned(n_j) = \emptyset$, and all constraints are fulfilled. Such an assignment is a valid one and may not exist. For example, if the number of tasks exceeds the number of free slots of the nodes or if the required memory for the tasks is not provided, there is no solution. Hence, we have two necessary conditions that must hold for obtaining a solution, i.e.:

$$n \leq \sum_{i=1}^{k} c(n_i) \qquad (3)$$

$$\sum_{j=1}^{n} m(t_j) \leq \sum_{i=1}^{k} m(n_i) \qquad (4)$$

It is worth noting that similar problems have additional constraints, e.g., stating that tasks need to be together in the same computing node. We may also introduce optimality criteria like preferring solutions requiring the least amount of computing nodes. Furthermore, we may also consider variants of the problem, i.e., reconfiguration of assignments. In the context of this paper, we do not tackle such extensions. We solely focus on answering the question regarding the applicability of the answer set program to solve the problem within a reasonable amount of time.

After outlining the problem in general, we present a solution using answer set programming where we rely on the syntax of the clingo solver<fnref n="1" /> [8], which is similar to the Prolog language. Due to space restrictions, we do not give an introduction to answer set programming (ASP). Instead, we refer to introductory literature into ASP, e.g., [9].

A clingo model for the node assignment problem comprises three parts. First, we define the number of computing nodes and tasks and their capacities and requirements. For every node, e.g., n2, we use three facts, where the predicate tcapacity denotes the maximum number of tasks, and mcapacity the maximum available memory for the given task.:

node(n2). tcapacity(n2,1). mcapacity(n2,20).

For each task, e.g., t1, we add two facts, where the predicate memory is for defining the required memory of the given task to a pre-defined value:

task(t1). memory(t1,30).

Second, we generate all potential solutions. For this purpose, we introduce a predicate for a node assignment

of a task. Let us call this predicate select that takes a task T as the first parameter and node N as the second. In clingo, the generate part for the node assignment problem is given as follows:

{ select(T,N) : node(N) } = 1 :- task(T).

This rule generates a grounded predicate that assigns tasks to each computing node. Obviously, not all assignments are correct when considering the constraints. Hence, in the last part, we formalize the first two constraints of the general problem, i.e., Equations 1 and 2, but not the other Equations 3 and 4. For this purpose, we introduce a predicate nrTasksAssigned that holds the number of tasks that are assigned to a particular node and a predicate memRequired that holds the required memory for a node considering the assigned tasks. The information regarding the predicates can be obtained from the selected task for a node (select predicate) and the memory required for a task. For the latter, we introduce the predicate memory. The predicate nrTasksAssigned can be formalized in clingo as follows:

nrTasksAssigned(N,M) :-
M = #count {T:select(T,N)},
node(N).

Similar, we can define the memRequired predicate:

memRequired(N,M) :-
M = #sum {NM:select(T,N), memory(T,NM)},
node(N).

Using these predicates, we can formulate the constraints:

- nrTasksAssigned(N,M), tcapacity(N,C), M>C.

- memRequired(N,M), mcapacity(N,C), M > C.

The first constraint states that it is impossible to assign more tasks to a node than the node can hold. The second constraint states that the memory requirements of all tasks should not exceed the memory capacity of the computing node.

## 3. Experimental evaluation

The following experimental evaluation aims to investigate the runtime behavior for finding one solution of the task to computation node assignment problem using the ASP solver clingo. In particular, we are interested in the number of nodes that can be handled requiring less than a fixed boundary of time, e.g., 0.01 or 0.1 seconds. In the following, we outline the experimental setup and present and discuss the obtained results.

<footnote n="1">¹See https://potassco.org/about/</footnote>
<figure><img src="image_35.png" /><figcaption>**Figure 1:** Solving runtime of consistent instances</figcaption></figure>

**Experimental setup:** To develop several instances of the task assignment problem, we wrote a Java program for generating such instances automatically. We ranged the number of nodes from 5 to 100. The number of tasks for each instance was randomly chosen between the number of nodes and double the number of nodes. The capacity of each node was randomly set from 1, 2, ..., 10. The memory provided by each node was randomly chosen from 20, 40, 60, ..., 200. The memory required by every task was randomly set from 10, 20, and 30. With this setup, we generated only satisfiable instances, i.e., problem instances where a solution exists. For a category of instances comprising *n* nodes, we called the instance generator 10 times. Finally, we received 200 different problem instances.

We conducted the experiments using an Apple MacBook Pro, with an Apple M1 CPU comprising 8 cores and 16 GB of main memory, running under macOS Sonoma Version 14.4.1. For computing solutions, we relied on clingo version 5.7.1 and applied the standard setup.

**Experimental results:** After generating the problem instances, we ran clingo to compute one solution, i.e., we ran clingo using the prompt clingo `-time-limit=10 -outf=2` for each file. Hence, we set a time limit of 10 seconds and obtained all results in JSON format. After analyzing the results for correctness, we summarized the outcome, i.e., the runtime for each category of a particular number of nodes. Figure 1 depicts the minimum, maximum, and average runtime for all 10 runs for each category.

We see that when using ASP solving utilizing clingo we can provide one solution even for larger instances of 100 computing nodes in a reasonable amount of time. However, when using the approach during operation, and especially for systems with harder requirements regarding answering time, e.g., real-time systems, a runtime of almost 3 seconds might not be feasible. We would like answers in less than 0.1 or 0.01 seconds for such systems,

which can be achieved for 20 or 13 nodes, respectively.

Motivated by the results, we performed further experiments, considering problems that likely cannot be solved. Unfortunately, in this case, we often ran into reaching the solving time limit of 10 seconds, even starting with small examples only considering 5 computing nodes. Instances with more than 7 nodes that might be unsatisfiable always reach the 10-second limit. For those instances where unsatisfiability could be established, the runtime varies between 0.003 and 6.255 seconds. The latter was obtained for a problem instance comprising 7 computing nodes. Hence, unsatisfiable instances can hardly be identified when considering more computing nodes, which might also be an issue for practical applications.

We carried out another experiment to tackle the mentioned problem of potential unsatisfiability. We selected 3 problem instances for which we could not compute a result. Two instances had 7 nodes, and one had 15 nodes. For these problem instances, we added further constraints that cover Equations 3 and 4. For all three clingo files that correspond to the problem instances, we added the following code:

```
totalCapacity(C) :- C=#sum{T:tcapacity(N,T)}.
totalMemReq(C) :- C=#sum{M:memory(T,M)}.
totalMem(C) :- C=#sum{N:mcapacity(CN,N)}.
:- totalCapacity(C), C < 21.
:- totalMemReq(Ctask), totalMem(Cnode),
Ctask > Cnode.
```

Note that the 21 in the above code represents the number of tasks<fnref n="2" />. We adapted this value for each instance and set it to 21, 28, and 60 respectively. When running clingo on the three files, we obtained an immediate response of unsatisfiability. In all cases, this response was less than 0.025 seconds. Hence, adding further constraints that allow distinguishing satisfiable from unsatisfiable cases as early as possible solves the problem.

In summary, clingo allows for fast computation of solutions if they exist. The reasoning for the mentioned tasks-to-computing-nodes assignment problem is fast enough for at least smaller examples to ensure a timely response. However, whether this is good enough depends on the application domain. The challenges we obtained in the case of unsatisfiability can be solved by setting a time limit for clingo and introducing additional constraints. Results from this case study may also apply to other configuration problems.

**Threats to validity:** There are many threats to validity worth mentioning. The experimental evaluation is

<footnote n="2">²The number of tasks for a particular problem instance can also be obtained using clingo. The command `#count{T:task(T)}` delivers this number. However, we set the number manually for the three experiments.</footnote>
limited in the number of problem instances. There might be satisfiable instances that may take longer than reported for a given number of computing nodes. However, we do not expect a very large deviation from the results. Furthermore, we only considered one rather simple configuration problem. In case of more complex problems, we expect different runtimes. Nevertheless, the effect of adding constraints to determine unsatisfiability as early as possible should still be visible. This might also hold for the observation that unsatisfiability might be hard to identify and, therefore, require more computing time. We carried out all experiments using clingo's standard-setting. There might be differences to observe when changing parameters and setup. There might also be differences when considering other versions of clingo, the hardware, or the operating system. Finally, the representation of the problem in clingo might also influence the performance.

## 4. Conclusions

In this paper, we used the configuration problem of assigning tasks to computing nodes to answer whether answer-set programming is feasible for practical applications. For smaller problem instances, answer set programming might be feasible, providing a fast response within a fraction of a second. For larger instances, we may not be able to provide a solution within a reasonable answer time. Furthermore, we identified a challenge, i.e., the extended runtime required for providing an answer in case of unsatisfiability, and a solution, i.e., the effect of additional constraints on reducing the runtime. In future research, we want to extend the configuration problem to capture the case of task assignments for computing networks at runtime. For this purpose, we want to formulate a corresponding re-configuration problem. Furthermore, we want to extend the experimental evaluation using more example instances and additional constraints and consider computing optimal solutions concerning a given optimization criteria, e.g., using the least number of computing nodes.

## References

[1] E. M. Strøm, T. M. Münsberg, L. Hvam, Identifying potential applications of service configuration systems in a logistics company, in: J. M. Horcas, J. A. Galindo, R. Comploi-Taupe, L. Fuentes (Eds.), Proc. 25th Intl. Workshop on Configuration, Málaga, Spain, September 6-7, 2023, CEUR-WS.org, 2023, pp. 60–66. URL: https://ceur-ws.org/Vol-3509/paper9.pdf.

[2] S. Muñoz-Hermoso, D. Benavides, F. J. D. Mayo, Multi-level configuration in smart governance systems, in: J. M. Horcas, J. A. Galindo, R. Comploi-

Taupe, L. Fuentes (Eds.), Proc. 25th Intl. Workshop on Configuration, Málaga, Spain, September 6-7, 2023, CEUR-WS.org, 2023, pp. 67–74. URL: https://ceur-ws.org/Vol-3509/paper10.pdf.

[3] R. Comploi-Taupe, G. Friedrich, T. Niestroj, Dynamic aggregates in expressive ASP heuristics for configuration problems, in: J. M. Horcas, J. A. Galindo, R. Comploi-Taupe, L. Fuentes (Eds.), Proc. 25th Intl. Workshop on Configuration, Málaga, Spain, September 6-7, 2023, CEUR-WS.org, 2023, pp. 75–84. URL: https://ceur-ws.org/Vol-3509/paper11.pdf.

[4] N. Rühling, T. Schaub, T. Stolzmann, Towards a formalization of configuration problems for asp-based reasoning: Preliminary report, in: J. M. Horcas, J. A. Galindo, R. Comploi-Taupe, L. Fuentes (Eds.), Proc. 25th Intl. Workshop on Configuration, Málaga, Spain, September 6-7, 2023, CEUR-WS.org, 2023, pp. 85–94. URL: https://ceur-ws.org/Vol-3509/paper12.pdf.

[5] R. Comploi-Taupe, A. A. Falkner, S. Hahn, T. Schaub, G. Schenner, Interactive configuration with ASP multi-shot solving, in: J. M. Horcas, J. A. Galindo, R. Comploi-Taupe, L. Fuentes (Eds.), Proc. 25th Intl. Workshop on Configuration, Málaga, Spain, September 6-7, 2023, CEUR-WS.org, 2023, pp. 95–103. URL: https://ceur-ws.org/Vol-3509/paper13.pdf.

[6] M. Abseher, M. Gebser, N. Musliu, T. Schaub, S. Woltran, Shift design with answer set programming, in: F. Calimeri, G. Ianni, M. Truszczynski (Eds.), Proc. 13th Intl. Conf. on Logic Programming and Nonmonotonic Reasoning, 2015, Lexington, KY, USA, September 27-30, 2015., volume 9345 of LNCS, Springer, 2015, pp. 32–39. URL: https://doi.org/10.1007/978-3-319-23264-5_4. doi:10.1007/978-3-319-23264-5\_4.

[7] A. Ballesteros, M. Barranco, J. Proenza, L. Almeida, F. Pozo, P. Palmer-Rodríguez, An infrastructure for enabling dynamic fault tolerance in highly-reliable adaptive distributed embedded systems based on switched ethernet, Sensors 22 (2022) 7099. URL: https://doi.org/10.3390/s22187099. doi:10.3390/S22187099.

[8] M. Gebser, R. Kaminski, B. Kaufmann, T. Schaub, Multi-shot asp solving with clingo, Theory and Practice of Logic Programming 19 (2019) 27–82. doi:10.1017/S1471068418000054.

[9] T. Eiter, G. Ianni, T. Krennwallner, Answer set programming: A primer, in: S. Tessaris, E. Franconi, T. Eiter, C. Gutierrez, S. Handschuh, M.-C. Rousset, R. A. Schmidt (Eds.), Reasoning Web. Semantic Technologies for Information Systems: 5th Intl. Summer School, Brixen-Bressanone, Italy, August 30 - September 4, 2009, pp. 40–110, Springer Berlin Heidelberg, . URL: https://doi.org/10.1007/978-3-642-03754-2_2. doi:10.1007/978-3-642-03754-2\_2.
Responsible Configuration Using LLM-based
Sustainability-Aware Explanations

Sebastian Lubos¹*, Alexander Felfernig¹*, Lothar Hotz², Thi Ngoc Trang Tran¹, Seda Polat-Erdeniz¹, Viet-Man Le¹, Damian Garber¹ and Merfat El-Mansi¹

¹Institute of Software Technology, Graz University of Technology, Graz, Austria

²Hamburger Informatik Technologie-Center e.V., Hamburg, Germany

**Abstract**

Configuration systems play an important role in achieving the sustainable development goals (SDGs) defined by the United Nations. As decision support systems, configurators help users to decide which components or features to include in or exclude from a configuration. An important task of configurators is the provision of explanations which help to achieve goals such as increasing configuration understandability, increasing a user's trust, and persuading users/customers to include specific configuration components. Our goal in this paper is to introduce the concept of „sustainability-aware explanations" which can help to support the sustainable development goals. The type of explanations we propose in this context are somehow orthogonal to typical explanations used in industrial configuration environments. A major objective in this context is to follow a „less-is-more" principle focusing on different aspects of the idea of „responsible configuration" which refers to configuration techniques explicitly supporting the mentioned sustainability goals. We report the initial results of an evaluation that provide insights on potential impacts of the proposed explanations.

**Keywords**

Explanations, Sustainability, Green Configuration, Responsible Configuration, Configuration for Good, Nudging, Persuasion, Knowledge-
based Configuration

# 1. Introduction

The 17 sustainable development goals (SDGs) defined by the United Nations (UN) provide a blueprint for peace and prosperity on our planet.¹ Examples of such goals are *good health and well-being* (e.g., in terms of fostering the consumption of healthy food), *responsible consumption and production* (e.g., in terms of reduced energy consumption), and *sustainable cities and communities* (e.g., in the context of tourism, avoiding negative environmental impacts and taking into account the local communities and cultural heritage) [1].

Knowledge-based configuration [2, 3, 4, 5] can be regarded as a core-technology of mass customization [6]. On the basis of configurators, users are enabled to design a product in an individualized fashion that fits their wishes and needs. In configuration settings, we can observe an ever-increasing demand for taking into account sustainability aspects [7, 8]. Following the basic definition of „configuration" given by Sabin and Weigel [3], i.e., „configuration is a special case of design activity where the configured artifact is assembled from a fixed set of well-defined component types and components are interacting in predefined ways", we define „responsible configuration" as „configuration which takes into account the United Nation's sustainable development goals".

In knowledge-based systems, explanations can be applied for different purposes [9]. First, so-called *why* explanations [10, 11, 12] focus on the aspect of mentioning the most

relevant user requirements that lead to the determination of a specific configuration. Furthermore, *why not* explanations focus on supporting users in situations where no solution can be identified [13, 14, 15]. From the application point of view, explanations can be applied to achieve different goals [16].² Examples thereof are *efficiency* (reducing the time that is needed to complete a configuration task), *persuasiveness* (convincing users to change their component selection behavior), *transparency* (making the inclusion or exclusion of specific components transparent to the user), *trust* (increasing a user's confidence in the configuration system), *scrutability* (making it possible for the user to adapt the configurator behavior, e.g., in terms of the used component inclusion/exclusion strategy), and *satisfaction* (e.g., increasing the usability of a configuration system). These goals must be regarded as examples – for related details we refer to [11, 16, 17, 18].

In this paper, we focus on the *persuasion aspect* of explanations [19]. More precisely, we analyze possibilities to formulate explanations in such a way that users are nudged towards more sustainability-aware configuration decisions. Following a „less-is-more" principle, we show how to formulate explanations following Cialdini's six principles of persuasion [20] (see Table 1).

Sustainability-aware explanations have to focus on argumentations including sustainability aspects. Our formulation of such explanations is based on *large language model* (LLM) prompts [21] which help to associate sustainable development goals with the mentioned persuasive principles. For example, in the context of car configuration, explanations could refer to the positive environmental aspects of purchasing smaller cars or on the advantages of electric vehicles compared to gasoline-driven ones.

Positive impacts of such sustainability-aware
explanations can be, for example, higher-quality
configuration decisions, a lower amount of unneeded
components, and components with less negative

ConfWS'24: 26th International Workshop on Configuration, Sep 2-3, 2024,
Girona, Spain

* Corresponding author.

slubos@ist.tugraz.at (S. Lubos); afelfern@ist.tugraz.at (A. Felfernig);  
lothar.hotz@uni-hamburg.de (L. Hotz); ttrang@ist.tugraz.at  
(T. N. T. Tran); spolater@ist.tugraz.at (S. Polat-Erdeniz);  
vietman.le@ist.tugraz.at (V. Le); dgarber@ist.tugraz.at (D. Garber);  
merfat.el-mansi@student.tugraz.at (M. El-Mansi)

0000-0002-5024-3786 (S. Lubos); 0000-0003-0108-3146 (A. Felfernig);  
0000-0001-7370-7726 (L. Hotz); 0000-0002-3550-8352 (T. N. T. Tran);  
0000-0001-5778-975X (V. Le)

<figure><img src="image_36.png" /></figure>

© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0).

¹https://sdgs.un.org/goals

²The categorizations of [11, 16] have been developed in the context of recommender systems but can also be applied in configuration contexts.
<table><caption>**Table 1**
Cialdini's principles of persuasion [20].</caption><thead><tr><td>principle</td><td>semantics</td></tr></thead><tbody><tr><td>reciprocity</td><td>feeling of an obligation to give something back</td></tr><tr><td>scarcity</td><td>reduced item availability increases preparedness to purchase</td></tr><tr><td>authority</td><td>experts have an increased influence on users</td></tr><tr><td>commitment and consistency</td><td>users prefer to be consistent with their articulated preferences</td></tr><tr><td>liking</td><td>users like to comply with other users who are similar to themselves</td></tr><tr><td>social proof</td><td>users follow the opinions (of a representative set) of other users</td></tr></tbody></table>

environmental impacts [8]. From a commercial point of view, such explanations might appear – at least to some extent – counterproductive due to potential consequences in terms of decreasing turnovers. Thus, sustainability-aware explanations are often in contrast to explanations in mainstream configuration environments which focus on increasing sales rates in most of the cases.

The contributions of this paper are the following. First, we propose the concept of sustainability-aware explanations for configurations. Second, we provide reference examples of such explanations in the automotive domain. Third, we present initial results of a corresponding evaluation.

The remainder of this paper is organized as follows. In Section 2, we provide different examples of LLM-generated sustainability-aware explanations in the car configuration domain. Thereafter, we discuss initial results of a related evaluation (Section 3). In Section 4, we discuss threats to validity. Finally, we conclude the paper with Section 5.

## 2. Sustainability-Aware Explanations with LLMs

In the following, we discuss scenarios where sustainability-aware explanations can have an impact on user decisions. All scenarios are related to car configuration where users receive explanations of current configurations. The major goal of such explanations is to make users think about their current configuration settings and to potentially adapt their articulated preferences. Consequently, our explanations are not in the line of *why* or *why not* explanations but focus more on indicating potential alternatives to the current configuration, i.e., a kind of *why not choose something else* explanation. All example explanations in this paper have been generated on the basis of the LLM ChatGPT 3.5.<fnref n="3" />

**Scenario 1: SUV vs. smaller car.** The idea is to make persons (configurator users) who intend to purchase an SUV more aware of sustainability aspects of smaller cars. To support this, we have generated LLM-based explanations using the following (example) LLM prompt: *Assume the following scenario: person A wants to purchase a car and is interested in an SUV. Please provide persuasive explanations against purchasing an SUV following the six persuasion principles of Cialdini.* The resulting explanations are depicted in Table 2.

**Scenario 2: Long vs. standard range battery.** The idea is to make configurator users interested in purchasing a car with a long-range battery aware of the sustainability aspects of standard-range batteries. To support such explanations, we have generated LLM-based explanations using the following LLM prompt: *person A wants to purchase an electric car and is interested in a long-range battery. Please provide persuasive arguments against purchasing a long range battery following the six persuasion principles of Cialdini.* The corresponding LLM-generated sustainability-aware explanations are depicted in Table 3.

**Scenario 3: Car not needed in city center.** Configurator users should think about the advantages of not having a car when living in the city center. We have generated related LLM-based persuasive explanations using the following LLM prompt: *person A who lives directly in the city center with various connections to public transportation wants to purchase a car. Please provide persuasive arguments against purchasing a car following the six persuasion principles of Cialdini.* The corresponding sustainability-aware explanations are depicted in Table 4.

**Scenario 4: Less costly car due to financial situation.** The idea is making configurator users with limited financial resources intending to purchase an expensive car to change their mind and purchase a less expensive car. To support such explanations, we have generated LLM-based explanations using the following (example) LLM prompt formulation: *person A with very limited financial resources and a family with three children wants to purchase an expensive car. Please provide persuasive arguments against purchasing an expensive car following the six persuasion principles of Cialdini.* The related LLM-generated explanations are depicted in Table 5.

## 3. Evaluation

**Properties of LLM-based explanations.** In Table 6, we summarize the different argumentation lines generated by the large language model (LLM). (1) In the context of the persuasion dimension *reciprocity*, LLM-generated explanations refer to the aspect of „giving something back to the community“, for example, purchasing an eco-friendly vehicle can be a way of giving back to the environment. (2) Explanations related to the persuasion dimension *scarcity* on the one hand refer to decreasing incentives for sustainable equipment (e.g., cars), on the other hand to limited resources (e.g., financial resources). (3) In the context of the persuasion dimension *authority*, different experts such as environmental experts are used as representatives of authorities. (4) Explanations related to the persuasion dimension *commitment* assume an existing commitment of the current user, for example, already proved in previous configuration sessions. (5) In the context of the persuasion dimension *liking*, LLM-generated explanations refer to a user’s family, friends, and neighbors (e.g., your family will like your decision). (6) Explanations related to the persuasion dimension *social proof* refer to trends of peers, the wider community, and similar families.

**LLM-based impact estimates.** Using the LLM prompt which of these explanations would have the highest persuasive impact on a user? Please provide a ranking., we asked the

<footnote n="3">³https://chat.openai.com</footnote>
<table><caption>**Table 2**
Sustainability-aware explanations related to the aspect of purchasing a smaller car compared to an SUV.</caption><thead><tr><td>principle</td><td>LLM explanation</td></tr></thead><tbody><tr><td>reciprocity</td><td>Consider the environmental impact and how it affects everyone. Choosing a more eco-friendly vehicle can be your way of giving back to the community and environment. Others will likely appreciate and reciprocate your thoughtful decision, fostering a positive cycle of environmentally conscious choices.</td></tr><tr><td>commitment and consistency</td><td>You've always been committed to sustainability and reducing your carbon footprint. Opting for an SUV contradicts these values due to its higher emissions and fuel consumption. Staying consistent with your commitment to the environment means choosing a more fuel-efficient and eco-friendly car.</td></tr><tr><td>social proof</td><td>Look at the growing trend among your peers and the wider community towards hybrid and electric vehicles. Many people are switching to these options because they are better for the environment and more economical in the long run. Following this trend shows you're in tune with progressive, responsible choices.</td></tr><tr><td>authority</td><td>Environmental experts and automotive industry leaders are advocating for smaller, more efficient vehicles to combat climate change and reduce pollution. Following the guidance of these authorities can help you make a well-informed decision that aligns with expert recommendations.</td></tr><tr><td>liking</td><td>Your friends and family who care about the environment will appreciate and support your choice of a more sustainable vehicle. This decision can strengthen your relationships, as they see you aligning your actions with shared values and concerns.</td></tr><tr><td>scarcity</td><td>With increasing regulations and shifts towards renewable energy, fuel-efficient and eco-friendly vehicles may soon become the norm, potentially leading to fewer incentives for traditional gas-guzzling SUVs. Take advantage of the current incentives for hybrid or electric vehicles before they become more scarce.</td></tr></tbody></table>

<table><caption>**Table 3**
Sustainability-aware explanations related to the aspect of purchasing a standard compared to a long-range battery.</caption><thead><tr><td>principle</td><td>LLM explanation</td></tr></thead><tbody><tr><td>reciprocity</td><td>Think about the balance between what you get and what you give. By opting for a standard-range battery, you're reducing the environmental impact associated with producing larger batteries. This considerate choice benefits the community and environment, and others may appreciate your mindful decision, leading them to reciprocate with similar sustainable choices.</td></tr><tr><td>commitment and consistency</td><td>You've been committed to reducing your carbon footprint and promoting sustainability. A standard-range battery is more aligned with these values, as it requires fewer resources to produce and has a lower environmental impact. Staying consistent with your commitment to sustainability means choosing the option that minimizes ecological harm.</td></tr><tr><td>social proof</td><td>Many environmentally conscious drivers are opting for electric vehicles with standard-range batteries because they strike a good balance between range and environmental impact. By choosing a standard-range battery, you're aligning with a growing community of eco-friendly drivers who prioritize sustainability over convenience.</td></tr><tr><td>authority</td><td>Experts in environmental science and sustainable technology often highlight the advantages of smaller, more efficient batteries. They point out that while long-range batteries offer more convenience, the production and disposal of larger batteries have a higher environmental cost. Following the advice of these authorities can help you make a more environmentally responsible decision.</td></tr><tr><td>liking</td><td>Your friends and family who are also concerned about environmental issues will likely appreciate your choice of a standard-range battery. This decision can enhance your relationships as they see you making sacrifices for the greater good and staying true to your shared values.</td></tr><tr><td>scarcity</td><td>As technology advances, the efficiency of electric vehicle batteries is continually improving. Standard-range batteries are becoming more capable, offering longer ranges and better performance. By choosing a standard-range battery now, you can take advantage of current technologies and innovations without feeling the pressure to invest in a long-range battery that may soon become less necessary.</td></tr></tbody></table>

LLM also for a ranking of the impact of the generated explanations following the idea of LLM self-evaluation [22]. In most settings, the dimensions *authority* and *commitment & consistency* have been regarded as the two most impactful persuasion dimensions (see Table 7). The related LLM-based argument is that the latter appeals directly to a person's desire to act in accordance with their past beliefs and statements and the former has a high impact specifically in scenarios where the underlying topic involves technical details. Finally, the dimension of *social proof* can be impactful in situations where social trends and peer behaviors impact decisions.

**Feedback of study participants.** For a very first evaluation beyond the LLM feedback, we conducted a small user study in our research group with N=10 participants (computer science students at our university). The participants were asked to rank the different explanations according to their potential persuasive impact. The results are included in Table 7. Overall, there exists an overlap

between the explanations ranked highest by the LLM and those selected by the study participants. In this context, the *authority* principle has been regarded as relevant in all example configuration scenarios. This initial result indicates basic LLM capabilities to recommend persuasion strategies.

## 4. Threats to Validity

The explanation concepts presented in this paper are based on one selected configuration scenario (car configuration). These explanations are just high-level examples and many further (also more detailed ones) can be envisioned for car configuration (e.g., the sustainability aspects of a less powerful car engine) and beyond. In our work, we did not focus on a specific phase of a configuration process, i.e., the mentioned explanations could even be used before the configuration process has been started (e.g., as explanations in wish lists or product information). Gaining more related insights is a major focus of our future research.
<table><caption>**Table 4**
Sustainability-aware explanations related to the aspect of *waiving a car in the city center*.</caption><thead><tr><td>principle</td><td>LLM explanation</td></tr></thead><tbody><tr><td>reciprocity</td><td>Consider how much the city has invested in developing a robust public transportation system. By using these resources instead of buying a car, you show appreciation and reciprocate the city's efforts to provide efficient and sustainable transportation options. This can inspire others to also rely on public transport, enhancing the community's collective effort to reduce traffic and pollution.</td></tr><tr><td>commitment and consistency</td><td>You've always been committed to living a minimalist and environmentally friendly lifestyle. Owning a car might contradict these values, adding unnecessary expenses and contributing to urban pollution. Staying consistent with your principles means continuing to use the excellent public transportation available to you.</td></tr><tr><td>social proof</td><td>Many city dwellers are moving away from car ownership in favor of public transportation, biking, and walking. This trend reflects a growing recognition of the benefits of car-free living in urban areas. By following this trend, you align yourself with a progressive community that prioritizes sustainability and efficient urban living.</td></tr><tr><td>authority</td><td>Urban planning experts and environmental authorities advocate for reduced car usage in city centers to decrease congestion and pollution. By heeding their advice and utilizing public transport, you're supporting proven strategies that improve city life and contribute to a healthier environment.</td></tr><tr><td>liking</td><td>Your friends and neighbors who also rely on public transportation will likely appreciate and support your decision to avoid car ownership. This shared experience can strengthen your bonds with those around you, as you collectively benefit from less traffic, cleaner air, and a more vibrant urban community.</td></tr><tr><td>scarcity</td><td>Parking spaces and road capacity in the city center are limited resources. By not purchasing a car, you're helping to reduce the demand for these scarce resources, making the urban environment more livable for everyone. Additionally, public transport allows you to avoid the hassle and expense associated with finding and paying for parking.</td></tr></tbody></table>

<table><caption>**Table 5**
Sustainability-aware explanations related to the aspect of *purchasing an affordable car*.</caption><thead><tr><td>principle</td><td>LLM explanation</td></tr></thead><tbody><tr><td>reciprocity</td><td>Think about the support you've received from friends, family, and community during tough financial times. By opting for a more affordable car, you demonstrate financial responsibility and can reciprocate their support by being in a better position to help others when they need it.</td></tr><tr><td>commitment and consistency</td><td>You've always been committed to providing the best for your family while managing your limited financial resources wisely. Purchasing an expensive car contradicts this commitment and could put unnecessary financial strain on your household. Staying consistent with your goal of financial stability means choosing a car that fits within your budget.</td></tr><tr><td>social proof</td><td>Many families in similar financial situations prioritize practicality and affordability when it comes to transportation. By choosing a more economical vehicle, you're following a proven path that many others have taken to ensure they can meet their family's needs without financial stress.</td></tr><tr><td>authority</td><td>Financial advisors and experts consistently recommend living within your means and avoiding large, unnecessary expenses, especially when money is tight. By following this expert advice, you're making a prudent decision that aligns with sound financial practices and secures your family's financial future.</td></tr><tr><td>liking</td><td>Your friends and family will likely admire and respect your decision to prioritize your family's well-being over the allure of an expensive car. Making a practical choice shows that you value their advice and shared values of financial prudence and responsibility.</td></tr><tr><td>scarcity</td><td>Financial resources are currently scarce for your family. By not purchasing an expensive car, you conserve these limited resources for more critical needs like education, healthcare, and everyday living expenses. This ensures that you have the financial flexibility to handle unexpected costs and opportunities that arise.</td></tr></tbody></table>

The presented impact ranking of explanations has been primarily discussed on the basis of an LLM-generated ranking [22] including corresponding argumentations that help to understand the proposed ranking. More detailed studies with real users (and more detailed related preference and context information) are planned within the scope of future work also to better understand the limitations of LLMs with regard to the recommendation of persuasion strategies. Up to now, no LLM-related hallucination effects could be observed, however, this is an important aspect to be taken into account in future work. A recently mentioned new persuasion principle (identification) [23] will be taken into account in future studies. Finally, more detailed LLM prompts better taking into account the context (and

preferences) of the current user are regarded as an important topic of future work.

## 5. Conclusions

In this paper, we have introduced the concept of sustainability-aware explanations of configurations. Using the example of car configuration, we have explained and exemplified this type of explanation. Following a set of persuasion dimensions, we have analyzed the LLM-generated explanations with regard to the used argumentation lines and analyzed the impact of the generated explanations on the user. In this context, LLMs
<table><caption>**Table 6**

LLM-based argumentation lines for Cialdini's principles of persuasion [20].</caption><thead><tr><td>principle</td><td>argumentation line</td></tr></thead><tbody><tr><td>reciprocity</td><td>giving something back to the community and the environment</td></tr><tr><td>scarcity</td><td>fewer incentives for sustainable equipment, limited available financial resources</td></tr><tr><td>authority</td><td>environmental experts, urban planning experts, financial advisors</td></tr><tr><td>commitment and consistency</td><td>existing commitment to sustainability in the past</td></tr><tr><td>liking</td><td>family, friends, neighbors</td></tr><tr><td>social proof</td><td>trends of peers, wider community, and similar families</td></tr></tbody></table>

<table><caption>**Table 7**

Scenario-dependent preferred explanations (top-2 LLM and study participant-preferred explanations).</caption><thead><tr><td>scenario</td><td>top-2 (LLM)</td><td>top-2 (study participants)</td></tr></thead><tbody><tr><td>SUV vs. smaller car</td><td>(1) commitment & consistency, (2) authority</td><td>(1) authority, (2) liking</td></tr><tr><td>Long vs. standard range battery</td><td>(1) authority, (2) commitment & consistency</td><td>(1) authority, (2) social proof</td></tr><tr><td>Car not needed in city center</td><td>(1) social proof, (2) authority</td><td>(1) authority, (2) reciprocity</td></tr><tr><td>Less costly car due to financial situation</td><td>(1) authority, (2) commitment & consistency</td><td>(1) authority, (2) commitment & consistency</td></tr></tbody></table>

show to be applicable in terms of generating explanations in a flexible fashion but also to recommend explanations in specific configuration contexts. Our future work will include detailed studies with real users with the goal to compare LLM-based rankings with the perception of explanations by real users. Further research will include an analysis of the effects of combining explanations (e.g., integrating authority-based with commitment-based explanations).

## References

[1] A. Felfernig, M. Wundara, T. Tran, S. Polat-Erdeniz, S. Lubos, M. E. Mansi, D. Garber, V. Le, Recommender systems for sustainability: overview and research issues, Frontiers in Big Data 6 (2023). URL: https://www.frontiersin.org/articles/10.3389/fdata.2023.1284511. doi:10.3389/fdata.2023.1284511.

[2] A. Felfernig, L. Hotz, C. Bagley, J. Tiihonen, Knowledge-based Configuration - From Research to Business Cases, Morgan Kaufmann, 2014.

[3] D. Sabin, R. Weigel, Product configuration frameworks-a survey, IEEE Intelligent Systems 13 (1998) 42-49. doi:10.1109/5254.708432.

[4] M. Stumptner, An Overview of Knowledge-based Configuration, AI Communications 10 (1997) 111-126.

[5] A. Felfernig, A. Falkner, D. Benavides, Feature Models: AI-Driven Design, Analysis and Applications,

SpringerBriefs in Computer Science, Springer, Cham, 2024. doi:10.1007/978-3-031-61874-1.

[6] B. J. Pine, B. Victor, A. Boynton, Making mass customization work, Harvard Business Review 71 (1993) 108-119.

[7] N. Tchertchian, D. Millet, Optimization approach for attractive and sustainable products, Procedia CIRP 90 (2020) 350-354. doi:10.1016/j.procir.2020.01.103.

[8] R. Wiezorek, N. Christensen, Integrating sustainability information in configurators, in: Configuration Workshop (ConfWS), 2021, pp. 58-64. URL: https://ceur-ws.org/Vol-2945/52-RW-ConfWS21_paper_16.pdf.

[9] T. N. T. Tran, A. Felfernig, V. M. Le, T. M. N. Chau, T. G. Mai, User needs for explanations of recommendations: In-depth analyses of the role of item domain and personal characteristics, in: 31st ACM Conference on User Modeling, Adaptation and Personalization, UMAP '23, ACM, New York, NY, USA, 2023, pp. 54-65. URL: https://doi.org/10.1145/3565472.3592950. doi:10.1145/3565472.3592950.

[10] G. Friedrich, Elimination of spurious explanations, in: 16th European Conference on Artificial Intelligence, ECAI'04, IOS Press, NLD, 2004, pp. 813-817.

[11] G. Friedrich, M. Zanker, A taxonomy for generating explanations in recommender systems, AI Magazine 32 (2011) 90-98. doi:10.1609/aimag.v32i3.2365.

[12] S. P. Erdeniz, M. Schrempf, D. Kramer, P. P. Rainer, A. Felfernig, T. Tran, T. Burgstaller, S. Lubos, Computational evaluation of model-agnostic explainable ai using local feature importance in healthcare, in: J. M. Juarez, M. Marcos, G. Stiglic, A. Tucker (Eds.), Artificial Intelligence in Medicine, Springer Nature Switzerland, Cham, 2023, pp. 114-119.

[13] A. Felfernig, M. Schubert, S. Reiterer, Personalized diagnosis for over-constrained problems, in: 23rd International Joint Conference on Artificial Intelligence, IJCAI '13, AAAI Press, 2013, pp. 1990-1996.

[14] V.-M. Le, A. Felfernig, T. N. T. Tran, M. Uta, Informedqx: Informed conflict detection for over-constrained problems, AAAI Conference on Artificial Intelligence 38 (2024) 10616-10623. doi:10.1609/aaai.v38i9.28932.

[15] B. O'Sullivan, A. Papadopoulos, B. Faltings, P. Pu, Representative explanations for over-constrained problems, in: 22nd National Conference on Artificial Intelligence - Volume 1, AAAI'07, AAAI Press, 2007, pp. 323-328.

[16] N. Tintarev, J. Masthoff, Evaluating the effectiveness of explanations for recommender systems, User Modeling and User-Adapted Interaction 22 (2012) 399-439. doi:10.1007/s11257-011-9117-5.

[17] N. Tintarev, Explanations of recommendations, in: ACM Conference on Recommender Systems, RecSys '07, Association for Computing Machinery, New York, NY, USA, 2007, pp. 203-206. doi:10.1145/1297231.1297275.

[18] N. Tintarev, J. Masthoff, A survey of explanations in recommender systems, in: ICDEW '07, IEEE Computer Society, USA, 2007, pp. 801-810. doi:10.1109/ICDEW.2007.4401070.

[19] A. Felfernig, B. Gula, G. Leitner, M. Maier, R. Melcher,
E. Teppan, Persuasion in knowledge-based recommendation, in: H. Oinas-Kukkonen, P. Hasle, M. Harjumaa, K. Segerståhl, P. Øhrstrøm (Eds.), Persuasive Technology, Springer, Berlin, Heidelberg, 2008, pp. 71–82.

[20] R. Cialdini, Influence: The Psychology of Persuasion, Quill, New York, NY, USA, 1993.

[21] S. Lubos, A. Felfernig, T. Tran, D. Garber, M. Mansi, S. Erdeniz, V. Le, Leveraging llms for the quality assurance of software requirements, in: Proceedings of the 32nd IEEE International Requirements Engineering 2024 Conference (RE@Next! Track), IEEE, 2024, p. to appear.

[22] Y. Chang, X. Wang, J. Wang, Y. Wu, L. Yang, K. Zhu, H. Chen, X. Yi, C. Wang, Y. Wang, W. Ye, Y. Zhang, Y. Chang, P. S. Yu, Q. Yang, X. Xie, A survey on evaluation of large language models, ACM Trans. Intell. Syst. Technol. 15 (2024). doi:10.1145/3641289.

[23] R. Cialdini, Influence, New and Expanded: The Psychology of Persuasion, HarperCollins, 2021.
Semantics-Preserving Merging of Feature Models

Mathias Uta<fnref n="1" />, Viet-Man Le<fnref n="2" />, Alexander Felfernig<fnref n="2" />, Damian Garber<fnref n="2" />, Gottfried Schenner<fnref n="3" /> and
Thi Ngoc Trang Tran<fnref n="2" />

**Abstract**

Large and globally operating enterprises can be confronted with situations where local variability models representing the constraints of individual countries and markets have to be integrated to support a centralized variability management. For example, a car producer operating in the U.S. as well as the European market, could be interested in having a centralized variability (feature) model representing the variability spaces of all supported markets. To achieve this goal, existing local feature models and the corresponding knowledge bases have to be integrated in such a way that the configuration spaces remain the same, for example, for the European market, we would request to support exactly the same set of car configurations that are supported by the corresponding local feature model. In this paper, we introduce an algorithmic approach that supports the merging of feature models in such a way that the semantics of the original feature models is preserved. We present our algorithm and the results of a solver performance analysis which has been conducted on the basis of real-world feature models.

**Keywords**

Variability Modeling, Feature Models, Model Merging, Redundancy Elimination, Configuration

# 1. Introduction

Feature models (FMs) are an intuitive way of representing commonality and variability properties of complex systems [1, 2, 3]. Specifically, in scenarios where companies are operating on a global basis, integration scenarios can arise where country or region-specific feature models have to be integrated to support a more globalized variability management. Think about a scenario where a car producer operating in the European and the US market decides to centralize variability management activities. On the technical (feature model) level, formerly region- or country-specific models have to be integrated in a systematic fashion in one centralized variability model. In this paper, we present an algorithmic approach to integrate (merge) two different (“old”) feature models (e.g., the feature model $FMUS_{old}$ could denote a local feature model of a US car provider) in a semantics-preserving way where the solution (configuration) spaces of the local feature models are “transferred” to an integrated feature model which reflects exactly the same set of solutions: $solutions(FMUS_{old}) \cup solutions(FMEU_{old})$

equals solutions($FM_{new}$). In this context, we assume that $FMUS_{old}$ and $FMEU_{old}$ represent the local feature models of a globally operating car manufacturer and $FM_{new}$ is the result of merging the local feature models (and related knowledge bases).

Knowledge base merging has been approached in various ways. For example, the *alignment* of knowledge bases is based on the idea of knowledge base integration by identifying concepts in different knowledge bases that represent the same underlying concept but are represented by different names. Knowledge base alignment is specifically performed in situations where numerous knowledge bases have to be integrated [4]. Knowledge base *merging* is based on a set of predefined merging operations [5, 6], for example, consistency-based merging follows the goal of deriving a maximally consistent set of logical formulae that represent the union of the formulae of the original knowledge bases. Such integrations basically follow the idea of generating maximally satisfiable subsets (of rules) [7], i.e., sets that cannot be further extended (with original rules) without making the resulting knowledge base inconsistent.

*Feature model merging* [8, 9, 10, 11, 12, 13] is also in the line of the ideas of the previously mentioned approaches. Feature models can become quite large and complex [14], which makes the development and maintenance of single models a challenging task. Following the idea of *separation of concerns* [15], Aydin et al. [16] propose an approach to construct stakeholder-individual feature models which are then merged for the purpose of providing a unified view on the feature space. In the context

ConfWS'24: 26th International Workshop on Configuration, Sep 2–3,
2024, Girona, Spain

<figure><img src="image_37.png" /></figure>

mathias.uta@siemens-energy.com (M. Uta);

vietman.le@ist.tugraz.at (V. Le); alexander.felfernig@ist.tugraz.at

(A. Felfernig); dgarber@ist.tugraz.at (D. Garber);

gottfried.schenner@siemens.com (G. Schenner);

ttrang@ist.tugraz.at (T. N. T. Tran)

<figure><img src="image_38.png" /></figure>

0000-0002-1670-7508 (M. Uta); 0000-0001-5778-975X (V. Le);

0000-0003-0108-3146 (A. Felfernig); 0000-0002-3550-8352

(T. N. T. Tran)

<figure><img src="image_39.png" /></figure>

© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0).

<footnote n="1">¹Siemens Energy AG, Erlangen, Germany</footnote>

<footnote n="2">²Graz University of Technology, Graz, Austria</footnote>

<footnote n="3">³Siemens AG, Vienna, Austria</footnote>
<figure><img src="image_40.png" /><figcaption>**Figure 1:** Example basic feature model from the automotive domain where *type* refers to the car type which can be (lim)ousine, (com)bi, (cit)y, and suv. Furthermore, the car *color* can be (b)lack or (w)hite, the *engine* can be 1l, 1.5l, and 2l. *Fuel* can be (d)iesel, (e)lectric, (g)asoline, and (h)ybrid, representing the supported types of fuel. Finally, a *coupling* unit is regarded as an optional feature.</figcaption></figure>

of such a merging process, different “issues” have to be resolved, for example, some stakeholders regard a feature as optional while others think it should be mandatory. Furthermore, depending on the given scenario, feature naming can also become an issue if no “maximum feature set” has been specified ahead of the merging process. For such scenarios, Aydin et al. [16] propose a standard merging procedure that is able to generate a reference feature model, which then serves as a basis for further discussions and decision-making.

With a similar motivation, i.e., making large feature model development easier, Acher et al. [8], propose a set of integration operations for “local” feature models which basically support the goal of integrating local models into a global one. In this context, the authors also specify feature model relationships on a logical basis, for example, one feature model *FM1* is the specialization of a feature model *FM2* if the configuration space of *FM1* is a subset of the configuration space of *FM2* – see also Thüm et al. [17, 3]. The authors also introduce a *merge* operation where the introduced semantics does not support semantics preservation but requires that the result of the merging operation is equivalent or a superset of the solution (configuration) spaces of the two original feature models, i.e., *solutions(*FM1*)* ⊔ *solutions(*FM2*)* ⊆ *solutions(*merge(*FM1*, *FM2*))*). Such a semantics of a merge operation is also considered in the contributions of Broek et al. [10], Carbonell et al. [11], and She et al. [18].

Following the *union merge* semantics introduced in Schobbens et al. [12], the feature model merging approach presented in this paper focuses on the preservation of the semantics of the source feature models used as an input for the merging procedure. In other words, it supports a semantics-preserving merging where the configuration space of the feature model resulting from a merging operation is exactly the union of the configuration spaces of the original feature models: *solutions(*FM1*)* ⊔ *solutions(*FM2*)* = *solutions(*merge(*FM1*, *FM2*))* which is more restrictive

compared to the union semantics introduced by Acher et al. [8].

Compared to related work on feature model semantics preservation [10, 13], our approach provides a generalization in terms of (1) supporting arbitrary constraint types (in contrast to specific feature model related constraints such as *requires* and *incompatible*) and (2) taking into account redundancy-freeness in terms of assuring that redundant constraints as a result of a merging procedure can be detected and eliminated from the feature model. In our approach, the original feature models and the resulting feature model (result of the merging operation) are represented as constraint satisfaction problems (CSPs) [19]. To demonstrate the applicability of our approach, we present the results of a corresponding performance analysis.

The remainder of this paper is structured as follows. In Section 2, we introduce a working example consisting of simplified feature models from the automotive domain. Using this example, we discuss our algorithmic approach to semantics-preserving feature model merging in Section 3. To show the performance of our approach, we report the results of a corresponding performance evaluation (see Section 4). Finally, we conclude the paper with a discussion of existing threats to validity (Section 5) and a corresponding summary of the contributions of this paper (Section 6).

## 2. Example Scenario

We now introduce a simplified example of a feature model merging scenario. Our basic underlying assumption is that the original feature models are consistent, i.e., it is possible that at least one solution can be identified and also that the feature set of the original models are the same, i.e., the differences are primarily observable in terms of the constraints defined in the individual models. In our example from the automotive domain, the original feature models are denoted as *FMUS*<sub>old</sub> (the original US feature model) and *FMEU*<sub>old</sub> which denotes the
original European Union feature model. In this context, we assume that these feature models are consistent, i.e., non-void [20], meaning that at least one configuration can be identified for each of those models. Finally, we denote the resulting model (the merging result) as $FM_{new}$.

Figure 1 represents the basic feature model (i.e., configuration model [21]) that in the following will be used as a working example. This feature model represents all relevant features that can be used to define variability knowledge, i.e., we assume that the same set of features is used to represent variability knowledge in $FMEU_{old}$ and $FMUS_{old}$. Differences in the two variability models can exist in terms of constraints representing individual configuration spaces. In the following, we specify constraints that define the properties of the two original feature models $FMEU_{old}$ and $FMUS_{old}$ represented in terms of individual constraint satisfaction problems (CSPs) representing the European and the US feature model [19].<fnref n="1" /> These CSPs are defined in terms of variables with corresponding domain definitions (e.g., type(lim, com, sit, suv) denotes the variable type with the allowed values) and a corresponding set of constraints [22].

Note that region is an additional variable representing a contextual information, i.e., to which region a generated configuration belongs to. Contexts follow the idea of separation of concerns [15] which supports a kind of decentralized modeling [23]. For example, using the context variable region, the constraint $c_{1us} : fuel \neq h$ would be expressed as $c_{1us} : region = US \rightarrow fuel \neq h$ explicitly indicating that this constraint has to hold for configurations generated on the basis of the $FMUS_{old}$ CSP.

* $FMUS_{old}$: {region(US), type(lim, com, cit, suv), color(b, w), engine(1l, 1.5l, 2l), fuel(d, e, g, h), coupling(yes, no), $c_{1us}$ : fuel \neq h, $c_{2us}$ : fuel = e \rightarrow coupling = no, $c_{3us}$ : fuel = d \rightarrow color = b}

* $FMEU_{old}$: {region(EU), type(lim, com, cit, suv), color(b, w), engine(1l, 1.5l, 2l), fuel(d, e, g, h), coupling(yes, no), $c_{1eu}$ : fuel \neq g, $c_{2eu}$ : fuel = e \rightarrow coupling = no, $c_{3eu}$ : fuel = d \rightarrow type \neq cit}

To show the differences between the feature models $FMEU_{old}$ and $FMUS_{old}$, Table 1 provides an overview of the number of solutions supported by the original (region-specific) feature models.

## 3. Merging Feature Models

In order to be able to merge the two original feature models ($FMEU_{old}$ and $FMUS_{old}$) in a semantics-preserving

<table><caption>**Table 1**
Number of consistent solutions (configurations) related to the original and contextualized feature models.</caption><thead><tr><td>Feature model</td><td>#configurations</td></tr></thead><tbody><tr><td>$FMEU_{old}$</td><td>108</td></tr><tr><td>$FMUS_{old}$</td><td>96</td></tr><tr><td>$FM' = FMEU'_{old} \cup FMUS'_{old}$</td><td>204</td></tr><tr><td>$FMEU'_{old} \cap FMUS'_{old}$</td><td>84</td></tr></tbody></table>

fashion, each constraint of the two original feature models (represented as CSPs) has to be contextualized using the context variable region.<fnref n="2" /> Assuming the two regions European Union and US, our context variable could be defined as region(EU, US) denoting the variable region with the allowed values {EU, US}. More precisely, each constraint $c_{[i]eu}$ ($c_{[i]us}$) of the “EU” (“US”) CSP (derived from the $FMEU_{old}$ ($FMUS_{old}$) feature model) has to be translated into a contextualized representation – see the following example: $c_{1eu} : fuel \neq g$ would be translated into a corresponding contextualized form $c_{1eu'} : region = EU \rightarrow (fuel \neq g)$. The resulting contextualized variants of the original knowledge bases $FMEU_{old}$ and $FMUS_{old}$ are denoted as $FMEU'_{old}$ and $FMUS'_{old}$.

* $FMUS'_{old}$: {region(US), type(lim, com, cit, suv), color(b, w), engine(1l, 1.5l, 2l), fuel(d, e, g, h), coupling(yes, no), $c'_{1us}$ : region = US \rightarrow (fuel \neq h), $c'_{2us}$ : region = US \rightarrow (fuel = e \rightarrow coupling = no), $c'_{3us}$ : region = US \rightarrow (fuel = d \rightarrow color = b)}

* $FMEU'_{old}$: {region(EU), type(lim, com, cit, suv), color(b, w), engine(1l, 1.5l, 2l), fuel(d, e, g, h), coupling(yes, no), $c'_{1eu}$ : region = EU \rightarrow (fuel \neq g), $c'_{2eu}$ : region = EU \rightarrow (fuel = e \rightarrow coupling = no), $c'_{3eu}$ : region = EU \rightarrow (fuel = d \rightarrow type \neq cit)}

Note that the solution (configuration) spaces of the contextualized feature models $FMEU'_{old}$ and $FMUS'_{old}$ are the same as those of the original ones (assuming a corresponding context setting, e.g., region = EU). Following this argumentation, solutions($FMEU_{old}$) $\cup$ solutions($FMUS_{old}$) = solutions($FMEU'_{old}$ $\cup$ $FMUS'_{old}$) which supports our goal of achieving a semantics-preserving merging of the original knowledge bases (see Table 1).

The algorithmic approach to support such a semantics-preserving merging is shown in Algorithm 1 (MERGEFM) which itself is a FLAMA [24] prototype implementation. In a first step (starting with line 6 of MERGEFM), those constraints in the contextualized original knowledge bases

<footnote n="1">¹The feature name abbreviations of $FMEU_{old}$ and $FMUS_{old}$ are defined in Figure 1.</footnote>

<footnote n="2">²In general, contexts can be represented by a set of variables (i.e., not necessarily one).</footnote>
(in Algorithm 1 denoted as $FM'_1$ and $FM'_2$) can be decontextualized where such a contextualization is not needed (c is a decontextualized version of c'): if $\neg c$ is consistent with $FM'_1 \cup FM'_2$, there (obviously) exist solutions supporting $\neg c$. In such a case, the constraint c must be added in a contextualized fashion to the resulting knowledge base $FM$, since some feature model configuration (in the other knowledge base) supports $\neg c$. If $\neg c$ is inconsistent with $FM'_1 \cup FM'_2$, c can be added in decontextualized fashion to the resulting knowledge base $FM$. In a second step (starting with line 14 of Algorithm 1), each constraint of the resulting knowledge base has to be checked for redundancy: in a logical sense, a constraint c can be regarded as redundant if $FM - \{c\}$ is inconsistent with $\neg c$ which means that the constraint does not reduce the solution space of $FM$ and thus logically follows from the constraints in $FM$ (and can be deleted from the constraints in $FM$).

<caption>**Algorithm 1 MERGEFM($FM'_1, FM'_2$): $FM$**</caption>

1: $\{FM'_1, FM'_2\}$: two contextualized and consistent feature models
2: $\{c'\}$: constraint c in contextualized form
3: $\{FM\}$: feature model as a result of MERGEFM
4: $FM \leftarrow \{\}$;
5: $FM' \leftarrow FM'_1 \cup FM'_2$;
6: **for all** $c' \in FM'$ **do**
7: &nbsp;&nbsp;&nbsp;&nbsp;**if** inconsistent($\{\neg c\} \cup FM' \cup FM$) **then**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$FM \leftarrow FM \cup \{c'\}$;
9: &nbsp;&nbsp;&nbsp;&nbsp;**else**
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$FM \leftarrow FM \cup \{c'\}$;
11: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
12: $FM' \leftarrow FM' - \{c'\}$;
13: **end for**
14: **for all** $c \in FM$ **do**
15: &nbsp;&nbsp;&nbsp;&nbsp;**if** inconsistent($\{FM - \{c\}\} \cup \{\neg c\}$) **then**
16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$FM \leftarrow FM - \{c'\}$;
17: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
18: **end for**
19: **return** $FM$;

When applying Algorithm 1 to $FMUS_{old}$ and $FMEU_{old}$, the resulting knowledge base $FM_{new}$ looks like as follows. In the resulting knowledge base, the constraint $c'_{2us}$ has been decontextualized. Also, as a result of applying Algorithm 1, constraint $c'_{2eu}$ can be regarded as redundant and thus can be deleted from $FM_{new}$.$^3$

* $FM_{new}$: $\{region(US,EU), type(lim,com,cit,suv), color(b,w), engine(1l, 1.5l, 2l), fuel(d, e, g, h), coupling(yes,no), c'_{1us} : region = US \rightarrow (fuel \neq h), c'_{2us} : fuel = e \rightarrow coupling = no, c'_{3us} : region = \}$

$US \rightarrow (fuel = d \rightarrow color = b), c'_{eu} : region = EU \rightarrow (fuel \neq g), c'_{3eu} : region = EU \rightarrow (fuel = d \rightarrow type \neq cit)}$

On the algorithmic level, the resulting knowledge base $FM_{new}$ is represented in terms of a constraint satisfaction problem. One possibility of representing the integrated knowledge base as the resulting integrated feature model is depicted in Figure 2.

## 4. Performance Evaluation

In this section, we discuss the results of an initial performance analysis we have conducted to evaluate MERGEFM (Algorithm 1)$^4$. For this analysis, we applied 8 real-world variability models with varying sizes collected from the S.P.L.O.T. feature model repository [25] and the Diverso Lab's benchmark$^5$ [26]. Table 4 shows the characteristics of these models (denoted as $\phi$). In order to generate “to-be-merged” feature models ($FM'_1$ and $FM'_2$) with different shares of contextualized constraints from individual $\phi$s, we determined the needed number of relationships or cross-tree constraints. We then modified these selected relationships/cross-tree constraints by changing their type, for example, changing mandatory to optional, changing alternative to or, or changing requires to excludes. The resulting models ($FM'_1 \cup FM'_2 = FM'$) are represented as constraint satisfaction problems [19] that differ individually in terms of the number of constraints (#constraints) and the degree of contextualization (expressed as percentages in Tables 2 and 3). In order to take into account deviations in time measurements, we repeated each experimental setting 10 times where in each repetition cycle the constraints in the individual (contextualized) knowledge bases $FM'$ were ordered randomly. All analyses have been conducted with an Apple M1 Pro (8 cores) computer with 16-GB RAM. For evaluation purposes, we used the CHOCO solver$^6$ to perform the needed consistency checks.

The number of consistency checks needed for decontextualization is linear in terms of the number of constraints in $FM'$. A performance evaluation of MERGEFM with different knowledge base sizes and degrees of contextualized constraints in $FM$ is depicted in Table 2. In MERGEFM, the runtime (measured in terms of milliseconds needed by the constraint solver$^7$ to find a solution) increases with the number of constraints in $FM'$ and decreases with the number of contextualized constraints in

<footnote>$^3$Alternatively, $c'_{2us}$ could be deleted as a redundant constraint (instead of $c'_{2eu}$).</footnote>

<footnote>$^4$The dataset, the implementation of algorithms, and evaluation programs can be found at https://github.com/AIG-ist-tugraz/FMMerging.</footnote>

<footnote>$^5$https://github.com/flamapy/benchmarking</footnote>

<footnote>$^6$choco-solver.org</footnote>

<footnote>$^7$For the purposes of our evaluation we generated variability models represented as constraint satisfaction problems formulated using the CHOCO constraint solver - www.choco-solver.org.</footnote>
<figure><img src="image_41.png" /><figcaption>**Figure 2:** Example integrated feature model derived from *FM*<sub>new</sub>. This model includes contextual information (the region) represented as feature(s). Simple contextualized constraints such as *c*'<sub>lus</sub> : region = US → (fuel ≠ h) are translated directly into a corresponding feature model constraint (as excludes relationship), for the representation of more complex constraints such as *c*'<sub>seu</sub> : region = EU → (fuel = d → type ≠ c), the corresponding feature model constraint is textually annotated with the context information (e.g., region=EU). This graphical representation of contexts in feature models follows the idea of contextual diagrams as introduced by Felfernig et. al [23].</figcaption></figure>

**Table 2**

Avg. runtime (in seconds) of MERGEFM measured with different configuration knowledge base sizes (of $FM'_1$ and $FM'_2$) and shares of related contextualized constraints (10-50% contextualization).

<table><thead><tr><th>feature model (φ)</th><th>#constraints(φ)</th><th>10%</th><th>20%</th><th>30%</th><th>40%</th><th>50%</th></tr></thead><tbody><tr><td>IDE</td><td>13</td><td>0.008</td><td>0.007</td><td>0.007</td><td>0.006</td><td>0.006</td></tr><tr><td>Arcade</td><td>66</td><td>0.060</td><td>0.056</td><td>0.054</td><td>0.052</td><td>0.054</td></tr><tr><td>FQA</td><td>101</td><td>2.560</td><td>2.341</td><td>2.794</td><td>2.812</td><td>3.684</td></tr><tr><td>Invest</td><td>233</td><td>3.018</td><td>3.860</td><td>4.879</td><td>5.781</td><td>5.915</td></tr><tr><td>Win8</td><td>405</td><td>154.825</td><td>171.516</td><td>165.988</td><td>158.998</td><td>149.323</td></tr><tr><td>EMB</td><td>1,029</td><td>1,621</td><td>1,361</td><td>1,138</td><td>1,043</td><td>972</td></tr><tr><td>EA</td><td>2,670</td><td>3,810</td><td>3,870</td><td>3,899</td><td>4,023</td><td>4,032</td></tr><tr><td>Linux</td><td>13,972</td><td>45,641</td><td>52,711</td><td>47,516</td><td>56,536</td><td>57,034</td></tr></tbody></table>

**Table 3**

Avg. runtime (msec) of the merged configuration knowledge bases (FM) to calculate a configuration measured with different knowledge base sizes (of FM) and shares of contextualized constraints in FM (10-50% contextualization).

<table><thead><tr><th>feature model (φ)</th><th>#constraints(φ)</th><th>10%</th><th>20%</th><th>30%</th><th>40%</th><th>50%</th></tr></thead><tbody><tr><td>IDE</td><td>13</td><td>0.050</td><td>0.042</td><td>0.039</td><td>0.037</td><td>0.037</td></tr><tr><td>Arcade</td><td>66</td><td>0.069</td><td>0.057</td><td>0.060</td><td>0.053</td><td>0.055</td></tr><tr><td>FQA</td><td>101</td><td>0.072</td><td>0.069</td><td>0.071</td><td>0.072</td><td>0.079</td></tr><tr><td>Invest</td><td>233</td><td>4.755</td><td>2.992</td><td>2.742</td><td>2.346</td><td>2.293</td></tr><tr><td>Win8</td><td>405</td><td>3.832</td><td>4.058</td><td>5.385</td><td>4.695</td><td>4.413</td></tr><tr><td>EMB</td><td>1,029</td><td>22.034</td><td>24.190</td><td>25.029</td><td>25.603</td><td>26.980</td></tr><tr><td>EA</td><td>2,670</td><td>40.501</td><td>41.227</td><td>43.741</td><td>45.311</td><td>51.483</td></tr><tr><td>Linux</td><td>13,972</td><td>143.698</td><td>199.822</td><td>143.756</td><td>159.515</td><td>112.986</td></tr></tbody></table>

**Table 4**

Feature models used for MERGEFM evaluation (IDE=IDE product line, Arcade=Arcade Game PL, FQA=Feature model for Functional Quality Attributes, Invest=Feature model for Decision-making for Investments on Enterprise Information Systems, Win8=Accessibility options provided by Windows 8 OS, EMB=EMB Toolkit, EA=EA 2468, Linux=Linux kernel version 2.6.33.3).

<table><thead><tr><th>feature model (φ)</th><th>IDE</th><th>Arcade</th><th>FQA</th><th>Invest</th><th>Win8</th><th>EMB</th><th>EA</th><th>Linux</th></tr></thead><tbody><tr><td>#features</td><td>14</td><td>61</td><td>178</td><td>366</td><td>451</td><td>1,179</td><td>1,408</td><td>6,467</td></tr><tr><td>#hierarchical constraints</td><td>11</td><td>32</td><td>92</td><td>41</td><td>267</td><td>862</td><td>1,389</td><td>6,322</td></tr><tr><td>#cross-tree constraints</td><td>2</td><td>34</td><td>9</td><td>192</td><td>138</td><td>167</td><td>1,281</td><td>7,650</td></tr><tr><td>#CSP constraints</td><td>13</td><td>66</td><td>101</td><td>233</td><td>405</td><td>1,029</td><td>2,670</td><td>13,972</td></tr></tbody></table>
FM. The increase in efficiency can be explained by the fact that a higher degree of contextualization includes more situations where the inconsistency check in Line 7 (Algorithm 1) terminates earlier (a solution has been found) compared to situations where no solution could be found. In addition, Table 3 indicates that the performance of solution search does not differ depending on the degree of contextualization in the resulting knowledge base FM.

Consequently, integrating individual variability models can trigger the following improvements. (1) De-contextualization in FM can lead to less cognitive efforts when adapting / extending knowledge bases (due to a potentially lower number of constraints [27] and a lower degree of contextualization). (2) Reducing the overall number of constraints in FM can also improve runtime performance of the resulting integrated knowledge base.

## 5. Threats to Validity

We are aware that our evaluation is in fact based on real-world feature models, however, synthesized variants thereof have been used for MERGEFM evaluation purposes. Furthermore, our approach is based on the assumption that the “to-be-merged” feature models have the same set of features, i.e., we assume feature equivalence. In this context, we assume that in real-world scenarios further streamlining tasks (e.g., feature name alignment) have to be completed before MERGEFM can be activated. Our basic assumption behind redundancy elimination and de-contextualization in MERGEFM is that the understandability and maintainability of feature models can be improved – although already confirmed by related work [27], further research is needed to better understand major impact factors that make feature models (and underlying knowledge bases) easier to understand and maintainable.

## 6. Conclusions and Future Work

In this paper, we have introduced an approach to the consistency-based merging of variability models represented as constraint satisfaction problems. The approach helps to build semantics-preserving feature models in the sense that the solution spaces of the resulting knowledge bases (result of the merging process) correspond to the union of the solution spaces of the original knowledge bases. Such an approach can be useful in the mentioned integration scenario but as well in situations where different parts (representing different contexts) of a knowledge are developed in a de-centralized fashion and integrated thereafter. Besides the preservation of the original semantics, our approach also helps to make the resulting

knowledge base compact in the sense of deleting redundant constraints and not needed contextual information. The runtime performance of our approach is shown on the basis of a first performance analysis with real-world feature models. Future work will include the evaluation of our concepts with further knowledge bases and the development of alternative merging algorithms with the goal to further improve runtime performance. Furthermore, we will evaluate different alternative feature model representations that help to represent contextualized constraints – one such representation has been discussed in this paper.

## References

[1] K. Kang, S. Cohen, J. Hess, W. Novak, S. Peterson, Feature-oriented domain analysis feasibility study (foda), Technical Report, CMU/SEI-90-TR-021 (1990).

[2] K. Czarnecki, S. Helsen, U. Eisenecker, Formalizing cardinality-based feature models and their specialization, SoftwareProcess: Improvement and Practice 10 (2005) 7–29.

[3] A. Felfernig, A. Falkner, D. Benavides, Feature Models: AI-Driven Design, Analysis and Applications, SpringerBriefs in Computer Science, Springer, Cham, 2024. doi:10.1007/978-3-031-61874-1.

[4] L. Galarraga, N. Preda, F. Suchanek, Mining rules to align knowledge bases, in: Proceedings of the 2013 Workshop on Automated Knowledge Base Construction, San Francisco, CA, 2013, pp. 43–48.

[5] J. Delgrande, T. Schaub, A consistency-based framework for merging knowledge bases, Journal of Applied Logic 5 (2007) 459–477.

[6] P. Liberatore, M. Schaerf, Arbitraton (or how to merge knowledge bases), IEEE Transactions on Knowledge and Data Engineering 10 (1998) 76–90.

[7] R. Reiter, A theory of diagnosis from first principles, AI Journal 23 (1987) 57–95.

[8] M. Acher, P. Collet, P. Lahire, R. France, Composing feature models, in: M. van den Brand, D. Gašević, J. Gray (Eds.), Software Language Engineering, Springer, Berlin, Heidelberg, 2010, pp. 62–81.

[9] V. Bischoff, K. Farias, L. Gonçales, J. Victória Barbosa, Integration of feature models: A systematic mapping study, Information and Software Technology 105 (2019) 209–225. URL: https://www.sciencedirect.com/science/article/pii/S0950584916302178. doi:https://doi.org/10.1016/j.infsof.2018.08.016.

[10] P. van den Broek, I. Galvao, J. Noppen, Merging feature models, in: 15th International Software Product Line Conference, Jeju Island, South Korea, 2010, pp. 83–90.
[11] J. Carbonnel, M. Huchard, A. Miralles, C. Nebut, Feature model composition assisted by formal concept analysis, in: 12th International Conference on Evaluation of Novel Approaches to Software Engineering, 2017, pp. 27–37. doi:10.5220/0006276600270037.

[12] P. Y. Schobbens, P. Heymans, J. C. Trigaux, Feature Diagrams: A Survey and a Formal Semantics, in: 14th IEEE International Requirements Engineering Conference (RE’06), Minneapolis/St. Paul, MN, USA, 2006, pp. 139–148. doi:10.1109/RE.2006.23.

[13] S. Segura, D. Benavides, A. Ruiz-Cortés, P. Trinidad, Automated Merging of Feature Models Using Graph Transformations, in: Generative and Transformational Techniques in Software Engineering II, volume 5235 of Lecture Notes in Computer Science, Springer, 2006, pp. 139–148. doi:10.1109/10.1007/978-3-540-88643-3_15.

[14] M. Acher, H. Martin, L. Lesoil, A. Blouin, J. Jézéquel, D. Khelladi, E. Djamel, O. Barais, J. Pereira, Feature Subset Selection for Learning Huge Configuration Spaces: The Case of Linux Kernel Size, in: 26th ACM International Systems and Software Product Line Conference - Volume A, ACM, 2022, pp. 85–96. URL: https://doi.org/10.1145/3546932.3546997. doi:10.1145/3546932.3546997.

[15] B. Nuseibeh, J. Kramer, A. Finkelstein, Viewpoints: meaningful relationships are difficult!, in: 25th International Conference on Software Engineering, 2003, pp. 676–681. doi:10.1109/ICSE.2003.1201254.

[16] E. A. Aydin, H. Oguztuzun, A. H. Dogru, A. S. Karatas, Merging Multi-view Feature Models by Local Rules, in: 9th International Conference on Software Engineering Research, Management and Applications, Baltimore, MD, USA, 2011, pp. 140–147. doi:10.1109/SERA.2011.34.

[17] T. Thüm, D. Batory, C. Kästner, Reasoning about edits to feature models, in: 31st International Conference on Software Engineering, ICSE '09, IEEE Computer Society, USA, 2009, pp. 254–264. URL: https://doi.org/10.1109/ICSE.2009.5070526. doi:10.1109/ICSE.2009.5070526.

[18] S. She, U. Ryssel, N. Andersen, A. Wąsowski, K. Czarnecki, Efficient synthesis of feature models, Information and Software Technology 56 (2014) 1122–1143. URL: https://www.sciencedirect.com/science/article/pii/S0950584914000238. doi:https://doi.org/10.1016/j.infsof.2014.01.012.

[19] E. Tsang, Foundations of Constraint Satisfaction, Academic Press, London, 1993.

[20] D. Benavides, S. Segura, A. Ruiz-Cortes, Automated analysis of feature models 20 years later: A literature review, Information Systems 35 (2010) 615–636.

[21] A. Felfernig, L. Hotz, C. Bagley, J. Tiihonen, Knowledge-based Configuration: From Research to Business Cases, 1st ed., Morgan Kaufmann Publishers, 2014.

[22] D. Benavides, P. Trinidad, A. Ruiz-Cortes, Using constraint programming to reason on feature models, in: 17th International Conference on Software Engineering and Knowledge Engineering (SEKE'2005), Taipei, Taiwan, 2005, pp. 677–682.

[23] A. Felfernig, D. Jannach, M. Zanker, Contextual diagrams as structuring mechanisms for designing configuration knowledge bases in uml, in: 3rd International Conference on the Unified Modeling Language (UML2000), volume 1939 of Lecture Notes in Computer Science, Springer, York, UK, 2000, pp. 240–254.

[24] J. Galindo, J. Horcas, A. Felfernig, D. Fernandez-Amoros, D. Benavides, Flama: A collaborative effort to build a new framework for the automated analysis of feature models, in: 27th ACM International Systems and Software Product Line Conference - Volume B, SPLC '23, Association for Computing Machinery, New York, NY, USA, 2023, pp. 16–19. URL: https://doi.org/10.1145/3579028.3609008. doi:10.1145/3579028.3609008.

[25] M. Mendonca, M. Branco, D. Cowan, S.P.L.O.T.: Software Product Lines Online Tools, in: Proceedings of the 24th ACM SIGPLAN Conference Companion on Object Oriented Programming Systems Languages and Applications, OOPSLA '09, ACM, New York, NY, USA, 2009, pp. 761–762. doi:10.1145/1639950.1640002.

[26] R. Heradio, D. Fernandez-Amoros, J. A. Galindo, D. Benavides, D. Batory, Uniform and scalable sampling of highly configurable systems, Empirical Software Engineering 27 (2022) 44.

[27] A. Felfernig, M. Mandl, A. Pum, M. Schubert, Empirical knowledge engineering: cognitive aspects in the development of constraint-based recommenders, in: Proceedings of the 23rd International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE'10, Springer-Verlag, Berlin, Heidelberg, 2010, pp. 631–640.
# An extensive comparison of preprocessing methods in the context of configuration space learning

Damian Garber¹*, Alexander Felfernig¹, Viet-Man Le¹, Tamim Burgstaller¹ and Merfat El-Mansi¹

¹Graz University of Technology, Inffeldgasse 16b, Graz, Styria, Austria

**Abstract**

One of the core goals in the research field of configuration space learning is building precise predictive models that allow for reliably estimating the performance of a configuration without requiring costly tests. The models used for this purpose are usually machine learning-based. However, the models show significant deviations in their performance depending on the investigated Software Product Line (SPL), the applied data preprocessing, and the number of sample configurations collected. Thus, we investigate the impact of different preprocessing methods and their behavior when using different SPLs, machine learning models, and sample sizes. Performance comparisons on this scale are usually not conducted due to their prohibitively expensive execution time requirements, even for smaller SPLs. Thus, we used three fully enumerated spaces as our training data, which allows for more generalized results. Our results show that the average factors between the worst and best-performing preprocessing methods are 2.05 (BerkeleyDBC), 1.17 (7z), and 1.84 (VP9). Further, no single preprocessing method tested was able to outperform all others, nor was this the case within one specific SPL or model type. This underlines the importance of testing new approaches with multiple preprocessing methods.

**Keywords**

Configuration Space Learning, Machine Learning, Preprocessing

## 1. Introduction

The discovery of configurations that optimize the performance of any given Software Product Line (SPL) is one of the core goals of configuration space learning. The performance of a model can take many forms and rely heavily on the use case. For instance, one may optimize a SPL to perform a core task very efficiently or optimize for the size of the compiled SPL binary. This optimization usually takes place in steps. The first step is sampling configurations from the configuration space of the SPL and measuring the target property, which often entails compiling and running tests or benchmarks, a very time and resource-intensive undertaking. One can use these samples to train a prediction model, which is then used to find a configuration that optimizes the target property. In this paper, we focus on the creation and training of the prediction model. Many factors can impact the performance of a performance prediction model for SPLs, from the SPL itself to the sampling approach used to collect the training data. However, our focus lies on one

of the factors often neglected in SPL performance prediction: Preprocessing. We will define any necessary terms used in this paper in Section 2. Preprocessing has proven itself in many other domains that employ machine learning-based prediction models. However, literature reviews such as Gong and Chen [1] show that less than half of the investigated studies within the field of configuration performance learning use preprocessing, further discussed in Section 3. Accordingly, we thus conduct an in-depth investigation on the influence of preprocessing on performance prediction models for SPLs. To this end, we measure the performance of 4 preprocessing methods in the context of 3 SPLs, 5 machine learning models, and 20 different sizes of training sets. We discuss the details of the experimental evaluation in Section 4, followed by a discussion of the results in Section 5.

## 2. Definitions

Software Product Line (SPL). SPLs, as a concept started to gain widespread popularity at the beginning of the 2000s [2]. Engström and Runeson [3] describe SPLs as the paradigm of forming derivate products from a set of generic components. A SPL has multiple features, each supporting an individual domain of values, which allows for the generation of diverse products using the same components.

Configuration. In the context of a SPL, a configuration defines for each feature the corresponding feature value. However, there may exist additional constraints within

ConfWS'24: 26th International Workshop on Configuration, Sep 2-3,
2024, Girona, Spain

*Corresponding author.

dgarber@ist.tugraz.at (D. Garber);

alexander.felfernig@ist.tugraz.at (A. Felfernig);

vietman.le@ist.tugraz.at (V. Le); tamim.burgstaller@ist.tugraz.at

(T. Burgstaller); merfat.elmansi@un.org (M. El-Mansi)

0009-0005-0993-0911 (D. Garber); 0000-0003-0108-3146

(A. Felfernig); 0000-0001-5778-975X (V. Le); 0009-0007-4522-8497

(T. Burgstaller); 0009-0005-2695-4210 (M. El-Mansi)

<figure><img src="image_42.png" /></figure>

© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0).
the SPL. Thus, we speak of a valid configuration if none of the assigned values is inconsistent with any of the constraints.

*Configuration Space.* The configuration space of a SPL describes the space spanned by all valid configurations of the SPL. The size of configuration spaces commonly grows exponentially with the number of features, and we speak of colossal configuration spaces if its size is $\gg 10^{10}$ [4].

## 3. Related Work

The three fully enumerated configuration spaces provided by Oh et al.[4] facilitate the comprehensive performance analysis and comparison we conducted. They use them to show that relatively simple approaches like uniform random sampling can outperform well-established tools like SPL Conquerer [5] to find near-optimal configurations for SPLs. We build on this idea and conduct a comparison of different preprocessing methods. The reasoning behind conducting this comparison is the alarming result of Gong and Chen [1]. They performed a literature review on deep configuration performance learning and reported that 44 out of 85 investigated studies used the data as it was without any preprocessing. This limited utilization implies a lack of awareness of the impact of preprocessing methods. This lack of awareness may then aggravate the difficulty of reproducing and validating the results of published works. Dacrema et al. [6], for example, investigated 18 new approaches published recently, of which they could only reproduce 7. Of the 7 reproduced approaches, they showed that they can outperform 6 by using relatively simple other approaches. The importance of preprocessing methods in many domains has long since been established. Wu et al.[7], for example, shows that preprocessing improves the performance of streamflow forecasts. Rasekhi et al. [8] report improvements in the prediction of epileptic seizures by using preprocessing.

We further include in our tests different sample sizes, which allows us to investigate the reaction of the preprocessing methods to changing sample sizes. Acher et al.[9] sampled and measured 95854 Linux configurations, a minute fraction of the configuration space of $2^{15000}$ ($2.818 \times 10^{4515}$) configurations spaned by Linux. They reported to have needed 15000 hours of computation time to collect the samples. Guo et al. [10] uses tree-based models to predict configuration performances. Martin et al.[11] focus on using transfer learning across different versions of the Linux kernel to predict the performances of the versions. They mention preprocessing only for encoding configurations into formats compatible with their machine-learning approach.

The literature reviews of Gong and Chen [1] and Pereira

<table><caption>**Table 1**
Specifications of the machine used in the experiments</caption><thead><tr><td>Name</td><td>Value</td></tr></thead><tbody><tr><td>Vendor</td><td>Lenovo</td></tr><tr><td>Product</td><td>20N6001GGE</td></tr><tr><td>CPU</td><td>Intel Core i7-8665U (4x 1,90 GHz)</td></tr><tr><td>RAM</td><td>32GB (DDR4)</td></tr><tr><td>OS</td><td>Manjaro Linux</td></tr><tr><td>Kernel version</td><td>6.1.80.-1-MANJARO</td></tr></tbody></table>

et al. [12] named multiple data sampling approaches used in configuration performance learning. However, both identified random sampling as the most popular approach. Pereira et al. [13] conducted a dedicated study on sampling approaches for learning configuration spaces. They suggest using uniform random sampling as long as it is computationally feasible. Accordingly, we adapted it for our comparison.

## 4. Experimental Setup

This section will discuss the exact experimental setup for data collection and which machine learning models, preprocessing methods, and datasets we were using. All measurements were collected using the same machine with specifications as they are listed in Table 1. We use Mean Absolute Percentage Error (MAPE) to evaluate the model performances, which is one of the most commonly used metrics in literature [1] [12] [13]. The code was implemented in Python using the widely used scikit-learn<fnref n="1" /> library [14]. We used Uniform Random Sampling (URS) to generate the training sets of different sizes for model learning. We can perform URS by selecting configurations randomly from the set of valid configurations. The size of the training sets range from 50 to 1000 in steps of 50. However, the tests for all models and preprocessing methods use, within the same iteration, the same training set of a specific size. After the performance of all models using the preprocessing applied to the training sets is measured, these measurements are repeated 15 times, each time with new training sets selected with URS. The average of the resulting MAPE values in the 15 iterations is the value we use when we discuss the results.

### 4.1. Datasets

For our comparison, we use a dataset of fully enumerated configuration spaces. Thus, the dataset includes all valid configurations for a given SPL. In addition, a value, like execution times of benchmarks or similar, representing the performance of each configuration was measured. We use three such datasets based on three configurable

<footnote n="1">¹https://scikit-learn.org/stable/index.html</footnote>
software projects: **BerkeleyDBC**<fnref n="2" />, **7z**<fnref n="3" />, and **VP9**<fnref n="4" />. The datasets are used in the work of Oh et al.[4], and they were made available in their resources<fnref n="5" />. Oh et al.[4] provided the following description of the three datasets.

**BerkeleyDBC** is an embedded database system with 9

<table><caption>**Table 2**</caption><thead><tr><th>Name</th><th>Domain</th></tr></thead><tbody><tr><td>DIAGNOSTIC</td><td>0 | 1</td></tr><tr><td>HAVE_STATISTICS</td><td>0 | 1</td></tr><tr><td>HAVE_REPLICATION</td><td>0 | 1</td></tr><tr><td>HAVE_CRYPTO</td><td>0 | 1</td></tr><tr><td>HAVE SEQUENCE</td><td>0 | 1</td></tr><tr><td>HAVE_VERIFY</td><td>0 | 1</td></tr><tr><td>HAVE_HASH</td><td>0 | 1</td></tr><tr><td>CACHESIZE</td><td>CS16MB | CS32MB | CS64MB | CS512MB</td></tr><tr><td>PAGESIZE</td><td>PS1K | PS4K | PS8K | PS16K | PS32K</td></tr></tbody></table>

BerkeleyDBC variable names and their respective domains

variables and 2560 configurations. Benchmark response times were measured. We visualize the variable names and their domains in Table 2.

7z is a file archiver with 9 variables and 68640 configurations. Compression times were measured. We visualize the variable names and their domains in Table 3.

VP9 is a video encoder with 12 variables and 216000 configurations. Video encoding times were measured. We visualize the variable names and their domains in Table 4.

Although these three configuration spaces do not approach the sizes of colossal configuration spaces like Linux, which spans a configuration space with 2¹⁵⁰⁰⁰ configurations[9], they still have sizes where an enumeration is no longer an option, and thus fall in the purview of the research field of configuration space learning. Depending on the complexity of the tests and the underlying system, procuring very few samples may already be very costly. Acher et al.[9], for example, reported 15000 hours of computation to build and measure 95854 Linux configurations. We selected these datasets due to two main advantages. The first is avoiding the extreme computation times of collecting such data, and the second is that using them allows us to test multiple iterations of training sets of different sizes.

## 4.2. Models

We selected five different types of machine-learning models, each representing a different general approach to

<table><caption>**Table 3**</caption><thead><tr><th>Name</th><th>Domain</th></tr></thead><tbody><tr><td>root</td><td>0 | 1</td></tr><tr><td>CompressionMethod</td><td>LZMA | LZMA2 | PPMd | BZip2 | Deflate</td></tr><tr><td>x</td><td>x_0", "x_2 | x_4 | x_6 | x_8 | x_10</td></tr><tr><td>BlockSize</td><td>BlockSize_1", "BlockSize_2 | BlockSize_4 | BlockSize_8 | BlockSize_16 | BlockSize_32 | BlockSize_64 | BlockSize_128 | BlockSize_256 | BlockSize_512 | BlockSize_1024 | BlockSize_2048 | BlockSize_4096</td></tr><tr><td>Files</td><td>Files_0 | Files_10 | Files_20 | Files_30 | Files_40 | Files_50 | Files_60 | Files_70 | Files_80 | Files_90 | Files_100</td></tr><tr><td>tmOff</td><td>0 | 1</td></tr><tr><td>mtOff</td><td>0 | 1</td></tr><tr><td>HeaderCompressionOff</td><td>0 | 1</td></tr><tr><td>filterOff</td><td>0 | 1</td></tr></tbody></table>

7z variable names and their respective domains

maximize the usefulness of our results. In our implementations, we used models from the scikit-learn<fnref n="6" /> python library [14]. For the sake of reproducibility, we did not perform any parameter tuning on the models and used their respective default settings if not explicitly stated otherwise.

The first model is a Multi-Layer Perceptron (MLP) model, a feedforward neural network approach. We set the maximum of iterations to 1000 and activated early stopping for our tests. MLPs are, according to Gong and Chen [1], the most popular approach when conducting deep configuration performance learning. However, it is a very data-intensive approach that needs comparatively large training sets to perform well.

The second model is a K-Nearest Neighbors (KNN) model, a memory-based approach. The model finds the k-nearest neighbors to a configuration from the training set, in our case the default value 5. The KNN model predicts the performance of the configuration by calculating the average of the performances of the configuration's k nearest neighbors. In our case, the average was weighted by the distance between the neighbor and the configuration. The third model is a Random Forest (RF), an ensemble method employing several decision trees generated using the training data to predict the performance of an un-

<footnote n="2">²https://www.oracle.com/database/technologies/related/berkeleydb.html</footnote>

<footnote n="3">³https://www.7-zip.org/download.html</footnote>

<footnote n="4">⁴https://www.webmproject.org/vp9/</footnote>

<footnote n="5">⁵https://zenodo.org/records/7776627</footnote>

<footnote n="6">⁶https://scikit-learn.org/stable/index.html</footnote>
<table><caption>**Table 4**

VP9 variable names and their respective domains</caption><thead><tr><th>Name</th><th>Domain</th></tr></thead><tbody><tr><td>root</td><td>0 | 1</td></tr><tr><td>lagInFrames</td><td>lagInFrames_0 | lagInFrames_8 | lagInFrames_16</td></tr><tr><td>endUsage</td><td>variableBitrate | constantBitrate | constrainedQuality</td></tr><tr><td>AdaptiveQuantizationMode</td><td>off | variance | complexity | cyclicRefresh</td></tr><tr><td>TileColumns</td><td>TileColumns_0 | TileColumns_3 | TileColumns_6</td></tr><tr><td>cpuUsed</td><td>cpuUsed_0 | cpuUsed_2 | cpuUsed_4 | cpuUsed_6 | cpuUsed_8</td></tr><tr><td>Threads</td><td>Threads_2 | Threads_4 | Threads_6 | Threads_8 | Threads_10</td></tr><tr><td>bitRate</td><td>bitRate_300 | bitRate_600 | bitRate_900 | bitRate_1200 | bitRate_1500</td></tr><tr><td>FrameBoost</td><td>0 | 1</td></tr><tr><td>lossless</td><td>0 | 1</td></tr><tr><td>AutoAltRef</td><td>0 | 1</td></tr><tr><td>Quality</td><td>good | realtime</td></tr></tbody></table>

known data point. We use bagged trees, which means we train all underlying decision trees to solve the problem using all features. The final result is in the context of classification decided based on a majority vote. However, in our context of regression, we calculate the final result by taking the mean of all results produced by the decision trees.

The fourth model is a Support Vector Machine (SVM), a well-established model based on statistical learning frameworks. We use a radial basis function as our kernel type.

The final model is an ElasticNet (EN) model, a derivate of linear regression models. The model combines L1 and L2 priors as a regularizer.

## 4.3. Preprocessing

We used several preprocessing methods to test their impact on the different models and training sizes. For the sake of this comparison, we do not distinguish between actual preprocessing methods like Standardization and encodings such as the One Hot Encoding.

The first preprocessing method discussed we call default (DEF). It provides a baseline for mostly unaltered data and leaves numeric values untouched. The boolean values are, however, encoded with 0 and 1 for false and true, respectively. If all values of a domain can be converted

into numbers this is done (e.g. CS32MB = 32, Table 2). If this is not possible, the string values are encoded using label encoding [15, 16], which assigns an increasing numeric value for each unique string in a domain. This format is the default state of the data. Thus, we apply all preprocessing methods mentioned hereafter to the data in this format.

The second preprocessing method is Min Max Scaling (MMS) [17, 18], which reduces the scale of a given feature to be between 0 and 1. We achieve this by applying Equation 1 on every feature of the configuration, where min and max are the minimum and maximum recorded numbers for this feature, respectively. When we apply this to the features encoded using label encoding, the result is a derivative of the former called scaled label encoding [19, 20].

$$f_i(x_i) = \frac{x_i - min_i}{max_i - min_i} \qquad (1)$$

The third preprocessing method is Standardization (STD) [21, 22], which is achieved by calculating the mean and standard deviation of each feature and applying Equation 2

$$f_i(x_i) = \frac{x_i - \mu_i}{\sigma_i} \qquad (2)$$

This results in the mean of every feature in the training set being now 0 and the standard deviation being 1.

The final preprocessing method is One Hot Encoding (OHE) [23, 24], which changes the domain of all features to a boolean domain. We achieve this by increasing the dimensions of the data by an encoding of the domain. Thus, if, for example, feature *f* has the domain 0, 6, 12, it would have been replaced with the features *f*₀, *f*₆, *f*₁₂ each of the three resulting boolean features are mutually exclusive and encode one possible value assigned to feature *f*.

# 5. Results

In this section, we showcase the measurements collected as described in the experimental setup section and discuss them. To this end, we will discuss the results of each dataset separately and what observations we made.

Firstly, we start with a discussion of our smallest SPL, BerkeleyDBC. All performance results are visualized in Figure 1. In the results for MLP, we see that OHE is performing best among all preprocessing methods regardless of sample size. However, we can also see a shift in the performances of the preprocessing approaches. STD started as the worst-performing preprocessing method. Despite that, with increasing sample size, it outperformed MMS and DEF. Accordingly, the results of STD approached the results of the best performer OHE for the larger sample sizes. However, when looking at Figure 2 and Figure
<figure><img src="image_43.png" /><figcaption>**Figure 1:** The performances of each preprocessing method applied to each model and a comparison between the top performers of each model applied to the BerkeleyDBC dataset.</figcaption></figure>

<figure><img src="image_44.png" /><figcaption>**Figure 2:** The performances of each preprocessing method applied to each model, and a comparison between the top performers of each model applied to the 7z dataset.</figcaption></figure>
<figure><img src="image_45.png" /><figcaption>**Figure 3:** The performances of each preprocessing method applied to each model, and a comparison between the top performers of each model applied to the VP9 dataset.</figcaption></figure>

3, we see that this behavior does not occur in the other datasets, but, in contrast to other approaches, the results of STD remain either relatively stable or improve with increasing sample sizes. We see a similar behavior on a smaller scale with MMS and DEF. MMS performed initially worse than DEF, overtaking it as soon as sample sizes became larger than 200 and achieving similar results from sample sizes 500 and larger. The other models, in contrast, showed more pronounced preferences for preprocessing methods. For the KNN model, DEF was the best-performing preprocessing method, followed by STD, MMS, and OHE. RF showed the best performance of all models with almost indistinguishable differences of 0.01% between the preprocessing methods on average. For the SVM model, DEF performed the worst with comparatively little improvement with larger sample sizes. The remaining preprocessing methods, from worst to best, MMS, STD, and OHE show relatively similar results, improving with increasing sample sizes. For the EN model, OHE performs best, and the remaining three, from worst to best, MMS, DEF, and STD show relatively similar results. The sample size has a comparatively small impact on the performances. Results with sample sizes of 200 and larger only show a minor oscillation and remain otherwise stable. The comparison between models shows that RF outperforms the other models. All models

except for EN show significantly better performances with larger sample sizes. However, MLP was impacted the most by the sample size. It overtook the performance of SVM at a sample size of 450 and EN at 900. Secondly, we will discuss the next larger SPL, 7z. We provide the results for this dataset in Figure 2. The first observation we can make is that the overall quality of the predicted results decreased. This matches our expectations, since we are predicting the performance of a larger SPL using an equivalent setup. Another observation we can make is that three of the five tested models showed strong oscillations in their performances or, for some preprocessing methods, a worsening of the performance with increasing sample size. The MLP model, for example, showed for the best and second best performing preprocessing methods, MMS and STD, respectively, no significant changes with increasing sample sizes. DEF and OHE showed meanwhile a decrease in performance with increasing sample sizes. The EN and SVM models showed strong oscillations with increasing sample sizes. However, the performances of the preprocessing methods all follow that same pattern, which suggests that the cause for this may lie in the model or the SPL rather than the preprocessing approaches. In the case of the SVM, the performances remained very similar. The preprocessing performances in the EN model follow the same oscillation
<table><caption>**Table 5**
Average MAPE value over all tested sample sizes from 50 to 1000 with steps of 50</caption><thead><tr><th>Model</th><th>Preprocessing</th><th>BerkeleyDBC</th><th>7z</th><th>VP9</th></tr></thead><tbody><tr><td>MLP</td><td>DEF</td><td>25.68%</td><td>114.76%</td><td>273.94%</td></tr><tr><td>MLP</td><td>MMS</td><td>26.29%</td><td><strong>99.97%</strong></td><td>144.24%</td></tr><tr><td>MLP</td><td>STD</td><td>31.12%</td><td>99.98%</td><td>129.80%</td></tr><tr><td>MLP</td><td>OHE</td><td><strong>10.27%</strong></td><td>104.41%</td><td><strong>117.11%</strong></td></tr><tr><td>KNN</td><td>DEF</td><td><strong>1.44%</strong></td><td>119.01%</td><td>182.27%</td></tr><tr><td>KNN</td><td>MMS</td><td>4.29%</td><td>82.30%</td><td>158.79%</td></tr><tr><td>KNN</td><td>STD</td><td>2.85%</td><td><strong>78.42%</strong></td><td><strong>124.31%</strong></td></tr><tr><td>KNN</td><td>OHE</td><td>4.47%</td><td>79.99%</td><td>241.55%</td></tr><tr><td>RF</td><td>DEF</td><td><strong>0.54%</strong></td><td>9.51%</td><td>15.14%</td></tr><tr><td>RF</td><td>MMS</td><td>0.55%</td><td>9.54%</td><td><strong>14.97%</strong></td></tr><tr><td>RF</td><td>STD</td><td>0.55%</td><td><strong>9.50%</strong></td><td>15.23%</td></tr><tr><td>RF</td><td>OHE</td><td><strong>0.54%</strong></td><td>10.82%</td><td>18.32%</td></tr><tr><td>SVM</td><td>DEF</td><td>6.44%</td><td>91.46%</td><td>249.59%</td></tr><tr><td>SVM</td><td>MMS</td><td>6.07%</td><td>91.33%</td><td>101.45%</td></tr><tr><td>SVM</td><td>STD</td><td>6.04%</td><td><strong>91.29%</strong></td><td><strong>100.35%</strong></td></tr><tr><td>SVM</td><td>OHE</td><td><strong>6.03%</strong></td><td>91.36%</td><td>116.08%</td></tr><tr><td>EN</td><td>DEF</td><td>5.19%</td><td>176.36%</td><td>246.24%</td></tr><tr><td>EN</td><td>MMS</td><td>5.31%</td><td>177.54%</td><td>273.19%</td></tr><tr><td>EN</td><td>STD</td><td>5.09%</td><td><strong>169.40%</strong></td><td>267.77%</td></tr><tr><td>EN</td><td>OHE</td><td><strong>2.54%</strong></td><td>173.59%</td><td><strong>226.60%</strong></td></tr></tbody></table>

pattern while being displaced with a relatively constant margin along the y-axis, with STD performing best. The KNN model performed as expected, showing constant improvements with increasing sample sizes for all preprocessing methods. However, it is notable that the best performer on the BerkelyDBC dataset DEF performs the worst now, with the former second-best performing STD taking its place as the best performer. The RF model remains again the best performer with a significant margin. The preprocessing performances are again very similar, but STD performs significantly better for the smallest tested sample size, thus outperforming the others.

Thirdly, we will discuss the largest SPL we investigated, VP9. The results collected for VP9 are shown in Figure 3. Our first observation is that the results for VP9 are closer to the results from BerkeleyDBC. There are again some oscillations in the results of MLP, but they are comparatively minor and show a clear trend to improvement with increasing sample sizes. We see again that the performance of the EN model remains unaffected by increasing sample sizes, except for some minor oscillations. The SVM model shows a similar pattern as it did with the BerkeleyDBC dataset. The DEF preprocessing method performs once more the worst and shows as the only method with no significant improvement with increasing sample size. KNN shows to be once more consistent, showing stable improvement with increasing sample size, STD performing best once more. The RF model performs once more best by a significant margin. The preprocessing methods have little impact on its performance, but some improve the prediction performance earlier, the

best performing being MMS.

Finally, we will discuss the results and our observations in general. To this end, we provide the average performances of all models and preprocessing approaches in Table 5. The first observation must be that preprocessing methods have a significant impact on the prediction performances. BerkeleyDBC has an average factor of 2.05 between the best and worst-performing preprocessing methods. In comparison, 7z and VP9 have an average factor of 1.17 and 1.84 respectively. This observation holds for all tested models, even for the best-performer RF. However, RF shows this impact only with the larger SPLs like 7z and VP9. In general, the differences are maximized at low sample sizes and become then smaller with increasing sample sizes. We observe a similar situation with the SVM model, except DEF, which was largely unsuited. DEF was in two out of three tested SPLs performing the worst, showing insignificant improvement with increasing sample sizes. For MLP, KNN, and EN, on the other hand, we can see significant performance differences on every sample size tested, with, in general, more pronounced differences when applying smaller sample sizes. We also observe multiple occasions where misrepresentation of performances could occur when conducting tests with only one preprocessing method. For instance, one can conclude that SVMs outperform MLPs on the BerkeleyDBC dataset for sample sizes smaller or equal to 1000 when conducting tests only with DEF or MMS. However, when testing with STD or OHE, we see that MLP outperforms SVMs on the BerkeleyDBC dataset for sample sizes greater than 650 or 400, respectively. From
this, we conclude that a sound comparison between two
or more predictive models should compare their perfor-
mances when using their best-performing preprocessing
methods. Omitting the preprocessing method used may,
by extension, lead to poorly reproducible results.

MLP showed to work on average best with OHE. The
performance of this model strongly correlated with the
sample size, and it usually started with comparatively
high MAPE scores that became more competitive with
increasing sample sizes. Furthermore, it is prone to os-
cillation. KNN showed to work on average best with
STD. It was one of the most stable and robust models,
achieving constant improvement with increasing sample
sizes, even in the context of SPLs like 7z that triggered
oscillation in most other models. However, its prediction
quality places it in the middle field. RF showed to work
on average best with MMS. This model outperformed
every other model significantly in every aspect we mea-
sured. Its worst performance using the smallest tested
sample size of 50 outperforms, in all but two cases, the
best performances of all other models. This performance
is then improved further with increasing sample size. The
model usually reaches a plateau relatively early on aver-
age at a sample size of 350, after which its improvement
slows significantly. SVM showed to work on average
best with STD. The model improves like RF on average
with a sample size up to 600 steadily, after which the
model starts to plateau in its improvement, except for the
already mentioned DEF. EN showed to work on average
best with OHE. This model showed, on average, com-
paratively minor improvements with increased sample
size.

6. Threats to validity

This paper compared multiple machine learning-based
models and explicitly did not perform any parameter tun-
ing for any one of the models. We used, if not stated
explicitly differently, always the default parameters de-
fined by the scikit-learn⁷ library [14]. Thus, we must
acknowledge that fine-tuning the model parameters, es-
pecially for the more complex models like MLP, likely
will improve the performances of the models employed.
However, the measured results are still valid and valuable
for comparing the model performances concerning the
preprocessing methods and the sizes of the training sets
employed.

7. Conclusion

We tested 15 scenarios of machine learning-based per-
formance prediction in the context of SPLs by measur-

ing the performance of five different machine learning
models on three SPLs with training sets of increasing
sizes. Except for two, all scenarios tested showed, in part,
radical changes in prediction quality depending on the
preprocessing method used. These changes were most
pronounced when we measured the model performances
with only a few samples to use as training sets and be-
came less distinctive with training sets of increased size.
On average, the disparity between the worst and the
best performing preprocessing method were factors of
2.05 (BerkeleyDBC), 1.17 (7z), and 1.84 (VP9). While we
identified the on average best performing preprocessing
methods for each model we tested, we also see, as visu-
alized in Table 5, that no single method outperforms all
others for each dataset, which holds as well if we only
focus on a single model. Thus, having shown both the
significant impact and the inconsistency in the perfor-
mance of preprocessing methods, we draw the following
conclusions. Results that do not state which, if any, pre-
processing method was employed become hard to repro-
duce. Further, the disregard of preprocessing methods
may pose a threat to the validity of results. In summary,
preprocessing methods are a high-impact, low-effort, and
inconsistent part of the field of SPL performance predic-
tion, and all these properties make them essential to be
considered and tested.

References

[1] J. Gong, T. Chen, Deep configuration performance learning: A systematic survey and taxonomy, 2024. arXiv:2403.03322.

[2] P. Clements, L. Northrop, Software product lines, Addison-Wesley Boston, 2002.

[3] E. Engström, P. Runeson, Software product line testing – a systematic mapping study, Information and Software Technology 53 (2011) 2–13. URL: https://www.sciencedirect.com/science/article/pii/S0950584910001709. doi:https://doi.org/10.1016/j.infsof.2010.05.011.

[4] J. Oh, D. Batory, R. Heradio, Finding near-optimal configurations in colossal spaces with statistical guarantees, ACM Trans. Softw. Eng. Methodol. 33 (2023). URL: https://doi.org/10.1145/3611663. doi:10.1145/3611663.

[5] N. Siegmund, M. Rosenmuller, C. Kastner, P. G. Giarrusso, S. Apel, S. S. Kolesnikov, Scalable prediction of non-functional properties in software product lines, in: 2011 15th International Software Product Line Conference, IEEE, 2011, pp. 160–169.

[6] M. F. Dacrema, P. Cremonesi, D. Jannach, Are we really making much progress? A worrying analysis of recent neural recommendation approaches,

<footnote>7https://scikit-learn.org/stable/index.html</footnote>
CoRR abs/1907.06902 (2019). URL: http://arxiv.org/ abs/1907.06902. arXiv: 1907.06902.

[7] C.-L. Wu, K.-W. Chau, Y.-S. Li, Predicting monthly streamflow using data-driven models coupled with data-preprocessing techniques, Water Resources Research 45 (2009).

[8] J. Rasekhi, M. R. K. Mollaei, M. Bandarabadi, C. A. Teixeira, A. Dourado, Preprocessing effects of 22 linear univariate features on the performance of seizure prediction methods, Journal of Neuroscience Methods 217 (2013) 9–16. URL: https://www.sciencedirect.com/science/ article/pii/S0165027013001246. doi:https://doi.org/10.1016/j.jneumeth.2013.03.019.

[9] M. Acher, H. Martin, J. A. Pereira, A. Blouin, J.-M. Jézéquel, D. E. Khelladi, L. Lesoil, O. Barais, Learning very large configuration spaces: What matters for Linux kernel sizes, Ph.D. thesis, Inria Rennes-Bretagne Atlantique, 2019.

[10] J. Guo, D. Yang, N. Siegmund, S. Apel, A. Sarkar, P. Valov, K. Czarnecki, A. Wasowski, H. Yu, Data-efficient performance learning for configurable systems, Empirical Software Engineering 23 (2018) 1826–1867.

[11] H. Martin, M. Acher, J. A. Pereira, L. Lesoil, J.-M. Jézéquel, D. E. Khelladi, Transfer learning across variants and versions: The case of linux kernel size, IEEE Transactions on Software Engineering 48 (2022) 4274–4290. doi:10.1109/TSE.2021. 3116768.

[12] J. A. Pereira, M. Acher, H. Martin, J. Jézéquel, G. Botterweck, A. Ventresque, Learning software configuration spaces: A systematic literature review, Journal of Systems and Software 182 (2021) 111044.

[13] J. Alves Pereira, M. Acher, H. Martin, J.-M. Jézéquel, Sampling effect on performance prediction of configurable systems: A case study, in: Proceedings of the ACM/SPEC International Conference on Performance Engineering, ICPE '20, Association for Computing Machinery, New York, NY, USA, 2020, p. 277–288. URL: https://doi.org/10.1145/3358960. 3379137. doi:10.1145/3358960.3379137.

[14] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, E. Duchesnay, Scikit-learn: Machine learning in Python, Journal of Machine Learning Research 12 (2011) 2825–2830.

[15] M. Acher, H. Martin, L. Lesoil, A. Blouin, J.-M. Jézéquel, D. E. Khelladi, O. Barais, J. A. Pereira, Feature subset selection for learning huge configuration spaces: the case of linux kernel size, in: Proceedings of the 26th ACM International Systems and Software Product Line Conference - Volume A,

SPLC '22, Association for Computing Machinery, New York, NY, USA, 2022, p. 85–96. URL: https://doi.org/10.1145/3546932.3546997. doi:10.1145/3546932.3546997.

[16] L. Bao, X. Liu, F. Wang, B. Fang, Actgan: Automatic configuration tuning for software systems with generative adversarial networks, in: 2019 34th IEEE/ACM International Conference on Automated Software Engineering (ASE), 2019, pp. 465–476. doi:10.1109/ASE.2019.00051.

[17] J. Gong, T. Chen, Predicting software performance with divide-and-learn, in: Proceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC/FSE 2023, Association for Computing Machinery, New York, NY, USA, 2023, p. 858–870. URL: https://doi.org/10.1145/3611643. 3616334. doi:10.1145/3611643.3616334.

[18] S. Fu, S. Gupta, R. Mittal, S. Ratnasamy, On the use of ML for blackbox system performance prediction, in: 18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21), USENIX Association, 2021, pp. 763–784. URL: https://www.usenix.org/conference/nsdi21/ presentation/fu.

[19] Q. Cao, M.-O. Pun, Y. Chen, Deep learning in network-level performance prediction using cross-layer information, IEEE Transactions on Network Science and Engineering 9 (2022) 2364–2377. doi:10.1109/TNSE.2022.3163274.

[20] J. Cheng, C. Gao, Z. Zheng, Hinnperf: Hierarchical interaction neural network for performance prediction of configurable systems, ACM Trans. Softw. Eng. Methodol. 32 (2023). URL: https://doi.org/10. 1145/3528100. doi:10.1145/3528100.

[21] K. Zhu, S. Ying, N. Zhang, D. Zhu, Software defect prediction based on enhanced metaheuristic feature selection optimization and a hybrid deep neural network, Journal of Systems and Software 180 (2021) 111026. URL: https://www.sciencedirect.com/ science/article/pii/S0164121221001230. doi:https://doi.org/10.1016/j.jss.2021.111026.

[22] D. Nemirovsky, T. Arkose, N. Markovic, M. Nemirovsky, O. Unsal, A. Cristal, A machine learning approach for performance prediction and scheduling on heterogeneous cpus, in: 2017 29th International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), 2017, pp. 121–128. doi:10.1109/SBAC-PAD.2017.23.

[23] K.-T. Ding, H.-S. Chen, Y.-L. Pan, H.-H. Chen, Y.-C. Lin, S.-H. Hung, Portable fast platform-aware neural architecture search for edge/mobile computing ai applications, ICSEA 2021 (2021) 108.

[24] Y. Gao, X. Gu, H. Zhang, H. Lin, M. Yang, Runtime performance prediction for deep learning
models with graph neural network, in: 2023
IEEE/ACM 45th International Conference on Soft-
ware Engineering: Software Engineering in Prac-
tice (ICSE-SEIP), 2023, pp. 368–380. doi:10.1109/
ICSE-SEIP58684.2023.00039.
# Exploiting Large Language Models for the Automated Generation of Constraint Satisfaction Problems

Lothar Hotz¹,*,†, Christian Bähnisch¹,†, Sebastian Lubos², Alexander Felfernig², Albert Haag³ and Johannes Twiefel⁴

¹Hamburger Informatik Technologie-Center e.V., Hamburg, Germany

²Graz University of Technology, Graz, Austria

³Product Management Haag GmbH, Bad Dürkheim, Germany

⁴exXxa GmbH, Hamburg, Germany

**Abstract**

Constraint Satisfaction Problems (CSPs) are a core technology that solves many real-world problems, especially for configuration tasks. A key success factor in this context is an efficient knowledge acquisition process where domain experts and knowledge engineers (developers of CSPs) should develop an agreement on the correctness of the expanding knowledge base as soon as possible. In this paper, we show how large language models (LLMs) can be applied to the automated generation of solutions for constraint satisfaction problems thus reducing overheads related to CSP development and maintenance in the future.

**Keywords**

Constraint Satisfaction Problems, Large Language Models, Knowledge Acquisition, Automated Generation

## 1. Introduction

Knowledge acquisition for knowledge-based systems, especially constraint-based systems, is a complex task. It includes the formalization of partly tangible knowledge with a knowledge model, such as a configuration, constraint, or feature model [1, 2]. Constrained-based systems, in particular, are often used to implement configuration systems, due to their ability to compute possible values for configurations or even directly configurations themselves [3]. Hence, modeling a configuration problem as a constraint satisfaction problem (CSP) is a typical approach for computing configurations. This type of modeling is similar to developing programs in a high-level programming language but also incorporates logical semantic elements.

Currently in software engineering, the use of large language models (LLMs) is exploited to support programmers in their daily tasks, such as coding, code completion, reviewing code, API programming, generating test cases, documentation, or identifying design patterns as well as learning programming languages or understanding legacy code [4].

This is achieved through general LLMs such as ChatGPT¹ or specific ones like for coding trained LLMs such as CoPilot², or software agents like CREWAI³ and AutoGenStudio⁴, or software assisting engineers such as Devine AI⁵ or its open source correspondent Devika⁶.

An example of developing a small game with a graphical user interface is GPT-Engineer⁷, which prompts in natural languages and provides the game logic and the graphical interface through HTML and CSS coding. Especially the combination of an LLM with a compiler or interpreter in a chain leads to a self-evaluation where a code, which is generated code by an LLM, is directly checked through the interpreter, and the resulting error message is taken as the next prompt for the LLM. Through iterating this (e.g., with a supporting tool such as LangCHAIN⁸) a syntactically correct program is created. However, broader tasks, such as reviewing a software architecture or refactoring code distributed over multiple files are hindered by the limited size of a prompt (the context window) to a given number of tokens such as 128, 000 input tokens for GPT-4. In summary, applying LLMs to software development still has to cope with issues such as limited context windows, maintainability

ConfWS'24: 26th International Workshop on Configuration, Sep 2-3, 2024, Girona, Spain

* Corresponding author.

† These authors contributed equally.

<figure><img src="image_46.png" /></figure>

lothar.hotz@uni-hamburg.de (L. Hotz);

christian.baehnisch@uni-hamburg.de (C. Bähnisch);
slubos@ist.tugraz.at (S. Lubos); afelfern@ist.tugraz.at

(A. Felfernig); albert@product-management-haag.de (A. Haag);

twiefel@exxxa.ai (J. Twiefel)

<figure><img src="image_47.png" /></figure>

0000-0001-7370-7726 (L. Hotz)

<figure><img src="image_48.png" /></figure>

<figure><img src="image_49.png" /></figure>

© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0)

¹Chat Generative Pre-Trained Transformer

²https://github.com/features/copilot. All URLs accessed in May 2024

³https://www.crewai.com/

⁴https://microsoft.github.io/autogen/blog/2023/12/01/AutoGenStudio

⁵https://preview.devin.ai/

⁶https://github.com/stitionai/devika

⁷https://github.com/gpt-engineer-org/gpt-engineer

⁸https://python.langchain.com/docs/get_started/introduction
of AI-created code, and applicability in project planning or software architecture.

Inspired by these approaches, for constraint satisfaction problems the following questions arise:

* Which knowledge acquisition and engineering tasks can be supported by LLMs?

* Can knowledge models be generated by LLMs? How is quality ensured?

* Which alternative implementations of a knowledge model are the most comprehensible or maintainable?

However, a main ingredient of LLMs is of course a prompt that triggers the generation of text, here of knowledge models. Hence, for a knowledge model, the questions are also:

* What type of prompts do we need?

* What has to be presented to the LLM?

* Is natural language text describing the problem enough?

* Should examples of the formal modeling language, which shall be used for formalization, be given?

* Or the complete language specification?

This paper explores the innovative use of LLMs to automatically generate constraint models in constraint programming languages like PyChoco<fnref n="9" />. Constraint programming involves defining problems in terms of variables, related variable domains, and constraints that must be satisfied. Popular problems in this domain include, e.g., the N-queens problem, Magic Square, Map Coloring, and the Traveling Salesperson Problem (TSP). To tackle such problems, we propose a generalized approach (Section 3) where an LLM is leveraged to generate a constraint model based on a provided prompt.

We test our approach based on several constraint satisfaction problem examples (Section 4). In this paper, we mainly concentrate on known examples from the constraint community given by well-known descriptions, not that much on new examples formulated in natural language. Although the task of starting with known problems is untypical for configuration problems, in our view, this step is necessary for exploring the possibilities of LLMs for knowledge modeling in general. This approach of using commonly known constraint and configuration problems builds a baseline for further work.

With our proposed approach, we aim to streamline the process of model creation in constraint programming, making it faster and more accessible by harnessing the capabilities of LLMs. The main idea is to define a general prompt once which describes the problem context and

then reuse this general prompt for specific knowledge engineering tasks at hand.

The remainder of this paper is organized as follows. Section 2 provides an overview of the state-of-the-art in LLM-based knowledge modeling. In Section 3, we sketch our proposed LLM-based CSP generation approach. In Section 4, we provide details regarding the LLM prompting approach based on different example CSP tasks. A discussion (Section 5) and a conclusion (Section 6) ends the paper.

## 2. State of the Art in LLMs and Knowledge Modeling

Many real-world problems can be interpreted as constraint satisfaction problems (CSPs). Knowledge engineers have the task of formalizing domain-specific constraints into corresponding constraint-based representations. This formalization step is often effortful and more assistance and automation are required in the modeling process which can be regarded as a major challenge for constraint-based systems [5]. Due to recent developments in the area of large language models (LLMs), we could envision agent-based approaches that support the (semi-)automated generation of CSPs [6]. In the following, we discuss related work on the application of LLMs to knowledge modeling.

The idea of exploiting synergy potentials of knowledge-based systems and language models for knowledge-base generation has been proposed a.o. by Petroni et al. [7], Ding et al. [8], and Razniewski et al. [9]. Suchanek and Luu [10] motivate the integration of LLMs with data-driven and knowledge-based approaches to exploit the advantages of both worlds, specifically, to let data-driven approaches act as a basis for grounding the LLM output in reality. In the work presented in our paper, a simple form of grounding is the usage of test cases to assure intended CSP semantics. A similar line of research is presented in Nayak and Timmapathini [11] where object and relation identification based on LLMs is investigated.

Ahmed and Choudhury [12] introduce the idea of applying LLMs to the generation of optimization problems. The motivation behind this is to make related problem formulation tasks more accessible to domain experts, i.e., to decrease the need for specialized mathematical knowledge to make problem formulations feasible. Based on a given dataset comprising different example problem definitions (and solutions), LLMs are used to generate optimization problem definitions for new problems defined in a textual fashion. A major difference compared to our work is that model fine-tuning is primarily based on a "human in the loop" approach whereas we focus more on automated fine-tuning giving LLM feedback on the

<footnote n="9">⁹https://pypi.org/project/pychoco/</footnote>
syntactical (is the generated CSP correct or what were the compilation issues?) and the semantic level with test cases. A related approach is the application of LLMs to support different types of strategic reasoning tasks, for example, in the context of economic simulations and game theory [13].

A very similar approach provides [14]. This 'Program of Thoughts' named approach also combines an LLM with an external Python interpreter, however, in [14] for computing numerical problems. Furthermore, the verification of the generated Python program is not discussed.

The adaptation of LLMs for logical reasoning tasks [15] can be performed either based on LLM fine-tuning where LLMs are trained (and adapted) for specific problem settings [16] or based on (automated) prompt adaptation [17]. Intending to improve the quality of code generation, Pan et al. [15] follow the idea of using constraint (and SAT) solver execution errors as feedback channels (in the prompting process) to increase the quality of code generation. The feedback approach presented in our paper extends the work of Pan et al. [15] in terms of additionally providing test cases that help to improve the quality of the generated CSP also on the semantic level.

In [18], various prompts are used to create source code with built-in variability. Specific prompts enable the generation of code in different programming languages, allowing for application configuration. However, a human developer would execute these prompts, no iterative process ensures the correctness of the resulting code.

The automated generation of CSPs can also be regarded as a specific type of ontology construction where concept hierarchies are derived based on different LLM prompts representing concept hierarchy-specific queries (see, for example, the work of Funk et al. [19]). An example of such a query is the following: *What are all of the most important subcategories of the category A?*

## 3. Methodology

Our approach for generating constraint models using LLMs is a structured, iterative process designed to create syntactically and semantically (almost) correct models. This begins by defining a *general LLM prompt* that can encompass the varying specifics of different constraint problems. For instance, the prompt can be tailored to a specific constraint problem but always solicits a PyChoco interpreter that solves the problem.

The process, furthermore, involves using an iterative loop where the LLM generates a constraint model based on the provided prompt. This generated model is then verified through a constraint interpreter or compiler. If the syntax of the model is incorrect, the result of the Python interpreter call is automatically taken as a prompt for a next iteration and the model is adjusted by the LLM

and the process repeats. This loop continues until the syntax is correct.

Once a syntactically correct model is produced, the next step is to verify its semantics. This is done by running a series of test cases specific to the problem domain. Successful completion of test cases indicates a correct semantic implementation (at least concerning the test cases).

This approach, thus, executes an iterative prompting of an LLM, where only a human user provides the first prompt, while the results of a Python interpreter are automatically used by the LLM as successive prompts. A complete example of such an iterative dialog including in-between generated answers of the LLM ("Assistant") is presented in the Appendix Section 2.

This methodology can be further detailed through the following steps:

**Leveraging Existing Knowledge Problems:** To create useful constraint models, we use logical problems that are well understood and documented on the internet. Examples include classic problems such as the N-queens problem, Map Coloring, or the Traveling Salesperson Problem. These problems are selected due to their well-known constraints and solution strategies.

**Integration with Constraint Solvers:** Once the logical problems are defined, we connect these models to a constraint system, here PyChoco - other suitable solvers could be used. This involves mapping the logical problem's constraints to the syntax and structures of the chosen constraint language and, thus, facilitating automated solving.

**Syntax Verification Loop:** An iterative process is set up where the LLM generates a constraint model based on the initial prompt. This model is then verified for syntactic correctness using the constraint interpreter or compiler. If errors are identified, the prompt is automatically adjusted by the LLM, by using an error message as a next prompt and the LLM regenerates the model. This loop continues until a syntactically correct model is achieved.

**Semantic Verification with Test Cases:** After achieving a syntactically correct model, the focus shifts to ensure semantic correctness. This involves introducing test cases specific to the defined problem. The LLM-generated model runs through these test cases to verify that it not only adheres to syntactic rules but also correctly implements the problem's logic. Iteration continues until the model passes all semantic verification tests.

**Generalizability:** The ultimate goal of our approach is to establish a generalizable method for generating constraint models using LLMs. By systematically using an iterative loop for both syntactic and semantic verification that employs examples and logical problem definitions, we aim to create a robust framework that can be adapted
tool Python_REPL, description: A Python shell. Use this to run and verify your solution to the constraint problem.
Input should be a valid Python script using pychoco. The last line should be "verify_solutions(solutions, ...}" in order
to verify your solutions

System:

You are an agent designed to solve constraint problems, you write python code to solve and verify constraint problems.
You have access to a python REPL, which you can use to execute python code and verify your solution. If you get an
error, debug your code and try again. You only use the constraint solver pychoco. You conclude your python code
with a variable "solutions" and verify it with the method call "verify_solutions(solutions, <problem_name>", where
<problem_name> is given to you as the first word of the instructions. "solutions" should be a list of all solutions to the
constraint problem. If verification fails, you correct your solution.

Use the following example as a template for solving constraint problems with pychoco:

User: ints10. find numbers one to 10.

Assistant:

'''python
from pychoco.model import Model
from test_tool import verify_solutions

model = Model()
x = model.intvar(1, 10, "x")

solver = model.getSolution()
solutions = [s.get_int_val(x) for s in solver.find_all_solutions()
verify_solutions(solutions, "ints10")
'''

**Figure 1:** General prompt including an example for the LLM on how to call the verification method. The first three lines (the tool description) are needed to avoid iterations related to wrongly calling the method *verify_solutions* (see Appendix Section 7 for created errors without those lines).

to various constraint languages and problems.

By following these steps, our approach leverages the
capabilities of LLMs to create accurate and efficient con-
straint models, providing a scalable solution for different
problem types.

4. Prompting Constraint Models

We divide prompts into a *general part* which is used
with each constraint problem, i.e., the *system prompt* (see
Section 4.1), and a *query part* which points to a specific
problem (see Section 4.2).

4.1. General Prompts

**Prompting Syntactic Valid Models** Figure 1 shows the general prompt which we developed for querying for constraint solutions. The prompt provides the following explanations to the LLM:

1. what role it has (“You are an agent...”),

2. the explanation of the REPL<fnref n="10" /> as a tool (“You have access...”),

3. a hint of the behavior of the tool (“The python REPL...”),

4. a hint of how to use the tool (“Use this...”),

5. to focus on that tool (“use only”).

**Prompting Semantic Verification:** To verify, if a semantic correct solution can be computed with the generated constraint model, we include a verification scheme that builds on tests. Those are specific for the constraint problem at hand. However, the general prompt is enhanced with a call to the verification method, which is parameterized with the name of the constraint problem. The verification scheme is given by an example that explains the parameterization, a constraint model, and the call to the verification method (Figure 1).

**Prompt Refinement:** For more understanding, of
why the LLM generates a certain code line in the model,
we have enforced the LLM to provide comments above
a code line (see Figure 2). This is done by explaining
in the prompt what a “Good python code example”<fnref n="11" /> is.
This is done, by repeating this text at various appropriate

<footnote n="10">¹⁰Read-Eval-Print-Loop</footnote>

<footnote n="11">¹¹The italic style in the prompt is only for the human reader, i.e., only the text is given as prompt.</footnote>