An efficient two-heuristic algorithm for the student-project allocation with preferences over projects

1 Introduction

In project-based courses, students must be assigned to projects to build projects together. To do this, either lecturers can propose a list of students for their projects or departments can assign students to lecturers for doing projects. If doing so, it is evident that there exist conflicts not only among lecturers but also among students since lecturers usually choose good academic students for their projects, while students typically choose projects based on their preferences. The question for this problem is how to allocate students to projects to meet the preference requirements of both students and lecturers. To solve this problem, Abraham et al. introduced the Student-Project Allocation problem (SPA) in 2003 [1]. In particular, an instance of SPA involves three non-empty sets of students, projects, and lecturers. Each lecturer offers a set of projects and ranks a subset of students in strict order of preference in their lists to whom they intend to supervise, while each student ranks a subset of the available projects in a strict order of preference in their lists that they find acceptable. Moreover, each project is offered by a unique lecturer, both projects and lecturers have capacity constraints to indicate the maximum number of students assigned to projects and lecturers. In this context, a stable matching refers to an assignment of students to projects such that there exist no student-project unstable pairs, i.e., the student and project are not matched together in the matching, but they prefer each other to their current assigned partners in the matching. Then, they proposed a student-oriented algorithm running in a linear time to find a student-optimal stable matching for a given instance of SPA, in which each student is assigned to the most preferred project they could get in any stable matching. In 2007, Abraham et al. [2] extended their work and introduced two algorithms for SPA. The first one is a student-oriented algorithm described in their previous work [1], while the second one is a lecturer-oriented algorithm running in a linear time to find a lecturer-optimal stable matching for a given instance of SPA, in which each lecturer is assigned to the most preferred students to whom they could get in any stable matching.

In practical applications, requiring each lecturer to rank a subset of students in a strict order as in SPA is unfair for both lecturers and students. For example, lecturers often strongly prefer to supervise students with good academic results rather than students with poor academic results. This sometimes leads to conflicts among lecturers and students. Moreover, if there are many students in SPA, it is difficult for lecturers to rank students in their lists. For these reasons, in 2008, Manlove and O’Malley [12] proposed a variant of SPA, called SPA with preferences over Projects (SPA-P), where lecturers rank a subset of projects in strict order rather than a subset of students in their lists. Given an instance of SPA-P, Manlove and O’Malley [12] showed that stable matchings could have different sizes, and the problem of finding a maximum stable matching is NP-hard even if each project and lecturer has a capacity 1.

In the last few years, several researchers have proposed efficient approximation algorithms and provided the lower and upper bounds for SPA-P. An algorithm is said to be an r-approximation algorithm for SPA-P if it results in a stable matching M with |M _opt |/|M|  ≤  r for all SPA-P instances, where M _opt is the stable matching of maximum size. In 2008, Manlove and O’Malley [12] extended the well-known Gale-Shapley algorithm [5] to propose a 2-approximation algorithm with linear time complexity, namely SPA-P-approx. This algorithm consists of a sequence of proposals, in which an unassigned student with a non-empty list proposes the most preferred project on her/his list to form student-project pairs of a matching such that the lecturers and projects satisfy their capacity constraints. The algorithm returns a stable matching in a finite number of iterations. In 2012, Iwama et al. [6] extended the SPA-P-approx [12] using Király’,s idea [8] and proposed a 3 2 -approximation algorithm with a linear time complexity, namely SPA-P-approx-promotion, to find a stable matching for instances of SPA-P. In 2020, Viet et al. [16] considered SPA-P as a constraint satisfaction problem and proposed a local search approach based on the min-conflicts algorithm [13, 15] to solve it. Recently, Manlove et al. [10, 11] investigated an integer programming approach to SPA-P and proposed a 3 2 -approximation algorithm to find stable matchings that are very close to having maximum cardinality over their tested instances.

So far, both SPA and SPA-P have received significant attention from the research community for their roles in developing automated systems for student project allocation. Several examples can be found at various institutions, such as the School of Computing Science at the University of Glasgow [9], the Faculty of Science at the University of Southern Denmark [3], and the Department of Computing Science at the University of York [7].

Our contribution : In this paper, we first analyze the weaknesses of the SPA-P-approx [12] and the SPA-P-approx-promotion [6] algorithms for solving the SPA-P problem. Accordingly, we propose two heuristic functions to improve the drawbacks of the SPA-P-approx and SPA-P-approx-promotion algorithms. We then propose an efficient two-heuristic algorithm, namely SPA-P-heuristic, for solving the SPA-P problem. We also show that our algorithm returns a stable matching after a finite number of iterations. To conduct our experiments, we propose a method to generate random SPA-P instances. Our experimental results over all the tested scenarios show that our proposed algorithm is much more efficient than the SPA-P-approx [12] and SPA-P-approx-promotion [6] algorithms in terms of execution time and solution quality for SPA-P instances of large sizes. Therefore, our algorithm can be applied to develop intelligent systems for student-project allocation.

The remainder of this paper is structured as follows. Section  gives a formal definition of SPA-P, Section algorithm presents our proposed algorithm, Section experiments discusses the experiments, and Section conclusions concludes our work.

2 SPA-P problem

In this section, we remind the SPA-P problem given in [6, 12]. An instance I of the SPA-P problem comprises a set S = {s₁, s₂, ⋯ , s _n } of students, a set P = {p₁, p₂, ⋯ , p _q } of projects, and a set L = {l₁, l₂, ⋯ , l _m } of lecturers, where (i) Each lecturer l _k  ∈ L offers a non-empty set P _k of projects in strict order of preference in their lists, subject to P₁ ∪ P₂ ∪ ⋯ ∪ P _m  = P and P _{k 1}  ∩ P _{k 2}  =   ∅ ,   ∀ k₁ ≠ k₂; (ii) Each student s _i  ∈ S ranks a non-empty set A _i  ⊆ P of projects in strict order of preference in their lists; (iii) Each lecturer l _k  ∈ L has a capacity d k ∈ ℤ + to indicate the maximum number of students to whom they can supervise; and (iv) Each project p _j  ∈ P has a capacity c j ∈ ℤ + to indicate the maximum number of students who can work p _j together. Hereafter, we use the list of notations shown in Table \ref tab:symbol for reader convenience.

For ∀s _i  ∈ S, ∀l _k  ∈ L, and ∀p _j  ∈ P, we denote rank (s _i , p _j ) and rank (l _k , p _j ) by the rank of p _j in s _i ’s and l _k ’s lists, respectively. If s _i and l _k prefer p _j as the α ^th and β ^th choices in their lists (1 ≤ α, β ≤ q), then rank (s _i , p _j ) = α and rank (l _k , p _j ) = β, respectively. For ∀p _j  ∈ A _i and ∀p _t  ∈ A _i , if s _i prefers p _j to p _t , we denote by rank (s _i , p _j ) < rank (s _i , p _t ). For ∀p _j  ∈ P _k and ∀p _t  ∈ P _k , if l _k prefers p _j to p _t , we denote by rank (l _k , p _j ) < rank (l _k , p _t ). Moreover, we denote rank (s _i , p _j ) =0 for ∀p _j  ∈ P \ A _i and rank (l _k , p _j ) =0 for ∀p _j  ∈ P \ P _k .

An assignmentM in I is a subset of S × P such that if (s _i , p _j ) ∈ M, then p _j  ∈ A _i . If l _k offers p _j and (s _i , p _j ) ∈ M, then we say that s _i is assigned to p _j and l _k in M, p _j is assigned to s _i in M, and l _k is assigned to s _i in M.

For ∀s _i  ∈ S, we denote M (s _i ) by the set of projects assigned to s _i in M and |M (s _i ) | by the number of projects in M (s _i ). If M (s _i ) =∅, then we say that s _i is unassigned in M. For ∀p _j  ∈ P, we denote M (p _j ) by the set of students assigned to p _j in M and |M (p _j ) | by the number of students in M (p _j ). If |M (p _j ) | > c _j , |M (p _j ) | < c _j , or |M (p _j ) | = c _j , then we say that p _j is over-subscribed, under-subscribed, or full, respectively. For ∀l _k  ∈ L, we denote M (l _k ) by the set of students assigned to l _k in M and |M (l _k ) | by the number of students in M (l _k ). If |M (l _k ) | > d _k , |M (l _k ) | < d _k , or |M (l _k ) | = d _k , then we say that l _k is over-subscribed, under-subscribed, or full, respectively.

A matchingM in I is an assignment such that |M (s _i ) |≤1, |M (p _j ) | ≤ c _j , and |M (l _k ) | ≤ d _k for ∀s _i  ∈ S, ∀p _j  ∈ P, and ∀l _k  ∈ L. If |M (s _i ) |=1, we denote M (s _i ) by the project assigned to s _i in M.

A pair (s _i , p _j ) ∈ (S × P) \ M is a blocking pair for a matching M if all the following conditions are met, where p _t  = M (s _i ): 1. 1.

p _j  ∈ A _i , i.e., s _i finds p _j acceptable;

OPEN IN VIEWER

Table 2

An instance of the SPA-P problem

Students’ lists	Lecturers’ lists	Students’ ranks	Lecturers’ ranks
s1: p1  p2  p5	l1: p3  p1  p2	s1: 1  2  0  0  3	l1: 2  3  1  0  0
s2: p1  p4	l2: p4  p5	s2: 1  0  0  2  0	l2: 0  0  0  1  2
s3: p2  p1  p4		s3: 2  1  0  3  0
s4: p3		s4: 0  0  1  0  0
s5: p3  p4		s5: 0  0  1  2  0
s6: p5  p3  p4		s6: 0  0  2  3  1
Projects’ capacities: c1 = 2, c2 = 2, c3 = 1, c4 = 1, c5 = 2.
Lecturers’ capacities: d1 = 3, d2 = 3.

A matching M in I is called stable if no blocking pair exists for M; otherwise, M is called unstable. Given a stable matching M, we denote |M| by the number of students assigned in M, i.e., the size of M. If |M| = n, then M is called perfect; otherwise, M is called non-perfect. The SPA-P problem aims to find a stable matching with maximum size, known as MAX-SPA-P [12].

An instance I of the SPA-P problem is given in Table \ref tab:SPA-P-Example, where S = {s₁, s₂, s₃, s₄, s₅, s₆}, P = {p₁, p₂, p₃, p₄, p₅}, L = {l₁, l₂}. The students’ and lecturers’ lists columns show the preference lists of students and lecturers over projects, respectively, i.e., A₁ = {p₁, p₂, p₅}, A₂ = {p₁, p₄}, A₃ = {p₂, p₁, p₄}, A₄ = {p₃}, A₅ = {p₃, p₄}, A₆ = {p₅, p₃, p₄}, P₁ = {p₃, p₁, p₂}, and P₂ = {p₄, p₅}. The students’ and lecturers’ ranks columns show the rank of projects in the students’ and lecturers’ lists, respectively, where if s _i and l _k prefer p _j as the α ^th and β ^th choices in their lists, then rank (s _i , p _j ) = α and rank (l _k , p _j ) = β. For example, in the students’ lists, we write “s₁: p₁p₂p₅”, meaning that s₁ prefers p₁ as the first choice, p₂ as the second choice, and p₅ as the third choice and therefore, rank (s₁, p₁) =1, rank (s₁, p₂) =2, and rank (s₁, p₅) =3 in the students’ ranks. We use similar notations in the lecturers’ lists. The matching M = {(s₁, p₅), (s₂, p₁), (s₃, p₂), (s₄, p₃), (s₅, p₄)} is unstable because there exist two blocking pairs consisting of (s₁, p₁) and (s₆, p₅) for M. Specifically, (s₁, p₁) ∉ M and s₁ prefers p₁ to p₅, so s₁ should be assigned to p₁. Meanwhile, (s₆, ∅) ∉ M, s₆ prefers the most p₅, and |M (p₅) | < c₅, so s₆ should be assigned to p₅. The matching M = {(s₁, p₁), (s₂, p₁), (s₃, p₄), (s₄, p₃), (s₆, p₅)} is a stable matching of size |M|=5. On the contrary, the matching M = {(s₁, p₅), (s₂, p₁), (s₃, p₁), (s₄, p₃), (s₅, p₄), (s₆, p₅)} is a maximum stable matching and it is also perfect since its size is |M|=6.

\label sec:algorithm

In this section, we first propose two heuristic functions used in our algorithm. Then, we propose an algorithm to find stable matchings of maximum size for the SPA-P problem. Finally, we give an execution of our algorithm for the SPA-P instance given in Table \ref tab:SPA-P-Example.

3.1 Heuristic definitions

\label sec:heuristic-definition

We consider the SPA-P-approx [12] and SPA-P-approx-promotion [6] algorithms for finding maximum stable matchings of SPA-P instances. The main principle of SPA-P-approx is as follows. At the beginning, the algorithm initializes a matching M to be empty, meaning that every student is unassigned to any project offered by lecturers. At each iteration, the algorithm finds the first project p _j of an unassigned student s _i with a non-empty list. If p _j is full, meaning that p _j does not have a slot for s _i , then the algorithm deletes p _j from s _i ’s list so that it does not choose p _j for s _i in the next iterations. Otherwise, the algorithm provisionally assigns p _j to s _i to form a stable pair (s _i , p _j ) ∈ M. When p _j is assigned to s _i , the lecturer l _k who offered p _j is assigned to s _i . If l _k is over-subscribed, the algorithm removes an arbitrary student s _r from M (p _z ), where p _z is l _k ’s worst non-empty project, and deletes p _z in s _r ’s list. Meanwhile, SPA-P-approx-promotion [6] algorithm runs as follows. At the beginning, the algorithm marks all students as unpromoted. At each iteration, the algorithm chooses the first project p _j of an unassigned student s _i with a non-empty list at each iteration. If p _j is full, the algorithm removes an arbitrary student s _r from M (p _j ) and adds (s _i , p _j ) to M. If l _k is over-subscribed, the algorithm removes an arbitrary student s _r from M (p _z ) such that l _k is full, where l _k is the lecturer who offered p _j and p _z is l _k ’s worst non-empty project in M (l _k ).

We found that removing an arbitrary student s _r in M (p _j ) or M (p _z ) is a weak point of both SPA-P-approx and SPA-P-approx-promotion algorithms. For example, we consider a specific case where the three following conditions are met: (i) M (p _z ) consists of at least two students s _r and s _w ; (ii) s _r ranks only one project; and (iii) s _w ranks more than one project. If we remove s _r from M, then s _r is unassigned in M forever, while if we remove s _w from M, then s _w can be assigned to some project in her/his list at the next iterations.

In the general case, we find in each iteration of the above algorithms that when a project p _j  ∈ A _i is assigned to a student s _i  ∈ S, if p _j is over-subscribed, we need to remove a student from M (p _j ) so that p _j is full. We recognize that the student removed from M (p _j ) should have the most remaining projects in her/his list since she/he has the most opportunity to be assigned to some project at the next iterations. Moreover, when a project p _j is assigned to a student s _i , the lecturer l _k who offered p _j can be over-subscribed. If l _k is over-subscribed, we need to remove a student from M (l _k ) so that l _k is full. To keep M stable, the student removed from M (l _k ) must be a student assigned to a project p _z , which is l _k ’s worst non-empty project, so that condition (3c) in the definition of a blocking pair is not violated. Similar to the case where p _j is over-subscribed, the student removed from M (p _z ) should have the most remaining projects in her/his list since she/he has the most opportunity to be assigned to some project at the next iterations. To solve these two issues, we propose two heuristic functions as follows:

Case 1: When a project p _j is over-subscribed, we propose a heuristic function for every student s _r  ∈ M (p _j ) as follows:

f ( s r ) = rank ( l k , p j ) + | A r | / ( q + 1 ) , ∀ s r ∈ M ( p j ) ,

(1)

where |A _r | is the number of projects in A _r and q is the number of projects in P. Then, the student is chosen to be removed from M as follows:

s w = argmax ( f ( s r ) ) , ∀ s r ∈ M ( p j ) .

(2)

It is evident that a student s _w determined by Equation \eqref eq:fsw means that rank (l _k , p _j ) is maximum and |A _w | is maximum. If we remove s _w from M (p _j ), then we keep the students in M (p _j ) who have the least opportunity to be reassigned to projects in their lists and remove the student s _w in M (p _j ) who has the most opportunity to be reassigned to some project in her/his list at the next iterations, since the student s _w ranks the most projects in her/his list.

Case 2: When a lecturer l _k is over-subscribed, we propose a heuristic function for every student s _r  ∈ M (l _k ) as follows:

g ( s r ) = rank ( l k , p z ) + | A r | / ( q + 1 ) , ∀ s r ∈ M ( l k ) ,

(3)

where p _z  = M (s _r ) is a project offered by l _k . Then, the student is chosen to be removed from M as follows:

s w = argmax ( g ( s r ) ) , ∀ s r ∈ M ( l k ) .

(4)

Similarly, a student s _w determined by Equation \eqref eq:gsw means that rank (l _k , p _z ) is maximum and |A _w | is maximum, where p _z  = M (s _w ). Since rank (l _k , p _z ) is a positive integer number and 0 < |A _w |/(q + 1) <1, if we remove such a student s _w meaning that p _z is l _k ’s worst non-empty project and s _w ranks the most projects in her/his list. By doing so, we not only keep M stable but also keep in M (l _k ) the students who have the least opportunity to be reassigned to projects in their lists and remove the student s _w in M (l _k ) who has the most opportunity to be reassigned to some project in her/his list at the next iterations.

Since the student s _w removed from M (p _j ) and M (l _k ) corresponds to the maximum f (s _w ) and g (s _w ) values given in Equations \eqref eq:fsw and \eqref eq:gsw, we call such a student s _w the worst student removed from either M (p _j ) or M (l _k ).

3.2 Algorithm for SPA-P

\label sec:SPA-heuristic

Our heuristic algorithm for finding maximum stable matchings of SPA-P instances, namely SPA-P-heuristic, is shown in Algorithm 1. During the execution of the algorithm, each student is marked active (i.e., a (s _i ) =1) or inactive (i.e., a (s _i ) =0). At the beginning, every student s _i  ∈ S is active and unassigned in M. At each iteration, if there exists an active student s _i with an empty list, then she/he becomes inactive forever (i.e., a (s _i ) =0). Therefore, she/he is unassigned in M and the algorithm runs the next iteration (lines 5–8). Otherwise, she/he is assigned to her/his most preferred project p _j to form a pair (s _i , p _j ) in M, and she/he becomes inactive (lines 9–12). If p _j is over-subscribed, then the worst student s _w in M (p _j ) determined by Equation \eqref eq:fsw is removed from M (lines 14–15), s _w deletes p _j in her/his list (line 16), and she/he becomes active again (line 17). If l _k is over-subscribed, then the worst student s _w in M (l _k ) determined by Equation \eqref eq:gsw is removed from M (lines 20–22). If so, s _w deletes p _z in her/his list, where p _z is offered by l _k and assigned to s _w (line 23), and she/he becomes active again (line 24). The algorithm repeats until all students are inactive and returns a stable matching.

Lemma 3.1.\label alg:terminate SPA-P-heuristic terminates after a finite number of iterations.

Proof. Given an instance I of SPA-P, we have each student s _i  ∈ S ranked |A _i | projects. Initially, every student s _i  ∈ S is marked active. At each iteration, a student s _i is assigned to her/his most preferred project p _j and she/he becomes inactive. When s _i is assigned to p _j , the lecturer l _k who offered p _j is assigned to s _i . If both p _j and l _k are not over-subscribed, then the algorithm terminates after n iterations. If p _j or l _k is over-subscribed, then some student s _w  ∈ M (p _j ) or s _w  ∈ M (l _k ), respectively, is removed from M. If so, s _w deletes M (s _w ) from her/his list and becomes active again. Although s _w becomes active, since s _w deletes M (s _w ) in her/his list, s _w is not reassigned to M (s _w ). Thus, if some student s _r is not assigned to any project, then s _r deletes every project p _t  ∈ A _r , making s _r ’s list empty and s _r inactive forever. We let

OPEN IN VIEWER

S = S₁ ∪ S₂, where S₁ is a set of students assigned to projects and S₂ is a set of students not assigned to any project. If so, we have (i) S₁∩ S₂ = ∅; (ii) every s _i  ∈ S₁ is inactive since s _i is assigned to some project in her/his list; and (iii) every s _r  ∈ S₂ is inactive since s _r ’s list is empty after deleting |A _r | projects in her/his list. This shows that all students are inactive after a finite number of iterations and therefore, the algorithm terminates since it runs when there exists an active student s _i  ∈ S. \myend

Lemma 3.2.\label alg:time SPA-P-heuristic finds a solution of SPA-P in O (n × q²) time.

Proof. It follows by the proof of Lemma 3.1 that in the best case, where every student is assigned to the first preferred project in their lists to form a stable matching, our algorithm takes O (n) time. In the worst case, where every student ranks all the projects in P and proposes the last preferred project in their lists, our algorithm takes O (n × q) time. When a project p _j is over-subscribed, our algorithm finds the worst student s _w in M (p _j ) to remove from M, so it takes O (q) time in the worst case. When a lecturer l _k is over-subscribed, our algorithm finds the worst student s _w in M (l _k ) to remove from M, so it takes O (m) time in the worst case. Therefore, our algorithm takes O (n × q × (O (q) + O (m)) = O (n × q × max (q, m)) time to find a solution of SPA-P. Since each lecturer must propose at least one project, we have q ≥ m or max (q, m) = q. This shows that our algorithm takes O (n × q × max (q, m)) = O (n × q²) time to find a solution of SPA-P. \myend

Lemma 3.3. SPA-P-heuristic returns a stable matching.

Proof. We assume that the algorithm returns a matching M and there exists a blocking pair (s _r , p _t ) ∈ (S × P) \ M for M. During the execution of the algorithm, we consider two cases:

Case 1: If p _t is not deleted from s _r ’s list, then s _r ’s list is not empty. If s _r is unassigned in M, then s _r is marked active. If so, the while loop would not have terminated and we get a contradiction with Lemma 3.1. Hence, s _r is assigned in M. Since we assume that (s _r , p _t ) blocks M, i.e., s _r prefers p _t to p _z  = M (s _r ). However, when s _r proposes p _z , p _z was the first project on s _r ’s list and we get a contradiction. Hence, M is stable.

Case 2: If p _t is deleted from s _r ’s list, then this occurs when (i) p _t is over-subscribed. If so, p _t becomes full and (s _r , p _t ) cannot block M; or (ii) l _k is over-subscribed, where l _k is the lecturer who offered p _t . If so, g (s _r ) is maximum as shown in Equation \eqref eq:gsw, i.e., rank (l _k , p _t ) is maximum and |A _r | is maximum. Since rank (l _k , p _t ) is a positive integer number and 0 < |A _r |/(q + 1) <1, meaning that p _t is l _k ’s worst non-empty project in M (l _k ). Now l _k becomes full in M and l _k ’s worst non-empty project in M (l _k ) is better than p _t . Hence, (s _r , p _t ) cannot block M. Since we assume that (s _r , p _t ) blocks M, we get a contradiction. Hence, M is stable.\myend

In this section, we present some experiments to evaluate the performance of our SPA-P-heuristic algorithm. We chose the SPA-P-approx [12] and SPA-P-approx-promotion [6] (for short, we call it SPA-P-promotion) algorithms to compare their solution quality and execution time with those of our SPA-P-heuristic algorithm since both SPA-P-approx and SPA-P-promotion are approximation algorithms with a linear time complexity. We implemented three algorithms by Matlab R2019a software on a laptop computer with Core i7-8550U CPU 1.8 GHz and 16 GB RAM, running on Windows 11.

Datasets. To conduct our experiments, we generated random SPA-P instances with four parameters (n, m, q, σ), where n is the number of students, m is the number of lecturers, q is the number of projects, and σ is the total capacity of q projects offered by all the lecturers, i.e., σ = ∑ j = 1 q c j . Given four parameters (n, m, q, σ), our method to generate a random SPA-P instance is as follows:

1. 1.

Generate a set S = {1, 2, ⋯ , n} of students, a set P = {1, 2, ⋯ , q} of projects, and a set L = {1, 2, ⋯ , m} of lecturers.

2.

Generate randomly non-empty sets P₁, P₂, ⋯ , P _m of projects such that P₁ ∪ P₂ ∪ ⋯ ∪ P _m  = P and P _i ∩ P _j  = ∅ for i = 1, 2, ⋯ m, j = 1, 2, ⋯ m, and i ≠ j. We consider P _k as a set of projects offered by lecturer l _k  ∈ L (l _k  = 1, 2, ⋯ , m).

3.

Iterate for each l _k  ∈ L and each p _j  ∈ P, if p _j is at the position β ^th in P _k , then we set rank (l _k , p _j ) = β; otherwise, we set rank (l _k , p _j ) =0. By doing so, we have a rank matrix of all the lecturers.

4.

Distribute the total capacity σ of all the projects randomly to the capacity c _j of each project p _j  ∈ P (j = 1, 2, ⋯ , q) such that 0 < c _j  < σ and ∑ j = 1 q c j = σ .

5.

Calculate the total capacity ρ _k of all the projects p _j  ∈ P _k and generate the capacity d _k of each lecturer l _k  ∈ L by setting d _k to be some percentage of ρ _k (e.g., d _k  = 100 % ρ _k , or d _k is a random integer number such that 80 % ρ _k  ≤ d _k  ≤ 100 % ρ _k ).

6.

Generate randomly non-empty sets A₁, A₂, ⋯, A _n of projects such that A _i  ⊆ P. We consider A _i as a set of projects proposed by student s _i  ∈ S (i = 1, 2, ⋯ , n).

7.

Iterate for each s _i  ∈ S and each p _j  ∈ P, if p _j is at the position α ^th in A _i , then we set rank (s _i , p _j ) = α; otherwise, we set rank (s _i , p _j ) =0. By doing so, we have a rank matrix of all the students.

As a result, our method represents an instance of SPA-P by a rank matrix of students, a rank matrix of lecturers, a capacity list of projects, and a capacity list of lecturers, which are inputs for our algorithm.

In our experiments, we generated 100 instances of SPA-P for each value of n. In each instance, we chose the values of m and q to make the student-to-lecturer ratio and the student-to-project ratio suitable for real applications. Besides, σ is chosen based on the value of n. To compare the performance of our SPA-P-heuristic algorithm with that of SPA-P-approx and SPA-P-promotion algorithms for SPA-P instances, we ran SPA-P-heuristic, SPA-P-approx, and SPA-P-promotion algorithms for each instance to find their solution and execution time. Then, we determined the percentage of perfect matchings, the average of unassigned students, and the average execution time found by each algorithm run on 100 instances of SPA-P to compare their performance.

4.1 Experiment 1

OPEN IN VIEWER

Fig. 1

Comparing solution quality and execution time of SPA-P-heuristic, SPA-P-approx, and SPA-P-promotion algorithms.

In this experiment, we chose the values of parameters n, m, and q as shown in Table \ref SPA-P-experiments. For each value of n varying from 500 to 5000 with steps 500, we generated 100 instances of SPA-P of parameters n, m, and q, where m and q are random numbers constrained by 0.02n ≤ m ≤ 0.1n and 0.1n ≤ q ≤ 0.4n, respectively. The constraints of m and q mean that the student-to-lecturer ratio is from 10 to 50 and each lecturer offers from 1 to 20 projects. In each instance, we let each student randomly rank from 1 to 20 projects in the set of projects offered by all lecturers. We set the total capacity σ of projects offered by all lecturers as n, i.e., σ = n. Then, we distributed σ randomly to the capacity c _j of each project p _j  ∈ P to ensure that ∑ j = 1 q c j = σ and 1 ≤ c _j  ≤ 100. Besides, we set the capacity d _k of each lecturer l _k to the total capacity of projects offered by l _k , i.e., d _k  = ∑c _t , where c _t is the capacity of projects p _t  ∈ P _k . By setting so, this scenario is a challenging experiment for the algorithms to find perfect matchings in SPA-P instances since each student has only a slot to be assigned to each project in their lists.

Figure 1(a) shows the percentage of perfect matchings found by SPA-P-heuristic, SPA-P-approx, and SPA-P-promotion algorithms. When n increases from 500 to 5000 with steps 500, SPA-P-heuristic finds a much higher percentage of perfect matchings than SPA-P-promotion and SPA-P-approx. Specifically, SPA-P-heuristic finds from 73% to 88% of perfect matchings, SPA-P-promotion finds from 51% to 73% of perfect matchings, while SPA-P-approx fails to find any perfect matchings of SPA-P instances.

Figure 1(b) shows the average number of unassigned students found by SPA-P-heuristic, SPA-P-approx, and SPA-P-promotion algorithms. When n increases from 500 to 5000 with steps 500, SPA-P-approx finds stable matchings with more than 22 unassigned students. Meanwhile, SPA-P-heuristic finds fewer unassigned students in stable matchings than SPA-P-promotion. This means that the stable matchings found by SPA-P-heuristic are larger than those found by SPA-P-promotion in terms of size.

OPEN IN VIEWER

Fig. 2

Comparing solution quality and execution time of SPA-P-heuristic, SPA-P-approx, and SPA-P-promotion algorithms.

Figure  1(c) shows the average execution time of SPA-P-heuristic, SPA-P-approx, and SPA-P-promotion algorithms. When n increases from 500 to 5000 with steps 500, the average execution time of SPA-P-approx increases from 0.0097 seconds to 5.2027 seconds, the average execution time of SPA-P-promotion increases from 0.0327 seconds to 3.9276 seconds, and the average execution time of SPA-P-heuristic increases from 0.0150 seconds to 2.5655 seconds. We see that when n ≥ 4000, SPA-P-heuristic runs about two times faster than SPA-P-promotion and SPA-P-approx.

Figure 1(d) shows the average number of iterations found by SPA-P-heuristic, SPA-P-approx, and SPA-P-promotion algorithms. We see that the average number of iterations found by SPA-P-heuristic is slightly smaller than that found by SPA-P-promotion, but larger than that found by SPA-P-approx. However, the average execution time of SPA-P-heuristic is much smaller than that found by SPA-P-promotion and SPA-P-approx, meaning that at each iteration, SPA-P-heuristic needs a smaller computation than SPA-P-promotion and SPA-P-approx.

In this experiment, we chose the values of parameters n, m, and q as those constraints in Experiment 1. In each randomly generated instance of SPA-P, we set each student to rank randomly from 1 to 20 projects in the set of projects offered by all lecturers. Moreover, we set the total capacity σ of projects offered by all lecturers as 1.1n, i.e., σ = 1.1n, and distributed σ randomly to the capacity c _j of each project p _j  ∈ P such that ∑ j = 1 q c j = σ and 1 ≤ c _j  ≤ 100. Besides, we set the capacity d _k of each lecturer l _k  ∈ L to a random integer number in [0.9ρ _k , ρ _k ], where ρ _k is the total capacity of projects offered by l _k . This means that σ = ∑ k = 1 m ρ k = ∑ j = 1 q c j = 1.1 n . Since 0.9ρ _k  ≤ d _k  ≤ ρ _k , we have 0.9 ∑ k = 1 m ρ k ≤ ∑ k = 1 m d k ≤ ∑ k = 1 m ρ k , i.e., 0.99 n ≤ ∑ k = 1 m d k ≤ 1.1 n . Therefore, if some generated instances that 0.99 n ≤ ∑ k = 1 m d k < n , then they have not any perfect matching.

Figure 2(a) shows the percentage of perfect matchings found by SPA-P-heuristic, SPA-P-approx, and SPA-P-promotion algorithms. When n varies from 500 to 5000 with steps 500, SPA-P-heuristic finds from 74% to 89% of perfect matchings, SPA-P-promotion finds from 69% to 85% of perfect matchings, while SPA-P-approx finds only from 0% to 20% of perfect matchings. It is obvious that SPA-P-heuristic finds a higher percentage of perfect matchings than SPA-P-promotion and SPA-P-approx. Compared to Experiment 1, we can see that when the total capacity of projects increases, i.e., the capacity of each project increases, it is easy for these algorithms to find perfect matchings in SPA-P instances.

Figure 2(b) shows the average number of unassigned students found by SPA-P-heuristic, SPA-P-approx, and SPA-P-promotion algorithms. When n increases from 500 to 5000 with steps 500, SPA-P-approx results in stable matchings with more than 15 unassigned students. In contrast, SPA-P-heuristic yields stable matchings with fewer unassigned students than SPA-P-promotion. This means that the stable matchings found by SPA-P-heuristic are larger than those generated by SPA-P-promotion in terms of size.

Figure 2(c) shows the average execution time of SPA-P-heuristic, SPA-P-approx, and SPA-P-promotion algorithms. When n varies from 500 to 5000 in increments of 500, the average execution time of SPA-P-approx increases from 0.0083 seconds to 3.1844 seconds, the average execution time of SPA-P-promotion increases from 0.0220 seconds to 3.0629 seconds, and the average execution time of SPA-P-heuristic increases from 0.0083 seconds to 1.0946 seconds. This shows that SPA-P-promotion and SPA-P-approx exhibit similar execution time, while SPA-P-heuristic runs approximately three times faster than both SPA-P-promotion and SPA-P-approx.

Figure 2(d) shows the average number of iterations used by SPA-P-heuristic, SPA-P-approx, and SPA-P-promotion algorithms. As in Experiment 1, we can see that SPA-P-heuristic used a smaller number of iterations than SPA-P-promotion, but a larger number of iterations than SPA-P-approx. Moreover, we can see that when the total capacity of projects increases, all these three algorithms not only find stable matchings faster than those, but also use a smaller number of iterations compared to those in Experiment 1.

4.3 Experiment 3

OPEN IN VIEWER

Fig. 3

Comparing solution quality and execution time of SPA-P-heuristic, SPA-P-approx, and SPA-P-promotion algorithms.

In this experiment, we chose n = 5000 and varied the total capacity σ of projects offered by all lecturers from 0.8n to 1.5n with steps 0.1n, i.e., σ varied from 4000 to 7500 with steps 500. For each combination of parameter values n and σ, we generated 100 instances of SPA-P, in which other parameters were set as follows: (i) m and q were random integer numbers constrained by 0.02 ≤ m ≤ 0.1n and 0.1n ≤ q ≤ 0.4n, i.e., 100 ≤ m ≤ 500 and 500 ≤ q ≤ 2000; (ii) σ was distributed randomly to the capacity c _j of each project p _j  ∈ P such that ∑ j = 1 q c j = σ and 1 ≤ c _j  ≤ 120; and (iii) d _k of each lecturer l _k  ∈ L was a random integer number such that 0.8ρ _k  ≤ d _k  ≤ 1.2ρ _k , where ρ _k is the total capacity of projects offered by l _k . As mentioned in Experiment 1, the constraints of m and q mean that the student-to-lecturer ratio was chosen from 10 to 50 and each lecturer offered from 1 to 20 projects.

Figure 3(a) shows the percentage of perfect matchings found by SPA-P-heuristic, SPA-P-approx, and SPA-P-promotion algorithms. We see that when the total capacity σ ∈ {4000, 4500}, all these three algorithms cannot find any perfect matching since we have σ < n, i.e., the total capacity σ of projects is not enough slots for n students. However, when σ = 5000, i.e., each project has only a slot for each student, all these three algorithms cannot find any perfect matching. When σ increases, the percentage of perfect matchings found by these algorithms increases since the capacity of projects and lecturers increases. However, SPA-P-heuristic finds a higher percentage of perfect matchings than SPA-P-approx and SPA-P-promotion.

Figure 3(b) shows the average of unassigned students found by SPA-P-heuristic, SPA-P-approx, and SPA-P-promotion algorithms. When σ increases, the average of unassigned students found by these algorithms decreases, meaning that the sizes of stable matchings increase. Moreover, we see that SPA-P-heuristic finds stable matchings whose sizes approximate those of SPA-P-promotion (i.e., the green line overlaps the blue line) but are larger than those of SPA-P-approx.

Figure 3(c) shows the average execution time of SPA-P-heuristic, SPA-P-approx, and SPA-P-promotion algorithms. When σ increases, the average execution time found by these algorithms decreases since the capacity of projects and lecturers increases, making these algorithms find stable matchings easier. When σ increases from 4000 to 7500, the average execution time of SPA-P-heuristic decreases from 7.66 seconds to 0.36 seconds, the average execution time of SPA-P-approx decreases from 53.28 seconds to 0.75 seconds, and the average execution time of SPA-P-promotion decreases from 113.82 seconds to 0.78 seconds. When σ = 4000, SPA-P-heuristic runs about 15 times faster than SPA-P-promotion and about 7 times faster than SPA - P - approx. When σ ≥ 5500, SPA-P-heuristic runs about 2 times faster than SPA-P-promotion and SPA-P-approx. In particular, when σ decreases from 5000 to 4000, the execution time of SPA-P-approx and SPA-P-promotion significantly increases, while that of SPA-P-heuristic almost remains unchanged.

Figure 3(d) shows the average number of iterations used by SPA-P-heuristic, SPA-P-approx, and SPA-P-promotion algorithms. As in Experiments 1 and 2, we see that SPA-P-heuristic used a smaller number of iterations than SPA-P-promotion, but a larger number of iterations than SPA-P-approx.

In summary, we see from the three experiments above that SPA-P-heuristic outperforms SPA-P-approx and SPA-P-promotion in solution quality and execution time. This can be explained as follows:

1.

In SPA-P-approx, there are two main reasons to show that this algorithm performed poorly in finding maximum matchings for SPA-P instances. Firstly, when an unassigned student s _i with a non-empty list chooses the first project p _j in her/his list, if p _j is full, then p _j is not assigned to s _i . However, if s _i has only a project p _j in her/his list and if the algorithm does not assign p _j to s _i , then s _i is single. Since M (p _j ) is a set of students assigned to p _j , if the algorithm removes some student from M (p _j ) and assigns p _j to s _i , then s _i is not single. Secondly, when a student s _i is assigned to a project p _j in her/his list, meaning that s _i is assigned to a lecturer l _k who offered p _j . If l _k is over-subscribed, the algorithm removes an arbitrary student s _r from M (p _z ), where p _z is l _k ’s worst non-empty project, and deletes p _z in s _r ’s list. If s _r remains only a project p _z in her/his list, then s _r becomes single. Since M (p _z ) is a set of students assigned to p _z and in this case, the algorithm should remove another student from M (p _z ) rather than s _r . Moreover, removing an arbitrary student s _r from M (p _z ) makes the algorithm find a stable matching difficult, leading to inefficient execution time.

2.

In SPA-P-approx-promotion, If a project p _j is full, the algorithm removes an arbitrary student s _r from M (p _j ) and adds (s _i , p _j ) to M. If a lecturer l _k is over-subscribed, the algorithm removes an arbitrary student s _r from M (p _z ), where l _k is the lecturer who offered p _j and p _z is l _k ’s worst non-empty project in M (l _k ). Similar to SPA-P-approx, removing an arbitrary student s _r in M (p _j ) or M (p _z ) is a weak point of SPA-P-approx-promotion. Moreover, when a student s _i with a non-empty list is unpromoted, she/he is allowed to recover her/his original list once again to find a project again in her/his list. This makes the algorithm inefficient in execution time.

3.

In SPA-P-heuristic, our heuristic functions f (x) and g (x) given in Equations \eqref eq:fx and \eqref eq:gx are used to keep the students in M who have the least opportunity to be reassigned to projects in their lists and remove the students in M who have the most opportunity to be reassigned to projects in their lists. Therefore, our SPA-P-heuristic solves the weaknesses of SPA-P-approx and SPA-P-promotion algorithms.

Finally, the scenarios of our experiments, where n = 5000, m ranges from 100 to 500, and q ranges from 500 to 2000, show that our SPA-P-heuristic results in maximum stable matchings in approximately 1.0 to 7.0 seconds. This underscores the remarkable efficiency of SPA-P-heuristic for dealing with large SPA-P instances.

5 Conclusions

In this paper, we propose a SPA-P-heuristic algorithm to find maximum stable matchings of SPA-P instances. At the beginning, our algorithm initializes a matching to be empty and sets all the students to be active. At each iteration, our algorithm finds an active student with a non-empty list. If such a student exists, our algorithm assigns to her/him the most preferred project in her/his list to form a student-project pair in the matching. If the assigned project overcomes its capacity, our algorithm uses a heuristic function to remove the worst student among students assigned to the project in the matching. If the lecturer who offered the project overcomes her/his capacity, our algorithm uses another heuristic function to remove the worst student among students assigned to the lecturer in the matching. When a student is assigned to a project, she/he becomes inactive. When a student removes a project assigned to her/him, she/he deletes the project from her/his list and becomes active again. Our algorithm repeats until all the students are inactive. We show that our algorithm returns a stable matching after a finite number of iterations. Our experimental results over all the tested scenarios show that our SPA-P-heuristic algorithm outperforms SPA-P-approx and SPA-P-promotion algorithms regarding solution quality and execution time for SPA-P instances of large sizes.

The SPA-P problem consists of variants such as the Student-Project Allocation with preferences over Projects with Ties (SPA-PT), the Student-Project Allocation problem with lecturer preferences over Students (SPA-S) [2], or the Student-Project Allocation problem with lecturer preferences over Students with Ties (SPA-ST) [4, 14]. Therefore, our approach can be extended by defining suitable heuristic functions to solve these problems efficiently.