Solving Integer Programming Problems Using Genetic Algorithms

Introduction

Linear Programming (LP) are a well known group of problems used mainly in industries for getting a better use of energy, reducing costs of manufacturing, scheduling and many others. They are expressed as follow in its basic form:

 minimize/maximize F(Xi) = C1*X1 + C2*X2 + C3*X3 + ... + Cn*Xn
 subject to A1*X1 + A2*X2 +... + An*Xn < DB1*X1 + B2*X2 + ... + B3*X3 < E

where Xi is a vector of variables to be solved for,
Ci is a vector of costs for each variable (depending on application),
and Ai, Bi are the vectors of constraints coefficients, D and E are the constraints itself.

Integer Programming is an extension to this kind of problem, where we have a special restriction that all variables must be integers.A well known and used method for solving this kind of problem is the Simplex method that, although it has exponential complexity in theory, in practice it is polynomial. But this method can't deal with the integer constraint (i.e. the variables must be of integer type), so we must use of another method to solve those kind of problems.

More on Linear Programming, Integer Programming and the methods to solve them can be found here.

A Problem To Be

First of all, let's formulate and prepare the variables of a simple example problem that will be used later when the programming action begins.Two ACME™ factories produce a best-seller (bought mainly by our smart Willy E. Coyote™) toy bomb-doll. But each toy requires an amount of 100Kg of gunpowder for a high explosive solution used on its fabrication.

We have 3 suppliers that produces it, each one with a different price:

 S1: $8.00 / ton
 S2: $3.00 / ton
 S3: $5.00 / ton

To ship the products from a supplier to a factory also has a cost:

  To: A B
From: S1 $ 5.00 $ 6.00
  S2 $ 9.00 $ 8.00
  S3 $ 6.00 $ 7.00

The stocking of these powders has a different price in each factory:

 A: $ 9.00
 B: $ 7.00

And we have a limit of how much we can stock, in factory A we can have as much as 550 tons, and in B we can have 700 tons.The suppliers can offer a limited amount of gunpowder, S1 can produce 390 tons, S2 can make 460 tons and S3, 370 tons.Each bomb-doll has a cost of $ 20.00 to be produced and it's sold for $ 320.00. Let's say that the Coyote™ will buy as much dolls as we produce them (so he can catch that nasty Road Runner™), we must, then, maximize the profit based on these.First of all, we must put this on LP form: Let's call P(Xi) as the profit function of the doll sells, where Xi is the vector variables, this is calculated by subtracting all the costs from the price of each doll.Since each doll is sold for $320.00 and it costs $ 20.00 to produce, we start with:

 P(D) = 320*D - 20*D = 300*D

where D is the number of dolls produced.But besides production cost we also have the gunpowder costs, the essential part of production. So let's do some namings:

 Tij is the amount of gunpowder acquired from supplier i and taken to factory j
 Ti is the amount of gunpowder acquired from supplier i
 Tj is the amount of gunpowder taken to factory j
 T is the total amount of gunpowder bought

So we will have 13 variables as follows:

 T1A, T2A, T3A, T1B, T2B, T3B, T1, T2, T3, TA, TB, T, D

From that we can deduce the costs with material, having the prices of each supplier, we have

C1(T1,T2,T3) = 8*T1 + 3*T2 + 5*T3

as the first cost equation. Let's consider the transport of cargo as the second cost, so:

C2(T1A,T2A,T3A,T1B,T2B,T3B) = 5*T1A + 9*T2A + 6*T3A + 6*T1B + 8*T2B + 7*T3B

And finally the costs of stocking:

C3(TA,TB) = 9*TA + 7*TB

Completing then the profit equation:

  P(T1A, T2A, T3A, T1B, T2B, T3B, T1, T2, T3, TA, TB, T, D) 
= 300*D - C1 - C2 - C3 
= 300*D - (8*T1 + 3*T2 + 5*T3) 
  - (5*T1A + 9*T2A + 6*T3A + 6*T1B + 8*T2B + 7*T3B) - (9*TA + 7*TB)

Constrained to:

 TA <= 550 (factory A can only hold 550 tons)
 TB <= 700T1 <= 390 (supplier 1 can only supply 390 tons)
 T2 <= 460T3 <= 370T1A, T2A, T3A, T1B, T2B, T3B, T1, T2, T3, TA, TB, T, D integers
 T1A, T2A, T3A, T1B, T2B, T3B, T1, T2, T3, TA, TB, T, D >= 0

Now we have a huge equations with lots of variables, but if we think a little more we can reduce it to six variables, so that:

(the sum of all gunpowder required from all 3 suppliers that we sent to factory A)
 TA = T1A + T2A + T3A 
 TB = T1B + T2B + T3B
 T1 = T1A + T1B
 T2 = T2A + T2B
 T3 = T3A + T3B
 T = T1 + T2 + T3 = TA + TB

This reduces to 7 variables: T1A, T2A, T3A, T1B, T2B, T3B, D

But since each doll requires 100KG of gunpowder, or 0.1 ton, we have:

 1* T = 10 * D => D = T/10

So we must focus only on the six basics variables: T1A, T2A, T3A, T1B, T2B, T3B, and our profit equation will be:

 P(Xi) = 300*(T/10) - (8*(T1A + T1B) + 3*(T2A + T2B) + 5*(T3A + T3B))
 - (5*T1A + 9*T2A + 6*T3A + 6*T1B + 8*T2B + 7*T3B) 
 - (9*(T1A + T2A + T3A) + 7*(T1B + T2B + T3B))

Genetic Algorithms

Now let's talk of the approach to be used in this problem, the Genetic Algorithms (GA from now on).GA is a technique based on evolution schemes of species, in which we have a population of individuals, represented by their own chromosome, as time goes by (and so the ‘while loop') we breed them, mutate some of them e select who shall live and who shall die, since the better an individual, greater the chance it has to be chosen for reproduction and for the next generation, we come up with a solution closer to the optimum (hopefully global) each time we get to a new generation.In this tutorial I'll take apart the basics on GA for there are many tutorials about this here. If you're not familiar with its concepts yet, please, read some basics tutorial, then get back here, so we can go on

Remember you can visit the Message Store to discuss this tutorial. Comments are always welcome!. There are already replies in the thread, why not join in?