A high-performance, extensible framework for solving optimization problems using Column Generation. Built with a Python frontend and C++ backend for optimal balance of usability and speed.
- High-Performance C++ Backend: SPPRC labeling algorithm with parallel execution
- Pure Python API: Easy to use, extend, and integrate
- Multiple Problem Types:
- Cutting Stock / Bin Packing
- Capacitated Vehicle Routing (CVRP)
- Vehicle Routing with Time Windows (VRPTW)
- Airline Crew Pairing
- Extensible Resource System: Accumulating, interval, state, and time window resources
- Multiple LP Solvers: HiGHS (default, open-source), CPLEX (optional)
- Parallel Pricing: Multi-threaded labeling for faster convergence
┌───────────────────────────────────────────────────────────────┐
│ Python Layer (User-facing API) │
│ - Problem definition (Network, Resources, Constraints) │
│ - Application solvers (Cutting Stock, VRP, Crew Pairing) │
│ - Parsers (BPPLIB, Kasirzadeh, Solomon) │
│ - Column generation orchestration │
├───────────────────────────────────────────────────────────────┤
│ C++ Core (Performance-critical) via pybind11 │
│ - Network/Arc/Node data structures │
│ - SPPRC labeling with dominance pruning │
│ - Parallel labeling (std::async) │
│ - ng-path relaxation, time windows │
└───────────────────────────────────────────────────────────────┘
See Architecture Guide for the complete picture: how components connect, the CG loop, and customization points.
- Python 3.9+
- C++ compiler with C++17 support
- CMake 3.15+
# Clone the repository
git clone https://github.com/miladbarooni/opencg.git
cd opencg
# Create conda environment (recommended)
conda env create -f environment.yml
conda activate opencg
# Install in development mode
pip install -e .from opencg._core import HAS_CPP_BACKEND
print(f"C++ backend available: {HAS_CPP_BACKEND}")from opencg.applications.cutting_stock import CuttingStockInstance, solve_cutting_stock
# Define instance
instance = CuttingStockInstance(
roll_width=100,
item_sizes=[45, 36, 31, 14],
item_demands=[97, 610, 395, 211],
name="example"
)
# Solve
solution = solve_cutting_stock(instance, max_iterations=100, verbose=True)
print(f"Rolls needed: {solution.num_rolls_ip}")from opencg.applications.vrp import CVRPInstance, solve_cvrp
instance = CVRPInstance(
depot=(0, 0),
customers=[(10, 0), (0, 10), (-10, 0), (0, -10)],
demands=[20, 15, 25, 10],
vehicle_capacity=50,
)
solution = solve_cvrp(instance)
print(f"Total distance: {solution.total_distance:.2f}")
for route in solution.routes:
print(f" Route: {route}")from opencg.applications.vrp import VRPTWInstance, solve_vrptw
instance = VRPTWInstance(
depot=(0, 0),
customers=[(10, 0), (0, 10)],
demands=[20, 15],
time_windows=[(0, 50), (20, 80)],
service_times=[10, 10],
vehicle_capacity=50,
depot_time_window=(0, 200),
)
solution = solve_vrptw(instance)from opencg.parsers import KasirzadehParser
from opencg.applications.crew_pairing import solve_crew_pairing
# Load benchmark instance
parser = KasirzadehParser()
problem = parser.parse("data/kasirzadeh/instance1")
# Solve with per-source pricing (high coverage)
solution = solve_crew_pairing(problem, use_per_source=True, verbose=True)
print(f"Coverage: {solution.coverage:.1f}%")For large problems, enable parallel pricing to speed up the labeling algorithm:
from opencg.pricing.fast_per_source import FastPerSourcePricing
from opencg.pricing import PricingConfig
pricing = FastPerSourcePricing(
problem,
config=PricingConfig(max_columns=200),
num_threads=8 # Use 8 threads (0 = auto-detect)
)Benchmark results on Kasirzadeh instance1 (1013 flights):
| Threads | Pricing Time | Speedup |
|---|---|---|
| 1 | 0.97s | 1.0x |
| 4 | 0.37s | 2.6x |
| 8 | 0.23s | 4.3x |
See the examples/notebooks/ directory for detailed tutorials:
- 01_cutting_stock.ipynb - Cutting stock basics and BPPLIB benchmarks
- 02_vehicle_routing.ipynb - CVRP with capacity constraints
- 03_crew_pairing.ipynb - Airline crew scheduling with multiple resources
- 04_parallel_pricing.ipynb - Parallel pricing performance
For detailed guides, see the docs/ directory:
| Guide | Description |
|---|---|
| Quick Start | Get started in 30 minutes |
| Building Networks | Construct time-space networks for your problem |
| Custom Resources | Create new resource constraints (time, capacity, skills) |
| Custom Pricing | Implement your own SPPRC pricing algorithms |
| Custom Master | Use different LP/MIP solvers (Gurobi, CPLEX) |
| Custom Applications | Model new optimization problems |
OpenCG is designed to be extensible. Here's a quick preview - see docs/ for complete guides.
from opencg.core.resource import Resource
class MyResource(Resource):
def extend(self, current_value, arc):
return current_value + arc.get_consumption(self.name, 0.0)
def is_feasible(self, value, node):
return value <= self.max_value
def dominates(self, value1, value2):
return value1 <= value2from opencg.pricing.base import PricingProblem
class MyPricing(PricingProblem):
def _solve_impl(self):
# Your pricing algorithm
columns = self._find_columns()
return PricingSolution(columns=columns, ...)See Custom Pricing Guide for complete examples including knapsack pricing and MIP-based pricing.
opencg/
├── opencg/ # Python package
│ ├── core/ # Core data structures (Node, Arc, Network, Column)
│ ├── master/ # LP/MIP solvers (HiGHS, CPLEX)
│ ├── pricing/ # SPPRC algorithms (labeling, per-source)
│ ├── solver/ # Column generation coordinator
│ ├── parsers/ # File format readers
│ └── applications/ # Domain-specific solvers
│ ├── cutting_stock.py
│ ├── crew_pairing/
│ └── vrp/
├── src/ # C++ source code
│ ├── core/ # C++ data structures
│ ├── pricing/ # C++ SPPRC implementation
│ └── bindings/ # pybind11 Python bindings
├── tests/ # Test suite
├── examples/ # Jupyter notebooks and scripts
└── data/ # Benchmark instances
- numpy: Array operations
- highspy: HiGHS LP solver (bundled)
- pybind11: C++/Python bindings (build only)
- matplotlib (optional): Visualization in notebooks
Tested on Windows 10, Intel Core i7-8700 (6 cores), 4 threads:
| Instance | Flights | Our Time | Lit. Time | Speedup | Coverage | Status |
|---|---|---|---|---|---|---|
| I1-727 | 1,013 | 82s | 150s | 1.83x faster | 100% | OPTIMAL |
| I2-DC9 | 1,500 | 294s | 260s | 0.89x | 100% | OPTIMAL |
| I3-D94 | 1,855 | 704s | 548s | 0.78x | 100% | OPTIMAL |
Key findings:
- 100% flight coverage on all instances (matches literature)
- 10-140x fewer iterations (11-21 vs 239-1968 in literature)
- Competitive runtime - faster on small instances, within 20-30% on larger ones
See PROJECT_STATUS.md for detailed results, known issues, and roadmap.
- The C++ backend provides 10-100x speedup over pure Python for labeling
- GIL is released during C++ solve(), enabling true parallel execution
- Per-source pricing is the key innovation achieving 100% coverage for crew pairing
- Use
max_labels_per_nodefor beam search (faster but heuristic)
MIT License - see LICENSE for details.
If you use OpenCG in your research, please cite:
@software{opencg2024,
title = {OpenCG: Open-Source Column Generation Framework},
author = {Barooni, Milad},
year = {2024},
url = {https://github.com/miladbarooni/opencg}
}- Kasirzadeh benchmark instances from airline crew pairing research
- BPPLIB bin packing benchmark library
- HiGHS open-source LP solver