发帖
雷达卡
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 [url=https://www.rdocumentation.org/packages/stats/versions/3.3.1/topics/optimhttps://www.rdocumentation.org/p ... /3.3.1/topics/optim]optim[/url] 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:
<span id="MathJax-Element-1-Frame" class="mjx-chtml MathJax_CHTML" tabindex="0" data-mathml="max∑i=1nvixisubject to∑i=1nwixi≤W,xi∈{0,1},i=1,…,n" role="presentation" style="display: inline-block; line-height: 0; font-size: 13.56px; word-wrap: normal; word-spacing: normal; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding-top: 1px; padding-bottom: 1px; position: relative;">maxn∑i=1vixisubject ton∑i=1wixi≤W,xi∈{0,1},i=1,…,nmax∑i=1nvixisubject to∑i=1nwixi≤W,xi∈{0,1},i=1,…,n
In ompr, the same problem is naturally expressed in R as follows:
model <- MIPModel() %>% add_variable(x, i = 1:n, type = "binary") %>% set_objective(sum_expr(v * x, i = 1:n)) %>% add_constraint(sum_expr(w * x, 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.
The ompr package is available on Github. For more information, check out the ompr home page linked below.
京公网安备 11010802022788号
