A population-based fast algorithm for a billion-dimensional resource allocation problem with integer variables. (English) Zbl 1403.90516
Summary: Among various complexities affecting the performance of an optimization algorithm, the search space dimension is a major factor. Another key complexity is the discreteness of the search space. When these two complexities are present in a single problem, optimization algorithms have been demonstrated to be inefficient, even in linear programming (LP) problems. In this paper, we consider a specific resource allocation problem constituting to an integer linear programming (ILP) problem which, although comes from a specific industry, is similar to other practical resource allocation and assignment problems. Based on a population based optimization approach, we present a computationally fast method to arrive at a near-optimal solution. Compared to two popular softwares ([A. Makhorin, “GNU linear programming kit”, https://www.gnu.org/software/glpk (2012); D. M. Gay, “IBM ILOG CPLEX optimization studio: Getting started with CPLEX (12th ed.)”, IBM (2015)]), which are not able to handle around 300 and 2000 integer variables while continuing to run for hours, respectively, our proposed method is able to find a near-optimal solution in less than a second on the same computer. Moreover, the main highlight of this study is to propose a customized population based optimization algorithm that scales in almost a linear computational complexity in handling 50,000 to one billion (\(10^{9}\)) variables. We believe that this is the first time such a large-sized real-world constrained problem is ever handled using any optimization algorithm. We perform sensitivity studies of our method for different problem parameters and these studies clearly demonstrate the reasons for such a fast and scale-up application of the proposed method.
MSC:
| 90C10 | Integer programming |
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 90C06 | Large-scale problems in mathematical programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
evolutionary computations; population-based optimization algorithm; large-scale optimization; resource allocation problem; billion variablesReferences:
| [1] | Akgül, M.; Hamacher, H. W.; Tufecki, S., The linear assignment problem, Combinatorial optimization, 85-122 (1992), Springer Verlag: Springer Verlag Berlin · Zbl 0784.90091 |
| [2] | Aminbaksh, S.; Sonmez, R., Discrete particle swarm optimization method for the large scale discrete time-cost trade-off problem, Expert Systems With Applications, 51, 177-185 (2016) |
| [3] | Bellman, R. E., The theory of dynamic programming, Bulletin of American Mathematical Society, 60, 6, 503-515 (1954) · Zbl 0057.12503 |
| [4] | Cheng, W. N.; Zhang, J.; Chung, H. S.H.; Zhong, W. L.; ad, W.-G. W.; Shi, Y. H., A novel set-based particle swarm optimization method for discrete optimization problems, IEEE Transactions on Evolutionary Computation, 14, 3, 278-300 (2010) |
| [5] | Dantzig, G. B., Linear programming and extensions (1988), Princeton University Press · Zbl 0108.33103 |
| [7] | Deb, K., An efficient constraint handling method for genetic algorithms, Computer Methods in Applied Mechanics and Engineering, 186, 2-4, 311-338 (2000) · Zbl 1028.90533 |
| [8] | Deb, K.; Agrawal, S., Understanding interactions among genetic algorithm parameters, Foundations of Genetic Algorithms, 5, 265-286 (1999) |
| [9] | Deb, K.; Reddy, A. R.; Singh, G., Optimal scheduling of casting sequence using genetic algorithms, Journal of Materials and Manufacturing Processes, 18, 3, 409-432 (2003) |
| [10] | Ermon, S.; Gomes, C. P.; Sabharwal, A.; Selman, B., Taming the curse of dimensionality: Discreteintegration by hashing and optimization, Proceedings of the 30th International Conference on Machine Learning, volume 28, 334-342 (2013), Atlanta, Georgia, USA |
| [11] | Fletcher, R.; Reeves, C. M., Function minimization by conjugate gradients, Computer Journal, 7, 149-154 (1964) · Zbl 0132.11701 |
| [13] | Goldberg, D. E., Genetic algorithms for search, optimization, and machine learning (1989), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0721.68056 |
| [14] | Goldberg, D. E.; Sastry, K.; Llora, X., Toward routine billion-variable optimization using genetic algorithms, Complexity, 12, 3, 27-29 (2007) |
| [15] | Holland, J. H., Adaptation in natural and artificial systems (1975), MIT Press: MIT Press Ann Arbor MI · Zbl 0317.68006 |
| [16] | Huang, L.; Gao, Z.; Zhang, D., Research on multi-fidelity aerodynamic optimization methods, Chinese Journal of Aeronautics, 26, 2, 279-286 (2013) |
| [17] | Iturriaga, S.; Nesmachnow, S., Solving very large optimization problems (up to one billion variables) with a parallel evolutionary algorithm in CPU and GPU, Proceedings of the P2P, parallel, grid, cloud, and internet computing, 267-272 (2012), IEEE Press: IEEE Press Piscatway, NJ: |
| [18] | Karmarkar, N., A new polynomial time algorithm for linear programming, Combinatorica, 4, 4, 373-395 (1984) · Zbl 0557.90065 |
| [19] | Kellerer, H.; Pferschy, U.; Pisinger, D., Knapsack problems (2004), Springer Verlag · Zbl 1103.90003 |
| [20] | Kong, M.; Tian, P., Apply the particle swarm optimization to the multidimensional knapsack problem, Proceedings of the artificial intelligence and soft computing conference (ICAISC), 1140-1149 (2006), Springer |
| [21] | Land, A. H.; Doig, A. G., An automatic method of solving discrete programming problems, Econometrica, 28, 3, 497-520 (1960) · Zbl 0101.37004 |
| [22] | Li, C.; Zhou, J.; Ouyang, S.; Chen, X. D.L., Improved decomposition coordination and discrete differential dynamic programming for optimization of large-scale hydropower system, Energy Conversion and Management, 84, 363-373 (2014) |
| [23] | Li, X.; Yao, X., Cooperatively coevolving particle swarms for large scale optimization, IEEE Transactions on Evolutionary Computation, 16, 2, 210-224 (2012) |
| [25] | Martello, S.; Toth, P., Knapsack problems: Algorithms and computer implementations (1990), Wiley · Zbl 0708.68002 |
| [26] | Michalewicz, Z., Heuristic methods for evolutionary computation techniques, Journal of Heuristics, 1, 177-206 (1995) · Zbl 0853.68157 |
| [27] | Mitchell, J. E., Branch-and-cut algorithms for combinatorial optimization problems, Handbook of applied optimization, 65-77 (2002), Oxford University Press |
| [28] | Molina-Cristbal, A.; Palmer, P. R.; Skinner, B. A.; Parks, G. T., Multi-fidelity simulation modelling in optimization of a submarine propulsion system, Proceedings of the IEEE vehicle power and propulsion conference (VPPC), 1-6 (2010), IEEE Press: IEEE Press Piscatway: |
| [29] | Nau, D. S.; Kumar, V.; Kanal, L., General branch and bound, and its relation to A* and AO*, Artificial Intelligence, 23, 1, 29-58 (1984) · Zbl 0537.68064 |
| [30] | Omidvar, M. N.; Li, X.; Mei, Y.; Yao, X., Cooperative co-evolution with differential grouping for large scale optimization, IEEE Transactions on Evolutionary Computation, 18, 3, 378-393 (2014) |
| [31] | Reklaitis, G. V.; Ravindran, A.; Ragsdell, K. M., Engineering optimization methods and applications (1983), Wiley: Wiley New York |
| [32] | Wang, Z.; Zoghi, M.; Hutter, F.; Matheson, D.; de Freitas, N., Bayesian optimization in high dimensions via random embeddings, Proceedings of the 23rd international joint conference on artificial intelligence, 1778-1784 (2013) |
| [33] | Xu, J.; Zhang, S.; Huang, E.; Chen, C.-H.; Lee, L. H.; Celik, N., Efficient multi-fidelity simulation optimization, Proceedings of the 2014 winter simulation conference, 3940-3951 (2014), IEEE Press: IEEE Press Piscataway, NJ, USA |
| [34] | Yang, B.; Xiao, H., On large scale evolutionary optimization using simplex-based cooperative coevolution genetic algorithm, Proceedings of the International conference on computational intelligence and software engineering, 1-5 (2009) |
| [35] | Yang, Z.; Tang, K.; Yao, X., Large scale evolutionary optimization using cooperative coevolution, Information Sciences, 178, 15, 2985-2999 (2008) · Zbl 1283.65064 |
| [36] | Zanakis, S. H.; Evans, J. R., Heuristic “optimization”: Why, when and how to use it, Interfaces, 11, 5, 84-91 (1981) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
