bounded NP-complete
Optical binary-matrix synthesis for solving bounded NP-complete combinatorial problems
Natan T.Shaked,MEMBER SPIE
Ben-Gurion University of the Negev Department of Electrical and Computer Engineering
P.O.Box653
Beer-Sheva84105,Israel
E-mail:natis@ee.bgu.ac.il
Tal Tabib
Gil Simon
Ben-Gurion University of the Negev Department of Electrical and Computer Engineering
P.O.Box653
Beer-Sheva84105,Israel
Stephane Messika
Shlomi Dolev
Ben-Gurion University of the Negev Department of Computer Science
P.O.Box653
Beer-Sheva84105,Israel
Joseph Rosen,MEMBER SPIE
Ben-Gurion University of the Negev Department of Electrical and Computer Engineering
P.O.Box653
Beer-Sheva84105,Israel Abstract.An optical method for synthesizing a binary matrix represent-ing all feasible solutions of a bounded?input length restricted?NP-complete combinatorial problem is presented.After the preparation of this matrix,an optical matrix-vector multiplier can be used in order to multiply the synthesized binary matrix and a grayscale vector represent-ing the weights of the problem.This yields the required solution vector. The synthesis of the binary matrix is based on an ef?cient algorithm that utilizes a small number of long-vector duplications.These duplications are performed optically by using an optical correlator.Simulations and experimental results are given.?2007Society of Photo-Optical Instrumentation Engineers.?DOI:10.1117/1.2799086?
Subject terms:optical computing;matrix multiplication;correlators;Fourier optics.
Paper070027R received Jan.15,2007;revised manuscript received Apr.24, 2007;accepted for publication May4,2007;published online Oct.24,2007.This paper is a revision of a paper presented at the SPIE conference an Optical Information Systems IV,Aug.2006,San Diego,Calif.The paper presented there appears?unrefereed?in SPIE Proceedings Vol.6311.
1Introduction
Ef?cient solutions to NP-complete combinatorial problems have been the goal of many researches.1Nevertheless,none of the researches has succeeded in?nding an ef?cient polynomial-time solution to these problems.Due to the dif-?culty of solving these problems,many approximation and heuristic methods have been proposed in the literature.1,2 However,the approximation methods do not always?nd the best solution within a reasonable computation time.On the other hand,the heuristic methods are able to solve these problems quickly for certain cases only.In fact,the com-putation time of the heuristic methods may be unexpected and even longer than that of an exhaustive search?checking all possibilities in an exhaustive manner?,due to unsuccess-ful attempts at optimization.2Therefore,when there is a need to ensure a prede?ned computation time,we may pre-fer to exhaustively check all possible solutions.However, because of the vast number of possible solutions?and there-fore the intricacy of the calculation and the large amount of required memory?,conventional computers may?nd it hard to carry out this exhaustive search.
Recently,3we have proposed a new optical system de-sign that is capable of solving bounded instances of NP-complete problems,such as the traveling salesman problem ?TSP?and the Hamiltonian path problem?HPP?,by check-
ing all feasible solutions more ef?ciently than conventional computers.This design is based on a fast optical matrix-
0091-3286/2007/$25.00?2007
SPIE Fig.1Example of a?ve-node TSP.
Optical Engineering46?10?,108201?October2007?
vector multiplication between a binary matrix,representing all feasible solutions,and a weight vector,representing the problem weights.The multiplication product is a vector representing the solutions of the problem.In the TSP,the required solution is the best?shortest?tour connecting a certain set of given node coordinates,where each node co-ordinate is visited exactly once.An example of a fully con-nected TSP graph,containing?ve nodes,is shown in Fig.1. In this kind of problem,the matrix-vector multiplication is performed between a binary matrix,representing all fea-sible TSP tours,and a grayscale weight vector,representing the?nite weights between the TSP nodes.The multiplica-tion product is a length vector representing the TSP tour lengths by peaks of light with different intensities.The shortest tour can be found by using an optical polynomial-time binary search,which utilizes an optical threshold plate.On the other hand,in the HPP,a decision whether there is a path connecting two nodes on the HPP graph is required?which implies that some of the graph edges may be blocked?.In the HPP,the binary matrix still represents all feasible paths?tours?,but the elements of the weight vector in this problem are binary as well.After the matrix-vector multiplication,any peak of light?with a certain in-tensity?obtained in the output of the optical system means that a Hamiltonian path exists.
The advantage of the proposed method is that once the binary matrix is synthesized,the TSP,HPP,and other re-lated problems of the same order?with the same number of nodes?can be solved optically by only changing the weight vector and performing the matrix-vector multiplication in an optical way.This optical matrix-vector multiplication can be performed by several methods,such as the Stanford multiplier and various correlation methods.4,5
In Ref.3,we have also provided a new ef?cient algo-rithm for synthesizing the binary matrix so that it contains all the feasible tours and only them.One advantage of this algorithm is that it synthesizes a binary matrix of N nodes that also contains the binary matrices of fewer than N nodes.This means that this matrix has to be synthesized only once for all problems with N or fewer nodes.Another advantage of this algorithm is that it uses a relatively small number of iterations in order to produce big vectors by duplications of existing vectors.
The synthesized binary matrix contains a large number,?N?1?!,of rows,each row representing a different feasible tour,and a relatively small number,N?N?1?,of columns, each column representing an edge related to one of the problem weights.Taking into account the large number of rows and the fact that conventional electronic computers may?nd it hard to duplicate such huge vectors?if the num-ber of nodes,N,is large?,the optical system proposed in this paper may be a useful method for synthesizing the binary matrix.According to this optical system design,the binary matrix’s long columns are duplicated one after the other by performing a correlation operation with shifted point functions for which the shifts are given by the binary matrix algorithm.We show that the number of duplications needed in order to synthesize a binary matrix of any size can be less than N3.The proposed method is tested by both simulations and lab experiments.
The rest of the paper is organized as follows.Section2 introduces the methodology of the proposed method.Sec-tion3explains the optical implementation of the method. Sections4and5present simulation and experimental re-sults,respectively.Section6makes some concluding remarks.
2Methodology
For simplicity of explanation,let us refer to the more gen-eral case of the TSP?although,as explained earlier,similar problems,such as the HPP,can be solved by the same method?.Our solution to the TSP is based on a multiplica-tion of a binary matrix,representing all feasible tours,by a weight vector,representing the weights of the problem. In Sec.2.1we present an ef?cient algorithm for synthesiz-ing the binary matrix,and in Sec.2.2we explain how to obtain the TSP solution by performing a matrix-vector multiplication.
2.1Synthesis of the Binary Matrix
The binary-matrix algorithm is able to synthesize the binary matrix of an N-node TSP by using the binary matrix of an ?N?1?-node TSP.The main advantage of this algorithm is
that it uses duplications of large vectors?in numbers on the order of the number of the feasible tours?by employing a relatively small number of repetitions?on the order of the weight-vector length?.As we show later on,this algorithm can be implemented in a pure optical system.
The binary matrix of an N-node TSP contains?N?1?! rows,each of which represents a different tour,and N?N?1?columns,each of which represents a different edge connecting one node to another.A1in the k’th row and in the l’th column of the binary matrix means that the k’th tour contains the l’th edge.
The iterative algorithm for synthesizing the binary ma-trix starts with a binary matrix representing the case of a three-node TSP and extends this matrix iteratively to a bi-nary matrix of the TSP with the required number of nodes. This algorithm is composed of two stages:the initialization stage and the induction stage.In the initialization stage,the weights?and hence the binary-matrix’s columns?are ar-ranged in a certain order so that the resulting binary matrix has some degree of symmetry.According to this order,the weights with their second index as1?which are underlined in the following equation?replace the orderly weights w k,k: w=?w1,2,w1,3,w1,4,w1,5,…,w1,i,...,w1,N,
w2,1,w2,3,w2,4,w2,5,…,w2,i,...,w2,N,
w3,2,w3,1,w3,4,w3,5,…,w3,i,...,w3,N,
w4,2,w4,3,w4,1,w4,5,…,w4,i,...,w4,N,...,
w N,2,w N,3,w N,4,w N,5,…,w N,i...,w N,N?1,w N,1?T.?1?Next,a binary matrix containing the two feasible tours passing through three nodes is generated as follows:
b N=3=
T1
T2?1100101
1011010?
ref w1,2w1,3w2,1w2,3w3,2w3,1
,?2?
where T k indicates the binary matrix row that represents the k’th tour,and w i,j represents the weight of the edge con-necting node i and node j.Note that the left column in this
matrix,marked “ref,”is a reference column ?which is uti-lized later in this subsection ?and should not be considered when analyzing the tours represented in the matrix.As can be seen from the binary matrix in Eq.?2?,the ?rst tour T 1is node 1→node 2→node 3→node 1,whereas the second tour T 2is node 1→node 3→node 2→node 1.
In the induction stage of the transition from an ?N ?1?-node TSP to an N -node TSP,we start by de?ning a new binary matrix of size ??N ?1?!???N ?N ?1?+1?,and while the ?rst column is reserved for the reference column,the rest of the N ?N ?1?columns are reserved for the col-umns that are related to the weights.The new matrix is then divided into N ?1horizontal sections,each of which con-tains ?N ?2?!rows.Each of the columns ?except the refer-ence column ?is duplicated once from the source matrix ?the binary matrix of an ?N ?1?-node TSP ?into each of the sections of the target matrix ?the binary matrix of an N -node TSP ?,whereas the reference column is duplicated twice into each of the sections.The duplication of the col-umns from the source matrix into the target matrix,as dem-onstrated in Fig.2,is always performed by the same set of rules described below:
1.Duplicate the ?rst ?reference ?column of the source matrix:a.
Duplicate the ?rst ?reference ?column of the source matrix into the left column of each of the N ?1sections of the target matrix.This generates the new reference column in the target matrix.This rule is demonstrated by the dashed arrows in Fig.2.
b.
Duplicate the ?rst ?reference ?column of the source matrix into the columns of the target ma-trix related to the weights w 1,k +1,where k is the section number.This means to duplicate this source-matrix column into the column related to the weight w 1,2in the ?rst section of the target
matrix,into the column related to the weight w 1,3in the second section of the target matrix,and so on,until it is duplicated into the column related to the weight w 1,N in the last section of the target matrix.This rule is demonstrated by the dash-dotted arrows in Fig.2.
2.Duplication of each of the remaining ?N ?1??N ?2?columns of the source matrix:a.
Fill the ?rst section of the target matrix:Each time take a different column related to the weight w i ,j in the source matrix and duplicate it into the column related to the weight w m ,n in the ?rst sec-tion of the target matrix,following these rules:if j =1,then m =i +1and n =1.?This rule is demon-strated by the thick solid arrow in Fig.2?.Other-wise,if j 1,then m =i +1and n =j +1.?This rule is demonstrated by the thick dotted arrow in Fig.2?.
b.
Fill the remaining sections of the target-matrix:Each time take a different column related to the weight w i ,j in the source matrix and duplicate it into the column related to the weight w m ,n in the k ’th section of the target-matrix ?k ?2?following these two-step rules:First,if j =1,then m ?=i +1and n ?=1.?This rule is demonstrated by the thin solid arrows in Fig.2?.Otherwise,if j 1,then m ?=i +1and n ?=j +1.?This rule is demonstrated by the thin dotted arrows in Fig.2?.Second,if m ?=2,then m =k +1;if m ?=k +1,then m =2.Oth-erwise,if m ? 2and m ? k +1,then m =m ?.The same goes for n ?and n :If n ?=2,then n =k +1;if n ?=k +1,then n =2.Otherwise,if n ? 2and n ? k +1,then n =n ?.
3.Fill the un?lled positions in the target matrix with zeros.The preceding rules should be implemented for the tran-sition from the N =3binary matrix to the N =4binary ma-trix,for the transition from the N =4binary matrix to the N =5binary matrix,and so on,until reaching the binary matrix with the required number of nodes.
Let us compute the complexity of the induction stage,which determines the complexity of the problem.Accord-ing to rules 1a and 1b of the induction stage of the algo-rithm,the number of duplications required for the reference column is 2?N ?1?,since we have N ?1sections in the tar-get matrix.The number of columns needed to be duplicated in rules 2a and 2b is ?N ?2??N ?1??the number of the rest of the columns in the source matrix ?,and they are dupli-cated into all of the sections,which means N ?1times.Therefore,the number of single duplications required for the transition from a binary matrix of an ?N ?1?-node TSP to the binary matrix of an N -node TSP is
#Dup ?N ?1?→N ?1?=2?N ?1?+?N ?1?2
?N ?2?
=N 3?4N 2+7N ?4?O ?N 3?.?3?
Since this process is recursive,and since we start with the binary matrix of a three-node TSP,the total number
of
Fig.2Example of the transition from the binary matrix of a three-node TSP to the binary matrix of a four-node TSP according to the binary-matrix algorithm.
single duplications required for the induction stage ?which de?nes its complexity ?is
#Dup 3→N ?1?=?k =4N
?2?k ?1?+?k ?1?2?k ?2???O ?N 4
?.
?4?
If we assume that the duplication of each of the source-matrix columns into the different sections of the target ma-trix can be done simultaneously,then according to rules 1a and 1b of the induction stage of the algorithm,the number of duplications required for the reference column is 1?since it is duplicated into the target-matrix 2?N ?1?times simul-taneously ?.The number of columns needed to be duplicated in rules 2a and 2b is ?N ?2??N ?1??the number of the rest of the columns in the source matrix ?,and they are dupli-cated into all of the N ?1sections of the target matrix si-multaneously.Therefore,the number of multiple duplica-tions required for the transition from a binary matrix of an ?N ?1?-node TSP to the binary matrix of an N -node TSP is
#Dup ?N ?1?→N ?2?=1+?N ?1??N ?2?=N 2?3N +3?O ?N 2
?,
?5?
and the number of multiple duplications required for the transition from a three-node TSP into an N -node TSP ?which de?nes the complexity of the induction stage ?is given by
#Dup 3→N ?2?=?k =4N
?1+?k ?1??k ?2???O ?N 3
?.
?6?
2.2Matrix-Vector Multiplication for Obtaining the
Problem Solution
As explained before,once the N -node binary matrix is syn-thesized,it can be used to solve TSPs with N or fewer nodes.In order to obtain the TSP solution,we multiply the synthesized binary matrix by a weight vector,representing the TSP weights.The resulting product is a vector contain-ing the lengths of the TSP tours.This can be expressed mathematically by the following formula:
?
100101011010?
??w 1,2w 1,3
w 2,1
w 2,3w 3,2
w 3,1?T
=
?
w 1,2+w 2,3+w 3,1w 1,3+w 3,2+w 2,1
?
.
?7?
As can be seen from this equation,in this case the resulting
length vector contains two elements.Each element is the total length of the corresponding tour.Note that although this example is quite simple,the same method can be car-ried out for any N -node TSP.After obtaining the length vector,its minimal element coincides with the best tour.As explained before,for other NP-complete problems such as the HPP,there is no need to ?nd the best tour,since any value in the tour-length vector that is equal to N indicates that a Hamiltonian path exists.
3Optical Implementation
In Sec.2,we describe a method for solving the TSP using a multiplication of a binary matrix by a weight vector.In this section,we show how this method can be implemented optically.Our design uses the bene?ts of optics in order to perform the multiplication of the quite large binary matrix by the weight vector.This is,of course,hard to do with conventional computers,due to the vast amount of memory storage and the complexity of the calculation.Section 3.1presents the optical implementation of the binary-matrix synthesis according to the binary-matrix algorithm pro-posed in Sec.2.1,whereas Section 3.2presents the optical implementation of the matrix-vector multiplication for ob-taining the length vector of the TSP,as explained in Sec.2.2.
3.1Optical Synthesis of the Binary Matrix
The algorithm proposed in Sec.2.1can be used in order to optically synthesize the binary matrix representing all fea-sible tours of an N -node TSP.In fact,the transition to the binary matrix of an N -node TSP requires the existence of the binary matrix of an ?N ?1?-node TSP.This transition is based on duplications of large vectors.The size of the du-plicated vectors is ?N ?2?!,and the complexity of
the
Fig.34f optical system for the optical implementation of the binary-matrix algorithm.
duplication is given by Eq.?4?or?6?.The fact that large
vectors can be duplicated by optical means leads us to
choose optics for implementing the binary-matrix
algorithm.
The4f optical system6shown in Fig.3is capable of
performing a convolution between two images.This system
is utilized to carry out a vector duplication by performing a
convolution between the vector and shifted spatial delta ?point?functions.The result of this convolution is the vec-tor shifted to the locations of the delta functions.We use
pairs of symmetric delta functions in order to get a real-
valued spectral transform that can be represented on a regu-
lar slide or on a spatial light modulator?SLM?.
The binary matrix is also represented on a slide?or an
SLM?.A white rectangle on this slide represents a1in the binary matrix,and a black rectangle on the slide represents a0in this matrix.Figure3demonstrates the transition from the four-node TSP binary matrix to the?ve-node TSP bi-nary matrix.As shown in this?gure,the source matrix?the binary matrix of N?1=4nodes?is represented on the slide placed in plane P1,whereas the target matrix?the binary matrix of N=5nodes?is accumulated during the correlation iterations on a?lm?or CCD camera?,which is placed on plane P3.As shown in Fig.3,the column that we would like to duplicate?according to the binary-matrix algorithm?is extracted from the source matrix by a vertical slit.
The synthesized transformed mask of the shifted delta
functions is placed on a slide?or an SLM?in plane P2. Each delta function is shifted in both the vertical and hori-zontal directions.The vertical shift is proportional to the suitable target-matrix section?according to the binary-matrix algorithm?.On the other hand,the horizontal shift is composed of both the shift of the column in the desired horizontal direction according to the binary-matrix algo-rithm and an additional shift that assures that the target matrix will not overlap with the other spatial components appearing on plane P3.This undesired overlap may occur because the convolution with the delta functions yields two duplications:one in the positive direction from the center of plane P3,and the other in the negative direction.After duplicating each of the source-matrix columns by this pro-cess,plane P3contains the binary matrix of an N-node TSP. Then,we can utilize this matrix to synthesize the binary matrix of an?N+1?-node TSP by using the same method. This continues till reaching the binary matrix of the TSP with the desired number of nodes.
The algorithm described in Sec.2.1provides the desti-nation of the duplications for each of the source-matrix columns.This can be accomplished by either the?rst or the second method,the complexities of which are given by Eqs.?4?and?6?,respectively.In the?rst method,we per-form a duplication of each of the source-matrix columns into a single destination in the target matrix.In order to perform that optically,we convolve a pair of shifted sym-metric delta functions with the column that should be du-plicated.The transformed representation of these two sym-metric delta functions can be expressed in the spectral domain as follows:
H?1??f x,f y?=1+cos?2?f x?X+A?+2?f y Y?,?8?where f x and f y are the horizontal and vertical spatial fre-quencies,respectively;X and Y are the horizontal and ver-tical shifts,respectively,given by the binary matrix algo-rithm;and A is the horizontal shift that assures the separation of the two matrices that appear on plane P3.
In the second method,we simultaneously perform a du-plication of each of the source-matrix columns into mul-tiple destinations in the target matrix.In order to perform that optically,we convolve a set of shifted symmetric delta-function pairs with the column that is to be duplicated.The transformed representation of this set of shifted symmetric delta-function pairs can be given by the Burch method7as H?2??f x,f y?=bias+I??i???x??X i+A?,y?Y i?
+??x+?X i+A?,y+Y i???,?9?
where x and y are the horizontal and vertical axes in the spatial domain,respectively;X i and Y i are the horizontal and vertical shifts,respectively,given by the binary matrix algorithm for the i’th delta-function pair;and I is the Fou-rier transformation
operator.
Fig.44f optical system for performing the multiplication of the binary matrix by the weight vector.
3.2Optical Matrix-Vector Multiplication for Obtaining
the Problem Solution
In order to perform the matrix-vector multiplication,the same 4f optical system used in Sec.3.1can be put into action again.This time,as shown in Fig.4,the weight vector is represented on a slide ?or an SLM ?,placed in the input plane P 1,by a set of normalized grayscale rectangles.The grayscale normalization is performed so that high weights are represented by low grayscale levels.3As also shown in Fig.4,the transformed binary-matrix mask is represented on a slide ?or an SLM ?,placed in the ?lter plane P 2.In order to synthesize the transformed binary-matrix mask,we can use several methods,such as the Burch method,7the VanderLugt method,6,8etc.The output plane P 3is the correlation plane of the system,and it con-tains a correlation matrix in which the middle column rep-resents the desired product of the binary matrix with the weight vector.This product is the length vector of the TSP.In Ref.3,we use the joint transform correlator ?JTC ?6,9in order to carry out the multiplication,by using both simula-tions and lab experiments.In the current paper,we use the
4f optical system to carry out the multiplication.The binary matrix is transformed to the spectral domain by using the Burch method.The implementation of the optical matrix-vector multiplier by the 4f optical system is demonstrated in the current paper by simulations.Simulations and experi-mental results demonstrating the optical synthesis of the binary matrix,which is explained in Sec.3.1,are also given in the current paper.
4Simulation Results
This section presents the simulations performed in order to check the proposed optical method.In the ?rst simulation ?presented in Sec.4.1?,we demonstrate the synthesis of the binary matrix for the transition from the binary matrix of a four-node TSP to the binary matrix of a ?ve-node TSP,whereas in the second simulation ?presented in Sec.4.2?,we demonstrate how the synthesized binary matrix can be used to solve the ?ve-node TSP shown in Fig.
1.
Fig.5Simulation results ?contrast-inverted pictures ?:?a ?the binary matrix of a four-node TSP ?the source matrix ?;?b ?the binary matrix of a ?ve-node TSP ?the target matrix ?
.
Fig.6The ?rst eight out of 56?lters used for the transition from the binary matrix of a four-node TSP to the binary matrix of a ?ve-node TSP in the ?rst method ?duplicating into a single location each time ?.The source-matrix column tag and the target-matrix section number are written below each
?lter.Fig.7Four out of 56contrast-inverted cumulative correlation planes depicting the transition from the binary matrix of a four-node TSP to the binary matrix of a ?ve-node TSP in the ?rst method ?duplicating into a single location each time ?:?a ??rst duplication;?b ?second duplication;?c ?third duplication;?d ?last ?56th ?duplication.
4.1Simulation of the Optical Synthesis of the
Binary Matrix
In order to synthesize the binary matrix of a ?ve-node TSP,we assume the existence of a binary matrix of a four-node TSP ?which can be synthesized beforehand from the binary matrix of a three-node TSP by using the same set of rules,de?ned in Sec.2.1?.To do that,we simulate the 4f optical system illustrated in Fig.3.On the input plane P 1,we place the binary matrix of a four-node TSP ?the source matrix ?shown in Fig.5?a ?,whereas the cumulative output plane P 3will eventually contain the binary matrix of a ?ve-node TSP ?the target matrix ?shown in Fig.5?b ?.As demon-strated in Fig.3,in each iteration only a single column from the source matrix enters the system.This column is Fourier-transformed and then multiplied by the required ?l-ter,which determines the locations into which this column is duplicated on the output plane P 3.On the ?lter plane P 2,we place the ?lter mask of the transformed delta functions.Simulations of both methods discussed in Sec.3.1are presented.In the ?rst simulation,we use the ?rst method,in which each of the columns is duplicated into a single loca-tion each time.According to Eq.?3?,the number of itera-tions needed for the transition from the source matrix to the target matrix is 56.Thus,56different ?lters ?each of which is de?ned by Eq.?8??are required in order to perform this transition.Figure 6shows the ?rst eight out of the 56?lters required for the transition.Figure 7?a ?–7?d ?show the cu-mulative output plane P 3after completing the ?rst,second,third,and last ?56th ?iteration of the transition,respectively.In Fig.7?a ?,the reference column from the source matrix is duplicated into the ?rst section of the target matrix that appears in the right diffraction order of the output plane P 3.Similarly,in Fig.7?b ?and 7?c ?,the reference column from the source matrix is duplicated into the second and third sections of the target matrix,respectively.Eventually,as
shown in Fig.7?d ?,the right diffraction order of the output plane P 3contains the complete target matrix.
In the second simulation,we use the second method,in which each of the columns is duplicated into multiple loca-tions each time.According to Eq.?5?,the number of itera-tions needed for this transition is 13.Thus,only 13differ-ent ?lters ?each of which is de?ned by Eq.?9??are required in order to perform the transition.Figure 8shows these ?lters.Figure 9?a ?–9?d ?show the cumulative output plane P 3after completing the ?rst,second,third,and last ?13th ?iteration of the transition,respectively.In Fig.9?a ?,the ref-erence column from the source matrix is duplicated into the ?rst,second,third,and fourth sections of the target matrix simultaneously ?twice into each section ?.In Fig.9?b ?and 9?c ?,the second and third columns,respectively,are simul-taneously duplicated from the source matrix into each of the sections of the target matrix ?once into each section ?.Eventually,as shown in Fig.9?d ?,the right diffraction
order
Fig.8The 13?lters used for the transition from the binary matrix of a four-node TSP to the binary matrix of a ?ve-node TSP in the sec-ond method ?duplicating into multiple locations each time ?.The source-matrix column tag is written below each
?lter.
Fig.9Four out of 13contrast-inverted cumulative correlation planes depicting the transition from the binary matrix of a four-node TSP to the binary matrix of a ?ve-node TSP in the second method ?duplicating into multiple locations each time ?:?a ??rst duplication;?b ?second duplication;?c ?third duplication;?d ?last ?13th ?duplication.
of the output plane P 3contains the ?nal target matrix ?the same result achieved in the ?rst method,as shown in Fig.7?d ??.
For both methods,the required binary matrix of a ?ve-node TSP ?the target matrix ?can be easily cut out from the right diffraction order of the output plane P 3that appears in Fig.7?d ?or 9?d ?.The left-diffraction-order matrix is an abnormal binary matrix caused by the inverse duplication of the delta function,due to the Burch method and to the fact that not all of the columns are symmetric.
Once the binary matrix of a ?ve-node TSP is obtained,we can use it either to solve any TSP of ?ve or fewer nodes,or to synthesize the binary matrix of a six-node TSP by utilizing the same set of rules ?de?ned in Sec.2.1?.4.2Simulation of the Optical Matrix-Vector
Multiplication for Obtaining the Problem Solution In this subsection,we demonstrate the solution of the TSP shown in Fig.1.This is performed ?according to the tech-nique explained in Sec.3.2?by correlating the suitable grayscale weight vector with the binary matrix of a ?ve-node TSP ?Fig.5?b ??that is synthesized in Sec.3.1.This grayscale weight vector,placed on the input plane P 1in the 4f optical system illustrated in Fig.4,is shown in Fig.10?a ?.The Burch mask of the synthesized binary matrix,used as the ?lter ?plane P 2?of the 4f optical system illus-trated in Fig.4,is shown in Fig.10?b ?.The result of the correlation operation appears on the output plane P 3of the
4f optical system illustrated in Fig.4.This output plane is shown in Fig.10?c ?,and it contains two correlation matri-ces,the right matrix of which can be used for the determi-nation of the best tour.This tour is indicated by the stron-gest spot ?or the highest peak ?in the middle column of this correlation matrix.The peak heights across this middle col-umn are displayed by bars in Fig.10?d ?.As seen in this ?gure,the highest bar appears in the place representing
the
Fig.10Simulation results of multiplying the binary matrix by the weight vector in order to obtain the TSP solution:?a ?the contrast-inverted weight vector corresponding to the ?ve-node TSP in Fig.1;?b ?the Burch mask of the synthesized binary matrix in Fig.5?b ?;?c ?the contrast-inverted correlation plane containing two diffraction orders,the right order of which is the correlation matrix;?d ?bars representing the peaks across the middle column of the correlation
matrix.
Fig.11The optical experiment setup.
seventh tour.This is the shortest tour and thus the solution to the TSP.Going back to the binary matrix ?shown in Fig.5?b ??reveals that this tour contains the following weights:w 1,3,w 2,4,w 3,2,w 4,5,w 5,1,which means that the shortest TSP tour is node 1→node 3→node 2→node 4→node 5→node 1.As can be concluded from Fig.1,this is indeed the shortest tour.
5Experimental Results
In this section,we demonstrate by an experiment the syn-thesis of the binary matrix of a ?ve-node TSP ?the target matrix ?by using the binary matrix of a four-node TSP ?the source matrix ?.This is performed by implementing the ?rst method ?demonstrated by a simulation in Sec. 4.1?,in which each column from the source matrix is duplicated into a single location in the target matrix each time.Figure 11shows a photograph of the experiment setup.As can be seen in this ?gure,a laser ?Uniphase 1144/P,17mW,632.8nm,HeNe polarized laser ?beam is expanded using a beam expander and illuminates the input plane ?P 1in Fig.3?,which is accomplished in the experiment by a regular slide.A lens with a focal length of 25cm Fourier-transforms the source-matrix column appearing on the in-put plane,and the Fourier transform is multiplied by the ?lter plane ?P 2in Fig.3?,which is accomplished in the
experiment by a computer-controlled SLM ?CRL Opto XGA2,1024?768pixels ?.Fifty-six ?lters are projected on the SLM ?the ?rst several ones of which are shown in Fig.6?.Then,another lens with a focal length of 30cm Fourier-transforms the multiplication result,and the output plane ?P 3in Fig.3?contains the duplication of the source-matrix column into the suitable location in the target matrix.A CCD camera ?Sony XC75-CE ?is placed in the output plane and records the intensity distribution there.The cumulative output plane,composed of the summation of the 56result-ing correlation planes,is shown in Fig.12?a ?.As seen in this ?gure,this plane indeed contains the target matrix ?the binary matrix of a ?ve-node TSP ?,and it can be compared with the cumulative correlation plane shown in Fig.7?d ?,obtained by simulation.Note that since the CCD camera aperture is not large enough to contain the binary matrix of a ?ve-node TSP,we have performed the task by concatenat-ing two CCD camera planes.
The precision of the binary matrix is extremely impor-tant,since after the synthesis of this matrix,every row in the matrix is multiplied,element by element,by the weight vector and summed into a single value representing a tour length.Therefore,an improvement of the experimental bi-nary matrix shown in Fig.12?a ?is required.This matrix has two unwanted artifacts,which are mainly caused by the medium quality of the SLM used in the ?lter plane of the 4f optical system synthesizing the binary matrix.These arti-facts are the following:?a ?background noise and low-intensity unwanted duplications appear on the cumulative output plane of the optical system;?b ?the light intensity on the output plane is not equally distributed along the binary-matrix columns.In order to eliminate artifact ?b ?,one has to equalize the light intensity along the columns.This can be done during the synthesis of the binary matrix by multiply-ing each duplicated column by a prede?ned mask placed just in front of the output plane.The transparency values in this mask should turn brighter from its left side to its right side for each concatenated CCD plane in order to compen-sate for the unequal light intensity values along the binary matrix columns.Artifact ?a ??the background noise and the low intensity unwanted duplications ?can be eliminated by applying a constant threshold with the CCD camera ?or with any other detector used in the output plane,such as an optical ?lm ?for each duplicated column during the synthe-sis of the binary matrix ?right after the equalization mask has been applied to this duplicated column ?.
Figure 12?b ?shows the experimental binary matrix after the multiplication by the equalization mask and after apply-ing a constant threshold eliminating the lowest 15%of the values in the output plane during the binary-matrix synthe-sis.The experimental binary matrix shown in Fig.12?b ?gives only 1.4%erroneous bits,compared to a resized ver-sion of the simulated binary matrix shown in Fig.5?b ?.Further suppression of the erroneous bits of the experimen-tal binary matrix might be obtained by using more precise optomechanical devices,which are not available in our laboratory at present.
6Discussion
The experimental results given in the previous section dem-onstrate a simple proof-of-principle case.However,note that in order to enable a single run ?without repetitions ?
of
Fig.12The accumulated binary matrix of a ?ve-node TSP obtained experimentally:?a ?without the equalization and the thresholding;?b ?with the equalization and the thresholding.
the proposed method for solving bigger problems with more nodes by using the currently available technologies, the authors think that high-resolution optical?lms should be employed in the input and output planes of the optical system used for synthesizing the binary matrix.The input ?lm will contain the?N?1?-node TSP binary matrix,and on correlating each of this matrix’s columns with suitable shifted delta functions,the N-node TSP binary matrix will be accumulated on the output?lm.After developing the output?lm,it can be used as the input?lm of the optical system synthesizing the?N+1?-node TSP binary matrix,or alternatively can be used for solving any TSP or HPP con-taining N or fewer nodes.In spite of the N?3relatively long development processes of the?lms,needed for obtain-ing the N-node TSP binary matrix,the required?lm has to be produced only once for solving any TSP or HPP con-taining N or fewer nodes,no matter what the problem weights are.Thus,the process of producing such a?lm can be considered as preprocessing,or as a preproduction of special optical hardware.
The use of a?lm to represent the binary matrix has another important advantage:the nonlinearities of the?lm can be exploited during the binary matrix synthesis in order to perform an automatic thresholding process10,11on the duplicated columns.As explained in Sec.5,this threshold-ing process is important for obtaining a binary matrix with high accuracy.
The authors are aware that currently the proposed opti-cal system cannot compete with electronic computers for TSPs or HPPs of high rank,due to technological limita-tions.In the future,decreasing the wavelength?which means being able to represent bigger binary matrices?or performing optical iterations with faster SLMs may help if and when the relevant technologies are improved.There-fore,we believe that the proposed optical system is impor-tant in its own right.
In addition,even with the currently available technolo-gies,the proposed method has two important features that might make it very useful for many practical applications. These features are the following:?a?the calculation time for obtaining the?nal solution is de?ned in advance?since all the feasible solutions are checked and no heuristic or approximation methods are used?;?b?after the initial prepa-ration of the binary matrix,the proposed optical system has real-time performance for TSPs and HPPs of low rank?up
to15nodes?.These two features of the optical system can
be exploited for cryptography,real-time satellite route de-
cisions,and in general for real-time decision making.
Let us demonstrate the real-time performance of the op-
tical system and compare it with the performance of an
electronic computer for a13-node HPP.In this problem,the
number of weights in the?binary?weight vector is12?13=156,whereas the number of feasible tours is12! =4.79?108.Therefore,the number of elements in the bi-
nary matrix is?156+1??4.79?108=7.52?1010.Let us assume the use of a Stanford vector-matrix incoherent multiplier.12The matrix in this multiplier can be repre-sented on an optical?lm?slide?,whereas the input vector can be represented by vertical-cavity surface-emitting la-sers?VCSELs?that can be controlled by a125-MHz,9-bit driver.As a result,the dynamic range of the weight vector is9bits,which directly affects the accuracy of the optical
system so that it cannot solve problems in which the inter-
connecting weights are represented by more than9bits.
Under the assumption that the resolution of the binary ma-trix?lm is1?m per binary matrix element,a27.4?27.4-cm?lm can contain the binary matrix of the13-node problem.After the preproduction of this?lm,the mul-
tiplication of the weight vector,representing the problem
weights,by the synthesized binary matrix,representing all
feasible tours of the problem,can be performed in the time
frame it takes the light to pass through the optical system
plus the time it takes to represent the weight vector con-
taining156elements by the VCSEL array,which makes up
a total of a few nanoseconds.This can be considered as
real-time performance.On the other hand,a conventional
computer,working in a frequency of a few gigahertz,can-
not check4.79?108tours?without using heuristic or ap-
proximation methods?in less than a few tenths of a second,
which means that it is8orders of magnitude slower than
what can be achieved by the proposed optical system,and
this cannot be considered as real-time performance.
7Conclusion
We have proposed an optical method for solving?bounded-
length input instances of?NP-complete problems,such as
the TSP and the HPP.The method exhaustively checks all
feasible solutions of the problem.There is a need to solve
this kind of problems by an exhaustive search in order to
ensure a prede?ned solution time.According to the pro-
posed method,we multiply a binary matrix,representing all
feasible tours,by a weight vector,representing the weights
of the problem.We have also provided an ef?cient algo-
rithm for the synthesis of the binary matrix.Once this ma-
trix is synthesized,it can be used to solve all TSPs and
HPPs with the same number of nodes or fewer.The syn-
thesis of the binary matrix is demonstrated by both com-
puter simulations and an optical experiment.There is good
agreement between the simulation and the experimental re-
sults.Currently,it is feasible to exhaustively solve TSPs
and HPPs which contain15or fewer nodes by a single
iteration of the proposed optical method within nanosec-
onds?can be considered as real-time performance?,whereas
a conventional electronic computer can perform this ex-
haustive search only within tens of seconds?cannot be con-
sidered as real-time performance?.There is still a problem
in solving,within a single optical iteration,TSPs and HPPs
with more than15nodes,due to the large size of their
binary matrices.Decreasing the wavelength might help re-
duce the size of the binary matrix and thus enable the so-
lutions of larger TSPs and HPPs.Decrease of the wave-
length,however,is currently quite limited by the currently
available light sources and SLMs.Anyway,in our opinion the real-time performance of the system,which can be ob-tained for small TSPs and HPPs?up to15nodes?by using the currently available technologies,testi?es to the advan-tages of the optical system.A possible direction of a future research in this?eld is to extend the proposed method to solving other NP-complete problems or other dif?cult problems.
Acknowledgments
This research was supported by the Israel Science Founda-tion Grant 119?03as well as by Intel,Deutsche Telecom,Rita Altura Trust Chair in Computer Sciences,and the Israel Ministry of Science.References
1.M.R.Garey and D.S.Johnson,Computers and Intractability.A Guide to the Theory of NP-completeness ,W.H.Freeman and Com-pany,New York ?1979?.
2. D.Gutfreund,R.Shaltiel,and A.Ta-Shma,“If NP languages are hard
on the worst-case then it is easy to ?nd their hard instances,”in Proc.20th Annual Conf.on Computational Complexity (CCC),IEEE ?2005?.Longer version available on the Web at http://www.cs.tau.ac.il/amnon/Papers/https://www.wendangku.net/doc/f715592146.html,05.journal.ps.
3.N.T.Shaked,S.Messika,S.Dolev,and J.Rosen,“Optical solution for bounded NP-complete problems,”Appl.Opt.46?5?,711–724?2007?.
4.J.W.Goodman,Introduction to Fourier Optics ,2nd ed.,pp.282–289,McGraw-Hill,New York ?1996?.
5. A.D.McAulay,Optical Computer Architectures:the Application of
Optical Concepts to Next Generation Computers ,pp.289–299,Wiley,New York ?1991?.
6.J.W.Goodman,Introduction to Fourier Optics ,2nd ed.,pp.232–246,McGraw-Hill,New York ?1996?.
7.J.J.Burch,“Computer algorithm for the synthesis of spatial fre-quency ?lters,”Proc.IEEE 55,599–601?1967?.
8. A.VanderLugt,“Signal detection by complex spatial ?ltering,”IEEE Trans.Inf.Theory IT-10,139–145?1964?.
9. C.S.Weaver and J.W.Goodman,“A technique for optically con-volving two functions,”Appl.Opt.5,1248–1249?1966?.
10. D.G.Feitelson,Optical Computing:A Survey for Computer Scien-tists ,p.98,MIT Press,Cambridge,MA ?1988?.
11.N.H.Farhat,“Nonlinear optical data processing and ?ltering:a fea-sibility study,”IEEE https://www.wendangku.net/doc/f715592146.html,put.24?4?,443–448?1975?.
12.J.W.Goodman,Introduction to Fourier Optics ,2nd ed.,
pp.284–286,McGraw-Hill,New York ?1996?
.Natan T.Shaked received his BSc and MSc ?summa cum laude ?degrees in electri-cal and computer engineering from Ben-Gurion University of the Negev,Beer Sheva,Israel,in 2002and 2004,respec-tively.Currently,he is working on his PhD in electrical and computer engineering and is an instructor in the Department of Electrical and Computer Engineering,Ben-Gurion University of the Negev.He has coauthored six scienti?c papers in refereed journals and
presented his work at seven different academic conferences.His current research interests include incoherent white-light holography and optical computing and
processing.
Tal Tabib received his BSc degree in elec-trical and computer engineering from Ben-Gurion University of the Negev in 2006.In his BSc,he majored in computers and com-munication systems,and performed ?nal BSc project in optics ?contributed to this pa-per ?.Currently,he is working as a logic de-sign engineer at a leading communication company providing unique wireless LAN so-
lutions.
Gil Simon received his BSc degree in elec-trical and computer engineering from Ben-Gurion University of the Negev in 2006.In his BSc,he majored in electro-optics,com-puter networking,and digital signal process-ing,and performed BSc project in optics ?contributed to this paper ?.Currently,he is working toward his MSc in digital signal pro-cessing at Tel-Aviv University,Israel,and is a hardware engineer at a leading company providing highly integrated silicon
solutions.
Stephane Messika has been a computer science assistant professor at Orsay Paris-Sud University since 2005.After receiving his MSc degree in mathematics,he com-pleted his PhD degree at école Normale Supérieure ?ENS ?Cachan,France in 2004.During his postdoctoral studies at Ben-Gurion University of the Negev,he worked on optical solutions of instances of NP-complete problems.His research interests include probabilistic algorithms,model
checking,and formal veri?cation.He received the Best Student Pa-per prize at the DISC 2004conference for his work on coupling for probabilistic
algorithms.
Shlomi Dolev received his BSc degree in engineering and BA degree in computer sci-ence in 1984and 1985,respectively,and his MSc and DSc degrees in computer sci-ence in 1990and 1992,respectively,from the Technion-Israel Institute of Technology.He is the author of the book Self-Stabilization ,published by the MIT Press in 2000,and is an associate editor of IEEE Transactions on Computers and of the AIAA Journal of Aerospace Computing,Informa-tion,and Communication .He established the Computer Science Department at Ben-Gurion University of the Negev,and served as the ?rst chair of this department.He is now a professor and holds the Rita Altura Trust Chair in Computer Sciences.His current re-search interests include distributed computing,distributed systems,communication networks,self-stabilization systems,cryptography,and optical
computing.
Joseph Rosen received his BSc,MSc,and DSc degrees in electrical engineering from the Technion-Israel Institute of Technology in 1984,1987,and 1992,respectively.He is currently a professor in the Department of Electrical and Computer Engineering,Ben-Gurion University of the Negev.He is a fel-low of the Optical Society of America and has coauthored more than 70scienti?c pa-pers in refereed journals.His research inter-ests include image processing,holography,
diffractive optics,interferometry,pattern recognition,optical comput-ing,and statistical optics.