Substance

Solving a M. J. D. Powell Problem with the Domino Method for General Nonlinear Integer Programming, Second Edition

Jsun Yui Wong

The following computer program seeks to solve the Powell problem taken from Mayne and Maratos [30].
 
While line 128 of the earlier edition is 128 FOR I=1 TO 3000, here line 128 is 128 FOR I=1 TO 2000.

0 REM  DEFDBL A-Z
1 DEFINT I,J,K
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J(99),AA(99),HR(32),HHR(32),LHS(44),PLHS(44),LB(22),UB(22),PX(44),J44(44),               PN(22),NN(22)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-3D+30
111 FOR J44=1 TO 5
112 A(J44)=-5+RND*10
113 NEXT J44
126 REM   IMAR=10+FIX(RND*4000)
128 FOR I=1 TO 2000
129 FOR KKQQ=1 TO 5
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
139 FOR IPP=1 TO FIX(1+RND*3)
140 B=1+FIX(RND*5)
160 R=(1-RND*2)*A(B)
164 X(B)=A(B)+(RND^3*R)
178 NEXT IPP
180 IF   (-1-X(1)^3) <.0000001 THEN 1670
181 X(2)=(-1-X(1)^3)  ^.333333333#
183 X(3)=( 5*   X(4)*X(5)     )/X(2)
187 N(6)=  - X(1)^2 -X(2)^2 -X(3)^2 -X(4)^2 -X(5)^2  +10
318 FOR J44= 6 TO 6
319 IF ABS(N(J44))   >0  THEN PN(J44)=-1000000!*ABS(N(J44)) ELSE PN(J44)=0
320 NEXT J44
321 IF   (X(1)*X(2)*X(3)*X(4)* X(5)        ) >80 THEN 1670
322 PDA=- EXP(X(1)*X(2)*X(3)*X(4)* X(5)        )
333 PD1= PDA +PN(6)
335 PDU=+PD1
466 P=PDU
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 5
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1512 NN(6)=N(6)
1557 GOTO 128
1670 NEXT I
1889 IF M<-.0541 THEN 1999
1904 PRINT A(1),A(2),A(3)
1905 PRINT A(4),A(5),NN(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=-20645 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

-1.72156   1.600821   1.818947
.7543155   .7720398   0
-5.397187E-02   -29683

-1.726046   1.606006   -1.810611
-.7588464   .7663875   0
-5.399023E-02   -28373

-1.708848   1.586092   -1.842087
-.7881126   .7414473   0
-5.406881E-02   -23852

-1.715382   1.59367   -1.830507
-.7669632   .7607204   0
-5.395286E-02   -20645

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 obtaining the output through JJJJ=-20645  was 24   minutes.

Acknowledgment

I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
 
References

[1] Egon Balas, An Additive Algorithm for Solving Linear Programs with Zero-One Variables. Operations Research, Vol. 13, 517-546 (1965).

[2] Egon Balas, Discrete Programming by the Filter Method. Operations Research, Vol. 15, No. 5 (Sep. - Oct., 1967), pp. 915-957.

[3] J. Bracken, G. P. McCormick, Selected Applications of Nonlinear Programming.  New York: John Wiley and Sons, 1968.

[4] Richard L. Burden, J. Douglas Faires, Numerical Analysis, Ninth Edition.  Brooks/Cole 2011.

[5] M. F. Cardoso, R. L. Salcedo, S. Feyo de Azevedo, D. Barbosa (1997), A Simulated Annealing Approach to the Solution of MINLP Problems.  Computers and Chemical Engineering, 21 (12) pp.1349-1364.

[6] S. H. Chew, Q. Zheng, Integral Global Optimization.  Volume 298 of Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, 1988.

[7] William Conley, Computer Optimization Techniques.  New York/Princeton: Petrocelli Books, Inc., 1980.

[8] William Conley, Optimization: A Simplified Approach.  New York/Princeton: Petrocelli Books, Inc., 1981.

[9] William Conley (1982), An Economic Order Quantity Problem.  International Journal of Mathematical Education in Science and Technology, Vol. 13, No. 3, pp. 265-268.

[10] William Conley, Computer Optimization Techniques, Revised Edition.  New York/Princeton: Petrocelli Books, Inc., 1984.

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

[13] R. J. Duffin, E. L. Peterson, C. Zener, Geometric Programming Theory and Applications.  John Wiley and Sons, 1967.

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

[15] Christodoulos A. Floudas, Nonlinear and Mixed-Integer Optimization.  Oxford University Press, 1995.

[16] C. A. Floudas, Deterministic Global Optimization.  Kluwer Academic Publishers, 2000.

[17] R. S. Garfinkel, G. L. Nemhauser, Integer Programming.  John Wiley, Inc. 1972.

[18] Amos Gilat and Vish Subramaniam, Numerical Methods for Engineers and Scientists: An Introduction with Applications Using MATLAB.  John Wiley and Sons, Inc. 2008.

[19] Donald Greenspan, Vincenzo Casulli, Numerical Analysis for Applied Mathematics, Science, and Enginerring.  Addison-Wesley Publishing Company, 1988.

[20] Peter L. Hammer, Sergiu Rudeanu, Boolean Methods in Operations Research and Related Areas.  New York: Springer-Verlag, 1968.

[21] Peter L. Hammer, Sergiu Rudeanu, Psudo-Boolean Programming.  Operations Research, March/April 1969 Vol. 17 No. 2, pp. 233-261.

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

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

[24] Ali Husseinzadeh Kashan (2011), An Efficient Algorithm for Constrained Global Optimization and Application to Mechanical Engineering Design: League Championship Algorithm (LCA).  Computer-Aided Design 43 (2011) 1769-1792.

[25] G. R. Kocis, I. E. Grossmann, Global Optimization of Nonconvex Mixed-Integer Nonlinear Programming Problems in Process Synthesis.  Ind. Eng. Chem. Res., Vol. 27, No. 8, 1988, pages 1407-1421.

[26] G. R. Kocis, I. E. Grossmann, A Modelling amd Decomposition Strategy for MINLP Optimization.  Computers and Chemical Engineering, Vol. 13, No. 7, July 1989, pages 797-819.

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

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

[29] Duan Li, Xiaoling Sun, Nonlinear Integer Programming.  Springer, 2006.

[30] D. Q. Mayne, N. Maratos (1979), A First Order, Exact Penalty Function Algorithm for Equallity Constrained Optimization Problems.  Mathematical Programming 16 (1979) 303-324.

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

[32] Keith Meintjes and Alexander P. Morgan, Chemical Equilibrium Systems as Numerical Test Problems.  ACM Transactions on Mathematical Software, Vol. 16, No. 2, June 1990, Pages 143-151.

[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] C. Mohan,  H. T. Nguyen (1999), A Controlled Random Search Technique Incorporating the Simulated Annealing Concept for Solving Integer and Mixed Integer Global Optimization Problems.  
Computational Optimization and Applications, July 1999, Vol. 14 Issue 1, pp.103-132.

[35] Ramon E. Moore, R. Baker Kearfott, Michael J. Cloud, An Introduction to Interval Analysis.  Cambridge University Press, 2009.

[36] Chi-Kong Ng, Lian-Sheng Zhang, Duan Li, Wei-Wen Tian (2005), Discrete Filled Function Method for Discrete Optimization.  Computational Optimization and Applications, 31, pp. 87-115, 2005.

[37] Panos Y. Papalambros, Douglass J. Wilde, Principles of Optimal Design: Modeling and Computation, Second Edition.  Cambridge University Press, 2000.

[38] D. R. Plane, C. McMillan, Discrete Optimization.  Englewood Cliffs: Prentice-Hall, 1971.

[39] John R. Rice, Numerical Methods, Software, and Analysis, Second Edition.  Academic Press, 1993.

[40] H. S. Ryoo, N. V. Sahinidis (1995), Global Optimization of Nonconvex NLPs and MINLPs with Applications in Process Design.  Computers and Chemical Engineering, Vol. 19, No. 5, pp. 551-566, 1995.

[41] Terry Shoup, A Practical Guide to Computer Methods for Engineers.  Englewood Cliffs: Prentice-Hall, 1979.

[42] M. Syslo, N. Deo, J. Kowalik, Discrete Optimization Algorithms with Pascal Programs.  Englewood Cliffs: Prentice-Hall, 1983.

[43] C. A. Trauth, R. E. Woolsey (1969), Integer Linear Programming: A Study in Computational Efficiency.  Management Science, Volume 15, 1969, 481-493.

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

[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, May 5).  The Domino Method Applied to Solving a Nonlinear System of Five Equations, Third Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/05/05

[47] Jsun Yui Wong (2011, May 15).  The Domino Method Applied to Solving a Nonlinear System of Ten Equations of a Model of Propane-in-Air Combustion, Fourth Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/05/15

[48] Jsun Yui Wong (2012, February 26).  The Domino Method of Nonlinear Discrete Programming Applied to a Small Problem from the Literature.  Retrieved from http://myblogsubstance.typepad.com/substance/2012/02

[49] Jsun Yui Wong (2011, November 20).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Air Transport Model of Markowitz and Manne, Fifth Edition Revisited.  Retrieved from http://myblogsubstance.typepad.com/substance/2011/11

[50] Jsun Yui Wong (2012, April 21).  The Domino Method of General Integer Nonlinear Programming Applied to a Five-Step Cantilever Beam Design.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/04/21/

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

[52] Jsun Yui Wong (2013, January 14).  The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with Integer Variables and Continuous Variables, Revised Edition.   Retrieved from http://myblogsubstance.typepad.com/substance/2013/01

[53] Jsun Yui Wong (2013, January 24).  The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with Eight 0-1 Variables and Nine Continuous Variables.   Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2013/01/24

 [54]  Liexiang Yan, Kun Shen, Shenghua Hu (2004), Solving Mixed Integer Nonlinear Programming Problems with Line-Up Competition Algorithm. Computers and Chemical Engineering, Volume 28, Issue 12, pages 2647-2657.

Solving a M. J. D. Powell Problem with the Domino Method for General Nonlinear Integer Programming

Jsun Yui Wong

The following computer program seeks to solve the Powell problem taken from Mayne and Maratos [30]. 

0 REM  DEFDBL A-Z
1 DEFINT I,J,K
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J(99),AA(99),HR(32),HHR(32),LHS(44),PLHS(44),LB(22),UB(22),PX(44),J44(44),               PN(22),NN(22)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-3D+30
111 FOR J44=1 TO 5
112 A(J44)=-5+RND*10
113 NEXT J44
126 REM   IMAR=10+FIX(RND*4000)
128 FOR I=1 TO 3000
129 FOR KKQQ=1 TO 5
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
139 FOR IPP=1 TO FIX(1+RND*3)
140 B=1+FIX(RND*5)
160 R=(1-RND*2)*A(B)
164 X(B)=A(B)+(RND^3*R)
178 NEXT IPP
180 IF   (-1-X(1)^3) <.0000001 THEN 1670
181 X(2)=(-1-X(1)^3)  ^.333333333#
183 X(3)=( 5*   X(4)*X(5)     )/X(2)
187 N(6)=  - X(1)^2 -X(2)^2 -X(3)^2 -X(4)^2 -X(5)^2  +10
318 FOR J44= 6 TO 6
319 IF ABS(N(J44))   >0  THEN PN(J44)=-1000000!*ABS(N(J44)) ELSE PN(J44)=0
320 NEXT J44
321 IF   (X(1)*X(2)*X(3)*X(4)* X(5)        ) >80 THEN 1670
322 PDA=- EXP(X(1)*X(2)*X(3)*X(4)* X(5)        )
333 PD1= PDA +PN(6)
335 PDU=+PD1
466 P=PDU
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 5
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1512 NN(6)=N(6)
1557 GOTO 128
1670 NEXT I
1889 IF M<-.0541 THEN 1999
1904 PRINT A(1),A(2),A(3)
1905 PRINT A(4),A(5),NN(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.  Only the top-two candidate solutions through JJJJ=-20793 are shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

-1.712664   1.590519   -1.835547
-.762468   .7657954   0
-5.395983E-02   -21372

-1.718274   1.597019   -1.825104
.7569612   -.7701121   0
-5.395743E-02   -20793

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 obtaining the output through JJJJ=-20793  was 33  minutes.

Acknowledgment

I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
 
References

[1] Egon Balas, An Additive Algorithm for Solving Linear Programs with Zero-One Variables. Operations Research, Vol. 13, 517-546 (1965).

[2] Egon Balas, Discrete Programming by the Filter Method. Operations Research, Vol. 15, No. 5 (Sep. - Oct., 1967), pp. 915-957.

[3] J. Bracken, G. P. McCormick, Selected Applications of Nonlinear Programming.  New York: John Wiley and Sons, 1968.

[4] Richard L. Burden, J. Douglas Faires, Numerical Analysis, Ninth Edition.  Brooks/Cole 2011.

[5] M. F. Cardoso, R. L. Salcedo, S. Feyo de Azevedo, D. Barbosa (1997), A Simulated Annealing Approach to the Solution of MINLP Problems.  Computers and Chemical Engineering, 21 (12) pp.1349-1364.

[6] S. H. Chew, Q. Zheng, Integral Global Optimization.  Volume 298 of Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, 1988.

[7] William Conley, Computer Optimization Techniques.  New York/Princeton: Petrocelli Books, Inc., 1980.

[8] William Conley, Optimization: A Simplified Approach.  New York/Princeton: Petrocelli Books, Inc., 1981.

[9] William Conley (1982), An Economic Order Quantity Problem.  International Journal of Mathematical Education in Science and Technology, Vol. 13, No. 3, pp. 265-268.

[10] William Conley, Computer Optimization Techniques, Revised Edition.  New York/Princeton: Petrocelli Books, Inc., 1984.

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

[13] R. J. Duffin, E. L. Peterson, C. Zener, Geometric Programming Theory and Applications.  John Wiley and Sons, 1967.

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

[15] Christodoulos A. Floudas, Nonlinear and Mixed-Integer Optimization.  Oxford University Press, 1995.

[16] C. A. Floudas, Deterministic Global Optimization.  Kluwer Academic Publishers, 2000.

[17] R. S. Garfinkel, G. L. Nemhauser, Integer Programming.  John Wiley, Inc. 1972.

[18] Amos Gilat and Vish Subramaniam, Numerical Methods for Engineers and Scientists: An Introduction with Applications Using MATLAB.  John Wiley and Sons, Inc. 2008.

[19] Donald Greenspan, Vincenzo Casulli, Numerical Analysis for Applied Mathematics, Science, and Enginerring.  Addison-Wesley Publishing Company, 1988.

[20] Peter L. Hammer, Sergiu Rudeanu, Boolean Methods in Operations Research and Related Areas.  New York: Springer-Verlag, 1968.

[21] Peter L. Hammer, Sergiu Rudeanu, Psudo-Boolean Programming.  Operations Research, March/April 1969 Vol. 17 No. 2, pp. 233-261.

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

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

[24] Ali Husseinzadeh Kashan (2011), An Efficient Algorithm for Constrained Global Optimization and Application to Mechanical Engineering Design: League Championship Algorithm (LCA).  Computer-Aided Design 43 (2011) 1769-1792.

[25] G. R. Kocis, I. E. Grossmann, Global Optimization of Nonconvex Mixed-Integer Nonlinear Programming Problems in Process Synthesis.  Ind. Eng. Chem. Res., Vol. 27, No. 8, 1988, pages 1407-1421.

[26] G. R. Kocis, I. E. Grossmann, A Modelling amd Decomposition Strategy for MINLP Optimization.  Computers and Chemical Engineering, Vol. 13, No. 7, July 1989, pages 797-819.

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

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

[29] Duan Li, Xiaoling Sun, Nonlinear Integer Programming.  Springer, 2006.

[30] D. Q. Mayne, N. Maratos (1979), A First Order, Exact Penalty Function Algorithm for Equallity Constrained Optimization Problems.  Mathematical Programming 16 (1979) 303-324.

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

[32] Keith Meintjes and Alexander P. Morgan, Chemical Equilibrium Systems as Numerical Test Problems.  ACM Transactions on Mathematical Software, Vol. 16, No. 2, June 1990, Pages 143-151.

[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] C. Mohan,  H. T. Nguyen (1999), A Controlled Random Search Technique Incorporating the Simulated Annealing Concept for Solving Integer and Mixed Integer Global Optimization Problems.  
Computational Optimization and Applications, July 1999, Vol. 14 Issue 1, pp.103-132.

[35] Ramon E. Moore, R. Baker Kearfott, Michael J. Cloud, An Introduction to Interval Analysis.  Cambridge University Press, 2009.

[36] Chi-Kong Ng, Lian-Sheng Zhang, Duan Li, Wei-Wen Tian (2005), Discrete Filled Function Method for Discrete Optimization.  Computational Optimization and Applications, 31, pp. 87-115, 2005.

[37] Panos Y. Papalambros, Douglass J. Wilde, Principles of Optimal Design: Modeling and Computation, Second Edition.  Cambridge University Press, 2000.

[38] D. R. Plane, C. McMillan, Discrete Optimization.  Englewood Cliffs: Prentice-Hall, 1971.

[39] John R. Rice, Numerical Methods, Software, and Analysis, Second Edition.  Academic Press, 1993.

[40] H. S. Ryoo, N. V. Sahinidis (1995), Global Optimization of Nonconvex NLPs and MINLPs with Applications in Process Design.  Computers and Chemical Engineering, Vol. 19, No. 5, pp. 551-566, 1995.

[41] Terry Shoup, A Practical Guide to Computer Methods for Engineers.  Englewood Cliffs: Prentice-Hall, 1979.

[42] M. Syslo, N. Deo, J. Kowalik, Discrete Optimization Algorithms with Pascal Programs.  Englewood Cliffs: Prentice-Hall, 1983.

[43] C. A. Trauth, R. E. Woolsey (1969), Integer Linear Programming: A Study in Computational Efficiency.  Management Science, Volume 15, 1969, 481-493.

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

[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, May 5).  The Domino Method Applied to Solving a Nonlinear System of Five Equations, Third Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/05/05

[47] Jsun Yui Wong (2011, May 15).  The Domino Method Applied to Solving a Nonlinear System of Ten Equations of a Model of Propane-in-Air Combustion, Fourth Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/05/15

[48] Jsun Yui Wong (2012, February 26).  The Domino Method of Nonlinear Discrete Programming Applied to a Small Problem from the Literature.  Retrieved from http://myblogsubstance.typepad.com/substance/2012/02

[49] Jsun Yui Wong (2011, November 20).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Air Transport Model of Markowitz and Manne, Fifth Edition Revisited.  Retrieved from http://myblogsubstance.typepad.com/substance/2011/11

[50] Jsun Yui Wong (2012, April 21).  The Domino Method of General Integer Nonlinear Programming Applied to a Five-Step Cantilever Beam Design.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/04/21/

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

[52] Jsun Yui Wong (2013, January 14).  The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with Integer Variables and Continuous Variables, Revised Edition.   Retrieved from http://myblogsubstance.typepad.com/substance/2013/01

[53] Jsun Yui Wong (2013, January 24).  The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with Eight 0-1 Variables and Nine Continuous Variables.   Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2013/01/24

 [54]  Liexiang Yan, Kun Shen, Shenghua Hu (2004), Solving Mixed Integer Nonlinear Programming Problems with Line-Up Competition Algorithm. Computers and Chemical Engineering, Volume 28, Issue 12, pages 2647-2657.

Solving a Mixed-Integer Nonlinear Programming Problem with the Domino Method for General Nonlinear Integer Programming

Jsun Yui Wong

The following computer program seeks to solve Example 4 on page 2652 of Yan, Shen, and Hu [53].  The source of this problem is Cardoso, Salcedo, Feyo de Azevedo, and Barbosa [5].

0 REM DEFDBL A-Z
1 DEFINT I,J,K
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J(99),AA(99),HR(32),HHR(32),LHS(44),PLHS(44),LB(22),UB(22),PX(44),J44(44),               PN(22),NN(22)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-3E+30
111 FOR J44=1 TO 3
112 A(J44)=RND
113 NEXT J44
121 FOR J44=4 TO 11
122 A(J44)=FIX(RND*2)
123 NEXT J44
126 REM   IMAR=10+FIX(RND*4000)
128 FOR I=1 TO 50
129 FOR KKQQ=1 TO 11
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
139 FOR IPP=1 TO FIX(1+RND*3)
140 B=4+FIX(RND*8)
150 GOTO 171
160 R=(1-RND*2)*A(B)
164 X(B)=A(B)+(RND^3*R)
165 GOTO 178
166 REM IF B>3.5 THEN 168 ELSE 178
168 REM X(B)=CINT(X(B))
171 IF A(B)=0 THEN X(B)=1 ELSE X(B)=0
178 NEXT IPP
191 N(12)=-1   + X( 10) +X( 11)
192 X(3)= 1   -.02^X(10)    *.06^X(11)
193 N(13)= -1+ X( 4 ) +X( 5 )      +  X( 6 )
195 X(1)= 1- .1^X( 4 )*.2^X( 5 )*.15^X(6)
197 N(14)= -1+ X( 7 ) +X( 8 )      +  X( 9 )
199 X(2)= 1- .05^X( 7 )*.2^X( 8 )*.15^X(9)
203 N(15)= 10 - 3*X( 4 ) -1*X( 5) -2*X(6)-3*X(7)-2*X(8)-1*X(9)-3*X(10) -2*X(11)
251 FOR J44=1 TO 11
252 IF X(J44)<0 THEN 1670
253 NEXT J44
261 FOR J44=4 TO 11
262 IF X(J44)>1 THEN 1670
263 NEXT J44
318 FOR J44=12 TO 15
319 IF N(J44)<0 THEN PN(J44)=1000000!*N(J44) ELSE PN(J44)=0
320 NEXT J44
322 PDA= X(1)*X(2)*X(3)
333 PD1= PDA +   PN(12)+PN(13)+PN(14)+PN(15)
335 PDU=+PD1
466 P=PDU
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 7
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1516 NN(12)=N(12)
1517 NN(13)=N(13)
1518 NN(14)=N(14)
1519 NN(15)=N(15)
1557 GOTO 128
1670 NEXT I
1889 IF M<.943 THEN 1999
1904 PRINT A(1),A(2),A(3)
1905 PRINT A(4),A(5),A(6),A(7)
1907 PRINT A(8),A(9),A(10),A(11)
1908 PRINT NN(12),NN(13)
1909 PRINT NN(14),NN(15)
1911 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 produced through JJJJ=-31972 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

.97   .9925   .98
0   1   1   1
1   1   0   0
0   1
1   0
.9434706   -31998

.97   .9925   .98
0   1   1   1
0   0   0   0
0   1
1   0
.9434706   -31996

.97   .9925   .98
0   1   1   1
1   0   1   1
0   1
1   0
.9434706   -31982

.97   .9925   .98
0   1   1   1
0   0   1   1
0   1
1   0
.9434706   -31978

.97   .9925   .98
0   1   1   1
0   1   1   0
0   1
1   0
.9434706   -31975

.97   .9925   .98
0   1   1   1
0   1   0   0
0   1
1   0
.9434706   -31974

.97   .9925   .98
0   1   1   1
1   0   1   0
0   1
1   0
.9434706   -31972

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 obtaining the output through JJJJ=-31972  was one second.

Acknowledgment

I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
 
References

[1] Egon Balas, An Additive Algorithm for Solving Linear Programs with Zero-One Variables. Operations Research, Vol. 13, 517-546 (1965).

[2] Egon Balas, Discrete Programming by the Filter Method. Operations Research, Vol. 15, No. 5 (Sep. - Oct., 1967), pp. 915-957.

[3] J. Bracken, G. P. McCormick, Selected Applications of Nonlinear Programming.  New York: John Wiley and Sons, 1968.

[4] Richard L. Burden, J. Douglas Faires, Numerical Analysis, Ninth Edition.  Brooks/Cole 2011.

[5] M. F. Cardoso, R. L. Salcedo, S. Feyo de Azevedo, D. Barbosa (1997), A Simulated Annealing Approach to the Solution of MINLP Problems.  Computers and Chemical Engineering, 21 (12) pp. 1349-1364.

[6] S. H. Chew, Q. Zheng, Integral Global Optimization.  Volume 298 of Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, 1988.

[7] William Conley, Computer Optimization Techniques.  New York/Princeton: Petrocelli Books, Inc., 1980.

[8] William Conley, Optimization: A Simplified Approach.  New York/Princeton: Petrocelli Books, Inc., 1981.

[9] William Conley (1982), An Economic Order Quantity Problem.  International Journal of Mathematical Education in Science and Technology, Vol. 13, No. 3, pp. 265-268.

[10] William Conley, Computer Optimization Techniques, Revised Edition.  New York/Princeton: Petrocelli Books, Inc., 1984.

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

[13] R. J. Duffin, E. L. Peterson, C. Zener, Geometric Programming Theory and Applications.  John Wiley and Sons, 1967.

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

[15] Christodoulos A. Floudas, Nonlinear and Mixed-Integer Optimization.  Oxford University Press, 1995.

[16] C. A. Floudas, Deterministic Global Optimization.  Kluwer Academic Publishers, 2000.

[17] R. S. Garfinkel, G. L. Nemhauser, Integer Programming.  John Wiley, Inc. 1972.

[18] Amos Gilat and Vish Subramaniam, Numerical Methods for Engineers and Scientists: An Introduction with Applications Using MATLAB.  John Wiley and Sons, Inc. 2008.

[19] Donald Greenspan, Vincenzo Casulli, Numerical Analysis for Applied Mathematics, Science, and Enginerring.  Addison-Wesley Publishing Company, 1988.

[20] Peter L. Hammer, Sergiu Rudeanu, Boolean Methods in Operations Research and Related Areas.  New York: Springer-Verlag, 1968.

[21] Peter L. Hammer, Sergiu Rudeanu, Psudo-Boolean Programming.  Operations Research, March/April 1969 Vol. 17 No. 2, pp. 233-261.

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

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

[24] Ali Husseinzadeh Kashan (2011), An Efficient Algorithm for Constrained Global Optimization and Application to Mechanical Engineering Design: League Championship Algorithm (LCA).  Computer-Aided Design 43 (2011) 1769-1792.

[25] G. R. Kocis, I. E. Grossmann, Global Optimization of Nonconvex Mixed-Integer Nonlinear Programming Problems in Process Synthesis.  Ind. Eng. Chem. Res., Vol. 27, No. 8, 1988, pages 1407-1421.

[26] G. R. Kocis, I. E. Grossmann, A Modelling amd Decomposition Strategy for MINLP Optimization.  Computers and Chemical Engineering, Vol. 13, No. 7, July 1989, pages 797-819.

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

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

[29] Duan Li, Xiaoling Sun, Nonlinear Integer Programming.  Springer, 2006.

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

[31] Keith Meintjes and Alexander P. Morgan, Chemical Equilibrium Systems as Numerical Test Problems.  ACM Transactions on Mathematical Software, Vol. 16, No. 2, June 1990, Pages 143-151.

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

[33] C. Mohan,  H. T. Nguyen (1999), A Controlled Random Search Technique Incorporating the Simulated Annealing Concept for Solving Integer and Mixed Integer Global Optimization Problems.  
Computational Optimization and Applications, July 1999, Vol. 14 Issue 1, pp.103-132.

[34] Ramon E. Moore, R. Baker Kearfott, Michael J. Cloud, An Introduction to Interval Analysis.  Cambridge University Press, 2009.

[35] Chi-Kong Ng, Lian-Sheng Zhang, Duan Li, Wei-Wen Tian (2005), Discrete Filled Function Method for Discrete Optimization.  Computational Optimization and Applications, 31, pp. 87-115, 2005.

[36] Panos Y. Papalambros, Douglass J. Wilde, Principles of Optimal Design: Modeling and Computation, Second Edition.  Cambridge University Press, 2000.

[37] D. R. Plane, C. McMillan, Discrete Optimization.  Englewood Cliffs: Prentice-Hall, 1971.

[38] John R. Rice, Numerical Methods, Software, and Analysis, Second Edition.  Academic Press, 1993.

[39] H. S. Ryoo, N. V. Sahinidis (1995), Global Optimization of Nonconvex NLPs and MINLPs with Applications in Process Design.  Computers and Chemical Engineering, Vol. 19, No. 5, pp. 551-566, 1995.

[40] Terry Shoup, A Practical Guide to Computer Methods for Engineers.  Englewood Cliffs: Prentice-Hall, 1979.

[41] M. Syslo, N. Deo, J. Kowalik, Discrete Optimization Algorithms with Pascal Programs.  Englewood Cliffs: Prentice-Hall, 1983.

[42] C. A. Trauth, R. E. Woolsey (1969), Integer Linear Programming: A Study in Computational Efficiency.  Management Science, Volume 15, 1969, 481-493.

[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, 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

[45] Jsun Yui Wong (2011, May 5).  The Domino Method Applied to Solving a Nonlinear System of Five Equations, Third Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/05/05

[46] Jsun Yui Wong (2011, May 15).  The Domino Method Applied to Solving a Nonlinear System of Ten Equations of a Model of Propane-in-Air Combustion, Fourth Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/05/15

[47] Jsun Yui Wong (2012, February 26).  The Domino Method of Nonlinear Discrete Programming Applied to a Small Problem from the Literature.  Retrieved from http://myblogsubstance.typepad.com/substance/2012/02

[48] Jsun Yui Wong (2011, November 20).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Air Transport Model of Markowitz and Manne, Fifth Edition Revisited.  Retrieved from http://myblogsubstance.typepad.com/substance/2011/11

[49] Jsun Yui Wong (2012, April 21).  The Domino Method of General Integer Nonlinear Programming Applied to a Five-Step Cantilever Beam Design.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/04/21/

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

[51] Jsun Yui Wong (2013, January 14).  The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with Integer Variables and Continuous Variables, Revised Edition.   Retrieved from http://myblogsubstance.typepad.com/substance/2013/01

[52] Jsun Yui Wong (2013, January 24).  The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with Eight 0-1 Variables and Nine Continuous Variables.   Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2013/01/24

 [53]  Liexiang Yan, Kun Shen, Shenghua Hu (2004), Solving Mixed Integer Nonlinear Programming Problems with Line-Up Competition Algorithm. Computers and Chemical Engineering, Volume 28, Issue 12, pages 2647-2657.

Solving Another Complicated Problem with the Domino Method for General Nonlinear Integer Programming, Second Edition

Jsun Yui Wong

The following computer program seeks to solve Example 5 on page 2652 of Yan, Shen, and Hu [52].  This is a "complicated" problem, Yan, Shen, and Hu [52, p. 2653].

In contrast to the older edition, the present edition features line 0 and line 171.

0 REM DEFDBL A-Z
1 DEFINT I,J,K
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J(99),AA(99),HR(32),HHR(32),LHS(44),PLHS(44),LB(22),UB(22),PX(44),J44(44),               PN(22),NN(22)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-3E+30
111 FOR J44=1 TO 3
112 A(J44)=RND
113 NEXT J44
121 FOR J44=4 TO 7
122 A(J44)=FIX(RND*2)
123 NEXT J44
126 REM   IMAR=10+FIX(RND*4000)
128 FOR I=1 TO 1000
129 FOR KKQQ=1 TO 7
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
139 FOR IPP=1 TO FIX(1+RND*3)
140 B=1+FIX(RND*7)
150 IF B<3.5 THEN 160 ELSE 171
160 R=(1-RND*2)*A(B)
164 X(B)=A(B)+(RND^3*R)
165 GOTO 178
166 REM IF B>3.5 THEN 168 ELSE 178
168 REM X(B)=CINT(X(B))
171 IF A(B)=0 THEN X(B)=1 ELSE X(B)=0
178 NEXT IPP
181 N(8)=1.2-X(1)   -X(4)
183 N(9)= 1.2 - X(1)-X(7)
187 N(10)= 1.8-  X( 2 ) -X( 5 )
189 N(11)= 1.64- X( 2 )^2 -X( 5 )  ^2
191 N(12)= 2.5- X( 3 ) -X( 6 )
192 N(13)= 4.25- X( 3 )^2 -X( 6 ) ^2
193 N(14)= 4.64- X( 3 )^2 -X( 5 ) ^2
195 N(15)= 5.5- X( 1 )^2 -X( 2 ) ^2   -X(3)^2   -X(6)^2
197 N(16)= 5- X( 1 ) -X( 2 )-X( 3)     -X(4)   -X(5)  -X(6)
251 FOR J44=1 TO 7
252 IF X(J44)<0 THEN 1670
253 NEXT J44
261 FOR J44=4 TO 7
262 IF X(J44)>1.00001 THEN 1670
263 NEXT J44
318 FOR J44= 8 TO 16
319 IF N(J44)<0 THEN PN(J44)=1000000!*N(J44) ELSE PN(J44)=0
320 NEXT J44
322 PDA=-( X(1)-1)^2 -  (X(2)-2   )^2   -(X(3)-3  )^2   -(X(4) -1)^2               -( X(5) -2 )^2  -(X(6)- 1)^2  + LOG(X(7)+1 )
333 PD1= PDA +PN(8)+PN(9)+PN(10)+PN(11)+PN(12)+PN(13)+PN(14)+PN(15)+PN(16)
335 PDU=+PD1
466 P=PDU
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 7
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1511 REM NN(7)=N(7)
1512 NN(8)=N(8)
1513 NN(9)=N(9)
1514 NN(10)=N(10)
1515 NN(11)=N(11)
1516 NN(12)=N(12)
1517 NN(13)=N(13)
1518 NN(14)=N(14)
1519 NN(15)=N(15)
1520 NN(16)=N(16)
1557 GOTO 128
1670 NEXT I
1889 IF M<-4.7 THEN 1999
1904 PRINT A(1),A(2),A(3)
1905 PRINT A(4),A(5),A(6),A(7)
1906 PRINT M,JJJJ
1907 PRINT NN(8),NN(9),NN(10)
1908 PRINT NN(11),NN(12),NN(13)
1909 PRINT NN(14),NN(15),NN(16)
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 produced 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.

.1999995   .7999973   1.907877
1   1   0   1
-4.579592   -32000
4.768372E-07   4.768372E-07   2.622604E-06
4.291535E-06   .5921227   .6100042
4.053116E-06   1.180009   9.212589E-02

.1999956   .799987   1.907876
1   1   0   1
-4.579627   -31998
4.410744E-06   4.410744E-06   1.299381E-05
2.086163E-05   .5921243   .6100106
1.049042E-05   1.180033   9.214211E-02

.1999933   .7999999   1.90785
1   1   0   1
-4.579655   -31997
6.67572E-06   6.67572E-06   0
2.384186E-07   .59215   .6101084
1.08242E-04   1.180111   9.215712E-02

.2000001   .7999948   1.907873
1   1   0   1
-4.579606   -31996
0   0   5.126E-06
8.34465E-06   .5921269   .6100202
2.002716E-05   1.180029   9.213209E-02

.1999997   .7999935   1.90785
1   1   0   1
-4.579662   -31995
3.576279E-07   3.576279E-07   6.437302E-06
1.049042E-05   .5921505   .6101101
1.09911E-04   1.180121   9.215712E-02

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 obtaining the output through JJJJ=-31995  was five seconds.

Acknowledgment

I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
 
References

[1] Egon Balas, An Additive Algorithm for Solving Linear Programs with Zero-One Variables. Operations Research, Vol. 13, 517-546 (1965).

[2] Egon Balas, Discrete Programming by the Filter Method. Operations Research, Vol. 15, No. 5 (Sep. - Oct., 1967), pp. 915-957.

[3] J. Bracken, G. P. McCormick, Selected Applications of Nonlinear Programming.  New York: John Wiley and Sons, 1968.

[4] Richard L. Burden, J. Douglas Faires, Numerical Analysis, Ninth Edition.  Brooks/Cole 2011.

[5] S. H. Chew, Q. Zheng, Integral Global Optimization.  Volume 298 of Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, 1988.

[6] William Conley, Computer Optimization Techniques.  New York/Princeton: Petrocelli Books, Inc., 1980.

[7] William Conley, Optimization: A Simplified Approach.  New York/Princeton: Petrocelli Books, Inc., 1981.

[8] William Conley (1982), An Economic Order Quantity Problem.  International Journal of Mathematical Education in Science and Technology, Vol. 13, No. 3, pp. 265-268.

[9] William Conley, Computer Optimization Techniques, Revised Edition.  New York/Princeton: Petrocelli Books, Inc., 1984.

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

[12] R. J. Duffin, E. L. Peterson, C. Zener, Geometric Programming Theory and Applications.  John Wiley and Sons, 1967.

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

[14] Christodoulos A. Floudas, Nonlinear and Mixed-Integer Optimization.  Oxford University Press, 1995.

[15] C. A. Floudas, Deterministic Global Optimization.  Kluwer Academic Publishers, 2000.

[16] R. S. Garfinkel, G. L. Nemhauser, Integer Programming.  John Wiley, Inc. 1972.

[17] Amos Gilat and Vish Subramaniam, Numerical Methods for Engineers and Scientists: An Introduction with Applications Using MATLAB.  John Wiley and Sons, Inc. 2008.

[18] Donald Greenspan, Vincenzo Casulli, Numerical Analysis for Applied Mathematics, Science, and Enginerring.  Addison-Wesley Publishing Company, 1988.

[19] Peter L. Hammer, Sergiu Rudeanu, Boolean Methods in Operations Research and Related Areas.  New York: Springer-Verlag, 1968.

[20] Peter L. Hammer, Sergiu Rudeanu, Psudo-Boolean Programming.  Operations Research, March/April 1969 Vol. 17 No. 2, pp. 233-261.

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

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

[23] Ali Husseinzadeh Kashan (2011), An Efficient Algorithm for Constrained Global Optimization and Application to Mechanical Engineering Design: League Championship Algorithm (LCA).  Computer-Aided Design 43 (2011) 1769-1792.

[24] G. R. Kocis, I. E. Grossmann, Global Optimization of Nonconvex Mixed-Integer Nonlinear Programming Problems in Process Synthesis.  Ind. Eng. Chem. Res., Vol. 27, No. 8, 1988, pages 1407-1421.

[25] G. R. Kocis, I. E. Grossmann, A Modelling amd Decomposition Strategy for MINLP Optimization.  Computers and Chemical Engineering, Vol. 13, No. 7, July 1989, pages 797-819.

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

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

[28] Duan Li, Xiaoling Sun, Nonlinear Integer Programming.  Springer, 2006.

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

[30] Keith Meintjes and Alexander P. Morgan, Chemical Equilibrium Systems as Numerical Test Problems.  ACM Transactions on Mathematical Software, Vol. 16, No. 2, June 1990, Pages 143-151.

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

[32] C. Mohan,  H. T. Nguyen (1999), A Controlled Random Search Technique Incorporating the Simulated Annealing Concept for Solving Integer and Mixed Integer Global Optimization Problems.  
Computational Optimization and Applications, July 1999, Vol. 14 Issue 1, pp.103-132.

[33] Ramon E. Moore, R. Baker Kearfott, Michael J. Cloud, An Introduction to Interval Analysis.  Cambridge University Press, 2009.

[34] Chi-Kong Ng, Lian-Sheng Zhang, Duan Li, Wei-Wen Tian (2005), Discrete Filled Function Method for Discrete Optimization.  Computational Optimization and Applications, 31, pp. 87-115, 2005.

[35] Panos Y. Papalambros, Douglass J. Wilde, Principles of Optimal Design: Modeling and Computation, Second Edition.  Cambridge University Press, 2000.

[36] D. R. Plane, C. McMillan, Discrete Optimization.  Englewood Cliffs: Prentice-Hall, 1971.

[37] John R. Rice, Numerical Methods, Software, and Analysis, Second Edition.  Academic Press, 1993.

[38] H. S. Ryoo, N. V. Sahinidis (1995), Global Optimization of Nonconvex NLPs and MINLPs with Applications in Process Design.  Computers and Chemical Engineering, Vol. 19, No. 5, pp. 551-566, 1995.

[39] Terry Shoup, A Practical Guide to Computer Methods for Engineers.  Englewood Cliffs: Prentice-Hall, 1979.

[40] M. Syslo, N. Deo, J. Kowalik, Discrete Optimization Algorithms with Pascal Programs.  Englewood Cliffs: Prentice-Hall, 1983.

[41] C. A. Trauth, R. E. Woolsey (1969), Integer Linear Programming: A Study in Computational Efficiency.  Management Science, Volume 15, 1969, 481-493.

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

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

[44] Jsun Yui Wong (2011, May 5).  The Domino Method Applied to Solving a Nonlinear System of Five Equations, Third Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/05/05

[45] Jsun Yui Wong (2011, May 15).  The Domino Method Applied to Solving a Nonlinear System of Ten Equations of a Model of Propane-in-Air Combustion, Fourth Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/05/15

[46] Jsun Yui Wong (2012, February 26).  The Domino Method of Nonlinear Discrete Programming Applied to a Small Problem from the Literature.  Retrieved from http://myblogsubstance.typepad.com/substance/2012/02

[47] Jsun Yui Wong (2011, November 20).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Air Transport Model of Markowitz and Manne, Fifth Edition Revisited.  Retrieved from http://myblogsubstance.typepad.com/substance/2011/11

[48] Jsun Yui Wong (2012, April 21).  The Domino Method of General Integer Nonlinear Programming Applied to a Five-Step Cantilever Beam Design.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/04/21/

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

[50] Jsun Yui Wong (2013, January 14).  The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with Integer Variables and Continuous Variables, Revised Edition.   Retrieved from http://myblogsubstance.typepad.com/substance/2013/01

[51] Jsun Yui Wong (2013, January 24).  The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with Eight 0-1 Variables and Nine Continuous Variables.   Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2013/01/24

 [52]  Liexiang Yan, Kun Shen, Shenghua Hu, Solving Mixed Integer Nonlinear Programming Problems with Line-Up Competition Algorithm.  Computers and Chemical Engineering, Volume 28, Issue 12, November 2004, pages 2647-2657.

Solving a Complicated Problem with the Domino Method for General Nonlinear Integer Programming, Second Edition

Jsun Yui Wong

The following computer program seeks to solve Example 6 on pages 2652-2653 of Yan, Shen, and Hu [52].  This is a "complicated" problem, Yan, Shen, and Hu [52, p. 2653].

In contrast to the older edition, the present edition features line 0 and line 171.

0 REM DEFDBL A-Z
1 DEFINT I,J,K
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J(99),AA(99),HR(32),HHR(32),LHS(44),PLHS(44),LB(22),UB(22),PX(44),J44(44)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-3E+30
111 FOR J44=1 TO 4
112 A(J44)=RND
113 NEXT J44
121 FOR J44=5 TO 8
122 A(J44)=FIX(RND*5)
123 NEXT J44
126 REM   IMAR=10+FIX(RND*4000)
128 FOR I=1 TO 1000
129 FOR KKQQ=1 TO 8
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
139 FOR IPP=1 TO FIX(1+RND*3)
140 B=1+FIX(RND*8)
150 IF B<4.5 THEN 160 ELSE 171
160 R=(1-RND*2)*A(B)
164 X(B)=A(B)+(RND^3*R)
165 GOTO 178
166 REM IF B>4.5 THEN 168 ELSE 178
168 REM X(B)=CINT(X(B))
171 IF RND<.5 THEN X(B)=A(B)-1 ELSE X(B)=A(B)+1
178 NEXT IPP
181 X(2)=1-X(1)
183 X(4)=       X(1)+X(2)-X(3)
187 N(9)=    -4+  X( 5 ) +X( 6 )
189 N(10)=    -4+  X( 7 ) +X( 8 )
251 FOR J44=1 TO 8
252 IF X(J44)<0 THEN 1670
253 NEXT J44
261 FOR J44=5 TO 8
262 IF X(J44)>4.00001 THEN 1670
263 NEXT J44
271 IF X(5)<4*X(1)-.00001 THEN 1670
272 IF X(6)<4*X(2)-.00001 THEN 1670
273 IF X(7)<4*X(3)-.00001 THEN 1670
274 IF X(8)<4*X(4)-.00001 THEN 1670
318 FOR J44= 9 TO 10
319 IF N(J44)<0 THEN PN(J44)=1000000!*N(J44) ELSE PN(J44)=0
320 NEXT J44
322 PDA=-(  2.1*EXP(X(5))  -3*LOG(11*X(1)     )          )
323 PDB=-(.1*EXP(X(6))  -1*LOG(11*X(2)     )            )
324 PDC=-(4.1*EXP(X(7))  -3*LOG(11*X(3)     )          )
325 PDD=-(.1*EXP(X(8))  -4*LOG(11*X(4)     )          )
327 PDT=PDA+PDB+PDC+PDD
333 PD1= PDT +PN(9)+PN(10)
335 PDU=+PD1
466 P=PDU
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 8
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1513 NN(9)=N(9)
1514 NN(10)=N(10)
1557 GOTO 128
1670 NEXT I
1889 IF M<-5 THEN 1999
1904 PRINT A(1),A(2),A(3),A(4)
1905 PRINT A(5),A(6),A(7),A(8)
1906 PRINT M,JJJJ
1909 PRINT NN(9),NN(10)
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 produced through JJJJ=-31704 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

.2499996   .7500005   .25   .7500001
1   3   1   3
-4.249788   -31883
0   0

.2500007   .7499993   .2500024   .7499976
1   3   1   3
-4.249758   -31828
0   0

.2500009   .7499992   .2500013   .7499987
1   3   1   3
-4.249765   -31827
0   0

.2500014   .7499986   .2500021   .749998
1   3   1   3
-4.249751   -31822
0   0

.2500022   .7499979   .2500019   .7499981
1   3   1   3
-4.249747   -31704
0   0

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 obtaining the output through JJJJ=-31704  was 24 seconds.       

Acknowledgment

I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
 
References

[1] Egon Balas, An Additive Algorithm for Solving Linear Programs with Zero-One Variables. Operations Research, Vol. 13, 517-546 (1965).

[2] Egon Balas, Discrete Programming by the Filter Method. Operations Research, Vol. 15, No. 5 (Sep. - Oct., 1967), pp. 915-957.

[3] J. Bracken, G. P. McCormick, Selected Applications of Nonlinear Programming.  New York: John Wiley and Sons, 1968.

[4] Richard L. Burden, J. Douglas Faires, Numerical Analysis, Ninth Edition.  Brooks/Cole 2011.

[5] S. H. Chew, Q. Zheng, Integral Global Optimization.  Volume 298 of Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, 1988.

[6] William Conley, Computer Optimization Techniques.  New York/Princeton: Petrocelli Books, Inc., 1980.

[7] William Conley, Optimization: A Simplified Approach.  New York/Princeton: Petrocelli Books, Inc., 1981.

[8] William Conley (1982), An Economic Order Quantity Problem.  International Journal of Mathematical Education in Science and Technology, Vol. 13, No. 3, pp. 265-268.

[9] William Conley, Computer Optimization Techniques, Revised Edition.  New York/Princeton: Petrocelli Books, Inc., 1984.

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

[12] R. J. Duffin, E. L. Peterson, C. Zener, Geometric Programming Theory and Applications.  John Wiley and Sons, 1967.

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

[14] Christodoulos A. Floudas, Nonlinear and Mixed-Integer Optimization.  Oxford University Press, 1995.

[15] C. A. Floudas, Deterministic Global Optimization.  Kluwer Academic Publishers, 2000.

[16] R. S. Garfinkel, G. L. Nemhauser, Integer Programming.  John Wiley, Inc. 1972.

[17] Amos Gilat and Vish Subramaniam, Numerical Methods for Engineers and Scientists: An Introduction with Applications Using MATLAB.  John Wiley and Sons, Inc. 2008.

[18] Donald Greenspan, Vincenzo Casulli, Numerical Analysis for Applied Mathematics, Science, and Enginerring.  Addison-Wesley Publishing Company, 1988.

[19] Peter L. Hammer, Sergiu Rudeanu, Boolean Methods in Operations Research and Related Areas.  New York: Springer-Verlag, 1968.

[20] Peter L. Hammer, Sergiu Rudeanu, Psudo-Boolean Programming.  Operations Research, March/April 1969 Vol. 17 No. 2, pp. 233-261.

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

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

[23] Ali Husseinzadeh Kashan (2011), An Efficient Algorithm for Constrained Global Optimization and Application to Mechanical Engineering Design: League Championship Algorithm (LCA).  Computer-Aided Design 43 (2011) 1769-1792.

[24] G. R. Kocis, I. E. Grossmann, Global Optimization of Nonconvex Mixed-Integer Nonlinear Programming Problems in Process Synthesis.  Ind. Eng. Chem. Res., Vol. 27, No. 8, 1988, pages 1407-1421.

[25] G. R. Kocis, I. E. Grossmann, A Modelling amd Decomposition Strategy for MINLP Optimization.  Computers and Chemical Engineering, Vol. 13, No. 7, July 1989, pages 797-819.

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

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

[28] Duan Li, Xiaoling Sun, Nonlinear Integer Programming.  Springer, 2006.

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

[30] Keith Meintjes and Alexander P. Morgan, Chemical Equilibrium Systems as Numerical Test Problems.  ACM Transactions on Mathematical Software, Vol. 16, No. 2, June 1990, Pages 143-151.

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

[32] C. Mohan,  H. T. Nguyen (1999), A Controlled Random Search Technique Incorporating the Simulated Annealing Concept for Solving Integer and Mixed Integer Global Optimization Problems.  
Computational Optimization and Applications, July 1999, Vol. 14 Issue 1, pp.103-132.

[33] Ramon E. Moore, R. Baker Kearfott, Michael J. Cloud, An Introduction to Interval Analysis.  Cambridge University Press, 2009.

[34] Chi-Kong Ng, Lian-Sheng Zhang, Duan Li, Wei-Wen Tian (2005), Discrete Filled Function Method for Discrete Optimization.  Computational Optimization and Applications, 31, pp. 87-115, 2005.

[35] Panos Y. Papalambros, Douglass J. Wilde, Principles of Optimal Design: Modeling and Computation, Second Edition.  Cambridge University Press, 2000.

[36] D. R. Plane, C. McMillan, Discrete Optimization.  Englewood Cliffs: Prentice-Hall, 1971.

[37] John R. Rice, Numerical Methods, Software, and Analysis, Second Edition.  Academic Press, 1993.

[38] H. S. Ryoo, N. V. Sahinidis (1995), Global Optimization of Nonconvex NLPs and MINLPs with Applications in Process Design.  Computers and Chemical Engineering, Vol. 19, No. 5, pp. 551-566, 1995.

[39] Terry Shoup, A Practical Guide to Computer Methods for Engineers.  Englewood Cliffs: Prentice-Hall, 1979.

[40] M. Syslo, N. Deo, J. Kowalik, Discrete Optimization Algorithms with Pascal Programs.  Englewood Cliffs: Prentice-Hall, 1983.

[41] C. A. Trauth, R. E. Woolsey (1969), Integer Linear Programming: A Study in Computational Efficiency.  Management Science, Volume 15, 1969, 481-493.

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

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

[44] Jsun Yui Wong (2011, May 5).  The Domino Method Applied to Solving a Nonlinear System of Five Equations, Third Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/05/05

[45] Jsun Yui Wong (2011, May 15).  The Domino Method Applied to Solving a Nonlinear System of Ten Equations of a Model of Propane-in-Air Combustion, Fourth Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/05/15

[46] Jsun Yui Wong (2012, February 26).  The Domino Method of Nonlinear Discrete Programming Applied to a Small Problem from the Literature.  Retrieved from http://myblogsubstance.typepad.com/substance/2012/02

[47] Jsun Yui Wong (2011, November 20).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Air Transport Model of Markowitz and Manne, Fifth Edition Revisited.  Retrieved from http://myblogsubstance.typepad.com/substance/2011/11

[48] Jsun Yui Wong (2012, April 21).  The Domino Method of General Integer Nonlinear Programming Applied to a Five-Step Cantilever Beam Design.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/04/21/

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

[50] Jsun Yui Wong (2013, January 14).  The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with Integer Variables and Continuous Variables, Revised Edition.   Retrieved from http://myblogsubstance.typepad.com/substance/2013/01

[51] Jsun Yui Wong (2013, January 24).  The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with Eight 0-1 Variables and Nine Continuous Variables.   Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2013/01/24

 [52]  Liexiang Yan, Kun Shen, Shenghua Hu, Solving Mixed Integer Nnonlinear Programming Problems with Line-Up Competition Algorithm.  Computers and Chemical Engineering, Volume 28, Issue 12, November 2004, pages 2647-2657.

Solving Another Complicated Problem with the Domino Method for General Nonlinear Integer Programming

Jsun Yui Wong

The following computer program seeks to solve Example 5 on page 2652 of Yan, Shen, and Hu [52].  This is a "complicated" problem, Yan, Shen, and Hu [52, p. 2653].

0 DEFDBL A-Z
1 DEFINT I,J,K
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J(99),AA(99),HR(32),HHR(32),LHS(44),PLHS(44),LB(22),UB(22),PX(44),J44(44),               PN(22),NN(22)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-3E+30
111 FOR J44=1 TO 3
112 A(J44)=RND
113 NEXT J44
121 FOR J44=4 TO 7
122 A(J44)=FIX(RND*2)
123 NEXT J44
126 REM   IMAR=10+FIX(RND*4000)
128 FOR I=1 TO 1000
129 FOR KKQQ=1 TO 7
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
139 FOR IPP=1 TO FIX(1+RND*3)
140 B=1+FIX(RND*7)
160 R=(1-RND*2)*A(B)
164 X(B)=A(B)+(RND^3*R)
166 IF B>3.5 THEN 168 ELSE 178
168 X(B)=CINT(X(B))
178 NEXT IPP
181 N(8)=1.2-X(1)   -X(4)
183 N(9)= 1.2 - X(1)-X(7)
187 N(10)= 1.8-  X( 2 ) -X( 5 )
189 N(11)= 1.64- X( 2 )^2 -X( 5 )  ^2
191 N(12)= 2.5- X( 3 ) -X( 6 )
192 N(13)= 4.25- X( 3 )^2 -X( 6 ) ^2
193 N(14)= 4.64- X( 3 )^2 -X( 5 ) ^2
195 N(15)= 5.5- X( 1 )^2 -X( 2 ) ^2   -X(3)^2   -X(6)^2
197 N(16)= 5- X( 1 ) -X( 2 )-X( 3)     -X(4)   -X(5)  -X(6)
251 FOR J44=1 TO 7
252 IF X(J44)<0 THEN 1670
253 NEXT J44
261 FOR J44=4 TO 7
262 IF X(J44)>1.00001 THEN 1670
263 NEXT J44
318 FOR J44= 8 TO 16
319 IF N(J44)<0 THEN PN(J44)=1000000!*N(J44) ELSE PN(J44)=0
320 NEXT J44
322 PDA=-( X(1)-1)^2 -  (X(2)-2   )^2   -(X(3)-3  )^2   -(X(4) -1)^2               -( X(5) -2 )^2  -(X(6)- 1)^2  + LOG(X(7)+1 )
333 PD1= PDA +PN(8)+PN(9)+PN(10)+PN(11)+PN(12)+PN(13)+PN(14)+PN(15)+PN(16)
335 PDU=+PD1
466 P=PDU
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 7
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1511 REM NN(7)=N(7)
1512 NN(8)=N(8)
1513 NN(9)=N(9)
1514 NN(10)=N(10)
1515 NN(11)=N(11)
1516 NN(12)=N(12)
1517 NN(13)=N(13)
1518 NN(14)=N(14)
1519 NN(15)=N(15)
1520 NN(16)=N(16)
1557 GOTO 128
1670 NEXT I
1889 IF M<-4.7 THEN 1999
1904 PRINT A(1),A(2),A(3)
1905 PRINT A(4),A(5),A(6),A(7)
1906 PRINT M,JJJJ
1907 PRINT NN(8),NN(9),NN(10)
1908 PRINT NN(11),NN(12),NN(13)
1909 PRINT NN(14),NN(15),NN(16)
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 produced through JJJJ=-31909 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

.2000000471835003    .7999996324807675   1.907878139806937
1   1   0   1
-4.579583783504305   -31971
5.00215480148114D-10   5.00215480148114D-10   3.198355166822431D-07
5.737255222015847D-07   .5921218601930628   .610001003646821
8.701324166748847D-07   1.180001572804056   9.212218052879495D-02

.1999998784652326    .7999996454669664   1.90787779842476
1   1   0   1
-4.579584767948652   -31922
1.692184832258192D-07   1.692184832258192D-07   3.068493177604825D-07
5.529476133081524D-07   .5921222015752398   .61000230627789
2.17276348574158D-06   1.18000292214451   9.212267764304072D-02

.1999997863589514   .7999999402616476   1.907878280098487
1   1   0   1
-4.579583155718467   -31909
2.613247644667194D-07   2.613247644667194D-07   1.205463662223849D-08
8.127624559484126D-08   .5921217199015132   .61000046832844
3.348140357184448D-07   1.180000649366174   9.212199328091431D-02

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 obtaining the output through JJJJ=-31909  was one minute and a half.

Acknowledgment

I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
 
References

[1] Egon Balas, An Additive Algorithm for Solving Linear Programs with Zero-One Variables. Operations Research, Vol. 13, 517-546 (1965).

[2] Egon Balas, Discrete Programming by the Filter Method. Operations Research, Vol. 15, No. 5 (Sep. - Oct., 1967), pp. 915-957.

[3] J. Bracken, G. P. McCormick, Selected Applications of Nonlinear Programming.  New York: John Wiley and Sons, 1968.

[4] Richard L. Burden, J. Douglas Faires, Numerical Analysis, Ninth Edition.  Brooks/Cole 2011.

[5] S. H. Chew, Q. Zheng, Integral Global Optimization.  Volume 298 of Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, 1988.

[6] William Conley, Computer Optimization Techniques.  New York/Princeton: Petrocelli Books, Inc., 1980.

[7] William Conley, Optimization: A Simplified Approach.  New York/Princeton: Petrocelli Books, Inc., 1981.

[8] William Conley (1982), An Economic Order Quantity Problem.  International Journal of Mathematical Education in Science and Technology, Vol. 13, No. 3, pp. 265-268.

[9] William Conley, Computer Optimization Techniques, Revised Edition.  New York/Princeton: Petrocelli Books, Inc., 1984.

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

[12] R. J. Duffin, E. L. Peterson, C. Zener, Geometric Programming Theory and Applications.  John Wiley and Sons, 1967.

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

[14] Christodoulos A. Floudas, Nonlinear and Mixed-Integer Optimization.  Oxford University Press, 1995.

[15] C. A. Floudas, Deterministic Global Optimization.  Kluwer Academic Publishers, 2000.

[16] R. S. Garfinkel, G. L. Nemhauser, Integer Programming.  John Wiley, Inc. 1972.

[17] Amos Gilat and Vish Subramaniam, Numerical Methods for Engineers and Scientists: An Introduction with Applications Using MATLAB.  John Wiley and Sons, Inc. 2008.

[18] Donald Greenspan, Vincenzo Casulli, Numerical Analysis for Applied Mathematics, Science, and Enginerring.  Addison-Wesley Publishing Company, 1988.

[19] Peter L. Hammer, Sergiu Rudeanu, Boolean Methods in Operations Research and Related Areas.  New York: Springer-Verlag, 1968.

[20] Peter L. Hammer, Sergiu Rudeanu, Psudo-Boolean Programming.  Operations Research, March/April 1969 Vol. 17 No. 2, pp. 233-261.

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

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

[23] Ali Husseinzadeh Kashan (2011), An Efficient Algorithm for Constrained Global Optimization and Application to Mechanical Engineering Design: League Championship Algorithm (LCA).  Computer-Aided Design 43 (2011) 1769-1792.

[24] G. R. Kocis, I. E. Grossmann, Global Optimization of Nonconvex Mixed-Integer Nonlinear Programming Problems in Process Synthesis.  Ind. Eng. Chem. Res., Vol. 27, No. 8, 1988, pages 1407-1421.

[25] G. R. Kocis, I. E. Grossmann, A Modelling amd Decomposition Strategy for MINLP Optimization.  Computers and Chemical Engineering, Vol. 13, No. 7, July 1989, pages 797-819.

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

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

[28] Duan Li, Xiaoling Sun, Nonlinear Integer Programming.  Springer, 2006.

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

[30] Keith Meintjes and Alexander P. Morgan, Chemical Equilibrium Systems as Numerical Test Problems.  ACM Transactions on Mathematical Software, Vol. 16, No. 2, June 1990, Pages 143-151.

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

[32] C. Mohan,  H. T. Nguyen (1999), A Controlled Random Search Technique Incorporating the Simulated Annealing Concept for Solving Integer and Mixed Integer Global Optimization Problems.  
Computational Optimization and Applications, July 1999, Vol. 14 Issue 1, pp.103-132.

[33] Ramon E. Moore, R. Baker Kearfott, Michael J. Cloud, An Introduction to Interval Analysis.  Cambridge University Press, 2009.

[34] Chi-Kong Ng, Lian-Sheng Zhang, Duan Li, Wei-Wen Tian (2005), Discrete Filled Function Method for Discrete Optimization.  Computational Optimization and Applications, 31, pp. 87-115, 2005.

[35] Panos Y. Papalambros, Douglass J. Wilde, Principles of Optimal Design: Modeling and Computation, Second Edition.  Cambridge University Press, 2000.

[36] D. R. Plane, C. McMillan, Discrete Optimization.  Englewood Cliffs: Prentice-Hall, 1971.

[37] John R. Rice, Numerical Methods, Software, and Analysis, Second Edition.  Academic Press, 1993.

[38] H. S. Ryoo, N. V. Sahinidis (1995), Global Optimization of Nonconvex NLPs and MINLPs with Applications in Process Design.  Computers and Chemical Engineering, Vol. 19, No. 5, pp. 551-566, 1995.

[39] Terry Shoup, A Practical Guide to Computer Methods for Engineers.  Englewood Cliffs: Prentice-Hall, 1979.

[40] M. Syslo, N. Deo, J. Kowalik, Discrete Optimization Algorithms with Pascal Programs.  Englewood Cliffs: Prentice-Hall, 1983.

[41] C. A. Trauth, R. E. Woolsey (1969), Integer Linear Programming: A Study in Computational Efficiency.  Management Science, Volume 15, 1969, 481-493.

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

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

[44] Jsun Yui Wong (2011, May 5).  The Domino Method Applied to Solving a Nonlinear System of Five Equations, Third Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/05/05

[45] Jsun Yui Wong (2011, May 15).  The Domino Method Applied to Solving a Nonlinear System of Ten Equations of a Model of Propane-in-Air Combustion, Fourth Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/05/15

[46] Jsun Yui Wong (2012, February 26).  The Domino Method of Nonlinear Discrete Programming Applied to a Small Problem from the Literature.  Retrieved from http://myblogsubstance.typepad.com/substance/2012/02

[47] Jsun Yui Wong (2011, November 20).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Air Transport Model of Markowitz and Manne, Fifth Edition Revisited.  Retrieved from http://myblogsubstance.typepad.com/substance/2011/11

[48] Jsun Yui Wong (2012, April 21).  The Domino Method of General Integer Nonlinear Programming Applied to a Five-Step Cantilever Beam Design.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/04/21/

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

[50] Jsun Yui Wong (2013, January 14).  The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with Integer Variables and Continuous Variables, Revised Edition.   Retrieved from http://myblogsubstance.typepad.com/substance/2013/01

[51] Jsun Yui Wong (2013, January 24).  The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with Eight 0-1 Variables and Nine Continuous Variables.   Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2013/01/24

 [52]  Liexiang Yan, Kun Shen, Shenghua Hu, Solving Mixed Integer Nonlinear Programming Problems with Line-Up Competition Algorithm. Computers and Chemical Engineering, Volume 28, Issue 12, November 2004, pages 2647-2657.

Solving a Complicated Problem with the Domino Method for General Nonlinear Integer Programming

Jsun Yui Wong

The following computer program seeks to solve Example 6 on pages 2652-2653 of Yan, Shen, and Hu [52].  This is a "complicated" problem, Yan, Shen, and Hu [52, p. 2653].

0 DEFDBL A-Z
1 DEFINT I,J,K
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J(99),AA(99),HR(32),HHR(32),LHS(44),PLHS(44),LB(22),UB(22),PX(44),J44(44)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-3E+30
111 FOR J44=1 TO 4
112 A(J44)=RND
113 NEXT J44
121 FOR J44=5 TO 8
122 A(J44)=FIX(RND*5)
123 NEXT J44
126 REM   IMAR=10+FIX(RND*4000)
128 FOR I=1 TO 1000
129 FOR KKQQ=1 TO 8
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
139 FOR IPP=1 TO FIX(1+RND*3)
140 B=1+FIX(RND*8)
160 R=(1-RND*2)*A(B)
164 X(B)=A(B)+(RND^3*R)
166 IF B>4.5 THEN 168 ELSE 178
168 X(B)=CINT(X(B))
178 NEXT IPP
181 X(2)=1-X(1)
183 X(4)=       X(1)+X(2)-X(3)
187 N(9)=    -4+  X( 5 ) +X( 6 )
189 N(10)=    -4+  X( 7 ) +X( 8 )
251 FOR J44=1 TO 8
252 IF X(J44)<0 THEN 1670
253 NEXT J44
261 FOR J44=5 TO 8
262 IF X(J44)>4.00001 THEN 1670
263 NEXT J44
271 IF X(5)<4*X(1)-.00001 THEN 1670
272 IF X(6)<4*X(2)-.00001 THEN 1670
273 IF X(7)<4*X(3)-.00001 THEN 1670
274 IF X(8)<4*X(4)-.00001 THEN 1670
318 FOR J44= 9 TO 10
319 IF N(J44)<0 THEN PN(J44)=1000000!*N(J44) ELSE PN(J44)=0
320 NEXT J44
322 PDA=-(  2.1*EXP(X(5))  -3*LOG(11*X(1)     )          )
323 PDB=-(.1*EXP(X(6))  -1*LOG(11*X(2)     )            )
324 PDC=-(4.1*EXP(X(7))  -3*LOG(11*X(3)     )          )
325 PDD=-(.1*EXP(X(8))  -4*LOG(11*X(4)     )          )
327 PDT=PDA+PDB+PDC+PDD
333 PD1= PDT +PN(9)+PN(10)
335 PDU=+PD1
466 P=PDU
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 8
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1513 NN(9)=N(9)
1514 NN(10)=N(10)
1557 GOTO 128
1670 NEXT I
1889 IF M<-5 THEN 1999
1904 PRINT A(1),A(2),A(3),A(4)
1905 PRINT A(5),A(6),A(7),A(8)
1906 PRINT M,JJJJ
1909 PRINT NN(9),NN(10)
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 produced through JJJJ=-30781 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

.2500020900811729   .7499979099188271   .2500021522094225
.7499978477905775
1   3   1   3
-4.249746148642606   -31491
0   0

.2500022860377385   .7499977139622615   .2500020525933064
.7499979474066936
1   3   1   3
-4.249744722556481   -31269
0   0

.250002446274809   .749997553725191   .2500022927616655
.7499977072383345
1   3   1   3
-4.249741412286298   -30781
0   0

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 obtaining the output through JJJJ=-30781  was two minutes and a half.

Acknowledgment

I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
 
References

[1] Egon Balas, An Additive Algorithm for Solving Linear Programs with Zero-One Variables. Operations Research, Vol. 13, 517-546 (1965).

[2] Egon Balas, Discrete Programming by the Filter Method. Operations Research, Vol. 15, No. 5 (Sep. - Oct., 1967), pp. 915-957.

[3] J. Bracken, G. P. McCormick, Selected Applications of Nonlinear Programming.  New York: John Wiley and Sons, 1968.

[4] Richard L. Burden, J. Douglas Faires, Numerical Analysis, Ninth Edition.  Brooks/Cole 2011.

[5] S. H. Chew, Q. Zheng, Integral Global Optimization.  Volume 298 of Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, 1988.

[6] William Conley, Computer Optimization Techniques.  New York/Princeton: Petrocelli Books, Inc., 1980.

[7] William Conley, Optimization: A Simplified Approach.  New York/Princeton: Petrocelli Books, Inc., 1981.

[8] William Conley (1982), An Economic Order Quantity Problem.  International Journal of Mathematical Education in Science and Technology, Vol. 13, No. 3, pp. 265-268.

[9] William Conley, Computer Optimization Techniques, Revised Edition.  New York/Princeton: Petrocelli Books, Inc., 1984.

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

[12] R. J. Duffin, E. L. Peterson, C. Zener, Geometric Programming Theory and Applications.  John Wiley and Sons, 1967.

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

[14] Christodoulos A. Floudas, Nonlinear and Mixed-Integer Optimization.  Oxford University Press, 1995.

[15] C. A. Floudas, Deterministic Global Optimization.  Kluwer Academic Publishers, 2000.

[16] R. S. Garfinkel, G. L. Nemhauser, Integer Programming.  John Wiley, Inc. 1972.

[17] Amos Gilat and Vish Subramaniam, Numerical Methods for Engineers and Scientists: An Introduction with Applications Using MATLAB.  John Wiley and Sons, Inc. 2008.

[18] Donald Greenspan, Vincenzo Casulli, Numerical Analysis for Applied Mathematics, Science, and Enginerring.  Addison-Wesley Publishing Company, 1988.

[19] Peter L. Hammer, Sergiu Rudeanu, Boolean Methods in Operations Research and Related Areas.  New York: Springer-Verlag, 1968.

[20] Peter L. Hammer, Sergiu Rudeanu, Psudo-Boolean Programming.  Operations Research, March/April 1969 Vol. 17 No. 2, pp. 233-261.

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

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

[23] Ali Husseinzadeh Kashan (2011), An Efficient Algorithm for Constrained Global Optimization and Application to Mechanical Engineering Design: League Championship Algorithm (LCA).  Computer-Aided Design 43 (2011) 1769-1792.

[24] G. R. Kocis, I. E. Grossmann, Global Optimization of Nonconvex Mixed-Integer Nonlinear Programming Problems in Process Synthesis.  Ind. Eng. Chem. Res., Vol. 27, No. 8, 1988, pages 1407-1421.

[25] G. R. Kocis, I. E. Grossmann, A Modelling amd Decomposition Strategy for MINLP Optimization.  Computers and Chemical Engineering, Vol. 13, No. 7, July 1989, pages 797-819.

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

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

[28] Duan Li, Xiaoling Sun, Nonlinear Integer Programming.  Springer, 2006.

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

[30] Keith Meintjes and Alexander P. Morgan, Chemical Equilibrium Systems as Numerical Test Problems.  ACM Transactions on Mathematical Software, Vol. 16, No. 2, June 1990, Pages 143-151.

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

[32] C. Mohan,  H. T. Nguyen (1999), A Controlled Random Search Technique Incorporating the Simulated Annealing Concept for Solving Integer and Mixed Integer Global Optimization Problems.  
Computational Optimization and Applications, July 1999, Vol. 14 Issue 1, pp.103-132.

[33] Ramon E. Moore, R. Baker Kearfott, Michael J. Cloud, An Introduction to Interval Analysis.  Cambridge University Press, 2009.

[34] Chi-Kong Ng, Lian-Sheng Zhang, Duan Li, Wei-Wen Tian (2005), Discrete Filled Function Method for Discrete Optimization.  Computational Optimization and Applications, 31, pp. 87-115, 2005.

[35] Panos Y. Papalambros, Douglass J. Wilde, Principles of Optimal Design: Modeling and Computation, Second Edition.  Cambridge University Press, 2000.

[36] D. R. Plane, C. McMillan, Discrete Optimization.  Englewood Cliffs: Prentice-Hall, 1971.

[37] John R. Rice, Numerical Methods, Software, and Analysis, Second Edition.  Academic Press, 1993.

[38] H. S. Ryoo, N. V. Sahinidis (1995), Global Optimization of Nonconvex NLPs and MINLPs with Applications in Process Design.  Computers and Chemical Engineering, Vol. 19, No. 5, pp. 551-566, 1995.

[39] Terry Shoup, A Practical Guide to Computer Methods for Engineers.  Englewood Cliffs: Prentice-Hall, 1979.

[40] M. Syslo, N. Deo, J. Kowalik, Discrete Optimization Algorithms with Pascal Programs.  Englewood Cliffs: Prentice-Hall, 1983.

[41] C. A. Trauth, R. E. Woolsey (1969), Integer Linear Programming: A Study in Computational Efficiency.  Management Science, Volume 15, 1969, 481-493.

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

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

[44] Jsun Yui Wong (2011, May 5).  The Domino Method Applied to Solving a Nonlinear System of Five Equations, Third Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/05/05

[45] Jsun Yui Wong (2011, May 15).  The Domino Method Applied to Solving a Nonlinear System of Ten Equations of a Model of Propane-in-Air Combustion, Fourth Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/05/15

[46] Jsun Yui Wong (2012, February 26).  The Domino Method of Nonlinear Discrete Programming Applied to a Small Problem from the Literature.  Retrieved from http://myblogsubstance.typepad.com/substance/2012/02

[47] Jsun Yui Wong (2011, November 20).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Air Transport Model of Markowitz and Manne, Fifth Edition Revisited.  Retrieved from http://myblogsubstance.typepad.com/substance/2011/11

[48] Jsun Yui Wong (2012, April 21).  The Domino Method of General Integer Nonlinear Programming Applied to a Five-Step Cantilever Beam Design.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/04/21/

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

[50] Jsun Yui Wong (2013, January 14).  The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with Integer Variables and Continuous Variables, Revised Edition.   Retrieved from http://myblogsubstance.typepad.com/substance/2013/01

[51] Jsun Yui Wong (2013, January 24).  The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with Eight 0-1 Variables and Nine Continuous Variables.   Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2013/01/24

 [52]  Liexiang Yan, Kun Shen, Shenghua Hu, Solving Mixed Integer Nonlinear Programming Problems with Line-Up Competition Algorithm.  Computers and Chemical Engineering, Volume 28, Issue 12, November 2004, pages 2647-2657.

Still Testing the Algorithm Presented Here

Jsun Yui Wong

The following computer program uses Example 5.6 on pages 101-105 of Conley [7] to test the present algorithm for its level of computational accuracy.  The computer program below is interested in integer solutions only.

0 DEFDBL A-Z
1 DEFINT I,J,K
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J(99),AA(99),HR(32),HHR(32),LHS(44),PLHS(44),LB(22),UB(22),PX(44),J44(44)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-3E+30
101 A(1)=5+FIX(RND*11)
102 A(2)=85+FIX(RND*66)
103 A(3)=60+FIX(RND*121)
104 A(4)=4+FIX(RND*17)
105 A(5)=0+FIX(RND*101)
106 A(6)=0+FIX(RND*(A(3)+1)   )
126 REM   IMAR=10+FIX(RND*4000)
128 FOR I=1 TO 5000
129 FOR KKQQ=1 TO 6
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
139 FOR IPP=1 TO FIX(1+RND*3)
140 B=1+FIX(RND*6)
160 R=(1-RND*2)*A(B)
164 X(B)=A(B)+(RND^3*R)
167 X(B)=CINT(X(B)  )
168 NEXT IPP
301 IF X(1)<5 THEN 1670
302 IF X(2)<85 THEN 1670
303 IF X(3)<60 THEN 1670
304 IF X(4)<4 THEN 1670
305 IF X(5)<0 THEN 1670
306 IF X(6)<0 THEN 1670
311 IF X(1)>15 THEN 1670
312 IF X(2)>150 THEN 1670
313 IF X(3)>180 THEN 1670
314 IF X(4)>20 THEN 1670
315 IF X(5)>100 THEN 1670
316 IF X(6)>X(3) THEN 1670
323 PDB=-1#*X(1)^4+40#*X(1)^3-600#*X(1)^2-1.04#*X(2)^2+253#*X(2)-.98#*X(3)^2+200#*X(3)-.95#*X(4)^2+19#*X(4)-.88#*X(5)^2+81#*X(5)-X(6)^2+100#*X(6)    +3937000!
324 PDC=4000#*X(1)+.045#*X(1)*X(3)+.025#*X(4)*X(5)+.07#*X(2)*X(3)                 -.03#*X(3)*X(6)
333 PD1=  +PDB +PDC
335 PDU=+PD1
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<0 THEN 1999
1904 PRINT A(1),A(2),A(3),A(4),A(5)
1905 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=-31996 is presented below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

11   125   106   11   46
48   3977856.67   -32000

11   125   106   11   46
48   3977856.67   -31999

11   125   106   11   46
48   3977856.67   -31998

11   125   106   11   46
48   3977856.67   -31997

11   125   106   11   46
48   3977856.67   -31996

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 obtaining the output through JJJJ=-31996  was three seconds.

Acknowledgment

I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
 
References

[1] Egon Balas, An Additive Algorithm for Solving Linear Programs with Zero-One Variables. Operations Research, Vol. 13, 517-546 (1965).

[2] Egon Balas, Discrete Programming by the Filter Method. Operations Research, Vol. 15, No. 5 (Sep. - Oct., 1967), pp. 915-957.

[3] J. Bracken, G. P. McCormick, Selected Applications of Nonlinear Programming.  New York: John Wiley and Sons, 1968.

[4] Richard L. Burden, J. Douglas Faires, Numerical Analysis, Ninth Edition.  Brooks/Cole 2011.

[5] S. H. Chew, Q. Zheng, Integral Global Optimization.  Volume 298 of Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, 1988.

[6] William Conley, Computer Optimization Techniques.  New York/Princeton: Petrocelli Books, Inc., 1980.

[7] William Conley, Optimization: A Simplified Approach.  New York/Princeton: Petrocelli Books, Inc., 1981.

[8] William Conley (1982), An Economic Order Quantity Problem.  International Journal of Mathematical Education in Science and Technology, Vol. 13, No. 3, pp. 265-268.

[9] William Conley, Computer Optimization Techniques, Revised Edition.  New York/Princeton: Petrocelli Books, Inc., 1984.

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

[12] R. J. Duffin, E. L. Peterson, C. Zener, Geometric Programming Theory and Applications.  John Wiley and Sons, 1967.

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

[14] Christodoulos A. Floudas, Nonlinear and Mixed-Integer Optimization.  Oxford University Press, 1995.

[15] C. A. Floudas, Deterministic Global Optimization.  Kluwer Academic Publishers, 2000.

[16] R. S. Garfinkel, G. L. Nemhauser, Integer Programming.  John Wiley, Inc. 1972.

[17] Amos Gilat and Vish Subramaniam, Numerical Methods for Engineers and Scientists: An Introduction with Applications Using MATLAB.  John Wiley and Sons, Inc. 2008.

[18] Donald Greenspan, Vincenzo Casulli, Numerical Analysis for Applied Mathematics, Science, and Enginerring.  Addison-Wesley Publishing Company, 1988.

[19] Peter L. Hammer, Sergiu Rudeanu, Boolean Methods in Operations Research and Related Areas.  New York: Springer-Verlag, 1968.

[20] Peter L. Hammer, Sergiu Rudeanu, Psudo-Boolean Programming.  Operations Research, March/April 1969 Vol. 17 No. 2, pp. 233-261.

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

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

[23] Ali Husseinzadeh Kashan (2011), An Efficient Algorithm for Constrained Global Optimization and Application to Mechanical Engineering Design: League Championship Algorithm (LCA).  Computer-Aided Design 43 (2011) 1769-1792.

[24] G. R. Kocis, I. E. Grossmann, Global Optimization of Nonconvex Mixed-Integer Nonlinear Programming Problems in Process Synthesis.  Ind. Eng. Chem. Res., Vol. 27, No. 8, 1988, pages 1407-1421.

[25] G. R. Kocis, I. E. Grossmann, A Modelling amd Decomposition Strategy for MINLP Optimization.  Computers and Chemical Engineering, Vol. 13, No. 7, July 1989, pages 797-819.

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

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

[28] Duan Li, Xiaoling Sun, Nonlinear Integer Programming.  Springer, 2006.

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

[30] Keith Meintjes and Alexander P. Morgan, Chemical Equilibrium Systems as Numerical Test Problems.  ACM Transactions on Mathematical Software, Vol. 16, No. 2, June 1990, Pages 143-151.

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

[32] C. Mohan,  H. T. Nguyen (1999), A Controlled Random Search Technique Incorporating the Simulated Annealing Concept for Solving Integer and Mixed Integer Global Optimization Problems.  
Computational Optimization and Applications, July 1999, Vol. 14 Issue 1, pp.103-132.

[33] Ramon E. Moore, R. Baker Kearfott, Michael J. Cloud, An Introduction to Interval Analysis.  Cambridge University Press, 2009.

[34] Chi-Kong Ng, Lian-Sheng Zhang, Duan Li, Wei-Wen Tian (2005), Discrete Filled Function Method for Discrete Optimization.  Computational Optimization and Applications, 31, pp. 87-115, 2005.

[35] Panos Y. Papalambros, Douglass J. Wilde, Principles of Optimal Design: Modeling and Computation, Second Edition.  Cambridge University Press, 2000.

[36] D. R. Plane, C. McMillan, Discrete Optimization.  Englewood Cliffs: Prentice-Hall, 1971.

[37] John R. Rice, Numerical Methods, Software, and Analysis, Second Edition.  Academic Press, 1993.

[38] H. S. Ryoo, N. V. Sahinidis (1995), Global Optimization of Nonconvex NLPs and MINLPs with Applications in Process Design.  Computers and Chemical Engineering, Vol. 19, No. 5, pp. 551-566, 1995.

[39] Terry Shoup, A Practical Guide to Computer Methods for Engineers.  Englewood Cliffs: Prentice-Hall, 1979.

[40] M. Syslo, N. Deo, J. Kowalik, Discrete Optimization Algorithms with Pascal Programs.  Englewood Cliffs: Prentice-Hall, 1983.

[41] C. A. Trauth, R. E. Woolsey (1969), Integer Linear Programming: A Study in Computational Efficiency.  Management Science, Volume 15, 1969, 481-493.

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

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

[44] Jsun Yui Wong (2011, May 5).  The Domino Method Applied to Solving a Nonlinear System of Five Equations, Third Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/05/05

[45] Jsun Yui Wong (2011, May 15).  The Domino Method Applied to Solving a Nonlinear System of Ten Equations of a Model of Propane-in-Air Combustion, Fourth Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/05/15

[46] Jsun Yui Wong (2012, February 26).  The Domino Method of Nonlinear Discrete Programming Applied to a Small Problem from the Literature.  Retrieved from http://myblogsubstance.typepad.com/substance/2012/02

[47] Jsun Yui Wong (2011, November 20).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Air Transport Model of Markowitz and Manne, Fifth Edition Revisited.  Retrieved from http://myblogsubstance.typepad.com/substance/2011/11

[48] Jsun Yui Wong (2012, April 21).  The Domino Method of General Integer Nonlinear Programming Applied to a Five-Step Cantilever Beam Design.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/04/21/

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

[50] Jsun Yui Wong (2013, January 14).  The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with Integer Variables and Continuous Variables, Revised Edition.   Retrieved from http://myblogsubstance.typepad.com/substance/2013/01

[51] Jsun Yui Wong (2013, January 24).  The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with Eight 0-1 Variables and Nine Continuous Variables.   Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2013/01/24

 

Solving a Production Planning Problem with the Domino Method for General Nonlinear Integer Programming

Jsun Yui Wong

The following computer program seeks to solve the production planning problem on pages 161-163 of Conley [7].  The computer program below is interested in integer solutions only.  Its line 112, which is 112 A(J44)=FIX(RND*50), is noteworthy; N(7), N(8), and N(9) of line 201, line 205, and line 209, respectively, are slack variables.

0 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),J(99),AA(99),HR(32),HHR(32),LHS(44),PLHS(44),LB(22),UB(22),PX(44),J44(44)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-3E+30
111 FOR J44=1 TO 6
112 A(J44)=FIX(RND*50)
113 NEXT J44
126 REM   IMAR=10+FIX(RND*4000)
128 FOR I=1 TO 5000
129 FOR KKQQ=1 TO 6
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
139 FOR IPP=1 TO FIX(1+RND*3)
140 B=1+FIX(RND*6)
160 R=(1-RND*2)*A(B)
161 REM IF RND<.5 THEN 162 ELSE 164
162 IF RND<.5 THEN X(B)=A(B)-RND*50 ELSE X(B)=A(B)+RND*50
163 GOTO 171
164 X(B)=A(B)+(RND^3*R)
167 REM X(B)=CINT(X(B)  )
171 IF X(1)>.5 THEN X(3)=1 ELSE X(3)  = 0
173 IF X(2)>.5 THEN X(4)=1 ELSE X(4)  = 0
178 NEXT IPP
201 N(7)=80000!-2*X(1)-X(2)
205 N(8)=100000!-3*X(1)-2.5*X(2)
209 N(9)=120000!-1.9*X(1)-3*X(2)
301 IF X(1)<0 THEN 1670
302 IF X(2)<0 THEN 1670
303 IF X(3)<0 THEN 1670
304 IF X(4)<0 THEN 1670
305 IF X(5)<1 THEN 1670
306 IF X(6)<1 THEN 1670
311 IF X(1)>32000 THEN 1670
312 IF X(2)>32000 THEN 1670
313 IF X(3)>1 THEN 1670
314 IF X(4)>1 THEN 1670
315 IF X(5)>2*X(1) THEN 1670
316 IF X(6)>X(2) THEN 1670
318 FOR J44= 7 TO 9
319 IF N(J44)<0 THEN PN(J44)=1000000!*N(J44) ELSE PN(J44)=0
320 NEXT J44
323 PDB=-.0025*X(1)^2+100*X(1)-10000*X(3)-(100*X(5)/2+50*X(1)/X(5)  ) -2*X(1)
324 PDC=-.002*X(2)^2+120*X(2)-12000*X(4)-(80*X(6)/2+35*X(2)/X(6)  ) -2.4*X(2)
325 REM   PDD= X(1)*X(9)+X(1)*X(10)+X(2)*X(10)+X(1)*X(5)+X(4)*X(7)
333 PD1=  +PDB +PDC  +PN(7)+PN(8)+PN(9)
335 PDU=+PD1
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
1511 NN(7)=N(7)
1512 NN(8)=N(8)
1513 NN(9)=N(9)
1557 GOTO 128
1670 NEXT I
1889 IF M<2488750! THEN 1999
1904 PRINT A(1),A(2),A(3),A(4),A(5)
1905 PRINT A(6),M,JJJJ
1909 PRINT NN(7),NN(8),NN(9)
1999 NEXT JJJJ

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

13825   23410   1   1   118
143   2488775.375   -31915
28940   0   23502.5

13820   23416   1   1   118
143   2488775.3125   -31886
28944   0   23494

13825   23410   1   1   118
143   2488775.375   -31884
28940   0   23502.5

13825   23410   1   1   118
143   2488775.375   -31864
28940   0   23502.5

13825   23410   1   1   118
143   2488775.375   -31850
28940   0   23502.5

In the same run, other candidate solutions were also produced.

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 obtaining the output through JJJJ=-31850  was seven minutes.

Acknowledgment

I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
 
References

[1] Egon Balas, An Additive Algorithm for Solving Linear Programs with Zero-One Variables. Operations Research, Vol. 13, 517-546 (1965).

[2] Egon Balas, Discrete Programming by the Filter Method. Operations Research, Vol. 15, No. 5 (Sep. - Oct., 1967), pp. 915-957.

[3] J. Bracken, G. P. McCormick, Selected Applications of Nonlinear Programming.  New York: John Wiley and Sons, 1968.

[4] Richard L. Burden, J. Douglas Faires, Numerical Analysis, Ninth Edition.  Brooks/Cole 2011.

[5] S. H. Chew, Q. Zheng, Integral Global Optimization.  Volume 298 of Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, 1988.

[6] William Conley, Computer Optimization Techniques.  New York/Princeton: Petrocelli Books, Inc., 1980.

[7] William Conley, Optimization: A Simplified Approach.  New York/Princeton: Petrocelli Books, Inc., 1981.

[8] William Conley (1982), An Economic Order Quantity Problem.  International Journal of Mathematical Education in Science and Technology, Vol. 13, No. 3, pp. 265-268.

[9] William Conley, Computer Optimization Techniques, Revised Edition.  New York/Princeton: Petrocelli Books, Inc., 1984.

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

[12] R. J. Duffin, E. L. Peterson, C. Zener, Geometric Programming Theory and Applications.  John Wiley and Sons, 1967.

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

[14] Christodoulos A. Floudas, Nonlinear and Mixed-Integer Optimization.  Oxford University Press, 1995.

[15] C. A. Floudas, Deterministic Global Optimization.  Kluwer Academic Publishers, 2000.

[16] R. S. Garfinkel, G. L. Nemhauser, Integer Programming.  John Wiley, Inc. 1972.

[17] Amos Gilat and Vish Subramaniam, Numerical Methods for Engineers and Scientists: An Introduction with Applications Using MATLAB.  John Wiley and Sons, Inc. 2008.

[18] Donald Greenspan, Vincenzo Casulli, Numerical Analysis for Applied Mathematics, Science, and Enginerring.  Addison-Wesley Publishing Company, 1988.

[19] Peter L. Hammer, Sergiu Rudeanu, Boolean Methods in Operations Research and Related Areas.  New York: Springer-Verlag, 1968.

[20] Peter L. Hammer, Sergiu Rudeanu, Psudo-Boolean Programming.  Operations Research, March/April 1969 Vol. 17 No. 2, pp. 233-261.

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

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

[23] Ali Husseinzadeh Kashan (2011), An Efficient Algorithm for Constrained Global Optimization and Application to Mechanical Engineering Design: League Championship Algorithm (LCA).  Computer-Aided Design 43 (2011) 1769-1792.

[24] G. R. Kocis, I. E. Grossmann, Global Optimization of Nonconvex Mixed-Integer Nonlinear Programming Problems in Process Synthesis.  Ind. Eng. Chem. Res., Vol. 27, No. 8, 1988, pages 1407-1421.

[25] G. R. Kocis, I. E. Grossmann, A Modelling amd Decomposition Strategy for MINLP Optimization.  Computers and Chemical Engineering, Vol. 13, No. 7, July 1989, pages 797-819.

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

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

[28] Duan Li, Xiaoling Sun, Nonlinear Integer Programming.  Springer, 2006.

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

[30] Keith Meintjes and Alexander P. Morgan, Chemical Equilibrium Systems as Numerical Test Problems.  ACM Transactions on Mathematical Software, Vol. 16, No. 2, June 1990, Pages 143-151.

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

[32] C. Mohan,  H. T. Nguyen (1999), A Controlled Random Search Technique Incorporating the Simulated Annealing Concept for Solving Integer and Mixed Integer Global Optimization Problems.  
Computational Optimization and Applications, July 1999, Vol. 14 Issue 1, pp.103-132.

[33] Ramon E. Moore, R. Baker Kearfott, Michael J. Cloud, An Introduction to Interval Analysis.  Cambridge University Press, 2009.

[34] Chi-Kong Ng, Lian-Sheng Zhang, Duan Li, Wei-Wen Tian (2005), Discrete Filled Function Method for Discrete Optimization.  Computational Optimization and Applications, 31, pp. 87-115, 2005.

[35] Panos Y. Papalambros, Douglass J. Wilde, Principles of Optimal Design: Modeling and Computation, Second Edition.  Cambridge University Press, 2000.

[36] D. R. Plane, C. McMillan, Discrete Optimization.  Englewood Cliffs: Prentice-Hall, 1971.

[37] John R. Rice, Numerical Methods, Software, and Analysis, Second Edition.  Academic Press, 1993.

[38] H. S. Ryoo, N. V. Sahinidis (1995), Global Optimization of Nonconvex NLPs and MINLPs with Applications in Process Design.  Computers and Chemical Engineering, Vol. 19, No. 5, pp. 551-566, 1995.

[39] Terry Shoup, A Practical Guide to Computer Methods for Engineers.  Englewood Cliffs: Prentice-Hall, 1979.

[40] M. Syslo, N. Deo, J. Kowalik, Discrete Optimization Algorithms with Pascal Programs.  Englewood Cliffs: Prentice-Hall, 1983.

[41] C. A. Trauth, R. E. Woolsey (1969), Integer Linear Programming: A Study in Computational Efficiency.  Management Science, Volume 15, 1969, 481-493.

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

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

[44] Jsun Yui Wong (2011, May 5).  The Domino Method Applied to Solving a Nonlinear System of Five Equations, Third Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/05/05

[45] Jsun Yui Wong (2011, May 15).  The Domino Method Applied to Solving a Nonlinear System of Ten Equations of a Model of Propane-in-Air Combustion, Fourth Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/05/15

[46] Jsun Yui Wong (2012, February 26).  The Domino Method of Nonlinear Discrete Programming Applied to a Small Problem from the Literature.  Retrieved from http://myblogsubstance.typepad.com/substance/2012/02

[47] Jsun Yui Wong (2011, November 20).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Air Transport Model of Markowitz and Manne, Fifth Edition Revisited.  Retrieved from http://myblogsubstance.typepad.com/substance/2011/11

[48] Jsun Yui Wong (2012, April 21).  The Domino Method of General Integer Nonlinear Programming Applied to a Five-Step Cantilever Beam Design.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/04/21/

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

[50] Jsun Yui Wong (2013, January 14).  The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with Integer Variables and Continuous Variables, Revised Edition.   Retrieved from http://myblogsubstance.typepad.com/substance/2013/01

[51] Jsun Yui Wong (2013, January 24).  The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with Eight 0-1 Variables and Nine Continuous Variables.   Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2013/01/24

 

Again Testing the Algorithm Presented Here

Again Testing the Algorithm Presented Here

Jsun Yui Wong

The following computer program uses the example on pages 147-159 of Conley [9] to test the present algorithm for its level of computational accuracy.   The test problem is to maximize 4000000-(X(1)-70)^2-(X(2)-70)^2-(X(3)-70)^2-(X(4)-70)^2-(X(5)-70)^2-(X(6)-70)^2-(X(7)-70)^2-(X(8)-70)^2-(X(9)-70)^2    -(X(10)-70)^2         -( X(11)-70  )^2  -(  X(12)-70)^2.

 Line 101, which is 101 A(J44)=-1000+FIX(RND*2001), is noteworthy.

0 DEFDBL A-Z
1 DEFINT I,J,K,A,X
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J(99),AA(99),HR(32),HHR(32),LHS(44),PLHS(44),LB(22),UB(22),PX(44),J44(44)
4 REM    DIM PE(35,35)
5 REM    DIM SD(35,35)
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-3E+30
100 FOR J44=1 TO 12
101 A(J44)=-1000+FIX(RND*2001)
102 NEXT J44
126 REM   IMAR=10+FIX(RND*4000)
128 FOR I=1 TO 1000
129 FOR KKQQ=1 TO 12
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
139 FOR IPP=1 TO FIX(1+RND*3)
140 B=1+FIX(RND*12)
160 R=(1-RND*2)*A(B)
161 IF RND<.5 THEN 162 ELSE 164
162 IF RND<.5 THEN X(B)=A(B)-RND*5 ELSE X(B)=A(B)+RND*5
163 GOTO 168
164 X(B)=A(B)+(RND^3*R)
166 REM IF B=1 OR B=2 OR B=3 OR B=8 OR B=9 THEN 167 ELSE 168
167 REM X(B)=CINT(X(B)  )
168 NEXT IPP
323 PDB=4000000#-(X(1)-70)^2-(X(2)-70)^2-(X(3)-70)^2-(X(4)-70)^2-(X(5)-70)^2-(X(6)-70)^2-(X(7)-70)^2-(X(8)-70)^2-(X(9)-70)^2    -(X(10)-70)^2         -( X(11)-70  )^2  -(  X(12)-70)^2
333 PD1=  +PDB
335 PDU=+PD1
466 P=PDU
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 12
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<0 THEN 1999
1904 PRINT A(1),A(2),A(3),A(4),A(5)
1905 PRINT A(6),A(7),A(8),A(9),A(10)
1909 PRINT A(11),A(12),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 produced through JJJJ=-31997 is shown below.  What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.

70   70   70   70   70
70   70   70   70   70
70   70   4000000   -32000

70   70   70   70   70
70   70   70   70   70
70   70   4000000   -31999

70   70   70   70   70
70   70   70   70   70
70   70   4000000   -31998

70   70   70   70   70
70   70   70   70   70
70   70   4000000   -31997

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 obtaining the output through JJJJ=-31997  was one second.

Acknowledgment

I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
 
References

[1] Egon Balas, An Additive Algorithm for Solving Linear Programs with Zero-One Variables. Operations Research, Vol. 13, 517-546 (1965).

[2] Egon Balas, Discrete Programming by the Filter Method. Operations Research, Vol. 15, No. 5 (Sep. - Oct., 1967), pp. 915-957.

[3] J. Bracken, G. P. McCormick, Selected Applications of Nonlinear Programming.  New York: John Wiley and Sons, 1968.

[4] Richard L. Burden, J. Douglas Faires, Numerical Analysis, Ninth Edition.  Brooks/Cole 2011.

[5] S. H. Chew, Q. Zheng, Integral Global Optimization.  Volume 298 of Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, 1988.

[6] William Conley, Computer Optimization Techniques.  New York/Princeton: Petrocelli Books, Inc., 1980.

[7] William Conley, Optimization: A Simplified Approach.  New York/Princeton: Petrocelli Books, Inc., 1981.

[8] William Conley (1982), An Economic Order Quantity Problem.  International Journal of Mathematical Education in Science and Technology, Vol. 13, No. 3, pp. 265-268.

[9] William Conley, Computer Optimization Techniques, Revised Edition.  New York/Princeton: Petrocelli Books, Inc., 1984.

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

[12] R. J. Duffin, E. L. Peterson, C. Zener, Geometric Programming Theory and Applications.  John Wiley and Sons, 1967.

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

[14] Christodoulos A. Floudas, Nonlinear and Mixed-Integer Optimization.  Oxford University Press, 1995.

[15] C. A. Floudas, Deterministic Global Optimization.  Kluwer Academic Publishers, 2000.

[16] R. S. Garfinkel, G. L. Nemhauser, Integer Programming.  John Wiley, Inc. 1972.

[17] Amos Gilat and Vish Subramaniam, Numerical Methods for Engineers and Scientists: An Introduction with Applications Using MATLAB.  John Wiley and Sons, Inc. 2008.

[18] Donald Greenspan, Vincenzo Casulli, Numerical Analysis for Applied Mathematics, Science, and Enginerring.  Addison-Wesley Publishing Company, 1988.

[19] Peter L. Hammer, Sergiu Rudeanu, Boolean Methods in Operations Research and Related Areas.  New York: Springer-Verlag, 1968.

[20] Peter L. Hammer, Sergiu Rudeanu, Psudo-Boolean Programming.  Operations Research, March/April 1969 Vol. 17 No. 2, pp. 233-261.

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

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

[23] Ali Husseinzadeh Kashan (2011), An Efficient Algorithm for Constrained Global Optimization and Application to Mechanical Engineering Design: League Championship Algorithm (LCA).  Computer-Aided Design 43 (2011) 1769-1792.

[24] G. R. Kocis, I. E. Grossmann, Global Optimization of Nonconvex Mixed-Integer Nonlinear Programming Problems in Process Synthesis.  Ind. Eng. Chem. Res., Vol. 27, No. 8, 1988, pages 1407-1421.

[25] G. R. Kocis, I. E. Grossmann, A Modelling amd Decomposition Strategy for MINLP Optimization.  Computers and Chemical Engineering, Vol. 13, No. 7, July 1989, pages 797-819.

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

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

[28] Duan Li, Xiaoling Sun, Nonlinear Integer Programming.  Springer, 2006.

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

[30] Keith Meintjes and Alexander P. Morgan, Chemical Equilibrium Systems as Numerical Test Problems.  ACM Transactions on Mathematical Software, Vol. 16, No. 2, June 1990, Pages 143-151.

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

[32] C. Mohan,  H. T. Nguyen (1999), A Controlled Random Search Technique Incorporating the Simulated Annealing Concept for Solving Integer and Mixed Integer Global Optimization Problems.  
Computational Optimization and Applications, July 1999, Vol. 14 Issue 1, pp.103-132.

[33] Ramon E. Moore, R. Baker Kearfott, Michael J. Cloud, An Introduction to Interval Analysis.  Cambridge University Press, 2009.

[34] Chi-Kong Ng, Lian-Sheng Zhang, Duan Li, Wei-Wen Tian (2005), Discrete Filled Function Method for Discrete Optimization.  Computational Optimization and Applications, 31, pp. 87-115, 2005.

[35] Panos Y. Papalambros, Douglass J. Wilde, Principles of Optimal Design: Modeling and Computation, Second Edition.  Cambridge University Press, 2000.

[36] D. R. Plane, C. McMillan, Discrete Optimization.  Englewood Cliffs: Prentice-Hall, 1971.

[37] John R. Rice, Numerical Methods, Software, and Analysis, Second Edition.  Academic Press, 1993.

[38] H. S. Ryoo, N. V. Sahinidis (1995), Global Optimization of Nonconvex NLPs and MINLPs with Applications in Process Design.  Computers and Chemical Engineering, Vol. 19, No. 5, pp. 551-566, 1995.

[39] Terry Shoup, A Practical Guide to Computer Methods for Engineers.  Englewood Cliffs: Prentice-Hall, 1979.

[40] M. Syslo, N. Deo, J. Kowalik, Discrete Optimization Algorithms with Pascal Programs.  Englewood Cliffs: Prentice-Hall, 1983.

[41] C. A. Trauth, R. E. Woolsey (1969), Integer Linear Programming: A Study in Computational Efficiency.  Management Science, Volume 15, 1969, 481-493.

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

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

[44] Jsun Yui Wong (2011, May 5).  The Domino Method Applied to Solving a Nonlinear System of Five Equations, Third Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/05/05

[45] Jsun Yui Wong (2011, May 15).  The Domino Method Applied to Solving a Nonlinear System of Ten Equations of a Model of Propane-in-Air Combustion, Fourth Edition.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/05/15

[46] Jsun Yui Wong (2012, February 26).  The Domino Method of Nonlinear Discrete Programming Applied to a Small Problem from the Literature.  Retrieved from http://myblogsubstance.typepad.com/substance/2012/02

[47] Jsun Yui Wong (2011, November 20).  A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Air Transport Model of Markowitz and Manne, Fifth Edition Revisited.  Retrieved from http://myblogsubstance.typepad.com/substance/2011/11

[48] Jsun Yui Wong (2012, April 21).  The Domino Method of General Integer Nonlinear Programming Applied to a Five-Step Cantilever Beam Design.  Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/04/21/

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

[50] Jsun Yui Wong (2013, January 14).  The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with Integer Variables and Continuous Variables, Revised Edition.   Retrieved from http://myblogsubstance.typepad.com/substance/2013/01

[51] Jsun Yui Wong (2013, January 24).  The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Programming Problem with Eight 0-1 Variables and Nine Continuous Variables.   Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2013/01/24