This primer provides a comprehensive guide to using and understanding Google OR-Tools' CP-SAT solver, targeting computer science students and engineers familiar with Python and combinatorial optimization. It bridges the gap between theoretical optimization and practical implementation, offering a hands-on approach with numerous code examples. The CP-SAT solver is presented as a powerful alternative to traditional Mixed Integer Programming (MIP) solvers, particularly effective for problems with complex logical constraints.

How It Works

CP-SAT is a constraint programming solver that leverages techniques from SAT solvers and Mixed Integer Programming. It models optimization problems declaratively using variables, constraints, and an objective function. The solver then uses advanced techniques like propagation, domain reduction, and search strategies to efficiently find optimal or feasible solutions, often outperforming MIP solvers on problems with intricate logical structures. Its Python API closely mirrors mathematical notation, facilitating easier model formulation and debugging.

Quick Start & Requirements

• Install: pip install -U ortools
• Requirements: Python 3, standard laptop sufficient (minimum 4 cores, 16GB RAM recommended). GPU is unnecessary.
• Documentation: https://d-krupke.github.io/cpsat-primer/

Highlighted Details

• Covers fundamental CP-SAT concepts: installation, basic and advanced modeling, parameter tuning, log interpretation, and underlying techniques.
• Explores specialized constraints for routing (circuit, multiple_circuit), scheduling (intervals, no_overlap, cumulative), and packing problems.
• Discusses practical aspects like coding patterns, building optimization APIs, benchmarking, and integrating CP-SAT with ML.
• Provides detailed comparisons with MIP, SAT solvers, SMT, NLP, and modeling languages.
• Includes advanced topics like Large Neighborhood Search (LNS) for tackling larger problems and Multi-Objective Optimization.

Maintenance & Community

The primer is authored by Dominik Krupke with contributions from Leon Lan, Michael Perk, and others. It encourages community contributions via GitHub issues and pull requests. Contact is available via email.

Licensing & Compatibility

Content is freely usable under CC-BY 4.0. Smaller parts can be copied for non-commercial, educational purposes without acknowledgment.

Limitations & Caveats

CP-SAT does not support continuous variables directly; they must be approximated with integers. While powerful, it may not always match the raw speed of specialized SAT or MIP solvers on problems purely dominated by boolean logic or linear constraints, respectively. The primer notes that some advanced features or parameter tuning might require significant expertise.