Вырожденная система линейных уравнений. Как решить?

[glukmaker]

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

Например в системе:
$x_1+x_2+x_3+x_4=5$
$x_1+x_2=5$

Понятно что $x_3=0$ и $x_4=0$

Что можно применить для решения таких систем? Метод перебора не подходит, из-за огромного кол-ва вариантов.
Какие есть для подобных задач численные методы/алгоритмы? Или что вы можете посоветовать?

[EXE]

Как можно понять, коэффициенты Вам известны, чем тогда плох тот же метод Гаусса? Что касается появления свободных переменных в процессе решения, то перебор вариантов решения несложно программируется, потому что у Вас будет четверичная система счисления, и количество решений будет конечным. То есть, Вы можете сначала оценить количество всех решений сверху, исходя из количества разрядов, а потом из него выбрать подходящие. Не кажется сложным.

[glukmaker]

EXE в сообщении #1128067 писал(а):

Как можно понять, коэффициенты Вам известны, чем тогда плох тот же метод Гаусса?

Коэффициенты-то известны, но среди них очень много нулевых. И количество уравнений часто бывает что составляет 20-30% от количества переменных.
А перебор вариантов... допустим у меня 40 переменных, по 2 бита на каждую, итого 80 битов. Перебирать такое нереально. Ибо это такое громадное число вариантов (как минимум с 24 нулями), и еще каждый нужно проверить чтобы он не противоречил системе.

[EXE]

Вы говорите о количестве свободных переменных?
Что Вас смущает в большом количестве нулевых коэффициентов?
Обоснуйте, пожалуйста, чётче проблему с битами и с 24 нулями.
И каким образом из моего сообщения можно сделать вывод о предложении перебора?

[Octagon]

(Оффтоп)

glukmaker в сообщении #1128046 писал(а):

Например в системе:
$x_1+x_2+x_3+x_4=5$
$x_1+x_2=5$

Понятно что $x_3=0$ и $x_4=0$

Вообще-то, понятно, что $x_3=-x_4$.

А на самом деле все совсем просто.
Учебник по линейной алгебре удовлетворит ваши потребности на 100%. Оттуда вы узнаете как выглядит общее решение для любой системы линейных уравнений, на что оно натягивается и кучу других интересных вещей.


Также, я прикинул, что любая реализация библиотек aka матлаба, которая сейчас есть почти в любом языке, сведёт вашу работу к минимуму.

[Утундрий]

(Оффтоп)

Octagon в сообщении #1128168 писал(а):

Вообще-то, понятно, что $x_3=-x_4$.

glukmaker в сообщении #1128046 писал(а):

Значения переменных ограничены, и могут быть целыми числами от 0 до 3

[mihaild]

Совсем без перебора не получится, т.к. вопрос о существовании гамильтонова цикла в графе с $v$ и $e$ ребрами сводится к такой системе с $v$ уравнениями и $e$ неизвестными: неизвестные - ребра, $0$, если соответствующее ребро не берем, $1$, если берем. Уравнения - сумма переменных, соответствующих ребрам, инцидентным каждой вершине, равна $2$. Ограничение на количество - $v$ единиц, $e - v$ нулей.

edit: бред (см. ниже)

[NSKuber]

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

Уравнения - сумма переменных, соответствующих ребрам, инцидентным каждой вершине, равна $2$.

С такими уравнениями решение системы не обязано быть гамильтоновым циклом.

[mihaild]

А если так?
Взяли граф, хотим найти независимое множество из $n$ вершин. Взяли по переменной $x_i$ для каждой вершины (будет $0$, если вершина не входит в множество, и $1$, если входит), $y_j$ для каждого ребра (будет $0$, если одна из инцидентных ребру вершин входи в множество, $1$, если не входит).
Для каждого ребра $k$, соединяющего вершины $i$ и $j$ пишем $x_i + x_j + y_k = 1$. Пишем уравнение $\sum\limits_i x_i = n$. Далее перебираем все варианты, сколько нулей среди значений переменных (число вариантов линейно по размеру графа).
Делаем независимое множество из решения: берем все вершины, соответствующие равным единице $x$. Оно независимо, т.к. если бы вершины $i$ и $j$ из него соединялись ребром $k$, то было бы $x_i + x_j + y_k \geqslant 2$.
Делаем решение из независимого множества: говорим, что у нас число единиц равно $n$ плюс число ребер, не соединенных ни с одной вершиной из независимого множества. Если $i$-я вершина принадлежит множеству, берем $x_i = 1$, иначе $x_i = 0$. Для ребер, не соединенных ни с одной вершиной множества, берем $y = 1$, для остальных $y = 0$. Все уравнения выполняются, ограничение на количество тоже.

[NSKuber]

mihaild
Теперь очень даже правдоподобно.
Да, сложная задача получается.

[Vince Diesel]

glukmaker в сообщении #1128046 писал(а):

Или что вы можете посоветовать?

Системы компьютерной алгебры. Можно попробовать впрямую решать. А еще они линейные целочисленные системы $\mod\ 4$ умеют решать эффективно. Давая ответ в параметрическом виде, типа $(c_1+2 c_2,0,1,c_2,\dots)$. Переменные, на чьих местах нет параметров, и принимают только одно значение. Правда, потом придется выяснять, нет ли других таких переменных, поскольку решений исходной системы может быть меньше. И вообще, является ли какое-либо из полученных решений решением исходной системы. Если решений не очень много (скажем, порядка $10^7$), то проверить вполне реально.

[mserg]

Для данного варианта потребуется эффективный решатель целочисленных линейных задач (ЦЛЗ). Из бесплатных или условно бесплатных могу посоветовать CBC и SCIP.

Алгоритм следующий.
1. Решить исходную задачу ЦЛЗ.
2. Если решений нет, то конец.
3. Если решение есть, то обозначим допустимое решение через $y_j$
4. Для каждой переменной $x_j$ рассмотреть два варианта, когда $x_j>y_j$ и $x_j<y_j$.
5. Для каждого варианта решить задачу ЦЛЗ. Если есть хотя бы одно решение, то $x_j$ неоднозначна. Если нет, - то однозначна.

Описанный алгоритм может быть усовершенствован. Например,
* найденные однозначные переменные сразу фиксировать.
* если в любом найденном допустимом решении п.5 некоторая переменная отличается от решения п.2, то такая переменная неоднозначна и, если она не рассматривалась в п. 4 и п. 5, то и не нужно рассматривать.

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