In this article, we take the Knapsack problem from before and model it using the matrix based interface in ROI. ROI is short for the R Optimization Infrastructure and is an excellent family of packages to solve a variaty of optimization problems, including MILPs.
\[ \begin{equation*} \begin{array}{ll@{}ll} \text{max} & \displaystyle\sum\limits_{i=1}^{n} v_{i}x_{i} & &\\ \text{subject to}& \displaystyle\sum\limits_{i=1}^{n} w_{i}x_{i} \leq W, & &\\ & x_{i} \in \{0,1\}, &i=1 ,\ldots, n& \end{array} \end{equation*} \]
A first step is of course to load the package and define some model parameters:
library(ROI)## ROI.plugin.glpk: R Optimization Infrastructure## Registered solver plugins: nlminb, cbc, glpk.## Default solver: auto.n <- 10
W <- 2
v <- runif(n)
w <- runif(n)Here v and w are vectors of the length n that can be directly passed to ROI.
Let’s build the constraint first. As the Knapsack problem only has one constraint (i.e. one row in the constraint matrix), this step is rather simple:
constraints <- L_constraint(w, "<=", W)Then we define an optimization model:
model <- OP(objective = v,
constraints = constraints,
bounds = V_bound(li = 1:n, lb = rep.int(0, n), ui = 1:n, ub = rep.int(1, n)),
types = rep.int("B", n),
maximum = TRUE)
model## ROI Optimization Problem:
##
## Maximize a linear objective function of length 10 with
## - 10 binary objective variables,
##
## subject to
## - 1 constraint of type linear.
## - 0 lower and 10 upper non-standard variable bounds.The parameters of OP are self-explaining: we create an optimization problem with the objective coefficient vector v and our constraint from above. We further define variable bounds for all \(0 \leq x_i\leq 1\) and set the type to “B”, meaning they are binary variables.
Having now formulated our problem, we can pass it to one of the many available solvers. In this case we use GLPK.
library(ROI.plugin.glpk)
res <- ROI_solve(model, "glpk", verbose = TRUE)## <SOLVER MSG> ----
## GLPK Simplex Optimizer, v4.65
## 1 row, 10 columns, 10 non-zeros
## * 0: obj = -0.000000000e+00 inf = 0.000e+00 (10)
## * 8: obj = 5.141899448e+00 inf = 0.000e+00 (0)
## OPTIMAL LP SOLUTION FOUND
## GLPK Integer Optimizer, v4.65
## 1 row, 10 columns, 10 non-zeros
## 10 integer variables, all of which are binary
## Integer optimization begins...
## Long-step dual simplex will be used
## + 8: mip = not found yet <= +inf (1; 0)
## Solution found by heuristic: 4.99495245353
## + 9: mip = 4.994952454e+00 <= tree is empty 0.0% (0; 1)
## INTEGER OPTIMAL SOLUTION FOUND
## <!SOLVER MSG> ----res## Optimal solution found.
## The objective value is: 4.994952e+00ROI provides function to access the optimal solution (i.e. the concrete values of all \(x_i\)). A \(1\) means, we put the object into our knapsack, a \(0\) means the opposite.
ROI::solution(res)## [1] 1 1 0 1 1 1 0 0 1 1And we are done: we solved the knapsack problem using GLPK and ROI.