Prachi Shah

Lower bound on size of branch-and-bound trees for solving lot-sizing problem

  • Santanu S. Dey
  • Prachi Shah
    • Categories 0-1 Programming, Integer Programming Tags , ,

    We show that there exists a family of instances of the lot-sizing problem, such that any branch-and-bound tree that solves them requires an exponential number of nodes, even in the case when the branchings are performed on general split disjunctions. ArticleDownload View PDF

    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