API

struct TwoStageSpanningTreeInstance{T}

Fields

• graph::Graphs.SimpleGraphs.SimpleGraph{Int64}: Graph

• first_stage_costs::Vector: First stage costs for each edge

• second_stage_costs::Matrix: Second stage costs for each edge and scenario [e, s]

struct TwoStageSpanningTreeSolution

Fields

• y::BitVector

• z::BitMatrix

MILP_separation_problem(graph, weights; MILP_solver, tol)

Solve the separation problem using the MILP formulation.

anticipative_solution(
    instance::TwoStageSpanningTreeInstance
) -> NamedTuple{(:value, :y, :z), <:Tuple{Any, Any, Any}}
anticipative_solution(
    instance::TwoStageSpanningTreeInstance,
    scenario::Int64
) -> NamedTuple{(:value, :y, :z), <:Tuple{Any, Any, Any}}

Compute an anticipative solution for given scenario.

benders_decomposition(
    instance::TwoStageSpanningTreeInstance;
    MILP_solver,
    tol,
    verbose
) -> TwoStageSpanningTreeSolution

Returns the optimal solution using a Benders decomposition algorithm.

column_generation(
    instance;
    MILP_solver,
    tol,
    verbose
) -> NamedTuple{(:value, :ν, :μ, :columns), <:Tuple{Union{Float64, Vector{Float64}}, Vector{Float64}, Any, Vector{BitVector}}}

Solves the linear relaxation using a column generation algorithm.

column_heuristic(
    instance;
    MILP_solver,
    verbose
) -> TwoStageSpanningTreeSolution

Column generation heuristic, that solves the linear relaxation and then outputs the solution of the proble restricted to selected columns. Returns an heuristic solution.

cut_generation(
    instance::TwoStageSpanningTreeInstance;
    separation_problem,
    MILP_solver,
    verbose
) -> TwoStageSpanningTreeSolution

Returns the optimal solution using a cut generation algorithm with custom separation problem solver.

cut_separation_problem(
    graph,
    weights;
    MILP_solver,
    tol
) -> Tuple{Any, Any, Any}

Solve the separation problem using the min cut formulation.

is_feasible(
    solution::TwoStageSpanningTreeSolution,
    instance::TwoStageSpanningTreeInstance;
    verbose
) -> Bool

Check if a given solution is feasible for given instance.

kruskal(
    g::Graphs.AbstractGraph,
    weights::AbstractVector;
    minimize
) -> NamedTuple{(:value, :tree), <:Tuple{Any, Any}}

Kruskal's algorithm. Same as Graphs.kruskal_mst, but also returns the value of the tree, and a binary vector instead of a vecror of edges.

lagrangian_relaxation(
    inst::TwoStageSpanningTreeInstance;
    nb_epochs,
    stop_gap
) -> Tuple{TwoStageSpanningTreeSolution, NamedTuple{(:lb, :ub, :best_theta, :lb_history, :ub_history), <:Tuple{Any, Any, Matrix{Float64}, Vector{Float64}, Vector{Float64}}}}

Return an heuristic solution using a combination of lagarngian relaxation and lagrangian heuristic.

nb_scenarios(
    instance::TwoStageSpanningTreeInstance
) -> Int64

Return the number of scenarios of instance.

plot_grid_graph(graph, n, m, weights=nothing)

Arguments

• graph: grid graph to plot
• n: n dimension
• m: m dimension
• weights: edge weights to display (optional)

plot_scenario(
    solution::TwoStageSpanningTreeSolution,
    instance::TwoStageSpanningTreeInstance,
    scenario;
    show_node_indices,
    δ,
    δ₂,
    n,
    m
)

Plot the two-stage tree from solution for requested scenario.

solution_from_first_stage_forest(
    forest::BitVector,
    instance::TwoStageSpanningTreeInstance
) -> TwoStageSpanningTreeSolution

Return the associated two-stage solution from given first stage forest and instance.

solution_value(
    solution::TwoStageSpanningTreeSolution,
    instance::TwoStageSpanningTreeInstance
) -> Any

Compute the objective value of given solution for given instance.