Операция ИЛИ и поиск max для нескольких матричных столбцов

[zgemm]

Добрый день,

имеется довольно большая матрица, близкая к квадратной (то есть число столбцов-строк близко по значениям). В моем случае ее размерность составляет около 10к * 10к. Каждый матричный элемент - это или 0, или 1. Надо выбрать $K$ столбцов, так, чтобы максимизировать число строк в этих столбцах, в которых есть хотя бы одна единица. По условию $K$ - довольно маленькое, но, к сожалению, не 1 или 2, в моем случае, значение $K$ находится в пределе 10.

Кроме как перебором по всем столбцам или запуском чего-то типа метода отжига без гарантии того, что решится, ничего в голову не приходит. Перебор даже на суперкомпьютере не осуществим. Метод отжига попробовал, но за день на довольно быстрой рабочей станции и с распараллеливанием по ядрам - не дало результата, всяко находятся каждый час все новые и новые варианты, и на сколько долго будут находится - не понятно. То есть или есть монотонная сходимость без гарантии попадания в глобальный максимум, или совсем нет сходимости.

Скажите, пожалуйста, есть ли какой-то детерминистический или с гарантированной сходимостью, но, в то же время, не NP-полный алгоритм для решения этой задачи?

Спасибо

[ozheredov]

zgemm, Добрый день,

возможно, я туплю, но:

а) если макс по числу ненулевых элементов столбца, то это просто наибольший элемент из суммы всех строк матрицы

б)если именно целых строк, то какая разница, с каким именно столбцом ассоциировать строку?

[zgemm]

ozheredov,

не-не-не, смотрите, берем $K=3$, то есть берем какие-то три столбца. В них и только в них рассматриваем строки. Если в строке есть хотя бы одна единица, то помечаем строку как с единицей. Теперь считаем все строки, что были помечены как строки с единицами. То есть если у нас $K=1$ , то надо найти ту строку, у которой больше всего единиц, если $K=2$, то тут надо искать по двум циклам номеров строк, и для каждой такой пары смотреть есть ли единица в строке, и считать такие строки, а вот для существенно больших $K$ все становится довольно не разумно сложным.

-- 01.09.2024, 22:36 --

То есть пусть у нас дана матрица $A \in R^{N \times M}$, и задано $K$, тогда мы ищем такие индексы $i_1,...,i_K \in [1,...,N]$, что

$$\max_{i_1,...,i_K} \sum_m^M {\rm bool}\left(\sum_k^K a_{i_k,m}\right)$$

${\rm bool}(x)$ равна 1 если $x \ne 0$, и 0 иначе.

EDIT: поправил формулу, но через Аверсона - понятнее, я забыл как это называется.

[ozheredov]

zgemm в сообщении #1652710 писал(а):

$$\max_{i_1,...,i_K} \sum_m^M {\rm bool}\left(\sum_k^K a_{i_k,j}\right)$$

$a_{i_k,j}$ это элемент $i_k$-той строки и $j$-того столбца. Мы перебираем множества из K номеров строк? И что делают в формуле индексы $m$ и $j$?

[dgwuqtj]

Я так понял, надо найти

$$\max_{j_1 < \ldots < j_K} \sum_i \bigl[\bigvee_{k = 1}^K a_{i, j_k}\bigr],$$

где $[\ldots]$ скобка Айверсона (то, что zgemm обозначил через bool). У меня $i$ пробегает номера строк, а $j_k$ — столбцов.

[zgemm]

dgwuqtj в сообщении #1652714 писал(а):

Я так понял, надо найти...

да, точно, а то я местоположение индексов и строк местами переставил.

[SergeyGubanov]

Сосчитать количество единиц в каждом столбце, отсортировать столбцы по количеству единиц, взять первые $G$ из них с наибольшим количеством единиц (причём $G > K$), потом из $G$ наиболее перспективных столбцов полным перебором выбрать $K$ наилучших столбцов. Число $G$ выбрать так, чтобы полный перебор закончился за разумное время.

Решение не точное, но точно проверить-то всё равно нельзя. Для точной проверки понадобится полный перебор.

[ozheredov]

zgemm в сообщении #1652702 писал(а):

всяко находятся каждый час все новые и новые варианты

zgemm, Вы уверены, что задача

dgwuqtj в сообщении #1652714 писал(а):

найти

$$\max_{j_1 < \ldots < j_K} \sum_i \bigl[\bigvee_{k = 1}^K a_{i, j_k}\bigr],$$

имеет единственное решение?

[zgemm]

SergeyGubanov в сообщении #1652737 писал(а):

Сосчитать количество единиц в каждом столбце, отсортировать столбцы по количеству единиц, взять первые $G$ из них с наибольшим количеством единиц (причём $G > K$), потом из $G$ наиболее перспективных столбцов полным перебором выбрать $K$ наилучших столбцов. Число $G$ выбрать так, чтобы полный перебор закончился за разумное время.

да, верно, то, что Вы предлагаете очень похоже на начальное приближение для метода отжига. К сожалению, если брать мало перспективных столбцов, то потом отжиг долго сходится, если много - то это долго решается.

-- 02.09.2024, 10:27 --

ozheredov в сообщении #1652744 писал(а):

...
имеет единственное решение?

я это не говорил, но по крайней мере верхний предел значения легко оценивается (число строк). То есть если вдруг мы дошли до значения, равного числу строк, то можно смело утверждать, что мы забежали на один из не улучшаемых максимумов. Правда в реальных задачах у меня точный максимум оказывается меньше, чем теоретически возможный. (у меня набор матриц, и для матриц размера около 1000 и $K=4$ можно перебором дождаться).

[пианист]

zgemm
А к MIP оно не сведется?

[zgemm]

Кстати, об отжиге.

Начальное приближение выбираю так. Беру столбец с самым большим числом единиц. Далее перебираю все остальные столбцы так, что совместно с первым будет максимум. Также добавляю до тех пор, пока не получу нужное число столбцов.

Отжиг: берем $K$ столбцов и пробуем заменить один не выбранный на то, что выбрано и получить наиболее хороший результат. Далее бросаем монетку, если самый лучший выбор не улучшил достигаемое значение, и если монетка в "воздухе зависла", то ухудшаем. Без ухудшения метод валится в локальный максимум и оттуда не выбирается (это со всеми отжигами так).

-- 02.09.2024, 10:35 --

пианист в сообщении #1652746 писал(а):

zgemm
А к MIP оно не сведется?

пока сам не могу это или доказать или опровергнуть, поэтому и вопрошаю.

[пианист]

Если не наврал, то как-то так (синтаксис gmpl):

(Оффтоп)

param n := 1000;
param m := 1050;

param K := 10;

set strng := 1..n;
set clmn := 1..m;

param a{i in strng, j in clmn};

var x{j in clmn}, binary;
var y{i in strng}, binary;

maximize obj: sum{i in strng} y[i];

s.t. num_clmn: sum{j in clmn} x[j] = K;

s.t. def_y_up{i in strng}: m*y[i] - sum{j in clmn}(a[i,j]*x[j]) <= m-1;
s.t. def_y_dn{i in strng}: m*y[i] - sum{j in clmn}(a[i,j]*x[j]) >= 0;

solve;


printf 'column \n' > 'columns.txt';
printf{j in clmn: x[j]>0} '%5d \n', j >> 'columns.txt';

data;

param a :=
1 1 0
1 2 1
...
;

end;

[zgemm]

пианист в сообщении #1652753 писал(а):

Если не наврал, то как-то так (синтаксис gmpl):

круто, спасибо большое! Попробую как gmpl это решает. Я как-то мимо этого пакета прошел.

[пианист]

zgemm в сообщении #1652772 писал(а):

Я как-то мимо этого пакета прошел.

Ну перепишите под то, что привычнее. Тут главное, что в MIP можно записывать логические операции (def_y_up и def_y_dn в коде). Не особо удобно, но как-то можно.

[zgemm]

пианист в сообщении #1652782 писал(а):

Ну перепишите под то, что привычнее. Тут главное, что в MIP можно записывать логические операции (def_y_up и def_y_dn в коде). Не особо удобно, но как-то можно.

мне-то главное понять суть каким методом гарантированно это решать, так как решать надо много раз и в реальном времени, и ...(!) на встраиваемых системах, где не факт, что у меня доступ к этой библиотеке будет. С другой стороны, если в библиотеке - есть, скорей всего ничем лучше решить не получится, то есть надо будет разобрать как оно решает и переписать в удобоваримом варианте.