Model and Solve Mixed Integer Programs • ompr

OMPR (Optimization Modelling 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.

This is a beta version. Currently working towards a first stable version for CRAN. At the moment not recommended for production systems / important analyses. Although most obvious bugs should be gone. Happy to get bug reports or feedback.

Supported problem classes

Objective types

Linear

Constraint types

Linear

Variable types

Continuous
Integer-valued

Install

To install the current development version use devtools:

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

Available solver bindings

Package	Description	Build Linux	Build Windows	Test coverage
ompr.roi	Bindings to ROI (GLPK, Symphony, CPLEX etc.)

A simple example:

library(dplyr)
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

DSL

MIPModel() create an empty mixed integer linear model
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 solution of a solved model for a given variable or group of variables

Solver

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

library(dplyr)
library(ROI)
library(ROI.plugin.glpk)
library(ompr)
library(ompr.roi)
max_capacity <- 5
n <- 10
weights <- runif(n, max = max_capacity)
MIPModel() %>%
  add_variable(x[i], i = 1:n, type = "binary") %>%
  set_objective(sum_expr(weights[i] * x[i], i = 1:n), "max") %>%
  add_constraint(sum_expr(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 symphony.

library(dplyr)
library(ROI)
library(ROI.plugin.symphony)
library(ompr)
library(ompr.roi)
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_expr(y[i], i = 1:max_bins), "min") %>%
  add_constraint(sum_expr(weights[j] * x[i, j], j = 1:n) <= y[i] * bin_size, i = 1:max_bins) %>%
  add_constraint(sum_expr(x[i, j], i = 1:max_bins) == 1, j = 1:n) %>%
  solve_model(with_ROI(solver = "symphony", verbosity = 1)) %>% 
  get_solution(x[i, j]) %>%
  filter(value > 0) %>%
  arrange(i)