Mip Model

struct Column

A struct for representing a column in the network flow MIP model. Each column is indexed by a (partial) hyper-tree and a commodity.

struct CommodityFlowComponent

A struct for representing the flow component of a specific commodity within a network flow model.

Contains a JuMP implementation of:

• the arc and path flow variables and flow conservation constraints associated with the commodity;
• the flow demand and capacity constraints of the commodity.

struct NetworkFlowMipModel

A struct for representing a mixed-integer programming (MIP) model for network flow problems.

Fields

• mip_model::JuMP.Model: The JuMP model object for the MIP.
• problem::NetworkFlowModel.Problem: The network flow problem instance.
• commodity_to_flow_data::Dict{Commodity,CommodityFlowComponent}: A dictionary mapping commodities to their respective flow components.
• arc_to_capacity_constraint::Dict{NetworkFlowModel.Arc,JuMP.ConstraintRef}: A dictionary mapping arcs to their capacity constraints in the MIP model.
• side_constrs::Vector{JuMP.ConstraintRef}: A vector of additional side constraints added to the MIP model.
• dual_decimal_precision::Int: The precision used for the dual values retrieved from the JuMP model.

This struct is used to encapsulate all the components necessary to define and solve a MIP for a network flow problem, including the model itself, the problem data, constraints, and settings for numerical precision.

NetworkFlowMipModel(
    problem::NetworkFlowModel.Problem, 
    params::MipSolverParams
) -> NetworkFlowMipModel

Create a new mixed-integer programming (MIP) model for a network flow problem.

Returns

• NetworkFlowMipModel: A NetworkFlowMipModel instance with initialized MIP model, constraints, and variables.

AbstractSolver.solve(
    problem::NetworkFlowModel.Problem, 
    params::MipSolverParams;
    time_limit::Float64 = Inf
) -> PrimalSolution

Solve a network flow problem directly as a mixed-integer programming (MIP) model. Keyword parameter time_limit is given in seconds.

Returns

• A PrimalSolution object representing the optimal solution.

add_column!(flow_component::CommodityFlowComponent, column::Column)

Add a column to the CommodityFlowComponent if it does not already exist.

Returns a JuMP variable reference for the newly added column. Returns nothing if the variable already exists.

This function creates a variable, assigns it a cost coefficient in the objective function, and updates flow conservation and commodity flow constraints to include this variable.

add_column!(
    model::NetworkFlowMipModel,
    column::Column,
) -> Bool

Add a column/variable to the MIP model representing the flow of a commodity along a specific hyper-tree. The hyper-tree can represent a single hyper-arc, a partial hyper-tree, or a complete hyper-tree from the source to the sink of the commodity. The variable is added only if the hyper-tree is in the network of the problem and an equivalent variable does not already exist.

Returns

• true if the variable was successfully added, otherwise false.

delete_column!(flow_component::CommodityFlowComponent, column::Column)

Delete a column from the CommodityFlowComponent by setting the upper bound to 0 and removing it from assocaited data structures.

Note: setting the variable upper bound to 0 is more efficient than deleting the variable.

get_arc_flow_solution(flow_component::CommodityFlowComponent) -> ArcFlowSolution

Retrieve the flow solution for all arcs within the CommodityFlowComponent.

This function calculates the flow solution for each arc by rounding the value of the associated variable and aggregating the flow values from the path variables as well.

get_columns(flow_component::CommodityFlowComponent)

Return all columns that have been created in the CommodityFlowComponent.

get_columns(mip_model::NetworkFlowMipModel, commodity::Commodity) -> Vector{Column}

Get all columns associated with the given commodity.

get_dual_solution(model::NetworkFlowMipModel) -> DualSolution

Retrieve the dual solution from a solved NetworkFlowMipModel. Only works if the model is an LP model (all variables are linear).

get_flow_conservation_constraint!(
    flow_component::CommodityFlowComponent, vertex::Vertex
)

Retrieve or create a flow conservation constraint for a specified vertex within the CommodityFlowComponent.

Returns

• constraint::JuMP.ConstraintRef: The JuMP constraint reference for the flow conservation at the specified vertex.

This function ensures that there is a flow conservation constraint for each vertex. If the constraint does not exist, it is created with a default expression of 0.0 == 0.0.

get_primal_solution(model::NetworkFlowMipModel) -> PrimalSolution

Retrieve the primal solution from a solved MIP model

optimize!(model::NetworkFlowMipModel; time_limit::Float64 = Inf)

Optimize the MIP model associated with a network flow problem by calling JuMP.optimize!(). time_limit is given in seconds.

Returns

• nothing.