您可以将其重新表述为

$x^{*}=\arg \min x^{T}Lx+ t$

受制于

$t \geq P^{T}x$

$t \geq -P^{T}x$

$x \in \left\{ 0, 1 \right\}^{n}$

这是一个 0-1 混合整数二次规划问题 (MIQP)为正定的情况可由 CPLEX 等求解器很好地处理。 $L$

您可以免费下载 YALMIP http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Main.Download。YALMIP 会为你做脏活。安装 YALMIP，运行 yalmiptest 测试安装，阅读http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.Basics。如果您有 CPLEX 可用并安装在 MATYLAB 下，它将/可以使用它，否则会使用其他东西。L 不必是 psd 以便在 YALMIP 下使用 CPLEX 或 scip 作为求解器求解。但是，您说它是拉普拉斯矩阵，因此必须是 psd。

n = length(P); % this is not really YALMIP code
x = binvar(n,1) % declare x as binary; would use sdpvar instead for continuous variable
sol = optimize([Ax<=b,Ax==b,lb<=x<=ub],x'*L*x+abs(P'*x))

是完整的 YALMIP 代码来解决这个问题。求解后，value(x) 提供了 x 的最优值。

如果您想指定一个特定的求解器，例如 scip，而不是让 YALMIP 选择求解器，请使用表格

sol = optimize([Ax<=b,Ax==b,lb<=x<=ub],x' L x+abs(P'*x), sdpsettings('solver','scip'))

您不需要输入通用格式。YALMIP 会在“幕后”为您处理这些问题，以形成适合求解器的形式。只需输入您拥有的约束即可。如果除了 x 是二进制之外没有任何约束，则可以使用 [] 代替 [Ax<=b,Ax==b,lb<=x<=ub] 。另请注意， sdpvar 并不意味着 x 被声明为 senidefinite。该声明是 YALMIP 仅针对 SDP 时的保留。