Sign Out
Logged In:
Tab Image

Latest News

IBM is now able to produce more reliable weather forecasts
IBM now has the capability of isolating and analysing the outcomes of location-specific impacts...

Taxiing need not be taxing
The University of Lincoln has secured a £1m EPSRC grant to develop a new aircraft routing and s...

The risk posed by projected climate change on the world's ability to grow enough food.
A US team of researchers found that forecasted shifts in climate by 2070 would occur too quickl...

Improving clinical care for cancer and intensive care patients and those with chronic wounds

The world's biggest technology companies are joining forces to consider the future of artificial intelligence.
Amazon, Google's DeepMind, Facebook, IBM and Microsoft will work together on issues such as pri...


Tab Image


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


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.