TLDR: This paper introduces a novel approach to large-scale exact optimization by using Domain-Independent Dynamic Programming (DIDP) as a generic pricing solver within the column generation and branch-and-price framework. It details new features in DIDP that enhance its capability for modeling and solving pricing problems, including filter operations, set resource variables, fractional knapsack expressions, and a generic labeling solver. Experimental results across seven problem classes demonstrate that DIDP-backed branch-and-price implementations can outperform state-of-the-art commercial solvers on static mixed-integer programming formulations, highlighting DIDP’s potential for rapid prototyping and bridging mathematical programming with AI search methods.
Large-scale optimization problems are a cornerstone of modern industry and logistics, from scheduling flights to packing goods efficiently. However, these problems often involve an enormous number of variables, making them incredibly difficult to solve using traditional methods. This is where advanced techniques like column generation and branch-and-price come into play, breaking down complex problems into more manageable parts.
A recent research paper, titled “Column Generation Using Domain-Independent Dynamic Programming,” by Ryo Kuroiwa and Edward Lam, introduces a significant advancement in this field. The authors propose using Domain-Independent Dynamic Programming (DIDP) as a generic and flexible tool to solve the ‘pricing problem’ – a crucial, application-specific sub-problem within the column generation framework. Traditionally, solving this pricing problem requires custom-built algorithms tailored to each specific application, which limits reusability and slows down development.
The core idea is to leverage DIDP, a software package designed for modeling and solving arbitrary dynamic programs, as a ‘black-box’ pricing solver. This approach aims to make high-performance column generation more accessible and less reliant on bespoke coding for every new problem. The paper highlights that even basic implementations of branch-and-price, when powered by DIDP for pricing, can surpass the performance of world-leading commercial solvers on static mixed-integer programming formulations across various problem types.
Enhancing DIDP for Optimization
To achieve this, the researchers introduced four key new features to DIDP:
- Filter Operation: This allows for the efficient construction of subsets of elements that satisfy specific conditions, helping to reduce the size of the problem space.
- Set Resource Variables: Extending the concept of ‘state dominance’ (where one problem state is clearly superior to another), this feature allows set variables to be used in defining dominance, leading to more effective pruning of unnecessary states during the search.
- Fractional Knapsack Expression: This new expression type enables the efficient computation of a powerful ‘dual bound’ – a lower estimate of the optimal solution value. This bound is crucial for guiding the search and pruning unpromising paths.
- Generic Labeling Solver: A new search algorithm was developed for DIDP that prioritizes states based on resource variables in a lexicographic order. This mimics the behavior of traditional, problem-specific labeling algorithms often used in vehicle routing problems, but in a generic, domain-independent manner.
Also Read:
- DEEPPLANNER: A New Approach to Sharpen AI Agent Planning for Complex Research
- GammaZero: Guiding AI Decisions in Uncertain Worlds with Graph Representations
Experimental Validation
The effectiveness of this DIDP-backed approach was rigorously tested across seven different NP-hard problem classes:
- Bin Packing Problem (BPP)
- Graph Coloring Problem (GCP)
- Parallel Machine Scheduling Problem (P||ΣwiCi)
- Multi-Runway Aircraft Scheduling Problem (MRASP)
- Vehicle Routing Problem with Time Windows (VRPTW)
- Cumulative Vehicle Routing Problem with Time Windows (CumVRPTW)
- Pickup and Delivery Problem with Time Windows (PDPTW)
The results were compelling. For problems like Parallel Machine Scheduling, the DIDP-backed branch-and-price solved all instances significantly faster than other approaches. While the best DIDP search algorithm (CAASDy or the new Labeling algorithm) varied by problem, the overall performance often matched or exceeded that of commercial solvers like Gurobi and academic solvers like GCG and SCIP on compact MIP formulations. Notably, the traditional labeling algorithm, when generalized through DIDP, proved highly effective for vehicle routing problems, while CAASDy, an AI-community-developed search method, showed strong performance in other areas, including the PDPTW.
This research underscores the immense value of DIDP for rapid prototyping of column generation solvers. It provides a flexible modeling layer combined with a reusable library of search algorithms, offering quick proof-of-concept evidence for new column generation strategies without the need for extensive, specialized coding. The success also highlights the benefits of interdisciplinary collaboration between mathematical programming and artificial intelligence planning communities, paving the way for more generalized and efficient optimization tools. For more details, you can read the full paper here.
