A Study of the Mean Field Approach to Knapsack Problems

Area of Science:

• Operations Research
• Computational Science
• Artificial Intelligence

Background:

• Knapsack and generalized assignment problems are NP-hard optimization challenges.
• Mean field theory offers a novel computational approach to complex combinatorial problems.

Purpose of the Study:

• To extend the mean field theory (MFT) approach to multiple knapsack and generalized assignment problems.
• To evaluate the performance of the MFT approach against existing algorithms.
• To explore the suitability of MFT for hardware implementation.

Main Methods:

• Application of Potts mean field equations to model the dynamics of knapsack and assignment problems.
• Numerical testing and comparison with state-of-the-art conventional algorithms.
• Investigation of performance with reduced bit precision in MFT equations.
• Development of a hybrid algorithm combining linear programming and MFT.

Main Results:

• The MFT approach demonstrates good performance, comparable to conventional algorithms.
• Performance remains robust even with limited bit precision, indicating efficiency.
• The parallel nature of MFT equations is suitable for microchip implementation.
• A hybrid LP-MFT algorithm significantly improves performance on homogeneous N x M knapsack problems.

Conclusions:

• Mean field theory provides an effective and efficient method for solving multiple knapsack and generalized assignment problems.
• The MFT approach is computationally efficient and suitable for hardware acceleration.
• Hybrid algorithms can further enhance performance for specific problem instances.