I have a big linear optimizer I'm running and need some help setting up the constraints to get what I want. It's hard for me to express it in words exactly (hence the vague post-title), so I've written an example, details:
- Select a total of 5 items, maximizing value and keeping the cost under 5k.
- Each item has 2 "types". They are either labeled
type1
= A, B, C, D, or E, and eithertype2
= X or Y. - 4 items must be type X, 1 must be type Y
The below example works great, but I want to add two more constraints and I'm not really sure how to do it. The two other constraints:
- I want every optimization to have at least 2 instances of
type1
. I don't care which type there's multiple of or if two different types are multiples (e.g. 2 A's and 2 C's), which is why I'm thinking of it as an "or" constraint (A > 2 OR B > 2 OR...). Is this even doable? - This one might be a bit more difficult: Whichever "type Y" is chosen, I don't want that
type1
to show up again. So say the Y item istype1
= C, I want every other chosen item to not be C. I imagine I'll need to add another dummy matrix interactingtype1
andtype2
Example of desired result:
id type1 type2 value cost
10 10 B X 19 865
11 11 C Y 19 1097
18 18 D X 19 1005
40 40 B X 20 956
45 45 A X 20 980
WORKING EXAMPLE:
library(lpSolve)
library(dplyr)
# setup df
id <- 1:50
type1 <- sample(c('A', 'B', 'C', 'D', 'E'), length(id), replace = T)
type2 <- sample(c('X', 'X', 'X', 'Y'), length(id), replace = T)
value <- round(runif(length(id), 0, 20),0)
cost <- round(runif(length(id), 750, 1250),0)
df <- data.frame(id, type1, type2, value, cost) %>%
mutate(total = 1)
# Attach dummy vars
type1Dummy <- as.data.frame.matrix(table(df$id, df$type1))
type2Dummy <- as.data.frame.matrix(table(df$id, df$type2))
df <- cbind(df, type1Dummy, type2Dummy)
# constraints
totalNum <- 5
totalCost <- 5000
totalX <- 4
totalY <- 1
rhs <- c(totalNum, totalCost, totalX, totalY)
# Direction vector
numDir <- '=='
costDir <- '<='
xDir <- '=='
yDir <- '=='
dir <- c(numDir, costDir, xDir, yDir)
# Setup opt
obj <- df$value
mat <- t(data.frame(df$total, df$cost, df$X, df$Y))
# Solver Setup
sol <- lpSolve::lp("max",
objective.in = obj,
const.mat = mat,
const.dir = dir,
const.rhs = rhs,
all.bin = T
)
df$selected <- sol$solution
dfSolved <- df[df$selected == 1,]
dfSolved
Thank you for your help!