Jsun Yui Wong
"These tests suggest that LB1 is adequate for problems with up to 35 departments. For larger problems, the linear programs become too large and too difficult to solve with the currently available LP solvers" (Amaral 2009). "Our computational results suggest that this approach can routinely obtain optimal layouts for SRFLPs with up to 25 facilities in a few hours, and in several dozen hours for SRFLPs with up to 30 facilities" (Anjos and Vannelli 2008).
This paper is concerned with the ordering problem of Simmons (1969). Specifically, the computer program listed below tries to solve a case with eighty departments/facilities. The half lengths of the eighty departments are shown in line 11 through line 20; these half lengths are used in line 1335.
The flows are shown in line 684 through line 1005. These flows were not chosen scientifically. These flows are not random mainly because line 991 is repeated 14 times; line 991 by itself is more random than that. The other flows and some flows of line 991 were obtained from Nugent et al. (1968; all of the flows from the n=20 case and from the n=30 case) and from Skorin-Kapov (1990; all of the flows from the 42-department/facility case). Not all of the flows in line 1005 are needed.
The following computer program is a heuristic procedure. To be within .1% of the unknown optimal objective function value is the research goal. The present strategy is to use the multi-computer method that uses a number of personal computers running simultaneously and independently. To save human labor, each computer runs a very slightly different computer program. For example, if there are three computers, one computer can run with 1126 IMAR=10+RND*5000, the second can run with 1126 IMAR=10+RND*6000, and the third can run with 1126 IMAR=10+RND*7000. Otherwise the three computer programs are the same. This method is illustrated below.
0 DEFINT A-Z
1 DEFSNG S,M
2 DIM X(82),A(82)
4 DIM HS(82,82),HR(82),MP(82,82)
5 FOR IZ=1 TO 80
6 REM
7 READ HR(IZ)
8 REM
9 NEXT IZ
10 REM
11 DATA 10,10,10,10,10,10,10,10,10,10
12 DATA 20,20,20,20,20,20,20,20,20,20
13 DATA 20,20,20,20,20,20,20,20,20,20
14 DATA 20,20,20,20,20,20,20,20,20,20
15 DATA 20,20,20,20,20,20,20,20,20,20
16 DATA 20,20,20,20,20,20,20,20,20,20
17 DATA 20,20,20,20,20,20,20,20,20,20
20 DATA 30,30,30,30,30,30,30,30,30,30
679 FOR IZ=1 TO 79
680 FOR JZ=IZ+1 TO 80
681 READ HS(IZ,JZ)
682 NEXT JZ
683 NEXT IZ
684 DATA 0,5,0,5,2,10,3,1,5,5,5,0,0,5,4,4,0,0,1
685 DATA 3,10,5,1,5,1,2,4,2,5,0,10,10,3,0,5,10,5
686 DATA 2,0,5,2,4,4,5,0,0,0,5,1,0,0,5,0,0
687 DATA 1,0,5,2,1,0,10,2,2,0,2,1,5,2,5,5
688 DATA 5,6,5,2,5,2,0,5,1,1,1,5,2,5,1
689 DATA 5,2,1,6,0,0,10,0,2,0,1,0,1,5
690 DATA 0,0,0,5,10,2,2,5,1,2,1,0,10
691 DATA 1,1,10,10,2,0,10,2,5,2,2,10
692 DATA 2,0,3,5,5,0,5,0,0,0,2
693 DATA 5,5,0,5,1,0,0,5,5,2
694 DATA 5,2,5,1,10,0,2,2,5
695 DATA 2,10,5,0,1,1,2,5
696 DATA 2,2,1,0,0,0,5
697 DATA 5,5,1,5,5,0
698 DATA 3,0,5,10,10
699 DATA 0,0,2,0
700 DATA 5,2,0
701 DATA 1,1
702 DATA 6
784 DATA 2,10,5,4,1,5,6,5,0,2,0,0,1,2,5,0,5,0,2,5,5,0,10,0,1,4,2,0,0,0,2,0,5,5,0,10,10,0,0,0,2
785 DATA 1,0,5,1,0,0,0,2,1,0,5,10,0,1,0,10,10,0,2,1,1,0,0,3,5,10,0,5,0,2,1,1,3,10,5,0,10,0,1,4
786 DATA 0,1,5,10,0,0,1,0,5,0,3,2,5,1,5,0,1,1,1,5,1,2,2,0,1,1,5,2,6,1,1,0,10,5,10,5,5,2,1
787 DATA 0,1,0,0,10,2,1,2,5,5,5,5,0,2,2,6,5,5,0,5,2,1,0,0,1,2,3,2,10,5,4,0,0,2,10,3,0,5
788 DATA 1,6,1,1,0,0,6,0,0,2,2,2,3,5,0,2,2,2,0,5,5,5,0,1,5,0,4,2,2,1,5,6,2,2,0,5,5
789 DATA 0,5,1,5,1,0,0,0,1,0,0,0,1,0,0,1,2,5,5,1,2,1,10,0,0,0,2,5,0,10,5,4,5,5,2,5
790 DATA 0,5,4,10,10,2,0,2,5,10,0,4,5,6,4,0,2,1,2,1,2,2,0,2,3,2,5,0,0,0,0,1,1,6,1
791 DATA 0,1,5,2,0,0,2,2,0,2,0,0,4,0,0,2,5,3,2,2,5,2,2,2,5,0,2,5,2,2,0,5,1,3
792 DATA 5,0,5,4,2,10,5,0,2,2,1,2,0,0,6,1,5,0,0,0,0,5,10,10,3,5,1,2,0,0,10,1,6
793 DATA 1,2,5,3,2,5,5,5,10,0,0,1,2,4,0,0,5,0,3,2,5,0,0,1,5,2,0,1,5,2,0,10
794 DATA 5,2,5,0,2,1,2,0,2,0,5,2,5,1,4,0,1,10,3,5,5,0,5,2,0,0,0,5,0,0,5
795 DATA 1,0,0,0,10,2,4,5,0,0,0,0,1,10,5,1,1,5,5,2,1,5,10,5,3,5,5,1,5,5
796 DATA 0,0,0,3,0,5,6,0,5,2,1,1,5,2,1,0,0,10,5,5,2,2,5,1,1,0,1,0,0
797 DATA 10,2,5,1,5,5,2,2,0,0,1,2,0,5,2,4,5,10,4,0,10,2,10,1,2,5,4,1
798 DATA 0,6,0,1,2,0,2,0,0,0,5,5,2,5,0,5,1,5,1,5,0,5,5,2,10,5,5
799 DATA 2,0,5,5,2,0,4,0,0,0,0,0,2,2,0,0,5,2,0,5,1,0,5,0,2,0
800 DATA 0,0,5,1,1,0,3,5,0,2,1,5,1,5,6,0,3,5,0,5,0,0,5,5,10
801 DATA 5,5,0,0,2,2,6,10,0,2,0,2,2,10,2,0,5,1,0,6,3,4,5,5
802 DATA 1,0,0,0,3,2,10,4,5,5,2,5,1,1,2,5,0,0,10,3,2,1,10
803 DATA 3,1,2,0,2,10,10,5,2,1,2,1,0,10,2,5,0,5,0,4,0,2
804 DATA 0,2,0,4,4,1,1,0,5,1,5,10,1,0,0,5,10,10,4,5,2
805 DATA 5,5,2,5,2,10,0,2,0,2,4,0,2,5,5,2,2,2,5,0
806 DATA 2,0,2,0,2,0,5,2,0,2,1,5,10,6,1,5,2,0,0
807 DATA 2,10,0,2,0,0,5,3,5,2,0,10,10,3,0,2,1,0
808 DATA 1,4,0,5,4,1,0,2,2,1,1,0,4,0,3,5,5
809 DATA 2,10,5,0,1,5,0,0,10,2,5,0,0,0,0,1
810 DATA 2,0,2,3,0,5,0,3,2,0,2,10,0,1,2
811 DATA 3,2,5,0,10,2,0,5,5,2,1,0,0,0
812 DATA 0,0,0,3,6,5,0,5,2,1,5,0,2
813 DATA 1,0,5,4,10,5,1,0,10,5,0,3
814 DATA 2,0,5,2,0,2,0,10,3,0,0
815 DATA 2,4,1,2,0,0,2,2,0,6,2,5,0,0,0,2,2,0,0,2,1,0,10,0,0,1,10,5,2,0,2,1,0,0,0,2,5,0,3,5,10,10,5,0,1,2,10,0,0,1,0,4,2,1,5
954 DATA 3,2,0,0,2,10,5,0,5,2,5,0,0,2,0,5,6,3,0,1,10,0,10,2,1,1,1,0,1
955 DATA 4,0,10,4,0,0,2,2,1,0,5,0,0,0,0,2,0,1,6,1,0,1,2,2,5,1,10,5
956 DATA 3,4,0,5,5,5,1,4,1,0,4,0,4,0,6,3,2,5,5,2,1,0,0,3,1,0,2
957 DATA 0,0,0,2,2,0,6,0,2,5,2,5,1,1,1,1,2,2,4,0,2,0,2,2,5,5
958 DATA 5,2,0,0,0,0,2,0,0,0,0,2,1,0,0,2,0,5,1,0,2,1,0,2,1
959 DATA 1,2,2,1,4,10,10,2,5,5,0,5,0,0,0,10,0,0,0,4,0,10,1,1
960 DATA 10,10,5,10,10,6,0,0,10,2,1,10,1,5,5,2,3,5,0,2,0,1,3
961 DATA 1,3,5,0,0,0,2,4,5,2,10,6,0,5,5,2,5,0,5,5,0,2
962 DATA 10,2,1,5,2,0,3,0,2,0,0,4,0,5,2,0,5,2,2,5,2
963 DATA 5,5,6,0,1,5,5,0,5,2,3,5,0,5,2,10,10,1,5,2
964 DATA 0,0,1,2,1,0,2,0,0,0,6,6,0,4,5,3,2,2,10
965 DATA 5,5,2,0,0,0,0,2,0,4,5,10,1,0,0,0,0,1
966 DATA 2,0,4,2,2,1,0,6,2,1,5,5,0,0,1,5,5
967 DATA 2,1,0,5,3,10,0,0,4,2,0,0,4,2,5,5,4,5,1,0,1,0,5,0,2,0,0,5,1,1,0,0,3,0,2,2,0,2,0,5,0,5,2,5,10,2,2,0,0,0,6,5,3,5,0,0,5,1
968 DATA 5,1,2,10,10,4,0,0,5,0,0,0,0,5,5,1,0,5,2,1,2,10,10
969 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2
991 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
992 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
993 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
994 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
995 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
996 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
997 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
998 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
999 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1000 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1001 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1002 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1003 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1004 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1005 DATA 5,2,1,3,1,5,6,5,5,3,4,0,1,0,0,0,5,0,0,5,0,4,4,5,0,2,5,0,4,4,1,0,2,2,5,5,0,1,0,0,1,0,10,1,0,0,0,0,0,0,0,10,2,2,2,10,6,3,2,5,2,6,3,5,4,4,2,1,1,4,5,3,2,2,3,1,4,5,6,2,2,3,1,0,3,0,5,2,1,3,4,5,2,6,5,1,0,0,2,10,5,3,1,5,4,6,3,2,5,0,0,0,5
1118 FOR JJJJ=-32000 TO 32000
1119 RANDOMIZE JJJJ
1120 M=-9999999999999999#
1121 FOR ZI=1 TO 80
1122 A(ZI)=RND*10000
1123 NEXT ZI
1126 IMAR=10+RND*5000
1128 FOR I=1 TO IMAR
1129 FOR KK=1 TO 80
1131 X(KK)=A(KK)
1132 NEXT KK
1223 IJL=1+FIX(RND*80)
1255 IF RND<.9 THEN X(IJL)=RND*10000 ELSE X(IJL)=A(IJL)+1
1332 FOR IM1=1 TO 79
1334 FOR IM2=IM1+1 TO 80
1335 IF ABS(X(IM1)-X(IM2))<(HR(IM1)+HR(IM2)) THEN MP(IM1,IM2)=-9999999999# ELSE MP(IM1,IM2)=0
1338 NEXT IM2
1339 NEXT IM1
1431 SUMNL=0
1432 FOR IN1=1 TO 79
1434 FOR IN2=IN1+1 TO 80
1437 SUMNL=SUMNL+MP(IN1,IN2)
1438 NEXT IN2
1439 NEXT IN1
1631 SUMUL=0
1632 FOR IS1=1 TO 79
1634 FOR IS2=IS1+1 TO 80
1637 SUMUL=SUMUL+HS(IS1,IS2)*ABS(X(IS1)-X(IS2))
1638 NEXT IS2
1639 NEXT IS1
1646 SP=-SUMUL+SUMNL
1656 IF SP<=M THEN 1670
1657 FOR KEW=1 TO 80
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=SP
1666 GOTO 1128
1670 NEXT I
1890 IF M>-9999999! 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)
1916 PRINT A(21),A(22),A(23),A(24),A(25)
1917 PRINT A(26),A(27),A(28),A(29),A(30)
1918 PRINT A(31),A(32),A(33),A(34),A(35)
1919 PRINT A(36),A(37),A(38),A(39),A(40)
1920 PRINT A(41),A(42),A(43),A(44),A(45)
1921 PRINT A(46),A(47),A(48),A(49),A(50)
1922 PRINT A(51),A(52),A(53),A(54),A(55)
1923 PRINT A(56),A(57),A(58),A(59),A(60)
1924 PRINT A(61),A(62),A(63),A(64),A(65)
1925 PRINT A(66),A(67),A(68),A(69),A(70)
1926 PRINT A(71),A(72),A(73),A(74),A(75)
1927 PRINT A(76),A(77),A(78),A(79),A(80)
1959 PRINT M,JJJJ
1999 NEXT JJJJ
The BASIC computer program above was run with Microsoft's GW BASIC 3.11 interpreter, which is not a compiler. The candidate solution with the best objective function value produced during the first thirty hours of running is presented immediately below. What follows is a manual copy from the computer monitor.
4769 4224 4064 4124 4704
4553 4284 4971 3824 4452
5241 3794 3974 5142 5866
5780 4583 3334 6020 5013
4094 5284 3414 4625 2994
4417 3294 4891 5498 3134
5821 3894 3454 4334 4932
2894 5907 4522 3214 5689
4154 5324 5059 4374 4254
3374 2854 5186 5582 3534
3854 4738 5539 3934 3614
5101 5735 4799 3174 3034
4839 4194 3254 3494 4482
3694 3654 4668 3574 5432
2740 2804 3084 2944 3744
5382 5963 6070 5632 4024
-8734049 -31990
One can check the solution/result at JJJJ=-31990 to see whether there is a gap between any two adjacent facilities. If there is, then joining the two adjacent facilities together will make the actual cost of this order to be less than 8734049. There are gaps in the sequence above.
The best candidate solution from the computer running with 1126 IMAR=10+RND*6000 has the objective function value of 8859337 at JJJJ=-31996.
The best candidate solution from the computer running with 1126 IMAR=10+RND*7000 has the objective function value of 8827945 at JJJJ=-31998.
Interpreted in accordance with line 1912 through line 1959, the candidate solutions above were produced during the first thirty hours of simultaneous running on three personal computers each with the speed of about 2.66 GHz. and with the IBM basica/D interpreter.
References
Amaral, A. R. S., "A New Lower Bound for the Single Row Facility Layout Problem," Discrete Applied Mathematics 157, 183-190 (2009).
Anjos, M. F., and A. Vannelli, "Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes," INFORMS Journal on Computing 20, 611-617 (2008).
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.
Nugent, C. E., R. E. Vollmann, and J. Ruml, "An Experimental Comparison of Techniques for the Assignment of Facilities to Locations," Operations Research, 16 (1968), 150-173.
Simmons, D. M., "One-Dimensional Space Allocation: an Ordering Algorithm," Operations Research 17, 812-826 (1969).
Skorin-Kapov, J., "Tabu Search Applied to the Quadratic Assignment Problem," ORSA Journal on Computing 2, 33-45 (1990).
