A dual genetic algorithm for nonlinear integer programs

An approach for nonlinear integer programs based on a dual genetic algorithm is developed. It has a wide range of applications which includes planning, operational and design problems. This approach consists of relaxing some selected constraints of the integer program in question, using a nonlinear penalty function. Weak and strong duality results are established for the corresponding dual problem. This strong duality result is exact as opposed to the known asymptotic strong duality established for continuous programming, where exact strong duality exists only for convex problems. The nonlinear penalty has the characteristic of only penalizing nonfeasible solutions (as opposed to Lagrangian relaxation which also rewards feasible solutions); this alleviates the dual degeneracy problem. A genetic algorithm for solving the resultant dual problem is developed. It is based on nontraditional genetic operators: elitist reproduction, Bernoulli crossover, and immigration (or massive mutation). The latter operator guarantees convergence of the algorithm. An adaptive strategy for varying the penalty parameters is embedded in this genetic algorithm. This genetic algorithm is easy to implement and adapt to different settings. It is applied to three problems: (1) facility location, (2) task allocation, and (3) assembly line balancing, where a special solution coding/decoding method is introduced. Extensive computational experiments show excellent results for the first two problems, and mixed for the third. Overall, they show the high performance and robustness of this approach.