Игра на доске 10x10

[mihaild]

Alex Krylov в сообщении #1679318 писал(а):

Короче говоря, вся надежда на нулевой "integrality gap" за счет структурности

Надежды нет, потому что равномерное размазывание всех чисел по доске дает стоимость $505$, а целочисленная не больше $500$.

[vicvolf]

Alex Krylov в сообщении #1679318 писал(а):

Можно и как-то так:

$Y_{i,j}\in\left\lbrace 0,1 \right\rbrace$

$\sum\limits_{i=1}^{N} Y_{i,j}=1\quad\forall j =1,\dots,N$

$\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N} Y_{i,j}=N$

Условия непрерывности траекторий (вроде такое имеет смысл):
$\\ \sum\limits_{i=1}^{N-1}(Y_{i,j+1}+Y_{i+1,j})+\sum\limits_{i=1}^{N-1}(Y_{i+1,j+1}+Y_{i,j})+\sum\limits_{i=1}^{N}(Y_{i,j}+Y_{i,j+1})=2 \\ \forall j =1,\dots,N-1 $

Далее, если ослабить невыпуклые булевы ограничения $X_{i,j}\in\left\lbrace 0,1 \right\rbrace,\; Y_{i,j}\in\left\lbrace 0,1 \right\rbrace$, заменив их на $0\leqslant X_{i,j}\leqslant 1, \quad 0\leqslant Y_{i,j}\leqslant 1 \quad \forall i,j$, то приходим к разрешимой билинейной минимаксной задаче с независимыми линейными ограничениями: $\min\limits_{Y}\max\limits_{X}\sum\limits_{i,j}^{}c_{i,j}Y_{i,j}=\max\limits_{X}\min\limits_{Y}\sum\limits_{i,j}^{}c_{i,j}Y_{i,j}$, где величины $c_{i,j}$ определены выше и зависят линейно от $X_{i,j}$.

Короче говоря, вся надежда на нулевой "integrality gap" за счет структурности.

Ослабление булевых ограничений до непрерывных интервалов $[0, 1]$ и переход к билинейной задаче не упрощает решение, а скорее усложняет его из-за следующих причин:
1. Проблемы билинейной задачи
- Невыпуклость: Билинейные задачи (с произведениями переменных) являются невыпуклыми, что делает их NP-трудными даже для непрерывных переменных. Методы решения часто сходятся к локальным минимумам, не гарантируя глобальной оптимальности.
- Вычислительная сложность: Алгоритмы для билинейных задач (например, чередующаяся оптимизация) требуют множества итераций и могут не справиться с размерностью $10 \times 10$.
2. Потеря структуры задачи
- Физическая интерпретация: Непрерывные значения $Y_{i,j} \in [0, 1]$ теряют смысл "посещения клетки" или "перехода", что требует постобработки (например, округления), которая может нарушить целостность решения.
- Нарушение ограничений: После округления могут возникнуть нарушения условий вроде $\sum Y_{i,j} = N$ или непрерывности пути.
3. Сравнение с ILP
- Точность: Исходная IL-модель с бинарными переменными гарантирует корректное решение, соответствующее физическому смыслу.
- Современные солверы: Инструменты вроде Gurobi или CPLEX эффективно решают ILP для таблиц $10 \times 10$ (1000 переменных) за приемлемое время благодаря предобработке и эвристикам.
- Декомпозиция: Для больших таблиц можно использовать методы декомпозиции (например, Branch and Bound), которые неприменимы к билинейным задачам.

[lel0lel]

(Оффтоп)

Интересно, это только у меня такое ощущение, что к обсуждению присоеденился ИИ?

[Alex Krylov]

Цитата:

Интересно, это только у меня такое ощущение, что к обсуждению присоеденился ИИ?

Ну, судя по качеству ответов, "восстание машин" нам еще долго не грозит
Тест Тьюринга провален...

[vicvolf]

mihaild в сообщении #1679319 писал(а):

Надежды нет, потому что равномерное размазывание всех чисел по доске дает стоимость $505$, а целочисленная не больше $500$.

Целочисленное программирование - это метод нахождения оптимального решения, а равномерное размазывание это одна из стратегий, которая не является оптимальной. Никто здесь не доказал оптимальность какого-либо решения. Как я уже писал, нахождение оптимального решения, в данном случае, является очень трудоемкой задачей. Доказали только то, что оптимальное решение $\geq 500$. Вполне возможно, что оптимальное решение больше 500.

[lel0lel]

vicvolf в сообщении #1679333 писал(а):

Никто здесь не доказал оптимальность какого-либо решения.

12d3 доказал.

12d3 в сообщении #1678891 писал(а):

Рассмотрим горизонтальную полоску 2х10 с наименьшей суммой, которая не превосходит 1010. Выбирая в каждом столбике из двух клеток наименьшее число, получим путь с суммой, не превосходящей $\frac{1010 - 10}{2} = 500$.

[Alex Krylov]

Ответ невпопад:

Цитата:

1. Проблемы билинейной задачи... Билинейные задачи (с произведениями переменных) являются невыпуклыми, что делает их NP-трудными

Речь о минимаксе! См. напр. https://web.stanford.edu/~boyd/papers/pdf/dsp.pdf, раздел Dual Reduction
Ключевые слова: convex-concave minimax, saddle point, saddle problems итд

[vicvolf]

lel0lel в сообщении #1679335 писал(а):

vicvolf в сообщении #1679333 писал(а):

Никто здесь не доказал оптимальность какого-либо решения.

12d3 доказал.

12d3 в сообщении #1678891 писал(а):

Рассмотрим горизонтальную полоску 2х10 с наименьшей суммой, которая не превосходит 1010. Выбирая в каждом столбике из двух клеток наименьшее число, получим путь с суммой, не превосходящей $\frac{1010 - 10}{2} = 500$.

Да, это оптимальная стратегия в игре 2х10, но оптимальность данной стратегии для игры 10х10 это не доказывает, так как данные игры отличатюся. В игре 2х10 король на каждом шаге выбирает только один из двух вариантов, поэтому оптимальная стратегия: выбор минимального числа в каждом столбце. В игре 10х10 путь короля — это последовательность из 10 клеток и локальный выбор минимума в каждом столбце не гарантирует глобальный минимум.

[mihaild]

vicvolf в сообщении #1679452 писал(а):

Да, это оптимальная стратегия в игре 2х10, но оптимальность данной стратегии для игры 10х10 это не доказывает, так как данные игры отличатюся

Что, простите?
Доказано, что на любой доске существует маршрут стоимостью не больше $500$.
Ранее доказано, что существует доска, на которой не существует маршрута стоимостью меньше $500$.
Что тут еще доказывать?

И откуда взялась какая-то "игра $2 \times 10$"?

[Alex Krylov]

Тут оптимальной является матрица, не просто дающая построчно 505, а для которой (если использовать синтаксис Matlab) выполняется
max(max(abs(diff(A,1))))=1

Используется синтаксис Matlab M

A
     1     8     9    16
     2     7    10    15
     3     6    11    14
     4     5    12    13
diff(A,1)
     1    -1     1    -1
     1    -1     1    -1
     1    -1     1    -1
max(max(abs(diff(A,1))))
     1

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

[Alex Krylov]

Пару слов об integrality gap на примере линейной задачи о назначениях:
Вот исходная линейная задача о назначениях:
$\\ \min\limits_{x_{ij}}\sum\limits_{i,j=1}^{N}w_{ij}x_{ij}\\\sum\limits_{i=1}^{N}x_{ij}=1\;\forall j\\\sum\limits_{j=1}^{N}x_{ij}=1\;\forall i\\x_{ij}\in\left\lbrace 0,1\right\rbrace$

Если мы последнее булево ограничение $x_{ij}\in\left\lbrace 0,1\right\rbrace$ ослабим, заменив его на $0\leqslant x_{ij}\leqslant1$, то перед нами будет обычная линейная программа:
$\\ \min\limits_{}\sum\limits_{i=1}^{N!}\operatorname{tr}(W^TX_i)\xi_i\\0\leqslant\xi_i\leqslant 1;\;\limits_{}\sum\limits_{i=1}^{N!}\xi_i=1$
где $W=[w_{ij}]$, $X_i$ - все возможные (корректные целочисленные) назначения.

Видно, что решение линейной программы ищется внутри симплекса, натянутого на корректные $\left\lbrace0,1\right\rbrace$-значные решения! Как известно, решение такой задачи лежит либо в одной из вершин симплекса, либо на его грани/ребре. Если матрица задачи о назначениях допускает строго одно оптимальное решение, то решение указанной линейной программы будет лежать в вершине симплекса и будет целочисленным. Если матрица задачи о назначениях допускает несколько решений, то решение линейной программы будет взвешенной суммой целочисленных решений (геометрический центр вершин симплекса, на которых достигается оптимум). Это свойство решателей - помещать решение в барицентр.

Вот пример матрицы задачи о назначениях, допускающей два оптимальных назначения ($X_1$ и $X_2$):
$W=\begin{bmatrix}5&3&1\\2&6&7\\8&3&1\end{bmatrix}$

$X_1=\begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix}$, $X_2=\begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix}$, $X_3=\begin{bmatrix}0&0&1\\1&0&0\\0&1&0\end{bmatrix}$,
$X_4=\begin{bmatrix}1&0&0\\0&0&1\\0&1&0\end{bmatrix}$,$X_5=\begin{bmatrix}0&0&1\\0&1&0\\1&0&0\end{bmatrix}$, $X_6=\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}$

$\sum\limits_{i=1}^{N!}\operatorname{tr}(W^TX_i)\xi_i = 6\xi_1 + 6\xi_2 + 18\xi_3 + 15\xi_4 + 15\xi_5 + 12\xi_6$
Оптимальное (нецелочисленное) решение:
$X_{opt} = \frac{1}{2}(X_1+X_2) = \begin{bmatrix}0&1&0\\0.5&0&0.5\\0.5&0&0.5\end{bmatrix}$
Целочисленные решения реконструируемы!

Вот пример матрицы, допускающей только одно оптимальное решение ($X_6$):
$W=\begin{bmatrix}1&2&8\\7&5&7\\9&3&4\end{bmatrix}$
$\sum\limits_{i=1}^{N!}\operatorname{tr}(W^TX_i)\xi_i = 18\xi_1 + 13\xi_2 + 18\xi_3 + 11\xi_4 + 22\xi_5 + 10\xi_6$
Оптимальное (целочисленное) решение:
$X_{opt}=X_6=\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}$

[Alex Krylov]

Если учесть позапрошлый пост, то всего имеется $2\,10!=7\,257\,600$ оптимальных решений. Можно ожидать, что релаксационное решение будет их взвешенной комбинацией (если там нет каких-то дополнительных нюансов), т.е. все числа будут ровным слоем размазаны по таблице $10\times10$. А вот если мы возьмем и одно из чисел принудительно закрепим за какой-то конкретной ячейкой таблицы $10\times10$. Например, единицу принудительно закрепим за ячейкой $(1,1)$... То ситуация должна заметно улучшиться! Из такого решения уже можно извлечь гораздо больше полезной информации (нежели просто значение оптимума или его оценка).

[Alex Krylov]

К посту выше...

Цитата:

все числа будут ровным слоем размазаны по таблице $10\times10$

Это конечн ляпсус... Цифра 1 будет равномерно размазана по 1-й и 10-строкам, цифра 2 - по 2-й и 9-й строкам итд... Т.е. даже в этом случае (нецелочисленное) решение будет содержать существенную информацию

[vicvolf]

mihaild в сообщении #1679453 писал(а):

И откуда взялась какая-то "игра $2 \times 10$"?

Наверно мною допущена терминологическая неточность. Конечно, матричная игра $2 \times 10$ - это когда один игрок имеет 2 стратегии, а второй - 10. В данном случае я имел в виду обозначение здесь:

12d3 в сообщении #1678891 писал(а):

Рассмотрим горизонтальную полоску 2х10 с наименьшей суммой, которая не превосходит 1010. Выбирая в каждом столбике из двух клеток наименьшее число, получим путь с суммой, не превосходящей $\frac{1010 - 10}{2} = 500$.

Просто хотел сказать, что на части шахматной доски 2х10 числа могут быть расположены в виде "змейки", а на другой части 8х10 они могут быть расположены по-другому. Тогда у короля может быть маршрут с суммой меньше 500. Поэтому важно, что делается на другой части доски.

[Alex Krylov]

Несколькими постами выше в тексте имеются опечатки:

Вот это

Цитата:

$\sum\limits_{i=1}^{N!}\operatorname{tr}(W^TX_i)\xi_i = 6\xi_1 + 6\xi_2 + 18\xi_3 + 15\xi_4 + 15\xi_5 + 12\xi_6$
Оптимальное (нецелочисленное) решение:
$X_{opt} = \frac{1}{2}(X_1+X_2) = \begin{bmatrix}0&1&0\\0.5&0&0.5\\0.5&0&0.5\end{bmatrix}$

следует читать, как это:

Цитата:

$\sum\limits_{i=1}^{N!}\operatorname{tr}(W^TX_i)\xi_i = 18\xi_1 + 6\xi_2 + 6\xi_3 + 15\xi_4 + 15\xi_5 + 12\xi_6$
Оптимальное (нецелочисленное) решение:
$X_{opt} = \frac{1}{2}(X_2+X_3) = \begin{bmatrix}0&0.5&0.5\\1&0&0\\0&0.5&0.5\end{bmatrix}$