An EMO algorithm combined with benders decomposition to optimizing a mixed-integer linear optimization over an efficient set

Abstract

In this work we analyze the problem of optimizing a linear function with mixed-integer variables over the efficient set of a linear multiobjective lower level problem. A new algorithm is proposed based on combining Benders Decomposition (BD) [1] and the EMO approach proposed in [3]. On the one hand, BD is a popular method to solve mixed-integer single-objective problems by projecting out some of the variables of the problem. Integrating BD into an extension of the approach proposed in [2] for pure integer problems allows us to derive an exact (but computationally costly) approach. With the goals of reducing the resolution CPU times and being able to solve larger instances, we combine the above approach with an evolutionary multiobjective optimization (EMO) algorithms in the resolution of the subproblem. Concretely, the EMO algorithm is applied to construct efficiently the approximated Pareto frontier of the linear multiobjective problem. As the dual approach will subsequently use, the decomposition-based EMO algorithm called WASF-GA [3] (Weighting Achievement Scalarizing Function Genetic Algorithm) is introduced into the process with the aim to transform the secondary problem into a set of single-objective linear subproblems. These solutions allow us to derive optimality and feasibility cuts for the BD approach. The methodology is applied to a classical facility location problem in order to test it computationally.