Towards Merging Binary Integer Programming Techniques with Genetic Algorithms

Abstract EN

This paper presents a framework based on merging a binary integer programming technique with a genetic algorithm.

The framework uses both lower and upper bounds to make the employed mathematical formulation of a problem as tight as possible.

For problems whose optimal solutions cannot be obtained, precision is traded with speed through substituting the integrality constrains in a binary integer program with a penalty.

In this way, instead of constraining a variable u with binary restriction, u is considered as real number between 0 and 1, with the penalty of Mu(1-u), in which M is a large number.

Values not near to the boundary extremes of 0 and 1 make the component of Mu(1-u) large and are expected to be avoided implicitly.

The nonbinary values are then converted to priorities, and a genetic algorithm can use these priorities to fill its initial pool for producing feasible solutions.

The presented framework can be applied to many combinatorial optimization problems.

Here, a procedure based on this framework has been applied to a scheduling problem, and the results of computational experiments have been discussed, emphasizing the knowledge generated and inefficiencies to be circumvented with this framework in future.