Module 6 - Modelling languages and some final problems


This is a hand-in written by Group 60 (FIRE) for the weekly module #6 in the mathematical modelling course (DAT026) at Chalmers University of Technology.

Group 60 consists of:

  • Mazdak Farrokhzad

    • 901011-0279


    • Program: IT

    • Time spent: 16 hours, 57 minutes

  • Niclas Alexandersson

    • 920203-0111


    • Program: IT

    • Time spent: 10 hours, 36 minutes

We hereby declare that we have both actively participated in solving every exercise, and all solutions are entirely our own work.

Disclaimer: Please do note that the numbering of the sections in the TOC and elsewhere are not intended to follow the numbering of the problem. The problem referred to is always explicitly stated in the title itself (e.g: Problem 1...)

Problem 1 - AMPL for (integer) linear programming

a) Brief description diet2.mod and AMPL

A quick, but relatively unimportant analysis of the AMPL syntax structure: Looking at the diet2.mod file, we quickly see that all statements in AMPL are ; (semicolon) terminated, just like C family languages. In any line where a # character is encountered, the rest of the line is treated as a comment, just like Perl. Assignment is done with the := operator, like in ALGOL 1958 and Pascal.

The keyword:

  • set <name> [<O>] [:= <A>] declares a set with optional parts enclosed in [..].

  • param <name> [<S>] [<C>] [<T>] declares parameter(s) (values given in advance) of name with with optional constraints <C> of optional type <T> for each element in optional set indexing <S>.

  • var works like param, but instead of giving a value in advance, the value of a variable is to be determined during trough optimization.

  • minimize <name> [<S>] : <O> states an objective function <O> to minimize with <name> given optional sets <S> to iterate over (or no set to iterate over).

  • minimize <name> [S] : <C> states a constraint <C> with <name> to honour given optional sets <S> to iterate over (or no set to iterate over).

We do an expression-for-expression analysis of the file:

  1. set NUTR ordered; declares an ordered set NUTR, henceforth known as \({{\mathbb{N}}}\).

  2. set FOOD ordered; declares an ordered set FOOD, henceforth known as \({{\mathbb{F}}}\).

  3. param cost[...]; declares a parameter \(c_j = cost_j \geq 0, \forall j \in {{\mathbb{F}}}\). This cost is the dollar cost of each food item.

  4. param f_min[...]; declares \(fl_j = f_{min_j} \geq 0, \forall j \in {{\mathbb{F}}}\) defaulting to \(0\) (if not provided).

  5. param f_max[...]; declares \(fu_j = f_{max_j} \geq fl_j, \forall j \in {{\mathbb{F}}}\) defaulting to \(2\). \([fl_j, fu_j]\) seems to be the lower and upper limits on the number of packages in the diet.

  6. param n_min[...]; declares \(nl_i = n_{min_i} \geq 0, \forall i \in {{\mathbb{N}}}\) defaulting to \(0\).

  7. param n_max[...]; declares \(nu_i = n_{max_i} \geq nl_i, \forall i \in {{\mathbb{N}}}\) defaulting to \(\infty\). \([nl_j, nu_j]\) seems to be the lower and upper limits on the amount of each nutrient in the diet.

  8. param amt[...]; declares \(a_{i,j} = amt_{i,j} \geq 0, \forall n \in {{\mathbb{N}}}, j \in {{\mathbb{F}}}\). This forms a matrix/table of nutrition values for each food item.

  9. var Buy [...]; declares an unknown integral variable \(b_j = Buy_j \in [fl_j, fu_j], \forall j \in {{\mathbb{F}}}\). That is: the number of items to buy of each \(j\) must be in the interval \([fl_j, fu_j]\) for that \(j\).

  10. minimize Total_Cost: [...] states that we want to: \[\mathtt{minimize} \sum_{j \in {{\mathbb{F}}}} \left[ c_j \cdot b_j \right]\] That is: to minimize the total cost of all purchased food items.

  11. subject to Diet {i in NUTR}:[...] states a constraint: \[\forall i \in {{\mathbb{N}}}: nl_i \leq \sum_{j \in {{\mathbb{F}}}} \left[ a_{i,j} \cdot b_j \right] \leq nu_i\] That is: the total nutrition recieved from all food for each nutrition type should be in the interval \([nl_i, nu_i]\) for each nutrition type \(i \in {{\mathbb{N}}}\). This can be considered a form of Dietary Reference Intake (DRI) for each daily diet.

  12. subject to McNuggetsSauces: [...]; states: the sum of a number of different spreads(“sauces”) bought should not exceed the sum of Chicken McNuggets pieces bought.

  13. subject to SaladToppings: [...]; states: the sum of a number of different toppings bought should not exceed the sum of a variety of sallads bought.

  14. subject to SaladDressings: [...]; states: the sum of a number of different dressings bought should not exceed the sum of a variety of sallads bought.

  15. subject to OneDrinkPerMeal: [...]; states: the sum of drinks in all meals in a day should not exceed \(3\) (breakfeast, lunch, dinner).

  16. subject to FatCaloriesLimit: [...]; states: the sum of calories from fat in the diet can at most be as much as the sum of \(1/3\) of all calories in the diet.

In summation, all of the above minimizes the cost of the 3 customary daily meals (breakfeast, lunch, dinner) while still being within DRI (swedish: Rekommenderat Dagligt Intag (RDI) ) plus some uninteresting food-type specific constraints as well as only including \(1\) drink per meal and not letting the number of calories coming from fat exceed \(1/3\) of total calories from the meals.

b) Total number of variables and constraints in this model

The only variables declared are done in the expression: var Buy {j in FOOD} [...]; . Thus we have \({\left\vert{{{\mathbb{F}}}}\right\vert}\) variables.

Conversely, if we count each constraint in subject to Diet {i in NUTR}: [...]; as a separate constraint for each \(i \in {{\mathbb{N}}}\), this statement contributes with \({\left\vert{N}\right\vert}\) constraints, so a total of: \({\left\vert{N}\right\vert} + 5\), otherwise - if the statement only counts as one constraint, the total is: \(1 + 6\).

If we’d like to add a menu item, we need only to add an entry \(x \in {{\mathbb{F}}}\) and add a row to the \(amt\) matrix.

c) Alternatives: write an optimization problem directly, vs. AMPL

If we were forced to choose between the LP format or the MPS format, the former would be the winner hands down. In the LP format, the separation of concerns is at least clear. You can in seconds see where the objective function is declared, and where the constraints constraints are declared as well as bounds, etc. In contrast, the MPS format is as unintelligiblea as old assembler code written without labels and comments. But the LP format is still light-years away from the AMPL format which very clearly separates sets, known data, variables and constraints and provides a for-each mechanism and concept-data separation which is invaluable. The concept-data separation/for-each mechanism is the most important motivation to use AMPL and avoid LP /MPS .

As is the case with deciding whether to choose ASM or stick to C++ or similar languages, where there are few if any reasons to write code in ASM since compilers will often produce better machine code than hand written ASM - the AMPL format will probably provide optimized code as well as retaining readablity which is one of the most important aspects of programming. The reason to use ASM in some cases is special instructions not writable in a higher-level language or when a C compiler does not exist - but there’s probabily no case that AMPL can’t handle.

d) Some Ad Hoc Constraints

The first additional Ad Hoc Constraint that came to mind was daily diets of vegetarians - in this case, we just need to make sure that all foods that include meat are not included in the diet. If foods containing meats are less expensive, the total cost (objective function) will be forced to go up - if not, they won’t be included in the first place. We leave any potential lacking vegetarian foods that make up for violated DRI constraints as an exercise for the reader. Tip: soy beans have a lot of proteins.

The constraint becomes (in AMPL): subject to Vegetarian: 0 = Buy["Hamburger"] + Buy["Cheeseburger"] + Buy["Quarter Pounder w/ Cheese"] + Buy["McLean Deluxe"] + Buy["McLean Deluxe w/ Cheese"] + Buy["Big Mac"] + Buy["Filet-O-Fish"] + Buy["McGrilled Chicken"] + Buy["McChicken Sandwich"] + Buy["Chicken McNuggets (6 pcs)"] + Buy["Chicken McNuggets (9 pcs)"] + Buy["Chicken McNuggets (20 pcs)"] + Buy["Chef Salad"] + Buy["Chunky Chicken Salad"] + Buy["Bacon Bits"] + Buy["Egg McMuffin"] + Buy["Sausage McMuffin"] + Buy["Sansage McMuffin with Egg"] + Buy["English Muffin"] + Buy["Sausage Biscuit"] + Buy["Sausage Biscuit with Egg"] + Buy["Bacon, Egg & Cheese Biscuit"] + Buy["Breakfast Burrito"];