|Illustration Credit: Yesenia Carrero /UConn|
These professors made a ridiculously hard logistics problem easy to solve. In the process, they smashed a basic tenet of computer theory. And now they’re offering a $10,000 prize to anyone who can show they’re wrong.
“You have many choices to make. What’s your best choice, given limited resources, to maximize your profit?” asks Moustapha Diaby, an associate professor of operations management in UConn’s School of Business.
It may be the basic question of life in a capitalist society. It’s also the basic question behind operations research, a field of study that blossomed in the 1940s. One of operations research’s basic insights is that linear programming, which is part of a broader technique called “constrained optimization,” can answer these common business questions, says Diaby.
Imagine, for example, that you run an oil refinery. You need to decide how much gasoline (g) and diesel fuel (d) to make from each barrel of oil in order to maximize your profit. If you make a $3 profit per gallon of gas, and $5 per gallon of diesel, the objective of the optimization problem would be to maximize 3g + 5d.
But there are some constraints. For every barrel of oil, the refining process limits you to certain proportions of gas to diesel, maybe 2g + 5d = 10. From a mathematician’s point of view, the maximization equation and the constraint equation each define a plane. To solve the problem, they map out these planes together, and find the spot where the profit is highest. That spot would tell you exactly what proportion of gasoline to diesel you can refine to maximize the money you get.
We can solve it with a couple of examples in our heads; for example, according to the constraint equation, if you make 1 part of gasoline, you’d make 8/5 parts diesel. Plug that into the profit equation, and you’d get 11 dollars profit. If you make 3 parts of gasoline from the barrel, you’d make 4/5 parts diesel, and a profit of 13 dollars. You can do this for any number greater than 0 (because you can’t make negative -2 gallons of gas.)
With only two options, it’s pretty easy. In a real refinery, you’d have many more choices of product: jet fuel, bunker fuel, asphalt, kerosene, naphtha, paraffin. And more constraints, too. Instead of just two planes, you’d have to analyze many at the same time. But the problem would still be easy to solve with a computer using linear programming. Many, many business challenges can be effectively analyzed this way, from manufacturing to merchandising. But there’s one area in which it fails: the Traveling Salesman Problem.
The Road Less Traveled
Until now, no one could figure out the classic conundrum of how a traveling salesman can minimize his travel distance without having to calculate every possible route. Formally described, the Traveling Salesman Problem features a salesman who needs to visit clients in a specific number of cities while traveling the shortest distance. The constraints are that he must visit every client, but only once; the parameters a, b, c, etc. are the distances between each pair of clients. The problem seems perfect for the linear programming method. Except—and this is key—you have only one salesman, and he cannot be split into parts.
From a human point of view, this is obvious. But the way linear programming analysis works, the ideal solution might require us to have fractional salesmen traveling around. Maximizing profits at an eighth of a gallon of diesel fuel is easy for a petroleum refiner. Minimizing travel distance with an eighth of a salesman is impossible.
“Up to now, nobody could find a way to express the requirement that you cannot split a traveler in the form of hyperplanes,” says Diaby. That means basic linear programming just wouldn’t work.
So, for the last 70 years, people have solved traveling salesman problems by splitting the problem into a series of mathematical models, and then solving them iteratively. The solution of each model depends on the solution of the statement immediately before it.
For example, pick one possible path through the cities and add up the distances. Then pick a different path and do it all over again. And then again, until you’ve looked at every possible path the salesman could take. If there are five cities the salesman must visit, you need to calculate 32 possible routes. If you have 10 cities, you have 1,024 possible routes. At 15 cities, you get 32,768 possible routes. In general, the number of possible routes is 2n, where n equals the number of cities.
“As n grows, pretty soon, you will find yourself with a number that exceeds the number of atoms in the universe,” Diaby says. Even if the salesman is traveling between just 100 cities, an examination of all the possible routes exceeds the calculation capacity of any computer in existence today.
That might seem a silly thing to worry about. After all, who really needs to travel to 100 different cities on a single trip?
Your mail carrier, for one. Just substitute “addresses” for cities. UPS, FedEx, DHL, and other logistics and shipping companies deal with the same challenge on a larger scale every day. Supply chain managers, too. The traveling salesman problem has puzzled logistics managers and mathematicians alike since the 1950s. Now, Diaby and his coauthors believe they have solved the problem by taking a new approach.
Simplify With Complexity
Diaby, Mark Karwan of State University of New York Buffalo, and Lei Sun, Associate Director of Digital, Data Science and Operations Research at Linde, began by focusing on an easy way to express the requirement that the traveler cannot be “split” with hyperplane equations. In their process, the travel costs could no longer be accounted for with the simple variables commonly used in the traveling salesmen problem. They fixed this issue by using a more complex variable. With this fix, their linear program with could always be solved without splitting the traveler!
“Every city and its leg of the trip (and order of visit) is combined with every other pair of city-legs to form a more complex variable. This is very different from the usual, simple ‘city to city’ two dimensional variables used in classic formulations,” Karwan says.
Diaby adds, “Our variables are six dimensional, but the traditional two-dimensional travel leg variables can be inferred from some of them. This allows us to account the total travel cost properly.”
In addition to solving the traveling salesman problem, their solution answers a long-standing question about the mathematics of computability. For almost a century, it’s been known that there are problems which cannot be solved by a computer. Those are called undecidable problems. Other problems are decidable; a computer can always solve them.
But the decidable problems are split into two classes: in the first, called P, the problem is “easy” for a computer to solve relatively quickly. In the second class, called NP, it’s not known whether the problem is easy for a computer to solve quickly, but it is easy to check whether any given solution is correct or not.
If a problem can be solved easily, then it is also easy to check if a given solution is the correct one. So, in that sense, a problem that is in P is also in NP. It has been an open question in computer theory whether P and NP are really the same category of problems. Some mathematicians argue that P = NP, that is, there aren’t really any NP problems that are hard to solve, just problems for which we don’t yet know algorithms that can solve them easily.
Diaby, Karwan and Sun’s traveling salesman problem solution supports that. Their algorithm shows that the traveling salesman problem is actually P, which automatically means P = NP. They have posted their proofs and algorithm here, and offer a $10,000 prize to anyone who can find an example for which it doesn’t work. That is, a traveling salesman problem that cannot be solved with their algorithm.
Describing their approach more technically, Karwan says “The operations research community will recognize that we have used an engineering/modeling approach to lift the classic assignment approach (assign which city to which stage of the trip) into a higher-dimensional space and then applied an appropriately modified cost function. There is no reference to the classic city-to-city polytope, and its variables and constraints would be redundant in our model.”
“Nobody has been able to find a specific flaw in our proofs, but only refer to work that theorizes that it can’t be done. A criticism against prior versions of our model was that they were too large to be meaningfully tested on actual problems. The current version of our model is hundreds-to-thousands of times smaller. So, meaningful experimentation can now be conducted on it. “We want to get the community to look and try it out,” Diaby says.
Source/Credit: University of Connecticut | Kim Krieger