golomb

Golomb Ruler Optimization

C++20 project for finding optimal Golomb rulers using multiple approaches: heuristics, MCTS, and exact methods.

Overview

A Golomb ruler is a set of marks at integer positions such that all pairwise distances are distinct. This project implements three optimization layers:

Core - Bitset-based distance tracking and validation (O(1) distance checks)
Heuristics - Evolutionary algorithm with local search for quick solutions
MCTS - Monte Carlo Tree Search with PUCT selection for balanced exploration
Exact - OR-Tools CP-SAT solver for optimal solutions

Features

Efficient distance tracking: Bitset representation for O(1) conflict detection
Multiple solvers: Evolutionary, MCTS, exact CP-SAT
Modular architecture: Clean separation between core, heuristics, MCTS, and exact layers
Comprehensive testing: Catch2 unit tests and Google Benchmark performance tests
Modern C++: C++20 standard with strict warnings and sanitizers in debug builds

Building

Prerequisites

CMake 3.22+
C++20 compiler (GCC 10+, Clang 13+)
Git (for CPM package manager)

Quick Start

./scripts/build.sh
./scripts/run_tests.sh

# Or manually
mkdir build
cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j
ctest --test-dir build

Pre-built Binaries

Download pre-compiled binaries from the latest successful CI run:

Linux: golomb_cli-Linux artifact

Extract the executable and run directly.

Usage

./build/golomb_cli --order 8 --ub 120 --mode mcts --iters 5000

# Options:
#   --order <n>       Number of marks (default: 8)
#   --ub <value>      Upper bound for positions (default: 120)
#   --mode <mode>     heur|mcts|exact (default: heur)
#   --iters <n>       Iterations for heur/mcts (default: 1000)
#   --c-puct <value>  PUCT exploration constant (default: 1.4)
#   --timeout <ms>    Exact solver timeout (default: 10000)

Architecture

core/              - Distance bitset, validation, state management
utils/             - RNG utilities
heuristics/        - Evolutionary algorithm, local search
mcts/              - PUCT-based MCTS with hooks for policy/value networks
exact/             - OR-Tools CP-SAT solver for exact optimization
cli/               - Command-line interface

See docs/ARCHITECTURE.md for detailed design documentation.

Documentation

Full API documentation is automatically generated with Doxygen and deployed to GitHub Pages:

View Online Documentation

Documentation is automatically updated on every push to the master branch.

Testing

# Run all tests
./scripts/run_tests.sh

# Run benchmarks
./build/golomb_benchmarks

Code Formatting

./scripts/format.sh

Performance Benchmarks

This project uses Google Benchmark for performance testing. Benchmarks run automatically on every push to master, comparing performance with previous commits to detect regressions.

View benchmark results:

Latest benchmark run
Historical benchmark data is stored in the gh-pages branch

Run benchmarks locally:

./build/golomb_benchmarks

Benchmark categories:

Core operations (rule building, validation)
Greedy seed generation (various sizes)
Evolutionary algorithm (different population sizes and iterations)
MCTS (various iteration counts and exploration parameters)
Algorithm comparisons (Greedy vs Evolutionary vs MCTS)

Performance regressions >10% will trigger warnings in pull requests.

Claude Code Integration (MCP)

This project is configured with Model Context Protocol (MCP) servers for enhanced development with Claude Code in VS Code.

Configured MCP servers:

GitHub: Manage issues, PRs, and workflows
Git: Advanced git operations (log, diff, blame)
Filesystem: Extended file system access
Memory: Persistent notes between Claude sessions

Setup instructions: See docs/MCP_GUIDE.md

Prerequisites: Node.js 18+

Contributing

We welcome contributions! This project uses Conventional Commits for automated versioning and changelog generation.

Quick start:

Fork and clone the repository
Create a feature branch: git checkout -b feat/your-feature
Make your changes following our coding standards
Use conventional commit messages (see below)
Run tests and ensure they pass
Submit a pull request

Commit message format:

# Feature (minor version bump)
git commit -m "feat(core): add parallel distance calculation"

# Bug fix (patch version bump)
git commit -m "fix(mcts): correct PUCT formula"

# Breaking change (major version bump)
git commit -m "feat!: redesign API

BREAKING CHANGE: RuleState constructor signature changed"

For detailed guidelines: See CONTRIBUTING.md

Future Work

Optimize CP-SAT model formulation for larger instances
Add neural network policy/value for MCTS
Implement parallel MCTS with virtual loss
Export MCTS tree to Graphviz for visualization
Add ILP formulation with distance variables
Implement Benders decomposition for large instances

License

MIT License - See LICENSE

References

This site is open source. Improve this page.