2

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?

nbro
  • 42,615
  • 12
  • 119
  • 217
YLM
  • 121
  • 3

1 Answers1

2

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.

Diego Gomez
  • 395
  • 4
  • 14