Substance

The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with a Nonlinear Equality Constraint

Jsun Yui Wong

The computer program listed below seeks to solve Example 11 of Ryoo and Sahinidis [23, p. 564].                      
Line 263 through line 328 partly describe the problem.

Line 263 and line 265 show two dominoes.  When X(3) is optimal, X(1) is optimal; see line 263 and line 265.

0 REM DEFDBL A-Z
1 REM   DEFINT A,X
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),LHS(44),PLHS(44),LB(22),UB(22)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
76 LB(1)=0:LB(2)=0:LB(3)=100
78 UB(1)=34:UB(2)=17:UB(3)=300
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-7E+30
101 A(1)=LB(1)+(RND*34)
102 A(2)=LB(2)+(RND*17)
103 A(3)=LB(3)+(RND*200)
126 IMAR=10+FIX(RND*1500)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 3
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
153  B=1+FIX(RND*3)
156  IF RND<.25 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.33 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(1-RND*2)*(RND^(RND*7) )*A(B)
157 REM  IF RND<.25 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.33 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(1-RND*2)*(RND^(RND*7) )*(A(B)+.01)
158 REM    IF RND<.5 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE      X(B)=CINT(A(B))+FIX(1+RND*3)
263 X(3)= ( -600*X(2)+15000)  / 50
265 X(1)=    (   -5000+50*X(3)    )/(   600-X(3)       )
281 FOR J78=1 TO 3
282 IF X(J78)<LB(J78)  THEN 1670
283 NEXT J78
285 IF  X(1)>34 THEN 1670
287 IF  X(2)>17 THEN 1670
289 IF  X(3)>300 THEN 1670
328 PDU=-35* X(1)^.6-35*X(2)^.6
466 P=PDU
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 3
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 REM    IF M<3 THEN 1999
1904 PRINT A(1),A(2),A(3),M,JJJJ
1906 REM   PRINT A(6),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run via basica/D of Microsoft's GW-BASIC 3.11 interpreter for DOS.  The complete output through JJJJ=-31998 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

2.343751E-05   16.66665   100.0002   -189.3699
-32000

0   16.66667   100   -189.3116   -31999

0   16.66667   100   -189.3116   -31998

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 from JJJJ=-32000 through JJJJ=-31998 was two 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] 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] Jerome Bracken, Garth P. McCormick, Selected Applications of Nonlinear Programming.  New York: John Wiley and Sons, Inc., 1968.

[9] R. C. Carlson and G. L. Nemhauser, Scheduling To Minimize Interaction Cost.  Operations Research, Vol. 14, No. 1 (Jan. - Feb., 1966), pp. 52-58.

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

[11] C. A. Floudas, P. M. Pardalos, A Collection of Test Problems for Constrained Global Optimization Algorithms.  Springer-Verlag, 1990.

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

[14] David M. Himmelblau, Applied Nonlinear Programming.  New York: McGraw-Hill Book Company, 1972.

[15] Willi Hock, Klaus Schittkowski, Test Examples for Nonlinear Programming Codes.  Berlin: Springer-Verlag, 1981.

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

[17] Philipp Hungerlaender (April 2012), Single-Row Equidistant Facility Layout as a Special Case of Single-Row Facility Layout.  Retrieved from www.optimization-online.org./DB_HTML/2012/04/3432.html

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

[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] H. S. Ryoo, N. V. Sahinidis, Global Optimization of Nonconvex NLPs and MINLPs with Applications in Process Design.  Computers and Chemical Engineering, Vol. 19, No. 5, pp. 551-566, 1995.

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

[25] G. Stephanopoulos, A. W. Westerberg, The Use of Hestenes' Method of Multipliers to Resolve
Dual Gaps in Engineering System Optimization.  Journal of Optimization Theory and Applications,  Vol.15, No. 3, pp. 285-309, 1975.

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

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

[28] Jsun Yui Wong (2012, April 24).  The Domino Method of General Integer Nonlinear Programming  Applied to Problem 10 of Lawler and Bell.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/4/24/

[29] Jsun Yui Wong (2012, September 27).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a Linear Ordering Problem with 22 Facilities.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/9/27/

The Domino Method of General Integer Nonlinear Programming Applied to a Chemical Equilibrium Problem

Jsun Yui Wong

The computer program listed below seeks to solve Example 6 of Ryoo and Sahinidis [23, p. 564].                      
Line 262 through line 328 partly describe the problem.

Line 262, line 263, and line 269 show a sequence of dominoes.  3*X(1) triggers the domino process.

0 REM DEFDBL A-Z
1 REM   DEFINT A,X
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),LHS(44),PLHS(44),LB(22),UB(22)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
76 LB(1)=0:LB(2)=0:LB(3)=0
78 UB(1)=12.5:UB(2)=37.5:UB(3)=50
79 REM  UB(4)=2
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-7E+30
101 A(1)=LB(1)+(RND*34)
102    A(2)=LB(2)+(RND*17)
103    A(3)=LB(3)+(RND*200)
126 IMAR=10+FIX(RND*1500)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 3
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
153  B=1+FIX(RND*3)
156  IF RND<.25 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.33 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(1-RND*2)*(RND^(RND*7) )*A(B)
157 REM  IF RND<.25 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.33 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(1-RND*2)*(RND^(RND*7) )*(A(B)+.01)
158 REM    IF RND<.5 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE      X(B)=CINT(A(B))+FIX(1+RND*3)
262 X(2)=3*X(1)
263 X(3)=  50   -X(1)-X(2)
269  X(4)=   .000169-( X(3)^2 )/( X(1)*X(2)^3   )
281 FOR J78=1 TO 3
282 IF X(J78)<LB(J78)  THEN 1670
283 NEXT J78
285 IF  X(1)>12.5 THEN 1670
287 IF  X(2)>37.5 THEN 1670
289 IF  X(3)>50 THEN 1670
315    IF ABS(X(4)) >0 THEN PX=-999999999#*ABS(X(4))  ELSE PX=0
328 PDU=PX
466 P=PDU
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 3
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889    IF M<-1 THEN 1999
1904 PRINT A(1),A(2),A(3),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run via basica/D of Microsoft's GW-BASIC 3.11 interpreter for DOS.  The complete output through JJJJ=-31993 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

10.60186   31.80557   7.592575   -2.910383E-02
-32000

10.60186   31.80557   7.592575   -2.910383E-02
-31999

10.60186   31.80557   7.592572   -.2182787   -31998

10.60186   31.80557   7.592575   -2.910383E-02
-31996

Division by zero

Overflow

Overflow

10.60186   31.80557   7.592575   -2.910383E-02
-31993

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 from JJJJ=-32000 through JJJJ=-31993 was two 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] 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] Jerome Bracken, Garth P. McCormick, Selected Applications of Nonlinear Programming.  New York: John Wiley and Sons, Inc., 1968.

[9] R. C. Carlson and G. L. Nemhauser, Scheduling To Minimize Interaction Cost.  Operations Research, Vol. 14, No. 1 (Jan. - Feb., 1966), pp. 52-58.

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

[11] C. A. Floudas, P. M. Pardalos, A Collection of Test Problems for Constrained Global Optimization Algorithms.  Springer-Verlag, 1990.

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

[14] David M. Himmelblau, Applied Nonlinear Programming.  New York: McGraw-Hill Book Company, 1972.

[15] Willi Hock, Klaus Schittkowski, Test Examples for Nonlinear Programming Codes.  Berlin: Springer-Verlag, 1981.

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

[17] Philipp Hungerlaender (April 2012), Single-Row Equidistant Facility Layout as a Special Case of Single-Row Facility Layout.  Retrieved from www.optimization-online.org./DB_HTML/2012/04/3432.html

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

[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] H. S. Ryoo, N. V. Sahinidis, Global Optimization of Nonconvex NLPs and MINLPs with Applications in Process Design.  Computers and Chemical Engineering, Vol. 19, No. 5, pp. 551-566, 1995.

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

[25] G. Stephanopoulos, A. W. Westerberg, The Use of Hestenes' Method of Multipliers to Resolve
Dual Gaps in Engineering System Optimization.  Journal of Optimization Theory and Applications,  Vol.15, No. 3, pp. 285-309, 1975.

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

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

[28] Jsun Yui Wong (2012, April 24).  The Domino Method of General Integer Nonlinear Programming  Applied to Problem 10 of Lawler and Bell.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/4/24/

[29] Jsun Yui Wong (2012, September 27).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a Linear Ordering Problem with 22 Facilities.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/9/27/

The Domino Method of General Integer Nonlinear Programming Applied to Insulated Steel Tank Design

Jsun Yui Wong

The computer program listed below seeks to solve Example 4 of Ryoo and Sahinidis [23, p. 564].               
Line 160 through line 328 partly describe the problem.

The fall of domino one, X(3), is followed immediately by the fall of domino two, X(2); see line 160 and line  262.

0 REM DEFDBL A-Z
1 REM   DEFINT A,X
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),LHS(44),PLHS(44),LB(22),UB(22)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
76 LB(1)=0:LB(2)=14.7:LB(3)=-459.67
77 LB(4)=0
78 UB(1)=15.1:UB(2)=94.2:UB(3)=80
79 REM  UB(4)=2
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-7E+30
101 A(1)=LB(1)+(RND*15.1)
102 A(2)=LB(2)+(RND*79.5)
103 A(3)=LB(3)+(RND*539.67)
104 A(4)=LB(4)+(RND*1000)
126 IMAR=10+FIX(RND*1500)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 4
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
153  B=1+FIX(RND*4)
156  IF RND<.25 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.33 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(1-RND*2)*(RND^(RND*7) )*A(B)
157 REM  IF RND<.25 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.33 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(1-RND*2)*(RND^(RND*7) )*(A(B)+.01)
158 REM    IF RND<.5 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE      X(B)=CINT(A(B))+FIX(1+RND*3)
160 X(3)=   ( 144*80-X(1)*X(4)    )/144
262 X(2)=EXP(   ( -3950/( X(3)+460)   )   +11.86              )
281 FOR J78=1 TO 4
282 IF X(J78)<LB(J78)  THEN 1670
283 NEXT J78
285 IF  X(1)>15.1 THEN 1670
287 IF  X(2)>94.2 THEN 1670
289 IF  X(3)>80 THEN 1670
328 PDU=-400*X(1)^.9    -1000    -22*(  X(2)-14.7   )^1.2    -X(4)
466 P=PDU
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 4
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-5400 THEN 1999
1904 PRINT A(1),A(2),A(3),A(4),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run via basica/D of Microsoft's GW-BASIC 3.11 interpreter for DOS.  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.

5.957262   29.4046   5.86518   1792   -5339.252
-32000

0   94.17781   80   0   -5194.864
-31999

5.957302   29.39025   5.838352   1792.637   -5339.252
-31998

5.959651   29.3887   5.835456   1792   -5339.253
-31997

5.952299   29.39341   5.844279   1794   -5339.252
-31996

9.711648E-08   94.17781   80   1.51577E-04  
-5194.864   -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 from JJJJ=-32000 through JJJJ=-31995 was one second.

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] Jerome Bracken, Garth P. McCormick, Selected Applications of Nonlinear Programming.  New York: John Wiley and Sons, Inc., 1968.

[9] R. C. Carlson and G. L. Nemhauser, Scheduling To Minimize Interaction Cost.  Operations Research, Vol. 14, No. 1 (Jan. - Feb., 1966), pp. 52-58.

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

[11] C. A. Floudas, P. M. Pardalos, A Collection of Test Problems for Constrained Global Optimization Algorithms.  Springer-Verlag, 1989.

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

[14] David M. Himmelblau, Applied Nonlinear Programming.  New York: McGraw-Hill Book Company, 1972.

[15] Willi Hock, Klaus Schittkowski, Test Examples for Nonlinear Programming Codes.  Berlin: Springer-Verlag, 1981.

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

[17] Philipp Hungerlaender (April 2012), Single-Row Equidistant Facility Layout as a Special Case of Single-Row Facility Layout.  Retrieved from www.optimization-online.org./DB_HTML/2012/04/3432.html

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

[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] H. S. Ryoo, N. V. Sahinidis, Global Optimization of Nonconvex NLPs and MINLPs with Applications in Process Design.  Computers and Chemical Engineering, Vol. 19, No. 5, pp. 551-566, 1995.

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

[25] G. Stephanopoulos, A. W. Westerberg, The Use of Hestenes' Method of Multipliers to Resolve
Dual Gaps in Engineering System Optimization.  Journal of Optimization Theory and Applications,  Vol.15, No. 3, pp. 285-309, 1975.

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

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

[28] Jsun Yui Wong (2012, April 24).  The Domino Method of General Integer Nonlinear Programming  Applied to Problem 10 of Lawler and Bell.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/4/24/

[29] Jsun Yui Wong (2012, September 27).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a Linear Ordering Problem with 22 Facilities.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/9/27/

The Domino Method of General Integer Nonlinear Programming Applied to a Small Nonlinear Programming Test Problem from the Literature

Jsun Yui Wong

The computer program listed below seeks to solve Test Problem 4 of the nonlinear programming chapter of Floudas and Pardalos [11, pp. 28-29].  The source of this problem is Stephanopoulos and Westerberg [24, pp. 305-307].  Line 263 through line 328 partly describe the problem.

Line 263, line 265, and line 267 show a sequence of dominoes.  3*X(1)+3 triggers the domino process; see line 263.  X(5) and X(6) are slack variables; see line 265 and line 267.

0 REM DEFDBL A-Z
1 REM   DEFINT A,X
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),LHS(44),PLHS(44),LB(22),UB(22)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
76 LB(1)=0:LB(2)=0:LB(3)=0
77 LB(4)=0
78 UB(1)=3:UB(2)=50:UB(3)=50
79 UB(4)=2
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-7E+30
101 A(1)=LB(1)+(RND*3)
102    A(2)=LB(2)+(RND*50)
103    A(3)=LB(3)+(RND*50)
104 A(4)=LB(4)+(RND*2)
126 IMAR=10+FIX(RND*1500)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 4
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
153  B=1+FIX(RND*4)
156  IF RND<.25 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.33 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(1-RND*2)*(RND^(RND*7) )*A(B)
157 REM  IF RND<.25 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.33 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(1-RND*2)*(RND^(RND*7) )*(A(B)+.01)
158 REM    IF RND<.5 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE      X(B)=CINT(A(B))+FIX(1+RND*3)
263 X(2)=3*X(1)+3
265 X(5)=4-X(1)-2*X(3)
267 X(6)=4-X(2)-X(4)
281 FOR J78=1 TO 4
282 IF X(J78)<LB(J78)  THEN 1670
283 NEXT J78
285 IF  X(1)>3 THEN 1670
287 IF  X(4)>2 THEN 1670
316 IF X(5)<0 THEN PX(5)=999999999#*X(5) ELSE PX(5)=0
317 IF X(6)<0 THEN PX(6)=999999999#*X(6) ELSE PX(6)=0
328 PDU=- X(1)^.6-2*X(2)^.6-2*X(3)+2*X(2)+X(4)+PX(5)+PX(6)
466 P=PDU
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 6
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889  IF M<3 THEN 1999
1904 PRINT A(1),A(2),A(3),A(4),A(5)
1906 PRINT A(6),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run via basica/D of Microsoft's GW-BASIC 3.11 interpreter for DOS.  The complete output through JJJJ=-31989 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

0   3   5.029215E-08   1
4
0   3.133636   -31999

0   3   0   .9999955   4
4.529953E-06   3.133631   -31998

0   3   3.268906E-08   1
4
0   3.133636   -31993

0   3   0   .9999999   4
5.960465E-08   3.133636   -31991

2.428132E-12   3   0   .9999842
4
1.573563E-05   3.13362   -31990

0   3   0   1   4
0   3.133636   -31989

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 from JJJJ=-32000 through JJJJ=-31989 was two 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] 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] Jerome Bracken, Garth P. McCormick, Selected Applications of Nonlinear Programming.  New York: John Wiley and Sons, Inc., 1968.

[9] R. C. Carlson and G. L. Nemhauser, Scheduling To Minimize Interaction Cost.  Operations Research, Vol. 14, No. 1 (Jan. - Feb., 1966), pp. 52-58.

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

[11] C. A. Floudas, P. M. Pardalos, A Collection of Test Problems for Constrained Global Optimization Algorithms.  Springer-Verlag, 1989.

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

[14] David M. Himmelblau, Applied Nonlinear Programming.  New York: McGraw-Hill Book Company, 1972.

[15] Willi Hock, Klaus Schittkowski, Test Examples for Nonlinear Programming Codes.  Berlin: Springer-Verlag, 1981.

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

[17] Philipp Hungerlaender (April 2012), Single-Row Equidistant Facility Layout as a Special Case of Single-Row Facility Layout.  Retrieved from www.optimization-online.org./DB_HTML/2012/04/3432.html

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

[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] Donald M. Simmons (1969), One-Dimensional Space Allocation: An Ordering Algorithm.     Operations Research, Vol. 17, No. 5 (Sep. - Oct., 1969), pp. 812-826.

[24] G. Stephanopoulos, A. W. Westerberg, The Use of Hestenes' Method of Multipliers to Resolve
Dual Gaps in Engineering System Optimization.  Journal of Optimization Theory and Applications,  Vol.15, No. 3, pp. 285-309, 1975.

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

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

[27] Jsun Yui Wong (2012, April 24).  The Domino Method of General Integer Nonlinear Programming  Applied to Problem 10 of Lawler and Bell.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/4/24/

[28] Jsun Yui Wong (2012, September 27).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a Linear Ordering Problem with 22 Facilities.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/9/27/

The Domino Method of General Integer Nonlinear Programming Applied to Two Small Test Problems from the Literature

Jsun Yui Wong

The two computer programs listed below seek to solve Test Problem 6 and Test Problem 7 on pages 30-31 and on pages 31-32 of Floudas and Pardalos [11], respectively.

Test Problem 6 of Chapter 4 of Floudas and Pardalos

Line 255 through line 328 partly describe this problem 6.  In this problem the fall/optimization of domino one/X(3) is followed by the fall/optimization of domino two/X(4).  These two variables are slack variables. 

0 REM DEFDBL A-Z
1 REM   DEFINT A,X
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),LHS(44),PLHS(44),LB(22),UB(22)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
76 LB(1)=0:LB(2)=0
78 UB(1)=3:UB(2)=4
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-7E+30
101 A(1)=LB(1)+(RND*3)
102 A(2)=LB(2)+(RND*4)
126 IMAR=10+FIX(RND*1500)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 2
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
153  B=1+FIX(RND*2)
156  IF RND<.25 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.33 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(1-RND*2)*(RND^(RND*7) )*A(B)
158 REM    IF RND<.5 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE      X(B)=CINT(A(B))+FIX(1+RND*3)
255 X(3)= -X(2)   +2*X(1)^4-8*X(1)^3+8*X(1)^2+2
257 X(4)= -X(2)   +4*X(1)^4-32*X(1)^3+88*X(1)^2-96*X(1)+36
281 FOR J78=1 TO 2
282 IF X(J78)<LB(J78)  THEN 1670
283 NEXT J78
285 IF  X(1)>3    THEN 1670
287 IF  X(2)>4 THEN 1670
311 IF X(3)<0 THEN PX(3)=999999999#*X(3) ELSE PX(3)=0
313 IF X(4)<0 THEN PX(4)=999999999#*X(4) ELSE PX(4)=0
328 PDU= X(1)+X(2)+PX(3)     +PX(4)
466 P=PDU
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 4
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889   IF M<5.5 THEN 1999
1903 PRINT A(1),A(2),A(3),A(4)
1904 PRINT M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run via basica/D of Microsoft's GW-BASIC 3.11 interpreter for DOS.  The complete output through JJJJ=-30322 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

2.331576   3.168781   2.656937E-02   0
5.500358   -31892

2.330446   3.174179   1.189041E-02   0
5.504626   -31211

2.330385   3.174458   .0111084   0
5.504843   -30738

2.331024   3.171436   1.937103E-02   0
5.502461   -30687

2.331447   3.169457   .0248375   0
5.500904   -30648

2.329783   3.177286   3.353119E-03   0
5.507069   -30322

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 from JJJJ=-32000 through JJJJ=-30322 was 125 seconds.

Test Problem 7 of Chapter 4 of Floudas and Pardalos

Line 261 through line 328 partly describe this problem.  The source of this problem is Soland [24].

0 REM DEFDBL A-Z
1 REM   DEFINT A,X
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),LHS(44),PLHS(44),LB(22),UB(22)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
76 LB(1)=0:LB(2)=0
78 UB(1)=2:UB(2)=3
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-7E+30
101 A(1)=LB(1)+(RND*2)
102 A(2)=LB(2)+(RND*3)
126 IMAR=10+FIX(RND*1500)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 2
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
153  B=1+FIX(RND*2)
156  IF RND<.25 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.33 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(1-RND*2)*(RND^(RND*7) )*A(B)
158 REM    IF RND<.5 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE      X(B)=CINT(A(B))+FIX(1+RND*3)
261 X(2)=    -2*X(1)^4+2
281 FOR J78=1 TO 2
282 IF X(J78)<LB(J78)  THEN 1670
283 NEXT J78
285 IF  X(1)>2    THEN 1670
287 IF  X(2)>3 THEN 1670
328 PDU= 12*X(1)+7*X(2)-X(2)^2
466 P=PDU
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 2
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<10 THEN 1999
1904 PRINT A(1),A(2),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run via basica/D of Microsoft's GW-BASIC 3.11 interpreter for DOS.  The complete output through JJJJ=-31998 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

.7176762   1.469428   16.73889   -32000

.7172239   1.470765   16.73889   -31999

.7174568   1.470077   16.7389   -31998

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 from JJJJ=-32000 through JJJJ=-31998 was one second.

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] Jerome Bracken, Garth P. McCormick, Selected Applications of Nonlinear Programming.  New York: John Wiley and Sons, Inc., 1968.

[9] R. C. Carlson and G. L. Nemhauser, Scheduling To Minimize Interaction Cost.  Operations Research, Vol. 14, No. 1 (Jan. - Feb., 1966), pp. 52-58.

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

[11] C. A. Floudas, P. M. Pardalos, A Collection of Test Problems for Constrained Global Optimization Algorithms.  Springer-Verlag, 1990.

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

[14] David M. Himmelblau, Applied Nonlinear Programming.  New York: McGraw-Hill Book Company, 1972.

[15] Willi Hock, Klaus Schittkowski, Test Examples for Nonlinear Programming Codes.  Berlin: Springer-Verlag, 1981.

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

[17] Philipp Hungerlaender (April 2012), Single-Row Equidistant Facility Layout as a Special Case of Single-Row Facility Layout.  Retrieved from www.optimization-online.org./DB_HTML/2012/04/3432.html

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

[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] Donald M. Simmons (1969), One-Dimensional Space Allocation: An Ordering Algorithm.     Operations Research, Vol. 17, No. 5 (Sep. - Oct., 1969), pp. 812-826.

[24] R. M. Soland (1971), An Algorithm for Separable Nonconvex Programming Problems ii: Nonconvex Constraints.  Management Science, 17(11), pp. 759-773, 1971.

[25] G. Stephanopoulos, A. W. Westerberg (1975), The Use of Hestenes' Method of Multipliers to Resolve Dual Gaps in Engineering System Optimization.  Journal of Optimization Theory and Applications,  Vol.15, No. 3, pp. 285-309, 1975.

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

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

[28] Jsun Yui Wong (2012, April 24).  The Domino Method of General Integer Nonlinear Programming  Applied to Problem 10 of Lawler and Bell.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/4/24/

[29] Jsun Yui Wong (2012, September 27).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a Linear Ordering Problem with 22 Facilities.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/9/27/

The Domino Method of General Integer Nonlinear Programming Applied to a Small Test Problem from the Literature

Jsun Yui Wong

The computer program listed below seeks to solve Test Problem 3 on page 28 of Floudas and Pardalos [11].  The source of this problem is Stephanopoulos and Westerberg [24, pp. 304-305]. Line 263 through line 328 partly describe the problem.

Line 263 through line 267 show a sequence of dominoes.  3*X(1)+3*X(3) triggers the domino process; see line 263.  X(5) and X(6) are slack variables; see line 265 and line 267.

0 REM DEFDBL A-Z
1 REM   DEFINT A,X
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),LHS(44),PLHS(44),LB(22),UB(22)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
76 LB(1)=0:LB(2)=0:LB(3)=0
77 LB(4)=0
78 UB(1)=3:UB(2)=50:UB(3)=50
79 UB(4)=1
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-7E+30
101 A(1)=LB(1)+(RND*3)
102    A(2)=LB(2)+(RND*50)
103    A(3)=LB(3)+(RND*50)
104 A(4)=LB(4)+(RND*1)
126 IMAR=10+FIX(RND*1500)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 4
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
153  B=1+FIX(RND*4)
156  IF RND<.25 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.33 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(1-RND*2)*(RND^(RND*7) )*A(B)
158 REM    IF RND<.5 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE      X(B)=CINT(A(B))+FIX(1+RND*3)
263 X(2)=3*X(1)+3*X(3)
265 X(5)=4-X(1)-2*X(3)
267 X(6)=4-X(2)-2*X(4)
281 FOR J78=1 TO 4
282 IF X(J78)<LB(J78)  THEN 1670
283 NEXT J78
285 IF  X(1)>3 THEN 1670
287 IF  X(4)>1 THEN 1670
316 IF X(5)<0 THEN PX(5)=999999999#*X(5) ELSE PX(5)=0
317 IF X(6)<0 THEN PX(6)=999999999#*X(6) ELSE PX(6)=0
328 PDU=- X(1)^.6-X(2)^.6+6*X(1)+4*X(3)-3*X(4) +PX(5)+PX(6)
466 P=PDU
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 6
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889  IF M<4.5 THEN 1999
1904 PRINT A(1),A(2),A(3),A(4),A(5)
1905 PRINT A(6)
1906 PRINT M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run via basica/D of Microsoft's GW-BASIC 3.11 interpreter for DOS.  The complete output through JJJJ=-31981 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

1.333333   3.999998   0   3.996583E-08
2.666668
2.304254E-06
4.514199   -31995

1.333291   3.999873   0   0   2.666709
1.275539E-04
4.514014   -31990

1.333333   3.999999   0   4.948405E-08
2.666667
8.547062E-07
4.5142   -31981

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 from JJJJ=-32000 through JJJJ=-31981 was three 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] 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] Jerome Bracken, Garth P. McCormick, Selected Applications of Nonlinear Programming.  New York: John Wiley and Sons, Inc., 1968.

[9] R. C. Carlson and G. L. Nemhauser, Scheduling To Minimize Interaction Cost.  Operations Research, Vol. 14, No. 1 (Jan. - Feb., 1966), pp. 52-58.

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

[11] C. A. Floudas, P. M. Pardalos, A Collection of Test Problems for Constrained Global Optimization Algorithms.  Springer-Verlag, 1990.

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

[14] David M. Himmelblau, Applied Nonlinear Programming.  New York: McGraw-Hill Book Company, 1972.

[15] Willi Hock, Klaus Schittkowski, Test Examples for Nonlinear Programming Codes.  Berlin: Springer-Verlag, 1981.

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

[17] Philipp Hungerlaender (April 2012), Single-Row Equidistant Facility Layout as a Special Case of Single-Row Facility Layout.  Retrieved from www.optimization-online.org./DB_HTML/2012/04/3432.html

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

[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] Donald M. Simmons (1969), One-Dimensional Space Allocation: An Ordering Algorithm.     Operations Research, Vol. 17, No. 5 (Sep. - Oct., 1969), pp. 812-826.

[24] G. Stephanopoulos, A. W. Westerberg, The Use of Hestenes' Method of Multipliers to Resolve
Dual Gaps in Engineering System Optimization.  Journal of Optimization Theory and Applications,  Vol.15, No. 3, pp. 285-309, 1975.

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

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

[27] Jsun Yui Wong (2012, April 24).  The Domino Method of General Integer Nonlinear Programming  Applied to Problem 10 of Lawler and Bell.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/4/24/

[28] Jsun Yui Wong (2012, September 27).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a Linear Ordering Problem with 22 Facilities.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/9/27/

The Domino Method of General Integer Nonlinear Programming Applied to a Test Problem from the Literature

Jsun Yui Wong

The computer program listed below seeks to solve Test Problem 5 on pages 29-30 of Floudas and Pardalos [11].  The source of this problem is Stephanopoulos and Westerberg [24, p. 307]. Line 261 through line 328 partly describe the problem.

Line 261 through line 271 show a sequence of dominoes.  X(6)/4 triggers the domino process; see line 261.

0 REM DEFDBL A-Z
1 REM   DEFINT A,X
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),LHS(44),PLHS(44),LB(22),UB(22)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
76 LB(1)=0:LB(2)=0:LB(3)=0
77 LB(4)=0:LB(5)=0:LB(6)=0
78 UB(1)=3:UB(2)=50:UB(3)=4
79 UB(4)=50:UB(5)=2:UB(6)=50
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-7E+30
101 A(1)=LB(1)+(RND*3)
102 A(2)=LB(2)+(RND*50)
103 A(3)=LB(3)+(RND*4)
104 A(4)=LB(4)+(RND*50)
105 A(5)=LB(5)+(RND*2)
106 A(6)=LB(6)+(RND*50)
126 IMAR=10+FIX(RND*1500)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 6
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
153  B=1+FIX(RND*6)
156  IF RND<.25 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.33 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(1-RND*2)*(RND^(RND*7) )*A(B)
158 REM    IF RND<.5 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE      X(B)=CINT(A(B))+FIX(1+RND*3)
261 X(4)=X(6)/4
263 X(2)=3*X(1)+3*X(4)
265 X(7)=4-X(1)-2*X(4)
267 X(8)=4-X(2)-X(5)
269 X(3)=2*X(2)+2*X(5)
271 X(9)=6-X(3)-X(6)
281 FOR J78=1 TO 6
282 IF X(J78)<LB(J78)  THEN 1670
283 NEXT J78
285 IF  X(1)>3 THEN 1670
287 IF  X(5)>2 THEN 1670
288 IF  X(3)>4 THEN 1670
316 IF X(7)<0 THEN PX(7)=999999999#*X(7) ELSE PX(7)=0
317 IF X(8)<0 THEN PX(8)=999999999#*X(8) ELSE PX(8)=0
318 IF X(9)<0 THEN PX(9)=999999999#*X(9) ELSE PX(9)=0
328 PDU=- X(1)^.6-X(2)^.6-X(3)^.4-2*X(4)-5*X(5)+4*X(3)+X(6) +PX(7)+PX(8)+PX(9)
466 P=PDU
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 9
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<13.3 THEN 1999
1904 PRINT A(1),A(2),A(3),A(4),A(5)
1905 PRINT A(6),A(7),A(8),A(9)
1906 PRINT M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run via basica/D of Microsoft's GW-BASIC 3.11 interpreter for DOS.  The complete output through JJJJ=-19442 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

.1689649   2   4   .4977017   0
1.990807   2.835632   2   9.193182E-03
13.39449   -31997

.1665382   1.999843   3.999686   .5000762   0
2.000305   2.83331   2.000157   9.059906E-06
13.40109   -27948

.16661458   1.999375   3.998749   .5003124   0
2.00125   2.83323   2.000625   1.192093E-06
13.39867   -19442

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 from JJJJ=-32000 through JJJJ=-19442 was five 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] Jerome Bracken, Garth P. McCormick, Selected Applications of Nonlinear Programming.  New York: John Wiley and Sons, Inc., 1968.

[9] R. C. Carlson and G. L. Nemhauser, Scheduling To Minimize Interaction Cost.  Operations Research, Vol. 14, No. 1 (Jan. - Feb., 1966), pp. 52-58.

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

[11] C. A. Floudas, P. M. Pardalos, A Collection of Test Problems for Constrained Global Optimization Algorithms.  Springer-Verlag, 1990.

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

[14] David M. Himmelblau, Applied Nonlinear Programming.  New York: McGraw-Hill Book Company, 1972.

[15] Willi Hock, Klaus Schittkowski, Test Examples for Nonlinear Programming Codes.  Berlin: Springer-Verlag, 1981.

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

[17] Philipp Hungerlaender (April 2012), Single-Row Equidistant Facility Layout as a Special Case of Single-Row Facility Layout.  Retrieved from www.optimization-online.org./DB_HTML/2012/04/3432.html

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

[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] Donald M. Simmons (1969), One-Dimensional Space Allocation: An Ordering Algorithm.     Operations Research, Vol. 17, No. 5 (Sep. - Oct., 1969), pp. 812-826.

[24] G. Stephanopoulos, A. W. Westerberg, The Use of Hestenes' Method of Multipliers to Resolve
Dual Gaps in Engineering System Optimization.  Journal of Optimization Theory and Applications,  Vol.15, No. 3, pp. 285-309, 1975.

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

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

[27] Jsun Yui Wong (2012, April 24).  The Domino Method of General Integer Nonlinear Programming  Applied to Problem 10 of Lawler and Bell.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/4/24/

[28] Jsun Yui Wong (2012, September 27).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a Linear Ordering Problem with 22 Facilities.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/9/27/

An Illustration of the Domino Method of General Integer Nonlinear Programming

Jsun Yui Wong

To illustrate the domino process, the computer program listed below uses Problem 1 on pages 393-394 of Himmelblau [13].  The source of this problem is Bracken and McCormick [8, p. 19]. Line 291 through line 324 partly describe the problem.

The fall/optimization of domino one/X(1) helps the fall/optimization of domino 2/X(3) because the number for X(1) and the number for X(2) determine the number for X(3); see line 291 and line 292, respectively.  In the following computer program it is not hard for domino one to fall because that only depends on X(2).  (2*X(2)-1) triggers the domino process; see line 291.  Here X(3) is the slack variable.

0 REM DEFDBL A-Z
1 REM   DEFINT A,X
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),LHS(44),PLHS(44),LB(22),UB(22)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
76 LB(1)=0:LB(2)=0
78 UB(1)=50:UB(2)=50
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-7E+30
101 A(1)=LB(1)+FIX(RND*51)
102 A(2)=LB(2)+FIX(RND*51)
126 IMAR=10+FIX(RND*1500)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 2
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
153  B=1+FIX(RND*2)
156   IF RND<.25 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.33 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(1-RND*2)*(RND^(RND*7) )*A(B)
158 REM    IF RND<.5 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE      X(B)=CINT(A(B))+FIX(1+RND*3)
251 FOR J78=1 TO 2
252 IF X(J78)<LB(J78)  THEN 1670
253 NEXT J78
254 FOR J79=1 TO 2
255 IF  X(J79)>UB(J79) THEN 1670
256 NEXT J79
291 X(1)=2*X(2)-1
292 X(3)=-X(1)^2/4-X(2)^2+1
308 IF X(3)<0 THEN PLHS(3)=999999!*X(3) ELSE PLHS(3)=0
324 PDU=-(  X(1)-2)^2-(X(2)-1)^2          +PLHS(3)
466 P=PDU
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 3
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-2 THEN 1999
1904 PRINT A(1),A(2),A(3),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run via basica/D of Microsoft's GW-BASIC 3.11 interpreter for DOS.  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.

.8228754   .9114377   3.576279E-07   -1.393466
-31996

.8228755   .9114378   2.384186E-07   -1.393465
-31992

.8228756   .9114378   5.960465E-08   -1.393465
-31990

.8228621   .9114311   1.788139E-05   -1.393498
-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 from JJJJ=-32000 through JJJJ=-31987 was two 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] 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] Jerome Bracken, Garth P. McCormick, Selected Applications of Nonlinear Programming.  New York: John Wiley and Sons, Inc., 1968.

[9] R. C. Carlson and G. L. Nemhauser, Scheduling To Minimize Interaction Cost.  Operations Research, Vol. 14, No. 1 (Jan. - Feb., 1966), pp. 52-58.

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

[13] David M. Himmelblau, Applied Nonlinear Programming.  New York: McGraw-Hill Book Company, 1972.

[14] Willi Hock, Klaus Schittkowski, Test Examples for Nonlinear Programming Codes.  Berlin: Springer-Verlag, 1981.

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

[16] Philipp Hungerlaender (April 2012), Single-Row Equidistant Facility Layout as a Special Case of Single-Row Facility Layout.  Retrieved from www.optimization-online.org./DB_HTML/2012/04/3432.html

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

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

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

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

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

[25] Jsun Yui Wong (2012, April 24).  The Domino Method of General Integer Nonlinear Programming  Applied to Problem 10 of Lawler and Bell.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/4/24/

[26] Jsun Yui Wong (2012, September 27).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a Linear Ordering Problem with 22 Facilities.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/9/27/

A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to an Integer Nonlinear Programming Problem, Second Edition

Jsun Yui Wong

Based on the computer program of the earlier edition, the following computer program seeks to solve Problem 10 on page 1108 of Lawler and Bell [30].  Line 291 through line 323 partly describe the problem.  The nonlinear objective function of line 323 is noteworthy. 

In this paper X(9) through X(18) are slack variables.

0 REM DEFDBL A-Z
1 DEFINT A,X
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),LHS(44),PLHS(44),LB(22),UB(22)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
76 LB(1)=0:LB(2)=0:LB(3)=0:LB(4)=0:LB(5)=0
77 LB(6)=0:LB(7)=0:LB(8)=0
78 UB(1)=7:UB(2)=15:UB(3)=7:UB(4)=7:UB(5)=15
79 UB(6)=7:UB(7)=15:UB(8)=7
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-7E+30
101 A(1)=LB(1)+FIX(RND*8)
102 A(2)=LB(2)+FIX(RND*16)
103 A(3)=LB(3)+FIX(RND*8)
104 A(4)=LB(4)+FIX(RND*8)
105 A(5)=LB(5)+FIX(RND*16)
106 A(6)=LB(6)+FIX(RND*8)
107 A(7)=LB(7)+FIX(RND*16)
108 A(8)=LB(8)+FIX(RND*8)
126 IMAR=10+FIX(RND*1500)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 8
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
153  B=1+FIX(RND*8)
156 REM  IF RND<.25 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.33 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(1-RND*2)*(RND^(RND*7) )*A(B)
158 IF RND<.5 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE      X(B)=CINT(A(B))+FIX(1+RND*3)
251 FOR J78=1 TO 8
252 IF X(J78)<LB(J78)  THEN 1670
253 NEXT J78
254 FOR J79=1 TO 8
255 IF  X(J79)>UB(J79) THEN 1670
256 NEXT J79
291 X(9)=2*X(1)+2*X(4)+8*X(8)-12
292 X(10)=11*X(1)+7*X(4)+13*X(6)-41
293 X(11)=6*X(2)+9*X(4)*X(6)+5*X(7)-60
294 X(12)=3*X(2)+5*X(5)+7*X(8)-42
295 X(13)=6*X(2)*X(7)+9*X(3)+5*X(5)-53
296 X(14)=4*X(3)*X(7)+X(5)-13
297 REM FOR J42=1 TO 6
298 REM IF LHS(J42)<0 THEN PLHS(J42)=999999!*LHS(J42) ELSE PLHS(J42)=0
299 REM NEXT J42
301 X(15)=-2*X(1)-4*X(2)-7*X(4)-3*X(5)-X(7)+69
302 X(16)=-9*X(1)*X(8)-6*X(3)*X(5)-4*X(3)*X(7)+47
303 X(17)=-12*X(2)-8*X(2)*X(8)-2*X(3)*X(6)+73
304 X(18)=-X(3)-4*X(5)-2*X(6)-9*X(8)+31
307 FOR J43=9 TO 18
308 IF X(J43)<0 THEN PLHS(J43)=999999!*X(J43) ELSE PLHS(J43)=0
309 NEXT J43
315 LT=0
316 FOR J49=9 TO 18
317 LT=LT+PLHS(J49)
319 NEXT J49
323 PDU=-X(1)*X(2)*X(3)-X(1)*X(4)*X(5)-X(2)*X(4)*X(6)-X(2)*X(5)*X(7)-X(6)*X(7)*X(8)           +LT
466 P=PDU
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 18
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-111 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)
1912 PRINT M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run via basica/D of Microsoft's GW-BASIC 3.11 interpreter for DOS.  The complete output through JJJJ=-31860 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

5   4   1   1   6
3   2   0   0   60
1   0   34   1   16
3   19   0
-110   -31882

5   4   1   1   6
3   2   0   0   60
1   0   34   1   16
3   19   0
-110   -31876

5   4   1   1   6
3   2   0   0   60
1   0   34   1   16
3   19   0
-110   -31860

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 from JJJJ=-32000 through JJJJ=-31860 was 13 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] 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] R. C. Carlson and G. L. Nemhauser, Scheduling To Minimize Interaction Cost.  Operations Research, Vol. 14, No. 1 (Jan. - Feb., 1966), pp. 52-58.

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

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

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

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

[14] F. E. Davis, M. D. Devine, and R. P. Lutz, Scheduling Activities Among Conflicting Facilities To Minimize Conflict Cost.  Mathematical Programming 6 (1974) 224-228)

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

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

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

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

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

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

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

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

[23] Willi Hock, Klaus Schittkowski, Test Examples for Nonlinear Programming Codes.  Berlin: Springer-Verlag, 1981.

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

[25] Philipp Hungerlaender (April 2012), Single-Row Equidistant Facility Layout as a Special Case of Single-Row Facility Layout.  Retrieved from www.optimization-online.org./DB_HTML/2012/04/3432.html

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

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

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

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

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

[31] Sven Leyffer, "Deterministic Methods for Mixed Integer Nonlinear Programming," Ph. D. thesis, University of Dundee.  Dundee: December 1993.  (This thesis was obtained via Google search.)

[32] 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.
 
[33] 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.

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

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

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

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

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

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

[40] Tjark Vredeveld and Jan Karel Lenstra, On Local Search for the Generalized Graph Coloring Problem.  Operations Research Letters, 31 (2003) 28-34.

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

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

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

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

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

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

[47] Jsun Yui Wong (2012, April 24).  The Domino Method of General Integer Nonlinear Programming  Applied to Problem 10 of Lawler and Bell.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/4/24/

[48] Jsun Yui Wong (2012, September 27).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a Linear Ordering Problem with 22 Facilities.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/9/27/

[49] 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 Lawler and Bell's Problem 4, Third Edition

Jsun Yui Wong

Based on the computer program of the Second Edition, the following computer program seeks to solve Problem 4 of Lawler and Bell [23, p. 1107].  Line 291 through line 423 partly describe the problem.  The nonlinear objective function involving line 377 and line 404 and the nonlinear constraints shown in line 294 and in line 302 are noteworthy. 

The upper bound of 1000 for X(7) is used in line 79 and in line 107.

0 REM DEFDBL A-Z
1 DEFINT A,X
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),LHS(44),PLHS(44),LB(22),UB(22)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
76 LB(1)=0:LB(2)=0:LB(3)=0:LB(4)=0:LB(5)=0
77 LB(6)=0:LB(7)=0
78 UB(1)=7:UB(2)=7:UB(3)=7:UB(4)=15:UB(5)=15
79 UB(6)=7:UB(7)=1000
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-7E+30
101 A(1)=LB(1)+FIX(RND*8)
102 A(2)=LB(2)+FIX(RND*8)
103 A(3)=LB(3)+FIX(RND*8)
104 A(4)=LB(4)+FIX(RND*16)
105 A(5)=LB(5)+FIX(RND*16)
106 A(6)=LB(6)+FIX(RND*8)
107 A(7)=LB(7)+FIX(RND*1001)
126 IMAR=10+FIX(RND*1500)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 7
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
153  B=1+FIX(RND*7)
155 REM
156 REM  IF RND<.25 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE IF RND<.33 THEN X(B)=CINT(A(B))+FIX(1+RND*3) ELSE X(B)=A(B)+(1-RND*2)*(RND^(RND*7) )*A(B)
158 IF RND<.5 THEN X(B)=CINT(A(B))-FIX(1+RND*3) ELSE      X(B)=CINT(A(B))+FIX(1+RND*3)
251 FOR J78=1 TO 7
252 IF X(J78)<LB(J78)  THEN 1670
253 NEXT J78
254 FOR J79=1 TO 7
255 IF  X(J79)>UB(J79) THEN 1670
256 NEXT J79
291 X(8)=X(1)+X(2)+X(3)-6
292 X(9)=X(4)+X(5)+6*X(6)-8
293 X(10)=X(1)*X(6)+X(2)+3*X(5)-7
294 X(11)=4*X(2)*X(7)+3*X(4)*X(5)-25
297 REM   FOR J42=1 TO 4
298 REM   IF LHS(J42)<0 THEN PLHS(J42)=999999!*LHS(J42) ELSE PLHS(J42)=0
299 REM   NEXT J42
301 X(12)=-3*X(1)-2*X(3)-X(5)+7
302 X(13)=-3*X(1)*X(3)-6*X(4)-4*X(5)+20
303 X(14)=-4*X(1)-2*X(3)-X(6)*X(7)+15
307 FOR J43=8 TO 14
308 IF X(J43)<0 THEN PLHS(J43)=999999!*X(J43) ELSE PLHS(J43)=0
309 NEXT J43
315 LT=0
316 FOR J49=8 TO 14
317 LT=LT+PLHS(J49)
319 NEXT J49
341 TPDT=0
361 FOR JB=1 TO 7
371 FOR JA=1 TO 7
377 TPDT=TPDT-X(JB)*X(JA)
391 NEXT JA
401 NEXT JB
402 TPDT2=0
403 FOR JD=1 TO 7
404 TPDT2=TPDT2+X(JD)*X(JD)
405 NEXT JD
423 PDU=    TPDT +   TPDT2   +LT
466 P=PDU
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 14
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-50 THEN 1999
1901 PRINT A(1),A(2),A(3),A(4),A(5)
1903 PRINT A(6),A(7),A(8),A(9),A(10)
1904 PRINT A(11),A(12),A(13),A(14)
1906 PRINT M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run via basica/D of Microsoft's GW-BASIC 3.11 interpreter for DOS.  The complete output through JJJJ=-31710 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

0   7   0   0   0
2   1   1   4   0
3   7   20   13
-46   -31922

0   7   0   0   0
2   1   1   4   0
3   7   20   13
-46   -31822

0   7   0   0   0
2   1   1   4   0
3   7   20   13
-46   -31756

0   7   0   0   0
2   1   1   4   0
3   7   20   13
-46   -31710

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 from JJJJ=-32000 through JJJJ=-31710 was two minutes and a half.

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] R. C. Carlson and G. L. Nemhauser, Scheduling To Minimize Interaction Cost.  Operations Research, Vol. 14, No. 1 (Jan. - Feb., 1966), pp. 52-58.

[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] 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] F. E. Davis, M. D. Devine, and R. P. Lutz, Scheduling Activities Among Conflicting Facilities To Minimize Conflict Cost.  Mathematical Programming 6 (1974) 224-228)

[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] 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] Philipp Hungerlaender, Miguel F. Anjos (January 2012), A Semidefinite Optimization Approach to Free-Space Multi-Row Facility Layout.  Les Cahiers du GERAD.  Retrieved from www.gerad.ca/fichiers/cahiers/G-2012-03.pdf

[19] Philipp Hungerlaender (April 2012), Single-Row Equidistant Facility Layout as a Special Case of Single-Row Facility Layout.  Retrieved from www.optimization-online.org./DB_HTML/2012/04/3432.html

[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]  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] Sven Leyffer, "Deterministic Methods for Mixed Integer Nonlinear Programming," Ph. D. thesis, University of Dundee.  Dundee: December 1993.  (This thesis was obtained via Google search.)

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

[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] Tjark Vredeveld and Jan Karel Lenstra, On Local Search for the Generalized Graph Coloring Problem.  Operations Research Letters, 31 (2003) 28-34.

[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 (2012, April 24).  The Domino Method of General Integer Nonlinear Programming  Applied to Problem 10 of Lawler and Bell.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/4/24/

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