OR-Tools

A specialized engine for solving Vehicle Routing Problems (VRP) and their variants. It uses constraint programming and local search metaheuristics to find near-optimal routes for fleets.

• Core Models: Supports CVRP, VRPTW, PDP, and DARP out of the box.
• Strategy: Implements Guided Local Search and Tabu Search to escape local minima.
• Customization: Allows defining custom distance and demand callbacks for complex constraints.

A Constraint Programming solver based on SAT (Boolean satisfiability) techniques. It excels at finding feasible solutions for highly constrained combinatorial problems where the search space is vast.

• Paradigm: Declarative modeling—you define variables, domains, and constraints; the solver handles the search.
• Strengths: Scheduling, resource allocation, and complex logical constraints.
• Engine: Uses lazy clause generation, combining SAT solving with finite domain propagation.

A unified interface for Mixed-Integer Linear Programming (MILP) and linear programming. It acts as an abstraction layer over multiple solvers, both open-source and commercial.

• Backends: Supports Gurobi, CPLEX, and Google's own GLOP and PDLP solvers.
• Modeling: Write a model once and switch solvers without changing the code.
• Use Case: Ideal for problems with linear objectives and constraints, like network flow and production planning.

A library of highly optimized algorithms for problems modeled as graphs. This is the computational backbone for many routing and assignment tasks.

• Algorithms: Includes Dijkstra's, A*, and specialized solvers for Minimum Cost Flow and Maximum Flow.
• Assignment: Solves linear sum assignment problems (minimum weight perfect matching in bipartite graphs) efficiently.
• Integration: Often used as a subroutine within larger VRP or scheduling models to compute distance matrices.

Google's in-house linear programming solver, optimized for pure continuous linear problems. It implements a revised simplex algorithm.

• Performance: Designed for high-speed execution on large-scale, sparse linear programs.
• Role: Serves as the default LP solver within the MathOpt interface and is used internally by CP-SAT for linear relaxations.
• Limitation: Solves only continuous linear problems; does not handle integer variables directly.

A first-order method solver for large-scale linear and convex quadratic programming. It is designed to exploit GPU and TPU hardware acceleration.

• Algorithm: Uses a primal-dual hybrid gradient method, fundamentally different from simplex or interior-point methods.
• Scale: Targets problems with billions of variables and constraints that are intractable for traditional solvers.
• Hardware: Achieves significant speedups by parallelizing operations on accelerator hardware.

The canonical combinatorial optimization challenge that OR-Tools is designed to solve. VRP seeks the optimal set of routes for a fleet of vehicles to service a geographically dispersed set of customers.

• Objective: Minimize total cost (distance, time, or vehicles used)
• Constraints: Vehicle capacity, time windows, route duration limits
• Scale: Real-world instances often involve thousands of nodes

OR-Tools provides dedicated VRP solvers that use local search and metaheuristics to find near-optimal solutions in seconds.

A declarative paradigm where you define variables, their domains, and the constraints between them, then let a solver find feasible or optimal assignments. OR-Tools includes a powerful CP-SAT solver.

• Excels at feasibility problems with complex logical constraints
• Uses propagation to prune the search space before branching
• Ideal for scheduling, rostering, and bin-packing problems

CP complements MILP by handling non-linear constraints more naturally.

An optimization model with a linear objective and linear constraints where some variables must take integer values. OR-Tools integrates with both its own GLOP solver and external solvers like Gurobi and SCIP.

• Solved via Branch and Bound and cutting-plane methods
• Handles discrete decisions: facility location, vehicle assignment
• The MPSolver wrapper in OR-Tools provides a unified API across backends

MILP guarantees global optimality but can be computationally expensive at scale.

A metaheuristic framework that iteratively destroys and repairs parts of a solution to escape local optima. OR-Tools uses ALNS as a core strategy within its routing library.

• Destroy operators: Remove a subset of visits (random, worst-cost, related)
• Repair operators: Reinsert removed visits using greedy or regret-based heuristics
• Adaptive layer: Tracks operator performance and selects the most effective ones dynamically

ALNS is particularly effective for large-scale VRPs with tight time windows.

A state-of-the-art commercial mathematical optimization solver for LP, MILP, and QP problems. OR-Tools can use Gurobi as a backend via its MPSolver interface.

• Consistently ranks among the fastest solvers on MIPLIB benchmarks
• Offers distributed and cloud-based solving for massive instances
• Provides fine-grained control over cut generation and heuristics

When OR-Tools' built-in solvers hit complexity limits, Gurobi is a common enterprise upgrade path.

An algorithm for solving large-scale linear programs where the number of variables is too large to enumerate explicitly. It is foundational to many advanced VRP solvers.

• Restricted Master Problem: Solves with a subset of columns (e.g., feasible routes)
• Pricing Subproblem: Generates new columns with negative reduced cost
• Iterates until no improving columns exist

OR-Tools does not implement column generation natively, but it is a common extension pattern for custom VRP variants.