TLDR: AutoCO is a novel end-to-end method that enables Large Language Models (LLMs) to proactively solve Nonlinear Combinatorial Optimization Problems (NCOPs). It achieves this by using LLMs to generate adaptive constraint relaxation strategies, employing a triple-representation scheme for synchronized evolution of strategies, algorithms, and code, and integrating a bidirectional coevolution mechanism (Evolutionary Algorithms for local refinement and Monte Carlo Tree Search for global exploration). Experiments show AutoCO significantly outperforms traditional and existing LLM-based methods in terms of optimality gap and efficiency across diverse NCOP benchmarks.
Nonlinear Combinatorial Optimization Problems, or NCOPs, are a significant challenge in many fields, from scheduling logistics to managing energy distribution and planning industrial operations. These problems are notoriously difficult because they involve complex, non-convex objectives and constraints, leading to fragmented solution spaces that are hard to navigate efficiently. Traditional methods often rely on experts to manually simplify these constraints, a process that is both time-consuming and difficult to scale.
Recent advancements in Large Language Models (LLMs) have shown promise in automating problem-solving. However, existing LLM-based approaches typically act as passive validators of constraints rather than actively designing strategies to tackle the problem’s core complexity. They often struggle with the intricate interactions between constraints inherent in NCOPs, leading to limited effectiveness.
Introducing AutoCO: A New Paradigm for Optimization
A groundbreaking new method called AutoCO (Automated Constraint Optimization) aims to overcome these limitations by transforming LLMs into proactive strategy architects for NCOPs. This end-to-end approach allows LLMs to “learn to relax” constraints, making complex problems more manageable. The research paper, titled “Learn to Relax with Large Language Models: Solving Nonlinear Combinatorial Optimization Problems via Bidirectional Coevolution,” details this innovative system. You can read the full paper here.
AutoCO introduces several key innovations:
1. LLM-Driven Constraint Relaxation Strategy Generation
Instead of manual expert input, AutoCO uses LLMs to automate the process of constraint relaxation. It works in three steps:
- Constraint Importance Analysis: LLMs analyze the problem description to identify all constraints and assign an importance weight to each, focusing the optimization effort where it matters most.
- Constraint Relaxation Range Suggestion: Based on importance, LLMs suggest adaptive relaxation factor ranges for each constraint, defining how much a constraint can be loosened or tightened.
- Constraint Relaxation Strategy Generation: Combining these insights, the LLM generates an initial set of relaxation strategies, ensuring they are systematically derived rather than random.
2. Triple Representation Scheme
Previous LLM-based methods often used dual representations (algorithm and code), which proved insufficient for NCOPs due to their complex constraint handling. AutoCO introduces a novel triple representation scheme for each potential solution, integrating three coupled components: the constraint relaxation strategy, the algorithmic concept, and the executable code. This unified approach allows LLMs to maintain coherence and reason across different levels of abstraction, facilitating a more effective coevolution of strategy and code.
3. Bidirectional Coevolution Mechanism
To navigate the fragmented and non-convex solution spaces of NCOPs, AutoCO employs a unique bidirectional coevolution mechanism. This mechanism synergistically combines:
- Local Coevolutionary Optimization via Evolutionary Algorithms (EA): EAs perform fine-grained local refinement, exploring promising solutions within a specific area. LLMs guide this evolution, modifying strategies, concepts, and code while maintaining consistency.
- Global Strategy Exploration via Monte Carlo Tree Search (MCTS): MCTS explores the broader constraint relaxation strategy space, providing global guidance. It helps balance exploitation (improving known good solutions) and exploration (finding new promising areas).
This continuous, bidirectional exchange of information allows the system to escape local optima and efficiently explore diverse solution regions, mimicking human-like refinement processes.
Experimental Validation and Performance
The effectiveness and generalizability of AutoCO were validated through extensive experiments on three challenging NCOP benchmarks: Multi-Drone Delivery (MDD), Safety Facility Layout (SFL), and Traveling Salesman with Time Windows (TSPTW). These problems were chosen to represent different levels of nonlinearity, constraint coupling, and solution space fragmentation.
AutoCO consistently demonstrated superior performance compared to traditional methods and existing LLM-based optimization approaches. For instance, it achieved a significant reduction in the optimality gap (the difference from the ideal solution) across various problem sets. In the MDD domain, AutoCO reduced the optimality gap to 20.77% compared to ReEvo’s 55.34%. For TSPTW-C, AutoCO achieved a 58.05% gap, markedly outperforming FunSearch (183.40%) and EoH (134.71%). Overall, AutoCO achieved an average 20.51% reduction in the optimality gap compared to state-of-the-art LLM-based methods.
Beyond solution quality, AutoCO also showed remarkable efficiency in generating initial feasible solutions quickly and minimizing performance stagnation. While its overall runtime might appear longer than some baselines, the time allocation is balanced across global exploration, solution generation, and refinement, leading to a more comprehensive and intelligent search. Ablation studies further confirmed the critical contribution of each component, especially the constraint relaxation module and the bidirectional coevolution mechanism.
Also Read:
- Evo-Merging: Combining Black-Box Language Models for Enhanced AI Services
- Empowering Language Models with Advanced Planning Capabilities
Conclusion
AutoCO represents a significant leap forward in automated optimization, empowering LLMs to move beyond passive validation to become active architects of problem-solving strategies for complex NCOPs. By systematically integrating LLM-driven constraint relaxation, a triple-representation scheme, and a bidirectional coevolution mechanism, AutoCO offers a powerful, end-to-end solution that reduces manual engineering and advances autonomous problem-solving in challenging optimization domains.
