Types

mutable struct BP_info

Mutable structure where extra information about the branch-and-price execution is stored

Fields

• LB::Float64: best primal value
• UB::Float64: best dual value
• nb_col_root::Int: number of columns generated at root node

mutable struct BP_params

Mutable structure where the options of the branch-and-price solver are stored

Fields

• optimizer::String: LP and IP solver that will be used to solve the master (default is HiGHS)
• verbose::Bool: true if messages are printed during the solution (default = true)
• is_pief::Bool: true if the chains are considered in the master model using a position-indexed extended edge formulation (default = false)
• fvs::Bool: true if a feedback vertex set is used to reduce the number of graph copies (default = true)
• reduce_vertices::Bool: true if we try deleting useless vertices in graph copies (default = true)
• is_column_disjoint::Bool: true if we require column disjoint columns at each column generation iteration (default = true)
• max_intersecting_columns::Int: true maximum number of generated columns covering each vertex (default = 6)
• is_tabu_list::Bool: true if we stop solving a subproblem as soon as it does not produce any positive cost column; this subproblem will be considered again when proving optimality (default = true)
• solve_master_IP::Bool: true if we solve the master IP to find feasible solutions (default = true)
• time_limit_master_IP::Float64: time limit (seconds) at each solution of the master IP (default = 10.0)
• freq_solve_master_IP::Int: number of new columns that must be added in the master IP between two solutions of this IP (default = 1)
• restart_for_IP::Bool: true if the root node can be solved twice to generate more columns when the IP master could not prove optimality of the relaxation value (default = true)
• nb_threads::Int: if the LP and IP solver can be called on multiple threads, specify the maximum number of threads that will be used.

mutable struct BP_status

Mutable structure where the results of the branch-and-price are stored

Fields

• bp_info::BP_info: extra info about the branch-and-price execution
• status::String: status of solution: ONGOING, OPTIMAL or TIMELIMIT
• objective_value::Float64: objective value of the best solution found
• relative_gap::Float64: final relative optimality gap
• best_cycles::Vector{Vector{Int}}: selected cycles in the best primal value
• best_chains::Vector{Vector{Int}}: selected chains in the best primal value
• node_count::Int: total number of branch-and-bound nodes explored during the solution proces
• solve_time::Float64: time spent in the solution process; this might be different from the specified time limit even if status is TIME_LIMIT, since parsing and preprocessing is counted in cpu time
• nb_cols_last_ip::Int: number of columns in the master IP at last solution

mutable struct Graph_copies

Mutable structure describing the copies of the graph: one copy per vertex or one copy per vertex of a feedback vertex set if the option is set. It is important to note that the copies related to altruist donors always appear first in the list of copies

Fields

• sources::Vector{Int}: source of each graph copy
• is_vertex_list::Vector{BitVector}: for each copy and each vertex, true if the vertex belongs to the copy
• d_to_vstar_list::Vector{Vector{Int}}: in each copy, distance from each vertex to the source
• d_from_vstar_list::Vector{Vector{Int}}: in each copy, distance from each vertex to the source
• nb_copies::Int: number of graph copies
• is_arc_list::Vector{BitVector}: for each copy and each arc index, true if the arc appears in the copy
• chain_mip::Model: shared MIP model that will be solved every time a chain subproblem needs to be solved to optimality

mutable struct Graph_info

struct Instance

Non-mutable structure describing the instance that is solved

Fields

• graph::SimpleDiGraph: graph describing compatibilities between pairs and with altruist donors
• vertex_weight::Vector{Float64}: weight of each vertex
• edge_weight::Matrix{Float64}: weight of each arc (0 if there is no arc)
• pairs::Vector{Int}: indices of the donor/patient pair vertices
• altruists::Vector{Int}: indices of the altruist donor vertices
• nb_pairs::Int: number of donor/patient pairs
• nb_altruists::Int: number of altruist donors
• max_cycle_length::Int: maximum length of a feasible exchange cycle
• max_chain_length::Int: maximum length of a feasible exchange chain
• is_vertex_weighted::Bool: true if all weights are actually on the vertices

mutable struct MIP_params

Mutable structure where the solving options of the compact formulation are stored

Fields

• optimizer::String: LP and IP solver that will be used to solve the master (default is HiGHS for IPs and LPs)
• verbose::Bool: true if messages are printed during the solution (default = true)
• model_type::Mip_model: type of MIP compact model that is to be solved (default = HPIEF)
• fvs::Bool: true if a feedback vertex set is used to reduce the number of graph copies (default = true)
• reduce_vertices::Bool: true if we try deleting useless arcs in graph copies (default = true)
• reduce_arcs::Bool: true if we try deleting useless arcs in graph copies (default = true)
• symmetry_break::Bool: true if the MIP model is modified to reduce the number of optimal solutions (default = true)
• nb_threads::Int: if the LP and IP solver can be called on multiple threads, specify the maximum number of threads that will be used.

Mip_model

Enumerated structure specifying the considered formulation when solving a compact formulation of the kidney exchange problem

Enumerate values

• HPIEF: Hybrid position-indexed extended formulation
• EXTENDED_EDGE: Cycles are handled with an extended edge formulation and chains are handled with position-indexed variables
• CYCLE_CUT: Cycles are handled with an extended edge formulation and chains are handled with cycle cuts to avoid long cycles
• RELAXED_ARC: Arc formulation where the size of cycles and chains are not considered

mutable struct PoolGenerator

Compatibility graph generator based on Saidman et al. (2006)

This is known colloquially as the "Saidman Generator".

mutable struct Solution_status

mutable struct Subgraph_info

struct VertexAltruist <: KidneyExchange.Vertex

struct VertexPair <: KidneyExchange.Vertex