The importance of Relaxations and Benders Cuts in Decomposition Techniques: Two Case Studies - Abstract


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.





Quick Links
 Last updated Mar. 21, 2004