Multiple Knapsack problem

[JGWilson83]

I'm trying to solve a multiple knapsack problem but my constraint is causing an issue (I've been able to solve a multi-dimensional knapsack problem easily enough, but utilising multiple capacities is causing an issue):

Here is the code I've used to solve the inital knapsack problem (and I've included the dataset I'm using):

library(tidyverse)
library(ROI)
library(ROI.plugin.glpk)
library(ompr)
library(ompr.roi)

KP <- read.csv("knapsack_data.csv")

# Create variables from data to use in model
n <- nrow(KP)
v <- KP$Value
w <- KP$Weight
c <- 240 #Set knapsack capacity

solution <- MIPModel() %>%
  add_variable(x[i], i = 1:n, type = "binary") %>%
  set_objective(sum_expr(v[i] * x[i], i = 1:n), "max") %>%
  add_constraint(sum_expr(w[i] * x[i], i = 1:n) <= c) %>%
  solve_model(with_ROI(solver = "glpk")) %>% 
  get_solution(x[i]) 
  #filter(value > 0)

# Now join solution to original dataframe
df <- cbind(KP,capacity=240,solution[,3,drop=FALSE])
ouput <- df %>% filter(value > 0) 

With the multiple knapsack, I'm trying to create a vector containing the knapsack capacity, and then create a x[i, j] binary variable that is set to 1 if item i is assigned to knapsack j:

# Create variables from data to use in model
n <- nrow(KP)
v <- KP$Value
w <- KP$Weight
c <- c(240,150)
m <- length(c)

# Now solve the model
solution <- MIPModel() %>%
  add_variable(x[i, j], i = 1:n,j=1:m, type = "binary") %>%
  set_objective(sum_expr(v[i] * x[i, j], i = 1:n, j=1:m), "max") %>%
  add_constraint(sum_expr(w[i] * x[i, j], i = 1:n, j=1:m) <= c[j]) %>% #This constraint ensures that the weight of the items must be less than the capacity
  add_constraint(sum_expr(x[i, j], i = 1:n, j=1:m) <= 1) %>% #This constraint ensure that an item can only be included in a single knapsack - not across multiple knapsacks
  solve_model(with_ROI(solver = "glpk")) %>% 
  get_solution(x[i, j]) 

I've tried debugging the code, and the issue seems to be related to the constraint formulation as the variables and objective generate correctly, however, I'm at a loss as to why the constraint isn't working. Any suggestions would be most welcome. knapsack_data.csv

[sbmack]

add_constraint(sum_expr(w[i] * x[i, j], i = 1:n, j=1:m) <= c[j]) %>% #This constraint ensures that the weight of the items must be less than the capacity

It looks like you need to create multiple constraints for each c[j] So j should be indexed on the right hand side:

add_constraint(sum_expr(w[i] * x[i, j], i = 1:n) <= c[j], j = 1:m)

Suggest you review the Bin Packing example for adding 2 dimensional constraints: https://dirkschumacher.github.io/ompr/index.html

[JGWilson83]

Hi,

Thanks for the assistance , it really is very much appreciated. I got the code to run, just need to figure out how to limit each item to just being used once now. I'll check the bin-packing example out now.

Thanks again

[JGWilson83]

Further to your advice, I managed to get a solution as follows:

# Create variables from data to use in model
n <- nrow(KP)
v <- KP$Value
w <- KP$Weight
c <- c(240,150)
m <- length(c)

# Now solve the model
solution <- MIPModel() %>%
  add_variable(x[i, j], i = 1:n,j=1:m, type = "binary") %>%
  set_objective(sum_expr(v[i] * x[i, j], i = 1:n, j=1:m), "max") %>%
  add_constraint(sum_expr(w[i] * x[i, j], i = 1:n) <= c[j], j = 1:m) %>%
  add_constraint(sum_expr(x[i, j], j = 1:m) <= 1, i=1:n) %>%
  solve_model(with_ROI(solver = "glpk")) %>% 
  get_solution(x[i, j]) 

Thanks again for the tip/pointer