A fuzzy multidimensional multiple-choice knapsack model for project portfolio selection using an evolutionary algorithm

Project portfolio selection problems are inherently complex problems with multiple and often conflicting objectives. Numerous analytical techniques ranging from simple weighted scoring to complex mathematical programming approaches have been proposed to solve these problems with precise data. However, the project data in real-world problems are often imprecise or ambiguous. We propose a fuzzy Multidimensional Multiple-choice Knapsack Problem (MMKP) formulation for project portfolio selection. The proposed model is composed of an Efficient Epsilon-Constraint (EEC) method and a customized multi-objective evolutionary algorithm. A Data Envelopment Analysis (DEA) model is used to prune the generated solutions into a limited and manageable set of implementable alternatives. Statistical analysis is performed to investigate the effectiveness of the proposed approach in comparison with the competing methods in the literature. A case study is presented to demonstrate the applicability of the proposed model and exhibit the efficacy of the procedures and algorithms.     

A branch-and-bound algorithm for hard multiple knapsack problems

The multiple knapsack problem (MKP) is a classical combinatorial optimization problem. A recent algorithm for some classes of the MKP is bin-completion, a bin-oriented, branch-and-bound algorithm. In this paper, we propose path-symmetry and path-dominance criteria for pruning nodes in the MKP branch-and-bound search space. In addition, we integrate the ??bound-and-bound?? upper bound validation technique used in previous MKP solvers. We show experimentally that our new MKP solver, which successfully integrates dominance based pruning, symmetry breaking, and bound-and-bound, significantly outperforms previous solvers on some classes of hard problem instances.     

A fuzzy approach to R&D project portfolio selection

A major advance in the development of project selection tools came with the application of options reasoning in the field of Research and Development (R&D). The options approach to project evaluation seeks to correct the deficiencies of traditional methods of valuation through the recognition that managerial flexibility can bring significant value to projects. Our main concern is how to deal with non-statistical imprecision we encounter when judging or estimating future cash flows. In this paper, we develop a methodology for valuing options on R&D projects, when future cash flows are estimated by trapezoidal fuzzy numbers. In particular, we present a fuzzy mixed integer programming model for the R&D optimal portfolio selection problem, and discuss how our methodology can be used to build decision support tools for optimal R&D project selection in a corporate environment.     

Using fuzzy numbers in knapsack problems

This paper investigates knapsack problems in which all of the weight coefficients are fuzzy numbers. This work is based on the assumption that each weight coefficient is imprecise due to the use of decimal truncation or rough estimation of the coefficients by the decision-maker. To deal with this kind of imprecise data, fuzzy sets provide a powerful tool to model and solve this problem. Our work intends to extend the original knapsack problem into a more generalized problem that would be useful in practical situations. As a result, our study shows that the fuzzy knapsack problem is an extension of the crisp knapsack problem, and that the crisp knapsack problem is a special case of the fuzzy knapsack problem.     

Viability of infeasible portfolio selection problems: A fuzzy approach

This paper deals with fuzzy optimization schemes for managing a portfolio in the framework of risk–return trade-off. Different models coexist to select the best portfolio according to their respective objective functions and many of them are linearly constrained. We are concerned with the infeasible instances of such models. This infeasibility, usually provoked by the conflict between the desired return and the diversification requirements proposed by the investor, can be satisfactorily avoided by using fuzzy linear programming techniques. We propose an algorithm to repair infeasibility and we illustrate its performance on a numerical example.     

A multi-objective genetic algorithm for cardinality constrained fuzzy portfolio selection

This paper presents a new procedure that extends genetic algorithms from their traditional domain of optimization to fuzzy ranking strategy for selecting efficient portfolios of restricted cardinality. The uncertainty of the returns on a given portfolio is modeled using fuzzy quantities and a downside risk function is used to describe the investor's aversion to risk. The fitness functions are based both on the value and the ambiguity of the trapezoidal fuzzy number which represents the uncertainty on the return. The soft-computing approach allows us to consider uncertainty and vagueness in databases and also to incorporate subjective characteristics into the portfolio selection problem. We use a data set from the Spanish stock market to illustrate the performance of our approach to the portfolio selection problem.     

Considering decision decentralizations to solve bi-level multi-objective decision-making problems: A fuzzy approach

This paper investigates decentralized bi-level multi-objective linear programming (DBL-MOLP) problems with a single decision-maker (DM) at the higher level and more than one DM at the lower level. Each DM can have more than one objective function, which is formulated as a fuzzy goal. To characterize the decision decentralization in a DBL-MOLP problem, this paper proposes an assignment scheme of relative satisfaction for the higher-level DM to ensure his leadership and therefore prevent the paradox problem reported in the literature, where lower-level DMs have higher satisfaction degrees than that of the higher-level DM. Through the assignment scheme, if the higher-level DM is not satisfied with the resulting solutions of objective functions, the re-solving process is easily conducted by adjusting the level of relative satisfaction for the associated lower-level DMs. A linearization transformation approach is also presented to facilitate the solution process. To emphasize some important fuzzy goals, a weighting scheme is considered in this paper. A numerical example is used for illustration, and comparisons with existing approaches are conducted to demonstrate the feasibility of the proposed method.     

Solving multi-level multi-objective linear programming problems through fuzzy goal programming approach

In this paper, two new algorithms are presented to solve multi-level multi-objective linear programming (ML-MOLP) problems through the fuzzy goal programming (FGP) approach. The membership functions for the defined fuzzy goals of all objective functions at all levels are developed in the model formulation of the problem; so also are the membership functions for vectors of fuzzy goals of the decision variables, controlled by decision makers at the top levels. Then the fuzzy goal programming approach is used to achieve the highest degree of each of the membership goals by minimizing their deviational variables and thereby obtain the most satisfactory solution for all decision makers.     

An exact algorithm for large multiple knapsack problems

The Multiple Knapsack Problem (MKP) is the problem of assigning a subset of n items to m distinct knapsacks, such that the total profit sum of the selected items is maximized, without exceeding the capacity of each of the knapsacks. The problem has several applications in naval as well as financial management. A new exact algorithm for the MKP is presented, which is specially designed for solving large problem instances. The recursive branch-and-bound algorithm applies surrogate relaxation for deriving upper bounds, while lower bounds are obtained by splitting the surrogate solution into the m knapsacks by solving a series of Subset-sum Problems. A new separable dynamic programming algorithm is presented for the solution of Subset-sum Problems, and we also use this algorithm for tightening the capacity constraints in order to obtain better upper bounds. The developed algorithm is compared to the mtm algorithm by Martello and Toth, showing the benefits of the new approach. A surprising result is that large instances with n=100 000 items may be solved in less than a second, and the algorithm has a stable performance even for instances with coefficients in a moderately large range.     

A fuzzy MCDM approach for stock selection

A fuzzy MCDM approach is applied to the stock selection problem, where the proposed approach can deal with qualitative information in addition to quantitative information. A hierarchy of major–sub criteria is then established to reduce the dependence between criteria. The ratings of alternatives versus qualitative sub-criteria and the weights of major- and sub-criteria are assessed in linguistic terms represented by fuzzy numbers. Each sub-criterion is in a benefit, cost, or balanced nature. New standardization methods for fuzzy numbers in the cost and balanced nature are presented. The algorithms of membership functions of the final aggregation are completely developed instead of approximation. The final aggregations in fuzzy numbers are then defuzzified to crisp values in order to rank the performance of alternatives. Moreover, the ratio of market price to performance (PP) is suggested to filter the over/under-pricing of alternatives. A set of buying/selling strategies are recommended according to the performance and PP. An empirical example then demonstrates the processing of the proposed approach.     

A novel two-phase group decision making approach for construction project selection in a fuzzy environment

This paper considers a construction project problem under multiple criteria in a fuzzy environment and proposes a new two-phase group decision making (GDM) approach. This approach integrates a modified analytic network process (ANP) and an improved compromise ranking method, known as VIKOR. To take uncertainty and risk into account, a new decision making approach is presented with multiple fuzzy information by a group of experts, and a risk attitude for each expert is incorporated that can be expressed linguistically. First, a modified fuzzy ANP method is introduced to address the problem of dependence as well as feedback among conflicting criteria and to determine their relative importance. Then, a fuzzy VIKOR method is extended to rank potential projects on the basis of their overall performance. An illustrative example from the literature is provided for the construction project problem to demonstrate the effectiveness and feasibility of the proposed approach. The computational results show that the proposed two-phase GDM approach is suitable to cope with imprecision and subjectivity for the complicated decision making problem. Finally, the associated results of the proposed approach with risk attitudes and without risk attitudes are compared with the results reported by Cheng and Li [1], and the merits are highlighted.     

A parallel multiple reference point approach for multi-objective optimization

This paper presents a multiple reference point approach for multi-objective optimization problems of discrete and combinatorial nature. When approximating the Pareto Frontier, multiple reference points can be used instead of traditional techniques. These multiple reference points can easily be implemented in a parallel algorithmic framework. The reference points can be uniformly distributed within a region that covers the Pareto Frontier. An evolutionary algorithm is based on an achievement scalarizing function that does not impose any restrictions with respect to the location of the reference points in the objective space. Computational experiments are performed on a bi-objective flow-shop scheduling problem. Results, quality measures as well as a statistical analysis are reported in the paper.     

A QFD-based fuzzy MCDM approach for supplier selection

Supplier selection is a highly important multi-criteria group decision making problem, which requires a trade-off between multiple criteria exhibiting vagueness and imprecision with the involvement of a group of experts. In this paper, a fuzzy multi-criteria group decision making approach that makes use of the quality function deployment (QFD) concept is developed for supplier selection process. The proposed methodology initially identifies the features that the purchased product should possess in order to satisfy the company’s needs, and then it seeks to establish the relevant supplier assessment criteria. Moreover, the proposed algorithm enables to consider the impacts of inner dependence among supplier assessment criteria. The upper and the lower bounds of the weights of supplier assessment criteria and ratings of suppliers are computed by using the fuzzy weighted average (FWA) method. The FWA method allows for the fusion of imprecise and subjective information expressed as linguistic variables or fuzzy numbers. The method produces less imprecise and more realistic overall desirability levels, and thus it rectifies the problem of loss of information. A fuzzy number ranking method that is based on area measurement is used to obtain the final ranking of suppliers. The computational procedure of the proposed framework is illustrated through a supplier selection problem reported in an earlier study.     

An efficient multi-objective evolutionary fuzzy system for regression problems

During the last years, multi-objective evolutionary algorithms (MOEAs) have been extensively employed as optimization tools for generating fuzzy rule-based systems (FRBSs) with different trade-offs between accuracy and interpretability from data. Since the size of the search space and the computational cost of the fitness evaluation depend on the number of input variables and instances, respectively, managing high-dimensional and large datasets is a critical issue.In this paper, we focus on MOEAs applied to learn concurrently the rule base and the data base of Mamdani FRBSs and propose to tackle the issue by exploiting the synergy between two different techniques. The first technique is based on a novel method which reduces the search space by learning rules not from scratch, but rather from a heuristically generated rule base. The second technique performs an instance selection by exploiting a co-evolutionary approach where cyclically a genetic algorithm evolves a reduced training set which is used in the evolution of the MOEA.The effectiveness of the synergy has been tested on twelve datasets. Using non-parametric statistical tests we show that, although achieving statistically equivalent solutions, the adoption of this synergy allows saving up to 97.38% of the execution time with respect to a state-of-the-art multi-objective evolutionary approach which learns rules from scratch.     

A new method for solving linear multi-objective transportation problems with fuzzy parameters

There are several methods in the literature for solving transportation problems by representing the parameters as normal fuzzy numbers. Chiang [J. Chiang, The optimal solution of the transportation problem with fuzzy demand and fuzzy product, J. Inform. Sci. Eng. 21 (2005) 439-451] pointed out that it is better to represent the parameters as (λ, ρ) interval-valued fuzzy numbers instead of normal fuzzy numbers and proposed a method to find the optimal solution of single objective transportation problems by representing the availability and demand as (λ, ρ) interval-valued fuzzy numbers. In this paper, the shortcomings of the existing method are pointed out and to overcome these shortcomings, a new method is proposed to find solution of a linear multi-objective transportation problem by representing all the parameters as (λ, ρ) interval-valued fuzzy numbers. To illustrate the proposed method a numerical example is solved. The advantages of the proposed method over existing method are also discussed.     

A redundancy detection algorithm for fuzzy stochastic multi-objective linear fractional programming problems

The computational complexity of linear and nonlinear programming problems depends on the number of objective functions and constraints involved and solving a large problem often becomes a difficult task. Redundancy detection and elimination provides a suitable tool for reducing this complexity and simplifying a linear or nonlinear programming problem while maintaining the essential properties of the original system. Although a large number of redundancy detection methods have been proposed to simplify linear and nonlinear stochastic programming problems, very little research has been developed for fuzzy stochastic (FS) fractional programming problems. We propose an algorithm that allows to simultaneously detect both redundant objective function(s) and redundant constraint(s) in FS multi-objective linear fractional programming problems. More precisely, our algorithm reduces the number of linear fuzzy fractional objective functions by transforming them in probabilistic–possibilistic constraints characterized by predetermined confidence levels. We present two numerical examples to demonstrate the applicability of the proposed algorithm and exhibit its efficacy.     

A new approach to find project characteristics and multiple possible critical paths in a fuzzy project network

Graphs are widely used to represent data and relationships. Among all graphs, a particularly useful family is the family of trees. In this paper, we utilize a rooted tree to describe a fuzzy project network as it enables simplification in finding earliest starting times and trapezoidal fuzzy numbers to express the operation times for all activities in project network. As there is an increasing demand that the decision maker needs “Multiple possible critical paths” to decrease the decision risk for project management, in this paper, we introduce an effective graphical method to compute project characteristics such as total float, earliest and latest times of activities in fuzzy project network and a new ranking to find possible critical paths. Numerical example is provided to explain the proposed procedure in detail; the results have shown that the procedure is very useful and flexible in finding total floats. By comparing the critical paths obtained by this method with the previous methods, it is shown that the proposed method is effective in finding possible critical paths.     

Optimal project selection: Stochastic knapsack with finite time horizon

A time-constrained capital-budgeting problem arises when projects, which can contribute to achieving a desired target state before a specified deadline, arrive sequentially. We model such problems by treating projects as randomly arriving requests, each with a funding cost, a proposed benefit, and a known probability of success. The problem is to allocate a non-renewable initial budget to projects over time so as to maximise the expected benefit obtained by a certain time, T, called the deadline, where T can be either a constant or a random variable. Each project must be accepted or rejected as soon as it arrives. We developed a stochastic dynamic programming formulation and solution of this problem, showing that the optimal strategy is to dynamically determine ‘acceptance intervals’ such that a project of type i is accepted when, and only when, it arrives during an acceptance interval for projects of type i.     

Resolution approach for multi-objective problems with uncertain demands

The job-shop scheduling problem (JSP) is one of the hardest problems (NP-complete problem). In a lot of cases, the combination of goals and resource exponentially increases search space. The objective of resolution of such a problem is generally, to maximize the production with a lower cost and makespan. In this paper, we explain how to modify the objective function of genetic algorithms to treat the multi-objective problem and to generate a set of diversified “optimal” solutions in order to help decision maker. We are interested in one of the problems occurring in the production workshops where the list of demands is split into firm (certain) jobs and predicted jobs. One wishes to maximize the produced quantity, while minimizing as well as possible the makespan and the production costs. Genetic algorithms are used to find the scheduling solution of the firm jobs because they are well adapted to the treatment of the multi-objective optimization problems. The predicted jobs will be inserted in the real solutions (given by genetic algorithms). The solutions proposed by our approach are compared to the lower bound of the cost and makespan in order to prove the quality and robustness of our proposed approach.     

A geometric approach for solving fuzzy linear programming problems

In this paper we first recall some definitions and results of fuzzy plane geometry, and then introduce some definitions in the geometry of two-dimensional fuzzy linear programming (FLP). After defining the optimal solution based on these definitions, we use the geometric approach for obtaining optimal solution(s) and show that the algebraic solutions obtained by Zimmermann method (ZM) and our geometric solutions are the same. Finally, numerical examples are solved by these two methods.