After recently moving into a new place, I was surprised to find that none of the windows had flyscreens on them. So I set myself the task of making them. After watching tutorials on YouTube (as every aspiring but unqualified DIY-er does), I learnt that to make the rectangular “frame” part of a flyscreen you buy framing in 2.5m lengths for the sides and cut it to match the size of your window. Seemed easy enough and not at all related to mathematics, right?!?
 Framing |  A finished flyscreen |
Wrong! Before I could even start construction, I needed to decide how many lengths of framing I needed. I didn’t want to buy more length than necessary (that would be wasteful and we wouldn’t want that!), so having measured my window dimensions, I did what every normal person would do: I set up an optimisation problem to finding the minimum number of lengths needed to complete the job.
This particular problem is known as the cutting stock problem. Here’s Wikipedia description of the problem:
In operations research, the cutting-stock problem is the problem of cutting standard-sized pieces of stock material, such as paper rolls or sheet metal, into pieces of specified sizes while minimizing material wasted.
https://en.wikipedia.org/wiki/Cutting_stock_problem
In my case, the “stock material” is the 2.5m lengths of framing, the specified sizes are the dimensions of all the windows in my house, and “minimising material wasted” means to minimisation the number framing lengths needed.
Mathematically, the cutting stock problem is NP-hard. It’s usually formulated an integer program for which it can be solved in practice. My flyscreen instances were of relatively small problem size, so this was no issue and they solved in seconds using an out of the box solver.
Dynamical Mathematical Gazette 