可行性检查

计算科学 优化 非线性规划 凸优化
2021-11-28 22:11:15

考虑以下优化问题:

MinCX

AXb

xixj=xsxtijst

xj0;

在哪里A是邻接矩阵和C是一个常数向量。

如何以一种有效的方式检查这个优化问题的可行性?

1个回答

你不能。优化和可行性是等价的问题,因为优化可以通过解决一系列可行性问题来实现。因此,两者都属于同一计算复杂度类。在回答您提出的类似问题时,我表明您的公式是非凸的。确定此类问题的可行性通常是NP-困难的问题。

从该类似问题中删除的答案指出,零向量是您的问题的可行解决方案;如果您施加目标必须小于或等于的约束ε为了ε>0,那么可行性问题是不平凡的。