A general decomposition approach for multi-criteria decision trees

In this paper, we address the dynamic and multi-criteria decision-making problems under uncertainty, generally represented by multi-criteria decision trees. Decision-making consists of choosing, at each period, a decision that maximizes the decision-maker outcomes. These outcomes should often be measured against a set of heterogeneous and conflicting criteria. Generating the set of non-dominated solutions is a common approach considered in the literature to solve the multi-criteria decision trees, but it becomes very challenging for large problems. We propose a new approach to solve multi-criteria decision trees without generating the set of all non-dominated solutions, which should reduce the computation time and the cardinality of the solution set. In particular, the proposed approach combines the advantages of decomposition with the application of multi-criteria decision aid (MCDA) methods at each decision node. A generalization of the Bellman’s principle of decomposition to the multi-criteria context is put forward. A decomposition theorem is therefore proposed. Under the sufficient conditions stated by the theorem, the principle of decomposition will generate the set of best compromise strategies. Seven MCDA methods are then characterized (lexicographic, weighted sum, multi-attribute value theory, TOPSIS, ELECTRE III, and PROMETHEE II) against the conditions of the theorem of decomposition and against other properties (neutrality, anonymous, fidelity, dominance, independency), in order to confirm or infirm their applicability with the proposed decomposition principle. Moreover, the relationship between independency and temporal consistence is discussed as well as the effects of incomparableness, rank reversals, and use of thresholds. Two conjectures resulted from this characterization.     

A novel approach to interval-valued intuitionistic fuzzy soft set based decision making

The soft set theory, originally proposed by Molodtsov, can be used as a general mathematical tool for dealing with uncertainty. The interval-valued intuitionistic fuzzy soft set is a combination of an interval-valued intuitionistic fuzzy set and a soft set. The aim of this paper is to investigate the decision making based on interval-valued intuitionistic fuzzy soft sets. By means of level soft sets, we develop an adjustable approach to interval-valued intuitionistic fuzzy soft sets based decision making and some numerical examples are provided to illustrate the developed approach. Furthermore, we also define the concept of the weighted interval-valued intuitionistic fuzzy soft set and apply it to decision making.     

Fuzzy decision trees

We propose here to extend the decision trees method to the case when the involved data (probabilities, cost, profits, losses) appear as words belonging to the common language whose semantic representations are fuzzy sets. First we discuss the reasons why such an extension is to be aimed at. Then in the fuzzy case we carry out a reformalization of the basic concepts of probability and utility theory. Finally we show how these reformalized concepts can be applied to fuzzy decision trees.     

A data envelopment approach to decision analysis

A decision aid to assist the development of a linear valuation function for multiple attribute problems is proposed, based on a linear programming formulation using a constraint set structured in a similar manner to data envelopment analysis (DEA). Value functions which favour each decision option are calculated, and efficient, potentially optimal, options identified. These are used to help a decision maker progressively to articulate preferences, indicators of his/her values, in an interactive, structurally flexible manner. As preference indications are provided, candidate value functions and hitherto efficient options inconsistent with his/her declarations are eliminated, thus proceeding towards an explicit value function and, if needed a corresponding complete option order.     

A convex analytic approach to Markov decision processes

Summary This paper develops a new framework for the study of Markov decision processes in which the control problem is viewed as an optimization problem on the set of canonically induced measures on the trajectory space of the joint state and control process. This set is shown to be compact convex. One then associates with each of the usual cost criteria (infinite horizon discounted cost, finite horizon, control up to an exit time) a naturally defined occupation measure such that the cost is an integral of some function with respect to this measure. These measures are shown to form a compact convex set whose extreme points are characterized. Classical results about existence of optimal strategies are recovered from this and several applications to multicriteria and constrained optimization problems are briefly indicated.Research supported by NSF Grant CDR-85-00108     

Incorporating stochastic processes to overcome unmanageable decision trees

Many decision problems, when approached by decision analysis in practice, have the property that a full, accurate and realistic decision tree mushrooms into unmanageable proportions. A pruning process undertaken to overcome enormous trees handles excessive width of the tree. This paper outlines an idea for managing the depth of decision trees by partitioning the time horizon into a short and long term. A decision tree of reasonable depth covers the short term, and events that can occur over extended periods of time are represented by a Markov process. Generalization of this idea is possible if another type of a stochastic process is applicable. With the proliferation of end user computing, software support for the idea is now available.     

A fuzzy closeness approach to fuzzy multi-attribute decision making

The aim of this paper is to develop a new fuzzy closeness (FC) methodology for multi-attribute decision making (MADM) in fuzzy environments, which is an important research field in decision science and operations research. The TOPSIS method based on an aggregating function representing “closeness to the ideal solution” is one of the well-known MADM methods. However, while the highest ranked alternative by the TOPSIS method is the best in terms of its ranking index, this does not mean that it is always the closest to the ideal solution. Furthermore, the TOPSIS method presumes crisp data while fuzziness is inherent in decision data and decision making processes, so that fuzzy ratings using linguistic variables are better suited for assessing decision alternatives. In this paper, a new FC method for MADM under fuzzy environments is developed by introducing a multi-attribute ranking index based on the particular measure of closeness to the ideal solution, which is developed from the fuzzy weighted Minkowski distance used as an aggregating function in a compromise programming method. The FC method of compromise ranking determines a compromise solution, providing a maximum “group utility” for the “majority” and a minimum individual regret for the “opponent”. A real example of a personnel selection problem is examined to demonstrate the implementation process of the method proposed in this paper.     

A cutting plane approach to capacitated lot-sizing with start-up costs

We consider a mixed integer model for multi-item single machine production planning, incorporating both start-up costs and machine capacity. The single-item version of this model is studied from the polyhedral point of view and several families of valid inequalities are derived. For some of these inequalities, we give necessary and sufficient facet inducing conditions, and efficient separation algorithms. We use these inequalities in a cutting plane/branch and bound procedure. A set of real life based problems with 5 items and up to 36 periods is solved to optimality.     

A new genetic approach to construct near-optimal binary search trees

Many definitive and approximate methods have been so far proposed for the construction of an optimal binary search tree. One such method is the use of evolutionary algorithms with satisfactorily improved cost efficiencies. This paper will propose a new genetic algorithm for making a near-optimal binary search tree. In this algorithm, a new greedy method is used for the crossover of chromosomes while a new way is also developed for inducing mutation in them. Practical results show a rapid and desirable convergence towards the near-optimal solution. The use of a heuristic to create not so costly chromosomes as the first offspring, the greediness of the crossover, and the application of elitism in the selection of future generation chromosomes are the most important factors leading to near-optimal solutions by the algorithm at desirably high speeds. Due to the practical results, increasing problem size does not cause any considerable difference between the solution obtained from the algorithm and exact solution.     

Fringe analysis of plane trees related to cutting and pruning

Rooted plane trees are reduced by four different operations on the fringe. The number of surviving nodes after reducing the tree repeatedly for a fixed number of times is asymptotically analyzed. The four different operations include cutting all or only the leftmost leaves or maximal paths. This generalizes the concept of pruning a tree. The results include exact expressions and asymptotic expansions for the expected value and the variance as well as central limit theorems.     

One approach to constructing cutting algorithms with dropping of cutting planes

We propose a general cutting method for conditional minimization of continuous functions. We calculate iteration points by partially embeddimg the admissible set in approximating polyhedral sets. We describe the features of the proposed method and prove its convergence. The constructed general method does not imply the inclusion of each of approximating sets in the previous one. This feature allows us to construct cutting algorithms which periodically drop any additional restrictions which occur in the solution process.     

A novel approach to multi attribute group decision making based on trapezoidal interval type-2 fuzzy soft sets

Soft set theory, originally proposed by Molodtsov, has become an effective mathematical tool to deal with uncertainty. A type-2 fuzzy set, which is characterized by a fuzzy membership function, can provide us with more degrees of freedom to represent the uncertainty and the vagueness of the real world. Interval type-2 fuzzy sets are the most widely used type-2 fuzzy sets. In this paper, we first introduce the concept of trapezoidal interval type-2 fuzzy numbers and present some arithmetic operations between them. As a special case of interval type-2 fuzzy sets, trapezoidal interval type-2 fuzzy numbers can express linguistic assessments by transforming them into numerical variables objectively. Then, by combining trapezoidal interval type-2 fuzzy sets with soft sets, we propose the notion of trapezoidal interval type-2 fuzzy soft sets. Furthermore, some operations on trapezoidal interval type-2 fuzzy soft sets are defined and their properties are investigated. Finally, by using trapezoidal interval type-2 fuzzy soft sets, we propose a novel approach to multi attribute group decision making under interval type-2 fuzzy environment. A numerical example is given to illustrate the feasibility and effectiveness of the proposed method.     

A novel approach to Bilevel nonlinear programming

Recently developed methods of monotonic optimization have been applied successfully for studying a wide class of nonconvex optimization problems, that includes, among others, generalized polynomial programming, generalized multiplicative and fractional programming, discrete programming, optimization over the efficient set, complementarity problems. In the present paper the monotonic approach is extended to the General Bilevel Programming GBP Problem. It is shown that (GBP) can be transformed into a monotonic optimization problem which can then be solved by “polyblock” approximation or, more efficiently, by a branch-reduce-and-bound method using monotonicity cuts. The method is particularly suitable for Bilevel Convex Programming and Bilevel Linear Programming.      

A fast heuristic attribute reduction approach to ordered decision systems

Rough set theory has shown success in being a filter-based feature selection approach for analyzing information systems. One of its main aims is to search for a feature subset called a reduct, which preserves the classification ability of the original system. In this paper, we consider ordered decision systems, where the preference order, a fundamental concept in dominance-based rough set approach, plays a critical role. In recent literature, based on the greedy hill climbing method, many heuristic attribute reduction algorithms are proposed by utilizing significance measures of attributes, and they are extended to deal with ordered decision systems. Unfortunately, they are often time-consuming, especially when applied to deal with large scale data sets with high dimensions. To reduce the complexity, a novel accelerator is introduced in heuristic algorithms from the perspectives of objects and criteria. Based on the new accelerator, the number of objects and the dimension of criteria are lessened thus making the accelerated algorithms faster than their original counterparts while maintaining the same reducts. Experimental analysis shows the validity and efficiency of the proposed methods.     

A decision approach to competitive electronic sealed-bid auctions for land

Electronic markets for land are innovative techniques potentially advantageous to buyers and private sellers, the latter being interested in sealed-bid auctions assuring high levels of competition among many bidders so that coalitions and cooperative games are ruled out. Land electronic tendering requires sufficient online information for bidders such as valuation reports by prestigious surveyors. To help the bidder make his best choice, we propose a decision model for moderately pessimistic players facing tenders where competition among a great number of independent antagonists excludes the use of cooperative games and involves strict uncertainty. A worked example concerning farmland in Spain is presented.     

A fuzzy soft set theoretic approach to decision making problems

The problem of decision making in an imprecise environment has found paramount importance in recent years. A novel method of object recognition from an imprecise multiobserver data has been presented here. The method involves construction of a Comparison Table from a fuzzy soft set in a parametric sense for decision making.     

A topological approach to the theory of groups acting on trees

Bass and Serre recast the foundations of combinatorial group theory in [7]. Here we apply the allied notions of fundamental group and covering space to redevelop their theory in a less combinatorial fashion; for example the Bass—Serre Structure Theorem is proved with no a priori knowledge of the group theoretic structure of the fundamental group of a graph of groups. Van Kampen's Theorem is used only once, in its simplest form (in the proof of Theorem 7). Cancellation arguments and normal form theorems, such as Britton's Lemma, are completely avoided; indeed they are incidental corollaries from our viewpoint. The tree which plays a central role in [7] appears in Theorem 2 as the natural analogue of the “strecken komplexe” introduced by A. Speiser [8], and subsequently also employed by R. Nevanlinna [5], to describe certain simply connected Riemann surfaces occurring in value distribution theory.     

Lower bounds for algebraic decision trees

A topological method is given for obtaining lower bounds for the height of algebraic decision trees. The method is applied to the knapsack problem where an $\text{Ω(n}{}^2\text{)}$ bound is obtained for trees with bounded-degree polynomial tests, thus extending the Dobkin-Lipton result for linear trees. Applications to the convex hull problem and the distinct element problem are also indicated. Some open problems are discussed.