operations_research::MinCostPerfectMatching Class Reference

#include <perfect_matching.h>

Public Types
enum	Status { OPTIMAL = 0 , INFEASIBLE = 1 , INTEGER_OVERFLOW = 2 , COST_OVERFLOW = 3 }

Public Member Functions
	MinCostPerfectMatching ()
	MinCostPerfectMatching (int num_nodes)
void	Reset (int num_nodes)
void	AddEdgeWithCost (int tail, int head, int64_t cost)
ABSL_MUST_USE_RESULT Status	Solve ()
int64_t	OptimalCost () const
int	Match (int node) const
const std::vector< int > &	Matches () const

Detailed Description

Given an undirected graph with costs on each edges, this class allows to compute a perfect matching with minimum cost. A matching is a set of disjoint pairs of nodes connected by an edge. The matching is perfect if all nodes are matched to each others.

Definition at line 50 of file perfect_matching.h.

Member Enumeration Documentation

Status

enum operations_research::MinCostPerfectMatching::Status

Solves the min-cost perfect matching problem on the given graph.

NOTE(user): If needed we could support a time limit. Aborting early will not provide a perfect matching, but the algorithm does maintain a valid lower bound on the optimal cost that gets better and better during execution until it reaches the optimal value. Similarly, it is easy to support an early stop if this bound crosses a preset threshold.

Enumerator
OPTIMAL	A perfect matching with min-cost has been found.
INFEASIBLE	There is no perfect matching in this graph.
INTEGER_OVERFLOW	The costs are too large and caused an overflow during the algorithm execution.
COST_OVERFLOW	Advanced usage: the matching is OPTIMAL and was computed without overflow, but its OptimalCost() does not fit on an int64_t. Note that Match() still work and you can re-compute the cost in double for instance.

Definition at line 81 of file perfect_matching.h.

Constructor & Destructor Documentation

MinCostPerfectMatching() [1/2]

operations_research::MinCostPerfectMatching::MinCostPerfectMatching ( )

inline

Todo

(user): For now we ask the number of nodes at construction, but we could automatically infer it from the added edges if needed.

Definition at line 54 of file perfect_matching.h.

MinCostPerfectMatching() [2/2]

operations_research::MinCostPerfectMatching::MinCostPerfectMatching ( int num_nodes )

inlineexplicit

Definition at line 55 of file perfect_matching.h.

Member Function Documentation

AddEdgeWithCost()

void operations_research::MinCostPerfectMatching::AddEdgeWithCost	(	int	tail,
		int	head,
		int64_t	cost )

Adds an undirected edges between the two given nodes.

For now we only accept non-negative cost.

Todo

(user): We can easily shift all costs if negative costs are needed.

Important: The algorithm supports multi-edges, but it will be slower. So it is better to only add one edge with a minimum cost between two nodes. In particular, do not add both AddEdge(a, b, cost) and AddEdge(b, a, cost).

Todo

(user): We could just presolve them away.

Definition at line 40 of file perfect_matching.cc.

Match()

int operations_research::MinCostPerfectMatching::Match ( int node ) const

inline

Returns the node matched to the given node. In a perfect matching all nodes have a match. Only valid when the last solve status was OPTIMAL.

Definition at line 109 of file perfect_matching.h.

Matches()

const std::vector< int > & operations_research::MinCostPerfectMatching::Matches ( ) const

inline

Definition at line 113 of file perfect_matching.h.

OptimalCost()

int64_t operations_research::MinCostPerfectMatching::OptimalCost ( ) const

inline

Returns the cost of the perfect matching. Only valid when the last solve status was OPTIMAL.

Definition at line 102 of file perfect_matching.h.

Reset()

void operations_research::MinCostPerfectMatching::Reset

(

int

num_nodes

)

Resets the class for a new graph.

Todo

(user): Eventually, we may support incremental Solves(). Or at least memory reuse if one wants to solve many problems in a row.

Definition at line 34 of file perfect_matching.cc.

Solve()

MinCostPerfectMatching::Status operations_research::MinCostPerfectMatching::Solve

(

)

We want all dual and all slack value to never overflow. After Initialize() they are both bounded by the 2 * maximum cost. And we track an upper bound on these quantities. The factor two is because of the re-scaling we do internally since all our dual values are actually multiple of 1/2.

Note

since the whole code in BlossomGraph assumes that dual/slack have a magnitude that is always lower than kMaxCostValue it is important to use it here since there is no reason it cannot be smaller than kint64max.

Todo

(user): Improve the overflow detection if needed. The current one seems ok though.

Todo

(user): Maybe there is a faster/better way to recover the mapping in the presence of blossoms.

Definition at line 52 of file perfect_matching.cc.

---

The documentation for this class was generated from the following files:

• ortools/graph/perfect_matching.h
• ortools/graph/perfect_matching.cc