Linear programming salad mixture optimization with PuLP

Question

I've set up the following LP problem and everything appears to be working except for my percent of mass constraint for salad greens. I want the mass of salad greens to be at least 40%, but I'm getting a syntax error with PuLP's lpSum, and I'm not sure how to reconcile it.

I'm have the following constraints for each salad:

 At least 15 grams of protein

 At least 2 and at most 8 grams of fat

 At least 4 grams of carbohydrates

 At most 200 milligrams of sodium

 At least 40% leafy greens by mass.

from pulp import *

# Creates a list of the Ingredients
Ingredients = ['TOMATO', 'LETTUCE', 'SPINACH', 'CARROT', 'SUNFLOWER', 'TOFU', 'CHICKPEAS', 'OIL']

kcal = {'TOMATO': 21, 
         'LETTUCE': 16, 
         'SPINACH': 40, 
         'CARROT': 41, 
         'SUNFLOWER': 585, 
         'TOFU': 120,
         'CHICKPEAS': 164,
         'OIL': 884}

protein = {'TOMATO': 0.85, 
         'LETTUCE': 1.62, 
         'SPINACH': 2.86, 
         'CARROT': 0.93, 
         'SUNFLOWER': 23.4, 
         'TOFU': 16,
         'CHICKPEAS': 9,
         'OIL': 0}

fat = {'TOMATO': 0.33, 
         'LETTUCE': 0.20, 
         'SPINACH': 0.39, 
         'CARROT': 0.24, 
         'SUNFLOWER': 48.7, 
         'TOFU': 5.0,
         'CHICKPEAS': 2.6,
         'OIL': 100.0}

carbs = {'TOMATO': 4.64, 
         'LETTUCE': 2.37, 
         'SPINACH': 3.63, 
         'CARROT': 9.58, 
         'SUNFLOWER': 15.0, 
         'TOFU': 3.0,
         'CHICKPEAS': 27.0,
         'OIL': 0.0}

sodium = {'TOMATO': 9.0, 
         'LETTUCE': 28.0, 
         'SPINACH': 65.0, 
         'CARROT': 69.0, 
         'SUNFLOWER': 3.80, 
         'TOFU': 120.0,
         'CHICKPEAS': 78.0,
         'OIL': 0.0}

cost = {'TOMATO': 1.0, 
         'LETTUCE': 0.75, 
         'SPINACH': 0.50, 
         'CARROT': 0.50, 
         'SUNFLOWER': 0.45, 
         'TOFU': 2.15,
         'CHICKPEAS': 0.95,
         'OIL': 2.00}

# Create the 'prob' variable to contain the problem data
prob = LpProblem("The Salad Problem", LpMinimize)

# A dictionary called 'ingredient_vars' is created to contain the referenced Variables
ingredient_vars = LpVariable.dicts("Ingr",Ingredients,0)

# The objective function is added to 'prob' first
prob += lpSum([kcal[i]*ingredient_vars[i] for i in Ingredients]), "Total kCal of Ingredients per salad"

# The constraints are added to 'prob'
prob += lpSum([protein[i] * ingredient_vars[i] for i in Ingredients]) >= 15.0, "ProteinRequirement"
prob += 8.0 >= lpSum([fat[i] * ingredient_vars[i] for i in Ingredients]) >= 2.0, "FatRequirement"
prob += lpSum([carbs[i] * ingredient_vars[i] for i in Ingredients]) >= 4.0, "CarbRequirement"
prob += lpSum([sodium[i] * ingredient_vars[i] for i in Ingredients]) <= 200.0, "SodiumRequirement"
prob += lpSum(prob.variables()[2].varValue + prob.variables()[4].varValue) / lpSum([prob.variables()[i].varValue for i in range(8)]) >= 0.40, "GreensRequirement"

prob.solve()

# The status of the solution is printed to the screen
print("Status:", LpStatus[prob.status])

# Each of the variables is printed with it's resolved optimum value
for v in prob.variables():
    print(v.name, "=", v.varValue)

# The optimised objective function value is printed to the screen
print("Total kCal of Ingredients per salad = ", value(prob.objective))

This is the constraint that's giving me the issue:

prob += lpSum(prob.variables()[2].varValue + prob.variables()[4].varValue) / lpSum([prob.variables()[i].varValue for i in range(8)]) >= 0.40, "GreensRequirement"

This gives an error for using the + operator on NoneType, since the variables don't have values yet. I'm just not sure exactly how to set up a constraint of this kind. I've looked through the PuLP docs on this, but I haven't had any luck figuring out the issue.

Answer 1

Some remarks

• As you said yourself, you can't build constraints which are based on the value of some not-yet optimized decision-variable!
  • Constraints using .varValue are not possible
• I don't get the concept of prob.variables()[2] in general as opposed to access ingredient_vars[i] like before (but as i don't know what exactly prob.variables returns i will ignore this)
• If you replace the .varValue access and just use the variables directly, you are building a constraint with a division which is not linear and pulp will not accept this
  • Even if pulp would accept this, the solver won't be able to solve this (LP-solver)

What to do

We need to:

• build a linear-constraint to represent your ratio-constraint

Theory

We use the reformulation described in the documentation of lpsolve here. An excerpt:

^{Screenshot of lpsolve's documentation (http://lpsolve.sourceforge.net/5.1/ratio.htm)}

In practice

Remark: As i'm unfamiliar with the prob.variables()[2]-like access of variables and too lazy to check the docs, i'm guessing here that greens are: LETTUCE + SPINACH. Feel free to change it if i misunderstood this!

The constraint looks hardcoded (not nice but might be okay for your example) like this:

prob += (0 - 0.4) * ingredient_vars['TOMATO'] + (1 - 0.4) * ingredient_vars['LETTUCE'] + \
        (1 - 0.4) * ingredient_vars['SPINACH'] + (0 - 0.4) * ingredient_vars['CARROT'] + \
        (0 - 0.4) * ingredient_vars['SUNFLOWER'] + (0 - 0.4) * ingredient_vars['TOFU'] + \
        (0 - 0.4) * ingredient_vars['CHICKPEAS'] + (0 - 0.4) * ingredient_vars['OIL'] >= 0.0, 'GreensRequirement'

This is a direct translation from the formulation of lpsolve's docs. Check the assumptions we had to made!

Example output

Two examples using exactly your code with the replaced constraint (given my assumptions of ingredients beeing green):

Ratio of 0.4 (described in code above)

('Status:', 'Optimal')
('Ingr_CARROT', '=', 0.0)
('Ingr_CHICKPEAS', '=', 0.0)
('Ingr_LETTUCE', '=', 0.58548009)
('Ingr_OIL', '=', 0.0)
('Ingr_SPINACH', '=', 0.0)
('Ingr_SUNFLOWER', '=', 0.0)
('Ingr_TOFU', '=', 0.87822014)
('Ingr_TOMATO', '=', 0.0)
('Total kCal of Ingredients per salad = ', 114.75409824)

Ratio of 0.9

('Status:', 'Optimal')
('Ingr_CARROT', '=', 0.0)
('Ingr_CHICKPEAS', '=', 0.0)
('Ingr_LETTUCE', '=', 4.4146501)
('Ingr_OIL', '=', 0.0)
('Ingr_SPINACH', '=', 0.0)
('Ingr_SUNFLOWER', '=', 0.0)
('Ingr_TOFU', '=', 0.49051668)
('Ingr_TOMATO', '=', 0.0)
('Total kCal of Ingredients per salad = ', 129.4964032)