Towards merging binary integer programming techniques with genetic algorithms (Q1748518)

Summary: 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 \(M u(1 - u)\), in which \(M\) is a large number. Values not near to the boundary extremes of 0 and 1 make the component of \(M u(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.