Parallel Max-Min Ant System for Solving Combinatorial Constraint-satisfaction Problems
ISEF · 2020 Systems Software
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.
Competition history
- ISEF 2020
Resources
Related projects
ISEF · 2019
General Distributed Backtracking Framework for Solving Combinatorial Constraint Satisfaction Problems
CWSF · 2026
HybridCSP
ISEF · 2024
A Novel Approach for Optimization of Genetic Algorithm Parameters Used in Solving NP-Complete Problems via the Generic Sudoku N x N Paradigm
ISEF · 2017
Traffic Congestion Reduction Using Ant Colony Optimization
Closest projects by meaning, across every fair and year in the corpus.
Source: Regeneron International Science and Engineering Fair