column-generation
When the user wants to solve large-scale optimization problems using column generation, decomposition methods, or Dantzig-Wolfe decomposition. Also use when the user mentions "column generation," "master problem," "pricing problem," "cutting stock," "crew scheduling," "vehicle routing with column gen," "branch-and-price," or when the problem has exponentially many variables. For general optimization, see optimization-modeling. For metaheuristics, see metaheuristic-optimization.
npx skills add majiayu000/claude-skill-registry --skill column-generation-kishorkukreja-awesome-supply-chain --agent claude-code
Same command for any agent — swap --agent for codex, cursor, copilot.
Weekly change comes from our own snapshots, not the repository page — it measures attention, not adoption.
What it does
Implements column generation and decomposition methods for large-scale optimization problems with exponentially many variables. It guides the agent to use a master problem to select a subset of patterns and a pricing subproblem to generate new patterns, iterating until no improving pattern exists, then solves a final integer program to obtain a concrete solution.
How it works
- Starts with an initial set of simple patterns that fit within the roll width for cutting stock.
- Repeatedly:
- Solve the Restricted Master Problem (RMP) to minimize total rolls while meeting piece demands; obtain dual values (shadow prices).
- Solve the Pricing Problem (a knapsack-style subproblem) to maximize the dual-weighted value of a new pattern under the roll width constraint; compute reduced cost as 1.0 minus the pattern value.
- If the reduced cost is negative, add the new pattern to the pool and repeat; otherwise stop.
- After termination, solves a final Mixed Integer Program (MIP) using all generated patterns to minimize total rolls and extract pattern usage.
- Provides auxiliary methods to print the solution, plot convergence, and visualize patterns.
When to use it
Use when solving large-scale optimization problems with exponentially many variables where a column-generation approach is appropriate, especially cutting stock, and generally large-scale decomposable problems requiring a master–pricing structure. Triggered when the problem resembles a set-partitioning master problem with a pricing subproblem under resource constraints.
What it can touch
- It relies on tools and libraries for linear and integer programming: the implementation uses PULP with the CBC solver for both master and pricing problems, and for final MIP.
- It handles data structures for patterns as dictionaries mapping piece types to counts, and keeps patterns in a list for iteration.
Caveats
- Depends on CBC solver availability through PULP; performance is solver-driven.
- Dual extraction from the master problem uses a fallback heuristic if duals aren’t accessible from constraints.
- Termination relies on reduced cost threshold (-1e-6) to declare optimality; numerical issues may affect convergence.
- The initial patterns and final MIP assume integer usage of patterns and demand satisfaction as stated in the code.
# Column Generation You are an expert in column generation and decomposition methods for large-scale supply chain optimization. Your goal is to help solve problems with exponentially many variables by generating only relevant columns (variables) on demand, making previously intractable problems solvable. ## Initial Assessment Before applying column generation, understand: 1. **Problem Structure** - Does problem have exponentially many variables? - Can it be decomposed into master and subproblems? - Is there a natural decomposition structure? - Are constraints decomposable? 2. **Problem Characteristics** - Problem type? (cutting stock, routing, crew scheduling, packing) - Size? (thousands to millions of variables) - Why is standard MIP approach failing? - Required solution quality? 3. **Computational Environment** - Solver access? (need LP/MIP solver) - Subproblem complexity? (easy or hard to solve) - Time constraints? - Parallel computing available? 4. **Technical Expertise** - Team familiarity with column generation? - Ability to formulate subproblem? - Need for exact vs. heuristic solutions? --- ## Column Generation Framework ### Core Concept **Problem Decomposition:** - **Master
- Initial Assessment
- Column Generation Framework
- Core Concept
- Mathematical Foundation
- Cutting Stock Problem with Column Generation
- Problem Description
- Implementation
- Vehicle Routing with Column Generation
- Route-Based Formulation
- Implementation Outline
- Branch-and-Price
- Combining Column Generation with Branch-and-Bound
- Implementation Sketch
- Advanced Column Generation Techniques
What does the column-generation skill do?
When the user wants to solve large-scale optimization problems using column generation, decomposition methods, or Dantzig-Wolfe decomposition. Also use when the user mentions "column generation," "master problem," "pricing problem," "cutting stock," "crew scheduling," "vehicle routing with column gen," "branch-and-price," or when the problem has exponentially many variables. For general optimization, see optimization-modeling. For metaheuristics, see metaheuristic-optimization.
How do I install it?
Run `npx skills add majiayu000/claude-skill-registry --skill column-generation-kishorkukreja-awesome-supply-chain --agent claude-code` — it drops the skill into your project so the agent can pick it up. Swap the --agent value for codex, cursor or copilot if you use one of those.
Where does this skill come from?
From majiayu000/claude-skill-registry, a repository with 534 stars. We read it straight from the repository tree rather than a submitted listing, so what you see here is what is actually published.
Is a popular skill a good skill?
Not necessarily. Stars measure attention, not adoption — a repository can trend for a week and be abandoned. That is why we show the weekly change from our own snapshots next to the total, instead of a single flattering number.