minimum_weight_perfect_bmatching(g, b[, w]; cutoff=Inf)

Given a graph g and an edgemap w containing the weights associated to each edge, returns the perfect b-matching with the minimum total weight.

A perfect b-matching M is a collection of edges in g such that every vertex has exactly b incident edges in M .

If w is not given, all edges will be considered to have weight one (results in max cardinality b-matching).

Edges e with no associated value in w or with w[e] > cutoff will not be considered for the matching.

The algorithm uses Linear Programming to solve the linear relaxation of the problem first, then eventually refines the solution with an Integer Programming solver.

The efficiency of the algorithm depends on the input graph:

• If the graph is bipartite, then the LP relaxation is integral.
• If the graph is not bipartite, then an IP may be required to refine the solution

and the computation time may grow exponentially.

The package JuMP.jl and one of its supported solvers are required.

Returns a tuple (status, W, match) containing:

• a solve status (indicating whether the problem was solved to optimality)
• the tototal weight W of the matching
• a vector of vectors match, where match[v] contains the b neighbors of v in the optimal matching.

Example

julia> g = CompleteGraph(30)
julia> w = EdgeMap(g, e -> rand())
julia> status, W, match = minimum_weight_perfect_bmatching(g, 2, w)

minimum_weight_perfect_matching(g, weights::AEdgeMap{T}; cutoff=typemax{T}) where {T<:Real}

Given a graph g and an edgemap weights containing non-negative weights associated to edges, returns a matching with the mimimum total weight among the ones containing exactly nv(g)/2 edges.

Edges in g not present in weights will not be considered for the matching. To reduce computational time, a cutoff argument can be given. Only edges with weight lower than cutoff will be considered for the matching.

This function relies on the BlossomV.jl package, a julia wrapper around Kolmogorov's BlossomV algorithm.

The return value is a NamedTuple object match with fields:

match.weight: total weight of the matching

match.mate:    `mate[i] = j` if vertex `i` is matched to vertex `j`.
               `mate[i] = -1` for unmatched vertices.

Example

g = random_regular_graph(30, 4)
w = EdgeMap(g, e -> rand())
match = minimum_weight_perfect_matching(g, w)
print(match.weight)
print(match.mate)

solve_tsp(g, w; cutoff=Inf)

Given a graph g and an edgemap w containing the weight associated to each edge, solves the Travelling Salesman Problem, returning the tour among all the cities with minimal total weight.

Edges e with no associated value in w or with w[e] > cutoff will not be considered for the optimal tour.

The algorithm uses a generic Integer Programming solver combined with a lazy constraint augmentation procedure.

The package JuMP.jl and one of its supported solvers are required.

Returns a tuple (status, W, tour) containing:

• a solve status (indicating whether the problem was solved to optimality)
• the tototal weight W of the tour
• a vector tour containing the sequence of vertices in the optimal tour.

Example

pos = rand(30, 2)
g = CompleteGraph(30)
w = EdgeMap(g, e -> norm(pos[src(e)] - pos[dst(e)]))
status, W, tour = solve_tsp(g, w)