[R] Need advice on linear programming in R

[Michael Hannon]

Thanks, Florian.  That looks very useful.

-- Mike

On Thu, Sep 1, 2016 at 2:33 AM, Florian Schwendinger
<FlorianSchwendinger at gmx.at> wrote:
> You could try ROI
> <https://cran.r-project.org/web/packages/ROI/index.html>
> you write the model once and can use several solver, therefore
> you could just try which solver performs best (uses a low amount of
> memory) for your given problem.
>
> solver overview:
> <http://roi.r-forge.r-project.org/jekyll/update/2016/06/17/new_roi_version.html>
>
> simple LP example:
> <http://roi.r-forge.r-project.org/examples/lp.html>
>
> Best,
> Florian
>
> Gesendet: Donnerstag, 01. September 2016 um 05:34 Uhr
> Von: "Michael Hannon" <jmhannon.ucdavis at gmail.com>
> An: "R help" <r-help at r-project.org>
> Betreff: [R] Need advice on linear programming in R
> Greetings. A subset of a problem that the group I work with turns out to be
> an optimization problem, in the sense of linear programming.
>
> We've looked at several approaches to this but haven't found one that seems
> to
> be the right fit. I'm looking for some guidance in finding an R package that
> does what we want in an acceptable time.
>
> Here's a toy example. We start with a matrix, called "gMat1" (historical
> reasons):
>
>> gMat1 <- matrix(c(3, 6, 9, 5, 9, 5), nrow=3)
>> print(gMat1)
> [,1] [,2]
> [1,] 3 5
> [2,] 6 9
> [3,] 9 5
>
> The goal is to add the contents of one column of each row to one of two bins
> (in general the number of bins equals the number of columns) such that the
> minimum number in each bin is maximized. An example follows.
>
> In the toy example, the possibilities can be enumerated simply:
>
>> allChoices <- expand.grid(rep(list(1:ncol(gMat1)), nrow(gMat1)))
>> print(allChoices)
> Var1 Var2 Var3
> 1 1 1 1
> 2 2 1 1
> 3 1 2 1
> 4 2 2 1
> 5 1 1 2
> 6 2 1 2
> 7 1 2 2
> 8 2 2 2
>
> For example, with the first choice, (1, 1, 1), column 1, hence, bin 1, is
> selected for all three rows, giving a result for the two bins of:
>
> 18 0
>
> For the second choice, (2, 1, 1), the '2' in the first position selects the
> contents of column 2 for bin 2. The remaining (1, 1) select the (6, 9) in
> the
> first column and assign those to bin 1:
>
> 15 5
>
> The result is a set of "binSums" corresponding to the each of the set of
> possible choices:
>
>> print(binSums)
> [,1] [,2]
> [1,] 18 0
> [2,] 15 5
> [3,] 12 9
> [4,] 9 14
> [5,] 9 5
> [6,] 6 10
> [7,] 3 14
> [8,] 0 19
>
> Having generated the sums, the goal is to pick the row that has the largest
> minimum and map that back to the original choice. In the toy example, both
> rows 3 and 4 satisfy that criterion ('9' is the minimum in each, and '9' is
> bigger than the minima in the other 6 rows -- 0, 3, 5, 6).
>
> In the real case there are potentially thousands of rows and columns, so
> eye-balling is not an option. And, in fact, using "expand.grid" isn't even
> an
> option to generate the original choices.
>
> We've tried some ad hoc approaches that seem to work tolerably well. Here's
> one that we *might* have considered, if we *could* have generated the
> "allChoices/binSums":
>
>> bsVar <- apply(binSums, 1, var)
>> locBestVar <- which(bsVar == min(bsVar))
>> allChoices[locBestVar, ]
> Var1 Var2 Var3
> 3 1 2 1
>
> But there was a feeling within the group that we didn't have a solid-enough
> foundation using the ad hoc approaches. Hence, we asked for help from an
> expert in Operations Research. He was able to solve a problem of realistic
> size in more or less no time at all using the "GAMS" software:
>
> https://www.gams.com/
>
> Unfortunately, GAMS is not free software, and we are hoping to produce an R
> package that is freely distributable. The next suggestion was to use Gurobi:
>
> http://www.gurobi.com/
>
> which is evidently free for academic use but not otherwise. Better, but
> still
> not perfect. (And I couldn't use the free version of Gurobi while working
> from home, as it didn't consider my home network to be associated with an
> academic institution -- which of course it isn't).
>
> Finally, we tried:
>
> Rglpk_solve_LP
>
> from the R package "Rglpk":
>
> https://cran.r-project.org/web/packages/Rglpk/index.html
>
> This satisfied the licensing constraints, but we were unable to produce a
> result in a "finite" amount of time. By this I mean that we ran the Rglpk
> software on a problem with 200 rows and 20 columns on the latest Mac Pro
> with
> 64GB of memory, and it didn't finish overnight. A realistic problem would
> have at least 10000 rows and 50 columns. (This admittedly might simply have
> been a consequence of our unfamiliarity with the package. Suggestions
> welcome.) To be clear, this process is not something we'd be doing once in
> order to build the package. This is something an end user would have to do
> every time he/she ran our package.
>
> If you've managed to read this far and have any suggestions as to how we
> might
> proceed, please send them my way. Thanks.
>
> -- Mike
>
> ______________________________________________
> R-help at r-project.org mailing list -- To UNSUBSCRIBE and more, see
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.
>
>