perfect graph

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

    Energy-Efficient Timetabling in a German Underground System

  • Andreas Bärmann
  • Maximilian Merkert
  • Patrick Gemander
  • Alexander Martin
  • Frederik Nöth
    • Categories Graphs and Matroids, Polyhedra, Scheduling Tags , , , ,

    Timetabling of railway traffic and other modes of transport is among the most prominent applications of discrete optimization in practice. However, it has only been recently that the connection between timetabling and energy consumption has been studied more extensively. In our joint project VAG Verkehrs-Aktiengesellschaft, the transit authority and operator of underground transport in the … Read more

    The Clique Problem with Multiple-Choice Constraints under a Cycle-Free Dependency Graph

  • Andreas Bärmann
  • Maximilian Merkert
  • Patrick Gemander
    • Categories Graphs and Matroids, Polyhedra, Scheduling Tags , , , ,

    The clique problem with multiple-choice constraints (CPMC) represents a very common substructure in many real-world applications, for example scheduling problems with precedence constraints. It consists in finding a clique in a graph whose nodes are partitioned into subsets, such that exactly one node from each subset is chosen. Even though we can show that (CPMC) … Read more