OR-Tools

The CP-SAT solver is a state-of-the-art constraint programming solver for Constraint Satisfaction Problems (CSPs) and Constraint Optimization Problems (COPs). It combines SAT and CP techniques to handle problems with arbitrary constraints over integer and Boolean variables.

• Core Mechanism: Uses propagation and search with advanced techniques like lazy clause generation.
• Typical Use Cases: Scheduling, rostering, packing, and configuration problems where constraints are complex and logical.
• Key Feature: Can find proven optimal solutions and provides infeasibility explanations.

Provides interfaces to powerful Linear Programming (LP) and Mixed-Integer Programming (MIP) solvers for problems with linear constraints and a linear objective function.

• Primary Solver: Includes a wrapper for Google's GLOP (open-source LP solver) and supports commercial solvers like CPLEX and Gurobi.
• MIP Solver: The SCIP wrapper allows solving problems where some variables must be integers.
• Typical Use Cases: Resource allocation, network flows, production planning, and budget optimization.
• Key Feature: Solves to provable optimality using algorithms like the simplex method and branch and bound.

A specialized, high-level library for solving classic and rich Vehicle Routing Problems (VRPs). It abstracts the complex underlying constraint and optimization models.

• Constraints Handled: Vehicle capacity, time windows, pickups & deliveries, driver breaks, and fleet compatibility.
• Algorithmic Core: Uses a hybrid approach combining local search (e.g., guided local search, simulated annealing) with constraint programming.
• Key Feature: Includes time-dimension callbacks for managing cumulative quantities like travel time and load over a route.

Provides efficient, specialized algorithms for classic graph-based optimization problems that are often sub-problems in larger systems.

• Linear Sum Assignment: Solves the "best matching" problem (e.g., tasks to workers) using the Hungarian algorithm.
• Max Flow / Min Cost Flow: Solves network flow problems for optimal resource distribution through a graph.
• Typical Use Cases: Job assignment, transportation networks, and bipartite matching.
• Key Feature: These are polynomial-time algorithms, offering extremely fast solutions for their problem classes.

Includes solvers for classic NP-hard combinatorial problems involving the optimal packing or selection of items.

• Bin Packing: Minimizes the number of bins (of fixed capacity) needed to pack a set of items.
• Multiple Knapsack: Maximizes the total value of items placed into multiple knapsacks with capacity limits.
• Algorithmic Approach: Often uses branch and bound and dynamic programming-based algorithms.
• Typical Use Cases: Container loading, resource allocation with discrete units, and capital budgeting.

OR-Tools emphasizes separation of modeling and solving. It provides a unified modeling API across solver types and supports multiple programming languages.

• Modeling API: Define variables, constraints, and objectives in a solver-agnostic way using its CP-SAT, Linear Solver, or Routing modeling layers.
• Language Support: Primary APIs in C++, Python, Java, and .NET (C#).
• Key Feature: The same model can often be passed to different solver backends for performance comparison. This architecture allows for rapid prototyping and production deployment from the same codebase.

Constraint Programming is a paradigm for solving combinatorial problems by stating constraints (logical relations) between variables and using inference and search to find solutions. OR-Tools includes a high-performance CP-SAT solver.

• Core Idea: Model the problem as a set of variables, domains, and constraints. The solver performs constraint propagation to prune impossible values and uses search (like backtracking) to explore possibilities.
• Use Cases: Scheduling, rostering, configuration, and puzzles (e.g., N-Queens).
• Key Feature: Excellent for problems with complex, non-linear constraints that are difficult to express in purely linear models.

Mixed-Integer Programming is a mathematical optimization technique where some decision variables are constrained to be integers. OR-Tools provides wrappers to powerful MIP solvers like SCIP and CBC, and its CP-SAT solver also handles integer constraints.

• Core Idea: Problems are modeled with a linear objective function and linear constraints. The 'integer' requirement makes problems discrete and NP-hard.
• Use Cases: Resource allocation, facility location, network design, and portfolio optimization.
• Comparison to CP: MIP excels when the core model is linear and the objective is paramount; CP is often better for highly constrained feasibility problems with complex logic.

The Vehicle Routing Problem is a classic combinatorial optimization challenge of finding optimal routes for a fleet of vehicles to serve a set of customers. OR-Tools has a dedicated, highly optimized VRP library.

• Core Constraints: Typically include vehicle capacity, time windows for deliveries, and total route duration/distance limits.
• Extensions: OR-Tools handles rich variants like VRP with Pickups and Deliveries (VRPPD), VRP with Resource Constraints, and VRP with Drop Penalties.
• Algorithm: Uses a hybrid of constraint programming and local search (e.g., guided local search, tabu search) to find high-quality solutions for large-scale problems.