二次约束下覆盖问题的可近似性

《European Journal of Operational Research》：On the approximability of covering problem under a quadratic constraint

　　

• 研究了一个二元二次约束线性规划问题。• 针对常秩正定半正定矩阵的 n-近似算法。• 针对常秩正定半正定矩阵的资源增强算法。• 针对 cp-秩为 2 的矩阵的 PTAS，改进了当前最佳结果 QPTAS。• 提供了数值实验以证明 PTAS 的有效性。引言经典的极小化背包问题广泛出现在各类应用中，其目标是在满足聚合重量不低于规定下界的前提下，寻找一个物品子集使得总成本最小。近期的应用，特别是在电力与能源调度领域，推动了背包问题变体的研究，其中物品重量被建模为复数而非实数，从而自然地引出了二次约束形式。我们将这类问题称为 Covering（覆盖问题），可表示为如下一般形式：(CQP) min_{x∈{0,1}^n} c^T x，s.t. x^T Q x ≥ B2，其中 c∈???，Q∈???? 是对称且正定半正定（PSD）的，B∈??，x=(x?,…,x?)^T 编码优化变量。1 特别地，我们进一步假设约束矩阵 Q 具有常秩 k。因此，Q 可分解为 Q = V V^T，其中 V 为某个 n×k 矩阵；相应地，约束 (2) 可表示为 Σ_{i=1}^k (q_i^T x)2 ≥ B2，其中 q_i 是 V 的第 i 列。此类分解可在 O(n3 + (n log2 n) log log 1/δ) 时间内找到，相对误差界为 δ（Pan & Chen, 1999）。一个重要的特殊情况是 Q 具有常完全正定秩（cp-rank）s，即它允许类似的分解，但 V 为非负矩阵（参见下文的定义 1）。尽管一般情况下计算这样的矩阵 V 是 NP-难的（Dickinson & Gijben, 2014），但当 Q 具有常 cp-rank 时，可在多项式时间 poly(L, n^{O(s2)}, log 1/δ) 内完成（相对误差界为 δ），其中 L 是输入的比特长度（K. Elbassioni & T.T. Nguyen, 2017）。因此，约束 (2) 可写为 s 个非负线性函数的平方和。本文的主要关注点是 s=2 的特殊情况。定义 1（Berman & Shaked-Monderer, 2003）对称的 PSD 矩阵 Q∈????? 是 cp-秩为 s 的完全正定矩阵，若 s 是使得存在矩阵 V∈????? 满足 Q = V V^T 的最小正整数。具有常秩二次约束的 Covering 问题最近出现在多个应用中，特别是在电力与能源调度领域（参见 Chau et al., 2016, Elbassioni et al., 2019 及 Klimm et al. (2022)）。我们简要回顾其中一些应用。例 1 气体供应网络中的福利最大化考虑一个由有向路径图 G=(V,E) 表示的气体管道网络，节点从左到右编号为 {0,…,k}。假设有 n 个运输请求 (s_j, t_j, q_j), j∈[n]?{1,…,n}，其中 s_j∈V 和 t_j∈V 分别表示入口和出口节点，q_j∈?_{≥0} 为待运输的天然气量。网络中的气流遵循 Weymouth 方程（Weymouth, 1912），其形式为 β_{ij} q_{ij} |q_{ij}| = π_i - π_j, ?(i,j)∈E。这里，q_{ij}∈? 是管道 (i,j) 上的流量；β_{ij}∈?_{>0} 是概括管道段物理特性的常数；π_i 表示节点 i∈V 处的平方压力。压差的符号决定气流方向。目标是在给定网络中平方压力最大差界的前提下，选择一组运输请求予以服务，其中最大差为 π_0 - π_k = Σ_{i=1}^k (π_{i-1} - π_i) = Σ_{i=1}^k β_{i-1,i} (Σ_{j∈[n]: (i-1,i)∈E_j} q_j x_j)2，其中 x_j∈{0,1} 表示是否选择运输请求 j∈[n]，E_j?E 表示 G 中唯一 (s_j, t_j)-路径所包含的边集。例 2 处理器频率调节中的任务选择考虑一个配备 k 个处理核心的移动设备。假设有 n 个任务，每个任务由工作量向量 q_j∈??? 刻画。计算从时间 0 开始，所有被选中的任务必须在时间 1 之前完成。为适应不同工作量，每个核心可以以不同处理速度运行。在频率调节框架下，通常假设核心 j 以速度 s 运行时消耗的能量与 β_j s2 成正比，其中 β_j>0 是核心 j 的特定参数（参见 Irani and Pruhs (2005) 及 Wierman et al. (2012)）。对于任何选定的任务子集，可以不失一般性地假设每个核心以恰好能在时间 1 完成所需的最低恒定速度运行。因此，核心 j 以速度 Σ_{i∈[n]} x_i q_{ji} 运行，其中 x_i∈{0,1} 表示是否选择任务 i。相应地，总能耗为 Σ_{j=1}^k β_j (Σ_{i∈[n]} x_i q_{ji})2。例 3 电力生产中的机组组合问题考虑一个简化的单时段机组组合问题，这是电力系统工程中的经典优化问题（Wood & Wollenberg, 2012）。该问题涉及调度 n 个发电机组，每个机组具有自身产能和运行成本，以在单个时段内满足固定且无弹性的电力需求 D。每个发电机组 i 可以开启或关闭，产生相关成本 λ_i^on/λ_i^off。当机组启动时，它产生一定量复功率，表示为 p_i^R + i·p_i^I（其中 p_i^R 和 p_i^I 分别为有功功率和无功功率，i 表示虚数单位），并产生生产成本 c_i。目标是在遵守总产生功率幅值（或视在功率）约束的前提下，决定哪些机组应启动，以使成本最小，即 ||Σ_{i is activated} (p_i^R + i·p_i^I)|| ≥ D，等价于 (Σ_{i is activated} p_i^R)2 + (Σ_{i is activated} p_i^I)2 ≥ D2。引入二元决策变量 x_i∈{0,1} 表示是否启动发电机组 i，需求约束可表示为 (Σ_{i∈[n]} p_i^R x_i)2 + (Σ_{i∈[n]} p_i^I x_i)2 ≥ D2。分节摘录硬度与近似算法CQP 是 NP-难的，因为它是经典极小化背包问题的推广。事实上，由于对于二元变量 x_i 有 x_i2 = x_i，当 Q 为对角矩阵时，二次约束 (2) 退化为线性约束。值得注意的是，CQP 可视为研究充分的二次背包问题（QKP）的对偶问题（Galli et al., 2025, Pisinger, 2007），后者在线性装箱约束下最大化二次函数。与 QKP 类似，CQP 也可具有图论解释如下。当 Q 具有 cp-秩 2 时的情况我们考虑 CQP 的一个特殊情况，其中约束具有 (p^T x)2 + (q^T x)2 ≥ B2 的形式，其中（线性无关）向量 p, q∈???。我们进一步假设 (Σ_{i∈[n]} p_i)2 + (Σ_{i∈[n]} q_i)2 ≥ B2，以保证问题可行。我们旨在基于线性规划技术为 CQP 提供 PTAS。记 NLP 为 CQP 的（非凸）松弛问题。(NLP) min_{x∈[0,1]^n} c^T x，s.t. (p^T x)2 + (q^T x)2 ≥ B2。观察到松弛问题 NLP 是非凸的，因此无法用现有技术求解当 Q 为常秩正定半正定矩阵时的情况本节研究具有约束 (3) 的 CQP 的可近似性，其中 k 为常数，向量 q_i 可能包含负分量。记 q_{ij} 为 q_i 的第 j 个分量，且不失一般性地假设 q_i∈?? 且 B∈??。数值实验尽管算法 3 中的 PTAS 具有理论价值，但对于中等规模的 CQP 实例，其计算量仍然很大，主要原因是候选子集的组合枚举以及重复调用算法 1（需要求解 LP）。为补充上述理论结果并说明所提出的近似方案如何转化为可实际实施的流程，我们构建了 PTAS 的启发式变体，称为 PTAS_H，方法是讨论与结论我们研究并提出了覆盖问题 CQP 在非凸二次约束下的新算法结果，重点关注约束矩阵 Q 为非负、PSD 且具有常秩的情形。作为结果，我们获得了 CQP 的 n-近似算法和在资源增强下的多项式时间算法。值得注意的是，我们通过为 CQP 的特殊情况（约束矩阵具有常 cp-秩）提供 PTAS，解决了 Elbassioni et al. (2019) 提出的开放问题。CRediT 作者贡献声明 Trung Thanh Nguyen：撰写—审阅与编辑，撰写—原稿，项目管理，方法学，形式分析，概念化。Khaled Elbassioni：撰写—审阅与编辑，撰写—原稿，监督，方法学，形式分析，概念化。Areg Karapetyan：撰写—原稿，形式分析。Majid Khonji：监督。利益冲突声明作者声明不存在已知的可能影响本文所报告工作的竞争性财务利益或个人关系。致谢我们感谢编辑和审稿人的有益评论和建议，这些极大地提高了手稿的质量和清晰度。第一作者的工作由越南国家经济大学资助。Trung Thanh Nguyen | Khaled Elbassioni | Areg Karapetyan | Majid Khonji