Branch-and-Bound Applications in Combinatorial Data Analysis

1. Front Matter

   Pages i-xii

   PDF

2. Introduction

   Pages 1-12

3. Cluster Analysis—Partitioning

   1. An Introduction to Branch-and-Bound Methods for Partitioning

      Pages 15-24

   2. Minimum-Diameter Partitioning

      Pages 25-41

   3. Minimum Within-Cluster Sums of Dissimilarities Partitioning

      Pages 43-58

   4. Minimum Within-Cluster Sums of Squares Partitioning

      Pages 59-76

   5. Multiobjective Partitioning

      Pages 77-87

4. Seriation

   1. Introduction to the Branch-and-Bound Paradigm for Seriation

      Pages 91-95

   2. Seriation—Maximization of a Dominance Index

      Pages 97-112

   3. Seriation—Maximization of Gradient Indices

      Pages 113-128

   4. Seriation—Unidimensional Scaling

      Pages 129-146

   5. Seriation—Multiobjective Seriation

      Pages 147-169

5. Variable Selection

   1. Introduction to Branch-and-Bound Methods for Variable Selection

      Pages 173-175

   2. Variable Selection for Cluster Analysis

      Pages 177-185

   3. Variable Selection for Regression Analysis

      Pages 187-202

6. Back Matter

   Pages 203-221

   PDF

This 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).

• Analysis
• Cluster analysis
• Graph
• Regression analysis
• Sim
• Statistical Analysis
• algorithms
• classification
• clustering
• data analysis
• operations research
• optimization

From the reviews:

"To say it unadorned at the outset, this excellent mongraph by Brusco and Stahl on applications of branch-and-bound algorithms in combinatorial data anlaysis fills a long neglected gap in the quantitative psychology literature, and will prove an indispensable companion to any researcher having serious interest in advanced techniques for seriation/scaling and nonhierarchical clustering." Psychometrika

"This monograph is true to its purpose: developing and carefully explaining the application of branch-and-bound (B&B) algorithms for the solution of specific combinatorial optimization problems in statistics. … One of the bright features of this book is the even handed way in which the B&B methods are presented. In each case, the authors clearly spell out not only the process but also its strengths and limitations. … Brusco and Stahl do a nice job … ." (Jon R. Kettenring, SIAM Review, Vol. 48 (2), 2006)

"This book both summarizes and illustrates the methods that are currently available for applying branch-and-bound methods to certain data analysis situations. … The mathematical basis is clearly explained, pseudo-code for the algorithms is given where needed, very simple cases are used to demonstrate the methodology, and larger examples are also presented. … Care is taken to discuss the limitations as well as the advantages of the branch-and-bound approach." (C.D. Kemp, Short Book Reviews, Vol. 26 (1), 2006)

"This book … is the first attempt to use this technique, branch and bound, to solve discrete optimization problems that arise in statistical data analysis. The authors are one of the pioneers in this area and authored a series of papers in relevant leading journals. This book is … written in a more lucid language, and includes a good number of examples, illustrations and case studies. … This book is going to be extremely useful to the researchers or practitioners of combinatorialdata analysis." (Bimal Roy, Sankhya: The Indian Journal of Statistics, Vol. 68 (1), 2006)

"It is the aim of this monograph to summarise and illustrate available methods for applying the branch-and-bound process to problems of combinatorial data analysis. … The book is well suited to all students and researchers interested in the implementation of branch-and-bound procedures for the statistical analysis of data." (Christina Diakaki, Zentralblatt MATH, Vol. 1093 (19), 2006)

"The aim of this book is to build a bridge between operations research (discrete optimization) and statistics. … Overall, the book is well structured and easily readable and a good introduction to the field of Branch and Bound algorithms as a possible solution to selected problems in statistics." (Gero Szepannek, Statistical Papers, Vol. 48, 2007)

"Michael Brusco and Stephanie Stahl suggest solving combinatorial data analysis problems by using the branch-and-bound technique to optimize the objective functions that measure goodness of grouping or sequencing. … Brusco and Stahl’s book is valuable for students and researchers interested in optimization or data analysis. … They provide mathematical descriptions of objective functions and bounds, pseudocodes, step-by-step illustrations, software programs, and their results for several problems." (Julius Zilinskas, Interfaces, Vol. 37 (1), 2007)

• Department of Marketing College of Business, Florida State University, Tallahassee, USA

  Michael J. Brusco

• Tallahassee, USA

  Stephanie Stahl

Policies and ethics