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. Article Download View Lower bound on size of branch-and-bound trees for solving lot-sizing problem

    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