My question is about the classic resource constrained project scheduling problem. In my approach, I need to compute a lower bound which is both very tight and very fast. The linear relaxation of which MILP formulation for RCPSP gives the best lower bound? I expect that one of the time-indexed versions provides the best lower bound but I am not sure which one.
Does anyone know of any other fast (linear/polynomial) and tight lower bounding approach?
As the problem is NP-hard you will most probably not be able to obtain a very good lower bound very fast - at least not on most realistically sized problems. That is precisely the nature of NP-hard problems.
From the work of a former PhD student in our group - working on real production planning problems at her company - it has become clear that it is crucial that the variable definition is the "right one", and what is right depends on the problem. In her case, she had the most success with time-indexed models, where she started with a discretization that was course, and then made the time steps smaller, while utilizing a fairly good solution to a courser model as a starting point for the next problem - which then had a more fine time discretization. Whether that works well for your problem I couldn't say, but that is something that I would try. Her publications are quite easy to find.
There is a presentation entitled "Recent developments in mixed integer linear programming formulations for the resource-constrained project scheduling problem" which is available on the web
There is also the chapter "Mixed-Integer Linear Programming Formulations" in the "Handbook on Project Management and Scheduling"
In constraint programming, there are classical algorithms to prune search space for resource constraints : energetic reasoning (strong, n^3 or n^2 log n recently it appears) and edge finding (weaker, n^2 or k n log n). The more the optimal solutions are packed the better.
I would recommend timetable edge finding: http://vilim.eu/petr/
You can also adapt theta-tree based algorithms (see Vilim's 2009 articles for instance) to the RCPSP.
- Badges
- Science topic
- Similar topics
- Psychology