CODEWITHSUNDEEP
roptimizationconstraintsknapsack-problemlpsolve
Eric_Alan
Eric_Alan

Reputation: 115

lpSolve - "Must Not Be Together" Constraint?

The Problem

I am using lpSolve to find the optimal lineup for a fantasy baseball team - a knapsack problem involving the price SALARY and projected points DK of each player PLAYERID within the given constraints of the contest.

The current code works great, but I have a constraint I would like to add that I can't quite figure out. The new constraint is to not have any players in the lineup facing one of the pitchers SP in the same lineup.

What I Have So Far

I created a column called MNBT (Must Not Be Together) which defines the opposing pitcher's PLAYERID that must not be found in the same lineup as each player, but I am stuck there. The first 20 rows of the data.frame slate_players are as follows (I can provide all 91 rows for this specific contest if needed):

   PLAYERID POS TEAM OPP SALARY    DK TEAM_O    MNBT
1     37584  SP  LAD OAK  10000 18.42    0SP   13170
2     11292  SP  TEX HOU   9300 18.41    0SP 1452665
3   1452665  SP  HOU TEX   7400 15.22    0SP   11292
4     11168  SP  BAL BOS   6900  9.06    0SP   13502
5     13170  SP  OAK LAD   6800  6.06    0SP   37584
6     13502  SP  BOS BAL   6700 13.52    0SP   11168
7   2038873  SP  KCR DET   6600 18.45    0SP   34649
8     34649  SP  DET KCR   6500  7.46    0SP 2038873
9     11446   C  KCR DET   5300  7.55    KCR   34649
10  1054004   C  LAD OAK   5000  8.25    LAD   13170
11    15541   C  BOS BAL   4500  7.08    BOS   11168
12  1252110   C  OAK LAD   4100  5.07    OAK   37584
13    22667   C  BAL BOS   3400  7.09    BAL   13502
14    10290   C  TEX HOU   2900  4.08    TEX 1452665
15    13171   C  DET KCR   2800  5.45    DET 2038873
16    17552   C  HOU TEX   2600  4.47    HOU   11292
17    36727  1B  LAD OAK   5800  9.09    LAD   13170
18    17648  1B  LAD OAK   5400  8.57    LAD   13170
19    17887  1B  OAK LAD   4900  7.30    OAK   37584
20    17851  1B  KCR DET   4400  7.24    KCR   34649
[...]

The Current lpSolve Code

# count the unique players and teams on the slate
unique_teams = unique(slate_players$TEAM_O)
unique_players = unique(slate_players$PLAYERID)

# define the objective for the solver
obj = slate_players$DK

# create a constraint matrix for the solver
con = rbind(t(model.matrix(~ POS + 0, slate_players)), #Positions
            t(model.matrix(~ PLAYERID + 0, slate_players)), #DupPlayers
            t(model.matrix(~ TEAM_O + 0, slate_players)), #SameTeam
            rep(1,nrow(slate_players)), #TotPlayers
            slate_players$SALARY) #MaxSalary

# set the direction for each of the constraints
dir = c("==", #1B
        "==", #2B
        "==", #3B
        "==", #C
        "==", #OF
        "==", #SP
        "==", #SS
        rep('<=',length(unique_players)), #DupPlayers
        rep('<=',length(unique_teams)), #SameTeam
        "==", #TotPlayers
        "<=") #MaxSalary

# set the limits for the right-hand side of the constraints
rhs = c(1, #1B
        1, #2B
        1, #3B
        1, #C
        3, #OF
        2, #SP
        1, #SS
        rep(1,length(unique_players)), #DupPlayers
        rep(5,length(unique_teams)), #SameTeam
        10, #TotPlayers
        50000) #MaxSalary

# find the optimal solution using the solver
result = lp("max", obj, con, dir, rhs, all.bin = TRUE)

# create a table for the players that are in optimal solution
solindex = which(result$solution==1)
optsolution = slate_players[solindex,]

The Question

How do I code this new constraint? I have been doing these kinds of adjustments manually, but I would really appreciate it if there were a solution available to automate this process. Thank you!

Upvotes: 2

Views: 242

Answers (2)

Eric_Alan
Eric_Alan

Reputation: 115

What I ended up doing, rather than a single MNBT column, was creating a helper column for each individual pitcher SP to indicate which hitters he may not appear in the optimal solution with. In these columns, I assigned a value for the pitcher of 5 and a value of 1 for each hitter he must not appear with. The constraint then became that the sum of each of these columns would be <= 5. The logic is that a maximum of 5 hitters may be in the same lineup facing any individual pitcher, but if that same pitcher appeared in the optimal solution, none of the hitters he was facing would be.

Upvotes: 1

windyvation
windyvation

Reputation: 561

While this doesn't create the set of constraints for you, this example is of one of those constraints that @AirSquid mentioned might help.

In the example above, the 6th player (13502) could not play against the 13th player (22667).

Add to the constraint:

c(0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0)

Add to the directions:

"<="

Add to the right hand side:

1

The next trick is how to generate all of these sets of constraints in R. Cheerio.

Upvotes: 0

Related Questions