So, suppose you’re in university, it’s that time of the year again (i.e. exams) and you already have written some of them. Some are still left though and you wonder: How hard can you fail — or: how good do you have to be — in the following exams given that you do not want your *mean* grade to be worse than a given value.

## Linear programming

Say you’re in Germany and the possible grades are `[1, 1.3, 1.7, 2, .. 4]`

(i.e. a closed interval) with 1 being the best grade and 4 being only a minor step to a major fuckup. Given that you’ve already written four exams with the grades `1, 1, 1.3 and 1`

and that you do not want to have a mean grade worse than `1.49`

in the end (because 1.5 would be rounded to 2 on your diploma), but there still are 9 more exams to write, the question is: Which worst-case grades can you have in the following exams and what would that imply for the others?

This is what’s known to be a linear programming or linear optimization problem, and since the values (here: the number of grades) are constrained to be discrete values, it’s integer programming.

The goal of linear programming is to find the arguments \(x\) of the objective function \(f(x)\) such that \(f(x)\) is maximized, given some constraints on \(x\) . In Matlab, all linear programming functions try to minimize the cost function, so the problem is formulated as

\begin{align}

\underset{x}{\mathrm{min}} \, f(\vec{x}) \, \mathrm{such}\,\mathrm{that} \, \left\{\begin{matrix} \underline{A}\cdot \vec{x} \leq \vec{b} \\ \underline{A}_{eq} \cdot \vec{x} = \vec{b}_{eq} \end{matrix}\right.

\end{align}

Obviously, maximizing an objective function is the same as minimizing it’s negative, so \(\mathrm{max} \, f(\vec{x}) = -\mathrm{min} \left(\, -f(\vec{x}) \right)\) . In Matlab, these kind of problems can be solved with the `linprog`

function.

## Integer programming in Matlab is binary

Unfortunately, integer programming in Matlab is binary, meaning that the solutions \(x\) may be either `0`

or `1`

. (This is actually a lie, since you can very well use the genetic solver `ga`

, but let’s ignore that for a second.) So the discrete counterpart of `linprog`

in Matlab is `bintprog`

, as in binary integer programming. For our example, that’s pretty okay, because you can’t have a 3/4 grade in any exam; Either you do have that given grade or you don’t.

So, here’s a quick starter:

Let’s assume you wouldn’t expect anything worse than grade 2. This gives us four options and the objective function is.

\begin{align}

f(\vec{x}) = 1 x_1 + 1.3 x_2 + 1.7 x_3 + 2 x_4

\end{align}

Obviously only one grade is possible per class/exam, so we have to constrain these parameters to

\begin{align}

(1 x_1 + 1 x_2 + 1 x_3 + 1 x_4) \leq 1

\end{align}

saying that either none or exactly one parameter may be \(1\) . This works here, because \(0\) for all parameters won’t be the maximum of the objective function.

Also we want to find the combination of grades that is not worse than, say, \(1.5\) , so we have

\begin{align}

(1 x_1 + 1.3 x_2 + 1.7 x_3 + 2 x_4) \leq 1.5

\end{align}

which results in the following linear equation system of

\begin{align}

\begin{bmatrix}

1 & 1 & 1 & 1 \\

1 & 1.3 & 1.7 & 2

\end{bmatrix} \cdot \begin{bmatrix}

x_1 \\ x_2 \\ x_3 \\ x_4

\end{bmatrix} \leq \begin{bmatrix}

1 \\

1.5

\end{bmatrix}

\end{align}

Which corresponds to the following Matlab code:

f = [1 1.3 1.7 2]; A = [1 1 1 1; 1 1.3 1.7 2] b = [1; 1.5]; x = bintprog(-f, A, b) % note that we are minimizing f

Sure enough this will result in `x`

being `[0 1 0 0]`

(i.e. grade 1.3), which is the only possible solution to the problem.

## Taking it to the next level

Now the previous example was oversimplified, so let’s spice it up. Let’s say we already wrote 4 exams and the grades are \(\{1, 1, 1.3, 1\}\) ; let’s call this vector `have`

. We also know that there are \(N = 9\) exams left, which gives us `N = 9; M = N+length(have)`

, and that we expect grades in the closed interval of \([1, 1.3, 1.7, 2, .., 3]\) , which we’ll call `grades`

. Also, the worst case grade we want to achieve in the mean over all exams is given as \(1.49\) and this’ll be our `worst_case`

variable.

Now all of the possible `grades`

values will be allowed for each exam, so the inequation constraint for the mean grade would be

\begin{align}

\frac{1}{M} \left( \underbrace{h_1 + h_2 + \cdots + h_n}_{\mathrm{have}} + \sum_{i}^{N} \left( 1x_1^{(i)} + 1.3x_2^{(i)} + \cdots + 3x_n^{(i)} \right) \right) \leq 1.49

\end{align}

Unfortunately this means that the objective function is defined as

\begin{align}

f(\vec{x}, \vec{h}) &= \underbrace{h_1 + h_2 + \cdots + h_n}_{\mathrm{have}} \\

& + \underbrace{\left( 1x_1^{(1)} + 1.3x_2^{(1)} + \cdots + 3x_n^{(1)} \right)}_{\mathrm{exam 1}} \\

& + \underbrace{\left( 1x_1^{(2)} + 1.3x_2^{(2)} + \cdots + 3x_n^{(2)} \right)}_{\mathrm{exam 2}} \\

& + \cdots

\end{align}

and that means we have to replicate the `grades`

vector for every exam. Luckily Matlab sports a function called `repmat`

which repeats a given matrix (or vector) a given number of times.

So we define

have = [1 1 1.3 1]; % our known grades grades = [1 1.3 1.7 2 2.3 2.7 3]; % allowed grades N = 9; % number of exams left n = repmat(grades 1, N); % all possible grades for all exams g = [have n]; % our given values and all grades f = -g; % the objective function

after which the inequation constraint for the mean grade then is easily assembled as

M = N+length(have); % the total number of all grades worst_case = 1.49; % the worst-case mean grade A = g * (1/M); % weighted sum, i.e. mean value b = worst_case;

Some constraints are still to be enforced though:

- All
`have`

grades must be part of the solution vector - Exactly
`N`

grades must be selected from the expanded grade vector`n`

above.

These are our equality constraints. A solution to this would be

Aeq = [[ones(size(have)) zeros(size(n))]; % sum all the 'have' grades [zeros(size(have)) ones(size(n))]]; % sum all but the 'have' grades beq = [length(have); N];

Punching them into `bintprog`

gives us

x = bintprog(f, A, b, Aeq, beq);

Which will send Matlab sleeping for a couple of minutes, depending on the number of allowed grades and exams left. Matlab gives us `x`

which is a vector of the (binary) coefficients \(x_1, x_2, \cdots x_n\) to the objective functions.

In the end, we’ll just remove all the known grades `have`

from the result and print out the solution in terms of grades, like so:

% pick the grades from the (nonnegative) objective vector grades = g(x ~= 0); % remove all known grades while keeping duplicates while ~isempty(have) grades(find(grades == have(1), 1, 'first')) = []; have(1) = []; end % Print it out. there_you_go = sort(grades, 'descend')

And we’re set.

## Case study #1

Given the parameters

have = [1 1 1.3 1]; N = 9; worst_case = 1.49; grades = [1 1.3 1.7 2 2.3 2.7 3];

The optimization result is

there_you_go = 3 3 2.7 1.3 1 1 1 1 1

Meaning that you would be able to write two times a grade `3`

and also a `2.7`

without having to worry about your mean grade. You would then better resort to writing only `1.3`

and `1`

grades though for the rest of the exams.

## Case study #2

Assuming you can do better than `2.7`

, the parameters may be

have = [1 1 1.3 1]; N = 9; worst_case = 1.49; grades = [1 1.3 1.7 2 2.3];

And as a result, the optimization would yield

there_you_go = 2.3 2.3 2 1.7 1.7 1.7 1.3 1 1

Which I think looks better in the long term.

## Source code on GitHub

The source code for this breathtaking experiment can be found in bintprog_grades.m as a GitHub Gist. Have fun and coffee.