MILP Factory › Implementation in Google OR-Tools
Machine Learning from ScratchAll chapters MILP Factory › Implementation in Google OR-ToolsOne section · Sections in this chapter5 / 8 ↓
Reading tools Definitions & inline links
Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.
Article links
Make inline references clickable
Google OR-Tools provides an excellent framework for solving MILP problems with its CP-SAT solver, which is specifically designed for constraint programming and mixed integer problems. OR-Tools offers both a Python API and C++ implementation, making it accessible for data scientists while maintaining high performance.
Basic Factory Optimization
Let's start with a simple factory optimization problem that demonstrates the core MILP concepts. We'll solve the two-product problem from our earlier example using OR-Tools.
First, we set up the problem by creating a solver, defining variables, and specifying constraints:
from ortools.linear_solver import pywraplp
def solve_factory_optimization():
"""
Solve a factory optimization problem using Google OR-Tools MILP solver.
Problem: Maximize profit from two products with machine capacity constraints.
"""
# Create the solver
solver = pywraplp.Solver.CreateSolver("SCIP")
if not solver:
return None
# Define variables
# x1 = units of product 1 to produce
# x2 = units of product 2 to produce
x1 = solver.IntVar(0, solver.infinity(), "x1")
x2 = solver.IntVar(0, solver.infinity(), "x2")
# Define constraints
# Machine A: 2x1 + 3x2 <= 12
constraint_a = solver.Constraint(-solver.infinity(), 12)
constraint_a.SetCoefficient(x1, 2)
constraint_a.SetCoefficient(x2, 3)
# Machine B: 4x1 + 2x2 <= 16
constraint_b = solver.Constraint(-solver.infinity(), 16)
constraint_b.SetCoefficient(x1, 4)
constraint_b.SetCoefficient(x2, 2)
# Objective: maximize 3x1 + 2x2
objective = solver.Objective()
objective.SetCoefficient(x1, 3)
objective.SetCoefficient(x2, 2)
objective.SetMaximization()
# Solve the problem
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
# Calculate solution values
x1_value = x1.solution_value()
x2_value = x2.solution_value()
profit = solver.Objective().Value()
# Verify constraints
machine_a_usage = 2 * x1_value + 3 * x2_value
machine_b_usage = 4 * x1_value + 2 * x2_value
return {
"x1": x1_value,
"x2": x2_value,
"profit": profit,
"machine_a_usage": machine_a_usage,
"machine_b_usage": machine_b_usage,
"status": "OPTIMAL",
}
else:
return {"status": "NO_SOLUTION"}
# Solve the problem
result = solve_factory_optimization()Now let's display the results:
Optimal solution found! Product 1 (x₁): 3 units Product 2 (x₂): 2 units Total profit: $13.00 Constraint verification: Machine A usage: 12.0 hours (capacity: 12) Machine B usage: 16.0 hours (capacity: 16)
The solver found an optimal solution. The production quantities and profit values shown above match our earlier manual calculation. The constraint verification confirms that both machines are fully utilized, with Machine A using exactly its full capacity of 12 hours and Machine B using its full capacity of 16 hours. This full utilization indicates that the solution is efficient and that the capacity constraints are binding, meaning we cannot increase production without violating constraints. When both constraints are binding at the optimal solution, it suggests that the problem is well-formulated and that the solver has found the true optimal point where no further improvement is possible.
Advanced Factory Optimization with Setup Costs
Now let's tackle a more realistic factory optimization problem that includes setup costs and multiple products. This demonstrates how binary variables model discrete setup decisions alongside continuous production quantities.
We'll optimize production of three products across three machines, where each product requires a setup (incurring a fixed cost) before production can begin:
def solve_advanced_factory_optimization():
"""
Advanced factory optimization with setup costs and multiple products.
Problem: Optimize production of 3 products with:
- Setup costs (binary decisions)
- Machine capacity constraints
- Demand constraints
- Profit maximization
"""
# Create the solver
solver = pywraplp.Solver.CreateSolver("SCIP")
if not solver:
return None
# Problem parameters
products = ["Product_A", "Product_B", "Product_C"]
machines = ["Machine_1", "Machine_2", "Machine_3"]
# Production data: [product][machine] = hours required
# Product A: efficient on Machine 2, uses Machine 1 and 3 moderately
# Product B: heavy on Machine 2 (bottleneck), efficient elsewhere
# Product C: balanced but uses all machines equally
production_time = [
[3, 1, 2], # Product A: efficient, especially on Machine 2
[1, 4, 2], # Product B: heavy on Machine 2 bottleneck
[3, 3, 3], # Product C: balanced but uses more total time
]
# Machine capacities (hours) - Machine 2 is the bottleneck
machine_capacity = [28, 18, 24] # Machine 2 is tightest constraint
# Profit per unit - make Product A competitive
profit_per_unit = [14, 11, 15] # Product A and C are close
# Setup costs - create interesting trade-offs
# Product A: moderate setup, good profit, efficient production
# Product B: low setup, moderate profit, but bottleneck constraint
# Product C: higher setup, best profit, but uses more machine time
setup_cost = [30, 18, 50] # Product C setup is higher
# Demand constraints - allow reasonable production
max_demand = [7, 5, 8]
# Create variables
# x[i] = units of product i to produce
x = []
for i in range(len(products)):
x.append(solver.IntVar(0, max_demand[i], f"x_{i}"))
# y[i] = 1 if product i is produced (setup), 0 otherwise
y = []
for i in range(len(products)):
y.append(solver.IntVar(0, 1, f"y_{i}"))
# Machine capacity constraints
for j in range(len(machines)):
constraint = solver.Constraint(-solver.infinity(), machine_capacity[j])
for i in range(len(products)):
constraint.SetCoefficient(x[i], production_time[i][j])
constraint.SetCoefficient(y[j], 0) # Setup doesn't consume machine time
# Setup constraints: if x[i] > 0, then y[i] = 1
# This is enforced by: x[i] <= max_demand[i] * y[i]
for i in range(len(products)):
constraint = solver.Constraint(-solver.infinity(), 0)
constraint.SetCoefficient(x[i], 1)
constraint.SetCoefficient(y[i], -max_demand[i])
# Objective: maximize profit - setup costs
objective = solver.Objective()
for i in range(len(products)):
objective.SetCoefficient(x[i], profit_per_unit[i])
objective.SetCoefficient(y[i], -setup_cost[i])
objective.SetMaximization()
# Solve
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
# Extract solution values
production = [x[i].solution_value() for i in range(len(products))]
setup = [y[i].solution_value() for i in range(len(products))]
# Calculate detailed metrics
total_profit = 0
total_setup_cost = 0
product_details = []
for i, product in enumerate(products):
units = production[i]
setup_flag = setup[i]
product_profit = units * profit_per_unit[i]
product_setup = setup_flag * setup_cost[i]
net_contribution = product_profit - product_setup
product_details.append(
{
"product": product,
"units": units,
"setup": setup_flag,
"product_profit": product_profit,
"setup_cost": product_setup,
"net_contribution": net_contribution,
}
)
total_profit += product_profit
total_setup_cost += product_setup
# Calculate machine utilization
machine_utilization = []
for j, machine in enumerate(machines):
usage = sum(
production_time[i][j] * production[i]
for i in range(len(products))
)
utilization = usage / machine_capacity[j] * 100
machine_utilization.append(
{
"machine": machine,
"usage": usage,
"capacity": machine_capacity[j],
"utilization": utilization,
}
)
return {
"production": production,
"setup": setup,
"total_profit": total_profit,
"total_setup_cost": total_setup_cost,
"net_profit": total_profit - total_setup_cost,
"product_details": product_details,
"machine_utilization": machine_utilization,
"status": "OPTIMAL",
}
else:
return {"status": "NO_SOLUTION"}
# Solve the advanced problem
advanced_result = solve_advanced_factory_optimization()Let's examine the optimization results:
Advanced Factory Optimization Results: ================================================== Product_A: Units produced: 7 Setup required: Yes Product profit: $98.00 Setup cost: $30.00 Net contribution: $68.00 Product_B: Units produced: 2 Setup required: Yes Product profit: $22.00 Setup cost: $18.00 Net contribution: $4.00 Product_C: Units produced: 0 Setup required: No Product profit: $0.00 Setup cost: $0.00 Net contribution: $0.00 Total profit from production: $120.00 Total setup costs: $48.00 Net profit: $72.00 Machine Utilization: Machine_1: 23.0/28 hours (82.1%) Machine_2: 15.0/18 hours (83.3%) Machine_3: 18.0/24 hours (75.0%)
The optimization results demonstrate how the solver balances production quantities against setup costs. Products with higher profit margins and lower setup costs are prioritized in the optimal solution, while products that don't contribute enough to cover their setup costs may be excluded entirely. For example, if a product has a setup cost of $50 but only generates $40 in profit, the solver will set its production to zero rather than incurring a net loss.
The machine utilization percentages indicate how efficiently each machine is being used. Values near 100% suggest that machine capacity is a binding constraint, meaning that increasing capacity would allow for higher production and potentially greater profit. Lower utilization (e.g., below 80%) might indicate that other constraints, such as demand limits, setup cost trade-offs, or resource availability on other machines, are preventing full machine usage. In such cases, the bottleneck is not the machine capacity itself but rather other factors in the optimization problem.
Let's visualize the results from the advanced factory optimization:
Total Net Profit: $72.00 - Production Profit: $120.00 - Setup Costs: $48.00 Products Produced: 2 out of 3 Average Machine Utilization: 80.2%
Sensitivity Analysis
Understanding how changes in problem parameters affect optimal solutions helps us make better decisions. Let's perform sensitivity analysis by solving the optimization problem under different scenarios:
def solve_scenario(profit, setup):
"""Solve a single scenario and return results"""
# Try multiple solvers in order of preference
solver_names = ["SCIP", "CBC", "GLOP"]
solver = None
for solver_name in solver_names:
solver = pywraplp.Solver.CreateSolver(solver_name)
if solver:
break
if not solver:
return None
x = [solver.IntVar(0, 10, f"x_{i}") for i in range(3)]
y = [solver.IntVar(0, 1, f"y_{i}") for i in range(3)]
production_time = [[2, 1, 3], [1, 3, 2], [3, 2, 1]]
machine_capacity = [20, 25, 15]
# Machine capacity constraints
for j in range(3):
constraint = solver.Constraint(-solver.infinity(), machine_capacity[j])
for i in range(3):
constraint.SetCoefficient(x[i], production_time[i][j])
# Setup constraints: if x[i] > 0, then y[i] = 1
for i in range(3):
constraint = solver.Constraint(-solver.infinity(), 0)
constraint.SetCoefficient(x[i], 1)
constraint.SetCoefficient(y[i], -10)
# Objective: maximize profit - setup costs
objective = solver.Objective()
for i in range(3):
objective.SetCoefficient(x[i], profit[i])
objective.SetCoefficient(y[i], -setup[i])
objective.SetMaximization()
# Solve with a time limit
solver.SetTimeLimit(5000)
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
return {
"net_profit": solver.Objective().Value(),
"production": [x[i].solution_value() for i in range(3)],
"setup": [y[i].solution_value() for i in range(3)],
}
else:
return {
"net_profit": 0.0,
"production": [0.0, 0.0, 0.0],
"setup": [0.0, 0.0, 0.0],
}
# Define scenarios with adjusted parameters to ensure profitable solutions
scenarios = [
("Original", [15, 12, 18], [50, 40, 60]),
("Higher\nProduct\nProfit", [20, 18, 25], [50, 40, 60]),
("Lower\nSetup\nCosts", [15, 12, 18], [25, 20, 30]),
("High\nSetup\nCosts", [15, 12, 18], [100, 80, 120]),
]
# Solve all scenarios
sensitivity_results = []
for name, profit, setup in scenarios:
result = solve_scenario(profit, setup)
if result:
sensitivity_results.append((name, result))
else:
sensitivity_results.append(
(
name,
{
"net_profit": 0.0,
"production": [0.0, 0.0, 0.0],
"setup": [0.0, 0.0, 0.0],
},
)
)Now let's display the sensitivity analysis results:
Sensitivity Analysis: Impact of Parameter Changes ============================================================ Original: ------------------------------ Net Profit: $50.00 Production: ['0', '5', '5'] Setup Decisions: ['0', '1', '1'] Higher Product Profit: ------------------------------ Net Profit: $115.00 Production: ['0', '5', '5'] Setup Decisions: ['0', '1', '1'] Lower Setup Costs: ------------------------------ Net Profit: $100.00 Production: ['0', '5', '5'] Setup Decisions: ['0', '1', '1'] High Setup Costs: ------------------------------ Net Profit: $4.00 Production: ['0', '7', '0'] Setup Decisions: ['0', '1', '0']
The sensitivity analysis reveals how parameter changes affect optimal decisions. Comparing the scenarios shown above, higher product profits generally lead to increased production and higher net profits, as the additional revenue more than compensates for setup costs. When product profits increase by 25-40% (as in the "Higher Product Profit" scenario), the solver can justify additional setups and higher production volumes.
Lower setup costs make it economically viable to produce more products, potentially increasing total production volume. When setup costs are reduced by 50% (as in the "Lower Setup Costs" scenario), products that were previously unprofitable due to high setup costs may now be included in the optimal solution. Conversely, high setup costs (doubled in the "High Setup Costs" scenario) may cause the optimizer to reduce the number of products produced, focusing only on those with the best profit-to-setup-cost ratios. This analysis helps factory managers understand which parameters have the most impact on profitability and where to focus improvement efforts, such as negotiating lower setup costs or improving production efficiency to increase profit margins.
Let's visualize the sensitivity analysis results to compare how different scenarios affect the optimal solution:
Original: Net Profit: $50.00 Production: ['0', '5', '5'] Setup Decisions: ['0', '1', '1'] Higher Product Profit: Net Profit: $115.00 Production: ['0', '5', '5'] Setup Decisions: ['0', '1', '1'] Lower Setup Costs: Net Profit: $100.00 Production: ['0', '5', '5'] Setup Decisions: ['0', '1', '1'] High Setup Costs: Net Profit: $4.00 Production: ['0', '7', '0'] Setup Decisions: ['0', '1', '0']
Key Parameters
Below are some of the main parameters and methods that affect how MILP solvers work and perform in Google OR-Tools:
Key Solver Parameters
-
Solver.CreateSolver(solver_name): Creates a solver instance. Common options include'SCIP'(recommended for MILP),'CBC'(open-source alternative), and'GLOP'(for linear programming only). SCIP typically provides the best performance for mixed integer problems but requires a license for commercial use. -
SetTimeLimit(seconds): Sets the maximum time in milliseconds for the solver to run (default: no limit). Use this to prevent the solver from running indefinitely on difficult problems. Typical values range from 1000-10000 milliseconds depending on problem complexity. -
SetNumThreads(n): Sets the number of threads for parallel solving (default: uses all available cores). For large problems, increasing threads can speed up solution time, but may not always improve performance due to overhead.
Key Variable Creation Methods
-
IntVar(lower_bound, upper_bound, name): Creates an integer variable with specified bounds. Usesolver.infinity()for unbounded variables. Integer variables are important for modeling discrete decisions like production quantities that should be whole numbers. -
BoolVar(name): Creates a binary variable (equivalent toIntVar(0, 1, name)). Binary variables model yes/no decisions like setup choices or machine selection. More efficient than integer variables for binary decisions. -
NumVar(lower_bound, upper_bound, name): Creates a continuous variable for quantities that can take fractional values. Use when integer constraints are not required, as continuous variables solve faster.
Key Constraint Methods
-
Constraint(lower_bound, upper_bound): Creates a linear constraint with specified bounds. Use-solver.infinity()for unbounded lower bounds andsolver.infinity()for unbounded upper bounds. The constraint is enforced as: lower_bound ≤ expression ≤ upper_bound. -
SetCoefficient(variable, coefficient): Sets the coefficient for a variable in a constraint. Call this method for each variable in the constraint expression. Coefficients can be positive or negative to model resource consumption or production.
Key Objective Methods
-
SetMaximization(): Sets the objective to maximize (default is minimization). Use for profit maximization problems. The objective function is built by setting coefficients for each variable. -
SetMinimization(): Sets the objective to minimize. Use for cost minimization problems. This is the default behavior if neither method is called. -
SetCoefficient(variable, coefficient): Sets the coefficient for a variable in the objective function. Positive coefficients for maximization problems, negative for minimization (or vice versa depending on whether you're maximizing profit or minimizing cost).
Key Solution Methods
-
Solve(): Solves the optimization problem and returns a status code. ReturnsSolver.OPTIMALif an optimal solution was found,Solver.FEASIBLEif a feasible but not necessarily optimal solution was found, or other status codes for infeasible or unbounded problems. -
solution_value(): Returns the value of a variable in the optimal solution. Call this method on each variable after a successful solve to extract the solution values. -
Objective().Value(): Returns the value of the objective function at the optimal solution. Use this to get the total profit or cost after solving.