Pictures of the Future Spring 2006
Simulation – Mathematics
Optimization by the Numbers
Most managers dream about finding ways to boost productivity while cutting costs. But very few of them know that many decision processes and automation tasks can be optimized using mathematics. Siemens has established a Technical Center at Corporate Technology for just that purpose.
Dr. Johannes Nierwetberg illustrates how the best possible path to a distant target (thick yellow line) derives from the use of algorithms that identify the best possible local paths (narrow yellow lines)
The rules are clear. When the traffic light is red, you stop. When it’s green, you go. But on yellow? Impatient drivers invent different shades of yellow—like amber or saffron—so they can feel better about running the light. Their action can have very different consequences. They may get there faster, pay a fine, or wind up in the hospital.
For mathematicians, this traffic light situation is a classic optimization problem. The savings in time must be weighed against the cost of the ticket. Companies also constantly have to make decisions. But those decisions, if wrong, can cost a lot more than a traffic ticket—and can amount to the corporate equivalent of going to the hospital. What’s more, in the case of business solutions many interacting variables, which are often difficult to sort out, have to be considered. "In complex, networked and dynamic situations our brains make mistakes," warns Prof. Dietrich Dörner, a cognition expert at the University of Bamberg, Germany.
Fortunately, electronic systems are available to make things easier. Guided by mathematical algorithms, computers can help optimize many processes. One of the pioneers in this discipline is Prof. Ulrich Lauther at Siemens Corporate Technology (CT) in Munich. A graduate electrical engineer who has taught at Berkeley and the University of Stuttgart, Lauther was given a tough assignment at Siemens in 1992: Optimize the telephone network of Poona, a city in India with a population of three million. The backbone of this network was to consist of fiberglass, although the last 300 meters to user locations had to be copper cables. Multiplexers in between would have to handle up to 60 lines each. An important goal was to minimize the total cost of the lines, multiplexers, trenching work, etc. Lauther’s algorithms enabled him to solve the task brilliantly. They produced a solution that cut costs by 15 % compared to a manually developed plan. Lauther’s result was also technically correct—unlike the conventional paper plan, in which one multiplexer was erroneously connected to 70 households.
Competitive Advantages. Word got out about this achievement. At the Discrete Optimization Department at Siemens CT, a staff of 20—mostly mathematicians—is available to tackle anything that can be optimized mathematically. "What’s so fantastic about this kind of optimization is that, at the customer level, it is seen as a competitive advantage," notes Dr. Johannes Nierwetberg, who heads the Department. In most cases, the percentage of cost and time savings is in the double digit range. Nierwetberg’s department has developed an entire tool kit of algorithms for this work.
One such tool, for instance, optimized the queuing of components for insertion into a printed circuit board, thus increasing throughput by 13 %. But even though Nierwetberg can calculate the resulting benefits down to the last euro and cent, many managers remain skeptical. Making them understand that many of their problems can be solved mathematically isn’t easy. As a case in point, Siemens was engaged by a customer in the steel industry to take a close look at rolling crude-steel ingots. Since the rotation of the rolls, the transport times, the cooling of the ingots, the processing time and the operator actions aren’t exactly predictable, a control program designed to increase the throughput of the mill must include all these uncertainties in its calculations. "Like a chess player, our software recalculates the best strategy every few seconds," says Nierwetberg. Usually there’s enough time for a "best move." If not, the software executes a "safe move" and controls the process to ensure that no problems arise. Today this software program is running at several steel mills, where it has substantially increased throughputs.
Siemens researcher Prof. Albert Gilg demonstrates how unstable a state can be at its mathematical optimum. For example, you can slide off a mountain pinnacle in any direction
The same mathematical principles can also be used to achieve faster data transmission rates via landlines or wireless links. In automated production systems, for instance, large data volumes are constantly interchanged between sensors, actuators and computers. To coordinate these elements perfectly, the right data must be available at the right place and at the right time. In a new approach, special bus lines are being replaced by standard Ethernet cables. However, using the conventional Ethernet protocol could cause delays when too many data packets have to be accommodated by the bus. This, in turn, would interfere with the synchronization of the drives in a production line. As a result, the routing and timing of the data packets must be planned in advance.
Everyone is familiar with such scheduling problems. Builders, for example, know all about having the roofers show up before all the walls are in place.
Efficient Data Traffic Planning. One application that had to overcome such constraints was Profinet RT, an automation solution from Siemens’ Automation and Drives Group. For the Profinet IRT version, Ulrich Lauther developed a new software tool for planning real-time messages in a network composed of Ethernet cables and time-synchronized nodes. The tool is aptly named Isochronous Real-Time (IRT). It computes how and when data must be sent through the network in order to ensure that the clock pulse is maintained and the required time per cycle is minimized. The time intervals freed up by such efficient planning can be used for conventional TCP/IP traffic, such as browser or software downloads. The key principle is this: Time-critical data get priority. They are consistently fed into the dataflow at the same point in the cycle and reach their destination reliably and nearly in real-time. Less important data share the remaining bandwidth.
By way of comparison, in Profinet IRT an instruction cycle takes less than 1 ms. In its precursor, Profinet RT, it took ten, and in standard Internet connections it takes as long as 100 ms. Optimization is now accomplished in the blink of an eye. A network of 124 nodes (e.g. drives), 465 messages and 576 recipients requires less than one second to compute when, and over what route, which message must be sent to what recipient.
Profinet IRT is already being used successfully at a pilot customer: MAN Roland, a manufacturer of printing machines near Frankfurt, Germany. The cylinders of a rotary press for illustration printing revolve so fast that they can print 90,000 pages per hour. Yet they are so precise that they can superimpose color dots with a precision of five micrometers. Signals throughout the system vary from the specified timeline by less than half a microsecond, which increases the printing speed and precision while eliminating paper tears. All future automation solutions from Siemens will be based on Profinet IRT, which has been on the market since the spring of 2006. The product will be sold with an engineering tool based on Lauther’s optimization algorithm.
Acceleration by a Factor of 200. Wireless data transmission is even more critical, because it’s more cost-intensive. In a satellite-based road toll system like the one in Germany, new software must be downloaded every so often to onboard units (OBUs) on vehicles—for instance, when new toll roads are added. In the past, trucks had to visit a shop to have this done. In the future, new software will be downloaded automatically via mobile communications. Nearly half a million OBUs are now on the road in Germany. And there will be even more in other countries that are planning to charge passenger car tolls. The cost of exchanging all of that software—around 2.5 Mbyte apiece—would be enormous.
Lauther has developed a method that compresses such software updates by a factor of 200, to a minuscule 12 kilobytes, allowing the data transmission to be accomplished in a matter of seconds. How did he do it? Lauther’s algorithm limits the transmission to the difference between two files. And his algorithm doesn’t seek out just any difference, such as only those bits of code that have changed. Instead, it consistently selects the smallest possible difference between the old and new program codes—and that can be proven mathematically.
Lauther has also completed a similar project for BenQ Corporation, the new owner of the Siemens mobile communications business. Today, the software in a typical mobile phone amounts to 25 megabytes. But updates that correct faults or support new functions should amount to just a few kilobytes, since it should be possible to download them automatically via the wireless network.
The Discrete Optimization Department also works on mobile communications networks themselves. Dr. Hans Heller, a mathematician, develops algorithms that find the best locations for cellular transmission towers to assure complete network coverage at the lowest cost. Heller is confident that "there is still a lot of room for further improvement."
In developing UMTS networks, Siemens prefers to use existing GSM towers to help its customers keep their costs to a minimum. However, an optimally located GSM base station isn’t necessarily optimally located for UMTS. But time is of the essence—Siemens is now building a UTMS network in Shanghai. So Heller is running the network through his algorithm as a test case. If the results are satisfactory, Heller’s optimization algorithm will be integrated into the site selection program, which the Siemens Communications Group will be using for the first time in Shanghai.
Bernd Müller
Optimization—from Greedy to Taboo
The cook in a hospital kitchen may find it a challenge to plan a balanced diet with a limited selection of foodstuffs and a tight budget. This puzzle is a classic example of mathematical optimization, and is referred to as a linear task because there are simple relationships between the variables, without discontinuities. Twice as much orange juice provides twice the vitamins. The cook might be able to solve that puzzle just by wading through dietary charts and foodstuff price lists. But optimization problems lurking in production processes are much more complex. In the 60-year history of mathematical optimization, mathematicians have devised many useful algorithms. The first linear algorithms were put to work in World War II to plan equipment and food logistics. Today, off-the-shelf software is available for solving linear problems.
More recent are algorithms for discrete optimization, in which variables change only in discrete steps. A boiled egg, for instance, is usually consumed entirely or not at all. That makes it more difficult for the cook to maintain the right balance between protein and cholesterol.
An important part of the know-how at Siemens’ Discrete Optimization Department is the ability to search all existing algorithms to find the one that fits the problem. To avoid having to re-invent the wheel, Professor Ulrich Lauther, a world-class specialist in Discrete Optimization, has established the C++ TURBO class library, a toolbox containing pre-existing as well as further developed algorithms for discrete optimization in the C++ programming language. "These algorithms have been tested over and over and are essentially flawless, which can generally not be taken for granted in such complex mathematical tools," notes Lauther. Lauther knows of no other organization that has such a well-equipped optimization toolbox. There is no such thing as a "panacea algorithm" that accomplishes all tasks at the same time, but many optimization tasks can be broken down into their constituent parts and then solved using the algorithms of the TURBO library. As a rule, 70 % of the program code is derived from the library and only 30 % needs to be newly generated to fit a project. In the Profinet IRT optimization algorithm, for instance, nearly three-fourths of the 23,000 lines of code come from the library. Below is a small selection of "discrete optimization" strategies:
- Greedy: The greedy algorithm defines a specified starting state and then selects—step by step—the next state so that gain is maximized. This algorithm is well suited to defining the best itinerary of a business traveler by finding the shortest route through several cities, or to laying out conductors on microchips. But a greedy algorithm doesn’t always lead to the best solution. In placing cellular transmission towers, for instance, it may be best to position some towers at a less-than-optimal spot to get the best possible network coverage overall at the lowest possible cost.
- Taboo search: Unlike the greedy algorithm, a taboo search does permit some changes for the worse—though to the smallest extent possible. To prevent this process from becoming circular, the most recent steps taken are declared "taboo," meaning that they can’t be undone. This approach can be used to find solutions beyond the scope of the greedy method.
- Simulated annealing: This algorithm can be used to find the "global minimum" of a system. A function that depends on many parameters generally resembles a hilly landscape. A marble, on its way down, will rarely wind up in the global minimum, because it gets stuck in one of the many local minimums. The annealing algorithm is based on an analogy from solid-state theory—the thermal vibrations of atoms can be used to escape from local minima. When subjected to slow cooling, the system will tend to end up at the global minimum—analogous to the annealing of metals. This method is used, for example, to minimize mutual interference of mobile communications frequencies in adjacent regions.