Using maq to solve knapsack LPs

[erikcs]

One side use case for maq could be to solve linear programs that belongs to the class of linear multiple-choice knapsack problems.

LPs of the form (where the coefficients $c_{ik} > 0$)

$$ \max_x \frac{1}{n} \sum_{i=1}^{n} \sum_{k=1}^{K} a_{ik} x_{ik} $$

$$ \text{s.t.} \frac{1}{n} \sum_{i=1}^{n} \sum_{k=1}^{K} c_{ik} x_{ik} \leq B $$ $$ \sum_{k=1}^{K} x_{ik} \leq 1, i=1\ldots n $$ $$ x_{ik} \geq 0, k=1\ldots K, i=1\ldots n $$

can be solved efficiently with maqfor any budget constraints $B$. Here is a simple example.

WIth lpSolve (~ 8 seconds)

library(lpSolve)
n = 10000
K = 3
a.mat = matrix(10 * rnorm(n * K), n, K)
c.mat = matrix(1 + runif(n * K), n, K)
B = 0.7


# Representation for LP solve
x.coeffs = c(t(a.mat)) / n
A.mat = matrix(0, n, length(x.coeffs))
start = 1
for (row in 1:nrow(A.mat)) {
  end = start + K -1
  A.mat[row, start:end] = 1
  start = end + 1
}
c.coeff = c(t(c.mat)) / n
f.con = rbind(A.mat, c.coeff)
f.dir = rep("<=", nrow(f.con))
f.rhs = c(rep(1, nrow(A.mat)), B)

# Solution with LP solve
system.time(lp.res <- lp("max", x.coeffs, f.con, f.dir, f.rhs))
# user  system elapsed 
# 8.662   1.760  11.898

objective.lp = sum(x.coeffs * lp.res$solution)
objective.lp
# [1] 6.977869

x.mat.lp = matrix(lp.res$solution, nrow = n, byrow = TRUE)
head(x.mat.lp)
#       [,1] [,2] [,3]
# [1,]    0    0    0
# [2,]    0    0    0
# [3,]    1    0    0
# [4,]    0    0    0
# [5,]    0    0    0
# [6,]    0    0    0

With maq (~ 0.002 seconds)

library(maq)
# Solution for all B with maq
system.time(mq <- maq(a.mat, c.mat, a.mat))
# user  system elapsed 
# 0.002   0.000   0.002 

average_gain(mq, B)
# estimate  std.err 
# 6.977869 0.000000 

head(predict(mq, B))
#       [,1] [,2] [,3]
# [1,]    0    0    0
# [2,]    0    0    0
# [3,]    1    0    0
# [4,]    0    0    0
# [5,]    0    0    0
# [6,]    0    0    0