Hands-on Optimization with OR-Tools in Python

From Beginning to Giving Up

This book is still under development.

For the Impatient

If you have experience with other optimization tools and you are just looking for some OR-Tools code examples, the example formulation and implementation below should give you a jump start. The formulation is devoid of any practical meanings.

\[\begin{align} \text{min.} &\quad \sum_{s \in \mathcal{S}} \sum_{d \in \mathcal{D}} c_{sd} x_{sd} \label{tp-obj} \\ \text{s.t.} &\quad \sum_{d \in \mathcal{D}} x_{sd} = p_s, \ \forall s \in \mathcal{S} \label{tp-cons1} \\ &\quad \sum_{s \in \mathcal{S}} x_{sd} = m_d, \ \forall d \in \mathcal{D} \label{tp-cons2} \\ &\quad x_{sd} \geq 0, \ \forall s \in \mathcal{S}, d \in \mathcal{D} \label{tp-cons3} \end{align}\]

The implementation in OR-Tools of the above model aims to convey a few information:

• A solver object has to be instantiated first in order to create variables, objective and constraints.
• Numerical variables can be created using the solver.NumVar() method.
• Objective is added using the solver.Minimize() (solver.Maximize()) function.
• Constraints are added using the solver.Add() function.
• Objective and constraint expressions can be built by first putting their elements into a list and using the solver.Sum() method to aggregate them.

from ortools.linear_solver import pywraplp

# gather data
num_sources = 4
num_destinations = 5
supplies = [58, 55, 64, 71]
demands = [44, 28, 36, 52, 88]
costs = [[8, 5, 13, 12, 12], 
        [8, 7, 18, 6, 5], 
        [11, 12, 5, 11, 18], 
        [19, 13, 5, 10, 18]]

# create solver
solver = pywraplp.Solver.CreateSolver("GLOP")

# create decision variables
var_flow = []
for src_idx in range(num_sources):
    vars = [
        solver.NumVar(0, solver.Infinity(), 
                    name=f"var_{src_idx}, {dest_idx}")
        for dest_idx in range(num_destinations)
    ]
    var_flow.append(vars)

# create constraints
for src_idx in range(num_sources):
    expr = [var_flow[src_idx][dest_idx] 
            for dest_idx in range(num_destinations)]
    solver.Add(solver.Sum(expr) == supplies[src_idx])

for dest_idx in range(num_destinations):
    expr = [var_flow[src_idx][dest_idx] 
            for src_idx in range(num_sources)]
    solver.Add(solver.Sum(expr) == demands[dest_idx])

# create objective function
obj_expr = []
for src_idx in range(num_sources):
    for dest_idx in range(num_destinations):
        obj_expr.append(var_flow[src_idx][dest_idx] * costs[src_idx][dest_idx])
solver.Minimize(solver.Sum(obj_expr))

status = solver.Solve()

opt_flow = []
if status == pywraplp.Solver.OPTIMAL:
    print(f"optimal obj = {solver.Objective().Value()}")
    for src_idx in range(num_sources):
        opt_vals = [var_flow[src_idx][dest_idx].solution_value()
                    for dest_idx in range(num_destinations)]
        opt_flow.append(opt_vals)