0

Hello and thanks in advance. Fresh off the heels of this question I acquired some more RAM and now have enough memory to fit all the matrices I need to run a linear programming solver. Now the problem is none of the Linear Programming packages in R seem to support long vectors (ie large matrices).

I've tried functions Rsymphony_solve_LP, Rglpk_solve_LP and lp from packages Rsymphony, Rglpk, and lpSolve respectively. All report a similar error to the one below:

Error in rbind(const.mat, const.dir.num, const.rhs) : 
  long vectors not supported yet: bind.c:1544

I also have my code below in case that helps...the constraint matrix mat is my big matrix (7062 rows by 364520 columns) created using the package bigmemory. When I run this this line the matrix is pulled into memory and then after a while the errors show.

Rsymph <- Rsymphony_solve_LP(obj,mat[1:nrow(mat),1:ncol(mat)],dir,rhs,types=types,max=max, write_lp=T)

I'm guessing this is a hard-coded error in each of the three functions? Is there currently a linear programming solver in R or even Python that supports long vectors? Should I contact the package maintainers or just edit the code myself? Thanks!

Community
  • 1
  • 1
gtnbz2nyt
  • 1,465
  • 3
  • 17
  • 33
  • Is your constraint matrix sparse? If so, you should specify them sparsely using, e.g., `set.row` from lpSolveAPI. If it's not sparse, then I'd imagine you'll having trouble solving an LP that large anyways. – josliber Mar 04 '15 at 17:14
  • @josilber It's not sparse...but you're suggesting I might have some luck turning it into a sparse matrix? – gtnbz2nyt Mar 04 '15 at 17:20
  • What I'm saying is that if the constraint matrix is mostly non-zero then solving an LP of that size is going to be computationally challenging even if you get it into the solver. If the constraint matrix is mostly 0 you should definitely use LP packages' mechanisms for inputting sparse matrices. – josliber Mar 04 '15 at 18:21
  • @josilber There's a decent amount of non-zero values in there, but the decision variables is going to be a binary type so it should be doable...I'll look more into using sparse Matrices...is there a specific package that works better or an example of using sparse matrix syntax you can point to? thanks! – gtnbz2nyt Mar 04 '15 at 18:25
  • @josilber, I have been able to do this with a 7038x196280 constraint matrix. You can see the original question [here](http://stats.stackexchange.com/questions/136608/constrained-assignment-problem-linear-programming-genetic-algorithm-etc), it's a mutlifacility problem. I initially did try this with a genetic algorithm but I don't have much experience in that. I feel like this should be doable. – gtnbz2nyt Mar 04 '15 at 18:52

1 Answers1

1

The package lpSolveAPI can solve long-vector linear programming problems. You have to first start my declaring a Linear Programming object, then add the constraints:

library(lpSolveAPI)

#Generate Linear Programming Object
lprec <- make.lp(nrow = 0 # Number of Constraints
                 , ncol = ncol(mat) # Number of Decision Variables
)

#Set Objective Function to Minimize
set.objfn(lprec, obj)

#Add Constraints
#Note Direction and RHS is included along with Constraint Value
for(i in 1:nrow(mat) ){
  add.constraint(lprec,mat[i,], dir[i], rhs[i])
  print(i)
}

#Set Decision Variable Type
set.type(lprec, c(1:ncol(mat)), type = c("binary"))

#Solve Model
solve(lprec)

#Obtain Solutions
get.total.iter(lprec)
get.objective(lprec)
get.variables(lprec)

There's a good introduction to this package here.

gtnbz2nyt
  • 1,465
  • 3
  • 17
  • 33