Keywords: integer programming, linear programming, modelling, optimization
Webpages:
https://github.com/dirkschumacher/ompr Many real world optimization problems, such as the popular traveling salesman problem, can be formulated as a mixed-integer linear program (MILP). The aim of MILP is to optimize a linear objective function, subject to a set of linear constraints. Over the past decades, specialized open-source and commercial solvers have been developed, such as the GNU Linear Programming Kit (GLPK) which can efficiently solve these kinds of problems.
In
R, interfaces to these solvers are mostly matrix oriented. When solving a MILP in
R, you would thus first need to develop your actual model and then translate it into code that constructs a matrix and vectors before passing it to a solver. Especially for more complex models, the
R code might be rather hard to develop and to reason about without additional documentation.
ompr is a domain specific language that lets you model MILPs declaratively using functions like set_objective, add_variable or add_constraint. Together with
magrittr pipes you can build a model just like a
dplyr statement incrementally, without worrying on how to build the matrix and vectors. Furthermore, an
ompr model is independent from specific solvers and a lot of popular solvers can easily be used through the
ROI family of packages (Hornik et al. 2016).
The idea to model mixed-integer programs algebraically is not new in general. Domain specific languages such as GNU MathProg or the JuMP project (Dunning, Huchette, and Lubin 2015) in
Julia implement a similar approach as
ompr and inspired its development. As far as I know, there is one other related
R package,
roml (Vana, Schwendinger, and Hochreiter 2016), that is currently under development and follows a similiar pathway.
The
ompr package is developed and available on GitHub. In addition to the package itself several vignettes and examples exist describing how to model and solve popular optimization problems, such as the traveling salesman problem, the warehouse location problem or solving Sudokus interactively with
shiny.
In this talk I will present the modelling features of
ompr, how the package can be used to solve practical optimization problems and some ideas for future developments.
References Dunning, Iain, Joey Huchette, and Miles Lubin. 2015. “JuMP: A Modeling Language for Mathematical Optimization.”
arXiv:1508.01982 [Math.OC].
http://arxiv.org/abs/1508.01982.
GNU Linear Programming Kit. 2017.
http://www.gnu.org/software/glpk/glpk.html.
Hornik, Kurt, David Meyer, Florian Schwendinger, and Stefan Theussl. 2016.
ROI: R Optimization Infrastructure.
https://CRAN.R-project.org/package=ROI.
Vana, Laura, Florian Schwendinger, and Ronald Hochreiter. 2016.
R Optimization Modeling Language.
https://r-forge.r-project.org/projects/roml/.
