Reusable components in decision tree induction algorithms

We propose a generic decision tree framework that supports reusable components design. The proposed generic decision tree framework consists of several sub-problems which were recognized by analyzing well-known decision tree induction algorithms, namely ID3, C4.5, CART, CHAID, QUEST, GUIDE, CRUISE, and CTREE. We identified reusable components in these algorithms as well as in several of their partial improvements that can be used as solutions for sub-problems in the generic decision tree framework. The identified components can now be used outside the algorithm they originate from. Combining reusable components allows the replication of original algorithms, their modification but also the creation of new decision tree induction algorithms. Every original algorithm can outperform other algorithms under specific conditions but can also perform poorly when these conditions change. Reusable components allow exchanging of solutions from various algorithms and fast design of new algorithms. We offer a generic framework for component-based algorithms design that enhances understanding, testing and usability of decision tree algorithm parts.     

Practical arbitrage‐free scenario tree reduction methods and their applications in financial optimization

We construct an arbitrage‐free scenario tree reduction model, from which some arbitrage‐free scenario tree reduction algorithms are designed. They ensure that the reduced scenario trees are arbitrage free. Numerical results show the practicality and efficiency of the proposed algorithms. Results for multistage portfolio selection problems demonstrate the necessity and importance for guaranteeing that the reduced scenario trees are arbitrage free, as well as the practicality of the proposed arbitrage‐free scenario tree reduction algorithms for financial optimization.     

Exact arithmetic on the Stern–Brocot tree

In this paper we present the Stern–Brocot tree as a basis for performing exact arithmetic on rational numbers. There exists an elegant binary representation for positive rational numbers based on this tree [Graham et al., Concrete Mathematics, 1994]. We will study this representation by investigating various algorithms to perform exact rational arithmetic using an adaptation of the homographic and the quadratic algorithms that were first proposed by Gosper for computing with continued fractions. We will show generalisations of homographic and quadratic algorithms to multilinear forms in n variables. Finally, we show an application of the algorithms for evaluating polynomials.     

Markovian trees: properties and algorithms

In this paper we introduce a structure called the Markovian tree (MT). We define the MT and explore its alternative representation as a continuous-time Markovian Multitype Branching Process. We then develop two algorithms, the Depth and Order algorithms to determine the probability of eventual extinction of the MT process. We show that both of these algorithms have very natural physically intuitive interpretations and are analogues of the Neuts and U algorithms in Matrix-analytic Methods. Furthermore, we show that a special case of the Depth algorithm sheds new light on the interpretation of the sample paths of the Neuts algorithm.     

On the strong chromatic index and maximum induced matching of tree-cographs,permutation graphs and chordal bipartite graphs

We show that there exist linear-time algorithms that compute the strong chromatic index and a maximum induced matching of tree-cographs when the decomposition tree is a part of the input. We also show that there exist efficient algorithms for the strong chromatic index of (bipartite) permutation graphs and of chordal bipartite graphs.     

Once edge-reinforced random walk on a tree

 We consider a nearest neighbor walk on a regular tree, with transition probabilities proportional to weights or conductances of the edges. Initially all edges have weight 1, and the weight of an edge is increased to $c > 1$ when the edge is traversed for the first time. After such a change the weight of an edge stays at $c$ forever. We show that such a walk is transient for all values of $c \ge 1$, and that the walk moves off to infinity at a linear rate. We also prove an invariance principle for the height of the walk. Received: 6 March 2001 / Revised version: 16 July 2001 / Published online: 15 March 2002     

Tree-Structured Mixed-Effects Regression Modeling for Longitudinal Data

Tree-structured models have been widely used because they function as interpretable prediction models that offer easy data visualization. A number of tree algorithms have been developed for univariate response data and can be extended to analyze multivariate response data. We propose a tree algorithm by combining the merits of a tree-based model and a mixed-effects model for longitudinal data. We alleviate variable selection bias through residual analysis, which is used to solve problems that exhaustive search approaches suffer from, such as undue preference to split variables with more possible splits, expensive computational cost, and end-cut preference. Most importantly, our tree algorithm discovers trends over time on each of the subspaces from recursive partitioning, while other tree algorithms predict responses. We investigate the performance of our algorithm with both simulation and real data studies. We also develop an R package melt that can be used conveniently and freely. Additional results are provided as online supplementary material.     

A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem

The capacitated minimum spanning tree (CMST) problem is to find a minimum cost spanning tree in a network where nodes have specified demands, with an additional capacity constraints on the subtrees incident to a given source node s. The capacitated minimum spanning tree problem arises as an important subproblem in many telecommunication network design problems. In a recent paper, Ahuja et al. (Math. Program. 91 (2001) 71) proposed two very large-scale neighborhood search algorithms for the capacitated minimum spanning tree problem. Their first node-based neighborhood structure is obtained by performing multi-exchanges involving several trees where each tree contributes a single node. Their second tree-based neighborhood structure is obtained by performing multi-exchanges where each tree contributes a subtree. The computational investigations found that node-based multi-exchange neighborhood gives the best performance for the homogenous demand case (when all nodes have the same demand), and the tree-based multi-exchange neighborhood gives the best performance for the heterogeneous demand case (when nodes may have different demands). In this paper, we propose a composite neighborhood structure that subsumes both the node-based and tree-based neighborhoods, and outperforms both the previous neighborhood search algorithms for solving the capacitated minimum spanning tree problem on standard benchmark instances. We also develop improved dynamic programming based exact algorithms for searching the composite neighborhood.     

On Rotations and the Generation of Binary Trees

The rotation graph, G_n, has vertex set consisting of all binary trees with n nodes. Two vertices are connected by an edge if a single rotation will transform one tree into the other. We provide a simpler proof of a result of Lucas that G_n, contains a Hamilton path. Our proof deals directly with the pointer representation of the binary tree. This proof provides the basis of an algorithm for generating all binary trees that can be implemented to run on a pointer machine and to use only constant time between the output of successive trees. Ranking and unranking algorithms are developed for the ordering of binary trees implied by the generation algorithm. These algorithms have time complexity O(n²) (arithmetic operations). We also show strong relationships amongst various representations of binary trees and amongst binary tree generation algorithms that have recently appeared in the literature.     

The robust minimum spanning tree problem: Compact and convex uncertainty

We consider the robust minimum spanning tree problem where edges costs are on a compact and convex subset of Rⁿ. We give the location of the robust deviation scenarios for a tree and characterizations of strictly strong edges and non-weak edges leading to recognition algorithms.     

Classification Trees With Bivariate Linear Discriminant Node Models

This article introduces a classification tree algorithm that can simultaneously reduce tree size, improve class prediction, and enhance data visualization. We accomplish this by fitting a bivariate linear discriminant model to the data in each node. Standard algorithms can produce fairly large tree structures because they employ a very simple node model, wherein the entire partition associated with a node is assigned to one class. We reduce the size of our trees by letting the discriminant models share part of the data complexity. Being themselves classifiers, the discriminant models can also help to improve prediction accuracy. Finally, because the discriminant models use only two predictor variables at a time, their effects are easily visualized by means of two-dimensional plots. Our algorithm does not simply fit discriminant models to the terminal nodes of a pruned tree, as this does not reduce the size of the tree. Instead, discriminant modeling is carried out in all phases of tree growth and the misclassification costs of the node models are explicitly used to prune the tree. Our algorithm is also distinct from the “linear combination split” algorithms that partition the data space with arbitrarily oriented hyperplanes. We use axis-orthogonal splits to preserve the interpretability of the tree structures. An extensive empirical study with real datasets shows that, in general, our algorithm has better prediction power than many other tree or nontree algorithms.     

Finding all nondominated points of multi-objective integer programs

We develop exact algorithms for multi-objective integer programming (MIP) problems. The algorithms iteratively generate nondominated points and exclude the regions that are dominated by the previously-generated nondominated points. One algorithm generates new points by solving models with additional binary variables and constraints. The other algorithm employs a search procedure and solves a number of models to find the next point avoiding any additional binary variables. Both algorithms guarantee to find all nondominated points for any MIP problem. We test the performance of the algorithms on randomly-generated instances of the multi-objective knapsack, multi-objective shortest path and multi-objective spanning tree problems. The computational results show that the algorithms work well.     

Numerical algorithms and simulations for reflected backward stochastic differential equations with two continuous barriers

In this paper we study different algorithms for reflected backward stochastic differential equations (BSDE in short) with two continuous barriers based on the framework of using a binomial tree to simulate 1-d Brownian motion. We introduce numerical algorithms by the penalization method and the reflected method, respectively. In the end simulation results are also presented.     

Numerical algorithms and simulations for reflected backward stochastic differential equations with two continuous barriers

In this paper we study different algorithms for reflected backward stochastic differential equations (BSDE in short) with two continuous barriers based on the framework of using a binomial tree to simulate 1-d Brownian motion. We introduce numerical algorithms by the penalization method and the reflected method, respectively. In the end simulation results are also presented.     

Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem

Evolutionary algorithms are applied to problems that are not well understood as well as to problems in combinatorial optimization. The analysis of these search heuristics has been started for some well-known polynomial solvable problems. Such analyses are starting points for the analysis of evolutionary algorithms on difficult problems. We present the first runtime analysis of a multi-objective evolutionary algorithm on a NP-hard problem. The subject of our analysis is the multi-objective minimum spanning tree problem for which we give upper bounds on the expected time until a simple evolutionary algorithm has produced a population including for each extremal point of the Pareto front a corresponding spanning tree. These points are of particular interest as they give a 2-approximation of the Pareto front. We show that in expected pseudopolynomial time a population is produced that includes for each extremal point a corresponding spanning tree.     

Algorithms for propositional model counting

We present algorithms for the propositional model counting problem #SAT. The algorithms utilize tree decompositions of certain graphs associated with the given CNF formula; in particular we consider primal, dual, and incidence graphs. We describe the algorithms coherently for a direct comparison and with sufficient detail for making an actual implementation reasonably easy. We discuss several aspects of the algorithms including worst-case time and space requirements.     

Lower and upper bounds for the spanning tree with minimum branch vertices

We study a variant of the spanning tree problem where we require that, for a given connected graph, the spanning tree to be found has the minimum number of branch vertices (that is vertices of the tree whose degree is greater than two). We provide four different formulations of the problem and compare different relaxations of them, namely Lagrangian relaxation, continuous relaxation, mixed integer-continuous relaxation. We approach the solution of the Lagrangian dual both by means of a standard subgradient method and an ad-hoc finite ascent algorithm based on updating one multiplier at the time. We provide numerical result comparison of all the considered relaxations on a wide set of benchmark instances. A useful follow-up of tackling the Lagrangian dual is the possibility of getting a feasible solution for the original problem with no extra costs. We evaluate the quality of the resulting upper bound by comparison either with the optimal solution, whenever available, or with the feasible solution provided by some existing heuristic algorithms.     

Computing optimal rectilinear Steiner trees: A survey and experimental evaluation

The rectilinear Steiner tree problem is to find a minimum-length rectilinear interconnection of a set of points in the plane. A reduction from the rectilinear Steiner tree problem to the graph Steiner tree problem allows the use of exact algorithms for the graph Steiner tree problem to solve the rectilinear problem. Furthermore, a number of more direct, geometric algorithms have been devised for computing optimal rectilinear Steiner trees. This paper surveys algorithms for computing optimal rectilinear Steiner trees and presents experimental results comparing nine of them: graph Steiner tree algorithms due to Beasley, Bern, Dreyfus and Wagner, Hakimi, and Shore, Foulds, and Gibbons and geometric algorithms due to Ganley and Cohoon, Salowe and Warme, and Thomborson, Alpern, and Carter.     

Packing Steiner trees: a cutting plane algorithm and computational results

In this paper we describe a cutting plane algorithm for the Steiner tree packing problem. We use our algorithm to solve some switchbox routing problems of VLSI-design and report on our computational experience. This includes a brief discussion of separation algorithms, a new LP-based primal heuristic and implementation details. The paper is based on the polyhedral theory for the Steiner tree packing polyhedron developed in our companion paper (this issue) and meant to turn this theory into an algorithmic tool for the solution of practical problems.     

Orbitopal fixing

The topic of this paper are integer programming models in which a subset of 0/1-variables encode a partitioning of a set of objects into disjoint subsets. Such models can be surprisingly hard to solve by branch-and-cut algorithms if the order of the subsets of the partition is irrelevant, since this kind of symmetry unnecessarily blows up the search tree.We present a general tool, called orbitopal fixing, for enhancing the capabilities of branch-and-cut algorithms in solving such symmetric integer programming models. We devise a linear time algorithm that, applied at each node of the search tree, removes redundant parts of the tree produced by the above mentioned symmetry. The method relies on certain polyhedra, called orbitopes, which have been introduced in [14]. It does, however, not explicitly add inequalities to the model. Instead, it uses certain fixing rules for variables. We demonstrate the computational power of orbitopal fixing at the example of a graph partitioning problem.