Back to list All Articles Archives Search RSS Terug naar lijst Alle artikelen Archieven Zoek RSS

A million dollar reward for the definitive answer!

A million dollar reward for the definitive answer!

The 50 most important research questions for the Netherlands

Where is the line between the predictable and the unpredictable?

“Our field – operations research – has thrived on this problem,” says professor Stan van Hoesel, while he puts a sheet of paper on the table and leaves the room. The paper shows the outline of Germany and inside it a maze of dotted lines. Two minutes later he returns with two cups of coffee and asks: “Can you see what it is?”

It turns out to be one of the many versions of the so-called travelling salesman problem: what is the shortest possible tour that visits each of a list of cities. In this case, the list contains 12,000 cities. “That is unbelievably complicated,” says Van Hoesel. “We can calculate the shortest route between two cities quite easily. All route planners make use of this algorithm, which we owe to the Dutch information scientist Edsger Dijkstra, who died in 2002.”

Operations researchers call the latter a P problem, because there is a quick solution to it. Unfortunately the world is full of problems to which this does not apply at the moment: these are referred to as NP-hard problems, such as the travelling salesman problem. Examples include timetables and complicated rosters. The basic question is whether these NP problems can really be solved or not. This is one of the seven classic unsolved, mathematical questions selected in 2000 by the Clay Mathematics Institute in Cambridge. The first to solve it gets one million dollars.

“The difficulty is that the solution should apply to all cases. We have conquered the travelling salesman problem for a list of 30 thousand cities. For anything over that number, the algorithm does not work.”

Operations research is in fact applied mathematics, says Van Hoesel, who has worked for such companies as KPN, the Dutch Railway, and France Telecom. Its applications are manifold. He is currently talking with Q-park about the most suitable parking rates to charge visitors if they no longer need to pay per hour but per minute. At the same time there is a study on increasing the height of the dikes surrounding the IJsselmeer.

“The water level is expected to rise over the next hundred years and there are dozens of dikes around the IJsselmeer that will have to be heightened. The question is which dikes need to be dealt with, considering the damage that would otherwise be caused. The Bureau for Economic Policy Analysis wants to know how they can keep the cost, in terms of damage and dike repairs, as low as possible. We have now made a model that can be used to calculate this. It is not altogether clear yet but I am confident that it will work.”

 

Maurice Timmermans

The Royal Netherlands Academy of Arts and Sciences (KNAW) has listed the 50 most important research questions for the Netherlands. The 50th is the result of a competition, which was won by two UM researchers

Categories:Categorieën:

CommentsReacties

There are currently no comments.Er zijn geen reacties.

Post a Comment

Laat een reactie achter

Door een reactie te plaatsen gaat u akkoord met de verwerking van de ingevulde gegevens door Observant.
Voor meer informatie: Privacyverklaring
By responding, you agree to send the entered data to Observant.
For more info: Privacy statement

Name (required)

Email (required)