带整数解的线性系统约束优化

Question

我有兴趣解决以下优化问题，并求出最小正整数系数：

min(x1 + x2 + x3)
s.t. 
2x1 – 2x3 = 0
2x2 – x3 = 0

由于方程的数量与变量数不匹配，我还添加了x1 = 1的约束。使用来自工具的文档，我对代码进行了如下修改：

mat = np.array([[2,0,-2],[0,2,-1]])
def create_data_model(mat):
    num_rows, num_vars =mat.shape
    data = {}
    data['constraint_coeffs'] = [
          [2, 0, -2],
          [0, 2, -1],
          [1, 0, 0],
      ]
    data['bounds'] = [0, 0, 1]
    data['obj_coeffs'] = [1, 1, 1]
    data['num_vars'] = num_vars
    offset = np.max((num_rows, num_vars))-np.min((num_rows, num_vars))
    data['num_constraints'] = num_rows+offset
    return data

data=create_data_model(mat)
infinity = solver.infinity()
x = {}
for j in range(data['num_vars']):
    x[j] = solver.IntVar(0, infinity, 'x[%i]' % j)
print('Number of variables =', solver.NumVariables())

for i in range(data['num_constraints']):
    constraint = solver.RowConstraint(0, data['bounds'][i], '')
    for j in range(data['num_vars']):
        constraint.SetCoefficient(x[j], data['constraint_coeffs'][i][j])

print('Number of constraints =', solver.NumConstraints())

objective = solver.Objective()
for j in range(data['num_vars']):
    objective.SetCoefficient(x[j], data['obj_coeffs'][j])
objective.SetMinimization()

if status == pywraplp.Solver.OPTIMAL:
    for j in range(data['num_vars']):
        print(x[j].name(), ' = ', x[j].solution_value())
    print()
    print('Problem solved in %f milliseconds' % solver.wall_time())
    print('Problem solved in %d iterations' % solver.iterations())
    print('Problem solved in %d branch-and-bound nodes' % solver.nodes())
else:
    print('The problem does not have an optimal solution.')

denoms=[x[0].solution_value().as_integer_ratio()[1], x[1].solution_value().as_integer_ratio()[1],
       x[2].solution_value().as_integer_ratio()[1]]
scaling_factor=lcmm(*denoms) #a method to get the least common multiple
coeff=[scaling_factor*x[0].solution_value(), scaling_factor*x[1].solution_value(),
       scaling_factor*x[2].solution_value()]

这应该返回1,0.5，1作为最优解，它在缩放后变成2,1,2。

(1)在我的实现中，求解者找不到最优解。为什么会这样呢？

(2)得到最小正整数解有更简单的方法吗？

Answer 1

我在你的代码中看到了一些问题。

这句话是：

x[j] = solver.IntVar(0.0, infinity, 'x[%i]' % j)

您是说优化器必须生成整数。但是，您的示例的答案是将x2作为0.5，因此它将无法给出最优解。尝试：

x[j] = solver.NumVar(0.0, infinity, 'x[%i]' % j)

允许漂浮。然后你可以把它乘成整数。

另一个问题是，使用以下方法设置每个约束：

constraint = solver.Constraint(0, data['bounds'][i], '')

这意味着这个表达式的下界是0，上界是数据结构中的bound值。但是，对于第三个约束，这就像说0 <= x1 <= 1 (bounds2是1)一样。但是，您希望将其设置为相等，而不是从0到某些绑定的范围。您可以将行替换为

constraint = solver.Constraint(data['bounds'][i], data['bounds'][i], '')

来保证这个值正是你想要的。您还可以将“界”重命名为“目标值”，以便更清楚地表明，这不是上限或下限，而是您想要的确切目标。

最后，我不知道您在代码中运行status = solver.Solve()的位置。它应该就在您检查status之前在if/else中。

希望这能有所帮助！

Answer 2

我认为下面的代码会给出解决方案，我们唯一需要做的就是将.5之间的上、下界设置为无穷大。这可能不是完美的代码，但我得到了您的答案与此代码。

from scipy.optimize import minimize

obj_fun = lambda x: (x[0]+ x[1]+ x[2])

constraint = ({'type': 'eq', 'fun': lambda x:  2*x[0] - 2*x[2]},
        {'type': 'eq', 'fun': lambda x: 2*x[1]-x[2]})


bound = ((.5, None), (.5, None),(.5,None))
res = minimize(obj_fun, (2, 0,0), method='SLSQP', bounds=bound,
               constraints=constraint)

res