Solving Integer Programming Problems Using Genetic Algorithms
By ai-depot | May 25, 2003
Looking at the challenges of integer programming, this article describes how to apply evolutionary techniques to optimizing systems of equations. Example code is provided in C.
Written by Fabr�cio Olivetti de Fran�a.
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.
Tags: none
Category: tutorial |
April 15th, 2007 at 8:40 am
nicely written article
August 30th, 2007 at 11:45 pm
I liked to know about the Integer Programming using GA and different between about the LP and Ip.
September 13th, 2007 at 3:39 am
pls explain the following as regarding integer programming problem. Sepration,fathoming,branching,bounding.
October 25th, 2007 at 10:21 am
Very nice!
Your tut help me a lot in my course.
Thank you very much.
February 2nd, 2008 at 12:32 pm
You should add a list of problems for moms to use for home schooling. It would definitely help! :-)
February 2nd, 2008 at 12:33 pm
It would sure help if you had a list of math problems for us moms. Thx. ;-)
February 8th, 2008 at 5:57 am
very good