Max Cut

Problem Definition

Max Cut problem is defined on weighted graphs. The goal is to find a partition of the vertices into two sets such that the sum of the weights of the edges between the two sets is maximized.

Interfaces

To initialize a MaxCut, we need to specify the graph and the weights of the edges.

julia> using ProblemReductions, Graphs
julia> g = SimpleGraph(3){3, 0} undirected simple Int64 graph
julia> for (i,j) in [(1,2),(1,3),(2,3)]
           add_edge!(g,i,j)
       end # Add edges on the graph
julia> maxcut = MaxCut(g,[1,2,3]) # specify the weights of the edgesMaxCut{Vector{Int64}}(SimpleGraph{Int64}(3, [[2, 3], [1, 3], [1, 2]]), [1, 2, 3])

Here the graph is a simple graph with 3 vertices and 3 edges. The weights of the edges are [1,2,3].

Required functions and optional functions: set_parameters, num_variables are implemented for this model.

julia> mc = set_parameters(maxcut, [2,1,3]) # set the weights and get a new instanceMaxCut{Vector{Int64}}(SimpleGraph{Int64}(3, [[2, 3], [1, 3], [1, 2]]), [2, 1, 3])
julia> num_variables(maxcut) # return the number of vertices3