Дискретная оптимизация - выбор ровно N элементов из каждой строки и столбца матрицы оценок

Question

Учитывая матрицу баллов, я бы хотел выбрать ровно n элементов из каждого столбца и каждой строки так, чтобы общий балл выбранных элементов по всей матрице был как можно выше.

Пример: с учетом матрицы затрат

array([[0.65500799, 0.79214695, 0.39854742],
       [0.53634974, 0.3682463 , 0.99663978],
       [0.73423119, 0.87150676, 0.80823699]])

Оптимальный выбор для n = 1:

array([[1., 0., 0.],
       [0., 0., 1.],
       [0., 1., 0.]])

, общая оценка этого решения составляет 0,65500799 + 0,87150676 + 0,99663978

Оптимальный выбор для n = 2:

array([[1., 1., 0.],
       [1., 0., 1.],
       [0., 1., 1.]])

Общая оценка этого решения составляет 0,65500799 + 0,53634974 + 0,79214695 + 0,87150676 + 0,99663978 + 0,80823699

Эти решения были получены наивным Поиск в ширину (BFS) .Тем не менее, этот подход не является вычислительно выполнимым (время взрыва) для более крупных задач (например, 10x10, n = 2).

Вопросы:

1. Как эта дискретная проблема оптимизацииклассифицированы?
2. Какая эвристика может позволить быстро найти хорошие решения для этой проблемы?
3. Какие библиотеки Python реализуют эту эвристику?

Answer 1

Вот решение, основанное на целочисленном программировании (IP).

Переменные решения: x[i,j] = 1, если мы выберем элемент в строке i, столбец j.

Параметры (входы): s[i,j] = оценка для ввода (i, j)

Формулировка:

maximize sum {i, j} s[i,j] * x[i,j]
subject to sum {i} x[i,j] = n     for all j
           sum {j} x[i,j] = n     for all i
           x[i,j] in {0,1}        for all i, j

Это можно реализовать в Python / PuLP или в специальном пакете, таком как gurobipy или docplex.Я ожидал бы, что эти решатели могут решить даже умеренно большие случаи проблемы, до оптимальности (не эвристически), в доли секунды.