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 exact

ALGORITHM ARTICLE

Held-Karp subset dynamic programming

Problem. Exact symmetric travelling-salesman tour.

Core idea. The best partial tour is identified by visited subset and final vertex.

Procedure

  1. Initialize the depot subset.
  2. Extend each state to an unseen vertex.
  3. Close and reconstruct the minimum cycle.

Certificate. Complete subset recurrence and minimum final return.

Data structures and API

from optfin_orlab.tsp import TSP

solver = TSP()
result = solver.solve(...)

Complexity. O(2ⁿn²) time; O(2ⁿn) memory

Limits. Exponential memory restricts instance size.

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.
  • CorrectnessComplete subset recurrence and minimum final return.
  • ComplexityO(2ⁿn²) time; O(2ⁿn) memory
  • Operational limitExponential memory restricts instance size.
  • 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 Held-Karp subset dynamic programming.

Open Luna for this algorithm

Back to the algorithm blog