 |
    |
Efficiently Solving: A Large-Scale Integer Linear Program Using a Customized Genetic Algorithm
Kalyanmoy Deb1 and Koushik Pal2
1Kanpur Genetic Algorithms Laboratory (KanGAL), Department of Mechanical Engineering, Indian Institute of Technology Kanpur, Kanpur, PIN 208016, India
deb@iitk.ac.in
http://www.iitk.ac.in/kangal/deb.htm
2Department of Mathematics and Scientific Computing, Indian Institute of Technology Kanpur, Kanpur, 208016, India
kapal@iitk.ac.in
Abstract. Many optimal scheduling and resource allocation problems involve large number of integer variables and the resulting optimization problems become integer linear programs (ILPs) having a linear objective function and linear inequality/equality constraints. The integer restrictions of variables in these problems cause tremendous difficulty for classical optimization methods to find the optimal or a near-optimal solution. The popular branch-and-bound method is an exponential algorithm and faces difficulties in handling ILP problems having thousands or tens of thousands of variables. In this paper, we extend a previously-suggested customized GA with four variations of a multi-parent concept and significantly better results are reported. We show variations in computational time and number of function evaluations for 100 to 100,000-variable ILP problems and in all problems a near-linear complexity is observed. The exploitation of linearity in objective function and constraints through genetic crossover and mutation operators is the main reason for success in solving such large-scale applications. This study should encourage further use of customized implementations of EAs in similar other applications.
Keywords: Integer linear programs, customized GAs, Large-scale optimization, computational time
LNCS 3102, p. 1054 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004