Suppose you are given a scheduling problem and told to optimize the total time taken. After a great deal of work you might well find the shortest schedule, but such a schedule is likely to require a very careful interplay between jobs and so not have much slack available. The schedule is likely to be fragile: if unforeseen circumstances force some job to be delayed then it might be difficult or impossible to repair the schedule.
Experience suggests that it is is often better to take a solution that is slightly sub-optimal but a lot more resilient. By paying a little more money up front we might get a solution far less likely to end up requiring very expensive repairs.
However, a problem arises when we try to quantify this intuition and transform it into workable algorithms and solutions.
In order to tackle this problem from a fresh viewpoint we have introduced the concept of supermodels.
The simplest kind of supermodel is a model with a guaranteed, though limited, robustness. For example, a supermodel of a satisfiability problem is a model with the guarantee that if any one variable is flipped, then there is some other variable that you can flip to recover a model again.
The main surprise from this work is that finding supermodels is generally in the same complexity class (NP-complete) as finding models.