OR-Tools
OR-Tools - operations research tools - for Ruby
Installation
Download the OR-Tools C++ library. Then run:
bundle config build.or-tools --with-or-tools-dir=/path/to/or-tools
Add this line to your application’s Gemfile:
gem 'or-tools'
Getting Started
Linear Optimization
Constraint Optimization
Integer Optimization
Routing
Bin Packing
Network Flows
Assignment
The Glop Linear Solver
Declare the solver
solver = ORTools::Solver.new("LinearProgrammingExample", :glop)
Create the variables
x = solver.num_var(0, solver.infinity, "x")
y = solver.num_var(0, solver.infinity, "y")
Define the constraints
constraint0 = solver.constraint(-solver.infinity, 14)
constraint0.set_coefficient(x, 1)
constraint0.set_coefficient(y, 2)
constraint1 = solver.constraint(0, solver.infinity)
constraint1.set_coefficient(x, 3)
constraint1.set_coefficient(y, -1)
constraint2 = solver.constraint(-solver.infinity, 2)
constraint2.set_coefficient(x, 1)
constraint2.set_coefficient(y, -1)
Define the objective function
objective = solver.objective
objective.set_coefficient(x, 3)
objective.set_coefficient(y, 4)
objective.set_maximization
Invoke the solver
solver.solve
Display the solution
opt_solution = 3 * x.solution_value + 4 * y.solution_value
puts "Number of variables = #{solver.num_variables}"
puts "Number of constraints = #{solver.num_constraints}"
puts "Solution:"
puts "x = #{x.solution_value}"
puts "y = #{y.solution_value}"
puts "Optimal objective value = #{opt_solution}"
CP-SAT Solver
Declare the model
model = ORTools::CpModel.new
Create the variables
num_vals = 3
x = model.new_int_var(0, num_vals - 1, "x")
y = model.new_int_var(0, num_vals - 1, "y")
z = model.new_int_var(0, num_vals - 1, "z")
Create the constraint
model.add(x != y)
Call the solver
solver = ORTools::CpSolver.new
status = solver.solve(model)
Display the first solution
if status == :feasible
puts "x = #{solver.value(x)}"
puts "y = #{solver.value(y)}"
puts "z = #{solver.value(z)}"
end
Solving an Optimization Problem
Declare the model
model = ORTools::CpModel.new
Create the variables
var_upper_bound = [50, 45, 37].max
x = model.new_int_var(0, var_upper_bound, "x")
y = model.new_int_var(0, var_upper_bound, "y")
z = model.new_int_var(0, var_upper_bound, "z")
Define the constraints
model.add(x*2 + y*7 + z*3 <= 50)
model.add(x*3 - y*5 + z*7 <= 45)
model.add(x*5 + y*2 - z*6 <= 37)
Define the objective function
model.maximize(x*2 + y*2 + z*3)
Call the solver
solver = ORTools::CpSolver.new
status = solver.solve(model)
if status == :optimal
puts "Maximum of objective function: #{solver.objective_value}"
puts
puts "x value: #{solver.value(x)}"
puts "y value: #{solver.value(y)}"
puts "z value: #{solver.value(z)}"
end
Mixed-Integer Programming
Declare the MIP solver
solver = ORTools::Solver.new("simple_mip_program", :cbc)
Define the variables
infinity = solver.infinity
x = solver.int_var(0.0, infinity, "x")
y = solver.int_var(0.0, infinity, "y")
puts "Number of variables = #{solver.num_variables}"
Define the constraints
c0 = solver.constraint(-infinity, 17.5)
c0.set_coefficient(x, 1)
c0.set_coefficient(y, 7)
c1 = solver.constraint(-infinity, 3.5)
c1.set_coefficient(x, 1);
c1.set_coefficient(y, 0);
puts "Number of constraints = #{solver.num_constraints}"
Define the objective
objective = solver.objective
objective.set_coefficient(x, 1)
objective.set_coefficient(y, 10)
objective.set_maximization
Call the solver
status = solver.solve
Display the solution
if status == :optimal
puts "Solution:"
puts "Objective value = #{solver.objective.value}"
puts "x = #{x.solution_value}"
puts "y = #{y.solution_value}"
else
puts "The problem does not have an optimal solution."
end
Traveling Salesperson Problem (TSP)
Create the data
data = {}
data[:distance_matrix] = [
[0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972],
[2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579],
[713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260],
[1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987],
[1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371],
[1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999],
[2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701],
[213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099],
[2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600],
[875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162],
[1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200],
[2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504],
[1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0]
]
data[:num_vehicles] = 1
data[:depot] = 0
Create the distance callback
manager = ORTools::RoutingIndexManager.new(data[:distance_matrix].length, data[:num_vehicles], data[:depot])
routing = ORTools::RoutingModel.new(manager)
distance_callback = lambda do |from_index, to_index|
from_node = manager.index_to_node(from_index)
to_node = manager.index_to_node(to_index)
data[:distance_matrix][from_node][to_node]
end
transit_callback_index = routing.register_transit_callback(distance_callback)
routing.set_arc_cost_evaluator_of_all_vehicles(transit_callback_index)
Run the solver
assignment = routing.solve(first_solution_strategy: :path_cheaper_arc)
Print the solution
puts "Objective: #{assignment.objective_value} miles"
index = routing.start(0)
plan_output = String.new("Route for vehicle 0:\n")
route_distance = 0
while !routing.end?(index)
plan_output += " #{manager.index_to_node(index)} ->"
previous_index = index
index = assignment.value(routing.next_var(index))
route_distance += routing.arc_cost_for_vehicle(previous_index, index, 0)
end
plan_output += " #{manager.index_to_node(index)}\n"
puts plan_output
Vehicle Routing Problem (VRP)
Create the data
data = {}
data[:distance_matrix] = [
[0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662],
[548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210],
[776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754],
[696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358],
[582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244],
[274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708],
[502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480],
[194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856],
[308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514],
[194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468],
[536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354],
[502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844],
[388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730],
[354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536],
[468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194],
[776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798],
[662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0]
]
data[:num_vehicles] = 4
data[:depot] = 0
Define the distance callback
manager = ORTools::RoutingIndexManager.new(data[:distance_matrix].length, data[:num_vehicles], data[:depot])
routing = ORTools::RoutingModel.new(manager)
distance_callback = lambda do |from_index, to_index|
from_node = manager.index_to_node(from_index)
to_node = manager.index_to_node(to_index)
data[:distance_matrix][from_node][to_node]
end
transit_callback_index = routing.register_transit_callback(distance_callback)
routing.set_arc_cost_evaluator_of_all_vehicles(transit_callback_index)
Add a distance dimension
dimension_name = "Distance"
routing.add_dimension(transit_callback_index, 0, 3000, true, dimension_name)
distance_dimension = routing.mutable_dimension(dimension_name)
distance_dimension.global_span_cost_coefficient = 100
Run the solver
solution = routing.solve(first_solution_strategy: :path_cheapest_arc)
Print the solution
max_route_distance = 0
data[:num_vehicles].times do |vehicle_id|
index = routing.start(vehicle_id)
plan_output = String.new("Route for vehicle #{vehicle_id}:\n")
route_distance = 0
while !routing.end?(index)
plan_output += " #{manager.index_to_node(index)} -> "
previous_index = index
index = solution.value(routing.next_var(index))
route_distance += routing.arc_cost_for_vehicle(previous_index, index, vehicle_id)
end
plan_output += "#{manager.index_to_node(index)}\n"
plan_output += "Distance of the route: #{route_distance}m\n\n"
puts plan_output
max_route_distance = [route_distance, max_route_distance].max
end
puts "Maximum of the route distances: #{max_route_distance}m"
Routing Options
routing.solve(
solution_limit: 10,
time_limit: 10, # seconds,
lns_time_limit: 10, # seconds
first_solution_strategy: :path_cheapest_arc,
local_search_metaheuristic: :guided_local_search,
log_search: true
)
The Knapsack Problem
Create the data
values = [
360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 670, 892, 600, 38, 48, 147,
78, 256, 63, 17, 120, 164, 432, 35, 92, 110, 22, 42, 50, 323, 514, 28,
87, 73, 78, 15, 26, 78, 210, 36, 85, 189, 274, 43, 33, 10, 19, 389, 276,
312
]
weights = [[
7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 59, 18, 0, 36, 3, 8, 15, 42, 9, 0,
42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 2, 4, 18, 56, 7, 29, 93, 44, 71,
3, 86, 66, 31, 65, 0, 79, 20, 65, 52, 13
]]
capacities = [850]
Declare the solver
solver = ORTools::KnapsackSolver.new(:branch_and_bound, "KnapsackExample")
Call the solver
solver.init(values, weights, capacities)
computed_value = solver.solve
packed_items = []
packed_weights = []
total_weight = 0
puts "Total value = #{computed_value}"
values.length.times do |i|
if solver.best_solution_contains?(i)
packed_items << i
packed_weights << weights[0][i]
total_weight += weights[0][i]
end
end
puts "Total weight: #{total_weight}"
puts "Packed items: #{packed_items}"
puts "Packed weights: #{packed_weights}"
Multiple Knapsacks
Create the data
data = {}
weights = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
values = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
data[:weights] = weights
data[:values] = values
data[:items] = (0...weights.length).to_a
data[:num_items] = weights.length
num_bins = 5
data[:bins] = (0...num_bins).to_a
data[:bin_capacities] = [100, 100, 100, 100, 100]
Declare the solver
solver = ORTools::Solver.new("simple_mip_program", :cbc)
Create the variables
x = {}
data[:items].each do |i|
data[:bins].each do |j|
x[[i, j]] = solver.int_var(0, 1, "x_%i_%i" % [i, j])
end
end
Define the constraints
data[:items].each do |i|
sum = ORTools::LinearExpr.new
data[:bins].each do |j|
sum += x[[i, j]]
end
solver.add(sum <= 1.0)
end
data[:bins].each do |j|
weight = ORTools::LinearExpr.new
data[:items].each do |i|
weight += x[[i, j]] * data[:weights][i]
end
solver.add(weight <= data[:bin_capacities][j])
end
Define the objective
objective = solver.objective
data[:items].each do |i|
data[:bins].each do |j|
objective.set_coefficient(x[[i, j]], data[:values][i])
end
end
objective.set_maximization
Call the solver and print the solution
status = solver.solve
if status == :optimal
puts "Total packed value: #{objective.value}"
total_weight = 0
data[:bins].each do |j|
bin_weight = 0
bin_value = 0
puts "Bin #{j}\n\n"
data[:items].each do |i|
if x[[i, j]].solution_value > 0
puts "Item #{i} - weight: #{data[:weights][i]} value: #{data[:values][i]}"
bin_weight += data[:weights][i]
bin_value += data[:values][i]
end
end
puts "Packed bin weight: #{bin_weight}"
puts "Packed bin value: #{bin_value}"
puts
total_weight += bin_weight
end
puts "Total packed weight: #{total_weight}"
else
puts "The problem does not have an optimal solution."
end
Bin Packing Problem
Create the data
data = {}
weights = [48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30]
data[:weights] = weights
data[:items] = (0...weights.length).to_a
data[:bins] = data[:items]
data[:bin_capacity] = 100
Declare the solver
solver = ORTools::Solver.new("simple_mip_program", :cbc)
Create the variables
x = {}
data[:items].each do |i|
data[:bins].each do |j|
x[[i, j]] = solver.int_var(0, 1, "x_%i_%i" % [i, j])
end
end
y = {}
data[:bins].each do |j|
y[j] = solver.int_var(0, 1, "y[%i]" % j)
end
Define the constraints
data[:items].each do |i|
solver.add(solver.sum(data[:bins].map { |j| x[[i, j]] }) == 1)
end
data[:bins].each do |j|
sum = solver.sum(data[:items].map { |i| x[[i, j]] * data[:weights][i] })
solver.add(sum <= y[j] * data[:bin_capacity])
end
Define the objective
solver.minimize(solver.sum(data[:bins].map { |j| y[j] }))
Call the solver and print the solution
if status == :optimal
num_bins = 0
data[:bins].each do |j|
if y[j].solution_value == 1
bin_items = []
bin_weight = 0
data[:items].each do |i|
if x[[i, j]].solution_value > 0
bin_items << i
bin_weight += data[:weights][i]
end
end
if bin_weight > 0
num_bins += 1
puts "Bin number #{j}"
puts " Items packed: #{bin_items}"
puts " Total weight: #{bin_weight}"
puts
end
end
end
puts
puts "Number of bins used: #{num_bins}"
puts "Time = #{solver.wall_time} milliseconds"
else
puts "The problem does not have an optimal solution."
end
Maximum Flows
Define the data
start_nodes = [0, 0, 0, 1, 1, 2, 2, 3, 3]
end_nodes = [1, 2, 3, 2, 4, 3, 4, 2, 4]
capacities = [20, 30, 10, 40, 30, 10, 20, 5, 20]
Declare the solver and add the arcs
max_flow = ORTools::SimpleMaxFlow.new
start_nodes.length.times do |i|
max_flow.add_arc_with_capacity(start_nodes[i], end_nodes[i], capacities[i])
end
Invoke the solver and display the results
if max_flow.solve(0, 4) == :optimal
puts "Max flow: #{max_flow.optimal_flow}"
puts
puts " Arc Flow / Capacity"
max_flow.num_arcs.times do |i|
puts "%1s -> %1s %3s / %3s" % [
max_flow.tail(i),
max_flow.head(i),
max_flow.flow(i),
max_flow.capacity(i)
]
end
puts "Source side min-cut: #{max_flow.source_side_min_cut}"
puts "Sink side min-cut: #{max_flow.sink_side_min_cut}"
else
puts "There was an issue with the max flow input."
end
Minimum Cost Flows
Define the data
start_nodes = [ 0, 0, 1, 1, 1, 2, 2, 3, 4]
end_nodes = [ 1, 2, 2, 3, 4, 3, 4, 4, 2]
capacities = [15, 8, 20, 4, 10, 15, 4, 20, 5]
unit_costs = [ 4, 4, 2, 2, 6, 1, 3, 2, 3]
supplies = [20, 0, 0, -5, -15]
Declare the solver and add the arcs
min_cost_flow = ORTools::SimpleMinCostFlow.new
start_nodes.length.times do |i|
min_cost_flow.add_arc_with_capacity_and_unit_cost(
start_nodes[i], end_nodes[i], capacities[i], unit_costs[i]
)
end
supplies.length.times do |i|
min_cost_flow.set_node_supply(i, supplies[i])
end
Invoke the solver and display the results
if min_cost_flow.solve == :optimal
puts "Minimum cost #{min_cost_flow.optimal_cost}"
puts
puts " Arc Flow / Capacity Cost"
min_cost_flow.num_arcs.times do |i|
cost = min_cost_flow.flow(i) * min_cost_flow.unit_cost(i)
puts "%1s -> %1s %3s / %3s %3s" % [
min_cost_flow.tail(i),
min_cost_flow.head(i),
min_cost_flow.flow(i),
min_cost_flow.capacity(i),
cost
]
end
else
puts "There was an issue with the min cost flow input."
end
Assignment
Create the data
cost = [[ 90, 76, 75, 70],
[ 35, 85, 55, 65],
[125, 95, 90, 105],
[ 45, 110, 95, 115]]
rows = cost.length
cols = cost[0].length
Create the solver
assignment = ORTools::LinearSumAssignment.new
Add the costs to the solver
rows.times do |worker|
cols.times do |task|
if cost[worker][task]
assignment.add_arc_with_cost(worker, task, cost[worker][task])
end
end
end
Invoke the solver
solve_status = assignment.solve
if solve_status == :optimal
puts "Total cost = #{assignment.optimal_cost}"
puts
assignment.num_nodes.times do |i|
puts "Worker %d assigned to task %d. Cost = %d" % [
i,
assignment.right_mate(i),
assignment.assignment_cost(i)
]
end
elsif solve_status == :infeasible
puts "No assignment is possible."
elsif solve_status == :possible_overflow
puts "Some input costs are too large and may cause an integer overflow."
end
Assignment as a Min Cost Problem
Create the solver
min_cost_flow = ORTools::SimpleMinCostFlow.new
Create the data
start_nodes = [0, 0, 0, 0] + [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4] + [5, 6, 7, 8]
end_nodes = [1, 2, 3, 4] + [5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8] + [9, 9, 9, 9]
capacities = [1, 1, 1, 1] + [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] + [1, 1, 1, 1]
costs = [0, 0, 0, 0] + [90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115] + [0, 0, 0, 0]
supplies = [4, 0, 0, 0, 0, 0, 0, 0, 0, -4]
source = 0
sink = 9
tasks = 4
Create the graph and constraints
start_nodes.length.times do |i|
min_cost_flow.add_arc_with_capacity_and_unit_cost(
start_nodes[i], end_nodes[i], capacities[i], costs[i]
)
end
supplies.length.times do |i|
min_cost_flow.set_node_supply(i, supplies[i])
end
Invoke the solver
if min_cost_flow.solve == :optimal
puts "Total cost = #{min_cost_flow.optimal_cost}"
puts
min_cost_flow.num_arcs.times do |arc|
if min_cost_flow.tail(arc) != source && min_cost_flow.head(arc) != sink
if min_cost_flow.flow(arc) > 0
puts "Worker %d assigned to task %d. Cost = %d" % [
min_cost_flow.tail(arc),
min_cost_flow.head(arc),
min_cost_flow.unit_cost(arc)
]
end
end
end
else
puts "There was an issue with the min cost flow input."
end
Assignment as a MIP Problem
Create the solver
solver = ORTools::Solver.new("SolveAssignmentProblemMIP", :cbc)
Create the data
cost = [[90, 76, 75, 70],
[35, 85, 55, 65],
[125, 95, 90, 105],
[45, 110, 95, 115],
[60, 105, 80, 75],
[45, 65, 110, 95]]
team1 = [0, 2, 4]
team2 = [1, 3, 5]
team_max = 2
Create the variables
num_workers = cost.length
num_tasks = cost[1].length
x = {}
num_workers.times do |i|
num_tasks.times do |j|
x[[i, j]] = solver.bool_var("x[#{i},#{j}]")
end
end
Create the objective function
solver.minimize(solver.sum(
num_workers.times.flat_map { |i| num_tasks.times.map { |j| x[[i, j]] * cost[i][j] } }
))
Create the constraints
num_workers.times do |i|
solver.add(solver.sum(num_tasks.times.map { |j| x[[i, j]] }) <= 1)
end
num_tasks.times do |j|
solver.add(solver.sum(num_workers.times.map { |i| x[[i, j]] }) == 1)
end
solver.add(solver.sum(team1.flat_map { |i| num_tasks.times.map { |j| x[[i, j]] } }) <= team_max)
solver.add(solver.sum(team2.flat_map { |i| num_tasks.times.map { |j| x[[i, j]] } }) <= team_max)
Invoke the solver
sol = solver.solve
puts "Total cost = #{solver.objective.value}"
puts
num_workers.times do |i|
num_tasks.times do |j|
if x[[i, j]].solution_value > 0
puts "Worker %d assigned to task %d. Cost = %d" % [
i,
j,
cost[i][j]
]
end
end
end
puts
puts "Time = #{solver.wall_time} milliseconds"
History
View the changelog
Contributing
Everyone is encouraged to help improve this project. Here are a few ways you can help:
- Report bugs
- Fix bugs and submit pull requests
- Write, clarify, or fix documentation
- Suggest or add new features
To get started with development:
git clone https://github.com/ankane/or-tools.git
cd or-tools
bundle install
bundle exec rake compile -- --with-or-tools-dir=/path/to/or-tools
bundle exec rake test
Resources