I am currently working on creating an algorithm to solve a complex assignment problem. The problem is basically as follows: there are d "sessions" each with m "sections" each with some maximum capacity; there are n people that will each give r preferences for each session. The objective is to assign optimally the people to one section per session.
The algorithm that I am thinking about is a linear program as follows.
First, let Pⱼ∈[r]ᵈˣᵐ be the matrix of preferences for the j-th person (so it each element is ranked 0-r for each section in each session). Then we have M∈[n]ᵈˣᵐ as the matrix of section capacities. Then, we will define the variables Aⱼ∈{(0,1)}ᵈˣᵐ as the (unnormalized) assignment probabilities of the j-th person for each section in each session.
We will maximize:
∑ⱼ〈Aⱼ,Pⱼ〉
Subject to
0 < A_{jkl} < 1 ∀ (i,j,k)
∑ⱼ Aⱼᵢₖ≤Mᵢₖ ∀ (i,k)
The last step is to give final assignments for each person in each section using Aⱼₖ/∑ᵢAⱼₖᵢ as a categorical probability distribution for the j-th person in the k-th session.
Does this approach seem like it will give an approximately correct answer? If so, how would I go about finding the approximation ratio? If not, any tips on better approaches would be much appreciated. This is definitely a very difficult program to set up, so I apologize if my explanation was a bit hard to follow. I am happy to clarify anything.