Mixed integer linear programming in R

R build status CRAN Status Codecov test coverage

OMPR (Optimization Modeling Package) is a DSL to model and solve Mixed Integer Linear Programs. It is inspired by the excellent Jump project in Julia.

Here are some problems you could solve with this package:

The Wikipedia article gives a good starting point if you would like to learn more about the topic.

I am always happy to get bug reports or feedback.

Install

CRAN

install.packages("ompr")
install.packages("ompr.roi")

Development version

To install the current development version use devtools:

remotes::install_github("dirkschumacher/ompr")
remotes::install_github("dirkschumacher/ompr.roi")

Available solver bindings

A simple example:

suppressPackageStartupMessages(library(dplyr, quietly = TRUE)) 
suppressPackageStartupMessages(library(ROI))
library(ROI.plugin.glpk)
library(ompr)
library(ompr.roi)

result <- MIPModel() |>
  add_variable(x, type = "integer") |>
  add_variable(y, type = "continuous", lb = 0) |>
  set_bounds(x, lb = 0) |>
  set_objective(x + y, "max") |>
  add_constraint(x + y <= 11.25) |>
  solve_model(with_ROI(solver = "glpk"))
get_solution(result, x)
#>  x 
#> 11
get_solution(result, y)
#>    y 
#> 0.25

API

These functions currently form the public API. More detailed docs can be found in the package function docs or on the website

DSL

Backends

There are currently two backends. A backend is the function that initializes an empty model.

Solvers

Solvers are in different packages. ompr.ROI uses the ROI package which offers support for all kinds of solvers.

Further Examples

Please take a look at the docs for bigger examples.

Knapsack

max_capacity <- 5
n <- 10
set.seed(1234)
weights <- runif(n, max = max_capacity)
MIPModel() |>
  add_variable(x[i], i = 1:n, type = "binary") |>
  set_objective(sum_over(weights[i] * x[i], i = 1:n), "max") |>
  add_constraint(sum_over(weights[i] * x[i], i = 1:n) <= max_capacity) |>
  solve_model(with_ROI(solver = "glpk")) |>
  get_solution(x[i]) |>
  filter(value > 0)
#>   variable i value
#> 1        x 1     1
#> 2        x 6     1
#> 3        x 7     1
#> 4        x 8     1

Bin Packing

An example of a more difficult model solved by GLPK

max_bins <- 10
bin_size <- 3
n <- 10
weights <- runif(n, max = bin_size)
MIPModel() |>
  add_variable(y[i], i = 1:max_bins, type = "binary") |>
  add_variable(x[i, j], i = 1:max_bins, j = 1:n, type = "binary") |>
  set_objective(sum_over(y[i], i = 1:max_bins), "min") |>
  add_constraint(sum_over(weights[j] * x[i, j], j = 1:n) <= y[i] * bin_size, i = 1:max_bins) |>
  add_constraint(sum_over(x[i, j], i = 1:max_bins) == 1, j = 1:n) |>
  solve_model(with_ROI(solver = "glpk", verbose = TRUE)) |>
  get_solution(x[i, j]) |>
  filter(value > 0) |>
  arrange(i)
#> <SOLVER MSG>  ----
#> GLPK Simplex Optimizer, v4.65
#> 20 rows, 110 columns, 210 non-zeros
#>       0: obj =   0.000000000e+00 inf =   1.000e+01 (10)
#>      29: obj =   4.546337429e+00 inf =   0.000e+00 (0)
#> *    34: obj =   4.546337429e+00 inf =   0.000e+00 (0)
#> OPTIMAL LP SOLUTION FOUND
#> GLPK Integer Optimizer, v4.65
#> 20 rows, 110 columns, 210 non-zeros
#> 110 integer variables, all of which are binary
#> Integer optimization begins...
#> Long-step dual simplex will be used
#> +    34: mip =     not found yet >=              -inf        (1; 0)
#> +    62: >>>>>   5.000000000e+00 >=   5.000000000e+00   0.0% (13; 0)
#> +    62: mip =   5.000000000e+00 >=     tree is empty   0.0% (0; 25)
#> INTEGER OPTIMAL SOLUTION FOUND
#> <!SOLVER MSG> ----
#>    variable  i  j value
#> 1         x  1  2     1
#> 2         x  1  9     1
#> 3         x  1 10     1
#> 4         x  2  5     1
#> 5         x  2  7     1
#> 6         x  2  8     1
#> 7         x  3  6     1
#> 8         x  4  4     1
#> 9         x 10  1     1
#> 10        x 10  3     1

License

MIT

Contributing

Please post an issue first before sending a PR.

Please note that this project is released with a Contributor Code of Conduct. By participating in this project you agree to abide by its terms.