Week 9: Linear programming

In the following exercises you will learn the basics of Pyomo. Setting up a simple problem is relatively straightforward, but adding extra variables/constraints quickly becomes problematic if you don’t learn how to use its more advanced functionality.

These exercises will take you through setting up a basic problem with simple notation before moving to the more advanced functionality on the same problem. Finally, we will tackle a significantly larger problem requiring importing data.

Supplementary material

Exercise 1 - a simple diet problem

The backdrop to this exercise is https://www.youtube.com/watch?v=36Uj1ZhWqa8; there is no need to watch the video unless you would like a reminder of how linear programming works.

In this exercise, a company would like to minimise the cost of “healthy” side dishes for their burgers. They have three basic ingredients: carrot, white cabbage, and pickled cucumbers.

The costs (per kg) of each of these ingredients are

Ingredient Cost
Carrot 0.75
Cabbage 0.50
Cucumber 0.15

Their nutritional contents, with requirements per side dish, are

Nutrition Carrot Cabbage Cucumber Requirement
Vitamin A (mg/kg) 35 0.5 0.5 0.5mg
Vitamin B (mg/kg) 60 300 10 15mg
Dietary Fibre (g/kg) 30 20 10 4g
  1. Create a model object to hold the problem. E.g., pyo.ConcreteModel().
  2. Create variables corresponding to each ingredient. E.g., pyo.Var(within=pyo.NonNegativeReals).
  3. Create an objective function to minimise the total cost. E.g., pyo.Objective(expr=..., sense=pyo.minimize).
  4. Create constraints for each of the nutritional requirements. E.g., pyo.Constraint(expr=...).
  5. Solve the linear program. E.g., solver = pyo.SolverFactory('glpk') ; results = solver.solve(model, tee=True) ; model.pprint(). Does the solution match that of the YouTube video (carrot = 9.5g, cabbage = 38g, cucumber = 294g)?
  6. Let’s suppose that cucumbers aren’t available. There are a couple of ways we could achieve this - for example, we could rebuild with the third column removed. Alternatively, we could add an equality constraint on the problem (cucumber = 0).

Exercise 2 - a simple diet problem extended

The goal with this exercise is to simplify the construction of the objective function and the constraints. Often data is provided in tableaus (as above) and instead of manually typing out constraints, we can use loops over the rows/columns of the table. This may not seem simpler for this small example, but it will be significantly easier for large problems.

  1. Read slides 28-30 of the Pyomo Workshop Slides (link above; “Simple Modeling Example: Classic Knapsack Problem” onwards). How might you create a similar structure for the diet problem?

  2. Use the variables (carrot, cabbage, cucumber) as the indices, with the cost and nutritional content as dictionaries (e.g., cost = {'carrot': 0.75, ...} and vitaminA = {'carrot': 35}). Create the full problem in Pyomo, solve it, and check your answer matches with exercise 1.

  3. Using dictionaries, it was possible to simplify the problem so we have a single variable (with indices ['carrot', 'cabbage', 'cucumber']), but all the constraints are still defined separately. To store all the constraint information in a single table, we can create a dictionary of the form nutrition = {('carrot', 'vitamin A'): 35, ('carrot', 'vitamin B'): 60, ..., ('cucumber', 'fibre'): 10}. Create a dictionary for the nutrition and a separate dictionary for the requirements.

  4. Rather than give names to individual constraints, it is possible to create a list of constraints in Pyomo. This enables us to use loops to create many constraints easily. The form of the command is

    model.constraints = pyo.ConstraintList()
for n in nutrient_names:
   model.constraints.add(...)

    How can you use this form to condense the creation of all the constraints? Solve the problem and check that your results match your previous results.

    • Creating a dictionary by hand in this way is quite painful. We’d usually load one in from a spreadsheet directly - see the next exercise.

Exercise 3 - a bigger diet problem

In this problem, we have a much bigger and more realistic data set to work with. In this case you would not want to work by hand. Instead, we will use the approaches developed in exercise 2 to solve the problem.

  1. Download the data files:
  2. Open each one in Excel (or similar) to familiarise yourself with the data.
  3. Import Pandas to read the CSV files: import pandas as pd.
  4. Load the data files using data = pd.read_csv(filename, index_col=0).
  5. The list of foods can be extracted from the food price data by taking the first column: foods = prices.index.values.tolist(). Similarly, the list of nutrient names can be taken from the first column of the nutritional requirements: nutrient_names = requirements.index.values.tolist().
  6. Convert the data files into dictionaries using data_dict = data.stack().to_dict().
  7. Set up your linear programming problem as in exercise 2 and solve it.
    • Note that there are both minimum and maximum nutritional requirements.

The solution that I get is:

Frozen Broccoli  =  0.0
Carrots, Raw  =  0.257921686004706
Celery, Raw  =  0.0
Frozen Corn  =  0.0
Lettuce, Iceberg,Raw  =  0.0
Peppers, Sweet, Raw  =  0.0
Potatoes, Baked  =  6.11992356370029
Tofu  =  0.0
Roasted Chicken  =  0.0
Spaghetti W/ Sauce  =  0.0
Tomato,Red,Ripe,Raw  =  0.0
Apple, Raw, w/Skin  =  0.0
Banana  =  0.0
Grapes  =  0.0
Kiwifruit, Raw, Fresh  =  0.0
Oranges  =  0.0
Bagels  =  0.0
Wheat Bread  =  0.0
White Bread  =  0.0
Oatmeal Cookies  =  0.0
Apple Pie  =  0.0
Chocolate Chip Cookies  =  0.0
Butter, Regular  =  0.0
Cheddar Cheese  =  0.0
3.3% Fat, Whole Milk  =  0.0
2% Lowfat Milk  =  0.0
Skim Milk  =  2.00270396628937
Poached Eggs  =  0.0
Scrambled Eggs  =  0.0
Bologna, Turkey  =  0.0
Frankfurter, Beef  =  0.0
Ham, Sliced, Extralean  =  0.0
Kielbasa, Pork  =  0.0
Cap'N Crunch  =  0.0
Cheerios  =  0.0
Corn Flakes, Kellogg'S  =  0.0
Raisin Bran, Kellogg'S  =  0.0
Rice Krispies  =  0.0
Special K  =  0.0
Oatmeal  =  0.0
Malt-O-Meal, Choc  =  0.0
Pizza w/Pepperoni  =  0.0
Taco  =  0.0
Hamburger w/Toppings  =  0.0
Hotdog, Plain  =  0.0
Couscous  =  0.0
White Rice  =  0.117814898855647
Macaroni, cooked  =  0.0
Peanut Butter  =  3.92286261080103
Pork  =  0.0
Sardines in Oil  =  0.0
White Tuna in Water  =  0.0
Popcorn, Air-Popped  =  0.15278313277272
Potato Chips, BBQ  =  0.0
Pretzels  =  0.0
Tortilla Chips  =  0.0
Chicken Noodle Soup  =  0.0
Splt Pea&Ham Soup  =  0.0
Veggie Beef Soup  =  0.0
New Eng Clam Chwd  =  0.0
Tomato Soup  =  0.0
New Eng Clam Chwd, w/Mlk  =  0.0
Crm Mshrm Soup, w/Mlk  =  0.0
Bean Bacon Soup, w/Watr  =  0.0