121#ifndef OR_TOOLS_GRAPH_ONE_TREE_LOWER_BOUND_H_
122#define OR_TOOLS_GRAPH_ONE_TREE_LOWER_BOUND_H_
152template <
typename CostType>
156 : step1_initialized_(false),
159 max_iterations_(max_iterations > 0 ? max_iterations
160 : MaxIterations(number_of_nodes)),
161 number_of_nodes_(number_of_nodes) {}
163 bool Next() {
return iteration_++ < max_iterations_; }
166 return (1.0 * (iteration_ - 1) * (2 * max_iterations_ - 5) /
167 (2 * (max_iterations_ - 1))) *
169 (iteration_ - 2) * step1_ +
170 (0.5 * (iteration_ - 1) * (iteration_ - 2) /
171 ((max_iterations_ - 1) * (max_iterations_ - 2))) *
176 const std::vector<int>& degrees) {
177 if (!step1_initialized_) {
178 step1_initialized_ =
true;
179 UpdateStep(one_tree_cost);
183 void OnNewWMax(CostType one_tree_cost) { UpdateStep(one_tree_cost); }
188 static int MaxIterations(
int number_of_nodes) {
189 return static_cast<int>(28 * std::pow(number_of_nodes, 0.62));
192 void UpdateStep(CostType one_tree_cost) {
193 step1_ = one_tree_cost / (2 * number_of_nodes_);
196 bool step1_initialized_;
199 const int max_iterations_;
200 const int number_of_nodes_;
205template <
typename CostType,
typename CostFunction>
210 number_of_iterations_(2 * number_of_nodes),
217 number_of_nodes,
cost);
222 const int min_iterations = 2;
223 if (iteration_ >= number_of_iterations_) {
224 number_of_iterations_ /= 2;
225 if (number_of_iterations_ < min_iterations)
return false;
237 const std::vector<int>& degrees) {
239 for (
int degree : degrees) {
240 const double delta = degree - 2;
243 step_ = lambda_ * (upper_bound_ - w) / norm;
250 int number_of_iterations_;
251 CostType upper_bound_;
261template <
typename CostFunction>
263 int number_of_neighbors,
264 const CostFunction&
cost) {
265 using CostType =
decltype(
cost(0, 0));
266 std::set<std::pair<int, int>> nearest;
267 for (
int i = 0; i < number_of_nodes; ++i) {
268 std::vector<std::pair<CostType, int>> neighbors;
269 neighbors.reserve(number_of_nodes - 1);
270 for (
int j = 0; j < number_of_nodes; ++j) {
272 neighbors.emplace_back(
cost(i, j), j);
275 int size = neighbors.size();
276 if (number_of_neighbors < size) {
277 std::nth_element(neighbors.begin(),
278 neighbors.begin() + number_of_neighbors - 1,
280 size = number_of_neighbors;
282 for (
int j = 0; j < size; ++j) {
283 nearest.insert({i, neighbors[j].second});
284 nearest.insert({neighbors[j].second, i});
292template <
typename CostFunction>
294 const CostFunction&
cost,
295 std::set<std::pair<int, int>>* arcs) {
297 const std::vector<int> mst =
301 for (
int arc : mst) {
302 arcs->insert({graph.
Tail(arc), graph.
Head(arc)});
303 arcs->insert({graph.
Head(arc), graph.
Tail(arc)});
309template <
typename CostFunction,
typename GraphType,
typename AcceptFunction>
311 const CostFunction&
cost,
312 AcceptFunction accept) {
314 double best_edge_cost = 0;
315 for (
const auto node : graph.AllNodes()) {
317 const double edge_cost =
cost(node, source);
318 if (best_node == -1 || edge_cost < best_edge_cost) {
320 best_edge_cost = edge_cost;
330template <
typename CostFunction,
typename GraphType,
typename CostType>
332 const CostFunction&
cost,
333 const std::vector<double>& weights,
334 const std::vector<int>& sorted_arcs,
335 CostType* one_tree_cost) {
336 const auto weighed_cost = [&
cost, &weights](
int from,
int to) {
337 return cost(from, to) + weights[from] + weights[to];
340 std::vector<int> mst;
341 if (!sorted_arcs.empty()) {
342 mst = BuildKruskalMinimumSpanningTreeFromSortedArcs<GraphType>(graph,
345 mst = BuildPrimMinimumSpanningTree<GraphType>(
346 graph, [&weighed_cost, &graph](
int arc) {
347 return weighed_cost(graph.Tail(arc), graph.Head(arc));
350 std::vector<int> degrees(graph.num_nodes() + 1, 0);
352 for (
int arc : mst) {
353 degrees[graph.Head(arc)]++;
354 degrees[graph.Tail(arc)]++;
355 *one_tree_cost +=
cost(graph.Tail(arc), graph.Head(arc));
359 const int extra_node = graph.num_nodes();
360 const auto update_one_tree = [extra_node, one_tree_cost, °rees,
362 *one_tree_cost +=
cost(node, extra_node);
367 graph, extra_node, weighed_cost,
368 [extra_node](
int n) {
return n != extra_node; });
369 update_one_tree(node);
371 graph, extra_node, weighed_cost,
372 [extra_node, node](
int n) {
return n != extra_node && n != node; }));
377template <
typename CostFunction,
typename Algorithm>
379 int nearest_neighbors,
380 const CostFunction&
cost,
381 Algorithm* algorithm) {
382 if (number_of_nodes < 2)
return 0;
383 if (number_of_nodes == 2)
return cost(0, 1) +
cost(1, 0);
384 using CostType =
decltype(
cost(0, 0));
391 for (
const auto& arc : nearest) {
392 graph.
AddArc(arc.first, arc.second);
394 std::vector<double> weights(number_of_nodes, 0);
395 std::vector<double> best_weights(number_of_nodes, 0);
396 double max_w = -std::numeric_limits<double>::infinity();
399 while (algorithm->Next()) {
400 CostType one_tree_cost = 0;
401 const std::vector<int> degrees =
403 algorithm->OnOneTree(one_tree_cost, w, degrees);
405 for (
int j = 0; j < number_of_nodes; ++j) {
406 w += weights[j] * (degrees[j] - 2);
410 best_weights = weights;
411 algorithm->OnNewWMax(one_tree_cost);
413 const double step = algorithm->GetStep();
414 for (
int j = 0; j < number_of_nodes; ++j) {
415 weights[j] += step * (degrees[j] - 2);
422 CostType one_tree_cost = 0;
426 const std::vector<int> degrees =
429 for (
int j = 0; j < number_of_nodes; ++j) {
430 w += best_weights[j] * (degrees[j] - 2);
451template <
typename CostFunction>
453 int number_of_nodes,
const CostFunction&
cost,
455 using CostType =
decltype(
cost(0, 0));
459 number_of_nodes,
parameters.volgenant_jonker_iterations);
466 number_of_nodes,
cost);
479template <
typename CostFunction>
CostType TravelingSalesmanCost()
void OnNewWMax(CostType one_tree_cost)
void OnOneTree(CostType one_tree_cost, double w, const std::vector< int > °rees)
HeldWolfeCrowderEvaluator(int number_of_nodes, const CostFunction &cost)
VolgenantJonkerEvaluator(int number_of_nodes, int max_iterations)
void OnNewWMax(CostType one_tree_cost)
void OnOneTree(CostType one_tree_cost, double w, const std::vector< int > °rees)
NodeIndexType Tail(ArcIndexType arc) const
NodeIndexType Head(ArcIndexType arc) const
ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
void AddArcsFromMinimumSpanningTree(int number_of_nodes, const CostFunction &cost, std::set< std::pair< int, int > > *arcs)
double ComputeOneTreeLowerBound(int number_of_nodes, const CostFunction &cost)
int GetNodeMinimizingEdgeCostToSource(const GraphType &graph, int source, const CostFunction &cost, AcceptFunction accept)
std::vector< typename Graph::ArcIndex > BuildPrimMinimumSpanningTree(const Graph &graph, const ArcValue &arc_value)
double ComputeOneTreeLowerBoundWithParameters(int number_of_nodes, const CostFunction &cost, const TravelingSalesmanLowerBoundParameters ¶meters)
std::vector< int > ComputeOneTree(const GraphType &graph, const CostFunction &cost, const std::vector< double > &weights, const std::vector< int > &sorted_arcs, CostType *one_tree_cost)
std::set< std::pair< int, int > > NearestNeighbors(int number_of_nodes, int number_of_neighbors, const CostFunction &cost)
double ComputeOneTreeLowerBoundWithAlgorithm(int number_of_nodes, int nearest_neighbors, const CostFunction &cost, Algorithm *algorithm)
int volgenant_jonker_iterations