Combinatorial optimization and hierarchical classifications

This paper is devoted to some selected topics relating Combinatorial Optimization and Hierarchical Classification. It is oriented toward extensions of the standard classification schemes (the hierarchies): pyramids, quasi-hierarchies, circular clustering, rigid clustering and others. Bijection theorems between these models and dissimilarity models allow to state some clustering problems as optimization problems. Within the galaxy of optimization we have especially discussed the following: NP-completeness results and search for polynomial instances; problems solved in a polynomial time (e.g. subdominant theory); design, analysis and applications of algorithms. In contrast with the orientation to new clustering problems, the last part discusses some standard algorithmic approaches.Received: July 2004, Revised: September 2004, MSC classification: 62H30, 91C20, 05C65, 90C27, 68R01     

A top-down hierarchical classification method

In this paper we present an original top-down hierarchical classification algorithm. In our approach we associate to each decomposition a ‘degree of separability’ which is used to evaluate the efficiency of the decomposition. In particular, it shows whether or not the classes are well separated and also whether or not they are homogeneous. This algorithm can be applied to items defined by real and bounded numbers.     

A multi-parametric programming approach for multilevel hierarchical and decentralised optimisation problems

In this paper, we outline the foundations of a general global optimisation strategy for the solution of multilevel hierarchical and general decentralised multilevel problems, based on our recent developments on multi-parametric programming and control theory. The core idea is to recast each optimisation subproblem, present in the hierarchy, as a multi-parametric programming problem, with parameters being the optimisation variables belonging to the remaining subproblems. This then transforms the multilevel problem into single-level linear/convex optimisation problems. For decentralised systems, where more than one optimisation problem is present at each level of the hierarchy, Nash equilibrium is considered. A three person dynamic optimisation problem is presented to illustrate the mathematical developments.     

A hierarchical copula-based world-wide valuation of sovereign risk

We propose a new model for the aggregation of risks that is very flexible and useful in high dimensional problems. We propose a copula-based model that is both hierarchical and hybrid (HYC for short), because: (i) the dependence structure is modeled as a hierarchical copula, (ii) it unifies the idea of the clusterized homogeneous copula-based approach (CHC for short) and its limiting version (LHC for short) proposed in Bernardi and Romagnoli (2012, 2013). Based on this, we compute the loss function of a world-wide sovereign debt portfolio which accounts for a systemic dependence of all countries, in line with a global valuation of financial risks. Our approach enables us to take into account the non-exchangeable behavior of a sovereign debts’ portfolio clustered into several classes with homogeneous risk and to recover a possible risks’ hierarchy. A comparison between the HYC loss surface and those computed through a pure limiting approach, which is commonly used in high dimensional problems, is presented and the impact of the concentration and the granularity errors is appreciated. Finally the impact of an enlargement of the dependence structure is discussed, in the contest of a geographical area sub-portfolios analysis now relevant to determine the risk contributions of subgroups under the presence of a wider dependence structure. This argument is presented in relation to the evaluation of the insurance premium and the collateral related to the designed project of an euro-insurance-bond.     

Identification of fuzzy relation models using hierarchical fair competition-based parallel genetic algorithms and information granulation

The paper is concerned with a hybrid optimization of fuzzy inference systems based on hierarchical fair competition-based parallel genetic algorithms (HFCGA) and information granulation. The process of information granulation is realized with the aid of the C-Means clustering. HFCGA being a multi-population based parallel genetic algorithms (PGA) is exploited here to realize structure optimization and carry out parameter estimation of the fuzzy models. The HFCGA becomes helpful in the context of fuzzy models as it restricts a premature convergence encountered quite often in optimization problems. It concerns a set of parameters of the model including among others the number of input variables to be used, a specific subset of input variables, and the number of membership functions. In the hybrid optimization process, two general optimization mechanisms are explored. The structural development of the fuzzy model is realized via the HFCGA optimization and C-Means, whereas to deal with the parametric optimization we proceed with a standard least square method and the use of the HFCGA technique. A suite of comparative studies demonstrates that the proposed algorithm leads to the models whose performance is superior in comparison with some other constructs commonly used in fuzzy modeling.     

Efficient and reliable hierarchical error estimates for an elliptic obstacle problem

We present and analyze novel hierarchical a posteriori error estimates for a self-adjoint elliptic obstacle problem. Under a suitable saturation assumption, we prove the efficiency and reliability of our hierarchical estimates. The proof is based upon some new observations on the efficiency of some hierarchical error indicators. These new observations allow us to remove an additional regularity condition on the underlying grid required in the previous analysis. Numerical computations confirm our theoretical findings.     

Spectra of generalized compositions of graphs and hierarchical networks

We compute the Laplacian spectra and eigenfunctions of generalized compositions of graphs, as explicit functions of the spectra and eigenfunctions of their components. Applications to two-level hierarchical graphs are given. We introduce the tree composition of graphs and study its spectral decomposition, with applications to some hierarchical networks.     

Chameleon based on clustering feature tree and its application in customer segmentation

Clustering analysis plays an important role in the filed of data mining. Nowadays, hierarchical clustering technique is becoming one of the most widely used clustering techniques. However, for most algorithms of hierarchical clustering technique, the requirements of high execution efficiency and high accuracy of clustering result cannot be met at the same time. After analyzing the advantages and disadvantages of the hierarchical algorithms, the paper puts forward a two-stage clustering algorithm, named Chameleon Based on Clustering Feature Tree (CBCFT), which hybridizes the Clustering Tree of algorithm BIRCH with algorithm CHAMELEON. By calculating the time complexity of CBCFT, the paper argues that the time complexity of CBCFT increases linearly with the number of data. By experimenting on sample data set, this paper demonstrates that CBCFT is able to identify clusters with large variance in size and shape and is robust to outliers. Moreover, the result of CBCFT is as similar as that of CHAMELEON, but CBCFT overcomes the shortcoming of the low execution efficiency of CHAMELEON. Although the execution time of CBCFT is longer than BIRCH, the clustering result of CBCFT is much satisfactory than that of BIRCH. Finally, through a case of customer segmentation of Chinese Petroleum Corp. HUBEI branch; the paper demonstrates that the clustering result of the case is meaningful and useful. The research is partially supported by National Natural Science Foundation of China (grants #70372049 and #70121001).     

Grid Methods in Computational Real Algebraic (and Semialgebraic) Geometry

In recent years, a family of numerical algorithms to solve problems in real algebraic and semialgebraic geometry has been slowly growing. Unlike their counterparts in symbolic computation they are numerically stable. But their complexity analysis, based on the condition of the data, is radically different from the usual complexity analysis in symbolic computation as these numerical algorithms may run forever on a thin set of ill-posed inputs.     

Modelling and hierarchical diagnosis of timed discrete-event systems

A new diagnostic method for hierarchically structured discrete-event systems is presented. The efficiency of this method results from the fact that the complexity of the diagnostic task is reduced by first detecting a faulty component using a coarse process model on a high level of abstraction, and subsequently refining the result by investigating the faulty component with the help of a detailed component model in order to identify the fault with sufficient precision. On both abstraction levels, the method uses a timed discrete-event model of the appropriate part of the system. On the higher abstraction level a timed event graph is used that describes how the temporal distance of the events is changed by component faults. On the lower level of abstraction, timed automata are used to cope with the non-determinism of the event sequence generated by the faulty and faultless components. The approach is illustrated by the diagnosis of a batch process.     

Study of the plant recolonization process in a burnt heathland using a method of hierarchical classification

The reinstallation of different plant-species and their evolution during a ten-year period in a heathland after a fire accident has been studied by using the algorithm of heirarchical classification based on correlation (ABC) introduced by Tallur.¹ Classification under contiguity restraint of the set of observation points (subintervals of an experimental observation line) enables one to determine the ‘patches’ having uniform vegetation structure. Lerman's ‘local’ and ‘global’ statistics are used to condense the classification tree to its significant nodes and to choose the most significant partition. x² statistics are proposed to test whether a given patch has a ‘significant’ vegetation structure and if the association between a patch and a plant species is significant. Evolution of the horizontal structure of vegetation is studied by comparing the sets of patches obtained at successive observation dates and the corresponding dominant species.     

Evaluating and selecting the supplier in detergent production industry using hierarchical fuzzy TOPSIS

Supply chain management has increasingly attracted attention as a systematic approach to integrate the supply chain in order to planning and controlling the materials and information from suppliers to customers. One of the most important issues in supply chain management is selection of the appropriate supplier which has significant effect on purchasing cost decrease and increase in the organization’s competition ability. Selection of the best supplier is naturally complex with no definite structure, and dependent on the type of suppliers’ activity. In the process of decision making about suppliers and many qualitative and quantitative performance indicators such as quality, price, flexibility, and due date should be considered. Then, the supplier selection problem is a multi-criteria decision making problem where numerous methods have been proposed to solve this problem so far. In the current paper, four suppliers of imported raw material “Tripolyphosphate (TPP)” (primary material to produce the detergent powder with a case study in Iran) are evaluated based on 25 effective criteria using the hierarchical fuzzy TOPSIS (HFTOPSIS) approach.     

E-Bayesian estimation and hierarchical Bayesian estimation of failure rate

This paper introduces a new method, E-Bayesian estimation method, to estimate failure rate. The method is suitable for the censored or truncated data with small sample sizes and high reliability. The definition and properties of E-Bayesian estimation are given. A real data set is discussed, which shows that the method is both efficiency and easy to operate.     

Integrating Interval Estimates of Global Optima and Local Search Methods for Combinatorial Optimization Problems

The problem of estimating the global optimal values of intractable combinatorial optimization problems is of interest to researchers developing and evaluating heuristics for these problems. In this paper we present a method for combining statistical optimum prediction techniques with local search methods such as simulated annealing and tabu search and illustrate the approach on a single machine scheduling problem. Computational experiments show that the approach yields useful estimates of optimal values with very reasonable computational effort.     

Cooperative computing with fragmentable and mergeable groups

This work considers the problem of performing a set of N tasks on a set of P cooperating message-passing processors (PN). The processors use a group communication service (GCS) to coordinate their activity in the setting where dynamic changes in the underlying network topology cause the processor groups to change over time. GCSs have been recognized as effective building blocks for fault-tolerant applications in such settings. Our results explore the efficiency of fault-tolerant cooperative computation using GCSs. The original investigation of this area by (Dolev et al., Dynamic load balancing with group communication, in: Proc. of the 6th International Colloquium on Structural Information and Communication Complexity, 1999) focused on competitive lower bounds, non-redundant task allocation schemes and work-efficient algorithms in the presence of fragmentation regroupings. In this work we investigate work-efficient and message-efficient algorithms for fragmentation and merge regroupings. We present an algorithm that uses GCSs and implements a coordinator-based strategy. For the analysis of our algorithm we introduce the notion of view-graphs that represent the partially-ordered view evolution history witnessed by the processors. For fragmentations and merges, the work of the algorithm (defined as the worst case total number of task executions counting multiplicities) is not more than min{N·f+N,N·P}, and the message complexity is no worse than 4(N·f+N+P·m), where f and m denote the number of new groups created by fragmentations and merges, respectively. Note that the constants are very small and that, interestingly, while the work efficiency depends on the number of groups f created as the result of fragmentations, work does not depend on the number of groups m created as the result of merges.     

A class of hierarchical queueing networks and their analysis

Queueing networks are an adequate model type for the analysis of complex system behavior. Most of the more realistic models are rather complex and do not fall into the easy solvable class of product form networks. Those models have to be analyzed by numerical solution of the underlying Markov chain and/or approximation techniques including simulation. In this paper a class of hierarchically structured queueing networks is considered and it is shown that the hierarchical model structure is directly reflected in the state space and the generator matrix of the underlying Markov chain. Iterative solution techniques for stationary and transient analysis can be modified to make use of the model structure and allow an efficient numerical analysis of large, up to now not solvable queueing networks.     

A branch and cut algorithm for the hierarchical network design problem

The Hierarchical Network Design Problem consists of locating a minimum cost bi-level network on a graph. The higher level sub-network is a path visiting two or more nodes. The lower level sub-network is a forest connecting the remaining nodes to the path. We optimally solve the problem using an ad hoc branch and cut procedure. Relaxed versions of a base model are solved using an optimization package and, if binary variables have fractional values or if some of the relaxed constraints are violated in the solution, cutting planes are added. Once no more cuts can be added, branch and bound is used. The method for finding valid cutting planes is presented. Finally, we use different available test instances to compare the procedure with the best known published optimal procedure, with good results. In none of the instances we needed to apply branch and bound, but only the cutting planes.     

Optimization based DC programming and DCA for hierarchical clustering

One of the most promising approaches for clustering is based on methods of mathematical programming. In this paper we propose new optimization methods based on DC (Difference of Convex functions) programming for hierarchical clustering. A bilevel hierarchical clustering model is considered with different optimization formulations. They are all nonconvex, nonsmooth optimization problems for which we investigate attractive DC optimization Algorithms called DCA. Numerical results on some artificial and real-world databases are reported. The results demonstrate that the proposed algorithms are more efficient than related existing methods.