| Article ID: | iaor20051761 |
| Country: | Germany |
| Volume: | 26 |
| Issue: | 2 |
| Start Page Number: | 251 |
| End Page Number: | 262 |
| Publication Date: | Jan 2004 |
| Journal: | OR Spektrum |
| Authors: | Baptiste P., Demassey S. |
| Keywords: | programming: linear |
The best lower bound for the Resource Constrained Project Scheduling Problem is currently based on the resolution of several Linear Programs. In this paper, we show that (1) intensive constraint propagation can be used to tighten the initial formulation of the linear programs and (2) we introduce several sets of valid cutting planes. These improves allow us to “close” 16 new instances of the Project Scheduling Problem test archive library (PSPLIB) with 60 activities and to improve the best known lower bounds of 64 instances.