我正在努力尝试实现 Dinur-Nissim 算法，并停留在如何解决具有多个未知数和大量方程以及约束的线性不等式集上。
例： 0.2<=c4<=0.66
0.66<=c3<=1.56
0.96<=C3+C4<=2.26
约束： 0<=ci<=1
和许多其他方程，未知数直到cn，其中n是数据库的大小，所以我需要一个适用于大量方程的解决方案。
我试图寻找一些库，但其中大多数都解决了最大化或最小化问题，所以我不确定是否可以将这些方程转换为这些问题之一。
使用 scipy 的 linprog 的简单方法(线性规划;LP 可能是这里可用的最具体/最强大的优化问题类型！
法典
from scipy.optimize import linprog
c = [0, 0, 0, 0] # empty objective
A = [[0, 0, 0, -1], [0, 0, 0, 1],
[0, 0, -1, 0], [0, 0, 1, 0],
[0, 0, -1, -1], [0, 0, 1, 1]]
b = [-0.2, 0.66, -0.66, 1.56, -0.96, 2.26]
result = linprog(c, A, b, bounds=(0,1))
print(result)
输出
fun: -0.0
message: 'Optimization terminated successfully.'
nit: 3
slack: array([ 0.1 , 0.9 , 1.3 , 1. , 1. , 0.34, 0.7 , 0. , 0. , 0. ])
status: 0
success: True
x: array([ 0. , 0. , 0.66, 0.3 ])
以上是linprog的基本用法：
- 我们不需要任何目标，因此将所有因素保持零(见
c( - 我们需要
Ax <= b形式来表示我们的不平等：0.96 <= c3+c4 <=> c3+c4 >= 0.96 <=> -c3 -c4 <= 0.96
请记住，linprog 不如商业求解器稳定。你也可以用SLSQP解决这个问题。
以上，结合您的描述：
基本上最后一步涉及根据 c 的值做出决定，如果 ci>1/2 则 xi=1 否则 xi=0，所以我只需要找到满足不等式的 c 区域
在一般情况下没有多大意义，因为如您的帖子中所述，优化返回一个可行的值，并且如果没有额外的建模，求解器不关心您的阈值 0.5。所以你应该再次检查你的理论(我没有检查你的算法来实现;也许问题的性质允许这种方法(。