I'm trying to select 5 values in the first row, 1 value in rows 2-9, and maximize the objective function. The only thing I can't figure out how to embed in the problem is that I can only choose a value once - which is to say, if value 49.27 is selected for row 1, I can't also choose value 49.27 for row 9.
obj <- c(
49.2723892,
31.4629786,
25.3265757,
23.3915431,
19.5677222,
19.2621303,
18.2912147,
16.7899278,
14.5498144,
12.7440869,
11.6331623,
11.0012557,
7.9473880,
7.8453557,
3.7182273,
0.2084929,
0.0100000
)
mat <- as.matrix(c(1, 0, 0, 0, 0, 0, 0, 0, 1)) %>%
cbind( c(0, 1, 1, 0, 0, 0, 0, 0, 1),
c(1, 0, 0, 0, 0, 0, 0, 0, 1),
c(0, 0, 1, 1, 0, 0, 0, 0, 1),
c(0, 0, 0, 0, 1, 1, 0, 0, 1),
c(0, 0, 0, 0, 0, 1, 1, 0, 1),
c(0, 0, 0, 0, 0, 0, 1, 1, 1),
c(0, 0, 0, 0, 1, 1, 0, 0, 1),
c(1, 0, 0, 0, 0, 0, 0, 0, 1),
c(1, 0, 0, 0, 0, 0, 0, 0, 1),
c(0, 1, 0, 1, 0, 0, 0, 0, 1),
c(0, 1, 1, 0, 0, 0, 0, 0, 1),
c(1, 0, 0, 0, 0, 0, 0, 0, 1),
c(1, 0, 0, 0, 0, 0, 0, 0, 1),
c(1, 0, 0, 0, 0, 0, 0, 0, 1),
c(0, 0, 0, 0, 0, 0, 0, 1, 1),
c(0, 0, 0, 0, 0, 0, 0, 1, 1)
)
const.dir <- c("==", "==", "==", "==","==","==","==", "==", "==")
const.rhs <- c(5, 1, 1, 1, 1, 1, 1, 1, 1)
sol <- lp(direction = "max", obj,
mat, const.dir, const.rhs)
Am I missing something?
Why is it returning the following:
"Error: no feasible solution found"
I agree that {CVXR} is better suited, at the very least syntactically, to handle this problem. But just for the sake of completeness, here's how you can do this in {lpSolve}.
I repeated the obj values for each row and zeroed out the values that cannot be selected (a vector of length = 153, i.e. 9 x 17). Then, created a 26 x 153 constraint matrix (9 + 17 rows and 9 x 17 columns). I also changed the constraint directions and RHS accordingly (vectors of length = 26).
nr <- nrow(mat)
nc <- ncol(mat)
# repeat obj values for each row, but zero out unavailable ones
obj_vector <- rep(obj, nr) * as.vector(t(mat))
constraint_matrix <- matrix(0, nrow = nr + nc, ncol = nr * nc)
# each row must select exactly const.rhs[i] values
constraint_matrix[1:nr, ] <- sapply(1:nr, \(i)
replace(numeric(nr*nc),
(i-1)*nc + 1:nc, mat[i,])) |> t()
# each value can be selected at most once
constraint_matrix[(nr+1):(nr+nc), ] <- sapply(1:nc, \(j)
as.numeric(rep(1:nc,
nr) == j)) |> t()
# row sum constraints (exact) and column sum constraints (at most once)
const.dir <- c(rep("==", nr), rep("<=", nc))
# row requirements and each value used at most once
const.rhs_full <- c(const.rhs, rep(1, nc))
# solution
sol <- lpSolve::lp(
direction = "max",
objective.in = obj_vector,
const.mat = constraint_matrix,
const.dir = const.dir,
const.rhs = const.rhs_full,
all.bin = TRUE
)
# checking if the solution was successful
sol$status
#> [1] 0
# optimum value
sol$objval
#> [1] 261.2402
# solution matrix
solution_matrix <- matrix(sol$solution, nrow = nr, ncol = nc, byrow = TRUE)
# making sure row constraints are satisfied (const.rhs)
rowSums(solution_matrix)
#> [1] 5 1 1 1 1 1 1 1 1
# making sure no values were used more than once
colSums(solution_matrix)
#> [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0
# to verify against CVXR solution
## same values selected, but not for the same rows
colSums(row(solution_matrix) * solution_matrix)
#> [1] 1 3 1 4 5 7 8 6 1 1 2 9 1 0 0 0 0
Created on 2025-07-07 with reprex v2.1.1
obj <- c(
49.2723892, 31.4629786, 25.3265757, 23.3915431, 19.5677222,
19.2621303, 18.2912147, 16.7899278, 14.5498144, 12.7440869,
11.6331623, 11.0012557, 7.9473880, 7.8453557, 3.7182273,
0.2084929, 0.0100000
)
mat <- structure(c(1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0,
1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0,
0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1,
1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1,
1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0,
0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1,
0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0,
0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0,
0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1),
dim = c(9L, 17L))
const.rhs <- c(5, 1, 1, 1, 1, 1, 1, 1, 1)