⚠

EXPERIMENTAL: These features are experimental and should not be used in production systems.

Mathematical Optimization: The Transportation Problem

The transportation problem is a classic optimization problem in operations research and supply chain management. The goal is to find the most cost-effective way to transport goods from multiple supply nodes (factories, warehouses, etc.) to various demand nodes (stores, customers, etc.). Each supply node has a limited supply capacity, and each demand node has a certain demand level. Additionally, there is a cost associated with transporting goods from each supply node to each demand node.

Because the transportation problem is a linear programming problem, we can use Rel’s Mathematical Optimization Library to model and solve it. To begin, we will first import operators from the mathopt:Solver:Solve DSL. These operators are used to define the objective function and constraints of the optimization problem.

// model
 
// Import the mathopt library DSL operators.
with mathopt:Solver:Solve use sum, foreach, +, -, *, ≼, ≽, /, =

The data for the transportation problem is summarized in the following relation:

// model
 
// Define the data.
module data
    def supply_nodes    = "S1" ; "S2"
    def demand_nodes    = "D1" ; "D2" ; "D3"
    def supply          = { ("S1", 50) ; ("S2", 60) }
    def demand          = { ("D1", 30) ; ("D2", 40) ; ("D3", 40) }
    def transport_costs = {
        ("S1", "D1", 8) ; ("S1", "D2", 6) ; ("S1", "D3", 10) ;
        ("S2", "D1", 5) ; ("S2", "D2", 4) ; ("S2", "D3", 3)
    }
end
// Bring values from data into scope.
with data use supply_nodes, demand_nodes, supply, demand, transport_costs

The data here specifies a set of supply nodes supply_nodes and a set of demand nodes demand_nodes. Each supply node s has a supply capacity supply[s], and each demand node d has a demand level demand[d]. Additionally, there is a transportation cost transport_costs[s, d] associated with transporting goods from supply node s to demand node d. In summary, we observe:

supply_nodes: Set of supply nodes (e.g., factories, warehouses)
demand_nodes: Set of demand nodes (e.g., stores, customers)
supply[s]: Supply capacity at supply node s
demand[d]: Demand level at demand node d
transport_costs[s, d]: Transportation cost per unit from supply node s to demand node d

The goal is to determine the optimal transportation plan, represented by the decision variables x[s, d], which indicates the number of goods to be transported from supply node s to demand node d. With the following code, we define the decision variables x[s, d]:

// model
 
// Define model decision variables.
def model:variables = rel:mathopt:variables[
    {:x, "continuous", (supply_nodes, demand_nodes)};
    {:x, "lower_bound", 0.0}
]
// Bring values from model:variables into scope.
with model:variables use x

The objective function here is to minimize the total transportation cost. This is formulated by multiplying the decision variable x[s, d] with the corresponding transportation cost transport_costs[s, d]. Here, x[s, d] represents the quantity of goods transported from supply node s to demand node d. The objective function sums this up for all supply and demand node pairs.

// model
 
// Define the sense of the optimization problem and the objective function.
def model:minimize = sum[transport_costs[s, d] * x[s, d] for s in supply_nodes, d in demand_nodes]

Supply constraints: For each supply node, the total quantity of goods transported out of it (sum of x[s, d] for all demand nodes d) should not exceed the supply capacity of that node supply[s].

// model
 
// Define the supply constraints.
// For each supply node, the total quantity of goods transported out of it should not exceed the supply capacity of that node.
def model:constraints:supply = foreach[s in supply_nodes : sum[x[s, d] for d in demand_nodes] ≼ supply[s]]

Demand constraints: For each demand node, the total quantity of goods transported to it (sum of x[s, d] for all supply nodes s) should be at least the demand of that node demand[d].

// model
 
// Define the demand constraints.
// For each demand node, the total quantity of goods transported to it should be at least the demand of that node.
def model:constraints:demand = foreach[d in demand_nodes : sum[x[s, d] for s in supply_nodes] ≽ demand[d]]

These two sets of constraints ensure that we respect the supply and demand limits at each node while minimizing the overall transportation cost.

We have formulated our model as a classical linear programming (LP) problem, which can be efficiently solved using LP solvers. Rel’s Mathematical Optimization Library provides a convenient way to define and solve such problems in a high-level, declarative manner. The following line of code passes the model to an optimizer, which will solve the optimization problem and return the result.

// model
 
// Optimize the model.
def result = rel:mathopt:optimize[model, {}]

Once the model is solved, we can extract the results. The following line of code uses the rel:mathopt:extract_result relation to retrieve the solution of the optimization problem, including the optimal values of the decision variables and the optimal objective value.

// read query
 
// Extract the result of the optimization process.
def output = rel:mathopt:extract_result[result, model:variables]

The extracted table will contain information about the optimization outcome, objective value, solution, solver, solver time, and other details. You can use this information to analyze the optimal transportation plan and the total transportation cost.

That’s it! You’ve learned how to formulate and solve a transportation problem using Rel’s Mathematical Optimization Library. By understanding the basic components of the model, such as the objective function, variables, and constraints, you can adapt this approach to solve other linear programming, mixed-integer programming, quadratic programming, and mixed-integer quadratic programming problems.

Full Code Implementation

The full code implementation of the transportation problem is shown below. You can copy and paste this code into the Rel console to run it.

// model
 
// Import the Mathematical Optimization Library DSL operators.
with mathopt:Solver:Solve use sum, foreach, +, -, *, ≼, ≽, /, =
 
// Define the data.
module data
    def supply_nodes    = "S1" ; "S2"
    def demand_nodes    = "D1" ; "D2" ; "D3"
    def supply          = { ("S1", 50) ; ("S2", 60) }
    def demand          = { ("D1", 30) ; ("D2", 40) ; ("D3", 40) }
    def transport_costs = {
        ("S1", "D1", 8) ; ("S1", "D2", 6) ; ("S1", "D3", 10) ;
        ("S2", "D1", 5) ; ("S2", "D2", 4) ; ("S2", "D3", 3)
    }
end
// Bring values from data into scope.
with data use supply_nodes, demand_nodes, supply, demand, transport_costs
 
// Define model decision variables.
def model:variables = rel:mathopt:variables[
    {:x, "continuous", (supply_nodes, demand_nodes)};
    {:x, "lower_bound", 0.0}
]
// Bring values from model:variables into scope.
with model:variables use x
 
// Define the sense of the optimization problem and the objective function.
def model:minimize = sum[transport_costs[s, d] * x[s, d] for s in supply_nodes, d in demand_nodes]
 
// Define the supply constraints.
// For each supply node, the total quantity of goods transported out of it should not exceed the supply capacity of that node.
def model:constraints:supply = foreach[s in supply_nodes : sum[x[s, d] for d in demand_nodes] ≼ supply[s]]
 
// Define the demand constraints.
// For each demand node, the total quantity of goods transported to it should be at least the demand of that node.
def model:constraints:demand = foreach[d in demand_nodes : sum[x[s, d] for s in supply_nodes] ≽ demand[d]]
 
// Optimize the model.
def result = rel:mathopt:optimize[model, {}]
 
// Extract the result of the optimization process.
def output = rel:mathopt:extract_result[result, model:variables]

Alternatively, you can wrap the model in a module that keeps the imported DSL operators local to the module. This can be beneficial when you want to use Rel base operators with the same name as the DSL operators.

// model
 
// Define the data.
module data
    def supply_nodes    = "S1" ; "S2"
    def demand_nodes    = "D1" ; "D2" ; "D3"
    def supply          = { ("S1", 50) ; ("S2", 60) }
    def demand          = { ("D1", 30) ; ("D2", 40) ; ("D3", 40) }
    def transport_costs = {
        ("S1", "D1", 8) ; ("S1", "D2", 6) ; ("S1", "D3", 10) ;
        ("S2", "D1", 5) ; ("S2", "D2", 4) ; ("S2", "D3", 3)
    }
end
 
// Define your model as a module.
module model
    // Import the Mathematical Optimization Library DSL operators.
    with mathopt:Solver:Solve use sum, foreach, +, -, *, ≼, ≽, /, =
 
    // Bring values from data into scope.
    with data use supply_nodes, demand_nodes, supply, demand, transport_costs
 
    // Define the model decision variables.
    def variables = rel:mathopt:variables[
        {:x, "continuous", (supply_nodes, demand_nodes)};
        {:x, "lower_bound", 0.0}
    ]
    // Bring the variables into scope.
    with variables use x
 
    // Define the sense of the optimization problem and the objective function.
    def minimize = sum[transport_costs[s, d] * x[s, d] for s in supply_nodes, d in demand_nodes]
 
    // Define the sense of the optimization problem and the objective function.
    def minimize = sum[transport_costs[s, d] * x[s, d] for s in supply_nodes, d in demand_nodes]
 
    // Define the supply constraints.
    // For each supply node, the total quantity of goods transported out of it should not exceed the supply capacity of that node.
    def constraints:supply = foreach[s in supply_nodes : sum[x[s, d] for d in demand_nodes] ≼ supply[s]]
 
    // Define the demand constraints.
    // For each demand node, the total quantity of goods transported to it should be at least the demand of that node.
    def constraints:demand = foreach[d in demand_nodes : sum[x[s, d] for s in supply_nodes] ≽ demand[d]]
end
 
// Optimize the model.
def result = rel:mathopt:optimize[model, {}]
 
// Extract the result of the optimization process.
def output = rel:mathopt:extract_result[result, model:variables]

Was this doc helpful?