The last ten years have seen extensive work on the instance hardness of intractable problems, most of it focussed on phase transitions in decision problems such as k-SAT and graph coloring. Surprisingly, here has been very little on the instance hardness of the optimization form of these problems, although optimization ("Find the least resources required to solve this problem") is much more used in practice than decision ("Is there a solution within resource bound B?"). One important indicator of problem hardness is the "backbone", or set of variables which are set to the same values in all solutions.
In this paper we extend the notion of a backbone from decision to optimization problems (and also to approximation problems). We find that for some optimization problems (e.g. graph coloring) the backbone size is positively correlated with hardness, while for others (e.g. Travelling Salesman) the cost of finding an optimal solution is positively correlated with the backbone length, while the cost of proving it optimal is negatively correlated. Yet other problems (e.g. number partitioning) show regions of each of these behaviours. Here we report our experimantal findings, and some reflections on why these things should be.