Knapsack Debugging and the Value of Open Source

Part of my research responsibilities is building and maintaining a fire simulation program for an area of Eastern Oregon. The idea is to simulate fire and growth under different suppression and fire treatment policies so we can generate an optimal policy. Everything was proceeding smoothly until the closed-source fire spread model refused to simulate any landscape past 40 years. To make things worse, any of 1 million pixels could cause the error, and each pixel could reach its error state via any combination of annual growth and fire transitions. The number of combinations made checking the file manually impossible (the sun would run out of fuel). Thankfully, a few tests and careful thought reduced the problem space.

1. If I ran the program without updating pixels that burn, it still failed at 40 years every time. Conclusion: The problem is present in the growth of the landscape.
2. Any combination of growth transitions with timings summing to 40 could be the problem. For example, ten four-year transitions or one 40 year transition could be the problem. This is pretty close to the knapsack problem, which is hard in the technical sense. However, if I ran the program with every transition taking one year, it failed in two years. Now I know that the problem happens after two transitions, and these two transitions must sum to 40.
3. Now that I had groups of problem transitions (those summing to 40), I could use efficient search methods to find the problem transitions.

With the problem transitions, I finally had the “bad” data and could find the source of the problem. It turned out to be an error in the file’s metadata. A bit anticlimactic, but I still danced with joy.

Although I am happy to have found the bug, this experience highlights the value of open source software. If the fire model were open source, I could trace the error back to the problem. Instead, I had to MacGyver it.

* This video was the quickest way to explain the MacGyver Reference. It should not be construed as an endorsement of MasterCard by the author or seanbmcgregor.com.