Parallel Max-Min Ant System for Solving Combinatorial Constraint-satisfaction Problems

Overview

Many mathematical and practical problems, such as Sudoku, timetabling, and resource distribution, require elements of a set to be arranged in a way that satisfies specific conditions. Such tasks, called constraint-satisfaction problems (CSPs), include NP-complete instances, so there is no known polynomial-time algorithm to solve the general-case CSP. In order to reduce the time required to solve large CSP instances, an Ant Colony Optimization (ACO) algorithm called the Max-Min Ant System (MMAS) was adapted for combinatorial CSPs, parallelized, and augmented with new heuristics. The resulting MMAS framework was tested for a specific CSP instance (the Costas-array problem, which remains an open problem in mathematics for some sizes). The effectiveness of the MMAS framework was assessed by computing its efficiency with respect to number of processors utilized and comparing its runtimes with and without the new heuristics. By both measurements, the parallel MMAS framework proved to be an effective tool for solving CSPs. The MMAS framework maintained efficient processor utilization (E=1) for problem sizes M=13 and exhibited lower runtimes when using the new heuristics. Higher levels of parallelization can be achieved in the future by investigating distributed versions of MMAS that can pool the computational resources of multiple machines.