In January and February 2013, I participated in the Mathematical Contest in Modeling, run by COMAP. The contest was to last 4 days from 5:00 p.m. (Pacific Time) on Thursday January 31, 2013, to 5:00 p.m. on Monday February 4. We would have to choose one of two real-world problems and do our best to solve it with a mathematical model.
Here is our paper, exactly as it was submitted for the contest. Below is a description of our experience.
Preparations
I prepared extensively for the contest. The dozen UW participants met every Friday for several months to discuss past contest problems. Over Christmas break, Siyu Jiang, Yuxuan (Shawn) Zhang, and I formed a team. Shawn was a sophomore like me, who was also in the 134- and 334-series honors calculus classes. He came from China and studied computer science. Siyu was from China as well, a junior in electrical engineering.
We decided to study different applicable areas of mathematics: Shawn took probability, I read up on calculus of variations and PDEs and learned LaTeX and tikz, and Siyu studied optimization and learned how to use Matlab. We also read papers from past contests and thought about strategy.
At the end of break, we performed a mock contest for slightly less than four days. In the beginning, we felt we made some progress, but as the end approached, we wasted time tinkering and did not write enough. For example, I spent several hours learning more about the tikz package and making pretty diagrams (although this was not a waste of time ultimately because that knowledge would pay off during the actual contest).
A couple weeks after break, we had another mock-up, but only of the first day. After that, our preparation focused on clearing time for the contest. Those four days had to be free of classes and homework, which meant working ahead on homework and getting permission to skip class. The week of the contest, Professor Morrow, who was overseeing the UW participants, gave us keys to the various math buildings and accounts to access the math department’s server.
Although I normally commuted to school, I decided to stay at Shawn’s house during the contest. Thursday morning, my dad dropped me off there with clothes and food supplies to last through Monday. I went to class and relaxed for most of that day, but I had to take a Latin midterm which had been scheduled for Monday.
Thursday: Choosing a Problem and Brainstorming
At 4:30, the UW participants met and chose rooms. Siyu was not there because he had to finish a lab. Although we had decided to work in the CS building for most of the contest, on Thursday we took possession of a classroom in the basement of Communications, near the Math Study Center, politely ousting the previous occupants.
At ten to five, the problems appeared online (although I had to refresh the page several times!). Shawn and I eagerly read the problem statements, and thought about how we would approach the problems and which one we should choose. Siyu arrived just about at five.
In summary, the two problems were:
- Circular brownie pans cook more evenly, but rectangular pans pack better in a rectangular oven. Model the heat distribution in a pan. Determine the best shape of pan for a given oven to optimize a given combination of efficient packing and even heat distribution.
- Come up with an effective water strategy to meet the needs of 2025 for one the following countries: the United States, China, Russia, Egypt, or Saudi Arabia. Address storage and movement, desalinization, and conservation.
Of the two problems, the first seemed more tractable. The second appeared far more open-ended, and we did not know anything about water strategiss, so that problem was not immediately interesting. We would have had to do research before we even knew what the question was.
Of course, we knew full well that the apparent mathematical precision and tractability of the first problem was deceptive. MCM problems are never well-posed, even if they sound mathematical when you first read them. Choosing the more precise problem is a tradeoff because in the more open-ended problems, teams have more leeway in how to approach the problem.
Notwithstanding, we quickly opted for the first problem.
Instantly, we began spouting off ideas. We thought of modeling the heat distribution with the heat equation. We researched the heat distribution in ovens. We thought of pan shapes to consider. We brainstormed ways to simulate packing pans into an oven. Our master strategy was to model the two parts separately–heat distribution and packing efficiency. Combining these results would solve the forward problem: Given a pan, how is the heat distributed, and how efficiently can we pack it? After that, we would attack the backwards problem: which pan is best?
From the beginning, I gravitated toward the heat problem, while Shawn focused on the packing. The division seemed natural, but we would have benefited from more interaction during Thursday and Friday. Perhaps that would have prevented the disasters that were to follow.
Friday: Dead Ends
We went to bed at about midnight on Thursday. On Friday, we worked in the CS lab. Siyu and I researched how bread bakes. (A complex interaction between heat flows and moisture flows leads to formation of an evaporation front which divides crust and crumb. That is because bread does not have a uniform density and heat transfers by convection as well as conduction.) However, we decided brownies are more uniform in density than bread, so using the heat equation would still be a good approximation.
However, Mathematica and Matlab could not solve the heat equation the way we wanted. We wanted a solution for any kind of pan shape; they would only do rectangles. We wanted the boundary condition to simulate thermal transfer from the outside; they would not accept boundary conditions involving the derivative of temperature with respect to time. However, someone had invented a Mathematica package that would do what we wanted! It was not available online. I emailed Kevin Loranger, the math computing help guy. He sent an email to the man who made the package asking him to send it to us. "We will see," Kevin wrote.
Interspersed with our heat modeling, Siyu and I attempted to write parts of the paper and come up with good shapes to test our model on. We looked at the shapes that the heat distribution formed in a square and tried to come up with a shape that would describe that. I knew we were wasting time not knowing what to do. I hoped the man would send us the PDE package and save us.<
Meanwhile, Shawn tried to invent a simulated annealing program that would pack pans into an oven. However, we had not formulated the problem well enough to use that algorithm, so we got no good results. I suggested that Shawn try something else. I should have learned more precisely what he was doing, and we should have discussed it all together, but I was too distracted with the heat distribution, and we did not have any better ideas off the top of our heads to model the packing.
I realized we were in desperate trouble. We had read an article about contest strategy by Kline, and by his schedule we should have been much farther by the end of Friday. However, at the end of the day, we had been sent the PDE package! A ray of hope and excitement shot through me. We continued to work late into the night, but I just wanted to go to bed. I familiarized myself with the syntax of the PDE program.
Shawn also found an article describing how to circumscribe any polygon with a hexagon which could tessellate the plane. The hexagon would be circumscribed with minimal added area. The resulting tessellation would be nearly optimal packing for the original polygon.
I went to bed hopeful that night, but we were not out of the water yet.
Saturday: Something Resembling a Solution
On Saturday, we decided that I should be the one who worked with the PDE program, since I was more familiar with Mathematica. Shawn implemented the algorithm he had found, which took considerable work, and the program still had bugs at the end of the day. Siyu worked on the paper, which was quite difficult since we had no results yet.
The PDE package worked nicely on all the examples that came with it. But it was quite delicate. There was no thorough instruction manual. There were compatibility issues because it was written an on earlier version of Mathematica, but it seemed to work as long as we did not let Mathematica find out about those issues. I tried to make it solve the heat equation over a hexagon, but after I finally managed to phrase the problem correctly, the software did not ever finish its computations. I don't know whether there was a bug or it just took a long time. Even when we stuck to the sort of boundary conditions Mathematica's built-in NDSolve liked, the program took forever.
On Saturday afternoon, I was desperate. I tried a change of variables to change a rhombus into a square, so that we could use Mathematica's built-in solver, but it still did not like the boundary conditions. Although I had read how to solve PDEs numerically, I didn't think we had enough time left. I called a meeting of the three of us, and began brainstorming with erratic creativity.
The program was not working, I said. But we needed data fast. It was time for an experiment. Since there was no time to cook brownies, we could do another kind of experiment. As a little research quickly confirmed, the heat equation also models diffusion. So we could get our results by dipping paper in water and seeing how the water seeps in from the edges. Siyu and I went into the lounge and experimented with various kinds of paper in water. I was on the verge of going out shopping for supplies when I had a more useful insight.
Instead of actually experimenting with diffusion, we could simulate it with a computer program. Quickly I typed up a Java code that would do a random-walk-like simulation, moving “true” values randomly across a boolean array. The trues were like particles and the falses were empty space. After a little more work, we could display the results as a picture with black and white pixels and we improved the accuracy of the simulation. We started with a white shape on a black background, then we let the black area diffuse into the white zone and measured how much of the original white space turned black after a certain number of time steps.
The results were just as satisfying as the basic insight. We could view the program as simulating the diffusion of a gas into an empty space, or water into a sponge, or more importantly, heat into a brownie pan because the same equations governed all three. We had discovered a useful heuristic for the contest: if you can’t model what you want, then model something else!
Of course, I did not have the mathematical maturity to make any rigorous estimates about the assuracy of my simulation.
Soon I had applied the program to various kinds of shapes. We had thought of a squircle, which "averaged" a circle and square in polar coordinates. We also made squares with rounded corners, and we considered regular polygons. We normalized the area of all of them to one. I coded up simulations for each shape and gathered data.
We stayed up until about 4:00 a.m. By that time, we had written up an explanation of our heat distribution model and the polygon-fitting algorithm we had found. Shawn's program still had some bugs, but it was nearly ready and had worked well on some shapes.
We were going to survive. Our model would be imperfect because of our earlier wasted time; specifically, we had only modeled the heat equation in two dimensions, and we only considered packing efficiency on the infinite plane, not a finite oven with edges. The second problem in particular was a serious strike against us, since the problem statement had explicitly given the oven's length and width as parameters, but it would not be fatal if we wrote well and honestly acknowledged our limitations. We might not win, but we would finish well.
Sunday and Monday: The Endgame
On Sunday, Shawn discovered that the bug in his program would not occur if he moved the shape to a different location. That was a good enough answer for us. The rest of the day was devoted to writing and gathering data. Using Mathematica, we fit polynomial models to the data for each kind of shape. Using the tikz package, I made nice graphs of our results. According to our model, hexagons performed quite well, but our ingenious "squircle" was quite useless; the circle or the square was always better than the squircle, depeding on whether you put a higher priority on even heat distribution or efficient packing.
<We went to bed at 6:00a.m. We still had not finished the packing data for squares with rounded corners. We did not have a summary, and other sections of our paper were incomplete. All that had to be done Monday. The first thing was the data; as it turned out the squares with rounded corners were almost always outperformed by either the circle or the hexagon. So much for that idea.
We wrote and drew up diagrams continuously from 10:00 to 4:00. I had to do the diagrams, and I edited and compiled all the sections. Shawn and Siyu were always either writing or reading and making suggestions. Around 4:00, we finished the last section. We did not have time for better writing or more mature reflection, but at least we had finished. We figured out how to turn the paper in, and we emailed the right things to the right people.
We printed the paper and brought it to Professor Morrow and signed the necessary forms and returned the keys. I was excited to have finished and already thinking about what to do next time, but I was also very tired. I went and cleaned up my stuff at Shawn's, and my dad took me home.
The next day, I had some new insights into the problem. I realized our approach to the backwards problem of just testing specific shapes had been rather ad-hoc. A better approach would have generated a shape without any preconceived notion of what to try. We could have used simulated annealing to create a shape in the following way. We would start with a pixelated shape with a certain number of pixels. We would measure the amount of burning and the packing efficiency of the shape–that would be the energy function for the annealing algorithm. We would move some white pixels around the change the shape slightly–that would be the neighboring state for annealing. Then we would search for the best shape using simulated annealing.
Of course, I wish we could have done that during the contest, but I realize we had time limitations, and I am still happy just to have finished.