使用布尔决策矩阵进行 Scipy 最小化

Question

我有两组点（A 组和 B 组）之间的距离矩阵。每个 A 点都与相同数量的 B 点相关联（如果可能的话）。

我想最小化 A 点与其 B 关联点之间的平均距离的标准差。

我的目标函数如下：

from scipy.optimize import minimize

def objective( x , distances ):

  decision_matrix = x.reshape( distances.shape[0] , distances.shape[1] )

  avg_distances = np.sum( distances * decision_matrix , axis = 1 ) / np.sum( decision_matrix , axis = 1 )

  std_distances = np.std( avg_distances )

  return std_distances

其中x是决策矩阵，0或1：0 A点和B点无关联，1关联。

我想实施以下限制：

• x 矩阵的元素为 0 或 1
• 对 x 列中的元素求和 = 1：没有孤立的 B 点，并且当 B 点与 A 点关联时，它不能与另一个 A 点关联
• 每个 A 点应关联相同数量的 B 点（2 个 A 点和 10 个 B 点 -> 每个 A 点将关联 5 个 B 点）

我的目的是在规定的约束下获得A点，B点配对，最小化目标函数。

有人可以给我一些关于如何使用 scipy 包实现该目标的提示吗？我在实施这些限制方面遇到了一些困难。谢谢。

Answer 1

这是一个部分解决方案，假设您愿意调整目标函数，以便问题可以表示为二进制整数 LP。

例如，如果您想最小化相应 A-B 点之间的距离总和：

import numpy as np
import matplotlib.pyplot as plt
from scipy import optimize, linalg
rng = np.random.default_rng(35982456879456)
n_a = 3
n_b = 9
n_a2b = n_b / n_a

# A_... is an equality constrant matrix
# B_... is equality_constraint RHS
# a has to do with points in group "a"
# b has to do with point in group "b"
a = rng.random((2, 3, 1))
b = rng.random((2, 1, 9))

distances = np.sum((a - b)**2, axis=0).ravel()

# This linear system represents the constraint that each
# point in group "a" is assigned to exactly `n_a2b` points
# in group "b"
ones = np.ones(n_b)
A_a_to_n = linalg.block_diag(ones, ones, ones)
B_a_to_n = np.full(n_a, n_a2b)

# This linear system represents the constraint that each
# point in group "b" is assigned to exactly one points
# in group "a"
ones = np.ones((n_a, 1))
A_b_to_1 = linalg.block_diag(*([ones]*n_b)).reshape(n_b, -1)
B_b_to_1 = np.ones(n_b)

# For the full linear system
A = np.vstack((A_a_to_n, A_b_to_1))
B = np.concatenate((B_a_to_n, B_b_to_1))

# Solve
integrality = np.ones(distances.size)
res = optimize.milp(distances, constraints=(A, B, B), 
                    integrality=integrality)

# Plot
colors = ['r', 'g', 'b']
for i_a, i_b in zip(*np.where(res.x.reshape(3, -1))):
    print(i_a, i_b)
    plt.plot(a[0, i_a, 0], a[1, i_a, 0], colors[i_a]+'o')
    plt.plot(b[0, 0, i_b], b[1, 0, i_b], colors[i_a]+'.')

听起来您更热衷于最小化簇内平均距离之间的方差（/标准差）。如果您愿意接受基于单一规范的价差衡量标准，我认为您可以将其纳入上面的框架中。

例如，假设您希望最小化最大簇内平均距离和最小簇内平均距离之间的最大差异。

您可以创建三个新的（浮点）决策变量并将它们限制为等于簇内平均距离。我们称它们为

d1

、

d2

、

d3

。

创建三个新的决策变量来表示它们之间的成对差异。例如：

d12 = d2 - d1

、

d13 = d3 - d1

、

d23 = d3 - d2

。还创建

d21

、

d31

和

d32

（这些的负数）。

创建一个新的决策变量

d_max

，表示所有这些变量中的最大值（

d12

、

d21

、

d13

、

d31

、

d23

、

d32

）。您可以通过将其限制为大于它们中的每一个来确保它是最大值。

将目标函数设置为

d_max

。