Optimization function applied to table of values in R

Question

`values <-    matrix(c(0.174,0.349,1.075,3.1424,0.173,0.346,1.038,3.114,0.171,0.343,1.03,3.09,0.17,0.34,1.02,3.06),ncol=4)    `

I am attempting to maximize the total value for the dataset taking only one value from each row, and with associated costs for each column

subject to:

1. One value column used per row.

2. cost of each use of column 1 is 4

   cost of each use of column 2 is 3

   cost of each use of column 3 is 2

   cost of each use of column 4 is 1

   total cost <= 11

These are stand in values for a larger dataset. I need to be able to apply it directly to all the rows of a dataset.

I have been trying to use the lpSolve package, with no success.

`f.obj <- values
f.con <- c(4,3,2,1)
f.dir <- "<="
f.rhs <- 11

lp("max", f.obj, f.con, f.dir, f.rhs)`

I am getting a solution of "0"

I do not know how to model this in a way that chooses one value per row and then uses a different value in calculating the constraints.

Answer 1

Looks like the problem is as follows:

1. We have a matrix a[i,j] with values, and a vector c[j] with costs.

2. We want to select one value for each row such that:

   a. total cost <= 11

   b. total value is maximized

3. To develop a mathematical model, we introduce binary variables x[i,j] ∈ {0,1}. With this, we can write:

   max sum((i,j), a[i,j]*x[i,j])
   subject to 
        sum((i,j), c[j]*x[i,j]) <= 11  
        sum(j, x[i,j]) = 1   ∀i
        x[i,j] ∈ {0,1}
   

4. Implement in R. I use here CVXR.

    #
    # data
    # A : values
    # C : cost
    #
   
    A <- matrix(c(0.174,0.349,1.075,3.1424,0.173,0.346,1.038,3.114,0.171,0.343,1.03,3.09,0.17,0.34,1.02,3.06),ncol=4)
   
    C <- c(4,3,2,1)
   
    maxcost <- 11
   
    #
    # form a matrix cmat[i,j] indicating the cost of element i,j
    #    
    cmat <- matrix(C,nrow=dim(A)[1],ncol=dim(A)[2],byrow=T)
   
    #
    # problem:
    # pick one value from each row
    # such that total value of selected cells is maximized
    # and cost of selected cells is limited to maxcost
    #
    # model:
    # min sum((i,j), a[i,j]*x[i,j])
    # subject to
    #     sum((i,j), c[j]*x[i,j]) <= maxcost
    #     sum(j,x[i,j]) = 1    ∀i
    #     x[i,j] ∈ {0,1}
    #
    #
   
    library(CVXR)
   
    x = Variable(dim(A), name="x", boolean=T)
   
    p <- Problem(Maximize(sum_entries(A*x)),
             constraints=list(
               sum_entries(cmat*x) <= maxcost,
               sum_entries(x,axis=1) == 1
               ))
   
    res <- solve(p,verbose=T)
    res$status
    res$value
    res$getValue(x)*A
   

The output looks like:

> res$status
[1] "optimal"

> res$value
[1] 4.7304

> res$getValue(x)*A
       [,1] [,2]  [,3] [,4]
[1,] 0.0000    0 0.000 0.17
[2,] 0.0000    0 0.343 0.00
[3,] 1.0750    0 0.000 0.00
[4,] 3.1424    0 0.000 0.00     

The description in the original post is not very precise. For instance, I assumed that we need to select precisely one cell from each row. If we just want "select at most one cell from each row", then replace

sum(j, x[i,j]) = 1   ∀i

by

sum(j, x[i,j]) <= 1   ∀i