1 // Copyright 2010-2021 Google LLC 2 // Licensed under the Apache License, Version 2.0 (the "License"); 3 // you may not use this file except in compliance with the License. 4 // You may obtain a copy of the License at 5 // 6 // http://www.apache.org/licenses/LICENSE-2.0 7 // 8 // Unless required by applicable law or agreed to in writing, software 9 // distributed under the License is distributed on an "AS IS" BASIS, 10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 11 // See the License for the specific language governing permissions and 12 // limitations under the License. 13 14 // [START program] 15 // The Stigler diet problem. 16 package com.google.ortools.linearsolver.samples; 17 // [START import] 18 import com.google.ortools.Loader; 19 import com.google.ortools.linearsolver.MPConstraint; 20 import com.google.ortools.linearsolver.MPObjective; 21 import com.google.ortools.linearsolver.MPSolver; 22 import com.google.ortools.linearsolver.MPVariable; 23 import java.util.ArrayList; 24 import java.util.List; 25 // [END import] 26 27 /** Stigler diet example. */ 28 public final class StiglerDiet { main(String[] args)29 public static void main(String[] args) { 30 Loader.loadNativeLibraries(); 31 // [START data_model] 32 // Nutrient minimums. 33 List<Object[]> nutrients = new ArrayList<>(); 34 nutrients.add(new Object[] {"Calories (kcal)", 3.0}); 35 nutrients.add(new Object[] {"Protein (g)", 70.0}); 36 nutrients.add(new Object[] {"Calcium (g)", 0.8}); 37 nutrients.add(new Object[] {"Iron (mg)", 12.0}); 38 nutrients.add(new Object[] {"Vitamin A (kIU)", 5.0}); 39 nutrients.add(new Object[] {"Vitamin B1 (mg)", 1.8}); 40 nutrients.add(new Object[] {"Vitamin B2 (mg)", 2.7}); 41 nutrients.add(new Object[] {"Niacin (mg)", 18.0}); 42 nutrients.add(new Object[] {"Vitamin C (mg)", 75.0}); 43 44 List<Object[]> data = new ArrayList<>(); 45 data.add(new Object[] {"Wheat Flour (Enriched)", "10 lb.", 36, 46 new double[] {44.7, 1411, 2, 365, 0, 55.4, 33.3, 441, 0}}); 47 data.add(new Object[] { 48 "Macaroni", "1 lb.", 14.1, new double[] {11.6, 418, 0.7, 54, 0, 3.2, 1.9, 68, 0}}); 49 data.add(new Object[] {"Wheat Cereal (Enriched)", "28 oz.", 24.2, 50 new double[] {11.8, 377, 14.4, 175, 0, 14.4, 8.8, 114, 0}}); 51 data.add(new Object[] { 52 "Corn Flakes", "8 oz.", 7.1, new double[] {11.4, 252, 0.1, 56, 0, 13.5, 2.3, 68, 0}}); 53 data.add(new Object[] { 54 "Corn Meal", "1 lb.", 4.6, new double[] {36.0, 897, 1.7, 99, 30.9, 17.4, 7.9, 106, 0}}); 55 data.add(new Object[] { 56 "Hominy Grits", "24 oz.", 8.5, new double[] {28.6, 680, 0.8, 80, 0, 10.6, 1.6, 110, 0}}); 57 data.add( 58 new Object[] {"Rice", "1 lb.", 7.5, new double[] {21.2, 460, 0.6, 41, 0, 2, 4.8, 60, 0}}); 59 data.add(new Object[] { 60 "Rolled Oats", "1 lb.", 7.1, new double[] {25.3, 907, 5.1, 341, 0, 37.1, 8.9, 64, 0}}); 61 data.add(new Object[] {"White Bread (Enriched)", "1 lb.", 7.9, 62 new double[] {15.0, 488, 2.5, 115, 0, 13.8, 8.5, 126, 0}}); 63 data.add(new Object[] {"Whole Wheat Bread", "1 lb.", 9.1, 64 new double[] {12.2, 484, 2.7, 125, 0, 13.9, 6.4, 160, 0}}); 65 data.add(new Object[] { 66 "Rye Bread", "1 lb.", 9.1, new double[] {12.4, 439, 1.1, 82, 0, 9.9, 3, 66, 0}}); 67 data.add(new Object[] { 68 "Pound Cake", "1 lb.", 24.8, new double[] {8.0, 130, 0.4, 31, 18.9, 2.8, 3, 17, 0}}); 69 data.add(new Object[] { 70 "Soda Crackers", "1 lb.", 15.1, new double[] {12.5, 288, 0.5, 50, 0, 0, 0, 0, 0}}); 71 data.add( 72 new Object[] {"Milk", "1 qt.", 11, new double[] {6.1, 310, 10.5, 18, 16.8, 4, 16, 7, 177}}); 73 data.add(new Object[] {"Evaporated Milk (can)", "14.5 oz.", 6.7, 74 new double[] {8.4, 422, 15.1, 9, 26, 3, 23.5, 11, 60}}); 75 data.add( 76 new Object[] {"Butter", "1 lb.", 30.8, new double[] {10.8, 9, 0.2, 3, 44.2, 0, 0.2, 2, 0}}); 77 data.add(new Object[] { 78 "Oleomargarine", "1 lb.", 16.1, new double[] {20.6, 17, 0.6, 6, 55.8, 0.2, 0, 0, 0}}); 79 data.add(new Object[] { 80 "Eggs", "1 doz.", 32.6, new double[] {2.9, 238, 1.0, 52, 18.6, 2.8, 6.5, 1, 0}}); 81 data.add(new Object[] {"Cheese (Cheddar)", "1 lb.", 24.2, 82 new double[] {7.4, 448, 16.4, 19, 28.1, 0.8, 10.3, 4, 0}}); 83 data.add(new Object[] { 84 "Cream", "1/2 pt.", 14.1, new double[] {3.5, 49, 1.7, 3, 16.9, 0.6, 2.5, 0, 17}}); 85 data.add(new Object[] { 86 "Peanut Butter", "1 lb.", 17.9, new double[] {15.7, 661, 1.0, 48, 0, 9.6, 8.1, 471, 0}}); 87 data.add(new Object[] { 88 "Mayonnaise", "1/2 pt.", 16.7, new double[] {8.6, 18, 0.2, 8, 2.7, 0.4, 0.5, 0, 0}}); 89 data.add(new Object[] {"Crisco", "1 lb.", 20.3, new double[] {20.1, 0, 0, 0, 0, 0, 0, 0, 0}}); 90 data.add(new Object[] {"Lard", "1 lb.", 9.8, new double[] {41.7, 0, 0, 0, 0.2, 0, 0.5, 5, 0}}); 91 data.add(new Object[] { 92 "Sirloin Steak", "1 lb.", 39.6, new double[] {2.9, 166, 0.1, 34, 0.2, 2.1, 2.9, 69, 0}}); 93 data.add(new Object[] { 94 "Round Steak", "1 lb.", 36.4, new double[] {2.2, 214, 0.1, 32, 0.4, 2.5, 2.4, 87, 0}}); 95 data.add( 96 new Object[] {"Rib Roast", "1 lb.", 29.2, new double[] {3.4, 213, 0.1, 33, 0, 0, 2, 0, 0}}); 97 data.add(new Object[] { 98 "Chuck Roast", "1 lb.", 22.6, new double[] {3.6, 309, 0.2, 46, 0.4, 1, 4, 120, 0}}); 99 data.add( 100 new Object[] {"Plate", "1 lb.", 14.6, new double[] {8.5, 404, 0.2, 62, 0, 0.9, 0, 0, 0}}); 101 data.add(new Object[] {"Liver (Beef)", "1 lb.", 26.8, 102 new double[] {2.2, 333, 0.2, 139, 169.2, 6.4, 50.8, 316, 525}}); 103 data.add(new Object[] { 104 "Leg of Lamb", "1 lb.", 27.6, new double[] {3.1, 245, 0.1, 20, 0, 2.8, 3.9, 86, 0}}); 105 data.add(new Object[] { 106 "Lamb Chops (Rib)", "1 lb.", 36.6, new double[] {3.3, 140, 0.1, 15, 0, 1.7, 2.7, 54, 0}}); 107 data.add(new Object[] { 108 "Pork Chops", "1 lb.", 30.7, new double[] {3.5, 196, 0.2, 30, 0, 17.4, 2.7, 60, 0}}); 109 data.add(new Object[] { 110 "Pork Loin Roast", "1 lb.", 24.2, new double[] {4.4, 249, 0.3, 37, 0, 18.2, 3.6, 79, 0}}); 111 data.add(new Object[] { 112 "Bacon", "1 lb.", 25.6, new double[] {10.4, 152, 0.2, 23, 0, 1.8, 1.8, 71, 0}}); 113 data.add(new Object[] { 114 "Ham, smoked", "1 lb.", 27.4, new double[] {6.7, 212, 0.2, 31, 0, 9.9, 3.3, 50, 0}}); 115 data.add(new Object[] { 116 "Salt Pork", "1 lb.", 16, new double[] {18.8, 164, 0.1, 26, 0, 1.4, 1.8, 0, 0}}); 117 data.add(new Object[] {"Roasting Chicken", "1 lb.", 30.3, 118 new double[] {1.8, 184, 0.1, 30, 0.1, 0.9, 1.8, 68, 46}}); 119 data.add(new Object[] { 120 "Veal Cutlets", "1 lb.", 42.3, new double[] {1.7, 156, 0.1, 24, 0, 1.4, 2.4, 57, 0}}); 121 data.add(new Object[] { 122 "Salmon, Pink (can)", "16 oz.", 13, new double[] {5.8, 705, 6.8, 45, 3.5, 1, 4.9, 209, 0}}); 123 data.add(new Object[] { 124 "Apples", "1 lb.", 4.4, new double[] {5.8, 27, 0.5, 36, 7.3, 3.6, 2.7, 5, 544}}); 125 data.add(new Object[] { 126 "Bananas", "1 lb.", 6.1, new double[] {4.9, 60, 0.4, 30, 17.4, 2.5, 3.5, 28, 498}}); 127 data.add( 128 new Object[] {"Lemons", "1 doz.", 26, new double[] {1.0, 21, 0.5, 14, 0, 0.5, 0, 4, 952}}); 129 data.add(new Object[] { 130 "Oranges", "1 doz.", 30.9, new double[] {2.2, 40, 1.1, 18, 11.1, 3.6, 1.3, 10, 1998}}); 131 data.add(new Object[] { 132 "Green Beans", "1 lb.", 7.1, new double[] {2.4, 138, 3.7, 80, 69, 4.3, 5.8, 37, 862}}); 133 data.add(new Object[] { 134 "Cabbage", "1 lb.", 3.7, new double[] {2.6, 125, 4.0, 36, 7.2, 9, 4.5, 26, 5369}}); 135 data.add(new Object[] { 136 "Carrots", "1 bunch", 4.7, new double[] {2.7, 73, 2.8, 43, 188.5, 6.1, 4.3, 89, 608}}); 137 data.add(new Object[] { 138 "Celery", "1 stalk", 7.3, new double[] {0.9, 51, 3.0, 23, 0.9, 1.4, 1.4, 9, 313}}); 139 data.add(new Object[] { 140 "Lettuce", "1 head", 8.2, new double[] {0.4, 27, 1.1, 22, 112.4, 1.8, 3.4, 11, 449}}); 141 data.add(new Object[] { 142 "Onions", "1 lb.", 3.6, new double[] {5.8, 166, 3.8, 59, 16.6, 4.7, 5.9, 21, 1184}}); 143 data.add(new Object[] { 144 "Potatoes", "15 lb.", 34, new double[] {14.3, 336, 1.8, 118, 6.7, 29.4, 7.1, 198, 2522}}); 145 data.add(new Object[] { 146 "Spinach", "1 lb.", 8.1, new double[] {1.1, 106, 0, 138, 918.4, 5.7, 13.8, 33, 2755}}); 147 data.add(new Object[] {"Sweet Potatoes", "1 lb.", 5.1, 148 new double[] {9.6, 138, 2.7, 54, 290.7, 8.4, 5.4, 83, 1912}}); 149 data.add(new Object[] {"Peaches (can)", "No. 2 1/2", 16.8, 150 new double[] {3.7, 20, 0.4, 10, 21.5, 0.5, 1, 31, 196}}); 151 data.add(new Object[] { 152 "Pears (can)", "No. 2 1/2", 20.4, new double[] {3.0, 8, 0.3, 8, 0.8, 0.8, 0.8, 5, 81}}); 153 data.add(new Object[] { 154 "Pineapple (can)", "No. 2 1/2", 21.3, new double[] {2.4, 16, 0.4, 8, 2, 2.8, 0.8, 7, 399}}); 155 data.add(new Object[] {"Asparagus (can)", "No. 2", 27.7, 156 new double[] {0.4, 33, 0.3, 12, 16.3, 1.4, 2.1, 17, 272}}); 157 data.add(new Object[] { 158 "Green Beans (can)", "No. 2", 10, new double[] {1.0, 54, 2, 65, 53.9, 1.6, 4.3, 32, 431}}); 159 data.add(new Object[] {"Pork and Beans (can)", "16 oz.", 7.1, 160 new double[] {7.5, 364, 4, 134, 3.5, 8.3, 7.7, 56, 0}}); 161 data.add(new Object[] { 162 "Corn (can)", "No. 2", 10.4, new double[] {5.2, 136, 0.2, 16, 12, 1.6, 2.7, 42, 218}}); 163 data.add(new Object[] { 164 "Peas (can)", "No. 2", 13.8, new double[] {2.3, 136, 0.6, 45, 34.9, 4.9, 2.5, 37, 370}}); 165 data.add(new Object[] { 166 "Tomatoes (can)", "No. 2", 8.6, new double[] {1.3, 63, 0.7, 38, 53.2, 3.4, 2.5, 36, 1253}}); 167 data.add(new Object[] {"Tomato Soup (can)", "10 1/2 oz.", 7.6, 168 new double[] {1.6, 71, 0.6, 43, 57.9, 3.5, 2.4, 67, 862}}); 169 data.add(new Object[] { 170 "Peaches, Dried", "1 lb.", 15.7, new double[] {8.5, 87, 1.7, 173, 86.8, 1.2, 4.3, 55, 57}}); 171 data.add(new Object[] { 172 "Prunes, Dried", "1 lb.", 9, new double[] {12.8, 99, 2.5, 154, 85.7, 3.9, 4.3, 65, 257}}); 173 data.add(new Object[] {"Raisins, Dried", "15 oz.", 9.4, 174 new double[] {13.5, 104, 2.5, 136, 4.5, 6.3, 1.4, 24, 136}}); 175 data.add(new Object[] { 176 "Peas, Dried", "1 lb.", 7.9, new double[] {20.0, 1367, 4.2, 345, 2.9, 28.7, 18.4, 162, 0}}); 177 data.add(new Object[] {"Lima Beans, Dried", "1 lb.", 8.9, 178 new double[] {17.4, 1055, 3.7, 459, 5.1, 26.9, 38.2, 93, 0}}); 179 data.add(new Object[] {"Navy Beans, Dried", "1 lb.", 5.9, 180 new double[] {26.9, 1691, 11.4, 792, 0, 38.4, 24.6, 217, 0}}); 181 data.add(new Object[] {"Coffee", "1 lb.", 22.4, new double[] {0, 0, 0, 0, 0, 4, 5.1, 50, 0}}); 182 data.add(new Object[] {"Tea", "1/4 lb.", 17.4, new double[] {0, 0, 0, 0, 0, 0, 2.3, 42, 0}}); 183 data.add( 184 new Object[] {"Cocoa", "8 oz.", 8.6, new double[] {8.7, 237, 3, 72, 0, 2, 11.9, 40, 0}}); 185 data.add(new Object[] { 186 "Chocolate", "8 oz.", 16.2, new double[] {8.0, 77, 1.3, 39, 0, 0.9, 3.4, 14, 0}}); 187 data.add(new Object[] {"Sugar", "10 lb.", 51.7, new double[] {34.9, 0, 0, 0, 0, 0, 0, 0, 0}}); 188 data.add(new Object[] { 189 "Corn Syrup", "24 oz.", 13.7, new double[] {14.7, 0, 0.5, 74, 0, 0, 0, 5, 0}}); 190 data.add(new Object[] { 191 "Molasses", "18 oz.", 13.6, new double[] {9.0, 0, 10.3, 244, 0, 1.9, 7.5, 146, 0}}); 192 data.add(new Object[] {"Strawberry Preserves", "1 lb.", 20.5, 193 new double[] {6.4, 11, 0.4, 7, 0.2, 0.2, 0.4, 3, 0}}); 194 195 // [END data_model] 196 197 // [START solver] 198 // Create the linear solver with the GLOP backend. 199 MPSolver solver = MPSolver.createSolver("GLOP"); 200 if (solver == null) { 201 System.out.println("Could not create solver GLOP"); 202 return; 203 } 204 // [END solver] 205 206 // [START variables] 207 double infinity = java.lang.Double.POSITIVE_INFINITY; 208 List<MPVariable> foods = new ArrayList<>(); 209 for (int i = 0; i < data.size(); ++i) { 210 foods.add(solver.makeNumVar(0.0, infinity, (String) data.get(i)[0])); 211 } 212 System.out.println("Number of variables = " + solver.numVariables()); 213 // [END variables] 214 215 // [START constraints] 216 MPConstraint[] constraints = new MPConstraint[nutrients.size()]; 217 for (int i = 0; i < nutrients.size(); ++i) { 218 constraints[i] = solver.makeConstraint( 219 (double) nutrients.get(i)[1], infinity, (String) nutrients.get(i)[0]); 220 for (int j = 0; j < data.size(); ++j) { 221 constraints[i].setCoefficient(foods.get(j), ((double[]) data.get(j)[3])[i]); 222 } 223 // constraints.add(constraint); 224 } 225 System.out.println("Number of constraints = " + solver.numConstraints()); 226 // [END constraints] 227 228 // [START objective] 229 MPObjective objective = solver.objective(); 230 for (int i = 0; i < data.size(); ++i) { 231 objective.setCoefficient(foods.get(i), 1); 232 } 233 objective.setMinimization(); 234 // [END objective] 235 236 // [START solve] 237 final MPSolver.ResultStatus resultStatus = solver.solve(); 238 // [END solve] 239 240 // [START print_solution] 241 // Check that the problem has an optimal solution. 242 if (resultStatus != MPSolver.ResultStatus.OPTIMAL) { 243 System.err.println("The problem does not have an optimal solution!"); 244 if (resultStatus == MPSolver.ResultStatus.FEASIBLE) { 245 System.err.println("A potentially suboptimal solution was found."); 246 } else { 247 System.err.println("The solver could not solve the problem."); 248 return; 249 } 250 } 251 252 // Display the amounts (in dollars) to purchase of each food. 253 double[] nutrientsResult = new double[nutrients.size()]; 254 System.out.println("\nAnnual Foods:"); 255 for (int i = 0; i < foods.size(); ++i) { 256 if (foods.get(i).solutionValue() > 0.0) { 257 System.out.println((String) data.get(i)[0] + ": $" + 365 * foods.get(i).solutionValue()); 258 for (int j = 0; j < nutrients.size(); ++j) { 259 nutrientsResult[j] += ((double[]) data.get(i)[3])[j] * foods.get(i).solutionValue(); 260 } 261 } 262 } 263 System.out.println("\nOptimal annual price: $" + 365 * objective.value()); 264 265 System.out.println("\nNutrients per day:"); 266 for (int i = 0; i < nutrients.size(); ++i) { 267 System.out.println( 268 nutrients.get(i)[0] + ": " + nutrientsResult[i] + " (min " + nutrients.get(i)[1] + ")"); 269 } 270 // [END print_solution] 271 272 // [START advanced] 273 System.out.println("\nAdvanced usage:"); 274 System.out.println("Problem solved in " + solver.wallTime() + " milliseconds"); 275 System.out.println("Problem solved in " + solver.iterations() + " iterations"); 276 // [END advanced] 277 } 278 StiglerDiet()279 private StiglerDiet() {} 280 } 281 // [END program] 282