Computational Results of 3FNLS
Computational Results of 3FNLS
Below are some computational results of our algorithm called 3FNLS
(3-flip neighborhood local search), which was proposed in
M. Yagiura, M. Kishida and T. Ibaraki,
A 3-Flip Neighborhood Local Search for the Set Covering Problem,
European Journal of Operational Research, 172 (2006) 472-499.
In the tables below, "TTB" stands for "time to best," i.e.,
CPU time spent to find the best cost reported in the tables,
and "TET" stands for "total execution time."
Both TTB and TET are reported in seconds.
CLR instances
The 3FNLS algorithm was run on a PC with
a Xeon X3363 2.83 GHz, 6 MB cache, 24 GB memory.
The computation was done on a single thread.
The time limit was set to 300 seconds for each instance.
Computational results of 3FNLS for CLR instances
instance | cost | TTB | TET |
clr10 | 25 | 3.39 | 300 |
clr11 | 23 | 14.97 | 300 |
clr12 | 23 | 38.79 | 300 |
clr13 | 23 | 137.33 | 300 |
RAIL instances
For some RAIL instances, better solutions were found by 3FNLS
by allowing longer computation time.
The 3FNLS algorithm was run on a PC with
a Xeon X3363 2.83 GHz, 6 MB cache, 24 GB memory.
The computation was done on a single thread.
- prev. best: The best solution value reported in
Yagiura, Kishida and Ibaraki (2006).
- new best: The solution value better than prev. best.
- #found/#runs: The number of runs in which the "new best" was found,
and the total number of runs.
- avg. TTB: The average time to find the best solution,
where the average was taken for the runs in which a solution with
the cost in column "new best" was found.
- TET/run: The total execution time per run.
- ---: Better solutions were not found even after long computation time.
Better solutions found by 3FNLS for RAIL instances with 10 runs with time limit of 7200s
instance | prev. best | new best | #found/#runs | avg. TTB | TET/run |
rail2536 | 690 | --- | --- | --- | --- |
rail2586 | 945 | --- | --- | --- | --- |
rail4284 | 1064 | 1063 | 3/10 | 1909.01 | 7200 |
rail4872 | 1528 | 1527 | 1/10 | 3466.81 | 7200 |
Better solutions found by 3FNLS for RAIL instances with 20 runs with time limit of 10800s
instance | prev. best | new best | #found/#runs | avg. TTB | TET/run |
rail2536 | 690 | --- | --- | --- | --- |
rail2586 | 945 | 944 | 1/20 | 4735.92 | 10800 |
rail4284 | 1064 | 1063 | 6/20 | 2366.73 | 10800 |
rail4872 | 1528 | 1527 | 1/20 | 3466.81 | 10800 |
Mutsunori YAGIURA