We establish a number of facts about the relationship between these dif- ferent sorts of lower bounds, including the equivalence of certain linear- programming-based lower bounds for both of these problems to combi- natorial lower bounds used in successful branch-and-bound algorithms. As a result we obtain the first worst-case analysis of the quality of the lower bound delivered by these combinatorial relaxations.

We then give an empirical evaluation of the strength of the various lower bounds and heuristics. This extends and puts in a broader context a recent experimental evaluation by Savelsbergh and the authors of the empirical strength of both heuristics and lower bounds based on different LP-relaxations of a single-machine scheduling problem. We observe that on most kinds of synthetic data used in experimental studies a simple heuristic, used in successful combinatorial branch-and-bound algorithms for the problem, outperforms on average all of the LP-based heuristics. However, we identify other classes of problems on which the LP-based heuristics are superior, and report on experiments that give a qualitative sense of the range of dominance of each. Finally, we consider the impact of local improvement on the solutions.