Globally Optimal Clusterwise Regression By Column Generation Enhanced with Heuristics, Sequencing and Ending Subset Optimization

Carbonneau, RĂ©al; Caporossi, Gilles; Hansen, Pierre
July 2014
Journal of Classification;Jul2014, Vol. 31 Issue 2, p219
Academic Journal
A column generation based approach is proposed for solving the cluster-wise regression problem. The proposed strategy relies firstly on several efficient heuristic strategies to insert columns into the restricted master problem. If these heuristics fail to identify an improving column, an exhaustive search is performed starting with incrementally larger ending subsets, all the while iteratively performing heuristic optimization to ensure a proper balance of exact and heuristic optimization. Additionally, observations are sequenced by their dual variables and by their inclusion in joint pair branching rules. The proposed strategy is shown to outperform the best known alternative (BBHSE) when the number of clusters is greater than three. Additionally, the current work further demonstrates and expands the successful use of the new paradigm of using incrementally larger ending subsets to strengthen the lower bounds of a branch and bound search as pioneered by Brusco's Repetitive Branch and Bound Algorithm (RBBA).


Related Articles

  • STACK PRE-MARSHALLING PROBLEM: A HEURISTIC-GUIDED BRANCH-AND-BOUND ALGORITHM. Ruiyou Zhang; Zhong-Zhong Jiang; Won Young Yun // International Journal of Industrial Engineering;2015, Vol. 22 Issue 5, p509 

    The stack pre-marshalling (SPM) problem is a complex combinatorial optimization problem which arises mainly within the field of container logistics. This paper presents a heuristic-guided branch-and-bound (HGB&B) algorithm which can effectively be used to solve the SPM problem. The HGB&B...

  • Development of an Innovative Algorithm for the Traveling Salesman Problem (TSP). Froushani, Mahshid Abtahi; Yusuff, Rosnah Mohd. // European Journal of Scientific Research;Apr2009, Vol. 29 Issue 3, p349 

    A large number of real-world planning problems called combinatorial optimization problems share the following properties: They are optimization problems, are easy to state, and have a finite but usually very large number of feasible solutions. Branch and Bound (B&B) is by far the most widely...

  • A branch-and-bound algorithm for fitting anti-robinson structures to symmetric dissimilarity matrices. BRUSCO, MICHAEL J. // Psychometrika;Sep2002, Vol. 67 Issue 3, p459 

    The seriation of proximity matrices is an important problem in combinatorial data analysis and can be conducted using a variety of objective criteria. Some of the most popular criteria for evaluating an ordering of objects are based on (anti-) Robinson forms, which reflect the pattern of...

  • Scheduling Algorithms for the Maximal Total Revenue on a Single Processor with Starting Time Penalty. Un Gi Joo // Management Science & Financial Engineering;May2012, Vol. 18 Issue 1, p13 

    This paper considers a revenue maximization problem on a single processor. Each job is identified as its processing time, initial reward, reward decreasing rate, and preferred start time. If the processor starts a job at time zero, revenue of the job is its initial reward. However, the revenue...

  • bNEAT: a Bayesian network method for detecting epistatic interactions in genome-wide association studies. Bing Han; Xue-wen Chen // BMC Genomics;2011 Supplement 2, Vol. 12 Issue Suppl 2, p1 

    Background: Detecting epistatic interactions plays a significant role in improving pathogenesis, prevention, diagnosis and treatment of complex human diseases. A recent study in automatic detection of epistatic interactions shows that Markov Blanket-based methods are capable of finding genetic...

  • An efficient combined DCA and B&B using DC/SDP relaxation for globally solving binary quadratic programs. Pham Dinh, Tao; Nguyen Canh, Nam; Le Thi, Hoai // Journal of Global Optimization;Dec2010, Vol. 48 Issue 4, p595 

    This paper addresses a new continuous approach based on the DC (Difference of Convex functions) programming and DC algorithms (DCA) to Binary quadratic programs (BQP) which play a key role in combinatorial optimization. DCA is completely different from other avalaible methods and featured by...

  • A Multiobjective Branch-and-Bound Framework: Application to the Biobjective Spanning Tree Problem. Sourd, Francis; Spanjaard, Olivier // INFORMS Journal on Computing;Summer2008, Vol. 20 Issue 3, p472 

    This paper focuses on a multiobjective derivation of branch-and-bound procedures. Such a procedure aims to provide the set of Pareto-optimal solutions of a multiobjective combinatorial optimization problem. Unlike previous works on this issue, the bounding is performed here via a set of points...

  • A branch-and-bound algorithm for hard multiple knapsack problems. Fukunaga, Alex // Annals of Operations Research;Apr2011, Vol. 184 Issue 1, p97 

    The multiple knapsack problem (MKP) is a classical combinatorial optimization problem. A recent algorithm for some classes of the MKP is bin-completion, a bin-oriented, branch-and-bound algorithm. In this paper, we propose path-symmetry and path-dominance criteria for pruning nodes in the MKP...

  • A heterogeneous cooperative parallel search of branch-and-bound method and tabu search algorithm. Yi-Feng Hung; Wei-Chih Chen // Journal of Global Optimization;Sep2011, Vol. 51 Issue 1, p133 

    In this study, we present a heterogeneous cooperative parallel search that integrates branch-and-bound method and tabu search algorithm. These two algorithms perform searches in parallel and cooperate by asynchronously exchanging information about the best solutions found and new initial...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics