Sign Out
Logged In:
 
 
 
 
 
Tab Image

Latest News

Buzz for help
Results from a new study reveals product performance forecasts months before product release.

Life!
Madingley model capturing and depicting structure and function of ecosystems around the world.

Rowing for Gold
SAS and UK sport keeping UK rowers ahead. Using analytics to improve performance

Prevent long delays rather than reduce the average delay
Passengers offset schedule delay costs increase, even in very unreliable systems.

There is evidence that salmon use the Earth's magnetic field to perform extraordinary feats of navigation.
Study suggests Pacific salmon are born with a "magnetic map" that helps them to migrate.

More

Tab Image

Features

A window on the world of O.R.?
The “invisibility cloak” of science fiction is now fact, albeit with limitations. O.R. could claim to have had the power of invisibility for years, though not by desire; what we want is the opposite - a high-visibility jacket! Indeed, part of the mission of the OR Society is to help make our presence more visible. But perception involves both the observed and the observer. And all of us have open and hidden parts.

YOR18 – OR – A Twenty Twenty Vision
The 18th Young [to] OR Conference got off to a great start with the plenary session given by the President of the OR Society, Dr Geoff Royston. Antuela Tako, the chair of the organising committee, began the proceedings by telling the audience what had been planned for them and how to find out more about streams.

The Education & Research Committee
- Roles and Responsibilities: Brian Dangerfield (Liaison with ESRC)
Ruth Kaufman, Inside OR February 2013

Tab Image

Posted on 22 October 2012

Mathematics

Hard problems at OR54

At OR54, this year’s annual conference held 4-6 September in Edinburgh, NP hard problems were very much in evidence.  One of the papers was given by Guido Diepen who has used a constraint programming approach to the problem which is apparently particularly good at solving Sudoku type problems. 

A problem is classified as “P” (or P-hard) if it can be solved quickly.  There is another group which have the property that if one is given the solution then one can quickly verify that the answer is true or false.  This group is known as “NP” (or NP-hard).  Note, if one can solve a problem quickly then one can verify the solution quickly so a P-hard problem is also an NP-hard problem.  The literary million dollar question is whether the reverse is true; can all problems whose solutions can be verified quickly also be solved quickly?  The Cray Foundation offered one million dollars in 2000 to the first person to prove this one way or the other – so far there have been no takers.  There is a third category called NP-complete – these are the key to “life, the universe and everything”.

Not only does Guido Diepen’s solution solve problems quickly, provided there is a feasible solution, it does so in a way which makes it relatively easy for the user to describe in terms of the constraints.  An example is that one can simply state that all values in row j have to be different (for rows j = 1, 9) similarly for columns and for the 3x3 boxes.  These constraints require quite of a lot of coding to achieve the same in a linear or integer programming model.  Although this approach greatly simplifies the problem in terms of setting up the constraints, it still uses a heuristic approach so does not reduce the problem from NP to P.