Lecture07：双层规划⽅法
⽬录
本系列已发表⽂章列表：
参考书籍：
1. Gabriel, S. A., Conejo, A. J., Fuller, J. D., Hobbs, B. F., & Ruiz, C. (2012). Complementarity modeling in energy
markets (Vol. 180). Springer Science & Business Media.
2. Dempe, S. (2018). Bilevel optimization: theory, algorithms and applications (Vol. 3). TU Bergakademie Freiberg,
Fakultät für Mathematik und Informatik.
3. Luo, Z. Q., Pang, J. S., & Ralph, D. (1996). Mathematical programs with equilibrium constraints. Cambridge
University Press.
4. Pozo, D., Sauma, E., & Contreras, J. (2017). Basic theoretical foundations and insights on bilevel models and their
applications to power systems. Annals of Operations Rearch, 254(1), 303-334.网段
1 双层规划模型
1.1 ⼀个简单的例⼦
现在有两个玩家，称为领导者和跟随者，追随者的反应会影响领导者，领导者会预测追随者的反应。
因为追随者是看到领导者的⾏为之后，⾃⼰才⾏动，因此我们可以将联系约束，放到追随者的优化问题中。于是有：
这⾥，x和y 是领导者的决策变量，但x在追随者的优化中是参数。所以，双层规划模型是，⼀个优化问题受制于另⼀个优化问题的模型。
1.2 斯坦克尔伯格模型到双层规划模型
⼀般定义：
规划过程分为两层：上层规划是领导者的优化问题，下层规划是跟随者的优化问题。
上层规划受制于下层规划，也就是说下层规划问题本⾝是作为上层规划问题的约束存在的。
如果⼀部分跟随者同时是另⼀部分追随者的领导者，我们将可以建⽴起三层规划问题。
2 求解双层规划
2.1 Mathematical Program with Complementarity Constraint (MPCC)
下层问题被使⽤KKT条件替换，从⽽导致双层规划问题变为⼀个单⽬标优化程序。此外，在⼀些案例中，下层问题将被转化为均衡问题，此时⽅法称为Mathematical Program with Equilibrium Constraint (MPEC).
2.2 互补条件的线性化
2.2.1 Fortuny‐Amat (“Big‐M”) approach
智永退笔冢Fortuny-Amat, J., & McCarl, B. (1981). A reprentation and economic interpretation of a two-level programming problem. Journal of the operational Rearch Society, 32(9), 783-792.
使⽤⼤M求解问题后，应该检查⼀下原始互补问题是否成⽴。
注意事项：
1. 选择⽽是⽤⼤M⽅法应该谨慎，因为选择合适的⼤M值，是⼀件有挑战性的事情；如果选错了，可
能导致次优解或病态条件。
更多的细节参见：
1. Pineda, S., & Morales, J. M. (2019). Solving linear bilevel problems using big-Ms: not all that glitters is gold. IEEE
Transactions on Power Systems, 34(3), 2469-2471.
2. Kleinert, T., Labbé, M., Plein, F. A., & Schmidt, M. (2020). There’s no free lunch: on the hardness of choosing a
广之旅旅行社
correct big-M in bilevel optimization. Operations rearch, 68(6), 1716-1721.
3 策略提供问题（Strategic offering problem）
3.1 问题描述与模型
问题描述
1. Let’s consider a strategic power producer owning multiple generation units, indexed by i
2. All generation units belonging to rivals are indexed by –i
苫蔽成丘3. Demands are elastic to price, and indexed by k
4. No transmission network, unit commitment constraints, and uncertainty (for simplicity)
数学模型：切特
策略制定者是领导者，他的⽬标是最⼤化收益；于是有：
注解：
1. 供给价格在上层模型是变量，在下层模型是参数
2. 下层模型的所有原始和对偶变量是上层模型的变量
3.2 ⽣成下层问题的KKT条件
从⽽我们得到MPEC公式如下：
显然这是⼀个⾮线性问题，因为模型中包含互补条件约束。
腊肉的腌制方法
3.3 线性化互补条件
雷锋图片
引⼊辅助变量，将问题中的互补条件约束进⾏线性化，则有：
我们得到的仍是⼀个⾮线性混合整数规划，即 项，⽬前没有现成的求解器去处理它。我们通常想把它转换为混合整数线性规划或者⾮线性规划。
3.4 模型处理
清炒茭白
最终，我们将问题转化为混合整数线性规划问题：
