Abstract

We introduce an optical method based on white light interferometry in order to solve the well-known NP–complete traveling salesman problem. To our knowledge it is the first time that a method for the reduction of non–polynomial time to quadratic time has been proposed. We will show that this achievement is limited by the number of available photons for solving the problem. It will turn out that this number of photons is proportional to NN for a traveling salesman problem with N cities and that for large numbers of cities the method in practice therefore is limited by the signal–to–noise ratio. The proposed method is meant purely as a gedankenexperiment.

© 2007 Optical Society of America

Full Article  |  PDF Article

Errata

Tobias Haist and Wolfgang Osten, "An optical solution for the traveling salesman problem: erratum," Opt. Express 15, 12627-12627 (2007)
https://www.osapublishing.org/oe/abstract.cfm?uri=oe-15-20-12627

References

  • View by:
  • |
  • |

  1. G. Laporte, A. Asef-Vaziri, and C. Sriskandarajah, "Some applications of the generalized travelling salesman problem," J. Oper. Res. Soc. 47, 1461-1467 (1996).
  2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms, (MIT Press, 2001).
  3. C. Vourdouris and E. Tsang, "Guided local search and its application to the traveling salesman problem," Eur. J. Oper. Res. 113, 80-110 (1998).
  4. C. Kirkpatrick, "Optimization by simulated annealing: Quantitative studies," J. Stat. Phys. 34, 975-986 (1984).
    [CrossRef]
  5. J. J. Hopfield and D. W. Tank, "Neural’ computation of decisions in optimization problems," Biol. Cybern. 52, 381-384 (1985).
  6. F. Glover, E. Taillard, and D. de Werra, "A user’s guide to tabu search," Ann. Oper. Res. 41, 3-28 (1993).
    [CrossRef]
  7. S. Lin and W. Kernighan, "An effective heuristic algorithm for the traveling salesman problem,’Oper. Res. 21, 498-516, (1973).
    [CrossRef]
  8. J. Edmonds, "Matroids and the greedy algorithm," Math. Program. 1, 127-136 (1971).
    [CrossRef]
  9. S. Arora, "Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems," J. ACM 45, 753-7872 (1998).
    [CrossRef]
  10. D. S. Johnson, and L. A. McGeoch, "The traveling salesman problem: a case study in local optimization," in Local Search in Combinatorial Optimization," E. Aarts and J. K. Lenstra, eds., (Princton University Press, 2003).
  11. T. Hogg and D. Portnov, "Quantum optimization," Inf. Sci. 128, 181-197 (2000).
    [CrossRef]
  12. S. Y. Shin, B. T. Zhang, B.T., and S. S. Jun, "Solving traveling salesman problems using molecular programming," in Proceedings of the Congress on Evolutionary Computation, P. Angeline, Z. Michalewicz, M. Schoenauer, X. Yao, and A. Zalzala, eds., (IEEE Press, 1999), pp 994-1000.
  13. N. T. Shaked, S. Messika, S. Dolev, and J. Rosen, "Optical solution for bounded NP-complete problems," Appl. Opt. 46, 711-724 (2007).
    [CrossRef] [PubMed]
  14. G. S. Kino and S. C. Chi, "Mirau correlation microscope," Appl. Opt. 29, 3775-3783 (1990).
    [CrossRef] [PubMed]
  15. V. A. Kozlov, J. Hernandez-Codero, and T. F. Morse, "All-fiber coherent beam combining of fiber lasers," Opt. Lett. 24, 1814-1816 (1999).
    [CrossRef]
  16. B. E. A. Saleh and M. C. Teich, Fundamentals of Photonics, (Wiley, 1991).
    [CrossRef]
  17. A. F. Fercher, W. Drexler, C. K. Hitzenberger, and T. Lasser: "Optical coherence tomography — principles and applications," Reports on Progress in Physics 66, 239-303 (2003).
    [CrossRef]

2007

2003

A. F. Fercher, W. Drexler, C. K. Hitzenberger, and T. Lasser: "Optical coherence tomography — principles and applications," Reports on Progress in Physics 66, 239-303 (2003).
[CrossRef]

2000

T. Hogg and D. Portnov, "Quantum optimization," Inf. Sci. 128, 181-197 (2000).
[CrossRef]

1999

1998

S. Arora, "Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems," J. ACM 45, 753-7872 (1998).
[CrossRef]

C. Vourdouris and E. Tsang, "Guided local search and its application to the traveling salesman problem," Eur. J. Oper. Res. 113, 80-110 (1998).

1996

G. Laporte, A. Asef-Vaziri, and C. Sriskandarajah, "Some applications of the generalized travelling salesman problem," J. Oper. Res. Soc. 47, 1461-1467 (1996).

1993

F. Glover, E. Taillard, and D. de Werra, "A user’s guide to tabu search," Ann. Oper. Res. 41, 3-28 (1993).
[CrossRef]

1990

1985

J. J. Hopfield and D. W. Tank, "Neural’ computation of decisions in optimization problems," Biol. Cybern. 52, 381-384 (1985).

1984

C. Kirkpatrick, "Optimization by simulated annealing: Quantitative studies," J. Stat. Phys. 34, 975-986 (1984).
[CrossRef]

1973

S. Lin and W. Kernighan, "An effective heuristic algorithm for the traveling salesman problem,’Oper. Res. 21, 498-516, (1973).
[CrossRef]

1971

J. Edmonds, "Matroids and the greedy algorithm," Math. Program. 1, 127-136 (1971).
[CrossRef]

Ann. Oper. Res.

F. Glover, E. Taillard, and D. de Werra, "A user’s guide to tabu search," Ann. Oper. Res. 41, 3-28 (1993).
[CrossRef]

Appl. Opt.

Biol. Cybern.

J. J. Hopfield and D. W. Tank, "Neural’ computation of decisions in optimization problems," Biol. Cybern. 52, 381-384 (1985).

Eur. J. Oper. Res.

C. Vourdouris and E. Tsang, "Guided local search and its application to the traveling salesman problem," Eur. J. Oper. Res. 113, 80-110 (1998).

Inf. Sci.

T. Hogg and D. Portnov, "Quantum optimization," Inf. Sci. 128, 181-197 (2000).
[CrossRef]

J. ACM

S. Arora, "Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems," J. ACM 45, 753-7872 (1998).
[CrossRef]

J. Oper. Res. Soc.

G. Laporte, A. Asef-Vaziri, and C. Sriskandarajah, "Some applications of the generalized travelling salesman problem," J. Oper. Res. Soc. 47, 1461-1467 (1996).

J. Stat. Phys.

C. Kirkpatrick, "Optimization by simulated annealing: Quantitative studies," J. Stat. Phys. 34, 975-986 (1984).
[CrossRef]

Math. Program.

J. Edmonds, "Matroids and the greedy algorithm," Math. Program. 1, 127-136 (1971).
[CrossRef]

Oper. Res.

S. Lin and W. Kernighan, "An effective heuristic algorithm for the traveling salesman problem,’Oper. Res. 21, 498-516, (1973).
[CrossRef]

Opt. Lett.

Reports on Progress in Physics

A. F. Fercher, W. Drexler, C. K. Hitzenberger, and T. Lasser: "Optical coherence tomography — principles and applications," Reports on Progress in Physics 66, 239-303 (2003).
[CrossRef]

Other

B. E. A. Saleh and M. C. Teich, Fundamentals of Photonics, (Wiley, 1991).
[CrossRef]

D. S. Johnson, and L. A. McGeoch, "The traveling salesman problem: a case study in local optimization," in Local Search in Combinatorial Optimization," E. Aarts and J. K. Lenstra, eds., (Princton University Press, 2003).

S. Y. Shin, B. T. Zhang, B.T., and S. S. Jun, "Solving traveling salesman problems using molecular programming," in Proceedings of the Congress on Evolutionary Computation, P. Angeline, Z. Michalewicz, M. Schoenauer, X. Yao, and A. Zalzala, eds., (IEEE Press, 1999), pp 994-1000.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms, (MIT Press, 2001).

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (4)

Fig. 1.
Fig. 1.

The traveling salesman problem: Find the shortest round-trip through N cities.

Fig. 2.
Fig. 2.

Optical solution for the TSP by white light interferometry

Fig. 3.
Fig. 3.

Assembly of one city: N input and N output ports (for the asymmetrical TSP) are connected by a delay line of variable length. The overall delay for photons in city i is given by Di (see Eq. 1). Fan-in and Fan-out elements (e.g. star-couplers) can be used for a practical implementation.

Fig. 4.
Fig. 4.

Necessary energy per measurement (at λ=1 µ m)) for solving the TSP.

Equations (19)

Equations on this page are rendered with MathJax. Learn more.

D i = α 2 i + d
α > > N max ( d ij )
N total = ( N 1 ) + ( N 2 ) + 1 = i = 1 N 1 i = N 2 N 2
L = N d + i = 0 N 1 α 2 i + P
> N d + α ( 2 N 1 )
P = i = 1 N d Pathi
Δ L i = L i + d ij
N max = ( N 1 ) + ( N 2 ) + 2 = i = 2 N 1 i = N 2 N 2 1
I 1 = I 0 + 1 # C C i + R + 1 # W W C j 2 + k = 1 # K h = 1 # H k W kh 2
I 2 = I 0 + 1 # C C i + 1 # W W C j 2 + k = 1 # K h = 1 # H k W kh 2
I 1 I 2 = 1 # C C i + R + 1 # W W C j 2 1 # C C i + 1 # W W C j 2
P = G x 1 mm
1 mm < P < N max ( d ij ) = N x 1 m
N = N + k 1 mm d
I = 2 + 2 N N 2 e i ϕ 2 4 + 8 N N 2 cos ( ϕ )
N g < M 16 N N 2
N g 4 M < M 2 16 2 ( N N 2 ) 2
M 1 64 N N
N g ( 4 + 1 ) M = 5 64 N N

Metrics