• Stars
    star
    259
  • Rank 144,849 (Top 4 %)
  • Language
    R
  • License
    Other
  • Created over 7 years ago
  • Updated 3 months ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

R package to model Mixed Integer Linear Programs

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:

  • 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

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

  • ompr.roi - Bindings to ROI (GLPK, Symphony, CPLEX etc.)

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

  • 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 for more plugins.

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.

Related Projects

  • CVXR - an excellent package for “object-oriented modeling language for convex optimization”. LP/MIP is a special case.
  • ROML follows a similar approach, but it seems the package is still under initial development.

More Repositories

1

llr

Lisp-like-R: A clojure inspired lisp that compiles to R in R
R
189
star
2

encryptedRmd

🔑 Password protected markdown html reports in R using libsodium
HTML
167
star
3

r-shiny-electron

WIP: Electron and R shiny
JavaScript
103
star
4

armacmp

🚀 Automatically compile linear algebra R code to C++ with Armadillo
R
92
star
5

wasmr

Execute WebAssembly from R using wasmer
C++
74
star
6

thankr

Find out who maintains the R packages you use and say 'thank you'
R
62
star
7

duckduckr

🦆🦆🚶 DuckDuckGo's Instant Answer API for R
R
43
star
8

awesome-r-organizations

A community curated list of awesome companies/organizations that contribute open source R software/packages
43
star
9

defmacro

Load Time R Package Macros
R
34
star
10

logician

🖖 Prolog-style Logic Programming in pure R
R
32
star
11

transduceR

transducers in R
R
31
star
12

r-orms

R for Operations Research
HTML
30
star
13

TransitmapSolver.jl

Generate transitmaps automatically using mixed integer programming
Julia
24
star
14

htmlvault

Encrypt files in self-decrypting html files using libsodium
HTML
19
star
15

r-sudoku

Solve Sudokus with R, GLPK, shiny and ompr
R
19
star
16

learnsqlr

Learn SQL using R and duckdb
R
18
star
17

listcomp

List comprehensions in R
R
18
star
18

rcbc

COIN-OR branch and cut (CBC) bindings for R
R
18
star
19

PValueAdjust.jl

[deprecated] P-value adjustment methods for multiple testing correction
Julia
16
star
20

rcompilertools

Compiler Tools for R's bytecode compiler
R
15
star
21

armacmp-shiny

A small shiny app to transpile R to C++
R
14
star
22

blake3

BLAKE3 Cryptographic Hash Function in R
R
13
star
23

rhxl

Humanitarian Exchange Language (HXL standard) in R
R
11
star
24

torchoptim

A bit like 'stats::optim', but with torch
R
10
star
25

polyglotr

Use C, Rust, Go and Assemblyscript in an R package through WebAssembly
R
10
star
26

RBerlinData

Open data for Berlin in R [project is abandoned]
R
9
star
27

or-companies

List of companies that hire developers particular to work on combinatorial (optimization) problems
9
star
28

genossenschaften

List of German Wohnungsbaugenossenschaften (Housing cooperatives)
8
star
29

repint

ALTREP example of rep.int
C
8
star
30

nodepicosat

SAT solver PicoSAT for javascript
JavaScript
8
star
31

etherscanr

Etherscan.io api client for R (work in progress)
R
8
star
32

ompr.roi

ROI bindings for OMPR
R
8
star
33

armacmp-examples

Examples of algorithms automatically compiled from R to C++
R
8
star
34

covid-19-indicators

Epidemiological Indicators (CFR, incubation period, serial interval) for COVID-19
7
star
35

votingpower.r

Measure voting power in R
R
7
star
36

encryptedCredentials

Small, opinionated package to manage encrypted credentials in R
R
7
star
37

shiny-tsp

Traveling salesperson problem with shiny
R
6
star
38

ROI.plugin.cbc

ROI plugin for COIN-OR branch and cut (CBC) solver
R
6
star
39

rpicosat

PicoSAT bindings for R
R
6
star
40

rcppglm

GLM implementation in c++ with rcpp and armadillo
C++
5
star
41

blume_messnet_api

Blume Messnet API
Ruby
5
star
42

coreml

WIP and proof of concept: convert R models to coreml and back
R
5
star
43

iUPB

A popular app for the University of Paderborn, Germany [project is dead]
Ruby
4
star
44

notail

Experimental and simple tail-call optimisation for R functions
R
4
star
45

optplot

An R package for plotting optimization problems/models
R
4
star
46

defmacroex

An Example of defmacro
R
4
star
47

blume_crawler

A rake task to regularly download and save particulates statistics in Berlin
Ruby
4
star
48

dirichlet-rating

Uncertainty intervals around star based ratings in javascript
JavaScript
4
star
49

ndarray-linear-regression

Linear regression (with QR decomposition) with ndarrays
JavaScript
4
star
50

hellozig

Zig and R
C
3
star
51

covid-api

COVID-19 cases in Germany
R
3
star
52

geopattern

HTML widget for the geopattern javascript library
R
3
star
53

ContentSecurityPolicy

Content Security Policies for Shiny Apps
R
3
star
54

tfjs-glm

Generalized linear models in tensorflow.js (WIP)
JavaScript
3
star
55

cyclehack-crowd-estimation

3
star
56

lyft_incentive_allocation

An implementation of the lyft incentive allocation problem in R
R
3
star
57

lazyseq

Lazy R list that evaluate elements only when needed
R
2
star
58

recon-sitrep-generator

Just a proof of concept
R
2
star
59

r-orms-idealist

A project wishlist for Operations Research in R
2
star
60

LineFlowSolver.jl

Solve the line flow problem
Julia
2
star
61

ompr.highs

HiGHS solver bindings for {ompr}
R
2
star
62

berlin-air-quality

2
star
63

RcppBrainfuck

Compile Brainfuck to C++ from R
R
2
star
64

losep

An R package to detect seperation in binary classification models using linear programming
R
2
star
65

advent-of-code-2021

In LLR
2
star
66

rs-leastsquare

least squares in rust
Rust
2
star
67

knapsack-cbc-wasm

C++
2
star
68

immerh

Immer C++ Header Files
C++
1
star
69

tfjs-leastsquares

Solve linear least-squares problems in tensorflow.js
JavaScript
1
star
70

rsupport

A machine readable list of R package makers and how to compensate them for their hard work
1
star
71

ompr.glpk

R
1
star
72

ftrljs

FTRL-Proximal online learning algorithm for logistic regression in javascript
JavaScript
1
star
73

mlcombinatorics

machine learning and combinatorics ressources
1
star
74

ompr.symphony

R
1
star
75

elm-ecdf-spa

A toy elm app to showcase the elm-ecdf package
Elm
1
star
76

multi-way-number-partitioning-problem

Integer programming for the multi way number partitioning problem (WIP)
1
star
77

ompr.docs

documentation website for the R ompr package
HTML
1
star
78

ftrl

Dense FTRL-Proximal online learning algorithm for logistic regression in R
R
1
star
79

aoc2020

AoC2020 using llr (lisp like R)
1
star
80

llr-shiny

Just a small test writing a shiny app using llr
Clojure
1
star