A GENETIC ALGORITHM FOR THE MULTIPLE-CHOICE INTEGER-PROGRAM

We present a genetic algorithm for the multiple-choice integer program that finds an optimal solution with probability one (though it is typ ically used as a heuristic). General constraints are relaxed by a nonl inear penalty function for which the corresponding dual problem has we ak and strong duality. The relaxed problem is attacked by a genetic al gorithm with solution representation special to the multiple-choice st ructure. Nontraditional reproduction, crossover and mutation operation s are employed. Extensive computational tests for dual degenerate prob lem 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.