Using column generation in constraint-and-column generation for adjustable robust optimization > JSP
Loading the data
Our results can be found in the results.jsp.csv
file
with the following columns:
- “tag”: a tag always equal to “result” used grep the result line in our execution log file.
- “instance”: the path to the instance.
- “standard_phase_time_limit”: the time limit for the standard phase (i.e., without using CG).
- “master_solver”: the solver used for solving the CCG master problem: STD for standard, i.e., Gurobi, CG for column generation.
- “status”: the final status.
- “reason”: the final status reason.
- “has_large_scaled”: true if the CG phase has been started, false otherwise.
- “n_iterations”: the number of iterations.
- “total_time”: the total time to solve the problem.
- “master_time”: the time spent solving the master problem.
- “adversarial_time”: the time spent solving the adversarial problem.
- “best_bound”: the best bound found.
- “best_obj”: the best feasible point value.
- “relative_gap”: the final relative gap.
- “absolute_gap”: the final absolute gap.
- “adversarial_unexpected_status”: the status of the adversarial problem solver if it is not Optimal.
- “with_heuristic”: true if the CG-based heuristic is used.
- “with_non_optimal_pricing”: always false.
- “n_jobs”: the number of jobs in the instance.
- “Gamma”: the value for the uncertainty budget \(\Gamma\).
- “blank”: this column is left blank.
data = read.csv("results.jsp.csv", header = FALSE)
colnames(data) = c("tag", "instance", "standard_phase_time_limit", "master_solver", "status", "reason", "has_large_scaled", "n_iterations", "total_time", "master_time", "adversarial_time", "best_bound", "best_obj", "relative_gap", "absolute_gap", "adversarial_unexpected_status", "with_heuristic", "with_non_optimal_pricing", "n_jobs", "Gamma", "blank")
We start by removing the “tag” and the “blank” columns.
data = data[, !(names(data) %in% c("tag", "blank"))]
For homogeneity, we fix the total_time of unsolved instances to the time limit.
if (sum(data$total_time > 7200) > 0 ) {
data[data$total_time > 7200,]$total_time = 7200
}
Then, we create a column named “method” which gives a specific name to each method, comprising the approach for solving the CCG master problem, the time limit of the standard phase and a flag indicating if the CG-based heuristic was used.
data$method = paste0(data$master_solver, "_TL", data$standard_phase_time_limit, "_H", data$with_heuristic)
unique(data$method)
## [1] "STD_TLInf_H0" "CG_TL60_H0" "CG_TL60_H1"
data = data[data$method != "STD_TLInf_H1" & data$method != "CG_TL120_H0" & data$method != "CG_TL120_H1",]
Our final data reads.
Empirical Cumulative Distribution Function (ECDF)
We plot the ECDF of computation time over our set of instances for all approaches.
ggplot(data, aes(x = total_time, col = method)) + stat_ecdf(pad = FALSE) +
coord_cartesian(xlim = c(0,7200)) +
theme_minimal()
We export these results in csv to print them in tikz.
data_with_ecdf = data %>%
group_by(method) %>%
arrange(total_time) %>%
mutate(ecdf_value = ecdf(total_time)(total_time)) %>%
ungroup()
for (method in unique(data_with_ecdf$method)) {
output = data_with_ecdf[data_with_ecdf$method == method,]
output = output[,c("total_time", "ecdf_value")]
output$log_total_time = log10(output$total_time)
output = output[output$total_time < 7200,]
write.csv(output, file = paste0(method, ".csv"), row.names = FALSE)
}
Summary table
In this section, we create a table summarizing the main outcome of our computational experiments.
We first focus on the solved instances.
summary_data_lt_7200 <- data %>%
filter(total_time < 7200) %>%
group_by(n_jobs, Gamma, method) %>%
summarize(
avg_total_time = mean(total_time, na.rm = TRUE),
avg_master_time = mean(master_time, na.rm = TRUE),
avg_adversarial_time = mean(adversarial_time, na.rm = TRUE),
avg_n_iterations = mean(n_iterations, na.rm = TRUE),
sum_has_large_scaled = sum(has_large_scaled),
num_lines = n(),
.groups = "drop"
) %>%
ungroup() %>%
arrange(n_jobs, Gamma, method)
Then, we compute averages over the unsolved instances.
summary_data_ge_7200 <- data %>%
filter(total_time >= 7200) %>%
group_by(n_jobs, Gamma, method) %>%
summarize(
avg_n_iterations_unsolved = mean(n_iterations, na.rm = TRUE),
num_lines_unsolved = n()
) %>%
ungroup() %>%
arrange(n_jobs, Gamma, method)
## `summarise()` has grouped output by 'n_jobs', 'Gamma'. You can override using
## the `.groups` argument.
Finally, we merge our results.
transposed_data_lt_7200 <- summary_data_lt_7200 %>%
pivot_wider(names_from = method, values_from = avg_total_time:num_lines)
transposed_data_ge_7200 <- summary_data_ge_7200 %>%
pivot_wider(names_from = method, values_from = avg_n_iterations_unsolved:num_lines_unsolved) %>%
select(-n_jobs, -Gamma)
cbind(
transposed_data_lt_7200,
transposed_data_ge_7200
) %>%
kable() %>%
kable_styling(full_width = FALSE, position = "center")
n_jobs | Gamma | avg_total_time_CG_TL60_H0 | avg_total_time_CG_TL60_H1 | avg_total_time_STD_TLInf_H0 | avg_master_time_CG_TL60_H0 | avg_master_time_CG_TL60_H1 | avg_master_time_STD_TLInf_H0 | avg_adversarial_time_CG_TL60_H0 | avg_adversarial_time_CG_TL60_H1 | avg_adversarial_time_STD_TLInf_H0 | avg_n_iterations_CG_TL60_H0 | avg_n_iterations_CG_TL60_H1 | avg_n_iterations_STD_TLInf_H0 | sum_has_large_scaled_CG_TL60_H0 | sum_has_large_scaled_CG_TL60_H1 | sum_has_large_scaled_STD_TLInf_H0 | num_lines_CG_TL60_H0 | num_lines_CG_TL60_H1 | num_lines_STD_TLInf_H0 | avg_n_iterations_unsolved_CG_TL60_H0 | avg_n_iterations_unsolved_CG_TL60_H1 | avg_n_iterations_unsolved_STD_TLInf_H0 | num_lines_unsolved_CG_TL60_H0 | num_lines_unsolved_CG_TL60_H1 | num_lines_unsolved_STD_TLInf_H0 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
20 | 5 | 66.42400 | 65.27044 | 54.08124 | 64.09609 | 63.02577 | 53.16899 | 2.313212 | 2.230524 | 0.9013816 | 2.923077 | 2.897436 | 2.619718 | 12 | 12 | 0 | 78 | 78 | 71 | 202.5000 | 49.50000 | 6.666667 | 2 | 2 | 9 |
20 | 7 | 46.94752 | 47.12294 | 14.60095 | 44.96908 | 45.13257 | 13.47536 | 1.965655 | 1.977401 | 1.1148425 | 2.772152 | 2.772152 | 2.608108 | 7 | 7 | 0 | 79 | 79 | 74 | 115.0000 | 17.00000 | 6.000000 | 1 | 1 | 6 |
20 | 9 | 90.20025 | 91.33058 | 89.74445 | 88.71775 | 89.83822 | 89.05729 | 1.466528 | 1.476266 | 0.6760224 | 3.038461 | 3.051282 | 2.704225 | 12 | 12 | 0 | 78 | 78 | 71 | 77.5000 | 42.50000 | 7.222222 | 2 | 2 | 9 |
25 | 5 | 400.36587 | 511.59671 | 285.83855 | 386.40725 | 495.86043 | 272.51119 | 13.936068 | 15.711339 | 13.3123444 | 3.123077 | 3.227273 | 2.741379 | 16 | 17 | 0 | 65 | 66 | 58 | 111.9286 | 113.30769 | 6.500000 | 14 | 13 | 20 |
25 | 7 | 450.91390 | 373.72667 | 122.50668 | 357.09050 | 277.75319 | 41.95088 | 93.795642 | 95.947419 | 80.5427899 | 3.328571 | 3.231884 | 2.561403 | 16 | 15 | 0 | 70 | 69 | 57 | 112.0000 | 99.88889 | 6.142857 | 8 | 9 | 21 |
25 | 9 | 430.64829 | 371.89725 | 173.98447 | 379.69323 | 325.43881 | 125.67400 | 50.930327 | 46.435814 | 48.2944896 | 3.253731 | 3.121212 | 2.694915 | 16 | 15 | 0 | 67 | 66 | 59 | 88.4000 | 81.63636 | 6.500000 | 10 | 11 | 18 |
git push
action on the public repository
hlefebvr/hlefebvr.github.io
using rmarkdown and Github
Actions. This ensures the reproducibility of our data manipulation. The
last compilation was performed on the 12/09/24 14:05:52.