A Hybrid approach for integer programming combining genetic algorithms, linear programming and ordinal optimization

Hybrid methods are promising tools in integer programming, as they combine the best features of different methods in a complementary fashion. This pap er presents such a framework, integrating the notions of genetic algorithm, linear programming, and ordinal optimization in an effort to shorten compu tation times for large and/or difficult integer programming problems. Capit alizing on the central idea of ordinal optimization and on the learning cap ability of genetic algorithms to quickly generate good feasible solutions, and then using linear programming to solve the problem that results from fi xing the integer part of the solution, one may be able to obtain solutions that are close to optimal. Indeed ordinal optimization guarantees the quali ty of the solutions found. Numerical testing on a real-life complex schedul ing problem demonstrates the effectiveness and efficiency of this approach.