# A New Methodology for Solving Multiobjective Chance-Constrained Problems: An Application on IoT Systems

Authors: Kumru Didem Atalay; Tacettin Sercan Pekin; Ayşen Apaydin
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

This study presents a newly developed methodology to transform the chance-constrained problem into a deterministic problem and then solving this multiobjective deterministic problem with the proposed method. Chance-constrained problem contains independent gamma random variables that are denoted asaij. Two methods are proposed to obtain the deterministic equivalent of chance-constrained problem. The first of the methods is directly based on using the distribution, and the second consists of normalizing probabilistic constraints using Lyapunov’s central limit theorem. An algorithm which uses the Global Criterion Method is developed to solve the multiobjective deterministic equivalent of chance-constrained problem. The methodology is applied to a real-life engineering problem that consists of an IoT device and its data sending process. Using Lyapunov’s central limit theorem for large numbers of random variables is found to be more appropriate.


---

## Body

## 1. Introduction

Most decision problems, whether real world or hypothetical, can be defined with a mathematical programming model. Unfortunately, in many practical systems, it is very difficult to gather all necessary information to derive such models. This difficulty arises from the uncertainty of many of the factors in modeling equations. One possible reason for this uncertainty is the randomness of these factors, and stochastic programming is a branch of mathematical programming that theoretically and empirically focuses on “conditional extremum problems under incomplete information about random coefficients” [1].In terms of the investigation and optimization of complicated systems, the deterministic approach broadly dominates projection, planning, and management processes in economic and military sciences. However, by assuming that all initial data exhibit the same basic characteristics, the deterministic approach ignores the probabilistic properties of complicated systems. On the one hand, these deterministic systems emphasize objective laws. On the other hand, the deterministic approach is constantly undermined by random factors in real-life data. As such, a stochastic approach should be more useful for most real-life problems [2].Assume that a decision-maker wants to find the so-called “absolutely best” decision that corresponds to the minimum (or maximum) of a suitable objective function, while satisfying a given set of feasibility constraints. If the decision models are very complex, standard optimization strategies cannot be used to solve them directly. Therefore, a global optimization technique should be used. Global optimization applications are popular in all disciplines, including science, engineering, economy, and applied science. Global optimization is aimed at finding the best global solution of a model, in the presence of multiple local optima [3].The classical linear programming problem, which is a specific class of mathematical programming problems, is formulated as follows:(1)maxzx=∑j=1ncjxj,∑j=1naijxj≤bi,i=1,...,m,xj≥0,j=1,...,n.Note that all coefficients (i.e., technologic coefficientsaij, right-hand side values bi, and objective function coefficients cj for j=1,..,nandi=1,...,m) are deterministic. However, when at least one coefficient is a random variable, the problem becomes a stochastic programming problem.Stochastic programming problems can be classified into the following three categories: probability distribution problems, chance-constrained problems, and recourse problems.This paper attempts to analyze a class of chance-constrained stochastic programming problems. Chance-constrained programming assumes the presence of random data variations and permits constraint violations up to specified probability limits. To transform equation (1) into a chance-constrained problem, the original constraints ∑j=1naijxj≤bi, i=1,...,m, are replaced with the chance-constrained programming formulation P∑j=1naijxj≤bi≥1−δi, i=1,...,m. The term “chance-constrained” is used because of the constraints of P., which designate the probability of the event in parentheses. The parameters δi0<δi≤1 are assumed to be deterministically fixed. Chance-constrained programming is one of the major approaches for addressing random coefficients in mathematical programming problems [1, 4–9].Chance-constrained programming was first developed by Charnes and Cooper [5]. A variant of the Charnes and Cooper model, which utilized joint chance constraints, is given by Miller and Wagner [10]. Prekopa [11] introduced a more general case in which the right-hand side is allowed to have stochastically dependent components. Contini [12] developed an algorithm for stochastic goal programming which assumes that the random variable coefficients are normally distributed with known means and variances. In doing so, he transformed the stochastic problem into an equivalent deterministic quadratic programming problem. Rather than assuming that the coefficients are normally distributed, Sengupta [8] assumed a chi-squared distribution, which has a nonnegative range and is more applicable to economic models of production and investment. Jagannathan [7] obtained equivalent equations for chance-constrained programming models based on coefficient matrices with normally distributed elements and dependent random right-hand side elements. Regarding multiobjective stochastic linear programming problems, Stancu-Minasian [13] suggested a minimum risk approach, while both Leclercq [14] and Teghem et al. [15] have proposed interactive methods. Extensive discussion on the convex properties of stochastic problems can be found in [16]. Meanwhile, a fuzzy approach to stochastic programming has been presented by Mohan and Nguyen [17]. An interactive fuzzy satisfying method was also developed by Sakawa et al. [18]. Yang and Wen [19] presented a chance-constrained programming model for transmission system planning in the competitive electricity market environment. Huang [20] provided two types of credibility-based chance-constrained models for portfolio selection with fuzzy returns. Ağpak and Gökçen [21] developed new mathematical models for stochastic traditional and U-type assembly lines with a chance-constrained 0-1 integer programming technique. Henrion and Strugarek [22] investigated the convexity of chance constraints with independent random variables. Parpas et al. [23] proposed a stochastic algorithm for the global optimization of chance-constrained problems. They assumed that the probability measure used to evaluate the constraints is known only through its moments. Xu et al. [24] developed a robust hybrid stochastic chance-constraint programming model to support municipal solid waste management under uncertainty. Ben Abdelaziz and Masri [25] proposed a chance-constrained approach and a compromise programming approach to transform the multiobjective stochastic linear program with partial linear information on the probability distribution into its equivalent uniobjective problem. Goyal and Ravi [26] presented a polynomial time approximation scheme for the chance-constrained knapsack problem when item sizes are normally distributed and independent of other items. Zhang and Peng [27] proposed uncertain optimal assignment problem in which the uncertain factor is described by uncertainty theory. In order to construct an uncertain programming model, the concept of α-optimal assignment is proposed. After that, α-optimal model is given. Chen et al. [28] investigated an uncertain bicriteria solid transportation problem. Based on these equivalence relations, the optimal transportation plans were obtained by expected value goal programming and chance-constrained goal programming. Zhang et al. [29] investigated the fixed-charge solid transportation problem under uncertainty. Three models under different criteria were presented, which include expected value model, chance-constrained programming model, and measure-chance programming model. Majumder et al. [30] proposed an uncertain multiobjective Chinese postman problem under the framework of uncertainty theory, for an undirected connected network. The model is then solved using two classical multiobjective techniques, the Global Criterion Method and fuzzy programming method, and two multiobjective genetic algorithms. Majumder et al. [31] proposed a biobjective rough‐fuzzy quadratic minimum spanning tree problem which is modeled using rough‐fuzzy chance‐constrained programming technique. The linear and quadratic weights of the proposed model are considered as two different objectives which are optimized simultaneously. Atalay and Apaydın [4] proposed a new method using Esseen inequality to obtain deterministic equivalent of chance-constraint problems with gamma random variables. The method in this paper uses estimation of the distance between distribution of sum of these independent random variables having gamma distribution and normal distribution; probabilistic constraint obtained via Esseen inequality has been made deterministic using the approach suggested by Polya. The main purpose of the article is to transform the chance-constrained model into a deterministic model based on the Esseen inequality. As a result, the upper bounds of the chance constraints are derived by the Esseen inequality and approximate deterministic equivalent of the model is developed. Sarkar et al. [32] have reduced the chance constraints with independent gamma parameters to deterministic constraints. They have used geometric inequality and some other inequalities for obtained deterministic equivalent of chance constraints where the objective function may be considered as linear or nonlinear with deterministic cost coefficient. In contrast to the two papers discussed above, in our paper, distribution function is directly used and multiobjective mathematical model solution is obtained with the use of Global Criterion Method. Distribution function is on the left-hand side of the chance constraint. Besides, Pareto optimal solutions are also provided. Furthermore, deterministic equivalent of chance constraint which is derived by direct distribution function is compared to the approximate model which is derived using Lyapunov’s central limit theorem.To the best of our knowledge, there is not any study that proposes an algorithm for solving multiobjective chance-constraint problems with gamma random variables by directly using the distribution and then using Lyapunov’s central limit theorem and Global Criterion Method. Instead of using quantile rules, we directly used the distribution function. In this case, sinceakj are gamma random variables, ∑j=1nakjxj also becomes gamma random variables. Instead of using quantile function, distribution function of sum of independent random variables is directly used. According to this, distribution function F. is obtained and it is assigned as the left-hand side value of the chance constraint. In the mathematical model, the parameters of the chance constraint which are random variables have a distribution function and this distribution function provides the direct calculation of probability. Therefore, probabilistic chance-constraint corresponding to the direct distribution function is itself deterministic equivalent.In this paper, we consider a multiobjective chance-constrained stochastic programming problem, where the technologic coefficientsaij are independent gamma random variables with known means and variances. The decision why we use the gamma distribution is motivated by the fact that it has relationships with gamma and normal distributions. If univariate distribution relationship is examined, Gamma random variables consisting αβ and α2β parameters converge to normal distribution with parameters μ=αβ and σ2=α2β and β⟶∞ and X∼Nμ,σ2 [33]. Bivariate gamma distributions, such as by marginal transformation, are mainly derived from the bivariate normal in some fashion. A univariate chi-squared distribution can be derived from one or more independent and identically distributed normal variables. Moreover, a chi-squared random variable is a special case of gamma. As a result of this, a bivariate gamma model is related to the bivariate normal one [34].In addition, other distributions such as the exponential and chi-square distributions can be closely approximated by a gamma distribution. For our chance-constrained model, we developed a deterministic equivalent model without random variables. A transformation was implemented to convert the chance-constrained programming problem into a deterministic equivalent problem. This deterministic equivalent problem is obtained by two methods, that is, by deriving the direct distribution and then normalizing probabilistic constraints using Lyapunov’s central limit theorem [35]. After converting the problem into a deterministic model, we used global optimization to propose an algorithm that utilizes the Global Criterion Method to solve the multiobjective problems. The solution was applied to a real-life engineering problem. IoT devices and distributed computing are recently a hot topic, and there are fairly new problems arising rapidly following the emerging new hardware and software running on these IoT devices. These devices have limitations on energy usage, data transfer rate, and continuous usage time. These limitations and the need for maximum data transfer amount make the application a suitable problem for the model. We have applied the model for such an IoT application in this study. Using numerical examples, we compared the objective functions of models obtained from these exact and approximate methods.


## 2. Chance-Constrained Programming

An ordinary linear programming model is said to be chance-constrained if its linear constraints are associated with a set of probability measures that indicate the degree to which constraints can be violated [36]. As a stochastic programming method, chance-constrained programming includes fixing certain appropriate levels for random constraints. Thus, it is generally used for modeling technical or economic systems, particularly economic planning, input control, structural design, inventory, and air and water quality management problems. Under chance-constrained programming, each constraint can be realized with a certain probability.When some or all of the coefficients of the model are independent random variables, the chance-constrained programming formulation requires only that each constraint must hold for most of these combinations [6, 8, 37].A multiobjective chance-constrained programming problem can be stated as follows:(2)maxz1x=∑j=1nc1jxj=f1x,maxz2x=∑j=1nc2jxj=f2x,⋮maxzKx=∑j=1ncKjxj=fKx,P∑j=1naijxj≤bi≥1−δi,fori=1,2,...,m,xj≥0,j=1,2,...,n,δi∈0,1,i=1,2,...,m.Note thatδi are specified probabilities and that clj, l=1,2,...,K, aij, and bi are independent random variables. A general CCP problem is defined with model (2). In the model, one of the parameters, two of the parameters, or three of the parameters can be random variables. However, the main focus of this work is on the case where aij parameters are gamma random variables. Here, it is assumed that the decision variables xi are deterministic.


## 3. The Deterministic Equivalent of Chance-Constraint Models

In this section, we derive a deterministic equivalent of model (2), where aij,j=1,...,n, are independent random variables with known means and variances and cljand bi are constants. The kth chance constraint is given in model (2).(3)P∑j=1nakjxj≤bk≥1−δk.Note that eachakj has a finite third central moment. If the deterministic equivalent of constraint (3) can be derived, the problem can be converted by determining the distribution of ∑j=1nakjxj, which is the linear combination of akj. To derive the deterministic equivalent of the chance constraint (3), we propose two methods, namely, deriving the direct distribution and using Lyapunov’s central limit theorem. Both methods are first defined, and then they are adapted to the gamma distribution.The most suitable method for deriving the deterministic equivalent of a chance-constrained programming model is to find the direct distribution. However, as the number of decision variables increases to a large value ofn (more precisely, n≥5), it becomes very difficult to obtain the probability P∑j=1nakjxj≤bk. Therefore, in this case Lyapunov’s central limit theorem can be used to obtain an approximate solution.


### 3.1. Method I: Transformation of a Chance-Constrained Programming Model into a Deterministic Model Using the Distribution Directly—Multivariate Transformation

LetX1,X2,…,Xn be a random vector with a probability density function fXx1,x2,...,xn. Let A=x:fXx>0. Consider a new random vector, U1,U2,…,Un, which is defined as follows:(4)U1=g1X1,X2,...,Xn,U2=g2X1,X2,...,Xn,⋮Un=gnX1,X2,...,Xn.Suppose thatA0,A1,…,An is from a partition of A. The set A0, which may be an empty set, satisfies PX1,X2,…,Xn∈A0=0. The transformation U1,U2,…,Un=g1X1,..,Xn,…,gnX1,..,Xn is a one-to-one transformation from Aj onto ℬ=u1,u2,…,un:u1=g1x1,x2,…,xn,…,un=gnx1,x2,…,xn for each j=1,2,…,k. Then, for each j, the inverse function from ℬ to Aj can be obtained. Denote the jth inverse as follows:(5)x1=h1ju1,...,un,x2=h2ju1,...,un,⋮xn=hnju1,...,un.Foru1,u2,…,un∈ℬ, the jth inverse yields a unique x1,x2,…,xn∈Aj such that u1,u2,…,un=g1x1,x2,…,xn,…,un=gnx1,x2,…,xn. Let Jj denote the Jacobian computed from the jth inverse. Assuming that these Jacobians do not vanish identically on ℬ, we obtain the following representation of the joint probability density function fUu1,...,un for u∈ℬ [38]:(6)fUu1,...,un=∑j=1kfXh1ju1,...,un,...,hnju1,...,unJj.To obtain the deterministic equivalent of chance constraint (3), transformation methods can be used. Let ak1,ak2,...,akn be independent random variables. Consider the random variables U1,U2,…,Un, which are defined as follows:(7)U1=ak1x1,U2=ak1x1+ak2x2=U1+ak2x2,⋮Un=ak1x1+ak2x2+...+aknxn=Un−1+aknxn.By deriving the probability density functions of the random variablesU1,U2,...,Un, the deterministic equivalents of chance constraints can be obtained. Hence, chance constraint (3) can be converted to a deterministic equivalent as follows:(8)FUnbk≥1−δk.


### 3.2. Method II: Transformation of a Chance-Constrained Programming Model into a Deterministic Model Using Lyapunov’s Central Limit Theorem

LetX1,X2,...,Xn be independent random variables. Suppose that each Xj has a finite expected value and finite variance. Suppose also that the third central moments satisfy EXj−EXj3<∞j=1,2,...,n and the following Lyapunov condition [35]:(9)limn⟶∞∑j=1nEXj−EXj3Var∑j=1nXj=0.Then, the normalized sum of the random variablesXj converges to a standard normal random variable as n⟶∞.(10)P∑j=1nXj≤x=P∑j=1nXj−E∑j=1nXjVar∑j=1nXj≤x−E∑j=1nXjVar∑j=1nXj≅PZ≤x−E∑j=1nXjVar∑j=1nXj=Φx−E∑j=1nXjVar∑j=1nXj.The deterministic equivalent of chance constraint (3) can be obtained using normalization as follows:(11)Φbk−E∑j=1nakjxjVar∑j=1nakjxj≥1−δk,bk≥Var∑j=1nakjxjΦ−11−δk+E∑j=1nakjxj.In the following section, we provide a deterministic equivalent of constraint (3) for the two methods mentioned above when coefficients aij are independent gamma variables with different parameters.


## 3.1. Method I: Transformation of a Chance-Constrained Programming Model into a Deterministic Model Using the Distribution Directly—Multivariate Transformation

LetX1,X2,…,Xn be a random vector with a probability density function fXx1,x2,...,xn. Let A=x:fXx>0. Consider a new random vector, U1,U2,…,Un, which is defined as follows:(4)U1=g1X1,X2,...,Xn,U2=g2X1,X2,...,Xn,⋮Un=gnX1,X2,...,Xn.Suppose thatA0,A1,…,An is from a partition of A. The set A0, which may be an empty set, satisfies PX1,X2,…,Xn∈A0=0. The transformation U1,U2,…,Un=g1X1,..,Xn,…,gnX1,..,Xn is a one-to-one transformation from Aj onto ℬ=u1,u2,…,un:u1=g1x1,x2,…,xn,…,un=gnx1,x2,…,xn for each j=1,2,…,k. Then, for each j, the inverse function from ℬ to Aj can be obtained. Denote the jth inverse as follows:(5)x1=h1ju1,...,un,x2=h2ju1,...,un,⋮xn=hnju1,...,un.Foru1,u2,…,un∈ℬ, the jth inverse yields a unique x1,x2,…,xn∈Aj such that u1,u2,…,un=g1x1,x2,…,xn,…,un=gnx1,x2,…,xn. Let Jj denote the Jacobian computed from the jth inverse. Assuming that these Jacobians do not vanish identically on ℬ, we obtain the following representation of the joint probability density function fUu1,...,un for u∈ℬ [38]:(6)fUu1,...,un=∑j=1kfXh1ju1,...,un,...,hnju1,...,unJj.To obtain the deterministic equivalent of chance constraint (3), transformation methods can be used. Let ak1,ak2,...,akn be independent random variables. Consider the random variables U1,U2,…,Un, which are defined as follows:(7)U1=ak1x1,U2=ak1x1+ak2x2=U1+ak2x2,⋮Un=ak1x1+ak2x2+...+aknxn=Un−1+aknxn.By deriving the probability density functions of the random variablesU1,U2,...,Un, the deterministic equivalents of chance constraints can be obtained. Hence, chance constraint (3) can be converted to a deterministic equivalent as follows:(8)FUnbk≥1−δk.


## 3.2. Method II: Transformation of a Chance-Constrained Programming Model into a Deterministic Model Using Lyapunov’s Central Limit Theorem

LetX1,X2,...,Xn be independent random variables. Suppose that each Xj has a finite expected value and finite variance. Suppose also that the third central moments satisfy EXj−EXj3<∞j=1,2,...,n and the following Lyapunov condition [35]:(9)limn⟶∞∑j=1nEXj−EXj3Var∑j=1nXj=0.Then, the normalized sum of the random variablesXj converges to a standard normal random variable as n⟶∞.(10)P∑j=1nXj≤x=P∑j=1nXj−E∑j=1nXjVar∑j=1nXj≤x−E∑j=1nXjVar∑j=1nXj≅PZ≤x−E∑j=1nXjVar∑j=1nXj=Φx−E∑j=1nXjVar∑j=1nXj.The deterministic equivalent of chance constraint (3) can be obtained using normalization as follows:(11)Φbk−E∑j=1nakjxjVar∑j=1nakjxj≥1−δk,bk≥Var∑j=1nakjxjΦ−11−δk+E∑j=1nakjxj.In the following section, we provide a deterministic equivalent of constraint (3) for the two methods mentioned above when coefficients aij are independent gamma variables with different parameters.


## 4. The Deterministic Model for the Gamma Distribution

Definition 1.
Letak1,ak2,...,akn be independent random variables with parameters αkj,βkj. The probability density function for each random variable akj can be stated as follows:(12)fakj=1Γαkjβkjαkjakjαkj−1exp−akjβkj,akj>0,βkj>0,αkj>0,0,ow.
Method I: we start by considering a mathematical model with only two random variables. Forj=1,2, chance constraint (3) can be expressed as follows:(13)Pak1x1+ak2x2≤bk≥1−δk.
Note thatak1 and ak2 are independent gamma random variables with Γαk1,βk1 and Γαk2,βk2, respectively. To calculate the deterministic equivalent of chance constraint (13), we must first find the density of the random variable ak1x1+ak2x2. Therefore, we define random variables U1 and U2 as follows:(14)U1=ak1x1=Y1,U2=ak1x1+ak2x2=Y1+Y2=U1+Y2.
Note that the random variablesYj have a gamma distribution, with Γαkj,βkjxj = Γαkj,βkj∗. Let V2 be an auxiliary variable used to find the probability density function of U2.(15)U2=ak1x1+ak2x2=Y1+Y2=U1+Y2,V2=Y2=ak2x2.
Note that ify1=u2−v2 and y2=v2, then J=1. The joint probability density function of U2 and V2 is as follows:(16)fU2,V2u2,v2=fY1u2−v2fY2v2J=u2−v2αk1−1v2αk2−1Γαk1Γαk2βk1∗αk1βk2∗αk2exp−u2βk1∗exp−v21βk2∗−1βk1∗.
The marginal probability density function ofU2 can be computed as follows:(17)fU2u2=exp−u2/βk1∗Γαk1Γαk2βk1∗αk1βk2∗αk2⋅∫0u2u2−v2αk1−1v2αk2−1exp−v21βk2∗−1βk1∗dv2.
After integrating the above integral, we obtain the following expression:(18)fU2u2=u2αk1+αk2−1exp−u2/βk1∗βk1∗αk1βk2∗αk2Γαk1+αk2⋅hypergeomαk2,αk1+ααk2,−1βk2∗−1βk1∗u2.
Note that the termhypergeom is the generalized hypergeometric function defined by(19)hypergeoma,b;x=Fa,b;x=∑k=0∞akxkbkk!,b≠0,−1,−2,...,with(20)ak=aa+1...a+k−1=Γa+kΓa.
By substituting equation (19) into (18), the probability density function of U2 can be rewritten as follows:(21)fU2u2=u2αk1+αk2−1exp−u2/βk1∗βk1∗αk1βk2∗αk2Γαk1+αk2∑j=1∞αk2j−u21/βk2∗−1/βk1∗jαk1+αk2jj!.
The distribution function ofU2, which is the left side of the chance constraint given in (13) can be rewritten as follows:(22)PU2≤bk=FU2bk=1βk1∗αk1βk2∗αk2Γαk1+αk2∫0bku2αk1+αk2−1exp−u2βk1∗⋅∑j=1∞αk2j−u21/βk2∗−1/βk1∗jαk1+αk2jj!du2.
Thus, the deterministic equivalent of chance constraint (13) is as follows:(23)1βk1∗αk1βk2∗αk2Γαk1+αk2∫0bku2αk1+αk2−1exp−u2βk1∗∑j=1∞αk2j−u21/βk2∗−1/βk1∗jαk1+αk2jj!du2≥1−δk.
We now consider a chance-constraint with three random variables. Thekth chance constraint involving these random variables can be presented as follows:(24)Pak1x1+ak2x2+ak3x3≤bk≥1−δk.
Note thatak1, ak2, and ak3 are gamma random variables with Γαk1,βk1, Γαk2,βk2, and Γαk3,βk3, respectively. We define the random variable U3 and auxiliary variable V3 as follows:(25)U3=ak1x1+ak2x2+ak3x3=Y1+Y2+Y3=U2+Y3,V3=Y3=ak3x3.
Note that ifu2=u3−v3 and y3=v3, then J=1. The joint probability density function of U3 and V3 is as follows:(26)fU3,V3u3,v3=fU2u3−v3FY3v3J=u3−v3αk1+αk2−1exp−u3−v3/βk1∗exp−v3/βk3∗v3αk3−1βk1∗αk1βk2∗αk2βk3∗αk3Γαk1+αk2Γαk3⋅∑j=1∞αk2j−u3−v31/βk2∗−1/βk1∗jαk1+αk2jj!.
The marginal probability density function ofU3 can be computed as follows:(27)fU3u3=∫0u3fU3,V3u3,v3dv3.
The distribution function ofU3, which is on the left side of the chance constraints given in (24), can be written as follows:(28)PU3≤bk=FU3bk=∫0bkfU3u3du3.
Now, we consider a chance constraint involvingn random variables. To derive the marginal probability density function of Un, we define the random variable Un and auxiliary variable Vn as follows:(29)Un=ak1x1+ak2x2+⋯+aknxn=Y1+Y2+⋯+Yn=Un−1+Yn,Vn=Yn=aknxn.
Note that ifun−1=un−vn and yn=vn, then J=1. The joint probability density function of Un and Vn can be stated as follows:(30)fUn,Vnun,vn=fUn−1un−vnfYnvnJ.
The marginal probability density function ofUn can be computed as follows:(31)fUnun=∫0unfUn,Vnun,vndvn.
Hence, the deterministic equivalent of the left side of chance constraint (3) is(32)PUn≤bk=FUnbk=∫0bkfUnundun.
Thus, we have reached a generalized result forn random variables. The deterministic equivalent of chance constraint (3) can be easily calculated with equation (32) for known parameters of gamma distributions.
Method II: in this method, we apply Lyapunov’s central limit theorem to the gamma distributions with large values ofn. As such, we are able to transform chance constraint (3) to deterministic equivalent (11).(33)bk−∑j=1nαkjβkj2xj2Φ−11−δk−E∑j=1nαkjβkjxj≥0.


## 5. A New Algorithm for Multiobjective Chance-Constrained Problem Procedure

We now present a methodology for solving a multiobjective chance-constrained stochastic programming model. To derive a deterministic model, we use the proposed Methods I and II, as presented in Section4.Step 1: convert the given chance-constraint programming problem into an equivalent deterministic programming problem as discussed in Section4.Step 2: solve the deterministic problem obtained in Step 1, using only one objective at a time in model (2) and ignoring the others.Step 3: calculateflx∗,l=1,...,K, which is the feasible solution of each lth objective function with respect to flx. Find the corresponding values of the objective functions at each solution for comparison.Step 4: using the solutions obtained from Step 3 and the deterministic constraint obtained from Step 1, solve the following global criterion problem:(34)minz=∑l=1Kflx∗−flxflx∗p,x∈X.Setp=1 or p=2. While the value of p is increasing, total distance between flx∗ and flx is decreasing.


## 6. Application of the Newly Proposed Method to an IoT End-System

The Internet of Things [39] is an Internet-based information infrastructure which enables several smart “things” to communicate with each other and servers. These “things” are in general small devices with computing and communicating skills where most of the time measures some value. They need a power supply to operate, and since there are distributed, they often rely on battery power. This energy limitation requires some kind of intelligent power consumption and thus a good way of battery usage optimization.The battery usage optimization process has a number of constraints, and the result should maximize the total amount of data sending time. The data sending time is directly related to the accuracy of updating the current state of the nodes on the server. According to this, at each sending process, the node sends either the current measurement or its current location to the server. The measurement data contain a measured height in centimeters, and location data contain world coordinates of the node. Once the data are sent to the server, the value on the server is updated and the number of data sending processes provides a better result on the server side for further calculations. Thus, maximizing the data sending time directly improves the quality of server-side jobs. There are certain constraints while maximizing the data sending time. Height change can occur with a random frequency through a day. Similarly, device location can change with a random frequency. With these in mind, constraints are as follows.The first constraint is as follows: height change occurs with a random frequency every day and the assumption is that the height change is a gamma random variable with the parameters provided in Table1. Every time a static duration of time is required for sending process. Similarly, location change occurs with a random frequency every day, and every time a static duration of time is required for sending process. The total of this time cannot exceed 3 seconds a day because the battery has a 3-second limit daily.Table 1
Characteristics ofaij.
i,jEaijVaraijaij∼Γαij,βijEaijxjVaraijxjaijxj∼Γαij,βijxj1,111a11∼Γ1,1x1x12a11x1∼Γ1,x11,211a12∼Γ1,1x2x22a12x2∼Γ1,x22,111a21∼Γ1,1x1x12a21x1∼Γ1,x12,239a22∼Γ1,33x29x22a22x2∼Γ1,3x23,122a31∼Γ2,12x12x12a31x1∼Γ2,x13,224a32∼Γ1,22x24x22a32x2∼Γ1,2x2The second constraint is as follows: height change occurs with a random frequency every day and the assumption is that the height change is a gamma random variable with the parameters provided in Table1. Every time a static duration of time is required for sending process. Similarly, location change occurs with a random frequency every day, and every time a static duration of time is required for sending process. The total of this time cannot exceed 2 seconds without changing the measurement equipment because of its limitations.The third constraint is as follows: height change occurs with a random frequency every day and the assumption is that the height change is a gamma random variable with the parameters provided in Table1. Every time a static duration of time is required for sending process. Similarly, location change occurs with a random frequency every day, and every time a static duration of time is required for sending process. The total of this time cannot exceed 1 second on consecutive sending operations because the device cannot handle that much memory.This application requires 3 objective functions. The first objective function includes sending the data only as integer values where the total transmitted data at each time are the least and the objective is maximizing these transmitted data overall. The second objective function includes sending the data as float values where the total transmitted data are more than just sending integer values at each time and the objective is maximizing these transmitted data overall. The third objective function includes sending the data with data overheads which include the data types such as measurement or location. The final one has the most transmitted data at each time, and the objective is maximizing these transmitted data overall.The mathematical model of the above engineering problem with multiobjective, chance-constrained programming problem by using the methodology presented in Section5 is given as follows:(35)maxz1x=∑j=12c1jxj=f1x,maxz2x=∑j=12c2jxj=f2x,maxz3x=∑j=12c3jxj=f3x,P∑j=12a1jxj≤b1≥1−δ1,P∑j=12a2jxj≤b2≥1−δ2,P∑j=12a3jxj≤b3≥1−δ3,xj≥0,j=1,2.Note that the objective function coefficients, the right-hand side values, and the specified probabilities are determined asc11,c12,c21,c22,c31,c32=1,1,5,6,6,8, b1,b2,b3=3,2,1, and δ1,δ2,δ3=0.4,0.4,0.25, respectively. In this problem, akj is a gamma random variable with the characteristics shown in Table 1.From Method I, we obtain the following deterministic problem:(36)maxz1=x1+x2=f1,maxz2=5x1+6x2=f2,maxz3=6x1+8x2=f3,−x2exp3x1+x1exp3x2exp−3x1+x2x1x2+x2−x1≥0.6x2−x1,−3x2exp2x1+x1exp23x2exp−2x1+3x23x1x2+3x2−x1≥0.63x2−x1,−4exp−x1−2x22x1x2x22exp−1x1+4exp−1x1x1x2+2exp−1x1x2−exp−1x1x12+4x22−4x1x2+x12≥0.75−2x2+x12,xj>0,j=1,2.Note that nonnegative constraintxj≥0 is replaced with xj>0 to avoid dividing by zero in equation (36). From Method II, we obtain the following deterministic problem:(37)maxz1=x1+x2=f1,maxz2=5x1+6x2=f2,maxz3=6x1+8x2=f3,3−x1−x2−0.253347103x12+x220.5≥0,2−x1−3x2−0.253347103x12+9x220.5≥0,1−2x1−2x2−0.674492x12+4x220.5≥0,xj≥0,j=1,2.Then, we solve the deterministic models (36) and (37) for each objective function and derive the solution shown in Table 2.Table 2
Model solutions.
Method I (from model (36))Method II (from model (37))Forf1f1∗0.408228550.3598632x10.20414270.2399088x20.20414270.1199544f22.2455701.919270f32.8579982.399088Forf2f2∗2.2455701.946318x10.20414270.1817437x20.20414270.1729333f10.408228550.3546770f32.8579982.473929Forf3f3∗2.8884212.487224x10.025437990.1397264x20.34197420.2061083f10.36741220.3458346f22.1790351.935281Then, we apply the Global Criterion Method as the solution technique to consider the objectives together. Deterministic constraints that are obtained by these two methods were examined one by one for bothp=1 and p=2 in the multiobjective model. The solutions obtained by substituting the values given in Table 2 in model (34) in Step 4 are shown in Table 3.Table 3
Solutions from the Global Criterion Method.
Method I (from model (36))Method II (from model (37))p=1p=2p=1p=2minz0.019638060.000182790.018865910.00017017f10.37957880.38021550.35608630.3565821f22.1917252.1908621.9457431.945196f32.8651352.8608622.4671402.464064x10.085747580.090431200.19077530.1942964x20.29383120.28978430.16531100.1622857Goal programming (GP), proposed by Charnes and Cooper, is a classical method to solve multiobjective problems, which is widely used in the literature. This method uses an approach which converts a multiobjective problem into a single-objective problem. Thus, it is possible to achieve a single solution for the multiobjective problem [40]. The main idea of GP is to reach predefined goals for every single objective. Deviations of goals are tried to be minimized in GP because it is impossible to obtain a solution for every objective since the goals conflict with each other. Models (36) and (37) with dl− and dl+, l=1,2,3, are the positive deviations and negative deviations that are modeled and solved as goal programming which is proposed as an alternative to the Global Criterion Method which is given in Table 3. The result of the goal programming solution is given in Table 4.Table 4
Solutions from the goal programming.
Method I (from model (36))Method II (from model (37))Minz0.038030010.03132063f10.40829410.3518664f22.2456171.944759f32.8580592.482053x10.20414700.1664387x20.20414700.1854276d1−0.0017059260.008133627d1+0.0000000.000000d2−0.0043825950.005240505d2+0.0000000.000000d3−0.031941480.01794650d3+0.0000000.000000Membership function method is used for Pareto optimal solution. The procedure is as follows: first, structure membership functionμlflx is generated for every objective function flx. Second, μlflx is used as the new objective function for the structure of the new multiobjective programming problem. Then, this converts the new multiobjective programming problem into a single-objective programming problem by using appropriate methods. Finally, single-objective programming problem is solved to get the optimal solution, which is also the Pareto optimal solution of the original multiobjective programming problem [41]. Structure of the membership function for every objective function is as follows:(38)μlflx=flx−minx∈Xflxmaxx∈Xflx−minx∈Xflx,l=1,2,…,K.Pareto optimal solutions for model (36) is given in Table 5.Table 5
Pareto optimal solution for Method I (from model (36)).
w1w2w3f1f2f3x1x2Maxz0,40,40,20.4082852.245572.8579980.2041430.2041430.9976620,20,80,00.4076122.2467362.8630250.1989350.2086771.0001240,01,00,00.4056862.2478862.8730290.1862280.2194581.0011440,20,60,20.406562.2476792.8691190.1916780.2148810.9982780,20,40,40.4053352.2478572.8743740.1841520.2211830.9968160,60,00,40.408882.2440042.8524890.2092730.1996060.9953680,60,20,20.4095512.2412862.8443670.2160220.193530.998090,40,00,60.4062462.2478042.8706220.1896740.2165720.9938550,00,20,80.3990652.2412.885740.1533910.2456740.9987240,80,20,00.4082852.245572.8579980.2041430.2041430.9976620,20,00,80.4023182.2457322.882190.1681790.234140.9950990,00,80,20.4043352.2474852.8776290.1785260.2258090.9999270,80,00,20.4082852.245572.8579980.2041430.2041430.9976620,00,01,00.3968432.2368492.8863250.1442110.2526330.9991930,40,20,40.4073492.2470582.864720.1970360.2103130.9955660,60,40,00.4082862.245572.8579980.2041430.2041430.9976620,00,40,60.4010412.2441052.8840450.1621430.2388990.9987011,00,00,00.4082862.245572.8579980.2041450.2041400.9999990,20,20,60.4039262.2472262.8787490.1763290.2275970.9957520,40,60,00.4090652.2433742.8504870.2110180.1980471.000130,00,60,40.4027922.2462442.8813190.1705080.2322840.999108If model (36) is analyzed for Pareto optimal solutions, optimal solution for f1 is obtained when w1 = 1 and w2 = w3 = 0. According to this, functions are resulted as f1 = 0.408286, f2 = 2.24557, and f3 = 2.857998. Optimal solution for f2is obtained when w2 = 1 and w1 = w3 = 0. According to this, functions are resulted as f1 = 0.405686, f2 = 2.247886, and f3 = 2.873029. Optimal solution for f3 is obtained when w3 = 1 and w2 = w1 = 0. According to this, functions are resulted as f1 = 0.396843, f2 = 2.236849, and f3 = 2.886325. Graphical representations of Pareto optimal solution for model (36) are given in Figure 1.Figure 1
Graphical representations of the Pareto optimal solutions.If model (37) is analyzed for Pareto optimal solutions, optimal solution for f1 is obtained when w1 = 1 and w2 = w3 = 0. According to this, functions are resulted as f1 = 0.3598632, f2 = 1.919270, and f3 = 2.399088. Optimal solution for f2 is obtained when w2 = 1 and w1 = w3 = 0. According to this, functions are resulted as f1 = 0.3546770, f2 = 1.946318, and f3 = 2.473929. Optimal solution for f3 is obtained when w3 = 1 and w2 = w1 = 0. According to this, functions are resulted as f1 = 0.3458346, f2 = 1.935281, and f3 = 2.487224. Graphical representations of Pareto optimal solution for model (37) are given in Figure 1.


## 7. Results and Discussions

In this paper, we have considered a chance-constrained programming problem under the assumption that the random variablesaij are independent with gamma distributions. The main purpose of this paper is to transform the chance-constrained model into a deterministic model based on two proposed methods. Method I provides exact solutions for the conversion of a chance constraint into a deterministic constraint. Using Method I, we found the probability density function of a linear combination of n independent random variables. Then, using the probability density function, the chance constraints are transformed into deterministic constraints. For large values of n, we proposed Method II, which is an approximation method. As can be seen in the example in Table 1, the numerical results for the exact and approximate models are rather close to each other. In this case, we first used Method I; however, because of the complex and difficult calculations in Method I, Method II can also be used.As can be seen in Table2, for multiobjective problems, we calculated the objective value by considering all objective functions and then summarized the solutions of the deterministic model under the two methods. We compared the solutions of the deterministic model according to the decision variables and objective functions. Even for the special case with n=2, the objective values obtained from Method I and Method II are very similar. According to Lyapunov’s central limit theorem, it is obvious that we can obtain more approximate solutions for larger values of n.For the multiobjective case, solutions are presented in Table5. In the case of p=2, the decrease in deviations from the ideal solutions can be observed in objective values. As such, the numerical results from these two methods are very close to one another. For multiobjective problems, the Global Criterion Method provides more effective solutions after converting chance constraints to deterministic constraints.Considering the results obtained from the real-life problem in Section6, Table 3 is created as a summary. The multiobjective problems that are solved by Global Criterion Method are also solved by goal programming, and the results are given in Table 4. Also, Pareto optimal solutions for these problems are obtained, and the results are given in Tables 5 and 6, respectively. Graphical representations of these Pareto optimal solutions are also provided. According to the results provided in the table, optimal solutions for the tree objective functions can be summarized as follows:1st objective function: Method I (p=2) is the optimal solution, where f1 = 0.3802155≅0.38. The result demonstrates that, with sending minimum data as only integer value, the maximum total data sent can reach 0.38 MB of data.2nd objective function: Method I (p=1) is the optimal solution, where f2 = 2.191725≅2.19. The result demonstrates that, with sending medium size data as float values, the maximum total data sent can reach 2.19 MB of data.3rd objective function: Method I (p=1) is the optimal solution, where f3 = 2.865135≅2.87. The result demonstrates that, with sending minimum data as float values and their headers, the maximum total data sent can reach 2.87 MB of data.Table 6
Pareto optimal solution for Method II (from model (37)).
w1w2w3f1f2f3x1x2Maxz0,40,40,20.35727671.9440022.4588970.19965830.15761840.99437180,20,80,00.35660311.9451682.4639240.19445040.16215270.99771610,01,00,00.35467701.9463182.4739290.18174370.17293331.0000010,20,60,20.35555071.9461112.4700180.18719390.16835690.99615640,20,40,40.35432611.9462892.4752730.17966760.17465850.99499540,60,00,40.35787081.9424362.4533890.20478890.15308190.99123710,60,20,20.35854261.9397182.4452660.21153740.14700520.99374650,40,00,60.35523761.9462362.4715210.18518990.17004770.99107100,00,20,80.34805651.9394332.4866390.14890640.19915010.99910520,80,20,00.35966671.9288122.4189570.22918830.13047840.99776460,20,00,80.35130971.9441642.4830900.16369410.18761560.99391720,00,80,20.35332631.9459162.4785270.17404160.17928480.99913630,80,00,20.35937691.9333432.4291780.22291860.13645840.99425180,00,01,00.34583461.9352812.4872240.13972630.20610831.0000010,40,20,40.35634021.9454902.4656190.19255120.16378900.99252510,60,40,00.35907001.9363332.4363870.21808660.14098340.99662580,00,40,60.35003251.9425372.4849440.15765810.19237450.99867381,00,00,00.35986321.9192702.3990880.23990880.11995441.0000000,20,20,60.35291701.9456582.4796470.17184450.18107260.99424460,40,60,00.35805671.9418062.4513860.20653390.15152280.99660150,00,60,40.35178321.9446752.4822180.16602400.18575930.9986893The obtained results show that the methods provided can be applicable to such problems and the solutions prove that an optimal design can be achieved by our study. By comparing the values of objective functions, the designers may benefit the most applicable solution to their problems.



---

*Source: 9096272-2021-10-19.xml*