Jsun Yui Wong
"Solving systems of nonlinear equations is perhaps the most difficult problem in all of numerical computation," Rice [1, 1993, p. 355].
Modeled after the computer program in the June 30 post of the present blog, the computer program below tries to find multiple integer solutions of the following nonlinear system from Bellido [2, p. 348; 3, p. I-14]. These equations are used in line 1142 through line 1225 below.
Line 0 and line 3 of the computer program below are noteworthy.
X(1)^2+X(2)^2+X(3)^2-12*X(1)-68=0
X(4)^2+X(5)^2+X(6)^2-12*X(5)-68=0
X(7)^2+X(8)^2+X(9)^2-24*X(8)-12*X(9)+100=0
X(1)*X(4)+X(2)*X(5)+X(3)*X(6)-6*X(1)-6*X(5)-52=0
X(1)*X(7)+X(2)*X(8)+X(3)*X(9)-6*X(1)-12*X(8)-6*X(9)+64=0
X(4)*X(7)+X(5)*X(8)+X(6)*X(9)-6*X(5)-12*X(8)-6*X(9)+32=0
2*X(2)+2*X(3)-X(4)-X(5)-2*X(6)-X(7)-X(9)+18=0
X(1)+X(2)+2*X(3)+2*X(4)+2*X(6)-2*X(7)+X(8)-X(9)-38=0
X(1)+X(3)-2*X(4)+X(5)-X(6)+2*X(7)-2*X(8)+8=0
0 DEFINT A-Z
3 DEFDBL M,P,L
4 DIM X(42),A(42),L(33),K(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
91 FOR KK=1 TO 9
94 A(KK)=-100+FIX(RND*201)
95 NEXT KK
126 IMAR=10+FIX(RND*10000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 9
131 X(K)=A(K)
132 NEXT K
181 J=1+FIX(RND*9)
182 X(J)=-100+FIX(RND*201)
1142 L1=X(1)^2+X(2)^2+X(3)^2-12*X(1)-68
1143 L2=X(4)^2+X(5)^2+X(6)^2-12*X(5)-68
1144 L3=X(7)^2+X(8)^2+X(9)^2-24*X(8)-12*X(9)+100
1145 L4=X(1)*X(4)+X(2)*X(5)+X(3)*X(6)-6*X(1)-6*X(5)-52
1146 L5=X(1)*X(7)+X(2)*X(8)+X(3)*X(9)-6*X(1)-12*X(8)-6*X(9)+64
1147 L6=X(4)*X(7)+X(5)*X(8)+X(6)*X(9)-6*X(5)-12*X(8)-6*X(9)+32
1221 L7=2*X(2)+2*X(3)-X(4)-X(5)-2*X(6)-X(7)-X(9)+18
1223 L8=X(1)+X(2)+2*X(3)+2*X(4)+2*X(6)-2*X(7)+X(8)-X(9)-38
1225 L9=X(1)+X(3)-2*X(4)+X(5)-X(6)+2*X(7)-2*X(8)+8
1230 P1NEWMAY=-ABS(L1)-ABS(L2)-ABS(L3)-ABS(L4)-ABS(L5)-ABS(L6)-ABS(L7)-ABS(L8)-ABS(L9)
1448 P=P1NEWMAY
1451 IF P<=M THEN 1670
1657 FOR KEW=1 TO 9
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 LL1=L1:LL2=L2:LL3=L3:LL4=L4:LL5=L5:LL6=L6:LL7=L7:LL8=L8:LL9=L9
1666 GOTO 128
1670 NEXT I
1890 IF M>-1 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5),A(6),A(7),A(8),A(9)
1913 PRINT M,JJJJ
1914 PRINT LL1,LL2,LL3,LL4,LL5,LL6,LL7,LL8,LL9,M
1999 NEXT JJJJ
The BASIC computer program above was run with Microsoft's GW BASIC 3.11 interpreter, which is not a compiler. Its complete output through
JJJJ=-19985 is presented below. What immediately follows is a manual copy from the computer screen.
4 0 10 0 4
10 0 8 14
0 -27393
0 0 0 0 0
0 0 0 0 0
4 0 10 0 4
10 0 8 14
0 -25657
0 0 0 0 0
0 0 0 0 0
4 0 10 0 4
10 0 8 14
0 -24235
0 0 0 0 0
0 0 0 0 0
12 8 2 8 12
2 8 16 6
0 -19985
0 0 0 0 0
0 0 0 0 0
Interpreted in accordance with line 1912 through line 1914, the output above was obtained in two hours on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
[1] J. Rice. Numerical methods, software, and analysis, second ed. Academic Press, 1993.
[2] A.-M. Bellido. Construction of iteration functions for the simultaneous computation of the solutions of equations and algebraic systems. Numerical Algorithms 6 (1994) 317-351.
[3] A.-M. Bellido. "Construction of iteration functions for the simultaneous computation of the solutions of equations and algebraic systems," Seminaire d'ANALYSE NUMERIQUE, Annee 1991-1992, pp. I-1 to I-16. Universite Paul Sabatier de Toulouse, U.F.R. Mathematiques, Informatique, Gestion.
[4] W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery. Numerical recipes: the art of scientific computing, third ed. Cambridge University Press, 2007.
[5] Microsoft Corp. BASIC, second edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.
Tuesday, April 27, 2010
Sunday, April 25, 2010
In Search of Multiple Integer Solutions of a Nonlinear System of Nine Equations from the Literature
Jsun Yui Wong
"Solving systems of nonlinear equations is perhaps the most difficult problem in all of numerical computation," Rice [1, 1993, p. 355].
Modelled on the computer program in the June 30 post of the present blog, the computer program below tries to find multiple integer solutions of the following nonlinear system from Bellido [2, p. 348; 3, p. I-14]. These equations are used in line 1142 through line 1225 below.
X(1)^2+X(2)^2+X(3)^2-12*X(1)-68=0
X(4)^2+X(5)^2+X(6)^2-12*X(5)-68=0
X(7)^2+X(8)^2+X(9)^2-24*X(8)-12*X(9)+100=0
X(1)*X(4)+X(2)*X(5)+X(3)*X(6)-6*X(1)-6*X(5)-52=0
X(1)*X(7)+X(2)*X(8)+X(3)*X(9)-6*X(1)-12*X(8)-6*X(9)+64=0
X(4)*X(7)+X(5)*X(8)+X(6)*X(9)-6*X(5)-12*X(8)-6*X(9)+32=0
2*X(2)+2*X(3)-X(4)-X(5)-2*X(6)-X(7)-X(9)+18=0
X(1)+X(2)+2*X(3)+2*X(4)+2*X(6)-2*X(7)+X(8)-X(9)-38=0
X(1)+X(3)-2*X(4)+X(5)-X(6)+2*X(7)-2*X(8)+8=0
0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
91 FOR KK=1 TO 9
94 A(KK)=-100+FIX(RND*201)
95 NEXT KK
126 IMAR=10+FIX(RND*10000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 9
131 X(K)=A(K)
132 NEXT K
181 J=1+FIX(RND*9)
182 X(J)=-100+FIX(RND*201)
1142 L1=X(1)^2+X(2)^2+X(3)^2-12*X(1)-68
1143 L2=X(4)^2+X(5)^2+X(6)^2-12*X(5)-68
1144 L3=X(7)^2+X(8)^2+X(9)^2-24*X(8)-12*X(9)+100
1145 L4=X(1)*X(4)+X(2)*X(5)+X(3)*X(6)-6*X(1)-6*X(5)-52
1146 L5=X(1)*X(7)+X(2)*X(8)+X(3)*X(9)-6*X(1)-12*X(8)-6*X(9)+64
1147 L6=X(4)*X(7)+X(5)*X(8)+X(6)*X(9)-6*X(5)-12*X(8)-6*X(9)+32
1221 L7=2*X(2)+2*X(3)-X(4)-X(5)-2*X(6)-X(7)-X(9)+18
1223 L8=X(1)+X(2)+2*X(3)+2*X(4)+2*X(6)-2*X(7)+X(8)-X(9)-38
1225 L9=X(1)+X(3)-2*X(4)+X(5)-X(6)+2*X(7)-2*X(8)+8
1230 P1NEWMAY=-ABS(L1)-ABS(L2)-ABS(L3)-ABS(L4)-ABS(L5)-ABS(L6)-ABS(L7)-ABS(L8)-ABS(L9)
1448 P=P1NEWMAY
1451 IF P<=M THEN 1670
1657 FOR KEW=1 TO 9
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 LL1=L1:LL2=L2:LL3=L3:LL4=L4:LL5=L5:LL6=L6:LL7=L7:LL8=L8:LL9=L9
1666 GOTO 128
1670 NEXT I
1890 IF M>-1 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5),A(6),A(7),A(8),A(9)
1913 PRINT M,JJJJ
1914 PRINT LL1,LL2,LL3,LL4,LL5,LL6,LL7,LL8,LL9,M
1999 NEXT JJJJ
The BASIC computer program above was run with Microsoft's GW BASIC 3.11 interpreter, which is not a compiler. Its complete output through
JJJJ=-19985 is presented below. What immediately follows is a manual copy from the computer screen.
4 0 10 0 4
10 0 8 14
0 -27393
0 0 0 0 0
0 0 0 0 0
4 0 10 0 4
10 0 8 14
0 -25657
0 0 0 0 0
0 0 0 0 0
4 0 10 0 4
10 0 8 14
0 -24235
0 0 0 0 0
0 0 0 0 0
12 8 2 8 12
2 8 16 6
0 -19985
0 0 0 0 0
0 0 0 0 0
Interpreted in accordance with line 1912 through line 1914, the output above was obtained in four hours on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
[1] J. Rice. Numerical methods, software, and analysis, second ed. Academic Press, 1993.
[2] A.-M. Bellido. Construction of iteration functions for the simultaneous computation of the solutions of equations and algebraic systems. Numerical Algorithms 6 (1994) 317-351.
[3] A.-M. Bellido. "Construction of iteration functions for the simultaneous computation of the solutions of equations and algebraic systems," Seminaire d'ANALYSE NUMERIQUE, Annee 1991-1992, pp. I-1 to I-16. Universite Paul Sabatier de Toulouse, U.F.R. Mathematiques, Informatique, Gestion.
[4] W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery. Numerical recipes: the art of scientific computing, third ed. Cambridge University Press, 2007.
[5] Microsoft Corp. BASIC, second edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.
"Solving systems of nonlinear equations is perhaps the most difficult problem in all of numerical computation," Rice [1, 1993, p. 355].
Modelled on the computer program in the June 30 post of the present blog, the computer program below tries to find multiple integer solutions of the following nonlinear system from Bellido [2, p. 348; 3, p. I-14]. These equations are used in line 1142 through line 1225 below.
X(1)^2+X(2)^2+X(3)^2-12*X(1)-68=0
X(4)^2+X(5)^2+X(6)^2-12*X(5)-68=0
X(7)^2+X(8)^2+X(9)^2-24*X(8)-12*X(9)+100=0
X(1)*X(4)+X(2)*X(5)+X(3)*X(6)-6*X(1)-6*X(5)-52=0
X(1)*X(7)+X(2)*X(8)+X(3)*X(9)-6*X(1)-12*X(8)-6*X(9)+64=0
X(4)*X(7)+X(5)*X(8)+X(6)*X(9)-6*X(5)-12*X(8)-6*X(9)+32=0
2*X(2)+2*X(3)-X(4)-X(5)-2*X(6)-X(7)-X(9)+18=0
X(1)+X(2)+2*X(3)+2*X(4)+2*X(6)-2*X(7)+X(8)-X(9)-38=0
X(1)+X(3)-2*X(4)+X(5)-X(6)+2*X(7)-2*X(8)+8=0
0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
91 FOR KK=1 TO 9
94 A(KK)=-100+FIX(RND*201)
95 NEXT KK
126 IMAR=10+FIX(RND*10000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 9
131 X(K)=A(K)
132 NEXT K
181 J=1+FIX(RND*9)
182 X(J)=-100+FIX(RND*201)
1142 L1=X(1)^2+X(2)^2+X(3)^2-12*X(1)-68
1143 L2=X(4)^2+X(5)^2+X(6)^2-12*X(5)-68
1144 L3=X(7)^2+X(8)^2+X(9)^2-24*X(8)-12*X(9)+100
1145 L4=X(1)*X(4)+X(2)*X(5)+X(3)*X(6)-6*X(1)-6*X(5)-52
1146 L5=X(1)*X(7)+X(2)*X(8)+X(3)*X(9)-6*X(1)-12*X(8)-6*X(9)+64
1147 L6=X(4)*X(7)+X(5)*X(8)+X(6)*X(9)-6*X(5)-12*X(8)-6*X(9)+32
1221 L7=2*X(2)+2*X(3)-X(4)-X(5)-2*X(6)-X(7)-X(9)+18
1223 L8=X(1)+X(2)+2*X(3)+2*X(4)+2*X(6)-2*X(7)+X(8)-X(9)-38
1225 L9=X(1)+X(3)-2*X(4)+X(5)-X(6)+2*X(7)-2*X(8)+8
1230 P1NEWMAY=-ABS(L1)-ABS(L2)-ABS(L3)-ABS(L4)-ABS(L5)-ABS(L6)-ABS(L7)-ABS(L8)-ABS(L9)
1448 P=P1NEWMAY
1451 IF P<=M THEN 1670
1657 FOR KEW=1 TO 9
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 LL1=L1:LL2=L2:LL3=L3:LL4=L4:LL5=L5:LL6=L6:LL7=L7:LL8=L8:LL9=L9
1666 GOTO 128
1670 NEXT I
1890 IF M>-1 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5),A(6),A(7),A(8),A(9)
1913 PRINT M,JJJJ
1914 PRINT LL1,LL2,LL3,LL4,LL5,LL6,LL7,LL8,LL9,M
1999 NEXT JJJJ
The BASIC computer program above was run with Microsoft's GW BASIC 3.11 interpreter, which is not a compiler. Its complete output through
JJJJ=-19985 is presented below. What immediately follows is a manual copy from the computer screen.
4 0 10 0 4
10 0 8 14
0 -27393
0 0 0 0 0
0 0 0 0 0
4 0 10 0 4
10 0 8 14
0 -25657
0 0 0 0 0
0 0 0 0 0
4 0 10 0 4
10 0 8 14
0 -24235
0 0 0 0 0
0 0 0 0 0
12 8 2 8 12
2 8 16 6
0 -19985
0 0 0 0 0
0 0 0 0 0
Interpreted in accordance with line 1912 through line 1914, the output above was obtained in four hours on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
[1] J. Rice. Numerical methods, software, and analysis, second ed. Academic Press, 1993.
[2] A.-M. Bellido. Construction of iteration functions for the simultaneous computation of the solutions of equations and algebraic systems. Numerical Algorithms 6 (1994) 317-351.
[3] A.-M. Bellido. "Construction of iteration functions for the simultaneous computation of the solutions of equations and algebraic systems," Seminaire d'ANALYSE NUMERIQUE, Annee 1991-1992, pp. I-1 to I-16. Universite Paul Sabatier de Toulouse, U.F.R. Mathematiques, Informatique, Gestion.
[4] W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery. Numerical recipes: the art of scientific computing, third ed. Cambridge University Press, 2007.
[5] Microsoft Corp. BASIC, second edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.
Thursday, April 15, 2010
Solving a Nonlinear System of Four Equations from the Literature
Solving a Nonlinear System of Four Equations from the Literature
Jsun Yui Wong
"Solving systems of nonlinear equations is perhaps the most difficult problem in all of numerical computation," Rice [1, 1993, p. 355].
Originally intended for nonlinear integer programming, the following computer program tries to solve the following nonlinear system, which is based on a system in Shoup [2, pp. 40-41]. These equations are used in line 1141 through line 1150 below. As indicated in line 1157 through line 1160, tolerances of .0001s are used.
5*X(1)+3*X(2)+X(3)+X(4)=15
X(1)*X(2)+X(2)*X(3)+X(3)*X(4)=17
X(1)^2+X(2)^2+X(3)^2-X(4)^2=9
X(1)*X(3)+X(2)*X(4)+X(1)^3=8
0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
91 FOR KK=1 TO 4
94 A(KK)=-5+RND*10
95 NEXT KK
126 IMAR=10+FIX(RND*5000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 4
131 X(K)=A(K)
132 NEXT K
181 J=1+FIX(RND*4)
183 R=(1-RND*2)*A(J)
191 IF RND<.14 THEN X(J)=-5+RND*10 ELSE IF RND<.17 THEN X(J)=A(J)+R ELSE IF RND<.2 THEN X(J)=A(J)+RND*R ELSE IF RND<.25 THEN X(J)=A(J)+RND^2*R ELSE IF RND<.33 THEN X(J)=A(J)+RND^3*R ELSE IF RND<.5 THEN X(J)=A(J)+RND^4*R ELSE X(J)=INT(-5+RND*10)
1141 X(4)=-5*X(1)-3*X(2)-X(3)+15
1145 L1=X(1)*X(2)+X(2)*X(3)+X(3)*X(4)-17
1149 L2=X(1)^2+X(2)^2+X(3)^2-X(4)^2-9
1150 L3=X(1)*X(3)+X(2)*X(4)+X(1)^3-8
1152 L1K=L1
1153 L2K=L2
1154 L3K=L3
1157 IF ABS(L1)>.0001 THEN L1=-ABS(L1)*9999999! ELSE L1=0
1159 IF ABS(L2)>.0001 THEN L2=-ABS(L2)*9999999! ELSE L2=0
1160 IF ABS(L3)>.0001 THEN L3=-ABS(L3)*9999999! ELSE L3=0
1230 P1NEWMAY=L1+L2+L3
1448 P=P1NEWMAY
1451 IF P<=M THEN 1670
1657 FOR KEW=1 TO 4
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 LL1=L1K:LL2=L2K:LL3=L3K
1670 NEXT I
1890 IF M>-5 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),M,JJJJ,LL1,LL2,LL3
1999 NEXT JJJJ
The BASIC computer program above was run with Microsoft's GW BASIC 3.11 interpreter, which is not a compiler. Its complete output through JJJJ=-21946 is presented below. What immediately follows is a manual copy from the computer screen.
1 1 4 3 0
-30258 0 0 0
1 1 4 3 0
-28543 0 0 0
1 1 4 3 0
-21946 0 0 0
Interpreted in accordance with line 1912, the output above was obtained in thirty minutes on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
[1] J. Rice. Numerical methods, software, and analysis, second ed. Academic Press, 1993.
[2] T. E. Shoup. A Practical guide to computer methods for engineers. Prentice-Hall, 1979.
[3] W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery. Numerical recipes: the art of scientific computing, third ed. Cambridge University Press, 2007.
[4] Microsoft Corp. BASIC, second edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.
Jsun Yui Wong
"Solving systems of nonlinear equations is perhaps the most difficult problem in all of numerical computation," Rice [1, 1993, p. 355].
Originally intended for nonlinear integer programming, the following computer program tries to solve the following nonlinear system, which is based on a system in Shoup [2, pp. 40-41]. These equations are used in line 1141 through line 1150 below. As indicated in line 1157 through line 1160, tolerances of .0001s are used.
5*X(1)+3*X(2)+X(3)+X(4)=15
X(1)*X(2)+X(2)*X(3)+X(3)*X(4)=17
X(1)^2+X(2)^2+X(3)^2-X(4)^2=9
X(1)*X(3)+X(2)*X(4)+X(1)^3=8
0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
91 FOR KK=1 TO 4
94 A(KK)=-5+RND*10
95 NEXT KK
126 IMAR=10+FIX(RND*5000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 4
131 X(K)=A(K)
132 NEXT K
181 J=1+FIX(RND*4)
183 R=(1-RND*2)*A(J)
191 IF RND<.14 THEN X(J)=-5+RND*10 ELSE IF RND<.17 THEN X(J)=A(J)+R ELSE IF RND<.2 THEN X(J)=A(J)+RND*R ELSE IF RND<.25 THEN X(J)=A(J)+RND^2*R ELSE IF RND<.33 THEN X(J)=A(J)+RND^3*R ELSE IF RND<.5 THEN X(J)=A(J)+RND^4*R ELSE X(J)=INT(-5+RND*10)
1141 X(4)=-5*X(1)-3*X(2)-X(3)+15
1145 L1=X(1)*X(2)+X(2)*X(3)+X(3)*X(4)-17
1149 L2=X(1)^2+X(2)^2+X(3)^2-X(4)^2-9
1150 L3=X(1)*X(3)+X(2)*X(4)+X(1)^3-8
1152 L1K=L1
1153 L2K=L2
1154 L3K=L3
1157 IF ABS(L1)>.0001 THEN L1=-ABS(L1)*9999999! ELSE L1=0
1159 IF ABS(L2)>.0001 THEN L2=-ABS(L2)*9999999! ELSE L2=0
1160 IF ABS(L3)>.0001 THEN L3=-ABS(L3)*9999999! ELSE L3=0
1230 P1NEWMAY=L1+L2+L3
1448 P=P1NEWMAY
1451 IF P<=M THEN 1670
1657 FOR KEW=1 TO 4
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 LL1=L1K:LL2=L2K:LL3=L3K
1670 NEXT I
1890 IF M>-5 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),M,JJJJ,LL1,LL2,LL3
1999 NEXT JJJJ
The BASIC computer program above was run with Microsoft's GW BASIC 3.11 interpreter, which is not a compiler. Its complete output through JJJJ=-21946 is presented below. What immediately follows is a manual copy from the computer screen.
1 1 4 3 0
-30258 0 0 0
1 1 4 3 0
-28543 0 0 0
1 1 4 3 0
-21946 0 0 0
Interpreted in accordance with line 1912, the output above was obtained in thirty minutes on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
[1] J. Rice. Numerical methods, software, and analysis, second ed. Academic Press, 1993.
[2] T. E. Shoup. A Practical guide to computer methods for engineers. Prentice-Hall, 1979.
[3] W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery. Numerical recipes: the art of scientific computing, third ed. Cambridge University Press, 2007.
[4] Microsoft Corp. BASIC, second edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.
Sunday, March 28, 2010
A Heuristic Nonlinear Integer Programming Solver Applied to a Nonlinear Programming Problem
Jsun Yui Wong
The computer program listed below tries to solve the following problem from pages 572-574 of Goldstein and Price [1].
Minimize EXP(USQ)+(SIN(4*X(1)-3*X(2)))^4+(1/2)*(2*X(1)+X(2)-10)^2
where USQ is ( (1/2)*(X(1)^2+X(2)^2-25) )^2.
0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
91 FOR KK=1 TO 2
94 A(KK)=RND*5
95 NEXT KK
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 2
131 X(K)=A(K)
132 NEXT K
181 J=1+FIX(RND*2)
183 RC=(1-RND*2)*A(J)
191 IF RND<.17 THEN X(J)=RND*5 ELSE IF RND<.2 THEN X(J)=A(J)+(RC) ELSE IF RND<.25 THEN X(J)=A(J)+(RND*RC) ELSE IF RND<.33 THEN X(J)=A(J)+(RND^2*RC) ELSE IF RND<.5 THEN X(J)=A(J)+(RND^3*RC) ELSE X(J)=A(J)+(RND^4*RC)
1221 USQ=((1/2)*(X(1)^2+X(2)^2-25))^2
1222 IF USQ>88.02969 GOTO 1670
1228 P1NEWMAY=-EXP(USQ)-(SIN(4*X(1)-3*X(2)))^4-(1/2)*(2*X(1)+X(2)-10)^2
1448 P=P1NEWMAY
1451 IF P<=M THEN 1670
1657 FOR KEW=1 TO 2
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1670 NEXT I
1890 IF M>-1.00001 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),M,JJJJ
1999 NEXT JJJJ
The BASIC computer program above was run with Microsoft's GW BASIC 3.11 interpreter, which is not a compiler. The complete output through JJJJ=-31135 is presented below. What immediately follows is a manual copy from the computer screen.
2.999617983186508 4.000793869733004 -1.000004120842557
-31935
2.997184176516209 4.002264407964584 -1.000006155732966
-31858
3.002505007680922 3.998106750081269 -1.000004920671327
-31555
2.996787080731433 4.002527007369667 -1.000008002822571
-31473
2.999477299300685 4.000418875366682 -1.000000207975854
-31262
3.003159982826601 3.997395781740299 -1.000007940510827
-31135
Interpreted in accordance with line 1912, the output through JJJJ=-31135 was produced in forty seconds on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
[1] A. A. Goldstein, J. F. Price, "On Descent from Local Minima," Mathematics of Computation, Vol. 25, No. 115 (Jul. 1971), pp. 569-574.
[2] C. A. Floudas, P. M. Parados, "A collection of test problems for constrained global optimization," Lecture Notes in Computer Science, vol. 455, 1991.
[3] Microsoft Corp. BASIC. Second Edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.
The computer program listed below tries to solve the following problem from pages 572-574 of Goldstein and Price [1].
Minimize EXP(USQ)+(SIN(4*X(1)-3*X(2)))^4+(1/2)*(2*X(1)+X(2)-10)^2
where USQ is ( (1/2)*(X(1)^2+X(2)^2-25) )^2.
0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
91 FOR KK=1 TO 2
94 A(KK)=RND*5
95 NEXT KK
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 2
131 X(K)=A(K)
132 NEXT K
181 J=1+FIX(RND*2)
183 RC=(1-RND*2)*A(J)
191 IF RND<.17 THEN X(J)=RND*5 ELSE IF RND<.2 THEN X(J)=A(J)+(RC) ELSE IF RND<.25 THEN X(J)=A(J)+(RND*RC) ELSE IF RND<.33 THEN X(J)=A(J)+(RND^2*RC) ELSE IF RND<.5 THEN X(J)=A(J)+(RND^3*RC) ELSE X(J)=A(J)+(RND^4*RC)
1221 USQ=((1/2)*(X(1)^2+X(2)^2-25))^2
1222 IF USQ>88.02969 GOTO 1670
1228 P1NEWMAY=-EXP(USQ)-(SIN(4*X(1)-3*X(2)))^4-(1/2)*(2*X(1)+X(2)-10)^2
1448 P=P1NEWMAY
1451 IF P<=M THEN 1670
1657 FOR KEW=1 TO 2
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1670 NEXT I
1890 IF M>-1.00001 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),M,JJJJ
1999 NEXT JJJJ
The BASIC computer program above was run with Microsoft's GW BASIC 3.11 interpreter, which is not a compiler. The complete output through JJJJ=-31135 is presented below. What immediately follows is a manual copy from the computer screen.
2.999617983186508 4.000793869733004 -1.000004120842557
-31935
2.997184176516209 4.002264407964584 -1.000006155732966
-31858
3.002505007680922 3.998106750081269 -1.000004920671327
-31555
2.996787080731433 4.002527007369667 -1.000008002822571
-31473
2.999477299300685 4.000418875366682 -1.000000207975854
-31262
3.003159982826601 3.997395781740299 -1.000007940510827
-31135
Interpreted in accordance with line 1912, the output through JJJJ=-31135 was produced in forty seconds on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
[1] A. A. Goldstein, J. F. Price, "On Descent from Local Minima," Mathematics of Computation, Vol. 25, No. 115 (Jul. 1971), pp. 569-574.
[2] C. A. Floudas, P. M. Parados, "A collection of test problems for constrained global optimization," Lecture Notes in Computer Science, vol. 455, 1991.
[3] Microsoft Corp. BASIC. Second Edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.
Sunday, March 7, 2010
A Heuristic Nonlinear Integer Solver Applied to a Nonlinear Integer Problem from the Literature, Second Edition
Jsun Yui Wong
The following computer program tries to solve the following problem from page 102 of Conley (1980) and from page 123 of Mohan and Nguyen (1999). Maximize X(1)^2+X(1)*X(2)-X(2)^2+X(3)*X(1)-X(3)^2+8*X(4)^2-17*X(5)^2+6*X(6)^3+X(6)*X(5)*X(4)*X(7)+X(8)^3+X(9)^4-X(10)^5-X(10)*X(5)+18*X(3)*X(7)*X(6) subject to 0<=X(i)<=99 and integer for i=1,2,3,...,10.
0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(142),A(142),L(33),K(133),HR(111),F(33),J(33)
19 FOR JJJJ=-32000 TO 32000
20 RANDOMIZE JJJJ
21 M=-1D+17
91 FOR KK=1 TO 10
94 A(KK)=FIX(RND*100)
95 NEXT KK
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 10
131 X(K)=A(K)
132 NEXT K
181 J=1+FIX(RND*10)
192 X(J)=FIX(RND*100)
1225 P1NEWWAY=X(1)^2+X(1)*X(2)-X(2)^2+X(3)*X(1)-X(3)^2+8*X(4)^2-17*X(5)^2+6*X(6)^3+X(6)*X(5)*X(4)*X(7)+X(8)^3+X(9)^4-X(10)^5-X(10)*X(5)+18*X(3)*X(7)*X(6)
1448 P=P1NEWWAY
1451 IF P<=M THEN 1670
1657 FOR KEW=1 TO 10
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>216300717# THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1984 PRINT M,JJJJ
1999 NEXT JJJJ
The BASIC computer program above was run with Microsoft's GW BASIC 3.11 interpreter, which is not a compiler. Its complete output through JJJJ=-31979 is presented below. What immediately follows is a manual copy from the computer screen.
99 50 99 99 99
99 99 99 99 0
216300719 -31991
99 50 99 99 99
99 99 99 99 0
216300719 -31989
99 50 99 99 99
99 99 99 99 0
216300719 -31983
99 49 99 99 99
99 99 99 99 0
216300719 -31982
99 50 99 99 99
99 99 99 99 0
216300719 -31979
Interpreted in accordance with line 1912 through line 1914, the output through JJJJ=-31979 was produced in five seconds on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
W. Conley. Computer Optimization Techniques. Petrocelli Books Inc., New York, 1980.
D. Li and X. Sun. Nonlinear Integer Programming. Springer Science + Business Media, LLC, New York, 2006.
Microsoft Corp. BASIC. Second Edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.
C. Mohan and H. T. Nguyen. A controlled random search techniques incorporating the simulated annealling concept for solving integer and mixed integer global optimization problems. Computational Optimization and Applications, 14: 103-132, 1999.
The following computer program tries to solve the following problem from page 102 of Conley (1980) and from page 123 of Mohan and Nguyen (1999). Maximize X(1)^2+X(1)*X(2)-X(2)^2+X(3)*X(1)-X(3)^2+8*X(4)^2-17*X(5)^2+6*X(6)^3+X(6)*X(5)*X(4)*X(7)+X(8)^3+X(9)^4-X(10)^5-X(10)*X(5)+18*X(3)*X(7)*X(6) subject to 0<=X(i)<=99 and integer for i=1,2,3,...,10.
0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(142),A(142),L(33),K(133),HR(111),F(33),J(33)
19 FOR JJJJ=-32000 TO 32000
20 RANDOMIZE JJJJ
21 M=-1D+17
91 FOR KK=1 TO 10
94 A(KK)=FIX(RND*100)
95 NEXT KK
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 10
131 X(K)=A(K)
132 NEXT K
181 J=1+FIX(RND*10)
192 X(J)=FIX(RND*100)
1225 P1NEWWAY=X(1)^2+X(1)*X(2)-X(2)^2+X(3)*X(1)-X(3)^2+8*X(4)^2-17*X(5)^2+6*X(6)^3+X(6)*X(5)*X(4)*X(7)+X(8)^3+X(9)^4-X(10)^5-X(10)*X(5)+18*X(3)*X(7)*X(6)
1448 P=P1NEWWAY
1451 IF P<=M THEN 1670
1657 FOR KEW=1 TO 10
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>216300717# THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1984 PRINT M,JJJJ
1999 NEXT JJJJ
The BASIC computer program above was run with Microsoft's GW BASIC 3.11 interpreter, which is not a compiler. Its complete output through JJJJ=-31979 is presented below. What immediately follows is a manual copy from the computer screen.
99 50 99 99 99
99 99 99 99 0
216300719 -31991
99 50 99 99 99
99 99 99 99 0
216300719 -31989
99 50 99 99 99
99 99 99 99 0
216300719 -31983
99 49 99 99 99
99 99 99 99 0
216300719 -31982
99 50 99 99 99
99 99 99 99 0
216300719 -31979
Interpreted in accordance with line 1912 through line 1914, the output through JJJJ=-31979 was produced in five seconds on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.
References
W. Conley. Computer Optimization Techniques. Petrocelli Books Inc., New York, 1980.
D. Li and X. Sun. Nonlinear Integer Programming. Springer Science + Business Media, LLC, New York, 2006.
Microsoft Corp. BASIC. Second Edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.
C. Mohan and H. T. Nguyen. A controlled random search techniques incorporating the simulated annealling concept for solving integer and mixed integer global optimization problems. Computational Optimization and Applications, 14: 103-132, 1999.
Monday, January 11, 2010
A Heuristic Nonlinear Integer Solver Applied to a One-Dimensional Space Allocation Problem with Eighty Departments/Facilities, Second Edition
Jsun Yui Wong
"These tests suggest that LB1 is adequate for problems with up to 35 departments. For larger problems, the linear programs become too large and too difficult to solve with the currently available LP solvers" (Amaral 2009). "Our computational results suggest that this approach can routinely obtain optimal layouts for SRFLPs with up to 25 facilities in a few hours, and in several dozen hours for SRFLPs with up to 30 facilities" (Anjos and Vannelli 2008).
This paper is concerned with the ordering problem of Simmons (1969). Specifically, the computer program listed below tries to solve a case with eighty departments/facilities. The half lengths of the eighty departments are shown in line 11 through line 20; these half lengths are used in line 1335.
The flows are shown in line 684 through line 1005. These flows were not chosen scientifically. These flows are not random mainly because line 991 is repeated 14 times; line 991 by itself is more random than that. The other flows and some flows of line 991 were obtained from Nugent et al. (1968; all of the flows from the n=20 case and from the n=30 case) and from Skorin-Kapov (1990; all of the flows from the 42-department/facility case). Not all of the flows in line 1005 are needed.
The following computer program is a heuristic procedure. To be within .1% of the unknown optimal objective function value is the research goal. The present strategy is to use the multi-computer method that uses a number of personal computers running simultaneously and independently. To save human labor, each computer runs a very slightly different computer program. For example, if there are three computers, one computer can run with 1126 IMAR=10+RND*5000, the second can run with 1126 IMAR=10+RND*6000, and the third can run with 1126 IMAR=10+RND*7000. Otherwise the three computer programs are the same. This method is illustrated below.
0 DEFINT A-Z
1 DEFSNG S,M
2 DIM X(82),A(82)
4 DIM HS(82,82),HR(82),MP(82,82)
5 FOR IZ=1 TO 80
6 REM
7 READ HR(IZ)
8 REM
9 NEXT IZ
10 REM
11 DATA 10,10,10,10,10,10,10,10,10,10
12 DATA 20,20,20,20,20,20,20,20,20,20
13 DATA 20,20,20,20,20,20,20,20,20,20
14 DATA 20,20,20,20,20,20,20,20,20,20
15 DATA 20,20,20,20,20,20,20,20,20,20
16 DATA 20,20,20,20,20,20,20,20,20,20
17 DATA 20,20,20,20,20,20,20,20,20,20
20 DATA 30,30,30,30,30,30,30,30,30,30
679 FOR IZ=1 TO 79
680 FOR JZ=IZ+1 TO 80
681 READ HS(IZ,JZ)
682 NEXT JZ
683 NEXT IZ
684 DATA 0,5,0,5,2,10,3,1,5,5,5,0,0,5,4,4,0,0,1
685 DATA 3,10,5,1,5,1,2,4,2,5,0,10,10,3,0,5,10,5
686 DATA 2,0,5,2,4,4,5,0,0,0,5,1,0,0,5,0,0
687 DATA 1,0,5,2,1,0,10,2,2,0,2,1,5,2,5,5
688 DATA 5,6,5,2,5,2,0,5,1,1,1,5,2,5,1
689 DATA 5,2,1,6,0,0,10,0,2,0,1,0,1,5
690 DATA 0,0,0,5,10,2,2,5,1,2,1,0,10
691 DATA 1,1,10,10,2,0,10,2,5,2,2,10
692 DATA 2,0,3,5,5,0,5,0,0,0,2
693 DATA 5,5,0,5,1,0,0,5,5,2
694 DATA 5,2,5,1,10,0,2,2,5
695 DATA 2,10,5,0,1,1,2,5
696 DATA 2,2,1,0,0,0,5
697 DATA 5,5,1,5,5,0
698 DATA 3,0,5,10,10
699 DATA 0,0,2,0
700 DATA 5,2,0
701 DATA 1,1
702 DATA 6
784 DATA 2,10,5,4,1,5,6,5,0,2,0,0,1,2,5,0,5,0,2,5,5,0,10,0,1,4,2,0,0,0,2,0,5,5,0,10,10,0,0,0,2
785 DATA 1,0,5,1,0,0,0,2,1,0,5,10,0,1,0,10,10,0,2,1,1,0,0,3,5,10,0,5,0,2,1,1,3,10,5,0,10,0,1,4
786 DATA 0,1,5,10,0,0,1,0,5,0,3,2,5,1,5,0,1,1,1,5,1,2,2,0,1,1,5,2,6,1,1,0,10,5,10,5,5,2,1
787 DATA 0,1,0,0,10,2,1,2,5,5,5,5,0,2,2,6,5,5,0,5,2,1,0,0,1,2,3,2,10,5,4,0,0,2,10,3,0,5
788 DATA 1,6,1,1,0,0,6,0,0,2,2,2,3,5,0,2,2,2,0,5,5,5,0,1,5,0,4,2,2,1,5,6,2,2,0,5,5
789 DATA 0,5,1,5,1,0,0,0,1,0,0,0,1,0,0,1,2,5,5,1,2,1,10,0,0,0,2,5,0,10,5,4,5,5,2,5
790 DATA 0,5,4,10,10,2,0,2,5,10,0,4,5,6,4,0,2,1,2,1,2,2,0,2,3,2,5,0,0,0,0,1,1,6,1
791 DATA 0,1,5,2,0,0,2,2,0,2,0,0,4,0,0,2,5,3,2,2,5,2,2,2,5,0,2,5,2,2,0,5,1,3
792 DATA 5,0,5,4,2,10,5,0,2,2,1,2,0,0,6,1,5,0,0,0,0,5,10,10,3,5,1,2,0,0,10,1,6
793 DATA 1,2,5,3,2,5,5,5,10,0,0,1,2,4,0,0,5,0,3,2,5,0,0,1,5,2,0,1,5,2,0,10
794 DATA 5,2,5,0,2,1,2,0,2,0,5,2,5,1,4,0,1,10,3,5,5,0,5,2,0,0,0,5,0,0,5
795 DATA 1,0,0,0,10,2,4,5,0,0,0,0,1,10,5,1,1,5,5,2,1,5,10,5,3,5,5,1,5,5
796 DATA 0,0,0,3,0,5,6,0,5,2,1,1,5,2,1,0,0,10,5,5,2,2,5,1,1,0,1,0,0
797 DATA 10,2,5,1,5,5,2,2,0,0,1,2,0,5,2,4,5,10,4,0,10,2,10,1,2,5,4,1
798 DATA 0,6,0,1,2,0,2,0,0,0,5,5,2,5,0,5,1,5,1,5,0,5,5,2,10,5,5
799 DATA 2,0,5,5,2,0,4,0,0,0,0,0,2,2,0,0,5,2,0,5,1,0,5,0,2,0
800 DATA 0,0,5,1,1,0,3,5,0,2,1,5,1,5,6,0,3,5,0,5,0,0,5,5,10
801 DATA 5,5,0,0,2,2,6,10,0,2,0,2,2,10,2,0,5,1,0,6,3,4,5,5
802 DATA 1,0,0,0,3,2,10,4,5,5,2,5,1,1,2,5,0,0,10,3,2,1,10
803 DATA 3,1,2,0,2,10,10,5,2,1,2,1,0,10,2,5,0,5,0,4,0,2
804 DATA 0,2,0,4,4,1,1,0,5,1,5,10,1,0,0,5,10,10,4,5,2
805 DATA 5,5,2,5,2,10,0,2,0,2,4,0,2,5,5,2,2,2,5,0
806 DATA 2,0,2,0,2,0,5,2,0,2,1,5,10,6,1,5,2,0,0
807 DATA 2,10,0,2,0,0,5,3,5,2,0,10,10,3,0,2,1,0
808 DATA 1,4,0,5,4,1,0,2,2,1,1,0,4,0,3,5,5
809 DATA 2,10,5,0,1,5,0,0,10,2,5,0,0,0,0,1
810 DATA 2,0,2,3,0,5,0,3,2,0,2,10,0,1,2
811 DATA 3,2,5,0,10,2,0,5,5,2,1,0,0,0
812 DATA 0,0,0,3,6,5,0,5,2,1,5,0,2
813 DATA 1,0,5,4,10,5,1,0,10,5,0,3
814 DATA 2,0,5,2,0,2,0,10,3,0,0
815 DATA 2,4,1,2,0,0,2,2,0,6,2,5,0,0,0,2,2,0,0,2,1,0,10,0,0,1,10,5,2,0,2,1,0,0,0,2,5,0,3,5,10,10,5,0,1,2,10,0,0,1,0,4,2,1,5
954 DATA 3,2,0,0,2,10,5,0,5,2,5,0,0,2,0,5,6,3,0,1,10,0,10,2,1,1,1,0,1
955 DATA 4,0,10,4,0,0,2,2,1,0,5,0,0,0,0,2,0,1,6,1,0,1,2,2,5,1,10,5
956 DATA 3,4,0,5,5,5,1,4,1,0,4,0,4,0,6,3,2,5,5,2,1,0,0,3,1,0,2
957 DATA 0,0,0,2,2,0,6,0,2,5,2,5,1,1,1,1,2,2,4,0,2,0,2,2,5,5
958 DATA 5,2,0,0,0,0,2,0,0,0,0,2,1,0,0,2,0,5,1,0,2,1,0,2,1
959 DATA 1,2,2,1,4,10,10,2,5,5,0,5,0,0,0,10,0,0,0,4,0,10,1,1
960 DATA 10,10,5,10,10,6,0,0,10,2,1,10,1,5,5,2,3,5,0,2,0,1,3
961 DATA 1,3,5,0,0,0,2,4,5,2,10,6,0,5,5,2,5,0,5,5,0,2
962 DATA 10,2,1,5,2,0,3,0,2,0,0,4,0,5,2,0,5,2,2,5,2
963 DATA 5,5,6,0,1,5,5,0,5,2,3,5,0,5,2,10,10,1,5,2
964 DATA 0,0,1,2,1,0,2,0,0,0,6,6,0,4,5,3,2,2,10
965 DATA 5,5,2,0,0,0,0,2,0,4,5,10,1,0,0,0,0,1
966 DATA 2,0,4,2,2,1,0,6,2,1,5,5,0,0,1,5,5
967 DATA 2,1,0,5,3,10,0,0,4,2,0,0,4,2,5,5,4,5,1,0,1,0,5,0,2,0,0,5,1,1,0,0,3,0,2,2,0,2,0,5,0,5,2,5,10,2,2,0,0,0,6,5,3,5,0,0,5,1
968 DATA 5,1,2,10,10,4,0,0,5,0,0,0,0,5,5,1,0,5,2,1,2,10,10
969 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2
991 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
992 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
993 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
994 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
995 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
996 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
997 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
998 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
999 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1000 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1001 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1002 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1003 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1004 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1005 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1118 FOR JJJJ=-32000 TO 32000
1119 RANDOMIZE JJJJ
1120 M=-9999999999999999#
1121 FOR ZI=1 TO 80
1122 A(ZI)=RND*10000
1123 NEXT ZI
1126 IMAR=10+RND*5000
1128 FOR I=1 TO IMAR
1129 FOR KK=1 TO 80
1131 X(KK)=A(KK)
1132 NEXT KK
1223 IJL=1+FIX(RND*80)
1255 IF RND<.9 THEN X(IJL)=RND*10000 ELSE X(IJL)=A(IJL)+1
1332 FOR IM1=1 TO 79
1334 FOR IM2=IM1+1 TO 80
1335 IF ABS(X(IM1)-X(IM2))<(HR(IM1)+HR(IM2)) THEN MP(IM1,IM2)=-9999999999# ELSE MP(IM1,IM2)=0
1338 NEXT IM2
1339 NEXT IM1
1431 SUMNL=0
1432 FOR IN1=1 TO 79
1434 FOR IN2=IN1+1 TO 80
1437 SUMNL=SUMNL+MP(IN1,IN2)
1438 NEXT IN2
1439 NEXT IN1
1631 SUMUL=0
1632 FOR IS1=1 TO 79
1634 FOR IS2=IS1+1 TO 80
1637 SUMUL=SUMUL+HS(IS1,IS2)*ABS(X(IS1)-X(IS2))
1638 NEXT IS2
1639 NEXT IS1
1646 SP=-SUMUL+SUMNL
1656 IF SP<=M THEN 1670
1657 FOR KEW=1 TO 80
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=SP
1666 GOTO 1128
1670 NEXT I
1890 IF M>-9999999! THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1914 PRINT A(11),A(12),A(13),A(14),A(15)
1915 PRINT A(16),A(17),A(18),A(19),A(20)
1916 PRINT A(21),A(22),A(23),A(24),A(25)
1917 PRINT A(26),A(27),A(28),A(29),A(30)
1918 PRINT A(31),A(32),A(33),A(34),A(35)
1919 PRINT A(36),A(37),A(38),A(39),A(40)
1920 PRINT A(41),A(42),A(43),A(44),A(45)
1921 PRINT A(46),A(47),A(48),A(49),A(50)
1922 PRINT A(51),A(52),A(53),A(54),A(55)
1923 PRINT A(56),A(57),A(58),A(59),A(60)
1924 PRINT A(61),A(62),A(63),A(64),A(65)
1925 PRINT A(66),A(67),A(68),A(69),A(70)
1926 PRINT A(71),A(72),A(73),A(74),A(75)
1927 PRINT A(76),A(77),A(78),A(79),A(80)
1959 PRINT M,JJJJ
1999 NEXT JJJJ
The BASIC computer program above was run with Microsoft's GW BASIC 3.11 interpreter, which is not a compiler. The candidate solution with the best objective function value produced during the first thirty hours of running is presented immediately below. What follows is a manual copy from the computer monitor.
4769 4224 4064 4124 4704
4553 4284 4971 3824 4452
5241 3794 3974 5142 5866
5780 4583 3334 6020 5013
4094 5284 3414 4625 2994
4417 3294 4891 5498 3134
5821 3894 3454 4334 4932
2894 5907 4522 3214 5689
4154 5324 5059 4374 4254
3374 2854 5186 5582 3534
3854 4738 5539 3934 3614
5101 5735 4799 3174 3034
4839 4194 3254 3494 4482
3694 3654 4668 3574 5432
2740 2804 3084 2944 3744
5382 5963 6070 5632 4024
-8734049 -31990
One can check the solution/result at JJJJ=-31990 to see whether there is a gap between any two adjacent facilities. If there is, then joining the two adjacent facilities together will make the actual cost of this order to be less than 8734049. There are gaps in the sequence above.
The best candidate solution from the computer running with 1126 IMAR=10+RND*6000 has the objective function value of 8859337 at JJJJ=-31996.
The best candidate solution from the computer running with 1126 IMAR=10+RND*7000 has the objective function value of 8827945 at JJJJ=-31998.
Interpreted in accordance with line 1912 through line 1959, the candidate solutions above were produced during the first thirty hours of simultaneous running on three personal computers each with the speed of about 2.66 GHz. and with the IBM basica/D interpreter.
References
Amaral, A. R. S., "A New Lower Bound for the Single Row Facility Layout Problem," Discrete Applied Mathematics 157, 183-190 (2009).
Anjos, M. F., and A. Vannelli, "Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes," INFORMS Journal on Computing 20, 611-617 (2008).
Microsoft Corp. BASIC. Second Edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.
Nugent, C. E., R. E. Vollmann, and J. Ruml, "An Experimental Comparison of Techniques for the Assignment of Facilities to Locations," Operations Research, 16 (1968), 150-173.
Simmons, D. M., "One-Dimensional Space Allocation: an Ordering Algorithm," Operations Research 17, 812-826 (1969).
Skorin-Kapov, J., "Tabu Search Applied to the Quadratic Assignment Problem," ORSA Journal on Computing 2, 33-45 (1990).
"These tests suggest that LB1 is adequate for problems with up to 35 departments. For larger problems, the linear programs become too large and too difficult to solve with the currently available LP solvers" (Amaral 2009). "Our computational results suggest that this approach can routinely obtain optimal layouts for SRFLPs with up to 25 facilities in a few hours, and in several dozen hours for SRFLPs with up to 30 facilities" (Anjos and Vannelli 2008).
This paper is concerned with the ordering problem of Simmons (1969). Specifically, the computer program listed below tries to solve a case with eighty departments/facilities. The half lengths of the eighty departments are shown in line 11 through line 20; these half lengths are used in line 1335.
The flows are shown in line 684 through line 1005. These flows were not chosen scientifically. These flows are not random mainly because line 991 is repeated 14 times; line 991 by itself is more random than that. The other flows and some flows of line 991 were obtained from Nugent et al. (1968; all of the flows from the n=20 case and from the n=30 case) and from Skorin-Kapov (1990; all of the flows from the 42-department/facility case). Not all of the flows in line 1005 are needed.
The following computer program is a heuristic procedure. To be within .1% of the unknown optimal objective function value is the research goal. The present strategy is to use the multi-computer method that uses a number of personal computers running simultaneously and independently. To save human labor, each computer runs a very slightly different computer program. For example, if there are three computers, one computer can run with 1126 IMAR=10+RND*5000, the second can run with 1126 IMAR=10+RND*6000, and the third can run with 1126 IMAR=10+RND*7000. Otherwise the three computer programs are the same. This method is illustrated below.
0 DEFINT A-Z
1 DEFSNG S,M
2 DIM X(82),A(82)
4 DIM HS(82,82),HR(82),MP(82,82)
5 FOR IZ=1 TO 80
6 REM
7 READ HR(IZ)
8 REM
9 NEXT IZ
10 REM
11 DATA 10,10,10,10,10,10,10,10,10,10
12 DATA 20,20,20,20,20,20,20,20,20,20
13 DATA 20,20,20,20,20,20,20,20,20,20
14 DATA 20,20,20,20,20,20,20,20,20,20
15 DATA 20,20,20,20,20,20,20,20,20,20
16 DATA 20,20,20,20,20,20,20,20,20,20
17 DATA 20,20,20,20,20,20,20,20,20,20
20 DATA 30,30,30,30,30,30,30,30,30,30
679 FOR IZ=1 TO 79
680 FOR JZ=IZ+1 TO 80
681 READ HS(IZ,JZ)
682 NEXT JZ
683 NEXT IZ
684 DATA 0,5,0,5,2,10,3,1,5,5,5,0,0,5,4,4,0,0,1
685 DATA 3,10,5,1,5,1,2,4,2,5,0,10,10,3,0,5,10,5
686 DATA 2,0,5,2,4,4,5,0,0,0,5,1,0,0,5,0,0
687 DATA 1,0,5,2,1,0,10,2,2,0,2,1,5,2,5,5
688 DATA 5,6,5,2,5,2,0,5,1,1,1,5,2,5,1
689 DATA 5,2,1,6,0,0,10,0,2,0,1,0,1,5
690 DATA 0,0,0,5,10,2,2,5,1,2,1,0,10
691 DATA 1,1,10,10,2,0,10,2,5,2,2,10
692 DATA 2,0,3,5,5,0,5,0,0,0,2
693 DATA 5,5,0,5,1,0,0,5,5,2
694 DATA 5,2,5,1,10,0,2,2,5
695 DATA 2,10,5,0,1,1,2,5
696 DATA 2,2,1,0,0,0,5
697 DATA 5,5,1,5,5,0
698 DATA 3,0,5,10,10
699 DATA 0,0,2,0
700 DATA 5,2,0
701 DATA 1,1
702 DATA 6
784 DATA 2,10,5,4,1,5,6,5,0,2,0,0,1,2,5,0,5,0,2,5,5,0,10,0,1,4,2,0,0,0,2,0,5,5,0,10,10,0,0,0,2
785 DATA 1,0,5,1,0,0,0,2,1,0,5,10,0,1,0,10,10,0,2,1,1,0,0,3,5,10,0,5,0,2,1,1,3,10,5,0,10,0,1,4
786 DATA 0,1,5,10,0,0,1,0,5,0,3,2,5,1,5,0,1,1,1,5,1,2,2,0,1,1,5,2,6,1,1,0,10,5,10,5,5,2,1
787 DATA 0,1,0,0,10,2,1,2,5,5,5,5,0,2,2,6,5,5,0,5,2,1,0,0,1,2,3,2,10,5,4,0,0,2,10,3,0,5
788 DATA 1,6,1,1,0,0,6,0,0,2,2,2,3,5,0,2,2,2,0,5,5,5,0,1,5,0,4,2,2,1,5,6,2,2,0,5,5
789 DATA 0,5,1,5,1,0,0,0,1,0,0,0,1,0,0,1,2,5,5,1,2,1,10,0,0,0,2,5,0,10,5,4,5,5,2,5
790 DATA 0,5,4,10,10,2,0,2,5,10,0,4,5,6,4,0,2,1,2,1,2,2,0,2,3,2,5,0,0,0,0,1,1,6,1
791 DATA 0,1,5,2,0,0,2,2,0,2,0,0,4,0,0,2,5,3,2,2,5,2,2,2,5,0,2,5,2,2,0,5,1,3
792 DATA 5,0,5,4,2,10,5,0,2,2,1,2,0,0,6,1,5,0,0,0,0,5,10,10,3,5,1,2,0,0,10,1,6
793 DATA 1,2,5,3,2,5,5,5,10,0,0,1,2,4,0,0,5,0,3,2,5,0,0,1,5,2,0,1,5,2,0,10
794 DATA 5,2,5,0,2,1,2,0,2,0,5,2,5,1,4,0,1,10,3,5,5,0,5,2,0,0,0,5,0,0,5
795 DATA 1,0,0,0,10,2,4,5,0,0,0,0,1,10,5,1,1,5,5,2,1,5,10,5,3,5,5,1,5,5
796 DATA 0,0,0,3,0,5,6,0,5,2,1,1,5,2,1,0,0,10,5,5,2,2,5,1,1,0,1,0,0
797 DATA 10,2,5,1,5,5,2,2,0,0,1,2,0,5,2,4,5,10,4,0,10,2,10,1,2,5,4,1
798 DATA 0,6,0,1,2,0,2,0,0,0,5,5,2,5,0,5,1,5,1,5,0,5,5,2,10,5,5
799 DATA 2,0,5,5,2,0,4,0,0,0,0,0,2,2,0,0,5,2,0,5,1,0,5,0,2,0
800 DATA 0,0,5,1,1,0,3,5,0,2,1,5,1,5,6,0,3,5,0,5,0,0,5,5,10
801 DATA 5,5,0,0,2,2,6,10,0,2,0,2,2,10,2,0,5,1,0,6,3,4,5,5
802 DATA 1,0,0,0,3,2,10,4,5,5,2,5,1,1,2,5,0,0,10,3,2,1,10
803 DATA 3,1,2,0,2,10,10,5,2,1,2,1,0,10,2,5,0,5,0,4,0,2
804 DATA 0,2,0,4,4,1,1,0,5,1,5,10,1,0,0,5,10,10,4,5,2
805 DATA 5,5,2,5,2,10,0,2,0,2,4,0,2,5,5,2,2,2,5,0
806 DATA 2,0,2,0,2,0,5,2,0,2,1,5,10,6,1,5,2,0,0
807 DATA 2,10,0,2,0,0,5,3,5,2,0,10,10,3,0,2,1,0
808 DATA 1,4,0,5,4,1,0,2,2,1,1,0,4,0,3,5,5
809 DATA 2,10,5,0,1,5,0,0,10,2,5,0,0,0,0,1
810 DATA 2,0,2,3,0,5,0,3,2,0,2,10,0,1,2
811 DATA 3,2,5,0,10,2,0,5,5,2,1,0,0,0
812 DATA 0,0,0,3,6,5,0,5,2,1,5,0,2
813 DATA 1,0,5,4,10,5,1,0,10,5,0,3
814 DATA 2,0,5,2,0,2,0,10,3,0,0
815 DATA 2,4,1,2,0,0,2,2,0,6,2,5,0,0,0,2,2,0,0,2,1,0,10,0,0,1,10,5,2,0,2,1,0,0,0,2,5,0,3,5,10,10,5,0,1,2,10,0,0,1,0,4,2,1,5
954 DATA 3,2,0,0,2,10,5,0,5,2,5,0,0,2,0,5,6,3,0,1,10,0,10,2,1,1,1,0,1
955 DATA 4,0,10,4,0,0,2,2,1,0,5,0,0,0,0,2,0,1,6,1,0,1,2,2,5,1,10,5
956 DATA 3,4,0,5,5,5,1,4,1,0,4,0,4,0,6,3,2,5,5,2,1,0,0,3,1,0,2
957 DATA 0,0,0,2,2,0,6,0,2,5,2,5,1,1,1,1,2,2,4,0,2,0,2,2,5,5
958 DATA 5,2,0,0,0,0,2,0,0,0,0,2,1,0,0,2,0,5,1,0,2,1,0,2,1
959 DATA 1,2,2,1,4,10,10,2,5,5,0,5,0,0,0,10,0,0,0,4,0,10,1,1
960 DATA 10,10,5,10,10,6,0,0,10,2,1,10,1,5,5,2,3,5,0,2,0,1,3
961 DATA 1,3,5,0,0,0,2,4,5,2,10,6,0,5,5,2,5,0,5,5,0,2
962 DATA 10,2,1,5,2,0,3,0,2,0,0,4,0,5,2,0,5,2,2,5,2
963 DATA 5,5,6,0,1,5,5,0,5,2,3,5,0,5,2,10,10,1,5,2
964 DATA 0,0,1,2,1,0,2,0,0,0,6,6,0,4,5,3,2,2,10
965 DATA 5,5,2,0,0,0,0,2,0,4,5,10,1,0,0,0,0,1
966 DATA 2,0,4,2,2,1,0,6,2,1,5,5,0,0,1,5,5
967 DATA 2,1,0,5,3,10,0,0,4,2,0,0,4,2,5,5,4,5,1,0,1,0,5,0,2,0,0,5,1,1,0,0,3,0,2,2,0,2,0,5,0,5,2,5,10,2,2,0,0,0,6,5,3,5,0,0,5,1
968 DATA 5,1,2,10,10,4,0,0,5,0,0,0,0,5,5,1,0,5,2,1,2,10,10
969 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2
991 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
992 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
993 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
994 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
995 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
996 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
997 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
998 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
999 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1000 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1001 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1002 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1003 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1004 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1005 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1118 FOR JJJJ=-32000 TO 32000
1119 RANDOMIZE JJJJ
1120 M=-9999999999999999#
1121 FOR ZI=1 TO 80
1122 A(ZI)=RND*10000
1123 NEXT ZI
1126 IMAR=10+RND*5000
1128 FOR I=1 TO IMAR
1129 FOR KK=1 TO 80
1131 X(KK)=A(KK)
1132 NEXT KK
1223 IJL=1+FIX(RND*80)
1255 IF RND<.9 THEN X(IJL)=RND*10000 ELSE X(IJL)=A(IJL)+1
1332 FOR IM1=1 TO 79
1334 FOR IM2=IM1+1 TO 80
1335 IF ABS(X(IM1)-X(IM2))<(HR(IM1)+HR(IM2)) THEN MP(IM1,IM2)=-9999999999# ELSE MP(IM1,IM2)=0
1338 NEXT IM2
1339 NEXT IM1
1431 SUMNL=0
1432 FOR IN1=1 TO 79
1434 FOR IN2=IN1+1 TO 80
1437 SUMNL=SUMNL+MP(IN1,IN2)
1438 NEXT IN2
1439 NEXT IN1
1631 SUMUL=0
1632 FOR IS1=1 TO 79
1634 FOR IS2=IS1+1 TO 80
1637 SUMUL=SUMUL+HS(IS1,IS2)*ABS(X(IS1)-X(IS2))
1638 NEXT IS2
1639 NEXT IS1
1646 SP=-SUMUL+SUMNL
1656 IF SP<=M THEN 1670
1657 FOR KEW=1 TO 80
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=SP
1666 GOTO 1128
1670 NEXT I
1890 IF M>-9999999! THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1914 PRINT A(11),A(12),A(13),A(14),A(15)
1915 PRINT A(16),A(17),A(18),A(19),A(20)
1916 PRINT A(21),A(22),A(23),A(24),A(25)
1917 PRINT A(26),A(27),A(28),A(29),A(30)
1918 PRINT A(31),A(32),A(33),A(34),A(35)
1919 PRINT A(36),A(37),A(38),A(39),A(40)
1920 PRINT A(41),A(42),A(43),A(44),A(45)
1921 PRINT A(46),A(47),A(48),A(49),A(50)
1922 PRINT A(51),A(52),A(53),A(54),A(55)
1923 PRINT A(56),A(57),A(58),A(59),A(60)
1924 PRINT A(61),A(62),A(63),A(64),A(65)
1925 PRINT A(66),A(67),A(68),A(69),A(70)
1926 PRINT A(71),A(72),A(73),A(74),A(75)
1927 PRINT A(76),A(77),A(78),A(79),A(80)
1959 PRINT M,JJJJ
1999 NEXT JJJJ
The BASIC computer program above was run with Microsoft's GW BASIC 3.11 interpreter, which is not a compiler. The candidate solution with the best objective function value produced during the first thirty hours of running is presented immediately below. What follows is a manual copy from the computer monitor.
4769 4224 4064 4124 4704
4553 4284 4971 3824 4452
5241 3794 3974 5142 5866
5780 4583 3334 6020 5013
4094 5284 3414 4625 2994
4417 3294 4891 5498 3134
5821 3894 3454 4334 4932
2894 5907 4522 3214 5689
4154 5324 5059 4374 4254
3374 2854 5186 5582 3534
3854 4738 5539 3934 3614
5101 5735 4799 3174 3034
4839 4194 3254 3494 4482
3694 3654 4668 3574 5432
2740 2804 3084 2944 3744
5382 5963 6070 5632 4024
-8734049 -31990
One can check the solution/result at JJJJ=-31990 to see whether there is a gap between any two adjacent facilities. If there is, then joining the two adjacent facilities together will make the actual cost of this order to be less than 8734049. There are gaps in the sequence above.
The best candidate solution from the computer running with 1126 IMAR=10+RND*6000 has the objective function value of 8859337 at JJJJ=-31996.
The best candidate solution from the computer running with 1126 IMAR=10+RND*7000 has the objective function value of 8827945 at JJJJ=-31998.
Interpreted in accordance with line 1912 through line 1959, the candidate solutions above were produced during the first thirty hours of simultaneous running on three personal computers each with the speed of about 2.66 GHz. and with the IBM basica/D interpreter.
References
Amaral, A. R. S., "A New Lower Bound for the Single Row Facility Layout Problem," Discrete Applied Mathematics 157, 183-190 (2009).
Anjos, M. F., and A. Vannelli, "Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes," INFORMS Journal on Computing 20, 611-617 (2008).
Microsoft Corp. BASIC. Second Edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.
Nugent, C. E., R. E. Vollmann, and J. Ruml, "An Experimental Comparison of Techniques for the Assignment of Facilities to Locations," Operations Research, 16 (1968), 150-173.
Simmons, D. M., "One-Dimensional Space Allocation: an Ordering Algorithm," Operations Research 17, 812-826 (1969).
Skorin-Kapov, J., "Tabu Search Applied to the Quadratic Assignment Problem," ORSA Journal on Computing 2, 33-45 (1990).
Sunday, January 10, 2010
A Heuristic Nonlinear Integer Solver Applied to a One-Dimensional Space Allocation Problem with Eighty Departments/Facilities
Jsun Yui Wong
"These tests suggest that LB1 is adequate for problems with up to 35 departments. For larger problems, the linear programs become too large and too difficult to solve with the currently available LP solvers" (Amaral 2009). "Our computational results suggest that this approach can routinely obtain optimal layouts for SRFLPs with up to 25 facilities in a few hours, and in several dozen hours for SRFLPs with up to 30 facilities" (Anjos and Vannelli 2008).
This paper is concerned with the ordering problem of Simmons (1969). Specifically, the computer program listed below tries to solve a case with eighty departments/facilities. The half lengths of the eighty departments are shown in line 11 through line 20; these half lengths are used in line 1335.
The flows are shown in line 684 through line 1005. These flows were not chosen scientifically. These flows are not random mainly because line 991 is repeated 14 times; line 991 by itself is more random than that. The other flows and some flows of line 991 were obtained from Nugent et al. (1968; all of the flows from the n=20 case and from the n=30 case) and from Skorin-Kapov (1990; all of the flows from the 42-department/facility case). Not all of the flows in line 1005 are needed.
The following computer program is a heuristic procedure. To be within .1% of the unknown optimal objective function value is the research goal. The present strategy is to use the multi-computer method that uses a number of personal computers running simultaneously and independently. To save human labor, each computer runs a very slightly different computer program. For example, if there are three computers, one computer can run with 1126 IMAR=10+RND*5000, the second can run with 1126 IMAR=10+RND*6000, and the third can run with 1126 IMAR=10+RND*7000. Otherwise the three computer programs are the same. This method is illustrated below.
0 DEFINT A-Z
1 DEFSNG S,M
2 DIM X(82),A(82)
4 DIM HS(82,82),HR(82),MP(82,82)
5 FOR IZ=1 TO 80
6 REM
7 READ HR(IZ)
8 REM
9 NEXT IZ
10 REM
11 DATA 10,10,10,10,10,10,10,10,10,10
12 DATA 20,20,20,20,20,20,20,20,20,20
13 DATA 20,20,20,20,20,20,20,20,20,20
14 DATA 20,20,20,20,20,20,20,20,20,20
15 DATA 20,20,20,20,20,20,20,20,20,20
16 DATA 20,20,20,20,20,20,20,20,20,20
17 DATA 20,20,20,20,20,20,20,20,20,20
20 DATA 30,30,30,30,30,30,30,30,30,30
679 FOR IZ=1 TO 79
680 FOR JZ=IZ+1 TO 80
681 READ HS(IZ,JZ)
682 NEXT JZ
683 NEXT IZ
684 DATA 0,5,0,5,2,10,3,1,5,5,5,0,0,5,4,4,0,0,1
685 DATA 3,10,5,1,5,1,2,4,2,5,0,10,10,3,0,5,10,5
686 DATA 2,0,5,2,4,4,5,0,0,0,5,1,0,0,5,0,0
687 DATA 1,0,5,2,1,0,10,2,2,0,2,1,5,2,5,5
688 DATA 5,6,5,2,5,2,0,5,1,1,1,5,2,5,1
689 DATA 5,2,1,6,0,0,10,0,2,0,1,0,1,5
690 DATA 0,0,0,5,10,2,2,5,1,2,1,0,10
691 DATA 1,1,10,10,2,0,10,2,5,2,2,10
692 DATA 2,0,3,5,5,0,5,0,0,0,2
693 DATA 5,5,0,5,1,0,0,5,5,2
694 DATA 5,2,5,1,10,0,2,2,5
695 DATA 2,10,5,0,1,1,2,5
696 DATA 2,2,1,0,0,0,5
697 DATA 5,5,1,5,5,0
698 DATA 3,0,5,10,10
699 DATA 0,0,2,0
700 DATA 5,2,0
701 DATA 1,1
702 DATA 6
784 DATA 2,10,5,4,1,5,6,5,0,2,0,0,1,2,5,0,5,0,2,5,5,0,10,0,1,4,2,0,0,0,2,0,5,5,0,10,10,0,0,0,2
785 DATA 1,0,5,1,0,0,0,2,1,0,5,10,0,1,0,10,10,0,2,1,1,0,0,3,5,10,0,5,0,2,1,1,3,10,5,0,10,0,1,4
786 DATA 0,1,5,10,0,0,1,0,5,0,3,2,5,1,5,0,1,1,1,5,1,2,2,0,1,1,5,2,6,1,1,0,10,5,10,5,5,2,1
787 DATA 0,1,0,0,10,2,1,2,5,5,5,5,0,2,2,6,5,5,0,5,2,1,0,0,1,2,3,2,10,5,4,0,0,2,10,3,0,5
788 DATA 1,6,1,1,0,0,6,0,0,2,2,2,3,5,0,2,2,2,0,5,5,5,0,1,5,0,4,2,2,1,5,6,2,2,0,5,5
789 DATA 0,5,1,5,1,0,0,0,1,0,0,0,1,0,0,1,2,5,5,1,2,1,10,0,0,0,2,5,0,10,5,4,5,5,2,5
790 DATA 0,5,4,10,10,2,0,2,5,10,0,4,5,6,4,0,2,1,2,1,2,2,0,2,3,2,5,0,0,0,0,1,1,6,1
791 DATA 0,1,5,2,0,0,2,2,0,2,0,0,4,0,0,2,5,3,2,2,5,2,2,2,5,0,2,5,2,2,0,5,1,3
792 DATA 5,0,5,4,2,10,5,0,2,2,1,2,0,0,6,1,5,0,0,0,0,5,10,10,3,5,1,2,0,0,10,1,6
793 DATA 1,2,5,3,2,5,5,5,10,0,0,1,2,4,0,0,5,0,3,2,5,0,0,1,5,2,0,1,5,2,0,10
794 DATA 5,2,5,0,2,1,2,0,2,0,5,2,5,1,4,0,1,10,3,5,5,0,5,2,0,0,0,5,0,0,5
795 DATA 1,0,0,0,10,2,4,5,0,0,0,0,1,10,5,1,1,5,5,2,1,5,10,5,3,5,5,1,5,5
796 DATA 0,0,0,3,0,5,6,0,5,2,1,1,5,2,1,0,0,10,5,5,2,2,5,1,1,0,1,0,0
797 DATA 10,2,5,1,5,5,2,2,0,0,1,2,0,5,2,4,5,10,4,0,10,2,10,1,2,5,4,1
798 DATA 0,6,0,1,2,0,2,0,0,0,5,5,2,5,0,5,1,5,1,5,0,5,5,2,10,5,5
799 DATA 2,0,5,5,2,0,4,0,0,0,0,0,2,2,0,0,5,2,0,5,1,0,5,0,2,0
800 DATA 0,0,5,1,1,0,3,5,0,2,1,5,1,5,6,0,3,5,0,5,0,0,5,5,10
801 DATA 5,5,0,0,2,2,6,10,0,2,0,2,2,10,2,0,5,1,0,6,3,4,5,5
802 DATA 1,0,0,0,3,2,10,4,5,5,2,5,1,1,2,5,0,0,10,3,2,1,10
803 DATA 3,1,2,0,2,10,10,5,2,1,2,1,0,10,2,5,0,5,0,4,0,2
804 DATA 0,2,0,4,4,1,1,0,5,1,5,10,1,0,0,5,10,10,4,5,2
805 DATA 5,5,2,5,2,10,0,2,0,2,4,0,2,5,5,2,2,2,5,0
806 DATA 2,0,2,0,2,0,5,2,0,2,1,5,10,6,1,5,2,0,0
807 DATA 2,10,0,2,0,0,5,3,5,2,0,10,10,3,0,2,1,0
808 DATA 1,4,0,5,4,1,0,2,2,1,1,0,4,0,3,5,5
809 DATA 2,10,5,0,1,5,0,0,10,2,5,0,0,0,0,1
810 DATA 2,0,2,3,0,5,0,3,2,0,2,10,0,1,2
811 DATA 3,2,5,0,10,2,0,5,5,2,1,0,0,0
812 DATA 0,0,0,3,6,5,0,5,2,1,5,0,2
813 DATA 1,0,5,4,10,5,1,0,10,5,0,3
814 DATA 2,0,5,2,0,2,0,10,3,0,0
815 DATA 2,4,1,2,0,0,2,2,0,6,2,5,0,0,0,2,2,0,0,2,1,0,10,0,0,1,10,5,2,0,2,1,0,0,0,2,5,0,3,5,10,10,5,0,1,2,10,0,0,1,0,4,2,1,5
954 DATA 3,2,0,0,2,10,5,0,5,2,5,0,0,2,0,5,6,3,0,1,10,0,10,2,1,1,1,0,1
955 DATA 4,0,10,4,0,0,2,2,1,0,5,0,0,0,0,2,0,1,6,1,0,1,2,2,5,1,10,5
956 DATA 3,4,0,5,5,5,1,4,1,0,4,0,4,0,6,3,2,5,5,2,1,0,0,3,1,0,2
957 DATA 0,0,0,2,2,0,6,0,2,5,2,5,1,1,1,1,2,2,4,0,2,0,2,2,5,5
958 DATA 5,2,0,0,0,0,2,0,0,0,0,2,1,0,0,2,0,5,1,0,2,1,0,2,1
959 DATA 1,2,2,1,4,10,10,2,5,5,0,5,0,0,0,10,0,0,0,4,0,10,1,1
960 DATA 10,10,5,10,10,6,0,0,10,2,1,10,1,5,5,2,3,5,0,2,0,1,3
961 DATA 1,3,5,0,0,0,2,4,5,2,10,6,0,5,5,2,5,0,5,5,0,2
962 DATA 10,2,1,5,2,0,3,0,2,0,0,4,0,5,2,0,5,2,2,5,2
963 DATA 5,5,6,0,1,5,5,0,5,2,3,5,0,5,2,10,10,1,5,2
964 DATA 0,0,1,2,1,0,2,0,0,0,6,6,0,4,5,3,2,2,10
965 DATA 5,5,2,0,0,0,0,2,0,4,5,10,1,0,0,0,0,1
966 DATA 2,0,4,2,2,1,0,6,2,1,5,5,0,0,1,5,5
967 DATA 2,1,0,5,3,10,0,0,4,2,0,0,4,2,5,5,4,5,1,0,1,0,5,0,2,0,0,5,1,1,0,0,3,0,2,2,0,2,0,5,0,5,2,5,10,2,2,0,0,0,6,5,3,5,0,0,5,1
968 DATA 5,1,2,10,10,4,0,0,5,0,0,0,0,5,5,1,0,5,2,1,2,10,10
969 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2
991 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
992 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
993 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
994 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
995 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
996 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
997 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
998 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
999 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1000 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1001 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1002 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1003 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1004 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1005 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1118 FOR JJJJ=-32000 TO 32000
1119 RANDOMIZE JJJJ
1120 M=-9999999999999999#
1121 FOR ZI=1 TO 80
1122 A(ZI)=RND*10000
1123 NEXT ZI
1126 IMAR=10+RND*7000
1128 FOR I=1 TO IMAR
1129 FOR KK=1 TO 80
1131 X(KK)=A(KK)
1132 NEXT KK
1223 IJL=1+FIX(RND*80)
1255 IF RND<.9 THEN X(IJL)=RND*10000 ELSE X(IJL)=A(IJL)+1
1332 FOR IM1=1 TO 79
1334 FOR IM2=IM1+1 TO 80
1335 IF ABS(X(IM1)-X(IM2))<(HR(IM1)+HR(IM2)) THEN MP(IM1,IM2)=-9999999999# ELSE MP(IM1,IM2)=0
1338 NEXT IM2
1339 NEXT IM1
1431 SUMNL=0
1432 FOR IN1=1 TO 79
1434 FOR IN2=IN1+1 TO 80
1437 SUMNL=SUMNL+MP(IN1,IN2)
1438 NEXT IN2
1439 NEXT IN1
1631 SUMUL=0
1632 FOR IS1=1 TO 79
1634 FOR IS2=IS1+1 TO 80
1637 SUMUL=SUMUL+HS(IS1,IS2)*ABS(X(IS1)-X(IS2))
1638 NEXT IS2
1639 NEXT IS1
1646 SP=-SUMUL+SUMNL
1656 IF SP<=M THEN 1670
1657 FOR KEW=1 TO 80
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=SP
1666 GOTO 1128
1670 NEXT I
1890 IF M>-9999999! THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1914 PRINT A(11),A(12),A(13),A(14),A(15)
1915 PRINT A(16),A(17),A(18),A(19),A(20)
1916 PRINT A(21),A(22),A(23),A(24),A(25)
1917 PRINT A(26),A(27),A(28),A(29),A(30)
1918 PRINT A(31),A(32),A(33),A(34),A(35)
1919 PRINT A(36),A(37),A(38),A(39),A(40)
1920 PRINT A(41),A(42),A(43),A(44),A(45)
1921 PRINT A(46),A(47),A(48),A(49),A(50)
1922 PRINT A(51),A(52),A(53),A(54),A(55)
1923 PRINT A(56),A(57),A(58),A(59),A(60)
1924 PRINT A(61),A(62),A(63),A(64),A(65)
1925 PRINT A(66),A(67),A(68),A(69),A(70)
1926 PRINT A(71),A(72),A(73),A(74),A(75)
1927 PRINT A(76),A(77),A(78),A(79),A(80)
1959 PRINT M,JJJJ
1999 NEXT JJJJ
The BASIC computer program above was run with Microsoft's GW BASIC 3.11 interpreter, which is not a compiler. The candidate solution with the best objective function value produced during the first twenty hours of running is presented immediately below. What follows is a manual copy from the computer monitor.
4667 4966 4929 4207 5026
5682 4587 4607 5326 5303
4517 5823 4697 4996 5137
5180 3877 4097 3497 3577
4317 4397 5400 4817 4857
6032 5056 6075 4477 6177
4437 3997 5444 5096 6219
6264 5487 4357 5713 5554
4637 3677 3797 6307 6606
3917 5221 5265 3957 5863
6397 5601 4557 5359 4177
3537 3837 3757 6116 4897
6357 5647 4237 5981 3717
4777 4277 3457 4737 4137
4047 6478 6546 3627 5914
3287 3347 3407 5764 6660
-8827945 -31998
One can check the solution/result at JJJJ=-31998 to see whether there is a gap between any two adjacent facilities. If there is, then joining the two adjacent facilities together will make the actual cost of this order to be less than
8827945. There are gaps in the sequence above.
The best candidate solution from the computer running with 1126 IMAR=10+RND*5000 has the objective function value of 8903161 at JJJJ=-32000.
The best candidate solution from the computer running with 1126 IMAR=10+RND*6000 has the objective function value of 8859337 at JJJJ=-31996.
Interpreted in accordance with line 1912 through line 1959, the candidate solutions above were produced during the first twenty hours of simultaneous running on three personal computers each with the speed of about 2.66 GHz. and with the IBM basica/D interpreter.
References
Amaral, A. R. S., "A New Lower Bound for the Single Row Facility Layout Problem," Discrete Applied Mathematics 157, 183-190 (2009).
Anjos, M. F., and A. Vannelli, "Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes," INFORMS Journal on Computing 20, 611-617 (2008).
Microsoft Corp. BASIC. Second Edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.
Nugent, C. E., R. E. Vollmann, and J. Ruml, "An Experimental Comparison of Techniques for the Assignment of Facilities to Locations," Operations Research, 16 (1968), 150-173.
Simmons, D. M., "One-Dimensional Space Allocation: an Ordering Algorithm," Operations Research 17, 812-826 (1969).
Skorin-Kapov, J., "Tabu Search Applied to the Quadratic Assignment Problem," ORSA Journal on Computing 2, 33-45 (1990).
"These tests suggest that LB1 is adequate for problems with up to 35 departments. For larger problems, the linear programs become too large and too difficult to solve with the currently available LP solvers" (Amaral 2009). "Our computational results suggest that this approach can routinely obtain optimal layouts for SRFLPs with up to 25 facilities in a few hours, and in several dozen hours for SRFLPs with up to 30 facilities" (Anjos and Vannelli 2008).
This paper is concerned with the ordering problem of Simmons (1969). Specifically, the computer program listed below tries to solve a case with eighty departments/facilities. The half lengths of the eighty departments are shown in line 11 through line 20; these half lengths are used in line 1335.
The flows are shown in line 684 through line 1005. These flows were not chosen scientifically. These flows are not random mainly because line 991 is repeated 14 times; line 991 by itself is more random than that. The other flows and some flows of line 991 were obtained from Nugent et al. (1968; all of the flows from the n=20 case and from the n=30 case) and from Skorin-Kapov (1990; all of the flows from the 42-department/facility case). Not all of the flows in line 1005 are needed.
The following computer program is a heuristic procedure. To be within .1% of the unknown optimal objective function value is the research goal. The present strategy is to use the multi-computer method that uses a number of personal computers running simultaneously and independently. To save human labor, each computer runs a very slightly different computer program. For example, if there are three computers, one computer can run with 1126 IMAR=10+RND*5000, the second can run with 1126 IMAR=10+RND*6000, and the third can run with 1126 IMAR=10+RND*7000. Otherwise the three computer programs are the same. This method is illustrated below.
0 DEFINT A-Z
1 DEFSNG S,M
2 DIM X(82),A(82)
4 DIM HS(82,82),HR(82),MP(82,82)
5 FOR IZ=1 TO 80
6 REM
7 READ HR(IZ)
8 REM
9 NEXT IZ
10 REM
11 DATA 10,10,10,10,10,10,10,10,10,10
12 DATA 20,20,20,20,20,20,20,20,20,20
13 DATA 20,20,20,20,20,20,20,20,20,20
14 DATA 20,20,20,20,20,20,20,20,20,20
15 DATA 20,20,20,20,20,20,20,20,20,20
16 DATA 20,20,20,20,20,20,20,20,20,20
17 DATA 20,20,20,20,20,20,20,20,20,20
20 DATA 30,30,30,30,30,30,30,30,30,30
679 FOR IZ=1 TO 79
680 FOR JZ=IZ+1 TO 80
681 READ HS(IZ,JZ)
682 NEXT JZ
683 NEXT IZ
684 DATA 0,5,0,5,2,10,3,1,5,5,5,0,0,5,4,4,0,0,1
685 DATA 3,10,5,1,5,1,2,4,2,5,0,10,10,3,0,5,10,5
686 DATA 2,0,5,2,4,4,5,0,0,0,5,1,0,0,5,0,0
687 DATA 1,0,5,2,1,0,10,2,2,0,2,1,5,2,5,5
688 DATA 5,6,5,2,5,2,0,5,1,1,1,5,2,5,1
689 DATA 5,2,1,6,0,0,10,0,2,0,1,0,1,5
690 DATA 0,0,0,5,10,2,2,5,1,2,1,0,10
691 DATA 1,1,10,10,2,0,10,2,5,2,2,10
692 DATA 2,0,3,5,5,0,5,0,0,0,2
693 DATA 5,5,0,5,1,0,0,5,5,2
694 DATA 5,2,5,1,10,0,2,2,5
695 DATA 2,10,5,0,1,1,2,5
696 DATA 2,2,1,0,0,0,5
697 DATA 5,5,1,5,5,0
698 DATA 3,0,5,10,10
699 DATA 0,0,2,0
700 DATA 5,2,0
701 DATA 1,1
702 DATA 6
784 DATA 2,10,5,4,1,5,6,5,0,2,0,0,1,2,5,0,5,0,2,5,5,0,10,0,1,4,2,0,0,0,2,0,5,5,0,10,10,0,0,0,2
785 DATA 1,0,5,1,0,0,0,2,1,0,5,10,0,1,0,10,10,0,2,1,1,0,0,3,5,10,0,5,0,2,1,1,3,10,5,0,10,0,1,4
786 DATA 0,1,5,10,0,0,1,0,5,0,3,2,5,1,5,0,1,1,1,5,1,2,2,0,1,1,5,2,6,1,1,0,10,5,10,5,5,2,1
787 DATA 0,1,0,0,10,2,1,2,5,5,5,5,0,2,2,6,5,5,0,5,2,1,0,0,1,2,3,2,10,5,4,0,0,2,10,3,0,5
788 DATA 1,6,1,1,0,0,6,0,0,2,2,2,3,5,0,2,2,2,0,5,5,5,0,1,5,0,4,2,2,1,5,6,2,2,0,5,5
789 DATA 0,5,1,5,1,0,0,0,1,0,0,0,1,0,0,1,2,5,5,1,2,1,10,0,0,0,2,5,0,10,5,4,5,5,2,5
790 DATA 0,5,4,10,10,2,0,2,5,10,0,4,5,6,4,0,2,1,2,1,2,2,0,2,3,2,5,0,0,0,0,1,1,6,1
791 DATA 0,1,5,2,0,0,2,2,0,2,0,0,4,0,0,2,5,3,2,2,5,2,2,2,5,0,2,5,2,2,0,5,1,3
792 DATA 5,0,5,4,2,10,5,0,2,2,1,2,0,0,6,1,5,0,0,0,0,5,10,10,3,5,1,2,0,0,10,1,6
793 DATA 1,2,5,3,2,5,5,5,10,0,0,1,2,4,0,0,5,0,3,2,5,0,0,1,5,2,0,1,5,2,0,10
794 DATA 5,2,5,0,2,1,2,0,2,0,5,2,5,1,4,0,1,10,3,5,5,0,5,2,0,0,0,5,0,0,5
795 DATA 1,0,0,0,10,2,4,5,0,0,0,0,1,10,5,1,1,5,5,2,1,5,10,5,3,5,5,1,5,5
796 DATA 0,0,0,3,0,5,6,0,5,2,1,1,5,2,1,0,0,10,5,5,2,2,5,1,1,0,1,0,0
797 DATA 10,2,5,1,5,5,2,2,0,0,1,2,0,5,2,4,5,10,4,0,10,2,10,1,2,5,4,1
798 DATA 0,6,0,1,2,0,2,0,0,0,5,5,2,5,0,5,1,5,1,5,0,5,5,2,10,5,5
799 DATA 2,0,5,5,2,0,4,0,0,0,0,0,2,2,0,0,5,2,0,5,1,0,5,0,2,0
800 DATA 0,0,5,1,1,0,3,5,0,2,1,5,1,5,6,0,3,5,0,5,0,0,5,5,10
801 DATA 5,5,0,0,2,2,6,10,0,2,0,2,2,10,2,0,5,1,0,6,3,4,5,5
802 DATA 1,0,0,0,3,2,10,4,5,5,2,5,1,1,2,5,0,0,10,3,2,1,10
803 DATA 3,1,2,0,2,10,10,5,2,1,2,1,0,10,2,5,0,5,0,4,0,2
804 DATA 0,2,0,4,4,1,1,0,5,1,5,10,1,0,0,5,10,10,4,5,2
805 DATA 5,5,2,5,2,10,0,2,0,2,4,0,2,5,5,2,2,2,5,0
806 DATA 2,0,2,0,2,0,5,2,0,2,1,5,10,6,1,5,2,0,0
807 DATA 2,10,0,2,0,0,5,3,5,2,0,10,10,3,0,2,1,0
808 DATA 1,4,0,5,4,1,0,2,2,1,1,0,4,0,3,5,5
809 DATA 2,10,5,0,1,5,0,0,10,2,5,0,0,0,0,1
810 DATA 2,0,2,3,0,5,0,3,2,0,2,10,0,1,2
811 DATA 3,2,5,0,10,2,0,5,5,2,1,0,0,0
812 DATA 0,0,0,3,6,5,0,5,2,1,5,0,2
813 DATA 1,0,5,4,10,5,1,0,10,5,0,3
814 DATA 2,0,5,2,0,2,0,10,3,0,0
815 DATA 2,4,1,2,0,0,2,2,0,6,2,5,0,0,0,2,2,0,0,2,1,0,10,0,0,1,10,5,2,0,2,1,0,0,0,2,5,0,3,5,10,10,5,0,1,2,10,0,0,1,0,4,2,1,5
954 DATA 3,2,0,0,2,10,5,0,5,2,5,0,0,2,0,5,6,3,0,1,10,0,10,2,1,1,1,0,1
955 DATA 4,0,10,4,0,0,2,2,1,0,5,0,0,0,0,2,0,1,6,1,0,1,2,2,5,1,10,5
956 DATA 3,4,0,5,5,5,1,4,1,0,4,0,4,0,6,3,2,5,5,2,1,0,0,3,1,0,2
957 DATA 0,0,0,2,2,0,6,0,2,5,2,5,1,1,1,1,2,2,4,0,2,0,2,2,5,5
958 DATA 5,2,0,0,0,0,2,0,0,0,0,2,1,0,0,2,0,5,1,0,2,1,0,2,1
959 DATA 1,2,2,1,4,10,10,2,5,5,0,5,0,0,0,10,0,0,0,4,0,10,1,1
960 DATA 10,10,5,10,10,6,0,0,10,2,1,10,1,5,5,2,3,5,0,2,0,1,3
961 DATA 1,3,5,0,0,0,2,4,5,2,10,6,0,5,5,2,5,0,5,5,0,2
962 DATA 10,2,1,5,2,0,3,0,2,0,0,4,0,5,2,0,5,2,2,5,2
963 DATA 5,5,6,0,1,5,5,0,5,2,3,5,0,5,2,10,10,1,5,2
964 DATA 0,0,1,2,1,0,2,0,0,0,6,6,0,4,5,3,2,2,10
965 DATA 5,5,2,0,0,0,0,2,0,4,5,10,1,0,0,0,0,1
966 DATA 2,0,4,2,2,1,0,6,2,1,5,5,0,0,1,5,5
967 DATA 2,1,0,5,3,10,0,0,4,2,0,0,4,2,5,5,4,5,1,0,1,0,5,0,2,0,0,5,1,1,0,0,3,0,2,2,0,2,0,5,0,5,2,5,10,2,2,0,0,0,6,5,3,5,0,0,5,1
968 DATA 5,1,2,10,10,4,0,0,5,0,0,0,0,5,5,1,0,5,2,1,2,10,10
969 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2
991 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
992 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
993 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
994 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
995 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
996 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
997 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
998 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
999 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1000 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1001 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1002 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1003 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1004 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1005 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1118 FOR JJJJ=-32000 TO 32000
1119 RANDOMIZE JJJJ
1120 M=-9999999999999999#
1121 FOR ZI=1 TO 80
1122 A(ZI)=RND*10000
1123 NEXT ZI
1126 IMAR=10+RND*7000
1128 FOR I=1 TO IMAR
1129 FOR KK=1 TO 80
1131 X(KK)=A(KK)
1132 NEXT KK
1223 IJL=1+FIX(RND*80)
1255 IF RND<.9 THEN X(IJL)=RND*10000 ELSE X(IJL)=A(IJL)+1
1332 FOR IM1=1 TO 79
1334 FOR IM2=IM1+1 TO 80
1335 IF ABS(X(IM1)-X(IM2))<(HR(IM1)+HR(IM2)) THEN MP(IM1,IM2)=-9999999999# ELSE MP(IM1,IM2)=0
1338 NEXT IM2
1339 NEXT IM1
1431 SUMNL=0
1432 FOR IN1=1 TO 79
1434 FOR IN2=IN1+1 TO 80
1437 SUMNL=SUMNL+MP(IN1,IN2)
1438 NEXT IN2
1439 NEXT IN1
1631 SUMUL=0
1632 FOR IS1=1 TO 79
1634 FOR IS2=IS1+1 TO 80
1637 SUMUL=SUMUL+HS(IS1,IS2)*ABS(X(IS1)-X(IS2))
1638 NEXT IS2
1639 NEXT IS1
1646 SP=-SUMUL+SUMNL
1656 IF SP<=M THEN 1670
1657 FOR KEW=1 TO 80
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=SP
1666 GOTO 1128
1670 NEXT I
1890 IF M>-9999999! THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1914 PRINT A(11),A(12),A(13),A(14),A(15)
1915 PRINT A(16),A(17),A(18),A(19),A(20)
1916 PRINT A(21),A(22),A(23),A(24),A(25)
1917 PRINT A(26),A(27),A(28),A(29),A(30)
1918 PRINT A(31),A(32),A(33),A(34),A(35)
1919 PRINT A(36),A(37),A(38),A(39),A(40)
1920 PRINT A(41),A(42),A(43),A(44),A(45)
1921 PRINT A(46),A(47),A(48),A(49),A(50)
1922 PRINT A(51),A(52),A(53),A(54),A(55)
1923 PRINT A(56),A(57),A(58),A(59),A(60)
1924 PRINT A(61),A(62),A(63),A(64),A(65)
1925 PRINT A(66),A(67),A(68),A(69),A(70)
1926 PRINT A(71),A(72),A(73),A(74),A(75)
1927 PRINT A(76),A(77),A(78),A(79),A(80)
1959 PRINT M,JJJJ
1999 NEXT JJJJ
The BASIC computer program above was run with Microsoft's GW BASIC 3.11 interpreter, which is not a compiler. The candidate solution with the best objective function value produced during the first twenty hours of running is presented immediately below. What follows is a manual copy from the computer monitor.
4667 4966 4929 4207 5026
5682 4587 4607 5326 5303
4517 5823 4697 4996 5137
5180 3877 4097 3497 3577
4317 4397 5400 4817 4857
6032 5056 6075 4477 6177
4437 3997 5444 5096 6219
6264 5487 4357 5713 5554
4637 3677 3797 6307 6606
3917 5221 5265 3957 5863
6397 5601 4557 5359 4177
3537 3837 3757 6116 4897
6357 5647 4237 5981 3717
4777 4277 3457 4737 4137
4047 6478 6546 3627 5914
3287 3347 3407 5764 6660
-8827945 -31998
One can check the solution/result at JJJJ=-31998 to see whether there is a gap between any two adjacent facilities. If there is, then joining the two adjacent facilities together will make the actual cost of this order to be less than
8827945. There are gaps in the sequence above.
The best candidate solution from the computer running with 1126 IMAR=10+RND*5000 has the objective function value of 8903161 at JJJJ=-32000.
The best candidate solution from the computer running with 1126 IMAR=10+RND*6000 has the objective function value of 8859337 at JJJJ=-31996.
Interpreted in accordance with line 1912 through line 1959, the candidate solutions above were produced during the first twenty hours of simultaneous running on three personal computers each with the speed of about 2.66 GHz. and with the IBM basica/D interpreter.
References
Amaral, A. R. S., "A New Lower Bound for the Single Row Facility Layout Problem," Discrete Applied Mathematics 157, 183-190 (2009).
Anjos, M. F., and A. Vannelli, "Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes," INFORMS Journal on Computing 20, 611-617 (2008).
Microsoft Corp. BASIC. Second Edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.
Nugent, C. E., R. E. Vollmann, and J. Ruml, "An Experimental Comparison of Techniques for the Assignment of Facilities to Locations," Operations Research, 16 (1968), 150-173.
Simmons, D. M., "One-Dimensional Space Allocation: an Ordering Algorithm," Operations Research 17, 812-826 (1969).
Skorin-Kapov, J., "Tabu Search Applied to the Quadratic Assignment Problem," ORSA Journal on Computing 2, 33-45 (1990).
Subscribe to:
Posts (Atom)