Solving a Nonconvex Generalized Geometric Programming Problem with Continuous and Discrete Free Variables

Jsun Yui Wong

The computer program listed below seeks to solve the following problem from Li and Tsai [10, p. 1190]:

Minimize      X(1) ^ 3 * X(2) ^ 1.5 * X(3) ^ 3 + X(2) ^ 5.5 * X(3) + X(1) ^ 5

subject to

         3 * X(1) + 2 * X(2) - X(3)<=7,
     
         -5<=X(1) <= 2,
   
         0<=X(2) <=4,
     
        -5<= X(3) <=-1,
       
X(1) and X(2) are integers.

"This problem is a nonconvex GGP program with continuous and discrete variables.  Current exponential transformation methods [8, 9, 11, 20 ]) developed for solving mixed-integer GGP problems can not be adopted to treat this kind of problems," Li and Tsai [10, p. 1190].  For these four references, see Li and Tsai [10, p. 1192].

The added variable X(4) below is a slack variable.  One takes note of line 330, which is 330 IF X(J99) < 0 THEN X(J99) = X(J99) ELSE X(J99) = 0.


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

    43 IF RND < .125 THEN A(1) = -5 ELSE IF RND < .143 THEN A(1) = -4 ELSE IF RND < .167 THEN A(1) = -3 ELSE IF RND < .2 THEN A(1) = -2 ELSE IF RND < .25 THEN A(1) = -1 ELSE IF RND < .333 THEN A(1) = 0 ELSE IF RND < .5 THEN A(1) = 1 ELSE A(1) = 2


    46 IF RND < .2 THEN A(2) = 0 ELSE IF RND < .25 THEN A(2) = 1 ELSE IF RND < .333 THEN A(2) = 2 ELSE IF RND < .5 THEN A(2) = 3 ELSE A(2) = 4


    58 A(3) = -5 + RND * 4


    128 FOR I = 1 TO 1000



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


            181 J = 3 + FIX(RND * 0)

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

        191 NEXT IPP

        211 IF X(1) < -5 THEN 1670

        212 IF X(1) > 2 THEN 1670

        213 IF X(2) < 0 THEN 1670

        214 IF X(2) > 4 THEN 1670


        215 IF X(3) < -5 THEN 1670

        216 IF X(3) > -1 THEN 1670


        301 X(4) = 7 - 3 * X(1) - 2 * X(2) + X(3)

        325 FOR J99 = 4 TO 4


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


        331 NEXT J99


        357 POBA = -X(1) ^ 3 * X(2) ^ 1.5 * X(3) ^ 3 - X(2) ^ 5.5 * X(3) - X(1) ^ 5 + 1000000 * (X(4))


        466 P = POBA

        1111 IF P <= M THEN 1670


        1452 M = P
        1454 FOR KLX = 1 TO 4


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

    1670 NEXT I

    1889 IF M < 4300 THEN 1999

    1900 PRINT A(1), A(2), A(3), A(4)
    1901 PRINT M, JJJJ

1999 NEXT JJJJ


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

-2         4         -3.265986310694554         0
4491.159993973288         -32000

-2         4         -3.26598632362249         0
4491.159993973288         -31999.77000000004

-2         4         -3.265986340302407         0
4491.159993973288         -31999.32000000011

-2         4         -3.265986334731874         0
4491.159993973288         -31998.94000000017

-2         4         -3.265986310366938         0
4491.159993973288         -31997.96000000033

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 [26], the wall-clock time for obtaining the output through
JJJJ=  -31997.96000000033 was 10 seconds, 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 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]  Sjirk Boon. Solving systems of nonlinear equations. Sci. Math. Num-Analysis,1992, Newsgroup Article 3529.     .

[3]  H. Chickermane, H. C. Gea (1996)  Structural optimization using a new local approximation method, International Journal for Numerical Methods in Engineering, 39, pp. 829-846.

[4]  Piya Chootinan, Anthony Chen (2006).  Constraint Handling in genetic algorithms using a gradient-based repair method.  Computers and Operations Research 33 (2006) 2263-2281.

[5]  Amir Hossein Gandomi, Xin-She Yang, Amir Hossein Alavi (2011).  Mixed variable structural optimization using Firefly Algorithm, Computers and Structures 89 (2011) 2325-2336.

[6]  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.

[7]  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.

[8]  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.

[9]  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.

[10]  Han-Lin Li, Jung-Fa Tsai (2008).  Generalized Geometric Programming:  Mixed Continuous and Discrete Free Variables.  In: C. A. Floudas,  P. M. Pardalos (editors) Encyclopedia of Optimization, Second Edition, Ebook, pp. 1185-1192.  Springer, New York.

[11]  Ming-Hua Lin, Jung-Fa Tsai (2014).  A deterministic global approach for mixed-discrete structural optimization, Engineering Optimization  (2014) 46:7, pp. 863-879.9

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

[13]  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/

[14]  Ong Kok Meng, Ong Pauline, Sia Chee Kiong, H. A. Wahab, N. Jafferi. Application of Modified Flower Pollination Algorithm on Mechanical Engineering Design Problem.  IOP Conf. Series: Materials Science and Engineering 165 (2017) 012032.

[15]  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.

[16]  Sinan Melih Nigdeli, Gebrail Bekdas, Xin-She Yang (2016). Application of the Flower Pollination Algoritm in Structural Engineering. Springer International Publishing Switzerland 2016.  www.springer.com/cda/content/document/cda.../

[17]  Gideon Oron (1979) An algorithm for optimizing nonlinear contrained zero-one problems to improve wastewater treatment, Engineering Optimization, 4:2, 109-114.

[18]  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.

[19]  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.

[20]  P. B. Thanedar, G. N. Vanderplaats (1995).  Survey of discrete variable optimization for structural design,  Journal of Structural Engineering, 121 (2), 301-306 (1995).

[21]  Jung-Fa Tsai (2005).  Global optimization of nonlinear fractional programming problems in engineering design. Engineering Optimization  (2005) 37:4, pp. 399-409.

[22]  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.

[23]  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.

[24]  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.

[25]  Jung-Fa Tsai, Ming-Hua Lin (2013). An improved framework for solving NLIPs with signomial terms in the objective or constraints to global optimality.  Computers and Chemical Engineering (2013) 53 pp. 44-54.

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

[27] 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/ 

[28] 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.

[29]  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.

[30]  B. D. Youn, K. K. Choi (2004). A new responsesurface methodology for reliability-based design optimization.  Computers and Structures 82 (2004) 241-256.