A Genetic Algorithm with Neighborhood Search to Solve Integer and Linear Programming Problems

In this paper, a metaheuristic algorithm that combines genetic and neighbor search algorithms is proposed to solve integer linear programming problems. The individuals of the population are binary coded into a sequence of chromosomes (variables). Initially, chromosome length is five bits (genes) but if required they grow, up to 21 genes per chromosome, when looking for optima. The algorithm includes a test based on systematic neighborhood search to decide if it continues or stops. The algorithm is able to solve maximal or minimal integer linear programming problems in standard or non-standard form and linear programming problems with a simple adaptation. A comparative study was conducted with three algorithms; LINGO, Simplex LP and Evolutionary. These last two algorithms are from commercial solver in Excel spreadsheet software. The results show that the algorithm was able to find similar solution with LINGO and Simplex LP but better than the Evolutionary. A time study using problems from literature with two, three, four, eight and twelve variables is included.