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
instancecostTTBTET
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.
Better solutions found by 3FNLS for RAIL instances with 10 runs with time limit of 7200s
instanceprev. bestnew best#found/#runsavg. TTBTET/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
instanceprev. bestnew best#found/#runsavg. TTBTET/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