  |
| HOME | THIS ISSUE | CALENDAR | GRANTS | BACK ISSUES | < BACK | NEXT > |
Researcher develops mathematical model to help solve complex business problemsby David Bauman - April 30, 2007 | ||||
| Moustapha Diaby has developed a mathematical model that could provide answers to business problems so complex they cannot be solved by computers. Diaby, an associate professor of operations and information management in the School of Business, is an industrial mathematician who specializes in operations research and optimization procedures that help companies manage their production networks more efficiently. An article based on his research, titled “The Traveling Salesman Problem: A Linear Programming Formulation,” is to be published this month in the peer-reviewed journal WSEAS Transactions on Mathematics (WSEAS stands for World Scientific and Engineering Academy and Society). Diaby’s work may resolve the notorious “P versus NP question,” one of the most important unanswered questions in contemporary mathematics and theoretical computer science. The P vs. NP question essentially asks whether a problem whose solution can be verified to be correct in reasonable time on a computer can also, in principle, be solved in reasonable time. For example, a jigsaw puzzle can be verified to be the right answer by a quick visual inspection, but to put it together is not as easy. Diaby – through his research – is answering this question in the affirmative. His work could lead to billions of dollars in increased profits for business and industry, by providing an incentive to optimize many practical tasks. Consider, for example, the so-called Traveling Salesman Problem. Picture a traveling salesman planning the most efficient route to visit three cities by car. To save gas and time it makes sense to map a route where the total distance traveled is as small as possible. It’s a relatively easy task to come up with the best plan, as only six routes are possible. Suppose the salesman is trying to find the cheapest route between 10 cities, starting and ending at the same city and visiting each city only once. He’d probably want to use a computer to calculate mileage vs. time for different routes and work out the totals. He’d better, because with 10 cities to visit, the number of possible routes is more than 3 million! Add one more city and the number of possible routes jumps to almost 40 million. The exponential growth of possible routes to be examined makes finding the optimal route all but impossible.
Yet a 25-city itinerary is a reality for many professional salesmen. Similar dilemmas caused by data that present too many possibilities have stumped the airline industry’s efforts to determine optimal timing for pilot, crew, and aircraft flight and maintenance schedules, for example. Although computers can speed up a search through such data, the number of possibilities is so large that the search takes prohibitively long to complete. The only way to solve such cases practically is to find a method that avoids conducting an exhaustive computational search, says Diaby. The P vs. NP question essentially asks whether such a method exists. “The quest in mathematics and theoretical science over the past 40 years has been to discover an answer without having to enumerate all the possibilities,” he says. “The only way out of this problem is to recast it as a mathematical problem and solve it.” Diaby has spent the past three years developing a mathematical model that uses a linear programming formulation. Linear programming is commonly used in industry to help determine the best allocation of resources. Diaby applied intricate linear programming formulations to the Traveling Salesman Problem, enabling researchers to visualize a definitive answer to the P vs. NP question. Although he has not yet refined it into a tool that is practical for “business-sized” problems, he has demonstrated the principle, he adds. Some mathematicians and computer scientists are cagey as to whether he has really cracked the P vs. NP problem. “The P vs. NP issue is one of those notoriously difficult results to prove,” notes Suresh Nair, associate dean for graduate programs in the School of Business and Diaby’s colleague in the operations and information management department. “If this result can be scaled to industrial-sized problems, it would open the floodgates to other applications connected to it.” |
| ADVANCE HOME UCONN HOME |