! blend.txt - "blending problem" - integer programming example
!/
from http://people.brunel.ac.uk/~mastjjb/jeb/or/moreip.html
Integer programming example by J E Beasley

Blending problem

Consider the example of a manufacturer of animal feed who is producing a
feed mix for dairy cattle.  In our simple example the feed mix contains
two active ingredients and a filler to provide bulk.  One kg of feed mix
must contain a minimum quantity of each of four nutrients as below:

Nutrient       A     B     C     D
grams         90    50    20     2

The ingredients have the following nutrient values and cost:

                           A      B      C      D    Cost/kg
Ingredient 1 (gram/kg)   100     80     40     10      40
Ingredient 2 (gram/kg)   200    150     20      -      60

What should be the amounts of active ingredients and filler in one kg of
feed mix?

Blending problem solution

Variables

In order to solve this problem it is best to think in terms of one
kilogram of feed mix.  That kilogram is made up of three parts -
ingredient 1, ingredient 2 and filler, so let
  x1 = amount (kg) of ingredient 1 in one kg of feed mix
  x2 = amount (kg) of ingredient 2 in one kg of feed mix
  x3 = amount (kg) of filler in one kg of feed mix
where x1 >= 0, x2 >= 0 and x3 >= 0.

Constraints

   * balancing constraint (an implicit constraint due to the definition
     of the variables)

  x1 + x2 + x3 = 1  (each kg composed of ingredients 1 & 2 and filler)

   * nutrient constraints (per kg)

  100x1 + 200x2 >= 90  (nutrient A)
   80x1 + 150x2 >= 50  (nutrient B)
   40x1 +  20x2 >= 20  (nutrient C)
   10x1 >= 2           (nutrient D)

Note the use of an inequality rather than an equality in these constraints,
following the rule we put forward in the Two Mines example, where we assume
that the nutrient levels we want are lower limits on the amount of nutrient
in one kg of feed mix.

Objective

Presumably to minimize cost, i.e.

  minimize  40x1 + 60x2

which gives us our complete LP model for the blending problem.

--------------------------------------
My adjusted formulation:

Since I haven't defined floating point arithmetic, we will let x1,x2,xf
be integer kg quantities that add up to some large number N, say, 100.
(I'm calling the filler variable xf.)

   xf + x1 + x2 = N
   N = 100

Values x1/N,x2/N,xf/N will thus be the fraction of ingredient in each
kg of feed.  Making N larger will increase the resolution of the solution.  

The nutrient constraints can now be written as follows:

  100 x1 + 200 x2 >= 90 * N  (nutrient A)
   80 x1 + 150 x2 >= 50 * N  (nutrient B)
   40 x1 +  20 x2 >= 20 * N  (nutrient C)
   10 x1          >=  2 * N  (nutrient D)

The needed grams of nutrients are multiplied by N since we are dealing
with grams of nutrients needed in N kg quantities.

The cost formula can be left unchanged except that it now computes the
cost of a N kg quantity of feed:

   minimize  40 x1 + 60 x2       -- cost for N kg
!\

! x1,x2,xf,cost: - optimal relative ingredient kg quantities and cost

  (x1,x2,xf,cost: %x1 %x2 %xf %cost)<   ! relative int ingredients & N-kg cost 
    (== %N 100),    ! total quantity being considered -> resolution of solution
       ! -- could choose higher-resolution solution here, say, parts per 1000
    (iota_d %N %0-N),   ! decimal numbers from 0..N (APL fn name)
    (cartesian %0-N %0-N %0-N %args),  ! % ranges of the 3 ingredients
       ! -- This generalized cartesian product forms 3-element tuples
       !    of all combinations of integers from 0..N.
    (constraints    ! -- arg vars _0, _1, _2 represent ingredients filler,1,2
      ((_0 + _1 + _2 = %N)               ! 3 natural number vars sum to N
       (100 * _1 + 200 * _2 >= 90 * %N)   ! A nutrient grams required
       ( 80 * _1 + 150 * _2 >= 50 * %N)   ! B
       ( 40 * _1 +  20 * _2 >= 20 * %N)   ! C
       ( 10 * _1            >=  2 * %N)   ! D
      )   ! each constraint formula must evaluate to true
      %args %selected_args),  ! %selected args are tuples that satisfy constrs
    (minimize (40 * _1 + 60 * _2) %selected_args %cost (%xf %x1 %x2)).
       ! -- filler is free(?)