1. Generating QAP instances with known optimum solution and additively decomposable cost function
- Author
-
Madalina M. Drugan, Security, and Computational Modelling
- Subjects
Instance generator ,Mathematical optimization ,Control and Optimization ,business.industry ,Heuristic (computer science) ,Quadratic assignment problem ,Applied Mathematics ,Function (mathematics) ,Computer Science Applications ,Local optimum ,Computational Theory and Mathematics ,meta-heuristics ,Discrete Mathematics and Combinatorics ,Combinatorial optimization ,Local search (optimization) ,business ,Algorithm ,Metaheuristic ,Mathematics ,Generator (mathematics) - Abstract
Quadratic assignment problems (QAPs) is a NP-hard combinatorial optimization problem. QAPs are often used to compare the performance of meta-heuristics. In this paper, we propose a QAP problem instance generator that can be used for benchmarking for heuristic algorithms. Our QAP generator combines small size QAPs with known optimum solution into a larger size QAP instance. We call these instances composite QAPs (cQAPs), and we show that the cost function of composite QAPs is additively decomposable. We give mild conditions for which a composite QAP instance has known optimum solution. We generate cQAP instances using uniform distributions with different bounds for the component QAPs and for the rest of the cQAP elements. Numerical and analytical techniques that measure the difficulty of the composite QAP instances in comparison with other QAPs from the literature are introduced. These methods point out that some cQAP instances are difficult for local search with many local optimum of various values, low epistasis and non-trivial asymptotic behaviour.
- Published
- 2013