Friday, November 10, 2017

Solving in Integers Another Fractional Nonlinear Integer Programming Problem

Jsun Yui Wong

The computer program listed below seeks to solve the following integer problem:

Maximize           n1x / d1x + n2x / d2x + n3x / d3x

where

         n1x = X(1) ^ 2 - 16 * X(1) + X(2) ^ 2 - 16 * X(2) + X(3) ^ 2 - 16 * X(3) + X(4) ^ 2 - 16 * X(4) + 214,


         n2x = X(1) ^ 2 - 16 * X(1) + 2 * X(2) ^ 2 - 20 * X(2) + 3 * X(3) ^ 2 - 60 * X(3) + 4 * X(4) ^ 2 - 56 * X(4) + 586,


         n3x = X(1) ^ 2 - 20 * X(1) + X(2) ^ 2 - 20 * X(2) + X(3) ^ 2 - 20 * X(3) + X(4) ^ 2 - 20 * X(4) + 324,

         d1x = 2 * X(1) - X(2) - X(3) + X(4) + 2,

         d2x = -X(1) + X(2) + X(3) - X(4) + 10,

         d3x = X(1) ^ 2 - 4 * X(4),

subject to
     
        6<= X(1) <= 10,
       
        4<= X(2) <= 6,
     
        8<= X(3) <= 12,
     
        6<=X(4) <= 8,

        X(1) + X(2) + X(3) + X(4)<=26,

X(1) through X(4) are integer variables.

The integer problem above is based  on Example 4 in Shen, Duan, and Pei [23, p. 155].

X(5) below is a slack variable.


0 DEFDBL A-Z

2 DEFINT 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 STEP .01


    14 RANDOMIZE JJJJ
    16 M = -1D+37


    75 A(1) = 6 + RND * 4

    77 A(2) = 4 + RND * 2

    78 A(3) = 8 + RND * 4

    79 A(4) = 6 + RND * 2

    128 FOR I = 1 TO 2000




        129 FOR KKQQ = 1 TO 4

            130 X(KKQQ) = A(KKQQ)
        131 NEXT KKQQ
        133 FOR IPP = 1 TO (1 + FIX(RND * 3))



            181 J = 1 + FIX(RND * 4)

            183 r = (1 - RND * 2) * A(J)
            187 X(J) = A(J) + (RND ^ (RND * 10)) * r

        191 NEXT IPP
        193 REM GOTO 209
        196 FOR J99 = 1 TO 4

            199 X(J99) = INT(X(J99))


        204 NEXT J99


        209 IF X(1) < 6 THEN 1670

        212 IF X(1) > 10 THEN 1670

        214 IF X(2) < 4 THEN 1670

        216 IF X(2) > 6 THEN 1670
        218 IF X(3) < 8 THEN 1670

        222 IF X(3) > 12 THEN 1670

        229 IF X(4) < 6 THEN 1670
        23 IF X(4) > 8 THEN 1670


        306 X(5) = 26 - X(1) - X(2) - X(3) - X(4)



        327 XX(5) = X(5)



        330 IF X(5) < 0 THEN X(5) = X(5) ELSE X(5) = 0


        340 n1x = X(1) ^ 2 - 16 * X(1) + X(2) ^ 2 - 16 * X(2) + X(3) ^ 2 - 16 * X(3) + X(4) ^ 2 - 16 * X(4) + 214


        342 n2x = X(1) ^ 2 - 16 * X(1) + 2 * X(2) ^ 2 - 20 * X(2) + 3 * X(3) ^ 2 - 60 * X(3) + 4 * X(4) ^ 2 - 56 * X(4) + 586


        346 n3x = X(1) ^ 2 - 20 * X(1) + X(2) ^ 2 - 20 * X(2) + X(3) ^ 2 - 20 * X(3) + X(4) ^ 2 - 20 * X(4) + 324

        349 d1x = 2 * X(1) - X(2) - X(3) + X(4) + 2

        352 d2x = -X(1) + X(2) + X(3) - X(4) + 10

        355 d3x = X(1) ^ 2 - 4 * X(4)



        357 POBA = n1x / d1x + n2x / d2x + n3x / d3x + 1000000 * (X(5))



        466 P = POBA

        1111 IF P <= M THEN 1670



        1452 M = P
        1454 FOR KLX = 1 TO 5



            1456 XXX(KLX) = XX(KLX)

            1459 A(KLX) = X(KLX)
        1460 NEXT KLX
        1557 REM GOTO 128


    1670 NEXT I



    1889 IF M < -99999 THEN 1999

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

    1902 PRINT M, JJJJ

1999 NEXT JJJJ


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

6   4   8   6   0
2
-2.783333333333333   -32000       

6   4   8   6   0
2
-2.783333333333333   -31999.99   

6   4   8   6   0
2
-2.783333333333333   -31999.98   

6   4   8   6   0
2
-2.783333333333333   -31999.9700000001     

6   4   8   6   0
2
-2.783333333333333   -31999.9600000001     

Above there is no rounding by hand; it is just straight copying by hand from the monitor screen.  The candidate solution above at JJJJ=-32000, for example, is optimal, Senn, Duan, and Pei [23, p. 156].

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and qb64v1000-win [29], the wall-clock time for obtaining the output through JJJJ=  -31999.9600000001  was 2 seconds, not including the time for creating the .EXE file.   
   
Acknowledgment

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

References

[1] Yuichiro Anzai (1974). On Integer Fractional Programming. Journal of the Operations Research Society of Japan, Volume 17, No. 1, March 1974, pp. 49-66.  http://www..orsj.or.jp/~archiv/pdf/e_mag/Vol.17_01_049.pdf.
[2] Sjirk Boon. Solving systems of nonlinear equations. Sci. Math. Num-Analysis,1992, Newsgroup Article 3529.
[3]  S. S. Chadha (2002).   Fractional programming with absolute-value functions.   European Journal of Operational Research 141 (2002) pp. 233-238.
[4]  Ching-Ter Chang (2006).   Formulating the mixed integer fractional posynomial programming,  European Journal of Operational Research 173 (2006) pp. 370-386.       
[5] Piya Chootinan, Anthony Chen (2006). Constraint Handling in genetic algorithms using a gradient-based repair method. Computers and Operations Research 33 (2006) 2263-2281.
[6] Amir Hossein Gandomi, Xin-She Yang, Amir Hossein Alavi (2011). Mixed variable structural optimization using Firefly Algorithm, Computers and Structures 89 (2011) 2325-2336.
[7] Amir Hossein Gandomi, Xin-She Yang, Siamak Taratahari, Amir Hossein Alavi (2013). Firefly Algorithm with Chaos, Communications in Nonlinear Science and Numerical Sinulation 18 (2013) 89-98.
[8] Amir Hossein Gandomi, Xin-She Yang, Amir Hossein Alavi (2013). Cuckoo search algorithm: a metaheuristicapproach to solve structural optimization problem. Engineering with Computers (2013) 29:17-35.
[9] Amir Hossein Gandomi, Xin-She Yang, Amir Hossein Alavi (2013). Erratum to: Cuckoo search algorithm: a metaheuristicapproach to solve structural optimization problem. Engineering with Computers (2013) 29:245.
[10]  Chrysanthos E. Gounaris, Christodoulos A. Floudas.  Tight convex underestimators for Csquare-continuous problems: II. multivariate functions.  Journal of Global Optimization (2008) 42, pp. 69-89.
[11]  Han-Lin Li, Jung-Fa Tsai, Christodoulos A. Floudas (2008).  Convex underestimating for posynomial functions of postive variables.  Optimization Letters 2, 333-340 (2008).
[12] 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.
[13] Ming-Hua Lin, Jung-Fa Tsai (2014). A deterministic global approach for mixed-discrete structural optimization, Engineering Optimization (2014) 46:7, pp. 863-879.
[14]  Hao-Chun Lu, Han-Lin Li, Chrysanthos E. Gounaris, Christodoulos A. Floudas (2010).  Convex relaxation for solving posynomial problems.  Journal of Global Optimization (2010) 46, pp. 147-154.
[15]  Hao-Chun Lu (2012).  An efficient convexification method for solving generalized geometric problems.  Journal of Industrial and Management Optimization, Volume 8, Number 2, May 2012, pp. 429-455.
[16]  Hao-Chun Lu (2017).  Improved logarithnic linearizing method for optimization problems with free-sign pure discrete signomial terms. Journal of Global Optimization (2017) 68, pp. 95-123.
[17] Mathworks. Solving a mixed integer engineering design problem using the genetic algorithm – MATLAB & Simulink Example.
https://www.mathworks.com/help/gads/examples/solving-a-mixed-integer-engineering-design-problem-using-the-genetic-algorithm.html/
[18] 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.
[19] Sinan Melih Nigdeli, Gebrail Bekdas, Xin-She Yang (2016). Application of the Flower Pollination Algoritm in Structural Engineering. Springer International Publishing Switzerland 2016. http://www.springer.com/cda/content/document/cda…/
[20] Gideon Oron (1979) An algorithm for optimizing nonlinear contrained zero-one problems to improve wastewater treatment, Engineering Optimization, 4:2, 109-114.
[21] 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.
[22] c. R. Seshan, V. G. Tikekar (1980) Algorithms for Fractional Programming. Journal of the Indian Institute of Science 62 (B), Feb. 1980, Pp. 9-16.
[23]  Pei-Ping Shen, Yun-Peng Duan, Yong-Gang Pei.  A simplicial branch and duality bound algorithm for the sum of convex-convex ratios problem.  Journal of Computational and Applied Mathematics 223 (2009) 145-158.
[24] P. B. Thanedar, G. N. Vanderplaats (1995). Survey of discrete variable optimization for structural design, Journal of Structural Engineering, 121 (2), 301-306 (1995).
[25] Jung-Fa Tsai (2005). Global optimization of nonlinear fractional programming problems in engineering design. Engineering Optimization (2005) 37:4, pp. 399-409.
[26] Jung-Fa Tsai, Ming-Hua Lin (2007). Finding all solutions of systems of nonlinear equations with free variables. Engineering Optimization (2007) 39:6, pp. 649-659
[27] 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.
[28] 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.
[29] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64.
[30] 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/
[31]  Helen Wu (2015).  Geometric Programming.  https://optimization.mccormick.northwstern.edu/index.php/Geometric_Programming.
[32] Xin-She Yang, Christian Huyck, Mehmet Karamanoglu, Nawaz Khan (2014). True global optimality of the pressure vessel design problem: A benchmark for bio-inspired optimisation algorithms.  https://arxiv.org/pdf/1403.7793.pdf.
[33] Xin-She Yang, Amir Hossein Gandomi (2012). Bat algorithm: a novel approach for global engineering optimization. Engineering Computations: International Journal for Computer-Aided Engineering and Software, Vol. 20,No. 5, 2012, pp. 461-483.
[35] B. D. Youn, K. K. Choi (2004). A new responsesurface methodology for reliability-based design optimization.  Computers and Structures 82 (2004) 241-256.

No comments:

Post a Comment