ASU professor makes problem-solving software available to all; use it to plan a Fall Break road trip or an efficient diet
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.”
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.”
Sun Devil Soccer Comes From Behind to Defeat Washington in 2OTs
Madison Kmetko's goal in the 105th minute of play gave the Arizona State women's soccer team its first Pac-12 win on Thursday as the Sun Devils came from behind to defeat the Washington Huskies, 3-2 in double overtime.