Система линейных уравнений и неравенств

[unsa]

Добрый день.
Оригинальная задача:
Дан направленный ациклический граф с единственной точкой входа A (нет входящих ребр) и единственной точкой выхода B (нет исходящих ребр). Для каждого ребра указаны его min и max веса (не отрицательные). Также дан некий общий вес W. Необходимо определить веса x всех ребер (с учетом их min и max) так, чтобы вес любого маршрута из A в B был равен W.
Кроме того, заданы несколько желаемых (могут быть невыполнимы из-за ограничений на веса ребр) соотношений весов ребр вида $\frac{x_a}{L_a} = \frac{x_b}{L_b} = \dots \frac{x_c}{L_c}$.
Примечание 1: Если из-за соотношений весов вес ребра выходит за его допустимые границы, то вес этого ребра следует принять равным соответствующей границе (min или max) и исключить это ребро из желаемых соотношений весов (тем не менее, остальные пропорции должны сохраняться как и вес маршрута A->B).
Примечание 2: Если не учитывать направления ребр, то граф может содержать циклы.

Вот к чему свел:
$x_1 \dots x_n$ - искомые неизвестные
Дано:
1) система линейных уравнений

$$\left\{ \begin{array}{rcl} k_{1,1} \cdot x_1 + \dots + k_{1,n} \cdot x_n &=& w_1 \\ \dots \\ k_{m,1} \cdot x_1 + \dots + k_{m,n} \cdot x_n &=& w_m \\ \end{array} \right.$$

(k и w известны).
, причем $m<n$
Если это поможет, то можно представить эту систему в виде

$$\left\{ \begin{array}{rcl} K_{1,1} \cdot x_1 + \dots + K_{1,n} \cdot x_n &=& W \\ \dots \\ K_{m,1} \cdot x_1 + \dots + K_{m,n} \cdot x_n &=& W \\ \end{array} \right.$$

, причем K = 0 или K = 1, т.е. сумма некоторых равна константе, W \geqslant 0.

2) ограничения на каждую переменную (система неравенств)

$$\left\{ \begin{array}{rcl} \min_1 \leqslant x_1 \leqslant \max_1 \\ \dots \\ \min_n \leqslant x_n \leqslant \max_n \\ \end{array} \right.$$

(min и max известны)
, причем в совокупности с системой "1" имеется хотя бы одно решение (а как правило их больше одного), \min \geqslant 0.

3) система линейных уравнений

$$\left\{ \begin{array}{rcl} l_{1,1} \cdot x_1 + \dots + l_{1,n} \cdot x_n &=& 0 \\ \dots \\ l_{p,1} \cdot x_1 + \dots + l_{p,n} \cdot x_n &=& 0 \\ \end{array} \right.$$

(l известны)
, причем $m+p > n$ (если говорить более детально, то в каждом из этих уравнений строго 2 ненулевых коэффициента l). На самом деле эти уравнения получены из заданных соотношений вида $\frac{x_a}{L_a} = \frac{x_b}{L_b} = \dots \frac{x_c}{L_c}$

Задача:
найти такие $x_1 \dots x_n$, что:
- все уравнения из "1" строго выполняются
- все ограничения из "2" строго выполняются
- максимальное количество уравнений из "3" выполняются (уравнения в "3" приведены в порядке их "предпочтительности", т.е. в случае необходимости исключать их следует начиная с последнего).

В первую очередь интересует решение в целых числах, при этом уравнения из "3" (или часть из них) могут выполняться не строго, а с некой погрешностью. Во вторую - решение в нецелых, при этом уравнения из "3" (или часть из них) должны строго выполняться.

Проблемы:
Не ясно что делать с min & max: без них все сводится к системе линейных уравнений, в которой, правда, могут быть противоречия (желаемые соотношения весов могут иметь противоречия друг с другом) с которыми тоже надо что-то делать. Кроме того, количество ребер может исчисляться тысячами и требуется пересчитывать веса до пары сотен раз в секунду (граф меняется редко, обычно только W).
Буду рад подсказкам.

[пианист]

Первый вариант задача целочисленного ЛП.
Систему $3)$ заменяете, соответственно, на неравенства.
Насколько компьютер "потянет" Вашу задачу, не могу сказать, надо пробовать.
Закиньте в какой-нибудь пакет, типа glpk.
Второй вариант как-то не соображу, как можно формализовать "уравнения из "3" (или часть из них) должны строго выполняться" - только если все. Будет просто задача ЛП, она-то точно должна за разумное время считаться.
Можно еще подумать в сторону как-нибудь свести к задачам ЛП специального вида, типа min-cost-flow, для таких есть существенно более быстрые алгоритмы.

[worm2]

На ЗЛП не очень похоже, потому что не видать целевой функции (которую нужно минимизировать или максимизировать).

Ну, точнее, можно попробовать увидеть. Если все левые части в 3) возвести в квадрат и просуммировать. Или модули просуммировать. И сумму объявить целевой функцией, подлежащей минимизации. Только, во-первых, она линейной не будет. Если в квадрат возводить, то получается классическая задача квадратичного программирования с ограничениями. Есть методы для её решения, и программные пакеты тоже есть. А во-вторых, ну решим мы эту ЗКП, получим, что 3) выполняется с какими-то погрешностями, но, боюсь, что ни одно уравнение в точности не выполняется, а тут нужно, чтобы хоть какие-то точно выполнились. Ну и в-третьих, дискретность (целочисленность) всё портит, градиентные методы стройными рядами отправляются на север. Не выходит каменный цветок

[Sender]

worm2 в сообщении #1235100 писал(а):

На ЗЛП не очень похоже, потому что не видать целевой функции (которую нужно минимизировать или максимизировать).

Эм, что нам мешает взять, например, любое $x$ и оптимизировать его?

[пианист]

glpk, например, отсутствие minimize/maximize ни разу не смущает.
Типа, равна 0.

[unsa]

Спасибо всем за участие, но если честно, я не понял как сюда привязать ЗЛП, ведь в ней нужно находить минимум некой функции.
Зато я сделал следующее наблюдение: если получится решить в нецелых, то получить решение в целых из него будет легко.
Хочу сделать некоторые допущения, может быть тогда станет ясно как решать:
1. Решать можно и в нецелых,
2. Забыть на ограничения переменных сверху (т.е. от 2) остается только $\min_i \leqslant x_i$),
3. Считать что 3) дополняют 1) до n непротиворечивых уравнений (т.е. 1) + 3) имеют однозначное решение).
Текущая проблема:
После решения системы 1) + 3) получаем некое решение. Что делать, если некие $x_i<\min_i$? Взять все $x_i=\min_i$ в общем случае нельзя (легко построить пример, опровергающий такое способ). Что с этим делать? Вероятно, надо нужно взять некоторые (не всегда все) $x_i=\min_i$, заменить ими некоторые (какие пока не ясно) уравнения в 3) и повторить снова решать систему 1) + 3). Есть идеи?

[worm2]

Можно попробовать такую вещь:
I) Отказываемся от последнего уравнения $l_{p,1} \cdot x_1 + \dots + l_{p,n} \cdot x_n = 0$. В результате получаем прямую в $\mathbb{R}^n$, на которой лежат решения системы 1)+3): $\overrightarrow{x}=\overrightarrow{a}+\overrightarrow{b}\cdot t,\,t \in \mathbb{R}$.
II) На этой прямой отмечаем точки, соответствующие $x_i=\min_i$. Выбираем из них точку, в которой выполняется максимальное число ограничений 2). Пусть это точка, в которой $x_j=\min_j$. Фиксируем $x_j=\min_j$. Если какие-то ограничения в 2) ещё не выполнены, повторяем итерацию для меньшего числа неизвестных.
Получается алгоритм сложности $n^4$.
Хотя, можно ещё попробовать подшаманить: не решать на каждом шаге систему полностью заново, а как-то использовать информацию, полученную на предыдущем шаге. Я пока не соображу, как это сделать, нужно препарировать метод Гаусса. Но если получится, то будет $n^3$.

[Sender]

unsa в сообщении #1235724 писал(а):

Спасибо всем за участие, но если честно, я не понял как сюда привязать ЗЛП, ведь в ней нужно находить минимум некой функции.

Собственно, тут от ЗЛП требуется только алгоритм поиска опорного решения, разве нет?

[пианист]

unsa в сообщении #1235724 писал(а):

Спасибо всем за участие, но если честно, я не понял как сюда привязать ЗЛП, ведь в ней нужно находить минимум некой функции.

А что Вас смущает? Ну, положите эту функцию равной $0$.
glpk, повторюсь, целевая функция не обязательна, он и без нее чудненько все считает.
Думаю, что и другие пакеты так же.

unsa в сообщении #1235724 писал(а):

Зато я сделал следующее наблюдение: если получится решить в нецелых, то получить решение в целых из него будет легко.

Ну, значит, Вам повезло, у Вас "хорошая" задача.
Обычно так не бывает.

unsa в сообщении #1235724 писал(а):

3. Считать что 3) дополняют 1) до n непротиворечивых уравнений (т.е. 1) + 3) имеют однозначное решение).

А если такой вариант: считать целевой функцией сумму модулей левых частей $3)$?
Если Вам целочисленность не обязательна, получаем просто задачу ЛП.

[пианист]

Если все-таки нужно, чтобы те из уравнений $3)$, которые выполняются, выполнялись точно, то тоже можно, но тогда надо вводить бинарные переменные (грубо говоря, маркеры ноль-не ноль, сумму их устремляем к минимуму), т.е. опять-таки целочисленная задача :(
Вообще, конечно, я бы покрутил разные варианты и посмотрел результат.