CO-Bench
Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization
Carnegie Mellon University
CO-Bench evaluates the capability of LLM agents to autonomously design efficient algorithms for real-world challenging combinatorial optimization problems.
Method
Avg Score
Valid Solution
Above Classical
Survival Rate
Classical Solver
Classical Solver
LLM Agents
o3-mini + Greedy Refine
o3-mini + BestOfN
Reasoning LLMs
Base LLMs
Evaluation Setup: All LLM agents use o3-mini as the base model, evaluated over 64 iterations with a 10-second timeout per solution across 36 combinatorial optimization problems.
Metrics Explained:
• Avg Score: Average normalized solution quality across all 36 problems (higher is better)
• Valid Solution: Percentage of problems where a valid, feasible solution was generated
• Above Classical: Percentage of problems where the method outperforms classical solvers
• Survival Rate: Weighted metric combining solution quality and constraint satisfaction
About CO-Bench
What is CO-Bench?
CO-Bench is a comprehensive benchmark designed to evaluate Large Language Model (LLM) agents in developing efficient algorithms for combinatorial optimization problems. Unlike existing benchmarks that focus on solution correctness for small instances, CO-Bench emphasizes end-to-end algorithm design from abstract problem descriptions, evaluating agents' ability to discover efficient and potentially novel algorithms.
Problems
CO-Bench includes 36 real-world problems across diverse categories. Click on each problem to view its full description.
Packing problems (9)
Bin Packing - One-Dimensional
Minimize the number of bins required to pack items while ensuring the sum of item sizes within each bin does not exceed the specified bin capacity.
Multi-Demand Multidimensional Knapsack
Binary optimization extending classical knapsack with both upper-bound (≤) and lower-bound (≥) constraints, maximizing profit subject to resource limits and demand fulfillment requirements.
Multidimensional Knapsack Problem
Maximize total profit by selecting items associated with profit and resource consumption across multiple constraints, where resource usage must not exceed capacity for any constraint.
Container Loading
Given a 3D container and multiple box types, optimally place boxes to maximize volume utilization while respecting orientation constraints, boundary limits, and avoiding overlaps.
Container Loading with Weight Restrictions
Maximize container volume utilization by strategically placing boxes while adhering to spatial constraints, load-bearing limits, and orientation restrictions.
Packing Unequal Circles
Pack a subset of unequal circles into a fixed circular container to maximize the number of circles packed, ensuring all circles lie within the container and do not overlap.
Packing Unequal Circles (Area)
Pack circles into a circular container to maximize total area of packed circles while ensuring containment and non-overlap constraints are satisfied.
Packing Unequal Rectangles and Squares
Pack rectangles and squares into a circular container to maximize the number of packed items, with optional 90° rotation, ensuring all items fit within the circle without overlapping.
Packing Unequal Rectangles and Squares (Area)
Select and place rectangles/squares into a circular container to maximize total area, allowing 90° rotations while ensuring all corners lie within the circle and no overlaps occur.
Scheduling problems (7)
Aircraft Landing
Schedule landing times for planes across runways such that each landing occurs within its time window and all separation requirements are satisfied. Minimize total penalty cost from earliness and tardiness while ensuring no constraints are violated.
Common Due Date Scheduling
Determine an optimal job sequence that minimizes penalties from earliness and tardiness relative to a common due date, where the due date is computed as a fraction of total processing time.
Crew Scheduling
Assign tasks to crews to minimize transition costs between consecutive tasks, ensuring no overlaps, valid transitions exist, duty time limits are respected, and at most K crews are used.
Flow Shop Scheduling
Given n jobs and m machines, determine the optimal job sequence that minimizes the makespan. Each job follows the same machine order with specified processing times.
Hybrid Reentrant Shop Scheduling
Each job undergoes three operations: initialization on primary machines, setup on a remote server, and final processing on the same primary machine. Minimize makespan while ensuring precedence constraints.
Job Shop Scheduling
Assign start times to operations structured into sequential jobs, minimizing makespan while ensuring sequential processing within jobs and non-overlapping operations on machines.
Open Shop Scheduling
Schedule jobs across machines to minimize makespan where operations can be scheduled in any order, but each job processes on one machine at a time and each machine processes one job at a time.
Graph and set problems (5)
Maximum Independent Set (MIS)
Find the largest subset of vertices in an undirected graph such that no two vertices in the subset are adjacent (connected by an edge).
Graph Colouring
Assign positive integer colors to vertices ensuring no two adjacent vertices share the same color while minimizing the number of distinct colors used.
Equitable Partitioning Problem
Partition individuals with binary attributes into exactly 8 groups to minimize total imbalance, measured as average absolute differences from mean attribute counts across groups.
Set Partitioning
Choose columns to partition rows such that each row is covered exactly once while minimizing total cost of selected columns.
Set Covering
Select a subset of columns with associated costs such that every row is covered by at least one chosen column, minimizing total cost.
Facility location problems (4)
Capacitated Warehouse Location
Determine which warehouses to open and how to allocate portions of customer demands with splittable demand to minimize total costs while satisfying demand and capacity constraints.
Uncapacitated Warehouse Location
Select warehouses to open and assign each customer entirely to one open warehouse to minimize the sum of fixed opening costs and customer assignment costs.
p-Median - Capacitated
Select exactly p customers as medians and assign each customer to minimize total Euclidean distance cost while respecting capacity constraint Q for each median.
p-Median - Uncapacitated
Select p vertices as medians to minimize the sum of shortest distances from each vertex to its nearest median in a graph with precomputed cost matrix.
Cutting problems (4)
Assortment Problem
Arrange rectangular pieces within stock rectangles to minimize waste area percentage, allowing 90° rotation, with unlimited stock types (max 2 types) and specific quantity constraints per piece type.
Constrained Guillotine Cutting
Optimize guillotine-feasible placement of rectangular pieces on stock to maximize total value, where pieces can be cut via straight cuts (vertical/horizontal) that recursively partition the stock.
Constrained Non-Guillotine Cutting
Arrange rectangular pieces on stock with fixed dimensions to maximize total value, subject to piece usage constraints [min, max], optional 90° rotation, and non-overlap requirements.
Unconstrained Guillotine Cutting
Select and place rectangular pieces within a fixed stock to maximize total value, with optional 90° rotation and at most one use per piece, ensuring no overlaps and complete containment.
Routing problems (3)
TSP
The Traveling Salesman Problem (TSP) is a classic combinatorial optimization problem where, given a set of cities with known pairwise distances, the objective is to find the shortest possible tour that visits each city exactly once and returns to the starting city.
Vehicle Routing: Period Routing
The Period Vehicle Routing Problem requires planning delivery routes over a multi-day planning period. Each customer must be assigned one service schedule, and daily tours must be designed respecting capacity constraints while minimizing total distance traveled.
Resource Constrained Shortest Path
Find the shortest path from vertex 1 to vertex n in a directed graph while satisfying resource constraints, where cumulative consumption must fall within bounds for each resource type.
Assignment problems (2)
Assignment Problem
Optimally assign n items to n agents based on a cost matrix to minimize total assignment cost, where each item is assigned to exactly one agent.
Generalised Assignment Problem
Assign n jobs to m agents such that each job is assigned to exactly one agent and resource consumption per agent does not exceed capacity, optimizing total cost.
Tree problems (2)
Euclidean Steiner Problem
Compute a tree connecting all 2D terminal points with minimum total Euclidean length. Unlike MST, Steiner trees may introduce extra points (Steiner points) to reduce overall length.
Corporate Structuring
Construct a valid tree-structured corporate hierarchy rooted at a target to maximize after-tax income, considering different tax codes (Exemption, Deduction, Pooling) and withholding tax rates.
Citation
If you use CO-Bench in your research, please cite our paper:
@inproceedings{sun2025cobench,
title={CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization},
author={Sun, Weiwei and Feng, Shengyu and Li, Shanda and Yang, Yiming},
booktitle={AAAI Conference on Artificial Intelligence (AAAI)},
year={2026}
}