! 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(?)