2
$\begingroup$

I am not sure if I am in the right place but I am trying to find some infos or tutorial in one of my problem and I do not know where to look at or how this is call to help me in my research...

I am a variable, let's say it's a grade in school. For example I got 12 out of 20. My goal for next time is to get 16 out of 20. I can subscribe to many classes, all of them have a potential impact which will increase my grade. For example if it's a grade in math, the math class have a big impact, let's say 0.9 for example whereas the English class have an impact of 0.2 for this case.

In my problem, I have many variable (so many grade) with all of them I have a different goal. Example : Math 12/20 with goal of 16/20 Philosophy 8/20 with goal of 15/20 etc...

And I have my classes with many impact factor... I'd like to find a function which I will minimize it to find the optimum classes I have to take to increase my chance to get to my goal.

I need to find some algorithm about this trouble (of course, in my problem I will have many many variable, goal and impact factor...).

Some ideas where I can make some research about that ?

Thank you

EDIT

Let's take some examples with numbers. My impact factor will be between 0 and 1. 0 means no impact and 1 means a big impact. For example, if I'd like to improve my grade in Math (from 10/20 to 15/20) and that I take a Math class, the impact factor will be 1. But I have no idea for how much the Math grade will be increased...

Another example, maybe a physics class have a impact factor of let's say 0.6 for Math classes so maybe in a overall story with many grades to increase, it would be more beneficial to take a physics class than a math class because the physic class will increase a little bit math grade but also the physic grade and maybe the biology class...

So this is what I am to achieve. Which class you need to take that will minimize to sum of all the (targeted grades - actual grades)...

$\endgroup$
  • 1
    $\begingroup$ let's say you have for instance N subjects, then if I understand well, you have N fixed/known "impact factors" that correspond to the coefficients of each subject, N subgoals gi (= targeted grade in each subject i), and one overall objective which is the final grade G which is also known. You have then one equation with N unknown variables (all gi) which leads to an infinite number of solutions... What I'm not sure to understand is what you wanna try to minimise (nb of hours studying the subject ? N the number of subject ? Or the difference between targeted grades and the former grades?). $\endgroup$ – Jeanba Nov 19 '19 at 19:32
  • $\begingroup$ Thank you! I'd like to minimize the difference between targeted grades and the former grades $\endgroup$ – YLM Nov 21 '19 at 13:43
  • $\begingroup$ I think I start to understand what you are trying to achieve. There are still some things that are unclear to me however: (1) Are your targeted grade for each subject really already fixed? or do they rather represent a upper bound of what you think you would be able to perform? (2) Do you want to minimize the sum of the difference between your former and targeted grades or do you rather want to minimize the variance of the evolution of your grades? (might be more difficult to get +7 points in math than to get+3 in math + 3 in Physics + 3 in English and +3 in History ) $\endgroup$ – Jeanba Nov 21 '19 at 14:39
  • $\begingroup$ (1) it is what I think they would be able to perform. So for example if the impact factor is closed to 1 (impact factor is between 0 and 1, 0 = no impact, 1 = big impact) they will improved a lot the grade (but I have no idea how to know of how much they can improve... maybe this needs some machine learning to see afterwards the improvement of a grade depending of which classes they have attended..). (2) I'd like to minimize the sum of the difference between former and targeted grades). thank you $\endgroup$ – YLM Nov 22 '19 at 9:15
  • $\begingroup$ (2) then I think the pb is quite straightforward: Sort descending all the subjects according to their impact factor and add up the differences between the former and targeted grade. The sum should go from the subject with the higher impact factor to the subject that enables the sum of points to be sufficient for the global targeted grade to be reached. (1)How does it come you don't really know their actual impact on the grades? I thought your impact factors were related somewhat to the coefficients/credits associated with the subject. Could you give an example with numbers? $\endgroup$ – Jeanba Nov 22 '19 at 11:31
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.

$\endgroup$
  • $\begingroup$ Thank you. It helps! $\endgroup$ – YLM Nov 21 '19 at 13:41
  • $\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 Nov 21 '19 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 Nov 21 '19 at 16:37
  • 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 Nov 22 '19 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 Nov 22 '19 at 12:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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