Class KolmogorovWeightedPerfectMatching<V,E>
 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Implemented Interfaces:
MatchingAlgorithm<V,
E>
KolmogorovWeightedMatching
Let $G = (V, E, c)$ be an undirected graph with a realvalued cost function defined on it. A matching is an edgedisjoint subset of edges $M \subseteq E$. A matching is perfect if $2M = V$. In the weighted perfect matching problem the goal is to maximize or minimize the weighted sum of the edges in the matching. This class supports pseudographs, but a problem on a pseudograph can be easily reduced to a problem on a simple graph. Moreover, this reduction can heavily influence the running time since only an edge with a maximum or minimum weight between two vertices can belong to the matching in the corresponding optimization problems. Currently, users are responsible for doing this reduction themselves before invoking the algorithm.
Note that if the graph is unweighted and dense, SparseEdmondsMaximumCardinalityMatching
may be a better choice.
For more information about the algorithm see the following paper: Kolmogorov, V. Math. Prog. Comp. (2009) 1: 43. https://doi.org/10.1007/s1253200900028, and the original implementation: http://pub.ist.ac.at/~vnk/software/blossom5v2.05.src.tar.gz
The algorithm can be divided into two phases: initialization and the main algorithm. The initialization phase is responsible for converting the specified graph into the form convenient for the algorithm and for finding an initial matching to speed up the main part. Furthermore, the main part of the algorithm can be further divided into primal and dual updates. The primal phases are aimed at augmenting the matching so that the value of the objective function of the primal linear program increases. Dual updates are aimed at increasing the objective function of the dual linear program. The algorithm iteratively performs these primal and dual operations to build alternating trees of tight edges and augment the matching. Thus, at any stage of the algorithm the matching consists of tight edges. This means that the resulting perfect matching meets complementary slackness conditions, and is therefore optimal.
At construction time the set of options can be specified to define the strategies used by the
algorithm to perform initialization, dual updates, etc. This can be done with the
BlossomVOptions
. During the construction time the objective sense of the optimization
problem can be specified, i.e. whether to maximize of minimize the weight of the resulting
perfect matching. Default objective sense of the algorithm is to minimize the weight of the
resulting perfect matching. If the objective sense of the algorithm is to maximize the weight of
the matching, the problem is reduced to minimum weight perfect matching problem by multiplying
all edge weights by $1$. This class supports retrieving statistics for the algorithm
performance, see getStatistics()
. It provides the time
elapsed during primal operations and dual updates, as well as the number of these primal
operations performed.
The solution to a weighted perfect matching problem instance comes with a certificate of
optimality, which is represented by a solution to a dual linear program; see
KolmogorovWeightedPerfectMatching.DualSolution
. This class encapsulates a mapping from the node sets of odd cardinality to
the corresponding dual variables. This mapping doesn't contain the sets whose dual variables are
$0$. The computation of the dual solution is performed lazily and doesn't affect the running time
of finding a weighted perfect matching.
Here we describe the certificates of optimality more precisely. Let the graph $G = (V, E)$ be an undirected graph with cost function $c: V \mapsto \mathbb{R}$ defined on it. Let $\mathcal{O}$ be the set of all subsets of $V$ of odd cardinality containing at least 3 vertices, and $\delta(S), S \subset V$ be the set of boundary edges of $V$. Then minimum weight perfect matching problem has the following linear programming formulation: \[ \begin{align} \mbox{minimize} \qquad & \sum_{e\in E}c_e \cdot x_e &\\ s.t. \qquad & \sum_{e\in \delta^(i)} x_e = 1 & \forall i\in V\\ & \sum_{e\in \delta(S)}x_e \ge 1 & \forall S\in \mathcal{O} \\ & x_e \ge 0 & \forall e\in E \end{align}\] The corresponding dual linear program has the following form: \[ \begin{align} \mbox{maximize} \qquad & \sum_{x \in V}y_e &\\ s.t. \qquad & y_u + y_v + \sum_{S\in \mathcal{O}: e \in \delta(S)}y_S \le c_e & \forall\ e = \{u, v\}\in E\\ & x_S \ge 0 & \forall S\in \mathcal{O} \end{align} \] Let's use the following notation: $slack(e) = c_e  y_u  y_v  \sum_{S\in \mathcal{O}: e \in \delta(S)}y_S$. Complementary slackness conditions have the following form: \[ \begin{align} slack(e) > 0 &\Rightarrow x_e = 0 \\ y_S > 0 &\Rightarrow \sum_{e\in \delta(S)}x_e = 1 \end{align} \] Therefore, the slacks of all edges will be nonnegative and the slacks of matched edges will be $0$.
The maximum weight perfect matching problem has the following linear programming formulation: \[ \begin{align} \mbox{maximize} \qquad & \sum_{e\in E}c_e \cdot x_e &\\ s.t. \qquad &\sum_{e\in \delta^(i)} x_e = 1 & \forall i\in V\\ & \sum_{e\in \delta(S)}x_e \ge 1 & \forall S\in \mathcal{O} \\ & x_e \ge 0 & \forall e\in E \end{align} \] The corresponding dual linear program has the following form: \[ \begin{align} \mbox{minimize} \qquad & \sum_{x \in V}y_e &\\ s.t. \qquad & y_u + y_v + \sum_{S\in \mathcal{O}: e \in \delta(S)}y_S \ge c_e & \forall\ e = \{u, v\}\in E\\ & x_S \le 0 & \forall S\in \mathcal{O} \end{align} \] Complementary slackness conditions have the following form: \[ \begin{align} slack(e) < 0 &\Rightarrow x_e = 0 \\ y_S < 0 &\Rightarrow \sum_{e\in \delta(S)}x_e = 1 \end{align} \] Therefore, the slacks of all edges will be nonpositive and the slacks of matched edges will be $0$.
This class supports testing the optimality of the solution via
testOptimality()
. It also supports retrieval of the
computation error when the edge weights are real values via
getError()
. Both optimality test and error computation
are performed lazily and don't affect the running time of the main algorithm. If the problem
instance doesn't contain a perfect matching at all, the algorithm doesn't find a minimum weight
maximum matching; instead, it throws an exception.
 Author:
 Timofey Chudakov
 See Also:

KolmogorovWeightedMatching
BlossomVPrimalUpdater
BlossomVDualUpdater

Nested Class Summary
Modifier and TypeClassDescriptionstatic class
A solution to the dual linear program formulated on thegraph
static class
Describes the performance characteristics of the algorithm and numeric data about the number of performed dual operations during the main phase of the algorithmNested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm
MatchingAlgorithm.Matching<V,
E>, MatchingAlgorithm.MatchingImpl<V, E> 
Field Summary
Modifier and TypeFieldDescriptionstatic final BlossomVOptions
Default optionsstatic final double
Default epsilon used in the algorithmstatic final double
Default infinity value used in the algorithmstatic final double
Defines the threshold for throwing an exception about no perfect matching existenceFields inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm
DEFAULT_EPSILON

Constructor Summary
ConstructorDescriptionKolmogorovWeightedPerfectMatching
(Graph<V, E> graph) Constructs a new instance of the algorithm using the default options.KolmogorovWeightedPerfectMatching
(Graph<V, E> graph, BlossomVOptions options) Constructs a new instance of the algorithm with the specifiedoptions
.KolmogorovWeightedPerfectMatching
(Graph<V, E> graph, BlossomVOptions options, ObjectiveSense objectiveSense) Constructs a new instance of the algorithm with the specifiedoptions
.KolmogorovWeightedPerfectMatching
(Graph<V, E> graph, ObjectiveSense objectiveSense) Constructs a new instance of the algorithm using the default options. 
Method Summary
Modifier and TypeMethodDescriptionReturns the computed solution to the dual linear program with respect to the weighted perfect matching linear program formulation.double
getError()
Computes the error in the solution to the dual linear program.Computes and returns a weighted perfect matching in thegraph
.Returns the statistics describing the performance characteristics of the algorithm.boolean
Performs an optimality test after the perfect matching is computed.

Field Details

EPS
public static final double EPSDefault epsilon used in the algorithm See Also:

INFINITY
public static final double INFINITYDefault infinity value used in the algorithm See Also:

NO_PERFECT_MATCHING_THRESHOLD
public static final double NO_PERFECT_MATCHING_THRESHOLDDefines the threshold for throwing an exception about no perfect matching existence See Also:

DEFAULT_OPTIONS
Default options


Constructor Details

KolmogorovWeightedPerfectMatching
Constructs a new instance of the algorithm using the default options. The goal of the constructed algorithm is to minimize the weight of the resulting perfect matching. Parameters:
graph
 the graph for which to find a weighted perfect matching

KolmogorovWeightedPerfectMatching
Constructs a new instance of the algorithm using the default options. The goal of the constructed algorithm is to maximize or minimize the weight of the resulting perfect matching depending on themaximize
parameter. Parameters:
graph
 the graph for which to find a weighted perfect matchingobjectiveSense
 objective sense of the algorithm

KolmogorovWeightedPerfectMatching
Constructs a new instance of the algorithm with the specifiedoptions
. The objective sense of the constructed algorithm is to minimize the weight of the resulting matching Parameters:
graph
 the graph for which to find a weighted perfect matchingoptions
 the options which define the strategies for the initialization and dual updates

KolmogorovWeightedPerfectMatching
public KolmogorovWeightedPerfectMatching(Graph<V, E> graph, BlossomVOptions options, ObjectiveSense objectiveSense) Constructs a new instance of the algorithm with the specifiedoptions
. The goal of the constructed algorithm is to maximize or minimize the weight of the resulting perfect matching depending on themaximize
parameter. Parameters:
graph
 the graph for which to find a weighted perfect matchingoptions
 the options which define the strategies for the initialization and dual updatesobjectiveSense
 objective sense of the algorithm


Method Details

getMatching
Computes and returns a weighted perfect matching in thegraph
. See the class description for the relative definitions and algorithm description. Specified by:
getMatching
in interfaceMatchingAlgorithm<V,
E>  Returns:
 a weighted perfect matching for the
graph

getDualSolution
Returns the computed solution to the dual linear program with respect to the weighted perfect matching linear program formulation. Returns:
 the solution to the dual linear program formulated on the
graph

testOptimality
public boolean testOptimality()Performs an optimality test after the perfect matching is computed.More precisely, checks whether dual variables of all pseudonodes and resulting slacks of all edges are nonnegative and that slacks of all matched edges are exactly 0. Since the algorithm uses floating point arithmetic, this check is done with precision of
EPS
In general, this method should always return true unless the algorithm implementation has a bug.
 Returns:
 true iff the assigned dual variables satisfy the dual linear program formulation AND complementary slackness conditions are also satisfied. The total error must not exceed EPS

getError
public double getError()Computes the error in the solution to the dual linear program. More precisely, the total error equals the sum of: Absolute value of edge slack if negative or the edge is matched
 Absolute value of pseudonode variable if negative
 Returns:
 the total numeric error

getStatistics
Returns the statistics describing the performance characteristics of the algorithm. Returns:
 the statistics describing the algorithms characteristics
