A new exact method for linear bilevel problems with multiple objective functions at the lower level

Abstract

In this paper we consider linear bilevel programming problems with multiple objective functions at the lower level. We propose a general-purpose exact method to compute the optimistic optimal solution, which is based on the search of efficient extreme solutions of an associated multiobjective linear problem with many objective functions. We also explore a heuristic procedure relying on the same principles. Although this procedure cannot ensure the global optimal solution but just a local optimum, it has shown to be quite effective in problems where the global optimum is difficult to obtain within a reasonable timeframe. A computational study is presented to evaluate the performance of the exact method and the heuristic procedure, comparing them with an exact and an approximate method proposed by other authors, using randomly generated instances. Our approach reveals interesting results in problems with few upper-level variables.