Temat: Czy istnieje algorytm rozwiązujący układ równań liniowych...

Czy znacie jakiś algorytm który rozwiązuje układ równań liniowych o (tylko) binarnych niewiadomych, gdzie wszystkie współczynniki przed zmiennymi są również tylko binarne, czyli ze zbioru {0,1}. Dodam, że układ równań może nie być pełny, ale na pewno nie jest sprzeczny.

przykład :

x1+x2 =1
x1+x2+x3 =2
x4+x5 =2
x4+x5+x6=2

wynik : x1=??; x2=??; x3=1; x4=1; x5=1; x6=0

znalazłem pakiet do 'integer programming' :

http://cran.r-project.org/web/packages/Rglpk/Rglpk.pdf

Jednak pakiet 'Rglpk' służy do minimalizacji/maksymalizacji zadanej funkcji zmiennych Xi, a ja nie chcę min/max, chcę tylko rozwiązać układ równań, na tyle, na ile jest on rozwiązywalny (jak w przykładzie). Czy można w jakiś sposób sprowadzić zadanie max/min do zadania które ja chcę rozwiązać ?

Przykład tego co może rozwiązać 'Rglpk':

## Simple linear program.
## maximize: 2 x_1 + 4 x_2 + 3 x_3
## subject to: 3 x_1 + 4 x_2 + 2 x_3 == 6
## 2 x_1 + x_2 + x_3 == 4
## x_1 + 3 x_2 + 2 x_3 == 8
## x_1, x_2, x_3 są binarnymi zmiennymi

ps. dodam, że złożoność czasowa rozwiązania zadania chyba nie jest zbyt ważna, gdyż każde z równań zawiera średnio tylko około 4 zmiennych, jednak ilość samych równań może być dosyć dużaKamil Bęczyński edytował(a) ten post dnia 24.02.11 o godzinie 00:33

Temat: Czy istnieje algorytm rozwiązujący układ równań liniowych...

witaj,

nie wiem czy dobrze rozumiem problem. ale czy nie chodzi o cos takiego:

library(limSolve)
a<-matrix(c(1,1,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,0,1,1,0,0,0,1),nrow=4,ncol=6)

> b <- c(1,2,2,2)
> Solve(a,b)
[1] 0.5 0.5 1.0 1.0 1.0 0.0

Temat: Czy istnieje algorytm rozwiązujący układ równań liniowych...

Już wcześniej oglądałem tę funkcję, byłeś blisko, jednak zmienne niewiadome muszą być ze zbioru {0,1}, a takiego ograniczenia nie da się ustawić. Wypróbowywałem już tę funkcję, przy mniejszej liczbie równań niż zmiennych i niestety część zmiennych ma właściwe wartość (bliskie 0 lub 1), jednak część ma wartości zupełnie niewłaściwe, np. 1.25 zamiast 0, więc intuicyjna/chałupnicza metoda z zaokrąglaniem nie działa.

Udało mi się w końcu napisać algorytm, ale chyba jeszcze nie skaluje się dobrze.

Poprawiłem swego pierwszego posta, żeby był bardziej jasny.Kamil Bęczyński edytował(a) ten post dnia 24.02.11 o godzinie 00:34

Temat: Czy istnieje algorytm rozwiązujący układ równań liniowych...

Jeżeli masz równanie:

f(x) = 2x+3 = 0 <=> (2x+3)^2 = 0 <=> min(2x+3)^2

Jeżeli jest układ równań, to można to zamienić na szukanie minimum(maksimum):
min suma(fi^2)
gdzie fi to poszczególne równania.

Zastosowana w tym przypadku funkcja potęgowa (podnoszenie do kwadratu) oraz sumowanie składników jest arbitrarnym wyborem. Równie dobrze(?) można by wybrać moduł albo jeszcze inną przyjmującą jedynie dodatnie (poza zerem) wartości funkcję.
Podobnie sumowanie składników można by zastąpić np. maksimum ze składowych.

Temat: Czy istnieje algorytm rozwiązujący układ równań liniowych...

Wojciech Sobala:
Jeżeli masz równanie:

f(x) = 2x+3 = 0 <=> (2x+3)^2 = 0 <=> min(2x+3)^2

Jeżeli jest układ równań, to można to zamienić na szukanie minimum(maksimum):
min suma(fi^2)
gdzie fi to poszczególne równania.

Zastosowana w tym przypadku funkcja potęgowa (podnoszenie do kwadratu) oraz sumowanie składników jest arbitrarnym wyborem. Równie dobrze(?) można by wybrać moduł albo jeszcze inną przyjmującą jedynie dodatnie (poza zerem) wartości funkcję.
Podobnie sumowanie składników można by zastąpić np. maksimum ze składowych.

Tak to dobre rozwiązanie, niestety problemem jest to, że układy równań do rozwiązania mają około 60 i więcej zmiennych, poza tym, układ równań jest niepełny co powoduje, problem, gdyż chcę otrzymać wartości zmiennych które są jednoznacznie identyfikowalne przykładowy problem : x1+x2=1, x1 i x2 nie występują w innych równaniach, wtedy min (x1+x2-1)^2 nie jest jednoznaczna.
Równań ze zmiennymi nieidentyfikowalnymi nie da się łatwo usunąć, gdyż na przykład cały podukład równań dla zmiennych x1,x2,x3 może mieć postać x1+x3=1, x2+x3=1, dlatego metody oparte na minimalzacji/maksymalizacji funkcji celu odrzuciłem.Kamil Bęczyński edytował(a) ten post dnia 24.02.11 o godzinie 15:09