Genetic Algorithm-Based Approaches for Solving Inexact Optimization Problems and their Applications for Municipal Solid Waste Management

Abstract

This chapter proposes a genetic algorithm (GA)-based approach as an all-purpose problem-solving method for optimization problems with uncertainty. This chapter explains the GA-based method and presents details on the computation procedures involved for solving the three types of inexact optimization problems, which include the ILP, inexact quadratic programming (IQP) and inexact nonlinear programming (INLP) optimization problems.

1. Introduction

Linear and nonlinear programming are considered powerful optimization tools suitable for modeling and solving complex optimization problems in engineering. To handle uncertainty in real world data, inexact parameters and constraints are combined with various kinds of optimization techniques. Often a detailed solution of an inexact programming optimization problem involves a large number of direct comparisons to interactively identify the uncertain relationships among the objective function and decision variables, whether the problems are medium-sized or larger-scaled. When these methods are applied to complicated and nonlinear problems, the number of direct comparisons can become exponential.

The genetic algorithm (GA) method is a suitable optimization approach especially for solving problems that involve nonsmooth and multimodal search spaces. The GA-based optimization technique is suitable for solving linear and nonlinear programming optimization problems with inexact information; and the fields of application include operations research, industrial engineering and management science.

This chapter is organized as follows. Section 2 presents the background and literature review of this research. Section 3 discusses the proposed GA-based methods for solving inexact linear programming (ILP), inexact quadratic programming (IQP) and inexact nonlinear programming (INLP) problems. Section 4 presents the case study of using GAINLP in the solution of an INLP problem of solid waste disposal planning. Section 5 is the conclusion.

2. Background and literature review

Economic optimization in the operation programming of solid waste management was first proposed in the 1960s [1]. Different models of waste management planning have been developed in the following decades. The primary considerations involved include cost control, environmental sustainability and waste reutilization. The techniques employed include linear programming [2–5], mixed integer linear programming [6], multiobjective programming [7–9], nonlinear programming [10, 11], as well as their hybrids, which involve probability, fuzzy set and inexact analysis [12–16]. Due to complexity of the nonlinear programming problems for solid waste management, research works in the area are scant; some exceptions include [17, 18].

The approach of operational programming with inexact analysis often treats the uncertain parameters as intervals with known lower and upper bounds and unclear distributions. In real-life problems, while the available information is often inadequate and the distribution functions are often unknown, it is generally possible to represent the obtained data with inexact numbers that can be readily used in the inexact programming models. For decision makers, it is usually more feasible to represent uncertain information as inexact data than to specify distributions of fuzzy sets or probability functions. Hence, various kinds of inexact programming such as ILP, IQP, inexact integer programming (IIP), inexact dynamic programming (IDP) and inexact multiobjective programming (IMOP) have been developed and are well discussed [10, 11, 19]. It can be observed from these studies that applications of inexact models to practical solid waste planning systems are effective. These research reports demonstrated substantial effort has been developed to traditional binary analysis for ILP and IQP. However, traditional binary analysis methods for ILP and IQP involve unavoidable simplifications and assumptions, which often increase the chance for error in the problem-solving process and adversely affected the quality of the results. Moreover, a more complex model often increases the chance of error in the solution. It has been observed that more complex models often produce less optimal results, and studies that focus on INLP problems are scarce. For example, in [20], the methodology mainly focused on combining endpoint values of the inexact parameters to form a set of deterministic problems, which will only work for particular monotone functions within a small-scale model. Therefore, a more flexible problem-solving method for the general inexact optimization problems is desired.

Engineering problems that have traditionally been formulated as IQP or INLP problems often involve large and uneven search spaces, for which a global optimal solution is often not required. GA is a suitable optimization tool especially for solving complex and nonlinear problems, which involve nonsmooth and multimodal search spaces. Therefore, we suggest a GA-based method as a more effective problem-solving approach than the traditional inexact programming methods.

For implementation of GA, the Genetic Algorithm Solver of Global Optimization Toolbox (GASGOT), developed by MATLAB (Trademark of MathWord), has been adopted. GASGOT implements simulated evolution in the MATLAB environment using both binary and floating point representations and the ordered base representation. This enables flexible implementation of the genetic operators, selection functions, termination functions and evaluation functions. GASGOT was developed by the Department of Industrial Engineering of North Carolina State University as a toolbox of MATLAB. Hence, it runs in a MATLAB workspace and can be easily invoked by other programs.

In this study, the GA linear program solving engine of GASGOT has been adopted for ILP problems and GA nonlinear program solving engine of GASGOT has been adopted for IQP and INLP problems.

3. Methodology

3.1. GA-based method for solving ILP problems (GAILP)

A typical ILP problem can be expressed as follows:

$Max{f}^{\pm }={\displaystyle {\displaystyle \sum }_{j=1}^n}[c_j^{\pm }{x}_j^{\pm }]$E1

$s.t.{\displaystyle {\displaystyle \sum }_{j=1}^n}{a}_{ij}^{\pm }{x}_j^{\pm }\le b_i^{\pm },i=1,2,\dots m$E200

$x_j^{\pm }\ge 0,j=1,2,\dots ,n$E300

where $a_{ij}^{\pm },b_i^{\pm },c_j^{\pm }$are inexact parameters and $x_j^{\pm }$is an inexact variable. It is assumed that an optimal solution exists. For an inexact number $g^{\pm }\in [g^{-},g^{+}]$, $g^{+}$and $g^{-}$are the upper and lower bounds, respectively.

GA has been adopted for solving ILP problem. In this GA approach, the upper and lower bounds of the inexact numbers of coefficients $a_{ij}^{\pm },b_i^{\pm },c_j^{\pm }$can be determined by substituting the initial suboptimal decision variables into the objective function. $f^{+}$and $f^{-}$can be calculated directly without any uncertainty in the coefficients. This approach is called the GA-based method for solving ILP problems, or the GAILP method.

GAILP has been designed to include three stages, which are discussed as follows:

The objective of the first stage is to get an initial suboptimal $x_j^s$for the following problem, which is transformed from the ILP problem defined in Eq. (1):

$Max{f}^{\pm }={\displaystyle {\displaystyle \sum }_{j=1}^n}[c_j^r{x}_j^s]$E2

$s.t.{\displaystyle {\displaystyle \sum }_{j=1}^n}{a}_{ij}^r{x}_j^s\le b_i^r,i=1,2,\dots ,m$E5

$x_j\ge 0,j=1,2,\dots ,n$E6

Where $a_{ij}^r,b_i^r,c_j^r$are random numbers that satisfy the continuous uniform distribution in the intervals of $[a_{ij}^{-},a_{ij}^{+}]$, $[b_i^{-},b_i^{+}]$and $[c_j^{-},c_j^{+}]$,respectively. Then, the problem is solved by the GA linear program solving engine of GASGOT, which uses the objective function in Eq. (2) as the positive term of the fitness function and the constraints of Eq. (1) as the negative punishment terms. Thus, a suboptimal solution $f^s$can be identified and the corresponding decision variables of $x_j^s$are also obtained.

In the second stage, the inexact coefficients of $a_{ij}^{\pm },b_i^{\pm },c_j^{\pm }$will be determined. Let the determined coefficients corresponding to $f^{+}$be $a_{ij}^{{\pm }^{+}},b_i^{{\pm }^{+}},c_j^{{\pm }^{+}}$and those corresponding to $f^{-}$be $a_{ij}^{{\pm }^{-}},b_i^{{\pm }^{-}},c_j^{{\pm }^{-}}$. These two sets of coefficients can be obtained using the following method.

Substituting $x_j^s$into the formula of Eq. (1) will convert it into Eq. (3).

$Max{f}^{\pm }={\displaystyle {\displaystyle \sum }_{j=1}^n}[c_j^{\pm }{x}_j^s]$E3

$s.t.{\displaystyle {\displaystyle \sum }_{j=1}^n}{a}_{ij}^{\pm }{x}_j^s\le b_i^{\pm },i=1,2,\dots ,m$E800

To identify the coefficients $a_{ij}^{\pm },b_i^{\pm },c_j^{\pm }$corresponding to $f^{\pm }$, a set of objective functions needs to be constructed and solved. Since $x_j^s$are suboptimal variables, which tend to make the objective function closer to $f^{+}$, consider $a_{ij}^{\pm },b_i^{\pm },c_j^{\pm }$as variables, then the objective function of Eq. (4) can be constructed so as to find $c_j^{{\pm }^{+}}$.

$Max{f}^{\pm }={\displaystyle {\displaystyle \sum }_{j=1}^n}[c_j^{\pm }{x}_j^s]$E4

$s.t.{\displaystyle {\displaystyle \sum }_{j=1}^n}{a}_{ij}^{\pm }{x}_j^s\le b_i^{\pm },i=1,2,\dots ,m$E1000

The coefficients $c_j^{{\pm }^{+}}$are considered to be corresponding to $f^{+}$.

Meanwhile, the objective function presented in Eq. (5) can be constructed so as to find $c_j^{{\pm }^{-}}$.

$Min{f}^{\pm }={\displaystyle {\displaystyle \sum }_{j=1}^n}[c_j^{\pm }{x}_j^s]$E5

$s.t.{\displaystyle {\displaystyle \sum }_{j=1}^n}{a}_{ij}^{\pm }{x}_j^s\le b_i^{\pm },i=1,2,\dots ,m$E120

There are two kinds of decision schemes for inexact programming problems, which are the conservative scheme and the optimistic scheme [21]. The former assumes less risk than the latter, so that for a maximization objective function, planning for the lower bound of an objective value represents the conservative scheme and planning for the upper bound of an objective value represents the optimistic scheme. In terms of constraints, the conservative scheme involves more rigorous or stringent constraints and the optimistic scheme adopts more tolerant ones.

Thus, the problem of searching for $a_{ij}^{{\pm }^{+}},b_i^{{\pm }^{+}}$of the optimistic scheme and corresponding to the upper bound of the objective value of $f^{+}$can be represented as follows:

$Max{\displaystyle {\displaystyle \sum }_{j=1}^n}abs(a_{ij}^{\pm }{x}_j^s-b_i^{\pm })$E6

$s.t.{\displaystyle {\displaystyle \sum }_{j=1}^n}{a}_{ij}^{\pm }{x}_j^s\le b_i^{\pm },i=1,2,\dots ,m$E140

The problem,

$Min{\displaystyle {\displaystyle \sum }_{j=1}^n}abs(a_{ij}^{\pm }{x}_j^s-b_i^{\pm })$E7

$s.t.{\displaystyle {\displaystyle \sum }_{j=1}^n}{a}_{ij}^{\pm }{x}_j^s\le b_i^{\pm },i=1,2,\dots ,m$E160

will give $a_{ij}^{{\pm }^{-}},b_i^{{\pm }^{-}}$of the conservative scheme, corresponding to the lower bound of the objective value of $f^{-}$.

Hence, the values of $a_{ij}^{{\pm }^{+}},b_i^{{\pm }^{+}},c_j^{{\pm }^{+}}$and $a_{ij}^{{\pm }^{-}},b_i^{{\pm }^{-}},c_j^{{\pm }^{-}}$can be calculated.

In the third stage, the problem represented in Eq. (1) is converted into the following two subproblems:

For $f^{+}$,

$Max{f}^{+}={\displaystyle {\displaystyle \sum }_{j=1}^n}[c_j^{{\pm }^{+}}{x}_j^{\pm }]$E8

$s.t.{\displaystyle {\displaystyle \sum }_{j=1}^n}{a}_{ij}^{{\pm }^{+}}{x}_j^{\pm }\le b_i^{{\pm }^{+}},i=1,2,\dots ,m$E180

$x_j^{\pm }\ge 0,j=1,2,\dots ,n$E190

For $f^{-}$,

$Max{f}^{-}={\displaystyle {\displaystyle \sum }_{j=1}^n}[c_j^{{\pm }^{-}}{x}_j^{\pm }]$E9

$s.t.{\displaystyle {\displaystyle \sum }_{j=1}^n}{a}_{ij}^{{\pm }^{-}}{x}_j^{\pm }\le b_i^{{\pm }^{-}},i=1,2,\dots ,m$E210

$x_j^{\pm }\ge 0,j=1,2,\dots ,n$E220

This step eliminates the inexact parameters in Eq. (1) and generates instead Eq. (8) and Eq. (9) as typical linear programming (LP) problems, which can be solved easily.

Generally speaking, the interactive binary algorithm (IBA) proposed in [19, 22] can be used for solving inexact linear problems reliably and relatively quickly. However, this binary algorithm has some limitations. One of them, for example, is the limitation that the upper and lower bounds of an inexact coefficient cannot have different signs. In contrast, the GAILP does not have this kind of limitation because the GA method does not depend on any assumed distribution of the inexact parameter. Hence, the GAILP method effectively extends the scope of problems solvable using the methods of ILP. It is more adaptable for real world applications of optimization problems with uncertainty.

A sample ILP problem in [22] is as follows,

$Max{f}^{\pm }=c_1{x}_1^{\pm }+c_2{x}_2^{\pm }$E10

$s.t.a_{11}{x}_1^{\pm }+a_{12}{x}_2^{\pm }\le b_1$E240

$a_{21}{x}_1^{\pm }+a_{22}{x}_2^{\pm }\le b_2$E250

where c₁ = [26 , 30], c₂ = [− 6, − 5.5], a₁₁ = [8, 10], a₁₂ = [− 14, − 12], b₁ = [3.8, 4.2], a₂₁ = [2.4, 2.8], a₂₂ = [3.4, 4], b₂ = 6.5

By using the traditional IBA method [22], two submodels are obtained,

$Max{f}^{+}=30x_1^{+}-5.5x_2^{-}$E26

$s.t.8x_1^{+}-14x_2^{-}\le 4.2$E27

$2.4x_1^{+}+4x_2^{-}\le 6.5$E28

$x_1^{+}\ge 0,x_2^{-}\ge 0$E29

and

$Max{f}^{-}=26x_1^{-}-6.0x_2^{+}$E30

$s.t.10x_1^{-}-12x_2^{+}\le 3.8$E31

$2.8x_1^{-}+3.4x_2^{+}\le 6.5$E32

$x_1^{-}\ge 0,x_2^{+}\ge 0$E33

The results were $f^{+}=45.78,x_1=1.64,x_2=0.64;f^{-}=30.77,x_1=1.37,x_2=0.79$.

By using the GAILP, the results can be calculated with the following objective functions:

$Max{f}^{+}=30x_1^{+}-5.5x_2^{+}$E34

$s.t.8x_1^{+}-14x_2^{+}\le 4.2$E35

$2.4x_1^{+}+3.4x_2^{+}\le 6.5$E36

$x_1^{+}\ge 0,x_2^{+}\ge 0$E37

and

$Max{f}^{-}=26x_1^{-}-6.0x_2^{-}$E38

$s.t.10x_1^{-}-12x_2^{-}\le 3.8$E39

$2.8x_1^{-}+4x_2^{-}\le 6.5$E40

$x_1^{-}\ge 0,x_2^{-}\ge 0$E41

The results were $f^{+}=48.15,x_1=1.73,x_2=0.69;f^{-}=29.15,x_1=1.29,x_2=0.72$.

The GAILP method generates a solution, which is different from that obtained using the IBA proposed in [22]. A comparison will be discussed as follows:

For the $f^{+}$optimistic scheme, the GAILP method can generate a result that is guaranteed to be as close as possible to the upper bound of the constraints. Hence, the maximized value of the objective function is greater than that produced by the IBA. For the $f^{-}$conservative scheme, the GAILP method has a higher probability of satisfying the requirements of the constraints as close as possible to the lowest limit. Hence, the maximized objective value is smaller.

Figure 1.

Optimistic scheme,$f^{+}$.

Figure 2.

Zoom-in of the optimistic scheme,$f^{+}$.

In Figures 1 to 4, the bold lines denote the boundaries of the constraints, which limit the possible values for $x_1,x_2$to the left lower area. The constraint $a_{11}{x}_1^{\pm }+a_{12}{x}_2^{\pm }\le b_1$is shown in these figures as the grey bold solid lines, which is the same for both the IBA and GAILP methods. The dark bold dotted lines represent the constraint of $a_{21}{x}_1^{\pm }+a_{22}{x}_2^{\pm }\le b_2$given by the IBA and the dark bold solid lines represent the same constraint given by the proposed GAILP method.

The boundaries, together with the x₁, x₂ axes, enclose the entire area defined by the constraints. The objective functions $f^{+}=30x_1^{+}-5.5x_2^{+}$or $f^{-}=26x_1^{-}-6x_2^{-}$are groups of parallel lines, as shown in Figures 1 to 4 by the thin solid and dotted lines. With different values of $x_1$and $x_2$, these objective function lines would produce different intercepts on the two axes. These constraints restrict the objective function lines to cross with the constraints area, so that, at some vertex, the objective function would reach its extreme (i.e., maximized or minimized) values.

In Figures 1 to 4, the thin dotted lines are given by the IBA and the thin solid lines represent the objective functions given by the proposed GAILP method. The legends for Figure 1 to 4 are listed in Table 1.

Figure 3.

Conservative scheme,$f^{-}$.

Figure 4.

Zoom-in of the conservative scheme,$f^{-}$.

Table 1.

Legends for Figures 1 to 4.

3.2. GA-based method for solving IQP problems (GAIQP)

The GAILP method can be extended to solve the IQP problems or other more complicated INLP problems.

A typical IQP problem is formulated as follows:

$Max{f}^{\pm }={\sum }_{j=1}^n[c_j^{\pm }{x}_j^{\pm }+d_j^{\pm }{\left(x_j^{\pm }\right)}^2]$E11

$s.t.{\displaystyle {\displaystyle \sum _{j=1}^n}{a}_{ij}^{\pm }{x}_j^{\pm }\le b_i^{\pm },i=1,2,\dots m}$E43

$x_j^{\pm }\ge 0,j=1,2,\dots ,n$E44

where $a_{ij}^{\pm },b_i^{\pm },c_j^{\pm },d_j^{\pm }$are inexact parameters and $x_j^{\pm }$is an inexact variable.

In stage one, to obtain an initial suboptimal $x_j^s$from a problem transformed from the IQP problem:

$Maxf={\sum }_{j=1}^n[c_j^r{x}_j+d_j^r{\left({\text{x}}_{\text{j}}\right)}^2]$E12

$s.t.{\displaystyle {\displaystyle \sum _{j=1}^n}{a}_{ij}^r{x}_j^r\le b_j^r,i=1,2,\dots ,m}$E46

$x_j\ge 0,j=1,2,\dots ,n.$E47

where $a_{ij}^r,b_i^r,c_j^r,d_j^r$are random numbers that satisfy the continuous uniform distribution in the intervals $[a_{ij}^{-},a_{ij}^{+}],[b_i^{-},b_i^{+}],[c_j^{-},c_j^{+}]$and $[d_j^{-},d_j^{+}]$. Then, a suboptimal solution $f^s$can be identified, and the corresponding decision variables $x_j^s$are also obtained.

In the second stage, substituting $x_j^s$into the formula in Eq. (11). To determine the coefficients $a_{ij}^{\pm },b_i^{\pm },c_j^{\pm },d_j^{\pm }$corresponding to $f^{\pm }$

$Max{f}^{\pm }={\sum }_{j=1}^n[c_j^{\pm }{x}_j^s+d_j^{\pm }{\left(x_j^s\right)}^2]$E13

$s.t.{\displaystyle {\displaystyle \sum _{j=1}^n}{a}_{ij}^{\pm }{x}_j^s\le b_i^{\pm },i=1,2,\dots ,m}$E49

and

$Min{f}^{\pm }={\sum }_{j=1}^n[c_j^{\pm }{x}_j^s+d_j^{\pm }{\left(x_j^s\right)}^2]$E14

$s.t.{\displaystyle {\displaystyle \sum _{j=1}^n}{a}_{ij}^{\pm }{x}_j^s\le b_i^{\pm },i=1,2,\dots ,m}$E51

To determine $a_j^{{\pm }^{+}},b_i^{{\pm }^{+}}$of the optimistic scheme and corresponding to the upper limit of the objective value of$f^{+}$

$Max{\sum }_{j=1}^{n}abs\left(a_{ij}^{\pm }{x}_j^s-b_i^{\pm }\right)$E15

$s.t.{\displaystyle {\displaystyle \sum _{j=1}^n}{a}_{ij}^{\pm }{x}_j^s\le b_i^{\pm },i=1,2,\dots ,m}$E53

To obtain$a_j^{{\pm }^{-}},b_i^{{\pm }^{-}}$,

$Min{\sum }_{j=1}^{n}abs\left(a_{ij}^{\pm }{x}_j^s-b_i^{\pm }\right)$E16

$s.t.{\displaystyle {\displaystyle \sum _{j=1}^n}{a}_{ij}^{\pm }{x}_j^s\le b_i^{\pm },i=1,2,\dots ,m}$E55

In the third stage, the problem expressed in Eq. (11) has been converted into the following two subproblems:

For $f^{+}$,

$Max{f}^{+}={\sum }_{j=1}^n[c_j^{{\pm }^{+}}{x}_j^{\pm }+d_j^{{\pm }^{+}}{\left(x_j^{\pm }\right)}^2]$E17

$s.t.{\displaystyle {\displaystyle \sum _{j=1}^n}{a}_{ij}^{{\pm }^{+}}{x}_j^{\pm }\le b_i^{{\pm }^{+}},i=1,2,\dots ,m}$E57

$x_j^{\pm }\ge 0,j=1,2,\dots ,n$E58

For $f^{-}$,

$Max{f}^{-}={\sum }_{j=1}^n[c_j^{{\pm }^{-}}{x}_j^{\pm }+d_j^{{\pm }^{-}}{\left(x_j^{\pm }\right)}^2]$E18

$s.t.{\displaystyle {\displaystyle \sum _{j=1}^n}{a}_{ij}^{{\pm }^{-}}{x}_j^{\pm }\le b_i^{{\pm }^{-}},i=1,2,\dots ,m}$E60

$x_j^{\pm }\ge 0,j=1,2,\dots ,n$E61

The inexact information has been incorporated in these two subproblems. These two subproblems, as typical nonlinear programming problems, can be solved by the GA nonlinear program solving engine of GASGOT.

3.3. GA-based method for solving inexact nonlinear problems (GAINLP)

Quadratic programming problems are specific cases of nonlinear programming problems. Due to the lack of generally applicable algorithms for handling the nonlinear structure and the inexact information embedded in the structure, most nonlinear programming problems are difficult to solve. The IBA method proposed in [11, 22] is not intended for dealing with generic nonlinear problems. In contrast, the GA-based method can be used as a general problem solver for this type of problems because there is not much difference for GA between treating the term of $x_i^2$in quadratic programming problems and the terms $x_i{x}_j$or $x_i^{0.28}$in generic nonlinear programming problems. GAIQP can be modified to solve generic inexact nonlinear programming.

In the following, a computation experiment will be conducted to illustrate how the GAINLP method can handle complicated inexact nonlinear problems. A sample INLP problem is as follows:

$Max{f}^{\pm }=c_1^{\pm }{x}_1^{\pm }-c_2^{\pm }{\left(x_1^{\pm }\right)}^{0.3}-d_1^{\pm }{x}_2^{\pm }+d_2^{\pm }\left(x_1^{\pm }{x}_2^{\pm }\right)$E19

$s.t.a_{11}^{\pm }{\left(x_1^{\pm }\right)}^{0.5}+a_{12}^{\pm }{x}_2^{\pm }\le b_1^{\pm },$E63

$x_1^{\pm }+a_2^{\pm }{x}_2^{\pm }\le b_2^{\pm },$E64

$x_j^{\pm }\ge 0,j=1,2.$E65

where $a_{ij}^{\pm },b_i^{\pm },c_j^{\pm },d_j^{\pm }$are inexact parameters and $x_j^{\pm }$is an inexact variable. In this experiment,

$[c_1^{-},c_1^{+}]=[16,18];[c_2^{-},c_2^{+}]=[12,14];[d_1^{-},d_1^{+}]=[4,5];[d_2^{-},d_2^{+}]=[14,15];[a_{11}^{-},a_{11}^{+}]=[4.5,5.5];[a_{12}^{-},a_{12}^{+}]=[1.8,2.2];[b_1^{-},b_1^{+}]=[1.8,2.1];[a_2^{-},a_2^{+}]=[1.8,2.2];[b_2^{-},b_2^{+}]=[0.9,1.1]\text{.}$E66

GAINLP has been designed to include the three stages of problem solving.

In stage one, to obtain the initial suboptimal $x_j^s$, the random numbers of $a_{ij}^r,b_i^r,c_j^r,d_j^r$were selected to transform this INLP problem into a NLP problem, such that $a_{ij}^r,b_i^r,c_j^r,d_j^r$satisfy the continuous uniform distribution in the intervals of $[a_{ij}^{-},a_{ij}^{+}],[b_i^{-},b_i^{+}],[c_j^{-},c_j^{+}]$and $[d_j^{-},d_j^{+}]$.

$Max{f}^s=c_1^r{x}_1^s-c_2^r{\left(x_1^s\right)}^{0.3}-d_1^r{x}_2^s+d_2^r\left(x_1^s{x}_2^s\right)$E20

$s\text{.}t\text{.}{a}_{11}^r{\left(x_1^s\right)}^{0.5}+a_{12}^r{x}_2^s\le b_1^r,$E68

$x_1^s+a_2^r{x}_2^s\le b_2^r,$E69

$x_j^s\ge 0,j=1,2.$E70

Then, the heuristic search algorithm of the GA nonlinear program solving engine of GASGOT can be used to identify a suboptimal solution $f^s$, and the corresponding decision variable $x_j^s$. The objective function in Eq. (20) was used as the positive term of the fitness function and the constraints of Eq. (19) adopted as the negative punishment terms. The results are $x_1^s=0.346,x_2^s=0.171,f^s=-2.296$.

In stage two, by substituting $x_1^s,x_2^s$into Eq. (19), the inexact coefficients of $a_{ij}^{\pm },b_i^{\pm },c_j^{\pm },d_j^{\pm }$will be determined. The$x_1^s,x_2^s$obtained in stage one are used to construct two optimization problems in order to determine the coefficients of $a_{ij}^{{\pm }^{+}},b_i^{{\pm }^{+}},c_j^{{\pm }^{+}},d_j^{{\pm }^{+}}$and $a_{ij}^{{\pm }^{-}},b_i^{{\pm }^{-}},c_j^{{\pm }^{-}},d_j^{{\pm }^{-}}$, respectively. The coefficients from the first group are considered to be corresponding to the optimistic scheme $f^{+}$, while those from the second group correspond to the conservative scheme $f^{-}$. Considering $c_j^{\pm },d_j^{\pm }$are variables, the following two objective functions can be constructed:

$Max{f}^{+}=c_1^{{\pm }^{+}}{x}_1^s-c_2^{{\pm }^{+}}{\left(x_1^s\right)}^{0.3}-d_1^{{\pm }^{+}}{x}_2^s+d_2^{{\pm }^{+}}\left(x_1^s{x}_2^s\right)$E21

and

$Min{f}^{-}=c_1^{{\pm }^{-}}{x}_1^s-c_2^{{\pm }^{-}}{\left(x_1^s\right)}^{0.3}-d_1^{{\pm }^{-}}{x}_2^s+d_2^{{\pm }^{-}}\left(x_1^s{x}_2^s\right)$E22

$s\text{.}t\text{.}{c}_1^{{\pm }^{+}},c_1^{{\pm }^{-}}\in \left[16,18\right]$E73

$c_2^{{\pm }^{+}},c_2^{{\pm }^{-}}\in \left[12,14\right]$E74

$d_1^{{\pm }^{+}},d_1^{{\pm }^{-}}\in \left[4,5\right]$E75

$d_2^{{\pm }^{+}},d_2^{{\pm }^{-}}\in [14,15]$E76

To determine $a_{ij}^{{\pm }^{+}},b_i^{{\pm }^{+}}$of the optimistic scheme corresponding to the upper limit of the objective value $f^{+}$, the objective function can be constructed as follows:

$M\text{a}xabs\left(a_{11}^{\pm }{\left(x_1^s\right)}^{0.5}+a_{12}^{\pm }{x}_2^s-b_1^{\pm }\right)$E23

$\text{s}\text{.t}\text{.}{a}_{11}^{\pm }{\left(x_1^s\right)}^{0.5}+a_{12}^{\pm }{x}_2^s\le b_1^{\pm }$E78

and

$Maxabs(x_1^s+a_2^{\pm }{x}_2^s-b_2^{\pm })$E79

$s\text{.}t\text{.}{x}_1^s+a_2^{\pm }{x}_2^s\le b_2^{\pm }$E80

The objective functions to get $a_{ij}^{{\pm }^{-}},b_i^{{\pm }^{-}}$of the conservative scheme are

$Minabs\left(a_{11}^{\pm }{\left(x_1^s\right)}^{0.5}+a_{12}^{\pm }{x}_2^s-b_1^{\pm }\right)$E24

$s\text{.}t\text{.}{a}_{11}^{\pm }{\left(x_1^s\right)}^{0.5}+a_{12}^{\pm }{x}_2^s\le b_1^{\pm }$E82

and

$Minabs(x_1^s+a_2^{\pm }{x}_2^s-b_2^{\pm })$E83

$s\text{.}t\text{.}{x}_1^s+a_2^{\pm }{x}_2^s\le b_2^{\pm }$E84

By solving Eqs. (21)–(24), the values of all the inexact coefficients are obtained, i.e., $a_{11}^{{\pm }^{+}}=4.5,a_{12}^{{\pm }^{+}}=1.8,b_1^{{\pm }^{-}}=2.1,a_2^{{\pm }^{+}}=1.8,b_2^{{\pm }^{+}}=1.1;$$a_{11}^{{\pm }^{-}}=5.5,a_{12}^{{\pm }^{-}}=2.2,b_1^{{\pm }^{-}}=1.8,a_2^{{\pm }^{-}}=2.2,b_2^{{\pm }^{-}}=0.9$; $c_1^{{\pm }^{+}}=18,c_2^{{\pm }^{+}}=12,d_1^{{\pm }^{+}}=4,d_2^{{\pm }^{+}}=15$; $c_1^{{\pm }^{-}}=16,c_2^{{\pm }^{-}}=14,d_1^{{\pm }^{-}}=5,d_2^{{\pm }^{-}}=14$

In stage three, the objective function presented in Eq. (20) is converted into the following two subproblems:

$Max{f}^{+}=18x_1^{\pm }-12{\left(x_1^{\pm }\right)}^{0.3}-4x_2^{\pm }+15\left(x_1^{\pm }{x}_2^{\pm }\right)$E85

$s\text{.}t\mathrm{.4.5}{\left(x_1^{\pm }\right)}^{0.5}+1.8x_2^{\pm }\le 2.1,$E86

$x_1^{\pm }+1.8x_2^{\pm }\le 1.1,$E87

$x_1^{\pm }\ge 0,x_2^{\pm }\ge 0.$E88

and

$Max{f}^{-}=16x_1^{\pm }-14{\left(x_1^{\pm }\right)}^{0.3}-5x_2^{\pm }+14(x_1^{\pm }{x}_2^{\pm })$E89

$s\text{.}t\mathrm{.5.5}{\left(x_1^{\pm }\right)}^{0.5}+2.2x_2^{\pm }\le 1.8,$E90

$x_1^{\pm }+2.2x_2^{\pm }\le 0.9,$E91

$x_1^{\pm }\ge 0,x_2^{\pm }\ge 0.$E92

The inexact parameters in Eq. (20) have been eliminated, and two typical nonlinear optimization problems have been generated instead. The solution of the example (Eq. (19)) is$f^{\pm }=[-5.5575,-1.72]$, $x_1^{\pm }=[0.24727,0.38496]$, and $x_2^{\pm }=[0.1989,0.2053]\text{.}$

As demonstrated above, it can be seen that the GAINLP method can generate the optimal result without any simplification or assumption, and it can be adapted for applications of optimization problems with uncertainty. The next section demonstrates application of this method to a real world regional waste management problem.

4. Case study

Solid waste management is the process of removing waste materials from the surrounding environment, which involves the collection, separation, storage, processing, treatment, transport, recovery and disposal of solid waste. Landfill and incineration are two of the most commonly used solid waste disposal methods. The objective of a solid waste management process is to dispose discarded materials in a timely manner so as to prevent the spread of disease, minimize the likelihood of contamination and reduce their effects on human health and the environment.

The economy of scale (ES) is a microeconomics term, and it refers to the advantages that enterprises obtain due to their size or scale of operation, with the cost per unit of output generally decreasing as the scale increases and fixed costs are distributed over more units of output. In a solid waste management system, ES exists within the transportation process [23] and it can be expressed as a sizing model with a power law [11].

$C_t=C_{re}{\left(X_t/X_{re}\right)}^{1+m}$E25

where $X_t$(t/d) is a waste flow decision variable; $X_{re}$(t/d) is a reference waste flow; $C_t$($/t) is the transportation unit cost due to the ES of waste flow$X_t$(t/d); $C_{re}$($/t) is a coefficient reflecting the significance of the ES to the unit cost of waste transported for reference waste flow $X_{re}$(t/d), $C_{re}<0$; and mis an ES exponent which reflects the unit cost decline with respect to the waste flow, $-1<m<0$.

Figure 5.

Case study of municipalities and waste management facilities.

The study region includes three municipalities, a waste-to-energy (WTE) facility and a landfill, as shown in Figure 5. Three time periods are considered; each has an interval of five years. Over the 15-year planning horizon, an existing landfill and WTE facilities are available to serve the municipal solid waste (MSW) disposal needs in the region. The landfill has an existing capacity of $\left[2.05,2.30\right]\times {10}^6\text{t}$, and the WTE facility has a capacity of $\left[500,600\right]\text{t}/\text{d}$.The WTE facility generates residues of approximately $30\text{\%}$(on a mass basis) of the incoming waste streams, and its revenue from energy sale is $\left[15,25\right]\text{\$}/\text{t}$combusted.

Table 2 shows the waste generation rates of the three municipalities and the operating costs of the two facilities in the three periods.

Time period	k=1	k=2	k=3
Waste generation $W{G}_{jk}^{\pm }$(t/d)
Municipality 1 (j=1)	[260, 340]	[310, 390]	[360, 440]
Municipality 2 (j=2)	[160, 240]	[185, 265]	[210, 290]
Municipality 3 (j=3)	[260, 340]	[260, 340]	[310, 390]
Operation cost $O{P}_{ik}^{\pm }$($/t)
Landfill (i=1)	[30, 45]	[40, 60]	[50, 80]
WTE facility (i=2)	[55, 75]	[60, 85]	[65, 95]

Table 2.

Data for the waste generation and treatment/disposal.

Taking into consideration the effects of the ES, the INLP model can be formulated as follows:

$Min{f}^{\pm }={\displaystyle {\displaystyle \sum }_{i=1}^2}{\displaystyle {\displaystyle \sum }_{j=1}^3}{\displaystyle {\displaystyle \sum }_{k=1}^3}{L}_k{x}_{ijk}^{\pm }[A_{r{e}_{ijk}}^{\pm }+C_{r{e}_{ijk}}^{\pm }{\left(x_{ijk}^{\pm }/X_{r{e}_{ijk}}^{\pm }\right)}^{1+m}+\left(O{P}_{ik}^{\pm }\right)+{\displaystyle {\displaystyle \sum }_{k=1}^3}{L}_k(FE\ast {\displaystyle {\displaystyle \sum }_{j=1}^3}(x_{2jk}^{\pm }))\left\{A_{r{e}_{WTE-L{F}_k}}+C_{r{e}_{WTE-L{F}_k}}{(FE\ast {\displaystyle {\displaystyle \sum }_{j=1}^3}{x}_{2jk}^{\pm }/X_{re}{}_{WTE-L{F}_k}^{\pm })}^{1+m}+\left(O{P}_{1k}^{\pm }\right)\right\}-{\displaystyle {\displaystyle \sum }_{k=1}^3}{\displaystyle {\displaystyle \sum }_{j=1}^3}{x}_{2jk}^{\pm }R{E}_k^{\pm }$E26

$s\text{.}t\text{.}{\displaystyle {\displaystyle \sum }_{j=1}^3}{\displaystyle {\displaystyle \sum }_{k=1}^3}{L}_k\left[x_{1jk}^{\pm }+x_{2jk}^{\pm }FE\right]\le T{L}^{\pm }$E95

${\displaystyle {\displaystyle \sum }_{j=1}^3}{x}_{2jk}^{\pm }\le T{E}^{\pm },\forall k$E96

${\displaystyle {\displaystyle \sum }_{i=1}^2}{x}_{ijk}=W{G}_{jk}^{\pm },\forall j,k$E97

$X_{ijk}^{\pm }\ge 0,\forall i,j,k$E98

where iis the type of waste management facility ($i=1,2$, where $i=1$for landfill, 2 for WTE); jis the city, $j=1,2,3$; $k$is the time period, ; L_kis the length of period k, $L_1=L_2=L_3=365\ast 5$(day); $O{P}_{ik}^{\pm }$is the operating cost of facility during period k($/t); $R{E}_k^{\pm }$is the revenue from WTE during period k($/t), $R{E}_1^{\pm }=R{E}_2^{\pm }=R{E}_3^{\pm }=[15,25]$; $T{E}^{\pm }$is the capacity of WTE (t/d); $T{L}^{\pm }$is the capacity of the landfill (t); $W{G}_{jk}^{\pm }$is the waste disposal demand in city during period k(t/d); $x_{ijk}^{\pm }$is the waste flow from city jto facility iduring period k(t/d).

In this objective function (Eq. (26)), the first term on the right side reflects the transportation costs in each management period (k=1 to 3) from each city to each waste treatment unit, and the related operation costs. The second term reflects the cost incurred in transporting the products from the WTE facility to the landfill, and the operation cost at the landfill. The third term is the revenue generated from the WTE facility.

The MSW generation rates generally vary between different municipalities and for different periods, and the costs for the waste transportation and treatment also vary temporally and spatially. Furthermore, interactions exist between the waste flows and their transportation costs due to the effects of the ES (Eq. (25)). Table 3 and Table 4 show the parameters related to the ES, which include the fixed unit transportation cost $A_{re}$, the reference waste flow $X_{re}$and the coefficient $C_{re}$corresponding to $X_{re}$.

Fixed unit transportation cost ($/t)				Reference waste flow (t/d)
	k=1	k=2	k=3		k=1	k=2	k=3
City-to-landfill
$A_{r{e}_{11k}}^{\pm }$	[14.58, 19.40]	[16.04, 21.34]	[17.64, 23.48]	$X_{r{e}_{11k}}^{\pm }$	[220, 250]	[240, 280]	[260, 320]
$A_{r{e}_{12k}}^{\pm }$	[12.65, 16.87]	[13.92, 18.56]	[15.31, 20.41]	$X_{r{e}_{12k}}^{\pm }$	[160, 200]	[180, 220]	[220, 260]
$A_{r{e}_{13k}}^{\pm }$	[15.30, 20.49]	[16.83, 22.53]	[18.52, 24.79]	$X_{r{e}_{13k}}^{\pm }$	[160, 200]	[180, 240]	[200, 240]
City-to-WTE
$A_{r{e}_{21k}}^{\pm }$	[11.57, 15.42]	[12.73, 16.97]	[14.00, 18.66]	$X_{r{e}_{21k}}^{\pm }$	[200, 240]	[240, 280]	[280, 320]
$A_{r{e}_{22k}}^{\pm }$	[12.17, 16.15]	[13.39, 17.76]	[14.73, 19.54]	$X_{r{e}_{22k}}^{\pm }$	[120, 170]	[150, 190]	[180, 220]
$A_{r{e}_{23k}}^{\pm }$	[10.60, 14.10]	[11.67, 15.51]	[12.83, 17.06]	$X_{r{e}_{23k}}^{\pm }$	[220, 270]	[220, 270]	[240, 270]
WTE-to-landfill
$A_{r{e}_{WTE-L{F}_k}}^{\pm }$	[5.71, 7.62]	[6.28, 8.38]	[6.91, 9.33]	$X_{r{e}_{WTE-L{F}_k}}^{\pm }$	[170, 200]	[200, 260]	[240, 270]

Table 3.

Fixed unit transportation costs and reference waste flows.

	k=1	k=2	k=3		k=1	k=2	k=3
$C_{r{e}_{11k}}^{-}$	−2.7	−3.4	−3.8	$C_{r{e}_{21k}}^{-}$	−1.9	−2.6	−3.3
$C_{r{e}_{11k}}^{+}$	−4.1	−5.0	−6.3	$C_{r{e}_{21k}}^{+}$	−3.1	−4.0	−5.0
$C_{r{e}_{12k}}^{-}$	−1.7	−2.1	−2.8	$C_{r{e}_{22k}}^{-}$	−1.2	−1.7	−2.2
$C_{r{e}_{12k}}^{+}$	−2.8	−3.4	−4.5	$C_{r{e}_{22k}}^{+}$	−2.3	−2.8	−3.6
$C_{r{e}_{13\text{k}}}^{-}$	−2.1	−2.5	−3.1	$C_{r{e}_{23k}}^{-}$	−2.0	−2.2	−2.6
$C_{r{e}_{13k}}^{+}$	−3.4	−4.5	−5.0	$C_{r{e}_{23k}}^{+}$	−3.2	−3.5	−3.9
$C_{r{e}_{WTE-L{F}_k}}^{-}$	−0.8	−1.1	−1.4	$C_{r{e}_{WTE-L{F}_k}}^{+}$	−1.3	−1.8	−2.1

Table 4.

$C_{re}$($/t) The economy of scale coefficient corresponding to reference waste flow $X_{re}$.

Note: The + and – superscript sign of $C_{re}$represents the value of $C_{re}$relevant to the upper and lower bound of $X_{re}$only.

Hence, it can be observed that the traditional IBA cannot solve this problem without additional assumptions or simplifications. The following discussion will explain how traditional methods solve this problem by simplifying the nonlinear effects of the ES.

1. (i) Let $m=-1$, the effects of the ES are totally ignored. This converts the INLP problem to an ILP problem, and the GAILP method can solve the problem.

2. (ii) Assuming$-0.2<m<-0.1$, it is indicated that the nonlinear relationships in Eq. (26) can be approximated with grey quadratic functions within a predetermined degree of error. Thus, the INLP problem is converted into an IQP problem.

The left two columns of Table 5 list the solutions for $m=-1$and $-0.2<m<-0.1$.

Both of the above simplifications introduce inaccuracy and limitations. When the value of mdeviates away from the predetermined value, this inaccuracy will increase dramatically.

Applying the GAINLP model on the inexact nonlinear programming problem, the optimization problem can be solved directly without additional assumptions for the effects of the ES. Three different scenarios, ($m=-0.1,m=-0.3,\text{and}m=-0.5$) have been tested, and the solutions given by the GAINLP model are shown in the right three columns of Table 5.

The above three scenarios assume that the ES exponent is universal in the whole region during the entire period. However, this is not always necessarily true for practical engineering problems. More common situations may involve different scale exponents for various combinations of municipalities and facilities in different periods. Thus, Table 6 illustrates the solutions for the 4th scenario, which involves different scale exponents.

Decision variable(t/d)	ILP solution	IQP solution	Other solutions
	m=−1	−0.2<m<−0.1	m=−0.1	m=−0.3	m=−0.5
$x_{111}^{\pm }$	[210, 290]	[250, 290]	[203, 292]	[100, 221]	[35, 88]
$x_{112}^{\pm }$	0	[310, 350]	[1, 36]	[1, 44]	[1, 36]
$x_{113}^{\pm }$	[0, 30]	[360, 440]	[1, 44]	[126, 190]	[240, 300]
$x_{121}^{\pm }$	0	[0, 30]	[1, 43]	[60, 141]	[144, 240]
$x_{122}^{\pm }$	[0, 65]	[185, 225]	[1, 73]	[20, 103]	[75, 148]
$x_{123}^{\pm }$	[210, 290]	[50, 80]	[200, 290]	[200, 259]	[197, 260]
$x_{131}^{\pm }$	[0, 30]	0	[1, 37]	[90, 190]	[225, 312]
$x_{132}^{\pm }$	[260, 330]	0	[247, 332]	[189, 270]	[120, 200]
$x_{133}^{\pm }$	[170, 200]	0	[154, 209]	[139, 210]	[143, 192]
$x_{211}^{\pm }$	50	[10, 50]	[35, 58]	[120, 167]	[220, 307]
$x_{212}^{\pm }$	[310, 390]	[0, 40]	[295, 390]	[299, 385]	[295, 390]
$x_{213}^{\pm }$	[360, 410]	0	[329, 426]	[202, 323]	[120, 161]
$x_{221}^{\pm }$	[160, 240]	[160, 210]	[147, 240]	[55, 145]	[1, 30]
$x_{222}^{\pm }$	[185, 200]	[0, 40]	[165, 222]	[142, 200]	[80, 154]
$x_{223}^{\pm }$	0	[160, 210]	[1, 25]	[1, 40]	[1, 43]
$x_{231}^{\pm }$	[260, 310]	[260, 340]	[230, 320]	[122, 164]	[12, 40]
$x_{232}^{\pm }$	[0, 10]	[260, 340]	[1, 28]	[30, 100]	[108, 167]
$x_{233}^{\pm }$	[140, 190]	[310, 390]	[125, 200]	[125, 194]	[120, 214]
$f^{\pm }$= ($\text{\$}{10}^6$)	[220.2, 507.4]	[239.5, 514.1]	[209.8, 522.3]	[200.5, 519.6]	[197.6, 516.8]

Table 5.

Solutions obtained by ILP model (m=−1), IQP model (−0.2 <m<−0.1) and m=−0.1, 0.3 and 0.5.

In the 4th scenario, the weight of the transportation cost in the system operation cost varies according to different $C_t$values. The effect becomes significant when waste flow becomes lower and the hauling distances are substantial. This effect is a nonlinear function of the waste flow $x_{ijk}$, in which the reference waste flow $x_{re}$and the ES exponent mare the parameters. This problem is a complicated nonlinear programming problem, and the GAINLP has been shown to be adequate for solving this kind of problems. On the other hand, the traditional IBA methods will not be able to handle situations like the 4th scenario without additional assumptions and simplification.

Decision variable	Solution (t/d)	m	Decision variable	Solution (t/d)	m
$x_{111}^{\pm }$	[100, 192]	−0.15	$x_{211}^{\pm }$	[125, 189]	−0.1
$x_{112}^{\pm }$	[0, 40]	−0.2	$x_{212}^{\pm }$	[300, 390]	−0.15
$x_{113}^{\pm }$	[112, 178]	−0.35	$x_{213}^{\pm }$	[205, 312]	−0.15
$x_{121}^{\pm }$	[65, 139]	−0.2	$x_{221}^{\pm }$	[42, 142]	−0.45
$x_{122}^{\pm }$	[40, 78]	−0.3	$x_{222}^{\pm }$	[129, 192]	−0.3
$x_{123}^{\pm }$	[199, 279]	−0.3	$x_{223}^{\pm }$	[0, 40]	−0.1
$x_{131}^{\pm }$	[90, 189]	−0.25	$x_{231}^{\pm }$	[100, 198]	−0.3
$x_{132}^{\pm }$	[135, 280]	−0.25	$x_{232}^{\pm }$	[44, 113]	−0.45
$x_{133}^{\pm }$	[127, 218]	−0.3	$x_{233}^{\pm }$	[99, 219]	−0.4
$f^{\pm }$= $[194.7,500.1]$($\text{\$}{10}^6$)

Table 6.

Solutions when mis different for each municipality and each period.

Note: for transportation from WTE facility to landfill, m=−0.5.

Figure 6.

System cost comparisons.

The results also show that when the value of the ES exponent mbecomes smaller, from −0.1, −0.3 to −0.5, for both fpositive scheme and fnegative scheme, the value of the minimized objective function also becomes smaller. At the same time, the range of the intervals of the minimized objective function also decreases. This reflects how the ES exponent affects the overall cost for the entire period. A comparison of the results for the four scenarios is given in Figure 6.

5. Conclusions

In this chapter, the GA-based methods have been proposed and applied for identifying an all-purpose optimization solution for the ILP, IQP and INLP problems. These methods are called GAILP, GAIQP and GAINLP. Compared to these GA-based methods, the traditional problem-solving method has limitations due to the complexity involved in selecting the upper or lower bounds of variables and parameters when the subobjective functions are being constructed. The complexity arises due to the extensive computation and necessary associated assumptions and simplification. The solution procedures of the proposed GA-based optimization methods do not involve any such assumption or simplification, and the quality of the result is guaranteed. The GAINLP was applied to a solid waste management optimization problem, and the result analysis illustrates the practicality and flexibility of the proposed GAINLP method for solving more complex INLP problems.

GAILP, GAIQP and GAINLP have been implemented in MATLAB, and can be easily extended to include other nonlinear operation programming software packages so as to enhance the flexibility and efficiency of the problem-solving process. The GA-based heuristic optimization approach is flexible and it can be extended to find solutions for various types of operation programming scenarios that involve nonlinear optimization and inexact information. It can also be used as an all-purpose algorithm for economic optimizations.

Acknowledgments

The authors gratefully acknowledge the support of the Canada Research Chair program and the Natural Sciences and Engineering Research Council of Canada.