# OR-Tools - Google Optimization Tools

OR-Tools is Google's open-source software suite for solving combinatorial optimization problems. It provides fast, portable solvers for constraint programming, linear programming, mixed-integer programming, routing problems, and graph algorithms. The library is written in C++ with complete wrappers for Python, C#, Java, and .NET, making it accessible across multiple programming environments.

The suite includes multiple specialized solvers: CP-SAT for constraint programming with SAT-based solving, Glop and PDLP for linear programming, specialized routing solvers for Vehicle Routing Problems (VRP), and efficient graph algorithms for network flow and assignment problems. It also provides wrappers around commercial solvers like Gurobi and XPRESS. OR-Tools excels at solving practical optimization problems including scheduling, resource allocation, vehicle routing, bin packing, and network optimization.

## CP-SAT Constraint Programming Solver

The CP-SAT solver is the primary constraint programming interface for solving combinatorial optimization problems with variables, constraints, and objectives.

```python
from ortools.sat.python import cp_model

# Create model and variables
model = cp_model.CpModel()
var_upper_bound = max(50, 45, 37)
x = model.new_int_var(0, var_upper_bound, "x")
y = model.new_int_var(0, var_upper_bound, "y")
z = model.new_int_var(0, var_upper_bound, "z")

# Add constraints
model.add(2 * x + 7 * y + 3 * z <= 50)
model.add(3 * x - 5 * y + 7 * z <= 45)
model.add(5 * x + 2 * y - 6 * z <= 37)

# Set objective
model.maximize(2 * x + 2 * y + 3 * z)

# Solve
solver = cp_model.CpSolver()
status = solver.solve(model)

# Extract solution
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f"Maximum of objective function: {solver.objective_value}")
    print(f"x = {solver.value(x)}")
    print(f"y = {solver.value(y)}")
    print(f"z = {solver.value(z)}")
    print(f"Status: {solver.status_name(status)}")
    print(f"Conflicts: {solver.num_conflicts}")
    print(f"Branches: {solver.num_branches}")
    print(f"Wall time: {solver.wall_time} s")
else:
    print("No solution found.")
```

## Traveling Salesman Problem with CP-SAT

Solving TSP using circuit constraints to find the minimum distance tour visiting all cities exactly once.

```python
from ortools.sat.python import cp_model

# Distance matrix between cities
DISTANCE_MATRIX = [
    [0, 10938, 4542, 2835],
    [10938, 0, 6422, 9742],
    [4542, 6422, 0, 3644],
    [2835, 9742, 3644, 0]
]

num_nodes = len(DISTANCE_MATRIX)
all_nodes = range(num_nodes)

# Create model
model = cp_model.CpModel()

# Create circuit constraint arcs
obj_vars = []
obj_coeffs = []
arcs = []
arc_literals = {}

for i in all_nodes:
    for j in all_nodes:
        if i == j:
            continue

        # Boolean variable: does city j follow city i?
        lit = model.new_bool_var(f"{j} follows {i}")
        arcs.append((i, j, lit))
        arc_literals[i, j] = lit

        obj_vars.append(lit)
        obj_coeffs.append(DISTANCE_MATRIX[i][j])

# Add circuit constraint (ensures valid tour)
model.add_circuit(arcs)

# Minimize total distance
model.minimize(sum(obj_vars[i] * obj_coeffs[i] for i in range(len(obj_vars))))

# Solve with linearization for circuit
solver = cp_model.CpSolver()
solver.parameters.log_search_progress = True
solver.parameters.linearization_level = 2
status = solver.solve(model)

# Extract route
current_node = 0
str_route = f"{current_node}"
route_distance = 0
route_is_finished = False

while not route_is_finished:
    for i in all_nodes:
        if i == current_node:
            continue
        if solver.boolean_value(arc_literals[current_node, i]):
            str_route += f" -> {i}"
            route_distance += DISTANCE_MATRIX[current_node][i]
            current_node = i
            if current_node == 0:
                route_is_finished = True
            break

print(f"Route: {str_route}")
print(f"Travelled distance: {route_distance}")
```

## Assignment Problem with Group Constraints

Solving worker-to-task assignment with combination constraints and capacity limits using CP-SAT.

```python
from ortools.sat.python import cp_model

# Cost matrix: cost[worker][task]
cost = [
    [90, 76, 75, 70, 50, 74],
    [35, 85, 55, 65, 48, 101],
    [125, 95, 90, 105, 59, 120],
    [45, 110, 95, 115, 104, 83],
    [60, 105, 80, 75, 59, 62],
    [45, 65, 110, 95, 47, 31],
    [38, 51, 107, 41, 69, 99],
    [47, 85, 57, 71, 92, 77],
    [39, 63, 97, 49, 118, 56],
    [47, 101, 71, 60, 88, 109],
    [17, 39, 103, 64, 61, 92],
    [101, 45, 83, 59, 92, 27],
]

# Valid worker combinations for group 1 (workers 0-3)
group1 = [
    [0, 0, 1, 1],  # Workers 2, 3
    [0, 1, 0, 1],  # Workers 1, 3
    [0, 1, 1, 0],  # Workers 1, 2
    [1, 1, 0, 0],  # Workers 0, 1
    [1, 0, 1, 0],  # Workers 0, 2
]

# Task sizes and capacity limit
sizes = [10, 7, 3, 12, 15, 4, 11, 5]
total_size_max = 15

num_workers = len(cost)
num_tasks = len(cost[0])
all_workers = range(num_workers)
all_tasks = range(num_tasks)

# Create model
model = cp_model.CpModel()

# Variables: selected[i][j] = 1 if worker i does task j
selected = [
    [model.new_bool_var(f"x[{i},{j}]") for j in all_tasks]
    for i in all_workers
]

# works[i] = 1 if worker i is assigned any task
works = [model.new_bool_var(f"works[{i}]") for i in all_workers]

# Link selected and works variables
for i in range(num_workers):
    model.add_max_equality(works[i], selected[i])

# Each task assigned to at least one worker
for j in all_tasks:
    model.add(sum(selected[i][j] for i in all_workers) >= 1)

# Capacity constraint per worker
for i in all_workers:
    model.add(sum(sizes[j] * selected[i][j] for j in all_tasks) <= total_size_max)

# Group constraints: only allowed combinations of workers
model.add_allowed_assignments([works[0], works[1], works[2], works[3]], group1)

# Minimize total cost
model.minimize(
    sum(selected[i][j] * cost[i][j] for j in all_tasks for i in all_workers)
)

# Solve
solver = cp_model.CpSolver()
status = solver.solve(model)

if status == cp_model.OPTIMAL:
    print(f"Total cost = {solver.objective_value}")
    for i in all_workers:
        for j in all_tasks:
            if solver.boolean_value(selected[i][j]):
                print(f"Worker {i} assigned to task {j} with Cost = {cost[i][j]}")
    print(solver.response_stats())
```

## Linear Programming with Multiple Solvers

Solving LP problems using the natural language API with support for multiple backends (GLOP, CLP, GLPK, PDLP).

```python
from ortools.linear_solver import pywraplp

# Create solver (GLOP, GLPK_LP, CLP, PDLP, XPRESS_LP)
solver = pywraplp.Solver.CreateSolver('GLOP')

if not solver:
    print("Solver not available")
    exit(1)

infinity = solver.infinity()

# Create continuous variables x1, x2, x3 >= 0
x1 = solver.NumVar(0.0, infinity, "x1")
x2 = solver.NumVar(0.0, infinity, "x2")
x3 = solver.NumVar(0.0, infinity, "x3")

# Set objective: maximize 10*x1 + 6*x2 + 4*x3
solver.Maximize(10 * x1 + 6 * x2 + 4 * x3)

# Add constraints
c0 = solver.Add(10 * x1 + 4 * x2 + 5 * x3 <= 600, "ConstraintName0")
c1 = solver.Add(2 * x1 + 2 * x2 + 6 * x3 <= 300)
sum_of_vars = sum([x1, x2, x3])
c2 = solver.Add(sum_of_vars <= 100.0, "OtherConstraintName")

print(f"Number of variables = {solver.NumVariables()}")
print(f"Number of constraints = {solver.NumConstraints()}")

# Solve
result_status = solver.Solve()

# Check solution
if result_status == pywraplp.Solver.OPTIMAL:
    assert solver.VerifySolution(1e-7, True)
    print(f"Problem solved in {solver.wall_time()} milliseconds")
    print(f"Optimal objective value = {solver.Objective().Value()}")

    # Variable values
    print(f"x1 = {x1.solution_value()}")
    print(f"x2 = {x2.solution_value()}")
    print(f"x3 = {x3.solution_value()}")

    # Linear expression value
    print(f"Sum of vars: {sum_of_vars} = {sum_of_vars.solution_value()}")

    # Advanced: reduced costs and dual values
    print(f"Problem solved in {solver.iterations()} iterations")
    print(f"x1: reduced cost = {x1.reduced_cost()}")
    print(f"x2: reduced cost = {x2.reduced_cost()}")
    print(f"x3: reduced cost = {x3.reduced_cost()}")

    activities = solver.ComputeConstraintActivities()
    for constraint in [c0, c1, c2]:
        print(f"constraint: dual value = {constraint.dual_value()}")
        print(f"           activity = {activities[constraint.index()]}")
else:
    print("The problem does not have an optimal solution.")
```

## Vehicle Routing Problem with Prize Collecting

Solving prize-collecting VRP where vehicles can skip optional nodes to stay within distance limits while maximizing value collected.

```python
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

# Distance matrix between locations
DISTANCE_MATRIX = [
    [0, 10938, 4542, 2835],
    [10938, 0, 6422, 9742],
    [4542, 6422, 0, 3644],
    [2835, 9742, 3644, 0]
]

MAX_DISTANCE = 80_000
VISIT_VALUES = [0, 60_000, 50_000, 40_000]  # Value for visiting each node

num_nodes = len(DISTANCE_MATRIX)
num_vehicles = 4
depot = 0

# Create routing index manager
manager = pywrapcp.RoutingIndexManager(num_nodes, num_vehicles, depot)

# Create routing model
routing = pywrapcp.RoutingModel(manager)

# Distance callback
def distance_callback(from_index, to_index):
    """Returns the distance between the two nodes."""
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return DISTANCE_MATRIX[from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(distance_callback)

# Set arc cost for all vehicles
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

# Add distance dimension with maximum limit
dimension_name = 'Distance'
routing.AddDimension(
    transit_callback_index,
    0,  # no slack
    MAX_DISTANCE,  # vehicle maximum travel distance
    True,  # start cumul to zero
    dimension_name
)

distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(1)

# Allow dropping nodes with penalty (prize collecting)
for node in range(1, num_nodes):
    routing.AddDisjunction(
        [manager.NodeToIndex(node)],
        VISIT_VALUES[node]  # Penalty for not visiting = lost value
    )

# Set solution strategy
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
)
search_parameters.local_search_metaheuristic = (
    routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
)
search_parameters.time_limit.FromSeconds(15)

# Solve
assignment = routing.SolveWithParameters(search_parameters)

# Print solution
if assignment:
    print(f'Objective: {assignment.ObjectiveValue()}')

    # Display dropped nodes
    dropped_nodes = 'Dropped nodes:'
    for index in range(routing.Size()):
        if routing.IsStart(index) or routing.IsEnd(index):
            continue
        if assignment.Value(routing.NextVar(index)) == index:
            node = manager.IndexToNode(index)
            dropped_nodes += f' {node}({VISIT_VALUES[node]})'
    print(dropped_nodes)

    # Display routes
    total_distance = 0
    total_value = 0
    for v in range(manager.GetNumberOfVehicles()):
        index = routing.Start(v)
        plan_output = f'Route for vehicle {v}:\n'
        route_distance = 0
        value_collected = 0

        while not routing.IsEnd(index):
            node = manager.IndexToNode(index)
            value_collected += VISIT_VALUES[node]
            plan_output += f' {node} ->'
            previous_index = index
            index = assignment.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(previous_index, index, v)

        plan_output += f' {manager.IndexToNode(index)}\n'
        plan_output += f'Distance: {route_distance}m\n'
        plan_output += f'Value collected: {value_collected}\n'
        print(plan_output)

        total_distance += route_distance
        total_value += value_collected

    print(f'Total Distance: {total_distance}m')
    print(f'Total Value: {total_value}/{sum(VISIT_VALUES)}')
```

## Maximum Flow in Networks

Finding maximum flow from source to sink in a network using the SimpleMaxFlow graph algorithm.

```python
import numpy as np
from ortools.graph.python import max_flow

# Create solver
smf = max_flow.SimpleMaxFlow()

# Define network: parallel arrays for arcs
start_nodes = np.array([0, 0, 0, 1, 1, 2, 2, 3, 3])
end_nodes = np.array([1, 2, 3, 2, 4, 3, 4, 2, 4])
capacities = np.array([20, 30, 10, 40, 30, 10, 20, 5, 20])

# Add all arcs to the graph
all_arcs = smf.add_arcs_with_capacity(start_nodes, end_nodes, capacities)

# Find maximum flow from node 0 to node 4
status = smf.solve(0, 4)

if status != smf.OPTIMAL:
    print("There was an issue with the max flow input.")
    print(f"Status: {status}")
    exit(1)

print(f"Max flow: {smf.optimal_flow()}")
print("")
print(" Arc    Flow / Capacity")

solution_flows = smf.flows(all_arcs)
for arc, flow, capacity in zip(all_arcs, solution_flows, capacities):
    print(f"{smf.tail(arc)} -> {smf.head(arc)}   {flow:3}  / {capacity:3}")

# Get min-cut partitions
print(f"Source side min-cut: {smf.get_source_side_min_cut()}")
print(f"Sink side min-cut: {smf.get_sink_side_min_cut()}")
```

## Minimum Cost Flow for Network Optimization

Solving min-cost flow problems with supplies, demands, capacities, and unit costs on arcs.

```python
import numpy as np
from ortools.graph.python import min_cost_flow

# Create solver
smcf = min_cost_flow.SimpleMinCostFlow()

# Define network arcs with capacities and costs
start_nodes = np.array([0, 0, 1, 1, 1, 2, 2, 3, 4])
end_nodes = np.array([1, 2, 2, 3, 4, 3, 4, 4, 2])
capacities = np.array([15, 8, 20, 4, 10, 15, 4, 20, 5])
unit_costs = np.array([4, 4, 2, 2, 6, 1, 3, 2, 3])

# Define supplies (positive) and demands (negative) at each node
supplies = [20, 0, 0, -5, -15]

# Add arcs with capacity and unit cost
all_arcs = smcf.add_arcs_with_capacity_and_unit_cost(
    start_nodes, end_nodes, capacities, unit_costs
)

# Set node supplies/demands
smcf.set_nodes_supplies(np.arange(0, len(supplies)), supplies)

# Solve for minimum cost flow
status = smcf.solve()

if status != smcf.OPTIMAL:
    print("There was an issue with the min cost flow input.")
    print(f"Status: {status}")
    exit(1)

print(f"Minimum cost: {smcf.optimal_cost()}")
print("")
print(" Arc    Flow / Capacity  Cost")

solution_flows = smcf.flows(all_arcs)
costs = solution_flows * unit_costs

for arc, flow, cost in zip(all_arcs, solution_flows, costs):
    print(
        f"{smcf.tail(arc):1} -> {smcf.head(arc)}  "
        f"{flow:3}  / {smcf.capacity(arc):3}       {cost}"
    )
```

## Summary

OR-Tools provides production-grade optimization solvers for diverse problem classes. The CP-SAT solver excels at scheduling, assignment, and combinatorial problems with complex constraints. Linear solvers handle continuous optimization with multiple backend options. The specialized routing solver efficiently handles vehicle routing variants including time windows, capacity constraints, pickup-delivery, and prize collecting. Graph algorithms provide optimized implementations for network flow and assignment problems.

Integration is straightforward through pip installation (`pip install ortools`) with zero external dependencies for core functionality. The library supports multiple modeling styles from natural language APIs to explicit constraint formulation. Solutions include detailed statistics, dual values, and debugging information. OR-Tools scales from small prototypes to large-scale industrial applications, with parallel solving, time limits, solution callbacks, and warm-start capabilities. The extensive example library covers 50+ problem types including TSP, job shop scheduling, bin packing, sudoku, N-queens, knapsack variants, and complex real-world logistics scenarios.