Linear programming for fun and profit

This is a story of papers, probabilities, and puzzles, of essays, exams, and engineering: a story of general education requirements and linear programming solvers.

As finals week started in Spring term, after more than a year and a half of books and essays, I was finally at the end of HUM, UCSD’s grueling gen-ed writing and literature sequence. I faced just one final obstacle: the final exam of the final course of the sequence. From one essay to the next, my grade had been falling, and with how I’d been doing in HUM 5, all depended on this one exam. I was not prepared.

The Problem

Here was the format of the test:

• The lecturer posted in advance a list of five potential essay prompts for the final exam.
• At the start of the exam, the lecturer would pick three of the five prompts to give to us.
• During the exam, I would have to write essays responding to two of the three chosen prompts, and I’d be graded on both.

Everything was at stake, and yet I had so little time to prepare! I desperately needed to make optimal use of my time. Here were my own constraints:

1. I’ll assume the lecturer chooses randomly, and suppose without loss of generality I study most for prompt 1, less for prompt 2, etc., and least for prompt 5.
2. I’d like to prepare as little as possible for the exam, but I’d like to expect to be at least 95% prepared.

The Strategy

There are ten ways for the lecturer to pick three prompts: 123, 124, 125, 134, 135, 145, 234, 235, 245, and 345.

Looking at all the cases, if I always write the essays I’m most prepared for, there’s a 60% chance I’ll have to do prompt 1, a 60% chance I’ll have to do prompt 2, a 50% chance I’ll have to do prompt 3, and a 30% chance I’ll have to do prompt 4. (I can always avoid the dreaded prompt 5.) As a sanity check, these add up to 200%, since I have to write two essays.

Therefore, letting \(x_i\) be the amount I prepare for prompt \(i\), my expected preparedness for the essays I write is given by

\[\mathbb{E}[\textsf{preparedness}] = \frac1{20}\left(6x_1 + 6x_2 + 5x_3 + 3x_4\right)\]

This is a linear optimization problem! My constraints are all linear equations, as is what I want to minimize: \(x_1 + \dots + x_5\), the total amount of preparing.

So to find my optimal studying strategy, I plugged it into an off-the-shelf LP solver. I used GNU GLPK with the MathProg modeling language, since I found a convenient web interface for it. Here’s the program:

var x{1..5} >= 0, <= 1;

# Minimize the total amount of preparing
minimize total: sum{i in 1..5} x[i];

# Decreasing preparedness
subject to c1{i in 1..4}: x[i] >= x[i+1];

# Expected preparedness of at least 95%
subject to c2: 0.95 <= 0.3*x[1] + 0.3*x[2] + 0.25*x[3] + 0.15*x[4];

end;

Finally, here’s the optimal study plan:

And so I studied the first three prompts fully, only prepared ⅔ of the way for the fourth, and did not prepare at all for the final prompt.

Epilogue

The lecturer chose prompts 2, 3, and 5. I was as prepared as I could be, I wrote my essays with confidence (and lots of stress), and I passed the class.