在二进制矩阵中将 1 设置为 0 的最小成本

Question

假设我有一个包含 1 和 0 的矩阵：

[[1,1,1], [1,1,0],[0,0,1]]

在每次移动中，我可以将整行设置为 0，或者将整列设置为 0。 每行和每列都有一个关联的成本：

row_cost: [2, 2, 100]; col_cost: [5, 5, 10]

目标是找到将所有 1 设置为 0 的最小成本

在示例中，最小成本是设置第 1 行、第 2 行和第 3 列，这将花费 2 + 2 + 10 = 14

你们能帮我找出一个算法吗？

不确定这是否是设置封面问题的变体。尝试提出自下而上的动态规划算法，但没有成功

Answer 1

下面演示了以 ILP 表示的集合覆盖方法，在 Python 中使用

pyomo

来表达问题，并使用

cbc

或

highs

求解器来解决它。

对于较大的数据，它可以在大约 0.02 秒内解决 100x100 矩阵 @ 20% 1 的随机成本，并在 2 秒内解决 1000x1000 矩阵。这些来自注释掉的“大数据”部分。

代码：

"""
zero-ize matrix.  Set Covering Approach
"""
import random

import pyomo.environ as pyo
import numpy as np
import highspy

# DATA

# Original data...
m = [[1, 1, 1], [1, 1, 0], [0, 0, 1]]

row_cost = [2, 2, 100]
col_cost = [5, 5, 10]

# Bigger data...
# r, c = 10, 10
# # r, c = 100, 100
# # r, c = 1000, 1000
# m = np.random.binomial(n=1, p=0.20, size=(r, c))  # 20% coverage w/ random 1's
# row_cost = list(range(r))
# col_cost = list(range(c))
# random.shuffle(row_cost)
# random.shuffle(col_cost)

# define the set to be covered as (i, j) indices of the non-zero elements
U = [(i, j) for i in range(len(m)) for j in range(len(m[0])) if m[i][j] > 0]

# define the coverages of the row/column selections
coverage = {(i, j): (f'r{i}', f'c{j}') for (i, j) in U}

# capture the cost parameter
costs = dict()
for i in range(len(m)):
    costs[f'r{i}'] = row_cost[i]
for j in range(len(m[0])):
    costs[f'c{j}'] = col_cost[j]

# a convenience
S = costs.keys()

# define the ILP
model = pyo.ConcreteModel()

# SETS
model.S = pyo.Set(initialize=S, doc='subset labels by r/c')
model.U = pyo.Set(initialize=U, doc='elements')
# make an indexed set of which elements of U are covered by selections within S
model.C = pyo.Set(model.U, within=model.S, initialize=coverage, doc='subsets that cover elements in U')
# show this set...
model.C.pprint()

# VARS
model.x = pyo.Var(model.S, domain=pyo.Binary, doc='select', initialize=0)

# PARAMS
model.costs = pyo.Param(model.S, initialize=costs)

# OBJ:  minimize cost
model.obj = pyo.Objective(expr=pyo.sum_product(model.costs, model.x))


# CONSTRAINTS
@model.Constraint(model.U)
def covered(model, i, j):
    return sum(model.x[s] for s in model.C[i, j]) >= 1  # some selection of s must cover this ij location


# SOLVE
# --highs
# solver = pyo.SolverFactory('appsi_highs')
# solution = solver.solve(model)

# --cbc
solver = pyo.SolverFactory('cbc')
solution = solver.solve(model)
assert solution.solver.termination_condition == pyo.TerminationCondition.optimal

print(solution)
# print(m)
eps = 0.01  # some small epsilon for numerical error
selections = sorted({s for s in model.S if pyo.value(model.x[s]) > eps})
print(f'selections: {selections}')
print(f'cost: {pyo.value(model.obj)}')

输出（OP数据）：

C : subsets that cover elements in U
    Size=6, Index=U, Ordered=Insertion
    Key    : Dimen : Domain : Size : Members
    (0, 0) :     1 :      S :    2 : {'r0', 'c0'}
    (0, 1) :     1 :      S :    2 : {'r0', 'c1'}
    (0, 2) :     1 :      S :    2 : {'r0', 'c2'}
    (1, 0) :     1 :      S :    2 : {'r1', 'c0'}
    (1, 1) :     1 :      S :    2 : {'r1', 'c1'}
    (2, 2) :     1 :      S :    2 : {'r2', 'c2'}

Problem: 
- Name: unknown
  Lower bound: 14.0
  Upper bound: 14.0
  Number of objectives: 1
  Number of constraints: 6
  Number of variables: 6
  Number of binary variables: 6
  Number of integer variables: 6
  Number of nonzeros: 6
  Sense: minimize
Solver: 
- Status: ok
  User time: -1.0
  System time: 0.0
  Wallclock time: 0.0
  Termination condition: optimal
  Termination message: Model was solved to optimality (subject to tolerances), and an optimal solution is available.
  Statistics: 
    Branch and bound: 
      Number of bounded subproblems: 0
      Number of created subproblems: 0
    Black box: 
      Number of iterations: 0
  Error rc: 0
  Time: 0.009045839309692383
Solution: 
- number of solutions: 0
  number of solutions displayed: 0

selections: ['c2', 'r0', 'r1']
cost: 14.0