An algorithm to find stable solutions in linear–linear bilevel problems

Bilevel programming is widely used to model applications with two hierarchical decisions defining, respectively, an upper-level (leader) problem and a lower-level (follower) problem nested in the former. In this scenario, the stability of the solution is one of the main issues to address to have a well-posed optimization problem; indeed, the lower-level problem may admit more than one optimal solution generating uncertainty on what the real upper-level objective value will be (instability of the bilevel problem). Notwithstanding the importance of stability, the literature has concentrated the most on defining hypotheses and conditions warranting stability of bilevel problems rather than on algorithms able to find a stable solution to the latter. To give a contribution in this direction, in this paper, we define an algorithm capable of finding a stable solution in bilevel optimization problems. We restrict our analysis to the case in which both the leader and the follower problems are linear-continuous. The proposal starts with finding the optimistic solution of the single-level problem obtained by replacing the follower’s problem with its Karush–Kuhn–Tucker conditions, and the corresponding pessimistic solution. In the presence of instability, the algorithm removes one of the follower constraints at a time producing additional constraints for the leader problem in the attempt to define a new stable bilevel problem. Experimental results show that the algorithm can produce stable bilevel solutions representing an effective trade-off between the optimistic and the pessimistic solution values. The proposed algorithm may represent an effective tool for decision-makers aiming at finding robust solutions to bilevel problems.