Google OR-Tools

Google OR-Tools

Here is a basic example of using $OR-Tools$ in $Python$ to solve a simple linear programming problem.

$OR-Tools$ is a powerful optimization library provided by Google, and it can be used to solve a wide range of problems, including linear programming, mixed-integer programming, constraint programming, and more.

Example: Linear Programming with OR-Tools

This example demonstrates solving a linear programming problem where we want to maximize the objective function $3x + 4y$ subject to some constraints.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from ortools.linear_solver import pywraplp

def main():
    # Create the solver with the SCIP backend.
    solver = pywraplp.Solver.CreateSolver('SCIP')
    if not solver:
        return

    # Create the variables x and y.
    x = solver.NumVar(0, solver.infinity(), 'x')
    y = solver.NumVar(0, solver.infinity(), 'y')

    # Create the constraints.
    solver.Add(2 * x + 3 * y <= 12)
    solver.Add(4 * x + y <= 14)
    solver.Add(3 * x - y >= 0)

    # Define the objective function.
    objective = solver.Maximize(3 * x + 4 * y)

    # Solve the problem.
    status = solver.Solve()

    # Check the result status.
    if status == pywraplp.Solver.OPTIMAL:
        print('Solution:')
        print('Objective value =', solver.Objective().Value())
        print('x =', x.solution_value())
        print('y =', y.solution_value())
    else:
        print('The problem does not have an optimal solution.')

if __name__ == '__main__':
    main()

Explanation

  • Solver: We create a solver instance using pywraplp.Solver.CreateSolver('SCIP'). $SCIP$ is a powerful mixed-integer programming solver, and $OR-Tools$ uses it as one of its backends.
  • Variables: We define two variables, x and y, both with a lower bound of 0 and an upper bound of infinity.
  • Constraints: We add three constraints:
    1. $(2x + 3y \leq 12)$
    2. $(4x + y \leq 14)$
    3. $(3x - y \geq 0)$
  • Objective: We want to maximize the function $3x + 4y$.
  • Solve: The solver solves the problem, and we check if an optimal solution was found.
  • Result: If a solution is found, it prints the optimal objective value and the values of x and y.

Output

1
2
3
4
Solution:
Objective value = 17.0
x = 2.9999999999999996
y = 2.0000000000000018

Let’s break down the result of the optimization problem using $OR-Tools$:

Objective Value:

  • Objective value = 17.0: This is the maximum value of the objective function 3x + 4y given the constraints.
    The solver found that this is the highest value that can be achieved without violating any of the constraints.

Variable Values:

  • x = 2.9999999999999996: This is the optimal value of the variable x that maximizes the objective function.
    Due to floating-point precision in computational mathematics, this value is extremely close to 3 (but not exactly 3).
  • y = 2.0000000000000018: Similarly, this is the optimal value of the variable y. This value is extremely close to 2.

Interpretation:

  • Floating-Point Precision: The values 2.9999999999999996 for x and 2.0000000000000018 for y are due to the way computers handle floating-point arithmetic. In practice, these values can be considered as x = 3 and y = 2.

  • Objective Function Calculation: Given the optimal values of x and y, we can calculate the objective function:
    $$
    3x + 4y = 3(3) + 4(2) = 9 + 8 = 17
    $$
    This confirms that the objective value of 17.0 is indeed the maximum value that can be achieved under the given constraints.

Summary:

The solver has determined that to achieve the maximum value of 17 for the objective function 3x + 4y, the values of x and y should be approximately 3 and 2, respectively.

The slight deviations from exact integers are due to the limitations of floating-point representation in computers.

Running the Code

To run this code, ensure you have installed the $OR-Tools$ package.
You can install it using pip:

1
pip install ortools

This example should give you a good starting point for working with $OR-Tools$ in $Python$.