时间戳

首页 > 解决方案 > 我可以使用 cvxpy 将整数二维数组拆分为两个数组吗？

cvxpy - 我可以使用 cvxpy 将整数二维数组拆分为两个数组吗？

问题描述

我有一个问题想知道是否可以使用 cvxpy 解决：

问题： 我有一个二维整数数组，我想将它拆分为两个数组，使源数组的每一行都在第一个或第二个数组中。

这些数组的要求是，对于每一列，数组#1 中的整数之和将尽可能接近数组#2 中的整数之和的两倍。

示例： 考虑输入数组：

[
  [1, 2, 3, 4],
  [4, 6, 2, 5],
  [3, 9, 1, 2],
  [8, 1, 0, 9],
  [8, 4, 0, 5],
  [9, 8, 0, 4]
]

其列的总和[33, 30, 6, 29]非常理想，我们正在寻找 2 个数组，它们的列的总和将是：

当然，这并不总是可能的，但我正在寻找这个问题的最佳解决方案。

此特定示例的可能解决方案可能是：

[
  [1, 2, 3, 4],
  [4, 6, 2, 5],
  [8, 4, 0, 5],
  [9, 8, 0, 4]
]

使用列总和：[22, 20, 5, 18]

[
  [3, 9, 1, 2],
  [8, 1, 0, 9],
]

使用列总和：[11, 10, 1, 11]

有什么建议么？

标签： cvxpy

解决方案

您可以使用布尔向量变量来选择行。剩下要决定的唯一事情是惩罚错误的程度。在这种情况下，我只是使用了差异向量的范数。

import cvxpy as cp
import numpy as np
data = np.array([
  [1, 2, 3, 4],
  [4, 6, 2, 5],
  [3, 9, 1, 2],
  [8, 1, 0, 9],
  [8, 4, 0, 5],
  [9, 8, 0, 4]
])
x = cp.Variable(data.shape[0], boolean=True)
prob = cp.Problem(cp.Minimize(cp.norm((x - 2 * (1 - x)) * data)))
prob.solve()
A = np.round(x.value) @ data
B = np.round(1 - x.value) @ data

A并且B是行的总和。

(array([21., 20.,  4., 19.]), array([12., 10.,  2., 10.]))

推荐阅读