# Geometric Programming with Discrete Variables Subject to Max-Product Fuzzy Relation Constraints

Authors: Zejian Qin; Bingyuan Cao; Shu-Cherng Fang; Xiao-Peng Yang
Journal: Discrete Dynamics in Nature and Society
 (2018)

---

## Abstract

The problem of geometric programming subject to max-product fuzzy relation constraints with discrete variables is studied. The major difficulty in solving this problem comes from nonconvexity caused by these product terms in the general geometric function and the max-product relation constraints. We proposed a 0-1 mixed integer linear programming model and adopted the branch-and-bound scheme to solve the problem. Numerical experiments confirm that the proposed solution method is effective.


---

## Body

## 1. Introduction

Since fuzzy relation equations with max-min composition were firstly introduced by Sanchez [1–3], they have attracted much research attention. As an extension, fuzzy relation inequalities associated with max-t-norm were also studied. As demonstrated in [4], the complete solution set of max-t-norm fuzzy relation equations can be completely determined by a unique maximum solution and a finite number of minimal solutions. It is easy to compute the maximum solution, but finding all the minimal solutions is an NP-hard problem [4–6]. It is worth mentioning that Li and Fang [5] provided a complete survey and detailed discussion on fuzzy relational equations. They studied fuzzy relational equations in a general lattice-theoretic framework and introduced classification of basic fuzzy relational equations.Meanwhile, optimization problems subject to fuzzy relation equations or inequalities were introduced and studied. Fang and Li [7] firstly investigated a linear optimization problem with a consistent system of max-min equations. They converted it into a 0-1 integer programming problem and solved this by the branch-and-bound method. Then it became a unified framework to deal with the resolution of linear optimization problem subject to a system of fuzzy relational equations with max-t-norm composition. And linear programming problem with fuzzy relation constraints became a hot topic for further research [8–10]. Guo and Xia [11] proposed a method to accelerate the resolution of this problem. Zhang et al. [12] studied a linear objective optimization problem with max-min fuzzy relation inequalities.For nonlinear programming with fuzzy relation constraints, many achievements were gained. Wang et al. [13] first studied latticized linear programming subject to max-min fuzzy relation inequalities. In [14] Li and Fang made a further study on the latticized linear optimization (LLO) problem and its variant, which are a special class of optimization problems constrained by fuzzy relational equations or inequalities. Yang and Cao [15] and Wu [16] considered geometric optimization problems with single-term exponents under fuzzy relation equation constraints with max-min composition, where the objective function is Z=⋁i=1m(ci∧xiri). Zhou and Ahat [17] investigated similar problem where the composition was replaced by max-product. Yang et al. [18] investigated min-max programming problem subject to fuzzy relation inequality constraints with a special composition of addition-min. Yang et al. [19] studied the single-variable term semi-latticized geometric programming subject to max-product fuzzy relation equations. As important nonlinear programming, geometric programming with fuzzy relational constraints attracted some researchers’ attention. Yang and Cao [20] proposed a monomial geometric programming subject to max-min fuzzy relation equations with the objective function being z=c∏j=1nxjrj. Shivanian and Khorram [21] considered monomial geometric programming subject to fuzzy relation inequalities with max-product composition. Zhou et al. [22] investigated a special posynomial geometric programming problem subject to max-min fuzzy relation equations, in which the exponents of each variable are all nonpositive or nonnegative real numbers. Aliannezhadi et al. [23] investigated a monomial geometric programming objective function subject to bipolar max-product fuzzy relation constraints. All the objective functions of these optimization problems are special geometric functions. Because of the nonconvexity and complexity, problems with a general geometric objective function have not been studied. At the same time, the data in the real world could often be discrete instead of continuous. In particular, statistics data are often discrete numbers associated with real facts. Therefore, in this paper we study geometric programming subject to max-product fuzzy relational constraints, in which the objective function is a general geometric function and all the variables are of discrete values.The rest of the paper is organized as follows. In Section2, we introduce some basic concepts. A method to transform the original problem into a linear mix-integer programming model is proposed in Section 3. Numerical experiments are given to illustrate the effectiveness of the proposed solution method in Section 4. A simple conclusion is arranged in Section 5.


## 2. Problem

Consider the following geometric programming problem subject to max-product fuzzy relational constraints with discrete variables:(1)minfx=∑l∈Lcl∏j∈Jxjrl,j,s.t.⋁j∈Jai,jxj~bi,∀i∈I,xj∈dj1,dj2,…,djh⊂0,1∀j∈J,where I={1,2,…,m},J={1,2,…,n}, and L={1,2,…,p} are three index sets, and cl,rl,j∈R, ai,j∈(0,1] for i∈I,j∈J,l∈L. The notation “⋁” denotes the maximum operator and “~” can be “≤”, “≥”, or “=” for upper-bound constraints, lower-bound constraints, and equation constraints, respectively.We analyze the three kinds of max-product fuzzy relation constraints with discrete variables first.(i) For an upper-bound constraint:(2)⋁j∈Jai,jxj≤bi.It can be written in n constraints:(3)ai,jxj≤bi,i.e.,xj≤biai,j,j∈J.Hence xj≤⋀i∈I(bi/ai,j), where the notation “⋀” denotes the minimum operator. Combining with the discrete requirements: (4)xj∈dj1,dj2,…,djh,j∈J,we have (5)xj∈dj1,dj2,…,djh∩0,⋀i∈Ibiai,j,j∈J.By checking {dj1,dj2,…,djh} and ⋀i∈I(bi/ai,j), we can reset the discrete values of each variable.(ii) For an equation constraint:(6)⋁j∈Jai,jx=bi.It can be written as an upper-bound constraint and a lower-bound constraint, that is, (7)⋁j∈Jai,jxj≤bi,⋁j∈Jai,jxj≥bi.From (i) we know that the upper-bound constraint can be included in a new set of discrete values, and the lower-bound constraint can be grouped into other lower-bound constraints. Consequently, the constraints can all be transformed into max-product lower-bound constraints with discrete variables. Without loss of generality, in this paper we consider the following geometric programming problem subject to max-product fuzzy relational inequalities with discrete variables:(8)minfx=∑l∈Lcl∏j∈Jxjrl,j,s.t.⋁j∈Jai,jxj≥bii∈I,xj∈dj1,dj2,…,djh⊂0,1j∈J,where ai,j∈(0,1],bi∈[0,1],cl,rl,j∈R, for i∈I,j∈J,l∈L.The major difficulty in solving problem (8) comes from the nonconvexity caused by the cross-product terms in the objective function and the max operation in the fuzzy inequalities. We will introduce methods to transform the original problem into an equivalent 0-1 linear mixed integer programming problem and adopt the branch-and-bound scheme to find an optimal solution.


## 3. Linear Reformulation

### 3.1. Treating Geometric Function with Multivalued Discrete Variables

For solving problem (8), the first step is to convert each multivalued variable into 0-1 valued by considering(9)xj=∑k∈Kdjkujk,∑k∈Kujk=1,where K={1,2,…,h} is an index set and ujk∈{0,1} for j∈J and k∈K.It is important to know that thenh binary variables of {ujk},j∈J and k∈K, induced by (9), may cause heavy computational burden when n and h become large. To avoid this burden, Li et al. [24] proposed a logarithmic approach which needs only nlog2h binary variables (⌈·⌉ denotes the ceiling function), nh nonnegative variables, and nlog2h linear equations to represent the n discrete variables with h values by considering(10)λjw=∑k∈Ktw,kujk,j∈J,w∈W,where W={1,2,…,⌈log2h⌉} is an index set; λjw∈{0,1} is a binary variable; ujk≥0 is now a nonnegative variable, for j∈J,k∈K and w∈W; and tw,k are binary variables obtained by solving the equations of 1+∑w∈W2w-1tw,k=k for k∈K.The next step is to reformulate the objective function. Remembering thatujk∈{0,1} and ∑k∈Kujk=1, we denote zl,1=x1rl,1 for l∈L; then we have(11)zl,1=∑k=1hu1kd1krl,1,l∈L.Moreover, we denote(12)zl,j=zl,j-1xjrl,j,l∈L,j∈J∖1. Then the objective function can be expressed as(13)fx=∑l∈Lcl∏j∈Jxjrl,j=∑l∈Lclzl,n.In this way we can express the objective function of problem (8) as a linear function in {zl,n∣l∈L}. Note that the expression (12) is nonlinear, but by adopting the approach in [25], we can express them by using linear inequalities in {ujk∈{0,1}∣k∈K,j∈J∖{1}} in the next result.Lemma 1.
Givenl∈L,k∈K,j∈J∖{1}, the product term zl,j=zl,j-1xjrl,j, with xj∈{dj1,dj2,…,djh}, can be expressed by the following linear inequalities in {ujk} and {zl,j}:(14)djkrl,jzl,j-1-Ml,j1-ujk≤zl,j≤djkrl,jzl,j-1+Ml,j1-ujk,where ujk is defined in (9), and Ml,j is a sufficient large positive value such that(15)Ml,1=⋁k∈Kd1krl,1,Ml,j=Ml,j-1⋁k∈Kdjkrl,jj∈J∖1,l∈L.Proof.
Assume thatxj=djk∗ for a particular k∗. From (9), we have ujk∗=1 and other ujk=0.
(i) Fork=k∗, inequality (14) can be converted into the following equation: (16)zl,j=zl,j-1djk∗rl,j=zl,j-1xjrl,j.
(ii) Fork≠k∗, inequality (14) can transformed as(17)djkrl,jzl,j-1-Ml,j≤zl,j≤djkrl,jzl,j-1+Ml,j.Actually, from (i), we have (18)zl,j=zlj-1xjrl,j=⋯=zl,1x2rl,2⋯xjrl,j=∏s≤jxsrl,s.From (15), we know Ml,j=∏s≤j(⋁k∈Kdjkrl,j) and xj∈{dj1,dj2,…,djh}; therefore, (19)zl,j≤Ml,j.Hence, (20)djkrl,jzl,j-1-Ml,j≤zl,j-1-Ml,j-1djkrl,j≤0≤zl,j,zl,j≤Ml,j≤djkrl,jzl,j-1+Ml,j,djkrl,jzl,j-1-Ml,j≤zl,j≤djkrl,jzl,j-1+Ml,j.
From the above, we can see, whenk=k∗, (14) will be converted into (12); when k≠k∗, (14) will be converted into the redundant constraints (17). Consequently (12) can be expressed by (14).


### 3.2. Treating Max-Product Fuzzy Relation Inequalities

Firstly we recall some basic concepts and important properties of the max-product fuzzy inequalities:(21)⋁j∈Jai,jxj≥bii∈I.Denote A=(ai,j)m×n∈(0,1]n and x=(x1,x2,…,xn)T∈[0,1]n,b=(b1,b2,…,bm)T∈[0,1]m; “∘” represent the max-product composite operation; then a system of max-product fuzzy relation inequalities can be represented in the following matrix form:(22)A∘x≥b.The set of all the solutions of system (22) is called its solution set, denoted by XA,b,≥={x∣A∘x≥b}. If XA,b,≥≠∅, we say the system (22) is consistent; otherwise it is inconsistent [4, 26].Lemma 2 (see [5, 26, 27]).
LetA∘x≥b be a system of consistent max-product fuzzy relation inequalities; if x1∈X(A,b,≥) and x1≤x2∈[0,1]n, then we know x2∈X(A,b,≥).Definition 3 (see [26]).
A solutionx^∈X(A,b,≥) is said to be the maximum or greatest solution if and only if x≤x^ for all x∈X(A,b,≥). A solution xˇ∈X(A,b,≥) is said to be a minimal solution if and only if x≤xˇ implies x=xˇ for any x∈X(A,b,≥).Obviously, if the maximum solution of (22) exists, it is unique and x^=(1,1,…,1).Theorem 4 (see [26, 27]).
LetA∘x≥b be a system of max-product fuzzy relation inequalities; then it is consistent if and only if x^=(1,1,…,1)∈X(A,b,≥). Moreover, if the system is consistent, the solution set X(A,b,≥) can be fully determined by one maximum solution and a finite number of minimal solutions, that is, (23)XA,b,≥=⋃xˇ∈XˇA,b,≥x∈0,1n∣xˇ≤x≤x^,where Xˇ(A,b,≥) is the set of all minimal solutions of (22).The feasible domain restricted by the max-product fuzzy relation inequalities (22) can be fully characterised by the solution set X(A,b,≥). Actually, if we know all the minimal solutions, then the solution set X(A,b,≥) can be expressed. The main problem we face is computing all the minimal solutions of system (22). However this is an NP-hard problem [5, 26]. Hence we introduce a method to find all the potential minimal solutions instead of minimal solutions.Definition 5 (see [26]).
MatrixQ=(qi,j)m×n is called a discrimination matrix of (22) with(24)qij=biaij,aij≥bi,0,aij<bi.Theorem 6 (see [26]).
Let matrixQ be the discrimination matrix of the system (22). The system is consistent if and only if, for any i∈I, there exists at least one ji∈J such that qi,ji≠0.Definition 7 (see [27]).
LetQ be the discrimination matrix of the system (22) and matrix S=(si,j)m×n, where si,j∈{0,qi,j}. We call S a solution matrix if, for any i∈I, there exists a unique ji∈J such that si,ji≠0.LetS be a solution matrix of the system (22); denote xS=(x1S,x2S,…,xnS), where(25)xjS=⋁i∈Isi,j.Theorem 8 (see [27]).
LetS be a solution matrix of the system (22) and xS be defined by (25); then xS∈XA,b,≥. Moreover, for any x∈X(A,b,≥), there exists a solution matrix S with a corresponding xS such that xS≤x.From Theorem8, we know that, for any minimal solution xˇ of (22), the solution matrix S and its corresponding xS can be formed such that xS=xˇ. Then the feasible domain restricted by the max-product fuzzy relation inequalities constraints (22) can be expressed as(26)x∈XA,b,≥=⋃xˇ∈XˇA,b,≥x∣xˇ≤x≤x^=⋃S∈SQx∣xS≤x≤x^,where S(Q) denotes the set of all the solution matrix determined by discrimination matrix Q of system (22), and xS is a solution corresponding to the solution matrix S.Consider the definition of (25); we see that, for any solution matrix S and its corresponding xS, the inequality x≥xS is equivalent to the following constraints:(27)xj≥⋁ı∈Isi,j,j∈J,  i.e.,xj≥si,j,i∈I,j∈J.At the same time, we bring in mn binary variables vi,j∈{0,1}, for i∈I and j∈J; the element of matrix S can be expressed as(28)sij=vi,jqi,j,i∈I,j∈J,∑j∈Jpi,jvi,j=1,i∈I,j∈J,where vi,j∈{0,1} and pi,j=1,qij≠0;0,qij=0.Therefore, the feasible domain restricted by (22) can be characterised by(29)∑j∈Jpijvi,j=1,i∈I,(30)xj≥qi,jvi,j,i∈I,j∈J,where vi,j∈{0,1} and pi,j=1,qij≠0;0,qij=0.Adopting the method introduced above, we have a linear reformulation of the geometric objective function and max-product fuzzy relation inequality constraints. The original problem (8) can then be converted into the following 0-1 linear mixed integer programming model:LMIPminf=∑l∈Lclzl,ns.t.9,10,11,14,29,30xj,zl,j,ujk≥0,λjw,vi,j∈0,1i∈I,j∈J,k∈K,w∈W. Note that, in this model, there are n⌈log2⁡h⌉ binary variables of λjw; mn binary variables of vi,j; n nonnegative variables of xj; np nonnegative variables of zl,j; nh nonnegative variables of ujk; 2n+n⌈log2⁡h⌉+p+m linear equations (i.e., (9) + (10) + (11) + (29)); and 2(n-1)ph+mn linear inequality constraints (i.e., (14) + (30)) involved.Now we illustrate this model by a simple example.Example 9.
Consider the following geometric programming problem in discrete variables with max-product fuzzy relation inequality constraints:(31)minfx=x12x2x3-x1x2x3-1,s.t.A∘x=0.80.90.30.90.60.50.40.10.9∘x1x2x3≥b=0.720.270.36,x1,x2,x3∈0.3,0.5,0.7,0.9.
In this case,h=4,⌈log2⁡h⌉=2, adopting the logarithmic approach (10) and solving the equations of 1+t1,k+2t2,k=k for k=1,2,3,4; we have(32)tw,k2×4=01010011.Using (9) and (10), we have(33)0.3uj1+0.5uj2+0.7uj1+0.9uj4=xj,j=1,2,3,uj1+uj2+uj1+uj4=1,j=1,2,3,uj2+uj4=λj1,uj3+uj4=λj2,j=1,2,3.By (24) and (30), we have (34)Q=0.90.800.30.450.540.900.4,pi,j3×4=110111101.Then by applying (29) and (30), we have(35)v1,1+v1,2=1,v2,1+v2,2+v2,3=1,v3,1+v3,3=1,x1≥0.9v1,1,x1≥0.3v2,1,x1≥0.9v3,1,x2≥0.8v1,2,x2≥0.45v2,2,x3≥0.54v2,3,x3≥0.4v3,3.Finally, adding (11) and (14), problem (31) can be converted into the following model:(36)minf=z1,3+z2,3,s.t.0.3uj1+0.5uj2+0.7uj1+0.9uj4=xj,j=1,2,3,uj1+uj2+uj1+uj4=1,j=1,2,3,uj2+uj4=λj1,uj3+uj4=λj2,j=1,2,3,z1,1=0.09u11+0.25u12+0.49u11+0.81u14,z2,1=0.3u11+0.5u12+0.7u11+0.9u14,0.3z1,1-0.7291-u21≤z1,2≤0.3z1,1+0.7291-u21,0.5z1,1-0.7291-u22≤z1,2≤0.5z1,1+0.7291-u22,0.7z1,1-0.7291-u23≤z1,2≤0.7z1,1+0.7291-u23,0.9z1,1-0.7291-u24≤z1,2≤0.9z1,1+0.7291-u24,0.3z1,2-0.65611-u31≤z1,3≤0.3z1,2+0.65611-u31,0.5z1,2-0.65611-u32≤z1,3≤0.5z1,2+0.65611-u32,0.7z1,2-0.65611-u33≤z1,3≤0.7z1,2+0.65611-u33,0.9z1,2-0.65611-u34≤z1,3≤0.9z1,2+0.65611-u34,0.3z2,1-0.811-u21≤z2,2≤0.3z2,1+0.811-u21,0.5z2,1-0.811-u22≤z2,2≤0.5z2,1+0.811-u22,0.7z2,1-0.811-u23≤z2,2≤0.7z2,1+0.811-u23,0.9z2,1-0.811-u24≤z2,2≤0.9z2,1+0.811-u24,0.3z2,2-2.71-u31≤z2,3≤0.3z2,2+2.71-u31,0.5z2,2-2.71-u32≤z2,3≤0.5z2,2+2.71-u32,0.7z2,2-2.71-u33≤z2,3≤0.7z2,2+2.71-u33,0.9z2,2-2.71-u34≤z2,3≤0.9z2,2+2.71-u34,v1,1+v1,2=1,v2,1+v2,2+v2,3=1,v3,1+v3,3=1,x1≥0.9v1,1,x1≥0.3v2,1,x1≥0.9v3,1,x2≥0.8v1,2,x2≥0.45v2,2,x3≥0.54v2,3,x3≥0.4v3,3,λjw,vi,j∈0,1,ujk≥0,i=1,2,3,w=1,2,j=1,2,3,k=1,2,3,4.
Solving problem (36) leads to a solution (x1∗,x2∗,x3∗)=(0.9,0.9,0.3) with u14∗=u42∗=u31∗=1,λ11∗=λ12∗=λ21∗=λ22∗=1,  z1,1∗=0.81,z1,2∗=0.729,z1,3∗=0.2178,z2,1∗=0.9,z2,2∗=0.81,z2,3∗=2.7,  v1,1∗=v2,2∗=v3,1∗=1 and 0 for other variables. The corresponding optimal objective value is −2.4813.


## 3.1. Treating Geometric Function with Multivalued Discrete Variables

For solving problem (8), the first step is to convert each multivalued variable into 0-1 valued by considering(9)xj=∑k∈Kdjkujk,∑k∈Kujk=1,where K={1,2,…,h} is an index set and ujk∈{0,1} for j∈J and k∈K.It is important to know that thenh binary variables of {ujk},j∈J and k∈K, induced by (9), may cause heavy computational burden when n and h become large. To avoid this burden, Li et al. [24] proposed a logarithmic approach which needs only nlog2h binary variables (⌈·⌉ denotes the ceiling function), nh nonnegative variables, and nlog2h linear equations to represent the n discrete variables with h values by considering(10)λjw=∑k∈Ktw,kujk,j∈J,w∈W,where W={1,2,…,⌈log2h⌉} is an index set; λjw∈{0,1} is a binary variable; ujk≥0 is now a nonnegative variable, for j∈J,k∈K and w∈W; and tw,k are binary variables obtained by solving the equations of 1+∑w∈W2w-1tw,k=k for k∈K.The next step is to reformulate the objective function. Remembering thatujk∈{0,1} and ∑k∈Kujk=1, we denote zl,1=x1rl,1 for l∈L; then we have(11)zl,1=∑k=1hu1kd1krl,1,l∈L.Moreover, we denote(12)zl,j=zl,j-1xjrl,j,l∈L,j∈J∖1. Then the objective function can be expressed as(13)fx=∑l∈Lcl∏j∈Jxjrl,j=∑l∈Lclzl,n.In this way we can express the objective function of problem (8) as a linear function in {zl,n∣l∈L}. Note that the expression (12) is nonlinear, but by adopting the approach in [25], we can express them by using linear inequalities in {ujk∈{0,1}∣k∈K,j∈J∖{1}} in the next result.Lemma 1.
Givenl∈L,k∈K,j∈J∖{1}, the product term zl,j=zl,j-1xjrl,j, with xj∈{dj1,dj2,…,djh}, can be expressed by the following linear inequalities in {ujk} and {zl,j}:(14)djkrl,jzl,j-1-Ml,j1-ujk≤zl,j≤djkrl,jzl,j-1+Ml,j1-ujk,where ujk is defined in (9), and Ml,j is a sufficient large positive value such that(15)Ml,1=⋁k∈Kd1krl,1,Ml,j=Ml,j-1⋁k∈Kdjkrl,jj∈J∖1,l∈L.Proof.
Assume thatxj=djk∗ for a particular k∗. From (9), we have ujk∗=1 and other ujk=0.
(i) Fork=k∗, inequality (14) can be converted into the following equation: (16)zl,j=zl,j-1djk∗rl,j=zl,j-1xjrl,j.
(ii) Fork≠k∗, inequality (14) can transformed as(17)djkrl,jzl,j-1-Ml,j≤zl,j≤djkrl,jzl,j-1+Ml,j.Actually, from (i), we have (18)zl,j=zlj-1xjrl,j=⋯=zl,1x2rl,2⋯xjrl,j=∏s≤jxsrl,s.From (15), we know Ml,j=∏s≤j(⋁k∈Kdjkrl,j) and xj∈{dj1,dj2,…,djh}; therefore, (19)zl,j≤Ml,j.Hence, (20)djkrl,jzl,j-1-Ml,j≤zl,j-1-Ml,j-1djkrl,j≤0≤zl,j,zl,j≤Ml,j≤djkrl,jzl,j-1+Ml,j,djkrl,jzl,j-1-Ml,j≤zl,j≤djkrl,jzl,j-1+Ml,j.
From the above, we can see, whenk=k∗, (14) will be converted into (12); when k≠k∗, (14) will be converted into the redundant constraints (17). Consequently (12) can be expressed by (14).


## 3.2. Treating Max-Product Fuzzy Relation Inequalities

Firstly we recall some basic concepts and important properties of the max-product fuzzy inequalities:(21)⋁j∈Jai,jxj≥bii∈I.Denote A=(ai,j)m×n∈(0,1]n and x=(x1,x2,…,xn)T∈[0,1]n,b=(b1,b2,…,bm)T∈[0,1]m; “∘” represent the max-product composite operation; then a system of max-product fuzzy relation inequalities can be represented in the following matrix form:(22)A∘x≥b.The set of all the solutions of system (22) is called its solution set, denoted by XA,b,≥={x∣A∘x≥b}. If XA,b,≥≠∅, we say the system (22) is consistent; otherwise it is inconsistent [4, 26].Lemma 2 (see [5, 26, 27]).
LetA∘x≥b be a system of consistent max-product fuzzy relation inequalities; if x1∈X(A,b,≥) and x1≤x2∈[0,1]n, then we know x2∈X(A,b,≥).Definition 3 (see [26]).
A solutionx^∈X(A,b,≥) is said to be the maximum or greatest solution if and only if x≤x^ for all x∈X(A,b,≥). A solution xˇ∈X(A,b,≥) is said to be a minimal solution if and only if x≤xˇ implies x=xˇ for any x∈X(A,b,≥).Obviously, if the maximum solution of (22) exists, it is unique and x^=(1,1,…,1).Theorem 4 (see [26, 27]).
LetA∘x≥b be a system of max-product fuzzy relation inequalities; then it is consistent if and only if x^=(1,1,…,1)∈X(A,b,≥). Moreover, if the system is consistent, the solution set X(A,b,≥) can be fully determined by one maximum solution and a finite number of minimal solutions, that is, (23)XA,b,≥=⋃xˇ∈XˇA,b,≥x∈0,1n∣xˇ≤x≤x^,where Xˇ(A,b,≥) is the set of all minimal solutions of (22).The feasible domain restricted by the max-product fuzzy relation inequalities (22) can be fully characterised by the solution set X(A,b,≥). Actually, if we know all the minimal solutions, then the solution set X(A,b,≥) can be expressed. The main problem we face is computing all the minimal solutions of system (22). However this is an NP-hard problem [5, 26]. Hence we introduce a method to find all the potential minimal solutions instead of minimal solutions.Definition 5 (see [26]).
MatrixQ=(qi,j)m×n is called a discrimination matrix of (22) with(24)qij=biaij,aij≥bi,0,aij<bi.Theorem 6 (see [26]).
Let matrixQ be the discrimination matrix of the system (22). The system is consistent if and only if, for any i∈I, there exists at least one ji∈J such that qi,ji≠0.Definition 7 (see [27]).
LetQ be the discrimination matrix of the system (22) and matrix S=(si,j)m×n, where si,j∈{0,qi,j}. We call S a solution matrix if, for any i∈I, there exists a unique ji∈J such that si,ji≠0.LetS be a solution matrix of the system (22); denote xS=(x1S,x2S,…,xnS), where(25)xjS=⋁i∈Isi,j.Theorem 8 (see [27]).
LetS be a solution matrix of the system (22) and xS be defined by (25); then xS∈XA,b,≥. Moreover, for any x∈X(A,b,≥), there exists a solution matrix S with a corresponding xS such that xS≤x.From Theorem8, we know that, for any minimal solution xˇ of (22), the solution matrix S and its corresponding xS can be formed such that xS=xˇ. Then the feasible domain restricted by the max-product fuzzy relation inequalities constraints (22) can be expressed as(26)x∈XA,b,≥=⋃xˇ∈XˇA,b,≥x∣xˇ≤x≤x^=⋃S∈SQx∣xS≤x≤x^,where S(Q) denotes the set of all the solution matrix determined by discrimination matrix Q of system (22), and xS is a solution corresponding to the solution matrix S.Consider the definition of (25); we see that, for any solution matrix S and its corresponding xS, the inequality x≥xS is equivalent to the following constraints:(27)xj≥⋁ı∈Isi,j,j∈J,  i.e.,xj≥si,j,i∈I,j∈J.At the same time, we bring in mn binary variables vi,j∈{0,1}, for i∈I and j∈J; the element of matrix S can be expressed as(28)sij=vi,jqi,j,i∈I,j∈J,∑j∈Jpi,jvi,j=1,i∈I,j∈J,where vi,j∈{0,1} and pi,j=1,qij≠0;0,qij=0.Therefore, the feasible domain restricted by (22) can be characterised by(29)∑j∈Jpijvi,j=1,i∈I,(30)xj≥qi,jvi,j,i∈I,j∈J,where vi,j∈{0,1} and pi,j=1,qij≠0;0,qij=0.Adopting the method introduced above, we have a linear reformulation of the geometric objective function and max-product fuzzy relation inequality constraints. The original problem (8) can then be converted into the following 0-1 linear mixed integer programming model:LMIPminf=∑l∈Lclzl,ns.t.9,10,11,14,29,30xj,zl,j,ujk≥0,λjw,vi,j∈0,1i∈I,j∈J,k∈K,w∈W. Note that, in this model, there are n⌈log2⁡h⌉ binary variables of λjw; mn binary variables of vi,j; n nonnegative variables of xj; np nonnegative variables of zl,j; nh nonnegative variables of ujk; 2n+n⌈log2⁡h⌉+p+m linear equations (i.e., (9) + (10) + (11) + (29)); and 2(n-1)ph+mn linear inequality constraints (i.e., (14) + (30)) involved.Now we illustrate this model by a simple example.Example 9.
Consider the following geometric programming problem in discrete variables with max-product fuzzy relation inequality constraints:(31)minfx=x12x2x3-x1x2x3-1,s.t.A∘x=0.80.90.30.90.60.50.40.10.9∘x1x2x3≥b=0.720.270.36,x1,x2,x3∈0.3,0.5,0.7,0.9.
In this case,h=4,⌈log2⁡h⌉=2, adopting the logarithmic approach (10) and solving the equations of 1+t1,k+2t2,k=k for k=1,2,3,4; we have(32)tw,k2×4=01010011.Using (9) and (10), we have(33)0.3uj1+0.5uj2+0.7uj1+0.9uj4=xj,j=1,2,3,uj1+uj2+uj1+uj4=1,j=1,2,3,uj2+uj4=λj1,uj3+uj4=λj2,j=1,2,3.By (24) and (30), we have (34)Q=0.90.800.30.450.540.900.4,pi,j3×4=110111101.Then by applying (29) and (30), we have(35)v1,1+v1,2=1,v2,1+v2,2+v2,3=1,v3,1+v3,3=1,x1≥0.9v1,1,x1≥0.3v2,1,x1≥0.9v3,1,x2≥0.8v1,2,x2≥0.45v2,2,x3≥0.54v2,3,x3≥0.4v3,3.Finally, adding (11) and (14), problem (31) can be converted into the following model:(36)minf=z1,3+z2,3,s.t.0.3uj1+0.5uj2+0.7uj1+0.9uj4=xj,j=1,2,3,uj1+uj2+uj1+uj4=1,j=1,2,3,uj2+uj4=λj1,uj3+uj4=λj2,j=1,2,3,z1,1=0.09u11+0.25u12+0.49u11+0.81u14,z2,1=0.3u11+0.5u12+0.7u11+0.9u14,0.3z1,1-0.7291-u21≤z1,2≤0.3z1,1+0.7291-u21,0.5z1,1-0.7291-u22≤z1,2≤0.5z1,1+0.7291-u22,0.7z1,1-0.7291-u23≤z1,2≤0.7z1,1+0.7291-u23,0.9z1,1-0.7291-u24≤z1,2≤0.9z1,1+0.7291-u24,0.3z1,2-0.65611-u31≤z1,3≤0.3z1,2+0.65611-u31,0.5z1,2-0.65611-u32≤z1,3≤0.5z1,2+0.65611-u32,0.7z1,2-0.65611-u33≤z1,3≤0.7z1,2+0.65611-u33,0.9z1,2-0.65611-u34≤z1,3≤0.9z1,2+0.65611-u34,0.3z2,1-0.811-u21≤z2,2≤0.3z2,1+0.811-u21,0.5z2,1-0.811-u22≤z2,2≤0.5z2,1+0.811-u22,0.7z2,1-0.811-u23≤z2,2≤0.7z2,1+0.811-u23,0.9z2,1-0.811-u24≤z2,2≤0.9z2,1+0.811-u24,0.3z2,2-2.71-u31≤z2,3≤0.3z2,2+2.71-u31,0.5z2,2-2.71-u32≤z2,3≤0.5z2,2+2.71-u32,0.7z2,2-2.71-u33≤z2,3≤0.7z2,2+2.71-u33,0.9z2,2-2.71-u34≤z2,3≤0.9z2,2+2.71-u34,v1,1+v1,2=1,v2,1+v2,2+v2,3=1,v3,1+v3,3=1,x1≥0.9v1,1,x1≥0.3v2,1,x1≥0.9v3,1,x2≥0.8v1,2,x2≥0.45v2,2,x3≥0.54v2,3,x3≥0.4v3,3,λjw,vi,j∈0,1,ujk≥0,i=1,2,3,w=1,2,j=1,2,3,k=1,2,3,4.
Solving problem (36) leads to a solution (x1∗,x2∗,x3∗)=(0.9,0.9,0.3) with u14∗=u42∗=u31∗=1,λ11∗=λ12∗=λ21∗=λ22∗=1,  z1,1∗=0.81,z1,2∗=0.729,z1,3∗=0.2178,z2,1∗=0.9,z2,2∗=0.81,z2,3∗=2.7,  v1,1∗=v2,2∗=v3,1∗=1 and 0 for other variables. The corresponding optimal objective value is −2.4813.


## 4. Computational Experiments

To illustrate the effectiveness of the proposed method, we conduct some computational experiments. All the experiments have been run on a PC equipped with the Intel Core I7-6700HQ CPU, 8 GB RAM, and Windows 10 (64 bit) operating system. GUROBI (2016) is the chosen MIP solver for solving all the instances. To ensure the existence of an optimal solution in each case, we apply the following rules to randomly generate its coefficients:( 1 )   a i , j are generated randomly by the uniform distribution over (0,1], and cj are taken randomly from [-5,5] for i∈I and j∈.( 2 )  djk are generated randomly by the uniform distribution over (0,1] such that dj1<dj2<⋯<djh for j∈J and k∈K.( 3 ) When rl,j≤0, the elements djkrl,j and Mln may go to infinite; in order to avoid this, we generate rl,j randomly in the interval [-3,3] such that ∑j∈Jrl,j∈[-3,3] for l∈L and j∈J.( 4 ) To make sure the test instance is feasible, each bi is generated randomly by the uniform distribution over the interval of [(⋁j∈Jai,jdjh)×0.1,(⋁j∈Jai,jdjh)×0.7] for i∈I. Our computational experiments consist of 7 cases with {m=10,n=8,p=6},{m=12,n=10,p=6} and h∈{10,20,30,40}. Each case includes 20 test instances which are executed with the coefficients generated by the rules mentioned above.The computational results are shown in Table1. In the Table, V-Bin denotes the number of 0-1 variables, V-Con denotes the number of continuous variables, L-Eq denotes the number of linear equation constraints, L-Ine denotes the number of linear inequality constraints, Tave(s) denotes the average CPU time in seconds of solving 20 randomly generated instances of each case, and Tmax(s) means the longest CPU time in seconds we meet in each case.Table 1 m n p h V-Bin V-Cont L-Eq L-Ine T a v e   s T m a x   ( s ) 10 8 6 10 112 136 64 920 4.56 24.92 10 8 6 20 120 216 72 1760 25.67 210.85 10 8 6 30 120 296 72 2600 61.31 588.89 10 8 6 40 128 376 80 3440 238.77 2172.66 12 10 6 10 160 170 78 1200 30.30 141.03 12 10 6 20 170 270 88 2280 66.82 592.63 12 10 6 30 170 370 88 3360 202.51 1587.88From Table1, we can see that there are hundreds of binary variables and thousands of linear inequality constraints in each case. All the problem can be solved in 4 minutes in average. Even in the worst condition, we can also find the optimal solution in 1 hour. Therefore, our computational experiments support the efficiency of the proposed algorithm.Because of the nonconvexity of the geometric function and fuzzy relation equations (inequalities), the optimization problem of geometric programming with fuzzy relational constraints is difficult to solve. To make problem easier to solve, researchers chose special geometric functions as objective functions, such as monomials in [20, 21, 23] and posynomial function with special indexes in [17]. In our problem, the objective function is a general geometric function. At the same time, we add the restriction of discrete values for each variable. We transformed the problem into a linear mix-integer programming model and adopt the branch-bound method to develop an effective solution method.


## 5. Conclusion

In this paper, a geometric optimization problem subject to max-product fuzzy relation constraints with discrete variables is studied. For solving the problem, we replacen discrete variables in h values with binary variables by the logarithmic method. Then we transform the objective function into a linear function of p continuous variables subject to p equations and 2(n-1)ph inequalities. By checking all the potential minimal solutions, we further transform the max-product fuzzy relation inequality constraints into linear equality and inequality constraints with mn 0-1 binary variables. Finally, we built a 0-1 mixed integer linear programming model for solving the original problem. Numerical experiments support the efficiency of the proposed method. To the best of our knowledge, this is the first fuzzy optimization model including discrete variables.



---

*Source: 1610349-2018-04-12.xml*