Abstract

We present a new optical method for solving bounded (input-length-restricted) NP-complete combinatorial problems. We have chosen to demonstrate the method with an NP-complete problem called the traveling salesman problem (TSP). The power of optics in this method is realized by using a fast matrix–vector multiplication between a binary matrix, representing all feasible TSP tours, and a gray-scale vector, representing the weights among the TSP cities. The multiplication is performed optically by using an optical correlator. To synthesize the initial binary matrix representing all feasible tours, an efficient algorithm is provided. Simulations and experimental results prove the validity of the new method.

© 2007 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. D. Harel, Algorithmics: The Spirit of Computing (Addison-Wesley, 1987).
  2. G. Reinelt, The Traveling Salesman: Computational Solutions for TSP Applications (Springer-Verlag, 1994).
  3. J. E. Mitchell, "Branch-and-cut algorithms for combinatorial optimization problems," in Handbook of Applied Optimization (Oxford U. Press, 2002), pp. 65-77.
  4. K. A. Smith, "Neural networks for combinatorial optimization: a review of more than a decade of research," INFORMS J. Comput. 11, 15-34 (1999).
    [CrossRef]
  5. N. Collings, R. Sumi, K. J. Weible, B. Acklin, and W. Xue, "The use of optical hardware to find good solutions of the travelling salesman problem (TSP)," in Proc. SPIE 1806, 637-641 (1993).
    [CrossRef]
  6. D. Gutfreund, R. Shaltiel, and A. Ta-Shma, "If NP languages are hard on the worst-case then it is easy to find their hard instances," in Proceedings of the 20th Annual Conference on Computational Complexity (CCC) (2005). A long version of this paper is available on the web at http://www.cs.tau.ac.il/∼amnon/Papers/GST.cc05.journal.ps.
  7. J. W. Goodman, Introduction to Fourier Optics, 2nd ed. (McGraw-Hill, 1996), pp. 232-246.
  8. C. S. Weaver and J. W. Goodman, "A technique for optically convolving two functions," Appl. Opt. 5, 1248-1249 (1966).
    [CrossRef] [PubMed]
  9. A. VanderLugt, "Signal detection by complex spatial filtering," IEEE Trans. Inf. Theory IT-10, 139-145 (1964).
    [CrossRef]
  10. A. Homaifar, S. Guan, and G. E. Liepins, "Schema analysis of the traveling salesman problem using genetic algorithms," Complex Syst. 6, 183-217 (1992).
  11. D. G. Feitelson, Optical Computing: A Survey for Computer Scientists (MIT Press, 1988), pp. 148-163.
  12. M. A. Karim and A. A. S. Awwal, Optical Computing: An Introduction (Wiley, 1992), pp. 328-356.
  13. J. W. Goodman, Introduction to Fourier Optics, 2nd ed. (McGraw-Hill, 1996), pp. 282-289.
  14. A. D. McAulay, Optical Computer Architectures: The Application of Optical Concepts to Next Generation Computers (Wiley, 1991), pp. 289-299.
    [PubMed]
  15. S. Dolev, E. Korach, and G. Uzan, "A method for encryption and decryption of messages," PCT patent application WO 2006/001006 (5 January 2006).

1999 (1)

K. A. Smith, "Neural networks for combinatorial optimization: a review of more than a decade of research," INFORMS J. Comput. 11, 15-34 (1999).
[CrossRef]

1993 (1)

N. Collings, R. Sumi, K. J. Weible, B. Acklin, and W. Xue, "The use of optical hardware to find good solutions of the travelling salesman problem (TSP)," in Proc. SPIE 1806, 637-641 (1993).
[CrossRef]

1992 (1)

A. Homaifar, S. Guan, and G. E. Liepins, "Schema analysis of the traveling salesman problem using genetic algorithms," Complex Syst. 6, 183-217 (1992).

1966 (1)

1964 (1)

A. VanderLugt, "Signal detection by complex spatial filtering," IEEE Trans. Inf. Theory IT-10, 139-145 (1964).
[CrossRef]

Acklin, B.

N. Collings, R. Sumi, K. J. Weible, B. Acklin, and W. Xue, "The use of optical hardware to find good solutions of the travelling salesman problem (TSP)," in Proc. SPIE 1806, 637-641 (1993).
[CrossRef]

Awwal, A. A. S.

M. A. Karim and A. A. S. Awwal, Optical Computing: An Introduction (Wiley, 1992), pp. 328-356.

Collings, N.

N. Collings, R. Sumi, K. J. Weible, B. Acklin, and W. Xue, "The use of optical hardware to find good solutions of the travelling salesman problem (TSP)," in Proc. SPIE 1806, 637-641 (1993).
[CrossRef]

Dolev, S.

S. Dolev, E. Korach, and G. Uzan, "A method for encryption and decryption of messages," PCT patent application WO 2006/001006 (5 January 2006).

Feitelson, D. G.

D. G. Feitelson, Optical Computing: A Survey for Computer Scientists (MIT Press, 1988), pp. 148-163.

Goodman, J. W.

C. S. Weaver and J. W. Goodman, "A technique for optically convolving two functions," Appl. Opt. 5, 1248-1249 (1966).
[CrossRef] [PubMed]

J. W. Goodman, Introduction to Fourier Optics, 2nd ed. (McGraw-Hill, 1996), pp. 282-289.

J. W. Goodman, Introduction to Fourier Optics, 2nd ed. (McGraw-Hill, 1996), pp. 232-246.

Guan, S.

A. Homaifar, S. Guan, and G. E. Liepins, "Schema analysis of the traveling salesman problem using genetic algorithms," Complex Syst. 6, 183-217 (1992).

Gutfreund, D.

D. Gutfreund, R. Shaltiel, and A. Ta-Shma, "If NP languages are hard on the worst-case then it is easy to find their hard instances," in Proceedings of the 20th Annual Conference on Computational Complexity (CCC) (2005). A long version of this paper is available on the web at http://www.cs.tau.ac.il/∼amnon/Papers/GST.cc05.journal.ps.

Harel, D.

D. Harel, Algorithmics: The Spirit of Computing (Addison-Wesley, 1987).

Homaifar, A.

A. Homaifar, S. Guan, and G. E. Liepins, "Schema analysis of the traveling salesman problem using genetic algorithms," Complex Syst. 6, 183-217 (1992).

Karim, M. A.

M. A. Karim and A. A. S. Awwal, Optical Computing: An Introduction (Wiley, 1992), pp. 328-356.

Korach, E.

S. Dolev, E. Korach, and G. Uzan, "A method for encryption and decryption of messages," PCT patent application WO 2006/001006 (5 January 2006).

Liepins, G. E.

A. Homaifar, S. Guan, and G. E. Liepins, "Schema analysis of the traveling salesman problem using genetic algorithms," Complex Syst. 6, 183-217 (1992).

McAulay, A. D.

A. D. McAulay, Optical Computer Architectures: The Application of Optical Concepts to Next Generation Computers (Wiley, 1991), pp. 289-299.
[PubMed]

Mitchell, J. E.

J. E. Mitchell, "Branch-and-cut algorithms for combinatorial optimization problems," in Handbook of Applied Optimization (Oxford U. Press, 2002), pp. 65-77.

Reinelt, G.

G. Reinelt, The Traveling Salesman: Computational Solutions for TSP Applications (Springer-Verlag, 1994).

Shaltiel, R.

D. Gutfreund, R. Shaltiel, and A. Ta-Shma, "If NP languages are hard on the worst-case then it is easy to find their hard instances," in Proceedings of the 20th Annual Conference on Computational Complexity (CCC) (2005). A long version of this paper is available on the web at http://www.cs.tau.ac.il/∼amnon/Papers/GST.cc05.journal.ps.

Smith, K. A.

K. A. Smith, "Neural networks for combinatorial optimization: a review of more than a decade of research," INFORMS J. Comput. 11, 15-34 (1999).
[CrossRef]

Sumi, R.

N. Collings, R. Sumi, K. J. Weible, B. Acklin, and W. Xue, "The use of optical hardware to find good solutions of the travelling salesman problem (TSP)," in Proc. SPIE 1806, 637-641 (1993).
[CrossRef]

Ta-Shma, A.

D. Gutfreund, R. Shaltiel, and A. Ta-Shma, "If NP languages are hard on the worst-case then it is easy to find their hard instances," in Proceedings of the 20th Annual Conference on Computational Complexity (CCC) (2005). A long version of this paper is available on the web at http://www.cs.tau.ac.il/∼amnon/Papers/GST.cc05.journal.ps.

Uzan, G.

S. Dolev, E. Korach, and G. Uzan, "A method for encryption and decryption of messages," PCT patent application WO 2006/001006 (5 January 2006).

VanderLugt, A.

A. VanderLugt, "Signal detection by complex spatial filtering," IEEE Trans. Inf. Theory IT-10, 139-145 (1964).
[CrossRef]

Weaver, C. S.

Weible, K. J.

N. Collings, R. Sumi, K. J. Weible, B. Acklin, and W. Xue, "The use of optical hardware to find good solutions of the travelling salesman problem (TSP)," in Proc. SPIE 1806, 637-641 (1993).
[CrossRef]

Xue, W.

N. Collings, R. Sumi, K. J. Weible, B. Acklin, and W. Xue, "The use of optical hardware to find good solutions of the travelling salesman problem (TSP)," in Proc. SPIE 1806, 637-641 (1993).
[CrossRef]

Appl. Opt. (1)

Complex Syst. (1)

A. Homaifar, S. Guan, and G. E. Liepins, "Schema analysis of the traveling salesman problem using genetic algorithms," Complex Syst. 6, 183-217 (1992).

IEEE Trans. Inf. Theory (1)

A. VanderLugt, "Signal detection by complex spatial filtering," IEEE Trans. Inf. Theory IT-10, 139-145 (1964).
[CrossRef]

INFORMS J. Comput. (1)

K. A. Smith, "Neural networks for combinatorial optimization: a review of more than a decade of research," INFORMS J. Comput. 11, 15-34 (1999).
[CrossRef]

Proc. SPIE (1)

N. Collings, R. Sumi, K. J. Weible, B. Acklin, and W. Xue, "The use of optical hardware to find good solutions of the travelling salesman problem (TSP)," in Proc. SPIE 1806, 637-641 (1993).
[CrossRef]

Other (10)

D. Gutfreund, R. Shaltiel, and A. Ta-Shma, "If NP languages are hard on the worst-case then it is easy to find their hard instances," in Proceedings of the 20th Annual Conference on Computational Complexity (CCC) (2005). A long version of this paper is available on the web at http://www.cs.tau.ac.il/∼amnon/Papers/GST.cc05.journal.ps.

J. W. Goodman, Introduction to Fourier Optics, 2nd ed. (McGraw-Hill, 1996), pp. 232-246.

D. Harel, Algorithmics: The Spirit of Computing (Addison-Wesley, 1987).

G. Reinelt, The Traveling Salesman: Computational Solutions for TSP Applications (Springer-Verlag, 1994).

J. E. Mitchell, "Branch-and-cut algorithms for combinatorial optimization problems," in Handbook of Applied Optimization (Oxford U. Press, 2002), pp. 65-77.

D. G. Feitelson, Optical Computing: A Survey for Computer Scientists (MIT Press, 1988), pp. 148-163.

M. A. Karim and A. A. S. Awwal, Optical Computing: An Introduction (Wiley, 1992), pp. 328-356.

J. W. Goodman, Introduction to Fourier Optics, 2nd ed. (McGraw-Hill, 1996), pp. 282-289.

A. D. McAulay, Optical Computer Architectures: The Application of Optical Concepts to Next Generation Computers (Wiley, 1991), pp. 289-299.
[PubMed]

S. Dolev, E. Korach, and G. Uzan, "A method for encryption and decryption of messages," PCT patent application WO 2006/001006 (5 January 2006).

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 (13)

Fig. 1
Fig. 1

(Color online) Example of a seven-city symmetric TSP. The best (shortest) tour is indicated by bold lines.

Fig. 2
Fig. 2

Example of the induction stage of the algorithm that synthesizes the binary matrix—the transition from the N = 3 binary matrix to the N = 4 binary matrix: (a) steps I–V, (b) step VI, part 1—use section S1 of the new binary matrix to fill section S2 of this matrix, (c) step VI, part 2—use section S1 of the new binary matrix to fill section S3 of this matrix.

Fig. 3
Fig. 3

(Color online) The exact mask (white = 1, black = 0) that represents the binary matrix of N = 6, contains the easy-to-modify mask of N = 5 . The latter mask contains the N = 4 easy-to-modify mask, which contains the N = 3 easy-to-modify mask.

Fig. 4
Fig. 4

Exact masks (white = 1, black = 0) that represent the binary matrices of (a) N = 5 , (b) N = 4 , and (c) N = 3 .

Fig. 5
Fig. 5

JTC scheme.

Fig. 6
Fig. 6

JTC input and output planes for the seven-city TSP shown in Fig. 1. Note that the contrast of all images in this figure is inverted for a better visualization: (a) weight vector, (b) binary matrix including a reference column on the left, (c) output plane.

Fig. 7
Fig. 7

(Color online) (a) Cross section across the left column (at x = 8917 ) of the correlation matrix shown in the right-lower part of Fig. 6(c). (b) Cross section across the middle row (at y = 833 ) of the correlation matrix shown in the right-lower part of Fig. 6(c).

Fig. 8
Fig. 8

(Color online) Five-city symmetric TSP solved in both the second simulation and the optical experiment. The best (shortest) tour is indicated by bold lines.

Fig. 9
Fig. 9

(a) JTC input plane (contrast-inverted picture) for the five-city TSP shown in Fig. 8. (b) Enlarged picture of the left-upper portion of the binary matrix shown in (a).

Fig. 10
Fig. 10

JTC Fourier plane (contrast-inverted picture) for the five-city TSP shown in Fig. 8.

Fig. 11
Fig. 11

(Color online) JTC output plane for the five-city TSP shown in Fig. 8: (a) Entire output plane (contrast-inverted picture) obtained by simulation. (b) Zoomed-in picture of the right-bottom correlation matrix shown in (a). (c) Comparison between the cross section across the middle row of the correlation matrix obtained by simulation (dashed curve) and by experiment (solid curve).

Fig. 12
Fig. 12

Experimental results (contrast-inverted pictures) for the five-city TSP shown in Fig. 8: (a) One of the side orders on the JTC Fourier plane, (b) one of the correlation matrices on the JTC output plane.

Fig. 13
Fig. 13

(Color online) Comparison between the computation times of the optical and electronic processors for various TSP ranks.

Equations (21)

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

K symmetric = ( N 1 ) ! / 2 ,
M symmetric = N ( N 1 ) / 2.
K asymmetric = ( N 1 ) ! ,
M asymmetric = N ( N 1 ) .
Tour   1 : City   1 City   2 City   3 City   4 City   1 ,
Tour   2 : C i t y  1 City   3 City   4 City   2 City   1 ,
Tour   3 : City   1 City   4 City   2 City   3 City   1 .
Tour   1: l 1 = w 1 , 2 + w 2 , 3 + w 3 , 4 + w 1 , 4 ,
Tour   2 : l 2 = w 1 , 3 + w 3 , 4 + w 2 , 4 + w 1 , 2 ,
Tour   3 : l 3 = w 1 , 4 + w 2 , 4 + w 2 , 3 + w 1 , 3 .
w = [ w 1 , 2 , w 1 , 3 , w 1 , 4 , w 2 , 3 , w 2 , 4 , w 3 , 4 ] T ,
b = [ 1 0 1 1 0 1 1 1 0 0 1 1 0 1 1 1 1 0 ] .
l = b w = [ w 1 , 2 + 0 + w 1 , 4 + w 2 , 3 + 0 + w 3 , 4 w 1 , 2 + w 1 , 3 + 0 + 0 + w 2 , 4 + w 3 , 4 0 + w 1 , 3 + w 1 , 4 + w 2 , 3 + w 2 , 4 + 0 ]
= [ w 1 , 2 + w 1 , 4 + w 2 , 3 + w 3 , 4 w 1 , 2 + w 1 , 3 + w 2 , 4 + w 3 , 4 w 1 , 3 + w 1 , 4 + w 2 , 3 + w 2 , 4 ] = [ l 1 l 2 l 3 ] .
b initial = b N = 3 = T 1 T 2 [ 1 0 0 1 0 1 0 1 1 0 1 0 ] , w 1 , 2 w 1 , 3 w 2 , 1 w 2 , 3 w 3 , 2 w 3 , 1
w = [ w 1 , 2 , w 1 , 3 , w 1 , 4 , w 1 , 5 ,   , w 1 , i ,   , w 1 , N , w 2 , 1 , w 2 , 3 , w 2 , 4 , w 2 , 5 ,   , w 2 , i ,   , w 2 , N , w 3 , 2 , w 3 , 1 , w 3 , 4 , w 3 , 5 ,   , w 3 , i ,   , w 3 , N , w 4 , 2 , w 4 , 3 , w 4 , 1 , w 4 , 5 ,   , w 4 , i ,   , w 4 , N , w N , 2 , w N , 3 , w N , 4 , w N , 5 ,   , w N , i ,   , w N , N 1 , w N , 1 ] T .
G S i , j = G S max w i , j min ( w ) max ( w ) min ( w ) { G S max G S min } ,
U 1 ( x 1 , y 1 ) = [ b ( x 1 X b , y 1 + Y b ) + w ( x 1 + X w , y 1 Y w ) ] × n rect [ x 1 cos θ + y 1 sin θ n α α / 2 ] ,
U 2 ( x 2 , y 2 ) = A 1 [ B ( μ x 2 , μ y 2 ) e j 2 π μ ( x 2 X b y 2 Y b ) + W ( μ x 2 , μ y 2 ) e j 2 π μ ( x 2 X w y 2 Y W ) ] [ sinc ( μ α ( x 2 cos θ + y 2 sin θ ) 2 ) × m δ ( x 2 cos θ + y 2 sin θ m μ α ) ] ,
I 2 ( x 2 , y 2 ) = A 2 | B ( μ x 2 , μ y 2 ) e j 2 π μ ( x 2 X b y 2 Y b ) + W ( μ x 2 , μ y 2 ) e j 2 π μ ( x 2 X w y 2 Y w ) | 2 = A 2 [ | B ( μ x 2 , μ y 2 ) | 2 + | W ( μ x 2 , μ y 2 ) | 2 + B ( μ x 2 , μ y 2 ) W * ( μ x 2 , μ y 2 ) e j 2 π μ [ x 2 ( X b + X w ) y 2 ( Y b + Y w ) ] + B * ( μ x 2 , μ y 2 ) W ( μ x 2 , μ y 2 ) e j 2 π μ [ x 2 ( X b + X w ) y 2 ( Y b + Y w ) ] ] ,
U 3 ( x 3 , y 3 ) = ( A 2 / μ ) [ b ( x 3 , y 3 ) b ( x 3 , y 3 ) + w ( x 3 , y 3 ) w ( x 3 , y 3 ) + b ( x 3 , y 3 ) w ( x 3 , y 3 ) δ ( x 3 ( X b + X w ) , y 3 + ( Y b + Y w ) ) + w ( x 3 , y 3 ) b ( x 3 , y 3 ) δ ( x 3 + ( X b + X w ) , y 3 ( Y b + Y w ) ) ] ,

Metrics