An Application of a Computer Program for Integer Programming

Jsun Yui Wong

The computer program listed below seeks to solve the formulation on page 138 of Heragu (1997) without office 4 and office five and without making the assumption that the longer sides are horizontal. In order to have integer locations, the office lengths and widths used in the following computer program have been made twice as long as the given office lengths and widths, respectively.

0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(166),A(166),L(166),K(166),P(166),B(166),S(166)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 6
113 A(K)=FIX(RND*699)
115 NEXT K
121 FOR KF=7 TO 30
123 A(KF)=FIX(RND*2)
125 NEXT KF
126 IMAR=10+FIX(RND*500)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 30
131 X(KK)=A(KK)
132 NEXT KK
151 IF RND<.7 GOTO 222 ELSE IF RND<.5 GOTO 236 ELSE GOTO 241
222 IJL=1+FIX(RND*6)
233 IF RND<.95 THEN X(IJL)=FIX(RND*699) ELSE X(IJL)=A(IJL)-1
235 GOTO 1001
236 IJR=7+FIX(RND*24)
238 X(IJR)=FIX(RND*2)
239 GOTO 1001
241 IF RND<.5 THEN 243 ELSE 248
243 IJU=1+FIX(RND*6):IJV=1+FIX(RND*6)
244 X(IJU)=A(IJV):X(IJV)=A(IJU)
245 GOTO 1001
248 IJW=7+FIX(RND*24):IJX=7+FIX(RND*24)
249 X(IJW)=A(IJX):X(IJX)=A(IJW)
501 GOTO 1001
1001 S(1)=ABS(X(1)-X(2))-50+9999*X(7)
1002 S(2)=ABS(X(1)-X(2))-45+9999*X(8)
1003 S(3)=ABS(X(1)-X(2))-45+9999*X(9)
1004 S(4)=ABS(X(1)-X(2))-40+9999*X(10)
1005 S(5)=ABS(X(4)-X(5))-50+9999*X(11)
1006 S(6)=ABS(X(4)-X(5))-45+9999*X(12)
1007 S(7)=ABS(X(4)-X(5))-45+9999*X(13)
1008 S(8)=ABS(X(4)-X(5))-40+9999*X(14)
1009 S(9)=ABS(X(1)-X(3))-60+9999*X(15)
1010 S(10)=ABS(X(1)-X(3))-55+9999*X(16)
1011 S(11)=ABS(X(1)-X(3))-55+9999*X(17)
1012 S(12)=ABS(X(1)-X(3))-50+9999*X(18)
1013 S(13)=ABS(X(4)-X(6))-60+9999*X(19)
1014 S(14)=ABS(X(4)-X(6))-55+9999*X(20)
1015 S(15)=ABS(X(4)-X(6))-55+9999*X(21)
1016 S(16)=ABS(X(4)-X(6))-50+9999*X(22)
1017 S(17)=ABS(X(2)-X(3))-60+9999*X(23)
1018 S(18)=ABS(X(2)-X(3))-55+9999*X(24)
1019 S(19)=ABS(X(2)-X(3))-55+9999*X(25)
1020 S(20)=ABS(X(2)-X(3))-50+9999*X(26)
1021 S(21)=ABS(X(5)-X(6))-60+9999*X(27)
1022 S(22)=ABS(X(5)-X(6))-55+9999*X(28)
1023 S(23)=ABS(X(5)-X(6))-55+9999*X(29)
1024 S(24)=ABS(X(5)-X(6))-50+9999*X(30)
1049 SSS(1)=X(7)+X(8)+X(9)+X(10)+X(11)+X(12)+X(13)+X(14)-7
1050 SSS(2)=X(15)+X(16)+X(17)+X(18)+X(19)+X(20)+X(21)+X(22)-7
1055 SSS(3)=X(23)+X(24)+X(25)+X(26)+X(27)+X(28)+X(29)+X(30)-7
1107 FOR IJUL=1 TO 24
1111 IF S(IJUL)<0 THEN S(IJUL)=ABS(S(IJUL)) ELSE S(IJUL)=0
1115 NEXT IJUL
1121 IF SSS(1)=0 THEN SSS(1)=0 ELSE SSS(1)=ABS(SSS(1))
1122 IF SSS(2)=0 THEN SSS(2)=0 ELSE SSS(2)=ABS(SSS(2))
1123 IF SSS(3)=0 THEN SSS(3)=0 ELSE SSS(3)=ABS(SSS(3))
1285 PL11=-333333!*(S(1)+S(2)+S(3)+S(4)+S(5)+S(6)+S(7)+S(8)+S(9)+S(10)+S(11))
1286 PL12=-333333!*(S(12)+S(13)+S(14)+S(15)+S(16)+S(17)+S(18)+S(19)+S(20))
1287 PL13=-333333!*(S(21)+S(22)+S(23)+S(24))
1380 PH=-10*(ABS(X(1)-X(2))+ABS(X(4)-X(5)))-15*(ABS(X(1)-X(3))+ABS(X(4)-X(6)))-30*(ABS(X(2)-X(3))+ABS(X(5)-X(6)))
1587 PK=PH
1588 P=PK-333333!*(SSS(1))-333333!*(SSS(2))-333333!*(SSS(3))+PL11+PL12+PL13
1599 PR=PK
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 30
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-3270 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5),A(6)
1913 PRINT A(7),A(8),A(9),A(10)
1914 PRINT A(11),A(12),A(13),A(14)
1915 PRINT A(15),A(16),A(17),A(18)
1916 PRINT A(19),A(20),A(21),A(22)
1917 PRINT A(23),A(24),A(25),A(26)
1918 PRINT A(27),A(28),A(29),A(30)
1927 PRINT M,MM,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 3 minutes of running is presented below. (What immediately follows is a manual copy from the computer screen.)

379 429 379 323 273
273
1 1 0 1
1 1 1 1
1 1 1 1
1 1 1 0
1 1 1 0
1 1 1 1
-3250 -3250 -31978

285 285 235 370 330
330
1 1 1 1
1 1 1 0
1 1 1 0
1 1 1 1
1 1 1 0
1 1 1 1
-3250 -3250 -31798

346 296 296 113 163
113
1 1 1 0
1 1 1 1
1 1 1 0
1 1 1 1
1 1 1 1
1 1 1 0
-3250 -3250 -31784

433 383 383 130 180
130
1 1 1 1
1 0 1 1
1 1 1 0
1 1 1 1
1 1 1 1
1 1 1 0
-3250 -3250 -31766

318 368 368 443 493
443
1 1 0 1
1 1 1 1
1 1 1 0
1 1 1 1
1 1 1 1
1 1 1 0
-3250 -3250 -31758

544 494 494 87 135
85
1 1 0 1
1 1 1 1
1 1 1 0
1 1 1 1
1 1 1 1
1 1 1 0
-3250 -3250 -31718

551 501 551 270 220
220
0 1 1 1
1 1 1 1
1 1 1 1
1 1 1 0
1 1 1 0
1 1 1 1
-3250 -3250 -31640

338 388 388 465 415
465
0 1 1 1
1 1 1 1
1 1 1 0
1 1 1 1
1 1 1 1
1 1 1 0
-3250 -3250 -31577

250 200 200 159 109
159
1 0 1 1
1 1 1 1
1 1 1 0
1 1 1 1
1 1 1 1
1 1 1 0
-3250 -3250 -31544

140 140 140 174 134
84
1 1 1 1
1 1 1 0
1 1 1 1
1 0 1 1
1 1 1 1
1 1 1 0
-3250 -3250 -31543

The candidate solution above at JJJJ=-31543 is a usable layout of the three offices. Interpreted in accordance with line 1912 through line 1927, the output through JJJJ=-31543 was produced in the first 3 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

References

Heragu, S. S.: "Facilities Design," PWS Publishing Co., Boston, 1997.

Hillier, F. S., and G. J. Lieberman: "Introduction to Operations Research," Sixth Edition, pp. 498-499, McGraw-Hill, Inc., New York, 1995.

An Application of a Computer Program for Integer Programming

Jsun Yui Wong

The computer program listed below seeks to solve the formulation on page 138 of Heragu (1997). In order to have integer locations, the office lengths and widths used in the following computer program have been made twice as long as the given office lengths and widths, respectively.

0 DEFDBL A-Z
1 REM
3 DEFINT I,J,K
4 DIM X(166),A(166),L(166),K(166),P(166),B(166),S(166)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 10
113 A(K)=FIX(RND*699)
115 NEXT K
121 FOR KF=11 TO 20
123 A(KF)=FIX(RND*2)
125 NEXT KF
126 IMAR=10+FIX(RND*2000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 20
131 X(KK)=A(KK)
132 NEXT KK
151 IF RND<.7 GOTO 222 ELSE IF RND<.5 GOTO 236 ELSE GOTO 241
222 IJL=1+FIX(RND*10)
233 IF RND<.95 THEN X(IJL)=FIX(RND*699) ELSE X(IJL)=A(IJL)-1
235 GOTO 501
236 IJR=11+FIX(RND*10)
238 X(IJR)=FIX(RND*2)
239 GOTO 501
241 IF RND<.5 THEN 243 ELSE 248
243 IJU=1+FIX(RND*10):IJV=1+FIX(RND*10)
244 X(IJU)=A(IJV):X(IJV)=A(IJU)
245 GOTO 501
248 IJW=11+FIX(RND*10):IJX=11+FIX(RND*10)
249 X(IJW)=A(IJX):X(IJX)=A(IJW)
501 B(1)=ABS(X(1)-X(2))
502 B(2)=ABS(X(1)-X(3))
503 B(3)=ABS(X(1)-X(4))
504 B(4)=ABS(X(1)-X(5))
505 B(5)=ABS(X(2)-X(3))
506 B(6)=ABS(X(2)-X(4))
507 B(7)=ABS(X(2)-X(5))
508 B(8)=ABS(X(3)-X(4))
509 B(9)=ABS(X(3)-X(5))
510 B(10)=ABS(X(4)-X(5))
511 B(11)=ABS(X(6)-X(7))
512 B(12)=ABS(X(6)-X(8))
513 B(13)=ABS(X(6)-X(9))
514 B(14)=ABS(X(6)-X(10))
515 B(15)=ABS(X(7)-X(8))
516 B(16)=ABS(X(7)-X(9))
517 B(17)=ABS(X(7)-X(10))
518 B(18)=ABS(X(8)-X(9))
519 B(19)=ABS(X(8)-X(10))
520 B(20)=ABS(X(9)-X(10))
901 S(1)=B(1)-50+999*X(11)
902 S(2)=B(11)-40+999*(1-X(11))
903 S(3)=B(2)-60+999*X(12)
904 S(4)=B(12)-50+999*(1-X(12))
905 S(5)=B(3)-55+999*X(13)
906 S(6)=B(13)-40+999*(1-X(13))
907 S(7)=B(4)-60+999*X(14)
908 S(8)=B(14)-40+999*(1-X(14))
909 S(9)=B(5)-60+999*X(15)
910 S(10)=B(15)-50+999*(1-X(15))
911 S(11)=B(6)-55+999*X(16)
912 S(12)=B(16)-40+999*(1-X(16))
913 S(13)=B(7)-60+999*X(17)
914 S(14)=B(17)-40+999*(1-X(17))
915 S(15)=B(8)-65+999*X(18)
916 S(16)=B(18)-50+999*(1-X(18))
917 S(17)=B(9)-70+999*X(19)
918 S(18)=B(19)-50+999*(1-X(19))
919 S(19)=B(10)-65+999*X(20)
920 S(20)=B(20)-40+999*(1-X(20))
1107 FOR IJUL=1 TO 20
1111 IF S(IJUL)<0 THEN S(IJUL)=ABS(S(IJUL)) ELSE S(IJUL)=0
1115 NEXT IJUL
1285 PL11=-333333!*(S(1)+S(2)+S(3)+S(4)+S(5)+S(6)+S(7)+S(8)+S(9)+S(10)+S(11))
1286 PL12=-333333!*(S(12)+S(13)+S(14)+S(15)+S(16)+S(17)+S(18)+S(19)+S(20))
1380 PH=-10*(B(1)+B(11))-15*(B(2)+B(12))-20*(B(3)+B(13))
1381 PI=-30*(B(5)+B(15))-35*(B(6)+B(16))-10*(B(7)+B(17))
1384 PJ=-10*(B(8)+B(18))-20*(B(9)+B(19))-15*(B(10)+B(20))
1587 PK=PH+PI+PJ
1588 P=PK+PL11+PL12
1599 PR=PK
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 20
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1665 REM PRINT M,MM
1666 GOTO 128
1670 NEXT I
1890 IF M>-11111 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1914 PRINT A(11),A(12),A(13),A(14),A(15)
1915 PRINT A(16),A(17),A(18),A(19),A(20)
1917 PRINT M,MM,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the best candidate solutions produced in the first 5.2 hours of running are presented below. (What immediately follows is a manual copy from the computer screen.)

271 331 331 276 331
417 377 427 377 337
1 0 1 1 1
0 1 1 1 1
-11015 -11015 -14353

233 173 173 228 173
166 126 176 126 86
0 0 1 1 1
0 1 1 1 1
-11015 -11015 -10126

370 310 310 365 310
154 114 164 114 74
0 0 1 1 1
0 1 1 1 1
-11015 -11015 -9629

Interpreted in accordance with line 1912 through line 1917, the best candidate solutions through JJJJ=-9629 were produced in the first 5.2 hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

Reference

Heragu, S. S.: "Facilities Design," PWS Publishing Co., Boston, 1997.

Errata

Errata

Jsun Yui Wong

The following reference should have been cited in the nine preceding posts of the present blog.

Heragu, S. S., A. Kusiak. 1991. Efficient models for the facility layout problem. European Journal of Operational Research 53 1-13.

An Application of a Computer Program for Integer Programming, Second Edition

Jsun Yui Wong

The computer program listed below seeks to solve Problem P15 of Amaral (2006, p. 517), which is an instance of the allocation/ordering problem of Simmons (1969). In order to have integer locations, the department lengths used in the following computer program have been made twice as long as the given department lengths.

0 DEFDBL A-Z
1 REM
3 DEFINT I,J,K
4 DIM X(166),A(166),L(166),K(166),P(166),B(166),S(166)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 15
113 A(K)=FIX(RND*699)
115 NEXT K
126 IMAR=10+FIX(RND*20000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 15
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*15):IJM=1+FIX(RND*15):IJN=1+FIX(RND*15)
233 IF RND<.7 THEN X(IJL)=FIX(RND*699) ELSE IF RND<.05 THEN X(IJL)=A(IJL)-1 ELSE GOTO 244
235 GOTO 501
244 X(IJM)=A(IJN):X(IJN)=A(IJM)
501 B(1)=ABS(X(1)-X(2))
502 B(2)=ABS(X(1)-X(3))
503 B(3)=ABS(X(1)-X(4))
504 B(4)=ABS(X(1)-X(5))
505 B(5)=ABS(X(1)-X(6))
506 B(6)=ABS(X(1)-X(7))
507 B(7)=ABS(X(1)-X(8))
508 B(8)=ABS(X(1)-X(9))
509 B(9)=ABS(X(1)-X(10))
510 B(10)=ABS(X(1)-X(11))
511 B(11)=ABS(X(1)-X(12))
512 B(12)=ABS(X(1)-X(13))
513 B(13)=ABS(X(1)-X(14))
514 B(14)=ABS(X(1)-X(15))
515 B(15)=ABS(X(2)-X(3))
516 B(16)=ABS(X(2)-X(4))
517 B(17)=ABS(X(2)-X(5))
518 B(18)=ABS(X(2)-X(6))
519 B(19)=ABS(X(2)-X(7))
520 B(20)=ABS(X(2)-X(8))
521 B(21)=ABS(X(2)-X(9))
522 B(22)=ABS(X(2)-X(10))
523 B(23)=ABS(X(2)-X(11))
524 B(24)=ABS(X(2)-X(12))
525 B(25)=ABS(X(2)-X(13))
526 B(26)=ABS(X(2)-X(14))
527 B(27)=ABS(X(2)-X(15))
528 B(28)=ABS(X(3)-X(4))
529 B(29)=ABS(X(3)-X(5))
530 B(30)=ABS(X(3)-X(6))
531 B(31)=ABS(X(3)-X(7))
532 B(32)=ABS(X(3)-X(8))
533 B(33)=ABS(X(3)-X(9))
534 B(34)=ABS(X(3)-X(10))
535 B(35)=ABS(X(3)-X(11))
536 B(36)=ABS(X(3)-X(12))
537 B(37)=ABS(X(3)-X(13))
538 B(38)=ABS(X(3)-X(14))
539 B(39)=ABS(X(3)-X(15))
540 B(40)=ABS(X(4)-X(5))
541 B(41)=ABS(X(4)-X(6))
542 B(42)=ABS(X(4)-X(7))
543 B(43)=ABS(X(4)-X(8))
544 B(44)=ABS(X(4)-X(9))
545 B(45)=ABS(X(4)-X(10))
546 B(46)=ABS(X(4)-X(11))
547 B(47)=ABS(X(4)-X(12))
548 B(48)=ABS(X(4)-X(13))
549 B(49)=ABS(X(4)-X(14))
550 B(50)=ABS(X(4)-X(15))
551 B(51)=ABS(X(5)-X(6))
552 B(52)=ABS(X(5)-X(7))
553 B(53)=ABS(X(5)-X(8))
554 B(54)=ABS(X(5)-X(9))
555 B(55)=ABS(X(5)-X(10))
556 B(56)=ABS(X(5)-X(11))
557 B(57)=ABS(X(5)-X(12))
558 B(58)=ABS(X(5)-X(13))
559 B(59)=ABS(X(5)-X(14))
560 B(60)=ABS(X(5)-X(15))
561 B(61)=ABS(X(6)-X(7))
562 B(62)=ABS(X(6)-X(8))
563 B(63)=ABS(X(6)-X(9))
564 B(64)=ABS(X(6)-X(10))
565 B(65)=ABS(X(6)-X(11))
566 B(66)=ABS(X(6)-X(12))
567 B(67)=ABS(X(6)-X(13))
568 B(68)=ABS(X(6)-X(14))
569 B(69)=ABS(X(6)-X(15))
570 B(70)=ABS(X(7)-X(8))
571 B(71)=ABS(X(7)-X(9))
572 B(72)=ABS(X(7)-X(10))
573 B(73)=ABS(X(7)-X(11))
574 B(74)=ABS(X(7)-X(12))
575 B(75)=ABS(X(7)-X(13))
576 B(76)=ABS(X(7)-X(14))
577 B(77)=ABS(X(7)-X(15))
578 B(78)=ABS(X(8)-X(9))
579 B(79)=ABS(X(8)-X(10))
580 B(80)=ABS(X(8)-X(11))
581 B(81)=ABS(X(8)-X(12))
582 B(82)=ABS(X(8)-X(13))
583 B(83)=ABS(X(8)-X(14))
584 B(84)=ABS(X(8)-X(15))
585 B(85)=ABS(X(9)-X(10))
586 B(86)=ABS(X(9)-X(11))
587 B(87)=ABS(X(9)-X(12))
588 B(88)=ABS(X(9)-X(13))
589 B(89)=ABS(X(9)-X(14))
590 B(90)=ABS(X(9)-X(15))
591 B(91)=ABS(X(10)-X(11))
592 B(92)=ABS(X(10)-X(12))
593 B(93)=ABS(X(10)-X(13))
594 B(94)=ABS(X(10)-X(14))
595 B(95)=ABS(X(10)-X(15))
596 B(96)=ABS(X(11)-X(12))
597 B(97)=ABS(X(11)-X(13))
598 B(98)=ABS(X(11)-X(14))
599 B(99)=ABS(X(11)-X(15))
600 B(100)=ABS(X(12)-X(13))
601 B(101)=ABS(X(12)-X(14))
602 B(102)=ABS(X(12)-X(15))
603 B(103)=ABS(X(13)-X(14))
604 B(104)=ABS(X(13)-X(15))
605 B(105)=ABS(X(14)-X(15))
901 S(1)=B(1)-23
902 S(2)=B(2)-29
903 S(3)=B(3)-23
904 S(4)=B(4)-27
905 S(5)=B(5)-23
906 S(6)=B(6)-27
907 S(7)=B(7)-25
908 S(8)=B(8)-29
909 S(9)=B(9)-26
910 S(10)=B(10)-25
911 S(11)=B(11)-23
912 S(12)=B(12)-29
913 S(13)=B(13)-23
914 S(14)=B(14)-27
915 S(15)=B(15)-12
916 S(16)=B(16)-6
917 S(17)=B(17)-10
918 S(18)=B(18)-6
919 S(19)=B(19)-10
920 S(20)=B(20)-8
921 S(21)=B(21)-12
922 S(22)=B(22)-9
923 S(23)=B(23)-8
924 S(24)=B(24)-6
925 S(25)=B(25)-12
926 S(26)=B(26)-6
927 S(27)=B(27)-10
928 S(28)=B(28)-12
929 S(29)=B(29)-16
930 S(30)=B(30)-12
931 S(31)=B(31)-16
932 S(32)=B(32)-14
933 S(33)=B(33)-18
934 S(34)=B(34)-15
935 S(35)=B(35)-14
936 S(36)=B(36)-12
937 S(37)=B(37)-18
938 S(38)=B(38)-12
939 S(39)=B(39)-16
940 S(40)=B(40)-10
941 S(41)=B(41)-6
942 S(42)=B(42)-10
943 S(43)=B(43)-8
944 S(44)=B(44)-12
945 S(45)=B(45)-9
946 S(46)=B(46)-8
947 S(47)=B(47)-6
948 S(48)=B(48)-12
949 S(49)=B(49)-6
950 S(50)=B(50)-10
951 S(51)=B(51)-10
952 S(52)=B(52)-14
953 S(53)=B(53)-12
954 S(54)=B(54)-16
955 S(55)=B(55)-13
956 S(56)=B(56)-12
957 S(57)=B(57)-10
958 S(58)=B(58)-16
959 S(59)=B(59)-10
960 S(60)=B(60)-14
961 S(61)=B(61)-10
962 S(62)=B(62)-8
963 S(63)=B(63)-12
964 S(64)=B(64)-9
965 S(65)=B(65)-8
966 S(66)=B(66)-6
967 S(67)=B(67)-12
968 S(68)=B(68)-6
969 S(69)=B(69)-10
970 S(70)=B(70)-12
971 S(71)=B(71)-16
972 S(72)=B(72)-13
973 S(73)=B(73)-12
974 S(74)=B(74)-10
975 S(75)=B(75)-16
976 S(76)=B(76)-10
977 S(77)=B(77)-14
978 S(78)=B(78)-14
979 S(79)=B(79)-11
980 S(80)=B(80)-10
981 S(81)=B(81)-8
982 S(82)=B(82)-14
983 S(83)=B(83)-8
984 S(84)=B(84)-12
985 S(85)=B(85)-15
986 S(86)=B(86)-14
987 S(87)=B(87)-12
988 S(88)=B(88)-18
989 S(89)=B(89)-12
990 S(90)=B(90)-16
991 S(91)=B(91)-11
992 S(92)=B(92)-9
993 S(93)=B(93)-15
994 S(94)=B(94)-9
995 S(95)=B(95)-13
996 S(96)=B(96)-8
997 S(97)=B(97)-14
998 S(98)=B(98)-8
999 S(99)=B(99)-12
1000 S(100)=B(100)-12
1001 S(101)=B(101)-6
1002 S(102)=B(102)-10
1003 S(103)=B(103)-12
1004 S(104)=B(104)-16
1005 S(105)=B(105)-10
1107 FOR IJUL=1 TO 105
1111 IF S(IJUL)<0 THEN S(IJUL)=ABS(S(IJUL)) ELSE S(IJUL)=0
1115 NEXT IJUL
1380 PH=-10*B(1)-0*B(2)-5*B(3)-1*B(4)-0*B(5)-1*B(6)-2*B(7)-2*B(8)-2*B(9)
1381 PI=-2*B(10)-0*B(11)-4*B(12)-0*B(13)-0*B(14)-1*B(15)-3*B(16)-2*B(17)-2*B(18)
1384 PJ=-2*B(19)-3*B(20)-2*B(21)-0*B(22)-2*B(23)-0*B(24)-10*B(25)-5*B(26)-0*B(27)-10*B(28)
1385 PG=-2*B(29)-0*B(30)-2*B(31)-5*B(32)-4*B(33)-5*B(34)-2*B(35)-2*B(36)
1387 PF=-5*B(37)-5*B(38)-5*B(39)-1*B(40)-1*B(41)-5*B(42)-0*B(43)-0*B(44)-2*B(45)
1389 PE=-1*B(46)-0*B(47)-2*B(48)-5*B(49)-0*B(50)-3*B(51)-5*B(52)-5*B(53)-5*B(54)-1*B(55)
1391 PU=-0*B(56)-3*B(57)-0*B(58)-5*B(59)-5*B(60)-2*B(61)-2*B(62)-1*B(63)-5*B(64)-0*B(65)
1392 PV=-0*B(66)-2*B(67)-5*B(68)-10*B(69)-6*B(70)-0*B(71)-1*B(72)-5*B(73)-5*B(74)-5*B(75)
1393 PW=-1*B(76)-0*B(77)-5*B(78)-2*B(79)-10*B(80)-0*B(81)-5*B(82)-0*B(83)-0*B(84)-0*B(85)
1394 PX=-10*B(86)-5*B(87)-10*B(88)-0*B(89)-2*B(90)-0*B(91)-4*B(92)-0*B(93)-0*B(94)-5*B(95)
1395 PY=-5*B(96)-0*B(97)-5*B(98)-0*B(99)-3*B(100)-3*B(101)-0*B(102)-10*B(103)-2*B(104)-4*B(105)
1485 PL1=-333333!*(S(1)+S(2)+S(3)+S(4)+S(5)+S(6)+S(7)+S(8)+S(9)+S(10)+S(11)+S(12)+S(13)+S(14)+S(15)+S(16)+S(17)+S(18)+S(19)+S(20)+S(21)+S(22)+S(23)+S(24)+S(25)+S(26)+S(27)+S(28))
1486 PL2=-333333!*(S(29)+S(30)+S(31)+S(32)+S(33)+S(34)+S(35)+S(36))
1490 PL3=-333333!*(S(37)+S(38)+S(39)+S(40)+S(41)+S(42)+S(43)+S(44)+S(45))
1491 PL4=-333333!*(S(46)+S(47)+S(48)+S(49)+S(50)+S(51)+S(52)+S(53)+S(54)+S(55))
1493 PL5=-333333!*(S(56)+S(57)+S(58)+S(59)+S(60)+S(61)+S(62)+S(63)+S(64)+S(65)+S(66)+S(67)+S(68)+S(69)+S(70)+S(71)+S(72)+S(73)+S(74))
1494 PL6=-333333!*(S(75)+S(76)+S(77)+S(78)+S(79)+S(80)+S(81)+S(82)+S(83)+S(84)+S(85)+S(86)+S(87)+S(88)+S(89)+S(90)+S(91)+S(92)+S(93))
1495 PL7=-333333!*(S(94)+S(95)+S(96)+S(97)+S(98)+S(99)+S(100)+S(101)+S(102)+S(103)+S(104)+S(105))
1587 PK=PH+PI+PJ+PG+PF+PE+PU+PV+PW+PX+PY
1588 P=PK+PL1+PL2+PL3+PL4+PL5+PL6+PL7
1599 PR=PK
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 15
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-12700 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1914 PRINT A(11),A(12),A(13),A(14),A(15)
1915 PRINT M,MM,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 29 hours of running is presented below. (What immediately follows is a manual copy from the computer screen.)

278 301 401 389 417
427 367 355 331 450
345 377 313 383 437
-12610 -12610 -31135

343 320 206 218 228
194 248 266 290 171
276 258 308 238 184
-12676 -12676 -30879

142 204 266 254 282
292 232 196 172 301
186 242 216 248 314
-12667 -12667 -29661

420 397 297 309 281
271 325 343 367 248
353 335 385 315 261
-12614 -12614 -29334

241 300 364 352 380
390 330 318 270 413
308 340 288 346 400
-12610 -12610 -28901

Interpreted in accordance with line 1912, line 1913, line 1914, and line 1915, the output through JJJJ=-28901 was produced in the first 29 hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

References

Amaral, A.R.S., 2006. On the exact solution of a facility layout problem. European Journal of Operational Research 173, 508-518.

Simmons, D.M., 1969. One-dimensional space allocation: An ordering algorithm. Operations Research 17, 812-826.

An Application of a Computer Program for Integer Programming

Jsun Yui Wong

The computer program listed below seeks to solve Problem P15 of Amaral (2006, p. 517), which is a problem from Simmons (1969). In order to have integer locations, the department lengths used in the following computer program have been made twice as long as the given department lengths.

0 DEFDBL A-Z
1 REM
3 DEFINT I,J,K
4 DIM X(166),A(166),L(166),K(166),P(166),B(166),S(166)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 15
113 A(K)=FIX(RND*699)
115 NEXT K
126 IMAR=10+FIX(RND*20000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 15
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*15):IJM=1+FIX(RND*15):IJN=1+FIX(RND*15)
233 IF RND<.7 THEN X(IJL)=FIX(RND*699) ELSE IF RND<.05 THEN X(IJL)=A(IJL)-1 ELSE GOTO 244
235 GOTO 501
244 X(IJM)=A(IJN):X(IJN)=A(IJM)
501 B(1)=ABS(X(1)-X(2))
502 B(2)=ABS(X(1)-X(3))
503 B(3)=ABS(X(1)-X(4))
504 B(4)=ABS(X(1)-X(5))
505 B(5)=ABS(X(1)-X(6))
506 B(6)=ABS(X(1)-X(7))
507 B(7)=ABS(X(1)-X(8))
508 B(8)=ABS(X(1)-X(9))
509 B(9)=ABS(X(1)-X(10))
510 B(10)=ABS(X(1)-X(11))
511 B(11)=ABS(X(1)-X(12))
512 B(12)=ABS(X(1)-X(13))
513 B(13)=ABS(X(1)-X(14))
514 B(14)=ABS(X(1)-X(15))
515 B(15)=ABS(X(2)-X(3))
516 B(16)=ABS(X(2)-X(4))
517 B(17)=ABS(X(2)-X(5))
518 B(18)=ABS(X(2)-X(6))
519 B(19)=ABS(X(2)-X(7))
520 B(20)=ABS(X(2)-X(8))
521 B(21)=ABS(X(2)-X(9))
522 B(22)=ABS(X(2)-X(10))
523 B(23)=ABS(X(2)-X(11))
524 B(24)=ABS(X(2)-X(12))
525 B(25)=ABS(X(2)-X(13))
526 B(26)=ABS(X(2)-X(14))
527 B(27)=ABS(X(2)-X(15))
528 B(28)=ABS(X(3)-X(4))
529 B(29)=ABS(X(3)-X(5))
530 B(30)=ABS(X(3)-X(6))
531 B(31)=ABS(X(3)-X(7))
532 B(32)=ABS(X(3)-X(8))
533 B(33)=ABS(X(3)-X(9))
534 B(34)=ABS(X(3)-X(10))
535 B(35)=ABS(X(3)-X(11))
536 B(36)=ABS(X(3)-X(12))
537 B(37)=ABS(X(3)-X(13))
538 B(38)=ABS(X(3)-X(14))
539 B(39)=ABS(X(3)-X(15))
540 B(40)=ABS(X(4)-X(5))
541 B(41)=ABS(X(4)-X(6))
542 B(42)=ABS(X(4)-X(7))
543 B(43)=ABS(X(4)-X(8))
544 B(44)=ABS(X(4)-X(9))
545 B(45)=ABS(X(4)-X(10))
546 B(46)=ABS(X(4)-X(11))
547 B(47)=ABS(X(4)-X(12))
548 B(48)=ABS(X(4)-X(13))
549 B(49)=ABS(X(4)-X(14))
550 B(50)=ABS(X(4)-X(15))
551 B(51)=ABS(X(5)-X(6))
552 B(52)=ABS(X(5)-X(7))
553 B(53)=ABS(X(5)-X(8))
554 B(54)=ABS(X(5)-X(9))
555 B(55)=ABS(X(5)-X(10))
556 B(56)=ABS(X(5)-X(11))
557 B(57)=ABS(X(5)-X(12))
558 B(58)=ABS(X(5)-X(13))
559 B(59)=ABS(X(5)-X(14))
560 B(60)=ABS(X(5)-X(15))
561 B(61)=ABS(X(6)-X(7))
562 B(62)=ABS(X(6)-X(8))
563 B(63)=ABS(X(6)-X(9))
564 B(64)=ABS(X(6)-X(10))
565 B(65)=ABS(X(6)-X(11))
566 B(66)=ABS(X(6)-X(12))
567 B(67)=ABS(X(6)-X(13))
568 B(68)=ABS(X(6)-X(14))
569 B(69)=ABS(X(6)-X(15))
570 B(70)=ABS(X(7)-X(8))
571 B(71)=ABS(X(7)-X(9))
572 B(72)=ABS(X(7)-X(10))
573 B(73)=ABS(X(7)-X(11))
574 B(74)=ABS(X(7)-X(12))
575 B(75)=ABS(X(7)-X(13))
576 B(76)=ABS(X(7)-X(14))
577 B(77)=ABS(X(7)-X(15))
578 B(78)=ABS(X(8)-X(9))
579 B(79)=ABS(X(8)-X(10))
580 B(80)=ABS(X(8)-X(11))
581 B(81)=ABS(X(8)-X(12))
582 B(82)=ABS(X(8)-X(13))
583 B(83)=ABS(X(8)-X(14))
584 B(84)=ABS(X(8)-X(15))
585 B(85)=ABS(X(9)-X(10))
586 B(86)=ABS(X(9)-X(11))
587 B(87)=ABS(X(9)-X(12))
588 B(88)=ABS(X(9)-X(13))
589 B(89)=ABS(X(9)-X(14))
590 B(90)=ABS(X(9)-X(15))
591 B(91)=ABS(X(10)-X(11))
592 B(92)=ABS(X(10)-X(12))
593 B(93)=ABS(X(10)-X(13))
594 B(94)=ABS(X(10)-X(14))
595 B(95)=ABS(X(10)-X(15))
596 B(96)=ABS(X(11)-X(12))
597 B(97)=ABS(X(11)-X(13))
598 B(98)=ABS(X(11)-X(14))
599 B(99)=ABS(X(11)-X(15))
600 B(100)=ABS(X(12)-X(13))
601 B(101)=ABS(X(12)-X(14))
602 B(102)=ABS(X(12)-X(15))
603 B(103)=ABS(X(13)-X(14))
604 B(104)=ABS(X(13)-X(15))
605 B(105)=ABS(X(14)-X(15))
901 S(1)=B(1)-23
902 S(2)=B(2)-29
903 S(3)=B(3)-23
904 S(4)=B(4)-27
905 S(5)=B(5)-23
906 S(6)=B(6)-27
907 S(7)=B(7)-25
908 S(8)=B(8)-29
909 S(9)=B(9)-26
910 S(10)=B(10)-25
911 S(11)=B(11)-23
912 S(12)=B(12)-29
913 S(13)=B(13)-23
914 S(14)=B(14)-27
915 S(15)=B(15)-12
916 S(16)=B(16)-6
917 S(17)=B(17)-10
918 S(18)=B(18)-6
919 S(19)=B(19)-10
920 S(20)=B(20)-8
921 S(21)=B(21)-12
922 S(22)=B(22)-9
923 S(23)=B(23)-8
924 S(24)=B(24)-6
925 S(25)=B(25)-12
926 S(26)=B(26)-6
927 S(27)=B(27)-10
928 S(28)=B(28)-12
929 S(29)=B(29)-16
930 S(30)=B(30)-12
931 S(31)=B(31)-16
932 S(32)=B(32)-14
933 S(33)=B(33)-18
934 S(34)=B(34)-15
935 S(35)=B(35)-14
936 S(36)=B(36)-12
937 S(37)=B(37)-18
938 S(38)=B(38)-12
939 S(39)=B(39)-16
940 S(40)=B(40)-10
941 S(41)=B(41)-6
942 S(42)=B(42)-10
943 S(43)=B(43)-8
944 S(44)=B(44)-12
945 S(45)=B(45)-9
946 S(46)=B(46)-8
947 S(47)=B(47)-6
948 S(48)=B(48)-12
949 S(49)=B(49)-6
950 S(50)=B(50)-10
951 S(51)=B(51)-10
952 S(52)=B(52)-14
953 S(53)=B(53)-12
954 S(54)=B(54)-16
955 S(55)=B(55)-13
956 S(56)=B(56)-12
957 S(57)=B(57)-10
958 S(58)=B(58)-16
959 S(59)=B(59)-10
960 S(60)=B(60)-14
961 S(61)=B(61)-10
962 S(62)=B(62)-8
963 S(63)=B(63)-12
964 S(64)=B(64)-9
965 S(65)=B(65)-8
966 S(66)=B(66)-6
967 S(67)=B(67)-12
968 S(68)=B(68)-6
969 S(69)=B(69)-10
970 S(70)=B(70)-12
971 S(71)=B(71)-16
972 S(72)=B(72)-13
973 S(73)=B(73)-12
974 S(74)=B(74)-10
975 S(75)=B(75)-16
976 S(76)=B(76)-10
977 S(77)=B(77)-14
978 S(78)=B(78)-14
979 S(79)=B(79)-11
980 S(80)=B(80)-10
981 S(81)=B(81)-8
982 S(82)=B(82)-14
983 S(83)=B(83)-8
984 S(84)=B(84)-12
985 S(85)=B(85)-15
986 S(86)=B(86)-14
987 S(87)=B(87)-12
988 S(88)=B(88)-18
989 S(89)=B(89)-12
990 S(90)=B(90)-16
991 S(91)=B(91)-11
992 S(92)=B(92)-9
993 S(93)=B(93)-15
994 S(94)=B(94)-9
995 S(95)=B(95)-13
996 S(96)=B(96)-8
997 S(97)=B(97)-14
998 S(98)=B(98)-8
999 S(99)=B(99)-12
1000 S(100)=B(100)-12
1001 S(101)=B(101)-6
1002 S(102)=B(102)-10
1003 S(103)=B(103)-12
1004 S(104)=B(104)-16
1005 S(105)=B(105)-10
1107 FOR IJUL=1 TO 105
1111 IF S(IJUL)<0 THEN S(IJUL)=ABS(S(IJUL)) ELSE S(IJUL)=0
1115 NEXT IJUL
1380 PH=-10*B(1)-0*B(2)-5*B(3)-1*B(4)-0*B(5)-1*B(6)-2*B(7)-2*B(8)-2*B(9)
1381 PI=-2*B(10)-0*B(11)-4*B(12)-0*B(13)-0*B(14)-1*B(15)-3*B(16)-2*B(17)-2*B(18)
1384 PJ=-2*B(19)-3*B(20)-2*B(21)-0*B(22)-2*B(23)-0*B(24)-10*B(25)-5*B(26)-0*B(27)-10*B(28)
1385 PG=-2*B(29)-0*B(30)-2*B(31)-5*B(32)-4*B(33)-5*B(34)-2*B(35)-2*B(36)
1387 PF=-5*B(37)-5*B(38)-5*B(39)-1*B(40)-1*B(41)-5*B(42)-0*B(43)-0*B(44)-2*B(45)
1389 PE=-1*B(46)-0*B(47)-2*B(48)-5*B(49)-0*B(50)-3*B(51)-5*B(52)-5*B(53)-5*B(54)-1*B(55)
1391 PU=-0*B(56)-3*B(57)-0*B(58)-5*B(59)-5*B(60)-2*B(61)-2*B(62)-1*B(63)-5*B(64)-0*B(65)
1392 PV=-0*B(66)-2*B(67)-5*B(68)-10*B(69)-6*B(70)-0*B(71)-1*B(72)-5*B(73)-5*B(74)-5*B(75)
1393 PW=-1*B(76)-0*B(77)-5*B(78)-2*B(79)-10*B(80)-0*B(81)-5*B(82)-0*B(83)-0*B(84)-0*B(85)
1394 PX=-10*B(86)-5*B(87)-10*B(88)-0*B(89)-2*B(90)-0*B(91)-4*B(92)-0*B(93)-0*B(94)-5*B(95)
1395 PY=-5*B(96)-0*B(97)-5*B(98)-0*B(99)-3*B(100)-3*B(101)-0*B(102)-10*B(103)-2*B(104)-4*B(105)
1485 PL1=-333333!*(S(1)+S(2)+S(3)+S(4)+S(5)+S(6)+S(7)+S(8)+S(9)+S(10)+S(11)+S(12)+S(13)+S(14)+S(15)+S(16)+S(17)+S(18)+S(19)+S(20)+S(21)+S(22)+S(23)+S(24)+S(25)+S(26)+S(27)+S(28))
1486 PL2=-333333!*(S(29)+S(30)+S(31)+S(32)+S(33)+S(34)+S(35)+S(36))
1490 PL3=-333333!*(S(37)+S(38)+S(39)+S(40)+S(41)+S(42)+S(43)+S(44)+S(45))
1491 PL4=-333333!*(S(46)+S(47)+S(48)+S(49)+S(50)+S(51)+S(52)+S(53)+S(54)+S(55))
1493 PL5=-333333!*(S(56)+S(57)+S(58)+S(59)+S(60)+S(61)+S(62)+S(63)+S(64)+S(65)+S(66)+S(67)+S(68)+S(69)+S(70)+S(71)+S(72)+S(73)+S(74))
1494 PL6=-333333!*(S(75)+S(76)+S(77)+S(78)+S(79)+S(80)+S(81)+S(82)+S(83)+S(84)+S(85)+S(86)+S(87)+S(88)+S(89)+S(90)+S(91)+S(92)+S(93))
1495 PL7=-333333!*(S(94)+S(95)+S(96)+S(97)+S(98)+S(99)+S(100)+S(101)+S(102)+S(103)+S(104)+S(105))
1587 PK=PH+PI+PJ+PG+PF+PE+PU+PV+PW+PX+PY
1588 P=PK+PL1+PL2+PL3+PL4+PL5+PL6+PL7
1599 PR=PK
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 15
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-12700 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1914 PRINT A(11),A(12),A(13),A(14),A(15)
1915 PRINT M,MM,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 8 hours of running is presented below. (What immediately follows is a manual copy from the computer screen.)

278 301 401 389 417
427 367 355 331 450
345 377 313 383 437
-12610 -12610 -31135

Interpreted in accordance with line 1912, line 1913, line 1914, and line 1915, the output through JJJJ=-31135 was produced in the first 8 hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

References

Amaral, A.R.S., 2006. On the exact solution of a facility layout problem. European Journal of Operational Research 173, 508-518.

Simmons, D.M., 1969. One-dimensional space allocation: An ordering algorithm. Operations Research 17, 812-826.

An Application of An Integer Programming Computer Program

Jsun Yui Wong

The computer program listed below seeks to solve Problem S11 of Amaral (2006, p. 517), which is a problem from Simmons (1969). In order to have integer locations, the department lengths used in the following computer program have been made twice as long as the given department lengths.

0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(66),A(66),L(66),K(66),P(66),B(66),S(66)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 11
113 A(K)=FIX(RND*699)
115 NEXT K
126 IMAR=10+FIX(RND*12000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 11
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*11):IJM=1+FIX(RND*11):IJN=1+FIX(RND*11)
233 IF RND<.7 THEN X(IJL)=FIX(RND*699) ELSE IF RND<.05 THEN X(IJL)=A(IJL)-1 ELSE GOTO 244
235 GOTO 501
244 X(IJM)=A(IJN):X(IJN)=A(IJM)
501 B(1)=ABS(X(1)-X(2))
502 B(2)=ABS(X(1)-X(3))
503 B(3)=ABS(X(1)-X(4))
504 B(4)=ABS(X(1)-X(5))
505 B(5)=ABS(X(1)-X(6))
506 B(6)=ABS(X(1)-X(7))
507 B(7)=ABS(X(1)-X(8))
508 B(8)=ABS(X(2)-X(3))
509 B(9)=ABS(X(2)-X(4))
510 B(10)=ABS(X(2)-X(5))
511 B(11)=ABS(X(2)-X(6))
512 B(12)=ABS(X(2)-X(7))
513 B(13)=ABS(X(2)-X(8))
514 B(14)=ABS(X(3)-X(4))
515 B(15)=ABS(X(3)-X(5))
516 B(16)=ABS(X(3)-X(6))
517 B(17)=ABS(X(3)-X(7))
518 B(18)=ABS(X(3)-X(8))
519 B(19)=ABS(X(4)-X(5))
520 B(20)=ABS(X(4)-X(6))
521 B(21)=ABS(X(4)-X(7))
522 B(22)=ABS(X(4)-X(8))
523 B(23)=ABS(X(5)-X(6))
524 B(24)=ABS(X(5)-X(7))
525 B(25)=ABS(X(5)-X(8))
526 B(26)=ABS(X(6)-X(7))
527 B(27)=ABS(X(6)-X(8))
528 B(28)=ABS(X(7)-X(8))
529 B(29)=ABS(X(1)-X(9))
530 B(30)=ABS(X(2)-X(9))
531 B(31)=ABS(X(3)-X(9))
532 B(32)=ABS(X(4)-X(9))
533 B(33)=ABS(X(5)-X(9))
534 B(34)=ABS(X(6)-X(9))
535 B(35)=ABS(X(7)-X(9))
536 B(36)=ABS(X(8)-X(9))
537 B(37)=ABS(X(1)-X(10))
538 B(38)=ABS(X(2)-X(10))
539 B(39)=ABS(X(3)-X(10))
540 B(40)=ABS(X(4)-X(10))
541 B(41)=ABS(X(5)-X(10))
542 B(42)=ABS(X(6)-X(10))
543 B(43)=ABS(X(7)-X(10))
544 B(44)=ABS(X(8)-X(10))
545 B(45)=ABS(X(9)-X(10))
546 B(46)=ABS(X(1)-X(11))
547 B(47)=ABS(X(2)-X(11))
548 B(48)=ABS(X(3)-X(11))
549 B(49)=ABS(X(4)-X(11))
550 B(50)=ABS(X(5)-X(11))
551 B(51)=ABS(X(6)-X(11))
552 B(52)=ABS(X(7)-X(11))
553 B(53)=ABS(X(8)-X(11))
554 B(54)=ABS(X(9)-X(11))
555 B(55)=ABS(X(10)-X(11))
556 REM
557 REM
901 S(1)=B(1)-12
902 S(2)=B(2)-6
903 S(3)=B(3)-10
904 S(4)=B(4)-6
905 S(5)=B(5)-10
906 S(6)=B(6)-8
907 S(7)=B(7)-12
908 S(8)=B(8)-12
909 S(9)=B(9)-16
910 S(10)=B(10)-12
911 S(11)=B(11)-16
912 S(12)=B(12)-14
913 S(13)=B(13)-18
914 S(14)=B(14)-10
915 S(15)=B(15)-6
916 S(16)=B(16)-10
917 S(17)=B(17)-8
918 S(18)=B(18)-12
919 S(19)=B(19)-10
920 S(20)=B(20)-14
921 S(21)=B(21)-12
922 S(22)=B(22)-16
923 S(23)=B(23)-10
924 S(24)=B(24)-8
925 S(25)=B(25)-12
926 S(26)=B(26)-12
927 S(27)=B(27)-16
928 S(28)=B(28)-14
929 S(29)=B(29)-9
930 S(30)=B(30)-15
931 S(31)=B(31)-9
932 S(32)=B(32)-13
933 S(33)=B(33)-9
934 S(34)=B(34)-13
935 S(35)=B(35)-11
936 S(36)=B(36)-15
937 S(37)=B(37)-8
938 S(38)=B(38)-14
939 S(39)=B(39)-8
940 S(40)=B(40)-12
941 S(41)=B(41)-8
942 S(42)=B(42)-12
943 S(43)=B(43)-10
944 S(44)=B(44)-14
945 S(45)=B(45)-11
946 S(46)=B(46)-13
947 S(47)=B(47)-19
948 S(48)=B(48)-13
949 S(49)=B(49)-17
950 S(50)=B(50)-13
951 S(51)=B(51)-17
952 S(52)=B(52)-15
953 S(53)=B(53)-19
954 S(54)=B(54)-16
955 S(55)=B(55)-15
956 REM
1107 FOR IJUL=1 TO 55
1111 IF S(IJUL)<0 THEN S(IJUL)=ABS(S(IJUL)) ELSE S(IJUL)=0
1115 NEXT IJUL
1441 PL4=-333333!*(S(46)+S(47)+S(48)+S(49)+S(50)+S(51)+S(52)+S(53)+S(54)+S(55))
1443 PE=-3*B(46)-7*B(47)-0*B(48)-6*B(49)-2*B(50)-18*B(51)-7*B(52)-2*B(53)-0*B(54)-3*B(55)
1444 PF=-20*B(37)-6*B(38)-8*B(39)-14*B(40)-8*B(41)-7*B(42)-15*B(43)-7*B(44)-12*B(45)
1480 PH=-20*B(1)-2*B(2)-8*B(3)-0*B(4)-9*B(5)-5*B(6)-7*B(7)-8*B(8)-9*B(9)
1481 PI=-13*B(10)-17*B(11)-16*B(12)-1*B(13)-18*B(14)-0*B(15)-10*B(16)-4*B(17)-18*B(18)
1482 PL3=-333333!*(S(37)+S(38)+S(39)+S(40)+S(41)+S(42)+S(43)+S(44)+S(45))
1483 PG=-0*B(29)-8*B(30)-5*B(31)-2*B(32)-0*B(33)-2*B(34)-11*B(35)-1*B(36)
1484 PJ=-6*B(19)-16*B(20)-10*B(21)-4*B(22)-6*B(23)-0*B(24)-11*B(25)-6*B(26)-13*B(27)-1*B(28)
1485 PL1=-333333!*(S(1)+S(2)+S(3)+S(4)+S(5)+S(6)+S(7)+S(8)+S(9)+S(10)+S(11)+S(12)+S(13)+S(14)+S(15)+S(16)+S(17)+S(18)+S(19)+S(20)+S(21)+S(22)+S(23)+S(24)+S(25)+S(26)+S(27)+S(28))
1486 PL2=-333333!*(S(29)+S(30)+S(31)+S(32)+S(33)+S(34)+S(35)+S(36))
1487 PK=PH+PI+PJ+PG+PF+PE
1488 P=PK+PL1+PL2+PL3+PL4
1499 PR=PK
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 11
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-13900 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1915 PRINT A(11),M,MM,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 3 hours of running is presented below. (What immediately follows is a manual copy from the computer screen.)

111 99 141 131 161
151 85 173 74 119
192 -13867 -13867 -31876

334 346 304 314 298
288 360 272 371 326
253 -13887 -13887 -31589

319 307 349 339 369
359 293 381 282 327
400 -13867 -13867 -31231

568 580 538 548 518
528 594 506 605 560
487 -31867 -31867 -31007

Interpreted in accordance with line 1912, line 1913, and line 1915, the output through
JJJJ=-31007 was produced in the first 3 hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

References

Amaral, 2006 A.R.S. Amaral, On the exact solution of a facility layout problem, European Journal of Operational Research 173 (2006), pp. 508-518.

Simmons, 1969 D.M. Simmons, One-dimensional space allocation: An ordering algorithm, Operations Research 17 (1969), pp. 812-826.

Erratum

Erratum

Jsun Yui Wong

Referring to line 233 of the preceding post, of Saturday, July 18, 2009, I did not mean to type X(IJK); I meant to type X(IJL).

An Integer Programming Computer Program Applied to One-Dimensional Space Allocation

Jsun Yui Wong

The computer program listed below seeks to solve Problem S10 of Amaral (2006, p. 516), which is a problem from Simmons (1969). In order to have integer locations, the department lengths used in the following computer program have been made twice as long as the given department lengths.

0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(48),A(48),L(48),K(48),P(48),B(48),S(48)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 10
113 A(K)=FIX(RND*199)
115 NEXT K
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 10
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*10)
233 IF RND<.99 THEN X(IJL)=FIX(RND*199) ELSE IF RND<.5 THEN X(IJL)=A(IJL)-1 ELSE X(IJK)=A(IJL)+1
501 B(1)=ABS(X(1)-X(2))
502 B(2)=ABS(X(1)-X(3))
503 B(3)=ABS(X(1)-X(4))
504 B(4)=ABS(X(1)-X(5))
505 B(5)=ABS(X(1)-X(6))
506 B(6)=ABS(X(1)-X(7))
507 B(7)=ABS(X(1)-X(8))
508 B(8)=ABS(X(2)-X(3))
509 B(9)=ABS(X(2)-X(4))
510 B(10)=ABS(X(2)-X(5))
511 B(11)=ABS(X(2)-X(6))
512 B(12)=ABS(X(2)-X(7))
513 B(13)=ABS(X(2)-X(8))
514 B(14)=ABS(X(3)-X(4))
515 B(15)=ABS(X(3)-X(5))
516 B(16)=ABS(X(3)-X(6))
517 B(17)=ABS(X(3)-X(7))
518 B(18)=ABS(X(3)-X(8))
519 B(19)=ABS(X(4)-X(5))
520 B(20)=ABS(X(4)-X(6))
521 B(21)=ABS(X(4)-X(7))
522 B(22)=ABS(X(4)-X(8))
523 B(23)=ABS(X(5)-X(6))
524 B(24)=ABS(X(5)-X(7))
525 B(25)=ABS(X(5)-X(8))
526 B(26)=ABS(X(6)-X(7))
527 B(27)=ABS(X(6)-X(8))
528 B(28)=ABS(X(7)-X(8))
529 B(29)=ABS(X(1)-X(9))
530 B(30)=ABS(X(2)-X(9))
531 B(31)=ABS(X(3)-X(9))
532 B(32)=ABS(X(4)-X(9))
533 B(33)=ABS(X(5)-X(9))
534 B(34)=ABS(X(6)-X(9))
535 B(35)=ABS(X(7)-X(9))
536 B(36)=ABS(X(8)-X(9))
537 B(37)=ABS(X(1)-X(10))
538 B(38)=ABS(X(2)-X(10))
539 B(39)=ABS(X(3)-X(10))
540 B(40)=ABS(X(4)-X(10))
541 B(41)=ABS(X(5)-X(10))
542 B(42)=ABS(X(6)-X(10))
543 B(43)=ABS(X(7)-X(10))
544 B(44)=ABS(X(8)-X(10))
545 B(45)=ABS(X(9)-X(10))
546 REM
547 REM
548 REM
549 REM
901 S(1)=B(1)-9
902 S(2)=B(2)-15
903 S(3)=B(3)-10
904 S(4)=B(4)-8
905 S(5)=B(5)-12
906 S(6)=B(6)-14
907 S(7)=B(7)-15
908 S(8)=B(8)-12
909 S(9)=B(9)-7
910 S(10)=B(10)-5
911 S(11)=B(11)-9
912 S(12)=B(12)-11
913 S(13)=B(13)-12
914 S(14)=B(14)-13
915 S(15)=B(15)-11
916 S(16)=B(16)-15
917 S(17)=B(17)-17
918 S(18)=B(18)-18
919 S(19)=B(19)-6
920 S(20)=B(20)-10
921 S(21)=B(21)-12
922 S(22)=B(22)-13
923 S(23)=B(23)-8
924 S(24)=B(24)-10
925 S(25)=B(25)-11
926 S(26)=B(26)-14
927 S(27)=B(27)-15
928 S(28)=B(28)-17
929 S(29)=B(29)-12
930 S(30)=B(30)-9
931 S(31)=B(31)-15
932 S(32)=B(32)-10
933 S(33)=B(33)-8
934 S(34)=B(34)-12
935 S(35)=B(35)-14
936 S(36)=B(36)-15
937 S(37)=B(37)-13
938 S(38)=B(38)-10
939 S(39)=B(39)-16
940 S(40)=B(40)-11
941 S(41)=B(41)-9
942 S(42)=B(42)-13
943 S(43)=B(43)-15
944 S(44)=B(44)-16
945 S(45)=B(45)-13
946 REM
947 REM
948 REM
949 REM
1107 FOR IJUL=1 TO 45
1111 IF S(IJUL)<0 THEN S(IJUL)=ABS(S(IJUL)) ELSE S(IJUL)=0
1115 NEXT IJUL
1444 PF=-0*B(37)-7*B(38)-4*B(39)-5*B(40)-12*B(41)-5*B(42)-9*B(43)-7*B(44)-0*B(45)
1480 PH=-0*B(1)-9*B(2)-5*B(3)-1*B(4)-4*B(5)-5*B(6)-4*B(7)-4*B(8)-5*B(9)
1481 PI=-2*B(10)-7*B(11)-2*B(12)-9*B(13)-0*B(14)-7*B(15)-2*B(16)-5*B(17)-0*B(18)
1482 PL3=-333333!*(S(37)+S(38)+S(39)+S(40)+S(41)+S(42)+S(43)+S(44)+S(45))
1483 PG=-7*B(29)-0*B(30)-9*B(31)-2*B(32)-2*B(33)-3*B(34)-2*B(35)-1*B(36)
1484 PJ=-7*B(19)-9*B(20)-0*B(21)-5*B(22)-0*B(23)-4*B(24)-7*B(25)-4*B(26)-9*B(27)-0*B(28)
1485 PL1=-333333!*(S(1)+S(2)+S(3)+S(4)+S(5)+S(6)+S(7)+S(8)+S(9)+S(10)+S(11)+S(12)+S(13)+S(14)+S(15)+S(16)+S(17)+S(18)+S(19)+S(20)+S(21)+S(22)+S(23)+S(24)+S(25)+S(26)+S(27)+S(28))
1486 PL2=-333333!*(S(29)+S(30)+S(31)+S(32)+S(33)+S(34)+S(35)+S(36))
1487 PK=PH+PI+PJ+PG+PF
1488 P=PK+PL1+PL2+PL3
1499 PR=PK
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 10
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-5625 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9),A(10)
1915 PRINT M,MM,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 1.5 hours of running is presented below. (What immediately follows is a manual copy from the computer screen.)

131 80 146 87 107
71 117 56 161 98
-5563 -5563 -26486

Interpreted in accordance with line 1912, line 1913, and line 1915, the output through
JJJJ=-26486 was produced in the first 1.5 hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

References

Amaral, 2006 A.R.S. Amaral, On the exact solution of a facility layout problem, European Journal of Operational Research 173 (2006), pp. 508-518.

Simmons, 1969 D.M. Simmons, One-dimensional space allocation: An ordering algorithm, Operations Research 17 (1969), pp. 812-826.

An Integer Programming Computer Program Applied to One-Dimensional Space Allocation

Jsun Yui Wong

The computer program listed below seeks to solve Problem S9 of Amaral (2006, p. 515), which is a problem from Simmons (1969). In order to have integer locations, the department lengths used in the following computer program have been made twice as long as the given department lengths.

0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(44),A(44),L(44),K(44),P(44),B(44),S(44)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 9
113 A(K)=FIX(RND*199)
115 NEXT K
126 IMAR=10+FIX(RND*2000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 9
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*9)
233 X(IJL)=FIX(RND*199)
501 B(1)=ABS(X(1)-X(2))
502 B(2)=ABS(X(1)-X(3))
503 B(3)=ABS(X(1)-X(4))
504 B(4)=ABS(X(1)-X(5))
505 B(5)=ABS(X(1)-X(6))
506 B(6)=ABS(X(1)-X(7))
507 B(7)=ABS(X(1)-X(8))
508 B(8)=ABS(X(2)-X(3))
509 B(9)=ABS(X(2)-X(4))
510 B(10)=ABS(X(2)-X(5))
511 B(11)=ABS(X(2)-X(6))
512 B(12)=ABS(X(2)-X(7))
513 B(13)=ABS(X(2)-X(8))
514 B(14)=ABS(X(3)-X(4))
515 B(15)=ABS(X(3)-X(5))
516 B(16)=ABS(X(3)-X(6))
517 B(17)=ABS(X(3)-X(7))
518 B(18)=ABS(X(3)-X(8))
519 B(19)=ABS(X(4)-X(5))
520 B(20)=ABS(X(4)-X(6))
521 B(21)=ABS(X(4)-X(7))
522 B(22)=ABS(X(4)-X(8))
523 B(23)=ABS(X(5)-X(6))
524 B(24)=ABS(X(5)-X(7))
525 B(25)=ABS(X(5)-X(8))
526 B(26)=ABS(X(6)-X(7))
527 B(27)=ABS(X(6)-X(8))
528 B(28)=ABS(X(7)-X(8))
529 B(29)=ABS(X(1)-X(9))
530 B(30)=ABS(X(2)-X(9))
531 B(31)=ABS(X(3)-X(9))
532 B(32)=ABS(X(4)-X(9))
533 B(33)=ABS(X(5)-X(9))
534 B(34)=ABS(X(6)-X(9))
535 B(35)=ABS(X(7)-X(9))
536 B(36)=ABS(X(8)-X(9))
901 S(1)=B(1)-10
902 S(2)=B(2)-11
903 S(3)=B(3)-9
904 S(4)=B(4)-5
905 S(5)=B(5)-6
906 S(6)=B(6)-8
907 S(7)=B(7)-10
908 S(8)=B(8)-17
909 S(9)=B(9)-15
910 S(10)=B(10)-11
911 S(11)=B(11)-12
912 S(12)=B(12)-14
913 S(13)=B(13)-16
914 S(14)=B(14)-16
915 S(15)=B(15)-12
916 S(16)=B(16)-13
917 S(17)=B(17)-15
918 S(18)=B(18)-17
919 S(19)=B(19)-10
920 S(20)=B(20)-11
921 S(21)=B(21)-13
922 S(22)=B(22)-15
923 S(23)=B(23)-7
924 S(24)=B(24)-9
925 S(25)=B(25)-11
926 S(26)=B(26)-10
927 S(27)=B(27)-12
928 S(28)=B(28)-14
929 S(29)=B(29)-11
930 S(30)=B(30)-17
931 S(31)=B(31)-18
932 S(32)=B(32)-16
933 S(33)=B(33)-12
934 S(34)=B(34)-13
935 S(35)=B(35)-15
936 S(36)=B(36)-17
1107 FOR IJUL=1 TO 36
1111 IF S(IJUL)<0 THEN S(IJUL)=ABS(S(IJUL)) ELSE S(IJUL)=0
1115 NEXT IJUL
1480 PH=-0*B(1)-2*B(2)-8*B(3)-7*B(4)-4*B(5)-0*B(6)-1*B(7)-8*B(8)-0*B(9)
1481 PI=-2*B(10)-7*B(11)-4*B(12)-4*B(13)-2*B(14)-7*B(15)-8*B(16)-0*B(17)-2*B(18)
1483 PG=-6*B(29)-6*B(30)-6*B(31)-6*B(32)-6*B(33)-6*B(34)-6*B(35)-6*B(36)
1484 PJ=-5*B(19)-0*B(20)-8*B(21)-8*B(22)-5*B(23)-4*B(24)-7*B(25)-8*B(26)-2*B(27)-4*B(28)
1485 PL1=-333333!*(S(1)+S(2)+S(3)+S(4)+S(5)+S(6)+S(7)+S(8)+S(9)+S(10)+S(11)+S(12)+S(13)+S(14)+S(15)+S(16)+S(17)+S(18)+S(19)+S(20)+S(21)+S(22)+S(23)+S(24)+S(25)+S(26)+S(27)+S(28))
1486 PL2=-333333!*(S(29)+S(30)+S(31)+S(32)+S(33)+S(34)+S(35)+S(36))
1487 PK=PH+PI+PJ+PG
1488 P=PK+PL1+PL2
1499 PR=PK
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 9
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-4970 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8),A(9)
1915 PRINT M,MM,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 2.5 hours of running is presented below. (What immediately follows is a manual copy from the computer screen.)

60 114 97 33 55
84 46 18 71
-4939 -4939 -29824

113 71 54 134 108
83 121 149 96
-4959 -4959 -25780

99 159 142 78 104
129 91 63 116
-4941 -4941 -24725

Interpreted in accordance with line 1912, line 1913, and line 1915, the output through
JJJJ=-24725 was produced in the first 2.5 hours of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

References

Amaral, 2006 A.R.S. Amaral, On the exact solution of a facility layout problem, European Journal of Operational Research 173 (2006), pp. 508-518.

Simmons, 1969 D.M. Simmons, One-dimensional space allocation: An ordering algorithm, Operations Research 17 (1969), pp. 812-826.

An Integer Programming Computer Program Applied to One-Dimensional Space Allocation

Jsun Yui Wong

The computer program listed below seeks to solve Problem S8 of Amaral (2006, p. 514), which is a problem from Simmons (1969). In order to have integer locations, the department lengths used in the following computer program have been made twice as long as the given department lengths.

0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33),P(33),B(33),S(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 8
113 A(K)=FIX(RND*99)
115 NEXT K
126 IMAR=10+FIX(RND*2000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 8
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*8)
233 X(IJL)=FIX(RND*99)
501 B(1)=ABS(X(1)-X(2))
502 B(2)=ABS(X(1)-X(3))
503 B(3)=ABS(X(1)-X(4))
504 B(4)=ABS(X(1)-X(5))
505 B(5)=ABS(X(1)-X(6))
506 B(6)=ABS(X(1)-X(7))
507 B(7)=ABS(X(1)-X(8))
508 B(8)=ABS(X(2)-X(3))
509 B(9)=ABS(X(2)-X(4))
510 B(10)=ABS(X(2)-X(5))
511 B(11)=ABS(X(2)-X(6))
512 B(12)=ABS(X(2)-X(7))
513 B(13)=ABS(X(2)-X(8))
514 B(14)=ABS(X(3)-X(4))
515 B(15)=ABS(X(3)-X(5))
516 B(16)=ABS(X(3)-X(6))
517 B(17)=ABS(X(3)-X(7))
518 B(18)=ABS(X(3)-X(8))
519 B(19)=ABS(X(4)-X(5))
520 B(20)=ABS(X(4)-X(6))
521 B(21)=ABS(X(4)-X(7))
522 B(22)=ABS(X(4)-X(8))
523 B(23)=ABS(X(5)-X(6))
524 B(24)=ABS(X(5)-X(7))
525 B(25)=ABS(X(5)-X(8))
526 B(26)=ABS(X(6)-X(7))
527 B(27)=ABS(X(6)-X(8))
528 B(28)=ABS(X(7)-X(8))
529 REM
530 REM
531 REM
901 S(1)=B(1)-5
902 S(2)=B(2)-6
903 S(3)=B(3)-7
904 S(4)=B(4)-8
905 S(5)=B(5)-5
906 S(6)=B(6)-9
907 S(7)=B(7)-6
908 S(8)=B(8)-7
909 S(9)=B(9)-8
910 S(10)=B(10)-9
911 S(11)=B(11)-6
912 S(12)=B(12)-10
913 S(13)=B(13)-7
914 S(14)=B(14)-9
915 S(15)=B(15)-10
916 S(16)=B(16)-7
917 S(17)=B(17)-11
918 S(18)=B(18)-8
919 S(19)=B(19)-11
920 S(20)=B(20)-8
921 S(21)=B(21)-12
922 S(22)=B(22)-9
923 S(23)=B(23)-9
924 S(24)=B(24)-13
925 S(25)=B(25)-10
926 S(26)=B(26)-10
927 S(27)=B(27)-7
928 S(28)=B(28)-11
1107 FOR IJUL=1 TO 28
1111 IF S(IJUL)<0 THEN S(IJUL)=ABS(S(IJUL)) ELSE S(IJUL)=0
1115 NEXT IJUL
1480 PH=-6*B(1)-4*B(2)-1*B(3)-7*B(4)-3*B(5)-5*B(6)-0*B(7)-1*B(8)-2*B(9)
1481 PI=-5*B(10)-2*B(11)-4*B(12)-3*B(13)-0*B(14)-6*B(15)-3*B(16)-2*B(17)-2*B(18)
1484 PJ=-3*B(19)-4*B(20)-0*B(21)-1*B(22)-0*B(23)-6*B(24)-6*B(25)-3*B(26)-5*B(27)-2*B(28)
1485 PL=-333333!*(S(1)+S(2)+S(3)+S(4)+S(5)+S(6)+S(7)+S(8)+S(9)+S(10)+S(11)+S(12)+S(13)+S(14)+S(15)+S(16)+S(17)+S(18)+S(19)+S(20)+S(21)+S(22)+S(23)+S(24)+S(25)+S(26)+S(27)+S(28))
1486 PK=PH+PI+PJ
1488 P=PK+PL
1499 PR=PK
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 8
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-1611 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8)
1915 PRINT M,MM,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 50 minutes of running is presented below. (What immediately follows is a manual copy from the computer screen.)

54 49 72 95 62
87 39 80
-1602 -1602 -30956

71 76 53 30 63
38 86 45
-1602 -1602 -27316

Interpreted in accordance with line 1912, line 1913, and line 1915, the output through
JJJJ=-27316 was produced in the first 50 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

References

Amaral, 2006 A.R.S. Amaral, On the exact solution of a facility layout problem, European Journal of Operational Research 173 (2006), pp. 508-518.

Simmons, 1969 D.M. Simmons, One-dimensional space allocation: An ordering algorithm, Operations Research 17 (1969), pp. 812-826.

An Integer Programming Computer Program Applied to a One-Dimensional Layout Problem

Jsun Yui Wong

The computer program listed below seeks to solve Problem LW5 of Amaral (2006, p. 514), which is Problem 1 of Love and Wong (1976, p. 141). In order to have integer locations, the department lengths used in the following computer program have been made twice as long as the given department lengths.

0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33),P(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 5
113 A(K)=FIX(RND*99)
115 NEXT K
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR KK=1 TO 5
131 X(KK)=A(KK)
132 NEXT KK
222 IJL=1+FIX(RND*9)
233 X(IJL)=FIX(RND*99)
1151 P1=ABS(X(1)-X(2))-4
1153 IF P1<0 THEN P1=P1 ELSE P1=0
1155 P2=ABS(X(1)-X(3))-5
1157 IF P2<0 THEN P2=P2 ELSE P2=0
1161 P3=ABS(X(1)-X(4))-7
1163 IF P3<0 THEN P3=P3 ELSE P3=0
1164 P4=ABS(X(1)-X(5))-8
1165 IF P4<0 THEN P4=P4 ELSE P4=0
1166 P5=ABS(X(2)-X(3))-7
1167 IF P5<0 THEN P5=P5 ELSE P5=0
1168 P6=ABS(X(2)-X(4))-9
1169 IF P6<0 THEN P6=P6 ELSE P6=0
1171 P7=ABS(X(2)-X(5))-10
1173 IF P7<0 THEN P7=P7 ELSE P7=0
1175 P8=ABS(X(3)-X(4))-10
1177 IF P8<0 THEN P8=P8 ELSE P8=0
1181 P9=ABS(X(3)-X(5))-11
1182 IF P9<0 THEN P9=P9 ELSE P9=0
1184 P10=ABS(X(4)-X(5))-13
1185 IF P10<0 THEN P10=P10 ELSE P10=0
1482 PK=-2*ABS(X(1)-X(2))-1*ABS(X(1)-X(3))-0*ABS(X(1)-X(4))-1*ABS(X(1)-X(5))-0*ABS(X(2)-X(3))-2*ABS(X(2)-X(4))-2*ABS(X(2)-X(5))-6*ABS(X(3)-X(4))-3*ABS(X(3)-X(5))-4*ABS(X(4)-X(5))
1485 PL=-333333!*(ABS(P1)+ABS(P2)+ABS(P3)+ABS(P4)+ABS(P5)+ABS(P6)+ABS(P7)+ABS(P8)+ABS(P9)+ABS(P10))
1488 P=PK+PL
1499 PR=PK
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 5
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-303 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1915 PRINT M,MM,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 12 seconds of running is presented below. (What immediately follows is a manual copy from the computer screen.)

51 55 32 22 43
-302 -302 -31968

58 54 89 79 66
-302 -302 -31883

Interpreted in accordance with line 1912 and line 1915, the output through JJJJ=-31883 was produced in the first 12 seconds of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

References

Amaral, 2006 A.R.S. Amaral, On the exact solution of a facility layout problem, European Journal of Operational Research 173 (2006), pp. 508-518.

Love and Wong, 1976 R.F. Love and J.Y. Wong, On solving a one-dimensional allocation problem with integer programming, Information Processig and Operations Research (INFOR) 14 (1976), pp. 139-143.

An Integer Programming Computer Program Applied to a One-Dimensional Layout Problem

Jsun Yui Wong

The computer program listed below seeks to solve Problem P4 of Amaral (2006, p. 518).

0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33),P(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
111 FOR K=1 TO 4
113 A(IJL)=FIX(RND*50)
115 NEXT K
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 4
131 X(K)=A(K)
132 NEXT K
222 IJL=1+FIX(RND*4)
233 X(IJL)=FIX(RND*50)
1151 P1=ABS(X(1)-X(2))-11
1153 IF P1<0 THEN P1=P1 ELSE P1=0
1155 P2=ABS(X(1)-X(3))-12
1157 IF P2<0 THEN P2=P2 ELSE P2=0
1161 P3=ABS(X(1)-X(4))-18
1163 IF P3<0 THEN P3=P3 ELSE P3=0
1165 P4=ABS(X(2)-X(3))-10
1167 IF P4<0 THEN P4=P4 ELSE P4=0
1171 P5=ABS(X(2)-X(4))-16
1173 IF P5<0 THEN P5=P5 ELSE P5=0
1175 P6=ABS(X(3)-X(4))-17
1177 IF P6<0 THEN P6=P6 ELSE P6=0
1488 P=-5*ABS(X(1)-X(2))-2*ABS(X(1)-X(3))-11*ABS(X(1)-X(4))-3*ABS(X(2)-X(3))-2*ABS(X(2)-X(4))-7*ABS(X(3)-X(4))-333333!*(ABS(P1)+ABS(P2)+ABS(P3)+ABS(P4)+ABS(P5)+ABS(P6))
1499 PR=-5*ABS(X(1)-X(2))-2*ABS(X(1)-X(3))-11*ABS(X(1)-X(4))-3*ABS(X(2)-X(3))-2*ABS(X(2)-X(4))-7*ABS(X(3)-X(4))
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 4
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-639 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4)
1915 PRINT M,MM,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 5 seconds of running is presented below. (What immediately follows is a manual copy from the computer screen.)

35 46 0 17
-638 -638 -31982

14 3 49 32
-638 -638 -31969

13 2 48 31
-638 -638 -31917

Interpreted in accordance with line 1912 and line 1915, the output through JJJJ=-31917 was produced in the first 5 seconds of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

Reference

Amaral, 2006 A.R.S. Amaral, On the exact solution of a facility layout problem, European Journal of Operational Research 173 (2006), pp. 508-518.

A Computer Program for Solving Nonlinear Programs with Big Integer Variables and Continuous Variables

Jsun Yui Wong

The computer program listed below seeks to solve Problem 32 on page 430 of Himmelblau (1972) plus the restriction that X(4)= -10000, -9999, -9998,..., 0, 1, 2, 3,..., 9998, 9999, 10000. On page 171 Schittkowski (1987) cites the original Himmelblau problem. (The present paper's X(4) is Himmelblau's X(3).)

0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
93 A(1)=-200+RND*400
94 A(2)=-200+RND*400
95 A(3)=-200+RND*400
96 A(4)=-10000+FIX(RND*20001)
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 4
131 X(K)=A(K)
132 NEXT K
811 IF RND<.99 THEN 903 ELSE 991
903 IF RND<1/3 THEN 911 ELSE IF RND<.6666 THEN 921 ELSE 931
911 IF RND<.5 THEN X(1)=-200+RND*400 ELSE X(1)=A(1)+(1-2*RND)*.001*A(1)
915 GOTO 1151
921 IF RND>.5 THEN X(2)=-200+RND*400 ELSE X(2)=A(2)+(1-2*RND)*.001*A(2)
925 GOTO 1151
931 IF RND>.5 THEN X(3)=-200+RND*400 ELSE X(3)=A(3)+(1-2*RND)*.001*A(3)
935 GOTO 1151
991 X(4)=-10000+FIX(RND*20001)
1151 PN1=( ( ( (X(1)^2+X(2)^2*0+X(4)^2*0^2)/(1+X(3)^2*0) )-7.391 ) /7.391 )^2
1412 PN2=( ( ((X(1)^2+X(2)^2*.000428+X(4)^2*.000428^2)/(1+X(3)^2*.000428) )-11.18 ) /11.18 )^2
1413 PN3=((((X(1)^2+X(2)^2*.001+X(4)^2*.001^2)/(1+X(3)^2*.001))-16.44)/16.44)^2
1414 PN4=( ( ((X(1)^2+X(2)^2*.00161+X(4)^2*.00161^2)/(1+X(3)^2*.00161) )-16.2 ) /16.2 )^2
1415 PN5=( ( ((X(1)^2+X(2)^2*.00209+X(4)^2*.00209^2)/(1+X(3)^2*.00209) )-22.2 ) /22.2 )^2
1416 PN6=( ( ( (X(1)^2+X(2)^2*.00348+X(4)^2*.00348^2)/(1+X(3)^2*.00348) )-24.02 ) /24.02 )^2
1417 PN7=( (( (X(1)^2+X(2)^2*.00525+X(4)^2*.00525^2)/(1+X(3)^2*.00525) )-31.32 ) /31.32 )^2
1488 P=-10000*(PN1+PN2+PN3+PN4+PN5+PN6+PN7)
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 4
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-318.58 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3)
1915 PRINT A(4),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 135 minutes of running is presented below. (What immediately follows is a manual copy from the computer screen.)

2.714237050418973 140.4151258896569 31.49233633228084
-1705 -318.5732852674301 -31298

2.714280115627704 -140.2320246506003 31.42037915619026
1700 -318.5740851107986 -30759

-2.714207738385269 -140.6681589846467 -31.5975277066794
-1713 -318.5729772121449 -30490

2.714219334477566 140.659169951501 31.59590264214858
-1713 -318.5727862195563 -30038

-2.714275982647368 -140.6449146479193 31.5928202101209
-1713 -318.5725422579476 -29577

Interpreted in accordance with line 1912 and line 1915, the output through JJJJ=-29577 was produced in the first 135 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

References

D. M. Himmelblau (1972): "Applied Nonlinear Programming," McGraw-Hill, New York.

K. Schittkowski (1987): "More Test Problems for Nonlinear Programming Codes," Springer-Verlag, Berlin, Heidelberg, New York.

A Computer Program for Solving Nonlinear Programs with Big Integer Variables and Continuous Variables

Jsun Yui Wong

The computer program listed below seeks to solve Problem 351 on page 171 of Schittkowski (1987) plus the additional restriction that X(4)= -5000, -1999, -1998,..., 0, 1, 2, 3,..., 5000. (The present paper's X(4) is Schittkowski's X(3).)

0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
93 A(1)=-200+RND*400
94 A(2)=-200+RND*400
95 A(3)=-200+RND*400
96 A(4)=-5000+FIX(RND*10001)
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 4
131 X(K)=A(K)
132 NEXT K
811 IF RND<.99 THEN 903 ELSE 991
903 IF RND<1/3 THEN 911 ELSE IF RND<.6666 THEN 921 ELSE 931
911 IF RND<.5 THEN X(1)=-200+RND*400 ELSE X(1)=A(1)+(1-2*RND)*.001*A(1)
915 GOTO 1151
921 IF RND>.5 THEN X(2)=-200+RND*400 ELSE X(2)=A(2)+(1-2*RND)*.001*A(2)
925 GOTO 1151
931 IF RND>.5 THEN X(3)=-200+RND*400 ELSE X(3)=A(3)+(1-2*RND)*.001*A(3)
935 GOTO 1151
991 X(4)=-5000+FIX(RND*10001)
1151 PN1=( ( ( (X(1)^2+X(2)^2*0+X(4)^2*0^2)/(1+X(3)^2*0) )-7.391 ) /7.391 )^2
1412 PN2=( ( ((X(1)^2+X(2)^2*.000428+X(4)^2*.000428^2)/(1+X(3)^2*.000428) )-11.18 ) /11.18 )^2
1413 PN3=((((X(1)^2+X(2)^2*.001+X(4)^2*.001^2)/(1+X(3)^2*.001))-16.44)/16.44)^2
1414 PN4=( ( ((X(1)^2+X(2)^2*.00161+X(4)^2*.00161^2)/(1+X(3)^2*.00161) )-16.2 ) /16.2 )^2
1415 PN5=( ( ((X(1)^2+X(2)^2*.00209+X(4)^2*.00209^2)/(1+X(3)^2*.00209) )-22.2 ) /22.2 )^2
1416 PN6=( ( ( (X(1)^2+X(2)^2*.00348+X(4)^2*.00348^2)/(1+X(3)^2*.00348) )-24.02 ) /24.02 )^2
1417 PN7=( (( (X(1)^2+X(2)^2*.00525+X(4)^2*.00525^2)/(1+X(3)^2*.00525) )-31.32 ) /31.32 )^2
1488 P=-10000*(PN1+PN2+PN3+PN4+PN5+PN6+PN7)
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 4
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-318.58 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3)
1915 PRINT A(4),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 19 minutes of running is presented below. (What immediately follows is a manual copy from the computer screen.)

-2.714312896940182 140.3940069176071 31.48803319530502
1705 -318.5725440474395 -31836

2.714211402467661 140.6948587831022 31.60978675619501
1714 -318.5730861747321 -31650

Interpreted in accordance with line 1912 and line 1915, the output through JJJJ=-31650 was produced in the first 19 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

Reference

K. Schittkowski (1987): "More Test Problems for Nonlinear Programming Codes," Springer-Verlag, Berlin, Heidelberg, New York.

A Computer Program for Solving Nonlinear Programs with Big Integer Variables and Continuous Variables

Jsun Yui Wong

The computer program listed below seeks to solve Problem 351 on page 171 of Schittkowski (1987) plus the additional restriction that X(4)= -2000, -1999, -1998,..., 0, 1, 2, 3,..., 2000. (The present paper's X(4) is Schittkowski's X(3).)

0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
93 A(1)=-200+RND*400
94 A(2)=-200+RND*400
95 A(3)=-200+RND*400
96 A(4)=-2000+FIX(RND*4001)
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 4
131 X(K)=A(K)
132 NEXT K
811 IF RND<.99 THEN 903 ELSE 991
903 IF RND<1/3 THEN 911 ELSE IF RND<.6666 THEN 921 ELSE 931
911 IF RND<.5 THEN X(1)=-200+RND*400 ELSE X(1)=A(1)+(1-2*RND)*.001*A(1)
915 GOTO 1151
921 IF RND>.5 THEN X(2)=-200+RND*400 ELSE X(2)=A(2)+(1-2*RND)*.001*A(2)
925 GOTO 1151
931 IF RND>.5 THEN X(3)=-200+RND*400 ELSE X(3)=A(3)+(1-2*RND)*.001*A(3)
935 GOTO 1151
991 X(4)=-2000+FIX(RND*4001)
1151 PN1=( ( ( (X(1)^2+X(2)^2*0+X(4)^2*0^2)/(1+X(3)^2*0) )-7.391 ) /7.391 )^2
1412 PN2=( ( ((X(1)^2+X(2)^2*.000428+X(4)^2*.000428^2)/(1+X(3)^2*.000428) )-11.18 ) /11.18 )^2
1413 PN3=((((X(1)^2+X(2)^2*.001+X(4)^2*.001^2)/(1+X(3)^2*.001))-16.44)/16.44)^2
1414 PN4=( ( ((X(1)^2+X(2)^2*.00161+X(4)^2*.00161^2)/(1+X(3)^2*.00161) )-16.2 ) /16.2 )^2
1415 PN5=( ( ((X(1)^2+X(2)^2*.00209+X(4)^2*.00209^2)/(1+X(3)^2*.00209) )-22.2 ) /22.2 )^2
1416 PN6=( ( ( (X(1)^2+X(2)^2*.00348+X(4)^2*.00348^2)/(1+X(3)^2*.00348) )-24.02 ) /24.02 )^2
1417 PN7=( (( (X(1)^2+X(2)^2*.00525+X(4)^2*.00525^2)/(1+X(3)^2*.00525) )-31.32 ) /31.32 )^2
1488 P=-10000*(PN1+PN2+PN3+PN4+PN5+PN6+PN7)
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 4
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-318.58 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3)
1915 PRINT A(4),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 12 minutes of running is presented below. (What immediately follows is a manual copy from the computer screen.)

-2.714222937954861 140.2917355502167 -31.44020669713073
-1701 -318.5749116563952 -31981

2.714177822632929 140.6753855504382 31.59890524079304
1713 -318.5731749056944 -31940

-2.714359817426322 140.3029798440046 31.45529451959602
1703 -318.572363941116 -31782

Interpreted in accordance with line 1912 and line 1915, the output through JJJJ=-31782 was produced in the first 12 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

Reference

K. Schittkowski (1987): "More Test Problems for Nonlinear Programming Codes," Springer-Verlag, Berlin, Heidelberg, New York.

A Computer Program for Solving Nonlinear Programs with Big Integer Variables and Continuous Variables

Jsun Yui Wong

The computer program listed below seeks to solve Problem 351 on page 171 of Schittkowski (1987) plus the additional restriction that X(4)= 0, 1, 2, 3,..., 2000.
(The present paper's X(4) is Schittkowski's X(3).)

0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
93 A(1)=RND*200
94 A(2)=RND*200
95 A(3)=RND*200
96 A(4)=FIX(RND*2000)
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 4
131 X(K)=A(K)
132 NEXT K
811 IF RND<.99 THEN 903 ELSE 991
903 IF RND<1/3 THEN 911 ELSE IF RND<.6666 THEN 921 ELSE 931
911 IF RND<.5 THEN X(1)=RND*200 ELSE X(1)=A(1)+(1-2*RND)*.00001*A(1)
915 GOTO 1151
921 IF RND>.5 THEN X(2)=RND*200 ELSE X(2)=A(2)+(1-2*RND)*.00001*A(2)
925 GOTO 1151
931 IF RND>.5 THEN X(3)=RND*200 ELSE X(3)=A(3)+(1-2*RND)*.00001*A(3)
935 GOTO 1151
991 X(4)=FIX(RND*2001)
1151 PN1=( ( ( (X(1)^2+X(2)^2*0+X(4)^2*0^2)/(1+X(3)^2*0) )-7.391 ) /7.391 )^2
1412 PN2=( ( ((X(1)^2+X(2)^2*.000428+X(4)^2*.000428^2)/(1+X(3)^2*.000428) )-11.18 ) /11.18 )^2
1413 PN3=((((X(1)^2+X(2)^2*.001+X(4)^2*.001^2)/(1+X(3)^2*.001))-16.44)/16.44)^2
1414 PN4=( ( ((X(1)^2+X(2)^2*.00161+X(4)^2*.00161^2)/(1+X(3)^2*.00161) )-16.2 ) /16.2 )^2
1415 PN5=( ( ((X(1)^2+X(2)^2*.00209+X(4)^2*.00209^2)/(1+X(3)^2*.00209) )-22.2 ) /22.2 )^2
1416 PN6=( ( ( (X(1)^2+X(2)^2*.00348+X(4)^2*.00348^2)/(1+X(3)^2*.00348) )-24.02 ) /24.02 )^2
1417 PN7=( (( (X(1)^2+X(2)^2*.00525+X(4)^2*.00525^2)/(1+X(3)^2*.00525) )-31.32 ) /31.32 )^2
1488 P=-10000*(PN1+PN2+PN3+PN4+PN5+PN6+PN7)
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 4
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-318.6 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3)
1915 PRINT A(4),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 37 minutes of running is presented below. (What immediately follows is a manual copy from the computer screen.)

2.714010507796987 141.4974531034683 31.93520490677342
1738 -318.5943924629846 -31998

2.71426536308301 140.7310075994925 31.63039117713214
1716 -318.5734555283789 -31929

Interpreted in accordance with line 1912 and line 1915, the output through JJJJ=-31929 was produced in the first 37 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

Reference

K. Schittkowski (1987): "More Test Problems for Nonlinear Programming Codes," Springer-Verlag, Berlin, Heidelberg, New York.

A Computer Program for Solving Nonlinear Programs with Big Integer Variables and Continuous Variables

Jsun Yui Wong

The computer program listed below seeks to solve Problem 351 on page 171 of Schittkowski (1987) plus the additional restriction that X(4)= 0, 1, 2, 3,..., 2000.
(The present paper's X(4) is Schittkowski's X(3).)

0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
93 A(1)=RND*200
94 A(2)=RND*200
95 A(3)=RND*200
96 A(4)=FIX(RND*2000)
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 4
131 X(K)=A(K)
132 NEXT K
811 IF RND<.99 THEN 903 ELSE 991
903 IF RND<1/3 THEN 911 ELSE IF RND<.6666 THEN 921 ELSE 931
911 IF RND<.5 THEN X(1)=RND*200 ELSE X(1)=A(1)+(1-2*RND)*.00001*A(1)
915 GOTO 1151
921 IF RND>.5 THEN X(2)=RND*200 ELSE X(2)=A(2)+(1-2*RND)*.00001*A(2)
925 GOTO 1151
931 IF RND>.5 THEN X(3)=RND*200 ELSE X(3)=A(3)+(1-2*RND)*.00001*A(3)
935 GOTO 1151
991 X(4)=FIX(RND*2001)
1151 PN1=( ( ( (X(1)^2+X(2)^2*0+X(4)^2*0^2)/(1+X(3)^2*0) )-7.391 ) /7.391 )^2
1412 PN2=( ( ((X(1)^2+X(2)^2*.000428+X(4)^2*.000428^2)/(1+X(3)^2*.000428) )-11.18 ) /11.18 )^2
1413 PN3=((((X(1)^2+X(2)^2*.001+X(4)^2*.001^2)/(1+X(3)^2*.001))-16.44)/16.44)^2
1414 PN4=( ( ((X(1)^2+X(2)^2*.00161+X(4)^2*.00161^2)/(1+X(3)^2*.00161) )-16.2 ) /16.2 )^2
1415 PN5=( ( ((X(1)^2+X(2)^2*.00209+X(4)^2*.00209^2)/(1+X(3)^2*.00209) )-22.2 ) /22.2 )^2
1416 PN6=( ( ( (X(1)^2+X(2)^2*.00348+X(4)^2*.00348^2)/(1+X(3)^2*.00348) )-24.02 ) /24.02 )^2
1417 PN7=( (( (X(1)^2+X(2)^2*.00525+X(4)^2*.00525^2)/(1+X(3)^2*.00525) )-31.32 ) /31.32 )^2
1488 P=-10000*(PN1+PN2+PN3+PN4+PN5+PN6+PN7)
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 4
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-318.6 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3)
1915 PRINT A(4),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 37 minutes of running is presented below. (What immediately follows is a manual copy from the computer screen.)

2.714010507796987 141.4974531034683 31.93520490677342
1738 -318.5943924629846 -31998

2.71426536308301 140.7310075994925 31.63039117713214
1716 -318.5734555283789 -31929

Interpreted in accordance with line 1912 and line 1915, the output through JJJJ=-31929 was produced in the first 37 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

Reference

K. Schittkowski (1987): "More Test Problems for Nonlinear Programming Codes," Springer-Verlag, Berlin, Heidelberg, New York.

A Computer Program for Nonlinear Programs with Big Integer Variables and Continuous Variables

Jsun Yui Wong

The computer program listed below seeks to solve the following problem, which is Problem 346 on page 167 of Schittkowski (1987) plus the additional restriction that X(3)= 0, 1, 2, 3,..., or 125.

Objective function:
Maximize:
(.0201/10000000#)*X(1)^4*X(2)*X(3)^2

Constraints:
675-X(1)^2*X(2)>=0
.419-(X(1)^2*X(3)^2)/10000000#>=0
0<=X(1)<=36
0<=X(2)<=5
X(3)= 0, 1, 2, 3,..., 125.

0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
93 A(1)=RND*36
94 A(2)=RND*5
95 A(3)=FIX(RND*126)
103 REM
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 3
131 X(K)=A(K)
132 NEXT K
811 IF RND<.99 THEN 903 ELSE 961
903 IF RND<1/2 THEN 911 ELSE 921
911 IF RND<.5 THEN X(1)=RND*36 ELSE X(1)=A(1)+(1-2*RND)*.00001*A(1)
915 GOTO 1151
921 IF RND>.5 THEN X(2)=RND*5 ELSE X(2)=A(2)+(1-2*RND)*.00001*A(2)
925 GOTO 1151
961 X(3)=FIX(RND*126)
1151 P1=675-X(1)^2*X(2)
1159 IF P1<0 THEN P1=P1 ELSE P1=0
1255 P2=.419-(X(1)^2*X(3)^2)/10000000#
1259 IF P2<0 THEN P2=P2 ELSE P2=0
1355 REM
1359 REM
1488 P=(.0201/10000000#)*X(1)^4*X(2)*X(3)^2-333333!*(ABS(P1)+ABS(P2))
1499 PR=(.0201/10000000#)*X(1)^4*X(2)*X(3)^2
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 3
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>5.684 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3)
1915 PRINT M,MM,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 25 seconds of running is presented below. (What immediately follows is a manual copy from the computer screen.)

17.34702385316216 2.24312654607115 118
5.684780970732687 5.684780970732687 -31938

28.8302667451177 .812093927315822 71
5.68477979947611 5.68477979947611 -31918

24.96279110460882 1.083221828698728 82
5.684780780297064 5.684780780297064 -31909

Interpreted in accordance with line 1912 and line 1915, the output through JJJJ=-31909 was produced in the first 25 seconds of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

Reference

K. Schittkowski (1987): "More Test Problems for Nonlinear Programming Codes," Springer-Verlag, Berlin Heidelberg New York.

A Computer Program for Solving Nonlinear Programs with Integer (Binary or Not Binary) Variables and Continuous Variables

Jsun Yui Wong

The computer program listed below seeks to solve the following problem from Kocis and Grossmann (1987).

Objective function:
Maximize:
X(3)-2*X(1)-X(2)

Constraints:
X(1)-2*EXP(-X(2))=0
-X(1)+X(2)+X(3)<=0
0.5<=X(1)<=1.4
X(3)= 0 or 1.

0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
93 A(1)=.5+RND*.9
94 A(2)=-10+RND*20
103 A(3)=FIX(RND*2)
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 3
131 X(K)=A(K)
132 NEXT K
144 IF RND<.99 THEN 234 ELSE 961
234 IF RND<.5 THEN X(2)=-10+RND*20 ELSE X(2)=A(2)+(1-2*RND)*.00001*A(2)
255 GOTO 971
961 X(3)=FIX(RND*2)
971 X(1)=2*EXP(-X(2))
1151 P1=-X(1)+X(2)+X(3)
1159 IF P1>0 THEN P1=P1 ELSE P1=0
1488 P=X(3)-2*X(1)-X(2)-333333!*(ABS(P1))
1499 PR=X(3)-2*X(1)-X(2)
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 3
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-2.125 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3)
1915 PRINT M,MM,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 3 seconds of running is presented below. (What immediately follows is a manual copy from the computer screen.)

1.374822583072051 .3748224882596145 1
-2.124467654403717 -2.124467654403717 -32000

1.374822568960346 .3748224985239971 1
-2.12446763644469 -2.12446763644469 -31999

1.374822568049993 .3748224991861579 1
-2.124467635286143 -2.124467635286143 -31996

Interpreted in accordance with line 1912 and line 1915, the output through JJJJ=-31996 was produced in the first 3 seconds of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

Reference

Kocis, G. R. and Grossmann, I. E. (1987) Relaxation Strategy for the Structural Optimization of Process Flowsheets. Ind. Eng. Chem. Res. 26, 1869-1880.

A General Integer Programming Computer Program Applied to a Problem from the Literature, Second Edition

Jsun Yui Wong

The computer program listed below seeks to solve the following problem from Floudas [1].

Objective function:
Maximize:
.7*X(3)-5*(X(1)-.5)^2-.8

Constraints:
0-EXP(X(1)-.2)-X(2)<=0
1+X(2)+1.1*X(3)<=0
-.2+X(1)-1.2*X(3)<=0
0.2<=X(1)<=1
-2.22554<=X(2)<=-1
X(3)= 0 or 1.

0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
93 A(1)=.6
94 A(2)=-1.61277
103 A(3)=FIX(RND*2)
126 IMAR=10+FIX(RND*10000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 3
131 X(K)=A(K)
132 NEXT K
811 IF RND<.99 THEN 903 ELSE 961
903 IF RND<1/2 THEN 911 ELSE 921
911 IF RND<.5 THEN X(1)=.2+.00001*FIX(RND*80001!) ELSE X(1)=A(1)+(1-2*RND)*.00001*A(1)
915 GOTO 1151
921 IF RND>.5 THEN X(2)=-2.22554+.00001*FIX(RND*122555!) ELSE X(2)=A(2)+(1-2*RND)*.00001*A(2)
925 GOTO 1151
961 X(3)=FIX(RND*2)
1151 P1=0-EXP(X(1)-.2)-X(2)
1159 IF P1>0 THEN P1=P1 ELSE P1=0
1255 P2=1+X(2)+1.1*X(3)
1259 IF P2>0 THEN P2=P2 ELSE P2=0
1355 P3=-.2+X(1)-1.2*X(3)
1359 IF P3>0 THEN P3=P3 ELSE P3=0
1488 P=.7*X(3)-5*(X(1)-.5)^2-.8-333333!*(ABS(P1)+ABS(P2)+ABS(P3))
1499 PR=.7*X(3)-5*(X(1)-.5)^2-.8
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 3
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-1.0766 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3)
1915 PRINT M,MM,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 2 minutes of running is presented below. (What immediately follows is a manual copy from the computer screen.)

.9419378029450955 -2.100000954313284 1
-1.076545132201548 -1.076545132201548 -31923

.9419425242361793 -2.100010855476669 1
-1.076565997483088 -1.076565997483088 -31920

.9419380545337351 -2.10000147577616 1
-1.076546244067171 -1.076546244067171 -31900

Interpreted in accordance with line 1912 and line 1915, the output through JJJJ=-31900 was produced in the first 2 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

Reference

[1] Floudas, C. A. (1995) Nonlinear and Mixed-Integer Optimization--Fundamentals and Applications. Oxford University Press, Oxford.

A General Integer Programming Computer Program Applied to a Problem from the Literature

Jsun Yui Wong

The computer program listed below seeks to solve the following problem from Floudas [1].

Objective function:
Maximize:
.7*X(3)-5*(X(1)-.5)^2-.8

Constraints:
0-EXP(X(1)-.2)-X(2)<=0
1+X(2)+1.1*X(3)<=0
-.2+X(1)-1.2*X(3)<=0
0.2<=X(1)<=1
-2.22554<=X(2)<=-1
X(3)= 0 or 1.

0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
93 A(1)=.6
94 A(2)=-1.61277
103 A(3)=FIX(RND*2)
126 IMAR=10+FIX(RND*10000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 3
131 X(K)=A(K)
132 NEXT K
811 IF RND<.99 THEN 903 ELSE 961
903 IF RND<1/2 THEN 911 ELSE 921
911 X(1)=.2+.00001*FIX(RND*80001!)
915 GOTO 1151
921 X(2)=-2.22554+.00001*FIX(RND*122555!)
925 GOTO 1151
961 X(3)=FIX(RND*2)
1151 P1=0-EXP(X(1)-.2)-X(2)
1159 IF P1>0 THEN P1=P1 ELSE P1=0
1255 P2=1+X(2)+1.1*X(3)
1259 IF P2>0 THEN P2=P2 ELSE P2=0
1355 P3=-.2+X(1)-1.2*X(3)
1359 IF P3>0 THEN P3=P3 ELSE P3=0
1488 P=.7*X(3)-5*(X(1)-.5)^2-.8-333333!*(ABS(P1)+ABS(P2)+ABS(P3))
1499 PR=.7*X(3)-5*(X(1)-.5)^2-.8
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 3
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-1.078 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3)
1915 PRINT M,MM,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 2.5 minutes of running is presented below. (What immediately follows is a manual copy from the computer screen.)

.9419499635696411 -2.100019931793213 1
-1.076598875337893 -1.076598875337893 -31978

.9421799778938294 -2.100460052490234 1
-1.077615688092795 -1.077615688092795 -31871

.9420099854469299 -2.100139856338501 1
-1.076864160015834 -1.076864160015834 -31729

Interpreted in accordance with line 1912 and line 1915, the output through JJJJ=-31729 was produced in the first 2.5 minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

Reference

[1] Floudas, C. A. (1995) Nonlinear and Mixed-Integer Optimization--Fundamentals and Applications. Oxford University Press, Oxford.

A General Integer Nonlinear Programming Computer Program Applied to a Quadratic Capital Budgeting Problem

Jsun Yui Wong

The computer program listed below seeks to solve the following quadratic capital budgeting problem.

Objective function:
Maximize:
-(X(1)+2*X(2)+3*X(3)-X(4))*(2*X(1)+5*X(2)+3*X(3)-6*X(4))

Constraints:
-4+X(1)+2*X(2)+X(3)+3*X(4)>=4
X(j)=0, 1
j=1, 2, 3, 4.

This problem is Example 2 of Kocis and Grossmann [1, p. 1410].

0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
101 FOR KK=1 TO 4
103 A(KK)=FIX(RND*2)
106 NEXT KK
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 4
131 X(K)=A(K)
132 NEXT K
951 IJL2=1+FIX(RND*4)
961 X(IJL2)=FIX(RND*2)
1151 P1=-4+X(1)+2*X(2)+X(3)+3*X(4)
1159 IF P1<0 THEN P1=P1 ELSE P1=0
1488 P=-(X(1)+2*X(2)+3*X(3)-X(4))*(2*X(1)+5*X(2)+3*X(3)-6*X(4))-333333!*ABS(P1)
1499 PR=-(X(1)+2*X(2)+3*X(3)-X(4))*(2*X(1)+5*X(2)+3*X(3)-6*X(4))
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 4
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>0 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4)
1915 PRINT M,MM,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 2 seconds of running is presented below. (What immediately follows is a manual copy from the computer screen.)

0 1 0 1
1 1 -32000

0 1 0 1
1 1 -31999

0 0 1 1
6 6 -31998

0 1 0 1
1 1 -31997

0 1 0 1
1 1 -31996

0 1 0 1
1 1 -31995

0 0 1 1
6 6 -31994

0 0 1 1
6 6 -31993

Interpreted in accordance with line 1912 and line 1915, the output through JJJJ=-31993 was produced in the first 2 seconds of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

Reference

[1] Kocis, G. R.; Grossmann, I. E. Global Optimization of Nonconvex Mixed-Integer Nonlinear Programming (MINLP) Problems in Process Synthesis. Ind. Eng. Chem. Res. 1988, 27, 1407-1421.

An Application of a General Integer Nonlinear Programming Computer Program

Jsun Yui Wong

The computer program listed below seeks to solve Problem 9 of Lawler and Bell [1, p. 1108].

0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
91 FOR K=1 TO 8
93 A(K)=FIX(RND*8)
99 NEXT K
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 8
131 X(K)=A(K)
132 NEXT K
811 IF RND<1/8 THEN 901 ELSE IF RND<2/8 THEN 911 ELSE IF RND<3/8 THEN 921 ELSE IF RND<4/8 THEN 931 ELSE IF RND<5/8 THEN 941 ELSE IF RND<6/8 THEN 951 ELSE IF RND<7/8 THEN 961 ELSE 971
901 X(1)=FIX(RND*8)
905 GOTO 1151
911 X(2)=FIX(RND*16)
915 GOTO 1151
921 X(3)=FIX(RND*8)
925 GOTO 1151
931 X(4)=FIX(RND*8)
935 GOTO 1151
941 X(5)=FIX(RND*16)
945 GOTO 1151
951 X(6)=FIX(RND*8)
955 GOTO 1151
961 X(7)=FIX(RND*16)
965 GOTO 1151
971 X(8)=FIX(RND*8)
1151 P1=-12+2*X(1)+2*X(4)+8*X(8)
1159 IF P1<0 THEN P1=P1 ELSE P1=0
1255 P2=-41+11*X(1)+7*X(4)+13*X(6)
1259 IF P2<0 THEN P2=P2 ELSE P2=0
1355 P3=-60+6*X(2)+9*X(4)*X(6)+5*X(7)
1359 IF P3<0 THEN P3=P3 ELSE P3=0
1455 P4=-42+3*X(2)+5*X(5)+7*X(8)
1459 IF P4<0 THEN P4=P4 ELSE P4=0
1462 P5=-53+6*X(2)*X(7)+9*X(3)+5*X(5)
1469 IF P5<0 THEN P5=P5 ELSE P5=0
1472 P6=-13+4*X(3)*X(7)+X(5)
1479 IF P6<0 THEN P6=P6 ELSE P6=0
1480 P7=-69+2*X(1)+4*X(2)+7*X(4)+3*X(5)+X(7)
1481 IF P7>0 THEN P7=P7 ELSE P7=0
1482 P8=-47+9*X(1)*X(8)+6*X(3)*X(5)+4*X(3)*X(7)
1483 IF P8>0 THEN P8=P8 ELSE P8=0
1484 P9=-73+12*X(2)+8*X(2)*X(8)+2*X(3)*X(6)
1485 IF P9>0 THEN P9=P9 ELSE P9=0
1486 P10=-31+1*X(3)+4*X(5)+2*X(6)+9*X(8)
1487 IF P10>0 THEN P10=P10 ELSE P10=0
1488 P=-X(1)-X(2)-X(3)-X(4)-X(5)-X(6)-X(7)-X(8)-333333!*(ABS(P1)+ABS(P2)+ABS(P3)+ABS(P4)+ABS(P5)+ABS(P6)+ABS(P7)+ABS(P8)+ABS(P9)+ABS(P10))
1499 PR=-X(1)-X(2)-X(3)-X(4)-X(5)-X(6)-X(7)-X(8)
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 8
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-999 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8)
1915 PRINT M,MM,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 20 seconds of running is presented below. (What immediately follows is a manual copy from the computer screen.)

3 4 1 3 6
1 2 0
-20 -20 -31893

3 4 1 3 6
1 2 0
-20 -20 -31868

3 4 1 3 6
1 2 0
-20 -20 -31839

5 4 1 1 6
3 2 0
-22 -22 -31834

2 4 1 4 6
1 2 0
-20 -20 -31814

Interpreted in accordance with line 1912, line 1913, and line 1915, the output through JJJJ=-31814--with two alternative optima at JJJJ=-31893 and at JJJJ=-31814--was produced in the first 20 seconds of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

Reference

[1] E. L Lawler, M. D. Bell, "A Method for Solving Discrete Optimization Problems," Operations Research 14, 1098-1112 (1966).

A General Integer Nonlinear Programming Computer Program Applied to an Example from Capital Budgeting

Jsun Yui Wong

The computer program listed below seeks to solve the investment problem on page B-55 of Mao and Wallingford [1].

0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
91 FOR K=1 TO 8
93 A(K)=FIX(RND*2)
99 NEXT K
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 8
131 X(K)=A(K)
132 NEXT K
151 IAP=1+FIX(RND*8)
155 X(IAP)=FIX(RND*2)
1151 P1=-100+7*X(1)+35*X(2)+20*X(3)+12*X(4)+65*X(5)+60*X(6)+20*X(7)+5*X(8)
1159 IF P1>0 THEN P1=P1 ELSE P1=0
1255 P2=-70+5*X(1)+15*X(2)+30*X(3)+10*X(4)+7*X(5)+15*X(6)+50*X(7)+7*X(8)
1259 IF P2>0 THEN P2=P2 ELSE P2=0
1355 P3=-30+5*X(1)+12*X(2)+2*X(3)+10*X(4)+4*X(5)+2*X(6)+10*X(7)+7*X(8)
1359 IF P3>0 THEN P3=P3 ELSE P3=0
1455 P4=-15+5*X(1)+4*X(2)+0*X(3)+10*X(4)+4*X(5)+2*X(6)+5*X(7)+7*X(8)
1459 IF P4>0 THEN P4=P4 ELSE P4=0
1462 P5=-15+5*X(1)+4*X(2)+0*X(3)+6*X(4)+4*X(5)+2*X(6)+0*X(7)+7*X(8)
1469 IF P5>0 THEN P5=P5 ELSE P5=0
1472 P6=-15+2*X(1)+4*X(2)+8*X(3)+3*X(4)+4*X(5)+2*X(6)+0*X(7)+7*X(8)
1479 IF P6>0 THEN P6=P6 ELSE P6=0
1480 P7=X(1)-X(4)
1481 IF P7>0 THEN P7=P7 ELSE P7=0
1482 P8=-1+X(1)+X(2)+X(3)
1483 IF P8>0 THEN P8=P8 ELSE P8=0
1484 P9=-1+X(4)+X(5)+X(6)
1485 IF P9>0 THEN P9=P9 ELSE P9=0
1486 P10=-1+X(7)+X(8)
1487 IF P10>0 THEN P10=P10 ELSE P10=0
1491 P11=-1+X(1)+X(2)+X(3)
1492 IF P11<0 THEN P11=P11 ELSE P11=0
1495 P12=-1+X(4)+X(5)+X(6)
1496 IF P12<0 THEN P12=P12 ELSE P12=0
1498 P13=-1+X(7)+X(8)
1499 IF P13<0 THEN P13=P13 ELSE P13=0
1511 P=757*X(1)+825*X(2)+987*X(3)+350*X(4)+596*X(5)+650*X(6)+1420*X(7)+1425*X(8)-333333!*(ABS(P1)+ABS(P2)+ABS(P3)+ABS(P4)+ABS(P5)+ABS(P6)+ABS(P7)+ABS(P8)+ABS(P9)+ABS(P10)+ABS(P11)+ABS(P12)+ABS(P13))
1522 PR=757*X(1)+825*X(2)+987*X(3)+350*X(4)+596*X(5)+650*X(6)+1420*X(7)+1425*X(8)
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 8
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-999 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8)
1915 PRINT M,MM,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 2 seconds of running is presented below. (What immediately follows is a manual copy from the computer screen.)

0 1 0 0 0
1 0 1
2900 2900 -31996

0 1 0 0 0
1 0 1
2900 2900 -31995

Interpreted in accordance with line 1912, line 1913, and line 1915, the output through JJJJ=-31995 was produced in the first 2 seconds of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

Reference

[1] James C. T. Mao and B. A. Wallingford, "An Extension of Lawler and Bell's Method of Discrete Optimization with Examples from Capital Budgeting," Management Science 15, No. 2, Application Series, B51-B60 (Oct., 1968).

A Computer Program for Solving Discrete Optimization Problems

Jsun Yui Wong

The computer program listed below seeks to solve Problem 7 of Lawler and Bell [1, pp. 1107-1108].

0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
91 FOR K=1 TO 8
93 A(K)=FIX(RND*8)
99 NEXT K
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 8
131 X(K)=A(K)
132 NEXT K
811 IF RND<1/8 THEN 901 ELSE IF RND<2/8 THEN 911 ELSE IF RND<3/8 THEN 921 ELSE IF RND<4/8 THEN 931 ELSE IF RND<5/8 THEN 941 ELSE IF RND<6/8 THEN 951 ELSE IF RND<7/8 THEN 961 ELSE 971
901 X(1)=FIX(RND*8)
905 GOTO 1151
911 X(2)=FIX(RND*16)
915 GOTO 1151
921 X(3)=FIX(RND*8)
925 GOTO 1151
931 X(4)=FIX(RND*8)
935 GOTO 1151
941 X(5)=FIX(RND*16)
945 GOTO 1151
951 X(6)=FIX(RND*8)
955 GOTO 1151
961 X(7)=FIX(RND*16)
965 GOTO 1151
971 X(8)=FIX(RND*8)
1151 P1=-12+2*X(1)+2*X(4)+8*X(8)
1159 IF P1<0 THEN P1=P1 ELSE P1=0
1255 P2=-41+11*X(1)+7*X(4)+13*X(6)
1259 IF P2<0 THEN P2=P2 ELSE P2=0
1355 P3=-60+6*X(2)+9*X(4)*X(6)+5*X(7)
1359 IF P3<0 THEN P3=P3 ELSE P3=0
1455 P4=-42+3*X(2)+5*X(5)+7*X(8)
1459 IF P4<0 THEN P4=P4 ELSE P4=0
1462 P5=-53+6*X(2)*X(7)+9*X(3)+5*X(5)
1469 IF P5<0 THEN P5=P5 ELSE P5=0
1472 P6=-13+4*X(3)*X(7)+X(5)
1479 IF P6<0 THEN P6=P6 ELSE P6=0
1480 P7=-69+2*X(1)+4*X(2)+7*X(4)+3*X(5)+X(7)
1481 IF P7>0 THEN P7=P7 ELSE P7=0
1482 P8=-47+9*X(1)*X(8)+6*X(3)*X(5)+4*X(3)*X(7)
1483 IF P8>0 THEN P8=P8 ELSE P8=0
1484 P9=-73+12*X(2)+8*X(2)*X(8)+2*X(3)*X(6)
1485 IF P9>0 THEN P9=P9 ELSE P9=0
1486 P10=-31+1*X(3)+4*X(5)+2*X(6)+9*X(8)
1487 IF P10>0 THEN P10=P10 ELSE P10=0
1488 P=-3*X(1)*X(4)-X(2)-X(2)*X(5)-X(2)*X(7)-6*X(3)*X(8)-X(5)*X(7)-11*X(6)-333333!*(ABS(P1)+ABS(P2)+ABS(P3)+ABS(P4)+ABS(P5)+ABS(P6)+ABS(P7)+ABS(P8)+ABS(P9)+ABS(P10))
1499 PR=-3*X(1)*X(4)-X(2)-X(2)*X(5)-X(2)*X(7)-6*X(3)*X(8)-X(5)*X(7)-11*X(6)
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 8
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-999 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8)
1915 PRINT M,MM,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 8 seconds of running is presented below. (What immediately follows is a manual copy from the computer screen.)

4 4 1 2 6
2 2 0
-94 -94 -31968

2 4 1 4 6
1 2 0
-83 -83 -31939

Interpreted in accordance with line 1912, line 1914, and line 1915, the output through JJJJ=-31939 was produced in the first 8 seconds of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

Reference

[1] E. L. Lawler, M. D. Bell, "A Method for Solving Discrete Optimization Problems," Operations Research 14, 1098-1112 (1965).

An Application of An Integer Nonlinear Programming Computer Program

Jsun Yui Wong

The computer program listed below seeks to solve Problem 8 of Lawler and Bell [1, p. 1108].

0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
91 FOR K=1 TO 8
93 A(K)=FIX(RND*8)
99 NEXT K
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 8
131 X(K)=A(K)
132 NEXT K
811 IF RND<1/8 THEN 901 ELSE IF RND<2/8 THEN 911 ELSE IF RND<3/8 THEN 921 ELSE IF RND<4/8 THEN 931 ELSE IF RND<5/8 THEN 941 ELSE IF RND<6/8 THEN 951 ELSE IF RND<7/8 THEN 961 ELSE 971
901 X(1)=FIX(RND*8)
905 GOTO 1151
911 X(2)=FIX(RND*16)
915 GOTO 1151
921 X(3)=FIX(RND*8)
925 GOTO 1151
931 X(4)=FIX(RND*8)
935 GOTO 1151
941 X(5)=FIX(RND*16)
945 GOTO 1151
951 X(6)=FIX(RND*8)
955 GOTO 1151
961 X(7)=FIX(RND*16)
965 GOTO 1151
971 X(8)=FIX(RND*8)
1151 P1=-12+2*X(1)+2*X(4)+8*X(8)
1159 IF P1<0 THEN P1=P1 ELSE P1=0
1255 P2=-41+11*X(1)+7*X(4)+13*X(6)
1259 IF P2<0 THEN P2=P2 ELSE P2=0
1355 P3=-60+6*X(2)+9*X(4)*X(6)+5*X(7)
1359 IF P3<0 THEN P3=P3 ELSE P3=0
1455 P4=-42+3*X(2)+5*X(5)+7*X(8)
1459 IF P4<0 THEN P4=P4 ELSE P4=0
1462 P5=-53+6*X(2)*X(7)+9*X(3)+5*X(5)
1469 IF P5<0 THEN P5=P5 ELSE P5=0
1472 P6=-13+4*X(3)*X(7)+X(5)
1479 IF P6<0 THEN P6=P6 ELSE P6=0
1480 P7=-69+2*X(1)+4*X(2)+7*X(4)+3*X(5)+X(7)
1481 IF P7>0 THEN P7=P7 ELSE P7=0
1482 P8=-47+9*X(1)*X(8)+6*X(3)*X(5)+4*X(3)*X(7)
1483 IF P8>0 THEN P8=P8 ELSE P8=0
1484 P9=-73+12*X(2)+8*X(2)*X(8)+2*X(3)*X(6)
1485 IF P9>0 THEN P9=P9 ELSE P9=0
1486 P10=-31+1*X(3)+4*X(5)+2*X(6)+9*X(8)
1487 IF P10>0 THEN P10=P10 ELSE P10=0
1488 P=-X(1)^2-X(2)^2-X(3)^2-X(4)^2-X(5)^2-X(6)^2-X(7)^2-X(8)^2-333333!*(ABS(P1)+ABS(P2)+ABS(P3)+ABS(P4)+ABS(P5)+ABS(P6)+ABS(P7)+ABS(P8)+ABS(P9)+ABS(P10))
1499 PR=-X(1)^2-X(2)^2-X(3)^2-X(4)^2-X(5)^2-X(6)^2-X(7)^2-X(8)^2
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 8
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-999 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8)
1915 PRINT M,MM,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 14 seconds of running is presented below. (What immediately follows is a manual copy from the computer screen.)

3 4 1 3 6
1 2 0
-76 -76 -31893

Interpreted in accordance with line 1912, line 1913, and line 1915, the output through JJJJ=-31893 was produced in the first 14 seconds of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

Reference

[1] E. L. Lawler, M. D. Bell, "A Method for Solving Discrete Optimization Problems," Operations Research 14, 1098-1112 (1966).

An Application of an Integer Nonlinear Programming Computer Program

Jsun Yui Wong

The computer program listed below seeks to solve Problem 10 of Lawler and Bell [1, p. 1108].

0 DEFDBL A-Z
3 DEFINT I,J,K
4 DIM X(42),A(42),L(33),K(33)
5 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
91 FOR K=1 TO 8
93 A(K)=FIX(RND*8)
99 NEXT K
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 8
131 X(K)=A(K)
132 NEXT K
811 IF RND<1/8 THEN 901 ELSE IF RND<2/8 THEN 911 ELSE IF RND<3/8 THEN 921 ELSE IF RND<4/8 THEN 931 ELSE IF RND<5/8 THEN 941 ELSE IF RND<6/8 THEN 951 ELSE IF RND<7/8 THEN 961 ELSE 971
901 X(1)=FIX(RND*8)
905 GOTO 1151
911 X(2)=FIX(RND*16)
915 GOTO 1151
921 X(3)=FIX(RND*8)
925 GOTO 1151
931 X(4)=FIX(RND*8)
935 GOTO 1151
941 X(5)=FIX(RND*16)
945 GOTO 1151
951 X(6)=FIX(RND*8)
955 GOTO 1151
961 X(7)=FIX(RND*16)
965 GOTO 1151
971 X(8)=FIX(RND*8)
1151 P1=-12+2*X(1)+2*X(4)+8*X(8)
1159 IF P1<0 THEN P1=P1 ELSE P1=0
1255 P2=-41+11*X(1)+7*X(4)+13*X(6)
1259 IF P2<0 THEN P2=P2 ELSE P2=0
1355 P3=-60+6*X(2)+9*X(4)*X(6)+5*X(7)
1359 IF P3<0 THEN P3=P3 ELSE P3=0
1455 P4=-42+3*X(2)+5*X(5)+7*X(8)
1459 IF P4<0 THEN P4=P4 ELSE P4=0
1462 P5=-53+6*X(2)*X(7)+9*X(3)+5*X(5)
1469 IF P5<0 THEN P5=P5 ELSE P5=0
1472 P6=-13+4*X(3)*X(7)+X(5)
1479 IF P6<0 THEN P6=P6 ELSE P6=0
1480 P7=-69+2*X(1)+4*X(2)+7*X(4)+3*X(5)+X(7)
1481 IF P7>0 THEN P7=P7 ELSE P7=0
1482 P8=-47+9*X(1)*X(8)+6*X(3)*X(5)+4*X(3)*X(7)
1483 IF P8>0 THEN P8=P8 ELSE P8=0
1484 P9=-73+12*X(2)+8*X(2)*X(8)+2*X(3)*X(6)
1485 IF P9>0 THEN P9=P9 ELSE P9=0
1486 P10=-31+1*X(3)+4*X(5)+2*X(6)+9*X(8)
1487 IF P10>0 THEN P10=P10 ELSE P10=0
1488 P=-X(1)*X(2)*X(3)-X(1)*X(4)*X(5)-X(2)*X(4)*X(6)-X(2)*X(5)*X(7)-X(6)*X(7)*X(8)-333333!*(ABS(P1)+ABS(P2)+ABS(P3)+ABS(P4)+ABS(P5)+ABS(P6)+ABS(P7)+ABS(P8)+ABS(P9)+ABS(P10))
1499 PR=-X(1)*X(2)*X(3)-X(1)*X(4)*X(5)-X(2)*X(4)*X(6)-X(2)*X(5)*X(7)-X(6)*X(7)*X(8)
1551 IF P<=M THEN 1670
1657 FOR KEW=1 TO 8
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 MM=PR
1666 GOTO 128
1670 NEXT I
1890 IF M>-111 THEN 1912 ELSE 1999
1912 PRINT A(1),A(2),A(3),A(4),A(5)
1913 PRINT A(6),A(7),A(8)
1915 PRINT M,MM,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with the IBM basica/D interpreter, and the output produced in the first 14 seconds of running is presented below. (What immediately follows is a manual copy from the computer screen.)

5 4 1 1 6
3 2 0
-110 -110 -31876

Interpreted in accordance with line 1912, line 1913, and line 1915, the output through JJJJ=-31876 was produced in the first 14 seconds of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

Reference

[1] E. L. Lawler, M. D. Bell, "A Method for Solving Discrete Optimization Problems," Operations Research 14, 1098-1112 (1966).