Jsun Yui Wong
Modeled after the computer program in Wong [21], the following computer program seeks to solve the 25-city traveling salesperson problem in Held and Karp [8, p. 207]. Line 21 through line 1111 of the following computer program partly describe the problem.
Line 91 through line 113 generate a variety of initial solution vectors; different initial solution vectors can produce different levels of domino effect.
One notes that when the number of cities is 20, the number of possible routes is
121,645,100,408,832,000 [Ragsdale [17], p. 385].
0 REM DEFDBL A-Z
2 DEFINT I,J,K,X,A
3 DIM B(5),N(5),A(70),H(5),L(5),U(5),X(70),D(5),P(5),PS(3),AA(55),I(33),J(33)
8 DIM HR(49,49)
11 FOR IZ=0 TO 24
14 FOR JZ=0 TO 24
16 READ HR(IZ,JZ)
18 NEXT JZ
19 NEXT IZ
21 DATA 9999,182,086,129,211,185,185,041,174,106,018,073,186,071,026,233,288,212,201,183,290,208,093,373,453
22 DATA 182,9999,107,142,195,022,050,144,085,165,200,109,167,114,208,128,231,036,144,126,231,045,272,305,396
23 DATA 086,107,9999,167,249,099,099,058,088,151,104,026,100,050,112,208,252,126,167,162,264,122,179,308,417
24 DATA 129,142,167,9999,082,164,115,163,220,023,146,148,276,124,136,270,341,178,254,236,343,187,158,426,506
25 DATA 211,195,249,082,9999,217,175,245,280,105,228,230,349,206,218,323,423,231,336,318,425,240,240,500,588
26 DATA 185,022,099,164,217,9999,072,144,063,187,203,125,145,114,211,119,209,027,122,104,211,023,272,283,374
27 DATA 185,050,099,115,175,072,9999,144,127,138,203,117,199,114,211,167,271,075,184,166,270,085,272,355,436
28 DATA 041,144,058,163,245,144,144,9999,146,140,059,046,158,039,067,210,256,171,169,151,258,167,134,341,421
29 DATA 174,085,088,220,280,063,127,146,9999,237,192,112,082,136,200,120,178,088,079,095,180,065,267,240,343
30 DATA 106,165,151,023,105,187,138,140,237,9999,123,125,251,113,113,275,330,201,243,225,332,210,135,415,495
31 DATA 018,200,104,146,228,203,203,059,192,123,9999,091,204,089,022,251,306,230,219,201,308,226,087,391,471
32 DATA 073,109,026,148,230,125,117,046,112,125,091,9999,126,024,099,186,241,145,154,136,243,148,166,326,406
33 DATA 186,167,100,267,349,145,199,158,082,251,204,126,9999,150,212,158,189,170,096,114,187,147,279,208,321
34 DATA 071,114,050,124,206,114,114,039,136,113,089,024,150,9999,097,162,217,141,130,112,219,137,158,302,382
35 DATA 026,208,112,136,218,211,211,067,200,113,022,099,212,097,9999,259,314,238,227,209,316,234,067,399,479
36 DATA 233,128,208,270,323,119,167,201,120,275,251,186,158,162,259,9999,114,092,068,050,103,108,320,206,279
37 DATA 288,231,252,341,423,209,271,256,178,330,306,241,189,217,314,114,9999,203,099,105,036,186,375,094,165
38 DATA 212,036,126,178,231,027,075,171,088,201,230,145,170,141,238,092,203,9999,116,098,195,023,299,288,368
39 DATA 201,144,167,254,336,122,184,169,079,243,219,154,096,130,227,068,099,116,9999,018,101,099,288,193,264
40 DATA 183,126,162,236,318,104,166,151,095,225,201,136,114,112,209,050,105,098,018,9999,107,081,270,190,270
41 DATA 290,231,264,343,425,211,270,258,180,332,308,243,187,219,316,103,036,195,101,107,9999,188,377,128,195
42 DATA 208,045,122,187,240,023,085,167,065,210,226,148,147,137,234,108,186,023,099,081,188,9999,295,271,351
43 DATA 093,272,179,158,240,272,272,134,267,135,087,166,279,158,067,320,375,299,288,270,377,295,9999,460,540
44 DATA 373,305,308,426,500,283,355,341,240,415,391,326,208,302,399,206,094,288,193,190,128,271,460,9999,113
45 DATA 453,396,417,506,588,374,436,421,343,495,471,406,321,382,479,279,165,368,264,270,195,351,540,113,9999
68 FOR JJJJ=-32000 TO 32000
69 RANDOMIZE JJJJ
70 M=-1D+37
91 A(1)=1:A(2)=2:A(3)=3:A(4)=4:A(5)=5:A(6)=6:A(7)=7:A(8)=8:A(9)=9:A(10)=10
92 A(11)=11:A(12)=12:A(13)=13:A(14)=14:A(15)=15:A(16)=16:A(17)=17:A(18)=18:A(19)=19:A(20)=20
93 A(21)=21:A(22)=22:A(23)=23:A(24)=24
101 FOR J99=1 TO 48
103 J55=1+FIX(RND*24)
105 J66=1+FIX(RND*24)
108 AA(J55)=A(J55)
109 A(J55)=A(J66)
111 A(J66)=AA(J55)
113 NEXT J99
126 REM IMAR=10+FIX(RND*100)
128 FOR I=1 TO 500
129 FOR KKQQ=1 TO 24
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
194 J=1+FIX(RND*24)
196 JJ=1+FIX(RND*24)
198 X(J)=A(JJ)
199 X(JJ)=A(J)
305 PDU=0
311 FOR J88=0 TO 23
315 PDU=PDU- HR(X(J88),X(J88+1))
320 NEXT J88
355 P=PDU- HR(X(24),0)
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 24
1455 A(KLX)= ( X(KLX) )
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1899 IF M<-1722 THEN 2222
1994 PRINT A(1),A(2),A(3),A(4),A(5)
1995 PRINT A(6),A(7),A(8),A(9),A(10)
1996 PRINT A(11),A(12),A(13),A(14),A(15)
1997 PRINT A(16),A(17),A(18),A(19),A(20)
1998 PRINT A(21),A(22),A(23),A(24)
2211 PRINT M,JJJJ
2222 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter. The complete output through JJJJ=-11694 is shown below. What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.
7 13 11 2 12
23 24 16 20 15
19 18 8 5 21
17 1 6 4 3
9 22 14 10
-1719 -24334
10 14 22 9 3
4 6 1 17 21
5 8 18 19 15
20 16 24 23 12
2 11 13 7
-1719 -22813
10 14 22 9 3
4 6 1 5 17
21 8 18 19 15
20 16 24 23 12
2 11 13 7
-1711 -13508
7 13 11 2 12
23 24 16 20 15
19 18 8 21 17
5 1 6 4 3
9 22 14 10
-1711 -11694
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 running through JJJJ=-11694 was 37 minutes.
References
[1] L. L. Barachet (1957), Graphic Solution of the Travelling Salesman Problem. Operations Research, Vol. 5, pp. 841-845.
[2] T. Y. Chen, H. C. Chen (2009), Mixed-Discrete Structural Optimization Using a Rank-Niche Evolution Strategy, Engineering Optimization, 41:1, 39-58.
[3] Leon Cooper, U. N. Bhat, L. J. LeBlanc, Introduction to Operations Researach Models. W. B. Saunders Company, 1977.
[4] George B. Dantzig, Discrete-Variable Extremum Problems. Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.
[5] W. J. Fabrycky, P. M. Ghare, P. E. Torgersen, Applied Operations Research and Management Science. Englewood Cliffs, N. J. 07362: Prentice-Hall, Inc., 1984.
[6] Billy E. Gillett, Introduction to Operations Research: A Computer-Oriented Algorithmic Approach. McGraw-Hill, Inc., 1976.
[7] Martin Grotschel, Olaf Holland (1991), Solution of Large-Scale Symmetric Travelling Salesman Problems, Mathematical Programming 51, pp. 141-202.
[8] Michael Held, Richard Karp (1962), A Dynamic Programming Approach to Sequencing Problems, J. Soc. Indust. Appl. Math., Vol. 10, No. 1, March, 1962, pp. 196-210.
[9] 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.
[10] R. L. Karg, G. L. Thompson (1964), A Heuristic Approach to Solving Travelling Salesman Problems. Management Sciencce, Vol. 10, Number 2, pp. 225-248.
[11] A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems. Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.
[12] 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.
[13] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems. Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.
[14] Ken McAloon, Carol Tretkoff, Optimization and Computational Logic. John Wiley and Sons, Inc., 1996.
[15] 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.
[16] Katta G. Murty, Opereations Research: Deterministic Optimization Models. Prentice Hall, Upper Saddle River, New Jersey 07458, 1994.
[17] Cliff T. Ragsdale, Spreadsheet Modeling and Decision Analysis, Fifth Edition. South-Westen, Cengage Learning, 2008.
[18] H. H. Rosenbrock (1960), An Automatic Method for Finding the Greatest or Least Value of a Function, Computer Journal Vol. 3, pp. 175-184.
[19] Wayne L. Winston, Munirpallam Venkataramanan, Introduction to Mathematical Programming: Operations Research, Volume One, Fourth Edition. Pacific Grove, CA 93950: Brooks/Cole--Thomson Learning, 2003.
[20] Wayne L. Winston, S. Christian Albright, Practical Management Science, Third Edition. Thomson/South-Western, 2007.
[21] Jsun Yui Wong (2011, April 17). The Domino Method of Solving Nonlinear Systems of Equations. Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/04/17/
[22] Ji-Hui Zhang, Xin-He Xu (1999), An Efficient Evoutionary Programming Algorithm. Computers & Operations Research 26, 645-663.
« May 2012 | Main | July 2012 »
June 2012
06/24/2012
Ready-To-Run Computer Program Using the Domino Method of Integer Nonlinear Programming and Solving a 25-City Traveling Salesman Problem
Posted at 10:21 PM | Permalink | Comments (0)
06/22/2012
A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to an Asymmetric Traveling Salesperson Problem
Jsun Yui Wong
Based on the computer program in Wong [20], The following computer program seeks to solve the asymmetric traveling salesperson problem in Fabrycky, Ghare, and Torgersen [5], where the cost matrix is not symmetrical. Line 21 through line 1111 of the following computer program partly describe the problem.
0 REM DEFDBL A-Z
2 DEFINT I,J,K,X,A
3 DIM B(5),N(5),A(70),H(5),L(5),U(5),X(70),D(5),P(5),PS(3),AA(11),I(22),J(22)
8 DIM HR(49,49)
11 FOR IZ=0 TO 5
14 FOR JZ=0 TO 5
16 READ HR(IZ,JZ)
18 NEXT JZ
19 NEXT IZ
21 DATA 9999,20,23,27,29,34
22 DATA 21,9999,19,26,31,24
23 DATA 26,28,9999,15,36,26
24 DATA 25,16,25,9999,23,18
25 DATA 23,40,23,31,9999,10
26 DATA 27,18,12,35,16,9999
68 FOR JJJJ=-32000 TO 32000
69 RANDOMIZE JJJJ
70 M=-1D+37
91 A(1)=1:A(2)=2:A(3)=3:A(4)=4:A(5)=5
126 IMAR=10+FIX(RND*100)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 5
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
194 J=1+FIX(RND*5)
196 JJ=1+FIX(RND*5)
198 X(J)=A(JJ)
199 X(JJ)=A(J)
305 PDU=0
311 FOR J88=0 TO 4
315 PDU=PDU- HR(X(J88),X(J88+1))
320 NEXT J88
355 P=PDU- HR(X(5),0)
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 5
1455 A(KLX)= ( X(KLX) )
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1899 IF M<-105 THEN 2222
1994 PRINT A(1),A(2),A(3),A(4),A(5)
2211 PRINT M,JJJJ
2222 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter. The complete output through JJJJ=-31981 is shown below. What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.
4 5 2 3 1
-103 -31988
4 5 2 3 1
-103 -31987
4 5 2 3 1
-103 -31981
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM, and the IBM basica/D interpreter, version GW BASIC 3.11, the throughput time for producing the output above was one second.
References
[1] L. L. Barachet (1957), Graphic Solution of the Travelling Salesman Problem. Operations Research, Vol. 5, pp. 841-845.
[2] T. Y. Chen, H. C. Chen (2009), Mixed-Discrete Structural Optimization Using a Rank-Niche Evolution Strategy, Engineering Optimization, 41:1, 39-58.
[3] Leon Cooper, U. N. Bhat, L. J. LeBlanc, Introduction to Operations Researach Models. W. B. Saunders Company, 1977.
[4] George B. Dantzig, Discrete-Variable Extremum Problems. Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.
[5] W. J. Fabrycky, P. M. Ghare, P. E. Torgersen, Applied Operations Research and Management Science. Englewood Cliffs, N. J. 07362: Prentice-Hall, Inc., 1984.
[6] Billy E. Gillett, Introduction to Operations Research: A Computer-Oriented Algorithmic Approach. McGraw-Hill, Inc., 1976.
[7] Martin Grotschel, Olaf Holland (1991), Solution of Large-Scale Symmetric Travelling Salesman Problems, Mathematical Programming 51, pp. 141-202.
[8] 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.
[9] R. L. Karg, G. L. Thompson (1964), A Heuristic Approach to Solving Travelling Salesman Problems. Management Sciencce, Vol. 10, Number 2, pp. 225-248.
[10] A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems. Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.
[11] 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.
[12] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems. Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.
[13] Ken McAloon, Carol Tretkoff, Optimization and Computational Logic. John Wiley and Sons, Inc., 1996.
[14] 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.
[15] Katta G. Murty, Opereations Research: Deterministic Optimization Models. Prentice Hall, Upper Saddle River, New Jersey 07458, 1994.
[16] Cliff T. Ragsdale, Spreadsheet Modeling and Decision Analysis, Fifth Edition. South-Westen, Cengage Learning, 2008.
[17] H. H. Rosenbrock (1960), An Automatic Method for Finding the Greatest or Least Value of a Function, Computer Journal Vol. 3, pp. 175-184.
[18] Wayne L. Winston, Munirpallam Venkataramanan, Introduction to Mathematical Programming: Operations Research, Volume One, Fourth Edition. Pacific Grove, CA 93950: Brooks/Cole--Thomson Learning, 2003.
[19] Wayne L. Winston, S. Christian Albright, Practical Management Science, Third Edition. Thomson/South-Western, 2007.
[20] Jsun Yui Wong (2011, October 27). A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a New Formulation of a Twelve-City Traveling Salesman Problem, Sixth Edition. Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/10/27/
[21] Ji-Hui Zhang, Xin-He Xu (1999), An Efficient Evoutionary Programming Algorithm. Computers & Operations Research 26, 645-663.
Posted at 04:56 AM | Permalink | Comments (0)
06/21/2012
A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a 21-City Traveling Salesperson Problem
Jsun Yui Wong
Based on the computer program in Wong [19], the following computer program seeks to solve the 21-city traveling salesperson problem in Grotschel and Holland [6]. Line 21 through line 1111 of the following computer program partly describe the present problem.
0 REM DEFDBL A-Z
2 DEFINT I,J,K,X,A
3 DIM B(5),N(5),A(70),H(5),L(5),U(5),X(70),D(5),P(5),PS(3),AA(11),I(22),J(22)
8 DIM HR(49,49)
11 FOR IZ=0 TO 20
14 FOR JZ=0 TO 20
16 READ HR(IZ,JZ)
18 NEXT JZ
19 NEXT IZ
21 DATA 9999,510,635,091,385,155,110,130,490,370,155,068,610,655,480,265,255,450,170,240,380
22 DATA 510,9999,355,415,585,475,480,500,605,320,380,440,360,235,081,480,440,270,445,290,140
23 DATA 635,355,9999,605,390,495,570,540,295,700,640,575,705,585,435,420,755,625,750,590,495
24 DATA 091,415,605,9999,350,120,078,097,460,280,063,027,520,555,380,235,235,345,160,140,280
25 DATA 385,585,390,350,9999,240,320,285,120,590,430,320,835,750,575,125,650,660,495,480,480
26 DATA 155,475,495,120,240,9999,096,036,350,365,200,091,605,615,440,125,370,430,265,255,340
27 DATA 110,480,570,078,320,096,9999,029,425,350,160,048,590,625,455,200,320,420,220,205,350
28 DATA 130,500,540,097,285,036,029,9999,390,370,175,067,610,645,465,165,350,440,240,220,370
29 DATA 490,605,295,460,120,350,425,390,9999,625,535,430,865,775,600,230,680,690,600,515,505
30 DATA 370,320,700,280,590,365,350,370,625,9999,240,300,250,285,245,475,150,077,235,150,185
31 DATA 155,380,640,063,430,200,160,175,535,240,9999,090,480,515,345,310,175,310,125,100,240
32 DATA 068,440,575,027,320,091,048,067,430,300,090,9999,545,585,415,205,265,380,170,170,310
33 DATA 610,360,705,520,835,605,590,610,865,250,480,545,9999,190,295,715,400,180,485,390,345
34 DATA 655,234,585,555,750,615,625,645,775,285,515,585,190,9999,170,650,435,215,525,425,280
35 DATA 480,081,435,380,575,440,455,465,600,245,345,415,295,170,9999,475,385,190,405,255,105
36 DATA 265,480,420,235,125,125,200,165,230,475,310,205,715,650,475,9999,485,545,375,395,380
37 DATA 255,440,755,235,650,370,320,350,680,150,175,265,400,435,385,485,9999,225,087,205,280
38 DATA 450,270,625,345,660,430,420,440,690,077,310,380,180,215,190,545,225,9999,315,220,165
39 DATA 170,445,750,160,495,265,220,240,600,235,125,170,485,525,405,375,087,315,9999,155,305
40 DATA 240,290,590,140,480,255,205,220,515,150,100,170,390,425,255,395,205,220,155,9999,150
41 DATA 380,140,495,280,480,340,350,370,505,185,240,310,345,280,105,380,280,165,305,150,9999
68 FOR JJJJ=-32000 TO 32000
69 RANDOMIZE JJJJ
70 M=-1D+37
91 A(1)=1:A(2)=2:A(3)=3:A(4)=4:A(5)=5:A(6)=6:A(7)=7:A(8)=8:A(9)=9:A(10)=10
92 A(11)=11:A(12)=12:A(13)=13:A(14)=14:A(15)=15:A(16)=16:A(17)=17:A(18)=18:A(19)=19:A(20)=20
126 REM IMAR=10+FIX(RND*100)
128 FOR I=1 TO 200
129 FOR KKQQ=1 TO 20
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
194 J=1+FIX(RND*20)
196 JJ=1+FIX(RND*20)
198 X(J)=A(JJ)
199 X(JJ)=A(J)
305 PDU=0
311 FOR J88=0 TO 19
315 PDU=PDU- HR(X(J88),X(J88+1))
320 NEXT J88
355 P=PDU- HR(X(20),0)
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 20
1455 A(KLX)= ( X(KLX) )
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1899 IF M<-2707 THEN 2222
1994 PRINT A(1),A(2),A(3),A(4),A(5)
1995 PRINT A(6),A(7),A(8),A(9),A(10)
1996 PRINT A(11),A(12),A(13),A(14),A(15)
1997 PRINT A(16),A(17),A(18),A(19),A(20)
2211 PRINT M,JJJJ
2222 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter. The complete output through JJJJ=-27611 is shown below. What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.
6 7 5 15 4
8 2 1 20 14
13 12 17 9 16
18 19 10 3 11
-2707 -30262
6 7 5 15 4
8 2 1 20 14
13 12 17 9 16
18 19 10 3 11
-2707 -30104
6 7 5 15 4
8 2 1 20 14
13 12 17 9 16
18 19 10 3 11
-2707 -27611
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 throughput time for producing the output above was four minutes.
References
[1] L. L. Barachet (1957), Graphic Solution of the Travelling Salesman Problem. Operations Research, Vol. 5, pp. 841-845.
[2] T. Y. Chen, H. C. Chen (2009), Mixed-Discrete Structural Optimization Using a Rank-Niche Evolution Strategy, Engineering Optimization, 41:1, 39-58.
[3] Leon Cooper, U. N. Bhat, L. J. LeBlanc, Introduction to Operations Researach Models. W. B. Saunders Company, 1977.
[4] George B. Dantzig, Discrete-Variable Extremum Problems. Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.
[5] Billy E. Gillett, Introduction to Operations Research: A Computer-Oriented Algorithmic Approach. McGraw-Hill, Inc., 1976.
[6] Martin Grotschel, Olaf Holland (1991), Solution of Large-Scale Symmetric Travelling Salesman Problems, Mathematical Programming 51, pp. 141-202.
[7] 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.
[8] R. L. Karg, G. L. Thompson (1964), A Heuristic Approach to Solving Travelling Salesman Problems. Management Sciencce, Vol. 10, Number 2, pp. 225-248.
[9] A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems. Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.
[10] 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.
[11] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems. Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.
[12] Ken McAloon, Carol Tretkoff, Optimization and Computational Logic. John Wiley and Sons, Inc., 1996.
[13] 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.
[14] Katta G. Murty, Opereations Research: Deterministic Optimization Models. Prentice Hall, Upper Saddle River, New Jersey 07458, 1994.
[15] Cliff T. Ragsdale, Spreadsheet Modeling and Decision Analysis, Fifth Edition. South-Westen, Cengage Learning, 2008.
[16] H. H. Rosenbrock (1960), An Automatic Method for Finding the Greatest or Least Value of a Function, Computer Journal Vol. 3, pp. 175-184.
[17] Wayne L. Winston, Munirpallam Venkataramanan, Introduction to Mathematical Programming: Operations Research, Volume One, Fourth Edition. Pacific Grove, CA 93950: Brooks/Cole--Thomson Learning, 2003.
[18] Wayne L. Winston, S. Christian Albright, Practical Management Science, Third Edition. Thomson/South-Western, 2007.
[19] Jsun Yui Wong (2011, October 27). A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a New Formulation of a Twelve-City Traveling Salesman Problem, Sixth Edition. Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/10/27/
[20] Ji-Hui Zhang, Xin-He Xu (1999), An Efficient Evoutionary Programming Algorithm. Computers & Operations Research 26, 645-663.
Posted at 03:12 AM | Permalink | Comments (0)
06/19/2012
A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to an Eleven-City Traveling Salesperson Problem
Jsun Yui Wong
Based on the computer program in Wong [18], the following computer program seeks to solve the eleven-city traveling salesperson problem in Winston and Albright [17, pp. 454-456]. Line 21 through line 1111 of the following computer program partly describe the present problem.
0 REM DEFDBL A-Z
2 DEFINT I,J,K,X,A
3 DIM B(5),N(5),A(70),H(5),L(5),U(5),X(70),D(5),P(5),PS(3),AA(11),I(22),J(22)
8 DIM HR(49,49)
11 FOR IZ=0 TO 10
14 FOR JZ=0 TO 10
16 READ HR(IZ,JZ)
18 NEXT JZ
19 NEXT IZ
21 DATA 9999,0983,1815,1991,3036,1539,0213,2664,0792,2385,2612
22 DATA 0983,9999,1205,1050,2112,1390,0840,1729,0457,2212,2052
23 DATA 1815,1205,9999,0801,1425,1332,1604,1027,1237,1034,2404
24 DATA 1991,1050,0801,9999,1174,2057,1780,0836,1411,1765,1373
25 DATA 3036,2112,1425,1174,9999,2757,2825,0398,2456,0403,1919
26 DATA 1539,1390,1332,2057,2757,9999,1258,2359,1250,3097,3389
27 DATA 0213,0840,1604,1780,2825,1258,9999,2442,0386,3036,2900
28 DATA 2664,1729,1027,0836,0398,2359,2442,9999,2073,0800,1482
29 DATA 0792,0457,1237,1411,2456,1250,0386,2073,9999,2653,2517
30 DATA 2385,2212,1765,1034,0403,3097,3036,0800,2653,9999,0817
31 DATA 2612,2052,2404,1373,1919,3389,2900,1482,2517,0817,9999
68 FOR JJJJ=-32000 TO 32000
69 RANDOMIZE JJJJ
70 M=-1D+37
91 A(1)=1:A(2)=2:A(3)=3:A(4)=4:A(5)=5:A(6)=6:A(7)=7:A(8)=8:A(9)=9:A(10)=10
126 IMAR=10+FIX(RND*100)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 10
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
194 J=1+FIX(RND*10)
196 JJ=1+FIX(RND*10)
198 X(J)=A(JJ)
199 X(JJ)=A(J)
305 PDU=0
311 FOR J88=0 TO 9
315 PDU=PDU- HR(X(J88),X(J88+1))
320 NEXT J88
355 P=PDU- HR(X(10),0)
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 10
1455 A(KLX)= ( X(KLX) )
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1899 IF M<-9200 THEN 2222
1994 PRINT A(1),A(2),A(3),A(4),A(5)
1995 PRINT A(6),A(7),A(8),A(9),A(10)
2211 PRINT M,JJJJ
2222 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter. The complete output through JJJJ=-31965 is shown below. What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.
6 8 1 3 10
9 4 7 2 5
-8995 -31994
5 2 7 4 9
10 3 1 8 6
-8995 -31987
6 5 2 7 4
9 10 3 1 8
-9120 -31965
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 throughput time for producing the output above was one second.
References
[1] L. L. Barachet (1957), Graphic Solution of the Travelling Salesman Problem. Operations Research. Vol. 5, pp. 841-845.
[2] T. Y. Chen, H. C. Chen (2009), Mixed-Discrete Structural Optimization Using a Rank-Niche Evolution Strategy, Engineering Optimization, 41:1, 39-58.
[3] Leon Cooper, U. N. Bhat, L. J. LeBlanc, Introduction to Operations Researach Models. W. B. Saunders Company, 1977.
[4] George B. Dantzig, Discrete-Variable Extremum Problems. Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.
[5] Billy E. Gillett, Introduction to Operations Research: A Computer-Oriented Algorithmic Approach. McGraw-Hill, Inc., 1976.
[6] 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.
[7] R. L. Karg, G. L. Thompson (1964), A Heuristic Approach to Solving Travelling Salesman Problems. Management Sciencce, Vol. 10, Number 2, pp. 225-248.
[8] A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems. Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.
[9] 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.
[10] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems. Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.
[11] Ken McAloon, Carol Tretkoff, Optimization and Computational Logic. John Wiley and Sons, Inc., 1996.
[12] 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.
[13] Katta G. Murty, Opereations Research: Deterministic Optimization Models. Prentice Hall, Upper Saddle River, New Jersey 07458, 1994.
[14] Cliff T. Ragsdale, Spreadsheet Modeling and Decision Analysis, Fifth Edition. South-Westen, Cengage Learning, 2008.
[15] H. H. Rosenbrock (1960), An Automatic Method for Finding the Greatest or Least Value of a Function, Computer Journal Vol. 3, pp. 175-184.
[16] Wayne L. Winston, Munirpallam Venkataramanan, Introduction to Mathematical Programming: Operations Research, Volume One, Fourth Edition. Pacific Grove, CA 93950: Brooks/Cole--Thomson Learning, 2003.
[17] Wayne L. Winston, S. Christian Albright, Practical Management Science, Third Edition. Thomson/South-Western, 2007.
[18] Jsun Yui Wong (2011, October 27). A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a New Formulation of a Twelve-City Traveling Salesman Problem, Sixth Edition. Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/10/27/
[19] Ji-Hui Zhang, Xin-He Xu (1999), An Efficient Evoutionary Programming Algorithm. Computers & Operations Research 26, 645-663.
Posted at 04:21 AM | Permalink | Comments (0)
06/18/2012
A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a Ten-City Traveling Salesperson Problem from the Literature
Jsun Yui Wong
Based on the computer program in Wong [15], the following computer program seeks to solve the ten-city traveling salesperson problem in Gillett [5, pp. 207-210]. Line 21 through line 1111 of the following computer program partly describe the present problem.
0 REM DEFDBL A-Z
2 DEFINT I,J,K,X,A
3 DIM B(5),N(5),A(70),H(5),L(5),U(5),X(70),D(5),P(5),PS(3),AA(11),I(22),J(22)
8 DIM HR(49,49)
11 FOR IZ=0 TO 9
14 FOR JZ=0 TO 9
16 READ HR(IZ,JZ)
18 NEXT JZ
19 NEXT IZ
21 DATA 9999,184,292,449,670,516,598,618,881,909
22 DATA 184,9999,195,310,540,357,514,434,697,964
23 DATA 292,195,9999,215,380,232,434,493,719,955
24 DATA 449,310,215,9999,288,200,566,787,790,1020
25 DATA 670,540,380,288,9999,211,436,814,632,974
26 DATA 516,357,232,200,211,9999,381,642,697,952
27 DATA 598,514,434,566,436,381,9999,295,224,541
28 DATA 618,434,493,787,814,642,295,9999,320,341
29 DATA 881,697,719,790,632,697,224,320,9999,318
30 DATA 909,964,955,1020,974,952,541,341,318,9999
68 FOR JJJJ=-32000 TO 32000
69 RANDOMIZE JJJJ
70 M=-1D+37
91 A(1)=1:A(2)=2:A(3)=3:A(4)=4:A(5)=5:A(6)=6:A(7)=7:A(8)=8
92 A(9)=9
126 IMAR=10+FIX(RND*100)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 9
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
194 J=1+FIX(RND*9)
196 JJ=1+FIX(RND*9)
198 X(J)=A(JJ)
199 X(JJ)=A(J)
305 PDU=0
311 FOR J88=0 TO 8
315 PDU=PDU- HR(X(J88),X(J88+1))
320 NEXT J88
355 P=PDU- HR(X(9),0)
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 9
1455 A(KLX)= ( X(KLX) )
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1899 IF M<-2860 THEN 2222
1994 PRINT A(1),A(2),A(3),A(4),A(5)
1995 PRINT A(6),A(7),A(8),A(9)
2211 PRINT M,JJJJ
2222 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter. The complete output through JJJJ=-31939 is shown below. What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.
2 3 5 4 6
8 9 7 1
-2855 -31974
2 3 5 4 6
8 9 7 1
-2855 -31966
2 3 5 4 6
8 9 7 1
-2855 -31955
2 3 5 4 6
8 9 7 1
-2855 -31943
1 7 9 8 6
4 5 3 2
-2855 -31939
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 throughput time for producing the output above was one second.
References
[1] L. L. Barachet (1957), Graphic Solution of the Travelling Salesman Problem. Operations Research. Vol. 5, pp. 841-845.
[2] T. Y. Chen, H. C. Chen (2009), Mixed-Discrete Structural Optimization Using a Rank-Niche Evolution Strategy, Engineering Optimization, 41:1, 39-58.
[3] Leon Cooper, U. N. Bhat, L. J. LeBlanc, Introduction to Operations Researach Models. W. B. Saunders Company, 1977.
[4] George B. Dantzig, Discrete-Variable Extremum Problems. Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.
[5] Billy E. Gillett, Introduction to Operations Research: A Computer-Oriented Algorithmic Approach. McGraw-Hill, Inc., 1976.
[6] 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.
[7] R. L. Karg, G. L. Thompson (1964), A Heuristic Approach to Solving Travelling Salesman Problems. Management Sciencce, Vol. 10, Number 2, pp. 225-248.
[8] A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems. Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.
[9] 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.
[10] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems. Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.
[11] Ken McAloon, Carol Tretkoff, Optimization and Computational Logic. John Wiley and Sons, Inc., 1996.
[12] 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.
[13] Katta G. Murty, Opereations Research: Deterministic Optimization Models. Prentice Hall, Upper Saddle River, New Jersey 07458, 1994.
[14] H. H. Rosenbrock (1960), An Automatic Method for Finding the Greatest or Least Value of a Function, Computer Journal Vol. 3, pp. 175-184.
[15] Jsun Yui Wong (2011, October 27). A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a New Formulation of a Twelve-City Traveling Salesman Problem, Sixth Edition. Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/10/27/
[16] Ji-Hui Zhang, Xin-He Xu (1999), An Efficient Evoutionary Programming Algorithm. Computers & Operations Research 26, 645-663.
Posted at 07:07 AM | Permalink | Comments (0)
06/17/2012
A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a Seven-City Traveling Salesperson Problem
Jsun Yui Wong
Based on the computer program in Wong [11], the following computer program seeks to solve the seven-city traveling salesperson problem on pages 168-170 of Cooper, Bhat, and LeBlanc [2]. Line 21 through line 1111 of the following computer program partly describe the present problem.
0 REM DEFDBL A-Z
2 DEFINT I,J,K,X,A
3 DIM B(5),N(5),A(70),H(5),L(5),U(5),X(70),D(5),P(5),PS(3),AA(11)
8 DIM HR(49,49)
11 FOR IZ=0 TO 6
14 FOR JZ=0 TO 6
16 READ HR(IZ,JZ)
18 NEXT JZ
19 NEXT IZ
21 DATA 999,35,20,25,40,30,35
22 DATA 35,999,15,50,45,65,70
23 DATA 20,15,999,25,45,50,55
24 DATA 25,50,25,999,65,45,40
25 DATA 40,45,45,65,999,35,45
26 DATA 30,65,50,45,35,999,10
27 DATA 35,70,55,40,45,10,999
68 FOR JJJJ=-32000 TO 32000
69 RANDOMIZE JJJJ
70 M=-1D+37
91 A(1)=1:A(2)=2:A(3)=3:A(4)=4:A(5)=5:A(6)=6
126 IMAR=10+FIX(RND*100)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 6
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
194 J=1+FIX(RND*6)
196 JJ=1+FIX(RND*6)
198 X(J)=A(JJ)
199 X(JJ)=A(J)
305 PDU=0
311 FOR J88=0 TO 5
315 PDU=PDU- HR(X(J88),X(J88+1))
320 NEXT J88
355 P=PDU- HR(X(6),0)
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
1899 IF M<-195 THEN 2222
1994 PRINT A(1),A(2),A(3),A(4),A(5),A(6)
2211 PRINT M,JJJJ
2222 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter. The output through JJJJ=-31983 is shown below. What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.
.
.
.
3 2 1 4 5
6
-190 -31987
6 5 4 1 2
3
-190 -31986
2 1 4 5 6
3
-190 -31985
3 2 1 4 5
6
-190 -31983
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 throughput time for producing the output above was one second.
References
[1] T. Y. Chen, H. C. Chen (2009), Mixed-Discrete Structural Optimization Using a Rank-Niche Evolution Strategy, Engineering Optimization, 41:1, 39-58.
[2] Leon Cooper, U. N. Bhat, L. J. LeBlanc, Introduction to Operations Researach Models. W. B. Saunders Company, 1977.
[3] George B. Dantzig, Discrete-Variable Extremum Problems. Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.
[4] 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.
[5] A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems. Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.
[6] 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.
[7] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems. Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.
[8] Ken McAloon, Carol Tretkoff, Optimization and Computational Logic. John Wiley and Sons, Inc., 1996.
[9] 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.
[10] H. H. Rosenbrock (1960), An Automatic Method for Finding the Greatest or Least Value of a Function, Computer Journal Vol. 3, pp. 175-184.
[11] Jsun Yui Wong (2011, October 27). A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a New Formulation of a Twelve-City Traveling Salesman Problem, Sixth Edition. Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/10/27/
[12] Ji-Hui Zhang, Xin-He Xu (1999), An Efficient Evoutionary Programming Algorithm. Computers & Operations Research 26, 645-663.
Posted at 10:27 AM | Permalink | Comments (0)
06/15/2012
Testing a General Nonlinear Integer/Discrete/Continuous Programming Solver with the Rosenbrock Function of 9000 Zero-One Integer Variables
Jsun Yui Wong
The computer program listed below seeks to minimize the Rosenbrock function [8] of 9000 binary variables. Line 509 through line 1111 of the following computer program partly describe the present problem.
0 REM DEFDBL A-Z
2 DEFINT I,J,K,X,A
3 DIM B(5),N(5),A(9000),H(5),L(5),U(5),X(9000),D(5),P(5),PS(3),AA(11)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+37
40 FOR J44=1 TO 9000
41 A(J44)=FIX(RND*2)
42 NEXT J44
128 FOR PI=1 TO 300000!
129 FOR KKQQ=1 TO 9000
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 FOR IPP=1 TO (1+FIX(RND*5))
171 J=1+FIX(RND*9000)
444 X(J)=A(J) +FIX(RND*2)-FIX(RND*2 )
496 NEXT IPP
509 FOR J44=1 TO 9000
510 IF X(J44)<0 THEN 1670
511 IF X(J44)>1 THEN 1670
512 NEXT J44
611 PSUM1=0
613 FOR J44=1 TO 8999
615 PSUM1=PSUM1- 100* (X(J44)^2-X(J44+1) )^2 - (X(J44) -1 )^2
617 NEXT J44
735 P= PSUM1
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 9000
1455 A(KLX)= ( X(KLX) )
1456 NEXT KLX
1471 PRINT A(1),A(2),A(3),A(4),A(5)
1472 PRINT A(6),A(7),A(8),A(9),A(10)
1473 PRINT A(11),A(12),A(13),A(14),A(15)
1474 PRINT A(8986),A(8987),A(8988),A(8989),A(8990)
1475 PRINT A(8991),A(8992),A(8993),A(8994),A(8995)
1476 PRINT A(8996),A(8997),A(8998),A(8999),A(9000)
1555 PRINT M,JJJJ,PI
1557 GOTO 128
1670 NEXT PI
1899 IF M<-10 THEN 2222
2211 PRINT M,A(1),A(11),A(12),A(9000)
2222 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter. The first seven lines and the last lines of the output through 4.5 hours of running are shown below. What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.
1 0 1 0 1
1 1 1 1 0
0 1 0 1 0
0 0 1 1 1
1 1 1 1 1
0 0 0 0 1
-449584 -32000 3
.
.
.
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
-607 -32000 1884
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
-406 -32000 1905
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
-405 -32000 9842
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
-204 -32000 4743
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
-203 -32000 14301
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
-202 -32000 92408
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
-201 -32000 2989
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
0 -32000 42191
In accordance with line 1471 through line 1476, only 30 of the 9000 variable values are shown above.
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 throughput time for producing the output above was four hours and a half.
References
[1] T. Y. Chen, H. C. Chen (2009), Mixed-Discrete Structural Optimization Using a Rank-Niche Evolution Strategy, Engineering Optimization, 41:1, 39-58.
[2] George B. Dantzig, Discrete-Variable Extremum Problems. Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.
[3] 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.
[4] A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems. Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.
[5] 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.
[6] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems. Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.
[7] 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.
[8] H. H. Rosenbrock (1960), An Automatic Method for Finding the Greatest or Least Value of a Function, Computer Journal Vol. 3, pp. 175-184.
[9] Jsun Yui Wong (2011, April 17). The Domino Method of Solving Nonlinear Systems of Equations. Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/04/17/
[10] Yang R. L, Gu JF. An Efficient Simulated Annealing Global Optimization Algorithm. System Engineering and Practice 1997; 5:55-60. (This reference comes from Zhang and Xu [9]; the present writer has not seen a copy of this Yang and Gu article.)
[11] Ji-Hui Zhang, Xin-He Xu (1999), An Efficient Evoutionary Programming Algorithm. Computers & Operations Research 26, 645-663.
Posted at 11:47 AM | Permalink | Comments (0)
06/08/2012
Testing a General Nonlinear Integer/Discrete/Continuous Programming Solver with a Modified Test Problem Involving 3500 General Integer Variables
Jsun Yui Wong
The computer program listed below is about a modified test problem and its solution based on pages 649-653 of Zhang and Xu [10], One modification is from the biggest m=100 there to m=3500 here; the other modification is that all of the 3500 variables are general integer variables here, while the variables in the Zhang and Xu problem [10] are continuous. Their problem [10] is the source of a problem in Chen and Chen [1]. Line 509 through line 1111 of the following computer program partly describe this modified Zhang and Xu [10] problem.
0 REM DEFDBL A-Z
2 DEFINT I,J,K,X,A
3 DIM B(5),N(5),A(7000),H(5),L(5),U(5),X(7000),D(5),P(5),PS(3),AA(11)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+37
17 GOTO 50
40 FOR J44=1 TO 3500
41 A(J44)=-10+(RND*20)
42 NEXT J44
50 FOR J44=1 TO 3500
51 A(J44)=-4+RND*8
52 NEXT J44
126 REM IMAR=10+FIX(RND*100)
128 FOR PI=1 TO 100000!
129 FOR KKQQ=1 TO 3500
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 FOR IPP=1 TO (1+FIX(RND*5))
171 J=1+FIX(RND*3500)
172 GOTO 422
174 IF J<3500.5 THEN 182 ELSE 422
182 IF RND<.333 THEN 183 ELSE IF RND<.66 THEN 186 ELSE 222
183 R=(1-RND*2)*A(J)
184 X(J)=A(J)+ (RND^(RND*10))*R
185 GOTO 496
186 X(J)=A(J)+(FIX(RND*2))*.1*A(J)-(FIX(RND*2))*.1 *A(J)
188 GOTO 496
222 X(J)=-A(J)
396 GOTO 496
422 IF RND<.5 THEN 444 ELSE 455
444 X(J)=A(J) +FIX(RND*2)-FIX(RND*2 )
446 GOTO 496
455 X(J)=-A(J)
496 NEXT IPP
509 FOR J44=1 TO 3500
510 IF X(J44)<-10 THEN 1670
511 IF X(J44)>10 THEN 1670
512 NEXT J44
611 PSUM1=0
613 FOR J44=1 TO 3500
615 PSUM1=PSUM1+ X(J44)^4-16*X(J44)^2+5*X(J44)
617 NEXT J44
735 P= -(1/3500)*( PSUM1 )
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 3500
1455 A(KLX)= ( X(KLX) )
1456 NEXT KLX
1522 IF M<77.5 THEN 1557
1525 PRINT M,JJJJ
1533 REM IF M<77.5 THEN 1557
1534 FOR J44=1 TO 3500
1535 PJ44=ABS(A(J44)+3)
1536 IF PJ44>.01 THEN PRINT PJ44 ELSE 1538
1537 REM PRINT M,JJJJ
1538 NEXT J44
1540 GOTO 1557
1541 PRINT A(1),A(2),A(3),A(4),A(5)
1542 PRINT A(6),A(7),A(8),A(9),A(10)
1543 PRINT A(11),A(12),A(13),A(14),A(15)
1544 PRINT A(3496),A(3497),A(3498),A(3499),A(3500)
1552 PRINT A(3501),A(3502),A(3503),A(3504),A(3505)
1553 PRINT A(6986),A(6987),A(6988),A(6989),A(6990)
1554 PRINT A(6991),A(6992),A(6993),A(6994),A(6995)
1555 PRINT A(6996),A(6997),A(6998),A(6999),A(7000)
1556 PRINT M,JJJJ
1557 GOTO 128
1670 NEXT PI
1899 REM IF M<-1 THEN 2222
1991 PRINT A(1),A(2),A(3),A(1750)
2001 PRINT A(1751),A(1752),A(1753),A(1754),A(1755)
2211 PRINT M,JJJJ,A(3498),A(3499),A(3500)
2222 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter. The last lines of the output through four hours are shown below. What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.
77.98286 -32000
1
1
1
77.98857 -32000
1
1
77.99429 -32000
1
78 -32000
-3 -3 -3 -3
-3 -3 -3 -3 -3
78 -32000 -3 -3 -3
In accordance with line 1991, line 2001, and line 2211, only a few of the 3500 variable values are shown above.
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 throughput time for producing the output above was four hours.
References
[1] T. Y. Chen, H. C. Chen (2009), Mixed-Discrete Structural Optimization Using a Rank-Niche Evolution Strategy, Engineering Optimization, 41:1, 39-58.
[2] George B. Dantzig, Discrete-Variable Extremum Problems. Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.
[3] 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.
[4] A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems. Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.
[5] 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.
[6] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems. Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.
[7] 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.
[8] Jsun Yui Wong (2011, April 17). The Domino Method of Solving Nonlinear Systems of Equations. Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/04/17/
[9] Yang R. L, Gu JF. An Efficient Simulated Annealing Global Optimization Algorithm. System Engineering and Practice 1997; 5:55-60. (This reference comes from Zhang and Xu [9]; the present writer has not seen a copy of this Yang and Gu article.)
[10] Ji-Hui Zhang, Xin-He Xu (1999), An Efficient Evoutionary Programming Algorithm. Computers & Operations Research 26, 645-663.
Posted at 10:46 AM | Permalink | Comments (0)
06/01/2012
A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to Three Instances of a Nonlinear Problem from the Literature
Jsun Yui Wong
The computer programs listed below are about the m=10, m=20, and m=30 problems and their solutions given on pages 649-653 of Zhang and Xu [8]. Line 509 through line 1111 of each of the following computer programs partly describe each of the three instances.
The Instance of m=10
0 REM DEFDBL A-Z
2 DEFINT I,J,K
3 DIM B(5),N(5),A(7000),H(5),L(5),U(5),X(7000),D(5),P(5),PS(3),AA(11)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+37
40 FOR J44=1 TO 10
41 A(J44)=-10+(RND*10)
42 NEXT J44
43 GOTO 128
50 FOR J44=551 TO 1100
51 A(J44)=-10+FIX(RND*21)
52 NEXT J44
126 REM IMAR=10+FIX(RND*100)
128 FOR PI=1 TO 4000
129 FOR KKQQ=1 TO 10
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 FOR IPP=1 TO (1+FIX(RND*5))
171 J=1+FIX(RND*10)
174 REM IF J<550.5 THEN 182 ELSE 422
182 IF RND<.333 THEN 183 ELSE IF RND<.66 THEN 186 ELSE 222
183 R=(1-RND*2)*A(J)
184 X(J)=A(J)+ (RND^(RND*10))*R
185 GOTO 496
186 X(J)=A(J)+(FIX(RND*2))*.1*A(J)-(FIX(RND*2))*.1 *A(J)
188 GOTO 496
222 X(J)=-A(J)
396 GOTO 496
422 IF RND<.5 THEN 444 ELSE 455
444 X(J)=A(J) +FIX(RND*2)-FIX(RND*2 )
446 GOTO 496
455 X(J)=-A(J)
496 NEXT IPP
509 FOR J44=1 TO 10
510 IF X(J44)<-10 THEN 1670
511 IF X(J44)>10 THEN 1670
512 NEXT J44
611 PSUM1=0
613 FOR J44=1 TO 10
615 PSUM1=PSUM1+ X(J44)^4-16*X(J44)^2+5*X(J44)
617 NEXT J44
735 P= -(1/10)*( PSUM1 )
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 10
1455 A(KLX)= ( X(KLX) )
1456 NEXT KLX
1557 GOTO 128
1670 NEXT PI
1899 REM IF M<-1 THEN 2222
1994 PRINT A(1),A(2),A(3),A(4),A(5)
2013 PRINT A(6),A(7),A(8),A(9),A(10)
2211 PRINT M,JJJJ
2222 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter. The complete output through JJJJ=-31998 is shown below. What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.
-2.904215 -2.902744 -2.9053 -2.903789 -2.904075
-2.902615 -2.903205 -2.902659 -2.903918 -2.903548
78.33233 -32000
-2.903905 -2.902403 -2.90251 -2.903178 -2.903034
-2.903746 -2.903562 -2.903096 -2.903107 -2.902814
78.33235 -31999
-2.904184 -2.904591 -2.903737 -2.903394 -2.904412
-2.902613 -2.903679 -2.904415 -2.901948 -2.902696
78.33232 -31998
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM, and the IBM basica/D interpreter, version GW BASIC 3.11, the throughput time from
JJJJ=-32000 through JJJJ=-31998 was seven seconds.
The Instance of m=20
0 REM DEFDBL A-Z
2 DEFINT I,J,K
3 DIM B(5),N(5),A(7000),H(5),L(5),U(5),X(7000),D(5),P(5),PS(3),AA(11)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+37
40 FOR J44=1 TO 20
41 A(J44)=-10+(RND*10)
42 NEXT J44
43 GOTO 128
50 FOR J44=551 TO 1100
51 A(J44)=-10+FIX(RND*21)
52 NEXT J44
126 REM IMAR=10+FIX(RND*100)
128 FOR PI=1 TO 4000
129 FOR KKQQ=1 TO 20
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 FOR IPP=1 TO (1+FIX(RND*5))
171 J=1+FIX(RND*20)
174 REM IF J<550.5 THEN 182 ELSE 422
182 IF RND<.333 THEN 183 ELSE IF RND<.66 THEN 186 ELSE 222
183 R=(1-RND*2)*A(J)
184 X(J)=A(J)+ (RND^(RND*10))*R
185 GOTO 496
186 X(J)=A(J)+(FIX(RND*2))*.1*A(J)-(FIX(RND*2))*.1 *A(J)
188 GOTO 496
222 X(J)=-A(J)
396 GOTO 496
422 IF RND<.5 THEN 444 ELSE 455
444 X(J)=A(J) +FIX(RND*2)-FIX(RND*2 )
446 GOTO 496
455 X(J)=-A(J)
496 NEXT IPP
509 FOR J44=1 TO 20
510 IF X(J44)<-10 THEN 1670
511 IF X(J44)>10 THEN 1670
512 NEXT J44
611 PSUM1=0
613 FOR J44=1 TO 20
615 PSUM1=PSUM1+ X(J44)^4-16*X(J44)^2+5*X(J44)
617 NEXT J44
735 P= -(1/20)*( PSUM1 )
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 20
1455 A(KLX)= ( X(KLX) )
1456 NEXT KLX
1557 GOTO 128
1670 NEXT PI
1899 REM IF M<-1 THEN 2222
1994 PRINT A(1),A(2),A(3),A(4),A(5)
2013 PRINT A(16),A(17),A(18),A(19),A(20)
2211 PRINT M,JJJJ
2222 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter. The complete output through JJJJ=-31998 is shown below. What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.
-2.904776 -2.902851 -2.901441 -2.905091 -2.902554
-2.90326 -2.904727 -2.904323 -2.902633 -2.903141
78.33232 -32000
-2.903021 -2.904734 -2.901235 -2.90439 -2.901302
-2.901612 -2.903408 -2.902286 -2.903776 -2.904824
78.3323 -31999
-2.905179 -2.905311 -2.90193 -2.904196 -2.903858
-2.903952 -2.903284 -2.903139 -2.902726 -2.905148
78.33232 -31998
In accordance with line 1994 through line 2013, for each JJJJ, only ten of the twenty variable values are shown above.
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 throughput time from
JJJJ=-32000 through JJJJ=-31998 was twelve seconds.
The Instance of m=30
0 REM DEFDBL A-Z
2 DEFINT I,J,K
3 DIM B(5),N(5),A(7000),H(5),L(5),U(5),X(7000),D(5),P(5),PS(3),AA(11)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+37
40 FOR J44=1 TO 30
41 A(J44)=-10+(RND*10)
42 NEXT J44
43 GOTO 128
50 FOR J44=551 TO 1100
51 A(J44)=-10+FIX(RND*21)
52 NEXT J44
126 REM IMAR=10+FIX(RND*100)
128 FOR PI=1 TO 4000
129 FOR KKQQ=1 TO 30
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 FOR IPP=1 TO (1+FIX(RND*5))
171 J=1+FIX(RND*30)
174 REM IF J<550.5 THEN 182 ELSE 422
182 IF RND<.333 THEN 183 ELSE IF RND<.66 THEN 186 ELSE 222
183 R=(1-RND*2)*A(J)
184 X(J)=A(J)+ (RND^(RND*10))*R
185 GOTO 496
186 X(J)=A(J)+(FIX(RND*2))*.1*A(J)-(FIX(RND*2))*.1 *A(J)
188 GOTO 496
222 X(J)=-A(J)
396 GOTO 496
422 IF RND<.5 THEN 444 ELSE 455
444 X(J)=A(J) +FIX(RND*2)-FIX(RND*2 )
446 GOTO 496
455 X(J)=-A(J)
496 NEXT IPP
509 FOR J44=1 TO 30
510 IF X(J44)<-10 THEN 1670
511 IF X(J44)>10 THEN 1670
512 NEXT J44
611 PSUM1=0
613 FOR J44=1 TO 30
615 PSUM1=PSUM1+ X(J44)^4-16*X(J44)^2+5*X(J44)
617 NEXT J44
735 P= -(1/30)*( PSUM1 )
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 30
1455 A(KLX)= ( X(KLX) )
1456 NEXT KLX
1557 GOTO 128
1670 NEXT PI
1899 REM IF M<-1 THEN 2222
1994 PRINT A(1),A(2),A(3),A(4),A(5)
2013 PRINT A(26),A(27),A(28),A(29),A(30)
2211 PRINT M,JJJJ
2222 NEXT JJJJ
This BASIC computer program was run with Microsoft's GW BASIC 3.11 interpreter. The complete output through JJJJ=-31998 is shown below. What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.
-2.903004 -2.902174 -2.904 -2.903525 -2.903507
-2.902342 -2.9034 -2.905561 -2.904374 -2.903168
78.33232 -32000
-2.901691 -2.902458 -2.903106 -2.905223 -2.904535
-2.902813 -2.904311 -2.903152 -2.903649 -2.905746
78.33226 -31999
-2.901624 -2.902659 -2.898646 -2.904498 -2.904022
-2.901456 -2.905445 -2.902909 -2.901686 -2.906095
78.33223 -31998
In accordance with line 1994 through line 2013, for each JJJJ, only ten of the thirty variable values are shown above.
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 throughput time from
JJJJ=-32000 through JJJJ=-31998 was twenty seconds.
References
[1] T. Y. Chen, H. C. Chen (2009), Mixed-Discrete Structural Optimization Using a Rank-Niche Evolution Strategy, Engineering Optimization, 41:1, 39-58.
[2] George B. Dantzig, Discrete-Variable Extremum Problems. Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.
[3] 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.
[4] 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.
[5] Harry M. Markowitz, Alan S. Manne, On the Solution of Discrete Programming Problems. Econometrica, Vol. 25, No. 1 (Jan., 1957), pp. 84-110.
[5] Microsoft Corp., BASIC, Second Edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.
[7] Jsun Yui Wong (2011, April 17). The Domino Method of Solving Nonlinear Systems of Equations. Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/04/17/
[8] Ji-Hui Zhang, Xin-He Xu (1999), An Efficient Evoutionary Programming Algorithm. Computers & Operations Research 26, 645-663.
Posted at 07:45 AM | Permalink | Comments (0)
