totally unimodular

Schreier-Sims Cuts meet Stable Set: Preserving Problem Structure when Handling Symmetries

  • Christopher Hojny
  • Marc E. Pfetsch
  • José Verschae
    • Categories 0-1 Programming Tags , ,

    Symmetry handling inequalities (SHIs) are a popular tool to handle symmetries in integer programming. Despite their successful application in practice, only little is known about the interaction of SHIs with optimization problems. In this article, we focus on SST cuts, an attractive class of SHIs, and investigate their computational and polyhedral consequences for optimization problems. … Read more

    A Strongly Polynomial Simplex Method for Totally Unimodular LP

  • Shinji Mizuno
    • Categories Linear Programming Tags , , ,

    Kitahara and Mizuno get new bounds for the number of distinct solutions generated by the simplex method for linear programming (LP). In this paper, we combine results of Kitahara and Mizuno and Tardos’s strongly polynomial algorithm, and propose an algorithm for solving a standard form LP problem. The algorithm solves polynomial number of artificial LP … Read more