Mixed Integer Programming in R with the ompr package

December 19, 2016
By

(This article was first published on Revolutions, and kindly contributed to R-bloggers)

Numerical optimization is an important tool in the data scientist's toolbox. Many classical statistical problems boil down to finding the highest (or lowest) point on a multi-dimensional surface: the base R function optim provides many techniques for solving such maximum likelihood problems.

Counterintuitively, numerical optimizations are easiest (though rarely actually easy) when all of the variables are continuous and can take any value. When integer variables enter the mix, optimization becomes much, much harder. This typically happens when the optimization is constrained by a limited selection of objects, for example packages in a weight-limited cargo shipment, or stocks in a portfolio constrained by sector weightings and transaction costs. For tasks like these, you often need an algorithm for a specialized type of optimization: Mixed Integer Programming.

For problems like these, Dirk Schumacher has created the ompr package for R. This package provides a convenient syntax for describing the variables and contraints in an optimization problem. For example, take the classic "knapsack" problem of maximizing the total value of objects in a container subject to its maximum weight limit. In mathematical form, the problem can be described as an objective (quantity to be maximized) and a constraint:

$$
\begin{equation*}
\begin{array}{[email protected]{}ll}
\text{max} & \displaystyle\sum\limits_{i=1}^{n} v_{i}x_{i} & &\\
\text{subject to}& \displaystyle\sum\limits_{i=1}^{n} w_{i}x_{i} \leq W, & &\\
& x_{i} \in \{0,1\}, &i=1 ,\ldots, n&
\end{array}
\end{equation*}
$$

In ompr, the same problem is naturally expressed in R as follows:

model <- MIPModel() %>% 
  add_variable(x[i], i = 1:n, type = "binary") %>% 
  set_objective(sum_expr(v[i] * x[i], i = 1:n)) %>% 
  add_constraint(sum_expr(w[i] * x[i], i = 1:n) <= W)

To actually solve the problem, you need to provide a "backend" solver algorithm to ompr. It's designed to integrate with any solver, and currently works with the ROI (R Optimization Infrastructure) package. ROI in turn provides a number of solver algorithms including GLPK, the GNU Linear Programming Kit, which you can use to solve problems like this.

Dirk provides a number of worked examples of the ompr package in use. Examples include the Traveling Salesman problem, solving Soduku puzzles, and selecting optimal warehouse locations to minimize delivery costs to customers.

Warehouses

The ompr package is available on Github. For more information, check out the ompr home page linked below.

Dirk Schumacher: ompr: Mathematical Programming in R

To leave a comment for the author, please follow the link and comment on their blog: Revolutions.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.

Search R-bloggers


Sponsors

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)