An approximate solution method for combinatorial optimization. Hybrid approach of genetic algorithm and Lagrange relaxation method

In this paper the authors deal with an efficient method for obtaining a suboptimal solution of combinatorial optimization problems. They propose a hybrid approach of genetic algorithm (GA) and Lagrange relaxation method (LR) where the solution space of the given problem is partitioned into several small subspaces and only promising subspaces are searched for obtaining a suboptimal solution. The most promising subspace is found by GA where a lower bound of each subspace obtained by LR is used for evaluating the performance (degree of promise) of each subspace. The final suboptimal solution is obtained by searching an optimal or suboptimal solution in the most promising subspace. A numerical example of jobshop scheduling is included, and the computational burden and the accuracy of the solution are compared among the solutions obtained by the present hybrid approach, GA, and LR. [In Japanese.]