Plenary Talk - Decomposition approaches for a large-scale scheduling problem

Elina Rönnberg
Linköping University, Sweden

Abstract:
Generic state-of-the-art solvers for discrete optimisation are exceptionally powerful tools that efficiently solve a variety of problems. However, the scale and complexity of practically relevant problems can sometimes render these solvers incapable of even finding feasible solutions. In such cases, one possibility is to develop solution approaches that exploit problem structure to decompose the problem and then use the generic solvers for addressing the resulting subproblems. The success of such approaches relies on that the subproblems can be efficiently solved and that the information gained from that is sufficient to solve the original problem.

In an industry-academia collaboration between Linköping University and Saab Aeronautics, we address the scheduling of a kind of electronic systems in future aircraft. Briefly, this problem can be described as a rich multiprocessor scheduling problem that also includes the scheduling of a communication network. To find feasible solutions to practically relevant instances of this problem is challenging.

In this talk, I will present two different ways of decomposing the problem. The first relies on making a strong relaxation of the problem and then applying a constraint generation procedure. In this approach, both the relaxed problem and the subproblem are solved by a mixed-integer programming solver. The performance of the method is enhanced by an integration with adaptive large neighbourhood search. The second decomposition strategy is part of ongoing work and is based on logic-based Benders decomposition. In this case, the master problem is solved as a mixed-integer program and the subproblem is formulated as a constraint program. The computational results from the former approach will be compared with some preliminary results from the latter. To conclude the talk, the different ways of exploiting the problem structure and efficiency of solvers will be discussed and we will compare the properties of the resulting decomposition approaches.