When solving combinatorial optimization problems it can happen that using a single technique is not efficient enough. In this case, simplifying assumptions can transform a huge
and hard to solve problem in a manageable one, but they can widen the gap between the real world and the model. Heuristic approaches can quickly lead to solutions that can be far from
optimality. For some problems, that show a particular structure, it is possible to use decomposition techniques that produce manageable subproblems and solve them with different
approaches. Benders Decomposition is one of such approaches applicable to Integer Linear Programming. The subproblem should be a Linear Problem. This restriction has been relaxed in where the technique has been extended to solvers of any kind and called
Logic-Based Benders Decomposition (LBBD). The general technique is to find a solution to the first problem (called Master Problem (MP)) and than search for a solution to the second problem
(Sub-problem (SP)) constraining it to comply with the solution found by the MP. The two solvers are interleaved and they converge to the optimal solution (if any) for the problem overall. When
solving problems with a Benders Decomposition based technique, a number of project choices arises: at design level, the objective function (OF) depends either on MP or SP variables, or
both. This choice affects the way the two solvers interact. Generation of Benders Cuts; Benders Cuts are constraints, added to the MP model once a SP as been solved, that remove some solutions. Relaxation of the SP; to avoid the generation of trivially infeasible MP solutions, some relaxations of the SP should be added to the MP model.
We focus on two particular problems, the allocation and scheduling problem on Multi-Processor System-on-Chip (MPSoC) platforms (ASP), and the dynamic voltage scaling problem on energy-aware MPSoC (DVSP). These are very hard problems and they have never been solved to optimality by
the system design community. We used LBBD to solve the problems. The aim of this paper is to show the importance of the relaxations and Benders Cuts in terms of
their impact on the search time and on the number of times the two solvers iterate. In addition, we claim that, in general, a tradeoff between the complexity of the cuts and relaxations introduced and their impact on the number of iterations must be found.
