Reputation: 312
I'm following this guide on LPSolve, which I've used in the past, but I'm now getting the result "Error: no feasible solution found"
my data.table looks like so:
Position Name...ID Name ID Roster.Position Salary Game.Info TeamAbbrev AvgPointsPerGame
1 G Ben Bishop (11402606) ben bishop 11402606 G 8400 ARI@DAL 10/04/2018 08:30PM ET DAL 4.40
2 G Anton Khudobin (11402601) anton khudobin 11402601 G 8200 ARI@DAL 10/04/2018 08:30PM ET DAL 4.36
3 G Connor Hellebuyck (11402708) connor hellebuyck 11402708 G 7700 WPG@STL 10/04/2018 08:00PM ET WPG 5.42
4 C Tyler Seguin (11402648) tyler seguin 11402648 C/UTIL 7700 ARI@DAL 10/04/2018 08:30PM ET DAL 4.75
5 G Laurent Brossoit (11402681) laurent brossoit 11402681 G 7500 WPG@STL 10/04/2018 08:00PM ET WPG 2.26
6 G Eric Comrie (11402730) eric comrie 11402730 G 7500 WPG@STL 10/04/2018 08:00PM ET WPG 2.47
From there I modified to
New_proj$Position <- as.factor(New_proj$Position)
New_proj$Salary <-as.numeric(New_proj$Salary)
#### Prepare constraint matrix of zeros #####
A <- matrix(0, nrow = 6, ncol = nrow(New_proj))
#Designate the positions that are equivalent to each other when generating the optimal lineup
#There are 7 distinct positions and 1 constraint in which salary is < 50,000
#I.e. A player with the position 1B/2B can fill the 1B or the 2B position
#Add a "1" to all position that can fill that position slot
#Set C parameters
j<-1
i<-1
for (i in 1:nrow(New_proj)){
if (New_proj$Position[i]=="C" )
A[j,i]<-1
}
#W
j<-2
i<-1
for (i in 1:nrow(New_proj)){
if (New_proj$Position[i]=="LW" ||
New_proj$Position[i]=="RW" )
A[j,i]<-1
}
#D
j<-3
i<-1
for (i in 1:nrow(New_proj)){
if (New_proj$Position[i]=="D" )
A[j,i]<-1
}
#G
j<-4
i<-1
for (i in 1:nrow(New_proj)){
if (New_proj$Position[i]=="G" )
A[j,i]<-1
}
#U
j<-5
i<-1
for (i in 1:nrow(New_proj)){
if (New_proj$Position[i]=="C" ||
New_proj$Position[i]=="LW" ||
New_proj$Position[i]== "RW"||
New_proj$Position[i]=="D" )
A[j,i]<-1
}
A[6, ] <- New_proj$Salary # salary <= 50000
# Prepare input for LP solver
objective.in <- New_proj$AvgPointsPerGame
const.mat <- A[]
const.dir <- c("==", "==", "==", "==","==", "<=")
const.rhs <- c(2, 3, 2, 1,1, 50000)
# Generate optimal lineup with lp solve
require(lpSolve)
sol <- lp(direction = "max", objective.in, # maximize objective function
const.mat, const.dir, const.rhs # constraints
) # use binary variables only
### View the solution
inds <- which(sol$solution == 1)
Error: object 'dataset' not found
sol
Error: no feasible solution found
I can't tell where the difference is. I've also followed another tutorial which gives the same "no feasible solution" but I can't for the life of me figure out why. That suggests that there is some disconnect between what I'm asking it and what's in the matrix but I can't see where.
Any thoughts welcome.
Upvotes: 0
Views: 1639
Reputation: 6813
Edited:
The problem is the 5th constraint. I have noticed is that there are substantially more 1s in the 5th row of A
, so I guess it is harder to find a solution there, because you can only set one of the variables to 1
for a solution.
rowSums(A[1:5,])
[1] 28 56 47 17 131
If you look at the LHS
the problem becomes clearer. You can only set 1 free variable to 1
if the coefficient in A[5, ]
(i.e. the fifth constraint) is 1
. So let's assume you have set 1 of these variables to one, you still need to satisfy constraints 1
to 3
. But: there are only o
coefficient in those rows, so you will not be able to satisfy those constraints.
A[, A[5, ] == 0]
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17]
[1,] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
[2,] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
[3,] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
[4,] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
[5,] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
[6,] 8400 8200 7700 7500 7500 7400 7200 7100 6900 6500 6500 6500 6500 6500 6500 6500 6500
If you only use this constraint, the problem is infeasible. If you use all constraints but this one, it is feasible. Also, if you change the RHS of the 5th constraint to 2
, the problem becomes feasible as well.
Original Answer:
This is the mathematical formulation of your problem:
Objective Function:
4.4*x1 + 4.36*x2 + 5.42*x3 + 4.75*x4 + 2.26*x5 + 2.47*x6
Constraints:
0*x1 + 0*x2 + 0*x3 + 1*x4 + 0*x5 + 0*x6 == 2
0*x1 + 0*x2 + 0*x3 + 0*x4 + 0*x5 + 0*x6 == 3
0*x1 + 0*x2 + 0*x3 + 0*x4 + 0*x5 + 0*x6 == 2
1*x1 + 1*x2 + 1*x3 + 0*x4 + 1*x5 + 1*x6 == 1
0*x1 + 0*x2 + 0*x3 + 1*x4 + 0*x5 + 0*x6 == 1
8400*x1 + 8200*x2 + 7700*x3 + 7700*x4 + 7500*x5 + 7500*x6 <= 50000
If you look at the 2nd and 3rd constraint, you can see that they can never be greater than 0, because all coefficients are 0
.
In the comments you have also specified that all variables should be binary. The default value of all.bin
in lp()
is however FALSE
.
If you do set all.bin = TRUE
, you will find that the first constraint will also be infeasible.
Upvotes: 3