Substance

A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a Double-Row Facility Layout Problem of Seventeen Facilities

Jsun Yui Wong

The following computer program seeks to solve Instance P17 on page 18 of Hungerlaender and Anjos [21]; the data are from Anjos [6].  This is a corridor allocation problem [4].

Because of line 111, the first row can have 9, 10, 11, or 12 facilities.

0 REM DEFDBL A-Z
1 DEFINT I,J,K,X,A
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J44(2002),J(99),AA(99),HR(32),HHR(32),Y(33),C(33),CC(33)
3 DIM HS(49,49)
4 DIM PE(49,49)
5 DIM SD(49,49)
27   HR(1)=20:HR(2)=3:HR(3)=9:HR(4)=3:HR(5)=7
28   HR(6)=3:HR(7)=7:HR(8)=5:HR(9)=9:HR(10)=6
29   HR(11)=5:HR(12)=3:HR(13)=9:HR(14)=3:HR(15)=7
30   HR(16)=3:HR(17)=7
31 FOR IL=1 TO 17
32 FOR JL=1 TO 17
33 READ HS(IL,JL)
34 NEXT JL
35 NEXT IL
61 DATA 999,0,5,0,5,2,10,3,1,5,5,5,0,0,5,4,4
62 DATA 0,999,3,10,5,1,5,1,2,4,2,5,0,10,10,3,0
63 DATA 5,3,999,2,0,5,2,4,4,5,0,0,0,5,1,0,0
64 DATA 0,10,2,999,1,0,5,2,1,0,10,2,2,0,2,1,5
66 DATA 5,5,0,1,999,5,6,5,2,5,2,0,5,1,1,1,5
67 DATA 2,1,5,0,5,999,5,2,1,6,0,0,10,0,2,0,1
68 DATA 10,5,2,5,6,5,999,0,0,0,5,10,2,2,5,1,2
69 DATA 3,1,4,2,5,2,0,999,1,1,10,10,2,0,10,2,5
70 DATA 1,2,4,1,2,1,0,1,999,2,0,3,5,5,0,5,0
71 DATA 5,4,5,0,5,6,0,1,2,999,5,5,0,5,1,0,0
72 DATA 5,2,0,10,2,0,5,10,0,5,999,5,2,5,1,10,0
73 DATA 5,5,0,2,0,0,10,10,3,5,5,999,2,10,5,0,1
74 DATA 0,0,0,2,5,10,2,2,5,0,2,2,999,2,2,1,0
75 DATA 0,10,5,0,1,0,2,0,5,5,5,10,2,999,5,5,1
76 DATA 5,10,1,2,1,2,5,10,0,1,1,5,2,5,999,3,0
77 DATA 4,3,0,1,1,0,1,2,5,0,10,0,1,5,3,999,0
78 DATA 4,0,0,5,5,1,2,5,0,0,0,1,0,1,0,0,999
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-1D+37
91 FOR J44=1 TO 17
93 A(J44)=J44
94 NEXT J44
111 IF RND<1/4 THEN IMAX=9 ELSE IF RND<1/3 THEN IMAX=10 ELSE IF RND<1/2 THEN       IMAX=11   ELSE IMAX=12
126 REM IMAR=10+FIX(RND*1000)
128 FOR I=1 TO 500
129 FOR KKQQ=1 TO 17
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 III=1+FIX(RND*17)
134 JJJ=1+FIX(RND*17)
221    X(III)=A(JJJ)
223    X(JJJ)=A(III)
231 FOR J44=1 TO 17
233 FOR J45=1 TO 17
234 IF X(J44)=J45 THEN HHR(J44)=HR(J44)  ELSE GOTO 238
237 Y(J45)=J44
238 NEXT J45
253 FOR ISE20 =1 TO IMAX
254 C(ISE20)=.5*HHR(Y(ISE20))
258 FOR ISE2000 =ISE20+1 TO IMAX
259 C(ISE20)=C(ISE20)+HHR(Y(ISE2000)    )
263 NEXT ISE2000
269 NEXT ISE20
386 FOR ISE20N =IMAX+1 TO 17
387 C(ISE20N)=.5*HHR(Y(ISE20N))
388 FOR ISE2000N =ISE20N+1 TO 17
389 C(ISE20N)=C(ISE20N)+HHR(Y(ISE2000N)    )
390 NEXT ISE2000N
391 NEXT ISE20N
395 NEXT J44
411 PROD=0
412 FOR J44=1 TO 17
413 FOR J45=J44+1 TO 17
414 PROD=PROD    -HS(Y(J44),Y(J45))*ABS(  C(J44)-C(J45)  )
415 NEXT J45
416 NEXT J44
422 P=PROD
999 REM
1111 IF P<=M THEN 1670
1452 M=P
1453 FOR KLX=1 TO 17
1454 CC(KLX)=C(KLX)
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1559 IIMAX=IMAX
1657 GOTO 128
1670 NEXT I
1889 IF M<-4700 THEN 1999
1901 PRINT A(1),A(2),A(3),A(4),A(5)
1902 PRINT A(6),A(7),A(8),A(9),A(10)
1903 PRINT A(11),A(12),A(13),A(14),A(15)
1904 PRINT A(16),A(17)
1905   PRINT CC(1),CC(2),CC(3),CC(4),CC(5)
1906   PRINT CC(6),CC(7),CC(8),CC(9),CC(10)
1907   PRINT CC(11),CC(12),CC(13),CC(14),CC(15)
1908   PRINT CC(16),CC(17)
1919 PRINT M,JJJJ,IIMAX
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter.  Selected candidate solutions through JJJJ=-31829 are shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

10   14   16   3   2
8   11   13   9   7
4   5   17   15   6
12   1
46.5   39.5   34.5   30.5   26.5
21.5   15   10.5   4.5   49
35.5   30.5   26.5   22.5   19.5
13.5   4.5
-4672   -31972   9

11   6   16   12   2
9   3   5   10   8
13   14   17   7   15
4   1
49.5   42.5   35.5   30.5   26.5
22.5   19.5   15   10.5   4.5
46   34.5   30.5   26.5   21.5
13.5   4.5
-4673   -31970   10

.
.
.

10   6   8   5   2
16   11   12   9   15
13   4   17   14   3
7   1
47.5   40.5   33.5   28.5   25.5
22.5   19.5   13.5   4.5   48
34.5   28.5   23.5   19.5   15
10.5   4.5
-4666   -31829   9

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM, and the IBM basica/D interpreter, version GW BASIC 3.11,  the wall-clock time through JJJJ= -31829 was eleven minutes.

References

[1] Andre R. S. Amaral (2006), On the Exact Solution of a Facility Layout Problem.  European Journal of Operational Research 173 (2006), pp. 508-518.

[2] Andre R. S. Amaral (2008), An Exact Approach to the One-Dimensional Facility Layout Problem.  Operations Research, Vol. 56, No. 4 (July-August, 2008), pp. 1026-1033.

[3] Andre R. S. Amaral (2011), Optimal Solutions for the Double Row Layout Problem.  Optimization Letters, DOI 10.1007/s11590-011-0426-8, published on line 30 November 2011, Springer-Verlag 2011.

[4] Andre R. S. Amaral (2012), The Corridor Allocation Problem.  Computers and Operations Research 39 (2012), pp. 3325-3330.

[5] Miguel F. Anjos, Anthony Vannelli, Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes.  INFORMS Journal on Computing, Vol. 20, No. 4, Fall 2008, pp. 611-617.
 
[6] Miguel F. Anjos (2012), FLPLIB--Facility Layout Database.  Retrieved on September 25 2012 from www.gerad.ca/files/Sites/Anjos/indexFR.html

[7] David L. Applegate, Robert E. Bixby, Vasek Chvatal, William J. Cook, The Traveling Salesman Problem: A Computational Study.  Princeton and Oxford: Princeton University Press, 2006.

[8] L. L. Barachet (1957), Graphic Solution of the Travelling Salesman Problem.  Operations Research. Vol. 5, pp. 841-845.

[9] T. Y. Chen, H. C. Chen (2009), Mixed-Discrete Structural Optimization Using a Rank-Niche Evolution Strategy, Engineering Optimization, 41:1, 39-58.

[10] Leon Cooper, U. N. Bhat, L. J. LeBlanc, Introduction to Operations Research Models.  W. B. Saunders Company, 1977.

[11] George B. Dantzig, Discrete-Variable Extremum Problems.  Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.

[12] G. Dantzig, R. Fulkerson, S. Johnson, Solution of a Large-Scale Traveling-Salesman Problem. 
Operations Research, Vol. 2, No. 4 (Nov., 1954), pp. 393-410.

[13] Zvi Drezner (1980), DISCON: A New Method for the Layout Problem.  Operations Research, Vol. 28, No. 6 (Nov. - Dec., 1980), pp. 1375-1384.

[14] W. J. Fabrycky, P. M. Ghare, P. E. Torgersen, Applied Operations Research and Management Science.  Englewood Cliffs, N. J. 07362: Prentice-Hall, Inc., 1984.

[15] Billy E. Gillett, Introduction to Operations Research: A Computer-Oriented Algorithmic Approach.  McGraw-Hill, Inc., 1976.

[16] Diptesh Ghosh, Ravi Kothari, Population Heuristics for the Corridor Allocation Problem, W.P. No. 2012-09-02, September 2012.  Retrieved on September 14 2012 from Google search.

[17] Martin Grotschel, Olaf Holland (1991), Solution of Large-Scale Symmetric Travelling Salesman Problems, Mathematical Programming 51, pp. 141-202.

[18] Sunderesh S. Heragu, Andrew Kusiak (1988), Machine Layout Problem in Flexible Manufacturing Systems.  Operations Research, Vol. 36, No. 2, Operations Research in Manufacturing (Mar. - Apr., 1988), pp. 258-268.

[19] S. S. Heragu, A. Kusiak (1991), Efficient Models for the Facility Layout Problem.  European Journal of Operational Research, Vol. 53 (1991), pp. 1-13.

[20] S. S. Heragu, Facilities Design, Third Edition.  Boca Raton, Florida: CRC Press, 2008.

[21] Philipp Hungerlaender, Miguel F. Anjos (January 2012), A Semidefinite Optimization Approach to Free-Space Multi-Row Facility Layout.  Les Cashiers du GERAD.  Retrieved from www.gerad.ca/fichiers/cahiers/G-2012-03.pdf

[22] Michael Junger, Thomas M. Liebling, Dennis Naddef, George L. Nemhauser, William R. Pulleybank, Gerhart Reinelt, Giovanni Rinaldi, Lawrence A. Wolsey--Editors, 50 Years of Integer Programming 1958-2008.  Berlin: Springer, 2010.

[23] R. L. Karg, G. L. Thompson (1964), A Heuristic Approach to Solving Travelling Salesman Problems.  Management Science, Vol. 10, Number 2, pp. 225-248.

[24] K. Ravi Kumar, George C. Hadjinicola, Ting-li Lin (1995), A Heuristic Procedure for the Single-Row Facility Layout Problem.  European Journal of Operational Research 87 (1995) 65-73.

[25]  A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems.  Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.

[26] E. L. Lawler, M. D. Bell, A Method for Solving Discrete Optimization Problems.  Operations Research, Vol. 14, No. 6 (Nov.-Dec., 1966), pp. 1098-1112.

[27] Robert F. Love, Jsun Y. Wong (1976), On Solving a One-Dimensional Space Allocation Problem with Integer Programming.  INFOR, Vol. 14, No. 2, June 1976, pp. 139-143.
 
[28] 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.

[29] Katta G. Murty, Operations Research: Deterministic Optimization Models.  Prentice Hall, Upper Saddle River, New Jersey 07458, 1994.

[30] C. E. Nugent, T. E. Vollmann, J. Ruml (1968), An Experimental Comparison of Techniques for the Assignment of Facilities to Locations, Operations Research 16 (1968), pp. 150-173.

[31] Christopher J. Picone, Wilbert E. Wilhelm (1986), "A Perturbation Scheme To Improve Hillier's Solution to the Facilities Layout Problem": a Clarification.  Management Science Vol. 32, No. 2, February 1986, pp. 253-254. 

[32] Cliff T. Ragsdale, Spreadsheet Modeling and Decision Analysis, Fifth Edition.  South-Westen, Cengage Learning, 2008.

[33] H. H. Rosenbrock (1960), An Automatic Method for Finding the Greatest or Least Value of a Function, Computer Journal Vol. 3, pp. 175-184.

[34] Donald M. Simmons (1969), One-Dimensional Space Allocation: An Ordering Algorithm.     Operations Research, Vol. 17, No. 5 (Sep. - Oct., 1969), pp. 812-826.

[35] Wayne L. Winston, Munirpallam Venkataramanan, Introduction to Mathematical Programming: Operations Research, Volume One, Fourth Edition.  Pacific Grove, CA 93950: Brooks/Cole--Thomson Learning, 2003.

[36] Wayne L. Winston, S. Christian Albright, Practical Management Science, Third Edition.  Thomson/South-Western, 2007.

[37] Jsun Yui Wong (2009, July 18).  An Integer Programming Computer Program Applied to One-Dimensional Space Allocation.  Retrieved from http://wongsllllblog.blogspot.com/2009/07/

[38] Jsun Yui Wong (2009, November 2).  A Computer Program for Relative Location of Circular Facilities.  Retrieved on September 3, 2012, from http://wongsllllblog.blogspot.ca/2009/11/

[39] Jsun Yui Wong (2009, December 18).  A Heuristic Nonlinear Integer Solver Applied to a Problem of Assignment of Facilities to Locations.  Retrieved from http://wongsnewnewblog.blogspot.ca/2009/12/

[40] Jsun Yui Wong (2011, October 27).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a New Formulation of a Twelve-City Traveling Salesman Problem, Sixth Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/10/27/

[41] Ji-Hui Zhang, Xin-He Xu (1999), An Efficient Evolutionary Programming Algorithm.  Computers and Operations Research 26, 645-663.

A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a Linear Ordering Problem with 24 Facilities

Jsun Yui Wong

The following computer program seeks to solve Instance N-24 of Hungerlaender [21] and of Anjos [6].

0 REM DEFDBL A-Z
1 DEFINT I,J,K,X,A
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J44(2002),J(99),AA(99),HR(32),HHR(32)
3 DIM HS(49,49)
4 DIM PE(49,49)
5 DIM SD(49,49)
11 FOR J44=1 TO 24
15   HR(J44)=1
17 NEXT J44
31 FOR IL=1 TO 23
32 FOR JL=IL+1 TO 24
33 READ HS(IL,JL)
34 NEXT JL
35 NEXT IL
52 DATA 6,4,0,0,4,20,10,0,10,4,10,0,0,4,0,10,12,6,0,2,20,0,20
53 DATA 8,0,20,8,0,0,4,4,2,0,10,0,0,0,0,4,0,2,12,2,0,2
54 DATA 6,8,0,10,10,10,2,8,2,0,8,0,8,0,12,6,4,10,10,4,2
55 DATA 0,0,0,4,4,0,12,0,4,10,4,10,2,2,2,2,4,4,8,0
56 DATA 10,4,0,0,0,0,4,0,0,0,0,4,2,0,0,4,0,10,2
57 DATA 2,4,4,2,8,20,20,4,10,10,0,10,0,0,0,20,0,0
58 DATA 20,20,10,20,20,12,0,0,20,4,2,20,2,10,10,4,6
59 DATA 2,6,10,0,0,0,4,8,10,4,20,12,0,10,10,4
60 DATA 20,4,2,10,4,0,6,0,4,0,0,8,0,10,4
61 DATA 10,10,12,0,2,10,10,0,10,4,6,10,0,10
62 DATA 0,0,2,4,2,0,4,0,0,0,12,12,0
63 DATA 10,10,4,0,0,0,0,4,0,8,10,20
64 DATA 4,0,8,4,4,2,0,12,4,2,10
65 DATA 4,2,0,10,6,20,0,0,8,4
66 DATA 8,10,2,0,2,0,10,0,4
67 DATA 0,6,0,4,4,0,4,0
68 DATA 4,4,0,0,0,12,10
69 DATA 10,2,4,20,20,8
70 DATA 0,10,10,2,0
71 DATA 10,4,2,6
72 DATA 8,0,2
73 DATA 10,0
74 DATA 0
78 FOR JJJJ=-32000 TO 32000
79 RANDOMIZE JJJJ
80 M=-1D+37
81 FOR J44=1 TO 24
83 A(J44)=J44
84 NEXT J44
126 REM IMAR=10+FIX(RND*1000)
128 FOR I=1 TO 3000
129 FOR KKQQ=1 TO 24
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 III=1+FIX(RND*24)
134 JJJ=1+FIX(RND*24)
221    X(III)=A(JJJ)
223    X(JJJ)=A(III)
225 FOR II=1 TO 23
227 FOR JJ=II+1 TO 24
231 SD(II,JJ)=0
235 SD(II,JJ)=.5*HR(II)+.5*HR(JJ)
239 FOR KK = 1 TO 24
241 IF X(II)<X(JJ) THEN 245 ELSE 249
245 IF X(KK)>X(II) AND X(KK) <X(JJ) THEN HHR(KK)=HR(KK) ELSE HHR(KK)=0
247 GOTO 255
249 IF X(KK)>X(JJ) AND X(KK) <X(II) THEN HHR(KK)=HR(KK) ELSE HHR(KK)=0
255 SD(II,JJ)=SD(II,JJ)+HHR(KK)
261 NEXT KK
267 NEXT JJ
271 NEXT II
305 PDU=0
309 FOR IW=1 TO 23
312 FOR J88=IW+1 TO 24
318 PDU=PDU-HS(IW,J88)*SD(IW,J88)
320 NEXT J88
321 NEXT IW
359 POB1=PDU
444 P1NEWMAY=POB1
466 P=P1NEWMAY
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 24
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-8290 THEN 1999
1901 PRINT A(1),A(2),A(3),A(4),A(5)
1902 PRINT A(6),A(7),A(8),A(9),A(10)
1903 PRINT A(11),A(12),A(13),A(14),A(15)
1904 PRINT A(16),A(17),A(18),A(19),A(20)
1905 PRINT A(21),A(22),A(23),A(24)
1917 PRINT M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter.  The complete output through JJJJ=-31930 is shown below.  What follows is a hand copy from the computer-monitor screen.  Immediately below there is no rounding by hand.

12   2   13   22   1
5   11   17   8   9
18   6   4   23   21
10   20   15   16   24
3   14   19   7
-8270   -31999

10   2   15   22   1
5   11   17   8   9
18   6   4   23   21
16   20   14   13   24
3   12   19   7
-8288   -31972

13   23   12   3   24
20   14   8   17   16
7   19   21   2   4
15   5   10   9   1
22   11   6   18
-8270   -31930

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM, and the IBM basica/D interpreter, version GW BASIC 3.11,  the wall-clock time through JJJJ= -31930 was  2 hours and 50 minutes.

References

[1] Andre R. S. Amaral (2006), On the Exact Solution of a Facility Layout Problem.  European Journal of Operational Research 173 (2006), pp. 508-518.

[2] Andre R. S. Amaral (2008), An Exact Approach to the One-Dimensional Facility Layout Problem.  Operations Research, Vol. 56, No. 4 (July-August, 2008), pp. 1026-1033.

[3] Andre R. S. Amaral (2011), Optimal Solutions for the Double Row Layout Problem.  Optimization Letters, DOI 10.1007/s11590-011-0426-8, published on line 30 November 2011, Springer-Verlag 2011.

[4] Andre R. S. Amaral (2012), The Corridor Allocation Problem.  Computers and Operations Research 39 (2012), pp. 3325-3330.

[5] Miguel F. Anjos, Anthony Vannelli, Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes.  INFORMS Journal on Computing, Vol. 20, No. 4, Fall 2008, pp. 611-617.

[6] Miguel F. Anjos (2012), FLPLIB--Facility Layout Database.  Retrieved on September 25 2012 from www.gerad.ca/files/Sites/Anjos/indexFR.html.

[7] David L. Applegate, Robert E. Bixby, Vasek Chvatal, William J. Cook, The Traveling Salesman Problem: A Computational Study.  Princeton and Oxford: Princeton University Press, 2006.

[8] L. L. Barachet (1957), Graphic Solution of the Travelling Salesman Problem.  Operations Research. Vol. 5, pp. 841-845.

[9] T. Y. Chen, H. C. Chen (2009), Mixed-Discrete Structural Optimization Using a Rank-Niche Evolution Strategy, Engineering Optimization, 41:1, 39-58.

[10] Leon Cooper, U. N. Bhat, L. J. LeBlanc, Introduction to Operations Research Models.  W. B. Saunders Company, 1977.

[11] George B. Dantzig, Discrete-Variable Extremum Problems.  Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.

[12] G. Dantzig, R. Fulkerson, S. Johnson, Solution of a Large-Scale Traveling-Salesman Problem. 
Operations Research, Vol. 2, No. 4 (Nov., 1954), pp. 393-410.

[13] Zvi Drezner (1980), DISCON: A New Method for the Layout Problem.  Operations Research, Vol. 28, No. 6 (Nov. - Dec., 1980), pp. 1375-1384.

[14] W. J. Fabrycky, P. M. Ghare, P. E. Torgersen, Applied Operations Research and Management Science.  Englewood Cliffs, N. J. 07362: Prentice-Hall, Inc., 1984.

[15] Billy E. Gillett, Introduction to Operations Research: A Computer-Oriented Algorithmic Approach.  McGraw-Hill, Inc., 1976.

[16] Diptesh Ghosh, Ravi Kothari, Population Heuristics for the Corridor Allocation Problem, W.P. No. 2012-09-02, September 2012.  Retrieved on September 14 2012 from Google search.

[17] Martin Grotschel, Olaf Holland (1991), Solution of Large-Scale Symmetric Travelling Salesman Problems, Mathematical Programming 51, pp. 141-202.

[18] Sunderesh S. Heragu, Andrew Kusiak (1988), Machine Layout Problem in Flexible Manufacturing Systems.  Operations Research, Vol. 36, No. 2, Operations Research in Manufacturing (Mar. - Apr., 1988), pp. 258-268.

[19] S. S. Heragu, A. Kusiak (1991), Efficient Models for the Facility Layout Problem.  European Journal of Operational Research, Vol. 53 (1991), pp. 1-13.

[20] S. S. Heragu, Facilities Design, Third Edition.  Boca Raton, Florida: CRC Press, 2008.

[21]  Philipp Hungerlaender, Single-Row Equidistant Facility Layout as a Special Case of Single-Row Facility Layout.  Retrieved from www.optimization-online.org/

[22] Michael Junger, Thomas M. Liebling, Dennis Naddef, George L. Nemhauser, William R. Pulleybank, Gerhart Reinelt, Giovanni Rinaldi, Lawrence A. Wolsey--Editors, 50 Years of Integer Programming 1958-2008.  Berlin: Springer, 2010.

[23] R. L. Karg, G. L. Thompson (1964), A Heuristic Approach to Solving Travelling Salesman Problems.  Management Science, Vol. 10, Number 2, pp. 225-248.

[24] K. Ravi Kumar, George C. Hadjinicola, Ting-li Lin (1995), A Heuristic Procedure for the Single-Row Facility Layout Problem.  European Journal of Operational Research 87 (1995) 65-73.

[25]  A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems.  Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.

[26] E. L. Lawler, M. D. Bell, A Method for Solving Discrete Optimization Problems.  Operations Research, Vol. 14, No. 6 (Nov.-Dec., 1966), pp. 1098-1112.

[27] Robert F. Love, Jsun Y. Wong (1976), On Solving a One-Dimensional Space Allocation Problem with Integer Programming.  INFOR, Vol. 14, No. 2, June 1976, pp. 139-143.
 
[28] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems.  Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.     

[29] Ken McAloon, Carol Tretkoff, Optimization and Computational Logic.  John Wiley and Sons, Inc., 1996.

[30] 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.

[31] Katta G. Murty, Operations Research: Deterministic Optimization Models.  Prentice Hall, Upper Saddle River, New Jersey 07458, 1994.

[32] C. E. Nugent, T. E. Vollmann, J. Ruml (1968), An Experimental Comparison of Techniques for the Assignment of Facilities to Locations, Operations Research 16 (1968), pp. 150-173.

[33] Christopher J. Picone, Wilbert E. Wilhelm (1986), "A Perturbation Scheme To Improve Hillier's Solution to the Facilities Layout Problem": a Clarification.  Management Science Vol. 32, No. 2, February 1986, pp. 253-254. 

[34] Cliff T. Ragsdale, Spreadsheet Modeling and Decision Analysis, Fifth Edition.  South-Westen, Cengage Learning, 2008.

[35] H. H. Rosenbrock (1960), An Automatic Method for Finding the Greatest or Least Value of a Function, Computer Journal Vol. 3, pp. 175-184.

[36] Donald M. Simmons (1969), One-Dimensional Space Allocation: An Ordering Algorithm.     Operations Research, Vol. 17, No. 5 (Sep. - Oct., 1969), pp. 812-826.

[37] Wayne L. Winston, Munirpallam Venkataramanan, Introduction to Mathematical Programming: Operations Research, Volume One, Fourth Edition.  Pacific Grove, CA 93950: Brooks/Cole--Thomson Learning, 2003.

[38] Wayne L. Winston, S. Christian Albright, Practical Management Science, Third Edition.  Thomson/South-Western, 2007.

[39] Jsun Yui Wong (2009, July 18).  An Integer Programming Computer Program Applied to One-Dimensional Space Allocation.  Retrieved from http://wongsllllblog.blogspot.com/2009/07/

[40] Jsun Yui Wong (2009, November 2).  A Computer Program for Relative Location of Circular Facilities.  Retrieved on September 3, 2012, from http://wongsllllblog.blogspot.ca/2009/11/

[41] Jsun Yui Wong (2009, December 18).  A Heuristic Nonlinear Integer Solver Applied to a Problem of Assignment of Facilities to Locations.  Retrieved from http://wongsnewnewblog.blogspot.ca/2009/12/

[42] Jsun Yui Wong (2011, October 27).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a New Formulation of a Twelve-City Traveling Salesman Problem, Sixth Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/10/27/

[43] Ji-Hui Zhang, Xin-He Xu (1999), An Efficient Evolutionary Programming Algorithm.  Computers and Operations Research 26, 645-663.

A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Corridor Allocation Problem with Eleven Facilities, Fourth Edition

Jsun Yui Wong

The following computer program seeks to solve Problem S11 on page 3328 of Amaral [4] and on page 9 of Ghosh and Kothari [15].

Because of line 111, the first row can have 6, 7, 8, or 9 facilities.

0 REM DEFDBL A-Z
1 DEFINT I,J,K,X,A
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J44(2002),J(99),AA(99),HR(32),HHR(32),Y(33),C(33),CC(33)
3 DIM HS(49,49)
4 DIM PE(49,49)
5 DIM SD(49,49)
27   HR(1)=3:HR(2)=9:HR(3)=3:HR(4)=7:HR(5)=3
28   HR(6)=7:HR(7)=5:HR(8)=9:HR(9)=6:HR(10)=5 :HR(11)=10
31 FOR IL=1 TO 11
32 FOR JL=1 TO 11
33 READ HS(IL,JL)
34 NEXT JL
35 NEXT IL
61 DATA 999,20,2,8,0,9,5,7,0,20,3
62 DATA 20,999,8,9,13,17,16,1,8,6,7
63 DATA 2,8,999,18,0,10,4,18,5,8,0
64 DATA 8,9,18,999,6,16,10,4,2,14,6
66 DATA 0,13,0,6,999,6,0,11,0,8,2
67 DATA 9,17,10,16,6,999,6,13,2,7,18
68 DATA 5,16,4,10,0,6,999,1,11,15,7
69 DATA 7,1,18,4,11,13,1,999,1,7,2
70 DATA 0,8,5,2,0,2,11,1,999,12,0
71 DATA 20,6,8,14,8,7,15,7,12,999,3
72 DATA 3,7,0,6,2,18,7,2,0,3,999
78 FOR JJJJ=-32000 TO 32000
79 RANDOMIZE JJJJ
80 M=-1D+37
81 FOR J44=1 TO 11
83 A(J44)=J44
84 NEXT J44
111 IF RND<1/4 THEN IMAX=6 ELSE IF RND<1/3 THEN IMAX=7 ELSE IF RND<1/2 THEN       IMAX=8   ELSE IMAX=9
126 REM IMAR=10+FIX(RND*1000)
128 FOR I=1 TO 500
129 FOR KKQQ=1 TO 11
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 III=1+FIX(RND*11)
134 JJJ=1+FIX(RND*11)
221    X(III)=A(JJJ)
223    X(JJJ)=A(III)
231 FOR J44=1 TO 11
233 FOR J45=1 TO 11
234 IF X(J44)=J45 THEN HHR(J44)=HR(J44)  ELSE GOTO 238
237 Y(J45)=J44
238 NEXT J45
253 FOR ISE20 =1 TO IMAX
254 C(ISE20)=.5*HHR(Y(ISE20))
258 FOR ISE2000 =ISE20+1 TO IMAX
259 C(ISE20)=C(ISE20)+HHR(Y(ISE2000)    )
263 NEXT ISE2000
269 NEXT ISE20
386 FOR ISE20N =IMAX+1 TO 11
387 C(ISE20N)=.5*HHR(Y(ISE20N))
388 FOR ISE2000N =ISE20N+1 TO 11
389 C(ISE20N)=C(ISE20N)+HHR(Y(ISE2000N)    )
390 NEXT ISE2000N
391 NEXT ISE20N
395 NEXT J44
411 PROD=0
412 FOR J44=1 TO 11
413 FOR J45=J44+1 TO 11
414 PROD=PROD    -HS(Y(J44),Y(J45))*ABS(  C(J44)-C(J45)  )
415 NEXT J45
416 NEXT J44
422 P=PROD
1111 IF P<=M THEN 1670
1452 M=P
1453 FOR KLX=1 TO 11
1454 CC(KLX)=C(KLX)
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1559 IIMAX=IMAX
1657 GOTO 128
1670 NEXT I
1889 IF M<-4000 THEN 1999
1901 PRINT A(1),A(2),A(3),A(4),A(5)
1902 PRINT A(6),A(7),A(8),A(9)
1903 PRINT A(10),A(11)
1905   PRINT CC(1),CC(2),CC(3),CC(4),CC(5)
1906   PRINT CC(6),CC(7),CC(8),CC(9)
1907   PRINT CC(10),CC(11)
1919 PRINT M,JJJJ,IIMAX
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter.  Selected candidate solutions through JJJJ=-31931 are shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

4   10   2   9   1
3   6   8   7
5   11
30.5   27.5   22.5   17.5   13.5
8.5   3   30.5   22.5
14.5   5
-3580.5   -32000   7

5   10   3   4   2
9   7   1   8
6   11
36.5   30.5   27.5   22.5   17.5
13.5   8.5   3   22.5
14.5   5
-3970.5   -31999   8

.
.
.


8   7   4   9   10
5   2   6   1
3   11
32   26.5   21.5   17.5   12.5
4.5   27.5   21.5   16.5
11.5   5
-3439.5   -31931   6

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM, and the IBM basica/D interpreter, version GW BASIC 3.11,  the wall-clock time through JJJJ= -31931 was seventy seconds.

References

[1] Andre R. S. Amaral (2006), On the Exact Solution of a Facility Layout Problem.  European Journal of Operational Research 173 (2006), pp. 508-518.

[2] Andre R. S. Amaral (2008), An Exact Approach to the One-Dimensional Facility Layout Problem.  Operations Research, Vol. 56, No. 4 (July-August, 2008), pp. 1026-1033.

[3] Andre R. S. Amaral (2011), Optimal Solutions for the Double Row Layout Problem.  Optimization Letters, DOI 10.1007/s11590-011-0426-8, published on line 30 November 2011, Springer-Verlag 2011.

[4] Andre R. S. Amaral (2012), The Corridor Allocation Problem.  Computers and Operations Research 39 (2012), pp. 3325-3330.

[5] Miguel F. Anjos, Anthony Vannelli, Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes.  INFORMS Journal on Computing, Vol. 20, No. 4, Fall 2008, pp. 611-617.

[6] David L. Applegate, Robert E. Bixby, Vasek Chvatal, William J. Cook, The Traveling Salesman Problem: A Computational Study.  Princeton and Oxford: Princeton University Press, 2006.

[7] L. L. Barachet (1957), Graphic Solution of the Travelling Salesman Problem.  Operations Research, Vol. 5, pp. 841-845.

[8] T. Y. Chen, H. C. Chen (2009), Mixed-Discrete Structural Optimization Using a Rank-Niche Evolution Strategy, Engineering Optimization, 41:1, 39-58.

[9] Leon Cooper, U. N. Bhat, L. J. LeBlanc, Introduction to Operations Research Models.  W. B. Saunders Company, 1977.

[10] George B. Dantzig, Discrete-Variable Extremum Problems.  Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.

[11] G. Dantzig, R. Fulkerson, S. Johnson, Solution of a Large-Scale Traveling-Salesman Problem. 
Operations Research, Vol. 2, No. 4 (Nov., 1954), pp. 393-410.

[12] Zvi Drezner (1980), DISCON: A New Method for the Layout Problem.  Operations Research, Vol. 28, No. 6 (Nov. - Dec., 1980), pp. 1375-1384.

[13] W. J. Fabrycky, P. M. Ghare, P. E. Torgersen, Applied Operations Research and Management Science.  Englewood Cliffs, N. J. 07362: Prentice-Hall, Inc., 1984.

[14] Billy E. Gillett, Introduction to Operations Research: A Computer-Oriented Algorithmic Approach.  McGraw-Hill, Inc., 1976.

[15] Diptesh Ghosh, Ravi Kothari, Population Heuristics for the Corridor Allocation Problem, W.P. No. 2012-09-02, September 2012.  Retrieved on September 14 2012 from Google search.

[16] Martin Grotschel, Olaf Holland (1991), Solution of Large-Scale Symmetric Travelling Salesman Problems, Mathematical Programming 51, pp. 141-202.

[17] Sunderesh S. Heragu, Andrew Kusiak (1988), Machine Layout Problem in Flexible Manufacturing Systems.  Operations Research, Vol. 36, No. 2, Operations Research in Manufacturing (Mar. - Apr., 1988), pp. 258-268.

[18] S. S. Heragu, A. Kusiak (1991), Efficient Models for the Facility Layout Problem.  European Journal of Operational Research, Vol. 53 (1991), pp. 1-13.

[19] S. S. Heragu, Facilities Design, Third Edition.  Boca Raton, Florida: CRC Press, 2008.

[20] Michael Junger, Thomas M. Liebling, Dennis Naddef, George L. Nemhauser, William R. Pulleybank, Gerhart Reinelt, Giovanni Rinaldi, Lawrence A. Wolsey--Editors, 50 Years of Integer Programming 1958-2008.  Berlin: Springer, 2010.

[21] R. L. Karg, G. L. Thompson (1964), A Heuristic Approach to Solving Travelling Salesman Problems.  Management Science, Vol. 10, Number 2, pp. 225-248.

[22] K. Ravi Kumar, George C. Hadjinicola, Ting-li Lin (1995), A Heuristic Procedure for the Single-Row Facility Layout Problem.  European Journal of Operational Research 87 (1995) 65-73.

[23]  A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems.  Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.

[24] E. L. Lawler, M. D. Bell, A Method for Solving Discrete Optimization Problems.  Operations Research, Vol. 14, No. 6 (Nov.-Dec., 1966), pp. 1098-1112.

[25] Robert F. Love, Jsun Y. Wong (1976), On Solving a One-Dimensional Space Allocation Problem with Integer Programming.  INFOR, Vol. 14, No. 2, June 1976, pp. 139-143.
 
[26] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems.  Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.     

[27] Ken McAloon, Carol Tretkoff, Optimization and Computational Logic.  John Wiley and Sons, Inc., 1996.

[28] 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.

[29] Katta G. Murty, Operations Research: Deterministic Optimization Models.  Prentice Hall, Upper Saddle River, New Jersey 07458, 1994.

[30] C. E. Nugent, T. E. Vollmann, J. Ruml (1968), An Experimental Comparison of Techniques for the Assignment of Facilities to Locations, Operations Research 16 (1968), pp. 150-173.

[31] Christopher J. Picone, Wilbert E. Wilhelm (1986), "A Perturbation Scheme To Improve Hillier's Solution to the Facilities Layout Problem": a Clarification.  Management Science Vol. 32, No. 2, February 1986, pp. 253-254. 

[32] Cliff T. Ragsdale, Spreadsheet Modeling and Decision Analysis, Fifth Edition.  South-Westen, Cengage Learning, 2008.

[33] H. H. Rosenbrock (1960), An Automatic Method for Finding the Greatest or Least Value of a Function, Computer Journal Vol. 3, pp. 175-184.

[34] Donald M. Simmons (1969), One-Dimensional Space Allocation: An Ordering Algorithm.     Operations Research, Vol. 17, No. 5 (Sep. - Oct., 1969), pp. 812-826.

[35] Wayne L. Winston, Munirpallam Venkataramanan, Introduction to Mathematical Programming: Operations Research, Volume One, Fourth Edition.  Pacific Grove, CA 93950: Brooks/Cole--Thomson Learning, 2003.

[36] Wayne L. Winston, S. Christian Albright, Practical Management Science, Third Edition.  Thomson/South-Western, 2007.

[37] Jsun Yui Wong (2009, July 18).  An Integer Programming Computer Program Applied to One-Dimensional Space Allocation.  Retrieved from http://wongsllllblog.blogspot.com/2009/07/

[38] Jsun Yui Wong (2009, November 2).  A Computer Program for Relative Location of Circular Facilities.  Retrieved on September 3, 2012, from http://wongsllllblog.blogspot.ca/2009/11/

[39] Jsun Yui Wong (2009, December 18).  A Heuristic Nonlinear Integer Solver Applied to a Problem of Assignment of Facilities to Locations.  Retrieved from http://wongsnewnewblog.blogspot.ca/2009/12/

[40] Jsun Yui Wong (2011, October 27).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a New Formulation of a Twelve-City Traveling Salesman Problem, Sixth Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/10/27/

[41] Ji-Hui Zhang, Xin-He Xu (1999), An Efficient Evolutionary Programming Algorithm.  Computers and Operations Research 26, 645-663.

A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Corridor Allocation Problem with Fifteen Facilities, Fifth Edition

Jsun Yui Wong

The following computer program seeks to solve the n=15 corridor allocation problem on page 3328 of Amaral [4] and on page 9 of Ghosh and Kothari [15].  The lengths of line 27 through line 30 and the flows of line 61 through line 76 are from Amaral [2, p. 1031].  Line 111 is new.

0 REM DEFDBL A-Z
1 DEFINT I,J,K,X,A
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J44(2002),J(99),AA(99),HR(32),HHR(32),Y(33),C(33),CC(33)
3 DIM HS(49,49)
4 DIM PE(49,49)
5 DIM SD(49,49)
27   HR(1)=20:HR(2)=3:HR(3)=9:HR(4)=3:HR(5)=7
28   REM   HR(6)=4:HR(7)=6:HR(8)=8:HR(9)=9
29   HR(6)=3:HR(7)=7:HR(8)=5:HR(9)=9:HR(10)=6
30   HR(11)=5:HR(12)=3:HR(13)=9:HR(14)=3:HR(15)=7
31 FOR IL=1 TO 15
32 FOR JL=1 TO 15
33 READ HS(IL,JL)
34 NEXT JL
35 NEXT IL
61 DATA 999,10,0,5,1,0,1,2,2,2,2,0,4,0,0
62 DATA 10,999,1,3,2,2,2,3,2,0,2,0,10,5,0
63 DATA 0,1,999,10,2,0,2,5,4,5,2,2,5,5,5
64 DATA 5,3,10,999,1,1,5,0,0,2,1,0,2,5,0
66 DATA 1,2,2,1,999,3,5,5,5,1,0,3,0,5,5
67 DATA 0,2,0,1,3,999,2,2,1,5,0,0,2,5,10
68 DATA 1,2,2,5,5,2,999,6,0,1,5,5,5,1,0
69 DATA 2,3,5,0,5,2,6,999,5,2,10,0,5,0,0
70 DATA 2,2,4,0,5,1,0,5,999,0,10,5,10,0,2
71 DATA 2,0,5,2,1,5,1,2,0,999,0,4,0,0,5
72 DATA 2,2,2,1,0,0,5,10,10,0,999,5,0,5,0
73 DATA 0,0,2,0,3,0,5,0,5,4,3,999,3,3,0
74 DATA 4,10,5,2,0,2,5,5,10,0,0,3,999,10,2
75 DATA 0,5,5,5,5,5,1,0,0,0,5,3,10,999,4
76 DATA 0,0,5,0,5,10,0,0,2,5,0,0,2,4,999
78 FOR JJJJ=-32000 TO 32000
79 RANDOMIZE JJJJ
80 M=-1D+37
81 FOR J44=1 TO 15
83 A(J44)=J44
84 NEXT J44
111 IF RND<1/4 THEN IMAX=8 ELSE IF RND<1/3 THEN IMAX=9 ELSE IF RND<1/2 THEN       IMAX=10   ELSE IMAX=11
126 REM IMAR=10+FIX(RND*1000)
128 FOR I=1 TO 500
129 FOR KKQQ=1 TO 15
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 III=1+FIX(RND*15)
134 JJJ=1+FIX(RND*15)
221    X(III)=A(JJJ)
223    X(JJJ)=A(III)
231 FOR J44=1 TO 15
233 FOR J45=1 TO 15
234 IF X(J44)=J45 THEN HHR(J44)=HR(J44)  ELSE GOTO 238
237 Y(J45)=J44
238 NEXT J45
253 FOR ISE20 =1 TO IMAX
254 C(ISE20)=.5*HHR(Y(ISE20))
258 FOR ISE2000 =ISE20+1 TO IMAX
259 C(ISE20)=C(ISE20)+HHR(Y(ISE2000)    )
263 NEXT ISE2000
269 NEXT ISE20
386 FOR ISE20N =IMAX+1 TO 15
387 C(ISE20N)=.5*HHR(Y(ISE20N))
388 FOR ISE2000N =ISE20N+1 TO 15
389 C(ISE20N)=C(ISE20N)+HHR(Y(ISE2000N)    )
390 NEXT ISE2000N
391 NEXT ISE20N
395 NEXT J44
411 PROD=0
412 FOR J44=1 TO 15
413 FOR J45=J44+1 TO 15
414 PROD=PROD    -HS(Y(J44),Y(J45))*ABS(  C(J44)-C(J45)  )
415 NEXT J45
416 NEXT J44
422 P=PROD
1111 IF P<=M THEN 1670
1452 M=P
1453 FOR KLX=1 TO 15
1454 CC(KLX)=C(KLX)
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1559 IIMAX=IMAX
1657 GOTO 128
1670 NEXT I
1889 IF M<-99222! THEN 1999
1901 PRINT A(1),A(2),A(3),A(4),A(5)
1902 PRINT A(6),A(7),A(8),A(9),A(10)
1903 PRINT A(11),A(12),A(13),A(14),A(15)
1905   PRINT CC(1),CC(2),CC(3),CC(4),CC(5)
1906   PRINT CC(6),CC(7),CC(8),CC(9),CC(10)
1907   PRINT CC(11),CC(12),CC(13),CC(14),CC(15)
1919 PRINT M,JJJJ,IIMAX
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter.  Only summary output through JJJJ=-31937 is shown below.  What follows is a hand-copy summary output from the computer-monitor screen; immediately below there is no rounding by hand.

-3377   -32000   9

-3408   -31999   9

-3626   -31998   9

-3744   -31997   11

-3229   -31996   8

-3611   -31995   10

-3673  -31994   11

-3756   -31993   11

-3789   -31992   11

-3527   -31991   9

-3917   -31990   11

-3247   -31989   9

-3347   -31988   10

-3678   -31987   11

-3401   -31986   9

-3567   -31985   9

-3375   -31984   9

-3342   -31983   8

-3214   -31982   8

-3250   -31981   8

-3194   -31980   8

-3243   -31979   10

-3500   -31978   10

-3368   -31977   8

-3451   -31976   10

-3299   -31975   9

-3243   -31974   10

-3356   -31973   9

-3777   -31972   10

-3547   -31971   10

-3390   -31970   8

-3415   -31969   10

-3652   -31968   11

-3718   -31967   9

-3430   -31966   8

-3732   -31965   11

-3368   -31964   10

-3413   -31963   10

-3444   -31962   11

-3420   -31961   9

-3666   -31960   10

-3732   -31959   11

-3362   -31958   11

-3275   -31957   9

-3315   -31956   10

-3384   -31955   9

-3297   -31954   8

-3699   -31953   9

-3397   -31952   9

-3796   -31951   11

-3207   -31950   8

-3839   -31949   11

-3366   -31948   9

-3510   -31947   10

-3393   -31946   8

-3457   -31945   9

-3387   -31944   10

-3673   -31943   11

-3531   -31942   11

-3469   -31941   10

-3718   -31940   11

-3756   -31939   11

-3256   -31938   9

1   10   13   6   7
14   12   3   9   15
11   4   2   5   8
47   32.5   25.5   21.5   18.5
15.5   10.5   3.5   37.5   31.5
27.5   21.5   13.5   7.5   3
-3183   -31937   8

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM, and the IBM basica/D interpreter, version GW BASIC 3.11,  the wall-clock time through JJJJ= -31937 was three minutes.

References

[1] Andre R. S. Amaral (2006), On the Exact Solution of a Facility Layout Problem.  European Journal of Operational Research 173 (2006), pp. 508-518.

[2] Andre R. S. Amaral (2008), An Exact Approach to the One-Dimensional Facility Layout Problem.  Operations Research, Vol. 56, No. 4 (July-August, 2008), pp. 1026-1033.

[3] Andre R. S. Amaral (2011), Optimal Solutions for the Double Row Layout Problem.  Optimization Letters, DOI 10.1007/s11590-011-0426-8, published on line 30 November 2011, Springer-Verlag 2011.

[4] Andre R. S. Amaral (2012), The Corridor Allocation Problem.  Computers and Operations Research 39 (2012), pp. 3325-3330.

[5] Miguel F. Anjos, Anthony Vannelli, Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes.  INFORMS Journal on Computing, Vol. 20, No. 4, Fall 2008, pp. 611-617.

[6] David L. Applegate, Robert E. Bixby, Vasek Chvatal, William J. Cook, The Traveling Salesman Problem: A Computational Study.  Princeton and Oxford: Princeton University Press, 2006.

[7] L. L. Barachet (1957), Graphic Solution of the Travelling Salesman Problem.  Operations Research, Vol. 5, pp. 841-845.

[8] T. Y. Chen, H. C. Chen (2009), Mixed-Discrete Structural Optimization Using a Rank-Niche Evolution Strategy, Engineering Optimization, 41:1, 39-58.

[9] Leon Cooper, U. N. Bhat, L. J. LeBlanc, Introduction to Operations Research Models.  W. B. Saunders Company, 1977.

[10] George B. Dantzig, Discrete-Variable Extremum Problems.  Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.

[11] G. Dantzig, R. Fulkerson, S. Johnson, Solution of a Large-Scale Traveling-Salesman Problem. 
Operations Research, Vol. 2, No. 4 (Nov., 1954), pp. 393-410.

[12] Zvi Drezner (1980), DISCON: A New Method for the Layout Problem.  Operations Research, Vol. 28, No. 6 (Nov. - Dec., 1980), pp. 1375-1384.

[13] W. J. Fabrycky, P. M. Ghare, P. E. Torgersen, Applied Operations Research and Management Science.  Englewood Cliffs, N. J. 07362: Prentice-Hall, Inc., 1984.

[14] Billy E. Gillett, Introduction to Operations Research: A Computer-Oriented Algorithmic Approach.  McGraw-Hill, Inc., 1976.

[15] Diptesh Ghosh, Ravi Kothari, Population Heuristics for the Corridor Allocation Problem, W.P. No. 2012-09-02, September 2012.  Retrieved on September 14 2012 from Google search.

[16] Martin Grotschel, Olaf Holland (1991), Solution of Large-Scale Symmetric Travelling Salesman Problems, Mathematical Programming 51, pp. 141-202.

[17] Sunderesh S. Heragu, Andrew Kusiak (1988), Machine Layout Problem in Flexible Manufacturing Systems.  Operations Research, Vol. 36, No. 2, Operations Research in Manufacturing (Mar. - Apr., 1988), pp. 258-268.

[18] S. S. Heragu, A. Kusiak (1991), Efficient Models for the Facility Layout Problem.  European Journal of Operational Research, Vol. 53 (1991), pp. 1-13.

[19] S. S. Heragu, Facilities Design, Third Edition.  Boca Raton, Florida: CRC Press, 2008.

[20] Michael Junger, Thomas M. Liebling, Dennis Naddef, George L. Nemhauser, William R. Pulleybank, Gerhart Reinelt, Giovanni Rinaldi, Lawrence A. Wolsey--Editors, 50 Years of Integer Programming 1958-2008.  Berlin: Springer, 2010.

[21] R. L. Karg, G. L. Thompson (1964), A Heuristic Approach to Solving Travelling Salesman Problems.  Management Science, Vol. 10, Number 2, pp. 225-248.

[22] K. Ravi Kumar, George C. Hadjinicola, Ting-li Lin (1995), A Heuristic Procedure for the Single-Row Facility Layout Problem.  European Journal of Operational Research 87 (1995) 65-73.

[23]  A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems.  Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.

[24] E. L. Lawler, M. D. Bell, A Method for Solving Discrete Optimization Problems.  Operations Research, Vol. 14, No. 6 (Nov.-Dec., 1966), pp. 1098-1112.

[25] Robert F. Love, Jsun Y. Wong (1976), On Solving a One-Dimensional Space Allocation Problem with Integer Programming.  INFOR, Vol. 14, No. 2, June 1976, pp. 139-143.
 
[26] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems.  Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.     

[27] Ken McAloon, Carol Tretkoff, Optimization and Computational Logic.  John Wiley and Sons, Inc., 1996.

[28] 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.

[29] Katta G. Murty, Opereations Research: Deterministic Optimization Models.  Prentice Hall, Upper Saddle River, New Jersey 07458, 1994.

[30] C. E. Nugent, T. E. Vollmann, J. Ruml (1968), An Experimental Comparison of Techniques for the Assignment of Facilities to Locations, Operations Research 16 (1968), pp. 150-173.

[31] Christopher J. Picone, Wilbert E. Wilhelm (1986), "A Perturbation Scheme To Improve Hillier's Solution to the Facilities Layout Problem": a Clarification.  Management Science Vol. 32, No. 2, February 1986, pp. 253-254. 

[32] Cliff T. Ragsdale, Spreadsheet Modeling and Decision Analysis, Fifth Edition.  South-Westen, Cengage Learning, 2008.

[33] H. H. Rosenbrock (1960), An Automatic Method for Finding the Greatest or Least Value of a Function, Computer Journal Vol. 3, pp. 175-184.

[34] Donald M. Simmons (1969), One-Dimensional Space Allocation: An Ordering Algorithm.     Operations Research, Vol. 17, No. 5 (Sep. - Oct., 1969), pp. 812-826.

[35] Wayne L. Winston, Munirpallam Venkataramanan, Introduction to Mathematical Programming: Operations Research, Volume One, Fourth Edition.  Pacific Grove, CA 93950: Brooks/Cole--Thomson Learning, 2003.

[36] Wayne L. Winston, S. Christian Albright, Practical Management Science, Third Edition.  Thomson/South-Western, 2007.

[37] Jsun Yui Wong (2009, July 18).  An Integer Programming Computer Program Applied to One-Dimensional Space Allocation.  Retrieved from http://wongsllllblog.blogspot.com/2009/07/

[38] Jsun Yui Wong (2009, November 2).  A Computer Program for Relative Location of Circular Facilities.  Retrieved on September 3, 2012, from http://wongsllllblog.blogspot.ca/2009/11/

[39] Jsun Yui Wong (2009, December 18).  A Heuristic Nonlinear Integer Solver Applied to a Problem of Assignment of Facilities to Locations.  Retrieved from http://wongsnewnewblog.blogspot.ca/2009/12/

[40] Jsun Yui Wong (2011, October 27).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a New Formulation of a Twelve-City Traveling Salesman Problem, Sixth Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/10/27/

[41] Ji-Hui Zhang, Xin-He Xu (1999), An Efficient Evolutionary Programming Algorithm.  Computers and Operations Research 26, 645-663.

A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Corridor Allocation Problem with Fifteen Facilities, Fourth Edition

Jsun Yui Wong

The following computer program is cautious of the possibility that this instance of the corridor allocation problem can be unusual in that one row has nine facilities--see line 374--and the other row has six facilities.  One recalls that the older editions have one row having eight facilities and the other row having seven facilities.

0 REM DEFDBL A-Z
1 DEFINT I,J,K,X,A
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J44(2002),J(99),AA(99),HR(32),HHR(32),Y(33),C(33),CC(33)
3 DIM HS(49,49)
4 DIM PE(49,49)
5 DIM SD(49,49)
27   HR(1)=20:HR(2)=3:HR(3)=9:HR(4)=3:HR(5)=7
28   REM   HR(6)=4:HR(7)=6:HR(8)=8:HR(9)=9
29   HR(6)=3:HR(7)=7:HR(8)=5:HR(9)=9:HR(10)=6
30   HR(11)=5:HR(12)=3:HR(13)=9:HR(14)=3:HR(15)=7
31 FOR IL=1 TO 15
32 FOR JL=1 TO 15
33 READ HS(IL,JL)
34 NEXT JL
35 NEXT IL
61 DATA 999,10,0,5,1,0,1,2,2,2,2,0,4,0,0
62 DATA 10,999,1,3,2,2,2,3,2,0,2,0,10,5,0
63 DATA 0,1,999,10,2,0,2,5,4,5,2,2,5,5,5
64 DATA 5,3,10,999,1,1,5,0,0,2,1,0,2,5,0
66 DATA 1,2,2,1,999,3,5,5,5,1,0,3,0,5,5
67 DATA 0,2,0,1,3,999,2,2,1,5,0,0,2,5,10
68 DATA 1,2,2,5,5,2,999,6,0,1,5,5,5,1,0
69 DATA 2,3,5,0,5,2,6,999,5,2,10,0,5,0,0
70 DATA 2,2,4,0,5,1,0,5,999,0,10,5,10,0,2
71 DATA 2,0,5,2,1,5,1,2,0,999,0,4,0,0,5
72 DATA 2,2,2,1,0,0,5,10,10,0,999,5,0,5,0
73 DATA 0,0,2,0,3,0,5,0,5,4,3,999,3,3,0
74 DATA 4,10,5,2,0,2,5,5,10,0,0,3,999,10,2
75 DATA 0,5,5,5,5,5,1,0,0,0,5,3,10,999,4
76 DATA 0,0,5,0,5,10,0,0,2,5,0,0,2,4,999
78 FOR JJJJ=-32000 TO 32000
79 RANDOMIZE JJJJ
80 M=-1D+37
81 FOR J44=1 TO 15
83 A(J44)=J44
84 NEXT J44
126 REM IMAR=10+FIX(RND*1000)
128 FOR I=1 TO 500
129 FOR KKQQ=1 TO 15
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 III=1+FIX(RND*15)
134 JJJ=1+FIX(RND*15)
221    X(III)=A(JJJ)
223    X(JJJ)=A(III)
231 FOR J44=1 TO 15
233 FOR J45=1 TO 15
234 IF X(J44)=J45 THEN HHR(J44)=HR(J44)  ELSE GOTO 238
237 Y(J45)=J44
238 NEXT J45
330 C(1)=.5*HHR(Y(1))+HHR(Y(2))+HHR(Y(3))+HHR(Y(4))+HHR(Y(5))+HHR(Y(6) )+HHR(Y(7)   )+HHR(Y(8)  ) +HHR(Y(9))
331 C(2)=.5*HHR(Y(2))+HHR(Y(3))+HHR(Y(4))+HHR(Y(5))+HHR(Y(6))+HHR(Y(7) )+HHR(Y(8)   )+HHR(Y(9)  )
333 C(3)=.5*HHR(Y(3))+HHR(Y(4))+HHR(Y(5))+HHR(Y(6))+HHR(Y(7))+HHR(Y(8) )+HHR(Y(9)   )
335 C(4)=.5*HHR(Y(4))+HHR(Y(5))+HHR(Y(6))+HHR(Y(7))+HHR(Y(8))+HHR(Y(9) )
361 C(5)=.5*HHR(Y(5))+HHR(Y(6))+HHR(Y(7))+HHR(Y(8))+HHR(Y(9))
364 C(6)=.5*HHR(Y(6))+HHR(Y(7))+HHR(Y(8))+HHR(Y(9))
368 C(7)=.5*HHR(Y(7))+HHR(Y(8))+HHR(Y(9))
373 C(8)=.5*HHR(Y(8))+HHR(Y(9))
374 C(9)=.5*HHR(Y(9))
379 C(10)=.5*HHR(Y(10))+HHR(Y(11))+HHR(Y(12))+HHR(Y(13))+HHR(Y(14))+HHR(Y(15) )
380 C(11)=.5*HHR(Y(11))+HHR(Y(12))+HHR(Y(13))+HHR(Y(14))+HHR(Y(15))
381 C(12)=.5*HHR(Y(12))+HHR(Y(13))+HHR(Y(14))+HHR(Y(15))
382 C(13)=.5*HHR(Y(13))+HHR(Y(14))+HHR(Y(15))
383 C(14)=.5*HHR(Y(14))+HHR(Y(15))
384 C(15)=.5*HHR(Y(15))
395 NEXT J44
411 PROD=0
412 FOR J44=1 TO 15
413 FOR J45=J44+1 TO 15
414 PROD=PROD    -HS(Y(J44),Y(J45))*ABS(  C(J44)-C(J45)  )
415 NEXT J45
416 NEXT J44
422 P=PROD
1111 IF P<=M THEN 1670
1452 M=P
1453 FOR KLX=1 TO 15
1454 CC(KLX)=C(KLX)
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-3222 THEN 1999
1901 PRINT A(1),A(2),A(3),A(4),A(5)
1902 PRINT A(6),A(7),A(8),A(9),A(10)
1903 PRINT A(11),A(12),A(13),A(14),A(15)
1905   PRINT CC(1),CC(2),CC(3),CC(4),CC(5)
1906   PRINT CC(6),CC(7),CC(8),CC(9),CC(10)
1907   PRINT CC(11),CC(12),CC(13),CC(14),CC(15)
1919 PRINT M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter.  The complete output through JJJJ=-31908 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

10   2   14   6   7
8   13   3   1   9
12   4   11   5   15
37.5   31.5   27.5   23.5   20.5
17.5   12.5   7.5   3   47
32.5   25.5   19.5   11.5   3.5
-3217   -31998

10   3   14   6   7
8   13   2   1   9
11   4   12   5   15
37.5   30.5   26.5   23.5   20.5
17.5   12.5   7.5   3   47
34.5   27.5   19.5   11.5   3.5
-3216   -31987

10   3   14   6   7
8   13   2   1   9
11   4   12   5   15
37.5   30.5   26.5   23.5   20.5
17.5   12.5   7.5   3   47
34.5   27.5   19.5   11.5   3.5
-3216   -31977

10   2   14   6   7
8   13   2   1   9
12   4   11   5   15
37.5   31.5   27.5   23.5   20.5
17.5   12.5   7.5   3   47
32.5   25.5   19.5   11.5   3.5
-3217   -31972

10   2   14   6   7
8   13   2   1   9
12   4   11   5   15
37.5   31.5   27.5   23.5   20.5
17.5   12.5   7.5   3   47
32.5   25.5   19.5   11.5   3.5
-3217   -31966

10   2   14   6   7
8   13   2   1   9
12   4   11   5   15
37.5   31.5   27.5   23.5   20.5
17.5   12.5   7.5   3   47
32.5   25.5   19.5   11.5   3.5
-3217   -31965

10   3   14   6   7
8   13   2   1   9
11   4   12   5   15
37.5   30.5   26.5   23.5   20.5
17.5   12.5   7.5   3   47
34.5   27.5   19.5   11.5   3.5
-3216   -31946

10   3   14   6   7
8   13   2   1   9
11   4   12   5   15
37.5   30.5   26.5   23.5   20.5
17.5   12.5   7.5   3   47
34.5   27.5   19.5   11.5   3.5
-3216   -31935

10   3   14   6   7
8   13   2   1   9
11   4   12   5   15
37.5   30.5   26.5   23.5   20.5
17.5   12.5   7.5   3   47
34.5   27.5   19.5   11.5   3.5
-3216   -31922

1   3   13   7   8
14   12   4   10   15
2   5   11   6   9
46   33.5   29.5   25.5   21.5
18.5   15.5   10.5   3.5   38.5
29.5   21.5   13.5   7.5   3
-3222   -31908

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM, and the IBM basica/D interpreter, version GW BASIC 3.11,  the wall-clock time through JJJJ= -31908 was two minutes.

Thus the computer programs of the older editions have produced more attractive computational results.

References

[1] Andre R. S. Amaral (2006), On the Exact Solution of a Facility Layout Problem.  European Journal of Operational Research 173 (2006), pp. 508-518.

[2] Andre R. S. Amaral (2008), An Exact Approach to the One-Dimensional Facility Layout Problem.  Operations Research, Vol. 56, No. 4 (July-August, 2008), pp. 1026-1033.

[3] Andre R. S. Amaral (2011), Optimal Solutions for the Double Row Layout Problem.  Optimization Letters, DOI 10.1007/s11590-011-0426-8, published on line 30 November 2011, Springer-Verlag 2011.

[4] Andre R. S. Amaral (2012), The Corridor Allocation Problem.  Computers and Operations Research 39 (2012), pp. 3325-3330.

[5] Miguel F. Anjos, Anthony Vannelli, Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes.  INFORMS Journal on Computing, Vol. 20, No. 4, Fall 2008, pp. 611-617.

[6] David L. Applegate, Robert E. Bixby, Vasek Chvatal, William J. Cook, The Traveling Salesman Problem: A Computational Study.  Princeton and Oxford: Princeton University Press, 2006.

[7] L. L. Barachet (1957), Graphic Solution of the Travelling Salesman Problem.  Operations Research. Vol. 5, pp. 841-845.

[8] T. Y. Chen, H. C. Chen (2009), Mixed-Discrete Structural Optimization Using a Rank-Niche Evolution Strategy, Engineering Optimization, 41:1, 39-58.

[9] Leon Cooper, U. N. Bhat, L. J. LeBlanc, Introduction to Operations Research Models.  W. B. Saunders Company, 1977.

[10] George B. Dantzig, Discrete-Variable Extremum Problems.  Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.

[11] G. Dantzig, R. Fulkerson, S. Johnson, Solution of a Large-Scale Traveling-Salesman Problem. 
Operations Research, Vol. 2, No. 4 (Nov., 1954), pp. 393-410.

[12] Zvi Drezner (1980), DISCON: A New Method for the Layout Problem.  Operations Research, Vol. 28, No. 6 (Nov. - Dec., 1980), pp. 1375-1384.

[13] W. J. Fabrycky, P. M. Ghare, P. E. Torgersen, Applied Operations Research and Management Science.  Englewood Cliffs, N. J. 07362: Prentice-Hall, Inc., 1984.

[14] Billy E. Gillett, Introduction to Operations Research: A Computer-Oriented Algorithmic Approach.  McGraw-Hill, Inc., 1976.

[15] Diptesh Ghosh, Ravi Kothari, Population Heuristics for the Corridor Allocation Problem, W.P. No. 2012-09-02, September 2012.  Retrieved on September 14 2012 from Google search.

[16] Martin Grotschel, Olaf Holland (1991), Solution of Large-Scale Symmetric Travelling Salesman Problems, Mathematical Programming 51, pp. 141-202.

[17] Sunderesh S. Heragu, Andrew Kusiak (1988), Machine Layout Problem in Flexible Manufacturing Systems.  Operations Research, Vol. 36, No. 2, Operations Research in Manufacturing (Mar. - Apr., 1988), pp. 258-268.

[18] S. S. Heragu, A. Kusiak (1991), Efficient Models for the Facility Layout Problem.  European Journal of Operational Research, Vol. 53 (1991), pp. 1-13.

[19] S. S. Heragu, Facilities Design, Third Edition.  Boca Raton, Florida: CRC Press, 2008.

[20] Michael Junger, Thomas M. Liebling, Dennis Naddef, George L. Nemhauser, William R. Pulleybank, Gerhart Reinelt, Giovanni Rinaldi, Lawrence A. Wolsey--Editors, 50 Years of Integer Programming 1958-2008.  Berlin: Springer, 2010.

[21] R. L. Karg, G. L. Thompson (1964), A Heuristic Approach to Solving Travelling Salesman Problems.  Management Science, Vol. 10, Number 2, pp. 225-248.

[22] K. Ravi Kumar, George C. Hadjinicola, Ting-li Lin (1995), A Heuristic Procedure for the Single-Row Facility Layout Problem.  European Journal of Operational Research 87 (1995) 65-73.

[23]  A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems.  Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.

[24] E. L. Lawler, M. D. Bell, A Method for Solving Discrete Optimization Problems.  Operations Research, Vol. 14, No. 6 (Nov.-Dec., 1966), pp. 1098-1112.

[25] Robert F. Love, Jsun Y. Wong (1976), On Solving a One-Dimensional Space Allocation Problem with Integer Programming.  INFOR, Vol. 14, No. 2, June 1976, pp. 139-143.
 
[26] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems.  Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.     

[27] Ken McAloon, Carol Tretkoff, Optimization and Computational Logic.  John Wiley and Sons, Inc., 1996.

[28] 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.

[29] Katta G. Murty, Opereations Research: Deterministic Optimization Models.  Prentice Hall, Upper Saddle River, New Jersey 07458, 1994.

[30] C. E. Nugent, T. E. Vollmann, J. Ruml (1968), An Experimental Comparison of Techniques for the Assignment of Facilities to Locations, Operations Research 16 (1968), pp. 150-173.

[31] Christopher J. Picone, Wilbert E. Wilhelm (1986), "A Perturbation Scheme To Improve Hillier's Solution to the Facilities Layout Problem": a Clarification.  Management Science Vol. 32, No. 2, February 1986, pp. 253-254. 

[32] Cliff T. Ragsdale, Spreadsheet Modeling and Decision Analysis, Fifth Edition.  South-Westen, Cengage Learning, 2008.

[33] H. H. Rosenbrock (1960), An Automatic Method for Finding the Greatest or Least Value of a Function, Computer Journal Vol. 3, pp. 175-184.

[34] Donald M. Simmons (1969), One-Dimensional Space Allocation: An Ordering Algorithm.     Operations Research, Vol. 17, No. 5 (Sep. - Oct., 1969), pp. 812-826.

[35] Wayne L. Winston, Munirpallam Venkataramanan, Introduction to Mathematical Programming: Operations Research, Volume One, Fourth Edition.  Pacific Grove, CA 93950: Brooks/Cole--Thomson Learning, 2003.

[36] Wayne L. Winston, S. Christian Albright, Practical Management Science, Third Edition.  Thomson/South-Western, 2007.

[37] Jsun Yui Wong (2009, July 18).  An Integer Programming Computer Program Applied to One-Dimensional Space Allocation.  Retrieved from http://wongsllllblog.blogspot.com/2009/07/

[38] Jsun Yui Wong (2009, November 2).  A Computer Program for Relative Location of Circular Facilities.  Retrieved on September 3, 2012, from http://wongsllllblog.blogspot.ca/2009/11/

[39] Jsun Yui Wong (2009, December 18).  A Heuristic Nonlinear Integer Solver Applied to a Problem of Assignment of Facilities to Locations.  Retrieved from http://wongsnewnewblog.blogspot.ca/2009/12/

[40] Jsun Yui Wong (2011, October 27).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a New Formulation of a Twelve-City Traveling Salesman Problem, Sixth Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/10/27/

[41] Ji-Hui Zhang, Xin-He Xu (1999), An Efficient Evolutionary Programming Algorithm.  Computers and Operations Research 26, 645-663.

A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Corridor Allocation Problem with Eleven Facilities, Third Edition

Jsun Yui Wong

The following computer program seeks to solve Problem S11 on page 3328 of Amaral [3] and on page 9 of Ghosh and Kothari [14]. 

Because of line 233 through line 240, the computer program here is shorter than the computer program of the Second Edition.

0 REM DEFDBL A-Z
1 DEFINT I,J,K,X,A
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J44(2002),J(99),AA(99),HR(32),HHR(32),Y(33),C(33),CC(33)
3 DIM HS(49,49)
4 DIM PE(49,49)
5 DIM SD(49,49)
27   HR(1)=3:HR(2)=9:HR(3)=3:HR(4)=7:HR(5)=3
28   HR(6)=7:HR(7)=5:HR(8)=9:HR(9)=6:HR(10)=5
29   HR(11)=10
31 FOR IL=1 TO 11
32 FOR JL=1 TO 11
33 READ HS(IL,JL)
34 NEXT JL
35 NEXT IL
61 DATA 999,20,2,8,0,9,5,7,0,20,3
62 DATA 20,999,8,9,13,17,16,1,8,6,7
63 DATA 2,8,999,18,0,10,4,18,5,8,0
64 DATA 8,9,18,999,6,16,10,4,2,14,6
66 DATA 0,13,0,6,999,6,0,11,0,8,2
67 DATA 9,17,10,16,6,999,6,13,2,7,18
68 DATA 5,16,4,10,0,6,999,1,11,15,7
69 DATA 7,1,18,4,11,13,1,999,1,7,2
70 DATA 0,8,5,2,0,2,11,1,999,12,0
71 DATA 20,6,8,14,8,7,15,7,12,999,3
72 DATA 3,7,0,6,2,18,7,2,0,3,999
78 FOR JJJJ=-32000 TO 32000
79 RANDOMIZE JJJJ
80 M=-1D+37
81 FOR J44=1 TO 11
83 A(J44)=J44
84 NEXT J44
126 REM IMAR=10+FIX(RND*1000)
128 FOR I=1 TO 500
129 FOR KKQQ=1 TO 11
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 III=1+FIX(RND*11)
134 JJJ=1+FIX(RND*11)
221    X(III)=A(JJJ)
223    X(JJJ)=A(III)
231 FOR J44=1 TO 11
233 FOR J45=1 TO 11
234 IF X(J44)=J45 THEN HHR(J44)=HR(J44)  ELSE GOTO 240
237 Y(J45)=J44
240 NEXT J45
310 C(1)=.5*HHR(Y(1))+HHR(Y(2))+HHR(Y(3))+HHR(Y(4))+HHR(Y(5))+HHR(Y(6))
311 C(2)=.5*HHR(Y(2))+HHR(Y(3))+HHR(Y(4))+HHR(Y(5))+HHR(Y(6))
314 C(3)=.5*HHR(Y(3))+HHR(Y(4))+HHR(Y(5))+HHR(Y(6))
318 C(4)=.5*HHR(Y(4))+HHR(Y(5))+HHR(Y(6))
323 C(5)=.5*HHR(Y(5))+HHR(Y(6))
328 C(6)=.5*HHR(Y(6))
341 C(7)=.5*HHR(Y(7))+HHR(Y(8))+HHR(Y(9))+HHR(Y(10))+HHR(Y(11))
345 C(8)=.5*HHR(Y(8))+HHR(Y(9))+HHR(Y(10))+HHR(Y(11))
349 C(9)=.5*HHR(Y(9))+HHR(Y(10))+HHR(Y(11))
353 C(10)=.5*HHR(Y(10))+HHR(Y(11))
355 C(11)=.5*HHR(Y(11))
357 NEXT J44
359 PROD=0
361 FOR J44=1 TO 11
368 FOR J45=J44+1 TO 11
371 PROD=PROD    -HS(Y(J44),Y(J45))*ABS(  C(J44)-C(J45)  )
381 NEXT J45
388 NEXT J44
422 P=PROD
1111 IF P<=M THEN 1670
1452 M=P
1453 FOR KLX=1 TO 11
1454 CC(KLX)=C(KLX)
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-3444 THEN 1999
1901 PRINT A(1),A(2),A(3),A(4),A(5)
1902 PRINT A(6),A(7),A(8),A(9),A(10),A(11)
1903   PRINT CC(1),CC(2),CC(3),CC(4),CC(5)
1904   PRINT CC(6),CC(7),CC(8),CC(9),CC(10),CC(11)
1919 PRINT M,JJJJ
1999 NEXT JJJJ
6799 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter.  The complete output through JJJJ=-31954 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

8   7   4   9   10
5   2   6   1   3
11
32   26.5   21.5   17.5   12.5
4.5   27.5   21.5   16.5   11.5
5
-3439.5   -31990

8   7   4   9   10
5   2   6   1   3
11
32   26.5   21.5   17.5   12.5
4.5   27.5   21.5   16.5   11.5
5
-3439.5   -31954

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM, and the IBM basica/D interpreter, version GW BASIC 3.11,  the wall-clock time through JJJJ= -31954 was 21 seconds.

References

[1] Andre R. S. Amaral (2006), On the Exact Solution of a Facility Layout Problem.  European Journal of Operational Research 173 (2006), pp. 508-518.

[2] Andre R. S. Amaral (2008), An Exact Approach to the One-Dimensional Facility Layout Problem.  Operations Research, Vol. 56, No. 4 (July-August, 2008), pp. 1026-1033.

[3] Andre R. S. Amaral (2012), The Corridor Allocation Problem.  Computers and Operations Research 39 (2012), pp. 3325-3330.

[4] Miguel F. Anjos, Anthony Vannelli, Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes.  INFORMS Journal on Computing, Vol. 20, No. 4, Fall 2008, pp. 611-617.

[5] David L. Applegate, Robert E. Bixby, Vasek Chvatal, William J. Cook, The Traveling Salesman Problem: A Computational Study.  Princeton and Oxford: Princeton University Press, 2006.

[6] L. L. Barachet (1957), Graphic Solution of the Travelling Salesman Problem.  Operations Research, Vol. 5, pp. 841-845.

[7] T. Y. Chen, H. C. Chen (2009), Mixed-Discrete Structural Optimization Using a Rank-Niche Evolution Strategy, Engineering Optimization, 41:1, 39-58.

[8] Leon Cooper, U. N. Bhat, L. J. LeBlanc, Introduction to Operations Researach Models.  W. B. Saunders Company, 1977.

[9] George B. Dantzig,  Discrete-Variable Extremum Problems.  Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.

[10] G. Dantzig, R. Fulkerson, S. Johnson, Solution of a Large-Scale Traveling-Salesman Problem. 
Operations Research, Vol. 2, No. 4 (Nov., 1954), pp. 393-410.

[11] Zvi Drezner (1980), DISCON: A New Method for the Layout Problem.  Operations Research, Vol. 28, No. 6 (Nov. - Dec., 1980), pp. 1375-1384.

[12] W. J. Fabrycky, P. M. Ghare, P. E. Torgersen, Applied Operations Research and Management Science.  Englewood Cliffs, N. J. 07362: Prentice-Hall, Inc., 1984.

[13] Billy E. Gillett, Introduction to Operations Research: A Computer-Oriented Algorithmic Approach.  McGraw-Hill, Inc., 1976.

[14] Diptesh Ghosh, Ravi Kothari, Population Heuristics for the Corridor Allocation Problem, W.P. No. 2012-09-02, September 2012.  Retrieved on September 14 2012 from Google search.

[15] Martin Grotschel, Olaf Holland (1991), Solution of Large-Scale Symmetric Travelling Salesman Problems, Mathematical Programming 51, pp. 141-202.

[16] Sunderesh S. Heragu, Andrew Kusiak (1988), Machine Layout Problem in Flexible Manufacturing Systems.  Operations Research, Vol. 36, No. 2, Operations Research in Manufacturing (Mar. - Apr., 1988), pp. 258-268.

[17] S. S. Heragu, A. Kusiak (1991), Efficient Models for the Facility Layout Problem.  European Journal of Operational Research, Vol. 53 (1991), pp. 1-13.

[18] S. S. Heragu, Facilities Design, Third Edition.  Boca Raton, Florida: CRC Press, 2008.

[19] Michael Junger, Thomas M. Liebling, Dennis Naddef, George L. Nemhauser, William R. Pulleybank, Gerhart Reinelt, Giovanni Rinaldi, Lawrence A. Wolsey--Editors, 50 Years of Integer Programming 1958-2008.  Berlin: Springer, 2010.

[20] R. L. Karg, G. L. Thompson (1964), A Heuristic Approach to Solving Travelling Salesman Problems.  Management Science, Vol. 10, Number 2, pp. 225-248.

[21] K. Ravi Kumar, George C. Hadjinicola, Ting-li Lin (1995), A Heuristic Procedure for the Single-Row Facility Layout Problem.  European Journal of Operational Research 87 (1995) 65-73.

[22]  A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems.  Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.

[23] E. L. Lawler, M. D. Bell, A Method for Solving Discrete Optimization Problems.  Operations Research, Vol. 14, No. 6 (Nov.-Dec., 1966), pp. 1098-1112.

[24] Robert F. Love, Jsun Y. Wong (1976), On Solving a One-Dimensional Space Allocation Problem with Integer Programming.  INFOR, Vol. 14, No. 2, June 1976, pp. 139-143.
 
[25] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems.  Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.     

[26] Ken McAloon, Carol Tretkoff, Optimization and Computational Logic.  John Wiley and Sons, Inc., 1996.

[27] 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.

[28] Katta G. Murty, Opereations Research: Deterministic Optimization Models.  Prentice Hall, Upper Saddle River, New Jersey 07458, 1994.

[29] C. E. Nugent, T. E. Vollmann, J. Ruml (1968), An Experimental Comparison of Techniques for the Assignment of Facilities to Locations, Operations Research 16 (1968), pp. 150-173.

[30] Christopher J. Picone, Wilbert E. Wilhelm (1986), "A Perturbation Scheme To Improve Hillier's Solution to the Facilities Layout Problem": a Clarification.  Management Science Vol. 32, No. 2, February 1986, pp. 253-254. 

[31] Cliff T. Ragsdale, Spreadsheet Modeling and Decision Analysis, Fifth Edition.  South-Westen, Cengage Learning, 2008.

[32] H. H. Rosenbrock (1960), An Automatic Method for Finding the Greatest or Least Value of a Function, Computer Journal Vol. 3, pp. 175-184.

[33] Donald M. Simmons (1969), One-Dimensional Space Allocation: An Ordering Algorithm.     Operations Research, Vol. 17, No. 5 (Sep. - Oct., 1969), pp. 812-826.

[34] Wayne L. Winston, Munirpallam Venkataramanan, Introduction to Mathematical Programming: Operations Research, Volume One, Fourth Edition.  Pacific Grove, CA 93950: Brooks/Cole--Thomson Learning, 2003.

[35] Wayne L. Winston, S. Christian Albright, Practical Management Science, Third Edition.  Thomson/South-Western, 2007.

[36] Jsun Yui Wong (2009, July 18).  An Integer Programming Computer Program Applied to One-Dimensional Space Allocation.  Retrieved from http://wongsllllblog.blogspot.com/2009/07/

[37] Jsun Yui Wong (2009, November 2).  A Computer Program for Relative Location of Circular Facilities.  Retrieved on September 3, 2012, from http://wongsllllblog.blogspot.ca/2009/11/

[38] Jsun Yui Wong (2009, December 18).  A Heuristic Nonlinear Integer Solver Applied to a Problem of Assignment of Facilities to Locations.  Retrieved from http://wongsnewnewblog.blogspot.ca/2009/12/

[39] Jsun Yui Wong (2011, October 27).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a New Formulation of a Twelve-City Traveling Salesman Problem, Sixth Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/10/27/

[40] Ji-Hui Zhang, Xin-He Xu (1999), An Efficient Evoutionary Programming Algorithm.  Computers and Operations Research 26, 645-663.

A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Corridor Allocation Problem with Fifteen Facilities, Third Edition

Jsun Yui Wong

The following computer program seeks to solve the n=15 corridor allocation problem on page 3328 of Amaral [3] and on page 9 of Ghosh and Kothari [14].  The lengths of line 27 through line 30 and the flows of line 61 through line 76 are from Amaral [2, p. 1031].

Line 234 here is different from line 234 of the preceding paper.

0 REM DEFDBL A-Z
1 DEFINT I,J,K,X,A
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J44(2002),J(99),AA(99),HR(32),HHR(32),Y(33),C(33),CC(33)
3 DIM HS(49,49)
4 DIM PE(49,49)
5 DIM SD(49,49)
27   HR(1)=20:HR(2)=3:HR(3)=9:HR(4)=3:HR(5)=7
28   REM   HR(6)=4:HR(7)=6:HR(8)=8:HR(9)=9
29   HR(6)=3:HR(7)=7:HR(8)=5:HR(9)=9:HR(10)=6
30   HR(11)=5:HR(12)=3:HR(13)=9:HR(14)=3:HR(15)=7
31 FOR IL=1 TO 15
32 FOR JL=1 TO 15
33 READ HS(IL,JL)
34 NEXT JL
35 NEXT IL
61 DATA 999,10,0,5,1,0,1,2,2,2,2,0,4,0,0
62 DATA 10,999,1,3,2,2,2,3,2,0,2,0,10,5,0
63 DATA 0,1,999,10,2,0,2,5,4,5,2,2,5,5,5
64 DATA 5,3,10,999,1,1,5,0,0,2,1,0,2,5,0
66 DATA 1,2,2,1,999,3,5,5,5,1,0,3,0,5,5
67 DATA 0,2,0,1,3,999,2,2,1,5,0,0,2,5,10
68 DATA 1,2,2,5,5,2,999,6,0,1,5,5,5,1,0
69 DATA 2,3,5,0,5,2,6,999,5,2,10,0,5,0,0
70 DATA 2,2,4,0,5,1,0,5,999,0,10,5,10,0,2
71 DATA 2,0,5,2,1,5,1,2,0,999,0,4,0,0,5
72 DATA 2,2,2,1,0,0,5,10,10,0,999,5,0,5,0
73 DATA 0,0,2,0,3,0,5,0,5,4,3,999,3,3,0
74 DATA 4,10,5,2,0,2,5,5,10,0,0,3,999,10,2
75 DATA 0,5,5,5,5,5,1,0,0,0,5,3,10,999,4
76 DATA 0,0,5,0,5,10,0,0,2,5,0,0,2,4,999
78 FOR JJJJ=-32000 TO 32000
79 RANDOMIZE JJJJ
80 M=-1D+37
81 FOR J44=1 TO 15
83 A(J44)=J44
84 NEXT J44
126 REM IMAR=10+FIX(RND*1000)
128 FOR I=1 TO 500
129 FOR KKQQ=1 TO 15
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 III=1+FIX(RND*15)
134 JJJ=1+FIX(RND*15)
221    X(III)=A(JJJ)
223    X(JJJ)=A(III)
231 FOR J44=1 TO 15
233 FOR J45=1 TO 15
234 IF X(J44)=J45 THEN HHR(J44)=HR(J44)  ELSE GOTO 240
237 Y(J45)=J44
240 NEXT J45
331 C(1)=.5*HHR(Y(1))+HHR(Y(2))+HHR(Y(3))+HHR(Y(4))+HHR(Y(5))+HHR(Y(6) )+HHR(Y(7)   )+HHR(Y(8)  )
333 C(2)=.5*HHR(Y(2))+HHR(Y(3))+HHR(Y(4))+HHR(Y(5))+HHR(Y(6))+HHR(Y(7) )+HHR(Y(8)   )
335 C(3)=.5*HHR(Y(3))+HHR(Y(4))+HHR(Y(5))+HHR(Y(6))+HHR(Y(7))+HHR(Y(8) )
361 C(4)=.5*HHR(Y(4))+HHR(Y(5))+HHR(Y(6))+HHR(Y(7))+HHR(Y(8))
364 C(5)=.5*HHR(Y(5))+HHR(Y(6))+HHR(Y(7))+HHR(Y(8))
368 C(6)=.5*HHR(Y(6))+HHR(Y(7))+HHR(Y(8))
373 C(7)=.5*HHR(Y(7))+HHR(Y(8))
377 C(8)=.5*HHR(Y(8))
378 C(9)=.5*HHR(Y(9))+HHR(Y(10))+HHR(Y(11))+HHR(Y(12))+HHR(Y(13))+HHR(Y(14) )+HHR(Y(15)   )
379 C(10)=.5*HHR(Y(10))+HHR(Y(11))+HHR(Y(12))+HHR(Y(13))+HHR(Y(14))+HHR(Y(15) )
380 C(11)=.5*HHR(Y(11))+HHR(Y(12))+HHR(Y(13))+HHR(Y(14))+HHR(Y(15))
381 C(12)=.5*HHR(Y(12))+HHR(Y(13))+HHR(Y(14))+HHR(Y(15))
382 C(13)=.5*HHR(Y(13))+HHR(Y(14))+HHR(Y(15))
383 C(14)=.5*HHR(Y(14))+HHR(Y(15))
384 C(15)=.5*HHR(Y(15))
395 NEXT J44
411 PROD=0
412 FOR J44=1 TO 15
413 FOR J45=J44+1 TO 15
414 PROD=PROD    -HS(Y(J44),Y(J45))*ABS(  C(J44)-C(J45)  )
415 NEXT J45
416 NEXT J44
422 P=PROD
1111 IF P<=M THEN 1670
1452 M=P
1453 FOR KLX=1 TO 15
1454 CC(KLX)=C(KLX)
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-3195 THEN 1999
1901 PRINT A(1),A(2),A(3),A(4),A(5)
1902 PRINT A(6),A(7),A(8),A(9),A(10)
1903 PRINT A(11),A(12),A(13),A(14),A(15)
1905   PRINT CC(1),CC(2),CC(3),CC(4),CC(5)
1906   PRINT CC(6),CC(7),CC(8),CC(9),CC(10)
1907   PRINT CC(11),CC(12),CC(13),CC(14),CC(15)
1919 PRINT M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter.  The complete output through JJJJ=-31833 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

1   10   13   6   7
14   12   3   9   15
11   4   2   5   8
47   32.5   25.5   21.5   18.5
15.5   10.5   3.5   37.5   31.5
27.5   21.5   13.5   7.5   3
-3183   -31985

1   10   14   6   5
7   12   3   9   15
11   4   2   13   8
47   32.5   25.5   21.5   16.5
11.5   8.5   3.5   37.5   31.5
27.5   21.5   16.5   10.5   3
-3194   -31932

1   10   13   6   7
14   12   3   9   15
11   4   2   5   8
47   32.5   25.5   21.5   18.5
15.5   10.5   3.5   37.5   31.5
27.5   21.5   13.5   7.5   3
-3183   -31918

1   10   14   6   5
7   12   3   9   15
11   4   2   13   8
47   32.5   25.5   21.5   16.5
11.5   8.5   3.5   37.5   31.5
27.5   21.5   16.5   10.5   3
-3194   -31886

1   10   14   6   5
7   12   3   9   15
11   4   2   13   8
47   32.5   25.5   21.5   16.5
11.5   8.5   3.5   37.5   31.5
27.5   21.5   16.5   10.5   3
-3194   -31871

1   10   13   6   7
14   12   3   9   15
11   4   2   5   8
47   32.5   25.5   21.5   18.5
15.5   10.5   3.5   37.5   31.5
27.5   21.5   13.5   7.5   3
-3183   -31833

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM, and the IBM basica/D interpreter, version GW BASIC 3.11,  the wall-clock time through JJJJ= -31833 was four minutes.

References

[1] Andre R. S. Amaral (2006), On the Exact Solution of a Facility Layout Problem.  European Journal of Operational Research 173 (2006), pp. 508-518.

[2] Andre R. S. Amaral (2008), An Exact Approach to the One-Dimensional Facility Layout Problem.  Operations Research, Vol. 56, No. 4 (July-August, 2008), pp. 1026-1033.

[3] Andre R. S. Amaral (2012), The Corridor Allocation Problem.  Computers and Operations Research 39 (2012), pp. 3325-3330.

[4] Miguel F. Anjos, Anthony Vannelli, Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes.  INFORMS Journal on Computing, Vol. 20, No. 4, Fall 2008, pp. 611-617.

[5] David L. Applegate, Robert E. Bixby, Vasek Chvatal, William J. Cook, The Traveling Salesman Problem: A Computational Study.  Princeton and Oxford: Princeton University Press, 2006.

[6] L. L. Barachet (1957), Graphic Solution of the Travelling Salesman Problem.  Operations Research, Vol. 5, pp. 841-845.

[7] T. Y. Chen, H. C. Chen (2009), Mixed-Discrete Structural Optimization Using a Rank-Niche Evolution Strategy, Engineering Optimization, 41:1, 39-58.

[8] Leon Cooper, U. N. Bhat, L. J. LeBlanc, Introduction to Operations Researach Models.  W. B. Saunders Company, 1977.

[9] George B. Dantzig,  Discrete-Variable Extremum Problems.  Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.

[10] G. Dantzig, R. Fulkerson, S. Johnson, Solution of a Large-Scale Traveling-Salesman Problem. 
Operations Research, Vol. 2, No. 4 (Nov., 1954), pp. 393-410.

[11] Zvi Drezner (1980), DISCON: A New Method for the Layout Problem.  Operations Research, Vol. 28, No. 6 (Nov. - Dec., 1980), pp. 1375-1384.

[12] W. J. Fabrycky, P. M. Ghare, P. E. Torgersen, Applied Operations Research and Management Science.  Englewood Cliffs, N. J. 07362: Prentice-Hall, Inc., 1984.

[13] Billy E. Gillett, Introduction to Operations Research: A Computer-Oriented Algorithmic Approach.  McGraw-Hill, Inc., 1976.

[14] Diptesh Ghosh, Ravi Kothari, Population Heuristics for the Corridor Allocation Problem, W.P. No. 2012-09-02, September 2012.  Retrieved on September 14 2012 from Google search.

[15] Martin Grotschel, Olaf Holland (1991), Solution of Large-Scale Symmetric Travelling Salesman Problems, Mathematical Programming 51, pp. 141-202.

[16] Sunderesh S. Heragu, Andrew Kusiak (1988), Machine Layout Problem in Flexible Manufacturing Systems.  Operations Research, Vol. 36, No. 2, Operations Research in Manufacturing (Mar. - Apr., 1988), pp. 258-268.

[17] S. S. Heragu, A. Kusiak (1991), Efficient Models for the Facility Layout Problem.  European Journal of Operational Research, Vol. 53 (1991), pp. 1-13.

[18] S. S. Heragu, Facilities Design, Third Edition.  Boca Raton, Florida: CRC Press, 2008.

[19] Michael Junger, Thomas M. Liebling, Dennis Naddef, George L. Nemhauser, William R. Pulleybank, Gerhart Reinelt, Giovanni Rinaldi, Lawrence A. Wolsey--Editors, 50 Years of Integer Programming 1958-2008.  Berlin: Springer, 2010.

[20] R. L. Karg, G. L. Thompson (1964), A Heuristic Approach to Solving Travelling Salesman Problems.  Management Science, Vol. 10, Number 2, pp. 225-248.

[21] K. Ravi Kumar, George C. Hadjinicola, Ting-li Lin (1995), A Heuristic Procedure for the Single-Row Facility Layout Problem.  European Journal of Operational Research 87 (1995) 65-73.

[22]  A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems.  Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.

[23] E. L. Lawler, M. D. Bell, A Method for Solving Discrete Optimization Problems.  Operations Research, Vol. 14, No. 6 (Nov.-Dec., 1966), pp. 1098-1112.

[24] Robert F. Love, Jsun Y. Wong (1976), On Solving a One-Dimensional Space Allocation Problem with Integer Programming.  INFOR, Vol. 14, No. 2, June 1976, pp. 139-143.
 
[25] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems.  Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.     

[26] Ken McAloon, Carol Tretkoff, Optimization and Computational Logic.  John Wiley and Sons, Inc., 1996.

[27] 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.

[28] Katta G. Murty, Operations Research: Deterministic Optimization Models.  Prentice Hall, Upper Saddle River, New Jersey 07458, 1994.

[29] C. E. Nugent, T. E. Vollmann, J. Ruml (1968), An Experimental Comparison of Techniques for the Assignment of Facilities to Locations, Operations Research 16 (1968), pp. 150-173.

[30] Christopher J. Picone, Wilbert E. Wilhelm (1986), "A Perturbation Scheme To Improve Hillier's Solution to the Facilities Layout Problem": a Clarification.  Management Science Vol. 32, No. 2, February 1986, pp. 253-254. 

[31] Cliff T. Ragsdale, Spreadsheet Modeling and Decision Analysis, Fifth Edition.  South-Westen, Cengage Learning, 2008.

[32] H. H. Rosenbrock (1960), An Automatic Method for Finding the Greatest or Least Value of a Function, Computer Journal Vol. 3, pp. 175-184.

[33] Donald M. Simmons (1969), One-Dimensional Space Allocation: An Ordering Algorithm.     Operations Research, Vol. 17, No. 5 (Sep. - Oct., 1969), pp. 812-826.

[34] Wayne L. Winston, Munirpallam Venkataramanan, Introduction to Mathematical Programming: Operations Research, Volume One, Fourth Edition.  Pacific Grove, CA 93950: Brooks/Cole--Thomson Learning, 2003.

[35] Wayne L. Winston, S. Christian Albright, Practical Management Science, Third Edition.  Thomson/South-Western, 2007.

[36] Jsun Yui Wong (2009, July 18).  An Integer Programming Computer Program Applied to One-Dimensional Space Allocation.  Retrieved from http://wongsllllblog.blogspot.com/2009/07/

[37] Jsun Yui Wong (2009, November 2).  A Computer Program for Relative Location of Circular Facilities.  Retrieved on September 3, 2012, from http://wongsllllblog.blogspot.ca/2009/11/

[38] Jsun Yui Wong (2009, December 18).  A Heuristic Nonlinear Integer Solver Applied to a Problem of Assignment of Facilities to Locations.  Retrieved from http://wongsnewnewblog.blogspot.ca/2009/12/

[39] Jsun Yui Wong (2011, October 27).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a New Formulation of a Twelve-City Traveling Salesman Problem, Sixth Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/10/27/

[40] Ji-Hui Zhang, Xin-He Xu (1999), An Efficient Evoutionary Programming Algorithm.  Computers and Operations Research 26, 645-663.

A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Corridor Allocation Problem with Fifteen Facilities, Second Edition

Jsun Yui Wong

The following computer program seeks to solve the n=15 corridor allocation problem on page 3328 of Amaral [3] and on page 9 of Ghosh and Kothari [14].  The lengths of line 27 through line 30 and the flows of line 61 through line 76 are from Amaral [2, p. 1031].

Because of line 233 through line 240, the following computer program is shorter than the computer program of the preceding paper.

0 REM DEFDBL A-Z
1 DEFINT I,J,K,X,A
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J44(2002),J(99),AA(99),HR(32),HHR(32),Y(33),C(33),CC(33)
3 DIM HS(49,49)
4 DIM PE(49,49)
5 DIM SD(49,49)
27   HR(1)=20:HR(2)=3:HR(3)=9:HR(4)=3:HR(5)=7
28   REM   HR(6)=4:HR(7)=6:HR(8)=8:HR(9)=9
29   HR(6)=3:HR(7)=7:HR(8)=5:HR(9)=9:HR(10)=6
30   HR(11)=5:HR(12)=3:HR(13)=9:HR(14)=3:HR(15)=7
31 FOR IL=1 TO 15
32 FOR JL=1 TO 15
33 READ HS(IL,JL)
34 NEXT JL
35 NEXT IL
61 DATA 999,10,0,5,1,0,1,2,2,2,2,0,4,0,0
62 DATA 10,999,1,3,2,2,2,3,2,0,2,0,10,5,0
63 DATA 0,1,999,10,2,0,2,5,4,5,2,2,5,5,5
64 DATA 5,3,10,999,1,1,5,0,0,2,1,0,2,5,0
66 DATA 1,2,2,1,999,3,5,5,5,1,0,3,0,5,5
67 DATA 0,2,0,1,3,999,2,2,1,5,0,0,2,5,10
68 DATA 1,2,2,5,5,2,999,6,0,1,5,5,5,1,0
69 DATA 2,3,5,0,5,2,6,999,5,2,10,0,5,0,0
70 DATA 2,2,4,0,5,1,0,5,999,0,10,5,10,0,2
71 DATA 2,0,5,2,1,5,1,2,0,999,0,4,0,0,5
72 DATA 2,2,2,1,0,0,5,10,10,0,999,5,0,5,0
73 DATA 0,0,2,0,3,0,5,0,5,4,3,999,3,3,0
74 DATA 4,10,5,2,0,2,5,5,10,0,0,3,999,10,2
75 DATA 0,5,5,5,5,5,1,0,0,0,5,3,10,999,4
76 DATA 0,0,5,0,5,10,0,0,2,5,0,0,2,4,999
78 FOR JJJJ=-32000 TO 32000
79 RANDOMIZE JJJJ
80 M=-1D+37
81 FOR J44=1 TO 15
83 A(J44)=J44
84 NEXT J44
126 REM IMAR=10+FIX(RND*1000)
128 FOR I=1 TO 500
129 FOR KKQQ=1 TO 15
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 III=1+FIX(RND*15)
134 JJJ=1+FIX(RND*15)
221    X(III)=A(JJJ)
223    X(JJJ)=A(III)
231 FOR J44=1 TO 15
233 FOR J45=1 TO 15
234 IF X(J44)=J45 THEN HHR(J45)=HR(J45)  ELSE GOTO 240
237 Y(J45)=J44
240 NEXT J45
331 C(1)=.5*HHR(Y(1))+HHR(Y(2))+HHR(Y(3))+HHR(Y(4))+HHR(Y(5))+HHR(Y(6) )+HHR(Y(7)   )+HHR(Y(8)  )
333 C(2)=.5*HHR(Y(2))+HHR(Y(3))+HHR(Y(4))+HHR(Y(5))+HHR(Y(6))+HHR(Y(7) )+HHR(Y(8)   )
335 C(3)=.5*HHR(Y(3))+HHR(Y(4))+HHR(Y(5))+HHR(Y(6))+HHR(Y(7))+HHR(Y(8) )
361 C(4)=.5*HHR(Y(4))+HHR(Y(5))+HHR(Y(6))+HHR(Y(7))+HHR(Y(8))
364 C(5)=.5*HHR(Y(5))+HHR(Y(6))+HHR(Y(7))+HHR(Y(8))
368 C(6)=.5*HHR(Y(6))+HHR(Y(7))+HHR(Y(8))
373 C(7)=.5*HHR(Y(7))+HHR(Y(8))
377 C(8)=.5*HHR(Y(8))
378 C(9)=.5*HHR(Y(9))+HHR(Y(10))+HHR(Y(11))+HHR(Y(12))+HHR(Y(13))+HHR(Y(14) )+HHR(Y(15)   )
379 C(10)=.5*HHR(Y(10))+HHR(Y(11))+HHR(Y(12))+HHR(Y(13))+HHR(Y(14))+HHR(Y(15) )
380 C(11)=.5*HHR(Y(11))+HHR(Y(12))+HHR(Y(13))+HHR(Y(14))+HHR(Y(15))
381 C(12)=.5*HHR(Y(12))+HHR(Y(13))+HHR(Y(14))+HHR(Y(15))
382 C(13)=.5*HHR(Y(13))+HHR(Y(14))+HHR(Y(15))
383 C(14)=.5*HHR(Y(14))+HHR(Y(15))
384 C(15)=.5*HHR(Y(15))
395 NEXT J44
411 PROD=0
412 FOR J44=1 TO 15
413 FOR J45=J44+1 TO 15
414 PROD=PROD    -HS(Y(J44),Y(J45))*ABS(  C(J44)-C(J45)  )
415 NEXT J45
416 NEXT J44
422 P=PROD
1111 IF P<=M THEN 1670
1452 M=P
1453 FOR KLX=1 TO 15
1454 CC(KLX)=C(KLX)
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-3195 THEN 1999
1901 PRINT A(1),A(2),A(3),A(4),A(5)
1902 PRINT A(6),A(7),A(8),A(9),A(10)
1903 PRINT A(11),A(12),A(13),A(14),A(15)
1905   PRINT CC(1),CC(2),CC(3),CC(4),CC(5)
1906   PRINT CC(6),CC(7),CC(8),CC(9),CC(10)
1907   PRINT CC(11),CC(12),CC(13),CC(14),CC(15)
1919 PRINT M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter.  The complete output through JJJJ=-31833 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

1   10   13   6   7
14   12   3   9   15
11   4   2   5   8
47   32.5   25.5   21.5   18.5
15.5   10.5   3.5   37.5   31.5
27.5   21.5   13.5   7.5   3
-3183   -31985

1   10   14   6   5
7   12   3   9   15
11   4   2   13   8
47   32.5   25.5   21.5   16.5
11.5   8.5   3.5   37.5   31.5
27.5   21.5   16.5   10.5   3
-3194   -31932

1   10   13   6   7
14   12   3   9   15
11   4   2   5   8
47   32.5   25.5   21.5   18.5
15.5   10.5   3.5   37.5   31.5
27.5   21.5   13.5   7.5   3
-3183   -31918

1   10   14   6   5
7   12   3   9   15
11   4   2   13   8
47   32.5   25.5   21.5   16.5
11.5   8.5   3.5   37.5   31.5
27.5   21.5   16.5   10.5   3
-3194   -31886

1   10   14   6   5
7   12   3   9   15
11   4   2   13   8
47   32.5   25.5   21.5   16.5
11.5   8.5   3.5   37.5   31.5
27.5   21.5   16.5   10.5   3
-3194   -31871

1   10   13   6   7
14   12   3   9   15
11   4   2   5   8
47   32.5   25.5   21.5   18.5
15.5   10.5   3.5   37.5   31.5
27.5   21.5   13.5   7.5   3
-3183   -31833

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM, and the IBM basica/D interpreter, version GW BASIC 3.11,  the wall-clock time through JJJJ= -31833 was four minutes.

References

[1] Andre R. S. Amaral (2006), On the Exact Solution of a Facility Layout Problem.  European Journal of Operational Research 173 (2006), pp. 508-518.

[2] Andre R. S. Amaral (2008), An Exact Approach to the One-Dimensional Facility Layout Problem.  Operations Research, Vol. 56, No. 4 (July-August, 2008), pp. 1026-1033.

[3] Andre R. S. Amaral (2012), The Corridor Allocation Problem.  Computers and Operations Research 39 (2012), pp. 3325-3330.

[4] Miguel F. Anjos, Anthony Vannelli, Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes.  INFORMS Journal on Computing, Vol. 20, No. 4, Fall 2008, pp. 611-617.

[5] David L. Applegate, Robert E. Bixby, Vasek Chvatal, William J. Cook, The Traveling Salesman Problem: A Computational Study.  Princeton and Oxford: Princeton University Press, 2006.

[6] L. L. Barachet (1957), Graphic Solution of the Travelling Salesman Problem.  Operations Research, Vol. 5, pp. 841-845.

[7] T. Y. Chen, H. C. Chen (2009), Mixed-Discrete Structural Optimization Using a Rank-Niche Evolution Strategy, Engineering Optimization, 41:1, 39-58.

[8] Leon Cooper, U. N. Bhat, L. J. LeBlanc, Introduction to Operations Researach Models.  W. B. Saunders Company, 1977.

[9] George B. Dantzig,  Discrete-Variable Extremum Problems.  Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.

[10] G. Dantzig, R. Fulkerson, S. Johnson, Solution of a Large-Scale Traveling-Salesman Problem. 
Operations Research, Vol. 2, No. 4 (Nov., 1954), pp. 393-410.

[11] Zvi Drezner (1980), DISCON: A New Method for the Layout Problem.  Operations Research, Vol. 28, No. 6 (Nov. - Dec., 1980), pp. 1375-1384.

[12] W. J. Fabrycky, P. M. Ghare, P. E. Torgersen, Applied Operations Research and Management Science.  Englewood Cliffs, N. J. 07362: Prentice-Hall, Inc., 1984.

[13] Billy E. Gillett, Introduction to Operations Research: A Computer-Oriented Algorithmic Approach.  McGraw-Hill, Inc., 1976.

[14] Diptesh Ghosh, Ravi Kothari, Population Heuristics for the Corridor Allocation Problem, W.P. No. 2012-09-02, September 2012.  Retrieved on September 14 2012 from Google search.

[15] Martin Grotschel, Olaf Holland (1991), Solution of Large-Scale Symmetric Travelling Salesman Problems, Mathematical Programming 51, pp. 141-202.

[16] Sunderesh S. Heragu, Andrew Kusiak (1988), Machine Layout Problem in Flexible Manufacturing Systems.  Operations Research, Vol. 36, No. 2, Operations Research in Manufacturing (Mar. - Apr., 1988), pp. 258-268.

[17] S. S. Heragu, A. Kusiak (1991), Efficient Models for the Facility Layout Problem.  European Journal of Operational Research, Vol. 53 (1991), pp. 1-13.

[18] S. S. Heragu, Facilities Design, Third Edition.  Boca Raton, Florida: CRC Press, 2008.

[19] Michael Junger, Thomas M. Liebling, Dennis Naddef, George L. Nemhauser, William R. Pulleybank, Gerhart Reinelt, Giovanni Rinaldi, Lawrence A. Wolsey--Editors, 50 Years of Integer Programming 1958-2008.  Berlin: Springer, 2010.

[20] R. L. Karg, G. L. Thompson (1964), A Heuristic Approach to Solving Travelling Salesman Problems.  Management Science, Vol. 10, Number 2, pp. 225-248.

[21] K. Ravi Kumar, George C. Hadjinicola, Ting-li Lin (1995), A Heuristic Procedure for the Single-Row Facility Layout Problem.  European Journal of Operational Research 87 (1995) 65-73.

[22]  A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems.  Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.

[23] E. L. Lawler, M. D. Bell, A Method for Solving Discrete Optimization Problems.  Operations Research, Vol. 14, No. 6 (Nov.-Dec., 1966), pp. 1098-1112.

[24] Robert F. Love, Jsun Y. Wong (1976), On Solving a One-Dimensional Space Allocation Problem with Integer Programming.  INFOR, Vol. 14, No. 2, June 1976, pp. 139-143.
 
[25] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems.  Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.     

[26] Ken McAloon, Carol Tretkoff, Optimization and Computational Logic.  John Wiley and Sons, Inc., 1996.

[27] 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.

[28] Katta G. Murty, Operations Research: Deterministic Optimization Models.  Prentice Hall, Upper Saddle River, New Jersey 07458, 1994.

[29] C. E. Nugent, T. E. Vollmann, J. Ruml (1968), An Experimental Comparison of Techniques for the Assignment of Facilities to Locations," Operations Research 16 (1968), pp. 150-173.

[30] Christopher J. Picone, Wilbert E. Wilhelm (1986), "A Perturbation Scheme To Improve Hillier's Solution to the Facilities Layout Problem": a Clarification.  Management Science Vol. 32, No. 2, February 1986, pp. 253-254. 

[31] Cliff T. Ragsdale, Spreadsheet Modeling and Decision Analysis, Fifth Edition.  South-Westen, Cengage Learning, 2008.

[32] H. H. Rosenbrock (1960), An Automatic Method for Finding the Greatest or Least Value of a Function, Computer Journal Vol. 3, pp. 175-184.

[33] Donald M. Simmons (1969), One-Dimensional Space Allocation: An Ordering Algorithm.     Operations Research, Vol. 17, No. 5 (Sep. - Oct., 1969), pp. 812-826.

[34] Wayne L. Winston, Munirpallam Venkataramanan, Introduction to Mathematical Programming: Operations Research, Volume One, Fourth Edition.  Pacific Grove, CA 93950: Brooks/Cole--Thomson Learning, 2003.

[35] Wayne L. Winston, S. Christian Albright, Practical Management Science, Third Edition.  Thomson/South-Western, 2007.

[36] Jsun Yui Wong (2009, July 18).  An Integer Programming Computer Program Applied to One-Dimensional Space Allocation.  Retrieved from http://wongsllllblog.blogspot.com/2009/07/

[37] Jsun Yui Wong (2009, November 2).  A Computer Program for Relative Location of Circular Facilities.  Retrieved on September 3, 2012, from http://wongsllllblog.blogspot.ca/2009/11/

[38] Jsun Yui Wong (2009, December 18).  A Heuristic Nonlinear Integer Solver Applied to a Problem of Assignment of Facilities to Locations.  Retrieved from http://wongsnewnewblog.blogspot.ca/2009/12/

[39] Jsun Yui Wong (2011, October 27).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a New Formulation of a Twelve-City Traveling Salesman Problem, Sixth Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/10/27/

[40] Ji-Hui Zhang, Xin-He Xu (1999), An Efficient Evolutionary Programming Algorithm.  Computers and Operations Research 26, 645-663.

A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Corridor Allocation Problem with Fifteen Facilities

Jsun Yui Wong

The following computer program seeks to solve the n=15 corridor allocation problem on page 3328 of Amaral [3] and on page 9 of Ghosh and Kothari [14]. The lengths of line 27 through line 30 and the flows of line 61 through line 76 are from Amaral [2, p. 1031].

0 REM DEFDBL A-Z

1 DEFINT I,J,K,X,A

2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J44(2002),J(99),AA(99),HR(32),HHR(32),Y(33),C(33),CC(33)

3 DIM HS(49,49)

4 DIM PE(49,49)

5 DIM SD(49,49)

27 HR(1)=20:HR(2)=3:HR(3)=9:HR(4)=3:HR(5)=7

28 REM HR(6)=4:HR(7)=6:HR(8)=8:HR(9)=9

29 HR(6)=3:HR(7)=7:HR(8)=5:HR(9)=9:HR(10)=6

30 HR(11)=5:HR(12)=3:HR(13)=9:HR(14)=3:HR(15)=7

31 FOR IL=1 TO 15

32 FOR JL=1 TO 15

33 READ HS(IL,JL)

34 NEXT JL

35 NEXT IL

61 DATA 999,10,0,5,1,0,1,2,2,2,2,0,4,0,0

62 DATA 10,999,1,3,2,2,2,3,2,0,2,0,10,5,0

63 DATA 0,1,999,10,2,0,2,5,4,5,2,2,5,5,5

64 DATA 5,3,10,999,1,1,5,0,0,2,1,0,2,5,0

66 DATA 1,2,2,1,999,3,5,5,5,1,0,3,0,5,5

67 DATA 0,2,0,1,3,999,2,2,1,5,0,0,2,5,10

68 DATA 1,2,2,5,5,2,999,6,0,1,5,5,5,1,0

69 DATA 2,3,5,0,5,2,6,999,5,2,10,0,5,0,0

70 DATA 2,2,4,0,5,1,0,5,999,0,10,5,10,0,2

71 DATA 2,0,5,2,1,5,1,2,0,999,0,4,0,0,5

72 DATA 2,2,2,1,0,0,5,10,10,0,999,5,0,5,0

73 DATA 0,0,2,0,3,0,5,0,5,4,3,999,3,3,0

74 DATA 4,10,5,2,0,2,5,5,10,0,0,3,999,10,2

75 DATA 0,5,5,5,5,5,1,0,0,0,5,3,10,999,4

76 DATA 0,0,5,0,5,10,0,0,2,5,0,0,2,4,999

78 FOR JJJJ=-32000 TO 32000

79 RANDOMIZE JJJJ

80 M=-1D+37

81 FOR J44=1 TO 15

83 A(J44)=J44

84 NEXT J44

126 REM IMAR=10+FIX(RND*1000)

128 FOR I=1 TO 500

129 FOR KKQQ=1 TO 15

130 X(KKQQ)=A(KKQQ)

131 NEXT KKQQ

133 III=1+FIX(RND*15)

134 JJJ=1+FIX(RND*15)

221 X(III)=A(JJJ)

223 X(JJJ)=A(III)

231 FOR J44=1 TO 15

234 IF X(J44)=1 THEN HHR(J44)=HR(J44) ELSE GOTO 244

237 Y(1)=J44

244 IF X(J44)=2 THEN HHR(J44)=HR(J44) ELSE GOTO 254

247 Y(2)=J44

254 IF X(J44)=3 THEN HHR(J44)=HR(J44) ELSE GOTO 257

255 Y(3)=J44

257 IF X(J44)=4 THEN HHR(J44)=HR(J44) ELSE GOTO 259

258 Y(4)=J44

259 IF X(J44)=5 THEN HHR(J44)=HR(J44) ELSE GOTO 277

260 Y(5)=J44

277 IF X(J44)=6 THEN HHR(J44)=HR(J44) ELSE GOTO 279

278 Y(6)=J44

279 IF X(J44)=7 THEN HHR(J44)=HR(J44) ELSE GOTO 285

280 Y(7)=J44

285 IF X(J44)=8 THEN HHR(J44)=HR(J44) ELSE GOTO 289

287 Y(8)=J44

289 IF X(J44)=9 THEN HHR(J44)=HR(J44) ELSE GOTO 301

293 Y(9)=J44

301 IF X(J44)=10 THEN HHR(J44)=HR(J44) ELSE GOTO 305

303 Y(10)=J44

305 IF X(J44)=11 THEN HHR(J44)=HR(J44) ELSE GOTO 309

307 Y(11)=J44

309 IF X(J44)=12 THEN HHR(J44)=HR(J44) ELSE GOTO 313

311 Y(12)=J44

313 IF X(J44)=13 THEN HHR(J44)=HR(J44) ELSE GOTO 317

315 Y(13)=J44

317 IF X(J44)=14 THEN HHR(J44)=HR(J44) ELSE GOTO 321

319 Y(14)=J44

321 IF X(J44)=15 THEN HHR(J44)=HR(J44) ELSE GOTO 331

323 Y(15)=J44

331 C(1)=.5*HHR(Y(1))+HHR(Y(2))+HHR(Y(3))+HHR(Y(4))+HHR(Y(5))+HHR(Y(6) )+HHR(Y(7) )+HHR(Y(8) )

333 C(2)=.5*HHR(Y(2))+HHR(Y(3))+HHR(Y(4))+HHR(Y(5))+HHR(Y(6))+HHR(Y(7) )+HHR(Y(8) )

335 C(3)=.5*HHR(Y(3))+HHR(Y(4))+HHR(Y(5))+HHR(Y(6))+HHR(Y(7))+HHR(Y(8) )

361 C(4)=.5*HHR(Y(4))+HHR(Y(5))+HHR(Y(6))+HHR(Y(7))+HHR(Y(8))

364 C(5)=.5*HHR(Y(5))+HHR(Y(6))+HHR(Y(7))+HHR(Y(8))

368 C(6)=.5*HHR(Y(6))+HHR(Y(7))+HHR(Y(8))

373 C(7)=.5*HHR(Y(7))+HHR(Y(8))

377 C(8)=.5*HHR(Y(8))

378 C(9)=.5*HHR(Y(9))+HHR(Y(10))+HHR(Y(11))+HHR(Y(12))+HHR(Y(13))+HHR(Y(14) )+HHR(Y(15) )

379 C(10)=.5*HHR(Y(10))+HHR(Y(11))+HHR(Y(12))+HHR(Y(13))+HHR(Y(14))+HHR(Y(15) )

380 C(11)=.5*HHR(Y(11))+HHR(Y(12))+HHR(Y(13))+HHR(Y(14))+HHR(Y(15))

381 C(12)=.5*HHR(Y(12))+HHR(Y(13))+HHR(Y(14))+HHR(Y(15))

382 C(13)=.5*HHR(Y(13))+HHR(Y(14))+HHR(Y(15))

383 C(14)=.5*HHR(Y(14))+HHR(Y(15))

384 C(15)=.5*HHR(Y(15))

395 NEXT J44

411 PROD=0

412 FOR J44=1 TO 15

413 FOR J45=J44+1 TO 15

414 PROD=PROD -HS(Y(J44),Y(J45))*ABS( C(J44)-C(J45) )

415 NEXT J45

416 NEXT J44

422 P=PROD

1111 IF P<=M THEN 1670

1452 M=P

1453 FOR KLX=1 TO 15

1454 CC(KLX)=C(KLX)

1455 A(KLX)=X(KLX)

1456 NEXT KLX

1557 GOTO 128

1670 NEXT I

1889 IF M<-3195 THEN 1999

1901 PRINT A(1),A(2),A(3),A(4),A(5)

1902 PRINT A(6),A(7),A(8),A(9),A(10)

1903 PRINT A(11),A(12),A(13),A(14),A(15)

1905 PRINT CC(1),CC(2),CC(3),CC(4),CC(5)

1906 PRINT CC(6),CC(7),CC(8),CC(9),CC(10)

1907 PRINT CC(11),CC(12),CC(13),CC(14),CC(15)

1919 PRINT M,JJJJ

1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter. The complete output through JJJJ=-31833 is shown below. What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

1 10 13 6 7

14 12 3 9 15

11 4 2 5 8

47 32.5 25.5 21.5 18.5

15.5 10.5 3.5 37.5 31.5

27.5 21.5 13.5 7.5 3

-3183 -31985

1 10 14 6 5

7 12 3 9 15

11 4 2 13 8

47 32.5 25.5 21.5 16.5

11.5 8.5 3.5 37.5 31.5

27.5 21.5 16.5 10.5 3

-3194 -31932

1 10 13 6 7

14 12 3 9 15

11 4 2 5 8

47 32.5 25.5 21.5 18.5

15.5 10.5 3.5 37.5 31.5

27.5 21.5 13.5 7.5 3

-3183 -31918

1 10 14 6 5

7 12 3 9 15

11 4 2 13 8

47 32.5 25.5 21.5 16.5

11.5 8.5 3.5 37.5 31.5

27.5 21.5 16.5 10.5 3

-3194 -31886

1 10 14 6 5

7 12 3 9 15

11 4 2 13 8

47 32.5 25.5 21.5 16.5

11.5 8.5 3.5 37.5 31.5

27.5 21.5 16.5 10.5 3

-3194 -31871

1 10 13 6 7

14 12 3 9 15

11 4 2 5 8

47 32.5 25.5 21.5 18.5

15.5 10.5 3.5 37.5 31.5

27.5 21.5 13.5 7.5 3

-3183 -31833

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM, and the IBM basica/D interpreter, version GW BASIC 3.11, the wall-clock time through JJJJ= -31833 was four minutes.

References

[1] Andre R. S. Amaral (2006), On the Exact Solution of a Facility Layout Problem. European Journal of Operational Research 173 (2006), pp. 508-518.

[2] Andre R. S. Amaral (2008), An Exact Approach to the One-Dimensional Facility Layout Problem. Operations Research, Vol. 56, No. 4 (July-August, 2008), pp. 1026-1033.

[3] Andre R. S. Amaral (2012), The Corridor Allocation Problem. Computers and Operations Research 39 (2012), pp. 3325-3330.

[4] Miguel F. Anjos, Anthony Vannelli, Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes. INFORMS Journal on Computing, Vol. 20, No. 4, Fall 2008, pp. 611-617.

[5] David L. Applegate, Robert E. Bixby, Vasek Chvatal, William J. Cook, The Traveling Salesman Problem: A Computational Study. Princeton and Oxford: Princeton University Press, 2006.

[6] L. L. Barachet (1957), Graphic Solution of the Travelling Salesman Problem. Operations Research, Vol. 5, pp. 841-845.

[7] T. Y. Chen, H. C. Chen (2009), Mixed-Discrete Structural Optimization Using a Rank-Niche Evolution Strategy, Engineering Optimization, 41:1, 39-58.

[8] Leon Cooper, U. N. Bhat, L. J. LeBlanc, Introduction to Operations Researach Models. W. B. Saunders Company, 1977.

[9] George B. Dantzig, Discrete-Variable Extremum Problems. Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.

[10] G. Dantzig, R. Fulkerson, S. Johnson, Solution of a Large-Scale Traveling-Salesman Problem. Operations Research, Vol. 2, No. 4 (Nov., 1954), pp. 393-410.

[11] Zvi Drezner (1980), DISCON: A New Method for the Layout Problem. Operations Research, Vol. 28, No. 6 (Nov. - Dec., 1980), pp. 1375-1384.

[12] W. J. Fabrycky, P. M. Ghare, P. E. Torgersen, Applied Operations Research and Management Science. Englewood Cliffs, N. J. 07362: Prentice-Hall, Inc., 1984.

[13] Billy E. Gillett, Introduction to Operations Research: A Computer-Oriented Algorithmic Approach. McGraw-Hill, Inc., 1976.

[14] Diptesh Ghosh, Ravi Kothari, Population Heuristics for the Corridor Allocation Problem, W.P. No. 2012-09-02, September 2012. Retrieved on September 14 2012 from Google search.

[15] Martin Grotschel, Olaf Holland (1991), Solution of Large-Scale Symmetric Travelling Salesman Problems, Mathematical Programming 51, pp. 141-202.

[16] Sunderesh S. Heragu, Andrew Kusiak (1988), Machine Layout Problem in Flexible Manufacturing Systems. Operations Research, Vol. 36, No. 2, Operations Research in Manufacturing (Mar. - Apr., 1988), pp. 258-268.

[17] S. S. Heragu, A. Kusiak (1991), Efficient Models for the Facility Layout Problem. European Journal of Operational Research, Vol. 53 (1991), pp. 1-13.

[18] S. S. Heragu, Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.

[19] Michael Junger, Thomas M. Liebling, Dennis Naddef, George L. Nemhauser, William R. Pulleybank, Gerhart Reinelt, Giovanni Rinaldi, Lawrence A. Wolsey--Editors, 50 Years of Integer Programming 1958-2008. Berlin: Springer, 2010.

[20] R. L. Karg, G. L. Thompson (1964), A Heuristic Approach to Solving Travelling Salesman Problems. Management Science, Vol. 10, Number 2, pp. 225-248.

[21] K. Ravi Kumar, George C. Hadjinicola, Ting-li Lin (1995), A Heuristic Procedure for the Single-Row Facility Layout Problem. European Journal of Operational Research 87 (1995) 65-73.

[22] A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems. Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.

[23] E. L. Lawler, M. D. Bell, A Method for Solving Discrete Optimization Problems. Operations Research, Vol. 14, No. 6 (Nov.-Dec., 1966), pp. 1098-1112.

[24] Robert F. Love, Jsun Y. Wong (1976), On Solving a One-Dimensional Space Allocation Problem with Integer Programming. INFOR, Vol. 14, No. 2, June 1976, pp. 139-143.

[25] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems. Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.

[26] Ken McAloon, Carol Tretkoff, Optimization and Computational Logic. John Wiley and Sons, Inc., 1996.

[27] 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.

[28] Katta G. Murty, Operations Research: Deterministic Optimization Models. Prentice Hall, Upper Saddle River, New Jersey 07458, 1994.

[29] C. E. Nugent, T. E. Vollmann, J. Ruml (1968), An Experimental Comparison of Techniques for the Assignment of Facilities to Locations. Operations Research 16 (1968), pp. 150-173.

[30] Christopher J. Picone, Wilbert E. Wilhelm (1986), "A Perturbation Scheme To Improve Hillier's Solution to the Facilities Layout Problem": a Clarification. Management Science Vol. 32, No. 2, February 1986, pp. 253-254.

[31] Cliff T. Ragsdale, Spreadsheet Modeling and Decision Analysis, Fifth Edition. South-Westen, Cengage Learning, 2008.

[32] H. H. Rosenbrock (1960), An Automatic Method for Finding the Greatest or Least Value of a Function, Computer Journal Vol. 3, pp. 175-184.

[33] Donald M. Simmons (1969), One-Dimensional Space Allocation: An Ordering Algorithm. Operations Research, Vol. 17, No. 5 (Sep. - Oct., 1969), pp. 812-826.

[34] Wayne L. Winston, Munirpallam Venkataramanan, Introduction to Mathematical Programming: Operations Research, Volume One, Fourth Edition. Pacific Grove, CA 93950: Brooks/Cole--Thomson Learning, 2003.

[35] Wayne L. Winston, S. Christian Albright, Practical Management Science, Third Edition. Thomson/South-Western, 2007.

[36] Jsun Yui Wong (2009, July 18). An Integer Programming Computer Program Applied to One-Dimensional Space Allocation. Retrieved from http://wongsllllblog.blogspot.com/2009/07/

[37] Jsun Yui Wong (2009, November 2). A Computer Program for Relative Location of Circular Facilities. Retrieved on September 3, 2012, from http://wongsllllblog.blogspot.ca/2009/11/

[38] Jsun Yui Wong (2009, December 18). A Heuristic Nonlinear Integer Solver Applied to a Problem of Assignment of Facilities to Locations. Retrieved from http://wongsnewnewblog.blogspot.ca/2009/12/

[39] Jsun Yui Wong (2011, October 27). A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a New Formulation of a Twelve-City Traveling Salesman Problem, Sixth Edition. Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/10/27/

[40] Ji-Hui Zhang, Xin-He Xu (1999), An Efficient Evolutionary Programming Algorithm. Computers and Operations Research 26, 645-663.

　

　

A Computer Program for Relative Location of Circular Facilities, Sixth Edition

Jsun Yui Wong

Based on the computer program of the first edition [36], the following computer program seeks to solve the same example of locating five circular facilities and is an illustration of solving the nonlinear programming formulation on page 1375 and page 1376 of Drezner [11].

While line 252 of the preceding paper is 252 X(IJL)=A(IJL)+ FIX(RND*5) -FIX(RND*5), here line 251 is 251 X(IJL)=A(IJL)+ FIX(RND*2)*((RND)^(RND*5))*A(IJL) -FIX(RND*2)* ((RND)^(RND*5)) *A(IJL).

0 DEFSNG A-Z
1 DEFINT I,J,K,X,A
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J44(2002),J(99),AA(99),HR(32),HHR(32),C(22),CC(22),Y(22),A
3 REM    DIM HS(49,49)
4 DIM PE(49,49)
5 DIM SD(49,49)
6 DIM HS(49)
21 HR(1)=252.312
22 HR(2)=308.974
23 HR(3)=264.353
24 HR(4)=275.426
25 HR(5)=308.974
26 HR(6)=264.353
27 HR(7)=275.426
28 HR(8)=321.015
29 HR(9)=332.088
30 HR(10)=287.467
78 FOR JJJJ=-32000 TO 32000
79 RANDOMIZE JJJJ
80 M=-1D+37
81 FOR J44=1 TO 10
83 A(J44)=RND*1000
84 NEXT J44
126 REM IMAR=10+FIX(RND*1000)
128 FOR I=1 TO 500
129 FOR KKQQ=1 TO 10
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
132 IF RND<.5 THEN 133 ELSE 227
133 III=1+FIX(RND*10)
134 JJJ=1+FIX(RND*10)
221 X(III)=A(JJJ)
223 X(JJJ)=A(III)
224 GOTO 291
227 IJL=1+FIX(RND*10)
251 X(IJL)=A(IJL)+ FIX(RND*2)*((RND)^(RND*5))*A(IJL) -FIX(RND*2)* ((RND)^(RND*5)) *A(IJL)
252 REM X(IJL)=A(IJL)+ FIX(RND*5) -FIX(RND*5)
291 HS(1)=((X(1)-X(2))^2+ (X(6)-X(7))^2  )^.5
292 HS(2)=((X(1)-X(3))^2+ (X(6)-X(8))^2  )^.5
293 HS(3)=((X(1)-X(4))^2+ (X(6)-X(9))^2  )^.5
294 HS(4)=((X(1)-X(5))^2+ (X(6)-X(10))^2  )^.5
295 HS(5)=((X(2)-X(3))^2+ (X(7)-X(8))^2  )^.5
296 HS(6)=((X(2)-X(4))^2+ (X(7)-X(9))^2  )^.5
297 HS(7)=((X(2)-X(5))^2+ (X(7)-X(10))^2  )^.5
298 HS(8)=((X(3)-X(4))^2+ (X(8)-X(9))^2  )^.5
299 HS(9)=((X(3)-X(5))^2+ (X(8)-X(10))^2  )^.5
300 HS(10)=((X(4)-X(5))^2+ (X(9)-X(10))^2  )^.5
551 IF HS(1)<HR(1) THEN HS(1)=999999!
552 IF HS(2)<HR(2) THEN HS(2)=999999!
553 IF HS(3)<HR(3) THEN HS(3)=999999!
554 IF HS(4)<HR(4) THEN HS(4)=999999!
555 IF HS(5)<HR(5) THEN HS(5)=999999!
556 IF HS(6)<HR(6) THEN HS(6)=999999!
557 IF HS(7)<HR(7) THEN HS(7)=999999!
558 IF HS(8)<HR(8) THEN HS(8)=999999!
559 IF HS(9)<HR(9) THEN HS(9)=999999!
560 IF HS(10)<HR(10) THEN HS(10)=999999!
1621 PR1=-10*HS(1)-15*HS(2)-20*HS(3)-.01*HS(4)-30*HS(5)-35*HS(6)-10*HS(7)
1623 PR2=-10*HS(8)-20*HS(9)-15*HS(10)
1655 P=PR1+PR2
1656 IF P<=M THEN 1670
1657 FOR KLX=1 TO 10
1658 A(KLX)=X(KLX)
1659 NEXT KLX
1661 M=P
1666 GOTO   128
1670 NEXT I
1889   IF M<-53334! THEN 1999
1901 PRINT A(1),A(2),A(3),A(4),A(5)
1902 PRINT A(6),A(7),A(8),A(9),A(10)
1903  REM PRINT CC(1),CC(2),CC(3),CC(4),CC(5)
1904  REM   PRINT CC(6),CC(7),CC(8),CC(9),CC(10),CC(11)
1919 PRINT M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter.  The complete output through JJJJ=-5576 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

56   160   459   320   608
492   259   178   470   476
-53276.39   -30736

216   400   380   149   51
847   674   365   591   316
-53265.87   -28281

199   453   607   291   358
299   339   608   548   828
-53278.79   -5576

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM, and the IBM basica/D interpreter, version GW BASIC 3.11,  the wall-clock time through JJJJ= -5576 was one hour and forty minutes.

References

[1] Andre R. S. Amaral (2006), On the Exact Solution of a Facility Layout Problem.  European Journal of Operational Research 173 (2006), pp. 508-518.

[2] Andre R. S. Amaral (2008), An Exact Approach to the One-Dimensional Facility Layout Problem.  Operations Research, Vol. 56, No. 4 (July-August, 2008), pp. 1026-1033.

[3] Andre R. S. Amaral (2012), The Corridor Allocation Problem.  Computers and Operations Research 39 (2012), pp. 3325-3330.

[4] Miguel F. Anjos, Anthony Vannelli, Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes.  INFORMS Journal on Computing, Vol. 20, No. 4, Fall 2008, pp. 611-617.

[5] David L. Applegate, Robert E. Bixby, Vasek Chvatal, William J. Cook, The Traveling Salesman Problem: A Computational Study.  Princeton and Oxford: Princeton University Press, 2006.

[6] L. L. Barachet (1957), Graphic Solution of the Travelling Salesman Problem.  Operations Research, Vol. 5, pp. 841-845.

[7] T. Y. Chen, H. C. Chen (2009), Mixed-Discrete Structural Optimization Using a Rank-Niche Evolution Strategy, Engineering Optimization, 41:1, 39-58.

[8] Leon Cooper, U. N. Bhat, L. J. LeBlanc, Introduction to Operations Researach Models.  W. B. Saunders Company, 1977.

[9] George B. Dantzig,  Discrete-Variable Extremum Problems.  Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.

[10] G. Dantzig, R. Fulkerson, S. Johnson, Solution of a Large-Scale Traveling-Salesman Problem. 
Operations Research, Vol. 2, No. 4 (Nov., 1954), pp. 393-410.

[11] Zvi Drezner (1980), DISCON: A New Method for the Layout Problem.  Operations Research, Vol. 28, No. 6 (Nov. - Dec., 1980), pp. 1375-1384.

[12] W. J. Fabrycky, P. M. Ghare, P. E. Torgersen, Applied Operations Research and Management Science.  Englewood Cliffs, N. J. 07362: Prentice-Hall, Inc., 1984.

[13] Billy E. Gillett, Introduction to Operations Research: A Computer-Oriented Algorithmic Approach.  McGraw-Hill, Inc., 1976.

[14] Martin Grotschel, Olaf Holland (1991), Solution of Large-Scale Symmetric Travelling Salesman Problems, Mathematical Programming 51, pp. 141-202.

[15] Sunderesh S. Heragu, Andrew Kusiak (1988), Machine Layout Problem in Flexible Manufacturing Systems.  Operations Research, Vol. 36, No. 2, Operations Research in Manufacturing (Mar. - Apr., 1988), pp. 258-268.

[16] S. S. Heragu, A. Kusiak (1991), Efficient Models for the Facility Layout Problem.  European Journal of Operational Research, Vol. 53 (1991), pp. 1-13.

[17] S. S. Heragu, Facilities Design, Third Edition.  Boca Raton, Florida: CRC Press, 2008.

[18] Michael Junger, Thomas M. Liebling, Dennis Naddef, George L. Nemhauser, William R. Pulleybank, Gerhart Reinelt, Giovanni Rinaldi, Lawrence A. Wolsey--Editors, 50 Years of Integer Programming 1958-2008.  Berlin: Springer, 2010.

[19] R. L. Karg, G. L. Thompson (1964), A Heuristic Approach to Solving Travelling Salesman Problems.  Management Science, Vol. 10, Number 2, pp. 225-248.

[20] K. Ravi Kumar, George C. Hadjinicola, Ting-li Lin (1995), A Heuristic Procedure for the Single-Row Facility Layout Problem.  European Journal of Operational Research 87 (1995) 65-73.

[21]  A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems.  Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.

[22] E. L. Lawler, M. D. Bell, A Method for Solving Discrete Optimization Problems.  Operations Research, Vol. 14, No. 6 (Nov.-Dec., 1966), pp. 1098-1112.

[23] Robert F. Love, Jsun Y. Wong (1976), On Solving a One-Dimensional Space Allocation Problem with Integer Programming.  INFOR, Vol. 14, No. 2, June 1976, pp. 139-143.
 
[24] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems.  Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.     

[25] Ken McAloon, Carol Tretkoff, Optimization and Computational Logic.  John Wiley and Sons, Inc., 1996.

[26] 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.

[27] Katta G. Murty, Opereations Research: Deterministic Optimization Models.  Prentice Hall, Upper Saddle River, New Jersey 07458, 1994.

[28] C. E. Nugent, T. E. Vollmann, J. Ruml (1968), An Experimental Comparison of Techniques for the Assignment of Facilities to Locations, Operations Research 16 (1968), pp. 150-173.

[29] Christopher J. Picone, Wilbert E. Wilhelm (1986), "A Perturbation Scheme To Improve Hillier's Solution to the Facilities Layout Problem": a Clarification.  Management Science Vol. 32, No. 2, February 1986, pp. 253-254. 

[30] Cliff T. Ragsdale, Spreadsheet Modeling and Decision Analysis, Fifth Edition.  South-Westen, Cengage Learning, 2008.

[31] H. H. Rosenbrock (1960), An Automatic Method for Finding the Greatest or Least Value of a Function, Computer Journal Vol. 3, pp. 175-184.

[32] Donald M. Simmons (1969), One-Dimensional Space Allocation: An Ordering Algorithm.     Operations Research, Vol. 17, No. 5 (Sep. - Oct., 1969), pp. 812-826.

[33] Wayne L. Winston, Munirpallam Venkataramanan, Introduction to Mathematical Programming: Operations Research, Volume One, Fourth Edition.  Pacific Grove, CA 93950: Brooks/Cole--Thomson Learning, 2003.

[34] Wayne L. Winston, S. Christian Albright, Practical Management Science, Third Edition.  Thomson/South-Western, 2007.

[35] Jsun Yui Wong (2009, July 18).  An Integer Programming Computer Program Applied to One-Dimensional Space Allocation.  Retrieved from http://wongsllllblog.blogspot.com/2009/07/

[36] Jsun Yui Wong (2009, November 2).  A Computer Program for Relative Location of Circular Facilities.  Retrieved on September 3, 2012, from http://wongsllllblog.blogspot.ca/2009/11/

[37] Jsun Yui Wong (2009, December 18).  A Heuristic Nonlinear Integer Solver Applied to a Problem of Assignment of Facilities to Locations.  Retrieved from http://wongsnewnewblog.blogspot.ca/2009/12/

[38] Jsun Yui Wong (2011, October 27).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a New Formulation of a Twelve-City Traveling Salesman Problem, Sixth Edition.     Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/10/27/

[39] Ji-Hui Zhang, Xin-He Xu (1999), An Efficient Evoutionary Programming Algorithm.  Computers and Operations Research 26, 645-663.