operations_research::ChristofidesPathSolver< CostType, ArcIndex, NodeIndex, CostFunction > Class Template Reference

#include <christofides.h>

Public Types
enum class	MatchingAlgorithm { MINIMUM_WEIGHT_MATCHING , MINIMUM_WEIGHT_MATCHING_WITH_MIP , MINIMAL_WEIGHT_MATCHING }

Public Member Functions
	ChristofidesPathSolver (NodeIndex num_nodes, CostFunction costs)
void	SetMatchingAlgorithm (MatchingAlgorithm matching)
CostType	TravelingSalesmanCost ()
	Returns the cost of the approximate TSP tour.
std::vector< NodeIndex >	TravelingSalesmanPath ()
	Returns the approximate TSP tour.
bool	Solve ()

Detailed Description

template<typename CostType, typename ArcIndex = int64_t, typename NodeIndex = int32_t, typename CostFunction = std::function<CostType(NodeIndex, NodeIndex)>>
class operations_research::ChristofidesPathSolver< CostType, ArcIndex, NodeIndex, CostFunction >

Definition at line 53 of file christofides.h.

Member Enumeration Documentation

MatchingAlgorithm

template<typename CostType , typename ArcIndex = int64_t, typename NodeIndex = int32_t, typename CostFunction = std::function<CostType(NodeIndex, NodeIndex)>>

enum class operations_research::ChristofidesPathSolver::MatchingAlgorithm

strong

Enumerator
MINIMUM_WEIGHT_MATCHING
MINIMUM_WEIGHT_MATCHING_WITH_MIP
MINIMAL_WEIGHT_MATCHING

Definition at line 55 of file christofides.h.

Constructor & Destructor Documentation

ChristofidesPathSolver()

template<typename CostType , typename ArcIndex , typename NodeIndex , typename CostFunction >

operations_research::ChristofidesPathSolver< CostType, ArcIndex, NodeIndex, CostFunction >::ChristofidesPathSolver	(	NodeIndex	num_nodes,
		CostFunction	costs )

Definition at line 222 of file christofides.h.

Member Function Documentation

SetMatchingAlgorithm()

template<typename CostType , typename ArcIndex = int64_t, typename NodeIndex = int32_t, typename CostFunction = std::function<CostType(NodeIndex, NodeIndex)>>

void operations_research::ChristofidesPathSolver< CostType, ArcIndex, NodeIndex, CostFunction >::SetMatchingAlgorithm ( MatchingAlgorithm matching )

inline

Sets the matching algorithm to use. A minimum weight perfect matching (MINIMUM_WEIGHT_MATCHING) guarantees the 3/2 upper bound to the optimal solution. A minimal weight perfect matching (MINIMAL_WEIGHT_MATCHING) finds a locally minimal weight matching which does not offer any bound guarantee but, as of 1/2017, is orders of magnitude faster than the minimum matching. By default, MINIMAL_WEIGHT_MATCHING is selected.

Todo

(user): Change the default when minimum matching gets faster.

Definition at line 72 of file christofides.h.

Solve()

template<typename CostType , typename ArcIndex , typename NodeIndex , typename CostFunction >

bool operations_research::ChristofidesPathSolver< CostType, ArcIndex, NodeIndex, CostFunction >::Solve

(

)

Runs the Christofides algorithm. Returns true if a solution was found, false otherwise.

Compute Minimum Spanning Tree.

Detect odd degree nodes.

Find minimum-weight perfect matching on odd-degree-node complete graph.

Todo

(user): Make this code available as an independent algorithm.

Todo

(user): Cost caching was added and can gain up to 20% but increases memory usage; see if we can avoid caching.

Build Eulerian path on minimum spanning tree + closing edges from matching and extract a solution to the Traveling Salesman from the path by skipping duplicate nodes.

Definition at line 255 of file christofides.h.

TravelingSalesmanCost()

template<typename CostType , typename ArcIndex , typename NodeIndex , typename CostFunction >

CostType operations_research::ChristofidesPathSolver< CostType, ArcIndex, NodeIndex, CostFunction >::TravelingSalesmanCost

(

)

Returns the cost of the approximate TSP tour.

Definition at line 233 of file christofides.h.

TravelingSalesmanPath()

template<typename CostType , typename ArcIndex , typename NodeIndex , typename CostFunction >

std::vector< NodeIndex > operations_research::ChristofidesPathSolver< CostType, ArcIndex, NodeIndex, CostFunction >::TravelingSalesmanPath

(

)

Returns the approximate TSP tour.

Definition at line 244 of file christofides.h.

---

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

• ortools/graph/christofides.h