In 1958, Gomory (1963a) devised a method, known as the "method for integer forms", for solving integer programming problems. In 1960, Gomory (1963b) devised another method for solving all integer linear programming problems.

Several computers codes using one or both methods have been written; and have successfully solved many real problems. However, their performance has not been nearly as predictable as that of ordinary linear programming codes-which are themselves rather unpredictable as regards running time (Beale, 1965). Martin et al. (1963) Author ? ? : Department of Computer Science, Eritrea Institute of Technology, Asmara, The State of Eritrea, North East Africa. E-mail : senanu.kumdev@gmail.com, ikgulam@gmail.com Author ? : Department of Mechanical & Vehicle Engineering, Adama Science & Technology University, Adama, Ethiopia, Africa. E-mail : singh_ajit_pal@hotmail.com used a variant method of integer form called the "accelerated euclidean algorithms". Dakin (1964) and Driebeck (1964) have developed programs using a "branch and bound" method for mixed integer programming. Later Forest et al. (1974), Tomlin (1971), Driebeck (1966), Dakin (1965), Beale and Small (1965), and others improved or refined the branch and bound approach of solving integer programming problems in a number of ways. There are many survey articles and text books to describe the usage of refined and improved methods of using branch and bound approaches (Hansen, 1979;Ravindran, 1983a, 1985b) But the most important facet of both Gomory's cutting plan approach and branch and bound approach is that they can be applied only after obtaining noninteger solution using traditional optimization techniques like Simplex Algorithms.

But the proposed cultural algorithmic approach directly searches the integer solution in the population space which is a space obtained by narrowing the population space where the population space is obtained by the constraints of the problem.

The implementation of the cultural algorithm is presented here to find ) , ( 21 x x which satisfies all the n constraints and yields the optimal value for Z . As IPP is a kind of constrained optimization problem, the constraints including non-negativity constraints and integer restrictions are availed as knowledge component to build the belief space. A cultural algorithm, introduced by Reynolds (1994), and seen as extension to genetic algorithm, is a computational model of cultural evolution process in nature where there is a knowledge component in addition to population component. The knowledge component is used to build belief space. The best individuals are selected from belief space using a fitness function. These best individuals are used to update the belief space via a vote acceptance function.

Generally cultural algorithms use five different kinds of knowledge component namely: normative, domain specific, situational, historical and topographical knowledge. The proposed cultural algorithm for solving two variable integer programming problems with n constraints uses a normative kind of knowledge gained from constraints including non-negativity and integer restrictions.

The proposed cultural algorithm for solving two variable integer programming problems uses the frame work for constrained optimization problem introduced by Carlos and Licardo (2002) to identify knowledge component and to build belief space. The algorithm is also using a variant of test bed introduced by Chang and Reynolds (1996) as the backbone of computational procedure.


# II. THE CULTURAL ALGORITHM FOR SLOVING TWO VARIABLE INTERGER

PROGRAMMIN PROBLEMS x

When the constrain i is as
i i i c x b x a ? + 1 1 with ? , then i S can be defined as i i a c x ? ? 1 0 irrespective of i b and if i i a c
is real, it should be rounded off to the immediate lower positive integer.

When the constraint i is as
i i i c x b x a ? + 1 1 with ? , then i S can be defined as ? ? ? 1 x a c i i irrespective of i b and if i i a c
is real, it should be rounded off to the immediate higher positive integer . Note that if 0 = i a in the constraint i , then this constraint is ignored in defining space for 1 x .

ii. Definition of Population Space for 2

x When the constraint i is as
i i i c x b x a ? + 2 1 with ? , then i T can be defined as i i b c x ? ? 1 0 irrespective of i a and if i i b c
is real, it should be rounded off to the immediate lower positive integer.

When the constraint i is as
i i i c x b x a ? + 2 1 with ? , then i T can be defined as ? ? ? 1 x b c i i irrespective of i a and if i i b c
is real, it should be rounded off to the immediate higher positive integer . Note that if 
0 = i b in the constraint i , thenx , { } g g g l l l x POP , 1 , 2 ,..., 2 , 1 , ) ( 1 ? ? + + =
as the range of values between lowest ) (l and greatest ) (g for 1

x will satisfy all the n constraints. This population space can also be stated as
{ } n S S S x POP ? ? ? ,..., ) ( 2 1 1 =
. Similarly, we build the population space for
2 x as { } n T T T x POP ? ? ? ,..., ) ( 2 1 2 = . ? Step 2: Initialization of Belief Space
When the objective function is to maximize ) (OC in achieving optimal 2 1 qx px + ) to build the belief space.

The fitness function which identifies and returns the optimal contributor is defined as follows:

Fitness Function:

When the objective function is to maximize
2 1 qx px + : The OC for 1 x is )) ( max( 1 x POP if 0 ? p ; The OC for 1 x is )) ( min( 1 x POP if 0 ? p ; The OC for 2 x is )) ( max( 2 x POP if 0 ? q ; The OC for 2 x is )) ( min( 2 x POP if 0 ? q ;
A Cultural Algorithm for the Two Variable Integer Programming Problem


# Global Journal of Computer Science and Technology Volume XII Issue II Version I

Similarly, when the objective function is to minimize
2 1 qx px + : The OC for 1 x is )) ( min( 1 x POP if 0 ? p ; The OC for 1 x is )) ( max( 1 x POP if 0 ? p ; The OC for 2 x is )) ( min( 2 x POP if 0 ? q ; The OC for 2 x is )) ( max( 2 x POP if 0 ? q ;
When the objective function is to maximize 2 1 qx px + , the optimal contribution that 1

x can put in
2 1 qx px + is [ ] p x OC * 1 )) ( and 2 x can put is [ ] q x OC * 2 )) ( . Here if [ ] [ ] q x OC p x OC * 2 * 1 )) ( )) ( ? then 1
x can be greater contributor than 2 x , otherwise 2

x is greater contributor than 1 x in achieving optimal 2 1 qx px + .

Similarly, when the objective function is to minimize
2 1 qx px + , and if ] )) ( [ ] )) ( [ * 2 * 1 q x OC p x OC ? then 2
x can be greater contributor than 1 x , otherwise
1
x is greater contributor than 2 x in achieving optimal . This indicates the population space of
1
x and/or 2 x is unbounded or indefinite. We adapt the following rules in such instances.

1. If the population space of both 1

x and 2 x are bounded/definite and non-null, we identify the GC as discussed earlier and make use of this in building belief space. 2. If the population space of any one variable is found to be unbounded/indefinite or null, we consider the other variable as GC in building belief space irrespective of the unbounded/indefinite or null population space of former variable.


# If the population spaces of both variables are

found to be unbounded/indefinite or null, then this is indication that there is inability in building the belief space. With such population spaces, we declare that the problem has infeasible or unbounded solution space.

When the GC is identified evidently, we believe that the

)) )( max( GC POP is playing the greatest role than all other components in the population space in achieving the maximum
2 1 qx px + and )) )( min(
GC POP is playing the greatest role than all other components in population space in achieving the minimum 2 1 qx px + . Note that, here, GC is either 1

x or 2

x . Thus we define the belief space ) (i BLF , ( i is initially 0), as follows:

Building Belief Space: Case I: When 1

x is found to be GC and the objective function is to maximize
2 1 qx px + : ) , ( ) ( 2 1 x x i BLF = such that: )) ( max( 1 1 x POP x = ; ; 2 B x ? where B is a set of integers which is intersection of n B B B
,..., , 2 1 and i B can be defined as
i i i b x a c x ) ( 1 2 ? ? if the constraint i is as i i i c x b x a ? + 2 1 with ? and as i i i b x a c x ) ( 1 2 ? ? if the constraint i as i i i c x b x a ? + 2 1 with ? where )) ( max( 1 1 x POP x = .
If the constraint i is as
i i i c x b x a ? + 2 1 with of ? , then i i i b x a c ) ( 1 ?
should be rounded off to the immediate lower positive integer and it is as
i i i c x b x a ? + 2 1 with ? , then i i i b x a c
) ( 1 ? should be rounded off to the immediate higher positive integer.

Case II : When 1

x is found to be GC and the objective function is to minimize
2 1 qx px + : ) , ( ) ( 2 1 x x i BLF = such that: )) ( min( 1 1 x POP x = ; ; 2 B x ? where B is a set of integers which is intersection of n B B B ,..., ,21
and i B can be defined as
i i i b x a c x ) ( 1 2 ? ? if the constraint i is as i i i c x b x a ? + 2 1
with ? and as
i i i b x a c x ) ( 1 2 ? ? if the constraint i as i i i c x b x a ? + 2 1 with ? where )) ( min( 1 1 x POP x = .
If the constraint i is as
i i i c x b x a ? + 2 1 with of ? , then i i i b x a c ) ( 1 ?
should be rounded off to the immediate lower positive integer and it is as
i i i c x b x a ? + 2 1 with ? , then i i i b x a c ) ( 1 ?
should be rounded off to the immediate higher positive integer. x is found to be GC and the objective function is to maximize
2 1 qx px + : ) , ( ) ( 2 1 x x i BLF = such that: ; 1 B x ? )) ( max( 2 2 x POP x = ; where B is a set of integers which is intersection of n B B B
,..., , 2 1 and i B can be defined as
i i i a x b c x ) ( 2 1 ? ? if the constraint i is as i i i c x b x a ? + 2 1
with ? and as
i i i a x b c x ) ( 2 1 ? ? if the constraint i as i i i c x b x a ? + 2 1 with ? where )) ( max( 1 2 x POP x = . If the constraint i is as i i i c x b x a ? + 2 1 with of ? , then i i i a x b c ) ( 2 ?
should be rounded off to the immediate lower positive integer and it is as
i i i c x b x a ? + 2 1 with ? , then i i i a x b c ) ( 2 ?
should be rounded off to the immediate higher positive integer.

Case IV: When 2

x is found to be GC and the objective function is to minimize
2 1 qx px + : ) , ( ) ( 2 1 x x i BLF = such that: ; 1 B x ? )) ( min( 2 2 x POP x = ; where B is a set of integers which is intersection of n B B B ,..., ,21
and i B can be defined as
i i i a x b c x ) ( 2 1 ? ? if the constraint i is as i i i c x b x a ? + 2 1 with ? and as i i i a x b c x ) ( 2 1 ? ? if the constraint i as i i i c x b x a ? + 2 1 with ? where )) ( min( 1 2 x POP x = . If the constraint i is as i i i c x b x a ? + 2 1 with of ? , then i i i a x b c ) ( 2 ?
should be rounded off to the immediate lower positive integer and it is as
i i i c x b x a ? + 2 1 with ? , then i i i a x b c ) ( 2 ?
should be rounded off to the immediate higher positive integer.

Note that, hereafter, we use the terms greater contributor ) (GC and lower contributor ) (LC , instead of 1

x and 2

x . If 1 x is found to be GC in the earlier step then 2

x is LC , otherwise 1 x is LC and 2 x is GC .


# ? Step 3: Evaluation of Space

The moment we arrive to evaluate the current belief space, GC is fixed with one single best component and LC lies in the set B . Now lets search the best component for LC from B which may produce the optimal value of  )) (i BLF Z = and classify this outcome of evaluation as non-futile.

There may be an uncommon situation here while evaluating current belief space in search of the best component of LC that suits with the best component of GC which is already fixed while defining the current belief space. The unusual situation is that the set B identified for LC while defining the current belief space may be a null set. This indicates that there exist no single component in population space of LC to accept the best component chosen for GC to build the current belief space. In such situations, we assume that the mission with current belief space is failed and classify this outcome of evaluation as futile.
? Step 4: Vote Acceptance Function If the )) 1 ( ( )) ( ? ? = i BLF Z i BLF Z
when the objective function is to maximize x are the best components used for GC and LC in calculating

))
1 ( ? = i BLF Z . Similarly, If the )) 1 ( ( )) ( ? ? = i BLF Z i BLF Z
when the objective function is to minimize 


# Global Journal of Computer Science and Technology Volume XII Issue II Version I

The vote acceptance function rejects the outcome of evaluation in all other circumstances except the above explained situations. Thus the function rejects the outcome of evaluation and suggest to reproduce the population space in all the following instances:
IF WE ARE WORKING WITH INITIAL BELIEF SPACE (THAT IS ) (i BLF WHERE 0 = i ) IF THE OUTCOME OF EVALUATION OF ) (i BLF WAS FOUND TO BE FUTILE. IF )) 1 ( ( )) ( ( ? ? i BLF Z i BLF Z WHEN THE OBJECTIVE FUNCTION IS TO MAXIMIZE 2 1 qx px Z + = . )) 1 ( ( )) ( ( ? ? i BLF Z i BLF Z WHEN THE OBJECTIVE FUNCTION IS TO MINIMIZE 2 1 qx px Z + = .
? Step 5: Modification in the Belief Space When the vote acceptance function suggests to reproduce population space, we modify the current belief space ) (i BLF to get ) 1 ( + i BLF by the modifying the GC . Note that the GC is one fixed component and LC lies in the set B in the current belief space. We now modify this belief space by adjusting the component fixed to the GC . Based on this modified GC , we define once again the set B where LC lies, which along with fixed modified component of GC forms new belief space ) 1 ( + i BLF . Thus the modification to GC is brought as follows:

Case I: If the objective function is to maximize such that GC is the component codified above and LC belongs to the set B defined above. This modified belief space is then submitted to the promote influence function which will deicide the further course on whether this space is to be evaluated or not. a. Step 6: Promote Influence Function
3![Cultural Algorithm for the Two Variable Integer Programming Problem © 2012 Global Journals Inc. (US) Global Journal of Computer Science and Technology Volume XII Issue II Version I January 2012 Case III: When 2](image-2.png "A 3")

Case II: If the objective function is to maximize2 1 qx px +and the co-efficient of LC in objectivefunction is less than zero or if the objective function is tominimize2 1 qx px +and the co-efficient of LC inobjective function is greater than zero , the smallestcomponent of B is considered as the best componentfor LC .Find the value ofZ=2 1 qx px +using the bestcomponents of2 1 qx px +and the co-efficient of LC in objectivefunction is greater than zero or if the objective function isto minimize2 1 qx px +and the co-efficient of LC inobjective function is less than zero, then the largestcomponent of B is considered as the best componentfor LC .
2 1 qx px +and the co-efficient of GC in objectivefunction is greater than zero or if the objective function isto minimize2 1 qx px +belief spaceBLF( + i) 1as shown in the section 2.2.2Building Belief Space.Now the new belief spaceBLF( + i) 1is(, 1 x 2 x)
			January 2012© 2012 Global Journals Inc. (US)
			January 2012© 2012 Global Journals Inc. (US)
			Global Journal of Computer Science and Technology Volume XII Issue II Version I 6 January 2012 © 2012 Global Journals Inc. (US)
		
		
			

## III.


## CONCLUSION

A specific implementation of cultural algorithm is presented using the computational model of cultural evolution process to solve two variable IPPs. Identifying formative knowledge sources in IPPs, the belief space is built in addition to the traditional framework of genetic algorithms. Whilst the existing approaches like Gomery's and Branch and Bound need non-integer solution produced by traditional optimization methods like simplex algorithms, the proposed algorithm steer clear of the computational load of solving linear programming problem relaxations. Comparing the complexity of Gomery's and Branch and Bound approaches, searching global optimal solution using proposed cultural algorithm is especially slender. This implementation can be extended for solving IPPs with any number of decision variables and constraints with signed integers in future. 
			
			

				


* 
	
		Survey of integer programming
		
			EM LBeale
		
	
	
		Operational Research Quarterly
		
			16
			2
			
			1965
		
	




* 
	
		Mixed integer programming by a branch and bound technique
		
			EM LBeale
		
		
			RSmall
		
	
	
		Proceedings of the Third IFIP Congress
				the Third IFIP Congress
		
			1965
			
		
	




* 
	
		A cultural algorithm for constrained optimization
		
			AC CCarlos
		
		
			LBLicardo
		
	
	
		MICAI-Advances in Artificial Intelligence, Second Mexican, International Conference on Artificial Intelligence
		Series-Lecture Notes in Computer Science
		Merida, Yucatan, Mexico, Proceedings; UK
		
			Springer-Verlag London
			2002. April 22-26
			2313
			
		
	




* 
	
		A test bed for solving optimization problems using cultural algorithms
		
			CJChang
		
		
			RGReynolds
		
	
	
		Management Science
		John R. M. and Peter, A.
		
			20
			5
			
			1996
		
	
	(eds.) programming problems with umpire




* 
	
		All-integer integer programming algorithm
		
			REGomory
		
	
	
		Industrial Scheduling
				
			JFMuth
			GLThompson
		
		
			Prentice Hall
			1963. 1960
			
		
	
	First issued in IBM Research Center Research Report RC-189




* 
	
		An algorithm for integer solutions to linear programs
		
			REGomory
		
		R.L. Graves and P
		
			1963
		
	




* 
	
		Nonlinear integer programming algorithms: a survey
		
			OKWolfe ; Gupta
		
		
			ARavindran
		
		No. 1
	
	
		First issued in Princeton-IBM Mathematics Research Project
				
			McGraw-Hill
			1958. 1983
			20
			
		
	
	Technical Report
	Recent Advances in Mathematical Programming




* 
	
		Branch and bound experiments in convex nonlinear integer programming
		
			OKGupta
		
		
			ARavindran
		
	
	
		Management Science
		
			12
			
			1985
		
	




* 
	
		Methods of nonlinear 0-1 programming
		
			PHansen
		
	
	
		Annals of Discrete Mathematics
		
			1979
		
	




* 
	
		An accelerated euclidean algorithm for integer linear programming
		
			GTMartin
		
		
			RLGraves
		
		
			PWolfe
		
	
	
		Recent Advances in Mathematical Programming
				
			McGraw-Hill
			1963
			
		
	




* 
	
		An introduction to cultural algorithms
		
			RGReynolds
		
	
	
		Proceedings of the Third Annual Conference on Evolutionary Programming
				the Third Annual Conference on Evolutionary ProgrammingSan Diego, California
		
			1994. February 24-26
			
		
	




* 
	
		An improved branch and bound method for integer programming
		
			JATomlin
		
	
	
		Operations Research
		
			19
			
			1971