We study pessimistic bilevel optimization with bilinear objectives and linear constraints. Assuming a compact polyhedral leader domain, nonempty follower solution sets, and a finite pessimistic infimum, we derive mixed-integer linear optimization formulations that attain this infimum, even when the original problem has no optimal solution. This setting has applications such as pricing, security and decision-focused learning.
The construction combines LP duality, support selection, and homogeneous witnesses, together with a KKT reformulation for leader-dependent follower constraints. Optimal reformulation solutions yield explicit leader decisions with pessimistic objective values arbitrarily close to the infimum. For rational data, all formulations have polynomial encoding length, also showing that the problem is NP-complete.