使用 OR 工具 CP-SAT 最大化 2D 点之间的各个距离

Question

我正在尝试编写一种算法，最大化 2D 点之间的欧几里德距离之和。 基于（并感谢）这个讨论，我想将整个事情放入

for

循环中，以便可以针对多个点完成此操作。

这是我尝试做的：

from ortools.sat.python import cp_model
model = cp_model.CpModel()

distance_range = 20
number_of_points = 3

a = []    # list to collect all points
# create set of required (x, y) points 
for i in range(number_robots):
    x_i = model.NewIntVar(1, distance_range , 'x_%i' %i)
    y_i = model.NewIntVar(1, distance_range , 'y_%i' %i)
    a.append((x_i, y_i))

# find difference 
x_diff = model.NewIntVar(-distance_range , distance_range , 'x_diff')
y_diff = model.NewIntVar(-distance_range , distance_range , 'y_diff')
difference = []
for i in range(2):
    for j in range(2):
         model.AddAbsEquality(x_diff, a[i][0] - a[j][0])
         model.AddAbsEquality(y_diff, a[i][1] - a[j][1])
         difference.append((x_diff, y_diff))

# square the difference value
x_diff_sq = model.NewIntVar(0, distance_range^2 , '')
y_diff_sq = model.NewIntVar(0, distance_range^2 , '')
difference_sq = []

for i in range(2):
    model.AddMultiplicationEquality(x_diff_sq, a_diff[i][0], a_diff[i][0])
    model.AddMultiplicationEquality(y_diff_sq, a_diff[i][1], a_diff[i][1])
    difference_sq.append((x_diff_sq, y_diff_sq))

# sum of square distances, (x_i^2 + y_i^2)
distance_sq= model.NewIntVar(0, 2*distance_range , '')
for i in range(2):
    model.AddAbsEquality(distance_sq, difference_sq[i][0]+ difference_sq[i][1])

#Objective
model.Maximize(distance_sq)

# Creates a solver and solves the model.
solver = cp_model.CpSolver()
status = solver.Solve(model)


if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    for i in range(number_of_points):
        print("x_%i" %i, solver.Value(a[i][0]))
        print("y_%i" %i, solver.Value(a[i][1]))
else:
    print('No solution found.')

我尝试执行上面给出的代码，但我从未使距离最大化。所有点都有相同的坐标值。所以我尝试为

3 points

设置以下给定的约束

model.AllDifferent([a[0][0], a[1][0], a[2][0])    # all values of x should be different
model.AllDifferent([a[0][1], a[1][1], a[2][1])    # all values of y should be different

那么我没有得到任何最佳解决方案。我该如何解决这个问题？

我能够使用上面的代码来最大化/最小化fixed点和多个变量（决策变量）之间的距离，但很少有点重叠，这就是为什么我试图在点之间强制执行这个最大化目标.

Answer 1

这是一个带有平方距离的工作版本：

from ortools.sat.python import cp_model

model = cp_model.CpModel()

distance_range = 20
number_of_points = 3

# create set of required (x, y) points
x = [
    model.NewIntVar(1, distance_range, f'x_{i}')
    for i in range(number_of_points)
]
y = [
    model.NewIntVar(1, distance_range, f'y_{i}')
    for i in range(number_of_points)
]

# Build intermediate variables and get the list of square differences on each dimension.
objective_terms = []
for i in range(number_of_points - 1):
    for j in range(i + 1, number_of_points):
        x_diff = model.NewIntVar(-distance_range, distance_range, f'x_diff{i}')
        y_diff = model.NewIntVar(-distance_range, distance_range, f'y_diff{i}')
        model.Add(x_diff == x[i] - x[j])
        model.Add(y_diff == y[i] - y[j])
        x_diff_sq = model.NewIntVar(0, distance_range ** 2, f'x_diff_sq{i}')
        y_diff_sq = model.NewIntVar(0, distance_range ** 2, f'y_diff_sq{i}')
        model.AddMultiplicationEquality(x_diff_sq, x_diff, x_diff)
        model.AddMultiplicationEquality(y_diff_sq, y_diff, y_diff)
        objective_terms.append(x_diff_sq)
        objective_terms.append(y_diff_sq)

#Objective
model.Maximize(sum(objective_terms))

# Creates a solver and solves the model.
solver = cp_model.CpSolver()
solver.parameters.log_search_progress = True
solver.parameters.num_workers = 8
status = solver.Solve(model)

# Prints the solution.
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    for i in range(number_of_points):
        print(f'x_{i}={solver.Value(x[i])}')
        print(f'y_{i}={solver.Value(y[i])}')
else:
    print('No solution found.')

你的代码中有很多错误：

• 它无法编译（number_robots vs number_of_points）
• 它的缩进很严重
• 您在多个机器人中重复使用相同的变量（xdiff、y_diff、x_diff_sq、y_diff_sq）
• 你数了两次距离
• distance ^ 2 不是距离的平方，它是一个布尔运算符。使用**

因此，因为我们使用距离的平方，所以解是退化的（两个点在一个角，另一个在对角。

x_0=1
y_0=1
x_1=20
y_1=20
x_2=1
y_2=1

为了解决这个问题，我们引入一个整数变量，该变量将小于两个机器人之间距离的平方根。为了提高精度，我们将添加一个缩放因子。

这是中间代码：

objective_terms = []
scaling = 100
for i in range(number_of_points - 1):
    for j in range(i + 1, number_of_points):
        x_diff = model.NewIntVar(-distance_range, distance_range, f'x_diff{i}')
        y_diff = model.NewIntVar(-distance_range, distance_range, f'y_diff{i}')
        model.Add(x_diff == x[i] - x[j])
        model.Add(y_diff == y[i] - y[j])
        x_diff_sq = model.NewIntVar(0, distance_range ** 2, f'x_diff_sq{i}')
        y_diff_sq = model.NewIntVar(0, distance_range ** 2, f'y_diff_sq{i}')
        model.AddMultiplicationEquality(x_diff_sq, x_diff, x_diff)
        model.AddMultiplicationEquality(y_diff_sq, y_diff, y_diff)

        # we create a dist variable such that dist * dist < x_diff_sq + y_diff_sq.
        # To improve the precision, we scale x_diff_sq and y_diff_sq by a constant.
        scaled_distance = model.NewIntVar(0, distance_range * 2 * scaling, '')
        scaled_distance_square = model.NewIntVar(
            0, 2 * distance_range * distance_range * scaling * scaling, '')
        model.AddMultiplicationEquality(scaled_distance_square,
                                        scaled_distance, scaled_distance)
        model.Add(scaled_distance_square <= x_diff_sq * scaling +
                  y_diff_sq * scaling)
        objective_terms.append(scaled_distance)

给出了合理的答案：

x_0=1
y_0=1
x_1=20
y_1=1
x_2=1
y_2=20

我还重写了示例以最大化两个机器人之间的最小欧几里得距离。代码可在此处获取。