## Branch-and-Bound Applications in Combinatorial Data AnalysisThis monograph focuses on the application of the solution strategy known as branch-and-bound to problems of combinatorial data analysis. Combinatorial data analysis problems typically require either the sel- tion of a subset of objects from a larger (master) set, the grouping of a collection of objects into mutually exclusive and exhaustive subsets, or the sequencing of objects. To obtain verifiably optimal solutions for this class of problems, we must evaluate (either explicitly or implicitly) all feasible solutions. Unfortunately, the number of feasible solutions for problems of combinatorial data analysis grows exponentially with pr- lem size. For this reason, the explicit enumeration and evaluation of all solutions is computationally infeasible for all but the smallest problems. The branch-and-bound solution method is one type of partial enume- tion solution strategy that enables some combinatorial data analysis pr- lems to be solved optimally without explicitly enumerating all feasible solutions. To understand the operation of a branch-and-bound algorithm, we d- tinguish complete solutions from partial solutions. A complete solution is one for which a feasible solution to the optimization problem has been produced (e. g. , all objects are assigned to a group, or all objects are - signed a sequence position). A partial solution is an incomplete solution (e. g. , some objects are not assigned to a group, or some objects are not assigned a sequence position). |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

1 | |

Cluster AnalysisPartitioning | 9 |

Partitioning | 25 |

Minimum WithinCluster Sums of Dissimilarities Partitioning | 43 |

Minimum WithinCluster Sums of Squares Partitioning | 59 |

6 | 77 |

Introduction to the BranchandBound Paradigm for Seriation | 91 |

9 | 113 |

### Other editions - View all

Branch-and-Bound Applications in Combinatorial Data Analysis Michael J. Brusco,Stephanie Stahl Limited preview - 2005 |

Branch-and-Bound Applications in Combinatorial Data Analysis Michael J. Brusco,Stephanie Stahl No preview available - 2010 |

### Common terms and phrases

A(permutation(i adjacency test AltContribution AltPosition anti-Robinson assigned bbwcsum.for biobjective bound test Branch forward Branch right branch-and-bound algorithm Brusco Chapter cluster analysis column gradient compare2 computation criteria criterion 2.3 CSize(k CurrentContribution data in Table data set Defays diagonal dynamic programming efficient frontier entries Euclidean distances fathoming girth gradient indices heuristic Hubert implementation incumbent initial lower bound interchange test Kabah lambda(i loop loss function maximizing the dominance minimizing Minitab NewWithin2 num_k NUMBER NUMBER NUMBER number of clusters NUMBER OF OBJECTS objective function objective function value OBJECTS OBJECTS OBJECTS optimal permutation optimal solution pairwise dissimilarities partial sequence partial solution evaluation partition diameter permutation(j permutation(Position Position problem procedure Prune pseudocode psuedocode regression regression analysis reordering Retract row and column RSSy selected variables seriation SumLeft sums of dissimilarities sums of squares symmetric matrix tion unassigned objects unidimensional scaling unweighted upper bound variable selection within-cluster sums WithinJ