GitHub

Network Flow Model

FlowGenerator.NetworkFlowModel.ArcFlowSolution — Type
struct ArcFlowSolution

A solution object for network flow problems that maps arcs to their flows.

Fields

  • arc_to_flow_map::Dict{Arc,Float64}: A dictionary that maps Arc objects to Float64 flow values.
  • source::Vertex: The source of the flow.
  • sink::Vertex: The destination of of the flow.

Constructor

ArcFlowSolution(c::Commodity)

Constructs an ArcFlowSolution with an empty flow map and specified source and sink vertices based on a given Commodity.

source
FlowGenerator.NetworkFlowModel.Problem — Type
struct Problem

Encapsulates the data needed to define and solve a network flow optimization problem.

Fields

  • network::Network: Represents the flow network with nodes and arcs.
  • objective_function::ObjectiveFunction: A linear function defining the objective of the optimization.
  • arc_to_capacity_map::IndexedMap{Arc,Float64}: A mapping from arcs to their capacities.
  • arc_to_var_type_map::IndexedMap{Arc,VarType}: A mapping from arcs to their variable types, either INTEGER or CONTINUOUS.
  • constraints::Vector{Constraint}: A vector of generic linear side-constraints.
  • commodities::Vector{Commodity}: A vector of commodities to be sent through the network.
  • arc_to_side_constr_coeffs::LinkedListMap{Tuple{Int,Float64}}: An auxiliary mapping for side constraints coefficients for enhanced solution computation. To be computed by constructors.

Constructors

  • Problem(network, arc_to_cost, arc_to_capacity, arc_to_var_type, constraints, commodities): Constructs a Problem instance given network parameters and functions to define arc costs, capacities, variable types, constraints, and commodities.
  • Problem(problem, network): Constructs a new Problem instance based on an existing problem but with a different network structure.

Methods

  • get_network(problem): Returns the network of the problem.
  • get_arcs(problem): Returns the arcs of the problem's network.
  • get_vertices(problem): Returns the vertices of the problem's network.
  • get_constraints(problem): Returns the constraints of the problem.
  • get_commodities(problem): Returns the commodities of the problem.
  • get_cost(problem, arc): Returns the cost of an arc.
  • get_cost(problem, path): Returns the cost of a path.
  • get_capacity(problem, arc): Returns the capacity of an arc.
  • get_var_type(problem, arc): Returns the variable type of an arc.
  • get_constr_coeff_list(problem, arc): Returns the list of constraint coefficients for an arc.
  • push_constraint!(problem, constraint): Adds a new constraint to the problem.
  • pop_constraint!(problem): Removes the most recently added constraint from the problem.
  • _get_arc_to_side_constr_coeffs(arcs, constraints): Internal function to initialize the mapping of arcs to their side constraint coefficients.
  • is_problem_integer(problem): Returns true if the objective is integer for any feasible solution satisfying integrality constraints.
  • filter_arcs(problem, pred): Returns a new instance of Problem where only the arcs satisfying the predicate pred are kept.
source
FlowGenerator.NetworkFlowModel.VarType — Type
@enum VarType

An Enum type representing different variable types for arcs in a flow network problem.

Values

  • INTEGER: Indicates that the variable is restricted to integer values.
  • CONTINUOUS: Indicates that the variable can take any continuous real value.
source
Base.in — Method

Base.in(arc::Arc, network::Network)

Check if an arc is in the network.

source
Base.in — Method

Base.in(hyper_tree::HyperTree, network::Network)

Check if a hyper-tree is in the network.

source
Base.in — Method

Base.in(path::Path, network::Network)

Check if a path is in the network.

source
FlowGenerator.NetworkFlowModel.filter_arcs — Method
filter_arcs(problem::Problem, predicate::Function) -> Problem

Creates a new Problem instance by filtering out arcs in the original problem's network that do not satisfy a given predicate function.

source
FlowGenerator.NetworkFlowModel.find_path — Method
find_path(network::Network, source::Vertex, sink::Vertex, arc_to_flow::Function)

Returns a path from source to sink in a network with positive flow capacity. If no such path exists, returns nothing.

source
FlowGenerator.NetworkFlowModel.get_arc_reduced_cost — Method
get_arc_reduced_cost(problem::Problem, dual_solution::DualSolution, arc::Arc; capacity_dual = get_arc_capacity_dual(problem, dual_solution, arc))

Get the reduced cost of an arc based on the dual solution. The reduced cost is computed based on side constraint and capacity dual values, but not on commodity and flow conservation dual values.

source
FlowGenerator.NetworkFlowModel.get_obj_val — Method
get_obj_val(problem::Problem, solution::PrimalSolution)

Calculate the objective value of a primal solution for a given problem. The objective consists of: flow cost and constraint/commodity violation penalty costs

source
FlowGenerator.NetworkFlowModel.is_flow_conservation_feasible — Method
is_flow_conservation_feasible(sol::ArcFlowSolution)

Checks if flow conservation is feasible for an ArcFlowSolution.

Flow conservation is feasible if the flow conservation balance of all intermediate nodes is zero

Returns

  • true if flow conservation is feasible, false otherwise.
source