🤖 AI

Column Generation with Domain-Independent Dynamic Programming

This paper demonstrates that domain-independent dynamic programming (DIDP) can serve as a high-performance, generic pricing solver for column generation and branch-and-price, empirically outperforming existing automated solvers and specialized methods across four problem classes.

Original authors: Ryo Kuroiwa, Edward Lam

Published 2026-07-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ryo Kuroiwa, Edward Lam

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the captain of a massive cargo ship trying to deliver thousands of packages to different cities. You have a map, but the map is so huge that listing every single possible route from every port to every city would take longer than the age of the universe. This is the kind of headache mathematicians and computer scientists face when they try to solve "optimization" problems—finding the absolute best way to do something, like scheduling flights, routing delivery trucks, or assigning jobs to machines.

To tackle this, they use a clever trick called Column Generation. Think of it like building a puzzle. Instead of dumping the entire box of 10,000 pieces on the table and trying to fit them all at once, you start with just a few pieces. You solve the puzzle with those few, then ask a smart assistant: "Is there a piece I'm missing that would make this picture even better?" If the assistant finds one, you add it and solve again. You keep doing this until no better pieces can be found. The "assistant" is a special program called a pricing solver. Its job is to hunt for those missing, better pieces.

For a long time, these assistants were like custom-built robots. If you wanted to solve a trucking problem, you built a robot specifically for trucks. If you wanted to solve a flight schedule, you built a different robot for planes. These custom robots were super fast because they knew exactly how the problem worked, but they were terrible at learning new things. If you wanted to solve a slightly different problem, you had to build a whole new robot from scratch. This paper asks a big question: Can we build a "universal" assistant that is smart enough to handle any puzzle, but still fast enough to beat the custom robots?

The authors of this paper, Ryo Kuroiwa and Edward Lam, say "Yes, but we need to upgrade the brain." They introduce a method called Domain-Independent Dynamic Programming (DIDP). Think of this as a general-purpose thinking engine that doesn't need to be reprogrammed for every new puzzle. However, the standard version of this engine was a bit slow and clumsy when acting as the "assistant" for these massive puzzles.

To fix this, the authors gave the engine three new superpowers:

The "Filter" Goggles: Imagine you are looking for a needle in a haystack, but you know the needle is only in the top half of the hay. The new "filter" lets the engine instantly ignore the bottom half without even touching it. In math terms, this helps the engine quickly rule out impossible paths in a schedule.
The "Set" Backpack: Sometimes, the best way to know if a path is good is to look at the collection of things you've already picked up, not just the last thing you picked up. The new "set resource" feature lets the engine carry a backpack of items and instantly know if a new path is worse than one it's already seen, just by checking what's inside the bag.
The "Fractional" Calculator: This is a special math trick that lets the engine make a very quick, smart guess about how good a solution could be, even if it hasn't finished counting everything. It's like estimating the total weight of a suitcase by weighing a few items and doing a quick calculation, rather than weighing every single sock individually.

They also built a new way for the engine to explore the puzzle, called a labeling solver. Instead of just wandering around randomly or following a strict map, this new explorer prioritizes paths that look the most promising based on the "backpack" and "goggles" features.

When they tested this upgraded universal assistant on four different types of real-world problems—like routing delivery trucks with time windows, scheduling aircraft on runways, and assigning jobs to machines—it didn't just keep up; it raced ahead. In their experiments, the new DIDP method solved these problems much faster than the old custom robots and other generic methods that use different types of math (like Mixed-Integer Programming or Constraint Programming).

For example, in the truck routing tests, the new method was often dozens of times faster at finding the "missing pieces" than the other generic methods. While the custom robots (built specifically for one problem) are still the fastest in some very specific cases, this new universal engine is a huge leap forward. It proves that we don't always need to build a new robot for every new puzzle; with the right upgrades, one smart, flexible brain can handle a wide variety of complex challenges efficiently. The paper shows that by adding these specific modeling features and a smarter search strategy, a generic solver can finally compete with the specialized experts, making it easier to solve huge, complicated optimization problems without needing a team of specialists to build custom code for every single one.

Technical Summary: Column Generation with Domain-Independent Dynamic Programming

Problem Statement
Column generation and Branch-and-Price (B&P) are leading methods for solving large-scale exact optimization problems, such as routing and scheduling. These methods iterate between solving a restricted master problem and a pricing problem to generate columns with negative reduced costs. While high-performance column generation often relies on custom pricing algorithms—typically using problem-specific dynamic programming (DP)—this bespoke nature hinders the development of generic solvers. Existing generic approaches, such as those using Mixed-Integer Programming (MIP) or Constraint Programming (CP), often lack the efficiency of specialized DP algorithms. Conversely, specialized DP algorithms are difficult to generalize due to their implementation complexity. The paper addresses the challenge of creating a generic, high-performance pricing solver that retains the strengths of DP without requiring problem-specific coding.

Methodology
The authors propose using Domain-Independent Dynamic Programming (DIDP), a model-based paradigm based on the Dynamic Programming Description Language (DyPDL), as a generic pricing solver. Instead of implementing custom algorithms, the pricing problem is formulated as a declarative DP model and solved by general-purpose solvers.

To achieve performance competitive with specialized algorithms, the authors introduce three new modeling features and a new solving algorithm within the didp-rs software framework:

New Modeling Features:
- Higher-Order Expressions: Specifically, filter and reduce operations. These allow expressions to be applied to each element of a set, enabling complex state updates (e.g., removing nodes from an unvisited set based on deadline or capacity constraints) that were previously difficult to represent declaratively.
- Set Resource Variables: Extending the concept of resource variables (used for state dominance) to set variables. This allows a state to be dominated if its set of unvisited nodes is a subset (or superset) of another state's set, in addition to numeric resource comparisons.
- Fractional Knapsack Expression: A new expression to compute the Dantzig bound for the 0-1 knapsack problem in polynomial time. This serves as a powerful dual bound function for pricing problems where a subset of elements with negative reduced costs must be selected under resource constraints.
New Solving Algorithm (Generic Labeling Solver):
Unlike existing DIDP solvers (e.g., CAASDy, CABS) that select states based on $f$ -values (sum of path cost and heuristic estimate), the authors propose a labeling solver inspired by specialized SPPRC (Shortest Path Problem with Resource Constraints) algorithms.
- Selection Strategy: States are selected from the open list based on the lexicographic order of resource variables (e.g., preferring states with lower load or earlier time).
- Rationale: Expanding states with "better" resource values first increases the likelihood of finding high-quality columns early and pruning dominated states more effectively, aligning with the heuristic pricing strategies common in specialized solvers.

Case Studies and Implementation
The authors implemented B&P using their DIDP framework for four problem classes:

VRPTW (Vehicle Routing Problem with Time Windows): The pricing problem is an SPPRC.
PDPTW (Pickup and Delivery Problem with Time Windows): A variant of VRPTW.
$P||\sum w_j C_j$ (Parallel Machine Scheduling): A scheduling problem where the pricing problem involves selecting a job sequence.
MRASP (Multi-Runway Aircraft Scheduling): A complex scheduling problem involving separation times that do not satisfy the triangle inequality.

For all problems, the authors formulated the Master Problem (MP) in MIP and the pricing problem as a DIDP model, utilizing the new features (e.g., fractional knapsack bounds for VRPTW/PDPTW, set resource variables for MRASP).

Experimental Results
The authors compared their B&P DIDP approach against:

B&P MIP: Pricing solved via Gurobi.
B&P CP: Pricing solved via Google OR-Tools CP-SAT.
GCG: An automated B&P solver using SCIP for pricing.
VRPSolverEasy: A proprietary solver for VRPTW (used as a baseline for that specific class).

Key Findings:

Performance: B&P DIDP empirically outperformed generic B&P baselines (MIP and CP) and the automated solver GCG across all four problem classes.
Efficiency: DIDP was significantly faster in solving individual pricing problems (up to hundreds of times faster in some cases) and generally required fewer total iterations or generated more columns per iteration, leading to faster convergence.
Ablation Study:
- The labeling solver (resource-based selection) generally outperformed $f$ -value-based solvers (CAASDy, CABS) in terms of overall B&P performance, particularly in VRPTW and MRASP, by generating more promising columns earlier.
- The new modeling features (filter, set resource variables, fractional knapsack) consistently improved performance. Disabling the filter operation significantly increased state expansions and solving time. The fractional knapsack bound proved crucial for reducing search effort.

Significance and Claims
The paper claims to demonstrate that DIDP can serve as a generic pricing solver that bridges the gap between the flexibility of declarative modeling and the efficiency of specialized dynamic programming. By introducing specific modeling features and a labeling-based search strategy, the authors show that it is possible to achieve state-of-the-art performance on complex routing and scheduling problems without writing problem-specific pricing algorithms.

The authors modestly conclude that while their approach outperforms generic baselines, a gap remains compared to highly tuned, problem-specific B&P implementations. They identify future work in developing DIDP solvers specifically for heuristic pricing and incorporating problem-specific cuts to further close this gap.

Technical Summary: Column Generation with Domain-Independent Dynamic Programming

More like this