Efficiently solving: a large-scale integer linear program using a customized genetic algorithm

Deb, Kalyanmoy ; Pal, Koushik (2004) Efficiently solving: a large-scale integer linear program using a customized genetic algorithm Lecture Notes in Computer Science, 3102 . pp. 1054-1065. ISSN 0302-9743

Full text not available from this repository.

Official URL: http://www.springerlink.com/content/ckf7vng22vfa3q...

Related URL: http://dx.doi.org/10.1007/978-3-540-24854-5_104


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.

Item Type:Article
Source:Copyright of this article belongs to Springer.
Keywords:Integer Linear Programs; Customized GAs; Large-scale Optimization; Computational Time
ID Code:82734
Deposited On:14 Feb 2012 11:27
Last Modified:14 Feb 2012 11:27

Repository Staff Only: item control page