Lower Bounds for the RCPSP: Computational results

Philippe Baptiste and Sophie Demassey


This page provides detailed computational results for various benchmark instances of the resource-constrained project scheduling problem:

Three lower bounds LB-BK, LB-BK-E, and LB-BK-E-PREC [1] are reported. They are all based on the linear programming and constraint programming-based bound of Brucker and Knust [3], improving it by:

  1. using more intensive constraint programming techniques as preprocessing
  2. (for LB-BK-E and LB-BK-E-PREC) introducing several energetic reasoning-based cutting-planes to solve the linear program.

bd_ksd60.txt lower bounds for the PSPLIB benchmark instances with 60 activities
bd_ksd30.txt lower bounds for the PSPLIB benchmark instances with 30 activities
bd_bl.txt lower bounds for the Baptiste-Le Pape benchmark instances


[1] Philippe Baptiste and Sophie Demassey (2004) Tight LP Bounds for the Resource Constrained Project Scheduling, OR Spectrum 26: 251-262.

[2] Philippe Baptiste and Claude Le Pape (2000) Constraint propagation and decomposition techniques for highly disjunctive and highly cumulative project scheduling problems, Constraints 5 (1-2): 119-139.

[3] Peter Brucker and Sigrid Knust (2000) A linear programming and constraint propagation-based lower bound for the RCPSP, European Journal of Operational Research 127: 355-362.

[4] Rainer Kolisch, Christoph Schwindt, and Arno Sprecher (1998) Benchmark Instances for Project Scheduling Problems, in J. Weglarz (ed.), Handbook on Recent Advances in Project Scheduling, Kluwer, 197-212.