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