totally unimodular

The Impact of Symmetry Handling for the Stable Set Problem via Schreier-Sims Cuts

  • Christopher Hojny
  • Marc E. Pfetsch
  • José Verschae
    • Categories Integer Programming Tags , , ,

    Symmetry handling inequalities (SHIs) are an appealing and popular tool for handling symmetries in integer programming. Despite their practical application, little is known about their interaction with optimization problems. This article focuses on Schreier-Sims (SST) cuts, a recently introduced family of SHIs, and investigate their impact on the computational and polyhedral complexity of optimization problems. … Read more

    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