10
$\begingroup$

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.

|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mark L. Stone Jun 18 '19 at 10:22
  • 5
    $\begingroup$ 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. $\endgroup$ – Matteo Fischetti Jun 18 '19 at 12:23
  • $\begingroup$ Mertcan, is @MatteoFischetti's understanding correct? If so, he might be able to post an answer. $\endgroup$ – LarrySnyder610♦ Jun 24 '19 at 2:29
  • $\begingroup$ Or @MarkL.Stone's? $\endgroup$ – LarrySnyder610♦ Jun 24 '19 at 2:31
  • $\begingroup$ @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. $\endgroup$ – Mertcan Yetkin Jun 25 '19 at 18:08
4
$\begingroup$

Well, as @Matteo Fischetti has said in the comments to your question, your case of multiple "easy" secondary level problems is definitely more tractible than multiple levels. Even in a continuous linear case, you go one level higher in the polynomial hierarchy as you increase the number of levels [1].

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!

So you can regard having numerous trivial subproblems as having numerous binary variables.

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 \} $$

References

[1] Jeroslow, R. G. (1985). The polynomial hierarchy and a simple model for competitive analysis. Mathematical Programming, 32(2), 146–164.

|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.