CP-SAT Primer

The CP-SAT Primer is divided into two main parts:

Part 1: The Basics

Focuses on fundamental CP-SAT features:

• Installation & Hardware: Setting up the environment.
• Basic Modeling: Creating variables, objectives, and constraints.
• Advanced Modeling: Handling complex constraints like circuit constraints and intervals.
• Solver Behavior: Specifying parameters (time limits, parallelization), interpreting logs, and understanding the search core.
• Context: Comparing CP-SAT with other techniques and using MathOpt as a modeling layer.

Part 2: Advanced Topics

Focuses on engineering and deployment skills:

• Coding Patterns: Design patterns for maintainable algorithms.
• Deployment: Building optimization APIs for long-running jobs.
• Heuristics & Benchmarking: Developing powerful heuristics (e.g., Large Neighborhood Search) and scientifically benchmarking models.

MathOpt is a solver-agnostic modeling layer provided by Google OR-Tools. It offers a modern API for defining linear programs (LPs) and mixed-integer programs (MIPs).

Key Benefits

• Solver Agnostic: Easily switch between different solvers (e.g., HiGHS, Gurobi, CP-SAT) to find the best performance for your problem.
• Continuous Variables: Unlike CP-SAT, MathOpt supports continuous variables and floating-point coefficients when using compatible backends.

Limitations and Caveats

• CP-SAT Backend: When using CP_SAT as the backend, MathOpt's continuous and floating-point features are unavailable. You must discretize variables and coefficients to use CP-SAT.
• Constraint Types: MathOpt currently only supports linear constraints. It does not support non-linear operators like !=, <, or > (use equality or inequality forms instead).
• Overhead: There is a small amount of overhead compared to using a solver's native API directly.

Property-based testing is a methodology where you specify general properties (invariants) that your code must satisfy, and a tool automatically generates a wide range of test cases to verify them.

Unlike naive random testing, libraries like Hypothesis use strategies to systematically generate inputs. If a failure is found, the library performs shrinking—attempting to find the smallest possible counterexample that still triggers the failure. This makes debugging much easier.

In the context of optimization problems, property-based testing is used to ask questions like:

• "For any valid instance of my optimization problem, does the solver return a feasible solution (or report infeasibility correctly)?"
• "For any valid instance of the nurse rostering problem, is there always sufficient staffing to cover every shift?"

This approach complements unit tests: use unit tests for clear, deterministic components, and property-based tests to explore a wide space of edge cases and schema invariants.

Large Neighborhood Search (LNS) is a meta-heuristic technique used to solve large-scale optimization problems that might be too difficult for standard CP-SAT execution alone.

Instead of generating individual neighbor solutions one by one, LNS uses a "destroy and repair" approach:

1. Destroy: Randomly select a subset of variables or parts of the current solution and reset them (e.g., deleting items from a knapsack).
2. Repair: Formulate a "mini-problem" (subproblem) using the remaining solution as context and use a solver like CP-SAT to find the optimal new values for the destroyed parts.

This allows for a much broader exploration of the search space than traditional local search methods. While CP-SAT uses internal LNS subsolvers (like graph_arc_lns or rins/rens), you can implement your own problem-specific LNS to leverage your knowledge of the problem's structure, which often outperforms the solver's agnostic approach.

8 incomplete subsolvers: [feasibility_pump, graph_arc_lns, graph_cst_lns, graph_dec_lns, graph_var_lns, rins/rens, rnd_cst_lns, rnd_var_lns]

In models with a massive number of potential auxiliary variables (e.g., quadratic combinations of items), creating all variables upfront can lead to excessive memory usage and computational overhead.

Lazy Variable Construction involves creating variables only when they are actually accessed. This is typically implemented by overriding the __getitem__ method in a manager class. When a specific variable is requested, the class checks if it has already been created; if not, it instantiates the cp_model.IntVar and adds the necessary constraints to the model before returning it.

When to use:

• When the number of possible variables is large (e.g., quadratic in the number of items) but only a small subset is expected to be relevant to the constraints.
• To reduce the initial memory footprint of the model.

class _CombiVariables:
    def __init__(
        self,
        instance: KnapsackInstance,
        model: cp_model.CpModel,
        item_vars: _ItemSelectionVars,
    ):
        self.instance = instance
        self.model = model
        self.item_vars = item_vars
        self.bonus_vars = {}

    def __getitem__(self, item_pair: Tuple[int, int]) -> cp_model.IntVar:
        i, j = sorted(item_pair)
        if (i, j) not in self.bonus_vars:
            var = self.model.NewBoolVar(f"bonus_{i}_{j}")
            # Add constraint: var is true only if both items are packed
            self.model.add(
                self.item_vars.packs_item(i) + self.item_vars.packs_item(j) >= 2 * var
            )
            self.bonus_vars[(i, j)] = var
        return self.bonus_vars[(i, j)]