Destination: Optimization

Everyone’s got a morning routine; certain steps we take to get cleaned, dressed, fed and out the door on time. The order of those steps is very important. Switch it up and you could be late.

The same goes for building microchips, or performing surgery, or baking a pie — one misstep and the whole thing falls apart.

“Optimization is everywhere,” says Hans Mittelmann, professor in the School of Mathematical and Statistical Sciences at ASU. “It is the single most pervasive thing. Optimization needs to be applied to basically everything you do.”

ASU professor Hans Mittelmann

Acting out of what he describes as a sort of altruistic sense of duty, for the past 20-plus years Mittelmann has maintained a set of optimization problem “solvers,” many of which are available through the online web server NEOS.

The solvers, which are free and accessible to the public, can provide solutions to sudoku puzzles, supply chain production issues, and even “the diet problem” — how to select foods that will satisfy a set of daily nutritional requirements at a minimum cost.

Recently, a couple of road-trip enthusiasts used a solver Mittelmann made available through NEOS to find the most efficient route through 412 National Park Service sites in commemoration of its 100-year anniversary. Called Concorde, the solver provides a solution to what is known as the traveling-salesman problem: how to find the shortest route between many points in a closed loop.

In a blog post, one of the road trippers, Adam Larsen, called Concorde “one of the best traveling-salesman problem solvers out there,” and Mittelmann “a brilliant mathematician.”

The Concorde solver has also been used for Pokemon Go, to help players hit as many PokeStops as possible in various metropolitan areas.

“A lot of people have these kind of problems, but they have no way of implementing the commercial software needed to solve them,” said Mittelmann. “So I make it available to them through my solvers.”

Every solver he offers has sample submissions people can look at to see how they work. For the traveling-salesman problem, all one has to do is upload a list of the GPS coordinates of the map points they wish to visit, and the solver gives them an output of indexed legs of the journey that can be downloaded.

“The solver at NEOS is incredibly fast,” said Larsen. “The problem was solved in a mere matter of seconds.”

Though Concorde and solvers like it take only seconds to produce a solution, the software behind them is “very sophisticated.”

“Most of the programs I have installed have had a development period of some 10 or 15 years, and a number of people involved,” said Mittelmann. “They are so complex.”

Mittelmann (front row, center) with the class he taught on numerical optimization software at the University of Freiburg in Germany this summer. Photo courtesy of Hans Mittelmann

Because of that, the solvers need constant updating. Mittelmann estimates he spends a few hours a week doing just that, in addition to his teaching and research duties. But, he says, “It’s a service which I’m happy to provide,” adding that he’s always willing to give time to people who have questions about his solvers, which he did for one man who had been using the Concorde solver to help his 16-year-old son with geocachingGeocaching is an outdoor recreational activity in which participants use a Global Positioning System device and other navigational techniques to hide and seek containers, called “geocaches” or “caches,” at specific locations marked by coordinates all over the world..

Mittelmann has also used the Concorde solver to impress crowds at ASU’s Night of the Open Door. His exhibit, “A Picture Worth 100,000 Dots,” uses math to convert an image into 100,000 dots, and then draws a line as close as possible to the shortest length required to connect all the dots. If it were to be drawn by hand, it would take only one single stroke without lifting the pencil.

The exhibit has grown in popularity each year.

“I’m happy that it shows math to the broader public,” said Mittelmann.

His solvers are well-known around the world by experts and are often used by researchers and classes at universities and high schools. And the attention they’ve garnered has brought Mittelmann some exciting opportunities: This past summer he was invited to teach for two months at a summer school on numerical optimization software in Germany, and he was recently invited by the Department of Energy to participate in a study to better compute electricity distribution across the United States.

“I’m not an electricity expert at all, but they picked me because the key [to better electricity distribution] is optimization.

“So these are the rewards I get for my service activity, and I’m really happy that I can do that. I sit on the computer basically all day anyhow,” Mittelmann said with a laugh.