• ## Linear (binary) integer programming in Matlab

So, sup­pose you’re in uni­ver­si­ty, it’s that time of the year again (i.e. exams) and you already have writ­ten some of them. Some are still left though and you won­der: How hard can you fail — or: how good do you have to be — in the fol­low­ing exams giv­en that you do not want your mean grade to be worse than a giv­en val­ue.

## Linear programming

Say you’re in Ger­many and the pos­si­ble grades are [1, 1.3, 1.7, 2, .. 4] (i.e. a closed inter­val) with 1 being the best grade and 4 being only a minor step to a major fuck­up. Giv­en that you’ve already writ­ten 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 round­ed to 2 on your diplo­ma), but there still are 9 more exams to write, the ques­tion is: Which worst-case grades can you have in the fol­low­ing exams and what would that imply for the oth­ers?

This is what’s known to be a lin­ear pro­gram­ming or lin­ear opti­miza­tion prob­lem, and since the val­ues (here: the num­ber of grades) are con­strained to be dis­crete val­ues, it’s inte­ger pro­gram­ming.

The goal of lin­ear pro­gram­ming is to find the argu­ments $x$ of the objec­tive func­tion $f(x)$ such that $f(x)$ is max­i­mized, giv­en some con­straints on $x$ . In Mat­lab, all lin­ear pro­gram­ming func­tions try to min­i­mize the cost func­tion, so the prob­lem is for­mu­lat­ed 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}

Obvi­ous­ly, max­i­miz­ing an objec­tive func­tion is the same as min­i­miz­ing it’s neg­a­tive, so $\mathrm{max} \, f(\vec{x}) = -\mathrm{min} \left(\, -f(\vec{x}) \right)$ . In Mat­lab, these kind of prob­lems can be solved with the linprog func­tion.

## Integer programming in Matlab is binary

Unfor­tu­nate­ly, inte­ger pro­gram­ming in Mat­lab is bina­ry, mean­ing that the solu­tions $x$ may be either 0 or 1. (This is actu­al­ly a lie, since you can very well use the genet­ic solver ga, but let’s ignore that for a sec­ond.) So the dis­crete coun­ter­part of linprog in Mat­lab is bintprog, as in bina­ry inte­ger pro­gram­ming. For our exam­ple, that’s pret­ty okay, because you can’t have a 3/4 grade in any exam; Either you do have that giv­en grade or you don’t.

So, here’s a quick starter:

Let’s assume you wouldn’t expect any­thing worse than grade 2. This gives us four options and the objec­tive func­tion is.

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

Obvi­ous­ly only one grade is pos­si­ble per class/exam, so we have to con­strain these para­me­ters to

\begin{align}
(1 x_1 + 1 x_2 + 1 x_3 + 1 x_4) \leq 1
\end{align}

say­ing that either none or exact­ly one para­me­ter may be $1$ . This works here, because $0$ for all para­me­ters won’t be the max­i­mum of the objec­tive func­tion.
Also we want to find the com­bi­na­tion 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 fol­low­ing lin­ear equa­tion sys­tem 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 cor­re­sponds to the fol­low­ing Mat­lab 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 pos­si­ble solu­tion to the prob­lem.

## Taking it to the next level

Now the pre­vi­ous exam­ple was over­sim­pli­fied, 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 vec­tor 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 inter­val 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 giv­en as $1.49$ and this’ll be our worst_case vari­able.

Now all of the pos­si­ble grades val­ues will be allowed for each exam, so the inequa­tion con­straint 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}

Unfor­tu­nate­ly this means that the objec­tive func­tion 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 repli­cate the grades vec­tor for every exam. Luck­i­ly Mat­lab sports a func­tion called repmat which repeats a giv­en matrix (or vec­tor) a giv­en num­ber 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 inequa­tion con­straint for the mean grade then is eas­i­ly assem­bled 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 con­straints are still to be enforced though:

• All have grades must be part of the solu­tion vec­tor
• Exact­ly N grades must be select­ed from the expand­ed grade vec­tor n above.

These are our equal­i­ty con­straints. A solu­tion 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];


Punch­ing them into bintprog gives us

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


Which will send Mat­lab sleep­ing for a cou­ple of min­utes, depend­ing on the num­ber of allowed grades and exams left. Mat­lab gives us x which is a vec­tor of the (bina­ry) coef­fi­cients $x_1, x_2, \cdots x_n$ to the objec­tive func­tions.

In the end, we’ll just remove all the known grades have from the result and print out the solu­tion in terms of grades, like so:

% pick the grades from the (nonnegative) objective vector

% remove all known grades while keeping duplicates
while ~isempty(have)
have(1) = [];
end

% Print it out.


And we’re set.

## Case study #1

Giv­en the para­me­ters

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 opti­miza­tion result is

there_you_go =
3 3 2.7 1.3 1 1 1 1 1


Mean­ing that you would be able to write two times a grade 3 and also a 2.7 with­out hav­ing to wor­ry about your mean grade. You would then bet­ter resort to writ­ing only 1.3 and 1 grades though for the rest of the exams.

## Case study #2

Assum­ing you can do bet­ter than 2.7, the para­me­ters 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 opti­miza­tion would yield

there_you_go =
2.3 2.3 2 1.7 1.7 1.7 1.3 1 1


Which I think looks bet­ter in the long term.

## Source code on GitHub

The source code for this breath­tak­ing exper­i­ment can be found in bintprog_grades.m as a GitHub Gist. Have fun and cof­fee.