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

TSP assignment relaxation

Problem. Lower-bound a TSP by dropping global subtour connectivity.

Core idea. Every tour is a cycle cover, while a cycle cover may contain several cycles.

Procedure

  1. Forbid self loops.
  2. Solve assignment exactly.
  3. Extract cycles and report the lower bound.

Certificate. The relaxed feasible set contains every Hamiltonian tour.

Data structures and API

from optfin_orlab import TspAssignmentRelaxationSolver

solver = TspAssignmentRelaxationSolver()
result = solver.solve(...)

Complexity. O(n³)

Limits. The bound may be weak when many cheap subtours exist.

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.
  • CorrectnessThe relaxed feasible set contains every Hamiltonian tour.
  • ComplexityO(n³)
  • Operational limitThe bound may be weak when many cheap subtours exist.
  • 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 TSP assignment relaxation.

Open Luna for this algorithm

Back to the algorithm blog