Discrete mathematics in industry

摘要

There are so many discrete mathematical problems arising from all industrial sectors that it is difficult to know how to begin to classify them. Naturally they often involve some continuous aspect as well, arising from time or space or the physical variables in the real-world problem. For instance, consider the error-detecting and error-correcting codes that are used in all the digital communications we make each day. The construction of these codes is a purely discrete problem, yet the reason why such codes are needed arises from an underlying continuous problem of signal transmission over a radio link or optical fibre, and the probability distribution of errors in such transmissions. To give another example, a timetabling problem or a resource allocation problem will generally take a purely discrete form, yet it has arisen from real-world continuous constraints such as how long it takes a data packet to get from A to B, or a train, or a class of schoolchildren. So, when I describe some discrete industrial mathematics problems here, some of them also involve continuous variables: but the characteristic feature in each case is that the mathematically challenging part of the problem is essentially discrete,. The first two problems are industrial applications of graph theory and illustrate, incidentally, that not all industrial graph theory problems are the travelling salesman problem,. The third will be from combinatorial auctions of the kind used by Ofcom for spectrum licences, and the fourth is a regulatory problem to do with aircraft noise.