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 contraction and patching

Problem. Reconnect a cycle cover into one Hamiltonian tour.

Core idea. Enumerate cycle order and entry points while measuring bridge deltas exactly.

Procedure

  1. Validate disjoint cycles.
  2. Enumerate admissible orders and entries.
  3. Return the least-cost feasible patch.

Certificate. Hamiltonian-tour validation and recomputed patch cost.

Data structures and API

from optfin_orlab.exact import TspCycleContractionSolver

solver = TspCycleContractionSolver()
result = solver.solve(...)

Complexity. Exponential in cycle count and entry choices

Limits. Intended for small exact repair instances.

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.
  • CorrectnessHamiltonian-tour validation and recomputed patch cost.
  • ComplexityExponential in cycle count and entry choices
  • Operational limitIntended for small exact repair instances.
  • 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 contraction and patching.

Open Luna for this algorithm

Back to the algorithm blog