OPTFIN.ORGMultidisciplinary Research Laboratory for Operations Research and AI
Sign in

You are browsing anonymously. A verified sign-in is required before any personal or project data can appear.

IMPLEMENTED_LOCAL_TESTEDTSP bounds

ALGORITHM ARTICLE

One-tree lower bound

Problem. Certified lower bound for symmetric TSP.

Core idea. Combine an MST excluding the depot with its two cheapest incident edges.

Procedure

  1. Build the non-depot MST.
  2. Select two cheapest depot edges.
  3. Add both costs.

Certificate. Every tour induces such a spanning structure.

Data structures and API

from optfin_orlab.tsp import TSP

solver = TSP()
result = solver.lower_bound(...)

Complexity. O(n²) in the dense implementation

Limits. It is not generally a feasible tour.

OPTFIN AUDIT CHECKS

What has to reconcile before this method is trusted.

  • DefinitionProblem, objective, inputs and output are explicit.
  • Data structureThe public API and canonical source path are identified.
  • CorrectnessEvery tour induces such a spanning structure.
  • ComplexityO(n²) in the dense implementation
  • Operational limitIt is not generally a feasible tour.
  • ReproductionSource, executable test and evidence route remain linked.
View sourceOpen executable testReproduce evidence

LUNA ACADEMIC

Continue this algorithm in one research conversation.

Ask for the paper trail, executable test, source explanation, or a reproducibility plan for One-tree lower bound.

Open Luna for this algorithm

Back to the algorithm blog