Let a solver do the searching
A joiner can make tables and chairs, but the wood and the hours run out. Which mix earns the most? You could try plans for an afternoon. Or you could write the limits down and let a solver find the best plan, or prove there is none.
By the end of this lesson
Note
I can run an optimisation model and read its status, its plan and its shadow prices.
Key words
- Model: the limits and the goal, written down.
- Solver: a program that finds the best answer to a model.
- Slack: how much of a limit is left over.
- Shadow price: what one more unit of a limit is worth.
- Integer: a whole number, with no fractions.
Starter: what you already know
Note
Answer in your head. 1. What is a variable? 2. What does it mean to maximise something? 3. Can you make 2.5 chairs? You need the third answer in a moment.
Before you start
Note
Press Start the lab on the bar at the top of this lesson. This lab is a whole Ubuntu machine of your own, so it takes a little longer to come up than a container, and it installs its solvers the first time. Each Run button types its command into the machine's terminal, one after another in the same session. If one says the machine is still starting, wait a few seconds and press it again. To watch them, or to type your own, press Open terminal on the bar.
A model is a goal and some limits
Your files are in the folder optimisation. The first command moves into it. lp.py is a model written with PuLP: tables and chairs, a profit to maximise, and limits on wood, hours and storage. opt runs a Python file with the solvers ready. The first line says Optimal, which means the solver finished and the answer can be trusted. The plan is 20 tables and 60 chairs, a profit of 2800.
cd optimisationShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
opt lp.pyShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Check
Tip
Which limit has slack, and what is its shadow price? Answer: storage has 60 left over, so one more unit of storage is worth nothing. Wood and hours are used up, and their shadow prices are 20 and 10: one more plank adds 20 to the profit.
A common mistake
Warning
Many people think that any limit that is used up is holding the profit back by the same amount. It is not so. Read the shadow price: a used-up limit with a price of 20 is worth buying more of, and a limit with slack is worth nothing more, even if it is big.
Whole numbers need a different solver
integer.py picks projects, and a project is done whole or not at all. It solves the model twice. With fractions allowed the value is 45.17 and the plan does 0.67 of a project. Rounding that plan to whole projects costs 22 against a budget of 19, so it is not a plan. Asking for whole projects only gives a value of 42, with three projects: bridge, garden and theatre.
opt integer.pyShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Check
Tip
Why is the fractional answer worth more than the whole-number one? Answer: it has fewer rules. Allowing parts of a project can only help, so it is an upper limit on the whole-number answer.
A constraint solver makes a rota
shifts.py uses OR-Tools CP-SAT. Three nurses share three shifts a day for four days, and each has wishes not to work some shifts. Nobody works a night and then the next morning. The solver says OPTIMAL and that one wish has to be broken, because two nurses cannot both avoid the same shifts on the first day. A rota is printed for every day.
opt shifts.pyShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Exit check
Tip
Answer without looking back. 1. What does a solver do? 2. What does a status of Optimal tell you? 3. What is a shadow price? 4. Why can you not round a fractional plan? Answers: finds the best answer to a model; the solver finished and the answer is the best; what one more unit of a limit is worth; the rounded plan can break a limit. Now open README.md in your home folder with cat ~/README.md: you write two models.
For teachers
Tip
This lesson is a small example of a lesson worked in a lab: the steps and the Run buttons are the lesson, and the lab is each student's own copy. This lesson is worked in a VM lab: each student has an Ubuntu machine of their own with PuLP, CBC and OR-Tools installed, and a Run types into its terminal and shows what it printed. Key learning points: 1. A model is a goal and some limits, and a solver finds the best answer. 2. Read the status before the numbers. 3. Slack and shadow price say which limits matter. 4. Whole numbers need an integer solver, and rounding can break a limit. Common mistake: blaming any used-up limit without reading its price. Equipment: the lab and a browser. Tip: before the second Run, ask the class to round 0.67 of a project themselves. The lab itself has a check that marks two models on hidden instances. The operations research module solves its problems with SciPy; this lab is where a class meets PuLP and OR-Tools. Copy it into your own module and change it, or build one from scratch with the Lab menu in the lesson builder.