ompr

R package to model Mixed Integer Linear Programs

https://github.com/dirkschumacher/ompr

Keywords

Repository

R package to model Mixed Integer Linear Programs

README.Rmd

---
output: github_document
---



```{r, include = FALSE}
knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>",
  fig.path = "man/figures/README-",
  out.width = "100%"
)
```

# Mixed integer linear programming in R


[![R build status](https://github.com/dirkschumacher/ompr/workflows/R-CMD-check/badge.svg)](https://github.com/dirkschumacher/ompr/actions)
[![CRAN Status](https://www.r-pkg.org/badges/version/ompr)](https://cran.r-project.org/package=ompr)
[![Codecov test coverage](https://codecov.io/gh/dirkschumacher/ompr/branch/master/graph/badge.svg)](https://app.codecov.io/gh/dirkschumacher/ompr?branch=master)


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:

  * What is the cost minimal way to visit a set of clients and return home afterwards?
  * What is the optimal conference time table subject to certain constraints (e.g. availability of a projector)?
  * [Sudokus](https://github.com/dirkschumacher/r-sudoku)
  
The [Wikipedia](https://en.wikipedia.org/wiki/Integer_programming) 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

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

### Development version

To install the current development version use devtools:

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

## Available solver bindings

* [ompr.roi](https://github.com/dirkschumacher/ompr.roi) - Bindings to ROI (GLPK, Symphony, CPLEX etc.)

## A simple example:

```{r}
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)
get_solution(result, y)
```

## API

These functions currently form the public API. More detailed docs can be found in the package function docs or on the [website](https://dirkschumacher.github.io/ompr/)

### DSL
* `MIPModel()` create an empty mixed integer linear model (the old way)
* `add_variable()` adds variables to a model
* `set_objective()` sets the objective function of a model
* `set_bounds()` sets bounds of variables
* `add_constraint()` add constraints
* `solve_model()` solves a model with a given solver
* `get_solution()` returns the column solution (primal or dual) of a solved model for a given variable or group of variables
* `get_row_duals()` returns the row duals of a solution (only if it is an LP)
* `get_column_duals()` returns the column duals of a solution (only if it is an LP)

### Backends

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

* `MIPModel()` is the standard MILP Model.
* `MILPModel()` is another backend specifically optimized for linear models and is often faster than `MIPModel()`. It has different semantics, as it is vectorized. Currently experimental and might be deprecated in the future.

### Solvers

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

* `with_ROI(solver = "glpk")` solve the model with GLPK. Install `ROI.plugin.glpk`
* `with_ROI(solver = "symphony")` solve the model with Symphony. Install `ROI.plugin.symphony`
* `with_ROI(solver = "cplex")` solve the model with CPLEX. Install `ROI.plugin.cplex`
* ... See the [ROI package](https://CRAN.R-project.org/package=ROI) for more plugins.

 
## Further Examples

Please take a look at the [docs](https://dirkschumacher.github.io/ompr/articles/index.html) for bigger examples.

### Knapsack

```{r}
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)
```

### Bin Packing
An example of a more difficult model solved by GLPK

```{r}
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)
```


## 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.

## Related Projects

* [CVXR](https://cvxr.rbind.io/) - an excellent package for "object-oriented modeling language for convex optimization". LP/MIP is a special case.
* [ROML](https://r-forge.r-project.org/projects/roml/) follows a similar approach, but it seems the package is still under initial development.

Owner

Citation (CITATION.cff)

# -----------------------------------------------------------
# CITATION file created with {cffr} R package, v0.2.1
# See also: https://docs.ropensci.org/cffr/
# -----------------------------------------------------------

cff-version: 1.2.0
message: 'To cite package "ompr" in publications use:'
type: software
license: MIT
title: 'ompr: Model and Solve Mixed Integer Linear Programs'
version: 1.0.2
abstract: Model mixed integer linear programs in an algebraic way directly in R. The
  model is solver-independent and thus offers the possibility to solve a model with
  different solvers. It currently only supports linear constraints and objective functions.
  See the 'ompr' website <https://dirkschumacher.github.io/ompr/> for more information,
  documentation and examples.
authors:
- family-names: Schumacher
  given-names: Dirk
  email: mail@dirk-schumacher.net
preferred-citation:
  type: manual
  title: 'ompr: Model and Solve Mixed Integer Linear Programs'
  authors:
  - family-names: Schumacher
    given-names: Dirk
    email: mail@dirk-schumacher.net
  version: 1.0.2
  abstract: Model mixed integer linear programs in an algebraic way directly in R.
    The model is solver-independent and thus offers the possibility to solve a model
    with different solvers. It currently only supports linear constraints and objective
    functions. See the 'ompr' website <https://dirkschumacher.github.io/ompr/> for
    more information, documentation and examples.
  repository: https://CRAN.R-project.org/package=ompr
  repository-code: https://github.com/dirkschumacher/ompr
  url: https://github.com/dirkschumacher/ompr
  contact:
  - family-names: Schumacher
    given-names: Dirk
    email: mail@dirk-schumacher.net
  keywords:
  - integer-programming
  - linear-programming
  - milp
  - mip
  - optimization
  - r
  license: MIT
  year: '2022'
repository: https://CRAN.R-project.org/package=ompr
repository-code: https://github.com/dirkschumacher/ompr
url: https://github.com/dirkschumacher/ompr
contact:
- family-names: Schumacher
  given-names: Dirk
  email: mail@dirk-schumacher.net
keywords:
- integer-programming
- linear-programming
- milp
- mip
- optimization
- r
references:
- type: software
  title: 'R: A Language and Environment for Statistical Computing'
  notes: Depends
  authors:
  - name: R Core Team
  location:
    name: Vienna, Austria
  year: '2022'
  url: https://www.R-project.org/
  institution:
    name: R Foundation for Statistical Computing
  version: '>= 3.2.0'
- type: software
  title: lazyeval
  abstract: 'lazyeval: Lazy (Non-Standard) Evaluation'
  notes: Imports
  authors:
  - family-names: Wickham
    given-names: Hadley
    email: hadley@rstudio.com
  year: '2022'
  url: https://CRAN.R-project.org/package=lazyeval
- type: software
  title: rlang
  abstract: 'rlang: Functions for Base Types and Core R and ''Tidyverse'' Features'
  notes: Imports
  authors:
  - family-names: Henry
    given-names: Lionel
    email: lionel@rstudio.com
  - family-names: Wickham
    given-names: Hadley
    email: hadley@rstudio.com
  year: '2022'
  url: https://CRAN.R-project.org/package=rlang
  version: '>= 0.2.0'
- type: software
  title: listcomp
  abstract: 'listcomp: List Comprehensions'
  notes: Imports
  authors:
  - family-names: Schumacher
    given-names: Dirk
    email: mail@dirk-schumacher.net
  year: '2022'
  url: https://CRAN.R-project.org/package=listcomp
  version: '>= 0.4.0'
- type: software
  title: methods
  abstract: 'R: A Language and Environment for Statistical Computing'
  notes: Imports
  authors:
  - name: R Core Team
  location:
    name: Vienna, Austria
  year: '2022'
  url: https://www.R-project.org/
  institution:
    name: R Foundation for Statistical Computing
- type: software
  title: data.table
  abstract: 'data.table: Extension of `data.frame`'
  notes: Imports
  authors:
  - family-names: Dowle
    given-names: Matt
    email: mattjdowle@gmail.com
  - family-names: Srinivasan
    given-names: Arun
    email: asrini@pm.me
  year: '2022'
  url: https://CRAN.R-project.org/package=data.table
- type: software
  title: Matrix
  abstract: 'Matrix: Sparse and Dense Matrix Classes and Methods'
  notes: Imports
  authors:
  - family-names: Bates
    given-names: Douglas
  - family-names: Maechler
    given-names: Martin
    email: mmaechler+Matrix@gmail.com
    orcid: https://orcid.org/0000-0002-8685-9910
  year: '2022'
  url: https://CRAN.R-project.org/package=Matrix
- type: software
  title: fastmap
  abstract: 'fastmap: Fast Data Structures'
  notes: Imports
  authors:
  - family-names: Chang
    given-names: Winston
    email: winston@rstudio.com
  year: '2022'
  url: https://CRAN.R-project.org/package=fastmap
- type: software
  title: covr
  abstract: 'covr: Test Coverage for Packages'
  notes: Suggests
  authors:
  - family-names: Hester
    given-names: Jim
    email: james.f.hester@gmail.com
  year: '2022'
  url: https://CRAN.R-project.org/package=covr
- type: software
  title: magrittr
  abstract: 'magrittr: A Forward-Pipe Operator for R'
  notes: Suggests
  authors:
  - family-names: Bache
    given-names: Stefan Milton
    email: stefan@stefanbache.dk
  - family-names: Wickham
    given-names: Hadley
    email: hadley@rstudio.com
  year: '2022'
  url: https://CRAN.R-project.org/package=magrittr
- type: software
  title: testthat
  abstract: 'testthat: Unit Testing for R'
  notes: Suggests
  authors:
  - family-names: Wickham
    given-names: Hadley
    email: hadley@rstudio.com
  year: '2022'
  url: https://CRAN.R-project.org/package=testthat

GitHub Events

Committers

Last synced: 7 months ago

Issues and Pull Requests

Last synced: 5 months ago

Packages