Substance

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

Jsun Yui Wong

Based on the computer program of the older edition, the following computer program seeks to solve Problem S11 on page 3328 of Amaral [3].

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),C(22),CC(22),Y(22),A
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
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
232 IF X(J44)=1 THEN HHR(J44)=HR(J44)  ELSE GOTO 234
233 Y(1)=J44
234 IF X(J44)=2 THEN HHR(J44)=HR(J44)  ELSE GOTO 244
237 Y(2)=J44
244 IF X(J44)=3 THEN HHR(J44)=HR(J44) ELSE GOTO 254
247 Y(3)=J44
254 IF X(J44)=4 THEN HHR(J44)=HR(J44) ELSE GOTO 257
255 Y(4)=J44
257 IF X(J44)=5 THEN HHR(J44)=HR(J44) ELSE GOTO 259
258 Y(5)=J44
259 IF X(J44)=6 THEN HHR(J44)=HR(J44) ELSE GOTO 277
260 Y(6)=J44
277 IF X(J44)=7   THEN HHR(J44)=HR(J44) ELSE GOTO 279
278 Y(7)=J44
279 IF X(J44)=8 THEN HHR(J44)=HR(J44) ELSE GOTO 285
280 Y(8)=J44
285 IF X(J44)=9 THEN HHR(J44)=HR(J44) ELSE GOTO 289
287 Y(9)=J44
289 IF X(J44)=10 THEN HHR(J44)=HR(J44) ELSE GOTO 296
293 Y(10)=J44
296 IF X(J44)=11 THEN HHR(J44)=HR(J44) ELSE GOTO 307
298 Y(11)=J44
307 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))
327 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))
356 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

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] W. J. Fabrycky, P. M. Ghare, P. E. Torgersen, Applied Operations Research and Management Science.  Englewood Cliffs, N. J. 07362: Prentice-Hall, Inc., 1984.

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

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

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

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

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

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

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

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

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

[21] 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.
 
[22] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems.  Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.     

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

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

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

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

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

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

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

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

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

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

[33] 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/

[34] 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/

[35] 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/

[36] 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

Jsun Yui Wong

The following computer program seeks to solve Problem S11 on page 3328 of Amaral [3].

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),C(22),CC(22)
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
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
232 IF X(J44)=6 THEN HHR(J44)=HR(J44)  ELSE GOTO 234
233 Y=J44
234 IF X(J44)=5 THEN HHR(J44)=HR(J44)  ELSE GOTO 244
237 YY=J44
244 IF X(J44)=4 THEN HHR(J44)=HR(J44) ELSE GOTO 254
247 YYY=J44
254 IF X(J44)=3 THEN HHR(J44)=HR(J44) ELSE GOTO 257
255 YYYY=J44
257 IF X(J44)=2 THEN HHR(J44)=HR(J44) ELSE GOTO 259
258 YYYYY=J44
259 IF X(J44)=1 THEN HHR(J44)=HR(J44) ELSE GOTO 277
260 YYYYYY=J44
277 IF X(J44)=11   THEN HHR(J44)=HR(J44) ELSE GOTO 279
278 YYYYYYY=J44
279 IF X(J44)=10 THEN HHR(J44)=HR(J44) ELSE GOTO 285
280 YYYYYYYY=J44
285 IF X(J44)=9 THEN HHR(J44)=HR(J44) ELSE GOTO 289
287 YYYYYYYYY=J44
289 IF X(J44)=8 THEN HHR(J44)=HR(J44) ELSE GOTO 296
293 YYYYYYYYYY=J44
296 IF X(J44)=7 THEN HHR(J44)=HR(J44) ELSE GOTO 307
298 YYYYYYYYYYY=J44
307 C(6)=.5*HHR(Y)+HHR(YY)+HHR(YYY)+HHR(YYYY)+HHR(YYYYY)+HHR(YYYYYY)
311 C(5)=.5*HHR(YY)+HHR(YYY)+HHR(YYYY)+HHR(YYYYY)+HHR(YYYYYY)
314 C(4)=.5*HHR(YYY)+HHR(YYYY)+HHR(YYYYY)+HHR(YYYYYY)
318 C(3)=.5*HHR(YYYY)+HHR(YYYYY)+HHR(YYYYYY)
323 C(2)=.5*HHR(YYYYY)+HHR(YYYYYY)
327 C(1)=.5*HHR(YYYYYY)
341 C(11  )=.5*HHR(YYYYYYY)+HHR(YYYYYYYY)+HHR(YYYYYYYYY)+HHR(YYYYYYYYYY)+HHR(YYYYYYYYYYY)
345 C(10)=.5*HHR(YYYYYYYY)+HHR(YYYYYYYYY)+HHR(YYYYYYYYYY)+HHR(YYYYYYYYYYY)
349 C(9)=.5*HHR(YYYYYYYYY)+HHR(YYYYYYYYYY)+HHR(YYYYYYYYYYY)
353 C(8)=.5*HHR(YYYYYYYYYY)+HHR(YYYYYYYYYYY)
355 C(7)=.5*HHR(YYYYYYYYYYY)
361 NEXT J44
401 PNEW=-HS(Y,YY)*ABS(C(6)-C(5))-HS(Y,YYY)*ABS(C(6)-C(4))-HS(Y,YYYY)*ABS (C(6)-C(3))-HS(Y,YYYYY)*ABS(C(6)-C(2))-HS(Y,YYYYYY)*ABS(C(6)-C(1))-HS(Y,YYYYYYY)*ABS(C(6)-C(11))-HS(Y,YYYYYYYY)*ABS(C(6)-C(10))-HS(Y,YYYYYYYYY)*ABS(C(6)-C(9))
403 PNEWS=-HS(Y,YYYYYYYYYY)*ABS(C(6)-C( 8))-HS(Y,YYYYYYYYYYY)*ABS(C(6)-C(7))
406 PNEWW=-HS(YY,YYY)*ABS(C(5)-C(4))-HS(YY,YYYY)*ABS(C(5)-C(3))-HS(YY,YYYYY)*ABS(C(5)-C(2))-HS(YY,YYYYYY)*ABS(C(5)-C(1))-HS(YY,YYYYYYY)*ABS(C(5)-C(11))-HS(YY,YYYYYYYY)*ABS(C(5)-C(10))
407 PNEWWS=-HS(YY,YYYYYYYYY)*ABS(C(5)-C(9))-HS(YY,YYYYYYYYYY)*ABS(C(5)-C(8))-HS(YY,YYYYYYYYYYY)*ABS(C(5)-C(7))
408 PNEWWW=-HS(YYY,YYYY)*ABS(C(4)-C(3))-HS(YYY,YYYYY)*ABS(C(4)-C(2))-HS(YYY,YYYYYY)*ABS(C(4)-C(1))-HS(YYY,YYYYYYY)*ABS(C(4)-C(11))-HS(YYY,YYYYYYYY)*ABS(C(4)-C(10))-HS(YYY,YYYYYYYYY)*ABS(C(4)-C(9))-HS(YYY,YYYYYYYYYY)*ABS(C(4)-C(8))
409 PNEWWWS=-HS(YYY,YYYYYYYYYYY)*ABS(C(4)-C(7))
410 PNEWWWW=-HS(YYYY,YYYYY)*ABS(C(3)-C(2))-HS(YYYY,YYYYYY)*ABS(C(3)-C(1))-HS(YYYY,YYYYYYY)*ABS(C(3)-C(11))-HS(YYYY,YYYYYYYY)*ABS (C(3)-C(10))-HS(YYYY,YYYYYYYYY)*ABS(C(3)-C(9))-HS(YYYY,YYYYYYYYYY)*ABS(C(3)-C(8)) -HS(YYYY,YYYYYYYYYYY  )*ABS(C( 3)-C(7))
411 PNEWWWWW=-HS(YYYYY,YYYYYY)*ABS(C(2)-C(1))-HS(YYYYY,YYYYYYY)*ABS(C(2)-C(11))-HS(YYYYY,YYYYYYYY)*ABS(C(2)-C(10))-HS(YYYYY,YYYYYYYYY)*ABS (C(2)-C(9))-HS(YYYYY,YYYYYYYYYY)*ABS(C(2)-C(8)) -HS(YYYYY,YYYYYYYYYYY )*ABS(C(2)- C(7) )
412 PNEWWWWWW=-HS(YYYYYY,YYYYYYY)*ABS(C(1)-C(11))-HS(YYYYYY,YYYYYYYY)*ABS(C(1)-C(10))-HS(YYYYYY,YYYYYYYYY)*ABS(C(1)-C(9))-HS(YYYYYY,YYYYYYYYYY)*ABS (C(1)-C(8)     )    -HS(YYYYYY,YYYYYYYYYYY   )*ABS( C(1)-C(7) )
413 PNEWWWWWWW=-HS(YYYYYYY,YYYYYYYY)*ABS(C(11)-C(10))-HS(YYYYYYY,YYYYYYYYY)*ABS(C(11)-C(9))-HS(YYYYYYY,YYYYYYYYYY)*ABS(C(11)-C(8))-HS(YYYYYYY,YYYYYYYYYYY )*ABS(C(11)-C( 7) )
414 PNEWWWWWWWW=-HS(YYYYYYYY,YYYYYYYYY)*ABS(C(10)-C(9))-HS(YYYYYYYY,YYYYYYYYYY)*ABS(C(10)-C(8))    -HS(YYYYYYYY,YYYYYYYYYYY   )*ABS( C(10)-C(7)  )
416 PNEWWWWWWWWW=-HS(YYYYYYYYY,YYYYYYYYYY)*ABS(C(9)-C(8))-HS (YYYYYYYYY,YYYYYYYYYYY )*ABS(C(9)-C(7)     )
418 PNEWWWWWWWWWW=-HS(YYYYYYYYYY,YYYYYYYYYYY)*ABS(C(8)-C(7))
421 P=PNEW+PNEWS+PNEWW+PNEWWS+PNEWWW+ PNEWWWS +PNEWWWW+PNEWWWWW+PNEWWWWWW+PNEWWWWWWW+PNEWWWWWWWW + PNEWWWWWWWWW   +PNEWWWWWWWWWW
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

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

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

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

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= -31339 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] W. J. Fabrycky, P. M. Ghare, P. E. Torgersen, Applied Operations Research and Management Science.  Englewood Cliffs, N. J. 07362: Prentice-Hall, Inc., 1984.

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

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

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

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

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

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

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

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

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

[21] 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.
 
[22] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems.  Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.     

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

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

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

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

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

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

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

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

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

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

[33] 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/

[34] 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/

[35] 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/

[36] 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 a One-Dimensional Layout Problem of 30 Facilities, Third Edition

Jsun Yui Wong

The following computer program seeks to solve Problem 8 of Heragu and Kusiak [14, page 9].  The article by Anjos and Vannelli also considers this problem [3, pages 614-615].

Lines 27, 28, and 29 here are different from lines 27, 28, and 29 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)
3 DIM HS(49,49)
4 DIM PE(49,49)
5 DIM SD(49,49)
11 REM FOR J44=1 TO 30
15 REM  HR(J44)=1
17 REM NEXT J44
27 HR(1)=3:HR(2)=9:HR(3)=3:HR(4)=7:HR(5)=3:HR(6)=7:HR(7)=5:HR(8)=9:   HR(9)=6:HR(10)=5
28 HR(11)=3:HR(12)=9:HR(13)=3:HR(14)=7:HR(15)=3:HR(16)=7:HR(17)=5:HR(18)=9:   HR(19)=6:HR(20)=5
29 HR(21)=3:HR(22)=9:HR(23)=3:HR(24)=7:HR(25)=3:HR(26)=7:HR(27)=5:HR(28)=9:   HR(29)=6:HR(30)=5
31 FOR IL=1 TO 29
32 FOR JL=IL+1 TO 30
33 READ HS(IL,JL)
34 NEXT JL
35 NEXT IL
42 DATA 3,2,0,0,2,10,5,0,5,2,5,0,0,2,0,5,6,3,0,1,10,0,10,2,1,1,1,0,1
43 DATA 4,0,10,4,0,0,2,2,1,0,5,0,0,0,0,2,0,1,6,1,0,1,2,2,5,1,10,5
44 DATA 3,4,0,5,5,5,1,4,1,0,4,0,4,0,6,3,2,5,5,2,1,0,0,3,1,0,2
45 DATA 0,0,0,2,2,0,6,0,2,5,2,5,1,1,1,1,2,2,4,0,2,0,2,2,5,5
46 DATA 5,2,0,0,0,0,2,0,0,0,0,2,1,0,0,2,0,5,1,0,2,1,0,2,1
47 DATA 1,2,2,1,4,10,10,2,5,5,0,5,0,0,0,10,0,0,0,4,0,10,1,1
48 DATA 10,10,5,10,10,6,0,0,10,2,1,10,1,5,5,2,3,5,0,2,0,1,3
49 DATA 1,3,5,0,0,0,2,4,5,2,10,6,0,5,5,2,5,0,5,5,0,2
50 DATA 10,2,1,5,2,0,3,0,2,0,0,4,0,5,2,0,5,2,2,5,2
51 DATA 5,5,6,0,1,5,5,0,5,2,3,5,0,5,2,10,10,1,5,2
52 DATA 0,0,1,2,1,0,2,0,0,0,6,6,0,4,5,3,2,2,10
53 DATA 5,5,2,0,0,0,0,2,0,4,5,10,1,0,0,0,0,1
54 DATA 2,0,4,2,2,1,0,6,2,1,5,5,0,0,1,5,5
55 DATA 2,1,0,5,3,10,0,0,4,2,0,0,4,2,5,5
56 DATA 4,5,1,0,1,0,5,0,2,0,0,5,1,1,0
57 DATA 0,3,0,2,2,0,2,0,5,0,5,2,5,10
58 DATA 2,2,0,0,0,6,5,3,5,0,0,5,1
59 DATA 5,1,2,10,10,4,0,0,5,0,0,0
60 DATA 0,5,5,1,0,5,2,1,2,10,10
61 DATA 5,2,1,3,1,5,6,5,5,3
62 DATA 4,0,1,0,0,0,5,0,0
63 DATA 5,0,4,4,5,0,2,5
64 DATA 0,4,4,1,0,2,2
65 DATA 5,5,0,1,0,0
66 DATA 1,0,10,1,0
67 DATA 0,0,0,0
68 DATA 0,0,10
69 DATA 2,2
70 DATA 2
78 FOR JJJJ=-32000 TO 32000
79 RANDOMIZE JJJJ
80 M=-1D+37
81 FOR J44=1 TO 30
83 A(J44)=J44
84 NEXT J44
126 REM IMAR=10+FIX(RND*1000)
128 FOR I=1 TO 700
129 FOR KKQQ=1 TO 30
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 III=1+FIX(RND*30)
134 JJJ=1+FIX(RND*30)
221    X(III)=A(JJJ)
223    X(JJJ)=A(III)
225 FOR II=1 TO 29
227 FOR JJ=II+1 TO 30
231 SD(II,JJ)=0
235 SD(II,JJ)=.5*HR(II)+.5*HR(JJ)
239 FOR KK = 1 TO 30
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 29
312 FOR J88=IW+1 TO 30
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 30
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-44977! 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),A(25)
1906 PRINT A(26),A(27),A(28),A(29),A(30)
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=-31938 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

9   1   18   29   2
6   17   25   15   14
19   4   13   28   10
22   8   7   24   27
16   11   12   5   20
3   21   30   26   23
-44976   -31988

21   30   13   2   29
25   14   6   16   17
12   27   18   3   23
9   24   22   7   4
15   20   19   26   11
28   10   1   5   8
-44965   -31940

10   1   18   29   2
6   17   25   15   14
19   4   13   28   8
22   7   9   24   27
16   11   12   5   20
3   21   30   26   23
-44965   -31938

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= -31938 was three hours and fifteen 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] 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[20] 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.
 
[21] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems.  Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.     

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

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

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

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

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

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

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

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

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

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

[32] 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/

[33] 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/

[34] 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/

[35] 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 Single-Row Layout Problem of 30 Facilities with Clearance Requirement, Second Edition

Jsun Yui Wong

The following computer program seeks to solve Problem Lit-Cl-8 in Anjos and Vannelli [3, page 615].  The source of this problem is Heragu and Kusiak [13].  The article by Kumar, Hadjinicola, and Lin [17, page 70, Table 1] also considers this problem.

While line 128 of the older edition is 128 FOR I=1 TO 300, here line 128 is 128 FOR I=1 TO 400.

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 REM   FOR J44=1 TO 30
15 REM   HR(J44)=1
17 REM   NEXT J44
18 HR(1)=.05:HR(2)=.03:HR(3)=.06
19   HR(4)=.04:HR(5)=.02:HR(6)=.06:HR(7)=9.000001E-02:HR(8)=.02
20   HR(9)=.06:HR(10)=.05:HR(11)=.06:HR(12)=.02
28   HR(13)=.04:HR(14)=.03:HR(15)=.04:HR(16)=.02:HR(17)=.03:HR(18)=.04:   HR(19)=.05:HR(20)=9.000001E-02
29  HR(21)=.06:HR(22)=.02:HR(23)=.02:HR(24)=.03:HR(25)=.04:HR(26)=.05:HR(27)=.05:HR(28)=.02:   HR(29)=.03:HR(30)=.04
31 FOR IL=1 TO 29
32 FOR JL=IL+1 TO 30
33 READ HS(IL,JL)
34 NEXT JL
35 NEXT IL
42 DATA 3,2,0,0,2,10,5,0,5,2,5,0,0,2,0,5,6,3,0,1,10,0,10,2,1,1,1,0,1
43 DATA 4,0,10,4,0,0,2,2,1,0,5,0,0,0,0,2,0,1,6,1,0,1,2,2,5,1,10,5
44 DATA 3,4,0,5,5,5,1,4,1,0,4,0,4,0,6,3,2,5,5,2,1,0,0,3,1,0,2
45 DATA 0,0,0,2,2,0,6,0,2,5,2,5,1,1,1,1,2,2,4,0,2,0,2,2,5,5
46 DATA 5,2,0,0,0,0,2,0,0,0,0,2,1,0,0,2,0,5,1,0,2,1,0,2,1
47 DATA 1,2,2,1,4,10,10,2,5,5,0,5,0,0,0,10,0,0,0,4,0,10,1,1
48 DATA 10,10,5,10,10,6,0,0,10,2,1,10,1,5,5,2,3,5,0,2,0,1,3
49 DATA 1,3,5,0,0,0,2,4,5,2,10,6,0,5,5,2,5,0,5,5,0,2
50 DATA 10,2,1,5,2,0,3,0,2,0,0,4,0,5,2,0,5,2,2,5,2
51 DATA 5,5,6,0,1,5,5,0,5,2,3,5,0,5,2,10,10,1,5,2
52 DATA 0,0,1,2,1,0,2,0,0,0,6,6,0,4,5,3,2,2,10
53 DATA 5,5,2,0,0,0,0,2,0,4,5,10,1,0,0,0,0,1
54 DATA 2,0,4,2,2,1,0,6,2,1,5,5,0,0,1,5,5
55 DATA 2,1,0,5,3,10,0,0,4,2,0,0,4,2,5,5
56 DATA 4,5,1,0,1,0,5,0,2,0,0,5,1,1,0
57 DATA 0,3,0,2,2,0,2,0,5,0,5,2,5,10
58 DATA 2,2,0,0,0,6,5,3,5,0,0,5,1
59 DATA 5,1,2,10,10,4,0,0,5,0,0,0
60 DATA 0,5,5,1,0,5,2,1,2,10,10
61 DATA 5,2,1,3,1,5,6,5,5,3
62 DATA 4,0,1,0,0,0,5,0,0
63 DATA 5,0,4,4,5,0,2,5
64 DATA 0,4,4,1,0,2,2
65 DATA 5,5,0,1,0,0
66 DATA 1,0,10,1,0
67 DATA 0,0,0,0
68 DATA 0,0,10
69 DATA 2,2
70 DATA 2
78 FOR JJJJ=-32000 TO 32000
79 RANDOMIZE JJJJ
80 M=-1D+37
81 FOR J44=1 TO 30
83 A(J44)=J44
84 NEXT J44
126 REM IMAR=10+FIX(RND*1000)
128 FOR I=1 TO 400
129 FOR KKQQ=1 TO 30
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 III=1+FIX(RND*30)
134 JJJ=1+FIX(RND*30)
221    X(III)=A(JJJ)
223    X(JJJ)=A(III)
225 FOR II=1 TO 29
227 FOR JJ=II+1 TO 30
231 SD(II,JJ)=0
235 SD(II,JJ)=.5*HR(II)+.5*HR(JJ)
239 FOR KK = 1 TO 30
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 29
312 FOR J88=IW+1 TO 30
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 30
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-334.87 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),A(25)
1906 PRINT A(26),A(27),A(28),A(29),A(30)
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=-31904 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

24   8   3   4   7
20   23   16   29   26
12   22   21   5   28
17   27   13   11   1
2   15   14   25   19
30   6   18   10   9
-334.6552   -31943

7   23   28   27   24
11   8   16   2   5
12   9   10   26   3
19   4   15   20   30
29   13   14   6   17
1   25   18   21   22
-334.7351   -31904

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= -31904 was three hours 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] Miguel F. Anjos, Anthony Vannelli (2008), 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[20] 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.
 
[21] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems.  Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.     

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

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

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

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

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

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

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

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

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

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

[32] 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/

[33] 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/

[34] 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/

[35] 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 a Single-Row Layout Problem of Eight Facilities with Clearance Requirement

Jsun Yui Wong

The following computer program seeks to solve Problem Lit-Cl-4 in Anjos and Vannelli [3, page 10].  The source of this problem is Heragu and Kusiak [13].  The article by Kumar, Hadjinicola, and Lin [17, page 70, Table 1] also considers this problem.

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)
27 HR(1)=.05:HR(2)=.03:HR(3)=.06
28   HR(4)=.04:HR(5)=.02:HR(6)=.06:HR(7)=9.000001E-02:HR(8)=.02
31 FOR IL=1 TO 7
32 FOR JL=IL+1 TO 8
33 READ HS(IL,JL)
34 NEXT JL
35 NEXT IL
64 DATA 5,2,4,1,0,0,6
65 DATA 3,0,2,2,2,0
66 DATA 0,0,0,0,5
67 DATA 5,2,2,10
68 DATA 10,0,0
69 DATA 5,1
70 DATA 10
78 FOR JJJJ=-32000 TO 32000
79 RANDOMIZE JJJJ
80 M=-1D+37
81 FOR J44=1 TO 8
83 A(J44)=J44
84 NEXT J44
126 REM IMAR=10+FIX(RND*1000)
128 FOR I=1 TO 100
129 FOR KKQQ=1 TO 8
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 III=1+FIX(RND*8)
134 JJJ=1+FIX(RND*8)
221    X(III)=A(JJJ)
223    X(JJJ)=A(III)
225 FOR II=1 TO 7
227 FOR JJ=II+1 TO 8
231 SD(II,JJ)=0
235 SD(II,JJ)=.5*HR(II)+.5*HR(JJ)
239 FOR KK = 1 TO 8
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 7
312 FOR J88=IW+1 TO 8
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 8
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-6.5 THEN 1999
1901 PRINT A(1),A(2),A(3),A(4),A(5)
1902 PRINT A(6),A(7),A(8),M,JJJJ
1999 NEXT JJJJ

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

3   2   1   5   6
7   8   4   -6.295   -32000

3   2   1   5   7
8   6   4   -6.445001   -31999

3   2   1   5   6
7   8   4   -6.295   -31998

3   2   1   5   6
7   8   4   -6.295   -31997

3   2   1   5   7
8   6   4   -6.445001   -31996

3   2   1   5   7
8   6   4   -6.445001   -31993

3   2   1   5   6
7   8   4   -6.295   -31992

3   2   1   5   7
8   6   4   -6.445001   -31991

6   7   8   4   3
2   1   5   -6.295   -31988

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= -31988 was four 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] Miguel F. Anjos, Anthony Vannelli, Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes.  Retrieved on Auguest 18, 2012, from Google search.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[20] 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.
 
[21] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems.  Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.     

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

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

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

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

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

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

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

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

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

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

[32] 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/

[33] 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/

[34] 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/

[35] 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 Single-Row Layout Problem of Seven Facilities with Clearance Requirement

Jsun Yui Wong

The following computer program seeks to solve Problem Lit-Cl-3 in Anjos and Vannelli [3, page 10].  The source of this problem is Heragu and Kusiak [13].  The article by Kumar, Hadjinicola, and Lin [17, page 70, Table 1] also considers this problem.

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)
27 HR(1)=.05:HR(2)=.03:HR(3)=.06
28   HR(4)=.04:HR(5)=.02:HR(6)=.06:HR(7)=9.000001E-02
31 FOR IL=1 TO 6
32 FOR JL=IL+1 TO 7
33 READ HS(IL,JL)
34 NEXT JL
35 NEXT IL
65 DATA 5,2,4,1,0,0
66 DATA 3,0,2,2,2
67 DATA 1,0,2,5
68 DATA 5,2,2
69 DATA 10,0
70 DATA 5
78 FOR JJJJ=-32000 TO 32000
79 RANDOMIZE JJJJ
80 M=-1D+37
81 FOR J44=1 TO 7
83 A(J44)=J44
84 NEXT J44
126 REM IMAR=10+FIX(RND*1000)
128 FOR I=1 TO 100
129 FOR KKQQ=1 TO 7
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 III=1+FIX(RND*7)
134 JJJ=1+FIX(RND*7)
221    X(III)=A(JJJ)
223    X(JJJ)=A(III)
225 FOR II=1 TO 6
227 FOR JJ=II+1 TO 7
231 SD(II,JJ)=0
235 SD(II,JJ)=.5*HR(II)+.5*HR(JJ)
239 FOR KK = 1 TO 7
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 6
312 FOR J88=IW+1 TO 7
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 7
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-4.75 THEN 1999
1901 PRINT A(1),A(2),A(3),A(4),A(5)
1902 PRINT A(6),A(7)
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=-31928 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

1   2   6   3   4
5   7
-4.73   -31989

1   2   6   3   4
5   7
-4.73   -31974

1   2   6   3   4
5   7
-4.73   -31972

7   6   2   5   4
3   1
-4.73   -31957

1   2   6   3   4
5   7
-4.73   -31928

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= -31928 was 12 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] Miguel F. Anjos, Anthony Vannelli, Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes.  Retrieved on Auguest 18, 2012, from Google search.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[20] 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.
 
[21] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems.  Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.     

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

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

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

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

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

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

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

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

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

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

[32] 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/

[33] 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/

[34] 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/

[35] 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 Single-Row Layout Problem of 30 Facilities with Clearance Requirement

Jsun Yui Wong

The following computer program seeks to solve Problem Lit-Cl-8 in Anjos and Vannelli [3, Section 4.2].  The source of this problem is Heragu and Kusiak [13].

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 REM   FOR J44=1 TO 30
15 REM   HR(J44)=1
17 REM   NEXT J44
18 HR(1)=.05:HR(2)=.03:HR(3)=.06
19   HR(4)=.04:HR(5)=.02:HR(6)=.06:HR(7)=9.000001E-02:HR(8)=.02
20   HR(9)=.06:HR(10)=.05:HR(11)=.06:HR(12)=.02
28   HR(13)=.04:HR(14)=.03:HR(15)=.04:HR(16)=.02:HR(17)=.03:HR(18)=.04:   HR(19)=.05:HR(20)=9.000001E-02
29  HR(21)=.06:HR(22)=.02:HR(23)=.02:HR(24)=.03:HR(25)=.04:HR(26)=.05:HR(27)=.05:HR(28)=.02:   HR(29)=.03:HR(30)=.04
31 FOR IL=1 TO 29
32 FOR JL=IL+1 TO 30
33 READ HS(IL,JL)
34 NEXT JL
35 NEXT IL
42 DATA 3,2,0,0,2,10,5,0,5,2,5,0,0,2,0,5,6,3,0,1,10,0,10,2,1,1,1,0,1
43 DATA 4,0,10,4,0,0,2,2,1,0,5,0,0,0,0,2,0,1,6,1,0,1,2,2,5,1,10,5
44 DATA 3,4,0,5,5,5,1,4,1,0,4,0,4,0,6,3,2,5,5,2,1,0,0,3,1,0,2
45 DATA 0,0,0,2,2,0,6,0,2,5,2,5,1,1,1,1,2,2,4,0,2,0,2,2,5,5
46 DATA 5,2,0,0,0,0,2,0,0,0,0,2,1,0,0,2,0,5,1,0,2,1,0,2,1
47 DATA 1,2,2,1,4,10,10,2,5,5,0,5,0,0,0,10,0,0,0,4,0,10,1,1
48 DATA 10,10,5,10,10,6,0,0,10,2,1,10,1,5,5,2,3,5,0,2,0,1,3
49 DATA 1,3,5,0,0,0,2,4,5,2,10,6,0,5,5,2,5,0,5,5,0,2
50 DATA 10,2,1,5,2,0,3,0,2,0,0,4,0,5,2,0,5,2,2,5,2
51 DATA 5,5,6,0,1,5,5,0,5,2,3,5,0,5,2,10,10,1,5,2
52 DATA 0,0,1,2,1,0,2,0,0,0,6,6,0,4,5,3,2,2,10
53 DATA 5,5,2,0,0,0,0,2,0,4,5,10,1,0,0,0,0,1
54 DATA 2,0,4,2,2,1,0,6,2,1,5,5,0,0,1,5,5
55 DATA 2,1,0,5,3,10,0,0,4,2,0,0,4,2,5,5
56 DATA 4,5,1,0,1,0,5,0,2,0,0,5,1,1,0
57 DATA 0,3,0,2,2,0,2,0,5,0,5,2,5,10
58 DATA 2,2,0,0,0,6,5,3,5,0,0,5,1
59 DATA 5,1,2,10,10,4,0,0,5,0,0,0
60 DATA 0,5,5,1,0,5,2,1,2,10,10
61 DATA 5,2,1,3,1,5,6,5,5,3
62 DATA 4,0,1,0,0,0,5,0,0
63 DATA 5,0,4,4,5,0,2,5
64 DATA 0,4,4,1,0,2,2
65 DATA 5,5,0,1,0,0
66 DATA 1,0,10,1,0
67 DATA 0,0,0,0
68 DATA 0,0,10
69 DATA 2,2
70 DATA 2
78 FOR JJJJ=-32000 TO 32000
79 RANDOMIZE JJJJ
80 M=-1D+37
81 FOR J44=1 TO 30
83 A(J44)=J44
84 NEXT J44
126 REM IMAR=10+FIX(RND*1000)
128 FOR I=1 TO 300
129 FOR KKQQ=1 TO 30
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 III=1+FIX(RND*30)
134 JJJ=1+FIX(RND*30)
221    X(III)=A(JJJ)
223    X(JJJ)=A(III)
225 FOR II=1 TO 29
227 FOR JJ=II+1 TO 30
231 SD(II,JJ)=0
235 SD(II,JJ)=.5*HR(II)+.5*HR(JJ)
239 FOR KK = 1 TO 30
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 29
312 FOR J88=IW+1 TO 30
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 30
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-337 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),A(25)
1906 PRINT A(26),A(27),A(28),A(29),A(30)
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=-31987 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

6   12   25   26   11
13   4   19   3   5
24   8   9   27   29
22   10   21   17   30
1   18   20   7   14
2   28   15   16   23
-335.505   -31990

6   22   28   27   20
12   4   14   2   5
3   9   11   26   25
19   8   17   18   30
29   15   16   7   10
1   24   13   21   23
-335.6651   -31989

7   23   28   27   24
11   8   16   2   5
12   9   10   26   3
17   4   19   20   30
29   13   18   6   14
1   25   15   21   22
-334.6752   -31987

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= -31987 was 40 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] Miguel F. Anjos, Anthony Vannelli, Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes.  Retrieved on Auguest 18, 2012, from Google search.

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

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

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

[7] Leon Cooper, U. N. Bhat, L. J. LeBlanc, Introduction to Operations Researach Models.  W. B. Saunders Company, 1977.
h
[8] George B. Dantzig,  Discrete-Variable Extremum Problems.  Operations Researc, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.

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

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

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

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

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

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

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

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

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

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

[19] 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.
 
[20] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems.  Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.     

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

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

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

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

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

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

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

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

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

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

[31] 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/

[32] 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/

[33] 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/

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

ERRATUM: A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a One-Dimensional Layout Problem of 30 Facilities, Second Edition

Jsun Yui Wong

The last sentence should read:

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= -31938 was three hours and fifteen minutes.

A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a One-Dimensional Layout Problem of 30 Facilities, Second Edition

Jsun Yui Wong

The following computer program seeks to solve Problem 8 of Heragu and Kusiak [12, page 9].  The lengths given in line 27, line 28, and line 29 are twice as long as the lengths in Heragu and Kusiak [12, page 9]. 

While line 128 of the preceding paper is 128 FOR I=1 TO 900, here line 128 is 128 FOR I=1 TO 700.

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)
27 HR(1)=6:HR(2)=18:HR(3)=6:HR(4)=14:HR(5)=6:HR(6)=14:HR(7)=10:HR(8)=18:   HR(9)=12:HR(10)=10
28 HR(11)=6:HR(12)=18:HR(13)=6:HR(14)=14:HR(15)=6:HR(16)=14:HR(17)=10:HR(18)=18:   HR(19)=12:HR(20)=10
29 HR(21)=6:HR(22)=18:HR(23)=6:HR(24)=14:HR(25)=6:HR(26)=14:HR(27)=10:HR(28)=18:   HR(29)=12:HR(30)=10
31 FOR IL=1 TO 29
32 FOR JL=IL+1 TO 30
33 READ HS(IL,JL)
34 NEXT JL
35 NEXT IL
42 DATA 3,2,0,0,2,10,5,0,5,2,5,0,0,2,0,5,6,3,0,1,10,0,10,2,1,1,1,0,1
43 DATA 4,0,10,4,0,0,2,2,1,0,5,0,0,0,0,2,0,1,6,1,0,1,2,2,5,1,10,5
44 DATA 3,4,0,5,5,5,1,4,1,0,4,0,4,0,6,3,2,5,5,2,1,0,0,3,1,0,2
45 DATA 0,0,0,2,2,0,6,0,2,5,2,5,1,1,1,1,2,2,4,0,2,0,2,2,5,5
46 DATA 5,2,0,0,0,0,2,0,0,0,0,2,1,0,0,2,0,5,1,0,2,1,0,2,1
47 DATA 1,2,2,1,4,10,10,2,5,5,0,5,0,0,0,10,0,0,0,4,0,10,1,1
48 DATA 10,10,5,10,10,6,0,0,10,2,1,10,1,5,5,2,3,5,0,2,0,1,3
49 DATA 1,3,5,0,0,0,2,4,5,2,10,6,0,5,5,2,5,0,5,5,0,2
50 DATA 10,2,1,5,2,0,3,0,2,0,0,4,0,5,2,0,5,2,2,5,2
51 DATA 5,5,6,0,1,5,5,0,5,2,3,5,0,5,2,10,10,1,5,2
52 DATA 0,0,1,2,1,0,2,0,0,0,6,6,0,4,5,3,2,2,10
53 DATA 5,5,2,0,0,0,0,2,0,4,5,10,1,0,0,0,0,1
54 DATA 2,0,4,2,2,1,0,6,2,1,5,5,0,0,1,5,5
55 DATA 2,1,0,5,3,10,0,0,4,2,0,0,4,2,5,5
56 DATA 4,5,1,0,1,0,5,0,2,0,0,5,1,1,0
57 DATA 0,3,0,2,2,0,2,0,5,0,5,2,5,10
58 DATA 2,2,0,0,0,6,5,3,5,0,0,5,1
59 DATA 5,1,2,10,10,4,0,0,5,0,0,0
60 DATA 0,5,5,1,0,5,2,1,2,10,10
61 DATA 5,2,1,3,1,5,6,5,5,3
62 DATA 4,0,1,0,0,0,5,0,0
63 DATA 5,0,4,4,5,0,2,5
64 DATA 0,4,4,1,0,2,2
65 DATA 5,5,0,1,0,0
66 DATA 1,0,10,1,0
67 DATA 0,0,0,0
68 DATA 0,0,10
69 DATA 2,2
70 DATA 2
78 FOR JJJJ=-32000 TO 32000
79 RANDOMIZE JJJJ
80 M=-1D+37
81 FOR J44=1 TO 30
83 A(J44)=J44
84 NEXT J44
126 REM IMAR=10+FIX(RND*1000)
128 FOR I=1 TO 700
129 FOR KKQQ=1 TO 30
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 III=1+FIX(RND*30)
134 JJJ=1+FIX(RND*30)
221    X(III)=A(JJJ)
223    X(JJJ)=A(III)
225 FOR II=1 TO 29
227 FOR JJ=II+1 TO 30
231 SD(II,JJ)=0
235 SD(II,JJ)=.5*HR(II)+.5*HR(JJ)
239 FOR KK = 1 TO 30
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 29
312 FOR J88=IW+1 TO 30
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 30
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-89975! 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),A(25)
1906 PRINT A(26),A(27),A(28),A(29),A(30)
1917 PRINT M,JJJJ
1999 NEXT JJJJ

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

9   1   18   29   2
6   17   25   15   14
19   4   13   28   10
22   8   7   24   27
16   11   12   5   20
3   21   30   26   23
-89952   -31988

21   30   13   2   29
25   14   6   16   17
12   27   18   3   23
9   24  22  7   4
15   20   19   26  11
28   10   1   5   8
-89930   -31940

10   1   18   29   2
6   17   25   15   14
19   4   13   28   8
22   7   9   24   27
16   11   12   5  20
3   21   30   26   23
-89930   -31938

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= -31938 was four hours.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[17] 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.
 
[18] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems.  Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.     

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

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

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

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

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

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

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

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

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

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

[29] 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/

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

[31] 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/

[32] 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 One-Dimensional Layout Problem of 30 Facilities

Jsun Yui Wong

The following computer program seeks to solve Problem 8 of Heragu and Kusiak [12, page 9]. 


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)
27 HR(1)=6:HR(2)=18:HR(3)=6:HR(4)=14:HR(5)=6:HR(6)=14:HR(7)=10:HR(8)=18:   HR(9)=12:HR(10)=10
28 HR(11)=6:HR(12)=18:HR(13)=6:HR(14)=14:HR(15)=6:HR(16)=14:HR(17)=10:HR(18)=18:   HR(19)=12:HR(20)=10
29 HR(21)=6:HR(22)=18:HR(23)=6:HR(24)=14:HR(25)=6:HR(26)=14:HR(27)=10:HR(28)=18:   HR(29)=12:HR(30)=10
31 FOR IL=1 TO 29
32 FOR JL=IL+1 TO 30
33 READ HS(IL,JL)
34 NEXT JL
35 NEXT IL
42 DATA 3,2,0,0,2,10,5,0,5,2,5,0,0,2,0,5,6,3,0,1,10,0,10,2,1,1,1,0,1
43 DATA 4,0,10,4,0,0,2,2,1,0,5,0,0,0,0,2,0,1,6,1,0,1,2,2,5,1,10,5
44 DATA 3,4,0,5,5,5,1,4,1,0,4,0,4,0,6,3,2,5,5,2,1,0,0,3,1,0,2
45 DATA 0,0,0,2,2,0,6,0,2,5,2,5,1,1,1,1,2,2,4,0,2,0,2,2,5,5
46 DATA 5,2,0,0,0,0,2,0,0,0,0,2,1,0,0,2,0,5,1,0,2,1,0,2,1
47 DATA 1,2,2,1,4,10,10,2,5,5,0,5,0,0,0,10,0,0,0,4,0,10,1,1
48 DATA 10,10,5,10,10,6,0,0,10,2,1,10,1,5,5,2,3,5,0,2,0,1,3
49 DATA 1,3,5,0,0,0,2,4,5,2,10,6,0,5,5,2,5,0,5,5,0,2
50 DATA 10,2,1,5,2,0,3,0,2,0,0,4,0,5,2,0,5,2,2,5,2
51 DATA 5,5,6,0,1,5,5,0,5,2,3,5,0,5,2,10,10,1,5,2
52 DATA 0,0,1,2,1,0,2,0,0,0,6,6,0,4,5,3,2,2,10
53 DATA 5,5,2,0,0,0,0,2,0,4,5,10,1,0,0,0,0,1
54 DATA 2,0,4,2,2,1,0,6,2,1,5,5,0,0,1,5,5
55 DATA 2,1,0,5,3,10,0,0,4,2,0,0,4,2,5,5
56 DATA 4,5,1,0,1,0,5,0,2,0,0,5,1,1,0
57 DATA 0,3,0,2,2,0,2,0,5,0,5,2,5,10
58 DATA 2,2,0,0,0,6,5,3,5,0,0,5,1
59 DATA 5,1,2,10,10,4,0,0,5,0,0,0
60 DATA 0,5,5,1,0,5,2,1,2,10,10
61 DATA 5,2,1,3,1,5,6,5,5,3
62 DATA 4,0,1,0,0,0,5,0,0
63 DATA 5,0,4,4,5,0,2,5
64 DATA 0,4,4,1,0,2,2
65 DATA 5,5,0,1,0,0
66 DATA 1,0,10,1,0
67 DATA 0,0,0,0
68 DATA 0,0,10
69 DATA 2,2
70 DATA 2
78 FOR JJJJ=-32000 TO 32000
79 RANDOMIZE JJJJ
80 M=-1D+37
81 FOR J44=1 TO 30
83 A(J44)=J44
84 NEXT J44
126 REM IMAR=10+FIX(RND*1000)
128 FOR I=1 TO 900
129 FOR KKQQ=1 TO 30
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 III=1+FIX(RND*30)
134 JJJ=1+FIX(RND*30)
221    X(III)=A(JJJ)
223    X(JJJ)=A(III)
225 FOR II=1 TO 29
227 FOR JJ=II+1 TO 30
231 SD(II,JJ)=0
235 SD(II,JJ)=.5*HR(II)+.5*HR(JJ)
239 FOR KK = 1 TO 30
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 29
312 FOR J88=IW+1 TO 30
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 30
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-90000! 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),A(25)
1906 PRINT A(26),A(27),A(28),A(29),A(30)
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=-31995 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

21   30   13   2   29
25   14   6   16   17
12   27   18   3   23
9   24  22  7   4
15   20   19   26  11
28   10   1   5   8
-89930   -31995

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 for the output through JJJJ= -31995 was 21 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] 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

[17] 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.
 
[18] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems.  Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.     

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

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

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

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

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

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

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

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

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

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

[29] 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/

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

[31] 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/

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