Verification guided search improves solving of operations research tasks
VERAS: Verification-Guided Adaptive Search for Reliable Operations Research
Software EngineeringArtificial Intelligence
Summary
Operations research problems often need careful checking to make sure solutions really work and meet goals. The authors show that just making a computer check its own solutions doesn’t guarantee they follow all the rules or are the best. They created VERAS, a system that uses a special checker to find problems and guide fixes, improving solution quality and reliability. VERAS performed better than previous methods on benchmark tests and real industry problems.
What this means in practice
- •For logistics planners: Cut peak network bandwidth usage in data centers by applying verification guided solution improvement during planning.
- •For distribution network designers: Reduce annual costs in distribution network planning by integrating adaptive verification feedback into optimization routines.
Authors
Minbo Ma, Honglin Zhang, Bangtao Zhou, Chunguang Yu, Dasheng Ju, Yichen Shen, Fengli Xu, Yong Li
Abstract
Advances in reasoning, coding, and tool use enable LLM agents to solve operations research (OR) problems through iterative problem modeling, program construction, and verification. Yet passing self-authored verification does not ensure that the solutions satisfy task constraints and meet optimization quality. This gap can arise from correlated specification errors, where the generated program and its checks share omissions or misinterpretations of task requirements, alongside incomplete verification coverage and ineffective optimization strategies. We propose VERAS, a verification-guided adaptive search harness for reliable OR that uses verification evidence to prioritize feasibility repair, constraint-coverage review, and solution-quality improvement. VERAS combines task-specific solution checkers with a separate verification agent to examine candidate solutions against the task requirements. It uses verification feedback to guide feasibility repair, additional constraint checking, and objective improvement, while candidate acceptance criteria screen revisions for deterioration in output validity or constraint satisfaction. On ORAgentBench, VERAS achieves a 42.99% pass rate, exceeding the reported 35.51% of Codex using the same LLM. Across two industrial-scale OR problems, VERAS reduces inter-datacenter peak bandwidth by 10.34% relative to native Codex and lowers annualized distribution network planning costs by 6.28% compared with expert-designed solutions. Code and evidence are available at https://github.com/holimario/VERAS.