An Evolutionary Solver for Pure Integer Linear Programming

In this paper we introduce an evolutionary algorithm for the solution of pure integer linear programs. All the variables of the problem are fixed by the evolutionary system. If they correspond to a feasible solution, their evaluation is determined directly by the objective function. If the variables correspond to an unfeasible solution, the evaluation is measured by the sum of infeasibilities, which can be determined by simple linear algebra manipulations. The algorithm proposed does not require the solution of continuous linear programs. We report results obtained for some standard benchmark problems, and compare them with those obtained by branch-and-bound. The performance of the evolutionary algorithm is promising. Good feasible solutions were generally obtained, and in some of the difficult benchmark tests it outperformed branch-and-bound.