带有二元变量与全幺模约束的二次函数最小化问题求解咨询

这个问题挺有意思的——结合了二次0-1优化和全幺模约束，刚好能利用全幺模矩阵的特殊结构避开暴力枚举的指数复杂度，我来拆解下不同情况的可行思路：

先明确核心结构：二次项的性质是关键 #

首先把二次多项式 $q(x_1,...,x_n)$ 拆写成 $q(x) = x^T Q x + c^T x + d$（d是常数，不影响优化方向），解法思路完全取决于矩阵Q的性质：

情况1：q是凸二次多项式（Q半正定） #

如果Q是半正定的，问题属于凸优化范畴，结合全幺模约束可以这么处理：

• 先尝试松弛变量求解：把0-1变量松弛为连续变量 $0 \leq x_i \leq 1$，求解凸二次规划：
  $$\min_{Ax = b, 0 \leq x \leq 1}(q(x))$$
  因为A是全幺模的，若二次项只有对角项（即Q是对角矩阵），则 $x_i^2 = x_i$（毕竟x_i是0-1变量），此时q直接退化为线性函数！问题就变成全幺模约束下的线性规划，直接用单纯形法就能得到整数最优解——这也是全幺模矩阵的核心优势：线性规划的基可行解必为整数。
• 如果有交叉项且松弛解非整数：可以用分支定界法。每次选一个非整数变量，分支为 $x_i=0$ 和 $x_i=1$，子问题的约束依然保持全幺模性，所以每个子问题的线性/凸二次松弛都能高效求解，分支次数会远小于暴力枚举的指数级。

情况2：q是非凸二次多项式（Q不定） #

非凸二次0-1规划本身是NP-hard的，但全幺模约束依然能帮我们简化问题：

• 线性化交叉项：把所有交叉项 $x_i x_j$ 替换成新的0-1变量 $y_{ij}$，同时添加约束：
  $$y_{ij} \leq x_i, \quad y_{ij} \leq x_j, \quad y_{ij} \geq x_i + x_j - 1$$
  这样原二次问题就转化为关于x和y的线性规划问题，目标函数变为线性，约束包括原有的 $Ax=b$ 加上这些y的约束。
• 利用全幺模性简化求解：原矩阵A是全幺模的，新增的y的约束对应的系数矩阵也是全幺模的（每个约束的系数都是-1、1或0，符合全幺模矩阵的判定条件）。若扩展后的整个约束矩阵依然全幺模，那么这个线性0-1规划的松弛解就是整数解，直接用单纯形法就能搞定；即使扩展矩阵不是全幺模，分支定界时子问题的松弛依然能借助全幺模性快速求解，效率远高于暴力枚举。

针对你的实际排班场景 #

从你提到的员工月度排班问题来看，二次项大概率是用来表达“惩罚连续排班”“避免特定员工同时排班”这类逻辑，这些都很容易通过线性化转化为线性约束，最终大概率能变成全幺模约束下的线性0-1规划，直接用单纯形法就能高效求解，完全不用暴力枚举所有可能的排班组合。

备注：内容来源于stack exchange，提问作者Kandinskij