Skip to content

Latest commit

 

History

History
176 lines (149 loc) · 13.1 KB

output.md

File metadata and controls

176 lines (149 loc) · 13.1 KB

Output

NOTE: although the final acronym chosen for the problem is 'SCP-CS', the code has been developed when the chosen acronym was 'SCCS' and it has not been changed due to practical reasons; therefore, in this codebase 'SCCS' must be intended as a synonym of 'SCP-CS'.

Result files

A folder named output/ is created in the top level folder when the program is run for the first time. The output/ folder contains two subfolders:

  • results/: contains two to three csv files for each execution, named following the pattern results_<START_DATETIME>(|_grasp|_gurobi).csv. Each row in these csv files gathers information related to the execution and the outcome of one action among SCCS_BIN, SCCS_MIP and SCCS_GRASP performed by the program for each data set file provided as input. For more information on the meaning of each column in these csv files see the csv result files section below.

  • logs/: this folder has the same structure as the datasets/ folder. Whenever any action is performed on a given data set file with path datasets/<rel_path>/file_name.txt one or more coresponding log files are created inside the folder logs/<rel_path>/ holding infomation about the execution and the results of that action (in addition to those saved inside the results/ folder). According to the type of action the generated files are the following.

    • SCCS_GRASP:

      • One log file named <INSTANCE_ID>_sccs_grasp_<START_DATETIME>.log that contains a human readable version of the data in the corresponding row of the csv file results/results_<START_DATETIME>_grasp.csv.
      • One json file named <INSTANCE_ID>_sccs_grasp_<START_DATETIME>.json that contains the same data as the corresponding row of the csv file inside results/results_<START_DATETIME>_grasp.json.

    • SCCS_BIN, SCCS_MIP and SCCS_QO:

      • One log file named <INSTANCE_ID>_sccs_(bin|mip)_<START_DATETIME>.log that contains a human readable version of the data in the corresponding row of the csv file results/results_<START_DATETIME>_gurobi.csv plus the complete output generated at runtime by Gurobi.
      • One sol file named <INSTANCE_ID>_sccs_(bin|mip)_<START_DATETIME>.sol generated by Gurobi. This file contains the solution found by Gurobi and its content is described in Gurobi official documentation
      • One json file named <INSTANCE_ID>_sccs_(bin|mip)_<START_DATETIME>.json generated by Gurobi. This file contains information about the solution and its content is described in Gurobi official documentation

Csv result files

  1. Each csv file named results_<START_DATETIME>.csv contains one row for each executed action of type SCCS_BIN, SCCS_MIP, SCCS_QO or SCCS_GRASP and the following columns.

    INSTANCE_ID         : the path of the data set file relative to the `dataset/` folder
ACTION              : either SCCS_BIN, SCCS_MIP, SCCS_QO or SCCS_GRASP
STATUS              : either OPTIMAL, DONE, TIME_LIMIT or RUNTIME_EXCEPTION
CMD_ARGS            : the command that executed this action
CPU_COUNT:          : the maximum number of logical CPU cores that can be used
TIME_LIMIT          : the maximum number of second after which execution is halted (for each instance)

N_ELEMENTS          : number of elements inside the set to cover
N_SUBSETS           : number of subsets available to cover the given set
CONFLICT_THRESHOLD  : two subsets are considered to be in conflict if the cardinality
                    of their intersection is greater than this (integer) value

SUBSETS_COST                       : sum of the costs of all available subsets
NON_ZERO_SUBSET_COSTS_COUNT        : number of subsets with non-zero cost
SUBSET_COSTS_DISTRIB               : a 'k -> v' mapping where 'v' is the number of subsets
                                     with cost 'k'
AGGREGATED_SUBSET_COSTS_DISTRIB    : a '(a,b) -> v' mapping where 'v' is the number of subsets
                                     with cost bigger than or equal to 'a' and lower than 'b'

CONFLICTS_COST                     : sum of all the conflict costs
NON_ZERO_CONFLICT_COSTS_COUNT      : number of conflicts with non-zero cost
CONFLICT_COSTS_DISTRIB             : a 'k -> v' mapping where 'v' is the number of conflicts
                                     with cost 'k'
AGGREGATED_CONFLICT_COSTS_DISTRIB  : a '(a,b) -> v' mapping where 'v' is the number of conflicts
                                     with cost bigger than or equal to 'a' and lower than 'b'
MAX_CONFLICTS                      : the theorical maximum number of conflicts
                                     (i.e., binom(n_subsets, 2))

USER_TIME        : the sum of the user time of all processes spawned by an algorithm
                   (reliable only for the GRASP algorithm)
SYSTEM_TIME      : the sum of the system time of all processes spawned by an algorithm
                   (reliable only for the GRASP algorithm)
READ_TIME        : time taken to load an instance from a data set file
INIT_TIME        : time taken to build the Gurobi model or to build the data structures needed
                   by the GRASP algorithm
TIME_TO_BEST     : the time taken to find the final solution returned by an algorithm
SOLVE_TIME       : the time taken to effectively execute an algorithm (for SCCS_BIN and SCCS_MIP
                   it does not include INIT_TIME and READ_TIME)
TOTAL_TIME       : roughtly equivalent to INIT_TIME + SOLVE_TIME (for internal purposes only)

SOLUTION_VALID                              : True if the pair (SOLUTION, SOLUTION_COST) is
                                              consistent, False otherwise
SOLUTION_COST                               : the cost of the SOLUTION (i.e. the value of the
                                              objective function)
SOLUTION_SUBSETS_COST                       : the sum of the cost of all subsets contained in
                                              the SOLUTION
SOLUTION_NON_ZERO_SUBSET_COSTS_COUNT        : the number of subsets with non-zero cost contained
                                              in the SOLUTION
SOLUTION_SUBSET_COSTS_DISTRIB               : a 'k -> v' mapping where 'v' is the number of
                                              subsets with cost 'k' in the SOLUTION
SOLUTION_AGGREGATED_SUBSET_COSTS_DISTRIB    : a '(a,b) -> v' mapping where 'v' is the number of
                                              subsets in the SOLUTION with cost bigger than or
                                              equal to 'a' and lower than 'b'
SOLUTION_CONFLICTS_COST                     : the sum of all conflict costs contained in the
                                              SOLUTION
SOLUTION_NON_ZERO_CONFLICT_COSTS_COUNT      : the number of conflicts with non-zero cost
                                              contained in the SOLUTION
SOLUTION_CONFLICT_COSTS_DISTRIB             : a 'k -> v' mapping where 'v' is the number of
                                              conflicts with cost 'k' in the SOLUTION
SOLUTION_AGGREGATED_CONFLICT_COSTS_DISTRIB  : a '(a,b) -> v' mapping where 'v' is the number of
                                              conflicts in the SOLUTION with cost bigger than or
                                              equal to 'a' and lower than 'b'
SOLUTION                                    : the list of subset indexes in the best solution

RESULTS_FILE_PATH   : relative path to the csv file containing information about the results of
                    SCCS_BIN, SCCS_MIP and SCCS_GRASP actions
PYTHON_INTERPRETER  : the version of the Python interpreter used to run the program
RUNTIME_EXCEPTION   : any exception thrown during the execution of the current action

  1. Each csv file named results_<START_DATETIME>_grasp.csv contains one row for each executed action of type SCCS_GRASP and all columns listed in point (1.) plus the following.

    WORKER_COUNT               : the number of subprocess used
STAGES                     : either 1 (if less than 3 logical cores are available) or 2 (otherwise)

MAX_CANDIDATES             : the maximum number of candidates used during the first phase of
                             both the first and second stage of the algorithm
ITERATIONS_LIMIT           : the number of iterations after which each subprocess executing the
                             algorithm must stop (unused, for development purpose only)
STALE_ITERATIONS_LIMIT     : the number of consecutive iterations after which the GRASP
                             algorithm halts if the incumbent solution has not been improved
S1_MAX_CANDIDATES          : the maximum number of candidates used during the first phase of the
                             first stage of the algorithm
S1_TIME_LIMIT              : the maximum number of second after which execution of the first
                             stage of the algorithm is halted
S1_ITERATIONS_LIMIT        : the number of iterations after which each subprocess executing the
                             first stage of the algorithm must stop (unused, for development
                             purpose only)
S1_STALE_ITERATIONS_LIMIT  : the number of consecutive iterations after which the first stage of
                             the algorithm halts if the incumbent solution has not been improved
S2_MAX_CANDIDATES          : the maximum number of candidates used during the second phase of
                             the first stage of the algorithm
S2_TIME_LIMIT              : the maximum number of second after which execution of the second
                             stage of the algorithm is halted
S2_ITERATIONS_LIMIT        : the number of iterations after which each subprocess executing the
                             second stage of the algorithm must stop (unused, for development
                             purpose only)
S2_STALE_ITERATIONS_LIMIT  : the number of consecutive iterations after which the second stage
                             of the algorithm halts if the incumbent solution has not been improved

INTER_STAGE_TIME           : interval in seconds between the completion of the first stage by
                             the first worker and the beginning of the second stage

ITERATIONS_COUNT           : the number of iterations performed by the algorithm (the sum of the
                             number of iterations performed in each stage)
P1_SHARED_CACHE_HIT_COUNT  : number of times that the state of the current cover has been
                             retrieved from the shared cache
P1_SHARED_CACHE_MISS_COUNT : number of times that the state of the current cover has not been
                             retrieved from the shared cache (and hence computed)
P2_H0_MOVE_COUNT           : the number of moves of type (h,0) that has been applied
P2_H1_MOVE_COUNT           : the number of moves of type (h,1) that has been applied
P2_1H_MOVE_COUNT           : the number of moves of type (1,h) that has been applied

S1_STATUS                  : the status at the end of the first stage (either DONE or TIME_LIMIT)
S1_SOLUTION                : the list of subset indexes in the best solution found at the end of
                             the first stage
S1_SOLUTION_COST           : the cost of the solution returned at the end of the first stage
                             (i.e. the value of the objective function)
S1_TIME_TO_BEST            : the time taken to find the solution returned at the end of the
                             first stage

S2_STATUS                  : the status at the end of the second stage (either DONE or TIME_LIMIT)
S2_SOLUTION                : the list of subset indexes in the best solution found at the end of
                             the second stage
S2_SOLUTION_COST           : the cost of the solution returned at the end of the second stage
                             (i.e. the value of the objective function)
S2_TIME_TO_BEST            : the time taken to find the solution returned at the end of the
                             second stage

  2. Each csv file named results_<START_DATETIME>_gurobi.csv contains one row for each executed action of type SCCS_BIN or SCCS_MIP and all columns listed in point (1.) plus the following.

    RELAXED                : whether of not the relaxed version of a Gurobi model was solved
SOLUTION_BEST_BOUND    : the best bound (lower bound) found by Gurobi
SOLUTION_SOLUTION_GAP  : the percentual gap between the best bound and the solution found by Gurobi
GUROBI_VERSION         : the version of Gurobi