A population-based fast algorithm for a billion-dimensional resource allocation problem with integer variables

Kalyanmoy Deb and Christie Myburgh

European Journal of Operational Research, 2017, vol. 261, issue 2, 460-474

Abstract: 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 (glpk,Makhorin, 2012 and CPLEX,Gay, 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 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 (109) 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.

Keywords: Evolutionary computations; Population-based optimization algorithm; Large-scale optimization; Resource allocation problem; Billion variables (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221717301212
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:261:y:2017:i:2:p:460-474

DOI: 10.1016/j.ejor.2017.02.015

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().