Abstract
The article presents solution procedure of geometric programming with imprecise coefficients. We have considered problems with imprecise data as a form of an interval in nature. Many authors have solved the imprecise problem by geometric programming technique in a different way. In this paper, we introduce parametric functional form of an interval number and then solve the problem by geometric programming technique. The advantage of the present approach is that we get optimal solution of the objective function directly without solving equivalent transformed problems. Numerical examples are presented to support of the proposed approach.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Geometric programming (GP) is an efficient technique for solving a particular type of nonlinear optimization problems. It has interesting applications in different fields of Engineering, Science, Management, etc. Duffin et al. [1] put a foundation stone to solve applications of engineering problems by developing basic theories of geometric programming. Examples of application of GP are reliability optimization (Govil [2, 3], Mahapatra and Roy [4], Mahapatra and Mahapatra [5]), engineering design (Choi and Bricker [6], Prasad et al. [7]), integrated circuit design (Chu and Wong [8], Hershenson et al. [9], Mandal and Visvanathan [10]), inventory management (Cheng [11], Kim and Lee [12], Lee [13], Jung and Klein [14], Abuo El Ata et al. [15], Worrall and Hall [16], Liu [17]), project management (Scott and Jefferson [18]), etc. The most remarkable property of geometric programming is that a problem with highly nonlinear constraints can be transformed equivalently into a problem with only linear constraints. This is due to a strong duality theorem for geometric programming problems. For posynomial form of the primal problem, there exists a global minimizing solution to that problem, and this solution can be obtained by solving the dual maximization. The development of a powerful solution technique for GP is due to the linear dual constraints as the linearly constrained programs are generally easier to solve than the ones with nonlinear constraints.
Several researchers (Avriel and Dembo [19], Beightler and Philips [20], Duffin and Peterson [21], Duffin et al. [1], Fang et al. [22], Kyparisis [23], Kortanek and No [24], Kortanek et al. [25], Maranas and Floudas [26], Peterson [27], Rajgopal [28], Rajgopal and Bricker [29, 30], Yang and Bricker [31], Zhu et al. [32]) developed efficient and effective algorithms for solving the geometric programming problems when the objective and constraint coefficients are known. The problem parameters of many applications of geometric programming problems are estimates of actual values (Beightler and Philips [20]). In real life, the data cannot be recorded or collected precisely due to human errors or some unexpected situations. Therefore, there are many cases in which these coefficients may not be presented in a precise manner. The idea of fuzziness (impreciseness) in GP, i.e. fuzzy geometric programming, has been proposed by Cao [33]. There is an essential and fundamental book by Cao dealing with fuzzy geometric programming [34]. Yang and Cao [35] presented an outline of the origin and applications of fuzzy geometric programming. An alternative approach is to apply interval estimates [36] instead of single values to represent the uncertain parameters. Liu [37] developed a solution method of posynomial geometric programming with interval exponents and coefficients. A pair of two-level mathematical programs is formulated, and hence it solves the pair of problems using the geometric programming technique to obtain the objective value as an interval number. Ojha and Das [38] developed a solution procedure using GP technique by splitting the cost coefficients, constraint coefficients and exponents with the help of binary numbers.
In this paper, we consider posynomial geometric programs and develop a solution procedure that is able to calculate the optimal objective value for the problem, where at least one of the parameters is an interval number. We present parameters as an interval in parametric function form and then solve this parametric problem by a GP technique which is called the parametric geometric programming (PGP). A parametric mathematical program is formulated to calculate the different value of the objective function for different value of the parameter. The proposed procedure is more effective and interesting since we get different solutions of the problem using functional form of an interval parameter for different value of parameters. We develop a solution procedure to solve such nonlinear programming problems using the GP technique. The main advantage of the presented procedure is that it is not required to form and solve two-level mathematical programming which is time consuming.
The rest of this paper is organized as follows: In Sect. 2, a preliminary idea of GP is presented. Section 3 briefly states the posynomial geometric programming problem with imprecise parameters. Then parametric mathematical problem is formulated for calculating the objective value. In Sect. 4, we have used two examples based on Dinkle and Tretter [39] (later on Liu [40] used these problems for imprecise coefficients using the GP technique) to explain the idea of this paper. Finally, in Sect. 5, some conclusions are drawn from the discussion.
2 Geometric Programming
Let us consider a constrained posynomial geometric programming problem in the following form:
The posynomial function contains T 0 terms in the objective function and T m terms in the inequality constrains. The coefficient of each term is positive by definition of posynomial. Let T=T 0+T 1+⋯+T m be the total number of terms in the primal program. The degree of difficulty (DD) is defined as DD=Total no. of terms−(Total no. of variables−1)=T−(N+1).
The dual problem (with the objective function d(w), where w≡{w(w mt ), ∀m=0,1,…,M; t=1,2,…,T m } is the decision vector) of the geometric programming problem (1) for the general posynomial case is as follows:
-
Case I:
For T≥N+1, the dual program presents a system of linear equations for the dual variables where the number of linear equations is either less than or equal to the number of dual variables. A solution vector exists for the dual variable (Beightler and Philips [20]).
-
Case II:
For T<N+1, the dual program presents a system of linear equations for the dual variables where the number of linear equations is greater than the number of dual variables. In this case, generally, no solution vector exists for the dual variables. However, one can get an approximate solution vector for this system using either the least squares or the linear programming method.
3 Imprecise Geometric Programming with Solution Procedure
By the definition of posynomial, all the coefficients are positive in nature. In model (1), all the coefficients are considered as precise. Intuitively, if any of the coefficients is imprecise, the problem cannot be solved by the GP technique. Furthermore, when the right-hand side value becomes an interval number rather than a single value, then it is not so straightforward to convert the constraint to the standard form like model (1). For an imprecise coefficient, we present the problem with an interval coefficient and its solution procedure in this section.
3.1 Geometric Programming with Interval Coefficient
Suppose the right-hand sides of the constraints in the geometric program (1) are replaced by b m ’s which are all positive numbers. If b m =1 for all m, then this new geometric program coincides with the standard one. Otherwise, the constraints need some amendment to be consistent with model (1). Let \(\hat{c}_{0t},\hat{c}_{mt}\) and \(\hat{b}_{m}\) denote the interval counterparts of c 0t , c mt , b m , respectively. The posynomial geometric programming problem with imprecise parameters is of the following form:
where \(\hat{c}_{0t}\in [ c_{0t}^{L},c_{0t}^{U} ] ,~\hat{c}_{mt}\in [ c_{mt}^{L},c_{mt}^{U} ] ,~\hat{b}_{m}\in [b_{m}^{L},b_{m}^{U} ] ,~c_{0t}^{L},~c_{mt}^{L},~b_{m}^{L}>0\) for all m and t.
Definition 3.1
(Interval-valued function)
Let a>0,b>0 and consider the interval [a,b]. From a mathematical point of view, any real number can be represented on a line. Similarly, we can represent an interval by a function. If the interval is of the form [a,b], the interval-valued function is taken as
3.2 Proposed Solution Technique of Imprecise Geometric Programming
The posynomial functions f m (x), m=0,1,…,M, contain T m terms in the objective function and inequality constraints. By the definition of the posynomial, all the coefficients c mt for m=0,1,…,M and t=1,2,…,T m are positive. The model (3) can be written in the form
The following theorem gives the idea that the solution of (3) is possible in the form of parametric approach, when the coefficients are the interval values of the posynomial GP problem.
Theorem 3.1
The parametric nonlinear programming problem
provides the solution of the interval-valued nonlinear programming problem
where \(\hat{c}_{0t}\in [ c_{0t}^{L},c_{0t}^{U} ] \), \(\hat{c}_{mt}\in [ c_{mt}^{L},c_{mt}^{U} ] \), \(\hat{b}_{m}\in [b_{m}^{L},b_{m}^{U} ] \), \(c_{0t}^{L}\), \(c_{mt}^{L}\), \(b_{m}^{L}>0\) for all m and t.
Proof
The given problem (3) can be written as follows:
For any t, if we take \(\alpha_{t}\in [ c_{0t}^{L},c_{0t}^{U} ]\), \(\beta_{t}\in [ c_{mt}^{L},c_{mt}^{U} ]\) and \(\gamma_{t}\in [ b_{m}^{L},b_{m}^{U} ] \), the problem (6) reduces to
where \(\alpha_{t}\in [ c_{0t}^{L},c_{0t}^{U} ] \), \(\beta_{t}\in [ c_{mt}^{L},c_{mt}^{U} ]\) and \(\gamma_{t}\in [b_{m}^{L},b_{m}^{U} ]\).
For any fixed m, let us consider the interval-valued function \(h_{m}(p)=a_{m}^{1-p}b_{m}^{p}\) for p∈[0,1] for an interval α m ∈[a m ,b m ]. Since h m (p) is a strictly monotone increasing and continuous function, the above equation reduces to
where \(\alpha_{t}\in (c_{0t}^{L})^{1-p}(c_{0t}^{U})^{p}\), \(\beta_{t}\in (c_{mt}^{L})^{1-p}(c_{mt}^{U})^{p}\), \(\gamma_{t}\in (b_{m}^{L})^{p}(b_{m}^{U})^{1-p}\) and p∈[0,1]. Since \(h_{m}(p)~=a_{m}^{1-p}b_{m}^{p}\) for p∈[0,1] is a strictly monotone and continuous function, its inverse exists. Let δ be the inverse of h m (p), then \(p=\frac{\log \delta -\log a_{m}}{\log b_{m}-\log a_{m}}\); therefore, we can find any particular α m for some values of p∈[0,1].
Thus we can find the solution of the given problem only by solving the parametric problem, which can be written as follows:
□
Hence, according to Theorem 3.1, one can derive the optimal solution of the problem (3) by solving problem (4). The solution of problem (9) by the GP technique is called PGP.
4 Numerical Examples
In this section, two examples are given to illustrate the proposed methodology presented in this paper using the GP technique.
Example 4.1
This problem taken from Dinkle and Tretter [39] is to perform sensitivity analysis using interval arithmetic by the GP technique. The associated mathematical form of the problem is also investigated by Liu [40]. We also consider here the same form of that problem as follows:
where (20,70) represents the interval of the coefficient in the objective function.
According to Theorem 3.1, problem (10) can be transformed into the following parametric form:
Using the parametric geometric programming technique, the solution of problem (11) can be obtained by the solution of the corresponding dual problem:
Since the DD of problem (11) is 1, first we find the following relations in terms of w 12 using constraint equations of the dual problem
Therefore, the dual problem is of the following form:
Taking logarithms of both sides and using the differential calculus rules for finding the optimal solution of the above problem, we get the optimal \(w_{12}^{\ast }\) which satisfies the relation given below:
Then using the optimal \(w_{12}^{\ast }\) in (12), we get the optimal \(w_{01}^{\ast }\), \(w_{02}^{\ast }\), \(w_{03}^{\ast}\) and \(w_{11}^{\ast }\).
Now the primal–dual relations are as follows:
Form the above relations, we obtain the optimal solutions of the primal variables as follows:
The optimal solutions of the problem for different values of the parameter p are presented in Table 1.
Example 4.2
The second problem is taken from Liu \([40]\) where the parameters in the objective function and constraints are interval numbers as follows:
Based on Theorem 3.1, the above problem (13) can be written in parametric form as follows:
The dual problem of problem (14) using parametric geometric programming is obtained as follows:
Since the DD of problem (13) is 1, we first find the solution of the system of linear equations of the dual problem in terms of one variable as follows:
Now the dual problem can be written in terms of w 22 as follows:
To find the optimal value of w 22, taking logarithms and applying the rules of differential calculus for the variable w 22, we get
Numerical solutions of this problem are presented in Table 2.
For p=0, the lower bound of the interval value of the parameter is used to find the optimal solution. Case p=1 means that the upper bound of the interval parameter is used for the optimal solution. These two values yield the lower and upper bounds of the optimal solution. However, one can get the intermediate optimal result using a proper value of p which is the main advantage of the proposed technique. We have presented optimal solutions of Examples 4.1 and 4.2 in Tables 1 and 2, respectively, for some intermediate values of p∈(0,1) using the proposed parametric geometric programming technique; this is the main advantage of the proposed technique.
5 Conclusions
Geometric programming has undergone different development in theoretical and practical applications in various fields. Most of the researchers have developed the GP technique based on the assumption that the parameters are precisely known but the scenario is different in real life. In this paper, we have developed a method to find the optimal solution by the GP technique when some parameters are imprecise in nature. There are very few paper (Cao [33, 34], Yang and Cao [35], Liu [17, 37, 40], Ojha and Das [38], Mahapatra and Mahapatra [5]) where the impreciseness of parameters is considered. The solution procedure of these papers by the GP technique states the interval value of the objective function and is also time consuming. But the technique that we have presented will take minimal time and the problem can be solved easily without constructing equivalent problems. The ability of calculating the cost coefficients and constraint coefficients developed in this paper might help lead to more realistic modeling efforts in engineering design areas.
References
Duffin, R.J., Peterson, E.L., Zener, C.: Geometric Programming—Theory and Applications. Wiley, New York (1967)
Govil, K.K.: Geometric programming method for optimal reliability allocation for a series system subject to cost constraint. Microelectron. Reliab. 23(5), 783–784 (1983)
Govil, K.K.: Optimal maintainability allocation using the geometric programming method. Microelectron. Reliab. 32(1/2), 265–266 (1992)
Mahapatra, G.S., Roy, T.K.: Optimal fuzzy reliability for a series system with cost constraints using fuzzy geometric programming. Tamsui Oxf. J. Manag. Sci. 22(2), 51–61 (2006)
Mahapatra, B.S., Mahapatra, G.S.: Reliability and cost analysis of series system models using fuzzy parametric geometric programming. Fuzzy Inf. Eng. 2(4), 399–411 (2010)
Choi, J.C., Bricker, D.L.: Effectiveness of a geometric programming algorithm for optimization of machining economics models. Comput. Oper. Res. 10, 957–961 (1996)
Prasad, A.V.S.R.K., Rao, P.N., Rao, U.R.K.: Optimal selection of process parameters for turning operations in a CAPP system. Int. J. Prod. Res. 35, 1495–1522 (1997)
Chu, C., Wong, D.F.: VLSI circuit performance optimization by geometric programming. Ann. Oper. Res. 105, 37–60 (2001)
Hershenson, M.D., Boyd, S.P., Lee, T.H.: Optimal design of a CMOS op-amp via geometric programming. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 20, 1–21 (2001)
Mandal, P.P., Visvanathan, V.: FCMOS op-amp sizing using a geometric programming formulation. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 20, 22–38 (2001)
Cheng, T.C.E.: An economic order quantity model with demand-dependent unit production cost and imperfect production process. IIE Trans. 23, 23–28 (1991)
Kim, D., Lee, W.J.: Optimal joint pricing and lot sizing with fixed and variable capacity. Eur. J. Oper. Res. 109, 212–227 (1998)
Lee, W.J.: Determining order quantity and selling price by geometric programming: Optimal solution, bounds, and sensitivity. Decis. Sci. 24, 76–87 (1993)
Jung, H., Klein, C.M.: Optimal inventory policies for an economic order quantity model with decreasing cost functions. Eur. J. Oper. Res. 165, 108–126 (2005)
Abuo-El-Ata, M.O., Fergany, H.A., El-Wakeel, M.F.: Probabilistic multi-item inventory model with varying order cost under two restrictions: A geometric programming approach. Int. J. Prod. Econ. 83, 223–231 (2003)
Worrall, B.M., Hall, M.A.: The analysis of an inventory control model using posynomial geometric programming. Int. J. Prod. Res. 20, 657–667 (1982)
Liu, S.T.: Using geometric programming to profit maximization with interval coefficients and quantity discount. Appl. Math. Comput. 209, 259–265 (2009)
Scott, C.H., Jefferson, T.R.: Allocation of resources in project management. Int. J. Syst. Sci. 26, 413–420 (1995)
Avriel, M., Dembo, R., Passy, U.: Solution of generalized geometric programs. Int. J. Numer. Methods Eng. 9, 149–168 (1975)
Beightler, C.S., Philips, D.T.: Applied Geometric Programming. Wiley, New York (1976)
Duffin, R.J., Peterson, E.L.: Geometric programming with signomials. J. Optim. Theory Appl. 11, 3–35 (1973)
Fang, S.C., Peterson, E.L., Rajasekera, J.R.: Controlled dual perturbations for posynomial programs. Eur. J. Oper. Res. 35, 111–117 (1988)
Kyparisis, J.: Sensitivity analysis in geometric programming: Theory and computations. Ann. Oper. Res. 27, 39–64 (1990)
Kortanek, K.O., No, H.: A second order affine scaling algorithm for the geometric programming dual with logarithmic barrier. Optimization 23, 303–322 (1992)
Kortanek, K.O., Xu, X., Ye, Y.: An infeasible interior-point algorithm for solving primal and dual geometric programs. Math. Program. 76, 155–181 (1997)
Maranas, C.D., Floudas, C.A.: Global optimization in generalized geometric programming. Comput. Chem. Eng. 21, 351–369 (1997)
Peterson, E.L.: The fundamental relations between geometric programming duality, parametric programming duality, and ordinary Lagrangian duality. Ann. Oper. Res. 105, 109–153 (2001)
Rajgopal, J.: An alternative approach to the refined duality theory of geometric programming. J. Math. Anal. Appl. 167, 266–288 (1992)
Rajgopal, J., Bricker, D.L.: Posynomial geometric programming as a special case of semi-infinite linear programming. J. Optim. Theory Appl. 66, 455–475 (1990)
Rajgopal, J., Bricker, D.L.: Solving posynomial geometric programming problems via generalized linear programming. Comput. Optim. Appl. 21, 95–109 (2002)
Yang, H.H., Bricker, D.L.: Investigation of path-following algorithms for signomial geometric programming problems. Eur. J. Oper. Res. 103, 230–241 (1997)
Zhu, J., Kortanek, K.O., Huang, S.: Controlled dual perturbations for central path trajectories in geometric programming. Eur. J. Oper. Res. 73, 524–531 (1992)
Cao, B.Y.: Solution and theory of question for a kind of fuzzy positive geometric program. In: Proc. 2nd IFSA Congress, Tokyo, vol. 1, pp. 205–208 (1987)
Cao, B.Y.: Fuzzy Geometric Programming. Applied Optimization, vol. 76. Springer, Berlin (2002)
Yang, H., Cao, B.Y.: Fuzzy geometric programming and its application. Fuzzy Inf. Eng. 2(1), 101–112 (2010)
Wu, H.C.: Duality theory for optimization problems with interval-valued objective functions. J. Optim. Theory Appl. 144, 615–628 (2010)
Liu, S.T.: Posynomial geometric programming with interval exponents and coefficients. Eur. J. Oper. Res. 186, 17–27 (2008)
Ojha, A.K., Das, A.K.: Geometric programming problem with coefficients and exponents associated with binary numbers. Int. J. Comput. Sci. 7(1/2), 49–55 (2010)
Dinkle, J.J., Tretter, M.J.: An interval arithmetic approach to sensitivity analysis in geometric programming. Oper. Res. 35, 866–869 (1987)
Liu, S.T.: Posynomial geometric programming with parametric uncertainty. Eur. J. Oper. Res. 168, 345–353 (2006)
Acknowledgements
The authors would like to express their gratitude to the Editor-in-Chief and Referees for their encouragement and constructive comments in revising the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Mordecai Avriel.
Rights and permissions
About this article
Cite this article
Mahapatra, G.S., Mandal, T.K. Posynomial Parametric Geometric Programming with Interval Valued Coefficient. J Optim Theory Appl 154, 120–132 (2012). https://doi.org/10.1007/s10957-012-9996-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-012-9996-6