Constrained two-dimensional cutting: an improvement of Christofides and Whitlock's exact algorithm

Christofides and Whitlock have developed a top-down algorithm which combines in a nice tree search procedure Gilmore and Gomory's algorithm and a transportation routine called at each node of the tree for solving exactly the constrained two-dimensional cutting problem. Recently, another bottom-up algorithm has been developed and reported as being more efficient. In this paper, we propose a modification to the branching strategy and we introduce the one-dimensional bounded knapsack in the original Christofides and Whitlock algorithm. Then, by exploiting dynamic programming properties we obtain good lower and upper bounds which lead to significant branching cuts, resulting in a drastic reduction of calls of the transportation routine. Finally, we propose an incremental solution of the numerous generated transportation problems. The resulting algorithm reveals superior performance to other known algorithms.     

On the complexity of searching game trees and other recursion trees

Game tree searching is one of the fundamental topics in artificial intelligence and decision analysis. The main results of this paper are: (1) A simple nondirectional algorithm for searching binary bi-valued game trees is presented and analysed. For a wide range of parameters s in Schrüfers s-tree model it has a smaller branching factor than directional search. (2) A cascade technique for game tree models with at least four different node values is presented. This technique yields algorithms with smaller branching factors than alpha-beta. (The amount of storage required by the algorithms in (1) and (2) is only linear in the depth of the searched trees.) (3) Recursion trees are defined as a natural generalisation of game trees. A combinatorial lower bound for the complexity of searching symmetric recursion trees is proved. (4) Those recursion trees are characterized which can be searched by pruning techniques.     

Towards a Tighter Coupling of Bottom-Up and Top-Down Sparse Matrix Ordering Methods

Most state-of-the-art ordering schemes for sparse matrices are a hybrid of a bottom-up method such as minimum degree and a top-down scheme such as George's nested dissection. In this paper we present an ordering algorithm that achieves a tighter coupling of bottom-up and top-down methods. In our methodology vertex separators are interpreted as the boundaries of the remaining elements in an unfinished bottom-up ordering. As a consequence, we are using bottom-up techniques such as quotient graphs and special node selection strategies for the construction of vertex separators. Once all separators have been found, we are using them as a skeleton for the computation of several bottom-up orderings. Experimental results show that the orderings obtained by our scheme are in general better than those obtained by other ordering codes.This revised version was published online in October 2005 with corrections to the Cover Date.     

A structured solution framework for fuzzy minimum spanning tree problem and its variants under different criteria

This paper develops a unified and structured solution framework for the minimum spanning tree (MST) problem and its variants (e.g., constrained MST problem and inverse MST problem) on networks with fuzzy link weights. It is applicable to any additive decision criterion under fuzziness (e.g., expected value, value at risk, and conditional value at risk), for generalized cases that the link weights may be represented by arbitrary types of fuzzy variables. It also applies to the entropy criterion while the link weights are continuous fuzzy variables. Following the optimality conditions of the fuzzy MST under different decision criteria proved first in this paper, it is shown that the MST problem and its variants on a fuzzy network can be converted into equivalent deterministic counterparts on their corresponding crisp networks. Consequently, these problems can be effectively solved via their deterministic counterparts without fuzzy simulation, and meanwhile, the performance of the trees under a specified criterion is precisely measured. The accuracy and efficiency are both significantly improved compared with other fuzzy simulation-based approaches. Numerical examples illustrate the superiority of the proposed solution framework. Furthermore, some new theoretical conclusions on the MST problem under fuzziness are also presented.

     

区间直觉模糊判断矩阵群决策中的逆判问题

研究了区间直觉模糊判断矩阵的群决策问题.定义了两种区间直觉模糊集相似度公式,给出两种与决策群体意见一致性程度最高的理想区间直觉模糊判断矩阵构造优化方法.利用矩阵对不同专家判断矩阵中相同位置元素的一致性进行分析,并对不同专家的判断信息进行整体相似程度分析,最后通过算例说明了该方法的有效性和实用性.     

Top-down approaches for integrated risk management: How accurate are they?

Banks and other financial institutions try to compute the necessary amount of total capital that they need for absorbing stochastically dependent losses from different risk types (e.g., credit risk and market risk). Two sophisticated procedures of this so-called integrated risk management are the top-down and the bottom-up approaches. When banks apply a more sophisticated risk integration approach at all, it is usually the top-down approach where copula functions are employed for linking the marginal distributions of profit and losses resulting from different risk types. However, it is not clear at all how accurate this approach is. Assuming that the bottom-up approach corresponds to the real-word data-generating process and using a comprehensive simulation study, it is shown that the top-down approach can underestimate the necessary amount of total capital for lower credit qualities. Furthermore, the direction and strength of the stochastic dependence between the risk types, the copula function employed, and the loss definitions all have an impact on the performance of the top-down approach. In addition, a goodness-of-fit test shows that, based on time series of loss data with realistic length, it is rather difficult to decide which copula function is the right one.     

On branching heuristics for the bi-objective 0/1 unidimensional knapsack problem

This paper focuses on branching strategies that are involved in branch and bound algorithms when solving multi-objective optimization problems. The choice of the branching variable at each node of the search tree constitutes indeed an important component of these algorithms. In this work we focus on multi-objective knapsack problems. In the literature, branching heuristics used for these problems are static, i.e., the order on the variables is determined prior to the execution. This study investigates the benefit of defining more sophisticated branching strategies. We first analyze and compare a representative set of classic branching heuristics and conclude that none can be identified as the best overall heuristic. Using an oracle, we highlight that combining branching heuristics within the same branch and bound algorithm leads to considerably reduced search trees but induces high computational costs. Based on learning adaptive techniques, we propose then dynamic adaptive branching strategies that are able to select the suitable heuristic to apply at each node of the search tree. Experiments are conducted on the bi-objective 0/1 unidimensional knapsack problem.     

A fuzzy-stochastic OWA model for robust multi-criteria decision making

All realistic Multi-Criteria Decision Making (MCDM) problems face various kinds of uncertainty. Since the evaluations of alternatives with respect to the criteria are uncertain they will be assumed to have stochastic nature. To obtain the uncertain optimism degree of the decision maker fuzzy linguistic quantifiers will be used. Then a new approach for fuzzy-stochastic modeling of MCDM problems will be introduced by merging the stochastic and fuzzy approaches into the OWA operator. The results of the new approach, entitled FSOWA, give the expected value and the variance of the combined goodness measure for each alternative. Robust decision depends on the combined goodness measures of alternatives and also on the variations of these measures under uncertainty. In order to combine these two characteristics a composite goodness measure will be defined. The theoretical results will be illustrated in a watershed management problem. By using this measure will give more sensitive decisions to the stakeholders whose optimism degrees are different than that of the decision maker. FSOWA can be used for robust decision making on the competitive alternatives under uncertainty.     

A two-phase method for selecting IMRT treatment beam angles: Branch-and-Prune and local neighborhood search

This paper presents a new two-phase solution approach to the beam angle and fluence map optimization problem in Intensity Modulated Radiation Therapy (IMRT) planning. We introduce Branch-and-Prune (B&P) to generate a robust feasible solution in the first phase. A local neighborhood search algorithm is developed to find a local optimal solution from the Phase I starting point in the second phase. The goal of the first phase is to generate a clinically acceptable feasible solution in a fast manner based on a Branch-and-Bound tree. In this approach, a substantially reduced search tree is iteratively constructed. In each iteration, a merit score based branching rule is used to select a pool of promising child nodes. Then pruning rules are applied to select one child node as the branching node for the next iteration. The algorithm terminates when we obtain a desired number of angles in the current node. Although Phase I generates quality feasible solutions, it does not guarantee optimality. Therefore, the second phase is designed to converge Phase I starting solutions to local optimality. Our methods are tested on two sets of real patient data. Results show that not only can B&P alone generate clinically acceptable solutions, but the two-phase method consistently generates local optimal solutions, some of which are shown to be globally optimal.     

Information-theoretic approaches to branching in search

Deciding what question to branch on at each node is a key element of search algorithms. In this paper, we describe a collection of techniques for branching decisions that are motivated from an information-theoretic perspective. The idea is to drive the search to reduce the uncertainty (entropy) in the current subproblem. We present four families of methods for branch question selection in mixed integer programming that use this idea. In the first, a variable to branch on is selected based on lookahead. This method performs comparably to strong branching on MIPLIB, and better than strong branching on hard real-world procurement optimization instances on which CPLEX’s default strong branching outperforms CPLEX’s default branching strategy. The second family combines this idea with strong branching. The third family does not use lookahead, but instead exploits the tie between indicator variables and the variables they govern. This significantly outperforms the state-of-the-art branching strategies on both combinatorial procurement problems and facility location problems. The fourth family concerns branching using carefully constructed linear inequality constraints over sets of variables.     

基于Vague集信息的多属性群决策专家水平评判方法

针对基于Vague集信息的多属性群决策专家水平评判问题提出了两种评判方法.首先引进了基于Vague集信息的多属性群决策信息体(即决策信息体)的相关概念,通过决策信息体构造了基于Vague集信息的一致性决策矩阵及模糊熵,其次利用Vague集信息的相似度量以及Vague集信息的模糊熵两种信息不确定性度量方法,对基于Vague集信息的多属性群决策专家水平评判问题提出了两种评判方法,即统计分析方法和模糊熵分析方法,对专家的评判水平进行排序.最后,通过一个算例说明两种方法的一致性、有效性和实用性.     

New bounds and constraint propagation techniques for the clique partitioning problem

This paper considers the problem of clustering the vertices of a complete edge-weighted graph. The objective is to maximize the sum of the edge weights within the clusters (also called cliques). This so-called Clique Partitioning Problem (CPP) is NP-complete, and has several real-life applications such as groupings in flexible manufacturing systems, in biology, in flight gate assignment, etc. Numerous heuristics and exact approaches as well as benchmark tests have been presented in the literature. Most exact methods use branch and bound with branching over edges. We present tighter upper bounds for each search tree node than those known from the literature, improve the constraint propagation techniques for fixing edges in each node, and present a new branching scheme. The theoretical improvements are reflected by computational tests with real-life data. Although a standard solver delivers best results on randomly generated data, the runtime of the proposed algorithm is very low when being applied to instances on object clustering.     

TASC: Two-attribute-set clustering through decision tree construction

Clustering is the process of grouping a set of objects into classes of similar objects. In the past, clustering algorithms had a common problem that they use only one set of attributes for both partitioning the data space and measuring the similarity between objects. This problem has limited the use of the existing algorithms on some practical situation. Hence, this paper introduces a new clustering algorithm, which partitions data space by constructing a decision tree using one attribute set, and measures the degree of similarity using another. Three different partitioning methods are presented. The algorithm is explained with illustration. The performance and accuracy of the four partitioning methods are evaluated and compared.     

Zero-one integer programs with few constraints —Efficient branch and bound algorithms

The 0–1 integer programming problem and its special case, the 0–1 knapsack problem are frequently encountered in modeling various design and decision making processes. This paper is a follow-up paper to [4] and deals with the development of an effective solution procedure for 0–1 integer programs with few constraints. Detailed computational experiments are carried out and different separation, branching and bounding rules are compared using an experimental branch and bound code. An efficient branch and bound procedure is developed, tested and compared with previously developed optimal algorithms. It is suggested that this procedure may also be used as a heuristic method for large problems by early termination of the tree search. This scheme is tested and found to be very effective.     

Dynamic project selection and funding under risk: A decision tree based MILP approach

This paper presents a mixed integer linear programming (MILP) model for a new class of dynamic project selection and funding problems under risk given multiple scarce resources of different qualifications. The underlying stochastic decision tree concept extends classical approaches mainly in that it adds a novel node type that allows for the continuous control of discrete branching probability distributions. The control functions are piecewise linear and are convex for the costs and concave for the benefits. The MILP-model has been embedded in a prototype Decision Support System (DSS). With respect to the proposed solution the DSS provides complete probability distributions for both costs and benefits.     

考虑n中连续取k失效准则的树状系统可靠性求解方法

树状网络系统在管道运输,网络通信中较为常见,对其进行可靠性评估对系统设计及优化具有重要意义。针对树状冗余系统,在n中连续取k失效准则下,通过有限马尔可夫嵌入法并对其进行变形,研究了树状系统可靠性求解方法。本文对树状系统建模加以定义,提出了基于层数参数,层-节点向量,父-子节点矩阵三元参数的树状系统表示方法,研究了变形有限马尔可夫嵌入法的树状系统n中连续取k失效准则下的可靠性求解方法,给出了三个数值算例应用并分析了算法的运算复杂度。最后,本文对比讨论了基于概率母函数法的树状系统在n中连续取k准则下系统可靠性求解方法的研究,得出结论本文算法针对树状冗余系统n中连续取k失效准则下系统可靠性求解应用范围更广,求解效率较高。     

Branch-reduction-bound algorithm for generalized geometric programming

This article presents a branch-reduction-bound algorithm for globally solving the generalized geometric programming problem. To solve the problem, an equivalent monotonic optimization problem whose objective function is just a simple univariate is proposed by exploiting the particularity of this problem. In contrast to usual branch-and-bound methods, in the algorithm the upper bound of the subproblem in each node is calculated easily by arithmetic expressions. Also, a reduction operation is introduced to reduce the growth of the branching tree during the algorithm search. The proposed algorithm is proven to be convergent and guarantees to find an approximative solution that is close to the actual optimal solution. Finally, numerical examples are given to illustrate the feasibility and efficiency of the present algorithm.     

Genetic learning of accurate and compact fuzzy rule based systems based on the 2-tuples linguistic representation

One of the problems that focus the research in the linguistic fuzzy modeling area is the trade-off between interpretability and accuracy. To deal with this problem, different approaches can be found in the literature. Recently, a new linguistic rule representation model was presented to perform a genetic lateral tuning of membership functions. It is based on the linguistic 2-tuples representation that allows the lateral displacement of a label considering an unique parameter. This way to work involves a reduction of the search space that eases the derivation of optimal models and therefore, improves the mentioned trade-off.Based on the 2-tuples rule representation, this work proposes a new method to obtain linguistic fuzzy systems by means of an evolutionary learning of the data base a priori (number of labels and lateral displacements) and a simple rule generation method to quickly learn the associated rule base. Since this rule generation method is run from each data base definition generated by the evolutionary algorithm, its selection is an important aspect. In this work, we also propose two new ad hoc data-driven rule generation methods, analyzing the influence of them and other rule generation methods in the proposed learning approach. The developed algorithms will be tested considering two different real-world problems.     

Job shop scheduling with beam search

Beam Search is a heuristic method for solving optimization problems. It is an adaptation of the branch and bound method in which only some nodes are evaluated in the search tree. At any level, only the promising nodes are kept for further branching and remaining nodes are pruned off permanently. In this paper, we develop a beam search based scheduling algorithm for the job shop problem. Both the makespan and mean tardiness are used as the performance measures. The proposed algorithm is also compared with other well known search methods and dispatching rules for a wide variety of problems. The results indicate that the beam search technique is a very competitive and promising tool which deserves further research in the scheduling literature.     

Solving generalized fuzzy data envelopment analysis model: a parametric approach

Data envelopment analysis (DEA) is a non-parametric technique to assess the performance of a set of homogeneous decision making units (DMUs) with common crisp inputs and outputs. Regarding the problems that are modelled out of the real world, the data cannot constantly be precise and sometimes they are vague or fluctuating. So in the modelling of such data, one of the best approaches is using the fuzzy numbers. Substituting the fuzzy numbers for the crisp numbers in DEA, the traditional DEA problem transforms into a fuzzy data envelopment analysis (FDEA) problem. Different methods have been suggested to compute the efficiency of DMUs in FDEA models so far but the most of them have limitations such as complexity in calculation, non-contribution of decision maker in decision making process, utilizable for a specific model of FDEA and using specific group of fuzzy numbers. In the present paper, to overcome the mentioned limitations, a new approach is proposed. In this approach, the generalized FDEA problem is transformed into a parametric programming, in which, parameter selection depends on the decision maker’s ideas. Two numerical examples are used to illustrate the approach and to compare it with some other approaches.