Imagine you are at a ski resort, but don’t have any skiing gear. You can rent or buy it, but which should you do?
The answer hinges on how much you’re likely to ski in the future. But you don’t yet know that, so how do you decide?
This is not just an innocuous problem. We face many similar decisions that depend on unknowable information about the future.
How much stock should I buy to satisfy future demand? How much should I save to support my retirement?
Computer systems are teeming with similar so-called “online problems”, such as deciding which data to store in a form that can be quickly accessed, and when to send data into a network.
They do it using “algorithms” – sets of rules and instructions that break down how a computer is going to set about a particular task. And some of these algorithms are inspired by studying puzzles such as the ski-rental problem.
Algorithms can also cope with increasing complexity. Do you like solving puzzles such as Sudoku or the Rubik’s cube, but are getting tired of the typical 9×9 Sudoku and 3x3x3 Rubik’s cube? How about a super-sized 16×16 Sudoku or a 6x6x6 Rubik’s cube? While puzzles of such sizes stretch human capabilities, computers can breeze through them with just a bit more computing power.
The amount of extra processing power required isn’t necessarily linear, though – doubling the size of a puzzle can require a million times more computational grunt.
Indeed, there are tons of problems, from puzzles to practical applications, which steadfastly resist computer scientists’ attempts to find an efficient algorithm.
Some of these are problems that on the face of it don’t seem that hard at all – how to optimally pack a knapsack with any set of different-sized objects, for example, or how to find the shortest cycle route on a map – can actually be extremely tricky, to the extent that finding the best solution requires an absurd or impractical amount of computing power.
In these cases, the answer is sometimes to look for a solution that is “good enough”, rather than necessarily the best. It can be the case that an algorithm produces outcomes approximately close to the best, while using far less computing power than the dead-accurate alternative.
All these algorithms underpin the information economy on which we all depend, making information processing faster and more cost-effective.
They power our gadgets, which use ingenious algorithms that continuously optimise the quality of their graphics and speed up processing time.
And they can help us with the new challenges of sustainability. How do we balance energy supplies and demands for an uncertain future? How do we allocate scarce resources effectively, despite the growing complexity?
One such problem we are working on at the Masdar Institute is how to efficiently regulate power generation in the presence of an unsteady renewable energy supply, such as wind or solar.
We are designing algorithms that can determine when the backup power supply – a traditional power plant – should be turned on to meet a shortage of energy from a renewable source, in real-time.
The result, we hope, will be a more efficient and reliable renewable energy-powered electricity grid – essential if Abu Dhabi is to meet its target of 7 per cent of its power from renewables by 2030.
Dr. Sid Chi-Kin Chau is an assistant professor of computing and information science at the Masdar Institute.
