2
$\begingroup$

Consider a problem with many objectives. In my case, these are school grades for different courses (or subjects). To be more concrete, suppose that my current grade for the math course is $12/20$ and for the philosophy course is $8/20$. My objective is to get $16/20$ for the math course and $15/20$ for the philosophy course.

I have the possibility to take different courses, but I need to decide which ones. These courses can have a different impact depending on the subject. Let's say that the impact factor is in the range $[0, 1]$, where $0$ means no impact and $1$ means a big impact. Then the math course could have a big impact (e.g. $0.9$) on the grade, while maybe a philosophy course may not have such a big impact.

The overall goal is to increase all the grades as much as possible while taking into account the impact of their associated course. In my case, I can have more than two courses and subjects.

So, which algorithms can I use to solve this problem?

Improve this question
$\endgroup$
1
  • $\begingroup$ I have edited your post to simplify and hopefully clarify your explanation. Please, make sure that the current version is still consistent with your initial problem. Also, if you have found the solution to your problem, feel free to write an answer below or to accept an existing answer (if it solved your problem). $\endgroup$
    – nbro
    Commented Jun 21, 2020 at 16:32

1 Answer 1

Reset to default
2
$\begingroup$

From your description, the problem you want to solve is a linear optimization problem: suppose we use the indices $i$ and $j$ to denote the $i-$th class and the $j-$th grade. Also, let us call $y_j$ the current value of the $j-th$ grade, $g_j$ the goal value in grade $j$, $c_{ij}$ the impact factor of taking class $i$ in grade $j$, and $x_i$ the binary variable that indicates if you go to class $i$ or not. Now, suppose you decided to take certain classes (which is equivalent to choosing the values $x_i$ for each $i$) and measure the new grades $\tilde g_j$. If your impact factors are accurate, then the new grades should be $\tilde g_j = \sum_i(x_ic_{ij}+y_j)$. Clearly, what you would like is for this new values to be as close as possible to the goal values. So, a possible way to express your optimization problem is that you want to minimize the addition of all these differences:

$$\min_{x_0,\cdots,x_n} \sum_j g_j - \tilde g_j = \sum_j g_j - \sum_i(x_ic_{ij}+y_j), \\ \text{s.t. } x_i\in\{0,1\}, \forall\hspace 2pt i.$$

Most probably, you will have certain time restrictions. For example, maybe each class takes $t_i$ hours from your time and your total available time is just $T$ hours. Or maybe you have a limit of classes $N$ you can take, irrespective of their time duration. With these two constraints, your problem would look like this:

$$\min_{x_0,\cdots,x_n} \sum_j g_j - \sum_i(x_ic_{ij}+y_j), \\ \text{s.t. } x_i\in\{0,1\}, \forall\hspace 2pt i,\\ \sum_ix_it_i\leq T,\\ \sum_i x_i\leq N.$$

Apart from the constraint that $x_i$ should be 0 or 1, this is a linear optimization problem with linear constraints. Integer programming is an area of optimization that studies this type of problems so probably it's a good direction for your research.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I may have missed something but I am actually quite surprised about how the impact factors are taken into account here. Could you define them in a more explicit way? $\endgroup$
    – Jeanba
    Commented Nov 21, 2019 at 15:06
  • $\begingroup$ I just interpreted the "impact factor" of a class i in grade j as the value improvement that can be obtained in this grade j by taking class i. So, if x_i is 0, then there is no improvement, but if it is 1, the improvement is precisely the value of the impact factor. This is a simple model, but it's the one I understood was proposed in the question. $\endgroup$
    – Diego Gomez
    Commented Nov 21, 2019 at 16:37
  • $\begingroup$ the impact factor (as I have imagined in start) is a value between 0 and 1, with 0 = no impact and 1 = big impact. What I do not know is for how much the grade will be improved if I used the impact factor 1... This is something I am actually making some research... Probably will need some machine learning algorithm to test afterwards the impact of a class on the grades... to improve this impact factor value... $\endgroup$
    – YLM
    Commented Nov 22, 2019 at 9:17
  • 1
    $\begingroup$ You should consider using probabilistic graphical models if the impact factors (i.e., a linear model) turn out to be poor descriptors of the effect of taking one class in certain grade. Basically, they would allow you to model how certain interaction of classes affects the distribution of your grades. The benefit of this method is that it's easier to answer questions later of how does taking a class i affect the grade j, in comparison with deep learning methods. $\endgroup$
    – Diego Gomez
    Commented Nov 22, 2019 at 12:44
  • 1
    $\begingroup$ Of course, in that case the optimization problem would not be linear and Integer Programming would not be helpful. Non-linear optimization methods like stochastic gradient descent, which means neural networks too, could be helpful. However, I'm not sure how to assure in that case that your x's are either 0 or 1. $\endgroup$
    – Diego Gomez
    Commented Nov 22, 2019 at 12:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .