-
Notifications
You must be signed in to change notification settings - Fork 35
/
Copy pathREADME.Rmd
164 lines (120 loc) · 5.55 KB
/
README.Rmd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
---
output: github_document
---
<!-- README.md is generated from README.Rmd. Please edit that file -->
```{r, include = FALSE}
knitr::opts_chunk$set(
collapse = TRUE,
comment = "#>",
fig.path = "man/figures/README-",
out.width = "100%"
)
```
# Mixed integer linear programming in R
<!-- badges: start -->
[](https://github.com/dirkschumacher/ompr/actions)
[](https://cran.r-project.org/package=ompr)
[](https://app.codecov.io/gh/dirkschumacher/ompr?branch=master)
<!-- badges: end -->
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.