Monday, July 31, 2017

Using the MINLP Solver Presented Here

Jsun Yui Wong

The computer program listed below seeks to solve the nonconvex example on pp. 45-47 of Tsai and Lin [7].

The X(6), X(7), and X(8) of the following computer program are slack variables.  Line 403 below refers to the given objective function.

0 REM  DEFDBL A-Z

2 DEFINT I, J, K

3 DIM B(99), N(99), A(99), H(99), L(99), U(99), X(1111), D(111), P(111), PS(33)
12 FOR JJJJ = -32000 TO 32111

    14 RANDOMIZE JJJJ
    16 M = -1D+37
    64 FOR J44 = 1 TO 5
        65 A(J44) = 1 + RND * 9


    66 NEXT J44

    77 A(1) = -7 + RND * 12


    126 REM IMAR=10+FIX(RND*32000)
    128 FOR I = 1 TO 10000


        129 FOR KKQQ = 1 TO 5
            130 X(KKQQ) = A(KKQQ)
        131 NEXT KKQQ
        133 FOR IPP = 1 TO (1 + FIX(RND * 3))
            181 J = 1 + FIX(RND * 5)
            183 R = (1 - RND * 2) * A(J)
            187 X(J) = A(J) + (RND ^ (RND * 10)) * R
        222 NEXT IPP
        223 REM GOTO 233

        225 REM FOR J23 = 1 TO 4

        227 X(3) = INT(X(3))



        229 REM NEXT J23


        233 X(6) = 2 - X(1) - 6 * X(2) + X(3) + 5 * X(4)

        244 X(7) = -10 - (X(3) ^ 1.5) * X(4) - .5 * X(2) - 3 * X(1)


        249 X(8) = 6 + X(1) + .5 * X(4) - X(5)

        283 IF X(1) < -7 THEN 1670

        284 IF X(1) > 5 THEN 1670

        286 IF X(2) < 1 THEN 1670

        287 IF X(2) > 10 THEN 1670

        288 IF X(3) < 1 THEN 1670

        289 IF X(3) > 5 THEN 1670

        291 IF X(4) < 2 THEN 1670

        292 IF X(4) > 8 THEN 1670

        297 IF X(5) < 2 THEN 1670

        298 IF X(5) > 9 THEN 1670


        331 FOR J44 = 6 TO 8

            335 IF X(J44) < 0 THEN PS(J44) = ABS(X(J44)) ELSE PS(J44) = 0

        339 NEXT J44
        403 POBA2 = -(X(1) ^ 2 * X(2) ^ -2 * X(3) - 2 * X(2) ^ .7 * X(3) ^ .2 + X(4) * X(5) ^ -2 - 2 * X(1) - 4 * X(3))




        411 POBA = POBA2 - 1000000 * PS(6) - 1000000 * PS(7) - 1000000 * PS(8)



        422 REM POBA = POBA2 + (PS(4))
        459 POB1 = POBA
        463 P1NEWMAY = POB1
        466 P = P1NEWMAY
        1111 IF P <= M THEN 1670
        1452 M = P
        1453 PPOBA2 = POBA2
        1454 FOR KLX = 1 TO 8


            1455 A(KLX) = X(KLX)
        1456 NEXT KLX
        1557 REM   GOTO 128

    1670 NEXT I
    1889 IF M < -2.906 THEN 1999

    1900 PRINT A(1), A(2), A(3), A(4)

    1904 PRINT A(5), A(6), A(7), A(8), M, JJJJ, PPOBA2

1999 NEXT JJJJ

This BASIC computer program was run with qb64v1000-win [8].  The complete output through JJJJ=-30627 is shown below:

-5.341226                4.52466                1           3.761347
2.539448                   1.907349E-06             2.384186E-07
0         -2.905618      -31874        -2.905618

-5.321954                4.488379                1            3.721663
2.538877                9.536743E-07             1.001358E-05
0         -2.905934      -31454        -2.905934

-5.333839                4.510576                1            3.745927
2.53912             1.502037E-05             3.020763E-04
3.933907E-06         -2.905985      -31356        -2.905985

-5.374219                4.586674                1           3.829311
2.540405      7.281303E-04      1.0252E-05             3.147125E-05
-2.905988      -30627        -2.905988

Above there is no rounding by hand; it is just straight copying by hand from the monitor screen.

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [8], the wall-clock time for obtaining the output through JJJJ=-30627 was 35 seconds.

Acknowledgment

I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.

References

[1]  Yuichiro Anzai (1974).  On Integer Fractional Programming.  Journal Operations Research Society of Japan, Volume 17, No. 1, March 1974, pp. 49-66.
www..orsj.or.jp/~archiv/pdf/e_mag/Vol.17_01_049.pdf.

[2]  Han-Lin Li, Jung-Fa Tsai (2008).  A distributed computational algorithm for solving portfolio problems with integer variables.  European Journal of Operational Research 186 (2008) pp.882-891.

[3]   Harry Markowitz  (1952).   Portfolio Selection.   The Journal of Finance  7 (2008) pp. 77-91.

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

[5]  H. S. Ryoo, N. V. Sahinidis (1995).  Global optimization of nonconvex NLP and MINLP with applications in process design. Computers and Chemical Engineering Vol. 19 (5) (1995) pp. 551-566.

[6]  Jung-Fa Tsai, Ming-Hua Lin, Yi-Chung Hu (2007).  On generalized geometric programming problems with non-positive variables.  European Journal of Operational Research 178 (2007) pp. 10-19.

[7]  Jung-Fa Tsai, Ming-Hua Lin (2008).  Global optimization of signomial mixed-integer nonlinear programming with free variables.  Journal of Global Optimization  (2008) 42  pp. 39-49.

[8] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64.    

[9] Jsun Yui Wong (2012, April 12).  The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Fractional Programming Problem from the Literature. http://myblogsubstance.typepad.com/substance/2012/04/12/

Saturday, July 29, 2017

A Computer Program about Markowitz Portfolio Selection

Jsun Yui Wong

The computer program listed below seeks to solve the small example about Markowitz portfolio selection [3] on pp. 888-890 of Li and Tsai [2].

Minimize           .0108 * X(1) ^ 2 + .0584 * X(2) ^ 2 + .0942 * X(3) ^ 2 + .0248 * X(1) * X(2) + .0262 * X(1) * X(3) + .1108 * X(2) * X(3)

subject to          1.089 * X(1) + 1.214 * X(2) + 1.235 * X(3)  >=  115

X(1) + X(2) + X(3)  =  100

where X(1),  X(2), and X(3) are integers.

Below X(1) through X(3) are integer variables, and X(4) is a slack variable.


0 REM  DEFDBL A-Z

2 DEFINT I, J, K

3 DIM B(99), N(99), A(99), H(99), L(99), U(99), X(1111), D(111), P(111), PS(33)
12 FOR JJJJ = -32000 TO 32000


    14 RANDOMIZE JJJJ
    16 M = -1D+37
    64 FOR J44 = 1 TO 3
        65 A(J44) = RND * 10

    66 NEXT J44
    126 REM IMAR=10+FIX(RND*32000)
    128 FOR I = 1 TO 10000


        129 FOR KKQQ = 1 TO 3
            130 X(KKQQ) = A(KKQQ)
        131 NEXT KKQQ
        133 FOR IPP = 1 TO (1 + FIX(RND * 2))
            181 J = 1 + FIX(RND * 3)
            183 R = (1 - RND * 2) * A(J)
            187 X(J) = A(J) + (RND ^ (RND * 10)) * R
        222 NEXT IPP

        223 X(1) = 100 - X(2) - X(3)


        224 FOR J33 = 1 TO 3

            226 X(J33) = INT(X(J33))

        227 NEXT J33

        229 REM X(5) = 1
        233 X(4) = -115 + 1.089 * X(1) + 1.214 * X(2) + 1.235 * X(3)
   
        281 FOR J44 = 1 TO 3


            283 IF X(J44) < 0 THEN 1670

            284 IF X(J44) > 100 THEN 1670

        285 NEXT J44

        331 FOR J44 = 4 TO 4

            332 IF X(J44) < 0 THEN PS(J44) = ABS(X(J44)) ELSE PS(J44) = 0
        333 NEXT J44
        403 POBA2 = -(.0108 * X(1) ^ 2 + .0584 * X(2) ^ 2 + .0942 * X(3) ^ 2 + .0248 * X(1) * X(2) + .0262 * X(1) * X(3) + .1108 * X(2) * X(3))


        411 POBA = POBA2 - 1000000 * (PS(4))


        459 POB1 = POBA
        463 P1NEWMAY = POB1
        466 P = P1NEWMAY
        1111 IF P <= M THEN 1670
        1452 M = P
        1453 PPOBA2 = POBA2
        1454 FOR KLX = 1 TO 11

            1455 A(KLX) = X(KLX)
        1456 NEXT KLX
        1557 GOTO 128
    1670 NEXT I
    1889 IF M < -224.647 THEN 1999

    1900 PRINT A(1), A(2), A(3), A(4)
 
    1904 PRINT M, JJJJ, PPOBA2
1999 NEXT JJJJ

This BASIC computer program was run with qb64v1000-win [5].  The complete output through JJJJ=-24202 is shown below:

53    36     11      .006
-223.8916       -28885       -223.8916

53    35     12        .027
-224.6452         -27481           -224.6452

53    36     11      .006
-223.8916       -25873       -223.8916

53    35     12        .027
-224.6452         -24202           -224.6452

Above there is no rounding by hand; it is just straight copying by hand from the monitor screen.

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [5], the wall-clock time for obtaining the output through JJJJ=-24202 was 2 minutes and 15 seconds.

Acknowledgment

I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.

References

[1]  Yuichiro Anzai (1974).  On Integer Fractional Programming.  Journal Operations Research Society of Japan, Volume 17, No. 1, March 1974, pp. 49-66.
www..orsj.or.jp/~archiv/pdf/e_mag/Vol.17_01_049.pdf.

[2]  Han-Lin Li, Jung-Fa Tsai (2008).  A distributed computational algorithm for solving portfolio problems with integer variables.  European Journal of Operational Research 186 (2008) pp.882-891.

[3]   Harry Markowitz  (1952).   Portfolio Selection.   The Journal of Finance 7 (2008) pp. 77-91.

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

[5] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64.    

[6] Jsun Yui Wong (2012, April 12).  The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Fractional Programming Problem from the Literature. http://myblogsubstance.typepad.com/substance/2012/04/12/

Sunday, July 23, 2017

A Computer Program for Integer Fractional Programming, Revised Edition


Jsun Yui Wong

The computer program listed below seeks to solve the integer fractional programming example on pages 55-57 of Anzai [1].

Here X(1) through X(5) are integer variables, and X(6) through X(11) are slack variables.  

Whereas line 128 and line 1454 of the preceding paper are 128 FOR I = 1 TO 1000 and 1454 FOR KLX = 1 TO 8, here line 128 and line 1454 are 128 FOR I = 1 TO 50 and 1454 FOR KLX = 1 TO 11, respectively.

0 DEFDBL A-Z
2 DEFINT I, J, K

3 DIM B(99), N(99), A(99), H(99), L(99), U(99), X(1111), D(111), P(111), PS(33)
12 FOR JJJJ = -32000 TO 32000

    14 RANDOMIZE JJJJ
    16 M = -1D+37
    64 FOR J44 = 1 TO 5
        65 A(J44) = .1 + RND * 9.899999
    66 NEXT J44
    126 REM IMAR=10+FIX(RND*32000)
    128 FOR I = 1 TO 50

        129 FOR KKQQ = 1 TO 5
            130 X(KKQQ) = A(KKQQ)
        131 NEXT KKQQ
        133 FOR IPP = 1 TO (1 + FIX(RND * 4))
            181 J = 1 + FIX(RND * 5)
            183 R = (1 - RND * 2) * A(J)
            187 X(J) = A(J) + (RND ^ (RND * 10)) * R
            188 GOTO 222
            189 REM   X(J)=A(J)+PA
            190 REM X(J)=A(J)+FIX(RND*2 )-FIX(RND*2)
            191 REM   X(J)=A(J)+FIX(RND*3)-FIX(RND*3)
        222 NEXT IPP

        224 FOR J33 = 1 TO 5

            226 X(J33) = INT(X(J33))

        227 NEXT J33

        229 X(5) = 1

        231 REM FOR J44=1 TO 5
        233 REM IF X(J44)<.1 THEN 1670
        234 REM IF X(J44)>10 THEN 1670
        235 REM NEXT J44

        240 X(6) = X(1) - 2 * X(2) + 9

        259 X(7) = -4 * X(1) - X(2) + 21

        261 X(8) = -X(1) + 3 * X(2)

        266 X(9) = 4 * X(1) + 5 * X(2) - 12

        268 X(10) = 2 * X(3) - 6 * X(4) + 21

        270 X(11) = -7 * X(3) - 4 * X(4) + 39

        281 FOR J44 = 1 TO 5

            283 IF X(J44) < 0 THEN 1670

            284 IF X(J44) > 10 THEN 1670
        285 NEXT J44

        331 FOR J44 = 6 TO 11
            332 IF X(J44) < 0 THEN PS(J44) = ABS(X(J44)) ELSE PS(J44) = 0
        333 NEXT J44
        403 POBA2 = -(-X(1) - 3 * X(2) - X(3) + X(4) - X(5)) / (2 * X(1) + X(2) + 3 * X(3) + 5 * X(4) + X(5))
        411 POBA = POBA2 - 999999999# * (PS(6) + PS(7) + PS(8) + PS(9) + PS(10) + PS(11))
        459 POB1 = POBA
        463 P1NEWMAY = POB1
        466 P = P1NEWMAY
        1111 IF P <= M THEN 1670
        1452 M = P
        1453 PPOBA2 = POBA2
        1454 FOR KLX = 1 TO 11

            1455 A(KLX) = X(KLX)
        1456 NEXT KLX
        1557 GOTO 128
    1670 NEXT I
    1889 REM IF M<0 THEN 1999
    1900 PRINT A(1), A(2), A(3), A(4)
    1901 PRINT A(5), A(6), A(7), A(8)

    1902 PRINT A(9), A(10), A(11)

    1904 PRINT M, JJJJ, PPOBA2
1999 NEXT JJJJ

This BASIC computer program was run with qb64v1000-win [3].  The complete output through JJJJ=-31996 is shown below:

0         4         0          0
1         1         17        12
8         21         39
2.6        -32000         2.6

0         4         0          0
1         1         17        12
8         21         39
2.6        -31999         2.6

0         4         0          0
1         1         17        12
8         21         39
2.6        -31998         2.6

0         2          0          0
1         5         19        6
-2        21        39
-1999999995.666667        -31997         2.333333333333334

0         4         0          0
1         1         17        12
8         21         39
2.6        -31996         2.6

Above there is no rounding by hand; it is just straight copying by hand from the monitor screen.

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [3], the wall-clock time for obtaining the output through JJJJ=-31996 was 3 seconds, not including "Creating .EXEC file" time..

Acknowledgment

I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.

References

[1]  Yuichiro Anzai (1974).  On Integer Fractional Programming.  Journal Operations Research Society of Japan, Volume 17, No. 1, March 1974, pp. 49-66.
www..orsj.or.jp/~archiv/pdf/e_mag/Vol.17_01_049.pdf.

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

[3] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64      

[4] Jsun Yui Wong (2012, April 12).  The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Fractional Programming Problem from the Literature. http://myblogsubstance.typepad.com/substance/2012/04/12/  

A Computer Program for Integer Fractional Programming

Jsun Yui Wong

The computer program listed below seeks to solve the integer fractional programming example on pages 55-57 of Anzai [1].

Here X(1) through X(5) are integer variables, and X(6) through X(11) are slack variables.  

0 DEFDBL A-Z
2 DEFINT I, J, K

3 DIM B(99), N(99), A(99), H(99), L(99), U(99), X(1111), D(111), P(111), PS(33)
12 FOR JJJJ = -32000 TO 32000
    14 RANDOMIZE JJJJ
    16 M = -1D+37
    64 FOR J44 = 1 TO 5
        65 A(J44) = .1 + RND * 9.899999
    66 NEXT J44
    126 REM IMAR=10+FIX(RND*32000)
    128 FOR I = 1 TO 1000
        129 FOR KKQQ = 1 TO 5
            130 X(KKQQ) = A(KKQQ)
        131 NEXT KKQQ
        133 FOR IPP = 1 TO (1 + FIX(RND * 4))
            181 J = 1 + FIX(RND * 5)
            183 R = (1 - RND * 2) * A(J)
            187 X(J) = A(J) + (RND ^ (RND * 10)) * R
            188 GOTO 222
            189 REM   X(J)=A(J)+PA
            190 REM X(J)=A(J)+FIX(RND*2 )-FIX(RND*2)
            191 REM   X(J)=A(J)+FIX(RND*3)-FIX(RND*3)
        222 NEXT IPP

        224 FOR J33 = 1 TO 5

            226 X(J33) = INT(X(J33))


        227 NEXT J33

        229 X(5) = 1

        231 REM FOR J44=1 TO 5
        233 REM IF X(J44)<.1 THEN 1670
        234 REM IF X(J44)>10 THEN 1670
        235 REM NEXT J44


        240 X(6) = X(1) - 2 * X(2) + 9

        259 X(7) = -4 * X(1) - X(2) + 21

        261 X(8) = -X(1) + 3 * X(2)

        266 X(9) = 4 * X(1) + 5 * X(2) - 12

        268 X(10) = 2 * X(3) - 6 * X(4) + 21

        270 X(11) = -7 * X(3) - 4 * X(4) + 39

        281 FOR J44 = 1 TO 5

            283 IF X(J44) < 0 THEN 1670

            284 IF X(J44) > 10 THEN 1670
        285 NEXT J44

        331 FOR J44 = 6 TO 11
            332 IF X(J44) < 0 THEN PS(J44) = ABS(X(J44)) ELSE PS(J44) = 0
        333 NEXT J44
        403 POBA2 = -(-X(1) - 3 * X(2) - X(3) + X(4) - X(5)) / (2 * X(1) + X(2) + 3 * X(3) + 5 * X(4) + X(5))
        411 POBA = POBA2 - 999999999# * (PS(6) + PS(7) + PS(8) + PS(9) + PS(10) + PS(11))
        459 POB1 = POBA
        463 P1NEWMAY = POB1
        466 P = P1NEWMAY
        1111 IF P <= M THEN 1670
        1452 M = P
        1453 PPOBA2 = POBA2
        1454 FOR KLX = 1 TO 8
            1455 A(KLX) = X(KLX)
        1456 NEXT KLX
        1557 GOTO 128
    1670 NEXT I
    1889 REM IF M<0 THEN 1999
    1900 PRINT A(1), A(2), A(3), A(4)
    1901 PRINT A(5), A(6), A(7), A(8)

    1902 PRINT A(9), A(10), A(11)

    1904 PRINT M, JJJJ, PPOBA2
1999 NEXT JJJJ

This BASIC computer program was run with qb64v1000-win [3].  The complete output through JJJJ=-31995 is shown below:

0         4         0          0
1         1         17        12
0         0         0
2.6        -32000         2.6

0         4         0          0
1         1         17        12
0         0         0
2.6        -31999         2.6

2         1         0          0
1         9         12        1
0         0         0
1        -31998         1

0         4         0          0
1         1         17        12
0         0         0
2.6        -31997         2.6

0         4         0          0
1         1         17        12
0         0         0
2.6        -31996         2.6

0         4         0          0
1         1         17        12
0         0         0
2.6        -31995         2.6

Above there is no rounding by hand; it is just straight copying by hand from the monitor screen.

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [3], the wall-clock time for obtaining the output through JJJJ=-31995 was 10 seconds.

Acknowledgment

I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.

References

[1]  Y. Anzai (1974).  On Integer Fractional Programming.  Journal Operations Research Society of Japan, Volume 17, No. 1, March 1974, pp. 49-66.

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

[3] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64      

[4] Jsun Yui Wong (2012, April 12).  The Domino Method of General Integer Nonlinear Programming Applied to a Nonlinear Fractional Programming Problem from the Literature. http://myblogsubstance.typepad.com/substance/2012/04/12/