Table 2: Cpu times (t) in secs, nodes (n) and constraint checks (cc) from RLFAP
instances. Algorithms that use heuristics are denoted by their name + H. The best cpu time among the lmaxRPC methods is highlighted.

| instance    | ACrm    | lmaxRPCrm lmaxRPC3rm lmaxRPCrm + H lmaxRPC3rm + H   |         |         |         |         |
|-------------|---------|-----------------------------------------------------|---------|---------|---------|---------|
| scen11      | t       | 5.4                                                 | 13.2    | 4.6     | 12.5    | 4.3     |
| n           | 4,367   | 1,396                                               | 1,396   | 1,292   | 1,292   |         |
| cc          | 5M      | 92M                                                 | 29M     | 90M     | 26M     |         |
| scen11-f10  | t       | 11.0                                                | 29.0    | 12.3    | 22.3    | 9.8     |
| n           | 9,597   | 2,276                                               | 2,276   | 1,983   | 1,983   |         |
| cc          | 11M     | 141M                                                | 51M     | 114M    | 41M     |         |
| scen2-f25   | t       | 27.1                                                | 109.2   | 43.0    | 79.6    | 32.6    |
| n           | 43,536  | 8,310                                               | 8,310   | 6,179   | 6,179   |         |
| cc          | 44M     | 427M                                                | 151M    | 315M    | 113M    |         |
| scen3-f11   | t       | 7.4                                                 | 30.8    | 12.6    | 17.3    | 7.8     |
| n           | 7,962   | 2,309                                               | 2,309   | 1,852   | 1,852   |         |
| cc          | 9M      | 132M                                                | 46M     | 80M     | 29M     |         |
| scen11-f7   | t       | 4,606.5                                             | 8,307.5 | 3,062.8 | 6,269.0 | 2,377.6 |
| n 3,696,154 | 552,907 | 552,907                                             | 522,061 | 522,061 |         |         |
| cc          | 4,287M  | 35,897M                                             | 9,675M  | 22,899M | 6,913M  |         |
| scen11-f8   | t       | 521.1                                               | 2,680.6 | 878.0   | 1,902.4 | 684.7   |
| n           | 345,877 | 112,719                                             | 112,719 | 106,352 | 106,352 |         |
| cc          | 638M    | 10,163M                                             | 3,172M  | 7,585M  | 2,314M  |         |
| graph8-f10  | t       | 16.4                                                | 16.8    | 9.1     | 11.0    | 6.3     |
| n           | 18,751  | 4,887                                               | 4,887   | 3,608   | 3,608   |         |
| cc          | 14M     | 71M                                                 | 31M     | 51M     | 21M     |         |
| graph14-f28 | t       | 31.4                                                | 4.1     | 3.1     | 2.6     | 2.1     |
| n           | 57,039  | 2,917                                               | 2,917   | 1,187   | 1,187   |         |
| cc          | 13M     | 17M                                                 | 8M      | 13M     | 6M      |         |
| graph9-f9   | t       | 273.5                                               | 206.3   | 101.5   | 289.5   | 146.9   |
| n           | 273,766 | 26,276                                              | 26,276  | 49,627  | 49,627  |         |
| cc          | 158M    | 729M                                                | 290M    | 959M    | 371M    |         |

Experiments showed that lmaxRPCrm is the most efficient among existing algorithms when applied during search, which confirms the results given in [10]. Accordingly, lmaxRPC3rm is the most efficient among our algorithms. It is between two and four times faster than maxRPC3rm on hard instances, while algorithms lmaxRPC3 and lmaxRPC2 are not competitive when used during search because of the data structures they maintain. In general, when applied during search, any maxRPC algorithm is clearly inferior to the corresponding light version. The reduction in visited nodes achieved by the former is relatively small and does not compensate for the higher run times of enforcing maxRPC.

Results from Tables 2 and 3 demonstrate that lmaxRPC3rm always outperforms lmaxRPCrm, often considerably. This was the case in all 200 instances tried. The use of heuristics improves the performance of both lmaxRPC algo-