Sign Out
Logged In:
 
 
 
 
 
Tab Image

Latest News

Graduate economy
UK has passed a significant milestone towards becoming a graduate economy

A2B beautifully
Yahoo Labs have devised an algorithm that will give the “prettiest” route from A to B.

Yahoo threatened with fine
Yahoo said the US government threatened fine if the search giant failed to hand over user data.

In the Clouds
Warwick Business School campus to open at The Shard

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

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.