clique problem with multiple-choice constraints

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

    Staircase Compatibility and its Applications in Scheduling and Piecewise Linearization

  • Andreas Bärmann
  • Maximilian Merkert
  • Thorsten Gellermann
  • Oskar Schneider
    • Categories (Mixed) Integer Linear Programming, Polyhedra, Scheduling Tags , , , ,

    We consider the clique problem with multiple-choice constraints (CPMC) and characterize a case where it is possible to give an efficient description of the convex hull of its feasible solutions. This new special case, which we call staircase compatibility, generalizes common properties in several applications and allows for a linear description of the integer feasible … Read more