ortools

# Google OR-Tools - Combinatorial Optimization OR-Tools provides specialized solvers for hard combinatorial problems. Its crown jewel is the CP-SAT solver, which uses Constraint Programming and Satisfiability techniques to find optimal solutions for scheduling and resource allocation problems that are impossible for standard linear solvers. ## When to Use - **Vehicle Routing (VRP)**: Finding the best paths for a fleet of vehicles to deliver goods. - **Scheduling**: Creating shift rosters, project timelines, or job-shop schedules. - **Bin Packing**: Fitting objects of different sizes into a finite number of bins. - **Knapsack Problem**: Selecting items to maximize value within a weight limit. - **Linear Programming (LP)**: Standard resource allocation with continuous variables. - **Integer Programming (MIP)**: Optimization where variables must be whole numbers (e.g., "number of machines to buy"). - **Network Flows**: Calculating max flow or min cost in a graph. ## Reference Documentation **Official docs**: https://developers.google.com/optimization **GitHub**: https://github.com/google/or-tools **Search patterns**: `cp_model.CpModel`, `pywraplp.Solver`, `routing_enums_pb2`, `AddConstraint` ## Core Principles ### Modeling vs. Solving OR-Tools separates the **Definition** of the problem (Variables, Constraints, Objective) from the **Solver** engine. You build a model, then pass it to a solver instance. ### CP-SAT (Constraint Programming) The most modern and recommended solver for discrete problems. **Critical Note**: CP-SAT works with integers only. If you have floating-point numbers (like `0.5`), you must scale them (e.g., multiply by 100 and work with integers). ### Status Codes After solving, always check the status. It can be `OPTIMAL`, `FEASIBLE` (a solution found, but maybe not the best), `INFEASIBLE` (impossible to solve), or `LIMIT_REACHED`. ## Quick Reference ### Installation ```bash pip install ortools ``` ### Standard Imports ```python from ortools.sat.python import cp_model from ortools.linear_solver import pywraplp from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp ``` ### Basic Pattern - CP-SAT Solver (Integer Logic) ```python from ortools.sat.python import cp_model # 1. Create the model model = cp_model.CpModel() # 2. Define variables: NewIntVar(lower_bound, upper_bound, name) x = model.NewIntVar(0, 10, 'x') y = model.NewIntVar(0, 10, 'y') # 3. Add constraints model.Add(x + y <= 8) model.Add(x > 2) # 4. Define Objective model.Maximize(x + 2 * y) # 5. Solve solver = cp_model.CpSolver() status = solver.Solve(model) if status == cp_model.OPTIMAL: print(f'x = {solver.Value(x)}, y = {solver.Value(y)}') ``` ## Critical Rules ### ✅ DO - **Use CP-SAT for Discrete Tasks** - It is significantly faster than MIP solvers for scheduling and logic-heavy problems. - **Scale your Floats** - Since CP-SAT is an integer solver, convert `1.25` to `125` and adjust the logic. - **Check Status First** - Never access variable values if the status is `INFEASIBLE`. - **Use AddElement for indexing** - To use a variable as an index in an array, use the specialized constraint `model.AddElement`. - **Set a Time Limit** - For complex problems, use `solver.parameters.max_time_in_seconds = 60.0` to get the best possible solution within a minute. - **Verify with Value()** - Access results using `solver.Value(var)`, not the variable object itself. ### ❌ DON'T - **Don't use Python if in Constraints** - You cannot use `if x > 5: model.Add(...)`. Use boolean implications (`OnlyEnforceIf`). - **Don't use non-linear math** - CP-SAT and LP solvers don't support `x * y` (where both are variables) or `sin(x)`. For `x * y`, you need specialized linearization or piecewise approximations. - **Avoid huge domains** - Defining a variable with a range of 0 to 1,000,000,000 can slow down the solver. Narrow the bounds as much as possible. ## Anti-Patterns (NEVER) ```python from ortools.sat.python import cp_model # ❌ BAD: Using standard Python logic inside the model # if solver.Value(x) > 5: # ❌ Value() is not available during modeling! # model.Add(y == 1) # ✅ GOOD: Conditional constraints (Logical Implication) b = model.NewBoolVar('b') model.Add(x > 5).OnlyEnforceIf(b) model.Add(x <= 5).OnlyEnforceIf(b.Not()) model.Add(y == 1).OnlyEnforceIf(b) # ❌ BAD: Floating point variables in CP-SAT # x = model.NewIntVar(0, 1.5, 'x') # ❌ Error! # ✅ GOOD: Scaling # x_scaled = model.NewIntVar(0, 150, 'x_scaled') # 150 represents 1.50 ``` ## Linear Programming (pywraplp) ### Resource Allocation (Continuous Variables) ```python from ortools.linear_solver import pywraplp # Create solver with GLOP backend (Google Linear Optimization Package) solver = pywraplp.Solver.CreateSolver('GLOP') # Define continuous variables x = solver.NumVar(0, solver.infinity(), 'x') y = solver.NumVar(0, solver.infinity(), 'y') # Constraint: x + 2y <= 14 ct = solver.Constraint(-solver.infinity(), 14) ct.SetCoefficient(x, 1) ct.SetCoefficient(y, 2) # Objective: Maximize 3x + 4y objective = solver.Objective() objective.SetCoefficient(x, 3) objective.SetCoefficient(y, 4) objective.SetMaximization() solver.Solve() print(f'Solution: x={x.solution_value()}, y={y.solution_value()}') ``` ## Vehicle Routing (VRP) ### The Logistics Engine ```python from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp def solve_vrp(): # 1. Distance Matrix (distance between locations) data = {'distance_matrix': [[0, 10, 20], [10, 0, 15], [20, 15, 0]], 'num_vehicles': 1, 'depot': 0} # 2. Setup Index Manager and Routing Model manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']), data['num_vehicles'], data['depot']) routing = pywrapcp.RoutingModel(manager) # 3. Create Distance Callback def distance_callback(from_index, to_index): return data['distance_matrix'][manager.IndexToNode(from_index)][manager.IndexToNode(to_index)] transit_callback_index = routing.RegisterTransitCallback(distance_callback) routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # 4. Solve search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) solution = routing.SolveWithParameters(search_parameters) return solution ``` ## Constraint Programming: Scheduling ### Job-Shop Example (Tasks with dependencies) ```python model = cp_model.CpModel() # Define an Interval Variable (Start, Duration, End) duration = 10 start_var = model.NewIntVar(0, 100, 'start') end_var = model.NewIntVar(0, 100, 'end') interval_var = model.NewIntervalVar(start_var, duration, end_var, 'interval') # No-overlap constraint (Machines can only do one task at a time) model.AddNoOverlap([interval_var1, interval_var2, interval_var3]) ``` ## Practical Workflows ### 1. Employee Shift Scheduling ```python def solve_shifts(num_employees, num_days, shifts_per_day): model = cp_model.CpModel() shifts = {} for e in range(num_employees): for d in range(num_days): for s in range(shifts_per_day): shifts[(e, d, s)] = model.NewBoolVar(f'shift_e{e}d{d}s{s}') # Constraint: Each shift is assigned to exactly one employee for d in range(num_days): for s in range(shifts_per_day): model.Add(sum(shifts[(e, d, s)] for e in range(num_employees)) == 1) # Constraint: Each employee works at most one shift per day for e in range(num_employees): for d in range(num_days): model.Add(sum(shifts[(e, d, s)] for s in range(shifts_per_day)) <= 1) solver = cp_model.CpSolver() status = solver.Solve(model) return shifts, solver ``` ### 2. Multi-Knapsack (Packing items into bins) ```python def bin_packing(items, bin_capacities): model = cp_model.CpModel() # x[i, j] = 1 if item i is in bin j x = {} for i in range(len(items)): for j in range(len(bin_capacities)): x[i, j] = model.NewBoolVar(f'x_{i}_{j}') # Each item in exactly one bin for i in range(len(items)): model.Add(sum(x[i, j] for j in range(len(bin_capacities))) == 1) # Bin capacity constraint for j in range(len(bin_capacities)): model.Add(sum(x[i, j] * items[i] for i in range(len(items))) <= bin_capacities[j]) ``` ## Performance Optimization ### Hinting (Warm Start) If you have a good initial guess, provide it to the solver to speed up search. ```python model.AddHint(x, 5) model.AddHint(y, 2) ``` ### Parallel Solving CP-SAT can use multiple threads to explore different parts of the search tree. ```python solver = cp_model.CpSolver() solver.parameters.num_search_workers = 8 # Use 8 CPU cores ``` ## Common Pitfalls and Solutions ### Floating Point Math Errors As mentioned, OR-Tools CP-SAT is strictly integer. ```python # ❌ Problem: model.Add(x * 0.1 <= 5) # ✅ Solution: model.Add(x <= 50) # Multiply both sides by 10 ``` ### Infeasible Models If `solver.Solve(model)` returns `INFEASIBLE`, it means your constraints are contradictory. ```python # ✅ Solution: Use 'Sufficient Assmptions' or 'Constraint Relaxation' # to identify which constraint is causing the conflict. ``` ### Symmetry If items A and B are identical, the solver will waste time checking both "A in Bin 1, B in Bin 2" and "B in Bin 1, A in Bin 2". ```python # ✅ Solution: Add symmetry-breaking constraints # model.Add(x_A <= x_B) # Force an ordering ``` ## Best Practices 1. **Always check solver status** before accessing variable values 2. **Scale floating-point values** to integers when using CP-SAT 3. **Set time limits** for complex problems to get feasible solutions quickly 4. **Use appropriate solver** - CP-SAT for discrete, GLOP for continuous LP 5. **Break symmetry** in models with identical variables to speed up solving 6. **Narrow variable domains** as much as possible for better performance 7. **Use hints** when you have good initial guesses 8. **Enable parallel solving** for large problems when available 9. **Verify solutions** by checking constraints are satisfied 10. **Document your model** - variable names and constraint logic Google OR-Tools is the heavy machinery of the optimization world. It solves the discrete puzzles that power global logistics, airline scheduling, and manufacturing, turning impossible "Trial and Error" into mathematical certainty.