perfect graph

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