Linear Programming Problem R using lpSolveAPI

Question

Here is the data I'm working with:

structure(list(Name = c("Jokic", "Butler", "Murray", "Adebayo", 
"Porter", "Gordon", "Martin", "Pope", "Vincent", "Lowry", "Brown", 
"Strus", "Robinson", "Green", "Highsmith"), Points = c(62.8, 
48.8, 45.8, 41.8, 35.3, 30.3, 29.3, 23.8, 23.3, 22.3, 21.8, 19, 
16.3, 8.5, 6.8), Cost = c(14000, 13400, 10800, 9200, 7600, 6600, 
7400, 5600, 5800, 5200, 6200, 4800, 4200, 2200, 1400)), class = c("tbl_df", 
"tbl", "data.frame"), row.names = c(NA, -15L))

Here's my current code:

library(readxl)
library(tidyverse)
library(lpSolveAPI)

# Read the data from Excel
data <- read_excel("C:/Users/M0185JN/Downloads/NBA_1.xlsx")
data$cpt_points <- 1.5*data$Points
data$cpt_cost <- 1.5*data$Cost

#Players
num_players <- rep(1,nrow(data))
num_captain <- rep(1,nrow(data))

# Define the objective function coefficients
obj <- data$Points*num_players + data$cpt_points*num_captain

# Create a new LP model
lprec <- make.lp(nrow(data), nrow(data))

# Set the optimization direction to maximize
lp.control(lprec, sense = "maximize")

# Set the objective function coefficients
set.objfn(lprec, obj)

# Set type of decision variables
set.type(lprec, 1:nrow(data), type = "binary")

# Constraint: Pick exactly 5 players
add.constraint(lprec, num_players, "=", 5)
add.constraint(lprec, num_captain, "=", 1)

# Constraint: Total cost must be less than or equal to 50,000
add.constraint(lprec, data$Cost*num_players + data$cpt_cost*num_captain, "<=", 50000)

# Constraint: No Duplicate Players
add.constraint(lprec, num_players + num_captain, "<=", 1)

# Solve the linear programming problem
solve(lprec)

# Get the solution status
status <- get.solutioncount(lprec)

# Check if a solution was found
if (status > 0) {
  # Retrieve the values of the decision variables
  player_picked <- get.variables(lprec)
  
  # Create a data frame with the players and their corresponding picked status
  result <- data.frame(Name = data$Name, Picked = player_picked)
  
  # Filter the data frame to show only the players that were picked (Picked = 1)
  picked_players <- result[result$Picked == 1, ]
  
  # Print the picked players
  print(picked_players)
} else {
  print("No feasible solution found.")
}

The code is continuing to give me a "No Feasible Solution Found." when I know for a fact there is. Here are the constraints better explained:

I have to pick 6 players
1 is going to get cpt_points and cpt_cost while the others are getting Points and Cost.
You can also not pick the same player to get both.
Total cost cannot exceed 50000.

It's odd that the team has five players plus a captain. Shouldn't it have four players plus a captain? — Reinderien
– Reinderien, Commented Jun 2, 2023 at 22:29

Reinderien · Accepted Answer · 2023-12-27 19:49:57Z

Some suspicious stuff, like the "number-of" variables which should probably instead be assignment vectors where the captain is not considered a player. The following succeeds but I have not translated it back to R.

import pandas as pd
import pulp

index = pd.Index(name='Name', data=(
    'Jokic', 'Butler', 'Murray', 'Adebayo',
    'Porter', 'Gordon', 'Martin', 'Pope', 'Vincent', 'Lowry', 'Brown',
    'Strus', 'Robinson', 'Green', 'Highsmith',
))

df = pd.DataFrame(
    index=index,
    data={
        'Points': (
            62.8, 48.8, 45.8, 41.8, 35.3, 30.3, 29.3,
            23.8, 23.3, 22.3, 21.8, 19, 16.3, 8.5, 6.8,
        ),
        'Cost': (
            14000, 13400, 10800, 9200, 7600, 6600, 7400,
            5600, 5800, 5200, 6200, 4800, 4200, 2200, 1400,
        ),
        'Captain': pulp.LpVariable.matrix(
            name='captain', indices=index, cat=pulp.LpBinary),
        'Player': pulp.LpVariable.matrix(
            name='player', indices=index, cat=pulp.LpBinary),
    },
)

prob = pulp.LpProblem(name='nba_team', sense=pulp.LpMaximize)

# person cannot be both a player and a captain; make these mutually exclusive
for name, row in df.iterrows():
    prob.addConstraint(name=f'excl_{name}', constraint=row['Captain'] + row['Player'] <= 1)

# the total cost is the matrix product of costs with both the captain and player assignment vars
captain_cost, player_cost = df['Cost'] @ df[['Captain', 'Player']]
captain_coef = 1.5
total_cost = captain_coef*captain_cost + player_cost
prob.addConstraint(name='total_cost', constraint=total_cost <= 50_000)

# there are exactly four non-captain players
prob.addConstraint(name='n_players', constraint=df['Player'].sum() == 4)
# there is exactly one captain
prob.addConstraint(name='n_captains', constraint=df['Captain'].sum() == 1)

# maximize the number of points for the roster, with more weight to the captain
captain_points, player_points = df['Points'] @ df[['Captain', 'Player']]
prob.setObjective(captain_coef*captain_points + player_points)

print(prob)
prob.solve()
assert prob.status == pulp.LpStatusOptimal

captains = df.loc[
    df['Captain'].apply(pulp.value) > 0.5,
    ['Points', 'Cost'],
]
players = df.loc[
    df['Player'].apply(pulp.value) > 0.5,
    ['Points', 'Cost'],
]
print(f'{prob.objective.value():.1f} points for ${total_cost.value():,.2f}\n')
print('Captain:')
print(captains, end='\n\n')
print('Players:')
print(players)

nba_team:
MAXIMIZE
62.699999999999996*Adebayo_captain + 41.8*Adebayo_player + 32.7*Brown_captain + 21.8*Brown_player + 73.19999999999999*Butler_captain + 48.8*Butler_player + 45.45*Gordon_captain + 30.3*Gordon_player + 12.75*Green_captain + 8.5*Green_player + 10.2*Highsmith_captain + 6.8*Highsmith_player + 94.19999999999999*Jokic_captain + 62.8*Jokic_player + 33.45*Lowry_captain + 22.3*Lowry_player + 43.95*Martin_captain + 29.3*Martin_player + 68.69999999999999*Murray_captain + 45.8*Murray_player + 35.7*Pope_captain + 23.8*Pope_player + 52.949999999999996*Porter_captain + 35.3*Porter_player + 24.450000000000003*Robinson_captain + 16.3*Robinson_player + 28.5*Strus_captain + 19.0*Strus_player + 34.95*Vincent_captain + 23.3*Vincent_player + 0.0
SUBJECT TO
Jokic_excl: Jokic_captain + Jokic_player <= 1

Butler_excl: Butler_captain + Butler_player <= 1

Murray_excl: Murray_captain + Murray_player <= 1

Adebayo_excl: Adebayo_captain + Adebayo_player <= 1

Porter_excl: Porter_captain + Porter_player <= 1

Gordon_excl: Gordon_captain + Gordon_player <= 1

Martin_excl: Martin_captain + Martin_player <= 1

Pope_excl: Pope_captain + Pope_player <= 1

Vincent_excl: Vincent_captain + Vincent_player <= 1

Lowry_excl: Lowry_captain + Lowry_player <= 1

Brown_excl: Brown_captain + Brown_player <= 1

Strus_excl: Strus_captain + Strus_player <= 1

Robinson_excl: Robinson_captain + Robinson_player <= 1

Green_excl: Green_captain + Green_player <= 1

Highsmith_excl: Highsmith_captain + Highsmith_player <= 1

total_cost: 13800 Adebayo_captain + 9200 Adebayo_player + 9300 Brown_captain
 + 6200 Brown_player + 20100 Butler_captain + 13400 Butler_player
 + 9900 Gordon_captain + 6600 Gordon_player + 3300 Green_captain
 + 2200 Green_player + 2100 Highsmith_captain + 1400 Highsmith_player
 + 21000 Jokic_captain + 14000 Jokic_player + 7800 Lowry_captain
 + 5200 Lowry_player + 11100 Martin_captain + 7400 Martin_player
 + 16200 Murray_captain + 10800 Murray_player + 8400 Pope_captain
 + 5600 Pope_player + 11400 Porter_captain + 7600 Porter_player
 + 6300 Robinson_captain + 4200 Robinson_player + 7200 Strus_captain
 + 4800 Strus_player + 8700 Vincent_captain + 5800 Vincent_player <= 50000

n_players: Adebayo_player + Brown_player + Butler_player + Gordon_player
 + Green_player + Highsmith_player + Jokic_player + Lowry_player
 + Martin_player + Murray_player + Pope_player + Porter_player
 + Robinson_player + Strus_player + Vincent_player = 4

n_captains: Adebayo_captain + Brown_captain + Butler_captain + Gordon_captain
 + Green_captain + Highsmith_captain + Jokic_captain + Lowry_captain
 + Martin_captain + Murray_captain + Pope_captain + Porter_captain
 + Robinson_captain + Strus_captain + Vincent_captain = 1

VARIABLES
0 <= Adebayo_captain <= 1 Integer
0 <= Adebayo_player <= 1 Integer
0 <= Brown_captain <= 1 Integer
0 <= Brown_player <= 1 Integer
0 <= Butler_captain <= 1 Integer
0 <= Butler_player <= 1 Integer
0 <= Gordon_captain <= 1 Integer
0 <= Gordon_player <= 1 Integer
0 <= Green_captain <= 1 Integer
0 <= Green_player <= 1 Integer
0 <= Highsmith_captain <= 1 Integer
0 <= Highsmith_player <= 1 Integer
0 <= Jokic_captain <= 1 Integer
0 <= Jokic_player <= 1 Integer
0 <= Lowry_captain <= 1 Integer
0 <= Lowry_player <= 1 Integer
0 <= Martin_captain <= 1 Integer
0 <= Martin_player <= 1 Integer
0 <= Murray_captain <= 1 Integer
0 <= Murray_player <= 1 Integer
0 <= Pope_captain <= 1 Integer
0 <= Pope_player <= 1 Integer
0 <= Porter_captain <= 1 Integer
0 <= Porter_player <= 1 Integer
0 <= Robinson_captain <= 1 Integer
0 <= Robinson_player <= 1 Integer
0 <= Strus_captain <= 1 Integer
0 <= Strus_player <= 1 Integer
0 <= Vincent_captain <= 1 Integer
0 <= Vincent_player <= 1 Integer


Result - Optimal solution found

Objective value:                225.40000000
Enumerated nodes:               0
Total iterations:               0
Time (CPU seconds):             0.03
Time (Wallclock seconds):       0.04

Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.04   (Wallclock seconds):       0.04

225.4 points for $50,000.00

Captain:
       Points   Cost
Name                
Jokic    62.8  14000

Players:
         Points  Cost
Name                 
Adebayo    41.8  9200
Porter     35.3  7600
Gordon     30.3  6600
Pope       23.8  5600

If it turns out that you really do want six players, then change the 4 to 5 and this produces

224.7 points for $50,000.00

Captain:
       Points   Cost
Name                
Jokic    62.8  14000

Players:
           Points  Cost
Name                   
Adebayo      41.8  9200
Porter       35.3  7600
Gordon       30.3  6600
Robinson     16.3  4200
Highsmith     6.8  1400

Collectives™ on Stack Overflow

Linear Programming Problem R using lpSolveAPI

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related