Flow Generator

NetworkFlowProblemBuilder

This structure is used to build network flow problems. The builder allows the user to define a network with vertices, arcs, and commodities, and side constraints.

Usage

Creating a new instance of the builder:

builder = new_problem_builder()

Adding elements to the problem:

vertex = new_vertex!(builder)
arc = new_arc!(builder, vertex1, vertex2)
commodity = new_commodity!(builder, source_vertex, sink_vertex, demand, capacity)

Setting arc properties:

set_cost!(builder, arc, cost)
set_capacity!(builder, arc, capacity)
set_var_type!(builder, arc, var_type)

Defining a side-constraint:

constraint = new_constraint!(builder, lb, ub)
set_constraint_coefficient!(builder, constraint, arc, coefficient)

Once the problem is fully constructed, it can be converted into a NetworkFlowModel.Problem and optimized using an appropriate MIP solver:

problem = get_problem(builder)
solution = optimize!(problem, mip_solver)

Examples

builder = new_problem_builder()
v1 = new_vertex!(builder)
v2 = new_vertex!(builder)
v3 = new_vertex!(builder)
arc1 = new_arc!(builder, v1, v2; cost=5.0, capacity=10.0, var_type=CONTINUOUS)
arc2 = new_arc!(builder, v1, v2; var_type=INTEGER)
set_cost!(builder, arc2, 7.0)
commodity = new_commodity!(builder, v1, v3, 2.0, 10.0)
constraint = new_constraint!(builder, lb=9.0, ub=10.0
set_constraint_coefficient!(builder, constraint, arc1, 1.0)
set_constraint_coefficient!(builder, constraint, arc2, 2.0)
problem = get_problem(builder)
mip_solver = HiGHS.Optimizer
solution = optimize!(problem, mip_solver)

filter_arcs_by_reduced_cost(problem::Problem, mip_solver, cutoff::Number)

Remove arcs that are not good candidates to find a solution better than cutoff.

Returns the filtered problem.

get_arcs(network::Network)

Return the arcs in a network.

get_arcs(path::Path)

Return the arcs in a path. The arcs do not follow any particular order.

get_flow(solution::NetworkFlowModel.PrimalSolution, arc::Arc)

Return the total flow for a specific arc in the given solution.

get_flow(solution::NetworkFlowModel.PrimalSolution, commodity::Commodity, arc::Arc)

Return the flow for a specific commodity and arc in the given solution.

get_obj_val(problem::NetworkFlowModel.Problem, solution::NetworkFlowModel.PrimalSolution)

Return the objective value for the given problem and solution.

get_path_to_flow_map(
    problem::NetworkFlowModel.Problem,
    solution::NetworkFlowModel.PrimalSolution,
    commodity::Commodity,
)

Return the path to flow map for a specific commodity in the given solution.

get_problem(builder::NetworkFlowProblemBuilder)

Create a NetworkFlowModel.Problem based on the data given in NetworkFlowProblemBuilder.

new_arc!(
    builder::NetworkFlowProblemBuilder,
    tail_to_multiplier_map::Dict{Vertex,Float64},
    head::Vertex;
    cost::Float64 = 0.0,
    capacity::Float64 = Inf,
    var_type::VarType = CONTINUOUS,
)

Create a new (hyper-)arc in the network flow problem builder.

Note: VarType can be either CONTINUOUS or INTEGER

new_arc!(
    builder::NetworkFlowProblemBuilder,
    (tail, multiplier)::Tuple{Vertex,Float64},
    head::Vertex;
    cost::Float64 = 0.0,
    capacity::Float64 = Inf,
    var_type::VarType = CONTINUOUS,
)

Create a new arc in the network flow problem builder.

Note: VarType can be either CONTINUOUS or `INTEGER

new_arc!(
    builder::NetworkFlowProblemBuilder,
    tail::Vertex,
    head::Vertex;
    cost::Float64 = 0.0,
    capacity::Float64 = Inf,
    var_type::VarType = CONTINUOUS,
)

Create a new arc in the network flow problem builder.

Note: VarType can be either CONTINUOUS or INTEGER

new_commodity!(
    builder::NetworkFlowProblemBuilder,
    source::Vertex,
    sink::Vertex,
    demand::Number,
    capacity::Number;
    violation_penalty_cost::Number = 1e3,
)

Add a new commodity to the network flow problem builder.

new_constraint!(
    builder::NetworkFlowProblemBuilder;
    lb::Float64 = -Inf,
    ub::Float64 = Inf,
    violation_penalty_cost::Float64 = 1e3,
)

Create a new linear constraint and add it to the network flow problem builder.

Exceptions

• ArgumentError: If the lower bound is greater than the upper bound, or if the bounds are infeasible or unbounded.

new_problem_builder()

Create a new empty instance of NetworkFlowProblemBuilder.

new_vertex!(builder::NetworkFlowProblemBuilder)

Create a new vertex in the network flow problem builder.

optimize!(
    problem::NetworkFlowModel.Problem,
    mip_solver;
    initial_paths::Vector{Tuple{Commodity,Path}} = Tuple{Commodity,Path}[],
    obj_cutoff = Inf,
)

Optimize the network flow problem using FlowGenerator internal solver based on the specified MIP optimizer.

Returns a PrimalSolution object.

optimize!(
    problem::NetworkFlowModel.Problem,
    params::Parameters.AbstractSolverParams;
    initial_paths::Vector{Tuple{Commodity,Path}} = Tuple{Commodity,Path}[],
)

Optimize the network flow problem using the specified solver parameters.

Returns a PrimalSolution object.

optimize_by_mip_solver!(problem::NetworkFlowModel.Problem, mip_solver; time_limit::Float64 = 3600)

Optimize the network flow problem directly by an external MIP solver. Keyword parameter time_limit is given in seconds.

Returns a PrimalSolution object.

optimize_linear_relaxation!(problem::NetworkFlowModel.Problem, mip_solver; use_column_generation::Bool = false)

Optimize the network flow problem while ignoring all variable integrality constraints.

set_capacity!(builder::NetworkFlowProblemBuilder, arc::Arc, capacity::Float64)

Set the capacity of an arc in the network flow problem builder.

set_constraint_coefficient!(
    builder::NetworkFlowProblemBuilder,
    constraint::DoubleBoundedConstraint,
    arc::Arc,
    coeff::Float64,
)

Set the coefficient of an arc in a linear constraint in the network flow problem builder.

set_cost!(builder::NetworkFlowProblemBuilder, arc::Arc, cost::Float64)

Set the cost of an arc in the network flow problem builder.

set_var_type!(builder::NetworkFlowProblemBuilder, arc::Arc, var_type::VarType)

Set the variable type of an arc in the network flow problem builder.