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 repair

ALGORITHM ARTICLE

Cycle branch and bound

Problem. Find the best cycle-cover reconnection without enumerating every completion.

Core idea. A lower bound on unfinished bridge cost prunes partial reconnections.

Procedure

  1. Branch on cycle order and entries.
  2. Bound remaining bridge deltas.
  3. Keep the best complete feasible tour.

Certificate. Feasible incumbent plus exhausted or bounded reconnection tree.

Data structures and API

from optfin_orlab import TspCycleBranchAndBoundSolver

solver = TspCycleBranchAndBoundSolver()
result = solver.solve(...)

Complexity. Exponential in the worst case

Limits. Certification is over the represented reconnection space.

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.
  • CorrectnessFeasible incumbent plus exhausted or bounded reconnection tree.
  • ComplexityExponential in the worst case
  • Operational limitCertification is over the represented reconnection space.
  • 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 Cycle branch and bound.

Open Luna for this algorithm

Back to the algorithm blog