New Scientist vol 150 issue 2035 - 22 June 96, page 38 Have we got problems for you A change is as good as a rest for an Oxford mathematician who hardly ever gets to see the practical results of his hard labour. So Jon Chapman leapt at the chance to join a team of other academic escapees for a delicious week of grappling with the kind of problem that drives industry mad. He kept a diary of what happened as the group hung out in pubs, restaurants and lecture halls in search of solutions Sunday 18 March: The Royal Oak pub. This is where we're all supposed to meet, and by early evening people are beginning to trickle in. In all, there will be more than 80 mathematicians, and 14 representatives from eight companies, keen to pick their brains. It's a neat idea -- the companies bring along things that they're having trouble with, and the academics spend the week working on the problems for free. There are advantages for both sides. For instance, even though I am an applied mathematician working on real-world problems, my research tends to be long-term, and I'm unlikely to see the practical results. Occasionally, some of the problems can even lead to further research projects and publications -- I'm still collaborating on work that originated in a similar workshop four years ago. But for the most part, this week is the only time I'll look at these problems. It is a welcome chance to forget my own research and work on something completely different that could have immediate practical benefits. Monday 19 March: Main lecture hall. One by one, the industrialists take the stand to present their problems. This year, there are eight problems to choose from, ranging from modelling the effects of council housing policy on homeless populations for Shelter to what's wrong with mobile phones. Some mathematicians like to stay with the same problem all week, to really get their teeth into it, while others like me tend to wander around, helping out with a problem for a few hours, then moving on to the next. There are plenty of questions in these opening sessions as the academics try to strip away the sometimes baffling company jargon and get to the heart of the problems. I like the look of two problems in particular. The first involves tiny but annoying pinholes that are messing up a screen-printing process. Apparently, the printing involves forcing paint through a fine wire mesh, some of whose holes are masked to make the desired pattern. The process is supposed to leave a nice uniform layer of paint on the material below, but pinholes sometimes form where the wires in the mesh cross. The company is looking for ways to fix the problem by changing the properties of the paint -- easier than changing the whole printing process. The second problem I plan to work on involves cutting jumbo rolls of paper to the individual widths demanded by different customers. For each new order, the blades on the cutting machine are arranged into a set of patterns, optimised by a computer program to minimise the amount of waste paper at the edge of each roll. Since each new pattern means that the blades on the cutting machine must be repositioned -- which is time-consuming -- the question is whether different patterns can be combined. The company, Graycon, has already worked out general ways to turn two patterns into one, and three into two. Could we find efficient four to three and five to four reductions? Could we find a more general way of taking any number of patterns and reducing them by one -- an n to n-1 reduction? Would this catch all possible reductions? To cap it all, we have to find a way to compute the answers to these questions by running a program for less than a minute -- roughly the time the factory operator is willing to wait -- on a simple Pentium processor. We retire to the safety of the bar to plan our attack. Tuesday 20 March: Work on the problems begins in earnest. Each problem is allocated its own room and participants wander in and out as they wish. I decide to start on the pinholing. The first task is physics, rather than maths. We need to work out how the pinholes form before we can build a mathematical model for the process and check the model's predictions against any experimental results the company can give us. Alistair Fitt from the University of Southampton stands at the board, and the rest of us sit on tables and chairs, offering suggestions. This brainstorming process is what I love most about study groups. Nobody teaches you this at university, but you can learn a lot by simply thinking out loud with a bunch of other mathematicians. Students tend to be more cautious about putting forward an idea in case everyone else thinks it's ridiculous. But it's soon clear that everybody has their fair share of foolish ideas, and the newcomers start to relax. We need to work out not only why the pinholes form, but also what holds them open long enough for the paint to dry. Initially, when the mesh is removed, the paint film will be uneven, and forces such as gravity and surface tension will make it spread out into a uniform film. Of these forces, we reckon that surface tension will be most important in trying to close up pinholes. The next step is to work out what could resist the action of the surface tension. The prime candidate is the viscous resistance -- the force that makes it difficult to stir treacle. Balancing these two forces, we work out that typical pinholes should close in about a second. Unfortunately, paint takes much longer than this to dry and pinholes stay open in wet paint for several minutes. As the way forward becomes muddier, the group splinters into smaller groups, each discussing aspects of the problem and taking turns to quiz the industrialists. As answers go in and out of focus, groups merge and splinter again. We discover that the paint contains small particles about 5 micrometres in diameter. This is why it will behave like a solid when under a small amount of stress, and only begin to flow when the stress reaches a critical value. It's a phenomenon known as a yield stress. This gives us our first stab at working out why the defects in the paint surface last so long: perhaps yield stress is holding the pinholes open while the paint dries. Unfortunately, holding open the tiny pinholes that are seen in real life would take ten times the experimentally measured yield stress. As the group begins to put together a model for the printing process to see whether the way pinholes form sheds some light on their unusual longevity, I decide to check out what is happening elsewhere. In the paper cutting room, two groups are beavering away. At the back of the room one group is using high-level mathematics to work on the problem. I'm not familiar with this branch of mathematics, so I join the other group, which has managed to formulate the problem, but unfortunately its statement turns out to be too cumbersome to be useful. On the plus side, they have solved one question already: by trial and error, the group has come up with an example of three patterns which could be reduced to one, but not to two. In other words, a general nto n-1 solution would not pick up all possible reductions. As the day goes on, we get a feel for the problem by working through some simple examples applying Graycon's two-to-one and three-to-two reductions. Each pattern is a collection of customer widths into which the jumbo roll will be divided. We decide that a general approach will have to work one step at a time by switching widths between patterns. For example, say the jumbo roll is 300 centimetres long, and we have two patterns, one with widths of 100 cm, 100 cm and 80 cm and one with 90 cm, 90 cm and 110 cm. In this case, we can switch a width of 100 cm in the first pattern for one of 90 cm in the second pattern to get two new patterns with widths of 100 cm, 90 cm and 80 cm, and 100 cm, 90 cm and 110 cm. These patterns are more similar than the original two, since they contain two out of three widths in common. If we can switch the remaining width of 80 cm in the first case with one of 110 cm in another pattern then we will have two identical patterns, and so will have reduced the total number of patterns by one. We work through some three-to-two reductions by switching one roll at a time and try to identify what made a good switch -- one that increases the similarity between patterns. By the end of the day, we have developed some simple rules which we hope will form the basis of an algorithm. Discussions continue over dinner and well into the night in the bar. Wednesday 21 March: Yesterday evening, the paper cutting seemed in good shape, so I begin back in the pinholing room. Sadly, there is still no sign of a mechanism to explain why pinholes stay open. Several ideas are suggested, checked out and chucked out because they end up producing a totally unrealistic pinhole shape. Meanwhile, back in paper cutting, the group has developed an algorithm. To function as a computer program, the rules have to be exact and comprehensive enough to cope with any situation without the need for humans to tinker with it. After working through more examples by hand and ironing out some of the wrinkles, Mark Shephard, a graduate student from Oxford, volunteers to turn it into computer code. The high-level maths group reports back. They have been able to show that the simplest problem involving only three cuts per jumbo roll belongs to a class of mathematical problems known as NP hard ("Hard maths, no problem", New Scientist, 28 October, 1995 p 40). For these problems, the time it takes to solve them increases exponentially with the size of the problem. In other words, finding the absolute minimum number of patterns would be very difficult and time consuming. The rest of us are not too disappointed -- this means we have not missed something simple, and our back of the envelope algorithm is probably the best we can hope for in a week. Thursday 22 March: Back in the pinholing room, we find a possible clue: there are more pinholes at higher printing pressures, and in paints containing larger particles. John Hinch, a reader in applied maths at Cambridge, promptly comes up with a theory to account for the longevity of pinholes. The yield stress is caused by the solid particles becoming locked against each other, and depends on their concentration. If there were more particles concentrated near the pinholes, this could boost the yield stress enough to balance the surface tension. But what could increase the particle concentration? Sam Howison, maths lecturer at Oxford, has an idea. When the mesh is pushed down, the particles are squeezed out and shoot sideways. When the mesh is lifted, they should all return, but if it is lifted quickly, an air bubble may form between the mesh and the paint. The upshot could be a pinhole, surrounded by a higher concentration of paint particles. It has taken until Thursday afternoon, but we finally have a plausible mechanism. Back in paper cutting, the algorithm has been turned into computer code. We test it on a few examples and it turns six patterns into three and ten into seven. This last example takes 2 seconds on an old 286 processor -- well within our allowed computing budget. A leader is chosen for each problem to collect all the ideas and work out how to present them to the whole gathering the next day. Being a leader means spending the evening writing presentations for the morning. For the rest of us, the week's work is over, and we can relax in the bar. Friday 23 March: Back in the main lecture theatre, the academics say their piece. I am always amazed at the process by which the groups' tangled ideas turn into a coherent presentation by Friday morning. Most problems have gone well. The industrialists seem happy. The Graycon people are delighted with the initial performance of the algorithm, but will need to test it thoroughly. And experiments will be needed to check whether we are right about the mechanism for pinhole formation. If it bears up to closer examination, we can think about devising a cure. Perhaps next year.