计算科学 - 线性规划的最大约束满足 - 吾爱随笔录

我需要解决的问题是最大化线性规划中满足的约束。

更具体地说，假设我有一个不可行的 LP 问题，我现在的目标是找到我可以满足的最大约束数。

放在一个公式的方式：

max \sum_{i = 1}^{K} x_{i}, s.t. d i a g (x) (A - b) y \geq 0

$\max \sum_{i=1}^K x_i,\\ \text{s.t.}\ \mathrm{diag}(x)(A-b) y \geq 0$

我有 $A \in \mathbb{R}^{k\times m}$ 和 $y \in \mathbb{R}^m$

如果 $y$ 在有限域中，则将是最大可满足性（MAX-SAT），这被证明是一个 NP-hard 问题。但是，对于线性规划问题，我找不到它是 NP-hard 还是多项式时间可解的。

如果对此有任何研究，请告诉我。