Diet problem in Picat
I'm currently participating in a Coursera MOOC (massive open online course) Linear and Integer Programming by Sriram Sankaranarayanan and Shalom D. Ruben.
As an example of a linear programming problem the course presents "Diet problem": given list of foods with costs and amounts of nutrients of different types, find the least expensive diet that satisfies specified requirements of min/max amount for each nutrient.
The course instructors show how to solve this problem using different tools: MATLAB, GLPK, Excel, CVXOPT. I want to show how the problem can be solved using new logic-based multi-paradigm programming language Picat. My Picat program is a translation of Shalom's DietProblem.py.
import mip. main => Food = ['Frozen Broccoli', 'Carrots,Raw', 'Celery, Raw', 'Frozen Corn', 'Lettuce,Iceberg,Raw', 'Peppers, Sweet, Raw', 'Potatoes, Baked', 'Tofu', 'Roasted Chicken', 'Spaghetti W/ Sauce', 'Tomato,Red,Ripe,Raw', 'Apple,Raw,W/Skin', 'Banana', 'Grapes', 'Kiwifruit,Raw,Fresh', 'Oranges', 'Bagels', 'Wheat Bread', 'White Bread', 'Oatmeal Cookies', 'Apple Pie', 'Chocolate Chip Cookies', 'Butter,Regular', 'Cheddar Cheese', '3.3% Fat,Whole Milk', '2% Lowfat Milk', 'Skim Milk', 'Poached Eggs', 'Scrambled Eggs', 'Bologna,Turkey', 'Frankfurter, Beef', 'Ham,Sliced,Extralean', 'Kielbasa,Prk', 'Cap''N Crunch', 'Cheerios', 'Corn Flks, Kellogg''S', 'Raisin Brn, Kellg''S', 'Rice Krispies', 'Special K', 'Oatmeal', 'Malt-O-Meal,Choc', 'Pizza W/Pepperoni', 'Taco', 'Hamburger W/Toppings', 'Hotdog, Plain', 'Couscous', 'White Rice', 'Macaroni,Ckd', 'Peanut Butter', 'Pork', 'Sardines in Oil', 'White Tuna in Water', 'Popcorn,Air-Popped', 'Potato Chips,Bbqflvr', 'Pretzels', 'Tortilla Chip', 'Chicknoodl Soup', 'Splt Pea&Hamsoup', 'Vegetbeef Soup', 'Neweng Clamchwd', 'Tomato Soup', 'New E Clamchwd,W/Mlk', 'Crm Mshrm Soup,W/Mlk', 'Beanbacn Soup,W/Watr'], AmountofNutrients_PerFood = [[73.8, 0, 0.8, 68.2, 13.6, 8.5, 8, 5867.4, 160.2, 159, 2.3], [23.7, 0, 0.1, 19.2, 5.6, 1.6, 0.6, 15471, 5.1, 14.9, 0.3], [6.4, 0, 0.1, 34.8, 1.5, 0.7, 0.3, 53.6, 2.8, 16, 0.2], [72.2, 0, 0.6, 2.5, 17.1, 2, 2.5, 106.6, 5.2, 3.3, 0.3], [2.6, 0, 0, 1.8, 0.4, 0.3, 0.2, 66, 0.8, 3.8, 0.1], [20, 0, 0.1, 1.5, 4.8, 1.3, 0.7, 467.7, 66.1, 6.7, 0.3], [171.5, 0, 0.2, 15.2, 39.9, 3.2, 3.7, 0, 15.6, 22.7, 4.3], [88.2, 0, 5.5, 8.1, 2.2, 1.4, 9.4, 98.6, 0.1, 121.8, 6.2], [277.4, 129.9, 10.8, 125.6, 0, 0, 42.2, 77.4, 0, 21.9, 1.8], [358.2, 0, 12.3, 1237.1, 58.3, 11.6, 8.2, 3055.2, 27.9, 80.2, 2.3], [25.8, 0, 0.4, 11.1, 5.7, 1.4, 1, 766.3, 23.5, 6.2, 0.6], [81.4, 0, 0.5, 0, 21, 3.7, 0.3, 73.1, 7.9, 9.7, 0.2], [104.9, 0, 0.5, 1.1, 26.7, 2.7, 1.2, 92.3, 10.4, 6.8, 0.4], [15.1, 0, 0.1, 0.5, 4.1, 0.2, 0.2, 24, 1, 3.4, 0.1], [46.4, 0, 0.3, 3.8, 11.3, 2.6, 0.8, 133, 74.5, 19.8, 0.3], [61.6, 0, 0.2, 0, 15.4, 3.1, 1.2, 268.6, 69.7, 52.4, 0.1], [78, 0, 0.5, 151.4, 15.1, 0.6, 3, 0, 0, 21, 1], [65, 0, 1, 134.5, 12.4, 1.3, 2.2, 0, 0, 10.8, 0.7], [65, 0, 1, 132.5, 11.8, 1.1, 2.3, 0, 0, 26.2, 0.8], [81, 0, 3.3, 68.9, 12.4, 0.6, 1.1, 2.9, 0.1, 6.7, 0.5], [67.2, 0, 3.1, 75.4, 9.6, 0.5, 0.5, 35.2, 0.9, 3.1, 0.1], [78.1, 5.1, 4.5, 57.8, 9.3, 0, 0.9, 101.8, 0, 6.2, 0.4], [35.8, 10.9, 4.1, 41.3, 0, 0, 0, 152.9, 0, 1.2, 0], [112.7, 29.4, 9.3, 173.7, 0.4, 0, 7, 296.5, 0, 202, 0.2], [149.9, 33.2, 8.1, 119.6, 11.4, 0, 8, 307.4, 2.3, 291.3, 0.1], [121.2, 18.3, 4.7, 121.8, 11.7, 0, 8.1, 500.2, 2.3, 296.7, 0.1], [85.5, 4.4, 0.4, 126.2, 11.9, 0, 8.4, 499.8, 2.4, 302.3, 0.1], [74.5, 211.5, 5, 140, 0.6, 0, 6.2, 316, 0, 24.5, 0.7], [99.6, 211.2, 7.3, 168, 1.3, 0, 6.7, 409.2, 0.1, 42.6, 0.7], [56.4, 28.1, 4.3, 248.9, 0.3, 0, 3.9, 0, 0, 23.8, 0.4], [141.8, 27.4, 12.8, 461.7, 0.8, 0, 5.4, 0, 10.8, 9, 0.6], [37.1, 13.3, 1.4, 405.1, 0.3, 0, 5.5, 0, 7.4, 2, 0.2], [80.6, 17.4, 7.1, 279.8, 0.6, 0, 3.4, 0, 5.5, 11.4, 0.4], [119.6, 0, 2.6, 213.3, 23, 0.5, 1.4, 40.6, 0, 4.8, 7.5], [111, 0, 1.8, 307.6, 19.6, 2, 4.3, 1252.2, 15.1, 48.6, 4.5], [110.5, 0, 0.1, 290.5, 24.5, 0.7, 2.3, 1252.2, 15.1, 0.9, 1.8], [115.1, 0, 0.7, 204.4, 27.9, 4, 4, 1250.2, 0, 12.9, 16.8], [112.2, 0, 0.2, 340.8, 24.8, 0.4, 1.9, 1252.2, 15.1, 4, 1.8], [110.8, 0, 0.1, 265.5, 21.3, 0.7, 5.6, 1252.2, 15.1, 8.2, 4.5], [145.1, 0, 2.3, 2.3, 25.3, 4, 6.1, 37.4, 0, 18.7, 1.6], [607.2, 0, 1.5, 16.5, 128.2, 0, 17.3, 0, 0, 23.1, 47.2], [181, 14.2, 7, 267, 19.9, 0, 10.1, 281.9, 1.6, 64.6, 0.9], [369.4, 56.4, 20.6, 802, 26.7, 0, 20.7, 855, 2.2, 220.6, 2.4], [275, 42.8, 10.2, 563.9, 32.7, 0, 13.6, 126.3, 2.6, 51.4, 2.5], [242.1, 44.1, 14.5, 670.3, 18, 0, 10.4, 0, 0.1, 23.5, 2.3], [100.8, 0, 0.1, 4.5, 20.9, 1.3, 3.4, 0, 0, 7.2, 0.3], [102.7, 0, 0.2, 0.8, 22.3, 0.3, 2.1, 0, 0, 7.9, 0.9], [98.7, 0, 0.5, 0.7, 19.8, 0.9, 3.3, 0, 0, 4.9, 1], [188.5, 0, 16, 155.5, 6.9, 2.1, 7.7, 0, 0, 13.1, 0.6], [710.8, 105.1, 72.2, 38.4, 0, 0, 13.8, 14.7, 0, 59.9, 0.4], [49.9, 34.1, 2.7, 121.2, 0, 0, 5.9, 53.8, 0, 91.7, 0.7], [115.6, 35.7, 2.1, 333.2, 0, 0, 22.7, 68, 0, 3.4, 0.5], [108.3, 0, 1.2, 1.1, 22.1, 4.3, 3.4, 55.6, 0, 2.8, 0.8], [139.2, 0, 9.2, 212.6, 15, 1.2, 2.2, 61.5, 9.6, 14.2, 0.5], [108, 0, 1, 486.2, 22.5, 0.9, 2.6, 0, 0, 10.2, 1.2], [142, 0, 7.4, 149.7, 17.8, 1.8, 2, 55.6, 0, 43.7, 0.4], [150.1, 12.3, 4.6, 1862.2, 18.7, 1.5, 7.9, 1308.7, 0, 27.1, 1.5], [184.8, 7.2, 4, 964.8, 26.8, 4.1, 11.1, 4872, 7, 33.6, 2.1], [158.1, 10, 3.8, 1915.1, 20.4, 4, 11.2, 3785.1, 4.8, 32.6, 2.2], [175.7, 10, 5, 1864.9, 21.8, 1.5, 10.9, 20.1, 4.8, 82.8, 2.8], [170.7, 0, 3.8, 1744.4, 33.2, 1, 4.1, 1393, 133, 27.6, 3.5], [163.7, 22.3, 6.6, 992, 16.6, 1.5, 9.5, 163.7, 3.5, 186, 1.5], [203.4, 19.8, 13.6, 1076.3, 15, 0.5, 6.1, 153.8, 2.2, 178.6, 0.6], [172, 2.5, 5.9, 951.3, 22.8, 8.6, 7.9, 888, 1.5, 81, 2]], Cost = [0.16, 0.07, 0.04, 0.18, 0.02, 0.53, 0.06, 0.31, 0.84, 0.78, 0.27, 0.24, 0.15, 0.32, 0.49, 0.15, 0.16, 0.05, 0.06, 0.09, 0.16, 0.03, 0.05, 0.25, 0.16, 0.23, 0.13, 0.08, 0.11, 0.15, 0.27, 0.33, 0.15, 0.31, 0.28, 0.28, 0.34, 0.32, 0.38, 0.82, 0.52, 0.44, 0.59, 0.83, 0.31, 0.39, 0.08, 0.17, 0.07, 0.81, 0.45, 0.69, 0.04, 0.22, 0.12, 0.19, 0.39, 0.67, 0.71, 0.75, 0.39, 0.99, 0.65, 0.67], Min_Nutrients = [2000, 0, 0, 0, 0, 25, 50, 5000, 50, 800, 10], Max_Nutrients = [2250, 300, 65, 2400, 300, 100, 100, 50000, 20000, 1600, 30], N = length(Food), Xs = new_list(N), foreach (I in 1..N) Xs[I] #>= 0.0 end, M = length(Min_Nutrients), foreach (J in 1..M) Amount #= sum([Xs[I] * AmountofNutrients_PerFood[I,J] : I in 1..N]), Amount #>= Min_Nutrients[J], Amount #<= Max_Nutrients[J] end, TotalCost #= sum([Xs[I] * Cost[I] : I in 1..N]), solve($[min(TotalCost)], Xs), foreach (I in 1..N) if Xs[I] > 0.0 then printf("%-20w : %5.2f\n", Food[I], Xs[I]) end end.
First line of the program imports linear programming module 'mip'. Many lines of code after that are just data for the problem instance.
Lines 145-149 create a list of N non-negative decision variables. Lines 151-156 specify that total amount of each nutrient is constrained by Min_Nutrients and Max_Nutrients (this part uses list comprehension – very handy feature of Picat).
Line 158 specifies total cost of the diet using list comprehension. The next line obtains the solution for the problem that minimizes the total cost.
Finally, we output (using C-like 'printf') names and amounts of each type of food present (amount is greater than 0) in our diet.
Running the program yields the same solution as DietProblem.py:
$ picat DietProblem.pi
0: objval = 0.000000000e+00 infeas = 1.000000000e+00 (130)
111: objval = 2.102242357e+00 infeas = 0.000000000e+00 (44)
* 111: objval = 2.102242357e+00 infeas = 0.000000000e+00 (44)
* 151: objval = 9.560078273e-01 infeas = 0.000000000e+00 (21)
OPTIMAL SOLUTION FOUND
Carrots,Raw : 0.24
Potatoes, Baked : 3.54
Skim Milk : 2.17
Peanut Butter : 3.60
Popcorn,Air-Popped : 4.82
Link to the Picat program: DietProblem.pi.
Also see http://www.hakank.org/picat/diet2.pi for Håkan Kjellerstrand's Picat solution for a different formulation of Diet problem.