Mathematical Optimization

Ada:

Hello! I’m Ada Lovelace.

I lived in the 19th century and I developed the first ever computer program. I think it’s amazing what this has evolved into today. Fraunhofer IIS has even named its new competence center after me: the ADA Lovelace Center for Analytics, Data and Applications.

This is where researchers and scientists work on developing, enhancing and applying methods and techniques based on artificial intelligence. Really exciting stuff! What I’d like to know, of course, is what research is being done there now. So today, I’m talking to Andy. He works at the ADA Lovelace Center, coordinating the mathematical optimization competence group. I myself am no stranger to math, but could you please explain a little about the methods you use?

 

Andy:

Hello Ada! I’d love to tell you about the work we do.

Essentially, mathematical optimization comes into play when a company wants to make its workflows and processes more efficient. That company generally sets us a clear-cut task, like drawing up run schedules, production plans or shift schedules for its employees. We can help optimize the situation by coding all the decisions that need to be made, as well as the effects of those decisions, into a mathematical model. The solutions to the model then precisely describe the solutions that also work for the planning model.

The company’s planners also furnish us with an assessment criterion that lets us tell the good solutions from the bad ones. Once we’ve solved the problem, we pass it on to the user, who can then check to make sure we’ve met all the conditions. It often happens that something gets left out, either because it was never formally recorded, seemed to go without saying or existed solely as the planner’s gut feeling. Little by little, we identify all the restrictions that have to be factored in. And in the end, we really have a solution that checks off all the relevant boxes.

 

Ada:

That sounds fascinating! Since much of my work had to do with data, I know that there are many different kinds of data out there. What kind of data do you use in the work you’re describing?

 

Andy:

The fact is, solving any problem requires a clearly defined set of parameters, namely those that describe the problem at hand. For example, to optimize a production plan, I need data on the availability of raw materials, machinery and personnel. I have to know the level of customer demand as well as the costs associated with consuming the various resources. For each effect that must be taken into account, I need precisely the right kinds of data for describing that effect. And even if the data itself isn’t entirely accurate, or if it will change depending on, say, future events, we can still make a difference – whether by minimizing projected costs or minimizing costs should the worst happen.

 

Ada:

And is there a minimum or maximum number of parameters?

 

Andy:

Not really, no. It’s more a case of the more complex the problem, the more parameters are required to solve it. This tends to come up when physical effects are involved, such as how natural gas flows through pipelines, or when you have water or other liquids moving through a tube. Then there’s no getting around solving certain physical equations, and that means I have to be able to determine the parameters as precisely as possible. For instance, this is also true when I’m optimizing power grids – at the moment we’re optimizing the energy efficiency of the Nuremberg subway system. One thing we have to know is exactly how energy recuperation works. Whenever a train brakes, it can convert some of its kinetic energy back into electrical energy, feed it back into the grid and another train can then use that energy to accelerate. We need to know these effects inside out before we can describe them in an optimization model.

 

Ada:

Ah, so that’s how it works!

There are now many methods and skills that fall within the scope of artificial intelligence. The ADA Lovelace Center is already working with nine of them. What’s so special about mathematical optimization?

 

Andy:

I’d have to say that what’s special about mathematical optimization is that it provides us with the mathematically proven best solution for a given problem. As I said earlier, we arrive at that solution by translating the task at hand into a mathematical model. Into this model we’ve coded every single conceivable solution, not leaving out any possibility. You can think of it like a large point cloud in a space, where each point represents a solution. The target criterion provided by the planner basically highlights the good points – in other words, the good solutions. And once we have those, we can zero in on the optimum solution. “Optimum” means the “best possible” or the “best conceivable.” So what we’re looking for is the best possible solution for any given planning problem.

We then design our algorithms so that they search specifically among the good solutions to find the optimum one, and as such can eliminate the vast majority of bad solutions right at the start. And using special techniques that we develop in-house, we can efficiently sift through the remaining good solutions to find the best possible one. In this way we really end up with the optimum solution.

 

Ada:

So, if I’ve understood you correctly, the focus at the ADA Lovelace Center is on developing the mathematical foundation for finding not just a solution, but the best solution to a given problem. And this foundation is then applied in further projects, for instance with industry partners. This is bound to appeal to organizations in many different areas. Where can these methods be applied? In what industry, or in what sectors?

 

Andy:

As a matter of fact, optimization plays a role in a whole range of different sectors. We’ve worked with Deutsche Bahn to optimize transport routes for freight traffic and we’ve drafted plans for train driver deployment. In my own doctoral dissertation, I calculated how to optimize traffic in the rail network. Right now, we’re working with VAG in Nuremberg to make subway traffic more efficient. We’re doing this by creating better timetables. By making slight adjustments to when trains depart and how fast they go, we can, for example, prevent too many trains from departing at the same time. When this happens, the grid has to provide the trains with a great deal of energy all at once, which drives up costs. As I mentioned earlier, when one train brakes, the recuperated energy can be made available to another train to accelerate. However, this hinges on one train braking precisely when another is accelerating. We can ensure this happens through optimization.

The same is true when we optimize energy networks. For instance, we’re working with OpenNet Europe to optimize how natural gas flows through pipelines. And in collaboration with Siemens, we’ve already worked out plans for decentralized, self-sustaining settlements. In partnership with SAP, we’re calculating optimized production plans for industry. And with Bilfinger, we’ve already optimized the energy efficiency of future buildings. We’re also currently working with the Martin Bauer Group to optimize its tea production. To maintain product quality, we’re examining which batches of raw materials from which warehouse need to be combined to produce which end product.

So you can see that optimization is a broad field. Our methods and techniques could be applied in virtually any sector.

 

Ada:

This already sounds like considerable added value and progress. I’m wondering something, though: given the wealth of expertise in AI, what other methods could be paired with mathematical optimization? Is this perhaps already happening somewhere? What are the benefits?

 

Andy:

The combination of mathematical optimization and artificial intelligence is an extremely dynamic and fascinating area of research. It’s ultimately about taking the insights that machine learning gives us and distilling them into concrete recommendations for action. The simplest way to apply machine learning is to estimate and define previously unknown parameters for the problem at hand. For example, you can use past demand data to estimate a manufacturing company’s current customer demand. You can also use data to derive the probability distribution, which allows you to identify what will likely turn out to be the best solution. I’m most interested in optimization in real time – in other words, while a system is running. This essentially involves submitting short-term forecasts for what the system will do next at any given point, so that we can intervene to optimize and regulate the situation. We’re working on similar techniques, for instance as part of the project with VAG in Nuremberg, and whenever we’re asked to control a company’s production processes in real time.

 

Ada:

I have to say that I’m really amazed at how rapidly the field of mathematical optimization has advanced over the past 100 years. It’s now possible to solve complex models that in my time were considered unsolvable. And the way the various methods are now being combined marks yet another leap forward. I’d like to thank Andy for this fascinating conversation, and I also want to say that I’m looking forward to getting to know more colleagues from the ADA Lovelace Center and hearing more about the other areas of expertise and application. That’s it for me, Ada Lovelace.

 

Until next time!