Tight LP bounds for resource constrained project scheduling (Q1880319)

In the paper destructive lower bound procedures for the resource-constrained project scheduling problem (RCPSP) are described, which are based on constrained propagation and linear programming. After generating redundant disjunctive resources by solving a mixed integer program, constraint propagation is applied in order to derive new constraints or to detect infeasibility. Afterwards, a linear programming lower bound is calculated, which strengthens the lower bound from \textit{P. Brucker} and \textit{S. Knust} [Eur. J. Oper. Res. 127, No. 2, 355--362 (2000; Zbl 0990.90055)] by additional cuts. Computational results are presented for the well-known RCPSP-instances from the library PSPLIB [cf. \textit{R. Kolisch} and \textit{A. Sprecher}, Eur. J. Oper. Res. 96, No. 1, 205--216 (1997; Zbl 0947.90587)].