Search

Pareto optimality is the fundamental construct employed to determine whether a given solution to a multi-criteria mathematical optimization model is preferred to another solution. In this paper we describe an approach (Pattern Efficient Set Algorithm – PESA) to generating a pattern-efficient set of non-dominated vectors to a multi-objective optimization problem. Our approach incorporates an optimization model designed to yield certain non-dominated vectors that can fill gaps between already generated non-dominated vectors, providing a way to deal with the adjacency of generated non-dominated vectors and to quantify the gaps between them. We also propose a pseudo-randomized variant of PESA (rPESA) that randomly generates hypothetical bounds for the objective functions and uses them in the optimization model. To test our approach we selected ten problems from the literature, including bi-objective, 3-objective, 5-objective and 10-objective test instances with non-convex, disconnected or continuous Pareto. The inverted generational distance (IGD) and the hyper-volume (HV) are used as performance metrics to measure the quality of the obtained approximations. We also present graphically the numerical results from applying our method.

This study surveys the use of fuzzy numbers in classic optimization models, and its effects on making decisions. In a wide sense, mathematical programming is a collection of tools used in mathematical optimization to make good decisions. There are many sectors of economy that employ it. Finance and government, logistics and manufacturing, the distribution of the electrical power are worth to be first mentioned. When real life problems are modeled mathematically, there is always a trade-off between model’s accuracy and complexity. By this survey, we aim to present in a concise form some mathematical models from the literature together with the methods to solve them. We will focus mainly on fuzzy fractional programming problems. We will also refer to but not describe in detail the multi-criteria decision-making problems involving fuzzy numbers and linear fractional programming models.

The main contribution of this paper is the procedure that constructs a good approximation to the non-dominated set of multiple objective linear fractional programming problem using the solutions to certain linear optimization problems. In our approach we propose a way to generate a discrete set of feasible solutions that are further used as starting points in any procedure for deriving efficient solutions. The efficient solutions are mapped into non-dominated points that form a 0th order approximation of the Pareto front. We report the computational results obtained by solving random generated instances, and show that the approximations obtained by running our procedure are better than those obtained by running other procedures suggested in the recent literature. We evaluated the quality of each approximation using classic metrics.

Optimization problems in the fuzzy environment are widely studied in the literature. We restrict our attention to mathematical programming problems with coefficients and/or decision variables expressed by fuzzy numbers. Since the review of the recent literature on mathematical programming in the fuzzy environment shows that the extension principle is widely present through the fuzzy arithmetic but much less involved in the foundations of the solution concepts, we believe that efforts to rehabilitate the idea of following the extension principle when deriving relevant fuzzy descriptions to optimal solutions are highly needed. This paper identifies the current position and role of the extension principle in solving mathematical programming problems that involve fuzzy numbers in their models, highlighting the indispensability of the extension principle in approaching this class of problems. After presenting the basic ideas in fuzzy optimization, underlying the advantages and disadvantages of different solution approaches, we review the main methodologies yielding solutions that elude the extension principle, and then compare them to those that follow it. We also suggest research directions focusing on using the extension principle in all stages of the optimization process.

In this paper, proposing a mathematical model with disjunctive constraint system, and providing approximate membership function shapes to the optimal values of the decision variables, we improve the solution approach to transportation problems with trapezoidal fuzzy parameters. We further extend the approach to solving transportation problems with intuitionistic fuzzy parameters; and compare the membership function shapes of the fuzzy solutions obtained by our approach to the fuzzy solutions to full fuzzy transportation problems yielded by approaches found in the literature.

We approach the full fuzzy linear programming by grounding the definition of the optimal solution in the extension principle framework. Employing a Monte Carlo simulation, we compare an empirically derived solution to the solutions yielded by approaches proposed in the literature. We also propose a model able to numerically describe the membership function of the fuzzy set of feasible objective values. At the same time, the decreasing (increasing) side of this membership function represents the right (left) side of the membership function of the fuzzy set containing the maximal (minimal) objective values. Our aim is to provide decision-makers with relevant information on the extreme values that the objective function can reach under uncertain given constraints.

A wide variety of solution approaches to linear programming problems in fuzzy environment are proposed in the recent literature. For this study we consider a linear programming problem with fuzzy inequality constraints, and both coefficients and decision variables described by trapezoidal fuzzy numbers. Our solution approach takes into consideration decision maker’s acceptance degree of the violated fuzzy constraints. We use the interval expectation of the trapezoidal fuzzy numbers to transform the original problem into an interval optimization problem. Then, using an order relation to rank the intervals; and handling the acceptance degree of the violated fuzzy constraints as a parameter in the optimization model, we analyze the Pareto optimal solutions to a parametric bi-objective linear programming problem. For a fixed value of the acceptance degree provided by the decision maker, but after a parametric analysis with respect to the parameter used for aggregating the two objectives, the decision maker becomes better informed about the nature of the problem he has to complete. We illustrate our new solution approach using numerical examples found in the literature, and emphasize its advantages.

The aim of this paper is to introduce two crisp linear models to solve fuzzy multiple objective linear fractional programming problems. In a novel manner we construct two piece-wise linear membership functions to describe the fuzzy goal linked to a linear fractional objective. They are related to the numerator and denominator of the fractional objective function; and we show that using the fuzzy-and operator to aggregate them a convenient description of the original fractional fuzzy goal is obtained. Further on, with the help of the fuzzy-and operator we aggregate all fuzzy goals and constraints, formulate a crisp linear model, and use it to provide a solution to the initial fuzzy multiple objective linear fractional programming problem. The second model embeds in distinct ways the positive and negative information, the desires and restrictions respectively; and aggregates in a bipolar manner the goals and constraints. The main advantage of using the new models lies in the fact that they are linear, and can generate distinct solutions to the multiple objective problem by varying the thresholds and tolerance limits imposed on the fuzzy goals.

The class of fuzzy multi-objective linear optimization problems with fuzzy coefficients in the objective functions is addressed in this paper. We introduce a parametric approach that helps to compute the membership values of the extreme points in the fuzzy set solution to such problems. We analyze the efficiency of the feasible basic solutions to a parametric multi-objective linear programming problem through the optimality test in a related linear programming problem. The particular case of triangular fuzzy numbers is presented in detail, and the possible degeneracy of the basic feasible solutions is handled. This paper is a continuation of our work on special classes of fuzzy optimization problems. Previously single-objective (linear and linear fractional) optimization problems with fuzzy coefficients in the objective functions were successfully solved.

The class of fuzzy linear fractional optimization problems with fuzzy coefficients in the objective function is considered in this paper. We propose a parametric method for computing the membership values of the extreme points in the fuzzy set solution to such problems. We replace the exhaustive computation of the membership values--found in the literature for solving the same class of problems--by a parametric analysis of the efficiency of the feasible basic solutions to the bi-objective linear fractional programming problem through the optimality test in a related linear programming problem, thus simplifying the computation. An illustrative example from the field of production planning is included in the paper to complete the theoretical presentation of the solving approach, but also to emphasize how many real life problems may be modelled mathematically using fuzzy linear fractional optimization.

5G networks, as an emerging technology, calls for novel solutions to several research problems, many of them having in focus a better usage of sparse spectrum capacity. In the attempt to leverage spectrum, additional unlicensed band, available for wireless technology, is combined with the licensed part of the spectrum, managed by traditional mobile providers, thus making a heterogeneous network environment of Primary Networks (PNs). In such an environment desirous users (i.e. Secondary Users (SU)) equipped with multiple radio access technology are able to select the appropriate network considering not just interference, but other parameters as well (e.g. QoS, data rates, prices etc.). We consider the architecture with central Cognitive Network Provider (CNP) and several heterogeneous PNs, in which SUs are contending for empty channels in one of the PNs that best suit their needs for bandwidth, data rate and price. Applying cognitive radio network principles leads to the well-known problem of Network Selection and Channel Allocation. CNP has to solve this NP-hard problem by considering equally the demands of the heterogeneous PNs as well as the best interest of SUs. In this paper we propose two different bi-objective models and solve them by generating their non-dominated points. First model allocates SUs to networks with respect to costs, target interferences, and data rate capacities; while the second model splits PNs in channels, and allocates SUs to channels with respect to their additional demands for low latency. We generate the efficient sets of the instances found in the literature; and compare our results with the existing results obtained by the nature inspired meta-heuristic approaches.

In 1994, Chanas and Kuchta suggested one approach to determine the membership function of a fuzzy solution to the fuzzy linear optimization problem with fuzzy coefficients in the objective function, based on computing the sum of lengths of certain intervals. In 2012, Dempe and Ruziyeva introduced a methodology for realizing Chanas and Kuchta's idea, and derived explicit formulas for computing the endpoints of the suggested intervals in the particular case of triangular fuzzy numbers. The purpose of this paper is to extend Dempe and Ruziyeva's approach by handling the possible degeneracy of basic feasible solutions, and derive new formulas for computing the values of the membership function. The special example considered by Dempe and Ruziyeva is again used to illustrate the relevance of the extended solving procedure and new formulas.

Chakraborty and Gupta, in their paper “Fuzzy mathematical programming for multi objective linear fractional programming problem”, published in Fuzzy Sets and Systems 125 (2002), claimed that their methodology proposed for solving multi objective linear fractional programming problem always yields an efficient solution. This paper indicates that their claim is generally wrong and this is due to the non-equivalence of the original problem and the associated linear problem.

The Service Oriented Approach (SOA) is based on the idea that distributed applications can be flexibly composed by integrating independently developed component services. Due to the fact that a large number of available services offer similar functionality, when choosing actual services to be included in the composition their non-functional (Quality of Service – QoS) properties must also be taken into account. On the other hand certain constraints regarding the required performances (i.e. the required QoS levels) may also be given. Therefore, web service selection presents a multiple-objective multiple constraint problem and in this paper we model it as a discrete multiple-objective linear fractional programming (MOLFP) problem. In order to solve this problem we use a previously published technique for generating strongly efficient solutions to a continuous MOLFP problem to the discrete case. We present a complete methodology for solving the multiple criteria web service selection problem and report the experimental results obtained by testing it on 50 random instances generated by varying the input parameters.

Toksari, in his paper ‘Taylor series approach to fuzzy multiobjective linear fractional programming’, published in Information Sciences 178 (2008), proposed a new method to solve multiple objective linear fractional programming problems and declared that it is more effective when compare to previous methods. He constructed fuzzy goals and then used first order Taylor-polynomials to approximate the corresponding linear fractional membership functions by linear functions. Aggregating the linear functions Toksari obtained a crisp linear programming problem and claimed that it is ‘equal’ to the fuzzy fractional one. In this paper, we indicate the fallacy that arises by using Taylor approximation and propose an improved method that guarantees the efficiency of the solution it provides. Both practical applications from Toksari’s paper are recalled to show that the improvements we suggest are effective.

The vehicle routing problem (VRP) is one of the most explored combinatorial problems in operations research. A very fast and simple algorithm that solves the VRP is the well known Clarke-Wright savings algorithm. In this paper we introduce a new way of merging routes and the corresponding formula for calculating savings. We also apply the enhanced merging to develop a new heuristic - Extended Savings Algorithm (ESA) that dynamically recalculates savings during iterations. Computational results show that, on average ESA gives better solutions than the original savings algorithm. Implementing randomization of some steps of our heuristic we obtained even better results which competes with more complex and well known heuristics. The ESA is further used to generate good routes as part of a set-covering-based algorithm for the Capacitated VRP (CVRP). The numerical results of our experiments are reported.

The solution concept in multi-objective programming is represented by a program which reaches “the best compromise”. Many solving methods find a good compromise feasible solution and then check whether the solution is efficient or not. In this paper, using the efficiency test introduced by Lotfi et al. (2010) [12] , we propose two procedures for deriving weakly and strongly efficient solutions in multi-objective linear fractional programming problems (MOLFPP) starting from any feasible solution, and present their possible applications in multiple criteria decision-making process. Then, we discuss a shortcoming of some fuzzy approaches to solving MOLFPP and modify them in order to guarantee the efficiency of the optimal solution.

In this paper we formulate and prove two upper bounds for the nondominated set of multi-objective combinatorial optimization problems with integer coefficients. We also show that under certain assumptions, reasonable and applicable in the majority of practical problems, the number of nondominated points grows following a polynomial function.

Multimodal biometric verification systems use information from several biometric modalities to verify an identity of a person. The false acceptance rate (FAR) and false rejection rate (FRR) are metrics generally used to measure the performance of such systems. In this paper we propose a novel approach to determine the upper and lower acceptance thresholds in sequential multimodal biometric matching, in such a way that the expected values of FAR and FRR for the entire system are minimized. We linearize locally the score distributions of both genuine users and impostors using the least squares method, and derive formulas for the approximated FAR and FRR for each matcher. Further, we aim to minimize both probabilities for entire processing chain. In order to find the best compromise between them, we analyze the efficient solutions to the associated bi-objective programming problem. The results of our experiments are also reported in the paper. They showed a good performance of the sequential multiple biometric matching system based on optimized thresholds comparing with the widely adopted parallel fusion multimodal biometric systems.

In this paper we shall propose an algorithm for solving fuzzy linear programming problems with trapezoidal numbers using a penalty method. We will transform the problem of maximizing a function having trapezoidal fuzzy number values under some constraints into a deterministic multi-objective programming problem by penalizing the objective function for possible constraint violation. Furthermore, the obtained deterministic problem will have only unavoidable inequalities between trapezoidal fuzzy numbers parameters as constraints.

Transportation is widely present in human activities and supports many economic activities. Using phones, reading mails, traveling, and flying involve the routing of messages, people, and goods. One of the present aims of research is to fill the gap between academic research and practical applications. Our aim is to present a simple and flexible heuristic for solving the capacitated vehicle routing problem and heterogeneous fleet vehicle routing problems, and discuss its advantages compared to other well-known heuristics. The flexibility of our approach comes from the simplicity of the solution procedure and is especially important when the algorithm is going to be applied to solving real-life problems.

In our earlier articles, we proposed two methods for solving the fully fuzzified linear fractional programming (FFLFP) problems. In this paper, we introduce a different approach of evaluating fuzzy inequalities between two triangular fuzzy numbers and solving FFLFP problems. First, using the Charnes-Cooper method, we transform the linear fractional programming problem into a linear one. Second, the problem of maximizing a function with triangular fuzzy value is transformed into a problem of deterministic multiple objective linear programming. Illustrative numerical examples are given to clarify the developed theory and the proposed algorithm.

The number of efficient points in criteria space of multiple objective combinatorial optimization problems is considered in this paper. It is concluded that under certain assumptions, that number grows polynomially although the number of Pareto optimal solutions grows exponentially with the problem size. In order to perform experiments, an original algorithm for obtaining all efficient points was formulated and implemented for three classical multiobjective combinatorial optimization problems. Experimental results with the shortest path problem, the Steiner tree problem on graphs and the traveling salesman problem show that the number of efficient points is much lower than a polynomial upper bound.

The importance of linear fractional programming comes from the fact that many real life problems are based on the ratio of physical or economic values (for example cost/-time, cost/volume, profit/cost or any other quantities that measure the efficiency of a system) expressed by linear functions. Usually, the coefficients used in mathematical models are subject to errors of measurement or vary with market conditions. Dealing with inaccuracy or uncertainty of the input data is made possible by means of the fuzzy set theory. Our purpose is to introduce a method of solving a linear fractional programming problem with uncertain coefficients in the objective function. We have applied recent concepts of fuzzy solution based on α-cuts and Pareto optimal solutions of a biobjective optimization problem. As far as solving methods are concerned, the linear fractional programming, as an extension of linear programming, is easy enough to be handled by means of linear programming but complicated enough to elude a simple analogy. We follow the construction of the fuzzy solution for the linear case introduced by Dempe and Ruziyeva (2012), avoid the inconvenience of the classic weighted sum method for determining Pareto optimal solutions and generate the set of solutions for a linear fractional program with fuzzy coefficients in the objective function.

Multi-modal biometric verification systems use information from several biometric modalities to verify an identity of a person. The false acceptance rate (FAR)and false rejection rate (FRR) are metrics generally used to measure the performance of such systems.In this paper, we first approximate the score distributions of both genuine users and impostors by continuous distributions. Then we incorporate the exact expressions of the distributions in the formulas for the expected values of both FAR and FRR for each matcher. In order to determine the upper and lower acceptance thresholds in the sequential multi-modal biometric matching, we further minimize the expected values of FAR and FRR for the entire processing chain. We propose a non-linear bi-objective programming problem whose objective functions are the two error probabilities. We analyze the efficient set of the bi-objective problem, and derive an efficient solution as a best compromise between the error probabilities. Replacing the least squares approximation of the score distributions by a continuous distributionapproximation, this approach modifies the method presented in Stanojević et al. [15] (doi: 10.1109/ICCCC.2016.7496752) (a).The results of our experiments showed a good performance of the sequential multiple biometric matching system based on continuous distribution approximation and optimized thresholds.(a)Reprinted (partial) and extended, with permission based on License Number3938230385072 © [2016] IEEE, from "Computers Communications and Control (ICCCC), 2016 6th International Conference on".