Description

Below are experimental results for a new O(n2) edge-finding filtering algorithm for cumulative resource constraints, as reported in: Experiments were performed on the PSPLib Resource-Constrained Project Scheduling Problem (rcpsp) benchmarks, specifically the J30, J60 and J90 single-mode instance sets. The new filter was compared with the state-of-the-art edge-finder for cumulative resources, described in:

The quadratic filter was implemented on the Gecode 3.4.2 constraint programming toolbox, and compared with the included implementation of Vilím's algorithm.

Runtimes

The first file reports runtimes (in ms) and makespans for the best solution out of three trials for each of the two algorithms. Speed-up shows the proportional increase in speed for the quadratic algorithm; instances not solved by the cut-off time of 300 seconds have no time reported. Additionally, the number of propagations, size of the search tree (number of nodes), peak depth, and number of backtracks (fails) are reported. The reported number of propagations is for all constraints posted on the problem, including those enforcing the precedence constraints.

[Runtimes]

Propagation Strength

In order to more accurately compare the propagation strength of the two algorithms, the propagators were instrumented. The following results once again show the number of propagations, nodes, and fails, and the peak depth, for all solved instances; however, in this case, the number of reported propagations is for the edge-finding propagator only.

[Propagations]