# Student Course Allocation Problem with Many Constraints [closed]

Problem statement

In an university, there are $$t$$ course categories, $$m$$ courses, $$n$$ sections, $$p$$ students.

$$i$$-th section has:

1. A student capacity: $$cap_i$$.
2. Two lecture timings. (Formally, each section has two elements from $$S$$ associated with itself, where $$S$$ contains all lecture timings.)
3. A parent course $$course_i$$. ($$m \leq n$$)

$$i$$-th course has:

1. Some lecture section(s) under it. (As mentioned above.)
2. A parent course category $$category_i$$. ($$t \leq m$$)

Each student has ordered all $$n$$ sections from $$1$$ to $$n$$ on the basis of his/her preference.

Now, each student $$i$$ has to be allocated $$q_i$$ ($$2 \geq q_i \geq 1$$) sections such that:

1. No student has been allocated more than two or more section that have the same element(s) from $$S$$ associated with themselves. Formally, if the sets of lecture timings of allocated sections for a student $$i$$ are $$T_1$$, $$T_2$$, $$\cdots$$, $$T_{q_i}$$, then allocation should ensure that $$|T_1 \cup T_2 \cup \cdots \cup T_{q_i}| = 2{q_i}$$.
2. No student has been allocated two or more sections which have the same parent course.
3. No student has been allocated more than $$u$$ sections which have a parent course which have the same course category. ($$u \geq 1$$) Formally, let $$X$$ be a list of $$category_{course_{j}}$$ where $$j$$ is any section allocated to a student. The frequency of any element in $$X$$ should not exceed $$u$$.
4. No section $$j$$ is allocated to more than $$cap_j$$ students.
5. $$\sum_{j=1}^p cost(j)$$ is minimized. $$cost(x)$$ is defined as the sum of positions of the $$x$$th student's allocated sections in his/her preference list. For example, a student had ordered the courses P, Q, R, S in the order: R, Q, S, P. If he/she was allocated Q and S, cost() function will return 5. (2+3)

Constraints:

• $$1 \leq t \leq 7$$
• $$3 \leq m \leq 9$$
• $$5 \leq n \leq 30$$
• $$250 \leq p \leq 700$$
• $$\sum_{i=1}^p q_i \leq \sum_{i=1}^n cap_i$$

My take

I tried to represent the problem in the form of a k-partite graph. Doing so would have helped implement network flow algorithms like minimum-cost, maximum-flow. However, I have not been able to come up with any representation that satisfies all of the given constraints.