=Paper=
{{Paper
|id=Vol-1183/gedm_paper01
|storemode=property
|title=A Binary Integer Programming Model for Global Optimization of Learning Path Discovery
|pdfUrl=https://ceur-ws.org/Vol-1183/gedm_paper01.pdf
|volume=Vol-1183
|dblpUrl=https://dblp.org/rec/conf/edm/BelacelDL14
}}
==A Binary Integer Programming Model for Global Optimization of Learning Path Discovery==
https://ceur-ws.org/Vol-1183/gedm_paper01.pdf
A Binary Integer Programming Model for Global
Optimization of Learning Path Discovery
Nabil Belacel Guillaume Durand François Laplante
National Research Council Canada National Research Council Canada Université de Moncton
100, des Aboiteaux St. 100, des Aboiteaux St. 60, Notre-Dame-du-Sacré-Cœur St.
Moncton, E1A 7R1,Canada Moncton, E1A 7R1,Canada Moncton, E1A 3E9,Canada
+1.506.861.0963 +1.506.861.0961 +1.506.381.6220
nabil.belacel@NRC.gc.ca guillaume.durand@NRC.gc.ca francois.laplante@umoncton.ca
ABSTRACT competency state. For example, a learner with solid grounds in
This paper introduces a method based on graph theory and integer arithmetic (starting location) willing to learn the solving of
operations research techniques to optimize learning path systems with multiple variables (destination) should be advised to
discovery. In this method, learning objects are considered as previously learn to solve one variable linear equations (next step
nodes and competencies as vertices of a learning graph. A first of the itinerary).
step consists in reducing the solution space by obtaining an Over the years, educational data mining and recommendation
induced subgraph H. In a second step, the search of an optimal technologies have proposed significant contributions to provide
learning path in H is considered as a binary integer programming learners with adequate learning material by recommending
problem which we propose to solve using an exact method based educational papers [18] or internet links [10], using collaborative
on the well-known branch-and-bound algorithm. The method and/or content-based filtering. These approaches usually aim at
detailed in the paper takes into account the prerequisite and gained recommending learning material satisfying an immediate interest
competencies as constraints of the optimization problem by rather than fitting in the learner’s sequential learning process.
minimizing the total competencies needed to reach the learning
objective. Sequential pattern [28] and process mining [19] technologies have
also been investigated. However, these technologies have been
Keywords used to understand the learner’s interaction with content to
discover general patterns and trends rather than to recommend
Learning path, learning object recommendation, graph theory, adapted learning paths to learners.
clique, mathematical programming, binary integer programming,
branch-and-bound algorithm. Other approaches, in the course generation research community,
address the need for recommending not only the learning objects
1. INTRODUCTION themselves, but sequences of learning objects. Sicilia et al. [17] or
Global Positioning System (GPS) is a Global Navigation Satellite Ulrich and Melis [20] addressed learning design concepts and
System (GNSS) that is massively used by car drivers. This large requirements through Course Generation. Though numerous
acceptance is easily understandable by the benefits that such a solutions have been proposed, using statistical methods [13],
system can offer. Car navigation systems can dynamically decision rules [23], production rules [11], Markov processes [8]
calculate an itinerary between two points taking into account, and Hierarchical Task Network Planning [17, 21, 22], most of
depending on the system, several constraints like duration, them do not take into account eventual competency dependencies
distance, closed roads, traffic jams, etc....Drivers can focus among learning objects and/or are not designed for large
exclusively on their driving limiting risks of accidents, stress, and repositories of interdependent learning objects1.
losing their way.
Therefore, we detailed in [7] a dynamic graph based model and a
To some extent, the learning path followed by a student could be heuristic approach tailored to find a learning path in a graph
seen as an itinerary between several learning objects [9]. In this containing millions of learning object nodes.
context, constraints on learning objects are not distance or time
duration to go from one learning object to the other but rather This paper is an extension of this previous work and summarizes
prerequisite and gained competencies. As a result the itinerary or the model, the heuristic presented in [7], and proposes a major
path between learning objects is regulated by competency optimization to calculate a global optimum learning path. In the
dependencies that lead a learner from an initial to a targeted previous work [7], we applied a greedy heuristic algorithm to
obtain a pseudo-optimal learning path from a set of cliques.
Greedy heuristics are efficient, but they sometimes get stuck in a
local solution and fail to find a global optimum [26]. They are
based on an intimate knowledge of the problem structure and have
no scope of incremental improvement.
1
A more complete discussion can be found in [7].
Therefore, in this work we slightly reformulate our model in order is a set of competencies offered by vertex v
to fit as an integer programming problem and we propose an exact
method based on the branch-and-bound algorithm. The relationship between learning objects and competencies is
multidimensional [6]: a learning object can require several
2. PROBLEM CONSIDERED competencies and transmit more than one competency to the
In order to facilitate the understanding of the presented model, learner as well. The existence of an edge between two learning
several key elements and assumptions need to be clearly defined. objects u and v can be formalized by the following formula:
A competency can be seen as a knowledge component being part ( ) ( ) { }
of a “model that decomposes learning into individual knowledge
( )
components (KCs)” [16]. In this paper, a competency is “an
observable or measurable ability of an actor to perform a where ( ) ( ) means that the competencies required
necessary action(s) in given context(s) to achieve a specific by v are provided by learning object u. Condition 1 is sufficient
outcome(s)” [12]. A competency in our situation can be a but not necessary. For example, before having completed u, the
prerequisite to the efficient completion of a learning object. learner might already have some or the totality of the
According to Wiley [25], a learning object is “any digital resource competencies required by v. This means that we may have an arc
that can be reused to support learning”. In the rest of the paper we between u and v even though none the competencies required by v
define the learning object as any digital resource that can be are provided by u. In other words, edge set also depends on the
reused to provide a competency gain. learner’s competency set at time t: ( ( )) and
A learner is a dynamic user interacting with learning objects in () { } where are competencies which
order to increase his/her competencies from an initial set to a the learner possesses. As a result, graph G is a dynamic directed
targeted set of competencies. We assume that a learner completing graph and condition 1 can be strengthened by the necessary and
a learning object will gain the competencies targeted to be sufficient condition 2:
transmitted by the interaction with the learning object. We also { } ( ) ( ) ( )
assume that a learner who would not possess the prerequisite set
of competencies required by a learning object should not attempt ( )
this learning object since this would result in a limited
competency gain. 2.2 Model Dynamicity
The dynamicity of our model is due to the fact that a learning
Last but not least, we assume that the number of learning objects object can bring competencies that could be among the
available is very large (millions to billions of learning objects) and prerequisites of future learning objects.
that each learning object cannot provide the gain of a competency
that is a pre-requisite to itself.
2.1 Graph Theory Contribution
Graph theory aims at studying mathematical structures composed
of elements having relationships or connection between them. The
use of directed graphs is not a novelty in e-learning systems [1, 3,
24, 25]; however, we were unable to find a formal model for
discussing learning path problems based on graph theory,
especially one taking into account the dynamic nature of a
learning environment.
A directed graph, or digraph, G = (V, E) consists of:
A non-empty finite set V of elements called vertices or
nodes, Figure 1. Edge dynamicity.
A finite set E of distinct ordered pairs of vertices called
arcs, directed edges, or arrows. For example, as shown in Figure 1, a learning object D could be
Let G = (V, E) be a directed graph for a personalized learning accessible to a learner if he has acquired the competencies c1 and
path. Each vertex or node in G corresponds to a learning object. c2. Assuming that competency c1 is provided by learning objects
Two vertices are connected if there exists a dependency relation, A and C and competency c2 is provided by learning objects B and
such that one vertex satisfies the prerequisites of the other. So, C; D is reachable if learning objects A and B are completed or if
each edge between two vertices { } means that the learning learning object C is completed. If a learner completes learning
object is accessible from . The accessibility property required object A at time t and learning object B at time t+1, the learner
to define edges between vertices relies on post and pre-requisite will have the competencies required to reach D and according to
competencies associated to each learning object. the condition 2, a new edge between B and D will be created (red
Considering { }, this edge means that after having edge on Figure 1).
completed the learning object u, the learner should have the
required competencies to undertake resource v. By extension, each
3. INVESTIGATED SOLUTION
vertex v is represented by a pair ( , ) where: 3.1 Reducing the solution space
Eliminating irrelevant learning objects is generally the first step of
is a set of the competencies required by vertex v a course generation tool [1, 15]. In our case, as the learning object
repository is supposed to be very large, the learning objects
cannot all be checked individually. The approach we chose
consists in reducing the considered solution space by obtaining an
induced subgraph H which consists of all the vertices and edges
between the vertices in G that could be used in the learning path.
The algorithm can be seen as a loop generating complete sub-
graphs, or cliques, until one such clique is generated whose
prerequisites are a subset of the learner’s competencies. Cliques
are generated in a top-down fashion where we begin with the
target clique, which is composed of a single learning object (we
create a fictitious learning object, β, whose prerequisite
competencies correspond to the list of the learner’s target
competencies). Cliques are then generated by finding every vertex
where at least one output competency is found in the prerequisite Figure 3. G’ consists of connected cliques.
competencies of the clique (the union of all prerequisite
competencies of every learning object within the clique) to which
it is prerequisite. As such, cliques contain the largest possible As shown in Figure 3, G’, consisting of the vertices E of sets
subset of vertices which satisfies the condition “if every learning v1,…,vn, is an induced sub-graph of G. If the learner has
object in the clique is completed, then every learning object in the completed all the vertices of vi, he/she will have access to all the
following clique is accessible”. We simplify the stopping vertices of vi+1, thus all subsets of vertices of vi can be considered
condition by adding a second fictitious object, α, into the dataset to be a clique.
with no prerequisite competencies and with the learner’s current
competencies as its output competencies. If a clique contains this In addition to reducing the solution space, clique generation is
object, the stopping condition is true. also an efficient way to check whether a solution learning path
exists between α and β. If the algorithm is not able to generate
β6 cliques linking α and β, there is no need to proceed forward with
an algorithm aiming at finding one of the possible solutions.
v1 A65 E63,5 ↑ 6
3.2 Greedy Algorithm
v2 3,2,4 5 ↑ 3,5 Once the induced sub-graph is obtained, we use a greedy
T 7 U0
algorithm that searches for a local optimum within each clique.
v3 ↑ 0, 7 The definition of such a local optimum, depending on the dataset
L0,78,9 I79 K08 and the results pursued, has to follow a specific heuristic or
strategy.
Α8,9 ↑ 8, 9 The shortest path strategy seems to be widely accepted in the
literature [1, 27]. This strategy is not necessarily the best to adopt
α: Fictitious LO with initial learner competency state in any situation since the proposed learning path might lead to the
β: Fictitious LO with targeted learner competency state learning of non–essential competencies and potentially cognitive
overloads. For example a learning object could lead to
LO list of gained competencies LO list of prerequisite competencies competency gains that would not be required to reach the targeted
Figure 2. Induced sub-graph generation. learner competency state; there is no need to understand the proof
of the Landau Damping to learn about the history of theoretical
physics. Considering a learning object presenting an introduction
to the perturbation theory and a second one introducing the theory
Considering the target competency β as shown in Figure 2, all the
and the proof of the Landau Dumping, it might make sense to
vertices leading to those competencies (competency 6 in Figure 2)
choose the first one in order to minimize the cognitive load to the
are selected in a set v1, then the learning objects leading to the
learner. Some might argue that using such “straight to the point”
prerequisites of set v1 (competencies 3 and 5) are selected from
heuristic might limit too drastically the natural curiosity of the
graph G to create the set v2. This mechanism continues until the
learner. As any heuristic, we agree that it is discussable but this is
prerequisite competencies of the set vn are all competencies which
not the purpose of this paper.
the learner has already acquired.
The greedy algorithm considered attempts to find a path by
considering each clique one after the other and reducing it to a
minimal subset of itself which still verifies the condition “if every
learning object in the clique is completed, then every learning
object in the following clique is accessible”.
β6 Considering our example (Example 1):
{ }
v1 A65 E63,5 ↑ 6 { }
v2 T3,2,47 U50 ↑ 3,5 { }
v3 L0,78,9 I79 K08 ↑ 0,7
Α8,9 ↑ 8, 9
α: Fictitious LO with initial learner competency state
β: Fictitious LO with targeted learner competency state
LO list of gained competencies LO list of prerequisite competencies ( )
Figure 4. Illustration of the greedy algorithm execution
The first clique considered will be the one leading to the targeted
competencies (the clique satisfying the prerequisites of β). In the
case of the three cliques v1 to v3 as illustrated by Figure 3, v1 will
be considered first followed by v2 then by v3.
( )
For each clique, the local optimum is considered obtained when
the minimum subset of vertices with a minimum “degree”, being
the sum of the number of prerequisite competencies and output
competencies of the vertex, are found. In other words, the greedy
algorithm select in each clique a set of learning objects
minimizing the number of competencies required and gained in
order to locally limit the cognitive load of the selected material.
The greedy algorithm locally optimizes a function called “deg”
(for degree) detailed in the following section.
For clique v1, the selected learning object is A since its number of ( )
prerequisites is smaller than that of E while they share the same
competency gain. As A has been chosen in v1, only the objects in From this example the solution sequence using the greedy
v2 respecting the new v1’s prerequisites is chosen. As a result, the algorithm is .
algorithm chooses U in v2. In v3, K and L lead to v2’s prerequisite
but K requires fewer prerequisites than L, therefore K is selected To check if we get an optimal solution or not, we have to calculate
and the proposed learning path is . the objective function called deg. The objective function
returns the total number of prerequisite and gained competencies
4. OPTIMIZATION of a set of learning objects.
In this section we present our mathematical model for learning We can draw from the previous example the following conditions
path discovery and then we introduce the algorithm for solving to check if we have an optimal solution or not.
our mathematical model.
Let { } a solution set ( contains at least one
After eliminating irrelevant learning objects in the first step, we learning object as in example 3).
generate the optimal solution from the obtained induced sub-graph
as presented in Figure 4. For this purpose, we applied in [7] a ()
greedy algorithm to obtain an optimal or pseudo-optimal learning ( )
path from a set of cliques. Greedy heuristics are computationally
efficient, but they sometimes fail to find a global optimum as we
explain in the following section. ( { }) ∑ ∑( ) ( )
4.1 Notation and limits of the Greedy
heuristic
Let , , the matrices representing the distribution of
the competencies that are prerequisite to the items contained ( { }) ( { })
in the cliques, the competencies that are gained when the n ( )
items of the cliques are performed, and the clique distribution of
Condition ( ) and ( ) mean that the competencies required by a
the n items. Note that the matrix could be considered as a Q- clique set have to be covered by the gains of the previous clique
Matrix [5]. set and two different clique sets cannot share the same clique.
While condition ( ) defines the deg function, condition ( )
introduces the optimality condition. A learning path is optimal if
no other path with a lower degree exists. However this doesn’t 4.2 Formulating the integer programming
apply at the clique level since the optimal is not necessary the
set of clique having the lowest degree. The global optimum is
problem
not the sum of the local optima calculated by the greedy Let us consider n items or learning objects and m competencies;
algorithm. is the matrix representing m prerequisite competencies for
the n items and is the matrix representing the
The following example highlights this case where local optima competencies that are gained when the n items are performed. In
obtained by the greedy algorithm lead to non-optimal solution. other words, if = 1 means that the item i has competency j as
Example 2: one of its prerequisite competencies; and = 1, means that the
β6 competency is gained when the item is performed. The
personalized learning path may then be formulated as a binary
v1 M65 N6,74 ↑ 6 integer programming (BIP) as follows:
Minimize:
v2 5
O 3,4 P 84 ↑ 4,5
∑ (∑( ) ) ( ) ( )
v3 8 3.4 ↑ 3, 4, 8
T7 R 7
Subject to:
α7 ↑ 7
(∑ ) ( )
( ) { }
( )
The solution obtained by the greedy algorithm is X = {xi, i=1,...,n}, are the decision variables such that:
and the associated value of the objective function
deg ( ) is equal to 10. As the algorithm starts from , it chooses { ( )
in each clique the learning object with the lowest degree which is
and keeps going until it reaches .
The path is an alternative that the We suppose that x1 = 1 and xn = 1, knowing that:
algorithm did not find. It’s even a better alternative since
( ) ( ) and the optimal solution.
The following example highlights another case where local
optima obtained by the greedy algorithm lead to a non-optimum
solution. In this example, two learning objects are selected in one The function (1) represents the total number of prerequisite and
of the generated cliques. gained competencies to be minimized. The constraints (2) states
Example 3: that if the item i has competency j as one of its prerequisite
competencies; the competency j should be gained from the items
β6 on the learning path (1,…, i-1). Our problem is to minimize the
objective function (1) subject to (2) and (3).
v1 M65 N6,74 ↑ 6
To find the optimal learning path we have to solve the BIP
problem with (n+m) constraints and n decision variables xi=1,…n
v2 ↑ 4,5
O53,9 P48 { }
Considering example 3, the prerequisite and gain matrices Q and
v3 ↑ 3, 9, 8 G can be written as follows:
T87 Y97, Z37
The competencies that are required by the items are represented
α7 ↑ 7 by the matrix Q (9x7).
( )
The objective function of the path ( ) is 9,
which means that the path ( ) is the optimal
solution.
In the following section, we use the notation introduced here to
propose a mathematical formulation of our learning path
optimization problem as an integer programming problem.
( )
The competencies that are gained by the items are represented by structure the enumeration procedure so that only a tiny fraction of
the matrix G (9x7). feasible solutions need to be explored.
A well-known approach called branch-and-bound technique
(B&B) provides such a procedure. B&B traces back to the 1960s’
and the work of Land and Doig [14]. Since then, B&B algorithms
have been applied with success to a variety of operations research
problems. B&B is a divide and conquer method. It divides a large
problem into a few smaller ones (This is the “Branch” part). The
conquering part estimates the goodness of the solution that is
obtained from each of the sub-problems; the problem is divided
until solvable sub-problems are obtained (this is the “bound”
part).
( )
For the bounding part we use a linear programming relaxation to
estimate the optimal solution [26]. For an integer programming
The BIP formulation of example 3 is given as follows: model P; the linear programming model obtained by dropping the
requirement that “all variables must be integers” is called the
Minimize :
linear programming relaxation of P.
deg (X) = x1+2x2+2x3+2x4+3x5+2x6+2x7+3x8+x9
Subject to:
x2 - x1
x3 - x1
x4 - x1
x5 - x3
x5 - x4
x6 - x2
x7 - x5
x8 - x6
x9 – x7- x8
{ }
x1 is the fictitious learning object α with initial learner Figure 5. Branch and bound algorithm that traverses the tree
competency state. by solving BIPs at every node of the tree.
x9 is the fictitious learning object with targeted learner
competency state. The general approach of a BIP B&B algorithm [26] is presented
in the following steps (see also Figure 5):
Since x1 = x9 = 1, then our BIP becomes:
Initialization: Set deg* = + ∞.
Minimize :
The initial step represents the root node of the B&B search tree.
deg (X) = 2x2+2x3+2x4+3x5+2x6+2x7 +3x8
The root node corresponds to the continuous relaxation of the
Subject to: BIP(0≤ X ≤1), the solution value provides lower bound.
x5 - x3 Apply the bounding step, fathoming step, and optimality test
x5 - x4 described below. If not fathomed, classify this problem as the one
remaining “subproblems” for performing the first full iteration
x6 - x2 below.
x7 - x5 Steps for each iteration:
x8 - x6 1. Branching: Among the remaining (unfathomed)
- x7 - x8 subproblems, select the one that was created most
recently (break ties by selecting the subproblem with the
{ }
larger bound). Branch from the node for this
4.3 The Branch-and-Bound (B&B) method subproblem to create two new subproblems by fixing
the next variable (the branching variable) at either 0 or 1
for solving the BIP problem (see Figure 5).
Since the BIP problem is bounded, it has only a finite number of 2. Bounding For each new subproblem, obtain its bound
feasible solutions. It is then natural to consider using an by applying the simplex method to its LP-relaxation and
enumeration procedure to find an optimal solution. However, in rounding down the value of deg for the resulting
the case of large learning object repositories (millions of items), optimal solution.
an enumeration procedure might be ill adapted (even after 3. Fathoming (Pruning rules): The pruning rules for B&B
reducing the solution space); therefore, it is imperative to cleverly BIP are based on optimality and feasibility of BIP. For
each new sub-problem, apply the fathoming tests and on the dataset topology (average number of gain and prerequisite
discard those sub-problems that are fathomed by any of competencies per learning object). The solution space may remain
the tests. large after the reduction
Optimality test: Stop when there are no remaining sub-problems: Therefore, to deal with very large problems, we will implement a
variant of the B&B algorithm such as Branch & Cut [2] or Branch
The current incumbent is optimal,
& Price [4]. Applegate et al. [2] showed how Branch & Cut could
Otherwise, return to perform another iteration.
get a global optimal for extremely large binary optimization
A sub-problem is fathomed (dismissed from further consideration) problems. It will be then interesting to measure both in terms of
if it verifies one of the following tests: computational time and accuracy how the greedy search compares
1. The relaxation of the sub-problem has an optimal to the B&B-like approach.
solution with deg < deg where deg* is the current best
solution (The solution is dominated by upper bound);
6. ACKNOWLEDGMENTS
2. The relaxation of the sub-problem (LP-relaxation) has This work is part of the National Research Council of Canada’s
no feasible solution; Learning and Performance Support Systems (NRC LPSS)
3. The relaxation of the sub-problem has an optimal program. The LPSS program addresses training, development and
solution that has all binary values. (If this solution is performance support in all industry sectors, including education,
better than the incumbent, it becomes the new oil and gas, policing, military and medical devices.
incumbent, and test1 is reapplied to all unfathomed sub-
problems with the new larger deg*).
7. REFERENCES
[1] Alian, M. Jabri, R. 2009. A shortest adaptive learning path in
For example, the example 3 solved by B&B produces an optimal e-learning systems: Mathematical view, Journal of American
solution with deg* = 9 and x2=1, x6=1, x8=1 where the number of Science 5(6) (2009) 32-42.
nodes explored is 1 because the first LP-relaxation at node 1 gives
[2] Applegate, D., Bixby, R., Chvatal, V. and Cook, W. 1998.
an integer optimal solution with deg*=9 and the 3rd fathomed test
On The solution of traveling salesman problems, in: Proc.
is true, so we do not need to branch anymore.
Int. Congress of Mathematicians, Doc. Math. J. DMV, Vol.
Decision Variables x1 x2 x3 x4 x5 x6 x7 x8 x9 645.
LO α T Y Z O P M N [3] Atif, Y., Benlarmi, R., and Berri, J. 2003. Learning Objects
X* 1 1 0 0 0 1 0 1 1 Based Framework for Self-Adaptive Learning, Education
and Information Technologies, IFIP Journal, Kluwer
Figure 6. Solution of example 3in the B&B algorithm. Academic Publishers 8(4) (2003) 345-368.
[4] Bamhart, C, Johnson, E. L., Nemhauser, G. L., Savelsbergh,
M. W. P. and Vance, P. H. 1998. Branch-and-price: column
As illustrated in Figure 6, the optimal solution of the B&B generation for huge integer programs, Operations Research
algorithm is X*={1, 1, 0, 0, 0, 1, 0, 1, 1} and the optimal path is: 46:316.
.
[5] Barnes, T. 2005. The Q-matrix Method: Mining Student
5. CONCLUSION Response Data for Knowledge. Proceedings of the Workshop
The clique based approach is an asset since it offers an efficient on Educational Data Mining at the Annual Meeting of the
way to reduce the solution space and check the existence of a American Association for Artificial Intelligence.
solution. However, a greedy search within the cliques to find a [6] Carchiolo, V., Longheu, A., and Malgeri, M. 2010. Reliable
leaning path does not lead, in many cases, to the best learning path peers and useful resources: Searching for the best
according to the criteria considered. personalised learning path in a trust- and recommendation-
Binary integer programming is a well-known mathematical aware environment, Information Sciences 180(10) (2010)
optimization approach. While reformulating the conditions an 1893-1907.
optimal learning path should meet, we realised how we could [7] Durand, G., Belacel, N., and Laplante, F. 2013. Graph theory
benefit from expressing the constraints as a binary programming based model for learning path recommendation. Information
problem. Sciences. 251(10) (2013) 10-21.
Our preliminary implementation of the proposed optimization [8] Durand, G., Laplante, F. and Kop, R. 2011. A learning
using the bintprog function (MATLAB), a function based on the Design Recommendation System Based On Markov
branch- and-bound (B&B) algorithm, shows the accuracy of the Decision Processes, Proc. 17th ACM Conference on
proposed integer program model. Knowledge Discovery and Data Mining (SIGKDD)
In future work, we will apply the proposed binary integer model Workshop on Knowledge Discovery in Educational Data,
in order to build a learning design recommendation system in the San Diego, CA.
case where learning objects are stored in very large repositories. [9] Durand, G., Downes, S. 2009. Toward Simple Learning
Even though the B&B algorithm is highly accurate and somehow Design 2.0. In: 4th Int. Conf. on Computer Science
computationally efficient, it is not efficient enough to deal with &Education 2009, Nanning, China, 894-897.
very large size problem instances. In some cases, the bounding
step of B&B is not invoked, and the branch and bound algorithm [10] Godoy, D., Amandi, A. 2010. Link Recommendation in E-
can then generate a huge number of sub-problems. learning Systems based on Content-based Student Profiles,
In: Romero C., Ventura S., Pechenizkiy, M., Baker, R.
Moreover, as mentioned in [7], the efficiency of reducing the (Eds.), Handbook of Educational Data Mining, Data Mining
solution space with the cliques’ mechanism is highly dependent
and Knowledge Discovery Series, Chapman & Hall/CRC [20] Ullrich, C., Melis, E. 2010. Complex Course Generation
Press, 273-286. Adapted to Pedagogical Scenarios and its Evaluation,
[11] Huang, Y.M., Chen, J.N., Huang, T.C., Jeng, Y.L., and Kuo, Educational Technology & Society, 13 (2) (2010) 102–115.
Y.H. 2008. Standardized course generation process using [21] Ullrich, C., Melis, E. 2009. Pedagogically founded
Dynamic Fuzzy Petri Nets, Expert Systems with courseware generation based on HTN-planning, Expert
Applications, 34 (2008) 72-86. Systems with Applications 36(5) (2009) 9319-9332.
[12] ISO 24763/final version: Conceptual Reference Model for [22] Ullrich C. 2005. Course Generation Based on HTN Planning,
Competencies and Related Objects, 2011. Proc. 13th Annual Workshop of the SIG Adaptivity and User
[13] Karampiperis, P., Sampson, D. 2005.Adaptive learning Modeling in Interactive Systems, Saarbrucken, Germany,74-
resources sequencing in educational hypermedia systems. 79.
Educational Technology & Society 8 (4) (2005) 128-147. [23] Vassileva, J., Deters, R. 1998, Dynamic courseware
[14] Land, A. H., Doig, A. G. 1960. An automatic method of generation on the www, British Journal of Educational
solving discrete programming problems. Econometrica Technology, 29(1) (1998) 5–14.
28(3), 497–520. [24] Viet, A., Si, D.H. 2006. ACGs: Adaptive Course Generation
[15] Liu, J., Greer J. 2004. Individualized Selection of Learning System - An efficient approach to Build E-learning, Proc.
Object, In: Workshop on Applications of Semantic Web 6th IEEE International Conference on Computer and
Technologies for e-Learning, Maceió, Brazil. Information Technology, Jeju Island, Korea, 259-265.
[16] Pavlik, P. I. Jr., Presson, N., and Koedinger K. R. 2007. [25] Wiley, D.A. 2002. Connecting Learning Objects to
Optimizing knowledge component learning using a dynamic Instructional Design Theory: A Definition, a Metaphor, and a
structural model of practice, Proc. 8th International Taxonomy, In: The Instructional Use of Learning Objects,
Conference on Cognitive Modeling. Ann Arbor, MI. D. A. WILEY (Ed.), 3-23.
[17] Sicilia, M.-A., Sánchez-Alonso, S. and García-Barriocanal, [26] Winston, W.L., Venkataramanan, M. 2003. Operations
E. 2006. On supporting the process of learning design Research: Introduction to Mathematical Programming.
through planners, Proc. Virtual Campus Post-Selected and Thompson, 4th Edition.
Extended, 81–89. [27] Zhao, C., Wan, L. 2006. A Shortest Learning Path Selection
[18] Tang, T.Y., Mccalla, G.G. 2010. Data Mining for Contextual Algorithm in E-learning, Proc. 6th IEEE International
Educational Recommendation and Evaluation Strategies, In: Conference on Advanced Learning Technologies, Kerkrade,
Romero C., Ventura S., Pechenizkiy, M., Baker, R. (Eds.), The Netherlands, 94-95.
Handbook of Educational Data Mining, Data Mining and [28] Zhou, M., Xu, Y., Nesbit, J.C. and Winne, P.H. 2010.
Knowledge Discovery Series, Chapman & Hall/CRC Press, Sequential pattern analysis of learning logs: Methodology
Chapter 18,257-271. and applications, In: Romero C., Ventura S., Pechenizkiy,
[19] Trcka, N., Pechenizkiy, M. and Van-Deraalst, W. 2010. M., Baker, R. (Eds.), Handbook of Educational Data Mining,
Process Mining from Educational Data, In: Romero C., Data Mining and Knowledge Discovery Series, Chapman &
Ventura S., Pechenizkiy, M., Baker, R. (Eds.), Handbook of Hall/CRC Press, Chapter 8, 107-120.
Educational Data Mining, Data Mining and Knowledge
Discovery Series, Chapman & Hall/CRC Press, Chapter 9,
123-141.