In their article Mixed-Integer Linear Programming Reformulations for Batch Process Design with Discrete Equipment Sizes in Industrial and Engineering Chemistry Research and referring to a Grossmann and Sargent [1] model for optimal sizing, Voudouris and Grossmann wrote, "A major assumption in this formulation is that the vessel sizes Vj are assumed to be continuous within specified lower and upper bounds Vjlo and Vjup. In real life, howerver, only vessels of discrete sizes are available," [2, p. 1316]. The present paper uses a case of replacing continuous equipment sizes with discrete equipment sizes to illustrate a computer program for integer programming formulations. The computer program listed here includes a method for restricting the values of a set of 0-1 variables.
This illustration replaces 300<= Vj <=3000, for j=1 to 6 of Salcedo's Example 9 [3, pp. 269-272] with Vj must be 700, 1000, 1400, 2000, or 2800, for j=1 to 6. These discrete equipment sizes are from Voudouris and Grosmann [2, p. 1323]. Salcedo's Example 9 is Example 4 of Kocis and Grossmann [4, p. 1417]. Salcedo's description of his Example 9 is given on pages 268-269 of Salcedo [3, pp. 268-269]. His input data are given on pages 269 and 270 [3]; these data come from Kocis and Grossmann [4, p. 1417].
Benefitting from the computer program on pages 229-232 of Conley [5], the following computer program follows Grossmann and Sargent's [2] and Kocis and Grossmann's [4] mathematical formulation plus the replacement of the continuous equipment sizes of Salcedo's Example 9 with the five discrete equipment sizes mentioned above. These discrete equipment sizes are used in line 533 through line 538.
1 DEFDBL A-Z
2 DEFINT I,J,K
5 DIM B(99),N(99),A(99),H(99),L(99),U(99),X(1111),D(111)
12 FOR JJJJ=-32000 TO -16000
14 RANDOMIZE JJJJ
16 M=-1D+17
25 B(1)=700:B(2)=700:B(3)=700:B(4)=700
26 B(5)=700:B(6)=700
27 B(7)=2.075:B(8)=1.7:B(9)=2.975:B(10)=.875:B(11)=1.05
28 B(12)=86.458333333333#:B(13)=42.5:B(14)=89.25
29 B(15)=23.333333333333#:B(16)=21
30 FOR KLN=23 TO 52
31 B(KLN)=0
32 NEXT KLN
33 B(17)=1:B(18)=1:B(19)=1:B(20)=1
34 B(21)=1:B(22)=1
37 N(1)=2800:N(2)=2800:N(3)=2800:N(4)=2800
38 N(5)=2800:N(6)=2800
39 N(7)=8.3:N(8)=6.8:N(9)=11.9:N(10)=3.5:N(11)=4.2
41 N(12)=379.7468354#:N(13)=882.3529412#:N(14)=833.333333333#
42 N(15)=638.2978723#:N(16)=666.666666666#
43 N(17)=4:N(18)=4:N(19)=4:N(20)=4
44 N(21)=4:N(22)=4
46 FOR KLP=23 TO 52
47 N(KLP)=1
48 NEXT KLP
61 FOR KLQ=1 TO 22
62 A(KLQ)=B(KLQ)+RND*(N(KLQ)-B(KLQ))
63 NEXT KLQ
64 FOR KLQQ=23 TO 52
65 A(KLQQ)=0
66 NEXT KLQQ
67 A(27)=1:A(32)=1:A(37)=1:A(42)=1:A(47)=1:A(52)=1
71 FOR KLR=1 TO 52
72 H(KLR)=3
73 NEXT KLR
88 FOR JJJ=1 TO 1000 STEP 10
90 FOR INEW=1 TO 5
94 FOR J=INEW*2 TO 0 STEP -2
102 FOR JJ=0 TO 22
111 KKLL=FIX(1+22*RND)
128 FOR I=1 TO 15
129 FOR KKQQ=1 TO 52
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
132 FOR K=1 TO 22
133 IF RND<=.5 THEN 298 ELSE 230
230 IF A(K)-(N(K)-B(K))/H(K)^J
255 GOTO 265
260 L(K)=A(K)-(N(K)-B(K))/H(K)^J
265 IF A(K)+(N(K)-B(K))/H(K)^J>N(K) THEN 266 ELSE 268
266 U(K)=N(K)-L(K)
267 GOTO 272
268 U(K)=A(K)+(N(K)-B(K))/H(K)^J-L(K)
272 GOTO 300
298 X(K)=A(K)+2*RND*(2*RND-1)*(1/(1+RND*JJJ))*.05*A(K)
299 GOTO 302
300 X(K)=(L(K)+2*RND*RND*U(K))
302 NEXT K
304 X(JJ)=A(JJ)
305 KLPS=FIX(1+KKLL*RND)
307 FOR KLA1=1 TO KLPS
308 KLA2=FIX(1+52*RND)
309 X(KLA2)=A(KLA2)
310 NEXT KLA1
343 IF RND>.1 GOTO 461
352 IF RND<=.9 THEN 353 ELSE 355
353 X(JJ)=B(JJ)
354 GOTO 461
355 X(JJ)=N(JJ)
461 IF X(17)>4 THEN 1670
462 IF X(17)<1 THEN 1670
463 IF X(18)>4 THEN 1670
464 IF X(18)<1 THEN 1670
465 IF X(19)>4 THEN 1670
466 IF X(19)<1 THEN 1670
467 IF X(20)>4 THEN 1670
468 IF X(20)<1 THEN 1670
469 IF X(21)>4 THEN 1670
470 IF X(21)<1 THEN 1670
471 IF X(22)>4 THEN 1670
472 IF X(22)<1 THEN 1670
483 IF X(7)>8.3 THEN 1670
484 IF X(7)<2.075# THEN 1670
485 IF X(8)>6.8 THEN 1670
486 IF X(8)<1.7# THEN 1670
487 IF X(9)>11.9 THEN 1670
488 IF X(9)<2.975# THEN 1670
489 IF X(10)>3.5 THEN 1670
490 IF X(10)<.875# THEN 1670
491 IF X(11)>4.2 THEN 1670
492 IF X(11)<1.05 THEN 1670
493 IF X(12)>379.7468354# THEN 1670
494 IF X(12)<86.4583333333# THEN 1670
495 IF X(13)>882.3529412# THEN 1670
496 IF X(13)<42.5 THEN 1670
497 IF X(14)>833.3333333333333# THEN 1670
498 IF X(14)<89.25 THEN 1670
499 IF X(15)>638.2978723# THEN 1670
500 IF X(15)<23.3333333333333# THEN 1670
501 IF X(16)>666.666666666666# THEN 1670
502 IF X(16)<21 THEN 1670
504 X(17)=FIX(X(17)):X(18)=FIX(X(18)):X(19)=FIX(X(19)):X(20)=FIX(X(20)):X(21)=FIX(X(21)):X(22)=FIX(X(22))
505 IF RND<1/6 THEN 511 ELSE IF RND<2/6 THEN 514 ELSE IF RND<3/6 THEN 517 ELSE IF RND<4/6 THEN 520 ELSE IF RND<5/6 THEN 523 ELSE 526
511 AHOR1=FIX(23+RND*5):BHOR1=FIX(23+RND*5)
512 X(AHOR1)=A(BHOR1):X(BHOR1)=A(AHOR1)
513 GOTO 533
514 AHOR2=FIX(28+RND*5):BHOR2=FIX(28+RND*5)
515 X(AHOR2)=A(BHOR2):X(BHOR2)=A(AHOR2)
516 GOTO 533
517 AHOR3=FIX(33+RND*5):BHOR3=FIX(33+RND*5)
518 X(AHOR3)=A(BHOR3):X(BHOR3)=A(AHOR3)
519 GOTO 533
520 AHOR4=FIX(38+RND*5):BHOR4=FIX(38+RND*5)
521 X(AHOR4)=A(BHOR4):X(BHOR4)=A(AHOR4)
522 GOTO 533
523 AHOR5=FIX(43+RND*5):BHOR5=FIX(43+RND*5)
524 X(AHOR5)=A(BHOR5):X(BHOR5)=A(AHOR5)
525 GOTO 533
526 AHOR6=FIX(48+RND*5):BHOR6=FIX(48+RND*5)
527 X(AHOR6)=A(BHOR6):X(BHOR6)=A(AHOR6)
533 X(1)=700*X(23)+1000*X(24)+1400*X(25)+2000*X(26)+2800*X(27)
534 X(2)=700*X(28)+1000*X(29)+1400*X(30)+2000*X(31)+2800*X(32)
535 X(3)=700*X(33)+1000*X(34)+1400*X(35)+2000*X(36)+2800*X(37)
536 X(4)=700*X(38)+1000*X(39)+1400*X(40)+2000*X(41)+2800*X(42)
537 X(5)=700*X(43)+1000*X(44)+1400*X(45)+2000*X(46)+2800*X(47)
538 X(6)=700*X(48)+1000*X(49)+1400*X(50)+2000*X(51)+2800*X(52)
541 FOR KKKQQQ=1 TO 10
542 KMID=1+FIX(RND*6)
543 X(KMID)=A(KMID)
545 NEXT KKKQQQ
559 PE=(250000!*X(7)/X(12)+150000!*X(8)/X(13)+180000!*X(9)/X(14)+160000!*X(10)/X(15)+120000!*X(11)/X(16))-6000
560 IF PE>0 THEN PE=PE ELSE PE=0
561 P11=X(1)-7.9*X(12)
562 P12=X(2)-2!*X(12)
563 P13=X(3)-5.2*X(12)
564 P14=X(4)-4.9*X(12)
565 P15=X(5)-6.1*X(12)
566 P16=X(6)-4.2*X(12)
567 P17=X(1)-.7*X(13)
568 P18=X(2)-.8*X(13)
569 P19=X(3)-.9*X(13)
570 P20=X(4)-3.4*X(13)
571 P21=X(5)-2.1*X(13)
572 P22=X(6)-2.5*X(13)
573 P23=X(1)-.7*X(14)
574 P24=X(2)-2.6*X(14)
575 P25=X(3)-1.6*X(14)
576 P26=X(4)-3.6*X(14)
577 P27=X(5)-3.2*X(14)
578 P28=X(6)-2.9*X(14)
579 P29=X(1)-4.7*X(15)
580 P30=X(2)-2.3*X(15)
581 P31=X(3)-1.6*X(15)
582 P32=X(4)-2.7*X(15)
583 P33=X(5)-1.2*X(15)
584 P34=X(6)-2.5*X(15)
585 P35=X(1)-1.2*X(16)
586 P36=X(2)-3.6*X(16)
587 P37=X(3)-2.4*X(16)
588 P38=X(4)-4.5*X(16)
589 P39=X(5)-1.6*X(16)
590 P40=X(6)-2.1*X(16)
598 REM
599 REM
601 P51=X(17)*X(7)-6.4
602 P52=X(18)*X(7)-4.7
603 P53=X(19)*X(7)-8.3
604 P54=X(20)*X(7)-3.9
605 P55=X(21)*X(7)-2.1
606 P56=X(22)*X(7)-1.2
607 P57=X(17)*X(8)-6.8
608 P58=X(18)*X(8)-6.4
609 P59=X(19)*X(8)-6.5
610 P60=X(20)*X(8)-4.4
611 P61=X(21)*X(8)-2.3
612 P62=X(22)*X(8)-3.2
613 P63=X(17)*X(9)-1!
614 P64=X(18)*X(9)-6.3
615 P65=X(19)*X(9)-5.4
616 P66=X(20)*X(9)-11.9
617 P67=X(21)*X(9)-5.7
618 P68=X(22)*X(9)-6.2
619 P69=X(17)*X(10)-3.2
620 P70=X(18)*X(10)-3!
621 P71=X(19)*X(10)-3.5
622 P72=X(20)*X(10)-3.3
623 P73=X(21)*X(10)-2.8
624 P74=X(22)*X(10)-3.4
625 P75=X(17)*X(11)-2.1
626 P76=X(18)*X(11)-2.5
627 P77=X(19)*X(11)-4.2
628 P78=X(20)*X(11)-3.6
629 P79=X(21)*X(11)-3.7
630 P80=X(22)*X(11)-2.2
801 IF P11<0 THEN P11=P11 ELSE P11=0
802 IF P12<0 THEN P12=P12 ELSE P12=0
803 IF P13<0 THEN P13=P13 ELSE P13=0
804 IF P14<0 THEN P14=P14 ELSE P14=0
805 IF P15<0 THEN P15=P15 ELSE P15=0
806 IF P16<0 THEN P16=P16 ELSE P16=0
807 IF P17<0 THEN P17=P17 ELSE P17=0
808 IF P18<0 THEN P18=P18 ELSE P18=0
809 IF P19<0 THEN P19=P19 ELSE P19=0
810 IF P20<0 THEN P20=P20 ELSE P20=0
811 IF P21<0 THEN P21=P21 ELSE P21=0
812 IF P22<0 THEN P22=P22 ELSE P22=0
813 IF P23<0 THEN P23=P23 ELSE P23=0
814 IF P24<0 THEN P24=P24 ELSE P24=0
815 IF P25<0 THEN P25=P25 ELSE P25=0
816 IF P26<0 THEN P26=P26 ELSE P26=0
817 IF P27<0 THEN P27=P27 ELSE P27=0
818 IF P28<0 THEN P28=P28 ELSE P28=0
819 IF P29<0 THEN P29=P28 ELSE P29=0
820 IF P30<0 THEN P30=P30 ELSE P30=0
821 IF P31<0 THEN P31=P31 ELSE P31=0
822 IF P32<0 THEN P32=P32 ELSE P32=0
823 IF P33<0 THEN P33=P33 ELSE P33=0
824 IF P34<0 THEN P34=P34 ELSE P34=0
825 IF P35<0 THEN P35=P35 ELSE P35=0
826 IF P36<0 THEN P36=P36 ELSE P36=0
827 IF P37<0 THEN P37=P37 ELSE P37=0
828 IF P38<0 THEN P38=P38 ELSE P38=0
829 IF P39<0 THEN P39=P39 ELSE P39=0
830 IF P40<0 THEN P40=P40 ELSE P40=0
831 IF P51<0 THEN P51=P51 ELSE P51=0
832 IF P52<0 THEN P52=P52 ELSE P52=0
833 IF P53<0 THEN P53=P53 ELSE P53=0
834 IF P54<0 THEN P54=P53 ELSE P54=0
835 IF P55<0 THEN P55=P55 ELSE P55=0
836 IF P56<0 THEN P56=P56 ELSE P56=0
837 IF P57<0 THEN P57=P57 ELSE P57=0
838 IF P58<0 THEN P58=P58 ELSE P58=0
839 IF P59<0 THEN P59=P59 ELSE P59=0
840 IF P60<0 THEN P60=P60 ELSE P60=0
841 IF P61<0 THEN P61=P61 ELSE P61=0
842 IF P62<0 THEN P62=P62 ELSE P62=0
843 IF P63<0 THEN P63=P63 ELSE P63=0
844 IF P64<0 THEN P64=P64 ELSE P64=0
845 IF P65<0 THEN P65=P65 ELSE P65=0
846 IF P66<0 THEN P66=P66 ELSE P66=0
847 IF P67<0 THEN P67=P67 ELSE P67=0
848 IF P68<0 THEN P68=P68 ELSE P68=0
849 IF P69<0 THEN P69=P69 ELSE P69=0
850 IF P70<0 THEN P70=P70 ELSE P70=0
851 IF P71<0 THEN P71=P71 ELSE P71=0
852 IF P72<0 THEN P72=P72 ELSE P72=0
853 IF P73<0 THEN P73=P73 ELSE P73=0
854 IF P74<0 THEN P74=P74 ELSE P74=0
855 IF P75<0 THEN P75=P75 ELSE P75=0
856 IF P76<0 THEN P76=P76 ELSE P76=0
857 IF P77<0 THEN P77=P77 ELSE P77=0
858 IF P78<0 THEN P78=P78 ELSE P78=0
859 IF P79<0 THEN P79=P79 ELSE P79=0
860 IF P80<0 THEN P80=P80 ELSE P80=0
1201 PS1=555555!*P11+555555!*P12+555555!*P13+555555!*P14+555555!*P15+555555!*P16+555555!*P17+555555!*P18+555555!*P19+555555!*P20
1202 PS2=555555!*P21+555555!*P22+555555!*P23+555555!*P24+555555!*P25+555555!*P26+555555!*P27+555555!*P28+555555!*P29+555555!*P30
1203 PS3=555555!*P31+555555!*P32+555555!*P33+555555!*P34+555555!*P35+555555!*P36+555555!*P37+555555!*P38+555555!*P39+555555!*P40
1204 PS4=555555!*P51+555555!*P52+555555!*P53+555555!*P54+555555!*P55+555555!*P56+555555!*P57+555555!*P58+555555!*P59+555555!*P60
1205 PS5=555555!*P61+555555!*P62+555555!*P63+555555!*P64+555555!*P65+555555!*P66+555555!*P67+555555!*P68+555555!*P69+555555!*P70
1206 PS6=555555!*P71+555555!*P72+555555!*P73+555555!*P74+555555!*P75+555555!*P76+555555!*P77+555555!*P78+555555!*P79+555555!*P80
1331 IF X(1)<0 GOTO 1670
1332 IF X(2)<0 GOTO 1670
1333 IF X(3)<0 GOTO 1670
1334 IF X(4)<0 GOTO 1670
1335 IF X(5)<0 GOTO 1670
1336 IF X(6)<0 GOTO 1670
1447 P1=+250*X(17)*X(1)^.6+250*X(18)*X(2)^.6+250*X(19)*X(3)^.6+250*X(20)*X(4)^.6+250*X(21)*X(5)^.6+250*X(22)*X(6)^.6
1449 P=-P1-555555!*PE+PS1+PS2+PS3+PS4+PS5+PS6
1451 IF P<=M THEN 1670
1452 M=P
1453 PP1=P1
1454 FOR KLX=1 TO 52
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1457 GOTO 128
1670 NEXT I
1702 NEXT JJ
1706 NEXT J
1777 NEXT INEW
1888 NEXT JJJ
1890 IF M>-333333! THEN 1916 ELSE 1999
1916 PRINT JJJJ,A(1),A(2),A(3),A(4),A(5),A(6),A(7)
1917 PRINT A(8),A(9),A(10),A(11),A(12),A(13),A(14),A(15),A(16)
1918 PRINT A(17),A(18),A(19),A(20),A(21),A(22),M,PP1
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the best candidate solutions from JJJJ=-32000 through JJJJ=-31896 (in compressed form and to be interpreted in accordance with line 1916 through line 1918) are presented below.
-31992 2800 2000 2000 2800
2800 2800 3.202003443017386
3.407750208212112 6.201432945196092 3.405226077737206
3.731339719542587 353.5234674878737 823.3822533614164
769.1888332478399 637.0468985192472 555.3591679145774
2 2 3 2 1
1 -295088.1528303848 295088.1528303848
-31967 2800 2800 2000 2800
2800 2800 3.204423317423649
3.45726448986246 6.200048558020126 3.410949046717939
3.707249228236958 348.1112487685418 814.7937834271105
757.3385868747027 637.1690083696522 614.2790086238543
2 2 3 2 1
1 -305785.2087396884 305785.2087396884
-31906 2800 2800 2000 2800
2800 2800 3.208288443590261
3.405107479059507 6.201375813226306 3.401268881042718
3.729916553867051 347.9511155819437 820.8089461823656
768.006521087299 633.1442934270412 608.5278574395473
2 2 3 2 1
1 -305785.2087396884 305785.2087396884
-31898 2800 2800 2000 2800
2800 2800 3.202372145502365
3.459960670884915 6.205170297994183 3.40544866946053
3.730569658697647 354.0656941245111 744.5818193168934
777.1566853662473 625.3623246271263 610.9551808229138
2 2 3 2 1
1 -305785.2087396884 305785.2087396884
-31896 2800 2000 2000 2800
2800 2800 3.204852812074871
3.40006173507553 6.207650513408338 3.403374023264902
3.70505641290593 354.0917044721211 820.1954627513843
769.0616242224669 635.8768019379574 554.0939382289513
2 2 3 2 1
1 -295088.1528303848 295088.1528303848
This cost of $295088.1528303848 for our discrete equipmnt size problem is 3.356% more than the cost of $285506 for the corresponding continuous equipment size problem reported by Kocis and Grossmann [4, p. 1417] and by Floudas et al. [6, p. 1120].
Thus the cost of 295088.1528303848 occurred only two times during the first 20 hours of running the program above on a personal computer with an Intel 2.66 GHz. chip and the IBM interpreter. If one makes changes to the computer program, such as a change of changing line 128 above to, for example, 128 FOR I=1 TO 14, one may or may not obtain 295088.1528303848, which may or may not be the minimum. This point is relevant to the present problem AND beyond it. That leads to a general remedy that in general, in order to increase the chance of getting an optimal solution, one preferably should run several computers simultaneously, each with a different line 128. Running several computers simultaneously can mitigate the possible danger of missed optimality, and that can produce a usable solution faster. Also, one should look into other algorithms for solving the problem [2].
Line 65, line 67, line 511, line 512, line 533, and line 543 of the computer program above are basic to a method that makes only one variable of the five 0-1 variables--x(23), x(24), x(25), x(26), and x(27)--equal 1. The other similar lines do the same to the other 0-1 variables. More generally, this method can be useful for other integer programming formulations.
References
[1] I. E. Grossmann and R. W. H. Sargent, "Optimal design of multipurpose chemical plants," Ind. Eng. Chem. Process Des. Dev., Vol. 18, No. 2, 1979, pp. 343-348.
[2] V. T. Voudouris, and I. E. Grossmann, "Mixed-integer linear programming reformulations for batch proxcess design with discrete equipment sizes," Ind. Eng. Chem. Res., Vol. 31, No. 5, 1992, pp. 1315-1325.
[3] R. L. Salcedo, "Solving nonconvex nonlinear programming and mixed-integer nonlinear programming problems with adaptive random search," Ind. Eng. Chem. Res., Vol. 31, No. 1, 1992, pp. 262-273.
[4] G. R. Kocis and I. E. Grossmann, "Global optimization of nonconvex mixed-integer nonlinear programming (MINLP) problem in process synthesis," Ind. Eng. Chem. Res., Vol. 27, No. 8, 1988, pp. 1407-1421.
[5] W. C. Conley, Optimization: A Simplified Approach. Petrocelli, Princeton, New Jersey, 1981, pp. 229-232.
[6] C. A. Floudas, A. Aggarwal, and A. R. Ciric, "Global optimum search for nonconvex NLP and MINLP problems," Comput. Chem. Eng., Vol. 13, No. 10, 1989, pp. 1117-1132.
