[NEW!] I have just released the code of the PCP solver we used for the experimentation, with all the MCS detection algorithm implemented.
This page contains links to pseudo-code and experimental results for an MCS detection method we proposed, based on the solution of a minimum flow problem. In exerimentation we compare:
- the min-flow based strategy (referred to as MINFLOW)
- the enumerative strategy from: "Laborie, P. (2005). Complete MCS-Based Search: Application to Resource Constrained Project Scheduling. Proc. of IJCAI (pp. 181-186). Professional Book Center.", referred to as ENUM
- the envelope based strategy from "Policella, N., Smith, S. F., Cesta, A., & Oddi, A. (2004). Generating Robust Schedules through Temporal Flexibility. Proc. of ICAPS (pp. 209-218).", referred to as PEAKS
- min-flow plus random CS minimization, referred to as RAND
All appraoches are tested within a (retively) classical CP Depth First Search approach (referred to as CP) and an optimization appraoch based on the destructive computation of increasing lower bounds (referred to as SWEEP). More details can be found in this paper.
Here is the pseudo-code for minium flow computation and for the extracttion of the maximum weight independent set (if the graph has been build by splitting nodes with non-null flow resource requirement):
Beware, while the real code has been extensively tested, the pseudo code has not.
The following list contains link to tables with the results for single approaches and pairwise comparisons; note that since comparison are done on an instance basis, their data cannot be deduced by single approach tables. All tables are in CSV format and use Linux EOL.
The following list is a selection of summary results; they are much more readable than the previous ones.
- summary for single approaches
- pairwise appraoch comparison, with CP strategy
- pairwise approach comparison, with SWEEP strategy
- comparison of CP and SWEEP strategy for each approach
- summary for j120