GenSC is a highly configurable framework, which integrates many effective techniques. After automatic configuration, GenSC can instantiate effective local search algorithms that exhibits high performance on solving different types of SCP instances. Extensive experiments on various application SCP instances demonstrate that GenSC performs much better than previous algorithms, indicating that GenSC advances the state of the art in SCP solving.
- Chuan Luo ([email protected])
- Taoyu Chen ([email protected])
- This project is licensed under the terms of the GPLv3 license.
-
All the benchmarks can be found in the directory entitled
Benchmarks
, includingOR-Large
,OR-Small
,Rail
,SCP-CLR
,SCP-CYC
,STS
,SoftTest-L
,SoftTest-M
,SoftTest-S
. Their sizes are summarized inbenchmark_sizes.csv
. -
In our paper, we used SMAC for GenSC's configuration tuning. For each benchmark, we used the following instances as training sets:
Benchmark | Training Set |
---|---|
Rail | rail-507, rail-2536, rail-4284 |
SCP-CLR | scpclr-10, scpclr-12 |
SCP-CYC | scpcyc-6, scpcyc-8, scpcyc-10 |
STS | sts-135, sts-405 |
SoftTest-S | Apache, x264 |
SoftTest-M | BDBC, Dune |
SoftTest-L | sac |
- The source codes of GenSC can be found in the directory entitled
Code
.
To build GenSC, please run the following command:
cd Code && make
Quick Start
To run GenSC with automatically selected parameters and a specific instance (for example:
rail-507.txt
inBenchmarks/Rail/
):./GenSC -inst ../Benchmarks/Rail/rail-507.txt
- All of GenSC's parameters include
General Parameters:
-inst <path/to/instance> specifies the location of the instance (required)
-auto <0/1> whether to select algorithmic parameters automatically (default 1)
-print_sol <0/1> whether to print the solution after GenSC finished searching (see Output Format) (default 1)
-print_step <0/1> whether to print the steps during and after the search (see Output Format) (default 1)
-formatted_print <0/1> whether to print in a more human-friendly format (see Output Format) (default 1)
Specific Algorithmic Parameters:
-cutoff_time <integer in [1, 2147483647]> specifies the time GenSC is permitted to run (in seconds) (default 1000)
-seed <integer in [0, 2147483647]> specifies the seed (default 0)
-max_step <integer in [1, 9223372036854775807]> specifies the maximum step (iterations) of GenSC (default 9223372036854775807)
-perform_bms <0/1> whether to perform BMS heuristic (default 1)
-bms_t <integer in [1, 2147483647]> Available Only When -perform_bms=1 (default 80)
-subset_score_calculation <1/2> (default 2)
-united_calculation_mu <integer in [2, 2147483647]> (default 5)
-solution_initialization_scheme <1-4> (default 4)
-perform_cc <0/1> (default 1)
-perform_iscc <0/1> (default 0)
-perform_tabu <0/1> (default 1)
-tabu_alpha <integer in [1, 2147483647]> (default 4)
-reconstruction_scheme <1-3> (default 1)
-reconstruct_swap_T <integer in [2, 2147483647]> Available Only When -reconstruction_scheme=3 (default 5)
-subset_removal_scheme <1/2> (default 1)
-SAinitN <integer in <2, 5>> Available Only When -subset_removal_scheme=2 (default 5)
-SAt <integer in [1, 2147483647]> Available Only When -subset_removal_scheme=2 (default 10000)
-subset_addition_scheme <1-5> (default 4)
-novel_addition_prob <float in [0, 1]> Available Only When -subset_addition_scheme=2/4 (default 0.1)
-perform_alternate_method <1-4> (default 4)
-update_item_weights_scheme <1-3> (default 3)
-update_item_weights_SAPST <integer in [1, 2147483647]> Available Only When -update_item_weights_scheme=1 (default 100)
-update_item_weights_SAPSR <float in [0, 1]> Available Only When -update_item_weights_scheme=1 (default 0.9)
-update_item_weights_PAWSP <float in [0, 1]> Available Only When -update_item_weights_scheme=2 (default 0.8)
-subset_selection_scheme <1-9> (default 9)
However, some values of the parameters are prohibited since they are contradicted:
-subset_score_calculation=1 && subset_selection_scheme>3
-perform_alternate_method=4 && -subset_removal_scheme=2
- To run GenSC with optimal configurations for every benchmark:
run
./GenSC -inst ../Benchmarks/...
or
For Rail
./GenSC -perform_bms 1 -bms_t 5000 -subset_score_calculation 2 -united_calculation_mu 3 -solution_initialization_scheme 1 -perform_cc 1 -perform_iscc 0 -perform_tabu 1 -tabu_alpha 80 -reconstruction_scheme 2 -subset_removal_scheme 1 -subset_addition_scheme 4 -novel_addition_prob 0.21 -perform_alternate_method 4 -update_item_values_scheme 3 -subset_selection_scheme 8 -inst ../Benchmarks/Rail/...For SCP-CLR
./GenSC -perform_bms 1 -bms_t 170 -subset_score_calculation 2 -united_calculation_mu 80 -solution_initialization_scheme 4 -perform_cc 1 -perform_iscc 0 -perform_tabu 1 -tabu_alpha 5 -reconstruction_scheme 2 -subset_removal_scheme 1 -subset_addition_scheme 4 -novel_addition_prob 0.5 -perform_alternate_method 4 -update_item_values_scheme 3 -subset_selection_scheme 9 -inst ../Benchmarks/SCP-CLR/...For SCP-CYC
./GenSC -perform_bms 1 -bms_t 230 -subset_score_calculation 2 -united_calculation_mu 200 -solution_initialization_scheme 3 -perform_cc 0 -perform_iscc 1 -perform_tabu 0 -reconstruction_scheme 1 -subset_removal_scheme 2 -SAinitN 4 -SAt 50000 -subset_addition_scheme 2 -novel_addition_prob 0.1 -perform_alternate_method 2 -update_item_values_scheme 3 -subset_selection_scheme 2 -inst ../Benchmarks/SCP-CYC/...For STS
./GenSC -perform_bms 1 -bms_t 150 -subset_score_calculation 2 -united_calculation_mu 70 -solution_initialization_scheme 3 -perform_cc 1 -perform_iscc 0 -perform_tabu 1 -tabu_alpha 3 -reconstruction_scheme 1 -subset_removal_scheme 1 -subset_addition_scheme 3 -perform_alternate_method 4 -update_item_values_scheme 3 -subset_selection_scheme 8 -inst ../Benchmarks/STS/...For SoftTest-S
./GenSC -perform_bms 0 -subset_score_calculation 2 -united_calculation_mu 11 -solution_initialization_scheme 1 -perform_cc 0 -perform_iscc 0 -perform_tabu 1 -tabu_alpha 30 -reconstruction_scheme 1 -subset_removal_scheme 1 -subset_addition_scheme 3 -perform_alternate_method 1 -update_item_values_scheme 3 -subset_selection_scheme 7 -inst ../Benchmarks/SoftTest-S/...For SoftTest-M
./GenSC -perform_bms 1 -bms_t 800 -subset_score_calculation 2 -united_calculation_mu 4 -solution_initialization_scheme 4 -perform_cc 0 -perform_iscc 0 -perform_tabu 1 -tabu_alpha 100 -reconstruction_scheme 2 -subset_removal_scheme 2 -SAinitN 4 -SAt 30000 -subset_addition_scheme 3 -perform_alternate_method 2 -update_item_values_scheme 3 -subset_selection_scheme 9 -inst ../Benchmarks/SoftTest-M/...For SoftTest-L
./GenSC -perform_bms 1 -bms_t 300 -subset_score_calculation 2 -united_calculation_mu 15 -solution_initialization_scheme 1 -perform_cc 0 -perform_iscc 0 -perform_tabu 1 -tabu_alpha 10 -reconstruction_scheme 2 -subset_removal_scheme 1 -subset_addition_scheme 3 -perform_alternate_method 2 -update_item_values_scheme 3 -subset_selection_scheme 9 -inst ../Benchmarks/SoftTest-L/...
- To run GenSC with custom configurations:
run
./GenSC -auto 0 ...
Note that -auto 0 is required
- The output file of GenSC consist of lines starting with 'c', 'o' and 'v', 'c' for comments, 'o' for output and 'v' for detailed solution. A typical output (with default parameters) may look like:
c
c GenSC -- A Novel and General Local Search Framework for Set Covering Problem (SCP)
c Version: 1.0
c
c best_weight best_time best_step
o 181 0.14 10
o 180 0.21 15
c total step: 20
c set_cover_weight: 180 run_time: 0.21 best_step: 15
c detailed_set_cover:
v 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 ......
- As labeled in the output, the three numbers in a line starting with 'o' are: the best weight found, the time of finding the best weight in seconds, the step of finding the best weight.
- At last GenSC outputs a summary of steps, weight and runtime then a line starting with 'v' containing specific results.
The output format can be customized using parameters -print_sol, -print_step and -formatted_print.
-print_sol
determines whether to print the detailed solution (the line starting with 'v'). Select 0 to disable.
-print_step
determines whether to print the information related to steps (best_step and total step). Select 0 to disable.
-formatted_print
determines whether to print as above (selecting 1), or GenSC will print simply as follows (selecting 0).c c GenSC -- A Novel and General Local Search Framework for Set Covering Problem (SCP) c Version: 1.0 c o 181 o 180 c total step: 20 c set_cover_weight: 180 run_time: 0.21 best_step: 15 c detailed_set_cover: v 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 ......