A Genetic Algorithm for the Multiple-Choice Integer Program

Abstract

We present a genetic algorithm for the multiple-choice integer program that finds an optimal solution with probability one (though it is typically used as a heuristic). General constraints are relaxed by a nonlinear penalty function for which the corresponding dual problem has weak and strong duality. The relaxed problem is attacked by a genetic algorithm with solution representation special to the multiple-choice structure. Nontraditional reproduction, crossover and mutation operations are employed. Extensive computational tests for dual degenerate problem instances show that suboptimal solutions can be obtained with the genetic algorithm within running times that are shorter than those of the OSL optimization routine.