如何使用谷歌的CP-SAT求解器计算非线性优化的"AddAbsEquality"或"AddMultiplicationEqualit"？

Question

我的目标是根据预测的序列恢复数据序列。假设原始数据序列为x_org = [10,20,30,40,50]但我收到的随机数据为x_ran = [50,40,20,10,30]． 现在，我的目标是通过保持它们最接近原始模式(最小化恢复损失)来恢复模式。

我使用了与"与团队工作人员分配"几乎相似的方法;和"求解一个优化问题";可在google OR-tool网站[https://developers.google.com/optimization/assignment/assignment_teams]和[https://developers.google.com/optimization/cp/integer_opt_cp]下载。

我可以最小化损失(误差)的总和，但不能计算平方和/绝对总和。

from ortools.sat.python import cp_model
x_org = [10, 20, 30, 40, 50]
x_ran = [50, 40, 20, 10, 30]
n = len(x_org)

model = cp_model.CpModel()
# Defidning recovered data
x_rec = [model.NewIntVar(0, 10000, 'x_rec_%i') for i in range(n)]
# Defidning recovery loss        
x_loss = [model.NewIntVar(0, 10000, 'x_loss_%i' % i) for i in range(n)]
# Defining a (recovery) mapping matrix 
M = {}
for i in range(n):
for j in range(n):
M[i, j] = model.NewBoolVar('M[%i,%i]' % (i, j)) 

# -----------------Constraints---------------%
# Each sensor is assigned one unique measurement.
for i in range(n):
model.Add(sum([M[i, j] for j in range(n)]) == 1)
# Each measurement is assigned one unique sensor.
for j in range(n):
model.Add(sum([M[i, j] for i in range(n)]) == 1)

# Recovering the remapped data x_rec=M*x_ran (like, Ax =b)
for i in range(n):   
model.Add(x_rec[i] == sum([M[i,j]*x_ran[j] for j in range(n)]))
# Loss = orginal data - recovered data
for i in range(n):
x_loss[i] = x_org[i] - x_rec[i]

# minimizing recovery loss
model.Minimize(sum(x_loss))
#--------------- Calling solver -------------%
# Solves and prints out the solution.
solver = cp_model.CpSolver()
status = solver.Solve(model)
print('Solve status: %s' % solver.StatusName(status))
if status == cp_model.OPTIMAL:
print('Optimal objective value: %i' % solver.ObjectiveValue())
for i in range(n):
print('x_loss[%i] = %i' %(i,solver.Value(x_loss[i]))) 

则不含绝对误差和的输出为:

Solve status: OPTIMAL
Optimal objective value: 0
x_loss[0] = -10
x_loss[1] = -30
x_loss[2] = 0
x_loss[3] = 30
x_loss[4] = 10

表明即使损失总和为零，恢复也是不正确的。然而，当我试图添加另一个int变量来存储损失的绝对值时，编译器给出了一个错误。

# Defidning abs recovery loss        
x_loss_abs = [model.NewIntVar(0, 10000, 'x_loss_abs_%i' % i) for i in range(n)] 
# Loss = orginal data - recovered data
for i in range(n):
model.AddAbsEquality(x_loss_abs[i], x_loss[i])
#model.AddMultiplicationEquality(x_loss_abs[i], [x_loss[i], x_loss[i]])

错误是回溯:

TypeError                                 Traceback (most recent call last)
<ipython-input-42-2a043a8fef8b> in <module>
3 # Loss = orginal data - recovered data
4 for i in range(n):
----> 5     model.AddAbsEquality(x_loss_abs[i], x_loss[i])
~/anaconda3/envs/tensorgpu/lib/python3.7/site-packages/ortools/sat/python/cp_model.py in AddAbsEquality(self, target, var)
1217         ct = Constraint(self.__model.constraints)
1218         model_ct = self.__model.constraints[ct.Index()]
-> 1219         index = self.GetOrMakeIndex(var)
1220         model_ct.int_max.vars.extend([index, -index - 1])
1221         model_ct.int_max.target = self.GetOrMakeIndex(target)
~/anaconda3/envs/tensorgpu/lib/python3.7/site-packages/ortools/sat/python/cp_model.py in GetOrMakeIndex(self, arg)
1397         else:
1398             raise TypeError('NotSupported: model.GetOrMakeIndex(' + str(arg) +
-> 1399                             ')')
1400 
1401     def GetOrMakeBooleanIndex(self, arg):
TypeError: NotSupported: model.GetOrMakeIndex((-x_rec_%i + 10))

你能告诉我怎样才能使赔偿损失的绝对总和/平方和降到最低吗?谢谢。

Answer 1

AddAbsEquality要求参数是变量(而不是表达式，如x_org[i] - x_rec[i])。所以我们必须在使用它之前创建一个临时决策变量(这里是v)。下面的代码似乎可以工作:

# ...
x_loss_abs = [model.NewIntVar(0, 10000, 'x_loss_abs_%i' % i) for i in range(n)]
# ...
for i in range(n):
# x_loss[i] = x_org[i] - x_rec[i] # Original
v = model.NewIntVar(-1000,1000,"v") # Temporary variable
model.Add(v == x_org[i] - x_rec[i] )
model.AddAbsEquality(x_loss_abs[i],v)
# ....
model.Minimize(sum(x_loss_abs))

解决方案是(我改变了输出):

Optimal objective value: 0
x_org: [[10, 20, 30, 40, 50]]
x_rec: [10, 20, 30, 40, 50]
x_loss: [0, 0, 0, 0, 0]