Getting Started with Google OR-Tools: A Practical Guide for Beginners

Comparing OR-Tools Solvers: CP-SAT vs. Linear vs. RoutingOR-Tools is Google’s open-source operations research suite that provides several high-performance solvers for different classes of optimization problems. This article compares three commonly used components: CP-SAT, Linear (MIP/LP), and Routing, explaining their strengths, typical use cases, modeling approaches, and practical tips for choosing between them.

Overview: the three solvers

• CP-SAT (Constraint Programming — SAT-based): a general-purpose, boolean/sat-driven constraint solver with excellent performance on combinatorial optimization problems. It supports integer and boolean variables, linear constraints, logical constraints, table constraints, scheduling primitives, and objective optimization (maximize/minimize). CP-SAT is the recommended solver in OR-Tools for many mixed integer and combinatorial problems due to its robustness and built-in strategies (search heuristics, restarts, and advanced presolve).

• Linear (LP/MIP): OR-Tools includes linear programming (LP) and mixed-integer programming (MIP) interfaces. These solvers are best for problems expressible with linear objective and linear constraints (continuous or integer variables). Linear solvers excel when problems have large-scale continuous structure or when you rely on strong LP relaxations and branch-and-bound techniques. OR-Tools can use internal solvers and integrate with external MIP solvers (CBC, SCIP, commercial solvers) for better performance on some classes of MIP problems.

• Routing: a specialized solver built on top of CP-SAT geared toward vehicle routing problems (VRP) and related variants (traveling salesman problem, pickup-and-delivery, CVRP, time windows, capacity constraints, route costs, etc.). It provides high-level modeling constructs (vehicles, nodes, vehicles’ capacities, cost callbacks, time/distance matrices) and fast meta-heuristics tuned for routing use cases.

Problem types and where each shines

• CP-SAT

  • Best for: scheduling, resource allocation, complex combinatorial constraints, assignment problems, problems combining logical constraints with arithmetic, cutting and packing (small-to-medium), timetabling.
  • Strengths: supports rich constraint types (reified constraints, boolean combinations), handles integer variables very well, strong default heuristics, good for problems without neat linear relaxations.
  • Limitations: performance may degrade on very large-scale linear-dominant MIP problems compared to specialized MIP solvers.

• Linear (LP/MIP)

  • Best for: large-scale linear optimization, problems where LP relaxation gives tight bounds, network flows, production planning, inventory, portfolio optimization.
  • Strengths: mature algorithms (simplex, interior point, branch-and-bound), strong performance on continuous or large sparse integer programs, well-understood duality and sensitivity analysis.
  • Limitations: harder to express complex logical constraints naturally; can require big-M or additional variables for logical constructs, which may weaken relaxations.

• Routing

  • Best for: vehicle routing, TSP, VRP with many realistic constraints (time windows, capacities, pickups/deliveries), route optimization at scale.
  • Strengths: high-level API tailored to routing, built-in local search metaheuristics, specialized move operators, efficient for large node counts, integrates with CP-SAT for improved finding of feasible solutions.
  • Limitations: specialized to routing—less flexible for non-routing combinatorial problems.

Modeling approaches and API differences

• CP-SAT

  • Modeling style: define IntVar/BoolVar variables, add linear and logical constraints, add objective(s). Many constraints are expressible directly (element, circuit, table). Uses CpModel in Python/C++/Java.
  • Solving: model → CpSolver → specify time limit, search parameters, solution callbacks.
  • Example features: AddAllowedAssignments (table constraints), AddCircuit, AddAbsEquality, AddBoolOr/And, AddMultiplicationEquality (with caveats).

• Linear (LP/MIP)

  • Modeling style: define variables continuous or integer, add linear constraints/linear objective. Use MPS/LP formats or solver-specific model builders in OR-Tools.
  • Solving: create linear solver instance (CBC, SCIP, GLPK, commercial), set parameters, solve; can extract basis info with some solvers.
  • Example features: direct access to continuous relaxation, advanced presolve and cut generation via backend solver.

• Routing

  • Modeling style: define RoutingIndexManager (maps nodes/vehicles), build RoutingModel, register callbacks (distance/time/cost), add dimension(s) for time/capacity, set search parameters and first solution strategies/local search metaheuristics.
  • Solving: RoutingModel uses specialized solvers and local search operators; can use CP-SAT for final improvement in recent versions.
  • Example features: AddDimension for time windows, AddDimensionWithVehicleCapacity, TransitCallbacks, vehicle costs, disjunctions (optional visits).

Performance characteristics and scaling

• CP-SAT

  • Good multi-core utilization and modern SAT-based search; often finds high-quality feasible solutions quickly.
  • Performance sensitive to variable domain sizes and large dense linear constraints; modeling choices (symmetry breaking, bounds tightening, avoiding large Big-Ms) matter a lot.
  • Use warm starts via hinting when you have good initial solutions.

• Linear (LP/MIP)

  • Scales well for very large sparse problems with powerful commercial solvers (Gurobi, CPLEX) offering best throughput.
  • Quality depends on LP relaxation tightness; adding cutting planes, valid inequalities, or better formulations helps.
  • Deterministic behavior often preferred in production pipelines.

• Routing

  • Highly optimized for problems with thousands of nodes and many vehicles using heuristics and metaheuristics.
  • Fast at producing good feasible tours; optimality proofs are often infeasible for large VRPs but heuristics give usable solutions.
  • Tuning first solution strategy and local search parameters can significantly change result quality and runtime.

When to mix solvers

• Use CP-SAT for the combinatorial core, and LP/MIP for continuous subproblems — solve subproblems with appropriate solver and feed results via callbacks or a decomposed approach.
• Use Routing for route structure and CP-SAT/MIP for complex side constraints (e.g., nonlinear cost computations) by iterating between solvers.
• Example: solve assignment and time scheduling with CP-SAT, then solve detailed vehicle-loading (linear knapsack) with MIP and iterate.

Practical tips and best practices

• Choose the solver matching the problem structure: combinatorial → CP-SAT; linear-dominant → MIP; routing → Routing.
• Tighten variable domains and add redundant but strengthening constraints.
• Avoid large Big-M constants; prefer logical constraints or indicator constraints when available.
• Use symmetry-breaking constraints to reduce search space.
• Start with short time limits to get feasible solutions quickly, then increase limits for improvement.
• Profile model size (#vars, #constraints) and experiment with solver parameters (num_search_workers, cp-sat specific heuristics, MIP cuts).
• For routing, precompute distance/time matrices and use appropriate first-solution strategies (e.g., PATH_CHEAPEST_ARC or PARALLEL_CHEAPEST_INSERTION).

Example snippets (conceptual)

CP-SAT (Python, conceptual)

from ortools.sat.python import cp_model model = cp_model.CpModel() x = model.NewIntVar(0, 10, 'x') y = model.NewIntVar(0, 10, 'y') model.Add(x + 2*y <= 14) model.Maximize(3*x + 4*y) solver = cp_model.CpSolver() solver.parameters.max_time_in_seconds = 10 solver.Solve(model) 

MIP (Python, conceptual)

from ortools.linear_solver import pywraplp solver = pywraplp.Solver.CreateSolver('CBC') x = solver.IntVar(0, 10, 'x') y = solver.IntVar(0, 10, 'y') solver.Add(x + 2*y <= 14) solver.Maximize(3*x + 4*y) solver.Solve() 

Routing (Python, conceptual)

from ortools.constraint_solver import pywrapcp, routing_enums_pb2 manager = pywrapcp.RoutingIndexManager(num_nodes, num_vehicles, depot) routing = pywrapcp.RoutingModel(manager) def dist_callback(from_index, to_index):     return distance_matrix[manager.IndexToNode(from_index)][manager.IndexToNode(to_index)] transit_cb_idx = routing.RegisterTransitCallback(dist_callback) routing.SetArcCostEvaluatorOfAllVehicles(transit_cb_idx) search_params = pywrapcp.DefaultRoutingSearchParameters() search_params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC routing.SolveWithParameters(search_params) 

Quick decision guide

• If your problem is vehicle routing or TSP-like: use Routing.
• If your problem has many logical constraints, scheduling, or combinatorial structure: use CP-SAT.
• If your problem is large-scale linear/integer programming with strong LP relaxation: use Linear (MIP/LP) or a commercial MIP solver.

Conclusion

Each OR-Tools solver has a sweet spot: CP-SAT for general combinatorial and scheduling tasks, Linear/MIP for large-scale linear optimization, and Routing for specialized vehicle-routing problems. Choosing the right solver — and modeling accordingly — typically matters more than micro-optimizing solver parameters.