Python for Home-Ec

04:00 PM - 04:25 PM on July 17, 2016, Room CR6

Adam Forsyth

Audience level:

novice

Description

Have you ever tried to make something with scrap wood, and wondered how to use it optimally? Do have a bunch of pickles and jams you made, and you want to eat them in an order that maximizes variety? These are real problems a co-worker of mine had, and we used Python to solve them. I'll show the data we started with, the solutions we came up with, and a bit of the computer science behind them.

Abstract

My co-worker Jonathan is a programmer, farmer, and do-it-yourselfer. Last fall, he had two problems he was trying to solve. The first was how to make a countertop with some scrap wood he had left over. The second was how to portion out the variety of pickles, jams, and sauces from his farm week-by-week over the winter to maximize variety. He recognized these were problems a computer could help him solve, and even wrote a solution for binning the preserves, but it didn't work well. Together, we wrote solutions in Python that gave him much better results that without computer help.

First, the "scrap wood" problem. Say you've got a bunch of pieces of wood. You need a bunch of pieces of various lengths, shorter than the pieces you have to work with. Since the lengths you need don't add up exactly to the pieces you have, if you don't do it right, you're going to end up with a bunch of short pieces cut off and have to glue them together to make the last few pieces.

In the knapsack problem, you have a bunch of items of various weights and values, and you're trying to fit as much value into a knapsack as possible without exceeding its weight limit. If you now imagine many knapsacks with different limits (the pieces of wood we have to work with) and that the items weights each equal their values (since the lengths we need to cut don't have a separate cost from their length), you have our problem.

The simplest approximation for solving the multiple knapsack problem is greedy reduction. Starting with the longest length we need, take it from the shortest piece that will accommodate it. This method guarantees you use at least 50% of the length if possible, but isn't near optimal. For our problem, it almost works -- and by reordering the pieces of wood slightly we can make it work. Sometimes, an approximate solution is good enough.

So now let's say you have a bunch of jars of food -- different numbers of each type. You are going to be eating them all winter, so you want to space out jars of the same type as far apart as possible, to maximize the variety you're eating on a weekly basis. You're going to eat the same number each week so that you can spread them out evenly until you start getting fresh produce in the summer. Jonathan had written code to solve this problem that worked well enough for types of food with a lot of jars, but not so well for ones with lower numbers of jars.

So we want the jars of the same type to be as far apart as possible. If we imagine time as a line, and the jars as points on it, those points are pushing against each other, trying to get as far apart as possible on the line --they're like magnets repelling each other, and we want to reduce how hard they push against each other by getting them evenly spaced as far apart as possible. If this sounds familiar to anyone, that's because a well known approximation technique, simulated annealing, is simulating exactly this -- particles trying to maximize their distance apart so as to minimize the energy of the system. Simulated annealing is used to find approximate solutions to problems where trying to find the best solution may result in it getting worse before it gets better.

In this case though, we didn't use simulated annealing at all. We only needed a solution that was "good enough", and we thought of a simple method to try to achieve that. Starting with the type of food we have the most of, insert them into a list equally spaced throughout, then repeat with less and less common types of food. This results in an even spacing regardless of the specific numbers you have of each type of food.

Each of these problems benefited from a computer-assisted solution, despite involving no big data and only a small amount of calculation. A little knowledge of programming can take you a long way when the job is optimization.