NP-Engine: Enhancing Large Language Models' Optimization Reasoning Capabilities with Verifiable Synthetic NP Problems

The NP-Engine project systematically enhances the reasoning capabilities of large language models (LLMs) in combinatorial optimization by generating verifiable synthetic NP-hard problems, filling the gap of LLMs' lack of specialized optimization training data, and providing a new training paradigm for practical scenarios such as operations research and scheduling optimization.

LLMs perform well in tasks like natural language processing, but they lack capabilities when dealing with combinatorial optimization NP-hard problems (e.g., TSP, knapsack problem); traditional optimization algorithms rely on expert design, while LLMs lack targeted training data. The goal of NP-Engine is to automatically generate verifiable synthetic NP problems to provide high-quality optimization reasoning training data for LLMs.

1. Problem Generator: Generates diverse NP-hard problems (including combinatorial optimization, constraint satisfaction, resource allocation types), considering structural characteristics and difficulty gradients; 2. Verifiability Guarantee: For small-scale problems, use exact algorithms to find optimal solutions; for large-scale ones, use verified heuristic algorithms to get reference solutions, ensuring the accuracy of problem-solution pairs; 3. Reasoning Chain Construction: Draw on chain-of-thought technology to record fine-grained supervision signals such as intermediate decision steps and pruning strategies for optimization problems.

• Controllable Scale and Difficulty Stratification: Supports scales from tens to thousands of variables, with difficulty levels progressing step by step; - Wide Domain Coverage: Covers multiple fields such as operations research and computer science, enhancing the model's generalization ability; - Solution Quality Assurance: All solutions are strictly verified to ensure correctness or quantifiable bounds of approximate optimality.

LLMs fine-tuned with NP-Engine data show significant improvements: 1. Solution Accuracy: For small and medium-scale problems, generates near-optimal or optimal solutions; 2. Reasoning Efficiency: Converges to high-quality solutions with fewer iterative steps; 3. Cross-Problem Generalization: Shows good transferability on unseen new types of optimization problems.

• Supply Chain and Logistics: Assists in path planning, inventory management, etc., reducing costs and improving efficiency; - Production Scheduling: Optimizes job shop scheduling and resource allocation, enhancing production efficiency; - Network Design: Supports communication network topology and traffic scheduling optimization, building efficient and reliable infrastructure.

Methodological Insights: Synthesizing high-quality data can enhance LLMs' reasoning capabilities in specific domains and can be extended to other mathematical and engineering fields. Future directions include multimodal fusion, online learning, and human-machine collaborative optimization. Conclusion: NP-Engine opens up new possibilities for the application of LLMs in combinatorial optimization and is expected to play a key role in more deep mathematical reasoning scenarios.