The rcbc package provides an interface to the
CBC (COIN-OR branchand cut)
solver (Forrest & Lougee-Heimer 2005). Specifically, CBC is an
open-source mixed integer programming solver that is developed as part of
the Computational Infrastructure for Operations Research (COIN-OR) project.
By interfacing with the CBC solver, the rcbc package can be
used to generate optimal solutions to optimization problems (using the
cbc_solve function).
Forrest J and Lougee-Heimer R (2005) CBC User Guide. In Emerging theory, Methods, and Applications (pp. 257--277). INFORMS, Catonsville, MD. doi:10.1287/educ.1053.0020 .
# \dontrun{
# Mathematically define a mixed integer programming problem
## maximize:
## 1 * x + 2 * y + 0.5 * z (eqn 1a)
## subject to:
## x + y <= 1 (eqn 1b)
## 3 * x + 4 * z >= 5 (eqn 1c)
## z = 4 (eqn 1d)
## 0 <= x <= 10 (eqn 1e)
## 0 <= y <= 11 (eqn 1f)
## 0 <= z <= 13 (eqn 1g)
## x, y, z is integer (eqn 1h)
# Create variables to represent this problem
### define objective function (eqn 1a)
obj <- c(1, 2, 0.5)
## define constraint matrix (eqns 1c--1d)
A <- matrix(c(1, 1, 0, 3, 0, 4, 0, 0, 1), byrow = TRUE, nrow = 3)
print(A)
#> [,1] [,2] [,3]
#> [1,] 1 1 0
#> [2,] 3 0 4
#> [3,] 0 0 1
## note that we could also define the constraint matrix using a
## sparse format to reduce memory consumption
## (though not needed for such a small problem)
library(Matrix)
A_sp <- sparseMatrix(
i = c(1, 2, 1, 2, 3),
j = c(1, 1, 2, 3, 3),
x = c(1, 3, 1, 4, 1))
print(A_sp)
#> 3 x 3 sparse Matrix of class "dgCMatrix"
#>
#> [1,] 1 1 .
#> [2,] 3 . 4
#> [3,] . . 1
## define upper and lower bounds for constraints (eqns 1c--1d)
row_ub <- c(1, Inf, 4)
row_lb <- c(-Inf, 5, 4)
## define upper and lower bounds for decision variables (eqns 1e--1g)
col_ub <- c(10, 11, 13)
col_lb <- c(0, 0, 0)
## specify which decision variables are integer (eqn 1h)
is_integer <- c(TRUE, TRUE, TRUE)
# Generate solution
## run solver (with default settings)
result <- cbc_solve(
obj = obj, mat = A, is_integer = is_integer,
row_lb = row_lb, row_ub = row_ub,
col_lb = col_lb, col_ub = col_ub,
max = TRUE)
## print result
print(result)
#> $column_solution
#> [1] 0 1 4
#>
#> $objective_value
#> [1] 4
#>
#> $is_proven_optimal
#> [1] TRUE
#>
#> $is_proven_dual_infeasible
#> [1] FALSE
#>
#> $is_proven_infeasible
#> [1] FALSE
#>
#> $is_node_limit_reached
#> [1] FALSE
#>
#> $is_solution_limit_reached
#> [1] FALSE
#>
#> $is_abandoned
#> [1] FALSE
#>
#> $is_iteration_limit_reached
#> [1] FALSE
#>
#> $is_seconds_limit_reached
#> [1] FALSE
#>
#> attr(,"class")
#> [1] "rcbc_milp_result"
## extract information from result
objective_value(result) # objective value of solution
#> [1] 4
column_solution(result) # decision variable values in solution
#> [1] 0 1 4
solution_status(result) # status description
#> [1] "optimal"
# Generate a solution with customized settings
## specify that only a single thread should be used,
## we only need a solution within 20% of optimality,
## and that we can only 2 (wall clock) seconds for the solution
cbc_args <- list(threads = "1", ratio = "0.2", sec = "2", timem = "elapsed")
## run solver (with customized settings)
result2 <- cbc_solve(
obj = obj, mat = A, is_integer = is_integer,
row_lb = row_lb, row_ub = row_ub,
col_lb = col_lb, col_ub = col_ub,
max = TRUE, cbc_args = cbc_args)
## print result
## we can see that this result is exactly the same as the previous
## result, so these customized settings did not really any influence.
## this is because the optimization problem is incredibly simple
## and so \emph{CBC} can find the optimal solution pretty much instantly
## we would expect such customized settings to have an influence
## when solving more complex problems
print(result2)
#> $column_solution
#> [1] 0 1 4
#>
#> $objective_value
#> [1] 4
#>
#> $is_proven_optimal
#> [1] TRUE
#>
#> $is_proven_dual_infeasible
#> [1] FALSE
#>
#> $is_proven_infeasible
#> [1] FALSE
#>
#> $is_node_limit_reached
#> [1] FALSE
#>
#> $is_solution_limit_reached
#> [1] FALSE
#>
#> $is_abandoned
#> [1] FALSE
#>
#> $is_iteration_limit_reached
#> [1] FALSE
#>
#> $is_seconds_limit_reached
#> [1] FALSE
#>
#> attr(,"class")
#> [1] "rcbc_milp_result"
# }