A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to an Oil Production Problem with 25 Oil Wells, One-or-Two-or-Three Platforms, and Manhattan Distances

Jsun Yui Wong   

The following computer program tries to solve a problem based on the first example in Cheung, Langevin, and Delmaire [1, pp. 17-20].  In the present paper, the number of oil platforms to be used is one or two or three; it is not fixed at three.  Three different platform costs are shown in line 1591 through line 1593.  Manhattan (rectangular) distances are used in line 1380 through line 1383.  The locations of the 25 wells given in line 23 and line 24 are from Table 1 of Cheung, Langevin, and Delmaire [1].  Global optimization is the goal.

0 DEFSNG A-Z
3 DEFINT I,J,K,H
4 DIM X(1555),A(1555),L(1555),K(1555),PNEM(1555),ILO(1555),J(1555),PNE1(222),PNE2(222),PNE3(222),PNE4(222),PNE5(222),PNE6(222),PNE7(222)
18 FOR IL=1 TO 50
19 READ L(IL)
20 NEXT IL
23 DATA 22,3,69,44,44,50,70,12,97,51,94,35,100,62,94,26,13,75,65,99,58,59,82,31,13,95,87,29
24 DATA 41,87,47,94,15,89,20,85,31,50,12,99,86,75,47,98,0,52,54,92,90,79
75 FOR JJJJ=-32000 TO 32000
76 RANDOMIZE JJJJ
77 M=-1.7E+38
88 FOR IAA=1 TO 6
89 A(IAA)=RND*100
90 NEXT IAA
98 IF RND<.5 THEN 101 ELSE 111
101 FOR IBA= 11 TO 85 STEP 1
102 A(IBA)=1
103 NEXT IBA
105 GOTO 126
111 FOR IBB= 11 TO 85 STEP 1
112 A(IBB)=0
113 NEXT IBB
121 FOR IBB= 11 TO 85 STEP 3
122 A(IBB)=1
123 NEXT IBB
126 REM   IMAR=10+FIX(RND*32700)
128 FOR I=1 TO 327
129 FOR K=1 TO 85
131 X(K)=A(K)
132 NEXT K
141 IF RND<.5 THEN 181 ELSE 244
181 J=1+FIX(RND*6)
183 R=RND*(1-RND*2)*A(J)
191 IF RND<.14 THEN X(J)=A(J)+RND^5*R ELSE IF RND<.17 THEN X(J)=A(J)+R ELSE IF RND<.2 THEN X(J)=A(J)+RND*R ELSE IF RND<.25 THEN X(J)=A(J)+RND^2*R ELSE IF RND<.33 THEN X(J)=A(J)+RND^3*R ELSE IF RND<.5 THEN X(J)=A(J)+RND^4*R ELSE X(J)=A(J)+RND^6*R
192 GOTO 1333
244 IF RND<1/25 THEN JJ=11 ELSE IF RND<1/24 THEN JJ=14 ELSE IF RND<1/23 THEN JJ=17 ELSE IF RND<1/22 THEN JJ=20 ELSE IF RND<1/21 THEN JJ=23 ELSE IF RND<1/20 THEN JJ=26 ELSE IF RND<1/19 THEN JJ=29 ELSE 246
245 GOTO 705
246 IF RND<1/18 THEN JJ=32 ELSE IF RND<1/17 THEN JJ=35 ELSE IF RND<1/16 THEN JJ=38 ELSE IF RND<1/15 THEN JJ=41 ELSE IF RND<1/14 THEN JJ=44 ELSE IF RND<1/13 THEN JJ=47 ELSE IF RND<1/12 THEN JJ=50 ELSE 248
247 GOTO 705
248 IF RND<1/11 THEN JJ=53 ELSE IF RND<1/10 THEN JJ=56 ELSE IF RND<1/9 THEN JJ=59 ELSE IF RND<1/8 THEN JJ=62 ELSE IF RND<1/7 THEN JJ=65 ELSE IF RND<1/6 THEN JJ=68 ELSE IF RND<1/5 THEN JJ=71 ELSE 250
249 GOTO 705
250 IF RND<1/4 THEN JJ=74 ELSE IF RND<1/3 THEN JJ=77 ELSE IF RND<1/2 THEN JJ=80 ELSE JJ=83
705 IF RND<1/3 THEN X(JJ)=0:X(JJ+1)=0:X(JJ+2)=1 ELSE IF RND<1/2 THEN X(JJ)=0:X(JJ+1)=1:X(JJ+2)=0 ELSE 713
708 GOTO 1333
713 X(JJ)=1:X(JJ+1)=0:X(JJ+2)=0
714 GOTO 1333
1333 REM
1367 FOR H=1 TO 25
1380 PNE1(H)=-(ABS(L(H*2-1)-X(1))+ABS(L(H*2)-X(4)))*X(3*H+8)
1381 PNE2(H)=-(ABS(L(H*2-1)-X(2))+ABS(L(H*2)-X(5)))*X(3*H+9)
1383 PNE3(H)=-(ABS(L(H*2-1)-X(3))+ABS(L(H*2)-X(6)))*X(3*H+10)
1388 PNEM(H)=PNE1(H)+PNE2(H)+PNE3(H)
1389 NEXT H
1390 PSUM=0
1391 FOR HH=1 TO 25
1393 PSUM=PSUM+PNEM(HH)
1396 NEXT HH
1511 S1=0
1513 FOR H1=1 TO 73 STEP 3
1515 S1=S1+X(10+H1)
1518 NEXT H1
1521 S2=0
1523 FOR H2=2 TO 74 STEP 3
1525 S2=S2+X(10+H2)
1528 NEXT H2
1531 S3=0
1533 FOR H3=3 TO 75 STEP 3
1535 S3=S3+X(10+H3)
1538 NEXT H3
1591 IF S1>.1 THEN PLCOST1=50+25*S1^.5 ELSE PLCOST1=0
1592 IF S2>.1 THEN PLCOST2=76+21*S2^.5 ELSE PLCOST2=0
1593 IF S3>.1 THEN PLCOST3=128+16*S3^.5 ELSE PLCOST3=0
1599 PLCOSTT=PLCOST1+PLCOST2+PLCOST3
1601 P=PSUM-PLCOSTT
1651 IF P<=M THEN 1670
1657 FOR KEW=1 TO 85
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1663 SS1=S1:SS2=S2:SS3=S3
1666 GOTO 128
1670 NEXT I
1890 IF M>-1070 THEN 1931 ELSE 2999
1931 FOR IPR=11 TO 83 STEP 3
1933 LPRINT A(IPR),A(IPR+1),A(IPR+2)
1938 NEXT IPR
1952 LPRINT A(1),A(2),A(3),A(4),A(5),A(6),M
1955 LPRINT SS1,SS2,SS3,JJJJ,M
2999 NEXT JJJJ

The BASIC computer program above was run with Microsoft's GW BASIC 3.11 interpreter, which is not a compiler.  The top-two solutions produced during the first minute of running are presented below.  What immediately follows is a hand copy from the output on paper.

100
010
100
010
010
010
010
010
001
001
100
010
001
010
001
001
001
001
100
001
010
001
100
001
010
30.99982   89.96662   20.57498   50.00007   35.08133
92.24376   -1061.906
5   10   10   -31996   -1061.906

100
001
100
001
001
001
001
001
100
010
001
001
010
001
010
010
010
010
100
010
001
010
100
010
001
21.997   41.00225   86.99771   50.00011   93.99917
43.99995   -1055.977
5   9   11   -31983   -1055.977

Interpreted in accordance with line 1931 through line 1955, the output above was produced in one minute of running on a personal computer with an Intel 2.66 GHz. chip and the IBM basica/D interpreter.

In general, with the present algorithm a usable solution may come early, late, or worse.  To alleviate this shortcoming, one can simultaneously run independent computers with different line 128s.  Here is one example: 128 FOR I=1 TO 1000, 128 FOR I=1 TO 2000, 128 FOR I=1 TO 3000, 128 FOR I=1 TO 4000, and 128 FOR I=1 TO 5000.

References

[1] B. K.-S. Cheung, A. Langevin and H. Delmaire, Coupling Genetic Algorithm with a Grid Search Method To Solve Mixed Integer Nonlinear Programming Problems, Computers Math. Applic. Vol. 34, No. 12, pp.13-23, 1997. 

[2] Microsoft Corp. BASIC, second edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.