Solve a mixed integer problem with CBC

CBC (COIN-OR branch and cut) is an open-source mixed integer programming solver (Forrest & Lougee-Heimer 2005). It is developed as part of the Computational Infrastructure for Operations Research (COIN-OR) project. By leveraging the CBC solver, this function can be used to generate solutions to optimization problems.

cbc_solve(
  obj,
  mat,
  row_ub = rep.int(Inf, nrow(mat)),
  row_lb = rep.int(-Inf, nrow(mat)),
  col_lb = rep.int(-Inf, ncol(mat)),
  col_ub = rep.int(Inf, ncol(mat)),
  is_integer = rep.int(FALSE, ncol(mat)),
  max = FALSE,
  cbc_args = list(),
  initial_solution = NULL
)

Arguments

obj: numeric vector if coefficients to specify the objective function. Note that arguments should have one value per decision variable (i.e. column in mat).
mat: matrix (i.e. matrix or Matrix-class) of constraint coefficients. Here, each column corresponds to a different decision variable, and each row corresponds to a different constraint. To improve performance, it is recommended to specify the matrix using a sparse format (see sparseMatrix).
row_ub: numeric vector of upper bounds for constraints. Note that arguments should have one value per constraint (i.e. row in mat). Defaults to a vector of infinity (Inf) values for each constraint.
row_lb: numeric vector of lower bounds for constraints. Note that arguments should have one value per constraint (i.e. row in mat). Defaults to a vector of negative infinity (-Inf) values for each constraint.
col_lb: numeric vector of lower bounds for decision variables. Note that arguments should have one value per decision variable (i.e. column in mat). Defaults to a vector of negative infinity (-Inf) values for each variable.
col_ub: numeric vector of upper bounds for decision variables. Note that arguments should have one value per decision variable (i.e. column in mat). Defaults to a vector of infinity (Inf) values for each variable.
is_integer: logical vector indicating if (TRUE) each decision variable is integer or (FALSE) not an integer. Note that arguments should have one value per decision variable (i.e. column in mat). Defaults to a vector of FALSE values for each variable (meaning that all variables are continuous).
max: logical (i.e. TRUE or FALSE) should the solver aim to maximize the objective function? Defaults to FALSE.
cbc_args: list of character CBC arguments to customize the optimization procedures (see CBC parameters section for details). Defaults to list(), such that default settings are used to generate solutions. Note that all arguments must be supplied as a character object (see below for examples).
initial_solution: numeric initial values for starting solution. Missing (NA) values can be used to indicate that the starting value for a solution should be automatically calculated. Note that only initial values for integer variables (per argument to is_integer) are actually used to generate solutions. This is due to the behavior of the CBC solver. Defaults to NULL such that the starting solution is automatically generated.

Value

A list containing the solution and additional information. Specifically, it contains the following elements:

column_solution: numeric values of the decision variables in the solution (same order as columns in the constraint matrix).
objective_value: numeric objective value of the solution.
status: character description of the optimization process when it finished. This description is based on the result of the following elements. For example, an "optimal" status indicates that the optimization process finished because it found an optimal solution. Also, if a maximum time limit was specified (using cbc_args), an "timelimit" status indicates that the optimization process finished because it ran out of time. Furthermore, an "infeasible" status indicates that there is no possible solution to the specified optimization problem. This "infeasible" status could potentially mean that there was a mistake when constructing the input data.
is_proven_optimal: logical indicating if the solution proven to be optimal.
is_proven_dual_infeasible: logical indicating if the dual is proven to be infeasible.
is_proven_infeasible: logical indicating if the optimization problem is proven to be infeasible.
is_node_limit_reached: logical indicating if the maximum number of nodes permitted for solving the optimization problem was reached.
is_solution_limit_reached: logical indicating if the maximum number of solutions (including those generated before finding the final solution) permitted for solving the optimization problem was reached.
is_abandoned: logical indicating if the optimization process was abandoned part way through solving the optimization problem.
is_iteration_limit_reached: logical indicating if the maximum number of iterations permitted for solving the optimization problem was reached.
is_seconds_limit_reached: logical indicating if the maximum number of seconds permitted for for solving the optimization problem was reached.

CBC parameters

Many different parameters can be specified to customize the optimization process (see the user manual full list). Among all these parameters, some of the most useful parameters include the following:

log: Should information be printed during the solve process? Defaults to "1" meaning that information will be printed to the console. To prevent this, a value of "0" can be specified.
verbose: The level of detail to provide when printing information to the console. Defaults to "1" for a relatively small amount of detail. For maximum detail, a value of "15" can be specified.
presolve: Should the optimization process include a pre-processing step that attempts to simplify the optimization problem? Defaults to "On" such that this pre-processing step is performed. To disable this step, a value of "Off" can be specified.
ratio: Optimality gap for solving the problem. The optimization process will stop when the performance of the best found solution is near enough to optimality based on this parameter. For example, a value of 0.15 means that the optimization process will stop when the best found solution is within 15 Defaults to "0", such that only an optimal solution is returned.
sec: Maximum amount of time permitted for completing the optimization process. Defaults to "1e+100". Note that time is measured based on the TIMEM parameter.
timem: Method to measure time. Defaults to "cpu" such that timing is measured using CPU time. To specify that time should be measured based on overall time elapsed (e.g. based on a wall clock), a value of "elapsed" can be specified.
threads: Number of threads to use for solving the optimization problem. For example, a value of "4" indicates that four threads should be used. Defaults to "0", such that the number of threads is automatically determined.
maxso: Maximum number of solutions permitted to examine during the optimization process. For example, a value of "1" can be used to obtain the first feasible solution.

References

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 .

Examples

# \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"
# }