Min-flow based MCS Detection
[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):
LEGENDA: - Q = queue containing nodes (indices) to be visited - pre[i] = predecessor of node "i" along a diminishing path; in detail, if the predecessor is node "j", pre[i] stores "j+1" if node "i" is reached through a forward arc, "-j-1" if it is reached through a backward arc - d[i] = maximum allowed variation at node "i" on a diminishing path - source = index of the source node - sink = index of the sink node - flow[i][j] = flow on arc (t, j) - r[i][j] = minimum flow requirement on arc (i, j) find initial flow (with any technique) // start building diminishing paths stop = false while stop is false: // reset current diminishing path set all pre[i] to 0 // add source node to the current diminishing path pre[source] = source + 1 d[source] = infinity // start building the path while Q is not empty and pre[sink] = 0: pop a node index "i" from Q // visit forward arcs for each arc (i, j) in the graph with pre[j] != 0: // visit a forward arc only if it appears in the residual graph if flow[i][j] > r[i][j]: pre[j] = i + 1 d[i] = min(d[i], flow[i][j] - r[i][j]) push j on Q // visit backward arcs for each arc (j, i) in the graph with pre[j] != 0: // always visit backward arcs (there's not upper limit on the flow) pre[j] = -i -1 d[j] = min(d[i], infinity) push j on Q // now, if the sink has not been reached, the minimum flow has been found if pre[sink] = 0: stop = true // else, we have to diminish the flow along the path else: i = sink while i != source: if pre[i] > 0: // update flow on a forward arc j = pre[i]-1 subtract d[sink] from flow[j][i] else: // update flow on a backward arc j = -pre[i] -1 sum d[sink] to flow[i][j] // move to previous node on the path i = j // extract relevant arcs from the S/T cut (in the modified resource graph, // those correspond to activities/requirements for each arc (i, j) in the graph: // if node i has been visited, node j has not and the flow is not null if pre[i] != 0 and pre[j] = 0 and flow[i][j] > 0: add pair (i, j) to the set of relevant arcs in the S/T cut // compute overall flow value f = sum of flow[source][i] for every arc (source, i) in the graph
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