OR-Tools

Google OR-Tools is an open-source, fast, and portable software suite designed to solve combinatorial optimization problems. It uses state-of-the-art algorithms to find optimal or near-optimal solutions from vast sets of possible solutions. The .NET wrapper allows developers to integrate these optimization capabilities into .NET applications.

Key problem domains include:

• Vehicle Routing: Finding optimal routes for fleets subject to constraints like capacity or time windows.
• Scheduling: Optimizing task sequences on machines or resources with precedence constraints.
• Bin Packing: Maximizing the number of objects packed into bins with fixed capacities.
• Constraint Programming: Finding feasible solutions based on complex constraints (e.g., resource exclusivity or distance limits).
• Linear and Mixed-Integer Programming: Using solvers like Glop (linear optimizer) or SCIP (mixed-integer programming) to optimize objective functions subject to linear inequalities.
• Graph Algorithms: Solving shortest path, min-cost flow, max flow, and linear sum assignment problems.

OR-Tools is an open-source suite of operations research tools developed by Google. It provides specialized solvers for several mathematical optimization domains:

• Constraint Programming
  • CP-SAT solver: A constraint programming solver utilizing SAT (satisfiability) methods.
  • Original CP solver: A standard constraint programming solver.
• Linear and Mixed-Integer Programming
  • Glop: A linear optimizer designed to find the optimal value of a linear objective function subject to linear inequality constraints.
  • MPSolver and ModelBuilder: High-level wrappers that interface with various commercial and open-source solvers, such as CBC, CLP, GLPK, Gurobi, or SCIP.
• Vehicle Routing
  • A specialized library for solving routing problems to identify optimal vehicle paths under specific constraints.
• Graph Algorithms
  • Implementations for finding shortest paths, min-cost flows, max flows, and linear sum assignments.

OR-Tools provides a variety of C++ examples categorized by the underlying solver or problem type. Use these as templates for your own modeling:

Constraint Solver Examples

Focus on modeling objects like integer variables, arithmetic constraints, and search strategies:

• cryptarithm.cc: Basic modeling (variables, arithmetic constraints, simple search).
• golomb.cc: Handling objective functions and collecting multiple solutions.
• magic_square.cc: Using automatic search.
• costas_array.cc: Feasibility (hard constraints) vs. Optimization (soft constraints/violation costs).
• jobshop.cc: Job scheduling on machines.
• nqueens.cc: Solving N-Queens and breaking symmetries during search.
• network_routing_sat.cc: Multicommodity mono-routing with capacity constraints.
• sports_scheduling_sat.cc: Soccer championship scheduling using global constraints.
• dobble_ls.cc: Writing custom Local Search operators, filters, and simple constraints.

Routing Examples

Specific implementations for vehicle and delivery logistics:

• cvrptw.cc: Capacitated Vehicle Routing Problem with Time Windows.
• pdptw.cc: Pickup and Delivery Problem with Time Windows.

Graph Examples

Using graph-based APIs:

• flow_api.cc: Min-Cost Flow and Max-Flow APIs.
• linear_assignment_api.cc: Linear Sum Assignment solver.
• dimacs_assignment.cc: Solving DIMACS assignment challenges.

Linear and Integer Programming Examples

Using the linear solver wrapper API:

• linear_programming.cc: Solving Linear Programming (LP) problems.
• integer_programming.cc: Solving Integer Programming (IP) problems.
• linear_solver_protocol_buffers.cc: Using Protocol Buffers for LP/IP input and output.
• strawberry_fields_with_column_generation.cc: Dynamic column generation for 2D covering problems.

OR-Tools provides a unified way to model and solve Linear Programming (LP) and Integer Programming (IP) problems. The modern workflow involves modeling your problem using the MPModelRequest Protocol Buffer API and then passing that request to a solver using the SolveMPModel() function.

Core Components

• MPModelRequest (Proto API): Defined in linear_solver.proto, this is the primary way to describe your optimization model (objective function, constraints, and variable types).
• SolveMPModel(): The main entry point for execution, found in solve_mp_model.h. It takes an MPModelRequest and runs it through a specified solver engine.
• ModelBuilder: Available in Python and Java, these classes provide a high-level abstraction to help you construct complex MPModelRequest objects, particularly when dealing with linear expressions.
• MPSolver (Legacy): An older API that is no longer in active development. While it is largely interoperable with the MPModelRequest API, it may not support all modern features.

Problem Mathematical Form

Models typically follow this structure: $$\begin{array}{lll} (P) & \max & cx\ & s.t. & L\leq Ax\leq U\ & & l\leq x\leq u\ & &x_i\in\mathbb{Z}\quad\forall i\in I\ \end{array}$$