本论文于2020年发表于知名期刊 INFORMS Journal on Computing 上。
1. 问题背景
Unit Commitment (UC) 是指对发电机组进行调度的一大类优化问题。在计划周期内的每个小时，决策者需要决定哪些单元应该运行以及它们应该产生多大的电力。每个单元通常具有最小和最大的功率输出、二次生产成本曲线以及固定的启动和关闭成本。其他的一些约束可能包括斜坡速率，限制每小时发电量的剧烈变化，以及最小启动和最小下降约束，以防止机组过于频繁地启动和关闭。
而SCUC问题是UC的一个子问题。除了在前面所提到的约束外，SCUC在此基础上加入了强制每条运输线中的电流不能超过其安全限制的约束，以保证功率的可交付性。
为了保证在组件发生故障时仍然具有足够的安全裕度，该问题不仅考虑了正常工作条件下的传输约束，还考虑了系统中存在传输线故障时的传输约束。这样，即使输电线路意外发生故障并且网络中的潮流发生变化，也不会违反输电线路的热限制。这同时也是北美电力可靠性公司的强制要求。
2. 问题模型
考虑一个由$B$条总线，$G$台发电机和$L$条输电线路组成的电力系统。设定$T$为计划周期内的小时集合。对于每个发电机$g \in G$和小时$t \in T$，令$x_{gt}$为指示发电机是否运行的二元决策变量，$y_{gt}$为表示所产生的电量的连续决策变量。
因此，我们的问题可以表述为：
\[\begin{align} {\rm minimize} & \sum_{g\in{G}}C_g(x_{g,\cdot}, y_{g, \cdot}) \\ {\rm subject \ to \ } & (x_{g,\cdot}, y_{g, \cdot}) \in \mathcal{G}_g, \forall g \in G \\ & \sum_{g \in G}y_{gt}=\sum_{b\in B}d_{bt},\forall b\in B, t\in T \\ & -F_l^0\leq\sum_{b\in B}\delta_{lb}^0\left(\sum_{g\in G_b} y_{gt} - d_{bt}\right) \leq F_l^0,\forall l\in L,t\in T \\ & -F_l^c\leq\sum_{b\in B}\delta_{lb}^c\left(\sum_{g\in G_b} y_{gt} - d_{bt}\right) \leq F_l^c,\forall l\in L,t\in T \\ & x_{gt} \in \{0, 1\}, \forall g \in G, t \in T \\ & y_{gt} \geq 0, \forall g \in G, t \in T \end{align}\]在目标函数(1)中，$c_g$为一个分段线性函数，包含了发电机$g$的启动、关闭和运行成本。而$(x_{g,\cdot},y_{g,\cdot})$则是向量$(x_{gt_1,\cdots,x_{gt_k},y_{gt_1},\cdots,y_{gt_k}})$的缩写，此处${t_1,\cdots,t_k}=T$。
约束(2)对每个小时启动的发电机数量、功率进行了限制，包括了生产限制、最小启动数量、最大启动数量、斜坡速率等等。
约束(3)强制要求产生的总电量等于每条总线的需求$d_{bt}$总和。
约束(4)保障在正常系统条件下电力的可交付性。集合$G_b$表示与总线$b$相连的发电机集合。
约束(5)保障在某个场景下线路c发生停电的情况下电力的可交付性。
约束(4)、(5)对SCUC的求解具有显著的影响。这一类约束的总数和输电线路的数量呈二次关系。由于大型电力系统可以拥有超过10,000条线路，因此约束总数很容易超出上亿条。更糟糕的是，这些约束通常非常密集，这使得将它们全部添加到模型中对于大规模实例来说是不切实际的，这不仅是因为MIP的性能下降，对内存的要求也是难以满足的。幸运的是，已经有文献发现仅满足这些约束中的一小部分就可以保证自动满足所有剩余的约束。而如何去识别约束的这个关键子集非常具有挑战性。
3. 学习策略
假设SCUC问题中的每个实例$I(p)$完全由实值向量$p$描述。这些参数仅包括市场经营者在市场清算过程发生前一天不知道的数据。例如，它们可能包括峰值系统需求和每台发电机的运行成本。在这项工作中，作者假定网络拓扑和发电机总数是可以提前知道的，因此不需要通过参数对它们进行编码。
给定训练实例$I(p^1),\cdots,I(p^s)$，这些实例和我们目前期望解决的实例相类似，可以直接来自于历史真实数据，也可以通过对$p$的概率分布进行采样来人工生成。了解这种分布并不是一个不合理的假设，因为市场运营商多年来一直在每天解决SCUC，并且拥有大量可以轻松分析的累积数据。
在市场清算的前一天，我们进行训练的过程（train phase）。在这个过程中，我们的任务是构建预测函数$\phi$，将每一个可能的参数$p\in R^n$映射到一个提示向量。为了构建这个函数，我们对训练实例$I(p^1),\cdots,I(p^s)$进行解决。
在实际的市场清算中，当我们面临解决新的问题的时间压力时，开始第二个过程——测试（test phase）。在这个过程中，给定一个参数向量$\hat{p}$，构建实例$I(\hat{p})$，我们的目标就是尽快解决$I(\hat{p})$。为了实现这个目标，我们首先计算提示向量$\phi(\hat{p})$，然后将$(I(\hat{p}), \phi(\hat{p}))$嵌入求解器中。
这里的一个假设是：作者使用了定制的MIP求解器，除了需要求解的实例$I(\hat{p})$外，它还可以接收提示向量来改善求解时间。提示向量中可能包括热启动列表、应固定的变量列表、要强制执行的初始约束等等。
在下文中，作者提出了三种不同的ML模型，针对解决SCUC中的不同挑战。第一个模型的重点是预测违反约束的传输和N-1安全约束。第二个模型侧重于产生初始可行解，作为热启动。第三个模型旨在预测解可能位于仿射子空间。
3.1 学习违反传输约束
如第2节中所提到的，解决SCUC时最复杂的因素之一在处理需要强制执行的大量传输和安全约束。而此处的第一个模型旨在预测哪些传输约束最初应该添加到松弛中，哪些约束可以安全地省略。
回到约束中，
\[-F_l^c\leq\sum_{b\in B}\delta_{lb}^c\left(\sum_{g\in G_b} y_{gt} - d_{bt}\right) \leq F_l^c,\forall l\in L,t\in T\]我们假定定制的MIP求解器收到的提示向量为
\[h_{l,c,t} \in \{ ENFORCE, RELAX\}, \forall l \in L, c \in L \cup \{0\}, t \in T\]提示向量中给出了在应急场景$c$，时段$t$中传输线$l$的热限制是否可能在最优解中仍然有效（binding）。
在该算法中，第一次迭代中我们只保留提示向量中的传输约束。而在之后的迭代内，同baseline方法一样，不断添加违反约束的小子集，直到没有发现进一步的违反。如果提示向量能够预测成功，那么算法收敛只需要一次迭代，否则则需要额外的迭代，但总是可以返回一个正确的解决方案的。预测器的误报率决定了迭代的次数。
对于这样的预测任务，我们基于KNN提出了一个简单的学习策略。假设$p^1,\cdots,p^s$为训练参数。在训练过程中，我们利用Algorithm 1解决实例$I(p^1),\cdots,I(p^s)$，此时初始的指示向量对所有的约束都设置为RELAX。在求解每一个训练算例$I(p^i)$的过程中，我们记录在迭代中加入relaxation的约束集合$\mathcal{\Phi}^i\subset L \times(L \cup {0}) \times T$。在测试的过程中，给定参数$\hat{p}$，预测器找到$k$个向量$p^{i_1},\cdots,p^{i_k}$使用KNN法。
3.2 学习热启动
另一个解决大规模SCUC问题实例的挑战在于获取高质量的初始可行解。在这节中，我们的目标在于，基于大量先前的最优解决方案，产生一个（部分）解决方案，作为warm start。
对于这样的预测任务，再一次使用了基于kNN的学习策略。假设$p^1,\cdots,p^s$为训练参数，$(x^1,y^1),\cdots,(x^s,y^s)$为它们的最优解。原则上，$(x^1,y^1),\cdots,(x^s,y^s)$可以直接作为warm start提供给求解器，但是实际上在进行每一个解的处理时需要耗费大量的时间。因此，在这里通过KNN的方法构建单个（部分，可能不可行）的解交给求解器“修复”。
这个想法源自于我们可以只设置具有高置信度的变量值，而对于低置信度的变量值，我们交给求解器进行求解。为了最大限度的提升这一方案的可用性，在这里我们只专注于设置0-1变量$x$的值，所有连续变量$y$的值交给求解器求解。
给定测试参数$\hat{p}$，首先我们找到$k$个最近的训练实例$I(p^{i_1}),\cdots,I(p^{i_k})$对应的最优解$(x^{i_1},y^{i_1}),\cdots,(x^{i_k},y^{i_k})$。然后，对于每个变量$x_{gt}$，我们计算平均数$\overline{x_{gt}} = \frac{1}{k}\sum_{j=1}^kx_{gt}^{i_j}$。如果$\overline{x_{gt}}>p,p\in [0.5, 1.0]$，我们就将$\overline{x_{gt}}$设置为1；如果$\overline{x_{gt}}<1-p,p\in [0.5, 1.0]$，我们就将$\overline{x_{gt}}$设置为0。
3.3 学习仿射子空间
在实际经验中，市场经营者自然而然地在自己的电力系统的最优解决方案中学习到了一些模式。例如，他们知道某些发电机组（称为基本机组）几乎肯定会全天投入使用，而其他机组（称为峰值机组）通常仅在高峰需求期间上线。但当SCUC被转化为数学问题的时候，这些直观的模式往往会被丢失。
鉴于特定电力系统的固定特性和实际参数分布，可以尝试将新的约束添加到SCUC的MIP模型当中，以限制其解空间，而不影响最优解集。因此，在本节，我们开发了一个ML模型，用于根据统计数据自动查找此类约束。
令$\hat{p}$为参数变量，我们的目标是能够构建模型对超平面$(h^1,h_0^1),\cdots,(h^k,h_0^k)$进行预测，使得$I(\hat{p})$的最优解$(x,y)$满足$<h^i,x>=h_0^i,\forall i = 1,\cdots,k$。在该工作中，我们限制超平面的形式为：
\[x_{gt} = 0 \\ x_{gt} = 1 \\ x_{gt} = x_{g,t+1}\]也就是说，预测器尝试去决定每个变量$x_{gt}$是应该等于0还是1，或者等于下一个时段的变量$x_{g,t+1}$。为了防止冲突，每个变量至多选择超平面中的某一个形式。
在指示向量中，我们提前构建好所有超平面，然后在训练过程中去将每个超平面映射到一个预测函数${ADD,SKIP}$来决定是否应该加入这个超平面。
References
Xavier, Álinson S., Feng Qiu, and Shabbir Ahmed. “Learning to solve large-scale security-constrained unit commitment problems.” INFORMS Journal on Computing 33.2 (2021): 739-756.