Today, virtually all computers are parallel systems with multiple processors. To efficiently use such a system it is crucial to carefully map and schedule the tasks of a program onto the processors. This is a very hard optimisation problem and can be described as a Mixed Integer Linear Program (MILP). Despite extensive research, only small instances can be computed optimally by modern solvers today.
Delayed Column Generation is an algorithm that has been successfully deployed for large MILP in other domains. The advantage is that not all possibilities need to be enumerated. One starts with a smaller problem and only brings in new variables as needed. In practise this can be significantly faster than directly solving the original MILP. In this project you will be investigating the modelling and implementation of the task scheduling problem with a Column Generation algorithm.
Students will benefit fromfamiliarity with Linear Programming and solvers, e.g. CPLEX or Gruobi
Undergraduate
None
No lab has been assigned to this project