On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems

Enumerative approaches to solving optimization problems, such as branch and bound, require a subroutine that produces a lower bound on the value of the optimal solution. In the domain of scheduling problems the requisite lower bound has typically been derived from either the solution to a linear-programming (LP) relaxation of the problem or the solution to a combinatorial relaxation. In this paper we investigate, from a theoretical perspective, the relationship between several LP-based lower bounds and combinatorial lower bounds for three scheduling problems in which the goal is to minimize the average weighted completion time of the jobs scheduled.We establish a number of facts about the relationship between these different sorts of lower bounds, including the equivalence of certain LP-based lower bounds for these problems to combinatorial 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 bounds delivered by these combinatorial relaxations.