# Is it possible (or straightforward) to define many secondary problems in bilevel programming?

I am new to bilevel programming. I was wondering whether it is possible (or straightforward) to formulate a bilevel problem in which there are many secondary-level problems?

An example might be a type of attacker-defender problem where there are multiple simultaneous attackers against a single defender, or vice-versa. Let us assume that each attacker can attack in a different region (independent of the other attackers) but the defender has to have a strategy to defend against them all.

In the model, I would like to leverage the fact that the secondary problem can decompose into many subproblems such that the problems individually are quite easy to solve, but there are numerous subproblems.

• You have one outer (upper level) problem, which has several independent (non-overlapping variables) inner (lower level) problems? So overall problem can be formulated as outer problem with KKT conditions for each inner problem, presuming KKT conditions apply? So several complementarity conditions in the overall problem formulation. – Mark L. Stone Jun 18 '19 at 10:22
• If I understand correctly, you have in fact a single secondary-level problem, whose solution is simplified by the fact that it decomposes into multiple independent subproblems. In other words, you don’t have a hierarchy (chain) of subproblems—that would lead to much more complicated multilevel problems. – Matteo Fischetti Jun 18 '19 at 12:23
• Mertcan, is @MatteoFischetti's understanding correct? If so, he might be able to post an answer. – LarrySnyder610 Jun 24 '19 at 2:29
• Or @MarkL.Stone's? – LarrySnyder610 Jun 24 '19 at 2:31
• @MatteoFischetti That is correct. Basically, I would like to leverage this property where I have many independent problems with each of them being simple to solve. – Mertcan Yetkin Jun 25 '19 at 18:08

But having multiple "easy" problems is not a complete triviality either. For example, $$Ax \leq b \\ 0\leq x \leq 1\\ y \geq 0\\ y_i \in \arg\min_y \{ y: y \geq -x_i; y \geq x_i -1 \} \} \quad i=1,\dots,n$$ This has $$n$$ simple bilevel constraints. Each program is trivial enough to have a closed form solution, $$y_i = \max \{x_i-1, -x_i\}$$! This along with the requirement $$y\geq 0$$ enforces that $$x\in\{0,1\}$$. In other words, we have re-written a binary program this way asking for one "trivial" bilevel constraint in the lifted space for each binary variable!
That said, it is also fair to have numerous such bilevel constraints - they can be rewritten as a single one. In our case as $$(y_1, \dots, y_n) \in \arg\min_y \left \{ \sum_{i=1}^n y_i: y_i \geq -x_i; y_i \geq x_i -1 \quad i=1,\dots,n \right \}$$