Network Models
Connection
OperationsResearchModels.Network.Connection — Type
ConnectionDescription
A structure to hold a directed connection between two nodes in a network.
Fields
from::Int64: The starting node of the connection.to::Int64: The ending node of the connection.value::Real: The value associated with the connection (e.g. distance, time, capacity).
Example
# Create a connection from node 1 to node 2 with a distance of 5 kms.
conn = Connection(1, 2, 5)ShortestPathProblem
OperationsResearchModels.ShortestPath.ShortestPathProblem — Type
ShortestPathProblemDescription
Defines the shortest path problem.
Fields
connections::Vector{Connection}: The connections (edges) in the network.
Shortest Path
OperationsResearchModels.solve — Method
solve(problem)Description
Solves a shortest path problem given by an object of in type ShortestPathProblem.
Arguments
problem::ShortestPathProblem: The problem in type of ShortestPathProblem
Output
ShortestPathResult: The custom data type that holds path and cost.
Example
conns = [
Connection(1, 2, 3),
Connection(1, 3, 2),
Connection(1, 4, 4),
Connection(2, 5, 3),
Connection(3, 5, 1),
Connection(3, 6, 1),
Connection(4, 6, 2),
Connection(5, 7, 6),
Connection(6, 7, 5),
]
result = solve(ShortestPathProblem(conns))
println(result.path)
# 3-element Vector{Connection}:
# Connection(1, 3, 2)
# Connection(3, 6, 1)
# Connection(6, 7, 5)
println(result.cost)
# 8.0In this function it's assumed that the problem has a unique start and finish node. A heuristic approach is used to find the start and finish nodes. If a node has only outcoming connections, it is considered the start node. If a node has only incoming connections, it is considered the finish node. Of course a network can have multiple start and finish nodes, but this heuristic simplifies the problem. Future implementations could explore more complex scenarios with multiple start and finish nodes.
ShortestPathResult
OperationsResearchModels.ShortestPath.ShortestPathResult — Type
ShortestPathResultDescription
A structure to hold the result of the shortest path problem.
Fields
path::Vector{Connection}: The connections (edges) in the shortest path.cost::Float64: The total cost of the shortest path.model::JuMP.Model: The JuMP model used to solve the problem.
Maximum Flow Problem
OperationsResearchModels.MaximumFlow.MaximumFlowProblem — Type
MaximumFlowProblemDescription
Defines the maximum flow problem.
Fields
connections::Vector{Connection}: The connections (edges) in the network.
See also MaximumFlowResult, solve(::MaximumFlowProblem)
Maximum Flow
OperationsResearchModels.solve — Method
solve(problem)Description
Solves a maximum flow problem given by an object of in type MaximumFlowProblem.
Arguments
problem::MaximumFlowProblem: The problem in type of MaximumFlowProblem
Output
MaximumFlowResult: The custom data type that holds path and flow.
Example
conns = [
Connection(1, 2, 3),
Connection(1, 3, 2),
Connection(1, 4, 4),
Connection(2, 5, 3),
Connection(3, 5, 1),
Connection(3, 6, 1),
Connection(4, 6, 2),
Connection(5, 7, 6),
Connection(6, 7, 5),
];
problem = MaximumFlowProblem(conns)
result = solve(problem);
println(result.path)
println(result.flow)In this function it's assumed that the problem has a unique start and finish node. A heuristic approach is used to find the start and finish nodes. If a node has only outcoming connections, it is considered the start node. If a node has only incoming connections, it is considered the finish node. Of course a network can have multiple start and finish nodes, but this heuristic simplifies the problem. Future implementations could explore more complex scenarios with multiple start and finish nodes.
See also MaximumFlowProblem, MaximumFlowResult
MaximumFlowResult
OperationsResearchModels.MaximumFlow.MaximumFlowResult — Type
MaximumFlowResultDescription
A structure to hold the result of the maximum flow problem.
Fields
path::Vector{Connection}: The connections (edges) in the flow path.flow::Float64: The total flow through the network.model::JuMP.Model: The JuMP model used to solve the problem.
MinimumCostFlowProblem
OperationsResearchModels.MinimumCostFlow.MinimumCostFlowProblem — Type
MinimumCostFlowProblemDescription
Defines the minimum cost flow problem.
Fields
connections::Vector{Connection}: The connections (edges) in the network.costs::Vector{Connection}: The costs associated with each connection.
See also MinimumCostFlowResult, solve(::MinimumCostFlowProblem)
Minimum Cost Flow
OperationsResearchModels.solve — Method
solve(problem)Description
This function solves the Minimum Cost Flow problem by first solving the Maximum Flow problem and then using the flow value to solve the Minimum Cost Flow problem.
Arguments
problem::MinimumCostFlowProblem: The problem in type of MinimumCostFlowProblem
In this function it's assumed that the problem has a unique start and finish node. A heuristic approach is used to find the start and finish nodes. If a node has only outcoming connections, it is considered the start node. If a node has only incoming connections, it is considered the finish node. Of course a network can have multiple start and finish nodes, but this heuristic simplifies the problem. Future implementations could explore more complex scenarios with multiple start and finish nodes.
OperationsResearchModels.solve — Method
solve(problem, flow)Description
This function solves the Minimum Cost Flow problem given a flow value.
Arguments
problem::MinimumCostFlowProblem: The problem in type of MinimumCostFlowProblemflow::Float64: The flow value to be used in the problem.
See also MinimumCostFlowProblem, MinimumCostFlowResult
MinimumCostFlowResult
OperationsResearchModels.MinimumCostFlow.MinimumCostFlowResult — Type
MinimumCostFlowResultDescription
A structure to hold the result of the minimum cost flow problem.
Fields
path::Vector{Connection}: The connections (edges) in the flow path.cost::Float64: The total cost of the flow.model::JuMP.Model: The JuMP model used to solve the problem.
See also MinimumCostFlowProblem, solve(::MinimumCostFlowProblem)
MstProblem
OperationsResearchModels.MinimumSpanningTree.MstProblem — Type
MstProblemDescription
Defines the minimum spanning tree problem.
Fields
data::Union{Vector{Connection}, AbstractMatrix{<:Real}}: The data representing the network. It can be either a vector of connections or a distance matrix.
The Connection object defines a directed edge, but for the minimum spanning tree problem, the edges are considered undirected.
See also MstResult, solve(::MstProblem)
Minimum Spanning Tree
OperationsResearchModels.solve — Method
solve(problem::MstProblem)Description
Obtains the minimum spanning tree.
Arguments
problem::MstProblem: The problem in type of MstProblem
Output
::MstResult: A MstResult object that holds the results.
Details
- This function uses Prim's algorithm to find the minimum spanning tree. It tracks each unvisited node's nearest connection to the growing tree and updates only the connections adjacent to each newly selected node.
Examples
conns = Connection[
Connection(1, 2, 10),
Connection(2, 3, 10),
Connection(3, 4, 10),
Connection(1, 4, 10)
]
result = solve(MstProblem(conns))
MstResult(Connection[Connection(3, 4, 10), Connection(1, 4, 10), Connection(2, 3, 10)], 30.0)
println(result.distance)
println(result.connections)See also MstResult, solve(::MstProblem)
MstResult
OperationsResearchModels.MinimumSpanningTree.MstResult — Type
MstResultDescription
A structure to hold the result of the minimum spanning tree problem.
Fields
connections::Vector{Connection}: The connections (edges) in the minimum spanning tree.distance::Float64: The total distance (weight) of the minimum spanning tree.
See also MstProblem, solve(::MstProblem)