<p>There is ambiguity in your problem statement that, depending on how it is resolved, will change the algorithm that you would want to employ. I will discuss the ambiguity later.</p>
<p>As others have suggested, this falls into the domain of combinatorial optimization and there are many different OR tools that could be used to solve this.</p>
<p>To start, I would suggest employing a sequence of weighted bipartite matchings with (possibly) solution pruning.</p>
<p>Here is a solution written in python using networkx based on a sequence of two bipartite matchings (the first being a weighted one for students, the second being unweighted.)</p>
<pre><code>#!/usr/bin/python

&quot;&quot;&quot;
filename: student_assign.py
purpose:  demonstrate that the problem described in 
          https://stackoverflow.com/questions/62755778/modified-version-of-student-project-allocation-algorithm
          can be solved as a sequence of assignment problems solved through a weighted bipartite matching.
&quot;&quot;&quot;


import networkx as nx
import numpy as np

# For this demonstration we take data directly from the problem description
#supervisor | Topics of Interest | No. Of Groups
#L1         | P1, P3, P4         |     2
#L2         | P5, P2, P9         |     1
#L3         | P1, P3, P4         |     1
#L4         | P1, P3, P4         |     4
#L5         | SP1, P3, P8        |     3
#L6         | P32, P3, P40       |     3


supervisors = {
        'L1' : { 'topics' : ['P1', 'P3', 'P4'], 'num_groups' : 2},
        'L2' : { 'topics' : ['P5', 'P2', 'P9'], 'num_groups' : 1},
        'L3' : { 'topics' : ['P1', 'P3', 'P4'], 'num_groups' : 1},
        'L4' : { 'topics' : ['P1', 'P3', 'P4'], 'num_groups' : 4},
        'L5' : { 'topics' : ['SP1', 'P3', 'P8'], 'num_groups' : 3},
        'L6' : { 'topics' : ['P32', 'P3', 'P40'], 'num_groups' : 3},
        }

all_topics = sorted(list({ t  for s in supervisors for t in supervisors[s]['topics'] }))


# assuming there is a typo in the problem specification and 'supervisor' = 'student' below
#supervisor | Pref1 | Pref 2 | Pref 3 | Pref 4 |
#S1         |  P4   |  P1    |  SP1   |   P5   |
#S2         |  P1   |  P9    |  SP1   |   P5   |
#S3         |  P3   |  P1    |  P2    |   P5   |
#S4         |  P4   |  P1    |  P40   |   P5   |
#S5         |  P4   |  P32   |  SP1   |   P5   |
#S6         |  P9   |  P1    |  SP1   |   P5   |

students = {
        'S1' : ['P4', 'P1', 'SP1', 'P5'] ,
        'S2' : ['P1', 'P9', 'SP1', 'P5'] ,
        'S3' : ['P3', 'P1', 'P2', 'P5'] ,
        'S4' : ['P4', 'P1', 'P40', 'P5'] ,
        'S5' : ['P4', 'P32', 'SP1', 'P5'] ,
        'S6' : ['P9', 'P1', 'SP1', 'P5'] ,
        }

MAX_GROUP_SIZE = 2


def get_student_assignments_to_topics(all_topics,students,max_group_size=MAX_GROUP_SIZE):
    G = nx.DiGraph()
    G.add_node('sink',demand=len(students))

    for topic in all_topics:
        G.add_node(topic)
        G.add_edge(topic, 'sink', weight = 0, capacity = max_group_size)

    for student in students:
        prefs = students[student]
        G.add_node(student,demand=-1)
        # add increasing weight edges from student to preferences (lowest == best)
        for i, topic in enumerate(prefs):
            G.add_edge(student, topic, weight = i, capacity = 1)

    # solve the weighted matching
    flow_dict = nx.min_cost_flow(G)

    # decode which student is assigned to which topic
    student_assignments = { t : [] for t in all_topics}
    for student in students:
        adjacency = flow_dict[student]
        prefs = students[student]
        for pref in prefs:
            if adjacency[pref]:
                student_assignments[pref].append(student)
                break

    return student_assignments


def get_topic_assignments_to_supervisors(student_assignments,supervisors):
    non_empty_student_assignments = { topic : student_assignments[topic] for topic in student_assignments if len(student_assignments[topic]) &gt; 0}

    G = nx.DiGraph()
    G.add_node('sink',demand=len(non_empty_student_assignments))

    for topic in non_empty_student_assignments:
        G.add_node(topic,demand=-1)

    for supervisor in supervisors:
        supervisor_properties = supervisors[supervisor]
        for topic in supervisor_properties['topics']:
            if topic in non_empty_student_assignments:
                G.add_edge(topic, supervisor, weight = 0, capacity = 1)
        G.add_edge(supervisor, 'sink', weight = 0, capacity = supervisor_properties['num_groups'])

    # solve the unweighted matching
    flow_dict = nx.min_cost_flow(G)

    # decode which supervisor is assigned to which topic
    topic_assignments = { s : [] for s in supervisors}
    for supervisor in supervisors:
        supervisor_properties = supervisors[supervisor]
        for topic in supervisor_properties['topics']:
            if topic in non_empty_student_assignments:
                adjacency = flow_dict[topic]
                if adjacency[supervisor]:
                    topic_assignments[supervisor].append(topic)

    return topic_assignments




# assign students to topics by preference
student_assignments = get_student_assignments_to_topics(all_topics,students)
# assign all topics with at least one student to a supervisor who fits the criteria
topic_assignments = get_topic_assignments_to_supervisors(student_assignments,supervisors)

print 'These are the assignment of students to topics based on preference:'
print student_assignments
print 'These are the assignment of topics to supervisors based on availability:'
print topic_assignments
</code></pre>
<p>This script outputs:</p>
<pre><code>These are the assignment of students to topics based on preference:
{'P2': [], 'P3': ['S3'], 'P1': ['S2', 'S1'], 'P4': ['S5', 'S4'], 'P5': [], 'SP1': [], 'P8': [], 'P9': ['S6'], 'P32': [], 'P40': []}
These are the assignment of topics to supervisors based on availability:
{'L6': [], 'L4': ['P1', 'P3'], 'L5': [], 'L2': ['P9'], 'L3': ['P4'], 'L1': []}

</code></pre>
<h2>Ambiguity</h2>
<p>There is ambiguity as to how you want to handle important edge cases:</p>
<ul>
<li>what if topics have no interest from students?</li>
<li>what if a topic only has one interested student?</li>
<li>students may have to rank all possible topics to ensure a solution exists?</li>
<li>should supervisors have preference for topics as well (if so whose preference takes precedence?)</li>
<li>should supervisor assignment to topics be load balanced (solutions with all supervisors having similar amount of work being preferred)?</li>
</ul>
<p>Answers to these specific questions that disambiguiate are very important and will shape the type of solution you craft (as well as being able to communicate to users of your algorithm what exactly is optimized.)</p>
<p>I definitely recommend you spend more time disambiguiating your problem.</p>
<h2>Solution existence</h2>
<p>The sequential bipartite matching algorithm presented here will find optimal solutions; however, it may not find <em>a</em> solution even if one exists.</p>
<p>This can happen if the solution of the first matching produces a set of projects for which there is no assignment of supervisors.</p>
<p>One possible way to address this is to systematically search through subsets of possible projects until a solution exists (see pruning below.)</p>
<h2>Pruning solutions</h2>
<p>If some assignments of students to topics is unfavorable, an easy way to prevent that solution from being possible is to set weights of student-topic assignment very high (infinity.) This gives a structured way to prune unwanted pairings:</p>
<ol>
<li>Solve the weighted bipartite matching</li>
<li>Identify undesirable student-topic pairing</li>
<li>Set weight to infinity or remove edge between student-topic pairing, resolve.</li>
</ol>
<h2>Efficiency</h2>
<p>Here python was used with networkx to optimize prototyping ability <em>not</em> efficiency. If you wish to scale this solution to large problem sizes, I would recommend the lemon MCF library (in particular the cost scaling <a href="https://arxiv.org/pdf/1207.6381.pdf" rel="nofollow noreferrer">MCF algorithm</a>) or Andrew V Goldberg's original cost-scaling MCF algorithm <a href="https://github.com/iveney/cs2" rel="nofollow noreferrer">implementation</a>.</p>
<p>In my experience benchmarking MCF, these are the two most competitive implementations. I don't have experience with Google-OR's implementation of MCF.</p>
Modified version of Student Project Allocation algorithm
<p>I am working on a project for a non-profit organization where they are trying to help students with special needs to match to different project topics. Each student will have four preferences and a set of supervisors will have their list of preferences on the topics they supervise.</p>
<p>The solution I look for is an algorithm which can find an optimum solution to match students to project topics and supervisors.</p>
<p>I have done extensive reading on SPA, HR and other Greedy Algorithms and even tried a flavour of Genetic algorithm. So far I have nothing but stress.</p>
<p>Here is the flow of the program.</p>
<ol>
<li>We have a pool of topics for supervisors to show their interest. Supervisors can pick topics where they like to supervise and they can also suggest a topic and decide how many project groups they would like to supervise.</li>
</ol>
<p><code>P1, P2, P3, P4, P5 ...... Pn ... SP1, SP2, SP3 .... SPn</code></p>
<p>In the above list, <code>P1 ... Pn</code> are existing topics and <code>SP1...SPn</code> are suggested topics.</p>
<p>Let's say after this round, we have a list of supervisors with the following preference.</p>
<pre><code>supervisor | Topics of Interest | No. Of Groups
L1         | P1, P3, P4         |     2
L2         | P5, P2, P9         |     1
L3         | P1, P3, P4         |     1
L4         | P1, P3, P4         |     4
L5         | SP1, P3, P8        |     3
L6         | P32, P3, P40       |     3

</code></pre>
<p>After the above round, we know that there are only supervisors who can Supervise students on the following topics.</p>
<p><code>P1, P2, P3, P4, P8, P9, P32, P40, SP1</code></p>
<ol start="2">
<li>When we open the topics for the students, they will only be able to pick projects from the above list, with their preference/priority. For example</li>
</ol>
<pre><code>student    | Pref1 | Pref 2 | Pref 3 | Pref 4 |
S1         |  P4   |  P1    |  SP1   |   P5   |
S2         |  P1   |  P9    |  SP1   |   P5   |
S3         |  P3   |  P1    |  P2    |   P5   |
S4         |  P4   |  P1    |  P40   |   P5   |
S5         |  P4   |  P32   |  SP1   |   P5   |
...
Sn         |  P9   |  P1    |  SP1   |   P5   |

</code></pre>
<p>Now, once the students pick the preference, We will then decide a number <code>MAX_GROUP_SIZE</code> and we will run our algorithm to group these students into partitions where we will</p>
<p>a. Group students with similar interests into same group ( eg. We add Students who picked P1 as their <code>pref1</code> and fill in the rest with <code>pref2, pref3, pref4</code> when they don't have groups for their first choices).
b. Assign a supervisor to a group where he has shown interest in the project ( Ideally, every students first preferences or best-matched project)
c. We need to make sure that we don't overload the supervisor, if a supervisor has shown interest in <code>P1, P2, P3</code> and mentioned that he can only supervise <code>2</code> projects, then we should only add him to <code>2</code> projects.</p>
<p>So far, I have been trying the above-explained algorithms and I still don't think I have a justified solution for the students. I prefer a solution which is more biased towards the students since they have special needs. If anyone can point me in the right direction or can provide me with a well-defined algorithm or an implementation I would not only appreciate the effort but I would buy you a coffee as well.</p>