Jsun Yui Wong
The computer program listed below seeks to solve the small example about Markowitz portfolio selection [3] on pp. 888-890 of Li and Tsai [2].
Minimize .0108 * X(1) ^ 2 + .0584 * X(2) ^ 2 + .0942 * X(3) ^ 2 + .0248 * X(1) * X(2) + .0262 * X(1) * X(3) + .1108 * X(2) * X(3)
subject to 1.089 * X(1) + 1.214 * X(2) + 1.235 * X(3) >= 115
X(1) + X(2) + X(3) = 100
where X(1), X(2), and X(3) are integers.
Below X(1) through X(3) are integer variables, and X(4) is a slack variable.
0 REM DEFDBL A-Z
2 DEFINT I, J, K
3 DIM B(99), N(99), A(99), H(99), L(99), U(99), X(1111), D(111), P(111), PS(33)
12 FOR JJJJ = -32000 TO 32000
14 RANDOMIZE JJJJ
16 M = -1D+37
64 FOR J44 = 1 TO 3
65 A(J44) = RND * 10
66 NEXT J44
126 REM IMAR=10+FIX(RND*32000)
128 FOR I = 1 TO 10000
129 FOR KKQQ = 1 TO 3
130 X(KKQQ) = A(KKQQ)
131 NEXT KKQQ
133 FOR IPP = 1 TO (1 + FIX(RND * 2))
181 J = 1 + FIX(RND * 3)
183 R = (1 - RND * 2) * A(J)
187 X(J) = A(J) + (RND ^ (RND * 10)) * R
222 NEXT IPP
223 X(1) = 100 - X(2) - X(3)
224 FOR J33 = 1 TO 3
226 X(J33) = INT(X(J33))
227 NEXT J33
229 REM X(5) = 1
233 X(4) = -115 + 1.089 * X(1) + 1.214 * X(2) + 1.235 * X(3)
281 FOR J44 = 1 TO 3
283 IF X(J44) < 0 THEN 1670
284 IF X(J44) > 100 THEN 1670
285 NEXT J44
331 FOR J44 = 4 TO 4
332 IF X(J44) < 0 THEN PS(J44) = ABS(X(J44)) ELSE PS(J44) = 0
333 NEXT J44
403 POBA2 = -(.0108 * X(1) ^ 2 + .0584 * X(2) ^ 2 + .0942 * X(3) ^ 2 + .0248 * X(1) * X(2) + .0262 * X(1) * X(3) + .1108 * X(2) * X(3))
411 POBA = POBA2 - 1000000 * (PS(4))
459 POB1 = POBA
463 P1NEWMAY = POB1
466 P = P1NEWMAY
1111 IF P <= M THEN 1670
1452 M = P
1453 PPOBA2 = POBA2
1454 FOR KLX = 1 TO 11
1455 A(KLX) = X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M < -224.647 THEN 1999
1900 PRINT A(1), A(2), A(3), A(4)
1904 PRINT M, JJJJ, PPOBA2
1999 NEXT JJJJ
This BASIC computer program was run with qb64v1000-win [5]. The complete output through JJJJ=-24202 is shown below:
53 36 11 .006
-223.8916 -28885 -223.8916
53 35 12 .027
-224.6452 -27481 -224.6452
53 36 11 .006
-223.8916 -25873 -223.8916
53 35 12 .027
-224.6452 -24202 -224.6452
Above there is no rounding by hand; it is just straight copying by hand from the monitor screen.
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [5], the wall-clock time for obtaining the output through JJJJ=-24202 was 2 minutes and 15 seconds.
Acknowledgment
I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
References
[1] Yuichiro Anzai (1974). On Integer Fractional Programming. Journal Operations Research Society of Japan, Volume 17, No. 1, March 1974, pp. 49-66.
www..orsj.or.jp/~archiv/pdf/e_mag/Vol.17_01_049.pdf.
[2] Han-Lin Li, Jung-Fa Tsai (2008). A distributed computational algorithm for solving portfolio problems with integer variables. European Journal of Operational Research 186 (2008) pp.882-891.
[3] Harry Markowitz (1952). Portfolio Selection. The Journal of Finance 7 (2008) pp. 77-91.
[4] 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.
[5] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64.
[6] Jsun Yui Wong (2012, April 12). The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Fractional Programming Problem from the Literature. http://myblogsubstance.typepad.com/substance/2012/04/12/
Saturday, July 29, 2017
Sunday, July 23, 2017
A Computer Program for Integer Fractional Programming, Revised Edition
Jsun Yui Wong
The computer program listed below seeks to solve the integer fractional programming example on pages 55-57 of Anzai [1].
Here X(1) through X(5) are integer variables, and X(6) through X(11) are slack variables.
Whereas line 128 and line 1454 of the preceding paper are 128 FOR I = 1 TO 1000 and 1454 FOR KLX = 1 TO 8, here line 128 and line 1454 are 128 FOR I = 1 TO 50 and 1454 FOR KLX = 1 TO 11, respectively.
0 DEFDBL A-Z
2 DEFINT I, J, K
3 DIM B(99), N(99), A(99), H(99), L(99), U(99), X(1111), D(111), P(111), PS(33)
12 FOR JJJJ = -32000 TO 32000
14 RANDOMIZE JJJJ
16 M = -1D+37
64 FOR J44 = 1 TO 5
65 A(J44) = .1 + RND * 9.899999
66 NEXT J44
126 REM IMAR=10+FIX(RND*32000)
128 FOR I = 1 TO 50
129 FOR KKQQ = 1 TO 5
130 X(KKQQ) = A(KKQQ)
131 NEXT KKQQ
133 FOR IPP = 1 TO (1 + FIX(RND * 4))
181 J = 1 + FIX(RND * 5)
183 R = (1 - RND * 2) * A(J)
187 X(J) = A(J) + (RND ^ (RND * 10)) * R
188 GOTO 222
189 REM X(J)=A(J)+PA
190 REM X(J)=A(J)+FIX(RND*2 )-FIX(RND*2)
191 REM X(J)=A(J)+FIX(RND*3)-FIX(RND*3)
222 NEXT IPP
224 FOR J33 = 1 TO 5
226 X(J33) = INT(X(J33))
227 NEXT J33
229 X(5) = 1
231 REM FOR J44=1 TO 5
233 REM IF X(J44)<.1 THEN 1670
234 REM IF X(J44)>10 THEN 1670
235 REM NEXT J44
240 X(6) = X(1) - 2 * X(2) + 9
259 X(7) = -4 * X(1) - X(2) + 21
261 X(8) = -X(1) + 3 * X(2)
266 X(9) = 4 * X(1) + 5 * X(2) - 12
268 X(10) = 2 * X(3) - 6 * X(4) + 21
270 X(11) = -7 * X(3) - 4 * X(4) + 39
281 FOR J44 = 1 TO 5
283 IF X(J44) < 0 THEN 1670
284 IF X(J44) > 10 THEN 1670
285 NEXT J44
331 FOR J44 = 6 TO 11
332 IF X(J44) < 0 THEN PS(J44) = ABS(X(J44)) ELSE PS(J44) = 0
333 NEXT J44
403 POBA2 = -(-X(1) - 3 * X(2) - X(3) + X(4) - X(5)) / (2 * X(1) + X(2) + 3 * X(3) + 5 * X(4) + X(5))
411 POBA = POBA2 - 999999999# * (PS(6) + PS(7) + PS(8) + PS(9) + PS(10) + PS(11))
459 POB1 = POBA
463 P1NEWMAY = POB1
466 P = P1NEWMAY
1111 IF P <= M THEN 1670
1452 M = P
1453 PPOBA2 = POBA2
1454 FOR KLX = 1 TO 11
1455 A(KLX) = X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 REM IF M<0 THEN 1999
1900 PRINT A(1), A(2), A(3), A(4)
1901 PRINT A(5), A(6), A(7), A(8)
1902 PRINT A(9), A(10), A(11)
1904 PRINT M, JJJJ, PPOBA2
1999 NEXT JJJJ
This BASIC computer program was run with qb64v1000-win [3]. The complete output through JJJJ=-31996 is shown below:
0 4 0 0
1 1 17 12
8 21 39
2.6 -32000 2.6
0 4 0 0
1 1 17 12
8 21 39
2.6 -31999 2.6
0 4 0 0
1 1 17 12
8 21 39
2.6 -31998 2.6
0 2 0 0
1 5 19 6
-2 21 39
-1999999995.666667 -31997 2.333333333333334
0 4 0 0
1 1 17 12
8 21 39
2.6 -31996 2.6
Above there is no rounding by hand; it is just straight copying by hand from the monitor screen.
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [3], the wall-clock time for obtaining the output through JJJJ=-31996 was 3 seconds, not including "Creating .EXEC file" time..
Acknowledgment
I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
References
[1] Yuichiro Anzai (1974). On Integer Fractional Programming. Journal Operations Research Society of Japan, Volume 17, No. 1, March 1974, pp. 49-66.
www..orsj.or.jp/~archiv/pdf/e_mag/Vol.17_01_049.pdf.
[2] 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.
[3] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64
[4] Jsun Yui Wong (2012, April 12). The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Fractional Programming Problem from the Literature. http://myblogsubstance.typepad.com/substance/2012/04/12/
A Computer Program for Integer Fractional Programming
Jsun Yui Wong
The computer program listed below seeks to solve the integer fractional programming example on pages 55-57 of Anzai [1].
Here X(1) through X(5) are integer variables, and X(6) through X(11) are slack variables.
0 DEFDBL A-Z
2 DEFINT I, J, K
3 DIM B(99), N(99), A(99), H(99), L(99), U(99), X(1111), D(111), P(111), PS(33)
12 FOR JJJJ = -32000 TO 32000
14 RANDOMIZE JJJJ
16 M = -1D+37
64 FOR J44 = 1 TO 5
65 A(J44) = .1 + RND * 9.899999
66 NEXT J44
126 REM IMAR=10+FIX(RND*32000)
128 FOR I = 1 TO 1000
129 FOR KKQQ = 1 TO 5
130 X(KKQQ) = A(KKQQ)
131 NEXT KKQQ
133 FOR IPP = 1 TO (1 + FIX(RND * 4))
181 J = 1 + FIX(RND * 5)
183 R = (1 - RND * 2) * A(J)
187 X(J) = A(J) + (RND ^ (RND * 10)) * R
188 GOTO 222
189 REM X(J)=A(J)+PA
190 REM X(J)=A(J)+FIX(RND*2 )-FIX(RND*2)
191 REM X(J)=A(J)+FIX(RND*3)-FIX(RND*3)
222 NEXT IPP
224 FOR J33 = 1 TO 5
226 X(J33) = INT(X(J33))
227 NEXT J33
229 X(5) = 1
231 REM FOR J44=1 TO 5
233 REM IF X(J44)<.1 THEN 1670
234 REM IF X(J44)>10 THEN 1670
235 REM NEXT J44
240 X(6) = X(1) - 2 * X(2) + 9
259 X(7) = -4 * X(1) - X(2) + 21
261 X(8) = -X(1) + 3 * X(2)
266 X(9) = 4 * X(1) + 5 * X(2) - 12
268 X(10) = 2 * X(3) - 6 * X(4) + 21
270 X(11) = -7 * X(3) - 4 * X(4) + 39
281 FOR J44 = 1 TO 5
283 IF X(J44) < 0 THEN 1670
284 IF X(J44) > 10 THEN 1670
285 NEXT J44
331 FOR J44 = 6 TO 11
332 IF X(J44) < 0 THEN PS(J44) = ABS(X(J44)) ELSE PS(J44) = 0
333 NEXT J44
403 POBA2 = -(-X(1) - 3 * X(2) - X(3) + X(4) - X(5)) / (2 * X(1) + X(2) + 3 * X(3) + 5 * X(4) + X(5))
411 POBA = POBA2 - 999999999# * (PS(6) + PS(7) + PS(8) + PS(9) + PS(10) + PS(11))
459 POB1 = POBA
463 P1NEWMAY = POB1
466 P = P1NEWMAY
1111 IF P <= M THEN 1670
1452 M = P
1453 PPOBA2 = POBA2
1454 FOR KLX = 1 TO 8
1455 A(KLX) = X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 REM IF M<0 THEN 1999
1900 PRINT A(1), A(2), A(3), A(4)
1901 PRINT A(5), A(6), A(7), A(8)
1902 PRINT A(9), A(10), A(11)
1904 PRINT M, JJJJ, PPOBA2
1999 NEXT JJJJ
This BASIC computer program was run with qb64v1000-win [3]. The complete output through JJJJ=-31995 is shown below:
0 4 0 0
1 1 17 12
0 0 0
2.6 -32000 2.6
0 4 0 0
1 1 17 12
0 0 0
2.6 -31999 2.6
2 1 0 0
1 9 12 1
0 0 0
1 -31998 1
0 4 0 0
1 1 17 12
0 0 0
2.6 -31997 2.6
0 4 0 0
1 1 17 12
0 0 0
2.6 -31996 2.6
0 4 0 0
1 1 17 12
0 0 0
2.6 -31995 2.6
Above there is no rounding by hand; it is just straight copying by hand from the monitor screen.
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [3], the wall-clock time for obtaining the output through JJJJ=-31995 was 10 seconds.
Acknowledgment
I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
References
[1] Y. Anzai (1974). On Integer Fractional Programming. Journal Operations Research Society of Japan, Volume 17, No. 1, March 1974, pp. 49-66.
[2] 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.
[3] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64
[4] Jsun Yui Wong (2012, April 12). The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Fractional Programming Problem from the Literature. http://myblogsubstance.typepad.com/substance/2012/04/12/
The computer program listed below seeks to solve the integer fractional programming example on pages 55-57 of Anzai [1].
Here X(1) through X(5) are integer variables, and X(6) through X(11) are slack variables.
0 DEFDBL A-Z
2 DEFINT I, J, K
3 DIM B(99), N(99), A(99), H(99), L(99), U(99), X(1111), D(111), P(111), PS(33)
12 FOR JJJJ = -32000 TO 32000
14 RANDOMIZE JJJJ
16 M = -1D+37
64 FOR J44 = 1 TO 5
65 A(J44) = .1 + RND * 9.899999
66 NEXT J44
126 REM IMAR=10+FIX(RND*32000)
128 FOR I = 1 TO 1000
129 FOR KKQQ = 1 TO 5
130 X(KKQQ) = A(KKQQ)
131 NEXT KKQQ
133 FOR IPP = 1 TO (1 + FIX(RND * 4))
181 J = 1 + FIX(RND * 5)
183 R = (1 - RND * 2) * A(J)
187 X(J) = A(J) + (RND ^ (RND * 10)) * R
188 GOTO 222
189 REM X(J)=A(J)+PA
190 REM X(J)=A(J)+FIX(RND*2 )-FIX(RND*2)
191 REM X(J)=A(J)+FIX(RND*3)-FIX(RND*3)
222 NEXT IPP
224 FOR J33 = 1 TO 5
226 X(J33) = INT(X(J33))
227 NEXT J33
229 X(5) = 1
231 REM FOR J44=1 TO 5
233 REM IF X(J44)<.1 THEN 1670
234 REM IF X(J44)>10 THEN 1670
235 REM NEXT J44
240 X(6) = X(1) - 2 * X(2) + 9
259 X(7) = -4 * X(1) - X(2) + 21
261 X(8) = -X(1) + 3 * X(2)
266 X(9) = 4 * X(1) + 5 * X(2) - 12
268 X(10) = 2 * X(3) - 6 * X(4) + 21
270 X(11) = -7 * X(3) - 4 * X(4) + 39
281 FOR J44 = 1 TO 5
283 IF X(J44) < 0 THEN 1670
284 IF X(J44) > 10 THEN 1670
285 NEXT J44
331 FOR J44 = 6 TO 11
332 IF X(J44) < 0 THEN PS(J44) = ABS(X(J44)) ELSE PS(J44) = 0
333 NEXT J44
403 POBA2 = -(-X(1) - 3 * X(2) - X(3) + X(4) - X(5)) / (2 * X(1) + X(2) + 3 * X(3) + 5 * X(4) + X(5))
411 POBA = POBA2 - 999999999# * (PS(6) + PS(7) + PS(8) + PS(9) + PS(10) + PS(11))
459 POB1 = POBA
463 P1NEWMAY = POB1
466 P = P1NEWMAY
1111 IF P <= M THEN 1670
1452 M = P
1453 PPOBA2 = POBA2
1454 FOR KLX = 1 TO 8
1455 A(KLX) = X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 REM IF M<0 THEN 1999
1900 PRINT A(1), A(2), A(3), A(4)
1901 PRINT A(5), A(6), A(7), A(8)
1902 PRINT A(9), A(10), A(11)
1904 PRINT M, JJJJ, PPOBA2
1999 NEXT JJJJ
This BASIC computer program was run with qb64v1000-win [3]. The complete output through JJJJ=-31995 is shown below:
0 4 0 0
1 1 17 12
0 0 0
2.6 -32000 2.6
0 4 0 0
1 1 17 12
0 0 0
2.6 -31999 2.6
2 1 0 0
1 9 12 1
0 0 0
1 -31998 1
0 4 0 0
1 1 17 12
0 0 0
2.6 -31997 2.6
0 4 0 0
1 1 17 12
0 0 0
2.6 -31996 2.6
0 4 0 0
1 1 17 12
0 0 0
2.6 -31995 2.6
Above there is no rounding by hand; it is just straight copying by hand from the monitor screen.
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [3], the wall-clock time for obtaining the output through JJJJ=-31995 was 10 seconds.
Acknowledgment
I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
References
[1] Y. Anzai (1974). On Integer Fractional Programming. Journal Operations Research Society of Japan, Volume 17, No. 1, March 1974, pp. 49-66.
[2] 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.
[3] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64
[4] Jsun Yui Wong (2012, April 12). The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Fractional Programming Problem from the Literature. http://myblogsubstance.typepad.com/substance/2012/04/12/
Monday, June 19, 2017
Solving a Double Row Layout Problem Having 16 Facilities
Jsun Yui Wong
Based on the computer program in Wong [17], the following computer program seeks to solve the problem named P16_a in Fischer, Fischer, and Hungerlander [10, p. 129, Table 1]. The data come from the PROP Instances-Amaral 2013 section of Anjos [8].
0 REM DEFDBL A-Z
1 DEFINT I, J, K, X, A
2 DIM B(99), N(99), A(2002), H(99), L(99), U(99), X(2002), D(111), P(111), PS(33), J44(2002), J(99), AA(99), HR(32), HHR(32), Y(33), C(33), CC(33)
3 DIM HS(49, 49)
4 DIM PE(49, 49)
5 DIM SD(49, 49)
27 HR(1) = 14: HR(2) = 11: HR(3) = 9: HR(4) = 5: HR(5) = 13
28 REM HR(6)=4:HR(7)=6:HR(8)=8:HR(9)=9
29 HR(6) = 5: HR(7) = 14: HR(8) = 7: HR(9) = 10: HR(10) = 11
30 HR(11) = 8: HR(12) = 14: HR(13) = 10: HR(14) = 11: HR(15) = 8: HR(16) = 5
31 FOR IL = 1 TO 16
32 FOR JL = 1 TO 16
33 READ HS(IL, JL)
34 NEXT JL
35 NEXT IL
61 DATA 999,0,5,0,5,2,10,3,1,5,5,5,0,0,5,4
62 DATA 0,999,3,10,5,1,5,1,2,4,2,5,0,10,10,3
63 DATA 5,3,999,2,0,5,2,4,4,5,0,0,0,5,1,0
64 DATA 0,10,2,999,1,0,5,2,1,0,10,2,2,0,2,1
66 DATA 5,5,0,1,999,5,6,5,2,5,2,0,5,1,1,1
67 DATA 2,1,5,0,5,999,5,2,1,6,0,0,10,0,2,0
68 DATA 10,5,2,5,6,5,999,0,0,0,5,10,2,2,5,1
69 DATA 3,1,4,2,5,2,0,999,1,1,10,10,2,0,10,2
70 DATA 1,2,4,1,2,1,0,1,999,2,0,3,5,5,0,5
71 DATA 5,4,5,0,5,6,0,1,2,999,5,5,0,5,1,0
72 DATA 5,2,0,10,2,0,5,10,0,5,999,5,2,5,1,10
73 DATA 5,5,0,2,0,0,10,10,3,5,5,999,2,10,5,0
74 DATA 0,0,0,2,5,10,2,2,5,0,2,2,999,2,2,1
75 DATA 0,10,5,0,1,0,2,0,5,5,5,10,2,999,5,5
76 DATA 5,10,1,2,1,2,5,10,0,1,1,5,2,5,999,3
77 DATA 4,3,0,1,1,0,1,2,5,0,10,0,1,5,3,999
78 FOR JJJJ = -32000 TO 32000
79 RANDOMIZE JJJJ
80 M = -1D+37
81 IMAX = 2 + FIX(RND * 13)
82 FOR J44 = 1 TO 16
83 A(J44) = J44
84 NEXT J44
111 REM IF RND < 1 / 4 THEN IMAX = 8 ELSE IF RND < 1 / 3 THEN IMAX = 9 ELSE IF RND < 1 / 2 THEN IMAX = 10 ELSE IMAX = 11
126 REM IMAR=10+FIX(RND*1000)
128 FOR I = 1 TO 1000
129 FOR KKQQ = 1 TO 16
130 X(KKQQ) = A(KKQQ)
131 NEXT KKQQ
133 III = 1 + FIX(RND * 16)
134 JJJ = 1 + FIX(RND * 16)
221 X(III) = A(JJJ)
223 X(JJJ) = A(III)
231 FOR J44 = 1 TO 16
233 FOR J45 = 1 TO 16
234 IF X(J44) = J45 THEN HHR(J44) = HR(J44) ELSE GOTO 238
237 Y(J45) = J44
238 NEXT J45
253 FOR ISE20 = 1 TO IMAX
254 C(ISE20) = .5 * HHR(Y(ISE20))
258 FOR ISE2000 = ISE20 + 1 TO IMAX
259 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))
263 NEXT ISE2000
269 NEXT ISE20
386 FOR ISE20N = IMAX + 1 TO 16
387 C(ISE20N) = .5 * HHR(Y(ISE20N))
388 FOR ISE2000N = ISE20N + 1 TO 16
389 C(ISE20N) = C(ISE20N) + HHR(Y(ISE2000N))
390 NEXT ISE2000N
391 NEXT ISE20N
395 NEXT J44
411 PROD = 0
412 FOR J44 = 1 TO 16
413 FOR J45 = J44 + 1 TO 16
414 PROD = PROD - HS(Y(J44), Y(J45)) * ABS(C(J44) - C(J45))
415 NEXT J45
416 NEXT J44
422 P = PROD
1111 IF P <= M THEN 1670
1452 M = P
1453 FOR KLX = 1 TO 16
1454 CC(KLX) = C(KLX)
1455 A(KLX) = X(KLX)
1456 NEXT KLX
1559 Iimax = IMAX
1657 GOTO 128
1670 NEXT I
1889 IF M < -7371 THEN 1999
1901 PRINT A(1), A(2), A(3), A(4), A(5)
1902 PRINT A(6), A(7), A(8), A(9), A(10)
1903 PRINT A(11), A(12), A(13), A(14), A(15), A(16)
1905 REM PRINT CC(1), CC(2), CC(3), CC(4), CC(5)
1906 REM PRINT CC(6), CC(7), CC(8), CC(9), CC(10)
1907 REM PRINT CC(11), CC(12), CC(13), CC(14), CC(15)
1919 PRINT M, JJJJ, Iimax
1999 NEXT JJJJ
This computer program was run with qb64v1000-win [16]. The complete output through JJJJ=-29826 is shown below:
16 4 3 13 2
9 7 14 1 10
5 6 8 11 15
12
-7370 -31479 7
16 4 3 13 2
9 7 14 1 10
5 6 8 11 15
12
-7370 -31269 7
16 4 3 13 2
9 7 14 1 10
5 6 8 11 15
12
-7370 -30457 7
9 13 12 6 11
2 16 7 10 3
14 15 1 4 8
5
-7370 -29826 9
Above there is no rounding by hand; it is just straight copying by hand from the monitor screen.
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [16], the wall-clock time for obtaining the output through JJJJ=-29826 was five minutes.
Acknowledgment
I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
References
[1] Andre R. S. Amaral (2006), On the Exact Solution of a Facility Layout Problem. European Journal of Operational Research 173 (2006), pp. 508-518.
[2] Andre R. S. Amaral (2008), An Exact Approach to the One-Dimensional Facility Layout Problem. Operations Research, Vol. 56, No. 4 (July-August, 2008), pp. 1026-1033.
[3] Andre R. S. Amaral (2011), Optimal Solutions for the Double Row Layout Problem. Optimization Letters, DOI 10.1007/s11590-011-0426-8, published on line 30 November 2011, Springer-Verlag 2011.
[4] Andre R. S. Amaral (2012), The Corridor Allocation Problem. Computers and Operations Research 39 (2012), pp. 3325-3330.
[5] Andre R. S. Amaral (2013), A Parallel Ordering Problem in Facilities Layout. Computers and Operations Research, Vol. 40, Issue 12, December 2013, pp. 2930-2939.
[6] Miguel F. Anjos, Anthony Vannelli, Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes. INFORMS Journal on Computing, Vol. 20, No. 4, Fall 2008, pp. 611-617.
[7] Miguel F. Anjos (2012), FLPLIB–Facility Layout Database. Retrieved on September 25 2012 from http://www.gerad.ca/files/Sites/Anjos/indexFR.html
[8] Miguel F. Anjos, FLPLIB–Facility Layout Database. http://www.miguelanjos.com.
[9] Miguel Anjos. QAP - A Quadratic Assignment Problem Library. www.anjos.mgi.polymtl.ca/qaplib/data.d/sko49.dat
[10] Anja Fischer, Frank Fischer. Philipp Hungerlaender, A New Exact Approach to the Space-Free Double Row Layout Problem.
K. Doerner et al. (eds) Operations Research Proceedings 2015. Springer 2017.
[11] S. S. Heragu, A. Kusiak. Efficient Models for the Facility Layout Problem. European Journal of Operational Research 53 (1), 1991, pp. 1-13.
[12] Philipp Hungerlaender, Miguel F. Anjos (January 2012), A Semidefinite Optimization Approach to Free-Space Multi-Row Facility Layout. Les Cahiers du GERAD. Retrieved from http://www.gerad.ca/fichiers/cahiers/G-2012-03.pdf
[13] Robert F. Love, Jsun Yui Wong (1976), On Solving a One-Dimensional Space Allocation Problem with Integer Programming, INFOR 14(2), pp. 139-143.
[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] C. E. Nugent, T. E Vollmann, J. Ruml (1968), An Experimental Comparison of Techniques for the Assignment of Facilities to Locations. Operations Research, Vol. 16, pp. 150-173.
[16] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64
[17] Jsun Yui Wong (2012, September 20). A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Corridor Allocation Problem with Fifteen Facilities, Fifth Edition. https://myblogsubstance.typepad.com/substance/2012/09/index.html/
[18] Ginger Yen (2008). Cutting-Plane Separation Strategies for Semidefinite Programming Models to Solve Single-Row Facility Layout Problems. A Master Thesis Presented to the University of Waterloo
Based on the computer program in Wong [17], the following computer program seeks to solve the problem named P16_a in Fischer, Fischer, and Hungerlander [10, p. 129, Table 1]. The data come from the PROP Instances-Amaral 2013 section of Anjos [8].
0 REM DEFDBL A-Z
1 DEFINT I, J, K, X, A
2 DIM B(99), N(99), A(2002), H(99), L(99), U(99), X(2002), D(111), P(111), PS(33), J44(2002), J(99), AA(99), HR(32), HHR(32), Y(33), C(33), CC(33)
3 DIM HS(49, 49)
4 DIM PE(49, 49)
5 DIM SD(49, 49)
27 HR(1) = 14: HR(2) = 11: HR(3) = 9: HR(4) = 5: HR(5) = 13
28 REM HR(6)=4:HR(7)=6:HR(8)=8:HR(9)=9
29 HR(6) = 5: HR(7) = 14: HR(8) = 7: HR(9) = 10: HR(10) = 11
30 HR(11) = 8: HR(12) = 14: HR(13) = 10: HR(14) = 11: HR(15) = 8: HR(16) = 5
31 FOR IL = 1 TO 16
32 FOR JL = 1 TO 16
33 READ HS(IL, JL)
34 NEXT JL
35 NEXT IL
61 DATA 999,0,5,0,5,2,10,3,1,5,5,5,0,0,5,4
62 DATA 0,999,3,10,5,1,5,1,2,4,2,5,0,10,10,3
63 DATA 5,3,999,2,0,5,2,4,4,5,0,0,0,5,1,0
64 DATA 0,10,2,999,1,0,5,2,1,0,10,2,2,0,2,1
66 DATA 5,5,0,1,999,5,6,5,2,5,2,0,5,1,1,1
67 DATA 2,1,5,0,5,999,5,2,1,6,0,0,10,0,2,0
68 DATA 10,5,2,5,6,5,999,0,0,0,5,10,2,2,5,1
69 DATA 3,1,4,2,5,2,0,999,1,1,10,10,2,0,10,2
70 DATA 1,2,4,1,2,1,0,1,999,2,0,3,5,5,0,5
71 DATA 5,4,5,0,5,6,0,1,2,999,5,5,0,5,1,0
72 DATA 5,2,0,10,2,0,5,10,0,5,999,5,2,5,1,10
73 DATA 5,5,0,2,0,0,10,10,3,5,5,999,2,10,5,0
74 DATA 0,0,0,2,5,10,2,2,5,0,2,2,999,2,2,1
75 DATA 0,10,5,0,1,0,2,0,5,5,5,10,2,999,5,5
76 DATA 5,10,1,2,1,2,5,10,0,1,1,5,2,5,999,3
77 DATA 4,3,0,1,1,0,1,2,5,0,10,0,1,5,3,999
78 FOR JJJJ = -32000 TO 32000
79 RANDOMIZE JJJJ
80 M = -1D+37
81 IMAX = 2 + FIX(RND * 13)
82 FOR J44 = 1 TO 16
83 A(J44) = J44
84 NEXT J44
111 REM IF RND < 1 / 4 THEN IMAX = 8 ELSE IF RND < 1 / 3 THEN IMAX = 9 ELSE IF RND < 1 / 2 THEN IMAX = 10 ELSE IMAX = 11
126 REM IMAR=10+FIX(RND*1000)
128 FOR I = 1 TO 1000
129 FOR KKQQ = 1 TO 16
130 X(KKQQ) = A(KKQQ)
131 NEXT KKQQ
133 III = 1 + FIX(RND * 16)
134 JJJ = 1 + FIX(RND * 16)
221 X(III) = A(JJJ)
223 X(JJJ) = A(III)
231 FOR J44 = 1 TO 16
233 FOR J45 = 1 TO 16
234 IF X(J44) = J45 THEN HHR(J44) = HR(J44) ELSE GOTO 238
237 Y(J45) = J44
238 NEXT J45
253 FOR ISE20 = 1 TO IMAX
254 C(ISE20) = .5 * HHR(Y(ISE20))
258 FOR ISE2000 = ISE20 + 1 TO IMAX
259 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))
263 NEXT ISE2000
269 NEXT ISE20
386 FOR ISE20N = IMAX + 1 TO 16
387 C(ISE20N) = .5 * HHR(Y(ISE20N))
388 FOR ISE2000N = ISE20N + 1 TO 16
389 C(ISE20N) = C(ISE20N) + HHR(Y(ISE2000N))
390 NEXT ISE2000N
391 NEXT ISE20N
395 NEXT J44
411 PROD = 0
412 FOR J44 = 1 TO 16
413 FOR J45 = J44 + 1 TO 16
414 PROD = PROD - HS(Y(J44), Y(J45)) * ABS(C(J44) - C(J45))
415 NEXT J45
416 NEXT J44
422 P = PROD
1111 IF P <= M THEN 1670
1452 M = P
1453 FOR KLX = 1 TO 16
1454 CC(KLX) = C(KLX)
1455 A(KLX) = X(KLX)
1456 NEXT KLX
1559 Iimax = IMAX
1657 GOTO 128
1670 NEXT I
1889 IF M < -7371 THEN 1999
1901 PRINT A(1), A(2), A(3), A(4), A(5)
1902 PRINT A(6), A(7), A(8), A(9), A(10)
1903 PRINT A(11), A(12), A(13), A(14), A(15), A(16)
1905 REM PRINT CC(1), CC(2), CC(3), CC(4), CC(5)
1906 REM PRINT CC(6), CC(7), CC(8), CC(9), CC(10)
1907 REM PRINT CC(11), CC(12), CC(13), CC(14), CC(15)
1919 PRINT M, JJJJ, Iimax
1999 NEXT JJJJ
This computer program was run with qb64v1000-win [16]. The complete output through JJJJ=-29826 is shown below:
16 4 3 13 2
9 7 14 1 10
5 6 8 11 15
12
-7370 -31479 7
16 4 3 13 2
9 7 14 1 10
5 6 8 11 15
12
-7370 -31269 7
16 4 3 13 2
9 7 14 1 10
5 6 8 11 15
12
-7370 -30457 7
9 13 12 6 11
2 16 7 10 3
14 15 1 4 8
5
-7370 -29826 9
Above there is no rounding by hand; it is just straight copying by hand from the monitor screen.
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [16], the wall-clock time for obtaining the output through JJJJ=-29826 was five minutes.
Acknowledgment
I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
References
[1] Andre R. S. Amaral (2006), On the Exact Solution of a Facility Layout Problem. European Journal of Operational Research 173 (2006), pp. 508-518.
[2] Andre R. S. Amaral (2008), An Exact Approach to the One-Dimensional Facility Layout Problem. Operations Research, Vol. 56, No. 4 (July-August, 2008), pp. 1026-1033.
[3] Andre R. S. Amaral (2011), Optimal Solutions for the Double Row Layout Problem. Optimization Letters, DOI 10.1007/s11590-011-0426-8, published on line 30 November 2011, Springer-Verlag 2011.
[4] Andre R. S. Amaral (2012), The Corridor Allocation Problem. Computers and Operations Research 39 (2012), pp. 3325-3330.
[5] Andre R. S. Amaral (2013), A Parallel Ordering Problem in Facilities Layout. Computers and Operations Research, Vol. 40, Issue 12, December 2013, pp. 2930-2939.
[6] Miguel F. Anjos, Anthony Vannelli, Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes. INFORMS Journal on Computing, Vol. 20, No. 4, Fall 2008, pp. 611-617.
[7] Miguel F. Anjos (2012), FLPLIB–Facility Layout Database. Retrieved on September 25 2012 from http://www.gerad.ca/files/Sites/Anjos/indexFR.html
[8] Miguel F. Anjos, FLPLIB–Facility Layout Database. http://www.miguelanjos.com.
[9] Miguel Anjos. QAP - A Quadratic Assignment Problem Library. www.anjos.mgi.polymtl.ca/qaplib/data.d/sko49.dat
[10] Anja Fischer, Frank Fischer. Philipp Hungerlaender, A New Exact Approach to the Space-Free Double Row Layout Problem.
K. Doerner et al. (eds) Operations Research Proceedings 2015. Springer 2017.
[11] S. S. Heragu, A. Kusiak. Efficient Models for the Facility Layout Problem. European Journal of Operational Research 53 (1), 1991, pp. 1-13.
[12] Philipp Hungerlaender, Miguel F. Anjos (January 2012), A Semidefinite Optimization Approach to Free-Space Multi-Row Facility Layout. Les Cahiers du GERAD. Retrieved from http://www.gerad.ca/fichiers/cahiers/G-2012-03.pdf
[13] Robert F. Love, Jsun Yui Wong (1976), On Solving a One-Dimensional Space Allocation Problem with Integer Programming, INFOR 14(2), pp. 139-143.
[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] C. E. Nugent, T. E Vollmann, J. Ruml (1968), An Experimental Comparison of Techniques for the Assignment of Facilities to Locations. Operations Research, Vol. 16, pp. 150-173.
[16] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64
[17] Jsun Yui Wong (2012, September 20). A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Corridor Allocation Problem with Fifteen Facilities, Fifth Edition. https://myblogsubstance.typepad.com/substance/2012/09/index.html/
[18] Ginger Yen (2008). Cutting-Plane Separation Strategies for Semidefinite Programming Models to Solve Single-Row Facility Layout Problems. A Master Thesis Presented to the University of Waterloo
Friday, May 19, 2017
Solving a k-Parallel Row Ordering Problem in Layout of 36 Facilities in 18 Rows
Jsun Yui Wong
Adapting to the computer program in Wong [14], the following computer program seeks to solve a k-parallel row ordering problem (k-PROP) of 36 facilities. Each row of the 18 rows has 2 facilities. See Amaral [5]. The data for flows and lengths used here can be found in Yen [15, pages 101-105 for flows and page 106 for lengths]. One notes that these lengths are the lengths of C.4.6 STE36-8 in Yen [15, p. 106].
0 REM DEFDBL A-Z
1 DEFINT I, J, K, X
2 DIM B(99), N(99), A(2002), H(99), L(99), U(99), X(2002), D(111), P(111), PS(39), J44(2002), J(99), AA(99), HR(39), HHR(39), Y(39), C(39), CC(39), RA(99)
3 DIM HS(49, 49)
4 DIM PE(49, 49)
5 DIM SD(49, 49)
17 HR(1) = 4: HR(2) = 2: HR(3) = 3: HR(4) = 2: HR(5) = 3: HR(6) = 1: HR(7) = 3: HR(8) = 1: HR(9) = 3
18 HR(10) = 4: HR(11) = 5: HR(12) = 2: HR(13) = 2: HR(14) = 3: HR(15) = 3: HR(16) = 3: HR(17) = 5: HR(18) = 3: HR(19) = 3: HR(20) = 5
19 HR(21) = 2: HR(22) = 5: HR(23) = 3
20 HR(24) = 3: HR(25) = 5: HR(26) = 4: HR(27) = 4: HR(28) = 3: HR(29) = 4: HR(30) = 3
29 HR(31) = 2: HR(32) = 2: HR(33) = 3: HR(34) = 2: HR(35) = 5: HR(36) = 3
31 FOR IL = 1 TO 36
32 FOR JL = 1 TO 36
33 READ HS(IL, JL)
34 NEXT JL
35 NEXT IL
41 DATA 9999,0,0,2,1,7,9,0,4,75,7,12,22,7,1,0,0,0,0,23,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
42 DATA 0,9999,0,0,0,0,4,16,0,8,0,0,16,0,0,0,0,6,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
43 DATA 0,0,9999,0,0,4,16,20,0,0,0,0,20,0,0,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
44 DATA 2,0,0,9999,29,5,18,47,23,2,4,0,48,0,4,0,0,0,0,25,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
45 DATA 1,0,0,29,9999,18,12,25,0,0,4,0,25,0,3,0,0,0,0,18,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0
46 DATA 7,0,4,5,18,9999,4,2,0,1,23,2,19,0,0,0,0,0,2,19,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
47 DATA 9,4,16,18,12,4,9999,0,14,72,7,8,39,8,40,8,0,8,4,7,0,0,0,0,0,0,0,28,8,0,0,0,0,0,0,0
48 DATA 0,16,20,47,25,2,0,9999,10,71,2,0,0,0,0,0,0,41,0,0,0,0,0,0,0,0,7,8,0,0,0,0,0,0,0,0
49 DATA 4,0,0,23,0,0,14,10,9999,14,0,0,18,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
50 DATA 75,8,0,2,0,1,72,71,14,9999,11,1,17,0,1,0,0,17,0,15,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
51 DATA 7,0,0,4,4,23,7,2,0,11,9999,316,33,8,2,0,0,0,8,34,0,0,6,0,0,0,10,0,0,6,0,0,0,0,0,0
52 DATA 12,0,0,0,0,2,8,0,0,1,316,9999,157,25,4,0,0,1,0,0,0,0,0,0,22,0,1,0,0,0,0,0,0,0,0,0
53 DATA 22,16,20,48,25,19,39,0,18,17,33,157,9999,11,6,0,0,6,0,5,8,3,10,0,0,0,9,11,2,0,0,1,0,0,0,0
54 DATA 7,0,0,0,0,0,8,0,0,0,8,25,11,9999,3,0,0,1,1,21,0,1,0,2,0,0,5,0,0,3,2,5,5,4,0,0
55 DATA 1,0,0,4,3,0,40,0,0,1,2,4,6,3,9999,19,0,2,2,12,0,0,0,0,0,0,0,7,3,0,0,0,0,0,0,0
56 DATA 0,0,0,0,0,0,8,0,0,0,0,0,0,0,19,9999,0,6,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
57 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,9999,40,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
58 DATA 0,6,0,0,0,0,8,41,0,17,0,1,6,1,2,6,40,9999,0,26,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
59 DATA 0,0,0,0,0,2,4,0,0,0,8,0,0,1,2,0,0,0,9999,13,9,0,7,0,0,0,0,27,16,3,0,20,0,4,0,0
60 DATA 23,4,4,25,18,19,7,0,0,15,34,0,5,21,12,1,0,26,13,9999,11,4,36,0,0,0,16,18,9,10,1,28,6,2,0,0
61 DATA 0,0,0,0,0,0,0,0,0,0,0,0,8,0,0,0,0,0,9,11,9999,36,6,0,8,0,2,0,0,0,0,0,0,0,0,0
62 DATA 0,0,0,0,3,0,0,0,0,0,0,0,3,1,0,0,0,0,0,4,36,9999,0,0,0,0,4,0,0,0,0,0,0,0,0,0
63 DATA 0,0,0,0,0,0,0,0,0,0,6,0,10,0,0,0,0,0,7,36,6,0,9999,0,0,12,9,0,0,0,0,0,0,0,0,0
64 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,9999,26,0,5,0,0,0,0,0,0,0,0,0
65 DATA 0,0,0,0,0,0,0,0,0,0,0,22,0,0,0,0,0,0,0,0,8,0,0,26,9999,35,2,0,0,0,0,0,0,0,0,0
66 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,12,0,35,9999,4,0,0,0,0,0,0,0,0,0
67 DATA 0,0,0,0,0,0,0,7,0,0,10,1,9,5,0,0,0,0,0,16,2,4,9,5,2,4,9999,0,0,0,0,0,0,0,0,0
68 DATA 0,0,0,0,0,0,28,8,0,0,0,0,11,0,7,0,0,0,27,18,0,0,0,0,0,0,0,9999,10,22,4,6,4,12,0,0
69 DATA 0,0,0,0,0,0,8,0,0,0,0,0,2,0,3,0,0,0,16,9,0,0,0,0,0,0,0,10,9999,19,12,0,0,0,0,0
70 DATA 0,0,0,0,0,0,0,0,0,0,6,0,0,3,0,0,0,0,3,10,0,0,0,0,0,0,0,22,19,9999,19,4,5,8,0,0
71 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,1,0,0,0,0,0,0,0,4,12,19,9999,0,3,13,0,0
72 DATA 0,0,0,0,0,0,0,0,0,0,0,0,1,5,0,0,0,0,20,28,0,0,0,0,0,0,0,6,0,4,0,9999,18,24,0,0
73 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,0,0,0,0,6,0,0,0,0,0,0,0,4,0,5,3,18,9999,20,0,0
74 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,4,0,0,0,0,4,2,0,0,0,0,0,0,0,12,0,8,13,24,20,9999,0,0
75 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,9999,0
76 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,9999
88 FOR JJJJ = -32000 TO 32000
89 RANDOMIZE JJJJ
90 M = -1D+37
91 FOR J44 = 1 TO 36
93 A(J44) = J44
94 NEXT J44
128 FOR I = 1 TO 1000
129 FOR KKQQ = 1 TO 36
130 X(KKQQ) = A(KKQQ)
131 NEXT KKQQ
133 III = 1 + FIX(RND * 36)
134 JJJ = 1 + FIX(RND * 36)
137 X(III) = A(JJJ)
139 X(JJJ) = A(III)
231 FOR J44 = 1 TO 36
233 FOR J45 = 1 TO 36
234 IF X(J44) = J45 THEN HHR(J44) = HR(J44) ELSE GOTO 238
237 Y(J45) = J44
238 NEXT J45
244 FOR RN = 1 TO 18
251 FOR ISE20 = (RN - 1) * 2 + 1 TO RN * 2
254 C(ISE20) = .5 * HHR(Y(ISE20))
258 FOR ISE2000 = ISE20 + 1 TO RN * 2
259 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))
263 NEXT ISE2000
269 NEXT ISE20
299 NEXT RN
499 NEXT J44
551 FOR RN = 1 TO 18
601 FOR J77 = (RN - 1) * 2 + 1 TO RN * 2
605 IF X(J77) > RN * 2 THEN 1670
609 NEXT J77
610 NEXT RN
811 PROD = 0
812 FOR J44 = 1 TO 36
813 FOR J45 = J44 + 1 TO 36
814 PROD = PROD - HS(Y(J44), Y(J45)) * ABS(C(J44) - C(J45))
815 NEXT J45
816 NEXT J44
822 P = PROD
1111 IF P <= M THEN 1670
1452 M = P
1453 FOR KLX = 1 TO 36
1454 CC(KLX) = C(KLX)
1455 A(KLX) = X(KLX)
1456 NEXT KLX
1657 GOTO 128
1670 NEXT I
1889 REM IF M < -999999 THEN 1999
1891 PRINT A(1), A(2), A(3), A(4), A(5)
1892 PRINT A(6), A(7), A(8), A(9), A(10)
1893 PRINT A(11), A(12), A(13), A(14), A(15)
1894 PRINT A(16), A(17), A(18), A(19), A(20)
1896 PRINT A(21), A(22), A(23), A(24), A(25)
1897 PRINT A(26), A(27), A(28), A(29), A(30)
1898 PRINT A(31), A(32), A(33), A(34), A(35), A(36), M, JJJJ
1999 NEXT JJJJ
1999 NEXT JJJJ
This computer program was run with qb64v1000-win [13]. The complete output through JJJJ=-31996 is shown below:
2 1 4 3 6
5 8 7 9 10
12 11 13 14 16
15 17 18 19 20
21 22 24 23 25
26 27 28 29 30
32 31 33 34 35
36 -5032 -32000
2 1 3 4 6
5 8 7 9 10
11 12 14 13 16
15 17 18 19 20
22 21 23 24 26
25 27 28 29 30
32 31 33 34 36
35 -4844 -31999
2 1 3 4 6
5 8 7 9 10
11 12 14 13 16
15 17 18 19 20
22 21 23 24 26
25 27 28 29 30
32 31 33 34 35
36 -4844 -31998
2 1 3 4 6
5 7 8 9 10
11 12 14 13 16
15 17 18 19 20
22 21 23 24 26
25 27 28 29 30
32 31 33 34 35
36 -4920 -31997
2 1 3 4 6
5 7 8 9 10
12 11 13 14 15
16 17 18 19 20
21 22 24 23 25
26 27 28 29 30
32 31 33 34 35
36 -5230 -31996
Above there is no rounding by hand; it is just straight copying by hand from the monitor screen.
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [13], the wall-clock time for obtaining the output through JJJJ=-31996 was 10 seconds.
Acknowledgment
I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
References
[1] Andre R. S. Amaral (2006), On the Exact Solution of a Facility Layout Problem. European Journal of Operational Research 173 (2006), pp. 508-518.
[2] Andre R. S. Amaral (2008), An Exact Approach to the One-Dimensional Facility Layout Problem. Operations Research, Vol. 56, No. 4 (July-August, 2008), pp. 1026-1033.
[3] Andre R. S. Amaral (2011), Optimal Solutions for the Double Row Layout Problem. Optimization Letters, DOI 10.1007/s11590-011-0426-8, published on line 30 November 2011, Springer-Verlag 2011.
[4] Andre R. S. Amaral (2012), The Corridor Allocation Problem. Computers and Operations Research 39 (2012), pp. 3325-3330.
[5] Andre R. S. Amaral (2013), A Parallel Ordering Problem in Facilities Layout. Computers and Operations Research, Vol. 40, Issue 12, December 2013, pp. 2930-2939.
[6] Miguel F. Anjos, Anthony Vannelli, Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes. INFORMS Journal on Computing, Vol. 20, No. 4, Fall 2008, pp. 611-617.
[7] Miguel F. Anjos (2012), FLPLIB–Facility Layout Database. Retrieved on September 25 2012 from http://www.gerad.ca/files/Sites/Anjos/indexFR.html
[8] Miguel F. Anjos, FLPLIB–Facility Layout Database. http://www.miguelanjos.com.
[9] S. S. Heragu, A. Kusiak. Efficient Models for the Facility Layout Problem. European Journal of Operational Research 53 (1), 1991, pp. 1-13.
[10] Philipp Hungerlaender, Miguel F. Anjos (January 2012), A Semidefinite Optimization Approach to Free-Space Multi-Row Facility Layout. Les Cahiers du GERAD. Retrieved from http://www.gerad.ca/fichiers/cahiers/G-2012-03.pdf
[11] 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.
[12] C. E. Nugent, T. E Vollmann, J. Ruml (1968), An Experimental Comparison of Techniques for the Assignment of Facilities to Locations. Operations Research, Vol. 16, pp. 150-173.
[13] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64
[14] Jsun Yui Wong (2012, September 17). A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Corridor Allocation Problem with Eleven Facilities, Third Edition. https://myblogsubstance.typepad.com/substance/2012/09/index.html/
[15] Ginger Yen (2008). Cutting-Plane Separation Strategies for Semidefinite Programming Models to Solve Single-Row Facility Layout Problems. A Master Thesis Presented to the University of Waterloo. UWSpace. http://hdl.handle.net/10012/4104.
Adapting to the computer program in Wong [14], the following computer program seeks to solve a k-parallel row ordering problem (k-PROP) of 36 facilities. Each row of the 18 rows has 2 facilities. See Amaral [5]. The data for flows and lengths used here can be found in Yen [15, pages 101-105 for flows and page 106 for lengths]. One notes that these lengths are the lengths of C.4.6 STE36-8 in Yen [15, p. 106].
0 REM DEFDBL A-Z
1 DEFINT I, J, K, X
2 DIM B(99), N(99), A(2002), H(99), L(99), U(99), X(2002), D(111), P(111), PS(39), J44(2002), J(99), AA(99), HR(39), HHR(39), Y(39), C(39), CC(39), RA(99)
3 DIM HS(49, 49)
4 DIM PE(49, 49)
5 DIM SD(49, 49)
17 HR(1) = 4: HR(2) = 2: HR(3) = 3: HR(4) = 2: HR(5) = 3: HR(6) = 1: HR(7) = 3: HR(8) = 1: HR(9) = 3
18 HR(10) = 4: HR(11) = 5: HR(12) = 2: HR(13) = 2: HR(14) = 3: HR(15) = 3: HR(16) = 3: HR(17) = 5: HR(18) = 3: HR(19) = 3: HR(20) = 5
19 HR(21) = 2: HR(22) = 5: HR(23) = 3
20 HR(24) = 3: HR(25) = 5: HR(26) = 4: HR(27) = 4: HR(28) = 3: HR(29) = 4: HR(30) = 3
29 HR(31) = 2: HR(32) = 2: HR(33) = 3: HR(34) = 2: HR(35) = 5: HR(36) = 3
31 FOR IL = 1 TO 36
32 FOR JL = 1 TO 36
33 READ HS(IL, JL)
34 NEXT JL
35 NEXT IL
41 DATA 9999,0,0,2,1,7,9,0,4,75,7,12,22,7,1,0,0,0,0,23,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
42 DATA 0,9999,0,0,0,0,4,16,0,8,0,0,16,0,0,0,0,6,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
43 DATA 0,0,9999,0,0,4,16,20,0,0,0,0,20,0,0,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
44 DATA 2,0,0,9999,29,5,18,47,23,2,4,0,48,0,4,0,0,0,0,25,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
45 DATA 1,0,0,29,9999,18,12,25,0,0,4,0,25,0,3,0,0,0,0,18,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0
46 DATA 7,0,4,5,18,9999,4,2,0,1,23,2,19,0,0,0,0,0,2,19,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
47 DATA 9,4,16,18,12,4,9999,0,14,72,7,8,39,8,40,8,0,8,4,7,0,0,0,0,0,0,0,28,8,0,0,0,0,0,0,0
48 DATA 0,16,20,47,25,2,0,9999,10,71,2,0,0,0,0,0,0,41,0,0,0,0,0,0,0,0,7,8,0,0,0,0,0,0,0,0
49 DATA 4,0,0,23,0,0,14,10,9999,14,0,0,18,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
50 DATA 75,8,0,2,0,1,72,71,14,9999,11,1,17,0,1,0,0,17,0,15,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
51 DATA 7,0,0,4,4,23,7,2,0,11,9999,316,33,8,2,0,0,0,8,34,0,0,6,0,0,0,10,0,0,6,0,0,0,0,0,0
52 DATA 12,0,0,0,0,2,8,0,0,1,316,9999,157,25,4,0,0,1,0,0,0,0,0,0,22,0,1,0,0,0,0,0,0,0,0,0
53 DATA 22,16,20,48,25,19,39,0,18,17,33,157,9999,11,6,0,0,6,0,5,8,3,10,0,0,0,9,11,2,0,0,1,0,0,0,0
54 DATA 7,0,0,0,0,0,8,0,0,0,8,25,11,9999,3,0,0,1,1,21,0,1,0,2,0,0,5,0,0,3,2,5,5,4,0,0
55 DATA 1,0,0,4,3,0,40,0,0,1,2,4,6,3,9999,19,0,2,2,12,0,0,0,0,0,0,0,7,3,0,0,0,0,0,0,0
56 DATA 0,0,0,0,0,0,8,0,0,0,0,0,0,0,19,9999,0,6,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
57 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,9999,40,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
58 DATA 0,6,0,0,0,0,8,41,0,17,0,1,6,1,2,6,40,9999,0,26,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
59 DATA 0,0,0,0,0,2,4,0,0,0,8,0,0,1,2,0,0,0,9999,13,9,0,7,0,0,0,0,27,16,3,0,20,0,4,0,0
60 DATA 23,4,4,25,18,19,7,0,0,15,34,0,5,21,12,1,0,26,13,9999,11,4,36,0,0,0,16,18,9,10,1,28,6,2,0,0
61 DATA 0,0,0,0,0,0,0,0,0,0,0,0,8,0,0,0,0,0,9,11,9999,36,6,0,8,0,2,0,0,0,0,0,0,0,0,0
62 DATA 0,0,0,0,3,0,0,0,0,0,0,0,3,1,0,0,0,0,0,4,36,9999,0,0,0,0,4,0,0,0,0,0,0,0,0,0
63 DATA 0,0,0,0,0,0,0,0,0,0,6,0,10,0,0,0,0,0,7,36,6,0,9999,0,0,12,9,0,0,0,0,0,0,0,0,0
64 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,9999,26,0,5,0,0,0,0,0,0,0,0,0
65 DATA 0,0,0,0,0,0,0,0,0,0,0,22,0,0,0,0,0,0,0,0,8,0,0,26,9999,35,2,0,0,0,0,0,0,0,0,0
66 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,12,0,35,9999,4,0,0,0,0,0,0,0,0,0
67 DATA 0,0,0,0,0,0,0,7,0,0,10,1,9,5,0,0,0,0,0,16,2,4,9,5,2,4,9999,0,0,0,0,0,0,0,0,0
68 DATA 0,0,0,0,0,0,28,8,0,0,0,0,11,0,7,0,0,0,27,18,0,0,0,0,0,0,0,9999,10,22,4,6,4,12,0,0
69 DATA 0,0,0,0,0,0,8,0,0,0,0,0,2,0,3,0,0,0,16,9,0,0,0,0,0,0,0,10,9999,19,12,0,0,0,0,0
70 DATA 0,0,0,0,0,0,0,0,0,0,6,0,0,3,0,0,0,0,3,10,0,0,0,0,0,0,0,22,19,9999,19,4,5,8,0,0
71 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,1,0,0,0,0,0,0,0,4,12,19,9999,0,3,13,0,0
72 DATA 0,0,0,0,0,0,0,0,0,0,0,0,1,5,0,0,0,0,20,28,0,0,0,0,0,0,0,6,0,4,0,9999,18,24,0,0
73 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,0,0,0,0,6,0,0,0,0,0,0,0,4,0,5,3,18,9999,20,0,0
74 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,4,0,0,0,0,4,2,0,0,0,0,0,0,0,12,0,8,13,24,20,9999,0,0
75 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,9999,0
76 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,9999
88 FOR JJJJ = -32000 TO 32000
89 RANDOMIZE JJJJ
90 M = -1D+37
91 FOR J44 = 1 TO 36
93 A(J44) = J44
94 NEXT J44
128 FOR I = 1 TO 1000
129 FOR KKQQ = 1 TO 36
130 X(KKQQ) = A(KKQQ)
131 NEXT KKQQ
133 III = 1 + FIX(RND * 36)
134 JJJ = 1 + FIX(RND * 36)
137 X(III) = A(JJJ)
139 X(JJJ) = A(III)
231 FOR J44 = 1 TO 36
233 FOR J45 = 1 TO 36
234 IF X(J44) = J45 THEN HHR(J44) = HR(J44) ELSE GOTO 238
237 Y(J45) = J44
238 NEXT J45
244 FOR RN = 1 TO 18
251 FOR ISE20 = (RN - 1) * 2 + 1 TO RN * 2
254 C(ISE20) = .5 * HHR(Y(ISE20))
258 FOR ISE2000 = ISE20 + 1 TO RN * 2
259 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))
263 NEXT ISE2000
269 NEXT ISE20
299 NEXT RN
499 NEXT J44
551 FOR RN = 1 TO 18
601 FOR J77 = (RN - 1) * 2 + 1 TO RN * 2
605 IF X(J77) > RN * 2 THEN 1670
609 NEXT J77
610 NEXT RN
811 PROD = 0
812 FOR J44 = 1 TO 36
813 FOR J45 = J44 + 1 TO 36
814 PROD = PROD - HS(Y(J44), Y(J45)) * ABS(C(J44) - C(J45))
815 NEXT J45
816 NEXT J44
822 P = PROD
1111 IF P <= M THEN 1670
1452 M = P
1453 FOR KLX = 1 TO 36
1454 CC(KLX) = C(KLX)
1455 A(KLX) = X(KLX)
1456 NEXT KLX
1657 GOTO 128
1670 NEXT I
1889 REM IF M < -999999 THEN 1999
1891 PRINT A(1), A(2), A(3), A(4), A(5)
1892 PRINT A(6), A(7), A(8), A(9), A(10)
1893 PRINT A(11), A(12), A(13), A(14), A(15)
1894 PRINT A(16), A(17), A(18), A(19), A(20)
1896 PRINT A(21), A(22), A(23), A(24), A(25)
1897 PRINT A(26), A(27), A(28), A(29), A(30)
1898 PRINT A(31), A(32), A(33), A(34), A(35), A(36), M, JJJJ
1999 NEXT JJJJ
1999 NEXT JJJJ
This computer program was run with qb64v1000-win [13]. The complete output through JJJJ=-31996 is shown below:
2 1 4 3 6
5 8 7 9 10
12 11 13 14 16
15 17 18 19 20
21 22 24 23 25
26 27 28 29 30
32 31 33 34 35
36 -5032 -32000
2 1 3 4 6
5 8 7 9 10
11 12 14 13 16
15 17 18 19 20
22 21 23 24 26
25 27 28 29 30
32 31 33 34 36
35 -4844 -31999
2 1 3 4 6
5 8 7 9 10
11 12 14 13 16
15 17 18 19 20
22 21 23 24 26
25 27 28 29 30
32 31 33 34 35
36 -4844 -31998
2 1 3 4 6
5 7 8 9 10
11 12 14 13 16
15 17 18 19 20
22 21 23 24 26
25 27 28 29 30
32 31 33 34 35
36 -4920 -31997
2 1 3 4 6
5 7 8 9 10
12 11 13 14 15
16 17 18 19 20
21 22 24 23 25
26 27 28 29 30
32 31 33 34 35
36 -5230 -31996
Above there is no rounding by hand; it is just straight copying by hand from the monitor screen.
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [13], the wall-clock time for obtaining the output through JJJJ=-31996 was 10 seconds.
Acknowledgment
I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
References
[1] Andre R. S. Amaral (2006), On the Exact Solution of a Facility Layout Problem. European Journal of Operational Research 173 (2006), pp. 508-518.
[2] Andre R. S. Amaral (2008), An Exact Approach to the One-Dimensional Facility Layout Problem. Operations Research, Vol. 56, No. 4 (July-August, 2008), pp. 1026-1033.
[3] Andre R. S. Amaral (2011), Optimal Solutions for the Double Row Layout Problem. Optimization Letters, DOI 10.1007/s11590-011-0426-8, published on line 30 November 2011, Springer-Verlag 2011.
[4] Andre R. S. Amaral (2012), The Corridor Allocation Problem. Computers and Operations Research 39 (2012), pp. 3325-3330.
[5] Andre R. S. Amaral (2013), A Parallel Ordering Problem in Facilities Layout. Computers and Operations Research, Vol. 40, Issue 12, December 2013, pp. 2930-2939.
[6] Miguel F. Anjos, Anthony Vannelli, Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes. INFORMS Journal on Computing, Vol. 20, No. 4, Fall 2008, pp. 611-617.
[7] Miguel F. Anjos (2012), FLPLIB–Facility Layout Database. Retrieved on September 25 2012 from http://www.gerad.ca/files/Sites/Anjos/indexFR.html
[8] Miguel F. Anjos, FLPLIB–Facility Layout Database. http://www.miguelanjos.com.
[9] S. S. Heragu, A. Kusiak. Efficient Models for the Facility Layout Problem. European Journal of Operational Research 53 (1), 1991, pp. 1-13.
[10] Philipp Hungerlaender, Miguel F. Anjos (January 2012), A Semidefinite Optimization Approach to Free-Space Multi-Row Facility Layout. Les Cahiers du GERAD. Retrieved from http://www.gerad.ca/fichiers/cahiers/G-2012-03.pdf
[11] 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.
[12] C. E. Nugent, T. E Vollmann, J. Ruml (1968), An Experimental Comparison of Techniques for the Assignment of Facilities to Locations. Operations Research, Vol. 16, pp. 150-173.
[13] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64
[14] Jsun Yui Wong (2012, September 17). A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Corridor Allocation Problem with Eleven Facilities, Third Edition. https://myblogsubstance.typepad.com/substance/2012/09/index.html/
[15] Ginger Yen (2008). Cutting-Plane Separation Strategies for Semidefinite Programming Models to Solve Single-Row Facility Layout Problems. A Master Thesis Presented to the University of Waterloo. UWSpace. http://hdl.handle.net/10012/4104.
Wednesday, May 10, 2017
Solving a k-Parallel Row Ordering Problem of 5 Rows and 36 Facilities
Jsun Yui Wong
Adapting to the computer program in Wong [14], the following computer program seeks to solve a k-parallel row ordering problem (k-PROP) of 36 facilities with the first four rows each having 7 facilities and the fifth row having 8 facilities. See Amaral [5]. The data for flows and lengths used here can be found in Yen [15, pages 101-105 for flows and page 106 for lengths].
0 REM DEFDBL A-Z
1 DEFINT I, J, K, X
2 DIM B(99), N(99), A(2002), H(99), L(99), U(99), X(2002), D(111), P(111), PS(39), J44(2002), J(99), AA(99), HR(39), HHR(39), Y(39), C(39), CC(39), RA(99)
3 DIM HS(49, 49)
4 DIM PE(49, 49)
5 DIM SD(49, 49)
9 HR(31) = 2: HR(32) = 2: HR(33) = 2: HR(34) = 1: HR(35) = 2: HR(36) = 2
17 HR(1) = 2: HR(2) = 1: HR(3) = 2: HR(4) = 1: HR(5) = 2: HR(6) = 3: HR(7) = 2: HR(8) = 2: HR(9) = 2
18 HR(10) = 2: HR(11) = 2: HR(12) = 2: HR(13) = 3: HR(14) = 2: HR(15) = 3: HR(16) = 3: HR(17) = 2: HR(18) = 2: HR(19) = 2: HR(20) = 2
29 HR(21) = 2: HR(22) = 2: HR(23) = 1
30 HR(24) = 3: HR(25) = 2: HR(26) = 2: HR(27) = 2: HR(28) = 1: HR(29) = 2: HR(30) = 2
31 FOR IL = 1 TO 36
32 FOR JL = 1 TO 36
33 READ HS(IL, JL)
34 NEXT JL
35 NEXT IL
41 DATA 9999,0,0,2,1,7,9,0,4,75,7,12,22,7,1,0,0,0,0,23,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
42 DATA 0,9999,0,0,0,0,4,16,0,8,0,0,16,0,0,0,0,6,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
43 DATA 0,0,9999,0,0,4,16,20,0,0,0,0,20,0,0,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
44 DATA 2,0,0,9999,29,5,18,47,23,2,4,0,48,0,4,0,0,0,0,25,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
45 DATA 1,0,0,29,9999,18,12,25,0,0,4,0,25,0,3,0,0,0,0,18,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0
46 DATA 7,0,4,5,18,9999,4,2,0,1,23,2,19,0,0,0,0,0,2,19,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
47 DATA 9,4,16,18,12,4,9999,0,14,72,7,8,39,8,40,8,0,8,4,7,0,0,0,0,0,0,0,28,8,0,0,0,0,0,0,0
48 DATA 0,16,20,47,25,2,0,9999,10,71,2,0,0,0,0,0,0,41,0,0,0,0,0,0,0,0,7,8,0,0,0,0,0,0,0,0
49 DATA 4,0,0,23,0,0,14,10,9999,14,0,0,18,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
50 DATA 75,8,0,2,0,1,72,71,14,9999,11,1,17,0,1,0,0,17,0,15,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
51 DATA 7,0,0,4,4,23,7,2,0,11,9999,316,33,8,2,0,0,0,8,34,0,0,6,0,0,0,10,0,0,6,0,0,0,0,0,0
52 DATA 12,0,0,0,0,2,8,0,0,1,316,9999,157,25,4,0,0,1,0,0,0,0,0,0,22,0,1,0,0,0,0,0,0,0,0,0
53 DATA 22,16,20,48,25,19,39,0,18,17,33,157,9999,11,6,0,0,6,0,5,8,3,10,0,0,0,9,11,2,0,0,1,0,0,0,0
54 DATA 7,0,0,0,0,0,8,0,0,0,8,25,11,9999,3,0,0,1,1,21,0,1,0,2,0,0,5,0,0,3,2,5,5,4,0,0
55 DATA 1,0,0,4,3,0,40,0,0,1,2,4,6,3,9999,19,0,2,2,12,0,0,0,0,0,0,0,7,3,0,0,0,0,0,0,0
56 DATA 0,0,0,0,0,0,8,0,0,0,0,0,0,0,19,9999,0,6,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
57 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,9999,40,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
58 DATA 0,6,0,0,0,0,8,41,0,17,0,1,6,1,2,6,40,9999,0,26,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
59 DATA 0,0,0,0,0,2,4,0,0,0,8,0,0,1,2,0,0,0,9999,13,9,0,7,0,0,0,0,27,16,3,0,20,0,4,0,0
60 DATA 23,4,4,25,18,19,7,0,0,15,34,0,5,21,12,1,0,26,13,9999,11,4,36,0,0,0,16,18,9,10,1,28,6,2,0,0
61 DATA 0,0,0,0,0,0,0,0,0,0,0,0,8,0,0,0,0,0,9,11,9999,36,6,0,8,0,2,0,0,0,0,0,0,0,0,0
62 DATA 0,0,0,0,3,0,0,0,0,0,0,0,3,1,0,0,0,0,0,4,36,9999,0,0,0,0,4,0,0,0,0,0,0,0,0,0
63 DATA 0,0,0,0,0,0,0,0,0,0,6,0,10,0,0,0,0,0,7,36,6,0,9999,0,0,12,9,0,0,0,0,0,0,0,0,0
64 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,9999,26,0,5,0,0,0,0,0,0,0,0,0
65 DATA 0,0,0,0,0,0,0,0,0,0,0,22,0,0,0,0,0,0,0,0,8,0,0,26,9999,35,2,0,0,0,0,0,0,0,0,0
66 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,12,0,35,9999,4,0,0,0,0,0,0,0,0,0
67 DATA 0,0,0,0,0,0,0,7,0,0,10,1,9,5,0,0,0,0,0,16,2,4,9,5,2,4,9999,0,0,0,0,0,0,0,0,0
68 DATA 0,0,0,0,0,0,28,8,0,0,0,0,11,0,7,0,0,0,27,18,0,0,0,0,0,0,0,9999,10,22,4,6,4,12,0,0
69 DATA 0,0,0,0,0,0,8,0,0,0,0,0,2,0,3,0,0,0,16,9,0,0,0,0,0,0,0,10,9999,19,12,0,0,0,0,0
70 DATA 0,0,0,0,0,0,0,0,0,0,6,0,0,3,0,0,0,0,3,10,0,0,0,0,0,0,0,22,19,9999,19,4,5,8,0,0
71 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,1,0,0,0,0,0,0,0,4,12,19,9999,0,3,13,0,0
72 DATA 0,0,0,0,0,0,0,0,0,0,0,0,1,5,0,0,0,0,20,28,0,0,0,0,0,0,0,6,0,4,0,9999,18,24,0,0
73 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,0,0,0,0,6,0,0,0,0,0,0,0,4,0,5,3,18,9999,20,0,0
74 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,4,0,0,0,0,4,2,0,0,0,0,0,0,0,12,0,8,13,24,20,9999,0,0
75 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,9999,0
76 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,9999
88 FOR JJJJ = -32000 TO 32000
89 RANDOMIZE JJJJ
90 M = -1D+37
91 FOR J44 = 1 TO 36
93 A(J44) = J44
94 NEXT J44
121 REM IF RND < 1 / 4 THEN IMAX = 17 ELSE IF RND < 1 / 3 THEN IMAX = 17 ELSE IF RND < 1 / 2 THEN IMAX = 17 ELSE IMAX = 17
128 FOR I = 1 TO 10000
129 FOR KKQQ = 1 TO 36
130 X(KKQQ) = A(KKQQ)
131 NEXT KKQQ
133 III = 1 + FIX(RND * 36)
134 JJJ = 1 + FIX(RND * 36)
137 X(III) = A(JJJ)
139 X(JJJ) = A(III)
231 FOR J44 = 1 TO 36
233 FOR J45 = 1 TO 36
234 IF X(J44) = J45 THEN HHR(J44) = HR(J44) ELSE GOTO 238
237 Y(J45) = J44
238 NEXT J45
253 FOR ISE20 = 1 TO 7
254 C(ISE20) = .5 * HHR(Y(ISE20))
258 FOR ISE2000 = ISE20 + 1 TO 7
259 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))
263 NEXT ISE2000
269 NEXT ISE20
386 FOR ISE20 = 8 TO 14
387 C(ISE20) = .5 * HHR(Y(ISE20))
308 FOR ISE2000 = ISE20 + 1 TO 14
389 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))
390 NEXT ISE2000
391 NEXT ISE20
396 FOR ISE20 = 15 TO 21
397 C(ISE20) = .5 * HHR(Y(ISE20))
398 FOR ISE2000 = ISE20 + 1 TO 21
399 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))
400 NEXT ISE2000
401 NEXT ISE20
403 FOR ISE20 = 22 TO 28
404 C(ISE20) = .5 * HHR(Y(ISE20))
405 FOR ISE2000 = ISE20 + 1 TO 28
406 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))
407 NEXT ISE2000
408 NEXT ISE20
413 FOR ISE20 = 29 TO 36
414 C(ISE20) = .5 * HHR(Y(ISE20))
415 FOR ISE2000 = ISE20 + 1 TO 36
416 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))
417 NEXT ISE2000
418 NEXT ISE20
499 NEXT J44
601 FOR J77 = 1 TO 7
605 IF X(J77) > 7 THEN 1670
609 NEXT J77
611 FOR J77 = 8 TO 14
615 IF X(J77) > 14 THEN 1670
619 NEXT J77
621 FOR J77 = 15 TO 21
622 IF X(J77) > 21 THEN 1670
629 NEXT J77
631 FOR J77 = 22 TO 28
635 IF X(J77) > 28 THEN 1670
639 NEXT J77
641 FOR J77 = 29 TO 36
645 IF X(J77) > 36 THEN 1670
649 NEXT J77
811 PROD = 0
812 FOR J44 = 1 TO 36
813 FOR J45 = J44 + 1 TO 36
814 PROD = PROD - HS(Y(J44), Y(J45)) * ABS(C(J44) - C(J45))
815 NEXT J45
816 NEXT J44
822 P = PROD
1111 IF P <= M THEN 1670
1452 M = P
1453 FOR KLX = 1 TO 36
1454 CC(KLX) = C(KLX)
1455 A(KLX) = X(KLX)
1456 NEXT KLX
1559 IIMAX = IMAX
1657 GOTO 128
1670 NEXT I
1889 IF M < -7270 THEN 1999
1891 PRINT A(1), A(2), A(3), A(4), A(5)
1892 PRINT A(6), A(7), A(8), A(9), A(10)
1893 PRINT A(11), A(12), A(13), A(14), A(15)
1894 PRINT A(16), A(17), A(18), A(19), A(20)
1896 PRINT A(21), A(22), A(23), A(24), A(25)
1897 PRINT A(26), A(27), A(28), A(29), A(30)
1898 PRINT A(31), A(32), A(33), A(34), A(35), A(36), M, JJJJ
1999 NEXT JJJJ
This computer program was run with qb64v1000-win [13]. The complete output through JJJJ=-31962 is shown below:
5 2 1 4 6
7 3 9 8 10
13 12 11 14 18
15 16 17 20 19
21 28 26 22 23
24 27 25 32 33
31 35 36 34 30
29 -7259.5 -31980
5 2 1 4 6
7 3 9 8 10
13 12 11 14 18
15 16 17 20 19
21 28 26 22 23
24 27 25 32 33
31 35 36 34 29
30 -7259.5 -31976
5 2 1 4 6
7 3 9 8 10
13 12 11 14 18
15 16 17 20 19
21 28 26 22 23
24 27 25 32 33
31 35 36 34 29
30 -7259.5 -31962
Above there is no rounding by hand; it is just straight copying by hand from the monitor screen.
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [13], the wall-clock time for obtaining the output through JJJJ=-31962 was two minutes and a half.
Acknowledgment
I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
References
[1] Andre R. S. Amaral (2006), On the Exact Solution of a Facility Layout Problem. European Journal of Operational Research 173 (2006), pp. 508-518.
[2] Andre R. S. Amaral (2008), An Exact Approach to the One-Dimensional Facility Layout Problem. Operations Research, Vol. 56, No. 4 (July-August, 2008), pp. 1026-1033.
[3] Andre R. S. Amaral (2011), Optimal Solutions for the Double Row Layout Problem. Optimization Letters, DOI 10.1007/s11590-011-0426-8, published on line 30 November 2011, Springer-Verlag 2011.
[4] Andre R. S. Amaral (2012), The Corridor Allocation Problem. Computers and Operations Research 39 (2012), pp. 3325-3330.
[5] Andre R. S. Amaral (2013), A Parallel Ordering Problem in Facilities Layout. Computers and Operations Research, Vol. 40, Issue 12, December 2013, pp. 2930-2939.
[6] Miguel F. Anjos, Anthony Vannelli, Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes. INFORMS Journal on Computing, Vol. 20, No. 4, Fall 2008, pp. 611-617.
[7] Miguel F. Anjos (2012), FLPLIB–Facility Layout Database. Retrieved on September 25 2012 from http://www.gerad.ca/files/Sites/Anjos/indexFR.html
[8] Miguel F. Anjos, FLPLIB–Facility Layout Database. http://www.miguelanjos.com.
[9] S. S. Heragu, A. Kusiak. Efficient Models for the Facility Layout Problem. European Journal of Operational Research 53 (1), 1991, pp. 1-13.
[10] Philipp Hungerlaender, Miguel F. Anjos (January 2012), A Semidefinite Optimization Approach to Free-Space Multi-Row Facility Layout. Les Cahiers du GERAD. Retrieved from http://www.gerad.ca/fichiers/cahiers/G-2012-03.pdf
[11] 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.
[12] C. E. Nugent, T. E Vollmann, J. Ruml (1968), An Experimental Comparison of Techniques for the Assignment of Facilities to Locations. Operations Research, Vol. 16, pp. 150-173.
[13] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64
[14] Jsun Yui Wong (2012, September 17). A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Corridor Allocation Problem with Eleven Facilities, Third Edition. https://myblogsubstance.typepad.com/substance/2012/09/index.html/
[15] Ginger Yen (2008). Cutting-Plane Separation Strategies for Semidefinite Programming Models to Solve Single-Row Facility Layout Problems. A Master Thesis Presented to the University of Waterloo.
Adapting to the computer program in Wong [14], the following computer program seeks to solve a k-parallel row ordering problem (k-PROP) of 36 facilities with the first four rows each having 7 facilities and the fifth row having 8 facilities. See Amaral [5]. The data for flows and lengths used here can be found in Yen [15, pages 101-105 for flows and page 106 for lengths].
0 REM DEFDBL A-Z
1 DEFINT I, J, K, X
2 DIM B(99), N(99), A(2002), H(99), L(99), U(99), X(2002), D(111), P(111), PS(39), J44(2002), J(99), AA(99), HR(39), HHR(39), Y(39), C(39), CC(39), RA(99)
3 DIM HS(49, 49)
4 DIM PE(49, 49)
5 DIM SD(49, 49)
9 HR(31) = 2: HR(32) = 2: HR(33) = 2: HR(34) = 1: HR(35) = 2: HR(36) = 2
17 HR(1) = 2: HR(2) = 1: HR(3) = 2: HR(4) = 1: HR(5) = 2: HR(6) = 3: HR(7) = 2: HR(8) = 2: HR(9) = 2
18 HR(10) = 2: HR(11) = 2: HR(12) = 2: HR(13) = 3: HR(14) = 2: HR(15) = 3: HR(16) = 3: HR(17) = 2: HR(18) = 2: HR(19) = 2: HR(20) = 2
29 HR(21) = 2: HR(22) = 2: HR(23) = 1
30 HR(24) = 3: HR(25) = 2: HR(26) = 2: HR(27) = 2: HR(28) = 1: HR(29) = 2: HR(30) = 2
31 FOR IL = 1 TO 36
32 FOR JL = 1 TO 36
33 READ HS(IL, JL)
34 NEXT JL
35 NEXT IL
41 DATA 9999,0,0,2,1,7,9,0,4,75,7,12,22,7,1,0,0,0,0,23,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
42 DATA 0,9999,0,0,0,0,4,16,0,8,0,0,16,0,0,0,0,6,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
43 DATA 0,0,9999,0,0,4,16,20,0,0,0,0,20,0,0,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
44 DATA 2,0,0,9999,29,5,18,47,23,2,4,0,48,0,4,0,0,0,0,25,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
45 DATA 1,0,0,29,9999,18,12,25,0,0,4,0,25,0,3,0,0,0,0,18,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0
46 DATA 7,0,4,5,18,9999,4,2,0,1,23,2,19,0,0,0,0,0,2,19,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
47 DATA 9,4,16,18,12,4,9999,0,14,72,7,8,39,8,40,8,0,8,4,7,0,0,0,0,0,0,0,28,8,0,0,0,0,0,0,0
48 DATA 0,16,20,47,25,2,0,9999,10,71,2,0,0,0,0,0,0,41,0,0,0,0,0,0,0,0,7,8,0,0,0,0,0,0,0,0
49 DATA 4,0,0,23,0,0,14,10,9999,14,0,0,18,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
50 DATA 75,8,0,2,0,1,72,71,14,9999,11,1,17,0,1,0,0,17,0,15,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
51 DATA 7,0,0,4,4,23,7,2,0,11,9999,316,33,8,2,0,0,0,8,34,0,0,6,0,0,0,10,0,0,6,0,0,0,0,0,0
52 DATA 12,0,0,0,0,2,8,0,0,1,316,9999,157,25,4,0,0,1,0,0,0,0,0,0,22,0,1,0,0,0,0,0,0,0,0,0
53 DATA 22,16,20,48,25,19,39,0,18,17,33,157,9999,11,6,0,0,6,0,5,8,3,10,0,0,0,9,11,2,0,0,1,0,0,0,0
54 DATA 7,0,0,0,0,0,8,0,0,0,8,25,11,9999,3,0,0,1,1,21,0,1,0,2,0,0,5,0,0,3,2,5,5,4,0,0
55 DATA 1,0,0,4,3,0,40,0,0,1,2,4,6,3,9999,19,0,2,2,12,0,0,0,0,0,0,0,7,3,0,0,0,0,0,0,0
56 DATA 0,0,0,0,0,0,8,0,0,0,0,0,0,0,19,9999,0,6,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
57 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,9999,40,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
58 DATA 0,6,0,0,0,0,8,41,0,17,0,1,6,1,2,6,40,9999,0,26,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
59 DATA 0,0,0,0,0,2,4,0,0,0,8,0,0,1,2,0,0,0,9999,13,9,0,7,0,0,0,0,27,16,3,0,20,0,4,0,0
60 DATA 23,4,4,25,18,19,7,0,0,15,34,0,5,21,12,1,0,26,13,9999,11,4,36,0,0,0,16,18,9,10,1,28,6,2,0,0
61 DATA 0,0,0,0,0,0,0,0,0,0,0,0,8,0,0,0,0,0,9,11,9999,36,6,0,8,0,2,0,0,0,0,0,0,0,0,0
62 DATA 0,0,0,0,3,0,0,0,0,0,0,0,3,1,0,0,0,0,0,4,36,9999,0,0,0,0,4,0,0,0,0,0,0,0,0,0
63 DATA 0,0,0,0,0,0,0,0,0,0,6,0,10,0,0,0,0,0,7,36,6,0,9999,0,0,12,9,0,0,0,0,0,0,0,0,0
64 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,9999,26,0,5,0,0,0,0,0,0,0,0,0
65 DATA 0,0,0,0,0,0,0,0,0,0,0,22,0,0,0,0,0,0,0,0,8,0,0,26,9999,35,2,0,0,0,0,0,0,0,0,0
66 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,12,0,35,9999,4,0,0,0,0,0,0,0,0,0
67 DATA 0,0,0,0,0,0,0,7,0,0,10,1,9,5,0,0,0,0,0,16,2,4,9,5,2,4,9999,0,0,0,0,0,0,0,0,0
68 DATA 0,0,0,0,0,0,28,8,0,0,0,0,11,0,7,0,0,0,27,18,0,0,0,0,0,0,0,9999,10,22,4,6,4,12,0,0
69 DATA 0,0,0,0,0,0,8,0,0,0,0,0,2,0,3,0,0,0,16,9,0,0,0,0,0,0,0,10,9999,19,12,0,0,0,0,0
70 DATA 0,0,0,0,0,0,0,0,0,0,6,0,0,3,0,0,0,0,3,10,0,0,0,0,0,0,0,22,19,9999,19,4,5,8,0,0
71 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,1,0,0,0,0,0,0,0,4,12,19,9999,0,3,13,0,0
72 DATA 0,0,0,0,0,0,0,0,0,0,0,0,1,5,0,0,0,0,20,28,0,0,0,0,0,0,0,6,0,4,0,9999,18,24,0,0
73 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,0,0,0,0,6,0,0,0,0,0,0,0,4,0,5,3,18,9999,20,0,0
74 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,4,0,0,0,0,4,2,0,0,0,0,0,0,0,12,0,8,13,24,20,9999,0,0
75 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,9999,0
76 DATA 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,9999
88 FOR JJJJ = -32000 TO 32000
89 RANDOMIZE JJJJ
90 M = -1D+37
91 FOR J44 = 1 TO 36
93 A(J44) = J44
94 NEXT J44
121 REM IF RND < 1 / 4 THEN IMAX = 17 ELSE IF RND < 1 / 3 THEN IMAX = 17 ELSE IF RND < 1 / 2 THEN IMAX = 17 ELSE IMAX = 17
128 FOR I = 1 TO 10000
129 FOR KKQQ = 1 TO 36
130 X(KKQQ) = A(KKQQ)
131 NEXT KKQQ
133 III = 1 + FIX(RND * 36)
134 JJJ = 1 + FIX(RND * 36)
137 X(III) = A(JJJ)
139 X(JJJ) = A(III)
231 FOR J44 = 1 TO 36
233 FOR J45 = 1 TO 36
234 IF X(J44) = J45 THEN HHR(J44) = HR(J44) ELSE GOTO 238
237 Y(J45) = J44
238 NEXT J45
253 FOR ISE20 = 1 TO 7
254 C(ISE20) = .5 * HHR(Y(ISE20))
258 FOR ISE2000 = ISE20 + 1 TO 7
259 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))
263 NEXT ISE2000
269 NEXT ISE20
386 FOR ISE20 = 8 TO 14
387 C(ISE20) = .5 * HHR(Y(ISE20))
308 FOR ISE2000 = ISE20 + 1 TO 14
389 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))
390 NEXT ISE2000
391 NEXT ISE20
396 FOR ISE20 = 15 TO 21
397 C(ISE20) = .5 * HHR(Y(ISE20))
398 FOR ISE2000 = ISE20 + 1 TO 21
399 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))
400 NEXT ISE2000
401 NEXT ISE20
403 FOR ISE20 = 22 TO 28
404 C(ISE20) = .5 * HHR(Y(ISE20))
405 FOR ISE2000 = ISE20 + 1 TO 28
406 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))
407 NEXT ISE2000
408 NEXT ISE20
413 FOR ISE20 = 29 TO 36
414 C(ISE20) = .5 * HHR(Y(ISE20))
415 FOR ISE2000 = ISE20 + 1 TO 36
416 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))
417 NEXT ISE2000
418 NEXT ISE20
499 NEXT J44
601 FOR J77 = 1 TO 7
605 IF X(J77) > 7 THEN 1670
609 NEXT J77
611 FOR J77 = 8 TO 14
615 IF X(J77) > 14 THEN 1670
619 NEXT J77
621 FOR J77 = 15 TO 21
622 IF X(J77) > 21 THEN 1670
629 NEXT J77
631 FOR J77 = 22 TO 28
635 IF X(J77) > 28 THEN 1670
639 NEXT J77
641 FOR J77 = 29 TO 36
645 IF X(J77) > 36 THEN 1670
649 NEXT J77
811 PROD = 0
812 FOR J44 = 1 TO 36
813 FOR J45 = J44 + 1 TO 36
814 PROD = PROD - HS(Y(J44), Y(J45)) * ABS(C(J44) - C(J45))
815 NEXT J45
816 NEXT J44
822 P = PROD
1111 IF P <= M THEN 1670
1452 M = P
1453 FOR KLX = 1 TO 36
1454 CC(KLX) = C(KLX)
1455 A(KLX) = X(KLX)
1456 NEXT KLX
1559 IIMAX = IMAX
1657 GOTO 128
1670 NEXT I
1889 IF M < -7270 THEN 1999
1891 PRINT A(1), A(2), A(3), A(4), A(5)
1892 PRINT A(6), A(7), A(8), A(9), A(10)
1893 PRINT A(11), A(12), A(13), A(14), A(15)
1894 PRINT A(16), A(17), A(18), A(19), A(20)
1896 PRINT A(21), A(22), A(23), A(24), A(25)
1897 PRINT A(26), A(27), A(28), A(29), A(30)
1898 PRINT A(31), A(32), A(33), A(34), A(35), A(36), M, JJJJ
1999 NEXT JJJJ
This computer program was run with qb64v1000-win [13]. The complete output through JJJJ=-31962 is shown below:
5 2 1 4 6
7 3 9 8 10
13 12 11 14 18
15 16 17 20 19
21 28 26 22 23
24 27 25 32 33
31 35 36 34 30
29 -7259.5 -31980
5 2 1 4 6
7 3 9 8 10
13 12 11 14 18
15 16 17 20 19
21 28 26 22 23
24 27 25 32 33
31 35 36 34 29
30 -7259.5 -31976
5 2 1 4 6
7 3 9 8 10
13 12 11 14 18
15 16 17 20 19
21 28 26 22 23
24 27 25 32 33
31 35 36 34 29
30 -7259.5 -31962
Above there is no rounding by hand; it is just straight copying by hand from the monitor screen.
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [13], the wall-clock time for obtaining the output through JJJJ=-31962 was two minutes and a half.
Acknowledgment
I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
References
[1] Andre R. S. Amaral (2006), On the Exact Solution of a Facility Layout Problem. European Journal of Operational Research 173 (2006), pp. 508-518.
[2] Andre R. S. Amaral (2008), An Exact Approach to the One-Dimensional Facility Layout Problem. Operations Research, Vol. 56, No. 4 (July-August, 2008), pp. 1026-1033.
[3] Andre R. S. Amaral (2011), Optimal Solutions for the Double Row Layout Problem. Optimization Letters, DOI 10.1007/s11590-011-0426-8, published on line 30 November 2011, Springer-Verlag 2011.
[4] Andre R. S. Amaral (2012), The Corridor Allocation Problem. Computers and Operations Research 39 (2012), pp. 3325-3330.
[5] Andre R. S. Amaral (2013), A Parallel Ordering Problem in Facilities Layout. Computers and Operations Research, Vol. 40, Issue 12, December 2013, pp. 2930-2939.
[6] Miguel F. Anjos, Anthony Vannelli, Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes. INFORMS Journal on Computing, Vol. 20, No. 4, Fall 2008, pp. 611-617.
[7] Miguel F. Anjos (2012), FLPLIB–Facility Layout Database. Retrieved on September 25 2012 from http://www.gerad.ca/files/Sites/Anjos/indexFR.html
[8] Miguel F. Anjos, FLPLIB–Facility Layout Database. http://www.miguelanjos.com.
[9] S. S. Heragu, A. Kusiak. Efficient Models for the Facility Layout Problem. European Journal of Operational Research 53 (1), 1991, pp. 1-13.
[10] Philipp Hungerlaender, Miguel F. Anjos (January 2012), A Semidefinite Optimization Approach to Free-Space Multi-Row Facility Layout. Les Cahiers du GERAD. Retrieved from http://www.gerad.ca/fichiers/cahiers/G-2012-03.pdf
[11] 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.
[12] C. E. Nugent, T. E Vollmann, J. Ruml (1968), An Experimental Comparison of Techniques for the Assignment of Facilities to Locations. Operations Research, Vol. 16, pp. 150-173.
[13] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64
[14] Jsun Yui Wong (2012, September 17). A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Corridor Allocation Problem with Eleven Facilities, Third Edition. https://myblogsubstance.typepad.com/substance/2012/09/index.html/
[15] Ginger Yen (2008). Cutting-Plane Separation Strategies for Semidefinite Programming Models to Solve Single-Row Facility Layout Problems. A Master Thesis Presented to the University of Waterloo.
Monday, May 8, 2017
Solving An Instance of a K=4 Parallel Ordering Problem of Layout of 23 Facilities
Jsun Yui Wong
Adapting to the computer program in Wong [12], the following computer program seeks to solve the parallel row ordering problem (PROP) of 23 facilities with the first three rows each with 6 facilities and the fourth row with 5 facilities; see Amaral [5]. The data can be found in Amaral [5] and Anjos [8].
0 REM DEFDBL A-Z
1 DEFINT I, J, K, X
2 DIM B(99), N(99), A(2002), H(99), L(99), U(99), X(2002), D(111), P(111), PS(33), J44(2002), J(99), AA(99), HR(32), HHR(32), Y(33), C(33), CC(33)
3 DIM HS(49, 49)
4 DIM PE(49, 49)
5 DIM SD(49, 49)
17 HR(1) = 5: HR(2) = 13: HR(3) = 9: HR(4) = 6: HR(5) = 5: HR(6) = 10: HR(7) = 5: HR(8) = 9: HR(9) = 9
18 HR(10) = 5: HR(11) = 8: HR(12) = 12: HR(13) = 8: HR(14) = 11: HR(15) = 11: HR(16) = 8: HR(17) = 10: HR(18) = 6: HR(19) = 8: HR(20) = 14
29 HR(21) = 12: HR(22) = 8: HR(23) = 11
31 FOR IL = 1 TO 23
32 FOR JL = 1 TO 23
33 READ HS(IL, JL)
34 NEXT JL
35 NEXT IL
42 DATA 9999,3,2,0,0,2,10,5,0,5,2,5,0,0,2,0,5,6,3,0,1,10,0
43 DATA 3,9999,4,0,10,4,0,0,2,2,1,0,5,0,0,0,0,2,0,1,6,1,0
44 DATA 2,4,9999,3,4,0,5,5,5,1,4,1,0,4,0,4,0,6,3,2,5,5,2
45 DATA 0,0,3,9999,0,0,0,2,2,0,6,0,2,5,2,5,1,1,1,1,2,2,4
46 DATA 0,10,4,0,9999,5,2,0,0,0,0,2,0,0,0,0,2,1,0,0,2,0,5
47 DATA 2,4,0,0,5,9999,1,2,2,1,4,10,10,2,5,5,0,5,0,0,0,10,0
48 DATA 10,0,5,0,2,1,9999,10,10,5,10,10,6,0,0,10,2,1,10,1,5,5,2
49 DATA 5,0,5,2,0,2,10,9999,1,3,5,0,0,0,2,4,5,2,10,6,0,5,5
50 DATA 0,2,5,2,0,2,10,1,9999,10,2,1,5,2,0,3,0,2,0,0,4,0,5
51 DATA 5,2,1,0,0,1,5,3,10,9999,5,5,6,0,1,5,5,0,5,2,3,5,0
52 DATA 2,1,4,6,0,4,10,5,2,5,9999,0,0,1,2,1,0,2,0,0,0,6,6
53 DATA 5,0,1,0,2,10,10,0,1,5,0,9999,5,5,2,0,0,0,0,2,0,4,5
54 DATA 0,5,0,2,0,10,6,0,5,6,0,5,9999,2,0,4,2,2,1,0,6,2,1
55 DATA 0,0,4,5,0,2,0,0,2,0,1,5,2,9999,2,1,0,5,3,10,0,0,4
56 DATA 2,0,0,2,0,5,0,2,0,1,2,2,0,2,9999,4,5,1,0,1,0,5,0
57 DATA 0,0,4,5,0,5,10,4,3,5,1,0,4,1,4,9999,0,3,0,2,2,0,2
58 DATA 5,0,0,1,2,0,2,5,0,5,0,0,2,0,5,0,9999,2,2,0,0,0,6
59 DATA 6,2,6,1,1,5,1,2,2,0,2,0,2,5,1,3,2,9999,5,1,2,10,10
60 DATA 3,0,3,1,0,0,10,10,0,5,0,0,1,3,0,0,2,5,9999,0,5,5,1
61 DATA 0,1,2,1,0,0,1,6,0,2,0,2,0,10,1,2,0,1,0,9999,5,2,1
62 DATA 1,6,5,2,2,0,5,0,4,3,0,0,6,0,0,2,0,2,5,5,9999,4,0
63 DATA 10,1,5,2,0,10,5,5,0,5,6,4,2,0,5,0,0,10,5,2,4,9999,5
64 DATA 0,0,2,4,5,0,2,5,5,0,6,5,1,4,0,2,6,10,1,1,0,5,9999
88 FOR JJJJ = -32000 TO 32000
89 RANDOMIZE JJJJ
90 M = -1D+37
91 FOR J44 = 1 TO 23
93 A(J44) = J44
94 NEXT J44
111 REM IF RND < 1 / 4 THEN IMAX = 4 ELSE IF RND < 1 / 3 THEN IMAX = 4 ELSE IF RND < 1 / 2 THEN IMAX = 4 ELSE IMAX = 4
128 FOR I = 1 TO 5000
129 FOR KKQQ = 1 TO 23
130 X(KKQQ) = A(KKQQ)
131 NEXT KKQQ
133 III = 1 + FIX(RND * 23)
134 JJJ = 1 + FIX(RND * 23)
137 X(III) = A(JJJ)
139 X(JJJ) = A(III)
231 FOR J44 = 1 TO 23
233 FOR J45 = 1 TO 23
234 IF X(J44) = J45 THEN HHR(J44) = HR(J44) ELSE GOTO 238
237 Y(J45) = J44
238 NEXT J45
253 FOR ISE20 = 1 TO 6
254 C(ISE20) = .5 * HHR(Y(ISE20))
258 FOR ISE2000 = ISE20 + 1 TO 6
259 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))
263 NEXT ISE2000
269 NEXT ISE20
386 FOR ISE20 = 7 TO 12
387 C(ISE20) = .5 * HHR(Y(ISE20))
308 FOR ISE2000 = ISE20 + 1 TO 12
389 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))
390 NEXT ISE2000
391 NEXT ISE20
396 FOR ISE20 = 13 TO 18
397 C(ISE20) = .5 * HHR(Y(ISE20))
398 FOR ISE2000 = ISE20 + 1 TO 18
399 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))
400 NEXT ISE2000
401 NEXT ISE20
403 FOR ISE20 = 19 TO 23
404 C(ISE20) = .5 * HHR(Y(ISE20))
405 FOR ISE2000 = ISE20 + 1 TO 23
406 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))
407 NEXT ISE2000
408 NEXT ISE20
409 NEXT J44
601 FOR J77 = 1 TO 6
605 IF X(J77) > 6 THEN 1670
609 NEXT J77
611 FOR J77 = 7 TO 12
615 IF X(J77) > 12 THEN 1670
619 NEXT J77
621 FOR J77 = 13 TO 18
622 IF X(J77) > 18 THEN 1670
629 NEXT J77
631 FOR J77 = 19 TO 23
635 IF X(J77) > 23 THEN 1670
639 NEXT J77
811 PROD = 0
812 FOR J44 = 1 TO 23
813 FOR J45 = J44 + 1 TO 23
814 PROD = PROD - HS(Y(J44), Y(J45)) * ABS(C(J44) - C(J45))
815 NEXT J45
816 NEXT J44
1082 P = PROD
1111 IF P <= M THEN 1670
1452 M = P
1453 FOR KLX = 1 TO 23
1454 CC(KLX) = C(KLX)
1455 A(KLX) = X(KLX)
1456 NEXT KLX
1559 IIMAX = IMAX
1657 GOTO 128
1670 NEXT I
1891 PRINT A(1), A(2), A(3), A(4), A(5)
1892 PRINT A(6), A(7), A(8), A(9), A(10)
1893 PRINT A(11), A(12), A(13), A(14), A(15)
1894 PRINT A(16), A(17), A(18), A(19), A(20), A(21), A(22), A(23)
1991 PRINT CC(1), CC(2), CC(3), CC(4), CC(5)
1992 PRINT CC(6), CC(7), CC(8), CC(9), CC(10)
1993 PRINT CC(11), CC(12), CC(13), CC(14), CC(15)
1994 PRINT CC(16), CC(17), CC(18), CC(19), CC(20), CC(21), CC(22), CC(23)
1995 PRINT M, JJJJ
1999 NEXT JJJJ
This computer program was run with qb64v1000-win [11]. The output through JJJJ=-31993 is summarized below:
.
.
.
-8537 -32000
.
.
.
-8537 -31999
.
.
.
-8591 -31998
.
.
.
-8431 -31997
.
.
.
-8591 -31996
.
.
.
-8537 -31995
.
.
.
-8673 -31994
3 6 2 1 5
4 9 8 11 10
7 12 17 18 14
16 13 15 20 23
22 21 19
45 37.5 30.5 23 15.5
6.5 44 35.5 28.5 23.5
16.5 6 49 38.5 30
23 15 5.5 47.5 38
30 20 7
-8203 -31993
Above there is no rounding by hand; it is just straight copying by hand from the monitor screen.
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [11], the wall-clock time for obtaining the output through JJJJ=-31993 was 15 seconds.
Acknowledgment
I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
References
[1] Andre R. S. Amaral (2006), On the Exact Solution of a Facility Layout Problem. European Journal of Operational Research 173 (2006), pp. 508-518.
[2] Andre R. S. Amaral (2008), An Exact Approach to the One-Dimensional Facility Layout Problem. Operations Research, Vol. 56, No. 4 (July-August, 2008), pp. 1026-1033.
[3] Andre R. S. Amaral (2011), Optimal Solutions for the Double Row Layout Problem. Optimization Letters, DOI 10.1007/s11590-011-0426-8, published on line 30 November 2011, Springer-Verlag 2011.
[4] Andre R. S. Amaral (2012), The Corridor Allocation Problem. Computers and Operations Research 39 (2012), pp. 3325-3330.
[5] Andre R. S. Amaral (2013), A Parallel Ordering Problem in Facilities Layout. Computers and Operations Research, Vol. 40, Issue 12, December 2013, pp. 2930-2939.
[6] Miguel F. Anjos, Anthony Vannelli, Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes. INFORMS Journal on Computing, Vol. 20, No. 4, Fall 2008, pp. 611-617.
[7] Miguel F. Anjos (2012), FLPLIB--Facility Layout Database. Retrieved on September 25 2012 from www.gerad.ca/files/Sites/Anjos/indexFR.html
[8] Miguel F. Anjos, FLPLIB--Facility Layout Database. www.miguelanjos.com.
[9] Philipp Hungerlaender, Miguel F. Anjos (January 2012), A Semidefinite Optimization Approach to Free-Space Multi-Row Facility Layout. Les Cahiers du GERAD. Retrieved from www.gerad.ca/fichiers/cahiers/G-2012-03.pdf
[10] 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.
[11] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64
[12] Jsun Yui Wong (2012, September 17). A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Corridor Allocation Problem with Eleven Facilities, Third Edition. https://myblogsubstance.typepad.com/substance/2012/09/index.html/
Adapting to the computer program in Wong [12], the following computer program seeks to solve the parallel row ordering problem (PROP) of 23 facilities with the first three rows each with 6 facilities and the fourth row with 5 facilities; see Amaral [5]. The data can be found in Amaral [5] and Anjos [8].
0 REM DEFDBL A-Z
1 DEFINT I, J, K, X
2 DIM B(99), N(99), A(2002), H(99), L(99), U(99), X(2002), D(111), P(111), PS(33), J44(2002), J(99), AA(99), HR(32), HHR(32), Y(33), C(33), CC(33)
3 DIM HS(49, 49)
4 DIM PE(49, 49)
5 DIM SD(49, 49)
17 HR(1) = 5: HR(2) = 13: HR(3) = 9: HR(4) = 6: HR(5) = 5: HR(6) = 10: HR(7) = 5: HR(8) = 9: HR(9) = 9
18 HR(10) = 5: HR(11) = 8: HR(12) = 12: HR(13) = 8: HR(14) = 11: HR(15) = 11: HR(16) = 8: HR(17) = 10: HR(18) = 6: HR(19) = 8: HR(20) = 14
29 HR(21) = 12: HR(22) = 8: HR(23) = 11
31 FOR IL = 1 TO 23
32 FOR JL = 1 TO 23
33 READ HS(IL, JL)
34 NEXT JL
35 NEXT IL
42 DATA 9999,3,2,0,0,2,10,5,0,5,2,5,0,0,2,0,5,6,3,0,1,10,0
43 DATA 3,9999,4,0,10,4,0,0,2,2,1,0,5,0,0,0,0,2,0,1,6,1,0
44 DATA 2,4,9999,3,4,0,5,5,5,1,4,1,0,4,0,4,0,6,3,2,5,5,2
45 DATA 0,0,3,9999,0,0,0,2,2,0,6,0,2,5,2,5,1,1,1,1,2,2,4
46 DATA 0,10,4,0,9999,5,2,0,0,0,0,2,0,0,0,0,2,1,0,0,2,0,5
47 DATA 2,4,0,0,5,9999,1,2,2,1,4,10,10,2,5,5,0,5,0,0,0,10,0
48 DATA 10,0,5,0,2,1,9999,10,10,5,10,10,6,0,0,10,2,1,10,1,5,5,2
49 DATA 5,0,5,2,0,2,10,9999,1,3,5,0,0,0,2,4,5,2,10,6,0,5,5
50 DATA 0,2,5,2,0,2,10,1,9999,10,2,1,5,2,0,3,0,2,0,0,4,0,5
51 DATA 5,2,1,0,0,1,5,3,10,9999,5,5,6,0,1,5,5,0,5,2,3,5,0
52 DATA 2,1,4,6,0,4,10,5,2,5,9999,0,0,1,2,1,0,2,0,0,0,6,6
53 DATA 5,0,1,0,2,10,10,0,1,5,0,9999,5,5,2,0,0,0,0,2,0,4,5
54 DATA 0,5,0,2,0,10,6,0,5,6,0,5,9999,2,0,4,2,2,1,0,6,2,1
55 DATA 0,0,4,5,0,2,0,0,2,0,1,5,2,9999,2,1,0,5,3,10,0,0,4
56 DATA 2,0,0,2,0,5,0,2,0,1,2,2,0,2,9999,4,5,1,0,1,0,5,0
57 DATA 0,0,4,5,0,5,10,4,3,5,1,0,4,1,4,9999,0,3,0,2,2,0,2
58 DATA 5,0,0,1,2,0,2,5,0,5,0,0,2,0,5,0,9999,2,2,0,0,0,6
59 DATA 6,2,6,1,1,5,1,2,2,0,2,0,2,5,1,3,2,9999,5,1,2,10,10
60 DATA 3,0,3,1,0,0,10,10,0,5,0,0,1,3,0,0,2,5,9999,0,5,5,1
61 DATA 0,1,2,1,0,0,1,6,0,2,0,2,0,10,1,2,0,1,0,9999,5,2,1
62 DATA 1,6,5,2,2,0,5,0,4,3,0,0,6,0,0,2,0,2,5,5,9999,4,0
63 DATA 10,1,5,2,0,10,5,5,0,5,6,4,2,0,5,0,0,10,5,2,4,9999,5
64 DATA 0,0,2,4,5,0,2,5,5,0,6,5,1,4,0,2,6,10,1,1,0,5,9999
88 FOR JJJJ = -32000 TO 32000
89 RANDOMIZE JJJJ
90 M = -1D+37
91 FOR J44 = 1 TO 23
93 A(J44) = J44
94 NEXT J44
111 REM IF RND < 1 / 4 THEN IMAX = 4 ELSE IF RND < 1 / 3 THEN IMAX = 4 ELSE IF RND < 1 / 2 THEN IMAX = 4 ELSE IMAX = 4
128 FOR I = 1 TO 5000
129 FOR KKQQ = 1 TO 23
130 X(KKQQ) = A(KKQQ)
131 NEXT KKQQ
133 III = 1 + FIX(RND * 23)
134 JJJ = 1 + FIX(RND * 23)
137 X(III) = A(JJJ)
139 X(JJJ) = A(III)
231 FOR J44 = 1 TO 23
233 FOR J45 = 1 TO 23
234 IF X(J44) = J45 THEN HHR(J44) = HR(J44) ELSE GOTO 238
237 Y(J45) = J44
238 NEXT J45
253 FOR ISE20 = 1 TO 6
254 C(ISE20) = .5 * HHR(Y(ISE20))
258 FOR ISE2000 = ISE20 + 1 TO 6
259 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))
263 NEXT ISE2000
269 NEXT ISE20
386 FOR ISE20 = 7 TO 12
387 C(ISE20) = .5 * HHR(Y(ISE20))
308 FOR ISE2000 = ISE20 + 1 TO 12
389 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))
390 NEXT ISE2000
391 NEXT ISE20
396 FOR ISE20 = 13 TO 18
397 C(ISE20) = .5 * HHR(Y(ISE20))
398 FOR ISE2000 = ISE20 + 1 TO 18
399 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))
400 NEXT ISE2000
401 NEXT ISE20
403 FOR ISE20 = 19 TO 23
404 C(ISE20) = .5 * HHR(Y(ISE20))
405 FOR ISE2000 = ISE20 + 1 TO 23
406 C(ISE20) = C(ISE20) + HHR(Y(ISE2000))
407 NEXT ISE2000
408 NEXT ISE20
409 NEXT J44
601 FOR J77 = 1 TO 6
605 IF X(J77) > 6 THEN 1670
609 NEXT J77
611 FOR J77 = 7 TO 12
615 IF X(J77) > 12 THEN 1670
619 NEXT J77
621 FOR J77 = 13 TO 18
622 IF X(J77) > 18 THEN 1670
629 NEXT J77
631 FOR J77 = 19 TO 23
635 IF X(J77) > 23 THEN 1670
639 NEXT J77
811 PROD = 0
812 FOR J44 = 1 TO 23
813 FOR J45 = J44 + 1 TO 23
814 PROD = PROD - HS(Y(J44), Y(J45)) * ABS(C(J44) - C(J45))
815 NEXT J45
816 NEXT J44
1082 P = PROD
1111 IF P <= M THEN 1670
1452 M = P
1453 FOR KLX = 1 TO 23
1454 CC(KLX) = C(KLX)
1455 A(KLX) = X(KLX)
1456 NEXT KLX
1559 IIMAX = IMAX
1657 GOTO 128
1670 NEXT I
1891 PRINT A(1), A(2), A(3), A(4), A(5)
1892 PRINT A(6), A(7), A(8), A(9), A(10)
1893 PRINT A(11), A(12), A(13), A(14), A(15)
1894 PRINT A(16), A(17), A(18), A(19), A(20), A(21), A(22), A(23)
1991 PRINT CC(1), CC(2), CC(3), CC(4), CC(5)
1992 PRINT CC(6), CC(7), CC(8), CC(9), CC(10)
1993 PRINT CC(11), CC(12), CC(13), CC(14), CC(15)
1994 PRINT CC(16), CC(17), CC(18), CC(19), CC(20), CC(21), CC(22), CC(23)
1995 PRINT M, JJJJ
1999 NEXT JJJJ
This computer program was run with qb64v1000-win [11]. The output through JJJJ=-31993 is summarized below:
.
.
.
-8537 -32000
.
.
.
-8537 -31999
.
.
.
-8591 -31998
.
.
.
-8431 -31997
.
.
.
-8591 -31996
.
.
.
-8537 -31995
.
.
.
-8673 -31994
3 6 2 1 5
4 9 8 11 10
7 12 17 18 14
16 13 15 20 23
22 21 19
45 37.5 30.5 23 15.5
6.5 44 35.5 28.5 23.5
16.5 6 49 38.5 30
23 15 5.5 47.5 38
30 20 7
-8203 -31993
Above there is no rounding by hand; it is just straight copying by hand from the monitor screen.
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [11], the wall-clock time for obtaining the output through JJJJ=-31993 was 15 seconds.
Acknowledgment
I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
References
[1] Andre R. S. Amaral (2006), On the Exact Solution of a Facility Layout Problem. European Journal of Operational Research 173 (2006), pp. 508-518.
[2] Andre R. S. Amaral (2008), An Exact Approach to the One-Dimensional Facility Layout Problem. Operations Research, Vol. 56, No. 4 (July-August, 2008), pp. 1026-1033.
[3] Andre R. S. Amaral (2011), Optimal Solutions for the Double Row Layout Problem. Optimization Letters, DOI 10.1007/s11590-011-0426-8, published on line 30 November 2011, Springer-Verlag 2011.
[4] Andre R. S. Amaral (2012), The Corridor Allocation Problem. Computers and Operations Research 39 (2012), pp. 3325-3330.
[5] Andre R. S. Amaral (2013), A Parallel Ordering Problem in Facilities Layout. Computers and Operations Research, Vol. 40, Issue 12, December 2013, pp. 2930-2939.
[6] Miguel F. Anjos, Anthony Vannelli, Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes. INFORMS Journal on Computing, Vol. 20, No. 4, Fall 2008, pp. 611-617.
[7] Miguel F. Anjos (2012), FLPLIB--Facility Layout Database. Retrieved on September 25 2012 from www.gerad.ca/files/Sites/Anjos/indexFR.html
[8] Miguel F. Anjos, FLPLIB--Facility Layout Database. www.miguelanjos.com.
[9] Philipp Hungerlaender, Miguel F. Anjos (January 2012), A Semidefinite Optimization Approach to Free-Space Multi-Row Facility Layout. Les Cahiers du GERAD. Retrieved from www.gerad.ca/fichiers/cahiers/G-2012-03.pdf
[10] 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.
[11] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64
[12] Jsun Yui Wong (2012, September 17). A General Nonlinear Integer/Discrete/Continuous Programming Solver Applied to the Corridor Allocation Problem with Eleven Facilities, Third Edition. https://myblogsubstance.typepad.com/substance/2012/09/index.html/
Subscribe to:
Posts (Atom)