strong branching

A Theoretical and Computational Analysis of Full Strong-Branching

  • Santanu S. Dey
  • Yatharth Dubey
  • Marco Molinaro
  • Prachi Shah
    • Categories Branch and Cut Algorithms, Integer Programming Tags , , ,

    Full strong-branching (henceforth referred to as strong-branching) is a well-known variable selection rule that is known experimentally to produce significantly smaller branch-and-bound trees in comparison to all other known variable selection rules. In this paper, we attempt an analysis of the performance of the strong-branching rule both from a theoretical and a computational perspective. On … Read more

    An improved algorithm for computing Steiner minimal trees in Euclidean d-space

  • Kurt M. Anstreicher
  • Marcia Fampa
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Tags , , ,

    We describe improvements to Smith’s branch-and-bound (B&B) algorithm for the Euclidean Steiner problem in R^d. Nodes in the B&B tree correspond to full Steiner topologies associated with a subset of the terminal nodes, and branching is accomplished by “merging” a new terminal node with each edge in the current Steiner tree. For a given topology … Read more