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.