Edit on GitHub

Mincut

Doc is still in construction. Please check mincut.jl in ConstraintModels.jl for details on the implementation.

Constructing a Mincut model

Note that the Interdiction Cut problem is NP-hard.

ConstraintModels.mincut — Function
mincut(graph::AbstractMatrix{T}; source::Int, sink::Int, interdiction::Int = 0) where T <: Number

Compute the minimum cut of a graph.

Arguments:

  • graph: Any matrix <: AbstractMatrix that describes the capacities of the graph
  • source: Id of the source node; must be set
  • sink: Id of the sink node; must be set
  • interdiction: indicates the number of forbidden links