How to make it easier to express optimization problems?

[julianhyde]

We have previously shown how Morel can solve constraint problems such as four-coloring a map or buying cake ingredients to maximize profit.

The examples are taken from the MiniZinc tutorial and demonstrate that Morel can express these problems not that Morel can solve them efficiently. (Solving them efficiently is best done by generating code for an existing Solver.)

This approach does not work well if there are many variables, especially if the variables are entries in a vector or matrix. The cake recipe solver hard-codes the ingredients, cost of ingredients, and quantity of each ingredient in each recipe:

 (* A banana cake which takes 250g of self-raising flour, 2 mashed bananas,
 * 75g sugar and 100g of butter, and a chocolate cake which takes 200g of
 * self-raising flour, 75g of cocoa, 150g sugar and 150g of butter. We can sell
 * a chocolate cake for $4.50 and a banana cake for $4.00. And we have 4kg
 * self-raising flour, 6 bananas, 2kg of sugar, 500g of butter and 500g of
 * cocoa. The question is how many of each sort of cake should we bake for the
 * fete to maximize the profit. *)
from b, c
where b >= 0 andalso b <= 100      (*) number of banana cakes
andalso c >= 0 andalso c <= 100    (*) number of chocolate cakes
andalso 50 * b + 200 * c <= 4000   (*) flour
andalso 2 * b <= 6                 (*) bananas
andalso 75 * b + 150 * c <= 2000   (*) sugar
andalso 100 * b + 150 * c <= 500   (*) butter
andalso 75 * c <= 500              (*) cocoa
yield {b, c, profit = 400 * b + 450 * c}
order profit desc;

Could we make the algorithm more data-driven?

datatype ingredient =
  BANANA | FLOUR | SUGAR | BUTTER;
datatype recipe =
  BANANA_CAKE | CHOCOLATE_CAKE;
fun available FLOUR = 4000
  | available BANANA = 6
  | available SUGAR = 2000
  | available BUTTER = 500
  | available COCOA = 500;
fun require (BANANA_CAKE, FLOUR) = 50
  | require (CHOCOLATE_CAKE, BANANA) = 200
  | require (BANANA_CAKE, BANANA) = 2
  | require (CHOCOLATE_CAKE, BANANA) = 0
  | require (BANANA_CAKE, SUGAR) = 75
  | require (CHOCOLATE_CAKE, 150) = 150
  | require (BANANA_CAKE, BUTTER) = 100
  | require (CHOCOLATE_CAKE, BUTTER) = 150
  | require (BANANA_CAKE, COCOA) = 0
  | require (CHOCOLATE_CAKE, COCOA) = 75;
fun profit BANANA_CAKE = 400
   | profit CHOCOLATE_CAKE = 450;

from recipeAmounts : (recipe, int) dict
 where forAll i sum(from r yield recipeAmounts(r) * require (r, i)) < available(i)
  andalso forAll i recipeAmounts(i) >= 0;

This is a nice concise representation of the problem, close to the mathematical representation (involving Σ and ∀ operators).

What did we need to add to the language?

• A new type constructor, dict, that is like an array but its index may be a datatype
• Note that we use the dict recipeAmounts as a function: recipeAmounts(i), where i is an ingredient
• A forAll operator whose syntax is still TBD (but compare with the exists operator)
• The available, require and profit functions ought to be lookups into tables (lists of records)

[julianhyde]

Branch julianhyde/227-optimize has an example based on Gurobi's diet.py.