Python pulp constraint - Doubling the weight of any one variable which contributes the most

Question

I am trying to use http://www.philipkalinda.com/ds9.html to set up a constrained optimisation.

prob = pulp.LpProblem('FantasyTeam', pulp.LpMaximize)

        decision_variables = []

        res = self.team_df
        # Set up the LP

        for rownum, row in res.iterrows():
            variable = str('x' + str(rownum))
            variable = pulp.LpVariable(str(variable), lowBound = 0, upBound = 1, cat= 'Integer') #make variables binary
            decision_variables.append(variable)

        print ("Total number of decision_variables: " + str(len(decision_variables)))


        total_points = ""


        for rownum, row in res.iterrows():
            for i, player in enumerate(decision_variables):
                if rownum == i:
                    formula = row['TotalPoint']* player
            total_points += formula

        prob += total_points
        print ("Optimization function: " + str(total_points))

The above, however, creates an optimisation where if points earned by x1 = X1, x2=X2.... and xn=Xn, it maximises x1*X1 + x2*X2 +..... + xn*XN. Here xi is the points earned by the XI variable. However, in my case, I need to double the points for the variable that earns the most points. How do I set this up?

Maximize OBJ: 38.1 x0 + 52.5 x1 + 31.3 x10 + 7.8 x11 + 42.7 x12 + 42.3 x13 + 4.7 x14 + 49.5 x15 + 21.2 x16 + 11.8 x17 + 1.4 x18 + 3.2 x2 + 20.8 x3 + 1.2 x4 + 24 x5 + 25.9 x6 + 27.8 x7 + 6.2 x8 + 41 x9

When I maximise the sum x1 gets dropped but when I maximise with the top guy taking double points, it should be there

Here are the constraints I am using:-

Subject To
_C1: 10.5 x0 + 21.5 x1 + 17 x10 + 7.5 x11 + 11.5 x12 + 12 x13 + 7 x14 + 19 x15
 + 10.5 x16 + 5.5 x17 + 6.5 x18 + 6.5 x2 + 9.5 x3 + 9 x4 + 12 x5 + 12 x6
 + 9.5 x7 + 7 x8 + 14 x9 <= 100
_C10: x12 + x2 + x6 >= 1
_C11: x10 + x11 + x17 + x3 <= 4
_C12: x10 + x11 + x17 + x3 >= 1
_C13: x0 + x10 + x11 + x12 + x13 + x14 + x15 + x18 + x2 <= 5
_C14: x0 + x10 + x11 + x12 + x13 + x14 + x15 + x18 + x2 >= 3
_C15: x1 + x16 + x17 + x3 + x4 + x5 + x6 + x7 + x8 + x9 <= 5
_C16: x1 + x16 + x17 + x3 + x4 + x5 + x6 + x7 + x8 + x9 >= 3
_C2: x0 + x1 + x10 + x11 + x12 + x13 + x14 + x15 + x16 + x17 + x18 + x2 + x3
 + x4 + x5 + x6 + x7 + x8 + x9 = 8
_C3: x0 + x14 + x16 + x5 <= 4
_C4: x0 + x14 + x16 + x5 >= 1
_C5: x15 + x18 + x4 + x7 + x8 <= 4
_C6: x15 + x18 + x4 + x7 + x8 >= 1
_C7: x1 + x13 + x9 <= 4
_C8: x1 + x13 + x9 >= 1
_C9: x12 + x2 + x6 <= 4

Naturally, maximising A + B + C + D doesn't maximise max(2A+B+C+D, A+2B+C+D, A+B+2C+D, A+B+C+2D)

where are the constraints you are using? Maybe you can force x1 to be the one that earns most points — juvian
That part is further down in the code. All those constraints have been created later in the code. — Arc
Is x1 is not the one that earns most points as it gets multiplied by 21.5? or the points is the result of 21.5 * x1 ? — juvian

kabdulla kabdulla · Accepted Answer · 2018-11-19T20:58:57

I'm going to answer the question I think you're asking and you can correct me if I'm wrong. My understanding of your question is:

I have a series of binary variables x0...xN, and if a variable is included is receives some points. If it is not included it receives no points.
There are some constraints which apply to the selection
If (and only if) a variable is selected and if (and only if) it is the chosen variable which receives the highest number of points, then that particular variable gets double points
The objective is to maximize the total points including the doubling of the highest scoring one.

Assuming that's your question here is a dummy example that does that. Basically we add an auxiliary binary variable for each variable which is true iff (if and only if) that variable scores the most number of points:

from pulp import *

n_vars = 4
idxs = range(n_vars)
points = [2.0, 3.0, 4.0, 5.0]

prob = pulp.LpProblem('FantasyTeam', pulp.LpMaximize)

# Variables
x = LpVariable.dicts('x', idxs, cat='Binary')
x_highest_score = LpVariable.dicts('x_highest_score', idxs, cat='Binary')

# Objective
prob += lpSum([points[i]*(x[i] + x_highest_score[i]) for i in idxs])

# Constraints
# Exactly one item has highest score:
prob += lpSum([x_highest_score[i] for i in idxs]) == 1

# If a score is to be highest, it has to be chosen
for i in idxs:
    prob += x_highest_score[i] <= x[i]

# And some selection constraints:
prob += x[0] + x[1] + x[2] + 1.5*x[3] <= 3
prob += x[0] + x[2] + 3*x[3] <= 3
prob += x[0] + x[1] + x[2] + 2*x[3] <= 3
# etc...

# Solve problem
prob.solve()

# Get soln
x_soln = [x[i].varValue for i in idxs]
x_highest_soln = [x_highest_score[i].varValue for i in idxs]

# And print the outputs
print (("Status: "), LpStatus[prob.status])
print ("Total points: ", value(prob.objective))
print ("x = ", x_soln)
print ("x_highest_soln = ", x_highest_soln)

This should return the following:

Status:  Optimal
Total points:  13.0
x =  [0.0, 1.0, 0.0, 1.0]
x_highest_soln =  [0.0, 0.0, 0.0, 1.0]

If you turn off the double-points option, by changing the constraint to the following:

prob += lpSum([x_highest_score[i] for i in idxs]) == 1

I.E. none scores highest, you'll find a different set of choices is made.

Python pulp constraint - Doubling the weight of any one variable which contributes the most

1 Answers