A Practical Scheme to Compute the Pessimistic Bilevel Optimization Problem

In this paper, we present a new computation scheme for the pessimistic bilevel optimization problem, which so far does not have any computational methods generally applicable. We first develop a tight relaxation and then design a simple scheme to ensure a feasible and optimal solution. Then we discuss using this scheme to analyze and compute a linear pessimistic bilevel problem and several extensions. We also provide demonstrations on illustrative examples and a systematic numerical study on instances of two practical problems. Because of its simple structure and strong computational capacity, we believe that the developed scheme is of critical value in studying and solving pessimistic bilevel optimization problems arising from practice.