API for MinimumWeightTwoStageSpanningTree.jl

benders_decomposition(inst::TwoStageSpanningTreeInstance;
    MILP_solver=GLPK.Optimizer,
    tol=0.000001,
    silent=false,
)

Computes an optimal solution (with tolerance tol) of the two stage spanning tree problem using a Benders approach.

build_solve_and_encode_instance_as_maximum_weight_forest(;
    grid_size=3,
    seed=0,
    nb_scenarios=10,
    first_max=10,
    second_max=20,
    solver=lagrangian_heuristic_solver,
    load_and_save=true
)

Builds a two stage spanning tree instance with a square grid graph of width grid_size, seed for the random number generator, nb_scenarios for the second stage, first_max and second_max as first and second stage maximum weight.

Solves it with solver.

Encodes it for a pipeline with a maximum weight forest layer.

column_generation(inst::TwoStageSpanningTreeInstance;MILP_solver=GLPK.Optimizer,tol=0.00001)

Solves the dual of the linear relaxation of the two stage spanning tree MILP using a constraint generation.

Returns objective_value, duals

cut_generation(inst::TwoStageSpanningTreeInstance;
    MILP_solver=GLPK.Optimizer,
    separate_constraint_function=separate_forest_polytope_constraint_vertex_set_using_min_cut_MILP_formulation!,
    tol=0.000001,
    silent=false,
)

Solve the TwoStageSpanningTree instance inst using a cut generation approach.

separate_constraint_function indicates which method is used to separate the constraint on subsets of vertices. Two options are available

• separate_forest_polytope_constraint_vertex_set_using_min_cut_MILP_formulation!
• separate_forest_polytope_constraint_vertex_set_using_simple_MILP_formulation!

evaluate_first_stage_solution(inst::TwoStageSpanningTreeInstance, forest)

Returns the value of the solution of inst with forest as first stage solution.

kruskal_maximum_weight_forest(θ::AbstractVector;inst=inst)

Return a maximum weight forest on inst.g using θ as edge weight (returns a vector of edges)

lagrangian_relaxation(inst::TwoStageSpanningTreeInstance; nb_epochs=100)

Runs

• a subgradient algorithm during nb_epochs to solve the Lagrangian relaxation of inst (with θ initialized to 0)
• a lagrangian heuristic on the resulting solution

Returns lb, ub, forest, θ, training_losses with

• lb: value of the Lagrangian relaxation
• ub: value of the solution computed by the lagrangian heuristic
• forest: solution computed by the lagrangian heuristic
• θ: second stage problem value
• training_losses: vector with the value of the training losses along the subgradient algorithm

maximum_weight_forest_linear_maximizer(θ::AbstractVector;inst=inst)

Wrapper around kruskalmaximumweightforest(edgeweights_vector::AbstractVector, inst::TwoStageSpanningTreeInstance) that returns the solution encoded as a vector.

TwoStageSpanningTreeInstance

Contains all the relevant information defining a two stage spanning-tree instance.

Fields

• g::SimpleGraph{Int}: the graph
• edge_index::SparseMatrixCSC{Int64, Int64}: edge_index[src(e),dst(e)] contains the index of edge e
• nb_scenarios::Int: number of scenarios
• first_stage_weights_matrix::SparseMatrixCSC{Float64, Int64}:
• first_stage_weights_vector::Vector{Float64}:
• second_stage_weights::Vector{SparseMatrixCSC{Float64, Int64}}:

TwoStageSpanningTreeInstance(g::AbstractGraph;nb_scenarios=1, first_max=10, second_max=20)

Build a random TwoStageSpanningTreeInstance from graph g.

nb_scenarios scenarios are drawn, with first-stage weights drawn uniformly between 0 and first_max, and second-stage weights drawn uniformly between 0 an dsecond_max.

function build_flow_graph_for_constraint_pricing!(
    g::MetaGraph,
    flow_graph::MetaDiGraph,
    base_graph_vertices_vertex_index_in_flow_graph = Dict(),
    base_graph_edges_vertex_index_in_flow_graph = Dict()
)

Constraint separated: ∑{e in E(X)}xe <= |X| - 1 for any ∅ ⊊ X ⊊ V`

• g is the undirected graph on which the forest polytope is manipulated.
• flow_graph is a MetaDiGraph. It should be empty in input. It is modified by the function and contains afterwards the MetaDiGraph used to separate the forest polytope constraint on f

build_load_or_solve(;
    graph=grid(5,5),
    seed=0,
    nb_scenarios=10,
    first_max=10,
    second_max=20,
    solver=lagrangian_heuristic_solver,
    load_and_save=true
)

Three solvers available

• cut_solver
• benders_solver
• lagrangian_heuristic_solver

Return inst, val, sol with:

• inst: the instance generated
• val: value of the solution computed
• solution_computed: solution computed

function edge_index(inst::TwoStageSpanningTreeInstance, e::AbstractEdge)

Returns inst.edge_index[src(e),dst(e)].

kruskal_mst_value(g, distmx=weights(g); minimize=true)

extends kruskal_mst to return also the mst value

returns (mst weight), (mst edges)

kruskal_on_first_scenario_instance(instance::TwoStageSpanningTreeInstance)

Applies Kruskal algorithm with weight inst.firststageweights + inst.secondstageweights[1]

Return value, firststagevalue, firststagesolution

lagrangian_dual(θ::AbstractArray; inst::TwoStageSpanningTreeInstance)

Compute the value of the lagrangian dual function for TwoStageSpanningTreeInstance instance inst with duals θ

θ[edged_index(src(e),dst(e)),s] contains the value of the Lagrangian dual corresponding to edge e for scenario s

ChainRulesCore.rrule automatic differentiation with respect to θ works.

Return (value of the solution computed),(edges in the solution computed)

lagrangian_heuristic(θ::AbstractArray; inst::TwoStageSpanningTreeInstance)

Performs a lagrangian heuristic on TwoStageSpanningTree instance inst with duals θ.

θ[edge_index(src(e),dst(e)),s] contains the value of the Lagrangian dual corresponding to edge e for scenario s.

Return (value of the solution computed),(edges in the solution computed).

maximum_weight_forest_layer_linear_encoder(inst::TwoStageSpanningTreeInstance)

Returns X::Array{Float64} with X[f,edge_index(inst,e),s] containing the value of feature number f for edge e and scenario s

Features used: (all are homogeneous to a cost)

• first_stage_cost
• second_stage_cost_quantile
• best_stage_cost_quantile
• neighbors_first_stage_cost_quantile
• neighbors_scenario_second_stage_cost_quantile
• is_in_first_stage_x_first_stage_cost
• is_in_second_stage_x_second_stage_cost_quantile
• is_first_in_best_stage_x_best_stage_cost_quantile
• is_second_in_best_stage_x_best_stage_cost_quantile

For features with quantiles, the following quantiles are used: 0:0.1:1.

separate_forest_polytope_constraint_vertex_set_using_min_cut_MILP_formulation!(g::MetaGraph; MILP_solver=GLPK.Optimizer)

Uses a simple MILP to separate the constraints Constraint separated: ∑{e in E(X)} xe <= |X| - 1 for any ∅ ⊊ X ⊊ V`

• g is a MetaGraph, :cb_val property contains the value of x_e

returns: found, X

• found : boolean indicating if a violated constraint has been found
• X : vertex set corresponding to the violated constraint

separate_mst_Benders_cut!(g::MetaGraph ; MILP_solver=GLPK.Optimizer)

separates optimality and feasibility cuts for the Benders decomposition formulation of the MST problem

input: property :x_val contains the value of the master property :weight contains the value of the second stage

returns a boolean equals to true if the cut is a feasibility cut and false if it is an optimality cut (in that case, the cut might be satisfied)

The value of the duals μ and ν are stored in properties :mu and :nu of the g