In many scenarios, configurators support the configuration of a solution that satisfies the preferences of a single user. The concept of multi-configuration is based on the idea of configuring a set of configurations. Such a functionality is relevant in scenarios such as the configuration of personalized exams, the configuration of project teams, and the configuration of diferent trips for individual members of a tourist group (e.g., when visiting a specific city). In this paper, we exemplify the application of multi-configuration for generating individualized exams. We also provide a constraint solver performance analysis which helps to gain some insights into corresponding performance issues.
Configuration is the process of assembling basic components into a complex product while taking into account a set of constraints [1, 2, 3, 4]. Most existing configurators are based on the assumption that a solution (configugroup-based configuration [ 5, 6] focuses on the configuration of a solution for a group of users. Such a configuration must satisfy the preferences of each individual user as much as possible [7, 8]. Group-based configuration can be further extended to allow the configuration of a set of solutions based on the preferences of one or multiple users. Such a multi-configuration problem [9] includes a set of constraints specifying restrictions with regard to (1) the combination of multiple solutions and (2) properties of a specific solution. Scenarios including such configuration sets may benefit from multi-configuration. Related example scenarios are the following. ifgured for each student, where related constraints are specified by instructors and possibly also students. A configurator can support instructors during the exam nEvelop-O LGOBE (S. Lubos) https://www.tugraz.at/ (S. Lubos)
0009-0000-7774-6693 (B. Ritz); 0000-0003-0108-3146 (A. Felfernig); 0000-0001-5778-975X (V. Le); 0000-0002-5024-3786 © 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License tion problem (CSP) [14]. We exemplify diferent types of constraints supported by our configurator and also show
Multi-exam configuration . individual exams are con- configuration settings [ 13] also due to the fact that it is preparation phase and helps in the prevention of cheat- between configuration parameters. how the preferences of students can (potentially) be taken into account. In order to analyze constraint solver performance, we evaluate the runtime performance of an open source constraint solver (Choco) on the basis of a typical real-world exam configuration scenario.
The remainder of this paper is organized as follows.
In Section 2, we introduce a definition of a multiconfiguration task and provide an example from the domain of multi-exam configuration. In this context, we also introduce and exemplify diferent constraint types.
Thereafter, in Section 3, we evaluate the performance of Choco when solving multi-exam configuration tasks also including a performance analysis when solving a real-world configuration task. Threats to validity are discussed in Section 4. The paper is concluded with a discussion of open research issues in Section 5.
We now give a basic definition of a multi-configuration task (see Definition 1) (see [ 9]) and show how multi-exam configuration tasks can be introduced correspondingly.
Definition 1. A multi-configuration task can be defined as a tuple ( , , ) with = ⋃{ } is a set of finite domain variables ( is variable of configuration instance ), = ⋃{( )}a set of corresponding domain definitions, and = { 1, 2, ..., } a set of constraints.
In the following, we will use this definition to introduce the task for multi-exam configuration and outline what constraint types are supported by our configurator. In this context, the set of constraints can be defined by users represented by instructors and also students (where this is intended).
Following Definition 1, a multi-exam configuration task can be defined as follows.
•
= { 11.. , 11. 1.. 11. , .., . 1.. . } where is question of the exam of student , is Instructor constraints (defined by instructors) in rethe number of exams (students), is the number strict the set of questions that may or may not appear of questions per exam, . denotes the value of in exams. Each exam must fulfil all of these constraints. the k-th question property of question , and We distinguish between two types of related constraints: represents the number of question properties per intra-exam and inter-exam constraints. question (in our case, = 6 ). Our configurator supports the following question properties: 2.2.1. Intra-exam constraints
2. level - dificulty level of the question 3. min-duration - minimum estimated time
needed to answer the question 4. max-duration - maximum estimated time needed to answer the question Intra-exam constraints restrict which questions are eligible for being part of an exam. Such constraints refer to each individual exam. A simple form of intra-exam constraints is to directly define a specific question property. For example, let us assume that up to now a course has covered only one (the first) topic ( ). As a consequence, 5. type - type of the question (e.g. single/multiple choice, assignment task, etc.) 6. points - maximum number of points rewarded for correct answers • = {( 11)..( ), ( 11. 1)..( 11. 6), .., ( . 1)..( . 6)} where ( ) = {1..Ω}, with Ω being the total number of questions in the question pool, and ( . )is a question property domain (one out of the following): 1. dom(topic) = {1..} where is the number
of defined question topics 2. dom(level) = {1..} where is the number
of defined question complexity levels 3. dom(min-duration) = {1.. } with indicating the maximum specifiable value 4. dom(max-duration) = {1..} with indicating the maximum specifiable value 5. dom(type) = {1..} where is the number
of defined question types 6. dom(points) = {1..} where is the maximum amount of points • = { 1.. } where is the constraint identifier and is the number of constraints
Importantly, depending on the question 1..Ω assigned to a question variable , a set of corresponding question properties must hold, for example, if question 11 = 1, corresponding restrictions such as 11 = 1 → 11. = indicate the relevant question properties. In Subsection 3.2, we explain in which way we support this aspect in our configuration library. Furthermore, for each studentspecific exam , we need to include an alldiferent ( 1 .. ) constraint to avoid situations where a questions is assigned to the same exam twice. In our implementation, this aspect is taken into account on the basis of set variables (see also Subsection 3.2).
the instructor requires that only questions belonging to Instructors may also specify constraint scopes using topic are part of the first exam (see Formula 1).
Intra-exam constraints allow instructors to arbitrarily plication, see the examples in Formulas 8–10. percentages in order to describe which amount of questions per exam must satisfy the question property con(1) straint. For example, only between 10 and 20 percent of questions per exam should be solvable in less than five minutes (see Formula 7). 5 and 10 questions of each exam should be easy to solve, which is indicated by complexity level 1 (see Formula 6). 2. Example (average): The average complexity level of each exam is between 2 and 3. (see Formula 9).
(#) ⋀ =1 =1 (∑ . = 100
) (#) ⋀ =1 (2 ≤ ∑ =1 . ≤ 3)
Intra-exam constraints also support aggregations. In the context of our evaluation settings, we support the functions sum, average, and distinct count. For their ap1. Example (sum): The total amount of points per exam is 100 (see Formula 8). 3. Example (distinct count): Each exam consists of at least 3 diferent question topics (Formula 10). (#) ⋀ =1 (|{ .}| ≥ 3 ) (10) 2.2.2. Inter-exam constraints Similar to intra-exam constraints, inter-exam constraints restrict which questions may be part of exams. However, they constrain how often certain question or question properties may or may not appear in the entire exam conifguration. Therefore, inter-exam constraints depend on all exams combined, instead of every exam individually. Such constraints count, for example, how many exams have at least one question that fulfills a given constraint. This sum can be lower and/or upper bounded. For example, we assume that a specific question is part of at least
5 ≤ |{ ∈ ∶ = }| ≤ 10
(
As a special case of inter-exam constraints, instructors can restrict the degree of question overlap across exams, i.e., the number of questions that exams have in common. This is especially useful to prevent the generation of identical or very similar exams. The degree of overlap can be lower and upper bounded in order to restrict the minimum and maximum amount of questions that pairs of exams may share. For example (see Formula 12), the upper bound denotes that no pair of exams exists which shares more than 5 questions, whereas the lower bound states that every pair of exams must share at least 2 questions. This might be useful to create a sense of fairness among students but might lead to cheating. represents a set of questions comprising all questions of exam . Student constraints in can be specified by each student individually. They constrain only the student’s exam, no other exams are afected. Student constraints can only further narrow down instructor constraints.
Example: The instructor specifies a constraint such that between 20% and 50% of the questions of each exam must belong to topic (see Formula 14).
(#) ⋀ =1 (0.20 ≤ |{ ∈ ∶ . = )}|
Student decides to restrict this constraint even further so that only a maximum of 25% of questions of their exam belong to topic (see Formula 15).
|{ ∈ ∶ . = )}|
configuration setting. 2 We now present a performance analysis of our multi
We assume that (1) 450 students participate in an exam and (2) a question pool of 45 questions individually associated with one out of four diferent topic areas (topics) is available. Each exam should consist of = 10
questions.
We define the following constraints ( ): 1. Each exam should include questions related to at least 2 diferent topics.
≤ 0.50) (14) (15) (#) ⋀ =1 (|{ .}| ≥ 2
) 2. There is at most one multiple choice question.3
(|{ ∈ ∶ . = 3}| ≤ 1) neighbors requiring 8 constraints to be added. provided in the final paper version. 3Question type 3 was assumed to be multiple choice. lighted seat 34 (dark gray) and its neighbors (light gray) 2A link to the source code of our configuration approach will be suming a hall with 22 rows and 21 seats/row).
Instead of relying on a constant number of questions per student exam, it is also possible to support flexible lower and upper bounds. We support this aspect by utilizing Choco set variables. Every student exam includes a set of questions. The domain of a set variable is (implicitly) defined by lower and upper bound sets. The lower bound is a set of questions that each exam must include, whereas the upper bound defines the maximum possible question set. In our case, the lower bound is empty and the upper bound equals the question pool.
A varying number of questions per exam could trigger the need for further instructor constraints, for example, to restrict the allowed number of questions. Let us assume a defined question pool with
Ω = 3 questions ({1, 2, 3}) variables (model is a Choco model object). and = 2 exams ( 1 and 2) represented as Choco set e 1 = m o d e l . s e t V a r ( l b : { } , u b : { 1 , 2 , 3 } ) e 2 = m o d e l . s e t V a r ( l b : { } , u b : { 1 , 2 , 3 } )
Now, we want to specify that each exam (of student ) needs to include at least two and at most three questions.
In Choco, this constraint would be defined as follows.
e 1 . s e t C a r d ( m o d e l . i n t V a r (
In this simplified setting, the possible solution sets for both, 1 and 2 are: {1, 2}, {1, 3}, {2, 3}, and {1, 2, 3}.
If we also want to define restrictions on allowed question properties, the solver needs to know the question properties of each individual question. For scalability reasons, we avoid to define question/property relationships on the basis of constraints. Instead, we support a key-value data structure that allows the identification of question properties on the basis of the corresponding question ∈ {1..Ω} . Given such a structure, we are now able to define constraints referring to question properties, for example: in each exam, the number of questions of topic is exactly 2.
In Choco, no related built-in constraints exist. We have defined a custom constraint by extending the Propagator class and implemented the two required methods eration of the solving process. It tries to find solutions by 4A GitHub source code reference will be included in the final paper.
5. Neighboring exams share at most 2 questions (as- counting the number of questions that belong to the specpropagate and isEntailed.4 The former is called in each it- a useful approach in scenarios requiring solution set conified topic. If the current branch of the solving process cannot satisfy the constraint, a contradiction is indicated.
When taking into account this constraint, the possible solutions for 1 and 2 are {1, 2, 3} and {1, 3}.
We have also evaluated the solver performance with synthesized multi-exam configuration tasks along the dimensions of number of questions and number of exams. Each task utilizes the same 5 constraints as discussed in Subsection 3.1. We choose the lecture hall size depending on the amount of exams , using the formula ⌈√⌉ , since this is a fairly simple way to assure that all students will fit in the lecture hall and to keep a good ratio between rows and seats per row. The results of this performance evaluation are summarized in Table 1 showing acceptable runtime performances in the context of typical exam settings as well as extreme cases of around 1000 questions and up to 1000 students inducing solver runtimes up to nearly 3 minutes. Notice that a smaller question pool size does not always result in faster runtime.
In the context of the reported evaluation, we have applied the standard settings of the used constraint solver. A major topic of further work is to further improve runtime performance on the basis of diferent approaches supporting the learning of solver search heuristics (see, e.g., [15]). Fairness is a crucial aspect to be taken into account when it comes to the automated generation of exams. In this work, we have taken this aspect into account a.o. on the basis exam-specific criteria regarding the percentage of to-be-included questions that are related to a specific complexity level. For future work, we plan to further refine this aspect, for example, on the basis of optimization functions that help to balance the complexity of individual exams on a more fine-grained level. Finally, in real-world settings, we often have to deal with situations where a given set of constraints is inconsistent, i.e., no solution could be identified. In our future work, we will integrate corresponding repair concepts which will help users to find ways out from the so-called no solution could be found dilemma. Such approaches can be based o.a. on model-based diagnosis [16].
In this paper, we have introduced multi-configuration as ifguration, for example, exam configuration and project