0
$\begingroup$

I'm trying to do an assignment problem with the following characteristics:

I have two sets that need to be matched with each other, set A (Students) and set B (Class combinations). Set A and B have the same number of rows (there's 100% matching and no leftovers in either set)

Each row in Set A is a student with multiple categorical attributes (Gender, Age Group, Country of Residence etc). There can be any amount of attributes and each attribute can have any number of options (Age Group can be in bins of 5 or 10 etc).

Each row in Set B is a set of classes that each student in Set A can attend, such as (Physics, Chemistry, Linguistics). Each row has the same amount of classes (3 classes per row for example), and Y amount of classes to choose from. There are no repeating classes within a row, and the positional sequence of each class doesn't matter ([Physics, Chemistry] is the same as [Chemistry, Physics])

What I'm trying to do is match each student in set A to a class combination in set B such that each class in set B is taken by students of equal proportions across all student attribute. For example, if Country of Residence was 70:30 in set A between USA and Canada, the proportions of students taking each class should also be 70:30. This should apply to all student attributes in set A and classes in set B.

I understand that because it's not possible to match everything perfectly it would end up being a minimization problem where you minimize an error term that determines how far the class proportion is from the actual student proportion. However I've never dealt with assignment problems where both sides have attributes that need matching (worker and job), nor have I found any resources online about such problems and frankly don't know where to begin formulating this as an LP. If there's anyone who can provide advice about how to begin formulating such a problem that can be translated to a solver like or-tools (everything linearized as much as possible) would be extremely helpful.

EDIT 1:

Based on Sutanu's answer I've gotten some headway but I'm still slightly confused on the matching part.

I have 1 optimization variable:
Binary $x_{s,r}$ = Student s is taking row r

1 intermediary variable dependent on the optimization variable:
Binary $y_{s,c}$ = Student s is taking class c (Dependent on $x_{s,r}$)

1 preset binary variable for rows to class:
Binary $z_{r,c}$ = Row r contains class c
Functionally equivalent to $c_r$ in Sutanu's response

Preset binary variables for each categorical attribute and student
Binary $att_{s,a,b}$ = Student s is attribute a for given categorical attribute b (a = US/Canada for b = Country, or a = Fresh/Soph/Jr/Sr for b = Year etc)
(Intended to be functionally equivalent to $d_s$ in Sutanu's response)

Overall Constriants:
$\sum_{s}^{}x_{s,r} = 1$ forcing 1 row to be taken by 1 student
$\sum_{r}^{}x_{s,r} = 1$ forcing 1 student to take only 1 row

Linearization of $x_{s,r}$ & $z_{r,c}$ => $y_{s,c}$ :
$y_{s,c} \leqslant x_{s,r}$
$y_{s,c} \leqslant z_{r,c}$
$y_{s,c} \geqslant x_{s,r} + z_{r,c} - 1$

My question at the moment is: How exactly do I link $att_{s,a,b}$ and $y_{s,c}$ to make a variable that determines the number of students for a given attribute (US/Canada) are in a given class? Is the only way to make another binary variable $yatt_{s,a,b,c}$ if student s of attribute a in categorical attribute b is taking class c and linearize that for $att_{s,a,b}$ and $y_{s,c}$ => $yatt_{s,a,b,c}$?

I understand that this variable is what I should constrain to keep within the desired proportions (30% Canada / 70% USA etc), but I don't really know if there is a better way to create this variable than making $yatt_{s,a,b,c}$.

$\endgroup$

2 Answers 2

1
$\begingroup$

You'd need two optimization variables
Binary $ x_{s,r} = 1$ if student $s$ from set A is matched with row $r$ from set B
Binary $ y_{s,c} = 1$ of student is matched to a class $c$

Derived sets/matrix where each row
$c_r = \{r \in B \ | \ c \in r \} \ \ \forall$ classes $c$

$ d_s = \{s \in A | \ s \in d \} \ \forall $ attributes. Basically a set of attribute matrices where in each row constaints the students sharing that attribute. For example, a matrix called Country will have a row indexed as US containing students who are from US. Similarly for Canada.

Constraints
$ y_{s,c} \le \sum_{r \in c_r}x_{s,r} \le My_{s,c}$
where $M$ can be total number of classes any student is allowed to take

$ \sum_s x_{s,r} \ge 1 \quad \forall r$: match all rows to atleast 1 student

$ \sum_r x_{s,r} = 1 \quad \forall s$: match all students to 1 row

Proportion (expression not a constraints)
US_{class} = $ \sum_s U_sy_{s,c}$
Can_{class} = $ \sum_s C_s y_{s,c}$

So one of your objectives for the country will be like
$ \sum_s (3U_s y_{s,c} - 7C_sy_{y,c})$

Edit
You may use preset variables (basically constants) where $att_{a,b,s} = 1$ if student $s$ has value $b$ for attribute $a$.
So for a proportion constraint on an attribute
$\sum_s att_{a,b,s}y_{s,c} = p_{a,b} \sum_s y_{s,c} \quad \forall (a,b) \ \ \forall c$ where $p$ is the proportion for the value $b$ for the attribute $a$.

If using set $A_b$ that contains list of students $s$ with value $b$ for attribute $A$ then
$\sum_{s \in A_b} y_{s,c} = p_{a,b}\sum_s y_{s,c} \ \ \forall c$

$\endgroup$
1
  • $\begingroup$ Thank you for the comment. I've edited the question such that the 1st constraint is not needed (The intended question specs have all rows having the same number of classes making the 1st constraint redundant) I've also edited the question based on your comments and added a followup question about how exactly to link $d_s$ to the binary $y_{s,c}$ to then constrain the number of students of a given attribute attending a class to the desired proportions $\endgroup$
    – Riezz
    Aug 29, 2023 at 3:56
0
$\begingroup$

create 1 Boolean var per pair of (student, course)

Write the linear equations that constrain the model

Decide on the objective

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.