Re: [R] Need advice on linear programming in R

[Giorgio Garziano]

Hi Michael,

On top of all suggestions, I can mention the following packages for linear 
programming problems:


https://cran.r-project.org/web/packages/linprog/linprog.pdf


https://cran.r-project.org/web/packages/lpSolve/lpSolve.pdf


https://cran.r-project.org/web/packages/clue/clue.pdf

(see clue package solve_LSAP function)


https://cran.r-project.org/web/packages/adagio/adagio.pdf


As a reference book, "Using R for Numerical Analysis in Science and 
Engineering", CRC press:


https://www.crcpress.com/Using-R-for-Numerical-Analysis-in-Science-and-Engineering/Bloomfield/p/book/9781439884485



Further, I share with you the code implementing a greedy solution to your 
assignment problem:

set.seed(1023)
nbin <- 5
nrow <- 100
nvalue <- nbin*nrow

# generating random values
gMat2 <- matrix(as.integer(Mod(rnorm(nvalue, 5, 10))), nrow = nrow)
gMat2

# since you want to maximize the minimum bin sums value
# let us already find the maximum value per row and store its corresponding
# column id inside rowmax
rowmax <- apply(gMat2, 1, function(x) {which.max(x)})
rowmax

# maximum value per each row
max_per_row <- sapply(1:nrow, function(x) gMat2[x, rowmax[x]])
names(max_per_row) <- as.character(1:nrow)
max_per_row

# sorting max_per_row values in descreasing order
sorted <- base::sort(max_per_row, decreasing=TRUE)
sorted

# bin where to store sums
bin <- vector(mode="numeric", length = nbin)

# assignment output based on sorted vector
output <- c()

# looping on sorted and assign the bin with minimum current sum
for (i in seq_along(sorted)) {
  s <- sorted[i]
  min.bin <- which.min(bin)
  bin[min.bin] <- bin[min.bin] + s
  output <- c(output, min.bin)
}

df <- cbind(sorted, output)
ord <- order(as.integer(rownames(df)))

df2 <- df[ord,]
colnames(df2) <- c("value", "selected_bin")
df2 <- data.frame(selected_column = rowmax, df2)

# assignments table
df2

# resulting bins sum
bin

-

Best,

GG



[[alternative HTML version deleted]]

__
R-help@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.

Re: [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
<florianschwendin...@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.ucda...@gmail.com>
> An: "R help" <r-help@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
&g

Re: [R] Need advice on linear programming in R

[Michael Hannon]

Thanks, Peter.  Not useless at all, but I'm somewhat overwhelmed by
the choices.  I'll have a closer look at some of them.

-- Mike


On Thu, Sep 1, 2016 at 1:24 AM, peter dalgaard  wrote:
>
>> On 01 Sep 2016, at 05:34 , Michael Hannon  wrote:
>>
>> 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.
>>
>
> Possibly a completely useless piece of advice, but have you checked the CRAN 
> Task View:
>
> https://cran.r-project.org/web/views/Optimization.html#MathematicalProgrammingSolvers
>
> ?
>
> --
> Peter Dalgaard, Professor,
> Center for Statistics, Copenhagen Business School
> Solbjerg Plads 3, 2000 Frederiksberg, Denmark
> Phone: (+45)38153501
> Office: A 4.23
> Email: pd@cbs.dk  Priv: pda...@gmail.com
>
>
>
>
>
>
>
>
>

__
R-help@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.

Re: [R] Need advice on linear programming in R

[peter dalgaard]

> On 01 Sep 2016, at 05:34 , Michael Hannon  wrote:
> 
> 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.
> 

Possibly a completely useless piece of advice, but have you checked the CRAN 
Task View:

https://cran.r-project.org/web/views/Optimization.html#MathematicalProgrammingSolvers

?

-- 
Peter Dalgaard, Professor,
Center for Statistics, Copenhagen Business School
Solbjerg Plads 3, 2000 Frederiksberg, Denmark
Phone: (+45)38153501
Office: A 4.23
Email: pd@cbs.dk  Priv: pda...@gmail.com

__
R-help@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.

[R] Need advice on linear programming in R

[Michael Hannon]

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,]35
[2,]69
[3,]95

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
1111
2211
3121
4221
5112
6212
7122
8222

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,]   180
[2,]   155
[3,]   129
[4,]9   14
[5,]95
[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
3121

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 1 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@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.