Performance Guarantees of Recurrent Neural Networks for the Subset Sum Problem

Area of Science:

• Computer Science
• Artificial Intelligence
• Operations Research

Background:

• The subset sum problem is a well-known NP-hard problem with various existing solution methods.
• Neural network approaches show promise for combinatorial optimization, but performance guarantees for RNNs on subset sum are underexplored.

Purpose of the Study:

• To investigate the performance guarantees of recurrent neural networks (RNNs) for solving the subset sum problem.
• To develop a novel RNN construction method for computing exact and approximate subset sum solutions.

Main Methods:

• Developed a construction method for RNNs to solve subset sum problems.
• Rigorously defined the mathematical model for each hidden layer in the proposed RNNs.
• Provided mathematical proofs for the correctness and performance analysis of the RNNs.

Main Results:

• Proved that the proposed RNNs achieve approximate solutions (wNN) with a guaranteed performance bound relative to the optimal solution (wOPT), specifically wNN ≥ wOPT(1-ε).
• Demonstrated that the errors between approximate and optimal solutions are small and consistent with theoretical expectations.
• Validated the RNNs' effectiveness through examples, showing close alignment between actual and theoretical error values.

Conclusions:

• The proposed RNN-based approach provides a mathematically sound method for solving the subset sum problem with performance guarantees.
• Recurrence relations from dynamic programming can effectively simulate solution construction within RNNs.
• This research establishes a foundation for using RNNs in solving NP-hard combinatorial optimization problems.