#include <cmath>
#include <cstdint>
#include <limits>
#include <set>
#include <utility>
#include <vector>
#include "absl/types/span.h"
#include "ortools/base/logging.h"
#include "ortools/graph/christofides.h"
#include "ortools/graph/graph.h"
#include "ortools/graph/minimum_spanning_tree.h"

Functions
trees with all degrees equal w the current value of int	step1_ (0)

trees with all degrees equal w the current value of int	iteration_ (0)

trees with all degrees equal w the current value of int	max_iterations_ (max_iterations > 0 ? max_iterations :MaxIterations(number_of_nodes))

trees with all degrees equal w the current value of int	number_of_nodes_ (number_of_nodes)

bool	Next ()

double	GetStep () const

void	OnOneTree (CostType one_tree_cost, double w, absl::Span< const int > degrees)

void	OnNewWMax (CostType one_tree_cost)

Variables
trees with all degrees equal	to

trees with all degrees equal	therefore

trees with all degrees equal w the current value of	w

trees with all degrees equal w the current value of	degrees

trees with all degrees equal w the current value of int	max_iterations

Function Documentation

◆ GetStep()

double GetStep ( ) const

Definition at line 169 of file one_tree_lower_bound.h.

◆ iteration_()

trees with all degrees equal w the current value of int iteration_ ( 0 )

◆ max_iterations_()

trees with all degrees equal w the current value of int max_iterations_	(	max_iterations	,
		0 ? max_iterations	:MaxIterationsnumber_of_nodes )

◆ Next()

bool Next ( )

Definition at line 167 of file one_tree_lower_bound.h.

◆ number_of_nodes_()

trees with all degrees equal w the current value of int number_of_nodes_ ( number_of_nodes )

Definition at line 165 of file one_tree_lower_bound.h.

◆ OnNewWMax()

void OnNewWMax ( CostType one_tree_cost )

Definition at line 187 of file one_tree_lower_bound.h.

◆ OnOneTree()

void OnOneTree	(	CostType	one_tree_cost,
		double	w,
		absl::Span< const int >	degrees )

Definition at line 179 of file one_tree_lower_bound.h.

◆ step1_()

trees with all degrees equal w the current value of int step1_ ( 0 )

Variable Documentation

◆ degrees

trees with all degrees equal w the current value of degrees

Definition at line 149 of file one_tree_lower_bound.h.

◆ max_iterations

trees with all degrees equal w the current value of int max_iterations

Definition at line 159 of file one_tree_lower_bound.h.

◆ therefore

trees with all degrees equal therefore

Definition at line 34 of file one_tree_lower_bound.h.

◆ to

trees with all degrees equal to

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. An implementation of the Held-Karp symmetric Traveling Salesman (TSP) lower bound algorithm, inspired by "Estimating the Held-Karp lower bound for the geometric TSP" by Christine L. Valenzuela and Antonia J. Jones, European Journal of Operational Research, Volume 102, Issue 1, 1 October 1997, Pages 157-175.

The idea is to compute minimum 1-trees to evaluate a lower bound to the corresponding TSP. A minimum 1-tree is a minimum spanning tree on all nodes but one, to which are added the two shortest edges from the left-out node to the nodes of the spanning tree. The sum of the cost of the edges of the minimum 1-tree is a lower bound to the cost of the TSP. In order to improve (increase) this lower bound, the idea is to add weights to each nodes, weights which are added to the cost function used when computing the 1-tree. If weight[i] is the weight of node i, the cost function therefore becomes weighed_cost(i,j) = cost(i,j) + weight[i] + weight[j]. One can see that w = weighed_cost(minimum 1-tree) - Sum(2 * weight[i]) = cost(minimum 1-tree) + Sum(weight[i] * (degree[i] - 2)) is a valid lower bound to the TSP: 1) let T be the set of 1-trees on the nodes; 2) let U be the set of tours on the nodes; U is a subset of T (tours are