<p><div><div><div><div data-width="100" data-show-faces="false" data-send="true" data-layout="button_count" data-height="21" data-href="https://www.r-bloggers.com/mixed-integer-programming-in-r-with-the-ompr-package/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="http://blog.revolutionanalytics.com/2016/12/mixed-integer-programming-in-r-with-the-ompr-package.html"> Revolutions</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<div>
<p>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 <a target="_blank" rel="nofollow" href="https://www.rdocumentation.org/packages/stats/versions/3.3.1/topics/optimhttps://www.rdocumentation.org/packages/stats/versions/3.3.1/topics/optim">optim</a> provides many techniques for solving such <a target="_blank" rel="nofollow" href="http://blog.revolutionanalytics.com/2014/01/large-scale-optimization-with-optim-and-revoscaler.html">maximum likelihood problems</a>.</p>
<p>Counterintuitively, numerical optimizations are easiest (though rarely actually <em>easy</em>) when all of the variables are continuous and can take any value. When integer variables enter the mix, optimization becomes much, <em>much</em> harder. This typically happens when the optimization is constrained by a limited selection of objects, for example <a target="_blank" rel="nofollow" href="http://blog.revolutionanalytics.com/2012/07/using-integer-programming-in-r-to-optimize-cargo-loads.html">packages in a weight-limited cargo shipment</a>, or <a target="_blank" rel="nofollow" href="http://blog.revolutionanalytics.com/2009/01/portfolio-optimization-in-r.html">stocks in a portfolio</a> constrained by sector weightings and transaction costs. For tasks like these, you often need an algorithm for a specialized type of optimization: <a target="_blank" rel="nofollow" href="https://en.wikipedia.org/wiki/Integer_programming">Mixed Integer Programming</a>.</p>
<p>For problems like these, <a target="_blank" rel="nofollow" href="https://www.dirk-schumacher.net/">Dirk Schumacher</a> has created the <a target="_blank" rel="nofollow" href="https://dirkschumacher.github.io/ompr/">ompr package for R</a>. This package provides a convenient syntax for describing the variables and contraints in an optimization problem. For example, take the classic &quot;<a target="_blank" rel="nofollow" href="https://en.wikipedia.org/wiki/Knapsack_problem">knapsack</a>&quot; 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 <em>objective</em> (quantity to be maximized) and a <em>constraint</em>:</p>
<p>$$<br>\begin{equation*}<br>\begin{array}{ll@{}ll}<br>\text{max} &amp; \displaystyle\sum\limits_{i=1}^{n} v_{i}x_{i} &amp; &amp;\\<br>\text{subject to}&amp; \displaystyle\sum\limits_{i=1}^{n} w_{i}x_{i} \leq W, &amp; &amp;\\<br> &amp; x_{i} \in \{0,1\}, &amp;i=1 ,\ldots, n&amp;<br>\end{array}<br>\end{equation*}<br>$$</p>
<p>In ompr, the same problem is naturally expressed in R as follows:</p>
<div>
<pre>model <span>&lt;-</span> MIPModel() <span>%>%</span> 
  add_variable(x[i], i <span>=</span> <span>1</span><span>:</span>n, type <span>=</span> <span>&quot;binary&quot;</span>) <span>%>%</span> 
  set_objective(sum_expr(v[i] <span>*</span> x[i], i <span>=</span> <span>1</span><span>:</span>n)) <span>%>%</span> 
  add_constraint(sum_expr(w[i] <span>*</span> x[i], i <span>=</span> <span>1</span><span>:</span>n) <span>&lt;=</span> W)
</pre>
</div>
<p>To actually solve the problem, you need to provide a &quot;backend&quot; solver algorithm to ompr. It's designed to integrate with any solver, and currently works with the <a target="_blank" rel="nofollow" href="https://mran.microsoft.com/package/ROI/">ROI (R Optimization Infrastructure</a>) package. ROI in turn provides a number of solver algorithms including GLPK, the <a target="_blank" rel="nofollow" href="https://www.gnu.org/software/glpk/">GNU Linear Programming Kit</a>, which you can use to solve problems like this.</p>
<p>Dirk provides a number of worked examples of the ompr package in use. Examples include <a target="_blank" rel="nofollow" href="https://dirkschumacher.github.io/ompr/articles/problem-tsp.html">the Traveling Salesman problem</a>, <a target="_blank" rel="nofollow" href="https://dirkschumacher.github.io/ompr/articles/problem-tsp.html">solving Soduku puzzles</a>, and <a target="_blank" rel="nofollow" href="https://dirkschumacher.github.io/ompr/articles/problem-warehouse-location.html">selecting optimal warehouse locations</a> to minimize delivery costs to customers.</p>
<p><a target="_blank" rel="nofollow" href="http://revolution-computing.typepad.com/.a/6a010534b1db25970b01b7c8bea7ea970b-pi"><img title="Warehouses" alt="Warehouses" src="http://revolution-computing.typepad.com/.a/6a010534b1db25970b01b7c8bea7ea970b-800wi" border="0"></a></p>
<p>The <a target="_blank" rel="nofollow" href="https://github.com/dirkschumacher/ompr">ompr package is available on Github</a>. For more information, check out the ompr home page linked below.</p>
<p>Dirk Schumacher: <a target="_blank" rel="nofollow" href="https://dirkschumacher.github.io/ompr/">ompr: Mathematical Programming in R</a></p>
</div>
<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="http://blog.revolutionanalytics.com/2016/12/mixed-integer-programming-in-r-with-the-ompr-package.html"> Revolutions</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a title="The R Project for Statistical Computing" rel="nofollow" href="https://www.r-project.org/">R</a> news and <a title="R tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/tutorial">tutorials</a> on topics such as: <a title="Data science" rel="nofollow" href="https://www.r-bloggers.com/search/data%20science">Data science</a>, <a title="Big Data" rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data">Big Data, <a title="R jobs" rel="nofollow" href="https://www.r-users.com/">R jobs</a>, visualization (<a title="ggplot and ggplot2 tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2">ggplot2</a>, <a title="Boxplots using lattice and ggplot2 tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/boxplot">Boxplots</a>, <a title="Maps and gis" rel="nofollow" href="https://www.r-bloggers.com/search/map">maps</a>, <a title="Animation in R" rel="nofollow" href="https://www.r-bloggers.com/search/animation">animation</a>), programming (<a title="RStudio IDE for R" rel="nofollow" href="https://www.r-bloggers.com/search/RStudio">RStudio</a>, <a title="Sweave and literate programming" rel="nofollow" href="https://www.r-bloggers.com/search/sweave">Sweave</a>, <a title="LaTeX in R" rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX">LaTeX</a>, <a title="SQL and databases" rel="nofollow" href="https://www.r-bloggers.com/search/SQL">SQL</a>, <a title="Eclipse IDE for R" rel="nofollow" href="https://www.r-bloggers.com/search/eclipse">Eclipse</a>, <a title="git and github, Version Control System" rel="nofollow" href="https://www.r-bloggers.com/search/git">git</a>, <a title="Large data in R using Hadoop" rel="nofollow" href="https://www.r-bloggers.com/search/hadoop">hadoop</a>, <a title="Web Scraping of google, facebook, yahoo, twitter and more using R" rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping">Web Scraping</a>) statistics (<a title="Regressions and ANOVA analysis tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/regression">regression</a>, <a title="principal component analysis tutorial" rel="nofollow" href="https://www.r-bloggers.com/search/PCA">PCA</a>, <a title="Time series" rel="nofollow" href="https://www.r-bloggers.com/search/time+series">time series</a>, <a title="finance trading" rel="nofollow" href="https://www.r-bloggers.com/search/trading">trading</a>) and more...
<img height="1" alt="" width="1" src="http://feeds.feedburner.com/~r/RBloggers/~4/Qc9j4Kw3ONw"></a></div>