在雙層編程中是否可能(或直接)定義許多次要問題?


10

我是雙層編程的新手。我想知道是否有可能(或直接)提出一個存在許多次級問題的雙水平問題?

一個例子可能是一種攻擊者—防御者問題,其中有多個同時攻擊者針對單個防御者,反之亦然。讓我們假設每個攻擊者都可以在不同的區域(獨立於其他攻擊者)進行攻擊,但是防御者必須制定一種策略來防御所有人。

在模型中,我想利用以下事實:次要問題可以分解為許多子問題,因此各個問題都非常容易解決,但是存在許多子問題。

4

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.